Mercurial > hg
annotate mercurial/ancestor.py @ 47072:4c041c71ec01
revlog: introduce an explicit tracking of what the revlog is about
Since the dawn of time, people have been forced to rely to lossy introspection
of the index filename to determine what the purpose and role of the revlog they
encounter is. This is hacky, error prone, inflexible, abstraction-leaky,
<insert-your-own-complaints-here>.
In f63299ee7e4d Raphaël introduced a new attribute to track this information:
`revlog_kind`. However it is initialized in an odd place and various instances
end up not having it set. In addition is only tracking some of the information
we end up having to introspect in various pieces of code.
So we add a new attribute that holds more data and is more strictly enforced.
This work is done in collaboration with Raphaël.
The `revlog_kind` one will be removed/adapted in the next changeset. We expect
to be able to clean up various existing piece of code and to simplify coming
work around the newer revlog format.
Differential Revision: https://phab.mercurial-scm.org/D10352
author | Pierre-Yves David <pierre-yves.david@octobus.net> |
---|---|
date | Tue, 06 Apr 2021 05:20:24 +0200 |
parents | d4ba4d51f85f |
children | 6000f5b25c9b |
rev | line source |
---|---|
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 | 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 |