Mercurial > public > mercurial-scm > hg-stable

annotate mercurial/stabletailgraph/stabletailsort.py @ 50460:f0d2b18f0274

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
stabletailgraph: implement stable-tail sort This adds the computation of the "stable-tail sort", an incremental node sorting method. It is a stepping stone for the implementation of faster label discovery (for example for obs markers) and more caching.
author pacien <pacien.trangirard@pacien.net>
date Thu, 30 Mar 2023 22:22:44 +0200
parents
children e1496403b08c
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
50460
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
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
37 tail part, hopefully reducing the overall complexity of the stable sort.
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
38
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
39 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
40 """
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
41 r1, r2 = cl.fast_rank(p1), cl.fast_rank(p2)
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
42 if r1 < r2:
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
43 return (p1, p2)
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
44 elif r1 > r2:
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
45 return (p2, p1)
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
46 elif cl.node(p1) < cl.node(p2):
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
47 return (p1, p2)
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
48 else:
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
49 return (p2, p1)
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
50
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 def _nonoedipal_parent_revs(cl, rev):
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
53 """
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
54 Returns the non-œdipal parent pair of the given revision.
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
55
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
56 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
57 p1 in ancestors(p2) or p2 in ancestors(p1).
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
58 In the first case, p1 is the œdipal parent.
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
59 In the second case, p2 is the œdipal parent.
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
60
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
61 Œ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
62 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
63 iteration over the ancestors of a node.
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
64
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
65 The œdipal edges are eliminated here using the rank information.
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
66 """
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
67 p1, p2 = cl.parentrevs(rev)
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
68 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
69 return p2, nullrev
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
70 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
71 return p1, nullrev
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
72 else:
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
73 return p1, p2
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
74
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 def _stable_tail_sort(cl, head_rev):
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
77 """
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
78 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
79
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
80 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
81 sts(h) := [h] + excl(h) + sts(pt(h))
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
82 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
83
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
84 This implementation uses a call-stack whose size is
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
85 O(number of open merges).
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 As such, this implementation exists mainly as a defining reference.
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 cursor_rev = head_rev
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
90 while cursor_rev != nullrev:
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
91 yield cursor_rev
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 p1, p2 = _nonoedipal_parent_revs(cl, cursor_rev)
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
94 if p1 == nullrev:
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
95 cursor_rev = p2
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
96 elif p2 == nullrev:
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
97 cursor_rev = p1
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
98 else:
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
99 px, pt = _sorted_parents(cl, p1, p2)
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
100
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
101 tail_ancestors = ancestor.lazyancestors(
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
102 cl.parentrevs, (pt,), inclusive=True
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
103 )
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
104 exclusive_ancestors = (
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
105 a for a in _stable_tail_sort(cl, px) if a not in tail_ancestors
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
106 )
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
107
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
108 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
109 yield from itertools.islice(exclusive_ancestors, excl_part_size)
f0d2b18f0274 stabletailgraph: implement stable-tail sort
pacien <pacien.trangirard@pacien.net>
parents:
diff changeset
110 cursor_rev = pt