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 Jelmer Vernooij <jelmer@samba.org>
   4 # The code is loosely based on that in the sha1_file.c file from git itself,
   5 # which is Copyright (C) Linus Torvalds, 2005 and distributed under the
   6 # GPL version 2.
   7 #
   8 # This program is free software; you can redistribute it and/or
   9 # modify it under the terms of the GNU General Public License
  10 # as published by the Free Software Foundation; version 2
  11 # of the License.
  12 #
  13 # This program is distributed in the hope that it will be useful,
  14 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 # GNU General Public License for more details.
  17 #
  18 # You should have received a copy of the GNU General Public License
  19 # along with this program; if not, write to the Free Software
  20 # Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
  21 # MA  02110-1301, USA.
  22
  23 """Classes for dealing with packed git objects.
  24
  25 A pack is a compact representation of a bunch of objects, stored
  26 using deltas where possible.
  27
  28 They have two parts, the pack file, which stores the data, and an index
  29 that tells you where the data is.
  30
  31 To find an object you look in all of the index files 'til you find a
  32 match for the object name. You then use the pointer got from this as
  33 a pointer in to the corresponding packfile.
  34 """
  35
  36 from collections import defaultdict
  37 import hashlib
  38 from itertools import imap, izip
  39 import mmap
  40 import os
  41 import sha
  42 import struct
  43 import sys
  44 import zlib
  45
  46 from objects import (
  47         ShaFile,
  48         )
  49 from errors import ApplyDeltaError
  50
  51 supports_mmap_offset = (sys.version_info[0] >= 3 or
  52         (sys.version_info[0] == 2 and sys.version_info[1] >= 6))
  53
  54
  55 def take_msb_bytes(map, offset):
  56     ret = []
  57     while len(ret) == 0 or ret[-1] & 0x80:
  58         ret.append(ord(map[offset]))
  59         offset += 1
  60     return ret
  61
  62
  63 def read_zlib(data, offset, dec_size):
  64     obj = zlib.decompressobj()
  65     x = ""
  66     fed = 0
  67     while obj.unused_data == "":
  68         base = offset+fed
  69         add = data[base:base+1024]
  70         fed += len(add)
  71         x += obj.decompress(add)
  72     assert len(x) == dec_size
  73     comp_len = fed-len(obj.unused_data)
  74     return x, comp_len
  75
  76
  77 def iter_sha1(iter):
  78     sha = hashlib.sha1()
  79     for name in iter:
  80         sha.update(name)
  81     return sha.hexdigest()
  82
  83
  84 def hex_to_sha(hex):
  85   """Convert a hex string to a binary sha string."""
  86   ret = ""
  87   for i in range(0, len(hex), 2):
  88     ret += chr(int(hex[i:i+2], 16))
  89   return ret
  90
  91 def sha_to_hex(sha):
  92   """Convert a binary sha string to a hex sha string."""
  93   ret = ""
  94   for i in sha:
  95       ret += "%02x" % ord(i)
  96   return ret
  97
  98 MAX_MMAP_SIZE = 256 * 1024 * 1024
  99
 100 def simple_mmap(f, offset, size, access=mmap.ACCESS_READ):
 101     """Simple wrapper for mmap() which always supports the offset parameter.
 102
 103     :param f: File object.
 104     :param offset: Offset in the file, from the beginning of the file.
 105     :param size: Size of the mmap'ed area
 106     :param access: Access mechanism.
 107     :return: MMAP'd area.
 108     """
 109     if offset+size > MAX_MMAP_SIZE and not supports_mmap_offset:
 110         raise AssertionError("%s is larger than 256 meg, and this version "
 111             "of Python does not support the offset argument to mmap().")
 112     if supports_mmap_offset:
 113         return mmap.mmap(f.fileno(), size, access=access, offset=offset)
 114     else:
 115         class ArraySkipper(object):
 116
 117             def __init__(self, array, offset):
 118                 self.array = array
 119                 self.offset = offset
 120
 121             def __getslice__(self, i, j):
 122                 return self.array[i+self.offset:j+self.offset]
 123
 124             def __getitem__(self, i):
 125                 return self.array[i+self.offset]
 126
 127             def __len__(self):
 128                 return len(self.array) - self.offset
 129
 130             def __str__(self):
 131                 return str(self.array[self.offset:])
 132
 133         mem = mmap.mmap(f.fileno(), size+offset, access=access)
 134         if offset == 0:
 135             return mem
 136         return ArraySkipper(mem, offset)
 137
 138
 139 def resolve_object(offset, type, obj, get_ref, get_offset):
 140   """Resolve an object, possibly resolving deltas when necessary."""
 141   if not type in (6, 7): # Not a delta
 142      return type, obj
 143
 144   if type == 6: # offset delta
 145      (delta_offset, delta) = obj
 146      assert isinstance(delta_offset, int)
 147      assert isinstance(delta, str)
 148      offset = offset-delta_offset
 149      type, base_obj = get_offset(offset)
 150      assert isinstance(type, int)
 151   elif type == 7: # ref delta
 152      (basename, delta) = obj
 153      assert isinstance(basename, str) and len(basename) == 20
 154      assert isinstance(delta, str)
 155      type, base_obj = get_ref(basename)
 156      assert isinstance(type, int)
 157   type, base_text = resolve_object(offset, type, base_obj, get_ref, get_offset)
 158   return type, apply_delta(base_text, delta)
 159
 160
 161 class PackIndex(object):
 162   """An index in to a packfile.
 163
 164   Given a sha id of an object a pack index can tell you the location in the
 165   packfile of that object if it has it.
 166
 167   To do the loop it opens the file, and indexes first 256 4 byte groups
 168   with the first byte of the sha id. The value in the four byte group indexed
 169   is the end of the group that shares the same starting byte. Subtract one
 170   from the starting byte and index again to find the start of the group.
 171   The values are sorted by sha id within the group, so do the math to find
 172   the start and end offset and then bisect in to find if the value is present.
 173   """
 174
 175   def __init__(self, filename):
 176     """Create a pack index object.
 177
 178     Provide it with the name of the index file to consider, and it will map
 179     it whenever required.
 180     """
 181     self._filename = filename
 182     # Take the size now, so it can be checked each time we map the file to
 183     # ensure that it hasn't changed.
 184     self._size = os.path.getsize(filename)
 185     self._file = open(filename, 'r')
 186     self._contents = simple_mmap(self._file, 0, self._size)
 187     if self._contents[:4] != '\377tOc':
 188         self.version = 1
 189         self._fan_out_table = self._read_fan_out_table(0)
 190     else:
 191         (self.version, ) = struct.unpack_from(">L", self._contents, 4)
 192         assert self.version in (2,), "Version was %d" % self.version
 193         self._fan_out_table = self._read_fan_out_table(8)
 194         self._name_table_offset = 8 + 0x100 * 4
 195         self._crc32_table_offset = self._name_table_offset + 20 * len(self)
 196         self._pack_offset_table_offset = self._crc32_table_offset + 4 * len(self)
 197
 198   def __eq__(self, other):
 199     if type(self) != type(other):
 200         return False
 201
 202     if self._fan_out_table != other._fan_out_table:
 203         return False
 204
 205     for (name1, _, _), (name2, _, _) in izip(self.iterentries(), other.iterentries()):
 206         if name1 != name2:
 207             return False
 208     return True
 209
 210   def close(self):
 211     self._file.close()
 212
 213   def __len__(self):
 214     """Return the number of entries in this pack index."""
 215     return self._fan_out_table[-1]
 216
 217   def _unpack_entry(self, i):
 218     """Unpack the i-th entry in the index file.
 219
 220     :return: Tuple with object name (SHA), offset in pack file and
 221           CRC32 checksum (if known)."""
 222     if self.version == 1:
 223         (offset, name) = struct.unpack_from(">L20s", self._contents,
 224             (0x100 * 4) + (i * 24))
 225         return (name, offset, None)
 226     else:
 227         return (self._unpack_name(i), self._unpack_offset(i),
 228                 self._unpack_crc32_checksum(i))
 229
 230   def _unpack_name(self, i):
 231     if self.version == 1:
 232         return self._unpack_entry(i)[0]
 233     else:
 234         return struct.unpack_from("20s", self._contents,
 235                                   self._name_table_offset + i * 20)[0]
 236
 237   def _unpack_offset(self, i):
 238     if self.version == 1:
 239         return self._unpack_entry(i)[1]
 240     else:
 241         return struct.unpack_from(">L", self._contents,
 242                                   self._pack_offset_table_offset + i * 4)[0]
 243
 244   def _unpack_crc32_checksum(self, i):
 245     if self.version == 1:
 246         return None
 247     else:
 248         return struct.unpack_from(">L", self._contents,
 249                                   self._crc32_table_offset + i * 4)[0]
 250
 251   def __iter__(self):
 252       return imap(sha_to_hex, self._itersha())
 253
 254   def _itersha(self):
 255     for i in range(len(self)):
 256         yield self._unpack_name(i)
 257
 258   def objects_sha1(self):
 259     return iter_sha1(self._itersha())
 260
 261   def iterentries(self):
 262     """Iterate over the entries in this pack index.
 263
 264     Will yield tuples with object name, offset in packfile and crc32 checksum.
 265     """
 266     for i in range(len(self)):
 267         yield self._unpack_entry(i)
 268
 269   def _read_fan_out_table(self, start_offset):
 270     ret = []
 271     for i in range(0x100):
 272         ret.append(struct.unpack(">L", self._contents[start_offset+i*4:start_offset+(i+1)*4])[0])
 273     return ret
 274
 275   def check(self):
 276     """Check that the stored checksum matches the actual checksum."""
 277     return self.calculate_checksum() == self.get_stored_checksums()[1]
 278
 279   def calculate_checksum(self):
 280     f = open(self._filename, 'r')
 281     try:
 282         return hashlib.sha1(self._contents[:-20]).digest()
 283     finally:
 284         f.close()
 285
 286   def get_stored_checksums(self):
 287     """Return the SHA1 checksums stored for the corresponding packfile and
 288     this header file itself."""
 289     return str(self._contents[-40:-20]), str(self._contents[-20:])
 290
 291   def object_index(self, sha):
 292     """Return the index in to the corresponding packfile for the object.
 293
 294     Given the name of an object it will return the offset that object lives
 295     at within the corresponding pack file. If the pack file doesn't have the
 296     object then None will be returned.
 297     """
 298     size = os.path.getsize(self._filename)
 299     assert size == self._size, "Pack index %s has changed size, I don't " \
 300          "like that" % self._filename
 301     if len(sha) == 40:
 302         sha = hex_to_sha(sha)
 303     return self._object_index(sha)
 304
 305   def _object_index(self, sha):
 306       """See object_index"""
 307       idx = ord(sha[0])
 308       if idx == 0:
 309           start = 0
 310       else:
 311           start = self._fan_out_table[idx-1]
 312       end = self._fan_out_table[idx]
 313       assert start <= end
 314       while start <= end:
 315         i = (start + end)/2
 316         file_sha = self._unpack_name(i)
 317         if file_sha < sha:
 318           start = i + 1
 319         elif file_sha > sha:
 320           end = i - 1
 321         else:
 322           return self._unpack_offset(i)
 323       return None
 324
 325
 326 class PackData(object):
 327   """The data contained in a packfile.
 328
 329   Pack files can be accessed both sequentially for exploding a pack, and
 330   directly with the help of an index to retrieve a specific object.
 331
 332   The objects within are either complete or a delta aginst another.
 333
 334   The header is variable length. If the MSB of each byte is set then it
 335   indicates that the subsequent byte is still part of the header.
 336   For the first byte the next MS bits are the type, which tells you the type
 337   of object, and whether it is a delta. The LS byte is the lowest bits of the
 338   size. For each subsequent byte the LS 7 bits are the next MS bits of the
 339   size, i.e. the last byte of the header contains the MS bits of the size.
 340
 341   For the complete objects the data is stored as zlib deflated data.
 342   The size in the header is the uncompressed object size, so to uncompress
 343   you need to just keep feeding data to zlib until you get an object back,
 344   or it errors on bad data. This is done here by just giving the complete
 345   buffer from the start of the deflated object on. This is bad, but until I
 346   get mmap sorted out it will have to do.
 347
 348   Currently there are no integrity checks done. Also no attempt is made to try
 349   and detect the delta case, or a request for an object at the wrong position.
 350   It will all just throw a zlib or KeyError.
 351   """
 352
 353   def __init__(self, filename):
 354     """Create a PackData object that represents the pack in the given filename.
 355
 356     The file must exist and stay readable until the object is disposed of. It
 357     must also stay the same size. It will be mapped whenever needed.
 358
 359     Currently there is a restriction on the size of the pack as the python
 360     mmap implementation is flawed.
 361     """
 362     self._filename = filename
 363     assert os.path.exists(filename), "%s is not a packfile" % filename
 364     self._size = os.path.getsize(filename)
 365     assert self._size >= 12, "%s is too small for a packfile" % filename
 366     self._header_size = self._read_header()
 367
 368   def _read_header(self):
 369     f = open(self._filename, 'rb')
 370     try:
 371         header = f.read(12)
 372         f.seek(self._size-20)
 373         self._stored_checksum = f.read(20)
 374     finally:
 375         f.close()
 376     assert header[:4] == "PACK"
 377     (version,) = struct.unpack_from(">L", header, 4)
 378     assert version in (2, 3), "Version was %d" % version
 379     (self._num_objects,) = struct.unpack_from(">L", header, 8)
 380     return 12 # Header size
 381
 382   def __len__(self):
 383       """Returns the number of objects in this pack."""
 384       return self._num_objects
 385
 386   def calculate_checksum(self):
 387     f = open(self._filename, 'rb')
 388     try:
 389         map = simple_mmap(f, 0, self._size)
 390         return hashlib.sha1(map[:-20]).digest()
 391     finally:
 392         f.close()
 393
 394   def iterobjects(self):
 395     offset = self._header_size
 396     f = open(self._filename, 'rb')
 397     for i in range(len(self)):
 398         map = simple_mmap(f, offset, self._size-offset)
 399         (type, obj, total_size) = self._unpack_object(map)
 400         yield offset, type, obj
 401         offset += total_size
 402     f.close()
 403
 404   def iterentries(self):
 405     found = {}
 406     at = {}
 407     postponed = defaultdict(list)
 408     class Postpone(Exception):
 409         """Raised to postpone delta resolving."""
 410
 411     def get_ref_text(sha):
 412         if sha in found:
 413             return found[sha]
 414         raise Postpone, (sha, )
 415     todo = list(self.iterobjects())
 416     while todo:
 417       (offset, type, obj) = todo.pop(0)
 418       at[offset] = (type, obj)
 419       assert isinstance(offset, int)
 420       assert isinstance(type, int)
 421       assert isinstance(obj, tuple) or isinstance(obj, str)
 422       try:
 423         type, obj = resolve_object(offset, type, obj, get_ref_text,
 424             at.__getitem__)
 425       except Postpone, (sha, ):
 426         postponed[sha].append((offset, type, obj))
 427       else:
 428         shafile = ShaFile.from_raw_string(type, obj)
 429         sha = shafile.sha().digest()
 430         found[sha] = (type, obj)
 431         yield sha, offset, shafile.crc32()
 432         todo += postponed.get(sha, [])
 433     if postponed:
 434         raise KeyError([sha_to_hex(h) for h in postponed.keys()])
 435
 436   def sorted_entries(self):
 437     ret = list(self.iterentries())
 438     ret.sort()
 439     return ret
 440
 441   def create_index_v1(self, filename):
 442     entries = self.sorted_entries()
 443     write_pack_index_v1(filename, entries, self.calculate_checksum())
 444
 445   def create_index_v2(self, filename):
 446     entries = self.sorted_entries()
 447     write_pack_index_v2(filename, entries, self.calculate_checksum())
 448
 449   def get_stored_checksum(self):
 450     return self._stored_checksum
 451
 452   def check(self):
 453     return (self.calculate_checksum() == self.get_stored_checksum())
 454
 455   def get_object_at(self, offset):
 456     """Given an offset in to the packfile return the object that is there.
 457
 458     Using the associated index the location of an object can be looked up, and
 459     then the packfile can be asked directly for that object using this
 460     function.
 461     """
 462     assert isinstance(offset, long) or isinstance(offset, int),\
 463             "offset was %r" % offset
 464     assert offset >= self._header_size
 465     size = os.path.getsize(self._filename)
 466     assert size == self._size, "Pack data %s has changed size, I don't " \
 467          "like that" % self._filename
 468     f = open(self._filename, 'rb')
 469     try:
 470       map = simple_mmap(f, offset, size-offset)
 471       return self._unpack_object(map)[:2]
 472     finally:
 473       f.close()
 474
 475   def _unpack_object(self, map):
 476     bytes = take_msb_bytes(map, 0)
 477     type = (bytes[0] >> 4) & 0x07
 478     size = bytes[0] & 0x0f
 479     for i, byte in enumerate(bytes[1:]):
 480       size += (byte & 0x7f) << ((i * 7) + 4)
 481     raw_base = len(bytes)
 482     if type == 6: # offset delta
 483         bytes = take_msb_bytes(map, raw_base)
 484         assert not (bytes[-1] & 0x80)
 485         delta_base_offset = bytes[0] & 0x7f
 486         for byte in bytes[1:]:
 487             delta_base_offset += 1
 488             delta_base_offset <<= 7
 489             delta_base_offset += (byte & 0x7f)
 490         raw_base+=len(bytes)
 491         uncomp, comp_len = read_zlib(map, raw_base, size)
 492         assert size == len(uncomp)
 493         return type, (delta_base_offset, uncomp), comp_len+raw_base
 494     elif type == 7: # ref delta
 495         basename = map[raw_base:raw_base+20]
 496         uncomp, comp_len = read_zlib(map, raw_base+20, size)
 497         assert size == len(uncomp)
 498         return type, (basename, uncomp), comp_len+raw_base+20
 499     else:
 500         uncomp, comp_len = read_zlib(map, raw_base, size)
 501         assert len(uncomp) == size
 502         return type, uncomp, comp_len+raw_base
 503
 504
 505 class SHA1Writer(object):
 506
 507     def __init__(self, f):
 508         self.f = f
 509         self.sha1 = hashlib.sha1("")
 510
 511     def write(self, data):
 512         self.sha1.update(data)
 513         self.f.write(data)
 514
 515     def write_sha(self):
 516         sha = self.sha1.digest()
 517         assert len(sha) == 20
 518         self.f.write(sha)
 519         return sha
 520
 521     def close(self):
 522         sha = self.write_sha()
 523         self.f.close()
 524         return sha
 525
 526     def tell(self):
 527         return self.f.tell()
 528
 529
 530 def write_pack_object(f, type, object):
 531     """Write pack object to a file.
 532
 533     :param f: File to write to
 534     :param o: Object to write
 535     """
 536     ret = f.tell()
 537     if type == 6: # ref delta
 538         (delta_base_offset, object) = object
 539     elif type == 7: # offset delta
 540         (basename, object) = object
 541     size = len(object)
 542     c = (type << 4) | (size & 15)
 543     size >>= 4
 544     while size:
 545         f.write(chr(c | 0x80))
 546         c = size & 0x7f
 547         size >>= 7
 548     f.write(chr(c))
 549     if type == 6: # offset delta
 550         ret = [delta_base_offset & 0x7f]
 551         delta_base_offset >>= 7
 552         while delta_base_offset:
 553             delta_base_offset -= 1
 554             ret.insert(0, 0x80 | (delta_base_offset & 0x7f))
 555             delta_base_offset >>= 7
 556         f.write("".join([chr(x) for x in ret]))
 557     elif type == 7: # ref delta
 558         assert len(basename) == 20
 559         f.write(basename)
 560     f.write(zlib.compress(object))
 561     return f.tell()
 562
 563
 564 def write_pack(filename, objects, num_objects):
 565     f = open(filename + ".pack", 'w')
 566     try:
 567         entries, data_sum = write_pack_data(f, objects, num_objects)
 568     except:
 569         f.close()
 570     entries.sort()
 571     write_pack_index_v2(filename + ".idx", entries, data_sum)
 572
 573
 574 def write_pack_data(f, objects, num_objects):
 575     """Write a new pack file.
 576
 577     :param filename: The filename of the new pack file.
 578     :param objects: List of objects to write.
 579     :return: List with (name, offset, crc32 checksum) entries, pack checksum
 580     """
 581     entries = []
 582     f = SHA1Writer(f)
 583     f.write("PACK")               # Pack header
 584     f.write(struct.pack(">L", 2)) # Pack version
 585     f.write(struct.pack(">L", num_objects)) # Number of objects in pack
 586     for o in objects:
 587         sha1 = o.sha().digest()
 588         crc32 = o.crc32()
 589         # FIXME: Delta !
 590         t, o = o.as_raw_string()
 591         offset = write_pack_object(f, t, o)
 592         entries.append((sha1, offset, crc32))
 593     return entries, f.write_sha()
 594
 595
 596 def write_pack_index_v1(filename, entries, pack_checksum):
 597     """Write a new pack index file.
 598
 599     :param filename: The filename of the new pack index file.
 600     :param entries: List of tuples with object name (sha), offset_in_pack,  and
 601             crc32_checksum.
 602     :param pack_checksum: Checksum of the pack file.
 603     """
 604     f = open(filename, 'w')
 605     f = SHA1Writer(f)
 606     fan_out_table = defaultdict(lambda: 0)
 607     for (name, offset, entry_checksum) in entries:
 608         fan_out_table[ord(name[0])] += 1
 609     # Fan-out table
 610     for i in range(0x100):
 611         f.write(struct.pack(">L", fan_out_table[i]))
 612         fan_out_table[i+1] += fan_out_table[i]
 613     for (name, offset, entry_checksum) in entries:
 614         f.write(struct.pack(">L20s", offset, name))
 615     assert len(pack_checksum) == 20
 616     f.write(pack_checksum)
 617     f.close()
 618
 619
 620 def apply_delta(src_buf, delta):
 621     """Based on the similar function in git's patch-delta.c."""
 622     assert isinstance(src_buf, str), "was %r" % (src_buf,)
 623     assert isinstance(delta, str)
 624     out = ""
 625     def pop(delta):
 626         ret = delta[0]
 627         delta = delta[1:]
 628         return ord(ret), delta
 629     def get_delta_header_size(delta):
 630         size = 0
 631         i = 0
 632         while delta:
 633             cmd, delta = pop(delta)
 634             size |= (cmd & ~0x80) << i
 635             i += 7
 636             if not cmd & 0x80:
 637                 break
 638         return size, delta
 639     src_size, delta = get_delta_header_size(delta)
 640     dest_size, delta = get_delta_header_size(delta)
 641     assert src_size == len(src_buf)
 642     while delta:
 643         cmd, delta = pop(delta)
 644         if cmd & 0x80:
 645             cp_off = 0
 646             for i in range(4):
 647                 if cmd & (1 << i):
 648                     x, delta = pop(delta)
 649                     cp_off |= x << (i * 8)
 650             cp_size = 0
 651             for i in range(3):
 652                 if cmd & (1 << (4+i)):
 653                     x, delta = pop(delta)
 654                     cp_size |= x << (i * 8)
 655             if cp_size == 0:
 656                 cp_size = 0x10000
 657             if (cp_off + cp_size < cp_size or
 658                 cp_off + cp_size > src_size or
 659                 cp_size > dest_size):
 660                 break
 661             out += src_buf[cp_off:cp_off+cp_size]
 662         elif cmd != 0:
 663             out += delta[:cmd]
 664             delta = delta[cmd:]
 665         else:
 666             raise ApplyDeltaError("Invalid opcode 0")
 667
 668     if delta != "":
 669         raise ApplyDeltaError("delta not empty: %r" % delta)
 670
 671     if dest_size != len(out):
 672         raise ApplyDeltaError("dest size incorrect")
 673
 674     return out
 675
 676
 677 def write_pack_index_v2(filename, entries, pack_checksum):
 678     """Write a new pack index file.
 679
 680     :param filename: The filename of the new pack index file.
 681     :param entries: List of tuples with object name (sha), offset_in_pack,  and
 682             crc32_checksum.
 683     :param pack_checksum: Checksum of the pack file.
 684     """
 685     f = open(filename, 'w')
 686     f = SHA1Writer(f)
 687     f.write('\377tOc') # Magic!
 688     f.write(struct.pack(">L", 2))
 689     fan_out_table = defaultdict(lambda: 0)
 690     for (name, offset, entry_checksum) in entries:
 691         fan_out_table[ord(name[0])] += 1
 692     # Fan-out table
 693     for i in range(0x100):
 694         f.write(struct.pack(">L", fan_out_table[i]))
 695         fan_out_table[i+1] += fan_out_table[i]
 696     for (name, offset, entry_checksum) in entries:
 697         f.write(name)
 698     for (name, offset, entry_checksum) in entries:
 699         f.write(struct.pack(">l", entry_checksum))
 700     for (name, offset, entry_checksum) in entries:
 701         # FIXME: handle if MSBit is set in offset
 702         f.write(struct.pack(">L", offset))
 703     # FIXME: handle table for pack files > 8 Gb
 704     assert len(pack_checksum) == 20
 705     f.write(pack_checksum)
 706     f.close()
 707
 708
 709 class Pack(object):
 710
 711     def __init__(self, basename):
 712         self._basename = basename
 713         self._data_path = self._basename + ".pack"
 714         self._idx_path = self._basename + ".idx"
 715         self._data = None
 716         self._idx = None
 717
 718     def name(self):
 719         return self.idx.objects_sha1()
 720
 721     @property
 722     def data(self):
 723         if self._data is None:
 724             self._data = PackData(self._data_path)
 725             assert len(self.idx) == len(self._data)
 726             assert self.idx.get_stored_checksums()[0] == self._data.get_stored_checksum()
 727         return self._data
 728
 729     @property
 730     def idx(self):
 731         if self._idx is None:
 732             self._idx = PackIndex(self._idx_path)
 733         return self._idx
 734
 735     def close(self):
 736         if self._data is not None:
 737             self._data.close()
 738         self.idx.close()
 739
 740     def __eq__(self, other):
 741         return type(self) == type(other) and self.idx == other.idx
 742
 743     def __len__(self):
 744         """Number of entries in this pack."""
 745         return len(self.idx)
 746
 747     def __repr__(self):
 748         return "Pack(%r)" % self._basename
 749
 750     def __iter__(self):
 751         """Iterate over all the sha1s of the objects in this pack."""
 752         return iter(self.idx)
 753
 754     def check(self):
 755         return self.idx.check() and self.data.check()
 756
 757     def get_stored_checksum(self):
 758         return self.data.get_stored_checksum()
 759
 760     def __contains__(self, sha1):
 761         """Check whether this pack contains a particular SHA1."""
 762         return (self.idx.object_index(sha1) is not None)
 763
 764     def get_raw(self, sha1, resolve_ref=None):
 765         if resolve_ref is None:
 766             resolve_ref = self.get_raw
 767         offset = self.idx.object_index(sha1)
 768         if offset is None:
 769             raise KeyError(sha1)
 770
 771         type, obj = self.data.get_object_at(offset)
 772         assert isinstance(offset, int)
 773         return resolve_object(offset, type, obj, resolve_ref,
 774             self.data.get_object_at)
 775
 776     def __getitem__(self, sha1):
 777         """Retrieve the specified SHA1."""
 778         type, uncomp = self.get_raw(sha1)
 779         return ShaFile.from_raw_string(type, uncomp)
 780
 781     def iterobjects(self):
 782         for offset, type, obj in self.data.iterobjects():
 783             assert isinstance(offset, int)
 784             yield ShaFile.from_raw_string(
 785                     *resolve_object(offset, type, obj, self.get_raw,
 786                 self.data.get_object_at))
 787
 788
 789 def load_packs(path):
 790     if not os.path.exists(path):
 791         return
 792     for name in os.listdir(path):
 793         if name.startswith("pack-") and name.endswith(".pack"):
 794             yield Pack(os.path.join(path, name[:-len(".pack")]))