Mercurial > hg
annotate mercurial/ancestor.py @ 45438:ed95ccc94333
rhg: pass `ui` to `Command` `run`
Allow implementation of `From<clap::ArgMatches> for Command`
Differential Revision: https://phab.mercurial-scm.org/D8954
author | Antoine Cezar <antoine.cezar@octobus.net> |
---|---|
date | Tue, 04 Aug 2020 16:11:23 +0200 |
parents | fb16ad368606 |
children | 89a2afe31e82 |
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 # |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
3 # Copyright 2006 Matt Mackall <mpm@selenic.com> |
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): |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
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 |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
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): |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
201 '''return all the ancestors of revs that are not ancestors of self.bases |
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 |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
206 revision number order, which is a topological order.''' |
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 |