688ccd6b5f07e1ea1e27fb7ca2be678ae676837d
[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         """
319         if len(objects) == 0:
320             # Don't bother writing an empty pack file
321             return
322         f, commit = self.add_pack()
323         write_pack_data(f, objects, len(objects))
324         commit()
325
326
327 class DiskObjectStore(PackBasedObjectStore):
328     """Git-style object store that exists on disk."""
329
330     def __init__(self, path):
331         """Open an object store.
332
333         :param path: Path of the object store.
334         """
335         super(DiskObjectStore, self).__init__()
336         self.path = path
337         self.pack_dir = os.path.join(self.path, PACKDIR)
338         self._pack_cache_time = 0
339
340     def _load_packs(self):
341         pack_files = []
342         try:
343             self._pack_cache_time = os.stat(self.pack_dir).st_mtime
344             pack_dir_contents = os.listdir(self.pack_dir)
345             for name in pack_dir_contents:
346                 # TODO: verify that idx exists first
347                 if name.startswith("pack-") and name.endswith(".pack"):
348                     filename = os.path.join(self.pack_dir, name)
349                     pack_files.append((os.stat(filename).st_mtime, filename))
350         except OSError, e:
351             if e.errno == errno.ENOENT:
352                 return []
353             raise
354         pack_files.sort(reverse=True)
355         suffix_len = len(".pack")
356         return [Pack(f[:-suffix_len]) for _, f in pack_files]
357
358     def _pack_cache_stale(self):
359         try:
360             return os.stat(self.pack_dir).st_mtime > self._pack_cache_time
361         except OSError, e:
362             if e.errno == errno.ENOENT:
363                 return True
364             raise
365
366     def _get_shafile_path(self, sha):
367         # Check from object dir
368         return hex_to_filename(self.path, sha)
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 = ThinPackData(self, 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)
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()), len(p))
406         pack_sha = load_pack_index(temppath+".idx").objects_sha1()
407         newbasename = os.path.join(self.pack_dir, "pack-%s" % pack_sha)
408         os.rename(temppath+".pack", newbasename+".pack")
409         os.rename(temppath+".idx", newbasename+".idx")
410         self._add_known_pack(Pack(newbasename))
411
412     def move_in_pack(self, path):
413         """Move a specific file containing a pack into the pack directory.
414
415         :note: The file should be on the same file system as the 
416             packs directory.
417
418         :param path: Path to the pack file.
419         """
420         p = PackData(path)
421         entries = p.sorted_entries()
422         basename = os.path.join(self.pack_dir, 
423             "pack-%s" % iter_sha1(entry[0] for entry in entries))
424         write_pack_index_v2(basename+".idx", entries, p.get_stored_checksum())
425         p.close()
426         os.rename(path, basename + ".pack")
427         self._add_known_pack(Pack(basename))
428
429     def add_thin_pack(self):
430         """Add a new thin pack to this object store.
431
432         Thin packs are packs that contain deltas with parents that exist 
433         in a different pack.
434         """
435         fd, path = tempfile.mkstemp(dir=self.pack_dir, suffix=".pack")
436         f = os.fdopen(fd, 'wb')
437         def commit():
438             os.fsync(fd)
439             f.close()
440             if os.path.getsize(path) > 0:
441                 self.move_in_thin_pack(path)
442         return f, commit
443
444     def add_pack(self):
445         """Add a new pack to this object store. 
446
447         :return: Fileobject to write to and a commit function to 
448             call when the pack is finished.
449         """
450         fd, path = tempfile.mkstemp(dir=self.pack_dir, suffix=".pack")
451         f = os.fdopen(fd, 'wb')
452         def commit():
453             os.fsync(fd)
454             f.close()
455             if os.path.getsize(path) > 0:
456                 self.move_in_pack(path)
457         return f, commit
458
459     def add_object(self, obj):
460         """Add a single object to this object store.
461
462         :param obj: Object to add
463         """
464         dir = os.path.join(self.path, obj.id[:2])
465         try:
466             os.mkdir(dir)
467         except OSError, e:
468             if e.errno != errno.EEXIST:
469                 raise
470         path = os.path.join(dir, obj.id[2:])
471         if os.path.exists(path):
472             return # Already there, no need to write again
473         f = GitFile(path, 'wb')
474         try:
475             f.write(obj.as_legacy_object())
476         finally:
477             f.close()
478
479     @classmethod
480     def init(cls, path):
481         try:
482             os.mkdir(path)
483         except OSError, e:
484             if e.errno != errno.EEXIST:
485                 raise
486         os.mkdir(os.path.join(path, "info"))
487         os.mkdir(os.path.join(path, PACKDIR))
488         return cls(path)
489
490
491 class MemoryObjectStore(BaseObjectStore):
492     """Object store that keeps all objects in memory."""
493
494     def __init__(self):
495         super(MemoryObjectStore, self).__init__()
496         self._data = {}
497
498     def contains_loose(self, sha):
499         """Check if a particular object is present by SHA1 and is loose."""
500         return sha in self._data
501
502     def contains_packed(self, sha):
503         """Check if a particular object is present by SHA1 and is packed."""
504         return False
505
506     def __iter__(self):
507         """Iterate over the SHAs that are present in this store."""
508         return self._data.iterkeys()
509
510     @property
511     def packs(self):
512         """List with pack objects."""
513         return []
514
515     def get_raw(self, name):
516         """Obtain the raw text for an object.
517
518         :param name: sha for the object.
519         :return: tuple with numeric type and object contents.
520         """
521         return self[name].as_raw_string()
522
523     def __getitem__(self, name):
524         return self._data[name]
525
526     def add_object(self, obj):
527         """Add a single object to this object store.
528
529         """
530         self._data[obj.id] = obj
531
532     def add_objects(self, objects):
533         """Add a set of objects to this object store.
534
535         :param objects: Iterable over a list of objects.
536         """
537         for obj, path in objects:
538             self._data[obj.id] = obj
539
540
541 class ObjectImporter(object):
542     """Interface for importing objects."""
543
544     def __init__(self, count):
545         """Create a new ObjectImporter.
546
547         :param count: Number of objects that's going to be imported.
548         """
549         self.count = count
550
551     def add_object(self, object):
552         """Add an object."""
553         raise NotImplementedError(self.add_object)
554
555     def finish(self, object):
556         """Finish the imoprt and write objects to disk."""
557         raise NotImplementedError(self.finish)
558
559
560 class ObjectIterator(object):
561     """Interface for iterating over objects."""
562
563     def iterobjects(self):
564         raise NotImplementedError(self.iterobjects)
565
566
567 class ObjectStoreIterator(ObjectIterator):
568     """ObjectIterator that works on top of an ObjectStore."""
569
570     def __init__(self, store, sha_iter):
571         """Create a new ObjectIterator.
572
573         :param store: Object store to retrieve from
574         :param sha_iter: Iterator over (sha, path) tuples
575         """
576         self.store = store
577         self.sha_iter = sha_iter
578         self._shas = []
579
580     def __iter__(self):
581         """Yield tuple with next object and path."""
582         for sha, path in self.itershas():
583             yield self.store[sha], path
584
585     def iterobjects(self):
586         """Iterate over just the objects."""
587         for o, path in self:
588             yield o
589
590     def itershas(self):
591         """Iterate over the SHAs."""
592         for sha in self._shas:
593             yield sha
594         for sha in self.sha_iter:
595             self._shas.append(sha)
596             yield sha
597
598     def __contains__(self, needle):
599         """Check if an object is present.
600
601         :note: This checks if the object is present in 
602             the underlying object store, not if it would
603             be yielded by the iterator.
604
605         :param needle: SHA1 of the object to check for
606         """
607         return needle in self.store
608
609     def __getitem__(self, key):
610         """Find an object by SHA1.
611         
612         :note: This retrieves the object from the underlying
613             object store. It will also succeed if the object would
614             not be returned by the iterator.
615         """
616         return self.store[key]
617
618     def __len__(self):
619         """Return the number of objects."""
620         return len(list(self.itershas()))
621
622
623 def tree_lookup_path(lookup_obj, root_sha, path):
624     """Lookup an object in a Git tree.
625
626     :param lookup_obj: Callback for retrieving object by SHA1
627     :param root_sha: SHA1 of the root tree
628     :param path: Path to lookup
629     """
630     parts = path.split("/")
631     sha = root_sha
632     mode = None
633     for p in parts:
634         obj = lookup_obj(sha)
635         if not isinstance(obj, Tree):
636             raise NotTreeError(sha)
637         if p == '':
638             continue
639         mode, sha = obj[p]
640     return mode, sha
641
642
643 class MissingObjectFinder(object):
644     """Find the objects missing from another object store.
645
646     :param object_store: Object store containing at least all objects to be 
647         sent
648     :param haves: SHA1s of commits not to send (already present in target)
649     :param wants: SHA1s of commits to send
650     :param progress: Optional function to report progress to.
651     :param get_tagged: Function that returns a dict of pointed-to sha -> tag
652         sha for including tags.
653     :param tagged: dict of pointed-to sha -> tag sha for including tags
654     """
655
656     def __init__(self, object_store, haves, wants, progress=None,
657                  get_tagged=None):
658         self.sha_done = set(haves)
659         self.objects_to_send = set([(w, None, False) for w in wants if w not in haves])
660         self.object_store = object_store
661         if progress is None:
662             self.progress = lambda x: None
663         else:
664             self.progress = progress
665         self._tagged = get_tagged and get_tagged() or {}
666
667     def add_todo(self, entries):
668         self.objects_to_send.update([e for e in entries if not e[0] in self.sha_done])
669
670     def parse_tree(self, tree):
671         self.add_todo([(sha, name, not stat.S_ISDIR(mode)) for (mode, name, sha) in tree.entries() if not S_ISGITLINK(mode)])
672
673     def parse_commit(self, commit):
674         self.add_todo([(commit.tree, "", False)])
675         self.add_todo([(p, None, False) for p in commit.parents])
676
677     def parse_tag(self, tag):
678         self.add_todo([(tag.object[1], None, False)])
679
680     def next(self):
681         if not self.objects_to_send:
682             return None
683         (sha, name, leaf) = self.objects_to_send.pop()
684         if not leaf:
685             o = self.object_store[sha]
686             if isinstance(o, Commit):
687                 self.parse_commit(o)
688             elif isinstance(o, Tree):
689                 self.parse_tree(o)
690             elif isinstance(o, Tag):
691                 self.parse_tag(o)
692         if sha in self._tagged:
693             self.add_todo([(self._tagged[sha], None, True)])
694         self.sha_done.add(sha)
695         self.progress("counting objects: %d\r" % len(self.sha_done))
696         return (sha, name)
697
698
699 class ObjectStoreGraphWalker(object):
700     """Graph walker that finds out what commits are missing from an object 
701     store.
702     
703     :ivar heads: Revisions without descendants in the local repo
704     :ivar get_parents: Function to retrieve parents in the local repo
705     """
706
707     def __init__(self, local_heads, get_parents):
708         """Create a new instance.
709
710         :param local_heads: Heads to start search with
711         :param get_parents: Function for finding the parents of a SHA1.
712         """
713         self.heads = set(local_heads)
714         self.get_parents = get_parents
715         self.parents = {}
716
717     def ack(self, sha):
718         """Ack that a revision and its ancestors are present in the source."""
719         ancestors = set([sha])
720
721         # stop if we run out of heads to remove
722         while self.heads:
723             for a in ancestors:
724                 if a in self.heads:
725                     self.heads.remove(a)
726
727             # collect all ancestors
728             new_ancestors = set()
729             for a in ancestors:
730                 if a in self.parents:
731                     new_ancestors.update(self.parents[a])
732
733             # no more ancestors; stop
734             if not new_ancestors:
735                 break
736
737             ancestors = new_ancestors
738
739     def next(self):
740         """Iterate over ancestors of heads in the target."""
741         if self.heads:
742             ret = self.heads.pop()
743             ps = self.get_parents(ret)
744             self.parents[ret] = ps
745             self.heads.update(ps)
746             return ret
747         return None