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/fun.py | 29 +++++++++++++++++++++++++---- 1 file changed, 25 insertions(+), 4 deletions(-) (limited to 'lib/git/index/fun.py') 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/fun.py') 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 ++++++++++++++++++++++++++------------------------- 1 file changed, 65 insertions(+), 64 deletions(-) (limited to 'lib/git/index/fun.py') 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 -- 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/fun.py | 11 ++++++----- 1 file changed, 6 insertions(+), 5 deletions(-) (limited to 'lib/git/index/fun.py') 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