##// END OF EJS Templates
revlog.children: use parentrevs instead of parents
Benoit Boissinot -
r3470:c6773b7e default
parent child Browse files
Show More
@@ -1,1268 +1,1264 b''
1 1 """
2 2 revlog.py - storage back-end for mercurial
3 3
4 4 This provides efficient delta storage with O(1) retrieve and append
5 5 and O(changes) merge between branches
6 6
7 7 Copyright 2005, 2006 Matt Mackall <mpm@selenic.com>
8 8
9 9 This software may be used and distributed according to the terms
10 10 of the GNU General Public License, incorporated herein by reference.
11 11 """
12 12
13 13 from node import *
14 14 from i18n import gettext as _
15 15 from demandload import demandload
16 16 demandload(globals(), "binascii changegroup errno ancestor mdiff os")
17 17 demandload(globals(), "sha struct util zlib")
18 18
19 19 # revlog version strings
20 20 REVLOGV0 = 0
21 21 REVLOGNG = 1
22 22
23 23 # revlog flags
24 24 REVLOGNGINLINEDATA = (1 << 16)
25 25 REVLOG_DEFAULT_FLAGS = REVLOGNGINLINEDATA
26 26
27 27 REVLOG_DEFAULT_FORMAT = REVLOGNG
28 28 REVLOG_DEFAULT_VERSION = REVLOG_DEFAULT_FORMAT | REVLOG_DEFAULT_FLAGS
29 29
30 30 def flagstr(flag):
31 31 if flag == "inline":
32 32 return REVLOGNGINLINEDATA
33 33 raise RevlogError(_("unknown revlog flag %s" % flag))
34 34
35 35 def hash(text, p1, p2):
36 36 """generate a hash from the given text and its parent hashes
37 37
38 38 This hash combines both the current file contents and its history
39 39 in a manner that makes it easy to distinguish nodes with the same
40 40 content in the revision graph.
41 41 """
42 42 l = [p1, p2]
43 43 l.sort()
44 44 s = sha.new(l[0])
45 45 s.update(l[1])
46 46 s.update(text)
47 47 return s.digest()
48 48
49 49 def compress(text):
50 50 """ generate a possibly-compressed representation of text """
51 51 if not text: return ("", text)
52 52 if len(text) < 44:
53 53 if text[0] == '\0': return ("", text)
54 54 return ('u', text)
55 55 bin = zlib.compress(text)
56 56 if len(bin) > len(text):
57 57 if text[0] == '\0': return ("", text)
58 58 return ('u', text)
59 59 return ("", bin)
60 60
61 61 def decompress(bin):
62 62 """ decompress the given input """
63 63 if not bin: return bin
64 64 t = bin[0]
65 65 if t == '\0': return bin
66 66 if t == 'x': return zlib.decompress(bin)
67 67 if t == 'u': return bin[1:]
68 68 raise RevlogError(_("unknown compression type %r") % t)
69 69
70 70 indexformatv0 = ">4l20s20s20s"
71 71 v0shaoffset = 56
72 72 # index ng:
73 73 # 6 bytes offset
74 74 # 2 bytes flags
75 75 # 4 bytes compressed length
76 76 # 4 bytes uncompressed length
77 77 # 4 bytes: base rev
78 78 # 4 bytes link rev
79 79 # 4 bytes parent 1 rev
80 80 # 4 bytes parent 2 rev
81 81 # 32 bytes: nodeid
82 82 indexformatng = ">Qiiiiii20s12x"
83 83 ngshaoffset = 32
84 84 versionformat = ">i"
85 85
86 86 class lazyparser(object):
87 87 """
88 88 this class avoids the need to parse the entirety of large indices
89 89 """
90 90
91 91 # lazyparser is not safe to use on windows if win32 extensions not
92 92 # available. it keeps file handle open, which make it not possible
93 93 # to break hardlinks on local cloned repos.
94 94 safe_to_use = os.name != 'nt' or (not util.is_win_9x() and
95 95 hasattr(util, 'win32api'))
96 96
97 97 def __init__(self, dataf, size, indexformat, shaoffset):
98 98 self.dataf = dataf
99 99 self.format = indexformat
100 100 self.s = struct.calcsize(indexformat)
101 101 self.indexformat = indexformat
102 102 self.datasize = size
103 103 self.l = size/self.s
104 104 self.index = [None] * self.l
105 105 self.map = {nullid: -1}
106 106 self.allmap = 0
107 107 self.all = 0
108 108 self.mapfind_count = 0
109 109 self.shaoffset = shaoffset
110 110
111 111 def loadmap(self):
112 112 """
113 113 during a commit, we need to make sure the rev being added is
114 114 not a duplicate. This requires loading the entire index,
115 115 which is fairly slow. loadmap can load up just the node map,
116 116 which takes much less time.
117 117 """
118 118 if self.allmap: return
119 119 end = self.datasize
120 120 self.allmap = 1
121 121 cur = 0
122 122 count = 0
123 123 blocksize = self.s * 256
124 124 self.dataf.seek(0)
125 125 while cur < end:
126 126 data = self.dataf.read(blocksize)
127 127 off = 0
128 128 for x in xrange(256):
129 129 n = data[off + self.shaoffset:off + self.shaoffset + 20]
130 130 self.map[n] = count
131 131 count += 1
132 132 if count >= self.l:
133 133 break
134 134 off += self.s
135 135 cur += blocksize
136 136
137 137 def loadblock(self, blockstart, blocksize, data=None):
138 138 if self.all: return
139 139 if data is None:
140 140 self.dataf.seek(blockstart)
141 141 if blockstart + blocksize > self.datasize:
142 142 # the revlog may have grown since we've started running,
143 143 # but we don't have space in self.index for more entries.
144 144 # limit blocksize so that we don't get too much data.
145 145 blocksize = max(self.datasize - blockstart, 0)
146 146 data = self.dataf.read(blocksize)
147 147 lend = len(data) / self.s
148 148 i = blockstart / self.s
149 149 off = 0
150 150 for x in xrange(lend):
151 151 if self.index[i + x] == None:
152 152 b = data[off : off + self.s]
153 153 self.index[i + x] = b
154 154 n = b[self.shaoffset:self.shaoffset + 20]
155 155 self.map[n] = i + x
156 156 off += self.s
157 157
158 158 def findnode(self, node):
159 159 """search backwards through the index file for a specific node"""
160 160 if self.allmap: return None
161 161
162 162 # hg log will cause many many searches for the manifest
163 163 # nodes. After we get called a few times, just load the whole
164 164 # thing.
165 165 if self.mapfind_count > 8:
166 166 self.loadmap()
167 167 if node in self.map:
168 168 return node
169 169 return None
170 170 self.mapfind_count += 1
171 171 last = self.l - 1
172 172 while self.index[last] != None:
173 173 if last == 0:
174 174 self.all = 1
175 175 self.allmap = 1
176 176 return None
177 177 last -= 1
178 178 end = (last + 1) * self.s
179 179 blocksize = self.s * 256
180 180 while end >= 0:
181 181 start = max(end - blocksize, 0)
182 182 self.dataf.seek(start)
183 183 data = self.dataf.read(end - start)
184 184 findend = end - start
185 185 while True:
186 186 # we're searching backwards, so weh have to make sure
187 187 # we don't find a changeset where this node is a parent
188 188 off = data.rfind(node, 0, findend)
189 189 findend = off
190 190 if off >= 0:
191 191 i = off / self.s
192 192 off = i * self.s
193 193 n = data[off + self.shaoffset:off + self.shaoffset + 20]
194 194 if n == node:
195 195 self.map[n] = i + start / self.s
196 196 return node
197 197 else:
198 198 break
199 199 end -= blocksize
200 200 return None
201 201
202 202 def loadindex(self, i=None, end=None):
203 203 if self.all: return
204 204 all = False
205 205 if i == None:
206 206 blockstart = 0
207 207 blocksize = (512 / self.s) * self.s
208 208 end = self.datasize
209 209 all = True
210 210 else:
211 211 if end:
212 212 blockstart = i * self.s
213 213 end = end * self.s
214 214 blocksize = end - blockstart
215 215 else:
216 216 blockstart = (i & ~(32)) * self.s
217 217 blocksize = self.s * 64
218 218 end = blockstart + blocksize
219 219 while blockstart < end:
220 220 self.loadblock(blockstart, blocksize)
221 221 blockstart += blocksize
222 222 if all: self.all = True
223 223
224 224 class lazyindex(object):
225 225 """a lazy version of the index array"""
226 226 def __init__(self, parser):
227 227 self.p = parser
228 228 def __len__(self):
229 229 return len(self.p.index)
230 230 def load(self, pos):
231 231 if pos < 0:
232 232 pos += len(self.p.index)
233 233 self.p.loadindex(pos)
234 234 return self.p.index[pos]
235 235 def __getitem__(self, pos):
236 236 ret = self.p.index[pos] or self.load(pos)
237 237 if isinstance(ret, str):
238 238 ret = struct.unpack(self.p.indexformat, ret)
239 239 return ret
240 240 def __setitem__(self, pos, item):
241 241 self.p.index[pos] = item
242 242 def __delitem__(self, pos):
243 243 del self.p.index[pos]
244 244 def append(self, e):
245 245 self.p.index.append(e)
246 246
247 247 class lazymap(object):
248 248 """a lazy version of the node map"""
249 249 def __init__(self, parser):
250 250 self.p = parser
251 251 def load(self, key):
252 252 n = self.p.findnode(key)
253 253 if n == None:
254 254 raise KeyError(key)
255 255 def __contains__(self, key):
256 256 if key in self.p.map:
257 257 return True
258 258 self.p.loadmap()
259 259 return key in self.p.map
260 260 def __iter__(self):
261 261 yield nullid
262 262 for i in xrange(self.p.l):
263 263 ret = self.p.index[i]
264 264 if not ret:
265 265 self.p.loadindex(i)
266 266 ret = self.p.index[i]
267 267 if isinstance(ret, str):
268 268 ret = struct.unpack(self.p.indexformat, ret)
269 269 yield ret[-1]
270 270 def __getitem__(self, key):
271 271 try:
272 272 return self.p.map[key]
273 273 except KeyError:
274 274 try:
275 275 self.load(key)
276 276 return self.p.map[key]
277 277 except KeyError:
278 278 raise KeyError("node " + hex(key))
279 279 def __setitem__(self, key, val):
280 280 self.p.map[key] = val
281 281 def __delitem__(self, key):
282 282 del self.p.map[key]
283 283
284 284 class RevlogError(Exception): pass
285 285
286 286 class revlog(object):
287 287 """
288 288 the underlying revision storage object
289 289
290 290 A revlog consists of two parts, an index and the revision data.
291 291
292 292 The index is a file with a fixed record size containing
293 293 information on each revision, includings its nodeid (hash), the
294 294 nodeids of its parents, the position and offset of its data within
295 295 the data file, and the revision it's based on. Finally, each entry
296 296 contains a linkrev entry that can serve as a pointer to external
297 297 data.
298 298
299 299 The revision data itself is a linear collection of data chunks.
300 300 Each chunk represents a revision and is usually represented as a
301 301 delta against the previous chunk. To bound lookup time, runs of
302 302 deltas are limited to about 2 times the length of the original
303 303 version data. This makes retrieval of a version proportional to
304 304 its size, or O(1) relative to the number of revisions.
305 305
306 306 Both pieces of the revlog are written to in an append-only
307 307 fashion, which means we never need to rewrite a file to insert or
308 308 remove data, and can use some simple techniques to avoid the need
309 309 for locking while reading.
310 310 """
311 311 def __init__(self, opener, indexfile, datafile,
312 312 defversion=REVLOG_DEFAULT_VERSION):
313 313 """
314 314 create a revlog object
315 315
316 316 opener is a function that abstracts the file opening operation
317 317 and can be used to implement COW semantics or the like.
318 318 """
319 319 self.indexfile = indexfile
320 320 self.datafile = datafile
321 321 self.opener = opener
322 322
323 323 self.indexstat = None
324 324 self.cache = None
325 325 self.chunkcache = None
326 326 self.defversion = defversion
327 327 self.load()
328 328
329 329 def load(self):
330 330 v = self.defversion
331 331 try:
332 332 f = self.opener(self.indexfile)
333 333 i = f.read(4)
334 334 f.seek(0)
335 335 except IOError, inst:
336 336 if inst.errno != errno.ENOENT:
337 337 raise
338 338 i = ""
339 339 else:
340 340 try:
341 341 st = util.fstat(f)
342 342 except AttributeError, inst:
343 343 st = None
344 344 else:
345 345 oldst = self.indexstat
346 346 if (oldst and st.st_dev == oldst.st_dev
347 347 and st.st_ino == oldst.st_ino
348 348 and st.st_mtime == oldst.st_mtime
349 349 and st.st_ctime == oldst.st_ctime):
350 350 return
351 351 self.indexstat = st
352 352 if len(i) > 0:
353 353 v = struct.unpack(versionformat, i)[0]
354 354 flags = v & ~0xFFFF
355 355 fmt = v & 0xFFFF
356 356 if fmt == REVLOGV0:
357 357 if flags:
358 358 raise RevlogError(_("index %s invalid flags %x for format v0" %
359 359 (self.indexfile, flags)))
360 360 elif fmt == REVLOGNG:
361 361 if flags & ~REVLOGNGINLINEDATA:
362 362 raise RevlogError(_("index %s invalid flags %x for revlogng" %
363 363 (self.indexfile, flags)))
364 364 else:
365 365 raise RevlogError(_("index %s invalid format %d" %
366 366 (self.indexfile, fmt)))
367 367 self.version = v
368 368 if v == REVLOGV0:
369 369 self.indexformat = indexformatv0
370 370 shaoffset = v0shaoffset
371 371 else:
372 372 self.indexformat = indexformatng
373 373 shaoffset = ngshaoffset
374 374
375 375 if i:
376 376 if (lazyparser.safe_to_use and not self.inlinedata() and
377 377 st and st.st_size > 10000):
378 378 # big index, let's parse it on demand
379 379 parser = lazyparser(f, st.st_size, self.indexformat, shaoffset)
380 380 self.index = lazyindex(parser)
381 381 self.nodemap = lazymap(parser)
382 382 else:
383 383 self.parseindex(f, st)
384 384 if self.version != REVLOGV0:
385 385 e = list(self.index[0])
386 386 type = self.ngtype(e[0])
387 387 e[0] = self.offset_type(0, type)
388 388 self.index[0] = e
389 389 else:
390 390 self.nodemap = { nullid: -1}
391 391 self.index = []
392 392
393 393
394 394 def parseindex(self, fp, st):
395 395 s = struct.calcsize(self.indexformat)
396 396 self.index = []
397 397 self.nodemap = {nullid: -1}
398 398 inline = self.inlinedata()
399 399 n = 0
400 400 leftover = None
401 401 while True:
402 402 if st:
403 403 data = fp.read(65536)
404 404 else:
405 405 # hack for httprangereader, it doesn't do partial reads well
406 406 data = fp.read()
407 407 if not data:
408 408 break
409 409 if n == 0 and self.inlinedata():
410 410 # cache the first chunk
411 411 self.chunkcache = (0, data)
412 412 if leftover:
413 413 data = leftover + data
414 414 leftover = None
415 415 off = 0
416 416 l = len(data)
417 417 while off < l:
418 418 if l - off < s:
419 419 leftover = data[off:]
420 420 break
421 421 cur = data[off:off + s]
422 422 off += s
423 423 e = struct.unpack(self.indexformat, cur)
424 424 self.index.append(e)
425 425 self.nodemap[e[-1]] = n
426 426 n += 1
427 427 if inline:
428 428 off += e[1]
429 429 if off > l:
430 430 # some things don't seek well, just read it
431 431 fp.read(off - l)
432 432 if not st:
433 433 break
434 434
435 435
436 436 def ngoffset(self, q):
437 437 if q & 0xFFFF:
438 438 raise RevlogError(_('%s: incompatible revision flag %x') %
439 439 (self.indexfile, q))
440 440 return long(q >> 16)
441 441
442 442 def ngtype(self, q):
443 443 return int(q & 0xFFFF)
444 444
445 445 def offset_type(self, offset, type):
446 446 return long(long(offset) << 16 | type)
447 447
448 448 def loadindex(self, start, end):
449 449 """load a block of indexes all at once from the lazy parser"""
450 450 if isinstance(self.index, lazyindex):
451 451 self.index.p.loadindex(start, end)
452 452
453 453 def loadindexmap(self):
454 454 """loads both the map and the index from the lazy parser"""
455 455 if isinstance(self.index, lazyindex):
456 456 p = self.index.p
457 457 p.loadindex()
458 458 self.nodemap = p.map
459 459
460 460 def loadmap(self):
461 461 """loads the map from the lazy parser"""
462 462 if isinstance(self.nodemap, lazymap):
463 463 self.nodemap.p.loadmap()
464 464 self.nodemap = self.nodemap.p.map
465 465
466 466 def inlinedata(self): return self.version & REVLOGNGINLINEDATA
467 467 def tip(self): return self.node(len(self.index) - 1)
468 468 def count(self): return len(self.index)
469 469 def node(self, rev):
470 470 return (rev < 0) and nullid or self.index[rev][-1]
471 471 def rev(self, node):
472 472 try:
473 473 return self.nodemap[node]
474 474 except KeyError:
475 475 raise RevlogError(_('%s: no node %s') % (self.indexfile, hex(node)))
476 476 def linkrev(self, node):
477 477 return (node == nullid) and -1 or self.index[self.rev(node)][-4]
478 478 def parents(self, node):
479 479 if node == nullid: return (nullid, nullid)
480 480 r = self.rev(node)
481 481 d = self.index[r][-3:-1]
482 482 if self.version == REVLOGV0:
483 483 return d
484 484 return [ self.node(x) for x in d ]
485 485 def parentrevs(self, rev):
486 486 if rev == -1:
487 487 return (-1, -1)
488 488 d = self.index[rev][-3:-1]
489 489 if self.version == REVLOGV0:
490 490 return [ self.rev(x) for x in d ]
491 491 return d
492 492 def start(self, rev):
493 493 if rev < 0:
494 494 return -1
495 495 if self.version != REVLOGV0:
496 496 return self.ngoffset(self.index[rev][0])
497 497 return self.index[rev][0]
498 498
499 499 def end(self, rev): return self.start(rev) + self.length(rev)
500 500
501 501 def size(self, rev):
502 502 """return the length of the uncompressed text for a given revision"""
503 503 l = -1
504 504 if self.version != REVLOGV0:
505 505 l = self.index[rev][2]
506 506 if l >= 0:
507 507 return l
508 508
509 509 t = self.revision(self.node(rev))
510 510 return len(t)
511 511
512 512 # alternate implementation, The advantage to this code is it
513 513 # will be faster for a single revision. But, the results are not
514 514 # cached, so finding the size of every revision will be slower.
515 515 """
516 516 if self.cache and self.cache[1] == rev:
517 517 return len(self.cache[2])
518 518
519 519 base = self.base(rev)
520 520 if self.cache and self.cache[1] >= base and self.cache[1] < rev:
521 521 base = self.cache[1]
522 522 text = self.cache[2]
523 523 else:
524 524 text = self.revision(self.node(base))
525 525
526 526 l = len(text)
527 527 for x in xrange(base + 1, rev + 1):
528 528 l = mdiff.patchedsize(l, self.chunk(x))
529 529 return l
530 530 """
531 531
532 532 def length(self, rev):
533 533 if rev < 0:
534 534 return 0
535 535 else:
536 536 return self.index[rev][1]
537 537 def base(self, rev): return (rev < 0) and rev or self.index[rev][-5]
538 538
539 539 def reachable(self, rev, stop=None):
540 540 reachable = {}
541 541 visit = [rev]
542 542 reachable[rev] = 1
543 543 if stop:
544 544 stopn = self.rev(stop)
545 545 else:
546 546 stopn = 0
547 547 while visit:
548 548 n = visit.pop(0)
549 549 if n == stop:
550 550 continue
551 551 if n == nullid:
552 552 continue
553 553 for p in self.parents(n):
554 554 if self.rev(p) < stopn:
555 555 continue
556 556 if p not in reachable:
557 557 reachable[p] = 1
558 558 visit.append(p)
559 559 return reachable
560 560
561 561 def nodesbetween(self, roots=None, heads=None):
562 562 """Return a tuple containing three elements. Elements 1 and 2 contain
563 563 a final list bases and heads after all the unreachable ones have been
564 564 pruned. Element 0 contains a topologically sorted list of all
565 565
566 566 nodes that satisfy these constraints:
567 567 1. All nodes must be descended from a node in roots (the nodes on
568 568 roots are considered descended from themselves).
569 569 2. All nodes must also be ancestors of a node in heads (the nodes in
570 570 heads are considered to be their own ancestors).
571 571
572 572 If roots is unspecified, nullid is assumed as the only root.
573 573 If heads is unspecified, it is taken to be the output of the
574 574 heads method (i.e. a list of all nodes in the repository that
575 575 have no children)."""
576 576 nonodes = ([], [], [])
577 577 if roots is not None:
578 578 roots = list(roots)
579 579 if not roots:
580 580 return nonodes
581 581 lowestrev = min([self.rev(n) for n in roots])
582 582 else:
583 583 roots = [nullid] # Everybody's a descendent of nullid
584 584 lowestrev = -1
585 585 if (lowestrev == -1) and (heads is None):
586 586 # We want _all_ the nodes!
587 587 return ([self.node(r) for r in xrange(0, self.count())],
588 588 [nullid], list(self.heads()))
589 589 if heads is None:
590 590 # All nodes are ancestors, so the latest ancestor is the last
591 591 # node.
592 592 highestrev = self.count() - 1
593 593 # Set ancestors to None to signal that every node is an ancestor.
594 594 ancestors = None
595 595 # Set heads to an empty dictionary for later discovery of heads
596 596 heads = {}
597 597 else:
598 598 heads = list(heads)
599 599 if not heads:
600 600 return nonodes
601 601 ancestors = {}
602 602 # Turn heads into a dictionary so we can remove 'fake' heads.
603 603 # Also, later we will be using it to filter out the heads we can't
604 604 # find from roots.
605 605 heads = dict.fromkeys(heads, 0)
606 606 # Start at the top and keep marking parents until we're done.
607 607 nodestotag = heads.keys()
608 608 # Remember where the top was so we can use it as a limit later.
609 609 highestrev = max([self.rev(n) for n in nodestotag])
610 610 while nodestotag:
611 611 # grab a node to tag
612 612 n = nodestotag.pop()
613 613 # Never tag nullid
614 614 if n == nullid:
615 615 continue
616 616 # A node's revision number represents its place in a
617 617 # topologically sorted list of nodes.
618 618 r = self.rev(n)
619 619 if r >= lowestrev:
620 620 if n not in ancestors:
621 621 # If we are possibly a descendent of one of the roots
622 622 # and we haven't already been marked as an ancestor
623 623 ancestors[n] = 1 # Mark as ancestor
624 624 # Add non-nullid parents to list of nodes to tag.
625 625 nodestotag.extend([p for p in self.parents(n) if
626 626 p != nullid])
627 627 elif n in heads: # We've seen it before, is it a fake head?
628 628 # So it is, real heads should not be the ancestors of
629 629 # any other heads.
630 630 heads.pop(n)
631 631 if not ancestors:
632 632 return nonodes
633 633 # Now that we have our set of ancestors, we want to remove any
634 634 # roots that are not ancestors.
635 635
636 636 # If one of the roots was nullid, everything is included anyway.
637 637 if lowestrev > -1:
638 638 # But, since we weren't, let's recompute the lowest rev to not
639 639 # include roots that aren't ancestors.
640 640
641 641 # Filter out roots that aren't ancestors of heads
642 642 roots = [n for n in roots if n in ancestors]
643 643 # Recompute the lowest revision
644 644 if roots:
645 645 lowestrev = min([self.rev(n) for n in roots])
646 646 else:
647 647 # No more roots? Return empty list
648 648 return nonodes
649 649 else:
650 650 # We are descending from nullid, and don't need to care about
651 651 # any other roots.
652 652 lowestrev = -1
653 653 roots = [nullid]
654 654 # Transform our roots list into a 'set' (i.e. a dictionary where the
655 655 # values don't matter.
656 656 descendents = dict.fromkeys(roots, 1)
657 657 # Also, keep the original roots so we can filter out roots that aren't
658 658 # 'real' roots (i.e. are descended from other roots).
659 659 roots = descendents.copy()
660 660 # Our topologically sorted list of output nodes.
661 661 orderedout = []
662 662 # Don't start at nullid since we don't want nullid in our output list,
663 663 # and if nullid shows up in descedents, empty parents will look like
664 664 # they're descendents.
665 665 for r in xrange(max(lowestrev, 0), highestrev + 1):
666 666 n = self.node(r)
667 667 isdescendent = False
668 668 if lowestrev == -1: # Everybody is a descendent of nullid
669 669 isdescendent = True
670 670 elif n in descendents:
671 671 # n is already a descendent
672 672 isdescendent = True
673 673 # This check only needs to be done here because all the roots
674 674 # will start being marked is descendents before the loop.
675 675 if n in roots:
676 676 # If n was a root, check if it's a 'real' root.
677 677 p = tuple(self.parents(n))
678 678 # If any of its parents are descendents, it's not a root.
679 679 if (p[0] in descendents) or (p[1] in descendents):
680 680 roots.pop(n)
681 681 else:
682 682 p = tuple(self.parents(n))
683 683 # A node is a descendent if either of its parents are
684 684 # descendents. (We seeded the dependents list with the roots
685 685 # up there, remember?)
686 686 if (p[0] in descendents) or (p[1] in descendents):
687 687 descendents[n] = 1
688 688 isdescendent = True
689 689 if isdescendent and ((ancestors is None) or (n in ancestors)):
690 690 # Only include nodes that are both descendents and ancestors.
691 691 orderedout.append(n)
692 692 if (ancestors is not None) and (n in heads):
693 693 # We're trying to figure out which heads are reachable
694 694 # from roots.
695 695 # Mark this head as having been reached
696 696 heads[n] = 1
697 697 elif ancestors is None:
698 698 # Otherwise, we're trying to discover the heads.
699 699 # Assume this is a head because if it isn't, the next step
700 700 # will eventually remove it.
701 701 heads[n] = 1
702 702 # But, obviously its parents aren't.
703 703 for p in self.parents(n):
704 704 heads.pop(p, None)
705 705 heads = [n for n in heads.iterkeys() if heads[n] != 0]
706 706 roots = roots.keys()
707 707 assert orderedout
708 708 assert roots
709 709 assert heads
710 710 return (orderedout, roots, heads)
711 711
712 712 def heads(self, start=None):
713 713 """return the list of all nodes that have no children
714 714
715 715 if start is specified, only heads that are descendants of
716 716 start will be returned
717 717
718 718 """
719 719 if start is None:
720 720 start = nullid
721 721 startrev = self.rev(start)
722 722 reachable = {startrev: 1}
723 723 heads = {startrev: 1}
724 724
725 725 parentrevs = self.parentrevs
726 726 for r in xrange(startrev + 1, self.count()):
727 727 for p in parentrevs(r):
728 728 if p in reachable:
729 729 reachable[r] = 1
730 730 heads[r] = 1
731 731 if p in heads:
732 732 del heads[p]
733 733 return [self.node(r) for r in heads]
734 734
735 735 def children(self, node):
736 736 """find the children of a given node"""
737 737 c = []
738 738 p = self.rev(node)
739 739 for r in range(p + 1, self.count()):
740 n = self.node(r)
741 for pn in self.parents(n):
742 if pn == node:
743 c.append(n)
744 continue
745 elif pn == nullid:
746 continue
740 for pr in self.parentrevs(n):
741 if pr == p:
742 c.append(self.node(r))
747 743 return c
748 744
749 745 def lookup(self, id):
750 746 """locate a node based on:
751 747 - revision number or str(revision number)
752 748 - nodeid or subset of hex nodeid
753 749 """
754 750 if isinstance(id, (long, int)):
755 751 # rev
756 752 return self.node(id)
757 753 if len(id) == 20:
758 754 # possibly a binary node
759 755 # odds of a binary node being all hex in ASCII are 1 in 10**25
760 756 try:
761 757 node = id
762 758 r = self.rev(node) # quick search the index
763 759 return node
764 760 except RevlogError:
765 761 pass # may be partial hex id
766 762 try:
767 763 # str(rev)
768 764 rev = int(id)
769 765 if str(rev) != id: raise ValueError
770 766 if rev < 0: rev = self.count() + rev
771 767 if rev < 0 or rev >= self.count(): raise ValueError
772 768 return self.node(rev)
773 769 except (ValueError, OverflowError):
774 770 pass
775 771 try:
776 772 if len(id) == 40:
777 773 # a full hex nodeid?
778 774 node = bin(id)
779 775 r = self.rev(node)
780 776 return node
781 777 elif len(id) < 40:
782 778 # hex(node)[:...]
783 779 bin_id = bin(id[:len(id) & ~1]) # grab an even number of digits
784 780 node = None
785 781 for n in self.nodemap:
786 782 if n.startswith(bin_id) and hex(n).startswith(id):
787 783 if node is not None:
788 784 raise RevlogError(_("Ambiguous identifier"))
789 785 node = n
790 786 if node is not None:
791 787 return node
792 788 except TypeError:
793 789 pass
794 790
795 791 raise RevlogError(_("No match found"))
796 792
797 793 def cmp(self, node, text):
798 794 """compare text with a given file revision"""
799 795 p1, p2 = self.parents(node)
800 796 return hash(text, p1, p2) != node
801 797
802 798 def makenode(self, node, text):
803 799 """calculate a file nodeid for text, descended or possibly
804 800 unchanged from node"""
805 801
806 802 if self.cmp(node, text):
807 803 return hash(text, node, nullid)
808 804 return node
809 805
810 806 def diff(self, a, b):
811 807 """return a delta between two revisions"""
812 808 return mdiff.textdiff(a, b)
813 809
814 810 def patches(self, t, pl):
815 811 """apply a list of patches to a string"""
816 812 return mdiff.patches(t, pl)
817 813
818 814 def chunk(self, rev, df=None, cachelen=4096):
819 815 start, length = self.start(rev), self.length(rev)
820 816 inline = self.inlinedata()
821 817 if inline:
822 818 start += (rev + 1) * struct.calcsize(self.indexformat)
823 819 end = start + length
824 820 def loadcache(df):
825 821 cache_length = max(cachelen, length) # 4k
826 822 if not df:
827 823 if inline:
828 824 df = self.opener(self.indexfile)
829 825 else:
830 826 df = self.opener(self.datafile)
831 827 df.seek(start)
832 828 self.chunkcache = (start, df.read(cache_length))
833 829
834 830 if not self.chunkcache:
835 831 loadcache(df)
836 832
837 833 cache_start = self.chunkcache[0]
838 834 cache_end = cache_start + len(self.chunkcache[1])
839 835 if start >= cache_start and end <= cache_end:
840 836 # it is cached
841 837 offset = start - cache_start
842 838 else:
843 839 loadcache(df)
844 840 offset = 0
845 841
846 842 #def checkchunk():
847 843 # df = self.opener(self.datafile)
848 844 # df.seek(start)
849 845 # return df.read(length)
850 846 #assert s == checkchunk()
851 847 return decompress(self.chunkcache[1][offset:offset + length])
852 848
853 849 def delta(self, node):
854 850 """return or calculate a delta between a node and its predecessor"""
855 851 r = self.rev(node)
856 852 return self.revdiff(r - 1, r)
857 853
858 854 def revdiff(self, rev1, rev2):
859 855 """return or calculate a delta between two revisions"""
860 856 b1 = self.base(rev1)
861 857 b2 = self.base(rev2)
862 858 if b1 == b2 and rev1 + 1 == rev2:
863 859 return self.chunk(rev2)
864 860 else:
865 861 return self.diff(self.revision(self.node(rev1)),
866 862 self.revision(self.node(rev2)))
867 863
868 864 def revision(self, node):
869 865 """return an uncompressed revision of a given"""
870 866 if node == nullid: return ""
871 867 if self.cache and self.cache[0] == node: return self.cache[2]
872 868
873 869 # look up what we need to read
874 870 text = None
875 871 rev = self.rev(node)
876 872 base = self.base(rev)
877 873
878 874 if self.inlinedata():
879 875 # we probably have the whole chunk cached
880 876 df = None
881 877 else:
882 878 df = self.opener(self.datafile)
883 879
884 880 # do we have useful data cached?
885 881 if self.cache and self.cache[1] >= base and self.cache[1] < rev:
886 882 base = self.cache[1]
887 883 text = self.cache[2]
888 884 self.loadindex(base, rev + 1)
889 885 else:
890 886 self.loadindex(base, rev + 1)
891 887 text = self.chunk(base, df=df)
892 888
893 889 bins = []
894 890 for r in xrange(base + 1, rev + 1):
895 891 bins.append(self.chunk(r, df=df))
896 892
897 893 text = self.patches(text, bins)
898 894
899 895 p1, p2 = self.parents(node)
900 896 if node != hash(text, p1, p2):
901 897 raise RevlogError(_("integrity check failed on %s:%d")
902 898 % (self.datafile, rev))
903 899
904 900 self.cache = (node, rev, text)
905 901 return text
906 902
907 903 def checkinlinesize(self, tr, fp=None):
908 904 if not self.inlinedata():
909 905 return
910 906 if not fp:
911 907 fp = self.opener(self.indexfile, 'r')
912 908 fp.seek(0, 2)
913 909 size = fp.tell()
914 910 if size < 131072:
915 911 return
916 912 trinfo = tr.find(self.indexfile)
917 913 if trinfo == None:
918 914 raise RevlogError(_("%s not found in the transaction" %
919 915 self.indexfile))
920 916
921 917 trindex = trinfo[2]
922 918 dataoff = self.start(trindex)
923 919
924 920 tr.add(self.datafile, dataoff)
925 921 df = self.opener(self.datafile, 'w')
926 922 calc = struct.calcsize(self.indexformat)
927 923 for r in xrange(self.count()):
928 924 start = self.start(r) + (r + 1) * calc
929 925 length = self.length(r)
930 926 fp.seek(start)
931 927 d = fp.read(length)
932 928 df.write(d)
933 929 fp.close()
934 930 df.close()
935 931 fp = self.opener(self.indexfile, 'w', atomictemp=True)
936 932 self.version &= ~(REVLOGNGINLINEDATA)
937 933 if self.count():
938 934 x = self.index[0]
939 935 e = struct.pack(self.indexformat, *x)[4:]
940 936 l = struct.pack(versionformat, self.version)
941 937 fp.write(l)
942 938 fp.write(e)
943 939
944 940 for i in xrange(1, self.count()):
945 941 x = self.index[i]
946 942 e = struct.pack(self.indexformat, *x)
947 943 fp.write(e)
948 944
949 945 # if we don't call rename, the temp file will never replace the
950 946 # real index
951 947 fp.rename()
952 948
953 949 tr.replace(self.indexfile, trindex * calc)
954 950 self.chunkcache = None
955 951
956 952 def addrevision(self, text, transaction, link, p1=None, p2=None, d=None):
957 953 """add a revision to the log
958 954
959 955 text - the revision data to add
960 956 transaction - the transaction object used for rollback
961 957 link - the linkrev data to add
962 958 p1, p2 - the parent nodeids of the revision
963 959 d - an optional precomputed delta
964 960 """
965 961 if not self.inlinedata():
966 962 dfh = self.opener(self.datafile, "a")
967 963 else:
968 964 dfh = None
969 965 ifh = self.opener(self.indexfile, "a+")
970 966 return self._addrevision(text, transaction, link, p1, p2, d, ifh, dfh)
971 967
972 968 def _addrevision(self, text, transaction, link, p1, p2, d, ifh, dfh):
973 969 if text is None: text = ""
974 970 if p1 is None: p1 = self.tip()
975 971 if p2 is None: p2 = nullid
976 972
977 973 node = hash(text, p1, p2)
978 974
979 975 if node in self.nodemap:
980 976 return node
981 977
982 978 n = self.count()
983 979 t = n - 1
984 980
985 981 if n:
986 982 base = self.base(t)
987 983 start = self.start(base)
988 984 end = self.end(t)
989 985 if not d:
990 986 prev = self.revision(self.tip())
991 987 d = self.diff(prev, text)
992 988 data = compress(d)
993 989 l = len(data[1]) + len(data[0])
994 990 dist = end - start + l
995 991
996 992 # full versions are inserted when the needed deltas
997 993 # become comparable to the uncompressed text
998 994 if not n or dist > len(text) * 2:
999 995 data = compress(text)
1000 996 l = len(data[1]) + len(data[0])
1001 997 base = n
1002 998 else:
1003 999 base = self.base(t)
1004 1000
1005 1001 offset = 0
1006 1002 if t >= 0:
1007 1003 offset = self.end(t)
1008 1004
1009 1005 if self.version == REVLOGV0:
1010 1006 e = (offset, l, base, link, p1, p2, node)
1011 1007 else:
1012 1008 e = (self.offset_type(offset, 0), l, len(text),
1013 1009 base, link, self.rev(p1), self.rev(p2), node)
1014 1010
1015 1011 self.index.append(e)
1016 1012 self.nodemap[node] = n
1017 1013 entry = struct.pack(self.indexformat, *e)
1018 1014
1019 1015 if not self.inlinedata():
1020 1016 transaction.add(self.datafile, offset)
1021 1017 transaction.add(self.indexfile, n * len(entry))
1022 1018 if data[0]:
1023 1019 dfh.write(data[0])
1024 1020 dfh.write(data[1])
1025 1021 dfh.flush()
1026 1022 else:
1027 1023 ifh.seek(0, 2)
1028 1024 transaction.add(self.indexfile, ifh.tell(), self.count() - 1)
1029 1025
1030 1026 if len(self.index) == 1 and self.version != REVLOGV0:
1031 1027 l = struct.pack(versionformat, self.version)
1032 1028 ifh.write(l)
1033 1029 entry = entry[4:]
1034 1030
1035 1031 ifh.write(entry)
1036 1032
1037 1033 if self.inlinedata():
1038 1034 ifh.write(data[0])
1039 1035 ifh.write(data[1])
1040 1036 self.checkinlinesize(transaction, ifh)
1041 1037
1042 1038 self.cache = (node, n, text)
1043 1039 return node
1044 1040
1045 1041 def ancestor(self, a, b):
1046 1042 """calculate the least common ancestor of nodes a and b"""
1047 1043
1048 1044 def parents(rev):
1049 1045 return [p for p in self.parentrevs(rev) if p != -1]
1050 1046
1051 1047 c = ancestor.ancestor(self.rev(a), self.rev(b), parents)
1052 1048 if c is None:
1053 1049 return nullid
1054 1050
1055 1051 return self.node(c)
1056 1052
1057 1053 def group(self, nodelist, lookup, infocollect=None):
1058 1054 """calculate a delta group
1059 1055
1060 1056 Given a list of changeset revs, return a set of deltas and
1061 1057 metadata corresponding to nodes. the first delta is
1062 1058 parent(nodes[0]) -> nodes[0] the receiver is guaranteed to
1063 1059 have this parent as it has all history before these
1064 1060 changesets. parent is parent[0]
1065 1061 """
1066 1062 revs = [self.rev(n) for n in nodelist]
1067 1063
1068 1064 # if we don't have any revisions touched by these changesets, bail
1069 1065 if not revs:
1070 1066 yield changegroup.closechunk()
1071 1067 return
1072 1068
1073 1069 # add the parent of the first rev
1074 1070 p = self.parents(self.node(revs[0]))[0]
1075 1071 revs.insert(0, self.rev(p))
1076 1072
1077 1073 # build deltas
1078 1074 for d in xrange(0, len(revs) - 1):
1079 1075 a, b = revs[d], revs[d + 1]
1080 1076 nb = self.node(b)
1081 1077
1082 1078 if infocollect is not None:
1083 1079 infocollect(nb)
1084 1080
1085 1081 d = self.revdiff(a, b)
1086 1082 p = self.parents(nb)
1087 1083 meta = nb + p[0] + p[1] + lookup(nb)
1088 1084 yield changegroup.genchunk("%s%s" % (meta, d))
1089 1085
1090 1086 yield changegroup.closechunk()
1091 1087
1092 1088 def addgroup(self, revs, linkmapper, transaction, unique=0):
1093 1089 """
1094 1090 add a delta group
1095 1091
1096 1092 given a set of deltas, add them to the revision log. the
1097 1093 first delta is against its parent, which should be in our
1098 1094 log, the rest are against the previous delta.
1099 1095 """
1100 1096
1101 1097 #track the base of the current delta log
1102 1098 r = self.count()
1103 1099 t = r - 1
1104 1100 node = None
1105 1101
1106 1102 base = prev = -1
1107 1103 start = end = textlen = 0
1108 1104 if r:
1109 1105 end = self.end(t)
1110 1106
1111 1107 ifh = self.opener(self.indexfile, "a+")
1112 1108 ifh.seek(0, 2)
1113 1109 transaction.add(self.indexfile, ifh.tell(), self.count())
1114 1110 if self.inlinedata():
1115 1111 dfh = None
1116 1112 else:
1117 1113 transaction.add(self.datafile, end)
1118 1114 dfh = self.opener(self.datafile, "a")
1119 1115
1120 1116 # loop through our set of deltas
1121 1117 chain = None
1122 1118 for chunk in revs:
1123 1119 node, p1, p2, cs = struct.unpack("20s20s20s20s", chunk[:80])
1124 1120 link = linkmapper(cs)
1125 1121 if node in self.nodemap:
1126 1122 # this can happen if two branches make the same change
1127 1123 # if unique:
1128 1124 # raise RevlogError(_("already have %s") % hex(node[:4]))
1129 1125 chain = node
1130 1126 continue
1131 1127 delta = chunk[80:]
1132 1128
1133 1129 for p in (p1, p2):
1134 1130 if not p in self.nodemap:
1135 1131 raise RevlogError(_("unknown parent %s") % short(p))
1136 1132
1137 1133 if not chain:
1138 1134 # retrieve the parent revision of the delta chain
1139 1135 chain = p1
1140 1136 if not chain in self.nodemap:
1141 1137 raise RevlogError(_("unknown base %s") % short(chain[:4]))
1142 1138
1143 1139 # full versions are inserted when the needed deltas become
1144 1140 # comparable to the uncompressed text or when the previous
1145 1141 # version is not the one we have a delta against. We use
1146 1142 # the size of the previous full rev as a proxy for the
1147 1143 # current size.
1148 1144
1149 1145 if chain == prev:
1150 1146 tempd = compress(delta)
1151 1147 cdelta = tempd[0] + tempd[1]
1152 1148 textlen = mdiff.patchedsize(textlen, delta)
1153 1149
1154 1150 if chain != prev or (end - start + len(cdelta)) > textlen * 2:
1155 1151 # flush our writes here so we can read it in revision
1156 1152 if dfh:
1157 1153 dfh.flush()
1158 1154 ifh.flush()
1159 1155 text = self.revision(chain)
1160 1156 text = self.patches(text, [delta])
1161 1157 chk = self._addrevision(text, transaction, link, p1, p2, None,
1162 1158 ifh, dfh)
1163 1159 if not dfh and not self.inlinedata():
1164 1160 # addrevision switched from inline to conventional
1165 1161 # reopen the index
1166 1162 dfh = self.opener(self.datafile, "a")
1167 1163 ifh = self.opener(self.indexfile, "a")
1168 1164 if chk != node:
1169 1165 raise RevlogError(_("consistency error adding group"))
1170 1166 textlen = len(text)
1171 1167 else:
1172 1168 if self.version == REVLOGV0:
1173 1169 e = (end, len(cdelta), base, link, p1, p2, node)
1174 1170 else:
1175 1171 e = (self.offset_type(end, 0), len(cdelta), textlen, base,
1176 1172 link, self.rev(p1), self.rev(p2), node)
1177 1173 self.index.append(e)
1178 1174 self.nodemap[node] = r
1179 1175 if self.inlinedata():
1180 1176 ifh.write(struct.pack(self.indexformat, *e))
1181 1177 ifh.write(cdelta)
1182 1178 self.checkinlinesize(transaction, ifh)
1183 1179 if not self.inlinedata():
1184 1180 dfh = self.opener(self.datafile, "a")
1185 1181 ifh = self.opener(self.indexfile, "a")
1186 1182 else:
1187 1183 dfh.write(cdelta)
1188 1184 ifh.write(struct.pack(self.indexformat, *e))
1189 1185
1190 1186 t, r, chain, prev = r, r + 1, node, node
1191 1187 base = self.base(t)
1192 1188 start = self.start(base)
1193 1189 end = self.end(t)
1194 1190
1195 1191 return node
1196 1192
1197 1193 def strip(self, rev, minlink):
1198 1194 if self.count() == 0 or rev >= self.count():
1199 1195 return
1200 1196
1201 1197 if isinstance(self.index, lazyindex):
1202 1198 self.loadindexmap()
1203 1199
1204 1200 # When stripping away a revision, we need to make sure it
1205 1201 # does not actually belong to an older changeset.
1206 1202 # The minlink parameter defines the oldest revision
1207 1203 # we're allowed to strip away.
1208 1204 while minlink > self.index[rev][-4]:
1209 1205 rev += 1
1210 1206 if rev >= self.count():
1211 1207 return
1212 1208
1213 1209 # first truncate the files on disk
1214 1210 end = self.start(rev)
1215 1211 if not self.inlinedata():
1216 1212 df = self.opener(self.datafile, "a")
1217 1213 df.truncate(end)
1218 1214 end = rev * struct.calcsize(self.indexformat)
1219 1215 else:
1220 1216 end += rev * struct.calcsize(self.indexformat)
1221 1217
1222 1218 indexf = self.opener(self.indexfile, "a")
1223 1219 indexf.truncate(end)
1224 1220
1225 1221 # then reset internal state in memory to forget those revisions
1226 1222 self.cache = None
1227 1223 self.chunkcache = None
1228 1224 for x in xrange(rev, self.count()):
1229 1225 del self.nodemap[self.node(x)]
1230 1226
1231 1227 del self.index[rev:]
1232 1228
1233 1229 def checksize(self):
1234 1230 expected = 0
1235 1231 if self.count():
1236 1232 expected = self.end(self.count() - 1)
1237 1233
1238 1234 try:
1239 1235 f = self.opener(self.datafile)
1240 1236 f.seek(0, 2)
1241 1237 actual = f.tell()
1242 1238 dd = actual - expected
1243 1239 except IOError, inst:
1244 1240 if inst.errno != errno.ENOENT:
1245 1241 raise
1246 1242 dd = 0
1247 1243
1248 1244 try:
1249 1245 f = self.opener(self.indexfile)
1250 1246 f.seek(0, 2)
1251 1247 actual = f.tell()
1252 1248 s = struct.calcsize(self.indexformat)
1253 1249 i = actual / s
1254 1250 di = actual - (i * s)
1255 1251 if self.inlinedata():
1256 1252 databytes = 0
1257 1253 for r in xrange(self.count()):
1258 1254 databytes += self.length(r)
1259 1255 dd = 0
1260 1256 di = actual - self.count() * s - databytes
1261 1257 except IOError, inst:
1262 1258 if inst.errno != errno.ENOENT:
1263 1259 raise
1264 1260 di = 0
1265 1261
1266 1262 return (dd, di)
1267 1263
1268 1264
General Comments 0
You need to be logged in to leave comments. Login now