# Code dedicated to the computation and properties of "stable ranges"

#

# These stable ranges are use for obsolescence markers discovery

#

# Copyright 2017 Pierre-Yves David <pierre-yves.david@ens-lyon.org>

#

# This software may be used and distributed according to the terms of the

# GNU General Public License version 2 or any later version.

r"""stable range

General Goals and Properties

---------------------------

Stable-ranges get useful when some logic needs a recursive way to slice the

history of a repository in smaller and smaller group of revisions. Here is

example of such use cases:

* **bundle caching:**

  With an easy way to slice any subsets of history into stable-ranges, we

  can cache a small number of bundles covering these ranges and reuse them for

  other pull operations. Even if the pull operation have different boudaries.

* **metadata discovery:**

  With a simple way to recursively look at smaller and smaller ranges, an

  algorithm can do fine-grained discovery of area of history where some mutable

  metadata differ from one repository to another. Such meta data can be

  obsolescence markers, CI status, lightweight stag, etc...

To fix these use cases best, stable-ranges need some important properties:

* the total number of ranges needed to cover a full repository is well bounded.

* the minimal number of ranges to cover an arbitrary subset of the history is well bounded

* for the same section of history, the range will be the same on any

  repositories,

* the ranges are cheap to compute iteratively, each new revisions re-uses the

  ranges previous revisions uses.

Simple introduction to the Concepts

-----------------------------------

To keep things simple, let us look at the issue on a linear history::

  A -> B -> C -> D -> E -> F -> G -> H

To make sure we have range that cover each part of the history with a good

granularity we use some binary recursion. The standard stable range will be:

 [A -> B -> C -> D -> E -> F -> G -> H] size 8

 [A -> B -> C -> D]  [E -> F -> G -> H] size 4

 [A -> B]  [C -> D]  [E -> F]  [G -> H] size 2

 [A]  [B]  [C]  [D]  [E]  [F]  [G]  [H] size 1

Well bounded total number of ranges:

````````````````````````````````````

This binary slicing make sure we keep the total number of stable ranges under control.

As you can see, we have N size 1 ranges. They are trivial and we don't care

about them. Then we have: N/2 size 2 ranges + N/4 size 4 ranges + N/8 size 8

ranges, etc... So a total of about "length(repo)" standard ranges.

Well bounded number of range to cover a subset:

```````````````````````````````````````````````

Any subset of the history can be expressed with this standard ranges.

For example, [A, F] subset, can be covered with 2 ranges::

  [A ->[B -> C -> D]  [E -> F]

A less strivial example [B, F], still requires a small number of ranges (3)::

  [B]  [C -> D]  [E -> F]

In practice, any subset can be expressed in at most "2 x log2(length(subset))"

stable range, well bounded value.

Cheap incremental updates

`````````````````````````

The scheme describe above result in 2N subranges for a repository is size N. We

do not want to have to recompute these 2N stable-ranges whenever a new revision

is added to the repository. To achieve these, the stable-ranges are defined by

**fixed boundaries** that are independant from the total size of the

repository. Here is how it looks like in our example.

We start with a repository having only [A, F]. Notice how we still creates

power of two sized stable range::

  [A -> B -> C -> D]

  [A -> B]  [C -> D]  [E -> F]

  [A]  [B]  [C]  [D]  [E]  [F]

This we simply adds a new revision G, we reuse more the range we already have::

  [A -> B -> C -> D]

  [A -> B]  [C -> D]  [E -> F]

  [A]  [B]  [C]  [D]  [E]  [F]  [G]

Adding H is a bigger even as we read a new boundary.

  [A -> B -> C -> D -> E -> F -> G -> H]

  [A -> B -> C -> D]  [E -> F -> G -> H]

  [A -> B]  [C -> D]  [E -> F]  [G -> H]

  [A]  [B]  [C]  [D]  [E]  [F]  [G]  [H]

At most, adding a new revision `R` will introduces `log2(length(::R))` new

stable ranges.

More advanced elements

----------------------

Of course, the history of repository is not as simple as our linear example. So

how do we deal with the branching and merging? To do so, we leverage the

"stable sort" algorithm defined in the `stablesort.py` module. To define the

stable range that compose a set of revison `::R`, we linearize the space by

sorting it. The stable sort algorithm has two important property:

First, it give the same result on different repository. So we can use it to

algorithm involving multiple peers.

Second, in case of merge, it reuse the same order as the parents as much as possible.

This is important to keep reusing existing stable range as the repository grow.

How are ranges defined?

```````````````````````

To keep things small, and simple, a stable range always contains the final part

of a `stablesort(::R)` set of revision. It is defined by two items:

* its head revision, the R in `stablesort(::R)`

* the size of that range... well almost, for implementation reason, it uses the

  index of the first included item. Or in other word, the number of excluded

  initial item in `stablesort(::R)`.

Lets look at a practical case. In our initial example, `[A, B, C, D, E, F, G,

H]` is H-0; `[E, F, G, H]` is H-4; `[G, H]` is H-6 and `[H]` is H-7.

Let us look at a non linar graph::

 A - B - C - E

       |    /

        -D

and assume that `stablesort(::E) = [A, B, C, D, E]`. Then `[A, B, C]` is C-0,

`[A, B, D]` is D-0; `[D, E]` is E-3, `[E]` is E-4, etc...

Slicing in a non linear context

```````````````````````````````

Branching can also affect the way we slice things.

The small example above offers a simple example. For a size 5 (starting at the

root), standard slicing will want a size 4 part and size 1 part. So, in a

simple linear space `[A, B, C, D, E]` would be sliced as `[A, B, C, D] + [E]`.

However, in our non-linear case, `[A, B, C, D]` has two heads (C and D) and

cannot be expressed with a single range. As a result the range will be sliced

into more sub ranges::

    stdslice(A-0) = [A, B, C] + [D] + [E] = C-0 + D-2 + A-4

Yet, this does not mean ranges containing a merge will always result in slicing

with many revision. the sub ranges might also silently contains them. Let us

look at an exemple::

  A - B - C - D - E --- G - H

        |             /

         ---------- F

with::

  `stablesort(::H) == [A, B, C, D, E, F, G, H]`

then::

  stdslice(H-0) = [A, B, C, D] + [E, F, G, H] = D-0 + H-4

As a result the non linearity will increase the number of subranges involved,

but in practice the impact stay limited.

The total number of standard subranges stay under control with about

`O(log2(N))` new stable range introduced for each new revision. In practice the

total number of stableranges we have is about `O(length(repo))`

In addition, it is worth nothing that the head of the extra ranges we have to

use will match the destination of the "jump" cached by the stablesort

algorithm. So, all this slicing can usually be done without iterating over the

stable sorted revision.

Caching Strategy

----------------

The current caching strategy use a very space inefficient sqlite database.

testing show it often take 100x more space than what basic binary storage would

take. The sqlite storage was very useful at the proof of concept stage.

Since all new stable-ranges introduced by a revision R will be "R headed". So we

could easily store their standard subranges alongside the revision information

to reuse the existing revision index.

Subrange information can be efficiently stored, a naive approach storing all

stable ranges and their subranges would requires just 2 integer per range + 2

integer for any extra sub-ranges other than the first and last ones.

We can probably push efficiency further by taking advantage of the large

overlap in subranges for one non-merge revision to the next. This is probably a

premature optimisation until we start getting actual result for a naive binary

storage.

To use this at a large scale, it would be important to compute these data at

commit time and to exchange them alongside the revision over the network. This

is similar to what we do for other cached data.

It is also important to note that the smaller ranges can probably be computed

on the fly instead of being cached. The exact tradeoff would requires some

field testing.

Performance

-----------

The current implementation has not been especially optimized for performance.

The goal was mostly to get the order of magnitude of the algorithm complexity.

The result are convincing: medium repository get a full cache warming in a

couple of seconds and even very large and branchy repository get a fully warmed

in the order of tens of minutes. We do not observes a complexity explosion

making the algorithm unusable of large repositories.

A better cache implementation combined with an optimized version of the

algorithm should give much faster performance. Combined with commit-time

computation and exchange over the network, the overall impact of this should be

invisible to the user.

The stable range is currently successfully used in production for 2 use cases:

* obsolescence markers discovery,

* caching precomputed bundle while serving pulls

practical data

--------------

The evolve repository:

    number of revisions:          4833

    number of heads:                15

    number of merge:               612 ( 12%)

    number of range:              4826

      with   2 subranges:         4551 ( 94%)

      with   3 subranges:          255 (  5%)

      with   4 subranges:           12 (  0%)

      with   5 subranges:            7 (  0%)

      with   8 subranges:            1 (  0%)

    average range/revs:              0.99

    Estimated approximative size of a naive compact storage:

           41 056 bytes

    Current size of the sqlite cache (for comparison):

        5 312 512 bytes

The mercurial repository:

    number of revisions:         42849

    number of heads:                 2

    number of merge:              2647 (  6%)

    number of range:             41279

      with   2 subranges:        39740 ( 96%)

      with   3 subranges:         1494 (  3%)

      with   4 subranges:           39 (  0%)

      with   5 subranges:            5 (  0%)

      with   7 subranges:            1 (  0%)

    average range/revs:              0.96

    Estimated approximative size of a naive compact storage:

           342 968 bytes

    Current size of the sqlite cache (for comparison):

        62 803 968 bytes

The pypy repository (very brancy history):

    number of revisions:         97409

    number of heads:               183

    number of merge:              8371 (  8%)

    number of range:            107025

      with   2 subranges:       100166 ( 93%)

      with   3 subranges:         5839 (  5%)

      with   4 subranges:          605 (  0%)

      with   5 subranges:          189 (  0%)

      with   6 subranges:           90 (  0%)

      with   7 subranges:           38 (  0%)

      with   8 subranges:           18 (  0%)

      with   9 subranges:            9 (  0%)

      with  10 subranges:           15 (  0%)

      with  11 subranges:            4 (  0%)

      with  12 subranges:            6 (  0%)

      with  13 subranges:            7 (  0%)

      with  14 subranges:            6 (  0%)

      with  15 subranges:            1 (  0%)

      with  16 subranges:            2 (  0%)

      with  17 subranges:            2 (  0%)

      with  18 subranges:            3 (  0%)

      with  19 subranges:            2 (  0%)

      with  20 subranges:            3 (  0%)

      with  25 subranges:            1 (  0%)

      with  27 subranges:            1 (  0%)

      with  31 subranges:            3 (  0%)

      with  32 subranges:            2 (  0%)

      with  33 subranges:            1 (  0%)

      with  35 subranges:            1 (  0%)

      with  43 subranges:            1 (  0%)

      with  44 subranges:            1 (  0%)

      with  45 subranges:            2 (  0%)

      with  47 subranges:            1 (  0%)

      with  51 subranges:            1 (  0%)

      with  52 subranges:            1 (  0%)

      with  57 subranges:            1 (  0%)

      with  65 subranges:            1 (  0%)

      with  73 subranges:            1 (  0%)

      with  79 subranges:            1 (  0%)

    average range/revs:              1.10

    Estimated approximative size of a naive compact storage:

          934 176 bytes

    Current size of the sqlite cache (for comparison):

      201 236 480 bytes

A private and branchy repository:

    number of revisions:        605011

    number of heads:             14061

    number of merge:            118109 ( 19%)

    number of range:            747625

      with   2 subranges:       595985 ( 79%)

      with   3 subranges:       130196 ( 17%)

      with   4 subranges:        14093 (  1%)

      with   5 subranges:         4090 (  0%)

      with   6 subranges:          741 (  0%)

      with   7 subranges:          826 (  0%)

      with   8 subranges:         1313 (  0%)

      with   9 subranges:           83 (  0%)

      with  10 subranges:           22 (  0%)

      with  11 subranges:            9 (  0%)

      with  12 subranges:           26 (  0%)

      with  13 subranges:            5 (  0%)

      with  14 subranges:            9 (  0%)

      with  15 subranges:            3 (  0%)

      with  16 subranges:          212 (  0%)

      with  18 subranges:            6 (  0%)

      with  19 subranges:            3 (  0%)

      with  24 subranges:            1 (  0%)

      with  27 subranges:            1 (  0%)

      with  32 subranges:            1 (  0%)

    average range/revs:              1.23

    Estimated approximative size of a naive compact storage:

        7 501 928 bytes

    Current size of the sqlite cache (for comparison):

    1 950 310 400 bytes

"""

