merge with crew

mercurial/ancestor.py

@@ -1,264 +1,386 b''
 # ancestor.py - generic DAG ancestor algorithm for mercurial
 #
 # Copyright 2006 Matt Mackall <[e-mail]>
 #
 # This software may be used and distributed according to the terms of the
 # GNU General Public License version 2 or any later version.
 
 import heapq, util
 from node import nullrev
 
-def ancestor(a, b, pfunc):
+def ancestors(pfunc, *orignodes):
+    """
+    Returns the common ancestors of a and b that are furthest from a
+    root (as measured by longest path).
+
+    pfunc must return a list of parent vertices for a given vertex.
+    """
+    if not isinstance(orignodes, set):
+        orignodes = set(orignodes)
+    if nullrev in orignodes:
+        return set()
+    if len(orignodes) <= 1:
+        return orignodes
+
+    def candidates(nodes):
+        allseen = (1 << len(nodes)) - 1
+        seen = [0] * (max(nodes) + 1)
+        for i, n in enumerate(nodes):
+            seen[n] = 1 << i
+        poison = 1 << (i + 1)
+
+        gca = set()
+        interesting = left = len(nodes)
+        nv = len(seen) - 1
+        while nv >= 0 and interesting:
+            v = nv
+            nv -= 1
+            if not seen[v]:
+                continue
+            sv = seen[v]
+            if sv < poison:
+                interesting -= 1
+                if sv == allseen:
+                    gca.add(v)
+                    sv |= poison
+                    if v in nodes:
+                        left -= 1
+                        if left <= 1:
+                            # history is linear
+                            return set([v])
+            if sv < poison:
+                for p in pfunc(v):
+                    sp = seen[p]
+                    if p == nullrev:
+                        continue
+                    if sp == 0:
+                        seen[p] = sv
+                        interesting += 1
+                    elif sp != sv:
+                        seen[p] |= sv
+            else:
+                for p in pfunc(v):
+                    if p == nullrev:
+                        continue
+                    sp = seen[p]
+                    if sp and sp < poison:
+                        interesting -= 1
+                    seen[p] = sv
+        return gca
+
+    def deepest(nodes):
+        interesting = {}
+        count = max(nodes) + 1
+        depth = [0] * count
+        seen = [0] * count
+        mapping = []
+        for (i, n) in enumerate(sorted(nodes)):
+            depth[n] = 1
+            b = 1 << i
+            seen[n] = b
+            interesting[b] = 1
+            mapping.append((b, n))
+        nv = count - 1
+        while nv >= 0 and len(interesting) > 1:
+            v = nv
+            nv -= 1
+            dv = depth[v]
+            if dv == 0:
+                continue
+            sv = seen[v]
+            for p in pfunc(v):
+                if p == nullrev:
+                    continue
+                dp = depth[p]
+                nsp = sp = seen[p]
+                if dp <= dv:
+                    depth[p] = dv + 1
+                    if sp != sv:
+                        interesting[sv] += 1
+                        nsp = seen[p] = sv
+                        if sp:
+                            interesting[sp] -= 1
+                            if interesting[sp] == 0:
+                                del interesting[sp]
+                elif dv == dp - 1:
+                    nsp = sp | sv
+                    if nsp == sp:
+                        continue
+                    seen[p] = nsp
+                    interesting.setdefault(nsp, 0)
+                    interesting[nsp] += 1
+                    interesting[sp] -= 1
+                    if interesting[sp] == 0:
+                        del interesting[sp]
+            interesting[sv] -= 1
+            if interesting[sv] == 0:
+                del interesting[sv]
+
+        if len(interesting) != 1:
+            return []
+
+        k = 0
+        for i in interesting:
+            k |= i
+        return set(n for (i, n) in mapping if k & i)
+
+    gca = candidates(orignodes)
+
+    if len(gca) <= 1:
+        return gca
+    return deepest(gca)
+
+def genericancestor(a, b, pfunc):
     """
     Returns the common ancestor of a and b that is furthest from a
     root (as measured by longest path) or None if no ancestor is
     found. If there are multiple common ancestors at the same
     distance, the first one found is returned.
 
     pfunc must return a list of parent vertices for a given vertex
     """
 
     if a == b:
         return a
 
     a, b = sorted([a, b])
 
     # find depth from root of all ancestors
     # depth is stored as a negative for heapq
     parentcache = {}
     visit = [a, b]
     depth = {}
     while visit:
         vertex = visit[-1]
-        pl = pfunc(vertex)
+        pl = [p for p in pfunc(vertex) if p != nullrev]
         parentcache[vertex] = pl
         if not pl:
             depth[vertex] = 0
             visit.pop()
         else:
             for p in pl:
                 if p == a or p == b: # did we find a or b as a parent?
                     return p # we're done
                 if p not in depth:
                     visit.append(p)
             if visit[-1] == vertex:
                 # -(maximum distance of parents + 1)
                 depth[vertex] = min([depth[p] for p in pl]) - 1
                 visit.pop()
 
     # traverse ancestors in order of decreasing distance from root
     def ancestors(vertex):
         h = [(depth[vertex], vertex)]
         seen = set()
         while h:
             d, n = heapq.heappop(h)
             if n not in seen:
                 seen.add(n)
                 yield (d, n)
                 for p in parentcache[n]:
                     heapq.heappush(h, (depth[p], p))
 
     def generations(vertex):
         sg, s = None, set()
         for g, v in ancestors(vertex):
             if g != sg:
                 if sg:
                     yield sg, s
                 sg, s = g, set((v,))
             else:
                 s.add(v)
         yield sg, s
 
     x = generations(a)
     y = generations(b)
     gx = x.next()
     gy = y.next()
 
     # increment each ancestor list until it is closer to root than
     # the other, or they match
     try:
         while True:
             if gx[0] == gy[0]:
                 for v in gx[1]:
                     if v in gy[1]:
                         return v
                 gy = y.next()
                 gx = x.next()
             elif gx[0] > gy[0]:
                 gy = y.next()
             else:
                 gx = x.next()
     except StopIteration:
         return None
 
 def missingancestors(revs, bases, pfunc):
     """Return all the ancestors of revs that are not ancestors of bases.
 
     This may include elements from revs.
 
     Equivalent to the revset (::revs - ::bases). Revs are returned in
     revision number order, which is a topological order.
 
     revs and bases should both be iterables. pfunc must return a list of
     parent revs for a given revs.
     """
 
     revsvisit = set(revs)
     basesvisit = set(bases)
     if not revsvisit:
         return []
     if not basesvisit:
         basesvisit.add(nullrev)
     start = max(max(revsvisit), max(basesvisit))
     bothvisit = revsvisit.intersection(basesvisit)
     revsvisit.difference_update(bothvisit)
     basesvisit.difference_update(bothvisit)
     # At this point, we hold the invariants that:
     # - revsvisit is the set of nodes we know are an ancestor of at least one
     #   of the nodes in revs
     # - basesvisit is the same for bases
     # - bothvisit is the set of nodes we know are ancestors of at least one of
     #   the nodes in revs and one of the nodes in bases
     # - a node may be in none or one, but not more, of revsvisit, basesvisit
     #   and bothvisit at any given time
     # Now we walk down in reverse topo order, adding parents of nodes already
     # visited to the sets while maintaining the invariants. When a node is
     # found in both revsvisit and basesvisit, it is removed from them and
     # added to bothvisit instead. When revsvisit becomes empty, there are no
     # more ancestors of revs that aren't also ancestors of bases, so exit.
 
     missing = []
     for curr in xrange(start, nullrev, -1):
         if not revsvisit:
             break
 
         if curr in bothvisit:
             bothvisit.remove(curr)
             # curr's parents might have made it into revsvisit or basesvisit
             # through another path
             for p in pfunc(curr):
                 revsvisit.discard(p)
                 basesvisit.discard(p)
                 bothvisit.add(p)
             continue
 
         # curr will never be in both revsvisit and basesvisit, since if it
         # were it'd have been pushed to bothvisit
         if curr in revsvisit:
             missing.append(curr)
             thisvisit = revsvisit
             othervisit = basesvisit
         elif curr in basesvisit:
             thisvisit = basesvisit
             othervisit = revsvisit
         else:
             # not an ancestor of revs or bases: ignore
             continue
 
         thisvisit.remove(curr)
         for p in pfunc(curr):
             if p == nullrev:
                 pass
             elif p in othervisit or p in bothvisit:
                 # p is implicitly in thisvisit. This means p is or should be
                 # in bothvisit
                 revsvisit.discard(p)
                 basesvisit.discard(p)
                 bothvisit.add(p)
             else:
                 # visit later
                 thisvisit.add(p)
 
     missing.reverse()
     return missing
 
 class lazyancestors(object):
     def __init__(self, cl, revs, stoprev=0, inclusive=False):
         """Create a new object generating ancestors for the given revs. Does
         not generate revs lower than stoprev.
 
         This is computed lazily starting from revs. The object supports
         iteration and membership.
 
         cl should be a changelog and revs should be an iterable. inclusive is
         a boolean that indicates whether revs should be included. Revs lower
         than stoprev will not be generated.
 
         Result does not include the null revision."""
         self._parentrevs = cl.parentrevs
         self._initrevs = revs
         self._stoprev = stoprev
         self._inclusive = inclusive
 
         # Initialize data structures for __contains__.
         # For __contains__, we use a heap rather than a deque because
         # (a) it minimizes the number of parentrevs calls made
         # (b) it makes the loop termination condition obvious
         # Python's heap is a min-heap. Multiply all values by -1 to convert it
         # into a max-heap.
         self._containsvisit = [-rev for rev in revs]
         heapq.heapify(self._containsvisit)
         if inclusive:
             self._containsseen = set(revs)
         else:
             self._containsseen = set()
 
     def __iter__(self):
         """Generate the ancestors of _initrevs in reverse topological order.
 
         If inclusive is False, yield a sequence of revision numbers starting
         with the parents of each revision in revs, i.e., each revision is *not*
         considered an ancestor of itself.  Results are in breadth-first order:
         parents of each rev in revs, then parents of those, etc.
 
         If inclusive is True, yield all the revs first (ignoring stoprev),
         then yield all the ancestors of revs as when inclusive is False.
         If an element in revs is an ancestor of a different rev it is not
         yielded again."""
         seen = set()
         revs = self._initrevs
         if self._inclusive:
             for rev in revs:
                 yield rev
             seen.update(revs)
 
         parentrevs = self._parentrevs
         stoprev = self._stoprev
         visit = util.deque(revs)
 
         while visit:
             for parent in parentrevs(visit.popleft()):
                 if parent >= stoprev and parent not in seen:
                     visit.append(parent)
                     seen.add(parent)
                     yield parent
 
     def __contains__(self, target):
         """Test whether target is an ancestor of self._initrevs."""
         # Trying to do both __iter__ and __contains__ using the same visit
         # heap and seen set is complex enough that it slows down both. Keep
         # them separate.
         seen = self._containsseen
         if target in seen:
             return True
 
         parentrevs = self._parentrevs
         visit = self._containsvisit
         stoprev = self._stoprev
         heappop = heapq.heappop
         heappush = heapq.heappush
 
         targetseen = False
 
         while visit and -visit[0] > target and not targetseen:
             for parent in parentrevs(-heappop(visit)):
                 if parent < stoprev or parent in seen:
                     continue
                 # We need to make sure we push all parents into the heap so
                 # that we leave it in a consistent state for future calls.
                 heappush(visit, -parent)
                 seen.add(parent)
                 if parent == target:
                     targetseen = True
 
         return targetseen

mercurial/context.py

