From be97c4558992a437cde235aafc7ae2bd6df84ac8 Mon Sep 17 00:00:00 2001
From: Sebastian Thiel <byronimo@gmail.com>
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 +++++++--
 lib/git/objects/fun.py             | 118 +++++++++++++++++++++++++++++++++++++
 lib/git/repo.py                    |   2 +-
 test/git/performance/test_utils.py |  94 +++++++++++++++++++++++++++++
 test/git/test_fun.py               |  70 ++++++++++++++++++++++
 test/git/test_index.py             |   6 +-
 test/git/test_tree.py              |   5 ++
 8 files changed, 339 insertions(+), 9 deletions(-)
 create mode 100644 test/git/test_fun.py

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 <<CE_STAGESHIFT, tree_entry[2])
 	
+def aggressive_tree_merge(odb, tree_shas):
+	"""
+	:return: list of BaseIndexEntries representing the aggressive merge of the given
+		trees. All valid entries are on stage 0, whereas the conflicting ones are left 
+		on stage 1, 2 or 3, whereas stage 1 corresponds to the common ancestor tree, 
+		2 to our tree and 3 to 'their' tree.
+	:param tree_shas: 1, 2 or 3 trees as identified by their shas"""
+	out = list()
+	out_append = out.append
+	if len(tree_shas) == 1:
+		for entry in traverse_tree_recursive(odb, tree_shas[0]):
+			out_append(_tree_entry_to_baseindexentry(entry, 0))
+		# END for each entry
+	else:
+		raise ValueError("Cannot handle %i trees at once" % len(tree_shas))
+	# END handle tree shas
 	
+	return out
diff --git a/lib/git/objects/fun.py b/lib/git/objects/fun.py
index 7882437d..d21a7dad 100644
--- a/lib/git/objects/fun.py
+++ b/lib/git/objects/fun.py
@@ -2,6 +2,9 @@
 
 __all__ = ('tree_to_stream', 'tree_entries_from_data')
 
