This is an archive of the discontinued Mercurial Phabricator instance.

Differential D4315

dagutil: remove descendantset() and ancestorset()
ClosedPublic

Authored by indygreg on Aug 17 2018, 5:30 PM.

Details

Reviewers
None
Group Reviewers
hg-reviewers
Commits
rHG136ed75bbe12: dagutil: remove descendantset() and ancestorset()
Summary

descendantset() is unused after the previous commit. And
ancestorset() was only used by descendantset(), so it can be removed
as well.

.. api:: descendantset() and ancestorset() removed from dagutil

Use a revset instead when operating on the changelog. Or use
various functionality in the ancestor or dagop modules.

Diff Detail

Repository
rHG Mercurial
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

indygreg created this revision.Aug 17 2018, 5:30 PM
Closed by commit rHG136ed75bbe12: dagutil: remove descendantset() and ancestorset() (authored by indygreg). · Explain WhyAug 18 2018, 4:06 AM
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

PathPackages
Mmercurial/dagutil.py (46 lines)

Diff 10436

mercurial/dagutil.py

def parents(self, ix): def parents(self, ix):
'''list of parents ixs of ix''' '''list of parents ixs of ix'''
raise NotImplementedError raise NotImplementedError
def inverse(self): def inverse(self):
'''inverse DAG, where parents becomes children, etc.''' '''inverse DAG, where parents becomes children, etc.'''
raise NotImplementedError raise NotImplementedError
def ancestorset(self, starts, stops=None):
'''
set of all ancestors of starts (incl), but stop walk at stops (excl)
'''
raise NotImplementedError
def descendantset(self, starts, stops=None):
'''
set of all descendants of starts (incl), but stop walk at stops (excl)
'''
return self.inverse().ancestorset(starts, stops)
def headsetofconnecteds(self, ixs): def headsetofconnecteds(self, ixs):
''' '''
subset of connected list of ixs so that no node has a descendant in it subset of connected list of ixs so that no node has a descendant in it
By "connected list" we mean that if an ancestor and a descendant are in By "connected list" we mean that if an ancestor and a descendant are in
the list, then so is at least one path connecting them. the list, then so is at least one path connecting them.
''' '''
raise NotImplementedError raise NotImplementedError
class genericdag(basedag): class genericdag(basedag):
'''generic implementations for DAGs''' '''generic implementations for DAGs'''
def ancestorset(self, starts, stops=None):
if stops:
stops = set(stops)
else:
stops = set()
seen = set()
pending = list(starts)
while pending:
n = pending.pop()
if n not in seen and n not in stops:
seen.add(n)
pending.extend(self.parents(n))
return seen
def headsetofconnecteds(self, ixs): def headsetofconnecteds(self, ixs):
hds = set(ixs) hds = set(ixs)
if not hds: if not hds:
return hds return hds
for n in ixs: for n in ixs:
for p in self.parents(n): for p in self.parents(n):
hds.discard(p) hds.discard(p)
assert hds assert hds
return [prev2] return [prev2]
return [] return []
def inverse(self): def inverse(self):
if self._inverse is None: if self._inverse is None:
self._inverse = inverserevlogdag(self) self._inverse = inverserevlogdag(self)
return self._inverse return self._inverse
def ancestorset(self, starts, stops=None):
rlog = self._revlog
idx = rlog.index
if stops:
stops = set(stops)
else:
stops = set()
seen = set()
pending = list(starts)
while pending:
rev = pending.pop()
if rev not in seen and rev not in stops:
seen.add(rev)
revdata = idx[rev]
for i in [5, 6]:
prev = revdata[i]
if prev != nullrev:
pending.append(prev)
return seen
def headsetofconnecteds(self, ixs): def headsetofconnecteds(self, ixs):
if not ixs: if not ixs:
return set() return set()
rlog = self._revlog rlog = self._revlog
idx = rlog.index idx = rlog.index
headrevs = set(ixs) headrevs = set(ixs)
for rev in ixs: for rev in ixs:
revdata = idx[rev] revdata = idx[rev]