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