dagop: fix subsetparentswalker to set p1/p2 chains at merge revision

The previous implementation was wrong because the '1'/'2' key would be
appended at a fork revision. Since we traverse the graph from heads, a merge
revision is actually a branching point, where the sort key must be generated.

mercurial/dagop.py

@@ -1,1108 +1,1113 b''
 # dagop.py - graph ancestry and topology algorithm for revset
 #
 # Copyright 2010 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 __future__ import absolute_import
 
 import heapq
 
 from .node import nullrev
 from .thirdparty import attr
 from . import (
     error,
     mdiff,
     node,
     patch,
     pycompat,
     smartset,
 )
 
 baseset = smartset.baseset
 generatorset = smartset.generatorset
 
 # possible maximum depth between null and wdir()
 maxlogdepth = 0x80000000
 
 
 def _walkrevtree(pfunc, revs, startdepth, stopdepth, reverse):
     """Walk DAG using 'pfunc' from the given 'revs' nodes
 
     'pfunc(rev)' should return the parent/child revisions of the given 'rev'
     if 'reverse' is True/False respectively.
 
     Scan ends at the stopdepth (exlusive) if specified. Revisions found
     earlier than the startdepth are omitted.
     """
     if startdepth is None:
         startdepth = 0
     if stopdepth is None:
         stopdepth = maxlogdepth
     if stopdepth == 0:
         return
     if stopdepth < 0:
         raise error.ProgrammingError(b'negative stopdepth')
     if reverse:
         heapsign = -1  # max heap
     else:
         heapsign = +1  # min heap
 
     # load input revs lazily to heap so earlier revisions can be yielded
     # without fully computing the input revs
     revs.sort(reverse)
     irevs = iter(revs)
     pendingheap = []  # [(heapsign * rev, depth), ...] (i.e. lower depth first)
 
     inputrev = next(irevs, None)
     if inputrev is not None:
         heapq.heappush(pendingheap, (heapsign * inputrev, 0))
 
     lastrev = None
     while pendingheap:
         currev, curdepth = heapq.heappop(pendingheap)
         currev = heapsign * currev
         if currev == inputrev:
             inputrev = next(irevs, None)
             if inputrev is not None:
                 heapq.heappush(pendingheap, (heapsign * inputrev, 0))
         # rescan parents until curdepth >= startdepth because queued entries
         # of the same revision are iterated from the lowest depth
         foundnew = currev != lastrev
         if foundnew and curdepth >= startdepth:
             lastrev = currev
             yield currev
         pdepth = curdepth + 1
         if foundnew and pdepth < stopdepth:
             for prev in pfunc(currev):
                 if prev != node.nullrev:
                     heapq.heappush(pendingheap, (heapsign * prev, pdepth))
 
 
 def filectxancestors(fctxs, followfirst=False):
     """Like filectx.ancestors(), but can walk from multiple files/revisions,
     and includes the given fctxs themselves
 
     Yields (rev, {fctx, ...}) pairs in descending order.
     """
     visit = {}
     visitheap = []
 
     def addvisit(fctx):
         rev = fctx.rev()
         if rev not in visit:
             visit[rev] = set()
             heapq.heappush(visitheap, -rev)  # max heap
         visit[rev].add(fctx)
 
     if followfirst:
         cut = 1
     else:
         cut = None
 
     for c in fctxs:
         addvisit(c)
     while visit:
         currev = -(heapq.heappop(visitheap))
         curfctxs = visit.pop(currev)
         yield currev, curfctxs
         for c in curfctxs:
             for parent in c.parents()[:cut]:
                 addvisit(parent)
     assert not visitheap
 
 
 def filerevancestors(fctxs, followfirst=False):
     """Like filectx.ancestors(), but can walk from multiple files/revisions,
     and includes the given fctxs themselves
 
     Returns a smartset.
     """
     gen = (rev for rev, _cs in filectxancestors(fctxs, followfirst))
     return generatorset(gen, iterasc=False)
 
 
 def _genrevancestors(repo, revs, followfirst, startdepth, stopdepth, cutfunc):
     if followfirst:
         cut = 1
     else:
         cut = None
     cl = repo.changelog
 
     def plainpfunc(rev):
         try:
             return cl.parentrevs(rev)[:cut]
         except error.WdirUnsupported:
             return (pctx.rev() for pctx in repo[rev].parents()[:cut])
 
     if cutfunc is None:
         pfunc = plainpfunc
     else:
         pfunc = lambda rev: [r for r in plainpfunc(rev) if not cutfunc(r)]
         revs = revs.filter(lambda rev: not cutfunc(rev))
     return _walkrevtree(pfunc, revs, startdepth, stopdepth, reverse=True)
 
 
 def revancestors(
     repo, revs, followfirst=False, startdepth=None, stopdepth=None, cutfunc=None
 ):
     r"""Like revlog.ancestors(), but supports additional options, includes
     the given revs themselves, and returns a smartset
 
     Scan ends at the stopdepth (exlusive) if specified. Revisions found
     earlier than the startdepth are omitted.
 
     If cutfunc is provided, it will be used to cut the traversal of the DAG.
     When cutfunc(X) returns True, the DAG traversal stops - revision X and
     X's ancestors in the traversal path will be skipped. This could be an
     optimization sometimes.
 
     Note: if Y is an ancestor of X, cutfunc(X) returning True does not
     necessarily mean Y will also be cut. Usually cutfunc(Y) also wants to
     return True in this case. For example,
 
         D     # revancestors(repo, D, cutfunc=lambda rev: rev == B)
         |\    # will include "A", because the path D -> C -> A was not cut.
         B C   # If "B" gets cut, "A" might want to be cut too.
         |/
         A
     """
     gen = _genrevancestors(
         repo, revs, followfirst, startdepth, stopdepth, cutfunc
     )
     return generatorset(gen, iterasc=False)
 
 
 def _genrevdescendants(repo, revs, followfirst):
     if followfirst:
         cut = 1
     else:
         cut = None
 
     cl = repo.changelog
     first = revs.min()
     nullrev = node.nullrev
     if first == nullrev:
         # Are there nodes with a null first parent and a non-null
         # second one? Maybe. Do we care? Probably not.
         yield first
         for i in cl:
             yield i
     else:
         seen = set(revs)
         for i in cl.revs(first):
             if i in seen:
                 yield i
                 continue
             for x in cl.parentrevs(i)[:cut]:
                 if x != nullrev and x in seen:
                     seen.add(i)
                     yield i
                     break
 
 
 def _builddescendantsmap(repo, startrev, followfirst):
     """Build map of 'rev -> child revs', offset from startrev"""
     cl = repo.changelog
     nullrev = node.nullrev
     descmap = [[] for _rev in pycompat.xrange(startrev, len(cl))]
     for currev in cl.revs(startrev + 1):
         p1rev, p2rev = cl.parentrevs(currev)
         if p1rev >= startrev:
             descmap[p1rev - startrev].append(currev)
         if not followfirst and p2rev != nullrev and p2rev >= startrev:
             descmap[p2rev - startrev].append(currev)
     return descmap
 
 
 def _genrevdescendantsofdepth(repo, revs, followfirst, startdepth, stopdepth):
     startrev = revs.min()
     descmap = _builddescendantsmap(repo, startrev, followfirst)
 
     def pfunc(rev):
         return descmap[rev - startrev]
 
     return _walkrevtree(pfunc, revs, startdepth, stopdepth, reverse=False)
 
 
 def revdescendants(repo, revs, followfirst, startdepth=None, stopdepth=None):
     """Like revlog.descendants() but supports additional options, includes
     the given revs themselves, and returns a smartset
 
     Scan ends at the stopdepth (exlusive) if specified. Revisions found
     earlier than the startdepth are omitted.
     """
     if startdepth is None and (stopdepth is None or stopdepth >= maxlogdepth):
         gen = _genrevdescendants(repo, revs, followfirst)
     else:
         gen = _genrevdescendantsofdepth(
             repo, revs, followfirst, startdepth, stopdepth
         )
     return generatorset(gen, iterasc=True)
 
 
 def descendantrevs(revs, revsfn, parentrevsfn):
     """Generate revision number descendants in revision order.
 
     Yields revision numbers starting with a child of some rev in
     ``revs``. Results are ordered by revision number and are
     therefore topological. Each revision is not considered a descendant
     of itself.
 
     ``revsfn`` is a callable that with no argument iterates over all
     revision numbers and with a ``start`` argument iterates over revision
     numbers beginning with that value.
 
     ``parentrevsfn`` is a callable that receives a revision number and
     returns an iterable of parent revision numbers, whose values may include
     nullrev.
     """
     first = min(revs)
 
     if first == nullrev:
         for rev in revsfn():
             yield rev
         return
 
     seen = set(revs)
     for rev in revsfn(start=first + 1):
         for prev in parentrevsfn(rev):
             if prev != nullrev and prev in seen:
                 seen.add(rev)
                 yield rev
                 break
 
 
 class subsetparentswalker(object):
     r"""Scan adjacent ancestors in the graph given by the subset
 
     This computes parent-child relations in the sub graph filtered by
     a revset. Primary use case is to draw a revisions graph.
 
     In the following example, we consider that the node 'f' has edges to all
     ancestor nodes, but redundant paths are eliminated. The edge 'f'->'b'
     is eliminated because there is a path 'f'->'c'->'b' for example.
 
           - d - e -
          /         \
         a - b - c - f
 
     If the node 'c' is filtered out, the edge 'f'->'b' is activated.
 
           - d - e -
          /         \
         a - b -(c)- f
 
     Likewise, if 'd' and 'e' are filtered out, this edge is fully eliminated
     since there is a path 'f'->'c'->'b'->'a' for 'f'->'a'.
 
            (d) (e)
 
         a - b - c - f
 
     Implementation-wise, 'f' is passed down to 'a' as unresolved through the
     'f'->'e'->'d'->'a' path, whereas we do also remember that 'f' has already
     been resolved while walking down the 'f'->'c'->'b'->'a' path. When
     processing the node 'a', the unresolved 'f'->'a' path is eliminated as
     the 'f' end is marked as resolved.
 
     Ancestors are searched from the tipmost revision in the subset so the
     results can be cached. You should specify startrev to narrow the search
     space to ':startrev'.
     """
 
     def __init__(self, repo, subset, startrev=None):
         if startrev is not None:
             subset = repo.revs(b'%d:null', startrev) & subset
 
         # equivalent to 'subset = subset.sorted(reverse=True)', but there's
         # no such function.
         fastdesc = subset.fastdesc
         if fastdesc:
             desciter = fastdesc()
         else:
             if not subset.isdescending() and not subset.istopo():
                 subset = smartset.baseset(subset)
                 subset.sort(reverse=True)
             desciter = iter(subset)
 
         self._repo = repo
         self._changelog = repo.changelog
         self._subset = subset
 
         # scanning state (see _scanparents):
         self._tovisit = []
         self._pendingcnt = {}
         self._pointers = {}
         self._parents = {}
         self._inputhead = nullrev  # reassigned by self._advanceinput()
         self._inputtail = desciter
         self._bottomrev = nullrev
         self._advanceinput()
 
     def parentsset(self, rev):
         """Look up parents of the given revision in the subset, and returns
         as a smartset"""
         return smartset.baseset(self.parents(rev))
 
     def parents(self, rev):
         """Look up parents of the given revision in the subset
 
         The returned revisions are sorted by parent index (p1/p2).
         """
         self._scanparents(rev)
         return [r for _c, r in sorted(self._parents.get(rev, []))]
 
     def _parentrevs(self, rev):
         try:
             revs = self._changelog.parentrevs(rev)
             if revs[-1] == nullrev:
                 return revs[:-1]
             return revs
         except error.WdirUnsupported:
             return tuple(pctx.rev() for pctx in self._repo[None].parents())
 
     def _advanceinput(self):
         """Advance the input iterator and set the next revision to _inputhead"""
         if self._inputhead < nullrev:
             return
         try:
             self._inputhead = next(self._inputtail)
         except StopIteration:
             self._bottomrev = self._inputhead
             self._inputhead = nullrev - 1
 
     def _scanparents(self, stoprev):
         """Scan ancestors until the parents of the specified stoprev are
         resolved"""
 
         # 'tovisit' is the queue of the input revisions and their ancestors.
         # It will be populated incrementally to minimize the initial cost
         # of computing the given subset.
         #
         # For to-visit revisions, we keep track of
         # - the number of the unresolved paths: pendingcnt[rev],
         # - dict of the unresolved descendants and chains: pointers[rev][0],
         # - set of the already resolved descendants: pointers[rev][1].
         #
         # When a revision is visited, 'pointers[rev]' should be popped and
         # propagated to its parents accordingly.
         #
         # Once all pending paths have been resolved, 'pendingcnt[rev]' becomes
         # 0 and 'parents[rev]' contains the unsorted list of parent revisions
