dulwich/object_store.py

   1 # object_store.py -- Object store for git objects
   2 # Copyright (C) 2008-2013 Jelmer Vernooij <jelmer@samba.org>
   3 #                         and others
   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; either version 2
   8 # or (at your option) a later version of the License.
   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
  21 """Git object store interfaces and implementation."""
  22
  23
  24 from io import BytesIO
  25 import errno
  26 import itertools
  27 import os
  28 import stat
  29 import tempfile
  30
  31 from dulwich.diff_tree import (
  32     tree_changes,
  33     walk_trees,
  34     )
  35 from dulwich.errors import (
  36     NotTreeError,
  37     )
  38 from dulwich.file import GitFile
  39 from dulwich.objects import (
  40     Commit,
  41     ShaFile,
  42     Tag,
  43     Tree,
  44     ZERO_SHA,
  45     hex_to_sha,
  46     sha_to_hex,
  47     hex_to_filename,
  48     S_ISGITLINK,
  49     object_class,
  50     )
  51 from dulwich.pack import (
  52     Pack,
  53     PackData,
  54     PackInflater,
  55     iter_sha1,
  56     write_pack_header,
  57     write_pack_index_v2,
  58     write_pack_object,
  59     write_pack_objects,
  60     compute_file_sha,
  61     PackIndexer,
  62     PackStreamCopier,
  63     )
  64
  65 INFODIR = 'info'
  66 PACKDIR = 'pack'
  67
  68
  69 class BaseObjectStore(object):
  70     """Object store interface."""
  71
  72     def determine_wants_all(self, refs):
  73         return [sha for (ref, sha) in refs.iteritems()
  74                 if not sha in self and not ref.endswith("^{}") and
  75                    not sha == ZERO_SHA]
  76
  77     def iter_shas(self, shas):
  78         """Iterate over the objects for the specified shas.
  79
  80         :param shas: Iterable object with SHAs
  81         :return: Object iterator
  82         """
  83         return ObjectStoreIterator(self, shas)
  84
  85     def contains_loose(self, sha):
  86         """Check if a particular object is present by SHA1 and is loose."""
  87         raise NotImplementedError(self.contains_loose)
  88
  89     def contains_packed(self, sha):
  90         """Check if a particular object is present by SHA1 and is packed."""
  91         raise NotImplementedError(self.contains_packed)
  92
  93     def __contains__(self, sha):
  94         """Check if a particular object is present by SHA1.
  95
  96         This method makes no distinction between loose and packed objects.
  97         """
  98         return self.contains_packed(sha) or self.contains_loose(sha)
  99
 100     @property
 101     def packs(self):
 102         """Iterable of pack objects."""
 103         raise NotImplementedError
 104
 105     def get_raw(self, name):
 106         """Obtain the raw text for an object.
 107
 108         :param name: sha for the object.
 109         :return: tuple with numeric type and object contents.
 110         """
 111         raise NotImplementedError(self.get_raw)
 112
 113     def __getitem__(self, sha):
 114         """Obtain an object by SHA1."""
 115         type_num, uncomp = self.get_raw(sha)
 116         return ShaFile.from_raw_string(type_num, uncomp, sha=sha)
 117
 118     def __iter__(self):
 119         """Iterate over the SHAs that are present in this store."""
 120         raise NotImplementedError(self.__iter__)
 121
 122     def add_object(self, obj):
 123         """Add a single object to this object store.
 124
 125         """
 126         raise NotImplementedError(self.add_object)
 127
 128     def add_objects(self, objects):
 129         """Add a set of objects to this object store.
 130
 131         :param objects: Iterable over a list of objects.
 132         """
 133         raise NotImplementedError(self.add_objects)
 134
 135     def tree_changes(self, source, target, want_unchanged=False):
 136         """Find the differences between the contents of two trees
 137
 138         :param source: SHA1 of the source tree
 139         :param target: SHA1 of the target tree
 140         :param want_unchanged: Whether unchanged files should be reported
 141         :return: Iterator over tuples with
 142             (oldpath, newpath), (oldmode, newmode), (oldsha, newsha)
 143         """
 144         for change in tree_changes(self, source, target,
 145                                    want_unchanged=want_unchanged):
 146             yield ((change.old.path, change.new.path),
 147                    (change.old.mode, change.new.mode),
 148                    (change.old.sha, change.new.sha))
 149
 150     def iter_tree_contents(self, tree_id, include_trees=False):
 151         """Iterate the contents of a tree and all subtrees.
 152
 153         Iteration is depth-first pre-order, as in e.g. os.walk.
 154
 155         :param tree_id: SHA1 of the tree.
 156         :param include_trees: If True, include tree objects in the iteration.
 157         :return: Iterator over TreeEntry namedtuples for all the objects in a
 158             tree.
 159         """
 160         for entry, _ in walk_trees(self, tree_id, None):
 161             if not stat.S_ISDIR(entry.mode) or include_trees:
 162                 yield entry
 163
 164     def find_missing_objects(self, haves, wants, progress=None,
 165                              get_tagged=None,
 166                              get_parents=lambda commit: commit.parents):
 167         """Find the missing objects required for a set of revisions.
 168
 169         :param haves: Iterable over SHAs already in common.
 170         :param wants: Iterable over SHAs of objects to fetch.
 171         :param progress: Simple progress function that will be called with
 172             updated progress strings.
 173         :param get_tagged: Function that returns a dict of pointed-to sha -> tag
 174             sha for including tags.
 175         :param get_parents: Optional function for getting the parents of a commit.
 176         :return: Iterator over (sha, path) pairs.
 177         """
 178         finder = MissingObjectFinder(self, haves, wants, progress, get_tagged, get_parents=get_parents)
 179         return iter(finder.next, None)
 180
 181     def find_common_revisions(self, graphwalker):
 182         """Find which revisions this store has in common using graphwalker.
 183
 184         :param graphwalker: A graphwalker object.
 185         :return: List of SHAs that are in common
 186         """
 187         haves = []
 188         sha = next(graphwalker)
 189         while sha:
 190             if sha in self:
 191                 haves.append(sha)
 192                 graphwalker.ack(sha)
 193             sha = next(graphwalker)
 194         return haves
 195
 196     def generate_pack_contents(self, have, want, progress=None):
 197         """Iterate over the contents of a pack file.
 198
 199         :param have: List of SHA1s of objects that should not be sent
 200         :param want: List of SHA1s of objects that should be sent
 201         :param progress: Optional progress reporting method
 202         """
 203         return self.iter_shas(self.find_missing_objects(have, want, progress))
 204
 205     def peel_sha(self, sha):
 206         """Peel all tags from a SHA.
 207
 208         :param sha: The object SHA to peel.
 209         :return: The fully-peeled SHA1 of a tag object, after peeling all
 210             intermediate tags; if the original ref does not point to a tag, this
 211             will equal the original SHA1.
 212         """
 213         obj = self[sha]
 214         obj_class = object_class(obj.type_name)
 215         while obj_class is Tag:
 216             obj_class, sha = obj.object
 217             obj = self[sha]
 218         return obj
 219
 220     def _collect_ancestors(self, heads, common=set(),
 221                            get_parents=lambda commit: commit.parents):
 222         """Collect all ancestors of heads up to (excluding) those in common.
 223
 224         :param heads: commits to start from
 225         :param common: commits to end at, or empty set to walk repository
 226             completely
 227         :param get_parents: Optional function for getting the parents of a commit.
 228         :return: a tuple (A, B) where A - all commits reachable
 229             from heads but not present in common, B - common (shared) elements
 230             that are directly reachable from heads
 231         """
 232         bases = set()
 233         commits = set()
 234         queue = []
 235         queue.extend(heads)
 236         while queue:
 237             e = queue.pop(0)
 238             if e in common:
 239                 bases.add(e)
 240             elif e not in commits:
 241                 commits.add(e)
 242                 cmt = self[e]
 243                 queue.extend(get_parents(cmt))
 244         return (commits, bases)
 245
 246     def close(self):
 247         """Close any files opened by this object store."""
 248         # Default implementation is a NO-OP
 249
 250
 251 class PackBasedObjectStore(BaseObjectStore):
 252
 253     def __init__(self):
 254         self._pack_cache = None
 255
 256     @property
 257     def alternates(self):
 258         return []
 259
 260     def contains_packed(self, sha):
 261         """Check if a particular object is present by SHA1 and is packed.
 262
 263         This does not check alternates.
 264         """
 265         for pack in self.packs:
 266             if sha in pack:
 267                 return True
 268         return False
 269
 270     def __contains__(self, sha):
 271         """Check if a particular object is present by SHA1.
 272
 273         This method makes no distinction between loose and packed objects.
 274         """
 275         if self.contains_packed(sha) or self.contains_loose(sha):
 276             return True
 277         for alternate in self.alternates:
 278             if sha in alternate:
 279                 return True
 280         return False
 281
 282     def _load_packs(self):
 283         raise NotImplementedError(self._load_packs)
 284
 285     def _pack_cache_stale(self):
 286         """Check whether the pack cache is stale."""
 287         raise NotImplementedError(self._pack_cache_stale)
 288
 289     def _add_known_pack(self, pack):
 290         """Add a newly appeared pack to the cache by path.
 291
 292         """
 293         if self._pack_cache is not None:
 294             self._pack_cache.append(pack)
 295
 296     def close(self):
 297         pack_cache = self._pack_cache
 298         self._pack_cache = None
 299         while pack_cache:
 300             pack = pack_cache.pop()
 301             pack.close()
 302
 303     @property
 304     def packs(self):
 305         """List with pack objects."""
 306         if self._pack_cache is None or self._pack_cache_stale():
 307             self._pack_cache = self._load_packs()
 308         return self._pack_cache
 309
 310     def _iter_alternate_objects(self):
 311         """Iterate over the SHAs of all the objects in alternate stores."""
 312         for alternate in self.alternates:
 313             for alternate_object in alternate:
 314                 yield alternate_object
 315
 316     def _iter_loose_objects(self):
 317         """Iterate over the SHAs of all loose objects."""
 318         raise NotImplementedError(self._iter_loose_objects)
 319
 320     def _get_loose_object(self, sha):
 321         raise NotImplementedError(self._get_loose_object)
 322
 323     def _remove_loose_object(self, sha):
 324         raise NotImplementedError(self._remove_loose_object)
 325
 326     def pack_loose_objects(self):
 327         """Pack loose objects.
 328
 329         :return: Number of objects packed
 330         """
 331         objects = set()
 332         for sha in self._iter_loose_objects():
 333             objects.add((self._get_loose_object(sha), None))
 334         self.add_objects(list(objects))
 335         for obj, path in objects:
 336             self._remove_loose_object(obj.id)
 337         return len(objects)
 338
 339     def __iter__(self):
 340         """Iterate over the SHAs that are present in this store."""
 341         iterables = self.packs + [self._iter_loose_objects()] + [self._iter_alternate_objects()]
 342         return itertools.chain(*iterables)
 343
 344     def contains_loose(self, sha):
 345         """Check if a particular object is present by SHA1 and is loose.
 346
 347         This does not check alternates.
 348         """
 349         return self._get_loose_object(sha) is not None
 350
 351     def get_raw(self, name):
 352         """Obtain the raw text for an object.
 353
 354         :param name: sha for the object.
 355         :return: tuple with numeric type and object contents.
 356         """
 357         if len(name) == 40:
 358             sha = hex_to_sha(name)
 359             hexsha = name
 360         elif len(name) == 20:
 361             sha = name
 362             hexsha = None
 363         else:
 364             raise AssertionError("Invalid object name %r" % name)
 365         for pack in self.packs:
 366             try:
 367                 return pack.get_raw(sha)
 368             except KeyError:
 369                 pass
 370         if hexsha is None:
 371             hexsha = sha_to_hex(name)
 372         ret = self._get_loose_object(hexsha)
 373         if ret is not None:
 374             return ret.type_num, ret.as_raw_string()
 375         for alternate in self.alternates:
 376             try:
 377                 return alternate.get_raw(hexsha)
 378             except KeyError:
 379                 pass
 380         raise KeyError(hexsha)
 381
 382     def add_objects(self, objects):
 383         """Add a set of objects to this object store.
 384
 385         :param objects: Iterable over objects, should support __len__.
 386         :return: Pack object of the objects written.
 387         """
 388         if len(objects) == 0:
 389             # Don't bother writing an empty pack file
 390             return
 391         f, commit, abort = self.add_pack()
 392         try:
 393             write_pack_objects(f, objects)
 394         except:
 395             abort()
 396             raise
 397         else:
 398             return commit()
 399
 400
 401 class DiskObjectStore(PackBasedObjectStore):
 402     """Git-style object store that exists on disk."""
 403
 404     def __init__(self, path):
 405         """Open an object store.
 406
 407         :param path: Path of the object store.
 408         """
 409         super(DiskObjectStore, self).__init__()
 410         self.path = path
 411         self.pack_dir = os.path.join(self.path, PACKDIR)
 412         self._pack_cache_time = 0
 413         self._alternates = None
 414
 415     def __repr__(self):
 416         return "<%s(%r)>" % (self.__class__.__name__, self.path)
 417
 418     @property
 419     def alternates(self):
 420         if self._alternates is not None:
 421             return self._alternates
 422         self._alternates = []
 423         for path in self._read_alternate_paths():
 424             self._alternates.append(DiskObjectStore(path))
 425         return self._alternates
 426
 427     def _read_alternate_paths(self):
 428         try:
 429             f = GitFile(os.path.join(self.path, "info", "alternates"),
 430                     'rb')
 431         except (OSError, IOError) as e:
 432             if e.errno == errno.ENOENT:
 433                 return []
 434             raise
 435         ret = []
 436         try:
 437             for l in f.readlines():
 438                 l = l.rstrip("\n")
 439                 if l[0] == "#":
 440                     continue
 441                 if os.path.isabs(l):
 442                     ret.append(l)
 443                 else:
 444                     ret.append(os.path.join(self.path, l))
 445             return ret
 446         finally:
 447             f.close()
 448
 449     def add_alternate_path(self, path):
 450         """Add an alternate path to this object store.
 451         """
 452         try:
 453             os.mkdir(os.path.join(self.path, "info"))
 454         except OSError as e:
 455             if e.errno != errno.EEXIST:
 456                 raise
 457         alternates_path = os.path.join(self.path, "info/alternates")
 458         f = GitFile(alternates_path, 'wb')
 459         try:
 460             try:
 461                 orig_f = open(alternates_path, 'rb')
 462             except (OSError, IOError) as e:
 463                 if e.errno != errno.ENOENT:
 464                     raise
 465             else:
 466                 try:
 467                     f.write(orig_f.read())
 468                 finally:
 469                     orig_f.close()
 470             f.write("%s\n" % path)
 471         finally:
 472             f.close()
 473
 474         if not os.path.isabs(path):
 475             path = os.path.join(self.path, path)
 476         self.alternates.append(DiskObjectStore(path))
 477
 478     def _load_packs(self):
 479         pack_files = []
 480         try:
 481             self._pack_cache_time = os.stat(self.pack_dir).st_mtime
 482             pack_dir_contents = os.listdir(self.pack_dir)
 483             for name in pack_dir_contents:
 484                 # TODO: verify that idx exists first
 485                 if name.startswith("pack-") and name.endswith(".pack"):
 486                     filename = os.path.join(self.pack_dir, name)
 487                     pack_files.append((os.stat(filename).st_mtime, filename))
 488         except OSError as e:
 489             if e.errno == errno.ENOENT:
 490                 return []
 491             raise
 492         pack_files.sort(reverse=True)
 493         suffix_len = len(".pack")
 494         result = []
 495         try:
 496             for _, f in pack_files:
 497                 result.append(Pack(f[:-suffix_len]))
 498         except:
 499             for p in result:
 500                 p.close()
 501             raise
 502         return result
 503
 504     def _pack_cache_stale(self):
 505         try:
 506             return os.stat(self.pack_dir).st_mtime > self._pack_cache_time
 507         except OSError as e:
 508             if e.errno == errno.ENOENT:
 509                 return True
 510             raise
 511
 512     def _get_shafile_path(self, sha):
 513         # Check from object dir
 514         return hex_to_filename(self.path, sha)
 515
 516     def _iter_loose_objects(self):
 517         for base in os.listdir(self.path):
 518             if len(base) != 2:
 519                 continue
 520             for rest in os.listdir(os.path.join(self.path, base)):
 521                 yield base+rest
 522
 523     def _get_loose_object(self, sha):
 524         path = self._get_shafile_path(sha)
 525         try:
 526             return ShaFile.from_path(path)
 527         except (OSError, IOError) as e:
 528             if e.errno == errno.ENOENT:
 529                 return None
 530             raise
 531
 532     def _remove_loose_object(self, sha):
 533         os.remove(self._get_shafile_path(sha))
 534
 535     def _complete_thin_pack(self, f, path, copier, indexer):
 536         """Move a specific file containing a pack into the pack directory.
 537
 538         :note: The file should be on the same file system as the
 539             packs directory.
 540
 541         :param f: Open file object for the pack.
 542         :param path: Path to the pack file.
 543         :param copier: A PackStreamCopier to use for writing pack data.
 544         :param indexer: A PackIndexer for indexing the pack.
 545         """
 546         entries = list(indexer)
 547
 548         # Update the header with the new number of objects.
 549         f.seek(0)
 550         write_pack_header(f, len(entries) + len(indexer.ext_refs()))
 551
 552         # Must flush before reading (http://bugs.python.org/issue3207)
 553         f.flush()
 554
 555         # Rescan the rest of the pack, computing the SHA with the new header.
 556         new_sha = compute_file_sha(f, end_ofs=-20)
 557
 558         # Must reposition before writing (http://bugs.python.org/issue3207)
 559         f.seek(0, os.SEEK_CUR)
 560
 561         # Complete the pack.
 562         for ext_sha in indexer.ext_refs():
 563             assert len(ext_sha) == 20
 564             type_num, data = self.get_raw(ext_sha)
 565             offset = f.tell()
 566             crc32 = write_pack_object(f, type_num, data, sha=new_sha)
 567             entries.append((ext_sha, offset, crc32))
 568         pack_sha = new_sha.digest()
 569         f.write(pack_sha)
 570         f.close()
 571
 572         # Move the pack in.
 573         entries.sort()
 574         pack_base_name = os.path.join(
 575           self.pack_dir, 'pack-' + iter_sha1(e[0] for e in entries))
 576         os.rename(path, pack_base_name + '.pack')
 577
 578         # Write the index.
 579         index_file = GitFile(pack_base_name + '.idx', 'wb')
 580         try:
 581             write_pack_index_v2(index_file, entries, pack_sha)
 582             index_file.close()
 583         finally:
 584             index_file.abort()
 585
 586         # Add the pack to the store and return it.
 587         final_pack = Pack(pack_base_name)
 588         final_pack.check_length_and_checksum()
 589         self._add_known_pack(final_pack)
 590         return final_pack
 591
 592     def add_thin_pack(self, read_all, read_some):
 593         """Add a new thin pack to this object store.
 594
 595         Thin packs are packs that contain deltas with parents that exist outside
 596         the pack. They should never be placed in the object store directly, and
 597         always indexed and completed as they are copied.
 598
 599         :param read_all: Read function that blocks until the number of requested
 600             bytes are read.
 601         :param read_some: Read function that returns at least one byte, but may
 602             not return the number of bytes requested.
 603         :return: A Pack object pointing at the now-completed thin pack in the
 604             objects/pack directory.
 605         """
 606         fd, path = tempfile.mkstemp(dir=self.path, prefix='tmp_pack_')
 607         f = os.fdopen(fd, 'w+b')
 608
 609         try:
 610             indexer = PackIndexer(f, resolve_ext_ref=self.get_raw)
 611             copier = PackStreamCopier(read_all, read_some, f,
 612                                       delta_iter=indexer)
 613             copier.verify()
 614             return self._complete_thin_pack(f, path, copier, indexer)
 615         finally:
 616             f.close()
 617
 618     def move_in_pack(self, path):
 619         """Move a specific file containing a pack into the pack directory.
 620
 621         :note: The file should be on the same file system as the
 622             packs directory.
 623
 624         :param path: Path to the pack file.
 625         """
 626         p = PackData(path)
 627         try:
 628             entries = p.sorted_entries()
 629             basename = os.path.join(self.pack_dir,
 630                 "pack-%s" % iter_sha1(entry[0] for entry in entries))
 631             f = GitFile(basename+".idx", "wb")
 632             try:
 633                 write_pack_index_v2(f, entries, p.get_stored_checksum())
 634             finally:
 635                 f.close()
 636         finally:
 637             p.close()
 638         os.rename(path, basename + ".pack")
 639         final_pack = Pack(basename)
 640         self._add_known_pack(final_pack)
 641         return final_pack
 642
 643     def add_pack(self):
 644         """Add a new pack to this object store.
 645
 646         :return: Fileobject to write to, a commit function to
 647             call when the pack is finished and an abort
 648             function.
 649         """
 650         fd, path = tempfile.mkstemp(dir=self.pack_dir, suffix=".pack")
 651         f = os.fdopen(fd, 'wb')
 652         def commit():
 653             os.fsync(fd)
 654             f.close()
 655             if os.path.getsize(path) > 0:
 656                 return self.move_in_pack(path)
 657             else:
 658                 os.remove(path)
 659                 return None
 660         def abort():
 661             f.close()
 662             os.remove(path)
 663         return f, commit, abort
 664
 665     def add_object(self, obj):
 666         """Add a single object to this object store.
 667
 668         :param obj: Object to add
 669         """
 670         dir = os.path.join(self.path, obj.id[:2])
 671         try:
 672             os.mkdir(dir)
 673         except OSError as e:
 674             if e.errno != errno.EEXIST:
 675                 raise
 676         path = os.path.join(dir, obj.id[2:])
 677         if os.path.exists(path):
 678             return # Already there, no need to write again
 679         f = GitFile(path, 'wb')
 680         try:
 681             f.write(obj.as_legacy_object())
 682         finally:
 683             f.close()
 684
 685     @classmethod
 686     def init(cls, path):
 687         try:
 688             os.mkdir(path)
 689         except OSError as e:
 690             if e.errno != errno.EEXIST:
 691                 raise
 692         os.mkdir(os.path.join(path, "info"))
 693         os.mkdir(os.path.join(path, PACKDIR))
 694         return cls(path)
 695
 696
 697 class MemoryObjectStore(BaseObjectStore):
 698     """Object store that keeps all objects in memory."""
 699
 700     def __init__(self):
 701         super(MemoryObjectStore, self).__init__()
 702         self._data = {}
 703
 704     def _to_hexsha(self, sha):
 705         if len(sha) == 40:
 706             return sha
 707         elif len(sha) == 20:
 708             return sha_to_hex(sha)
 709         else:
 710             raise ValueError("Invalid sha %r" % (sha,))
 711
 712     def contains_loose(self, sha):
 713         """Check if a particular object is present by SHA1 and is loose."""
 714         return self._to_hexsha(sha) in self._data
 715
 716     def contains_packed(self, sha):
 717         """Check if a particular object is present by SHA1 and is packed."""
 718         return False
 719
 720     def __iter__(self):
 721         """Iterate over the SHAs that are present in this store."""
 722         return self._data.iterkeys()
 723
 724     @property
 725     def packs(self):
 726         """List with pack objects."""
 727         return []
 728
 729     def get_raw(self, name):
 730         """Obtain the raw text for an object.
 731
 732         :param name: sha for the object.
 733         :return: tuple with numeric type and object contents.
 734         """
 735         obj = self[self._to_hexsha(name)]
 736         return obj.type_num, obj.as_raw_string()
 737
 738     def __getitem__(self, name):
 739         return self._data[self._to_hexsha(name)]
 740
 741     def __delitem__(self, name):
 742         """Delete an object from this store, for testing only."""
 743         del self._data[self._to_hexsha(name)]
 744
 745     def add_object(self, obj):
 746         """Add a single object to this object store.
 747
 748         """
 749         self._data[obj.id] = obj
 750
 751     def add_objects(self, objects):
 752         """Add a set of objects to this object store.
 753
 754         :param objects: Iterable over a list of objects.
 755         """
 756         for obj, path in objects:
 757             self._data[obj.id] = obj
 758
 759     def add_pack(self):
 760         """Add a new pack to this object store.
 761
 762         Because this object store doesn't support packs, we extract and add the
 763         individual objects.
 764
 765         :return: Fileobject to write to and a commit function to
 766             call when the pack is finished.
 767         """
 768         f = BytesIO()
 769         def commit():
 770             p = PackData.from_file(BytesIO(f.getvalue()), f.tell())
 771             f.close()
 772             for obj in PackInflater.for_pack_data(p):
 773                 self._data[obj.id] = obj
 774         def abort():
 775             pass
 776         return f, commit, abort
 777
 778     def _complete_thin_pack(self, f, indexer):
 779         """Complete a thin pack by adding external references.
 780
 781         :param f: Open file object for the pack.
 782         :param indexer: A PackIndexer for indexing the pack.
 783         """
 784         entries = list(indexer)
 785
 786         # Update the header with the new number of objects.
 787         f.seek(0)
 788         write_pack_header(f, len(entries) + len(indexer.ext_refs()))
 789
 790         # Rescan the rest of the pack, computing the SHA with the new header.
 791         new_sha = compute_file_sha(f, end_ofs=-20)
 792
 793         # Complete the pack.
 794         for ext_sha in indexer.ext_refs():
 795             assert len(ext_sha) == 20
 796             type_num, data = self.get_raw(ext_sha)
 797             write_pack_object(f, type_num, data, sha=new_sha)
 798         pack_sha = new_sha.digest()
 799         f.write(pack_sha)
 800
 801     def add_thin_pack(self, read_all, read_some):
 802         """Add a new thin pack to this object store.
 803
 804         Thin packs are packs that contain deltas with parents that exist outside
 805         the pack. Because this object store doesn't support packs, we extract
 806         and add the individual objects.
 807
 808         :param read_all: Read function that blocks until the number of requested
 809             bytes are read.
 810         :param read_some: Read function that returns at least one byte, but may
 811             not return the number of bytes requested.
 812         """
 813         f, commit, abort = self.add_pack()
 814         try:
 815             indexer = PackIndexer(f, resolve_ext_ref=self.get_raw)
 816             copier = PackStreamCopier(read_all, read_some, f, delta_iter=indexer)
 817             copier.verify()
 818             self._complete_thin_pack(f, indexer)
 819         except:
 820             abort()
 821             raise
 822         else:
 823             commit()
 824
 825
 826 class ObjectImporter(object):
 827     """Interface for importing objects."""
 828
 829     def __init__(self, count):
 830         """Create a new ObjectImporter.
 831
 832         :param count: Number of objects that's going to be imported.
 833         """
 834         self.count = count
 835
 836     def add_object(self, object):
 837         """Add an object."""
 838         raise NotImplementedError(self.add_object)
 839
 840     def finish(self, object):
 841         """Finish the import and write objects to disk."""
 842         raise NotImplementedError(self.finish)
 843
 844
 845 class ObjectIterator(object):
 846     """Interface for iterating over objects."""
 847
 848     def iterobjects(self):
 849         raise NotImplementedError(self.iterobjects)
 850
 851
 852 class ObjectStoreIterator(ObjectIterator):
 853     """ObjectIterator that works on top of an ObjectStore."""
 854
 855     def __init__(self, store, sha_iter):
 856         """Create a new ObjectIterator.
 857
 858         :param store: Object store to retrieve from
 859         :param sha_iter: Iterator over (sha, path) tuples
 860         """
 861         self.store = store
 862         self.sha_iter = sha_iter
 863         self._shas = []
 864
 865     def __iter__(self):
 866         """Yield tuple with next object and path."""
 867         for sha, path in self.itershas():
 868             yield self.store[sha], path
 869
 870     def iterobjects(self):
 871         """Iterate over just the objects."""
 872         for o, path in self:
 873             yield o
 874
 875     def itershas(self):
 876         """Iterate over the SHAs."""
 877         for sha in self._shas:
 878             yield sha
 879         for sha in self.sha_iter:
 880             self._shas.append(sha)
 881             yield sha
 882
 883     def __contains__(self, needle):
 884         """Check if an object is present.
 885
 886         :note: This checks if the object is present in
 887             the underlying object store, not if it would
 888             be yielded by the iterator.
 889
 890         :param needle: SHA1 of the object to check for
 891         """
 892         return needle in self.store
 893
 894     def __getitem__(self, key):
 895         """Find an object by SHA1.
 896
 897         :note: This retrieves the object from the underlying
 898             object store. It will also succeed if the object would
 899             not be returned by the iterator.
 900         """
 901         return self.store[key]
 902
 903     def __len__(self):
 904         """Return the number of objects."""
 905         return len(list(self.itershas()))
 906
 907
 908 def tree_lookup_path(lookup_obj, root_sha, path):
 909     """Look up an object in a Git tree.
 910
 911     :param lookup_obj: Callback for retrieving object by SHA1
 912     :param root_sha: SHA1 of the root tree
 913     :param path: Path to lookup
 914     :return: A tuple of (mode, SHA) of the resulting path.
 915     """
 916     tree = lookup_obj(root_sha)
 917     if not isinstance(tree, Tree):
 918         raise NotTreeError(root_sha)
 919     return tree.lookup_path(lookup_obj, path)
 920
 921
 922 def _collect_filetree_revs(obj_store, tree_sha, kset):
 923     """Collect SHA1s of files and directories for specified tree.
 924
 925     :param obj_store: Object store to get objects by SHA from
 926     :param tree_sha: tree reference to walk
 927     :param kset: set to fill with references to files and directories
 928     """
 929     filetree = obj_store[tree_sha]
 930     for name, mode, sha in filetree.iteritems():
 931        if not S_ISGITLINK(mode) and sha not in kset:
 932            kset.add(sha)
 933            if stat.S_ISDIR(mode):
 934                _collect_filetree_revs(obj_store, sha, kset)
 935
 936
 937 def _split_commits_and_tags(obj_store, lst, ignore_unknown=False):
 938     """Split object id list into two list with commit SHA1s and tag SHA1s.
 939
 940     Commits referenced by tags are included into commits
 941     list as well. Only SHA1s known in this repository will get
 942     through, and unless ignore_unknown argument is True, KeyError
 943     is thrown for SHA1 missing in the repository
 944
 945     :param obj_store: Object store to get objects by SHA1 from
 946     :param lst: Collection of commit and tag SHAs
 947     :param ignore_unknown: True to skip SHA1 missing in the repository
 948         silently.
 949     :return: A tuple of (commits, tags) SHA1s
 950     """
 951     commits = set()
 952     tags = set()
 953     for e in lst:
 954         try:
 955             o = obj_store[e]
 956         except KeyError:
 957             if not ignore_unknown:
 958                 raise
 959         else:
 960             if isinstance(o, Commit):
 961                 commits.add(e)
 962             elif isinstance(o, Tag):
 963                 tags.add(e)
 964                 commits.add(o.object[1])
 965             else:
 966                 raise KeyError('Not a commit or a tag: %s' % e)
 967     return (commits, tags)
 968
 969
 970 class MissingObjectFinder(object):
 971     """Find the objects missing from another object store.
 972
 973     :param object_store: Object store containing at least all objects to be
 974         sent
 975     :param haves: SHA1s of commits not to send (already present in target)
 976     :param wants: SHA1s of commits to send
 977     :param progress: Optional function to report progress to.
 978     :param get_tagged: Function that returns a dict of pointed-to sha -> tag
 979         sha for including tags.
 980     :param get_parents: Optional function for getting the parents of a commit.
 981     :param tagged: dict of pointed-to sha -> tag sha for including tags
 982     """
 983
 984     def __init__(self, object_store, haves, wants, progress=None,
 985             get_tagged=None, get_parents=lambda commit: commit.parents):
 986         self.object_store = object_store
 987         self._get_parents = get_parents
 988         # process Commits and Tags differently
 989         # Note, while haves may list commits/tags not available locally,
 990         # and such SHAs would get filtered out by _split_commits_and_tags,
 991         # wants shall list only known SHAs, and otherwise
 992         # _split_commits_and_tags fails with KeyError
 993         have_commits, have_tags = \
 994                 _split_commits_and_tags(object_store, haves, True)
 995         want_commits, want_tags = \
 996                 _split_commits_and_tags(object_store, wants, False)
 997         # all_ancestors is a set of commits that shall not be sent
 998         # (complete repository up to 'haves')
 999         all_ancestors = object_store._collect_ancestors(
1000                 have_commits,
1001                 get_parents=self._get_parents)[0]
1002         # all_missing - complete set of commits between haves and wants
1003         # common - commits from all_ancestors we hit into while
1004         # traversing parent hierarchy of wants
1005         missing_commits, common_commits = object_store._collect_ancestors(
1006             want_commits,
1007             all_ancestors,
1008             get_parents=self._get_parents);
1009         self.sha_done = set()
1010         # Now, fill sha_done with commits and revisions of
1011         # files and directories known to be both locally
1012         # and on target. Thus these commits and files
1013         # won't get selected for fetch
1014         for h in common_commits:
1015             self.sha_done.add(h)
1016             cmt = object_store[h]
1017             _collect_filetree_revs(object_store, cmt.tree, self.sha_done)
1018         # record tags we have as visited, too
1019         for t in have_tags:
1020             self.sha_done.add(t)
1021
1022         missing_tags = want_tags.difference(have_tags)
1023         # in fact, what we 'want' is commits and tags
1024         # we've found missing
1025         wants = missing_commits.union(missing_tags)
1026
1027         self.objects_to_send = set([(w, None, False) for w in wants])
1028
1029         if progress is None:
1030             self.progress = lambda x: None
1031         else:
1032             self.progress = progress
1033         self._tagged = get_tagged and get_tagged() or {}
1034
1035     def add_todo(self, entries):
1036         self.objects_to_send.update([e for e in entries
1037                                      if not e[0] in self.sha_done])
1038
1039     def next(self):
1040         while True:
1041             if not self.objects_to_send:
1042                 return None
1043             (sha, name, leaf) = self.objects_to_send.pop()
1044             if sha not in self.sha_done:
1045                 break
1046         if not leaf:
1047             o = self.object_store[sha]
1048             if isinstance(o, Commit):
1049                 self.add_todo([(o.tree, "", False)])
1050             elif isinstance(o, Tree):
1051                 self.add_todo([(s, n, not stat.S_ISDIR(m))
1052                                for n, m, s in o.iteritems()
1053                                if not S_ISGITLINK(m)])
1054             elif isinstance(o, Tag):
1055                 self.add_todo([(o.object[1], None, False)])
1056         if sha in self._tagged:
1057             self.add_todo([(self._tagged[sha], None, True)])
1058         self.sha_done.add(sha)
1059         self.progress("counting objects: %d\r" % len(self.sha_done))
1060         return (sha, name)
1061
1062
1063 class ObjectStoreGraphWalker(object):
1064     """Graph walker that finds what commits are missing from an object store.
1065
1066     :ivar heads: Revisions without descendants in the local repo
1067     :ivar get_parents: Function to retrieve parents in the local repo
1068     """
1069
1070     def __init__(self, local_heads, get_parents):
1071         """Create a new instance.
1072
1073         :param local_heads: Heads to start search with
1074         :param get_parents: Function for finding the parents of a SHA1.
1075         """
1076         self.heads = set(local_heads)
1077         self.get_parents = get_parents
1078         self.parents = {}
1079
1080     def ack(self, sha):
1081         """Ack that a revision and its ancestors are present in the source."""
1082         ancestors = set([sha])
1083
1084         # stop if we run out of heads to remove
1085         while self.heads:
1086             for a in ancestors:
1087                 if a in self.heads:
1088                     self.heads.remove(a)
1089
1090             # collect all ancestors
1091             new_ancestors = set()
1092             for a in ancestors:
1093                 ps = self.parents.get(a)
1094                 if ps is not None:
1095                     new_ancestors.update(ps)
1096                 self.parents[a] = None
1097
1098             # no more ancestors; stop
1099             if not new_ancestors:
1100                 break
1101
1102             ancestors = new_ancestors
1103
1104     def next(self):
1105         """Iterate over ancestors of heads in the target."""
1106         if self.heads:
1107             ret = self.heads.pop()
1108             ps = self.get_parents(ret)
1109             self.parents[ret] = ps
1110             self.heads.update([p for p in ps if not p in self.parents])
1111             return ret
1112         return None