Add cgit compatibility testing framework.
[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 _pack_cache_stale(self):
257         """Check whether the pack cache is stale."""
258         raise NotImplementedError(self._pack_cache_stale)
259
260     def _add_known_pack(self, pack):
261         """Add a newly appeared pack to the cache by path.
262
263         """
264         if self._pack_cache is not None:
265             self._pack_cache.append(pack)
266
267     @property
268     def packs(self):
269         """List with pack objects."""
270         if self._pack_cache is None or self._pack_cache_stale():
271             self._pack_cache = self._load_packs()
272         return self._pack_cache
273
274     def _iter_loose_objects(self):
275         raise NotImplementedError(self._iter_loose_objects)
276
277     def _get_loose_object(self, sha):
278         raise NotImplementedError(self._get_loose_object)
279
280     def __iter__(self):
281         """Iterate over the SHAs that are present in this store."""
282         iterables = self.packs + [self._iter_loose_objects()]
283         return itertools.chain(*iterables)
284
285     def contains_loose(self, sha):
286         """Check if a particular object is present by SHA1 and is loose."""
287         return self._get_loose_object(sha) is not None
288
289     def get_raw(self, name):
290         """Obtain the raw text for an object.
291         
292         :param name: sha for the object.
293         :return: tuple with object type and object contents.
294         """
295         if len(name) == 40:
296             sha = hex_to_sha(name)
297             hexsha = name
298         elif len(name) == 20:
299             sha = name
300             hexsha = None
301         else:
302             raise AssertionError
303         for pack in self.packs:
304             try:
305                 return pack.get_raw(sha)
306             except KeyError:
307                 pass
308         if hexsha is None: 
309             hexsha = sha_to_hex(name)
310         ret = self._get_loose_object(hexsha)
311         if ret is not None:
312             return ret.type, ret.as_raw_string()
313         raise KeyError(hexsha)
314
315     def add_objects(self, objects):
316         """Add a set of objects to this object store.
317
318         :param objects: Iterable over objects, should support __len__.
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         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         dir = sha[:2]
369         file = sha[2:]
370         # Check from object dir
371         return os.path.join(self.path, dir, file)
372
373     def _iter_loose_objects(self):
374         for base in os.listdir(self.path):
375             if len(base) != 2:
376                 continue
377             for rest in os.listdir(os.path.join(self.path, base)):
378                 yield base+rest
379
380     def _get_loose_object(self, sha):
381         path = self._get_shafile_path(sha)
382         try:
383             return ShaFile.from_file(path)
384         except OSError, e:
385             if e.errno == errno.ENOENT:
386                 return None
387             raise
388
389     def move_in_thin_pack(self, path):
390         """Move a specific file containing a pack into the pack directory.
391
392         :note: The file should be on the same file system as the 
393             packs directory.
394
395         :param path: Path to the pack file.
396         """
397         data = PackData(path)
398
399         # Write index for the thin pack (do we really need this?)
400         temppath = os.path.join(self.pack_dir, 
401             sha_to_hex(urllib2.randombytes(20))+".tempidx")
402         data.create_index_v2(temppath, self.get_raw)
403         p = Pack.from_objects(data, load_pack_index(temppath))
404
405         # Write a full pack version
406         temppath = os.path.join(self.pack_dir, 
407             sha_to_hex(urllib2.randombytes(20))+".temppack")
408         write_pack(temppath, ((o, None) for o in p.iterobjects(self.get_raw)), 
409                 len(p))
410         pack_sha = load_pack_index(temppath+".idx").objects_sha1()
411         newbasename = os.path.join(self.pack_dir, "pack-%s" % pack_sha)
412         os.rename(temppath+".pack", newbasename+".pack")
413         os.rename(temppath+".idx", newbasename+".idx")
414         self._add_known_pack(Pack(newbasename))
415
416     def move_in_pack(self, path):
417         """Move a specific file containing a pack into the pack directory.
418
419         :note: The file should be on the same file system as the 
420             packs directory.
421
422         :param path: Path to the pack file.
423         """
424         p = PackData(path)
425         entries = p.sorted_entries()
426         basename = os.path.join(self.pack_dir, 
427             "pack-%s" % iter_sha1(entry[0] for entry in entries))
428         write_pack_index_v2(basename+".idx", entries, p.get_stored_checksum())
429         p.close()
430         os.rename(path, basename + ".pack")
431         self._add_known_pack(Pack(basename))
432
433     def add_thin_pack(self):
434         """Add a new thin pack to this object store.
435
436         Thin packs are packs that contain deltas with parents that exist 
437         in a different pack.
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_thin_pack(path)
446         return f, commit
447
448     def add_pack(self):
449         """Add a new pack to this object store. 
450
451         :return: Fileobject to write to and a commit function to 
452             call when the pack is finished.
453         """
454         fd, path = tempfile.mkstemp(dir=self.pack_dir, suffix=".pack")
455         f = os.fdopen(fd, 'wb')
456         def commit():
457             os.fsync(fd)
458             f.close()
459             if os.path.getsize(path) > 0:
460                 self.move_in_pack(path)
461         return f, commit
462
463     def add_object(self, obj):
464         """Add a single object to this object store.
465
466         :param obj: Object to add
467         """
468         dir = os.path.join(self.path, obj.id[:2])
469         if not os.path.isdir(dir):
470             os.mkdir(dir)
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
481 class MemoryObjectStore(BaseObjectStore):
482     """Object store that keeps all objects in memory."""
483
484     def __init__(self):
485         super(MemoryObjectStore, self).__init__()
486         self._data = {}
487
488     def contains_loose(self, sha):
489         """Check if a particular object is present by SHA1 and is loose."""
490         return sha in self._data
491
492     def contains_packed(self, sha):
493         """Check if a particular object is present by SHA1 and is packed."""
494         return False
495
496     def __iter__(self):
497         """Iterate over the SHAs that are present in this store."""
498         return self._data.iterkeys()
499
500     @property
501     def packs(self):
502         """List with pack objects."""
503         return []
504
505     def get_raw(self, name):
506         """Obtain the raw text for an object.
507         
508         :param name: sha for the object.
509         :return: tuple with object type and object contents.
510         """
511         return self[name].as_raw_string()
512
513     def __getitem__(self, name):
514         return self._data[name]
515
516     def add_object(self, obj):
517         """Add a single object to this object store.
518
519         """
520         self._data[obj.id] = obj
521
522     def add_objects(self, objects):
523         """Add a set of objects to this object store.
524
525         :param objects: Iterable over a list of objects.
526         """
527         for obj, path in objects:
528             self._data[obj.id] = obj
529
530
531 class ObjectImporter(object):
532     """Interface for importing objects."""
533
534     def __init__(self, count):
535         """Create a new ObjectImporter.
536
537         :param count: Number of objects that's going to be imported.
538         """
539         self.count = count
540
541     def add_object(self, object):
542         """Add an object."""
543         raise NotImplementedError(self.add_object)
544
545     def finish(self, object):
546         """Finish the imoprt and write objects to disk."""
547         raise NotImplementedError(self.finish)
548
549
550 class ObjectIterator(object):
551     """Interface for iterating over objects."""
552
553     def iterobjects(self):
554         raise NotImplementedError(self.iterobjects)
555
556
557 class ObjectStoreIterator(ObjectIterator):
558     """ObjectIterator that works on top of an ObjectStore."""
559
560     def __init__(self, store, sha_iter):
561         """Create a new ObjectIterator.
562
563         :param store: Object store to retrieve from
564         :param sha_iter: Iterator over (sha, path) tuples
565         """
566         self.store = store
567         self.sha_iter = sha_iter
568         self._shas = []
569
570     def __iter__(self):
571         """Yield tuple with next object and path."""
572         for sha, path in self.itershas():
573             yield self.store[sha], path
574
575     def iterobjects(self):
576         """Iterate over just the objects."""
577         for o, path in self:
578             yield o
579
580     def itershas(self):
581         """Iterate over the SHAs."""
582         for sha in self._shas:
583             yield sha
584         for sha in self.sha_iter:
585             self._shas.append(sha)
586             yield sha
587
588     def __contains__(self, needle):
589         """Check if an object is present.
590
591         :note: This checks if the object is present in 
592             the underlying object store, not if it would
593             be yielded by the iterator.
594
595         :param needle: SHA1 of the object to check for
596         """
597         return needle in self.store
598
599     def __getitem__(self, key):
600         """Find an object by SHA1.
601         
602         :note: This retrieves the object from the underlying
603             object store. It will also succeed if the object would
604             not be returned by the iterator.
605         """
606         return self.store[key]
607
608     def __len__(self):
609         """Return the number of objects."""
610         return len(list(self.itershas()))
611
612
613 def tree_lookup_path(lookup_obj, root_sha, path):
614     """Lookup an object in a Git tree.
615
616     :param lookup_obj: Callback for retrieving object by SHA1
617     :param root_sha: SHA1 of the root tree
618     :param path: Path to lookup
619     """
620     parts = path.split("/")
621     sha = root_sha
622     for p in parts:
623         obj = lookup_obj(sha)
624         if type(obj) is not Tree:
625             raise NotTreeError(sha)
626         if p == '':
627             continue
628         mode, sha = obj[p]
629     return mode, sha
630
631
632 class MissingObjectFinder(object):
633     """Find the objects missing from another object store.
634
635     :param object_store: Object store containing at least all objects to be 
636         sent
637     :param haves: SHA1s of commits not to send (already present in target)
638     :param wants: SHA1s of commits to send
639     :param progress: Optional function to report progress to.
640     """
641
642     def __init__(self, object_store, haves, wants, progress=None):
643         self.sha_done = set(haves)
644         self.objects_to_send = set([(w, None, False) for w in wants if w not in haves])
645         self.object_store = object_store
646         if progress is None:
647             self.progress = lambda x: None
648         else:
649             self.progress = progress
650
651     def add_todo(self, entries):
652         self.objects_to_send.update([e for e in entries if not e[0] in self.sha_done])
653
654     def parse_tree(self, tree):
655         self.add_todo([(sha, name, not stat.S_ISDIR(mode)) for (mode, name, sha) in tree.entries() if not S_ISGITLINK(mode)])
656
657     def parse_commit(self, commit):
658         self.add_todo([(commit.tree, "", False)])
659         self.add_todo([(p, None, False) for p in commit.parents])
660
661     def parse_tag(self, tag):
662         self.add_todo([(tag.object[1], None, False)])
663
664     def next(self):
665         if not self.objects_to_send:
666             return None
667         (sha, name, leaf) = self.objects_to_send.pop()
668         if not leaf:
669             o = self.object_store[sha]
670             if isinstance(o, Commit):
671                 self.parse_commit(o)
672             elif isinstance(o, Tree):
673                 self.parse_tree(o)
674             elif isinstance(o, Tag):
675                 self.parse_tag(o)
676         self.sha_done.add(sha)
677         self.progress("counting objects: %d\r" % len(self.sha_done))
678         return (sha, name)
679
680
681 class ObjectStoreGraphWalker(object):
682     """Graph walker that finds out what commits are missing from an object store."""
683
684     def __init__(self, local_heads, get_parents):
685         """Create a new instance.
686
687         :param local_heads: Heads to start search with
688         :param get_parents: Function for finding the parents of a SHA1.
689         """
690         self.heads = set(local_heads)
691         self.get_parents = get_parents
692         self.parents = {}
693
694     def ack(self, sha):
695         """Ack that a particular revision and its ancestors are present in the source."""
696         if sha in self.heads:
697             self.heads.remove(sha)
698         if sha in self.parents:
699             for p in self.parents[sha]:
700                 self.ack(p)
701
702     def next(self):
703         """Iterate over ancestors of heads in the target."""
704         if self.heads:
705             ret = self.heads.pop()
706             ps = self.get_parents(ret)
707             self.parents[ret] = ps
708             self.heads.update(ps)
709             return ret
710         return None