Show More
|
1 | NO CONTENT: new file 100644 |
@@ -0,0 +1,110 b'' | |||
|
1 | # stabletailsort.py - stable ordering of revisions | |
|
2 | # | |
|
3 | # Copyright 2021-2023 Pacien TRAN-GIRARD <pacien.trangirard@pacien.net> | |
|
4 | # | |
|
5 | # This software may be used and distributed according to the terms of the | |
|
6 | # GNU General Public License version 2 or any later version. | |
|
7 | ||
|
8 | """ | |
|
9 | Stable-tail sort computation. | |
|
10 | ||
|
11 | The "stable-tail sort", or STS, is a reverse topological ordering of the | |
|
12 | ancestors of a node, which tends to share large suffixes with the stable-tail | |
|
13 | sort of ancestors and other nodes, giving it its name. | |
|
14 | ||
|
15 | Its properties should make it suitable for making chunks of ancestors with high | |
|
16 | reuse and incrementality for example. | |
|
17 | ||
|
18 | This module and implementation are experimental. Most functions are not yet | |
|
19 | optimised to operate on large production graphs. | |
|
20 | """ | |
|
21 | ||
|
22 | import itertools | |
|
23 | from ..node import nullrev | |
|
24 | from .. import ancestor | |
|
25 | ||
|
26 | ||
|
27 | def _sorted_parents(cl, p1, p2): | |
|
28 | """ | |
|
29 | Chooses and returns the pair (px, pt) from (p1, p2). | |
|
30 | ||
|
31 | Where | |
|
32 | "px" denotes the parent starting the "exclusive" part, and | |
|
33 | "pt" denotes the parent starting the "Tail" part. | |
|
34 | ||
|
35 | "px" is chosen as the parent with the lowest rank with the goal of | |
|
36 | minimising the size of the exclusive part and maximise the size of the | |
|
37 | tail part, hopefully reducing the overall complexity of the stable sort. | |
|
38 | ||
|
39 | In case of equal ranks, the stable node ID is used as a tie-breaker. | |
|
40 | """ | |
|
41 | r1, r2 = cl.fast_rank(p1), cl.fast_rank(p2) | |
|
42 | if r1 < r2: | |
|
43 | return (p1, p2) | |
|
44 | elif r1 > r2: | |
|
45 | return (p2, p1) | |
|
46 | elif cl.node(p1) < cl.node(p2): | |
|
47 | return (p1, p2) | |
|
48 | else: | |
|
49 | return (p2, p1) | |
|
50 | ||
|
51 | ||
|
52 | def _nonoedipal_parent_revs(cl, rev): | |
|
53 | """ | |
|
54 | Returns the non-œdipal parent pair of the given revision. | |
|
55 | ||
|
56 | An œdipal merge is a merge with parents p1, p2 with either | |
|
57 | p1 in ancestors(p2) or p2 in ancestors(p1). | |
|
58 | In the first case, p1 is the œdipal parent. | |
|
59 | In the second case, p2 is the œdipal parent. | |
|
60 | ||
|
61 | Œdipal edges start empty exclusive parts. They do not bring new ancestors. | |
|
62 | As such, they can be skipped when computing any topological sort or any | |
|
63 | iteration over the ancestors of a node. | |
|
64 | ||
|
65 | The œdipal edges are eliminated here using the rank information. | |
|
66 | """ | |
|
67 | p1, p2 = cl.parentrevs(rev) | |
|
68 | if p1 == nullrev or cl.fast_rank(p2) == cl.fast_rank(rev) - 1: | |
|
69 | return p2, nullrev | |
|
70 | elif p2 == nullrev or cl.fast_rank(p1) == cl.fast_rank(rev) - 1: | |
|
71 | return p1, nullrev | |
|
72 | else: | |
|
73 | return p1, p2 | |
|
74 | ||
|
75 | ||
|
76 | def _stable_tail_sort(cl, head_rev): | |
|
77 | """ | |
|
78 | Naive topological iterator of the ancestors given by the stable-tail sort. | |
|
79 | ||
|
80 | The stable-tail sort of a node "h" is defined as the sequence: | |
|
81 | sts(h) := [h] + excl(h) + sts(pt(h)) | |
|
82 | where excl(h) := u for u in sts(px(h)) if u not in ancestors(pt(h)) | |
|
83 | ||
|
84 | This implementation uses a call-stack whose size is | |
|
85 | O(number of open merges). | |
|
86 | ||
|
87 | As such, this implementation exists mainly as a defining reference. | |
|
88 | """ | |
|
89 | cursor_rev = head_rev | |
|
90 | while cursor_rev != nullrev: | |
|
91 | yield cursor_rev | |
|
92 | ||
|
93 | p1, p2 = _nonoedipal_parent_revs(cl, cursor_rev) | |
|
94 | if p1 == nullrev: | |
|
95 | cursor_rev = p2 | |
|
96 | elif p2 == nullrev: | |
|
97 | cursor_rev = p1 | |
|
98 | else: | |
|
99 | px, pt = _sorted_parents(cl, p1, p2) | |
|
100 | ||
|
101 | tail_ancestors = ancestor.lazyancestors( | |
|
102 | cl.parentrevs, (pt,), inclusive=True | |
|
103 | ) | |
|
104 | exclusive_ancestors = ( | |
|
105 | a for a in _stable_tail_sort(cl, px) if a not in tail_ancestors | |
|
106 | ) | |
|
107 | ||
|
108 | excl_part_size = cl.fast_rank(cursor_rev) - cl.fast_rank(pt) - 1 | |
|
109 | yield from itertools.islice(exclusive_ancestors, excl_part_size) | |
|
110 | cursor_rev = pt |
This diff has been collapsed as it changes many lines, (710 lines changed) Show them Hide them | |||
@@ -0,0 +1,710 b'' | |||
|
1 | ==================================== | |
|
2 | Test for the stabletailgraph package | |
|
3 | ==================================== | |
|
4 | ||
|
5 | This test file contains a bunch of small test graphs with some minimal yet | |
|
6 | non-trivial structure, on which the various stable-tail graph and stable-tail | |
|
7 | sort functions are tested. | |
|
8 | ||
|
9 | Each case consists of the creation of the interesting graph structure, followed | |
|
10 | by a check, for each noteworthy node, of: | |
|
11 | - the stable-tail sort output. | |
|
12 | ||
|
13 | In the ASCII art of the diagrams, the side of the exclusive part which is | |
|
14 | followed in priority is denoted with "<" or ">" if it is on the left or right | |
|
15 | respectively. | |
|
16 | ||
|
17 | The intermediary linear parts in the example graph are there to force the | |
|
18 | exclusive part choice (made on a min rank condition). | |
|
19 | ||
|
20 | ||
|
21 | Setup | |
|
22 | ===== | |
|
23 | ||
|
24 | Enable the rank computation to test sorting based on the rank. | |
|
25 | ||
|
26 | $ cat << EOF >> $HGRCPATH | |
|
27 | > [format] | |
|
28 | > exp-use-changelog-v2=enable-unstable-format-and-corrupt-my-data | |
|
29 | > | |
|
30 | > [alias] | |
|
31 | > test-sts = debug::stable-tail-sort -T '{tags},' | |
|
32 | > test-log = log --graph -T '{tags} rank={_fast_rank}' | |
|
33 | > EOF | |
|
34 | ||
|
35 | ||
|
36 | Example 1: single merge node | |
|
37 | ============================ | |
|
38 | ||
|
39 | A base case with one branchpoint "b" and one merge node "e". | |
|
40 | ||
|
41 | The exclusive part, starting with the lowest-ranking parent "c" of "e", | |
|
42 | appears first in stable-tail sort of "e" and "f". | |
|
43 | ||
|
44 | # f | |
|
45 | # | | |
|
46 | # e | |
|
47 | # | | |
|
48 | # --<-- | |
|
49 | # | | | |
|
50 | # c d | |
|
51 | # | | | |
|
52 | # --+-- <- at this point, the sort of "e" is done consuming its | |
|
53 | # | exclusive part [c] and jumps back to its other parent "d" | |
|
54 | # b | |
|
55 | # | | |
|
56 | # a | |
|
57 | ||
|
58 | $ hg init example-1 | |
|
59 | $ cd example-1 | |
|
60 | $ hg debugbuilddag '.:a*a:b*b:c<b+2:d*c/d:e*e:f.' | |
|
61 | $ hg test-log | |
|
62 | o tip rank=8 | |
|
63 | | | |
|
64 | o f rank=7 | |
|
65 | | | |
|
66 | o e rank=6 | |
|
67 | |\ | |
|
68 | | o d rank=4 | |
|
69 | | | | |
|
70 | | o rank=3 | |
|
71 | | | | |
|
72 | o | c rank=3 | |
|
73 | |/ | |
|
74 | o b rank=2 | |
|
75 | | | |
|
76 | o a rank=1 | |
|
77 | ||
|
78 | ||
|
79 | Check the sort of the base linear case. | |
|
80 | ||
|
81 | $ hg test-sts c | |
|
82 | c,b,a, (no-eol) | |
|
83 | ||
|
84 | Check the stable-tail sort of "e": "c" should come before "d". | |
|
85 | ||
|
86 | $ hg test-sts e | |
|
87 | e,c,d,*,b,a, (no-eol) (glob) | |
|
88 | ||
|
89 | Check that the linear descendant of the merge inherits its sort properly. | |
|
90 | ||
|
91 | $ hg test-sts f | |
|
92 | f,e,c,d,*,b,a, (no-eol) (glob) | |
|
93 | ||
|
94 | $ cd .. | |
|
95 | ||
|
96 | ||
|
97 | Example 2: nested exclusive parts, without specific leap | |
|
98 | ======================================================== | |
|
99 | ||
|
100 | "g" is a merge node whose exclusive part contains a merge node "e". | |
|
101 | We check that the stable-tail sort recurses properly by delegating. | |
|
102 | ||
|
103 | Notice that parts of the sort of "e" is an infix of the sort of "g". | |
|
104 | This is an expected property of the sort. | |
|
105 | ||
|
106 | # g | |
|
107 | # | | |
|
108 | # ---<--- | |
|
109 | # | | | |
|
110 | # e | <- while processing the sort in the exclusive part of "g" | |
|
111 | # | | we recursively process the exclusive part of "e" | |
|
112 | # --<-- f | |
|
113 | # | | | | |
|
114 | # c d | | |
|
115 | # | | | | |
|
116 | # --+-- | | |
|
117 | # | | | |
|
118 | # b | | |
|
119 | # | | | |
|
120 | # ---+--- <- done with excl(g), jump to "f" | |
|
121 | # | | |
|
122 | # a | |
|
123 | ||
|
124 | $ hg init example-2 | |
|
125 | $ cd example-2 | |
|
126 | $ hg debugbuilddag '.:a*a:b*b:c<b+2:d*c/d:e<a+6:f*e/f:g.' | |
|
127 | $ hg test-log | |
|
128 | o tip rank=14 | |
|
129 | | | |
|
130 | o g rank=13 | |
|
131 | |\ | |
|
132 | | o f rank=7 | |
|
133 | | | | |
|
134 | | o rank=6 | |
|
135 | | | | |
|
136 | | o rank=5 | |
|
137 | | | | |
|
138 | | o rank=4 | |
|
139 | | | | |
|
140 | | o rank=3 | |
|
141 | | | | |
|
142 | | o rank=2 | |
|
143 | | | | |
|
144 | o | e rank=6 | |
|
145 | |\ \ | |
|
146 | | o | d rank=4 | |
|
147 | | | | | |
|
148 | | o | rank=3 | |
|
149 | | | | | |
|
150 | o | | c rank=3 | |
|
151 | |/ / | |
|
152 | o / b rank=2 | |
|
153 | |/ | |
|
154 | o a rank=1 | |
|
155 | ||
|
156 | Display the sort of "e" for reference | |
|
157 | ||
|
158 | $ hg test-sts e | |
|
159 | e,c,d,*,b,a, (no-eol) (glob) | |
|
160 | ||
|
161 | Check the correctness of the sort of "g", | |
|
162 | and that a part of the sort of "e" appears as an infix. | |
|
163 | ||
|
164 | $ hg test-sts g | |
|
165 | g,e,c,d,*,b,f,*,a, (no-eol) (glob) | |
|
166 | ||
|
167 | $ cd .. | |
|
168 | ||
|
169 | ||
|
170 | Example 3: shadowing of a final leap | |
|
171 | ==================================== | |
|
172 | ||
|
173 | We have a merge "f" whose exclusive part contains a merge "d". | |
|
174 | ||
|
175 | The inherited parent of "d" is not in the exclusive part of "f". | |
|
176 | At the end of the exclusive part of "d", | |
|
177 | the leap to "c" is shadowed by the leap to "e", i.e. the inherited part to "f". | |
|
178 | ||
|
179 | Notice that emitting "c" before "e" would break the reverse topological | |
|
180 | ordering. | |
|
181 | ||
|
182 | # f | |
|
183 | # | | |
|
184 | # ---<--- | |
|
185 | # | | | |
|
186 | # d | | |
|
187 | # | e | |
|
188 | # --<-- | | |
|
189 | # | | | | |
|
190 | # | +---- | |
|
191 | # b | | |
|
192 | # | c | |
|
193 | # | | | |
|
194 | # --+-- <- at this point, jumping to "e", not the shadowed "c" | |
|
195 | # | | |
|
196 | # a | |
|
197 | ||
|
198 | $ hg init example-3 | |
|
199 | $ cd example-3 | |
|
200 | $ hg debugbuilddag '.:a*a:b<a+2:c*b/c:d<c+3:e*d/e:f.' | |
|
201 | $ hg test-log | |
|
202 | o tip rank=10 | |
|
203 | | | |
|
204 | o f rank=9 | |
|
205 | |\ | |
|
206 | | o e rank=6 | |
|
207 | | | | |
|
208 | | o rank=5 | |
|
209 | | | | |
|
210 | | o rank=4 | |
|
211 | | | | |
|
212 | o | d rank=5 | |
|
213 | |\| | |
|
214 | | o c rank=3 | |
|
215 | | | | |
|
216 | | o rank=2 | |
|
217 | | | | |
|
218 | o | b rank=2 | |
|
219 | |/ | |
|
220 | o a rank=1 | |
|
221 | ||
|
222 | ||
|
223 | Display the sort of "d" for reference: | |
|
224 | ||
|
225 | $ hg test-sts d | |
|
226 | d,b,c,*,a, (no-eol) (glob) | |
|
227 | ||
|
228 | Check that we leap from "b" directly to "e" (shadowing the leap to "c"), | |
|
229 | and that "c" is then emitted after "e" (its descendant). | |
|
230 | ||
|
231 | $ hg test-sts f | |
|
232 | f,d,b,e,*,c,*,a, (no-eol) (glob) | |
|
233 | ||
|
234 | $ cd .. | |
|
235 | ||
|
236 | ||
|
237 | Example 4: skipping over nested exclusive part (entirely) | |
|
238 | ========================================================= | |
|
239 | ||
|
240 | We have a merge "f" whose exclusive part contains a merge "d". | |
|
241 | ||
|
242 | The exclusive part of "d" is not in the exclusive part of "f". | |
|
243 | However, some of the inherited part of "d" is part of the exclusive part of "f" | |
|
244 | and needs to be iterated over before leaping to the inherited part of "f". | |
|
245 | ||
|
246 | The sort of "d" is partially reused for the ordering of the exclusive part of | |
|
247 | "f". However the reused part is not contiguous in the sort of "d". | |
|
248 | ||
|
249 | # f | |
|
250 | # | | |
|
251 | # ---<--- | |
|
252 | # | | | |
|
253 | # d | | |
|
254 | # | e | |
|
255 | # -->-- | <- in the sort of "f", we need to skip "c" and leap to the | |
|
256 | # | | | inherited part of "d" | |
|
257 | # | +---- | |
|
258 | # b | | |
|
259 | # | c | |
|
260 | # | | | |
|
261 | # --+-- | |
|
262 | # | | |
|
263 | # a | |
|
264 | ||
|
265 | $ hg init example-4 | |
|
266 | $ cd example-4 | |
|
267 | $ hg debugbuilddag '.:a*a+1:b<a+1:c*b/c:d<c+4:e*d/e:f.' | |
|
268 | $ hg test-log | |
|
269 | o tip rank=11 | |
|
270 | | | |
|
271 | o f rank=10 | |
|
272 | |\ | |
|
273 | | o e rank=6 | |
|
274 | | | | |
|
275 | | o rank=5 | |
|
276 | | | | |
|
277 | | o rank=4 | |
|
278 | | | | |
|
279 | | o rank=3 | |
|
280 | | | | |
|
281 | o | d rank=5 | |
|
282 | |\| | |
|
283 | | o c rank=2 | |
|
284 | | | | |
|
285 | o | b rank=3 | |
|
286 | | | | |
|
287 | o | rank=2 | |
|
288 | |/ | |
|
289 | o a rank=1 | |
|
290 | ||
|
291 | ||
|
292 | Display the sort of "d" for reference: | |
|
293 | ||
|
294 | $ hg test-sts d | |
|
295 | d,c,b,*,a, (no-eol) (glob) | |
|
296 | ||
|
297 | Chack that sort "f" leaps from "d" to "b": | |
|
298 | ||
|
299 | $ hg test-sts f | |
|
300 | f,d,b,*,e,*,c,a, (no-eol) (glob) | |
|
301 | ||
|
302 | $ cd .. | |
|
303 | ||
|
304 | ||
|
305 | Example 5: skipping over nested exclusive part (partially) | |
|
306 | ========================================================== | |
|
307 | ||
|
308 | We have a merge "f" whose exclusive part contains a merge "d". | |
|
309 | ||
|
310 | Similar to example 4, but the exclusive part of "d" is only partially | |
|
311 | contained in the inherited part of "f". | |
|
312 | So, we need to leap in the middle of the exclusive part of "d". | |
|
313 | ||
|
314 | # f | |
|
315 | # | | |
|
316 | # ---<--- | |
|
317 | # | | | |
|
318 | # d | | |
|
319 | # | e | |
|
320 | # -->-- | | |
|
321 | # | | | | |
|
322 | # | g | | |
|
323 | # | | | | |
|
324 | # | +---- <- in the sort of "f", leaping from "g" to "b" | |
|
325 | # b | | |
|
326 | # | c | |
|
327 | # | | | |
|
328 | # --+-- | |
|
329 | # | | |
|
330 | # a | |
|
331 | ||
|
332 | $ hg init example-5 | |
|
333 | $ cd example-5 | |
|
334 | $ hg debugbuilddag '.:a*a+2:b<a+1:c+1:g*b/g:d<c+6:e*d/e:f.' | |
|
335 | $ hg test-log | |
|
336 | o tip rank=15 | |
|
337 | | | |
|
338 | o f rank=14 | |
|
339 | |\ | |
|
340 | | o e rank=8 | |
|
341 | | | | |
|
342 | | o rank=7 | |
|
343 | | | | |
|
344 | | o rank=6 | |
|
345 | | | | |
|
346 | | o rank=5 | |
|
347 | | | | |
|
348 | | o rank=4 | |
|
349 | | | | |
|
350 | | o rank=3 | |
|
351 | | | | |
|
352 | o | d rank=7 | |
|
353 | |\ \ | |
|
354 | | o | g rank=3 | |
|
355 | | |/ | |
|
356 | | o c rank=2 | |
|
357 | | | | |
|
358 | o | b rank=4 | |
|
359 | | | | |
|
360 | o | rank=3 | |
|
361 | | | | |
|
362 | o | rank=2 | |
|
363 | |/ | |
|
364 | o a rank=1 | |
|
365 | ||
|
366 | ||
|
367 | Display the sort of "d" for reference: | |
|
368 | ||
|
369 | $ hg test-sts d | |
|
370 | d,g,c,b,*,a, (no-eol) (glob) | |
|
371 | ||
|
372 | Check that sort "f" leaps from "g" to "b": | |
|
373 | ||
|
374 | $ hg test-sts f | |
|
375 | f,d,g,b,*,e,*,c,a, (no-eol) (glob) | |
|
376 | ||
|
377 | $ cd .. | |
|
378 | ||
|
379 | ||
|
380 | Example 6: merge in the inherited part | |
|
381 | ====================================== | |
|
382 | ||
|
383 | Variant of example 2, but with a merge ("f") in the inherited part of "g". | |
|
384 | ||
|
385 | "g" is a merge node whose inherited part contains a merge node "f". | |
|
386 | We check that the stable-tail sort delegates properly after the exclusive part. | |
|
387 | ||
|
388 | # g | |
|
389 | # | | |
|
390 | # ---<--- | |
|
391 | # | | | |
|
392 | # d f | |
|
393 | # | | | |
|
394 | # | ---<--- | |
|
395 | # | | | | |
|
396 | # | e c | |
|
397 | # | | | | |
|
398 | # ---+ | <- at this point, we're done (for good) with the exclusive | |
|
399 | # | | part of "g" | |
|
400 | # b | | |
|
401 | # | | | |
|
402 | # ---+--- | |
|
403 | # | | |
|
404 | # a | |
|
405 | ||
|
406 | $ hg init example-6 | |
|
407 | $ cd example-6 | |
|
408 | $ hg debugbuilddag '.:a*a:b<a+3:c*b:d*b:e*e/c:f*d/f:g.' | |
|
409 | $ hg test-log | |
|
410 | o tip rank=10 | |
|
411 | | | |
|
412 | o g rank=9 | |
|
413 | |\ | |
|
414 | | o f rank=7 | |
|
415 | | |\ | |
|
416 | | | o e rank=3 | |
|
417 | | | | | |
|
418 | o---+ d rank=3 | |
|
419 | / / | |
|
420 | o | c rank=4 | |
|
421 | | | | |
|
422 | o | rank=3 | |
|
423 | | | | |
|
424 | o | rank=2 | |
|
425 | | | | |
|
426 | | o b rank=2 | |
|
427 | |/ | |
|
428 | o a rank=1 | |
|
429 | ||
|
430 | ||
|
431 | Display the sort of "f" for reference: | |
|
432 | ||
|
433 | $ hg test-sts f | |
|
434 | f,e,b,c,*,a, (no-eol) (glob) | |
|
435 | ||
|
436 | Check that the sort of "g" delegates to the sort of "f" after processing its | |
|
437 | exclusive part of "g": | |
|
438 | ||
|
439 | $ hg test-sts g | |
|
440 | g,d,f,e,b,c,*,a, (no-eol) (glob) | |
|
441 | ||
|
442 | $ cd .. | |
|
443 | ||
|
444 | ||
|
445 | Example 7: postponed iteration of common exclusive ancestors | |
|
446 | ============================================================ | |
|
447 | ||
|
448 | Sibling merges "j" and "k", with partially shared exclusive parts. | |
|
449 | ||
|
450 | When considering the sort of "l", the iteration over this shared part cannot | |
|
451 | happen when iterating over excl(j) and has to be postponed to excl(k). | |
|
452 | ||
|
453 | # l | |
|
454 | # | | |
|
455 | # ----<---- | |
|
456 | # | | | |
|
457 | # j k | |
|
458 | # | | | |
|
459 | # -->-- --<-- | |
|
460 | # | | | | | |
|
461 | # g e h i | |
|
462 | # | | | | | |
|
463 | # | --+-- | <- at this point, for the sort of "l", the iteration on | |
|
464 | # f | | the end of excl(j) is postponed to the iteration of | |
|
465 | # | d | excl(k) | |
|
466 | # | | | | |
|
467 | # | c | | |
|
468 | # | | | | |
|
469 | # ---+--- | | |
|
470 | # | | | |
|
471 | # b | | |
|
472 | # | | | |
|
473 | # ----+----- | |
|
474 | # | | |
|
475 | # a | |
|
476 | ||
|
477 | $ hg init example-7 | |
|
478 | $ cd example-7 | |
|
479 | $ hg debugbuilddag \ | |
|
480 | > '.:a*a:b*b:c*c:d*d:e*b:f<f+3:g<d+2:h<a+6:i*e/g:j*h/i:k*j/k:l.' | |
|
481 | $ hg test-log | |
|
482 | o tip rank=21 | |
|
483 | | | |
|
484 | o l rank=20 | |
|
485 | |\ | |
|
486 | | o k rank=13 | |
|
487 | | |\ | |
|
488 | o \ \ j rank=10 | |
|
489 | |\ \ \ | |
|
490 | | | | o i rank=7 | |
|
491 | | | | | | |
|
492 | | | | o rank=6 | |
|
493 | | | | | | |
|
494 | | | | o rank=5 | |
|
495 | | | | | | |
|
496 | | | | o rank=4 | |
|
497 | | | | | | |
|
498 | | | | o rank=3 | |
|
499 | | | | | | |
|
500 | | | | o rank=2 | |
|
501 | | | | | | |
|
502 | | | o | h rank=6 | |
|
503 | | | | | | |
|
504 | | | o | rank=5 | |
|
505 | | | | | | |
|
506 | | o | | g rank=6 | |
|
507 | | | | | | |
|
508 | | o | | rank=5 | |
|
509 | | | | | | |
|
510 | | o | | rank=4 | |
|
511 | | | | | | |
|
512 | | o | | f rank=3 | |
|
513 | | | | | | |
|
514 | o---+ | e rank=5 | |
|
515 | / / / | |
|
516 | | o | d rank=4 | |
|
517 | | | | | |
|
518 | | o | c rank=3 | |
|
519 | |/ / | |
|
520 | o / b rank=2 | |
|
521 | |/ | |
|
522 | o a rank=1 | |
|
523 | ||
|
524 | ||
|
525 | Display the sort of "j" for reference: | |
|
526 | ||
|
527 | $ hg test-sts j | |
|
528 | j,e,d,c,g,*,f,b,a, (no-eol) (glob) | |
|
529 | ||
|
530 | Display the sort of "k" for reference: | |
|
531 | ||
|
532 | $ hg test-sts k | |
|
533 | k,h,*,d,c,b,i,*,a, (no-eol) (glob) | |
|
534 | ||
|
535 | Check that the common part of excl(j) and excl(k) is iterated over after "k": | |
|
536 | ||
|
537 | $ hg test-sts l | |
|
538 | l,j,e,g,*,f,k,h,*,d,c,b,i,*,a, (no-eol) (glob) | |
|
539 | ||
|
540 | $ cd .. | |
|
541 | ||
|
542 | ||
|
543 | Example 8: postponed iteration of common ancestors between parts | |
|
544 | ================================================================ | |
|
545 | ||
|
546 | Sibling merges "g" and "i", with some part shared between the inherited part | |
|
547 | of "g" and the exclusive part of "i". | |
|
548 | ||
|
549 | When considering the sort of "j", the iteration over this shared part cannot | |
|
550 | happen when iterating over inherited(g) and has to be postponed to excl(i). | |
|
551 | ||
|
552 | # j | |
|
553 | # | | |
|
554 | # ----<---- | |
|
555 | # | | | |
|
556 | # g i | |
|
557 | # | | | |
|
558 | # --<-- --<-- | |
|
559 | # | | | | | |
|
560 | # c f | h | |
|
561 | # | | | | | |
|
562 | # | --+-- | <- at this point, for the sort of "j", the iteration | |
|
563 | # | | | on the end of inherited(g) is postponed to the | |
|
564 | # | e | iteration of excl(k) | |
|
565 | # | | | | |
|
566 | # ---+--- | | |
|
567 | # b | | |
|
568 | # | | | |
|
569 | # ----+----- | |
|
570 | # | | |
|
571 | # a | |
|
572 | ||
|
573 | $ hg init example-8 | |
|
574 | $ cd example-8 | |
|
575 | $ hg debugbuilddag '.:a*a:b*b:c*b:d*d:e*e:f*c/f:g<a+5:h*e/h:i*g/i:j.' | |
|
576 | $ hg test-log | |
|
577 | o tip rank=15 | |
|
578 | | | |
|
579 | o j rank=14 | |
|
580 | |\ | |
|
581 | | o i rank=10 | |
|
582 | | |\ | |
|
583 | | | o h rank=6 | |
|
584 | | | | | |
|
585 | | | o rank=5 | |
|
586 | | | | | |
|
587 | | | o rank=4 | |
|
588 | | | | | |
|
589 | | | o rank=3 | |
|
590 | | | | | |
|
591 | | | o rank=2 | |
|
592 | | | | | |
|
593 | o | | g rank=7 | |
|
594 | |\ \ \ | |
|
595 | | o | | f rank=5 | |
|
596 | | |/ / | |
|
597 | | o | e rank=4 | |
|
598 | | | | | |
|
599 | | o | d rank=3 | |
|
600 | | | | | |
|
601 | o | | c rank=3 | |
|
602 | |/ / | |
|
603 | o / b rank=2 | |
|
604 | |/ | |
|
605 | o a rank=1 | |
|
606 | ||
|
607 | ||
|
608 | Display the sort of "g" for reference: | |
|
609 | ||
|
610 | $ hg test-sts g | |
|
611 | g,c,f,e,d,b,a, (no-eol) | |
|
612 | ||
|
613 | Display the sort of "i" for reference: | |
|
614 | ||
|
615 | $ hg test-sts i | |
|
616 | i,e,d,b,h,*,a, (no-eol) (glob) | |
|
617 | ||
|
618 | Check that the common part of inherited(g) and excl(k) is iterated over after | |
|
619 | "i": | |
|
620 | ||
|
621 | $ hg test-sts j | |
|
622 | j,g,c,f,i,e,d,b,h,*,a, (no-eol) (glob) | |
|
623 | ||
|
624 | $ cd .. | |
|
625 | ||
|
626 | ||
|
627 | Example 9: postponed iteration of common ancestors between both parts | |
|
628 | ===================================================================== | |
|
629 | ||
|
630 | This is a combination of example 7 and 8 at the same time. | |
|
631 | Both excl(i) and excl(j) share a common part. | |
|
632 | Same with inherited(i) and inherited(j). | |
|
633 | ||
|
634 | We test that the walk on the common ancestors in both cases is properly | |
|
635 | postponed when considering sort(k). | |
|
636 | ||
|
637 | # k | |
|
638 | # | | |
|
639 | # ----<---- | |
|
640 | # | | | |
|
641 | # i j | |
|
642 | # | | | |
|
643 | # --<-- --<-- | |
|
644 | # | | | | | |
|
645 | # c f g h | |
|
646 | # | | | | | |
|
647 | # | e | | | |
|
648 | # | | | | | |
|
649 | # +--]|[--- | <- rest of excl(i) postponed to excl(j) | |
|
650 | # | | | | |
|
651 | # b ----+---- <- rest of inherited(i) postponed to inherited(j) | |
|
652 | # | | | |
|
653 | # | d | |
|
654 | # | | | |
|
655 | # ----+---- | |
|
656 | # | | |
|
657 | # a | |
|
658 | ||
|
659 | $ hg init example-9 | |
|
660 | $ cd example-9 | |
|
661 | $ hg debugbuilddag '.:a*a:b*b:c*a:d*d:e*e:f<b+2:g<d+3:h*c/f:i*g/h:j*i/j:k.' | |
|
662 | $ hg test-log | |
|
663 | o tip rank=15 | |
|
664 | | | |
|
665 | o k rank=14 | |
|
666 | |\ | |
|
667 | | o j rank=9 | |
|
668 | | |\ | |
|
669 | o \ \ i rank=7 | |
|
670 | |\ \ \ | |
|
671 | | | | o h rank=5 | |
|
672 | | | | | | |
|
673 | | | | o rank=4 | |
|
674 | | | | | | |
|
675 | | | | o rank=3 | |
|
676 | | | | | | |
|
677 | | | o | g rank=4 | |
|
678 | | | | | | |
|
679 | | | o | rank=3 | |
|
680 | | | | | | |
|
681 | | o | | f rank=4 | |
|
682 | | | | | | |
|
683 | | o---+ e rank=3 | |
|
684 | | / / | |
|
685 | | | o d rank=2 | |
|
686 | | | | | |
|
687 | o | | c rank=3 | |
|
688 | |/ / | |
|
689 | o / b rank=2 | |
|
690 | |/ | |
|
691 | o a rank=1 | |
|
692 | ||
|
693 | ||
|
694 | Display sort(i) for reference: | |
|
695 | ||
|
696 | $ hg test-sts i | |
|
697 | i,c,b,f,e,d,a, (no-eol) | |
|
698 | ||
|
699 | Display sort(j) for reference: | |
|
700 | ||
|
701 | $ hg test-sts j | |
|
702 | j,g,*,b,h,*,d,a, (no-eol) (glob) | |
|
703 | ||
|
704 | Check that the end of excl(i) is postponed to excl(j), the end of inherited(i) | |
|
705 | is postponed to inherited(j) in sort(k): | |
|
706 | ||
|
707 | $ hg test-sts k | |
|
708 | k,i,c,f,e,j,g,*,b,h,*,d,a, (no-eol) (glob) | |
|
709 | ||
|
710 | $ cd .. |
@@ -93,6 +93,7 b' from . import (' | |||
|
93 | 93 | wireprotoserver, |
|
94 | 94 | ) |
|
95 | 95 | from .interfaces import repository |
|
96 | from .stabletailgraph import stabletailsort | |
|
96 | 97 | from .utils import ( |
|
97 | 98 | cborutil, |
|
98 | 99 | compression, |
@@ -3644,6 +3645,30 b' def debugssl(ui, repo, source=None, **op' | |||
|
3644 | 3645 | |
|
3645 | 3646 | |
|
3646 | 3647 | @command( |
|
3648 | b'debug::stable-tail-sort', | |
|
3649 | [ | |
|
3650 | ( | |
|
3651 | b'T', | |
|
3652 | b'template', | |
|
3653 | b'{rev}\n', | |
|
3654 | _(b'display with template'), | |
|
3655 | _(b'TEMPLATE'), | |
|
3656 | ), | |
|
3657 | ], | |
|
3658 | b'REV', | |
|
3659 | ) | |
|
3660 | def debug_stable_tail_sort(ui, repo, revspec, template, **opts): | |
|
3661 | """display the stable-tail sort of the ancestors of a given node""" | |
|
3662 | rev = logcmdutil.revsingle(repo, revspec).rev() | |
|
3663 | cl = repo.changelog | |
|
3664 | ||
|
3665 | displayer = logcmdutil.maketemplater(ui, repo, template) | |
|
3666 | sorted_revs = stabletailsort._stable_tail_sort(cl, rev) | |
|
3667 | for ancestor_rev in sorted_revs: | |
|
3668 | displayer.show(repo[ancestor_rev]) | |
|
3669 | ||
|
3670 | ||
|
3671 | @command( | |
|
3647 | 3672 | b"debugbackupbundle", |
|
3648 | 3673 | [ |
|
3649 | 3674 | ( |
@@ -1299,6 +1299,7 b' packages = [' | |||
|
1299 | 1299 | 'mercurial.hgweb', |
|
1300 | 1300 | 'mercurial.interfaces', |
|
1301 | 1301 | 'mercurial.pure', |
|
1302 | 'mercurial.stabletailgraph', | |
|
1302 | 1303 | 'mercurial.templates', |
|
1303 | 1304 | 'mercurial.thirdparty', |
|
1304 | 1305 | 'mercurial.thirdparty.attr', |
@@ -78,6 +78,7 b' Show debug commands if there are no othe' | |||
|
78 | 78 | debug-repair-issue6528 |
|
79 | 79 | debug-revlog-index |
|
80 | 80 | debug-revlog-stats |
|
81 | debug::stable-tail-sort | |
|
81 | 82 | debugancestor |
|
82 | 83 | debugantivirusrunning |
|
83 | 84 | debugapplystreamclonebundle |
@@ -273,6 +274,7 b' Show all commands + options' | |||
|
273 | 274 | debug-repair-issue6528: to-report, from-report, paranoid, dry-run |
|
274 | 275 | debug-revlog-index: changelog, manifest, dir, template |
|
275 | 276 | debug-revlog-stats: changelog, manifest, filelogs, template |
|
277 | debug::stable-tail-sort: template | |
|
276 | 278 | debugancestor: |
|
277 | 279 | debugantivirusrunning: |
|
278 | 280 | debugapplystreamclonebundle: |
@@ -987,6 +987,8 b' Test list of internal help commands' | |||
|
987 | 987 | dump index data for a revlog |
|
988 | 988 | debug-revlog-stats |
|
989 | 989 | display statistics about revlogs in the store |
|
990 | debug::stable-tail-sort | |
|
991 | display the stable-tail sort of the ancestors of a given node | |
|
990 | 992 | debugancestor |
|
991 | 993 | find the ancestor revision of two revisions in a given index |
|
992 | 994 | debugantivirusrunning |
General Comments 0
You need to be logged in to leave comments.
Login now