annotate mercurial/ancestor.py @ 35011:a2dfc723b6b5

bundle: allow bundlerepo to support alternative manifest implementations With our treemanifest logic, the manifests are no longer transported as part of the changegroup and are no longer stored in a revlog. This means the self.manifestlog line in bundlerepo.filestart no longer calls _constructmanifest, and therefore does not consume the manifest portion of the changegroup, which means filestart is not populated and we result in an infinite loop. The fix is to make filestart aware that self.manifestlog might not consume the changegroup part, and consume it manually if necessary. There's currently no way to test this in core, but our treemanifest extension has tests to cover this. Differential Revision: https://phab.mercurial-scm.org/D1329
author Durham Goode <durham@fb.com>
date Tue, 07 Nov 2017 10:16:53 -0800
parents bd872f64a8ba
children f8b46245b26a
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
25113
0ca8410ea345 util: drop alias for collections.deque
Martin von Zweigbergk <martinvonz@google.com>
parents: 23342
diff changeset
10 import collections
20034
1e5b38a919dd cleanup: move stdlib imports to their own import statement
Augie Fackler <raf@durin42.com>
parents: 18987
diff changeset
11 import heapq
25915
7ef98b38163f ancestor: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25639
diff changeset
12
7ef98b38163f ancestor: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25639
diff changeset
13 from .node import nullrev
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
14
21101
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
15 def commonancestorsheads(pfunc, *nodes):
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
16 """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
17 heads(::nodes[0] and ::nodes[1] and ...) .
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
18
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
19 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
20 """
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
21 if not isinstance(nodes, set):
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
22 nodes = set(nodes)
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
23 if nullrev in nodes:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
24 return set()
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
25 if len(nodes) <= 1:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
26 return nodes
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 allseen = (1 << len(nodes)) - 1
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
29 seen = [0] * (max(nodes) + 1)
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
30 for i, n in enumerate(nodes):
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
31 seen[n] = 1 << i
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
32 poison = 1 << (i + 1)
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
33
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
34 gca = set()
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
35 interesting = len(nodes)
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
36 nv = len(seen) - 1
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
37 while nv >= 0 and interesting:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
38 v = nv
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
39 nv -= 1
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
40 if not seen[v]:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
41 continue
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
42 sv = seen[v]
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
43 if sv < poison:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
44 interesting -= 1
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
45 if sv == allseen:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
46 gca.add(v)
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
47 sv |= poison
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
48 if v in nodes:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
49 # history is linear
32291
bd872f64a8ba cleanup: use set literals
Martin von Zweigbergk <martinvonz@google.com>
parents: 31476
diff changeset
50 return {v}
21101
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
51 if sv < poison:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
52 for p in pfunc(v):
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
53 sp = seen[p]
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
54 if p == nullrev:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
55 continue
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
56 if sp == 0:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
57 seen[p] = sv
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
58 interesting += 1
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
59 elif sp != sv:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
60 seen[p] |= sv
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
61 else:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
62 for p in pfunc(v):
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
63 if p == nullrev:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
64 continue
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
65 sp = seen[p]
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
66 if sp and sp < poison:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
67 interesting -= 1
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
68 seen[p] = sv
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
69 return gca
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
70
18986
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
71 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
72 """
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
73 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
74 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
75
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
76 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
77 """
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
78 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
79 interesting = {}
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
80 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
81 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
82 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
83 mapping = []
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
84 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
85 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
86 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
87 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
88 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
89 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
90 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
91 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
92 v = nv
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
93 nv -= 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
94 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
95 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
96 continue
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
97 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
98 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
99 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
100 continue
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
101 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
102 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
103 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
104 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
105 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
106 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
107 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
108 if sp:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
109 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
110 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
111 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
112 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
113 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
114 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
115 continue
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
116 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
117 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
118 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
119 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
120 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
121 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
122 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
123 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
124 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
125
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
126 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
127 return []
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
128
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
129 k = 0
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
130 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
131 k |= i
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
132 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
133
21101
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
134 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
135
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
136 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
137 return gca
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
138 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
139
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
140 class incrementalmissingancestors(object):
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
141 '''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
142
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
143 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
144 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
145 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
146 def __init__(self, pfunc, bases):
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
147 self.bases = set(bases)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
148 if not self.bases:
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
149 self.bases.add(nullrev)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
150 self.pfunc = pfunc
17970
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
151
23340
83225aff0265 ancestor: add a way to test whether a missing ancestor object has bases
Siddharth Agarwal <sid0@fb.com>
parents: 23339
diff changeset
152 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
153 '''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
154 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
155
23341
bcc3012f8477 ancestor: add a way to add to bases of a missing ancestor object
Siddharth Agarwal <sid0@fb.com>
parents: 23340
diff changeset
156 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
157 '''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
158 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
159
23342
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
160 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
161 '''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
162 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
163 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
164 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
165 # 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
166 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
167 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
168 return
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
169 # 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
170 # 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
171 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
172 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
173 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
174 # 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
175 return
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
176
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
177 for curr in xrange(start, min(revs) - 1, -1):
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 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
179 continue
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(curr)
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
181 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
182 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
183 # 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
184 break
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
185
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
186 def missingancestors(self, revs):
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
187 '''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
188
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
189 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
190
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
191 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
192 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
193 revsvisit = set(revs)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
194 basesvisit = self.bases
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
195 pfunc = self.pfunc
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
196 bothvisit = revsvisit.intersection(basesvisit)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
197 revsvisit.difference_update(bothvisit)
17970
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
198 if not revsvisit:
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
199 return []
17970
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
200
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
201 start = max(max(revsvisit), max(basesvisit))
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
202 # 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
203 # - 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
204 # one of the nodes in revs
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
205 # - basesvisit is the same for bases
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
206 # - 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
207 # 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
208 # 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
209 # basesvisit.
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
210 # 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
211 # 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
212 # 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
213 # 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
214 # 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
215 # exit.
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
216
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
217 missing = []
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
218 for curr in xrange(start, nullrev, -1):
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
219 if not revsvisit:
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
220 break
17970
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
221
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
222 if curr in bothvisit:
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
223 bothvisit.remove(curr)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
224 # 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
225 # another path
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
226 for p in pfunc(curr):
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
227 revsvisit.discard(p)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
228 basesvisit.add(p)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
229 bothvisit.add(p)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
230 continue
17970
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
231
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
232 if curr in revsvisit:
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
233 missing.append(curr)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
234 revsvisit.remove(curr)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
235 thisvisit = revsvisit
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
236 othervisit = basesvisit
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
237 elif curr in basesvisit:
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
238 thisvisit = basesvisit
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
239 othervisit = revsvisit
17970
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
240 else:
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
241 # 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
242 continue
17970
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
243
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
244 for p in pfunc(curr):
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
245 if p == nullrev:
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
246 pass
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
247 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
248 # 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
249 # in bothvisit
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
250 revsvisit.discard(p)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
251 basesvisit.add(p)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
252 bothvisit.add(p)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
253 else:
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
254 # visit later
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
255 thisvisit.add(p)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
256
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
257 missing.reverse()
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
258 return missing
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
259
18090
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
260 class lazyancestors(object):
23328
3a7d9c0c57a5 ancestor.lazyancestors: take parentrevs function rather than changelog
Siddharth Agarwal <sid0@fb.com>
parents: 22225
diff changeset
261 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
262 """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
263 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
264
18091
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
265 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
266 iteration and membership.
18090
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
267
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
268 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
269 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
270 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
271
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
272 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
273 self._parentrevs = pfunc
18090
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
274 self._initrevs = revs
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
275 self._stoprev = stoprev
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
276 self._inclusive = inclusive
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
277
18091
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
278 # Initialize data structures for __contains__.
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
279 # For __contains__, we use a heap rather than a deque because
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
280 # (a) it minimizes the number of parentrevs calls made
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
281 # (b) it makes the loop termination condition obvious
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
282 # Python's heap is a min-heap. Multiply all values by -1 to convert it
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
283 # into a max-heap.
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
284 self._containsvisit = [-rev for rev in revs]
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
285 heapq.heapify(self._containsvisit)
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
286 if inclusive:
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
287 self._containsseen = set(revs)
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
288 else:
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
289 self._containsseen = set()
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
290
22225
baecf4e1b7d0 ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 21101
diff changeset
291 def __nonzero__(self):
baecf4e1b7d0 ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 21101
diff changeset
292 """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
293 try:
29216
ead25aa27a43 py3: convert to next() function
timeless <timeless@mozdev.org>
parents: 25915
diff changeset
294 next(iter(self))
22225
baecf4e1b7d0 ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 21101
diff changeset
295 return True
baecf4e1b7d0 ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 21101
diff changeset
296 except StopIteration:
baecf4e1b7d0 ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 21101
diff changeset
297 return False
baecf4e1b7d0 ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 21101
diff changeset
298
31476
413b44003462 py3: add __bool__ to every class defining __nonzero__
Gregory Szorc <gregory.szorc@gmail.com>
parents: 29216
diff changeset
299 __bool__ = __nonzero__
413b44003462 py3: add __bool__ to every class defining __nonzero__
Gregory Szorc <gregory.szorc@gmail.com>
parents: 29216
diff changeset
300
18090
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
301 def __iter__(self):
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
302 """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
303
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
304 If inclusive is False, yield a sequence of revision numbers starting
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
305 with the parents of each revision in revs, i.e., each revision is *not*
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
306 considered an ancestor of itself. Results are in breadth-first order:
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
307 parents of each rev in revs, then parents of those, etc.
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
308
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
309 If inclusive is True, yield all the revs first (ignoring stoprev),
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
310 then yield all the ancestors of revs as when inclusive is False.
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
311 If an element in revs is an ancestor of a different rev it is not
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
312 yielded again."""
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
313 seen = set()
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
314 revs = self._initrevs
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
315 if self._inclusive:
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
316 for rev in revs:
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
317 yield rev
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
318 seen.update(revs)
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
319
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
320 parentrevs = self._parentrevs
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
321 stoprev = self._stoprev
25113
0ca8410ea345 util: drop alias for collections.deque
Martin von Zweigbergk <martinvonz@google.com>
parents: 23342
diff changeset
322 visit = collections.deque(revs)
18090
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
323
25639
7125225a5287 ancestors: prefetch method outside of the loop
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25113
diff changeset
324 see = seen.add
7125225a5287 ancestors: prefetch method outside of the loop
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25113
diff changeset
325 schedule = visit.append
7125225a5287 ancestors: prefetch method outside of the loop
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25113
diff changeset
326
18090
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
327 while visit:
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
328 for parent in parentrevs(visit.popleft()):
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
329 if parent >= stoprev and parent not in seen:
25639
7125225a5287 ancestors: prefetch method outside of the loop
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25113
diff changeset
330 schedule(parent)
7125225a5287 ancestors: prefetch method outside of the loop
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25113
diff changeset
331 see(parent)
18090
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
332 yield parent
18091
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
333
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
334 def __contains__(self, target):
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
335 """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
336 # Trying to do both __iter__ and __contains__ using the same visit
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
337 # heap and seen set is complex enough that it slows down both. Keep
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
338 # them separate.
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
339 seen = self._containsseen
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
340 if target in seen:
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
341 return True
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
342
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
343 parentrevs = self._parentrevs
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
344 visit = self._containsvisit
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
345 stoprev = self._stoprev
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
346 heappop = heapq.heappop
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
347 heappush = heapq.heappush
25639
7125225a5287 ancestors: prefetch method outside of the loop
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25113
diff changeset
348 see = seen.add
18091
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
349
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
350 targetseen = False
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
351
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
352 while visit and -visit[0] > target and not targetseen:
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
353 for parent in parentrevs(-heappop(visit)):
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
354 if parent < stoprev or parent in seen:
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
355 continue
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
356 # We need to make sure we push all parents into the heap so
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
357 # that we leave it in a consistent state for future calls.
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
358 heappush(visit, -parent)
25639
7125225a5287 ancestors: prefetch method outside of the loop
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25113
diff changeset
359 see(parent)
18091
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
360 if parent == target:
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
361 targetseen = True
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
362
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
363 return targetseen