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         self._pack_cache_time = 0
 344
 345     def _load_packs(self):
 346         pack_files = []
 347         try:
 348             self._pack_cache_time = os.stat(self.pack_dir).st_mtime
 349             pack_dir_contents = os.listdir(self.pack_dir)
 350             for name in pack_dir_contents:
 351                 # TODO: verify that idx exists first
 352                 if name.startswith("pack-") and name.endswith(".pack"):
 353                     filename = os.path.join(self.pack_dir, name)
 354                     pack_files.append((os.stat(filename).st_mtime, filename))
 355         except OSError, e:
 356             if e.errno == errno.ENOENT:
 357                 return []
 358             raise
 359         pack_files.sort(reverse=True)
 360         suffix_len = len(".pack")
 361         return [Pack(f[:-suffix_len]) for _, f in pack_files]
 362
 363     def _pack_cache_stale(self):
 364         try:
 365             return os.stat(self.pack_dir).st_mtime > self._pack_cache_time
 366         except OSError, e:
 367             if e.errno == errno.ENOENT:
 368                 return True
 369             raise
 370
 371     def _get_shafile_path(self, sha):
 372         dir = sha[:2]
 373         file = sha[2:]
 374         # Check from object dir
 375         return os.path.join(self.path, dir, file)
 376
 377     def _iter_loose_objects(self):
 378         for base in os.listdir(self.path):
 379             if len(base) != 2:
 380                 continue
 381             for rest in os.listdir(os.path.join(self.path, base)):
 382                 yield base+rest
 383
 384     def _get_loose_object(self, sha):
 385         path = self._get_shafile_path(sha)
 386         try:
 387             return ShaFile.from_file(path)
 388         except OSError, e:
 389             if e.errno == errno.ENOENT:
 390                 return None
 391             raise
 392
 393     def move_in_thin_pack(self, path):
 394         """Move a specific file containing a pack into the pack directory.
 395
 396         :note: The file should be on the same file system as the
 397             packs directory.
 398
 399         :param path: Path to the pack file.
 400         """
 401         data = PackData(path)
 402
 403         # Write index for the thin pack (do we really need this?)
 404         temppath = os.path.join(self.pack_dir,
 405             sha_to_hex(urllib2.randombytes(20))+".tempidx")
 406         data.create_index_v2(temppath, self.get_raw)
 407         p = Pack.from_objects(data, load_pack_index(temppath))
 408
 409         # Write a full pack version
 410         temppath = os.path.join(self.pack_dir,
 411             sha_to_hex(urllib2.randombytes(20))+".temppack")
 412         write_pack(temppath, ((o, None) for o in p.iterobjects(self.get_raw)),
 413                 len(p))
 414         pack_sha = load_pack_index(temppath+".idx").objects_sha1()
 415         newbasename = os.path.join(self.pack_dir, "pack-%s" % pack_sha)
 416         os.rename(temppath+".pack", newbasename+".pack")
 417         os.rename(temppath+".idx", newbasename+".idx")
 418         self._add_known_pack(Pack(newbasename))
 419
 420     def move_in_pack(self, path):
 421         """Move a specific file containing a pack into the pack directory.
 422
 423         :note: The file should be on the same file system as the
 424             packs directory.
 425
 426         :param path: Path to the pack file.
 427         """
 428         p = PackData(path)
 429         entries = p.sorted_entries()
 430         basename = os.path.join(self.pack_dir,
 431             "pack-%s" % iter_sha1(entry[0] for entry in entries))
 432         write_pack_index_v2(basename+".idx", entries, p.get_stored_checksum())
 433         p.close()
 434         os.rename(path, basename + ".pack")
 435         self._add_known_pack(Pack(basename))
 436
 437     def add_thin_pack(self):
 438         """Add a new thin pack to this object store.
 439
 440         Thin packs are packs that contain deltas with parents that exist
 441         in a different pack.
 442         """
 443         fd, path = tempfile.mkstemp(dir=self.pack_dir, suffix=".pack")
 444         f = os.fdopen(fd, 'wb')
 445         def commit():
 446             os.fsync(fd)
 447             f.close()
 448             if os.path.getsize(path) > 0:
 449                 self.move_in_thin_pack(path)
 450         return f, commit
 451
 452     def add_pack(self):
 453         """Add a new pack to this object store.
 454
 455         :return: Fileobject to write to and a commit function to
 456             call when the pack is finished.
 457         """
 458         fd, path = tempfile.mkstemp(dir=self.pack_dir, suffix=".pack")
 459         f = os.fdopen(fd, 'wb')
 460         def commit():
 461             os.fsync(fd)
 462             f.close()
 463             if os.path.getsize(path) > 0:
 464                 self.move_in_pack(path)
 465         return f, commit
 466
 467     def add_object(self, obj):
 468         """Add a single object to this object store.
 469
 470         :param obj: Object to add
 471         """
 472         dir = os.path.join(self.path, obj.id[:2])
 473         if not os.path.isdir(dir):
 474             os.mkdir(dir)
 475         path = os.path.join(dir, obj.id[2:])
 476         if os.path.exists(path):
 477             return # Already there, no need to write again
 478         f = GitFile(path, 'wb')
 479         try:
 480             f.write(obj.as_legacy_object())
 481         finally:
 482             f.close()
 483
 484
 485 class MemoryObjectStore(BaseObjectStore):
 486     """Object store that keeps all objects in memory."""
 487
 488     def __init__(self):
 489         super(MemoryObjectStore, self).__init__()
 490         self._data = {}
 491
 492     def contains_loose(self, sha):
 493         """Check if a particular object is present by SHA1 and is loose."""
 494         return sha in self._data
 495
 496     def contains_packed(self, sha):
 497         """Check if a particular object is present by SHA1 and is packed."""
 498         return False
 499
 500     def __iter__(self):
 501         """Iterate over the SHAs that are present in this store."""
 502         return self._data.iterkeys()
 503
 504     @property
 505     def packs(self):
 506         """List with pack objects."""
 507         return []
 508
 509     def get_raw(self, name):
 510         """Obtain the raw text for an object.
 511
 512         :param name: sha for the object.
 513         :return: tuple with object type and object contents.
 514         """
 515         return self[name].as_raw_string()
 516
 517     def __getitem__(self, name):
 518         return self._data[name]
 519
 520     def add_object(self, obj):
 521         """Add a single object to this object store.
 522
 523         """
 524         self._data[obj.id] = obj
 525
 526     def add_objects(self, objects):
 527         """Add a set of objects to this object store.
 528
 529         :param objects: Iterable over a list of objects.
 530         """
 531         for obj, path in objects:
 532             self._data[obj.id] = obj
 533
 534
 535 class ObjectImporter(object):
 536     """Interface for importing objects."""
 537
 538     def __init__(self, count):
 539         """Create a new ObjectImporter.
 540
 541         :param count: Number of objects that's going to be imported.
 542         """
 543         self.count = count
 544
 545     def add_object(self, object):
 546         """Add an object."""
 547         raise NotImplementedError(self.add_object)
 548
 549     def finish(self, object):
 550         """Finish the imoprt and write objects to disk."""
 551         raise NotImplementedError(self.finish)
 552
 553
 554 class ObjectIterator(object):
 555     """Interface for iterating over objects."""
 556
 557     def iterobjects(self):
 558         raise NotImplementedError(self.iterobjects)
 559
 560
 561 class ObjectStoreIterator(ObjectIterator):
 562     """ObjectIterator that works on top of an ObjectStore."""
 563
 564     def __init__(self, store, sha_iter):
 565         """Create a new ObjectIterator.
 566
 567         :param store: Object store to retrieve from
 568         :param sha_iter: Iterator over (sha, path) tuples
 569         """
 570         self.store = store
 571         self.sha_iter = sha_iter
 572         self._shas = []
 573
 574     def __iter__(self):
 575         """Yield tuple with next object and path."""
 576         for sha, path in self.itershas():
 577             yield self.store[sha], path
 578
 579     def iterobjects(self):
 580         """Iterate over just the objects."""
 581         for o, path in self:
 582             yield o
 583
 584     def itershas(self):
 585         """Iterate over the SHAs."""
 586         for sha in self._shas:
 587             yield sha
 588         for sha in self.sha_iter:
 589             self._shas.append(sha)
 590             yield sha
 591
 592     def __contains__(self, needle):
 593         """Check if an object is present.
 594
 595         :note: This checks if the object is present in
 596             the underlying object store, not if it would
 597             be yielded by the iterator.
 598
 599         :param needle: SHA1 of the object to check for
 600         """
 601         return needle in self.store
 602
 603     def __getitem__(self, key):
 604         """Find an object by SHA1.
 605
 606         :note: This retrieves the object from the underlying
 607             object store. It will also succeed if the object would
 608             not be returned by the iterator.
 609         """
 610         return self.store[key]
 611
 612     def __len__(self):
 613         """Return the number of objects."""
 614         return len(list(self.itershas()))
 615
 616
 617 def tree_lookup_path(lookup_obj, root_sha, path):
 618     """Lookup an object in a Git tree.
 619
 620     :param lookup_obj: Callback for retrieving object by SHA1
 621     :param root_sha: SHA1 of the root tree
 622     :param path: Path to lookup
 623     """
 624     parts = path.split("/")
 625     sha = root_sha
 626     for p in parts:
 627         obj = lookup_obj(sha)
 628         if type(obj) is not Tree:
 629             raise NotTreeError(sha)
 630         if p == '':
 631             continue
 632         mode, sha = obj[p]
 633     return mode, sha
 634
 635
 636 class MissingObjectFinder(object):
 637     """Find the objects missing from another object store.
 638
 639     :param object_store: Object store containing at least all objects to be
 640         sent
 641     :param haves: SHA1s of commits not to send (already present in target)
 642     :param wants: SHA1s of commits to send
 643     :param progress: Optional function to report progress to.
 644     :param get_tagged: Function that returns a dict of pointed-to sha -> tag
 645         sha for including tags.
 646     :param tagged: dict of pointed-to sha -> tag sha for including tags
 647     """
 648
 649     def __init__(self, object_store, haves, wants, progress=None,
 650                  get_tagged=None):
 651         self.sha_done = set(haves)
 652         self.objects_to_send = set([(w, None, False) for w in wants if w not in haves])
 653         self.object_store = object_store
 654         if progress is None:
 655             self.progress = lambda x: None
 656         else:
 657             self.progress = progress
 658         self._tagged = get_tagged and get_tagged() or {}
 659
 660     def add_todo(self, entries):
 661         self.objects_to_send.update([e for e in entries if not e[0] in self.sha_done])
 662
 663     def parse_tree(self, tree):
 664         self.add_todo([(sha, name, not stat.S_ISDIR(mode)) for (mode, name, sha) in tree.entries() if not S_ISGITLINK(mode)])
 665
 666     def parse_commit(self, commit):
 667         self.add_todo([(commit.tree, "", False)])
 668         self.add_todo([(p, None, False) for p in commit.parents])
 669
 670     def parse_tag(self, tag):
 671         self.add_todo([(tag.object[1], None, False)])
 672
 673     def next(self):
 674         if not self.objects_to_send:
 675             return None
 676         (sha, name, leaf) = self.objects_to_send.pop()
 677         if not leaf:
 678             o = self.object_store[sha]
 679             if isinstance(o, Commit):
 680                 self.parse_commit(o)
 681             elif isinstance(o, Tree):
 682                 self.parse_tree(o)
 683             elif isinstance(o, Tag):
 684                 self.parse_tag(o)
 685         if sha in self._tagged:
 686             self.add_todo([(self._tagged[sha], None, True)])
 687         self.sha_done.add(sha)
 688         self.progress("counting objects: %d\r" % len(self.sha_done))
 689         return (sha, name)
 690
 691
 692 class ObjectStoreGraphWalker(object):
 693     """Graph walker that finds out what commits are missing from an object store."""
 694
 695     def __init__(self, local_heads, get_parents):
 696         """Create a new instance.
 697
 698         :param local_heads: Heads to start search with
 699         :param get_parents: Function for finding the parents of a SHA1.
 700         """
 701         self.heads = set(local_heads)
 702         self.get_parents = get_parents
 703         self.parents = {}
 704
 705     def ack(self, sha):
 706         """Ack that a particular revision and its ancestors are present in the source."""
 707         if sha in self.heads:
 708             self.heads.remove(sha)
 709         if sha in self.parents:
 710             for p in self.parents[sha]:
 711                 self.ack(p)
 712
 713     def next(self):
 714         """Iterate over ancestors of heads in the target."""
 715         if self.heads:
 716             ret = self.heads.pop()
 717             ps = self.get_parents(ret)
 718             self.parents[ret] = ps
 719             self.heads.update(ps)
 720             return ret
 721         return None