/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-18 09:30:37 UTC
  • Revision ID: mbp@sourcefrog.net-20050718093037-c6eb37d3468cb809
- more diff TODOs

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/weave.py
28
28
# making _extract build and return a list, rather than being a generator
29
29
# takes 37.94s
30
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
31
# TODO: Perhaps have copy method for Weave instances?
52
32
 
53
33
# XXX: If we do weaves this way, will a merge still behave the same
71
51
# properly nested, that there is no text outside of an insertion, that
72
52
# insertions or deletions are not repeated, etc.
73
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
 
74
60
# TODO: Parallel-extract that passes back each line along with a
75
61
# description of which revisions include it.  Nice for checking all
76
62
# shas in parallel.
107
93
    the version-id is used to reference it in the larger world.
108
94
 
109
95
    The weave is represented as a list mixing edit instructions and
110
 
    literal text.  Each entry in _weave can be either a string (or
 
96
    literal text.  Each entry in _l can be either a string (or
111
97
    unicode), or a tuple.  If a string, it means that the given line
112
98
    should be output in the currently active revisions.
113
99
 
151
137
      should be no way to get an earlier version deleting a later
152
138
      version.
153
139
 
154
 
    _weave
155
 
        Text of the weave; list of control instruction tuples and strings.
 
140
    _l
 
141
        Text of the weave.
156
142
 
157
 
    _parents
 
143
    _v
158
144
        List of parents, indexed by version number.
159
145
        It is only necessary to store the minimal set of parents for
160
146
        each version; the parent's parents are implied.
162
148
    _sha1s
163
149
        List of hex SHA-1 of each version, or None if not recorded.
164
150
    """
165
 
 
166
 
    __slots__ = ['_weave', '_parents', '_sha1s']
167
 
    
168
151
    def __init__(self):
169
 
        self._weave = []
170
 
        self._parents = []
 
152
        self._l = []
 
153
        self._v = []
171
154
        self._sha1s = []
172
155
 
173
156
 
174
157
    def __eq__(self, other):
175
158
        if not isinstance(other, Weave):
176
159
            return False
177
 
        return self._parents == other._parents \
178
 
               and self._weave == other._weave
 
160
        return self._v == other._v \
 
161
               and self._l == other._l
179
162
    
180
163
 
181
164
    def __ne__(self, other):
192
175
            
193
176
        text
194
177
            Sequence of lines to be added in the new version."""
195
 
 
196
 
        self._check_versions(parents)
 
178
        ## self._check_versions(parents)
197
179
        ## self._check_lines(text)
198
 
        new_version = len(self._parents)
 
180
        idx = len(self._v)
199
181
 
200
182
        import sha
201
183
        s = sha.new()
202
 
        map(s.update, text)
 
184
        for l in text:
 
185
            s.update(l)
203
186
        sha1 = s.hexdigest()
204
187
        del s
205
188
 
206
 
        # if we abort after here the weave will be corrupt
207
 
        self._parents.append(frozenset(parents))
 
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
 
 
193
        if parents:
 
194
            ancestors = self.inclusions(parents)
 
195
            delta = self._delta(ancestors, text)
 
196
 
 
197
            # offset gives the number of lines that have been inserted
 
198
            # into the weave up to the current point; if the original edit instruction
 
199
            # says to change line A then we actually change (A+offset)
 
200
            offset = 0
 
201
 
 
202
            for i1, i2, newlines in delta:
 
203
                assert 0 <= i1
 
204
                assert i1 <= i2
 
205
                assert i2 <= len(self._l)
 
206
 
 
207
                # the deletion and insertion are handled separately.
 
208
                # first delete the region.
 
209
                if i1 != i2:
 
210
                    self._l.insert(i1+offset, ('[', idx))
 
211
                    self._l.insert(i2+offset+1, (']', idx))
 
212
                    offset += 2
 
213
                    # is this OK???
 
214
 
 
215
                if newlines:
 
216
                    # there may have been a deletion spanning up to
 
217
                    # i2; we want to insert after this region to make sure
 
218
                    # we don't destroy ourselves
 
219
                    i = i2 + offset
 
220
                    self._l[i:i] = [('{', idx)] \
 
221
                                   + newlines \
 
222
                                   + [('}', idx)]
 
223
                    offset += 2 + len(newlines)
 
224
 
 
225
            self._addversion(parents)
 
226
        else:
 
227
            # special case; adding with no parents revision; can do this
 
228
            # more quickly by just appending unconditionally
 
229
            self._l.append(('{', idx))
 
230
            self._l += text
 
231
            self._l.append(('}', idx))
 
232
 
 
233
            self._addversion(None)
 
234
 
208
235
        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
 
236
            
 
237
        return idx
295
238
 
296
239
 
297
240
    def inclusions(self, versions):
302
245
            while v >= 0:
303
246
                if v in i:
304
247
                    # include all its parents
305
 
                    i.update(self._parents[v])
 
248
                    i.update(self._v[v])
306
249
                v -= 1
307
250
            return i
308
251
        except IndexError:
311
254
 
312
255
    def minimal_parents(self, version):
313
256
        """Find the minimal set of parents for the version."""
314
 
        included = self._parents[version]
 
257
        included = self._v[version]
315
258
        if not included:
316
259
            return []
317
260
        
331
274
        return mininc
332
275
 
333
276
 
 
277
    def _addversion(self, parents):
 
278
        if parents:
 
279
            self._v.append(parents)
 
280
        else:
 
281
            self._v.append(set())
 
282
 
334
283
 
335
284
    def _check_lines(self, text):
336
285
        if not isinstance(text, list):
347
296
        """Check everything in the sequence of indexes is valid"""
348
297
        for i in indexes:
349
298
            try:
350
 
                self._parents[i]
 
299
                self._v[i]
351
300
            except IndexError:
352
301
                raise IndexError("invalid version number %r" % i)
353
302
 
377
326
 
378
327
        lineno = 0         # line of weave, 0-based
379
328
 
380
 
        for l in self._weave:
 
329
        for l in self._l:
381
330
            if isinstance(l, tuple):
382
331
                c, v = l
383
332
                isactive = None
423
372
 
424
373
        WFE = WeaveFormatError
425
374
 
426
 
        for l in self._weave:
 
375
        for l in self._l:
427
376
            if isinstance(l, tuple):
428
377
                c, v = l
429
378
                isactive = None
479
428
 
480
429
    def dump(self, to_file):
481
430
        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)
 
431
        print >>to_file, "Weave._l = ",
 
432
        pprint(self._l, to_file)
 
433
        print >>to_file, "Weave._v = ",
 
434
        pprint(self._v, to_file)
486
435
 
487
436
 
488
437
 
489
438
    def numversions(self):
490
 
        l = len(self._parents)
 
439
        l = len(self._v)
491
440
        assert l == len(self._sha1s)
492
441
        return l
493
442
 
494
443
 
495
 
    def __len__(self):
496
 
        return self.numversions()
497
 
 
498
 
 
499
444
    def check(self, progress_bar=None):
500
445
        # check no circular inclusions
501
446
        for version in range(self.numversions()):
502
 
            inclusions = list(self._parents[version])
 
447
            inclusions = list(self._v[version])
503
448
            if inclusions:
504
449
                inclusions.sort()
505
450
                if inclusions[-1] >= version:
565
510
        If line1=line2, this is a pure insert; if newlines=[] this is a
566
511
        pure delete.  (Similar to difflib.)
567
512
        """
 
513
        # basis a list of (origin, lineno, line)
 
514
        basis_lineno = []
 
515
        basis_lines = []
 
516
        for origin, lineno, line in self._extract(included):
 
517
            basis_lineno.append(lineno)
 
518
            basis_lines.append(line)
 
519
 
 
520
        # add a sentinal, because we can also match against the final line
 
521
        basis_lineno.append(len(self._l))
 
522
 
 
523
        # XXX: which line of the weave should we really consider
 
524
        # matches the end of the file?  the current code says it's the
 
525
        # last line of the weave?
 
526
 
 
527
        from difflib import SequenceMatcher
 
528
        s = SequenceMatcher(None, basis_lines, lines)
 
529
 
 
530
        # TODO: Perhaps return line numbers from composed weave as well?
 
531
 
 
532
        for tag, i1, i2, j1, j2 in s.get_opcodes():
 
533
            ##print tag, i1, i2, j1, j2
 
534
 
 
535
            if tag == 'equal':
 
536
                continue
 
537
 
 
538
            # i1,i2 are given in offsets within basis_lines; we need to map them
 
539
            # back to offsets within the entire weave
 
540
            real_i1 = basis_lineno[i1]
 
541
            real_i2 = basis_lineno[i2]
 
542
 
 
543
            assert 0 <= j1
 
544
            assert j1 <= j2
 
545
            assert j2 <= len(lines)
 
546
 
 
547
            yield real_i1, real_i2, lines[j1:j2]
568
548
 
569
549
 
570
550
            
670
650
 
671
651
 
672
652
 
673
 
def weave_info(w):
 
653
def weave_info(filename, out):
674
654
    """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')
 
655
    from weavefile import read_weave
 
656
    wf = file(filename, 'rb')
692
657
    w = read_weave(wf)
693
658
    # FIXME: doesn't work on pipes
694
659
    weave_size = wf.tell()
 
660
    print >>out, "weave file size %d bytes" % weave_size
 
661
    print >>out, "weave contains %d versions" % len(w._v)
695
662
 
696
663
    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
 
 
 
664
    print '%6s %6s %8s %40s %20s' % ('ver', 'lines', 'bytes', 'sha1', 'parents')
 
665
    for i in (6, 6, 8, 40, 20):
 
666
        print '-' * i,
 
667
    print
 
668
    for i in range(len(w._v)):
 
669
        text = w.get(i)
 
670
        lines = len(text)
 
671
        bytes = sum((len(a) for a in text))
 
672
        sha1 = w._sha1s[i]
 
673
        print '%6d %6d %8d %40s' % (i, lines, bytes, sha1),
 
674
        for pv in w._v[i]:
 
675
            print pv,
 
676
        print
 
677
        total += bytes
 
678
 
 
679
    print >>out, "versions total %d bytes" % total
 
680
    print >>out, "compression ratio %.3f" % (float(total)/float(weave_size))
710
681
 
711
682
 
712
683
def usage():
810
781
                lasto = origin
811
782
                
812
783
    elif cmd == 'info':
813
 
        weave_info(readit())
814
 
 
815
 
    elif cmd == 'stats':
816
 
        weave_stats(argv[2])
 
784
        weave_info(argv[2], sys.stdout)
817
785
        
818
786
    elif cmd == 'check':
819
787
        w = readit()
820
788
        pb = ProgressBar()
821
789
        w.check(pb)
822
790
        pb.clear()
823
 
        print '%d versions ok' % w.numversions()
824
791
 
825
792
    elif cmd == 'inclusions':
826
793
        w = readit()
828
795
 
829
796
    elif cmd == 'parents':
830
797
        w = readit()
831
 
        print ' '.join(map(str, w._parents[int(argv[3])]))
 
798
        print ' '.join(map(str, w._v[int(argv[3])]))
832
799
 
833
800
    elif cmd == 'plan-merge':
834
801
        w = readit()