mercurial/revlogutils/deltas.py
author Boris Feld <boris.feld@octobus.net>
Fri, 07 Sep 2018 11:17:31 -0400
changeset 39495 6a53842727c1
parent 39494 e72130f58f5d
child 39496 2f9f7889549b
permissions -rw-r--r--
snapshot: consider unrelated snapshots at a similar level first This new step is inserted before considering using a level-N snapshot as a base for a level-N+1 snapshot. We first check if existing level-N+1 snapshots using the same base would be a suitable base for a level-N+2 snapshot. This increases snapshot reuse and limits the risk of snapshot explosion in very branchy repositories. Using a "deeper" snapshot as the base also results in a smaller snapshot since it builds a level-N+2 intermediate snapshot instead of an N+1 one. This logic is similar for the one we added in a previous commit. In that previous commit is only applied to level-0 "siblings". We can see this effect in the test repository. Snapshots moved from lower levels to higher levels.
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
39330
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
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>
39330
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
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.
39330
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
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
39493
3ca144f1c8dd snapshot: search for unrelated but reusable full-snapshot
Boris Feld <boris.feld@octobus.net>
parents: 39492
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
39330
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
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
)
39330
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
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: 39329
diff changeset
    21
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
    22
from .constants import (
39329
729082bb9938 revlog: split constants into a new `revlogutils.constants` module
Boris Feld <boris.feld@octobus.net>
parents: 39232
diff changeset
    23
    REVIDX_ISCENSORED,
729082bb9938 revlog: split constants into a new `revlogutils.constants` module
Boris Feld <boris.feld@octobus.net>
parents: 39232
diff changeset
    24
    REVIDX_RAWTEXT_CHANGING_FLAGS,
729082bb9938 revlog: split constants into a new `revlogutils.constants` module
Boris Feld <boris.feld@octobus.net>
parents: 39232
diff changeset
    25
)
39330
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
    26
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
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
)
39330
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
    30
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
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
7633
08cabecfa8a8 errors: move revlog errors
Matt Mackall <mpm@selenic.com>
parents: 7365
diff changeset
    36
RevlogError = error.RevlogError
22934
8a096d4d0862 revlog: support importing censored file revision tombstones
Mike Edgar <adgar@google.com>
parents: 22785
diff changeset
    37
CensoredNodeError = error.CensoredNodeError
30745
c1b7b2285522 revlog: flag processor
Remi Chaintron <remi@fb.com>
parents: 30744
diff changeset
    38
39330
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
    39
# 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: 39329
diff changeset
    40
LIMIT_DELTA2TEXT = 2
1091
d62130f99a73 Move hash function back to revlog from node
mpm@selenic.com
parents: 1089
diff changeset
    41
38637
e33f784f2a44 revlog: introduce a tiny mock of a revlog class
Boris Feld <boris.feld@octobus.net>
parents: 38636
diff changeset
    42
class _testrevlog(object):
e33f784f2a44 revlog: introduce a tiny mock of a revlog class
Boris Feld <boris.feld@octobus.net>
parents: 38636
diff changeset
    43
    """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
    44
e33f784f2a44 revlog: introduce a tiny mock of a revlog class
Boris Feld <boris.feld@octobus.net>
parents: 38636
diff changeset
    45
    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
    46
        """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
    47
        self._data = data
e33f784f2a44 revlog: introduce a tiny mock of a revlog class
Boris Feld <boris.feld@octobus.net>
parents: 38636
diff changeset
    48
        self._srdensitythreshold = density
e33f784f2a44 revlog: introduce a tiny mock of a revlog class
Boris Feld <boris.feld@octobus.net>
parents: 38636
diff changeset
    49
        self._srmingapsize = mingap
e33f784f2a44 revlog: introduce a tiny mock of a revlog class
Boris Feld <boris.feld@octobus.net>
parents: 38636
diff changeset
    50
e33f784f2a44 revlog: introduce a tiny mock of a revlog class
Boris Feld <boris.feld@octobus.net>
parents: 38636
diff changeset
    51
    def start(self, rev):
e33f784f2a44 revlog: introduce a tiny mock of a revlog class
Boris Feld <boris.feld@octobus.net>
parents: 38636
diff changeset
    52
        if rev == 0:
