/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to dulwich/dulwich/pack.py

Fix branch cloning.

Show diffs side-by-side

added added

removed removed

Lines of Context:
dulwich/dulwich/pack.py
42
42
import struct
43
43
import sys
44
44
import zlib
45
 
import difflib
46
45
 
47
46
from objects import (
48
47
        ShaFile,
49
 
        hex_to_sha,
50
 
        sha_to_hex,
51
48
        )
52
49
from errors import ApplyDeltaError
53
50
 
84
81
    return sha.hexdigest()
85
82
 
86
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
 
87
100
MAX_MMAP_SIZE = 256 * 1024 * 1024
88
101
 
89
102
def simple_mmap(f, offset, size, access=mmap.ACCESS_READ):
312
325
      return None
313
326
 
314
327
 
315
 
def read_pack_header(f):
316
 
    header = f.read(12)
317
 
    assert header[:4] == "PACK"
318
 
    (version,) = struct.unpack_from(">L", header, 4)
319
 
    assert version in (2, 3), "Version was %d" % version
320
 
    (num_objects,) = struct.unpack_from(">L", header, 8)
321
 
    return (version, num_objects)
322
 
 
323
 
 
324
 
def read_pack_tail(f):
325
 
    return (f.read(20),)
326
 
 
327
 
 
328
 
def unpack_object(map):
329
 
    bytes = take_msb_bytes(map, 0)
330
 
    type = (bytes[0] >> 4) & 0x07
331
 
    size = bytes[0] & 0x0f
332
 
    for i, byte in enumerate(bytes[1:]):
333
 
      size += (byte & 0x7f) << ((i * 7) + 4)
334
 
    raw_base = len(bytes)
335
 
    if type == 6: # offset delta
336
 
        bytes = take_msb_bytes(map, raw_base)
337
 
        assert not (bytes[-1] & 0x80)
338
 
        delta_base_offset = bytes[0] & 0x7f
339
 
        for byte in bytes[1:]:
340
 
            delta_base_offset += 1
341
 
            delta_base_offset <<= 7
342
 
            delta_base_offset += (byte & 0x7f)
343
 
        raw_base+=len(bytes)
344
 
        uncomp, comp_len = read_zlib(map, raw_base, size)
345
 
        assert size == len(uncomp)
346
 
        return type, (delta_base_offset, uncomp), comp_len+raw_base
347
 
    elif type == 7: # ref delta
348
 
        basename = map[raw_base:raw_base+20]
349
 
        uncomp, comp_len = read_zlib(map, raw_base+20, size)
350
 
        assert size == len(uncomp)
351
 
        return type, (basename, uncomp), comp_len+raw_base+20
352
 
    else:
353
 
        uncomp, comp_len = read_zlib(map, raw_base, size)
354
 
        assert len(uncomp) == size
355
 
        return type, uncomp, comp_len+raw_base
356
 
 
357
 
 
358
328
class PackData(object):
359
329
  """The data contained in a packfile.
360
330
 
401
371
  def _read_header(self):
402
372
    f = open(self._filename, 'rb')
403
373
    try:
404
 
        (version, self._num_objects) = \
405
 
                read_pack_header(f)
 
374
        header = f.read(12)
406
375
        f.seek(self._size-20)
407
 
        (self._stored_checksum,) = read_pack_tail(f)
 
376
        self._stored_checksum = f.read(20)
408
377
    finally:
409
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)
410
383
 
411
384
  def __len__(self):
412
385
      """Returns the number of objects in this pack."""
425
398
    f = open(self._filename, 'rb')
426
399
    for i in range(len(self)):
427
400
        map = simple_mmap(f, offset, self._size-offset)
428
 
        (type, obj, total_size) = unpack_object(map)
 
401
        (type, obj, total_size) = self._unpack_object(map)
429
402
        yield offset, type, obj
430
403
        offset += total_size
431
404
    f.close()
502
475
    f = open(self._filename, 'rb')
503
476
    try:
504
477
      map = simple_mmap(f, offset, size-offset)
505
 
      return unpack_object(map)[:2]
 
478
      return self._unpack_object(map)[:2]
506
479
    finally:
507
480
      f.close()
508
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
 
509
511
 
510
512
class SHA1Writer(object):
511
513
    
570
572
    f = open(filename + ".pack", 'w')
571
573
    try:
572
574
        entries, data_sum = write_pack_data(f, objects, num_objects)
573
 
    finally:
 
575
    except:
574
576
        f.close()
575
577
    entries.sort()
576
578
    write_pack_index_v2(filename + ".idx", entries, data_sum)
577
579
 
578
580
 
579
 
def write_pack_data(f, objects, num_objects, window=10):
 
581
def write_pack_data(f, objects, num_objects):
580
582
    """Write a new pack file.
581
583
 
582
584
    :param filename: The filename of the new pack file.
583
585
    :param objects: List of objects to write.
584
586
    :return: List with (name, offset, crc32 checksum) entries, pack checksum
