No subject


Wed Jan 7 15:56:51 UTC 2009


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. 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.



-- 
Thanks and regards,
 Madhusudan.C.S

Blogs at: www.madhusudancs.info
Official Email ID: madhusudan at madhusudancs.info

--0016362851fc38015304661ca795
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

Hi Peter,<br>=A0 Thanks a lot for this exercise. It was an awesome<br>exper=
ience to read the code of mercurial and understand<br>how the graphs work. =
Really liked it a lot and also learnt<br>a lot of things in the process, re=
ad a lot of Mercurial code<br>

<br><div class=3D"gmail_quote">On Thu, Mar 26, 2009 at 12:34 PM, Peter Arre=
nbrecht <span dir=3D"ltr">&lt;<a href=3D"mailto:peter.arrenbrecht at gmail.com=
" target=3D"_blank">peter.arrenbrecht at gmail.com</a>&gt;</span> wrote:<br><b=
lockquote class=3D"gmail_quote" style=3D"border-left: 1px solid rgb(204, 20=
4, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">

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

from the Mercurial Code, please tell me if I have traced it <br>right.<br>
<br>mercurial/ancestor.py<br>
def ancestor(a, b, pfunc):<br>
=A0=A0=A0 # finding ancestors using generators(yield functions)<br>
=A0=A0=A0 # ...<br>
=A0=A0=A0 <br>=A0=A0=A0 # increment each ancestor list until it is closer t=
o root than<br>=A0=A0=A0 # the other, or they match<br>=A0=A0=A0 try:<br>=
=A0=A0=A0=A0=A0=A0=A0 while 1:<br>=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 if gx[0=
] =3D=3D gy[0]:<br>=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 for v in g=
x[1]:<br>=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 if v in =
gy[1]:<br>

=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 retur=
n v<br>=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 gy =3D y.next()<br>=A0=
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 gx =3D x.next()<br>=A0=A0=A0=A0=
=A0=A0=A0=A0=A0=A0=A0 elif gx[0] &gt; gy[0]:<br>=A0=A0=A0=A0=A0=A0=A0=A0=A0=
=A0=A0=A0=A0=A0=A0 gy =3D y.next()<br>=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 els=
e:<br>=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 gx =3D x.next()<br>

=A0=A0=A0 except StopIteration:<br>=A0=A0=A0=A0=A0=A0=A0 return None <br></=
div><br>From what I understood from this code snippet, mercurial first <br>
iterates over ancestors backwards on both Working Copy and<br>
the other branch to be merged until the ancestors have the<br>
same depth in the decreasing order of depth to the root. Once<br>the depth =
is same it takes the list of=20
ancestors in the Working<br>Copy with that particular depth one by one and =
checks to <br>
see if that Ancestor is also an ancestor of the other branch.<br><br>
So for the example given by Matt, let me try to explain <br>
what I understood (please correct me if I am wrong)<br>
a(r0) - b(1) - c(4) (default branch)<br>

=A0\=A0=A0=A0=A0=A0=A0=A0=A0 X <br>

 =A0d(2) - e(3) - f(5)  (say branch new)<br>
<br>
If I now want to merge c and f say, which have 2 common<br>
ancestors b and e which are not the ancestors of one <br>
another, I will have e as the common ancestor of c and f<br>with highest de=
pth to the root (i.e -2), so e  will be chosen<br>as the common ancestor=20
for the 3-way merge over e, since<br>Hope this is correct? <br><br>Same is =
the case if I am on branch &quot;new&quot; too. e(3) will be<br>chosen.<br>=
=A0
<br></div><blockquote class=3D"gmail_quote" style=3D"border-left: 1px solid=
 rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"> Can we=
 shallow clone<br>
such that the one Mercurial would normally choose is not present?</blockquo=
te><div>=A0</div>From what I analyzed, say we shallow clone single rooted <=
br>node c we anyways have no idea about what is happening on branch<br>&quo=
t;new&quot; at all, but if we shallow clone at b(1), we are first of all <b=
r>
screwed at c, since we are not having any info about e(3), for<br>the merge=
. So with current implementation and logic it is not possible<br>at all. Bu=
t I strongly feel we can think of a way to just keep c(4)<br>happy and shal=
low clone the rest as it is(say probably informing user<br>
that you will screw your repo if you don&#39;t allow this, so please <br>le=
t us get the minimum required changeset e(3) to keep c(4)<br>happy? If he s=
till says &quot;No I cannot&quot;, I think the solution can be to<br>to hav=
e merged c(4), with one of its parent pointing to NullRev<br>
and thereby further not allowing any further merges, that may<br>require e(=
3). But I don&#39;t see any such situation cropping up, since<br>we anyways=
 have a single branch at this point after shallow <br>clone?<br>Kindly corr=
ect me if I am wrong. <br>
<br><br clear=3D"all"></div><br>-- <br>Thanks and regards,<br> =A0Madhusuda=
n.C.S<br><br>Blogs at: <a href=3D"http://www.madhusudancs.info" target=3D"_=
blank">www.madhusudancs.info</a><br>Official Email ID: <a href=3D"mailto:ma=
dhusudan at madhusudancs.info" target=3D"_blank">madhusudan at madhusudancs.info<=
/a><br>



--0016362851fc38015304661ca795--


More information about the Mercurial-devel mailing list