e33f784f2a44 revlog: introduce a tiny mock of a revlog class
Boris Feld <boris.feld@octobus.net>
parents: 38636
diff changeset
    53
            return 0
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 - 1]
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 end(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._data[rev]
e33f784f2a44 revlog: introduce a tiny mock of a revlog class
Boris Feld <boris.feld@octobus.net>
parents: 38636
diff changeset
    58
e33f784f2a44 revlog: introduce a tiny mock of a revlog class
Boris Feld <boris.feld@octobus.net>
parents: 38636
diff changeset
    59
    def length(self, rev):
e33f784f2a44 revlog: introduce a tiny mock of a revlog class
Boris Feld <boris.feld@octobus.net>
parents: 38636
diff changeset
    60
        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
    61
38718
f8762ea73e0d sparse-revlog: implement algorithm to write sparse delta chains (issue5480)
Paul Morelle <paul.morelle@octobus.net>
parents: 38717
diff changeset
    62
    def __len__(self):
f8762ea73e0d sparse-revlog: implement algorithm to write sparse delta chains (issue5480)
Paul Morelle <paul.morelle@octobus.net>
parents: 38717
diff changeset
    63
        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
    64
39330
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
    65
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
    66
    """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
    67
e2ad93bcc084 revlog: introduce an experimental flag to slice chunks reads when too sparse
Paul Morelle <paul.morelle@octobus.net>
parents: 34823
diff changeset
    68
    ``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
    69
    Assume that revs are sorted.
38640
f62b8fb0a484 revlog: document and test _slicechunk
Boris Feld <boris.feld@octobus.net>
parents: 38639
diff changeset
    70
f62b8fb0a484 revlog: document and test _slicechunk
Boris Feld <boris.feld@octobus.net>
parents: 38639
diff changeset
    71
    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
    72
    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
    73
    `revlog._srmingapsize` is skipped.
f62b8fb0a484 revlog: document and test _slicechunk
Boris Feld <boris.feld@octobus.net>
parents: 38639
diff changeset
    74
38643
967fee55e8d9 revlog: postprocess chunk to slice them down to a certain size
Boris Feld <boris.feld@octobus.net>
parents: 38642
diff changeset
    75
    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
    76
    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
    77
    `revlog._srmingapsize`.
967fee55e8d9 revlog: postprocess chunk to slice them down to a certain size
Boris Feld <boris.feld@octobus.net>
parents: 38642
diff changeset
    78
967fee55e8d9 revlog: postprocess chunk to slice them down to a certain size
Boris Feld <boris.feld@octobus.net>
parents: 38642
diff changeset
    79
    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
    80
    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
    81
38640
f62b8fb0a484 revlog: document and test _slicechunk
Boris Feld <boris.feld@octobus.net>
parents: 38639
diff changeset
    82
    >>> revlog = _testrevlog([
f62b8fb0a484 revlog: document and test _slicechunk
Boris Feld <boris.feld@octobus.net>
parents: 38639
diff changeset
    83
    ...  5,  #00 (5)
f62b8fb0a484 revlog: document and test _slicechunk
Boris Feld <boris.feld@octobus.net>
parents: 38639
diff changeset
    84
    ...  10, #01 (5)
f62b8fb0a484 revlog: document and test _slicechunk
Boris Feld <boris.feld@octobus.net>
parents: 38639
diff changeset
    85
    ...  12, #02 (2)
f62b8fb0a484 revlog: document and test _slicechunk
Boris Feld <boris.feld@octobus.net>
parents: 38639
diff changeset
    86
    ...  12, #03 (empty)
f62b8fb0a484 revlog: document and test _slicechunk
Boris Feld <boris.feld@octobus.net>
parents: 38639
diff changeset
    87
    ...  27, #04 (15)
f62b8fb0a484 revlog: document and test _slicechunk
Boris Feld <boris.feld@octobus.net>
parents: 38639
diff changeset
    88
    ...  31, #05 (4)
f62b8fb0a484 revlog: document and test _slicechunk
Boris Feld <boris.feld@octobus.net>
parents: 38639
diff changeset
    89
    ...  31, #06 (empty)
f62b8fb0a484 revlog: document and test _slicechunk
Boris Feld <boris.feld@octobus.net>
parents: 38639
diff changeset
    90
    ...  42, #07 (11)
f62b8fb0a484 revlog: document and test _slicechunk
Boris Feld <boris.feld@octobus.net>
parents: 38639
diff changeset
    91
    ...  47, #08 (5)
f62b8fb0a484 revlog: document and test _slicechunk
Boris Feld <boris.feld@octobus.net>
parents: 38639
diff changeset
    92
    ...  47, #09 (empty)
f62b8fb0a484 revlog: document and test _slicechunk
Boris Feld <boris.feld@octobus.net>
parents: 38639
diff changeset
    93
    ...  48, #10 (1)
f62b8fb0a484 revlog: document and test _slicechunk
Boris Feld <boris.feld@octobus.net>
parents: 38639
diff changeset
    94
    ...  51, #11 (3)
f62b8fb0a484 revlog: document and test _slicechunk
Boris Feld <boris.feld@octobus.net>
parents: 38639
diff changeset
    95
    ...  74, #12 (23)
f62b8fb0a484 revlog: document and test _slicechunk
Boris Feld <boris.feld@octobus.net>
parents: 38639
diff changeset
    96
    ...  85, #13 (11)
f62b8fb0a484 revlog: document and test _slicechunk
Boris Feld <boris.feld@octobus.net>
parents: 38639
diff changeset
    97
    ...  86, #14 (1)
f62b8fb0a484 revlog: document and test _slicechunk
Boris Feld <boris.feld@octobus.net>
parents: 38639
diff changeset
    98
    ...  91, #15 (5)
f62b8fb0a484 revlog: document and test _slicechunk
Boris Feld <boris.feld@octobus.net>
parents: 38639
diff changeset
    99
    ... ])
f62b8fb0a484 revlog: document and test _slicechunk
Boris Feld <boris.feld@octobus.net>
parents: 38639
diff changeset
   100
39330
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   101
    >>> list(slicechunk(revlog, list(range(16))))
38640
f62b8fb0a484 revlog: document and test _slicechunk
Boris Feld <boris.feld@octobus.net>
parents: 38639
diff changeset
   102
    [[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]]
39330
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   103
    >>> list(slicechunk(revlog, [0, 15]))
38640
f62b8fb0a484 revlog: document and test _slicechunk
Boris Feld <boris.feld@octobus.net>
parents: 38639
diff changeset
   104
    [[0], [15]]
39330
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   105
    >>> list(slicechunk(revlog, [0, 11, 15]))
38640
f62b8fb0a484 revlog: document and test _slicechunk
Boris Feld <boris.feld@octobus.net>
parents: 38639
diff changeset
   106
    [[0], [11], [15]]
39330
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   107
    >>> list(slicechunk(revlog, [0, 11, 13, 15]))
38640
f62b8fb0a484 revlog: document and test _slicechunk
Boris Feld <boris.feld@octobus.net>
parents: 38639
diff changeset
   108
    [[0], [11, 13, 15]]
39330
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   109
    >>> 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
   110
    [[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
   111
967fee55e8d9 revlog: postprocess chunk to slice them down to a certain size
Boris Feld <boris.feld@octobus.net>
parents: 38642
diff changeset
   112
    Slicing with a maximum chunk size
39330
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   113
    >>> 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
   114
    [[0], [11], [13], [15]]
39330
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   115
    >>> 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
   116
    [[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
   117
    """
38643
967fee55e8d9 revlog: postprocess chunk to slice them down to a certain size
Boris Feld <boris.feld@octobus.net>
parents: 38642
diff changeset
   118
    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
   119
        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
   120
    # 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
   121
    # * 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
   122
    # * 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
   123
    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
   124
        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
   125
        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
   126
    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
   127
                                      deltainfo,
38641
feba6be0941b revlog: extract density based slicing into its own function
Boris Feld <boris.feld@octobus.net>
parents: 38640
diff changeset
   128
                                      revlog._srdensitythreshold,
feba6be0941b revlog: extract density based slicing into its own function
Boris Feld <boris.feld@octobus.net>
parents: 38640
diff changeset
   129
                                      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
   130
        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
   131
            yield subchunk
38641
feba6be0941b revlog: extract density based slicing into its own function
Boris Feld <boris.feld@octobus.net>
parents: 38640
diff changeset
   132
38718
f8762ea73e0d sparse-revlog: implement algorithm to write sparse delta chains (issue5480)
Paul Morelle <paul.morelle@octobus.net>
parents: 38717
diff changeset
   133
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
   134
    """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
   135
e59e27e52297 revlog: add function to slice chunk down to a given size
Boris Feld <boris.feld@octobus.net>
parents: 38641
diff changeset
   136
    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
   137
    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
   138
    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
   139
    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
   140
e59e27e52297 revlog: add function to slice chunk down to a given size
Boris Feld <boris.feld@octobus.net>
parents: 38641
diff changeset
   141
    >>> revlog = _testrevlog([
e59e27e52297 revlog: add function to slice chunk down to a given size
Boris Feld <boris.feld@octobus.net>
parents: 38641
diff changeset
   142
    ...  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
   143
    ...  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
   144
    ...  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
   145
    ...  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
   146
    ...  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
   147
    ...  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
   148
    ...  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
   149
    ...  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
   150
    ...  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
   151
    ... ])
e59e27e52297 revlog: add function to slice chunk down to a given size
Boris Feld <boris.feld@octobus.net>
parents: 38641
diff changeset
   152
e59e27e52297 revlog: add function to slice chunk down to a given size
Boris Feld <boris.feld@octobus.net>
parents: 38641
diff changeset
   153
    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
   154
    >>> 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
   155
    [[0]]
e59e27e52297 revlog: add function to slice chunk down to a given size
Boris Feld <boris.feld@octobus.net>
parents: 38641
diff changeset
   156
    >>> 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
   157
    [[6, 7]]
e59e27e52297 revlog: add function to slice chunk down to a given size
Boris Feld <boris.feld@octobus.net>
parents: 38641
diff changeset
   158
    >>> 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
   159
    [[0]]
e59e27e52297 revlog: add function to slice chunk down to a given size
Boris Feld <boris.feld@octobus.net>
parents: 38641
diff changeset
   160
    >>> 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
   161
    [[6, 7]]
e59e27e52297 revlog: add function to slice chunk down to a given size
Boris Feld <boris.feld@octobus.net>
parents: 38641
diff changeset
   162
e59e27e52297 revlog: add function to slice chunk down to a given size
Boris Feld <boris.feld@octobus.net>
parents: 38641
diff changeset
   163
    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
   164
    >>> 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
   165
    [[0], [1]]
e59e27e52297 revlog: add function to slice chunk down to a given size
Boris Feld <boris.feld@octobus.net>
parents: 38641
diff changeset
   166
    >>> 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
   167
    [[1], [3]]
e59e27e52297 revlog: add function to slice chunk down to a given size
Boris Feld <boris.feld@octobus.net>
parents: 38641
diff changeset
   168
    >>> 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
   169
    [[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
   170
    >>> 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
   171
    [[3], [5]]
e59e27e52297 revlog: add function to slice chunk down to a given size
Boris Feld <boris.feld@octobus.net>
parents: 38641
diff changeset
   172
    >>> 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
   173
    [[3], [5]]
e59e27e52297 revlog: add function to slice chunk down to a given size
Boris Feld <boris.feld@octobus.net>
parents: 38641
diff changeset
   174
    >>> 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
   175
    [[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
   176
    >>> 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
   177
    [[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
   178
e59e27e52297 revlog: add function to slice chunk down to a given size
Boris Feld <boris.feld@octobus.net>
parents: 38641
diff changeset
   179
    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
   180
    >>> 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
   181
    [[0], [1]]
e59e27e52297 revlog: add function to slice chunk down to a given size
Boris Feld <boris.feld@octobus.net>
parents: 38641
diff changeset
   182
    >>> 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
   183
    [[1], [3]]
e59e27e52297 revlog: add function to slice chunk down to a given size
Boris Feld <boris.feld@octobus.net>
parents: 38641
diff changeset
   184
    >>> 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
   185
    [[3], [5]]
e59e27e52297 revlog: add function to slice chunk down to a given size
Boris Feld <boris.feld@octobus.net>
parents: 38641
diff changeset
   186
    """
e59e27e52297 revlog: add function to slice chunk down to a given size
Boris Feld <boris.feld@octobus.net>
parents: 38641
diff changeset
   187
    assert targetsize is None or 0 <= targetsize
39330
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   188
    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
   189
        yield revs
e59e27e52297 revlog: add function to slice chunk down to a given size
Boris Feld <boris.feld@octobus.net>
parents: 38641
diff changeset
   190
        return
e59e27e52297 revlog: add function to slice chunk down to a given size
Boris Feld <boris.feld@octobus.net>
parents: 38641
diff changeset
   191
e59e27e52297 revlog: add function to slice chunk down to a given size
Boris Feld <boris.feld@octobus.net>
parents: 38641
diff changeset
   192
    startrevidx = 0
e59e27e52297 revlog: add function to slice chunk down to a given size
Boris Feld <boris.feld@octobus.net>
parents: 38641
diff changeset
   193
    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
   194
    endrevidx = 0
e59e27e52297 revlog: add function to slice chunk down to a given size
Boris Feld <boris.feld@octobus.net>
parents: 38641
diff changeset
   195
    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
   196
    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
   197
    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
   198
        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
   199
        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
   200
            endrevidx = idx
e59e27e52297 revlog: add function to slice chunk down to a given size
Boris Feld <boris.feld@octobus.net>
parents: 38641
diff changeset
   201
        else:
e59e27e52297 revlog: add function to slice chunk down to a given size
Boris Feld <boris.feld@octobus.net>
parents: 38641
diff changeset
   202
            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
   203
            if chunk:
e59e27e52297 revlog: add function to slice chunk down to a given size
Boris Feld <boris.feld@octobus.net>
parents: 38641
diff changeset
   204
                yield chunk
e59e27e52297 revlog: add function to slice chunk down to a given size
Boris Feld <boris.feld@octobus.net>
parents: 38641
diff changeset
   205
            startrevidx = idx
e59e27e52297 revlog: add function to slice chunk down to a given size
Boris Feld <boris.feld@octobus.net>
parents: 38641
diff changeset
   206
            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
   207
            endrevidx = idx
e59e27e52297 revlog: add function to slice chunk down to a given size
Boris Feld <boris.feld@octobus.net>
parents: 38641
diff changeset
   208
    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
   209
38718
f8762ea73e0d sparse-revlog: implement algorithm to write sparse delta chains (issue5480)
Paul Morelle <paul.morelle@octobus.net>
parents: 38717
diff changeset
   210
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
   211
                         mingapsize=0):
