/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/revfile.py

  • Committer: mbp at sourcefrog
  • Date: 2005-04-09 04:38:18 UTC
  • Revision ID: mbp@sourcefrog.net-20050409043818-6000f4ab6d40a31a21b99dd7
Revfile:- store and retrieve deltas!mdiff:- work on bytes not lines

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/revfile.py
 
1
#! /usr/bin/env python
 
2
 
 
3
# (C) 2005 Canonical Ltd
 
4
 
 
5
# based on an idea by Matt Mackall
 
6
# modified to squish into bzr by Martin Pool
 
7
 
 
8
# This program is free software; you can redistribute it and/or modify
 
9
# it under the terms of the GNU General Public License as published by
 
10
# the Free Software Foundation; either version 2 of the License, or
 
11
# (at your option) any later version.
 
12
 
 
13
# This program is distributed in the hope that it will be useful,
 
14
# but WITHOUT ANY WARRANTY; without even the implied warranty of
 
15
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
16
# GNU General Public License for more details.
 
17
 
 
18
# You should have received a copy of the GNU General Public License
 
19
# along with this program; if not, write to the Free Software
 
20
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
21
 
 
22
 
 
23
"""Packed file revision storage.
 
24
 
 
25
A Revfile holds the text history of a particular source file, such
 
26
as Makefile.  It can represent a tree of text versions for that
 
27
file, allowing for microbranches within a single repository.
 
28
 
 
29
This is stored on disk as two files: an index file, and a data file.
 
30
The index file is short and always read completely into memory; the
 
31
data file is much longer and only the relevant bits of it,
 
32
identified by the index file, need to be read.
 
33
 
 
34
Each text version is identified by the SHA-1 of the full text of
 
35
that version.  It also has a sequence number within the file.
 
36
 
 
37
The index file has a short header and then a sequence of fixed-length
 
38
records:
 
39
 
 
40
* byte[20]    SHA-1 of text (as binary, not hex)
 
41
* uint32      sequence number this is based on, or -1 for full text
 
42
* uint32      flags: 1=zlib compressed
 
43
* uint32      offset in text file of start
 
44
* uint32      length of compressed delta in text file
 
45
* uint32[3]   reserved
 
46
 
 
47
total 48 bytes.
 
48
 
 
49
The header is also 48 bytes for tidyness and easy calculation.
 
50
 
 
51
Both the index and the text are only ever appended to; a consequence
 
52
is that sequence numbers are stable references.  But not every
 
53
repository in the world will assign the same sequence numbers,
 
54
therefore the SHA-1 is the only universally unique reference.
 
55
 
 
56
This is meant to scale to hold 100,000 revisions of a single file, by
 
57
which time the index file will be ~4.8MB and a bit big to read
 
58
sequentially.
 
59
 
 
60
Some of the reserved fields could be used to implement a (semi?)
 
61
balanced tree indexed by SHA1 so we can much more efficiently find the
 
62
index associated with a particular hash.  For 100,000 revs we would be
 
63
able to find it in about 17 random reads, which is not too bad.
 
64
"""
 
65
 
 
66
 
 
67
# TODO: Something like pread() would make this slightly simpler and
 
68
# perhaps more efficient.
 
69
 
 
70
# TODO: Could also try to mmap things...
 
71
 
 
72
 
 
73
import sys, zlib, struct, mdiff, stat, os, sha
 
74
from binascii import hexlify, unhexlify
 
75
 
 
76
factor = 10
 
77
 
 
78
_RECORDSIZE = 48
 
79
 
 
80
_HEADER = "bzr revfile v1\n"
 
81
_HEADER = _HEADER + ('\xff' * (_RECORDSIZE - len(_HEADER)))
 
82
_NO_RECORD = 0xFFFFFFFFL
 
83
 
 
84
# fields in the index record
 
85
I_SHA = 0
 
86
I_BASE = 1
 
87
I_FLAGS = 2
 
88
I_OFFSET = 3
 
89
I_LEN = 4
 
