mercurial/dagop.py
author Yuya Nishihara <yuya@tcha.org>
Fri, 11 Sep 2020 14:41:05 +0900
branchstable
changeset 45416 4ebc5f325bed
parent 44659 67f757ed86e0
child 45942 89a2afe31e82
permissions -rw-r--r--
log: fix crash and bad filematcher lookup by -fr'wdir()' PATH "-fr'wdir()' ADDED-PATH" is still wrong, which will be fixed in default branch.
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
32903
27932a76a88d dagop: split module hosting DAG-related algorithms from revset
Yuya Nishihara <yuya@tcha.org>
parents: 32885
diff changeset
     1
# dagop.py - graph ancestry and topology algorithm for revset
11275
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     2
#
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     3
# Copyright 2010 Matt Mackall <mpm@selenic.com>
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     4
#
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     5
# This software may be used and distributed according to the terms of the
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     6
# GNU General Public License version 2 or any later version.
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     7
25971
e9cd028f2dff revset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25929
diff changeset
     8
from __future__ import absolute_import
e9cd028f2dff revset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25929
diff changeset
     9
20690
13c0327eeb6f revset: changed ancestors revset to return lazy generators
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20659
diff changeset
    10
import heapq
25971
e9cd028f2dff revset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25929
diff changeset
    11
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
    12
from .node import nullrev
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
    13
from .thirdparty import attr
25971
e9cd028f2dff revset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25929
diff changeset
    14
from . import (
e9cd028f2dff revset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25929
diff changeset
    15
    error,
32904
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
    16
    mdiff,
25971
e9cd028f2dff revset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25929
diff changeset
    17
    node,
32904
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
    18
    patch,
36918
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
    19
    pycompat,
45416
4ebc5f325bed log: fix crash and bad filematcher lookup by -fr'wdir()' PATH
Yuya Nishihara <yuya@tcha.org>
parents: 44659
diff changeset
    20
    scmutil,
30881
1be65deb3d54 smartset: move set classes and related functions from revset module (API)
Yuya Nishihara <yuya@tcha.org>
parents: 30850
diff changeset
    21
    smartset,
25971
e9cd028f2dff revset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25929
diff changeset
    22
)
11275
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    23
30881
1be65deb3d54 smartset: move set classes and related functions from revset module (API)
Yuya Nishihara <yuya@tcha.org>
parents: 30850
diff changeset
    24
baseset = smartset.baseset
1be65deb3d54 smartset: move set classes and related functions from revset module (API)
Yuya Nishihara <yuya@tcha.org>
parents: 30850
diff changeset
    25
generatorset = smartset.generatorset
1be65deb3d54 smartset: move set classes and related functions from revset module (API)
Yuya Nishihara <yuya@tcha.org>
parents: 30850
diff changeset
    26
33002
272a44cac57e revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 33001
diff changeset
    27
# possible maximum depth between null and wdir()
41359
431cf2c8c839 revset: support ranges in #generations relation
Anton Shestakov <av6@dwimlabs.net>
parents: 41277
diff changeset
    28
maxlogdepth = 0x80000000
33002
272a44cac57e revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 33001
diff changeset
    29
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
    30
33079
550c390cd9b2 dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents: 33078
diff changeset
    31
def _walkrevtree(pfunc, revs, startdepth, stopdepth, reverse):
33078
fb663bd0243f dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents: 33077
diff changeset
    32
    """Walk DAG using 'pfunc' from the given 'revs' nodes
fb663bd0243f dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents: 33077
diff changeset
    33
33079
550c390cd9b2 dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents: 33078
diff changeset
    34
    'pfunc(rev)' should return the parent/child revisions of the given 'rev'
550c390cd9b2 dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents: 33078
diff changeset
    35
    if 'reverse' is True/False respectively.
33078
fb663bd0243f dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents: 33077
diff changeset
    36
fb663bd0243f dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents: 33077
diff changeset
    37
    Scan ends at the stopdepth (exlusive) if specified. Revisions found
fb663bd0243f dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents: 33077
diff changeset
    38
    earlier than the startdepth are omitted.
fb663bd0243f dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents: 33077
diff changeset
    39
    """
33003
f63d111258da revset: add startdepth limit to ancestors() as internal option
Yuya Nishihara <yuya@tcha.org>
parents: 33002
diff changeset
    40
    if startdepth is None:
f63d111258da revset: add startdepth limit to ancestors() as internal option
Yuya Nishihara <yuya@tcha.org>
parents: 33002
diff changeset
    41
        startdepth = 0
33002
272a44cac57e revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 33001
diff changeset
    42
    if stopdepth is None:
41359
431cf2c8c839 revset: support ranges in #generations relation
Anton Shestakov <av6@dwimlabs.net>
parents: 41277
diff changeset
    43
        stopdepth = maxlogdepth
33027
a10f5f6771f6 dagop: raise ProgrammingError if stopdepth < 0
Martin von Zweigbergk <martinvonz@google.com>
parents: 33003
diff changeset
    44
    if stopdepth == 0:
33002
272a44cac57e revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 33001
diff changeset
    45
        return
33027
a10f5f6771f6 dagop: raise ProgrammingError if stopdepth < 0
Martin von Zweigbergk <martinvonz@google.com>
parents: 33003
diff changeset
    46
    if stopdepth < 0:
43077
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
    47
        raise error.ProgrammingError(b'negative stopdepth')
33079
550c390cd9b2 dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents: 33078
diff changeset
    48
    if reverse:
550c390cd9b2 dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents: 33078
diff changeset
    49
        heapsign = -1  # max heap
550c390cd9b2 dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents: 33078
diff changeset
    50
    else:
550c390cd9b2 dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents: 33078
diff changeset
    51
        heapsign = +1  # min heap
33002
272a44cac57e revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 33001
diff changeset
    52
32998
c7da57bbae96 dagop: comment why revancestors() doesn't heapify input revs at once
Yuya Nishihara <yuya@tcha.org>
parents: 32997
diff changeset
    53
    # load input revs lazily to heap so earlier revisions can be yielded
c7da57bbae96 dagop: comment why revancestors() doesn't heapify input revs at once
Yuya Nishihara <yuya@tcha.org>
parents: 32997
diff changeset
    54
    # without fully computing the input revs
33079
550c390cd9b2 dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents: 33078
diff changeset
    55
    revs.sort(reverse)
32997
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32904
diff changeset
    56
    irevs = iter(revs)
33079
550c390cd9b2 dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents: 33078
diff changeset
    57
    pendingheap = []  # [(heapsign * rev, depth), ...] (i.e. lower depth first)
20690
13c0327eeb6f revset: changed ancestors revset to return lazy generators
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20659
diff changeset
    58
32997
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32904
diff changeset
    59
    inputrev = next(irevs, None)
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32904
diff changeset
    60
    if inputrev is not None:
33079
550c390cd9b2 dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents: 33078
diff changeset
    61
        heapq.heappush(pendingheap, (heapsign * inputrev, 0))
20691
c1f666e27345 revset: optimized _revancestors method based on order of revisions
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20690
diff changeset
    62
33000
d3d36bcdf036 dagop: just compare with the last value to deduplicate input of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32999
diff changeset
    63
    lastrev = None
32999
08e2793d9f65 dagop: bulk rename variables in revancestors() generator
Yuya Nishihara <yuya@tcha.org>
parents: 32998
diff changeset
    64
    while pendingheap:
33001
92d0945a15e0 dagop: compute depth in revancestors() generator
Yuya Nishihara <yuya@tcha.org>
parents: 33000
diff changeset
    65
        currev, curdepth = heapq.heappop(pendingheap)
33079
550c390cd9b2 dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents: 33078
diff changeset
    66
        currev = heapsign * currev
32999
08e2793d9f65 dagop: bulk rename variables in revancestors() generator
Yuya Nishihara <yuya@tcha.org>
parents: 32998
diff changeset
    67
        if currev == inputrev:
32997
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32904
diff changeset
    68
            inputrev = next(irevs, None)
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32904
diff changeset
    69
            if inputrev is not None:
33079
550c390cd9b2 dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents: 33078
diff changeset
    70
                heapq.heappush(pendingheap, (heapsign * inputrev, 0))
33003
f63d111258da revset: add startdepth limit to ancestors() as internal option
Yuya Nishihara <yuya@tcha.org>
parents: 33002
diff changeset
    71
        # rescan parents until curdepth >= startdepth because queued entries
f63d111258da revset: add startdepth limit to ancestors() as internal option
Yuya Nishihara <yuya@tcha.org>
parents: 33002
diff changeset
    72
        # of the same revision are iterated from the lowest depth
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
    73
        foundnew = currev != lastrev
33003
f63d111258da revset: add startdepth limit to ancestors() as internal option
Yuya Nishihara <yuya@tcha.org>
parents: 33002
diff changeset
    74
        if foundnew and curdepth >= startdepth:
33000
d3d36bcdf036 dagop: just compare with the last value to deduplicate input of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32999
diff changeset
    75
            lastrev = currev