-        # and p1/p2 chains (excluding linear paths.)
+        # and p1/p2 chains (excluding linear paths.) The p1/p2 chains will be
+        # used as a sort key preferring p1. 'len(chain)' should be the number
+        # of merges between two revisions.
 
         subset = self._subset
         tovisit = self._tovisit  # heap queue of [-rev]
         pendingcnt = self._pendingcnt  # {rev: count} for visited revisions
         pointers = self._pointers  # {rev: [{unresolved_rev: chain}, resolved]}
         parents = self._parents  # {rev: [(chain, rev)]}
 
         while tovisit or self._inputhead >= nullrev:
             if pendingcnt.get(stoprev) == 0:
                 return
 
             # feed greater revisions from input set to queue
             if not tovisit:
                 heapq.heappush(tovisit, -self._inputhead)
                 self._advanceinput()
             while self._inputhead >= -tovisit[0]:
                 heapq.heappush(tovisit, -self._inputhead)
                 self._advanceinput()
 
             rev = -heapq.heappop(tovisit)
             if rev < self._bottomrev:
                 return
             if rev in pendingcnt and rev not in pointers:
                 continue  # already visited
 
             curactive = rev in subset
             pendingcnt.setdefault(rev, 0)  # mark as visited
             if curactive:
                 assert rev not in parents
                 parents[rev] = []
             unresolved, resolved = pointers.pop(rev, ({}, set()))
 
             if curactive:
                 # reached to active rev, resolve pending descendants' parents
                 for r, c in unresolved.items():
                     pendingcnt[r] -= 1
                     assert pendingcnt[r] >= 0
                     if r in resolved:
                         continue  # eliminate redundant path
                     parents[r].append((c, rev))
                     # mark the descendant 'r' as resolved through this path if
                     # there are still pending pointers. the 'resolved' set may
                     # be concatenated later at a fork revision.
                     if pendingcnt[r] > 0:
                         resolved.add(r)
                 unresolved.clear()
                 # occasionally clean resolved markers. otherwise the set
                 # would grow indefinitely.
                 resolved = {r for r in resolved if pendingcnt[r] > 0}
 
             parentrevs = self._parentrevs(rev)
             bothparentsactive = all(p in subset for p in parentrevs)
 
             # set up or propagate tracking pointers if
             # - one of the parents is not active,
             # - or descendants' parents are unresolved.
             if not bothparentsactive or unresolved or resolved:
                 if len(parentrevs) <= 1:
                     # can avoid copying the tracking pointer
                     parentpointers = [(unresolved, resolved)]
                 else:
                     parentpointers = [
                         (unresolved, resolved),
                         (unresolved.copy(), resolved.copy()),
                     ]
                     # 'rev' is a merge revision. increment the pending count
