mercurial/ancestor.py
author Pierre-Yves David <pierre-yves.david@octobus.net>
Tue, 13 Apr 2021 15:13:20 +0200
changeset 46914 50b79f8b802d
parent 46819 d4ba4d51f85f
child 48875 6000f5b25c9b
permissions -rw-r--r--
outgoing: move filtering logic in its own function This move code dedicated to a single purpose together and make the main code simpler. Right when we are getting ready to make it more complex :-D Differential Revision: https://phab.mercurial-scm.org/D10382
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     1
# ancestor.py - generic DAG ancestor algorithm for mercurial
b1db258e875c Abstract ancestor algorithm into generic function
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: 45942
diff changeset
     3
# Copyright 2006 Olivia Mackall <olivia@selenic.com>
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     4
#
8225
46293a0c7e9f updated license to be explicit about GPL version 2
Martin Geisler <mg@lazybytes.net>
parents: 7882
diff changeset
     5
# This software may be used and distributed according to the terms of the
10263
25e572394f5c Update license to GPLv2+
Matt Mackall <mpm@selenic.com>
parents: 8465
diff changeset
     6
# GNU General Public License version 2 or any later version.
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     7
25915
7ef98b38163f ancestor: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25639
diff changeset
     8
from __future__ import absolute_import
7ef98b38163f ancestor: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25639
diff changeset
     9
20034
1e5b38a919dd cleanup: move stdlib imports to their own import statement
Augie Fackler <raf@durin42.com>
parents: 18987
diff changeset
    10
import heapq
25915
7ef98b38163f ancestor: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25639
diff changeset
    11
7ef98b38163f ancestor: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25639
diff changeset
    12
from .node import nullrev
38783
e7aa113b14f7 global: use pycompat.xrange()
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38595
diff changeset
    13
from . import (
41244
4856c9b8cbaf ancestor: incrementalmissingancestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents: 40300
diff changeset
    14
    dagop,
40298
9cadb0f5f227 rust: hooking into Python code
Georges Racinet <gracinet@anybox.fr>
parents: 39581
diff changeset
    15
    policy,
38783
e7aa113b14f7 global: use pycompat.xrange()
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38595
diff changeset
    16
    pycompat,
e7aa113b14f7 global: use pycompat.xrange()
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38595
diff changeset
    17
)
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    18
43506
9f70512ae2cf cleanup: remove pointless r-prefixes on single-quoted strings
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
    19
parsers = policy.importmod('parsers')
40298
9cadb0f5f227 rust: hooking into Python code
Georges Racinet <gracinet@anybox.fr>
parents: 39581
diff changeset
    20
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 41244
diff changeset
    21
21101
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    22
def commonancestorsheads(pfunc, *nodes):
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    23
    """Returns a set with the heads of all common ancestors of all nodes,
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    24
    heads(::nodes[0] and ::nodes[1] and ...) .
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    25
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    26
    pfunc must return a list of parent vertices for a given vertex.
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    27
    """
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    28
    if not isinstance(nodes, set):
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    29
        nodes = set(nodes)
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    30
    if nullrev in nodes:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    31
        return set()
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    32
    if len(nodes) <= 1:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    33
        return nodes
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    34
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    35
    allseen = (1 << len(nodes)) - 1
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    36
    seen = [0] * (max(nodes) + 1)
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    37
    for i, n in enumerate(nodes):
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    38
        seen[n] = 1 << i
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    39
    poison = 1 << (i + 1)
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    40
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    41
    gca = set()
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    42
    interesting = len(nodes)
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    43
    nv = len(seen) - 1
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    44
    while nv >= 0 and interesting:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    45
        v = nv
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    46
        nv -= 1
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    47
        if not seen[v]:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    48
            continue
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    49
        sv = seen[v]
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    50
        if sv < poison:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    51
            interesting -= 1
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    52
            if sv == allseen:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    53
                gca.add(v)
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    54
                sv |= poison
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    55
                if v in nodes:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    56
                    # history is linear
32291
bd872f64a8ba cleanup: use set literals
Martin von Zweigbergk <martinvonz@google.com>
parents: 31476
diff changeset
    57
                    return {v}
