Interested in working on Partial Cloning

[Peter Arrenbrecht]

On Fri, Mar 27, 2009 at 6:59 PM, Madhusudan C.S <madhusudancs at gmail.com> wrote:
> 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

Good.

>
> On Thu, Mar 26, 2009 at 12:34 PM, Peter Arrenbrecht
> <peter.arrenbrecht at gmail.com> wrote:
>> 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

Yep.

> From what I understood from this code snippet, mercurial first
> iterates over ancestors backwards on both Working Copy and
> the other branch to be merged until the ancestors have the
> same depth in the decreasing order of depth to the root. Once
> the depth is same it takes the list of ancestors in the Working
> Copy with that particular depth one by one and checks to
> see if that Ancestor is also an ancestor of the other branch.
>
> So for the example given by Matt, let me try to explain
> what I understood (please correct me if I am wrong)
> a(r0) - b(1) - c(4) (default branch)
>  \         X
>  d(2) - e(3) - f(5) (say branch new)
>
> If I now want to merge c and f say, which have 2 common
> ancestors b and e which are not the ancestors of one
> another, I will have e as the common ancestor of c and f
> with highest depth to the root (i.e -2), so e will be chosen
> as the common ancestor for the 3-way merge over e, since
> Hope this is correct?
>
> Same is the case if I am on branch "new" too. e(3) will be
> chosen.

Sounds right.

>>
>> Can we shallow clone
>> such that the one Mercurial would normally choose is not present?
>
>
> From what I analyzed, say we shallow clone single rooted
> node c we anyways have no idea about what is happening on branch
> "new" at all, but if we shallow clone at b(1), we are first of all
> screwed at c, since we are not having any info about e(3), for
> the merge.

Right.

> So with current implementation and logic it is not possible
> at all. But I strongly feel we can think of a way to just keep c(4)
> happy and shallow clone the rest as it is(say probably informing user
> that you will screw your repo if you don't allow this, so please
> let us get the minimum required changeset e(3) to keep c(4)
> happy? If he still says "No I cannot", I think the solution can be to
> to have merged c(4), with one of its parent pointing to NullRev
> and thereby further not allowing any further merges, that may
> require e(3). But I don't see any such situation cropping up, since
> we anyways have a single branch at this point after shallow
> clone?
> Kindly correct me if I am wrong.

My intention was to forbid merges when the path to the chosen ancestor
involves a partial node. Because I think only then could there have
been another, closer ancestor in the full repo (haven't thought about
this in detail, much less tried to prove it so far). Have also not
thought about how to follow this path efficiently yet.

And then we would reallow such merges using the --force option.

-parren