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.

tests/test-convert-datesort

@@ -0,0 +1,40 b''
+#!/bin/sh
+
+cat >> $HGRCPATH <<EOF
+[extensions]
+convert=
+graphlog=
+EOF
+
+hg init t
+cd t
+echo a >> a
+hg ci -Am a0 -d '1 0'
+hg branch brancha
+echo a >> a
+hg ci -m a1 -d '2 0'
+echo a >> a
+hg ci -m a2 -d '3 0'
+echo a >> a
+hg ci -m a3 -d '4 0'
+hg up -C 0
+hg branch branchb
+echo b >> b
+hg ci -Am b0 -d '5 0'
+hg up -C brancha
+echo a >> a
+hg ci -m a4 -d '6 0'
+echo a >> a
+hg ci -m a5 -d '7 0'
+echo a >> a
+hg ci -m a6 -d '8 0'
+hg up -C branchb
+echo b >> b
+hg ci -m b1 -d '9 0'
+cd ..
+
+echo % convert with datesort
+hg convert --datesort t t2
+echo % graph converted repo
+hg -R t2 glog --template '#rev# "#desc#"\n'
+

tests/test-convert-datesort.out

@@ -0,0 +1,40 b''
+adding a
+marked working directory as branch brancha
+1 files updated, 0 files merged, 0 files removed, 0 files unresolved
+marked working directory as branch branchb
+adding b
+1 files updated, 0 files merged, 1 files removed, 0 files unresolved
+2 files updated, 0 files merged, 0 files removed, 0 files unresolved
+% convert with datesort
+initializing destination t2 repository
+scanning source...
+sorting...
+converting...
+8 a0
+7 a1
+6 a2
+5 a3
+4 b0
+3 a4
+2 a5
+1 a6
+0 b1
+% graph converted repo
+o  8 "b1"
+|
+| o  7 "a6"
+| |
+| o  6 "a5"
+| |
+| o  5 "a4"
+| |
+o |  4 "b0"
+| |
+| o  3 "a3"
+| |
+| o  2 "a2"
+| |
+| o  1 "a1"
+|/
+o  0 "a0"
+

hgext/convert/convcmd.py

@@ -110,6 +110,7 b' class converter(object):'
         visit = parents.keys()
         seen = {}
         children = {}
+        actives = []
 
         while visit:
             n = visit.pop(0)
@@ -118,49 +119,59 b' class converter(object):'
             # 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
 

tests/test-convert-clonebranches.out

@@ -16,11 +16,11 b' 1 files updated, 0 files merged, 0 files'
 (branch merge, don't forget to commit)
 marked working directory as branch branch3
 % incremental conversion
-2 c1
-pulling from branch0 into branch1
+2 c2
+pulling from branch0 into branch2
 2 changesets found
-1 c2
-pulling from branch0 into branch2
+1 c1
+pulling from branch0 into branch1
 2 changesets found
 0 c3
 pulling from branch2 into branch3