-                    # as the 'unresolved' dict will be duplicated.
+                    # as the 'unresolved' dict will be duplicated, and append
+                    # p1/p2 code to the existing chains.
                     for r in unresolved:
                         pendingcnt[r] += 1
+                        parentpointers[0][0][r] += b'1'
+                        parentpointers[1][0][r] += b'2'
                 for i, p in enumerate(parentrevs):
                     assert p < rev
                     heapq.heappush(tovisit, -p)
                     if p in pointers:
                         # 'p' is a fork revision. concatenate tracking pointers
                         # and decrement the pending count accordingly.
                         knownunresolved, knownresolved = pointers[p]
                         unresolved, resolved = parentpointers[i]
                         for r, c in unresolved.items():
-                            c += [b'1', b'2'][i]
                             if r in knownunresolved:
                                 # unresolved at both paths
                                 pendingcnt[r] -= 1
                                 assert pendingcnt[r] > 0
                                 # take shorter chain
                                 knownunresolved[r] = min(c, knownunresolved[r])
                             else:
                                 knownunresolved[r] = c
                         # simply propagate the 'resolved' set as deduplicating
                         # 'unresolved' here would be slightly complicated.
                         knownresolved.update(resolved)
                     else:
                         pointers[p] = parentpointers[i]
 
             # then, populate the active parents directly and add the current
             # 'rev' to the tracking pointers of the inactive parents.
             # 'pointers[p]' may be optimized out if both parents are active.
+            chaincodes = [b''] if len(parentrevs) <= 1 else [b'1', b'2']
             if curactive and bothparentsactive:
                 for i, p in enumerate(parentrevs):
-                    c = [b'1', b'2'][i]
+                    c = chaincodes[i]
                     parents[rev].append((c, p))
                     # no need to mark 'rev' as resolved since the 'rev' should
                     # be fully resolved (i.e. pendingcnt[rev] == 0)
                 assert pendingcnt[rev] == 0
             elif curactive:
                 for i, p in enumerate(parentrevs):
                     unresolved, resolved = pointers[p]
                     assert rev not in unresolved