38641
feba6be0941b revlog: extract density based slicing into its own function
Boris Feld <boris.feld@octobus.net>
parents: 38640
diff changeset
   212
    """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
   213
feba6be0941b revlog: extract density based slicing into its own function
Boris Feld <boris.feld@octobus.net>
parents: 38640
diff changeset
   214
    ``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
   215
    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
   216
38718
f8762ea73e0d sparse-revlog: implement algorithm to write sparse delta chains (issue5480)
Paul Morelle <paul.morelle@octobus.net>
parents: 38717
diff changeset
   217
    ``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
   218
    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
   219
38641
feba6be0941b revlog: extract density based slicing into its own function
Boris Feld <boris.feld@octobus.net>
parents: 38640
diff changeset
   220
    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
   221
    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
   222
    skipped.
feba6be0941b revlog: extract density based slicing into its own function
Boris Feld <boris.feld@octobus.net>
parents: 38640
diff changeset
   223
feba6be0941b revlog: extract density based slicing into its own function
Boris Feld <boris.feld@octobus.net>
parents: 38640
diff changeset
   224
    >>> revlog = _testrevlog([
feba6be0941b revlog: extract density based slicing into its own function
Boris Feld <boris.feld@octobus.net>
parents: 38640
diff changeset
   225
    ...  5,  #00 (5)
feba6be0941b revlog: extract density based slicing into its own function
Boris Feld <boris.feld@octobus.net>
parents: 38640
diff changeset
   226
    ...  10, #01 (5)
feba6be0941b revlog: extract density based slicing into its own function
Boris Feld <boris.feld@octobus.net>
parents: 38640
diff changeset
   227
    ...  12, #02 (2)
feba6be0941b revlog: extract density based slicing into its own function
Boris Feld <boris.feld@octobus.net>
parents: 38640
diff changeset
   228
    ...  12, #03 (empty)
feba6be0941b revlog: extract density based slicing into its own function
Boris Feld <boris.feld@octobus.net>
parents: 38640
diff changeset
   229
    ...  27, #04 (15)
feba6be0941b revlog: extract density based slicing into its own function
Boris Feld <boris.feld@octobus.net>
parents: 38640
diff changeset
   230
    ...  31, #05 (4)
feba6be0941b revlog: extract density based slicing into its own function
Boris Feld <boris.feld@octobus.net>
parents: 38640
diff changeset
   231
    ...  31, #06 (empty)
feba6be0941b revlog: extract density based slicing into its own function
Boris Feld <boris.feld@octobus.net>
parents: 38640
diff changeset
   232
    ...  42, #07 (11)
feba6be0941b revlog: extract density based slicing into its own function
Boris Feld <boris.feld@octobus.net>
parents: 38640
diff changeset
   233
    ...  47, #08 (5)
feba6be0941b revlog: extract density based slicing into its own function
Boris Feld <boris.feld@octobus.net>
parents: 38640
diff changeset
   234
    ...  47, #09 (empty)
feba6be0941b revlog: extract density based slicing into its own function
Boris Feld <boris.feld@octobus.net>
parents: 38640
diff changeset
   235
    ...  48, #10 (1)
feba6be0941b revlog: extract density based slicing into its own function
Boris Feld <boris.feld@octobus.net>
parents: 38640
diff changeset
   236
    ...  51, #11 (3)
feba6be0941b revlog: extract density based slicing into its own function
Boris Feld <boris.feld@octobus.net>
parents: 38640
diff changeset
   237
    ...  74, #12 (23)
feba6be0941b revlog: extract density based slicing into its own function
Boris Feld <boris.feld@octobus.net>
parents: 38640
diff changeset
   238
    ...  85, #13 (11)
feba6be0941b revlog: extract density based slicing into its own function
Boris Feld <boris.feld@octobus.net>
parents: 38640
diff changeset
   239
    ...  86, #14 (1)
feba6be0941b revlog: extract density based slicing into its own function
Boris Feld <boris.feld@octobus.net>
parents: 38640
diff changeset
   240
    ...  91, #15 (5)
feba6be0941b revlog: extract density based slicing into its own function
Boris Feld <boris.feld@octobus.net>
parents: 38640
diff changeset
   241
    ... ])
feba6be0941b revlog: extract density based slicing into its own function
Boris Feld <boris.feld@octobus.net>
parents: 38640
diff changeset
   242
38655
cd1c484e31e8 revlog: adjust doctest examples to be portable to Python 3
Augie Fackler <augie@google.com>
parents: 38644
diff changeset
   243
    >>> 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
   244
    [[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
   245
    >>> 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
   246
    [[0], [15]]
feba6be0941b revlog: extract density based slicing into its own function
Boris Feld <boris.feld@octobus.net>
parents: 38640
diff changeset
   247
    >>> 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
   248
    [[0], [11], [15]]
feba6be0941b revlog: extract density based slicing into its own function
Boris Feld <boris.feld@octobus.net>
parents: 38640
diff changeset
   249
    >>> 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
   250
    [[0], [11, 13, 15]]
feba6be0941b revlog: extract density based slicing into its own function
Boris Feld <boris.feld@octobus.net>
parents: 38640
diff changeset
   251
    >>> 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
   252
    [[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
   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
    ...                           mingapsize=20))
feba6be0941b revlog: extract density based slicing into its own function
Boris Feld <boris.feld@octobus.net>
parents: 38640
diff changeset
   255
    [[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
   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))
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
    >>> 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
   260
    ...                           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
   261
    [[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
   262
    """
34824
e2ad93bcc084 revlog: introduce an experimental flag to slice chunks reads when too sparse
Paul Morelle <paul.morelle@octobus.net>
parents: 34823
diff changeset
   263
    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
   264
    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
   265
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
   266
    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
   267
        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
   268
        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
   269
38718
f8762ea73e0d sparse-revlog: implement algorithm to write sparse delta chains (issue5480)
Paul Morelle <paul.morelle@octobus.net>
parents: 38717
diff changeset
   270
    nextrev = len(revlog)
f8762ea73e0d sparse-revlog: implement algorithm to write sparse delta chains (issue5480)
Paul Morelle <paul.morelle@octobus.net>
parents: 38717
diff changeset
   271
    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
   272
f8762ea73e0d sparse-revlog: implement algorithm to write sparse delta chains (issue5480)
Paul Morelle <paul.morelle@octobus.net>
parents: 38717
diff changeset
   273
    if deltainfo is None:
39330
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   274
        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
   275
        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
   276
    else:
f8762ea73e0d sparse-revlog: implement algorithm to write sparse delta chains (issue5480)
Paul Morelle <paul.morelle@octobus.net>
parents: 38717
diff changeset
   277
        deltachainspan = deltainfo.distance
f8762ea73e0d sparse-revlog: implement algorithm to write sparse delta chains (issue5480)
Paul Morelle <paul.morelle@octobus.net>
parents: 38717
diff changeset
   278
        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
   279
38641
feba6be0941b revlog: extract density based slicing into its own function
Boris Feld <boris.feld@octobus.net>
parents: 38640
diff changeset
   280
    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
   281
        yield revs
d083ae26c325 revlog: early return in _slicechunk when span is already small enough
Boris Feld <boris.feld@octobus.net>
parents: 38634
diff changeset
   282
        return
d083ae26c325 revlog: early return in _slicechunk when span is already small enough
Boris Feld <boris.feld@octobus.net>
parents: 38634
diff changeset
   283
38718
f8762ea73e0d sparse-revlog: implement algorithm to write sparse delta chains (issue5480)
Paul Morelle <paul.morelle@octobus.net>
parents: 38717
diff changeset
   284
    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
   285
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
   286
    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
   287
        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
   288
    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
   289
        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
   290
38641
feba6be0941b revlog: extract density based slicing into its own function
Boris Feld <boris.feld@octobus.net>
parents: 38640
diff changeset
   291
    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
   292
        yield revs
f0ea8b847831 revlog: early return in _slicechunk when density is already good
Paul Morelle <paul.morelle@octobus.net>
parents: 38632
diff changeset
   293
        return
f0ea8b847831 revlog: early return in _slicechunk when density is already good
Paul Morelle <paul.morelle@octobus.net>
parents: 38632
diff changeset
   294
39139
3730b779ed5b sparse-revlog: fix delta validity computation
Boris Feld <boris.feld@octobus.net>
parents: 38763
diff changeset
   295
    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
   296
        revs = list(revs)
f8762ea73e0d sparse-revlog: implement algorithm to write sparse delta chains (issue5480)
Paul Morelle <paul.morelle@octobus.net>
parents: 38717
diff changeset
   297
        revs.append(nextrev)
f8762ea73e0d sparse-revlog: implement algorithm to write sparse delta chains (issue5480)
Paul Morelle <paul.morelle@octobus.net>
parents: 38717
diff changeset
   298
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
   299
    # 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
   300
    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
   301
    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
   302
    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
   303
    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
   304
        if rev < nextrev:
f8762ea73e0d sparse-revlog: implement algorithm to write sparse delta chains (issue5480)
Paul Morelle <paul.morelle@octobus.net>
parents: 38717
diff changeset
   305
            revstart = start(rev)
f8762ea73e0d sparse-revlog: implement algorithm to write sparse delta chains (issue5480)
Paul Morelle <paul.morelle@octobus.net>
parents: 38717
diff changeset
   306
            revlen = length(rev)
f8762ea73e0d sparse-revlog: implement algorithm to write sparse delta chains (issue5480)
Paul Morelle <paul.morelle@octobus.net>
parents: 38717
diff changeset
   307
        else:
f8762ea73e0d sparse-revlog: implement algorithm to write sparse delta chains (issue5480)
Paul Morelle <paul.morelle@octobus.net>
parents: 38717
diff changeset
   308
            revstart = nextoffset
f8762ea73e0d sparse-revlog: implement algorithm to write sparse delta chains (issue5480)
Paul Morelle <paul.morelle@octobus.net>
parents: 38717
diff changeset
   309
            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
   310
34898
1bde8e8e5de0 sparse-read: ignore trailing empty revs in each read chunk
Paul Morelle <paul.morelle@octobus.net>
parents: 34881
diff changeset
   311
        # 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
   312
        if revlen == 0:
1bde8e8e5de0 sparse-read: ignore trailing empty revs in each read chunk
Paul Morelle <paul.morelle@octobus.net>
parents: 34881
diff changeset
   313
            continue
1bde8e8e5de0 sparse-read: ignore trailing empty revs in each read chunk
Paul Morelle <paul.morelle@octobus.net>
parents: 34881
diff changeset
   314
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
   315
        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
   316
            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
   317
            # 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
   318
            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
   319
                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
   320
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
        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
   322
9e18ab7f7240 sparse-read: move from a recursive-based approach to a heap-based one
Boris Feld <boris.feld@octobus.net>
parents: 34825
diff changeset
   323
    # 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
   324
    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
   325
    heapq.heapify(indicesheap)
38641
feba6be0941b revlog: extract density based slicing into its own function
Boris Feld <boris.feld@octobus.net>
parents: 38640
diff changeset
   326
    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
   327
        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
   328
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
        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
   330
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
   331
        # 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
   332
        # 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
   333
        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
   334
        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
   335
            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
   336
        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
   337
            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
   338
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
   339
    # 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
   340
    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
   341
    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
   342
        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
   343
1bde8e8e5de0 sparse-read: ignore trailing empty revs in each read chunk
Paul Morelle <paul.morelle@octobus.net>
parents: 34881
diff changeset
   344
        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
   345
        if chunk:
1bde8e8e5de0 sparse-read: ignore trailing empty revs in each read chunk
Paul Morelle <paul.morelle@octobus.net>
parents: 34881
diff changeset
   346
            yield chunk
1bde8e8e5de0 sparse-read: ignore trailing empty revs in each read chunk
Paul Morelle <paul.morelle@octobus.net>
parents: 34881
diff changeset
   347
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
   348
        previdx = idx
