mercurial/setdiscovery.py
author Martin von Zweigbergk <martinvonz@google.com>
Fri, 20 Dec 2019 14:03:12 -0800
changeset 44360 2bd3b95fdce0
parent 43506 9f70512ae2cf
child 45942 89a2afe31e82
permissions -rw-r--r--
copy: rewrite walkpat() to depend less on dirstate I want to add a `hg cp/mv -r <rev>` option to mark files as copied/moved in an existing commit (amending that commit). The code needs to not depend on the dirstate for that. Differential Revision: https://phab.mercurial-scm.org/D8031
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
     1
# setdiscovery.py - improved discovery of common nodeset for mercurial
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
     2
#
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
     3
# Copyright 2010 Benoit Boissinot <bboissin@gmail.com>
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
     4
# and Peter Arrenbrecht <peter@arrenbrecht.ch>
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
     5
#
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
     6
# This software may be used and distributed according to the terms of the
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
     7
# GNU General Public License version 2 or any later version.
20656
cdecbc5ab504 setdiscovery: document algorithms used
Olle Lundberg <geek@nerd.sh>
parents: 20034
diff changeset
     8
"""
cdecbc5ab504 setdiscovery: document algorithms used
Olle Lundberg <geek@nerd.sh>
parents: 20034
diff changeset
     9
Algorithm works in the following way. You have two repository: local and
cdecbc5ab504 setdiscovery: document algorithms used
Olle Lundberg <geek@nerd.sh>
parents: 20034
diff changeset
    10
remote. They both contains a DAG of changelists.
cdecbc5ab504 setdiscovery: document algorithms used
Olle Lundberg <geek@nerd.sh>
parents: 20034
diff changeset
    11
cdecbc5ab504 setdiscovery: document algorithms used
Olle Lundberg <geek@nerd.sh>
parents: 20034
diff changeset
    12
The goal of the discovery protocol is to find one set of node *common*,
cdecbc5ab504 setdiscovery: document algorithms used
Olle Lundberg <geek@nerd.sh>
parents: 20034
diff changeset
    13
the set of nodes shared by local and remote.
cdecbc5ab504 setdiscovery: document algorithms used
Olle Lundberg <geek@nerd.sh>
parents: 20034
diff changeset
    14
cdecbc5ab504 setdiscovery: document algorithms used
Olle Lundberg <geek@nerd.sh>
parents: 20034
diff changeset
    15
One of the issue with the original protocol was latency, it could
cdecbc5ab504 setdiscovery: document algorithms used
Olle Lundberg <geek@nerd.sh>
parents: 20034
diff changeset
    16
potentially require lots of roundtrips to discover that the local repo was a
cdecbc5ab504 setdiscovery: document algorithms used
Olle Lundberg <geek@nerd.sh>
parents: 20034
diff changeset
    17
subset of remote (which is a very common case, you usually have few changes
cdecbc5ab504 setdiscovery: document algorithms used
Olle Lundberg <geek@nerd.sh>
parents: 20034
diff changeset
    18
compared to upstream, while upstream probably had lots of development).
cdecbc5ab504 setdiscovery: document algorithms used
Olle Lundberg <geek@nerd.sh>
parents: 20034
diff changeset
    19
cdecbc5ab504 setdiscovery: document algorithms used
Olle Lundberg <geek@nerd.sh>
parents: 20034
diff changeset
    20
The new protocol only requires one interface for the remote repo: `known()`,
cdecbc5ab504 setdiscovery: document algorithms used
Olle Lundberg <geek@nerd.sh>
parents: 20034
diff changeset
    21
which given a set of changelists tells you if they are present in the DAG.
cdecbc5ab504 setdiscovery: document algorithms used
Olle Lundberg <geek@nerd.sh>
parents: 20034
diff changeset
    22
cdecbc5ab504 setdiscovery: document algorithms used
Olle Lundberg <geek@nerd.sh>
parents: 20034
diff changeset
    23
The algorithm then works as follow:
cdecbc5ab504 setdiscovery: document algorithms used
Olle Lundberg <geek@nerd.sh>
parents: 20034
diff changeset
    24
cdecbc5ab504 setdiscovery: document algorithms used
Olle Lundberg <geek@nerd.sh>
parents: 20034
diff changeset
    25
 - We will be using three sets, `common`, `missing`, `unknown`. Originally
cdecbc5ab504 setdiscovery: document algorithms used
Olle Lundberg <geek@nerd.sh>
parents: 20034
diff changeset
    26
 all nodes are in `unknown`.
cdecbc5ab504 setdiscovery: document algorithms used
Olle Lundberg <geek@nerd.sh>
parents: 20034
diff changeset
    27
 - Take a sample from `unknown`, call `remote.known(sample)`
cdecbc5ab504 setdiscovery: document algorithms used
Olle Lundberg <geek@nerd.sh>
parents: 20034
diff changeset
    28
   - For each node that remote knows, move it and all its ancestors to `common`
cdecbc5ab504 setdiscovery: document algorithms used
Olle Lundberg <geek@nerd.sh>
parents: 20034
diff changeset
    29
   - For each node that remote doesn't know, move it and all its descendants
cdecbc5ab504 setdiscovery: document algorithms used
Olle Lundberg <geek@nerd.sh>
parents: 20034
diff changeset
    30
   to `missing`
cdecbc5ab504 setdiscovery: document algorithms used
Olle Lundberg <geek@nerd.sh>
parents: 20034
diff changeset
    31
 - Iterate until `unknown` is empty
cdecbc5ab504 setdiscovery: document algorithms used
Olle Lundberg <geek@nerd.sh>
parents: 20034
diff changeset
    32
cdecbc5ab504 setdiscovery: document algorithms used
Olle Lundberg <geek@nerd.sh>
parents: 20034
diff changeset
    33
There are a couple optimizations, first is instead of starting with a random
cdecbc5ab504 setdiscovery: document algorithms used
Olle Lundberg <geek@nerd.sh>
parents: 20034
diff changeset
    34
sample of missing, start by sending all heads, in the case where the local
cdecbc5ab504 setdiscovery: document algorithms used
Olle Lundberg <geek@nerd.sh>
parents: 20034
diff changeset
    35
repo is a subset, you computed the answer in one round trip.
cdecbc5ab504 setdiscovery: document algorithms used
Olle Lundberg <geek@nerd.sh>
parents: 20034
diff changeset
    36
cdecbc5ab504 setdiscovery: document algorithms used
Olle Lundberg <geek@nerd.sh>
parents: 20034
diff changeset
    37
Then you can do something similar to the bisecting strategy used when
cdecbc5ab504 setdiscovery: document algorithms used
Olle Lundberg <geek@nerd.sh>
parents: 20034
diff changeset
    38
finding faulty changesets. Instead of random samples, you can try picking
cdecbc5ab504 setdiscovery: document algorithms used
Olle Lundberg <geek@nerd.sh>
parents: 20034
diff changeset
    39
nodes that will maximize the number of nodes that will be
cdecbc5ab504 setdiscovery: document algorithms used
Olle Lundberg <geek@nerd.sh>
parents: 20034
diff changeset
    40
classified with it (since all ancestors or descendants will be marked as well).
cdecbc5ab504 setdiscovery: document algorithms used
Olle Lundberg <geek@nerd.sh>
parents: 20034
diff changeset
    41
"""
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
    42
