From 43f91266a493c4888b4ff2a7997ccc4a381e7238 Mon Sep 17 00:00:00 2001
From: Linus Torvalds <torvalds@ppc970.osdl.org>
Date: Sat, 16 Apr 2005 09:11:49 -0700
Subject: [PATCH] Make 'read-tree' do a few more of the trivial merge cases.

This cuts down the work for the "real merge" to stuff where
people might actually disagree on the algorithm. The trivial
cases would seem to be totally independent of any policy.
---
 read-tree.c | 70 ++++++++++++++++++++++++++++++++++++++++++++++---------------
 1 file changed, 53 insertions(+), 17 deletions(-)

diff --git a/read-tree.c b/read-tree.c
index 59e6950a..c4ca86f4 100644
--- a/read-tree.c
+++ b/read-tree.c
@@ -73,26 +73,61 @@ static void remove_lock_file(void)
 		unlink(".git/index.lock");
 }
 
+static int same(struct cache_entry *a, struct cache_entry *b)
+{
+	return a->ce_mode == b->ce_mode && 
+		!memcmp(a->sha1, b->sha1, 20);
+}
+
+
 /*
- * This removes all identical entries and collapses them to state 0.
+ * This removes all trivial merges that don't change the tree
+ * and collapses them to state 0.
  *
- * _Any_ other merge (even a trivial one, like both ) is left to user policy.
- * That includes "both created the same file", and "both removed the same
- * file" - which are trivial, but the user might still want to _note_ it.
+ * _Any_ other merge is left to user policy.  That includes "both
+ * created the same file", and "both removed the same file" - which are
+ * trivial, but the user might still want to _note_ it. 
  */
-static int same_entry(struct cache_entry *a,
-			struct cache_entry *b,
-			struct cache_entry *c)
+static struct cache_entry *merge_entries(struct cache_entry *a,
+					 struct cache_entry *b,
+					 struct cache_entry *c)
 {
 	int len = ce_namelen(a);
-	return	a->ce_mode == b->ce_mode &&
-		a->ce_mode == c->ce_mode &&
-		ce_namelen(b) == len &&
-		ce_namelen(c) == len &&
-		!memcmp(a->name, b->name, len) &&
-		!memcmp(a->name, c->name, len) &&
-		!memcmp(a->sha1, b->sha1, 20) &&
-		!memcmp(a->sha1, c->sha1, 20);
+
+	/*
+	 * Are they all the same filename? We won't do
+	 * any name merging
+	 */
+	if (ce_namelen(b) != len ||
+	    ce_namelen(c) != len ||
+	    memcmp(a->name, b->name, len) ||
+	    memcmp(a->name, c->name, len))
+		return NULL;
+
+	/*
+	 * Ok, all three entries describe the same
+	 * filename, but maybe the contents or file
+	 * mode have changed?
+	 *
+	 * The trivial cases end up being the ones where two
+	 * out of three files are the same:
+	 *  - both destinations the same, trivially take either
+	 *  - one of the destination versions hasn't changed,
+	 *    take the other.
+	 *
+	 * The "all entries exactly the same" case falls out as
+	 * a special case of any of the "two same" cases.
+	 *
+	 * Here "a" is "original", and "b" and "c" are the two
+	 * trees we are merging.
+	 */
+	if (same(b,c))
+		return c;
+	if (same(a,b))
+		return c;
+	if (same(a,c))
+		return b;
+	return NULL;
 }
 
 static void trivially_merge_cache(struct cache_entry **src, int nr)
@@ -100,10 +135,11 @@ static void trivially_merge_cache(struct cache_entry **src, int nr)
 	struct cache_entry **dst = src;
 
 	while (nr) {
-		struct cache_entry *ce;
+		struct cache_entry *ce, *result;
 
 		ce = src[0];
-		if (nr > 2 && same_entry(ce, src[1], src[2])) {
+		if (nr > 2 && (result = merge_entries(ce, src[1], src[2])) != NULL) {
+			ce = result;
 			ce->ce_flags &= ~htons(CE_STAGEMASK);
 			src += 2;
 			nr -= 2;
-- 
2.11.0