+from stat import S_ISDIR
+				
+
 def tree_to_stream(entries, write):
 	"""Write the give list of entries into a stream using its write method
 	:param entries: **sorted** list of tuples with (binsha, mode, name)
@@ -64,3 +67,118 @@ def tree_entries_from_data(data):
 		out.append((sha, mode, name))
 	# END for each byte in data stream
 	return out
+	
+	
+def _find_by_name(tree_data, name, is_dir, start_at):
+	"""return data entry matching the given name and tree mode
+	or None.
+	Before the item is returned, the respective data item is set 
+	None in the tree_data list to mark it done"""
+	try:
+		item = tree_data[start_at]
+		if item and  item[2] == name and S_ISDIR(item[1]) == is_dir:
+			tree_data[start_at] = None
+			return item
+	except IndexError:
+		pass
+	# END exception handling
+	for index, item in enumerate(tree_data):
+		if item and item[2] == name and S_ISDIR(item[1]) == is_dir:
+			tree_data[index] = None
+			return item
+		# END if item matches
+	# END for each item
+	return None
+
+def _to_full_path(item, path_prefix):
+	"""Rebuild entry with given path prefix"""
+	if not item:
+		return item
+	return (item[0], item[1], path_prefix+item[2])
+	
+def traverse_trees_recursive(odb, tree_shas, path_prefix):
+	"""
+	:return: list with entries according to the given tree-shas. 
+		The result is encoded in a list
+		of n tuple|None per blob/commit, (n == len(tree_shas)), where 
+		* [0] == 20 byte sha
+		* [1] == mode as int
+		* [2] == path relative to working tree root
+		The entry tuple is None if the respective blob/commit did not 
+		exist in the given tree.
+	:param tree_shas: iterable of shas pointing to trees. All trees must 
+		be on the same level. A tree-sha may be None in which case None
+	:param path_prefix: a prefix to be added to the returned paths on this level, 
+		set it '' for the first iteration
+	:note: The ordering of the returned items will be partially lost"""
+	trees_data = list()
+	nt = len(tree_shas)
+	for tree_sha in tree_shas:
+		if tree_sha is None:
+			data = list()
+		else:
+			data = tree_entries_from_data(odb.stream(tree_sha).read())
+		# END handle muted trees
+		trees_data.append(data)
+	# END for each sha to get data for
+	
+	out = list()
+	out_append = out.append
+	
+	# find all matching entries and recursively process them together if the match
+	# is a tree. If the match is a non-tree item, put it into the result.
+	# Processed items will be set None
+	for ti, tree_data in enumerate(trees_data):
+		for ii, item in enumerate(tree_data):
+			if not item:
+				continue
+			# END skip already done items
+			entries = [ None for n in range(nt) ]
+			entries[ti] = item
+			sha, mode, name = item							# its faster to unpack
+			is_dir = S_ISDIR(mode)							# type mode bits
+			
+			# find this item in all other tree data items
+			# wrap around, but stop one before our current index, hence 
+			# ti+nt, not ti+1+nt
+			for tio in range(ti+1, ti+nt):
+				tio = tio % nt
+				entries[tio] = _find_by_name(trees_data[tio], name, is_dir, ii)
+			# END for each other item data
+			
+			# if we are a directory, enter recursion
+			if is_dir:
+				out.extend(traverse_trees_recursive(odb, [ei[0] for ei in entries if ei], path_prefix+name+'/'))
+			else:
+				out_append(tuple(_to_full_path(e, path_prefix) for e in entries))
+			# END handle recursion
+			
+			# finally mark it done
+			tree_data[ii] = None
+		# END for each item
+		
+		# we are done with one tree, set all its data empty
+		del(tree_data[:])
+	# END for each tree_data chunk
+	return out
+	
+def traverse_tree_recursive(odb, tree_sha, path_prefix):
+	"""
+	:return: list of entries of the tree pointed to by tree_sha. An entry
+		has the following format:
+		* [0] 20 byte sha
+		* [1] mode as int
+		* [2] path relative to the repository
+	:param path_prefix: prefix to prepend to the front of all returned paths"""
+	entries = list()
+	data = tree_entries_from_data(odb.stream(tree_sha).read())
+	
+	# unpacking/packing is faster than accessing individual items
+	for sha, mode, name in data:
+		if S_ISDIR(mode):
+			entries.extend(traverse_tree_recursive(odb, sha, path_prefix+name+'/'))
+		else:
+			entries.append((sha, mode, path_prefix+name))
+	# END for each item
+	
+	return entries
diff --git a/lib/git/repo.py b/lib/git/repo.py
index 74525403..f97126ea 100644
--- a/lib/git/repo.py
+++ b/lib/git/repo.py
@@ -71,7 +71,7 @@ class Repo(object):
 	# represents the configuration level of a configuration file
 	config_level = ("system", "global", "repository")
 
-	def __init__(self, path=None, odbt = GitCmdObjectDB):
+	def __init__(self, path=None, odbt = GitDB):
 		""" Create a new Repo instance
 
 		:param path: is the path to either the root git directory or the bare git repo::
diff --git a/test/git/performance/test_utils.py b/test/git/performance/test_utils.py
index 76adffec..16100f8b 100644
--- a/test/git/performance/test_utils.py
+++ b/test/git/performance/test_utils.py
@@ -57,3 +57,97 @@ class TestUtilPerformance(TestBigRepoR):
 			na = ni * 3
 			print >> sys.stderr, "Accessed %s[x] %i times in %s s ( %f acc / s)" % (cls.__name__, na, elapsed, na / elapsed)
 		# END for each sequence 