25973
fb5664eb8414 setdiscovery: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25914
diff changeset
    43
from __future__ import absolute_import
fb5664eb8414 setdiscovery: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25914
diff changeset
    44
25113
0ca8410ea345 util: drop alias for collections.deque
Martin von Zweigbergk <martinvonz@google.com>
parents: 23817
diff changeset
    45
import collections
20034
1e5b38a919dd cleanup: move stdlib imports to their own import statement
Augie Fackler <raf@durin42.com>
parents: 17426
diff changeset
    46
import random
25973
fb5664eb8414 setdiscovery: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25914
diff changeset
    47
fb5664eb8414 setdiscovery: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25914
diff changeset
    48
from .i18n import _
fb5664eb8414 setdiscovery: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25914
diff changeset
    49
from .node import (
fb5664eb8414 setdiscovery: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25914
diff changeset
    50
    nullid,
fb5664eb8414 setdiscovery: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25914
diff changeset
    51
    nullrev,
fb5664eb8414 setdiscovery: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25914
diff changeset
    52
)
fb5664eb8414 setdiscovery: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25914
diff changeset
    53
from . import (
26587
56b2bcea2529 error: get Abort from 'error' instead of 'util'
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25973
diff changeset
    54
    error,
42745
4d20b1fe8a72 rust-discovery: using from Python code
Georges Racinet <georges.racinet@octobus.net>
parents: 42742
diff changeset
    55
    policy,
32712
43bda143e3b2 discovery: include timing in the debug output
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32291
diff changeset
    56
    util,
25973
fb5664eb8414 setdiscovery: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25914
diff changeset
    57
)
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
    58
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42884
diff changeset
    59
39174
71d83b315778 setdiscovery: don't use dagutil for parent resolution
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39173
diff changeset
    60
def _updatesample(revs, heads, sample, parentfn, quicksamplesize=0):
23809
9ca2eb881b53 setdiscovery: document the '_updatesample' function
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 23808
diff changeset
    61
    """update an existing sample to match the expected size
9ca2eb881b53 setdiscovery: document the '_updatesample' function
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 23808
diff changeset
    62
39168
2d218db7389b setdiscovery: reflect use of revs instead of nodes
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39166
diff changeset
    63
    The sample is updated with revs exponentially distant from each head of the
2d218db7389b setdiscovery: reflect use of revs instead of nodes
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39166
diff changeset
    64
    <revs> set. (H~1, H~2, H~4, H~8, etc).
23809
9ca2eb881b53 setdiscovery: document the '_updatesample' function
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 23808
diff changeset
    65
9ca2eb881b53 setdiscovery: document the '_updatesample' function
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 23808
diff changeset
    66
    If a target size is specified, the sampling will stop once this size is
39168
2d218db7389b setdiscovery: reflect use of revs instead of nodes
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39166
diff changeset
    67
    reached. Otherwise sampling will happen until roots of the <revs> set are
23809
9ca2eb881b53 setdiscovery: document the '_updatesample' function
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 23808
diff changeset
    68
    reached.
9ca2eb881b53 setdiscovery: document the '_updatesample' function
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 23808
diff changeset
    69
39168
2d218db7389b setdiscovery: reflect use of revs instead of nodes
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39166
diff changeset
    70
    :revs:  set of revs we want to discover (if None, assume the whole dag)
39170
754f389b87f2 setdiscovery: pass heads into _updatesample()
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39169
diff changeset
    71
    :heads: set of DAG head revs
23809
9ca2eb881b53 setdiscovery: document the '_updatesample' function
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 23808
diff changeset
    72
    :sample: a sample to update
39174
71d83b315778 setdiscovery: don't use dagutil for parent resolution
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39173
diff changeset
    73
    :parentfn: a callable to resolve parents for a revision
23809
9ca2eb881b53 setdiscovery: document the '_updatesample' function
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 23808
diff changeset
    74
    :quicksamplesize: optional target size of the sample"""
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
    75
    dist = {}
25113
0ca8410ea345 util: drop alias for collections.deque
Martin von Zweigbergk <martinvonz@google.com>
parents: 23817
diff changeset
    76
    visit = collections.deque(heads)
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
    77
    seen = set()
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
    78
    factor = 1
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
    79
    while visit:
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
    80
        curr = visit.popleft()
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
    81
        if curr in seen:
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
    82
            continue
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
    83
        d = dist.setdefault(curr, 1)
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
    84
        if d > factor:
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
    85
            factor *= 2
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
    86
        if d == factor:
23814
6a5877a73141 setdiscovery: drop the 'always' argument to '_updatesample'
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 23813
diff changeset
    87
            sample.add(curr)
6a5877a73141 setdiscovery: drop the 'always' argument to '_updatesample'
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 23813
diff changeset
    88
            if quicksamplesize and (len(sample) >= quicksamplesize):
6a5877a73141 setdiscovery: drop the 'always' argument to '_updatesample'
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 23813
diff changeset
    89
                return
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
    90
        seen.add(curr)
39174
71d83b315778 setdiscovery: don't use dagutil for parent resolution
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39173
diff changeset
    91
71d83b315778 setdiscovery: don't use dagutil for parent resolution
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39173
diff changeset
    92
        for p in parentfn(curr):
71d83b315778 setdiscovery: don't use dagutil for parent resolution
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39173
diff changeset
    93
            if p != nullrev and (not revs or p in revs):
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
    94
                dist.setdefault(p, d + 1)
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
    95
                visit.append(p)
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
    96
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42884
diff changeset
    97
42741
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests
Georges Racinet <georges.racinet@octobus.net>
parents: 42425
diff changeset
    98
