This revision was automatically updated to reflect the committed changes. Closed by commit rHG8af835af0a85: dagop: extract DAG local heads functionality from revlog (authored by indygreg, committed by ).
REPOSITORY rHG Mercurial CHANGES SINCE LAST UPDATE https://phab.mercurial-scm.org/D4795?vs=11478&id=11609 REVISION DETAIL https://phab.mercurial-scm.org/D4795 AFFECTED FILES mercurial/dagop.py mercurial/revlog.py CHANGE DETAILS diff --git a/mercurial/revlog.py b/mercurial/revlog.py --- a/mercurial/revlog.py +++ b/mercurial/revlog.py @@ -1069,25 +1069,16 @@ return [self.node(r) for r in self.headrevs()] if start is None: - start = nullid - if stop is None: - stop = [] - stoprevs = set([self.rev(n) for n in stop]) - startrev = self.rev(start) - reachable = {startrev} - heads = {startrev} - - 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] + start = nullrev + else: + start = self.rev(start) + + stoprevs = set(self.rev(n) for n in stop or []) + + revs = dagop.headrevssubset(self.revs, self.parentrevs, startrev=start, + stoprevs=stoprevs) + + return [self.node(rev) for rev in revs] def children(self, node): """find the children of a given node""" diff --git a/mercurial/dagop.py b/mercurial/dagop.py --- a/mercurial/dagop.py +++ b/mercurial/dagop.py @@ -773,6 +773,42 @@ 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): """Linearize and topologically sort a list of revisions. To: indygreg, #hg-reviewers Cc: mercurial-devel _______________________________________________ Mercurial-devel mailing list Mercurial-devel@mercurial-scm.org https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel