mercurial/dagop.py
author Arseniy Alekseyev <aalekseyev@janestreet.com>
Thu, 21 Dec 2023 17:38:04 +0000
changeset 51395 a0d88b021a98
parent 49284 d44e3c45f0e4
child 51729 278af66e6595
permissions -rw-r--r--
unbundle: faster computation of changed heads To compute the set of changed heads it's sufficient to look at the recent commits, instead of looking at all heads currently in existence.
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
#
46819
d4ba4d51f85f contributor: change mentions of mpm to olivia
Raphaël Gomès <rgomes@octobus.net>
parents: 46113
diff changeset
     3
# Copyright 2010 Olivia Mackall <olivia@selenic.com>
11275
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
20690
13c0327eeb6f revset: changed ancestors revset to return lazy generators
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20659
diff changeset
     9
import heapq
25971
e9cd028f2dff revset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25929
diff changeset
    10
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
    11
from .thirdparty import attr
46113
59fa3890d40a node: import symbols explicitly
Joerg Sonnenberger <joerg@bec.de>
parents: 45942
diff changeset
    12
from .node import nullrev
25971
e9cd028f2dff revset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25929
diff changeset
    13
from . import (
e9cd028f2dff revset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25929
diff changeset
    14
    error,
32904
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
    15
    mdiff,
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
    16
    patch,
36918
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
    17
    pycompat,
45416
4ebc5f325bed log: fix crash and bad filematcher lookup by -fr'wdir()' PATH
Yuya Nishihara <yuya@tcha.org>
parents: 44659
diff changeset
    18
    scmutil,
30881
1be65deb3d54 smartset: move set classes and related functions from revset module (API)
Yuya Nishihara <yuya@tcha.org>
parents: 30850
diff changeset
    19
    smartset,
25971
e9cd028f2dff revset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25929
diff changeset
    20
)
11275
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    21
30881
1be65deb3d54 smartset: move set classes and related functions from revset module (API)
Yuya Nishihara <yuya@tcha.org>
parents: 30850
diff changeset
    22
baseset = smartset.baseset
1be65deb3d54 smartset: move set classes and related functions from revset module (API)
Yuya Nishihara <yuya@tcha.org>
parents: 30850
diff changeset
    23
generatorset = smartset.generatorset
1be65deb3d54 smartset: move set classes and related functions from revset module (API)
Yuya Nishihara <yuya@tcha.org>
parents: 30850
diff changeset
    24
33002
272a44cac57e revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 33001
diff changeset
    25
# possible maximum depth between null and wdir()
41359
431cf2c8c839 revset: support ranges in #generations relation
Anton Shestakov <av6@dwimlabs.net>
parents: 41277
diff changeset
    26
maxlogdepth = 0x80000000
33002
272a44cac57e revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 33001
diff changeset
    27
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
    28
33079
550c390cd9b2 dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents: 33078
diff changeset
    29
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
    30
    """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
    31
33079
550c390cd9b2 dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents: 33078
diff changeset
    32
    '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
    33
    if 'reverse' is True/False respectively.
33078
fb663bd0243f dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents: 33077
diff changeset
    34
fb663bd0243f dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents: 33077
diff changeset
    35
    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
    36
    earlier than the startdepth are omitted.
fb663bd0243f dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents: 33077
diff changeset
    37
    """
33003
f63d111258da revset: add startdepth limit to ancestors() as internal option
Yuya Nishihara <yuya@tcha.org>
parents: 33002
diff changeset
    38
    if startdepth is None:
f63d111258da revset: add startdepth limit to ancestors() as internal option
Yuya Nishihara <yuya@tcha.org>
parents: 33002
diff changeset
    39
        startdepth = 0
33002
272a44cac57e revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 33001
diff changeset
    40
    if stopdepth is None:
41359
431cf2c8c839 revset: support ranges in #generations relation
Anton Shestakov <av6@dwimlabs.net>
parents: 41277
diff changeset
    41
        stopdepth = maxlogdepth
33027
a10f5f6771f6 dagop: raise ProgrammingError if stopdepth < 0
Martin von Zweigbergk <martinvonz@google.com>
parents: 33003
diff changeset
    42
    if stopdepth == 0:
33002
272a44cac57e revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 33001
diff changeset
    43
        return
33027
a10f5f6771f6 dagop: raise ProgrammingError if stopdepth < 0
Martin von Zweigbergk <martinvonz@google.com>
parents: 33003
diff changeset
    44
    if stopdepth < 0:
43077
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
    45
        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
    46
    if reverse:
550c390cd9b2 dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents: 33078
diff changeset
    47
        heapsign = -1  # max heap
550c390cd9b2 dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents: 33078
diff changeset
    48
    else:
550c390cd9b2 dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents: 33078
diff changeset
    49
        heapsign = +1  # min heap
33002
272a44cac57e revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 33001
diff changeset
    50
32998
c7da57bbae96 dagop: comment why revancestors() doesn't heapify input revs at once
Yuya Nishihara <yuya@tcha.org>
parents: 32997
diff changeset
    51
    # 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
    52
    # 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
    53
    revs.sort(reverse)
32997
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32904
diff changeset
    54
    irevs = iter(revs)
33079
550c390cd9b2 dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents: 33078
diff changeset
    55
    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
    56
32997
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32904
diff changeset
    57
    inputrev = next(irevs, None)
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32904
diff changeset
    58
    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
    59
        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
    60
33000
d3d36bcdf036 dagop: just compare with the last value to deduplicate input of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32999
diff changeset
    61
    lastrev = None
32999
08e2793d9f65 dagop: bulk rename variables in revancestors() generator
Yuya Nishihara <yuya@tcha.org>
parents: 32998
diff changeset
    62
    while pendingheap:
33001
92d0945a15e0 dagop: compute depth in revancestors() generator
Yuya Nishihara <yuya@tcha.org>
parents: 33000
diff changeset
    63
        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
    64
        currev = heapsign * currev
32999
08e2793d9f65 dagop: bulk rename variables in revancestors() generator
Yuya Nishihara <yuya@tcha.org>
parents: 32998
diff changeset
    65
        if currev == inputrev:
32997
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32904
diff changeset
    66
            inputrev = next(irevs, None)
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32904
diff changeset
    67
            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
    68
                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
    69
        # 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
    70
        # 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
    71
        foundnew = currev != lastrev
33003
f63d111258da revset: add startdepth limit to ancestors() as internal option
Yuya Nishihara <yuya@tcha.org>
parents: 33002
diff changeset
    72
        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
    73
            lastrev = currev
32999
08e2793d9f65 dagop: bulk rename variables in revancestors() generator
Yuya Nishihara <yuya@tcha.org>
parents: 32998
diff changeset
    74
            yield currev
