Mercurial > hg
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.
author | Patrick Mezard <pmezard@gmail.com> |
---|---|
date | Sat, 16 Feb 2008 11:55:33 +0100 |
parents | 37cc79a5727a |
children | 516d8ffede7c |
line wrap: on
line diff
--- 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