dulwich/object_store.py

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