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