Mercurial > hg
diff hgext/convert/convcmd.py @ 8688:31e613a89750
convert: split toposort() into subfunctions for readability
author | Patrick Mezard <pmezard@gmail.com> |
---|---|
date | Mon, 01 Jun 2009 17:12:37 +0200 |
parents | e9e2a2c9b294 |
children | 9bc95f8eb018 |
line wrap: on
line diff
--- a/hgext/convert/convcmd.py Mon Jun 01 09:18:35 2009 -0400 +++ b/hgext/convert/convcmd.py Mon Jun 01 17:12:37 2009 +0200 @@ -117,31 +117,60 @@ def toposort(self, parents): '''Return an ordering such that every uncommitted changeset is preceeded by all its uncommitted ancestors.''' - visit = parents.keys() - seen = set() - children = {} - actives = [] + + def mapchildren(parents): + """Return a (children, roots) tuple where 'children' maps parent + revision identifiers to children ones, and 'roots' is the list of + revisions without parents. 'parents' must be a mapping of revision + identifier to its parents ones. + """ + visit = parents.keys() + seen = set() + children = {} + roots = [] - while visit: - n = visit.pop(0) - if n in seen: continue - seen.add(n) - # 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) + while visit: + n = visit.pop(0) + if n in seen: + continue + seen.add(n) + # 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: + roots.append(n) + + return children, roots - del seen - del visit + # Sort functions are supposed to take a list of revisions which + # can be converted immediately and pick one - if self.opts.get('datesort'): + def makebranchsorter(): + """If the previously converted revision has a child in the + eligible revisions list, pick it. Return the list head + otherwise. Branch sort attempts to minimize branch + switching, which is harmful for Mercurial backend + compression. + """ + prev = [None] + def picknext(nodes): + next = nodes[0] + for n in nodes: + if prev[0] in parents[n]: + next = n + break + prev[0] = next + return next + return picknext + + def makedatesorter(): + """Sort revisions by date.""" dates = {} def getdate(n): if n not in dates: @@ -150,18 +179,15 @@ def picknext(nodes): return min([(getdate(n), n) for n in nodes])[1] + + return picknext + + if self.opts.get('datesort'): + picknext = makedatesorter() 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 + picknext = makebranchsorter() + + children, actives = mapchildren(parents) s = [] pendings = {}