Raise sha error if necessary, always return refs, fix docs.
[jelmer/dulwich-libgit2.git] / dulwich / pack.py
1 # pack.py -- For dealing wih packed git objects.
2 # Copyright (C) 2007 James Westby <jw+debian@jameswestby.net>
3 # Copryight (C) 2008-2009 Jelmer Vernooij <jelmer@samba.org>
4
5 # This program is free software; you can redistribute it and/or
6 # modify it under the terms of the GNU General Public License
7 # as published by the Free Software Foundation; version 2
8 # of the License or (at your option) a later version.
9
10 # This program is distributed in the hope that it will be useful,
11 # but WITHOUT ANY WARRANTY; without even the implied warranty of
12 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13 # GNU General Public License for more details.
14
15 # You should have received a copy of the GNU General Public License
16 # along with this program; if not, write to the Free Software
17 # Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
18 # MA  02110-1301, USA.
19
20 """Classes for dealing with packed git objects.
21
22 A pack is a compact representation of a bunch of objects, stored
23 using deltas where possible.
24
25 They have two parts, the pack file, which stores the data, and an index
26 that tells you where the data is.
27
28 To find an object you look in all of the index files 'til you find a
29 match for the object name. You then use the pointer got from this as
30 a pointer in to the corresponding packfile.
31 """
32
33 try:
34     from collections import defaultdict
35 except ImportError:
36     from misc import defaultdict
37
38 from itertools import chain, imap, izip
39 import mmap
40 import os
41 import struct
42 try:
43     from struct import unpack_from
44 except ImportError:
45     from dulwich.misc import unpack_from
46 import sys
47 import zlib
48 import difflib
49
50 from dulwich.errors import (
51     ApplyDeltaError,
52     ChecksumMismatch,
53     )
54 from dulwich.lru_cache import (
55     LRUSizeCache,
56     )
57 from dulwich.objects import (
58     ShaFile,
59     hex_to_sha,
60     sha_to_hex,
61     )
62 from dulwich.misc import (
63     make_sha,
64     )
65
66 supports_mmap_offset = (sys.version_info[0] >= 3 or
67         (sys.version_info[0] == 2 and sys.version_info[1] >= 6))
68
69
70 def take_msb_bytes(map, offset):
71     ret = []
72     while len(ret) == 0 or ret[-1] & 0x80:
73         ret.append(ord(map[offset]))
74         offset += 1
75     return ret
76
77
78 def read_zlib_chunks(data, offset, dec_size):
79     obj = zlib.decompressobj()
80     ret = []
81     fed = 0
82     while obj.unused_data == "":
83         base = offset+fed
84         add = data[base:base+1024]
85         if len(add) < 1024:
86             add += "Z"
87         fed += len(add)
88         ret.append(obj.decompress(add))
89     comp_len = fed-len(obj.unused_data)
90     return ret, comp_len
91
92
93 def read_zlib(data, offset, dec_size):
94     ret, comp_len = read_zlib_chunks(data, offset, dec_size)
95     x = "".join(ret)
96     assert len(x) == dec_size
97     return x, comp_len
98
99
100 def iter_sha1(iter):
101     """Return the hexdigest of the SHA1 over a set of names.
102     
103     :param iter: Iterator over string objects
104     :return: 40-byte hex sha1 digest
105     """
106     sha1 = make_sha()
107     for name in iter:
108         sha1.update(name)
109     return sha1.hexdigest()
110
111
112 def simple_mmap(f, offset, size, access=mmap.ACCESS_READ):
113     """Simple wrapper for mmap() which always supports the offset parameter.
114
115     :param f: File object.
116     :param offset: Offset in the file, from the beginning of the file.
117     :param size: Size of the mmap'ed area
118     :param access: Access mechanism.
119     :return: MMAP'd area.
120     """
121     mem = mmap.mmap(f.fileno(), size+offset, access=access)
122     return mem, offset
123
124
125 def load_pack_index(filename):
126     f = open(filename, 'r')
127     if f.read(4) == '\377tOc':
128         version = struct.unpack(">L", f.read(4))[0]
129         if version == 2:
130             f.seek(0)
131             return PackIndex2(filename, file=f)
132         else:
133             raise KeyError("Unknown pack index format %d" % version)
134     else:
135         f.seek(0)
136         return PackIndex1(filename, file=f)
137
138
139 def bisect_find_sha(start, end, sha, unpack_name):
140     assert start <= end
141     while start <= end:
142         i = (start + end)/2
143         file_sha = unpack_name(i)
144         x = cmp(file_sha, sha)
145         if x < 0:
146             start = i + 1
147         elif x > 0:
148             end = i - 1
149         else:
150             return i
151     return None
152
153
154 class PackIndex(object):
155     """An index in to a packfile.
156   
157     Given a sha id of an object a pack index can tell you the location in the
158     packfile of that object if it has it.
159   
160     To do the loop it opens the file, and indexes first 256 4 byte groups
161     with the first byte of the sha id. The value in the four byte group indexed
162     is the end of the group that shares the same starting byte. Subtract one
163     from the starting byte and index again to find the start of the group.
164     The values are sorted by sha id within the group, so do the math to find
165     the start and end offset and then bisect in to find if the value is present.
166     """
167   
168     def __init__(self, filename, file=None):
169         """Create a pack index object.
170     
171         Provide it with the name of the index file to consider, and it will map
172         it whenever required.
173         """
174         self._filename = filename
175         # Take the size now, so it can be checked each time we map the file to
176         # ensure that it hasn't changed.
177         self._size = os.path.getsize(filename)
178         if file is None:
179             self._file = open(filename, 'r')
180         else:
181             self._file = file
182         self._contents, map_offset = simple_mmap(self._file, 0, self._size)
183         assert map_offset == 0
184   
185     def __eq__(self, other):
186         if not isinstance(other, PackIndex):
187             return False
188     
189         if self._fan_out_table != other._fan_out_table:
190             return False
191     
192         for (name1, _, _), (name2, _, _) in izip(self.iterentries(), other.iterentries()):
193             if name1 != name2:
194                 return False
195         return True
196   
197     def close(self):
198         self._file.close()
199   
200     def __len__(self):
201         """Return the number of entries in this pack index."""
202         return self._fan_out_table[-1]
203   
204     def _unpack_entry(self, i):
205         """Unpack the i-th entry in the index file.
206     
207         :return: Tuple with object name (SHA), offset in pack file and 
208               CRC32 checksum (if known)."""
209         raise NotImplementedError(self._unpack_entry)
210   
211     def _unpack_name(self, i):
212         """Unpack the i-th name from the index file."""
213         raise NotImplementedError(self._unpack_name)
214   
215     def _unpack_offset(self, i):
216         """Unpack the i-th object offset from the index file."""
217         raise NotImplementedError(self._unpack_offset)
218
219     def _unpack_crc32_checksum(self, i):
220         """Unpack the crc32 checksum for the i-th object from the index file."""
221         raise NotImplementedError(self._unpack_crc32_checksum)
222   
223     def __iter__(self):
224         return imap(sha_to_hex, self._itersha())
225   
226     def _itersha(self):
227         for i in range(len(self)):
228             yield self._unpack_name(i)
229   
230     def objects_sha1(self):
231         """Return the hex SHA1 over all the shas of all objects in this pack.
232         
233         :note: This is used for the filename of the pack.
234         """
235         return iter_sha1(self._itersha())
236   
237     def iterentries(self):
238         """Iterate over the entries in this pack index.
239        
240         Will yield tuples with object name, offset in packfile and crc32 checksum.
241         """
242         for i in range(len(self)):
243             yield self._unpack_entry(i)
244   
245     def _read_fan_out_table(self, start_offset):
246         ret = []
247         for i in range(0x100):
248             ret.append(struct.unpack(">L", self._contents[start_offset+i*4:start_offset+(i+1)*4])[0])
249         return ret
250   
251     def check(self):
252         """Check that the stored checksum matches the actual checksum."""
253         return self.calculate_checksum() == self.get_stored_checksum()
254   
255     def calculate_checksum(self):
256         """Calculate the SHA1 checksum over this pack index.
257
258         :return: This is a 20-byte binary digest
259         """
260         return make_sha(self._contents[:-20]).digest()
261
262     def get_pack_checksum(self):
263         """Return the SHA1 checksum stored for the corresponding packfile.
264         
265         :return: 20-byte binary digest
266         """
267         return str(self._contents[-40:-20])
268   
269     def get_stored_checksum(self):
270         """Return the SHA1 checksum stored for this index.
271         
272         :return: 20-byte binary digest
273         """
274         return str(self._contents[-20:])
275   
276     def object_index(self, sha):
277         """Return the index in to the corresponding packfile for the object.
278     
279         Given the name of an object it will return the offset that object lives
280         at within the corresponding pack file. If the pack file doesn't have the
281         object then None will be returned.
282         """
283         if len(sha) == 40:
284             sha = hex_to_sha(sha)
285         return self._object_index(sha)
286   
287     def _object_index(self, sha):
288         """See object_index.
289         
290         :param sha: A *binary* SHA string. (20 characters long)_
291         """
292         assert len(sha) == 20
293         idx = ord(sha[0])
294         if idx == 0:
295             start = 0
296         else:
297             start = self._fan_out_table[idx-1]
298         end = self._fan_out_table[idx]
299         i = bisect_find_sha(start, end, sha, self._unpack_name)
300         if i is None:
301             raise KeyError(sha)
302         return self._unpack_offset(i)
303             
304
305
306 class PackIndex1(PackIndex):
307     """Version 1 Pack Index."""
308
309     def __init__(self, filename, file=None):
310         PackIndex.__init__(self, filename, file)
311         self.version = 1
312         self._fan_out_table = self._read_fan_out_table(0)
313
314     def _unpack_entry(self, i):
315         (offset, name) = unpack_from(">L20s", self._contents, 
316             (0x100 * 4) + (i * 24))
317         return (name, offset, None)
318  
319     def _unpack_name(self, i):
320         offset = (0x100 * 4) + (i * 24) + 4
321         return self._contents[offset:offset+20]
322   
323     def _unpack_offset(self, i):
324         offset = (0x100 * 4) + (i * 24)
325         return unpack_from(">L", self._contents, offset)[0]
326   
327     def _unpack_crc32_checksum(self, i):
328         # Not stored in v1 index files
329         return None 
330   
331
332 class PackIndex2(PackIndex):
333     """Version 2 Pack Index."""
334
335     def __init__(self, filename, file=None):
336         PackIndex.__init__(self, filename, file)
337         assert self._contents[:4] == '\377tOc', "Not a v2 pack index file"
338         (self.version, ) = unpack_from(">L", self._contents, 4)
339         assert self.version == 2, "Version was %d" % self.version
340         self._fan_out_table = self._read_fan_out_table(8)
341         self._name_table_offset = 8 + 0x100 * 4
342         self._crc32_table_offset = self._name_table_offset + 20 * len(self)
343         self._pack_offset_table_offset = self._crc32_table_offset + 4 * len(self)
344
345     def _unpack_entry(self, i):
346         return (self._unpack_name(i), self._unpack_offset(i), 
347                 self._unpack_crc32_checksum(i))
348  
349     def _unpack_name(self, i):
350         offset = self._name_table_offset + i * 20
351         return self._contents[offset:offset+20]
352   
353     def _unpack_offset(self, i):
354         offset = self._pack_offset_table_offset + i * 4
355         return unpack_from(">L", self._contents, offset)[0]
356   
357     def _unpack_crc32_checksum(self, i):
358         return unpack_from(">L", self._contents, 
359                           self._crc32_table_offset + i * 4)[0]
360   
361
362
363 def read_pack_header(f):
364     """Read the header of a pack file.
365
366     :param f: File-like object to read from
367     """
368     header = f.read(12)
369     assert header[:4] == "PACK"
370     (version,) = unpack_from(">L", header, 4)
371     assert version in (2, 3), "Version was %d" % version
372     (num_objects,) = unpack_from(">L", header, 8)
373     return (version, num_objects)
374
375
376 def read_pack_tail(f):
377     return (f.read(20),)
378
379
380 def unpack_object(map, offset=0):
381     """Unpack a Git object.
382
383     :return: tuple with type, uncompressed data and compressed size
384     """
385     bytes = take_msb_bytes(map, offset)
386     type = (bytes[0] >> 4) & 0x07
387     size = bytes[0] & 0x0f
388     for i, byte in enumerate(bytes[1:]):
389         size += (byte & 0x7f) << ((i * 7) + 4)
390     raw_base = len(bytes)
391     if type == 6: # offset delta
392         bytes = take_msb_bytes(map, raw_base + offset)
393         assert not (bytes[-1] & 0x80)
394         delta_base_offset = bytes[0] & 0x7f
395         for byte in bytes[1:]:
396             delta_base_offset += 1
397             delta_base_offset <<= 7
398             delta_base_offset += (byte & 0x7f)
399         raw_base+=len(bytes)
400         uncomp, comp_len = read_zlib(map, offset + raw_base, size)
401         assert size == len(uncomp)
402         return type, (delta_base_offset, uncomp), comp_len+raw_base
403     elif type == 7: # ref delta
404         basename = map[offset+raw_base:offset+raw_base+20]
405         uncomp, comp_len = read_zlib(map, offset+raw_base+20, size)
406         assert size == len(uncomp)
407         return type, (basename, uncomp), comp_len+raw_base+20
408     else:
409         uncomp, comp_len = read_zlib(map, offset+raw_base, size)
410         assert len(uncomp) == size
411         return type, uncomp, comp_len+raw_base
412
413
414 def compute_object_size((num, obj)):
415     """Compute the size of a unresolved object for use with LRUSizeCache.
416     """
417     if num in (6, 7):
418         return len(obj[1])
419     assert isinstance(obj, str)
420     return len(obj)
421
422
423 class PackData(object):
424     """The data contained in a packfile.
425   
426     Pack files can be accessed both sequentially for exploding a pack, and
427     directly with the help of an index to retrieve a specific object.
428   
429     The objects within are either complete or a delta aginst another.
430   
431     The header is variable length. If the MSB of each byte is set then it
432     indicates that the subsequent byte is still part of the header.
433     For the first byte the next MS bits are the type, which tells you the type
434     of object, and whether it is a delta. The LS byte is the lowest bits of the
435     size. For each subsequent byte the LS 7 bits are the next MS bits of the
436     size, i.e. the last byte of the header contains the MS bits of the size.
437   
438     For the complete objects the data is stored as zlib deflated data.
439     The size in the header is the uncompressed object size, so to uncompress
440     you need to just keep feeding data to zlib until you get an object back,
441     or it errors on bad data. This is done here by just giving the complete
442     buffer from the start of the deflated object on. This is bad, but until I
443     get mmap sorted out it will have to do.
444   
445     Currently there are no integrity checks done. Also no attempt is made to try
446     and detect the delta case, or a request for an object at the wrong position.
447     It will all just throw a zlib or KeyError.
448     """
449   
450     def __init__(self, filename):
451         """Create a PackData object that represents the pack in the given filename.
452     
453         The file must exist and stay readable until the object is disposed of. It
454         must also stay the same size. It will be mapped whenever needed.
455     
456         Currently there is a restriction on the size of the pack as the python
457         mmap implementation is flawed.
458         """
459         self._filename = filename
460         assert os.path.exists(filename), "%s is not a packfile" % filename
461         self._size = os.path.getsize(filename)
462         self._header_size = 12
463         assert self._size >= self._header_size, "%s is too small for a packfile (%d < %d)" % (filename, self._size, self._header_size)
464         self._file = open(self._filename, 'rb')
465         self._read_header()
466         self._offset_cache = LRUSizeCache(1024*1024*20, 
467             compute_size=compute_object_size)
468
469     def close(self):
470         self._file.close()
471   
472     def _read_header(self):
473         (version, self._num_objects) = read_pack_header(self._file)
474         self._file.seek(self._size-20)
475         (self._stored_checksum,) = read_pack_tail(self._file)
476   
477     def __len__(self):
478         """Returns the number of objects in this pack."""
479         return self._num_objects
480   
481     def calculate_checksum(self):
482         """Calculate the checksum for this pack.
483
484         :return: 20-byte binary SHA1 digest
485         """
486         map, map_offset = simple_mmap(self._file, 0, self._size - 20)
487         try:
488             return make_sha(map[map_offset:self._size-20]).digest()
489         finally:
490             map.close()
491
492     def resolve_object(self, offset, type, obj, get_ref, get_offset=None):
493         """Resolve an object, possibly resolving deltas when necessary.
494         
495         :return: Tuple with object type and contents.
496         """
497         if type not in (6, 7): # Not a delta
498             return type, obj
499
500         if get_offset is None:
501             get_offset = self.get_object_at
502       
503         if type == 6: # offset delta
504             (delta_offset, delta) = obj
505             assert isinstance(delta_offset, int)
506             assert isinstance(delta, str)
507             base_offset = offset-delta_offset
508             type, base_obj = get_offset(base_offset)
509             assert isinstance(type, int)
510         elif type == 7: # ref delta
511             (basename, delta) = obj
512             assert isinstance(basename, str) and len(basename) == 20
513             assert isinstance(delta, str)
514             type, base_obj = get_ref(basename)
515             assert isinstance(type, int)
516             # Can't be a ofs delta, as we wouldn't know the base offset
517             assert type != 6
518             base_offset = None
519         type, base_text = self.resolve_object(base_offset, type, base_obj, get_ref)
520         if base_offset is not None:
521             self._offset_cache[base_offset] = type, base_text
522         ret = (type, apply_delta(base_text, delta))
523         return ret
524   
525     def iterobjects(self, progress=None):
526
527         class ObjectIterator(object):
528             
529             def __init__(self, pack):
530                 self.i = 0
531                 self.offset = pack._header_size
532                 self.num = len(pack)
533                 self.map, _ = simple_mmap(pack._file, 0, pack._size)
534
535             def __del__(self):
536                 self.map.close()
537
538             def __iter__(self):
539                 return self
540
541             def __len__(self):
542                 return self.num
543             
544             def next(self):
545                 if self.i == self.num:
546                     raise StopIteration
547                 (type, obj, total_size) = unpack_object(self.map, self.offset)
548                 crc32 = zlib.crc32(self.map[self.offset:self.offset+total_size]) & 0xffffffff
549                 ret = (self.offset, type, obj, crc32)
550                 self.offset += total_size
551                 if progress:
552                     progress(self.i, self.num)
553                 self.i+=1
554                 return ret
555         return ObjectIterator(self)
556   
557     def iterentries(self, ext_resolve_ref=None, progress=None):
558         found = {}
559         postponed = defaultdict(list)
560         class Postpone(Exception):
561             """Raised to postpone delta resolving."""
562           
563         def get_ref_text(sha):
564             assert len(sha) == 20
565             if sha in found:
566                 return self.get_object_at(found[sha])
567             if ext_resolve_ref:
568                 try:
569                     return ext_resolve_ref(sha)
570                 except KeyError:
571                     pass
572             raise Postpone, (sha, )
573         extra = []
574         todo = chain(self.iterobjects(progress=progress), extra)
575         for (offset, type, obj, crc32) in todo:
576             assert isinstance(offset, int)
577             assert isinstance(type, int)
578             assert isinstance(obj, tuple) or isinstance(obj, str)
579             try:
580                 type, obj = self.resolve_object(offset, type, obj, get_ref_text)
581             except Postpone, (sha, ):
582                 postponed[sha].append((offset, type, obj))
583             else:
584                 shafile = ShaFile.from_raw_string(type, obj)
585                 sha = shafile.sha().digest()
586                 found[sha] = offset
587                 yield sha, offset, crc32
588                 extra.extend(postponed.get(sha, []))
589         if postponed:
590             raise KeyError([sha_to_hex(h) for h in postponed.keys()])
591   
592     def sorted_entries(self, resolve_ext_ref=None, progress=None):
593         ret = list(self.iterentries(resolve_ext_ref, progress=progress))
594         ret.sort()
595         return ret
596   
597     def create_index_v1(self, filename, resolve_ext_ref=None, progress=None):
598         """Create a version 1 file for this data file.
599
600         :param filename: Index filename.
601         :param resolve_ext_ref: Function to use for resolving externally referenced
602             SHA1s (for thin packs)
603         :param progress: Progress report function
604         """
605         entries = self.sorted_entries(resolve_ext_ref, progress=progress)
606         write_pack_index_v1(filename, entries, self.calculate_checksum())
607   
608     def create_index_v2(self, filename, resolve_ext_ref=None, progress=None):
609         """Create a version 2 index file for this data file.
610
611         :param filename: Index filename.
612         :param resolve_ext_ref: Function to use for resolving externally referenced
613             SHA1s (for thin packs)
614         :param progress: Progress report function
615         """
616         entries = self.sorted_entries(resolve_ext_ref, progress=progress)
617         write_pack_index_v2(filename, entries, self.calculate_checksum())
618
619     def create_index(self, filename, resolve_ext_ref=None, progress=None, version=2):
620         """Create an  index file for this data file.
621
622         :param filename: Index filename.
623         :param resolve_ext_ref: Function to use for resolving externally referenced
624             SHA1s (for thin packs)
625         :param progress: Progress report function
626         """
627         if version == 1:
628             self.create_index_v1(filename, resolve_ext_ref, progress)
629         elif version == 2:
630             self.create_index_v2(filename, resolve_ext_ref, progress)
631         else:
632             raise ValueError("unknown index format %d" % version)
633   
634     def get_stored_checksum(self):
635         return self._stored_checksum
636   
637     def check(self):
638         return (self.calculate_checksum() == self.get_stored_checksum())
639   
640     def get_object_at(self, offset):
641         """Given an offset in to the packfile return the object that is there.
642     
643         Using the associated index the location of an object can be looked up, and
644         then the packfile can be asked directly for that object using this
645         function.
646         """
647         if offset in self._offset_cache:
648             return self._offset_cache[offset]
649         assert isinstance(offset, long) or isinstance(offset, int),\
650                 "offset was %r" % offset
651         assert offset >= self._header_size
652         map, map_offset = simple_mmap(self._file, offset, self._size-offset)
653         try:
654             ret = unpack_object(map, map_offset)[:2]
655             return ret
656         finally:
657             map.close()
658
659
660 class SHA1Writer(object):
661     """Wrapper around a file-like object that remembers the SHA1 of 
662     the data written to it."""
663     
664     def __init__(self, f):
665         self.f = f
666         self.sha1 = make_sha("")
667
668     def write(self, data):
669         self.sha1.update(data)
670         self.f.write(data)
671
672     def write_sha(self):
673         sha = self.sha1.digest()
674         assert len(sha) == 20
675         self.f.write(sha)
676         return sha
677
678     def close(self):
679         sha = self.write_sha()
680         self.f.close()
681         return sha
682
683     def tell(self):
684         return self.f.tell()
685
686
687 def write_pack_object(f, type, object):
688     """Write pack object to a file.
689
690     :param f: File to write to
691     :param o: Object to write
692     :return: Tuple with offset at which the object was written, and crc32
693     """
694     ret = f.tell()
695     packed_data_hdr = ""
696     if type == 6: # ref delta
697         (delta_base_offset, object) = object
698     elif type == 7: # offset delta
699         (basename, object) = object
700     size = len(object)
701     c = (type << 4) | (size & 15)
702     size >>= 4
703     while size:
704         packed_data_hdr += (chr(c | 0x80))
705         c = size & 0x7f
706         size >>= 7
707     packed_data_hdr += chr(c)
708     if type == 6: # offset delta
709         ret = [delta_base_offset & 0x7f]
710         delta_base_offset >>= 7
711         while delta_base_offset:
712             delta_base_offset -= 1
713             ret.insert(0, 0x80 | (delta_base_offset & 0x7f))
714             delta_base_offset >>= 7
715         packed_data_hdr += "".join([chr(x) for x in ret])
716     elif type == 7: # ref delta
717         assert len(basename) == 20
718         packed_data_hdr += basename
719     packed_data = packed_data_hdr + zlib.compress(object)
720     f.write(packed_data)
721     return (f.tell(), (zlib.crc32(packed_data) & 0xffffffff))
722
723
724 def write_pack(filename, objects, num_objects):
725     """Write a new pack data file.
726
727     :param filename: Path to the new pack file (without .pack extension)
728     :param objects: Iterable over (object, path) tuples to write
729     :param num_objects: Number of objects to write
730     """
731     f = open(filename + ".pack", 'w')
732     try:
733         entries, data_sum = write_pack_data(f, objects, num_objects)
734     finally:
735         f.close()
736     entries.sort()
737     write_pack_index_v2(filename + ".idx", entries, data_sum)
738
739
740 def write_pack_data(f, objects, num_objects, window=10):
741     """Write a new pack file.
742
743     :param filename: The filename of the new pack file.
744     :param objects: List of objects to write (tuples with object and path)
745     :return: List with (name, offset, crc32 checksum) entries, pack checksum
746     """
747     recency = list(objects)
748     # FIXME: Somehow limit delta depth
749     # FIXME: Make thin-pack optional (its not used when cloning a pack)
750     # Build a list of objects ordered by the magic Linus heuristic
751     # This helps us find good objects to diff against us
752     magic = []
753     for obj, path in recency:
754         magic.append( (obj.type, path, 1, -len(obj.as_raw_string()), obj) )
755     magic.sort()
756     # Build a map of objects and their index in magic - so we can find preceeding objects
757     # to diff against
758     offs = {}
759     for i in range(len(magic)):
760         offs[magic[i][4]] = i
761     # Write the pack
762     entries = []
763     f = SHA1Writer(f)
764     f.write("PACK")               # Pack header
765     f.write(struct.pack(">L", 2)) # Pack version
766     f.write(struct.pack(">L", num_objects)) # Number of objects in pack
767     for o, path in recency:
768         sha1 = o.sha().digest()
769         orig_t = o.type
770         raw = o.as_raw_string()
771         winner = raw
772         t = orig_t
773         #for i in range(offs[o]-window, window):
774         #    if i < 0 or i >= len(offs): continue
775         #    b = magic[i][4]
776         #    if b.type != orig_t: continue
777         #    base = b.as_raw_string()
778         #    delta = create_delta(base, raw)
779         #    if len(delta) < len(winner):
780         #        winner = delta
781         #        t = 6 if magic[i][2] == 1 else 7
782         offset, crc32 = write_pack_object(f, t, winner)
783         entries.append((sha1, offset, crc32))
784     return entries, f.write_sha()
785
786
787 def write_pack_index_v1(filename, entries, pack_checksum):
788     """Write a new pack index file.
789
790     :param filename: The filename of the new pack index file.
791     :param entries: List of tuples with object name (sha), offset_in_pack,  and
792             crc32_checksum.
793     :param pack_checksum: Checksum of the pack file.
794     """
795     f = open(filename, 'w')
796     f = SHA1Writer(f)
797     fan_out_table = defaultdict(lambda: 0)
798     for (name, offset, entry_checksum) in entries:
799         fan_out_table[ord(name[0])] += 1
800     # Fan-out table
801     for i in range(0x100):
802         f.write(struct.pack(">L", fan_out_table[i]))
803         fan_out_table[i+1] += fan_out_table[i]
804     for (name, offset, entry_checksum) in entries:
805         f.write(struct.pack(">L20s", offset, name))
806     assert len(pack_checksum) == 20
807     f.write(pack_checksum)
808     f.close()
809
810
811 def create_delta(base_buf, target_buf):
812     """Use python difflib to work out how to transform base_buf to target_buf.
813     
814     :param base_buf: Base buffer
815     :param target_buf: Target buffer
816     """
817     assert isinstance(base_buf, str)
818     assert isinstance(target_buf, str)
819     out_buf = ""
820     # write delta header
821     def encode_size(size):
822         ret = ""
823         c = size & 0x7f
824         size >>= 7
825         while size:
826             ret += chr(c | 0x80)
827             c = size & 0x7f
828             size >>= 7
829         ret += chr(c)
830         return ret
831     out_buf += encode_size(len(base_buf))
832     out_buf += encode_size(len(target_buf))
833     # write out delta opcodes
834     seq = difflib.SequenceMatcher(a=base_buf, b=target_buf)
835     for opcode, i1, i2, j1, j2 in seq.get_opcodes():
836         # Git patch opcodes don't care about deletes!
837         #if opcode == "replace" or opcode == "delete":
838         #    pass
839         if opcode == "equal":
840             # If they are equal, unpacker will use data from base_buf
841             # Write out an opcode that says what range to use
842             scratch = ""
843             op = 0x80
844             o = i1
845             for i in range(4):
846                 if o & 0xff << i*8:
847                     scratch += chr(o >> i)
848                     op |= 1 << i
849             s = i2 - i1
850             for i in range(2):
851                 if s & 0xff << i*8:
852                     scratch += chr(s >> i)
853                     op |= 1 << (4+i)
854             out_buf += chr(op)
855             out_buf += scratch
856         if opcode == "replace" or opcode == "insert":
857             # If we are replacing a range or adding one, then we just
858             # output it to the stream (prefixed by its size)
859             s = j2 - j1
860             o = j1
861             while s > 127:
862                 out_buf += chr(127)
863                 out_buf += target_buf[o:o+127]
864                 s -= 127
865                 o += 127
866             out_buf += chr(s)
867             out_buf += target_buf[o:o+s]
868     return out_buf
869
870
871 def apply_delta(src_buf, delta):
872     """Based on the similar function in git's patch-delta.c.
873     
874     :param src_buf: Source buffer
875     :param delta: Delta instructions
876     """
877     assert isinstance(src_buf, str), "was %r" % (src_buf,)
878     assert isinstance(delta, str)
879     out = []
880     index = 0
881     delta_length = len(delta)
882     def get_delta_header_size(delta, index):
883         size = 0
884         i = 0
885         while delta:
886             cmd = ord(delta[index])
887             index += 1
888             size |= (cmd & ~0x80) << i
889             i += 7
890             if not cmd & 0x80:
891                 break
892         return size, index
893     src_size, index = get_delta_header_size(delta, index)
894     dest_size, index = get_delta_header_size(delta, index)
895     assert src_size == len(src_buf), "%d vs %d" % (src_size, len(src_buf))
896     while index < delta_length:
897         cmd = ord(delta[index])
898         index += 1
899         if cmd & 0x80:
900             cp_off = 0
901             for i in range(4):
902                 if cmd & (1 << i): 
903                     x = ord(delta[index])
904                     index += 1
905                     cp_off |= x << (i * 8)
906             cp_size = 0
907             for i in range(3):
908                 if cmd & (1 << (4+i)): 
909                     x = ord(delta[index])
910                     index += 1
911                     cp_size |= x << (i * 8)
912             if cp_size == 0: 
913                 cp_size = 0x10000
914             if (cp_off + cp_size < cp_size or
915                 cp_off + cp_size > src_size or
916                 cp_size > dest_size):
917                 break
918             out.append(src_buf[cp_off:cp_off+cp_size])
919         elif cmd != 0:
920             out.append(delta[index:index+cmd])
921             index += cmd
922         else:
923             raise ApplyDeltaError("Invalid opcode 0")
924     
925     if index != delta_length:
926         raise ApplyDeltaError("delta not empty: %r" % delta[index:])
927
928     out = ''.join(out)
929     if dest_size != len(out):
930         raise ApplyDeltaError("dest size incorrect")
931
932     return out
933
934
935 def write_pack_index_v2(filename, entries, pack_checksum):
936     """Write a new pack index file.
937
938     :param filename: The filename of the new pack index file.
939     :param entries: List of tuples with object name (sha), offset_in_pack,  and
940             crc32_checksum.
941     :param pack_checksum: Checksum of the pack file.
942     """
943     f = open(filename, 'w')
944     f = SHA1Writer(f)
945     f.write('\377tOc') # Magic!
946     f.write(struct.pack(">L", 2))
947     fan_out_table = defaultdict(lambda: 0)
948     for (name, offset, entry_checksum) in entries:
949         fan_out_table[ord(name[0])] += 1
950     # Fan-out table
951     for i in range(0x100):
952         f.write(struct.pack(">L", fan_out_table[i]))
953         fan_out_table[i+1] += fan_out_table[i]
954     for (name, offset, entry_checksum) in entries:
955         f.write(name)
956     for (name, offset, entry_checksum) in entries:
957         f.write(struct.pack(">L", entry_checksum))
958     for (name, offset, entry_checksum) in entries:
959         # FIXME: handle if MSBit is set in offset
960         f.write(struct.pack(">L", offset))
961     # FIXME: handle table for pack files > 8 Gb
962     assert len(pack_checksum) == 20
963     f.write(pack_checksum)
964     f.close()
965
966
967 class Pack(object):
968     """A Git pack object."""
969
970     def __init__(self, basename):
971         self._basename = basename
972         self._data_path = self._basename + ".pack"
973         self._idx_path = self._basename + ".idx"
974         self._data = None
975         self._idx = None
976
977     @classmethod
978     def from_objects(self, data, idx):
979         """Create a new pack object from pack data and index objects."""
980         ret = Pack("")
981         ret._data = data
982         ret._idx = idx
983         return ret
984
985     def name(self):
986         """The SHA over the SHAs of the objects in this pack."""
987         return self.index.objects_sha1()
988
989     @property
990     def data(self):
991         """The pack data object being used."""
992         if self._data is None:
993             self._data = PackData(self._data_path)
994             assert len(self.index) == len(self._data)
995             idx_stored_checksum = self.index.get_pack_checksum()
996             data_stored_checksum = self._data.get_stored_checksum()
997             if idx_stored_checksum != data_stored_checksum:
998                 raise ChecksumMismatch(sha_to_hex(idx_stored_checksum), 
999                                        sha_to_hex(data_stored_checksum))
1000         return self._data
1001
1002     @property
1003     def index(self):
1004         """The index being used.
1005
1006         :note: This may be an in-memory index
1007         """
1008         if self._idx is None:
1009             self._idx = load_pack_index(self._idx_path)
1010         return self._idx
1011
1012     def close(self):
1013         if self._data is not None:
1014             self._data.close()
1015         self.index.close()
1016
1017     def __eq__(self, other):
1018         return type(self) == type(other) and self.index == other.index
1019
1020     def __len__(self):
1021         """Number of entries in this pack."""
1022         return len(self.index)
1023
1024     def __repr__(self):
1025         return "%s(%r)" % (self.__class__.__name__, self._basename)
1026
1027     def __iter__(self):
1028         """Iterate over all the sha1s of the objects in this pack."""
1029         return iter(self.index)
1030
1031     def check(self):
1032         """Check the integrity of this pack."""
1033         if not self.index.check():
1034             return False
1035         if not self.data.check():
1036             return False
1037         return True
1038
1039     def get_stored_checksum(self):
1040         return self.data.get_stored_checksum()
1041
1042     def __contains__(self, sha1):
1043         """Check whether this pack contains a particular SHA1."""
1044         try:
1045             self.index.object_index(sha1)
1046             return True
1047         except KeyError:
1048             return False
1049
1050     def get_raw(self, sha1, resolve_ref=None):
1051         offset = self.index.object_index(sha1)
1052         obj_type, obj = self.data.get_object_at(offset)
1053         if type(offset) is long:
1054           offset = int(offset)
1055         if resolve_ref is None:
1056             resolve_ref = self.get_raw
1057         return self.data.resolve_object(offset, obj_type, obj, resolve_ref)
1058
1059     def __getitem__(self, sha1):
1060         """Retrieve the specified SHA1."""
1061         type, uncomp = self.get_raw(sha1)
1062         return ShaFile.from_raw_string(type, uncomp)
1063
1064     def iterobjects(self, get_raw=None):
1065         """Iterate over the objects in this pack."""
1066         if get_raw is None:
1067             get_raw = self.get_raw
1068         for offset, type, obj, crc32 in self.data.iterobjects():
1069             assert isinstance(offset, int)
1070             yield ShaFile.from_raw_string(
1071                     *self.data.resolve_object(offset, type, obj, get_raw))
1072
1073
1074 def load_packs(path):
1075     if not os.path.exists(path):
1076         return
1077     for name in os.listdir(path):
1078         if name.startswith("pack-") and name.endswith(".pack"):
1079             yield Pack(os.path.join(path, name[:-len(".pack")]))
1080
1081
1082 try:
1083     from dulwich._pack import apply_delta, bisect_find_sha
1084 except ImportError:
1085     pass