| hg-reviewers |
As part of implementing an alternate storage backend, I found myself
having to reimplement this function.
The DAG traversal logic is generic and can be factored out into a
standalone function.
We could probably combine this with headrevs(). But I'll leave that
for another time.
| Lint Skipped |
| Unit Tests Skipped |
| Path | Packages | |||
|---|---|---|---|---|
| M | mercurial/dagop.py (36 lines) | |||
| M | mercurial/revlog.py (29 lines) |
| Commit | Parents | Author | Summary | Date |
|---|---|---|---|---|
| Gregory Szorc | Sep 28 2018, 1:20 PM |
| for rev in revs: | for rev in revs: | ||||
| for prev in parentsfn(rev): | for prev in parentsfn(rev): | ||||
| headrevs.discard(prev) | headrevs.discard(prev) | ||||
| headrevs.discard(node.nullrev) | headrevs.discard(node.nullrev) | ||||
| return headrevs | return headrevs | ||||
| def headrevssubset(revsfn, parentrevsfn, startrev=None, stoprevs=None): | |||||
| """Returns the set of all revs that have no children with control. | |||||
| ``revsfn`` is a callable that with no arguments returns an iterator over | |||||
| all revision numbers in topological order. With a ``start`` argument, it | |||||
| returns revision numbers starting at that number. | |||||
| ``parentrevsfn`` is a callable receiving a revision number and returns an | |||||
| iterable of parent revision numbers, where values can include nullrev. | |||||
| ``startrev`` is a revision number at which to start the search. | |||||
| ``stoprevs`` is an iterable of revision numbers that, when encountered, | |||||
| will stop DAG traversal beyond them. Parents of revisions in this | |||||
| collection will be heads. | |||||
| """ | |||||
| if startrev is None: | |||||
| startrev = nullrev | |||||
| stoprevs = set(stoprevs or []) | |||||
| reachable = {startrev} | |||||
| heads = {startrev} | |||||
| for rev in revsfn(start=startrev + 1): | |||||
| for prev in parentrevsfn(rev): | |||||
| if prev in reachable: | |||||
| if rev not in stoprevs: | |||||
| reachable.add(rev) | |||||
| heads.add(rev) | |||||
| if prev in heads and prev not in stoprevs: | |||||
| heads.remove(prev) | |||||
| return heads | |||||
| def linearize(revs, parentsfn): | def linearize(revs, parentsfn): | ||||
| """Linearize and topologically sort a list of revisions. | """Linearize and topologically sort a list of revisions. | ||||
| The linearization process tries to create long runs of revs where a child | The linearization process tries to create long runs of revs where a child | ||||
| rev comes immediately after its first parent. This is done by visiting the | rev comes immediately after its first parent. This is done by visiting the | ||||
| heads of the revs in inverse topological order, and for each visited rev, | heads of the revs in inverse topological order, and for each visited rev, | ||||
| visiting its second parent, then its first parent, then adding the rev | visiting its second parent, then its first parent, then adding the rev | ||||
| itself to the output list. | itself to the output list. | ||||
| as if they had no children | as if they had no children | ||||
| """ | """ | ||||
| if start is None and stop is None: | if start is None and stop is None: | ||||
| if not len(self): | if not len(self): | ||||
| return [nullid] | return [nullid] | ||||
| return [self.node(r) for r in self.headrevs()] | return [self.node(r) for r in self.headrevs()] | ||||
| if start is None: | if start is None: | ||||
| start = nullid | start = nullrev | ||||
| if stop is None: | else: | ||||
| stop = [] | start = self.rev(start) | ||||
| stoprevs = set([self.rev(n) for n in stop]) | |||||
| startrev = self.rev(start) | stoprevs = set(self.rev(n) for n in stop or []) | ||||
| reachable = {startrev} | |||||
| heads = {startrev} | revs = dagop.headrevssubset(self.revs, self.parentrevs, startrev=start, | ||||
| stoprevs=stoprevs) | |||||
| parentrevs = self.parentrevs | |||||
| for r in self.revs(start=startrev + 1): | |||||
| for p in parentrevs(r): | |||||
| if p in reachable: | |||||
| if r not in stoprevs: | |||||
| reachable.add(r) | |||||
| heads.add(r) | |||||
| if p in heads and p not in stoprevs: | |||||
| heads.remove(p) | |||||
| return [self.node(r) for r in heads] | return [self.node(rev) for rev in revs] | ||||
| def children(self, node): | def children(self, node): | ||||
| """find the children of a given node""" | """find the children of a given node""" | ||||
| c = [] | c = [] | ||||
| p = self.rev(node) | p = self.rev(node) | ||||
| for r in self.revs(start=p + 1): | for r in self.revs(start=p + 1): | ||||
| prevs = [pr for pr in self.parentrevs(r) if pr != nullrev] | prevs = [pr for pr in self.parentrevs(r) if pr != nullrev] | ||||
| if prevs: | if prevs: | ||||