33002
272a44cac57e revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 33001
diff changeset
    75
        pdepth = curdepth + 1
272a44cac57e revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 33001
diff changeset
    76
        if foundnew and pdepth < stopdepth:
33077
58ebb38456e0 dagop: factor out pfunc from revancestors() generator
Yuya Nishihara <yuya@tcha.org>
parents: 33076
diff changeset
    77
            for prev in pfunc(currev):
46113
59fa3890d40a node: import symbols explicitly
Joerg Sonnenberger <joerg@bec.de>
parents: 45942
diff changeset
    78
                if prev != nullrev:
33079
550c390cd9b2 dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents: 33078
diff changeset
    79
                    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
    80
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
    81
35276
205c3c6c1a51 dagop: extend filectxancestors() to walk multiple files
Yuya Nishihara <yuya@tcha.org>
parents: 35275
diff changeset
    82
def filectxancestors(fctxs, followfirst=False):
205c3c6c1a51 dagop: extend filectxancestors() to walk multiple files
Yuya Nishihara <yuya@tcha.org>
parents: 35275
diff changeset
    83
    """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
    84
    and includes the given fctxs themselves
2cb05e6043be dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 35276
diff changeset
    85
2cb05e6043be dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 35276
diff changeset
    86
    Yields (rev, {fctx, ...}) pairs in descending order.
2cb05e6043be dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 35276
diff changeset
    87
    """
35270
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents: 34065
diff changeset
    88
    visit = {}
35297
c9144396099b dagop: use heap to compute max rev in filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 35296
diff changeset
    89
    visitheap = []
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
    90
35274
2b348dc3239a dagop: change visit dict of filectxancestors() indexed solely by rev
Yuya Nishihara <yuya@tcha.org>
parents: 35273
diff changeset
    91
    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
    92
        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
    93
        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
    94
            visit[rev] = set()
35297
c9144396099b dagop: use heap to compute max rev in filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 35296
diff changeset
    95
            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
    96
        visit[rev].add(fctx)
2b348dc3239a dagop: change visit dict of filectxancestors() indexed solely by rev
Yuya Nishihara <yuya@tcha.org>
parents: 35273
diff changeset
    97
35270
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents: 34065
diff changeset
    98
    if followfirst:
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents: 34065
diff changeset
    99
        cut = 1
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents: 34065
diff changeset
   100
    else:
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents: 34065
diff changeset
   101
        cut = None
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents: 34065
diff changeset
   102
35276
205c3c6c1a51 dagop: extend filectxancestors() to walk multiple files
Yuya Nishihara <yuya@tcha.org>
parents: 35275
diff changeset
   103
    for c in fctxs:
205c3c6c1a51 dagop: extend filectxancestors() to walk multiple files
Yuya Nishihara <yuya@tcha.org>
parents: 35275
diff changeset
   104
        addvisit(c)
35275
b4b328ea6175 dagop: put start fctx into visit dict of filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 35274
diff changeset
   105
    while visit:
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   106
        currev = -(heapq.heappop(visitheap))
35296
2cb05e6043be dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 35276
diff changeset
   107
        curfctxs = visit.pop(currev)
2cb05e6043be dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 35276
diff changeset
   108
        yield currev, curfctxs
2cb05e6043be dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 35276
diff changeset
   109
        for c in curfctxs:
2cb05e6043be dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 35276
diff changeset
   110
            for parent in c.parents()[:cut]:
2cb05e6043be dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 35276
diff changeset
   111
                addvisit(parent)
35297
c9144396099b dagop: use heap to compute max rev in filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 35296
diff changeset
   112
    assert not visitheap
35296
2cb05e6043be dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 35276
diff changeset
   113
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   114
35296
2cb05e6043be dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 35276
diff changeset
   115
def filerevancestors(fctxs, followfirst=False):
2cb05e6043be dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 35276
diff changeset
   116
    """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
   117
    and includes the given fctxs themselves
2cb05e6043be dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 35276
diff changeset
   118
2cb05e6043be dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 35276
diff changeset
   119
    Returns a smartset.
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
    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
   122
    return generatorset(gen, iterasc=False)
35270
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents: 34065
diff changeset
   123
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   124
34065
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
   125
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
   126
    if followfirst:
fb663bd0243f dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents: 33077
diff changeset
   127
        cut = 1
fb663bd0243f dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents: 33077
diff changeset
   128
    else:
fb663bd0243f dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents: 33077
diff changeset
   129
        cut = None
fb663bd0243f dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents: 33077
diff changeset
   130
    cl = repo.changelog
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   131
34065
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
   132
    def plainpfunc(rev):
33078
fb663bd0243f dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents: 33077
diff changeset
   133
        try:
fb663bd0243f dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents: 33077
diff changeset
   134
            return cl.parentrevs(rev)[:cut]
fb663bd0243f dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents: 33077
diff changeset
   135
        except error.WdirUnsupported:
fb663bd0243f dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents: 33077
diff changeset
   136
            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
   137
34065
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
   138
    if cutfunc is None:
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
   139
        pfunc = plainpfunc
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
   140
    else:
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
   141
        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
   142
        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
   143
    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
   144
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   145
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   146
def revancestors(
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   147
    repo, revs, followfirst=False, startdepth=None, stopdepth=None, cutfunc=None
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   148
):
41533
0f64091cc851 global: make some docstrings raw strings
Gregory Szorc <gregory.szorc@gmail.com>
parents: 41389
diff changeset
   149
    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
   150
    the given revs themselves, and returns a smartset
272a44cac57e revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 33001
diff changeset
   151
33003
f63d111258da revset: add startdepth limit to ancestors() as internal option
Yuya Nishihara <yuya@tcha.org>
parents: 33002
diff changeset
   152
    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
   153
    earlier than the startdepth are omitted.
34065
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
   154
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
   155
    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
   156
    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
   157
    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
   158
    optimization sometimes.
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
   159
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
   160
    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
   161
    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
   162
    return True in this case. For example,
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
   163
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
   164
        D     # revancestors(repo, D, cutfunc=lambda rev: rev == B)
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
   165
        |\    # 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
   166
        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
   167
        |/
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
   168
        A
33002
272a44cac57e revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 33001
diff changeset
   169
    """
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   170
    gen = _genrevancestors(
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   171
        repo, revs, followfirst, startdepth, stopdepth, cutfunc
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   172
    )
32997
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32904
diff changeset
   173
    return generatorset(gen, iterasc=False)
16409
2cbd7dd0cc1f graphlog: fix --follow-first --rev combinations
Patrick Mezard <patrick@mezard.eu>
parents: 16402
diff changeset
   174
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   175
33073
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
   176
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
   177
    if followfirst:
