annotate mercurial/ancestor.py @ 40592:83e571ea06a9

commandserver: attach prompt default and choices to message These attributes are important to provide a GUI prompt to user.
author Yuya Nishihara <yuya@tcha.org>
date Sun, 04 Nov 2018 12:17:20 +0900
parents 72b94f946e90
children 4856c9b8cbaf
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
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
25e572394f5c Update license to GPLv2+
Matt Mackall <mpm@selenic.com>
parents: 8465
diff changeset
6 # GNU General Public License version 2 or any later version.
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
7
25915
7ef98b38163f ancestor: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25639
diff changeset
8 from __future__ import absolute_import
7ef98b38163f ancestor: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25639
diff changeset
9
20034
1e5b38a919dd cleanup: move stdlib imports to their own import statement
Augie Fackler <raf@durin42.com>
parents: 18987
diff changeset
10 import heapq
25915
7ef98b38163f ancestor: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25639
diff changeset
11
7ef98b38163f ancestor: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25639
diff changeset
12 from .node import nullrev
38783
e7aa113b14f7 global: use pycompat.xrange()
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38595
diff changeset
13 from . import (
40298
9cadb0f5f227 rust: hooking into Python code
Georges Racinet <gracinet@anybox.fr>
parents: 39581
diff changeset
14 policy,
38783
e7aa113b14f7 global: use pycompat.xrange()
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38595
diff changeset
15 pycompat,
e7aa113b14f7 global: use pycompat.xrange()
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38595
diff changeset
16 )
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
17
40298
9cadb0f5f227 rust: hooking into Python code
Georges Racinet <gracinet@anybox.fr>
parents: 39581
diff changeset
18 parsers = policy.importmod(r'parsers')
9cadb0f5f227 rust: hooking into Python code
Georges Racinet <gracinet@anybox.fr>
parents: 39581
diff changeset
19
21101
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
20 def commonancestorsheads(pfunc, *nodes):
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
21 """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
22 heads(::nodes[0] and ::nodes[1] and ...) .
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
23
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
24 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
25 """
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
26 if not isinstance(nodes, set):
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
27 nodes = set(nodes)
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
28 if nullrev in nodes:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
29 return set()
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
30 if len(nodes) <= 1:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
31 return nodes
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
32
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
33 allseen = (1 << len(nodes)) - 1
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
34 seen = [0] * (max(nodes) + 1)
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
35 for i, n in enumerate(nodes):
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
36 seen[n] = 1 << i
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
37 poison = 1 << (i + 1)
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
38
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
39 gca = set()
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
40 interesting = len(nodes)
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
41 nv = len(seen) - 1
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
42 while nv >= 0 and interesting:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
43 v = nv
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
44 nv -= 1
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
45 if not seen[v]:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
46 continue
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
47 sv = seen[v]
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
48 if sv < poison:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
49 interesting -= 1
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
50 if sv == allseen:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
51 gca.add(v)
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
52 sv |= poison
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
53 if v in nodes:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
54 # history is linear
32291
bd872f64a8ba cleanup: use set literals
Martin von Zweigbergk <martinvonz@google.com>
parents: 31476
diff changeset
55 return {v}
21101
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
56 if sv < poison:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
57 for p in pfunc(v):
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
58 sp = seen[p]
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
59 if p == nullrev:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
60 continue
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
61 if sp == 0:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
62 seen[p] = sv
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
63 interesting += 1
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
64 elif sp != sv:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
65 seen[p] |= sv
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
66 else:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
67 for p in pfunc(v):
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
68 if p == nullrev:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
69 continue
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
70 sp = seen[p]
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
71 if sp and sp < poison:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
72 interesting -= 1
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
73 seen[p] = sv
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
74 return gca
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
75
18986
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
76 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
77 """
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
78 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
79 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
80
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
81 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
82 """
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
83 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
84 interesting = {}
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
85 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
86 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
87 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
88 mapping = []
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
89 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
90 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
91 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
92 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
93 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
94 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
95 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
96 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
97 v = nv
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
98 nv -= 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
99 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
100 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
101 continue
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
102 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
103 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
104 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
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 dp = depth[p]
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
107 nsp = sp = seen[p]
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
108 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
109 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
110 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
111 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
112 nsp = seen[p] = sv
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
113 if sp:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
114 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
115 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
116 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
117 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
118 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
119 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
120 continue
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
121 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
122 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
123 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
124 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
125 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
126 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
127 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
128 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
129 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
130
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
131 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
132 return []
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
133
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
134 k = 0
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
135 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
136 k |= i
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
137 return set(n for (i, n) in mapping if k & i)
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
138
21101
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
139 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
140
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
141 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
142 return gca
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
143 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
144
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
145 class incrementalmissingancestors(object):
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
146 '''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
147
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
148 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
149 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
150 same internal data structures adds needless complexity.'''
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
151 def __init__(self, pfunc, bases):
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
152 self.bases = set(bases)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
153 if not self.bases:
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
154 self.bases.add(nullrev)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
155 self.pfunc = pfunc
17970
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
156
23340
83225aff0265 ancestor: add a way to test whether a missing ancestor object has bases
Siddharth Agarwal <sid0@fb.com>
parents: 23339
diff changeset
157 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
158 '''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
159 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
160
23341
bcc3012f8477 ancestor: add a way to add to bases of a missing ancestor object
Siddharth Agarwal <sid0@fb.com>
parents: 23340
diff changeset
161 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
162 '''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
163 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
164
23342
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
165 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
166 '''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
167 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
168 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
169 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
170 # 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
171 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
172 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
173 return
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
174 # 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
175 # 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
176 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
177 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
178 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
179 # 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
180 return
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
181
38783
e7aa113b14f7 global: use pycompat.xrange()
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38595
diff changeset
182 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
183 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
184 continue
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
185 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
186 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
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 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
189 break
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
190
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
191 def missingancestors(self, revs):
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
192 '''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
193
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
194 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
195
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
196 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
197 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
198 revsvisit = set(revs)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
199 basesvisit = self.bases
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
200 pfunc = self.pfunc
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
201 bothvisit = revsvisit.intersection(basesvisit)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
202 revsvisit.difference_update(bothvisit)
17970
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
203 if not revsvisit:
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
204 return []
17970
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
205
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
206 start = max(max(revsvisit), max(basesvisit))
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
207 # 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
208 # - 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
209 # one of the nodes in revs
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
210 # - basesvisit is the same for bases
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
211 # - 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
212 # 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
213 # 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
214 # basesvisit.
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
215 # 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
216 # 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
217 # 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
218 # 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
219 # 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
220 # exit.
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
221
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
222 missing = []
38783
e7aa113b14f7 global: use pycompat.xrange()
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38595
diff changeset
223 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
224 if not revsvisit:
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
225 break
17970
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
226
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
227 if curr in bothvisit:
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
228 bothvisit.remove(curr)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
229 # 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
230 # another path
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
231 for p in pfunc(curr):
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
232 revsvisit.discard(p)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
233 basesvisit.add(p)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
234 bothvisit.add(p)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
235 continue
17970
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
236
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
237 if curr in revsvisit:
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
238 missing.append(curr)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
239 revsvisit.remove(curr)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
240 thisvisit = revsvisit
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
241 othervisit = basesvisit
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
242 elif curr in basesvisit:
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
243 thisvisit = basesvisit
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
244 othervisit = revsvisit
17970
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
245 else:
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
246 # 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
247 continue
17970
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
248
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
249 for p in pfunc(curr):
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
250 if p == nullrev:
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
251 pass
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
252 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
253 # 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
254 # in bothvisit
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
255 revsvisit.discard(p)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
256 basesvisit.add(p)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
257 bothvisit.add(p)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
258 else:
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
259 # visit later
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
260 thisvisit.add(p)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
261
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
262 missing.reverse()
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
263 return missing
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
264
39481
b6a0e06b0f7d lazyancestors: extract __iter__ to free function
Martin von Zweigbergk <martinvonz@google.com>
parents: 39477
diff changeset
265 # 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
266 def _lazyancestorsiter(parentrevs, initrevs, stoprev, inclusive):
b6a0e06b0f7d lazyancestors: extract __iter__ to free function
Martin von Zweigbergk <martinvonz@google.com>
parents: 39477
diff changeset
267 seen = {nullrev}
39537
ca9983c35d89 ancestor: rename local aliases of heapq functions in _lazyancestorsiter()
Yuya Nishihara <yuya@tcha.org>
parents: 39536
diff changeset
268 heappush = heapq.heappush
ca9983c35d89 ancestor: rename local aliases of heapq functions in _lazyancestorsiter()
Yuya Nishihara <yuya@tcha.org>
parents: 39536
diff changeset
269 heappop = heapq.heappop
39538
238a1480d7ad ancestor: use heapreplace() in place of heappop/heappush()
Yuya Nishihara <yuya@tcha.org>
parents: 39537
diff changeset
270 heapreplace = heapq.heapreplace
39481
b6a0e06b0f7d lazyancestors: extract __iter__ to free function
Martin von Zweigbergk <martinvonz@google.com>
parents: 39477
diff changeset
271 see = seen.add
b6a0e06b0f7d lazyancestors: extract __iter__ to free function
Martin von Zweigbergk <martinvonz@google.com>
parents: 39477
diff changeset
272
b6a0e06b0f7d lazyancestors: extract __iter__ to free function
Martin von Zweigbergk <martinvonz@google.com>
parents: 39477
diff changeset
273 if inclusive:
39533
f6bcb4f9cd3c ancestor: remove alias of initrevs from _lazyancestorsiter()
Yuya Nishihara <yuya@tcha.org>
parents: 39482
diff changeset
274 visit = [-r for r in initrevs]
f6bcb4f9cd3c ancestor: remove alias of initrevs from _lazyancestorsiter()
Yuya Nishihara <yuya@tcha.org>
parents: 39482
diff changeset
275 seen.update(initrevs)
39481
b6a0e06b0f7d lazyancestors: extract __iter__ to free function
Martin von Zweigbergk <martinvonz@google.com>
parents: 39477
diff changeset
276 heapq.heapify(visit)
b6a0e06b0f7d lazyancestors: extract __iter__ to free function
Martin von Zweigbergk <martinvonz@google.com>
parents: 39477
diff changeset
277 else:
b6a0e06b0f7d lazyancestors: extract __iter__ to free function
Martin von Zweigbergk <martinvonz@google.com>
parents: 39477
diff changeset
278 visit = []
b6a0e06b0f7d lazyancestors: extract __iter__ to free function
Martin von Zweigbergk <martinvonz@google.com>
parents: 39477
diff changeset
279 heapq.heapify(visit)
39533
f6bcb4f9cd3c ancestor: remove alias of initrevs from _lazyancestorsiter()
Yuya Nishihara <yuya@tcha.org>
parents: 39482
diff changeset
280 for r in initrevs:
39535
b9ee9c2e10dd ancestor: unroll loop of parents in _lazyancestorsiter()
Yuya Nishihara <yuya@tcha.org>
parents: 39534
diff changeset
281 p1, p2 = parentrevs(r)
b9ee9c2e10dd ancestor: unroll loop of parents in _lazyancestorsiter()
Yuya Nishihara <yuya@tcha.org>
parents: 39534
diff changeset
282 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
283 heappush(visit, -p1)
39535
b9ee9c2e10dd ancestor: unroll loop of parents in _lazyancestorsiter()
Yuya Nishihara <yuya@tcha.org>
parents: 39534
diff changeset
284 see(p1)
b9ee9c2e10dd ancestor: unroll loop of parents in _lazyancestorsiter()
Yuya Nishihara <yuya@tcha.org>
parents: 39534
diff changeset
285 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
286 heappush(visit, -p2)
39535
b9ee9c2e10dd ancestor: unroll loop of parents in _lazyancestorsiter()
Yuya Nishihara <yuya@tcha.org>
parents: 39534
diff changeset
287 see(p2)
39481
b6a0e06b0f7d lazyancestors: extract __iter__ to free function
Martin von Zweigbergk <martinvonz@google.com>
parents: 39477
diff changeset
288
b6a0e06b0f7d lazyancestors: extract __iter__ to free function
Martin von Zweigbergk <martinvonz@google.com>
parents: 39477
diff changeset
289 while visit:
39536
bdb177923291 ancestor: optimize _lazyancestorsiter() for contiguous chains
Yuya Nishihara <yuya@tcha.org>
parents: 39535
diff changeset
290 current = -visit[0]
39534
fd9029d36c41 ancestor: return early from _lazyancestorsiter() when reached to stoprev
Yuya Nishihara <yuya@tcha.org>
parents: 39533
diff changeset
291 if current < stoprev:
fd9029d36c41 ancestor: return early from _lazyancestorsiter() when reached to stoprev
Yuya Nishihara <yuya@tcha.org>
parents: 39533
diff changeset
292 break
fd9029d36c41 ancestor: return early from _lazyancestorsiter() when reached to stoprev
Yuya Nishihara <yuya@tcha.org>
parents: 39533
diff changeset
293 yield current
39536
bdb177923291 ancestor: optimize _lazyancestorsiter() for contiguous chains
Yuya Nishihara <yuya@tcha.org>
parents: 39535
diff changeset
294 # 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
295 # 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
296 p1, p2 = parentrevs(current)
b9ee9c2e10dd ancestor: unroll loop of parents in _lazyancestorsiter()
Yuya Nishihara <yuya@tcha.org>
parents: 39534
diff changeset
297 if p1 not in seen:
39536
bdb177923291 ancestor: optimize _lazyancestorsiter() for contiguous chains
Yuya Nishihara <yuya@tcha.org>
parents: 39535
diff changeset
298 if current - p1 == 1:
bdb177923291 ancestor: optimize _lazyancestorsiter() for contiguous chains
Yuya Nishihara <yuya@tcha.org>
parents: 39535
diff changeset
299 visit[0] = -p1
bdb177923291 ancestor: optimize _lazyancestorsiter() for contiguous chains
Yuya Nishihara <yuya@tcha.org>
parents: 39535
diff changeset
300 else:
39538
238a1480d7ad ancestor: use heapreplace() in place of heappop/heappush()
Yuya Nishihara <yuya@tcha.org>
parents: 39537
diff changeset
301 heapreplace(visit, -p1)
39535
b9ee9c2e10dd ancestor: unroll loop of parents in _lazyancestorsiter()
Yuya Nishihara <yuya@tcha.org>
parents: 39534
diff changeset
302 see(p1)
39536
bdb177923291 ancestor: optimize _lazyancestorsiter() for contiguous chains
Yuya Nishihara <yuya@tcha.org>
parents: 39535
diff changeset
303 else:
39537
ca9983c35d89 ancestor: rename local aliases of heapq functions in _lazyancestorsiter()
Yuya Nishihara <yuya@tcha.org>
parents: 39536
diff changeset
304 heappop(visit)
39535
b9ee9c2e10dd ancestor: unroll loop of parents in _lazyancestorsiter()
Yuya Nishihara <yuya@tcha.org>
parents: 39534
diff changeset
305 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
306 heappush(visit, -p2)
39535
b9ee9c2e10dd ancestor: unroll loop of parents in _lazyancestorsiter()
Yuya Nishihara <yuya@tcha.org>
parents: 39534
diff changeset
307 see(p2)
39481
b6a0e06b0f7d lazyancestors: extract __iter__ to free function
Martin von Zweigbergk <martinvonz@google.com>
parents: 39477
diff changeset
308
18090
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
309 class lazyancestors(object):
23328
3a7d9c0c57a5 ancestor.lazyancestors: take parentrevs function rather than changelog
Siddharth Agarwal <sid0@fb.com>
parents: 22225
diff changeset
310 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
311 """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
312 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
313
18091
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
314 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
315 iteration and membership.
18090
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
316
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
317 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
318 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
319 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
320
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
321 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
322 self._parentrevs = pfunc
39476
7eadc9407867 ancestor: filter out initial revisions lower than stoprev
Yuya Nishihara <yuya@tcha.org>
parents: 39474
diff changeset
323 self._initrevs = revs = [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
324 self._stoprev = stoprev
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
325 self._inclusive = inclusive
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
326
39482
77a2f6d805f2 lazyancestors: reuse __iter__ implementation in __contains__
Martin von Zweigbergk <martinvonz@google.com>
parents: 39481
diff changeset
327 self._containsseen = set()
77a2f6d805f2 lazyancestors: reuse __iter__ implementation in __contains__
Martin von Zweigbergk <martinvonz@google.com>
parents: 39481
diff changeset
328 self._containsiter = _lazyancestorsiter(self._parentrevs,
77a2f6d805f2 lazyancestors: reuse __iter__ implementation in __contains__
Martin von Zweigbergk <martinvonz@google.com>
parents: 39481
diff changeset
329 self._initrevs,
77a2f6d805f2 lazyancestors: reuse __iter__ implementation in __contains__
Martin von Zweigbergk <martinvonz@google.com>
parents: 39481
diff changeset
330 self._stoprev,
77a2f6d805f2 lazyancestors: reuse __iter__ implementation in __contains__
Martin von Zweigbergk <martinvonz@google.com>
parents: 39481
diff changeset
331 self._inclusive)
18091
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
332
22225
baecf4e1b7d0 ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 21101
diff changeset
333 def __nonzero__(self):
baecf4e1b7d0 ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 21101
diff changeset
334 """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
335 try:
29216
ead25aa27a43 py3: convert to next() function
timeless <timeless@mozdev.org>
parents: 25915
diff changeset
336 next(iter(self))
22225
baecf4e1b7d0 ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 21101
diff changeset
337 return True
baecf4e1b7d0 ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 21101
diff changeset
338 except StopIteration:
baecf4e1b7d0 ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 21101
diff changeset
339 return False
baecf4e1b7d0 ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 21101
diff changeset
340
31476
413b44003462 py3: add __bool__ to every class defining __nonzero__
Gregory Szorc <gregory.szorc@gmail.com>
parents: 29216
diff changeset
341 __bool__ = __nonzero__
413b44003462 py3: add __bool__ to every class defining __nonzero__
Gregory Szorc <gregory.szorc@gmail.com>
parents: 29216
diff changeset
342
18090
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
343 def __iter__(self):
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
344 """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
345
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
346 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
347 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
348 *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
349 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
350 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
351
39474
a60dae060bc8 ancestors: ensure a consistent order even in the "inclusive" case
Boris Feld <boris.feld@octobus.net>
parents: 39473
diff changeset
352 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
353 reverse revision number order is still enforced."""
39581
68ce242c8b4b ancestor: remove extra generator from lazyancestors.__iter__()
Yuya Nishihara <yuya@tcha.org>
parents: 39538
diff changeset
354 return _lazyancestorsiter(self._parentrevs, self._initrevs,
68ce242c8b4b ancestor: remove extra generator from lazyancestors.__iter__()
Yuya Nishihara <yuya@tcha.org>
parents: 39538
diff changeset
355 self._stoprev, self._inclusive)
18091
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
356
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
357 def __contains__(self, target):
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
358 """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
359 seen = self._containsseen
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
360 if target in seen:
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
361 return True
39482
77a2f6d805f2 lazyancestors: reuse __iter__ implementation in __contains__
Martin von Zweigbergk <martinvonz@google.com>
parents: 39481
diff changeset
362 iter = self._containsiter
77a2f6d805f2 lazyancestors: reuse __iter__ implementation in __contains__
Martin von Zweigbergk <martinvonz@google.com>
parents: 39481
diff changeset
363 if iter is None:
77a2f6d805f2 lazyancestors: reuse __iter__ implementation in __contains__
Martin von Zweigbergk <martinvonz@google.com>
parents: 39481
diff changeset
364 # Iterator exhausted
77a2f6d805f2 lazyancestors: reuse __iter__ implementation in __contains__
Martin von Zweigbergk <martinvonz@google.com>
parents: 39481
diff changeset
365 return False
38595
f8b46245b26a py3: make 'None in lazyancestors' not crash
Yuya Nishihara <yuya@tcha.org>
parents: 32291
diff changeset
366 # 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
367 # 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
368 if target is None:
f8b46245b26a py3: make 'None in lazyancestors' not crash
Yuya Nishihara <yuya@tcha.org>
parents: 32291
diff changeset
369 return False
18091
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
370
25639
7125225a5287 ancestors: prefetch method outside of the loop
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25113
diff changeset
371 see = seen.add
39482
77a2f6d805f2 lazyancestors: reuse __iter__ implementation in __contains__
Martin von Zweigbergk <martinvonz@google.com>
parents: 39481
diff changeset
372 try:
77a2f6d805f2 lazyancestors: reuse __iter__ implementation in __contains__
Martin von Zweigbergk <martinvonz@google.com>
parents: 39481
diff changeset
373 while True:
77a2f6d805f2 lazyancestors: reuse __iter__ implementation in __contains__
Martin von Zweigbergk <martinvonz@google.com>
parents: 39481
diff changeset
374 rev = next(iter)
77a2f6d805f2 lazyancestors: reuse __iter__ implementation in __contains__
Martin von Zweigbergk <martinvonz@google.com>
parents: 39481
diff changeset
375 see(rev)
77a2f6d805f2 lazyancestors: reuse __iter__ implementation in __contains__
Martin von Zweigbergk <martinvonz@google.com>
parents: 39481
diff changeset
376 if rev == target:
77a2f6d805f2 lazyancestors: reuse __iter__ implementation in __contains__
Martin von Zweigbergk <martinvonz@google.com>
parents: 39481
diff changeset
377 return True
77a2f6d805f2 lazyancestors: reuse __iter__ implementation in __contains__
Martin von Zweigbergk <martinvonz@google.com>
parents: 39481
diff changeset
378 if rev < target:
77a2f6d805f2 lazyancestors: reuse __iter__ implementation in __contains__
Martin von Zweigbergk <martinvonz@google.com>
parents: 39481
diff changeset
379 return False
77a2f6d805f2 lazyancestors: reuse __iter__ implementation in __contains__
Martin von Zweigbergk <martinvonz@google.com>
parents: 39481
diff changeset
380 except StopIteration:
77a2f6d805f2 lazyancestors: reuse __iter__ implementation in __contains__
Martin von Zweigbergk <martinvonz@google.com>
parents: 39481
diff changeset
381 # 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
382 # free up memory.
77a2f6d805f2 lazyancestors: reuse __iter__ implementation in __contains__
Martin von Zweigbergk <martinvonz@google.com>
parents: 39481
diff changeset
383 self._containsiter = None
77a2f6d805f2 lazyancestors: reuse __iter__ implementation in __contains__
Martin von Zweigbergk <martinvonz@google.com>
parents: 39481
diff changeset
384 return False
40298
9cadb0f5f227 rust: hooking into Python code
Georges Racinet <gracinet@anybox.fr>
parents: 39581
diff changeset
385
40300
72b94f946e90 rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents: 40298
diff changeset
386 class rustlazyancestors(object):
40298
9cadb0f5f227 rust: hooking into Python code
Georges Racinet <gracinet@anybox.fr>
parents: 39581
diff changeset
387
9cadb0f5f227 rust: hooking into Python code
Georges Racinet <gracinet@anybox.fr>
parents: 39581
diff changeset
388 def __init__(self, index, revs, stoprev=0, inclusive=False):
9cadb0f5f227 rust: hooking into Python code
Georges Racinet <gracinet@anybox.fr>
parents: 39581
diff changeset
389 self._index = index
9cadb0f5f227 rust: hooking into Python code
Georges Racinet <gracinet@anybox.fr>
parents: 39581
diff changeset
390 self._stoprev = stoprev
9cadb0f5f227 rust: hooking into Python code
Georges Racinet <gracinet@anybox.fr>
parents: 39581
diff changeset
391 self._inclusive = inclusive
9cadb0f5f227 rust: hooking into Python code
Georges Racinet <gracinet@anybox.fr>
parents: 39581
diff changeset
392 # no need to prefilter out init revs that are smaller than stoprev,
9cadb0f5f227 rust: hooking into Python code
Georges Racinet <gracinet@anybox.fr>
parents: 39581
diff changeset
393 # it's done by rustlazyancestors constructor.
9cadb0f5f227 rust: hooking into Python code
Georges Racinet <gracinet@anybox.fr>
parents: 39581
diff changeset
394 # we need to convert to a list, because our ruslazyancestors
9cadb0f5f227 rust: hooking into Python code
Georges Racinet <gracinet@anybox.fr>
parents: 39581
diff changeset
395 # constructor (from C code) doesn't understand anything else yet
9cadb0f5f227 rust: hooking into Python code
Georges Racinet <gracinet@anybox.fr>
parents: 39581
diff changeset
396 self._initrevs = initrevs = list(revs)
9cadb0f5f227 rust: hooking into Python code
Georges Racinet <gracinet@anybox.fr>
parents: 39581
diff changeset
397
9cadb0f5f227 rust: hooking into Python code
Georges Racinet <gracinet@anybox.fr>
parents: 39581
diff changeset
398 self._containsiter = parsers.rustlazyancestors(
9cadb0f5f227 rust: hooking into Python code
Georges Racinet <gracinet@anybox.fr>
parents: 39581
diff changeset
399 index, initrevs, stoprev, inclusive)
9cadb0f5f227 rust: hooking into Python code
Georges Racinet <gracinet@anybox.fr>
parents: 39581
diff changeset
400
40300
72b94f946e90 rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents: 40298
diff changeset
401 def __nonzero__(self):
72b94f946e90 rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents: 40298
diff changeset
402 """False if the set is empty, True otherwise.
72b94f946e90 rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents: 40298
diff changeset
403
72b94f946e90 rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents: 40298
diff changeset
404 It's better to duplicate this essentially trivial method than
72b94f946e90 rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents: 40298
diff changeset
405 to subclass lazyancestors
72b94f946e90 rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents: 40298
diff changeset
406 """
72b94f946e90 rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents: 40298
diff changeset
407 try:
72b94f946e90 rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents: 40298
diff changeset
408 next(iter(self))
72b94f946e90 rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents: 40298
diff changeset
409 return True
72b94f946e90 rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents: 40298
diff changeset
410 except StopIteration:
72b94f946e90 rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents: 40298
diff changeset
411 return False
72b94f946e90 rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents: 40298
diff changeset
412
40298
9cadb0f5f227 rust: hooking into Python code
Georges Racinet <gracinet@anybox.fr>
parents: 39581
diff changeset
413 def __iter__(self):
9cadb0f5f227 rust: hooking into Python code
Georges Racinet <gracinet@anybox.fr>
parents: 39581
diff changeset
414 return parsers.rustlazyancestors(self._index,
9cadb0f5f227 rust: hooking into Python code
Georges Racinet <gracinet@anybox.fr>
parents: 39581
diff changeset
415 self._initrevs,
9cadb0f5f227 rust: hooking into Python code
Georges Racinet <gracinet@anybox.fr>
parents: 39581
diff changeset
416 self._stoprev,
9cadb0f5f227 rust: hooking into Python code
Georges Racinet <gracinet@anybox.fr>
parents: 39581
diff changeset
417 self._inclusive)
40300
72b94f946e90 rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents: 40298
diff changeset
418
72b94f946e90 rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents: 40298
diff changeset
419 def __contains__(self, target):
72b94f946e90 rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents: 40298
diff changeset
420 return target in self._containsiter