Mercurial > hg
annotate mercurial/ancestor.py @ 24449:bab983bb6fd1
revert: define 'wctx' a little earlier and use it more
author | Martin von Zweigbergk <martinvonz@google.com> |
---|---|
date | Tue, 24 Mar 2015 13:56:51 -0700 |
parents | f710644e1ce9 |
children | 0ca8410ea345 |
rev | line source |
---|---|
3135
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
1 # ancestor.py - generic DAG ancestor algorithm for mercurial |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
2 # |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
3 # Copyright 2006 Matt Mackall <mpm@selenic.com> |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
4 # |
8225
46293a0c7e9f
updated license to be explicit about GPL version 2
Martin Geisler <mg@lazybytes.net>
parents:
7882
diff
changeset
|
5 # This software may be used and distributed according to the terms of the |
10263 | 6 # GNU General Public License version 2 or any later version. |
3135
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
7 |
20034
1e5b38a919dd
cleanup: move stdlib imports to their own import statement
Augie Fackler <raf@durin42.com>
parents:
18987
diff
changeset
|
8 import heapq |
1e5b38a919dd
cleanup: move stdlib imports to their own import statement
Augie Fackler <raf@durin42.com>
parents:
18987
diff
changeset
|
9 import util |
17970
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
10 from node import nullrev |
3135
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
11 |
21101
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
12 def commonancestorsheads(pfunc, *nodes): |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
13 """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
|
14 heads(::nodes[0] and ::nodes[1] and ...) . |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
15 |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
16 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
|
17 """ |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
18 if not isinstance(nodes, set): |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
19 nodes = set(nodes) |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
20 if nullrev in nodes: |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
21 return set() |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
22 if len(nodes) <= 1: |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
23 return nodes |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
24 |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
25 allseen = (1 << len(nodes)) - 1 |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
26 seen = [0] * (max(nodes) + 1) |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
27 for i, n in enumerate(nodes): |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
28 seen[n] = 1 << i |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
29 poison = 1 << (i + 1) |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
30 |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
31 gca = set() |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
32 interesting = len(nodes) |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
33 nv = len(seen) - 1 |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
34 while nv >= 0 and interesting: |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
35 v = nv |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
36 nv -= 1 |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
37 if not seen[v]: |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
38 continue |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
39 sv = seen[v] |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
40 if sv < poison: |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
41 interesting -= 1 |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
42 if sv == allseen: |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
43 gca.add(v) |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
44 sv |= poison |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
45 if v in nodes: |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
46 # history is linear |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
47 return set([v]) |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
48 if sv < poison: |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
49 for p in pfunc(v): |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
50 sp = seen[p] |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
51 if p == nullrev: |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
52 continue |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
53 if sp == 0: |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
54 seen[p] = sv |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
55 interesting += 1 |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
56 elif sp != sv: |
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 else: |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
59 for p in pfunc(v): |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
60 if p == nullrev: |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
61 continue |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
62 sp = seen[p] |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
63 if sp and sp < poison: |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
64 interesting -= 1 |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
65 seen[p] = sv |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
66 return gca |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
67 |
18986
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
68 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
|
69 """ |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
70 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
|
71 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
|
72 |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
73 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
|
74 """ |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
75 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
|
76 interesting = {} |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
77 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
|
78 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
|
79 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
|
80 mapping = [] |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
81 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
|
82 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
|
83 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
|
84 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
|
85 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
|
86 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
|
87 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
|
88 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
|
89 v = nv |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
90 nv -= 1 |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
91 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
|
92 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
|
93 continue |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
94 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
|
95 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
|
96 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
|
97 continue |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
98 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
|
99 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
|
100 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
|
101 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
|
102 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
|
103 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
|
104 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
|
105 if sp: |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
106 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
|
107 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
|
108 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
|
109 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
|
110 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
|
111 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
|
112 continue |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
113 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
|
114 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
|
115 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
|
116 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
|
117 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
|
118 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
|
119 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
|
120 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
|
121 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
|
122 |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
123 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
|
124 return [] |
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 k = 0 |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
127 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
|
128 k |= i |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
129 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
|
130 |
21101
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
131 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
|
132 |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
133 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
|
134 return gca |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
135 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
|
136 |
23334
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
137 class incrementalmissingancestors(object): |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
138 '''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
|
139 |
23334
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
140 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
|
141 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
|
142 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
|
143 def __init__(self, pfunc, bases): |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
144 self.bases = set(bases) |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
145 if not self.bases: |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
146 self.bases.add(nullrev) |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
147 self.pfunc = pfunc |
17970
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
148 |
23340
83225aff0265
ancestor: add a way to test whether a missing ancestor object has bases
Siddharth Agarwal <sid0@fb.com>
parents:
23339
diff
changeset
|
149 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
|
150 '''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
|
151 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
|
152 |
23341
bcc3012f8477
ancestor: add a way to add to bases of a missing ancestor object
Siddharth Agarwal <sid0@fb.com>
parents:
23340
diff
changeset
|
153 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
|
154 '''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
|
155 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
|
156 |
23342
f710644e1ce9
ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents:
23341
diff
changeset
|
157 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
|
158 '''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
|
159 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
|
160 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
|
161 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
|
162 # 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
|
163 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
|
164 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
|
165 return |
f710644e1ce9
ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents:
23341
diff
changeset
|
166 # 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
|
167 # 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
|
168 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
|
169 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
|
170 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
|
171 # 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
|
172 return |
f710644e1ce9
ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents:
23341
diff
changeset
|
173 |
f710644e1ce9
ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents:
23341
diff
changeset
|
174 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
|
175 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
|
176 continue |
f710644e1ce9
ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents:
23341
diff
changeset
|
177 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
|
178 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
|
179 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
|
180 # 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
|
181 break |
f710644e1ce9
ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents:
23341
diff
changeset
|
182 |
23334
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
183 def missingancestors(self, revs): |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
184 '''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
|
185 |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
186 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
|
187 |
23334
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
188 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
|
189 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
|
190 revsvisit = set(revs) |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
191 basesvisit = self.bases |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
192 pfunc = self.pfunc |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
193 bothvisit = revsvisit.intersection(basesvisit) |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
194 revsvisit.difference_update(bothvisit) |
17970
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
195 if not revsvisit: |
23334
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
196 return [] |
17970
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
197 |
23334
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
198 start = max(max(revsvisit), max(basesvisit)) |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
199 # 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
|
200 # - 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
|
201 # one of the nodes in revs |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
202 # - basesvisit is the same for bases |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
203 # - 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
|
204 # 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
|
205 # 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
|
206 # basesvisit. |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
207 # 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
|
208 # 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
|
209 # 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
|
210 # 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
|
211 # 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
|
212 # exit. |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
213 |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
214 missing = [] |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
215 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
|
216 if not revsvisit: |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
217 break |
17970
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
218 |
23334
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
219 if curr in bothvisit: |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
220 bothvisit.remove(curr) |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
221 # 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
|
222 # another path |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
223 for p in pfunc(curr): |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
224 revsvisit.discard(p) |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
225 basesvisit.add(p) |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
226 bothvisit.add(p) |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
227 continue |
17970
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
228 |
23334
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
229 if curr in revsvisit: |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
230 missing.append(curr) |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
231 revsvisit.remove(curr) |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
232 thisvisit = revsvisit |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
233 othervisit = basesvisit |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
234 elif curr in basesvisit: |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
235 thisvisit = basesvisit |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
236 othervisit = revsvisit |
17970
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
237 else: |
23334
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
238 # 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
|
239 continue |
17970
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
240 |
23334
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
241 for p in pfunc(curr): |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
242 if p == nullrev: |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
243 pass |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
244 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
|
245 # 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
|
246 # in bothvisit |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
247 revsvisit.discard(p) |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
248 basesvisit.add(p) |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
249 bothvisit.add(p) |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
250 else: |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
251 # visit later |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
252 thisvisit.add(p) |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
253 |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
254 missing.reverse() |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
255 return missing |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
256 |
18090
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
257 class lazyancestors(object): |
23328
3a7d9c0c57a5
ancestor.lazyancestors: take parentrevs function rather than changelog
Siddharth Agarwal <sid0@fb.com>
parents:
22225
diff
changeset
|
258 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
|
259 """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
|
260 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
|
261 |
18091
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
262 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
|
263 iteration and membership. |
18090
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
264 |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
265 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
|
266 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
|
267 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
|
268 |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
269 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
|
270 self._parentrevs = pfunc |
18090
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
271 self._initrevs = revs |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
272 self._stoprev = stoprev |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
273 self._inclusive = inclusive |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
274 |
18091
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
275 # Initialize data structures for __contains__. |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
276 # 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
|
277 # (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
|
278 # (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
|
279 # 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
|
280 # into a max-heap. |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
281 self._containsvisit = [-rev for rev in revs] |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
282 heapq.heapify(self._containsvisit) |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
283 if inclusive: |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
284 self._containsseen = set(revs) |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
285 else: |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
286 self._containsseen = set() |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
287 |
22225
baecf4e1b7d0
ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
21101
diff
changeset
|
288 def __nonzero__(self): |
baecf4e1b7d0
ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
21101
diff
changeset
|
289 """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
|
290 try: |
baecf4e1b7d0
ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
21101
diff
changeset
|
291 iter(self).next() |
baecf4e1b7d0
ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
21101
diff
changeset
|
292 return True |
baecf4e1b7d0
ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
21101
diff
changeset
|
293 except StopIteration: |
baecf4e1b7d0
ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
21101
diff
changeset
|
294 return False |
baecf4e1b7d0
ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
21101
diff
changeset
|
295 |
18090
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
296 def __iter__(self): |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
297 """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
|
298 |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
299 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
|
300 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
|
301 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
|
302 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
|
303 |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
304 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
|
305 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
|
306 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
|
307 yielded again.""" |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
308 seen = set() |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
309 revs = self._initrevs |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
310 if self._inclusive: |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
311 for rev in revs: |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
312 yield rev |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
313 seen.update(revs) |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
314 |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
315 parentrevs = self._parentrevs |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
316 stoprev = self._stoprev |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
317 visit = util.deque(revs) |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
318 |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
319 while visit: |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
320 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
|
321 if parent >= stoprev and parent not in seen: |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
322 visit.append(parent) |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
323 seen.add(parent) |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
324 yield parent |
18091
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
325 |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
326 def __contains__(self, target): |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
327 """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
|
328 # 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
|
329 # 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
|
330 # them separate. |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
331 seen = self._containsseen |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
332 if target in seen: |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
333 return True |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
334 |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
335 parentrevs = self._parentrevs |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
336 visit = self._containsvisit |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
337 stoprev = self._stoprev |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
338 heappop = heapq.heappop |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
339 heappush = heapq.heappush |
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 targetseen = False |
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 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
|
344 for parent in parentrevs(-heappop(visit)): |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
345 if parent < stoprev or parent in seen: |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
346 continue |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
347 # 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
|
348 # 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
|
349 heappush(visit, -parent) |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
350 seen.add(parent) |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
351 if parent == target: |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
352 targetseen = True |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
353 |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
354 return targetseen |