21101
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    58
        if sv < poison:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    59
            for p in pfunc(v):
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    60
                sp = seen[p]
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    61
                if p == nullrev:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    62
                    continue
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    63
                if sp == 0:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    64
                    seen[p] = sv
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    65
                    interesting += 1
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    66
                elif sp != sv:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    67
                    seen[p] |= sv
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    68
        else:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    69
            for p in pfunc(v):
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    70
                if p == nullrev:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    71
                    continue
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    72
                sp = seen[p]
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    73
                if sp and sp < poison:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    74
                    interesting -= 1
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    75
                seen[p] = sv
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    76
    return gca
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    77
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 41244
diff changeset
    78
18986
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    79
def ancestors(pfunc, *orignodes):
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    80
    """
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    81
    Returns the common ancestors of a and b that are furthest from a
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    82
    root (as measured by longest path).
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    83
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    84
    pfunc must return a list of parent vertices for a given vertex.
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    85
    """
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 41244
diff changeset
    86
18986
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    87
    def deepest(nodes):
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    88
        interesting = {}
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    89
        count = max(nodes) + 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    90
        depth = [0] * count
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    91
        seen = [0] * count
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    92
        mapping = []
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    93
        for (i, n) in enumerate(sorted(nodes)):
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    94
            depth[n] = 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    95
            b = 1 << i
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    96
            seen[n] = b
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    97
            interesting[b] = 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    98
            mapping.append((b, n))
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    99
        nv = count - 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   100
        while nv >= 0 and len(interesting) > 1:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   101
            v = nv
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   102
            nv -= 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   103
            dv = depth[v]
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   104
            if dv == 0:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   105
                continue
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   106
            sv = seen[v]
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   107
            for p in pfunc(v):
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   108
                if p == nullrev:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   109
                    continue
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   110
                dp = depth[p]
43969
68b09ebf1c13 ancestor: drop another unused variable assignment
Matt Harbison <matt_harbison@yahoo.com>
parents: 43968
diff changeset
   111
                sp = seen[p]
18986
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   112
                if dp <= dv:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   113
                    depth[p] = dv + 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   114
                    if sp != sv:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   115
                        interesting[sv] += 1
43969
68b09ebf1c13 ancestor: drop another unused variable assignment
Matt Harbison <matt_harbison@yahoo.com>
parents: 43968
diff changeset
   116
                        seen[p] = sv
18986
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   117
                        if sp:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   118
                            interesting[sp] -= 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   119
                            if interesting[sp] == 0:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   120
                                del interesting[sp]
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   121
                elif dv == dp - 1:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   122
                    nsp = sp | sv
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   123
                    if nsp == sp:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   124
                        continue
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   125
                    seen[p] = nsp
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   126
                    interesting.setdefault(nsp, 0)
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   127
                    interesting[nsp] += 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   128
                    interesting[sp] -= 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   129
                    if interesting[sp] == 0:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   130
                        del interesting[sp]
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   131
            interesting[sv] -= 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   132
            if interesting[sv] == 0:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   133
                del interesting[sv]
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   134
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   135
        if len(interesting) != 1:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   136
            return []
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   137
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   138
        k = 0
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   139
        for i in interesting:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   140
            k |= i
44452
9d2b2df2c2ba cleanup: run pyupgrade on our source tree to clean up varying things
Augie Fackler <augie@google.com>
parents: 43969
diff changeset
   141
        return {n for (i, n) in mapping if k & i}
18986
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   142
21101
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
   143
    gca = commonancestorsheads(pfunc, *orignodes)
18986
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   144
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   145
    if len(gca) <= 1:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   146
        return gca
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   147
    return deepest(gca)
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   148
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 41244
diff changeset
   149
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   150
class incrementalmissingancestors(object):
45942
89a2afe31e82 formating: upgrade to black 20.8b1
Augie Fackler <raf@durin42.com>
parents: 44491
diff changeset
   151
    """persistent state used to calculate missing ancestors incrementally
17970
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   152
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   153
    Although similar in spirit to lazyancestors below, this is a separate class
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   154
    because trying to support contains and missingancestors operations with the
45942
89a2afe31e82 formating: upgrade to black 20.8b1
Augie Fackler <raf@durin42.com>
parents: 44491
diff changeset
   155
    same internal data structures adds needless complexity."""
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 41244
diff changeset
   156
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   157
    def __init__(self, pfunc, bases):
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   158
        self.bases = set(bases)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   159
        if not self.bases:
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   160
            self.bases.add(nullrev)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   161
        self.pfunc = pfunc
