Mercurial > hg
view mercurial/dagutil.py @ 39179:1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
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.
Differential Revision: https://phab.mercurial-scm.org/D4327
author | Gregory Szorc <gregory.szorc@gmail.com> |
---|---|
date | Fri, 17 Aug 2018 19:45:13 +0000 |
parents | 4cf3f54cc8e7 |
children | 8de526995844 |
line wrap: on
line source
# dagutil.py - dag utilities for mercurial # # Copyright 2010 Benoit Boissinot <bboissin@gmail.com> # and Peter Arrenbrecht <peter@arrenbrecht.ch> # # This software may be used and distributed according to the terms of the # GNU General Public License version 2 or any later version. from __future__ import absolute_import from .node import nullrev from . import ( dagop, ) class revlogdag(object): '''dag interface to a revlog''' def __init__(self, revlog): self._revlog = revlog def parents(self, ix): rlog = self._revlog idx = rlog.index revdata = idx[ix] prev = revdata[5] if prev != nullrev: prev2 = revdata[6] if prev2 == nullrev: return [prev] return [prev, prev2] prev2 = revdata[6] if prev2 != nullrev: return [prev2] return [] def linearize(self, ixs): '''linearize and topologically sort a list of revisions 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 heads of the given revs in inverse topological order, and for each visited rev, visiting its second parent, then its first parent, then adding the rev itself to the output list. ''' sorted = [] visit = list(dagop.headrevs(ixs, self.parents)) visit.sort(reverse=True) finished = set() while visit: cur = visit.pop() if cur < 0: cur = -cur - 1 if cur not in finished: sorted.append(cur) finished.add(cur) else: visit.append(-cur - 1) visit += [p for p in self.parents(cur) if p in ixs and p not in finished] assert len(sorted) == len(ixs) return sorted