Mercurial > hg
annotate mercurial/ancestor.py @ 21714:635a8201e356
qfold: allow to specify '--message/'--logfile' and '--edit' at the same time
Before this patch, 'hg qfold' disallows to specify
'--message/'--logfile' and '--edit' at the same time.
'hg qfold' has disallowed such combination since Mercurial 0.9.2, but
this restriction seems not to be reasonable for recent Mercurial,
because all other commands creating new changeset allow it.
This patch allows 'hg qfold' to specify '--message/'--logfile' and
'--edit' at the same time like other commands creating new changeset.
author | FUJIWARA Katsunori <foozy@lares.dti.ne.jp> |
---|---|
date | Sun, 01 Jun 2014 00:08:33 +0900 |
parents | 64911a12dc28 |
children | baecf4e1b7d0 |
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 |
17970
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
137 def missingancestors(revs, bases, pfunc): |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
138 """Return all the ancestors of revs that are not ancestors of bases. |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
139 |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
140 This may include elements from revs. |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
141 |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
142 Equivalent to the revset (::revs - ::bases). Revs are returned in |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
143 revision number order, which is a topological order. |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
144 |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
145 revs and bases should both be iterables. pfunc must return a list of |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
146 parent revs for a given revs. |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
147 """ |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
148 |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
149 revsvisit = set(revs) |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
150 basesvisit = set(bases) |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
151 if not revsvisit: |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
152 return [] |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
153 if not basesvisit: |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
154 basesvisit.add(nullrev) |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
155 start = max(max(revsvisit), max(basesvisit)) |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
156 bothvisit = revsvisit.intersection(basesvisit) |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
157 revsvisit.difference_update(bothvisit) |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
158 basesvisit.difference_update(bothvisit) |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
159 # At this point, we hold the invariants that: |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
160 # - revsvisit is the set of nodes we know are an ancestor of at least one |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
161 # of the nodes in revs |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
162 # - basesvisit is the same for bases |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
163 # - bothvisit is the set of nodes we know are ancestors of at least one of |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
164 # the nodes in revs and one of the nodes in bases |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
165 # - a node may be in none or one, but not more, of revsvisit, basesvisit |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
166 # and bothvisit at any given time |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
167 # Now we walk down in reverse topo order, adding parents of nodes already |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
168 # visited to the sets while maintaining the invariants. When a node is |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
169 # found in both revsvisit and basesvisit, it is removed from them and |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
170 # added to bothvisit instead. When revsvisit becomes empty, there are no |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
171 # more ancestors of revs that aren't also ancestors of bases, so exit. |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
172 |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
173 missing = [] |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
174 for curr in xrange(start, nullrev, -1): |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
175 if not revsvisit: |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
176 break |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
177 |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
178 if curr in bothvisit: |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
179 bothvisit.remove(curr) |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
180 # curr's parents might have made it into revsvisit or basesvisit |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
181 # through another path |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
182 for p in pfunc(curr): |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
183 revsvisit.discard(p) |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
184 basesvisit.discard(p) |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
185 bothvisit.add(p) |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
186 continue |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
187 |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
188 # curr will never be in both revsvisit and basesvisit, since if it |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
189 # were it'd have been pushed to bothvisit |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
190 if curr in revsvisit: |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
191 missing.append(curr) |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
192 thisvisit = revsvisit |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
193 othervisit = basesvisit |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
194 elif curr in basesvisit: |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
195 thisvisit = basesvisit |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
196 othervisit = revsvisit |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
197 else: |
17976
09d5681d5b72
ancestor: fix a comment (followup to 0b03454abae7)
Siddharth Agarwal <sid0@fb.com>
parents:
17970
diff
changeset
|
198 # not an ancestor of revs or bases: ignore |
17970
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
199 continue |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
200 |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
201 thisvisit.remove(curr) |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
202 for p in pfunc(curr): |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
203 if p == nullrev: |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
204 pass |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
205 elif p in othervisit or p in bothvisit: |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
206 # p is implicitly in thisvisit. This means p is or should be |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
207 # in bothvisit |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
208 revsvisit.discard(p) |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
209 basesvisit.discard(p) |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
210 bothvisit.add(p) |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
211 else: |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
212 # visit later |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
213 thisvisit.add(p) |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
214 |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
215 missing.reverse() |
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
216 return missing |
18090
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
217 |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
218 class lazyancestors(object): |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
219 def __init__(self, cl, revs, stoprev=0, inclusive=False): |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
220 """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
|
221 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
|
222 |
18091
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
223 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
|
224 iteration and membership. |
18090
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
225 |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
226 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
|
227 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
|
228 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
|
229 |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
230 Result does not include the null revision.""" |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
231 self._parentrevs = cl.parentrevs |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
232 self._initrevs = revs |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
233 self._stoprev = stoprev |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
234 self._inclusive = inclusive |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
235 |
18091
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
236 # Initialize data structures for __contains__. |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
237 # 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
|
238 # (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
|
239 # (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
|
240 # 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
|
241 # into a max-heap. |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
242 self._containsvisit = [-rev for rev in revs] |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
243 heapq.heapify(self._containsvisit) |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
244 if inclusive: |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
245 self._containsseen = set(revs) |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
246 else: |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
247 self._containsseen = set() |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
248 |
18090
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
249 def __iter__(self): |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
250 """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
|
251 |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
252 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
|
253 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
|
254 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
|
255 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
|
256 |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
257 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
|
258 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
|
259 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
|
260 yielded again.""" |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
261 seen = set() |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
262 revs = self._initrevs |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
263 if self._inclusive: |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
264 for rev in revs: |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
265 yield rev |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
266 seen.update(revs) |
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 parentrevs = self._parentrevs |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
269 stoprev = self._stoprev |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
270 visit = util.deque(revs) |
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 while visit: |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
273 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
|
274 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
|
275 visit.append(parent) |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
276 seen.add(parent) |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
277 yield parent |
18091
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
278 |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
279 def __contains__(self, target): |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
280 """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
|
281 # 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
|
282 # 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
|
283 # them separate. |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
284 seen = self._containsseen |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
285 if target in seen: |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
286 return True |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
287 |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
288 parentrevs = self._parentrevs |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
289 visit = self._containsvisit |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
290 stoprev = self._stoprev |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
291 heappop = heapq.heappop |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
292 heappush = heapq.heappush |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
293 |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
294 targetseen = False |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
295 |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
296 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
|
297 for parent in parentrevs(-heappop(visit)): |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
298 if parent < stoprev or parent in seen: |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
299 continue |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
300 # 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
|
301 # 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
|
302 heappush(visit, -parent) |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
303 seen.add(parent) |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
304 if parent == target: |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
305 targetseen = True |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
306 |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
307 return targetseen |