6ddc86eedc3b style: kill ersatz if-else ternary operators
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 24219
diff changeset
   178
        cut = 1
6ddc86eedc3b style: kill ersatz if-else ternary operators
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 24219
diff changeset
   179
    else:
6ddc86eedc3b style: kill ersatz if-else ternary operators
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 24219
diff changeset
   180
        cut = None
16409
2cbd7dd0cc1f graphlog: fix --follow-first --rev combinations
Patrick Mezard <patrick@mezard.eu>
parents: 16402
diff changeset
   181
33073
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
   182
    cl = repo.changelog
33076
a76a64c78807 dagop: use smartset.min() in revdescendants() generator
Yuya Nishihara <yuya@tcha.org>
parents: 33075
diff changeset
   183
    first = revs.min()
33073
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
   184
    if first == nullrev:
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
   185
        # 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
   186
        # 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
   187
        yield first
33073
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
   188
        for i in cl:
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
   189
            yield i
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
   190
    else:
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
   191
        seen = set(revs)
33075
d83b189aef83 dagop: change revdescendants() to include all root revisions
Yuya Nishihara <yuya@tcha.org>
parents: 33073
diff changeset
   192
        for i in cl.revs(first):
d83b189aef83 dagop: change revdescendants() to include all root revisions
Yuya Nishihara <yuya@tcha.org>
parents: 33073
diff changeset
   193
            if i in seen:
d83b189aef83 dagop: change revdescendants() to include all root revisions
Yuya Nishihara <yuya@tcha.org>
parents: 33073
diff changeset
   194
                yield i
d83b189aef83 dagop: change revdescendants() to include all root revisions
Yuya Nishihara <yuya@tcha.org>
parents: 33073
diff changeset
   195
                continue
33073
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
   196
            for x in cl.parentrevs(i)[:cut]:
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
   197
                if x != nullrev and x in seen:
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
   198
                    seen.add(i)
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
   199
                    yield i
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
   200
                    break
20692
7af341082b76 revset: changed descendants revset to use lazy generators
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20691
diff changeset
   201
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   202
33080
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   203
def _builddescendantsmap(repo, startrev, followfirst):
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   204
    """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
   205
    cl = repo.changelog
49284
d44e3c45f0e4 py3: replace `pycompat.xrange` by `range`
Manuel Jacob <me@manueljacob.de>
parents: 48946
diff changeset
   206
    descmap = [[] for _rev in range(startrev, len(cl))]
33080
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   207
    for currev in cl.revs(startrev + 1):
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   208
        p1rev, p2rev = cl.parentrevs(currev)
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   209
        if p1rev >= startrev:
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   210
            descmap[p1rev - startrev].append(currev)
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   211
        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
   212
            descmap[p2rev - startrev].append(currev)
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   213
    return descmap
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   214
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   215
33080
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   216
def _genrevdescendantsofdepth(repo, revs, followfirst, startdepth, stopdepth):
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   217
    startrev = revs.min()
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   218
    descmap = _builddescendantsmap(repo, startrev, followfirst)
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 pfunc(rev):
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   221
        return descmap[rev - startrev]
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   222
33080
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   223
    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
   224
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   225
33080
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   226
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
   227
    """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
   228
    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
   229
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   230
    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
   231
    earlier than the startdepth are omitted.
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   232
    """
41389
7e55ca658e4b dagop: check if stopdepth is greater than or equal to maxlogdepth
Anton Shestakov <av6@dwimlabs.net>
parents: 41359
diff changeset
   233
    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
   234
        gen = _genrevdescendants(repo, revs, followfirst)
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
   235
    else:
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   236
        gen = _genrevdescendantsofdepth(
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   237
            repo, revs, followfirst, startdepth, stopdepth
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   238
        )
33073
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
   239
    return generatorset(gen, iterasc=True)
16409
2cbd7dd0cc1f graphlog: fix --follow-first --rev combinations
Patrick Mezard <patrick@mezard.eu>
parents: 16402
diff changeset
   240
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   241
39999
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   242
def descendantrevs(revs, revsfn, parentrevsfn):
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   243
    """Generate revision number descendants in revision order.
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   244
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   245
    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
   246
    ``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
   247
    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
   248
    of itself.
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   249
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   250
    ``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
   251
    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
   252
    numbers beginning with that value.
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
    ``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
   255
    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
   256
    nullrev.
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
    first = min(revs)
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   259
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   260
    if first == nullrev:
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   261
        for rev in revsfn():
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   262
            yield rev
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   263
        return
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   264
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   265
    seen = set(revs)
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   266
    for rev in revsfn(start=first + 1):
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   267
        for prev in parentrevsfn(rev):
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   268
            if prev != nullrev and prev in seen:
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   269
                seen.add(rev)
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   270
                yield rev
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   271
                break
0b24fcd88066 dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39607
diff changeset
   272
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   273
48946
642e31cb55f0 py3: use class X: instead of class X(object):
Gregory Szorc <gregory.szorc@gmail.com>
parents: 48875
diff changeset
   274
