annotate mercurial/setdiscovery.py @ 44079:191a461d6be6

rust-utils: add util to find a slice in another slice Differential Revision: https://phab.mercurial-scm.org/D7863
author Raphaël Gomès <rgomes@octobus.net>
date Tue, 14 Jan 2020 18:00:05 +0100
parents 9f70512ae2cf
children 89a2afe31e82
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
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