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