class subsetparentswalker:
44592
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   275
    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
   276
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   277
    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
   278
    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
   279
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   280
    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
   281
    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
   282
    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
   283
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   284
          - d - e -
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   285
         /         \
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   286
        a - b - c - f
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
    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
   289
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   290
          - d - e -
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
        a - b -(c)- f
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
    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
   295
    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
   296
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   297
           (d) (e)
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   298
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   299
        a - b - c - f
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
    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
   302
    '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
   303
    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
   304
    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
   305
    the 'f' end is marked as resolved.
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   306
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   307
    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
   308
    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
   309
    space to ':startrev'.
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
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   312
    def __init__(self, repo, subset, startrev=None):
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   313
        if startrev is not None:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   314
            subset = repo.revs(b'%d:null', startrev) & subset
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
        # 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
   317
        # no such function.
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   318
        fastdesc = subset.fastdesc
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   319
        if fastdesc:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   320
            desciter = fastdesc()
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   321
        else:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   322
            if not subset.isdescending() and not subset.istopo():
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   323
                subset = smartset.baseset(subset)
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   324
                subset.sort(reverse=True)
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   325
            desciter = iter(subset)
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   326
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   327
        self._repo = repo
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   328
        self._changelog = repo.changelog
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   329
        self._subset = 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
        # scanning state (see _scanparents):
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   332
        self._tovisit = []
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   333
        self._pendingcnt = {}
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   334
        self._pointers = {}
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   335
        self._parents = {}
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   336
        self._inputhead = nullrev  # reassigned by self._advanceinput()
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   337
        self._inputtail = desciter
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   338
        self._bottomrev = nullrev
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   339
        self._advanceinput()
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   340
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   341
    def parentsset(self, rev):
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   342
        """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
   343
        as a smartset"""
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   344
        return smartset.baseset(self.parents(rev))
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   345
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   346
    def parents(self, rev):
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   347
        """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
   348
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   349
        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
   350
        """
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   351
        self._scanparents(rev)
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   352
        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
   353
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   354
    def _parentrevs(self, rev):
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   355
        try:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   356
            revs = self._changelog.parentrevs(rev)
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   357
            if revs[-1] == nullrev:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   358
                return revs[:-1]
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   359
            return revs
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   360
        except error.WdirUnsupported:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   361
            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
   362
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   363
    def _advanceinput(self):
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   364
        """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
   365
        if self._inputhead < nullrev:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   366
            return
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   367
        try:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   368
            self._inputhead = next(self._inputtail)
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   369
        except StopIteration:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   370
            self._bottomrev = self._inputhead
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   371
            self._inputhead = nullrev - 1
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   372
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   373
    def _scanparents(self, stoprev):
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   374
        """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
   375
        resolved"""
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
        # '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
   378
        # 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
   379
        # of computing the given subset.
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
        # For to-visit revisions, we keep track of
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   382
        # - the number of the unresolved paths: pendingcnt[rev],
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   383
        # - 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
   384
        # - 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
   385
        #
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   386
        # 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
   387
        # propagated to its parents accordingly.
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   388
        #
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   389
        # 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
   390
        # 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
   391
        # 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
   392
        # 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
   393
        # of merges between two revisions.
44592
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   394
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   395
        subset = self._subset
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   396
        tovisit = self._tovisit  # heap queue of [-rev]
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   397
        pendingcnt = self._pendingcnt  # {rev: count} for visited revisions
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   398
        pointers = self._pointers  # {rev: [{unresolved_rev: chain}, resolved]}
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   399
        parents = self._parents  # {rev: [(chain, rev)]}
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   400
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   401
        while tovisit or self._inputhead >= nullrev:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   402
            if pendingcnt.get(stoprev) == 0:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   403
                return
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
            # feed greater revisions from input set to queue
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   406
            if not tovisit:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   407
                heapq.heappush(tovisit, -self._inputhead)
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   408
                self._advanceinput()
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   409
            while self._inputhead >= -tovisit[0]:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   410
                heapq.heappush(tovisit, -self._inputhead)
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   411
                self._advanceinput()
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   412
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   413
            rev = -heapq.heappop(tovisit)
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   414
            if rev < self._bottomrev:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   415
                return
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   416
            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
   417
                continue  # already visited
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   418
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   419
            curactive = rev in subset
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   420
            pendingcnt.setdefault(rev, 0)  # mark as visited
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   421
            if curactive:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   422
                assert rev not in parents
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   423
                parents[rev] = []
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   424
            unresolved, resolved = pointers.pop(rev, ({}, set()))
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   425
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   426
            if curactive:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   427
                # reached to active rev, resolve pending descendants' parents
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   428
                for r, c in unresolved.items():
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   429
                    pendingcnt[r] -= 1
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   430
                    assert pendingcnt[r] >= 0
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   431
                    if r in resolved:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   432
                        continue  # eliminate redundant path
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   433
                    parents[r].append((c, rev))
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   434
                    # 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
   435
                    # 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
   436
                    # be concatenated later at a fork revision.
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   437
                    if pendingcnt[r] > 0:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   438
                        resolved.add(r)
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   439
                unresolved.clear()
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   440
                # occasionally clean resolved markers. otherwise the set
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   441
                # would grow indefinitely.
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   442
                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
   443
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   444
            parentrevs = self._parentrevs(rev)
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   445
            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
   446
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   447
            # set up or propagate tracking pointers if
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   448
            # - one of the parents is not active,
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   449
            # - or descendants' parents are unresolved.
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   450
            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
   451
                if len(parentrevs) <= 1:
25436f83fb95 dagop: simplify dict/set reuse condition in subsetparentswalker
Yuya Nishihara <yuya@tcha.org>
parents: 44592
diff changeset
   452
                    # can avoid copying the tracking pointer
25436f83fb95 dagop: simplify dict/set reuse condition in subsetparentswalker
Yuya Nishihara <yuya@tcha.org>
parents: 44592
diff changeset
   453
                    parentpointers = [(unresolved, resolved)]
25436f83fb95 dagop: simplify dict/set reuse condition in subsetparentswalker
Yuya Nishihara <yuya@tcha.org>
parents: 44592
diff changeset
   454
                else:
25436f83fb95 dagop: simplify dict/set reuse condition in subsetparentswalker
Yuya Nishihara <yuya@tcha.org>
parents: 44592
diff changeset
   455
                    parentpointers = [
25436f83fb95 dagop: simplify dict/set reuse condition in subsetparentswalker
Yuya Nishihara <yuya@tcha.org>
parents: 44592
diff changeset
   456
                        (unresolved, resolved),
25436f83fb95 dagop: simplify dict/set reuse condition in subsetparentswalker
Yuya Nishihara <yuya@tcha.org>
parents: 44592
diff changeset
   457
                        (unresolved.copy(), resolved.copy()),
25436f83fb95 dagop: simplify dict/set reuse condition in subsetparentswalker
Yuya Nishihara <yuya@tcha.org>
parents: 44592
diff changeset
   458
                    ]
44592
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   459
                    # '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
   460
                    # 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
   461
                    # p1/p2 code to the existing chains.
44592
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   462
                    for r in unresolved:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   463
                        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
   464
                        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
   465
                        parentpointers[1][0][r] += b'2'
44592
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   466
                for i, p in enumerate(parentrevs):
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   467
                    assert p < rev
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   468
                    heapq.heappush(tovisit, -p)
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   469
                    if p in pointers:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   470
                        # 'p' is a fork revision. concatenate tracking pointers
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   471
                        # and decrement the pending count accordingly.
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   472
                        knownunresolved, knownresolved = pointers[p]
44658
25436f83fb95 dagop: simplify dict/set reuse condition in subsetparentswalker
Yuya Nishihara <yuya@tcha.org>
parents: 44592
diff changeset
   473
                        unresolved, resolved = parentpointers[i]
44592
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   474
                        for r, c in unresolved.items():
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   475
                            if r in knownunresolved:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   476
                                # unresolved at both paths
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   477
                                pendingcnt[r] -= 1
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   478
                                assert pendingcnt[r] > 0
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   479
                                # take shorter chain
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   480
                                knownunresolved[r] = min(c, knownunresolved[r])
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   481
                            else:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   482
                                knownunresolved[r] = c
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   483
                        # simply propagate the 'resolved' set as deduplicating
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   484
                        # 'unresolved' here would be slightly complicated.
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   485
                        knownresolved.update(resolved)
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   486
                    else:
44658
25436f83fb95 dagop: simplify dict/set reuse condition in subsetparentswalker
Yuya Nishihara <yuya@tcha.org>
parents: 44592
diff changeset
   487
                        pointers[p] = parentpointers[i]
44592
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   488
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   489
            # 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
   490
            # '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
   491
            # '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
   492
            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
   493
            if curactive and bothparentsactive:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   494
                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
   495
                    c = chaincodes[i]
44592
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   496
                    parents[rev].append((c, p))
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   497
                    # 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
   498
                    # be fully resolved (i.e. pendingcnt[rev] == 0)
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   499
                assert pendingcnt[rev] == 0
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   500
            elif curactive:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   501
                for i, p in enumerate(parentrevs):
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   502
                    unresolved, resolved = pointers[p]
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   503
                    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
   504
                    c = chaincodes[i]
44592
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   505
                    if p in subset:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   506
                        parents[rev].append((c, p))
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   507
                        # mark 'rev' as resolved through this path
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   508
                        resolved.add(rev)
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   509
                    else:
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   510
                        pendingcnt[rev] += 1
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   511
                        unresolved[rev] = c
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   512
                assert 0 < pendingcnt[rev] <= 2
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   513
7cd5c0968139 templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents: 43077
diff changeset
   514
42446
055c3e2c44f0 revlog: speed up isancestor
Valentin Gatien-Baron <vgatien-baron@janestreet.com>
parents: 42445
diff changeset
   515
def _reachablerootspure(pfunc, minroot, roots, heads, includepath):
055c3e2c44f0 revlog: speed up isancestor
Valentin Gatien-Baron <vgatien-baron@janestreet.com>
parents: 42445
diff changeset
   516
    """See revlog.reachableroots"""
16862
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
   517
    if not roots:
26094
df41c7be16d6 reachableroots: construct and sort baseset in revset module
Yuya Nishihara <yuya@tcha.org>
parents: 26093
diff changeset
   518
        return []
26053
b68c9d232db6 reachableroots: use internal "revstates" array to test if rev is a root
Yuya Nishihara <yuya@tcha.org>
parents: 26006
diff changeset
   519
    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
   520
    visit = list(heads)
16862
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
   521
    reachable = set()
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
   522
    seen = {}
25566
15412bba5a68 revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25554
diff changeset
   523
    # 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
   524
    reached = reachable.add
15412bba5a68 revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25554
diff changeset
   525
    dovisit = visit.append
15412bba5a68 revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25554
diff changeset
   526
    nextvisit = visit.pop
16862
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
   527
    # 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
   528
    # sys.getrecursionlimit()
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
   529
    while visit:
25566
15412bba5a68 revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25554
diff changeset
   530
        rev = nextvisit()
16862
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
   531
        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
   532
            reached(rev)
26002
fd92bfbbe02d revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents: 26001
diff changeset
   533
            if not includepath:
fd92bfbbe02d revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents: 26001
diff changeset
   534
                continue
42446
055c3e2c44f0 revlog: speed up isancestor
Valentin Gatien-Baron <vgatien-baron@janestreet.com>
parents: 42445
diff changeset
   535
        parents = pfunc(rev)
16862
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
   536
        seen[rev] = parents
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
   537
        for parent in parents:
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
   538
            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
   539
                dovisit(parent)
16862
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
   540
    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
   541
        return baseset()
26002
fd92bfbbe02d revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents: 26001
diff changeset
   542
    if not includepath:
fd92bfbbe02d revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents: 26001
diff changeset
   543
        return reachable
16862
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
   544
    for rev in sorted(seen):
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
   545
        for parent in seen[rev]:
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
   546
            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
   547
                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
   548
    return reachable
16862
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
   549
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   550
26006
1ffd97cbf9a2 reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents: 26002
diff changeset
   551
def reachableroots(repo, roots, heads, includepath=False):
42446
055c3e2c44f0 revlog: speed up isancestor
Valentin Gatien-Baron <vgatien-baron@janestreet.com>
parents: 42445
diff changeset
   552
    """See revlog.reachableroots"""
26006
1ffd97cbf9a2 reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents: 26002
diff changeset
   553
    if not roots:
1ffd97cbf9a2 reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents: 26002
diff changeset
   554
        return baseset()
26093
204131131766 reachableroots: use smartset min
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 26091
diff changeset
   555
    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
   556
    roots = list(roots)
26006
1ffd97cbf9a2 reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents: 26002
diff changeset
   557
    heads = list(heads)
42446
055c3e2c44f0 revlog: speed up isancestor
Valentin Gatien-Baron <vgatien-baron@janestreet.com>
parents: 42445
diff changeset
   558
    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
   559
    revs = baseset(revs)
df41c7be16d6 reachableroots: construct and sort baseset in revset module
Yuya Nishihara <yuya@tcha.org>
parents: 26093
diff changeset
   560
    revs.sort()
df41c7be16d6 reachableroots: construct and sort baseset in revset module
Yuya Nishihara <yuya@tcha.org>
parents: 26093
diff changeset
   561
    return revs
26006
1ffd97cbf9a2 reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents: 26002
diff changeset
   562
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   563
32904
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   564
def _changesrange(fctx1, fctx2, linerange2, diffopts):
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   565
    """Return `(diffinrange, linerange1)` where `diffinrange` is True
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   566
    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
   567
    `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
   568
    """
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   569
    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
   570
    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
   571
    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
   572
    return diffinrange, linerange1
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   573
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   574
32904
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   575
def blockancestors(fctx, fromline, toline, followfirst=False):
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   576
    """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
   577
    `fromline`-`toline` range.
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   578
    """
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   579
    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
   580
    fctx = fctx.introfilectx()
32904
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   581
    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
   582
    while visit:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   583
        c, linerange2 = visit.pop(max(visit))
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   584
        pl = c.parents()
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   585
        if followfirst:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   586
            pl = pl[:1]
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   587
        if not pl:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   588
            # The block originates from the initial revision.
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   589
            yield c, linerange2
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   590
            continue
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   591
        inrange = False
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   592
        for p in pl:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   593
            inrangep, linerange1 = _changesrange(p, c, linerange2, diffopts)
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   594
            inrange = inrange or inrangep
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   595
            if linerange1[0] == linerange1[1]:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   596
                # 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
   597
                # 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
   598
                # branch.
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   599
                continue
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   600
            # 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
   601
            # _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
   602
            # (as srcrev) instead possibly topmost introrev.
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   603
            p._descendantrev = c.rev()
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   604
            visit[p.linkrev(), p.filenode()] = p, linerange1
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   605
        if inrange:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   606
            yield c, linerange2
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   607
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   608
32904
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   609
def blockdescendants(fctx, fromline, toline):
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   610
    """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
   611
    `fromline`-`toline` range.
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   612
    """
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   613
    # 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
   614
    # its parents.
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   615
    try:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   616
        c, linerange1 = next(blockancestors(fctx, fromline, toline))
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   617
    except StopIteration:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   618
        pass
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   619
    else:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   620
        if c == fctx:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   621
            yield c, linerange1
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   622
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   623
    diffopts = patch.diffopts(fctx._repo.ui)
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   624
    fl = fctx.filelog()
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   625
    seen = {fctx.filerev(): (fctx, (fromline, toline))}
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   626
    for i in fl.descendants([fctx.filerev()]):
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   627
        c = fctx.filectx(i)
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   628
        inrange = False
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   629
        for x in fl.parentrevs(i):
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   630
            try:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   631
                p, linerange2 = seen[x]
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   632
            except KeyError:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   633
                # nullrev or other branch
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   634
                continue
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   635
            inrangep, linerange1 = _changesrange(c, p, linerange2, diffopts)
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   636
            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
   637
            # 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
   638
            # 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
   639
            # 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
   640
            # information.
b2670290eab4 followlines: join merge parents line ranges in blockdescendants() (issue5595)
Denis Laxalde <denis.laxalde@logilab.fr>
parents: 33080
diff changeset
   641
            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
   642
                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
   643
                linerange1 = min(lbs), max(ubs)
32904
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   644
            seen[i] = c, linerange1
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   645
        if inrange:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   646
            yield c, linerange1
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
   647
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   648
36917
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   649
@attr.s(slots=True, frozen=True)
48946
642e31cb55f0 py3: use class X: instead of class X(object):
Gregory Szorc <gregory.szorc@gmail.com>
parents: 48875
diff changeset
   650
class annotateline:
36917
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   651
    fctx = attr.ib()
37065
b235bde38a83 annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents: 37064
diff changeset
   652
    lineno = attr.ib()
36917
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   653
    # 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
   654
    skip = attr.ib(default=False)
37066
b33b91ca2ec2 annotate: pack line content into annotateline object (API)
Yuya Nishihara <yuya@tcha.org>
parents: 37065
diff changeset
   655
    text = attr.ib(default=None)
36917
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   656
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   657
37064
434e520adb8c annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents: 36935
diff changeset
   658
@attr.s(slots=True, frozen=True)
48946
642e31cb55f0 py3: use class X: instead of class X(object):
Gregory Szorc <gregory.szorc@gmail.com>
parents: 48875
diff changeset
   659
class _annotatedfile:
37064
434e520adb8c annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents: 36935
diff changeset
   660
    # 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
   661
    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
   662
    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
   663
    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
   664
    # 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
   665
    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
   666
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   667
36919
8fba319750c2 dagop: move lines() out of annotate()
Yuya Nishihara <yuya@tcha.org>
parents: 36918
diff changeset
   668
def _countlines(text):
43077
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
   669
    if text.endswith(b"\n"):
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
   670
        return text.count(b"\n")
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
   671
    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
   672
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   673
37065
b235bde38a83 annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents: 37064
diff changeset
   674
def _decoratelines(text, fctx):
b235bde38a83 annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents: 37064
diff changeset
   675
    n = _countlines(text)
b235bde38a83 annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents: 37064
diff changeset
   676
    linenos = pycompat.rangelist(1, n + 1)
b235bde38a83 annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents: 37064
diff changeset
   677
    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
   678
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   679
36917
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   680
def _annotatepair(parents, childfctx, child, skipchild, diffopts):
45942
89a2afe31e82 formating: upgrade to black 20.8b1
Augie Fackler <raf@durin42.com>
parents: 45416
diff changeset
   681
    r"""
36917
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   682
    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
   683
    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
   684
    data.
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   685
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   686
    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
   687
    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
   688
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   689
    See test-annotate.py for unit tests.
45942
89a2afe31e82 formating: upgrade to black 20.8b1
Augie Fackler <raf@durin42.com>
parents: 45416
diff changeset
   690
    """
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   691
    pblocks = [
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   692
        (parent, mdiff.allblocks(parent.text, child.text, opts=diffopts))
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   693
        for parent in parents
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   694
    ]
36917
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   695
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   696
    if skipchild:
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   697
        # 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
   698
        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
   699
    # 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
   700
    # TODO: change this?
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   701
    for parent, blocks in pblocks:
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   702
        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
   703
            # 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
   704
            # belong to the child.
43077
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
   705
            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
   706
                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
   707
                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
   708
                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
   709
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   710
    if skipchild:
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   711
        # 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
   712
        # 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
   713
        # behavior.
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   714
        pblocks.reverse()
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   715
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   716
        # The heuristics are:
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   717
        # * 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
   718
        # 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
   719
        # * 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
   720
        #   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
   721
        # * 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
   722
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   723
        # 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
   724
        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
   725
        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
   726
            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
   727
                if a2 - a1 >= b2 - b1:
49284
d44e3c45f0e4 py3: replace `pycompat.xrange` by `range`
Manuel Jacob <me@manueljacob.de>
parents: 48946
diff changeset
   728
                    for bk in range(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
   729
                        if child.fctxs[bk] == childfctx:
36917
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   730
                            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
   731
                            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
   732
                            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
   733
                            child.skips[bk] = True
36917
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   734
                else:
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   735
                    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
   736
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   737
        # 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
   738
        # line.
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   739
        for parent, blocks in remaining:
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   740
            for a1, a2, b1, b2 in blocks:
49284
d44e3c45f0e4 py3: replace `pycompat.xrange` by `range`
Manuel Jacob <me@manueljacob.de>
parents: 48946
diff changeset
   741
                for bk in range(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
   742
                    if child.fctxs[bk] == childfctx:
36917
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   743
                        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
   744
                        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
   745
                        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
   746
                        child.skips[bk] = True
36917
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   747
    return child
7affcabf561e dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 35297
diff changeset
   748
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   749
37065
b235bde38a83 annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents: 37064
diff changeset
   750
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
   751
    """Core algorithm for filectx.annotate()
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   752
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   753
    `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
   754
    """
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   755
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   756
    # 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
   757
    # 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
   758
    # depth-first search.
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
    # 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
   761
    visit = [base]
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   762
    pcache = {}
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   763
    needed = {base: 1}
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   764
    while visit:
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   765
        f = visit.pop()
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   766
        if f in pcache:
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   767
            continue
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   768
        pl = parents(f)
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   769
        pcache[f] = pl
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   770
        for p in pl:
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   771
            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
   772
            if p not in pcache:
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   773
                visit.append(p)
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   774
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   775
    # 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
   776
    visit[:] = [base]
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   777
    hist = {}
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   778
    while visit:
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   779
        f = visit[-1]
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   780
        if f in hist:
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   781
            visit.pop()
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   782
            continue
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   783
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   784
        ready = True
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   785
        pl = pcache[f]
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   786
        for p in pl:
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   787
            if p not in hist:
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   788
                ready = False
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   789
                visit.append(p)
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   790
        if ready:
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   791
            visit.pop()
37065
b235bde38a83 annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents: 37064
diff changeset
   792
            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
   793
            skipchild = False
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   794
            if skiprevs is not None:
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   795
                skipchild = f._changeid in skiprevs
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   796
            curr = _annotatepair(
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   797
                [hist[p] for p in pl], f, curr, skipchild, diffopts
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   798
            )
36918
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   799
            for p in pl:
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   800
                if needed[p] == 1:
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   801
                    del hist[p]
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   802
                    del needed[p]
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   803
                else:
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   804
                    needed[p] -= 1
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   805
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   806
            hist[f] = curr
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   807
            del pcache[f]
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   808
37064
434e520adb8c annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents: 36935
diff changeset
   809
    a = hist[base]
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   810
    return [
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   811
        annotateline(*r)
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   812
        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
   813
    ]
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   814
36918
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents: 36917
diff changeset
   815
32903
27932a76a88d dagop: split module hosting DAG-related algorithms from revset
Yuya Nishihara <yuya@tcha.org>
parents: 32885
diff changeset
   816
def toposort(revs, parentsfunc, firstbranch=()):
29347
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   817
    """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
   818
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   819
    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
   820
    the number of parallel branches and their interleaving.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   821
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   822
    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
   823
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   824
      o  4
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
      o  1
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  3
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  2
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  0
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
    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
   835
    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
   836
    occur behind a merge.
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
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   839
    ### Quick summary of the algorithm
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   840
    #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   841
    # 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
   842
    # 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
   843
    # "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
   844
    # branches with interleaved revisions.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   845
    #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   846
    # During iteration revs are split into two groups:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   847
    # A) revision already emitted
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   848
    # 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
   849
    #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   850
    # for each REV, we do the following logic:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   851
    #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   852
    #   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
   853
    #   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
   854
    #   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
   855
    #   group first.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   856
    #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   857
    #   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
   858
    #   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
   859
    #   now awaiting for REV.parents() to be available.
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
    #   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
   862
    #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   863
    #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   864
    # 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
   865
    # puts it in group (A) from above).
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
    revs.sort(reverse=True)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   868
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   869
    # 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
   870
    # 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
   871
    # need to delay the revisions that reference them.
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
    # 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
   874
    # 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
   875
    # emitted.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   876
    unblocked = set(firstbranch)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   877
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   878
    # 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
   879
    #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   880
    #   (revs:    lists of revs waiting to be displayed,
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   881
    #    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
   882
    #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   883
    # 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
   884
    # 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
   885
    # 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
   886
    # 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
   887
    # 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
   888
    #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   889
    # 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
   890
    # 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
   891
    # 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
   892
    # 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
   893
    # 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
   894
    #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   895
    # 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
   896
    # 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
   897
    # '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
   898
    #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   899
    # 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
   900
    # 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
   901
    groups = [([], unblocked)]
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   902
    pendingheap = []
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   903
    pendingset = set()
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   904
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   905
    heapq.heapify(pendingheap)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   906
    heappop = heapq.heappop
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   907
    heappush = heapq.heappush
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   908
    for currentrev in revs:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   909
        # 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
   910
        if currentrev not in pendingset:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   911
            heappush(pendingheap, -currentrev)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   912
            pendingset.add(currentrev)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   913
        # 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
   914
        # processed.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   915
        rev = None
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   916
        while rev != currentrev:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   917
            rev = -heappop(pendingheap)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   918
            pendingset.remove(rev)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   919
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   920
            # 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
   921
            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
   922
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   923
            if matching:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   924
                # 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
   925
                # on the same revision.
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
                # 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
   928
                # observed. For example, given two groups:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   929
                #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   930
                # revs [5, 4] waiting for 1
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   931
                # revs [3, 2] waiting for 1
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   932
                #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   933
                # 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
   934
                # 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
   935
                # 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
   936
                # 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
   937
                # 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
   938
                #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   939
                # 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
   940
                # 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
   941
                # 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
   942
                # 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
   943
                targetidx = matching.pop(0)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   944
                trevs, tparents = groups[targetidx]
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   945
                for i in matching:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   946
                    gr = groups[i]
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   947
                    trevs.extend(gr[0])
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   948
                    tparents |= gr[1]
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   949
                # 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
   950
                # (starting from the last subgroup for performance and
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   951
                # sanity reasons)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   952
                for i in reversed(matching):
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   953
                    del groups[i]
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   954
            else:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   955
                # 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
   956
                targetidx = len(groups)
