dulwich/object_store.py

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