stablesort: write a flat version of the algorithm
This new version never needs to iterate over the full repository even when merge
are encountered.
Having the algorithm flat also prepare caching works since the iteration
sequence can we expressed with a couple of flat loop.
--- a/hgext3rd/evolve/stablesort.py Sat Nov 25 18:53:23 2017 -0500
+++ b/hgext3rd/evolve/stablesort.py Sun Nov 26 10:34:46 2017 -0500
@@ -314,23 +314,77 @@
return result
def _revsfrom(self, repo, head):
- parentsfunc = repo.changelog.parentrevs
+ tiebreaker = _mergepoint_tie_breaker(repo)
+ cl = repo.changelog
+ parentsfunc = cl.parentrevs
def parents(rev):
- return [p for p in parentsfunc(current) if p is not nodemod.nullrev]
+ return [p for p in parentsfunc(rev) if p is not nodemod.nullrev]
current = head
- ps = parents(current)
- while len(ps) == 1:
+ previous_current = None
+
+ while current is not None:
+ assert current is not previous_current
yield current
- current = ps[0]
+ previous_current = current
+
+ ps = parents(current)
+ if not ps:
+ current = None # break
+ if len(ps) == 1:
+ current = ps[0]
+ elif len(ps) == 2:
+ lower_parent, higher_parent = sorted(ps, key=tiebreaker)
+
+ for rev in self._process_exclusive_side(lower_parent,
+ higher_parent,
+ cl.findmissingrevs,
+ parents,
+ tiebreaker):
+ yield rev
+
+ current = lower_parent
+
+ def _process_exclusive_side(self, lower, higher, findmissingrevs, parents, tiebreaker):
+
+ exclusive = findmissingrevs(common=[lower],
+ heads=[higher])
+
+ stack = []
+ seen = set()
+ children = collections.defaultdict(set)
+ if not exclusive:
+ current = None
+ else:
+ current = higher
+ bound = set(exclusive)
+ for r in exclusive:
+ for p in parents(r):
+ children[p].add(r)
+
+ previous_current = None
+ while current is not None:
+ assert current is not previous_current
+ yield current
+ seen.add(current)
+ previous_current = current
+
ps = parents(current)
- if not ps:
- yield current
- elif len(ps) == 2:
- for rev in stablesort_mergepoint_head(repo, current)[::-1]:
- yield rev
+ usable_parents = [p for p in ps
+ if (p in bound and children[p].issubset(seen))]
+ if not usable_parents:
+ if stack:
+ current = stack.pop()
+ else:
+ current = None
+ elif len(usable_parents) == 1:
+ current = usable_parents[0]
+ else:
+ lower_parent, higher_parent = sorted(usable_parents, key=tiebreaker)
+ stack.append(lower_parent)
+ current = higher_parent
_methodmap = {
'branchpoint': stablesort_branchpoint,