32291
bd872f64a8ba cleanup: use set literals
Martin von Zweigbergk <martinvonz@google.com>
parents: 32085
diff changeset
   957
                groups.append(([], {rev}))
29347
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   958
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   959
            gr = groups[targetidx]
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   960
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   961
            # 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
   962
            # 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
   963
            # that relied on this rev must precede it.
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 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
   966
            # new nodes.
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
   967
            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
   968
                gr[0].append(rev)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   969
            gr[1].remove(rev)
46113
59fa3890d40a node: import symbols explicitly
Joerg Sonnenberger <joerg@bec.de>
parents: 45942
diff changeset
   970
            parents = [p for p in parentsfunc(rev) if p > nullrev]
29347
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   971
            gr[1].update(parents)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   972
            for p in parents:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   973
                if p not in pendingset:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   974
                    pendingset.add(p)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   975
                    heappush(pendingheap, -p)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   976
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   977
            # Look for a subgroup to display
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   978
            #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   979
            # 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
   980
            # 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
   981
            # 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
   982
            # 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
   983
            # subgroup. The heuristic could probably be better.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   984
            #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   985
            # 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
   986
            # 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
   987
            # well.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   988
            if not unblocked:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   989
                if len(groups) > 1:  # display other subset
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   990
                    targetidx = 1
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   991
                    gr = groups[1]
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   992
            elif not gr[1] & unblocked:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   993
                gr = None
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   994
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   995
            if gr is not None:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   996
                # 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
   997
                # subgroup
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   998
                unblocked |= gr[1]
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
   999
                # output all revisions in the subgroup
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
  1000
                for r in gr[0]:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
  1001
                    yield r
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
  1002
                # delete the subgroup that you just output
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
  1003
                # 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
  1004
                if targetidx:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
  1005
                    del groups[targetidx]
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
  1006
                else:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
  1007
                    gr[0][:] = []
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
  1008
    # 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
  1009
    # iterate over
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
  1010
    for g in groups:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
  1011
        for r in g[0]:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
  1012
            yield r
