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 dulwich/pack.py
- browse files at revision 0.211.35
- compare with another revision
- download diff
- download tarball
- view history from revision 0.211.35
- Committer: Jelmer Vernooij
- Date: 2008-12-11 10:52:43 UTC
- mto: (0.215.1 trunk)
- mto: This revision was merged to the branch mainline in revision 6960.
- Revision ID: jelmer@samba.org-20081211105243-dokx6i1dofwnlrrm
Add simple pack dump utility.
- files added:
- bin/dumppack
- files removed:
- dulwich/docs
- foreign
- tests
- files modified:
added
removed
dulwich/pack.py
35
35
36
36
from collections import defaultdict
37
37
import hashlib
38
from itertools import imap, izip
39
38
import mmap
40
39
import os
41
import sha
42
40
import struct
43
41
import sys
44
import zlib
45
46
from objects import (
47
ShaFile,
48
)
49
from errors import ApplyDeltaError
50
42
51
43
supports_mmap_offset = (sys.version_info[0] >= 3 or
52
44
(sys.version_info[0] == 2 and sys.version_info[1] >= 6))
53
45
54
55
def take_msb_bytes(map, offset):
56
ret = []
57
while len(ret) == 0 or ret[-1] & 0x80:
58
ret.append(ord(map[offset]))
59
offset += 1
60
return ret
61
62
63
def read_zlib(data, offset, dec_size):
64
obj = zlib.decompressobj()
65
x = ""
66
fed = 0
67
while obj.unused_data == "":
68
base = offset+fed
69
add = data[base:base+1024]
70
fed += len(add)
71
x += obj.decompress(add)
72
assert len(x) == dec_size
73
comp_len = fed-len(obj.unused_data)
74
return x, comp_len
75
76
77
def iter_sha1(iter):
78
sha = hashlib.sha1()
79
for name in iter:
80
sha.update(name)
81
return sha.hexdigest()
82
46
from objects import (ShaFile,
47
_decompress,
48
)
83
49
84
50
def hex_to_sha(hex):
85
"""Convert a hex string to a binary sha string."""
86
51
ret = ""
87
52
for i in range(0, len(hex), 2):
88
53
ret += chr(int(hex[i:i+2], 16))
89
54
return ret
90
55
91
92
56
def sha_to_hex(sha):
93
"""Convert a binary sha string to a hex sha string."""
94
57
ret = ""
95
58
for i in sha:
96
59
ret += "%02x" % ord(i)
97
60
return ret
98
61
99
100
62
MAX_MMAP_SIZE = 256 * 1024 * 1024
101
63
102
64
def simple_mmap(f, offset, size, access=mmap.ACCESS_READ):
103
"""Simple wrapper for mmap() which always supports the offset parameter.
104
105
:param f: File object.
106
:param offset: Offset in the file, from the beginning of the file.
107
:param size: Size of the mmap'ed area
108
:param access: Access mechanism.
109
:return: MMAP'd area.
110
"""
111
65
if offset+size > MAX_MMAP_SIZE and not supports_mmap_offset:
112
66
raise AssertionError("%s is larger than 256 meg, and this version "
113
67
"of Python does not support the offset argument to mmap().")
138
92
return ArraySkipper(mem, offset)
139
93
140
94
141
def resolve_object(offset, type, obj, get_ref, get_offset):
142
"""Resolve an object, possibly resolving deltas when necessary."""
143
if not type in (6, 7): # Not a delta
144
return type, obj
145
146
if type == 6: # offset delta
147
(delta_offset, delta) = obj
148
assert isinstance(delta_offset, int)
149
assert isinstance(delta, str)
150
offset = offset-delta_offset
151
type, base_obj = get_offset(offset)
152
assert isinstance(type, int)
153
elif type == 7: # ref delta
154
(basename, delta) = obj
155
assert isinstance(basename, str) and len(basename) == 20
156
assert isinstance(delta, str)
157
type, base_obj = get_ref(basename)
158
assert isinstance(type, int)
159
type, base_text = resolve_object(offset, type, base_obj, get_ref, get_offset)
160
return type, apply_delta(base_text, delta)
95
def multi_ord(map, start, count):
96
value = 0
97
for i in range(count):
98
value = value * 0x100 + ord(map[start+i])
99
return value
161
100
162
101
163
102
class PackIndex(object):
174
113
the start and end offset and then bisect in to find if the value is present.
175
114
"""
176
115
116
PACK_INDEX_HEADER_SIZE = 0x100 * 4
117
sha_bytes = 20
118
record_size = sha_bytes + 4
119
177
120
def __init__(self, filename):
178
121
"""Create a pack index object.
179
122
181
124
it whenever required.
182
125
"""
183
126
self._filename = filename
127
assert os.path.exists(filename), "%s is not a pack index" % filename
184
128
# Take the size now, so it can be checked each time we map the file to
185
129
# ensure that it hasn't changed.
186
130
self._size = os.path.getsize(filename)
197
141
self._crc32_table_offset = self._name_table_offset + 20 * len(self)
198
142
self._pack_offset_table_offset = self._crc32_table_offset + 4 * len(self)
199
143
200
def __eq__(self, other):
201
if type(self) != type(other):
202
return False
203
204
if self._fan_out_table != other._fan_out_table:
205
return False
206
207
for (name1, _, _), (name2, _, _) in izip(self.iterentries(), other.iterentries()):
208
if name1 != name2:
209
return False
210
return True
211
212
144
def close(self):
213
145
self._file.close()
214
146
223
155
CRC32 checksum (if known)."""
224
156
if self.version == 1:
225
157
(offset, name) = struct.unpack_from(">L20s", self._contents,
226
(0x100 * 4) + (i * 24))
158
self.PACK_INDEX_HEADER_SIZE + (i * self.record_size))
227
159
return (name, offset, None)
228
160
else:
229
161
return (self._unpack_name(i), self._unpack_offset(i),
250
182
return struct.unpack_from(">L", self._contents,
251
183
self._crc32_table_offset + i * 4)[0]
252
184
253
def __iter__(self):
254
return imap(sha_to_hex, self._itersha())
255
256
def _itersha(self):
257
for i in range(len(self)):
258
yield self._unpack_name(i)
259
260
def objects_sha1(self):
261
return iter_sha1(self._itersha())
262
263
185
def iterentries(self):
264
186
"""Iterate over the entries in this pack index.
265
187
300
222
size = os.path.getsize(self._filename)
301
223
assert size == self._size, "Pack index %s has changed size, I don't " \
302
224
"like that" % self._filename
303
if len(sha) == 40:
304
sha = hex_to_sha(sha)
305
225
return self._object_index(sha)
306
226
307
def _object_index(self, sha):
227
def _object_index(self, hexsha):
308
228
"""See object_index"""
309
idx = ord(sha[0])
310
if idx == 0:
311
start = 0
312
else:
313
start = self._fan_out_table[idx-1]
314
end = self._fan_out_table[idx]
315
assert start <= end
316
while start <= end:
229
sha = hex_to_sha(hexsha)
230
start = self._fan_out_table[ord(sha[0])-1]
231
end = self._fan_out_table[ord(sha[0])]
232
while start < end:
317
233
i = (start + end)/2
318
234
file_sha = self._unpack_name(i)
319
if file_sha < sha:
235
if file_sha == sha:
236
return self._unpack_offset(i)
237
elif file_sha < sha:
320
238
start = i + 1
321
elif file_sha > sha:
239
else:
322
240
end = i - 1
323
else:
324
return self._unpack_offset(i)
325
241
return None
326
242
327
243
364
280
self._filename = filename
365
281
assert os.path.exists(filename), "%s is not a packfile" % filename
366
282
self._size = os.path.getsize(filename)
367
self._header_size = 12
368
assert self._size >= self._header_size, "%s is too small for a packfile" % filename
369
283
self._read_header()
370
284
371
285
def _read_header(self):
393
307
finally:
394
308
f.close()
395
309
396
def iterobjects(self):
397
offset = self._header_size
398
f = open(self._filename, 'rb')
399
for i in range(len(self)):
400
map = simple_mmap(f, offset, self._size-offset)
401
(type, obj, total_size) = self._unpack_object(map)
402
yield offset, type, obj
403
offset += total_size
404
f.close()
405
406
def iterentries(self, ext_resolve_ref=None):
407
found = {}
408
at = {}
409
postponed = defaultdict(list)
410
class Postpone(Exception):
411
"""Raised to postpone delta resolving."""
412
413
def get_ref_text(sha):
414
if sha in found:
415
return found[sha]
416
if ext_resolve_ref:
417
try:
418
return ext_resolve_ref(sha)
419
except KeyError:
420
pass
421
raise Postpone, (sha, )
422
todo = list(self.iterobjects())
423
while todo:
424
(offset, type, obj) = todo.pop(0)
425
at[offset] = (type, obj)
426
assert isinstance(offset, int)
427
assert isinstance(type, int)
428
assert isinstance(obj, tuple) or isinstance(obj, str)
429
try:
430
type, obj = resolve_object(offset, type, obj, get_ref_text,
431
at.__getitem__)
432
except Postpone, (sha, ):
433
postponed[sha].append((offset, type, obj))
434
else:
435
shafile = ShaFile.from_raw_string(type, obj)
436
sha = shafile.sha().digest()
437
found[sha] = (type, obj)
438
yield sha, offset, shafile.crc32()
439
todo += postponed.get(sha, [])
440
if postponed:
441
raise KeyError([sha_to_hex(h) for h in postponed.keys()])
442
443
def sorted_entries(self, resolve_ext_ref=None):
444
ret = list(self.iterentries(resolve_ext_ref))
445
ret.sort()
446
return ret
447
448
def create_index_v1(self, filename):
449
entries = self.sorted_entries()
450
write_pack_index_v1(filename, entries, self.calculate_checksum())
451
452
def create_index_v2(self, filename):
453
entries = self.sorted_entries()
454
write_pack_index_v2(filename, entries, self.calculate_checksum())
455
456
def get_stored_checksum(self):
457
return self._stored_checksum
458
459
310
def check(self):
460
return (self.calculate_checksum() == self.get_stored_checksum())
311
return (self.calculate_checksum() == self._stored_checksum)
461
312
462
313
def get_object_at(self, offset):
463
314
"""Given an offset in to the packfile return the object that is there.
465
316
Using the associated index the location of an object can be looked up, and
466
317
then the packfile can be asked directly for that object using this
467
318
function.
319
320
Currently only non-delta objects are supported.
468
321
"""
469
assert isinstance(offset, long) or isinstance(offset, int),\
470
"offset was %r" % offset
471
assert offset >= self._header_size
322
assert isinstance(offset, long) or isinstance(offset, int)
472
323
size = os.path.getsize(self._filename)
473
324
assert size == self._size, "Pack data %s has changed size, I don't " \
474
325
"like that" % self._filename
475
326
f = open(self._filename, 'rb')
476
327
try:
477
328
map = simple_mmap(f, offset, size-offset)
478
return self._unpack_object(map)[:2]
329
return self._get_object_at(map)
479
330
finally:
480
331
f.close()
481
332
482
def _unpack_object(self, map):
483
bytes = take_msb_bytes(map, 0)
484
type = (bytes[0] >> 4) & 0x07
485
size = bytes[0] & 0x0f
486
for i, byte in enumerate(bytes[1:]):
487
size += (byte & 0x7f) << ((i * 7) + 4)
488
raw_base = len(bytes)
489
if type == 6: # offset delta
490
bytes = take_msb_bytes(map, raw_base)
491
assert not (bytes[-1] & 0x80)
492
delta_base_offset = bytes[0] & 0x7f
493
for byte in bytes[1:]:
494
delta_base_offset += 1
495
delta_base_offset <<= 7
496
delta_base_offset += (byte & 0x7f)
497
raw_base+=len(bytes)
498
uncomp, comp_len = read_zlib(map, raw_base, size)
499
assert size == len(uncomp)
500
return type, (delta_base_offset, uncomp), comp_len+raw_base
501
elif type == 7: # ref delta
502
basename = map[raw_base:raw_base+20]
503
uncomp, comp_len = read_zlib(map, raw_base+20, size)
504
assert size == len(uncomp)
505
return type, (basename, uncomp), comp_len+raw_base+20
506
else:
507
uncomp, comp_len = read_zlib(map, raw_base, size)
508
assert len(uncomp) == size
509
return type, uncomp, comp_len+raw_base
333
def _get_object_at(self, map):
334
first_byte = ord(map[0])
335
sign_extend = first_byte & 0x80
336
type = (first_byte >> 4) & 0x07
337
size = first_byte & 0x0f
338
cur_offset = 0
339
while sign_extend > 0:
340
byte = ord(map[cur_offset+1])
341
sign_extend = byte & 0x80
342
size_part = byte & 0x7f
343
size += size_part << ((cur_offset * 7) + 4)
344
cur_offset += 1
345
raw_base = cur_offset+1
346
# The size is the inflated size, so we have no idea what the deflated size
347
# is, so for now give it as much as we have. It should really iterate
348
# feeding it more data if it doesn't decompress, but as we have the whole
349
# thing then just use it.
350
raw = map[raw_base:]
351
uncomp = _decompress(raw)
352
obj = ShaFile.from_raw_string(type, uncomp)
353
return obj
510
354
511
355
512
356
class SHA1Writer(object):
519
363
self.sha1.update(data)
520
364
self.f.write(data)
521
365
522
def write_sha(self):
366
def close(self):
523
367
sha = self.sha1.digest()
524
368
assert len(sha) == 20
525
369
self.f.write(sha)
526
return sha
527
528
def close(self):
529
sha = self.write_sha()
530
370
self.f.close()
531
371
return sha
532
372
533
def tell(self):
534
return self.f.tell()
535
536
537
def write_pack_object(f, type, object):
538
"""Write pack object to a file.
539
540
:param f: File to write to
541
:param o: Object to write
542
"""
543
ret = f.tell()
544
if type == 6: # ref delta
545
(delta_base_offset, object) = object
546
elif type == 7: # offset delta
547
(basename, object) = object
548
size = len(object)
549
c = (type << 4) | (size & 15)
550
size >>= 4
551
while size:
552
f.write(chr(c | 0x80))
553
c = size & 0x7f
554
size >>= 7
555
f.write(chr(c))
556
if type == 6: # offset delta
557
ret = [delta_base_offset & 0x7f]
558
delta_base_offset >>= 7
559
while delta_base_offset:
560
delta_base_offset -= 1
561
ret.insert(0, 0x80 | (delta_base_offset & 0x7f))
562
delta_base_offset >>= 7
563
f.write("".join([chr(x) for x in ret]))
564
elif type == 7: # ref delta
565
assert len(basename) == 20
566
f.write(basename)
567
f.write(zlib.compress(object))
568
return f.tell()
569
570
571
def write_pack(filename, objects, num_objects):
572
f = open(filename + ".pack", 'w')
573
try:
574
entries, data_sum = write_pack_data(f, objects, num_objects)
575
except:
576
f.close()
577
entries.sort()
578
write_pack_index_v2(filename + ".idx", entries, data_sum)
579
580
581
def write_pack_data(f, objects, num_objects):
373
374
def write_pack(filename, objects):
582
375
"""Write a new pack file.
583
376
584
377
:param filename: The filename of the new pack file.
585
378
:param objects: List of objects to write.
586
379
:return: List with (name, offset, crc32 checksum) entries, pack checksum
587
380
"""
381
f = open(filename, 'w')
588
382
entries = []
589
383
f = SHA1Writer(f)
590
384
f.write("PACK") # Pack header
591
385
f.write(struct.pack(">L", 2)) # Pack version
592
f.write(struct.pack(">L", num_objects)) # Number of objects in pack
386
f.write(struct.pack(">L", len(objects))) # Number of objects in pack
593
387
for o in objects:
594
sha1 = o.sha().digest()
595
crc32 = o.crc32()
596
# FIXME: Delta !
597
t, o = o.as_raw_string()
598
offset = write_pack_object(f, t, o)
599
entries.append((sha1, offset, crc32))
600
return entries, f.write_sha()
388
pass # FIXME: Write object
389
return entries, f.close()
601
390
602
391
603
392
def write_pack_index_v1(filename, entries, pack_checksum):
608
397
crc32_checksum.
609
398
:param pack_checksum: Checksum of the pack file.
610
399
"""
400
# Sort entries first
401
402
entries = sorted(entries)
611
403
f = open(filename, 'w')
612
404
f = SHA1Writer(f)
613
405
fan_out_table = defaultdict(lambda: 0)
624
416
f.close()
625
417
626
418
627
def apply_delta(src_buf, delta):
628
"""Based on the similar function in git's patch-delta.c."""
629
assert isinstance(src_buf, str), "was %r" % (src_buf,)
630
assert isinstance(delta, str)
631
out = ""
632
def pop(delta):
633
ret = delta[0]
634
delta = delta[1:]
635
return ord(ret), delta
636
def get_delta_header_size(delta):
637
size = 0
638
i = 0
639
while delta:
640
cmd, delta = pop(delta)
641
size |= (cmd & ~0x80) << i
642
i += 7
643
if not cmd & 0x80:
644
break
645
return size, delta
646
src_size, delta = get_delta_header_size(delta)
647
dest_size, delta = get_delta_header_size(delta)
648
assert src_size == len(src_buf)
649
while delta:
650
cmd, delta = pop(delta)
651
if cmd & 0x80:
652
cp_off = 0
653
for i in range(4):
654
if cmd & (1 << i):
655
x, delta = pop(delta)
656
cp_off |= x << (i * 8)
657
cp_size = 0
658
for i in range(3):
659
if cmd & (1 << (4+i)):
660
x, delta = pop(delta)
661
cp_size |= x << (i * 8)
662
if cp_size == 0:
663
cp_size = 0x10000
664
if (cp_off + cp_size < cp_size or
665
cp_off + cp_size > src_size or
666
cp_size > dest_size):
667
break
668
out += src_buf[cp_off:cp_off+cp_size]
669
elif cmd != 0:
670
out += delta[:cmd]
671
delta = delta[cmd:]
672
else:
673
raise ApplyDeltaError("Invalid opcode 0")
674
675
if delta != "":
676
raise ApplyDeltaError("delta not empty: %r" % delta)
677
678
if dest_size != len(out):
679
raise ApplyDeltaError("dest size incorrect")
680
681
return out
682
683
684
419
def write_pack_index_v2(filename, entries, pack_checksum):
685
420
"""Write a new pack index file.
686
421
689
424
crc32_checksum.
690
425
:param pack_checksum: Checksum of the pack file.
691
426
"""
427
# Sort entries first
428
entries = sorted(entries)
692
429
f = open(filename, 'w')
693
430
f = SHA1Writer(f)
694
f.write('\377tOc') # Magic!
431
f.write('\377tOc')
695
432
f.write(struct.pack(">L", 2))
696
433
fan_out_table = defaultdict(lambda: 0)
697
434
for (name, offset, entry_checksum) in entries:
703
440
for (name, offset, entry_checksum) in entries:
704
441
f.write(name)
705
442
for (name, offset, entry_checksum) in entries:
706
f.write(struct.pack(">l", entry_checksum))
443
f.write(struct.pack(">L", entry_checksum))
707
444
for (name, offset, entry_checksum) in entries:
708
445
# FIXME: handle if MSBit is set in offset
709
446
f.write(struct.pack(">L", offset))
712
449
f.write(pack_checksum)
713
450
f.close()
714
451
715
716
class Pack(object):
717
718
def __init__(self, basename):
719
self._basename = basename
720
self._data_path = self._basename + ".pack"
721
self._idx_path = self._basename + ".idx"
722
self._data = None
723
self._idx = None
724
725
def name(self):
726
return self.idx.objects_sha1()
727
728
@property
729
def data(self):
730
if self._data is None:
731
self._data = PackData(self._data_path)
732
assert len(self.idx) == len(self._data)
733
assert self.idx.get_stored_checksums()[0] == self._data.get_stored_checksum()
734
return self._data
735
736
@property
737
def idx(self):
738
if self._idx is None:
739
self._idx = PackIndex(self._idx_path)
740
return self._idx
741
742
def close(self):
743
if self._data is not None:
744
self._data.close()
745
self.idx.close()
746
747
def __eq__(self, other):
748
return type(self) == type(other) and self.idx == other.idx
749
750
def __len__(self):
751
"""Number of entries in this pack."""
752
return len(self.idx)
753
754
def __repr__(self):
755
return "Pack(%r)" % self._basename
756
757
def __iter__(self):
758
"""Iterate over all the sha1s of the objects in this pack."""
759
return iter(self.idx)
760
761
def check(self):
762
return self.idx.check() and self.data.check()
763
764
def get_stored_checksum(self):
765
return self.data.get_stored_checksum()
766
767
def __contains__(self, sha1):
768
"""Check whether this pack contains a particular SHA1."""
769
return (self.idx.object_index(sha1) is not None)
770
771
def get_raw(self, sha1, resolve_ref=None):
772
if resolve_ref is None:
773
resolve_ref = self.get_raw
774
offset = self.idx.object_index(sha1)
775
if offset is None:
776
raise KeyError(sha1)
777
778
type, obj = self.data.get_object_at(offset)
779
assert isinstance(offset, int)
780
return resolve_object(offset, type, obj, resolve_ref,
781
self.data.get_object_at)
782
783
def __getitem__(self, sha1):
784
"""Retrieve the specified SHA1."""
785
type, uncomp = self.get_raw(sha1)
786
return ShaFile.from_raw_string(type, uncomp)
787
788
def iterobjects(self):
789
for offset, type, obj in self.data.iterobjects():
790
assert isinstance(offset, int)
791
yield ShaFile.from_raw_string(
792
*resolve_object(offset, type, obj, self.get_raw,
793
self.data.get_object_at))
794
795
796
def load_packs(path):
797
if not os.path.exists(path):
798
return
799
for name in os.listdir(path):
800
if name.startswith("pack-") and name.endswith(".pack"):
801
yield Pack(os.path.join(path, name[:-len(".pack")]))
Loggerhead is a web-based interface for Breezy
Version: 2.0.2.dev0