[PATCH 4 of 5] topoiter: support for noncontiguous revset
PierreYves David
pierreyves.david at enslyon.org
Tue Nov 18 17:56:10 CST 2014
# HG changeset patch
# User PierreYves David <pierreyves.david at fb.com>
# Date 1409850336 7200
# Thu Sep 04 19:05:36 2014 +0200
# Node ID 026932aa1c4f05cf930c5853ae894636399de111
# Parent ee131567469924b1642956ad5adfa9f6122ba6d3
topoiter: support for noncontiguous revset
The algorithm now work when some revision are skipped. We now use "first
included ancestors" instead of just "parent" to link changesets with each other.
diff git a/mercurial/graphmod.py b/mercurial/graphmod.py
 a/mercurial/graphmod.py
+++ b/mercurial/graphmod.py
@@ 18,17 +18,17 @@ Data depends on type.
"""
from mercurial.node import nullrev
import util
+import heapq
+
CHANGESET = 'C'
def topoiter(revs, parentsfunc):
"""topologically iter over a set of revision, one branch at a time.
 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.
@@ 89,20 +89,31 @@ def topoiter(revs, parentsfunc):
# and the <blocked> set contains the parents revisions of already emitted
# revision.
#
# You could preseed 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:
 # Look for a group awaiting on the current revision.
 matching = [i for i, g in enumerate(groups) if current in g[1]]
+ 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 group awaiting on the current revision.
+ matching = [i for i, g in enumerate(groups) if rev in g[1]]
if matching:
# The main idea is to gather together all set that await on the
# same revision.
#
@@ 128,23 +139,29 @@ def topoiter(revs, parentsfunc):
for i in reversed(matching):
del groups[i]
else:
# his is a new head we create a new group for it.
targetidx = len(groups)
 groups.append(([], set([current])))
+ groups.append(([], set([rev])))
gr = groups[targetidx]
# We now adds the current nodes to this groups. This is done after
# the group merging because all elements from a group 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 group 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
@@ 173,10 +190,15 @@ def topoiter(revs, parentsfunc):
# unless it is group[0] in which case you just empty it.
if targetidx:
del groups[targetidx]
else:
gr[0][:] = []
+ # Check if we have some group 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/testglogtopological.t b/tests/testglogtopological.t
 a/tests/testglogtopological.t
+++ b/tests/testglogtopological.t
@@ 35,10 +35,13 @@ later.
 
o  1
/
o 0
+
+(display all nodes)
+
$ hg config experimental.graphtopological=1 log G
o 8

o 3

@@ 54,5 +57,24 @@ later.
 
 o 4
/
o 0
+
+(revset skipping nodes)
+
+ $ hg config experimental.graphtopological=1 log G rev 'not (2+6)'
+ o 8
+ 
+ o 3
+ 
+ o 1
+ 
+  o 7
+  
+  o 5
+  
+  o 4
+ /
+ o 0
+
+
More information about the Mercurialdevel
mailing list