Implemented simple tree merging and a simple test, more elaborate testing is in progress

Byron · Byron · commit c0ef65b43688 · 2010-06-23T00:28:36.000+02:00
diff --git a/lib/git/index/fun.py b/lib/git/index/fun.py
@@ -5,11 +5,13 @@
 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,21 +198,89 @@ 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):
 	"""
 	: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"""
+	: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
@@ -8,17 +8,67 @@
 							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 @@ def test_tree_traversal(self):
 		
 		# 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