39179
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38783
diff changeset
  1013
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
  1014
39179
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38783
diff changeset
  1015
def headrevs(revs, parentsfn):
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38783
diff changeset
  1016
    """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
  1017
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38783
diff changeset
  1018
    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
  1019
    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
  1020
    including nullrev.
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
    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
  1023
    subset.
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38783
diff changeset
  1024
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38783
diff changeset
  1025
    ``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
  1026
    the input set.
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38783
diff changeset
  1027
    """
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38783
diff changeset
  1028
    headrevs = set(revs)
46113
59fa3890d40a node: import symbols explicitly
Joerg Sonnenberger <joerg@bec.de>
parents: 45942
diff changeset
  1029
    parents = {nullrev}
41277
61f9ef23a12f dagop: minor python optimization to `headrevs`
Boris Feld <boris.feld@octobus.net>
parents: 40000
diff changeset
  1030
    up = parents.update
39179
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
    for rev in revs:
41277
61f9ef23a12f dagop: minor python optimization to `headrevs`
Boris Feld <boris.feld@octobus.net>
parents: 40000
diff changeset
  1033
        up(parentsfn(rev))
61f9ef23a12f dagop: minor python optimization to `headrevs`
Boris Feld <boris.feld@octobus.net>
parents: 40000
diff changeset
  1034
    headrevs.difference_update(parents)
