← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/weave.py

  • Committer: Martin Pool
  • Date: 2005-07-14 08:03:52 UTC
  • Revision ID: mbp@sourcefrog.net-20050714080352-d8631baf3620057d
- start doing new weave-merge algorithm

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/weave.py
44
44
# properly nested, that there is no text outside of an insertion, that
45
45
# insertions or deletions are not repeated, etc.
46
46
 
 
47
# TODO: Make the info command just show info, not extract everything:
 
48
# it can be much faster.
 
49
 
 
50
# TODO: Perhaps use long integers as sets instead of set objects; may
 
51
# be faster.
 
52
 
 
53
# TODO: Parallel-extract that passes back each line along with a
 
54
# description of which revisions include it.  Nice for checking all
 
55
# shas in parallel.
 
56
 
 
57
 
47
58
 
48
59
 
49
60
try:
178
189
        sha1 = s.hexdigest()
179
190
        del s
180
191
 
 
192
        # TODO: It'd probably be faster to append things on to a new
 
193
        # list rather than modifying the existing one, which is likely
 
194
        # to cause a lot of copying.
 
195
 
181
196
        if parents:
182
197
            ancestors = self.inclusions(parents)
183
198
            delta = self._delta(ancestors, text)
225
240
        return idx
226
241
 
227
242
 
 
243
    def inclusions_bitset(self, versions):
 
244
        i = 0
 
245
        for v in versions:
 
246
            i |= (1L << v)
 
247
        v = max(versions)
 
248
        while v >= 0:
 
249
            if i & (1L << v):
 
250
                # if v is included, include all its parents
 
251
                for pv in self._v[v]:
 
252
                    i |= (1L << pv)
 
253
            v -= 1
 
254
        return i
 
255
 
 
256
 
228
257
    def inclusions(self, versions):
229
258
        """Return set of all ancestors of given version(s)."""
230
259
        i = set(versions)
301
330
            yield origin, text
302
331
 
303
332
 
 
333
    def _walk(self):
 
334
        """Walk the weave.
 
335
 
 
336
        Yields sequence of
 
337
        (lineno, insert, deletes, text)
 
338
        for each literal line.
 
339
        """
 
340
        
 
341
        istack = []
 
342
        dset = 0L
 
343
 
 
344
        lineno = 0         # line of weave, 0-based
 
345
 
 
346
        for l in self._l:
 
347
            if isinstance(l, tuple):
 
348
                c, v = l
 
349
                isactive = None
 
350
                if c == '{':
 
351
                    istack.append(v)
 
352
                elif c == '}':
 
353
                    oldv = istack.pop()
 
354
                elif c == '[':
 
355
                    vs = (1L << v)
 
356
                    assert not (dset & vs)
 
357
                    dset |= vs
 
358
                elif c == ']':
 
359
                    vs = (1L << v)
 
360
                    assert dset & vs
 
361
                    dset ^= vs
 
362
                else:
 
363
                    raise WeaveFormatError('unexpected instruction %r'
 
364
                                           % v)
 
365
            else:
 
366
                assert isinstance(l, basestring)
 
367
                assert istack
 
368
                yield lineno, istack[-1], dset, l
 
369
            lineno += 1
 
370
 
 
371
 
 
372
 
304
373
    def _extract(self, versions):
305
374
        """Yield annotation of lines in included set.
306
375
 
494
563
            yield real_i1, real_i2, lines[j1:j2]
495
564
 
496
565
 
 
566
            
 
567
    def plan_merge(self, ver_a, ver_b):
 
568
        """Return pseudo-annotation indicating how the two versions merge.
 
569
 
 
570
        This is computed between versions a and b and their common
 
571
        base.
 
572
 
 
573
        Weave lines present in none of them are skipped entirely.
 
574
        """
 
575
        inc_a = self.inclusions_bitset([ver_a])
 
576
        inc_b = self.inclusions_bitset([ver_b])
 
577
        inc_c = inc_a & inc_b
 
578
 
 
579
        for lineno, insert, deleteset, line in self._walk():
 
580
            insertset = (1L << insert)
 
581
            if deleteset & inc_c:
 
582
                # killed in parent; can't be in either a or b
 
583
                # not relevant to our work
 
584
                yield 'killed-base', line
 
585
            elif insertset & inc_c:
 
586
                # was inserted in base
 
587
                killed_a = bool(deleteset & inc_a)
 
588
                killed_b = bool(deleteset & inc_b)
 
589
                if killed_a and killed_b:
 
590
                    # killed in both
 
591
                    yield 'killed-both', line
 
592
                elif killed_a:
 
593
                    yield 'killed-a', line
 
594
                elif killed_b:
 
595
                    yield 'killed-b', line
 
596
                else:
 
597
                    yield 'unchanged', line
 
598
            elif insertset & inc_a:
 
599
                if deleteset & inc_a:
 
600
                    yield 'ghost-a', line
 
601
                else:
 
602
                    # new in A; not in B
 
603
                    yield 'new-a', line
 
604
            elif insertset & inc_b:
 
605
                if deleteset & inc_b:
 
606
                    yield 'ghost-b', line
 
607
                else:
 
608
                    yield 'new-b', line
 
609
            else:
 
610
                # not in either revision
 
611
                yield 'irrelevant', line
 
612
 
 
613
 
 
614
 
497
615
 
498
616
def weave_info(filename, out):
499
617
    """Show some text information about the weave."""
642
760
        w = readit()
643
761
        print ' '.join(map(str, w._v[int(argv[3])]))
644
762
 
 
763
    elif cmd == 'plan-merge':
 
764
        w = readit()
 
765
        for state, line in w.plan_merge(int(argv[3]), int(argv[4])):
 
766
            print '%14s | %s' % (state, line),
 
767
 
645
768
    elif cmd == 'merge':
646
769
        if len(argv) != 5:
647
770
            usage()