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