( )⚙ D4316 setdiscovery: reflect use of revs instead of nodes

This is an archive of the discontinued Mercurial Phabricator instance.

Differential D4316

setdiscovery: reflect use of revs instead of nodes
ClosedPublic

Authored by indygreg on Aug 17 2018, 5:30 PM.

Details

Reviewers
None
Group Reviewers
hg-reviewers
Commits
rHG2d218db7389b: setdiscovery: reflect use of revs instead of nodes
Summary

This code all operates on revision numbers. Update variable names
and comments accordingly.

Diff Detail

Repository
rHG Mercurial
Lint
Lint Skipped
Unit
Unit Tests Skipped

Event Timeline

indygreg created this revision.Aug 17 2018, 5:30 PM
Closed by commit rHG2d218db7389b: setdiscovery: reflect use of revs instead of nodes (authored by indygreg). · Explain WhyAug 18 2018, 4:06 AM
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

PathPackages
Mmercurial/setdiscovery.py (34 lines)

Diff 10410

mercurial/setdiscovery.py

nullrev, nullrev,
) )
from . import ( from . import (
dagutil, dagutil,
error, error,
util, util,
) )
def _updatesample(dag, nodes, sample, quicksamplesize=0): def _updatesample(dag, revs, sample, quicksamplesize=0):
"""update an existing sample to match the expected size """update an existing sample to match the expected size
The sample is updated with nodes exponentially distant from each head of the The sample is updated with revs exponentially distant from each head of the
<nodes> set. (H~1, H~2, H~4, H~8, etc). <revs> set. (H~1, H~2, H~4, H~8, etc).
If a target size is specified, the sampling will stop once this size is If a target size is specified, the sampling will stop once this size is
reached. Otherwise sampling will happen until roots of the <nodes> set are reached. Otherwise sampling will happen until roots of the <revs> set are
reached. reached.
:dag: a dag object from dagutil :dag: a dag object from dagutil
:nodes: set of nodes we want to discover (if None, assume the whole dag) :revs: set of revs we want to discover (if None, assume the whole dag)
:sample: a sample to update :sample: a sample to update
:quicksamplesize: optional target size of the sample""" :quicksamplesize: optional target size of the sample"""
# if nodes is empty we scan the entire graph # if revs is empty we scan the entire graph
if nodes: if revs:
heads = dag.headsetofconnecteds(nodes) heads = dag.headsetofconnecteds(revs)
else: else:
heads = dag.heads() heads = dag.heads()
dist = {} dist = {}
visit = collections.deque(heads) visit = collections.deque(heads)
seen = set() seen = set()
factor = 1 factor = 1
while visit: while visit:
curr = visit.popleft() curr = visit.popleft()
if curr in seen: if curr in seen:
continue continue
d = dist.setdefault(curr, 1) d = dist.setdefault(curr, 1)
if d > factor: if d > factor:
factor *= 2 factor *= 2
if d == factor: if d == factor:
sample.add(curr) sample.add(curr)
if quicksamplesize and (len(sample) >= quicksamplesize): if quicksamplesize and (len(sample) >= quicksamplesize):
return return
seen.add(curr) seen.add(curr)
for p in dag.parents(curr): for p in dag.parents(curr):
if not nodes or p in nodes: if not revs or p in revs:
dist.setdefault(p, d + 1) dist.setdefault(p, d + 1)
visit.append(p) visit.append(p)
def _takequicksample(dag, nodes, size): def _takequicksample(dag, revs, size):
"""takes a quick sample of size <size> """takes a quick sample of size <size>
It is meant for initial sampling and focuses on querying heads and close It is meant for initial sampling and focuses on querying heads and close
ancestors of heads. ancestors of heads.
:dag: a dag object :dag: a dag object
:nodes: set of nodes to discover :revs: set of revs to discover
:size: the maximum size of the sample""" :size: the maximum size of the sample"""
sample = dag.headsetofconnecteds(nodes) sample = dag.headsetofconnecteds(revs)
if len(sample) >= size: if len(sample) >= size:
return _limitsample(sample, size) return _limitsample(sample, size)
_updatesample(dag, None, sample, quicksamplesize=size) _updatesample(dag, None, sample, quicksamplesize=size)
return sample return sample
def _takefullsample(dag, nodes, size): def _takefullsample(dag, revs, size):
sample = dag.headsetofconnecteds(nodes) sample = dag.headsetofconnecteds(revs)
# update from heads # update from heads
_updatesample(dag, nodes, sample) _updatesample(dag, revs, sample)
# update from roots # update from roots
_updatesample(dag.inverse(), nodes, sample) _updatesample(dag.inverse(), revs, sample)
assert sample assert sample
sample = _limitsample(sample, size) sample = _limitsample(sample, size)
if len(sample) < size: if len(sample) < size:
more = size - len(sample) more = size - len(sample)
sample.update(random.sample(list(nodes - sample), more)) sample.update(random.sample(list(revs - sample), more))
return sample return sample
def _limitsample(sample, desiredlen): def _limitsample(sample, desiredlen):
"""return a random subset of sample of at most desiredlen item""" """return a random subset of sample of at most desiredlen item"""
if len(sample) > desiredlen: if len(sample) > desiredlen:
sample = set(random.sample(sample, desiredlen)) sample = set(random.sample(sample, desiredlen))
return sample return sample