32999
08e2793d9f65 dagop: bulk rename variables in revancestors() generator
Yuya Nishihara <yuya@tcha.org>
parents: 32998
diff changeset
    76
            yield currev
33002
272a44cac57e revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 33001
diff changeset
    77
        pdepth = curdepth + 1
272a44cac57e revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 33001
diff changeset
    78
        if foundnew and pdepth < stopdepth:
33077
58ebb38456e0 dagop: factor out pfunc from revancestors() generator
Yuya Nishihara <yuya@tcha.org>
parents: 33076
diff changeset
    79
            for prev in pfunc(currev):
58ebb38456e0 dagop: factor out pfunc from revancestors() generator
Yuya Nishihara <yuya@tcha.org>
parents: 33076
diff changeset
    80
                if prev != node.nullrev:
33079
550c390cd9b2 dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents: 33078
diff changeset
    81
                    heapq.heappush(pendingheap, (heapsign * prev, pdepth))
20690
13c0327eeb6f revset: changed ancestors revset to return lazy generators
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20659
diff changeset
    82
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
    83
35276
205c3c6c1a51 dagop: extend filectxancestors() to walk multiple files
Yuya Nishihara <yuya@tcha.org>
parents: 35275
diff changeset
    84
def filectxancestors(fctxs, followfirst=False):
205c3c6c1a51 dagop: extend filectxancestors() to walk multiple files
Yuya Nishihara <yuya@tcha.org>
parents: 35275
diff changeset
    85
    """Like filectx.ancestors(), but can walk from multiple files/revisions,
35296
2cb05e6043be dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 35276
diff changeset
    86
    and includes the given fctxs themselves
2cb05e6043be dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 35276
diff changeset
    87
2cb05e6043be dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 35276
diff changeset
    88
    Yields (rev, {fctx, ...}) pairs in descending order.
2cb05e6043be dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 35276
diff changeset
    89
    """
35270
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents: 34065
diff changeset
    90
    visit = {}
35297
c9144396099b dagop: use heap to compute max rev in filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 35296
diff changeset
    91
    visitheap = []
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
    92
35274
2b348dc3239a dagop: change visit dict of filectxancestors() indexed solely by rev
Yuya Nishihara <yuya@tcha.org>
parents: 35273
diff changeset
    93
    def addvisit(fctx):
45416
4ebc5f325bed log: fix crash and bad filematcher lookup by -fr'wdir()' PATH
Yuya Nishihara <yuya@tcha.org>
parents: 44659
diff changeset
    94
        rev = scmutil.intrev(fctx)
35274
2b348dc3239a dagop: change visit dict of filectxancestors() indexed solely by rev
Yuya Nishihara <yuya@tcha.org>
parents: 35273
diff changeset
    95
        if rev not in visit:
2b348dc3239a dagop: change visit dict of filectxancestors() indexed solely by rev
Yuya Nishihara <yuya@tcha.org>
parents: 35273
diff changeset
    96
            visit[rev] = set()
35297
c9144396099b dagop: use heap to compute max rev in filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 35296
diff changeset
    97
            heapq.heappush(visitheap, -rev)  # max heap
35274
2b348dc3239a dagop: change visit dict of filectxancestors() indexed solely by rev
Yuya Nishihara <yuya@tcha.org>
parents: 35273
diff changeset
    98
        visit[rev].add(fctx)
2b348dc3239a dagop: change visit dict of filectxancestors() indexed solely by rev
Yuya Nishihara <yuya@tcha.org>
parents: 35273
diff changeset
    99
35270
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents: 34065
diff changeset
   100
    if followfirst:
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents: 34065
diff changeset
   101
        cut = 1
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents: 34065
diff changeset
   102
    else:
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents: 34065
diff changeset
   103
        cut = None
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents: 34065
diff changeset
   104
35276
205c3c6c1a51 dagop: extend filectxancestors() to walk multiple files
Yuya Nishihara <yuya@tcha.org>
parents: 35275
diff changeset
   105
    for c in fctxs:
205c3c6c1a51 dagop: extend filectxancestors() to walk multiple files
Yuya Nishihara <yuya@tcha.org>
parents: 35275
diff changeset
   106
        addvisit(c)
35275
b4b328ea6175 dagop: put start fctx into visit dict of filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 35274
diff changeset
   107
    while visit:
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   108
        currev = -(heapq.heappop(visitheap))
35296
2cb05e6043be dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 35276
diff changeset
   109
        curfctxs = visit.pop(currev)
2cb05e6043be dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 35276
diff changeset
   110
        yield currev, curfctxs
2cb05e6043be dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 35276
diff changeset
   111
        for c in curfctxs:
2cb05e6043be dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 35276
diff changeset
   112
            for parent in c.parents()[:cut]:
2cb05e6043be dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 35276
diff changeset
   113
                addvisit(parent)
35297
c9144396099b dagop: use heap to compute max rev in filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 35296
diff changeset
   114
    assert not visitheap
35296
2cb05e6043be dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 35276
diff changeset
   115
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   116
35296
2cb05e6043be dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 35276
diff changeset
   117
def filerevancestors(fctxs, followfirst=False):
2cb05e6043be dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 35276
diff changeset
   118
    """Like filectx.ancestors(), but can walk from multiple files/revisions,
2cb05e6043be dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 35276
diff changeset
   119
    and includes the given fctxs themselves
2cb05e6043be dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 35276
diff changeset
   120
2cb05e6043be dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 35276
diff changeset
   121
    Returns a smartset.
2cb05e6043be dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 35276
diff changeset
   122
    """
2cb05e6043be dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 35276
diff changeset
   123
    gen = (rev for rev, _cs in filectxancestors(fctxs, followfirst))
2cb05e6043be dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 35276
diff changeset
   124
    return generatorset(gen, iterasc=False)
35270
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents: 34065
diff changeset
   125
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   126
34065
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
   127
def _genrevancestors(repo, revs, followfirst, startdepth, stopdepth, cutfunc):
33078
fb663bd0243f dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents: 33077
diff changeset
   128
    if followfirst:
fb663bd0243f dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents: 33077
diff changeset
   129
        cut = 1
fb663bd0243f dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents: 33077
diff changeset
   130
    else:
fb663bd0243f dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents: 33077
diff changeset
   131
        cut = None
fb663bd0243f dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents: 33077
diff changeset
   132
    cl = repo.changelog
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   133
34065
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
   134
    def plainpfunc(rev):
33078
fb663bd0243f dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents: 33077
diff changeset
   135
        try:
fb663bd0243f dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents: 33077
diff changeset
   136
            return cl.parentrevs(rev)[:cut]
fb663bd0243f dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents: 33077
diff changeset
   137
        except error.WdirUnsupported:
fb663bd0243f dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents: 33077
diff changeset
   138
            return (pctx.rev() for pctx in repo[rev].parents()[:cut])
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   139
34065
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
   140
    if cutfunc is None:
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
   141
        pfunc = plainpfunc
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
   142
    else:
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
   143
        pfunc = lambda rev: [r for r in plainpfunc(rev) if not cutfunc(r)]
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
   144
        revs = revs.filter(lambda rev: not cutfunc(rev))
33079
550c390cd9b2 dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents: 33078
diff changeset
   145
    return _walkrevtree(pfunc, revs, startdepth, stopdepth, reverse=True)
33078
fb663bd0243f dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents: 33077
diff changeset
   146
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   147
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   148
def revancestors(
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   149
    repo, revs, followfirst=False, startdepth=None, stopdepth=None, cutfunc=None
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   150
):
41533
0f64091cc851 global: make some docstrings raw strings
Gregory Szorc <gregory.szorc@gmail.com>
parents: 41389
diff changeset
   151
    r"""Like revlog.ancestors(), but supports additional options, includes
33002
272a44cac57e revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 33001
diff changeset
   152
    the given revs themselves, and returns a smartset
272a44cac57e revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 33001
diff changeset
   153
33003
f63d111258da revset: add startdepth limit to ancestors() as internal option
Yuya Nishihara <yuya@tcha.org>
parents: 33002
diff changeset
   154
    Scan ends at the stopdepth (exlusive) if specified. Revisions found
f63d111258da revset: add startdepth limit to ancestors() as internal option
Yuya Nishihara <yuya@tcha.org>
parents: 33002
diff changeset
   155
    earlier than the startdepth are omitted.
34065
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
   156
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
   157
    If cutfunc is provided, it will be used to cut the traversal of the DAG.
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
   158
    When cutfunc(X) returns True, the DAG traversal stops - revision X and
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
   159
    X's ancestors in the traversal path will be skipped. This could be an
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
   160
    optimization sometimes.
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
   161
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
   162
    Note: if Y is an ancestor of X, cutfunc(X) returning True does not
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
   163
    necessarily mean Y will also be cut. Usually cutfunc(Y) also wants to
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
   164
    return True in this case. For example,
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
   165
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
   166
        D     # revancestors(repo, D, cutfunc=lambda rev: rev == B)
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
   167
        |\    # will include "A", because the path D -> C -> A was not cut.
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
   168
        B C   # If "B" gets cut, "A" might want to be cut too.
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
   169
        |/
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
   170
        A
33002
272a44cac57e revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 33001
diff changeset
   171
    """
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   172
    gen = _genrevancestors(
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   173
        repo, revs, followfirst, startdepth, stopdepth, cutfunc
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   174
    )
