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
--- a/tests/test-convert-clonebranches.out Tue Dec 18 14:01:34 2007 -0600
+++ b/tests/test-convert-clonebranches.out Sat Feb 16 11:55:33 2008 +0100
@@ -16,11 +16,11 @@
(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
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/test-convert-datesort Sat Feb 16 11:55:33 2008 +0100
@@ -0,0 +1,40 @@
+#!/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'
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/test-convert-datesort.out Sat Feb 16 11:55:33 2008 +0100
@@ -0,0 +1,40 @@
+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"
+