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