| hg-reviewers |
This method needs to be implemented in other storage backends and is
generic if we parameterize the functions for retrieving revision
numbers and parent revision numbers.
Let's extract it to dagop so backends don't need to reinvent the
wheel.
I'm not too worried about performance overhead of the extra function
call because I don't expect anyone to be calling descendants() in a
tight loop.
| Lint Skipped |
| Unit Tests Skipped |
| Path | Packages | |||
|---|---|---|---|---|
| M | mercurial/dagop.py (34 lines) | |||
| M | mercurial/revlog.py (20 lines) |
| Commit | Parents | Author | Summary | Date |
|---|---|---|---|---|
| Gregory Szorc | Sep 28 2018, 1:03 PM |
| # dagop.py - graph ancestry and topology algorithm for revset | # dagop.py - graph ancestry and topology algorithm for revset | ||||
| # | # | ||||
| # Copyright 2010 Matt Mackall <mpm@selenic.com> | # Copyright 2010 Matt Mackall <mpm@selenic.com> | ||||
| # | # | ||||
| # This software may be used and distributed according to the terms of the | # This software may be used and distributed according to the terms of the | ||||
| # GNU General Public License version 2 or any later version. | # GNU General Public License version 2 or any later version. | ||||
| from __future__ import absolute_import | from __future__ import absolute_import | ||||
| import heapq | import heapq | ||||
| from .node import ( | |||||
| nullrev, | |||||
| ) | |||||
| from .thirdparty import ( | from .thirdparty import ( | ||||
| attr, | attr, | ||||
| ) | ) | ||||
| from . import ( | from . import ( | ||||
| error, | error, | ||||
| mdiff, | mdiff, | ||||
| node, | node, | ||||
| patch, | patch, | ||||
| """ | """ | ||||
| if startdepth is None and stopdepth is None: | if startdepth is None and stopdepth is None: | ||||
| gen = _genrevdescendants(repo, revs, followfirst) | gen = _genrevdescendants(repo, revs, followfirst) | ||||
| else: | else: | ||||
| gen = _genrevdescendantsofdepth(repo, revs, followfirst, | gen = _genrevdescendantsofdepth(repo, revs, followfirst, | ||||
| startdepth, stopdepth) | startdepth, stopdepth) | ||||
| return generatorset(gen, iterasc=True) | return generatorset(gen, iterasc=True) | ||||
| def descendantrevs(revs, revsfn, parentrevsfn): | |||||
| """Generate revision number descendants in revision order. | |||||
| Yields revision numbers starting with a child of some rev in | |||||
| ``revs``. Results are ordered by revision number and are | |||||
| therefore topological. Each revision is not considered a descendant | |||||
| of itself. | |||||
| ``revsfn`` is a callable that with no argument iterates over all | |||||
| revision numbers and with a ``start`` argument iterates over revision | |||||
| numbers beginning with that value. | |||||
| ``parentrevsfn`` is a callable that receives a revision number and | |||||
| returns an iterable of parent revision numbers, whose values may include | |||||
| nullrev. | |||||
| """ | |||||
| first = min(revs) | |||||
| if first == nullrev: | |||||
| for rev in revsfn(): | |||||
| yield rev | |||||
| return | |||||
| seen = set(revs) | |||||
| for rev in revsfn(start=first + 1): | |||||
| for prev in parentrevsfn(rev): | |||||
| if prev != nullrev and prev in seen: | |||||
| seen.add(rev) | |||||
| yield rev | |||||
| break | |||||
| def _reachablerootspure(repo, minroot, roots, heads, includepath): | def _reachablerootspure(repo, minroot, roots, heads, includepath): | ||||
| """return (heads(::<roots> and ::<heads>)) | """return (heads(::<roots> and ::<heads>)) | ||||
| If includepath is True, return (<roots>::<heads>).""" | If includepath is True, return (<roots>::<heads>).""" | ||||
| if not roots: | if not roots: | ||||
| return [] | return [] | ||||
| parentrevs = repo.changelog.parentrevs | parentrevs = repo.changelog.parentrevs | ||||
| roots = set(roots) | roots = set(roots) | ||||
| Does not generate revs lower than stoprev. | Does not generate revs lower than stoprev. | ||||
| See the documentation for ancestor.lazyancestors for more details.""" | See the documentation for ancestor.lazyancestors for more details.""" | ||||
| return ancestor.lazyancestors(self.parentrevs, revs, stoprev=stoprev, | return ancestor.lazyancestors(self.parentrevs, revs, stoprev=stoprev, | ||||
| inclusive=inclusive) | inclusive=inclusive) | ||||
| def descendants(self, revs): | def descendants(self, revs): | ||||
| """Generate the descendants of 'revs' in revision order. | return dagop.descendantrevs(revs, self.revs, self.parentrevs) | ||||
| Yield a sequence of revision numbers starting with a child of | |||||
| some rev in revs, i.e., each revision is *not* considered a | |||||
| descendant of itself. Results are ordered by revision number (a | |||||
| topological sort).""" | |||||
| first = min(revs) | |||||
| if first == nullrev: | |||||
| for i in self: | |||||
| yield i | |||||
| return | |||||
| seen = set(revs) | |||||
| for i in self.revs(start=first + 1): | |||||
| for x in self.parentrevs(i): | |||||
| if x != nullrev and x in seen: | |||||
| seen.add(i) | |||||
| yield i | |||||
| break | |||||
| def findcommonmissing(self, common=None, heads=None): | def findcommonmissing(self, common=None, heads=None): | ||||
| """Return a tuple of the ancestors of common and the ancestors of heads | """Return a tuple of the ancestors of common and the ancestors of heads | ||||
| that are not ancestors of common. In revset terminology, we return the | that are not ancestors of common. In revset terminology, we return the | ||||
| tuple: | tuple: | ||||
| ::common, (::heads) - (::common) | ::common, (::heads) - (::common) | ||||