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