« back to all changes in this revision
Viewing changes to bzrlib/weave.py
- browse files at revision 933
- compare with another revision
- download diff
- download tarball
- view history from revision 933
- Committer: Martin Pool
- Date: 2005-07-18 09:58:01 UTC
- Revision ID: mbp@sourcefrog.net-20050718095801-ac58616e90ee110d
- remove test that depends too much on weave internals
- files added:
- bzrlib/intset.py
- files modified:
- TODO
added
removed
bzrlib/weave.py
21
21
22
22
"""Weave - storage of related text file versions"""
23
23
24
# before intset (r923) 2000 versions in 41.5s
25
# with intset (r926) 2000 versions in 93s !!!
26
# better to just use plain sets.
27
28
# making _extract build and return a list, rather than being a generator
29
# takes 37.94s
30
24
31
# TODO: Perhaps have copy method for Weave instances?
25
32
26
33
# XXX: If we do weaves this way, will a merge still behave the same
27
34
# way if it's done in a different order? That's a pretty desirable
28
35
# property.
29
36
30
# TODO: How to write these to disk? One option is cPickle, which
31
# would be fast but less friendly to C, and perhaps not portable. Another is
32
33
37
# TODO: Nothing here so far assumes the lines are really \n newlines,
34
38
# rather than being split up in some other way. We could accomodate
35
39
# binaries, perhaps by naively splitting on \n or perhaps using
36
40
# something like a rolling checksum.
37
41
38
# TODO: Perhaps track SHA-1 in the header for protection? This would
39
# be redundant with it being stored in the inventory, but perhaps
40
# usefully so?
41
42
42
# TODO: Track version names as well as indexes.
43
43
44
# TODO: Probably do transitive expansion when specifying parents?
45
46
# TODO: Separate out some code to read and write weaves.
47
48
44
# TODO: End marker for each version so we can stop reading?
49
45
50
46
# TODO: Check that no insertion occurs inside a deletion that was
51
47
# active in the version of the insertion.
52
48
53
# TODO: Perhaps a special slower check() method that verifies more
54
# nesting constraints and the MD5 of each version?
55
56
57
58
try:
59
set
60
frozenset
61
except NameError:
62
from sets import Set, ImmutableSet
63
set = Set
64
frozenset = ImmutableSet
65
del Set, ImmutableSet
49
# TODO: In addition to the SHA-1 check, perhaps have some code that
50
# checks structural constraints of the weave: ie that insertions are
51
# properly nested, that there is no text outside of an insertion, that
52
# insertions or deletions are not repeated, etc.
53
54
# TODO: Make the info command just show info, not extract everything:
55
# it can be much faster.
56
57
# TODO: Perhaps use long integers as sets instead of set objects; may
58
# be faster.
59
60
# TODO: Parallel-extract that passes back each line along with a
61
# description of which revisions include it. Nice for checking all
62
# shas in parallel.
63
64
66
65
67
66
68
67
class WeaveError(Exception):
187
186
sha1 = s.hexdigest()
188
187
del s
189
188
189
# TODO: It'd probably be faster to append things on to a new
190
# list rather than modifying the existing one, which is likely
191
# to cause a lot of copying.
192
190
193
if parents:
191
194
ancestors = self.inclusions(parents)
192
195
delta = self._delta(ancestors, text)
275
278
if parents:
276
279
self._v.append(parents)
277
280
else:
278
self._v.append(frozenset())
281
self._v.append(set())
279
282
280
283
281
284
def _check_lines(self, text):
310
313
yield origin, text
311
314
312
315
316
def _walk(self):
317
"""Walk the weave.
318
319
Yields sequence of
320
(lineno, insert, deletes, text)
321
for each literal line.
322
"""
323
324
istack = []
325
dset = set()
326
327
lineno = 0 # line of weave, 0-based
328
329
for l in self._l:
330
if isinstance(l, tuple):
331
c, v = l
332
isactive = None
333
if c == '{':
334
istack.append(v)
335
elif c == '}':
336
oldv = istack.pop()
337
elif c == '[':
338
assert v not in dset
339
dset.add(v)
340
elif c == ']':
341
dset.remove(v)
342
else:
343
raise WeaveFormatError('unexpected instruction %r'
344
% v)
345
else:
346
assert isinstance(l, basestring)
347
assert istack
348
yield lineno, istack[-1], dset, l
349
lineno += 1
350
351
352
313
353
def _extract(self, versions):
314
354
"""Yield annotation of lines in included set.
315
355
328
368
329
369
isactive = None
330
370
371
result = []
372
331
373
WFE = WeaveFormatError
332
374
333
375
for l in self._l:
354
396
if isactive is None:
355
397
isactive = (not dset) and istack and (istack[-1] in included)
356
398
if isactive:
357
yield istack[-1], lineno, l
399
result.append((istack[-1], lineno, l))
358
400
lineno += 1
359
401
360
402
if istack:
364
406
raise WFE("unclosed deletion blocks at end of weave",
365
407
dset)
366
408
409
return result
410
411
367
412
368
413
def get_iter(self, version):
369
414
"""Yield lines for the specified version."""
377
422
378
423
def mash_iter(self, included):
379
424
"""Return composed version of multiple included versions."""
380
included = frozenset(included)
381
425
for origin, lineno, text in self._extract(included):
382
426
yield text
383
427
503
547
yield real_i1, real_i2, lines[j1:j2]
504
548
505
549
550
551
def plan_merge(self, ver_a, ver_b):
552
"""Return pseudo-annotation indicating how the two versions merge.
553
554
This is computed between versions a and b and their common
555
base.
556
557
Weave lines present in none of them are skipped entirely.
558
"""
559
inc_a = self.inclusions([ver_a])
560
inc_b = self.inclusions([ver_b])
561
inc_c = inc_a & inc_b
562
563
for lineno, insert, deleteset, line in self._walk():
564
if deleteset & inc_c:
565
# killed in parent; can't be in either a or b
566
# not relevant to our work
567
yield 'killed-base', line
568
elif insert in inc_c:
569
# was inserted in base
570
killed_a = bool(deleteset & inc_a)
571
killed_b = bool(deleteset & inc_b)
572
if killed_a and killed_b:
573
yield 'killed-both', line
574
elif killed_a:
575
yield 'killed-a', line
576
elif killed_b:
577
yield 'killed-b', line
578
else:
579
yield 'unchanged', line
580
elif insert in inc_a:
581
if deleteset & inc_a:
582
yield 'ghost-a', line
583
else:
584
# new in A; not in B
585
yield 'new-a', line
586
elif insert in inc_b:
587
if deleteset & inc_b:
588
yield 'ghost-b', line
589
else:
590
yield 'new-b', line
591
else:
592
# not in either revision
593
yield 'irrelevant', line
594
595
yield 'unchanged', '' # terminator
596
597
598
599
def weave_merge(self, plan):
600
lines_a = []
601
lines_b = []
602
ch_a = ch_b = False
603
604
for state, line in plan:
605
if state == 'unchanged' or state == 'killed-both':
606
# resync and flush queued conflicts changes if any
607
if not lines_a and not lines_b:
608
pass
609
elif ch_a and not ch_b:
610
# one-sided change:
611
for l in lines_a: yield l
612
elif ch_b and not ch_a:
613
for l in lines_b: yield l
614
elif lines_a == lines_b:
615
for l in lines_a: yield l
616
else:
617
yield '<<<<\n'
618
for l in lines_a: yield l
619
yield '====\n'
620
for l in lines_b: yield l
621
yield '>>>>\n'
622
623
del lines_a[:]
624
del lines_b[:]
625
ch_a = ch_b = False
626
627
if state == 'unchanged':
628
if line:
629
yield line
630
elif state == 'killed-a':
631
ch_a = True
632
lines_b.append(line)
633
elif state == 'killed-b':
634
ch_b = True
635
lines_a.append(line)
636
elif state == 'new-a':
637
ch_a = True
638
lines_a.append(line)
639
elif state == 'new-b':
640
ch_b = True
641
lines_b.append(line)
642
else:
643
assert state in ('irrelevant', 'ghost-a', 'ghost-b', 'killed-base',
644
'killed-both'), \
645
state
646
647
648
649
650
651
506
652
507
653
def weave_info(filename, out):
508
654
"""Show some text information about the weave."""
651
797
w = readit()
652
798
print ' '.join(map(str, w._v[int(argv[3])]))
653
799
800
elif cmd == 'plan-merge':
801
w = readit()
802
for state, line in w.plan_merge(int(argv[3]), int(argv[4])):
803
if line:
804
print '%14s | %s' % (state, line),
805
654
806
elif cmd == 'merge':
807
w = readit()
808
p = w.plan_merge(int(argv[3]), int(argv[4]))
809
sys.stdout.writelines(w.weave_merge(p))
810
811
elif cmd == 'mash-merge':
655
812
if len(argv) != 5:
656
813
usage()
657
814
return 1
Loggerhead is a web-based interface for Breezy
Version: 2.0.1