mercurial-scm/hg: mercurial/setdiscovery.py annotate

annotate mercurial/setdiscovery.py @ 41885:5baf06d2bb41

discovery: cache the children mapping used during each discovery During discovery, the `undecided` set keep shrinking. Therefore, the map computed for an iteration N will be valid for iteration N+1. Instead of computing the same data over and over we cache it the first time. Our private pathological case speed up from about 7.5 seconds to about 6.3 seconds. (starting from over 70s at the start of the full series)

author	Pierre-Yves David <pierre-yves.david@octobus.net>
date	Thu, 28 Feb 2019 01:48:20 +0100
parents	d5e6ae6e8012
children	a05f0bbefdd9

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()
41885 5baf06d2bb41 discovery: cache the children mapping used during each discovery Pierre-Yves David <pierre-yves.david@octobus.net> parents: 41884 diff changeset	119 self._childrenmap = None
41112 3023bc4b3da0 discovery: introduce a partialdiscovery object Boris Feld <boris.feld@octobus.net> parents: 41111 diff changeset	120
3023bc4b3da0 discovery: introduce a partialdiscovery object Boris Feld <boris.feld@octobus.net> parents: 41111 diff changeset	121 def addcommons(self, commons):
3023bc4b3da0 discovery: introduce a partialdiscovery object Boris Feld <boris.feld@octobus.net> parents: 41111 diff changeset	122 """registrer nodes known as common"""
3023bc4b3da0 discovery: introduce a partialdiscovery object Boris Feld <boris.feld@octobus.net> parents: 41111 diff changeset	123 self._common.addbases(commons)
41304 76873548b051 partialdiscovery: avoid `undecided` related computation sooner than necessary Boris Feld <boris.feld@octobus.net> parents: 41280 diff changeset	124 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	125 self._common.removeancestorsfrom(self._undecided)
41112 3023bc4b3da0 discovery: introduce a partialdiscovery object Boris Feld <boris.feld@octobus.net> parents: 41111 diff changeset	126
41170 96201120cdf5 discovery: move missing tracking inside the partialdiscovery object Boris Feld <boris.feld@octobus.net> parents: 41169 diff changeset	127 def addmissings(self, missings):
96201120cdf5 discovery: move missing tracking inside the partialdiscovery object Boris Feld <boris.feld@octobus.net> parents: 41169 diff changeset	128 """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	129 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	130 if newmissing:
f4277a35c42c discovery: compute newly discovered missing in a more efficient way Boris Feld <boris.feld@octobus.net> parents: 41245 diff changeset	131 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	132 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	133
41171 f46ffd23dae8 discovery: add a simple `addinfo` method Boris Feld <boris.feld@octobus.net> parents: 41170 diff changeset	134 def addinfo(self, sample):
f46ffd23dae8 discovery: add a simple `addinfo` method Boris Feld <boris.feld@octobus.net> parents: 41170 diff changeset	135 """consume an iterable of (rev, known) tuples"""
f46ffd23dae8 discovery: add a simple `addinfo` method Boris Feld <boris.feld@octobus.net> parents: 41170 diff changeset	136 common = set()
f46ffd23dae8 discovery: add a simple `addinfo` method Boris Feld <boris.feld@octobus.net> parents: 41170 diff changeset	137 missing = set()
f46ffd23dae8 discovery: add a simple `addinfo` method Boris Feld <boris.feld@octobus.net> parents: 41170 diff changeset	138 for rev, known in sample:
f46ffd23dae8 discovery: add a simple `addinfo` method Boris Feld <boris.feld@octobus.net> parents: 41170 diff changeset	139 if known:
f46ffd23dae8 discovery: add a simple `addinfo` method Boris Feld <boris.feld@octobus.net> parents: 41170 diff changeset	140 common.add(rev)
f46ffd23dae8 discovery: add a simple `addinfo` method Boris Feld <boris.feld@octobus.net> parents: 41170 diff changeset	141 else:
f46ffd23dae8 discovery: add a simple `addinfo` method Boris Feld <boris.feld@octobus.net> parents: 41170 diff changeset	142 missing.add(rev)
f46ffd23dae8 discovery: add a simple `addinfo` method Boris Feld <boris.feld@octobus.net> parents: 41170 diff changeset	143 if common:
f46ffd23dae8 discovery: add a simple `addinfo` method Boris Feld <boris.feld@octobus.net> parents: 41170 diff changeset	144 self.addcommons(common)
f46ffd23dae8 discovery: add a simple `addinfo` method Boris Feld <boris.feld@octobus.net> parents: 41170 diff changeset	145 if missing:
f46ffd23dae8 discovery: add a simple `addinfo` method Boris Feld <boris.feld@octobus.net> parents: 41170 diff changeset	146 self.addmissings(missing)
f46ffd23dae8 discovery: add a simple `addinfo` method Boris Feld <boris.feld@octobus.net> parents: 41170 diff changeset	147
41112 3023bc4b3da0 discovery: introduce a partialdiscovery object Boris Feld <boris.feld@octobus.net> parents: 41111 diff changeset	148 def hasinfo(self):
3023bc4b3da0 discovery: introduce a partialdiscovery object Boris Feld <boris.feld@octobus.net> parents: 41111 diff changeset	149 """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	150 return self._common.hasbases()
3023bc4b3da0 discovery: introduce a partialdiscovery object Boris Feld <boris.feld@octobus.net> parents: 41111 diff changeset	151
41169 3ce5b96482c6 discovery: add a `iscomplete` method to the `partialdiscovery` object Boris Feld <boris.feld@octobus.net> parents: 41168 diff changeset	152 def iscomplete(self):
3ce5b96482c6 discovery: add a `iscomplete` method to the `partialdiscovery` object Boris Feld <boris.feld@octobus.net> parents: 41168 diff changeset	153 """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	154 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	155
41167 870a89c6909d discovery: move undecided set on the partialdiscovery Boris Feld <boris.feld@octobus.net> parents: 41162 diff changeset	156 @property
870a89c6909d discovery: move undecided set on the partialdiscovery Boris Feld <boris.feld@octobus.net> parents: 41162 diff changeset	157 def undecided(self):
870a89c6909d discovery: move undecided set on the partialdiscovery Boris Feld <boris.feld@octobus.net> parents: 41162 diff changeset	158 if self._undecided is not None:
870a89c6909d discovery: move undecided set on the partialdiscovery Boris Feld <boris.feld@octobus.net> parents: 41162 diff changeset	159 return self._undecided
870a89c6909d discovery: move undecided set on the partialdiscovery Boris Feld <boris.feld@octobus.net> parents: 41162 diff changeset	160 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	161 return self._undecided
870a89c6909d discovery: move undecided set on the partialdiscovery Boris Feld <boris.feld@octobus.net> parents: 41162 diff changeset	162
41113 9815d3337f9b discovery: move common heads computation inside partialdiscovery object Boris Feld <boris.feld@octobus.net> parents: 41112 diff changeset	163 def commonheads(self):
9815d3337f9b discovery: move common heads computation inside partialdiscovery object Boris Feld <boris.feld@octobus.net> parents: 41112 diff changeset	164 """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	165 # 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	166 # common.bases and all its ancestors
41245 2a8782cc2e16 discovery: using the new basesheads() Georges Racinet <georges.racinet@octobus.net> parents: 41172 diff changeset	167 return self._common.basesheads()
41112 3023bc4b3da0 discovery: introduce a partialdiscovery object Boris Feld <boris.feld@octobus.net> parents: 41111 diff changeset	168
41881 e514799e4e07 discovery: use a lower level but faster way to retrieve parents Pierre-Yves David <pierre-yves.david@octobus.net> parents: 41880 diff changeset	169 def _parentsgetter(self):
e514799e4e07 discovery: use a lower level but faster way to retrieve parents Pierre-Yves David <pierre-yves.david@octobus.net> parents: 41880 diff changeset	170 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: 41880 diff changeset	171 def getparents(r):
e514799e4e07 discovery: use a lower level but faster way to retrieve parents Pierre-Yves David <pierre-yves.david@octobus.net> parents: 41880 diff changeset	172 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: 41880 diff changeset	173 return getparents
e514799e4e07 discovery: use a lower level but faster way to retrieve parents Pierre-Yves David <pierre-yves.david@octobus.net> parents: 41880 diff changeset	174
41884 d5e6ae6e8012 discovery: move children computation in its own method Pierre-Yves David <pierre-yves.david@octobus.net> parents: 41883 diff changeset	175 def _childrengetter(self, revs):
d5e6ae6e8012 discovery: move children computation in its own method Pierre-Yves David <pierre-yves.david@octobus.net> parents: 41883 diff changeset	176
41885 5baf06d2bb41 discovery: cache the children mapping used during each discovery Pierre-Yves David <pierre-yves.david@octobus.net> parents: 41884 diff changeset	177 if self._childrenmap is not None:
5baf06d2bb41 discovery: cache the children mapping used during each discovery Pierre-Yves David <pierre-yves.david@octobus.net> parents: 41884 diff changeset	178 return self._childrenmap.__getitem__
5baf06d2bb41 discovery: cache the children mapping used during each discovery Pierre-Yves David <pierre-yves.david@octobus.net> parents: 41884 diff changeset	179
41884 d5e6ae6e8012 discovery: move children computation in its own method Pierre-Yves David <pierre-yves.david@octobus.net> parents: 41883 diff changeset	180 # _updatesample() essentially does interaction over revisions to look
d5e6ae6e8012 discovery: move children computation in its own method Pierre-Yves David <pierre-yves.david@octobus.net> parents: 41883 diff changeset	181 # up their children. This lookup is expensive and doing it in a loop is
d5e6ae6e8012 discovery: move children computation in its own method Pierre-Yves David <pierre-yves.david@octobus.net> parents: 41883 diff changeset	182 # quadratic. We precompute the children for all relevant revisions and
d5e6ae6e8012 discovery: move children computation in its own method Pierre-Yves David <pierre-yves.david@octobus.net> parents: 41883 diff changeset	183 # make the lookup in _updatesample() a simple dict lookup.
41885 5baf06d2bb41 discovery: cache the children mapping used during each discovery Pierre-Yves David <pierre-yves.david@octobus.net> parents: 41884 diff changeset	184 self._childrenmap = children = {}
41884 d5e6ae6e8012 discovery: move children computation in its own method Pierre-Yves David <pierre-yves.david@octobus.net> parents: 41883 diff changeset	185
d5e6ae6e8012 discovery: move children computation in its own method Pierre-Yves David <pierre-yves.david@octobus.net> parents: 41883 diff changeset	186 parentrevs = self._parentsgetter()
d5e6ae6e8012 discovery: move children computation in its own method Pierre-Yves David <pierre-yves.david@octobus.net> parents: 41883 diff changeset	187
d5e6ae6e8012 discovery: move children computation in its own method Pierre-Yves David <pierre-yves.david@octobus.net> parents: 41883 diff changeset	188 for rev in sorted(revs):
d5e6ae6e8012 discovery: move children computation in its own method Pierre-Yves David <pierre-yves.david@octobus.net> parents: 41883 diff changeset	189 # Always ensure revision has an entry so we don't need to worry
d5e6ae6e8012 discovery: move children computation in its own method Pierre-Yves David <pierre-yves.david@octobus.net> parents: 41883 diff changeset	190 # about missing keys.
d5e6ae6e8012 discovery: move children computation in its own method Pierre-Yves David <pierre-yves.david@octobus.net> parents: 41883 diff changeset	191 children[rev] = []
d5e6ae6e8012 discovery: move children computation in its own method Pierre-Yves David <pierre-yves.david@octobus.net> parents: 41883 diff changeset	192 for prev in parentrevs(rev):
d5e6ae6e8012 discovery: move children computation in its own method Pierre-Yves David <pierre-yves.david@octobus.net> parents: 41883 diff changeset	193 if prev == nullrev:
d5e6ae6e8012 discovery: move children computation in its own method Pierre-Yves David <pierre-yves.david@octobus.net> parents: 41883 diff changeset	194 continue
d5e6ae6e8012 discovery: move children computation in its own method Pierre-Yves David <pierre-yves.david@octobus.net> parents: 41883 diff changeset	195 c = children.get(prev)
d5e6ae6e8012 discovery: move children computation in its own method Pierre-Yves David <pierre-yves.david@octobus.net> parents: 41883 diff changeset	196 if c is not None:
d5e6ae6e8012 discovery: move children computation in its own method Pierre-Yves David <pierre-yves.david@octobus.net> parents: 41883 diff changeset	197 c.append(rev)
d5e6ae6e8012 discovery: move children computation in its own method Pierre-Yves David <pierre-yves.david@octobus.net> parents: 41883 diff changeset	198 return children.__getitem__
d5e6ae6e8012 discovery: move children computation in its own method Pierre-Yves David <pierre-yves.david@octobus.net> parents: 41883 diff changeset	199
41879 e5ece0f46b40 discovery: moved sampling functions inside discovery object Georges Racinet <georges.racinet@octobus.net> parents: 41878 diff changeset	200 def takequicksample(self, headrevs, size):
e5ece0f46b40 discovery: moved sampling functions inside discovery object Georges Racinet <georges.racinet@octobus.net> parents: 41878 diff changeset	201 """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	202
e5ece0f46b40 discovery: moved sampling functions inside discovery object Georges Racinet <georges.racinet@octobus.net> parents: 41878 diff changeset	203 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	204 ancestors of heads.
e5ece0f46b40 discovery: moved sampling functions inside discovery object Georges Racinet <georges.racinet@octobus.net> parents: 41878 diff changeset	205
e5ece0f46b40 discovery: moved sampling functions inside discovery object Georges Racinet <georges.racinet@octobus.net> parents: 41878 diff changeset	206 :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	207 :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	208 revs = self.undecided
e5ece0f46b40 discovery: moved sampling functions inside discovery object Georges Racinet <georges.racinet@octobus.net> parents: 41878 diff changeset	209 if len(revs) <= size:
e5ece0f46b40 discovery: moved sampling functions inside discovery object Georges Racinet <georges.racinet@octobus.net> parents: 41878 diff changeset	210 return list(revs)
e5ece0f46b40 discovery: moved sampling functions inside discovery object Georges Racinet <georges.racinet@octobus.net> parents: 41878 diff changeset	211 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	212
e5ece0f46b40 discovery: moved sampling functions inside discovery object Georges Racinet <georges.racinet@octobus.net> parents: 41878 diff changeset	213 if len(sample) >= size:
e5ece0f46b40 discovery: moved sampling functions inside discovery object Georges Racinet <georges.racinet@octobus.net> parents: 41878 diff changeset	214 return _limitsample(sample, size)
e5ece0f46b40 discovery: moved sampling functions inside discovery object Georges Racinet <georges.racinet@octobus.net> parents: 41878 diff changeset	215
41881 e514799e4e07 discovery: use a lower level but faster way to retrieve parents Pierre-Yves David <pierre-yves.david@octobus.net> parents: 41880 diff changeset	216 _updatesample(None, headrevs, sample, self._parentsgetter(),
41879 e5ece0f46b40 discovery: moved sampling functions inside discovery object Georges Racinet <georges.racinet@octobus.net> parents: 41878 diff changeset	217 quicksamplesize=size)
e5ece0f46b40 discovery: moved sampling functions inside discovery object Georges Racinet <georges.racinet@octobus.net> parents: 41878 diff changeset	218 return sample
e5ece0f46b40 discovery: moved sampling functions inside discovery object Georges Racinet <georges.racinet@octobus.net> parents: 41878 diff changeset	219
e5ece0f46b40 discovery: moved sampling functions inside discovery object Georges Racinet <georges.racinet@octobus.net> parents: 41878 diff changeset	220 def takefullsample(self, headrevs, size):
e5ece0f46b40 discovery: moved sampling functions inside discovery object Georges Racinet <georges.racinet@octobus.net> parents: 41878 diff changeset	221 revs = self.undecided
e5ece0f46b40 discovery: moved sampling functions inside discovery object Georges Racinet <georges.racinet@octobus.net> parents: 41878 diff changeset	222 if len(revs) <= size:
e5ece0f46b40 discovery: moved sampling functions inside discovery object Georges Racinet <georges.racinet@octobus.net> parents: 41878 diff changeset	223 return list(revs)
e5ece0f46b40 discovery: moved sampling functions inside discovery object Georges Racinet <georges.racinet@octobus.net> parents: 41878 diff changeset	224 repo = self._repo
e5ece0f46b40 discovery: moved sampling functions inside discovery object Georges Racinet <georges.racinet@octobus.net> parents: 41878 diff changeset	225 sample = set(repo.revs('heads(%ld)', revs))
41881 e514799e4e07 discovery: use a lower level but faster way to retrieve parents Pierre-Yves David <pierre-yves.david@octobus.net> parents: 41880 diff changeset	226 parentrevs = self._parentsgetter()
41879 e5ece0f46b40 discovery: moved sampling functions inside discovery object Georges Racinet <georges.racinet@octobus.net> parents: 41878 diff changeset	227
e5ece0f46b40 discovery: moved sampling functions inside discovery object Georges Racinet <georges.racinet@octobus.net> parents: 41878 diff changeset	228 # update from heads
41880 55919b96c02a discovery: avoid computing identical sets of heads twice Pierre-Yves David <pierre-yves.david@octobus.net> parents: 41879 diff changeset	229 revsheads = sample.copy()
41881 e514799e4e07 discovery: use a lower level but faster way to retrieve parents Pierre-Yves David <pierre-yves.david@octobus.net> parents: 41880 diff changeset	230 _updatesample(revs, revsheads, sample, parentrevs)
41879 e5ece0f46b40 discovery: moved sampling functions inside discovery object Georges Racinet <georges.racinet@octobus.net> parents: 41878 diff changeset	231
e5ece0f46b40 discovery: moved sampling functions inside discovery object Georges Racinet <georges.racinet@octobus.net> parents: 41878 diff changeset	232 # update from roots
e5ece0f46b40 discovery: moved sampling functions inside discovery object Georges Racinet <georges.racinet@octobus.net> parents: 41878 diff changeset	233 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	234
41884 d5e6ae6e8012 discovery: move children computation in its own method Pierre-Yves David <pierre-yves.david@octobus.net> parents: 41883 diff changeset	235 childrenrevs = self._childrengetter(revs)
41879 e5ece0f46b40 discovery: moved sampling functions inside discovery object Georges Racinet <georges.racinet@octobus.net> parents: 41878 diff changeset	236
41884 d5e6ae6e8012 discovery: move children computation in its own method Pierre-Yves David <pierre-yves.david@octobus.net> parents: 41883 diff changeset	237 _updatesample(revs, revsroots, sample, childrenrevs)
41879 e5ece0f46b40 discovery: moved sampling functions inside discovery object Georges Racinet <georges.racinet@octobus.net> parents: 41878 diff changeset	238 assert sample
e5ece0f46b40 discovery: moved sampling functions inside discovery object Georges Racinet <georges.racinet@octobus.net> parents: 41878 diff changeset	239 sample = _limitsample(sample, size)
e5ece0f46b40 discovery: moved sampling functions inside discovery object Georges Racinet <georges.racinet@octobus.net> parents: 41878 diff changeset	240 if len(sample) < size:
e5ece0f46b40 discovery: moved sampling functions inside discovery object Georges Racinet <georges.racinet@octobus.net> parents: 41878 diff changeset	241 more = size - len(sample)
e5ece0f46b40 discovery: moved sampling functions inside discovery object Georges Racinet <georges.racinet@octobus.net> parents: 41878 diff changeset	242 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	243 return sample
e5ece0f46b40 discovery: moved sampling functions inside discovery object Georges Racinet <georges.racinet@octobus.net> parents: 41878 diff changeset	244
36715 613954a17a25 setdiscovery: back out changeset 5cfdf6137af8 (issue5809) Martin von Zweigbergk <martinvonz@google.com> parents: 35849 diff changeset	245 def findcommonheads(ui, local, remote,
14164 cb98fed52495 discovery: add new set-based discovery Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: diff changeset	246 initialsamplesize=100,
cb98fed52495 discovery: add new set-based discovery Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: diff changeset	247 fullsamplesize=200,
35304 f77121b6bf1b setdiscover: allow to ignore part of the local graph Boris Feld <boris.feld@octobus.net> parents: 32768 diff changeset	248 abortwhenunrelated=True,
f77121b6bf1b setdiscover: allow to ignore part of the local graph Boris Feld <boris.feld@octobus.net> parents: 32768 diff changeset	249 ancestorsof=None):
14206 2bf60f158ecb setdiscovery: limit lines to 80 characters Steven Brown <StevenGBrown@gmail.com> parents: 14164 diff changeset	250 '''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	251 missing nodes from or in remote.
14164 cb98fed52495 discovery: add new set-based discovery Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: diff changeset	252 '''
32712 43bda143e3b2 discovery: include timing in the debug output Pierre-Yves David <pierre-yves.david@octobus.net> parents: 32291 diff changeset	253 start = util.timer()
43bda143e3b2 discovery: include timing in the debug output Pierre-Yves David <pierre-yves.david@octobus.net> parents: 32291 diff changeset	254
14164 cb98fed52495 discovery: add new set-based discovery Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: diff changeset	255 roundtrips = 0
cb98fed52495 discovery: add new set-based discovery Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: diff changeset	256 cl = local.changelog
39159 5b32b3c618b2 setdiscovery: don't use dagutil for rev -> node conversions Gregory Szorc <gregory.szorc@gmail.com> parents: 38373 diff changeset	257 clnode = cl.node
39161 858a12846f4f setdiscovery: don't use dagutil for node -> rev conversion Gregory Szorc <gregory.szorc@gmail.com> parents: 39159 diff changeset	258 clrev = cl.rev
39159 5b32b3c618b2 setdiscovery: don't use dagutil for rev -> node conversions Gregory Szorc <gregory.szorc@gmail.com> parents: 38373 diff changeset	259
35304 f77121b6bf1b setdiscover: allow to ignore part of the local graph Boris Feld <boris.feld@octobus.net> parents: 32768 diff changeset	260 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	261 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	262 else:
860e83cd97de setdiscovery: don't use dagutil to compute heads Gregory Szorc <gregory.szorc@gmail.com> parents: 39161 diff changeset	263 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	264
14624 f03c82d1f50a setdiscovery: batch heads and known(ownheads) Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 14206 diff changeset	265 # 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	266 ui.debug("query 1; heads\n")
cb98fed52495 discovery: add new set-based discovery Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: diff changeset	267 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	268 sample = _limitsample(ownheads, initialsamplesize)
23192 73cfaa348650 discovery: indices between sample and yesno must match (issue4438) Mads Kiilerich <madski@unity3d.com> parents: 23191 diff changeset	269 # 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	270 sample = list(sample)
37631 2f626233859b wireproto: implement batching on peer executor interface Gregory Szorc <gregory.szorc@gmail.com> parents: 37630 diff changeset	271
2f626233859b wireproto: implement batching on peer executor interface Gregory Szorc <gregory.szorc@gmail.com> parents: 37630 diff changeset	272 with remote.commandexecutor() as e:
2f626233859b wireproto: implement batching on peer executor interface Gregory Szorc <gregory.szorc@gmail.com> parents: 37630 diff changeset	273 fheads = e.callcommand('heads', {})
2f626233859b wireproto: implement batching on peer executor interface Gregory Szorc <gregory.szorc@gmail.com> parents: 37630 diff changeset	274 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	275 '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	276 })
2f626233859b wireproto: implement batching on peer executor interface Gregory Szorc <gregory.szorc@gmail.com> parents: 37630 diff changeset	277
2f626233859b wireproto: implement batching on peer executor interface Gregory Szorc <gregory.szorc@gmail.com> parents: 37630 diff changeset	278 srvheadhashes, yesno = fheads.result(), fknown.result()
14164 cb98fed52495 discovery: add new set-based discovery Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: diff changeset	279
cb98fed52495 discovery: add new set-based discovery Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: diff changeset	280 if cl.tip() == nullid:
cb98fed52495 discovery: add new set-based discovery Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: diff changeset	281 if srvheadhashes != [nullid]:
cb98fed52495 discovery: add new set-based discovery Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: diff changeset	282 return [nullid], True, srvheadhashes
cb98fed52495 discovery: add new set-based discovery Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: diff changeset	283 return [nullid], False, []
cb98fed52495 discovery: add new set-based discovery Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: diff changeset	284
14206 2bf60f158ecb setdiscovery: limit lines to 80 characters Steven Brown <StevenGBrown@gmail.com> parents: 14164 diff changeset	285 # 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	286 # compatibility reasons)
14164 cb98fed52495 discovery: add new set-based discovery Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: diff changeset	287 ui.status(_("searching for changes\n"))
cb98fed52495 discovery: add new set-based discovery Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: diff changeset	288
41878 82884bbf8d2b discovery: rename `srvheads` to `knownsrvheads` Georges Racinet <georges.racinet@octobus.net> parents: 41304 diff changeset	289 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	290 for node in srvheadhashes:
858a12846f4f setdiscovery: don't use dagutil for node -> rev conversion Gregory Szorc <gregory.szorc@gmail.com> parents: 39159 diff changeset	291 if node == nullid:
858a12846f4f setdiscovery: don't use dagutil for node -> rev conversion Gregory Szorc <gregory.szorc@gmail.com> parents: 39159 diff changeset	292 continue
858a12846f4f setdiscovery: don't use dagutil for node -> rev conversion Gregory Szorc <gregory.szorc@gmail.com> parents: 39159 diff changeset	293
858a12846f4f setdiscovery: don't use dagutil for node -> rev conversion Gregory Szorc <gregory.szorc@gmail.com> parents: 39159 diff changeset	294 try:
41878 82884bbf8d2b discovery: rename `srvheads` to `knownsrvheads` Georges Racinet <georges.racinet@octobus.net> parents: 41304 diff changeset	295 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	296 # 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	297 except error.LookupError:
858a12846f4f setdiscovery: don't use dagutil for node -> rev conversion Gregory Szorc <gregory.szorc@gmail.com> parents: 39159 diff changeset	298 continue
858a12846f4f setdiscovery: don't use dagutil for node -> rev conversion Gregory Szorc <gregory.szorc@gmail.com> parents: 39159 diff changeset	299
41878 82884bbf8d2b discovery: rename `srvheads` to `knownsrvheads` Georges Racinet <georges.racinet@octobus.net> parents: 41304 diff changeset	300 if len(knownsrvheads) == len(srvheadhashes):
14833 308e1b5acc87 discovery: quiet note about heads Matt Mackall <mpm@selenic.com> parents: 14624 diff changeset	301 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	302 return srvheadhashes, False, srvheadhashes
14164 cb98fed52495 discovery: add new set-based discovery Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: diff changeset	303
36716 bf485b70d0ae setdiscovery: remove initialsamplesize from a condition Martin von Zweigbergk <martinvonz@google.com> parents: 36715 diff changeset	304 if len(sample) == len(ownheads) and all(yesno):
15497 9bea3aed6ee1 add missing localization markup Mads Kiilerich <mads@kiilerich.com> parents: 15063 diff changeset	305 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	306 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	307 return ownheadhashes, True, srvheadhashes
14624 f03c82d1f50a setdiscovery: batch heads and known(ownheads) Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 14206 diff changeset	308
14164 cb98fed52495 discovery: add new set-based discovery Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: diff changeset	309 # full blown discovery
cb98fed52495 discovery: add new set-based discovery Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: diff changeset	310
41167 870a89c6909d discovery: move undecided set on the partialdiscovery Boris Feld <boris.feld@octobus.net> parents: 41162 diff changeset	311 disco = partialdiscovery(local, ownheads)
23343 f8a2647fe020 setdiscovery: avoid a full changelog graph traversal Siddharth Agarwal <sid0@fb.com> parents: 23192 diff changeset	312 # 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	313 # response
41878 82884bbf8d2b discovery: rename `srvheads` to `knownsrvheads` Georges Racinet <georges.racinet@octobus.net> parents: 41304 diff changeset	314 disco.addcommons(knownsrvheads)
41171 f46ffd23dae8 discovery: add a simple `addinfo` method Boris Feld <boris.feld@octobus.net> parents: 41170 diff changeset	315 disco.addinfo(zip(sample, yesno))
16683 525fdb738975 cleanup: eradicate long lines Brodie Rao <brodie@sf.io> parents: 15713 diff changeset	316
14624 f03c82d1f50a setdiscovery: batch heads and known(ownheads) Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 14206 diff changeset	317 full = False
38350 9e70690a21ac setdiscovery: use progress helper Martin von Zweigbergk <martinvonz@google.com> parents: 37631 diff changeset	318 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	319 while not disco.iscomplete():
14164 cb98fed52495 discovery: add new set-based discovery Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: diff changeset	320
41112 3023bc4b3da0 discovery: introduce a partialdiscovery object Boris Feld <boris.feld@octobus.net> parents: 41111 diff changeset	321 if full or disco.hasinfo():
23747 f82173a90c2c setdiscovery: factorize similar sampling code Pierre-Yves David <pierre-yves.david@fb.com> parents: 23746 diff changeset	322 if full:
f82173a90c2c setdiscovery: factorize similar sampling code Pierre-Yves David <pierre-yves.david@fb.com> parents: 23746 diff changeset	323 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	324 else:
f82173a90c2c setdiscovery: factorize similar sampling code Pierre-Yves David <pierre-yves.david@fb.com> parents: 23746 diff changeset	325 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	326 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	327 targetsize = fullsamplesize
14624 f03c82d1f50a setdiscovery: batch heads and known(ownheads) Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 14206 diff changeset	328 else:
f03c82d1f50a setdiscovery: batch heads and known(ownheads) Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 14206 diff changeset	329 # use even cheaper initial sample
f03c82d1f50a setdiscovery: batch heads and known(ownheads) Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 14206 diff changeset	330 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	331 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	332 targetsize = initialsamplesize
41879 e5ece0f46b40 discovery: moved sampling functions inside discovery object Georges Racinet <georges.racinet@octobus.net> parents: 41878 diff changeset	333 sample = samplefunc(ownheads, targetsize)
14164 cb98fed52495 discovery: add new set-based discovery Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: diff changeset	334
cb98fed52495 discovery: add new set-based discovery Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: diff changeset	335 roundtrips += 1
38350 9e70690a21ac setdiscovery: use progress helper Martin von Zweigbergk <martinvonz@google.com> parents: 37631 diff changeset	336 progress.update(roundtrips)
14164 cb98fed52495 discovery: add new set-based discovery Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: diff changeset	337 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	338 % (roundtrips, len(disco.undecided), len(sample)))
14164 cb98fed52495 discovery: add new set-based discovery Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: diff changeset	339 # indices between sample and externalized version must match
cb98fed52495 discovery: add new set-based discovery Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: diff changeset	340 sample = list(sample)
37630 e1b32dc4646c wireproto: implement command executor interface for version 1 peers Gregory Szorc <gregory.szorc@gmail.com> parents: 36718 diff changeset	341
e1b32dc4646c wireproto: implement command executor interface for version 1 peers Gregory Szorc <gregory.szorc@gmail.com> parents: 36718 diff changeset	342 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	343 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	344 '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	345 }).result()
e1b32dc4646c wireproto: implement command executor interface for version 1 peers Gregory Szorc <gregory.szorc@gmail.com> parents: 36718 diff changeset	346
14624 f03c82d1f50a setdiscovery: batch heads and known(ownheads) Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 14206 diff changeset	347 full = True
14164 cb98fed52495 discovery: add new set-based discovery Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: diff changeset	348
41171 f46ffd23dae8 discovery: add a simple `addinfo` method Boris Feld <boris.feld@octobus.net> parents: 41170 diff changeset	349 disco.addinfo(zip(sample, yesno))
23343 f8a2647fe020 setdiscovery: avoid a full changelog graph traversal Siddharth Agarwal <sid0@fb.com> parents: 23192 diff changeset	350
41113 9815d3337f9b discovery: move common heads computation inside partialdiscovery object Boris Feld <boris.feld@octobus.net> parents: 41112 diff changeset	351 result = disco.commonheads()
32712 43bda143e3b2 discovery: include timing in the debug output Pierre-Yves David <pierre-yves.david@octobus.net> parents: 32291 diff changeset	352 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	353 progress.complete()
32712 43bda143e3b2 discovery: include timing in the debug output Pierre-Yves David <pierre-yves.david@octobus.net> parents: 32291 diff changeset	354 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	355 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	356 ' %d roundtrips in %.4fs\n')
41878 82884bbf8d2b discovery: rename `srvheads` to `knownsrvheads` Georges Racinet <georges.racinet@octobus.net> parents: 41304 diff changeset	357 missing = set(result) - set(knownsrvheads)
32768 483d47753726 setdiscovery: improves logged message Pierre-Yves David <pierre-yves.david@octobus.net> parents: 32713 diff changeset	358 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	359 elapsed)
14164 cb98fed52495 discovery: add new set-based discovery Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: diff changeset	360
cb98fed52495 discovery: add new set-based discovery Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: diff changeset	361 if not result and srvheadhashes != [nullid]:
cb98fed52495 discovery: add new set-based discovery Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: diff changeset	362 if abortwhenunrelated:
26587 56b2bcea2529 error: get Abort from 'error' instead of 'util' Pierre-Yves David <pierre-yves.david@fb.com> parents: 25973 diff changeset	363 raise error.Abort(_("repository is unrelated"))
14164 cb98fed52495 discovery: add new set-based discovery Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: diff changeset	364 else:
cb98fed52495 discovery: add new set-based discovery Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: diff changeset	365 ui.warn(_("warning: repository is unrelated\n"))
32291 bd872f64a8ba cleanup: use set literals Martin von Zweigbergk <martinvonz@google.com> parents: 28437 diff changeset	366 return ({nullid}, True, srvheadhashes,)
14164 cb98fed52495 discovery: add new set-based discovery Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: diff changeset	367
14981 192e02680d09 setdiscovery: return anyincoming=False when remote's only head is nullid Andrew Pritchard <andrewp@fogcreek.com> parents: 14833 diff changeset	368 anyincoming = (srvheadhashes != [nullid])
39159 5b32b3c618b2 setdiscovery: don't use dagutil for rev -> node conversions Gregory Szorc <gregory.szorc@gmail.com> parents: 38373 diff changeset	369 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	370 return result, anyincoming, srvheadhashes

Mercurial > public > mercurial-scm > hg

annotate mercurial/setdiscovery.py @ 41885:5baf06d2bb41