[PATCH] branchingrev: find the start of the branch containing a node

Florent Guillaume fg at nuxeo.com
Mon Feb 25 18:10:39 CST 2008


# HG changeset patch
# User Florent Guillaume <fg at nuxeo.com>
# Date 1203984621 -3600
# Node ID 689ecf3985b1c4a6dd2321dd9f30489f0d66105e
# Parent  50a277e6ceaeaa5f890cacc9dcab745a4387dd58
branchingrev: find the start of the branch containing a node

Adding a branchingrev method on the revlog (finds the oldest revision
that has the same single head as a given revision).

Adding a foo~~ syntax for parentrevspec to return that.

diff --git a/hgext/parentrevspec.py b/hgext/parentrevspec.py
--- a/hgext/parentrevspec.py
+++ b/hgext/parentrevspec.py
@@ -22,6 +22,7 @@ For example, if you can refer to a revis
   foo~0 = foo
   foo~1 = foo^1 = foo^ = first parent of foo
   foo~2 = foo^1^1 = foo^^ = first parent of first parent of foo
+  foo~~ = start of the branch containing foo
 '''
 import mercurial.repo
 
@@ -75,6 +76,12 @@ def reposetup(ui, repo):
                     if n:
                         rev = p[n - 1]
                     i = j
+                # foo~~ = start of the branch containing foo
+                elif suffix[i:i+2] == '~~':
+                    i += 2
+                    rev = cl.branchingrev(rev)
+                    if rev is None:
+                        raise
                 # foo~N => Nth first grandparent of foo
                 # foo~0 = foo
                 # foo~1 = foo^1 == foo^ == 1st parent of foo
diff --git a/mercurial/revlog.py b/mercurial/revlog.py
--- a/mercurial/revlog.py
+++ b/mercurial/revlog.py
@@ -1077,6 +1077,55 @@ class revlog(object):
 
         return self.node(c)
 
+    def branchingrev(self, rev):
+        """Return the start of the branch containing node.
+
+        Finds the oldest revision that has the same single head as rev.
+        Returns None if rev has several heads.
+        """
+        if rev == nullrev:
+            return None
+        count = self.count()
+        if rev < 0 or rev >= count:
+            raise IndexError(rev)
+        heads = [None] * (count + 1)
+        # None = no info yet
+        # n = single head n has been found for now
+        # False = several heads have been found
+        index = self.index
+        for r in xrange(count - 1, -1, -1):
+            e = index[r]
+            h = heads[r]
+            if h is False:
+                # common case above a branching point, propage False to
+                # parents
+                heads[e[5]] = heads[e[6]] = False
+                # here we use the fact that nullrev = -1, which maps to
+                # the last element of the list, which conveniently has
+                # one slot added there (the count + 1 above)
+            else:
+                if h is None:
+                    # a new head
+                    h = heads[r] = r
+                for p in e[5:7]:
+                    if p != nullrev:
+                        ph = heads[p]
+                        if ph is None:
+                            # set current head on unvisited parent
+                            heads[p] = h
+                        elif ph != h:
+                            # more than one head for parent
+                            heads[p] = False
+        head = heads[rev]
+        if head is False:
+            # we could have inlined this test in the loops above to
+            # get faster answers but this would have optimized the
+            # unlikely case that the user asked for the branchpoint
+            # of something with more than heads, at the expense of
+            # speed in the common case
+            return None
+        return heads.index(head)
+
     def group(self, nodelist, lookup, infocollect=None):
         """calculate a delta group
 
diff --git a/tests/test-branchingrev.py b/tests/test-branchingrev.py
new file mode 100644
--- /dev/null
+++ b/tests/test-branchingrev.py
@@ -0,0 +1,90 @@
+"""
+Setup with a branching point:
+
+    >>> commit("0")
+    >>> commit("1")
+    >>> commit("2")
+    >>> commit("3")
+    >>> commit("4", 1)
+    >>> commit("5")
+
+See what we get as branch points:
+
+    >>> showinfo()
+    0 [3, 5] None
+    1 [3, 5] None
+    2 [3]    2
+    3 [3]    2
+    4 [5]    4
+    5 [5]    4
+
+Merge the fork:
+
+    >>> commit("6", 3, 5)
+    0 files updated, 0 files merged, 0 files removed, 0 files unresolved
+    >>> commit("7")
+
+New branch points:
+
+    >>> showinfo()
+    0 [7]    0
+    1 [7]    0
+    2 [7]    0
+    3 [7]    0
+    4 [7]    0
+    5 [7]    0
+    6 [7]    0
+    7 [7]    0
+
+Now add a head in the middle of the fork.
+
+    >>> commit("8", 5)
+    >>> commit("9")
+
+New branch points:
+
+    >>> showinfo()
+    0 [7, 9] None
+    1 [7, 9] None
+    2 [7]    2
+    3 [7]    2
+    4 [7, 9] None
+    5 [7, 9] None
+    6 [7]    2
+    7 [7]    2
+    8 [9]    8
+    9 [9]    8
+
+"""
+
+import os
+from mercurial import hg, ui
+
+def commit(text, p1=None, p2=None):
+    if p1 is not None:
+        hg.clean(repo, repo.changelog.node(p1), show_stats=False)
+    if p2 is not None:
+        hg.merge(repo, p2, remind=False)
+    f = file('foo', 'a')
+    f.write('\n')
+    f.close()
+    repo.commit(text=text, date="0 0")
+
+def showinfo():
+    cl = repo.changelog
+    for r in xrange(cl.count()):
+        heads = [cl.rev(h) for h in cl.heads(cl.node(r))]
+        heads.sort()
+        print "%d %-6s %s" % (r, heads, cl.branchingrev(r))
+
+if __name__ == "__main__":
+    import doctest
+
+    repo = hg.repository(ui.ui(), 'testrepo', create=True)
+    os.chdir('testrepo')
+    f = file('foo', 'w')
+    f.write('foo\n')
+    f.close()
+    repo.add(['foo'])
+
+    doctest.testmod(extraglobs=globals())
diff --git a/tests/test-parentrevspec b/tests/test-parentrevspec
--- a/tests/test-parentrevspec
+++ b/tests/test-parentrevspec
@@ -19,6 +19,15 @@ commit()
     hg commit -d '0 0' -qAm "$msg" foo
 }
 
+lookup()
+{
+    for rev in "$@"; do
+	printf "$rev: "
+	hg id -nr $rev
+    done
+    true
+}
+
 hg init repo
 cd repo
 
@@ -30,20 +39,19 @@ commit '2: change foo 2a'
 commit '2: change foo 2a'
 commit '3: change foo 3a'
 commit '4: change foo 2b' 1
+
+hg log --template '#rev#:#node|short# #parents#\n'
+echo
+
+echo 'branching points'
+lookup "0~~" "1~~" "2~~" "3~~" "4~~"
+echo
+
 commit '5: merge' 3 4
 commit '6: change foo again'
 
 hg log --template '#rev#:#node|short# #parents#\n'
 echo
-
-lookup()
-{
-    for rev in "$@"; do
-	printf "$rev: "
-	hg id -nr $rev
-    done
-    true
-}
 
 tipnode=`hg id -ir tip`
 
@@ -66,4 +74,20 @@ echo 'with a tag "foo^bar" pointing to r
 echo 'with a tag "foo^bar" pointing to rev 2'
 hg tag -l -r 2 "foo^bar"
 lookup "foo^bar" "foo^bar^"
+echo
 
+echo 'branching points after merge'
+lookup "0~~" "1~~" "2~~" "3~~" "4~~" "5~~" "6~~"
+echo
+
+commit '7: start branch' 3
+commit '8: blah on branch'
+commit '9: again'
+
+hg log --template '#rev#:#node|short# #parents#\n'
+echo
+
+echo 'branching points after new branching'
+lookup "0~~" "1~~" "2~~" "3~~" "4~~" "5~~" "6~~" "7~~" "8~~" "9~~"
+
+
diff --git a/tests/test-parentrevspec.out b/tests/test-parentrevspec.out
--- a/tests/test-parentrevspec.out
+++ b/tests/test-parentrevspec.out
@@ -1,3 +1,16 @@ 6:755d1e0d79e9
+4:bb4475edb621 1:5d953a1917d1 
+3:a3e00c7dbf11 
+2:befc7d89d081 
+1:5d953a1917d1 
+0:837088b6e1d9 
+
+branching points
+0~~: abort: unknown revision '0~~'!
+1~~: abort: unknown revision '1~~'!
+2~~: 2
+3~~: 2
+4~~: 4
+
 6:755d1e0d79e9 
 5:9ce2ce29723a 3:a3e00c7dbf11 4:bb4475edb621 
 4:bb4475edb621 1:5d953a1917d1 
@@ -42,3 +55,35 @@ with a tag "foo^bar" pointing to rev 2
 with a tag "foo^bar" pointing to rev 2
 foo^bar: 2
 foo^bar^: abort: unknown revision 'foo^bar^'!
+
+branching points after merge
+0~~: 0
+1~~: 0
+2~~: 0
+3~~: 0
+4~~: 0
+5~~: 0
+6~~: 0
+
+9:ebb5b2a4ce17 
+8:c8e3e6d2d6ef 
+7:44190156be2e 3:a3e00c7dbf11 
+6:755d1e0d79e9 
+5:9ce2ce29723a 3:a3e00c7dbf11 4:bb4475edb621 
+4:bb4475edb621 1:5d953a1917d1 
+3:a3e00c7dbf11 
+2:befc7d89d081 
+1:5d953a1917d1 
+0:837088b6e1d9 
+
+branching points after new branching
+0~~: abort: unknown revision '0~~'!
+1~~: abort: unknown revision '1~~'!
+2~~: abort: unknown revision '2~~'!
+3~~: abort: unknown revision '3~~'!
+4~~: 4
+5~~: 4
+6~~: 4
+7~~: 7
+8~~: 7
+9~~: 7


More information about the Mercurial-devel mailing list