##// END OF EJS Templates
sparse-revlog: align endrevidx usages in the _slicechunktosize...
Boris Feld -
r40693:2eb48aa0 default
parent child Browse files
Show More
@@ -1,977 +1,977 b''
1 1 # revlogdeltas.py - Logic around delta computation for revlog
2 2 #
3 3 # Copyright 2005-2007 Matt Mackall <mpm@selenic.com>
4 4 # Copyright 2018 Octobus <contact@octobus.net>
5 5 #
6 6 # This software may be used and distributed according to the terms of the
7 7 # GNU General Public License version 2 or any later version.
8 8 """Helper class to compute deltas stored inside revlogs"""
9 9
10 10 from __future__ import absolute_import
11 11
12 12 import collections
13 13 import struct
14 14
15 15 # import stuff from node for others to import from revlog
16 16 from ..node import (
17 17 nullrev,
18 18 )
19 19 from ..i18n import _
20 20
21 21 from .constants import (
22 22 REVIDX_ISCENSORED,
23 23 REVIDX_RAWTEXT_CHANGING_FLAGS,
24 24 )
25 25
26 26 from ..thirdparty import (
27 27 attr,
28 28 )
29 29
30 30 from .. import (
31 31 error,
32 32 mdiff,
33 33 )
34 34
35 35 # maximum <delta-chain-data>/<revision-text-length> ratio
36 36 LIMIT_DELTA2TEXT = 2
37 37
38 38 class _testrevlog(object):
39 39 """minimalist fake revlog to use in doctests"""
40 40
41 41 def __init__(self, data, density=0.5, mingap=0, snapshot=()):
42 42 """data is an list of revision payload boundaries"""
43 43 self._data = data
44 44 self._srdensitythreshold = density
45 45 self._srmingapsize = mingap
46 46 self._snapshot = set(snapshot)
47 47
48 48 def start(self, rev):
49 49 if rev == 0:
50 50 return 0
51 51 return self._data[rev - 1]
52 52
53 53 def end(self, rev):
54 54 return self._data[rev]
55 55
56 56 def length(self, rev):
57 57 return self.end(rev) - self.start(rev)
58 58
59 59 def __len__(self):
60 60 return len(self._data)
61 61
62 62 def issnapshot(self, rev):
63 63 return rev in self._snapshot
64 64
65 65 def slicechunk(revlog, revs, targetsize=None):
66 66 """slice revs to reduce the amount of unrelated data to be read from disk.
67 67
68 68 ``revs`` is sliced into groups that should be read in one time.
69 69 Assume that revs are sorted.
70 70
71 71 The initial chunk is sliced until the overall density (payload/chunks-span
72 72 ratio) is above `revlog._srdensitythreshold`. No gap smaller than
73 73 `revlog._srmingapsize` is skipped.
74 74
75 75 If `targetsize` is set, no chunk larger than `targetsize` will be yield.
76 76 For consistency with other slicing choice, this limit won't go lower than
77 77 `revlog._srmingapsize`.
78 78
79 79 If individual revisions chunk are larger than this limit, they will still
80 80 be raised individually.
81 81
82 82 >>> data = [
83 83 ... 5, #00 (5)
84 84 ... 10, #01 (5)
85 85 ... 12, #02 (2)
86 86 ... 12, #03 (empty)
87 87 ... 27, #04 (15)
88 88 ... 31, #05 (4)
89 89 ... 31, #06 (empty)
90 90 ... 42, #07 (11)
91 91 ... 47, #08 (5)
92 92 ... 47, #09 (empty)
93 93 ... 48, #10 (1)
94 94 ... 51, #11 (3)
95 95 ... 74, #12 (23)
96 96 ... 85, #13 (11)
97 97 ... 86, #14 (1)
98 98 ... 91, #15 (5)
99 99 ... ]
100 100 >>> revlog = _testrevlog(data, snapshot=range(16))
101 101
102 102 >>> list(slicechunk(revlog, list(range(16))))
103 103 [[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]]
104 104 >>> list(slicechunk(revlog, [0, 15]))
105 105 [[0], [15]]
106 106 >>> list(slicechunk(revlog, [0, 11, 15]))
107 107 [[0], [11], [15]]
108 108 >>> list(slicechunk(revlog, [0, 11, 13, 15]))
109 109 [[0], [11, 13, 15]]
110 110 >>> list(slicechunk(revlog, [1, 2, 3, 5, 8, 10, 11, 14]))
111 111 [[1, 2], [5, 8, 10, 11], [14]]
112 112
113 113 Slicing with a maximum chunk size
114 114 >>> list(slicechunk(revlog, [0, 11, 13, 15], targetsize=15))
115 115 [[0], [11], [13], [15]]
116 116 >>> list(slicechunk(revlog, [0, 11, 13, 15], targetsize=20))
117 117 [[0], [11], [13, 15]]
118 118 """
119 119 if targetsize is not None:
120 120 targetsize = max(targetsize, revlog._srmingapsize)
121 121 # targetsize should not be specified when evaluating delta candidates:
122 122 # * targetsize is used to ensure we stay within specification when reading,
123 123 for chunk in _slicechunktodensity(revlog, revs,
124 124 revlog._srdensitythreshold,
125 125 revlog._srmingapsize):
126 126 for subchunk in _slicechunktosize(revlog, chunk, targetsize):
127 127 yield subchunk
128 128
129 129 def _slicechunktosize(revlog, revs, targetsize=None):
130 130 """slice revs to match the target size
131 131
132 132 This is intended to be used on chunk that density slicing selected by that
133 133 are still too large compared to the read garantee of revlog. This might
134 134 happens when "minimal gap size" interrupted the slicing or when chain are
135 135 built in a way that create large blocks next to each other.
136 136
137 137 >>> data = [
138 138 ... 3, #0 (3)
139 139 ... 5, #1 (2)
140 140 ... 6, #2 (1)
141 141 ... 8, #3 (2)
142 142 ... 8, #4 (empty)
143 143 ... 11, #5 (3)
144 144 ... 12, #6 (1)
145 145 ... 13, #7 (1)
146 146 ... 14, #8 (1)
147 147 ... ]
148 148
149 149 == All snapshots cases ==
150 150 >>> revlog = _testrevlog(data, snapshot=range(9))
151 151
152 152 Cases where chunk is already small enough
153 153 >>> list(_slicechunktosize(revlog, [0], 3))
154 154 [[0]]
155 155 >>> list(_slicechunktosize(revlog, [6, 7], 3))
156 156 [[6, 7]]
157 157 >>> list(_slicechunktosize(revlog, [0], None))
158 158 [[0]]
159 159 >>> list(_slicechunktosize(revlog, [6, 7], None))
160 160 [[6, 7]]
161 161
162 162 cases where we need actual slicing
163 163 >>> list(_slicechunktosize(revlog, [0, 1], 3))
164 164 [[0], [1]]
165 165 >>> list(_slicechunktosize(revlog, [1, 3], 3))
166 166 [[1], [3]]
167 167 >>> list(_slicechunktosize(revlog, [1, 2, 3], 3))
168 168 [[1, 2], [3]]
169 169 >>> list(_slicechunktosize(revlog, [3, 5], 3))
170 170 [[3], [5]]
171 171 >>> list(_slicechunktosize(revlog, [3, 4, 5], 3))
172 172 [[3], [5]]
173 173 >>> list(_slicechunktosize(revlog, [5, 6, 7, 8], 3))
174 174 [[5], [6, 7, 8]]
175 175 >>> list(_slicechunktosize(revlog, [0, 1, 2, 3, 4, 5, 6, 7, 8], 3))
176 176 [[0], [1, 2], [3], [5], [6, 7, 8]]
177 177
178 178 Case with too large individual chunk (must return valid chunk)
179 179 >>> list(_slicechunktosize(revlog, [0, 1], 2))
180 180 [[0], [1]]
181 181 >>> list(_slicechunktosize(revlog, [1, 3], 1))
182 182 [[1], [3]]
183 183 >>> list(_slicechunktosize(revlog, [3, 4, 5], 2))
184 184 [[3], [5]]
185 185
186 186 == No Snapshot cases ==
187 187 >>> revlog = _testrevlog(data)
188 188
189 189 Cases where chunk is already small enough
190 190 >>> list(_slicechunktosize(revlog, [0], 3))
191 191 [[0]]
192 192 >>> list(_slicechunktosize(revlog, [6, 7], 3))
193 193 [[6, 7]]
194 194 >>> list(_slicechunktosize(revlog, [0], None))
195 195 [[0]]
196 196 >>> list(_slicechunktosize(revlog, [6, 7], None))
197 197 [[6, 7]]
198 198
199 199 cases where we need actual slicing
200 200 >>> list(_slicechunktosize(revlog, [0, 1], 3))
201 201 [[0], [1]]
202 202 >>> list(_slicechunktosize(revlog, [1, 3], 3))
203 203 [[1], [3]]
204 204 >>> list(_slicechunktosize(revlog, [1, 2, 3], 3))
205 205 [[1], [2, 3]]
206 206 >>> list(_slicechunktosize(revlog, [3, 5], 3))
207 207 [[3], [5]]
208 208 >>> list(_slicechunktosize(revlog, [3, 4, 5], 3))
209 209 [[3], [4, 5]]
210 210 >>> list(_slicechunktosize(revlog, [5, 6, 7, 8], 3))
211 211 [[5], [6, 7, 8]]
212 212 >>> list(_slicechunktosize(revlog, [0, 1, 2, 3, 4, 5, 6, 7, 8], 3))
213 213 [[0], [1, 2], [3], [5], [6, 7, 8]]
214 214
215 215 Case with too large individual chunk (must return valid chunk)
216 216 >>> list(_slicechunktosize(revlog, [0, 1], 2))
217 217 [[0], [1]]
218 218 >>> list(_slicechunktosize(revlog, [1, 3], 1))
219 219 [[1], [3]]
220 220 >>> list(_slicechunktosize(revlog, [3, 4, 5], 2))
221 221 [[3], [5]]
222 222
223 223 == mixed case ==
224 224 >>> revlog = _testrevlog(data, snapshot=[0, 1, 2])
225 225 >>> list(_slicechunktosize(revlog, list(range(9)), 5))
226 226 [[0, 1], [2], [3, 4, 5], [6, 7, 8]]
227 227 """
228 228 assert targetsize is None or 0 <= targetsize
229 229 startdata = revlog.start(revs[0])
230 230 enddata = revlog.end(revs[-1])
231 231 fullspan = enddata - startdata
232 232 if targetsize is None or fullspan <= targetsize:
233 233 yield revs
234 234 return
235 235
236 236 startrevidx = 0
237 endrevidx = 0
237 endrevidx = 1
238 238 iterrevs = enumerate(revs)
239 239 next(iterrevs) # skip first rev.
240 240 # first step: get snapshots out of the way
241 241 for idx, r in iterrevs:
242 242 span = revlog.end(r) - startdata
243 243 snapshot = revlog.issnapshot(r)
244 244 if span <= targetsize and snapshot:
245 endrevidx = idx
245 endrevidx = idx + 1
246 246 else:
247 chunk = _trimchunk(revlog, revs, startrevidx, endrevidx + 1)
247 chunk = _trimchunk(revlog, revs, startrevidx, endrevidx)
248 248 if chunk:
249 249 yield chunk
250 250 startrevidx = idx
251 251 startdata = revlog.start(r)
252 endrevidx = idx
252 endrevidx = idx + 1
253 253 if not snapshot:
254 254 break
255 255
256 256 # for the others, we use binary slicing to quickly converge toward valid
257 257 # chunks (otherwise, we might end up looking for start/end of many
258 258 # revisions). This logic is not looking for the perfect slicing point, it
259 259 # focuses on quickly converging toward valid chunks.
260 260 nbitem = len(revs)
261 261 while (enddata - startdata) > targetsize:
262 262 endrevidx = nbitem
263 263 if nbitem - startrevidx <= 1:
264 264 break # protect against individual chunk larger than limit
265 265 localenddata = revlog.end(revs[endrevidx - 1])
266 266 span = localenddata - startdata
267 267 while span > targetsize:
268 268 if endrevidx - startrevidx <= 1:
269 269 break # protect against individual chunk larger than limit
270 270 endrevidx -= (endrevidx - startrevidx) // 2
271 271 localenddata = revlog.end(revs[endrevidx - 1])
272 272 span = localenddata - startdata
273 273 chunk = _trimchunk(revlog, revs, startrevidx, endrevidx)
274 274 if chunk:
275 275 yield chunk
276 276 startrevidx = endrevidx
277 277 startdata = revlog.start(revs[startrevidx])
278 278
279 279 chunk = _trimchunk(revlog, revs, startrevidx)
280 280 if chunk:
281 281 yield chunk
282 282
283 283 def _slicechunktodensity(revlog, revs, targetdensity=0.5,
284 284 mingapsize=0):
285 285 """slice revs to reduce the amount of unrelated data to be read from disk.
286 286
287 287 ``revs`` is sliced into groups that should be read in one time.
288 288 Assume that revs are sorted.
289 289
290 290 The initial chunk is sliced until the overall density (payload/chunks-span
291 291 ratio) is above `targetdensity`. No gap smaller than `mingapsize` is
292 292 skipped.
293 293
294 294 >>> revlog = _testrevlog([
295 295 ... 5, #00 (5)
296 296 ... 10, #01 (5)
297 297 ... 12, #02 (2)
298 298 ... 12, #03 (empty)
299 299 ... 27, #04 (15)
300 300 ... 31, #05 (4)
301 301 ... 31, #06 (empty)
302 302 ... 42, #07 (11)
303 303 ... 47, #08 (5)
304 304 ... 47, #09 (empty)
305 305 ... 48, #10 (1)
306 306 ... 51, #11 (3)
307 307 ... 74, #12 (23)
308 308 ... 85, #13 (11)
309 309 ... 86, #14 (1)
310 310 ... 91, #15 (5)
311 311 ... ])
312 312
313 313 >>> list(_slicechunktodensity(revlog, list(range(16))))
314 314 [[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]]
315 315 >>> list(_slicechunktodensity(revlog, [0, 15]))
316 316 [[0], [15]]
317 317 >>> list(_slicechunktodensity(revlog, [0, 11, 15]))
318 318 [[0], [11], [15]]
319 319 >>> list(_slicechunktodensity(revlog, [0, 11, 13, 15]))
320 320 [[0], [11, 13, 15]]
321 321 >>> list(_slicechunktodensity(revlog, [1, 2, 3, 5, 8, 10, 11, 14]))
322 322 [[1, 2], [5, 8, 10, 11], [14]]
323 323 >>> list(_slicechunktodensity(revlog, [1, 2, 3, 5, 8, 10, 11, 14],
324 324 ... mingapsize=20))
325 325 [[1, 2, 3, 5, 8, 10, 11], [14]]
326 326 >>> list(_slicechunktodensity(revlog, [1, 2, 3, 5, 8, 10, 11, 14],
327 327 ... targetdensity=0.95))
328 328 [[1, 2], [5], [8, 10, 11], [14]]
329 329 >>> list(_slicechunktodensity(revlog, [1, 2, 3, 5, 8, 10, 11, 14],
330 330 ... targetdensity=0.95, mingapsize=12))
331 331 [[1, 2], [5, 8, 10, 11], [14]]
332 332 """
333 333 start = revlog.start
334 334 length = revlog.length
335 335
336 336 if len(revs) <= 1:
337 337 yield revs
338 338 return
339 339
340 340 deltachainspan = segmentspan(revlog, revs)
341 341
342 342 if deltachainspan < mingapsize:
343 343 yield revs
344 344 return
345 345
346 346 readdata = deltachainspan
347 347 chainpayload = sum(length(r) for r in revs)
348 348
349 349 if deltachainspan:
350 350 density = chainpayload / float(deltachainspan)
351 351 else:
352 352 density = 1.0
353 353
354 354 if density >= targetdensity:
355 355 yield revs
356 356 return
357 357
358 358 # Store the gaps in a heap to have them sorted by decreasing size
359 359 gaps = []
360 360 prevend = None
361 361 for i, rev in enumerate(revs):
362 362 revstart = start(rev)
363 363 revlen = length(rev)
364 364
365 365 # Skip empty revisions to form larger holes
366 366 if revlen == 0:
367 367 continue
368 368
369 369 if prevend is not None:
370 370 gapsize = revstart - prevend
371 371 # only consider holes that are large enough
372 372 if gapsize > mingapsize:
373 373 gaps.append((gapsize, i))
374 374
375 375 prevend = revstart + revlen
376 376 # sort the gaps to pop them from largest to small
377 377 gaps.sort()
378 378
379 379 # Collect the indices of the largest holes until the density is acceptable
380 380 selected = []
381 381 while gaps and density < targetdensity:
382 382 gapsize, gapidx = gaps.pop()
383 383
384 384 selected.append(gapidx)
385 385
386 386 # the gap sizes are stored as negatives to be sorted decreasingly
387 387 # by the heap
388 388 readdata -= gapsize
389 389 if readdata > 0:
390 390 density = chainpayload / float(readdata)
391 391 else:
392 392 density = 1.0
393 393 selected.sort()
394 394
395 395 # Cut the revs at collected indices
396 396 previdx = 0
397 397 for idx in selected:
398 398
399 399 chunk = _trimchunk(revlog, revs, previdx, idx)
400 400 if chunk:
401 401 yield chunk
402 402
403 403 previdx = idx
404 404
405 405 chunk = _trimchunk(revlog, revs, previdx)
406 406 if chunk:
407 407 yield chunk
408 408
409 409 def _trimchunk(revlog, revs, startidx, endidx=None):
410 410 """returns revs[startidx:endidx] without empty trailing revs
411 411
412 412 Doctest Setup
413 413 >>> revlog = _testrevlog([
414 414 ... 5, #0
415 415 ... 10, #1
416 416 ... 12, #2
417 417 ... 12, #3 (empty)
418 418 ... 17, #4
419 419 ... 21, #5
420 420 ... 21, #6 (empty)
421 421 ... ])
422 422
423 423 Contiguous cases:
424 424 >>> _trimchunk(revlog, [0, 1, 2, 3, 4, 5, 6], 0)
425 425 [0, 1, 2, 3, 4, 5]
426 426 >>> _trimchunk(revlog, [0, 1, 2, 3, 4, 5, 6], 0, 5)
427 427 [0, 1, 2, 3, 4]
428 428 >>> _trimchunk(revlog, [0, 1, 2, 3, 4, 5, 6], 0, 4)
429 429 [0, 1, 2]
430 430 >>> _trimchunk(revlog, [0, 1, 2, 3, 4, 5, 6], 2, 4)
431 431 [2]
432 432 >>> _trimchunk(revlog, [0, 1, 2, 3, 4, 5, 6], 3)
433 433 [3, 4, 5]
434 434 >>> _trimchunk(revlog, [0, 1, 2, 3, 4, 5, 6], 3, 5)
435 435 [3, 4]
436 436
437 437 Discontiguous cases:
438 438 >>> _trimchunk(revlog, [1, 3, 5, 6], 0)
439 439 [1, 3, 5]
440 440 >>> _trimchunk(revlog, [1, 3, 5, 6], 0, 2)
441 441 [1]
442 442 >>> _trimchunk(revlog, [1, 3, 5, 6], 1, 3)
443 443 [3, 5]
444 444 >>> _trimchunk(revlog, [1, 3, 5, 6], 1)
445 445 [3, 5]
446 446 """
447 447 length = revlog.length
448 448
449 449 if endidx is None:
450 450 endidx = len(revs)
451 451
452 452 # If we have a non-emtpy delta candidate, there are nothing to trim
453 453 if revs[endidx - 1] < len(revlog):
454 454 # Trim empty revs at the end, except the very first revision of a chain
455 455 while (endidx > 1
456 456 and endidx > startidx
457 457 and length(revs[endidx - 1]) == 0):
458 458 endidx -= 1
459 459
460 460 return revs[startidx:endidx]
461 461
462 462 def segmentspan(revlog, revs):
463 463 """Get the byte span of a segment of revisions
464 464
465 465 revs is a sorted array of revision numbers
466 466
467 467 >>> revlog = _testrevlog([
468 468 ... 5, #0
469 469 ... 10, #1
470 470 ... 12, #2
471 471 ... 12, #3 (empty)
472 472 ... 17, #4
473 473 ... ])
474 474
475 475 >>> segmentspan(revlog, [0, 1, 2, 3, 4])
476 476 17
477 477 >>> segmentspan(revlog, [0, 4])
478 478 17
479 479 >>> segmentspan(revlog, [3, 4])
480 480 5
481 481 >>> segmentspan(revlog, [1, 2, 3,])
482 482 7
483 483 >>> segmentspan(revlog, [1, 3])
484 484 7
485 485 """
486 486 if not revs:
487 487 return 0
488 488 end = revlog.end(revs[-1])
489 489 return end - revlog.start(revs[0])
490 490
491 491 def _textfromdelta(fh, revlog, baserev, delta, p1, p2, flags, expectednode):
492 492 """build full text from a (base, delta) pair and other metadata"""
493 493 # special case deltas which replace entire base; no need to decode
494 494 # base revision. this neatly avoids censored bases, which throw when
495 495 # they're decoded.
496 496 hlen = struct.calcsize(">lll")
497 497 if delta[:hlen] == mdiff.replacediffheader(revlog.rawsize(baserev),
498 498 len(delta) - hlen):
499 499 fulltext = delta[hlen:]
500 500 else:
501 501 # deltabase is rawtext before changed by flag processors, which is
502 502 # equivalent to non-raw text
503 503 basetext = revlog.revision(baserev, _df=fh, raw=False)
504 504 fulltext = mdiff.patch(basetext, delta)
505 505
506 506 try:
507 507 res = revlog._processflags(fulltext, flags, 'read', raw=True)
508 508 fulltext, validatehash = res
509 509 if validatehash:
510 510 revlog.checkhash(fulltext, expectednode, p1=p1, p2=p2)
511 511 if flags & REVIDX_ISCENSORED:
512 512 raise error.StorageError(_('node %s is not censored') %
513 513 expectednode)
514 514 except error.CensoredNodeError:
515 515 # must pass the censored index flag to add censored revisions
516 516 if not flags & REVIDX_ISCENSORED:
517 517 raise
518 518 return fulltext
519 519
520 520 @attr.s(slots=True, frozen=True)
521 521 class _deltainfo(object):
522 522 distance = attr.ib()
523 523 deltalen = attr.ib()
524 524 data = attr.ib()
525 525 base = attr.ib()
526 526 chainbase = attr.ib()
527 527 chainlen = attr.ib()
528 528 compresseddeltalen = attr.ib()
529 529 snapshotdepth = attr.ib()
530 530
531 531 def isgooddeltainfo(revlog, deltainfo, revinfo):
532 532 """Returns True if the given delta is good. Good means that it is within
533 533 the disk span, disk size, and chain length bounds that we know to be
534 534 performant."""
535 535 if deltainfo is None:
536 536 return False
537 537
538 538 # - 'deltainfo.distance' is the distance from the base revision --
539 539 # bounding it limits the amount of I/O we need to do.
540 540 # - 'deltainfo.compresseddeltalen' is the sum of the total size of
541 541 # deltas we need to apply -- bounding it limits the amount of CPU
542 542 # we consume.
543 543
544 544 textlen = revinfo.textlen
545 545 defaultmax = textlen * 4
546 546 maxdist = revlog._maxdeltachainspan
547 547 if not maxdist:
548 548 maxdist = deltainfo.distance # ensure the conditional pass
549 549 maxdist = max(maxdist, defaultmax)
550 550
551 551 # Bad delta from read span:
552 552 #
553 553 # If the span of data read is larger than the maximum allowed.
554 554 #
555 555 # In the sparse-revlog case, we rely on the associated "sparse reading"
556 556 # to avoid issue related to the span of data. In theory, it would be
557 557 # possible to build pathological revlog where delta pattern would lead
558 558 # to too many reads. However, they do not happen in practice at all. So
559 559 # we skip the span check entirely.
560 560 if not revlog._sparserevlog and maxdist < deltainfo.distance:
561 561 return False
562 562
563 563 # Bad delta from new delta size:
564 564 #
565 565 # If the delta size is larger than the target text, storing the
566 566 # delta will be inefficient.
567 567 if textlen < deltainfo.deltalen:
568 568 return False
569 569
570 570 # Bad delta from cumulated payload size:
571 571 #
572 572 # If the sum of delta get larger than K * target text length.
573 573 if textlen * LIMIT_DELTA2TEXT < deltainfo.compresseddeltalen:
574 574 return False
575 575
576 576 # Bad delta from chain length:
577 577 #
578 578 # If the number of delta in the chain gets too high.
579 579 if (revlog._maxchainlen
580 580 and revlog._maxchainlen < deltainfo.chainlen):
581 581 return False
582 582
583 583 # bad delta from intermediate snapshot size limit
584 584 #
585 585 # If an intermediate snapshot size is higher than the limit. The
586 586 # limit exist to prevent endless chain of intermediate delta to be
587 587 # created.
588 588 if (deltainfo.snapshotdepth is not None and
589 589 (textlen >> deltainfo.snapshotdepth) < deltainfo.deltalen):
590 590 return False
591 591
592 592 # bad delta if new intermediate snapshot is larger than the previous
593 593 # snapshot
594 594 if (deltainfo.snapshotdepth
595 595 and revlog.length(deltainfo.base) < deltainfo.deltalen):
596 596 return False
597 597
598 598 return True
599 599
600 600 def _candidategroups(revlog, textlen, p1, p2, cachedelta):
601 601 """Provides group of revision to be tested as delta base
602 602
603 603 This top level function focus on emitting groups with unique and worthwhile
604 604 content. See _raw_candidate_groups for details about the group order.
605 605 """
606 606 # should we try to build a delta?
607 607 if not (len(revlog) and revlog._storedeltachains):
608 608 yield None
609 609 return
610 610
611 611 deltalength = revlog.length
612 612 deltaparent = revlog.deltaparent
613 613 good = None
614 614
615 615 deltas_limit = textlen * LIMIT_DELTA2TEXT
616 616
617 617 tested = set([nullrev])
618 618 candidates = _refinedgroups(revlog, p1, p2, cachedelta)
619 619 while True:
620 620 temptative = candidates.send(good)
621 621 if temptative is None:
622 622 break
623 623 group = []
624 624 for rev in temptative:
625 625 # skip over empty delta (no need to include them in a chain)
626 626 while (revlog._generaldelta
627 627 and not (rev == nullrev
628 628 or rev in tested
629 629 or deltalength(rev))):
630 630 tested.add(rev)
631 631 rev = deltaparent(rev)
632 632 # filter out revision we tested already
633 633 if rev in tested:
634 634 continue
635 635 tested.add(rev)
636 636 # filter out delta base that will never produce good delta
637 637 if deltas_limit < revlog.length(rev):
638 638 continue
639 639 # no need to try a delta against nullrev, this will be done as a
640 640 # last resort.
641 641 if rev == nullrev:
642 642 continue
643 643 # no delta for rawtext-changing revs (see "candelta" for why)
644 644 if revlog.flags(rev) & REVIDX_RAWTEXT_CHANGING_FLAGS:
645 645 continue
646 646 group.append(rev)
647 647 if group:
648 648 # XXX: in the sparse revlog case, group can become large,
649 649 # impacting performances. Some bounding or slicing mecanism
650 650 # would help to reduce this impact.
651 651 good = yield tuple(group)
652 652 yield None
653 653
654 654 def _findsnapshots(revlog, cache, start_rev):
655 655 """find snapshot from start_rev to tip"""
656 656 deltaparent = revlog.deltaparent
657 657 issnapshot = revlog.issnapshot
658 658 for rev in revlog.revs(start_rev):
659 659 if issnapshot(rev):
660 660 cache[deltaparent(rev)].append(rev)
661 661
662 662 def _refinedgroups(revlog, p1, p2, cachedelta):
663 663 good = None
664 664 # First we try to reuse a the delta contained in the bundle.
665 665 # (or from the source revlog)
666 666 #
667 667 # This logic only applies to general delta repositories and can be disabled
668 668 # through configuration. Disabling reuse source delta is useful when
669 669 # we want to make sure we recomputed "optimal" deltas.
670 670 if cachedelta and revlog._generaldelta and revlog._lazydeltabase:
671 671 # Assume what we received from the server is a good choice
672 672 # build delta will reuse the cache
673 673 good = yield (cachedelta[0],)
674 674 if good is not None:
675 675 yield None
676 676 return
677 677 for candidates in _rawgroups(revlog, p1, p2, cachedelta):
678 678 good = yield candidates
679 679 if good is not None:
680 680 break
681 681
682 682 # If sparse revlog is enabled, we can try to refine the available deltas
683 683 if not revlog._sparserevlog:
684 684 yield None
685 685 return
686 686
687 687 # if we have a refinable value, try to refine it
688 688 if good is not None and good not in (p1, p2) and revlog.issnapshot(good):
689 689 # refine snapshot down
690 690 previous = None
691 691 while previous != good:
692 692 previous = good
693 693 base = revlog.deltaparent(good)
694 694 if base == nullrev:
695 695 break
696 696 good = yield (base,)
697 697 # refine snapshot up
698 698 #
699 699 # XXX the _findsnapshots call can be expensive and is "duplicated" with
700 700 # the one done in `_rawgroups`. Once we start working on performance,
701 701 # we should make the two logics share this computation.
702 702 snapshots = collections.defaultdict(list)
703 703 _findsnapshots(revlog, snapshots, good + 1)
704 704 previous = None
705 705 while good != previous:
706 706 previous = good
707 707 children = tuple(sorted(c for c in snapshots[good]))
708 708 good = yield children
709 709
710 710 # we have found nothing
711 711 yield None
712 712
713 713 def _rawgroups(revlog, p1, p2, cachedelta):
714 714 """Provides group of revision to be tested as delta base
715 715
716 716 This lower level function focus on emitting delta theorically interresting
717 717 without looking it any practical details.
718 718
719 719 The group order aims at providing fast or small candidates first.
720 720 """
721 721 gdelta = revlog._generaldelta
722 722 sparse = revlog._sparserevlog
723 723 curr = len(revlog)
724 724 prev = curr - 1
725 725 deltachain = lambda rev: revlog._deltachain(rev)[0]
726 726
727 727 if gdelta:
728 728 # exclude already lazy tested base if any
729 729 parents = [p for p in (p1, p2) if p != nullrev]
730 730
731 731 if not revlog._deltabothparents and len(parents) == 2:
732 732 parents.sort()
733 733 # To minimize the chance of having to build a fulltext,
734 734 # pick first whichever parent is closest to us (max rev)
735 735 yield (parents[1],)
736 736 # then the other one (min rev) if the first did not fit
737 737 yield (parents[0],)
738 738 elif len(parents) > 0:
739 739 # Test all parents (1 or 2), and keep the best candidate
740 740 yield parents
741 741
742 742 if sparse and parents:
743 743 snapshots = collections.defaultdict(list) # map: base-rev: snapshot-rev
744 744 # See if we can use an existing snapshot in the parent chains to use as
745 745 # a base for a new intermediate-snapshot
746 746 #
747 747 # search for snapshot in parents delta chain
748 748 # map: snapshot-level: snapshot-rev
749 749 parents_snaps = collections.defaultdict(set)
750 750 candidate_chains = [deltachain(p) for p in parents]
751 751 for chain in candidate_chains:
752 752 for idx, s in enumerate(chain):
753 753 if not revlog.issnapshot(s):
754 754 break
755 755 parents_snaps[idx].add(s)
756 756 snapfloor = min(parents_snaps[0]) + 1
757 757 _findsnapshots(revlog, snapshots, snapfloor)
758 758 # search for the highest "unrelated" revision
759 759 #
760 760 # Adding snapshots used by "unrelated" revision increase the odd we
761 761 # reuse an independant, yet better snapshot chain.
762 762 #
763 763 # XXX instead of building a set of revisions, we could lazily enumerate
764 764 # over the chains. That would be more efficient, however we stick to
765 765 # simple code for now.
766 766 all_revs = set()
767 767 for chain in candidate_chains:
768 768 all_revs.update(chain)
769 769 other = None
770 770 for r in revlog.revs(prev, snapfloor):
771 771 if r not in all_revs:
772 772 other = r
773 773 break
774 774 if other is not None:
775 775 # To avoid unfair competition, we won't use unrelated intermediate
776 776 # snapshot that are deeper than the ones from the parent delta
777 777 # chain.
778 778 max_depth = max(parents_snaps.keys())
779 779 chain = deltachain(other)
780 780 for idx, s in enumerate(chain):
781 781 if s < snapfloor:
782 782 continue
783 783 if max_depth < idx:
784 784 break
785 785 if not revlog.issnapshot(s):
786 786 break
787 787 parents_snaps[idx].add(s)
788 788 # Test them as possible intermediate snapshot base
789 789 # We test them from highest to lowest level. High level one are more
790 790 # likely to result in small delta
791 791 floor = None
792 792 for idx, snaps in sorted(parents_snaps.items(), reverse=True):
793 793 siblings = set()
794 794 for s in snaps:
795 795 siblings.update(snapshots[s])
796 796 # Before considering making a new intermediate snapshot, we check
797 797 # if an existing snapshot, children of base we consider, would be
798 798 # suitable.
799 799 #
800 800 # It give a change to reuse a delta chain "unrelated" to the
801 801 # current revision instead of starting our own. Without such
802 802 # re-use, topological branches would keep reopening new chains.
803 803 # Creating more and more snapshot as the repository grow.
804 804
805 805 if floor is not None:
806 806 # We only do this for siblings created after the one in our
807 807 # parent's delta chain. Those created before has less chances
808 808 # to be valid base since our ancestors had to create a new
809 809 # snapshot.
810 810 siblings = [r for r in siblings if floor < r]
811 811 yield tuple(sorted(siblings))
812 812 # then test the base from our parent's delta chain.
813 813 yield tuple(sorted(snaps))
814 814 floor = min(snaps)
815 815 # No suitable base found in the parent chain, search if any full
816 816 # snapshots emitted since parent's base would be a suitable base for an
817 817 # intermediate snapshot.
818 818 #
819 819 # It give a chance to reuse a delta chain unrelated to the current
820 820 # revisions instead of starting our own. Without such re-use,
821 821 # topological branches would keep reopening new full chains. Creating
822 822 # more and more snapshot as the repository grow.
823 823 yield tuple(snapshots[nullrev])
824 824
825 825 if not sparse:
826 826 # other approach failed try against prev to hopefully save us a
827 827 # fulltext.
828 828 yield (prev,)
829 829
830 830 class deltacomputer(object):
831 831 def __init__(self, revlog):
832 832 self.revlog = revlog
833 833
834 834 def buildtext(self, revinfo, fh):
835 835 """Builds a fulltext version of a revision
836 836
837 837 revinfo: _revisioninfo instance that contains all needed info
838 838 fh: file handle to either the .i or the .d revlog file,
839 839 depending on whether it is inlined or not
840 840 """
841 841 btext = revinfo.btext
842 842 if btext[0] is not None:
843 843 return btext[0]
844 844
845 845 revlog = self.revlog
846 846 cachedelta = revinfo.cachedelta
847 847 baserev = cachedelta[0]
848 848 delta = cachedelta[1]
849 849
850 850 fulltext = btext[0] = _textfromdelta(fh, revlog, baserev, delta,
851 851 revinfo.p1, revinfo.p2,
852 852 revinfo.flags, revinfo.node)
853 853 return fulltext
854 854
855 855 def _builddeltadiff(self, base, revinfo, fh):
856 856 revlog = self.revlog
857 857 t = self.buildtext(revinfo, fh)
858 858 if revlog.iscensored(base):
859 859 # deltas based on a censored revision must replace the
860 860 # full content in one patch, so delta works everywhere
861 861 header = mdiff.replacediffheader(revlog.rawsize(base), len(t))
862 862 delta = header + t
863 863 else:
864 864 ptext = revlog.revision(base, _df=fh, raw=True)
865 865 delta = mdiff.textdiff(ptext, t)
866 866
867 867 return delta
868 868
869 869 def _builddeltainfo(self, revinfo, base, fh):
870 870 # can we use the cached delta?
871 871 delta = None
872 872 if revinfo.cachedelta:
873 873 cachebase, cachediff = revinfo.cachedelta
874 874 #check if the diff still apply
875 875 currentbase = cachebase
876 876 while (currentbase != nullrev
877 877 and currentbase != base
878 878 and self.revlog.length(currentbase) == 0):
879 879 currentbase = self.revlog.deltaparent(currentbase)
880 880 if currentbase == base:
881 881 delta = revinfo.cachedelta[1]
882 882 if delta is None:
883 883 delta = self._builddeltadiff(base, revinfo, fh)
884 884 revlog = self.revlog
885 885 header, data = revlog.compress(delta)
886 886 deltalen = len(header) + len(data)
887 887 chainbase = revlog.chainbase(base)
888 888 offset = revlog.end(len(revlog) - 1)
889 889 dist = deltalen + offset - revlog.start(chainbase)
890 890 if revlog._generaldelta:
891 891 deltabase = base
892 892 else:
893 893 deltabase = chainbase
894 894 chainlen, compresseddeltalen = revlog._chaininfo(base)
895 895 chainlen += 1
896 896 compresseddeltalen += deltalen
897 897
898 898 revlog = self.revlog
899 899 snapshotdepth = None
900 900 if deltabase == nullrev:
901 901 snapshotdepth = 0
902 902 elif revlog._sparserevlog and revlog.issnapshot(deltabase):
903 903 # A delta chain should always be one full snapshot,
904 904 # zero or more semi-snapshots, and zero or more deltas
905 905 p1, p2 = revlog.rev(revinfo.p1), revlog.rev(revinfo.p2)
906 906 if deltabase not in (p1, p2) and revlog.issnapshot(deltabase):
907 907 snapshotdepth = len(revlog._deltachain(deltabase)[0])
908 908
909 909 return _deltainfo(dist, deltalen, (header, data), deltabase,
910 910 chainbase, chainlen, compresseddeltalen,
911 911 snapshotdepth)
912 912
913 913 def _fullsnapshotinfo(self, fh, revinfo):
914 914 curr = len(self.revlog)
915 915 rawtext = self.buildtext(revinfo, fh)
916 916 data = self.revlog.compress(rawtext)
917 917 compresseddeltalen = deltalen = dist = len(data[1]) + len(data[0])
918 918 deltabase = chainbase = curr
919 919 snapshotdepth = 0
920 920 chainlen = 1
921 921
922 922 return _deltainfo(dist, deltalen, data, deltabase,
923 923 chainbase, chainlen, compresseddeltalen,
924 924 snapshotdepth)
925 925
926 926 def finddeltainfo(self, revinfo, fh):
927 927 """Find an acceptable delta against a candidate revision
928 928
929 929 revinfo: information about the revision (instance of _revisioninfo)
930 930 fh: file handle to either the .i or the .d revlog file,
931 931 depending on whether it is inlined or not
932 932
933 933 Returns the first acceptable candidate revision, as ordered by
934 934 _candidategroups
935 935
936 936 If no suitable deltabase is found, we return delta info for a full
937 937 snapshot.
938 938 """
939 939 if not revinfo.textlen:
940 940 return self._fullsnapshotinfo(fh, revinfo)
941 941
942 942 # no delta for flag processor revision (see "candelta" for why)
943 943 # not calling candelta since only one revision needs test, also to
944 944 # avoid overhead fetching flags again.
945 945 if revinfo.flags & REVIDX_RAWTEXT_CHANGING_FLAGS:
946 946 return self._fullsnapshotinfo(fh, revinfo)
947 947
948 948 cachedelta = revinfo.cachedelta
949 949 p1 = revinfo.p1
950 950 p2 = revinfo.p2
951 951 revlog = self.revlog
952 952
953 953 deltainfo = None
954 954 p1r, p2r = revlog.rev(p1), revlog.rev(p2)
955 955 groups = _candidategroups(self.revlog, revinfo.textlen,
956 956 p1r, p2r, cachedelta)
957 957 candidaterevs = next(groups)
958 958 while candidaterevs is not None:
959 959 nominateddeltas = []
960 960 if deltainfo is not None:
961 961 # if we already found a good delta,
962 962 # challenge it against refined candidates
963 963 nominateddeltas.append(deltainfo)
964 964 for candidaterev in candidaterevs:
965 965 candidatedelta = self._builddeltainfo(revinfo, candidaterev, fh)
966 966 if isgooddeltainfo(self.revlog, candidatedelta, revinfo):
967 967 nominateddeltas.append(candidatedelta)
968 968 if nominateddeltas:
969 969 deltainfo = min(nominateddeltas, key=lambda x: x.deltalen)
970 970 if deltainfo is not None:
971 971 candidaterevs = groups.send(deltainfo.base)
972 972 else:
973 973 candidaterevs = next(groups)
974 974
975 975 if deltainfo is None:
976 976 deltainfo = self._fullsnapshotinfo(fh, revinfo)
977 977 return deltainfo
General Comments 0
You need to be logged in to leave comments. Login now