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