32997
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32904
diff changeset
   175
    return generatorset(gen, iterasc=False)
16409
2cbd7dd0cc1f graphlog: fix --follow-first --rev combinations
Patrick Mezard <patrick@mezard.eu>
parents: 16402
diff changeset
   176
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   177
33073
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
   178
def _genrevdescendants(repo, revs, followfirst):
24306
6ddc86eedc3b style: kill ersatz if-else ternary operators
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 24219
diff changeset
   179
    if followfirst:
6ddc86eedc3b style: kill ersatz if-else ternary operators
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 24219
diff changeset
   180
        cut = 1
6ddc86eedc3b style: kill ersatz if-else ternary operators
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 24219
diff changeset
   181
    else:
6ddc86eedc3b style: kill ersatz if-else ternary operators
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 24219
diff changeset
   182
        cut = None
16409
2cbd7dd0cc1f graphlog: fix --follow-first --rev combinations
Patrick Mezard <patrick@mezard.eu>
parents: 16402
diff changeset
   183
33073
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
   184
    cl = repo.changelog
33076
a76a64c78807 dagop: use smartset.min() in revdescendants() generator
Yuya Nishihara <yuya@tcha.org>
parents: 33075
diff changeset
   185
    first = revs.min()
33073
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
   186
    nullrev = node.nullrev
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
   187
    if first == nullrev:
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
   188
        # Are there nodes with a null first parent and a non-null
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
   189
        # second one? Maybe. Do we care? Probably not.
33075
d83b189aef83 dagop: change revdescendants() to include all root revisions
Yuya Nishihara <yuya@tcha.org>
parents: 33073
diff changeset
   190
        yield first
33073
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
   191
        for i in cl:
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
   192
            yield i
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
   193
    else:
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
   194
        seen = set(revs)
33075
d83b189aef83 dagop: change revdescendants() to include all root revisions
Yuya Nishihara <yuya@tcha.org>
parents: 33073
diff changeset
   195
        for i in cl.revs(first):
d83b189aef83 dagop: change revdescendants() to include all root revisions
Yuya Nishihara <yuya@tcha.org>
parents: 33073
diff changeset
   196
            if i in seen:
d83b189aef83 dagop: change revdescendants() to include all root revisions
Yuya Nishihara <yuya@tcha.org>
parents: 33073
diff changeset
   197
                yield i
d83b189aef83 dagop: change revdescendants() to include all root revisions
Yuya Nishihara <yuya@tcha.org>
parents: 33073
diff changeset
   198
                continue
33073
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
   199
            for x in cl.parentrevs(i)[:cut]:
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
   200
                if x != nullrev and x in seen:
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
   201
                    seen.add(i)
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
   202
                    yield i
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
   203
                    break
20692
7af341082b76 revset: changed descendants revset to use lazy generators
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20691
diff changeset
   204
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   205
33080
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   206
def _builddescendantsmap(repo, startrev, followfirst):
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   207
    """Build map of 'rev -> child revs', offset from startrev"""
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   208
    cl = repo.changelog
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   209
    nullrev = node.nullrev
38783
e7aa113b14f7 global: use pycompat.xrange()
Gregory Szorc <gregory.szorc@gmail.com>
parents: 37066
diff changeset
   210
    descmap = [[] for _rev in pycompat.xrange(startrev, len(cl))]
33080
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   211
    for currev in cl.revs(startrev + 1):
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   212
        p1rev, p2rev = cl.parentrevs(currev)
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   213
        if p1rev >= startrev:
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   214
            descmap[p1rev - startrev].append(currev)
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   215
        if not followfirst and p2rev != nullrev and p2rev >= startrev:
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   216
            descmap[p2rev - startrev].append(currev)
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   217
    return descmap
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   218
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   219
33080
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   220
def _genrevdescendantsofdepth(repo, revs, followfirst, startdepth, stopdepth):
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   221
    startrev = revs.min()
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   222
    descmap = _builddescendantsmap(repo, startrev, followfirst)
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   223
33080
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   224
    def pfunc(rev):
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   225
        return descmap[rev - startrev]
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   226
33080
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   227
    return _walkrevtree(pfunc, revs, startdepth, stopdepth, reverse=False)
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   228
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   229
33080
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   230
def revdescendants(repo, revs, followfirst, startdepth=None, stopdepth=None):
33075
d83b189aef83 dagop: change revdescendants() to include all root revisions
Yuya Nishihara <yuya@tcha.org>
parents: 33073
diff changeset
   231
    """Like revlog.descendants() but supports additional options, includes
33080
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   232
    the given revs themselves, and returns a smartset
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   233
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   234
    Scan ends at the stopdepth (exlusive) if specified. Revisions found
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   235
    earlier than the startdepth are omitted.
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   236
    """
41389
7e55ca658e4b dagop: check if stopdepth is greater than or equal to maxlogdepth
Anton Shestakov <av6@dwimlabs.net>
parents: 41359
diff changeset
   237
    if startdepth is None and (stopdepth is None or stopdepth >= maxlogdepth):
33080
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   238
        gen = _genrevdescendants(repo, revs, followfirst)
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   239
    else:
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   240
        gen = _genrevdescendantsofdepth(
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   241
            repo, revs, followfirst, startdepth, stopdepth
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   242
        )
33073
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
   243
    return generatorset(gen, iterasc=True)
16409
2cbd7dd0cc1f graphlog: fix --follow-first --rev combinations
Patrick Mezard <patrick@mezard.eu>
parents: 16402
diff changeset
   244
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   245
39999
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   246
def descendantrevs(revs, revsfn, parentrevsfn):
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   247
    """Generate revision number descendants in revision order.
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   248
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   249
    Yields revision numbers starting with a child of some rev in
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   250
    ``revs``. Results are ordered by revision number and are
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   251
    therefore topological. Each revision is not considered a descendant
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   252
    of itself.
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   253
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   254
    ``revsfn`` is a callable that with no argument iterates over all
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   255
    revision numbers and with a ``start`` argument iterates over revision
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   256
    numbers beginning with that value.
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   257
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   258
    ``parentrevsfn`` is a callable that receives a revision number and
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   259
    returns an iterable of parent revision numbers, whose values may include
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   260
    nullrev.
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   261
    """
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   262
    first = min(revs)
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   263
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   264
    if first == nullrev:
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   265
        for rev in revsfn():
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   266
            yield rev
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   267
        return
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   268
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   269
    seen = set(revs)
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   270
    for rev in revsfn(start=first + 1):
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   271
        for prev in parentrevsfn(rev):
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   272
            if prev != nullrev and prev in seen:
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   273
                seen.add(rev)
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   274
                yield rev
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   275
                break
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   276
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   277
44592
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   278
class subsetparentswalker(object):
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   279
    r"""Scan adjacent ancestors in the graph given by the subset
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   280
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   281
    This computes parent-child relations in the sub graph filtered by
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   282
    a revset. Primary use case is to draw a revisions graph.
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   283
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   284
    In the following example, we consider that the node 'f' has edges to all
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   285
    ancestor nodes, but redundant paths are eliminated. The edge 'f'->'b'
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   286
    is eliminated because there is a path 'f'->'c'->'b' for example.
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   287
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   288
          - d - e -
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   289
         /         \
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   290
        a - b - c - f
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   291
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   292
    If the node 'c' is filtered out, the edge 'f'->'b' is activated.
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   293
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   294
          - d - e -
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   295
         /         \
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   296
        a - b -(c)- f
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   297
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   298
    Likewise, if 'd' and 'e' are filtered out, this edge is fully eliminated
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   299
    since there is a path 'f'->'c'->'b'->'a' for 'f'->'a'.
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   300
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   301
           (d) (e)
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   302
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   303
        a - b - c - f
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   304
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   305
    Implementation-wise, 'f' is passed down to 'a' as unresolved through the
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   306
    'f'->'e'->'d'->'a' path, whereas we do also remember that 'f' has already
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   307
    been resolved while walking down the 'f'->'c'->'b'->'a' path. When
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   308
    processing the node 'a', the unresolved 'f'->'a' path is eliminated as
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   309
    the 'f' end is marked as resolved.
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   310
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   311
    Ancestors are searched from the tipmost revision in the subset so the
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   312
    results can be cached. You should specify startrev to narrow the search
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   313
    space to ':startrev'.
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   314
    """
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   315
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   316
    def __init__(self, repo, subset, startrev=None):
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   317
        if startrev is not None:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   318
            subset = repo.revs(b'%d:null', startrev) & subset
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   319
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   320
        # equivalent to 'subset = subset.sorted(reverse=True)', but there's
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   321
        # no such function.
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   322
        fastdesc = subset.fastdesc
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   323
        if fastdesc:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   324
            desciter = fastdesc()
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   325
        else:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   326
            if not subset.isdescending() and not subset.istopo():
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   327
                subset = smartset.baseset(subset)
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   328
                subset.sort(reverse=True)
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   329
            desciter = iter(subset)
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   330
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   331
        self._repo = repo
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   332
        self._changelog = repo.changelog
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   333
        self._subset = subset
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   334
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   335
        # scanning state (see _scanparents):
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   336
        self._tovisit = []
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   337
        self._pendingcnt = {}
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   338
        self._pointers = {}
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   339
        self._parents = {}
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   340
        self._inputhead = nullrev  # reassigned by self._advanceinput()
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   341
        self._inputtail = desciter
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   342
        self._bottomrev = nullrev
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   343
        self._advanceinput()
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   344
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   345
    def parentsset(self, rev):
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   346
        """Look up parents of the given revision in the subset, and returns
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   347
        as a smartset"""
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   348
        return smartset.baseset(self.parents(rev))
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   349
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   350
    def parents(self, rev):
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   351
        """Look up parents of the given revision in the subset
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   352
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   353
        The returned revisions are sorted by parent index (p1/p2).
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   354
        """
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   355
        self._scanparents(rev)
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   356
        return [r for _c, r in sorted(self._parents.get(rev, []))]
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   357
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   358
    def _parentrevs(self, rev):
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   359
        try:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   360
            revs = self._changelog.parentrevs(rev)
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   361
            if revs[-1] == nullrev:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   362
                return revs[:-1]
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   363
            return revs
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   364
        except error.WdirUnsupported:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   365
            return tuple(pctx.rev() for pctx in self._repo[None].parents())
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   366
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   367
    def _advanceinput(self):
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   368
        """Advance the input iterator and set the next revision to _inputhead"""
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   369
        if self._inputhead < nullrev:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   370
            return
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   371
        try:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   372
            self._inputhead = next(self._inputtail)
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   373
        except StopIteration:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   374
            self._bottomrev = self._inputhead
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   375
            self._inputhead = nullrev - 1
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   376
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   377
    def _scanparents(self, stoprev):
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   378
        """Scan ancestors until the parents of the specified stoprev are
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   379
        resolved"""
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   380
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   381
        # 'tovisit' is the queue of the input revisions and their ancestors.
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   382
        # It will be populated incrementally to minimize the initial cost
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   383
        # of computing the given subset.
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   384
        #
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   385
        # For to-visit revisions, we keep track of
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   386
        # - the number of the unresolved paths: pendingcnt[rev],
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   387
        # - dict of the unresolved descendants and chains: pointers[rev][0],
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   388
        # - set of the already resolved descendants: pointers[rev][1].
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   389
        #
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   390
        # When a revision is visited, 'pointers[rev]' should be popped and
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   391
        # propagated to its parents accordingly.
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   392
        #
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   393
        # Once all pending paths have been resolved, 'pendingcnt[rev]' becomes
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   394
        # 0 and 'parents[rev]' contains the unsorted list of parent revisions
