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