5ab4dfbd18d9161a5a38f327204160c849e734e7
[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 import difflib
39 from itertools import (
40     chain,
41     imap,
42     izip,
43     )
44 import mmap
45 import os
46 import struct
47 try:
48     from struct import unpack_from
49 except ImportError:
50     from dulwich.misc import unpack_from
51 import sys
52 import zlib
53
54 from dulwich.errors import (
55     ApplyDeltaError,
56     ChecksumMismatch,
57     )
58 from dulwich.file import GitFile
59 from dulwich.lru_cache import (
60     LRUSizeCache,
61     )
62 from dulwich.objects import (
63     ShaFile,
64     hex_to_sha,
65     sha_to_hex,
66     object_header,
67     )
68 from dulwich.misc import (
69     make_sha,
70     )
71
72 supports_mmap_offset = (sys.version_info[0] >= 3 or
73         (sys.version_info[0] == 2 and sys.version_info[1] >= 6))
74
75
76 OFS_DELTA = 6
77 REF_DELTA = 7
78
79 DELTA_TYPES = (OFS_DELTA, REF_DELTA)
80
81
82 def take_msb_bytes(read):
83     """Read bytes marked with most significant bit.
84
85     :param read: Read function
86     """
87     ret = []
88     while len(ret) == 0 or ret[-1] & 0x80:
89         ret.append(ord(read(1)))
90     return ret
91
92
93 def read_zlib_chunks(read_some, dec_size, buffer_size=4096):
94     """Read zlib data from a buffer.
95
96     This function requires that the buffer have additional data following the
97     compressed data, which is guaranteed to be the case for git pack files.
98
99     :param read_some: Read function that returns at least one byte, but may
100         return less than the requested size
101     :param dec_size: Expected size of the decompressed buffer
102     :param buffer_size: Size of the read buffer
103     :return: Tuple with list of chunks, length of compressed data length and
104         and unused read data.
105     :raise zlib.error: if a decompression error occurred.
106     """
107     if dec_size <= -1:
108         raise ValueError("non-negative zlib data stream size expected")
109     obj = zlib.decompressobj()
110     ret = []
111     fed = 0
112     size = 0
113     while obj.unused_data == "":
114         add = read_some(buffer_size)
115         if not add:
116             raise zlib.error("EOF before end of zlib stream")
117         fed += len(add)
118         decomp = obj.decompress(add)
119         size += len(decomp)
120         ret.append(decomp)
121     if size != dec_size:
122         raise zlib.error("decompressed data does not match expected size")
123     comp_len = fed - len(obj.unused_data)
124     return ret, comp_len, obj.unused_data
125
126 def iter_sha1(iter):
127     """Return the hexdigest of the SHA1 over a set of names.
128
129     :param iter: Iterator over string objects
130     :return: 40-byte hex sha1 digest
131     """
132     sha1 = make_sha()
133     for name in iter:
134         sha1.update(name)
135     return sha1.hexdigest()
136
137
138 def load_pack_index(path):
139     """Load an index file by path.
140
141     :param filename: Path to the index file
142     :return: A PackIndex loaded from the given path
143     """
144     f = GitFile(path, 'rb')
145     try:
146         return load_pack_index_file(path, f)
147     finally:
148         f.close()
149
150
151 def _load_file_contents(f, size=None):
152     fileno = getattr(f, 'fileno', None)
153     # Attempt to use mmap if possible
154     if fileno is not None:
155         fd = f.fileno()
156         if size is None:
157             size = os.fstat(fd).st_size
158         try:
159             contents = mmap.mmap(fd, size, access=mmap.ACCESS_READ)
160         except mmap.error:
161             # Perhaps a socket?
162             pass
163         else:
164             return contents, size
165     contents = f.read()
166     size = len(contents)
167     return contents, size
168
169
170 def load_pack_index_file(path, f):
171     """Load an index file from a file-like object.
172
173     :param path: Path for the index file
174     :param f: File-like object
175     :return: A PackIndex loaded from the given file
176     """
177     contents, size = _load_file_contents(f)
178     if contents[:4] == '\377tOc':
179         version = struct.unpack(">L", contents[4:8])[0]
180         if version == 2:
181             return PackIndex2(path, file=f, contents=contents,
182                 size=size)
183         else:
184             raise KeyError("Unknown pack index format %d" % version)
185     else:
186         return PackIndex1(path, file=f, contents=contents, size=size)
187
188
189 def bisect_find_sha(start, end, sha, unpack_name):
190     """Find a SHA in a data blob with sorted SHAs.
191
192     :param start: Start index of range to search
193     :param end: End index of range to search
194     :param sha: Sha to find
195     :param unpack_name: Callback to retrieve SHA by index
196     :return: Index of the SHA, or None if it wasn't found
197     """
198     assert start <= end
199     while start <= end:
200         i = (start + end)/2
201         file_sha = unpack_name(i)
202         x = cmp(file_sha, sha)
203         if x < 0:
204             start = i + 1
205         elif x > 0:
206             end = i - 1
207         else:
208             return i
209     return None
210
211
212 class PackIndex(object):
213     """An index in to a packfile.
214
215     Given a sha id of an object a pack index can tell you the location in the
216     packfile of that object if it has it.
217
218     To do the loop it opens the file, and indexes first 256 4 byte groups
219     with the first byte of the sha id. The value in the four byte group indexed
220     is the end of the group that shares the same starting byte. Subtract one
221     from the starting byte and index again to find the start of the group.
222     The values are sorted by sha id within the group, so do the math to find
223     the start and end offset and then bisect in to find if the value is present.
224     """
225
226     def __init__(self, filename, file=None, contents=None, size=None):
227         """Create a pack index object.
228
229         Provide it with the name of the index file to consider, and it will map
230         it whenever required.
231         """
232         self._filename = filename
233         # Take the size now, so it can be checked each time we map the file to
234         # ensure that it hasn't changed.
235         if file is None:
236             self._file = GitFile(filename, 'rb')
237         else:
238             self._file = file
239         if contents is None:
240             self._contents, self._size = _load_file_contents(file, size)
241         else:
242             self._contents, self._size = (contents, size)
243
244     def __eq__(self, other):
245         if not isinstance(other, PackIndex):
246             return False
247
248         if self._fan_out_table != other._fan_out_table:
249             return False
250
251         for (name1, _, _), (name2, _, _) in izip(self.iterentries(),
252                                                  other.iterentries()):
253             if name1 != name2:
254                 return False
255         return True
256
257     def __ne__(self, other):
258         return not self.__eq__(other)
259
260     def close(self):
261         self._file.close()
262
263     def __len__(self):
264         """Return the number of entries in this pack index."""
265         return self._fan_out_table[-1]
266
267     def _unpack_entry(self, i):
268         """Unpack the i-th entry in the index file.
269
270         :return: Tuple with object name (SHA), offset in pack file and CRC32
271             checksum (if known).
272         """
273         raise NotImplementedError(self._unpack_entry)
274
275     def _unpack_name(self, i):
276         """Unpack the i-th name from the index file."""
277         raise NotImplementedError(self._unpack_name)
278
279     def _unpack_offset(self, i):
280         """Unpack the i-th object offset from the index file."""
281         raise NotImplementedError(self._unpack_offset)
282
283     def _unpack_crc32_checksum(self, i):
284         """Unpack the crc32 checksum for the i-th object from the index file."""
285         raise NotImplementedError(self._unpack_crc32_checksum)
286
287     def __iter__(self):
288         """Iterate over the SHAs in this pack."""
289         return imap(sha_to_hex, self._itersha())
290
291     def _itersha(self):
292         for i in range(len(self)):
293             yield self._unpack_name(i)
294
295     def objects_sha1(self):
296         """Return the hex SHA1 over all the shas of all objects in this pack.
297
298         :note: This is used for the filename of the pack.
299         """
300         return iter_sha1(self._itersha())
301
302     def iterentries(self):
303         """Iterate over the entries in this pack index.
304
305         :yields: tuples with object name, offset in packfile and crc32 checksum.
306         """
307         for i in range(len(self)):
308             yield self._unpack_entry(i)
309
310     def _read_fan_out_table(self, start_offset):
311         ret = []
312         for i in range(0x100):
313             fanout_entry = self._contents[start_offset+i*4:start_offset+(i+1)*4]
314             ret.append(struct.unpack(">L", fanout_entry)[0])
315         return ret
316
317     def check(self):
318         """Check that the stored checksum matches the actual checksum."""
319         # TODO: Check pack contents, too
320         actual = self.calculate_checksum()
321         stored = self.get_stored_checksum()
322         if actual != stored:
323             raise ChecksumMismatch(stored, actual)
324
325     def calculate_checksum(self):
326         """Calculate the SHA1 checksum over this pack index.
327
328         :return: This is a 20-byte binary digest
329         """
330         return make_sha(self._contents[:-20]).digest()
331
332     def get_pack_checksum(self):
333         """Return the SHA1 checksum stored for the corresponding packfile.
334
335         :return: 20-byte binary digest
336         """
337         return str(self._contents[-40:-20])
338
339     def get_stored_checksum(self):
340         """Return the SHA1 checksum stored for this index.
341
342         :return: 20-byte binary digest
343         """
344         return str(self._contents[-20:])
345
346     def object_index(self, sha):
347         """Return the index in to the corresponding packfile for the object.
348
349         Given the name of an object it will return the offset that object
350         lives at within the corresponding pack file. If the pack file doesn't
351         have the object then None will be returned.
352         """
353         if len(sha) == 40:
354             sha = hex_to_sha(sha)
355         return self._object_index(sha)
356
357     def _object_index(self, sha):
358         """See object_index.
359
360         :param sha: A *binary* SHA string. (20 characters long)_
361         """
362         assert len(sha) == 20
363         idx = ord(sha[0])
364         if idx == 0:
365             start = 0
366         else:
367             start = self._fan_out_table[idx-1]
368         end = self._fan_out_table[idx]
369         i = bisect_find_sha(start, end, sha, self._unpack_name)
370         if i is None:
371             raise KeyError(sha)
372         return self._unpack_offset(i)
373
374
375 class PackIndex1(PackIndex):
376     """Version 1 Pack Index."""
377
378     def __init__(self, filename, file=None, contents=None, size=None):
379         PackIndex.__init__(self, filename, file, contents, size)
380         self.version = 1
381         self._fan_out_table = self._read_fan_out_table(0)
382
383     def _unpack_entry(self, i):
384         (offset, name) = unpack_from(">L20s", self._contents,
385                                      (0x100 * 4) + (i * 24))
386         return (name, offset, None)
387
388     def _unpack_name(self, i):
389         offset = (0x100 * 4) + (i * 24) + 4
390         return self._contents[offset:offset+20]
391
392     def _unpack_offset(self, i):
393         offset = (0x100 * 4) + (i * 24)
394         return unpack_from(">L", self._contents, offset)[0]
395
396     def _unpack_crc32_checksum(self, i):
397         # Not stored in v1 index files
398         return None
399
400
401 class PackIndex2(PackIndex):
402     """Version 2 Pack Index."""
403
404     def __init__(self, filename, file=None, contents=None, size=None):
405         PackIndex.__init__(self, filename, file, contents, size)
406         assert self._contents[:4] == '\377tOc', "Not a v2 pack index file"
407         (self.version, ) = unpack_from(">L", self._contents, 4)
408         assert self.version == 2, "Version was %d" % self.version
409         self._fan_out_table = self._read_fan_out_table(8)
410         self._name_table_offset = 8 + 0x100 * 4
411         self._crc32_table_offset = self._name_table_offset + 20 * len(self)
412         self._pack_offset_table_offset = (self._crc32_table_offset +
413                                           4 * len(self))
414
415     def _unpack_entry(self, i):
416         return (self._unpack_name(i), self._unpack_offset(i),
417                 self._unpack_crc32_checksum(i))
418
419     def _unpack_name(self, i):
420         offset = self._name_table_offset + i * 20
421         return self._contents[offset:offset+20]
422
423     def _unpack_offset(self, i):
424         offset = self._pack_offset_table_offset + i * 4
425         return unpack_from(">L", self._contents, offset)[0]
426
427     def _unpack_crc32_checksum(self, i):
428         return unpack_from(">L", self._contents,
429                           self._crc32_table_offset + i * 4)[0]
430
431
432 def read_pack_header(read):
433     """Read the header of a pack file.
434
435     :param read: Read function
436     """
437     header = read(12)
438     assert header[:4] == "PACK"
439     (version,) = unpack_from(">L", header, 4)
440     assert version in (2, 3), "Version was %d" % version
441     (num_objects,) = unpack_from(">L", header, 8)
442     return (version, num_objects)
443
444
445 def chunks_length(chunks):
446     return sum(imap(len, chunks))
447
448
449 def unpack_object(read_all, read_some=None):
450     """Unpack a Git object.
451
452     :param read_all: Read function that blocks until the number of requested
453         bytes are read.
454     :param read_some: Read function that returns at least one byte, but may not
455         return the number of bytes requested.
456     :return: tuple with type, uncompressed data, compressed size and tail data.
457     """
458     if read_some is None:
459         read_some = read_all
460     bytes = take_msb_bytes(read_all)
461     type = (bytes[0] >> 4) & 0x07
462     size = bytes[0] & 0x0f
463     for i, byte in enumerate(bytes[1:]):
464         size += (byte & 0x7f) << ((i * 7) + 4)
465     raw_base = len(bytes)
466     if type == OFS_DELTA:
467         bytes = take_msb_bytes(read_all)
468         raw_base += len(bytes)
469         assert not (bytes[-1] & 0x80)
470         delta_base_offset = bytes[0] & 0x7f
471         for byte in bytes[1:]:
472             delta_base_offset += 1
473             delta_base_offset <<= 7
474             delta_base_offset += (byte & 0x7f)
475         uncomp, comp_len, unused = read_zlib_chunks(read_some, size)
476         assert size == chunks_length(uncomp)
477         return type, (delta_base_offset, uncomp), comp_len+raw_base, unused
478     elif type == REF_DELTA:
479         basename = read_all(20)
480         raw_base += 20
481         uncomp, comp_len, unused = read_zlib_chunks(read_some, size)
482         assert size == chunks_length(uncomp)
483         return type, (basename, uncomp), comp_len+raw_base, unused
484     else:
485         uncomp, comp_len, unused = read_zlib_chunks(read_some, size)
486         assert chunks_length(uncomp) == size
487         return type, uncomp, comp_len+raw_base, unused
488
489
490 def _compute_object_size((num, obj)):
491     """Compute the size of a unresolved object for use with LRUSizeCache."""
492     if num in DELTA_TYPES:
493         return chunks_length(obj[1])
494     return chunks_length(obj)
495
496
497 def obj_sha(type, chunks):
498     """Compute the SHA for a numeric type and object chunks."""
499     sha = make_sha()
500     sha.update(object_header(type, chunks_length(chunks)))
501     for chunk in chunks:
502         sha.update(chunk)
503     return sha.digest()
504
505
506 class PackData(object):
507     """The data contained in a packfile.
508
509     Pack files can be accessed both sequentially for exploding a pack, and
510     directly with the help of an index to retrieve a specific object.
511
512     The objects within are either complete or a delta aginst another.
513
514     The header is variable length. If the MSB of each byte is set then it
515     indicates that the subsequent byte is still part of the header.
516     For the first byte the next MS bits are the type, which tells you the type
517     of object, and whether it is a delta. The LS byte is the lowest bits of the
518     size. For each subsequent byte the LS 7 bits are the next MS bits of the
519     size, i.e. the last byte of the header contains the MS bits of the size.
520
521     For the complete objects the data is stored as zlib deflated data.
522     The size in the header is the uncompressed object size, so to uncompress
523     you need to just keep feeding data to zlib until you get an object back,
524     or it errors on bad data. This is done here by just giving the complete
525     buffer from the start of the deflated object on. This is bad, but until I
526     get mmap sorted out it will have to do.
527
528     Currently there are no integrity checks done. Also no attempt is made to
529     try and detect the delta case, or a request for an object at the wrong
530     position.  It will all just throw a zlib or KeyError.
531     """
532
533     def __init__(self, filename, file=None, size=None):
534         """Create a PackData object representing the pack in the given filename.
535
536         The file must exist and stay readable until the object is disposed of. It
537         must also stay the same size. It will be mapped whenever needed.
538
539         Currently there is a restriction on the size of the pack as the python
540         mmap implementation is flawed.
541         """
542         self._filename = filename
543         self._size = size
544         self._header_size = 12
545         if file is None:
546             self._file = GitFile(self._filename, 'rb')
547         else:
548             self._file = file
549         (version, self._num_objects) = read_pack_header(self._file.read)
550         self._offset_cache = LRUSizeCache(1024*1024*20,
551             compute_size=_compute_object_size)
552         self.pack = None
553
554     @classmethod
555     def from_file(cls, file, size):
556         return cls(str(file), file=file, size=size)
557
558     @classmethod
559     def from_path(cls, path):
560         return cls(filename=path)
561
562     def close(self):
563         self._file.close()
564
565     def __del__(self):
566         self.close()
567
568     def _get_size(self):
569         if self._size is not None:
570             return self._size
571         self._size = os.path.getsize(self._filename)
572         if self._size < self._header_size:
573             errmsg = ("%s is too small for a packfile (%d < %d)" %
574                       (self._filename, self._size, self._header_size))
575             raise AssertionError(errmsg)
576         return self._size
577
578     def __len__(self):
579         """Returns the number of objects in this pack."""
580         return self._num_objects
581
582     def calculate_checksum(self):
583         """Calculate the checksum for this pack.
584
585         :return: 20-byte binary SHA1 digest
586         """
587         s = make_sha()
588         self._file.seek(0)
589         todo = self._get_size() - 20
590         while todo > 0:
591             x = self._file.read(min(todo, 1<<16))
592             s.update(x)
593             todo -= len(x)
594         return s.digest()
595
596     def get_ref(self, sha):
597         """Get the object for a ref SHA, only looking in this pack."""
598         # TODO: cache these results
599         if self.pack is None:
600             raise KeyError(sha)
601         offset = self.pack.index.object_index(sha)
602         if not offset:
603             raise KeyError(sha)
604         type, obj = self.get_object_at(offset)
605         return offset, type, obj
606
607     def resolve_object(self, offset, type, obj, get_ref=None):
608         """Resolve an object, possibly resolving deltas when necessary.
609
610         :return: Tuple with object type and contents.
611         """
612         if type not in DELTA_TYPES:
613             return type, obj
614
615         if get_ref is None:
616             get_ref = self.get_ref
617         if type == OFS_DELTA:
618             (delta_offset, delta) = obj
619             # TODO: clean up asserts and replace with nicer error messages
620             assert isinstance(offset, int)
621             assert isinstance(delta_offset, int)
622             base_offset = offset-delta_offset
623             type, base_obj = self.get_object_at(base_offset)
624             assert isinstance(type, int)
625         elif type == REF_DELTA:
626             (basename, delta) = obj
627             assert isinstance(basename, str) and len(basename) == 20
628             base_offset, type, base_obj = get_ref(basename)
629             assert isinstance(type, int)
630         type, base_chunks = self.resolve_object(base_offset, type, base_obj)
631         chunks = apply_delta(base_chunks, delta)
632         # TODO(dborowitz): This can result in poor performance if large base
633         # objects are separated from deltas in the pack. We should reorganize
634         # so that we apply deltas to all objects in a chain one after the other
635         # to optimize cache performance.
636         if offset is not None:
637             self._offset_cache[offset] = type, chunks
638         return type, chunks
639
640     def iterobjects(self, progress=None):
641
642         class ObjectIterator(object):
643
644             def __init__(self, pack):
645                 self.i = 0
646                 self.offset = pack._header_size
647                 self.num = len(pack)
648                 self.map = pack._file
649
650             def __iter__(self):
651                 return self
652
653             def __len__(self):
654                 return self.num
655
656             def next(self):
657                 if self.i == self.num:
658                     raise StopIteration
659                 self.map.seek(self.offset)
660                 (type, obj, total_size, unused) = unpack_object(self.map.read)
661                 self.map.seek(self.offset)
662                 crc32 = zlib.crc32(self.map.read(total_size)) & 0xffffffff
663                 ret = (self.offset, type, obj, crc32)
664                 self.offset += total_size
665                 if progress:
666                     progress(self.i, self.num)
667                 self.i+=1
668                 return ret
669         return ObjectIterator(self)
670
671     def iterentries(self, progress=None):
672         """Yield entries summarizing the contents of this pack.
673
674         :param progress: Progress function, called with current and total object
675             count.
676         :yields: tuples with (sha, offset, crc32)
677         """
678         for offset, type, obj, crc32 in self.iterobjects(progress=progress):
679             assert isinstance(offset, int)
680             assert isinstance(type, int)
681             assert isinstance(obj, list) or isinstance(obj, tuple)
682             type, obj = self.resolve_object(offset, type, obj)
683             yield obj_sha(type, obj), offset, crc32
684
685     def sorted_entries(self, progress=None):
686         """Return entries in this pack, sorted by SHA.
687
688         :param progress: Progress function, called with current and total object
689             count
690         :return: List of tuples with (sha, offset, crc32)
691         """
692         ret = list(self.iterentries(progress=progress))
693         ret.sort()
694         return ret
695
696     def create_index_v1(self, filename, progress=None):
697         """Create a version 1 file for this data file.
698
699         :param filename: Index filename.
700         :param progress: Progress report function
701         """
702         entries = self.sorted_entries(progress=progress)
703         write_pack_index_v1(filename, entries, self.calculate_checksum())
704
705     def create_index_v2(self, filename, progress=None):
706         """Create a version 2 index file for this data file.
707
708         :param filename: Index filename.
709         :param progress: Progress report function
710         """
711         entries = self.sorted_entries(progress=progress)
712         write_pack_index_v2(filename, entries, self.calculate_checksum())
713
714     def create_index(self, filename, progress=None,
715                      version=2):
716         """Create an  index file for this data file.
717
718         :param filename: Index filename.
719         :param progress: Progress report function
720         """
721         if version == 1:
722             self.create_index_v1(filename, progress)
723         elif version == 2:
724             self.create_index_v2(filename, progress)
725         else:
726             raise ValueError("unknown index format %d" % version)
727
728     def get_stored_checksum(self):
729         """Return the expected checksum stored in this pack."""
730         self._file.seek(self._get_size()-20)
731         return self._file.read(20)
732
733     def check(self):
734         """Check the consistency of this pack."""
735         actual = self.calculate_checksum()
736         stored = self.get_stored_checksum()
737         if actual != stored:
738             raise ChecksumMismatch(stored, actual)
739
740     def get_object_at(self, offset):
741         """Given an offset in to the packfile return the object that is there.
742
743         Using the associated index the location of an object can be looked up,
744         and then the packfile can be asked directly for that object using this
745         function.
746         """
747         if offset in self._offset_cache:
748             return self._offset_cache[offset]
749         assert isinstance(offset, long) or isinstance(offset, int),\
750                 "offset was %r" % offset
751         assert offset >= self._header_size
752         self._file.seek(offset)
753         return unpack_object(self._file.read)[:2]
754
755
756 class ThinPackData(PackData):
757     """PackData for thin packs, which require an ObjectStore for resolving."""
758
759     def __init__(self, store, *args, **kwargs):
760         super(ThinPackData, self).__init__(*args, **kwargs)
761         self.store = store
762
763     def get_ref(self, sha):
764         """Resolve a reference looking in both this pack and the store."""
765         try:
766             # As part of completing a pack we create a Pack object with a
767             # ThinPackData and a full PackIndex, so check in the index first if
768             # possible.
769             # TODO(dborowitz): reevaluate this when the pack completion code is
770             # rewritten.
771             return super(ThinPackData, self).get_ref(sha)
772         except KeyError:
773             type, obj = self.store.get_raw(sha)
774             return None, type, obj
775
776     def iterentries(self, progress=None):
777         """Yield entries summarizing the contents of this pack.
778
779         :param progress: Progress function, called with current and
780             total object count.
781
782         This will yield tuples with (sha, offset, crc32)
783         """
784         found = {}
785         postponed = defaultdict(list)
786
787         class Postpone(Exception):
788             """Raised to postpone delta resolving."""
789
790             def __init__(self, sha):
791                 self.sha = sha
792
793         def get_ref_text(sha):
794             assert len(sha) == 20
795             if sha in found:
796                 offset = found[sha]
797                 type, obj = self.get_object_at(offset)
798                 return offset, type, obj
799             try:
800                 return self.get_ref(sha)
801             except KeyError:
802                 raise Postpone(sha)
803
804         extra = []
805         todo = chain(self.iterobjects(progress=progress), extra)
806         for (offset, type, obj, crc32) in todo:
807             assert isinstance(offset, int)
808             if obj is None:
809                 # Inflate postponed delta
810                 obj, type = self.get_object_at(offset)
811             assert isinstance(type, int)
812             assert isinstance(obj, list) or isinstance(obj, tuple)
813             try:
814                 type, obj = self.resolve_object(offset, type, obj, get_ref_text)
815             except Postpone, e:
816                 # Save memory by not storing the inflated obj in postponed
817                 postponed[e.sha].append((offset, type, None, crc32))
818             else:
819                 sha = obj_sha(type, obj)
820                 found[sha] = offset
821                 yield sha, offset, crc32
822                 extra.extend(postponed.pop(sha, []))
823         if postponed:
824             raise KeyError([sha_to_hex(h) for h in postponed.keys()])
825
826
827 class SHA1Reader(object):
828     """Wrapper around a file-like object that remembers the SHA1 of its data."""
829
830     def __init__(self, f):
831         self.f = f
832         self.sha1 = make_sha("")
833
834     def read(self, num=None):
835         data = self.f.read(num)
836         self.sha1.update(data)
837         return data
838
839     def check_sha(self):
840         stored = self.f.read(20)
841         if stored != self.sha1.digest():
842             raise ChecksumMismatch(self.sha1.hexdigest(), sha_to_hex(stored))
843
844     def close(self):
845         return self.f.close()
846
847     def tell(self):
848         return self.f.tell()
849
850
851 class SHA1Writer(object):
852     """Wrapper around a file-like object that remembers the SHA1 of its data."""
853
854     def __init__(self, f):
855         self.f = f
856         self.sha1 = make_sha("")
857
858     def write(self, data):
859         self.sha1.update(data)
860         self.f.write(data)
861
862     def write_sha(self):
863         sha = self.sha1.digest()
864         assert len(sha) == 20
865         self.f.write(sha)
866         return sha
867
868     def close(self):
869         sha = self.write_sha()
870         self.f.close()
871         return sha
872
873     def tell(self):
874         return self.f.tell()
875
876
877 def write_pack_object(f, type, object):
878     """Write pack object to a file.
879
880     :param f: File to write to
881     :param type: Numeric type of the object
882     :param object: Object to write
883     :return: Tuple with offset at which the object was written, and crc32
884     """
885     offset = f.tell()
886     packed_data_hdr = ""
887     if type == OFS_DELTA:
888         (delta_base_offset, object) = object
889     elif type == REF_DELTA:
890         (basename, object) = object
891     size = len(object)
892     c = (type << 4) | (size & 15)
893     size >>= 4
894     while size:
895         packed_data_hdr += (chr(c | 0x80))
896         c = size & 0x7f
897         size >>= 7
898     packed_data_hdr += chr(c)
899     if type == OFS_DELTA:
900         ret = [delta_base_offset & 0x7f]
901         delta_base_offset >>= 7
902         while delta_base_offset:
903             delta_base_offset -= 1
904             ret.insert(0, 0x80 | (delta_base_offset & 0x7f))
905             delta_base_offset >>= 7
906         packed_data_hdr += "".join([chr(x) for x in ret])
907     elif type == REF_DELTA:
908         assert len(basename) == 20
909         packed_data_hdr += basename
910     packed_data = packed_data_hdr + zlib.compress(object)
911     f.write(packed_data)
912     return (offset, (zlib.crc32(packed_data) & 0xffffffff))
913
914
915 def write_pack(filename, objects, num_objects):
916     """Write a new pack data file.
917
918     :param filename: Path to the new pack file (without .pack extension)
919     :param objects: Iterable over (object, path) tuples to write
920     :param num_objects: Number of objects to write
921     """
922     f = GitFile(filename + ".pack", 'wb')
923     try:
924         entries, data_sum = write_pack_data(f, objects, num_objects)
925     finally:
926         f.close()
927     entries.sort()
928     write_pack_index_v2(filename + ".idx", entries, data_sum)
929
930
931 def write_pack_data(f, objects, num_objects, window=10):
932     """Write a new pack file.
933
934     :param filename: The filename of the new pack file.
935     :param objects: List of objects to write (tuples with object and path)
936     :return: List with (name, offset, crc32 checksum) entries, pack checksum
937     """
938     recency = list(objects)
939     # FIXME: Somehow limit delta depth
940     # FIXME: Make thin-pack optional (its not used when cloning a pack)
941     # Build a list of objects ordered by the magic Linus heuristic
942     # This helps us find good objects to diff against us
943     magic = []
944     for obj, path in recency:
945         magic.append( (obj.type_num, path, 1, -obj.raw_length(), obj) )
946     magic.sort()
947     # Build a map of objects and their index in magic - so we can find
948     # preceeding objects to diff against
949     offs = {}
950     for i in range(len(magic)):
951         offs[magic[i][4]] = i
952     # Write the pack
953     entries = []
954     f = SHA1Writer(f)
955     f.write("PACK")               # Pack header
956     f.write(struct.pack(">L", 2)) # Pack version
957     f.write(struct.pack(">L", num_objects)) # Number of objects in pack
958     for o, path in recency:
959         sha1 = o.sha().digest()
960         orig_t = o.type_num
961         raw = o.as_raw_string()
962         winner = raw
963         t = orig_t
964         #for i in range(offs[o]-window, window):
965         #    if i < 0 or i >= len(offs): continue
966         #    b = magic[i][4]
967         #    if b.type_num != orig_t: continue
968         #    base = b.as_raw_string()
969         #    delta = create_delta(base, raw)
970         #    if len(delta) < len(winner):
971         #        winner = delta
972         #        t = 6 if magic[i][2] == 1 else 7
973         offset, crc32 = write_pack_object(f, t, winner)
974         entries.append((sha1, offset, crc32))
975     return entries, f.write_sha()
976
977
978 def write_pack_index_v1(filename, entries, pack_checksum):
979     """Write a new pack index file.
980
981     :param filename: The filename of the new pack index file.
982     :param entries: List of tuples with object name (sha), offset_in_pack,
983         and crc32_checksum.
984     :param pack_checksum: Checksum of the pack file.
985     """
986     f = GitFile(filename, 'wb')
987     try:
988         f = SHA1Writer(f)
989         fan_out_table = defaultdict(lambda: 0)
990         for (name, offset, entry_checksum) in entries:
991             fan_out_table[ord(name[0])] += 1
992         # Fan-out table
993         for i in range(0x100):
994             f.write(struct.pack(">L", fan_out_table[i]))
995             fan_out_table[i+1] += fan_out_table[i]
996         for (name, offset, entry_checksum) in entries:
997             f.write(struct.pack(">L20s", offset, name))
998         assert len(pack_checksum) == 20
999         f.write(pack_checksum)
1000     finally:
1001         f.close()
1002
1003
1004 def create_delta(base_buf, target_buf):
1005     """Use python difflib to work out how to transform base_buf to target_buf.
1006
1007     :param base_buf: Base buffer
1008     :param target_buf: Target buffer
1009     """
1010     assert isinstance(base_buf, str)
1011     assert isinstance(target_buf, str)
1012     out_buf = ""
1013     # write delta header
1014     def encode_size(size):
1015         ret = ""
1016         c = size & 0x7f
1017         size >>= 7
1018         while size:
1019             ret += chr(c | 0x80)
1020             c = size & 0x7f
1021             size >>= 7
1022         ret += chr(c)
1023         return ret
1024     out_buf += encode_size(len(base_buf))
1025     out_buf += encode_size(len(target_buf))
1026     # write out delta opcodes
1027     seq = difflib.SequenceMatcher(a=base_buf, b=target_buf)
1028     for opcode, i1, i2, j1, j2 in seq.get_opcodes():
1029         # Git patch opcodes don't care about deletes!
1030         #if opcode == "replace" or opcode == "delete":
1031         #    pass
1032         if opcode == "equal":
1033             # If they are equal, unpacker will use data from base_buf
1034             # Write out an opcode that says what range to use
1035             scratch = ""
1036             op = 0x80
1037             o = i1
1038             for i in range(4):
1039                 if o & 0xff << i*8:
1040                     scratch += chr((o >> i*8) & 0xff)
1041                     op |= 1 << i
1042             s = i2 - i1
1043             for i in range(2):
1044                 if s & 0xff << i*8:
1045                     scratch += chr((s >> i*8) & 0xff)
1046                     op |= 1 << (4+i)
1047             out_buf += chr(op)
1048             out_buf += scratch
1049         if opcode == "replace" or opcode == "insert":
1050             # If we are replacing a range or adding one, then we just
1051             # output it to the stream (prefixed by its size)
1052             s = j2 - j1
1053             o = j1
1054             while s > 127:
1055                 out_buf += chr(127)
1056                 out_buf += target_buf[o:o+127]
1057                 s -= 127
1058                 o += 127
1059             out_buf += chr(s)
1060             out_buf += target_buf[o:o+s]
1061     return out_buf
1062
1063
1064 def apply_delta(src_buf, delta):
1065     """Based on the similar function in git's patch-delta.c.
1066
1067     :param src_buf: Source buffer
1068     :param delta: Delta instructions
1069     """
1070     if type(src_buf) != str:
1071         src_buf = "".join(src_buf)
1072     if type(delta) != str:
1073         delta = "".join(delta)
1074     out = []
1075     index = 0
1076     delta_length = len(delta)
1077     def get_delta_header_size(delta, index):
1078         size = 0
1079         i = 0
1080         while delta:
1081             cmd = ord(delta[index])
1082             index += 1
1083             size |= (cmd & ~0x80) << i
1084             i += 7
1085             if not cmd & 0x80:
1086                 break
1087         return size, index
1088     src_size, index = get_delta_header_size(delta, index)
1089     dest_size, index = get_delta_header_size(delta, index)
1090     assert src_size == len(src_buf), "%d vs %d" % (src_size, len(src_buf))
1091     while index < delta_length:
1092         cmd = ord(delta[index])
1093         index += 1
1094         if cmd & 0x80:
1095             cp_off = 0
1096             for i in range(4):
1097                 if cmd & (1 << i):
1098                     x = ord(delta[index])
1099                     index += 1
1100                     cp_off |= x << (i * 8)
1101             cp_size = 0
1102             for i in range(3):
1103                 if cmd & (1 << (4+i)):
1104                     x = ord(delta[index])
1105                     index += 1
1106                     cp_size |= x << (i * 8)
1107             if cp_size == 0:
1108                 cp_size = 0x10000
1109             if (cp_off + cp_size < cp_size or
1110                 cp_off + cp_size > src_size or
1111                 cp_size > dest_size):
1112                 break
1113             out.append(src_buf[cp_off:cp_off+cp_size])
1114         elif cmd != 0:
1115             out.append(delta[index:index+cmd])
1116             index += cmd
1117         else:
1118             raise ApplyDeltaError("Invalid opcode 0")
1119
1120     if index != delta_length:
1121         raise ApplyDeltaError("delta not empty: %r" % delta[index:])
1122
1123     if dest_size != chunks_length(out):
1124         raise ApplyDeltaError("dest size incorrect")
1125
1126     return out
1127
1128
1129 def write_pack_index_v2(filename, entries, pack_checksum):
1130     """Write a new pack index file.
1131
1132     :param filename: The filename of the new pack index file.
1133     :param entries: List of tuples with object name (sha), offset_in_pack, and
1134         crc32_checksum.
1135     :param pack_checksum: Checksum of the pack file.
1136     """
1137     f = GitFile(filename, 'wb')
1138     try:
1139         f = SHA1Writer(f)
1140         f.write('\377tOc') # Magic!
1141         f.write(struct.pack(">L", 2))
1142         fan_out_table = defaultdict(lambda: 0)
1143         for (name, offset, entry_checksum) in entries:
1144             fan_out_table[ord(name[0])] += 1
1145         # Fan-out table
1146         for i in range(0x100):
1147             f.write(struct.pack(">L", fan_out_table[i]))
1148             fan_out_table[i+1] += fan_out_table[i]
1149         for (name, offset, entry_checksum) in entries:
1150             f.write(name)
1151         for (name, offset, entry_checksum) in entries:
1152             f.write(struct.pack(">L", entry_checksum))
1153         for (name, offset, entry_checksum) in entries:
1154             # FIXME: handle if MSBit is set in offset
1155             f.write(struct.pack(">L", offset))
1156         # FIXME: handle table for pack files > 8 Gb
1157         assert len(pack_checksum) == 20
1158         f.write(pack_checksum)
1159     finally:
1160         f.close()
1161
1162
1163 class Pack(object):
1164     """A Git pack object."""
1165
1166     def __init__(self, basename):
1167         self._basename = basename
1168         self._data_path = self._basename + ".pack"
1169         self._idx_path = self._basename + ".idx"
1170         self._data = None
1171         self._idx = None
1172
1173     @classmethod
1174     def from_objects(self, data, idx):
1175         """Create a new pack object from pack data and index objects."""
1176         ret = Pack("")
1177         ret._data = data
1178         ret._idx = idx
1179         data.pack = ret
1180         return ret
1181
1182     def name(self):
1183         """The SHA over the SHAs of the objects in this pack."""
1184         return self.index.objects_sha1()
1185
1186     @property
1187     def data(self):
1188         """The pack data object being used."""
1189         if self._data is None:
1190             self._data = PackData(self._data_path)
1191             self._data.pack = self
1192             assert len(self.index) == len(self._data)
1193             idx_stored_checksum = self.index.get_pack_checksum()
1194             data_stored_checksum = self._data.get_stored_checksum()
1195             if idx_stored_checksum != data_stored_checksum:
1196                 raise ChecksumMismatch(sha_to_hex(idx_stored_checksum),
1197                                        sha_to_hex(data_stored_checksum))
1198         return self._data
1199
1200     @property
1201     def index(self):
1202         """The index being used.
1203
1204         :note: This may be an in-memory index
1205         """
1206         if self._idx is None:
1207             self._idx = load_pack_index(self._idx_path)
1208         return self._idx
1209
1210     def close(self):
1211         if self._data is not None:
1212             self._data.close()
1213         self.index.close()
1214
1215     def __eq__(self, other):
1216         return type(self) == type(other) and self.index == other.index
1217
1218     def __len__(self):
1219         """Number of entries in this pack."""
1220         return len(self.index)
1221
1222     def __repr__(self):
1223         return "%s(%r)" % (self.__class__.__name__, self._basename)
1224
1225     def __iter__(self):
1226         """Iterate over all the sha1s of the objects in this pack."""
1227         return iter(self.index)
1228
1229     def check(self):
1230         """Check the integrity of this pack.
1231
1232         :raise ChecksumMismatch: if a checksum for the index or data is wrong
1233         """
1234         self.index.check()
1235         self.data.check()
1236
1237     def get_stored_checksum(self):
1238         return self.data.get_stored_checksum()
1239
1240     def __contains__(self, sha1):
1241         """Check whether this pack contains a particular SHA1."""
1242         try:
1243             self.index.object_index(sha1)
1244             return True
1245         except KeyError:
1246             return False
1247
1248     def get_raw(self, sha1):
1249         offset = self.index.object_index(sha1)
1250         obj_type, obj = self.data.get_object_at(offset)
1251         if type(offset) is long:
1252           offset = int(offset)
1253         type_num, chunks = self.data.resolve_object(offset, obj_type, obj)
1254         return type_num, "".join(chunks)
1255
1256     def __getitem__(self, sha1):
1257         """Retrieve the specified SHA1."""
1258         type, uncomp = self.get_raw(sha1)
1259         return ShaFile.from_raw_string(type, uncomp)
1260
1261     def iterobjects(self):
1262         """Iterate over the objects in this pack."""
1263         for offset, type, obj, crc32 in self.data.iterobjects():
1264             assert isinstance(offset, int)
1265             yield ShaFile.from_raw_chunks(
1266                     *self.data.resolve_object(offset, type, obj))
1267
1268
1269 try:
1270     from dulwich._pack import apply_delta, bisect_find_sha
1271 except ImportError:
1272     pass