mercurial-scm/hg-stable: mercurial/revlogutils/deltas.py annotate

annotate mercurial/revlogutils/deltas.py @ 40650:2f7e531ef3e7

sparse-revlog: skip the span check in the sparse-revlog case This significantly improves the performance on unbundling on smaller repositories. Mercurial: unbundling 1K revisions no-sparse-revlog: 500 ms sparse-revlog-before: 689 ms sparse-revlog-after: 484 ms Pypy: unbundling 1K revisions no-sparse-revlog: 1.242 s sparse-revlog-before: 1.135 s sparse-revlog-after: 0.860 s NetBeans: unbundling 1K revisions no-sparse-revlog: 1.386 s sparse-revlog-before: 2.368 s sparse-revlog-after: 1.191 s Mozilla: unbundling 1K revisions no-sparse-revlog: 3.103 s sparse-revlog-before: 3.367 s sparse-revlog-after: 3.093 s

author	Boris Feld <boris.feld@octobus.net>
date	Mon, 15 Oct 2018 15:45:08 +0200
parents	324ba8b14d78
children	3ac23dad6364

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

Mercurial > public > mercurial-scm > hg-stable

annotate mercurial/revlogutils/deltas.py @ 40650:2f7e531ef3e7