90
 
 
91
 
 
92
class RevfileError(Exception):
 
93
    pass
 
94
 
 
95
 
 
96
 
 
97
class Revfile:
 
98
    def __init__(self, basename):
 
99
        # TODO: Option to open readonly
 
100
 
 
101
        # TODO: Lock file  while open
 
102
 
 
103
        # TODO: advise of random access
 
104
 
 
105
        self.basename = basename
 
106
        
 
107
        idxname = basename + '.irev'
 
108
        dataname = basename + '.drev'
 
109
 
 
110
        idx_exists = os.path.exists(idxname)
 
111
        data_exists = os.path.exists(dataname)
 
112
 
 
113
        if idx_exists != data_exists:
 
114
            raise RevfileError("half-assed revfile")
 
115
        
 
116
        if not idx_exists:
 
117
            self.idxfile = open(idxname, 'w+b')
 
118
            self.datafile = open(dataname, 'w+b')
 
119
            
 
120
            print 'init empty file'
 
121
            self.idxfile.write(_HEADER)
 
122
            self.idxfile.flush()
 
123
        else:
 
124
            self.idxfile = open(idxname, 'r+b')
 
125
            self.datafile = open(dataname, 'r+b')
 
126
            
 
127
            h = self.idxfile.read(_RECORDSIZE)
 
128
            if h != _HEADER:
 
129
                raise RevfileError("bad header %r in index of %r"
 
130
                                   % (h, self.basename))
 
131
 
 
132
 
 
133
    def revision(self, rev):
 
134
        base = self.index[rev][0]
 
135
        start = self.index[base][1]
 
136
        end = self.index[rev][1] + self.index[rev][2]
 
137
        f = open(self.datafile())
 
138
 
 
139
        f.seek(start)
 
140
        data = f.read(end - start)
 
141
 
 
142
        last = self.index[base][2]
 
143
        text = zlib.decompress(data[:last])
 
144
 
 
145
        for r in range(base + 1, rev + 1):
 
146
            s = self.index[r][2]
 
147
            b = zlib.decompress(data[last:last + s])
 
148
            text = mdiff.bpatch(text, b)
 
149
            last = last + s
 
150
 
 
151
        return text    
 
152
 
 
153
 
 
154
    def _check_index(self, idx):
 
155
        if idx < 0 or idx > len(self):
 
156
            raise RevfileError("invalid index %r" % idx)
 
157
 
 
158
 
 
159
    def find_sha(self, s):
 
160
        assert isinstance(s, str)
 
161
        assert len(s) == 20
 
162
        
 
163
        for idx, idxrec in enumerate(self):
 
164
            if idxrec[I_SHA] == s:
 
165
                return idx
 
166
        else:
 
167
            return _NO_RECORD        
 
168
 
 
169
 
 
170
    def _add_common(self, text_sha, data, flags, base):
 
171
        """Add pre-processed data, can be either full text or delta."""
 
172
        idx = len(self)
 
173
        self.datafile.seek(0, 2)        # to end
 
174
        self.idxfile.seek(0, 2)
 
175
        assert self.idxfile.tell() == _RECORDSIZE * (idx + 1)
 
176
        data_offset = self.datafile.tell()
 
177
 
 
178
        assert isinstance(data, str) # not unicode or anything wierd
 
179
 
 
180
        self.datafile.write(data)
 
181
        self.datafile.flush()
 
182
 
 
183
        assert isinstance(text_sha, str)
 
184
        entry = text_sha
 
185
        entry += struct.pack(">IIII12x", base, flags, data_offset, len(data))
 
186
        assert len(entry) == _RECORDSIZE
 
187
 
 
188
        self.idxfile.write(entry)
 
189
        self.idxfile.flush()
 
190
 
 
191
        return idx
 
192
        
 
193
 
 
194
 
 
195
    def _add_full_text(self, text):
 
196
        """Add a full text to the file.
 
197
 
 
198
        This is not compressed against any reference version.
 
199
 
 
200
        Returns the index for that text."""
 
