|
1 # revlogdeltas.py - Logic around delta computation for revlog |
|
2 # |
|
3 # Copyright 2005-2007 Matt Mackall <mpm@selenic.com> |
|
4 # Copyright 2018 Octobus <contact@octobus.net> |
|
5 # |
|
6 # This software may be used and distributed according to the terms of the |
|
7 # GNU General Public License version 2 or any later version. |
|
8 """Helper class to compute deltas stored inside revlogs""" |
|
9 |
|
10 from __future__ import absolute_import |
|
11 |
|
12 import heapq |
|
13 import struct |
|
14 |
|
15 # import stuff from node for others to import from revlog |
|
16 from ..node import ( |
|
17 nullrev, |
|
18 ) |
|
19 from ..i18n import _ |
|
20 |
|
21 from .constants import ( |
|
22 REVIDX_ISCENSORED, |
|
23 REVIDX_RAWTEXT_CHANGING_FLAGS, |
|
24 ) |
|
25 |
|
26 from ..thirdparty import ( |
|
27 attr, |
|
28 ) |
|
29 |
|
30 from .. import ( |
|
31 error, |
|
32 mdiff, |
|
33 ) |
|
34 |
|
35 RevlogError = error.RevlogError |
|
36 CensoredNodeError = error.CensoredNodeError |
|
37 |
|
38 # maximum <delta-chain-data>/<revision-text-length> ratio |
|
39 LIMIT_DELTA2TEXT = 2 |
|
40 |
|
41 class _testrevlog(object): |
|
42 """minimalist fake revlog to use in doctests""" |
|
43 |
|
44 def __init__(self, data, density=0.5, mingap=0): |
|
45 """data is an list of revision payload boundaries""" |
|
46 self._data = data |
|
47 self._srdensitythreshold = density |
|
48 self._srmingapsize = mingap |
|
49 |
|
50 def start(self, rev): |
|
51 if rev == 0: |
|
52 return 0 |
|
53 return self._data[rev - 1] |
|
54 |
|
55 def end(self, rev): |
|
56 return self._data[rev] |
|
57 |
|
58 def length(self, rev): |
|
59 return self.end(rev) - self.start(rev) |
|
60 |
|
61 def __len__(self): |
|
62 return len(self._data) |
|
63 |
|
64 def slicechunk(revlog, revs, deltainfo=None, targetsize=None): |
|
65 """slice revs to reduce the amount of unrelated data to be read from disk. |
|
66 |
|
67 ``revs`` is sliced into groups that should be read in one time. |
|
68 Assume that revs are sorted. |
|
69 |
|
70 The initial chunk is sliced until the overall density (payload/chunks-span |
|
71 ratio) is above `revlog._srdensitythreshold`. No gap smaller than |
|
72 `revlog._srmingapsize` is skipped. |
|
73 |
|
74 If `targetsize` is set, no chunk larger than `targetsize` will be yield. |
|
75 For consistency with other slicing choice, this limit won't go lower than |
|
76 `revlog._srmingapsize`. |
|
77 |
|
78 If individual revisions chunk are larger than this limit, they will still |
|
79 be raised individually. |
|
80 |
|
81 >>> revlog = _testrevlog([ |
|
82 ... 5, #00 (5) |
|
83 ... 10, #01 (5) |
|
84 ... 12, #02 (2) |
|
85 ... 12, #03 (empty) |
|
86 ... 27, #04 (15) |
|
87 ... 31, #05 (4) |
|
88 ... 31, #06 (empty) |
|
89 ... 42, #07 (11) |
|
90 ... 47, #08 (5) |
|
91 ... 47, #09 (empty) |
|
92 ... 48, #10 (1) |
|
93 ... 51, #11 (3) |
|
94 ... 74, #12 (23) |
|
95 ... 85, #13 (11) |
|
96 ... 86, #14 (1) |
|
97 ... 91, #15 (5) |
|
98 ... ]) |
|
99 |
|
100 >>> list(slicechunk(revlog, list(range(16)))) |
|
101 [[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]] |
|
102 >>> list(slicechunk(revlog, [0, 15])) |
|
103 [[0], [15]] |
|
104 >>> list(slicechunk(revlog, [0, 11, 15])) |
|
105 [[0], [11], [15]] |
|
106 >>> list(slicechunk(revlog, [0, 11, 13, 15])) |
|
107 [[0], [11, 13, 15]] |
|
108 >>> list(slicechunk(revlog, [1, 2, 3, 5, 8, 10, 11, 14])) |
|
109 [[1, 2], [5, 8, 10, 11], [14]] |
|
110 |
|
111 Slicing with a maximum chunk size |
|
112 >>> list(slicechunk(revlog, [0, 11, 13, 15], targetsize=15)) |
|
113 [[0], [11], [13], [15]] |
|
114 >>> list(slicechunk(revlog, [0, 11, 13, 15], targetsize=20)) |
|
115 [[0], [11], [13, 15]] |
|
116 """ |
|
117 if targetsize is not None: |
|
118 targetsize = max(targetsize, revlog._srmingapsize) |
|
119 # targetsize should not be specified when evaluating delta candidates: |
|
120 # * targetsize is used to ensure we stay within specification when reading, |
|
121 # * deltainfo is used to pick are good delta chain when writing. |
|
122 if not (deltainfo is None or targetsize is None): |
|
123 msg = 'cannot use `targetsize` with a `deltainfo`' |
|
124 raise error.ProgrammingError(msg) |
|
125 for chunk in _slicechunktodensity(revlog, revs, |
|
126 deltainfo, |
|
127 revlog._srdensitythreshold, |
|
128 revlog._srmingapsize): |
|
129 for subchunk in _slicechunktosize(revlog, chunk, targetsize): |
|
130 yield subchunk |
|
131 |
|
132 def _slicechunktosize(revlog, revs, targetsize=None): |
|
133 """slice revs to match the target size |
|
134 |
|
135 This is intended to be used on chunk that density slicing selected by that |
|
136 are still too large compared to the read garantee of revlog. This might |
|
137 happens when "minimal gap size" interrupted the slicing or when chain are |
|
138 built in a way that create large blocks next to each other. |
|
139 |
|
140 >>> revlog = _testrevlog([ |
|
141 ... 3, #0 (3) |
|
142 ... 5, #1 (2) |
|
143 ... 6, #2 (1) |
|
144 ... 8, #3 (2) |
|
145 ... 8, #4 (empty) |
|
146 ... 11, #5 (3) |
|
147 ... 12, #6 (1) |
|
148 ... 13, #7 (1) |
|
149 ... 14, #8 (1) |
|
150 ... ]) |
|
151 |
|
152 Cases where chunk is already small enough |
|
153 >>> list(_slicechunktosize(revlog, [0], 3)) |
|
154 [[0]] |
|
155 >>> list(_slicechunktosize(revlog, [6, 7], 3)) |
|
156 [[6, 7]] |
|
157 >>> list(_slicechunktosize(revlog, [0], None)) |
|
158 [[0]] |
|
159 >>> list(_slicechunktosize(revlog, [6, 7], None)) |
|
160 [[6, 7]] |
|
161 |
|
162 cases where we need actual slicing |
|
163 >>> list(_slicechunktosize(revlog, [0, 1], 3)) |
|
164 [[0], [1]] |
|
165 >>> list(_slicechunktosize(revlog, [1, 3], 3)) |
|
166 [[1], [3]] |
|
167 >>> list(_slicechunktosize(revlog, [1, 2, 3], 3)) |
|
168 [[1, 2], [3]] |
|
169 >>> list(_slicechunktosize(revlog, [3, 5], 3)) |
|
170 [[3], [5]] |
|
171 >>> list(_slicechunktosize(revlog, [3, 4, 5], 3)) |
|
172 [[3], [5]] |
|
173 >>> list(_slicechunktosize(revlog, [5, 6, 7, 8], 3)) |
|
174 [[5], [6, 7, 8]] |
|
175 >>> list(_slicechunktosize(revlog, [0, 1, 2, 3, 4, 5, 6, 7, 8], 3)) |
|
176 [[0], [1, 2], [3], [5], [6, 7, 8]] |
|
177 |
|
178 Case with too large individual chunk (must return valid chunk) |
|
179 >>> list(_slicechunktosize(revlog, [0, 1], 2)) |
|
180 [[0], [1]] |
|
181 >>> list(_slicechunktosize(revlog, [1, 3], 1)) |
|
182 [[1], [3]] |
|
183 >>> list(_slicechunktosize(revlog, [3, 4, 5], 2)) |
|
184 [[3], [5]] |
|
185 """ |
|
186 assert targetsize is None or 0 <= targetsize |
|
187 if targetsize is None or segmentspan(revlog, revs) <= targetsize: |
|
188 yield revs |
|
189 return |
|
190 |
|
191 startrevidx = 0 |
|
192 startdata = revlog.start(revs[0]) |
|
193 endrevidx = 0 |
|
194 iterrevs = enumerate(revs) |
|
195 next(iterrevs) # skip first rev. |
|
196 for idx, r in iterrevs: |
|
197 span = revlog.end(r) - startdata |
|
198 if span <= targetsize: |
|
199 endrevidx = idx |
|
200 else: |
|
201 chunk = _trimchunk(revlog, revs, startrevidx, endrevidx + 1) |
|
202 if chunk: |
|
203 yield chunk |
|
204 startrevidx = idx |
|
205 startdata = revlog.start(r) |
|
206 endrevidx = idx |
|
207 yield _trimchunk(revlog, revs, startrevidx) |
|
208 |
|
209 def _slicechunktodensity(revlog, revs, deltainfo=None, targetdensity=0.5, |
|
210 mingapsize=0): |
|
211 """slice revs to reduce the amount of unrelated data to be read from disk. |
|
212 |
|
213 ``revs`` is sliced into groups that should be read in one time. |
|
214 Assume that revs are sorted. |
|
215 |
|
216 ``deltainfo`` is a _deltainfo instance of a revision that we would append |
|
217 to the top of the revlog. |
|
218 |
|
219 The initial chunk is sliced until the overall density (payload/chunks-span |
|
220 ratio) is above `targetdensity`. No gap smaller than `mingapsize` is |
|
221 skipped. |
|
222 |
|
223 >>> revlog = _testrevlog([ |
|
224 ... 5, #00 (5) |
|
225 ... 10, #01 (5) |
|
226 ... 12, #02 (2) |
|
227 ... 12, #03 (empty) |
|
228 ... 27, #04 (15) |
|
229 ... 31, #05 (4) |
|
230 ... 31, #06 (empty) |
|
231 ... 42, #07 (11) |
|
232 ... 47, #08 (5) |
|
233 ... 47, #09 (empty) |
|
234 ... 48, #10 (1) |
|
235 ... 51, #11 (3) |
|
236 ... 74, #12 (23) |
|
237 ... 85, #13 (11) |
|
238 ... 86, #14 (1) |
|
239 ... 91, #15 (5) |
|
240 ... ]) |
|
241 |
|
242 >>> list(_slicechunktodensity(revlog, list(range(16)))) |
|
243 [[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]] |
|
244 >>> list(_slicechunktodensity(revlog, [0, 15])) |
|
245 [[0], [15]] |
|
246 >>> list(_slicechunktodensity(revlog, [0, 11, 15])) |
|
247 [[0], [11], [15]] |
|
248 >>> list(_slicechunktodensity(revlog, [0, 11, 13, 15])) |
|
249 [[0], [11, 13, 15]] |
|
250 >>> list(_slicechunktodensity(revlog, [1, 2, 3, 5, 8, 10, 11, 14])) |
|
251 [[1, 2], [5, 8, 10, 11], [14]] |
|
252 >>> list(_slicechunktodensity(revlog, [1, 2, 3, 5, 8, 10, 11, 14], |
|
253 ... mingapsize=20)) |
|
254 [[1, 2, 3, 5, 8, 10, 11], [14]] |
|
255 >>> list(_slicechunktodensity(revlog, [1, 2, 3, 5, 8, 10, 11, 14], |
|
256 ... targetdensity=0.95)) |
|
257 [[1, 2], [5], [8, 10, 11], [14]] |
|
258 >>> list(_slicechunktodensity(revlog, [1, 2, 3, 5, 8, 10, 11, 14], |
|
259 ... targetdensity=0.95, mingapsize=12)) |
|
260 [[1, 2], [5, 8, 10, 11], [14]] |
|
261 """ |
|
262 start = revlog.start |
|
263 length = revlog.length |
|
264 |
|
265 if len(revs) <= 1: |
|
266 yield revs |
|
267 return |
|
268 |
|
269 nextrev = len(revlog) |
|
270 nextoffset = revlog.end(nextrev - 1) |
|
271 |
|
272 if deltainfo is None: |
|
273 deltachainspan = segmentspan(revlog, revs) |
|
274 chainpayload = sum(length(r) for r in revs) |
|
275 else: |
|
276 deltachainspan = deltainfo.distance |
|
277 chainpayload = deltainfo.compresseddeltalen |
|
278 |
|
279 if deltachainspan < mingapsize: |
|
280 yield revs |
|
281 return |
|
282 |
|
283 readdata = deltachainspan |
|
284 |
|
285 if deltachainspan: |
|
286 density = chainpayload / float(deltachainspan) |
|
287 else: |
|
288 density = 1.0 |
|
289 |
|
290 if density >= targetdensity: |
|
291 yield revs |
|
292 return |
|
293 |
|
294 if deltainfo is not None and deltainfo.deltalen: |
|
295 revs = list(revs) |
|
296 revs.append(nextrev) |
|
297 |
|
298 # Store the gaps in a heap to have them sorted by decreasing size |
|
299 gapsheap = [] |
|
300 heapq.heapify(gapsheap) |
|
301 prevend = None |
|
302 for i, rev in enumerate(revs): |
|
303 if rev < nextrev: |
|
304 revstart = start(rev) |
|
305 revlen = length(rev) |
|
306 else: |
|
307 revstart = nextoffset |
|
308 revlen = deltainfo.deltalen |
|
309 |
|
310 # Skip empty revisions to form larger holes |
|
311 if revlen == 0: |
|
312 continue |
|
313 |
|
314 if prevend is not None: |
|
315 gapsize = revstart - prevend |
|
316 # only consider holes that are large enough |
|
317 if gapsize > mingapsize: |
|
318 heapq.heappush(gapsheap, (-gapsize, i)) |
|
319 |
|
320 prevend = revstart + revlen |
|
321 |
|
322 # Collect the indices of the largest holes until the density is acceptable |
|
323 indicesheap = [] |
|
324 heapq.heapify(indicesheap) |
|
325 while gapsheap and density < targetdensity: |
|
326 oppgapsize, gapidx = heapq.heappop(gapsheap) |
|
327 |
|
328 heapq.heappush(indicesheap, gapidx) |
|
329 |
|
330 # the gap sizes are stored as negatives to be sorted decreasingly |
|
331 # by the heap |
|
332 readdata -= (-oppgapsize) |
|
333 if readdata > 0: |
|
334 density = chainpayload / float(readdata) |
|
335 else: |
|
336 density = 1.0 |
|
337 |
|
338 # Cut the revs at collected indices |
|
339 previdx = 0 |
|
340 while indicesheap: |
|
341 idx = heapq.heappop(indicesheap) |
|
342 |
|
343 chunk = _trimchunk(revlog, revs, previdx, idx) |
|
344 if chunk: |
|
345 yield chunk |
|
346 |
|
347 previdx = idx |
|
348 |
|
349 chunk = _trimchunk(revlog, revs, previdx) |
|
350 if chunk: |
|
351 yield chunk |
|
352 |
|
353 def _trimchunk(revlog, revs, startidx, endidx=None): |
|
354 """returns revs[startidx:endidx] without empty trailing revs |
|
355 |
|
356 Doctest Setup |
|
357 >>> revlog = _testrevlog([ |
|
358 ... 5, #0 |
|
359 ... 10, #1 |
|
360 ... 12, #2 |
|
361 ... 12, #3 (empty) |
|
362 ... 17, #4 |
|
363 ... 21, #5 |
|
364 ... 21, #6 (empty) |
|
365 ... ]) |
|
366 |
|
367 Contiguous cases: |
|
368 >>> _trimchunk(revlog, [0, 1, 2, 3, 4, 5, 6], 0) |
|
369 [0, 1, 2, 3, 4, 5] |
|
370 >>> _trimchunk(revlog, [0, 1, 2, 3, 4, 5, 6], 0, 5) |
|
371 [0, 1, 2, 3, 4] |
|
372 >>> _trimchunk(revlog, [0, 1, 2, 3, 4, 5, 6], 0, 4) |
|
373 [0, 1, 2] |
|
374 >>> _trimchunk(revlog, [0, 1, 2, 3, 4, 5, 6], 2, 4) |
|
375 [2] |
|
376 >>> _trimchunk(revlog, [0, 1, 2, 3, 4, 5, 6], 3) |
|
377 [3, 4, 5] |
|
378 >>> _trimchunk(revlog, [0, 1, 2, 3, 4, 5, 6], 3, 5) |
|
379 [3, 4] |
|
380 |
|
381 Discontiguous cases: |
|
382 >>> _trimchunk(revlog, [1, 3, 5, 6], 0) |
|
383 [1, 3, 5] |
|
384 >>> _trimchunk(revlog, [1, 3, 5, 6], 0, 2) |
|
385 [1] |
|
386 >>> _trimchunk(revlog, [1, 3, 5, 6], 1, 3) |
|
387 [3, 5] |
|
388 >>> _trimchunk(revlog, [1, 3, 5, 6], 1) |
|
389 [3, 5] |
|
390 """ |
|
391 length = revlog.length |
|
392 |
|
393 if endidx is None: |
|
394 endidx = len(revs) |
|
395 |
|
396 # If we have a non-emtpy delta candidate, there are nothing to trim |
|
397 if revs[endidx - 1] < len(revlog): |
|
398 # Trim empty revs at the end, except the very first revision of a chain |
|
399 while (endidx > 1 |
|
400 and endidx > startidx |
|
401 and length(revs[endidx - 1]) == 0): |
|
402 endidx -= 1 |
|
403 |
|
404 return revs[startidx:endidx] |
|
405 |
|
406 def segmentspan(revlog, revs, deltainfo=None): |
|
407 """Get the byte span of a segment of revisions |
|
408 |
|
409 revs is a sorted array of revision numbers |
|
410 |
|
411 >>> revlog = _testrevlog([ |
|
412 ... 5, #0 |
|
413 ... 10, #1 |
|
414 ... 12, #2 |
|
415 ... 12, #3 (empty) |
|
416 ... 17, #4 |
|
417 ... ]) |
|
418 |
|
419 >>> segmentspan(revlog, [0, 1, 2, 3, 4]) |
|
420 17 |
|
421 >>> segmentspan(revlog, [0, 4]) |
|
422 17 |
|
423 >>> segmentspan(revlog, [3, 4]) |
|
424 5 |
|
425 >>> segmentspan(revlog, [1, 2, 3,]) |
|
426 7 |
|
427 >>> segmentspan(revlog, [1, 3]) |
|
428 7 |
|
429 """ |
|
430 if not revs: |
|
431 return 0 |
|
432 if deltainfo is not None and len(revlog) <= revs[-1]: |
|
433 if len(revs) == 1: |
|
434 return deltainfo.deltalen |
|
435 offset = revlog.end(len(revlog) - 1) |
|
436 end = deltainfo.deltalen + offset |
|
437 else: |
|
438 end = revlog.end(revs[-1]) |
|
439 return end - revlog.start(revs[0]) |
|
440 |
|
441 @attr.s(slots=True, frozen=True) |
|
442 class _deltainfo(object): |
|
443 distance = attr.ib() |
|
444 deltalen = attr.ib() |
|
445 data = attr.ib() |
|
446 base = attr.ib() |
|
447 chainbase = attr.ib() |
|
448 chainlen = attr.ib() |
|
449 compresseddeltalen = attr.ib() |
|
450 snapshotdepth = attr.ib() |
|
451 |
|
452 def isgooddeltainfo(revlog, deltainfo, revinfo): |
|
453 """Returns True if the given delta is good. Good means that it is within |
|
454 the disk span, disk size, and chain length bounds that we know to be |
|
455 performant.""" |
|
456 if deltainfo is None: |
|
457 return False |
|
458 |
|
459 # - 'deltainfo.distance' is the distance from the base revision -- |
|
460 # bounding it limits the amount of I/O we need to do. |
|
461 # - 'deltainfo.compresseddeltalen' is the sum of the total size of |
|
462 # deltas we need to apply -- bounding it limits the amount of CPU |
|
463 # we consume. |
|
464 |
|
465 if revlog._sparserevlog: |
|
466 # As sparse-read will be used, we can consider that the distance, |
|
467 # instead of being the span of the whole chunk, |
|
468 # is the span of the largest read chunk |
|
469 base = deltainfo.base |
|
470 |
|
471 if base != nullrev: |
|
472 deltachain = revlog._deltachain(base)[0] |
|
473 else: |
|
474 deltachain = [] |
|
475 |
|
476 # search for the first non-snapshot revision |
|
477 for idx, r in enumerate(deltachain): |
|
478 if not revlog.issnapshot(r): |
|
479 break |
|
480 deltachain = deltachain[idx:] |
|
481 chunks = slicechunk(revlog, deltachain, deltainfo) |
|
482 all_span = [segmentspan(revlog, revs, deltainfo) |
|
483 for revs in chunks] |
|
484 distance = max(all_span) |
|
485 else: |
|
486 distance = deltainfo.distance |
|
487 |
|
488 textlen = revinfo.textlen |
|
489 defaultmax = textlen * 4 |
|
490 maxdist = revlog._maxdeltachainspan |
|
491 if not maxdist: |
|
492 maxdist = distance # ensure the conditional pass |
|
493 maxdist = max(maxdist, defaultmax) |
|
494 if revlog._sparserevlog and maxdist < revlog._srmingapsize: |
|
495 # In multiple place, we are ignoring irrelevant data range below a |
|
496 # certain size. Be also apply this tradeoff here and relax span |
|
497 # constraint for small enought content. |
|
498 maxdist = revlog._srmingapsize |
|
499 |
|
500 # Bad delta from read span: |
|
501 # |
|
502 # If the span of data read is larger than the maximum allowed. |
|
503 if maxdist < distance: |
|
504 return False |
|
505 |
|
506 # Bad delta from new delta size: |
|
507 # |
|
508 # If the delta size is larger than the target text, storing the |
|
509 # delta will be inefficient. |
|
510 if textlen < deltainfo.deltalen: |
|
511 return False |
|
512 |
|
513 # Bad delta from cumulated payload size: |
|
514 # |
|
515 # If the sum of delta get larger than K * target text length. |
|
516 if textlen * LIMIT_DELTA2TEXT < deltainfo.compresseddeltalen: |
|
517 return False |
|
518 |
|
519 # Bad delta from chain length: |
|
520 # |
|
521 # If the number of delta in the chain gets too high. |
|
522 if (revlog._maxchainlen |
|
523 and revlog._maxchainlen < deltainfo.chainlen): |
|
524 return False |
|
525 |
|
526 # bad delta from intermediate snapshot size limit |
|
527 # |
|
528 # If an intermediate snapshot size is higher than the limit. The |
|
529 # limit exist to prevent endless chain of intermediate delta to be |
|
530 # created. |
|
531 if (deltainfo.snapshotdepth is not None and |
|
532 (textlen >> deltainfo.snapshotdepth) < deltainfo.deltalen): |
|
533 return False |
|
534 |
|
535 # bad delta if new intermediate snapshot is larger than the previous |
|
536 # snapshot |
|
537 if (deltainfo.snapshotdepth |
|
538 and revlog.length(deltainfo.base) < deltainfo.deltalen): |
|
539 return False |
|
540 |
|
541 return True |
|
542 |
|
543 class deltacomputer(object): |
|
544 def __init__(self, revlog): |
|
545 self.revlog = revlog |
|
546 |
|
547 def _getcandidaterevs(self, p1, p2, cachedelta): |
|
548 """ |
|
549 Provides revisions that present an interest to be diffed against, |
|
550 grouped by level of easiness. |
|
551 """ |
|
552 revlog = self.revlog |
|
553 gdelta = revlog._generaldelta |
|
554 curr = len(revlog) |
|
555 prev = curr - 1 |
|
556 p1r, p2r = revlog.rev(p1), revlog.rev(p2) |
|
557 |
|
558 # should we try to build a delta? |
|
559 if prev != nullrev and revlog._storedeltachains: |
|
560 tested = set() |
|
561 # This condition is true most of the time when processing |
|
562 # changegroup data into a generaldelta repo. The only time it |
|
563 # isn't true is if this is the first revision in a delta chain |
|
564 # or if ``format.generaldelta=true`` disabled ``lazydeltabase``. |
|
565 if cachedelta and gdelta and revlog._lazydeltabase: |
|
566 # Assume what we received from the server is a good choice |
|
567 # build delta will reuse the cache |
|
568 yield (cachedelta[0],) |
|
569 tested.add(cachedelta[0]) |
|
570 |
|
571 if gdelta: |
|
572 # exclude already lazy tested base if any |
|
573 parents = [p for p in (p1r, p2r) |
|
574 if p != nullrev and p not in tested] |
|
575 |
|
576 if not revlog._deltabothparents and len(parents) == 2: |
|
577 parents.sort() |
|
578 # To minimize the chance of having to build a fulltext, |
|
579 # pick first whichever parent is closest to us (max rev) |
|
580 yield (parents[1],) |
|
581 # then the other one (min rev) if the first did not fit |
|
582 yield (parents[0],) |
|
583 tested.update(parents) |
|
584 elif len(parents) > 0: |
|
585 # Test all parents (1 or 2), and keep the best candidate |
|
586 yield parents |
|
587 tested.update(parents) |
|
588 |
|
589 if prev not in tested: |
|
590 # other approach failed try against prev to hopefully save us a |
|
591 # fulltext. |
|
592 yield (prev,) |
|
593 tested.add(prev) |
|
594 |
|
595 def buildtext(self, revinfo, fh): |
|
596 """Builds a fulltext version of a revision |
|
597 |
|
598 revinfo: _revisioninfo instance that contains all needed info |
|
599 fh: file handle to either the .i or the .d revlog file, |
|
600 depending on whether it is inlined or not |
|
601 """ |
|
602 btext = revinfo.btext |
|
603 if btext[0] is not None: |
|
604 return btext[0] |
|
605 |
|
606 revlog = self.revlog |
|
607 cachedelta = revinfo.cachedelta |
|
608 flags = revinfo.flags |
|
609 node = revinfo.node |
|
610 |
|
611 baserev = cachedelta[0] |
|
612 delta = cachedelta[1] |
|
613 # special case deltas which replace entire base; no need to decode |
|
614 # base revision. this neatly avoids censored bases, which throw when |
|
615 # they're decoded. |
|
616 hlen = struct.calcsize(">lll") |
|
617 if delta[:hlen] == mdiff.replacediffheader(revlog.rawsize(baserev), |
|
618 len(delta) - hlen): |
|
619 btext[0] = delta[hlen:] |
|
620 else: |
|
621 # deltabase is rawtext before changed by flag processors, which is |
|
622 # equivalent to non-raw text |
|
623 basetext = revlog.revision(baserev, _df=fh, raw=False) |
|
624 btext[0] = mdiff.patch(basetext, delta) |
|
625 |
|
626 try: |
|
627 res = revlog._processflags(btext[0], flags, 'read', raw=True) |
|
628 btext[0], validatehash = res |
|
629 if validatehash: |
|
630 revlog.checkhash(btext[0], node, p1=revinfo.p1, p2=revinfo.p2) |
|
631 if flags & REVIDX_ISCENSORED: |
|
632 raise RevlogError(_('node %s is not censored') % node) |
|
633 except CensoredNodeError: |
|
634 # must pass the censored index flag to add censored revisions |
|
635 if not flags & REVIDX_ISCENSORED: |
|
636 raise |
|
637 return btext[0] |
|
638 |
|
639 def _builddeltadiff(self, base, revinfo, fh): |
|
640 revlog = self.revlog |
|
641 t = self.buildtext(revinfo, fh) |
|
642 if revlog.iscensored(base): |
|
643 # deltas based on a censored revision must replace the |
|
644 # full content in one patch, so delta works everywhere |
|
645 header = mdiff.replacediffheader(revlog.rawsize(base), len(t)) |
|
646 delta = header + t |
|
647 else: |
|
648 ptext = revlog.revision(base, _df=fh, raw=True) |
|
649 delta = mdiff.textdiff(ptext, t) |
|
650 |
|
651 return delta |
|
652 |
|
653 def _builddeltainfo(self, revinfo, base, fh): |
|
654 # can we use the cached delta? |
|
655 if revinfo.cachedelta and revinfo.cachedelta[0] == base: |
|
656 delta = revinfo.cachedelta[1] |
|
657 else: |
|
658 delta = self._builddeltadiff(base, revinfo, fh) |
|
659 revlog = self.revlog |
|
660 header, data = revlog.compress(delta) |
|
661 deltalen = len(header) + len(data) |
|
662 chainbase = revlog.chainbase(base) |
|
663 offset = revlog.end(len(revlog) - 1) |
|
664 dist = deltalen + offset - revlog.start(chainbase) |
|
665 if revlog._generaldelta: |
|
666 deltabase = base |
|
667 else: |
|
668 deltabase = chainbase |
|
669 chainlen, compresseddeltalen = revlog._chaininfo(base) |
|
670 chainlen += 1 |
|
671 compresseddeltalen += deltalen |
|
672 |
|
673 revlog = self.revlog |
|
674 snapshotdepth = None |
|
675 if deltabase == nullrev: |
|
676 snapshotdepth = 0 |
|
677 elif revlog._sparserevlog and revlog.issnapshot(deltabase): |
|
678 # A delta chain should always be one full snapshot, |
|
679 # zero or more semi-snapshots, and zero or more deltas |
|
680 p1, p2 = revlog.rev(revinfo.p1), revlog.rev(revinfo.p2) |
|
681 if deltabase not in (p1, p2) and revlog.issnapshot(deltabase): |
|
682 snapshotdepth = len(revlog._deltachain(deltabase)[0]) |
|
683 |
|
684 return _deltainfo(dist, deltalen, (header, data), deltabase, |
|
685 chainbase, chainlen, compresseddeltalen, |
|
686 snapshotdepth) |
|
687 |
|
688 def finddeltainfo(self, revinfo, fh): |
|
689 """Find an acceptable delta against a candidate revision |
|
690 |
|
691 revinfo: information about the revision (instance of _revisioninfo) |
|
692 fh: file handle to either the .i or the .d revlog file, |
|
693 depending on whether it is inlined or not |
|
694 |
|
695 Returns the first acceptable candidate revision, as ordered by |
|
696 _getcandidaterevs |
|
697 """ |
|
698 if not revinfo.textlen: |
|
699 return None # empty file do not need delta |
|
700 |
|
701 cachedelta = revinfo.cachedelta |
|
702 p1 = revinfo.p1 |
|
703 p2 = revinfo.p2 |
|
704 revlog = self.revlog |
|
705 |
|
706 deltalength = self.revlog.length |
|
707 deltaparent = self.revlog.deltaparent |
|
708 |
|
709 deltainfo = None |
|
710 deltas_limit = revinfo.textlen * LIMIT_DELTA2TEXT |
|
711 for candidaterevs in self._getcandidaterevs(p1, p2, cachedelta): |
|
712 # filter out delta base that will never produce good delta |
|
713 candidaterevs = [r for r in candidaterevs |
|
714 if self.revlog.length(r) <= deltas_limit] |
|
715 nominateddeltas = [] |
|
716 for candidaterev in candidaterevs: |
|
717 # skip over empty delta (no need to include them in a chain) |
|
718 while candidaterev != nullrev and not deltalength(candidaterev): |
|
719 candidaterev = deltaparent(candidaterev) |
|
720 # no need to try a delta against nullid, this will be handled |
|
721 # by fulltext later. |
|
722 if candidaterev == nullrev: |
|
723 continue |
|
724 # no delta for rawtext-changing revs (see "candelta" for why) |
|
725 if revlog.flags(candidaterev) & REVIDX_RAWTEXT_CHANGING_FLAGS: |
|
726 continue |
|
727 candidatedelta = self._builddeltainfo(revinfo, candidaterev, fh) |
|
728 if isgooddeltainfo(self.revlog, candidatedelta, revinfo): |
|
729 nominateddeltas.append(candidatedelta) |
|
730 if nominateddeltas: |
|
731 deltainfo = min(nominateddeltas, key=lambda x: x.deltalen) |
|
732 break |
|
733 |
|
734 return deltainfo |