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