# HG changeset patch # User Pierre-Yves David # Date 1569432704 -7200 # Node ID 79c9bc7663c222e14d762dbd9f358440fd8c2201 # Parent 004704c5834fd0201771b4f0aa74f77a47bb2879 stable-doc: add more advanced examples diff -r 004704c5834f -r 79c9bc7663c2 hgext3rd/evolve/stablerange.py --- 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 --------------------------- diff -r 004704c5834f -r 79c9bc7663c2 hgext3rd/evolve/stablesort.py --- 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: