Mercurial > hg
annotate mercurial/pvec.py @ 29268:f200b58497f1
sslutil: reference appropriate config section in messaging
Error messages reference the config section defining the host
fingerprint. Now that we have multiple sections where this config
setting could live, we need to point the user at the appropriate
one.
We default to the new "hostsecurity" section. But we will still
refer them to the "hostfingerprint" section if a value is defined
there.
There are some corner cases where the messaging might be off. e.g.
they could define a SHA-1 fingerprint in both sections. IMO the
messaging needs a massive overhaul. I plan to do this as part
of future refactoring to security settings.
author | Gregory Szorc <gregory.szorc@gmail.com> |
---|---|
date | Sat, 28 May 2016 12:58:46 -0700 |
parents | 983e93d88193 |
children | 4462a981e8df |
rev | line source |
---|---|
16249 | 1 # pvec.py - probabilistic vector clocks for Mercurial |
2 # | |
3 # Copyright 2012 Matt Mackall <mpm@selenic.com> | |
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 | |
27501
983e93d88193
pvec: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
24339
diff
changeset
|
51 from __future__ import absolute_import |
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 ( |
983e93d88193
pvec: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
24339
diff
changeset
|
55 base85, |
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 |
59 _size = 448 # 70 chars b85-encoded | |
60 _bytes = _size / 8 | |
61 _depthbits = 24 | |
62 _depthbytes = _depthbits / 8 | |
63 _vecbytes = _bytes - _depthbytes | |
64 _vecbits = _vecbytes * 8 | |
17424
e7cfe3587ea4
fix trivial spelling errors
Mads Kiilerich <mads@kiilerich.com>
parents:
16249
diff
changeset
|
65 _radius = (_vecbits - 30) / 2 # high probability vectors are related |
16249 | 66 |
67 def _bin(bs): | |
68 '''convert a bytestring to a long''' | |
69 v = 0 | |
70 for b in bs: | |
71 v = v * 256 + ord(b) | |
72 return v | |
73 | |
74 def _str(v, l): | |
75 bs = "" | |
76 for p in xrange(l): | |
77 bs = chr(v & 255) + bs | |
78 v >>= 8 | |
79 return bs | |
80 | |
81 def _split(b): | |
82 '''depth and bitvec''' | |
83 return _bin(b[:_depthbytes]), _bin(b[_depthbytes:]) | |
84 | |
85 def _join(depth, bitvec): | |
86 return _str(depth, _depthbytes) + _str(bitvec, _vecbytes) | |
87 | |
88 def _hweight(x): | |
89 c = 0 | |
90 while x: | |
91 if x & 1: | |
92 c += 1 | |
93 x >>= 1 | |
94 return c | |
95 _htab = [_hweight(x) for x in xrange(256)] | |
96 | |
97 def _hamming(a, b): | |
98 '''find the hamming distance between two longs''' | |
99 d = a ^ b | |
100 c = 0 | |
101 while d: | |
102 c += _htab[d & 0xff] | |
103 d >>= 8 | |
104 return c | |
105 | |
106 def _mergevec(x, y, c): | |
107 # Ideally, this function would be x ^ y ^ ancestor, but finding | |
108 # ancestors is a nuisance. So instead we find the minimal number | |
109 # of changes to balance the depth and hamming distance | |
110 | |
111 d1, v1 = x | |
112 d2, v2 = y | |
113 if d1 < d2: | |
114 d1, d2, v1, v2 = d2, d1, v2, v1 | |
115 | |
116 hdist = _hamming(v1, v2) | |
117 ddist = d1 - d2 | |
118 v = v1 | |
119 m = v1 ^ v2 # mask of different bits | |
120 i = 1 | |
121 | |
122 if hdist > ddist: | |
123 # if delta = 10 and hdist = 100, then we need to go up 55 steps | |
124 # to the ancestor and down 45 | |
125 changes = (hdist - ddist + 1) / 2 | |
126 else: | |
127 # must make at least one change | |
128 changes = 1 | |
129 depth = d1 + changes | |
130 | |
131 # copy changes from v2 | |
132 if m: | |
133 while changes: | |
134 if m & i: | |
135 v ^= i | |
136 changes -= 1 | |
137 i <<= 1 | |
138 else: | |
139 v = _flipbit(v, c) | |
140 | |
141 return depth, v | |
142 | |
143 def _flipbit(v, node): | |
144 # converting bit strings to longs is slow | |
145 bit = (hash(node) & 0xffffffff) % _vecbits | |
146 return v ^ (1<<bit) | |
147 | |
148 def ctxpvec(ctx): | |
149 '''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
|
150 r = ctx.repo() |
16249 | 151 if not util.safehasattr(r, "_pveccache"): |
152 r._pveccache = {} | |
153 pvc = r._pveccache | |
154 if ctx.rev() not in pvc: | |
155 cl = r.changelog | |
156 for n in xrange(ctx.rev() + 1): | |
157 if n not in pvc: | |
158 node = cl.node(n) | |
159 p1, p2 = cl.parentrevs(n) | |
160 if p1 == nullrev: | |
161 # start with a 'random' vector at root | |
162 pvc[n] = (0, _bin((node * 3)[:_vecbytes])) | |
163 elif p2 == nullrev: | |
164 d, v = pvc[p1] | |
165 pvc[n] = (d + 1, _flipbit(v, node)) | |
166 else: | |
167 pvc[n] = _mergevec(pvc[p1], pvc[p2], node) | |
168 bs = _join(*pvc[ctx.rev()]) | |
169 return pvec(base85.b85encode(bs)) | |
170 | |
171 class pvec(object): | |
172 def __init__(self, hashorctx): | |
173 if isinstance(hashorctx, str): | |
174 self._bs = hashorctx | |
175 self._depth, self._vec = _split(base85.b85decode(hashorctx)) | |
176 else: | |
18918
5093d2a87ff6
pvec: use the correct name for an identifier
Bryan O'Sullivan <bryano@fb.com>
parents:
17424
diff
changeset
|
177 self._vec = ctxpvec(hashorctx) |
16249 | 178 |
179 def __str__(self): | |
180 return self._bs | |
181 | |
182 def __eq__(self, b): | |
183 return self._vec == b._vec and self._depth == b._depth | |
184 | |
185 def __lt__(self, b): | |
186 delta = b._depth - self._depth | |
187 if delta < 0: | |
188 return False # always correct | |
189 if _hamming(self._vec, b._vec) > delta: | |
190 return False | |
191 return True | |
192 | |
193 def __gt__(self, b): | |
194 return b < self | |
195 | |
196 def __or__(self, b): | |
197 delta = abs(b._depth - self._depth) | |
198 if _hamming(self._vec, b._vec) <= delta: | |
199 return False | |
200 return True | |
201 | |
202 def __sub__(self, b): | |
203 if self | b: | |
204 raise ValueError("concurrent pvecs") | |
205 return self._depth - b._depth | |
206 | |
207 def distance(self, b): | |
208 d = abs(b._depth - self._depth) | |
209 h = _hamming(self._vec, b._vec) | |
210 return max(d, h) | |
211 | |
212 def near(self, b): | |
213 dist = abs(b.depth - self._depth) | |
214 if dist > _radius or _hamming(self._vec, b._vec) > _radius: | |
215 return False |