17970
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   162
23340
83225aff0265 ancestor: add a way to test whether a missing ancestor object has bases
Siddharth Agarwal <sid0@fb.com>
parents: 23339
diff changeset
   163
    def hasbases(self):
83225aff0265 ancestor: add a way to test whether a missing ancestor object has bases
Siddharth Agarwal <sid0@fb.com>
parents: 23339
diff changeset
   164
        '''whether the common set has any non-trivial bases'''
32291
bd872f64a8ba cleanup: use set literals
Martin von Zweigbergk <martinvonz@google.com>
parents: 31476
diff changeset
   165
        return self.bases and self.bases != {nullrev}
23340
83225aff0265 ancestor: add a way to test whether a missing ancestor object has bases
Siddharth Agarwal <sid0@fb.com>
parents: 23339
diff changeset
   166
23341
bcc3012f8477 ancestor: add a way to add to bases of a missing ancestor object
Siddharth Agarwal <sid0@fb.com>
parents: 23340
diff changeset
   167
    def addbases(self, newbases):
bcc3012f8477 ancestor: add a way to add to bases of a missing ancestor object
Siddharth Agarwal <sid0@fb.com>
parents: 23340
diff changeset
   168
        '''grow the ancestor set by adding new bases'''
bcc3012f8477 ancestor: add a way to add to bases of a missing ancestor object
Siddharth Agarwal <sid0@fb.com>
parents: 23340
diff changeset
   169
        self.bases.update(newbases)
bcc3012f8477 ancestor: add a way to add to bases of a missing ancestor object
Siddharth Agarwal <sid0@fb.com>
parents: 23340
diff changeset
   170
41244
4856c9b8cbaf ancestor: incrementalmissingancestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents: 40300
diff changeset
   171
    def basesheads(self):
4856c9b8cbaf ancestor: incrementalmissingancestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents: 40300
diff changeset
   172
        return dagop.headrevs(self.bases, self.pfunc)
4856c9b8cbaf ancestor: incrementalmissingancestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents: 40300
diff changeset
   173
23342
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   174
    def removeancestorsfrom(self, revs):
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   175
        '''remove all ancestors of bases from the set revs (in place)'''
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   176
        bases = self.bases
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   177
        pfunc = self.pfunc
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   178
        revs.difference_update(bases)
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   179
        # nullrev is always an ancestor
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   180
        revs.discard(nullrev)
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   181
        if not revs:
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   182
            return
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   183
        # anything in revs > start is definitely not an ancestor of bases
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   184
        # revs <= start needs to be investigated
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   185
        start = max(bases)
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   186
        keepcount = sum(1 for r in revs if r > start)
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   187
        if len(revs) == keepcount:
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   188
            # no revs to consider
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   189
            return
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   190
38783
e7aa113b14f7 global: use pycompat.xrange()
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38595
diff changeset
   191
        for curr in pycompat.xrange(start, min(revs) - 1, -1):
23342
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   192
            if curr not in bases:
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   193
                continue
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   194
            revs.discard(curr)
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   195
            bases.update(pfunc(curr))
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   196
            if len(revs) == keepcount:
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   197
                # no more potential revs to discard
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   198
                break
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   199
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   200
    def missingancestors(self, revs):
45942
89a2afe31e82 formating: upgrade to black 20.8b1
Augie Fackler <raf@durin42.com>
parents: 44491
diff changeset
   201
        """return all the ancestors of revs that are not ancestors of self.bases
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   202
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   203
        This may include elements from revs.
17970
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   204
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   205
        Equivalent to the revset (::revs - ::self.bases). Revs are returned in
45942
89a2afe31e82 formating: upgrade to black 20.8b1
Augie Fackler <raf@durin42.com>
parents: 44491
diff changeset
   206
        revision number order, which is a topological order."""
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   207
        revsvisit = set(revs)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   208
        basesvisit = self.bases
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   209
        pfunc = self.pfunc
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   210
        bothvisit = revsvisit.intersection(basesvisit)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   211
        revsvisit.difference_update(bothvisit)
17970
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   212
        if not revsvisit:
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   213
            return []
