Mercurial > public > mercurial-scm > hg

annotate mercurial/setdiscovery.py @ 41879:e5ece0f46b40

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
discovery: moved sampling functions inside discovery object In this patch, we transform the sampling functions into methods of the `partialdiscovery` class in the Python case. This will provide multiple benefit. For example we can keep some cache from one sampling to another. In addition this will help the Oxidation work as all graph traversal related logic will be contained in a single object.
author Georges Racinet <georges.racinet@octobus.net>
date Wed, 27 Feb 2019 23:55:19 +0100
parents 82884bbf8d2b
children 55919b96c02a
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,
32712
43bda143e3b2 discovery: include timing in the debug output
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32291
diff changeset
55 util,
25973
fb5664eb8414 setdiscovery: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25914
diff changeset
56 )
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
57
39174
71d83b315778 setdiscovery: don't use dagutil for parent resolution
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39173
diff changeset
58 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
59 """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
60
39168
2d218db7389b setdiscovery: reflect use of revs instead of nodes
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39166
diff changeset
61 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
62 <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
63
9ca2eb881b53 setdiscovery: document the '_updatesample' function
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 23808
diff changeset
64 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
65 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
66 reached.
9ca2eb881b53 setdiscovery: document the '_updatesample' function
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 23808
diff changeset
67
39168
2d218db7389b setdiscovery: reflect use of revs instead of nodes
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39166
diff changeset
68 :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
69 :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
70 :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
71 :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
72 :quicksamplesize: optional target size of the sample"""
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
73 dist = {}
25113
0ca8410ea345 util: drop alias for collections.deque
Martin von Zweigbergk <martinvonz@google.com>
parents: 23817
diff changeset
74 visit = collections.deque(heads)
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
75 seen = set()
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
76 factor = 1
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
77 while visit:
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
78 curr = visit.popleft()
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
79 if curr in seen:
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
80 continue
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
81 d = dist.setdefault(curr, 1)
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
82 if d > factor:
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
83 factor *= 2
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
84 if d == factor:
23814
6a5877a73141 setdiscovery: drop the 'always' argument to '_updatesample'
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 23813
diff changeset
85 sample.add(curr)
6a5877a73141 setdiscovery: drop the 'always' argument to '_updatesample'
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 23813
diff changeset
86 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
87 return
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
88 seen.add(curr)
39174
71d83b315778 setdiscovery: don't use dagutil for parent resolution
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39173
diff changeset
89
71d83b315778 setdiscovery: don't use dagutil for parent resolution
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39173
diff changeset
90 for p in parentfn(curr):
71d83b315778 setdiscovery: don't use dagutil for parent resolution
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39173
diff changeset
91 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
92 dist.setdefault(p, d + 1)
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
93 visit.append(p)
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
94
23083
ee45f5c2ffcc setdiscovery: extract sample limitation in a `_limitsample` function
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 20656
diff changeset
95 def _limitsample(sample, desiredlen):
ee45f5c2ffcc setdiscovery: extract sample limitation in a `_limitsample` function
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 20656
diff changeset
96 """return a random subset of sample of at most desiredlen item"""
ee45f5c2ffcc setdiscovery: extract sample limitation in a `_limitsample` function
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 20656
diff changeset
97 if len(sample) > desiredlen:
ee45f5c2ffcc setdiscovery: extract sample limitation in a `_limitsample` function
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 20656
diff changeset
98 sample = set(random.sample(sample, desiredlen))
ee45f5c2ffcc setdiscovery: extract sample limitation in a `_limitsample` function
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 20656
diff changeset
99 return sample
ee45f5c2ffcc setdiscovery: extract sample limitation in a `_limitsample` function
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 20656
diff changeset
100
41112
3023bc4b3da0 discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41111
diff changeset
101 class partialdiscovery(object):
3023bc4b3da0 discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41111
diff changeset
102 """an object representing ongoing discovery
3023bc4b3da0 discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41111
diff changeset
103
3023bc4b3da0 discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41111
diff changeset
104 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
105 current set of changeset in various states:
3023bc4b3da0 discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41111
diff changeset
106
41172
3dcc96582627 discovery: improve partial discovery documentation
Boris Feld <boris.feld@octobus.net>
parents: 41171
diff changeset
107 - common: revs also known remotely
3dcc96582627 discovery: improve partial discovery documentation
Boris Feld <boris.feld@octobus.net>
parents: 41171
diff changeset
108 - 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
109 - missing: revs missing remotely
3dcc96582627 discovery: improve partial discovery documentation
Boris Feld <boris.feld@octobus.net>
parents: 41171
diff changeset
110 (all tracked revisions are known locally)
41112
3023bc4b3da0 discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41111
diff changeset
111 """
3023bc4b3da0 discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41111
diff changeset
112
41167
870a89c6909d discovery: move undecided set on the partialdiscovery
Boris Feld <boris.feld@octobus.net>
parents: 41162
diff changeset
113 def __init__(self, repo, targetheads):
41112
3023bc4b3da0 discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41111
diff changeset
114 self._repo = repo
41167
870a89c6909d discovery: move undecided set on the partialdiscovery
Boris Feld <boris.feld@octobus.net>
parents: 41162
diff changeset
115 self._targetheads = targetheads
41112
3023bc4b3da0 discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41111
diff changeset
116 self._common = repo.changelog.incrementalmissingrevs()
41167
870a89c6909d discovery: move undecided set on the partialdiscovery
Boris Feld <boris.feld@octobus.net>
parents: 41162
diff changeset
117 self._undecided = None
41170
96201120cdf5 discovery: move missing tracking inside the partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41169
diff changeset
118 self.missing = set()
41112
3023bc4b3da0 discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41111
diff changeset
119
3023bc4b3da0 discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41111
diff changeset
120 def addcommons(self, commons):
3023bc4b3da0 discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41111
diff changeset
121 """registrer nodes known as common"""
3023bc4b3da0 discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41111
diff changeset
122 self._common.addbases(commons)
41304
76873548b051 partialdiscovery: avoid `undecided` related computation sooner than necessary
Boris Feld <boris.feld@octobus.net>
parents: 41280
diff changeset
123 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
124 self._common.removeancestorsfrom(self._undecided)
41112
3023bc4b3da0 discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41111
diff changeset
125
41170
96201120cdf5 discovery: move missing tracking inside the partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41169
diff changeset
126 def addmissings(self, missings):
96201120cdf5 discovery: move missing tracking inside the partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41169
diff changeset
127 """registrer some nodes as missing"""
41280
f4277a35c42c discovery: compute newly discovered missing in a more efficient way
Boris Feld <boris.feld@octobus.net>
parents: 41245
diff changeset
128 newmissing = self._repo.revs('%ld::%ld', missings, self.undecided)
f4277a35c42c discovery: compute newly discovered missing in a more efficient way
Boris Feld <boris.feld@octobus.net>
parents: 41245
diff changeset
129 if newmissing:
f4277a35c42c discovery: compute newly discovered missing in a more efficient way
Boris Feld <boris.feld@octobus.net>
parents: 41245
diff changeset
130 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
131 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
132
41171
f46ffd23dae8 discovery: add a simple `addinfo` method
Boris Feld <boris.feld@octobus.net>
parents: 41170
diff changeset
133 def addinfo(self, sample):
f46ffd23dae8 discovery: add a simple `addinfo` method
Boris Feld <boris.feld@octobus.net>
parents: 41170
diff changeset
134 """consume an iterable of (rev, known) tuples"""
f46ffd23dae8 discovery: add a simple `addinfo` method
Boris Feld <boris.feld@octobus.net>
parents: 41170
diff changeset
135 common = set()
f46ffd23dae8 discovery: add a simple `addinfo` method
Boris Feld <boris.feld@octobus.net>
parents: 41170
diff changeset
136 missing = set()
f46ffd23dae8 discovery: add a simple `addinfo` method
Boris Feld <boris.feld@octobus.net>
parents: 41170
diff changeset
137 for rev, known in sample:
f46ffd23dae8 discovery: add a simple `addinfo` method
Boris Feld <boris.feld@octobus.net>
parents: 41170
diff changeset
138 if known:
f46ffd23dae8 discovery: add a simple `addinfo` method
Boris Feld <boris.feld@octobus.net>
parents: 41170
diff changeset
139 common.add(rev)
f46ffd23dae8 discovery: add a simple `addinfo` method
Boris Feld <boris.feld@octobus.net>
parents: 41170
diff changeset
140 else:
f46ffd23dae8 discovery: add a simple `addinfo` method
Boris Feld <boris.feld@octobus.net>
parents: 41170
diff changeset
141 missing.add(rev)
f46ffd23dae8 discovery: add a simple `addinfo` method
Boris Feld <boris.feld@octobus.net>
parents: 41170
diff changeset
142 if common:
f46ffd23dae8 discovery: add a simple `addinfo` method
Boris Feld <boris.feld@octobus.net>
parents: 41170
diff changeset
143 self.addcommons(common)
f46ffd23dae8 discovery: add a simple `addinfo` method
Boris Feld <boris.feld@octobus.net>
parents: 41170
diff changeset
144 if missing:
f46ffd23dae8 discovery: add a simple `addinfo` method
Boris Feld <boris.feld@octobus.net>
parents: 41170
diff changeset
145 self.addmissings(missing)
f46ffd23dae8 discovery: add a simple `addinfo` method
Boris Feld <boris.feld@octobus.net>
parents: 41170
diff changeset
146
41112
3023bc4b3da0 discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41111
diff changeset
147 def hasinfo(self):
3023bc4b3da0 discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41111
diff changeset
148 """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
149 return self._common.hasbases()
3023bc4b3da0 discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41111
diff changeset
150
41169
3ce5b96482c6 discovery: add a `iscomplete` method to the `partialdiscovery` object
Boris Feld <boris.feld@octobus.net>
parents: 41168
diff changeset
151 def iscomplete(self):
3ce5b96482c6 discovery: add a `iscomplete` method to the `partialdiscovery` object
Boris Feld <boris.feld@octobus.net>
parents: 41168
diff changeset
152 """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
153 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
154
41167
870a89c6909d discovery: move undecided set on the partialdiscovery
Boris Feld <boris.feld@octobus.net>
parents: 41162
diff changeset
155 @property
870a89c6909d discovery: move undecided set on the partialdiscovery
Boris Feld <boris.feld@octobus.net>
parents: 41162
diff changeset
156 def undecided(self):
870a89c6909d discovery: move undecided set on the partialdiscovery
Boris Feld <boris.feld@octobus.net>
parents: 41162
diff changeset
157 if self._undecided is not None:
870a89c6909d discovery: move undecided set on the partialdiscovery
Boris Feld <boris.feld@octobus.net>
parents: 41162
diff changeset
158 return self._undecided
870a89c6909d discovery: move undecided set on the partialdiscovery
Boris Feld <boris.feld@octobus.net>
parents: 41162
diff changeset
159 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
160 return self._undecided
870a89c6909d discovery: move undecided set on the partialdiscovery
Boris Feld <boris.feld@octobus.net>
parents: 41162
diff changeset
161
41113
9815d3337f9b discovery: move common heads computation inside partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41112
diff changeset
162 def commonheads(self):
9815d3337f9b discovery: move common heads computation inside partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41112
diff changeset
163 """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
164 # 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
165 # common.bases and all its ancestors
41245
2a8782cc2e16 discovery: using the new basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents: 41172
diff changeset
166 return self._common.basesheads()
41112
3023bc4b3da0 discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41111
diff changeset
167
41879
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
168 def takequicksample(self, headrevs, size):
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
169 """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
170
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
171 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
172 ancestors of heads.
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
173
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
174 :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
175 :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
176 revs = self.undecided
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
177 if len(revs) <= size:
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
178 return list(revs)
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
179 sample = set(self._repo.revs('heads(%ld)', revs))
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
180
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
181 if len(sample) >= size:
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
182 return _limitsample(sample, size)
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
183
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
184 _updatesample(None, headrevs, sample, self._repo.changelog.parentrevs,
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
185 quicksamplesize=size)
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
186 return sample
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
187
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
188 def takefullsample(self, headrevs, size):
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
189 revs = self.undecided
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
190 if len(revs) <= size:
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
191 return list(revs)
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
192 repo = self._repo
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
193 sample = set(repo.revs('heads(%ld)', revs))
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
194
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
195 # update from heads
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
196 revsheads = set(repo.revs('heads(%ld)', revs))
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
197 _updatesample(revs, revsheads, sample, repo.changelog.parentrevs)
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
198
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
199 # update from roots
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
200 revsroots = set(repo.revs('roots(%ld)', revs))
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
201
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
202 # _updatesample() essentially does interaction over revisions to look
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
203 # up their children. This lookup is expensive and doing it in a loop is
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
204 # quadratic. We precompute the children for all relevant revisions and
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
205 # make the lookup in _updatesample() a simple dict lookup.
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
206 #
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
207 # Because this function can be called multiple times during discovery,
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
208 # we may still perform redundant work and there is room to optimize
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
209 # this by keeping a persistent cache of children across invocations.
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
210 children = {}
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
211
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
212 parentrevs = repo.changelog.parentrevs
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
213 for rev in repo.changelog.revs(start=min(revsroots)):
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
214 # Always ensure revision has an entry so we don't need to worry
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
215 # about missing keys.
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
216 children.setdefault(rev, [])
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
217
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
218 for prev in parentrevs(rev):
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
219 if prev == nullrev:
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
220 continue
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
221
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
222 children.setdefault(prev, []).append(rev)
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
223
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
224 _updatesample(revs, revsroots, sample, children.__getitem__)
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
225 assert sample
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
226 sample = _limitsample(sample, size)
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
227 if len(sample) < size:
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
228 more = size - len(sample)
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
229 sample.update(random.sample(list(revs - sample), more))
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
230 return sample
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
231
36715
613954a17a25 setdiscovery: back out changeset 5cfdf6137af8 (issue5809)
Martin von Zweigbergk <martinvonz@google.com>
parents: 35849
diff changeset
232 def findcommonheads(ui, local, remote,
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
233 initialsamplesize=100,
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
234 fullsamplesize=200,
35304
f77121b6bf1b setdiscover: allow to ignore part of the local graph
Boris Feld <boris.feld@octobus.net>
parents: 32768
diff changeset
235 abortwhenunrelated=True,
f77121b6bf1b setdiscover: allow to ignore part of the local graph
Boris Feld <boris.feld@octobus.net>
parents: 32768
diff changeset
236 ancestorsof=None):
14206
2bf60f158ecb setdiscovery: limit lines to 80 characters
Steven Brown <StevenGBrown@gmail.com>
parents: 14164
diff changeset
237 '''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
238 missing nodes from or in remote.
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
239 '''
32712
43bda143e3b2 discovery: include timing in the debug output
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32291
diff changeset
240 start = util.timer()
43bda143e3b2 discovery: include timing in the debug output
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32291
diff changeset
241
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
242 roundtrips = 0
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
243 cl = local.changelog
39159
5b32b3c618b2 setdiscovery: don't use dagutil for rev -> node conversions
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38373
diff changeset
244 clnode = cl.node
39161
858a12846f4f setdiscovery: don't use dagutil for node -> rev conversion
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39159
diff changeset
245 clrev = cl.rev
39159
5b32b3c618b2 setdiscovery: don't use dagutil for rev -> node conversions
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38373
diff changeset
246
35304
f77121b6bf1b setdiscover: allow to ignore part of the local graph
Boris Feld <boris.feld@octobus.net>
parents: 32768
diff changeset
247 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
248 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
249 else:
860e83cd97de setdiscovery: don't use dagutil to compute heads
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39161
diff changeset
250 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
251
14624
f03c82d1f50a setdiscovery: batch heads and known(ownheads)
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 14206
diff changeset
252 # early exit if we know all the specified remote heads already
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
253 ui.debug("query 1; heads\n")
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
254 roundtrips += 1
23084
3ef893520a85 setdiscovery: limit the size of the initial sample (issue4411)
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 23083
diff changeset
255 sample = _limitsample(ownheads, initialsamplesize)
23192
73cfaa348650 discovery: indices between sample and yesno must match (issue4438)
Mads Kiilerich <madski@unity3d.com>
parents: 23191
diff changeset
256 # indices between sample and externalized version must match
73cfaa348650 discovery: indices between sample and yesno must match (issue4438)
Mads Kiilerich <madski@unity3d.com>
parents: 23191
diff changeset
257 sample = list(sample)
37631
2f626233859b wireproto: implement batching on peer executor interface
Gregory Szorc <gregory.szorc@gmail.com>
parents: 37630
diff changeset
258
2f626233859b wireproto: implement batching on peer executor interface
Gregory Szorc <gregory.szorc@gmail.com>
parents: 37630
diff changeset
259 with remote.commandexecutor() as e:
2f626233859b wireproto: implement batching on peer executor interface
Gregory Szorc <gregory.szorc@gmail.com>
parents: 37630
diff changeset
260 fheads = e.callcommand('heads', {})
2f626233859b wireproto: implement batching on peer executor interface
Gregory Szorc <gregory.szorc@gmail.com>
parents: 37630
diff changeset
261 fknown = e.callcommand('known', {
39159
5b32b3c618b2 setdiscovery: don't use dagutil for rev -> node conversions
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38373
diff changeset
262 'nodes': [clnode(r) for r in sample],
37631
2f626233859b wireproto: implement batching on peer executor interface
Gregory Szorc <gregory.szorc@gmail.com>
parents: 37630
diff changeset
263 })
2f626233859b wireproto: implement batching on peer executor interface
Gregory Szorc <gregory.szorc@gmail.com>
parents: 37630
diff changeset
264
2f626233859b wireproto: implement batching on peer executor interface
Gregory Szorc <gregory.szorc@gmail.com>
parents: 37630
diff changeset
265 srvheadhashes, yesno = fheads.result(), fknown.result()
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
266
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
267 if cl.tip() == nullid:
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
268 if srvheadhashes != [nullid]:
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
269 return [nullid], True, srvheadhashes
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
270 return [nullid], False, []
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
271
14206
2bf60f158ecb setdiscovery: limit lines to 80 characters
Steven Brown <StevenGBrown@gmail.com>
parents: 14164
diff changeset
272 # 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
273 # compatibility reasons)
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
274 ui.status(_("searching for changes\n"))
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
275
41878
82884bbf8d2b discovery: rename `srvheads` to `knownsrvheads`
Georges Racinet <georges.racinet@octobus.net>
parents: 41304
diff changeset
276 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
277 for node in srvheadhashes:
858a12846f4f setdiscovery: don't use dagutil for node -> rev conversion
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39159
diff changeset
278 if node == nullid:
858a12846f4f setdiscovery: don't use dagutil for node -> rev conversion
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39159
diff changeset
279 continue
858a12846f4f setdiscovery: don't use dagutil for node -> rev conversion
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39159
diff changeset
280
858a12846f4f setdiscovery: don't use dagutil for node -> rev conversion
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39159
diff changeset
281 try:
41878
82884bbf8d2b discovery: rename `srvheads` to `knownsrvheads`
Georges Racinet <georges.racinet@octobus.net>
parents: 41304
diff changeset
282 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
283 # 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
284 except error.LookupError:
858a12846f4f setdiscovery: don't use dagutil for node -> rev conversion
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39159
diff changeset
285 continue
858a12846f4f setdiscovery: don't use dagutil for node -> rev conversion
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39159
diff changeset
286
41878
82884bbf8d2b discovery: rename `srvheads` to `knownsrvheads`
Georges Racinet <georges.racinet@octobus.net>
parents: 41304
diff changeset
287 if len(knownsrvheads) == len(srvheadhashes):
14833
308e1b5acc87 discovery: quiet note about heads
Matt Mackall <mpm@selenic.com>
parents: 14624
diff changeset
288 ui.debug("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
289 return srvheadhashes, False, srvheadhashes
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
290
36716
bf485b70d0ae setdiscovery: remove initialsamplesize from a condition
Martin von Zweigbergk <martinvonz@google.com>
parents: 36715
diff changeset
291 if len(sample) == len(ownheads) and all(yesno):
15497
9bea3aed6ee1 add missing localization markup
Mads Kiilerich <mads@kiilerich.com>
parents: 15063
diff changeset
292 ui.note(_("all local heads known remotely\n"))
39159
5b32b3c618b2 setdiscovery: don't use dagutil for rev -> node conversions
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38373
diff changeset
293 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
294 return ownheadhashes, True, srvheadhashes
14624
f03c82d1f50a setdiscovery: batch heads and known(ownheads)
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 14206
diff changeset
295
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
296 # full blown discovery
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
297
41167
870a89c6909d discovery: move undecided set on the partialdiscovery
Boris Feld <boris.feld@octobus.net>
parents: 41162
diff changeset
298 disco = partialdiscovery(local, ownheads)
23343
f8a2647fe020 setdiscovery: avoid a full changelog graph traversal
Siddharth Agarwal <sid0@fb.com>
parents: 23192
diff changeset
299 # 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
300 # response
41878
82884bbf8d2b discovery: rename `srvheads` to `knownsrvheads`
Georges Racinet <georges.racinet@octobus.net>
parents: 41304
diff changeset
301 disco.addcommons(knownsrvheads)
41171
f46ffd23dae8 discovery: add a simple `addinfo` method
Boris Feld <boris.feld@octobus.net>
parents: 41170
diff changeset
302 disco.addinfo(zip(sample, yesno))
16683
525fdb738975 cleanup: eradicate long lines
Brodie Rao <brodie@sf.io>
parents: 15713
diff changeset
303
14624
f03c82d1f50a setdiscovery: batch heads and known(ownheads)
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 14206
diff changeset
304 full = False
38350
9e70690a21ac setdiscovery: use progress helper
Martin von Zweigbergk <martinvonz@google.com>
parents: 37631
diff changeset
305 progress = ui.makeprogress(_('searching'), unit=_('queries'))
41169
3ce5b96482c6 discovery: add a `iscomplete` method to the `partialdiscovery` object
Boris Feld <boris.feld@octobus.net>
parents: 41168
diff changeset
306 while not disco.iscomplete():
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
307
41112
3023bc4b3da0 discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41111
diff changeset
308 if full or disco.hasinfo():
23747
f82173a90c2c setdiscovery: factorize similar sampling code
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 23746
diff changeset
309 if full:
f82173a90c2c setdiscovery: factorize similar sampling code
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 23746
diff changeset
310 ui.note(_("sampling from both directions\n"))
f82173a90c2c setdiscovery: factorize similar sampling code
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 23746
diff changeset
311 else:
f82173a90c2c setdiscovery: factorize similar sampling code
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 23746
diff changeset
312 ui.debug("taking initial sample\n")
41879
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
313 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
314 targetsize = fullsamplesize
14624
f03c82d1f50a setdiscovery: batch heads and known(ownheads)
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 14206
diff changeset
315 else:
f03c82d1f50a setdiscovery: batch heads and known(ownheads)
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 14206
diff changeset
316 # use even cheaper initial sample
f03c82d1f50a setdiscovery: batch heads and known(ownheads)
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 14206
diff changeset
317 ui.debug("taking quick initial sample\n")
41879
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
318 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
319 targetsize = initialsamplesize
41879
e5ece0f46b40 discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents: 41878
diff changeset
320 sample = samplefunc(ownheads, targetsize)
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
321
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
322 roundtrips += 1
38350
9e70690a21ac setdiscovery: use progress helper
Martin von Zweigbergk <martinvonz@google.com>
parents: 37631
diff changeset
323 progress.update(roundtrips)
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
324 ui.debug("query %i; still undecided: %i, sample size is: %i\n"
41167
870a89c6909d discovery: move undecided set on the partialdiscovery
Boris Feld <boris.feld@octobus.net>
parents: 41162
diff changeset
325 % (roundtrips, len(disco.undecided), len(sample)))
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
326 # indices between sample and externalized version must match
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
327 sample = list(sample)
37630
e1b32dc4646c wireproto: implement command executor interface for version 1 peers
Gregory Szorc <gregory.szorc@gmail.com>
parents: 36718
diff changeset
328
e1b32dc4646c wireproto: implement command executor interface for version 1 peers
Gregory Szorc <gregory.szorc@gmail.com>
parents: 36718
diff changeset
329 with remote.commandexecutor() as e:
e1b32dc4646c wireproto: implement command executor interface for version 1 peers
Gregory Szorc <gregory.szorc@gmail.com>
parents: 36718
diff changeset
330 yesno = e.callcommand('known', {
39159
5b32b3c618b2 setdiscovery: don't use dagutil for rev -> node conversions
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38373
diff changeset
331 'nodes': [clnode(r) for r in sample],
37630
e1b32dc4646c wireproto: implement command executor interface for version 1 peers
Gregory Szorc <gregory.szorc@gmail.com>
parents: 36718
diff changeset
332 }).result()
e1b32dc4646c wireproto: implement command executor interface for version 1 peers
Gregory Szorc <gregory.szorc@gmail.com>
parents: 36718
diff changeset
333
14624
f03c82d1f50a setdiscovery: batch heads and known(ownheads)
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 14206
diff changeset
334 full = True
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
335
41171
f46ffd23dae8 discovery: add a simple `addinfo` method
Boris Feld <boris.feld@octobus.net>
parents: 41170
diff changeset
336 disco.addinfo(zip(sample, yesno))
23343
f8a2647fe020 setdiscovery: avoid a full changelog graph traversal
Siddharth Agarwal <sid0@fb.com>
parents: 23192
diff changeset
337
41113
9815d3337f9b discovery: move common heads computation inside partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents: 41112
diff changeset
338 result = disco.commonheads()
32712
43bda143e3b2 discovery: include timing in the debug output
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32291
diff changeset
339 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
340 progress.complete()
32712
43bda143e3b2 discovery: include timing in the debug output
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32291
diff changeset
341 ui.debug("%d total queries in %.4fs\n" % (roundtrips, elapsed))
32768
483d47753726 setdiscovery: improves logged message
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32713
diff changeset
342 msg = ('found %d common and %d unknown server heads,'
483d47753726 setdiscovery: improves logged message
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32713
diff changeset
343 ' %d roundtrips in %.4fs\n')
41878
82884bbf8d2b discovery: rename `srvheads` to `knownsrvheads`
Georges Racinet <georges.racinet@octobus.net>
parents: 41304
diff changeset
344 missing = set(result) - set(knownsrvheads)
32768
483d47753726 setdiscovery: improves logged message
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32713
diff changeset
345 ui.log('discovery', msg, len(result), len(missing), roundtrips,
32713
28240b75e880 discovery: log discovery result in non-trivial cases
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32712
diff changeset
346 elapsed)
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
347
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
348 if not result and srvheadhashes != [nullid]:
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
349 if abortwhenunrelated:
26587
56b2bcea2529 error: get Abort from 'error' instead of 'util'
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25973
diff changeset
350 raise error.Abort(_("repository is unrelated"))
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
351 else:
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
352 ui.warn(_("warning: repository is unrelated\n"))
32291
bd872f64a8ba cleanup: use set literals
Martin von Zweigbergk <martinvonz@google.com>
parents: 28437
diff changeset
353 return ({nullid}, True, srvheadhashes,)
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
354
14981
192e02680d09 setdiscovery: return anyincoming=False when remote's only head is nullid
Andrew Pritchard <andrewp@fogcreek.com>
parents: 14833
diff changeset
355 anyincoming = (srvheadhashes != [nullid])
39159
5b32b3c618b2 setdiscovery: don't use dagutil for rev -> node conversions
Gregory Szorc <gregory.szorc@gmail.com>
parents: 38373
diff changeset
356 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
357 return result, anyincoming, srvheadhashes