import abc

import functools

import heapq

import math

import time

from mercurial import (

    error,

    node as nodemod,

    scmutil,

    util,

)

from mercurial.i18n import _

from . import (

    compat,

    exthelper,

    firstmergecache,

    stablesort,

    utility,

)

filterparents = utility.filterparents

eh = exthelper.exthelper()

#################################

### Stable Range computation  ###

#################################

def _hlp2(i):

    """return highest power of two lower than 'i'"""

    return 2 ** int(math.log(i - 1, 2))

def subrangesclosure(repo, stablerange, heads):

    """set of all standard subrange under heads

    This is intended for debug purposes. Range are returned from largest to

    smallest in terms of number of revision it contains."""

    subranges = stablerange.subranges

    toproceed = [(r, 0, ) for r in heads]

    ranges = set(toproceed)

    while toproceed:

        entry = toproceed.pop()

        for r in subranges(repo, entry):

            if r not in ranges:

                ranges.add(r)

                toproceed.append(r)

    ranges = list(ranges)

    n = repo.changelog.node

    rangelength = stablerange.rangelength

    ranges.sort(key=lambda r: (-rangelength(repo, r), n(r[0])))

    return ranges

_stablerangemethodmap = {

    b'branchpoint': lambda repo: stablerange(),

    b'default': lambda repo: repo.stablerange,

    b'basic-branchpoint': lambda repo: stablerangebasic(),

    b'basic-mergepoint': lambda repo: stablerangedummy_mergepoint(),

    b'mergepoint': lambda repo: stablerange_mergepoint(),

}

@eh.command(

    b'debugstablerange',

    [

        (b'r', b'rev', [], b'operate on (rev, 0) ranges for rev in REVS'),

        (b'', b'subranges', False, b'recursively display data for subranges too'),

        (b'', b'verify', False, b'checks subranges content (EXPENSIVE)'),

        (b'', b'method', b'branchpoint',

         b'method to use, one of "branchpoint", "mergepoint"')

    ],

    _(b''))

def debugstablerange(ui, repo, **opts):

    """display standard stable subrange for a set of ranges

    Range as displayed as '<node>-<index> (<rev>, <depth>, <length>)', use

    --verbose to get the extra details in ().

    """

    short = nodemod.short

    revs = scmutil.revrange(repo, opts['rev'])

    if not revs:

        raise error.Abort(b'no revisions specified')

    if ui.verbose:

        template = b'%s-%d (%d, %d, %d)'

        def _rangestring(repo, rangeid):

            return template % (

                short(node(rangeid[0])),

                rangeid[1],

                rangeid[0],

                depth(unfi, rangeid[0]),

                length(unfi, rangeid)

            )