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