[PATCH 1 of 2] revlog: add branchingrev(rev) to find the start of the branch containing a node

Florent Guillaume fg at nuxeo.com
Tue Feb 26 07:07:04 CST 2008


# HG changeset patch
# User Florent Guillaume <fg at nuxeo.com>
# Date 1204031074 -3600
# Node ID 5058175e99fbd7078d5ca7f37a5c03c7e0918973
# Parent  50a277e6ceaeaa5f890cacc9dcab745a4387dd58
revlog: add branchingrev(rev) to find the start of the branch containing a node

Finds the oldest revision that has the same single head as rev.
Returns None if rev has several heads.

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())


More information about the Mercurial-devel mailing list