--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/mercurial/dagutil.py Mon May 02 19:21:30 2011 +0200
@@ -0,0 +1,242 @@
+# 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
+
+
+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
+
+
+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 - 1
+
+ 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