17970
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   214
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   215
        start = max(max(revsvisit), max(basesvisit))
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   216
        # At this point, we hold the invariants that:
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   217
        # - revsvisit is the set of nodes we know are an ancestor of at least
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   218
        #   one of the nodes in revs
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   219
        # - basesvisit is the same for bases
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   220
        # - bothvisit is the set of nodes we know are ancestors of at least one
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   221
        #   of the nodes in revs and one of the nodes in bases. bothvisit and
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   222
        #   revsvisit are mutually exclusive, but bothvisit is a subset of
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   223
        #   basesvisit.
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   224
        # Now we walk down in reverse topo order, adding parents of nodes
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   225
        # already visited to the sets while maintaining the invariants. When a
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   226
        # node is found in both revsvisit and basesvisit, it is removed from
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   227
        # revsvisit and added to bothvisit. When revsvisit becomes empty, there
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   228
        # are no more ancestors of revs that aren't also ancestors of bases, so
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   229
        # exit.
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   230
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   231
        missing = []
38783
e7aa113b14f7 global: use pycompat.xrange()
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38595
diff changeset
   232
        for curr in pycompat.xrange(start, nullrev, -1):
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   233
            if not revsvisit:
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   234
                break
17970
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   235
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   236
            if curr in bothvisit:
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   237
                bothvisit.remove(curr)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   238
                # curr's parents might have made it into revsvisit through
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   239
                # another path
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   240
                for p in pfunc(curr):
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   241
                    revsvisit.discard(p)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   242
                    basesvisit.add(p)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   243
                    bothvisit.add(p)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   244
                continue
17970
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   245
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   246
            if curr in revsvisit:
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   247
                missing.append(curr)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   248
                revsvisit.remove(curr)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   249
                thisvisit = revsvisit
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   250
                othervisit = basesvisit
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   251
            elif curr in basesvisit:
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   252
                thisvisit = basesvisit
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   253
                othervisit = revsvisit
17970
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   254
            else:
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   255
                # not an ancestor of revs or bases: ignore
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   256
                continue
17970
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   257
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   258
            for p in pfunc(curr):
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   259
                if p == nullrev:
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   260
                    pass
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   261
                elif p in othervisit or p in bothvisit:
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   262
                    # p is implicitly in thisvisit. This means p is or should be
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   263
                    # in bothvisit
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   264
                    revsvisit.discard(p)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   265
                    basesvisit.add(p)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   266
                    bothvisit.add(p)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   267
                else:
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   268
                    # visit later
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   269
                    thisvisit.add(p)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   270
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   271
        missing.reverse()
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   272
        return missing
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   273
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 41244
diff changeset
   274
39481
b6a0e06b0f7d lazyancestors: extract __iter__ to free function
Martin von Zweigbergk <martinvonz@google.com>
parents: 39477
diff changeset
   275
# Extracted from lazyancestors.__iter__ to avoid a reference cycle
b6a0e06b0f7d lazyancestors: extract __iter__ to free function
Martin von Zweigbergk <martinvonz@google.com>
parents: 39477
diff changeset
   276
def _lazyancestorsiter(parentrevs, initrevs, stoprev, inclusive):
b6a0e06b0f7d lazyancestors: extract __iter__ to free function
Martin von Zweigbergk <martinvonz@google.com>
parents: 39477
diff changeset
   277
    seen = {nullrev}
39537
ca9983c35d89 ancestor: rename local aliases of heapq functions in _lazyancestorsiter()
Yuya Nishihara <yuya@tcha.org>
parents: 39536
diff changeset
   278
    heappush = heapq.heappush
ca9983c35d89 ancestor: rename local aliases of heapq functions in _lazyancestorsiter()
Yuya Nishihara <yuya@tcha.org>
parents: 39536
diff changeset
   279
    heappop = heapq.heappop
39538
238a1480d7ad ancestor: use heapreplace() in place of heappop/heappush()
Yuya Nishihara <yuya@tcha.org>
parents: 39537
diff changeset
   280
    heapreplace = heapq.heapreplace
39481
b6a0e06b0f7d lazyancestors: extract __iter__ to free function
Martin von Zweigbergk <martinvonz@google.com>
parents: 39477
diff changeset
   281
    see = seen.add
b6a0e06b0f7d lazyancestors: extract __iter__ to free function
Martin von Zweigbergk <martinvonz@google.com>
parents: 39477
diff changeset
   282
