# Code dedicated to the computation of stable sorting

#

# These stable sorting are used stable ranges

#

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

stable from one repository to another, unlocking various capabilities. For

example it can be used for discovery purposes.

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:

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

We are always talking about set of revision defined by a single heads

(eg: `stablesort(::r)`)

For non merge revisions, the definition is simple::

  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:

    pl = stablemin(parents(m))

    ph = stablemax(parents(m))

    stablesort(::m) == stablesort(pl)

                       + [i for in in stablesort(ph) if in ph % pl]

                       + m

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, 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)`. 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:

  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

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

The stable sort assume we already have 2 important property cached for each

changesets:

1) changeset depth == len(::r)

2) first merge == max(merge() and ::r)

Caching strategy

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

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

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]

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:

    (jump-point, jump-destination, section-size)

* jump-point is the last revision number we should iterate over before jumping,

* jump-destination is the next revision we should iterate over after the jump point,

* section-size is the number of revision to be iterated before reaching jump-point.

the section-size is not directly used when doing a stable-sorted walk. However

it is useful for higher level piece of code to take decision without having to

actually walk the graph, (see stable range documentation).

For each merge, we store the set of jumps that cover the exclusive side.

Practical data

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

The mercurial repository has simple branching and few jumps:

    number of revisions:        69771

    number of merge:             2734

    number of jumps:             2950

    average jumps:                  1.079

    median jumps:                   1

    90% jumps:                      1

    99% jumps:                      3

    max jumps:                      6

    jump cache size:           35 400 bytes

Mozilla's branching is fairly simple too:

    number of revisions:       435078

    number of merge:            21035

    number of jumps:            31434

    average jumps:                  1.494

    median jumps:                   1

    90% jumps:                      2

    99% jumps:                      9

    max jumps:                    169

    jump cache size:          377 208 bytes

Pypy has a more complicated branching history but jumps cache remains reasonable

    number of revisions:        95010

    number of merge:             7911

    number of jumps:            24326

    average jumps:                  3.075

    median jumps:                   1

    90% jumps:                      5

    99% jumps:                     40

    max jumps:                    329

    jump cache size:          291 912 bytes

This still apply to larger private project:

    number of revisions:       605011

    number of merge:           118109

    number of jumps:           314925

    average jumps:                  2.667

    median jumps:                   1

    90% jumps:                      3

    99% jumps:                     34

    max jumps:                    660

    jump cache size:        3 779 100 bytes

It is worth noting that the last jump could be computed form other information,

removing one jump storage per merge. However this does not seems to be an issue

worth the troubles for now.

"""

import array

import collections

import struct

from mercurial import (

    commands,

    localrepo,

    error,

    node as nodemod,

    pycompat,

    scmutil,

)

from mercurial.i18n import _

from . import (

    compat,

    depthcache,

    exthelper,

    utility,

    genericcaches,

)

filterparents = utility.filterparents

eh = exthelper.exthelper()

def _mergepoint_tie_breaker(repo):

    """the key use to tie break merge parent

    Exists as a function to help playing with different approaches.

    Possible other factor are:

        * depth of node,

        * number of exclusive merges,

        * number of jump points.

        * <insert-your-idea>

    """

    node = repo.changelog.node

    depth = repo.depthcache.get

    def key(rev):

        return (-depth(rev), node(rev))

    return key

@eh.command(

    b'debugstablesort',

    [

        (b'r', b'rev', [], b'heads to start from'),

        (b'', b'method', b'branchpoint', b"method used for sorting, one of: "

         b"branchpoint, basic-mergepoint and basic-headstart"),

        (b'l', b'limit', b'', b'number of revision display (default to all)')

    ] + commands.formatteropts,

    _(b''))

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

    """display the ::REVS set topologically sorted in a stable way

    """

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

    method = opts['method']

    sorting = _methodmap.get(method)

    if sorting is None:

        valid_method = b', '.join(sorted(_methodmap))

        raise error.Abort(b'unknown sorting method: "%s"' % method,

                          hint=b'pick one of: %s' % valid_method)

    displayer = compat.changesetdisplayer(ui, repo, pycompat.byteskwargs(opts),

                                          buffered=True)

    kwargs = {}

    if opts['limit']:

        kwargs['limit'] = int(opts['limit'])

    for r in sorting(repo, revs, **kwargs):

        ctx = repo[r]

        displayer.show(ctx)

        displayer.flush(ctx)

    displayer.close()

@eh.command(

    b'debugstablesortcache',

    [] + commands.formatteropts,

    _(b''))

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

    """display data about the stable sort cache of a repository

    """

    unfi = repo.unfiltered()

    revs = unfi.revs('all()')

    nbrevs = len(revs)

    ui.write('number of revisions: %12d\n' % nbrevs)

    merge = unfi.revs('merge()')

    nbmerge = len(merge)

    cache = unfi.stablesort

    ui.write('number of merge:     %12d\n' % nbmerge)

    alljumps = []

    alljumpssize = []

    for r in merge:

        jumps = cache.getjumps(unfi, r)

        if jumps is None:

            continue # not a merge

        jumps = list(jumps)

        alljumps.append(jumps)

        alljumpssize.append(len(jumps))

    nbjumps = sum(alljumpssize)

    ui.write('number of jumps:     %12d\n' % nbjumps)

    if not nbjumps:

        return 0

    avgjumps = nbjumps / float(len(alljumpssize))

    ui.write('average jumps:                 %6.3f\n' % avgjumps)

    alljumpssize.sort()

    medianjumps = alljumpssize[len(alljumpssize) // 2]

    ui.write('median jumps:        %12d\n' % medianjumps)

    tensjumps = alljumpssize[len(alljumpssize) * 9 // 10]

    ui.write('90%% jumps:           %12d\n' % tensjumps)

    centsjumps = alljumpssize[len(alljumpssize) * 99 // 100]

    ui.write('99%% jumps:           %12d\n' % centsjumps)

    ui.write('max jumps:           %12d\n' % max(alljumpssize))

    ui.write('jump cache size:     %12d bytes\n' % (nbjumps * 12))

def stablesort_branchpoint(repo, revs, mergecallback=None):

    """return '::revs' topologically sorted in "stable" order

    This is a depth first traversal starting from 'nullrev', using node as a

    tie breaker.

    """

    # Various notes:

    #

    # * Bitbucket is used dates as tie breaker, that might be a good idea.

    #

    # * It seemds we can traverse in the same order from (one) head to bottom,

    #   if we the following record data for each merge:

    #

    #  - highest (stablesort-wise) common ancestors,

    #  - order of parents (tablesort-wise)

    cl = repo.changelog

    parents = cl.parentrevs

    nullrev = nodemod.nullrev

    n = cl.node

    # step 1: We need a parents -> children mapping for 2 reasons.

    #

    # * we build the order from nullrev to tip

    #

    # * we need to detect branching

    children = collections.defaultdict(list)

    for r in cl.ancestors(revs, inclusive=True):

        ps = filterparents(parents(r))

        if not ps:

            children[nullrev].append(r)

        for p in ps:

            children[p].append(r)

    # step two: walk back up

    # * pick lowest node in case of branching

    # * stack disregarded part of the branching

    # * process merge when both parents are yielded

    # track what changeset has been

    seen = [0] * (max(revs) + 2)

    seen[nullrev] = True # nullrev is known

    # starts from repository roots

    # reuse the list form the mapping as we won't need it again anyway

    stack = children[nullrev]

    if not stack:

        return []

    if 1 < len(stack):

        stack.sort(key=n, reverse=True)

    # list of rev, maybe we should yield, but since we built a children mapping we are 'O(N)' already

    result = []

    current = stack.pop()

    while current is not None or stack:

        if current is None:

            # previous iteration reached a merge or an unready merge,

            current = stack.pop()

            if seen[current]:

                current = None

                continue

        ps = filterparents(parents(current))

        if not all(seen[p] for p in ps):

            # we can't iterate on this merge yet because other child is not

            # yielded yet (and we are topo sorting) we can discard it for now

            # because it will be reached from the other child.

            current = None

            continue

        assert not seen[current]

        seen[current] = True

        result.append(current) # could be yield, cf earlier comment