[PATCH 4 of 5] shrink-revlog: add "reverse postorder" and "postorder reverse" toposorts

[Greg Ward]

# HG changeset patch
# User Greg Ward <greg-hg at gerg.ca>
# Date 1268187721 18000
# Node ID 64e286c22f29847dbd923799ad42dfa725c25a93
# Parent  bc81f126139f45243b6df5affd6e4eaa360a15e9
shrink-revlog: add "reverse postorder" and "postorder reverse" toposorts.

Based on a patch by Benoit Boissinot, adapted to the pluggable sort
algorithm design.  toposort_reversepostorder() is a very good
performer; it's designed to recreate what the revlog would have looked
like if Mercurial had parent deltas now.  toposort_postorderreverse()
is unstable and very inconsistent, but perhaps with some work it could
be made better.

diff --git a/contrib/shrink-revlog.py b/contrib/shrink-revlog.py
--- a/contrib/shrink-revlog.py
+++ b/contrib/shrink-revlog.py
@@ -81,6 +81,89 @@
     ui.note(_('%d suboptimal nodes\n') % suboptimal)
     return result
 
+def toposort_reversepostorder(ui, rl):
+    # postorder of the reverse directed graph
+
+    # map rev to list of parent revs (p2 first)
+    parents = {}
+    heads = set()
+    ui.status(_('reading revs\n'))
+    try:
+        for rev in rl:
+            ui.progress(_('reading'), rev, total=len(rl))
+            (p1, p2) = rl.parentrevs(rev)
+            if p1 == p2 == node.nullrev:
+                parents[rev] = ()       # root node
+            elif p1 == p2 or p2 == node.nullrev:
+                parents[rev] = (p1,)    # normal node
+            else:
+                parents[rev] = (p2, p1) # merge node
+
+            heads.add(rev)
+
+            for p in parents[rev]:
+                heads.discard(p)
+    finally:
+        ui.progress(_('reading'), None, total=len(rl))
+
+    ui.status(_('sorting revs\n'))
+    result = []
+    visit = list(heads)
+    visit.sort(reverse=True)
+    finished = set()
+
+    while visit:
+        cur = visit[-1]
+        for p in parents[cur]:
+            if p not in finished:
+                visit.append(p)
+                break
+        else:
+            result.append(cur)
+            finished.add(cur)
+            visit.pop()
+    return result
+
+def toposort_postorderreverse(ui, rl):
+    # reverse-postorder of the reverse directed graph
+
+    children = {}
+    roots = set()
+    ui.status(_('reading revs\n'))
+    try:
+        for rev in rl:
+            ui.progress(_('reading'), rev, total=len(rl))
+            (p1, p2) = rl.parentrevs(rev)
+            if p1 == p2 == node.nullrev:
+                roots.add(rev)
+
+            children[rev] = []
+
+            if p1 != node.nullrev:
+                children[p1].append(rev)
+            if p2 != node.nullrev:
+                children[p2].append(rev)
+    finally:
+        ui.progress(_('reading'), None, total=len(rl))
+
+    ui.status(_('sorting revs\n'))
+    result = []
+    visit = list(roots)
+    visit.sort()
+    finished = set()
+    while visit:
+        cur = visit[-1]
+        for p in children[cur]:
+            if p not in finished:
+                visit.append(p)
+                break
+        else:
+            result.append(cur)
+            finished.add(cur)
+            visit.pop()
+    result.reverse()
+    return result
+
 def writerevs(ui, r1, r2, order, tr):
 
     ui.status(_('writing revs\n'))