This is an archive of the discontinued Mercurial Phabricator instance.

Differential D4327

dagop: extract headsetofconnecteds() from dagutil
ClosedPublic

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

Details

Reviewers
None
Group Reviewers
hg-reviewers
Commits
rHG1c3184d7e882: dagop: extract headsetofconnecteds() from dagutil
Summary

The functionality for resolving the set of DAG heads from a
subset simply requires a function to resolve parent revisions.

Let's establish a function in the dagop module to do this, which
seems to be where generic DAG functionality goes these days.

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:31 PM
yuja added a subscriber: yuja.Aug 18 2018, 4:05 AM

+def headrevs(revs, parentsfn):
+ """Resolve the set of heads from a set of revisions.
+
+ Receives an iterable of revision numbers and a callbable that receives a
+ revision number and returns an iterable of parent revision numbers, possibly
+ including nullrev.
+
+ Returns a set of revision numbers that are DAG heads within the passed subset.
+ """
+ headrevs = set()

Absorbed fix from D4328 since this never be non-empty set.

Overall, the series looks really nice. Thanks.

Closed by commit rHG1c3184d7e882: dagop: extract headsetofconnecteds() from dagutil (authored by indygreg). · Explain WhyAug 18 2018, 4:07 AM
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

PathPackages
Mmercurial/dagop.py (23 lines)
Mmercurial/dagutil.py (21 lines)

Diff 10449

mercurial/dagop.py

del groups[targetidx] del groups[targetidx]
else: else:
gr[0][:] = [] gr[0][:] = []
# Check if we have some subgroup waiting for revisions we are not going to # Check if we have some subgroup waiting for revisions we are not going to
# iterate over # iterate over
for g in groups: for g in groups:
for r in g[0]: for r in g[0]:
yield r yield r
def headrevs(revs, parentsfn):
"""Resolve the set of heads from a set of revisions.
Receives an iterable of revision numbers and a callbable that receives a
revision number and returns an iterable of parent revision numbers, possibly
including nullrev.
Returns a set of revision numbers that are DAG heads within the passed
subset.
``nullrev`` is never included in the returned set, even if it is provided in
the input set.
"""
headrevs = set(revs)
for rev in revs:
for prev in parentsfn(rev):
headrevs.discard(prev)
headrevs.discard(node.nullrev)
return headrevs

mercurial/dagutil.py

# dagutil.py - dag utilities for mercurial # dagutil.py - dag utilities for mercurial
# #
# Copyright 2010 Benoit Boissinot <bboissin@gmail.com> # Copyright 2010 Benoit Boissinot <bboissin@gmail.com>
# and Peter Arrenbrecht <peter@arrenbrecht.ch> # and Peter Arrenbrecht <peter@arrenbrecht.ch>
# #
# 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
from .node import nullrev from .node import nullrev
from . import (
dagop,
)
class revlogdag(object): class revlogdag(object):
'''dag interface to a revlog''' '''dag interface to a revlog'''
def __init__(self, revlog): def __init__(self, revlog):
self._revlog = revlog self._revlog = revlog
def parents(self, ix): def parents(self, ix):
rlog = self._revlog rlog = self._revlog
idx = rlog.index idx = rlog.index
revdata = idx[ix] revdata = idx[ix]
prev = revdata[5] prev = revdata[5]
if prev != nullrev: if prev != nullrev:
prev2 = revdata[6] prev2 = revdata[6]
if prev2 == nullrev: if prev2 == nullrev:
return [prev] return [prev]
return [prev, prev2] return [prev, prev2]
prev2 = revdata[6] prev2 = revdata[6]
if prev2 != nullrev: if prev2 != nullrev:
return [prev2] return [prev2]
return [] return []
def headsetofconnecteds(self, ixs):
if not ixs:
return set()
rlog = self._revlog
idx = rlog.index
headrevs = set(ixs)
for rev in ixs:
revdata = idx[rev]
for i in [5, 6]:
prev = revdata[i]
if prev != nullrev:
headrevs.discard(prev)
assert headrevs
return headrevs
def linearize(self, ixs): def linearize(self, ixs):
'''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 The linearization process tries to create long runs of revs where
a child rev comes immediately after its first parent. This is done by a child rev comes immediately after its first parent. This is done by
visiting the heads of the given revs in inverse topological order, visiting the heads of the given revs in inverse topological order,
and for each visited rev, visiting its second parent, then its first and for each visited rev, visiting its second parent, then its first
parent, then adding the rev itself to the output list. parent, then adding the rev itself to the output list.
''' '''
sorted = [] sorted = []
visit = list(self.headsetofconnecteds(ixs)) visit = list(dagop.headrevs(ixs, self.parents))
visit.sort(reverse=True) visit.sort(reverse=True)
finished = set() finished = set()
while visit: while visit:
cur = visit.pop() cur = visit.pop()
if cur < 0: if cur < 0:
cur = -cur - 1 cur = -cur - 1
if cur not in finished: if cur not in finished:
sorted.append(cur) sorted.append(cur)
finished.add(cur) finished.add(cur)
else: else:
visit.append(-cur - 1) visit.append(-cur - 1)
visit += [p for p in self.parents(cur) visit += [p for p in self.parents(cur)
if p in ixs and p not in finished] if p in ixs and p not in finished]
assert len(sorted) == len(ixs) assert len(sorted) == len(ixs)
return sorted return sorted