39179
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38783
diff changeset
  1035
    return headrevs
39181
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1036
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
  1037
51395
a0d88b021a98 unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents: 49284
diff changeset
  1038
def headrevsdiff(parentsfn, start, stop):
a0d88b021a98 unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents: 49284
diff changeset
  1039
    """Compute how the set of heads changed between
a0d88b021a98 unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents: 49284
diff changeset
  1040
    revisions `start-1` and `stop-1`.
a0d88b021a98 unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents: 49284
diff changeset
  1041
    """
a0d88b021a98 unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents: 49284
diff changeset
  1042
    parents = set()
a0d88b021a98 unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents: 49284
diff changeset
  1043
a0d88b021a98 unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents: 49284
diff changeset
  1044
    heads_added = set()
a0d88b021a98 unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents: 49284
diff changeset
  1045
    heads_removed = set()
a0d88b021a98 unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents: 49284
diff changeset
  1046
a0d88b021a98 unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents: 49284
diff changeset
  1047
    for rev in range(stop - 1, start - 1, -1):
a0d88b021a98 unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents: 49284
diff changeset
  1048
        if rev in parents:
a0d88b021a98 unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents: 49284
diff changeset
  1049
            parents.remove(rev)
a0d88b021a98 unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents: 49284
diff changeset
  1050
        else:
