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