annotate mercurial/ancestor.py @ 27432:77d25b913f80

changegroup: introduce cg3, which has support for exchanging treemanifests I'm not entirely happy with using a trailing / on a "file" entry for transferring a treemanifest. We've discussed putting some flags on each file header[0], but I'm unconvinced that's actually any better: if we were going to add another feature to the cg format we'd still be doing a version bump anyway to cg4, so I'm inclined to not spend time coming up with a more sophisticated format until we actually know what the next feature we want to stuff in a changegroup will be. Test changes outside test-treemanifest.t are only due to the new CG3 bundlecap showing up in the wire protocol. Many thanks to adgar@google.com and martinvonz@google.com for helping me with various odd corners of the changegroup and treemanifest API. 0: It's not hard refactoring, nor is it a lot of work. I'm just disinclined to do speculative work when it's not clear what the customer would actually be.
author Augie Fackler <augie@google.com>
date Fri, 11 Dec 2015 11:23:49 -0500
parents 7ef98b38163f
children ead25aa27a43
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
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
50 return set([v])
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'''
83225aff0265 ancestor: add a way to test whether a missing ancestor object has bases
Siddharth Agarwal <sid0@fb.com>
parents: 23339
diff changeset
154 return self.bases and self.bases != set([nullrev])
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:
baecf4e1b7d0 ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 21101
diff changeset
294 iter(self).next()
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
18090
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
299 def __iter__(self):
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
300 """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
301
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
302 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
303 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
304 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
305 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
306
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
307 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
308 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
309 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
310 yielded again."""
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
311 seen = set()
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
312 revs = self._initrevs
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
313 if self._inclusive:
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
314 for rev in revs:
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
315 yield rev
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
316 seen.update(revs)
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
317
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
318 parentrevs = self._parentrevs
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
319 stoprev = self._stoprev
25113
0ca8410ea345 util: drop alias for collections.deque
Martin von Zweigbergk <martinvonz@google.com>
parents: 23342
diff changeset
320 visit = collections.deque(revs)
18090
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
321
25639
7125225a5287 ancestors: prefetch method outside of the loop
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25113
diff changeset
322 see = seen.add
7125225a5287 ancestors: prefetch method outside of the loop
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25113
diff changeset
323 schedule = visit.append
7125225a5287 ancestors: prefetch method outside of the loop
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25113
diff changeset
324
18090
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
325 while visit:
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
326 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
327 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
328 schedule(parent)
7125225a5287 ancestors: prefetch method outside of the loop
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25113
diff changeset
329 see(parent)
18090
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
330 yield parent
18091
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
331
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
332 def __contains__(self, target):
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
333 """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
334 # 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
335 # 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
336 # them separate.
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
337 seen = self._containsseen
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
338 if target in seen:
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
339 return True
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
340
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
341 parentrevs = self._parentrevs
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
342 visit = self._containsvisit
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
343 stoprev = self._stoprev
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
344 heappop = heapq.heappop
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
345 heappush = heapq.heappush
25639
7125225a5287 ancestors: prefetch method outside of the loop
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25113
diff changeset
346 see = seen.add
18091
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
347
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
348 targetseen = False
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 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
351 for parent in parentrevs(-heappop(visit)):
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
352 if parent < stoprev or parent in seen:
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
353 continue
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
354 # 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
355 # 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
356 heappush(visit, -parent)
25639
7125225a5287 ancestors: prefetch method outside of the loop
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25113
diff changeset
357 see(parent)
18091
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
358 if parent == target:
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
359 targetseen = True
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
360
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
361 return targetseen