Mercurial > hg
comparison mercurial/setdiscovery.py @ 39168:2d218db7389b
setdiscovery: reflect use of revs instead of nodes
This code all operates on revision numbers. Update variable names
and comments accordingly.
Differential Revision: https://phab.mercurial-scm.org/D4316
| author | Gregory Szorc <gregory.szorc@gmail.com> |
|---|---|
| date | Fri, 17 Aug 2018 17:21:11 +0000 |
| parents | 484c9fe570a7 |
| children | 140992750187 |
comparison
equal
deleted
inserted
replaced
| 39167:136ed75bbe12 | 39168:2d218db7389b |
|---|---|
| 54 dagutil, | 54 dagutil, |
| 55 error, | 55 error, |
| 56 util, | 56 util, |
| 57 ) | 57 ) |
| 58 | 58 |
| 59 def _updatesample(dag, nodes, sample, quicksamplesize=0): | 59 def _updatesample(dag, revs, sample, quicksamplesize=0): |
| 60 """update an existing sample to match the expected size | 60 """update an existing sample to match the expected size |
| 61 | 61 |
| 62 The sample is updated with nodes exponentially distant from each head of the | 62 The sample is updated with revs exponentially distant from each head of the |
| 63 <nodes> set. (H~1, H~2, H~4, H~8, etc). | 63 <revs> set. (H~1, H~2, H~4, H~8, etc). |
| 64 | 64 |
| 65 If a target size is specified, the sampling will stop once this size is | 65 If a target size is specified, the sampling will stop once this size is |
| 66 reached. Otherwise sampling will happen until roots of the <nodes> set are | 66 reached. Otherwise sampling will happen until roots of the <revs> set are |
| 67 reached. | 67 reached. |
| 68 | 68 |
| 69 :dag: a dag object from dagutil | 69 :dag: a dag object from dagutil |
| 70 :nodes: set of nodes we want to discover (if None, assume the whole dag) | 70 :revs: set of revs we want to discover (if None, assume the whole dag) |
| 71 :sample: a sample to update | 71 :sample: a sample to update |
| 72 :quicksamplesize: optional target size of the sample""" | 72 :quicksamplesize: optional target size of the sample""" |
| 73 # if nodes is empty we scan the entire graph | 73 # if revs is empty we scan the entire graph |
| 74 if nodes: | 74 if revs: |
| 75 heads = dag.headsetofconnecteds(nodes) | 75 heads = dag.headsetofconnecteds(revs) |
| 76 else: | 76 else: |
| 77 heads = dag.heads() | 77 heads = dag.heads() |
| 78 dist = {} | 78 dist = {} |
| 79 visit = collections.deque(heads) | 79 visit = collections.deque(heads) |
| 80 seen = set() | 80 seen = set() |
| 90 sample.add(curr) | 90 sample.add(curr) |
| 91 if quicksamplesize and (len(sample) >= quicksamplesize): | 91 if quicksamplesize and (len(sample) >= quicksamplesize): |
| 92 return | 92 return |
| 93 seen.add(curr) | 93 seen.add(curr) |
| 94 for p in dag.parents(curr): | 94 for p in dag.parents(curr): |
| 95 if not nodes or p in nodes: | 95 if not revs or p in revs: |
| 96 dist.setdefault(p, d + 1) | 96 dist.setdefault(p, d + 1) |
| 97 visit.append(p) | 97 visit.append(p) |
| 98 | 98 |
| 99 def _takequicksample(dag, nodes, size): | 99 def _takequicksample(dag, revs, size): |
| 100 """takes a quick sample of size <size> | 100 """takes a quick sample of size <size> |
| 101 | 101 |
| 102 It is meant for initial sampling and focuses on querying heads and close | 102 It is meant for initial sampling and focuses on querying heads and close |
| 103 ancestors of heads. | 103 ancestors of heads. |
| 104 | 104 |
| 105 :dag: a dag object | 105 :dag: a dag object |
| 106 :nodes: set of nodes to discover | 106 :revs: set of revs to discover |
| 107 :size: the maximum size of the sample""" | 107 :size: the maximum size of the sample""" |
| 108 sample = dag.headsetofconnecteds(nodes) | 108 sample = dag.headsetofconnecteds(revs) |
| 109 if len(sample) >= size: | 109 if len(sample) >= size: |
| 110 return _limitsample(sample, size) | 110 return _limitsample(sample, size) |
| 111 _updatesample(dag, None, sample, quicksamplesize=size) | 111 _updatesample(dag, None, sample, quicksamplesize=size) |
| 112 return sample | 112 return sample |
| 113 | 113 |
| 114 def _takefullsample(dag, nodes, size): | 114 def _takefullsample(dag, revs, size): |
| 115 sample = dag.headsetofconnecteds(nodes) | 115 sample = dag.headsetofconnecteds(revs) |
| 116 # update from heads | 116 # update from heads |
| 117 _updatesample(dag, nodes, sample) | 117 _updatesample(dag, revs, sample) |
| 118 # update from roots | 118 # update from roots |
| 119 _updatesample(dag.inverse(), nodes, sample) | 119 _updatesample(dag.inverse(), revs, sample) |
| 120 assert sample | 120 assert sample |
| 121 sample = _limitsample(sample, size) | 121 sample = _limitsample(sample, size) |
| 122 if len(sample) < size: | 122 if len(sample) < size: |
| 123 more = size - len(sample) | 123 more = size - len(sample) |
| 124 sample.update(random.sample(list(nodes - sample), more)) | 124 sample.update(random.sample(list(revs - sample), more)) |
| 125 return sample | 125 return sample |
| 126 | 126 |
| 127 def _limitsample(sample, desiredlen): | 127 def _limitsample(sample, desiredlen): |
| 128 """return a random subset of sample of at most desiredlen item""" | 128 """return a random subset of sample of at most desiredlen item""" |
| 129 if len(sample) > desiredlen: | 129 if len(sample) > desiredlen: |