[PATCH 6 of 6 RFC] shrink: add accounting of suboptimal nodes to the new algorithms

[Greg Ward]

# HG changeset patch
# User Greg Ward <greg-hg at gerg.ca>
# Date 1264042218 18000
# Node ID 4c7de048ce26047e4156fbbed3c3454944efd5e0
# Parent  e73ea6897ad92e7f56fa26d3fd4a832ca64c65ec
shrink: add accounting of suboptimal nodes to the new algorithms.

diff --git a/contrib/shrink-revlog.py b/contrib/shrink-revlog.py
--- a/contrib/shrink-revlog.py
+++ b/contrib/shrink-revlog.py
@@ -191,6 +191,7 @@
     visit = list(heads)
     visit.sort(reverse=True)
     finished = set()
+    suboptimal = p2pred = 0
 
     while visit:
         curr = visit[-1]
@@ -199,9 +200,20 @@
                 visit.append(p)
                 break
         else:
+            curparents = rl.parentrevs(curr)
+            if result and result[-1] != curparents[0]:
+                suboptimal += 1
+            if result and result[-1] == curparents[1]:
+                p2pred += 1
+
             result.append(curr)
             finished.add(curr)
             visit.pop()
+
+    ui.write('\n')
+    ui.write('%d suboptimal\n' % suboptimal)
+    ui.write('%d p2 is predecessor\n' % p2pred)
+
     return result
 
 def toposort_postorderreverse(ui, rl):
@@ -228,11 +240,13 @@
     finally:
         ui.write('\n')
 
-    ui.write('sorting ...\n')
+    ui.write('sorting ...')
     result = []
     visit = list(roots)
     visit.sort()
     finished = set()
+    suboptimal = p2pred = 0
+
     while visit:
         curr = visit[-1]
         for p in children[curr]:
@@ -240,9 +254,23 @@
                 visit.append(p)
                 break
         else:
+            # if cur is not the first parent of its successor, then the
+            # successor is a suboptimal node
+            if result:
+                succparents = rl.parentrevs(result[-1])
+                if succparents[0] != curr:
+                    suboptimal += 1
+                if succparents[1] == curr:
+                    p2pred += 1
+
             result.append(curr)
             finished.add(curr)
             visit.pop()
+
+    ui.write('\n')
+    ui.write('%d suboptimal\n' % suboptimal)
+    ui.write('%d p2 is predecessor\n' % p2pred)
+
     result.reverse()
     return result