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