+		
+	def test_instantiation(self):
+		ni = 100000
+		max_num_items = 4
+		for mni in range(max_num_items+1):
+			for cls in (tuple, list):
+				st = time()
+				for i in xrange(ni):
+					if mni == 0:
+						cls()
+					elif mni == 1:
+						cls((1,))
+					elif mni == 2:
+						cls((1,2))
+					elif mni == 3:
+						cls((1,2,3))
+					elif mni == 4:
+						cls((1,2,3,4))
+					else:
+						cls(x for x in xrange(mni))
+					# END handle empty cls
+				# END for each item
+				elapsed = time() - st
+				print >> sys.stderr, "Created %i %ss of size %i in %f s ( %f inst / s)" % (ni, cls.__name__, mni, elapsed, ni / elapsed)
+			# END for each type
+		# END for each item count
+		
+		# tuple and tuple direct
+		st = time()
+		for i in xrange(ni):
+			t = (1,2,3,4)
+		# END for each item
+		elapsed = time() - st
+		print >> sys.stderr, "Created %i tuples (1,2,3,4) in %f s ( %f tuples / s)" % (ni, elapsed, ni / elapsed)
+		
+		st = time()
+		for i in xrange(ni):
+			t = tuple((1,2,3,4))
+		# END for each item
+		elapsed = time() - st
+		print >> sys.stderr, "Created %i tuples tuple((1,2,3,4)) in %f s ( %f tuples / s)" % (ni, elapsed, ni / elapsed)
+		
+	def test_unpacking_vs_indexing(self):
+		ni = 1000000
+		list_items = [1,2,3,4]
+		tuple_items = (1,2,3,4)
+		
+		for sequence in (list_items, tuple_items):
+			st = time()
+			for i in xrange(ni):
+				one, two, three, four = sequence
+			# END for eac iteration
+			elapsed = time() - st
+			print >> sys.stderr, "Unpacked %i %ss of size %i in %f s ( %f acc / s)" % (ni, type(sequence).__name__, len(sequence), elapsed, ni / elapsed)
+			
+			st = time()
+			for i in xrange(ni):
+				one, two, three, four = sequence[0], sequence[1], sequence[2], sequence[3]
+			# END for eac iteration
+			elapsed = time() - st
+			print >> sys.stderr, "Unpacked %i %ss of size %i individually in %f s ( %f acc / s)" % (ni, type(sequence).__name__, len(sequence), elapsed, ni / elapsed)
+			
+			st = time()
+			for i in xrange(ni):
+				one, two = sequence[0], sequence[1]
+			# END for eac iteration
+			elapsed = time() - st
+			print >> sys.stderr, "Unpacked %i %ss of size %i individually (2 of 4) in %f s ( %f acc / s)" % (ni, type(sequence).__name__, len(sequence), elapsed, ni / elapsed)
+		# END for each sequence
+		
+	def test_large_list_vs_iteration(self):
+		# what costs more: alloc/realloc of lists, or the cpu strain of iterators ?
+		def slow_iter(ni):
+			for i in xrange(ni):
+				yield i
+		# END slow iter - be closer to the real world
+		
+		# alloc doesn't play a role here it seems 
+		for ni in (500, 1000, 10000, 20000, 40000):
+			st = time()
+			for i in list(xrange(ni)):
+				i
+			# END for each item
+			elapsed = time() - st
+			print >> sys.stderr, "Iterated %i items from list in %f s ( %f acc / s)" % (ni, elapsed, ni / elapsed)
+			
+			st = time()
+			for i in slow_iter(ni):
+				i
+			# END for each item
+			elapsed = time() - st
+			print >> sys.stderr, "Iterated %i items from iterator in %f s ( %f acc / s)" % (ni, elapsed, ni / elapsed)
+		# END for each number of iterations
+		
diff --git a/test/git/test_fun.py b/test/git/test_fun.py
new file mode 100644
index 00000000..ccf15c77
--- /dev/null
+++ b/test/git/test_fun.py
@@ -0,0 +1,70 @@
+from test.testlib import *
+from git.objects.fun import (
+								traverse_tree_recursive,
+								traverse_trees_recursive
+							)
+
+from git.index.fun import (
+							aggressive_tree_merge
+							)
+
+class TestFun(TestBase):
+	
+	def test_aggressive_tree_merge(self):
+		# head tree with additions, removals and modification compared to its predecessor
+		HC = self.rorepo.commit("6c1faef799095f3990e9970bc2cb10aa0221cf9c") 
+		H = HC.tree
+		B = HC.parents[0].tree
+		
+		# test new index from single tree
+	
+	def _assert_entries(self, entries, num_trees):
+		assert len(entries[0]) == num_trees
+		for entry in entries:
+			paths = set(e[2] for e in entry if e)
+			
+			# only one path per set of entries
+			assert len(paths) == 1
+		# END verify entry
+		
+	def test_tree_traversal(self):
+		# low level tree tarversal
+		odb = self.rorepo.odb
+		H = self.rorepo.tree('29eb123beb1c55e5db4aa652d843adccbd09ae18')	# head tree
+		M = self.rorepo.tree('e14e3f143e7260de9581aee27e5a9b2645db72de')	# merge tree
+		B = self.rorepo.tree('f606937a7a21237c866efafcad33675e6539c103')	# base tree
+		B_old = self.rorepo.tree('1f66cfbbce58b4b552b041707a12d437cc5f400a')	# old base tree
+		
+		# two very different trees
+		entries = traverse_trees_recursive(odb, [B_old.sha, H.sha], '')
+		self._assert_entries(entries, 2)
+		
+		oentries = traverse_trees_recursive(odb, [H.sha, B_old.sha], '')
+		assert len(oentries) == len(entries)
+		self._assert_entries(oentries, 2)
+		
+		# single tree
+		is_no_tree = lambda i, d: i.type != 'tree'
+		entries = traverse_trees_recursive(odb, [B.sha], '')
+		assert len(entries) == len(list(B.traverse(predicate=is_no_tree)))
+		self._assert_entries(entries, 1)
+		
+		# two trees
+		entries = traverse_trees_recursive(odb, [B.sha, H.sha], '')
+		self._assert_entries(entries, 2)
+		
+		# tree trees
+		entries = traverse_trees_recursive(odb, [B.sha, H.sha, M.sha], '')
+		self._assert_entries(entries, 3)
+		
+	def test_tree_traversal_single(self):
+		max_count = 50
+		count = 0
+		odb = self.rorepo.odb
+		for commit in self.rorepo.commit("29eb123beb1c55e5db4aa652d843adccbd09ae18").traverse():
+			if count >= max_count:
+				break
+			count += 1
+			entries = traverse_tree_recursive(odb, commit.tree.sha, '')
+			assert entries
+		# END for each commit
diff --git a/test/git/test_index.py b/test/git/test_index.py
index d0063e89..ae754430 100644
--- a/test/git/test_index.py
+++ b/test/git/test_index.py
@@ -580,7 +580,7 @@ class TestIndex(TestBase):
 		
 		# write all trees and compare them
 		# its important to have a few submodules in there too
