--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/mercurial/stabletailgraph/stabletailsort.py Thu Mar 30 22:22:44 2023 +0200
@@ -0,0 +1,110 @@
+# stabletailsort.py - stable ordering of revisions
+#
+# Copyright 2021-2023 Pacien TRAN-GIRARD <pacien.trangirard@pacien.net>
+#
+# This software may be used and distributed according to the terms of the
+# GNU General Public License version 2 or any later version.
+
+"""
+Stable-tail sort computation.
+
+The "stable-tail sort", or STS, is a reverse topological ordering of the
+ancestors of a node, which tends to share large suffixes with the stable-tail
+sort of ancestors and other nodes, giving it its name.
+
+Its properties should make it suitable for making chunks of ancestors with high
+reuse and incrementality for example.
+
+This module and implementation are experimental. Most functions are not yet
+optimised to operate on large production graphs.
+"""
+
+import itertools
+from ..node import nullrev
+from .. import ancestor
+
+
+def _sorted_parents(cl, p1, p2):
+ """
+ Chooses and returns the pair (px, pt) from (p1, p2).
+
+ Where
+ "px" denotes the parent starting the "exclusive" part, and
+ "pt" denotes the parent starting the "Tail" part.
+
+ "px" is chosen as the parent with the lowest rank with the goal of
+ minimising the size of the exclusive part and maximise the size of the
+ tail part, hopefully reducing the overall complexity of the stable sort.
+
+ In case of equal ranks, the stable node ID is used as a tie-breaker.
+ """
+ r1, r2 = cl.fast_rank(p1), cl.fast_rank(p2)
+ if r1 < r2:
+ return (p1, p2)
+ elif r1 > r2:
+ return (p2, p1)
+ elif cl.node(p1) < cl.node(p2):
+ return (p1, p2)
+ else:
+ return (p2, p1)
+
+
+def _nonoedipal_parent_revs(cl, rev):
+ """
+ Returns the non-œdipal parent pair of the given revision.
+
+ An œdipal merge is a merge with parents p1, p2 with either
+ p1 in ancestors(p2) or p2 in ancestors(p1).
+ In the first case, p1 is the œdipal parent.
+ In the second case, p2 is the œdipal parent.
+
+ Œdipal edges start empty exclusive parts. They do not bring new ancestors.
+ As such, they can be skipped when computing any topological sort or any
+ iteration over the ancestors of a node.
+
+ The œdipal edges are eliminated here using the rank information.
+ """
+ p1, p2 = cl.parentrevs(rev)
+ if p1 == nullrev or cl.fast_rank(p2) == cl.fast_rank(rev) - 1:
+ return p2, nullrev
+ elif p2 == nullrev or cl.fast_rank(p1) == cl.fast_rank(rev) - 1:
+ return p1, nullrev
+ else:
+ return p1, p2
+
+
+def _stable_tail_sort(cl, head_rev):
+ """
+ Naive topological iterator of the ancestors given by the stable-tail sort.
+
+ The stable-tail sort of a node "h" is defined as the sequence:
+ sts(h) := [h] + excl(h) + sts(pt(h))
+ where excl(h) := u for u in sts(px(h)) if u not in ancestors(pt(h))
+
+ This implementation uses a call-stack whose size is
+ O(number of open merges).
+
+ As such, this implementation exists mainly as a defining reference.
+ """
+ cursor_rev = head_rev
+ while cursor_rev != nullrev:
+ yield cursor_rev
+
+ p1, p2 = _nonoedipal_parent_revs(cl, cursor_rev)
+ if p1 == nullrev:
+ cursor_rev = p2
+ elif p2 == nullrev:
+ cursor_rev = p1
+ else:
+ px, pt = _sorted_parents(cl, p1, p2)
+
+ tail_ancestors = ancestor.lazyancestors(
+ cl.parentrevs, (pt,), inclusive=True
+ )
+ exclusive_ancestors = (
+ a for a in _stable_tail_sort(cl, px) if a not in tail_ancestors
+ )
+
+ excl_part_size = cl.fast_rank(cursor_rev) - cl.fast_rank(pt) - 1
+ yield from itertools.islice(exclusive_ancestors, excl_part_size)
+ cursor_rev = pt
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/test-stabletailgraph.t Thu Mar 30 22:22:44 2023 +0200
@@ -0,0 +1,710 @@
+====================================
+Test for the stabletailgraph package
+====================================
+
+This test file contains a bunch of small test graphs with some minimal yet
+non-trivial structure, on which the various stable-tail graph and stable-tail
+sort functions are tested.
+
+Each case consists of the creation of the interesting graph structure, followed
+by a check, for each noteworthy node, of:
+- the stable-tail sort output.
+
+In the ASCII art of the diagrams, the side of the exclusive part which is
+followed in priority is denoted with "<" or ">" if it is on the left or right
+respectively.
+
+The intermediary linear parts in the example graph are there to force the
+exclusive part choice (made on a min rank condition).
+
+
+Setup
+=====
+
+Enable the rank computation to test sorting based on the rank.
+
+ $ cat << EOF >> $HGRCPATH
+ > [format]
+ > exp-use-changelog-v2=enable-unstable-format-and-corrupt-my-data
+ >
+ > [alias]
+ > test-sts = debug::stable-tail-sort -T '{tags},'
+ > test-log = log --graph -T '{tags} rank={_fast_rank}'
+ > EOF
+
+
+Example 1: single merge node
+============================
+
+A base case with one branchpoint "b" and one merge node "e".
+
+The exclusive part, starting with the lowest-ranking parent "c" of "e",
+appears first in stable-tail sort of "e" and "f".
+
+# f
+# |
+# e
+# |
+# --<--
+# | |
+# c d
+# | |
+# --+-- <- at this point, the sort of "e" is done consuming its
+# | exclusive part [c] and jumps back to its other parent "d"
+# b
+# |
+# a
+
+ $ hg init example-1
+ $ cd example-1
+ $ hg debugbuilddag '.:a*a:b*b:c<b+2:d*c/d:e*e:f.'
+ $ hg test-log
+ o tip rank=8
+ |
+ o f rank=7
+ |
+ o e rank=6
+ |\
+ | o d rank=4
+ | |
+ | o rank=3
+ | |
+ o | c rank=3
+ |/
+ o b rank=2
+ |
+ o a rank=1
+
+
+Check the sort of the base linear case.
+
+ $ hg test-sts c
+ c,b,a, (no-eol)
+
+Check the stable-tail sort of "e": "c" should come before "d".
+
+ $ hg test-sts e
+ e,c,d,*,b,a, (no-eol) (glob)
+
+Check that the linear descendant of the merge inherits its sort properly.
+
+ $ hg test-sts f
+ f,e,c,d,*,b,a, (no-eol) (glob)
+
+ $ cd ..
+
+
+Example 2: nested exclusive parts, without specific leap
+========================================================
+
+"g" is a merge node whose exclusive part contains a merge node "e".
+We check that the stable-tail sort recurses properly by delegating.
+
+Notice that parts of the sort of "e" is an infix of the sort of "g".
+This is an expected property of the sort.
+
+# g
+# |
+# ---<---
+# | |
+# e | <- while processing the sort in the exclusive part of "g"
+# | | we recursively process the exclusive part of "e"
+# --<-- f
+# | | |
+# c d |
+# | | |
+# --+-- |
+# | |
+# b |
+# | |
+# ---+--- <- done with excl(g), jump to "f"
+# |
+# a
+
+ $ hg init example-2
+ $ cd example-2
+ $ hg debugbuilddag '.:a*a:b*b:c<b+2:d*c/d:e<a+6:f*e/f:g.'
+ $ hg test-log
+ o tip rank=14
+ |
+ o g rank=13
+ |\
+ | o f rank=7
+ | |
+ | o rank=6
+ | |
+ | o rank=5
+ | |
+ | o rank=4
+ | |
+ | o rank=3
+ | |
+ | o rank=2
+ | |
+ o | e rank=6
+ |\ \
+ | o | d rank=4
+ | | |
+ | o | rank=3
+ | | |
+ o | | c rank=3
+ |/ /
+ o / b rank=2
+ |/
+ o a rank=1
+
+Display the sort of "e" for reference
+
+ $ hg test-sts e
+ e,c,d,*,b,a, (no-eol) (glob)
+
+Check the correctness of the sort of "g",
+and that a part of the sort of "e" appears as an infix.
+
+ $ hg test-sts g
+ g,e,c,d,*,b,f,*,a, (no-eol) (glob)
+
+ $ cd ..
+
+
+Example 3: shadowing of a final leap
+====================================
+
+We have a merge "f" whose exclusive part contains a merge "d".
+
+The inherited parent of "d" is not in the exclusive part of "f".
+At the end of the exclusive part of "d",
+the leap to "c" is shadowed by the leap to "e", i.e. the inherited part to "f".
+
+Notice that emitting "c" before "e" would break the reverse topological
+ordering.
+
+# f
+# |
+# ---<---
+# | |
+# d |
+# | e
+# --<-- |
+# | | |
+# | +----
+# b |
+# | c
+# | |
+# --+-- <- at this point, jumping to "e", not the shadowed "c"
+# |
+# a
+
+ $ hg init example-3
+ $ cd example-3
+ $ hg debugbuilddag '.:a*a:b<a+2:c*b/c:d<c+3:e*d/e:f.'
+ $ hg test-log
+ o tip rank=10
+ |
+ o f rank=9
+ |\
+ | o e rank=6
+ | |
+ | o rank=5
+ | |
+ | o rank=4
+ | |
+ o | d rank=5
+ |\|
+ | o c rank=3
+ | |
+ | o rank=2
+ | |
+ o | b rank=2
+ |/
+ o a rank=1
+
+
+Display the sort of "d" for reference:
+
+ $ hg test-sts d
+ d,b,c,*,a, (no-eol) (glob)
+
+Check that we leap from "b" directly to "e" (shadowing the leap to "c"),
+and that "c" is then emitted after "e" (its descendant).
+
+ $ hg test-sts f
+ f,d,b,e,*,c,*,a, (no-eol) (glob)
+
+ $ cd ..
+
+
+Example 4: skipping over nested exclusive part (entirely)
+=========================================================
+
+We have a merge "f" whose exclusive part contains a merge "d".
+
+The exclusive part of "d" is not in the exclusive part of "f".
+However, some of the inherited part of "d" is part of the exclusive part of "f"
+and needs to be iterated over before leaping to the inherited part of "f".
+
+The sort of "d" is partially reused for the ordering of the exclusive part of
+"f". However the reused part is not contiguous in the sort of "d".
+
+# f
+# |
+# ---<---
+# | |
+# d |
+# | e
+# -->-- | <- in the sort of "f", we need to skip "c" and leap to the
+# | | | inherited part of "d"
+# | +----
+# b |
+# | c
+# | |
+# --+--
+# |
+# a
+
+ $ hg init example-4
+ $ cd example-4
+ $ hg debugbuilddag '.:a*a+1:b<a+1:c*b/c:d<c+4:e*d/e:f.'
+ $ hg test-log
+ o tip rank=11
+ |
+ o f rank=10
+ |\
+ | o e rank=6
+ | |
+ | o rank=5
+ | |
+ | o rank=4
+ | |
+ | o rank=3
+ | |
+ o | d rank=5
+ |\|
+ | o c rank=2
+ | |
+ o | b rank=3
+ | |
+ o | rank=2
+ |/
+ o a rank=1
+
+
+Display the sort of "d" for reference:
+
+ $ hg test-sts d
+ d,c,b,*,a, (no-eol) (glob)
+
+Chack that sort "f" leaps from "d" to "b":
+
+ $ hg test-sts f
+ f,d,b,*,e,*,c,a, (no-eol) (glob)
+
+ $ cd ..
+
+
+Example 5: skipping over nested exclusive part (partially)
+==========================================================
+
+We have a merge "f" whose exclusive part contains a merge "d".
+
+Similar to example 4, but the exclusive part of "d" is only partially
+contained in the inherited part of "f".
+So, we need to leap in the middle of the exclusive part of "d".
+
+# f
+# |
+# ---<---
+# | |
+# d |
+# | e
+# -->-- |
+# | | |
+# | g |
+# | | |
+# | +---- <- in the sort of "f", leaping from "g" to "b"
+# b |
+# | c
+# | |
+# --+--
+# |
+# a
+
+ $ hg init example-5
+ $ cd example-5
+ $ hg debugbuilddag '.:a*a+2:b<a+1:c+1:g*b/g:d<c+6:e*d/e:f.'
+ $ hg test-log
+ o tip rank=15
+ |
+ o f rank=14
+ |\
+ | o e rank=8
+ | |
+ | o rank=7
+ | |
+ | o rank=6
+ | |
+ | o rank=5
+ | |
+ | o rank=4
+ | |
+ | o rank=3
+ | |
+ o | d rank=7
+ |\ \
+ | o | g rank=3
+ | |/
+ | o c rank=2
+ | |
+ o | b rank=4
+ | |
+ o | rank=3
+ | |
+ o | rank=2
+ |/
+ o a rank=1
+
+
+Display the sort of "d" for reference:
+
+ $ hg test-sts d
+ d,g,c,b,*,a, (no-eol) (glob)
+
+Check that sort "f" leaps from "g" to "b":
+
+ $ hg test-sts f
+ f,d,g,b,*,e,*,c,a, (no-eol) (glob)
+
+ $ cd ..
+
+
+Example 6: merge in the inherited part
+======================================
+
+Variant of example 2, but with a merge ("f") in the inherited part of "g".
+
+"g" is a merge node whose inherited part contains a merge node "f".
+We check that the stable-tail sort delegates properly after the exclusive part.
+
+# g
+# |
+# ---<---
+# | |
+# d f
+# | |
+# | ---<---
+# | | |
+# | e c
+# | | |
+# ---+ | <- at this point, we're done (for good) with the exclusive
+# | | part of "g"
+# b |
+# | |
+# ---+---
+# |
+# a
+
+ $ hg init example-6
+ $ cd example-6
+ $ hg debugbuilddag '.:a*a:b<a+3:c*b:d*b:e*e/c:f*d/f:g.'
+ $ hg test-log
+ o tip rank=10
+ |
+ o g rank=9
+ |\
+ | o f rank=7
+ | |\
+ | | o e rank=3
+ | | |
+ o---+ d rank=3
+ / /
+ o | c rank=4
+ | |
+ o | rank=3
+ | |
+ o | rank=2
+ | |
+ | o b rank=2
+ |/
+ o a rank=1
+
+
+Display the sort of "f" for reference:
+
+ $ hg test-sts f
+ f,e,b,c,*,a, (no-eol) (glob)
+
+Check that the sort of "g" delegates to the sort of "f" after processing its
+exclusive part of "g":
+
+ $ hg test-sts g
+ g,d,f,e,b,c,*,a, (no-eol) (glob)
+
+ $ cd ..
+
+
+Example 7: postponed iteration of common exclusive ancestors
+============================================================
+
+Sibling merges "j" and "k", with partially shared exclusive parts.
+
+When considering the sort of "l", the iteration over this shared part cannot
+happen when iterating over excl(j) and has to be postponed to excl(k).
+
+# l
+# |
+# ----<----
+# | |
+# j k
+# | |
+# -->-- --<--
+# | | | |
+# g e h i
+# | | | |
+# | --+-- | <- at this point, for the sort of "l", the iteration on
+# f | | the end of excl(j) is postponed to the iteration of
+# | d | excl(k)
+# | | |
+# | c |
+# | | |
+# ---+--- |
+# | |
+# b |
+# | |
+# ----+-----
+# |
+# a
+
+ $ hg init example-7
+ $ cd example-7
+ $ hg debugbuilddag \
+ > '.: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.'
+ $ hg test-log
+ o tip rank=21
+ |
+ o l rank=20
+ |\
+ | o k rank=13
+ | |\
+ o \ \ j rank=10
+ |\ \ \
+ | | | o i rank=7
+ | | | |
+ | | | o rank=6
+ | | | |
+ | | | o rank=5
+ | | | |
+ | | | o rank=4
+ | | | |
+ | | | o rank=3
+ | | | |
+ | | | o rank=2
+ | | | |
+ | | o | h rank=6
+ | | | |
+ | | o | rank=5
+ | | | |
+ | o | | g rank=6
+ | | | |
+ | o | | rank=5
+ | | | |
+ | o | | rank=4
+ | | | |
+ | o | | f rank=3
+ | | | |
+ o---+ | e rank=5
+ / / /
+ | o | d rank=4
+ | | |
+ | o | c rank=3
+ |/ /
+ o / b rank=2
+ |/
+ o a rank=1
+
+
+Display the sort of "j" for reference:
+
+ $ hg test-sts j
+ j,e,d,c,g,*,f,b,a, (no-eol) (glob)
+
+Display the sort of "k" for reference:
+
+ $ hg test-sts k
+ k,h,*,d,c,b,i,*,a, (no-eol) (glob)
+
+Check that the common part of excl(j) and excl(k) is iterated over after "k":
+
+ $ hg test-sts l
+ l,j,e,g,*,f,k,h,*,d,c,b,i,*,a, (no-eol) (glob)
+
+ $ cd ..
+
+
+Example 8: postponed iteration of common ancestors between parts
+================================================================
+
+Sibling merges "g" and "i", with some part shared between the inherited part
+of "g" and the exclusive part of "i".
+
+When considering the sort of "j", the iteration over this shared part cannot
+happen when iterating over inherited(g) and has to be postponed to excl(i).
+
+# j
+# |
+# ----<----
+# | |
+# g i
+# | |
+# --<-- --<--
+# | | | |
+# c f | h
+# | | | |
+# | --+-- | <- at this point, for the sort of "j", the iteration
+# | | | on the end of inherited(g) is postponed to the
+# | e | iteration of excl(k)
+# | | |
+# ---+--- |
+# b |
+# | |
+# ----+-----
+# |
+# a
+
+ $ hg init example-8
+ $ cd example-8
+ $ 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.'
+ $ hg test-log
+ o tip rank=15
+ |
+ o j rank=14
+ |\
+ | o i rank=10
+ | |\
+ | | o h rank=6
+ | | |
+ | | o rank=5
+ | | |
+ | | o rank=4
+ | | |
+ | | o rank=3
+ | | |
+ | | o rank=2
+ | | |
+ o | | g rank=7
+ |\ \ \
+ | o | | f rank=5
+ | |/ /
+ | o | e rank=4
+ | | |
+ | o | d rank=3
+ | | |
+ o | | c rank=3
+ |/ /
+ o / b rank=2
+ |/
+ o a rank=1
+
+
+Display the sort of "g" for reference:
+
+ $ hg test-sts g
+ g,c,f,e,d,b,a, (no-eol)
+
+Display the sort of "i" for reference:
+
+ $ hg test-sts i
+ i,e,d,b,h,*,a, (no-eol) (glob)
+
+Check that the common part of inherited(g) and excl(k) is iterated over after
+"i":
+
+ $ hg test-sts j
+ j,g,c,f,i,e,d,b,h,*,a, (no-eol) (glob)
+
+ $ cd ..
+
+
+Example 9: postponed iteration of common ancestors between both parts
+=====================================================================
+
+This is a combination of example 7 and 8 at the same time.
+Both excl(i) and excl(j) share a common part.
+Same with inherited(i) and inherited(j).
+
+We test that the walk on the common ancestors in both cases is properly
+postponed when considering sort(k).
+
+# k
+# |
+# ----<----
+# | |
+# i j
+# | |
+# --<-- --<--
+# | | | |
+# c f g h
+# | | | |
+# | e | |
+# | | | |
+# +--]|[--- | <- rest of excl(i) postponed to excl(j)
+# | | |
+# b ----+---- <- rest of inherited(i) postponed to inherited(j)
+# | |
+# | d
+# | |
+# ----+----
+# |
+# a
+
+ $ hg init example-9
+ $ cd example-9
+ $ 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.'
+ $ hg test-log
+ o tip rank=15
+ |
+ o k rank=14
+ |\
+ | o j rank=9
+ | |\
+ o \ \ i rank=7
+ |\ \ \
+ | | | o h rank=5
+ | | | |
+ | | | o rank=4
+ | | | |
+ | | | o rank=3
+ | | | |
+ | | o | g rank=4
+ | | | |
+ | | o | rank=3
+ | | | |
+ | o | | f rank=4
+ | | | |
+ | o---+ e rank=3
+ | / /
+ | | o d rank=2
+ | | |
+ o | | c rank=3
+ |/ /
+ o / b rank=2
+ |/
+ o a rank=1
+
+
+Display sort(i) for reference:
+
+ $ hg test-sts i
+ i,c,b,f,e,d,a, (no-eol)
+
+Display sort(j) for reference:
+
+ $ hg test-sts j
+ j,g,*,b,h,*,d,a, (no-eol) (glob)
+
+Check that the end of excl(i) is postponed to excl(j), the end of inherited(i)
+is postponed to inherited(j) in sort(k):
+
+ $ hg test-sts k
+ k,i,c,f,e,j,g,*,b,h,*,d,a, (no-eol) (glob)
+
+ $ cd ..