44659
67f757ed86e0 dagop: fix subsetparentswalker to set p1/p2 chains at merge revision
Yuya Nishihara <yuya@tcha.org>
parents: 44658
diff changeset
   395
        # and p1/p2 chains (excluding linear paths.) The p1/p2 chains will be
67f757ed86e0 dagop: fix subsetparentswalker to set p1/p2 chains at merge revision
Yuya Nishihara <yuya@tcha.org>
parents: 44658
diff changeset
   396
        # used as a sort key preferring p1. 'len(chain)' should be the number
67f757ed86e0 dagop: fix subsetparentswalker to set p1/p2 chains at merge revision
Yuya Nishihara <yuya@tcha.org>
parents: 44658
diff changeset
   397
        # of merges between two revisions.
44592
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   398
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   399
        subset = self._subset
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   400
        tovisit = self._tovisit  # heap queue of [-rev]
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   401
        pendingcnt = self._pendingcnt  # {rev: count} for visited revisions
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   402
        pointers = self._pointers  # {rev: [{unresolved_rev: chain}, resolved]}
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   403
        parents = self._parents  # {rev: [(chain, rev)]}
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   404
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   405
        while tovisit or self._inputhead >= nullrev:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   406
            if pendingcnt.get(stoprev) == 0:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   407
                return
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   408
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   409
            # feed greater revisions from input set to queue
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   410
            if not tovisit:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   411
                heapq.heappush(tovisit, -self._inputhead)
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   412
                self._advanceinput()
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   413
            while self._inputhead >= -tovisit[0]:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   414
                heapq.heappush(tovisit, -self._inputhead)
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   415
                self._advanceinput()
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   416
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   417
            rev = -heapq.heappop(tovisit)
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   418
            if rev < self._bottomrev:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   419
                return
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   420
            if rev in pendingcnt and rev not in pointers:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   421
                continue  # already visited
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   422
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   423
            curactive = rev in subset
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   424
            pendingcnt.setdefault(rev, 0)  # mark as visited
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   425
            if curactive:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   426
                assert rev not in parents
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   427
                parents[rev] = []
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   428
            unresolved, resolved = pointers.pop(rev, ({}, set()))
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   429
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   430
            if curactive:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   431
                # reached to active rev, resolve pending descendants' parents
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   432
                for r, c in unresolved.items():
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   433
                    pendingcnt[r] -= 1
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   434
                    assert pendingcnt[r] >= 0
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   435
                    if r in resolved:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   436
                        continue  # eliminate redundant path
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   437
                    parents[r].append((c, rev))
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   438
                    # mark the descendant 'r' as resolved through this path if
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   439
                    # there are still pending pointers. the 'resolved' set may
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   440
                    # be concatenated later at a fork revision.
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   441
                    if pendingcnt[r] > 0:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   442
                        resolved.add(r)
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   443
                unresolved.clear()
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   444
                # occasionally clean resolved markers. otherwise the set
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   445
                # would grow indefinitely.
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   446
                resolved = {r for r in resolved if pendingcnt[r] > 0}
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   447
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   448
            parentrevs = self._parentrevs(rev)
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   449
            bothparentsactive = all(p in subset for p in parentrevs)
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   450
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   451
            # set up or propagate tracking pointers if
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   452
            # - one of the parents is not active,
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   453
            # - or descendants' parents are unresolved.
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   454
            if not bothparentsactive or unresolved or resolved:
44658
25436f83fb95 dagop: simplify dict/set reuse condition in subsetparentswalker
Yuya Nishihara <yuya@tcha.org>
parents: 44592
diff changeset
   455
                if len(parentrevs) <= 1:
25436f83fb95 dagop: simplify dict/set reuse condition in subsetparentswalker
Yuya Nishihara <yuya@tcha.org>
parents: 44592
diff changeset
   456
                    # can avoid copying the tracking pointer
25436f83fb95 dagop: simplify dict/set reuse condition in subsetparentswalker
Yuya Nishihara <yuya@tcha.org>
parents: 44592
diff changeset
   457
                    parentpointers = [(unresolved, resolved)]
25436f83fb95 dagop: simplify dict/set reuse condition in subsetparentswalker
Yuya Nishihara <yuya@tcha.org>
parents: 44592
diff changeset
   458
                else:
25436f83fb95 dagop: simplify dict/set reuse condition in subsetparentswalker
Yuya Nishihara <yuya@tcha.org>
parents: 44592
diff changeset
   459
                    parentpointers = [
25436f83fb95 dagop: simplify dict/set reuse condition in subsetparentswalker
Yuya Nishihara <yuya@tcha.org>
parents: 44592
diff changeset
   460
                        (unresolved, resolved),
25436f83fb95 dagop: simplify dict/set reuse condition in subsetparentswalker
Yuya Nishihara <yuya@tcha.org>
parents: 44592
diff changeset
   461
                        (unresolved.copy(), resolved.copy()),
25436f83fb95 dagop: simplify dict/set reuse condition in subsetparentswalker
Yuya Nishihara <yuya@tcha.org>
parents: 44592
diff changeset
   462
                    ]
44592
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   463
                    # 'rev' is a merge revision. increment the pending count
44659
67f757ed86e0 dagop: fix subsetparentswalker to set p1/p2 chains at merge revision
Yuya Nishihara <yuya@tcha.org>
parents: 44658
diff changeset
   464
                    # as the 'unresolved' dict will be duplicated, and append
67f757ed86e0 dagop: fix subsetparentswalker to set p1/p2 chains at merge revision
Yuya Nishihara <yuya@tcha.org>
parents: 44658
diff changeset
   465
                    # p1/p2 code to the existing chains.
44592
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   466
                    for r in unresolved:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   467
                        pendingcnt[r] += 1
44659
67f757ed86e0 dagop: fix subsetparentswalker to set p1/p2 chains at merge revision
Yuya Nishihara <yuya@tcha.org>
parents: 44658
diff changeset
   468
                        parentpointers[0][0][r] += b'1'
67f757ed86e0 dagop: fix subsetparentswalker to set p1/p2 chains at merge revision
Yuya Nishihara <yuya@tcha.org>
parents: 44658
diff changeset
   469
                        parentpointers[1][0][r] += b'2'
44592
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   470
                for i, p in enumerate(parentrevs):
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   471
                    assert p < rev
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   472
                    heapq.heappush(tovisit, -p)
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   473
                    if p in pointers:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   474
                        # 'p' is a fork revision. concatenate tracking pointers
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   475
                        # and decrement the pending count accordingly.
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   476
                        knownunresolved, knownresolved = pointers[p]
