/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/weave.py

  • Committer: Martin Pool
  • Date: 2005-07-17 17:53:39 UTC
  • mfrom: (909.1.5)
  • Revision ID: mbp@sourcefrog.net-20050717175339-9433d3dc4d9d3b5c
- Add IntSet class

- Start converting weave calculation to use it

Show diffs side-by-side

added added

removed removed

Lines of Context:
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
 
 
31
 
# with python -O, r923 does 2000 versions in 36.87s
32
 
 
33
 
# with optimizations to avoid mutating lists - 35.75!  I guess copying
34
 
# all the elements every time costs more than the small manipulations.
35
 
# a surprisingly small change.
36
 
 
37
 
# r931, which avoids using a generator for extract, does 36.98s
38
 
 
39
 
# with memoized inclusions, takes 41.49s; not very good
40
 
 
41
 
# with slots, takes 37.35s; without takes 39.16, a bit surprising
42
 
 
43
 
# with the delta calculation mixed in with the add method, rather than
44
 
# separated, takes 36.78s
45
 
 
46
 
# with delta folded in and mutation of the list, 36.13s
47
 
 
48
 
# with all this and simplification of add code, 33s 
49
 
 
50
 
 
51
24
# TODO: Perhaps have copy method for Weave instances?
52
25
 
53
26
# XXX: If we do weaves this way, will a merge still behave the same
71
44
# properly nested, that there is no text outside of an insertion, that
72
45
# insertions or deletions are not repeated, etc.
73
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
 
74
53
# TODO: Parallel-extract that passes back each line along with a
75
54
# description of which revisions include it.  Nice for checking all
76
55
# shas in parallel.
78
57
 
79
58
 
80
59
 
 
60
try:
 
61
    set
 
62
    frozenset
 
63
except NameError:
 
64
    from sets import Set, ImmutableSet
 
65
    set = Set
 
66
    frozenset = ImmutableSet
 
67
    del Set, ImmutableSet
 
68
 
 
69
 
 
70
 
81
71
class WeaveError(Exception):
82
72
    """Exception in processing weave"""
83
73
 
107
97
    the version-id is used to reference it in the larger world.
108
98
 
109
99
    The weave is represented as a list mixing edit instructions and