@@ -1,1371 +1,1371 b''
 # context.py - changeset and file context objects for mercurial
 #
 # Copyright 2006, 2007 Matt Mackall <[e-mail]>
 #
 # 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 nullid, nullrev, short, hex, bin
 from i18n import _
 import ancestor, mdiff, error, util, scmutil, subrepo, patch, encoding, phases
 import copies
 import match as matchmod
 import os, errno, stat
 import obsolete as obsmod
 import repoview
 
 propertycache = util.propertycache
 
 class changectx(object):
     """A changecontext object makes access to data related to a particular
     changeset convenient."""
     def __init__(self, repo, changeid=''):
         """changeid is a revision number, node, or tag"""
         if changeid == '':
             changeid = '.'
         self._repo = repo
 
         if isinstance(changeid, int):
             try:
                 self._node = repo.changelog.node(changeid)
             except IndexError:
                 raise error.RepoLookupError(
                     _("unknown revision '%s'") % changeid)
             self._rev = changeid
             return
         if isinstance(changeid, long):
             changeid = str(changeid)
         if changeid == '.':
             self._node = repo.dirstate.p1()
             self._rev = repo.changelog.rev(self._node)
             return
         if changeid == 'null':
             self._node = nullid
             self._rev = nullrev
             return
         if changeid == 'tip':
             self._node = repo.changelog.tip()
             self._rev = repo.changelog.rev(self._node)
             return
         if len(changeid) == 20:
             try:
                 self._node = changeid
                 self._rev = repo.changelog.rev(changeid)
                 return
             except LookupError:
                 pass
 
         try:
             r = int(changeid)
             if str(r) != changeid:
                 raise ValueError
             l = len(repo.changelog)
             if r < 0:
                 r += l
             if r < 0 or r >= l:
                 raise ValueError
             self._rev = r
             self._node = repo.changelog.node(r)
             return
         except (ValueError, OverflowError, IndexError):
             pass
 
         if len(changeid) == 40:
             try:
                 self._node = bin(changeid)
                 self._rev = repo.changelog.rev(self._node)
                 return
             except (TypeError, LookupError):
                 pass
 
         if changeid in repo._bookmarks:
             self._node = repo._bookmarks[changeid]
             self._rev = repo.changelog.rev(self._node)
             return
         if changeid in repo._tagscache.tags:
             self._node = repo._tagscache.tags[changeid]
             self._rev = repo.changelog.rev(self._node)
             return
         try:
             self._node = repo.branchtip(changeid)
             self._rev = repo.changelog.rev(self._node)
             return
         except error.RepoLookupError:
             pass
 
         self._node = repo.changelog._partialmatch(changeid)
         if self._node is not None:
             self._rev = repo.changelog.rev(self._node)
             return
 
         # lookup failed
         # check if it might have come from damaged dirstate
         #
         # XXX we could avoid the unfiltered if we had a recognizable exception
         # for filtered changeset access
         if changeid in repo.unfiltered().dirstate.parents():
             raise error.Abort(_("working directory has unknown parent '%s'!")
                               % short(changeid))
         try:
             if len(changeid) == 20:
                 changeid = hex(changeid)
         except TypeError:
             pass
         raise error.RepoLookupError(
             _("unknown revision '%s'") % changeid)
 
     def __str__(self):
         return short(self.node())
 
     def __int__(self):
         return self.rev()
 
     def __repr__(self):
         return "<changectx %s>" % str(self)
 
     def __hash__(self):
         try:
             return hash(self._rev)
         except AttributeError:
             return id(self)
 
     def __eq__(self, other):
         try:
             return self._rev == other._rev
         except AttributeError:
             return False
 
     def __ne__(self, other):
         return not (self == other)
 
     def __nonzero__(self):
         return self._rev != nullrev
 
     @propertycache
     def _changeset(self):
         return self._repo.changelog.read(self.rev())
 
     @propertycache
     def _manifest(self):
         return self._repo.manifest.read(self._changeset[0])
 
     @propertycache
     def _manifestdelta(self):
         return self._repo.manifest.readdelta(self._changeset[0])
 
     @propertycache
     def _parents(self):
         p = self._repo.changelog.parentrevs(self._rev)
         if p[1] == nullrev:
             p = p[:-1]
         return [changectx(self._repo, x) for x in p]
 
     @propertycache
     def substate(self):
         return subrepo.state(self, self._repo.ui)
 
     def __contains__(self, key):
         return key in self._manifest
 
     def __getitem__(self, key):
         return self.filectx(key)
 
     def __iter__(self):
         for f in sorted(self._manifest):
             yield f
 
     def changeset(self):
         return self._changeset
     def manifest(self):
         return self._manifest
     def manifestnode(self):
         return self._changeset[0]
 
     def rev(self):
         return self._rev
     def node(self):
         return self._node
     def hex(self):
         return hex(self._node)
     def user(self):
         return self._changeset[1]
     def date(self):
         return self._changeset[2]
     def files(self):
         return self._changeset[3]
     def description(self):
         return self._changeset[4]
     def branch(self):
         return encoding.tolocal(self._changeset[5].get("branch"))
     def closesbranch(self):
         return 'close' in self._changeset[5]
     def extra(self):
         return self._changeset[5]
     def tags(self):
         return self._repo.nodetags(self._node)
     def bookmarks(self):
         return self._repo.nodebookmarks(self._node)
     def phase(self):
         return self._repo._phasecache.phase(self._repo, self._rev)
     def phasestr(self):
         return phases.phasenames[self.phase()]
     def mutable(self):
         return self.phase() > phases.public
     def hidden(self):
         return self._rev in repoview.filterrevs(self._repo, 'visible')
 
     def parents(self):
         """return contexts for each parent changeset"""
         return self._parents
 
     def p1(self):
         return self._parents[0]
 
     def p2(self):
         if len(self._parents) == 2:
             return self._parents[1]
         return changectx(self._repo, -1)
 
     def children(self):
         """return contexts for each child changeset"""
         c = self._repo.changelog.children(self._node)
         return [changectx(self._repo, x) for x in c]
 
     def ancestors(self):
         for a in self._repo.changelog.ancestors([self._rev]):
             yield changectx(self._repo, a)
 
     def descendants(self):
         for d in self._repo.changelog.descendants([self._rev]):
             yield changectx(self._repo, d)
 
     def obsolete(self):
         """True if the changeset is obsolete"""
         return self.rev() in obsmod.getrevs(self._repo, 'obsolete')
 
     def extinct(self):
         """True if the changeset is extinct"""
         return self.rev() in obsmod.getrevs(self._repo, 'extinct')
 
     def unstable(self):
         """True if the changeset is not obsolete but it's ancestor are"""
         return self.rev() in obsmod.getrevs(self._repo, 'unstable')
 
     def bumped(self):
         """True if the changeset try to be a successor of a public changeset
 
         Only non-public and non-obsolete changesets may be bumped.
         """
         return self.rev() in obsmod.getrevs(self._repo, 'bumped')
 
     def divergent(self):
         """Is a successors of a changeset with multiple possible successors set
 
         Only non-public and non-obsolete changesets may be divergent.
         """
         return self.rev() in obsmod.getrevs(self._repo, 'divergent')
 
     def troubled(self):
         """True if the changeset is either unstable, bumped or divergent"""
         return self.unstable() or self.bumped() or self.divergent()
 
     def troubles(self):
         """return the list of troubles affecting this changesets.
 
         Troubles are returned as strings. possible values are:
         - unstable,
         - bumped,
         - divergent.
         """
         troubles = []
         if self.unstable():
             troubles.append('unstable')
         if self.bumped():
             troubles.append('bumped')
         if self.divergent():
             troubles.append('divergent')
         return troubles
 
     def _fileinfo(self, path):
         if '_manifest' in self.__dict__:
             try:
                 return self._manifest[path], self._manifest.flags(path)
             except KeyError:
                 raise error.ManifestLookupError(self._node, path,
                                                 _('not found in manifest'))
         if '_manifestdelta' in self.__dict__ or path in self.files():
             if path in self._manifestdelta:
                 return (self._manifestdelta[path],
                         self._manifestdelta.flags(path))
         node, flag = self._repo.manifest.find(self._changeset[0], path)
         if not node:
             raise error.ManifestLookupError(self._node, path,
                                             _('not found in manifest'))
 
         return node, flag
 
     def filenode(self, path):
         return self._fileinfo(path)[0]
 
     def flags(self, path):
         try:
             return self._fileinfo(path)[1]
         except error.LookupError:
             return ''
 
     def filectx(self, path, fileid=None, filelog=None):
         """get a file context from this changeset"""
         if fileid is None:
             fileid = self.filenode(path)
         return filectx(self._repo, path, fileid=fileid,
                        changectx=self, filelog=filelog)
 
     def ancestor(self, c2):
         """
         return the ancestor context of self and c2
         """
         # deal with workingctxs
         n2 = c2._node
         if n2 is None:
             n2 = c2._parents[0]._node
         n = self._repo.changelog.ancestor(self._node, n2)
         return changectx(self._repo, n)
 
     def descendant(self, other):
         """True if other is descendant of this changeset"""
         return self._repo.changelog.descendant(self._rev, other._rev)
 
     def walk(self, match):
         fset = set(match.files())
         # for dirstate.walk, files=['.'] means "walk the whole tree".
         # follow that here, too
         fset.discard('.')
         for fn in self:
             if fn in fset:
                 # specified pattern is the exact name
                 fset.remove(fn)
             if match(fn):
                 yield fn
         for fn in sorted(fset):
             if fn in self._dirs:
                 # specified pattern is a directory
                 continue
             if match.bad(fn, _('no such file in rev %s') % self) and match(fn):
                 yield fn
 
     def sub(self, path):
         return subrepo.subrepo(self, path)
 
     def match(self, pats=[], include=None, exclude=None, default='glob'):
         r = self._repo
         return matchmod.match(r.root, r.getcwd(), pats,
                               include, exclude, default,
                               auditor=r.auditor, ctx=self)
 
     def diff(self, ctx2=None, match=None, **opts):
         """Returns a diff generator for the given contexts and matcher"""
         if ctx2 is None:
             ctx2 = self.p1()
         if ctx2 is not None and not isinstance(ctx2, changectx):
             ctx2 = self._repo[ctx2]
         diffopts = patch.diffopts(self._repo.ui, opts)
         return patch.diff(self._repo, ctx2.node(), self.node(),
                           match=match, opts=diffopts)
 
     @propertycache
     def _dirs(self):
         return scmutil.dirs(self._manifest)
 
     def dirs(self):
         return self._dirs
 
     def dirty(self):
         return False
 
 class filectx(object):
     """A filecontext object makes access to data related to a particular
        filerevision convenient."""
     def __init__(self, repo, path, changeid=None, fileid=None,
                  filelog=None, changectx=None):
         """changeid can be a changeset revision, node, or tag.
            fileid can be a file revision or node."""
         self._repo = repo
         self._path = path
 
         assert (changeid is not None
                 or fileid is not None
                 or changectx is not None), \
                 ("bad args: changeid=%r, fileid=%r, changectx=%r"
                  % (changeid, fileid, changectx))
 
         if filelog:
             self._filelog = filelog
 
         if changeid is not None:
             self._changeid = changeid
         if changectx is not None:
             self._changectx = changectx
         if fileid is not None:
             self._fileid = fileid
 
     @propertycache
     def _changectx(self):
         try:
             return changectx(self._repo, self._changeid)
         except error.RepoLookupError:
             # Linkrev may point to any revision in the repository.  When the
             # repository is filtered this may lead to `filectx` trying to build
             # `changectx` for filtered revision. In such case we fallback to
             # creating `changectx` on the unfiltered version of the reposition.
             # This fallback should not be an issue because `changectx` from
             # `filectx` are not used in complex operations that care about
             # filtering.
             #
             # This fallback is a cheap and dirty fix that prevent several
             # crashes. It does not ensure the behavior is correct. However the
             # behavior was not correct before filtering either and "incorrect
             # behavior" is seen as better as "crash"
             #
             # Linkrevs have several serious troubles with filtering that are
             # complicated to solve. Proper handling of the issue here should be
             # considered when solving linkrev issue are on the table.
             return changectx(self._repo.unfiltered(), self._changeid)
 
     @propertycache
     def _filelog(self):
         return self._repo.file(self._path)
 
     @propertycache
     def _changeid(self):
         if '_changectx' in self.__dict__:
             return self._changectx.rev()
         else:
             return self._filelog.linkrev(self._filerev)
 
     @propertycache
     def _filenode(self):
         if '_fileid' in self.__dict__:
             return self._filelog.lookup(self._fileid)
         else:
             return self._changectx.filenode(self._path)
 
     @propertycache
     def _filerev(self):
         return self._filelog.rev(self._filenode)
 
     @propertycache
     def _repopath(self):
         return self._path
 
     def __nonzero__(self):
         try:
             self._filenode
             return True
         except error.LookupError:
             # file is missing
             return False
 
     def __str__(self):
         return "%s@%s" % (self.path(), short(self.node()))
 
     def __repr__(self):
         return "<filectx %s>" % str(self)
 
     def __hash__(self):
         try:
             return hash((self._path, self._filenode))
         except AttributeError:
             return id(self)
 
     def __eq__(self, other):
         try:
             return (self._path == other._path
                     and self._filenode == other._filenode)
         except AttributeError:
             return False
 
     def __ne__(self, other):
         return not (self == other)
 
     def filectx(self, fileid):
         '''opens an arbitrary revision of the file without
         opening a new filelog'''
         return filectx(self._repo, self._path, fileid=fileid,
                        filelog=self._filelog)
 
     def filerev(self):
         return self._filerev
     def filenode(self):
         return self._filenode
     def flags(self):
         return self._changectx.flags(self._path)
     def filelog(self):
         return self._filelog
 
     def rev(self):
         if '_changectx' in self.__dict__:
             return self._changectx.rev()
         if '_changeid' in self.__dict__:
             return self._changectx.rev()
         return self._filelog.linkrev(self._filerev)
 
     def linkrev(self):
         return self._filelog.linkrev(self._filerev)
     def node(self):
         return self._changectx.node()
     def hex(self):
         return hex(self.node())
     def user(self):
         return self._changectx.user()
     def date(self):
         return self._changectx.date()
     def files(self):
         return self._changectx.files()
     def description(self):
         return self._changectx.description()
     def branch(self):
         return self._changectx.branch()
     def extra(self):
         return self._changectx.extra()
     def phase(self):
         return self._changectx.phase()
     def phasestr(self):
         return self._changectx.phasestr()
     def manifest(self):
         return self._changectx.manifest()
     def changectx(self):
         return self._changectx
 
     def data(self):
         return self._filelog.read(self._filenode)
     def path(self):
         return self._path
     def size(self):
         return self._filelog.size(self._filerev)
 
     def isbinary(self):
         try:
             return util.binary(self.data())
         except IOError:
             return False
 
     def cmp(self, fctx):
         """compare with other file context
 
         returns True if different than fctx.
         """
         if (fctx._filerev is None
             and (self._repo._encodefilterpats
                  # if file data starts with '\1\n', empty metadata block is
                  # prepended, which adds 4 bytes to filelog.size().
                  or self.size() - 4 == fctx.size())
             or self.size() == fctx.size()):
             return self._filelog.cmp(self._filenode, fctx.data())
 
         return True
 
     def renamed(self):
         """check if file was actually renamed in this changeset revision
 
         If rename logged in file revision, we report copy for changeset only
         if file revisions linkrev points back to the changeset in question
         or both changeset parents contain different file revisions.
         """
 
         renamed = self._filelog.renamed(self._filenode)
         if not renamed:
             return renamed
 
         if self.rev() == self.linkrev():
             return renamed
 
         name = self.path()
         fnode = self._filenode
         for p in self._changectx.parents():
             try:
                 if fnode == p.filenode(name):
                     return None
             except error.LookupError:
                 pass
         return renamed
 
     def parents(self):
         p = self._path
         fl = self._filelog
         pl = [(p, n, fl) for n in self._filelog.parents(self._filenode)]
 
         r = self._filelog.renamed(self._filenode)
         if r:
             pl[0] = (r[0], r[1], None)
 
         return [filectx(self._repo, p, fileid=n, filelog=l)
                 for p, n, l in pl if n != nullid]
 
     def p1(self):
         return self.parents()[0]
 
     def p2(self):
         p = self.parents()
         if len(p) == 2:
             return p[1]
         return filectx(self._repo, self._path, fileid=-1, filelog=self._filelog)
 
     def children(self):
         # hard for renames
         c = self._filelog.children(self._filenode)
         return [filectx(self._repo, self._path, fileid=x,
                         filelog=self._filelog) for x in c]
 
     def annotate(self, follow=False, linenumber=None, diffopts=None):
         '''returns a list of tuples of (ctx, line) for each line
         in the file, where ctx is the filectx of the node where
         that line was last changed.
         This returns tuples of ((ctx, linenumber), line) for each line,
         if "linenumber" parameter is NOT "None".
         In such tuples, linenumber means one at the first appearance
         in the managed file.
         To reduce annotation cost,
         this returns fixed value(False is used) as linenumber,
         if "linenumber" parameter is "False".'''
 
         def decorate_compat(text, rev):
             return ([rev] * len(text.splitlines()), text)
 
         def without_linenumber(text, rev):
             return ([(rev, False)] * len(text.splitlines()), text)
 
         def with_linenumber(text, rev):
             size = len(text.splitlines())
             return ([(rev, i) for i in xrange(1, size + 1)], text)
 
         decorate = (((linenumber is None) and decorate_compat) or
                     (linenumber and with_linenumber) or
                     without_linenumber)
 
         def pair(parent, child):
             blocks = mdiff.allblocks(parent[1], child[1], opts=diffopts,
                                      refine=True)
             for (a1, a2, b1, b2), t in blocks:
                 # Changed blocks ('!') or blocks made only of blank lines ('~')
                 # belong to the child.
                 if t == '=':
                     child[0][b1:b2] = parent[0][a1:a2]
             return child
 
         getlog = util.lrucachefunc(lambda x: self._repo.file(x))
         def getctx(path, fileid):
             log = path == self._path and self._filelog or getlog(path)
             return filectx(self._repo, path, fileid=fileid, filelog=log)
         getctx = util.lrucachefunc(getctx)
 
         def parents(f):
             # we want to reuse filectx objects as much as possible
             p = f._path
             if f._filerev is None: # working dir
                 pl = [(n.path(), n.filerev()) for n in f.parents()]
             else:
                 pl = [(p, n) for n in f._filelog.parentrevs(f._filerev)]
 
             if follow:
                 r = f.renamed()
                 if r:
                     pl[0] = (r[0], getlog(r[0]).rev(r[1]))
 
             return [getctx(p, n) for p, n in pl if n != nullrev]
 
         # use linkrev to find the first changeset where self appeared
         if self.rev() != self.linkrev():
             base = self.filectx(self.filerev())
         else:
             base = self
 
         # This algorithm would prefer to be recursive, but Python is a
         # bit recursion-hostile. Instead we do an iterative
         # depth-first search.
 
         visit = [base]
         hist = {}
         pcache = {}
         needed = {base: 1}
         while visit:
             f = visit[-1]
             if f not in pcache:
                 pcache[f] = parents(f)
 
             ready = True
             pl = pcache[f]
             for p in pl:
                 if p not in hist:
                     ready = False
                     visit.append(p)
                     needed[p] = needed.get(p, 0) + 1
             if ready:
                 visit.pop()
                 curr = decorate(f.data(), f)
                 for p in pl:
                     curr = pair(hist[p], curr)
                     if needed[p] == 1:
                         del hist[p]
                     else:
                         needed[p] -= 1
 
                 hist[f] = curr
                 pcache[f] = []
 
         return zip(hist[base][0], hist[base][1].splitlines(True))
 
     def ancestor(self, fc2, actx):
         """
         find the common ancestor file context, if any, of self, and fc2
 
         actx must be the changectx of the common ancestor
         of self's and fc2's respective changesets.
         """
 
         # the easy case: no (relevant) renames
         if fc2.path() == self.path() and self.path() in actx:
             return actx[self.path()]
 
         # the next easiest cases: unambiguous predecessor (name trumps
         # history)
         if self.path() in actx and fc2.path() not in actx:
             return actx[self.path()]
         if fc2.path() in actx and self.path() not in actx:
             return actx[fc2.path()]
 
         # prime the ancestor cache for the working directory
         acache = {}
         for c in (self, fc2):
             if c._filerev is None:
                 pl = [(n.path(), n.filenode()) for n in c.parents()]
                 acache[(c._path, None)] = pl
 
         flcache = {self._repopath:self._filelog, fc2._repopath:fc2._filelog}
         def parents(vertex):
             if vertex in acache:
                 return acache[vertex]
             f, n = vertex
             if f not in flcache:
                 flcache[f] = self._repo.file(f)
             fl = flcache[f]
             pl = [(f, p) for p in fl.parents(n) if p != nullid]
             re = fl.renamed(n)
             if re:
                 pl.append(re)
             acache[vertex] = pl
             return pl
 
         a, b = (self._path, self._filenode), (fc2._path, fc2._filenode)
