Provide C implementation of tree item sorter.
[jelmer/dulwich-libgit2.git] / dulwich / objects.py
1 # objects.py -- Access to base git objects
2 # Copyright (C) 2007 James Westby <jw+debian@jameswestby.net>
3 # Copyright (C) 2008-2009 Jelmer Vernooij <jelmer@samba.org>
4 #
5 # This program is free software; you can redistribute it and/or
6 # modify it under the terms of the GNU General Public License
7 # as published by the Free Software Foundation; version 2
8 # of the License or (at your option) a later version of the License.
9 #
10 # This program is distributed in the hope that it will be useful,
11 # but WITHOUT ANY WARRANTY; without even the implied warranty of
12 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13 # GNU General Public License for more details.
14 #
15 # You should have received a copy of the GNU General Public License
16 # along with this program; if not, write to the Free Software
17 # Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
18 # MA  02110-1301, USA.
19
20
21 """Access to base git objects."""
22
23
24 import binascii
25 from cStringIO import (
26     StringIO,
27     )
28 import mmap
29 import os
30 import stat
31 import time
32 import zlib
33
34 from dulwich.errors import (
35     NotBlobError,
36     NotCommitError,
37     NotTreeError,
38     )
39 from dulwich.file import GitFile
40 from dulwich.misc import (
41     make_sha,
42     )
43
44 BLOB_ID = "blob"
45 TAG_ID = "tag"
46 TREE_ID = "tree"
47 COMMIT_ID = "commit"
48 PARENT_ID = "parent"
49 AUTHOR_ID = "author"
50 COMMITTER_ID = "committer"
51 OBJECT_ID = "object"
52 TYPE_ID = "type"
53 TAGGER_ID = "tagger"
54 ENCODING_ID = "encoding"
55
56 S_IFGITLINK = 0160000
57
58 def S_ISGITLINK(m):
59     return (stat.S_IFMT(m) == S_IFGITLINK)
60
61 def _decompress(string):
62     dcomp = zlib.decompressobj()
63     dcomped = dcomp.decompress(string)
64     dcomped += dcomp.flush()
65     return dcomped
66
67
68 def sha_to_hex(sha):
69     """Takes a string and returns the hex of the sha within"""
70     hexsha = binascii.hexlify(sha)
71     assert len(hexsha) == 40, "Incorrect length of sha1 string: %d" % hexsha
72     return hexsha
73
74
75 def hex_to_sha(hex):
76     """Takes a hex sha and returns a binary sha"""
77     assert len(hex) == 40, "Incorrent length of hexsha: %s" % hex
78     return binascii.unhexlify(hex)
79
80
81 def serializable_property(name, docstring=None):
82     def set(obj, value):
83         obj._ensure_parsed()
84         setattr(obj, "_"+name, value)
85         obj._needs_serialization = True
86     def get(obj):
87         obj._ensure_parsed()
88         return getattr(obj, "_"+name)
89     return property(get, set, doc=docstring)
90
91
92 class ShaFile(object):
93     """A git SHA file."""
94
95     @classmethod
96     def _parse_legacy_object(cls, map):
97         """Parse a legacy object, creating it and setting object._text"""
98         text = _decompress(map)
99         object = None
100         for posstype in type_map.keys():
101             if text.startswith(posstype):
102                 object = type_map[posstype]()
103                 text = text[len(posstype):]
104                 break
105         assert object is not None, "%s is not a known object type" % text[:9]
106         assert text[0] == ' ', "%s is not a space" % text[0]
107         text = text[1:]
108         size = 0
109         i = 0
110         while text[0] >= '0' and text[0] <= '9':
111             if i > 0 and size == 0:
112                 raise AssertionError("Size is not in canonical format")
113             size = (size * 10) + int(text[0])
114             text = text[1:]
115             i += 1
116         object._size = size
117         assert text[0] == "\0", "Size not followed by null"
118         text = text[1:]
119         object.set_raw_string(text)
120         return object
121
122     def as_legacy_object(self):
123         text = self.as_raw_string()
124         return zlib.compress("%s %d\0%s" % (self._type, len(text), text))
125
126     def as_raw_string(self):
127         if self._needs_serialization:
128             self.serialize()
129         return self._text
130
131     def __str__(self):
132         return self.as_raw_string()
133
134     def __hash__(self):
135         return hash(self.id)
136
137     def as_pretty_string(self):
138         return self.as_raw_string()
139
140     def _ensure_parsed(self):
141         if self._needs_parsing:
142             self._parse_text()
143
144     def set_raw_string(self, text):
145         if type(text) != str:
146             raise TypeError(text)
147         self._text = text
148         self._sha = None
149         self._needs_parsing = True
150         self._needs_serialization = False
151
152     @classmethod
153     def _parse_object(cls, map):
154         """Parse a new style object , creating it and setting object._text"""
155         used = 0
156         byte = ord(map[used])
157         used += 1
158         num_type = (byte >> 4) & 7
159         try:
160             object = num_type_map[num_type]()
161         except KeyError:
162             raise AssertionError("Not a known type: %d" % num_type)
163         while (byte & 0x80) != 0:
164             byte = ord(map[used])
165             used += 1
166         raw = map[used:]
167         object.set_raw_string(_decompress(raw))
168         return object
169
170     @classmethod
171     def _parse_file(cls, map):
172         word = (ord(map[0]) << 8) + ord(map[1])
173         if ord(map[0]) == 0x78 and (word % 31) == 0:
174             return cls._parse_legacy_object(map)
175         else:
176             return cls._parse_object(map)
177
178     def __init__(self):
179         """Don't call this directly"""
180         self._sha = None
181
182     def _parse_text(self):
183         """For subclasses to do initialisation time parsing"""
184
185     @classmethod
186     def from_file(cls, filename):
187         """Get the contents of a SHA file on disk"""
188         size = os.path.getsize(filename)
189         f = GitFile(filename, 'rb')
190         try:
191             map = mmap.mmap(f.fileno(), size, access=mmap.ACCESS_READ)
192             shafile = cls._parse_file(map)
193             return shafile
194         finally:
195             f.close()
196
197     @classmethod
198     def from_raw_string(cls, type, string):
199         """Creates an object of the indicated type from the raw string given.
200
201         Type is the numeric type of an object. String is the raw uncompressed
202         contents.
203         """
204         real_class = num_type_map[type]
205         obj = real_class()
206         obj.type = type
207         obj.set_raw_string(string)
208         return obj
209
210     @classmethod
211     def from_string(cls, string):
212         """Create a blob from a string."""
213         shafile = cls()
214         shafile.set_raw_string(string)
215         return shafile
216
217     def _raw_length(self):
218         """Returns the length of the raw string of this object."""
219         return len(self.as_raw_string())
220
221     def _header(self):
222         return "%s %lu\0" % (self._type, self._raw_length())
223
224     def _make_sha(self):
225         ret = make_sha()
226         ret.update(self._header())
227         ret.update(self.as_raw_string())
228         return ret
229
230     def sha(self):
231         """The SHA1 object that is the name of this object."""
232         if self._needs_serialization or self._sha is None:
233             self._sha = self._make_sha()
234         return self._sha
235
236     @property
237     def id(self):
238         return self.sha().hexdigest()
239
240     def get_type(self):
241         return self._num_type
242
243     def set_type(self, type):
244         self._num_type = type
245
246     type = property(get_type, set_type)
247
248     def __repr__(self):
249         return "<%s %s>" % (self.__class__.__name__, self.id)
250
251     def __ne__(self, other):
252         return self.id != other.id
253
254     def __eq__(self, other):
255         """Return true id the sha of the two objects match.
256
257         The __le__ etc methods aren't overriden as they make no sense,
258         certainly at this level.
259         """
260         return self.id == other.id
261
262
263 class Blob(ShaFile):
264     """A Git Blob object."""
265
266     _type = BLOB_ID
267     _num_type = 3
268
269     def __init__(self):
270         super(Blob, self).__init__()
271         self._chunked = []
272         self._text = ""
273         self._needs_parsing = False
274         self._needs_serialization = False
275
276     def _get_data(self):
277         if self._needs_serialization:
278             self.serialize()
279         return self._text
280
281     def _set_data(self, data):
282         self._text = data
283         self._needs_parsing = True
284         self._needs_serialization = False
285
286     data = property(_get_data, _set_data,
287             "The text contained within the blob object.")
288
289     def _get_chunked(self):
290         self._ensure_parsed()
291         return self._chunked
292
293     def _set_chunked(self, chunks):
294         self._chunked = chunks
295         self._needs_serialization = True
296
297     chunked = property(_get_chunked, _set_chunked,
298         "The text within the blob object, as chunks (not necessarily lines).")
299
300     def _parse_text(self):
301         self._chunked = [self._text]
302
303     def serialize(self):
304         self._text = "".join(self._chunked)
305
306     def _raw_length(self):
307         ret = 0
308         for chunk in self.chunked:
309             ret += len(chunk)
310         return ret
311
312     def _make_sha(self):
313         ret = make_sha()
314         ret.update(self._header())
315         for chunk in self._chunked:
316             ret.update(chunk)
317         return ret
318
319     @classmethod
320     def from_file(cls, filename):
321         blob = ShaFile.from_file(filename)
322         if blob._type != cls._type:
323             raise NotBlobError(filename)
324         return blob
325
326
327 class Tag(ShaFile):
328     """A Git Tag object."""
329
330     _type = TAG_ID
331     _num_type = 4
332
333     def __init__(self):
334         super(Tag, self).__init__()
335         self._needs_parsing = False
336         self._needs_serialization = True
337
338     @classmethod
339     def from_file(cls, filename):
340         blob = ShaFile.from_file(filename)
341         if blob._type != cls._type:
342             raise NotBlobError(filename)
343         return blob
344
345     @classmethod
346     def from_string(cls, string):
347         """Create a blob from a string."""
348         shafile = cls()
349         shafile.set_raw_string(string)
350         return shafile
351
352     def serialize(self):
353         f = StringIO()
354         f.write("%s %s\n" % (OBJECT_ID, self._object_sha))
355         f.write("%s %s\n" % (TYPE_ID, num_type_map[self._object_type]._type))
356         f.write("%s %s\n" % (TAG_ID, self._name))
357         if self._tagger:
358             if self._tag_time is None:
359                 f.write("%s %s\n" % (TAGGER_ID, self._tagger))
360             else:
361                 f.write("%s %s %d %s\n" % (TAGGER_ID, self._tagger, self._tag_time, format_timezone(self._tag_timezone)))
362         f.write("\n") # To close headers
363         f.write(self._message)
364         self._text = f.getvalue()
365         self._needs_serialization = False
366
367     def _parse_text(self):
368         """Grab the metadata attached to the tag"""
369         self._tagger = None
370         f = StringIO(self._text)
371         for l in f:
372             l = l.rstrip("\n")
373             if l == "":
374                 break # empty line indicates end of headers
375             (field, value) = l.split(" ", 1)
376             if field == OBJECT_ID:
377                 self._object_sha = value
378             elif field == TYPE_ID:
379                 self._object_type = type_map[value]
380             elif field == TAG_ID:
381                 self._name = value
382             elif field == TAGGER_ID:
383                 try:
384                     sep = value.index("> ")
385                 except ValueError:
386                     self._tagger = value
387                     self._tag_time = None
388                     self._tag_timezone = None
389                 else:
390                     self._tagger = value[0:sep+1]
391                     (timetext, timezonetext) = value[sep+2:].rsplit(" ", 1)
392                     try:
393                         self._tag_time = int(timetext)
394                     except ValueError: #Not a unix timestamp
395                         self._tag_time = time.strptime(timetext)
396                     self._tag_timezone = parse_timezone(timezonetext)
397             else:
398                 raise AssertionError("Unknown field %s" % field)
399         self._message = f.read()
400         self._needs_parsing = False
401
402     def _get_object(self):
403         """Returns the object pointed by this tag, represented as a tuple(type, sha)"""
404         self._ensure_parsed()
405         return (self._object_type, self._object_sha)
406
407     def _set_object(self, value):
408         self._ensure_parsed()
409         (self._object_type, self._object_sha) = value
410         self._needs_serialization = True
411
412     object = property(_get_object, _set_object)
413
414     name = serializable_property("name", "The name of this tag")
415     tagger = serializable_property("tagger",
416         "Returns the name of the person who created this tag")
417     tag_time = serializable_property("tag_time",
418         "The creation timestamp of the tag.  As the number of seconds since the epoch")
419     tag_timezone = serializable_property("tag_timezone",
420         "The timezone that tag_time is in.")
421     message = serializable_property("message", "The message attached to this tag")
422
423
424 def parse_tree(text):
425     """Parse a tree text.
426
427     :param text: Serialized text to parse
428     :return: Dictionary with names as keys, (mode, sha) tuples as values
429     """
430     ret = {}
431     count = 0
432     l = len(text)
433     while count < l:
434         mode_end = text.index(' ', count)
435         mode = int(text[count:mode_end], 8)
436         name_end = text.index('\0', mode_end)
437         name = text[mode_end+1:name_end]
438         count = name_end+21
439         sha = text[name_end+1:count]
440         ret[name] = (mode, sha_to_hex(sha))
441     return ret
442
443
444 def serialize_tree(items):
445     """Serialize the items in a tree to a text.
446
447     :param items: Sorted iterable over (name, mode, sha) tuples
448     :return: Serialized tree text
449     """
450     f = StringIO()
451     for name, mode, hexsha in items:
452         f.write("%04o %s\0%s" % (mode, name, hex_to_sha(hexsha)))
453     return f.getvalue()
454
455
456 def sorted_tree_items(entries):
457     """Iterate over a tree entries dictionary in the order in which 
458     the items would be serialized.
459
460     :param entries: Dictionary mapping names to (mode, sha) tuples
461     :return: Iterator over (name, mode, sha)
462     """
463     def cmp_entry((name1, value1), (name2, value2)):
464         if stat.S_ISDIR(value1[0]):
465             name1 += "/"
466         if stat.S_ISDIR(value2[0]):
467             name2 += "/"
468         return cmp(name1, name2)
469     for name, entry in sorted(entries.iteritems(), cmp=cmp_entry):
470         yield name, entry[0], entry[1]
471
472
473 class Tree(ShaFile):
474     """A Git tree object"""
475
476     _type = TREE_ID
477     _num_type = 2
478
479     def __init__(self):
480         super(Tree, self).__init__()
481         self._entries = {}
482         self._needs_parsing = False
483         self._needs_serialization = True
484
485     @classmethod
486     def from_file(cls, filename):
487         tree = ShaFile.from_file(filename)
488         if tree._type != cls._type:
489             raise NotTreeError(filename)
490         return tree
491
492     def __contains__(self, name):
493         self._ensure_parsed()
494         return name in self._entries
495
496     def __getitem__(self, name):
497         self._ensure_parsed()
498         return self._entries[name]
499
500     def __setitem__(self, name, value):
501         assert isinstance(value, tuple)
502         assert len(value) == 2
503         self._ensure_parsed()
504         self._entries[name] = value
505         self._needs_serialization = True
506
507     def __delitem__(self, name):
508         self._ensure_parsed()
509         del self._entries[name]
510         self._needs_serialization = True
511
512     def __len__(self):
513         self._ensure_parsed()
514         return len(self._entries)
515
516     def add(self, mode, name, hexsha):
517         assert type(mode) == int
518         assert type(name) == str
519         assert type(hexsha) == str
520         self._ensure_parsed()
521         self._entries[name] = mode, hexsha
522         self._needs_serialization = True
523
524     def entries(self):
525         """Return a list of tuples describing the tree entries"""
526         self._ensure_parsed()
527         # The order of this is different from iteritems() for historical
528         # reasons
529         return [
530             (mode, name, hexsha) for (name, mode, hexsha) in self.iteritems()]
531
532     def iteritems(self):
533         """Iterate over all entries in the order in which they would be
534         serialized.
535
536         :return: Iterator over (name, mode, sha) tuples
537         """
538         self._ensure_parsed()
539         return sorted_tree_items(self._entries)
540
541     def _parse_text(self):
542         """Grab the entries in the tree"""
543         self._entries = parse_tree(self._text)
544         self._needs_parsing = False
545
546     def serialize(self):
547         self._text = serialize_tree(self.iteritems())
548         self._needs_serialization = False
549
550     def as_pretty_string(self):
551         text = ""
552         for name, mode, hexsha in self.iteritems():
553             if mode & stat.S_IFDIR:
554                 kind = "tree"
555             else:
556                 kind = "blob"
557             text += "%04o %s %s\t%s\n" % (mode, kind, hexsha, name)
558         return text
559
560
561 def parse_timezone(text):
562     offset = int(text)
563     signum = (offset < 0) and -1 or 1
564     offset = abs(offset)
565     hours = int(offset / 100)
566     minutes = (offset % 100)
567     return signum * (hours * 3600 + minutes * 60)
568
569
570 def format_timezone(offset):
571     if offset % 60 != 0:
572         raise ValueError("Unable to handle non-minute offset.")
573     sign = (offset < 0) and '-' or '+'
574     offset = abs(offset)
575     return '%c%02d%02d' % (sign, offset / 3600, (offset / 60) % 60)
576
577
578 class Commit(ShaFile):
579     """A git commit object"""
580
581     _type = COMMIT_ID
582     _num_type = 1
583
584     def __init__(self):
585         super(Commit, self).__init__()
586         self._parents = []
587         self._encoding = None
588         self._needs_parsing = False
589         self._needs_serialization = True
590         self._extra = {}
591
592     @classmethod
593     def from_file(cls, filename):
594         commit = ShaFile.from_file(filename)
595         if commit._type != cls._type:
596             raise NotCommitError(filename)
597         return commit
598
599     def _parse_text(self):
600         self._parents = []
601         self._extra = []
602         self._author = None
603         f = StringIO(self._text)
604         for l in f:
605             l = l.rstrip("\n")
606             if l == "":
607                 # Empty line indicates end of headers
608                 break
609             (field, value) = l.split(" ", 1)
610             if field == TREE_ID:
611                 self._tree = value
612             elif field == PARENT_ID:
613                 self._parents.append(value)
614             elif field == AUTHOR_ID:
615                 self._author, timetext, timezonetext = value.rsplit(" ", 2)
616                 self._author_time = int(timetext)
617                 self._author_timezone = parse_timezone(timezonetext)
618             elif field == COMMITTER_ID:
619                 self._committer, timetext, timezonetext = value.rsplit(" ", 2)
620                 self._commit_time = int(timetext)
621                 self._commit_timezone = parse_timezone(timezonetext)
622             elif field == ENCODING_ID:
623                 self._encoding = value
624             else:
625                 self._extra.append((field, value))
626         self._message = f.read()
627         self._needs_parsing = False
628
629     def serialize(self):
630         f = StringIO()
631         f.write("%s %s\n" % (TREE_ID, self._tree))
632         for p in self._parents:
633             f.write("%s %s\n" % (PARENT_ID, p))
634         f.write("%s %s %s %s\n" % (AUTHOR_ID, self._author, str(self._author_time), format_timezone(self._author_timezone)))
635         f.write("%s %s %s %s\n" % (COMMITTER_ID, self._committer, str(self._commit_time), format_timezone(self._commit_timezone)))
636         if self.encoding:
637             f.write("%s %s\n" % (ENCODING_ID, self.encoding))
638         for k, v in self.extra:
639             if "\n" in k or "\n" in v:
640                 raise AssertionError("newline in extra data: %r -> %r" % (k, v))
641             f.write("%s %s\n" % (k, v))
642         f.write("\n") # There must be a new line after the headers
643         f.write(self._message)
644         self._text = f.getvalue()
645         self._needs_serialization = False
646
647     tree = serializable_property("tree", "Tree that is the state of this commit")
648
649     def _get_parents(self):
650         """Return a list of parents of this commit."""
651         self._ensure_parsed()
652         return self._parents
653
654     def _set_parents(self, value):
655         """Set a list of parents of this commit."""
656         self._ensure_parsed()
657         self._needs_serialization = True
658         self._parents = value
659
660     parents = property(_get_parents, _set_parents)
661
662     def _get_extra(self):
663         """Return extra settings of this commit."""
664         self._ensure_parsed()
665         return self._extra
666
667     extra = property(_get_extra)
668
669     author = serializable_property("author",
670         "The name of the author of the commit")
671
672     committer = serializable_property("committer",
673         "The name of the committer of the commit")
674
675     message = serializable_property("message",
676         "The commit message")
677
678     commit_time = serializable_property("commit_time",
679         "The timestamp of the commit. As the number of seconds since the epoch.")
680
681     commit_timezone = serializable_property("commit_timezone",
682         "The zone the commit time is in")
683
684     author_time = serializable_property("author_time",
685         "The timestamp the commit was written. as the number of seconds since the epoch.")
686
687     author_timezone = serializable_property("author_timezone",
688         "Returns the zone the author time is in.")
689
690     encoding = serializable_property("encoding",
691         "Encoding of the commit message.")
692
693
694 type_map = {
695     BLOB_ID : Blob,
696     TREE_ID : Tree,
697     COMMIT_ID : Commit,
698     TAG_ID: Tag,
699 }
700
701 num_type_map = {
702     0: None,
703     1: Commit,
704     2: Tree,
705     3: Blob,
706     4: Tag,
707     # 5 Is reserved for further expansion
708 }
709
710 try:
711     # Try to import C versions
712     from dulwich._objects import parse_tree, sorted_tree_items
713 except ImportError:
714     pass