b6a0e06b0f7d lazyancestors: extract __iter__ to free function
Martin von Zweigbergk <martinvonz@google.com>
parents: 39477
diff changeset
   283
    if inclusive:
39533
f6bcb4f9cd3c ancestor: remove alias of initrevs from _lazyancestorsiter()
Yuya Nishihara <yuya@tcha.org>
parents: 39482
diff changeset
   284
        visit = [-r for r in initrevs]
f6bcb4f9cd3c ancestor: remove alias of initrevs from _lazyancestorsiter()
Yuya Nishihara <yuya@tcha.org>
parents: 39482
diff changeset
   285
        seen.update(initrevs)
39481
b6a0e06b0f7d lazyancestors: extract __iter__ to free function
Martin von Zweigbergk <martinvonz@google.com>
parents: 39477
diff changeset
   286
        heapq.heapify(visit)
b6a0e06b0f7d lazyancestors: extract __iter__ to free function
Martin von Zweigbergk <martinvonz@google.com>
parents: 39477
diff changeset
   287
    else:
b6a0e06b0f7d lazyancestors: extract __iter__ to free function
Martin von Zweigbergk <martinvonz@google.com>
parents: 39477
diff changeset
   288
        visit = []
b6a0e06b0f7d lazyancestors: extract __iter__ to free function
Martin von Zweigbergk <martinvonz@google.com>
parents: 39477
diff changeset
   289
        heapq.heapify(visit)
39533
f6bcb4f9cd3c ancestor: remove alias of initrevs from _lazyancestorsiter()
Yuya Nishihara <yuya@tcha.org>
parents: 39482
diff changeset
   290
        for r in initrevs:
39535
b9ee9c2e10dd ancestor: unroll loop of parents in _lazyancestorsiter()
Yuya Nishihara <yuya@tcha.org>
parents: 39534
diff changeset
   291
            p1, p2 = parentrevs(r)
b9ee9c2e10dd ancestor: unroll loop of parents in _lazyancestorsiter()
Yuya Nishihara <yuya@tcha.org>
parents: 39534
diff changeset
   292
            if p1 not in seen:
39537
ca9983c35d89 ancestor: rename local aliases of heapq functions in _lazyancestorsiter()
Yuya Nishihara <yuya@tcha.org>
parents: 39536
diff changeset
   293
                heappush(visit, -p1)
39535
b9ee9c2e10dd ancestor: unroll loop of parents in _lazyancestorsiter()
Yuya Nishihara <yuya@tcha.org>
parents: 39534
diff changeset
   294
                see(p1)
b9ee9c2e10dd ancestor: unroll loop of parents in _lazyancestorsiter()
Yuya Nishihara <yuya@tcha.org>
parents: 39534
diff changeset
   295
            if p2 not in seen:
39537
ca9983c35d89 ancestor: rename local aliases of heapq functions in _lazyancestorsiter()
Yuya Nishihara <yuya@tcha.org>
parents: 39536
diff changeset
   296
                heappush(visit, -p2)
39535
b9ee9c2e10dd ancestor: unroll loop of parents in _lazyancestorsiter()
Yuya Nishihara <yuya@tcha.org>
parents: 39534
diff changeset
   297
                see(p2)
39481
b6a0e06b0f7d lazyancestors: extract __iter__ to free function
Martin von Zweigbergk <martinvonz@google.com>
parents: 39477
diff changeset
   298
b6a0e06b0f7d lazyancestors: extract __iter__ to free function
Martin von Zweigbergk <martinvonz@google.com>
parents: 39477
diff changeset
   299
    while visit:
39536
bdb177923291 ancestor: optimize _lazyancestorsiter() for contiguous chains
Yuya Nishihara <yuya@tcha.org>
parents: 39535
diff changeset
   300
        current = -visit[0]
39534
fd9029d36c41 ancestor: return early from _lazyancestorsiter() when reached to stoprev
Yuya Nishihara <yuya@tcha.org>
parents: 39533
diff changeset
   301
        if current < stoprev:
fd9029d36c41 ancestor: return early from _lazyancestorsiter() when reached to stoprev
Yuya Nishihara <yuya@tcha.org>
parents: 39533
diff changeset
   302
            break