-                    c = [b'1', b'2'][i]
+                    c = chaincodes[i]
                     if p in subset:
                         parents[rev].append((c, p))
                         # mark 'rev' as resolved through this path
                         resolved.add(rev)
                     else:
                         pendingcnt[rev] += 1
                         unresolved[rev] = c
                 assert 0 < pendingcnt[rev] <= 2
 
 
 def _reachablerootspure(pfunc, minroot, roots, heads, includepath):
     """See revlog.reachableroots"""
     if not roots:
         return []
     roots = set(roots)
     visit = list(heads)
     reachable = set()
     seen = {}
     # prefetch all the things! (because python is slow)
     reached = reachable.add
     dovisit = visit.append
     nextvisit = visit.pop
     # open-code the post-order traversal due to the tiny size of
     # sys.getrecursionlimit()
     while visit:
         rev = nextvisit()
         if rev in roots:
             reached(rev)
             if not includepath:
                 continue
         parents = pfunc(rev)
         seen[rev] = parents
         for parent in parents:
             if parent >= minroot and parent not in seen:
                 dovisit(parent)
     if not reachable:
         return baseset()
     if not includepath:
         return reachable
     for rev in sorted(seen):
         for parent in seen[rev]:
             if parent in reachable:
                 reached(rev)
     return reachable
 
 
 def reachableroots(repo, roots, heads, includepath=False):
     """See revlog.reachableroots"""
     if not roots:
         return baseset()
     minroot = roots.min()
     roots = list(roots)
     heads = list(heads)
     revs = repo.changelog.reachableroots(minroot, heads, roots, includepath)
     revs = baseset(revs)
     revs.sort()
     return revs
 
 
 def _changesrange(fctx1, fctx2, linerange2, diffopts):
     """Return `(diffinrange, linerange1)` where `diffinrange` is True
     if diff from fctx2 to fctx1 has changes in linerange2 and
     `linerange1` is the new line range for fctx1.
     """
     blocks = mdiff.allblocks(fctx1.data(), fctx2.data(), diffopts)
     filteredblocks, linerange1 = mdiff.blocksinrange(blocks, linerange2)
     diffinrange = any(stype == b'!' for _, stype in filteredblocks)
     return diffinrange, linerange1
 
 
 def blockancestors(fctx, fromline, toline, followfirst=False):
     """Yield ancestors of `fctx` with respect to the block of lines within
     `fromline`-`toline` range.
     """
     diffopts = patch.diffopts(fctx._repo.ui)
     fctx = fctx.introfilectx()
     visit = {(fctx.linkrev(), fctx.filenode()): (fctx, (fromline, toline))}
     while visit:
         c, linerange2 = visit.pop(max(visit))
         pl = c.parents()
         if followfirst:
             pl = pl[:1]
         if not pl:
             # The block originates from the initial revision.
             yield c, linerange2
             continue
         inrange = False
         for p in pl:
             inrangep, linerange1 = _changesrange(p, c, linerange2, diffopts)
             inrange = inrange or inrangep
             if linerange1[0] == linerange1[1]:
                 # Parent's linerange is empty, meaning that the block got
                 # introduced in this revision; no need to go futher in this
                 # branch.
                 continue
             # Set _descendantrev with 'c' (a known descendant) so that, when
             # _adjustlinkrev is called for 'p', it receives this descendant
             # (as srcrev) instead possibly topmost introrev.
             p._descendantrev = c.rev()
             visit[p.linkrev(), p.filenode()] = p, linerange1
         if inrange:
             yield c, linerange2
 
 
 def blockdescendants(fctx, fromline, toline):
     """Yield descendants of `fctx` with respect to the block of lines within
     `fromline`-`toline` range.
     """
     # First possibly yield 'fctx' if it has changes in range with respect to
     # its parents.
     try:
         c, linerange1 = next(blockancestors(fctx, fromline, toline))
     except StopIteration:
         pass
     else:
         if c == fctx:
             yield c, linerange1
 
     diffopts = patch.diffopts(fctx._repo.ui)
     fl = fctx.filelog()
     seen = {fctx.filerev(): (fctx, (fromline, toline))}
     for i in fl.descendants([fctx.filerev()]):
         c = fctx.filectx(i)
         inrange = False
         for x in fl.parentrevs(i):
             try:
                 p, linerange2 = seen[x]
             except KeyError:
                 # nullrev or other branch
                 continue
             inrangep, linerange1 = _changesrange(c, p, linerange2, diffopts)
             inrange = inrange or inrangep
             # If revision 'i' has been seen (it's a merge) and the line range
             # previously computed differs from the one we just got, we take the
             # surrounding interval. This is conservative but avoids loosing
             # information.
             if i in seen and seen[i][1] != linerange1:
                 lbs, ubs = zip(linerange1, seen[i][1])
                 linerange1 = min(lbs), max(ubs)
             seen[i] = c, linerange1
         if inrange:
             yield c, linerange1
 
 
 @attr.s(slots=True, frozen=True)
 class annotateline(object):
     fctx = attr.ib()
     lineno = attr.ib()
     # Whether this annotation was the result of a skip-annotate.
     skip = attr.ib(default=False)
     text = attr.ib(default=None)
 
 
 @attr.s(slots=True, frozen=True)
 class _annotatedfile(object):
     # list indexed by lineno - 1
     fctxs = attr.ib()
     linenos = attr.ib()
     skips = attr.ib()
     # full file content
     text = attr.ib()
 
 
 def _countlines(text):
     if text.endswith(b"\n"):
         return text.count(b"\n")
     return text.count(b"\n") + int(bool(text))
 
 
 def _decoratelines(text, fctx):
     n = _countlines(text)
     linenos = pycompat.rangelist(1, n + 1)
     return _annotatedfile([fctx] * n, linenos, [False] * n, text)
 
 
 def _annotatepair(parents, childfctx, child, skipchild, diffopts):
     r'''
     Given parent and child fctxes and annotate data for parents, for all lines
     in either parent that match the child, annotate the child with the parent's
     data.
 
     Additionally, if `skipchild` is True, replace all other lines with parent
     annotate data as well such that child is never blamed for any lines.
 
     See test-annotate.py for unit tests.
     '''
     pblocks = [
         (parent, mdiff.allblocks(parent.text, child.text, opts=diffopts))
         for parent in parents
     ]
 
     if skipchild:
         # Need to iterate over the blocks twice -- make it a list
         pblocks = [(p, list(blocks)) for (p, blocks) in pblocks]
     # Mercurial currently prefers p2 over p1 for annotate.
     # TODO: change this?
     for parent, blocks in pblocks:
         for (a1, a2, b1, b2), t in blocks:
             # Changed blocks ('!') or blocks made only of blank lines ('~')
             # belong to the child.
             if t == b'=':
                 child.fctxs[b1:b2] = parent.fctxs[a1:a2]
                 child.linenos[b1:b2] = parent.linenos[a1:a2]
                 child.skips[b1:b2] = parent.skips[a1:a2]
 
     if skipchild:
         # Now try and match up anything that couldn't be matched,
         # Reversing pblocks maintains bias towards p2, matching above
         # behavior.
         pblocks.reverse()
 
         # The heuristics are:
         # * Work on blocks of changed lines (effectively diff hunks with -U0).
         # This could potentially be smarter but works well enough.
         # * For a non-matching section, do a best-effort fit. Match lines in
         #   diff hunks 1:1, dropping lines as necessary.
         # * Repeat the last line as a last resort.
 
         # First, replace as much as possible without repeating the last line.
         remaining = [(parent, []) for parent, _blocks in pblocks]
         for idx, (parent, blocks) in enumerate(pblocks):
             for (a1, a2, b1, b2), _t in blocks:
                 if a2 - a1 >= b2 - b1:
                     for bk in pycompat.xrange(b1, b2):
                         if child.fctxs[bk] == childfctx:
                             ak = min(a1 + (bk - b1), a2 - 1)
                             child.fctxs[bk] = parent.fctxs[ak]
                             child.linenos[bk] = parent.linenos[ak]
                             child.skips[bk] = True
                 else:
                     remaining[idx][1].append((a1, a2, b1, b2))
 
         # Then, look at anything left, which might involve repeating the last
         # line.
         for parent, blocks in remaining:
             for a1, a2, b1, b2 in blocks:
                 for bk in pycompat.xrange(b1, b2):
                     if child.fctxs[bk] == childfctx:
                         ak = min(a1 + (bk - b1), a2 - 1)
                         child.fctxs[bk] = parent.fctxs[ak]
                         child.linenos[bk] = parent.linenos[ak]
                         child.skips[bk] = True
     return child
 
 
 def annotate(base, parents, skiprevs=None, diffopts=None):
     """Core algorithm for filectx.annotate()
 
     `parents(fctx)` is a function returning a list of parent filectxs.
     """
 
     # This algorithm would prefer to be recursive, but Python is a
     # bit recursion-hostile. Instead we do an iterative
     # depth-first search.
 
     # 1st DFS pre-calculates pcache and needed
     visit = [base]
     pcache = {}
     needed = {base: 1}
     while visit:
         f = visit.pop()
         if f in pcache:
             continue
         pl = parents(f)
         pcache[f] = pl
         for p in pl:
             needed[p] = needed.get(p, 0) + 1
             if p not in pcache:
                 visit.append(p)
 
     # 2nd DFS does the actual annotate
     visit[:] = [base]
     hist = {}
     while visit:
         f = visit[-1]
         if f in hist:
             visit.pop()
             continue
 
         ready = True
         pl = pcache[f]
         for p in pl:
             if p not in hist:
                 ready = False
                 visit.append(p)
         if ready:
             visit.pop()
             curr = _decoratelines(f.data(), f)
             skipchild = False
             if skiprevs is not None:
                 skipchild = f._changeid in skiprevs
             curr = _annotatepair(
                 [hist[p] for p in pl], f, curr, skipchild, diffopts
             )
             for p in pl:
                 if needed[p] == 1:
                     del hist[p]
                     del needed[p]
                 else:
                     needed[p] -= 1
 
             hist[f] = curr
             del pcache[f]
 
     a = hist[base]
     return [
         annotateline(*r)
         for r in zip(a.fctxs, a.linenos, a.skips, mdiff.splitnewlines(a.text))
     ]
 
 
 def toposort(revs, parentsfunc, firstbranch=()):
     """Yield revisions from heads to roots one (topo) branch at a time.
 
     This function aims to be used by a graph generator that wishes to minimize
     the number of parallel branches and their interleaving.
 
     Example iteration order (numbers show the "true" order in a changelog):
 
       o  4
       |
       o  1
       |
       | o  3
       | |
       | o  2
       |/
       o  0
 
     Note that the ancestors of merges are understood by the current
     algorithm to be on the same branch. This means no reordering will
     occur behind a merge.
     """
 
     ### Quick summary of the algorithm
     #
     # This function is based around a "retention" principle. We keep revisions
     # in memory until we are ready to emit a whole branch that immediately
     # "merges" into an existing one. This reduces the number of parallel
     # branches with interleaved revisions.
     #
     # During iteration revs are split into two groups:
     # A) revision already emitted
     # B) revision in "retention". They are stored as different subgroups.
     #
     # for each REV, we do the following logic:
     #
     #   1) if REV is a parent of (A), we will emit it. If there is a
     #   retention group ((B) above) that is blocked on REV being
     #   available, we emit all the revisions out of that retention
     #   group first.
     #
     #   2) else, we'll search for a subgroup in (B) awaiting for REV to be
     #   available, if such subgroup exist, we add REV to it and the subgroup is
     #   now awaiting for REV.parents() to be available.
     #
     #   3) finally if no such group existed in (B), we create a new subgroup.
     #
     #
     # To bootstrap the algorithm, we emit the tipmost revision (which
     # puts it in group (A) from above).
 
     revs.sort(reverse=True)
 
     # Set of parents of revision that have been emitted. They can be considered
     # unblocked as the graph generator is already aware of them so there is no
     # need to delay the revisions that reference them.
     #
     # If someone wants to prioritize a branch over the others, pre-filling this
     # set will force all other branches to wait until this branch is ready to be
     # emitted.
     unblocked = set(firstbranch)
 
     # list of groups waiting to be displayed, each group is defined by:
     #
     #   (revs:    lists of revs waiting to be displayed,
     #    blocked: set of that cannot be displayed before those in 'revs')
     #
     # The second value ('blocked') correspond to parents of any revision in the
     # group ('revs') that is not itself contained in the group. The main idea
     # of this algorithm is to delay as much as possible the emission of any
     # revision.  This means waiting for the moment we are about to display
     # these parents to display the revs in a group.
     #
     # This first implementation is smart until it encounters a merge: it will
     # emit revs as soon as any parent is about to be emitted and can grow an
     # arbitrary number of revs in 'blocked'. In practice this mean we properly
     # retains new branches but gives up on any special ordering for ancestors
     # of merges. The implementation can be improved to handle this better.
     #
     # The first subgroup is special. It corresponds to all the revision that
     # were already emitted. The 'revs' lists is expected to be empty and the
     # 'blocked' set contains the parents revisions of already emitted revision.
     #
     # You could pre-seed the <parents> set of groups[0] to a specific
     # changesets to select what the first emitted branch should be.
     groups = [([], unblocked)]
     pendingheap = []
     pendingset = set()
 
     heapq.heapify(pendingheap)
     heappop = heapq.heappop
     heappush = heapq.heappush
     for currentrev in revs:
         # Heap works with smallest element, we want highest so we invert
         if currentrev not in pendingset:
             heappush(pendingheap, -currentrev)
             pendingset.add(currentrev)
         # iterates on pending rev until after the current rev have been
         # processed.
         rev = None
         while rev != currentrev:
             rev = -heappop(pendingheap)
             pendingset.remove(rev)
 
             # Seek for a subgroup blocked, waiting for the current revision.
             matching = [i for i, g in enumerate(groups) if rev in g[1]]
 
             if matching:
                 # The main idea is to gather together all sets that are blocked
                 # on the same revision.
                 #
                 # Groups are merged when a common blocking ancestor is
                 # observed. For example, given two groups:
                 #
                 # revs [5, 4] waiting for 1
                 # revs [3, 2] waiting for 1
                 #
                 # These two groups will be merged when we process
                 # 1. In theory, we could have merged the groups when
                 # we added 2 to the group it is now in (we could have
                 # noticed the groups were both blocked on 1 then), but
                 # the way it works now makes the algorithm simpler.
                 #
                 # We also always keep the oldest subgroup first. We can
                 # probably improve the behavior by having the longest set
                 # first. That way, graph algorithms could minimise the length
                 # of parallel lines their drawing. This is currently not done.
                 targetidx = matching.pop(0)
                 trevs, tparents = groups[targetidx]
                 for i in matching:
                     gr = groups[i]
                     trevs.extend(gr[0])
                     tparents |= gr[1]
                 # delete all merged subgroups (except the one we kept)
                 # (starting from the last subgroup for performance and
                 # sanity reasons)
                 for i in reversed(matching):
                     del groups[i]
             else:
                 # This is a new head. We create a new subgroup for it.
                 targetidx = len(groups)
                 groups.append(([], {rev}))
 
             gr = groups[targetidx]
 
             # We now add the current nodes to this subgroups. This is done
             # after the subgroup merging because all elements from a subgroup
             # that relied on this rev must precede it.
             #
             # we also update the <parents> set to include the parents of the
             # new nodes.
             if rev == currentrev:  # only display stuff in rev
                 gr[0].append(rev)
             gr[1].remove(rev)
             parents = [p for p in parentsfunc(rev) if p > node.nullrev]
             gr[1].update(parents)
             for p in parents:
                 if p not in pendingset:
                     pendingset.add(p)
                     heappush(pendingheap, -p)
 
             # Look for a subgroup to display
             #
             # When unblocked is empty (if clause), we were not waiting for any
             # revisions during the first iteration (if no priority was given) or
             # if we emitted a whole disconnected set of the graph (reached a
             # root).  In that case we arbitrarily take the oldest known
             # subgroup. The heuristic could probably be better.
             #
             # Otherwise (elif clause) if the subgroup is blocked on
             # a revision we just emitted, we can safely emit it as
             # well.
             if not unblocked:
                 if len(groups) > 1:  # display other subset
                     targetidx = 1
                     gr = groups[1]
             elif not gr[1] & unblocked:
                 gr = None
 
             if gr is not None:
                 # update the set of awaited revisions with the one from the
                 # subgroup
                 unblocked |= gr[1]
                 # output all revisions in the subgroup
                 for r in gr[0]:
                     yield r
                 # delete the subgroup that you just output
                 # unless it is groups[0] in which case you just empty it.
                 if targetidx:
                     del groups[targetidx]
                 else:
                     gr[0][:] = []
     # Check if we have some subgroup waiting for revisions we are not going to
     # iterate over
     for g in groups:
         for r in g[0]:
             yield r
 
 
 def headrevs(revs, parentsfn):
     """Resolve the set of heads from a set of revisions.
 
     Receives an iterable of revision numbers and a callbable that receives a
     revision number and returns an iterable of parent revision numbers, possibly
     including nullrev.
 
     Returns a set of revision numbers that are DAG heads within the passed
     subset.
 
     ``nullrev`` is never included in the returned set, even if it is provided in
     the input set.
     """
     headrevs = set(revs)
     parents = {node.nullrev}
     up = parents.update
 
     for rev in revs:
         up(parentsfn(rev))
     headrevs.difference_update(parents)
     return headrevs
 
 
 def headrevssubset(revsfn, parentrevsfn, startrev=None, stoprevs=None):
     """Returns the set of all revs that have no children with control.
 
     ``revsfn`` is a callable that with no arguments returns an iterator over
     all revision numbers in topological order. With a ``start`` argument, it
     returns revision numbers starting at that number.
 
     ``parentrevsfn`` is a callable receiving a revision number and returns an
     iterable of parent revision numbers, where values can include nullrev.
 
     ``startrev`` is a revision number at which to start the search.
 
     ``stoprevs`` is an iterable of revision numbers that, when encountered,
     will stop DAG traversal beyond them. Parents of revisions in this
     collection will be heads.
     """
     if startrev is None:
         startrev = nullrev
 
     stoprevs = set(stoprevs or [])
 
     reachable = {startrev}
     heads = {startrev}
 
     for rev in revsfn(start=startrev + 1):
         for prev in parentrevsfn(rev):
             if prev in reachable:
                 if rev not in stoprevs:
                     reachable.add(rev)
                 heads.add(rev)
 
             if prev in heads and prev not in stoprevs:
                 heads.remove(prev)
 
     return heads
 
 
 def linearize(revs, parentsfn):
     """Linearize and topologically sort a list of revisions.
 
     The linearization process tries to create long runs of revs where a child
     rev comes immediately after its first parent. This is done by visiting the
     heads of the revs in inverse topological order, and for each visited rev,
     visiting its second parent, then its first parent, then adding the rev
     itself to the output list.
 
     Returns a list of revision numbers.
     """
     visit = list(sorted(headrevs(revs, parentsfn), reverse=True))
     finished = set()
     result = []
 
     while visit:
         rev = visit.pop()
         if rev < 0:
             rev = -rev - 1
 
             if rev not in finished:
                 result.append(rev)
                 finished.add(rev)
 
         else:
             visit.append(-rev - 1)
 
             for prev in parentsfn(rev):
                 if prev == node.nullrev or prev not in revs or prev in finished:
                     continue
 
                 visit.append(prev)
 
     assert len(result) == len(revs)
 
     return result

