Repair ancestor logic, fix up test cases

tests/test-merge7

@@ -0,0 +1,66 b''
+#!/bin/sh
+
+# initial
+hg init test-a
+cd test-a
+cat >test.txt <<"EOF"
+1
+2
+3
+EOF
+hg add test.txt
+hg commit -m "Initial" -d "0 0"
+
+# clone
+cd ..
+hg clone test-a test-b
+
+# change test-a
+cd test-a
+cat >test.txt <<"EOF"
+one
+two
+three
+EOF
+hg commit -m "Numbers as words" -d "0 0"
+
+# change test-b
+cd ../test-b
+cat >test.txt <<"EOF"
+1
+2.5
+3
+EOF
+hg commit -m "2 -> 2.5" -d "0 0"
+
+# now pull and merge from test-a
+hg pull
+HGMERGE=merge hg update -m
+# resolve conflict
+cat >test.txt <<"EOF"
+one
+two-point-five
+three
+EOF
+rm -f *.orig
+hg commit -m "Merge 1" -d "0 0"
+
+# change test-a again
+cd ../test-a
+cat >test.txt <<"EOF"
+one
+two-point-one
+three
+EOF
+hg commit -m "two -> two-point-one"
+
+# pull and merge from test-a again
+cd ../test-b
+hg pull
+HGMERGE=merge hg update --debug -m
+
+cat test.txt
+
+hg debugindex .hg/data/test.txt.i
+
+hg log

tests/test-merge7.out

@@ -0,0 +1,69 b''
+pulling from /tmp/hgtests.12359.29374.16319.16463/test-merge7/test-a
+searching for changes
+adding changesets
+adding manifests
+adding file changes
+added 1 changesets with 1 changes to 1 files (+1 heads)
+(run 'hg update' to get a working copy)
+merge: warning: conflicts during merge
+merging test.txt
+merging test.txt failed!
+pulling from /tmp/hgtests.12359.29374.16319.16463/test-merge7/test-a
+searching for changes
+adding changesets
+adding manifests
+adding file changes
+added 1 changesets with 1 changes to 1 files (+1 heads)
+(run 'hg update' to get a working copy)
+merge: warning: conflicts during merge
+resolving manifests
+ force None allow 1 moddirstate True linear False
+ ancestor 055d847dd401 local 2eded9ab0a5c remote 84cf5750dd20
+ test.txt versions differ, resolve
+merging test.txt
+resolving test.txt
+file test.txt: my fc3148072371 other d40249267ae3 ancestor 8fe46a3eb557
+merging test.txt failed!
+one
+<<<<<<< /tmp/hgtests.12359.29374.16319.16463/test-merge7/test-b/test.txt
+two-point-five
+=======
+two-point-one
+>>>>>>> /tmp/test.txt~other.bN33Pl
+three
+   rev    offset  length   base linkrev nodeid       p1           p2
+     0         0       7      0       0 01365c4cca56 000000000000 000000000000
+     1         7       9      1       1 7b013192566a 01365c4cca56 000000000000
+     2        16      15      2       2 8fe46a3eb557 01365c4cca56 000000000000
+     3        31      27      2       3 fc3148072371 7b013192566a 8fe46a3eb557
+     4        58      25      4       4 d40249267ae3 8fe46a3eb557 000000000000
+changeset:   4:50aec39675ea
+tag:         tip
+parent:      2:96b70246a118
+user:        test
+date:        Mon Sep 26 23:50:15 2005 +0000
+summary:     two -> two-point-one
+
+changeset:   3:50c3a7e29886
+parent:      1:d1e159716d41
+parent:      2:96b70246a118
+user:        test
+date:        Thu Jan  1 00:00:00 1970 +0000
+summary:     Merge 1
+
+changeset:   2:96b70246a118
+parent:      0:b1832b9d912a
+user:        test
+date:        Thu Jan  1 00:00:00 1970 +0000
+summary:     Numbers as words
+
+changeset:   1:d1e159716d41
+user:        test
+date:        Thu Jan  1 00:00:00 1970 +0000
+summary:     2 -> 2.5
+
+changeset:   0:b1832b9d912a
+user:        test
+date:        Thu Jan  1 00:00:00 1970 +0000
+summary:     Initial
+

mercurial/revlog.py

@@ -439,24 +439,45 b' class revlog:'
                 if n not in seen:
                     seen[n] = 1
                     r = self.rev(n)
-                    yield (-d, r, n)
+                    yield (-d, n)
                     for p in self.parents(n):
                         heapq.heappush(h, (-dist[p], p))
 
-        x = ancestors(a)
-        y = ancestors(b)
-        lx = x.next()
-        ly = y.next()
+        def generations(node):
+            sg, s = None, {}
+            for g,n in ancestors(node):
+                if g != sg:
+                    if sg:
+                        yield sg, s
+                    sg, s = g, {n:1}
+                else:
+                    s[n] = 1
+            yield sg, s
+
+        x = generations(a)
+        y = generations(b)
+        gx = x.next()
+        gy = y.next()
 
         # increment each ancestor list until it is closer to root than
         # the other, or they match
         while 1:
-            if lx == ly:
-                return lx[2]
-            elif lx < ly:
-                ly = y.next()
-            elif lx > ly:
-                lx = x.next()
+            #print "ancestor gen %s %s" % (gx[0], gy[0])
+            if gx[0] == gy[0]:
+                # find the intersection
+                i = [ n for n in gx[1] if n in gy[1] ]
+                if i:
+                    return i[0]
+                else:
+                    #print "next"
+                    gy = y.next()
+                    gx = x.next()
+            elif gx[0] < gy[0]:
+                #print "next y"
+                gy = y.next()
+            else:
+                #print "next x"
+                gx = x.next()
 
     def group(self, linkmap):
         """calculate a delta group

tests/test-up-local-change.out

@@ -15,7 +15,7 b' remote created b'
 getting b
 merging a
 resolving a
-file a: other d730145abbf9 ancestor b789fdd96dc2
+file a: my b789fdd96dc2 other d730145abbf9 ancestor b789fdd96dc2
 resolving manifests
  force None allow 1 moddirstate True linear True
  ancestor 1165e8bd193e local 1165e8bd193e remote 1165e8bd193e