fd9029d36c41 ancestor: return early from _lazyancestorsiter() when reached to stoprev
Yuya Nishihara <yuya@tcha.org>
parents: 39533
diff changeset
   303
        yield current
39536
bdb177923291 ancestor: optimize _lazyancestorsiter() for contiguous chains
Yuya Nishihara <yuya@tcha.org>
parents: 39535
diff changeset
   304
        # optimize out heapq operation if p1 is known to be the next highest
bdb177923291 ancestor: optimize _lazyancestorsiter() for contiguous chains
Yuya Nishihara <yuya@tcha.org>
parents: 39535
diff changeset
   305
        # revision, which is quite common in linear history.
39535
b9ee9c2e10dd ancestor: unroll loop of parents in _lazyancestorsiter()
Yuya Nishihara <yuya@tcha.org>
parents: 39534
diff changeset
   306
        p1, p2 = parentrevs(current)
b9ee9c2e10dd ancestor: unroll loop of parents in _lazyancestorsiter()
Yuya Nishihara <yuya@tcha.org>
parents: 39534
diff changeset
   307
        if p1 not in seen:
39536
bdb177923291 ancestor: optimize _lazyancestorsiter() for contiguous chains
Yuya Nishihara <yuya@tcha.org>
parents: 39535
diff changeset
   308
            if current - p1 == 1:
bdb177923291 ancestor: optimize _lazyancestorsiter() for contiguous chains
Yuya Nishihara <yuya@tcha.org>
parents: 39535
diff changeset
   309
                visit[0] = -p1
bdb177923291 ancestor: optimize _lazyancestorsiter() for contiguous chains
Yuya Nishihara <yuya@tcha.org>
parents: 39535
diff changeset
   310
            else:
39538
238a1480d7ad ancestor: use heapreplace() in place of heappop/heappush()
Yuya Nishihara <yuya@tcha.org>
parents: 39537
diff changeset
   311
                heapreplace(visit, -p1)
39535
b9ee9c2e10dd ancestor: unroll loop of parents in _lazyancestorsiter()
Yuya Nishihara <yuya@tcha.org>
parents: 39534
diff changeset
   312
            see(p1)
39536
bdb177923291 ancestor: optimize _lazyancestorsiter() for contiguous chains
Yuya Nishihara <yuya@tcha.org>
parents: 39535
diff changeset
   313
        else:
39537
ca9983c35d89 ancestor: rename local aliases of heapq functions in _lazyancestorsiter()
Yuya Nishihara <yuya@tcha.org>
parents: 39536
diff changeset
   314
            heappop(visit)
39535
b9ee9c2e10dd ancestor: unroll loop of parents in _lazyancestorsiter()
Yuya Nishihara <yuya@tcha.org>
parents: 39534
diff changeset
   315
        if p2 not in seen:
39537
ca9983c35d89 ancestor: rename local aliases of heapq functions in _lazyancestorsiter()
Yuya Nishihara <yuya@tcha.org>
parents: 39536
diff changeset
   316
            heappush(visit, -p2)
39535
b9ee9c2e10dd ancestor: unroll loop of parents in _lazyancestorsiter()
Yuya Nishihara <yuya@tcha.org>
parents: 39534
diff changeset
   317
            see(p2)
39481
b6a0e06b0f7d lazyancestors: extract __iter__ to free function
Martin von Zweigbergk <martinvonz@google.com>
parents: 39477
diff changeset
   318
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 41244
diff changeset
   319
18090
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   320
class lazyancestors(object):
23328
3a7d9c0c57a5 ancestor.lazyancestors: take parentrevs function rather than changelog
Siddharth Agarwal <sid0@fb.com>
parents: 22225
diff changeset
   321
    def __init__(self, pfunc, revs, stoprev=0, inclusive=False):
18090
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   322
        """Create a new object generating ancestors for the given revs. Does
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   323
        not generate revs lower than stoprev.
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   324
18091
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   325
        This is computed lazily starting from revs. The object supports
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   326
        iteration and membership.
18090
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   327
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   328
        cl should be a changelog and revs should be an iterable. inclusive is
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   329
        a boolean that indicates whether revs should be included. Revs lower
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   330
        than stoprev will not be generated.
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   331
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   332
        Result does not include the null revision."""