def _limitsample(sample, desiredlen, randomize=True):
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests
Georges Racinet <georges.racinet@octobus.net>
parents: 42425
diff changeset
    99
    """return a random subset of sample of at most desiredlen item.
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests
Georges Racinet <georges.racinet@octobus.net>
parents: 42425
diff changeset
   100
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests
Georges Racinet <georges.racinet@octobus.net>
parents: 42425
diff changeset
   101
    If randomize is False, though, a deterministic subset is returned.
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests
Georges Racinet <georges.racinet@octobus.net>
parents: 42425
diff changeset
   102
    This is meant for integration tests.
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests
Georges Racinet <georges.racinet@octobus.net>
parents: 42425
diff changeset
   103
    """
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests
Georges Racinet <georges.racinet@octobus.net>
parents: 42425
diff changeset
   104
    if len(sample) <= desiredlen:
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests
Georges Racinet <georges.racinet@octobus.net>
parents: 42425
diff changeset
   105
        return sample
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests
Georges Racinet <georges.racinet@octobus.net>
parents: 42425
diff changeset
   106
    if randomize:
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests
Georges Racinet <georges.racinet@octobus.net>
parents: 42425
diff changeset
   107
        return set(random.sample(sample, desiredlen))
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests
Georges Racinet <georges.racinet@octobus.net>
parents: 42425
diff changeset
   108
    sample = list(sample)
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests
Georges Racinet <georges.racinet@octobus.net>
parents: 42425
diff changeset
   109
    sample.sort()
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests
Georges Racinet <georges.racinet@octobus.net>
parents: 42425
diff changeset
   110
    return set(sample[:desiredlen])
23083
ee45f5c2ffcc setdiscovery: extract sample limitation in a `_limitsample` function
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 20656
diff changeset
   111
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42884
diff changeset
   112
41112
3023bc4b3da0 discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41111
diff changeset
   113
class partialdiscovery(object):
3023bc4b3da0 discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41111
diff changeset
   114
    """an object representing ongoing discovery
3023bc4b3da0 discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41111
diff changeset
   115
3023bc4b3da0 discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41111
diff changeset
   116
    Feed with data from the remote repository, this object keep track of the
3023bc4b3da0 discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41111
diff changeset
   117
    current set of changeset in various states:
3023bc4b3da0 discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41111
diff changeset
   118
41172
3dcc96582627 discovery: improve partial discovery documentation
Boris Feld <boris.feld@octobus.net>
parents: 41171
diff changeset
   119
    - common:    revs also known remotely
3dcc96582627 discovery: improve partial discovery documentation
Boris Feld <boris.feld@octobus.net>
parents: 41171
diff changeset
   120
    - undecided: revs we don't have information on yet
3dcc96582627 discovery: improve partial discovery documentation
Boris Feld <boris.feld@octobus.net>
parents: 41171
diff changeset
   121
    - missing:   revs missing remotely
3dcc96582627 discovery: improve partial discovery documentation
Boris Feld <boris.feld@octobus.net>
parents: 41171
diff changeset
   122
    (all tracked revisions are known locally)
41112
3023bc4b3da0 discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41111
diff changeset
   123
    """
3023bc4b3da0 discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41111
diff changeset
   124
42741
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests
Georges Racinet <georges.racinet@octobus.net>
parents: 42425
diff changeset
   125
    def __init__(self, repo, targetheads, respectsize, randomize=True):
41112
3023bc4b3da0 discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41111
diff changeset
   126
        self._repo = repo
41167
870a89c6909d discovery: move undecided set on the partialdiscovery
Boris Feld <boris.feld@octobus.net>
parents: 41162
diff changeset
   127
        self._targetheads = targetheads
41112
3023bc4b3da0 discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41111
diff changeset
   128
        self._common = repo.changelog.incrementalmissingrevs()
41167
870a89c6909d discovery: move undecided set on the partialdiscovery
Boris Feld <boris.feld@octobus.net>
parents: 41162
diff changeset
   129
        self._undecided = None
41170
96201120cdf5 discovery: move missing tracking inside the partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41169
diff changeset
   130
        self.missing = set()
41885
5baf06d2bb41 discovery: cache the children mapping used during each discovery
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41884
diff changeset
   131
        self._childrenmap = None
42402
5b34972a0094 setdiscovery: make progress on most connected groups each roundtrip
Martin von Zweigbergk <martinvonz@google.com>
parents: 42354
diff changeset
   132
        self._respectsize = respectsize
42741
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests
Georges Racinet <georges.racinet@octobus.net>
parents: 42425
diff changeset
   133
        self.randomize = randomize
41112
3023bc4b3da0 discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41111
diff changeset
   134
3023bc4b3da0 discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41111
diff changeset
   135
    def addcommons(self, commons):
42170
6631f3e89b6f setdiscovery: fix a few typos
Joerg Sonnenberger <joerg@bec.de>
parents: 42159
diff changeset
   136
        """register nodes known as common"""
41112
3023bc4b3da0 discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41111
diff changeset
   137
        self._common.addbases(commons)
41304
76873548b051 partialdiscovery: avoid `undecided` related computation sooner than necessary
Boris Feld <boris.feld@octobus.net>
parents: 41280
diff changeset
   138
        if self._undecided is not None:
76873548b051 partialdiscovery: avoid `undecided` related computation sooner than necessary
Boris Feld <boris.feld@octobus.net>
parents: 41280
diff changeset
   139
            self._common.removeancestorsfrom(self._undecided)
41112
3023bc4b3da0 discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41111
diff changeset
   140
41170
96201120cdf5 discovery: move missing tracking inside the partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41169
diff changeset
   141
    def addmissings(self, missings):
42170
6631f3e89b6f setdiscovery: fix a few typos
Joerg Sonnenberger <joerg@bec.de>
parents: 42159
diff changeset
   142
        """register some nodes as missing"""
43077
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
   143
        newmissing = self._repo.revs(b'%ld::%ld', missings, self.undecided)
41280
f4277a35c42c discovery: compute newly discovered missing in a more efficient way
Boris Feld <boris.feld@octobus.net>
parents: 41245
diff changeset
   144
        if newmissing:
f4277a35c42c discovery: compute newly discovered missing in a more efficient way
Boris Feld <boris.feld@octobus.net>
parents: 41245
diff changeset
   145
            self.missing.update(newmissing)
f4277a35c42c discovery: compute newly discovered missing in a more efficient way
Boris Feld <boris.feld@octobus.net>
parents: 41245
diff changeset
   146
            self.undecided.difference_update(newmissing)
41170
96201120cdf5 discovery: move missing tracking inside the partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41169
diff changeset
   147
41171
f46ffd23dae8 discovery: add a simple `addinfo` method
Boris Feld <boris.feld@octobus.net>
parents: 41170
diff changeset
   148
    def addinfo(self, sample):
f46ffd23dae8 discovery: add a simple `addinfo` method
Boris Feld <boris.feld@octobus.net>
parents: 41170
diff changeset
   149
        """consume an iterable of (rev, known) tuples"""
