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.50
- compare with another revision
- download diff
- download tarball
- view history from revision 0.211.50
- Committer: Jelmer Vernooij
- Date: 2008-12-12 15:37:07 UTC
- mto: (0.215.1 trunk)
- mto: This revision was merged to the branch mainline in revision 6960.
- Revision ID: jelmer@samba.org-20081212153707-usxaq2v8agvmp91k
Change README to be about Dulwich rather than Python-git.
- 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
42
import zlib
45
43
46
from objects import (
47
ShaFile,
48
)
49
from errors import ApplyDeltaError
50
51
44
supports_mmap_offset = (sys.version_info[0] >= 3 or
52
45
(sys.version_info[0] == 2 and sys.version_info[1] >= 6))
53
46
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
47
from objects import (ShaFile,
48
_decompress,
49
)
62
50
63
51
def read_zlib(data, offset, dec_size):
64
52
obj = zlib.decompressobj()
65
53
x = ""
66
54
fed = 0
67
55
while obj.unused_data == "":
68
base = offset+fed
69
add = data[base:base+1024]
56
add = data[offset+fed:offset+fed+1024]
70
57
fed += len(add)
71
58
x += obj.decompress(add)
72
59
assert len(x) == dec_size
74
61
return x, comp_len
75
62
76
63
77
def iter_sha1(iter):
78
sha = hashlib.sha1()
79
for name in iter:
80
sha.update(name)
81
return sha.hexdigest()
82
83
84
64
def hex_to_sha(hex):
85
"""Convert a hex string to a binary sha string."""
86
65
ret = ""
87
66
for i in range(0, len(hex), 2):
88
67
ret += chr(int(hex[i:i+2], 16))
89
68
return ret
90
69
91
92
70
def sha_to_hex(sha):
93
"""Convert a binary sha string to a hex sha string."""
94
71
ret = ""
95
72
for i in sha:
96
73
ret += "%02x" % ord(i)
97
74
return ret
98
75
99
100
76
MAX_MMAP_SIZE = 256 * 1024 * 1024
101
77
102
78
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
79
if offset+size > MAX_MMAP_SIZE and not supports_mmap_offset:
112
80
raise AssertionError("%s is larger than 256 meg, and this version "
113
81
"of Python does not support the offset argument to mmap().")
138
106
return ArraySkipper(mem, offset)
139
107
140
108
109
def multi_ord(map, start, count):
110
value = 0
111
for i in range(count):
112
value = value * 0x100 + ord(map[start+i])
113
return value
114
115
141
116
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
117
if type == 6: # offset delta
147
118
(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)
119
base_text = get_offset(offset-delta_offset)
120
pass # FIXME
153
121
elif type == 7: # ref delta
154
122
(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)
123
base_text = get_ref(basename)
124
pass # FIXME
125
else:
126
return type, obj
161
127
162
128
163
129
class PackIndex(object):
181
147
it whenever required.
182
148
"""
183
149
self._filename = filename
150
assert os.path.exists(filename), "%s is not a pack index" % filename
184
151
# Take the size now, so it can be checked each time we map the file to
185
152
# ensure that it hasn't changed.
186
153
self._size = os.path.getsize(filename)
198
165
self._pack_offset_table_offset = self._crc32_table_offset + 4 * len(self)
199
166
200
167
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
168
return (type(self) == type(other) and
169
self._fan_out_table == other._fan_out_table and
170
list(self.iterentries()) == list(other.iterentries()))
211
171
212
172
def close(self):
213
173
self._file.close()
251
211
self._crc32_table_offset + i * 4)[0]
252
212
253
213
def __iter__(self):
254
return imap(sha_to_hex, self._itersha())
255
256
def _itersha(self):
257
214
for i in range(len(self)):
258
yield self._unpack_name(i)
259
260
def objects_sha1(self):
261
return iter_sha1(self._itersha())
215
yield sha_to_hex(self._unpack_name(i))
262
216
263
217
def iterentries(self):
264
218
"""Iterate over the entries in this pack index.
364
318
self._filename = filename
365
319
assert os.path.exists(filename), "%s is not a packfile" % filename
366
320
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
self._read_header()
321
self._header_size = self._read_header()
370
322
371
323
def _read_header(self):
372
324
f = open(self._filename, 'rb')
380
332
(version,) = struct.unpack_from(">L", header, 4)
381
333
assert version in (2, 3), "Version was %d" % version
382
334
(self._num_objects,) = struct.unpack_from(">L", header, 8)
335
return 12 # Header size
383
336
384
337
def __len__(self):
385
338
"""Returns the number of objects in this pack."""
394
347
f.close()
395
348
396
349
def iterobjects(self):
350
"""Yields (name, offset, crc32 checksum)."""
397
351
offset = self._header_size
398
352
f = open(self._filename, 'rb')
399
353
for i in range(len(self)):
403
357
offset += total_size
404
358
f.close()
405
359
406
def iterentries(self, ext_resolve_ref=None):
360
def iterentries(self):
407
361
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)
362
postponed = list(self.iterobjects())
363
while postponed:
364
(offset, type, obj) = postponed.pop()
429
365
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))
366
type, obj = resolve_object(offset, type, obj, found.__getitem__,
367
self.get_object_at)
368
except KeyError:
369
postponed.append((offset, type, obj))
434
370
else:
435
371
shafile = ShaFile.from_raw_string(type, obj)
436
372
sha = shafile.sha().digest()
437
373
found[sha] = (type, obj)
438
374
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
375
448
376
def create_index_v1(self, filename):
449
entries = self.sorted_entries()
377
entries = list(self.iterentries())
450
378
write_pack_index_v1(filename, entries, self.calculate_checksum())
451
379
452
380
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
381
entries = list(self.iterentries())
382
write_pack_index_v1(filename, entries, self.calculate_checksum())
458
383
459
384
def check(self):
460
return (self.calculate_checksum() == self.get_stored_checksum())
385
return (self.calculate_checksum() == self._stored_checksum)
461
386
462
387
def get_object_at(self, offset):
463
388
"""Given an offset in to the packfile return the object that is there.
466
391
then the packfile can be asked directly for that object using this
467
392
function.
468
393
"""
469
assert isinstance(offset, long) or isinstance(offset, int),\
470
"offset was %r" % offset
471
assert offset >= self._header_size
394
assert isinstance(offset, long) or isinstance(offset, int), "offset was %r" % offset
472
395
size = os.path.getsize(self._filename)
473
396
assert size == self._size, "Pack data %s has changed size, I don't " \
474
397
"like that" % self._filename
480
403
f.close()
481
404
482
405
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)
406
first_byte = ord(map[0])
407
sign_extend = first_byte & 0x80
408
type = (first_byte >> 4) & 0x07
409
size = first_byte & 0x0f
410
cur_offset = 0
411
while sign_extend > 0:
412
byte = ord(map[cur_offset+1])
413
sign_extend = byte & 0x80
414
size_part = byte & 0x7f
415
size += size_part << ((cur_offset * 7) + 4)
416
cur_offset += 1
417
raw_base = cur_offset+1
489
418
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)
419
# FIXME: Parse size
420
raise AssertionError("OFS_DELTA not yet supported")
498
421
uncomp, comp_len = read_zlib(map, raw_base, size)
499
422
assert size == len(uncomp)
500
return type, (delta_base_offset, uncomp), comp_len+raw_base
423
return type, (uncomp, offset), comp_len+raw_base
501
424
elif type == 7: # ref delta
502
basename = map[raw_base:raw_base+20]
503
uncomp, comp_len = read_zlib(map, raw_base+20, size)
425
basename = map[cur_offset:cur_offset+20]
426
raw_base += 20
427
uncomp, comp_len = read_zlib(map, raw_base, size)
504
428
assert size == len(uncomp)
505
return type, (basename, uncomp), comp_len+raw_base+20
429
# text = apply_delta(base, uncomp)
430
return type, (uncomp, basename), comp_len+raw_base
506
431
else:
432
# The size is the inflated size, so we have no idea what the deflated size
433
# is, so for now give it as much as we have. It should really iterate
434
# feeding it more data if it doesn't decompress, but as we have the whole
435
# thing then just use it.
507
436
uncomp, comp_len = read_zlib(map, raw_base, size)
508
437
assert len(uncomp) == size
509
438
return type, uncomp, comp_len+raw_base
519
448
self.sha1.update(data)
520
449
self.f.write(data)
521
450
522
def write_sha(self):
451
def close(self):
523
452
sha = self.sha1.digest()
524
453
assert len(sha) == 20
525
454
self.f.write(sha)
526
return sha
527
528
def close(self):
529
sha = self.write_sha()
530
455
self.f.close()
531
456
return sha
532
457
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):
458
459
def write_pack(filename, objects):
582
460
"""Write a new pack file.
583
461
584
462
:param filename: The filename of the new pack file.
585
463
:param objects: List of objects to write.
586
464
:return: List with (name, offset, crc32 checksum) entries, pack checksum
587
465
"""
466
f = open(filename, 'w')
588
467
entries = []
589
468
f = SHA1Writer(f)
590
469
f.write("PACK") # Pack header
591
470
f.write(struct.pack(">L", 2)) # Pack version
592
f.write(struct.pack(">L", num_objects)) # Number of objects in pack
471
f.write(struct.pack(">L", len(objects))) # Number of objects in pack
593
472
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()
473
pass # FIXME: Write object
474
return entries, f.close()
601
475
602
476
603
477
def write_pack_index_v1(filename, entries, pack_checksum):
608
482
crc32_checksum.
609
483
:param pack_checksum: Checksum of the pack file.
610
484
"""
485
# Sort entries first
486
487
entries = sorted(entries)
611
488
f = open(filename, 'w')
612
489
f = SHA1Writer(f)
613
490
fan_out_table = defaultdict(lambda: 0)
626
503
627
504
def apply_delta(src_buf, delta):
628
505
"""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 = ""
506
data = str(delta)
632
507
def pop(delta):
633
508
ret = delta[0]
634
509
delta = delta[1:]
645
520
return size, delta
646
521
src_size, delta = get_delta_header_size(delta)
647
522
dest_size, delta = get_delta_header_size(delta)
648
assert src_size == len(src_buf)
649
523
while delta:
650
524
cmd, delta = pop(delta)
651
525
if cmd & 0x80:
653
527
for i in range(4):
654
528
if cmd & (1 << i):
655
529
x, delta = pop(delta)
656
cp_off |= x << (i * 8)
530
cp_off |= x << (x << (i * 8))
657
531
cp_size = 0
658
532
for i in range(3):
659
if cmd & (1 << (4+i)):
533
if cmd & (1 << (2 << 3+i)):
660
534
x, delta = pop(delta)
661
cp_size |= x << (i * 8)
662
if cp_size == 0:
663
cp_size = 0x10000
535
cp_size |= x << (x << (i * 8))
536
if cp_size == 0: cp_size = 0x10000
664
537
if (cp_off + cp_size < cp_size or
665
538
cp_off + cp_size > src_size or
666
539
cp_size > dest_size):
667
540
break
668
out += src_buf[cp_off:cp_off+cp_size]
541
out += text[cp_off:cp_off+cp_size]
542
dest_size -= cp_size
669
543
elif cmd != 0:
670
out += delta[:cmd]
671
delta = delta[cmd:]
544
if cmd > dest_size:
545
break
546
out += data[:cmd]
547
data = data[cmd:]
548
dest_size -= cmd
672
549
else:
673
raise ApplyDeltaError("Invalid opcode 0")
550
raise AssertionError("Invalid opcode 0")
674
551
675
if delta != "":
676
raise ApplyDeltaError("delta not empty: %r" % delta)
552
if data != []:
553
raise AssertionError("data not empty: %r" % data)
677
554
678
if dest_size != len(out):
679
raise ApplyDeltaError("dest size incorrect")
555
if dest_size != 0:
556
raise AssertionError("dest size not empty")
680
557
681
558
return out
682
559
689
566
crc32_checksum.
690
567
:param pack_checksum: Checksum of the pack file.
691
568
"""
569
# Sort entries first
570
entries = sorted(entries)
692
571
f = open(filename, 'w')
693
572
f = SHA1Writer(f)
694
f.write('\377tOc') # Magic!
573
f.write('\377tOc')
695
574
f.write(struct.pack(">L", 2))
696
575
fan_out_table = defaultdict(lambda: 0)
697
576
for (name, offset, entry_checksum) in entries:
703
582
for (name, offset, entry_checksum) in entries:
704
583
f.write(name)
705
584
for (name, offset, entry_checksum) in entries:
706
f.write(struct.pack(">l", entry_checksum))
585
f.write(struct.pack(">L", entry_checksum))
707
586
for (name, offset, entry_checksum) in entries:
708
587
# FIXME: handle if MSBit is set in offset
709
588
f.write(struct.pack(">L", offset))
717
596
718
597
def __init__(self, basename):
719
598
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
599
self._idx = PackIndex(basename + ".idx")
600
self._pack = PackData(basename + ".pack")
601
assert len(self._idx) == len(self._pack)
749
602
750
603
def __len__(self):
751
604
"""Number of entries in this pack."""
752
return len(self.idx)
605
return len(self._idx)
753
606
754
607
def __repr__(self):
755
608
return "Pack(%r)" % self._basename
756
609
757
610
def __iter__(self):
758
611
"""Iterate over all the sha1s of the objects in this pack."""
759
return iter(self.idx)
612
return iter(self._idx)
760
613
761
614
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()
615
return self._idx.check() and self._pack.check()
766
616
767
617
def __contains__(self, sha1):
768
618
"""Check whether this pack contains a particular SHA1."""
769
return (self.idx.object_index(sha1) is not None)
619
return (self._idx.object_index(sha1) is not None)
770
620
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)
621
def _get_text(self, sha1):
622
offset = self._idx.object_index(sha1)
775
623
if offset is None:
776
624
raise KeyError(sha1)
777
625
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)
626
type, obj = self._pack.get_object_at(offset)
627
return resolve_object(offset, type, obj, self._get_text,
628
self._pack.get_object_at)
782
629
783
630
def __getitem__(self, sha1):
784
631
"""Retrieve the specified SHA1."""
785
type, uncomp = self.get_raw(sha1)
632
type, uncomp = self._get_text(sha1)
786
633
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