110
 
    literal text.  Each entry in _weave can be either a string (or
 
100
    literal text.  Each entry in _l can be either a string (or
111
101
    unicode), or a tuple.  If a string, it means that the given line
112
102
    should be output in the currently active revisions.
113
103
 
151
141
      should be no way to get an earlier version deleting a later
152
142
      version.
153
143
 
154
 
    _weave
155
 
        Text of the weave; list of control instruction tuples and strings.
 
144
    _l
 
145
        Text of the weave.
156
146
 
157
 
    _parents
 
147
    _v
158
148
        List of parents, indexed by version number.
159
149
        It is only necessary to store the minimal set of parents for
160
150
        each version; the parent's parents are implied.
162
152
    _sha1s
163
153
        List of hex SHA-1 of each version, or None if not recorded.
164
154
    """
165
 
 
166
 
    __slots__ = ['_weave', '_parents', '_sha1s']
167
 
    
168
155
    def __init__(self):
169
 
        self._weave = []
170
 
        self._parents = []
 
156
        self._l = []
 
157
        self._v = []
171
158
        self._sha1s = []
172
159
 
173
160
 
174
161
    def __eq__(self, other):
175
162
        if not isinstance(other, Weave):
176
163
            return False
177
 
        return self._parents == other._parents \
178
 
               and self._weave == other._weave
 
164
        return self._v == other._v \
 
165
               and self._l == other._l
179
166
    
180
167
 
181
168
    def __ne__(self, other):
192
179
            
193
180
        text
194
181
            Sequence of lines to be added in the new version."""
195
 
 
196
 
        self._check_versions(parents)
 
182
        ## self._check_versions(parents)
197
183
        ## self._check_lines(text)
198
 
        new_version = len(self._parents)
 
184
        idx = len(self._v)
199
185
 
200
186
        import sha
201
187
        s = sha.new()
202
 
        map(s.update, text)
 
188
        for l in text:
 
189
            s.update(l)
203
190
        sha1 = s.hexdigest()
204
191
        del s
205
192
 
206
 
        # if we abort after here the weave will be corrupt
207
 
        self._parents.append(frozenset(parents))
 
193
        # TODO: It'd probably be faster to append things on to a new
 
194
        # list rather than modifying the existing one, which is likely
 
195
        # to cause a lot of copying.
 
196
 
 
197
        if parents:
 
198
            ancestors = self.inclusions(parents)
 
199
            delta = self._delta(ancestors, text)
 
200
 
 
201
            # offset gives the number of lines that have been inserted
 
202
            # into the weave up to the current point; if the original edit instruction
 
203
            # says to change line A then we actually change (A+offset)
 
204
            offset = 0
 
205
 
 
206
            for i1, i2, newlines in delta:
 
207
                assert 0 <= i1
 
208
                assert i1 <= i2
 
209
                assert i2 <= len(self._l)
 
210
 
 
211
                # the deletion and insertion are handled separately.
 
212
                # first delete the region.
 
213
                if i1 != i2:
 
214
                    self._l.insert(i1+offset, ('[', idx))
 
215
                    self._l.insert(i2+offset+1, (']', idx))
 
216
                    offset += 2
 
217
                    # is this OK???
 
218
 
 
219
                if newlines:
 
220
                    # there may have been a deletion spanning up to
 
221
                    # i2; we want to insert after this region to make sure
 
222
                    # we don't destroy ourselves
 
223
                    i = i2 + offset
 
224
                    self._l[i:i] = [('{', idx)] \
 
225
                                   + newlines \
 
226
                                   + [('}', idx)]
 
227
                    offset += 2 + len(newlines)
 
228
 
 
229
            self._addversion(parents)
 
230
        else:
 
231
            # special case; adding with no parents revision; can do this
 
232
            # more quickly by just appending unconditionally
 
233
            self._l.append(('{', idx))
 
234
            self._l += text
 
235
            self._l.append(('}', idx))
 
236
 
 
237
            self._addversion(None)
 
238
 
208
239
        self._sha1s.append(sha1)
209
 
 
210
 
            
211
 
        if not parents:
212
 
            # special case; adding with no parents revision; can do
213
 
            # this more quickly by just appending unconditionally.
214
 
            # even more specially, if we're adding an empty text we
215
 
            # need do nothing at all.
216
 
            if text:
217
 
                self._weave.append(('{', new_version))
218
 
                self._weave.extend(text)
219
 
                self._weave.append(('}', new_version))
220
 
        
221
 
            return new_version
222
 
 
223
 
        if len(parents) == 1:
224
 
            pv = list(parents)[0]
225
 
            if sha1 == self._sha1s[pv]:
226
 
                # special case: same as the single parent
227
 
                return new_version
228
 
            
229
 
 
230
 
        ancestors = self.inclusions(parents)
231
 
 
232
 
        l = self._weave
233
 
 
234
 
        # basis a list of (origin, lineno, line)
235
 
        basis_lineno = []
236
 
        basis_lines = []
237
 
        for origin, lineno, line in self._extract(ancestors):
238
 
            basis_lineno.append(lineno)
239
 
            basis_lines.append(line)
240
 
 
241
 
        # another small special case: a merge, producing the same text as auto-merge
242
 
        if text == basis_lines:
243
 
            return new_version            
244
 
 
245
 
        # add a sentinal, because we can also match against the final line
246
 
        basis_lineno.append(len(self._weave))
247
 
 
248
 
        # XXX: which line of the weave should we really consider
249
 
        # matches the end of the file?  the current code says it's the
250
 
        # last line of the weave?
251
 
 
252
 
        #print 'basis_lines:', basis_lines
253
 
        #print 'new_lines:  ', lines
254
 
 
255
 
        from difflib import SequenceMatcher
256
 
        s = SequenceMatcher(None, basis_lines, text)
257
 
 
258
 
        # offset gives the number of lines that have been inserted
259
 
        # into the weave up to the current point; if the original edit instruction
260
 
        # says to change line A then we actually change (A+offset)
261
 
        offset = 0
262
 
 
263
 
        for tag, i1, i2, j1, j2 in s.get_opcodes():
264
 
            # i1,i2 are given in offsets within basis_lines; we need to map them
265
 
            # back to offsets within the entire weave
266
 
            #print 'raw match', tag, i1, i2, j1, j2
267
 
            if tag == 'equal':
268
 
                continue
269
 
 
270
 
            i1 = basis_lineno[i1]
271
 
            i2 = basis_lineno[i2]
272
 
 
273
 
            assert 0 <= j1 <= j2 <= len(text)
274
 
 
275
 
            #print tag, i1, i2, j1, j2
276
 
 
277
 
            # the deletion and insertion are handled separately.
278
 
            # first delete the region.
279
 
            if i1 != i2:
280
 
                self._weave.insert(i1+offset, ('[', new_version))
281
 
                self._weave.insert(i2+offset+1, (']', new_version))
282
 
                offset += 2
283
 
 
284
 
            if j1 != j2:
285
 
                # there may have been a deletion spanning up to
286
 
                # i2; we want to insert after this region to make sure
287
 
                # we don't destroy ourselves
288
 
                i = i2 + offset
289
 
                self._weave[i:i] = ([('{', new_version)] 
290
 
                                + text[j1:j2] 
291
 
                                + [('}', new_version)])
292
 
                offset += 2 + (j2 - j1)
293
 
 
294
 
        return new_version
 
240
            
 
241
        return idx
 
242
 
 
243
 
 
244
    def inclusions_bitset(self, versions):
 
245
        i = 0
 
246
        for v in versions:
 
247
            i |= (1L << v)
 
248
        v = max(versions)
 
249
        while v >= 0:
 
250
            if i & (1L << v):
 
251
                # if v is included, include all its parents
 
252
                for pv in self._v[v]:
 
253
                    i |= (1L << pv)
 
254
            v -= 1
 
255
        return i
295
256
 
296
257
 
297
258
    def inclusions(self, versions):
298
259
        """Return set of all ancestors of given version(s)."""
299
 
        i = set(versions)
 
260
        from bzrlib.intset import IntSet
 
261
        
 
262
        i = IntSet(versions)
300
263
        v = max(versions)
301
264
        try:
302
265
            while v >= 0:
303
266
                if v in i:
304
267
                    # include all its parents
305
 
                    i.update(self._parents[v])
 
268
                    i.update(self._v[v])
306
269
                v -= 1
307
270
            return i
308
271
        except IndexError:
311
274
 
312
275
    def minimal_parents(self, version):
313
276
        """Find the minimal set of parents for the version."""
314
 
        included = self._parents[version]
 
277
        from bzrlib.intset import IntSet
 
278
        
 
279
        included = self._v[version]
315
280
        if not included:
316
281
            return []
317
282
        
319
284
        li.sort(reverse=True)
320
285
 
321
286
        mininc = []
322
 
        gotit = set()
 
287
        gotit = IntSet()
323
288
 
324
289
        for pv in li:
325
290
            if pv not in gotit:
331
296
        return mininc
332
297
 
333
298
 
 
299
    def _addversion(self, parents):
 
300
        if parents:
 
301
            self._v.append(parents)
 
302
        else:
 
303
            self._v.append(frozenset())
 
304
 
334
305
 
335
306
    def _check_lines(self, text):
336
307
        if not isinstance(text, list):
347
318
        """Check everything in the sequence of indexes is valid"""
348
319
        for i in indexes:
349
320
            try:
350
 
                self._parents[i]
 
321
                self._v[i]
351
322
            except IndexError:
352
323
                raise IndexError("invalid version number %r" % i)
353
324
 
373
344
        """
374
345
        
375
346
        istack = []
376
 
        dset = set()
 
347
        dset = 0L
377
348
 
378
349
        lineno = 0         # line of weave, 0-based
379
350
 
380
 
        for l in self._weave:
 
351
        for l in self._l:
381
352
            if isinstance(l, tuple):
382
353
                c, v = l
383
354
                isactive = None
386
357
                elif c == '}':
387
358
                    oldv = istack.pop()
388
359
                elif c == '[':
389
 
                    assert v not in dset
390
 
                    dset.add(v)
 
360
                    vs = (1L << v)
 
361
                    assert not (dset & vs)
 
362
                    dset |= vs
391
363
                elif c == ']':
392
 
                    dset.remove(v)
 
364
                    vs = (1L << v)
 
365
                    assert dset & vs
 
366
                    dset ^= vs
393
367
                else:
394
368
                    raise WeaveFormatError('unexpected instruction %r'
395
369
                                           % v)
419
393
 
420
394
        isactive = None
421
395
 
422
 
        result = []
423
 
 
424
396
        WFE = WeaveFormatError
425
397
 
426
 
        for l in self._weave:
 
398
        for l in self._l:
427
399
            if isinstance(l, tuple):
428
400
                c, v = l
429
401
                isactive = None
447
419
                if isactive is None:
448
420
                    isactive = (not dset) and istack and (istack[-1] in included)
449
421
                if isactive:
450
 
                    result.append((istack[-1], lineno, l))
 
422
                    yield istack[-1], lineno, l
451
423
            lineno += 1
452
424
 
453
425
        if istack:
457
429
            raise WFE("unclosed deletion blocks at end of weave",
458
430
                                   dset)
459
431
 
460
 
        return result
461
 
    
462
 
 
463
432
 
464
433
    def get_iter(self, version):
465
434
        """Yield lines for the specified version."""
473
442
 
474
443
    def mash_iter(self, included):
475
444
        """Return composed version of multiple included versions."""
 
445
        included = frozenset(included)
476
446
        for origin, lineno, text in self._extract(included):
477
447
            yield text
478
448
 
479
449
 
480
450
    def dump(self, to_file):
481
451
        from pprint import pprint
482
 
        print >>to_file, "Weave._weave = ",
483
 
        pprint(self._weave, to_file)
484
 
        print >>to_file, "Weave._parents = ",
485
 
        pprint(self._parents, to_file)
 
452
        print >>to_file, "Weave._l = ",
 
453
        pprint(self._l, to_file)
 
454
        print >>to_file, "Weave._v = ",
 
455
        pprint(self._v, to_file)
486
456
 
487
457
 
488
458
 
489
459
    def numversions(self):
490
 
        l = len(self._parents)
 
460
        l = len(self._v)
491
461
        assert l == len(self._sha1s)
492
462
        return l
493
463
 
494
464
 
495
 
    def __len__(self):
496
 
        return self.numversions()
497
 
 
498
 
 
499
465
    def check(self, progress_bar=None):
500
466
        # check no circular inclusions
501
467
        for version in range(self.numversions()):
502
 
            inclusions = list(self._parents[version])
 
468
            inclusions = list(self._v[version])
503
469
            if inclusions:
504
470
                inclusions.sort()
505
471
                if inclusions[-1] >= version:
565
531
        If line1=line2, this is a pure insert; if newlines=[] this is a
566
532
        pure delete.  (Similar to difflib.)
567
533
        """
 
534
        # basis a list of (origin, lineno, line)
 
535
        basis_lineno = []
 
536
        basis_lines = []
 
537
        for origin, lineno, line in self._extract(included):
 
538
            basis_lineno.append(lineno)
 
539
            basis_lines.append(line)
 
540
 
 
541
        # add a sentinal, because we can also match against the final line
 
542
        basis_lineno.append(len(self._l))
 
543
 
 
544
        # XXX: which line of the weave should we really consider
 
545
        # matches the end of the file?  the current code says it's the
 
546
        # last line of the weave?
 
547
 
 
548
        from difflib import SequenceMatcher
 
549
        s = SequenceMatcher(None, basis_lines, lines)
 
550
 
 
551
        # TODO: Perhaps return line numbers from composed weave as well?
 
552
 
 
553
        for tag, i1, i2, j1, j2 in s.get_opcodes():
 
554
            ##print tag, i1, i2, j1, j2
 
555
 
 
556
            if tag == 'equal':
 
557
                continue
 
558
 
 
559
            # i1,i2 are given in offsets within basis_lines; we need to map them
 
560
            # back to offsets within the entire weave
 
561
            real_i1 = basis_lineno[i1]
 
562
            real_i2 = basis_lineno[i2]
 
563
 
 
564
            assert 0 <= j1
 
565
            assert j1 <= j2
 
566
            assert j2 <= len(lines)
 
567
 
 
568
            yield real_i1, real_i2, lines[j1:j2]
568
569
 
569
570
 
570
571
            
576
577
 
577
578
        Weave lines present in none of them are skipped entirely.
578
579
        """
579
 
        inc_a = self.inclusions([ver_a])
580
 
        inc_b = self.inclusions([ver_b])
 
580
        inc_a = self.inclusions_bitset([ver_a])
 
581
        inc_b = self.inclusions_bitset([ver_b])
581
582
        inc_c = inc_a & inc_b
582
583
 
583
584
        for lineno, insert, deleteset, line in self._walk():
 
585
            insertset = (1L << insert)
584
586
            if deleteset & inc_c:
585
587
                # killed in parent; can't be in either a or b
586
588
                # not relevant to our work
587
589
                yield 'killed-base', line
588
 
            elif insert in inc_c:
 
590
            elif insertset & inc_c:
589
591
                # was inserted in base
590
592
                killed_a = bool(deleteset & inc_a)
591
593
                killed_b = bool(deleteset & inc_b)
597
599
                    yield 'killed-b', line
598
600
                else:
599
601
                    yield 'unchanged', line
600
 
            elif insert in inc_a:
 
602
            elif insertset & inc_a:
601
603
                if deleteset & inc_a:
602
604
                    yield 'ghost-a', line
603
605
                else:
604
606
                    # new in A; not in B
605
607
                    yield 'new-a', line
606
 
            elif insert in inc_b:
 
608
            elif insertset & inc_b:
607
609
                if deleteset & inc_b:
608
610
                    yield 'ghost-b', line
609
611
                else:
670
672
 
671
673
 
672
674
 
673
 
def weave_info(w):
 
675
def weave_info(filename, out):
674
676
    """Show some text information about the weave."""
675
 
    print '%6s %40s %20s' % ('ver', 'sha1', 'parents')
676
 
    for i in (6, 40, 20):
677
 
        print '-' * i,
678
 
    print
679
 
    for i in range(w.numversions()):
680
 
        sha1 = w._sha1s[i]
681
 
        print '%6d %40s %s' % (i, sha1, ' '.join(map(str, w._parents[i])))
682
 
 
683
 
 
684
 
 
685
 
def weave_stats(weave_file):
686
 
    from bzrlib.progress import ProgressBar
687
 
    from bzrlib.weavefile import read_weave
688
 
 
689
 
    pb = ProgressBar()
690
 
 
691
 
    wf = file(weave_file, 'rb')
 
677
    from weavefile import read_weave
 
678
    wf = file(filename, 'rb')
692
679
    w = read_weave(wf)
693
680
    # FIXME: doesn't work on pipes
694
681
    weave_size = wf.tell()
 
682
    print >>out, "weave file size %d bytes" % weave_size
 
683
    print >>out, "weave contains %d versions" % len(w._v)
695
684
 
696
685
    total = 0
697
 
    vers = len(w)
698
 
    for i in range(vers):
699
 
        pb.update('checking sizes', i, vers)
700
 
        for line in w.get_iter(i):
701
 
            total += len(line)
702
 
 
703
 
    pb.clear()
704
 
 
705
 
    print 'versions          %9d' % vers
706
 
    print 'weave file        %9d bytes' % weave_size
707
 
    print 'total contents    %9d bytes' % total
708
 
    print 'compression ratio %9.2fx' % (float(total) / float(weave_size))
709
 
 
 
686
    print '%6s %6s %8s %40s %20s' % ('ver', 'lines', 'bytes', 'sha1', 'parents')
 
687
    for i in (6, 6, 8, 40, 20):
 
688
        print '-' * i,
 
689
    print
 
690
    for i in range(len(w._v)):
 
691
        text = w.get(i)
 
692
        lines = len(text)
 
693
        bytes = sum((len(a) for a in text))
 
694
        sha1 = w._sha1s[i]
 
695
        print '%6d %6d %8d %40s' % (i, lines, bytes, sha1),
 
696
        for pv in w._v[i]:
 
697
            print pv,
 
698
        print
 
699
        total += bytes
 
700
 
 
701
    print >>out, "versions total %d bytes" % total
 
702
    print >>out, "compression ratio %.3f" % (float(total)/float(weave_size))
710
703
 
711
704
 
712
705
def usage():
810
803
                lasto = origin
811
804
                
812
805
    elif cmd == 'info':
813
 
        weave_info(readit())
814
 
 
815
 
    elif cmd == 'stats':
816
 
        weave_stats(argv[2])
 
806
        weave_info(argv[2], sys.stdout)
817
807
        
818
808
    elif cmd == 'check':
819
809
        w = readit()
820
810
        pb = ProgressBar()
821
811
        w.check(pb)
822
812
        pb.clear()
823
 
        print '%d versions ok' % w.numversions()
824
813
 
825
814
    elif cmd == 'inclusions':
826
815
        w = readit()
828
817
 
829
818
    elif cmd == 'parents':
830
819
        w = readit()
831
 
        print ' '.join(map(str, w._parents[int(argv[3])]))
 
820
        print ' '.join(map(str, w._v[int(argv[3])]))
832
821
 
833
822
    elif cmd == 'plan-merge':
834
823
        w = readit()