23328
3a7d9c0c57a5 ancestor.lazyancestors: take parentrevs function rather than changelog
Siddharth Agarwal <sid0@fb.com>
parents: 22225
diff changeset
   333
        self._parentrevs = pfunc
43968
5ce6daa67658 ancestor: drop an unused local variable assignment
Matt Harbison <matt_harbison@yahoo.com>
parents: 43506
diff changeset
   334
        self._initrevs = [r for r in revs if r >= stoprev]
18090
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   335
        self._stoprev = stoprev
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   336
        self._inclusive = inclusive
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   337
39482
77a2f6d805f2 lazyancestors: reuse __iter__ implementation in __contains__
Martin von Zweigbergk <martinvonz@google.com>
parents: 39481
diff changeset
   338
        self._containsseen = set()
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 41244
diff changeset
   339
        self._containsiter = _lazyancestorsiter(
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 41244
diff changeset
   340
            self._parentrevs, self._initrevs, self._stoprev, self._inclusive
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 41244
diff changeset
   341
        )
18091
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   342
22225
baecf4e1b7d0 ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 21101
diff changeset
   343
    def __nonzero__(self):
baecf4e1b7d0 ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 21101
diff changeset
   344
        """False if the set is empty, True otherwise."""
baecf4e1b7d0 ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 21101
diff changeset
   345
        try:
29216
ead25aa27a43 py3: convert to next() function
timeless <timeless@mozdev.org>
parents: 25915
diff changeset
   346
            next(iter(self))
22225
baecf4e1b7d0 ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 21101
diff changeset
   347
            return True
baecf4e1b7d0 ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 21101
diff changeset
   348
        except StopIteration:
baecf4e1b7d0 ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 21101
diff changeset
   349
            return False
baecf4e1b7d0 ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 21101
diff changeset
   350
31476
413b44003462 py3: add __bool__ to every class defining __nonzero__
Gregory Szorc <gregory.szorc@gmail.com>
parents: 29216
diff changeset
   351
    __bool__ = __nonzero__
413b44003462 py3: add __bool__ to every class defining __nonzero__
Gregory Szorc <gregory.szorc@gmail.com>
parents: 29216
diff changeset
   352
18090
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   353
    def __iter__(self):
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   354
        """Generate the ancestors of _initrevs in reverse topological order.
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   355
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   356
        If inclusive is False, yield a sequence of revision numbers starting
39473
b6db2e80a9ce ancestors: actually iterate over ancestors in topological order (issue5979)
Boris Feld <boris.feld@octobus.net>
parents: 38783
diff changeset
   357
        with the parents of each revision in revs, i.e., each revision is
b6db2e80a9ce ancestors: actually iterate over ancestors in topological order (issue5979)
Boris Feld <boris.feld@octobus.net>
parents: 38783
diff changeset
   358
        *not* considered an ancestor of itself. Results are emitted in reverse
b6db2e80a9ce ancestors: actually iterate over ancestors in topological order (issue5979)
Boris Feld <boris.feld@octobus.net>
parents: 38783
diff changeset
   359
        revision number order. That order is also topological: a child is
b6db2e80a9ce ancestors: actually iterate over ancestors in topological order (issue5979)
Boris Feld <boris.feld@octobus.net>
parents: 38783
diff changeset
   360
        always emitted before its parent.
18090
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   361
39474
a60dae060bc8 ancestors: ensure a consistent order even in the "inclusive" case
Boris Feld <boris.feld@octobus.net>
parents: 39473
diff changeset
   362
        If inclusive is True, the source revisions are also yielded. The
a60dae060bc8 ancestors: ensure a consistent order even in the "inclusive" case
Boris Feld <boris.feld@octobus.net>
parents: 39473
diff changeset
   363
        reverse revision number order is still enforced."""
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 41244
diff changeset
   364
        return _lazyancestorsiter(
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 41244
diff changeset
   365
            self._parentrevs, self._initrevs, self._stoprev, self._inclusive
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 41244
diff changeset
   366
        )
18091
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   367
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   368
    def __contains__(self, target):
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   369
        """Test whether target is an ancestor of self._initrevs."""
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   370
        seen = self._containsseen
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   371
        if target in seen:
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   372
            return True
39482
77a2f6d805f2 lazyancestors: reuse __iter__ implementation in __contains__
Martin von Zweigbergk <martinvonz@google.com>
parents: 39481
diff changeset
   373
        iter = self._containsiter
