Patchwork [4,of,5,V2] groupbranchiter: support for non-contiguous revset

login
register
mail settings
Submitter Pierre-Yves David
Date Dec. 2, 2014, 5:29 p.m.
Message ID <d9e86be59f0365deeca0.1417541365@marginatus.alto.octopoid.net>
Download mbox | patch
Permalink /patch/6948/
State Accepted
Commit d3d30bf2a299c2992a80460c6c7a9b6d35355219
Headers show

Comments

Pierre-Yves David - Dec. 2, 2014, 5:29 p.m.
# HG changeset patch
# User Pierre-Yves David <pierre-yves.david@fb.com>
# Date 1409850336 -7200
#      Thu Sep 04 19:05:36 2014 +0200
# Node ID d9e86be59f0365deeca01edc76c0c4aca03fe06d
# Parent  d6d5d500d40da001a3757f46e7fb43920d25df17
groupbranchiter: support for non-contiguous revset

The algorithm now work when some revisions are skipped. We now use "first
included ancestors" instead of just "parent" to link changesets with each other.

Patch

diff --git a/mercurial/graphmod.py b/mercurial/graphmod.py
--- a/mercurial/graphmod.py
+++ b/mercurial/graphmod.py
@@ -18,10 +18,12 @@  Data depends on type.
 """
 
 from mercurial.node import nullrev
 import util
 
+import heapq
+
 CHANGESET = 'C'
 
 def groupbranchiter(revs, parentsfunc):
     """yield revision from heads to roots one (topo) branch after the other.
 
@@ -38,12 +40,10 @@  def groupbranchiter(revs, parentsfunc):
       | |
       | o  2
       |/
       o  0
 
-    Currently does not handle non contigious <revs> input.
-
     Currently consider every changeset under a merge to be on the same branch
     using revision number to sort them.
 
     Could be easily extend to give priority to an initial branch."""
     ### Quick summary of the algorithm
@@ -101,20 +101,31 @@  def groupbranchiter(revs, parentsfunc):
     # were already emitted. The 'revs' lists is expected to be empty and the
     # 'blocked' set contains the parents revisions of already emitted revision.
     #
     # You could pre-seed the <parents> set of groups[0] to a specific
     # changesets to select what the first emitted branch should be.
-    #
-    # We do not support revisions will hole yet, but adding such support would
-    # be easy. The iteration will have to be done using both input revision and
-    # parents (see cl.ancestors function + a few tweaks) but only revisions
-    # parts of the initial set should be emitted.
     groups = [([], unblocked)]
-    for current in revs:
-        if True:
+    pendingheap = []
+    pendingset = set()
+
+    heapq.heapify(pendingheap)
+    heappop = heapq.heappop
+    heappush = heapq.heappush
+    for currentrev in revs:
+        # Heap works with smallest element, we want highest so we invert
+        if currentrev not in pendingset:
+            heappush(pendingheap, -currentrev)
+            pendingset.add(currentrev)
+        # iterates on pending rev until after the current rev have been
+        # processeed.
+        rev = None
+        while rev != currentrev:
+            rev = -heappop(pendingheap)
+            pendingset.remove(rev)
+
             # Seek for a subgroup blocked, waiting for the current revision.
-            matching = [i for i, g in enumerate(groups) if current in g[1]]
+            matching = [i for i, g in enumerate(groups) if rev in g[1]]
 
             if matching:
                 # The main idea is to gather together all sets that await on
                 # the same revision.
                 #
@@ -138,23 +149,29 @@  def groupbranchiter(revs, parentsfunc):
                 for i in reversed(matching):
                     del groups[i]
             else:
                 # This is a new head. We create a new subgroup for it.
                 targetidx = len(groups)
-                groups.append(([], set([current])))
+                groups.append(([], set([rev])))
 
             gr = groups[targetidx]
 
             # We now adds the current nodes to this subgroups. This is done
             # after the subgroup merging because all elements from a subgroup
             # that relied on this rev must preceed it.
             #
             # we also update the <parents> set to includes the parents on the
             # new nodes.
-            gr[0].append(current)
-            gr[1].remove(current)
-            gr[1].update([p for p in parentsfunc(current) if p > nullrev])
+            if rev == currentrev: # only display stuff in rev
+                gr[0].append(rev)
+            gr[1].remove(rev)
+            parents = [p for p in parentsfunc(rev) if p > nullrev]
+            gr[1].update(parents)
+            for p in parents:
+                if p not in pendingset:
+                    pendingset.add(p)
+                    heappush(pendingheap, -p)
 
             # Look for a subgroup to display
             #
             # When unblocked is empty (if clause), We are not waiting over any
             # revision during the first iteration (if no priority was given) or
@@ -183,10 +200,15 @@  def groupbranchiter(revs, parentsfunc):
                 # unless it is groups[0] in which case you just empty it.
                 if targetidx:
                     del groups[targetidx]
                 else:
                     gr[0][:] = []
+    # Check if we have some subgroup waiting for revision we are not going to
+    # iterate over
+    for g in groups:
+        for r in g[0]:
+            yield r
 
 def dagwalker(repo, revs):
     """cset DAG generator yielding (id, CHANGESET, ctx, [parentids]) tuples
 
     This generator function walks through revisions (which should be ordered
diff --git a/tests/test-glog-topological.t b/tests/test-glog-topological.t
--- a/tests/test-glog-topological.t
+++ b/tests/test-glog-topological.t
@@ -35,10 +35,13 @@  later.
   | |
   o |  1
   |/
   o  0
   
+
+(display all nodes)
+
   $ hg --config experimental.graph-topological=1 log -G
   o  8
   |
   o  3
   |
@@ -54,5 +57,24 @@  later.
   | |
   | o  4
   |/
   o  0
   
+
+(revset skipping nodes)
+
+  $ hg --config experimental.graph-topological=1 log -G --rev 'not (2+6)'
+  o  8
+  |
+  o  3
+  |
+  o  1
+  |
+  | o  7
+  | |
+  | o  5
+  | |
+  | o  4
+  |/
+  o  0
+  
+