hgext3rd/topic/evolvebits.py
author Anton Shestakov <av6@dwimlabs.net>
Fri, 08 May 2020 22:50:09 +0800
branchmercurial-4.6
changeset 5368 844b1ad5b34b
parent 5312 9035901412e6
permissions -rw-r--r--
test-compat: merge mercurial-4.7 into mercurial-4.6
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
1982
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
     1
import collections
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
     2
3697
6aff4bb3970d compat: drop compatibility layer for successorssets
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 3017
diff changeset
     3
from mercurial import (
6aff4bb3970d compat: drop compatibility layer for successorssets
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 3017
diff changeset
     4
    obsutil,
6aff4bb3970d compat: drop compatibility layer for successorssets
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 3017
diff changeset
     5
)
2694
8a222745a71c topic: adapt to function migrate to obsutil
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 1982
diff changeset
     6
1982
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
     7
# Copied from evolve 081605c2e9b6
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
     8
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
     9
def _orderrevs(repo, revs):
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    10
    """Compute an ordering to solve instability for the given revs
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    11
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    12
    revs is a list of unstable revisions.
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    13
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    14
    Returns the same revisions ordered to solve their instability from the
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    15
    bottom to the top of the stack that the stabilization process will produce
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    16
    eventually.
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    17
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    18
    This ensures the minimal number of stabilizations, as we can stabilize each
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    19
    revision on its final stabilized destination.
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    20
    """
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    21
    # Step 1: Build the dependency graph
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    22
    dependencies, rdependencies = builddependencies(repo, revs)
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    23
    # Step 2: Build the ordering
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    24
    # Remove the revisions with no dependency(A) and add them to the ordering.
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    25
    # Removing these revisions leads to new revisions with no dependency (the
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    26
    # one depending on A) that we can remove from the dependency graph and add
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    27
    # to the ordering. We progress in a similar fashion until the ordering is
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    28
    # built
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    29
    solvablerevs = [r for r in sorted(dependencies.keys())
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    30
                    if not dependencies[r]]
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    31
    ordering = []
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    32
    while solvablerevs:
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    33
        rev = solvablerevs.pop()
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    34
        for dependent in rdependencies[rev]:
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    35
            dependencies[dependent].remove(rev)
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    36
            if not dependencies[dependent]:
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    37
                solvablerevs.append(dependent)
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    38
        del dependencies[rev]
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    39
        ordering.append(rev)
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    40
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    41
    ordering.extend(sorted(dependencies))
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    42
    return ordering
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    43
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    44
def builddependencies(repo, revs):
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    45
    """returns dependency graphs giving an order to solve instability of revs
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    46
    (see _orderrevs for more information on usage)"""
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    47
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    48
    # For each troubled revision we keep track of what instability if any should
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    49
    # be resolved in order to resolve it. Example:
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    50
    # dependencies = {3: [6], 6:[]}
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    51
    # Means that: 6 has no dependency, 3 depends on 6 to be solved
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    52
    dependencies = {}
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    53
    # rdependencies is the inverted dict of dependencies
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    54
    rdependencies = collections.defaultdict(set)
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    55
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    56
    for r in revs:
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    57
        dependencies[r] = set()
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    58
        for p in repo[r].parents():
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    59
            try:
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    60
                succ = _singlesuccessor(repo, p)
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    61
            except MultipleSuccessorsError as exc:
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    62
                dependencies[r] = exc.successorssets
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    63
                continue
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    64
            if succ in revs:
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    65
                dependencies[r].add(succ)
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    66
                rdependencies[succ].add(r)
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    67
    return dependencies, rdependencies
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    68
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    69
def _singlesuccessor(repo, p):
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    70
    """returns p (as rev) if not obsolete or its unique latest successors
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    71
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    72
    fail if there are no such successor"""
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    73
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    74
    if not p.obsolete():
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    75
        return p.rev()
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    76
    obs = repo[p]
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    77
    ui = repo.ui
5312
9035901412e6 topic: provide cache to successorssets() in _singlesuccessor()
Anton Shestakov <av6@dwimlabs.net>
parents: 5019
diff changeset
    78
    cache = {}
9035901412e6 topic: provide cache to successorssets() in _singlesuccessor()
Anton Shestakov <av6@dwimlabs.net>
parents: 5019
diff changeset
    79
    newer = obsutil.successorssets(repo, obs.node(), cache=cache)
1982
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    80
    # search of a parent which is not killed
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    81
    while not newer:
4814
48b30ff742cb python3: use format-source to run byteify-strings in .py files
Raphaël Gomès <rgomes@octobus.net>
parents: 3697
diff changeset
    82
        ui.debug(b"stabilize target %s is plain dead,"
48b30ff742cb python3: use format-source to run byteify-strings in .py files
Raphaël Gomès <rgomes@octobus.net>
parents: 3697
diff changeset
    83
                 b" trying to stabilize on its parent\n" %
1982
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    84
                 obs)
5019
967e9a87e82d cleanup: replace .parents()[0] by .p1()
Martin von Zweigbergk <martinvonz@google.com>
parents: 4814
diff changeset
    85
        obs = obs.p1()
5312
9035901412e6 topic: provide cache to successorssets() in _singlesuccessor()
Anton Shestakov <av6@dwimlabs.net>
parents: 5019
diff changeset
    86
        newer = obsutil.successorssets(repo, obs.node(), cache=cache)
3017
0884856a4143 stack: handle basic case of splitting with crash
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 2922
diff changeset
    87
    if 1 < len(newer):
0884856a4143 stack: handle basic case of splitting with crash
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 2922
diff changeset
    88
        # divergence case
0884856a4143 stack: handle basic case of splitting with crash
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 2922
diff changeset
    89
        # we should pick as arbitrary one
1982
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    90
        raise MultipleSuccessorsError(newer)
3017
0884856a4143 stack: handle basic case of splitting with crash
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 2922
diff changeset
    91
    elif 1 < len(newer[0]):
4814
48b30ff742cb python3: use format-source to run byteify-strings in .py files
Raphaël Gomès <rgomes@octobus.net>
parents: 3697
diff changeset
    92
        splitheads = list(repo.revs(b'heads(%ln::%ln)', newer[0], newer[0]))
3017
0884856a4143 stack: handle basic case of splitting with crash
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 2922
diff changeset
    93
        if 1 < len(splitheads):
0884856a4143 stack: handle basic case of splitting with crash
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 2922
diff changeset
    94
            # split case, See if we can make sense of it.
0884856a4143 stack: handle basic case of splitting with crash
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 2922
diff changeset
    95
            raise MultipleSuccessorsError(newer)
0884856a4143 stack: handle basic case of splitting with crash
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 2922
diff changeset
    96
        return splitheads[0]
1982
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    97
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    98
    return repo[newer[0][0]].rev()
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    99
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
   100
class MultipleSuccessorsError(RuntimeError):
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
   101
    """Exception raised by _singlesuccessor when multiple successor sets exists
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
   102
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
   103
    The object contains the list of successorssets in its 'successorssets'
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
   104
    attribute to call to easily recover.
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
   105
    """
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
   106
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
   107
    def __init__(self, successorssets):
d87fc4f749e6 evolve: extract the code copied from evolve in a submodule
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
   108
        self.successorssets = successorssets