a0d88b021a98 unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents: 49284
diff changeset
  1051
            heads_added.add(rev)
a0d88b021a98 unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents: 49284
diff changeset
  1052
        for p in parentsfn(rev):
a0d88b021a98 unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents: 49284
diff changeset
  1053
            parents.add(p)
a0d88b021a98 unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents: 49284
diff changeset
  1054
a0d88b021a98 unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents: 49284
diff changeset
  1055
    # now `parents` is the collection of candidate removed heads
a0d88b021a98 unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents: 49284
diff changeset
  1056
    rev = start - 1
a0d88b021a98 unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents: 49284
diff changeset
  1057
    while parents:
a0d88b021a98 unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents: 49284
diff changeset
  1058
        if rev in parents:
a0d88b021a98 unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents: 49284
diff changeset
  1059
            heads_removed.add(rev)
a0d88b021a98 unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents: 49284
diff changeset
  1060
            parents.remove(rev)
a0d88b021a98 unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents: 49284
diff changeset
  1061
a0d88b021a98 unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents: 49284
diff changeset
  1062
        for p in parentsfn(rev):
a0d88b021a98 unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents: 49284
diff changeset
  1063
            parents.discard(p)
a0d88b021a98 unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents: 49284
diff changeset
  1064
        rev = rev - 1
a0d88b021a98 unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents: 49284
diff changeset
  1065
a0d88b021a98 unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents: 49284
diff changeset
  1066
    return (heads_removed, heads_added)
a0d88b021a98 unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents: 49284
diff changeset
  1067
a0d88b021a98 unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents: 49284
diff changeset
  1068
40000
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1069
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
  1070
    """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
  1071
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1072
    ``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
  1073
    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
  1074
    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
  1075
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1076
    ``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
  1077
    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
  1078
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1079
    ``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
  1080
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1081
    ``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
  1082
    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
  1083
    collection will be heads.
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1084
    """
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1085
    if startrev is None:
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1086
        startrev = nullrev
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1087
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1088
    stoprevs = set(stoprevs or [])
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1089
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1090
    reachable = {startrev}
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1091
    heads = {startrev}
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1092
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1093
    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
  1094
        for prev in parentrevsfn(rev):
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1095
            if prev in reachable:
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1096
                if rev not in stoprevs:
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1097
                    reachable.add(rev)
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1098
                heads.add(rev)
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1099
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1100
            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
  1101
                heads.remove(prev)
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1102
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1103
    return heads
8af835af0a85 dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39999
diff changeset
  1104
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42446
diff changeset
  1105
39181
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1106
def linearize(revs, parentsfn):
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1107
    """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
  1108
39607
5362c96f2feb dagop: fix typo spotted while doing unrelated investigation
Augie Fackler <augie@google.com>
parents: 39181
diff changeset
  1109
    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
  1110
    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
  1111
    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
  1112
    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
  1113
    itself to the output list.
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1114
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1115
    Returns a list of revision numbers.
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1116
    """
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1117
    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
  1118
    finished = set()
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1119
    result = []
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1120
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1121
    while visit:
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1122
        rev = visit.pop()
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1123
        if rev < 0:
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1124
            rev = -rev - 1
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1125
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1126
            if rev not in finished:
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1127
                result.append(rev)
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1128
                finished.add(rev)
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1129
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1130
        else:
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1131
            visit.append(-rev - 1)
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1132
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1133
            for prev in parentsfn(rev):
46113
59fa3890d40a node: import symbols explicitly
Joerg Sonnenberger <joerg@bec.de>
parents: 45942
diff changeset
  1134
                if prev == nullrev or prev not in revs or prev in finished:
39181
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1135
                    continue
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1136
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1137
                visit.append(prev)
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1138
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1139
    assert len(result) == len(revs)
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1140
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39179
diff changeset
  1141
    return result