201
        return self._add_common(sha.new(text).digest(), text, 0, _NO_RECORD)
 
202
 
 
203
 
 
204
    def _add_delta(self, text, base):
 
205
        """Add a text stored relative to a previous text."""
 
206
        self._check_index(base)
 
207
        text_sha = sha.new(text).digest()
 
208
        base_text = self.get(base)
 
209
        data = mdiff.bdiff(base_text, text)
 
210
        return self._add_common(text_sha, data, 0, base)
 
211
 
 
212
 
 
213
    def add(self, text, base=None):
 
214
        # TODO: check it's not already present?
 
215
        assert 0
 
216
 
 
217
        
 
218
    def addrevision(self, text, changeset):
 
219
        t = self.tip()
 
220
        n = t + 1
 
221
 
 
222
        if not n % factor:
 
223
            data = zlib.compress(text)
 
224
            base = n
 
225
        else:
 
226
            prev = self.revision(t)
 
227
            data = zlib.compress(mdiff.bdiff(prev, text))
 
228
            base = self.index[t][0]
 
229
 
 
230
        offset = 0
 
231
        if t >= 0:
 
232
            offset = self.index[t][1] + self.index[t][2]
 
233
 
 
234
        self.index.append((base, offset, len(data), changeset))
 
235
        entry = struct.pack(">llll", base, offset, len(data), changeset)
 
236
 
 
237
        open(self.indexfile(), "a").write(entry)
 
238
        open(self.datafile(), "a").write(data)
 
239
 
 
240
 
 
241
    def get(self, idx):
 
242
        idxrec = self[idx]
 
243
        base = idxrec[I_BASE]
 
244
        if base == _NO_RECORD:
 
245
            text = self._get_full_text(idx, idxrec)
 
246
        else:
 
247
            text = self._get_patched(idx, idxrec)
 
248
 
 
249
        if sha.new(text).digest() != idxrec[I_SHA]:
 
250
            raise RevfileError("corrupt SHA-1 digest on record %d"
 
251
                               % idx)
 
252
 
 
253
        return text
 
254
 
 
255
 
 
256
 
 
257
    def _get_raw(self, idx, idxrec):
 
258
        l = idxrec[I_LEN]
 
259
        if l == 0:
 
260
            return ''
 
261
 
 
262
        self.datafile.seek(idxrec[I_OFFSET])
 
263
 
 
264
        data = self.datafile.read(l)
 
265
        if len(data) != l:
 
266
            raise RevfileError("short read %d of %d "
 
267
                               "getting text for record %d in %r"
 
268
                               % (len(data), l, idx, self.basename))
 
269
 
 
270
        return data
 
271
        
 
272
 
 
273
    def _get_full_text(self, idx, idxrec):
 
274
        assert idxrec[I_FLAGS] == 0
 
275
        assert idxrec[I_BASE] == _NO_RECORD
 
276
 
 
277
        text = self._get_raw(idx, idxrec)
 
278
 
 
279
        return text
 
280
 
 
281
 
 
282
    def _get_patched(self, idx, idxrec):
 
283
        assert idxrec[I_FLAGS] == 0
 
284
        base = idxrec[I_BASE]
 
285
        assert base >= 0
 
286
        assert base < idx    # no loops!
 
287
 
 
288
        base_text = self.get(base)
 
289
        patch = self._get_raw(idx, idxrec)
 
290
 
 
291
        text = mdiff.bpatch(base_text, patch)
 
292
 
 
293
        return text
 
294
 
 
295
 
 
296
 
 
297
    def __len__(self):
 
298
        """Return number of revisions."""
 
299
        l = os.fstat(self.idxfile.fileno())[stat.ST_SIZE]
 
300
        if l % _RECORDSIZE:
 
301
            raise RevfileError("bad length %d on index of %r" % (l, self.basename))
 
302
        if l < _RECORDSIZE:
 
303
            raise RevfileError("no header present in index of %r" % (self.basename))
 
304
        return int(l / _RECORDSIZE) - 1
 