f46ffd23dae8 discovery: add a simple `addinfo` method
Boris Feld <boris.feld@octobus.net>
parents: 41170
diff changeset
   150
        common = set()
f46ffd23dae8 discovery: add a simple `addinfo` method
Boris Feld <boris.feld@octobus.net>
parents: 41170
diff changeset
   151
        missing = set()
f46ffd23dae8 discovery: add a simple `addinfo` method
Boris Feld <boris.feld@octobus.net>
parents: 41170
diff changeset
   152
        for rev, known in sample:
f46ffd23dae8 discovery: add a simple `addinfo` method
Boris Feld <boris.feld@octobus.net>
parents: 41170
diff changeset
   153
            if known:
f46ffd23dae8 discovery: add a simple `addinfo` method
Boris Feld <boris.feld@octobus.net>
parents: 41170
diff changeset
   154
                common.add(rev)
f46ffd23dae8 discovery: add a simple `addinfo` method
Boris Feld <boris.feld@octobus.net>
parents: 41170
diff changeset
   155
            else:
f46ffd23dae8 discovery: add a simple `addinfo` method
Boris Feld <boris.feld@octobus.net>
parents: 41170
diff changeset
   156
                missing.add(rev)
f46ffd23dae8 discovery: add a simple `addinfo` method
Boris Feld <boris.feld@octobus.net>
parents: 41170
diff changeset
   157
        if common:
f46ffd23dae8 discovery: add a simple `addinfo` method
Boris Feld <boris.feld@octobus.net>
parents: 41170
diff changeset
   158
            self.addcommons(common)
f46ffd23dae8 discovery: add a simple `addinfo` method
Boris Feld <boris.feld@octobus.net>
parents: 41170
diff changeset
   159
        if missing:
f46ffd23dae8 discovery: add a simple `addinfo` method
Boris Feld <boris.feld@octobus.net>
parents: 41170
diff changeset
   160
            self.addmissings(missing)
f46ffd23dae8 discovery: add a simple `addinfo` method
Boris Feld <boris.feld@octobus.net>
parents: 41170
diff changeset
   161
41112
3023bc4b3da0 discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41111
diff changeset
   162
    def hasinfo(self):
3023bc4b3da0 discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41111
diff changeset
   163
        """return True is we have any clue about the remote state"""
3023bc4b3da0 discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41111
diff changeset
   164
        return self._common.hasbases()
3023bc4b3da0 discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41111
diff changeset
   165
41169
3ce5b96482c6 discovery: add a `iscomplete` method to the `partialdiscovery` object
Boris Feld <boris.feld@octobus.net>
parents: 41168
diff changeset
   166
    def iscomplete(self):
3ce5b96482c6 discovery: add a `iscomplete` method to the `partialdiscovery` object
Boris Feld <boris.feld@octobus.net>
parents: 41168
diff changeset
   167
        """True if all the necessary data have been gathered"""
3ce5b96482c6 discovery: add a `iscomplete` method to the `partialdiscovery` object
Boris Feld <boris.feld@octobus.net>
parents: 41168
diff changeset
   168
        return self._undecided is not None and not self._undecided
3ce5b96482c6 discovery: add a `iscomplete` method to the `partialdiscovery` object
Boris Feld <boris.feld@octobus.net>
parents: 41168
diff changeset
   169
41167
870a89c6909d discovery: move undecided set on the partialdiscovery
Boris Feld <boris.feld@octobus.net>
parents: 41162
diff changeset
   170
    @property
870a89c6909d discovery: move undecided set on the partialdiscovery
Boris Feld <boris.feld@octobus.net>
parents: 41162
diff changeset
   171
    def undecided(self):
870a89c6909d discovery: move undecided set on the partialdiscovery
Boris Feld <boris.feld@octobus.net>
parents: 41162
diff changeset
   172
        if self._undecided is not None:
870a89c6909d discovery: move undecided set on the partialdiscovery
Boris Feld <boris.feld@octobus.net>
parents: 41162
diff changeset
   173
            return self._undecided
870a89c6909d discovery: move undecided set on the partialdiscovery
Boris Feld <boris.feld@octobus.net>
parents: 41162
diff changeset
   174
        self._undecided = set(self._common.missingancestors(self._targetheads))
870a89c6909d discovery: move undecided set on the partialdiscovery
Boris Feld <boris.feld@octobus.net>
parents: 41162
diff changeset
   175
        return self._undecided
870a89c6909d discovery: move undecided set on the partialdiscovery
Boris Feld <boris.feld@octobus.net>
parents: 41162
diff changeset
   176
42103
362726923ba3 discovery: stop direct use of attribute of partialdiscovery
Georges Racinet <georges.racinet@octobus.net>
parents: 41979
diff changeset
   177
    def stats(self):
362726923ba3 discovery: stop direct use of attribute of partialdiscovery
Georges Racinet <georges.racinet@octobus.net>
parents: 41979
diff changeset
   178
        return {
43162
3c6976b1f693 py3-discovery: using plain str in stats dict
Georges Racinet <georges.racinet@octobus.net>
parents: 43077
diff changeset
   179
            'undecided': len(self.undecided),
42103
362726923ba3 discovery: stop direct use of attribute of partialdiscovery
Georges Racinet <georges.racinet@octobus.net>
parents: 41979
diff changeset
   180
        }
362726923ba3 discovery: stop direct use of attribute of partialdiscovery
Georges Racinet <georges.racinet@octobus.net>
parents: 41979
diff changeset
   181
41113
9815d3337f9b discovery: move common heads computation inside partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41112
diff changeset
   182
    def commonheads(self):
9815d3337f9b discovery: move common heads computation inside partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41112
diff changeset
   183
        """the heads of the known common set"""
9815d3337f9b discovery: move common heads computation inside partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41112
diff changeset
   184
        # heads(common) == heads(common.bases) since common represents
9815d3337f9b discovery: move common heads computation inside partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41112
diff changeset
   185
        # common.bases and all its ancestors
41245
2a8782cc2e16 discovery: using the new basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents: 41172
diff changeset
   186
        return self._common.basesheads()
41112
3023bc4b3da0 discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41111
diff changeset
   187
41881
e514799e4e07 discovery: use a lower level but faster way to retrieve parents
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41880
diff changeset
   188
    def _parentsgetter(self):
e514799e4e07 discovery: use a lower level but faster way to retrieve parents
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41880
diff changeset
   189
        getrev = self._repo.changelog.index.__getitem__
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42884
diff changeset
   190
41881
e514799e4e07 discovery: use a lower level but faster way to retrieve parents
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41880
diff changeset
   191
        def getparents(r):
