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