Mercurial > hg
annotate mercurial/pvec.py @ 35816:f6ca1e11d8b4 stable
revset: evaluate filesets against each revision for 'file()' (issue5778)
After f2aeff8a87b6, the fileset was evaluated to a set of files against the
working directory, and then those files were applied against each revision. The
result was nonsense. For example, `hg log -r 'file("set:exec()")'` on the
Mercurial repo listed revision 0 because it has the `hg` script, which is
currently +x. But that bit wasn't applied until revision 280 (which
'contains()' properly indicates).
This technique was borrowed from checkstatus(), which services adds(),
modifies(), and removes(), so it seems safe enough. The 'r:' case is explicitly
assigned to wdirrev, freeing up rev=None to mean "re-evaluate at each revision".
The distinction is important to avoid behavior changes with `hg log set:...`
(test-largefiles-misc.t and test-fileset-generated.t drop current log output
without this). I'm not sure what the right behavior for that is (1fd352aa08fc
explicitly enabled this behavior for graphlog), but the day before the release
isn't the time to experiment.
author | Matt Harbison <matt_harbison@yahoo.com> |
---|---|
date | Sun, 28 Jan 2018 14:08:59 -0500 |
parents | 4462a981e8df |
children | e7aa113b14f7 |
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 util, |
983e93d88193
pvec: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
24339
diff
changeset
|
56 ) |
16249 | 57 |
58 _size = 448 # 70 chars b85-encoded | |
59 _bytes = _size / 8 | |
60 _depthbits = 24 | |
61 _depthbytes = _depthbits / 8 | |
62 _vecbytes = _bytes - _depthbytes | |
63 _vecbits = _vecbytes * 8 | |
17424
e7cfe3587ea4
fix trivial spelling errors
Mads Kiilerich <mads@kiilerich.com>
parents:
16249
diff
changeset
|
64 _radius = (_vecbits - 30) / 2 # high probability vectors are related |
16249 | 65 |
66 def _bin(bs): | |
67 '''convert a bytestring to a long''' | |
68 v = 0 | |
69 for b in bs: | |
70 v = v * 256 + ord(b) | |
71 return v | |
72 | |
73 def _str(v, l): | |
74 bs = "" | |
75 for p in xrange(l): | |
76 bs = chr(v & 255) + bs | |
77 v >>= 8 | |
78 return bs | |
79 | |
80 def _split(b): | |
81 '''depth and bitvec''' | |
82 return _bin(b[:_depthbytes]), _bin(b[_depthbytes:]) | |
83 | |
84 def _join(depth, bitvec): | |
85 return _str(depth, _depthbytes) + _str(bitvec, _vecbytes) | |
86 | |
87 def _hweight(x): | |
88 c = 0 | |
89 while x: | |
90 if x & 1: | |
91 c += 1 | |
92 x >>= 1 | |
93 return c | |
94 _htab = [_hweight(x) for x in xrange(256)] | |
95 | |
96 def _hamming(a, b): | |
97 '''find the hamming distance between two longs''' | |
98 d = a ^ b | |
99 c = 0 | |
100 while d: | |
101 c += _htab[d & 0xff] | |
102 d >>= 8 | |
103 return c | |
104 | |
105 def _mergevec(x, y, c): | |
106 # Ideally, this function would be x ^ y ^ ancestor, but finding | |
107 # ancestors is a nuisance. So instead we find the minimal number | |
108 # of changes to balance the depth and hamming distance | |
109 | |
110 d1, v1 = x | |
111 d2, v2 = y | |
112 if d1 < d2: | |
113 d1, d2, v1, v2 = d2, d1, v2, v1 | |
114 | |
115 hdist = _hamming(v1, v2) | |
116 ddist = d1 - d2 | |
117 v = v1 | |
118 m = v1 ^ v2 # mask of different bits | |
119 i = 1 | |
120 | |
121 if hdist > ddist: | |
122 # if delta = 10 and hdist = 100, then we need to go up 55 steps | |
123 # to the ancestor and down 45 | |
124 changes = (hdist - ddist + 1) / 2 | |
125 else: | |
126 # must make at least one change | |
127 changes = 1 | |
128 depth = d1 + changes | |
129 | |
130 # copy changes from v2 | |
131 if m: | |
132 while changes: | |
133 if m & i: | |
134 v ^= i | |
135 changes -= 1 | |
136 i <<= 1 | |
137 else: | |
138 v = _flipbit(v, c) | |
139 | |
140 return depth, v | |
141 | |
142 def _flipbit(v, node): | |
143 # converting bit strings to longs is slow | |
144 bit = (hash(node) & 0xffffffff) % _vecbits | |
145 return v ^ (1<<bit) | |
146 | |
147 def ctxpvec(ctx): | |
148 '''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
|
149 r = ctx.repo() |
16249 | 150 if not util.safehasattr(r, "_pveccache"): |
151 r._pveccache = {} | |
152 pvc = r._pveccache | |
153 if ctx.rev() not in pvc: | |
154 cl = r.changelog | |
155 for n in xrange(ctx.rev() + 1): | |
156 if n not in pvc: | |
157 node = cl.node(n) | |
158 p1, p2 = cl.parentrevs(n) | |
159 if p1 == nullrev: | |
160 # start with a 'random' vector at root | |
161 pvc[n] = (0, _bin((node * 3)[:_vecbytes])) | |
162 elif p2 == nullrev: | |
163 d, v = pvc[p1] | |
164 pvc[n] = (d + 1, _flipbit(v, node)) | |
165 else: | |
166 pvc[n] = _mergevec(pvc[p1], pvc[p2], node) | |
167 bs = _join(*pvc[ctx.rev()]) | |
32201
4462a981e8df
base85: proxy through util module
Yuya Nishihara <yuya@tcha.org>
parents:
27501
diff
changeset
|
168 return pvec(util.b85encode(bs)) |
16249 | 169 |
170 class pvec(object): | |
171 def __init__(self, hashorctx): | |
172 if isinstance(hashorctx, str): | |
173 self._bs = hashorctx | |
32201
4462a981e8df
base85: proxy through util module
Yuya Nishihara <yuya@tcha.org>
parents:
27501
diff
changeset
|
174 self._depth, self._vec = _split(util.b85decode(hashorctx)) |
16249 | 175 else: |
18918
5093d2a87ff6
pvec: use the correct name for an identifier
Bryan O'Sullivan <bryano@fb.com>
parents:
17424
diff
changeset
|
176 self._vec = ctxpvec(hashorctx) |
16249 | 177 |
178 def __str__(self): | |
179 return self._bs | |
180 | |
181 def __eq__(self, b): | |
182 return self._vec == b._vec and self._depth == b._depth | |
183 | |
184 def __lt__(self, b): | |
185 delta = b._depth - self._depth | |
186 if delta < 0: | |
187 return False # always correct | |
188 if _hamming(self._vec, b._vec) > delta: | |
189 return False | |
190 return True | |
191 | |
192 def __gt__(self, b): | |
193 return b < self | |
194 | |
195 def __or__(self, b): | |
196 delta = abs(b._depth - self._depth) | |
197 if _hamming(self._vec, b._vec) <= delta: | |
198 return False | |
199 return True | |
200 | |
201 def __sub__(self, b): | |
202 if self | b: | |
203 raise ValueError("concurrent pvecs") | |
204 return self._depth - b._depth | |
205 | |
206 def distance(self, b): | |
207 d = abs(b._depth - self._depth) | |
208 h = _hamming(self._vec, b._vec) | |
209 return max(d, h) | |
210 | |
211 def near(self, b): | |
212 dist = abs(b.depth - self._depth) | |
213 if dist > _radius or _hamming(self._vec, b._vec) > _radius: | |
214 return False |