From be97c4558992a437cde235aafc7ae2bd6df84ac8 Mon Sep 17 00:00:00 2001 From: Sebastian Thiel Date: Tue, 22 Jun 2010 21:23:47 +0200 Subject: Initial frame for implementing read_tree using pure python. As git-read-tree can do much more than we can ( and faster assumably ), the .new method is used to create new index instances from up to 3 trees. Implemented multi-tree traversal to facilitate building a stage list more efficiently ( although I am not sure whether it could be faster to use a dictionary together with some intensive lookup ), including test Added performance to learn how fast certain operations are, and whether one should be preferred over another --- lib/git/index/base.py | 24 +++++++++++++++++++++--- lib/git/index/fun.py | 29 +++++++++++++++++++++++++---- 2 files changed, 46 insertions(+), 7 deletions(-) (limited to 'lib/git/index') diff --git a/lib/git/index/base.py b/lib/git/index/base.py index 06437702..f1be00e0 100644 --- a/lib/git/index/base.py +++ b/lib/git/index/base.py @@ -133,7 +133,6 @@ class IndexFile(LazyMixin, diff.Diffable, Serializable): def _index_path(self): return join_path_native(self.repo.git_dir, "index") - @property def path(self): """ :return: Path to the index file we are representing """ @@ -240,6 +239,26 @@ class IndexFile(LazyMixin, diff.Diffable, Serializable): self.repo.git.read_tree(args) return self + @classmethod + def new(cls, repo, *tree_sha): + """ Merge the given treeish revisions into a new index which is returned. + This method behaves like git-read-tree --aggressive when doing the merge. + + :param repo: The repository treeish are located in. + + :param *tree_sha: + see ``from_tree`` + + :return: + New IndexFile instance. Its path will be undefined. + If you intend to write such a merged Index, supply an alternate file_path + to its 'write' method.""" + base_entries = aggressive_tree_merge(repo.odb, tree_sha) + + inst = cls(self.repo) + raise NotImplementedError("convert to entries") + + @classmethod def from_tree(cls, repo, *treeish, **kwargs): """ @@ -275,8 +294,7 @@ class IndexFile(LazyMixin, diff.Diffable, Serializable): As the underlying git-read-tree command takes into account the current index, it will be temporarily moved out of the way to assure there are no unsuspected - interferences. - """ + interferences.""" if len(treeish) == 0 or len(treeish) > 3: raise ValueError("Please specify between 1 and 3 treeish, got %i" % len(treeish)) diff --git a/lib/git/index/fun.py b/lib/git/index/fun.py index 9f877a66..962e139a 100644 --- a/lib/git/index/fun.py +++ b/lib/git/index/fun.py @@ -12,8 +12,10 @@ from git.utils import ( ) from typ import ( + BaseIndexEntry, IndexEntry, - CE_NAMEMASK + CE_NAMEMASK, + CE_STAGESHIFT ) from util import ( @@ -23,7 +25,6 @@ from util import ( from gitdb.base import IStream from gitdb.typ import str_tree_type -from binascii import a2b_hex __all__ = ('write_cache', 'read_cache', 'write_tree_from_cache', 'entry_key' ) @@ -150,6 +151,7 @@ def write_tree_from_cache(entries, odb, sl, si=0): :return: tuple(binsha, list(tree_entry, ...)) a tuple of a sha and a list of tree entries being a tuple of hexsha, mode, name""" tree_items = list() + tree_items_append = tree_items.append ci = sl.start end = sl.stop while ci < end: @@ -161,7 +163,7 @@ def write_tree_from_cache(entries, odb, sl, si=0): rbound = entry.path.find('/', si) if rbound == -1: # its not a tree - tree_items.append((entry.binsha, entry.mode, entry.path[si:])) + tree_items_append((entry.binsha, entry.mode, entry.path[si:])) else: # find common base range base = entry.path[si:rbound] @@ -178,7 +180,7 @@ def write_tree_from_cache(entries, odb, sl, si=0): # enter recursion # ci - 1 as we want to count our current item as well sha, tree_entry_list = write_tree_from_cache(entries, odb, slice(ci-1, xi), rbound+1) - tree_items.append((sha, S_IFDIR, base)) + tree_items_append((sha, S_IFDIR, base)) # skip ahead ci = xi @@ -193,5 +195,24 @@ def write_tree_from_cache(entries, odb, sl, si=0): istream = odb.store(IStream(str_tree_type, len(sio.getvalue()), sio)) return (istream.binsha, tree_items) +def _tree_entry_to_baseindexentry(tree_entry, stage): + return BaseIndexEntry(tree_entry[1], tree_entry[0], stage < Date: Wed, 23 Jun 2010 00:28:36 +0200 Subject: Implemented simple tree merging and a simple test, more elaborate testing is in progress --- lib/git/index/fun.py | 86 +++++++++++++++++++++++++++++++++++++++++++++++----- 1 file changed, 78 insertions(+), 8 deletions(-) (limited to 'lib/git/index') diff --git a/lib/git/index/fun.py b/lib/git/index/fun.py index 962e139a..79fcfddb 100644 --- a/lib/git/index/fun.py +++ b/lib/git/index/fun.py @@ -5,11 +5,13 @@ more versatile from stat import S_IFDIR from cStringIO import StringIO +from git.utils import IndexFileSHA1Writer from git.errors import UnmergedEntriesError -from git.objects.fun import tree_to_stream -from git.utils import ( - IndexFileSHA1Writer, - ) +from git.objects.fun import ( + tree_to_stream, + traverse_tree_recursive, + traverse_trees_recursive + ) from typ import ( BaseIndexEntry, @@ -196,7 +198,7 @@ def write_tree_from_cache(entries, odb, sl, si=0): return (istream.binsha, tree_items) def _tree_entry_to_baseindexentry(tree_entry, stage): - return BaseIndexEntry(tree_entry[1], tree_entry[0], stage < Date: Wed, 23 Jun 2010 13:49:05 +0200 Subject: Added test for aggressive_tree_merge --- lib/git/index/fun.py | 129 ++++++++++++++++++++++++++------------------------- lib/git/index/typ.py | 3 ++ 2 files changed, 68 insertions(+), 64 deletions(-) (limited to 'lib/git/index') diff --git a/lib/git/index/fun.py b/lib/git/index/fun.py index 79fcfddb..b04d018f 100644 --- a/lib/git/index/fun.py +++ b/lib/git/index/fun.py @@ -218,71 +218,72 @@ def aggressive_tree_merge(odb, tree_shas): for entry in traverse_tree_recursive(odb, tree_shas[-1], ''): out_append(_tree_entry_to_baseindexentry(entry, 0)) # END for each entry - elif len(tree_shas) == 3: - for base, ours, theirs in traverse_trees_recursive(odb, tree_shas, ''): - if base is not None: - # base version exists - if ours is not None: - # ours exists - if theirs is not None: - # it exists in all branches, if it was changed in both - # its a conflict, otherwise we take the changed version - # This should be the most common branch, so it comes first - if( base[0] != ours[0] and base[0] != theirs[0] and ours[0] != theirs[0] ) or \ - ( base[1] != ours[1] and base[1] != theirs[1] and ourse[1] != theirs[1] ): - # changed by both - out_append(_tree_entry_to_baseindexentry(base, 1)) - out_append(_tree_entry_to_baseindexentry(ours, 2)) - out_append(_tree_entry_to_baseindexentry(theirs, 3)) - elif base[0] != ours[0] or base[1] != ours[1]: - # only we changed it - out_append(_tree_entry_to_baseindexentry(ours, 0)) - else: - # either nobody changed it, or they did. In either - # case, use theirs - out_append(_tree_entry_to_baseindexentry(theirs, 0)) - # END handle modification + return out + # END handle single tree + + if len(tree_shas) > 3: + raise ValueError("Cannot handle %i trees at once" % len(tree_shas)) + + # three trees + for base, ours, theirs in traverse_trees_recursive(odb, tree_shas, ''): + if base is not None: + # base version exists + if ours is not None: + # ours exists + if theirs is not None: + # it exists in all branches, if it was changed in both + # its a conflict, otherwise we take the changed version + # This should be the most common branch, so it comes first + if( base[0] != ours[0] and base[0] != theirs[0] and ours[0] != theirs[0] ) or \ + ( base[1] != ours[1] and base[1] != theirs[1] and ours[1] != theirs[1] ): + # changed by both + out_append(_tree_entry_to_baseindexentry(base, 1)) + out_append(_tree_entry_to_baseindexentry(ours, 2)) + out_append(_tree_entry_to_baseindexentry(theirs, 3)) + elif base[0] != ours[0] or base[1] != ours[1]: + # only we changed it + out_append(_tree_entry_to_baseindexentry(ours, 0)) else: - - if ours[0] != base[0] or ours[1] != base[1]: - # they deleted it, we changed it, conflict - out_append(_tree_entry_to_baseindexentry(base, 1)) - out_append(_tree_entry_to_baseindexentry(ours, 2)) - out_append(_tree_entry_to_baseindexentry(theirs, 3)) - # else: - # we didn't change it, ignore - # pass - # END handle our change - # END handle theirs + # either nobody changed it, or they did. In either + # case, use theirs + out_append(_tree_entry_to_baseindexentry(theirs, 0)) + # END handle modification else: - if theirs is None: - # deleted in both, its fine - its out - pass - else: - if theirs[0] != base[0] or theirs[1] != base[1]: - # deleted in ours, changed theirs, conflict - out_append(_tree_entry_to_baseindexentry(base, 1)) - out_append(_tree_entry_to_baseindexentry(ours, 2)) - out_append(_tree_entry_to_baseindexentry(theirs, 3)) - # END theirs changed - #else: - # theirs didnt change - # pass - # END handle theirs - # END handle ours + + if ours[0] != base[0] or ours[1] != base[1]: + # they deleted it, we changed it, conflict + out_append(_tree_entry_to_baseindexentry(base, 1)) + out_append(_tree_entry_to_baseindexentry(ours, 2)) + # else: + # we didn't change it, ignore + # pass + # END handle our change + # END handle theirs else: - # all three can't be None - if ours is None: - # added in their branch - out_append(_tree_entry_to_baseindexentry(theirs, 0)) - elif theirs is None: - # added in our branch - out_append(_tree_entry_to_baseindexentry(ours, 0)) - # END hanle heads - # END handle base exists - # END for each entries tuple - else: - raise ValueError("Cannot handle %i trees at once" % len(tree_shas)) - # END handle tree shas - + if theirs is None: + # deleted in both, its fine - its out + pass + else: + if theirs[0] != base[0] or theirs[1] != base[1]: + # deleted in ours, changed theirs, conflict + out_append(_tree_entry_to_baseindexentry(base, 1)) + out_append(_tree_entry_to_baseindexentry(theirs, 3)) + # END theirs changed + #else: + # theirs didnt change + # pass + # END handle theirs + # END handle ours + else: + # all three can't be None + if ours is None: + # added in their branch + out_append(_tree_entry_to_baseindexentry(theirs, 0)) + elif theirs is None: + # added in our branch + out_append(_tree_entry_to_baseindexentry(ours, 0)) + # END hanle heads + # END handle base exists + # END for each entries tuple + return out diff --git a/lib/git/index/typ.py b/lib/git/index/typ.py index 6ef1d2f2..d9cafa2e 100644 --- a/lib/git/index/typ.py +++ b/lib/git/index/typ.py @@ -56,6 +56,9 @@ class BaseIndexEntry(tuple): def __str__(self): return "%o %s %i\t%s" % (self.mode, self.hexsha, self.stage, self.path) + + def __repr__(self): + return "(%o, %s, %i, %s)" % (self.mode, self.hexsha, self.stage, self.path) @property def mode(self): -- cgit v1.2.3 From 1e2265a23ecec4e4d9ad60d788462e7f124f1bb7 Mon Sep 17 00:00:00 2001 From: Sebastian Thiel Date: Wed, 23 Jun 2010 15:48:57 +0200 Subject: fixed critical bug in traverse_trees_recursive, implemented IndexFile.new including simple test, it may be simple as the methods it uses are throroughly tested --- lib/git/index/base.py | 17 ++++++++++++----- lib/git/index/fun.py | 11 ++++++----- 2 files changed, 18 insertions(+), 10 deletions(-) (limited to 'lib/git/index') diff --git a/lib/git/index/base.py b/lib/git/index/base.py index f1be00e0..af45171b 100644 --- a/lib/git/index/base.py +++ b/lib/git/index/base.py @@ -59,14 +59,16 @@ from git.utils import ( ) from fun import ( + entry_key, write_cache, read_cache, - write_tree_from_cache, - entry_key + aggressive_tree_merge, + write_tree_from_cache ) from gitdb.base import IStream from gitdb.db import MemoryDB +from itertools import izip __all__ = ( 'IndexFile', 'CheckoutError' ) @@ -253,10 +255,15 @@ class IndexFile(LazyMixin, diff.Diffable, Serializable): New IndexFile instance. Its path will be undefined. If you intend to write such a merged Index, supply an alternate file_path to its 'write' method.""" - base_entries = aggressive_tree_merge(repo.odb, tree_sha) + base_entries = aggressive_tree_merge(repo.odb, [str(t) for t in tree_sha]) - inst = cls(self.repo) - raise NotImplementedError("convert to entries") + inst = cls(repo) + # convert to entries dict + entries = dict(izip(((e.path, e.stage) for e in base_entries), + (IndexEntry.from_base(e) for e in base_entries))) + + inst.entries = entries + return inst @classmethod diff --git a/lib/git/index/fun.py b/lib/git/index/fun.py index b04d018f..23a6d8f9 100644 --- a/lib/git/index/fun.py +++ b/lib/git/index/fun.py @@ -78,15 +78,16 @@ def write_cache(entries, stream, extension_data=None, ShaStreamCls=IndexFileSHA1 def read_entry(stream): """Return: One entry of the given stream""" beginoffset = stream.tell() - ctime = unpack(">8s", stream.read(8))[0] - mtime = unpack(">8s", stream.read(8))[0] + read = stream.read + ctime = unpack(">8s", read(8))[0] + mtime = unpack(">8s", read(8))[0] (dev, ino, mode, uid, gid, size, sha, flags) = \ - unpack(">LLLLLL20sH", stream.read(20 + 4 * 6 + 2)) + unpack(">LLLLLL20sH", read(20 + 4 * 6 + 2)) path_size = flags & CE_NAMEMASK - path = stream.read(path_size) + path = read(path_size) real_size = ((stream.tell() - beginoffset + 8) & ~7) - data = stream.read((beginoffset + real_size) - stream.tell()) + data = read((beginoffset + real_size) - stream.tell()) return IndexEntry((mode, sha, flags, path, ctime, mtime, dev, ino, uid, gid, size)) def read_header(stream): -- cgit v1.2.3