44658
25436f83fb95 dagop: simplify dict/set reuse condition in subsetparentswalker
Yuya Nishihara <yuya@tcha.org>
parents: 44592
diff changeset
   477
                        unresolved, resolved = parentpointers[i]
44592
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   478
                        for r, c in unresolved.items():
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   479
                            if r in knownunresolved:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   480
                                # unresolved at both paths
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   481
                                pendingcnt[r] -= 1
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   482
                                assert pendingcnt[r] > 0
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   483
                                # take shorter chain
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   484
                                knownunresolved[r] = min(c, knownunresolved[r])
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   485
                            else:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   486
                                knownunresolved[r] = c
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   487
                        # simply propagate the 'resolved' set as deduplicating
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   488
                        # 'unresolved' here would be slightly complicated.
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   489
                        knownresolved.update(resolved)
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   490
                    else:
44658
25436f83fb95 dagop: simplify dict/set reuse condition in subsetparentswalker
Yuya Nishihara <yuya@tcha.org>
parents: 44592
diff changeset
   491
                        pointers[p] = parentpointers[i]
44592
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   492
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   493
            # then, populate the active parents directly and add the current
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   494
            # 'rev' to the tracking pointers of the inactive parents.
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   495
            # 'pointers[p]' may be optimized out if both parents are active.
44659
67f757ed86e0 dagop: fix subsetparentswalker to set p1/p2 chains at merge revision
Yuya Nishihara <yuya@tcha.org>
parents: 44658
diff changeset
   496
            chaincodes = [b''] if len(parentrevs) <= 1 else [b'1', b'2']
44592
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   497
            if curactive and bothparentsactive:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   498
                for i, p in enumerate(parentrevs):
44659
67f757ed86e0 dagop: fix subsetparentswalker to set p1/p2 chains at merge revision
Yuya Nishihara <yuya@tcha.org>
parents: 44658
diff changeset
   499
                    c = chaincodes[i]
44592
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   500
                    parents[rev].append((c, p))
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   501
                    # no need to mark 'rev' as resolved since the 'rev' should
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   502
                    # be fully resolved (i.e. pendingcnt[rev] == 0)
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   503
                assert pendingcnt[rev] == 0
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   504
            elif curactive:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   505
                for i, p in enumerate(parentrevs):
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   506
                    unresolved, resolved = pointers[p]
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   507
                    assert rev not in unresolved
44659
67f757ed86e0 dagop: fix subsetparentswalker to set p1/p2 chains at merge revision
Yuya Nishihara <yuya@tcha.org>
parents: 44658
diff changeset
   508
                    c = chaincodes[i]
44592
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   509
                    if p in subset:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   510
                        parents[rev].append((c, p))
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   511
                        # mark 'rev' as resolved through this path
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   512
                        resolved.add(rev)
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   513
                    else:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   514
                        pendingcnt[rev] += 1
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   515
                        unresolved[rev] = c
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   516
                assert 0 < pendingcnt[rev] <= 2
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   517
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   518
42446
055c3e2c44f0 revlog: speed up isancestor
Valentin Gatien-Baron <vgatien-baron@janestreet.com>
parents: 42445
diff changeset
   519
def _reachablerootspure(pfunc, minroot, roots, heads, includepath):
055c3e2c44f0 revlog: speed up isancestor
Valentin Gatien-Baron <vgatien-baron@janestreet.com>
parents: 42445
diff changeset
   520
    """See revlog.reachableroots"""
16862
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
   521
    if not roots:
26094
df41c7be16d6 reachableroots: construct and sort baseset in revset module
Yuya Nishihara <yuya@tcha.org>
parents: 26093
diff changeset
   522
        return []
26053
b68c9d232db6 reachableroots: use internal "revstates" array to test if rev is a root
Yuya Nishihara <yuya@tcha.org>
parents: 26006
diff changeset
   523
    roots = set(roots)
22487
e40bb83d0989 revset: stop using a baseset instead of a plain list in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22483
diff changeset
   524
    visit = list(heads)
16862
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
   525
    reachable = set()
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
   526
    seen = {}
25566
15412bba5a68 revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25554
diff changeset
   527
    # prefetch all the things! (because python is slow)
15412bba5a68 revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25554
diff changeset
   528
    reached = reachable.add
15412bba5a68 revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25554
diff changeset
   529
    dovisit = visit.append
15412bba5a68 revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25554
diff changeset
   530
    nextvisit = visit.pop
16862
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
   531
    # open-code the post-order traversal due to the tiny size of
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
   532
    # sys.getrecursionlimit()
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
   533
    while visit:
25566
15412bba5a68 revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25554
diff changeset
   534
        rev = nextvisit()
16862
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
   535
        if rev in roots:
25566
15412bba5a68 revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25554
diff changeset
   536
            reached(rev)
26002
fd92bfbbe02d revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents: 26001
diff changeset
   537
            if not includepath:
fd92bfbbe02d revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents: 26001
diff changeset
   538
                continue
42446
055c3e2c44f0 revlog: speed up isancestor
Valentin Gatien-Baron <vgatien-baron@janestreet.com>
parents: 42445
diff changeset
   539
        parents = pfunc(rev)
16862
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
   540
        seen[rev] = parents
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
   541
        for parent in parents:
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
   542
            if parent >= minroot and parent not in seen:
25566
15412bba5a68 revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25554
diff changeset
   543
                dovisit(parent)
16862
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
   544
    if not reachable:
22802
1fcd361efaf4 baseset: use default value instead of [] when possible
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22801
diff changeset
   545
        return baseset()
26002
fd92bfbbe02d revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents: 26001
diff changeset
   546
    if not includepath:
fd92bfbbe02d revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents: 26001
diff changeset
   547
        return reachable
16862
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
   548
    for rev in sorted(seen):
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
   549
        for parent in seen[rev]:
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
   550
            if parent in reachable:
25566
15412bba5a68 revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25554
diff changeset
   551
                reached(rev)
26091
60bbd4f9abd1 reachableroots: sort the smartset in the pure version too
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 26060
diff changeset
   552
    return reachable
16862
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
   553
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   554
26006
1ffd97cbf9a2 reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents: 26002
diff changeset
   555
def reachableroots(repo, roots, heads, includepath=False):
42446
055c3e2c44f0 revlog: speed up isancestor
Valentin Gatien-Baron <vgatien-baron@janestreet.com>
parents: 42445
diff changeset
   556
    """See revlog.reachableroots"""
26006
1ffd97cbf9a2 reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents: 26002
diff changeset
   557
    if not roots:
1ffd97cbf9a2 reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents: 26002
diff changeset
   558
        return baseset()
26093
204131131766 reachableroots: use smartset min
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 26091
diff changeset
   559
    minroot = roots.min()
26053
b68c9d232db6 reachableroots: use internal "revstates" array to test if rev is a root
Yuya Nishihara <yuya@tcha.org>
parents: 26006
diff changeset
   560
    roots = list(roots)
26006
1ffd97cbf9a2 reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents: 26002
diff changeset
   561
    heads = list(heads)
42446
055c3e2c44f0 revlog: speed up isancestor
Valentin Gatien-Baron <vgatien-baron@janestreet.com>
parents: 42445
diff changeset
   562
    revs = repo.changelog.reachableroots(minroot, heads, roots, includepath)
26094
df41c7be16d6 reachableroots: construct and sort baseset in revset module
Yuya Nishihara <yuya@tcha.org>
parents: 26093
diff changeset
   563
    revs = baseset(revs)
df41c7be16d6 reachableroots: construct and sort baseset in revset module
Yuya Nishihara <yuya@tcha.org>
parents: 26093
diff changeset
   564
    revs.sort()
df41c7be16d6 reachableroots: construct and sort baseset in revset module
Yuya Nishihara <yuya@tcha.org>
parents: 26093
diff changeset
   565
    return revs
26006
1ffd97cbf9a2 reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents: 26002
diff changeset
   566
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   567
32904
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   568
def _changesrange(fctx1, fctx2, linerange2, diffopts):
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   569
    """Return `(diffinrange, linerange1)` where `diffinrange` is True
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   570
    if diff from fctx2 to fctx1 has changes in linerange2 and
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   571
    `linerange1` is the new line range for fctx1.
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   572
    """
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   573
    blocks = mdiff.allblocks(fctx1.data(), fctx2.data(), diffopts)
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   574
    filteredblocks, linerange1 = mdiff.blocksinrange(blocks, linerange2)
43077
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
   575
    diffinrange = any(stype == b'!' for _, stype in filteredblocks)
32904
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   576
    return diffinrange, linerange1
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   577
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   578
32904
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   579
def blockancestors(fctx, fromline, toline, followfirst=False):
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   580
    """Yield ancestors of `fctx` with respect to the block of lines within
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   581
    `fromline`-`toline` range.
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   582
    """
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   583
    diffopts = patch.diffopts(fctx._repo.ui)