41979
0d467e4de4ae discovery: fix embarrassing typo in slice definition
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41889
diff changeset
   192
            return getrev(r)[5:7]
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42884
diff changeset
   193
41881
e514799e4e07 discovery: use a lower level but faster way to retrieve parents
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41880
diff changeset
   194
        return getparents
e514799e4e07 discovery: use a lower level but faster way to retrieve parents
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41880
diff changeset
   195
41886
a05f0bbefdd9 discovery: explicitly use `undecided` for the children mapping
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41885
diff changeset
   196
    def _childrengetter(self):
41884
d5e6ae6e8012 discovery: move children computation in its own method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41883
diff changeset
   197
41885
5baf06d2bb41 discovery: cache the children mapping used during each discovery
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41884
diff changeset
   198
        if self._childrenmap is not None:
41889
3ba9ca537f57 discovery: clarify why the caching of children is valid
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41886
diff changeset
   199
            # During discovery, the `undecided` set keep shrinking.
3ba9ca537f57 discovery: clarify why the caching of children is valid
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41886
diff changeset
   200
            # Therefore, the map computed for an iteration N will be
3ba9ca537f57 discovery: clarify why the caching of children is valid
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41886
diff changeset
   201
            # valid for iteration N+1. Instead of computing the same
3ba9ca537f57 discovery: clarify why the caching of children is valid
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41886
diff changeset
   202
            # data over and over we cached it the first time.
41885
5baf06d2bb41 discovery: cache the children mapping used during each discovery
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41884
diff changeset
   203
            return self._childrenmap.__getitem__
5baf06d2bb41 discovery: cache the children mapping used during each discovery
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41884
diff changeset
   204
41884
d5e6ae6e8012 discovery: move children computation in its own method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41883
diff changeset
   205
        # _updatesample() essentially does interaction over revisions to look
d5e6ae6e8012 discovery: move children computation in its own method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41883
diff changeset
   206
        # up their children. This lookup is expensive and doing it in a loop is
d5e6ae6e8012 discovery: move children computation in its own method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41883
diff changeset
   207
        # quadratic. We precompute the children for all relevant revisions and
d5e6ae6e8012 discovery: move children computation in its own method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41883
diff changeset
   208
        # make the lookup in _updatesample() a simple dict lookup.
41885
5baf06d2bb41 discovery: cache the children mapping used during each discovery
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41884
diff changeset
   209
        self._childrenmap = children = {}
41884
d5e6ae6e8012 discovery: move children computation in its own method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41883
diff changeset
   210
d5e6ae6e8012 discovery: move children computation in its own method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41883
diff changeset
   211
        parentrevs = self._parentsgetter()
41886
a05f0bbefdd9 discovery: explicitly use `undecided` for the children mapping
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41885
diff changeset
   212
        revs = self.undecided
41884
d5e6ae6e8012 discovery: move children computation in its own method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41883
diff changeset
   213
d5e6ae6e8012 discovery: move children computation in its own method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41883
diff changeset
   214
        for rev in sorted(revs):
d5e6ae6e8012 discovery: move children computation in its own method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41883
diff changeset
   215
            # Always ensure revision has an entry so we don't need to worry
d5e6ae6e8012 discovery: move children computation in its own method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41883
diff changeset
   216
            # about missing keys.
d5e6ae6e8012 discovery: move children computation in its own method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41883
diff changeset
   217
            children[rev] = []
d5e6ae6e8012 discovery: move children computation in its own method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41883
diff changeset
   218
            for prev in parentrevs(rev):
d5e6ae6e8012 discovery: move children computation in its own method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41883
diff changeset
   219
                if prev == nullrev:
d5e6ae6e8012 discovery: move children computation in its own method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41883
diff changeset
   220
                    continue
d5e6ae6e8012 discovery: move children computation in its own method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41883
diff changeset
   221
                c = children.get(prev)
d5e6ae6e8012 discovery: move children computation in its own method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41883
diff changeset
   222
                if c is not None:
d5e6ae6e8012 discovery: move children computation in its own method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41883
diff changeset
   223
                    c.append(rev)
d5e6ae6e8012 discovery: move children computation in its own method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41883
diff changeset
   224
        return children.__getitem__
d5e6ae6e8012 discovery: move children computation in its own method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41883
diff changeset
   225
41879
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
   226
    def takequicksample(self, headrevs, size):
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
   227
        """takes a quick sample of size <size>
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
   228
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
   229
        It is meant for initial sampling and focuses on querying heads and close
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
   230
        ancestors of heads.
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
   231
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
   232
        :headrevs: set of head revisions in local DAG to consider
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
   233
        :size: the maximum size of the sample"""
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
   234
        revs = self.undecided
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
   235
        if len(revs) <= size:
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
   236
            return list(revs)
43077
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
   237
        sample = set(self._repo.revs(b'heads(%ld)', revs))
41879
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
   238
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
   239
        if len(sample) >= size:
42741
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests
Georges Racinet <georges.racinet@octobus.net>
parents: 42425
diff changeset
   240
            return _limitsample(sample, size, randomize=self.randomize)
41879
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
   241
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42884
diff changeset
   242
        _updatesample(
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42884
diff changeset
   243
            None, headrevs, sample, self._parentsgetter(), quicksamplesize=size
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42884
diff changeset
   244
        )
41879
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
   245
        return sample
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
   246
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
   247
    def takefullsample(self, headrevs, size):
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
   248
        revs = self.undecided
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
   249
        if len(revs) <= size:
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
   250
            return list(revs)
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
   251
        repo = self._repo
43077
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
   252
        sample = set(repo.revs(b'heads(%ld)', revs))
41881
e514799e4e07 discovery: use a lower level but faster way to retrieve parents
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41880
diff changeset
   253
        parentrevs = self._parentsgetter()
41879
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
   254
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
   255
        # update from heads
41880
55919b96c02a discovery: avoid computing identical sets of heads twice
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41879
diff changeset
   256
        revsheads = sample.copy()
41881
e514799e4e07 discovery: use a lower level but faster way to retrieve parents
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41880
diff changeset
   257
        _updatesample(revs, revsheads, sample, parentrevs)
41879
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
   258
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
   259
        # update from roots
43077
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
   260
        revsroots = set(repo.revs(b'roots(%ld)', revs))
41886
a05f0bbefdd9 discovery: explicitly use `undecided` for the children mapping
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41885
diff changeset
   261
        childrenrevs = self._childrengetter()
41884
d5e6ae6e8012 discovery: move children computation in its own method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 41883
diff changeset
   262
        _updatesample(revs, revsroots, sample, childrenrevs)
41879
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
   263
        assert sample
42425
b9ff059fd194 discovery: be more conservative when adjusting the sample size
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42402
diff changeset
   264
