|
|
# 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 node import nullrev
|
|
|
from i18n import _
|
|
|
|
|
|
|
|
|
class basedag(object):
|
|
|
'''generic interface for DAGs
|
|
|
|
|
|
terms:
|
|
|
"ix" (short for index) identifies a nodes internally,
|
|
|
"id" identifies one externally.
|
|
|
|
|
|
All params are ixs unless explicitly suffixed otherwise.
|
|
|
Pluralized params are lists or sets.
|
|
|
'''
|
|
|
|
|
|
def __init__(self):
|
|
|
self._inverse = None
|
|
|
|
|
|
def nodeset(self):
|
|
|
'''set of all node idxs'''
|
|
|
raise NotImplementedError
|
|
|
|
|
|
def heads(self):
|
|
|
'''list of head ixs'''
|
|
|
raise NotImplementedError
|
|
|
|
|
|
def parents(self, ix):
|
|
|
'''list of parents ixs of ix'''
|
|
|
raise NotImplementedError
|
|
|
|
|
|
def inverse(self):
|
|
|
'''inverse DAG, where parents becomes children, etc.'''
|
|
|
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):
|
|
|
'''
|
|
|
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
|
|
|
the list, then so is at least one path connecting them.
|
|
|
'''
|
|
|
raise NotImplementedError
|
|
|
|
|
|
def externalize(self, ix):
|
|
|
'''return a list of (or set if given a set) of node ids'''
|
|
|
return self._externalize(ix)
|
|
|
|
|
|
def externalizeall(self, ixs):
|
|
|
'''return a list of (or set if given a set) of node ids'''
|
|
|
ids = self._externalizeall(ixs)
|
|
|
if isinstance(ixs, set):
|
|
|
return set(ids)
|
|
|
return list(ids)
|
|
|
|
|
|
def internalize(self, id):
|
|
|
'''return a list of (or set if given a set) of node ixs'''
|
|
|
return self._internalize(id)
|
|
|
|
|
|
def internalizeall(self, ids, filterunknown=False):
|
|
|
'''return a list of (or set if given a set) of node ids'''
|
|
|
ixs = self._internalizeall(ids, filterunknown)
|
|
|
if isinstance(ids, set):
|
|
|
return set(ixs)
|
|
|
return list(ixs)
|
|
|
|
|
|
|
|
|
class genericdag(basedag):
|
|
|
'''generic implementations for DAGs'''
|
|
|
|
|
|
def ancestorset(self, starts, stops=None):
|
|
|
stops = stops and set(stops) or 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):
|
|
|
hds = set(ixs)
|
|
|
if not hds:
|
|
|
return hds
|
|
|
for n in ixs:
|
|
|
for p in self.parents(n):
|
|
|
hds.discard(p)
|
|
|
assert hds
|
|
|
return hds
|
|
|
|
|
|
|
|
|
class revlogbaseddag(basedag):
|
|
|
'''generic dag interface to a revlog'''
|
|
|
|
|
|
def __init__(self, revlog, nodeset):
|
|
|
basedag.__init__(self)
|
|
|
self._revlog = revlog
|
|
|
self._heads = None
|
|
|
self._nodeset = nodeset
|
|
|
|
|
|
def nodeset(self):
|
|
|
return self._nodeset
|
|
|
|
|
|
def heads(self):
|
|
|
if self._heads is None:
|
|
|
self._heads = self._getheads()
|
|
|
return self._heads
|
|
|
|
|
|
def _externalize(self, ix):
|
|
|
return self._revlog.index[ix][7]
|
|
|
def _externalizeall(self, ixs):
|
|
|
idx = self._revlog.index
|
|
|
return [idx[i][7] for i in ixs]
|
|
|
|
|
|
def _internalize(self, id):
|
|
|
ix = self._revlog.rev(id)
|
|
|
if ix == nullrev:
|
|
|
raise LookupError(id, self._revlog.indexfile, _('nullid'))
|
|
|
return ix
|
|
|
def _internalizeall(self, ids, filterunknown):
|
|
|
rl = self._revlog
|
|
|
if filterunknown:
|
|
|
return [r for r in map(rl.nodemap.get, ids)
|
|
|
if r is not None and r != nullrev]
|
|
|
return map(self._internalize, ids)
|
|
|
|
|
|
|
|
|
class revlogdag(revlogbaseddag):
|
|
|
'''dag interface to a revlog'''
|
|
|
|
|
|
def __init__(self, revlog):
|
|
|
revlogbaseddag.__init__(self, revlog, set(xrange(len(revlog))))
|
|
|
|
|
|
def _getheads(self):
|
|
|
return [r for r in self._revlog.headrevs() if r != nullrev]
|
|
|
|
|
|
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 inverse(self):
|
|
|
if self._inverse is None:
|
|
|
self._inverse = inverserevlogdag(self)
|
|
|
return self._inverse
|
|
|
|
|
|
def ancestorset(self, starts, stops=None):
|
|
|
rlog = self._revlog
|
|
|
idx = rlog.index
|
|
|
stops = stops and set(stops) or 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):
|
|
|
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):
|
|
|
'''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(self.headsetofconnecteds(ixs))
|
|
|
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
|
|
|
|
|
|
|
|
|
class inverserevlogdag(revlogbaseddag, genericdag):
|
|
|
'''inverse of an existing revlog dag; see revlogdag.inverse()'''
|
|
|
|
|
|
def __init__(self, orig):
|
|
|
revlogbaseddag.__init__(self, orig._revlog, orig._nodeset)
|
|
|
self._orig = orig
|
|
|
self._children = {}
|
|
|
self._roots = []
|
|
|
self._walkfrom = len(self._revlog) - 1
|
|
|
|
|
|
def _walkto(self, walkto):
|
|
|
rev = self._walkfrom
|
|
|
cs = self._children
|
|
|
roots = self._roots
|
|
|
idx = self._revlog.index
|
|
|
while rev >= walkto:
|
|
|
data = idx[rev]
|
|
|
isroot = True
|
|
|
for prev in [data[5], data[6]]: # parent revs
|
|
|
if prev != nullrev:
|
|
|
cs.setdefault(prev, []).append(rev)
|
|
|
isroot = False
|
|
|
if isroot:
|
|
|
roots.append(rev)
|
|
|
rev -= 1
|
|
|
self._walkfrom = rev
|
|
|
|
|
|
def _getheads(self):
|
|
|
self._walkto(nullrev)
|
|
|
return self._roots
|
|
|
|
|
|
def parents(self, ix):
|
|
|
if ix is None:
|
|
|
return []
|
|
|
if ix <= self._walkfrom:
|
|
|
self._walkto(ix)
|
|
|
return self._children.get(ix, [])
|
|
|
|
|
|
def inverse(self):
|
|
|
return self._orig
|
|
|
|
