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