##// END OF EJS Templates
revlog: add a children function...
mpm@selenic.com -
r370:c90385d8 default
parent child Browse files
Show More
@@ -1,522 +1,535 b''
1 # revlog.py - storage back-end for mercurial
1 # revlog.py - storage back-end for mercurial
2 #
2 #
3 # This provides efficient delta storage with O(1) retrieve and append
3 # This provides efficient delta storage with O(1) retrieve and append
4 # and O(changes) merge between branches
4 # and O(changes) merge between branches
5 #
5 #
6 # Copyright 2005 Matt Mackall <mpm@selenic.com>
6 # Copyright 2005 Matt Mackall <mpm@selenic.com>
7 #
7 #
8 # This software may be used and distributed according to the terms
8 # This software may be used and distributed according to the terms
9 # of the GNU General Public License, incorporated herein by reference.
9 # of the GNU General Public License, incorporated herein by reference.
10
10
11 import zlib, struct, sha, binascii, heapq
11 import zlib, struct, sha, binascii, heapq
12 from mercurial import mdiff
12 from mercurial import mdiff
13
13
14 def hex(node): return binascii.hexlify(node)
14 def hex(node): return binascii.hexlify(node)
15 def bin(node): return binascii.unhexlify(node)
15 def bin(node): return binascii.unhexlify(node)
16 def short(node): return hex(node[:4])
16 def short(node): return hex(node[:4])
17
17
18 def compress(text):
18 def compress(text):
19 if not text: return text
19 if not text: return text
20 if len(text) < 44:
20 if len(text) < 44:
21 if text[0] == '\0': return text
21 if text[0] == '\0': return text
22 return 'u' + text
22 return 'u' + text
23 bin = zlib.compress(text)
23 bin = zlib.compress(text)
24 if len(bin) > len(text):
24 if len(bin) > len(text):
25 if text[0] == '\0': return text
25 if text[0] == '\0': return text
26 return 'u' + text
26 return 'u' + text
27 return bin
27 return bin
28
28
29 def decompress(bin):
29 def decompress(bin):
30 if not bin: return bin
30 if not bin: return bin
31 t = bin[0]
31 t = bin[0]
32 if t == '\0': return bin
32 if t == '\0': return bin
33 if t == 'x': return zlib.decompress(bin)
33 if t == 'x': return zlib.decompress(bin)
34 if t == 'u': return bin[1:]
34 if t == 'u': return bin[1:]
35 raise "unknown compression type %s" % t
35 raise "unknown compression type %s" % t
36
36
37 def hash(text, p1, p2):
37 def hash(text, p1, p2):
38 l = [p1, p2]
38 l = [p1, p2]
39 l.sort()
39 l.sort()
40 return sha.sha(l[0] + l[1] + text).digest()
40 return sha.sha(l[0] + l[1] + text).digest()
41
41
42 nullid = "\0" * 20
42 nullid = "\0" * 20
43 indexformat = ">4l20s20s20s"
43 indexformat = ">4l20s20s20s"
44
44
45 class lazyparser:
45 class lazyparser:
46 def __init__(self, data, revlog):
46 def __init__(self, data, revlog):
47 self.data = data
47 self.data = data
48 self.s = struct.calcsize(indexformat)
48 self.s = struct.calcsize(indexformat)
49 self.l = len(data)/self.s
49 self.l = len(data)/self.s
50 self.index = [None] * self.l
50 self.index = [None] * self.l
51 self.map = {nullid: -1}
51 self.map = {nullid: -1}
52 self.all = 0
52 self.all = 0
53 self.revlog = revlog
53 self.revlog = revlog
54
54
55 def load(self, pos=None):
55 def load(self, pos=None):
56 if self.all: return
56 if self.all: return
57 if pos is not None:
57 if pos is not None:
58 block = pos / 1000
58 block = pos / 1000
59 i = block * 1000
59 i = block * 1000
60 end = min(self.l, i + 1000)
60 end = min(self.l, i + 1000)
61 else:
61 else:
62 self.all = 1
62 self.all = 1
63 i = 0
63 i = 0
64 end = self.l
64 end = self.l
65 self.revlog.index = self.index
65 self.revlog.index = self.index
66 self.revlog.nodemap = self.map
66 self.revlog.nodemap = self.map
67
67
68 while i < end:
68 while i < end:
69 d = self.data[i * self.s: (i + 1) * self.s]
69 d = self.data[i * self.s: (i + 1) * self.s]
70 e = struct.unpack(indexformat, d)
70 e = struct.unpack(indexformat, d)
71 self.index[i] = e
71 self.index[i] = e
72 self.map[e[6]] = i
72 self.map[e[6]] = i
73 i += 1
73 i += 1
74
74
75 class lazyindex:
75 class lazyindex:
76 def __init__(self, parser):
76 def __init__(self, parser):
77 self.p = parser
77 self.p = parser
78 def __len__(self):
78 def __len__(self):
79 return len(self.p.index)
79 return len(self.p.index)
80 def load(self, pos):
80 def load(self, pos):
81 self.p.load(pos)
81 self.p.load(pos)
82 return self.p.index[pos]
82 return self.p.index[pos]
83 def __getitem__(self, pos):
83 def __getitem__(self, pos):
84 return self.p.index[pos] or self.load(pos)
84 return self.p.index[pos] or self.load(pos)
85 def append(self, e):
85 def append(self, e):
86 self.p.index.append(e)
86 self.p.index.append(e)
87
87
88 class lazymap:
88 class lazymap:
89 def __init__(self, parser):
89 def __init__(self, parser):
90 self.p = parser
90 self.p = parser
91 def load(self, key):
91 def load(self, key):
92 if self.p.all: return
92 if self.p.all: return
93 n = self.p.data.find(key)
93 n = self.p.data.find(key)
94 if n < 0: raise KeyError("node " + hex(key))
94 if n < 0: raise KeyError("node " + hex(key))
95 pos = n / self.p.s
95 pos = n / self.p.s
96 self.p.load(pos)
96 self.p.load(pos)
97 def __contains__(self, key):
97 def __contains__(self, key):
98 self.p.load()
98 self.p.load()
99 return key in self.p.map
99 return key in self.p.map
100 def __iter__(self):
100 def __iter__(self):
101 for i in xrange(self.p.l):
101 for i in xrange(self.p.l):
102 try:
102 try:
103 yield self.p.index[i][6]
103 yield self.p.index[i][6]
104 except:
104 except:
105 self.p.load(i)
105 self.p.load(i)
106 yield self.p.index[i][6]
106 yield self.p.index[i][6]
107 def __getitem__(self, key):
107 def __getitem__(self, key):
108 try:
108 try:
109 return self.p.map[key]
109 return self.p.map[key]
110 except KeyError:
110 except KeyError:
111 try:
111 try:
112 self.load(key)
112 self.load(key)
113 return self.p.map[key]
113 return self.p.map[key]
114 except KeyError:
114 except KeyError:
115 raise KeyError("node " + hex(key))
115 raise KeyError("node " + hex(key))
116 def __setitem__(self, key, val):
116 def __setitem__(self, key, val):
117 self.p.map[key] = val
117 self.p.map[key] = val
118
118
119 class revlog:
119 class revlog:
120 def __init__(self, opener, indexfile, datafile):
120 def __init__(self, opener, indexfile, datafile):
121 self.indexfile = indexfile
121 self.indexfile = indexfile
122 self.datafile = datafile
122 self.datafile = datafile
123 self.opener = opener
123 self.opener = opener
124 self.cache = None
124 self.cache = None
125
125
126 try:
126 try:
127 i = self.opener(self.indexfile).read()
127 i = self.opener(self.indexfile).read()
128 except IOError:
128 except IOError:
129 i = ""
129 i = ""
130
130
131 if len(i) > 10000:
131 if len(i) > 10000:
132 # big index, let's parse it on demand
132 # big index, let's parse it on demand
133 parser = lazyparser(i, self)
133 parser = lazyparser(i, self)
134 self.index = lazyindex(parser)
134 self.index = lazyindex(parser)
135 self.nodemap = lazymap(parser)
135 self.nodemap = lazymap(parser)
136 else:
136 else:
137 s = struct.calcsize(indexformat)
137 s = struct.calcsize(indexformat)
138 l = len(i) / s
138 l = len(i) / s
139 self.index = [None] * l
139 self.index = [None] * l
140 m = [None] * l
140 m = [None] * l
141
141
142 n = 0
142 n = 0
143 for f in xrange(0, len(i), s):
143 for f in xrange(0, len(i), s):
144 # offset, size, base, linkrev, p1, p2, nodeid
144 # offset, size, base, linkrev, p1, p2, nodeid
145 e = struct.unpack(indexformat, i[f:f + s])
145 e = struct.unpack(indexformat, i[f:f + s])
146 m[n] = (e[6], n)
146 m[n] = (e[6], n)
147 self.index[n] = e
147 self.index[n] = e
148 n += 1
148 n += 1
149
149
150 self.nodemap = dict(m)
150 self.nodemap = dict(m)
151 self.nodemap[nullid] = -1
151 self.nodemap[nullid] = -1
152
152
153
153
154 def tip(self): return self.node(len(self.index) - 1)
154 def tip(self): return self.node(len(self.index) - 1)
155 def count(self): return len(self.index)
155 def count(self): return len(self.index)
156 def node(self, rev): return (rev < 0) and nullid or self.index[rev][6]
156 def node(self, rev): return (rev < 0) and nullid or self.index[rev][6]
157 def rev(self, node): return self.nodemap[node]
157 def rev(self, node): return self.nodemap[node]
158 def linkrev(self, node): return self.index[self.nodemap[node]][3]
158 def linkrev(self, node): return self.index[self.nodemap[node]][3]
159 def parents(self, node):
159 def parents(self, node):
160 if node == nullid: return (nullid, nullid)
160 if node == nullid: return (nullid, nullid)
161 return self.index[self.nodemap[node]][4:6]
161 return self.index[self.nodemap[node]][4:6]
162
162
163 def start(self, rev): return self.index[rev][0]
163 def start(self, rev): return self.index[rev][0]
164 def length(self, rev): return self.index[rev][1]
164 def length(self, rev): return self.index[rev][1]
165 def end(self, rev): return self.start(rev) + self.length(rev)
165 def end(self, rev): return self.start(rev) + self.length(rev)
166 def base(self, rev): return self.index[rev][2]
166 def base(self, rev): return self.index[rev][2]
167
167
168 def heads(self):
168 def heads(self):
169 p = {}
169 p = {}
170 h = []
170 h = []
171 for r in range(self.count() - 1, -1, -1):
171 for r in range(self.count() - 1, -1, -1):
172 n = self.node(r)
172 n = self.node(r)
173 if n not in p:
173 if n not in p:
174 h.append(n)
174 h.append(n)
175 for pn in self.parents(n):
175 for pn in self.parents(n):
176 p[pn] = 1
176 p[pn] = 1
177 return h
177 return h
178
179 def children(self, node):
180 c = []
181 p = self.rev(node)
182 for r in range(p + 1, self.count()):
183 n = self.node(r)
184 for pn in self.parents(n):
185 if pn == p:
186 c.append(p)
187 continue
188 elif pn == nullid:
189 continue
190 return c
178
191
179 def lookup(self, id):
192 def lookup(self, id):
180 try:
193 try:
181 rev = int(id)
194 rev = int(id)
182 return self.node(rev)
195 return self.node(rev)
183 except ValueError:
196 except ValueError:
184 c = []
197 c = []
185 for n in self.nodemap:
198 for n in self.nodemap:
186 if id in hex(n):
199 if id in hex(n):
187 c.append(n)
200 c.append(n)
188 if len(c) > 1: raise KeyError("Ambiguous identifier")
201 if len(c) > 1: raise KeyError("Ambiguous identifier")
189 if len(c) < 1: raise KeyError("No match found")
202 if len(c) < 1: raise KeyError("No match found")
190 return c[0]
203 return c[0]
191
204
192 return None
205 return None
193
206
194 def diff(self, a, b):
207 def diff(self, a, b):
195 return mdiff.textdiff(a, b)
208 return mdiff.textdiff(a, b)
196
209
197 def patches(self, t, pl):
210 def patches(self, t, pl):
198 return mdiff.patches(t, pl)
211 return mdiff.patches(t, pl)
199
212
200 def delta(self, node):
213 def delta(self, node):
201 r = self.rev(node)
214 r = self.rev(node)
202 b = self.base(r)
215 b = self.base(r)
203 if r == b:
216 if r == b:
204 return self.diff(self.revision(self.node(r - 1)),
217 return self.diff(self.revision(self.node(r - 1)),
205 self.revision(node))
218 self.revision(node))
206 else:
219 else:
207 f = self.opener(self.datafile)
220 f = self.opener(self.datafile)
208 f.seek(self.start(r))
221 f.seek(self.start(r))
209 data = f.read(self.length(r))
222 data = f.read(self.length(r))
210 return decompress(data)
223 return decompress(data)
211
224
212 def revision(self, node):
225 def revision(self, node):
213 if node == nullid: return ""
226 if node == nullid: return ""
214 if self.cache and self.cache[0] == node: return self.cache[2]
227 if self.cache and self.cache[0] == node: return self.cache[2]
215
228
216 text = None
229 text = None
217 rev = self.rev(node)
230 rev = self.rev(node)
218 start, length, base, link, p1, p2, node = self.index[rev]
231 start, length, base, link, p1, p2, node = self.index[rev]
219 end = start + length
232 end = start + length
220 if base != rev: start = self.start(base)
233 if base != rev: start = self.start(base)
221
234
222 if self.cache and self.cache[1] >= base and self.cache[1] < rev:
235 if self.cache and self.cache[1] >= base and self.cache[1] < rev:
223 base = self.cache[1]
236 base = self.cache[1]
224 start = self.start(base + 1)
237 start = self.start(base + 1)
225 text = self.cache[2]
238 text = self.cache[2]
226 last = 0
239 last = 0
227
240
228 f = self.opener(self.datafile)
241 f = self.opener(self.datafile)
229 f.seek(start)
242 f.seek(start)
230 data = f.read(end - start)
243 data = f.read(end - start)
231
244
232 if not text:
245 if not text:
233 last = self.length(base)
246 last = self.length(base)
234 text = decompress(data[:last])
247 text = decompress(data[:last])
235
248
236 bins = []
249 bins = []
237 for r in xrange(base + 1, rev + 1):
250 for r in xrange(base + 1, rev + 1):
238 s = self.length(r)
251 s = self.length(r)
239 bins.append(decompress(data[last:last + s]))
252 bins.append(decompress(data[last:last + s]))
240 last = last + s
253 last = last + s
241
254
242 text = mdiff.patches(text, bins)
255 text = mdiff.patches(text, bins)
243
256
244 if node != hash(text, p1, p2):
257 if node != hash(text, p1, p2):
245 raise IOError("integrity check failed on %s:%d"
258 raise IOError("integrity check failed on %s:%d"
246 % (self.datafile, rev))
259 % (self.datafile, rev))
247
260
248 self.cache = (node, rev, text)
261 self.cache = (node, rev, text)
249 return text
262 return text
250
263
251 def addrevision(self, text, transaction, link, p1=None, p2=None):
264 def addrevision(self, text, transaction, link, p1=None, p2=None):
252 if text is None: text = ""
265 if text is None: text = ""
253 if p1 is None: p1 = self.tip()
266 if p1 is None: p1 = self.tip()
254 if p2 is None: p2 = nullid
267 if p2 is None: p2 = nullid
255
268
256 node = hash(text, p1, p2)
269 node = hash(text, p1, p2)
257
270
258 if node in self.nodemap:
271 if node in self.nodemap:
259 return node
272 return node
260
273
261 n = self.count()
274 n = self.count()
262 t = n - 1
275 t = n - 1
263
276
264 if n:
277 if n:
265 base = self.base(t)
278 base = self.base(t)
266 start = self.start(base)
279 start = self.start(base)
267 end = self.end(t)
280 end = self.end(t)
268 prev = self.revision(self.tip())
281 prev = self.revision(self.tip())
269 d = self.diff(prev, text)
282 d = self.diff(prev, text)
270 data = compress(d)
283 data = compress(d)
271 dist = end - start + len(data)
284 dist = end - start + len(data)
272
285
273 # full versions are inserted when the needed deltas
286 # full versions are inserted when the needed deltas
274 # become comparable to the uncompressed text
287 # become comparable to the uncompressed text
275 if not n or dist > len(text) * 2:
288 if not n or dist > len(text) * 2:
276 data = compress(text)
289 data = compress(text)
277 base = n
290 base = n
278 else:
291 else:
279 base = self.base(t)
292 base = self.base(t)
280
293
281 offset = 0
294 offset = 0
282 if t >= 0:
295 if t >= 0:
283 offset = self.end(t)
296 offset = self.end(t)
284
297
285 e = (offset, len(data), base, link, p1, p2, node)
298 e = (offset, len(data), base, link, p1, p2, node)
286
299
287 self.index.append(e)
300 self.index.append(e)
288 self.nodemap[node] = n
301 self.nodemap[node] = n
289 entry = struct.pack(indexformat, *e)
302 entry = struct.pack(indexformat, *e)
290
303
291 transaction.add(self.datafile, e[0])
304 transaction.add(self.datafile, e[0])
292 self.opener(self.datafile, "a").write(data)
305 self.opener(self.datafile, "a").write(data)
293 transaction.add(self.indexfile, n * len(entry))
306 transaction.add(self.indexfile, n * len(entry))
294 self.opener(self.indexfile, "a").write(entry)
307 self.opener(self.indexfile, "a").write(entry)
295
308
296 self.cache = (node, n, text)
309 self.cache = (node, n, text)
297 return node
310 return node
298
311
299 def ancestor(self, a, b):
312 def ancestor(self, a, b):
300 # calculate the distance of every node from root
313 # calculate the distance of every node from root
301 dist = {nullid: 0}
314 dist = {nullid: 0}
302 for i in xrange(self.count()):
315 for i in xrange(self.count()):
303 n = self.node(i)
316 n = self.node(i)
304 p1, p2 = self.parents(n)
317 p1, p2 = self.parents(n)
305 dist[n] = max(dist[p1], dist[p2]) + 1
318 dist[n] = max(dist[p1], dist[p2]) + 1
306
319
307 # traverse ancestors in order of decreasing distance from root
320 # traverse ancestors in order of decreasing distance from root
308 def ancestors(node):
321 def ancestors(node):
309 # we store negative distances because heap returns smallest member
322 # we store negative distances because heap returns smallest member
310 h = [(-dist[node], node)]
323 h = [(-dist[node], node)]
311 seen = {}
324 seen = {}
312 earliest = self.count()
325 earliest = self.count()
313 while h:
326 while h:
314 d, n = heapq.heappop(h)
327 d, n = heapq.heappop(h)
315 r = self.rev(n)
328 r = self.rev(n)
316 if n not in seen:
329 if n not in seen:
317 seen[n] = 1
330 seen[n] = 1
318 yield (-d, n)
331 yield (-d, n)
319 for p in self.parents(n):
332 for p in self.parents(n):
320 heapq.heappush(h, (-dist[p], p))
333 heapq.heappush(h, (-dist[p], p))
321
334
322 x = ancestors(a)
335 x = ancestors(a)
323 y = ancestors(b)
336 y = ancestors(b)
324 lx = x.next()
337 lx = x.next()
325 ly = y.next()
338 ly = y.next()
326
339
327 # increment each ancestor list until it is closer to root than
340 # increment each ancestor list until it is closer to root than
328 # the other, or they match
341 # the other, or they match
329 while 1:
342 while 1:
330 if lx == ly:
343 if lx == ly:
331 return lx[1]
344 return lx[1]
332 elif lx < ly:
345 elif lx < ly:
333 ly = y.next()
346 ly = y.next()
334 elif lx > ly:
347 elif lx > ly:
335 lx = x.next()
348 lx = x.next()
336
349
337 def group(self, linkmap):
350 def group(self, linkmap):
338 # given a list of changeset revs, return a set of deltas and
351 # given a list of changeset revs, return a set of deltas and
339 # metadata corresponding to nodes. the first delta is
352 # metadata corresponding to nodes. the first delta is
340 # parent(nodes[0]) -> nodes[0] the receiver is guaranteed to
353 # parent(nodes[0]) -> nodes[0] the receiver is guaranteed to
341 # have this parent as it has all history before these
354 # have this parent as it has all history before these
342 # changesets. parent is parent[0]
355 # changesets. parent is parent[0]
343
356
344 revs = []
357 revs = []
345 needed = {}
358 needed = {}
346
359
347 # find file nodes/revs that match changeset revs
360 # find file nodes/revs that match changeset revs
348 for i in xrange(0, self.count()):
361 for i in xrange(0, self.count()):
349 if self.index[i][3] in linkmap:
362 if self.index[i][3] in linkmap:
350 revs.append(i)
363 revs.append(i)
351 needed[i] = 1
364 needed[i] = 1
352
365
353 # if we don't have any revisions touched by these changesets, bail
366 # if we don't have any revisions touched by these changesets, bail
354 if not revs:
367 if not revs:
355 yield struct.pack(">l", 0)
368 yield struct.pack(">l", 0)
356 return
369 return
357
370
358 # add the parent of the first rev
371 # add the parent of the first rev
359 p = self.parents(self.node(revs[0]))[0]
372 p = self.parents(self.node(revs[0]))[0]
360 revs.insert(0, self.rev(p))
373 revs.insert(0, self.rev(p))
361
374
362 # for each delta that isn't contiguous in the log, we need to
375 # for each delta that isn't contiguous in the log, we need to
363 # reconstruct the base, reconstruct the result, and then
376 # reconstruct the base, reconstruct the result, and then
364 # calculate the delta. We also need to do this where we've
377 # calculate the delta. We also need to do this where we've
365 # stored a full version and not a delta
378 # stored a full version and not a delta
366 for i in xrange(0, len(revs) - 1):
379 for i in xrange(0, len(revs) - 1):
367 a, b = revs[i], revs[i + 1]
380 a, b = revs[i], revs[i + 1]
368 if a + 1 != b or self.base(b) == b:
381 if a + 1 != b or self.base(b) == b:
369 for j in xrange(self.base(a), a + 1):
382 for j in xrange(self.base(a), a + 1):
370 needed[j] = 1
383 needed[j] = 1
371 for j in xrange(self.base(b), b + 1):
384 for j in xrange(self.base(b), b + 1):
372 needed[j] = 1
385 needed[j] = 1
373
386
374 # calculate spans to retrieve from datafile
387 # calculate spans to retrieve from datafile
375 needed = needed.keys()
388 needed = needed.keys()
376 needed.sort()
389 needed.sort()
377 spans = []
390 spans = []
378 oo = -1
391 oo = -1
379 ol = 0
392 ol = 0
380 for n in needed:
393 for n in needed:
381 if n < 0: continue
394 if n < 0: continue
382 o = self.start(n)
395 o = self.start(n)
383 l = self.length(n)
396 l = self.length(n)
384 if oo + ol == o: # can we merge with the previous?
397 if oo + ol == o: # can we merge with the previous?
385 nl = spans[-1][2]
398 nl = spans[-1][2]
386 nl.append((n, l))
399 nl.append((n, l))
387 ol += l
400 ol += l
388 spans[-1] = (oo, ol, nl)
401 spans[-1] = (oo, ol, nl)
389 else:
402 else:
390 oo = o
403 oo = o
391 ol = l
404 ol = l
392 spans.append((oo, ol, [(n, l)]))
405 spans.append((oo, ol, [(n, l)]))
393
406
394 # read spans in, divide up chunks
407 # read spans in, divide up chunks
395 chunks = {}
408 chunks = {}
396 for span in spans:
409 for span in spans:
397 # we reopen the file for each span to make http happy for now
410 # we reopen the file for each span to make http happy for now
398 f = self.opener(self.datafile)
411 f = self.opener(self.datafile)
399 f.seek(span[0])
412 f.seek(span[0])
400 data = f.read(span[1])
413 data = f.read(span[1])
401
414
402 # divide up the span
415 # divide up the span
403 pos = 0
416 pos = 0
404 for r, l in span[2]:
417 for r, l in span[2]:
405 chunks[r] = decompress(data[pos: pos + l])
418 chunks[r] = decompress(data[pos: pos + l])
406 pos += l
419 pos += l
407
420
408 # helper to reconstruct intermediate versions
421 # helper to reconstruct intermediate versions
409 def construct(text, base, rev):
422 def construct(text, base, rev):
410 bins = [chunks[r] for r in xrange(base + 1, rev + 1)]
423 bins = [chunks[r] for r in xrange(base + 1, rev + 1)]
411 return mdiff.patches(text, bins)
424 return mdiff.patches(text, bins)
412
425
413 # build deltas
426 # build deltas
414 deltas = []
427 deltas = []
415 for d in xrange(0, len(revs) - 1):
428 for d in xrange(0, len(revs) - 1):
416 a, b = revs[d], revs[d + 1]
429 a, b = revs[d], revs[d + 1]
417 n = self.node(b)
430 n = self.node(b)
418
431
419 # do we need to construct a new delta?
432 # do we need to construct a new delta?
420 if a + 1 != b or self.base(b) == b:
433 if a + 1 != b or self.base(b) == b:
421 if a >= 0:
434 if a >= 0:
422 base = self.base(a)
435 base = self.base(a)
423 ta = chunks[self.base(a)]
436 ta = chunks[self.base(a)]
424 ta = construct(ta, base, a)
437 ta = construct(ta, base, a)
425 else:
438 else:
426 ta = ""
439 ta = ""
427
440
428 base = self.base(b)
441 base = self.base(b)
429 if a > base:
442 if a > base:
430 base = a
443 base = a
431 tb = ta
444 tb = ta
432 else:
445 else:
433 tb = chunks[self.base(b)]
446 tb = chunks[self.base(b)]
434 tb = construct(tb, base, b)
447 tb = construct(tb, base, b)
435 d = self.diff(ta, tb)
448 d = self.diff(ta, tb)
436 else:
449 else:
437 d = chunks[b]
450 d = chunks[b]
438
451
439 p = self.parents(n)
452 p = self.parents(n)
440 meta = n + p[0] + p[1] + linkmap[self.linkrev(n)]
453 meta = n + p[0] + p[1] + linkmap[self.linkrev(n)]
441 l = struct.pack(">l", len(meta) + len(d) + 4)
454 l = struct.pack(">l", len(meta) + len(d) + 4)
442 yield l
455 yield l
443 yield meta
456 yield meta
444 yield d
457 yield d
445
458
446 yield struct.pack(">l", 0)
459 yield struct.pack(">l", 0)
447
460
448 def addgroup(self, revs, linkmapper, transaction, unique = 0):
461 def addgroup(self, revs, linkmapper, transaction, unique = 0):
449 # given a set of deltas, add them to the revision log. the
462 # given a set of deltas, add them to the revision log. the
450 # first delta is against its parent, which should be in our
463 # first delta is against its parent, which should be in our
451 # log, the rest are against the previous delta.
464 # log, the rest are against the previous delta.
452
465
453 # track the base of the current delta log
466 # track the base of the current delta log
454 r = self.count()
467 r = self.count()
455 t = r - 1
468 t = r - 1
456 node = nullid
469 node = nullid
457
470
458 base = prev = -1
471 base = prev = -1
459 start = end = 0
472 start = end = 0
460 if r:
473 if r:
461 start = self.start(self.base(t))
474 start = self.start(self.base(t))
462 end = self.end(t)
475 end = self.end(t)
463 measure = self.length(self.base(t))
476 measure = self.length(self.base(t))
464 base = self.base(t)
477 base = self.base(t)
465 prev = self.tip()
478 prev = self.tip()
466
479
467 transaction.add(self.datafile, end)
480 transaction.add(self.datafile, end)
468 transaction.add(self.indexfile, r * struct.calcsize(indexformat))
481 transaction.add(self.indexfile, r * struct.calcsize(indexformat))
469 dfh = self.opener(self.datafile, "a")
482 dfh = self.opener(self.datafile, "a")
470 ifh = self.opener(self.indexfile, "a")
483 ifh = self.opener(self.indexfile, "a")
471
484
472 # loop through our set of deltas
485 # loop through our set of deltas
473 chain = None
486 chain = None
474 for chunk in revs:
487 for chunk in revs:
475 node, p1, p2, cs = struct.unpack("20s20s20s20s", chunk[:80])
488 node, p1, p2, cs = struct.unpack("20s20s20s20s", chunk[:80])
476 link = linkmapper(cs)
489 link = linkmapper(cs)
477 if node in self.nodemap:
490 if node in self.nodemap:
478 # this can happen if two branches make the same change
491 # this can happen if two branches make the same change
479 if unique:
492 if unique:
480 raise "already have %s" % hex(node[:4])
493 raise "already have %s" % hex(node[:4])
481 continue
494 continue
482 delta = chunk[80:]
495 delta = chunk[80:]
483
496
484 if not chain:
497 if not chain:
485 # retrieve the parent revision of the delta chain
498 # retrieve the parent revision of the delta chain
486 chain = p1
499 chain = p1
487 if not chain in self.nodemap:
500 if not chain in self.nodemap:
488 raise "unknown base %s" % short(chain[:4])
501 raise "unknown base %s" % short(chain[:4])
489
502
490 # full versions are inserted when the needed deltas become
503 # full versions are inserted when the needed deltas become
491 # comparable to the uncompressed text or when the previous
504 # comparable to the uncompressed text or when the previous
492 # version is not the one we have a delta against. We use
505 # version is not the one we have a delta against. We use
493 # the size of the previous full rev as a proxy for the
506 # the size of the previous full rev as a proxy for the
494 # current size.
507 # current size.
495
508
496 if chain == prev:
509 if chain == prev:
497 cdelta = compress(delta)
510 cdelta = compress(delta)
498
511
499 if chain != prev or (end - start + len(cdelta)) > measure * 2:
512 if chain != prev or (end - start + len(cdelta)) > measure * 2:
500 # flush our writes here so we can read it in revision
513 # flush our writes here so we can read it in revision
501 dfh.flush()
514 dfh.flush()
502 ifh.flush()
515 ifh.flush()
503 text = self.revision(chain)
516 text = self.revision(chain)
504 text = self.patches(text, [delta])
517 text = self.patches(text, [delta])
505 chk = self.addrevision(text, transaction, link, p1, p2)
518 chk = self.addrevision(text, transaction, link, p1, p2)
506 if chk != node:
519 if chk != node:
507 raise "consistency error adding group"
520 raise "consistency error adding group"
508 measure = len(text)
521 measure = len(text)
509 else:
522 else:
510 e = (end, len(cdelta), self.base(t), link, p1, p2, node)
523 e = (end, len(cdelta), self.base(t), link, p1, p2, node)
511 self.index.append(e)
524 self.index.append(e)
512 self.nodemap[node] = r
525 self.nodemap[node] = r
513 dfh.write(cdelta)
526 dfh.write(cdelta)
514 ifh.write(struct.pack(indexformat, *e))
527 ifh.write(struct.pack(indexformat, *e))
515
528
516 t, r, chain, prev = r, r + 1, node, node
529 t, r, chain, prev = r, r + 1, node, node
517 start = self.start(self.base(t))
530 start = self.start(self.base(t))
518 end = self.end(t)
531 end = self.end(t)
519
532
520 dfh.close()
533 dfh.close()
521 ifh.close()
534 ifh.close()
522 return node
535 return node
General Comments 0
You need to be logged in to leave comments. Login now