305
 
 
306
 
 
307
    def __getitem__(self, idx):
 
308
        """Index by sequence id returns the index field"""
 
309
        ## TODO: Can avoid seek if we just moved there...
 
310
        self._seek_index(idx)
 
311
        return self._read_next_index()
 
312
 
 
313
 
 
314
    def _seek_index(self, idx):
 
315
        if idx < 0:
 
316
            raise RevfileError("invalid index %r" % idx)
 
317
        self.idxfile.seek((idx + 1) * _RECORDSIZE)
 
318
        
 
319
 
 
320
    def _read_next_index(self):
 
321
        rec = self.idxfile.read(_RECORDSIZE)
 
322
        if not rec:
 
323
            raise IndexError("end of index file")
 
324
        elif len(rec) != _RECORDSIZE:
 
325
            raise RevfileError("short read of %d bytes getting index %d from %r"
 
326
                               % (len(rec), idx, self.basename))
 
327
        
 
328
        return struct.unpack(">20sIIII12x", rec)
 
329
 
 
330
        
 
331
    def dump(self, f=sys.stdout):
 
332
        f.write('%-8s %-40s %-8s %-8s %-8s %-8s\n' 
 
333
                % tuple('idx sha1 base flags offset len'.split()))
 
334
        f.write('-------- ---------------------------------------- ')
 
335
        f.write('-------- -------- -------- --------\n')
 
336
 
 
337
        for i, rec in enumerate(self):
 
338
            f.write("#%-7d %40s " % (i, hexlify(rec[0])))
 
339
            if rec[1] == _NO_RECORD:
 
340
                f.write("(none)   ")
 
341
            else:
 
342
                f.write("#%-7d " % rec[1])
 
343
                
 
344
            f.write("%8x %8d %8d\n" % (rec[2], rec[3], rec[4]))
 
345
        
 
346
 
 
347
 
 
348
def main(argv):
 
349
    r = Revfile("testrev")
 
350
 
 
351
    try:
 
352
        cmd = argv[1]
 
353
    except IndexError:
 
354
        sys.stderr.write("usage: revfile dump\n"
 
355
                         "       revfile add\n"
 
356
                         "       revfile add-delta BASE\n"
 
357
                         "       revfile get IDX\n"
 
358
                         "       revfile find-sha HEX\n")
 
359
        return 1
 
360
        
 
361
 
 
362
    if cmd == 'add':
 
363
        new_idx = r._add_full_text(sys.stdin.read())
 
364
        print 'added idx %d' % new_idx
 
365
    elif cmd == 'add-delta':
 
366
        new_idx = r._add_delta(sys.stdin.read(), int(argv[2]))
 
367
        print 'added idx %d' % new_idx
 
368
    elif cmd == 'dump':
 
369
        r.dump()
 
370
    elif cmd == 'get':
 
371
        try:
 
372
            idx = int(argv[2])
 
373
        except IndexError:
 
374
            sys.stderr.write("usage: revfile get IDX\n")
 
375
            return 1
 
376
 
 
377
        if idx < 0 or idx >= len(r):
 
378
            sys.stderr.write("invalid index %r\n" % idx)
 
379
            return 1
 
380
 
 
381
        sys.stdout.write(r.get(idx))
 
382
    elif cmd == 'find-sha':
 
383
        try:
 
384
            s = unhexlify(argv[2])
 
385
        except IndexError:
 
386
            sys.stderr.write("usage: revfile find-sha HEX\n")
 
387
            return 1
 
388
 
 
389
        idx = r.find_sha(s)
 
390
        if idx == _NO_RECORD:
 
391
            sys.stderr.write("no such record\n")
 
392
            return 1
 
393
        else:
 
394
            print idx
 
395
            
 
396
    else:
 
397
        sys.stderr.write("unknown command %r\n" % cmd)
 
398
        return 1
 
399
    
 
400
 
 
401
if __name__ == '__main__':
 
402
    import sys
 
403
    sys.exit(main(sys.argv) or 0)