77a2f6d805f2 lazyancestors: reuse __iter__ implementation in __contains__
Martin von Zweigbergk <martinvonz@google.com>
parents: 39481
diff changeset
   374
        if iter is None:
77a2f6d805f2 lazyancestors: reuse __iter__ implementation in __contains__
Martin von Zweigbergk <martinvonz@google.com>
parents: 39481
diff changeset
   375
            # Iterator exhausted
77a2f6d805f2 lazyancestors: reuse __iter__ implementation in __contains__
Martin von Zweigbergk <martinvonz@google.com>
parents: 39481
diff changeset
   376
            return False
38595
f8b46245b26a py3: make 'None in lazyancestors' not crash
Yuya Nishihara <yuya@tcha.org>
parents: 32291
diff changeset
   377
        # Only integer target is valid, but some callers expect 'None in self'
f8b46245b26a py3: make 'None in lazyancestors' not crash
Yuya Nishihara <yuya@tcha.org>
parents: 32291
diff changeset
   378
        # to be False. So we explicitly allow it.
f8b46245b26a py3: make 'None in lazyancestors' not crash
Yuya Nishihara <yuya@tcha.org>
parents: 32291
diff changeset
   379
        if target is None:
f8b46245b26a py3: make 'None in lazyancestors' not crash
Yuya Nishihara <yuya@tcha.org>
parents: 32291
diff changeset
   380
            return False
18091
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   381
25639
7125225a5287 ancestors: prefetch method outside of the loop
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25113
diff changeset
   382
        see = seen.add
39482
77a2f6d805f2 lazyancestors: reuse __iter__ implementation in __contains__
Martin von Zweigbergk <martinvonz@google.com>
parents: 39481
diff changeset
   383
        try:
77a2f6d805f2 lazyancestors: reuse __iter__ implementation in __contains__
Martin von Zweigbergk <martinvonz@google.com>
parents: 39481
diff changeset
   384
            while True:
77a2f6d805f2 lazyancestors: reuse __iter__ implementation in __contains__
Martin von Zweigbergk <martinvonz@google.com>
parents: 39481
diff changeset
   385
                rev = next(iter)
77a2f6d805f2 lazyancestors: reuse __iter__ implementation in __contains__
Martin von Zweigbergk <martinvonz@google.com>
parents: 39481
diff changeset
   386
                see(rev)
77a2f6d805f2 lazyancestors: reuse __iter__ implementation in __contains__
Martin von Zweigbergk <martinvonz@google.com>
parents: 39481
diff changeset
   387
                if rev == target:
77a2f6d805f2 lazyancestors: reuse __iter__ implementation in __contains__
Martin von Zweigbergk <martinvonz@google.com>
parents: 39481
diff changeset
   388
                    return True
77a2f6d805f2 lazyancestors: reuse __iter__ implementation in __contains__
Martin von Zweigbergk <martinvonz@google.com>
parents: 39481
diff changeset
   389
                if rev < target:
77a2f6d805f2 lazyancestors: reuse __iter__ implementation in __contains__
Martin von Zweigbergk <martinvonz@google.com>
parents: 39481
diff changeset
   390
                    return False
77a2f6d805f2 lazyancestors: reuse __iter__ implementation in __contains__
Martin von Zweigbergk <martinvonz@google.com>
parents: 39481
diff changeset
   391
        except StopIteration:
77a2f6d805f2 lazyancestors: reuse __iter__ implementation in __contains__
Martin von Zweigbergk <martinvonz@google.com>
parents: 39481
diff changeset
   392
            # Set to None to indicate fast-path can be used next time, and to
77a2f6d805f2 lazyancestors: reuse __iter__ implementation in __contains__
Martin von Zweigbergk <martinvonz@google.com>
parents: 39481
diff changeset
   393
            # free up memory.
77a2f6d805f2 lazyancestors: reuse __iter__ implementation in __contains__
Martin von Zweigbergk <martinvonz@google.com>
parents: 39481
diff changeset
   394
            self._containsiter = None
77a2f6d805f2 lazyancestors: reuse __iter__ implementation in __contains__
Martin von Zweigbergk <martinvonz@google.com>
parents: 39481
diff changeset
   395
            return False