Mercurial > hg
annotate mercurial/ancestor.py @ 26847:9f16787cbefd
util: drop Python 2.4 compat by directly importing md5 and sha1
There's been a fair amount of cruft here over the years, which we can all
just get rid of now.
author | Siddharth Agarwal <sid0@fb.com> |
---|---|
date | Sat, 24 Oct 2015 15:56:16 -0700 |
parents | 7ef98b38163f |
children | ead25aa27a43 |
rev | line source |
---|---|
3135
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
1 # ancestor.py - generic DAG ancestor algorithm for mercurial |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
2 # |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
3 # Copyright 2006 Matt Mackall <mpm@selenic.com> |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
4 # |
8225
46293a0c7e9f
updated license to be explicit about GPL version 2
Martin Geisler <mg@lazybytes.net>
parents:
7882
diff
changeset
|
5 # This software may be used and distributed according to the terms of the |
10263 | 6 # GNU General Public License version 2 or any later version. |
3135
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
7 |
25915
7ef98b38163f
ancestor: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
25639
diff
changeset
|
8 from __future__ import absolute_import |
7ef98b38163f
ancestor: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
25639
diff
changeset
|
9 |
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 |