tests/test-template-graph.t

@@ -1,337 +1,440 b''
 Test graph-related template functions
 =====================================
 
   $ cat <<'EOF' >> $HGRCPATH
   > [extensions]
   > drawdag = $RUNTESTDIR/drawdag.py
   > EOF
 
   $ hg init a
   $ cd a
 
   $ hg debugdrawdag <<'EOF'
   >   l
   >  / \
   > |   k
   > |   |\
   > |   | j
   > |   | |
   > i   | |
   > |\  | |
   > h | | |
   > | | | |
   > | g | |
   > | | | |
   > f | | |
   > | |/ /
   > | e |
   > | |/
   > | d
   > |/|
   > c |
   > | |
   > b |
   >   |
   >   a
   > EOF
 
   $ hg log -Gq -T'{rev} {tags}\n'
   o    11 l tip
   |\
   | o    10 i
   | |\
   o \ \    9 k
   |\ \ \
   +-----o  8 g
   | | |
   | o |  7 j
   | | |
   | | o  6 h
   | | |
   o | |  5 e
   |/ /
   | o  4 f
   | |
   o |  3 d
   |\|
   | o  2 c
   | |
   | o  1 b
   |
   o  0 a
   
 
   $ cd ..
 
+Create repository containing merges of p1 > p2:
+
+  $ hg init named-branch-order
+  $ cd named-branch-order
+
+  $ hg branch -q b0
+  $ hg ci -m 0
+  $ hg up -q null
+  $ hg branch -q b1
+  $ hg ci -m 1
+  $ hg up -q null
+  $ hg branch -q b2
+  $ hg ci -m 2
+  $ hg merge -q 1
+  $ hg ci -m 3
+  $ hg ci -m 4 --config ui.allowemptycommit=true
+  $ hg merge -q 0
+  $ hg ci -m 5
+  $ hg ci -m 6 --config ui.allowemptycommit=true
+  $ hg up -q 1
+  $ hg branch -q b7
+  $ hg ci -m 7
+  $ hg ci -m 8 --config ui.allowemptycommit=true
+  $ hg up -q 6
+  $ hg ci -m 9 --config ui.allowemptycommit=true
+  $ hg up -q 8
+  $ hg merge -q 9
+  $ hg ci -m 10
+
+  $ hg log -Gq -T'{rev} {branch} -> {p1.rev} {p2.rev}\n'
+  @    10 b7 -> 8 9
+  |\
+  | o  9 b2 -> 6 -1
+  | |
+  o |  8 b7 -> 7 -1
+  | |
+  o |  7 b7 -> 1 -1
+  | |
+  | o  6 b2 -> 5 -1
+  | |
+  | o    5 b2 -> 4 0
+  | |\
+  | | o  4 b2 -> 3 -1
+  | | |
+  +---o  3 b2 -> 2 1
+  | | |
+  | | o  2 b2 -> -1 -1
+  | |
+  o |  1 b1 -> -1 -1
+   /
+  o  0 b0 -> -1 -1
+  
+
+  $ cd ..
+
 subsetparents
 -------------
 
   $ cd a
 
   $ hg log -Gq -T '{rev} {tags}: {subsetparents(rev, revset("c+i"))}\n' -r 'c+i'
   o  10 i: 2
   :
   o  2 c:
   |
   ~
 
   $ hg log -Gq -T '{rev} {tags}: {subsetparents(rev, revset("c+h+i"))}\n' -r 'c+h+i'
   o    10 i: 6
   |\
   o :  6 h: 2
   :/
   o  2 c:
   |
   ~
 
   $ hg log -Gq -T '{rev} {tags}: {subsetparents(rev, revset("c+h+l"))}\n' -r 'c+h+l'
   o    11 l tip: 6
   :\
   : o  6 h: 2
   :/
   o  2 c:
   |
   ~
 
   $ hg log -Gq -T '{rev} {tags}: {subsetparents(rev, revset("c+f+l"))}\n' -r 'c+f+l'
   o    11 l tip: 4
   :\
   : o  4 f: 2
   :/
   o  2 c:
   |
   ~
 
   $ hg log -Gq -T '{rev} {tags}: {subsetparents(rev, revset("c+h+i+k"))}\n' -r 'c+h+i+k'
   o    10 i: 6
   |\
   | : o  9 k: 2
   | :/
   o :  6 h: 2
   :/
   o  2 c:
   |
   ~
 
   $ hg log -Gq -T '{rev} {tags}: {subsetparents(rev, revset("c+d+h+i+k"))}\n' -r 'c+d+h+i+k'
   o    10 i: 6 3
   |\
   | : o  9 k: 3
   | :/
   o :  6 h: 2
   : :
   : o  3 d: 2
   :/|
   : ~
   o  2 c:
   |
   ~
 
   $ hg log -Gq -T '{rev} {tags}: {subsetparents(rev, revset("c+j+k+i"))}\n' -r 'c+j+k+i'
   o  10 i: 2
   :
   : o  9 k: 7
   :/|
   : o  7 j: 2
   :/
   o  2 c:
   |
   ~
 
   $ hg log -Gq -T '{rev} {tags}: {subsetparents(rev, revset("c+e+f+j"))}\n' -r 'c+e+f+j'
   o  7 j: 2
   :
   : o  5 e: 2
   :/
   : o  4 f: 2
   :/
   o  2 c:
   |
   ~
 
   $ hg log -Gq -T '{rev} {tags}: {subsetparents(rev, revset("b+e+f+j"))}\n' -r 'b+e+f+j'
   o  7 j: 1
   :
   : o  5 e: 1
   :/
   : o  4 f: 1
   :/
   o  1 b:
   
 
   $ hg log -Gq -T '{rev} {tags}: {subsetparents(rev, revset("a+c+f+g+j+l"))}\n' -r 'a+c+f+g+j+l'
   o    11 l tip: 4 8 7
   :\
   : \
   : :\
   : : \
   : : :\
   : : : \
   : : : :\
   : o---+ :  8 g: 0 2
   : :/ / /
   : +---o  7 j: 0 2
   : : :/
   o---+  4 f: 2
    / /
   : o  2 c:
   : |
   : ~
   o  0 a:
   
 
   $ hg log -Gq -T '{rev} {tags}: {subsetparents(rev, revset("b+i+l"))}\n' -r 'b+i+l'
   o    11 l tip: 10
   |\
   o :  10 i: 1
   :/
   o  1 b:
   
 
   $ hg log -Gq -T '{rev} {tags}: {subsetparents(rev, revset("b+i+j+l"))}\n' -r 'b+i+j+l'
   o    11 l tip: 10 7
   |\
   | \
   | :\
   o : :  10 i: 1
   :/ /
   : o  7 j: 1
   :/
   o  1 b:
   
 
 null in subset:
 
   $ hg log -Gq -T '{rev} {tags}: {subsetparents(rev, revset("null+a+c+f"))}\n' -r 'null+a+c+f'
   o  4 f: 2
   |
   o  2 c: -1
   :
   : o  0 a: -1
   :/
   @  -1 : -1
   
 
   $ hg log -Gq -T '{rev} {tags}: {subsetparents(rev, revset("null+a+b+c+f"))}\n' -r 'null+a+b+c+f'
   o  4 f: 2
   |
   o  2 c: 1
   |
   o  1 b: -1
   |
   | o  0 a: -1
   |/
   @  -1 : -1
   
 
 wdir in subset:
 
   $ hg update -qC i
 
   $ hg log -Gq -T '{rev} {tags}: {subsetparents(rev, revset("f+k+wdir()"))}\n' -r 'f+k+wdir()'
   o  2147483647 : 4
   :
   : o    9 k:
   : |\
   : ~ ~
   o  4 f:
   |
   ~
 
   $ hg update -qC null
 
 Revisions not in subset:
 
   $ hg log -T '{rev} {tags}: {subsetparents(rev, revset("a+c+f+g+j+l"))}\n'
   11 l tip: 4 8 7
   10 i: 
   9 k: 
   8 g: 0 2
   7 j: 0 2
   6 h: 
   5 e: 
   4 f: 2
   3 d: 
   2 c: 
   1 b: 
   0 a: 
 
   $ hg log -T '{rev} {tags}: {subsetparents(rev, revset("b+c"))}\n'
   11 l tip: 
   10 i: 
   9 k: 
   8 g: 
   7 j: 
   6 h: 
   5 e: 
   4 f: 
   3 d: 
   2 c: 1
   1 b: 
   0 a: 
 
   $ hg log -T '{rev} {tags}: {subsetparents(rev, revset("b+c"))}\n' -r'reverse(null:2)'
   2 c: 1
   1 b: 
   0 a: 
   -1 : 
 
 Nothing excluded:
 
   $ hg log -T '{rev} {tags}: {subsetparents(rev, revset("null:wdir()"))}\n' -r'reverse(null:wdir())'
   2147483647 : -1
   11 l tip: 10 9
   10 i: 6 8
   9 k: 5 7
   8 g: 5
   7 j: 3
   6 h: 4
   5 e: 3
   4 f: 2
   3 d: 0 2
   2 c: 1
   1 b: -1
   0 a: -1
   -1 : -1
 
 Uncachable query:
 
   $ hg log -Gq -T '{rev} {tags}: {subsetparents(rev, revset("%d:%d", rev, rev - 1))}\n'
   o    11 l tip: 10
   |\
   | o    10 i:
   | |\
   o \ \    9 k:
   |\ \ \
   +-----o  8 g:
   | | |
   | o |  7 j:
   | | |
   | | o  6 h:
   | | |
   o | |  5 e:
   |/ /
   | o  4 f:
   | |
   o |  3 d: 2
   |\|
   | o  2 c: 1
   | |
   | o  1 b:
   |
   o  0 a: -1
   
 
 Invalid arguments:
 
   $ hg log -T '{subsetparents()}\n'
   hg: parse error: subsetparents expects two arguments
   [255]
   $ hg log -T '{subsetparents("a")}\n'
   hg: parse error: subsetparents expects two arguments
   [255]
   $ hg log -T '{subsetparents(rev, extras)}\n'
   hg: parse error: subsetparents expects a queried revset
   [255]
 
   $ cd ..
