##// END OF EJS Templates
revlog.lookup tweaks...
Matt Mackall -
r3438:b17f9d3e default
parent child Browse files
Show More
@@ -1,1261 +1,1268 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 740 n = self.node(r)
741 741 for pn in self.parents(n):
742 742 if pn == node:
743 743 c.append(n)
744 744 continue
745 745 elif pn == nullid:
746 746 continue
747 747 return c
748 748
749 749 def lookup(self, id):
750 750 """locate a node based on:
751 751 - revision number or str(revision number)
752 752 - nodeid or subset of hex nodeid
753 753 """
754 754 if isinstance(id, (long, int)):
755 755 # rev
756 756 return self.node(id)
757 if len(id) == 20:
758 # possibly a binary node
759 # odds of a binary node being all hex in ASCII are 1 in 10**25
760 try:
761 node = id
762 r = self.rev(node) # quick search the index
763 return node
764 except RevlogError:
765 pass # may be partial hex id
757 766 try:
758 767 # str(rev)
759 768 rev = int(id)
760 769 if str(rev) != id: raise ValueError
761 770 if rev < 0: rev = self.count() + rev
762 771 if rev < 0 or rev >= self.count(): raise ValueError
763 772 return self.node(rev)
764 773 except (ValueError, OverflowError):
765 774 pass
766 775 try:
767 # hex(node)[:...]
768 if len(id) % 2 == 0:
769 bin_id = bin(id)
770 else:
771 bin_id = bin(id[:-1])
772 node = None
773 for n in self.nodemap:
774 if n.startswith(bin_id) and hex(n).startswith(id):
775 if node is not None:
776 raise RevlogError(_("Ambiguous identifier"))
777 node = n
778 if node is not None:
776 if len(id) == 40:
777 # a full hex nodeid?
778 node = bin(id)
779 r = self.rev(node)
779 780 return node
781 elif len(id) < 40:
782 # hex(node)[:...]
783 bin_id = bin(id[:len(id) & ~1]) # grab an even number of digits
784 node = None
785 for n in self.nodemap:
786 if n.startswith(bin_id) and hex(n).startswith(id):
787 if node is not None:
788 raise RevlogError(_("Ambiguous identifier"))
789 node = n
790 if node is not None:
791 return node
780 792 except TypeError:
781 793 pass
782 794
783 # might need fixing if we change hash lengths
784 if len(id) == 20 and id in self.nodemap:
785 # node
786 return id
787
788 795 raise RevlogError(_("No match found"))
789 796
790 797 def cmp(self, node, text):
791 798 """compare text with a given file revision"""
792 799 p1, p2 = self.parents(node)
793 800 return hash(text, p1, p2) != node
794 801
795 802 def makenode(self, node, text):
796 803 """calculate a file nodeid for text, descended or possibly
797 804 unchanged from node"""
798 805
799 806 if self.cmp(node, text):
800 807 return hash(text, node, nullid)
801 808 return node
802 809
803 810 def diff(self, a, b):
804 811 """return a delta between two revisions"""
805 812 return mdiff.textdiff(a, b)
806 813
807 814 def patches(self, t, pl):
808 815 """apply a list of patches to a string"""
809 816 return mdiff.patches(t, pl)
810 817
811 818 def chunk(self, rev, df=None, cachelen=4096):
812 819 start, length = self.start(rev), self.length(rev)
813 820 inline = self.inlinedata()
814 821 if inline:
815 822 start += (rev + 1) * struct.calcsize(self.indexformat)
816 823 end = start + length
817 824 def loadcache(df):
818 825 cache_length = max(cachelen, length) # 4k
819 826 if not df:
820 827 if inline:
821 828 df = self.opener(self.indexfile)
822 829 else:
823 830 df = self.opener(self.datafile)
824 831 df.seek(start)
825 832 self.chunkcache = (start, df.read(cache_length))
826 833
827 834 if not self.chunkcache:
828 835 loadcache(df)
829 836
830 837 cache_start = self.chunkcache[0]
831 838 cache_end = cache_start + len(self.chunkcache[1])
832 839 if start >= cache_start and end <= cache_end:
833 840 # it is cached
834 841 offset = start - cache_start
835 842 else:
836 843 loadcache(df)
837 844 offset = 0
838 845
839 846 #def checkchunk():
840 847 # df = self.opener(self.datafile)
841 848 # df.seek(start)
842 849 # return df.read(length)
843 850 #assert s == checkchunk()
844 851 return decompress(self.chunkcache[1][offset:offset + length])
845 852
846 853 def delta(self, node):
847 854 """return or calculate a delta between a node and its predecessor"""
848 855 r = self.rev(node)
849 856 return self.revdiff(r - 1, r)
850 857
851 858 def revdiff(self, rev1, rev2):
852 859 """return or calculate a delta between two revisions"""
853 860 b1 = self.base(rev1)
854 861 b2 = self.base(rev2)
855 862 if b1 == b2 and rev1 + 1 == rev2:
856 863 return self.chunk(rev2)
857 864 else:
858 865 return self.diff(self.revision(self.node(rev1)),
859 866 self.revision(self.node(rev2)))
860 867
861 868 def revision(self, node):
862 869 """return an uncompressed revision of a given"""
863 870 if node == nullid: return ""
864 871 if self.cache and self.cache[0] == node: return self.cache[2]
865 872
866 873 # look up what we need to read
867 874 text = None
868 875 rev = self.rev(node)
869 876 base = self.base(rev)
870 877
871 878 if self.inlinedata():
872 879 # we probably have the whole chunk cached
873 880 df = None
874 881 else:
875 882 df = self.opener(self.datafile)
876 883
877 884 # do we have useful data cached?
878 885 if self.cache and self.cache[1] >= base and self.cache[1] < rev:
879 886 base = self.cache[1]
880 887 text = self.cache[2]
881 888 self.loadindex(base, rev + 1)
882 889 else:
883 890 self.loadindex(base, rev + 1)
884 891 text = self.chunk(base, df=df)
885 892
886 893 bins = []
887 894 for r in xrange(base + 1, rev + 1):
888 895 bins.append(self.chunk(r, df=df))
889 896
890 897 text = self.patches(text, bins)
891 898
892 899 p1, p2 = self.parents(node)
893 900 if node != hash(text, p1, p2):
894 901 raise RevlogError(_("integrity check failed on %s:%d")
895 902 % (self.datafile, rev))
896 903
897 904 self.cache = (node, rev, text)
898 905 return text
899 906
900 907 def checkinlinesize(self, tr, fp=None):
901 908 if not self.inlinedata():
902 909 return
903 910 if not fp:
904 911 fp = self.opener(self.indexfile, 'r')
905 912 fp.seek(0, 2)
906 913 size = fp.tell()
907 914 if size < 131072:
908 915 return
909 916 trinfo = tr.find(self.indexfile)
910 917 if trinfo == None:
911 918 raise RevlogError(_("%s not found in the transaction" %
912 919 self.indexfile))
913 920
914 921 trindex = trinfo[2]
915 922 dataoff = self.start(trindex)
916 923
917 924 tr.add(self.datafile, dataoff)
918 925 df = self.opener(self.datafile, 'w')
919 926 calc = struct.calcsize(self.indexformat)
920 927 for r in xrange(self.count()):
921 928 start = self.start(r) + (r + 1) * calc
922 929 length = self.length(r)
923 930 fp.seek(start)
924 931 d = fp.read(length)
925 932 df.write(d)
926 933 fp.close()
927 934 df.close()
928 935 fp = self.opener(self.indexfile, 'w', atomictemp=True)
929 936 self.version &= ~(REVLOGNGINLINEDATA)
930 937 if self.count():
931 938 x = self.index[0]
932 939 e = struct.pack(self.indexformat, *x)[4:]
933 940 l = struct.pack(versionformat, self.version)
934 941 fp.write(l)
935 942 fp.write(e)
936 943
937 944 for i in xrange(1, self.count()):
938 945 x = self.index[i]
939 946 e = struct.pack(self.indexformat, *x)
940 947 fp.write(e)
941 948
942 949 # if we don't call rename, the temp file will never replace the
943 950 # real index
944 951 fp.rename()
945 952
946 953 tr.replace(self.indexfile, trindex * calc)
947 954 self.chunkcache = None
948 955
949 956 def addrevision(self, text, transaction, link, p1=None, p2=None, d=None):
950 957 """add a revision to the log
951 958
952 959 text - the revision data to add
953 960 transaction - the transaction object used for rollback
954 961 link - the linkrev data to add
955 962 p1, p2 - the parent nodeids of the revision
956 963 d - an optional precomputed delta
957 964 """
958 965 if not self.inlinedata():
959 966 dfh = self.opener(self.datafile, "a")
960 967 else:
961 968 dfh = None
962 969 ifh = self.opener(self.indexfile, "a+")
963 970 return self._addrevision(text, transaction, link, p1, p2, d, ifh, dfh)
964 971
965 972 def _addrevision(self, text, transaction, link, p1, p2, d, ifh, dfh):
966 973 if text is None: text = ""
967 974 if p1 is None: p1 = self.tip()
968 975 if p2 is None: p2 = nullid
969 976
970 977 node = hash(text, p1, p2)
971 978
972 979 if node in self.nodemap:
973 980 return node
974 981
975 982 n = self.count()
976 983 t = n - 1
977 984
978 985 if n:
979 986 base = self.base(t)
980 987 start = self.start(base)
981 988 end = self.end(t)
982 989 if not d:
983 990 prev = self.revision(self.tip())
984 991 d = self.diff(prev, text)
985 992 data = compress(d)
986 993 l = len(data[1]) + len(data[0])
987 994 dist = end - start + l
988 995
989 996 # full versions are inserted when the needed deltas
990 997 # become comparable to the uncompressed text
991 998 if not n or dist > len(text) * 2:
992 999 data = compress(text)
993 1000 l = len(data[1]) + len(data[0])
994 1001 base = n
995 1002 else:
996 1003 base = self.base(t)
997 1004
998 1005 offset = 0
999 1006 if t >= 0:
1000 1007 offset = self.end(t)
1001 1008
1002 1009 if self.version == REVLOGV0:
1003 1010 e = (offset, l, base, link, p1, p2, node)
1004 1011 else:
1005 1012 e = (self.offset_type(offset, 0), l, len(text),
1006 1013 base, link, self.rev(p1), self.rev(p2), node)
1007 1014
1008 1015 self.index.append(e)
1009 1016 self.nodemap[node] = n
1010 1017 entry = struct.pack(self.indexformat, *e)
1011 1018
1012 1019 if not self.inlinedata():
1013 1020 transaction.add(self.datafile, offset)
1014 1021 transaction.add(self.indexfile, n * len(entry))
1015 1022 if data[0]:
1016 1023 dfh.write(data[0])
1017 1024 dfh.write(data[1])
1018 1025 dfh.flush()
1019 1026 else:
1020 1027 ifh.seek(0, 2)
1021 1028 transaction.add(self.indexfile, ifh.tell(), self.count() - 1)
1022 1029
1023 1030 if len(self.index) == 1 and self.version != REVLOGV0:
1024 1031 l = struct.pack(versionformat, self.version)
1025 1032 ifh.write(l)
1026 1033 entry = entry[4:]
1027 1034
1028 1035 ifh.write(entry)
1029 1036
1030 1037 if self.inlinedata():
1031 1038 ifh.write(data[0])
1032 1039 ifh.write(data[1])
1033 1040 self.checkinlinesize(transaction, ifh)
1034 1041
1035 1042 self.cache = (node, n, text)
1036 1043 return node
1037 1044
1038 1045 def ancestor(self, a, b):
1039 1046 """calculate the least common ancestor of nodes a and b"""
1040 1047
1041 1048 def parents(rev):
1042 1049 return [p for p in self.parentrevs(rev) if p != -1]
1043 1050
1044 1051 c = ancestor.ancestor(self.rev(a), self.rev(b), parents)
1045 1052 if c is None:
1046 1053 return nullid
1047 1054
1048 1055 return self.node(c)
1049 1056
1050 1057 def group(self, nodelist, lookup, infocollect=None):
1051 1058 """calculate a delta group
1052 1059
1053 1060 Given a list of changeset revs, return a set of deltas and
1054 1061 metadata corresponding to nodes. the first delta is
1055 1062 parent(nodes[0]) -> nodes[0] the receiver is guaranteed to
1056 1063 have this parent as it has all history before these
1057 1064 changesets. parent is parent[0]
1058 1065 """
1059 1066 revs = [self.rev(n) for n in nodelist]
1060 1067
1061 1068 # if we don't have any revisions touched by these changesets, bail
1062 1069 if not revs:
1063 1070 yield changegroup.closechunk()
1064 1071 return
1065 1072
1066 1073 # add the parent of the first rev
1067 1074 p = self.parents(self.node(revs[0]))[0]
1068 1075 revs.insert(0, self.rev(p))
1069 1076
1070 1077 # build deltas
1071 1078 for d in xrange(0, len(revs) - 1):
1072 1079 a, b = revs[d], revs[d + 1]
1073 1080 nb = self.node(b)
1074 1081
1075 1082 if infocollect is not None:
1076 1083 infocollect(nb)
1077 1084
1078 1085 d = self.revdiff(a, b)
1079 1086 p = self.parents(nb)
1080 1087 meta = nb + p[0] + p[1] + lookup(nb)
1081 1088 yield changegroup.genchunk("%s%s" % (meta, d))
1082 1089
1083 1090 yield changegroup.closechunk()
1084 1091
1085 1092 def addgroup(self, revs, linkmapper, transaction, unique=0):
1086 1093 """
1087 1094 add a delta group
1088 1095
1089 1096 given a set of deltas, add them to the revision log. the
1090 1097 first delta is against its parent, which should be in our
1091 1098 log, the rest are against the previous delta.
1092 1099 """
1093 1100
1094 1101 #track the base of the current delta log
1095 1102 r = self.count()
1096 1103 t = r - 1
1097 1104 node = None
1098 1105
1099 1106 base = prev = -1
1100 1107 start = end = textlen = 0
1101 1108 if r:
1102 1109 end = self.end(t)
1103 1110
1104 1111 ifh = self.opener(self.indexfile, "a+")
1105 1112 ifh.seek(0, 2)
1106 1113 transaction.add(self.indexfile, ifh.tell(), self.count())
1107 1114 if self.inlinedata():
1108 1115 dfh = None
1109 1116 else:
1110 1117 transaction.add(self.datafile, end)
1111 1118 dfh = self.opener(self.datafile, "a")
1112 1119
1113 1120 # loop through our set of deltas
1114 1121 chain = None
1115 1122 for chunk in revs:
1116 1123 node, p1, p2, cs = struct.unpack("20s20s20s20s", chunk[:80])
1117 1124 link = linkmapper(cs)
1118 1125 if node in self.nodemap:
1119 1126 # this can happen if two branches make the same change
1120 1127 # if unique:
1121 1128 # raise RevlogError(_("already have %s") % hex(node[:4]))
1122 1129 chain = node
1123 1130 continue
1124 1131 delta = chunk[80:]
1125 1132
1126 1133 for p in (p1, p2):
1127 1134 if not p in self.nodemap:
1128 1135 raise RevlogError(_("unknown parent %s") % short(p))
1129 1136
1130 1137 if not chain:
1131 1138 # retrieve the parent revision of the delta chain
1132 1139 chain = p1
1133 1140 if not chain in self.nodemap:
1134 1141 raise RevlogError(_("unknown base %s") % short(chain[:4]))
1135 1142
1136 1143 # full versions are inserted when the needed deltas become
1137 1144 # comparable to the uncompressed text or when the previous
1138 1145 # version is not the one we have a delta against. We use
1139 1146 # the size of the previous full rev as a proxy for the
1140 1147 # current size.
1141 1148
1142 1149 if chain == prev:
1143 1150 tempd = compress(delta)
1144 1151 cdelta = tempd[0] + tempd[1]
1145 1152 textlen = mdiff.patchedsize(textlen, delta)
1146 1153
1147 1154 if chain != prev or (end - start + len(cdelta)) > textlen * 2:
1148 1155 # flush our writes here so we can read it in revision
1149 1156 if dfh:
1150 1157 dfh.flush()
1151 1158 ifh.flush()
1152 1159 text = self.revision(chain)
1153 1160 text = self.patches(text, [delta])
1154 1161 chk = self._addrevision(text, transaction, link, p1, p2, None,
1155 1162 ifh, dfh)
1156 1163 if not dfh and not self.inlinedata():
1157 1164 # addrevision switched from inline to conventional
1158 1165 # reopen the index
1159 1166 dfh = self.opener(self.datafile, "a")
1160 1167 ifh = self.opener(self.indexfile, "a")
1161 1168 if chk != node:
1162 1169 raise RevlogError(_("consistency error adding group"))
1163 1170 textlen = len(text)
1164 1171 else:
1165 1172 if self.version == REVLOGV0:
1166 1173 e = (end, len(cdelta), base, link, p1, p2, node)
1167 1174 else:
1168 1175 e = (self.offset_type(end, 0), len(cdelta), textlen, base,
1169 1176 link, self.rev(p1), self.rev(p2), node)
1170 1177 self.index.append(e)
1171 1178 self.nodemap[node] = r
1172 1179 if self.inlinedata():
1173 1180 ifh.write(struct.pack(self.indexformat, *e))
1174 1181 ifh.write(cdelta)
1175 1182 self.checkinlinesize(transaction, ifh)
1176 1183 if not self.inlinedata():
1177 1184 dfh = self.opener(self.datafile, "a")
1178 1185 ifh = self.opener(self.indexfile, "a")
1179 1186 else:
1180 1187 dfh.write(cdelta)
1181 1188 ifh.write(struct.pack(self.indexformat, *e))
1182 1189
1183 1190 t, r, chain, prev = r, r + 1, node, node
1184 1191 base = self.base(t)
1185 1192 start = self.start(base)
1186 1193 end = self.end(t)
1187 1194
1188 1195 return node
1189 1196
1190 1197 def strip(self, rev, minlink):
1191 1198 if self.count() == 0 or rev >= self.count():
1192 1199 return
1193 1200
1194 1201 if isinstance(self.index, lazyindex):
1195 1202 self.loadindexmap()
1196 1203
1197 1204 # When stripping away a revision, we need to make sure it
1198 1205 # does not actually belong to an older changeset.
1199 1206 # The minlink parameter defines the oldest revision
1200 1207 # we're allowed to strip away.
1201 1208 while minlink > self.index[rev][-4]:
1202 1209 rev += 1
1203 1210 if rev >= self.count():
1204 1211 return
1205 1212
1206 1213 # first truncate the files on disk
1207 1214 end = self.start(rev)
1208 1215 if not self.inlinedata():
1209 1216 df = self.opener(self.datafile, "a")
1210 1217 df.truncate(end)
1211 1218 end = rev * struct.calcsize(self.indexformat)
1212 1219 else:
1213 1220 end += rev * struct.calcsize(self.indexformat)
1214 1221
1215 1222 indexf = self.opener(self.indexfile, "a")
1216 1223 indexf.truncate(end)
1217 1224
1218 1225 # then reset internal state in memory to forget those revisions
1219 1226 self.cache = None
1220 1227 self.chunkcache = None
1221 1228 for x in xrange(rev, self.count()):
1222 1229 del self.nodemap[self.node(x)]
1223 1230
1224 1231 del self.index[rev:]
1225 1232
1226 1233 def checksize(self):
1227 1234 expected = 0
1228 1235 if self.count():
1229 1236 expected = self.end(self.count() - 1)
1230 1237
1231 1238 try:
1232 1239 f = self.opener(self.datafile)
1233 1240 f.seek(0, 2)
1234 1241 actual = f.tell()
1235 1242 dd = actual - expected
1236 1243 except IOError, inst:
1237 1244 if inst.errno != errno.ENOENT:
1238 1245 raise
1239 1246 dd = 0
1240 1247
1241 1248 try:
1242 1249 f = self.opener(self.indexfile)
1243 1250 f.seek(0, 2)
1244 1251 actual = f.tell()
1245 1252 s = struct.calcsize(self.indexformat)
1246 1253 i = actual / s
1247 1254 di = actual - (i * s)
1248 1255 if self.inlinedata():
1249 1256 databytes = 0
1250 1257 for r in xrange(self.count()):
1251 1258 databytes += self.length(r)
1252 1259 dd = 0
1253 1260 di = actual - self.count() * s - databytes
1254 1261 except IOError, inst:
1255 1262 if inst.errno != errno.ENOENT:
1256 1263 raise
1257 1264 di = 0
1258 1265
1259 1266 return (dd, di)
1260 1267
1261 1268
General Comments 0
You need to be logged in to leave comments. Login now