| hg-reviewers |
This code all operates on revision numbers. Update variable names
and comments accordingly.
| Automatic diff as part of commit; lint not applicable. |
| Automatic diff as part of commit; unit tests not applicable. |
| Path | Packages | |||
|---|---|---|---|---|
| M | mercurial/setdiscovery.py (34 lines) |
| Status | Author | Revision | |
|---|---|---|---|
| Closed | indygreg | D4330 dagutil: remove module | |
| Closed | indygreg | ||
| Closed | indygreg | ||
| Closed | indygreg | ||
| Closed | indygreg | ||
| Closed | indygreg | ||
| Closed | indygreg | ||
| Closed | indygreg | ||
| Closed | indygreg | ||
| Closed | indygreg | ||
| Closed | indygreg | ||
| Closed | indygreg | ||
| Closed | indygreg | ||
| Closed | indygreg | ||
| Closed | indygreg | ||
| Closed | indygreg | ||
| Closed | indygreg | ||
| Closed | indygreg | ||
| Closed | indygreg | ||
| Closed | indygreg | ||
| Closed | indygreg | ||
| Closed | indygreg | ||
| Closed | indygreg | ||
| Closed | indygreg | ||
| Closed | indygreg |
| 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 | ||||