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