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