Mercurial > hg
annotate mercurial/stabletailgraph/stabletailsort.py @ 50896:b2b8c25f9462
hgwebmod: use sysstr to check for attribute presence
We do not need bytes here.
author | Pierre-Yves David <pierre-yves.david@octobus.net> |
---|---|
date | Wed, 30 Aug 2023 13:28:09 +0200 |
parents | 8fb3e942473a |
children | 1c5810ce737e |
rev | line source |
---|---|
50426
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
1 # stabletailsort.py - stable ordering of revisions |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
2 # |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
3 # Copyright 2021-2023 Pacien TRAN-GIRARD <pacien.trangirard@pacien.net> |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
4 # |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
5 # This software may be used and distributed according to the terms of the |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
6 # GNU General Public License version 2 or any later version. |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
7 |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
8 """ |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
9 Stable-tail sort computation. |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
10 |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
11 The "stable-tail sort", or STS, is a reverse topological ordering of the |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
12 ancestors of a node, which tends to share large suffixes with the stable-tail |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
13 sort of ancestors and other nodes, giving it its name. |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
14 |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
15 Its properties should make it suitable for making chunks of ancestors with high |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
16 reuse and incrementality for example. |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
17 |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
18 This module and implementation are experimental. Most functions are not yet |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
19 optimised to operate on large production graphs. |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
20 """ |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
21 |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
22 import itertools |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
23 from ..node import nullrev |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
24 from .. import ancestor |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
25 |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
26 |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
27 def _sorted_parents(cl, p1, p2): |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
28 """ |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
29 Chooses and returns the pair (px, pt) from (p1, p2). |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
30 |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
31 Where |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
32 "px" denotes the parent starting the "exclusive" part, and |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
33 "pt" denotes the parent starting the "Tail" part. |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
34 |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
35 "px" is chosen as the parent with the lowest rank with the goal of |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
36 minimising the size of the exclusive part and maximise the size of the |
50459
e1496403b08c
stabletailgraph: fix terminology in doc
pacien <pacien.trangirard@pacien.net>
parents:
50426
diff
changeset
|
37 tail part, hopefully reducing the overall complexity of the stable-tail |
e1496403b08c
stabletailgraph: fix terminology in doc
pacien <pacien.trangirard@pacien.net>
parents:
50426
diff
changeset
|
38 sort. |
50426
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
39 |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
40 In case of equal ranks, the stable node ID is used as a tie-breaker. |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
41 """ |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
42 r1, r2 = cl.fast_rank(p1), cl.fast_rank(p2) |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
43 if r1 < r2: |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
44 return (p1, p2) |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
45 elif r1 > r2: |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
46 return (p2, p1) |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
47 elif cl.node(p1) < cl.node(p2): |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
48 return (p1, p2) |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
49 else: |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
50 return (p2, p1) |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
51 |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
52 |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
53 def _nonoedipal_parent_revs(cl, rev): |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
54 """ |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
55 Returns the non-œdipal parent pair of the given revision. |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
56 |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
57 An œdipal merge is a merge with parents p1, p2 with either |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
58 p1 in ancestors(p2) or p2 in ancestors(p1). |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
59 In the first case, p1 is the œdipal parent. |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
60 In the second case, p2 is the œdipal parent. |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
61 |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
62 Œdipal edges start empty exclusive parts. They do not bring new ancestors. |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
63 As such, they can be skipped when computing any topological sort or any |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
64 iteration over the ancestors of a node. |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
65 |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
66 The œdipal edges are eliminated here using the rank information. |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
67 """ |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
68 p1, p2 = cl.parentrevs(rev) |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
69 if p1 == nullrev or cl.fast_rank(p2) == cl.fast_rank(rev) - 1: |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
70 return p2, nullrev |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
71 elif p2 == nullrev or cl.fast_rank(p1) == cl.fast_rank(rev) - 1: |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
72 return p1, nullrev |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
73 else: |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
74 return p1, p2 |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
75 |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
76 |
50527
dc372251d4dc
stabletailgraph: extract _parents util func
pacien <pacien.trangirard@pacien.net>
parents:
50526
diff
changeset
|
77 def _parents(cl, rev): |
dc372251d4dc
stabletailgraph: extract _parents util func
pacien <pacien.trangirard@pacien.net>
parents:
50526
diff
changeset
|
78 p1, p2 = _nonoedipal_parent_revs(cl, rev) |
dc372251d4dc
stabletailgraph: extract _parents util func
pacien <pacien.trangirard@pacien.net>
parents:
50526
diff
changeset
|
79 if p2 == nullrev: |
dc372251d4dc
stabletailgraph: extract _parents util func
pacien <pacien.trangirard@pacien.net>
parents:
50526
diff
changeset
|
80 return p1, p2 |
dc372251d4dc
stabletailgraph: extract _parents util func
pacien <pacien.trangirard@pacien.net>
parents:
50526
diff
changeset
|
81 |
dc372251d4dc
stabletailgraph: extract _parents util func
pacien <pacien.trangirard@pacien.net>
parents:
50526
diff
changeset
|
82 return _sorted_parents(cl, p1, p2) |
dc372251d4dc
stabletailgraph: extract _parents util func
pacien <pacien.trangirard@pacien.net>
parents:
50526
diff
changeset
|
83 |
dc372251d4dc
stabletailgraph: extract _parents util func
pacien <pacien.trangirard@pacien.net>
parents:
50526
diff
changeset
|
84 |
50525
1a4f54574e3d
stabletailgraph: clarify naiveness of current implementation
pacien <pacien.trangirard@pacien.net>
parents:
50459
diff
changeset
|
85 def _stable_tail_sort_naive(cl, head_rev): |
50426
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
86 """ |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
87 Naive topological iterator of the ancestors given by the stable-tail sort. |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
88 |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
89 The stable-tail sort of a node "h" is defined as the sequence: |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
90 sts(h) := [h] + excl(h) + sts(pt(h)) |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
91 where excl(h) := u for u in sts(px(h)) if u not in ancestors(pt(h)) |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
92 |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
93 This implementation uses a call-stack whose size is |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
94 O(number of open merges). |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
95 |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
96 As such, this implementation exists mainly as a defining reference. |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
97 """ |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
98 cursor_rev = head_rev |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
99 while cursor_rev != nullrev: |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
100 yield cursor_rev |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
101 |
50527
dc372251d4dc
stabletailgraph: extract _parents util func
pacien <pacien.trangirard@pacien.net>
parents:
50526
diff
changeset
|
102 px, pt = _parents(cl, cursor_rev) |
dc372251d4dc
stabletailgraph: extract _parents util func
pacien <pacien.trangirard@pacien.net>
parents:
50526
diff
changeset
|
103 if pt == nullrev: |
dc372251d4dc
stabletailgraph: extract _parents util func
pacien <pacien.trangirard@pacien.net>
parents:
50526
diff
changeset
|
104 cursor_rev = px |
50426
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
105 else: |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
106 tail_ancestors = ancestor.lazyancestors( |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
107 cl.parentrevs, (pt,), inclusive=True |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
108 ) |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
109 exclusive_ancestors = ( |
50525
1a4f54574e3d
stabletailgraph: clarify naiveness of current implementation
pacien <pacien.trangirard@pacien.net>
parents:
50459
diff
changeset
|
110 a |
1a4f54574e3d
stabletailgraph: clarify naiveness of current implementation
pacien <pacien.trangirard@pacien.net>
parents:
50459
diff
changeset
|
111 for a in _stable_tail_sort_naive(cl, px) |
1a4f54574e3d
stabletailgraph: clarify naiveness of current implementation
pacien <pacien.trangirard@pacien.net>
parents:
50459
diff
changeset
|
112 if a not in tail_ancestors |
50426
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
113 ) |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
114 |
50526
4fd2f7ab4177
stabletailgraph: clarify excl part size computation
pacien <pacien.trangirard@pacien.net>
parents:
50525
diff
changeset
|
115 # Notice that excl(cur) is disjoint from ancestors(pt), |
4fd2f7ab4177
stabletailgraph: clarify excl part size computation
pacien <pacien.trangirard@pacien.net>
parents:
50525
diff
changeset
|
116 # so there is no double-counting: |
4fd2f7ab4177
stabletailgraph: clarify excl part size computation
pacien <pacien.trangirard@pacien.net>
parents:
50525
diff
changeset
|
117 # rank(cur) = len([cur]) + len(excl(cur)) + rank(pt) |
50426
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
118 excl_part_size = cl.fast_rank(cursor_rev) - cl.fast_rank(pt) - 1 |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
119 yield from itertools.islice(exclusive_ancestors, excl_part_size) |
f0d2b18f0274
stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff
changeset
|
120 cursor_rev = pt |
50528
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
121 |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
122 |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
123 def _find_all_leaps_naive(cl, head_rev): |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
124 """ |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
125 Yields the leaps in the stable-tail sort of the given revision. |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
126 |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
127 A leap is a pair of revisions (source, target) consecutive in the |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
128 stable-tail sort of a head, for which target != px(source). |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
129 |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
130 Leaps are yielded in the same order as encountered in the stable-tail sort, |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
131 from head to root. |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
132 """ |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
133 sts = _stable_tail_sort_naive(cl, head_rev) |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
134 prev = next(sts) |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
135 for current in sts: |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
136 if current != _parents(cl, prev)[0]: |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
137 yield (prev, current) |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
138 |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
139 prev = current |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
140 |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
141 |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
142 def _find_specific_leaps_naive(cl, head_rev): |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
143 """ |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
144 Returns the specific leaps in the stable-tail sort of the given revision. |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
145 |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
146 Specific leaps are leaps appear in the stable-tail sort of a given |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
147 revision, but not in the stable-tail sort of any of its ancestors. |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
148 |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
149 The final leaps (leading to the pt of the considered merge) are omitted. |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
150 |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
151 Only merge nodes can have associated specific leaps. |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
152 |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
153 This implementations uses the whole leap sets of the given revision and |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
154 of its parents. |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
155 """ |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
156 px, pt = _parents(cl, head_rev) |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
157 if px == nullrev or pt == nullrev: |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
158 return # linear nodes cannot have specific leaps |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
159 |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
160 parents_leaps = set(_find_all_leaps_naive(cl, px)) |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
161 |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
162 sts = _stable_tail_sort_naive(cl, head_rev) |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
163 prev = next(sts) |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
164 for current in sts: |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
165 if current == pt: |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
166 break |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
167 if current != _parents(cl, prev)[0]: |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
168 leap = (prev, current) |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
169 if leap not in parents_leaps: |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
170 yield leap |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
171 |
8fb3e942473a
stabletailgraph: naive version of leap computation
pacien <pacien.trangirard@pacien.net>
parents:
50527
diff
changeset
|
172 prev = current |