Show More
@@ -1,110 +1,111 b'' | |||||
1 | # stabletailsort.py - stable ordering of revisions |
|
1 | # stabletailsort.py - stable ordering of revisions | |
2 | # |
|
2 | # | |
3 | # Copyright 2021-2023 Pacien TRAN-GIRARD <pacien.trangirard@pacien.net> |
|
3 | # Copyright 2021-2023 Pacien TRAN-GIRARD <pacien.trangirard@pacien.net> | |
4 | # |
|
4 | # | |
5 | # This software may be used and distributed according to the terms of the |
|
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. |
|
6 | # GNU General Public License version 2 or any later version. | |
7 |
|
7 | |||
8 | """ |
|
8 | """ | |
9 | Stable-tail sort computation. |
|
9 | Stable-tail sort computation. | |
10 |
|
10 | |||
11 | The "stable-tail sort", or STS, is a reverse topological ordering of the |
|
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 |
|
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. |
|
13 | sort of ancestors and other nodes, giving it its name. | |
14 |
|
14 | |||
15 | Its properties should make it suitable for making chunks of ancestors with high |
|
15 | Its properties should make it suitable for making chunks of ancestors with high | |
16 | reuse and incrementality for example. |
|
16 | reuse and incrementality for example. | |
17 |
|
17 | |||
18 | This module and implementation are experimental. Most functions are not yet |
|
18 | This module and implementation are experimental. Most functions are not yet | |
19 | optimised to operate on large production graphs. |
|
19 | optimised to operate on large production graphs. | |
20 | """ |
|
20 | """ | |
21 |
|
21 | |||
22 | import itertools |
|
22 | import itertools | |
23 | from ..node import nullrev |
|
23 | from ..node import nullrev | |
24 | from .. import ancestor |
|
24 | from .. import ancestor | |
25 |
|
25 | |||
26 |
|
26 | |||
27 | def _sorted_parents(cl, p1, p2): |
|
27 | def _sorted_parents(cl, p1, p2): | |
28 | """ |
|
28 | """ | |
29 | Chooses and returns the pair (px, pt) from (p1, p2). |
|
29 | Chooses and returns the pair (px, pt) from (p1, p2). | |
30 |
|
30 | |||
31 | Where |
|
31 | Where | |
32 | "px" denotes the parent starting the "exclusive" part, and |
|
32 | "px" denotes the parent starting the "exclusive" part, and | |
33 | "pt" denotes the parent starting the "Tail" part. |
|
33 | "pt" denotes the parent starting the "Tail" part. | |
34 |
|
34 | |||
35 | "px" is chosen as the parent with the lowest rank with the goal of |
|
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 |
|
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 |
|
37 | tail part, hopefully reducing the overall complexity of the stable-tail | |
|
38 | sort. | |||
38 |
|
39 | |||
39 | In case of equal ranks, the stable node ID is used as a tie-breaker. |
|
40 | In case of equal ranks, the stable node ID is used as a tie-breaker. | |
40 | """ |
|
41 | """ | |
41 | r1, r2 = cl.fast_rank(p1), cl.fast_rank(p2) |
|
42 | r1, r2 = cl.fast_rank(p1), cl.fast_rank(p2) | |
42 | if r1 < r2: |
|
43 | if r1 < r2: | |
43 | return (p1, p2) |
|
44 | return (p1, p2) | |
44 | elif r1 > r2: |
|
45 | elif r1 > r2: | |
45 | return (p2, p1) |
|
46 | return (p2, p1) | |
46 | elif cl.node(p1) < cl.node(p2): |
|
47 | elif cl.node(p1) < cl.node(p2): | |
47 | return (p1, p2) |
|
48 | return (p1, p2) | |
48 | else: |
|
49 | else: | |
49 | return (p2, p1) |
|
50 | return (p2, p1) | |
50 |
|
51 | |||
51 |
|
52 | |||
52 | def _nonoedipal_parent_revs(cl, rev): |
|
53 | def _nonoedipal_parent_revs(cl, rev): | |
53 | """ |
|
54 | """ | |
54 | Returns the non-Εdipal parent pair of the given revision. |
|
55 | Returns the non-Εdipal parent pair of the given revision. | |
55 |
|
56 | |||
56 | An Εdipal merge is a merge with parents p1, p2 with either |
|
57 | An Εdipal merge is a merge with parents p1, p2 with either | |
57 | p1 in ancestors(p2) or p2 in ancestors(p1). |
|
58 | p1 in ancestors(p2) or p2 in ancestors(p1). | |
58 | In the first case, p1 is the Εdipal parent. |
|
59 | In the first case, p1 is the Εdipal parent. | |
59 | In the second case, p2 is the Εdipal parent. |
|
60 | In the second case, p2 is the Εdipal parent. | |
60 |
|
61 | |||
61 | Εdipal edges start empty exclusive parts. They do not bring new ancestors. |
|
62 | Ε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 | As such, they can be skipped when computing any topological sort or any | |
63 | iteration over the ancestors of a node. |
|
64 | iteration over the ancestors of a node. | |
64 |
|
65 | |||
65 | The Εdipal edges are eliminated here using the rank information. |
|
66 | The Εdipal edges are eliminated here using the rank information. | |
66 | """ |
|
67 | """ | |
67 | p1, p2 = cl.parentrevs(rev) |
|
68 | p1, p2 = cl.parentrevs(rev) | |
68 | if p1 == nullrev or cl.fast_rank(p2) == cl.fast_rank(rev) - 1: |
|
69 | if p1 == nullrev or cl.fast_rank(p2) == cl.fast_rank(rev) - 1: | |
69 | return p2, nullrev |
|
70 | return p2, nullrev | |
70 | elif p2 == nullrev or cl.fast_rank(p1) == cl.fast_rank(rev) - 1: |
|
71 | elif p2 == nullrev or cl.fast_rank(p1) == cl.fast_rank(rev) - 1: | |
71 | return p1, nullrev |
|
72 | return p1, nullrev | |
72 | else: |
|
73 | else: | |
73 | return p1, p2 |
|
74 | return p1, p2 | |
74 |
|
75 | |||
75 |
|
76 | |||
76 | def _stable_tail_sort(cl, head_rev): |
|
77 | def _stable_tail_sort(cl, head_rev): | |
77 | """ |
|
78 | """ | |
78 | Naive topological iterator of the ancestors given by the stable-tail sort. |
|
79 | Naive topological iterator of the ancestors given by the stable-tail sort. | |
79 |
|
80 | |||
80 | The stable-tail sort of a node "h" is defined as the sequence: |
|
81 | The stable-tail sort of a node "h" is defined as the sequence: | |
81 | sts(h) := [h] + excl(h) + sts(pt(h)) |
|
82 | 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 | where excl(h) := u for u in sts(px(h)) if u not in ancestors(pt(h)) | |
83 |
|
84 | |||
84 | This implementation uses a call-stack whose size is |
|
85 | This implementation uses a call-stack whose size is | |
85 | O(number of open merges). |
|
86 | O(number of open merges). | |
86 |
|
87 | |||
87 | As such, this implementation exists mainly as a defining reference. |
|
88 | As such, this implementation exists mainly as a defining reference. | |
88 | """ |
|
89 | """ | |
89 | cursor_rev = head_rev |
|
90 | cursor_rev = head_rev | |
90 | while cursor_rev != nullrev: |
|
91 | while cursor_rev != nullrev: | |
91 | yield cursor_rev |
|
92 | yield cursor_rev | |
92 |
|
93 | |||
93 | p1, p2 = _nonoedipal_parent_revs(cl, cursor_rev) |
|
94 | p1, p2 = _nonoedipal_parent_revs(cl, cursor_rev) | |
94 | if p1 == nullrev: |
|
95 | if p1 == nullrev: | |
95 | cursor_rev = p2 |
|
96 | cursor_rev = p2 | |
96 | elif p2 == nullrev: |
|
97 | elif p2 == nullrev: | |
97 | cursor_rev = p1 |
|
98 | cursor_rev = p1 | |
98 | else: |
|
99 | else: | |
99 | px, pt = _sorted_parents(cl, p1, p2) |
|
100 | px, pt = _sorted_parents(cl, p1, p2) | |
100 |
|
101 | |||
101 | tail_ancestors = ancestor.lazyancestors( |
|
102 | tail_ancestors = ancestor.lazyancestors( | |
102 | cl.parentrevs, (pt,), inclusive=True |
|
103 | cl.parentrevs, (pt,), inclusive=True | |
103 | ) |
|
104 | ) | |
104 | exclusive_ancestors = ( |
|
105 | exclusive_ancestors = ( | |
105 | a for a in _stable_tail_sort(cl, px) if a not in tail_ancestors |
|
106 | a for a in _stable_tail_sort(cl, px) if a not in tail_ancestors | |
106 | ) |
|
107 | ) | |
107 |
|
108 | |||
108 | excl_part_size = cl.fast_rank(cursor_rev) - cl.fast_rank(pt) - 1 |
|
109 | excl_part_size = cl.fast_rank(cursor_rev) - cl.fast_rank(pt) - 1 | |
109 | yield from itertools.islice(exclusive_ancestors, excl_part_size) |
|
110 | yield from itertools.islice(exclusive_ancestors, excl_part_size) | |
110 | cursor_rev = pt |
|
111 | cursor_rev = pt |
General Comments 0
You need to be logged in to leave comments.
Login now