Mercurial > hg
annotate mercurial/ancestor.py @ 35816:f6ca1e11d8b4 stable
revset: evaluate filesets against each revision for 'file()' (issue5778)
After f2aeff8a87b6, the fileset was evaluated to a set of files against the
working directory, and then those files were applied against each revision. The
result was nonsense. For example, `hg log -r 'file("set:exec()")'` on the
Mercurial repo listed revision 0 because it has the `hg` script, which is
currently +x. But that bit wasn't applied until revision 280 (which
'contains()' properly indicates).
This technique was borrowed from checkstatus(), which services adds(),
modifies(), and removes(), so it seems safe enough. The 'r:' case is explicitly
assigned to wdirrev, freeing up rev=None to mean "re-evaluate at each revision".
The distinction is important to avoid behavior changes with `hg log set:...`
(test-largefiles-misc.t and test-fileset-generated.t drop current log output
without this). I'm not sure what the right behavior for that is (1fd352aa08fc
explicitly enabled this behavior for graphlog), but the day before the release
isn't the time to experiment.
author | Matt Harbison <matt_harbison@yahoo.com> |
---|---|
date | Sun, 28 Jan 2018 14:08:59 -0500 |
parents | bd872f64a8ba |
children | f8b46245b26a |
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 |
32291
bd872f64a8ba
cleanup: use set literals
Martin von Zweigbergk <martinvonz@google.com>
parents:
31476
diff
changeset
|
50 return {v} |
21101
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
51 if sv < poison: |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
52 for p in pfunc(v): |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
53 sp = seen[p] |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
54 if p == nullrev: |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
55 continue |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
56 if sp == 0: |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
57 seen[p] = sv |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
58 interesting += 1 |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
59 elif sp != sv: |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
60 seen[p] |= sv |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
61 else: |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
62 for p in pfunc(v): |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
63 if p == nullrev: |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
64 continue |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
65 sp = seen[p] |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
66 if sp and sp < poison: |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
67 interesting -= 1 |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
68 seen[p] = sv |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
69 return gca |
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
70 |
18986
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
71 def ancestors(pfunc, *orignodes): |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
72 """ |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
73 Returns the common ancestors of a and b that are furthest from a |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
74 root (as measured by longest path). |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
75 |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
76 pfunc must return a list of parent vertices for a given vertex. |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
77 """ |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
78 def deepest(nodes): |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
79 interesting = {} |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
80 count = max(nodes) + 1 |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
81 depth = [0] * count |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
82 seen = [0] * count |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
83 mapping = [] |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
84 for (i, n) in enumerate(sorted(nodes)): |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
85 depth[n] = 1 |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
86 b = 1 << i |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
87 seen[n] = b |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
88 interesting[b] = 1 |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
89 mapping.append((b, n)) |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
90 nv = count - 1 |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
91 while nv >= 0 and len(interesting) > 1: |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
92 v = nv |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
93 nv -= 1 |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
94 dv = depth[v] |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
95 if dv == 0: |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
96 continue |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
97 sv = seen[v] |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
98 for p in pfunc(v): |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
99 if p == nullrev: |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
100 continue |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
101 dp = depth[p] |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
102 nsp = sp = seen[p] |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
103 if dp <= dv: |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
104 depth[p] = dv + 1 |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
105 if sp != sv: |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
106 interesting[sv] += 1 |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
107 nsp = seen[p] = sv |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
108 if sp: |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
109 interesting[sp] -= 1 |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
110 if interesting[sp] == 0: |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
111 del interesting[sp] |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
112 elif dv == dp - 1: |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
113 nsp = sp | sv |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
114 if nsp == sp: |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
115 continue |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
116 seen[p] = nsp |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
117 interesting.setdefault(nsp, 0) |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
118 interesting[nsp] += 1 |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
119 interesting[sp] -= 1 |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
120 if interesting[sp] == 0: |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
121 del interesting[sp] |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
122 interesting[sv] -= 1 |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
123 if interesting[sv] == 0: |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
124 del interesting[sv] |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
125 |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
126 if len(interesting) != 1: |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
127 return [] |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
128 |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
129 k = 0 |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
130 for i in interesting: |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
131 k |= i |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
132 return set(n for (i, n) in mapping if k & i) |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
133 |
21101
64911a12dc28
ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents:
20985
diff
changeset
|
134 gca = commonancestorsheads(pfunc, *orignodes) |
18986
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
135 |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
136 if len(gca) <= 1: |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
137 return gca |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
138 return deepest(gca) |
2f7186400a07
ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents:
18091
diff
changeset
|
139 |
23334
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
140 class incrementalmissingancestors(object): |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
141 '''persistent state used to calculate missing ancestors incrementally |
17970
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
142 |
23334
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
143 Although similar in spirit to lazyancestors below, this is a separate class |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
144 because trying to support contains and missingancestors operations with the |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
145 same internal data structures adds needless complexity.''' |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
146 def __init__(self, pfunc, bases): |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
147 self.bases = set(bases) |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
148 if not self.bases: |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
149 self.bases.add(nullrev) |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
150 self.pfunc = pfunc |
17970
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
151 |
23340
83225aff0265
ancestor: add a way to test whether a missing ancestor object has bases
Siddharth Agarwal <sid0@fb.com>
parents:
23339
diff
changeset
|
152 def hasbases(self): |
83225aff0265
ancestor: add a way to test whether a missing ancestor object has bases
Siddharth Agarwal <sid0@fb.com>
parents:
23339
diff
changeset
|
153 '''whether the common set has any non-trivial bases''' |
32291
bd872f64a8ba
cleanup: use set literals
Martin von Zweigbergk <martinvonz@google.com>
parents:
31476
diff
changeset
|
154 return self.bases and self.bases != {nullrev} |
23340
83225aff0265
ancestor: add a way to test whether a missing ancestor object has bases
Siddharth Agarwal <sid0@fb.com>
parents:
23339
diff
changeset
|
155 |
23341
bcc3012f8477
ancestor: add a way to add to bases of a missing ancestor object
Siddharth Agarwal <sid0@fb.com>
parents:
23340
diff
changeset
|
156 def addbases(self, newbases): |
bcc3012f8477
ancestor: add a way to add to bases of a missing ancestor object
Siddharth Agarwal <sid0@fb.com>
parents:
23340
diff
changeset
|
157 '''grow the ancestor set by adding new bases''' |
bcc3012f8477
ancestor: add a way to add to bases of a missing ancestor object
Siddharth Agarwal <sid0@fb.com>
parents:
23340
diff
changeset
|
158 self.bases.update(newbases) |
bcc3012f8477
ancestor: add a way to add to bases of a missing ancestor object
Siddharth Agarwal <sid0@fb.com>
parents:
23340
diff
changeset
|
159 |
23342
f710644e1ce9
ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents:
23341
diff
changeset
|
160 def removeancestorsfrom(self, revs): |
f710644e1ce9
ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents:
23341
diff
changeset
|
161 '''remove all ancestors of bases from the set revs (in place)''' |
f710644e1ce9
ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents:
23341
diff
changeset
|
162 bases = self.bases |
f710644e1ce9
ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents:
23341
diff
changeset
|
163 pfunc = self.pfunc |
f710644e1ce9
ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents:
23341
diff
changeset
|
164 revs.difference_update(bases) |
f710644e1ce9
ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents:
23341
diff
changeset
|
165 # nullrev is always an ancestor |
f710644e1ce9
ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents:
23341
diff
changeset
|
166 revs.discard(nullrev) |
f710644e1ce9
ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents:
23341
diff
changeset
|
167 if not revs: |
f710644e1ce9
ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents:
23341
diff
changeset
|
168 return |
f710644e1ce9
ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents:
23341
diff
changeset
|
169 # anything in revs > start is definitely not an ancestor of bases |
f710644e1ce9
ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents:
23341
diff
changeset
|
170 # revs <= start needs to be investigated |
f710644e1ce9
ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents:
23341
diff
changeset
|
171 start = max(bases) |
f710644e1ce9
ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents:
23341
diff
changeset
|
172 keepcount = sum(1 for r in revs if r > start) |
f710644e1ce9
ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents:
23341
diff
changeset
|
173 if len(revs) == keepcount: |
f710644e1ce9
ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents:
23341
diff
changeset
|
174 # no revs to consider |
f710644e1ce9
ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents:
23341
diff
changeset
|
175 return |
f710644e1ce9
ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents:
23341
diff
changeset
|
176 |
f710644e1ce9
ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents:
23341
diff
changeset
|
177 for curr in xrange(start, min(revs) - 1, -1): |
f710644e1ce9
ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents:
23341
diff
changeset
|
178 if curr not in bases: |
f710644e1ce9
ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents:
23341
diff
changeset
|
179 continue |
f710644e1ce9
ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents:
23341
diff
changeset
|
180 revs.discard(curr) |
f710644e1ce9
ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents:
23341
diff
changeset
|
181 bases.update(pfunc(curr)) |
f710644e1ce9
ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents:
23341
diff
changeset
|
182 if len(revs) == keepcount: |
f710644e1ce9
ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents:
23341
diff
changeset
|
183 # no more potential revs to discard |
f710644e1ce9
ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents:
23341
diff
changeset
|
184 break |
f710644e1ce9
ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents:
23341
diff
changeset
|
185 |
23334
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
186 def missingancestors(self, revs): |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
187 '''return all the ancestors of revs that are not ancestors of self.bases |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
188 |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
189 This may include elements from revs. |
17970
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
190 |
23334
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
191 Equivalent to the revset (::revs - ::self.bases). Revs are returned in |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
192 revision number order, which is a topological order.''' |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
193 revsvisit = set(revs) |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
194 basesvisit = self.bases |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
195 pfunc = self.pfunc |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
196 bothvisit = revsvisit.intersection(basesvisit) |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
197 revsvisit.difference_update(bothvisit) |
17970
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
198 if not revsvisit: |
23334
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
199 return [] |
17970
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
200 |
23334
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
201 start = max(max(revsvisit), max(basesvisit)) |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
202 # At this point, we hold the invariants that: |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
203 # - revsvisit is the set of nodes we know are an ancestor of at least |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
204 # one of the nodes in revs |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
205 # - basesvisit is the same for bases |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
206 # - bothvisit is the set of nodes we know are ancestors of at least one |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
207 # of the nodes in revs and one of the nodes in bases. bothvisit and |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
208 # revsvisit are mutually exclusive, but bothvisit is a subset of |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
209 # basesvisit. |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
210 # Now we walk down in reverse topo order, adding parents of nodes |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
211 # already visited to the sets while maintaining the invariants. When a |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
212 # node is found in both revsvisit and basesvisit, it is removed from |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
213 # revsvisit and added to bothvisit. When revsvisit becomes empty, there |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
214 # are no more ancestors of revs that aren't also ancestors of bases, so |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
215 # exit. |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
216 |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
217 missing = [] |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
218 for curr in xrange(start, nullrev, -1): |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
219 if not revsvisit: |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
220 break |
17970
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
221 |
23334
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
222 if curr in bothvisit: |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
223 bothvisit.remove(curr) |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
224 # curr's parents might have made it into revsvisit through |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
225 # another path |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
226 for p in pfunc(curr): |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
227 revsvisit.discard(p) |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
228 basesvisit.add(p) |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
229 bothvisit.add(p) |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
230 continue |
17970
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
231 |
23334
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
232 if curr in revsvisit: |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
233 missing.append(curr) |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
234 revsvisit.remove(curr) |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
235 thisvisit = revsvisit |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
236 othervisit = basesvisit |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
237 elif curr in basesvisit: |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
238 thisvisit = basesvisit |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
239 othervisit = revsvisit |
17970
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
240 else: |
23334
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
241 # not an ancestor of revs or bases: ignore |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
242 continue |
17970
0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents:
14494
diff
changeset
|
243 |
23334
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
244 for p in pfunc(curr): |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
245 if p == nullrev: |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
246 pass |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
247 elif p in othervisit or p in bothvisit: |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
248 # p is implicitly in thisvisit. This means p is or should be |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
249 # in bothvisit |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
250 revsvisit.discard(p) |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
251 basesvisit.add(p) |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
252 bothvisit.add(p) |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
253 else: |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
254 # visit later |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
255 thisvisit.add(p) |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
256 |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
257 missing.reverse() |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
258 return missing |
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23333
diff
changeset
|
259 |
18090
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
260 class lazyancestors(object): |
23328
3a7d9c0c57a5
ancestor.lazyancestors: take parentrevs function rather than changelog
Siddharth Agarwal <sid0@fb.com>
parents:
22225
diff
changeset
|
261 def __init__(self, pfunc, revs, stoprev=0, inclusive=False): |
18090
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
262 """Create a new object generating ancestors for the given revs. Does |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
263 not generate revs lower than stoprev. |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
264 |
18091
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
265 This is computed lazily starting from revs. The object supports |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
266 iteration and membership. |
18090
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
267 |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
268 cl should be a changelog and revs should be an iterable. inclusive is |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
269 a boolean that indicates whether revs should be included. Revs lower |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
270 than stoprev will not be generated. |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
271 |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
272 Result does not include the null revision.""" |
23328
3a7d9c0c57a5
ancestor.lazyancestors: take parentrevs function rather than changelog
Siddharth Agarwal <sid0@fb.com>
parents:
22225
diff
changeset
|
273 self._parentrevs = pfunc |
18090
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
274 self._initrevs = revs |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
275 self._stoprev = stoprev |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
276 self._inclusive = inclusive |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
277 |
18091
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
278 # Initialize data structures for __contains__. |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
279 # For __contains__, we use a heap rather than a deque because |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
280 # (a) it minimizes the number of parentrevs calls made |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
281 # (b) it makes the loop termination condition obvious |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
282 # Python's heap is a min-heap. Multiply all values by -1 to convert it |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
283 # into a max-heap. |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
284 self._containsvisit = [-rev for rev in revs] |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
285 heapq.heapify(self._containsvisit) |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
286 if inclusive: |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
287 self._containsseen = set(revs) |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
288 else: |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
289 self._containsseen = set() |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
290 |
22225
baecf4e1b7d0
ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
21101
diff
changeset
|
291 def __nonzero__(self): |
baecf4e1b7d0
ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
21101
diff
changeset
|
292 """False if the set is empty, True otherwise.""" |
baecf4e1b7d0
ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
21101
diff
changeset
|
293 try: |
29216
ead25aa27a43
py3: convert to next() function
timeless <timeless@mozdev.org>
parents:
25915
diff
changeset
|
294 next(iter(self)) |
22225
baecf4e1b7d0
ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
21101
diff
changeset
|
295 return True |
baecf4e1b7d0
ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
21101
diff
changeset
|
296 except StopIteration: |
baecf4e1b7d0
ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
21101
diff
changeset
|
297 return False |
baecf4e1b7d0
ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
21101
diff
changeset
|
298 |
31476
413b44003462
py3: add __bool__ to every class defining __nonzero__
Gregory Szorc <gregory.szorc@gmail.com>
parents:
29216
diff
changeset
|
299 __bool__ = __nonzero__ |
413b44003462
py3: add __bool__ to every class defining __nonzero__
Gregory Szorc <gregory.szorc@gmail.com>
parents:
29216
diff
changeset
|
300 |
18090
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
301 def __iter__(self): |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
302 """Generate the ancestors of _initrevs in reverse topological order. |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
303 |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
304 If inclusive is False, yield a sequence of revision numbers starting |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
305 with the parents of each revision in revs, i.e., each revision is *not* |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
306 considered an ancestor of itself. Results are in breadth-first order: |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
307 parents of each rev in revs, then parents of those, etc. |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
308 |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
309 If inclusive is True, yield all the revs first (ignoring stoprev), |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
310 then yield all the ancestors of revs as when inclusive is False. |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
311 If an element in revs is an ancestor of a different rev it is not |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
312 yielded again.""" |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
313 seen = set() |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
314 revs = self._initrevs |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
315 if self._inclusive: |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
316 for rev in revs: |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
317 yield rev |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
318 seen.update(revs) |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
319 |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
320 parentrevs = self._parentrevs |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
321 stoprev = self._stoprev |
25113
0ca8410ea345
util: drop alias for collections.deque
Martin von Zweigbergk <martinvonz@google.com>
parents:
23342
diff
changeset
|
322 visit = collections.deque(revs) |
18090
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
323 |
25639
7125225a5287
ancestors: prefetch method outside of the loop
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
25113
diff
changeset
|
324 see = seen.add |
7125225a5287
ancestors: prefetch method outside of the loop
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
25113
diff
changeset
|
325 schedule = visit.append |
7125225a5287
ancestors: prefetch method outside of the loop
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
25113
diff
changeset
|
326 |
18090
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
327 while visit: |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
328 for parent in parentrevs(visit.popleft()): |
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
329 if parent >= stoprev and parent not in seen: |
25639
7125225a5287
ancestors: prefetch method outside of the loop
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
25113
diff
changeset
|
330 schedule(parent) |
7125225a5287
ancestors: prefetch method outside of the loop
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
25113
diff
changeset
|
331 see(parent) |
18090
9abc55ef85b5
revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
332 yield parent |
18091
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
333 |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
334 def __contains__(self, target): |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
335 """Test whether target is an ancestor of self._initrevs.""" |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
336 # Trying to do both __iter__ and __contains__ using the same visit |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
337 # heap and seen set is complex enough that it slows down both. Keep |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
338 # them separate. |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
339 seen = self._containsseen |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
340 if target in seen: |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
341 return True |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
342 |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
343 parentrevs = self._parentrevs |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
344 visit = self._containsvisit |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
345 stoprev = self._stoprev |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
346 heappop = heapq.heappop |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
347 heappush = heapq.heappush |
25639
7125225a5287
ancestors: prefetch method outside of the loop
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
25113
diff
changeset
|
348 see = seen.add |
18091
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
349 |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
350 targetseen = False |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
351 |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
352 while visit and -visit[0] > target and not targetseen: |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
353 for parent in parentrevs(-heappop(visit)): |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
354 if parent < stoprev or parent in seen: |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
355 continue |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
356 # We need to make sure we push all parents into the heap so |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
357 # that we leave it in a consistent state for future calls. |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
358 heappush(visit, -parent) |
25639
7125225a5287
ancestors: prefetch method outside of the loop
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
25113
diff
changeset
|
359 see(parent) |
18091
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
360 if parent == target: |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
361 targetseen = True |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
362 |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18090
diff
changeset
|
363 return targetseen |