-        v = ancestor.ancestor(a, b, parents)
+        v = ancestor.genericancestor(a, b, parents)
         if v:
             f, n = v
             return filectx(self._repo, f, fileid=n, filelog=flcache[f])
 
         return None
 
     def ancestors(self, followfirst=False):
         visit = {}
         c = self
         cut = followfirst and 1 or None
         while True:
             for parent in c.parents()[:cut]:
                 visit[(parent.rev(), parent.node())] = parent
             if not visit:
                 break
             c = visit.pop(max(visit))
             yield c
 
     def copies(self, c2):
         if not util.safehasattr(self, "_copycache"):
             self._copycache = {}
         sc2 = str(c2)
         if sc2 not in self._copycache:
             self._copycache[sc2] = copies.pathcopies(c2)
         return self._copycache[sc2]
 
 class workingctx(changectx):
     """A workingctx object makes access to data related to
     the current working directory convenient.
     date - any valid date string or (unixtime, offset), or None.
     user - username string, or None.
     extra - a dictionary of extra values, or None.
     changes - a list of file lists as returned by localrepo.status()
                or None to use the repository status.
     """
     def __init__(self, repo, text="", user=None, date=None, extra=None,
                  changes=None):
         self._repo = repo
         self._rev = None
         self._node = None
         self._text = text
         if date:
             self._date = util.parsedate(date)
         if user:
             self._user = user
         if changes:
             self._status = list(changes[:4])
             self._unknown = changes[4]
             self._ignored = changes[5]
             self._clean = changes[6]
         else:
             self._unknown = None
             self._ignored = None
             self._clean = None
 
         self._extra = {}
         if extra:
             self._extra = extra.copy()
         if 'branch' not in self._extra:
             try:
                 branch = encoding.fromlocal(self._repo.dirstate.branch())
             except UnicodeDecodeError:
                 raise util.Abort(_('branch name not in UTF-8!'))
             self._extra['branch'] = branch
         if self._extra['branch'] == '':
             self._extra['branch'] = 'default'
 
     def __str__(self):
         return str(self._parents[0]) + "+"
 
     def __repr__(self):
         return "<workingctx %s>" % str(self)
 
     def __nonzero__(self):
         return True
 
     def __contains__(self, key):
         return self._repo.dirstate[key] not in "?r"
 
     def _buildflagfunc(self):
         # Create a fallback function for getting file flags when the
         # filesystem doesn't support them
 
         copiesget = self._repo.dirstate.copies().get
 
         if len(self._parents) < 2:
             # when we have one parent, it's easy: copy from parent
             man = self._parents[0].manifest()
             def func(f):
                 f = copiesget(f, f)
                 return man.flags(f)
         else:
             # merges are tricky: we try to reconstruct the unstored
             # result from the merge (issue1802)
             p1, p2 = self._parents
             pa = p1.ancestor(p2)
             m1, m2, ma = p1.manifest(), p2.manifest(), pa.manifest()
 
             def func(f):
                 f = copiesget(f, f) # may be wrong for merges with copies
                 fl1, fl2, fla = m1.flags(f), m2.flags(f), ma.flags(f)
                 if fl1 == fl2:
                     return fl1
                 if fl1 == fla:
                     return fl2
                 if fl2 == fla:
                     return fl1
                 return '' # punt for conflicts
 
         return func
 
     @propertycache
     def _flagfunc(self):
         return self._repo.dirstate.flagfunc(self._buildflagfunc)
 
     @propertycache
     def _manifest(self):
         """generate a manifest corresponding to the working directory"""
 
         man = self._parents[0].manifest().copy()
         if len(self._parents) > 1:
             man2 = self.p2().manifest()
             def getman(f):
                 if f in man:
                     return man
                 return man2
         else:
             getman = lambda f: man
 
         copied = self._repo.dirstate.copies()
         ff = self._flagfunc
         modified, added, removed, deleted = self._status
         for i, l in (("a", added), ("m", modified)):
             for f in l:
                 orig = copied.get(f, f)
                 man[f] = getman(orig).get(orig, nullid) + i
                 try:
                     man.set(f, ff(f))
                 except OSError:
                     pass
 
         for f in deleted + removed:
             if f in man:
                 del man[f]
 
         return man
 
     def __iter__(self):
         d = self._repo.dirstate
         for f in d:
             if d[f] != 'r':
                 yield f
 
     @propertycache
     def _status(self):
         return self._repo.status()[:4]
 
     @propertycache
     def _user(self):
         return self._repo.ui.username()
 
     @propertycache
     def _date(self):
         return util.makedate()
 
     @propertycache
     def _parents(self):
         p = self._repo.dirstate.parents()
         if p[1] == nullid:
             p = p[:-1]
         return [changectx(self._repo, x) for x in p]
 
     def status(self, ignored=False, clean=False, unknown=False):
         """Explicit status query
         Unless this method is used to query the working copy status, the
         _status property will implicitly read the status using its default
         arguments."""
         stat = self._repo.status(ignored=ignored, clean=clean, unknown=unknown)
         self._unknown = self._ignored = self._clean = None
         if unknown:
             self._unknown = stat[4]
         if ignored:
             self._ignored = stat[5]
         if clean:
             self._clean = stat[6]
         self._status = stat[:4]
         return stat
 
     def manifest(self):
         return self._manifest
     def user(self):
         return self._user or self._repo.ui.username()
     def date(self):
         return self._date
     def description(self):
         return self._text
     def files(self):
         return sorted(self._status[0] + self._status[1] + self._status[2])
 
     def modified(self):
         return self._status[0]
     def added(self):
         return self._status[1]
     def removed(self):
         return self._status[2]
     def deleted(self):
         return self._status[3]
     def unknown(self):
         assert self._unknown is not None  # must call status first
         return self._unknown
     def ignored(self):
         assert self._ignored is not None  # must call status first
         return self._ignored
     def clean(self):
         assert self._clean is not None  # must call status first
         return self._clean
     def branch(self):
         return encoding.tolocal(self._extra['branch'])
     def closesbranch(self):
         return 'close' in self._extra
     def extra(self):
         return self._extra
 
     def tags(self):
         t = []
         for p in self.parents():
             t.extend(p.tags())
         return t
 
     def bookmarks(self):
         b = []
         for p in self.parents():
             b.extend(p.bookmarks())
         return b
 
     def phase(self):
         phase = phases.draft # default phase to draft
         for p in self.parents():
             phase = max(phase, p.phase())
         return phase
 
     def hidden(self):
         return False
 
     def children(self):
         return []
 
     def flags(self, path):
         if '_manifest' in self.__dict__:
             try:
                 return self._manifest.flags(path)
             except KeyError:
                 return ''
 
         try:
             return self._flagfunc(path)
         except OSError:
             return ''
 
     def filectx(self, path, filelog=None):
         """get a file context from the working directory"""
         return workingfilectx(self._repo, path, workingctx=self,
                               filelog=filelog)
 
     def ancestor(self, c2):
         """return the ancestor context of self and c2"""
         return self._parents[0].ancestor(c2) # punt on two parents for now
 
     def walk(self, match):
         return sorted(self._repo.dirstate.walk(match, sorted(self.substate),
                                                True, False))
 
     def dirty(self, missing=False, merge=True, branch=True):
         "check whether a working directory is modified"
         # check subrepos first
         for s in sorted(self.substate):
             if self.sub(s).dirty():
                 return True
         # check current working dir
         return ((merge and self.p2()) or
                 (branch and self.branch() != self.p1().branch()) or
                 self.modified() or self.added() or self.removed() or
                 (missing and self.deleted()))
 
     def add(self, list, prefix=""):
         join = lambda f: os.path.join(prefix, f)
         wlock = self._repo.wlock()
         ui, ds = self._repo.ui, self._repo.dirstate
         try:
             rejected = []
             for f in list:
                 scmutil.checkportable(ui, join(f))
                 p = self._repo.wjoin(f)
                 try:
                     st = os.lstat(p)
                 except OSError:
                     ui.warn(_("%s does not exist!\n") % join(f))
                     rejected.append(f)
                     continue
                 if st.st_size > 10000000:
                     ui.warn(_("%s: up to %d MB of RAM may be required "
                               "to manage this file\n"
                               "(use 'hg revert %s' to cancel the "
                               "pending addition)\n")
                               % (f, 3 * st.st_size // 1000000, join(f)))
                 if not (stat.S_ISREG(st.st_mode) or stat.S_ISLNK(st.st_mode)):
                     ui.warn(_("%s not added: only files and symlinks "
                               "supported currently\n") % join(f))
                     rejected.append(p)
                 elif ds[f] in 'amn':
                     ui.warn(_("%s already tracked!\n") % join(f))
                 elif ds[f] == 'r':
                     ds.normallookup(f)
                 else:
                     ds.add(f)
             return rejected
         finally:
             wlock.release()
 
     def forget(self, files, prefix=""):
         join = lambda f: os.path.join(prefix, f)
         wlock = self._repo.wlock()
         try:
             rejected = []
             for f in files:
                 if f not in self._repo.dirstate:
                     self._repo.ui.warn(_("%s not tracked!\n") % join(f))
                     rejected.append(f)
                 elif self._repo.dirstate[f] != 'a':
                     self._repo.dirstate.remove(f)
                 else:
                     self._repo.dirstate.drop(f)
             return rejected
         finally:
             wlock.release()
 
     def ancestors(self):
         for a in self._repo.changelog.ancestors(
             [p.rev() for p in self._parents]):
             yield changectx(self._repo, a)
 
     def undelete(self, list):
         pctxs = self.parents()
         wlock = self._repo.wlock()
         try:
             for f in list:
                 if self._repo.dirstate[f] != 'r':
                     self._repo.ui.warn(_("%s not removed!\n") % f)
                 else:
                     fctx = f in pctxs[0] and pctxs[0][f] or pctxs[1][f]
                     t = fctx.data()
                     self._repo.wwrite(f, t, fctx.flags())
                     self._repo.dirstate.normal(f)
         finally:
             wlock.release()
 
     def copy(self, source, dest):
         p = self._repo.wjoin(dest)
         if not os.path.lexists(p):
             self._repo.ui.warn(_("%s does not exist!\n") % dest)
         elif not (os.path.isfile(p) or os.path.islink(p)):
             self._repo.ui.warn(_("copy failed: %s is not a file or a "
                                  "symbolic link\n") % dest)
         else:
             wlock = self._repo.wlock()
             try:
                 if self._repo.dirstate[dest] in '?r':
                     self._repo.dirstate.add(dest)
                 self._repo.dirstate.copy(source, dest)
             finally:
                 wlock.release()
 
     def markcommitted(self, node):
         """Perform post-commit cleanup necessary after committing this ctx
 
         Specifically, this updates backing stores this working context
         wraps to reflect the fact that the changes reflected by this
         workingctx have been committed.  For example, it marks
         modified and added files as normal in the dirstate.
 
         """
 
         for f in self.modified() + self.added():
             self._repo.dirstate.normal(f)
         for f in self.removed():
             self._repo.dirstate.drop(f)
         self._repo.dirstate.setparents(node)
 
     def dirs(self):
         return self._repo.dirstate.dirs()
 
 class workingfilectx(filectx):
     """A workingfilectx object makes access to data related to a particular
        file in the working directory convenient."""
     def __init__(self, repo, path, filelog=None, workingctx=None):
         """changeid can be a changeset revision, node, or tag.
            fileid can be a file revision or node."""
         self._repo = repo
         self._path = path
         self._changeid = None
         self._filerev = self._filenode = None
 
         if filelog:
             self._filelog = filelog
         if workingctx:
             self._changectx = workingctx
 
     @propertycache
     def _changectx(self):
         return workingctx(self._repo)
 
     def __nonzero__(self):
         return True
 
     def __str__(self):
         return "%s@%s" % (self.path(), self._changectx)
 
     def __repr__(self):
         return "<workingfilectx %s>" % str(self)
 
     def data(self):
         return self._repo.wread(self._path)
     def renamed(self):
         rp = self._repo.dirstate.copied(self._path)
         if not rp:
             return None
         return rp, self._changectx._parents[0]._manifest.get(rp, nullid)
 
     def parents(self):
         '''return parent filectxs, following copies if necessary'''
         def filenode(ctx, path):
             return ctx._manifest.get(path, nullid)
 
         path = self._path
         fl = self._filelog
         pcl = self._changectx._parents
         renamed = self.renamed()
 
         if renamed:
             pl = [renamed + (None,)]
         else:
             pl = [(path, filenode(pcl[0], path), fl)]
 
         for pc in pcl[1:]:
             pl.append((path, filenode(pc, path), fl))
 
         return [filectx(self._repo, p, fileid=n, filelog=l)
                 for p, n, l in pl if n != nullid]
 
     def children(self):
         return []
 
     def size(self):
         return os.lstat(self._repo.wjoin(self._path)).st_size
     def date(self):
         t, tz = self._changectx.date()
         try:
             return (int(os.lstat(self._repo.wjoin(self._path)).st_mtime), tz)
         except OSError, err:
             if err.errno != errno.ENOENT:
                 raise
             return (t, tz)
 
     def cmp(self, fctx):
         """compare with other file context
 
         returns True if different than fctx.
         """
         # fctx should be a filectx (not a workingfilectx)
         # invert comparison to reuse the same code path
         return fctx.cmp(self)
 
 class memctx(object):
     """Use memctx to perform in-memory commits via localrepo.commitctx().
 
     Revision information is supplied at initialization time while
     related files data and is made available through a callback
     mechanism.  'repo' is the current localrepo, 'parents' is a
     sequence of two parent revisions identifiers (pass None for every
     missing parent), 'text' is the commit message and 'files' lists
     names of files touched by the revision (normalized and relative to
     repository root).
 
     filectxfn(repo, memctx, path) is a callable receiving the
     repository, the current memctx object and the normalized path of
     requested file, relative to repository root. It is fired by the
     commit function for every file in 'files', but calls order is
     undefined. If the file is available in the revision being
     committed (updated or added), filectxfn returns a memfilectx
     object. If the file was removed, filectxfn raises an
     IOError. Moved files are represented by marking the source file
     removed and the new file added with copy information (see
     memfilectx).
 
     user receives the committer name and defaults to current
     repository username, date is the commit date in any format
     supported by util.parsedate() and defaults to current date, extra
     is a dictionary of metadata or is left empty.
     """
     def __init__(self, repo, parents, text, files, filectxfn, user=None,
                  date=None, extra=None):
         self._repo = repo
         self._rev = None
         self._node = None
         self._text = text
         self._date = date and util.parsedate(date) or util.makedate()
         self._user = user
         parents = [(p or nullid) for p in parents]
         p1, p2 = parents
         self._parents = [changectx(self._repo, p) for p in (p1, p2)]
         files = sorted(set(files))
         self._status = [files, [], [], [], []]
         self._filectxfn = filectxfn
 
         self._extra = extra and extra.copy() or {}
         if self._extra.get('branch', '') == '':
             self._extra['branch'] = 'default'
 
     def __str__(self):
         return str(self._parents[0]) + "+"
 
     def __int__(self):
         return self._rev
 
     def __nonzero__(self):
         return True
 
     def __getitem__(self, key):
         return self.filectx(key)
 
     def p1(self):
         return self._parents[0]
     def p2(self):
         return self._parents[1]
 
     def user(self):
         return self._user or self._repo.ui.username()
     def date(self):
         return self._date
     def description(self):
         return self._text
     def files(self):
         return self.modified()
     def modified(self):
         return self._status[0]
     def added(self):
         return self._status[1]
     def removed(self):
         return self._status[2]
     def deleted(self):
         return self._status[3]
     def unknown(self):
         return self._status[4]
     def ignored(self):
         return self._status[5]
     def clean(self):
         return self._status[6]
     def branch(self):
         return encoding.tolocal(self._extra['branch'])
     def extra(self):
         return self._extra
     def flags(self, f):
         return self[f].flags()
 
     def parents(self):
         """return contexts for each parent changeset"""
         return self._parents
 
     def filectx(self, path, filelog=None):
         """get a file context from the working directory"""
         return self._filectxfn(self._repo, self, path)
 
     def commit(self):
         """commit context to the repo"""
         return self._repo.commitctx(self)
 
 class memfilectx(object):
     """memfilectx represents an in-memory file to commit.
 
     See memctx for more details.
     """
     def __init__(self, path, data, islink=False, isexec=False, copied=None):
         """
         path is the normalized file path relative to repository root.
         data is the file content as a string.
         islink is True if the file is a symbolic link.
         isexec is True if the file is executable.
         copied is the source file path if current file was copied in the
         revision being committed, or None."""
         self._path = path
         self._data = data
         self._flags = (islink and 'l' or '') + (isexec and 'x' or '')
         self._copied = None
         if copied:
             self._copied = (copied, nullid)
 
     def __nonzero__(self):
         return True
     def __str__(self):
         return "%s@%s" % (self.path(), self._changectx)
     def path(self):
         return self._path
     def data(self):
         return self._data
     def flags(self):
         return self._flags
     def isexec(self):
         return 'x' in self._flags
     def islink(self):
         return 'l' in self._flags
     def renamed(self):
         return self._copied

mercurial/parsers.c

@@ -1,1573 +1,1935 b''
 /*
  parsers.c - efficient content parsing
 
  Copyright 2008 Matt Mackall <[e-mail]> and others
 
  This software may be used and distributed according to the terms of
  the GNU General Public License, incorporated herein by reference.
 */
 
 #include <Python.h>
 #include <ctype.h>
 #include <stddef.h>
 #include <string.h>
 
 #include "util.h"
 
 static inline int hexdigit(const char *p, Py_ssize_t off)
 {
 	char c = p[off];
 
 	if (c >= '0' && c <= '9')
 		return c - '0';
 	if (c >= 'a' && c <= 'f')
 		return c - 'a' + 10;
 	if (c >= 'A' && c <= 'F')
 		return c - 'A' + 10;
 
 	PyErr_SetString(PyExc_ValueError, "input contains non-hex character");
 	return 0;
 }
 
 /*
  * Turn a hex-encoded string into binary.
  */
 static PyObject *unhexlify(const char *str, int len)
 {
 	PyObject *ret;
 	char *d;
 	int i;
 
 	ret = PyBytes_FromStringAndSize(NULL, len / 2);
 
 	if (!ret)
 		return NULL;
 
 	d = PyBytes_AsString(ret);
 
 	for (i = 0; i < len;) {
 		int hi = hexdigit(str, i++);
 		int lo = hexdigit(str, i++);
 		*d++ = (hi << 4) | lo;
 	}
 
 	return ret;
 }
 
 /*
  * This code assumes that a manifest is stitched together with newline
  * ('\n') characters.
  */
 static PyObject *parse_manifest(PyObject *self, PyObject *args)
 {
 	PyObject *mfdict, *fdict;
 	char *str, *cur, *start, *zero;
 	int len;
 
 	if (!PyArg_ParseTuple(args, "O!O!s#:parse_manifest",
 			      &PyDict_Type, &mfdict,
 			      &PyDict_Type, &fdict,
 			      &str, &len))
 		goto quit;
 
 	for (start = cur = str, zero = NULL; cur < str + len; cur++) {
 		PyObject *file = NULL, *node = NULL;
 		PyObject *flags = NULL;
 		ptrdiff_t nlen;
 
 		if (!*cur) {
 			zero = cur;
 			continue;
 		}
 		else if (*cur != '\n')
 			continue;
 
 		if (!zero) {
 			PyErr_SetString(PyExc_ValueError,
 					"manifest entry has no separator");
 			goto quit;
 		}
 
 		file = PyBytes_FromStringAndSize(start, zero - start);
 
 		if (!file)
 			goto bail;
 
 		nlen = cur - zero - 1;
 
 		node = unhexlify(zero + 1, nlen > 40 ? 40 : (int)nlen);
 		if (!node)
 			goto bail;
 
 		if (nlen > 40) {
 			flags = PyBytes_FromStringAndSize(zero + 41,
 							   nlen - 40);
 			if (!flags)
 				goto bail;
 
 			if (PyDict_SetItem(fdict, file, flags) == -1)
 				goto bail;
 		}
 
 		if (PyDict_SetItem(mfdict, file, node) == -1)
 			goto bail;
 
 		start = cur + 1;
 		zero = NULL;
 
 		Py_XDECREF(flags);
 		Py_XDECREF(node);
 		Py_XDECREF(file);
 		continue;
 	bail:
 		Py_XDECREF(flags);
 		Py_XDECREF(node);
 		Py_XDECREF(file);
 		goto quit;
 	}
 
 	if (len > 0 && *(cur - 1) != '\n') {
 		PyErr_SetString(PyExc_ValueError,
 				"manifest contains trailing garbage");
 		goto quit;
 	}
 
 	Py_INCREF(Py_None);
 	return Py_None;
 quit:
 	return NULL;
 }
 
 static PyObject *parse_dirstate(PyObject *self, PyObject *args)
 {
 	PyObject *dmap, *cmap, *parents = NULL, *ret = NULL;
 	PyObject *fname = NULL, *cname = NULL, *entry = NULL;
 	char *str, *cur, *end, *cpos;
 	int state, mode, size, mtime;
 	unsigned int flen;
 	int len;
 
 	if (!PyArg_ParseTuple(args, "O!O!s#:parse_dirstate",
 			      &PyDict_Type, &dmap,
 			      &PyDict_Type, &cmap,
 			      &str, &len))
 		goto quit;
 
 	/* read parents */
 	if (len < 40)
 		goto quit;
 
 	parents = Py_BuildValue("s#s#", str, 20, str + 20, 20);
 	if (!parents)
 		goto quit;
 
 	/* read filenames */
 	cur = str + 40;
 	end = str + len;
 
 	while (cur < end - 17) {
 		/* unpack header */
 		state = *cur;
 		mode = getbe32(cur + 1);
 		size = getbe32(cur + 5);
 		mtime = getbe32(cur + 9);
 		flen = getbe32(cur + 13);
 		cur += 17;
 		if (cur + flen > end || cur + flen < cur) {
 			PyErr_SetString(PyExc_ValueError, "overflow in dirstate");
 			goto quit;
 		}
 
 		entry = Py_BuildValue("ciii", state, mode, size, mtime);
 		if (!entry)
 			goto quit;
 		PyObject_GC_UnTrack(entry); /* don't waste time with this */
 
 		cpos = memchr(cur, 0, flen);
 		if (cpos) {
 			fname = PyBytes_FromStringAndSize(cur, cpos - cur);
 			cname = PyBytes_FromStringAndSize(cpos + 1,
 							   flen - (cpos - cur) - 1);
 			if (!fname || !cname ||
 			    PyDict_SetItem(cmap, fname, cname) == -1 ||
 			    PyDict_SetItem(dmap, fname, entry) == -1)
 				goto quit;
 			Py_DECREF(cname);
 		} else {
 			fname = PyBytes_FromStringAndSize(cur, flen);
 			if (!fname ||
 			    PyDict_SetItem(dmap, fname, entry) == -1)
 				goto quit;
 		}
 		cur += flen;
 		Py_DECREF(fname);
 		Py_DECREF(entry);
 		fname = cname = entry = NULL;
 	}
 
 	ret = parents;
 	Py_INCREF(ret);
 quit:
 	Py_XDECREF(fname);
 	Py_XDECREF(cname);
 	Py_XDECREF(entry);
 	Py_XDECREF(parents);
 	return ret;
 }
 
 static inline int getintat(PyObject *tuple, int off, uint32_t *v)
 {
 	PyObject *o = PyTuple_GET_ITEM(tuple, off);
 	long val;
 
 	if (PyInt_Check(o))
 		val = PyInt_AS_LONG(o);
 	else if (PyLong_Check(o)) {
 		val = PyLong_AsLong(o);
 		if (val == -1 && PyErr_Occurred())
 			return -1;
 	} else {
 		PyErr_SetString(PyExc_TypeError, "expected an int or long");
 		return -1;
 	}
 	if (LONG_MAX > INT_MAX && (val > INT_MAX || val < INT_MIN)) {
 		PyErr_SetString(PyExc_OverflowError,
 				"Python value to large to convert to uint32_t");
 		return -1;
 	}
 	*v = (uint32_t)val;
 	return 0;
 }
 
 static PyObject *dirstate_unset;
 
 /*
  * Efficiently pack a dirstate object into its on-disk format.
  */
 static PyObject *pack_dirstate(PyObject *self, PyObject *args)
 {
 	PyObject *packobj = NULL;
 	PyObject *map, *copymap, *pl;
 	Py_ssize_t nbytes, pos, l;
 	PyObject *k, *v, *pn;
 	char *p, *s;
 	double now;
 
 	if (!PyArg_ParseTuple(args, "O!O!Od:pack_dirstate",
 			      &PyDict_Type, &map, &PyDict_Type, &copymap,
 			      &pl, &now))
 		return NULL;
 
 	if (!PySequence_Check(pl) || PySequence_Size(pl) != 2) {
 		PyErr_SetString(PyExc_TypeError, "expected 2-element sequence");
 		return NULL;
 	}
 
 	/* Figure out how much we need to allocate. */
 	for (nbytes = 40, pos = 0; PyDict_Next(map, &pos, &k, &v);) {
 		PyObject *c;
 		if (!PyString_Check(k)) {
 			PyErr_SetString(PyExc_TypeError, "expected string key");
 			goto bail;
 		}
 		nbytes += PyString_GET_SIZE(k) + 17;
 		c = PyDict_GetItem(copymap, k);
 		if (c) {
 			if (!PyString_Check(c)) {
 				PyErr_SetString(PyExc_TypeError,
 						"expected string key");
 				goto bail;
 			}
 			nbytes += PyString_GET_SIZE(c) + 1;
 		}
 	}
 
 	packobj = PyString_FromStringAndSize(NULL, nbytes);
 	if (packobj == NULL)
 		goto bail;
 
 	p = PyString_AS_STRING(packobj);
 
 	pn = PySequence_ITEM(pl, 0);
 	if (PyString_AsStringAndSize(pn, &s, &l) == -1 || l != 20) {
 		PyErr_SetString(PyExc_TypeError, "expected a 20-byte hash");
 		goto bail;
 	}
 	memcpy(p, s, l);
 	p += 20;
 	pn = PySequence_ITEM(pl, 1);
 	if (PyString_AsStringAndSize(pn, &s, &l) == -1 || l != 20) {
 		PyErr_SetString(PyExc_TypeError, "expected a 20-byte hash");
 		goto bail;
 	}
 	memcpy(p, s, l);
 	p += 20;
 
 	for (pos = 0; PyDict_Next(map, &pos, &k, &v); ) {
 		uint32_t mode, size, mtime;
 		Py_ssize_t len, l;
 		PyObject *o;
 		char *s, *t;
 
 		if (!PyTuple_Check(v) || PyTuple_GET_SIZE(v) != 4) {
 			PyErr_SetString(PyExc_TypeError, "expected a 4-tuple");
 			goto bail;
 		}
 		o = PyTuple_GET_ITEM(v, 0);
 		if (PyString_AsStringAndSize(o, &s, &l) == -1 || l != 1) {
 			PyErr_SetString(PyExc_TypeError, "expected one byte");
 			goto bail;
 		}
 		*p++ = *s;
 		if (getintat(v, 1, &mode) == -1)
 			goto bail;
 		if (getintat(v, 2, &size) == -1)
 			goto bail;
 		if (getintat(v, 3, &mtime) == -1)
 			goto bail;
 		if (*s == 'n' && mtime == (uint32_t)now) {
 			/* See pure/parsers.py:pack_dirstate for why we do
 			 * this. */
 			if (PyDict_SetItem(map, k, dirstate_unset) == -1)
 				goto bail;
 			mode = 0, size = -1, mtime = -1;
 		}
 		putbe32(mode, p);
 		putbe32(size, p + 4);
 		putbe32(mtime, p + 8);
 		t = p + 12;
 		p += 16;
 		len = PyString_GET_SIZE(k);
 		memcpy(p, PyString_AS_STRING(k), len);
 		p += len;
 		o = PyDict_GetItem(copymap, k);
 		if (o) {
 			*p++ = '\0';
 			l = PyString_GET_SIZE(o);
 			memcpy(p, PyString_AS_STRING(o), l);
 			p += l;
 			len += l + 1;
 		}
 		putbe32((uint32_t)len, t);
 	}
 
 	pos = p - PyString_AS_STRING(packobj);
 	if (pos != nbytes) {
 		PyErr_Format(PyExc_SystemError, "bad dirstate size: %ld != %ld",
                              (long)pos, (long)nbytes);
 		goto bail;
 	}
 
 	return packobj;
 bail:
 	Py_XDECREF(packobj);
 	return NULL;
 }
 
 /*
  * A base-16 trie for fast node->rev mapping.
  *
  * Positive value is index of the next node in the trie
  * Negative value is a leaf: -(rev + 1)
  * Zero is empty
  */
 typedef struct {
 	int children[16];
 } nodetree;
 
 /*
  * This class has two behaviours.
  *
  * When used in a list-like way (with integer keys), we decode an
  * entry in a RevlogNG index file on demand. Our last entry is a
  * sentinel, always a nullid.  We have limited support for
  * integer-keyed insert and delete, only at elements right before the
  * sentinel.
  *
  * With string keys, we lazily perform a reverse mapping from node to
  * rev, using a base-16 trie.
  */
 typedef struct {
 	PyObject_HEAD
 	/* Type-specific fields go here. */
 	PyObject *data;        /* raw bytes of index */
 	PyObject **cache;      /* cached tuples */
 	const char **offsets;  /* populated on demand */
 	Py_ssize_t raw_length; /* original number of elements */
 	Py_ssize_t length;     /* current number of elements */
 	PyObject *added;       /* populated on demand */
 	PyObject *headrevs;    /* cache, invalidated on changes */
 	nodetree *nt;          /* base-16 trie */
 	int ntlength;          /* # nodes in use */
 	int ntcapacity;        /* # nodes allocated */
 	int ntdepth;           /* maximum depth of tree */
 	int ntsplits;          /* # splits performed */
 	int ntrev;             /* last rev scanned */
 	int ntlookups;         /* # lookups */
 	int ntmisses;          /* # lookups that miss the cache */
 	int inlined;
 } indexObject;
 
 static Py_ssize_t index_length(const indexObject *self)
 {
 	if (self->added == NULL)
 		return self->length;
 	return self->length + PyList_GET_SIZE(self->added);
 }
 
 static PyObject *nullentry;
 static const char nullid[20];
 
 static long inline_scan(indexObject *self, const char **offsets);
 
 #if LONG_MAX == 0x7fffffffL
 static char *tuple_format = "Kiiiiiis#";
 #else
 static char *tuple_format = "kiiiiiis#";
 #endif
 
 /* A RevlogNG v1 index entry is 64 bytes long. */
 static const long v1_hdrsize = 64;
 
 /*
  * Return a pointer to the beginning of a RevlogNG record.
  */
 static const char *index_deref(indexObject *self, Py_ssize_t pos)
 {
 	if (self->inlined && pos > 0) {
 		if (self->offsets == NULL) {
 			self->offsets = malloc(self->raw_length *
 					       sizeof(*self->offsets));
 			if (self->offsets == NULL)
 				return (const char *)PyErr_NoMemory();
 			inline_scan(self, self->offsets);
 		}
 		return self->offsets[pos];
 	}
 
 	return PyString_AS_STRING(self->data) + pos * v1_hdrsize;
 }
 
 /*
  * RevlogNG format (all in big endian, data may be inlined):
  *    6 bytes: offset
  *    2 bytes: flags
  *    4 bytes: compressed length
  *    4 bytes: uncompressed length
  *    4 bytes: base revision
  *    4 bytes: link revision
  *    4 bytes: parent 1 revision
  *    4 bytes: parent 2 revision
  *   32 bytes: nodeid (only 20 bytes used)
  */
 static PyObject *index_get(indexObject *self, Py_ssize_t pos)
 {
 	uint64_t offset_flags;
 	int comp_len, uncomp_len, base_rev, link_rev, parent_1, parent_2;
 	const char *c_node_id;
 	const char *data;
 	Py_ssize_t length = index_length(self);
 	PyObject *entry;
 
 	if (pos < 0)
 		pos += length;
 
 	if (pos < 0 || pos >= length) {
 		PyErr_SetString(PyExc_IndexError, "revlog index out of range");
 		return NULL;
 	}
 
 	if (pos == length - 1) {
 		Py_INCREF(nullentry);
 		return nullentry;
 	}
 
 	if (pos >= self->length - 1) {
 		PyObject *obj;
 		obj = PyList_GET_ITEM(self->added, pos - self->length + 1);
 		Py_INCREF(obj);
 		return obj;
 	}
 
 	if (self->cache) {
 		if (self->cache[pos]) {
 			Py_INCREF(self->cache[pos]);
 			return self->cache[pos];
 		}
 	} else {
 		self->cache = calloc(self->raw_length, sizeof(PyObject *));
 		if (self->cache == NULL)
 			return PyErr_NoMemory();
 	}
 
 	data = index_deref(self, pos);
 	if (data == NULL)
 		return NULL;
 
 	offset_flags = getbe32(data + 4);
 	if (pos == 0) /* mask out version number for the first entry */
 		offset_flags &= 0xFFFF;
 	else {
 		uint32_t offset_high = getbe32(data);
 		offset_flags |= ((uint64_t)offset_high) << 32;
 	}
 
 	comp_len = getbe32(data + 8);
 	uncomp_len = getbe32(data + 12);
 	base_rev = getbe32(data + 16);
 	link_rev = getbe32(data + 20);
 	parent_1 = getbe32(data + 24);
 	parent_2 = getbe32(data + 28);
 	c_node_id = data + 32;
 
 	entry = Py_BuildValue(tuple_format, offset_flags, comp_len,
 			      uncomp_len, base_rev, link_rev,
 			      parent_1, parent_2, c_node_id, 20);
 
 	if (entry)
 		PyObject_GC_UnTrack(entry);
 
 	self->cache[pos] = entry;
 	Py_INCREF(entry);
 
 	return entry;
 }
 
 /*
  * Return the 20-byte SHA of the node corresponding to the given rev.
  */
 static const char *index_node(indexObject *self, Py_ssize_t pos)
 {
 	Py_ssize_t length = index_length(self);
 	const char *data;
 
 	if (pos == length - 1 || pos == INT_MAX)
 		return nullid;
 
 	if (pos >= length)
 		return NULL;
 
 	if (pos >= self->length - 1) {
 		PyObject *tuple, *str;
 		tuple = PyList_GET_ITEM(self->added, pos - self->length + 1);
 		str = PyTuple_GetItem(tuple, 7);
 		return str ? PyString_AS_STRING(str) : NULL;
 	}
 
 	data = index_deref(self, pos);
 	return data ? data + 32 : NULL;
 }
 
 static int nt_insert(indexObject *self, const char *node, int rev);
 
 static int node_check(PyObject *obj, char **node, Py_ssize_t *nodelen)
 {
 	if (PyString_AsStringAndSize(obj, node, nodelen) == -1)
 		return -1;
 	if (*nodelen == 20)
 		return 0;
 	PyErr_SetString(PyExc_ValueError, "20-byte hash required");
 	return -1;
 }
 
 static PyObject *index_insert(indexObject *self, PyObject *args)
 {
 	PyObject *obj;
 	char *node;
 	long offset;
 	Py_ssize_t len, nodelen;
 
 	if (!PyArg_ParseTuple(args, "lO", &offset, &obj))
 		return NULL;
 
 	if (!PyTuple_Check(obj) || PyTuple_GET_SIZE(obj) != 8) {
 		PyErr_SetString(PyExc_TypeError, "8-tuple required");
 		return NULL;
 	}
 
 	if (node_check(PyTuple_GET_ITEM(obj, 7), &node, &nodelen) == -1)
 		return NULL;
 
 	len = index_length(self);
 
 	if (offset < 0)
 		offset += len;
 
 	if (offset != len - 1) {
 		PyErr_SetString(PyExc_IndexError,
 				"insert only supported at index -1");
 		return NULL;
 	}
 
 	if (offset > INT_MAX) {
 		PyErr_SetString(PyExc_ValueError,
 				"currently only 2**31 revs supported");
 		return NULL;
 	}
 
 	if (self->added == NULL) {
 		self->added = PyList_New(0);
 		if (self->added == NULL)
 			return NULL;
 	}
 
 	if (PyList_Append(self->added, obj) == -1)
 		return NULL;
 
 	if (self->nt)
 		nt_insert(self, node, (int)offset);
 
 	Py_CLEAR(self->headrevs);
 	Py_RETURN_NONE;
 }
 
 static void _index_clearcaches(indexObject *self)
 {
 	if (self->cache) {
 		Py_ssize_t i;
 
 		for (i = 0; i < self->raw_length; i++)
 			Py_CLEAR(self->cache[i]);
 		free(self->cache);
 		self->cache = NULL;
 	}
 	if (self->offsets) {
 		free(self->offsets);
 		self->offsets = NULL;
 	}
 	if (self->nt) {
 		free(self->nt);
 		self->nt = NULL;
 	}
 	Py_CLEAR(self->headrevs);
 }
 
 static PyObject *index_clearcaches(indexObject *self)
 {
 	_index_clearcaches(self);
 	self->ntlength = self->ntcapacity = 0;
 	self->ntdepth = self->ntsplits = 0;
 	self->ntrev = -1;
 	self->ntlookups = self->ntmisses = 0;
 	Py_RETURN_NONE;
 }
 
 static PyObject *index_stats(indexObject *self)
 {
 	PyObject *obj = PyDict_New();
 
 	if (obj == NULL)
 		return NULL;
 
 #define istat(__n, __d) \
 	if (PyDict_SetItemString(obj, __d, PyInt_FromSsize_t(self->__n)) == -1) \
 		goto bail;
 
 	if (self->added) {
 		Py_ssize_t len = PyList_GET_SIZE(self->added);
 		if (PyDict_SetItemString(obj, "index entries added",
 					 PyInt_FromSsize_t(len)) == -1)
 			goto bail;
 	}
 
 	if (self->raw_length != self->length - 1)
 		istat(raw_length, "revs on disk");
 	istat(length, "revs in memory");
 	istat(ntcapacity, "node trie capacity");
 	istat(ntdepth, "node trie depth");
 	istat(ntlength, "node trie count");
 	istat(ntlookups, "node trie lookups");
 	istat(ntmisses, "node trie misses");
 	istat(ntrev, "node trie last rev scanned");
 	istat(ntsplits, "node trie splits");
 
 #undef istat
 
 	return obj;
 
 bail:
 	Py_XDECREF(obj);
 	return NULL;
 }
 
 /*
  * When we cache a list, we want to be sure the caller can't mutate
  * the cached copy.
  */
 static PyObject *list_copy(PyObject *list)
 {
 	Py_ssize_t len = PyList_GET_SIZE(list);
 	PyObject *newlist = PyList_New(len);
 	Py_ssize_t i;
 
 	if (newlist == NULL)
 		return NULL;
 
 	for (i = 0; i < len; i++) {
 		PyObject *obj = PyList_GET_ITEM(list, i);
 		Py_INCREF(obj);
 		PyList_SET_ITEM(newlist, i, obj);
 	}
 
 	return newlist;
 }
 
 static PyObject *index_headrevs(indexObject *self)
 {
 	Py_ssize_t i, len, addlen;
 	char *nothead = NULL;
 	PyObject *heads;
 
 	if (self->headrevs)
 		return list_copy(self->headrevs);
 
 	len = index_length(self) - 1;
 	heads = PyList_New(0);
 	if (heads == NULL)
 		goto bail;
 	if (len == 0) {
 		PyObject *nullid = PyInt_FromLong(-1);
 		if (nullid == NULL || PyList_Append(heads, nullid) == -1) {
 			Py_XDECREF(nullid);
 			goto bail;
 		}
 		goto done;
 	}
 
 	nothead = calloc(len, 1);
 	if (nothead == NULL)
 		goto bail;
 
 	for (i = 0; i < self->raw_length; i++) {
 		const char *data = index_deref(self, i);
 		int parent_1 = getbe32(data + 24);
 		int parent_2 = getbe32(data + 28);
 		if (parent_1 >= 0)
 			nothead[parent_1] = 1;
 		if (parent_2 >= 0)
 			nothead[parent_2] = 1;
 	}
 
 	addlen = self->added ? PyList_GET_SIZE(self->added) : 0;
 
 	for (i = 0; i < addlen; i++) {
 		PyObject *rev = PyList_GET_ITEM(self->added, i);
 		PyObject *p1 = PyTuple_GET_ITEM(rev, 5);
 		PyObject *p2 = PyTuple_GET_ITEM(rev, 6);
 		long parent_1, parent_2;
 
 		if (!PyInt_Check(p1) || !PyInt_Check(p2)) {
 			PyErr_SetString(PyExc_TypeError,
 					"revlog parents are invalid");
 			goto bail;
 		}
 		parent_1 = PyInt_AS_LONG(p1);
 		parent_2 = PyInt_AS_LONG(p2);
 		if (parent_1 >= 0)
 			nothead[parent_1] = 1;
 		if (parent_2 >= 0)
 			nothead[parent_2] = 1;
 	}
 
 	for (i = 0; i < len; i++) {
 		PyObject *head;
 
 		if (nothead[i])
 			continue;
 		head = PyInt_FromLong(i);
 		if (head == NULL || PyList_Append(heads, head) == -1) {
 			Py_XDECREF(head);
 			goto bail;
 		}
 	}
 
 done:
 	self->headrevs = heads;
 	free(nothead);
 	return list_copy(self->headrevs);
 bail:
 	Py_XDECREF(heads);
 	free(nothead);
 	return NULL;
 }
 
 static inline int nt_level(const char *node, Py_ssize_t level)
 {
 	int v = node[level>>1];
 	if (!(level & 1))
 		v >>= 4;
 	return v & 0xf;
 }
 
 /*
  * Return values:
  *
  *   -4: match is ambiguous (multiple candidates)
  *   -2: not found
  * rest: valid rev
  */
 static int nt_find(indexObject *self, const char *node, Py_ssize_t nodelen,
 		   int hex)
 {
 	int (*getnybble)(const char *, Py_ssize_t) = hex ? hexdigit : nt_level;
 	int level, maxlevel, off;
 
 	if (nodelen == 20 && node[0] == '\0' && memcmp(node, nullid, 20) == 0)
 		return -1;
 
 	if (self->nt == NULL)
 		return -2;
 
 	if (hex)
 		maxlevel = nodelen > 40 ? 40 : (int)nodelen;
 	else
 		maxlevel = nodelen > 20 ? 40 : ((int)nodelen * 2);
 
 	for (level = off = 0; level < maxlevel; level++) {
 		int k = getnybble(node, level);
 		nodetree *n = &self->nt[off];
 		int v = n->children[k];
 
 		if (v < 0) {
 			const char *n;
 			Py_ssize_t i;
 
 			v = -v - 1;
 			n = index_node(self, v);
 			if (n == NULL)
 				return -2;
 			for (i = level; i < maxlevel; i++)
 				if (getnybble(node, i) != nt_level(n, i))
 					return -2;
 			return v;
 		}
 		if (v == 0)
 			return -2;
 		off = v;
 	}
 	/* multiple matches against an ambiguous prefix */
 	return -4;
 }
 
 static int nt_new(indexObject *self)
 {
 	if (self->ntlength == self->ntcapacity) {
 		self->ntcapacity *= 2;
 		self->nt = realloc(self->nt,
 				   self->ntcapacity * sizeof(nodetree));
 		if (self->nt == NULL) {
 			PyErr_SetString(PyExc_MemoryError, "out of memory");
 			return -1;
 		}
 		memset(&self->nt[self->ntlength], 0,
 		       sizeof(nodetree) * (self->ntcapacity - self->ntlength));
 	}
 	return self->ntlength++;
 }
 
 static int nt_insert(indexObject *self, const char *node, int rev)
 {
 	int level = 0;
 	int off = 0;
 
 	while (level < 40) {
 		int k = nt_level(node, level);
 		nodetree *n;
 		int v;
 
 		n = &self->nt[off];
 		v = n->children[k];
 
 		if (v == 0) {
 			n->children[k] = -rev - 1;
 			return 0;
 		}
 		if (v < 0) {
 			const char *oldnode = index_node(self, -v - 1);
 			int noff;
 
 			if (!oldnode || !memcmp(oldnode, node, 20)) {
 				n->children[k] = -rev - 1;
 				return 0;
 			}
 			noff = nt_new(self);
 			if (noff == -1)
 				return -1;
 			/* self->nt may have been changed by realloc */
 			self->nt[off].children[k] = noff;
 			off = noff;
 			n = &self->nt[off];
 			n->children[nt_level(oldnode, ++level)] = v;
 			if (level > self->ntdepth)
 				self->ntdepth = level;
 			self->ntsplits += 1;
 		} else {
 			level += 1;
 			off = v;
 		}
 	}
 
 	return -1;
 }
 
 static int nt_init(indexObject *self)
 {
 	if (self->nt == NULL) {
 		self->ntcapacity = self->raw_length < 4
 			? 4 : self->raw_length / 2;
 		self->nt = calloc(self->ntcapacity, sizeof(nodetree));
 		if (self->nt == NULL) {
 			PyErr_NoMemory();
 			return -1;
 		}
 		self->ntlength = 1;
 		self->ntrev = (int)index_length(self) - 1;
 		self->ntlookups = 1;
 		self->ntmisses = 0;
 		if (nt_insert(self, nullid, INT_MAX) == -1)
 			return -1;
 	}
 	return 0;
 }
 
 /*
  * Return values:
  *
  *   -3: error (exception set)
  *   -2: not found (no exception set)
  * rest: valid rev
  */
 static int index_find_node(indexObject *self,
 			   const char *node, Py_ssize_t nodelen)
 {
 	int rev;
 
 	self->ntlookups++;
 	rev = nt_find(self, node, nodelen, 0);
 	if (rev >= -1)
 		return rev;
 
 	if (nt_init(self) == -1)
 		return -3;
 
 	/*
 	 * For the first handful of lookups, we scan the entire index,
 	 * and cache only the matching nodes. This optimizes for cases
 	 * like "hg tip", where only a few nodes are accessed.
 	 *
 	 * After that, we cache every node we visit, using a single
 	 * scan amortized over multiple lookups.  This gives the best
 	 * bulk performance, e.g. for "hg log".
 	 */
 	if (self->ntmisses++ < 4) {
 		for (rev = self->ntrev - 1; rev >= 0; rev--) {
 			const char *n = index_node(self, rev);
 			if (n == NULL)
 				return -2;
 			if (memcmp(node, n, nodelen > 20 ? 20 : nodelen) == 0) {
 				if (nt_insert(self, n, rev) == -1)
 					return -3;
 				break;
 			}
 		}
 	} else {
 		for (rev = self->ntrev - 1; rev >= 0; rev--) {
 			const char *n = index_node(self, rev);
 			if (n == NULL) {
 				self->ntrev = rev + 1;
 				return -2;
 			}
 			if (nt_insert(self, n, rev) == -1) {
 				self->ntrev = rev + 1;
 				return -3;
 			}
 			if (memcmp(node, n, nodelen > 20 ? 20 : nodelen) == 0) {
 				break;
 			}
 		}
 		self->ntrev = rev;
 	}
 
 	if (rev >= 0)
 		return rev;
 	return -2;
 }
 
 static PyObject *raise_revlog_error(void)
 {
 	static PyObject *errclass;
 	PyObject *mod = NULL, *errobj;
 
 	if (errclass == NULL) {
 		PyObject *dict;
 
 		mod = PyImport_ImportModule("mercurial.error");
 		if (mod == NULL)
 			goto classfail;
 
 		dict = PyModule_GetDict(mod);
 		if (dict == NULL)
 			goto classfail;
 
 		errclass = PyDict_GetItemString(dict, "RevlogError");
 		if (errclass == NULL) {
 			PyErr_SetString(PyExc_SystemError,
 					"could not find RevlogError");
 			goto classfail;
 		}
 		Py_INCREF(errclass);
 	}
 
 	errobj = PyObject_CallFunction(errclass, NULL);
 	if (errobj == NULL)
 		return NULL;
 	PyErr_SetObject(errclass, errobj);
 	return errobj;
 
 classfail:
 	Py_XDECREF(mod);
 	return NULL;
 }
 
 static PyObject *index_getitem(indexObject *self, PyObject *value)
 {
 	char *node;
 	Py_ssize_t nodelen;
 	int rev;
 
 	if (PyInt_Check(value))
 		return index_get(self, PyInt_AS_LONG(value));
 
 	if (node_check(value, &node, &nodelen) == -1)
 		return NULL;
 	rev = index_find_node(self, node, nodelen);
 	if (rev >= -1)
 		return PyInt_FromLong(rev);
 	if (rev == -2)
 		raise_revlog_error();
 	return NULL;
 }
 
 static int nt_partialmatch(indexObject *self, const char *node,
 			   Py_ssize_t nodelen)
 {
 	int rev;
 
 	if (nt_init(self) == -1)
 		return -3;
 
 	if (self->ntrev > 0) {
 		/* ensure that the radix tree is fully populated */
 		for (rev = self->ntrev - 1; rev >= 0; rev--) {
 			const char *n = index_node(self, rev);
 			if (n == NULL)
 				return -2;
 			if (nt_insert(self, n, rev) == -1)
 				return -3;
 		}
 		self->ntrev = rev;
 	}
 
 	return nt_find(self, node, nodelen, 1);
 }
 
 static PyObject *index_partialmatch(indexObject *self, PyObject *args)
 {
 	const char *fullnode;
 	int nodelen;
 	char *node;
 	int rev, i;
 
 	if (!PyArg_ParseTuple(args, "s#", &node, &nodelen))
 		return NULL;
 
 	if (nodelen < 4) {
 		PyErr_SetString(PyExc_ValueError, "key too short");
 		return NULL;
 	}
 
 	if (nodelen > 40) {
 		PyErr_SetString(PyExc_ValueError, "key too long");
 		return NULL;
 	}
 
 	for (i = 0; i < nodelen; i++)
 		hexdigit(node, i);
 	if (PyErr_Occurred()) {
 		/* input contains non-hex characters */
 		PyErr_Clear();
 		Py_RETURN_NONE;
 	}
 
 	rev = nt_partialmatch(self, node, nodelen);
 
 	switch (rev) {
 	case -4:
 		raise_revlog_error();
 	case -3:
 		return NULL;
 	case -2:
 		Py_RETURN_NONE;
 	case -1:
 		return PyString_FromStringAndSize(nullid, 20);
 	}
 
 	fullnode = index_node(self, rev);
 	if (fullnode == NULL) {
 		PyErr_Format(PyExc_IndexError,
 			     "could not access rev %d", rev);
 		return NULL;
 	}
 	return PyString_FromStringAndSize(fullnode, 20);
 }
 
 static PyObject *index_m_get(indexObject *self, PyObject *args)
 {
 	Py_ssize_t nodelen;
 	PyObject *val;
 	char *node;
 	int rev;
 
 	if (!PyArg_ParseTuple(args, "O", &val))
 		return NULL;
 	if (node_check(val, &node, &nodelen) == -1)
 		return NULL;
 	rev = index_find_node(self, node, nodelen);
 	if (rev ==  -3)
 		return NULL;
 	if (rev == -2)
 		Py_RETURN_NONE;
 	return PyInt_FromLong(rev);
 }
 
 static int index_contains(indexObject *self, PyObject *value)
 {
 	char *node;
 	Py_ssize_t nodelen;
 
 	if (PyInt_Check(value)) {
 		long rev = PyInt_AS_LONG(value);
 		return rev >= -1 && rev < index_length(self);
 	}
 
 	if (node_check(value, &node, &nodelen) == -1)
 		return -1;
 
 	switch (index_find_node(self, node, nodelen)) {
 	case -3:
 		return -1;
 	case -2:
 		return 0;
 	default:
 		return 1;
 	}
 }
 
+static inline void index_get_parents(indexObject *self, int rev, int *ps)
+{
+	if (rev >= self->length - 1) {
+		PyObject *tuple = PyList_GET_ITEM(self->added,
+						  rev - self->length + 1);
+		ps[0] = (int)PyInt_AS_LONG(PyTuple_GET_ITEM(tuple, 5));
+		ps[1] = (int)PyInt_AS_LONG(PyTuple_GET_ITEM(tuple, 6));
+	} else {
+		const char *data = index_deref(self, rev);
+		ps[0] = getbe32(data + 24);
+		ps[1] = getbe32(data + 28);
+	}
+}
+
+typedef uint64_t bitmask;
+
+/*
+ * Given a disjoint set of revs, return all candidates for the
+ * greatest common ancestor. In revset notation, this is the set
+ * "heads(::a and ::b and ...)"
+ */
+static PyObject *find_gca_candidates(indexObject *self, const int *revs,
+				     int revcount)
+{
+	const bitmask allseen = (1ull << revcount) - 1;
+	const bitmask poison = 1ull << revcount;
+	PyObject *gca = PyList_New(0);
+	int i, v, interesting, left;
+	int maxrev = -1;
+	bitmask *seen;
+
+	for (i = 0; i < revcount; i++) {
+		if (revs[i] > maxrev)
+			maxrev = revs[i];
+	}
+
+	seen = calloc(sizeof(*seen), maxrev + 1);
+	if (seen == NULL)
+		return PyErr_NoMemory();
+
+	for (i = 0; i < revcount; i++)
+		seen[revs[i]] = 1ull << i;
+
+	interesting = left = revcount;
+
+	for (v = maxrev; v >= 0 && interesting; v--) {
+		long sv = seen[v];
+		int parents[2];
+
+		if (!sv)
+			continue;
+
+		if (sv < poison) {
+			interesting -= 1;
+			if (sv == allseen) {
+				PyObject *obj = PyInt_FromLong(v);
+				if (obj == NULL)
+					goto bail;
+				if (PyList_Append(gca, obj) == -1) {
+					Py_DECREF(obj);
+					goto bail;
+				}
+				sv |= poison;
+				for (i = 0; i < revcount; i++) {
+					if (revs[i] == v) {
+						if (--left <= 1)
+							goto done;
+						break;
+					}
+				}
+			}
+		}
+		index_get_parents(self, v, parents);
+
+		for (i = 0; i < 2; i++) {
+			int p = parents[i];
+			if (p == -1)
+				continue;
+			const long sp = seen[p];
+			if (sv < poison) {
+				if (sp == 0) {
+					seen[p] = sv;
+					interesting++;
+				}
+				else if (sp != sv)
+					seen[p] |= sv;
+			} else {
+				if (sp && sp < poison)
+					interesting--;
+				seen[p] = sv;
+			}
+		}
+	}
+
+done:
+	free(seen);
+	return gca;
+bail:
+	free(seen);
+	Py_XDECREF(gca);
+	return NULL;
+}
+
+/*
+ * Given a disjoint set of revs, return the subset with the longest
+ * path to the root.
+ */
+static PyObject *find_deepest(indexObject *self, PyObject *revs)
+{
+	const Py_ssize_t revcount = PyList_GET_SIZE(revs);
+	static const Py_ssize_t capacity = 24;
+	int *depth, *interesting = NULL;
+	int i, j, v, ninteresting;
+	PyObject *dict = NULL, *keys;
+	long *seen = NULL;
+	int maxrev = -1;
+	long final;
+
+	if (revcount > capacity) {
+		PyErr_Format(PyExc_OverflowError,
+			     "bitset size (%ld) > capacity (%ld)",
+			     revcount, capacity);
+		return NULL;
+	}
+
+	for (i = 0; i < revcount; i++) {
+		int n = (int)PyInt_AsLong(PyList_GET_ITEM(revs, i));
+		if (n > maxrev)
+			maxrev = n;
+	}
+
+	depth = calloc(sizeof(*depth), maxrev + 1);
+	if (depth == NULL)
+		return PyErr_NoMemory();
+
+	seen = calloc(sizeof(*seen), maxrev + 1);
+	if (seen == NULL) {
+		PyErr_NoMemory();
+		goto bail;
+	}
+
+	interesting = calloc(sizeof(*interesting), 2 << revcount);
+	if (interesting == NULL) {
+		PyErr_NoMemory();
+		goto bail;
+	}
+
+	for (i = 0; i < revcount; i++) {
+		int n = (int)PyInt_AsLong(PyList_GET_ITEM(revs, i));
+		long b = 1l << i;
+		depth[n] = 1;
+		seen[n] = b;
+		interesting[b] = 1;
+	}
+
+	ninteresting = (int)revcount;
+
+	for (v = maxrev; v >= 0 && ninteresting > 1; v--) {
+		int dv = depth[v];
+		int parents[2];
+		long sv;
+
+		if (dv == 0)
+			continue;
+
+		sv = seen[v];
+		index_get_parents(self, v, parents);
+
+		for (i = 0; i < 2; i++) {
+			int p = parents[i];
+			long nsp, sp;
+			int dp;
+
+			if (p == -1)
+				continue;
+
+			dp = depth[p];
+			nsp = sp = seen[p];
+			if (dp <= dv) {
+				depth[p] = dv + 1;
+				if (sp != sv) {
+					interesting[sv] += 1;
+					nsp = seen[p] = sv;
+					if (sp) {
+						interesting[sp] -= 1;
+						if (interesting[sp] == 0)
+							ninteresting -= 1;
+					}
+				}
+			}
+			else if (dv == dp - 1) {
+				nsp = sp | sv;
+				if (nsp == sp)
+					continue;
+				seen[p] = nsp;
+				interesting[nsp] += 1;
+				interesting[sp] -= 1;
+				if (interesting[sp] == 0)
+					ninteresting -= 1;
+			}
+		}
+		interesting[sv] -= 1;
+		if (interesting[sv] == 0)
+			ninteresting -= 1;
+	}
+
+	final = 0;
+	j = ninteresting;
+	for (i = 0; i < (int)(2 << revcount) && j > 0; i++) {
+		if (interesting[i] == 0)
+			continue;
+		final |= i;
+		j -= 1;
+	}
+	if (final == 0)
+		return PyList_New(0);
+
+	dict = PyDict_New();
+	if (dict == NULL)
+		goto bail;
+
+	j = ninteresting;
+	for (i = 0; i < revcount && j > 0; i++) {
+		PyObject *key;
+
+		if ((final & (1 << i)) == 0)
+			continue;
+
+		key = PyList_GET_ITEM(revs, i);
+		Py_INCREF(key);
+		Py_INCREF(Py_None);
+		if (PyDict_SetItem(dict, key, Py_None) == -1) {
+			Py_DECREF(key);
+			Py_DECREF(Py_None);
+			goto bail;
+		}
+		j -= 1;
+	}
+
+	keys = PyDict_Keys(dict);
+
+	free(depth);
+	free(seen);
+	free(interesting);
+	Py_DECREF(dict);
+
+	return keys;
+bail:
+	free(depth);
+	free(seen);
+	free(interesting);
+	Py_XDECREF(dict);
+
+	return NULL;
+}
+
+/*
+ * Given a (possibly overlapping) set of revs, return the greatest
+ * common ancestors: those with the longest path to the root.
+ */
+static PyObject *index_ancestors(indexObject *self, PyObject *args)
+{
+	PyObject *ret = NULL, *gca = NULL;
+	Py_ssize_t argcount, i, len;
+	bitmask repeat = 0;
+	int revcount = 0;
+	int *revs;
+
+	argcount = PySequence_Length(args);
+	revs = malloc(argcount * sizeof(*revs));
+	if (argcount > 0 && revs == NULL)
+		return PyErr_NoMemory();
+	len = index_length(self) - 1;
+
+	for (i = 0; i < argcount; i++) {
+		static const int capacity = 24;
+		PyObject *obj = PySequence_GetItem(args, i);
+		bitmask x;
+		long val;
+
+		if (!PyInt_Check(obj)) {
+			PyErr_SetString(PyExc_TypeError,
+					"arguments must all be ints");
+			goto bail;
+		}
+		val = PyInt_AsLong(obj);
+		if (val == -1) {
+			ret = PyList_New(0);
+			goto done;
+		}
+		if (val < 0 || val >= len) {
+			PyErr_SetString(PyExc_IndexError,
+					"index out of range");
+			goto bail;
+		}
+		/* this cheesy bloom filter lets us avoid some more
+		 * expensive duplicate checks in the common set-is-disjoint
+		 * case */
+		x = 1ull << (val & 0x3f);
+		if (repeat & x) {
+			int k;
+			for (k = 0; k < revcount; k++) {
+				if (val == revs[k])
+					goto duplicate;
+			}
+		}
+		else repeat |= x;
+		if (revcount >= capacity) {
+			PyErr_Format(PyExc_OverflowError,
+				     "bitset size (%d) > capacity (%d)",
+				     revcount, capacity);
+			goto bail;
+		}
+		revs[revcount++] = (int)val;
+	duplicate:;
+	}
+
+	if (revcount == 0) {
+		ret = PyList_New(0);
+		goto done;
+	}
+	if (revcount == 1) {
+		PyObject *obj;
+		ret = PyList_New(1);
+		if (ret == NULL)
+			goto bail;
+		obj = PyInt_FromLong(revs[0]);
+		if (obj == NULL)
+			goto bail;
+		PyList_SET_ITEM(ret, 0, obj);
+		goto done;
+	}
+
+	gca = find_gca_candidates(self, revs, revcount);
+	if (gca == NULL)
+		goto bail;
+
+	if (PyList_GET_SIZE(gca) <= 1) {
+		ret = gca;
+		Py_INCREF(gca);
+	}
+	else if (PyList_GET_SIZE(gca) == 1) {
+		ret = PyList_GET_ITEM(gca, 0);
+		Py_INCREF(ret);
+	}
+	else ret = find_deepest(self, gca);
+
+done:
+	free(revs);
+	Py_XDECREF(gca);
+
+	return ret;
+
+bail:
+	free(revs);
+	Py_XDECREF(gca);
+	Py_XDECREF(ret);
+	return NULL;
+}
+
 /*
  * Invalidate any trie entries introduced by added revs.
  */
 static void nt_invalidate_added(indexObject *self, Py_ssize_t start)
 {
 	Py_ssize_t i, len = PyList_GET_SIZE(self->added);
 
 	for (i = start; i < len; i++) {
 		PyObject *tuple = PyList_GET_ITEM(self->added, i);
 		PyObject *node = PyTuple_GET_ITEM(tuple, 7);
 
 		nt_insert(self, PyString_AS_STRING(node), -1);
 	}
 
 	if (start == 0)
 		Py_CLEAR(self->added);
 }
 
 /*
  * Delete a numeric range of revs, which must be at the end of the
  * range, but exclude the sentinel nullid entry.
  */
 static int index_slice_del(indexObject *self, PyObject *item)
 {
 	Py_ssize_t start, stop, step, slicelength;
 	Py_ssize_t length = index_length(self);
 	int ret = 0;
 
 	if (PySlice_GetIndicesEx((PySliceObject*)item, length,
 				 &start, &stop, &step, &slicelength) < 0)
 		return -1;
 
 	if (slicelength <= 0)
 		return 0;
 
 	if ((step < 0 && start < stop) || (step > 0 && start > stop))
 		stop = start;
 
 	if (step < 0) {
 		stop = start + 1;
 		start = stop + step*(slicelength - 1) - 1;
 		step = -step;
 	}
 
 	if (step != 1) {
 		PyErr_SetString(PyExc_ValueError,
 				"revlog index delete requires step size of 1");
 		return -1;
 	}
 
 	if (stop != length - 1) {
 		PyErr_SetString(PyExc_IndexError,
 				"revlog index deletion indices are invalid");
 		return -1;
 	}
 
 	if (start < self->length - 1) {
 		if (self->nt) {
 			Py_ssize_t i;
 
 			for (i = start + 1; i < self->length - 1; i++) {
 				const char *node = index_node(self, i);
 
 				if (node)
 					nt_insert(self, node, -1);
 			}
 			if (self->added)
 				nt_invalidate_added(self, 0);
 			if (self->ntrev > start)
 				self->ntrev = (int)start;
 		}
 		self->length = start + 1;
 		if (start < self->raw_length) {
 			if (self->cache) {
 				Py_ssize_t i;
 				for (i = start; i < self->raw_length; i++)
 					Py_CLEAR(self->cache[i]);
 			}
 			self->raw_length = start;
 		}
 		goto done;
 	}
 
 	if (self->nt) {
 		nt_invalidate_added(self, start - self->length + 1);
 		if (self->ntrev > start)
 			self->ntrev = (int)start;
 	}
 	if (self->added)
 		ret = PyList_SetSlice(self->added, start - self->length + 1,
 				      PyList_GET_SIZE(self->added), NULL);
 done:
 	Py_CLEAR(self->headrevs);
 	return ret;
 }
 
 /*
  * Supported ops:
  *
  * slice deletion
  * string assignment (extend node->rev mapping)
  * string deletion (shrink node->rev mapping)
  */
 static int index_assign_subscript(indexObject *self, PyObject *item,
 				  PyObject *value)
 {
 	char *node;
 	Py_ssize_t nodelen;
 	long rev;
 
 	if (PySlice_Check(item) && value == NULL)
 		return index_slice_del(self, item);
 
 	if (node_check(item, &node, &nodelen) == -1)
 		return -1;
 
 	if (value == NULL)
 		return self->nt ? nt_insert(self, node, -1) : 0;
 	rev = PyInt_AsLong(value);
 	if (rev > INT_MAX || rev < 0) {
 		if (!PyErr_Occurred())
 			PyErr_SetString(PyExc_ValueError, "rev out of range");
 		return -1;
 	}
 	return nt_insert(self, node, (int)rev);
 }
 
 /*
  * Find all RevlogNG entries in an index that has inline data. Update
  * the optional "offsets" table with those entries.
  */
 static long inline_scan(indexObject *self, const char **offsets)
 {
 	const char *data = PyString_AS_STRING(self->data);
 	const char *end = data + PyString_GET_SIZE(self->data);
 	long incr = v1_hdrsize;
 	Py_ssize_t len = 0;
 
 	while (data + v1_hdrsize <= end) {
 		uint32_t comp_len;
 		const char *old_data;
 		/* 3rd element of header is length of compressed inline data */
 		comp_len = getbe32(data + 8);
 		incr = v1_hdrsize + comp_len;
 		if (incr < v1_hdrsize)
 			break;
 		if (offsets)
 			offsets[len] = data;
 		len++;
 		old_data = data;
 		data += incr;
 		if (data <= old_data)
 			break;
 	}
 
 	if (data != end && data + v1_hdrsize != end) {
 		if (!PyErr_Occurred())
 			PyErr_SetString(PyExc_ValueError, "corrupt index file");
 		return -1;
 	}
 
 	return len;
 }
 
 static int index_init(indexObject *self, PyObject *args)
 {
 	PyObject *data_obj, *inlined_obj;
 	Py_ssize_t size;
 
 	if (!PyArg_ParseTuple(args, "OO", &data_obj, &inlined_obj))
 		return -1;
 	if (!PyString_Check(data_obj)) {
 		PyErr_SetString(PyExc_TypeError, "data is not a string");
 		return -1;
 	}
 	size = PyString_GET_SIZE(data_obj);
 
 	self->inlined = inlined_obj && PyObject_IsTrue(inlined_obj);
 	self->data = data_obj;
 	self->cache = NULL;
 
 	self->added = NULL;
 	self->headrevs = NULL;
 	self->offsets = NULL;
 	self->nt = NULL;
 	self->ntlength = self->ntcapacity = 0;
 	self->ntdepth = self->ntsplits = 0;
 	self->ntlookups = self->ntmisses = 0;
 	self->ntrev = -1;
 	Py_INCREF(self->data);
 
 	if (self->inlined) {
 		long len = inline_scan(self, NULL);
 		if (len == -1)
 			goto bail;
 		self->raw_length = len;
 		self->length = len + 1;
 	} else {
 		if (size % v1_hdrsize) {
 			PyErr_SetString(PyExc_ValueError, "corrupt index file");
 			goto bail;
 		}
 		self->raw_length = size / v1_hdrsize;
 		self->length = self->raw_length + 1;
 	}
 
 	return 0;
 bail:
 	return -1;
 }
 
 static PyObject *index_nodemap(indexObject *self)
 {
 	Py_INCREF(self);
 	return (PyObject *)self;
 }
 
 static void index_dealloc(indexObject *self)
 {
 	_index_clearcaches(self);
 	Py_DECREF(self->data);
 	Py_XDECREF(self->added);
 	PyObject_Del(self);
 }
 
 static PySequenceMethods index_sequence_methods = {
 	(lenfunc)index_length,   /* sq_length */
 	0,                       /* sq_concat */
 	0,                       /* sq_repeat */
 	(ssizeargfunc)index_get, /* sq_item */
 	0,                       /* sq_slice */
 	0,                       /* sq_ass_item */
 	0,                       /* sq_ass_slice */
 	(objobjproc)index_contains, /* sq_contains */
 };
 
 static PyMappingMethods index_mapping_methods = {
 	(lenfunc)index_length,                 /* mp_length */
 	(binaryfunc)index_getitem,             /* mp_subscript */
 	(objobjargproc)index_assign_subscript, /* mp_ass_subscript */
 };
 
 static PyMethodDef index_methods[] = {
+	{"ancestors", (PyCFunction)index_ancestors, METH_VARARGS,
+	 "return the gca set of the given revs"},
 	{"clearcaches", (PyCFunction)index_clearcaches, METH_NOARGS,
 	 "clear the index caches"},
 	{"get", (PyCFunction)index_m_get, METH_VARARGS,
 	 "get an index entry"},
 	{"headrevs", (PyCFunction)index_headrevs, METH_NOARGS,
 	 "get head revisions"},
 	{"insert", (PyCFunction)index_insert, METH_VARARGS,
 	 "insert an index entry"},
 	{"partialmatch", (PyCFunction)index_partialmatch, METH_VARARGS,
 	 "match a potentially ambiguous node ID"},
 	{"stats", (PyCFunction)index_stats, METH_NOARGS,
 	 "stats for the index"},
 	{NULL} /* Sentinel */
 };
 
 static PyGetSetDef index_getset[] = {
 	{"nodemap", (getter)index_nodemap, NULL, "nodemap", NULL},
 	{NULL} /* Sentinel */
 };
 
 static PyTypeObject indexType = {
 	PyObject_HEAD_INIT(NULL)
 	0,                         /* ob_size */
 	"parsers.index",           /* tp_name */
 	sizeof(indexObject),       /* tp_basicsize */
 	0,                         /* tp_itemsize */
 	(destructor)index_dealloc, /* tp_dealloc */
 	0,                         /* tp_print */
 	0,                         /* tp_getattr */
 	0,                         /* tp_setattr */
 	0,                         /* tp_compare */
 	0,                         /* tp_repr */
 	0,                         /* tp_as_number */
 	&index_sequence_methods,   /* tp_as_sequence */
 	&index_mapping_methods,    /* tp_as_mapping */
 	0,                         /* tp_hash */
 	0,                         /* tp_call */
 	0,                         /* tp_str */
 	0,                         /* tp_getattro */
 	0,                         /* tp_setattro */
 	0,                         /* tp_as_buffer */
 	Py_TPFLAGS_DEFAULT,        /* tp_flags */
 	"revlog index",            /* tp_doc */
 	0,                         /* tp_traverse */
 	0,                         /* tp_clear */
 	0,                         /* tp_richcompare */
 	0,                         /* tp_weaklistoffset */
 	0,                         /* tp_iter */
 	0,                         /* tp_iternext */
 	index_methods,             /* tp_methods */
 	0,                         /* tp_members */
 	index_getset,              /* tp_getset */
 	0,                         /* tp_base */
 	0,                         /* tp_dict */
 	0,                         /* tp_descr_get */
 	0,                         /* tp_descr_set */
 	0,                         /* tp_dictoffset */
 	(initproc)index_init,      /* tp_init */
 	0,                         /* tp_alloc */
 };
 
 /*
  * returns a tuple of the form (index, index, cache) with elements as
  * follows:
  *
  * index: an index object that lazily parses RevlogNG records
  * cache: if data is inlined, a tuple (index_file_content, 0), else None
  *
  * added complications are for backwards compatibility
  */
 static PyObject *parse_index2(PyObject *self, PyObject *args)
 {
 	PyObject *tuple = NULL, *cache = NULL;
 	indexObject *idx;
 	int ret;
 
 	idx = PyObject_New(indexObject, &indexType);
 	if (idx == NULL)
 		goto bail;
 
 	ret = index_init(idx, args);
 	if (ret == -1)
 		goto bail;
 
 	if (idx->inlined) {
 		cache = Py_BuildValue("iO", 0, idx->data);
 		if (cache == NULL)
 			goto bail;
 	} else {
 		cache = Py_None;
 		Py_INCREF(cache);
 	}
 
 	tuple = Py_BuildValue("NN", idx, cache);
 	if (!tuple)
 		goto bail;
 	return tuple;
 
 bail:
 	Py_XDECREF(idx);
 	Py_XDECREF(cache);
 	Py_XDECREF(tuple);
 	return NULL;
 }
 
 static char parsers_doc[] = "Efficient content parsing.";
 
 PyObject *encodedir(PyObject *self, PyObject *args);
 PyObject *pathencode(PyObject *self, PyObject *args);
 PyObject *lowerencode(PyObject *self, PyObject *args);
 
 static PyMethodDef methods[] = {
 	{"pack_dirstate", pack_dirstate, METH_VARARGS, "pack a dirstate\n"},
 	{"parse_manifest", parse_manifest, METH_VARARGS, "parse a manifest\n"},
 	{"parse_dirstate", parse_dirstate, METH_VARARGS, "parse a dirstate\n"},
 	{"parse_index2", parse_index2, METH_VARARGS, "parse a revlog index\n"},
 	{"encodedir", encodedir, METH_VARARGS, "encodedir a path\n"},
 	{"pathencode", pathencode, METH_VARARGS, "fncache-encode a path\n"},
 	{"lowerencode", lowerencode, METH_VARARGS, "lower-encode a path\n"},
 	{NULL, NULL}
 };
 
 void dirs_module_init(PyObject *mod);
 
 static void module_init(PyObject *mod)
 {
 	dirs_module_init(mod);
 
 	indexType.tp_new = PyType_GenericNew;
 	if (PyType_Ready(&indexType) < 0)
 		return;
 	Py_INCREF(&indexType);
 
 	PyModule_AddObject(mod, "index", (PyObject *)&indexType);
 
 	nullentry = Py_BuildValue("iiiiiiis#", 0, 0, 0,
 				  -1, -1, -1, -1, nullid, 20);
 	if (nullentry)
 		PyObject_GC_UnTrack(nullentry);
 
 	dirstate_unset = Py_BuildValue("ciii", 'n', 0, -1, -1);
 }
 
 #ifdef IS_PY3K
 static struct PyModuleDef parsers_module = {
 	PyModuleDef_HEAD_INIT,
 	"parsers",
 	parsers_doc,
 	-1,
 	methods
 };
 
 PyMODINIT_FUNC PyInit_parsers(void)
 {
 	PyObject *mod = PyModule_Create(&parsers_module);
 	module_init(mod);
 	return mod;
 }
 #else
 PyMODINIT_FUNC initparsers(void)
 {
 	PyObject *mod = Py_InitModule3("parsers", methods, parsers_doc);
 	module_init(mod);
 }
 #endif

mercurial/revlog.py

@@ -1,1345 +1,1340 b''
 # revlog.py - storage back-end for mercurial
 #
 # Copyright 2005-2007 Matt Mackall <[e-mail]>
 #
 # This software may be used and distributed according to the terms of the
 # GNU General Public License version 2 or any later version.
 
 """Storage back-end for Mercurial.
 
 This provides efficient delta storage with O(1) retrieve and append
 and O(changes) merge between branches.
 """
 
 # import stuff from node for others to import from revlog
 from node import bin, hex, nullid, nullrev
 from i18n import _
 import ancestor, mdiff, parsers, error, util, dagutil
 import struct, zlib, errno
 
 _pack = struct.pack
 _unpack = struct.unpack
 _compress = zlib.compress
 _decompress = zlib.decompress
 _sha = util.sha1
 
 # revlog header flags
 REVLOGV0 = 0
 REVLOGNG = 1
 REVLOGNGINLINEDATA = (1 << 16)
 REVLOGGENERALDELTA = (1 << 17)
 REVLOG_DEFAULT_FLAGS = REVLOGNGINLINEDATA
 REVLOG_DEFAULT_FORMAT = REVLOGNG
 REVLOG_DEFAULT_VERSION = REVLOG_DEFAULT_FORMAT | REVLOG_DEFAULT_FLAGS
 REVLOGNG_FLAGS = REVLOGNGINLINEDATA | REVLOGGENERALDELTA
 
 # revlog index flags
 REVIDX_KNOWN_FLAGS = 0
 
 # max size of revlog with inline data
 _maxinline = 131072
 _chunksize = 1048576
 
 RevlogError = error.RevlogError
 LookupError = error.LookupError
 
 def getoffset(q):
     return int(q >> 16)
 
 def gettype(q):
     return int(q & 0xFFFF)
 
 def offset_type(offset, type):
     return long(long(offset) << 16 | type)
 
 nullhash = _sha(nullid)
 
 def hash(text, p1, p2):
     """generate a hash from the given text and its parent hashes
 
     This hash combines both the current file contents and its history
     in a manner that makes it easy to distinguish nodes with the same
     content in the revision graph.
     """
     # As of now, if one of the parent node is null, p2 is null
     if p2 == nullid:
         # deep copy of a hash is faster than creating one
         s = nullhash.copy()
         s.update(p1)
     else:
         # none of the parent nodes are nullid
         l = [p1, p2]
         l.sort()
         s = _sha(l[0])
         s.update(l[1])
     s.update(text)
     return s.digest()
 
 def decompress(bin):
     """ decompress the given input """
     if not bin:
         return bin
     t = bin[0]
     if t == '\0':
         return bin
     if t == 'x':
         try:
             return _decompress(bin)
         except zlib.error, e:
             raise RevlogError(_("revlog decompress error: %s") % str(e))
     if t == 'u':
         return bin[1:]
     raise RevlogError(_("unknown compression type %r") % t)
 
 # index v0:
 #  4 bytes: offset
 #  4 bytes: compressed length
 #  4 bytes: base rev
 #  4 bytes: link rev
 # 32 bytes: parent 1 nodeid
 # 32 bytes: parent 2 nodeid
 # 32 bytes: nodeid
 indexformatv0 = ">4l20s20s20s"
 v0shaoffset = 56
 
 class revlogoldio(object):
     def __init__(self):
         self.size = struct.calcsize(indexformatv0)
 
     def parseindex(self, data, inline):
         s = self.size
         index = []
         nodemap =  {nullid: nullrev}
         n = off = 0
         l = len(data)
         while off + s <= l:
             cur = data[off:off + s]
             off += s
             e = _unpack(indexformatv0, cur)
             # transform to revlogv1 format
             e2 = (offset_type(e[0], 0), e[1], -1, e[2], e[3],
                   nodemap.get(e[4], nullrev), nodemap.get(e[5], nullrev), e[6])
             index.append(e2)
             nodemap[e[6]] = n
             n += 1
 
         # add the magic null revision at -1
         index.append((0, 0, 0, -1, -1, -1, -1, nullid))
 
         return index, nodemap, None
 
     def packentry(self, entry, node, version, rev):
         if gettype(entry[0]):
             raise RevlogError(_("index entry flags need RevlogNG"))
         e2 = (getoffset(entry[0]), entry[1], entry[3], entry[4],
               node(entry[5]), node(entry[6]), entry[7])
         return _pack(indexformatv0, *e2)
 
 # index ng:
 #  6 bytes: offset
 #  2 bytes: flags
 #  4 bytes: compressed length
 #  4 bytes: uncompressed length
 #  4 bytes: base rev
 #  4 bytes: link rev
 #  4 bytes: parent 1 rev
 #  4 bytes: parent 2 rev
 # 32 bytes: nodeid
 indexformatng = ">Qiiiiii20s12x"
 ngshaoffset = 32
 versionformat = ">I"
 
 class revlogio(object):
     def __init__(self):
         self.size = struct.calcsize(indexformatng)
 
     def parseindex(self, data, inline):
         # call the C implementation to parse the index data
         index, cache = parsers.parse_index2(data, inline)
         return index, getattr(index, 'nodemap', None), cache
 
     def packentry(self, entry, node, version, rev):
         p = _pack(indexformatng, *entry)
         if rev == 0:
             p = _pack(versionformat, version) + p[4:]
         return p
 
 class revlog(object):
     """
     the underlying revision storage object
 
     A revlog consists of two parts, an index and the revision data.
 
     The index is a file with a fixed record size containing
     information on each revision, including its nodeid (hash), the
     nodeids of its parents, the position and offset of its data within
     the data file, and the revision it's based on. Finally, each entry
     contains a linkrev entry that can serve as a pointer to external
     data.
 
     The revision data itself is a linear collection of data chunks.
     Each chunk represents a revision and is usually represented as a
     delta against the previous chunk. To bound lookup time, runs of
     deltas are limited to about 2 times the length of the original
     version data. This makes retrieval of a version proportional to
     its size, or O(1) relative to the number of revisions.
 
     Both pieces of the revlog are written to in an append-only
     fashion, which means we never need to rewrite a file to insert or
     remove data, and can use some simple techniques to avoid the need
     for locking while reading.
     """
     def __init__(self, opener, indexfile):
         """
         create a revlog object
 
         opener is a function that abstracts the file opening operation
         and can be used to implement COW semantics or the like.
         """
         self.indexfile = indexfile
         self.datafile = indexfile[:-2] + ".d"
         self.opener = opener
         self._cache = None
         self._basecache = (0, 0)
         self._chunkcache = (0, '')
         self.index = []
         self._pcache = {}
         self._nodecache = {nullid: nullrev}
         self._nodepos = None
 
         v = REVLOG_DEFAULT_VERSION
         opts = getattr(opener, 'options', None)
         if opts is not None:
             if 'revlogv1' in opts:
                 if 'generaldelta' in opts:
                     v |= REVLOGGENERALDELTA
             else:
                 v = 0
 
         i = ''
         self._initempty = True
         try:
             f = self.opener(self.indexfile)
             i = f.read()
             f.close()
             if len(i) > 0:
                 v = struct.unpack(versionformat, i[:4])[0]
                 self._initempty = False
         except IOError, inst:
             if inst.errno != errno.ENOENT:
                 raise
 
         self.version = v
         self._inline = v & REVLOGNGINLINEDATA
         self._generaldelta = v & REVLOGGENERALDELTA
         flags = v & ~0xFFFF
         fmt = v & 0xFFFF
         if fmt == REVLOGV0 and flags:
             raise RevlogError(_("index %s unknown flags %#04x for format v0")
                               % (self.indexfile, flags >> 16))
         elif fmt == REVLOGNG and flags & ~REVLOGNG_FLAGS:
             raise RevlogError(_("index %s unknown flags %#04x for revlogng")
                               % (self.indexfile, flags >> 16))
         elif fmt > REVLOGNG:
             raise RevlogError(_("index %s unknown format %d")
                               % (self.indexfile, fmt))
 
         self._io = revlogio()
         if self.version == REVLOGV0:
             self._io = revlogoldio()
         try:
             d = self._io.parseindex(i, self._inline)
         except (ValueError, IndexError):
             raise RevlogError(_("index %s is corrupted") % (self.indexfile))
         self.index, nodemap, self._chunkcache = d
         if nodemap is not None:
             self.nodemap = self._nodecache = nodemap
         if not self._chunkcache:
             self._chunkclear()
 
     def tip(self):
         return self.node(len(self.index) - 2)
     def __len__(self):
         return len(self.index) - 1
     def __iter__(self):
         return iter(xrange(len(self)))
     def revs(self, start=0, stop=None):
         """iterate over all rev in this revlog (from start to stop)"""
         step = 1
         if stop is not None:
             if start > stop:
                 step = -1
             stop += step
         else:
             stop = len(self)
         return xrange(start, stop, step)
 
     @util.propertycache
     def nodemap(self):
         self.rev(self.node(0))
         return self._nodecache
 
     def hasnode(self, node):
         try:
             self.rev(node)
             return True
         except KeyError:
             return False
 
     def clearcaches(self):
         try:
             self._nodecache.clearcaches()
         except AttributeError:
             self._nodecache = {nullid: nullrev}
             self._nodepos = None
 
     def rev(self, node):
         try:
             return self._nodecache[node]
         except RevlogError:
             # parsers.c radix tree lookup failed
             raise LookupError(node, self.indexfile, _('no node'))
         except KeyError:
             # pure python cache lookup failed
             n = self._nodecache
             i = self.index
             p = self._nodepos
             if p is None:
                 p = len(i) - 2
             for r in xrange(p, -1, -1):
                 v = i[r][7]
                 n[v] = r
                 if v == node:
                     self._nodepos = r - 1
                     return r
             raise LookupError(node, self.indexfile, _('no node'))
 
     def node(self, rev):
         return self.index[rev][7]
     def linkrev(self, rev):
         return self.index[rev][4]
     def parents(self, node):
         i = self.index
         d = i[self.rev(node)]
         return i[d[5]][7], i[d[6]][7] # map revisions to nodes inline
     def parentrevs(self, rev):
         return self.index[rev][5:7]
     def start(self, rev):
         return int(self.index[rev][0] >> 16)
     def end(self, rev):
         return self.start(rev) + self.length(rev)
     def length(self, rev):
         return self.index[rev][1]
     def chainbase(self, rev):
         index = self.index
         base = index[rev][3]
         while base != rev:
             rev = base
             base = index[rev][3]
         return base
     def flags(self, rev):
         return self.index[rev][0] & 0xFFFF
     def rawsize(self, rev):
         """return the length of the uncompressed text for a given revision"""
         l = self.index[rev][2]
         if l >= 0:
             return l
 
         t = self.revision(self.node(rev))
         return len(t)
     size = rawsize
 
     def ancestors(self, revs, stoprev=0, inclusive=False):
         """Generate the ancestors of 'revs' in reverse topological order.
         Does not generate revs lower than stoprev.
 
         See the documentation for ancestor.lazyancestors for more details."""
 
         return ancestor.lazyancestors(self, revs, stoprev=stoprev,
                                       inclusive=inclusive)
 
     def descendants(self, revs):
         """Generate the descendants of 'revs' in revision order.
 
         Yield a sequence of revision numbers starting with a child of
         some rev in revs, i.e., each revision is *not* considered a
         descendant of itself.  Results are ordered by revision number (a
         topological sort)."""
         first = min(revs)
         if first == nullrev:
             for i in self:
                 yield i
             return
 
         seen = set(revs)
         for i in self.revs(start=first + 1):
             for x in self.parentrevs(i):
                 if x != nullrev and x in seen:
                     seen.add(i)
                     yield i
                     break
 
     def findcommonmissing(self, common=None, heads=None):
         """Return a tuple of the ancestors of common and the ancestors of heads
         that are not ancestors of common. In revset terminology, we return the
         tuple:
 
           ::common, (::heads) - (::common)
 
         The list is sorted by revision number, meaning it is
         topologically sorted.
 
         'heads' and 'common' are both lists of node IDs.  If heads is
         not supplied, uses all of the revlog's heads.  If common is not
         supplied, uses nullid."""
         if common is None:
             common = [nullid]
         if heads is None:
             heads = self.heads()
 
         common = [self.rev(n) for n in common]
         heads = [self.rev(n) for n in heads]
 
         # we want the ancestors, but inclusive
         has = set(self.ancestors(common))
         has.add(nullrev)
         has.update(common)
 
         # take all ancestors from heads that aren't in has
         missing = set()
         visit = util.deque(r for r in heads if r not in has)
         while visit:
             r = visit.popleft()
             if r in missing:
                 continue
             else:
                 missing.add(r)
                 for p in self.parentrevs(r):
                     if p not in has:
                         visit.append(p)
         missing = list(missing)
         missing.sort()
         return has, [self.node(r) for r in missing]
 
     def findmissingrevs(self, common=None, heads=None):
         """Return the revision numbers of the ancestors of heads that
         are not ancestors of common.
 
         More specifically, return a list of revision numbers corresponding to
         nodes N such that every N satisfies the following constraints:
 
           1. N is an ancestor of some node in 'heads'
           2. N is not an ancestor of any node in 'common'
 
         The list is sorted by revision number, meaning it is
         topologically sorted.
 
         'heads' and 'common' are both lists of revision numbers.  If heads is
         not supplied, uses all of the revlog's heads.  If common is not
         supplied, uses nullid."""
         if common is None:
             common = [nullrev]
         if heads is None:
             heads = self.headrevs()
 
         return ancestor.missingancestors(heads, common, self.parentrevs)
 
     def findmissing(self, common=None, heads=None):
         """Return the ancestors of heads that are not ancestors of common.
 
         More specifically, return a list of nodes N such that every N
         satisfies the following constraints:
 
           1. N is an ancestor of some node in 'heads'
           2. N is not an ancestor of any node in 'common'
 
         The list is sorted by revision number, meaning it is
         topologically sorted.
 
         'heads' and 'common' are both lists of node IDs.  If heads is
         not supplied, uses all of the revlog's heads.  If common is not
         supplied, uses nullid."""
         if common is None:
             common = [nullid]
         if heads is None:
             heads = self.heads()
 
         common = [self.rev(n) for n in common]
         heads = [self.rev(n) for n in heads]
 
         return [self.node(r) for r in
                 ancestor.missingancestors(heads, common, self.parentrevs)]
 
     def nodesbetween(self, roots=None, heads=None):
         """Return a topological path from 'roots' to 'heads'.
 
         Return a tuple (nodes, outroots, outheads) where 'nodes' is a
         topologically sorted list of all nodes N that satisfy both of
         these constraints:
 
           1. N is a descendant of some node in 'roots'
           2. N is an ancestor of some node in 'heads'
 
         Every node is considered to be both a descendant and an ancestor
         of itself, so every reachable node in 'roots' and 'heads' will be
         included in 'nodes'.
 
         'outroots' is the list of reachable nodes in 'roots', i.e., the
         subset of 'roots' that is returned in 'nodes'.  Likewise,
         'outheads' is the subset of 'heads' that is also in 'nodes'.
 
         'roots' and 'heads' are both lists of node IDs.  If 'roots' is
         unspecified, uses nullid as the only root.  If 'heads' is
         unspecified, uses list of all of the revlog's heads."""
         nonodes = ([], [], [])
         if roots is not None:
             roots = list(roots)
             if not roots:
                 return nonodes
             lowestrev = min([self.rev(n) for n in roots])
         else:
             roots = [nullid] # Everybody's a descendant of nullid
             lowestrev = nullrev
         if (lowestrev == nullrev) and (heads is None):
             # We want _all_ the nodes!
             return ([self.node(r) for r in self], [nullid], list(self.heads()))
         if heads is None:
             # All nodes are ancestors, so the latest ancestor is the last
             # node.
             highestrev = len(self) - 1
             # Set ancestors to None to signal that every node is an ancestor.
             ancestors = None
             # Set heads to an empty dictionary for later discovery of heads
             heads = {}
         else:
             heads = list(heads)
             if not heads:
                 return nonodes
             ancestors = set()
             # Turn heads into a dictionary so we can remove 'fake' heads.
             # Also, later we will be using it to filter out the heads we can't
             # find from roots.
             heads = dict.fromkeys(heads, False)
             # Start at the top and keep marking parents until we're done.
             nodestotag = set(heads)
             # Remember where the top was so we can use it as a limit later.
             highestrev = max([self.rev(n) for n in nodestotag])
             while nodestotag:
                 # grab a node to tag
                 n = nodestotag.pop()
                 # Never tag nullid
                 if n == nullid:
                     continue
                 # A node's revision number represents its place in a
                 # topologically sorted list of nodes.
                 r = self.rev(n)
                 if r >= lowestrev:
                     if n not in ancestors:
                         # If we are possibly a descendant of one of the roots
                         # and we haven't already been marked as an ancestor
                         ancestors.add(n) # Mark as ancestor
                         # Add non-nullid parents to list of nodes to tag.
                         nodestotag.update([p for p in self.parents(n) if
                                            p != nullid])
                     elif n in heads: # We've seen it before, is it a fake head?
                         # So it is, real heads should not be the ancestors of
                         # any other heads.
                         heads.pop(n)
             if not ancestors:
                 return nonodes
             # Now that we have our set of ancestors, we want to remove any
             # roots that are not ancestors.
 
             # If one of the roots was nullid, everything is included anyway.
             if lowestrev > nullrev:
                 # But, since we weren't, let's recompute the lowest rev to not
                 # include roots that aren't ancestors.
 
                 # Filter out roots that aren't ancestors of heads
                 roots = [n for n in roots if n in ancestors]
                 # Recompute the lowest revision
                 if roots:
                     lowestrev = min([self.rev(n) for n in roots])
                 else:
                     # No more roots?  Return empty list
                     return nonodes
             else:
                 # We are descending from nullid, and don't need to care about
                 # any other roots.
                 lowestrev = nullrev
                 roots = [nullid]
         # Transform our roots list into a set.
         descendants = set(roots)
         # Also, keep the original roots so we can filter out roots that aren't
         # 'real' roots (i.e. are descended from other roots).
         roots = descendants.copy()
         # Our topologically sorted list of output nodes.
         orderedout = []
         # Don't start at nullid since we don't want nullid in our output list,
         # and if nullid shows up in descendants, empty parents will look like
         # they're descendants.
         for r in self.revs(start=max(lowestrev, 0), stop=highestrev + 1):
             n = self.node(r)
             isdescendant = False
             if lowestrev == nullrev:  # Everybody is a descendant of nullid
                 isdescendant = True
             elif n in descendants:
                 # n is already a descendant
                 isdescendant = True
                 # This check only needs to be done here because all the roots
                 # will start being marked is descendants before the loop.
                 if n in roots:
                     # If n was a root, check if it's a 'real' root.
                     p = tuple(self.parents(n))
                     # If any of its parents are descendants, it's not a root.
                     if (p[0] in descendants) or (p[1] in descendants):
                         roots.remove(n)
             else:
                 p = tuple(self.parents(n))
                 # A node is a descendant if either of its parents are
                 # descendants.  (We seeded the dependents list with the roots
                 # up there, remember?)
                 if (p[0] in descendants) or (p[1] in descendants):
                     descendants.add(n)
                     isdescendant = True
             if isdescendant and ((ancestors is None) or (n in ancestors)):
                 # Only include nodes that are both descendants and ancestors.
                 orderedout.append(n)
                 if (ancestors is not None) and (n in heads):
                     # We're trying to figure out which heads are reachable
                     # from roots.
                     # Mark this head as having been reached
                     heads[n] = True
                 elif ancestors is None:
                     # Otherwise, we're trying to discover the heads.
                     # Assume this is a head because if it isn't, the next step
                     # will eventually remove it.
                     heads[n] = True
                     # But, obviously its parents aren't.
                     for p in self.parents(n):
                         heads.pop(p, None)
         heads = [n for n, flag in heads.iteritems() if flag]
         roots = list(roots)
         assert orderedout
         assert roots
         assert heads
         return (orderedout, roots, heads)
 
     def headrevs(self):
         try:
             return self.index.headrevs()
         except AttributeError:
             return self._headrevs()
 
     def _headrevs(self):
         count = len(self)
         if not count:
             return [nullrev]
         # we won't iter over filtered rev so nobody is a head at start
         ishead = [0] * (count + 1)
         index = self.index
         for r in self:
             ishead[r] = 1  # I may be an head
             e = index[r]
             ishead[e[5]] = ishead[e[6]] = 0  # my parent are not
         return [r for r, val in enumerate(ishead) if val]
 
     def heads(self, start=None, stop=None):
         """return the list of all nodes that have no children
 
         if start is specified, only heads that are descendants of
         start will be returned
         if stop is specified, it will consider all the revs from stop
         as if they had no children
         """
         if start is None and stop is None:
             if not len(self):
                 return [nullid]
             return [self.node(r) for r in self.headrevs()]
 
         if start is None:
             start = nullid
         if stop is None:
             stop = []
         stoprevs = set([self.rev(n) for n in stop])
         startrev = self.rev(start)
         reachable = set((startrev,))
         heads = set((startrev,))
 
         parentrevs = self.parentrevs
         for r in self.revs(start=startrev + 1):
             for p in parentrevs(r):
                 if p in reachable:
                     if r not in stoprevs:
                         reachable.add(r)
                     heads.add(r)
                 if p in heads and p not in stoprevs:
                     heads.remove(p)
 
         return [self.node(r) for r in heads]
 
     def children(self, node):
         """find the children of a given node"""
         c = []
         p = self.rev(node)
         for r in self.revs(start=p + 1):
             prevs = [pr for pr in self.parentrevs(r) if pr != nullrev]
             if prevs:
                 for pr in prevs:
                     if pr == p:
                         c.append(self.node(r))
             elif p == nullrev:
                 c.append(self.node(r))
         return c
 
     def descendant(self, start, end):
         if start == nullrev:
             return True
         for i in self.descendants([start]):
             if i == end:
                 return True
             elif i > end:
                 break
         return False
 
     def ancestor(self, a, b):
         """calculate the least common ancestor of nodes a and b"""
 
-        # fast path, check if it is a descendant
         a, b = self.rev(a), self.rev(b)
-        start, end = sorted((a, b))
-        if self.descendant(start, end):
-            return self.node(start)
-
-        def parents(rev):
-            return [p for p in self.parentrevs(rev) if p != nullrev]
-
-        c = ancestor.ancestor(a, b, parents)
-        if c is None:
-            return nullid
-
-        return self.node(c)
+        try:
+            ancs = self.index.ancestors(a, b)
+        except (AttributeError, OverflowError):
+            ancs = ancestor.ancestors(self.parentrevs, a, b)
+        if ancs:
+            # choose a consistent winner when there's a tie
+            return min(map(self.node, ancs))
+        return nullid
 
     def _match(self, id):
         if isinstance(id, int):
             # rev
             return self.node(id)
         if len(id) == 20:
             # possibly a binary node
             # odds of a binary node being all hex in ASCII are 1 in 10**25
             try:
                 node = id
                 self.rev(node) # quick search the index
                 return node
             except LookupError:
                 pass # may be partial hex id
         try:
             # str(rev)
             rev = int(id)
             if str(rev) != id:
                 raise ValueError
             if rev < 0:
                 rev = len(self) + rev
             if rev < 0 or rev >= len(self):
                 raise ValueError
             return self.node(rev)
         except (ValueError, OverflowError):
             pass
         if len(id) == 40:
             try:
                 # a full hex nodeid?
                 node = bin(id)
                 self.rev(node)
                 return node
             except (TypeError, LookupError):
                 pass
 
     def _partialmatch(self, id):
         try:
             return self.index.partialmatch(id)
         except RevlogError:
             # parsers.c radix tree lookup gave multiple matches
             raise LookupError(id, self.indexfile, _("ambiguous identifier"))
         except (AttributeError, ValueError):
             # we are pure python, or key was too short to search radix tree
             pass
 
         if id in self._pcache:
             return self._pcache[id]
 
         if len(id) < 40:
             try:
                 # hex(node)[:...]
                 l = len(id) // 2  # grab an even number of digits
                 prefix = bin(id[:l * 2])
                 nl = [e[7] for e in self.index if e[7].startswith(prefix)]
                 nl = [n for n in nl if hex(n).startswith(id)]
                 if len(nl) > 0:
                     if len(nl) == 1:
                         self._pcache[id] = nl[0]
                         return nl[0]
                     raise LookupError(id, self.indexfile,
                                       _('ambiguous identifier'))
                 return None
             except TypeError:
                 pass
 
     def lookup(self, id):
         """locate a node based on:
             - revision number or str(revision number)
             - nodeid or subset of hex nodeid
         """
         n = self._match(id)
         if n is not None:
             return n
         n = self._partialmatch(id)
         if n:
             return n
 
         raise LookupError(id, self.indexfile, _('no match found'))
 
     def cmp(self, node, text):
         """compare text with a given file revision
 
         returns True if text is different than what is stored.
         """
         p1, p2 = self.parents(node)
         return hash(text, p1, p2) != node
 
     def _addchunk(self, offset, data):
         o, d = self._chunkcache
         # try to add to existing cache
         if o + len(d) == offset and len(d) + len(data) < _chunksize:
             self._chunkcache = o, d + data
         else:
             self._chunkcache = offset, data
 
     def _loadchunk(self, offset, length):
         if self._inline:
             df = self.opener(self.indexfile)
         else:
             df = self.opener(self.datafile)
 
         readahead = max(65536, length)
         df.seek(offset)
         d = df.read(readahead)
         df.close()
         self._addchunk(offset, d)
         if readahead > length:
             return util.buffer(d, 0, length)
         return d
 
     def _getchunk(self, offset, length):
         o, d = self._chunkcache
         l = len(d)
 
         # is it in the cache?
         cachestart = offset - o
         cacheend = cachestart + length
         if cachestart >= 0 and cacheend <= l:
             if cachestart == 0 and cacheend == l:
                 return d # avoid a copy
             return util.buffer(d, cachestart, cacheend - cachestart)
 
         return self._loadchunk(offset, length)
 
     def _chunkraw(self, startrev, endrev):
         start = self.start(startrev)
         length = self.end(endrev) - start
         if self._inline:
             start += (startrev + 1) * self._io.size
         return self._getchunk(start, length)
 
     def _chunk(self, rev):
         return decompress(self._chunkraw(rev, rev))
 
     def _chunkbase(self, rev):
         return self._chunk(rev)
 
     def _chunkclear(self):
         self._chunkcache = (0, '')
 
     def deltaparent(self, rev):
         """return deltaparent of the given revision"""
         base = self.index[rev][3]
         if base == rev:
             return nullrev
         elif self._generaldelta:
             return base
         else:
             return rev - 1
 
     def revdiff(self, rev1, rev2):
         """return or calculate a delta between two revisions"""
         if rev1 != nullrev and self.deltaparent(rev2) == rev1:
             return str(self._chunk(rev2))
 
         return mdiff.textdiff(self.revision(rev1),
                               self.revision(rev2))
 
     def revision(self, nodeorrev):
         """return an uncompressed revision of a given node or revision
         number.
         """
         if isinstance(nodeorrev, int):
             rev = nodeorrev
             node = self.node(rev)
         else:
             node = nodeorrev
             rev = None
 
         cachedrev = None
         if node == nullid:
             return ""
         if self._cache:
             if self._cache[0] == node:
                 return self._cache[2]
             cachedrev = self._cache[1]
 
         # look up what we need to read
         text = None
         if rev is None:
             rev = self.rev(node)
 
         # check rev flags
         if self.flags(rev) & ~REVIDX_KNOWN_FLAGS:
             raise RevlogError(_('incompatible revision flag %x') %
                               (self.flags(rev) & ~REVIDX_KNOWN_FLAGS))
 
         # build delta chain
         chain = []
         index = self.index # for performance
         generaldelta = self._generaldelta
         iterrev = rev
         e = index[iterrev]
         while iterrev != e[3] and iterrev != cachedrev:
             chain.append(iterrev)
             if generaldelta:
                 iterrev = e[3]
             else:
                 iterrev -= 1
             e = index[iterrev]
         chain.reverse()
         base = iterrev
 
         if iterrev == cachedrev:
             # cache hit
             text = self._cache[2]
 
         # drop cache to save memory
         self._cache = None
 
         self._chunkraw(base, rev)
         if text is None:
             text = str(self._chunkbase(base))
 
         bins = [self._chunk(r) for r in chain]
         text = mdiff.patches(text, bins)
 
         text = self._checkhash(text, node, rev)
 
         self._cache = (node, rev, text)
         return text
 
     def _checkhash(self, text, node, rev):
         p1, p2 = self.parents(node)
         if node != hash(text, p1, p2):
             raise RevlogError(_("integrity check failed on %s:%d")
                               % (self.indexfile, rev))
         return text
 
     def checkinlinesize(self, tr, fp=None):
         if not self._inline or (self.start(-2) + self.length(-2)) < _maxinline:
             return
 
         trinfo = tr.find(self.indexfile)
         if trinfo is None:
             raise RevlogError(_("%s not found in the transaction")
                               % self.indexfile)
 
         trindex = trinfo[2]
         dataoff = self.start(trindex)
 
         tr.add(self.datafile, dataoff)
 
         if fp:
             fp.flush()
             fp.close()
 
         df = self.opener(self.datafile, 'w')
         try:
             for r in self:
                 df.write(self._chunkraw(r, r))
         finally:
             df.close()
 
         fp = self.opener(self.indexfile, 'w', atomictemp=True)
         self.version &= ~(REVLOGNGINLINEDATA)
         self._inline = False
         for i in self:
             e = self._io.packentry(self.index[i], self.node, self.version, i)
             fp.write(e)
 
         # if we don't call close, the temp file will never replace the
         # real index
         fp.close()
 
         tr.replace(self.indexfile, trindex * self._io.size)
         self._chunkclear()
 
     def addrevision(self, text, transaction, link, p1, p2, cachedelta=None):
         """add a revision to the log
 
         text - the revision data to add
         transaction - the transaction object used for rollback
         link - the linkrev data to add
         p1, p2 - the parent nodeids of the revision
         cachedelta - an optional precomputed delta
         """
         node = hash(text, p1, p2)
         if node in self.nodemap:
             return node
 
         dfh = None
         if not self._inline:
             dfh = self.opener(self.datafile, "a")
         ifh = self.opener(self.indexfile, "a+")
         try:
             return self._addrevision(node, text, transaction, link, p1, p2,
                                      cachedelta, ifh, dfh)
         finally:
             if dfh:
                 dfh.close()
             ifh.close()
 
     def compress(self, text):
         """ generate a possibly-compressed representation of text """
         if not text:
             return ("", text)
         l = len(text)
         bin = None
         if l < 44:
             pass
         elif l > 1000000:
             # zlib makes an internal copy, thus doubling memory usage for
             # large files, so lets do this in pieces
             z = zlib.compressobj()
             p = []
             pos = 0
             while pos < l:
                 pos2 = pos + 2**20
                 p.append(z.compress(text[pos:pos2]))
                 pos = pos2
             p.append(z.flush())
             if sum(map(len, p)) < l:
                 bin = "".join(p)
         else:
             bin = _compress(text)
         if bin is None or len(bin) > l:
             if text[0] == '\0':
                 return ("", text)
             return ('u', text)
         return ("", bin)
 
     def _addrevision(self, node, text, transaction, link, p1, p2,
                      cachedelta, ifh, dfh):
         """internal function to add revisions to the log
 
         see addrevision for argument descriptions.
         invariants:
         - text is optional (can be None); if not set, cachedelta must be set.
           if both are set, they must correspond to each other.
         """
         btext = [text]
         def buildtext():
             if btext[0] is not None:
                 return btext[0]
             # flush any pending writes here so we can read it in revision
             if dfh:
                 dfh.flush()
             ifh.flush()
             basetext = self.revision(self.node(cachedelta[0]))
             btext[0] = mdiff.patch(basetext, cachedelta[1])
             chk = hash(btext[0], p1, p2)
             if chk != node:
                 raise RevlogError(_("consistency error in delta"))
             return btext[0]
 
         def builddelta(rev):
             # can we use the cached delta?
             if cachedelta and cachedelta[0] == rev:
                 delta = cachedelta[1]
             else:
                 t = buildtext()
                 ptext = self.revision(self.node(rev))
                 delta = mdiff.textdiff(ptext, t)
             data = self.compress(delta)
             l = len(data[1]) + len(data[0])
             if basecache[0] == rev:
                 chainbase = basecache[1]
             else:
                 chainbase = self.chainbase(rev)
             dist = l + offset - self.start(chainbase)
             if self._generaldelta:
                 base = rev
             else:
                 base = chainbase
             return dist, l, data, base, chainbase
 
         curr = len(self)
         prev = curr - 1
         base = chainbase = curr
         offset = self.end(prev)
         flags = 0
         d = None
         basecache = self._basecache
         p1r, p2r = self.rev(p1), self.rev(p2)
 
         # should we try to build a delta?
         if prev != nullrev:
             if self._generaldelta:
                 if p1r >= basecache[1]:
                     d = builddelta(p1r)
                 elif p2r >= basecache[1]:
                     d = builddelta(p2r)
                 else:
                     d = builddelta(prev)
             else:
                 d = builddelta(prev)
             dist, l, data, base, chainbase = d
 
         # full versions are inserted when the needed deltas
         # become comparable to the uncompressed text
         if text is None:
             textlen = mdiff.patchedsize(self.rawsize(cachedelta[0]),
                                         cachedelta[1])
         else:
             textlen = len(text)
         if d is None or dist > textlen * 2:
             text = buildtext()
             data = self.compress(text)
             l = len(data[1]) + len(data[0])
             base = chainbase = curr
 
         e = (offset_type(offset, flags), l, textlen,
              base, link, p1r, p2r, node)
         self.index.insert(-1, e)
         self.nodemap[node] = curr
 
         entry = self._io.packentry(e, self.node, self.version, curr)
         if not self._inline:
             transaction.add(self.datafile, offset)
             transaction.add(self.indexfile, curr * len(entry))
             if data[0]:
                 dfh.write(data[0])
             dfh.write(data[1])
             dfh.flush()
             ifh.write(entry)
         else:
             offset += curr * self._io.size
             transaction.add(self.indexfile, offset, curr)
             ifh.write(entry)
             ifh.write(data[0])
             ifh.write(data[1])
             self.checkinlinesize(transaction, ifh)
 
         if type(text) == str: # only accept immutable objects
             self._cache = (node, curr, text)
         self._basecache = (curr, chainbase)
         return node
 
     def group(self, nodelist, bundler, reorder=None):
         """Calculate a delta group, yielding a sequence of changegroup chunks
         (strings).
 
         Given a list of changeset revs, return a set of deltas and
         metadata corresponding to nodes. The first delta is
         first parent(nodelist[0]) -> nodelist[0], the receiver is
         guaranteed to have this parent as it has all history before
         these changesets. In the case firstparent is nullrev the
         changegroup starts with a full revision.
         """
 
         # if we don't have any revisions touched by these changesets, bail
         if len(nodelist) == 0:
             yield bundler.close()
             return
 
         # for generaldelta revlogs, we linearize the revs; this will both be
         # much quicker and generate a much smaller bundle
         if (self._generaldelta and reorder is not False) or reorder:
             dag = dagutil.revlogdag(self)
             revs = set(self.rev(n) for n in nodelist)
             revs = dag.linearize(revs)
         else:
             revs = sorted([self.rev(n) for n in nodelist])
 
         # add the parent of the first rev
         p = self.parentrevs(revs[0])[0]
         revs.insert(0, p)
 
         # build deltas
         for r in xrange(len(revs) - 1):
             prev, curr = revs[r], revs[r + 1]
             for c in bundler.revchunk(self, curr, prev):
                 yield c
 
         yield bundler.close()
 
     def addgroup(self, bundle, linkmapper, transaction):
         """
         add a delta group
 
         given a set of deltas, add them to the revision log. the
         first delta is against its parent, which should be in our
         log, the rest are against the previous delta.
         """
 
         # track the base of the current delta log
         content = []
         node = None
 
         r = len(self)
         end = 0
         if r:
             end = self.end(r - 1)
         ifh = self.opener(self.indexfile, "a+")
         isize = r * self._io.size
         if self._inline:
             transaction.add(self.indexfile, end + isize, r)
             dfh = None
         else:
             transaction.add(self.indexfile, isize, r)
             transaction.add(self.datafile, end)
             dfh = self.opener(self.datafile, "a")
 
         try:
             # loop through our set of deltas
             chain = None
             while True:
                 chunkdata = bundle.deltachunk(chain)
                 if not chunkdata:
                     break
                 node = chunkdata['node']
                 p1 = chunkdata['p1']
                 p2 = chunkdata['p2']
                 cs = chunkdata['cs']
                 deltabase = chunkdata['deltabase']
                 delta = chunkdata['delta']
 
                 content.append(node)
 
                 link = linkmapper(cs)
                 if node in self.nodemap:
                     # this can happen if two branches make the same change
                     chain = node
                     continue
 
                 for p in (p1, p2):
                     if p not in self.nodemap:
                         raise LookupError(p, self.indexfile,
                                           _('unknown parent'))
 
                 if deltabase not in self.nodemap:
                     raise LookupError(deltabase, self.indexfile,
                                       _('unknown delta base'))
 
                 baserev = self.rev(deltabase)
                 chain = self._addrevision(node, None, transaction, link,
                                           p1, p2, (baserev, delta), ifh, dfh)
                 if not dfh and not self._inline:
                     # addrevision switched from inline to conventional
                     # reopen the index
                     ifh.close()
                     dfh = self.opener(self.datafile, "a")
                     ifh = self.opener(self.indexfile, "a")
         finally:
             if dfh:
                 dfh.close()
             ifh.close()
 
         return content
 
     def strip(self, minlink, transaction):
         """truncate the revlog on the first revision with a linkrev >= minlink
 
         This function is called when we're stripping revision minlink and
         its descendants from the repository.
 
         We have to remove all revisions with linkrev >= minlink, because
         the equivalent changelog revisions will be renumbered after the
         strip.
 
         So we truncate the revlog on the first of these revisions, and
         trust that the caller has saved the revisions that shouldn't be
         removed and that it'll re-add them after this truncation.
         """
         if len(self) == 0:
             return
 
         for rev in self:
             if self.index[rev][4] >= minlink:
                 break
         else:
             return
 
         # first truncate the files on disk
         end = self.start(rev)
         if not self._inline:
             transaction.add(self.datafile, end)
             end = rev * self._io.size
         else:
             end += rev * self._io.size
 
         transaction.add(self.indexfile, end)
 
         # then reset internal state in memory to forget those revisions
         self._cache = None
         self._chunkclear()
         for x in xrange(rev, len(self)):
             del self.nodemap[self.node(x)]
 
         del self.index[rev:-1]
 
     def checksize(self):
         expected = 0
         if len(self):
             expected = max(0, self.end(len(self) - 1))
 
         try:
             f = self.opener(self.datafile)
             f.seek(0, 2)
             actual = f.tell()
             f.close()
             dd = actual - expected
         except IOError, inst:
             if inst.errno != errno.ENOENT:
                 raise
             dd = 0
 
         try:
             f = self.opener(self.indexfile)
             f.seek(0, 2)
             actual = f.tell()
             f.close()
             s = self._io.size
             i = max(0, actual // s)
             di = actual - (i * s)
             if self._inline:
                 databytes = 0
                 for r in self:
                     databytes += max(0, self.length(r))
                 dd = 0
                 di = actual - len(self) * s - databytes
         except IOError, inst:
             if inst.errno != errno.ENOENT:
                 raise
             di = 0
 
         return (dd, di)
 
     def files(self):
         res = [self.indexfile]
         if not self._inline:
             res.append(self.datafile)
         return res