b9ff059fd194 discovery: be more conservative when adjusting the sample size
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42402
diff changeset
   265
        if not self._respectsize:
b9ff059fd194 discovery: be more conservative when adjusting the sample size
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42402
diff changeset
   266
            size = max(size, min(len(revsroots), len(revsheads)))
b9ff059fd194 discovery: be more conservative when adjusting the sample size
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42402
diff changeset
   267
42741
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests
Georges Racinet <georges.racinet@octobus.net>
parents: 42425
diff changeset
   268
        sample = _limitsample(sample, size, randomize=self.randomize)
41879
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
   269
        if len(sample) < size:
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
   270
            more = size - len(sample)
42741
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests
Georges Racinet <georges.racinet@octobus.net>
parents: 42425
diff changeset
   271
            takefrom = list(revs - sample)
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests
Georges Racinet <georges.racinet@octobus.net>
parents: 42425
diff changeset
   272
            if self.randomize:
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests
Georges Racinet <georges.racinet@octobus.net>
parents: 42425
diff changeset
   273
                sample.update(random.sample(takefrom, more))
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests
Georges Racinet <georges.racinet@octobus.net>
parents: 42425
diff changeset
   274
            else:
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests
Georges Racinet <georges.racinet@octobus.net>
parents: 42425
diff changeset
   275
                takefrom.sort()
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests
Georges Racinet <georges.racinet@octobus.net>
parents: 42425
diff changeset
   276
                sample.update(takefrom[:more])
41879
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
   277
        return sample
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
   278
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42884
diff changeset
   279
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42884
diff changeset
   280
partialdiscovery = policy.importrust(
43506
9f70512ae2cf cleanup: remove pointless r-prefixes on single-quoted strings
Augie Fackler <augie@google.com>
parents: 43162
diff changeset
   281
    'discovery', member='PartialDiscovery', default=partialdiscovery
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42884
diff changeset
   282
)
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42884
diff changeset
   283
42745
4d20b1fe8a72 rust-discovery: using from Python code
Georges Racinet <georges.racinet@octobus.net>
parents: 42742
diff changeset
   284
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42884
diff changeset
   285
def findcommonheads(
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42884
diff changeset
   286
    ui,
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42884
diff changeset
   287
    local,
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42884
diff changeset
   288
    remote,
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42884
diff changeset
   289
    initialsamplesize=100,
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42884
diff changeset
   290
    fullsamplesize=200,
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42884
diff changeset
   291
    abortwhenunrelated=True,
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42884
diff changeset
   292
    ancestorsof=None,
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42884
diff changeset
   293
    samplegrowth=1.05,
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42884
diff changeset
   294
):
14206
2bf60f158ecb setdiscovery: limit lines to 80 characters
Steven Brown <StevenGBrown@gmail.com>
parents: 14164
diff changeset
   295
    '''Return a tuple (common, anyincoming, remoteheads) used to identify
2bf60f158ecb setdiscovery: limit lines to 80 characters
Steven Brown <StevenGBrown@gmail.com>
parents: 14164
diff changeset
   296
    missing nodes from or in remote.
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
   297
    '''
32712
43bda143e3b2 discovery: include timing in the debug output
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32291
diff changeset
   298
    start = util.timer()
43bda143e3b2 discovery: include timing in the debug output
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32291
diff changeset
   299
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
   300
    roundtrips = 0
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
   301
    cl = local.changelog
39159
5b32b3c618b2 setdiscovery: don't use dagutil for rev -> node conversions
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38373
diff changeset
   302
    clnode = cl.node
39161
858a12846f4f setdiscovery: don't use dagutil for node -> rev conversion
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39159
diff changeset
   303
    clrev = cl.rev
39159
5b32b3c618b2 setdiscovery: don't use dagutil for rev -> node conversions
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38373
diff changeset
   304
35304
f77121b6bf1b setdiscover: allow to ignore part of the local graph
Boris Feld <boris.feld@octobus.net>
parents: 32768
diff changeset
   305
    if ancestorsof is not None:
39165
860e83cd97de setdiscovery: don't use dagutil to compute heads
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39161
diff changeset
   306
        ownheads = [clrev(n) for n in ancestorsof]
860e83cd97de setdiscovery: don't use dagutil to compute heads
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39161
diff changeset
   307
    else:
860e83cd97de setdiscovery: don't use dagutil to compute heads
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39161
diff changeset
   308
        ownheads = [rev for rev in cl.headrevs() if rev != nullrev]
860e83cd97de setdiscovery: don't use dagutil to compute heads
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39161
diff changeset
   309
14624
f03c82d1f50a setdiscovery: batch heads and known(ownheads)
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 14206
diff changeset
   310
    # early exit if we know all the specified remote heads already
43077
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
   311
    ui.debug(b"query 1; heads\n")
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
   312
    roundtrips += 1
42159
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   313
    # We also ask remote about all the local heads. That set can be arbitrarily
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   314
    # large, so we used to limit it size to `initialsamplesize`. We no longer
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   315
    # do as it proved counter productive. The skipped heads could lead to a
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   316
    # large "undecided" set, slower to be clarified than if we asked the
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   317
    # question for all heads right away.
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   318
    #
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   319
    # We are already fetching all server heads using the `heads` commands,
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   320
    # sending a equivalent number of heads the other way should not have a
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   321
    # significant impact.  In addition, it is very likely that we are going to
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   322
    # have to issue "known" request for an equivalent amount of revisions in
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   323
    # order to decide if theses heads are common or missing.
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   324
    #
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   325
    # find a detailled analysis below.
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   326
    #
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   327
    # Case A: local and server both has few heads
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   328
    #
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   329
    #     Ownheads is below initialsamplesize, limit would not have any effect.
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   330
    #
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   331
    # Case B: local has few heads and server has many
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   332
    #
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   333
    #     Ownheads is below initialsamplesize, limit would not have any effect.
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   334
    #
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   335
    # Case C: local and server both has many heads
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   336
    #
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   337
    #     We now transfert some more data, but not significantly more than is
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   338
    #     already transfered to carry the server heads.
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   339
    #
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   340
    # Case D: local has many heads, server has few
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   341
    #
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   342
    #   D.1 local heads are mostly known remotely
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   343
    #
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   344
    #     All the known head will have be part of a `known` request at some
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   345
    #     point for the discovery to finish. Sending them all earlier is
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   346
    #     actually helping.
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   347
    #
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   348
    #     (This case is fairly unlikely, it requires the numerous heads to all
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   349
    #     be merged server side in only a few heads)
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   350
    #
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   351
    #   D.2 local heads are mostly missing remotely
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   352
    #
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   353
    #     To determine that the heads are missing, we'll have to issue `known`
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   354
    #     request for them or one of their ancestors. This amount of `known`
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   355
    #     request will likely be in the same order of magnitude than the amount
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   356
    #     of local heads.
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   357
    #
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   358
    #     The only case where we can be more efficient using `known` request on
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   359
    #     ancestors are case were all the "missing" local heads are based on a
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   360
    #     few changeset, also "missing".  This means we would have a "complex"
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   361
    #     graph (with many heads) attached to, but very independant to a the
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   362
    #     "simple" graph on the server. This is a fairly usual case and have
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   363
    #     not been met in the wild so far.
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   364
    if remote.limitedarguments:
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   365
        sample = _limitsample(ownheads, initialsamplesize)
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   366
        # indices between sample and externalized version must match
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   367
        sample = list(sample)
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   368
    else:
