changeset 4854:79c9bc7663c2

stable-doc: add more advanced examples

--- a/hgext3rd/evolve/stablerange.py	Wed Sep 25 18:23:37 2019 +0200
+++ b/hgext3rd/evolve/stablerange.py	Wed Sep 25 19:31:44 2019 +0200
@@ -6,7 +6,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 range
+r"""stable range
 
 General Goals and Properties
 ---------------------------

--- a/hgext3rd/evolve/stablesort.py	Wed Sep 25 18:23:37 2019 +0200
+++ b/hgext3rd/evolve/stablesort.py	Wed Sep 25 19:31:44 2019 +0200
@@ -66,23 +66,61 @@
 
 This is visible in the example above:
 
-    stablesort(::G) = stablesort(::D) + [stablesort(::F) % ::D] + [G]
+    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)
+implementation details (eg: could be node-order, in the example it is
+alphabetical 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`.
+pl]` is just the contiguous final range of `stablesort(ph)`. This is the case
+in the example we have looked at so far::
+
+    stablesort(::F) - ::D = [A, B, E, F] - [A, B, C ,D] = stablesort(::F)[-2:]
+
+
+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`.Let's have a
+look at an example of such case::
+
+  A - B ----- F - H
+   \    \   /   /
+    \     E - G
+     \  /   /
+      C - D
+
+We have the following stablesort:
 
-Another important details is that, in practice, the sorted revision are always
+  stablesort(::A) = [A]
+  stablesort(::B) = [A, B]
+  stablesort(::C) = [A, C]
+  stablesort(::D) = [A, C, D]
+  stablesort(::E) = [A, B, C, E]
+  stablesort(::F) = [A, B, C, E, F]
+  stablesort(::G) = [A, B, C, D, E, G]
+  stablesort(::H) = [A, B, C, E, F, D, G, H]
+
+The stable order of `stablesort(::H)` match our definition::
+
+
+  stablesort(::H) = [A, B, C, E, F] + [D, G] + [H]
+  stablesort(::F) = [A, B, C, E, F]
+  stablesort(::G) - ::F = [A, B, C, D, E, G] - [A, B, C, E, F] = [D, G]
+
+In this order, we reuse all of `stablesort(::H)`, but the subset of
+`stablesort(::G)` we reuse is not contiguous, we had to skip over 'E' that is
+already contained inside ::F.
+
+Usage
+-----
+
+An important details is that, in practice, the sorted revision are always
 walked backward, from the head of the set of revisions.
 
 preexisting cached data
@@ -99,12 +137,44 @@
 
 Since we always walk from the head, the iteration mostly have to follow the
 unique parent of non merge revision. For merge revision, we need to iterate
-through one of the parent before coming back to the other parent eventually.
+over the revisions accessible only through one of the parent before coming back
+to the other parent eventually.
+
+To efficiently cache the revision path we need to walk, we records "jumps". A
+jump is a revision where the next revision (in the stable sort) will not be a
+parent of the current revision, but another revision in the graph.
+
+In the first (simple) example above, we had::
+
+  A -> B -> C -> D -> G -> H
+         \         /
+          > E -> F
+
+  stablesort(::D) = [A, B, C, D]
+  stablesort(::F) = [A, B, E, F]
+  stablesort(::G) = [A, B, C, D, E, F, G]
 
-To effiently cache the path we need to walk, we records "jumps". A jump is a
-point where the next revision will not be a parent of the current revision, but
-another point in the graph. This correspond to point were we need to "come back
-to the other parent".
+In this case, when caching stable sort data for `G`, we need to record the `E
+-> D` jump. This correspond to point were we are done iterating over the
+revision accessible through `F` and we need to "jump back to the other parent"
+of `G`: `D`.
+
+
+
+In the second (more advance) example above, we had::
+
+  A - B ----- F - H
+   \    \   /   /
+    \     E - G
+     \  /   /
+      C - D
+
+  stablesort(::F) = [A, B, C, E, F]
+  stablesort(::G) = [A, B, C, D, E, G]
+  stablesort(::H) = [A, B, C, E, F, D, G, H]
+
+In this case, when caching stable sort data for `G`, we need to record the `G
+-> D` and the `D -> F` jumps.
 
 Jumps are recorded using the following formats: