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