35271
d90c534099b1 filectx: extract helper method to obtain filectx pointing to its introrev
Yuya Nishihara <yuya@tcha.org>
parents: 35270
diff changeset
   584
    fctx = fctx.introfilectx()
32904
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   585
    visit = {(fctx.linkrev(), fctx.filenode()): (fctx, (fromline, toline))}
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   586
    while visit:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   587
        c, linerange2 = visit.pop(max(visit))
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   588
        pl = c.parents()
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   589
        if followfirst:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   590
            pl = pl[:1]
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   591
        if not pl:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   592
            # The block originates from the initial revision.
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   593
            yield c, linerange2
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   594
            continue
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   595
        inrange = False
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   596
        for p in pl:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   597
            inrangep, linerange1 = _changesrange(p, c, linerange2, diffopts)
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   598
            inrange = inrange or inrangep
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   599
            if linerange1[0] == linerange1[1]:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   600
                # Parent's linerange is empty, meaning that the block got
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   601
                # introduced in this revision; no need to go futher in this
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   602
                # branch.
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   603
                continue
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   604
            # Set _descendantrev with 'c' (a known descendant) so that, when
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   605
            # _adjustlinkrev is called for 'p', it receives this descendant
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   606
            # (as srcrev) instead possibly topmost introrev.
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   607
            p._descendantrev = c.rev()
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   608
            visit[p.linkrev(), p.filenode()] = p, linerange1
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   609
        if inrange:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   610
            yield c, linerange2
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   611
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   612
32904
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   613
def blockdescendants(fctx, fromline, toline):
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   614
    """Yield descendants of `fctx` with respect to the block of lines within
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   615
    `fromline`-`toline` range.
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   616
    """
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   617
    # First possibly yield 'fctx' if it has changes in range with respect to
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   618
    # its parents.
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   619
    try:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   620
        c, linerange1 = next(blockancestors(fctx, fromline, toline))
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   621
    except StopIteration:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   622
        pass
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   623
    else:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   624
        if c == fctx:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   625
            yield c, linerange1
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   626
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   627
    diffopts = patch.diffopts(fctx._repo.ui)
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   628
    fl = fctx.filelog()
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   629
    seen = {fctx.filerev(): (fctx, (fromline, toline))}
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   630
    for i in fl.descendants([fctx.filerev()]):
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   631
        c = fctx.filectx(i)
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   632
        inrange = False
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   633
        for x in fl.parentrevs(i):
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   634
            try:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   635
                p, linerange2 = seen[x]
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   636
            except KeyError:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   637
                # nullrev or other branch
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   638
                continue
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   639
            inrangep, linerange1 = _changesrange(c, p, linerange2, diffopts)
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   640
            inrange = inrange or inrangep
33284
b2670290eab4 followlines: join merge parents line ranges in blockdescendants() (issue5595)
Denis Laxalde <denis.laxalde@logilab.fr>
parents: 33080
diff changeset
   641
            # If revision 'i' has been seen (it's a merge) and the line range
b2670290eab4 followlines: join merge parents line ranges in blockdescendants() (issue5595)
Denis Laxalde <denis.laxalde@logilab.fr>
parents: 33080
diff changeset
   642
            # previously computed differs from the one we just got, we take the
b2670290eab4 followlines: join merge parents line ranges in blockdescendants() (issue5595)
Denis Laxalde <denis.laxalde@logilab.fr>
parents: 33080
diff changeset
   643
            # surrounding interval. This is conservative but avoids loosing
b2670290eab4 followlines: join merge parents line ranges in blockdescendants() (issue5595)
Denis Laxalde <denis.laxalde@logilab.fr>
parents: 33080
diff changeset
   644
            # information.
b2670290eab4 followlines: join merge parents line ranges in blockdescendants() (issue5595)
Denis Laxalde <denis.laxalde@logilab.fr>
parents: 33080
diff changeset
   645
            if i in seen and seen[i][1] != linerange1:
b2670290eab4 followlines: join merge parents line ranges in blockdescendants() (issue5595)
Denis Laxalde <denis.laxalde@logilab.fr>
parents: 33080
diff changeset
   646
                lbs, ubs = zip(linerange1, seen[i][1])
b2670290eab4 followlines: join merge parents line ranges in blockdescendants() (issue5595)
Denis Laxalde <denis.laxalde@logilab.fr>
parents: 33080
diff changeset
   647
                linerange1 = min(lbs), max(ubs)
32904
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   648
            seen[i] = c, linerange1
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   649
        if inrange:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   650
            yield c, linerange1
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   651
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   652
36917
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   653
@attr.s(slots=True, frozen=True)
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   654
class annotateline(object):
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   655
    fctx = attr.ib()
37065
b235bde38a83 annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents: 37064
diff changeset
   656
    lineno = attr.ib()
36917
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   657
    # Whether this annotation was the result of a skip-annotate.
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   658
    skip = attr.ib(default=False)
37066
b33b91ca2ec2 annotate: pack line content into annotateline object (API)
Yuya Nishihara <yuya@tcha.org>
parents: 37065
diff changeset
   659
    text = attr.ib(default=None)
36917
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   660
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   661
37064
434e520adb8c annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents: 36935
diff changeset
   662
@attr.s(slots=True, frozen=True)
434e520adb8c annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents: 36935
diff changeset
   663
class _annotatedfile(object):
434e520adb8c annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents: 36935
diff changeset
   664
    # list indexed by lineno - 1
434e520adb8c annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents: 36935
diff changeset
   665
    fctxs = attr.ib()
434e520adb8c annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents: 36935
diff changeset
   666
    linenos = attr.ib()
434e520adb8c annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents: 36935
diff changeset
   667
    skips = attr.ib()
434e520adb8c annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents: 36935
diff changeset
   668
    # full file content
434e520adb8c annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents: 36935
diff changeset
   669
    text = attr.ib()
434e520adb8c annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents: 36935
diff changeset
   670
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   671
36919
8fba319750c2 dagop: move lines() out of annotate()
Yuya Nishihara <yuya@tcha.org>
parents: 36918
diff changeset
   672
def _countlines(text):
43077
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
   673
    if text.endswith(b"\n"):
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
   674
        return text.count(b"\n")
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
   675
    return text.count(b"\n") + int(bool(text))
36919
8fba319750c2 dagop: move lines() out of annotate()
Yuya Nishihara <yuya@tcha.org>
parents: 36918
diff changeset
   676
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   677
37065
b235bde38a83 annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents: 37064
diff changeset
   678
def _decoratelines(text, fctx):
b235bde38a83 annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents: 37064
diff changeset
   679
    n = _countlines(text)
b235bde38a83 annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents: 37064
diff changeset
   680
    linenos = pycompat.rangelist(1, n + 1)
b235bde38a83 annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents: 37064
diff changeset
   681
    return _annotatedfile([fctx] * n, linenos, [False] * n, text)
b235bde38a83 annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents: 37064
diff changeset
   682
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   683
36917
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   684
def _annotatepair(parents, childfctx, child, skipchild, diffopts):
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   685
    r'''
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   686
    Given parent and child fctxes and annotate data for parents, for all lines
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   687
    in either parent that match the child, annotate the child with the parent's
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   688
    data.
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   689
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   690
    Additionally, if `skipchild` is True, replace all other lines with parent
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   691
    annotate data as well such that child is never blamed for any lines.
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   692
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   693
    See test-annotate.py for unit tests.
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   694
    '''
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   695
    pblocks = [
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   696
        (parent, mdiff.allblocks(parent.text, child.text, opts=diffopts))
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   697
        for parent in parents
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   698
    ]
36917
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   699
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   700
    if skipchild:
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   701
        # Need to iterate over the blocks twice -- make it a list
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   702
        pblocks = [(p, list(blocks)) for (p, blocks) in pblocks]
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   703
    # Mercurial currently prefers p2 over p1 for annotate.
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   704
    # TODO: change this?
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   705
    for parent, blocks in pblocks:
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   706
        for (a1, a2, b1, b2), t in blocks:
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   707
            # Changed blocks ('!') or blocks made only of blank lines ('~')
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   708
            # belong to the child.
43077
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
   709
            if t == b'=':
37064
434e520adb8c annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents: 36935
diff changeset
   710
                child.fctxs[b1:b2] = parent.fctxs[a1:a2]
434e520adb8c annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents: 36935
diff changeset
   711
                child.linenos[b1:b2] = parent.linenos[a1:a2]
434e520adb8c annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents: 36935
diff changeset
   712
                child.skips[b1:b2] = parent.skips[a1:a2]
36917
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   713
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   714
    if skipchild:
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   715
        # Now try and match up anything that couldn't be matched,
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   716
        # Reversing pblocks maintains bias towards p2, matching above
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   717
        # behavior.
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   718
        pblocks.reverse()
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   719
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   720
        # The heuristics are:
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   721
        # * Work on blocks of changed lines (effectively diff hunks with -U0).
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   722
        # This could potentially be smarter but works well enough.
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   723
        # * For a non-matching section, do a best-effort fit. Match lines in
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   724
        #   diff hunks 1:1, dropping lines as necessary.
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   725
        # * Repeat the last line as a last resort.
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   726
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   727
        # First, replace as much as possible without repeating the last line.
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   728
        remaining = [(parent, []) for parent, _blocks in pblocks]
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   729
        for idx, (parent, blocks) in enumerate(pblocks):
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   730
            for (a1, a2, b1, b2), _t in blocks:
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   731
                if a2 - a1 >= b2 - b1:
