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