--- 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: