← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/revfile.py

  • Committer: mbp at sourcefrog
  • Date: 2005-04-09 06:36:40 UTC
  • Revision ID: mbp@sourcefrog.net-20050409063640-728d43dff50e91d8c09c83e3
update rsync exclude patterns

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/revfile.py
67
67
something faster than difflib, which is after all pure Python.
68
68
Another approach is to just store the gzipped full text of big files,
69
69
though perhaps that's too perverse?
70
 
 
71
 
The iter method here will generally read through the whole index file
72
 
in one go.  With readahead in the kernel and python/libc (typically
73
 
128kB) this means that there should be no seeks and often only one
74
 
read() call to get everything into memory.
75
70
"""
76
71
 
77
72
 
89
84
# if there are gaps and that can happen if we're interrupted while
90
85
# writing to the datafile.  Overlapping would be very bad though.
91
86
 
92
 
# TODO: Shouldn't need to lock if we always write in append mode and
93
 
# then ftell after writing to see where it went.  In any case we
94
 
# assume the whole branch is protected by a lock.
 
87
 
95
88
 
96
89
import sys, zlib, struct, mdiff, stat, os, sha
97
90
from binascii import hexlify, unhexlify
98
91
 
 
92
factor = 10
 
93
 
99
94
_RECORDSIZE = 48
100
95
 
101
96
_HEADER = "bzr revfile v1\n"
112
107
FL_GZIP = 1
113
108
 
114
109
# maximum number of patches in a row before recording a whole text.
115
 
CHAIN_LIMIT = 10
 
110
CHAIN_LIMIT = 50
116
111
 
117
112
 
118
113
class RevfileError(Exception):
121
116
class LimitHitException(Exception):
122
117
    pass
123
118
 
124
 
class Revfile(object):
125
 
    def __init__(self, basename, mode):
 
119
class Revfile:
 
120
    def __init__(self, basename):
 
121
        # TODO: Option to open readonly
 
122
 
126
123
        # TODO: Lock file  while open
127
124
 
128
125
        # TODO: advise of random access
129
126
 
130
127
        self.basename = basename
131
 
 
132
 
        if mode not in ['r', 'w']:
133
 
            raise RevfileError("invalid open mode %r" % mode)
134
 
        self.mode = mode
135
128
        
136
129
        idxname = basename + '.irev'
137
130
        dataname = basename + '.drev'
143
136
            raise RevfileError("half-assed revfile")
144
137
        
145
138
        if not idx_exists:
146
 
            if mode == 'r':
147
 
                raise RevfileError("Revfile %r does not exist" % basename)
148
 
            
149
139
            self.idxfile = open(idxname, 'w+b')
150
140
            self.datafile = open(dataname, 'w+b')
151
141
            
 
142
            print 'init empty file'
152
143
            self.idxfile.write(_HEADER)
153
144
            self.idxfile.flush()
154
145
        else:
155
 
            if mode == 'r':
156
 
                diskmode = 'rb'
157
 
            else:
158
 
                diskmode = 'r+b'
159
 
                
160
 
            self.idxfile = open(idxname, diskmode)
161
 
            self.datafile = open(dataname, diskmode)
 
146
            self.idxfile = open(idxname, 'r+b')
 
147
            self.datafile = open(dataname, 'r+b')
162
148
            
163
149
            h = self.idxfile.read(_RECORDSIZE)
164
150
            if h != _HEADER:
170
156
        if idx < 0 or idx > len(self):
171
157
            raise RevfileError("invalid index %r" % idx)
172
158
 
173
 
    def _check_write(self):
174
 
        if self.mode != 'w':
175
 
            raise RevfileError("%r is open readonly" % self.basename)
176
 
 
177
159
 
178
160
    def find_sha(self, s):
179
161
        assert isinstance(s, str)
216
198
        assert self.idxfile.tell() == _RECORDSIZE * (idx + 1)
217
199
        data_offset = self.datafile.tell()
218
200
 
219
 
        assert isinstance(data, str) # not unicode or anything weird
 
201
        assert isinstance(data, str) # not unicode or anything wierd
220
202
 
221
203
        self.datafile.write(data)
222
204
        self.datafile.flush()
242
224
        return self._add_compressed(text_sha, text, _NO_RECORD, compress)
243
225
 
244
226
 
245
 
    # NOT USED
246
 
    def _choose_base(self, seed, base):
247
 
        while seed & 3 == 3:
248
 
            if base == _NO_RECORD:
249
 
                return _NO_RECORD
250
 
            idxrec = self[base]
251
 
            if idxrec[I_BASE] == _NO_RECORD:
252
 
                return base
253
 
 
254
 
            base = idxrec[I_BASE]
255
 
            seed >>= 2
256
 
                
257
 
        return base        # relative to this full text
258
 
        
259
 
 
260
 
 
261
227
    def _add_delta(self, text, text_sha, base, compress):
262
228
        """Add a text stored relative to a previous text."""
263
229
        self._check_index(base)
264
 
 
 
230
        
265
231
        try:
266
 
            base_text = self.get(base, CHAIN_LIMIT)
 
232
            base_text = self.get(base, recursion_limit=CHAIN_LIMIT)
267
233
        except LimitHitException:
268
234
            return self._add_full_text(text, text_sha, compress)
269
235
        
270
236
        data = mdiff.bdiff(base_text, text)
271
 
 
272
 
 
273
 
        if True: # paranoid early check for bad diff
274
 
            result = mdiff.bpatch(base_text, data)
275
 
            assert result == text
276
 
            
277
237
        
278
238
        # If the delta is larger than the text, we might as well just
279
239
        # store the text.  (OK, the delta might be more compressible,
285
245
            return self._add_compressed(text_sha, data, base, compress)
286
246
 
287
247
 
288
 
    def add(self, text, base=None, compress=True):
 
248
    def add(self, text, base=_NO_RECORD, compress=True):
289
249
        """Add a new text to the revfile.
290
250
 
291
251
        If the text is already present them its existing id is
299
259
        only be used if it would be a size win and if the existing
300
260
        base is not at too long of a delta chain already.
301
261
        """
302
 
        if base == None:
303
 
            base = _NO_RECORD
304
 
        
305
 
        self._check_write()
306
 
        
307
262
        text_sha = sha.new(text).digest()
308
263
 
309
264
        idx = self.find_sha(text_sha)
312
267
            # it's the same, in case someone ever breaks SHA-1.
313
268
            return idx                  # already present
314
269
        
315
 
        # base = self._choose_base(ord(text_sha[0]), base)
316
 
 
317
270
        if base == _NO_RECORD:
318
271
            return self._add_full_text(text, text_sha, compress)
319
272
        else:
338
291
            text = self._get_patched(idx, idxrec, recursion_limit)
339
292
 
340
293
        if sha.new(text).digest() != idxrec[I_SHA]:
341
 
            raise RevfileError("corrupt SHA-1 digest on record %d in %s"
342
 
                               % (idx, self.basename))
 
294
            raise RevfileError("corrupt SHA-1 digest on record %d"
 
295
                               % idx)
343
296
 
344
297
        return text
345
298
 
412
365
        """Index by sequence id returns the index field"""
413
366
        ## TODO: Can avoid seek if we just moved there...
414
367
        self._seek_index(idx)
415
 
        idxrec = self._read_next_index()
416
 
        if idxrec == None:
417
 
            raise IndexError("no index %d" % idx)
418
 
        else:
419
 
            return idxrec
 
368
        return self._read_next_index()
420
369
 
421
370
 
422
371
    def _seek_index(self, idx):
423
372
        if idx < 0:
424
373
            raise RevfileError("invalid index %r" % idx)
425
374
        self.idxfile.seek((idx + 1) * _RECORDSIZE)
426
 
 
427
 
 
428
 
 
429
 
    def __iter__(self):
430
 
        """Read back all index records.
431
 
 
432
 
        Do not seek the index file while this is underway!"""
433
 
        ## sys.stderr.write(" ** iter called ** \n")
434
 
        self._seek_index(0)
435
 
        while True:
436
 
            idxrec = self._read_next_index()
437
 
            if not idxrec:
438
 
                break
439
 
            yield idxrec
440
375
        
441
376
 
442
377
    def _read_next_index(self):
443
378
        rec = self.idxfile.read(_RECORDSIZE)
444
379
        if not rec:
445
 
            return None
 
380
            raise IndexError("end of index file")
446
381
        elif len(rec) != _RECORDSIZE:
447
382
            raise RevfileError("short read of %d bytes getting index %d from %r"
448
383
                               % (len(rec), idx, self.basename))
478
413
        for idx in range(len(self)):
479
414
            t += len(self.get(idx))
480
415
        return t
481
 
 
482
 
 
483
 
    def check(self, pb=None):
484
 
        """Extract every version and check its hash."""
485
 
        total = len(self)
486
 
        for i in range(total):
487
 
            if pb:
488
 
                pb.update("check revision", i, total)
489
 
            # the get method implicitly checks the SHA-1
490
 
            self.get(i)
491
 
        if pb:
492
 
            pb.clear()
493
416
        
494
417
 
495
418
 
496
419
def main(argv):
 
420
    r = Revfile("testrev")
 
421
 
497
422
    try:
498
423
        cmd = argv[1]
499
 
        filename = argv[2]
500
424
    except IndexError:
501
 
        sys.stderr.write("usage: revfile dump REVFILE\n"
502
 
                         "       revfile add REVFILE < INPUT\n"
503
 
                         "       revfile add-delta REVFILE BASE < INPUT\n"
504
 
                         "       revfile add-series REVFILE BASE FILE...\n"
505
 
                         "       revfile get REVFILE IDX\n"
506
 
                         "       revfile find-sha REVFILE HEX\n"
507
 
                         "       revfile total-text-size REVFILE\n"
508
 
                         "       revfile last REVFILE\n")
 
425
        sys.stderr.write("usage: revfile dump\n"
 
426
                         "       revfile add\n"
 
427
                         "       revfile add-delta BASE\n"
 
428
                         "       revfile get IDX\n"
 
429
                         "       revfile find-sha HEX\n"
 
430
                         "       revfile total-text-size\n"
 
431
                         "       revfile last\n")
509
432
        return 1
510
433
 
511
 
    if filename.endswith('.drev') or filename.endswith('.irev'):
512
 
        filename = filename[:-5]
513
 
 
514
 
    def rw():
515
 
        return Revfile(filename, 'w')
516
 
 
517
 
    def ro():
518
 
        return Revfile(filename, 'r')
519
 
 
520
434
    if cmd == 'add':
521
 
        print rw().add(sys.stdin.read())
 
435
        new_idx = r.add(sys.stdin.read())
 
436
        print new_idx
522
437
    elif cmd == 'add-delta':
523
 
        print rw().add(sys.stdin.read(), int(argv[3]))
524
 
    elif cmd == 'add-series':
525
 
        r = rw()
526
 
        rev = int(argv[3])
527
 
        for fn in argv[4:]:
528
 
            print rev
529
 
            rev = r.add(file(fn).read(), rev)
 
438
        new_idx = r.add(sys.stdin.read(), int(argv[2]))
 
439
        print new_idx
530
440
    elif cmd == 'dump':
531
 
        ro().dump()
 
441
        r.dump()
532
442
    elif cmd == 'get':
533
443
        try:
534
 
            idx = int(argv[3])
 
444
            idx = int(argv[2])
535
445
        except IndexError:
536
 
            sys.stderr.write("usage: revfile get FILE IDX\n")
 
446
            sys.stderr.write("usage: revfile get IDX\n")
537
447
            return 1
538
448
 
539
 
        r = ro()
540
 
 
541
449
        if idx < 0 or idx >= len(r):
542
450
            sys.stderr.write("invalid index %r\n" % idx)
543
451
            return 1
545
453
        sys.stdout.write(r.get(idx))
546
454
    elif cmd == 'find-sha':
547
455
        try:
548
 
            s = unhexlify(argv[3])
 
456
            s = unhexlify(argv[2])
549
457
        except IndexError:
550
 
            sys.stderr.write("usage: revfile find-sha FILE HEX\n")
 
458
            sys.stderr.write("usage: revfile find-sha HEX\n")
551
459
            return 1
552
460
 
553
 
        idx = ro().find_sha(s)
 
461
        idx = r.find_sha(s)
554
462
        if idx == _NO_RECORD:
555
463
            sys.stderr.write("no such record\n")
556
464
            return 1
557
465
        else:
558
466
            print idx
559
467
    elif cmd == 'total-text-size':
560
 
        print ro().total_text_size()
 
468
        print r.total_text_size()
561
469
    elif cmd == 'last':
562
 
        print len(ro())-1
563
 
    elif cmd == 'check':
564
 
        import bzrlib.progress
565
 
        pb = bzrlib.progress.ProgressBar()
566
 
        ro().check(pb)
 
470
        print len(r)-1
567
471
    else:
568
472
        sys.stderr.write("unknown command %r\n" % cmd)
569
473
        return 1