Mercurial > hg
annotate mercurial/pvec.py @ 47279:40b51c28b242
dirstate-v2: Update the expected output of some tests for new requirement
Fix most test failures (except in test-narrow-debugrebuilddirstate.t and
test-upgrade-repo.t) caused by the new entry in config or in .hg/requires
when running `run-tests.py --extra-config-opt format.exp-dirstate-v2=1`
There is no CI so far for this configuration.
Differential Revision: https://phab.mercurial-scm.org/D10718
author | Simon Sapin <simon.sapin@octobus.net> |
---|---|
date | Wed, 19 May 2021 13:15:00 +0200 |
parents | d4ba4d51f85f |
children | 6000f5b25c9b |
rev | line source |
---|---|
16249 | 1 # pvec.py - probabilistic vector clocks for Mercurial |
2 # | |
46819
d4ba4d51f85f
contributor: change mentions of mpm to olivia
Raphaël Gomès <rgomes@octobus.net>
parents:
44602
diff
changeset
|
3 # Copyright 2012 Olivia Mackall <olivia@selenic.com> |
16249 | 4 # |
5 # This software may be used and distributed according to the terms of the | |
6 # GNU General Public License version 2 or any later version. | |
7 | |
8 ''' | |
9 A "pvec" is a changeset property based on the theory of vector clocks | |
10 that can be compared to discover relatedness without consulting a | |
11 graph. This can be useful for tasks like determining how a | |
12 disconnected patch relates to a repository. | |
13 | |
14 Currently a pvec consist of 448 bits, of which 24 are 'depth' and the | |
15 remainder are a bit vector. It is represented as a 70-character base85 | |
16 string. | |
17 | |
18 Construction: | |
19 | |
20 - a root changeset has a depth of 0 and a bit vector based on its hash | |
21 - a normal commit has a changeset where depth is increased by one and | |
22 one bit vector bit is flipped based on its hash | |
23 - a merge changeset pvec is constructed by copying changes from one pvec into | |
24 the other to balance its depth | |
25 | |
26 Properties: | |
27 | |
28 - for linear changes, difference in depth is always <= hamming distance | |
29 - otherwise, changes are probably divergent | |
30 - when hamming distance is < 200, we can reliably detect when pvecs are near | |
31 | |
32 Issues: | |
33 | |
34 - hamming distance ceases to work over distances of ~ 200 | |
35 - detecting divergence is less accurate when the common ancestor is very close | |
36 to either revision or total distance is high | |
37 - this could probably be improved by modeling the relation between | |
38 delta and hdist | |
39 | |
40 Uses: | |
41 | |
42 - a patch pvec can be used to locate the nearest available common ancestor for | |
43 resolving conflicts | |
44 - ordering of patches can be established without a DAG | |
45 - two head pvecs can be compared to determine whether push/pull/merge is needed | |
46 and approximately how many changesets are involved | |
47 - can be used to find a heuristic divergence measure between changesets on | |
48 different branches | |
49 ''' | |
50 | |
44602
a89aa2d7b34d
pvec: drop an unused `from __future__ import division`
Martin von Zweigbergk <martinvonz@google.com>
parents:
43793
diff
changeset
|
51 from __future__ import absolute_import |
27501
983e93d88193
pvec: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
24339
diff
changeset
|
52 |
983e93d88193
pvec: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
24339
diff
changeset
|
53 from .node import nullrev |
983e93d88193
pvec: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
24339
diff
changeset
|
54 from . import ( |
38783
e7aa113b14f7
global: use pycompat.xrange()
Gregory Szorc <gregory.szorc@gmail.com>
parents:
32201
diff
changeset
|
55 pycompat, |
27501
983e93d88193
pvec: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
24339
diff
changeset
|
56 util, |
983e93d88193
pvec: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
24339
diff
changeset
|
57 ) |
16249 | 58 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
38783
diff
changeset
|
59 _size = 448 # 70 chars b85-encoded |
43465
90aac60b6697
pvec: migrate to modern integer division
Augie Fackler <augie@google.com>
parents:
43463
diff
changeset
|
60 _bytes = _size // 8 |
16249 | 61 _depthbits = 24 |
43465
90aac60b6697
pvec: migrate to modern integer division
Augie Fackler <augie@google.com>
parents:
43463
diff
changeset
|
62 _depthbytes = _depthbits // 8 |
16249 | 63 _vecbytes = _bytes - _depthbytes |
64 _vecbits = _vecbytes * 8 | |
43465
90aac60b6697
pvec: migrate to modern integer division
Augie Fackler <augie@google.com>
parents:
43463
diff
changeset
|
65 _radius = (_vecbits - 30) // 2 # high probability vectors are related |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
38783
diff
changeset
|
66 |
16249 | 67 |
68 def _bin(bs): | |
69 '''convert a bytestring to a long''' | |
70 v = 0 | |
71 for b in bs: | |
72 v = v * 256 + ord(b) | |
73 return v | |
74 | |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
38783
diff
changeset
|
75 |
16249 | 76 def _str(v, l): |
43479
8e89b6e1e0cd
pvec: add an explicit type hint to help pytype
Augie Fackler <augie@google.com>
parents:
43465
diff
changeset
|
77 # type: (int, int) -> bytes |
43077
687b865b95ad
formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents:
43076
diff
changeset
|
78 bs = b"" |
38783
e7aa113b14f7
global: use pycompat.xrange()
Gregory Szorc <gregory.szorc@gmail.com>
parents:
32201
diff
changeset
|
79 for p in pycompat.xrange(l): |
43463
271af23d01a9
pvec: fix overlooked chr() call
Augie Fackler <augie@google.com>
parents:
43115
diff
changeset
|
80 bs = pycompat.bytechr(v & 255) + bs |
16249 | 81 v >>= 8 |
82 return bs | |
83 | |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
38783
diff
changeset
|
84 |
16249 | 85 def _split(b): |
86 '''depth and bitvec''' | |
87 return _bin(b[:_depthbytes]), _bin(b[_depthbytes:]) | |
88 | |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
38783
diff
changeset
|
89 |
16249 | 90 def _join(depth, bitvec): |
91 return _str(depth, _depthbytes) + _str(bitvec, _vecbytes) | |
92 | |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
38783
diff
changeset
|
93 |
16249 | 94 def _hweight(x): |
95 c = 0 | |
96 while x: | |
97 if x & 1: | |
98 c += 1 | |
99 x >>= 1 | |
100 return c | |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
38783
diff
changeset
|
101 |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
38783
diff
changeset
|
102 |
38783
e7aa113b14f7
global: use pycompat.xrange()
Gregory Szorc <gregory.szorc@gmail.com>
parents:
32201
diff
changeset
|
103 _htab = [_hweight(x) for x in pycompat.xrange(256)] |
16249 | 104 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
38783
diff
changeset
|
105 |
16249 | 106 def _hamming(a, b): |
107 '''find the hamming distance between two longs''' | |
108 d = a ^ b | |
109 c = 0 | |
110 while d: | |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
38783
diff
changeset
|
111 c += _htab[d & 0xFF] |
16249 | 112 d >>= 8 |
113 return c | |
114 | |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
38783
diff
changeset
|
115 |
16249 | 116 def _mergevec(x, y, c): |
117 # Ideally, this function would be x ^ y ^ ancestor, but finding | |
118 # ancestors is a nuisance. So instead we find the minimal number | |
119 # of changes to balance the depth and hamming distance | |
120 | |
121 d1, v1 = x | |
122 d2, v2 = y | |
123 if d1 < d2: | |
124 d1, d2, v1, v2 = d2, d1, v2, v1 | |
125 | |
126 hdist = _hamming(v1, v2) | |
127 ddist = d1 - d2 | |
128 v = v1 | |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
38783
diff
changeset
|
129 m = v1 ^ v2 # mask of different bits |
16249 | 130 i = 1 |
131 | |
132 if hdist > ddist: | |
133 # if delta = 10 and hdist = 100, then we need to go up 55 steps | |
134 # to the ancestor and down 45 | |
43465
90aac60b6697
pvec: migrate to modern integer division
Augie Fackler <augie@google.com>
parents:
43463
diff
changeset
|
135 changes = (hdist - ddist + 1) // 2 |
16249 | 136 else: |
137 # must make at least one change | |
138 changes = 1 | |
139 depth = d1 + changes | |
140 | |
141 # copy changes from v2 | |
142 if m: | |
143 while changes: | |
144 if m & i: | |
145 v ^= i | |
146 changes -= 1 | |
147 i <<= 1 | |
148 else: | |
149 v = _flipbit(v, c) | |
150 | |
151 return depth, v | |
152 | |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
38783
diff
changeset
|
153 |
16249 | 154 def _flipbit(v, node): |
155 # converting bit strings to longs is slow | |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
38783
diff
changeset
|
156 bit = (hash(node) & 0xFFFFFFFF) % _vecbits |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
38783
diff
changeset
|
157 return v ^ (1 << bit) |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
38783
diff
changeset
|
158 |
16249 | 159 |
160 def ctxpvec(ctx): | |
161 '''construct a pvec for ctx while filling in the cache''' | |
24339
bcc319d936a3
pvec: replace 'ctx._repo' with 'ctx.repo()'
Matt Harbison <matt_harbison@yahoo.com>
parents:
18918
diff
changeset
|
162 r = ctx.repo() |
43115
4aa72cdf616f
py3: delete b'' prefix from safehasattr arguments
Martin von Zweigbergk <martinvonz@google.com>
parents:
43077
diff
changeset
|
163 if not util.safehasattr(r, "_pveccache"): |
16249 | 164 r._pveccache = {} |
165 pvc = r._pveccache | |
166 if ctx.rev() not in pvc: | |
167 cl = r.changelog | |
38783
e7aa113b14f7
global: use pycompat.xrange()
Gregory Szorc <gregory.szorc@gmail.com>
parents:
32201
diff
changeset
|
168 for n in pycompat.xrange(ctx.rev() + 1): |
16249 | 169 if n not in pvc: |
170 node = cl.node(n) | |
171 p1, p2 = cl.parentrevs(n) | |
172 if p1 == nullrev: | |
173 # start with a 'random' vector at root | |
174 pvc[n] = (0, _bin((node * 3)[:_vecbytes])) | |
175 elif p2 == nullrev: | |
176 d, v = pvc[p1] | |
177 pvc[n] = (d + 1, _flipbit(v, node)) | |
178 else: | |
179 pvc[n] = _mergevec(pvc[p1], pvc[p2], node) | |
180 bs = _join(*pvc[ctx.rev()]) | |
32201
4462a981e8df
base85: proxy through util module
Yuya Nishihara <yuya@tcha.org>
parents:
27501
diff
changeset
|
181 return pvec(util.b85encode(bs)) |
16249 | 182 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
38783
diff
changeset
|
183 |
16249 | 184 class pvec(object): |
185 def __init__(self, hashorctx): | |
43746
10662ac7849e
pvec: fix a `str` type conditional for py3
Matt Harbison <matt_harbison@yahoo.com>
parents:
43115
diff
changeset
|
186 if isinstance(hashorctx, bytes): |
16249 | 187 self._bs = hashorctx |
32201
4462a981e8df
base85: proxy through util module
Yuya Nishihara <yuya@tcha.org>
parents:
27501
diff
changeset
|
188 self._depth, self._vec = _split(util.b85decode(hashorctx)) |
16249 | 189 else: |
18918
5093d2a87ff6
pvec: use the correct name for an identifier
Bryan O'Sullivan <bryano@fb.com>
parents:
17424
diff
changeset
|
190 self._vec = ctxpvec(hashorctx) |
16249 | 191 |
192 def __str__(self): | |
193 return self._bs | |
194 | |
195 def __eq__(self, b): | |
196 return self._vec == b._vec and self._depth == b._depth | |
197 | |
198 def __lt__(self, b): | |
199 delta = b._depth - self._depth | |
200 if delta < 0: | |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
38783
diff
changeset
|
201 return False # always correct |
16249 | 202 if _hamming(self._vec, b._vec) > delta: |
203 return False | |
204 return True | |
205 | |
206 def __gt__(self, b): | |
207 return b < self | |
208 | |
209 def __or__(self, b): | |
210 delta = abs(b._depth - self._depth) | |
211 if _hamming(self._vec, b._vec) <= delta: | |
212 return False | |
213 return True | |
214 | |
215 def __sub__(self, b): | |
216 if self | b: | |
43077
687b865b95ad
formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents:
43076
diff
changeset
|
217 raise ValueError(b"concurrent pvecs") |
16249 | 218 return self._depth - b._depth |
219 | |
220 def distance(self, b): | |
221 d = abs(b._depth - self._depth) | |
222 h = _hamming(self._vec, b._vec) | |
223 return max(d, h) | |
224 | |
225 def near(self, b): | |
226 dist = abs(b.depth - self._depth) | |
227 if dist > _radius or _hamming(self._vec, b._vec) > _radius: | |
228 return False |