-		max_count = 100
+		max_count = 25
 		count = 0
 		for commit in rw_repo.head.commit.traverse():
 			if count >= max_count:
@@ -593,3 +593,7 @@ class TestIndex(TestBase):
 			assert index.write_tree() == orig_tree
 		# END for each commit 
 		
+	def test_index_new(self):
+		self.fail("todo index new")
+		
+		
diff --git a/test/git/test_tree.py b/test/git/test_tree.py
index d983cb2f..a443bd97 100644
--- a/test/git/test_tree.py
+++ b/test/git/test_tree.py
@@ -7,6 +7,10 @@
 import os
 from test.testlib import *
 from git import *
+from git.objects.fun import (
+								traverse_tree_recursive,
+								traverse_trees_recursive
+							)
 from cStringIO import StringIO
 
 class TestTree(TestBase):
@@ -136,3 +140,4 @@ class TestTree(TestBase):
 	def test_repr(self):
 		tree = Tree(self.rorepo, 'abc')
 		assert_equal('<git.Tree "abc">', repr(tree))
+
-- 
cgit v1.2.3


From c0ef65b43688b1a4615a1e7332f6215f9a8abb19 Mon Sep 17 00:00:00 2001
From: Sebastian Thiel <byronimo@gmail.com>
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 +++++++++++++++++++++++++++++++++++++++++++++++-----
 test/git/test_fun.py | 64 +++++++++++++++++++++++++++++++++-----
 2 files changed, 135 insertions(+), 15 deletions(-)

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 <<CE_STAGESHIFT, tree_entry[2])
+	return BaseIndexEntry((tree_entry[1], tree_entry[0], stage <<CE_STAGESHIFT, tree_entry[2]))
 	
 def aggressive_tree_merge(odb, tree_shas):
 	"""
@@ -204,13 +206,81 @@ def aggressive_tree_merge(odb, tree_shas):
 		trees. All valid entries are on stage 0, whereas the conflicting ones are left 
 		on stage 1, 2 or 3, whereas stage 1 corresponds to the common ancestor tree, 
 		2 to our tree and 3 to 'their' tree.
-	:param tree_shas: 1, 2 or 3 trees as identified by their shas"""
+	:param tree_shas: 1, 2 or 3 trees as identified by their shas
+		If 1 or two, the entries will effectively correspond to the last given tree
+		If 3 are given, a 3 way merge is performed"""
 	out = list()
 	out_append = out.append
-	if len(tree_shas) == 1:
-		for entry in traverse_tree_recursive(odb, tree_shas[0]):
+	
+	# one and two way is the same for us, as we don't have to handle an existing
+	# index, instrea
+	if len(tree_shas) in (1,2):
+		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 
+					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
+				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
+			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
diff --git a/test/git/test_fun.py b/test/git/test_fun.py
index ccf15c77..4ddc1910 100644
--- a/test/git/test_fun.py
+++ b/test/git/test_fun.py
@@ -8,17 +8,67 @@ from git.index.fun import (
 							aggressive_tree_merge
 							)
 
+from git.index import IndexFile
+from stat import (
+					S_IFDIR, 
+					S_IFREG,
+					S_IFLNK
+				)
+
 class TestFun(TestBase):
 	
+	def _assert_index_entries(self, entries, trees):
+		index = IndexFile.from_tree(self.rorepo, *trees)
+		assert entries
+		assert len(index.entries) == len(entries)
+		for entry in entries:
+			assert (entry.path, entry.stage) in index.entries
+		# END assert entry matches fully
+	
 	def test_aggressive_tree_merge(self):
 		# head tree with additions, removals and modification compared to its predecessor
+		odb = self.rorepo.odb
 		HC = self.rorepo.commit("6c1faef799095f3990e9970bc2cb10aa0221cf9c") 
 		H = HC.tree
 		B = HC.parents[0].tree
 		
-		# test new index from single tree
+		# entries from single tree
+		trees = [H.sha]
+		self._assert_index_entries(aggressive_tree_merge(odb, trees), trees)
+		
+		# from multiple trees
+		trees = [B.sha, H.sha]
+		self._assert_index_entries(aggressive_tree_merge(odb, trees), trees)
+		
+		# three way, no conflict
+		tree = self.rorepo.tree
+		B = tree("35a09c0534e89b2d43ec4101a5fb54576b577905")
+		H = tree("4fe5cfa0e063a8d51a1eb6f014e2aaa994e5e7d4")
+		M = tree("1f2b19de3301e76ab3a6187a49c9c93ff78bafbd")
+		trees = [B.sha, H.sha, M.sha]
+		self._assert_index_entries(aggressive_tree_merge(odb, trees), trees)
+		
+		# three-way, conflict in at least one file, both modified
+		B = tree("a7a4388eeaa4b6b94192dce67257a34c4a6cbd26")
+		H = tree("f9cec00938d9059882bb8eabdaf2f775943e00e5")
+		M = tree("44a601a068f4f543f73fd9c49e264c931b1e1652")
+		trees = [B.sha, H.sha, M.sha]
+		self._assert_index_entries(aggressive_tree_merge(odb, trees), trees)
+
+	def make_tree(odb, entries):
+		"""create a tree from the given tree entries and safe it to the database"""
+		
+	
+	@with_rw_repo('0.1.6')
+	def test_three_way_merge(self, rwrepo):
+		def mkfile(name, sha, executable=0):
+			return (sha, S_IFREG | 644 | executable*0111, name)
+		def mkcommit(name, sha):
+			return (sha, S_IFDIR | S_IFLNK, name)
+		odb = rwrepo.odb
+		
 	
-	def _assert_entries(self, entries, num_trees):
+	def _assert_tree_entries(self, entries, num_trees):
 		assert len(entries[0]) == num_trees
 		for entry in entries:
 			paths = set(e[2] for e in entry if e)
@@ -37,25 +87,25 @@ class TestFun(TestBase):
 		
 		# two very different trees
 		entries = traverse_trees_recursive(odb, [B_old.sha, H.sha], '')
-		self._assert_entries(entries, 2)
+		self._assert_tree_entries(entries, 2)
 		
 		oentries = traverse_trees_recursive(odb, [H.sha, B_old.sha], '')
 		assert len(oentries) == len(entries)
-		self._assert_entries(oentries, 2)
+		self._assert_tree_entries(oentries, 2)
 		
 		# single tree
 		is_no_tree = lambda i, d: i.type != 'tree'
 		entries = traverse_trees_recursive(odb, [B.sha], '')
 		assert len(entries) == len(list(B.traverse(predicate=is_no_tree)))
-		self._assert_entries(entries, 1)
+		self._assert_tree_entries(entries, 1)
 		
 		# two trees
 		entries = traverse_trees_recursive(odb, [B.sha, H.sha], '')
-		self._assert_entries(entries, 2)
+		self._assert_tree_entries(entries, 2)
 		
 		# tree trees
 		entries = traverse_trees_recursive(odb, [B.sha, H.sha, M.sha], '')
-		self._assert_entries(entries, 3)
+		self._assert_tree_entries(entries, 3)
 		
 	def test_tree_traversal_single(self):
 		max_count = 50
-- 
cgit v1.2.3


From aea0243840a46021e6f77c759c960a06151d91c9 Mon Sep 17 00:00:00 2001
From: Sebastian Thiel <byronimo@gmail.com>
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 ++
 lib/git/repo.py      |   2 +-
 test/git/test_fun.py | 111 ++++++++++++++++++++++++++++++++++++++++++--
 4 files changed, 175 insertions(+), 70 deletions(-)

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):
diff --git a/lib/git/repo.py b/lib/git/repo.py
index f97126ea..79275106 100644
--- a/lib/git/repo.py
+++ b/lib/git/repo.py
@@ -742,7 +742,7 @@ class Repo(object):
 		# we at least give a proper error instead of letting git fail
 		prev_cwd = None
 		prev_path = None
-		odbt = kwargs.pop('odbt', GitCmdObjectDB)
+		odbt = kwargs.pop('odbt', type(self.odb))
 		if os.name == 'nt':
 			if '~' in path:
 				raise OSError("Git cannot handle the ~ character in path %r correctly" % path)
diff --git a/test/git/test_fun.py b/test/git/test_fun.py
index 4ddc1910..ce610014 100644
--- a/test/git/test_fun.py
+++ b/test/git/test_fun.py
@@ -1,20 +1,26 @@
 from test.testlib import *
 from git.objects.fun import (
 								traverse_tree_recursive,
-								traverse_trees_recursive
+								traverse_trees_recursive, 
+								tree_to_stream
 							)
 
 from git.index.fun import (
 							aggressive_tree_merge
 							)
 
-from git.index import IndexFile
+from gitdb.base import IStream
+from gitdb.typ import str_tree_type
+
 from stat import (
 					S_IFDIR, 
 					S_IFREG,
 					S_IFLNK
 				)
 
+from git.index import IndexFile
+from cStringIO import StringIO
+
 class TestFun(TestBase):
 	
 	def _assert_index_entries(self, entries, trees):
@@ -55,18 +61,113 @@ class TestFun(TestBase):
 		trees = [B.sha, H.sha, M.sha]
 		self._assert_index_entries(aggressive_tree_merge(odb, trees), trees)
 
-	def make_tree(odb, entries):
+	def mktree(self, odb, entries):
 		"""create a tree from the given tree entries and safe it to the database"""
-		
+		sio = StringIO()
+		tree_to_stream(entries, sio.write)
+		sio.seek(0)
+		istream = odb.store(IStream(str_tree_type, len(sio.getvalue()), sio))
+		return istream.sha
 	
 	@with_rw_repo('0.1.6')
 	def test_three_way_merge(self, rwrepo):
 		def mkfile(name, sha, executable=0):
-			return (sha, S_IFREG | 644 | executable*0111, name)
+			return (sha, S_IFREG | 0644 | executable*0111, name)
 		def mkcommit(name, sha):
 			return (sha, S_IFDIR | S_IFLNK, name)
+		def assert_entries(entries, num_entries, has_conflict=False):
+			assert len(entries) == num_entries
+			assert has_conflict == (len([e for e in entries if e.stage != 0]) > 0)
+		mktree = self.mktree
+			
+		shaa = "\1"*20
+		shab = "\2"*20
+		shac = "\3"*20
+		
 		odb = rwrepo.odb
 		
+		# base tree
+		bfn = 'basefile'
+		fbase = mkfile(bfn, shaa)
+		tb = mktree(odb, [fbase])
+		
+		# non-conflicting new files, same data
+		fa = mkfile('1', shab)
+		th = mktree(odb, [fbase, fa])
+		fb = mkfile('2', shac)
+		tm = mktree(odb, [fbase, fb])
+		
+		# two new files, same base file
+		trees = [tb, th, tm]
+		assert_entries(aggressive_tree_merge(odb, trees), 3)
+		
+		# both delete same file, add own one
+		fa = mkfile('1', shab)
+		th = mktree(odb, [fa])
+		fb = mkfile('2', shac)
+		tm = mktree(odb, [fb])
+		
+		# two new files
+		trees = [tb, th, tm]
+		assert_entries(aggressive_tree_merge(odb, trees), 2)
+		
+		# modify same base file, differently
+		fa = mkfile(bfn, shab)
+		th = mktree(odb, [fa])
+		fb = mkfile(bfn, shac)
+		tm = mktree(odb, [fb])
+		
+		# conflict, 3 versions on 3 stages
+		trees = [tb, th, tm]
+		assert_entries(aggressive_tree_merge(odb, trees), 3, True)
+		
+		
+		# change mode on same base file, by making one a commit, the other executable
+		# no content change ( this is totally unlikely to happen in the real world )
+		fa = mkcommit(bfn, shaa)
+		th = mktree(odb, [fa])
+		fb = mkfile(bfn, shaa, executable=1)
+		tm = mktree(odb, [fb])
+		
+		# conflict, 3 versions on 3 stages, because of different mode
+		trees = [tb, th, tm]
+		assert_entries(aggressive_tree_merge(odb, trees), 3, True)
+		
+		for is_them in range(2):
+			# only we/they change contents
+			fa = mkfile(bfn, shab)
+			th = mktree(odb, [fa])
+			
+			trees = [tb, th, tb]
+			if is_them:
+				trees = [tb, tb, th]
+			entries = aggressive_tree_merge(odb, trees)
+			assert len(entries) == 1 and entries[0].binsha == shab
+			
+			# only we/they change the mode
+			fa = mkcommit(bfn, shaa)
+			th = mktree(odb, [fa])
+			
+			trees = [tb, th, tb]
+			if is_them:
+				trees = [tb, tb, th]
+			entries = aggressive_tree_merge(odb, trees)
+			assert len(entries) == 1 and entries[0].binsha == shaa and entries[0].mode == fa[1]
+			
+			# one side deletes, the other changes = conflict
+			fa = mkfile(bfn, shab)
+			th = mktree(odb, [fa])
+			tm = mktree(odb, [])
+			trees = [tb, th, tm]
+			if is_them:
+				trees = [tb, tm, th]
+			# as one is deleted, there are only 2 entries
+			assert_entries(aggressive_tree_merge(odb, trees), 2, True)
+		# END handle ours, theirs
+		
+		
+		
+		
 	
 	def _assert_tree_entries(self, entries, num_trees):
 		assert len(entries[0]) == num_trees
-- 
cgit v1.2.3


From 1e2265a23ecec4e4d9ad60d788462e7f124f1bb7 Mon Sep 17 00:00:00 2001
From: Sebastian Thiel <byronimo@gmail.com>
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 ++++++-----
 lib/git/objects/fun.py |  2 +-
 test/git/test_fun.py   |  9 ++++-----
 test/git/test_index.py |  9 ++++++++-
 5 files changed, 31 insertions(+), 17 deletions(-)

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):
diff --git a/lib/git/objects/fun.py b/lib/git/objects/fun.py
index d21a7dad..c2e7358f 100644
--- a/lib/git/objects/fun.py
+++ b/lib/git/objects/fun.py
@@ -148,7 +148,7 @@ def traverse_trees_recursive(odb, tree_shas, path_prefix):
 			
 			# if we are a directory, enter recursion
 			if is_dir:
-				out.extend(traverse_trees_recursive(odb, [ei[0] for ei in entries if ei], path_prefix+name+'/'))
+				out.extend(traverse_trees_recursive(odb, [((ei and ei[0]) or None) for ei in entries], path_prefix+name+'/'))
 			else:
 				out_append(tuple(_to_full_path(e, path_prefix) for e in entries))
 			# END handle recursion
diff --git a/test/git/test_fun.py b/test/git/test_fun.py
index ce610014..b2b94415 100644
--- a/test/git/test_fun.py
+++ b/test/git/test_fun.py
@@ -60,6 +60,9 @@ class TestFun(TestBase):
 		M = tree("44a601a068f4f543f73fd9c49e264c931b1e1652")
 		trees = [B.sha, H.sha, M.sha]
 		self._assert_index_entries(aggressive_tree_merge(odb, trees), trees)
+		
+		# too many trees
+		self.failUnlessRaises(ValueError, aggressive_tree_merge, odb, trees*2)
 
 	def mktree(self, odb, entries):
 		"""create a tree from the given tree entries and safe it to the database"""
@@ -164,14 +167,10 @@ class TestFun(TestBase):
 			# as one is deleted, there are only 2 entries
 			assert_entries(aggressive_tree_merge(odb, trees), 2, True)
 		# END handle ours, theirs
-		
-		
-		
-		
 	
 	def _assert_tree_entries(self, entries, num_trees):
-		assert len(entries[0]) == num_trees
 		for entry in entries:
+			assert len(entry) == num_trees
 			paths = set(e[2] for e in entry if e)
 			
 			# only one path per set of entries
diff --git a/test/git/test_index.py b/test/git/test_index.py
index ae754430..35580135 100644
--- a/test/git/test_index.py
+++ b/test/git/test_index.py
@@ -594,6 +594,13 @@ class TestIndex(TestBase):
 		# END for each commit 
 		
 	def test_index_new(self):
-		self.fail("todo index new")
+		B = self.rorepo.tree("6d9b1f4f9fa8c9f030e3207e7deacc5d5f8bba4e")
+		H = self.rorepo.tree("25dca42bac17d511b7e2ebdd9d1d679e7626db5f")
+		M = self.rorepo.tree("e746f96bcc29238b79118123028ca170adc4ff0f")
+		
+		for args in ((B,), (B,H), (B,H,M)):
+			index = IndexFile.new(self.rorepo, *args)
+			assert isinstance(index, IndexFile)
+		# END for each arg tuple
 		
 		
-- 
cgit v1.2.3