34898
1bde8e8e5de0 sparse-read: ignore trailing empty revs in each read chunk
Paul Morelle <paul.morelle@octobus.net>
parents: 34881
diff changeset
   349
1bde8e8e5de0 sparse-read: ignore trailing empty revs in each read chunk
Paul Morelle <paul.morelle@octobus.net>
parents: 34881
diff changeset
   350
    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
   351
    if chunk:
1bde8e8e5de0 sparse-read: ignore trailing empty revs in each read chunk
Paul Morelle <paul.morelle@octobus.net>
parents: 34881
diff changeset
   352
        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
   353
39330
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   354
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: 39329
diff changeset
   355
    """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: 39329
diff changeset
   356
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   357
    Doctest Setup
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   358
    >>> revlog = _testrevlog([
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   359
    ...  5,  #0
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   360
    ...  10, #1
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   361
    ...  12, #2
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   362
    ...  12, #3 (empty)
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   363
    ...  17, #4
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   364
    ...  21, #5
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   365
    ...  21, #6 (empty)
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   366
    ... ])
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   367
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   368
    Contiguous cases:
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   369
    >>> _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: 39329
diff changeset
   370
    [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: 39329
diff changeset
   371
    >>> _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: 39329
diff changeset
   372
    [0, 1, 2, 3, 4]
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   373
    >>> _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: 39329
diff changeset
   374
    [0, 1, 2]
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   375
    >>> _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: 39329
diff changeset
   376
    [2]
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   377
    >>> _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: 39329
diff changeset
   378
    [3, 4, 5]
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   379
    >>> _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: 39329
diff changeset
   380
    [3, 4]
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   381
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   382
    Discontiguous cases:
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   383
    >>> _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: 39329
diff changeset
   384
    [1, 3, 5]
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   385
    >>> _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: 39329
diff changeset
   386
    [1]
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   387
    >>> _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: 39329
diff changeset
   388
    [3, 5]
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   389
    >>> _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: 39329
diff changeset
   390
    [3, 5]
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   391
    """
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   392
    length = revlog.length
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   393
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   394
    if endidx is None:
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   395
        endidx = len(revs)
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   396
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   397
    # 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: 39329
diff changeset
   398
    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: 39329
diff changeset
   399
        # 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: 39329
