Interested in working on Partial Cloning

[Madhusudan C.S]

Hi Peter,
  Thanks a lot for this exercise. It was an awesome
experience to read the code of mercurial and understand
how the graphs work. Really liked it a lot and also learnt
a lot of things in the process, read a lot of Mercurial code

On Thu, Mar 26, 2009 at 12:34 PM, Peter Arrenbrecht <
peter.arrenbrecht at gmail.com> wrote:

> On Tue, Mar 24, 2009 at 10:19 AM, Madhusudan C.S <madhusudancs at gmail.com>
> wrote:
> >> As I said above, not _the_ ancestor, but _a_ common ancestor that is
> >> nearer. Can you imagine and sketch such a scenario? (Try one with more
> >> than one common ancestor first. Then one where a shallow clone rooted
> >> at a particular node would be missing the nearer one. This should give
> >> you a good introduction to thinking about these DAGs. Sketching these
> >> in ASCII art is a bit of a pain, so you might want to just sketch by
> >> hand, then create the situation in a temp repo and use `hg glog` to
> >> have it ASCII-graphed for you.)
> >>
> > I made an attempt to imagine the scenario you mentioned.
> > Please tell me if I am right or correct me if I am wrong.
> > (Hopefully studying 1 full semester of Graph Theory will
> > come to my rescue ;-) )
> >
> > Scenario with multiple common ancestors
> >        d - e
> >       /
> >   b - c
> >  /     \
> > a       f - g
> >  \     /
> >   h - i - j - k
> >
> > In this scenario e and g AFAI have understood have more
> > than one common ancestors, them being a and c. We can
> > also say e g and k have multiple common ancestors. Am
> > I right?
>
> Yes, but. Since a is also an ancestor of c, I would think a merge
> would always choose c as the merge base. And there is no way you can
> shallow clone to get e, g, and a, but not c. Can you find a scenario
> where neither of the two common ancestors is an ancestor of the other?
> Can you figure out what rules Mercurial uses to choose one over the
> other when merging (by looking into the code)?


Finally after searching, thinking and putting prints at every
possible point ;-) in the code I found the actual code snippet
that Finds out the ancestor during merge. Here is the snippet
from the Mercurial Code, please tell me if I have traced it
right.

mercurial/ancestor.py
def ancestor(a, b, pfunc):
    # finding ancestors using generators(yield functions)
    # ...

    # increment each ancestor list until it is closer to root than
    # the other, or they match
    try:
        while 1:
            if gx[0] == gy[0]:
                for v in gx[1]:
                    if v in gy[1]:
                        return v
                gy = y.next()
                gx = x.next()
            elif gx[0] > gy[0]:
                gy = y.next()
            else:
                gx = x.next()
    except StopIteration:
        return None