38783
e7aa113b14f7 global: use pycompat.xrange()
Gregory Szorc <gregory.szorc@gmail.com>
parents: 37066
diff changeset
   732
                    for bk in pycompat.xrange(b1, b2):
37064
434e520adb8c annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents: 36935
diff changeset
   733
                        if child.fctxs[bk] == childfctx:
36917
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   734
                            ak = min(a1 + (bk - b1), a2 - 1)
37064
434e520adb8c annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents: 36935
diff changeset
   735
                            child.fctxs[bk] = parent.fctxs[ak]
434e520adb8c annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents: 36935
diff changeset
   736
                            child.linenos[bk] = parent.linenos[ak]
434e520adb8c annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents: 36935
diff changeset
   737
                            child.skips[bk] = True
36917
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   738
                else:
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   739
                    remaining[idx][1].append((a1, a2, b1, b2))
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   740
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   741
        # Then, look at anything left, which might involve repeating the last
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   742
        # line.
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   743
        for parent, blocks in remaining:
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   744
            for a1, a2, b1, b2 in blocks:
38783
e7aa113b14f7 global: use pycompat.xrange()
Gregory Szorc <gregory.szorc@gmail.com>
parents: 37066
diff changeset
   745
                for bk in pycompat.xrange(b1, b2):
37064
434e520adb8c annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents: 36935
diff changeset
   746
                    if child.fctxs[bk] == childfctx:
36917
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   747
                        ak = min(a1 + (bk - b1), a2 - 1)
37064
434e520adb8c annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents: 36935
diff changeset
   748
                        child.fctxs[bk] = parent.fctxs[ak]
434e520adb8c annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents: 36935
diff changeset
   749
                        child.linenos[bk] = parent.linenos[ak]
434e520adb8c annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents: 36935
diff changeset
   750
                        child.skips[bk] = True
36917
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   751
    return child
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   752
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   753
37065
b235bde38a83 annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents: 37064
diff changeset
   754
def annotate(base, parents, skiprevs=None, diffopts=None):
36918
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   755
    """Core algorithm for filectx.annotate()
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   756
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   757
    `parents(fctx)` is a function returning a list of parent filectxs.
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   758
    """
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   759
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   760
    # This algorithm would prefer to be recursive, but Python is a
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   761
    # bit recursion-hostile. Instead we do an iterative
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   762
    # depth-first search.
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   763
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   764
    # 1st DFS pre-calculates pcache and needed
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   765
    visit = [base]
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   766
    pcache = {}
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   767
    needed = {base: 1}
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   768
    while visit:
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   769
        f = visit.pop()
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   770
        if f in pcache:
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   771
            continue
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   772
        pl = parents(f)
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   773
        pcache[f] = pl
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   774
        for p in pl:
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   775
            needed[p] = needed.get(p, 0) + 1
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   776
            if p not in pcache:
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   777
                visit.append(p)
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   778
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   779
    # 2nd DFS does the actual annotate
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   780
    visit[:] = [base]
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   781
    hist = {}
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   782
    while visit:
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   783
        f = visit[-1]
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   784
        if f in hist:
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   785
            visit.pop()
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   786
            continue
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   787
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   788
        ready = True
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   789
        pl = pcache[f]
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   790
        for p in pl:
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   791
            if p not in hist:
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   792
                ready = False
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   793
                visit.append(p)
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   794
        if ready:
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   795
            visit.pop()
37065
b235bde38a83 annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents: 37064
diff changeset
   796
            curr = _decoratelines(f.data(), f)
36918
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   797
            skipchild = False
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   798
            if skiprevs is not None:
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   799
                skipchild = f._changeid in skiprevs
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   800
            curr = _annotatepair(
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   801
                [hist[p] for p in pl], f, curr, skipchild, diffopts
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   802
            )
36918
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   803
            for p in pl:
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   804
                if needed[p] == 1:
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   805
                    del hist[p]
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   806
                    del needed[p]
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   807
                else:
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   808
                    needed[p] -= 1
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   809
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   810
            hist[f] = curr
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   811
            del pcache[f]
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   812
37064
434e520adb8c annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents: 36935
diff changeset
   813
    a = hist[base]
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   814
    return [
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   815
        annotateline(*r)
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   816
        for r in zip(a.fctxs, a.linenos, a.skips, mdiff.splitnewlines(a.text))
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   817
    ]
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   818
36918
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   819
32903
27932a76a88d dagop: split module hosting DAG-related algorithms from revset
Yuya Nishihara <yuya@tcha.org>
parents: 32885
diff changeset
   820
def toposort(revs, parentsfunc, firstbranch=()):
29347
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   821
    """Yield revisions from heads to roots one (topo) branch at a time.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   822
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   823
    This function aims to be used by a graph generator that wishes to minimize
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   824
    the number of parallel branches and their interleaving.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   825
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   826
    Example iteration order (numbers show the "true" order in a changelog):
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   827
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   828
      o  4
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   829
      |
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   830
      o  1
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   831
      |
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   832
      | o  3
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   833
      | |
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   834
      | o  2
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   835
      |/
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   836
      o  0
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   837
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   838
    Note that the ancestors of merges are understood by the current
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   839
    algorithm to be on the same branch. This means no reordering will
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   840
    occur behind a merge.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   841
    """
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   842
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   843
    ### Quick summary of the algorithm
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   844
    #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   845
    # This function is based around a "retention" principle. We keep revisions
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   846
    # in memory until we are ready to emit a whole branch that immediately
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   847
    # "merges" into an existing one. This reduces the number of parallel
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   848
    # branches with interleaved revisions.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   849
    #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   850
    # During iteration revs are split into two groups:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   851
    # A) revision already emitted
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   852
    # B) revision in "retention". They are stored as different subgroups.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   853
    #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   854
    # for each REV, we do the following logic:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   855
    #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   856
    #   1) if REV is a parent of (A), we will emit it. If there is a
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   857
    #   retention group ((B) above) that is blocked on REV being
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   858
    #   available, we emit all the revisions out of that retention
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   859
    #   group first.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   860
    #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   861
    #   2) else, we'll search for a subgroup in (B) awaiting for REV to be
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   862
    #   available, if such subgroup exist, we add REV to it and the subgroup is
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   863
    #   now awaiting for REV.parents() to be available.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   864
    #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   865
    #   3) finally if no such group existed in (B), we create a new subgroup.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   866
    #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   867
    #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   868
    # To bootstrap the algorithm, we emit the tipmost revision (which
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   869
    # puts it in group (A) from above).
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   870
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   871
    revs.sort(reverse=True)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   872
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   873
    # Set of parents of revision that have been emitted. They can be considered
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   874
    # unblocked as the graph generator is already aware of them so there is no
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   875
    # need to delay the revisions that reference them.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   876
    #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   877
    # If someone wants to prioritize a branch over the others, pre-filling this
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   878
    # set will force all other branches to wait until this branch is ready to be
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   879
    # emitted.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   880
    unblocked = set(firstbranch)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   881
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   882
    # list of groups waiting to be displayed, each group is defined by:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   883
    #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   884
    #   (revs:    lists of revs waiting to be displayed,
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   885
    #    blocked: set of that cannot be displayed before those in 'revs')
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   886
    #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   887
    # The second value ('blocked') correspond to parents of any revision in the
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   888
    # group ('revs') that is not itself contained in the group. The main idea
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   889
    # of this algorithm is to delay as much as possible the emission of any
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   890
    # revision.  This means waiting for the moment we are about to display
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   891
    # these parents to display the revs in a group.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   892
    #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   893
    # This first implementation is smart until it encounters a merge: it will
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   894
    # emit revs as soon as any parent is about to be emitted and can grow an
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   895
    # arbitrary number of revs in 'blocked'. In practice this mean we properly
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   896
    # retains new branches but gives up on any special ordering for ancestors
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   897
    # of merges. The implementation can be improved to handle this better.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   898
    #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   899
    # The first subgroup is special. It corresponds to all the revision that
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   900
    # were already emitted. The 'revs' lists is expected to be empty and the
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   901
    # 'blocked' set contains the parents revisions of already emitted revision.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   902
    #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   903
    # You could pre-seed the <parents> set of groups[0] to a specific
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   904
    # changesets to select what the first emitted branch should be.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   905
    groups = [([], unblocked)]
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   906
    pendingheap = []
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   907
    pendingset = set()
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   908
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   909
    heapq.heapify(pendingheap)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   910
    heappop = heapq.heappop
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   911
    heappush = heapq.heappush
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   912
    for currentrev in revs:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   913
        # Heap works with smallest element, we want highest so we invert
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   914
        if currentrev not in pendingset:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   915
            heappush(pendingheap, -currentrev)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   916
            pendingset.add(currentrev)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   917
        # iterates on pending rev until after the current rev have been
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   918
        # processed.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   919
        rev = None
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   920
        while rev != currentrev:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   921
            rev = -heappop(pendingheap)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   922
            pendingset.remove(rev)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   923
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   924
            # Seek for a subgroup blocked, waiting for the current revision.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   925
            matching = [i for i, g in enumerate(groups) if rev in g[1]]
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   926
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   927
            if matching:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   928
                # The main idea is to gather together all sets that are blocked
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   929
                # on the same revision.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   930
                #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   931
                # Groups are merged when a common blocking ancestor is
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   932
                # observed. For example, given two groups:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   933
                #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   934
                # revs [5, 4] waiting for 1
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   935
                # revs [3, 2] waiting for 1
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   936
                #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   937
                # These two groups will be merged when we process
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   938
                # 1. In theory, we could have merged the groups when
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   939
                # we added 2 to the group it is now in (we could have
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   940
                # noticed the groups were both blocked on 1 then), but
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   941
                # the way it works now makes the algorithm simpler.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   942
                #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   943
                # We also always keep the oldest subgroup first. We can
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   944
                # probably improve the behavior by having the longest set
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   945
                # first. That way, graph algorithms could minimise the length
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   946
                # of parallel lines their drawing. This is currently not done.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   947
                targetidx = matching.pop(0)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   948
                trevs, tparents = groups[targetidx]
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   949
                for i in matching:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   950
                    gr = groups[i]
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   951
                    trevs.extend(gr[0])
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   952
                    tparents |= gr[1]
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   953
                # delete all merged subgroups (except the one we kept)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   954
                # (starting from the last subgroup for performance and
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   955
                # sanity reasons)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   956
                for i in reversed(matching):
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   957
                    del groups[i]
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   958
            else:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   959
                # This is a new head. We create a new subgroup for it.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   960
                targetidx = len(groups)
