author | Pierre-Yves David <pierre-yves.david@ens-lyon.org> |
Fri, 24 Mar 2017 11:27:56 +0100 | |
changeset 2235 | eadb1c69e350 |
parent 2234 | 16a5a37ced62 |
child 2236 | c0e2ba85e76a |
permissions | -rw-r--r-- |
2125
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
1 |
# Code dedicated to the computation and properties of "stable ranges" |
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
2 |
# |
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
3 |
# These stable ranges are use for obsolescence markers discovery |
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
4 |
# |
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
5 |
# Copyright 2017 Pierre-Yves David <pierre-yves.david@ens-lyon.org> |
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
6 |
# |
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
7 |
# This software may be used and distributed according to the terms of the |
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
8 |
# GNU General Public License version 2 or any later version. |
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
9 |
|
2129
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
10 |
import collections |
2223
2ba541e1ea01
stablerange: add warming of the subrange
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2222
diff
changeset
|
11 |
import heapq |
2130
d784622dd5dc
stablerange: move the range class in the new module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2129
diff
changeset
|
12 |
import math |
d784622dd5dc
stablerange: move the range class in the new module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2129
diff
changeset
|
13 |
|
2125
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
14 |
from mercurial import ( |
2129
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
15 |
commands, |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
16 |
cmdutil, |
2125
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
17 |
localrepo, |
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
18 |
node as nodemod, |
2129
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
19 |
scmutil, |
2125
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
20 |
) |
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
21 |
|
2129
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
22 |
from mercurial.i18n import _ |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
23 |
|
2125
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
24 |
from . import ( |
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
25 |
exthelper, |
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
26 |
) |
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
27 |
|
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
28 |
eh = exthelper.exthelper() |
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
29 |
|
2129
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
30 |
################################## |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
31 |
### Stable topological sorting ### |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
32 |
################################## |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
33 |
@eh.command( |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
34 |
'debugstablesort', |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
35 |
[ |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
36 |
('', 'rev', [], 'heads to start from'), |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
37 |
] + commands.formatteropts, |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
38 |
_('')) |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
39 |
def debugstablesort(ui, repo, **opts): |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
40 |
"""display the ::REVS set topologically sorted in a stable way |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
41 |
""" |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
42 |
revs = scmutil.revrange(repo, opts['rev']) |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
43 |
displayer = cmdutil.show_changeset(ui, repo, opts, buffered=True) |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
44 |
for r in stablesort(repo, revs): |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
45 |
ctx = repo[r] |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
46 |
displayer.show(ctx) |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
47 |
displayer.flush(ctx) |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
48 |
displayer.close() |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
49 |
|
2212
afb35ad42040
stablesort: allow a callback to be triggered on merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2211
diff
changeset
|
50 |
def stablesort(repo, revs, mergecallback=None): |
2129
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
51 |
"""return '::revs' topologically sorted in "stable" order |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
52 |
|
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
53 |
This is a depth first traversal starting from 'nullrev', using node as a |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
54 |
tie breaker. |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
55 |
""" |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
56 |
# Various notes: |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
57 |
# |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
58 |
# * Bitbucket is used dates as tie breaker, that might be a good idea. |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
59 |
# |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
60 |
# * It seemds we can traverse in the same order from (one) head to bottom, |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
61 |
# if we the following record data for each merge: |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
62 |
# |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
63 |
# - highest (stablesort-wise) common ancestors, |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
64 |
# - order of parents (tablesort-wise) |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
65 |
cl = repo.changelog |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
66 |
parents = cl.parentrevs |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
67 |
nullrev = nodemod.nullrev |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
68 |
n = cl.node |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
69 |
# step 1: We need a parents -> children mapping for 2 reasons. |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
70 |
# |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
71 |
# * we build the order from nullrev to tip |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
72 |
# |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
73 |
# * we need to detect branching |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
74 |
children = collections.defaultdict(list) |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
75 |
for r in cl.ancestors(revs, inclusive=True): |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
76 |
p1, p2 = parents(r) |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
77 |
children[p1].append(r) |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
78 |
if p2 != nullrev: |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
79 |
children[p2].append(r) |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
80 |
# step two: walk back up |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
81 |
# * pick lowest node in case of branching |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
82 |
# * stack disregarded part of the branching |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
83 |
# * process merge when both parents are yielded |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
84 |
|
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
85 |
# track what changeset has been |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
86 |
seen = [0] * (max(revs) + 2) |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
87 |
seen[-1] = True # nullrev is known |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
88 |
# starts from repository roots |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
89 |
# reuse the list form the mapping as we won't need it again anyway |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
90 |
stack = children[nullrev] |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
91 |
if not stack: |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
92 |
return [] |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
93 |
if 1 < len(stack): |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
94 |
stack.sort(key=n, reverse=True) |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
95 |
|
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
96 |
# list of rev, maybe we should yield, but since we built a children mapping we are 'O(N)' already |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
97 |
result = [] |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
98 |
|
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
99 |
current = stack.pop() |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
100 |
while current is not None or stack: |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
101 |
if current is None: |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
102 |
# previous iteration reached a merge or an unready merge, |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
103 |
current = stack.pop() |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
104 |
if seen[current]: |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
105 |
current = None |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
106 |
continue |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
107 |
p1, p2 = parents(current) |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
108 |
if not (seen[p1] and seen[p2]): |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
109 |
# we can't iterate on this merge yet because other child is not |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
110 |
# yielded yet (and we are topo sorting) we can discard it for now |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
111 |
# because it will be reached from the other child. |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
112 |
current = None |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
113 |
continue |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
114 |
assert not seen[current] |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
115 |
seen[current] = True |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
116 |
result.append(current) # could be yield, cf earlier comment |
2212
afb35ad42040
stablesort: allow a callback to be triggered on merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2211
diff
changeset
|
117 |
if mergecallback is not None and p2 != nullrev: |
afb35ad42040
stablesort: allow a callback to be triggered on merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2211
diff
changeset
|
118 |
mergecallback(result, current) |
2129
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
119 |
cs = children[current] |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
120 |
if not cs: |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
121 |
current = None |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
122 |
elif 1 == len(cs): |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
123 |
current = cs[0] |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
124 |
else: |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
125 |
cs.sort(key=n, reverse=True) |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
126 |
current = cs.pop() # proceed on smallest |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
127 |
stack.extend(cs) # stack the rest for later |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
128 |
assert len(result) == len(set(result)) |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
129 |
return result |
d07bb7cbae2f
stablesort: move into the stablerange module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2128
diff
changeset
|
130 |
|
2130
d784622dd5dc
stablerange: move the range class in the new module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2129
diff
changeset
|
131 |
################################# |
d784622dd5dc
stablerange: move the range class in the new module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2129
diff
changeset
|
132 |
### Stable Range computation ### |
d784622dd5dc
stablerange: move the range class in the new module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2129
diff
changeset
|
133 |
################################# |
d784622dd5dc
stablerange: move the range class in the new module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2129
diff
changeset
|
134 |
|
2198
ab392bd1c518
stablerange: move a utility function around
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2197
diff
changeset
|
135 |
def _hlp2(i): |
ab392bd1c518
stablerange: move a utility function around
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2197
diff
changeset
|
136 |
"""return highest power of two lower than 'i'""" |
ab392bd1c518
stablerange: move a utility function around
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2197
diff
changeset
|
137 |
return 2 ** int(math.log(i - 1, 2)) |
ab392bd1c518
stablerange: move a utility function around
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2197
diff
changeset
|
138 |
|
2137
dd8ed58bf79c
stablerange: move the subrangesclosure inside the module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2136
diff
changeset
|
139 |
def subrangesclosure(repo, heads): |
dd8ed58bf79c
stablerange: move the subrangesclosure inside the module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2136
diff
changeset
|
140 |
"""set of all standard subrange under heads |
dd8ed58bf79c
stablerange: move the subrangesclosure inside the module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2136
diff
changeset
|
141 |
|
dd8ed58bf79c
stablerange: move the subrangesclosure inside the module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2136
diff
changeset
|
142 |
This is intended for debug purposes. Range are returned from largest to |
dd8ed58bf79c
stablerange: move the subrangesclosure inside the module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2136
diff
changeset
|
143 |
smallest in terms of number of revision it contains.""" |
2176
f5e1e43915a1
stablerange: use subranges from the main class in subrangesclosure
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2173
diff
changeset
|
144 |
subranges = repo.stablerange.subranges |
2196
2ecc88baabf9
stablerange: directly use tuple to refer to a stable range
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2194
diff
changeset
|
145 |
toproceed = [(r, 0, ) for r in heads] |
2137
dd8ed58bf79c
stablerange: move the subrangesclosure inside the module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2136
diff
changeset
|
146 |
ranges = set(toproceed) |
dd8ed58bf79c
stablerange: move the subrangesclosure inside the module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2136
diff
changeset
|
147 |
while toproceed: |
dd8ed58bf79c
stablerange: move the subrangesclosure inside the module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2136
diff
changeset
|
148 |
entry = toproceed.pop() |
2176
f5e1e43915a1
stablerange: use subranges from the main class in subrangesclosure
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2173
diff
changeset
|
149 |
for r in subranges(repo, entry): |
2137
dd8ed58bf79c
stablerange: move the subrangesclosure inside the module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2136
diff
changeset
|
150 |
if r not in ranges: |
dd8ed58bf79c
stablerange: move the subrangesclosure inside the module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2136
diff
changeset
|
151 |
ranges.add(r) |
dd8ed58bf79c
stablerange: move the subrangesclosure inside the module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2136
diff
changeset
|
152 |
toproceed.append(r) |
dd8ed58bf79c
stablerange: move the subrangesclosure inside the module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2136
diff
changeset
|
153 |
ranges = list(ranges) |
2142
7dc66a526b21
stablerange: stop using '.node' in subrangesclosure
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2141
diff
changeset
|
154 |
n = repo.changelog.node |
2167
d37f0423c072
stablerange: use rangelength in subrangesclosure
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2163
diff
changeset
|
155 |
rangelength = repo.stablerange.rangelength |
d37f0423c072
stablerange: use rangelength in subrangesclosure
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2163
diff
changeset
|
156 |
ranges.sort(key=lambda r: (-rangelength(repo, r), n(r[0]))) |
2137
dd8ed58bf79c
stablerange: move the subrangesclosure inside the module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2136
diff
changeset
|
157 |
return ranges |
dd8ed58bf79c
stablerange: move the subrangesclosure inside the module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2136
diff
changeset
|
158 |
|
2231
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
159 |
@eh.command( |
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
160 |
'debugstablerange', |
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
161 |
[ |
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
162 |
('', 'rev', [], 'operate on (rev, 0) ranges for rev in REVS'), |
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
163 |
('', 'subranges', False, 'recursively display data for subranges too'), |
2232
6b95bcc402fe
debugstablerange: add a --verify flag to the command
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2231
diff
changeset
|
164 |
('', 'verify', False, 'checks subranges content (EXPENSIVE)'), |
2231
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
165 |
], |
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
166 |
_('')) |
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
167 |
def debugstablerange(ui, repo, **opts): |
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
168 |
"""display standard stable subrange for a set of ranges |
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
169 |
|
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
170 |
Range as displayed as '<node>-<index> (<rev>, <depth>, <length>)', use |
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
171 |
--verbose to get the extra details in (). |
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
172 |
""" |
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
173 |
short = nodemod.short |
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
174 |
revs = scmutil.revrange(repo, opts['rev']) |
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
175 |
# prewarm depth cache |
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
176 |
unfi = repo.unfiltered() |
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
177 |
node = unfi.changelog.node |
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
178 |
stablerange = unfi.stablerange |
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
179 |
depth = stablerange.depthrev |
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
180 |
length = stablerange.rangelength |
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
181 |
subranges = stablerange.subranges |
2233
e922cd76804a
stablerange: warmup all upto a revision
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2232
diff
changeset
|
182 |
repo.stablerange.warmup(repo, max(revs)) |
2231
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
183 |
if opts['subranges']: |
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
184 |
ranges = subrangesclosure(repo, revs) |
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
185 |
else: |
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
186 |
ranges = [(r, 0) for r in revs] |
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
187 |
if ui.verbose: |
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
188 |
template = '%s-%d (%d, %d, %d)' |
2232
6b95bcc402fe
debugstablerange: add a --verify flag to the command
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2231
diff
changeset
|
189 |
|
2231
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
190 |
def _rangestring(repo, rangeid): |
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
191 |
return template % ( |
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
192 |
short(node(rangeid[0])), |
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
193 |
rangeid[1], |
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
194 |
rangeid[0], |
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
195 |
depth(unfi, rangeid[0]), |
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
196 |
length(unfi, rangeid) |
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
197 |
) |
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
198 |
else: |
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
199 |
template = '%s-%d' |
2232
6b95bcc402fe
debugstablerange: add a --verify flag to the command
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2231
diff
changeset
|
200 |
|
2231
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
201 |
def _rangestring(repo, rangeid): |
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
202 |
return template % ( |
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
203 |
short(node(rangeid[0])), |
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
204 |
rangeid[1], |
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
205 |
) |
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
206 |
|
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
207 |
for r in ranges: |
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
208 |
subs = subranges(unfi, r) |
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
209 |
subsstr = ', '.join(_rangestring(unfi, s) for s in subs) |
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
210 |
rstr = _rangestring(unfi, r) |
2232
6b95bcc402fe
debugstablerange: add a --verify flag to the command
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2231
diff
changeset
|
211 |
if opts['verify']: |
6b95bcc402fe
debugstablerange: add a --verify flag to the command
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2231
diff
changeset
|
212 |
status = 'leaf' |
6b95bcc402fe
debugstablerange: add a --verify flag to the command
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2231
diff
changeset
|
213 |
if 1 < length(unfi, r): |
6b95bcc402fe
debugstablerange: add a --verify flag to the command
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2231
diff
changeset
|
214 |
status = 'complete' |
6b95bcc402fe
debugstablerange: add a --verify flag to the command
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2231
diff
changeset
|
215 |
revs = set(stablerange.revsfromrange(unfi, r)) |
6b95bcc402fe
debugstablerange: add a --verify flag to the command
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2231
diff
changeset
|
216 |
subrevs = set() |
6b95bcc402fe
debugstablerange: add a --verify flag to the command
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2231
diff
changeset
|
217 |
for s in subs: |
6b95bcc402fe
debugstablerange: add a --verify flag to the command
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2231
diff
changeset
|
218 |
subrevs.update(stablerange.revsfromrange(unfi, s)) |
6b95bcc402fe
debugstablerange: add a --verify flag to the command
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2231
diff
changeset
|
219 |
if revs != subrevs: |
6b95bcc402fe
debugstablerange: add a --verify flag to the command
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2231
diff
changeset
|
220 |
status = 'missing' |
6b95bcc402fe
debugstablerange: add a --verify flag to the command
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2231
diff
changeset
|
221 |
ui.status('%s [%s] - %s\n' % (rstr, status, subsstr)) |
6b95bcc402fe
debugstablerange: add a --verify flag to the command
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2231
diff
changeset
|
222 |
else: |
6b95bcc402fe
debugstablerange: add a --verify flag to the command
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2231
diff
changeset
|
223 |
ui.status('%s - %s\n' % (rstr, subsstr)) |
2231
f872738bb5b3
stablerange: add a proper debugstablerange commands
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2227
diff
changeset
|
224 |
|
2200
d5a216dce71c
stablerange: rename the class
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2199
diff
changeset
|
225 |
class stablerange(object): |
2125
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
226 |
|
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
227 |
def __init__(self): |
2235
eadb1c69e350
stablerange: support loading the cache iteratively
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2234
diff
changeset
|
228 |
# The point up to which we have data in cache |
eadb1c69e350
stablerange: support loading the cache iteratively
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2234
diff
changeset
|
229 |
self._tiprev = None |
eadb1c69e350
stablerange: support loading the cache iteratively
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2234
diff
changeset
|
230 |
self._tipnode = None |
2234
16a5a37ced62
stablerange: add some basic documentation about the cache
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2233
diff
changeset
|
231 |
# cache the 'depth' of a changeset, the size of '::rev' |
2125
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
232 |
self._depthcache = {} |
2234
16a5a37ced62
stablerange: add some basic documentation about the cache
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2233
diff
changeset
|
233 |
# cache the standard stable subranges or a range |
2127
e2770faac2df
stablerange: move the subrange cache into our new class
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2126
diff
changeset
|
234 |
self._subrangescache = {} |
2184
3ec0be20e365
stablerange: add a cache for stablesort ordering
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2183
diff
changeset
|
235 |
# To slices merge, we need to walk their descendant in reverse stable |
3ec0be20e365
stablerange: add a cache for stablesort ordering
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2183
diff
changeset
|
236 |
# sort order. For now we perform a full stable sort their descendant |
3ec0be20e365
stablerange: add a cache for stablesort ordering
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2183
diff
changeset
|
237 |
# and then use the relevant top most part. This order is going to be |
3ec0be20e365
stablerange: add a cache for stablesort ordering
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2183
diff
changeset
|
238 |
# the same for all ranges headed at the same merge. So we cache these |
3ec0be20e365
stablerange: add a cache for stablesort ordering
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2183
diff
changeset
|
239 |
# value to reuse them accross the same invocation. |
3ec0be20e365
stablerange: add a cache for stablesort ordering
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2183
diff
changeset
|
240 |
self._stablesortcache = {} |
2213
fb2937b0dd49
revsfromrange: reuse information from the stablesort
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2212
diff
changeset
|
241 |
# something useful to compute the above |
fb2937b0dd49
revsfromrange: reuse information from the stablesort
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2212
diff
changeset
|
242 |
# mergerev -> stablesort, length |
fb2937b0dd49
revsfromrange: reuse information from the stablesort
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2212
diff
changeset
|
243 |
self._stablesortprepared = {} |
2209
d25d39b88c7f
stablerange: cache parents
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2208
diff
changeset
|
244 |
# caching parent call # as we do so many of them |
d25d39b88c7f
stablerange: cache parents
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2208
diff
changeset
|
245 |
self._parentscache = {} |
2220
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
246 |
# The first part of the stable sorted list of revision of a merge will |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
247 |
# shared with the one of others. This means we can reuse subranges |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
248 |
# computed from that point to compute some of the subranges from the |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
249 |
# merge. |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
250 |
self._inheritancecache = {} |
2184
3ec0be20e365
stablerange: add a cache for stablesort ordering
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2183
diff
changeset
|
251 |
|
2233
e922cd76804a
stablerange: warmup all upto a revision
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2232
diff
changeset
|
252 |
def warmup(self, repo, upto=None): |
e922cd76804a
stablerange: warmup all upto a revision
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2232
diff
changeset
|
253 |
"""warm the cache up""" |
2201
8d371329e8b9
stablecache: warmup on unfiltered repository
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2200
diff
changeset
|
254 |
repo = repo.unfiltered() |
2235
eadb1c69e350
stablerange: support loading the cache iteratively
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2234
diff
changeset
|
255 |
cl = repo.changelog |
2223
2ba541e1ea01
stablerange: add warming of the subrange
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2222
diff
changeset
|
256 |
# subrange should be warmed from head to range to be able to benefit |
2ba541e1ea01
stablerange: add warming of the subrange
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2222
diff
changeset
|
257 |
# from revsfromrange cache. otherwise each merge will trigger its own |
2ba541e1ea01
stablerange: add warming of the subrange
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2222
diff
changeset
|
258 |
# stablesort. |
2ba541e1ea01
stablerange: add warming of the subrange
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2222
diff
changeset
|
259 |
# |
2ba541e1ea01
stablerange: add warming of the subrange
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2222
diff
changeset
|
260 |
# we use the revnumber as an approximation for depth |
2ba541e1ea01
stablerange: add warming of the subrange
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2222
diff
changeset
|
261 |
ui = repo.ui |
2ba541e1ea01
stablerange: add warming of the subrange
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2222
diff
changeset
|
262 |
|
2235
eadb1c69e350
stablerange: support loading the cache iteratively
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2234
diff
changeset
|
263 |
if upto is None: |
eadb1c69e350
stablerange: support loading the cache iteratively
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2234
diff
changeset
|
264 |
upto = len(cl) - 1 |
eadb1c69e350
stablerange: support loading the cache iteratively
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2234
diff
changeset
|
265 |
if self._tiprev is None: |
eadb1c69e350
stablerange: support loading the cache iteratively
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2234
diff
changeset
|
266 |
revs = cl.revs(stop=upto) |
2233
e922cd76804a
stablerange: warmup all upto a revision
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2232
diff
changeset
|
267 |
nbrevs = upto + 1 |
e922cd76804a
stablerange: warmup all upto a revision
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2232
diff
changeset
|
268 |
else: |
2235
eadb1c69e350
stablerange: support loading the cache iteratively
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2234
diff
changeset
|
269 |
assert cl.node(self._tiprev) == self._tipnode |
eadb1c69e350
stablerange: support loading the cache iteratively
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2234
diff
changeset
|
270 |
if upto <= self._tiprev: |
eadb1c69e350
stablerange: support loading the cache iteratively
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2234
diff
changeset
|
271 |
return |
eadb1c69e350
stablerange: support loading the cache iteratively
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2234
diff
changeset
|
272 |
revs = cl.revs(start=self._tiprev + 1, stop=upto) |
eadb1c69e350
stablerange: support loading the cache iteratively
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2234
diff
changeset
|
273 |
nbrevs = upto - self._tiprev |
2223
2ba541e1ea01
stablerange: add warming of the subrange
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2222
diff
changeset
|
274 |
rangeheap = [] |
2ba541e1ea01
stablerange: add warming of the subrange
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2222
diff
changeset
|
275 |
for idx, r in enumerate(revs): |
2ba541e1ea01
stablerange: add warming of the subrange
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2222
diff
changeset
|
276 |
if not idx % 1000: |
2ba541e1ea01
stablerange: add warming of the subrange
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2222
diff
changeset
|
277 |
ui.progress(_("filling depth cache"), idx, total=nbrevs) |
2ba541e1ea01
stablerange: add warming of the subrange
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2222
diff
changeset
|
278 |
# warm up depth |
2135
8f63f4b1c33e
stablerange: add an official warmup function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2134
diff
changeset
|
279 |
self.depthrev(repo, r) |
2223
2ba541e1ea01
stablerange: add warming of the subrange
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2222
diff
changeset
|
280 |
rangeheap.append((-r, (r, 0))) |
2ba541e1ea01
stablerange: add warming of the subrange
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2222
diff
changeset
|
281 |
ui.progress(_("filling depth cache"), None, total=nbrevs) |
2ba541e1ea01
stablerange: add warming of the subrange
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2222
diff
changeset
|
282 |
|
2ba541e1ea01
stablerange: add warming of the subrange
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2222
diff
changeset
|
283 |
heappop = heapq.heappop |
2ba541e1ea01
stablerange: add warming of the subrange
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2222
diff
changeset
|
284 |
heappush = heapq.heappush |
2ba541e1ea01
stablerange: add warming of the subrange
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2222
diff
changeset
|
285 |
heapify = heapq.heapify |
2ba541e1ea01
stablerange: add warming of the subrange
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2222
diff
changeset
|
286 |
|
2ba541e1ea01
stablerange: add warming of the subrange
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2222
diff
changeset
|
287 |
original = set(rangeheap) |
2ba541e1ea01
stablerange: add warming of the subrange
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2222
diff
changeset
|
288 |
seen = 0 |
2ba541e1ea01
stablerange: add warming of the subrange
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2222
diff
changeset
|
289 |
heapify(rangeheap) |
2ba541e1ea01
stablerange: add warming of the subrange
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2222
diff
changeset
|
290 |
while rangeheap: |
2ba541e1ea01
stablerange: add warming of the subrange
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2222
diff
changeset
|
291 |
value = heappop(rangeheap) |
2ba541e1ea01
stablerange: add warming of the subrange
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2222
diff
changeset
|
292 |
if value in original: |
2ba541e1ea01
stablerange: add warming of the subrange
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2222
diff
changeset
|
293 |
if not seen % 1000: |
2ba541e1ea01
stablerange: add warming of the subrange
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2222
diff
changeset
|
294 |
ui.progress(_("filling stablerange cache"), seen, total=nbrevs) |
2ba541e1ea01
stablerange: add warming of the subrange
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2222
diff
changeset
|
295 |
seen += 1 |
2ba541e1ea01
stablerange: add warming of the subrange
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2222
diff
changeset
|
296 |
original.remove(value) # might have been added from other source |
2ba541e1ea01
stablerange: add warming of the subrange
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2222
diff
changeset
|
297 |
__, rangeid = value |
2226
83e6933ae00e
subranges: add a utility function to access the cache
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2225
diff
changeset
|
298 |
if self._getsub(rangeid) is None: |
2223
2ba541e1ea01
stablerange: add warming of the subrange
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2222
diff
changeset
|
299 |
for sub in self.subranges(repo, rangeid): |
2226
83e6933ae00e
subranges: add a utility function to access the cache
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2225
diff
changeset
|
300 |
if self._getsub(sub) is None: |
2223
2ba541e1ea01
stablerange: add warming of the subrange
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2222
diff
changeset
|
301 |
heappush(rangeheap, (-sub[0], sub)) |
2ba541e1ea01
stablerange: add warming of the subrange
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2222
diff
changeset
|
302 |
ui.progress(_("filling stablerange cache"), None, total=nbrevs) |
2135
8f63f4b1c33e
stablerange: add an official warmup function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2134
diff
changeset
|
303 |
|
2235
eadb1c69e350
stablerange: support loading the cache iteratively
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2234
diff
changeset
|
304 |
self._tiprev = upto |
eadb1c69e350
stablerange: support loading the cache iteratively
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2234
diff
changeset
|
305 |
self._tipnode = cl.node(upto) |
eadb1c69e350
stablerange: support loading the cache iteratively
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2234
diff
changeset
|
306 |
|
2125
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
307 |
def depthrev(self, repo, rev): |
2126
839e96521c5a
depth: extract code dedicated to depth of a merge in its own function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2125
diff
changeset
|
308 |
repo = repo.unfiltered() |
2125
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
309 |
cl = repo.changelog |
2224
49776d324d1a
depth: add a utility function to access the cache
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2223
diff
changeset
|
310 |
depth = self._getdepth |
2125
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
311 |
nullrev = nodemod.nullrev |
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
312 |
stack = [rev] |
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
313 |
while stack: |
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
314 |
revdepth = None |
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
315 |
current = stack[-1] |
2224
49776d324d1a
depth: add a utility function to access the cache
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2223
diff
changeset
|
316 |
revdepth = depth(current) |
2125
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
317 |
if revdepth is not None: |
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
318 |
stack.pop() |
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
319 |
continue |
2209
d25d39b88c7f
stablerange: cache parents
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2208
diff
changeset
|
320 |
p1, p2 = self._parents(current, cl.parentrevs) |
2125
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
321 |
if p1 == nullrev: |
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
322 |
# root case |
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
323 |
revdepth = 1 |
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
324 |
elif p2 == nullrev: |
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
325 |
# linear commit case |
2224
49776d324d1a
depth: add a utility function to access the cache
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2223
diff
changeset
|
326 |
parentdepth = depth(p1) |
2125
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
327 |
if parentdepth is None: |
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
328 |
stack.append(p1) |
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
329 |
else: |
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
330 |
revdepth = parentdepth + 1 |
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
331 |
else: |
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
332 |
# merge case |
2224
49776d324d1a
depth: add a utility function to access the cache
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2223
diff
changeset
|
333 |
revdepth = self._depthmerge(cl, current, p1, p2, stack) |
2125
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
334 |
if revdepth is not None: |
2225
81f5ebd9e9d0
depth: add a utility function to set the cache
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2224
diff
changeset
|
335 |
self._setdepth(current, revdepth) |
2125
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
336 |
stack.pop() |
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
337 |
# actual_depth = len(list(cl.ancestors([rev], inclusive=True))) |
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
338 |
# assert revdepth == actual_depth, (rev, revdepth, actual_depth) |
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
339 |
return revdepth |
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
340 |
|
2182
884f6309eae7
stablerange: minor method reorders on the main class
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2181
diff
changeset
|
341 |
def rangelength(self, repo, rangeid): |
884f6309eae7
stablerange: minor method reorders on the main class
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2181
diff
changeset
|
342 |
headrev, index = rangeid[0], rangeid[1] |
884f6309eae7
stablerange: minor method reorders on the main class
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2181
diff
changeset
|
343 |
return self.depthrev(repo, headrev) - index |
884f6309eae7
stablerange: minor method reorders on the main class
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2181
diff
changeset
|
344 |
|
884f6309eae7
stablerange: minor method reorders on the main class
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2181
diff
changeset
|
345 |
def subranges(self, repo, rangeid): |
2226
83e6933ae00e
subranges: add a utility function to access the cache
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2225
diff
changeset
|
346 |
cached = self._getsub(rangeid) |
2182
884f6309eae7
stablerange: minor method reorders on the main class
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2181
diff
changeset
|
347 |
if cached is not None: |
884f6309eae7
stablerange: minor method reorders on the main class
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2181
diff
changeset
|
348 |
return cached |
2204
61a8b51348a1
subranges: detach cache logic from computation logic
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2201
diff
changeset
|
349 |
value = self._subranges(repo, rangeid) |
2227
4b621b56e3a1
subranges: add a utility function to set the cache
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2226
diff
changeset
|
350 |
self._setsub(rangeid, value) |
2182
884f6309eae7
stablerange: minor method reorders on the main class
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2181
diff
changeset
|
351 |
return value |
884f6309eae7
stablerange: minor method reorders on the main class
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2181
diff
changeset
|
352 |
|
2183
3c2992afee71
stablerange: move revs computation within the main class
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2182
diff
changeset
|
353 |
def revsfromrange(self, repo, rangeid): |
2210
37bd878d2e58
more explicite name in revsfromrange
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2209
diff
changeset
|
354 |
headrev, index = rangeid |
2211
ecb46c7ee281
minor simplification around rangelength
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2210
diff
changeset
|
355 |
rangelength = self.rangelength(repo, rangeid) |
2214
14e876c5e1c3
stablerange: soon it will not provide any benefit and it gets in the way
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2213
diff
changeset
|
356 |
if rangelength == 1: |
14e876c5e1c3
stablerange: soon it will not provide any benefit and it gets in the way
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2213
diff
changeset
|
357 |
revs = [headrev] |
14e876c5e1c3
stablerange: soon it will not provide any benefit and it gets in the way
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2213
diff
changeset
|
358 |
else: |
14e876c5e1c3
stablerange: soon it will not provide any benefit and it gets in the way
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2213
diff
changeset
|
359 |
# get all revs under heads in stable order |
14e876c5e1c3
stablerange: soon it will not provide any benefit and it gets in the way
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2213
diff
changeset
|
360 |
# |
14e876c5e1c3
stablerange: soon it will not provide any benefit and it gets in the way
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2213
diff
changeset
|
361 |
# note: In the general case we can just walk down and then request |
14e876c5e1c3
stablerange: soon it will not provide any benefit and it gets in the way
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2213
diff
changeset
|
362 |
# data about the merge. But I'm not sure this function will be even |
14e876c5e1c3
stablerange: soon it will not provide any benefit and it gets in the way
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2213
diff
changeset
|
363 |
# call for the general case. |
14e876c5e1c3
stablerange: soon it will not provide any benefit and it gets in the way
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2213
diff
changeset
|
364 |
allrevs = self._stablesortcache.get(headrev) |
14e876c5e1c3
stablerange: soon it will not provide any benefit and it gets in the way
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2213
diff
changeset
|
365 |
if allrevs is None: |
14e876c5e1c3
stablerange: soon it will not provide any benefit and it gets in the way
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2213
diff
changeset
|
366 |
allrevs = self._getrevsfrommerge(repo, headrev) |
2186
57d58f27ffae
revsfromramge: hard code the single changeset range case
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2185
diff
changeset
|
367 |
if allrevs is None: |
2214
14e876c5e1c3
stablerange: soon it will not provide any benefit and it gets in the way
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2213
diff
changeset
|
368 |
allrevs = stablesort(repo, [headrev], |
14e876c5e1c3
stablerange: soon it will not provide any benefit and it gets in the way
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2213
diff
changeset
|
369 |
mergecallback=self._filestablesortcache) |
14e876c5e1c3
stablerange: soon it will not provide any benefit and it gets in the way
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2213
diff
changeset
|
370 |
self._stablesortcache[headrev] = allrevs |
14e876c5e1c3
stablerange: soon it will not provide any benefit and it gets in the way
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2213
diff
changeset
|
371 |
# takes from index |
14e876c5e1c3
stablerange: soon it will not provide any benefit and it gets in the way
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2213
diff
changeset
|
372 |
revs = allrevs[index:] |
2183
3c2992afee71
stablerange: move revs computation within the main class
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2182
diff
changeset
|
373 |
# sanity checks |
2211
ecb46c7ee281
minor simplification around rangelength
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2210
diff
changeset
|
374 |
assert len(revs) == rangelength |
2183
3c2992afee71
stablerange: move revs computation within the main class
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2182
diff
changeset
|
375 |
return revs |
3c2992afee71
stablerange: move revs computation within the main class
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2182
diff
changeset
|
376 |
|
2209
d25d39b88c7f
stablerange: cache parents
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2208
diff
changeset
|
377 |
def _parents(self, rev, func): |
d25d39b88c7f
stablerange: cache parents
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2208
diff
changeset
|
378 |
parents = self._parentscache.get(rev) |
d25d39b88c7f
stablerange: cache parents
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2208
diff
changeset
|
379 |
if parents is None: |
d25d39b88c7f
stablerange: cache parents
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2208
diff
changeset
|
380 |
parents = func(rev) |
d25d39b88c7f
stablerange: cache parents
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2208
diff
changeset
|
381 |
self._parentscache[rev] = parents |
d25d39b88c7f
stablerange: cache parents
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2208
diff
changeset
|
382 |
return parents |
d25d39b88c7f
stablerange: cache parents
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2208
diff
changeset
|
383 |
|
2224
49776d324d1a
depth: add a utility function to access the cache
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2223
diff
changeset
|
384 |
def _getdepth(self, rev): |
49776d324d1a
depth: add a utility function to access the cache
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2223
diff
changeset
|
385 |
"""utility function used to access the depth cache |
49776d324d1a
depth: add a utility function to access the cache
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2223
diff
changeset
|
386 |
|
49776d324d1a
depth: add a utility function to access the cache
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2223
diff
changeset
|
387 |
This mostly exist to help the on disk persistence.""" |
49776d324d1a
depth: add a utility function to access the cache
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2223
diff
changeset
|
388 |
return self._depthcache.get(rev) |
49776d324d1a
depth: add a utility function to access the cache
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2223
diff
changeset
|
389 |
|
2225
81f5ebd9e9d0
depth: add a utility function to set the cache
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2224
diff
changeset
|
390 |
def _setdepth(self, rev, value): |
81f5ebd9e9d0
depth: add a utility function to set the cache
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2224
diff
changeset
|
391 |
"""utility function used to set the depth cache |
81f5ebd9e9d0
depth: add a utility function to set the cache
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2224
diff
changeset
|
392 |
|
81f5ebd9e9d0
depth: add a utility function to set the cache
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2224
diff
changeset
|
393 |
This mostly exist to help the on disk persistence.""" |
81f5ebd9e9d0
depth: add a utility function to set the cache
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2224
diff
changeset
|
394 |
self._depthcache[rev] = value |
81f5ebd9e9d0
depth: add a utility function to set the cache
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2224
diff
changeset
|
395 |
|
2226
83e6933ae00e
subranges: add a utility function to access the cache
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2225
diff
changeset
|
396 |
def _getsub(self, rev): |
83e6933ae00e
subranges: add a utility function to access the cache
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2225
diff
changeset
|
397 |
"""utility function used to access the subranges cache |
83e6933ae00e
subranges: add a utility function to access the cache
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2225
diff
changeset
|
398 |
|
83e6933ae00e
subranges: add a utility function to access the cache
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2225
diff
changeset
|
399 |
This mostly exist to help the on disk persistence""" |
83e6933ae00e
subranges: add a utility function to access the cache
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2225
diff
changeset
|
400 |
return self._subrangescache.get(rev) |
83e6933ae00e
subranges: add a utility function to access the cache
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2225
diff
changeset
|
401 |
|
2227
4b621b56e3a1
subranges: add a utility function to set the cache
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2226
diff
changeset
|
402 |
def _setsub(self, rev, value): |
4b621b56e3a1
subranges: add a utility function to set the cache
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2226
diff
changeset
|
403 |
"""utility function used to set the subranges cache |
4b621b56e3a1
subranges: add a utility function to set the cache
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2226
diff
changeset
|
404 |
|
4b621b56e3a1
subranges: add a utility function to set the cache
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2226
diff
changeset
|
405 |
This mostly exist to help the on disk persistence.""" |
4b621b56e3a1
subranges: add a utility function to set the cache
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2226
diff
changeset
|
406 |
self._subrangescache[rev] = value |
4b621b56e3a1
subranges: add a utility function to set the cache
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2226
diff
changeset
|
407 |
|
2213
fb2937b0dd49
revsfromrange: reuse information from the stablesort
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2212
diff
changeset
|
408 |
def _filestablesortcache(self, sortedrevs, merge): |
fb2937b0dd49
revsfromrange: reuse information from the stablesort
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2212
diff
changeset
|
409 |
if merge not in self._stablesortprepared: |
fb2937b0dd49
revsfromrange: reuse information from the stablesort
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2212
diff
changeset
|
410 |
self._stablesortprepared[merge] = (sortedrevs, len(sortedrevs)) |
fb2937b0dd49
revsfromrange: reuse information from the stablesort
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2212
diff
changeset
|
411 |
|
fb2937b0dd49
revsfromrange: reuse information from the stablesort
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2212
diff
changeset
|
412 |
def _getrevsfrommerge(self, repo, merge): |
fb2937b0dd49
revsfromrange: reuse information from the stablesort
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2212
diff
changeset
|
413 |
prepared = self._stablesortprepared.get(merge) |
fb2937b0dd49
revsfromrange: reuse information from the stablesort
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2212
diff
changeset
|
414 |
if prepared is None: |
fb2937b0dd49
revsfromrange: reuse information from the stablesort
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2212
diff
changeset
|
415 |
return None |
fb2937b0dd49
revsfromrange: reuse information from the stablesort
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2212
diff
changeset
|
416 |
|
fb2937b0dd49
revsfromrange: reuse information from the stablesort
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2212
diff
changeset
|
417 |
mergedepth = self.depthrev(repo, merge) |
fb2937b0dd49
revsfromrange: reuse information from the stablesort
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2212
diff
changeset
|
418 |
allrevs = prepared[0][:prepared[1]] |
fb2937b0dd49
revsfromrange: reuse information from the stablesort
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2212
diff
changeset
|
419 |
nbextrarevs = prepared[1] - mergedepth |
fb2937b0dd49
revsfromrange: reuse information from the stablesort
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2212
diff
changeset
|
420 |
if not nbextrarevs: |
fb2937b0dd49
revsfromrange: reuse information from the stablesort
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2212
diff
changeset
|
421 |
return allrevs |
fb2937b0dd49
revsfromrange: reuse information from the stablesort
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2212
diff
changeset
|
422 |
|
fb2937b0dd49
revsfromrange: reuse information from the stablesort
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2212
diff
changeset
|
423 |
anc = repo.changelog.ancestors([merge], inclusive=True) |
fb2937b0dd49
revsfromrange: reuse information from the stablesort
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2212
diff
changeset
|
424 |
top = [] |
fb2937b0dd49
revsfromrange: reuse information from the stablesort
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2212
diff
changeset
|
425 |
counter = nbextrarevs |
fb2937b0dd49
revsfromrange: reuse information from the stablesort
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2212
diff
changeset
|
426 |
for rev in reversed(allrevs): |
fb2937b0dd49
revsfromrange: reuse information from the stablesort
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2212
diff
changeset
|
427 |
if rev in anc: |
fb2937b0dd49
revsfromrange: reuse information from the stablesort
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2212
diff
changeset
|
428 |
top.append(rev) |
fb2937b0dd49
revsfromrange: reuse information from the stablesort
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2212
diff
changeset
|
429 |
else: |
fb2937b0dd49
revsfromrange: reuse information from the stablesort
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2212
diff
changeset
|
430 |
counter -= 1 |
fb2937b0dd49
revsfromrange: reuse information from the stablesort
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2212
diff
changeset
|
431 |
if counter <= 0: |
fb2937b0dd49
revsfromrange: reuse information from the stablesort
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2212
diff
changeset
|
432 |
break |
fb2937b0dd49
revsfromrange: reuse information from the stablesort
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2212
diff
changeset
|
433 |
|
fb2937b0dd49
revsfromrange: reuse information from the stablesort
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2212
diff
changeset
|
434 |
bottomidx = prepared[1] - (nbextrarevs + len(top)) |
fb2937b0dd49
revsfromrange: reuse information from the stablesort
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2212
diff
changeset
|
435 |
revs = allrevs[:bottomidx] |
fb2937b0dd49
revsfromrange: reuse information from the stablesort
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2212
diff
changeset
|
436 |
revs.extend(reversed(top)) |
fb2937b0dd49
revsfromrange: reuse information from the stablesort
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2212
diff
changeset
|
437 |
return revs |
fb2937b0dd49
revsfromrange: reuse information from the stablesort
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2212
diff
changeset
|
438 |
|
2220
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
439 |
def _inheritancepoint(self, repo, merge): |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
440 |
"""Find the inheritance point of a Merge |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
441 |
|
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
442 |
The first part of the stable sorted list of revision of a merge will shared with |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
443 |
the one of others. This means we can reuse subranges computed from that point to |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
444 |
compute some of the subranges from the merge. |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
445 |
|
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
446 |
That point is latest point in the stable sorted list where the depth of the |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
447 |
revisions match its index (that means all revision earlier in the stable sorted |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
448 |
list are its ancestors, no dangling unrelated branches exists). |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
449 |
""" |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
450 |
value = self._inheritancecache.get(merge) |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
451 |
if value is None: |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
452 |
revs = self.revsfromrange(repo, (merge, 0)) |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
453 |
i = reversed(revs) |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
454 |
i.next() # pop the merge |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
455 |
expected = len(revs) - 1 |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
456 |
# Since we do warmup properly, we can expect the cache to be hot |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
457 |
# for everythin under the merge we investigate |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
458 |
cache = self._depthcache |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
459 |
# note: we cannot do a binary search because element under the |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
460 |
# inherited point might have mismatching depth because of inner |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
461 |
# branching. |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
462 |
for rev in i: |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
463 |
if cache[rev] == expected: |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
464 |
break |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
465 |
expected -= 1 |
2221
f61d091d318e
stablerange: small style fix
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2220
diff
changeset
|
466 |
value = (expected - 1, rev) |
2220
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
467 |
self._inheritancecache[merge] = value |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
468 |
return value |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
469 |
|
2224
49776d324d1a
depth: add a utility function to access the cache
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2223
diff
changeset
|
470 |
def _depthmerge(self, cl, rev, p1, p2, stack): |
2126
839e96521c5a
depth: extract code dedicated to depth of a merge in its own function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2125
diff
changeset
|
471 |
# sub method to simplify the main 'depthrev' one |
839e96521c5a
depth: extract code dedicated to depth of a merge in its own function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2125
diff
changeset
|
472 |
revdepth = None |
2224
49776d324d1a
depth: add a utility function to access the cache
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2223
diff
changeset
|
473 |
depth = self._getdepth |
49776d324d1a
depth: add a utility function to access the cache
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2223
diff
changeset
|
474 |
depth_p1 = depth(p1) |
49776d324d1a
depth: add a utility function to access the cache
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2223
diff
changeset
|
475 |
depth_p2 = depth(p2) |
2126
839e96521c5a
depth: extract code dedicated to depth of a merge in its own function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2125
diff
changeset
|
476 |
missingparent = False |
839e96521c5a
depth: extract code dedicated to depth of a merge in its own function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2125
diff
changeset
|
477 |
if depth_p1 is None: |
839e96521c5a
depth: extract code dedicated to depth of a merge in its own function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2125
diff
changeset
|
478 |
stack.append(p1) |
839e96521c5a
depth: extract code dedicated to depth of a merge in its own function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2125
diff
changeset
|
479 |
missingparent = True |
839e96521c5a
depth: extract code dedicated to depth of a merge in its own function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2125
diff
changeset
|
480 |
if depth_p2 is None: |
839e96521c5a
depth: extract code dedicated to depth of a merge in its own function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2125
diff
changeset
|
481 |
stack.append(p2) |
839e96521c5a
depth: extract code dedicated to depth of a merge in its own function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2125
diff
changeset
|
482 |
missingparent = True |
839e96521c5a
depth: extract code dedicated to depth of a merge in its own function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2125
diff
changeset
|
483 |
if missingparent: |
839e96521c5a
depth: extract code dedicated to depth of a merge in its own function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2125
diff
changeset
|
484 |
return None |
839e96521c5a
depth: extract code dedicated to depth of a merge in its own function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2125
diff
changeset
|
485 |
# computin depth of a merge |
839e96521c5a
depth: extract code dedicated to depth of a merge in its own function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2125
diff
changeset
|
486 |
# XXX the common ancestors heads could be cached |
839e96521c5a
depth: extract code dedicated to depth of a merge in its own function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2125
diff
changeset
|
487 |
ancnodes = cl.commonancestorsheads(cl.node(p1), cl.node(p2)) |
839e96521c5a
depth: extract code dedicated to depth of a merge in its own function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2125
diff
changeset
|
488 |
ancrevs = [cl.rev(a) for a in ancnodes] |
839e96521c5a
depth: extract code dedicated to depth of a merge in its own function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2125
diff
changeset
|
489 |
anyunkown = False |
839e96521c5a
depth: extract code dedicated to depth of a merge in its own function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2125
diff
changeset
|
490 |
ancdepth = [] |
839e96521c5a
depth: extract code dedicated to depth of a merge in its own function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2125
diff
changeset
|
491 |
for r in ancrevs: |
2224
49776d324d1a
depth: add a utility function to access the cache
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2223
diff
changeset
|
492 |
d = depth(r) |
2126
839e96521c5a
depth: extract code dedicated to depth of a merge in its own function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2125
diff
changeset
|
493 |
if d is None: |
839e96521c5a
depth: extract code dedicated to depth of a merge in its own function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2125
diff
changeset
|
494 |
anyunkown = True |
839e96521c5a
depth: extract code dedicated to depth of a merge in its own function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2125
diff
changeset
|
495 |
stack.append(r) |
839e96521c5a
depth: extract code dedicated to depth of a merge in its own function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2125
diff
changeset
|
496 |
ancdepth.append((r, d)) |
839e96521c5a
depth: extract code dedicated to depth of a merge in its own function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2125
diff
changeset
|
497 |
if anyunkown: |
839e96521c5a
depth: extract code dedicated to depth of a merge in its own function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2125
diff
changeset
|
498 |
return None |
839e96521c5a
depth: extract code dedicated to depth of a merge in its own function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2125
diff
changeset
|
499 |
if not ancrevs: |
839e96521c5a
depth: extract code dedicated to depth of a merge in its own function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2125
diff
changeset
|
500 |
# unrelated branch, (no common root) |
839e96521c5a
depth: extract code dedicated to depth of a merge in its own function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2125
diff
changeset
|
501 |
revdepth = depth_p1 + depth_p2 + 1 |
839e96521c5a
depth: extract code dedicated to depth of a merge in its own function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2125
diff
changeset
|
502 |
elif len(ancrevs) == 1: |
839e96521c5a
depth: extract code dedicated to depth of a merge in its own function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2125
diff
changeset
|
503 |
# one unique branch point: |
839e96521c5a
depth: extract code dedicated to depth of a merge in its own function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2125
diff
changeset
|
504 |
# we can compute depth without any walk |
839e96521c5a
depth: extract code dedicated to depth of a merge in its own function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2125
diff
changeset
|
505 |
depth_anc = ancdepth[0][1] |
839e96521c5a
depth: extract code dedicated to depth of a merge in its own function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2125
diff
changeset
|
506 |
revdepth = depth_p1 + (depth_p2 - depth_anc) + 1 |
839e96521c5a
depth: extract code dedicated to depth of a merge in its own function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2125
diff
changeset
|
507 |
else: |
839e96521c5a
depth: extract code dedicated to depth of a merge in its own function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2125
diff
changeset
|
508 |
# multiple ancestors, we pick one that is |
839e96521c5a
depth: extract code dedicated to depth of a merge in its own function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2125
diff
changeset
|
509 |
# * the deepest (less changeset outside of it), |
839e96521c5a
depth: extract code dedicated to depth of a merge in its own function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2125
diff
changeset
|
510 |
# * lowest revs because more chance to have descendant of other "above" |
839e96521c5a
depth: extract code dedicated to depth of a merge in its own function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2125
diff
changeset
|
511 |
anc, revdepth = max(ancdepth, key=lambda x: (x[1], -x[0])) |
839e96521c5a
depth: extract code dedicated to depth of a merge in its own function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2125
diff
changeset
|
512 |
revdepth += len(cl.findmissingrevs(common=[anc], heads=[rev])) |
839e96521c5a
depth: extract code dedicated to depth of a merge in its own function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2125
diff
changeset
|
513 |
return revdepth |
839e96521c5a
depth: extract code dedicated to depth of a merge in its own function
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2125
diff
changeset
|
514 |
|
2204
61a8b51348a1
subranges: detach cache logic from computation logic
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2201
diff
changeset
|
515 |
def _subranges(self, repo, rangeid): |
61a8b51348a1
subranges: detach cache logic from computation logic
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2201
diff
changeset
|
516 |
if self.rangelength(repo, rangeid) == 1: |
61a8b51348a1
subranges: detach cache logic from computation logic
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2201
diff
changeset
|
517 |
return [] |
61a8b51348a1
subranges: detach cache logic from computation logic
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2201
diff
changeset
|
518 |
slicepoint = self._slicepoint(repo, rangeid) |
2205
bd5e2496e5cd
subranges: remove the recursivity of the call to isubranges(parentrange)
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2204
diff
changeset
|
519 |
|
bd5e2496e5cd
subranges: remove the recursivity of the call to isubranges(parentrange)
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2204
diff
changeset
|
520 |
# make sure we have cache for all relevant parent first to prevent |
bd5e2496e5cd
subranges: remove the recursivity of the call to isubranges(parentrange)
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2204
diff
changeset
|
521 |
# recursion (python is bad with recursion |
bd5e2496e5cd
subranges: remove the recursivity of the call to isubranges(parentrange)
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2204
diff
changeset
|
522 |
stack = [] |
bd5e2496e5cd
subranges: remove the recursivity of the call to isubranges(parentrange)
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2204
diff
changeset
|
523 |
current = rangeid |
bd5e2496e5cd
subranges: remove the recursivity of the call to isubranges(parentrange)
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2204
diff
changeset
|
524 |
while current is not None: |
2219
d83bf4773433
stablerange: rearrange the code picking subrange to warm
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2218
diff
changeset
|
525 |
current = self._cold_reusable(repo, current, slicepoint) |
2205
bd5e2496e5cd
subranges: remove the recursivity of the call to isubranges(parentrange)
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2204
diff
changeset
|
526 |
if current is not None: |
bd5e2496e5cd
subranges: remove the recursivity of the call to isubranges(parentrange)
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2204
diff
changeset
|
527 |
stack.append(current) |
bd5e2496e5cd
subranges: remove the recursivity of the call to isubranges(parentrange)
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2204
diff
changeset
|
528 |
while stack: |
bd5e2496e5cd
subranges: remove the recursivity of the call to isubranges(parentrange)
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2204
diff
changeset
|
529 |
# these call will directly compute the subranges |
bd5e2496e5cd
subranges: remove the recursivity of the call to isubranges(parentrange)
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2204
diff
changeset
|
530 |
self.subranges(repo, stack.pop()) |
2204
61a8b51348a1
subranges: detach cache logic from computation logic
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2201
diff
changeset
|
531 |
return self._slicesrangeat(repo, rangeid, slicepoint) |
61a8b51348a1
subranges: detach cache logic from computation logic
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2201
diff
changeset
|
532 |
|
2219
d83bf4773433
stablerange: rearrange the code picking subrange to warm
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2218
diff
changeset
|
533 |
def _cold_reusable(self, repo, rangeid, slicepoint): |
2205
bd5e2496e5cd
subranges: remove the recursivity of the call to isubranges(parentrange)
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2204
diff
changeset
|
534 |
"""return parent range that it would be useful to prepare to slice |
bd5e2496e5cd
subranges: remove the recursivity of the call to isubranges(parentrange)
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2204
diff
changeset
|
535 |
rangeid at slicepoint |
bd5e2496e5cd
subranges: remove the recursivity of the call to isubranges(parentrange)
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2204
diff
changeset
|
536 |
|
bd5e2496e5cd
subranges: remove the recursivity of the call to isubranges(parentrange)
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2204
diff
changeset
|
537 |
This function also have the important task to update the revscache of |
2220
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
538 |
the parent rev s if possible and needed""" |
2209
d25d39b88c7f
stablerange: cache parents
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2208
diff
changeset
|
539 |
p1, p2 = self._parents(rangeid[0], repo.changelog.parentrevs) |
2220
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
540 |
if p2 == nodemod.nullrev: |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
541 |
# regular changesets, we pick the parent |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
542 |
reusablerev = p1 |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
543 |
else: |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
544 |
# merge, we try the inheritance point |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
545 |
# if it is too low, it will be ditched by the depth check anyway |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
546 |
index, reusablerev = self._inheritancepoint(repo, rangeid[0]) |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
547 |
|
2219
d83bf4773433
stablerange: rearrange the code picking subrange to warm
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2218
diff
changeset
|
548 |
# if we reached the slicepoint, no need to go further |
d83bf4773433
stablerange: rearrange the code picking subrange to warm
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2218
diff
changeset
|
549 |
if self.depthrev(repo, reusablerev) <= slicepoint: |
d83bf4773433
stablerange: rearrange the code picking subrange to warm
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2218
diff
changeset
|
550 |
return None |
d83bf4773433
stablerange: rearrange the code picking subrange to warm
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2218
diff
changeset
|
551 |
|
d83bf4773433
stablerange: rearrange the code picking subrange to warm
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2218
diff
changeset
|
552 |
reurange = (reusablerev, rangeid[1]) |
2205
bd5e2496e5cd
subranges: remove the recursivity of the call to isubranges(parentrange)
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2204
diff
changeset
|
553 |
# if we have an entry for the current range, lets update the cache |
bd5e2496e5cd
subranges: remove the recursivity of the call to isubranges(parentrange)
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2204
diff
changeset
|
554 |
# if we already have subrange for this range, no need to prepare it. |
2226
83e6933ae00e
subranges: add a utility function to access the cache
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2225
diff
changeset
|
555 |
if self._getsub(reurange) is not None: |
2205
bd5e2496e5cd
subranges: remove the recursivity of the call to isubranges(parentrange)
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2204
diff
changeset
|
556 |
return None |
2219
d83bf4773433
stablerange: rearrange the code picking subrange to warm
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2218
diff
changeset
|
557 |
|
2205
bd5e2496e5cd
subranges: remove the recursivity of the call to isubranges(parentrange)
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2204
diff
changeset
|
558 |
# look like we found a relevent parentrange with no cache yet |
2219
d83bf4773433
stablerange: rearrange the code picking subrange to warm
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2218
diff
changeset
|
559 |
return reurange |
2205
bd5e2496e5cd
subranges: remove the recursivity of the call to isubranges(parentrange)
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2204
diff
changeset
|
560 |
|
2132
d77262807411
stablerange: move standard slice point definition in main class
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2131
diff
changeset
|
561 |
def _slicepoint(self, repo, rangeid): |
2152
c00fb215cd80
stablerange: stop using '.head' in '_slicepoint'
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2151
diff
changeset
|
562 |
rangedepth = self.depthrev(repo, rangeid[0]) |
2132
d77262807411
stablerange: move standard slice point definition in main class
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2131
diff
changeset
|
563 |
step = _hlp2(rangedepth) |
d77262807411
stablerange: move standard slice point definition in main class
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2131
diff
changeset
|
564 |
standard_start = 0 |
2160
66b774ed1335
stablerange: stop using '.index' in '_slicepoint'
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2159
diff
changeset
|
565 |
while standard_start < rangeid[1] and 0 < step: |
2132
d77262807411
stablerange: move standard slice point definition in main class
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2131
diff
changeset
|
566 |
if standard_start + step < rangedepth: |
d77262807411
stablerange: move standard slice point definition in main class
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2131
diff
changeset
|
567 |
standard_start += step |
d77262807411
stablerange: move standard slice point definition in main class
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2131
diff
changeset
|
568 |
step //= 2 |
2160
66b774ed1335
stablerange: stop using '.index' in '_slicepoint'
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2159
diff
changeset
|
569 |
if rangeid[1] == standard_start: |
2168
3012d4ddfb23
stablerange: use rangelength in '_slicepoint'
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2167
diff
changeset
|
570 |
slicesize = _hlp2(self.rangelength(repo, rangeid)) |
2160
66b774ed1335
stablerange: stop using '.index' in '_slicepoint'
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2159
diff
changeset
|
571 |
slicepoint = rangeid[1] + slicesize |
2132
d77262807411
stablerange: move standard slice point definition in main class
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2131
diff
changeset
|
572 |
else: |
d77262807411
stablerange: move standard slice point definition in main class
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2131
diff
changeset
|
573 |
assert standard_start < rangedepth |
d77262807411
stablerange: move standard slice point definition in main class
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2131
diff
changeset
|
574 |
slicepoint = standard_start |
d77262807411
stablerange: move standard slice point definition in main class
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2131
diff
changeset
|
575 |
return slicepoint |
d77262807411
stablerange: move standard slice point definition in main class
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2131
diff
changeset
|
576 |
|
2131
86dd39478638
stablerange: move the slicing method on the central class
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2130
diff
changeset
|
577 |
def _slicesrangeat(self, repo, rangeid, globalindex): |
2209
d25d39b88c7f
stablerange: cache parents
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2208
diff
changeset
|
578 |
p1, p2 = self._parents(rangeid[0], repo.changelog.parentrevs) |
2220
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
579 |
if p2 == nodemod.nullrev: |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
580 |
reuserev = p1 |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
581 |
else: |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
582 |
index, reuserev = self._inheritancepoint(repo, rangeid[0]) |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
583 |
if index < globalindex: |
0b6745b91d6d
merge-slicing: introduce and use "inheritance point" for merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2219
diff
changeset
|
584 |
return self._slicesrangeatmerge(repo, rangeid, globalindex) |
2136
086a85c37e9e
stablerange: compute subranges from parent when possible
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2135
diff
changeset
|
585 |
|
2218
9e30934d4487
stablerange: rearrange the reusing logic to prepare to merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2217
diff
changeset
|
586 |
assert reuserev != nodemod.nullrev |
9e30934d4487
stablerange: rearrange the reusing logic to prepare to merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2217
diff
changeset
|
587 |
|
9e30934d4487
stablerange: rearrange the reusing logic to prepare to merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2217
diff
changeset
|
588 |
reuserange = (reuserev, rangeid[1]) |
9e30934d4487
stablerange: rearrange the reusing logic to prepare to merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2217
diff
changeset
|
589 |
top = (rangeid[0], globalindex) |
2187
c583efbaec78
revsfromrange: update cache for parentrange directly in the code
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2186
diff
changeset
|
590 |
|
2218
9e30934d4487
stablerange: rearrange the reusing logic to prepare to merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2217
diff
changeset
|
591 |
if rangeid[1] + self.rangelength(repo, reuserange) == globalindex: |
9e30934d4487
stablerange: rearrange the reusing logic to prepare to merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2217
diff
changeset
|
592 |
return [reuserange, top] |
9e30934d4487
stablerange: rearrange the reusing logic to prepare to merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2217
diff
changeset
|
593 |
# This will not initiate a recursion since we took appropriate |
9e30934d4487
stablerange: rearrange the reusing logic to prepare to merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2217
diff
changeset
|
594 |
# precaution in the caller of this method to ensure it will be so. |
9e30934d4487
stablerange: rearrange the reusing logic to prepare to merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2217
diff
changeset
|
595 |
# It the parent is a merge that will not be the case but computing |
9e30934d4487
stablerange: rearrange the reusing logic to prepare to merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2217
diff
changeset
|
596 |
# subranges from a merge will not recurse. |
9e30934d4487
stablerange: rearrange the reusing logic to prepare to merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2217
diff
changeset
|
597 |
reusesubranges = self.subranges(repo, reuserange) |
9e30934d4487
stablerange: rearrange the reusing logic to prepare to merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2217
diff
changeset
|
598 |
slices = reusesubranges[:-1] # pop the top |
9e30934d4487
stablerange: rearrange the reusing logic to prepare to merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2217
diff
changeset
|
599 |
slices.append(top) |
9e30934d4487
stablerange: rearrange the reusing logic to prepare to merge
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2217
diff
changeset
|
600 |
return slices |
2136
086a85c37e9e
stablerange: compute subranges from parent when possible
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2135
diff
changeset
|
601 |
|
2169
03baabcd1b9e
stablerange: use rangelength in '_slicesatrange'
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2168
diff
changeset
|
602 |
def _slicesrangeatmerge(self, repo, rangeid, globalindex): |
2161
0a06f5cbca4b
stablerange: stop using '.index' in '_slicesrangeat'
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2160
diff
changeset
|
603 |
localindex = globalindex - rangeid[1] |
2131
86dd39478638
stablerange: move the slicing method on the central class
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2130
diff
changeset
|
604 |
cl = repo.changelog |
86dd39478638
stablerange: move the slicing method on the central class
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2130
diff
changeset
|
605 |
|
86dd39478638
stablerange: move the slicing method on the central class
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2130
diff
changeset
|
606 |
result = [] |
2190
f4cc3cf27a3a
revsfromrange: remove reference to '_revs' in merge slicing
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2189
diff
changeset
|
607 |
allrevs = self.revsfromrange(repo, rangeid) |
f4cc3cf27a3a
revsfromrange: remove reference to '_revs' in merge slicing
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2189
diff
changeset
|
608 |
bottomrevs = allrevs[:localindex] |
2215
6d9cadc635d5
merge-slicing: simplify various aspect of the code
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2214
diff
changeset
|
609 |
|
6d9cadc635d5
merge-slicing: simplify various aspect of the code
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2214
diff
changeset
|
610 |
if globalindex == self.depthrev(repo, bottomrevs[-1]): |
6d9cadc635d5
merge-slicing: simplify various aspect of the code
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2214
diff
changeset
|
611 |
# simple case, top revision in the bottom set contains exactly the |
6d9cadc635d5
merge-slicing: simplify various aspect of the code
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2214
diff
changeset
|
612 |
# revision we needs |
6d9cadc635d5
merge-slicing: simplify various aspect of the code
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2214
diff
changeset
|
613 |
result.append((bottomrevs[-1], rangeid[1])) |
2131
86dd39478638
stablerange: move the slicing method on the central class
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2130
diff
changeset
|
614 |
else: |
86dd39478638
stablerange: move the slicing method on the central class
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2130
diff
changeset
|
615 |
parentrevs = cl.parentrevs |
2209
d25d39b88c7f
stablerange: cache parents
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2208
diff
changeset
|
616 |
parents = self._parents |
2217
37fa3d83f294
merge-slicing: explain an alternative implementation in a comments
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2216
diff
changeset
|
617 |
bheads = set(bottomrevs) |
2131
86dd39478638
stablerange: move the slicing method on the central class
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2130
diff
changeset
|
618 |
du = bheads.difference_update |
2216
de76219b42b8
merge-slicing: use reachable roots to filter the various branches
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2215
diff
changeset
|
619 |
reachableroots = repo.changelog.reachableroots |
2222
6b19998242ed
stablerange: fix merge slicing when range has multiple roots
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2221
diff
changeset
|
620 |
minrev = min(bottomrevs) |
2190
f4cc3cf27a3a
revsfromrange: remove reference to '_revs' in merge slicing
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2189
diff
changeset
|
621 |
for r in bottomrevs: |
2209
d25d39b88c7f
stablerange: cache parents
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2208
diff
changeset
|
622 |
du(parents(r, parentrevs)) |
2131
86dd39478638
stablerange: move the slicing method on the central class
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2130
diff
changeset
|
623 |
for h in bheads: |
2216
de76219b42b8
merge-slicing: use reachable roots to filter the various branches
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2215
diff
changeset
|
624 |
# reachable roots is fast because is C |
de76219b42b8
merge-slicing: use reachable roots to filter the various branches
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2215
diff
changeset
|
625 |
# |
de76219b42b8
merge-slicing: use reachable roots to filter the various branches
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2215
diff
changeset
|
626 |
# It is worth noting that will use this kind of filtering from |
de76219b42b8
merge-slicing: use reachable roots to filter the various branches
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2215
diff
changeset
|
627 |
# "h" multiple time in a warming run. So using "ancestors" and |
de76219b42b8
merge-slicing: use reachable roots to filter the various branches
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2215
diff
changeset
|
628 |
# caching that should be faster. But python code filtering on |
de76219b42b8
merge-slicing: use reachable roots to filter the various branches
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2215
diff
changeset
|
629 |
# the ancestors end up being slower. |
2222
6b19998242ed
stablerange: fix merge slicing when range has multiple roots
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2221
diff
changeset
|
630 |
hrevs = reachableroots(minrev, [h], bottomrevs, True) |
2194
8e7b2918e1a3
stablerange: directly use 'self' when possible
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2193
diff
changeset
|
631 |
start = self.depthrev(repo, h) - len(hrevs) |
2196
2ecc88baabf9
stablerange: directly use tuple to refer to a stable range
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2194
diff
changeset
|
632 |
entry = (h, start) |
2131
86dd39478638
stablerange: move the slicing method on the central class
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2130
diff
changeset
|
633 |
result.append(entry) |
2217
37fa3d83f294
merge-slicing: explain an alternative implementation in a comments
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2216
diff
changeset
|
634 |
|
37fa3d83f294
merge-slicing: explain an alternative implementation in a comments
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2216
diff
changeset
|
635 |
# Talking about python code being slow, the following code is an |
37fa3d83f294
merge-slicing: explain an alternative implementation in a comments
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2216
diff
changeset
|
636 |
# alternative implementation. |
37fa3d83f294
merge-slicing: explain an alternative implementation in a comments
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2216
diff
changeset
|
637 |
# |
37fa3d83f294
merge-slicing: explain an alternative implementation in a comments
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2216
diff
changeset
|
638 |
# It complexity is better since is does a single traversal on the |
37fa3d83f294
merge-slicing: explain an alternative implementation in a comments
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2216
diff
changeset
|
639 |
# bottomset. However since it is all python it end up being |
37fa3d83f294
merge-slicing: explain an alternative implementation in a comments
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2216
diff
changeset
|
640 |
# slower. |
37fa3d83f294
merge-slicing: explain an alternative implementation in a comments
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2216
diff
changeset
|
641 |
# I'm keeping it here as an inspiration for a future C version |
37fa3d83f294
merge-slicing: explain an alternative implementation in a comments
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2216
diff
changeset
|
642 |
# branches = [] |
37fa3d83f294
merge-slicing: explain an alternative implementation in a comments
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2216
diff
changeset
|
643 |
# for current in reversed(bottomrevs): |
37fa3d83f294
merge-slicing: explain an alternative implementation in a comments
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2216
diff
changeset
|
644 |
# ps = parents(current, parentrevs) |
37fa3d83f294
merge-slicing: explain an alternative implementation in a comments
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2216
diff
changeset
|
645 |
# found = False |
37fa3d83f294
merge-slicing: explain an alternative implementation in a comments
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2216
diff
changeset
|
646 |
# for brevs, bexpect in branches: |
37fa3d83f294
merge-slicing: explain an alternative implementation in a comments
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2216
diff
changeset
|
647 |
# if current in bexpect: |
37fa3d83f294
merge-slicing: explain an alternative implementation in a comments
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2216
diff
changeset
|
648 |
# found = True |
37fa3d83f294
merge-slicing: explain an alternative implementation in a comments
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2216
diff
changeset
|
649 |
# brevs.append(current) |
37fa3d83f294
merge-slicing: explain an alternative implementation in a comments
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2216
diff
changeset
|
650 |
# bexpect.discard(current) |
37fa3d83f294
merge-slicing: explain an alternative implementation in a comments
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2216
diff
changeset
|
651 |
# bexpect.update(ps) |
37fa3d83f294
merge-slicing: explain an alternative implementation in a comments
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2216
diff
changeset
|
652 |
# if not found: |
37fa3d83f294
merge-slicing: explain an alternative implementation in a comments
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2216
diff
changeset
|
653 |
# branches.append(([current], set(ps))) |
37fa3d83f294
merge-slicing: explain an alternative implementation in a comments
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2216
diff
changeset
|
654 |
# for revs, __ in reversed(branches): |
37fa3d83f294
merge-slicing: explain an alternative implementation in a comments
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2216
diff
changeset
|
655 |
# head = revs[0] |
37fa3d83f294
merge-slicing: explain an alternative implementation in a comments
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2216
diff
changeset
|
656 |
# index = self.depthrev(repo, head) - len(revs) |
37fa3d83f294
merge-slicing: explain an alternative implementation in a comments
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2216
diff
changeset
|
657 |
# result.append((head, index)) |
37fa3d83f294
merge-slicing: explain an alternative implementation in a comments
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2216
diff
changeset
|
658 |
|
2215
6d9cadc635d5
merge-slicing: simplify various aspect of the code
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2214
diff
changeset
|
659 |
# top part is trivial |
6d9cadc635d5
merge-slicing: simplify various aspect of the code
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2214
diff
changeset
|
660 |
top = (rangeid[0], globalindex) |
2131
86dd39478638
stablerange: move the slicing method on the central class
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2130
diff
changeset
|
661 |
result.append(top) |
86dd39478638
stablerange: move the slicing method on the central class
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2130
diff
changeset
|
662 |
return result |
86dd39478638
stablerange: move the slicing method on the central class
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2130
diff
changeset
|
663 |
|
2125
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
664 |
@eh.reposetup |
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
665 |
def setupcache(ui, repo): |
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
666 |
|
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
667 |
class stablerangerepo(repo.__class__): |
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
668 |
|
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
669 |
@localrepo.unfilteredpropertycache |
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
670 |
def stablerange(self): |
2200
d5a216dce71c
stablerange: rename the class
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
2199
diff
changeset
|
671 |
return stablerange() |
2125
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
672 |
|
e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff
changeset
|
673 |
repo.__class__ = stablerangerepo |