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