Mercurial > public > mercurial-scm > hg-stable
annotate mercurial/setdiscovery.py @ 41886:e514799e4e07
discovery: use a lower level but faster way to retrieve parents
We already know that no revision in the undecided set are filtered, so we can
skip multiple checks and directly access lower level data.
In a private pathological case, this improves the timing from about 70 seconds
to about 50 seconds. There are other actions to be taken to improve that case,
however this gives an idea of the general overhead.
| author | Pierre-Yves David <pierre-yves.david@octobus.net> |
|---|---|
| date | Thu, 28 Feb 2019 00:56:27 +0100 |
| parents | 55919b96c02a |
| children | c98420914c10 |
| 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, |
|
32732
43bda143e3b2
discovery: include timing in the debug output
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
32331
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 |
|
39207
71d83b315778
setdiscovery: don't use dagutil for parent resolution
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39206
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 |
|
39201
2d218db7389b
setdiscovery: reflect use of revs instead of nodes
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39199
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:
39199
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 |
|
39201
2d218db7389b
setdiscovery: reflect use of revs instead of nodes
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39199
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 |
|
39201
2d218db7389b
setdiscovery: reflect use of revs instead of nodes
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39199
diff
changeset
|
68 :revs: set of revs we want to discover (if None, assume the whole dag) |
|
39203
754f389b87f2
setdiscovery: pass heads into _updatesample()
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39202
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 |
|
39207
71d83b315778
setdiscovery: don't use dagutil for parent resolution
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39206
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) |
|
39207
71d83b315778
setdiscovery: don't use dagutil for parent resolution
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39206
diff
changeset
|
89 |
|
71d83b315778
setdiscovery: don't use dagutil for parent resolution
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39206
diff
changeset
|
90 for p in parentfn(curr): |
|
71d83b315778
setdiscovery: don't use dagutil for parent resolution
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39206
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 |
|
41115
3023bc4b3da0
discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents:
41114
diff
changeset
|
101 class partialdiscovery(object): |
|
3023bc4b3da0
discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents:
41114
diff
changeset
|
102 """an object representing ongoing discovery |
|
3023bc4b3da0
discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents:
41114
diff
changeset
|
103 |
|
3023bc4b3da0
discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents:
41114
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:
41114
diff
changeset
|
105 current set of changeset in various states: |
|
3023bc4b3da0
discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents:
41114
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) |
|
41115
3023bc4b3da0
discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents:
41114
diff
changeset
|
111 """ |
|
3023bc4b3da0
discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents:
41114
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): |
|
41115
3023bc4b3da0
discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents:
41114
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 |
|
41115
3023bc4b3da0
discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents:
41114
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() |
|
41115
3023bc4b3da0
discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents:
41114
diff
changeset
|
119 |
|
3023bc4b3da0
discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents:
41114
diff
changeset
|
120 def addcommons(self, commons): |
|
3023bc4b3da0
discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents:
41114
diff
changeset
|
121 """registrer nodes known as common""" |
|
3023bc4b3da0
discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents:
41114
diff
changeset
|
122 self._common.addbases(commons) |
|
41303
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) |
|
41115
3023bc4b3da0
discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents:
41114
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 |
|
41115
3023bc4b3da0
discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents:
41114
diff
changeset
|
147 def hasinfo(self): |
|
3023bc4b3da0
discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents:
41114
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:
41114
diff
changeset
|
149 return self._common.hasbases() |
|
3023bc4b3da0
discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents:
41114
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 |
|
41116
9815d3337f9b
discovery: move common heads computation inside partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents:
41115
diff
changeset
|
162 def commonheads(self): |
|
9815d3337f9b
discovery: move common heads computation inside partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents:
41115
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:
41115
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:
41115
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() |
|
41115
3023bc4b3da0
discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents:
41114
diff
changeset
|
167 |
|
41886
e514799e4e07
discovery: use a lower level but faster way to retrieve parents
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
41885
diff
changeset
|
168 def _parentsgetter(self): |
|
e514799e4e07
discovery: use a lower level but faster way to retrieve parents
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
41885
diff
changeset
|
169 getrev = self._repo.changelog.index.__getitem__ |
|
e514799e4e07
discovery: use a lower level but faster way to retrieve parents
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
41885
diff
changeset
|
170 def getparents(r): |
|
e514799e4e07
discovery: use a lower level but faster way to retrieve parents
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
41885
diff
changeset
|
171 return getrev(r)[5:6] |
|
e514799e4e07
discovery: use a lower level but faster way to retrieve parents
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
41885
diff
changeset
|
172 return getparents |
|
e514799e4e07
discovery: use a lower level but faster way to retrieve parents
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
41885
diff
changeset
|
173 |
|
41884
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
174 def takequicksample(self, headrevs, size): |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
175 """takes a quick sample of size <size> |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
176 |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
177 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:
41883
diff
changeset
|
178 ancestors of heads. |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
179 |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
180 :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:
41883
diff
changeset
|
181 :size: the maximum size of the sample""" |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
182 revs = self.undecided |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
183 if len(revs) <= size: |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
184 return list(revs) |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
185 sample = set(self._repo.revs('heads(%ld)', revs)) |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
186 |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
187 if len(sample) >= size: |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
188 return _limitsample(sample, size) |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
189 |
|
41886
e514799e4e07
discovery: use a lower level but faster way to retrieve parents
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
41885
diff
changeset
|
190 _updatesample(None, headrevs, sample, self._parentsgetter(), |
|
41884
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
191 quicksamplesize=size) |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
192 return sample |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
193 |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
194 def takefullsample(self, headrevs, size): |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
195 revs = self.undecided |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
196 if len(revs) <= size: |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
197 return list(revs) |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
198 repo = self._repo |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
199 sample = set(repo.revs('heads(%ld)', revs)) |
|
41886
e514799e4e07
discovery: use a lower level but faster way to retrieve parents
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
41885
diff
changeset
|
200 parentrevs = self._parentsgetter() |
|
41884
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
201 |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
202 # update from heads |
|
41885
55919b96c02a
discovery: avoid computing identical sets of heads twice
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
41884
diff
changeset
|
203 revsheads = sample.copy() |
|
41886
e514799e4e07
discovery: use a lower level but faster way to retrieve parents
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
41885
diff
changeset
|
204 _updatesample(revs, revsheads, sample, parentrevs) |
|
41884
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
205 |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
206 # update from roots |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
207 revsroots = set(repo.revs('roots(%ld)', revs)) |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
208 |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
209 # _updatesample() essentially does interaction over revisions to look |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
210 # 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:
41883
diff
changeset
|
211 # 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:
41883
diff
changeset
|
212 # make the lookup in _updatesample() a simple dict lookup. |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
213 # |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
214 # 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:
41883
diff
changeset
|
215 # 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:
41883
diff
changeset
|
216 # 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:
41883
diff
changeset
|
217 children = {} |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
218 |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
219 for rev in repo.changelog.revs(start=min(revsroots)): |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
220 # 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:
41883
diff
changeset
|
221 # about missing keys. |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
222 children.setdefault(rev, []) |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
223 |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
224 for prev in parentrevs(rev): |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
225 if prev == nullrev: |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
226 continue |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
227 |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
228 children.setdefault(prev, []).append(rev) |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
229 |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
230 _updatesample(revs, revsroots, sample, children.__getitem__) |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
231 assert sample |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
232 sample = _limitsample(sample, size) |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
233 if len(sample) < size: |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
234 more = size - len(sample) |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
235 sample.update(random.sample(list(revs - sample), more)) |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
236 return sample |
|
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
237 |
|
36738
613954a17a25
setdiscovery: back out changeset 5cfdf6137af8 (issue5809)
Martin von Zweigbergk <martinvonz@google.com>
parents:
35889
diff
changeset
|
238 def findcommonheads(ui, local, remote, |
|
14164
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
239 initialsamplesize=100, |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
240 fullsamplesize=200, |
|
35313
f77121b6bf1b
setdiscover: allow to ignore part of the local graph
Boris Feld <boris.feld@octobus.net>
parents:
32788
diff
changeset
|
241 abortwhenunrelated=True, |
|
f77121b6bf1b
setdiscover: allow to ignore part of the local graph
Boris Feld <boris.feld@octobus.net>
parents:
32788
diff
changeset
|
242 ancestorsof=None): |
|
14206
2bf60f158ecb
setdiscovery: limit lines to 80 characters
Steven Brown <StevenGBrown@gmail.com>
parents:
14164
diff
changeset
|
243 '''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
|
244 missing nodes from or in remote. |
|
14164
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
245 ''' |
|
32732
43bda143e3b2
discovery: include timing in the debug output
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
32331
diff
changeset
|
246 start = util.timer() |
|
43bda143e3b2
discovery: include timing in the debug output
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
32331
diff
changeset
|
247 |
|
14164
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
248 roundtrips = 0 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
249 cl = local.changelog |
|
39192
5b32b3c618b2
setdiscovery: don't use dagutil for rev -> node conversions
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38379
diff
changeset
|
250 clnode = cl.node |
|
39194
858a12846f4f
setdiscovery: don't use dagutil for node -> rev conversion
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39192
diff
changeset
|
251 clrev = cl.rev |
|
39192
5b32b3c618b2
setdiscovery: don't use dagutil for rev -> node conversions
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38379
diff
changeset
|
252 |
|
35313
f77121b6bf1b
setdiscover: allow to ignore part of the local graph
Boris Feld <boris.feld@octobus.net>
parents:
32788
diff
changeset
|
253 if ancestorsof is not None: |
|
39198
860e83cd97de
setdiscovery: don't use dagutil to compute heads
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39194
diff
changeset
|
254 ownheads = [clrev(n) for n in ancestorsof] |
|
860e83cd97de
setdiscovery: don't use dagutil to compute heads
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39194
diff
changeset
|
255 else: |
|
860e83cd97de
setdiscovery: don't use dagutil to compute heads
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39194
diff
changeset
|
256 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:
39194
diff
changeset
|
257 |
|
14624
f03c82d1f50a
setdiscovery: batch heads and known(ownheads)
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
14206
diff
changeset
|
258 # 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
|
259 ui.debug("query 1; heads\n") |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
260 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
|
261 sample = _limitsample(ownheads, initialsamplesize) |
|
23192
73cfaa348650
discovery: indices between sample and yesno must match (issue4438)
Mads Kiilerich <madski@unity3d.com>
parents:
23191
diff
changeset
|
262 # 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
|
263 sample = list(sample) |
|
37631
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 with remote.commandexecutor() as e: |
|
2f626233859b
wireproto: implement batching on peer executor interface
Gregory Szorc <gregory.szorc@gmail.com>
parents:
37630
diff
changeset
|
266 fheads = e.callcommand('heads', {}) |
|
2f626233859b
wireproto: implement batching on peer executor interface
Gregory Szorc <gregory.szorc@gmail.com>
parents:
37630
diff
changeset
|
267 fknown = e.callcommand('known', { |
|
39192
5b32b3c618b2
setdiscovery: don't use dagutil for rev -> node conversions
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38379
diff
changeset
|
268 '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
|
269 }) |
|
2f626233859b
wireproto: implement batching on peer executor interface
Gregory Szorc <gregory.szorc@gmail.com>
parents:
37630
diff
changeset
|
270 |
|
2f626233859b
wireproto: implement batching on peer executor interface
Gregory Szorc <gregory.szorc@gmail.com>
parents:
37630
diff
changeset
|
271 srvheadhashes, yesno = fheads.result(), fknown.result() |
|
14164
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
272 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
273 if cl.tip() == nullid: |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
274 if srvheadhashes != [nullid]: |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
275 return [nullid], True, srvheadhashes |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
276 return [nullid], False, [] |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
277 |
|
14206
2bf60f158ecb
setdiscovery: limit lines to 80 characters
Steven Brown <StevenGBrown@gmail.com>
parents:
14164
diff
changeset
|
278 # 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
|
279 # compatibility reasons) |
|
14164
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
280 ui.status(_("searching for changes\n")) |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
281 |
|
41883
82884bbf8d2b
discovery: rename `srvheads` to `knownsrvheads`
Georges Racinet <georges.racinet@octobus.net>
parents:
41303
diff
changeset
|
282 knownsrvheads = [] # revnos of remote heads that are known locally |
|
39194
858a12846f4f
setdiscovery: don't use dagutil for node -> rev conversion
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39192
diff
changeset
|
283 for node in srvheadhashes: |
|
858a12846f4f
setdiscovery: don't use dagutil for node -> rev conversion
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39192
diff
changeset
|
284 if node == nullid: |
|
858a12846f4f
setdiscovery: don't use dagutil for node -> rev conversion
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39192
diff
changeset
|
285 continue |
|
858a12846f4f
setdiscovery: don't use dagutil for node -> rev conversion
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39192
diff
changeset
|
286 |
|
858a12846f4f
setdiscovery: don't use dagutil for node -> rev conversion
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39192
diff
changeset
|
287 try: |
|
41883
82884bbf8d2b
discovery: rename `srvheads` to `knownsrvheads`
Georges Racinet <georges.racinet@octobus.net>
parents:
41303
diff
changeset
|
288 knownsrvheads.append(clrev(node)) |
|
39194
858a12846f4f
setdiscovery: don't use dagutil for node -> rev conversion
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39192
diff
changeset
|
289 # Catches unknown and filtered nodes. |
|
858a12846f4f
setdiscovery: don't use dagutil for node -> rev conversion
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39192
diff
changeset
|
290 except error.LookupError: |
|
858a12846f4f
setdiscovery: don't use dagutil for node -> rev conversion
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39192
diff
changeset
|
291 continue |
|
858a12846f4f
setdiscovery: don't use dagutil for node -> rev conversion
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39192
diff
changeset
|
292 |
|
41883
82884bbf8d2b
discovery: rename `srvheads` to `knownsrvheads`
Georges Racinet <georges.racinet@octobus.net>
parents:
41303
diff
changeset
|
293 if len(knownsrvheads) == len(srvheadhashes): |
|
14833
308e1b5acc87
discovery: quiet note about heads
Matt Mackall <mpm@selenic.com>
parents:
14624
diff
changeset
|
294 ui.debug("all remote heads known locally\n") |
|
39192
5b32b3c618b2
setdiscovery: don't use dagutil for rev -> node conversions
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38379
diff
changeset
|
295 return srvheadhashes, False, srvheadhashes |
|
14164
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
296 |
|
36739
bf485b70d0ae
setdiscovery: remove initialsamplesize from a condition
Martin von Zweigbergk <martinvonz@google.com>
parents:
36738
diff
changeset
|
297 if len(sample) == len(ownheads) and all(yesno): |
|
15497
9bea3aed6ee1
add missing localization markup
Mads Kiilerich <mads@kiilerich.com>
parents:
15063
diff
changeset
|
298 ui.note(_("all local heads known remotely\n")) |
|
39192
5b32b3c618b2
setdiscovery: don't use dagutil for rev -> node conversions
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38379
diff
changeset
|
299 ownheadhashes = [clnode(r) for r in ownheads] |
|
5b32b3c618b2
setdiscovery: don't use dagutil for rev -> node conversions
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38379
diff
changeset
|
300 return ownheadhashes, True, srvheadhashes |
|
14624
f03c82d1f50a
setdiscovery: batch heads and known(ownheads)
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
14206
diff
changeset
|
301 |
|
14164
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
302 # full blown discovery |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
303 |
|
41167
870a89c6909d
discovery: move undecided set on the partialdiscovery
Boris Feld <boris.feld@octobus.net>
parents:
41162
diff
changeset
|
304 disco = partialdiscovery(local, ownheads) |
|
23343
f8a2647fe020
setdiscovery: avoid a full changelog graph traversal
Siddharth Agarwal <sid0@fb.com>
parents:
23192
diff
changeset
|
305 # 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
|
306 # response |
|
41883
82884bbf8d2b
discovery: rename `srvheads` to `knownsrvheads`
Georges Racinet <georges.racinet@octobus.net>
parents:
41303
diff
changeset
|
307 disco.addcommons(knownsrvheads) |
|
41171
f46ffd23dae8
discovery: add a simple `addinfo` method
Boris Feld <boris.feld@octobus.net>
parents:
41170
diff
changeset
|
308 disco.addinfo(zip(sample, yesno)) |
| 16683 | 309 |
|
14624
f03c82d1f50a
setdiscovery: batch heads and known(ownheads)
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
14206
diff
changeset
|
310 full = False |
|
38356
9e70690a21ac
setdiscovery: use progress helper
Martin von Zweigbergk <martinvonz@google.com>
parents:
37631
diff
changeset
|
311 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
|
312 while not disco.iscomplete(): |
|
14164
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
313 |
|
41115
3023bc4b3da0
discovery: introduce a partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents:
41114
diff
changeset
|
314 if full or disco.hasinfo(): |
|
23747
f82173a90c2c
setdiscovery: factorize similar sampling code
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
23746
diff
changeset
|
315 if full: |
|
f82173a90c2c
setdiscovery: factorize similar sampling code
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
23746
diff
changeset
|
316 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
|
317 else: |
|
f82173a90c2c
setdiscovery: factorize similar sampling code
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
23746
diff
changeset
|
318 ui.debug("taking initial sample\n") |
|
41884
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
319 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
|
320 targetsize = fullsamplesize |
|
14624
f03c82d1f50a
setdiscovery: batch heads and known(ownheads)
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
14206
diff
changeset
|
321 else: |
|
f03c82d1f50a
setdiscovery: batch heads and known(ownheads)
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
14206
diff
changeset
|
322 # use even cheaper initial sample |
|
f03c82d1f50a
setdiscovery: batch heads and known(ownheads)
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
14206
diff
changeset
|
323 ui.debug("taking quick initial sample\n") |
|
41884
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
324 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
|
325 targetsize = initialsamplesize |
|
41884
e5ece0f46b40
discovery: moved sampling functions inside discovery object
Georges Racinet <georges.racinet@octobus.net>
parents:
41883
diff
changeset
|
326 sample = samplefunc(ownheads, targetsize) |
|
14164
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
327 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
328 roundtrips += 1 |
|
38356
9e70690a21ac
setdiscovery: use progress helper
Martin von Zweigbergk <martinvonz@google.com>
parents:
37631
diff
changeset
|
329 progress.update(roundtrips) |
|
14164
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
330 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
|
331 % (roundtrips, len(disco.undecided), len(sample))) |
|
14164
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
332 # indices between sample and externalized version must match |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
333 sample = list(sample) |
|
37630
e1b32dc4646c
wireproto: implement command executor interface for version 1 peers
Gregory Szorc <gregory.szorc@gmail.com>
parents:
36741
diff
changeset
|
334 |
|
e1b32dc4646c
wireproto: implement command executor interface for version 1 peers
Gregory Szorc <gregory.szorc@gmail.com>
parents:
36741
diff
changeset
|
335 with remote.commandexecutor() as e: |
|
e1b32dc4646c
wireproto: implement command executor interface for version 1 peers
Gregory Szorc <gregory.szorc@gmail.com>
parents:
36741
diff
changeset
|
336 yesno = e.callcommand('known', { |
|
39192
5b32b3c618b2
setdiscovery: don't use dagutil for rev -> node conversions
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38379
diff
changeset
|
337 '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:
36741
diff
changeset
|
338 }).result() |
|
e1b32dc4646c
wireproto: implement command executor interface for version 1 peers
Gregory Szorc <gregory.szorc@gmail.com>
parents:
36741
diff
changeset
|
339 |
|
14624
f03c82d1f50a
setdiscovery: batch heads and known(ownheads)
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
14206
diff
changeset
|
340 full = True |
|
14164
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
341 |
|
41171
f46ffd23dae8
discovery: add a simple `addinfo` method
Boris Feld <boris.feld@octobus.net>
parents:
41170
diff
changeset
|
342 disco.addinfo(zip(sample, yesno)) |
|
23343
f8a2647fe020
setdiscovery: avoid a full changelog graph traversal
Siddharth Agarwal <sid0@fb.com>
parents:
23192
diff
changeset
|
343 |
|
41116
9815d3337f9b
discovery: move common heads computation inside partialdiscovery object
Boris Feld <boris.feld@octobus.net>
parents:
41115
diff
changeset
|
344 result = disco.commonheads() |
|
32732
43bda143e3b2
discovery: include timing in the debug output
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
32331
diff
changeset
|
345 elapsed = util.timer() - start |
|
38379
ef692614e601
progress: hide update(None) in a new complete() method
Martin von Zweigbergk <martinvonz@google.com>
parents:
38356
diff
changeset
|
346 progress.complete() |
|
32732
43bda143e3b2
discovery: include timing in the debug output
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
32331
diff
changeset
|
347 ui.debug("%d total queries in %.4fs\n" % (roundtrips, elapsed)) |
|
32788
483d47753726
setdiscovery: improves logged message
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
32733
diff
changeset
|
348 msg = ('found %d common and %d unknown server heads,' |
|
483d47753726
setdiscovery: improves logged message
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
32733
diff
changeset
|
349 ' %d roundtrips in %.4fs\n') |
|
41883
82884bbf8d2b
discovery: rename `srvheads` to `knownsrvheads`
Georges Racinet <georges.racinet@octobus.net>
parents:
41303
diff
changeset
|
350 missing = set(result) - set(knownsrvheads) |
|
32788
483d47753726
setdiscovery: improves logged message
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
32733
diff
changeset
|
351 ui.log('discovery', msg, len(result), len(missing), roundtrips, |
|
32733
28240b75e880
discovery: log discovery result in non-trivial cases
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
32732
diff
changeset
|
352 elapsed) |
|
14164
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
353 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
354 if not result and srvheadhashes != [nullid]: |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
355 if abortwhenunrelated: |
|
26587
56b2bcea2529
error: get Abort from 'error' instead of 'util'
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
25973
diff
changeset
|
356 raise error.Abort(_("repository is unrelated")) |
|
14164
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
357 else: |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
358 ui.warn(_("warning: repository is unrelated\n")) |
|
32331
bd872f64a8ba
cleanup: use set literals
Martin von Zweigbergk <martinvonz@google.com>
parents:
28437
diff
changeset
|
359 return ({nullid}, True, srvheadhashes,) |
|
14164
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
360 |
|
14981
192e02680d09
setdiscovery: return anyincoming=False when remote's only head is nullid
Andrew Pritchard <andrewp@fogcreek.com>
parents:
14833
diff
changeset
|
361 anyincoming = (srvheadhashes != [nullid]) |
|
39192
5b32b3c618b2
setdiscovery: don't use dagutil for rev -> node conversions
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38379
diff
changeset
|
362 result = {clnode(r) for r in result} |
|
5b32b3c618b2
setdiscovery: don't use dagutil for rev -> node conversions
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38379
diff
changeset
|
363 return result, anyincoming, srvheadhashes |