diff changeset
   400
        while (endidx > 1
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   401
                and endidx > startidx
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   402
                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: 39329
diff changeset
   403
            endidx -= 1
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   404
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   405
    return revs[startidx:endidx]
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   406
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   407
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: 39329
diff changeset
   408
    """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: 39329
diff changeset
   409
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   410
    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: 39329
diff changeset
   411
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   412
    >>> revlog = _testrevlog([
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   413
    ...  5,  #0
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   414
    ...  10, #1
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   415
    ...  12, #2
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   416
    ...  12, #3 (empty)
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   417
    ...  17, #4
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   418
    ... ])
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   419
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   420
    >>> 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: 39329
diff changeset
   421
    17
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   422
    >>> segmentspan(revlog, [0, 4])
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   423
    17
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   424
    >>> segmentspan(revlog, [3, 4])
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   425
    5
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   426
    >>> segmentspan(revlog, [1, 2, 3,])
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   427
    7
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   428
    >>> segmentspan(revlog, [1, 3])
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   429
    7
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   430
    """
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   431
    if not revs:
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   432
        return 0
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   433
    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: 39329
diff changeset
   434
        if len(revs) == 1:
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   435
            return deltainfo.deltalen
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   436
        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: 39329
diff changeset
   437
        end = deltainfo.deltalen + offset
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   438
    else:
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   439
        end = revlog.end(revs[-1])
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   440
    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: 39329
diff changeset
   441
39331
fd0150a3c2fe revlogdeltas: extra fulltext building in its own function
Boris Feld <boris.feld@octobus.net>
parents: 39330
diff changeset
   442
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: 39330
diff changeset
   443
    """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: 39330
diff changeset
   444
    # 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: 39330
diff changeset
   445
    # 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: 39330
diff changeset
   446
    # they're decoded.
fd0150a3c2fe revlogdeltas: extra fulltext building in its own function
Boris Feld <boris.feld@octobus.net>
parents: 39330
diff changeset
   447
    hlen = struct.calcsize(">lll")
fd0150a3c2fe revlogdeltas: extra fulltext building in its own function
Boris Feld <boris.feld@octobus.net>
parents: 39330
diff changeset
   448
    if delta[:hlen] == mdiff.replacediffheader(revlog.rawsize(baserev),
fd0150a3c2fe revlogdeltas: extra fulltext building in its own function
Boris Feld <boris.feld@octobus.net>
parents: 39330
diff changeset
   449
                                               len(delta) - hlen):
fd0150a3c2fe revlogdeltas: extra fulltext building in its own function
Boris Feld <boris.feld@octobus.net>
parents: 39330
diff changeset
   450
        fulltext = delta[hlen:]
fd0150a3c2fe revlogdeltas: extra fulltext building in its own function
Boris Feld <boris.feld@octobus.net>
parents: 39330
diff changeset
   451
    else:
fd0150a3c2fe revlogdeltas: extra fulltext building in its own function
Boris Feld <boris.feld@octobus.net>
parents: 39330
diff changeset
   452
        # 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: 39330
diff changeset
   453
        # equivalent to non-raw text
fd0150a3c2fe revlogdeltas: extra fulltext building in its own function
Boris Feld <boris.feld@octobus.net>
parents: 39330
diff changeset
   454
        basetext = revlog.revision(baserev, _df=fh, raw=False)
fd0150a3c2fe revlogdeltas: extra fulltext building in its own function
Boris Feld <boris.feld@octobus.net>
parents: 39330
diff changeset
   455
        fulltext = mdiff.patch(basetext, delta)
fd0150a3c2fe revlogdeltas: extra fulltext building in its own function
Boris Feld <boris.feld@octobus.net>
parents: 39330
diff changeset
   456
fd0150a3c2fe revlogdeltas: extra fulltext building in its own function
Boris Feld <boris.feld@octobus.net>
parents: 39330
diff changeset
   457
    try:
fd0150a3c2fe revlogdeltas: extra fulltext building in its own function
Boris Feld <boris.feld@octobus.net>
parents: 39330
diff changeset
   458
        res = revlog._processflags(fulltext, flags, 'read', raw=True)
fd0150a3c2fe revlogdeltas: extra fulltext building in its own function
Boris Feld <boris.feld@octobus.net>
parents: 39330
diff changeset
   459
        fulltext, validatehash = res
fd0150a3c2fe revlogdeltas: extra fulltext building in its own function
Boris Feld <boris.feld@octobus.net>
parents: 39330
diff changeset
   460
        if validatehash:
fd0150a3c2fe revlogdeltas: extra fulltext building in its own function
Boris Feld <boris.feld@octobus.net>
parents: 39330
diff changeset
   461
            revlog.checkhash(fulltext, expectednode, p1=p1, p2=p2)
fd0150a3c2fe revlogdeltas: extra fulltext building in its own function
Boris Feld <boris.feld@octobus.net>
parents: 39330
diff changeset
   462
        if flags & REVIDX_ISCENSORED:
fd0150a3c2fe revlogdeltas: extra fulltext building in its own function
Boris Feld <boris.feld@octobus.net>
parents: 39330
diff changeset
   463
            raise RevlogError(_('node %s is not censored') % expectednode)
fd0150a3c2fe revlogdeltas: extra fulltext building in its own function
Boris Feld <boris.feld@octobus.net>
parents: 39330
diff changeset
   464
    except CensoredNodeError:
fd0150a3c2fe revlogdeltas: extra fulltext building in its own function
Boris Feld <boris.feld@octobus.net>
parents: 39330
diff changeset
   465
        # 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: 39330
diff changeset
   466
        if not flags & REVIDX_ISCENSORED:
fd0150a3c2fe revlogdeltas: extra fulltext building in its own function
Boris Feld <boris.feld@octobus.net>
parents: 39330
diff changeset
   467
            raise
fd0150a3c2fe revlogdeltas: extra fulltext building in its own function
Boris Feld <boris.feld@octobus.net>
parents: 39330
diff changeset
   468
    return fulltext
fd0150a3c2fe revlogdeltas: extra fulltext building in its own function
Boris Feld <boris.feld@octobus.net>
parents: 39330
diff changeset
   469
35638
edc9330acac1 revlog: introduce 'deltainfo' to distinguish from 'delta'
Paul Morelle <paul.morelle@octobus.net>
parents: 35637
diff changeset
   470
@attr.s(slots=True, frozen=True)
edc9330acac1 revlog: introduce 'deltainfo' to distinguish from 'delta'
Paul Morelle <paul.morelle@octobus.net>
parents: 35637
diff changeset
   471
class _deltainfo(object):
edc9330acac1 revlog: introduce 'deltainfo' to distinguish from 'delta'
Paul Morelle <paul.morelle@octobus.net>
parents: 35637
diff changeset
   472
    distance = attr.ib()
edc9330acac1 revlog: introduce 'deltainfo' to distinguish from 'delta'
Paul Morelle <paul.morelle@octobus.net>
parents: 35637
diff changeset
   473
    deltalen = attr.ib()
edc9330acac1 revlog: introduce 'deltainfo' to distinguish from 'delta'
Paul Morelle <paul.morelle@octobus.net>
parents: 35637
diff changeset
   474
    data = attr.ib()
edc9330acac1 revlog: introduce 'deltainfo' to distinguish from 'delta'
Paul Morelle <paul.morelle@octobus.net>
parents: 35637
diff changeset
   475
    base = attr.ib()
edc9330acac1 revlog: introduce 'deltainfo' to distinguish from 'delta'
Paul Morelle <paul.morelle@octobus.net>
parents: 35637
diff changeset
   476
    chainbase = attr.ib()
edc9330acac1 revlog: introduce 'deltainfo' to distinguish from 'delta'
Paul Morelle <paul.morelle@octobus.net>
parents: 35637
diff changeset
   477
    chainlen = attr.ib()
edc9330acac1 revlog: introduce 'deltainfo' to distinguish from 'delta'
Paul Morelle <paul.morelle@octobus.net>
parents: 35637
diff changeset
   478
    compresseddeltalen = attr.ib()
39154
e0da43e2f71f revlog: compute snapshot depth on delta info
Boris Feld <boris.feld@octobus.net>
parents: 39152
diff changeset
   479
    snapshotdepth = attr.ib()
35638
edc9330acac1 revlog: introduce 'deltainfo' to distinguish from 'delta'
Paul Morelle <paul.morelle@octobus.net>
parents: 35637
diff changeset
   480
39330
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   481
def isgooddeltainfo(revlog, deltainfo, revinfo):
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   482
    """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: 39329
diff changeset
   483
    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: 39329
diff changeset
   484
    performant."""
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   485
    if deltainfo is None:
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   486
        return False
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   487
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   488
    # - '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: 39329
diff changeset
   489
    #   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: 39329
diff changeset
   490
    # - '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: 39329
diff changeset
   491
    #   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: 39329
diff changeset
   492
    #   we consume.
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   493
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   494
    if revlog._sparserevlog:
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   495
        # As sparse-read will be used, we can consider that the distance,
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   496
        # instead of being the span of the whole chunk,
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   497
        # is the span of the largest read chunk
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   498
        base = deltainfo.base
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   499
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   500
        if base != nullrev:
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   501
            deltachain = revlog._deltachain(base)[0]
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   502
        else:
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   503
            deltachain = []
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   504
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   505
        # search for the first non-snapshot revision
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   506
        for idx, r in enumerate(deltachain):
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   507
            if not revlog.issnapshot(r):
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   508
                break
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   509
        deltachain = deltachain[idx:]
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   510
        chunks = slicechunk(revlog, deltachain, deltainfo)
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   511
        all_span = [segmentspan(revlog, revs, deltainfo)
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   512
                    for revs in chunks]
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   513
        distance = max(all_span)
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   514
    else:
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   515
        distance = deltainfo.distance
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   516
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   517
    textlen = revinfo.textlen
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   518
    defaultmax = textlen * 4
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   519
    maxdist = revlog._maxdeltachainspan
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   520
    if not maxdist:
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   521
        maxdist = distance # ensure the conditional pass
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   522
    maxdist = max(maxdist, defaultmax)
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   523
    if revlog._sparserevlog and maxdist < revlog._srmingapsize:
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   524
        # In multiple place, we are ignoring irrelevant data range below a
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   525
        # certain size. Be also apply this tradeoff here and relax span
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   526
        # constraint for small enought content.
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   527
        maxdist = revlog._srmingapsize
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   528
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   529
    # Bad delta from read span:
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   530
    #
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   531
    #   If the span of data read is larger than the maximum allowed.
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   532
    if maxdist < distance:
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   533
        return False
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   534
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   535
    # 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: 39329
diff changeset
   536
    #
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   537
    #   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: 39329
diff changeset
   538
    #   delta will be inefficient.
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   539
    if textlen < deltainfo.deltalen:
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   540
        return False
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   541
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   542
    # 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: 39329
diff changeset
   543
    #
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   544
    #   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: 39329
diff changeset
   545
    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: 39329
diff changeset
   546
        return False
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   547
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   548
    # Bad delta from chain length:
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   549
    #
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   550
    #   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: 39329
diff changeset
   551
    if (revlog._maxchainlen
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   552
            and revlog._maxchainlen < deltainfo.chainlen):
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   553
        return False
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   554
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   555
    # 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: 39329
diff changeset
   556
    #
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   557
    #   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: 39329
diff changeset
   558
    #   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: 39329
diff changeset
   559
    #   created.
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   560
    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: 39329
diff changeset
   561
            (textlen >> deltainfo.snapshotdepth) < deltainfo.deltalen):
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   562
        return False
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   563
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   564
    # 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: 39329
diff changeset
   565
    # snapshot
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   566
    if (deltainfo.snapshotdepth
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   567
            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: 39329
diff changeset
   568
        return False
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   569
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   570
    return True
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   571
39337
37957e07138c revlogdeltas: move finddeltainfo filtering inside _candidategroups
Boris Feld <boris.feld@octobus.net>
parents: 39336
diff changeset
   572
def _candidategroups(revlog, textlen, p1, p2, cachedelta):
39336
1c6ff52fe9cf revlogdeltas: split candidate groups selection from the filtering logic
Boris Feld <boris.feld@octobus.net>
parents: 39335
diff changeset
   573
    """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: 39335
diff changeset
   574
1c6ff52fe9cf revlogdeltas: split candidate groups selection from the filtering logic
Boris Feld <boris.feld@octobus.net>
parents: 39335
diff changeset
   575
    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: 39335
diff changeset
   576
    content. See _raw_candidate_groups for details about the group order.
39334
507f5b1dd7c8 revlogdeltas: extract _getcandidaterevs in a function
Boris Feld <boris.feld@octobus.net>
parents: 39333
diff changeset
   577
    """
39336
1c6ff52fe9cf revlogdeltas: split candidate groups selection from the filtering logic
Boris Feld <boris.feld@octobus.net>
parents: 39335
diff changeset
   578
    # should we try to build a delta?
1c6ff52fe9cf revlogdeltas: split candidate groups selection from the filtering logic
Boris Feld <boris.feld@octobus.net>
parents: 39335
diff changeset
   579
    if not (len(revlog) and revlog._storedeltachains):
1c6ff52fe9cf revlogdeltas: split candidate groups selection from the filtering logic
Boris Feld <boris.feld@octobus.net>
parents: 39335
diff changeset
   580
        return
1c6ff52fe9cf revlogdeltas: split candidate groups selection from the filtering logic
Boris Feld <boris.feld@octobus.net>
parents: 39335
diff changeset
   581
39337
37957e07138c revlogdeltas: move finddeltainfo filtering inside _candidategroups
Boris Feld <boris.feld@octobus.net>
parents: 39336
diff changeset
   582
    deltalength = revlog.length
37957e07138c revlogdeltas: move finddeltainfo filtering inside _candidategroups
Boris Feld <boris.feld@octobus.net>
parents: 39336
diff changeset
   583
    deltaparent = revlog.deltaparent
37957e07138c revlogdeltas: move finddeltainfo filtering inside _candidategroups
Boris Feld <boris.feld@octobus.net>
parents: 39336
diff changeset
   584
37957e07138c revlogdeltas: move finddeltainfo filtering inside _candidategroups
Boris Feld <boris.feld@octobus.net>
parents: 39336
diff changeset
   585
    deltas_limit = textlen * LIMIT_DELTA2TEXT
37957e07138c revlogdeltas: move finddeltainfo filtering inside _candidategroups
Boris Feld <boris.feld@octobus.net>
parents: 39336
diff changeset
   586
39336
1c6ff52fe9cf revlogdeltas: split candidate groups selection from the filtering logic
Boris Feld <boris.feld@octobus.net>
parents: 39335
diff changeset
   587
    tested = set([nullrev])
39337
37957e07138c revlogdeltas: move finddeltainfo filtering inside _candidategroups
Boris Feld <boris.feld@octobus.net>
parents: 39336
diff changeset
   588
    for temptative in _rawgroups(revlog, p1, p2, cachedelta):
37957e07138c revlogdeltas: move finddeltainfo filtering inside _candidategroups
Boris Feld <boris.feld@octobus.net>
parents: 39336
diff changeset
   589
        group = []
37957e07138c revlogdeltas: move finddeltainfo filtering inside _candidategroups
Boris Feld <boris.feld@octobus.net>
parents: 39336
diff changeset
   590
        for rev in temptative:
37957e07138c revlogdeltas: move finddeltainfo filtering inside _candidategroups
Boris Feld <boris.feld@octobus.net>
parents: 39336
diff changeset
   591
            # skip over empty delta (no need to include them in a chain)
37957e07138c revlogdeltas: move finddeltainfo filtering inside _candidategroups
Boris Feld <boris.feld@octobus.net>
parents: 39336
diff changeset
   592
            while not (rev == nullrev or rev in tested or deltalength(rev)):
37957e07138c revlogdeltas: move finddeltainfo filtering inside _candidategroups
Boris Feld <boris.feld@octobus.net>
parents: 39336
diff changeset
   593
                rev = deltaparent(rev)
37957e07138c revlogdeltas: move finddeltainfo filtering inside _candidategroups
Boris Feld <boris.feld@octobus.net>
parents: 39336
diff changeset
   594
                tested.add(rev)
37957e07138c revlogdeltas: move finddeltainfo filtering inside _candidategroups
Boris Feld <boris.feld@octobus.net>
parents: 39336
diff changeset
   595
            # filter out revision we tested already
37957e07138c revlogdeltas: move finddeltainfo filtering inside _candidategroups
Boris Feld <boris.feld@octobus.net>
parents: 39336
diff changeset
   596
            if rev in tested:
37957e07138c revlogdeltas: move finddeltainfo filtering inside _candidategroups
Boris Feld <boris.feld@octobus.net>
parents: 39336
diff changeset
   597
                continue
37957e07138c revlogdeltas: move finddeltainfo filtering inside _candidategroups
Boris Feld <boris.feld@octobus.net>
parents: 39336
diff changeset
   598
            tested.add(rev)
37957e07138c revlogdeltas: move finddeltainfo filtering inside _candidategroups
Boris Feld <boris.feld@octobus.net>
parents: 39336
diff changeset
   599
            # filter out delta base that will never produce good delta
37957e07138c revlogdeltas: move finddeltainfo filtering inside _candidategroups
Boris Feld <boris.feld@octobus.net>
parents: 39336
diff changeset
   600
            if deltas_limit < revlog.length(rev):
37957e07138c revlogdeltas: move finddeltainfo filtering inside _candidategroups
Boris Feld <boris.feld@octobus.net>
parents: 39336
diff changeset
   601
                continue
37957e07138c revlogdeltas: move finddeltainfo filtering inside _candidategroups
Boris Feld <boris.feld@octobus.net>
parents: 39336
diff changeset
   602
            # 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: 39336
diff changeset
   603
            # last resort.
37957e07138c revlogdeltas: move finddeltainfo filtering inside _candidategroups
Boris Feld <boris.feld@octobus.net>
parents: 39336
diff changeset
   604
            if rev == nullrev:
37957e07138c revlogdeltas: move finddeltainfo filtering inside _candidategroups
Boris Feld <boris.feld@octobus.net>
parents: 39336
diff changeset
   605
                continue
37957e07138c revlogdeltas: move finddeltainfo filtering inside _candidategroups
Boris Feld <boris.feld@octobus.net>
parents: 39336
diff changeset
   606
            # no delta for rawtext-changing revs (see "candelta" for why)
37957e07138c revlogdeltas: move finddeltainfo filtering inside _candidategroups
Boris Feld <boris.feld@octobus.net>
parents: 39336
diff changeset
   607
            if revlog.flags(rev) & REVIDX_RAWTEXT_CHANGING_FLAGS:
37957e07138c revlogdeltas: move finddeltainfo filtering inside _candidategroups
Boris Feld <boris.feld@octobus.net>
parents: 39336
diff changeset
   608
                continue
37957e07138c revlogdeltas: move finddeltainfo filtering inside _candidategroups
Boris Feld <boris.feld@octobus.net>
parents: 39336
diff changeset
   609
            group.append(rev)
39336
1c6ff52fe9cf revlogdeltas: split candidate groups selection from the filtering logic
Boris Feld <boris.feld@octobus.net>
parents: 39335
diff changeset
   610
        if group:
39493
3ca144f1c8dd snapshot: search for unrelated but reusable full-snapshot
Boris Feld <boris.feld@octobus.net>
parents: 39492
diff changeset
   611
            # 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: 39492
diff changeset
   612
            #      impacting performances. Some bounding or slicing mecanism
3ca144f1c8dd snapshot: search for unrelated but reusable full-snapshot
Boris Feld <boris.feld@octobus.net>
parents: 39492
diff changeset
   613
            #      would help to reduce this impact.
39337
37957e07138c revlogdeltas: move finddeltainfo filtering inside _candidategroups
Boris Feld <boris.feld@octobus.net>
parents: 39336
diff changeset
   614
            yield tuple(group)
39336
1c6ff52fe9cf revlogdeltas: split candidate groups selection from the filtering logic
Boris Feld <boris.feld@octobus.net>
parents: 39335
diff changeset
   615
39493
3ca144f1c8dd snapshot: search for unrelated but reusable full-snapshot
Boris Feld <boris.feld@octobus.net>
parents: 39492
diff changeset
   616
def _findsnapshots(revlog, cache, start_rev):
3ca144f1c8dd snapshot: search for unrelated but reusable full-snapshot
Boris Feld <boris.feld@octobus.net>
parents: 39492
diff changeset
   617
    """find snapshot from start_rev to tip"""
3ca144f1c8dd snapshot: search for unrelated but reusable full-snapshot
Boris Feld <boris.feld@octobus.net>
parents: 39492
diff changeset
   618
    deltaparent = revlog.deltaparent
39495
6a53842727c1 snapshot: consider unrelated snapshots at a similar level first
Boris Feld <boris.feld@octobus.net>
parents: 39494
diff changeset
   619
    issnapshot = revlog.issnapshot
39493
3ca144f1c8dd snapshot: search for unrelated but reusable full-snapshot
Boris Feld <boris.feld@octobus.net>
parents: 39492
diff changeset
   620
    for rev in revlog.revs(start_rev):
39495
6a53842727c1 snapshot: consider unrelated snapshots at a similar level first
Boris Feld <boris.feld@octobus.net>
parents: 39494
diff changeset
   621
        if issnapshot(rev):
6a53842727c1 snapshot: consider unrelated snapshots at a similar level first
Boris Feld <boris.feld@octobus.net>
parents: 39494
diff changeset
   622
            cache[deltaparent(rev)].append(rev)
39493
3ca144f1c8dd snapshot: search for unrelated but reusable full-snapshot
Boris Feld <boris.feld@octobus.net>
parents: 39492
diff changeset
   623
39336
1c6ff52fe9cf revlogdeltas: split candidate groups selection from the filtering logic
Boris Feld <boris.feld@octobus.net>
parents: 39335
diff changeset
   624
def _rawgroups(revlog, p1, p2, cachedelta):
1c6ff52fe9cf revlogdeltas: split candidate groups selection from the filtering logic
Boris Feld <boris.feld@octobus.net>
parents: 39335
diff changeset
   625
    """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: 39335
diff changeset
   626
1c6ff52fe9cf revlogdeltas: split candidate groups selection from the filtering logic
Boris Feld <boris.feld@octobus.net>
parents: 39335
diff changeset
   627
    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: 39335
diff changeset
   628
    without looking it any practical details.
1c6ff52fe9cf revlogdeltas: split candidate groups selection from the filtering logic
Boris Feld <boris.feld@octobus.net>
parents: 39335
diff changeset
   629
1c6ff52fe9cf revlogdeltas: split candidate groups selection from the filtering logic
Boris Feld <boris.feld@octobus.net>
parents: 39335
diff changeset
   630
    The group order aims at providing fast or small candidates first.
39334
507f5b1dd7c8 revlogdeltas: extract _getcandidaterevs in a function
Boris Feld <boris.feld@octobus.net>
parents: 39333
diff changeset
   631
    """
507f5b1dd7c8 revlogdeltas: extract _getcandidaterevs in a function
Boris Feld <boris.feld@octobus.net>
parents: 39333
diff changeset
   632
    gdelta = revlog._generaldelta
39492
a33f394b2bfd snapshot: try intermediate snapshot against parents' base
Boris Feld <boris.feld@octobus.net>
parents: 39488
diff changeset
   633
    sparse = revlog._sparserevlog
39334
507f5b1dd7c8 revlogdeltas: extract _getcandidaterevs in a function
Boris Feld <boris.feld@octobus.net>
parents: 39333
diff changeset
   634
    curr = len(revlog)
507f5b1dd7c8 revlogdeltas: extract _getcandidaterevs in a function
Boris Feld <boris.feld@octobus.net>
parents: 39333
diff changeset
   635
    prev = curr - 1
39492
a33f394b2bfd snapshot: try intermediate snapshot against parents' base
Boris Feld <boris.feld@octobus.net>
parents: 39488
diff changeset
   636
    deltachain = lambda rev: revlog._deltachain(rev)[0]
39334
507f5b1dd7c8 revlogdeltas: extract _getcandidaterevs in a function
Boris Feld <boris.feld@octobus.net>
parents: 39333
diff changeset
   637
39488
d629b6d2f05a revlog: clarify the comment attached to delta reuse
Boris Feld <boris.feld@octobus.net>
parents: 39487
diff changeset
   638
    # First we try to reuse a the delta contained in the bundle.
d629b6d2f05a revlog: clarify the comment attached to delta reuse
Boris Feld <boris.feld@octobus.net>
parents: 39487
diff changeset
   639
    # (or from the source revlog)
d629b6d2f05a revlog: clarify the comment attached to delta reuse
Boris Feld <boris.feld@octobus.net>
parents: 39487
diff changeset
   640
    #
d629b6d2f05a revlog: clarify the comment attached to delta reuse
Boris Feld <boris.feld@octobus.net>
parents: 39487
diff changeset
   641
    # This logic only applies to general delta repositories and can be disabled
d629b6d2f05a revlog: clarify the comment attached to delta reuse
Boris Feld <boris.feld@octobus.net>
parents: 39487
diff changeset
   642
    # through configuration. Disabling reuse of source delta is useful when
d629b6d2f05a revlog: clarify the comment attached to delta reuse
Boris Feld <boris.feld@octobus.net>
parents: 39487
diff changeset
   643
    # we want to make sure we recomputed "optimal" deltas.
39336
1c6ff52fe9cf revlogdeltas: split candidate groups selection from the filtering logic
Boris Feld <boris.feld@octobus.net>
parents: 39335
diff changeset
   644
    if cachedelta and gdelta and revlog._lazydeltabase:
1c6ff52fe9cf revlogdeltas: split candidate groups selection from the filtering logic
Boris Feld <boris.feld@octobus.net>
parents: 39335
diff changeset
   645
        # Assume what we received from the server is a good choice
1c6ff52fe9cf revlogdeltas: split candidate groups selection from the filtering logic
Boris Feld <boris.feld@octobus.net>
parents: 39335
diff changeset
   646
        # build delta will reuse the cache
1c6ff52fe9cf revlogdeltas: split candidate groups selection from the filtering logic
Boris Feld <boris.feld@octobus.net>
parents: 39335
diff changeset
   647
        yield (cachedelta[0],)
1c6ff52fe9cf revlogdeltas: split candidate groups selection from the filtering logic
Boris Feld <boris.feld@octobus.net>
parents: 39335
diff changeset
   648
1c6ff52fe9cf revlogdeltas: split candidate groups selection from the filtering logic
Boris Feld <boris.feld@octobus.net>
parents: 39335
diff changeset
   649
    if gdelta:
1c6ff52fe9cf revlogdeltas: split candidate groups selection from the filtering logic
Boris Feld <boris.feld@octobus.net>
parents: 39335
diff changeset
   650
        # exclude already lazy tested base if any
1c6ff52fe9cf revlogdeltas: split candidate groups selection from the filtering logic
Boris Feld <boris.feld@octobus.net>
parents: 39335
diff changeset
   651
        parents = [p for p in (p1, p2) if p != nullrev]
39334
507f5b1dd7c8 revlogdeltas: extract _getcandidaterevs in a function
Boris Feld <boris.feld@octobus.net>
parents: 39333
diff changeset
   652
39336
1c6ff52fe9cf revlogdeltas: split candidate groups selection from the filtering logic
Boris Feld <boris.feld@octobus.net>
parents: 39335
diff changeset
   653
        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: 39335
diff changeset
   654
            parents.sort()
1c6ff52fe9cf revlogdeltas: split candidate groups selection from the filtering logic
Boris Feld <boris.feld@octobus.net>
parents: 39335
diff changeset
   655
            # 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: 39335
diff changeset
   656
            # 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: 39335
diff changeset
   657
            yield (parents[1],)
1c6ff52fe9cf revlogdeltas: split candidate groups selection from the filtering logic
Boris Feld <boris.feld@octobus.net>
parents: 39335
diff changeset
   658
            # 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: 39335
diff changeset
   659
            yield (parents[0],)
1c6ff52fe9cf revlogdeltas: split candidate groups selection from the filtering logic
Boris Feld <boris.feld@octobus.net>
parents: 39335
diff changeset
   660
        elif len(parents) > 0:
1c6ff52fe9cf revlogdeltas: split candidate groups selection from the filtering logic
Boris Feld <boris.feld@octobus.net>
parents: 39335
diff changeset
   661
            # 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: 39335
diff changeset
   662
            yield parents
39334
507f5b1dd7c8 revlogdeltas: extract _getcandidaterevs in a function
Boris Feld <boris.feld@octobus.net>
parents: 39333
diff changeset
   663
39492
a33f394b2bfd snapshot: try intermediate snapshot against parents' base
Boris Feld <boris.feld@octobus.net>
parents: 39488
diff changeset
   664
    if sparse and parents:
39494
e72130f58f5d snapshot: consider all snapshots in the parents' chains
Boris Feld <boris.feld@octobus.net>
parents: 39493
diff changeset
   665
        snapshots = collections.defaultdict(list) # map: base-rev: snapshot-rev
39492
a33f394b2bfd snapshot: try intermediate snapshot against parents' base
Boris Feld <boris.feld@octobus.net>
parents: 39488
diff changeset
   666
        # 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: 39488
diff changeset
   667
        # a base for a new intermediate-snapshot
39494
e72130f58f5d snapshot: consider all snapshots in the parents' chains
Boris Feld <boris.feld@octobus.net>
parents: 39493
diff changeset
   668
        #
e72130f58f5d snapshot: consider all snapshots in the parents' chains
Boris Feld <boris.feld@octobus.net>
parents: 39493
diff changeset
   669
        # search for snapshot in parents delta chain
e72130f58f5d snapshot: consider all snapshots in the parents' chains
Boris Feld <boris.feld@octobus.net>
parents: 39493
diff changeset
   670
        # map: snapshot-level: snapshot-rev
e72130f58f5d snapshot: consider all snapshots in the parents' chains
Boris Feld <boris.feld@octobus.net>
parents: 39493
diff changeset
   671
        parents_snaps = collections.defaultdict(set)
39492
a33f394b2bfd snapshot: try intermediate snapshot against parents' base
Boris Feld <boris.feld@octobus.net>
parents: 39488
diff changeset
   672
        for p in parents:
39494
e72130f58f5d snapshot: consider all snapshots in the parents' chains
Boris Feld <boris.feld@octobus.net>
parents: 39493
diff changeset
   673
            for idx, s in enumerate(deltachain(p)):
e72130f58f5d snapshot: consider all snapshots in the parents' chains
Boris Feld <boris.feld@octobus.net>
parents: 39493
diff changeset
   674
                if not revlog.issnapshot(s):
e72130f58f5d snapshot: consider all snapshots in the parents' chains
Boris Feld <boris.feld@octobus.net>
parents: 39493
diff changeset
   675
                    break
e72130f58f5d snapshot: consider all snapshots in the parents' chains
Boris Feld <boris.feld@octobus.net>
parents: 39493
diff changeset
   676
                parents_snaps[idx].add(s)
39495
6a53842727c1 snapshot: consider unrelated snapshots at a similar level first
Boris Feld <boris.feld@octobus.net>
parents: 39494
diff changeset
   677
        snapfloor = min(parents_snaps[0]) + 1
6a53842727c1 snapshot: consider unrelated snapshots at a similar level first
Boris Feld <boris.feld@octobus.net>
parents: 39494
diff changeset
   678
        _findsnapshots(revlog, snapshots, snapfloor)
39494
e72130f58f5d snapshot: consider all snapshots in the parents' chains
Boris Feld <boris.feld@octobus.net>
parents: 39493
diff changeset
   679
        # Test them as possible intermediate snapshot base
e72130f58f5d snapshot: consider all snapshots in the parents' chains
Boris Feld <boris.feld@octobus.net>
parents: 39493
diff changeset
   680
        # 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: 39493
diff changeset
   681
        # likely to result in small delta
39495
6a53842727c1 snapshot: consider unrelated snapshots at a similar level first
Boris Feld <boris.feld@octobus.net>
parents: 39494
diff changeset
   682
        floor = None
39494
e72130f58f5d snapshot: consider all snapshots in the parents' chains
Boris Feld <boris.feld@octobus.net>
parents: 39493
diff changeset
   683
        for idx, snaps in sorted(parents_snaps.items(), reverse=True):
39495
6a53842727c1 snapshot: consider unrelated snapshots at a similar level first
Boris Feld <boris.feld@octobus.net>
parents: 39494
diff changeset
   684
            siblings = set()
6a53842727c1 snapshot: consider unrelated snapshots at a similar level first
Boris Feld <boris.feld@octobus.net>
parents: 39494
diff changeset
   685
            for s in snaps:
6a53842727c1 snapshot: consider unrelated snapshots at a similar level first
Boris Feld <boris.feld@octobus.net>
parents: 39494
diff changeset
   686
                siblings.update(snapshots[s])
6a53842727c1 snapshot: consider unrelated snapshots at a similar level first
Boris Feld <boris.feld@octobus.net>
parents: 39494
diff changeset
   687
            # 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: 39494
diff changeset
   688
            # 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: 39494
diff changeset
   689
            # suitable.
6a53842727c1 snapshot: consider unrelated snapshots at a similar level first
Boris Feld <boris.feld@octobus.net>
parents: 39494
diff changeset
   690
            #
6a53842727c1 snapshot: consider unrelated snapshots at a similar level first
Boris Feld <boris.feld@octobus.net>
parents: 39494
diff changeset
   691
            # 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: 39494
diff changeset
   692
            # 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: 39494
diff changeset
   693
            # 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: 39494
diff changeset
   694
            # 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: 39494
diff changeset
   695
6a53842727c1 snapshot: consider unrelated snapshots at a similar level first
Boris Feld <boris.feld@octobus.net>
parents: 39494
diff changeset
   696
            if floor is not None:
6a53842727c1 snapshot: consider unrelated snapshots at a similar level first
Boris Feld <boris.feld@octobus.net>
parents: 39494
diff changeset
   697
                # 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: 39494
diff changeset
   698
                # 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: 39494
diff changeset
   699
                # 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: 39494
diff changeset
   700
                # snapshot.
6a53842727c1 snapshot: consider unrelated snapshots at a similar level first
Boris Feld <boris.feld@octobus.net>
parents: 39494
diff changeset
   701
                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: 39494
diff changeset
   702
            yield tuple(sorted(siblings))
6a53842727c1 snapshot: consider unrelated snapshots at a similar level first
Boris Feld <boris.feld@octobus.net>
parents: 39494
diff changeset
   703
            # then test the base from our parent's delta chain.
39494
e72130f58f5d snapshot: consider all snapshots in the parents' chains
Boris Feld <boris.feld@octobus.net>
parents: 39493
diff changeset
   704
            yield tuple(sorted(snaps))
39495
6a53842727c1 snapshot: consider unrelated snapshots at a similar level first
Boris Feld <boris.feld@octobus.net>
parents: 39494
diff changeset
   705
            floor = min(snaps)
39493
3ca144f1c8dd snapshot: search for unrelated but reusable full-snapshot
Boris Feld <boris.feld@octobus.net>
parents: 39492
diff changeset
   706
        # 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: 39492
diff changeset
   707
        # 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: 39492
diff changeset
   708
        # intermediate snapshot.
3ca144f1c8dd snapshot: search for unrelated but reusable full-snapshot
Boris Feld <boris.feld@octobus.net>
parents: 39492
diff changeset
   709
        #
3ca144f1c8dd snapshot: search for unrelated but reusable full-snapshot
Boris Feld <boris.feld@octobus.net>
parents: 39492
diff changeset
   710
        # 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: 39492
diff changeset
   711
        # 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: 39492
diff changeset
   712
        # 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: 39492
diff changeset
   713
        # more and more snapshot as the repository grow.
3ca144f1c8dd snapshot: search for unrelated but reusable full-snapshot
Boris Feld <boris.feld@octobus.net>
parents: 39492
diff changeset
   714
        yield tuple(snapshots[nullrev])
39492
a33f394b2bfd snapshot: try intermediate snapshot against parents' base
Boris Feld <boris.feld@octobus.net>
parents: 39488
diff changeset
   715
39336
1c6ff52fe9cf revlogdeltas: split candidate groups selection from the filtering logic
Boris Feld <boris.feld@octobus.net>
parents: 39335
diff changeset
   716
    # other approach failed try against prev to hopefully save us a
1c6ff52fe9cf revlogdeltas: split candidate groups selection from the filtering logic
Boris Feld <boris.feld@octobus.net>
parents: 39335
diff changeset
   717
    # fulltext.
1c6ff52fe9cf revlogdeltas: split candidate groups selection from the filtering logic
Boris Feld <boris.feld@octobus.net>
parents: 39335
diff changeset
   718
    yield (prev,)
39334
507f5b1dd7c8 revlogdeltas: extract _getcandidaterevs in a function
Boris Feld <boris.feld@octobus.net>
parents: 39333
diff changeset
   719
39330
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   720
class deltacomputer(object):
35738
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   721
    def __init__(self, revlog):
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   722
        self.revlog = revlog
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   723
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   724
    def buildtext(self, revinfo, fh):
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   725
        """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
   726
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   727
        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
   728
        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
   729
                 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
   730
        """
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   731
        btext = revinfo.btext
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   732
        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
   733
            return btext[0]
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   734
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   735
        revlog = self.revlog
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   736
        cachedelta = revinfo.cachedelta
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   737
        baserev = cachedelta[0]
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   738
        delta = cachedelta[1]
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   739
39331
fd0150a3c2fe revlogdeltas: extra fulltext building in its own function
Boris Feld <boris.feld@octobus.net>
parents: 39330
diff changeset
   740
        fulltext = btext[0] = _textfromdelta(fh, revlog, baserev, delta,
fd0150a3c2fe revlogdeltas: extra fulltext building in its own function
Boris Feld <boris.feld@octobus.net>
parents: 39330
diff changeset
   741
                                             revinfo.p1, revinfo.p2,
fd0150a3c2fe revlogdeltas: extra fulltext building in its own function
Boris Feld <boris.feld@octobus.net>
parents: 39330
diff changeset
   742
                                             revinfo.flags, revinfo.node)
fd0150a3c2fe revlogdeltas: extra fulltext building in its own function
Boris Feld <boris.feld@octobus.net>
parents: 39330
diff changeset
   743
        return fulltext
35738
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   744
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   745
    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
   746
        revlog = self.revlog
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   747
        t = self.buildtext(revinfo, fh)
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   748
        if revlog.iscensored(base):
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   749
            # 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
   750
            # 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
   751
            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
   752
            delta = header + t
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   753
        else:
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   754
            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
   755
            delta = mdiff.textdiff(ptext, t)
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   756
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   757
        return delta
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   758
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   759
    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
   760
        # can we use the cached delta?
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   761
        if revinfo.cachedelta and revinfo.cachedelta[0] == base:
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   762
            delta = revinfo.cachedelta[1]
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   763
        else:
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   764
            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
   765
        revlog = self.revlog
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   766
        header, data = revlog.compress(delta)
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   767
        deltalen = len(header) + len(data)
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   768
        chainbase = revlog.chainbase(base)
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   769
        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
   770
        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
   771
        if revlog._generaldelta:
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   772
            deltabase = base
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   773
        else:
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   774
            deltabase = chainbase
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   775
        chainlen, compresseddeltalen = revlog._chaininfo(base)
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   776
        chainlen += 1
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   777
        compresseddeltalen += deltalen
39154
e0da43e2f71f revlog: compute snapshot depth on delta info
Boris Feld <boris.feld@octobus.net>
parents: 39152
diff changeset
   778
e0da43e2f71f revlog: compute snapshot depth on delta info
Boris Feld <boris.feld@octobus.net>
parents: 39152
diff changeset
   779
        revlog = self.revlog
e0da43e2f71f revlog: compute snapshot depth on delta info
Boris Feld <boris.feld@octobus.net>
parents: 39152
diff changeset
   780
        snapshotdepth = None
e0da43e2f71f revlog: compute snapshot depth on delta info
Boris Feld <boris.feld@octobus.net>
parents: 39152
diff changeset
   781
        if deltabase == nullrev:
e0da43e2f71f revlog: compute snapshot depth on delta info
Boris Feld <boris.feld@octobus.net>
parents: 39152
diff changeset
   782
            snapshotdepth = 0
e0da43e2f71f revlog: compute snapshot depth on delta info
Boris Feld <boris.feld@octobus.net>
parents: 39152
diff changeset
   783
        elif revlog._sparserevlog and revlog.issnapshot(deltabase):
e0da43e2f71f revlog: compute snapshot depth on delta info
Boris Feld <boris.feld@octobus.net>
parents: 39152
diff changeset
   784
            # A delta chain should always be one full snapshot,
e0da43e2f71f revlog: compute snapshot depth on delta info
Boris Feld <boris.feld@octobus.net>
parents: 39152
diff changeset
   785
            # 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: 39152
diff changeset
   786
            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: 39152
diff changeset
   787
            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: 39152
diff changeset
   788
                snapshotdepth = len(revlog._deltachain(deltabase)[0])
e0da43e2f71f revlog: compute snapshot depth on delta info
Boris Feld <boris.feld@octobus.net>
parents: 39152
diff changeset
   789
35738
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   790
        return _deltainfo(dist, deltalen, (header, data), deltabase,
39154
e0da43e2f71f revlog: compute snapshot depth on delta info
Boris Feld <boris.feld@octobus.net>
parents: 39152
diff changeset
   791
                          chainbase, chainlen, compresseddeltalen,
e0da43e2f71f revlog: compute snapshot depth on delta info
Boris Feld <boris.feld@octobus.net>
parents: 39152
diff changeset
   792
                          snapshotdepth)
35738
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   793
39333
5d343a24bff5 revlogdeltas: always return a delta info object in finddeltainfo
Boris Feld <boris.feld@octobus.net>
parents: 39332
diff changeset
   794
    def _fullsnapshotinfo(self, fh, revinfo):
5d343a24bff5 revlogdeltas: always return a delta info object in finddeltainfo
Boris Feld <boris.feld@octobus.net>
parents: 39332
diff changeset
   795
        curr = len(self.revlog)
5d343a24bff5 revlogdeltas: always return a delta info object in finddeltainfo
Boris Feld <boris.feld@octobus.net>
parents: 39332
diff changeset
   796
        rawtext = self.buildtext(revinfo, fh)
5d343a24bff5 revlogdeltas: always return a delta info object in finddeltainfo
Boris Feld <boris.feld@octobus.net>
parents: 39332
diff changeset
   797
        data = self.revlog.compress(rawtext)
5d343a24bff5 revlogdeltas: always return a delta info object in finddeltainfo
Boris Feld <boris.feld@octobus.net>
parents: 39332
diff changeset
   798
        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: 39332
diff changeset
   799
        deltabase = chainbase = curr
5d343a24bff5 revlogdeltas: always return a delta info object in finddeltainfo
Boris Feld <boris.feld@octobus.net>
parents: 39332
diff changeset
   800
        snapshotdepth = 0
5d343a24bff5 revlogdeltas: always return a delta info object in finddeltainfo
Boris Feld <boris.feld@octobus.net>
parents: 39332
diff changeset
   801
        chainlen = 1
5d343a24bff5 revlogdeltas: always return a delta info object in finddeltainfo
Boris Feld <boris.feld@octobus.net>
parents: 39332
diff changeset
   802
5d343a24bff5 revlogdeltas: always return a delta info object in finddeltainfo
Boris Feld <boris.feld@octobus.net>
parents: 39332
diff changeset
   803
        return _deltainfo(dist, deltalen, data, deltabase,
5d343a24bff5 revlogdeltas: always return a delta info object in finddeltainfo
Boris Feld <boris.feld@octobus.net>
parents: 39332
diff changeset
   804
                          chainbase, chainlen, compresseddeltalen,
5d343a24bff5 revlogdeltas: always return a delta info object in finddeltainfo
Boris Feld <boris.feld@octobus.net>
parents: 39332
diff changeset
   805
                          snapshotdepth)
5d343a24bff5 revlogdeltas: always return a delta info object in finddeltainfo
Boris Feld <boris.feld@octobus.net>
parents: 39332
diff changeset
   806
35738
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   807
    def finddeltainfo(self, revinfo, fh):
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   808
        """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
   809
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   810
        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
   811
        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
   812
                 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
   813
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   814
        Returns the first acceptable candidate revision, as ordered by
39334
507f5b1dd7c8 revlogdeltas: extract _getcandidaterevs in a function
Boris Feld <boris.feld@octobus.net>
parents: 39333
diff changeset
   815
        _candidategroups
39333
5d343a24bff5 revlogdeltas: always return a delta info object in finddeltainfo
Boris Feld <boris.feld@octobus.net>
parents: 39332
diff changeset
   816
5d343a24bff5 revlogdeltas: always return a delta info object in finddeltainfo
Boris Feld <boris.feld@octobus.net>
parents: 39332
diff changeset
   817
        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: 39332
diff changeset
   818
        snapshot.
35738
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   819
        """
39085
dbb3e9e44fce revlog: do not search for delta for empty content
Boris Feld <boris.feld@octobus.net>
parents: 39084
diff changeset
   820
        if not revinfo.textlen:
39333
5d343a24bff5 revlogdeltas: always return a delta info object in finddeltainfo
Boris Feld <boris.feld@octobus.net>
parents: 39332
diff changeset
   821
            return self._fullsnapshotinfo(fh, revinfo)
39085
dbb3e9e44fce revlog: do not search for delta for empty content
Boris Feld <boris.feld@octobus.net>
parents: 39084
diff changeset
   822
39332
6f4b8f607a31 revlogdeltas: move special cases around raw revisions in finddeltainfo
Boris Feld <boris.feld@octobus.net>
parents: 39331
diff changeset
   823
        # 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: 39331
diff changeset
   824
        # 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: 39331
diff changeset
   825
        # avoid overhead fetching flags again.
6f4b8f607a31 revlogdeltas: move special cases around raw revisions in finddeltainfo
Boris Feld <boris.feld@octobus.net>
parents: 39331
diff changeset
   826
        if revinfo.flags & REVIDX_RAWTEXT_CHANGING_FLAGS:
39333
5d343a24bff5 revlogdeltas: always return a delta info object in finddeltainfo
Boris Feld <boris.feld@octobus.net>
parents: 39332
diff changeset
   827
            return self._fullsnapshotinfo(fh, revinfo)
39332
6f4b8f607a31 revlogdeltas: move special cases around raw revisions in finddeltainfo
Boris Feld <boris.feld@octobus.net>
parents: 39331
diff changeset
   828
35738
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   829
        cachedelta = revinfo.cachedelta
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   830
        p1 = revinfo.p1
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   831
        p2 = revinfo.p2
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
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   834
        deltainfo = None
39335
1441eb38849f revlogdeltas: pass revision number to _candidatesgroups
Boris Feld <boris.feld@octobus.net>
parents: 39334
diff changeset
   835
        p1r, p2r = revlog.rev(p1), revlog.rev(p2)
39337
37957e07138c revlogdeltas: move finddeltainfo filtering inside _candidategroups
Boris Feld <boris.feld@octobus.net>
parents: 39336
diff changeset
   836
        groups = _candidategroups(self.revlog, revinfo.textlen,
37957e07138c revlogdeltas: move finddeltainfo filtering inside _candidategroups
Boris Feld <boris.feld@octobus.net>
parents: 39336
diff changeset
   837
                                             p1r, p2r, cachedelta)
39334
507f5b1dd7c8 revlogdeltas: extract _getcandidaterevs in a function
Boris Feld <boris.feld@octobus.net>
parents: 39333
diff changeset
   838
        for candidaterevs in groups:
35738
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   839
            nominateddeltas = []
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   840
            for candidaterev in candidaterevs:
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   841
                candidatedelta = self._builddeltainfo(revinfo, candidaterev, fh)
39330
655b5b465953 revlog: split functionality related to deltas computation in a new module
Boris Feld <boris.feld@octobus.net>
parents: 39329
diff changeset
   842
                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
   843
                    nominateddeltas.append(candidatedelta)
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   844
            if nominateddeltas:
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   845
                deltainfo = min(nominateddeltas, key=lambda x: x.deltalen)
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   846
                break
f90f6fd130c1 revlog: group delta computation methods under _deltacomputer object
Paul Morelle <paul.morelle@octobus.net>
parents: 35737
diff changeset
   847
39333
5d343a24bff5 revlogdeltas: always return a delta info object in finddeltainfo
Boris Feld <boris.feld@octobus.net>
parents: 39332
diff changeset
   848
        if deltainfo is None:
5d343a24bff5 revlogdeltas: always return a delta info object in finddeltainfo
Boris Feld <boris.feld@octobus.net>
parents: 39332
diff changeset
   849
            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
   850
        return deltainfo