4f9a89837f07 setdiscovery: stop limiting the number of local head we initially send
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42103
diff changeset
   369
        sample = ownheads
37631
2f626233859b wireproto: implement batching on peer executor interface
Gregory Szorc <gregory.szorc@gmail.com>
parents: 37630
diff changeset
   370
2f626233859b wireproto: implement batching on peer executor interface
Gregory Szorc <gregory.szorc@gmail.com>
parents: 37630
diff changeset
   371
    with remote.commandexecutor() as e:
43077
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
   372
        fheads = e.callcommand(b'heads', {})
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
   373
        fknown = e.callcommand(
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
   374
            b'known', {b'nodes': [clnode(r) for r in sample],}
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
   375
        )
37631
2f626233859b wireproto: implement batching on peer executor interface
Gregory Szorc <gregory.szorc@gmail.com>
parents: 37630
diff changeset
   376
2f626233859b wireproto: implement batching on peer executor interface
Gregory Szorc <gregory.szorc@gmail.com>
parents: 37630
diff changeset
   377
    srvheadhashes, yesno = fheads.result(), fknown.result()
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
   378
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
   379
    if cl.tip() == nullid:
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
   380
        if srvheadhashes != [nullid]:
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
   381
            return [nullid], True, srvheadhashes
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
   382
        return [nullid], False, []
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
   383
14206
2bf60f158ecb setdiscovery: limit lines to 80 characters
Steven Brown <StevenGBrown@gmail.com>
parents: 14164
diff changeset
   384
    # start actual discovery (we note this before the next "if" for
2bf60f158ecb setdiscovery: limit lines to 80 characters
Steven Brown <StevenGBrown@gmail.com>
parents: 14164
diff changeset
   385
    # compatibility reasons)
43077
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
   386
    ui.status(_(b"searching for changes\n"))
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
   387
41878
82884bbf8d2b discovery: rename `srvheads` to `knownsrvheads`
Georges Racinet <georges.racinet@octobus.net>
parents: 41304
diff changeset
   388
    knownsrvheads = []  # revnos of remote heads that are known locally
39161
858a12846f4f setdiscovery: don't use dagutil for node -> rev conversion
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39159
diff changeset
   389
    for node in srvheadhashes:
858a12846f4f setdiscovery: don't use dagutil for node -> rev conversion
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39159
diff changeset
   390
        if node == nullid:
858a12846f4f setdiscovery: don't use dagutil for node -> rev conversion
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39159
diff changeset
   391
            continue
858a12846f4f setdiscovery: don't use dagutil for node -> rev conversion
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39159
diff changeset
   392
858a12846f4f setdiscovery: don't use dagutil for node -> rev conversion
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39159
diff changeset
   393
        try:
41878
82884bbf8d2b discovery: rename `srvheads` to `knownsrvheads`
Georges Racinet <georges.racinet@octobus.net>
parents: 41304
diff changeset
   394
            knownsrvheads.append(clrev(node))
39161
858a12846f4f setdiscovery: don't use dagutil for node -> rev conversion
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39159
diff changeset
   395
        # Catches unknown and filtered nodes.
858a12846f4f setdiscovery: don't use dagutil for node -> rev conversion
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39159
diff changeset
   396
        except error.LookupError:
858a12846f4f setdiscovery: don't use dagutil for node -> rev conversion
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39159
diff changeset
   397
            continue
858a12846f4f setdiscovery: don't use dagutil for node -> rev conversion
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39159
diff changeset
   398
41878
82884bbf8d2b discovery: rename `srvheads` to `knownsrvheads`
Georges Racinet <georges.racinet@octobus.net>
parents: 41304
diff changeset
   399
    if len(knownsrvheads) == len(srvheadhashes):
43077
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
   400
        ui.debug(b"all remote heads known locally\n")
39159
5b32b3c618b2 setdiscovery: don't use dagutil for rev -> node conversions
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38373
diff changeset
   401
        return srvheadhashes, False, srvheadhashes
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
   402
36716
bf485b70d0ae setdiscovery: remove initialsamplesize from a condition
Martin von Zweigbergk <martinvonz@google.com>
parents: 36715
diff changeset
   403
    if len(sample) == len(ownheads) and all(yesno):
43077
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
   404
        ui.note(_(b"all local changesets known remotely\n"))
39159
5b32b3c618b2 setdiscovery: don't use dagutil for rev -> node conversions
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38373
diff changeset
   405
        ownheadhashes = [clnode(r) for r in ownheads]
5b32b3c618b2 setdiscovery: don't use dagutil for rev -> node conversions
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38373
diff changeset
   406
        return ownheadhashes, True, srvheadhashes
14624
f03c82d1f50a setdiscovery: batch heads and known(ownheads)
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 14206
diff changeset
   407
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
   408
    # full blown discovery
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
   409
43077
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
   410
    randomize = ui.configbool(b'devel', b'discovery.randomize')
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42884
diff changeset
   411
    disco = partialdiscovery(
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42884
diff changeset
   412
        local, ownheads, remote.limitedarguments, randomize=randomize
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42884
diff changeset
   413
    )
23343
f8a2647fe020 setdiscovery: avoid a full changelog graph traversal
Siddharth Agarwal <sid0@fb.com>
parents: 23192
diff changeset
   414
    # treat remote heads (and maybe own heads) as a first implicit sample
f8a2647fe020 setdiscovery: avoid a full changelog graph traversal
Siddharth Agarwal <sid0@fb.com>
parents: 23192
diff changeset
   415
    # response
41878
82884bbf8d2b discovery: rename `srvheads` to `knownsrvheads`
Georges Racinet <georges.racinet@octobus.net>
parents: 41304
diff changeset
   416
    disco.addcommons(knownsrvheads)
41171
f46ffd23dae8 discovery: add a simple `addinfo` method
Boris Feld <boris.feld@octobus.net>
parents: 41170
diff changeset
   417
    disco.addinfo(zip(sample, yesno))