585
587
    """
586
 
    recency = list(objects)
587
 
    # FIXME: Somehow limit delta depth
588
 
    # FIXME: Make thin-pack optional (its not used when cloning a pack)
589
 
    # Build a list of objects ordered by the magic Linus heuristic
590
 
    # This helps us find good objects to diff against us
591
 
    magic = []
592
 
    for obj, path in recency:
593
 
        magic.append( (obj.type, path, 1, -len(obj.as_raw_string()[1]), obj) )
594
 
    magic.sort()
595
 
    # Build a map of objects and their index in magic - so we can find preceeding objects
596
 
    # to diff against
597
 
    offs = {}
598
 
    for i in range(len(magic)):
599
 
        offs[magic[i][4]] = i
600
 
    # Write the pack
601
588
    entries = []
602
589
    f = SHA1Writer(f)
603
590
    f.write("PACK")               # Pack header
604
591
    f.write(struct.pack(">L", 2)) # Pack version
605
592
    f.write(struct.pack(">L", num_objects)) # Number of objects in pack
606
 
    for o, path in recency:
 
593
    for o in objects:
607
594
        sha1 = o.sha().digest()
608
595
        crc32 = o.crc32()
609
 
        orig_t, raw = o.as_raw_string()
610
 
        winner = raw
611
 
        t = orig_t
612
 
        #for i in range(offs[o]-window, window):
613
 
        #    if i < 0 or i >= len(offs): continue
614
 
        #    b = magic[i][4]
615
 
        #    if b.type != orig_t: continue
616
 
        #    _, base = b.as_raw_string()
617
 
        #    delta = create_delta(base, raw)
618
 
        #    if len(delta) < len(winner):
619
 
        #        winner = delta
620
 
        #        t = 6 if magic[i][2] == 1 else 7
621
 
        offset = write_pack_object(f, t, winner)
 
596
        # FIXME: Delta !
 
597
        t, o = o.as_raw_string()
 
598
        offset = write_pack_object(f, t, o)
622
599
        entries.append((sha1, offset, crc32))
623
600
    return entries, f.write_sha()
624
601
 
647
624
    f.close()
648
625
 
649
626
 
650
 
def create_delta(base_buf, target_buf):
651
 
    """Use python difflib to work out how to transform base_buf to target_buf"""
652
 
    assert isinstance(base_buf, str)
653
 
    assert isinstance(target_buf, str)
654
 
    out_buf = ""
655
 
    # write delta header
656
 
    def encode_size(size):
657
 
        ret = ""
658
 
        c = size & 0x7f
659
 
        size >>= 7
660
 
        while size:
661
 
            ret += chr(c | 0x80)
662
 
            c = size & 0x7f
663
 
            size >>= 7
664
 
        ret += chr(c)
665
 
        return ret
666
 
    out_buf += encode_size(len(base_buf))
667
 
    out_buf += encode_size(len(target_buf))
668
 
    # write out delta opcodes
669
 
    seq = difflib.SequenceMatcher(a=base_buf, b=target_buf)
670
 
    for opcode, i1, i2, j1, j2 in seq.get_opcodes():
671
 
        # Git patch opcodes don't care about deletes!
672
 
        #if opcode == "replace" or opcode == "delete":
673
 
        #    pass
674
 
        if opcode == "equal":
675
 
            # If they are equal, unpacker will use data from base_buf
676
 
            # Write out an opcode that says what range to use
677
 
            scratch = ""
678
 
            op = 0x80
679
 
            o = i1
680
 
            for i in range(4):
681
 
                if o & 0xff << i*8:
682
 
                    scratch += chr(o >> i)
683
 
                    op |= 1 << i
684
 
            s = i2 - i1
685
 
            for i in range(2):
686
 
                if s & 0xff << i*8:
687
 
                    scratch += chr(s >> i)
688
 
                    op |= 1 << (4+i)
689
 
            out_buf += chr(op)
690
 
            out_buf += scratch
691
 
        if opcode == "replace" or opcode == "insert":
692
 
            # If we are replacing a range or adding one, then we just
693
 
            # output it to the stream (prefixed by its size)
694
 
            s = j2 - j1
695
 
            o = j1
696
 
            while s > 127:
697
 
                out_buf += chr(127)
698
 
                out_buf += target_buf[o:o+127]
699
 
                s -= 127
700
 
                o += 127
701
 
            out_buf += chr(s)
702
 
            out_buf += target_buf[o:o+s]
703
 
    return out_buf
704
 
 
705
 
 
706
627
def apply_delta(src_buf, delta):
707
628
    """Based on the similar function in git's patch-delta.c."""
708
629
    assert isinstance(src_buf, str), "was %r" % (src_buf,)
724
645
        return size, delta
725
646
    src_size, delta = get_delta_header_size(delta)
726
647
    dest_size, delta = get_delta_header_size(delta)
727
 
    assert src_size == len(src_buf), "%d vs %d" % (src_size, len(src_buf))
 
648
    assert src_size == len(src_buf)
728
649
    while delta:
729
650
        cmd, delta = pop(delta)
730
651
        if cmd & 0x80:
848
769
        return (self.idx.object_index(sha1) is not None)
849
770
 
850
771
    def get_raw(self, sha1, resolve_ref=None):
 
772
        if resolve_ref is None:
 
773
            resolve_ref = self.get_raw
851
774
        offset = self.idx.object_index(sha1)
852
775
        if offset is None:
853
776
            raise KeyError(sha1)
862
785
        type, uncomp = self.get_raw(sha1)
863
786
        return ShaFile.from_raw_string(type, uncomp)
864
787
 
865
 
    def iterobjects(self, get_raw=None):
866
 
        if get_raw is None:
867
 
            def get_raw(x):
868
 
                raise KeyError(x)
 
788
    def iterobjects(self):
869
789
        for offset, type, obj in self.data.iterobjects():
870
790
            assert isinstance(offset, int)
871
791
            yield ShaFile.from_raw_string(
872
 
                    *resolve_object(offset, type, obj, 
873
 
                        get_raw, 
874
 
                    self.data.get_object_at))
 
792
                    *resolve_object(offset, type, obj, self.get_raw, 
 
793
                self.data.get_object_at))
875
794
 
876
795
 
877
796
def load_packs(path):