+
+subsetparents: p1/p2 order
+-------------------------
+
+  $ cd named-branch-order
+
+Parents should be sorted in p1/p2 order since p1 is likely to belong to
+the same named branch:
+
+  $ hg log -Gq -T '{rev} {tags}: {subsetparents(rev, revset("0+1+2+6"))}\n' -r '0+1+2+6'
+  o    6 : 2 1 0
+  :\
+  : \
+  : :\
+  : : o  2 :
+  : :
+  : o  1 :
+  :
+  o  0 :
+  
+
+  $ hg log -Gq -T '{rev} {tags}: {subsetparents(rev, revset("0+1+2+6+10"))}\n' -r '0+1+2+6+10'
+  @    10 tip: 6
+  :\
+  : o    6 : 2 1 0
+  :/:\
+  : : o  2 :
+  : :
+  o :  1 :
+   /
+  o  0 :
+  
+
+And p1 path should be selected if both p1/p2 paths exist:
+
+  $ hg log -Gq -T '{rev} {tags}: {subsetparents(rev, revset("0+1+2+10"))}\n' -r '0+1+2+10'
+  @    10 tip: 1 2 0
+  :\
+  : \
+  : :\
+  : : o  2 :
+  : :
+  o :  1 :
+   /
+  o  0 :
+  
+
+  $ cd ..