diff hgext/convert/convcmd.py @ 6100:49c69e1e4aa2

convert: fix --datesort ordering

Two branches a and b starting at root, with commits interleaved like:
root a0 a1 b0 a2 a3 b1
were converted in the following order:
root a0 b0 a1 b1 a2 a3

Replace depth based toposort with a more classic traversal method.

--- a/hgext/convert/convcmd.py	Tue Dec 18 14:01:34 2007 -0600
+++ b/hgext/convert/convcmd.py	Sat Feb 16 11:55:33 2008 +0100
@@ -110,6 +110,7 @@
         visit = parents.keys()
         seen = {}
         children = {}
+        actives = []
 
         while visit:
             n = visit.pop(0)
@@ -118,49 +119,59 @@
             # Ensure that nodes without parents are present in the 'children'
             # mapping.
             children.setdefault(n, [])
+            hasparent = False
             for p in parents[n]:
                 if not p in self.map:
                     visit.append(p)
+                    hasparent = True
                 children.setdefault(p, []).append(n)
+            if not hasparent:
+                actives.append(n)
+
+        del seen
+        del visit
+
+        if self.opts.get('datesort'):
+            dates = {}
+            def getdate(n):
+                if n not in dates:
+                    dates[n] = util.parsedate(self.commitcache[n].date)
+                return dates[n]
+
+            def picknext(nodes):
+                return min([(getdate(n), n) for n in nodes])[1]
+        else:
+            prev = [None]
+            def picknext(nodes):
+                # Return the first eligible child of the previously converted
+                # revision, or any of them.
+                next = nodes[0]
+                for n in nodes:
+                    if prev[0] in parents[n]:
+                        next = n
+                        break
+                prev[0] = next
+                return next
 
         s = []
-        removed = {}
-        visit = children.keys()
-        while visit:
-            n = visit.pop(0)
-            if n in removed: continue
-            dep = 0
-            if n in parents:
-                for p in parents[n]:
-                    if p in self.map: continue
-                    if p not in removed:
-                        # we're still dependent
-                        visit.append(n)
-                        dep = 1
-                        break
+        pendings = {}
+        while actives:
+            n = picknext(actives)
+            actives.remove(n)
+            s.append(n)
 
-            if not dep:
-                # all n's parents are in the list
-                removed[n] = 1
-                if n not in self.map:
-                    s.append(n)
-                if n in children:
-                    for c in children[n]:
-                        visit.insert(0, c)
+            # Update dependents list
+            for c in children.get(n, []):
+                if c not in pendings:
+                    pendings[c] = [p for p in parents[c] if p not in self.map]
+                pendings[c].remove(n)
+                if not pendings[c]:
+                    # Parents are converted, node is eligible
+                    actives.insert(0, c)
+                    pendings[c] = None
 
-        if self.opts.get('datesort'):
-            depth = {}
-            for n in s:
-                depth[n] = 0
-                pl = [p for p in self.commitcache[n].parents
-                      if p not in self.map]
-                if pl:
-                    depth[n] = max([depth[p] for p in pl]) + 1
-
-            s = [(depth[n], util.parsedate(self.commitcache[n].date), n)
-                 for n in s]
-            s.sort()
-            s = [e[2] for e in s]
+        if len(s) != len(parents):
+            raise util.Abort(_("not all revisions were sorted"))
 
         return s