changeset 4853:004704c5834f

stable-doc: add multiples example for the simple cases

--- a/hgext3rd/evolve/stablesort.py	Thu Sep 26 10:00:51 2019 +0200
+++ b/hgext3rd/evolve/stablesort.py	Wed Sep 25 18:23:37 2019 +0200
@@ -7,7 +7,7 @@
 # This software may be used and distributed according to the terms of the
 # GNU General Public License version 2 or any later version.
 
-"""Stable sorting for the mercurial graph
+r"""Stable sorting for the mercurial graph
 
 The goal is to provided an efficient, revnum independant way, to sort revisions
 in a topologicaly. Having it independant from revnum is important to make it
@@ -16,6 +16,30 @@
 
 This docstring describe the currently preferred solution:
 
+Probleme definition
+-------------------
+
+We want a way to order revision in the graph. For a linear history things are simple::
+
+  A -> B -> C -> D -> E -> F -> G -> H
+
+  stablesort(::H) = [A, B, C, D, E, F, G, H]
+
+However, things become more complicated when the graph is not linear::
+
+  A -> B -> C -> D -> G -> H
+         \         /
+          > E -> F
+
+  stablesort(::A) = [A]
+  stablesort(::B) = [A, B]
+  stablesort(::C) = [A, B, C]
+  stablesort(::D) = [A, B, C, D]
+  stablesort(::E) = [A, B, E]
+  stablesort(::F) = [A, B, E, F]
+  stablesort(::G) = [A, B, C, D, E, F, G]
+  stablesort(::H) = [A, B, C, D, E, F, G, H]
+
 Basic principle:
 ----------------
 
@@ -24,7 +48,13 @@
 
 For non merge revisions, the definition is simple::
 
-    stablesort(::r) == stablesort(p1(r)) + r
+  stablesort(::r) == stablesort(p1(r)) + r
+
+This is visible in some of the example above:
+
+  stablesort(::B) = stablesort(::A) + [B]
+  stablesort(::E) = stablesort(::B) + [E]
+  stablesort(::H) = stablesort(::G) + [H]
 
 For merge revision, we reuse as much as possible of the parents order:
 
@@ -34,11 +64,23 @@
                        + [i for in in stablesort(ph) if in ph % pl]
                        + m
 
-The `ph % pl` set of revision is called the "exclusive part". In this area we
-try to reuse as much as the stable-sorted order for `ph`. In simple case, the
-`[i for i in stablesort(ph) if i in ph % pl]` is just the contiguous final range of
-`stablesort(ph)`. However in more advance case, this will not be contiguous and
-we'll need to skip over multiple parts of `stablesort(ph)` to cover `ph % pl`.
+This is visible in the example above:
+
+    stablesort(::G) = stablesort(::D) + [stablesort(::F) % ::D] + [G]
+    stablesort(::G) = [A, B, C, D] + ([A, B, E, F] - [A, B, C ,D]) + [G]
+    stablesort(::G) = [A, B, C, D] + [E, F] + [G]
+
+To decide which parent goes first in the stablesort, we need to order them. The
+`stablemin/stablemax` function express this. The actual order used is an
+implementation details (eg: could be node-order)
+
+The `ph % pl` set of revision is called the "exclusive part". It correspond to
+all revisions ancestors of `ph` (`ph` included) that are not ancestors of `pl`
+(`pl` included).  In this area we try to reuse as much as the stable-sorted
+order for `ph`. In simple case, the `[i for i in stablesort(ph) if i in ph %
+pl]` is just the contiguous final range of `stablesort(ph)`. However in more
+advance case, this will not be contiguous and we'll need to skip over multiple
+parts of `stablesort(ph)` to cover `ph % pl`.
 
 Another important details is that, in practice, the sorted revision are always
 walked backward, from the head of the set of revisions.