16683
525fdb738975 cleanup: eradicate long lines
Brodie Rao <brodie@sf.io>
parents: 15713
diff changeset
   418
14624
f03c82d1f50a setdiscovery: batch heads and known(ownheads)
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 14206
diff changeset
   419
    full = False
43077
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
   420
    progress = ui.makeprogress(_(b'searching'), unit=_(b'queries'))
41169
3ce5b96482c6 discovery: add a `iscomplete` method to the `partialdiscovery` object
Boris Feld <boris.feld@octobus.net>
parents: 41168
diff changeset
   421
    while not disco.iscomplete():
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
   422
41112
3023bc4b3da0 discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41111
diff changeset
   423
        if full or disco.hasinfo():
23747
f82173a90c2c setdiscovery: factorize similar sampling code
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 23746
diff changeset
   424
            if full:
43077
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
   425
                ui.note(_(b"sampling from both directions\n"))
23747
f82173a90c2c setdiscovery: factorize similar sampling code
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 23746
diff changeset
   426
            else:
43077
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
   427
                ui.debug(b"taking initial sample\n")
41879
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
   428
            samplefunc = disco.takefullsample
23130
ced632394371 setdiscovery: limit the size of all sample (issue4411)
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 23084
diff changeset
   429
            targetsize = fullsamplesize
42354
dbd0fcca6dfc discovery: slowly increase sampling size
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42170
diff changeset
   430
            if not remote.limitedarguments:
dbd0fcca6dfc discovery: slowly increase sampling size
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 42170
diff changeset
   431
                fullsamplesize = int(fullsamplesize * samplegrowth)
14624
f03c82d1f50a setdiscovery: batch heads and known(ownheads)
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 14206
diff changeset
   432
        else:
f03c82d1f50a setdiscovery: batch heads and known(ownheads)
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 14206
diff changeset
   433
            # use even cheaper initial sample
43077
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
   434
            ui.debug(b"taking quick initial sample\n")
41879
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
   435
            samplefunc = disco.takequicksample
23130
ced632394371 setdiscovery: limit the size of all sample (issue4411)
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 23084
diff changeset
   436
            targetsize = initialsamplesize
41879
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
   437
        sample = samplefunc(ownheads, targetsize)
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
   438
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
   439
        roundtrips += 1
38350
9e70690a21ac setdiscovery: use progress helper
Martin von Zweigbergk <martinvonz@google.com>
parents: 37631
diff changeset
   440
        progress.update(roundtrips)
42103
362726923ba3 discovery: stop direct use of attribute of partialdiscovery
Georges Racinet <georges.racinet@octobus.net>
parents: 41979
diff changeset
   441
        stats = disco.stats()
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42884
diff changeset
   442
        ui.debug(
43077
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
   443
            b"query %i; still undecided: %i, sample size is: %i\n"
43162
3c6976b1f693 py3-discovery: using plain str in stats dict
Georges Racinet <georges.racinet@octobus.net>
parents: 43077
diff changeset
   444
            % (roundtrips, stats['undecided'], len(sample))
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42884
diff changeset
   445
        )
42103
362726923ba3 discovery: stop direct use of attribute of partialdiscovery
Georges Racinet <georges.racinet@octobus.net>
parents: 41979
diff changeset
   446
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
   447
        # indices between sample and externalized version must match
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
   448
        sample = list(sample)
37630
e1b32dc4646c wireproto: implement command executor interface for version 1 peers
Gregory Szorc <gregory.szorc@gmail.com>
parents: 36718
diff changeset
   449
e1b32dc4646c wireproto: implement command executor interface for version 1 peers
Gregory Szorc <gregory.szorc@gmail.com>
parents: 36718
diff changeset
   450
        with remote.commandexecutor() as e:
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42884
diff changeset
   451
            yesno = e.callcommand(
43077
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
   452
                b'known', {b'nodes': [clnode(r) for r in sample],}
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42884
diff changeset
   453
            ).result()
37630
e1b32dc4646c wireproto: implement command executor interface for version 1 peers
Gregory Szorc <gregory.szorc@gmail.com>
parents: 36718
diff changeset
   454
14624
f03c82d1f50a setdiscovery: batch heads and known(ownheads)
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 14206
diff changeset
   455
        full = True
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
   456
41171
f46ffd23dae8 discovery: add a simple `addinfo` method
Boris Feld <boris.feld@octobus.net>
parents: 41170
diff changeset
   457
        disco.addinfo(zip(sample, yesno))
23343
f8a2647fe020 setdiscovery: avoid a full changelog graph traversal
Siddharth Agarwal <sid0@fb.com>
parents: 23192
diff changeset
   458
41113
9815d3337f9b discovery: move common heads computation inside partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41112
diff changeset
   459
    result = disco.commonheads()
32712
43bda143e3b2 discovery: include timing in the debug output
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32291
diff changeset
   460
    elapsed = util.timer() - start
38373
ef692614e601 progress: hide update(None) in a new complete() method
Martin von Zweigbergk <martinvonz@google.com>
parents: 38350
diff changeset
   461
    progress.complete()
43077
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
   462
    ui.debug(b"%d total queries in %.4fs\n" % (roundtrips, elapsed))
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42884
diff changeset
   463
    msg = (
43077
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
   464
        b'found %d common and %d unknown server heads,'
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
   465
        b' %d roundtrips in %.4fs\n'
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42884
diff changeset
   466
    )
41878
82884bbf8d2b discovery: rename `srvheads` to `knownsrvheads`
Georges Racinet <georges.racinet@octobus.net>
parents: 41304
diff changeset
   467
    missing = set(result) - set(knownsrvheads)
43077
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
   468
    ui.log(b'discovery', msg, len(result), len(missing), roundtrips, elapsed)
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
   469
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
   470
    if not result and srvheadhashes != [nullid]:
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
   471
        if abortwhenunrelated:
43077
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
   472
            raise error.Abort(_(b"repository is unrelated"))
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
   473
        else:
43077
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
   474
            ui.warn(_(b"warning: repository is unrelated\n"))
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42884
diff changeset
   475
        return (
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42884
diff changeset
   476
            {nullid},
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42884
diff changeset
   477
            True,
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42884
diff changeset
   478
            srvheadhashes,
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42884
diff changeset
   479
        )
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
   480
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 42884
diff changeset
   481
    anyincoming = srvheadhashes != [nullid]
39159
5b32b3c618b2 setdiscovery: don't use dagutil for rev -> node conversions
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38373
diff changeset
   482
    result = {clnode(r) for r in result}
5b32b3c618b2 setdiscovery: don't use dagutil for rev -> node conversions
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38373
diff changeset
   483
    return result, anyincoming, srvheadhashes