dulwich/object_store.py

   1 # object_store.py -- Object store for git objects
   2 # Copyright (C) 2008-2009 Jelmer Vernooij <jelmer@samba.org>
   3 #
   4 # This program is free software; you can redistribute it and/or
   5 # modify it under the terms of the GNU General Public License
   6 # as published by the Free Software Foundation; either version 2
   7 # or (at your option) a later version of the License.
   8 #
   9 # This program is distributed in the hope that it will be useful,
  10 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 # GNU General Public License for more details.
  13 #
  14 # You should have received a copy of the GNU General Public License
  15 # along with this program; if not, write to the Free Software
  16 # Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
  17 # MA  02110-1301, USA.
  18
  19
  20 """Git object store interfaces and implementation."""
  21
  22
  23 import errno
  24 import itertools
  25 import os
  26 import posixpath
  27 import stat
  28 import tempfile
  29 import urllib2
  30
  31 from dulwich.errors import (
  32     NotTreeError,
  33     )
  34 from dulwich.file import GitFile
  35 from dulwich.objects import (
  36     Commit,
  37     ShaFile,
  38     Tag,
  39     Tree,
  40     hex_to_sha,
  41     sha_to_hex,
  42     hex_to_filename,
  43     S_ISGITLINK,
  44     object_class,
  45     )
  46 from dulwich.pack import (
  47     Pack,
  48     PackData,
  49     ThinPackData,
  50     iter_sha1,
  51     load_pack_index,
  52     write_pack,
  53     write_pack_data,
  54     write_pack_index_v2,
  55     )
  56
  57 INFODIR = 'info'
  58 PACKDIR = 'pack'
  59
  60
  61 class BaseObjectStore(object):
  62     """Object store interface."""
  63
  64     def determine_wants_all(self, refs):
  65         return [sha for (ref, sha) in refs.iteritems()
  66                 if not sha in self and not ref.endswith("^{}")]
  67
  68     def iter_shas(self, shas):
  69         """Iterate over the objects for the specified shas.
  70
  71         :param shas: Iterable object with SHAs
  72         :return: Object iterator
  73         """
  74         return ObjectStoreIterator(self, shas)
  75
  76     def contains_loose(self, sha):
  77         """Check if a particular object is present by SHA1 and is loose."""
  78         raise NotImplementedError(self.contains_loose)
  79
  80     def contains_packed(self, sha):
  81         """Check if a particular object is present by SHA1 and is packed."""
  82         raise NotImplementedError(self.contains_packed)
  83
  84     def __contains__(self, sha):
  85         """Check if a particular object is present by SHA1.
  86
  87         This method makes no distinction between loose and packed objects.
  88         """
  89         return self.contains_packed(sha) or self.contains_loose(sha)
  90
  91     @property
  92     def packs(self):
  93         """Iterable of pack objects."""
  94         raise NotImplementedError
  95
  96     def get_raw(self, name):
  97         """Obtain the raw text for an object.
  98
  99         :param name: sha for the object.
 100         :return: tuple with numeric type and object contents.
 101         """
 102         raise NotImplementedError(self.get_raw)
 103
 104     def __getitem__(self, sha):
 105         """Obtain an object by SHA1."""
 106         type_num, uncomp = self.get_raw(sha)
 107         return ShaFile.from_raw_string(type_num, uncomp)
 108
 109     def __iter__(self):
 110         """Iterate over the SHAs that are present in this store."""
 111         raise NotImplementedError(self.__iter__)
 112
 113     def add_object(self, obj):
 114         """Add a single object to this object store.
 115
 116         """
 117         raise NotImplementedError(self.add_object)
 118
 119     def add_objects(self, objects):
 120         """Add a set of objects to this object store.
 121
 122         :param objects: Iterable over a list of objects.
 123         """
 124         raise NotImplementedError(self.add_objects)
 125
 126     def tree_changes(self, source, target, want_unchanged=False):
 127         """Find the differences between the contents of two trees
 128
 129         :param object_store: Object store to use for retrieving tree contents
 130         :param tree: SHA1 of the root tree
 131         :param want_unchanged: Whether unchanged files should be reported
 132         :return: Iterator over tuples with (oldpath, newpath), (oldmode, newmode), (oldsha, newsha)
 133         """
 134         todo = set([(source, target, "")])
 135         while todo:
 136             (sid, tid, path) = todo.pop()
 137             if sid is not None:
 138                 stree = self[sid]
 139             else:
 140                 stree = {}
 141             if tid is not None:
 142                 ttree = self[tid]
 143             else:
 144                 ttree = {}
 145             for name, oldmode, oldhexsha in stree.iteritems():
 146                 oldchildpath = posixpath.join(path, name)
 147                 try:
 148                     (newmode, newhexsha) = ttree[name]
 149                     newchildpath = oldchildpath
 150                 except KeyError:
 151                     newmode = None
 152                     newhexsha = None
 153                     newchildpath = None
 154                 if (want_unchanged or oldmode != newmode or
 155                     oldhexsha != newhexsha):
 156                     if stat.S_ISDIR(oldmode):
 157                         if newmode is None or stat.S_ISDIR(newmode):
 158                             todo.add((oldhexsha, newhexsha, oldchildpath))
 159                         else:
 160                             # entry became a file
 161                             todo.add((oldhexsha, None, oldchildpath))
 162                             yield ((None, newchildpath), (None, newmode), (None, newhexsha))
 163                     else:
 164                         if newmode is not None and stat.S_ISDIR(newmode):
 165                             # entry became a dir
 166                             yield ((oldchildpath, None), (oldmode, None), (oldhexsha, None))
 167                             todo.add((None, newhexsha, newchildpath))
 168                         else:
 169                             yield ((oldchildpath, newchildpath), (oldmode, newmode), (oldhexsha, newhexsha))
 170
 171             for name, newmode, newhexsha in ttree.iteritems():
 172                 childpath = posixpath.join(path, name)
 173                 if not name in stree:
 174                     if not stat.S_ISDIR(newmode):
 175                         yield ((None, childpath), (None, newmode), (None, newhexsha))
 176                     else:
 177                         todo.add((None, newhexsha, childpath))
 178
 179     def iter_tree_contents(self, tree_id, include_trees=False):
 180         """Iterate the contents of a tree and all subtrees.
 181
 182         Iteration is depth-first pre-order, as in e.g. os.walk.
 183
 184         :param tree_id: SHA1 of the tree.
 185         :param include_trees: If True, include tree objects in the iteration.
 186         :yield: Tuples of (path, mode, hexhsa) for objects in a tree.
 187         """
 188         todo = [('', stat.S_IFDIR, tree_id)]
 189         while todo:
 190             path, mode, hexsha = todo.pop()
 191             is_subtree = stat.S_ISDIR(mode)
 192             if not is_subtree or include_trees:
 193                 yield path, mode, hexsha
 194             if is_subtree:
 195                 entries = reversed(list(self[hexsha].iteritems()))
 196                 for name, entry_mode, entry_hexsha in entries:
 197                     entry_path = posixpath.join(path, name)
 198                     todo.append((entry_path, entry_mode, entry_hexsha))
 199
 200     def find_missing_objects(self, haves, wants, progress=None,
 201                              get_tagged=None):
 202         """Find the missing objects required for a set of revisions.
 203
 204         :param haves: Iterable over SHAs already in common.
 205         :param wants: Iterable over SHAs of objects to fetch.
 206         :param progress: Simple progress function that will be called with
 207             updated progress strings.
 208         :param get_tagged: Function that returns a dict of pointed-to sha -> tag
 209             sha for including tags.
 210         :return: Iterator over (sha, path) pairs.
 211         """
 212         finder = MissingObjectFinder(self, haves, wants, progress, get_tagged)
 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 = graphwalker.next()
 223         while sha:
 224             if sha in self:
 225                 haves.append(sha)
 226                 graphwalker.ack(sha)
 227             sha = graphwalker.next()
 228         return haves
 229
 230     def get_graph_walker(self, heads):
 231         """Obtain a graph walker for this object store.
 232
 233         :param heads: Local heads to start search with
 234         :return: GraphWalker object
 235         """
 236         return ObjectStoreGraphWalker(heads, lambda sha: self[sha].parents)
 237
 238     def generate_pack_contents(self, have, want, progress=None):
 239         """Iterate over the contents of a pack file.
 240
 241         :param have: List of SHA1s of objects that should not be sent
 242         :param want: List of SHA1s of objects that should be sent
 243         :param progress: Optional progress reporting method
 244         """
 245         return self.iter_shas(self.find_missing_objects(have, want, progress))
 246
 247     def peel_sha(self, sha):
 248         """Peel all tags from a SHA.
 249
 250         :param sha: The object SHA to peel.
 251         :return: The fully-peeled SHA1 of a tag object, after peeling all
 252             intermediate tags; if the original ref does not point to a tag, this
 253             will equal the original SHA1.
 254         """
 255         obj = self[sha]
 256         obj_class = object_class(obj.type_name)
 257         while obj_class is Tag:
 258             obj_class, sha = obj.object
 259             obj = self[sha]
 260         return obj
 261
 262
 263 class PackBasedObjectStore(BaseObjectStore):
 264
 265     def __init__(self):
 266         self._pack_cache = None
 267
 268     def contains_packed(self, sha):
 269         """Check if a particular object is present by SHA1 and is packed."""
 270         for pack in self.packs:
 271             if sha in pack:
 272                 return True
 273         return False
 274
 275     def _load_packs(self):
 276         raise NotImplementedError(self._load_packs)
 277
 278     def _pack_cache_stale(self):
 279         """Check whether the pack cache is stale."""
 280         raise NotImplementedError(self._pack_cache_stale)
 281
 282     def _add_known_pack(self, pack):
 283         """Add a newly appeared pack to the cache by path.
 284
 285         """
 286         if self._pack_cache is not None:
 287             self._pack_cache.append(pack)
 288
 289     @property
 290     def packs(self):
 291         """List with pack objects."""
 292         if self._pack_cache is None or self._pack_cache_stale():
 293             self._pack_cache = self._load_packs()
 294         return self._pack_cache
 295
 296     def _iter_loose_objects(self):
 297         """Iterate over the SHAs of all loose objects."""
 298         raise NotImplementedError(self._iter_loose_objects)
 299
 300     def _get_loose_object(self, sha):
 301         raise NotImplementedError(self._get_loose_object)
 302
 303     def _remove_loose_object(self, sha):
 304         raise NotImplementedError(self._remove_loose_object)
 305
 306     def pack_loose_objects(self):
 307         """Pack loose objects.
 308
 309         :return: Number of objects packed
 310         """
 311         objects = set()
 312         for sha in self._iter_loose_objects():
 313             objects.add((self._get_loose_object(sha), None))
 314         self.add_objects(objects)
 315         for obj, path in objects:
 316             self._remove_loose_object(obj.id)
 317         return len(objects)
 318
 319     def __iter__(self):
 320         """Iterate over the SHAs that are present in this store."""
 321         iterables = self.packs + [self._iter_loose_objects()]
 322         return itertools.chain(*iterables)
 323
 324     def contains_loose(self, sha):
 325         """Check if a particular object is present by SHA1 and is loose."""
 326         return self._get_loose_object(sha) is not None
 327
 328     def get_raw(self, name):
 329         """Obtain the raw text for an object.
 330
 331         :param name: sha for the object.
 332         :return: tuple with numeric type and object contents.
 333         """
 334         if len(name) == 40:
 335             sha = hex_to_sha(name)
 336             hexsha = name
 337         elif len(name) == 20:
 338             sha = name
 339             hexsha = None
 340         else:
 341             raise AssertionError
 342         for pack in self.packs:
 343             try:
 344                 return pack.get_raw(sha)
 345             except KeyError:
 346                 pass
 347         if hexsha is None:
 348             hexsha = sha_to_hex(name)
 349         ret = self._get_loose_object(hexsha)
 350         if ret is not None:
 351             return ret.type_num, ret.as_raw_string()
 352         raise KeyError(hexsha)
 353
 354     def add_objects(self, objects):
 355         """Add a set of objects to this object store.
 356
 357         :param objects: Iterable over objects, should support __len__.
 358         :return: Pack object of the objects written.
 359         """
 360         if len(objects) == 0:
 361             # Don't bother writing an empty pack file
 362             return
 363         f, commit = self.add_pack()
 364         write_pack_data(f, objects, len(objects))
 365         return commit()
 366
 367
 368 class DiskObjectStore(PackBasedObjectStore):
 369     """Git-style object store that exists on disk."""
 370
 371     def __init__(self, path):
 372         """Open an object store.
 373
 374         :param path: Path of the object store.
 375         """
 376         super(DiskObjectStore, self).__init__()
 377         self.path = path
 378         self.pack_dir = os.path.join(self.path, PACKDIR)
 379         self._pack_cache_time = 0
 380
 381     def _load_packs(self):
 382         pack_files = []
 383         try:
 384             self._pack_cache_time = os.stat(self.pack_dir).st_mtime
 385             pack_dir_contents = os.listdir(self.pack_dir)
 386             for name in pack_dir_contents:
 387                 # TODO: verify that idx exists first
 388                 if name.startswith("pack-") and name.endswith(".pack"):
 389                     filename = os.path.join(self.pack_dir, name)
 390                     pack_files.append((os.stat(filename).st_mtime, filename))
 391         except OSError, e:
 392             if e.errno == errno.ENOENT:
 393                 return []
 394             raise
 395         pack_files.sort(reverse=True)
 396         suffix_len = len(".pack")
 397         return [Pack(f[:-suffix_len]) for _, f in pack_files]
 398
 399     def _pack_cache_stale(self):
 400         try:
 401             return os.stat(self.pack_dir).st_mtime > self._pack_cache_time
 402         except OSError, e:
 403             if e.errno == errno.ENOENT:
 404                 return True
 405             raise
 406
 407     def _get_shafile_path(self, sha):
 408         # Check from object dir
 409         return hex_to_filename(self.path, sha)
 410
 411     def _iter_loose_objects(self):
 412         for base in os.listdir(self.path):
 413             if len(base) != 2:
 414                 continue
 415             for rest in os.listdir(os.path.join(self.path, base)):
 416                 yield base+rest
 417
 418     def _get_loose_object(self, sha):
 419         path = self._get_shafile_path(sha)
 420         try:
 421             return ShaFile.from_path(path)
 422         except (OSError, IOError), e:
 423             if e.errno == errno.ENOENT:
 424                 return None
 425             raise
 426
 427     def _remove_loose_object(self, sha):
 428         os.remove(self._get_shafile_path(sha))
 429
 430     def move_in_thin_pack(self, path):
 431         """Move a specific file containing a pack into the pack directory.
 432
 433         :note: The file should be on the same file system as the
 434             packs directory.
 435
 436         :param path: Path to the pack file.
 437         """
 438         data = ThinPackData(self.get_raw, path)
 439
 440         # Write index for the thin pack (do we really need this?)
 441         temppath = os.path.join(self.pack_dir,
 442             sha_to_hex(urllib2.randombytes(20))+".tempidx")
 443         data.create_index_v2(temppath)
 444         p = Pack.from_objects(data, load_pack_index(temppath))
 445
 446         # Write a full pack version
 447         temppath = os.path.join(self.pack_dir,
 448             sha_to_hex(urllib2.randombytes(20))+".temppack")
 449         write_pack(temppath, ((o, None) for o in p.iterobjects()), len(p))
 450         pack_sha = load_pack_index(temppath+".idx").objects_sha1()
 451         newbasename = os.path.join(self.pack_dir, "pack-%s" % pack_sha)
 452         os.rename(temppath+".pack", newbasename+".pack")
 453         os.rename(temppath+".idx", newbasename+".idx")
 454         final_pack = Pack(newbasename)
 455         self._add_known_pack(final_pack)
 456         return final_pack
 457
 458     def move_in_pack(self, path):
 459         """Move a specific file containing a pack into the pack directory.
 460
 461         :note: The file should be on the same file system as the
 462             packs directory.
 463
 464         :param path: Path to the pack file.
 465         """
 466         p = PackData(path)
 467         entries = p.sorted_entries()
 468         basename = os.path.join(self.pack_dir,
 469             "pack-%s" % iter_sha1(entry[0] for entry in entries))
 470         f = GitFile(basename+".idx", "wb")
 471         try:
 472             write_pack_index_v2(f, entries, p.get_stored_checksum())
 473         finally:
 474             f.close()
 475         p.close()
 476         os.rename(path, basename + ".pack")
 477         final_pack = Pack(basename)
 478         self._add_known_pack(final_pack)
 479         return final_pack
 480
 481     def add_thin_pack(self):
 482         """Add a new thin pack to this object store.
 483
 484         Thin packs are packs that contain deltas with parents that exist
 485         in a different pack.
 486         """
 487         fd, path = tempfile.mkstemp(dir=self.pack_dir, suffix=".pack")
 488         f = os.fdopen(fd, 'wb')
 489         def commit():
 490             os.fsync(fd)
 491             f.close()
 492             if os.path.getsize(path) > 0:
 493                 return self.move_in_thin_pack(path)
 494             else:
 495                 return None
 496         return f, commit
 497
 498     def add_pack(self):
 499         """Add a new pack to this object store.
 500
 501         :return: Fileobject to write to and a commit function to
 502             call when the pack is finished.
 503         """
 504         fd, path = tempfile.mkstemp(dir=self.pack_dir, suffix=".pack")
 505         f = os.fdopen(fd, 'wb')
 506         def commit():
 507             os.fsync(fd)
 508             f.close()
 509             if os.path.getsize(path) > 0:
 510                 return self.move_in_pack(path)
 511             else:
 512                 return None
 513         return f, commit
 514
 515     def add_object(self, obj):
 516         """Add a single object to this object store.
 517
 518         :param obj: Object to add
 519         """
 520         dir = os.path.join(self.path, obj.id[:2])
 521         try:
 522             os.mkdir(dir)
 523         except OSError, e:
 524             if e.errno != errno.EEXIST:
 525                 raise
 526         path = os.path.join(dir, obj.id[2:])
 527         if os.path.exists(path):
 528             return # Already there, no need to write again
 529         f = GitFile(path, 'wb')
 530         try:
 531             f.write(obj.as_legacy_object())
 532         finally:
 533             f.close()
 534
 535     @classmethod
 536     def init(cls, path):
 537         try:
 538             os.mkdir(path)
 539         except OSError, e:
 540             if e.errno != errno.EEXIST:
 541                 raise
 542         os.mkdir(os.path.join(path, "info"))
 543         os.mkdir(os.path.join(path, PACKDIR))
 544         return cls(path)
 545
 546
 547 class MemoryObjectStore(BaseObjectStore):
 548     """Object store that keeps all objects in memory."""
 549
 550     def __init__(self):
 551         super(MemoryObjectStore, self).__init__()
 552         self._data = {}
 553
 554     def contains_loose(self, sha):
 555         """Check if a particular object is present by SHA1 and is loose."""
 556         return sha in self._data
 557
 558     def contains_packed(self, sha):
 559         """Check if a particular object is present by SHA1 and is packed."""
 560         return False
 561
 562     def __iter__(self):
 563         """Iterate over the SHAs that are present in this store."""
 564         return self._data.iterkeys()
 565
 566     @property
 567     def packs(self):
 568         """List with pack objects."""
 569         return []
 570
 571     def get_raw(self, name):
 572         """Obtain the raw text for an object.
 573
 574         :param name: sha for the object.
 575         :return: tuple with numeric type and object contents.
 576         """
 577         return self[name].as_raw_string()
 578
 579     def __getitem__(self, name):
 580         return self._data[name]
 581
 582     def add_object(self, obj):
 583         """Add a single object to this object store.
 584
 585         """
 586         self._data[obj.id] = obj
 587
 588     def add_objects(self, objects):
 589         """Add a set of objects to this object store.
 590
 591         :param objects: Iterable over a list of objects.
 592         """
 593         for obj, path in objects:
 594             self._data[obj.id] = obj
 595
 596
 597 class ObjectImporter(object):
 598     """Interface for importing objects."""
 599
 600     def __init__(self, count):
 601         """Create a new ObjectImporter.
 602
 603         :param count: Number of objects that's going to be imported.
 604         """
 605         self.count = count
 606
 607     def add_object(self, object):
 608         """Add an object."""
 609         raise NotImplementedError(self.add_object)
 610
 611     def finish(self, object):
 612         """Finish the import and write objects to disk."""
 613         raise NotImplementedError(self.finish)
 614
 615
 616 class ObjectIterator(object):
 617     """Interface for iterating over objects."""
 618
 619     def iterobjects(self):
 620         raise NotImplementedError(self.iterobjects)
 621
 622
 623 class ObjectStoreIterator(ObjectIterator):
 624     """ObjectIterator that works on top of an ObjectStore."""
 625
 626     def __init__(self, store, sha_iter):
 627         """Create a new ObjectIterator.
 628
 629         :param store: Object store to retrieve from
 630         :param sha_iter: Iterator over (sha, path) tuples
 631         """
 632         self.store = store
 633         self.sha_iter = sha_iter
 634         self._shas = []
 635
 636     def __iter__(self):
 637         """Yield tuple with next object and path."""
 638         for sha, path in self.itershas():
 639             yield self.store[sha], path
 640
 641     def iterobjects(self):
 642         """Iterate over just the objects."""
 643         for o, path in self:
 644             yield o
 645
 646     def itershas(self):
 647         """Iterate over the SHAs."""
 648         for sha in self._shas:
 649             yield sha
 650         for sha in self.sha_iter:
 651             self._shas.append(sha)
 652             yield sha
 653
 654     def __contains__(self, needle):
 655         """Check if an object is present.
 656
 657         :note: This checks if the object is present in
 658             the underlying object store, not if it would
 659             be yielded by the iterator.
 660
 661         :param needle: SHA1 of the object to check for
 662         """
 663         return needle in self.store
 664
 665     def __getitem__(self, key):
 666         """Find an object by SHA1.
 667
 668         :note: This retrieves the object from the underlying
 669             object store. It will also succeed if the object would
 670             not be returned by the iterator.
 671         """
 672         return self.store[key]
 673
 674     def __len__(self):
 675         """Return the number of objects."""
 676         return len(list(self.itershas()))
 677
 678
 679 def tree_lookup_path(lookup_obj, root_sha, path):
 680     """Lookup an object in a Git tree.
 681
 682     :param lookup_obj: Callback for retrieving object by SHA1
 683     :param root_sha: SHA1 of the root tree
 684     :param path: Path to lookup
 685     """
 686     parts = path.split("/")
 687     sha = root_sha
 688     mode = None
 689     for p in parts:
 690         obj = lookup_obj(sha)
 691         if not isinstance(obj, Tree):
 692             raise NotTreeError(sha)
 693         if p == '':
 694             continue
 695         mode, sha = obj[p]
 696     return mode, sha
 697
 698
 699 class MissingObjectFinder(object):
 700     """Find the objects missing from another object store.
 701
 702     :param object_store: Object store containing at least all objects to be
 703         sent
 704     :param haves: SHA1s of commits not to send (already present in target)
 705     :param wants: SHA1s of commits to send
 706     :param progress: Optional function to report progress to.
 707     :param get_tagged: Function that returns a dict of pointed-to sha -> tag
 708         sha for including tags.
 709     :param tagged: dict of pointed-to sha -> tag sha for including tags
 710     """
 711
 712     def __init__(self, object_store, haves, wants, progress=None,
 713                  get_tagged=None):
 714         self.sha_done = set(haves)
 715         self.objects_to_send = set([(w, None, False) for w in wants if w not in haves])
 716         self.object_store = object_store
 717         if progress is None:
 718             self.progress = lambda x: None
 719         else:
 720             self.progress = progress
 721         self._tagged = get_tagged and get_tagged() or {}
 722
 723     def add_todo(self, entries):
 724         self.objects_to_send.update([e for e in entries if not e[0] in self.sha_done])
 725
 726     def parse_tree(self, tree):
 727         self.add_todo([(sha, name, not stat.S_ISDIR(mode)) for (mode, name, sha) in tree.entries() if not S_ISGITLINK(mode)])
 728
 729     def parse_commit(self, commit):
 730         self.add_todo([(commit.tree, "", False)])
 731         self.add_todo([(p, None, False) for p in commit.parents])
 732
 733     def parse_tag(self, tag):
 734         self.add_todo([(tag.object[1], None, False)])
 735
 736     def next(self):
 737         if not self.objects_to_send:
 738             return None
 739         (sha, name, leaf) = self.objects_to_send.pop()
 740         if not leaf:
 741             o = self.object_store[sha]
 742             if isinstance(o, Commit):
 743                 self.parse_commit(o)
 744             elif isinstance(o, Tree):
 745                 self.parse_tree(o)
 746             elif isinstance(o, Tag):
 747                 self.parse_tag(o)
 748         if sha in self._tagged:
 749             self.add_todo([(self._tagged[sha], None, True)])
 750         self.sha_done.add(sha)
 751         self.progress("counting objects: %d\r" % len(self.sha_done))
 752         return (sha, name)
 753
 754
 755 class ObjectStoreGraphWalker(object):
 756     """Graph walker that finds what commits are missing from an object store.
 757
 758     :ivar heads: Revisions without descendants in the local repo
 759     :ivar get_parents: Function to retrieve parents in the local repo
 760     """
 761
 762     def __init__(self, local_heads, get_parents):
 763         """Create a new instance.
 764
 765         :param local_heads: Heads to start search with
 766         :param get_parents: Function for finding the parents of a SHA1.
 767         """
 768         self.heads = set(local_heads)
 769         self.get_parents = get_parents
 770         self.parents = {}
 771
 772     def ack(self, sha):
 773         """Ack that a revision and its ancestors are present in the source."""
 774         ancestors = set([sha])
 775
 776         # stop if we run out of heads to remove
 777         while self.heads:
 778             for a in ancestors:
 779                 if a in self.heads:
 780                     self.heads.remove(a)
 781
 782             # collect all ancestors
 783             new_ancestors = set()
 784             for a in ancestors:
 785                 if a in self.parents:
 786                     new_ancestors.update(self.parents[a])
 787
 788             # no more ancestors; stop
 789             if not new_ancestors:
 790                 break
 791
 792             ancestors = new_ancestors
 793
 794     def next(self):
 795         """Iterate over ancestors of heads in the target."""
 796         if self.heads:
 797             ret = self.heads.pop()
 798             ps = self.get_parents(ret)
 799             self.parents[ret] = ps
 800             self.heads.update(ps)
 801             return ret
 802         return None