32291
bd872f64a8ba cleanup: use set literals
Martin von Zweigbergk <martinvonz@google.com>
parents: 32085
diff changeset
   961
                groups.append(([], {rev}))
29347
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   962
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   963
            gr = groups[targetidx]
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   964
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   965
            # We now add the current nodes to this subgroups. This is done
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   966
            # after the subgroup merging because all elements from a subgroup
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   967
            # that relied on this rev must precede it.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   968
            #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   969
            # we also update the <parents> set to include the parents of the
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   970
            # new nodes.
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   971
            if rev == currentrev:  # only display stuff in rev
29347
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   972
                gr[0].append(rev)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   973
            gr[1].remove(rev)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   974
            parents = [p for p in parentsfunc(rev) if p > node.nullrev]
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   975
            gr[1].update(parents)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   976
            for p in parents:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   977
                if p not in pendingset:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   978
                    pendingset.add(p)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   979
                    heappush(pendingheap, -p)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   980
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   981
            # Look for a subgroup to display
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   982
            #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   983
            # When unblocked is empty (if clause), we were not waiting for any
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   984
            # revisions during the first iteration (if no priority was given) or
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   985
            # if we emitted a whole disconnected set of the graph (reached a
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   986
            # root).  In that case we arbitrarily take the oldest known
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   987
            # subgroup. The heuristic could probably be better.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   988
            #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   989
            # Otherwise (elif clause) if the subgroup is blocked on
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   990
            # a revision we just emitted, we can safely emit it as
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   991
            # well.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   992
            if not unblocked:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   993
                if len(groups) > 1:  # display other subset
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   994
                    targetidx = 1
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   995
                    gr = groups[1]
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   996
            elif not gr[1] & unblocked:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   997
                gr = None
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   998
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   999
            if gr is not None:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
  1000
                # update the set of awaited revisions with the one from the
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
  1001
                # subgroup
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
  1002
                unblocked |= gr[1]
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
  1003
                # output all revisions in the subgroup
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
  1004
                for r in gr[0]:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
  1005
                    yield r
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
  1006
                # delete the subgroup that you just output
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
  1007
                # unless it is groups[0] in which case you just empty it.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
  1008
                if targetidx:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
  1009
                    del groups[targetidx]
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
  1010
                else:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
  1011
                    gr[0][:] = []
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
  1012
    # Check if we have some subgroup waiting for revisions we are not going to
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
  1013
    # iterate over
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
  1014
    for g in groups:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
  1015
        for r in g[0]:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
  1016
            yield r
39179
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38783
diff changeset
  1017
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
  1018
39179
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38783
diff changeset
  1019
def headrevs(revs, parentsfn):
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38783
diff changeset
  1020
    """Resolve the set of heads from a set of revisions.
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38783
diff changeset
  1021
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38783
diff changeset
  1022
    Receives an iterable of revision numbers and a callbable that receives a
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38783
diff changeset
  1023
    revision number and returns an iterable of parent revision numbers, possibly
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38783
diff changeset
  1024
    including nullrev.
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38783
diff changeset
  1025
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38783
diff changeset
  1026
    Returns a set of revision numbers that are DAG heads within the passed
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38783
diff changeset
  1027
    subset.
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38783
diff changeset
  1028
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38783
diff changeset
  1029
    ``nullrev`` is never included in the returned set, even if it is provided in
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38783
diff changeset
  1030
    the input set.
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38783
diff changeset
  1031
    """
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38783
diff changeset
  1032
    headrevs = set(revs)
42057
566daffc607d cleanup: use set literals where possible
Martin von Zweigbergk <martinvonz@google.com>
parents: 41533
diff changeset
  1033
    parents = {node.nullrev}
41277
61f9ef23a12f dagop: minor python optimization to `headrevs`
Boris Feld <boris.feld@octobus.net>
parents: 40000
diff changeset
  1034
    up = parents.update
39179
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38783
diff changeset
  1035
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38783
diff changeset
  1036
    for rev in revs:
41277
61f9ef23a12f dagop: minor python optimization to `headrevs`
Boris Feld <boris.feld@octobus.net>
parents: 40000
diff changeset
  1037
        up(parentsfn(rev))
61f9ef23a12f dagop: minor python optimization to `headrevs`
Boris Feld <boris.feld@octobus.net>
parents: 40000
diff changeset
  1038
    headrevs.difference_update(parents)
39179
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38783
diff changeset
  1039
    return headrevs
39181
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1040
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
  1041
40000
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1042
def headrevssubset(revsfn, parentrevsfn, startrev=None, stoprevs=None):
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1043
    """Returns the set of all revs that have no children with control.
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1044
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1045
    ``revsfn`` is a callable that with no arguments returns an iterator over
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1046
    all revision numbers in topological order. With a ``start`` argument, it
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1047
    returns revision numbers starting at that number.
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1048
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1049
    ``parentrevsfn`` is a callable receiving a revision number and returns an
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1050
    iterable of parent revision numbers, where values can include nullrev.
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1051
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1052
    ``startrev`` is a revision number at which to start the search.
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1053
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1054
    ``stoprevs`` is an iterable of revision numbers that, when encountered,
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1055
    will stop DAG traversal beyond them. Parents of revisions in this
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1056
    collection will be heads.
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1057
    """
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1058
    if startrev is None:
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1059
        startrev = nullrev
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1060
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1061
    stoprevs = set(stoprevs or [])
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1062
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1063
    reachable = {startrev}
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1064
    heads = {startrev}
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1065
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1066
    for rev in revsfn(start=startrev + 1):
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1067
        for prev in parentrevsfn(rev):
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1068
            if prev in reachable:
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1069
                if rev not in stoprevs:
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1070
                    reachable.add(rev)
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1071
                heads.add(rev)
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1072
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1073
            if prev in heads and prev not in stoprevs:
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1074
                heads.remove(prev)
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1075
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1076
    return heads
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1077
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
  1078
39181
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1079
def linearize(revs, parentsfn):
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1080
    """Linearize and topologically sort a list of revisions.
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1081
39607
5362c96f2feb dagop: fix typo spotted while doing unrelated investigation
Augie Fackler <augie@google.com>
parents: 39181
diff changeset
  1082
    The linearization process tries to create long runs of revs where a child
39181
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1083
    rev comes immediately after its first parent. This is done by visiting the
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1084
    heads of the revs in inverse topological order, and for each visited rev,
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1085
    visiting its second parent, then its first parent, then adding the rev
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1086
    itself to the output list.
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1087
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1088
    Returns a list of revision numbers.
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1089
    """
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1090
    visit = list(sorted(headrevs(revs, parentsfn), reverse=True))
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1091
    finished = set()
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1092
    result = []
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1093
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1094
    while visit:
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1095
        rev = visit.pop()
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1096
        if rev < 0:
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1097
            rev = -rev - 1
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1098
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1099
            if rev not in finished:
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1100
                result.append(rev)
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1101
                finished.add(rev)
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1102
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1103
        else:
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1104
            visit.append(-rev - 1)
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1105
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1106
            for prev in parentsfn(rev):
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1107
                if prev == node.nullrev or prev not in revs or prev in finished:
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1108
                    continue
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1109
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1110
                visit.append(prev)
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1111
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1112
    assert len(result) == len(revs)
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1113
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1114
    return result