From cd3c095caa6f61b4a2952e7ea167938c5b69bc3d Mon Sep 17 00:00:00 2001
From: Junio C Hamano <gitster@pobox.com>
Date: Sun, 20 Sep 2009 11:10:14 -0700
Subject: tests: move convenience regexp to match object names to test-lib.sh

Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff --git a/t/diff-lib.sh b/t/diff-lib.sh
index 4bddeb5..75a35fc 100644
--- a/t/diff-lib.sh
+++ b/t/diff-lib.sh
@@ -1,7 +1,5 @@
 :
 
-_x40='[0-9a-f][0-9a-f][0-9a-f][0-9a-f][0-9a-f]'
-_x40="$_x40$_x40$_x40$_x40$_x40$_x40$_x40$_x40"
 sanitize_diff_raw='/^:/s/ '"$_x40"' '"$_x40"' \([A-Z]\)[0-9]*	/ X X \1#	/'
 compare_diff_raw () {
     # When heuristics are improved, the score numbers would change.
diff --git a/t/t1000-read-tree-m-3way.sh b/t/t1000-read-tree-m-3way.sh
index 22ba7a5..4f17172 100755
--- a/t/t1000-read-tree-m-3way.sh
+++ b/t/t1000-read-tree-m-3way.sh
@@ -126,9 +126,6 @@ cat >expected <<\EOF
 100644 X 0	Z/NN
 EOF
 
-_x40='[0-9a-f][0-9a-f][0-9a-f][0-9a-f][0-9a-f]'
-_x40="$_x40$_x40$_x40$_x40$_x40$_x40$_x40$_x40"
-
 check_result () {
     git ls-files --stage | sed -e 's/ '"$_x40"' / X /' >current &&
     test_cmp expected current
diff --git a/t/t1001-read-tree-m-2way.sh b/t/t1001-read-tree-m-2way.sh
index c2d408b..6327d20 100755
--- a/t/t1001-read-tree-m-2way.sh
+++ b/t/t1001-read-tree-m-2way.sh
@@ -26,8 +26,6 @@ read_tree_twoway () {
     git read-tree -m "$1" "$2" && git ls-files --stage
 }
 
-_x40='[0-9a-f][0-9a-f][0-9a-f][0-9a-f][0-9a-f]'
-_x40="$_x40$_x40$_x40$_x40$_x40$_x40$_x40$_x40"
 compare_change () {
 	sed -n >current \
 	    -e '/^--- /d; /^+++ /d; /^@@ /d;' \
diff --git a/t/t1002-read-tree-m-u-2way.sh b/t/t1002-read-tree-m-u-2way.sh
index 5e40cec..0241329 100755
--- a/t/t1002-read-tree-m-u-2way.sh
+++ b/t/t1002-read-tree-m-u-2way.sh
@@ -10,8 +10,6 @@ This is identical to t1001, but uses -u to update the work tree as well.
 '
 . ./test-lib.sh
 
-_x40='[0-9a-f][0-9a-f][0-9a-f][0-9a-f][0-9a-f]'
-_x40="$_x40$_x40$_x40$_x40$_x40$_x40$_x40$_x40"
 compare_change () {
 	sed >current \
 	    -e '1{/^diff --git /d;}' \
diff --git a/t/t3100-ls-tree-restrict.sh b/t/t3100-ls-tree-restrict.sh
index ee60d03..eee0d34 100755
--- a/t/t3100-ls-tree-restrict.sh
+++ b/t/t3100-ls-tree-restrict.sh
@@ -43,8 +43,6 @@ test_expect_success \
      tree=`git write-tree` &&
      echo $tree'
 
-_x40='[0-9a-f][0-9a-f][0-9a-f][0-9a-f][0-9a-f]'
-_x40="$_x40$_x40$_x40$_x40$_x40$_x40$_x40$_x40"
 test_output () {
     sed -e "s/ $_x40	/ X	/" <current >check
     test_cmp expected check
diff --git a/t/t3101-ls-tree-dirname.sh b/t/t3101-ls-tree-dirname.sh
index 8be9fb4..06654c6 100755
--- a/t/t3101-ls-tree-dirname.sh
+++ b/t/t3101-ls-tree-dirname.sh
@@ -39,8 +39,6 @@ test_expect_success \
      tree=`git write-tree` &&
      echo $tree'
 
-_x05='[0-9a-f][0-9a-f][0-9a-f][0-9a-f][0-9a-f]'
-_x40="$_x05$_x05$_x05$_x05$_x05$_x05$_x05$_x05"
 test_output () {
     sed -e "s/ $_x40	/ X	/" <current >check
     test_cmp expected check
diff --git a/t/t4006-diff-mode.sh b/t/t4006-diff-mode.sh
index 8c1b81e..ff8c2f7 100755
--- a/t/t4006-diff-mode.sh
+++ b/t/t4006-diff-mode.sh
@@ -20,8 +20,6 @@ test_expect_success \
     'test_chmod +x rezrov &&
      git diff-index $tree >current'
 
-_x40='[0-9a-f][0-9a-f][0-9a-f][0-9a-f][0-9a-f]'
-_x40="$_x40$_x40$_x40$_x40$_x40$_x40$_x40$_x40"
 sed -e 's/\(:100644 100755\) \('"$_x40"'\) \2 /\1 X X /' <current >check
 echo ":100644 100755 X X M	rezrov" >expected
 
diff --git a/t/t6012-rev-list-simplify.sh b/t/t6012-rev-list-simplify.sh
index 510bb96..af34a1e 100755
--- a/t/t6012-rev-list-simplify.sh
+++ b/t/t6012-rev-list-simplify.sh
@@ -8,9 +8,6 @@ note () {
 	git tag "$1"
 }
 
-_x40='[0-9a-f][0-9a-f][0-9a-f][0-9a-f][0-9a-f]'
-_x40="$_x40$_x40$_x40$_x40$_x40$_x40$_x40$_x40"
-
 unnote () {
 	git name-rev --tags --stdin | sed -e "s|$_x40 (tags/\([^)]*\)) |\1 |g"
 }
diff --git a/t/test-lib.sh b/t/test-lib.sh
index ec3336a..05efe1f 100644
--- a/t/test-lib.sh
+++ b/t/test-lib.sh
@@ -74,6 +74,12 @@ case $(echo $GIT_TRACE |tr "[A-Z]" "[a-z]") in
 		;;
 esac
 
+# Convenience
+#
+# A regexp to match 5 and 40 hexdigits
+_x05='[0-9a-f][0-9a-f][0-9a-f][0-9a-f][0-9a-f]'
+_x40="$_x05$_x05$_x05$_x05$_x05$_x05$_x05$_x05"
+
 # Each test should start with something like this, after copyright notices:
 #
 # test_description='Description of this test...
-- 
cgit v0.10.2-6-g49f6


From 934f930b3144d03cacd16bc5117ef2afe3b1d04d Mon Sep 17 00:00:00 2001
From: Junio C Hamano <gitster@pobox.com>
Date: Sun, 20 Sep 2009 11:49:56 -0700
Subject: more D/F conflict tests

Before starting to muck with this code, let's expose the current
breakages that we intend to fix.

Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff --git a/t/t1012-read-tree-df.sh b/t/t1012-read-tree-df.sh
new file mode 100755
index 0000000..a961e2a
--- /dev/null
+++ b/t/t1012-read-tree-df.sh
@@ -0,0 +1,102 @@
+#!/bin/sh
+
+test_description='read-tree D/F conflict corner cases'
+
+. ./test-lib.sh
+
+maketree () {
+	(
+		rm -f .git/index .git/index.lock &&
+		git clean -d -f -f -q -x &&
+		name="$1" &&
+		shift &&
+		for it
+		do
+			path=$(expr "$it" : '\([^:]*\)') &&
+			mkdir -p $(dirname "$path") &&
+			echo "$it" >"$path" &&
+			git update-index --add "$path" || exit
+		done &&
+		git tag "$name" $(git write-tree)
+	)
+}
+
+settree () {
+	rm -f .git/index .git/index.lock &&
+	git clean -d -f -f -q -x &&
+	git read-tree "$1" &&
+	git checkout-index -f -q -u -a &&
+	git update-index --refresh
+}
+
+checkindex () {
+	git ls-files -s |
+	sed "s|^[0-7][0-7]* $_x40 \([0-3]\)	|\1 |" >current &&
+	cat >expect &&
+	test_cmp expect current
+}
+
+test_expect_success setup '
+	maketree O-000 a/b-2/c/d a/b/c/d a/x &&
+	maketree A-000 a/b-2/c/d a/b/c/d a/x &&
+	maketree A-001 a/b-2/c/d a/b/c/d a/b/c/e a/x &&
+	maketree B-000 a/b-2/c/d a/b     a/x &&
+
+	maketree O-010 t-0     t/1  t/2 t=3 &&
+	maketree A-010 t-0 t            t=3 &&
+	maketree B-010         t/1:     t=3: &&
+
+	maketree O-020 ds/dma/ioat.c ds/dma/ioat_dca.c &&
+	maketree A-020 ds/dma/ioat/Makefile ds/dma/ioat/registers.h &&
+	:
+'
+
+test_expect_failure '3-way (1)' '
+	settree A-000 &&
+	git read-tree -m -u O-000 A-000 B-000 &&
+	checkindex <<-EOF
+	3 a/b
+	0 a/b-2/c/d
+	1 a/b/c/d
+	2 a/b/c/d
+	0 a/x
+	EOF
+'
+
+test_expect_failure '3-way (2)' '
+	settree A-001 &&
+	git read-tree -m -u O-000 A-001 B-000 &&
+	checkindex <<-EOF
+	3 a/b
+	0 a/b-2/c/d
+	1 a/b/c/d
+	2 a/b/c/d
+	2 a/b/c/e
+	0 a/x
+	EOF
+'
+
+test_expect_success '3-way (3)' '
+	settree A-010 &&
+	git read-tree -m -u O-010 A-010 B-010 &&
+	checkindex <<-EOF
+	2 t
+	1 t-0
+	2 t-0
+	1 t/1
+	3 t/1
+	1 t/2
+	0 t=3
+	EOF
+'
+
+test_expect_success '2-way (1)' '
+	settree O-020 &&
+	git read-tree -m -u O-020 A-020 &&
+	checkindex <<-EOF
+	0 ds/dma/ioat/Makefile
+	0 ds/dma/ioat/registers.h
+	EOF
+'
+
+test_done
-- 
cgit v0.10.2-6-g49f6


From 1ee26571e97c64bccecfd26d1a1c1c631412a1b7 Mon Sep 17 00:00:00 2001
From: Junio C Hamano <gitster@pobox.com>
Date: Sat, 19 Sep 2009 14:07:14 -0700
Subject: traverse_trees(): handle D/F conflict case sanely

traverse_trees() is supposed to call its callback with all the matching
entries from the given trees.  The current algorithm keeps a pointer to
each of the tree being traversed, and feeds the entry with the earliest
name to the callback.

This breaks down if the trees being traversed looks like this:

    A    B
    t-1  t
    t-2  u
    t/a  v

When we are currently looking at an entry "t-1" in tree A, and tree B has
returned "t", feeding "t" from the B and not feeding anything from A, only
because "t-1" sorts later than "t", will miss an entry for a subtree "t"
behind the current entry in tree A.

This introduces extended_entry_extract() helper function that gives what
name is expected from the tree, and implements a mechanism to look-ahead
in the tree object using it, to make sure such a case is handled sanely.
Traversal in tree A in the above example will first return "t" to match
that of B, and then the next request for an entry to A then returns "t-1".

This roughly corresponds to what Linus's "prepare for one-entry lookahead"
wanted to do, but because this does implement look ahead, t6035 and one more
test in t1012 reveal that the approach would not work without adjusting the
side that walks the index in unpack_trees() as well.

Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff --git a/t/t1012-read-tree-df.sh b/t/t1012-read-tree-df.sh
index a961e2a..f1e650a 100755
--- a/t/t1012-read-tree-df.sh
+++ b/t/t1012-read-tree-df.sh
@@ -76,7 +76,7 @@ test_expect_failure '3-way (2)' '
 	EOF
 '
 
-test_expect_success '3-way (3)' '
+test_expect_failure '3-way (3)' '
 	settree A-010 &&
 	git read-tree -m -u O-010 A-010 B-010 &&
 	checkindex <<-EOF
@@ -90,7 +90,7 @@ test_expect_success '3-way (3)' '
 	EOF
 '
 
-test_expect_success '2-way (1)' '
+test_expect_failure '2-way (1)' '
 	settree O-020 &&
 	git read-tree -m -u O-020 A-020 &&
 	checkindex <<-EOF
diff --git a/t/t6035-merge-dir-to-symlink.sh b/t/t6035-merge-dir-to-symlink.sh
index 5b96fb0..b9a280e 100755
--- a/t/t6035-merge-dir-to-symlink.sh
+++ b/t/t6035-merge-dir-to-symlink.sh
@@ -48,7 +48,7 @@ test_expect_success 'setup for merge test' '
 	git tag baseline
 '
 
-test_expect_success 'do not lose a/b-2/c/d in merge (resolve)' '
+test_expect_failure 'do not lose a/b-2/c/d in merge (resolve)' '
 	git reset --hard &&
 	git checkout baseline^0 &&
 	git merge -s resolve master &&
diff --git a/tree-walk.c b/tree-walk.c
index 02e2aed..08796c2 100644
--- a/tree-walk.c
+++ b/tree-walk.c
@@ -60,13 +60,6 @@ void *fill_tree_descriptor(struct tree_desc *desc, const unsigned char *sha1)
 	return buf;
 }
 
-static int entry_compare(struct name_entry *a, struct name_entry *b)
-{
-	return df_name_compare(
-			a->path, tree_entry_len(a->path, a->sha1), a->mode,
-			b->path, tree_entry_len(b->path, b->sha1), b->mode);
-}
-
 static void entry_clear(struct name_entry *a)
 {
 	memset(a, 0, sizeof(*a));
@@ -138,66 +131,264 @@ char *make_traverse_path(char *path, const struct traverse_info *info, const str
 	return path;
 }
 
+struct tree_desc_skip {
+	struct tree_desc_skip *prev;
+	const void *ptr;
+};
+
+struct tree_desc_x {
+	struct tree_desc d;
+	struct tree_desc_skip *skip;
+};
+
+static int name_compare(const char *a, int a_len,
+			const char *b, int b_len)
+{
+	int len = (a_len < b_len) ? a_len : b_len;
+	int cmp = memcmp(a, b, len);
+	if (cmp)
+		return cmp;
+	return (a_len - b_len);
+}
+
+static int check_entry_match(const char *a, int a_len, const char *b, int b_len)
+{
+	/*
+	 * The caller wants to pick *a* from a tree or nothing.
+	 * We are looking at *b* in a tree.
+	 *
+	 * (0) If a and b are the same name, we are trivially happy.
+	 *
+	 * There are three possibilities where *a* could be hiding
+	 * behind *b*.
+	 *
+	 * (1) *a* == "t",   *b* == "ab"  i.e. *b* sorts earlier than *a* no
+	 *                                matter what.
+	 * (2) *a* == "t",   *b* == "t-2" and "t" is a subtree in the tree;
+	 * (3) *a* == "t-2", *b* == "t"   and "t-2" is a blob in the tree.
+	 *
+	 * Otherwise we know *a* won't appear in the tree without
+	 * scanning further.
+	 */
+
+	int cmp = name_compare(a, a_len, b, b_len);
+
+	/* Most common case first -- reading sync'd trees */
+	if (!cmp)
+		return cmp;
+
+	if (0 < cmp) {
+		/* a comes after b; it does not matter if it is case (3)
+		if (b_len < a_len && !memcmp(a, b, b_len) && a[b_len] < '/')
+			return 1;
+		*/
+		return 1; /* keep looking */
+	}
+
+	/* b comes after a; are we looking at case (2)? */
+	if (a_len < b_len && !memcmp(a, b, a_len) && b[a_len] < '/')
+		return 1; /* keep looking */
+
+	return -1; /* a cannot appear in the tree */
+}
+
+/*
+ * From the extended tree_desc, extract the first name entry, while
+ * paying attention to the candidate "first" name.  Most importantly,
+ * when looking for an entry, if there are entries that sorts earlier
+ * in the tree object representation than that name, skip them and
+ * process the named entry first.  We will remember that we haven't
+ * processed the first entry yet, and in the later call skip the
+ * entry we processed early when update_extended_entry() is called.
+ *
+ * E.g. if the underlying tree object has these entries:
+ *
+ *    blob    "t-1"
+ *    blob    "t-2"
+ *    tree    "t"
+ *    blob    "t=1"
+ *
+ * and the "first" asks for "t", remember that we still need to
+ * process "t-1" and "t-2" but extract "t".  After processing the
+ * entry "t" from this call, the caller will let us know by calling
+ * update_extended_entry() that we can remember "t" has been processed
+ * already.
+ */
+
+static void extended_entry_extract(struct tree_desc_x *t,
+				   struct name_entry *a,
+				   const char *first,
+				   int first_len)
+{
+	const char *path;
+	int len;
+	struct tree_desc probe;
+	struct tree_desc_skip *skip;
+
+	/*
+	 * Extract the first entry from the tree_desc, but skip the
+	 * ones that we already returned in earlier rounds.
+	 */
+	while (1) {
+		if (!t->d.size) {
+			entry_clear(a);
+			break; /* not found */
+		}
+		entry_extract(&t->d, a);
+		for (skip = t->skip; skip; skip = skip->prev)
+			if (a->path == skip->ptr)
+				break; /* found */
+		if (!skip)
+			break;
+		/* We have processed this entry already. */
+		update_tree_entry(&t->d);
+	}
+
+	if (!first || !a->path)
+		return;
+
+	/*
+	 * The caller wants "first" from this tree, or nothing.
+	 */
+	path = a->path;
+	len = tree_entry_len(a->path, a->sha1);
+	switch (check_entry_match(first, first_len, path, len)) {
+	case -1:
+		entry_clear(a);
+	case 0:
+		return;
+	default:
+		break;
+	}
+
+	/*
+	 * We need to look-ahead -- we suspect that a subtree whose
+	 * name is "first" may be hiding behind the current entry "path".
+	 */
+	probe = t->d;
+	while (probe.size) {
+		entry_extract(&probe, a);
+		path = a->path;
+		len = tree_entry_len(a->path, a->sha1);
+		switch (check_entry_match(first, first_len, path, len)) {
+		case -1:
+			entry_clear(a);
+		case 0:
+			return;
+		default:
+			update_tree_entry(&probe);
+			break;
+		}
+		/* keep looking */
+	}
+	entry_clear(a);
+}
+
+static void update_extended_entry(struct tree_desc_x *t, struct name_entry *a)
+{
+	if (t->d.entry.path == a->path) {
+		update_tree_entry(&t->d);
+	} else {
+		/* we have returned this entry early */
+		struct tree_desc_skip *skip = xmalloc(sizeof(*skip));
+		skip->ptr = a->path;
+		skip->prev = t->skip;
+		t->skip = skip;
+	}
+}
+
+static void free_extended_entry(struct tree_desc_x *t)
+{
+	struct tree_desc_skip *p, *s;
+
+	for (s = t->skip; s; s = p) {
+		p = s->prev;
+		free(s);
+	}
+}
+
 int traverse_trees(int n, struct tree_desc *t, struct traverse_info *info)
 {
 	int ret = 0;
 	struct name_entry *entry = xmalloc(n*sizeof(*entry));
+	int i;
+	struct tree_desc_x *tx = xcalloc(n, sizeof(*tx));
+
+	for (i = 0; i < n; i++)
+		tx[i].d = t[i];
 
 	for (;;) {
-		unsigned long mask = 0;
-		unsigned long dirmask = 0;
-		int i, last;
+		unsigned long mask, dirmask;
+		const char *first = NULL;
+		int first_len = 0;
+		struct name_entry *e;
+		int len;
 
-		last = -1;
 		for (i = 0; i < n; i++) {
-			if (!t[i].size)
+			e = entry + i;
+			extended_entry_extract(tx + i, e, NULL, 0);
+		}
+
+		/*
+		 * A tree may have "t-2" at the current location even
+		 * though it may have "t" that is a subtree behind it,
+		 * and another tree may return "t".  We want to grab
+		 * all "t" from all trees to match in such a case.
+		 */
+		for (i = 0; i < n; i++) {
+			e = entry + i;
+			if (!e->path)
 				continue;
-			entry_extract(t+i, entry+i);
-			if (last >= 0) {
-				int cmp = entry_compare(entry+i, entry+last);
-
-				/*
-				 * Is the new name bigger than the old one?
-				 * Ignore it
-				 */
-				if (cmp > 0)
+			len = tree_entry_len(e->path, e->sha1);
+			if (!first) {
+				first = e->path;
+				first_len = len;
+				continue;
+			}
+			if (name_compare(e->path, len, first, first_len) < 0) {
+				first = e->path;
+				first_len = len;
+			}
+		}
+
+		if (first) {
+			for (i = 0; i < n; i++) {
+				e = entry + i;
+				extended_entry_extract(tx + i, e, first, first_len);
+				/* Cull the ones that are not the earliest */
+				if (!e->path)
 					continue;
-				/*
-				 * Is the new name smaller than the old one?
-				 * Ignore all old ones
-				 */
-				if (cmp < 0)
-					mask = 0;
+				len = tree_entry_len(e->path, e->sha1);
+				if (name_compare(e->path, len, first, first_len))
+					entry_clear(e);
 			}
+		}
+
+		/* Now we have in entry[i] the earliest name from the trees */
+		mask = 0;
+		dirmask = 0;
+		for (i = 0; i < n; i++) {
+			if (!entry[i].path)
+				continue;
 			mask |= 1ul << i;
 			if (S_ISDIR(entry[i].mode))
 				dirmask |= 1ul << i;
-			last = i;
 		}
 		if (!mask)
 			break;
-		dirmask &= mask;
-
-		/*
-		 * Clear all the unused name-entries.
-		 */
-		for (i = 0; i < n; i++) {
-			if (mask & (1ul << i))
-				continue;
-			entry_clear(entry + i);
-		}
 		ret = info->fn(n, mask, dirmask, entry, info);
 		if (ret < 0)
 			break;
-		if (ret)
-			mask &= ret;
+		mask &= ret;
 		ret = 0;
-		for (i = 0; i < n; i++) {
+		for (i = 0; i < n; i++)
 			if (mask & (1ul << i))
-				update_tree_entry(t + i);
-		}
+				update_extended_entry(tx + i, entry + i);
 	}
 	free(entry);
+	for (i = 0; i < n; i++)
+		free_extended_entry(tx + i);
+	free(tx);
 	return ret;
 }
 
-- 
cgit v0.10.2-6-g49f6


From cee2d6ae6379e7c76e602d55ccc1d4babc1979c0 Mon Sep 17 00:00:00 2001
From: Junio C Hamano <gitster@pobox.com>
Date: Sun, 11 Oct 2009 13:38:11 -0700
Subject: Aggressive three-way merge: fix D/F case

When the ancestor used to have a blob "P", your tree removed it, and the
tree you are merging with also removed it, the agressive three-way cleanly
merges to remove that blob.  If the other tree added a new blob "P/Q"
while removing "P", it should also merge cleanly to remove "P" and create
"P/Q" (since neither the ancestor nor your tree could have had it, so it
is a typical "created in one").

The "aggressive" rule is not new anymore.  Reword the stale comment.

Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff --git a/t/t6035-merge-dir-to-symlink.sh b/t/t6035-merge-dir-to-symlink.sh
index b9a280e..d1b2287 100755
--- a/t/t6035-merge-dir-to-symlink.sh
+++ b/t/t6035-merge-dir-to-symlink.sh
@@ -74,7 +74,7 @@ test_expect_success 'setup a merge where dir a/b-2 changed to symlink' '
 	git tag test2
 '
 
-test_expect_failure 'merge should not have conflicts (resolve)' '
+test_expect_success 'merge should not have conflicts (resolve)' '
 	git reset --hard &&
 	git checkout baseline^0 &&
 	git merge -s resolve test2 &&
diff --git a/unpack-trees.c b/unpack-trees.c
index dd5999c..7413ff0 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -767,7 +767,8 @@ int threeway_merge(struct cache_entry **stages, struct unpack_trees_options *o)
 		remote = NULL;
 	}
 
-	/* First, if there's a #16 situation, note that to prevent #13
+	/*
+	 * First, if there's a #16 situation, note that to prevent #13
 	 * and #14.
 	 */
 	if (!same(remote, head)) {
@@ -781,7 +782,8 @@ int threeway_merge(struct cache_entry **stages, struct unpack_trees_options *o)
 		}
 	}
 
-	/* We start with cases where the index is allowed to match
+	/*
+	 * We start with cases where the index is allowed to match
 	 * something other than the head: #14(ALT) and #2ALT, where it
 	 * is permitted to match the result instead.
 	 */
@@ -811,12 +813,13 @@ int threeway_merge(struct cache_entry **stages, struct unpack_trees_options *o)
 	if (!head && !remote && any_anc_missing)
 		return 0;
 
-	/* Under the new "aggressive" rule, we resolve mostly trivial
+	/*
+	 * Under the "aggressive" rule, we resolve mostly trivial
 	 * cases that we historically had git-merge-one-file resolve.
 	 */
 	if (o->aggressive) {
-		int head_deleted = !head && !df_conflict_head;
-		int remote_deleted = !remote && !df_conflict_remote;
+		int head_deleted = !head;
+		int remote_deleted = !remote;
 		struct cache_entry *ce = NULL;
 
 		if (index)
-- 
cgit v0.10.2-6-g49f6


From da165f470ede6540873d33cb8bc2ff8e13c60520 Mon Sep 17 00:00:00 2001
From: Junio C Hamano <gitster@pobox.com>
Date: Thu, 7 Jan 2010 14:59:54 -0800
Subject: unpack-trees.c: prepare for looking ahead in the index

This prepares but does not yet implement a look-ahead in the index entries
when traverse-trees.c decides to give us tree entries in an order that
does not match what is in the index.

A case where a look-ahead in the index is necessary happens when merging
branch B into branch A while the index matches the current branch A, using
a tree O as their common ancestor, and these three trees looks like this:

   O        A       B
   t                t
   t-i      t-i     t-i
   t-j      t-j
            t/1
            t/2

The traverse_trees() function gets "t", "t-i" and "t" from trees O, A and
B first, and notices that A may have a matching "t" behind "t-i" and "t-j"
(indeed it does), and tells A to give that entry instead.  After unpacking
blob "t" from tree B (as it hasn't changed since O in B and A removed it,
it will result in its removal), it descends into directory "t/".

The side that walked index in parallel to the tree traversal used to be
implemented with one pointer, o->pos, that points at the next index entry
to be processed.  When this happens, the pointer o->pos still points at
"t-i" that is the first entry.  We should be able to skip "t-i" and "t-j"
and locate "t/1" from the index while the recursive invocation of
traverse_trees() walks and match entries found there, and later come back
to process "t-i".

While that look-ahead is not implemented yet, this adds a flag bit,
CE_UNPACKED, to mark the entries in the index that has already been
processed.  o->pos pointer has been renamed to o->cache_bottom and it
points at the first entry that may still need to be processed.

Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff --git a/cache.h b/cache.h
index bf468e5..9a95963 100644
--- a/cache.h
+++ b/cache.h
@@ -178,6 +178,8 @@ struct cache_entry {
 #define CE_HASHED    (0x100000)
 #define CE_UNHASHED  (0x200000)
 
+#define CE_UNPACKED  (0x1000000)
+
 /*
  * Extended on-disk flags
  */
diff --git a/diff-lib.c b/diff-lib.c
index adf1c5f..f759917 100644
--- a/diff-lib.c
+++ b/diff-lib.c
@@ -359,21 +359,6 @@ static void do_oneway_diff(struct unpack_trees_options *o,
 	show_modified(revs, tree, idx, 1, cached, match_missing);
 }
 
-static inline void skip_same_name(struct cache_entry *ce, struct unpack_trees_options *o)
-{
-	int len = ce_namelen(ce);
-	const struct index_state *index = o->src_index;
-
-	while (o->pos < index->cache_nr) {
-		struct cache_entry *next = index->cache[o->pos];
-		if (len != ce_namelen(next))
-			break;
-		if (memcmp(ce->name, next->name, len))
-			break;
-		o->pos++;
-	}
-}
-
 /*
  * The unpack_trees() interface is designed for merging, so
  * the different source entries are designed primarily for
@@ -395,9 +380,6 @@ static int oneway_diff(struct cache_entry **src, struct unpack_trees_options *o)
 	struct cache_entry *tree = src[1];
 	struct rev_info *revs = o->unpack_data;
 
-	if (idx && ce_stage(idx))
-		skip_same_name(idx, o);
-
 	/*
 	 * Unpack-trees generates a DF/conflict entry if
 	 * there was a directory in the index and a tree
diff --git a/unpack-trees.c b/unpack-trees.c
index 7413ff0..685adb4 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -126,18 +126,109 @@ static inline int call_unpack_fn(struct cache_entry **src, struct unpack_trees_o
 	return ret;
 }
 
-static int unpack_index_entry(struct cache_entry *ce, struct unpack_trees_options *o)
+static void mark_ce_used(struct cache_entry *ce, struct unpack_trees_options *o)
+{
+	ce->ce_flags |= CE_UNPACKED;
+
+	if (o->cache_bottom < o->src_index->cache_nr &&
+	    o->src_index->cache[o->cache_bottom] == ce) {
+		int bottom = o->cache_bottom;
+		while (bottom < o->src_index->cache_nr &&
+		       o->src_index->cache[bottom]->ce_flags & CE_UNPACKED)
+			bottom++;
+		o->cache_bottom = bottom;
+	}
+}
+
+static void mark_all_ce_unused(struct index_state *index)
+{
+	int i;
+	for (i = 0; i < index->cache_nr; i++)
+		index->cache[i]->ce_flags &= ~CE_UNPACKED;
+}
+
+static int locate_in_src_index(struct cache_entry *ce,
+			       struct unpack_trees_options *o)
+{
+	struct index_state *index = o->src_index;
+	int len = ce_namelen(ce);
+	int pos = index_name_pos(index, ce->name, len);
+	if (pos < 0)
+		pos = -1 - pos;
+	return pos;
+}
+
+/*
+ * We call unpack_index_entry() with an unmerged cache entry
+ * only in diff-index, and it wants a single callback.  Skip
+ * the other unmerged entry with the same name.
+ */
+static void mark_ce_used_same_name(struct cache_entry *ce,
+				   struct unpack_trees_options *o)
+{
+	struct index_state *index = o->src_index;
+	int len = ce_namelen(ce);
+	int pos;
+
+	for (pos = locate_in_src_index(ce, o); pos < index->cache_nr; pos++) {
+		struct cache_entry *next = index->cache[pos];
+		if (len != ce_namelen(next) ||
+		    memcmp(ce->name, next->name, len))
+			break;
+		mark_ce_used(next, o);
+	}
+}
+
+static struct cache_entry *next_cache_entry(struct unpack_trees_options *o)
+{
+	const struct index_state *index = o->src_index;
+	int pos = o->cache_bottom;
+
+	while (pos < index->cache_nr) {
+		struct cache_entry *ce = index->cache[pos];
+		if (!(ce->ce_flags & CE_UNPACKED))
+			return ce;
+		pos++;
+	}
+	return NULL;
+}
+
+static void add_same_unmerged(struct cache_entry *ce,
+			      struct unpack_trees_options *o)
+{
+	struct index_state *index = o->src_index;
+	int len = ce_namelen(ce);
+	int pos = index_name_pos(index, ce->name, len);
+
+	if (0 <= pos)
+		die("programming error in a caller of mark_ce_used_same_name");
+	for (pos = -pos - 1; pos < index->cache_nr; pos++) {
+		struct cache_entry *next = index->cache[pos];
+		if (len != ce_namelen(next) ||
+		    memcmp(ce->name, next->name, len))
+			break;
+		add_entry(o, next, 0, 0);
+		mark_ce_used(next, o);
+	}
+}
+
+static int unpack_index_entry(struct cache_entry *ce,
+			      struct unpack_trees_options *o)
 {
 	struct cache_entry *src[5] = { ce, NULL, };
+	int ret;
 
-	o->pos++;
+	mark_ce_used(ce, o);
 	if (ce_stage(ce)) {
 		if (o->skip_unmerged) {
 			add_entry(o, ce, 0, 0);
 			return 0;
 		}
 	}
-	return call_unpack_fn(src, o);
+	ret = call_unpack_fn(src, o);
+	if (ce_stage(ce))
+		mark_ce_used_same_name(ce, o);
+	return ret;
 }
 
 static int traverse_trees_recursive(int n, unsigned long dirmask, unsigned long df_conflicts, struct name_entry *names, struct traverse_info *info)
@@ -212,6 +303,20 @@ static int compare_entry(const struct cache_entry *ce, const struct traverse_inf
 	return ce_namelen(ce) > traverse_path_len(info, n);
 }
 
+static int ce_in_traverse_path(const struct cache_entry *ce,
+			       const struct traverse_info *info)
+{
+	if (!info->prev)
+		return 1;
+	if (do_compare_entry(ce, info->prev, &info->name))
+		return 0;
+	/*
+	 * If ce (blob) is the same name as the path (which is a tree
+	 * we will be descending into), it won't be inside it.
+	 */
+	return (info->pathlen < ce_namelen(ce));
+}
+
 static struct cache_entry *create_ce_entry(const struct traverse_info *info, const struct name_entry *n, int stage)
 {
 	int len = traverse_path_len(info, n);
@@ -300,23 +405,27 @@ static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, str
 
 	/* Are we supposed to look at the index too? */
 	if (o->merge) {
-		while (o->pos < o->src_index->cache_nr) {
-			struct cache_entry *ce = o->src_index->cache[o->pos];
-			int cmp = compare_entry(ce, info, p);
+		while (1) {
+			struct cache_entry *ce = next_cache_entry(o);
+			int cmp;
+			if (!ce)
+				break;
+			cmp = compare_entry(ce, info, p);
 			if (cmp < 0) {
 				if (unpack_index_entry(ce, o) < 0)
 					return unpack_failed(o, NULL);
 				continue;
 			}
 			if (!cmp) {
-				o->pos++;
 				if (ce_stage(ce)) {
 					/*
-					 * If we skip unmerged index entries, we'll skip this
-					 * entry *and* the tree entries associated with it!
+					 * If we skip unmerged index
+					 * entries, we'll skip this
+					 * entry *and* the tree
+					 * entries associated with it!
 					 */
 					if (o->skip_unmerged) {
-						add_entry(o, ce, 0, 0);
+						add_same_unmerged(ce, o);
 						return mask;
 					}
 				}
@@ -329,6 +438,13 @@ static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, str
 	if (unpack_nondirectories(n, mask, dirmask, src, names, info) < 0)
 		return -1;
 
+	if (src[0]) {
+		if (ce_stage(src[0]))
+			mark_ce_used_same_name(src[0], o);
+		else
+			mark_ce_used(src[0], o);
+	}
+
 	/* Now handle any directories.. */
 	if (dirmask) {
 		unsigned long conflicts = mask & ~dirmask;
@@ -345,11 +461,13 @@ static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, str
 			matches = cache_tree_matches_traversal(o->src_index->cache_tree,
 							       names, info);
 			/*
-			 * Everything under the name matches.  Adjust o->pos to
-			 * skip the entire hierarchy.
+			 * Everything under the name matches; skip the
+			 * entire hierarchy.  diff_index_cached codepath
+			 * special cases D/F conflicts in such a way that
+			 * it does not do any look-ahead, so this is safe.
 			 */
 			if (matches) {
-				o->pos += matches;
+				o->cache_bottom += matches;
 				return mask;
 			}
 		}
@@ -382,11 +500,10 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options
 
 	memset(&o->result, 0, sizeof(o->result));
 	o->result.initialized = 1;
-	if (o->src_index) {
-		o->result.timestamp.sec = o->src_index->timestamp.sec;
-		o->result.timestamp.nsec = o->src_index->timestamp.nsec;
-	}
+	o->result.timestamp.sec = o->src_index->timestamp.sec;
+	o->result.timestamp.nsec = o->src_index->timestamp.nsec;
 	o->merge_size = len;
+	mark_all_ce_unused(o->src_index);
 
 	if (!dfc)
 		dfc = xcalloc(1, cache_entry_size(0));
@@ -400,18 +517,38 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options
 		info.fn = unpack_callback;
 		info.data = o;
 
+		if (o->prefix) {
+			/*
+			 * Unpack existing index entries that sort before the
+			 * prefix the tree is spliced into.  Note that o->merge
+			 * is always true in this case.
+			 */
+			while (1) {
+				struct cache_entry *ce = next_cache_entry(o);
+				if (!ce)
+					break;
+				if (ce_in_traverse_path(ce, &info))
+					break;
+				if (unpack_index_entry(ce, o) < 0)
+					goto return_failed;
+			}
+		}
+
 		if (traverse_trees(len, t, &info) < 0)
-			return unpack_failed(o, NULL);
+			goto return_failed;
 	}
 
 	/* Any left-over entries in the index? */
 	if (o->merge) {
-		while (o->pos < o->src_index->cache_nr) {
-			struct cache_entry *ce = o->src_index->cache[o->pos];
+		while (1) {
+			struct cache_entry *ce = next_cache_entry(o);
+			if (!ce)
+				break;
 			if (unpack_index_entry(ce, o) < 0)
-				return unpack_failed(o, NULL);
+				goto return_failed;
 		}
 	}
+	mark_all_ce_unused(o->src_index);
 
 	if (o->trivial_merges_only && o->nontrivial_merge)
 		return unpack_failed(o, "Merge requires file-level merging");
@@ -421,6 +558,10 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options
 	if (o->dst_index)
 		*o->dst_index = o->result;
 	return ret;
+
+return_failed:
+	mark_all_ce_unused(o->src_index);
+	return unpack_failed(o, NULL);
 }
 
 /* Here come the merge functions */
@@ -522,7 +663,9 @@ static int verify_clean_subdirectory(struct cache_entry *ce, const char *action,
 	 * in that directory.
 	 */
 	namelen = strlen(ce->name);
-	for (i = o->pos; i < o->src_index->cache_nr; i++) {
+	for (i = locate_in_src_index(ce, o);
+	     i < o->src_index->cache_nr;
+	     i++) {
 		struct cache_entry *ce2 = o->src_index->cache[i];
 		int len = ce_namelen(ce2);
 		if (len < namelen ||
@@ -530,12 +673,14 @@ static int verify_clean_subdirectory(struct cache_entry *ce, const char *action,
 		    ce2->name[namelen] != '/')
 			break;
 		/*
-		 * ce2->name is an entry in the subdirectory.
+		 * ce2->name is an entry in the subdirectory to be
+		 * removed.
 		 */
 		if (!ce_stage(ce2)) {
 			if (verify_uptodate(ce2, o))
 				return -1;
 			add_entry(o, ce2, CE_REMOVE, 0);
+			mark_ce_used(ce2, o);
 		}
 		cnt++;
 	}
@@ -591,7 +736,6 @@ static int verify_absent(struct cache_entry *ce, const char *action,
 		return 0;
 
 	if (!lstat(ce->name, &st)) {
-		int ret;
 		int dtype = ce_to_dtype(ce);
 		struct cache_entry *result;
 
@@ -619,28 +763,8 @@ static int verify_absent(struct cache_entry *ce, const char *action,
 			 * files that are in "foo/" we would lose
 			 * them.
 			 */
-			ret = verify_clean_subdirectory(ce, action, o);
-			if (ret < 0)
-				return ret;
-
-			/*
-			 * If this removed entries from the index,
-			 * what that means is:
-			 *
-			 * (1) the caller unpack_callback() saw path/foo
-			 * in the index, and it has not removed it because
-			 * it thinks it is handling 'path' as blob with
-			 * D/F conflict;
-			 * (2) we will return "ok, we placed a merged entry
-			 * in the index" which would cause o->pos to be
-			 * incremented by one;
-			 * (3) however, original o->pos now has 'path/foo'
-			 * marked with "to be removed".
-			 *
-			 * We need to increment it by the number of
-			 * deleted entries here.
-			 */
-			o->pos += ret;
+			if (verify_clean_subdirectory(ce, action, o) < 0)
+				return -1;
 			return 0;
 		}
 
diff --git a/unpack-trees.h b/unpack-trees.h
index d19df44..9a0733e 100644
--- a/unpack-trees.h
+++ b/unpack-trees.h
@@ -30,7 +30,7 @@ struct unpack_trees_options {
 		     diff_index_cached,
 		     gently;
 	const char *prefix;
-	int pos;
+	int cache_bottom;
 	struct dir_struct *dir;
 	merge_fn_t fn;
 	struct unpack_trees_error_msgs msgs;
-- 
cgit v0.10.2-6-g49f6


From 730f72840cc50c523fe4cdd796ea2d2fc4571a28 Mon Sep 17 00:00:00 2001
From: Junio C Hamano <gitster@pobox.com>
Date: Sun, 20 Sep 2009 00:03:39 -0700
Subject: unpack-trees.c: look ahead in the index

This makes the traversal of index be in sync with the tree traversal.
When unpack_callback() is fed a set of tree entries from trees, it
inspects the name of the entry and checks if the an index entry with
the same name could be hiding behind the current index entry, and

 (1) if the name appears in the index as a leaf node, it is also
     fed to the n_way_merge() callback function;

 (2) if the name is a directory in the index, i.e. there are entries in
     that are underneath it, then nothing is fed to the n_way_merge()
     callback function;

 (3) otherwise, if the name comes before the first eligible entry in the
     index, the index entry is first unpacked alone.

When traverse_trees_recursive() descends into a subdirectory, the
cache_bottom pointer is moved to walk index entries within that directory.

All of these are omitted for diff-index, which does not even want to be
fed an index entry and a tree entry with D/F conflicts.

This fixes 3-way read-tree and exposes a bug in other parts of the system
in t6035, test #5.  The test prepares these three trees:

 O = HEAD^
    100644 blob e69de29bb2d1d6434b8b29ae775ad8c2e48c5391    a/b-2/c/d
    100644 blob e69de29bb2d1d6434b8b29ae775ad8c2e48c5391    a/b/c/d
    100644 blob e69de29bb2d1d6434b8b29ae775ad8c2e48c5391    a/x

 A = HEAD
    100644 blob e69de29bb2d1d6434b8b29ae775ad8c2e48c5391    a/b-2/c/d
    100644 blob e69de29bb2d1d6434b8b29ae775ad8c2e48c5391    a/b/c/d
    100644 blob 587be6b4c3f93f93c489c0111bba5596147a26cb    a/x

 B = master
    120000 blob a36b77384451ea1de7bd340ffca868249626bc52    a/b
    100644 blob e69de29bb2d1d6434b8b29ae775ad8c2e48c5391    a/b-2/c/d
    100644 blob e69de29bb2d1d6434b8b29ae775ad8c2e48c5391    a/x

With a clean index that matches HEAD, running

    git read-tree -m -u --aggressive $O $A $B

now yields

    120000 a36b77384451ea1de7bd340ffca868249626bc52 3       a/b
    100644 e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 0       a/b-2/c/d
    100644 e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 1       a/b/c/d
    100644 e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 2       a/b/c/d
    100644 587be6b4c3f93f93c489c0111bba5596147a26cb 0       a/x

which is correct.  "master" created "a/b" symlink that did not exist,
and removed "a/b/c/d" while HEAD did not do touch either path.

Before this series, read-tree did not notice the situation and resolved
addition of "a/b" and removal of "a/b/c/d" independently.  If A = HEAD had
another path "a/b/c/e" added, this merge should conflict but instead it
silently resolved "a/b" and then immediately overwrote it to add
"a/b/c/e", which was quite bogus.

Tests in t1012 start to work with this.

Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff --git a/diff-lib.c b/diff-lib.c
index f759917..c9998f4 100644
--- a/diff-lib.c
+++ b/diff-lib.c
@@ -425,6 +425,7 @@ int run_diff_index(struct rev_info *revs, int cached)
 		exit(128);
 
 	diff_set_mnemonic_prefix(&revs->diffopt, "c/", cached ? "i/" : "w/");
+	diffcore_fix_diff_index(&revs->diffopt);
 	diffcore_std(&revs->diffopt);
 	diff_flush(&revs->diffopt);
 	return 0;
diff --git a/diff.c b/diff.c
index 08bbd3e..3bfb4a1 100644
--- a/diff.c
+++ b/diff.c
@@ -3628,6 +3628,23 @@ static void diffcore_skip_stat_unmatch(struct diff_options *diffopt)
 	*q = outq;
 }
 
+static int diffnamecmp(const void *a_, const void *b_)
+{
+	const struct diff_filepair *a = *((const struct diff_filepair **)a_);
+	const struct diff_filepair *b = *((const struct diff_filepair **)b_);
+	const char *name_a, *name_b;
+
+	name_a = a->one ? a->one->path : a->two->path;
+	name_b = b->one ? b->one->path : b->two->path;
+	return strcmp(name_a, name_b);
+}
+
+void diffcore_fix_diff_index(struct diff_options *options)
+{
+	struct diff_queue_struct *q = &diff_queued_diff;
+	qsort(q->queue, q->nr, sizeof(q->queue[0]), diffnamecmp);
+}
+
 void diffcore_std(struct diff_options *options)
 {
 	if (options->skip_stat_unmatch)
diff --git a/diff.h b/diff.h
index 15fcecd..471f606 100644
--- a/diff.h
+++ b/diff.h
@@ -208,6 +208,7 @@ extern int diff_setup_done(struct diff_options *);
 #define DIFF_PICKAXE_REGEX	2
 
 extern void diffcore_std(struct diff_options *);
+extern void diffcore_fix_diff_index(struct diff_options *);
 
 #define COMMON_DIFF_OPTIONS_HELP \
 "\ncommon diff options:\n" \
diff --git a/t/t1012-read-tree-df.sh b/t/t1012-read-tree-df.sh
index f1e650a..9811d46 100755
--- a/t/t1012-read-tree-df.sh
+++ b/t/t1012-read-tree-df.sh
@@ -51,7 +51,7 @@ test_expect_success setup '
 	:
 '
 
-test_expect_failure '3-way (1)' '
+test_expect_success '3-way (1)' '
 	settree A-000 &&
 	git read-tree -m -u O-000 A-000 B-000 &&
 	checkindex <<-EOF
@@ -63,7 +63,7 @@ test_expect_failure '3-way (1)' '
 	EOF
 '
 
-test_expect_failure '3-way (2)' '
+test_expect_success '3-way (2)' '
 	settree A-001 &&
 	git read-tree -m -u O-000 A-001 B-000 &&
 	checkindex <<-EOF
@@ -76,7 +76,7 @@ test_expect_failure '3-way (2)' '
 	EOF
 '
 
-test_expect_failure '3-way (3)' '
+test_expect_success '3-way (3)' '
 	settree A-010 &&
 	git read-tree -m -u O-010 A-010 B-010 &&
 	checkindex <<-EOF
@@ -90,7 +90,7 @@ test_expect_failure '3-way (3)' '
 	EOF
 '
 
-test_expect_failure '2-way (1)' '
+test_expect_success '2-way (1)' '
 	settree O-020 &&
 	git read-tree -m -u O-020 A-020 &&
 	checkindex <<-EOF
diff --git a/unpack-trees.c b/unpack-trees.c
index 685adb4..74cabc3 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -231,9 +231,37 @@ static int unpack_index_entry(struct cache_entry *ce,
 	return ret;
 }
 
+static int find_cache_pos(struct traverse_info *, const struct name_entry *);
+
+static void restore_cache_bottom(struct traverse_info *info, int bottom)
+{
+	struct unpack_trees_options *o = info->data;
+
+	if (o->diff_index_cached)
+		return;
+	o->cache_bottom = bottom;
+}
+
+static int switch_cache_bottom(struct traverse_info *info)
+{
+	struct unpack_trees_options *o = info->data;
+	int ret, pos;
+
+	if (o->diff_index_cached)
+		return 0;
+	ret = o->cache_bottom;
+	pos = find_cache_pos(info->prev, &info->name);
+
+	if (pos < -1)
+		o->cache_bottom = -2 - pos;
+	else if (pos < 0)
+		o->cache_bottom = o->src_index->cache_nr;
+	return ret;
+}
+
 static int traverse_trees_recursive(int n, unsigned long dirmask, unsigned long df_conflicts, struct name_entry *names, struct traverse_info *info)
 {
-	int i;
+	int i, ret, bottom;
 	struct tree_desc t[MAX_UNPACK_TREES];
 	struct traverse_info newinfo;
 	struct name_entry *p;
@@ -254,7 +282,11 @@ static int traverse_trees_recursive(int n, unsigned long dirmask, unsigned long
 			sha1 = names[i].sha1;
 		fill_tree_descriptor(t+i, sha1);
 	}
-	return traverse_trees(n, t, &newinfo);
+
+	bottom = switch_cache_bottom(&newinfo);
+	ret = traverse_trees(n, t, &newinfo);
+	restore_cache_bottom(&newinfo, bottom);
+	return ret;
 }
 
 /*
@@ -393,6 +425,82 @@ static int unpack_failed(struct unpack_trees_options *o, const char *message)
 	return -1;
 }
 
+/* NEEDSWORK: give this a better name and share with tree-walk.c */
+static int name_compare(const char *a, int a_len,
+			const char *b, int b_len)
+{
+	int len = (a_len < b_len) ? a_len : b_len;
+	int cmp = memcmp(a, b, len);
+	if (cmp)
+		return cmp;
+	return (a_len - b_len);
+}
+
+/*
+ * The tree traversal is looking at name p.  If we have a matching entry,
+ * return it.  If name p is a directory in the index, do not return
+ * anything, as we will want to match it when the traversal descends into
+ * the directory.
+ */
+static int find_cache_pos(struct traverse_info *info,
+			  const struct name_entry *p)
+{
+	int pos;
+	struct unpack_trees_options *o = info->data;
+	struct index_state *index = o->src_index;
+	int pfxlen = info->pathlen;
+	int p_len = tree_entry_len(p->path, p->sha1);
+
+	for (pos = o->cache_bottom; pos < index->cache_nr; pos++) {
+		struct cache_entry *ce = index->cache[pos];
+		const char *ce_name, *ce_slash;
+		int cmp, ce_len;
+
+		if (!ce_in_traverse_path(ce, info))
+			continue;
+		if (ce->ce_flags & CE_UNPACKED)
+			continue;
+		ce_name = ce->name + pfxlen;
+		ce_slash = strchr(ce_name, '/');
+		if (ce_slash)
+			ce_len = ce_slash - ce_name;
+		else
+			ce_len = ce_namelen(ce) - pfxlen;
+		cmp = name_compare(p->path, p_len, ce_name, ce_len);
+		/*
+		 * Exact match; if we have a directory we need to
+		 * delay returning it.
+		 */
+		if (!cmp)
+			return ce_slash ? -2 - pos : pos;
+		if (0 < cmp)
+			continue; /* keep looking */
+		/*
+		 * ce_name sorts after p->path; could it be that we
+		 * have files under p->path directory in the index?
+		 * E.g.  ce_name == "t-i", and p->path == "t"; we may
+		 * have "t/a" in the index.
+		 */
+		if (p_len < ce_len && !memcmp(ce_name, p->path, p_len) &&
+		    ce_name[p_len] < '/')
+			continue; /* keep looking */
+		break;
+	}
+	return -1;
+}
+
+static struct cache_entry *find_cache_entry(struct traverse_info *info,
+					    const struct name_entry *p)
+{
+	int pos = find_cache_pos(info, p);
+	struct unpack_trees_options *o = info->data;
+
+	if (0 <= pos)
+		return o->src_index->cache[pos];
+	else
+		return NULL;
+}
+
 static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, struct name_entry *names, struct traverse_info *info)
 {
 	struct cache_entry *src[MAX_UNPACK_TREES + 1] = { NULL, };
@@ -406,8 +514,14 @@ static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, str
 	/* Are we supposed to look at the index too? */
 	if (o->merge) {
 		while (1) {
-			struct cache_entry *ce = next_cache_entry(o);
 			int cmp;
+			struct cache_entry *ce;
+
+			if (o->diff_index_cached)
+				ce = next_cache_entry(o);
+			else
+				ce = find_cache_entry(info, p);
+
 			if (!ce)
 				break;
 			cmp = compare_entry(ce, info, p);
-- 
cgit v0.10.2-6-g49f6


From ba655da537a999670c7b21e0446e774a1f9733ea Mon Sep 17 00:00:00 2001
From: Junio C Hamano <gitster@pobox.com>
Date: Mon, 14 Sep 2009 02:22:00 -0700
Subject: read-tree --debug-unpack

A debugging patch.

Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff --git a/builtin-read-tree.c b/builtin-read-tree.c
index 2a3a32c..0c1f40d 100644
--- a/builtin-read-tree.c
+++ b/builtin-read-tree.c
@@ -64,6 +64,34 @@ static int exclude_per_directory_cb(const struct option *opt, const char *arg,
 	return 0;
 }
 
+static void debug_stage(const char *label, struct cache_entry *ce,
+			struct unpack_trees_options *o)
+{
+	printf("%s ", label);
+	if (!ce)
+		printf("(missing)\n");
+	else if (ce == o->df_conflict_entry)
+		printf("(conflict)\n");
+	else
+		printf("%06o #%d %s %.8s\n",
+		       ce->ce_mode, ce_stage(ce), ce->name,
+		       sha1_to_hex(ce->sha1));
+}
+
+static int debug_merge(struct cache_entry **stages, struct unpack_trees_options *o)
+{
+	int i;
+
+	printf("* %d-way merge\n", o->merge_size);
+	debug_stage("index", stages[0], o);
+	for (i = 1; i <= o->merge_size; i++) {
+		char buf[24];
+		sprintf(buf, "ent#%d", i);
+		debug_stage(buf, stages[i], o);
+	}
+	return 0;
+}
+
 static struct lock_file lock_file;
 
 int cmd_read_tree(int argc, const char **argv, const char *unused_prefix)
@@ -98,6 +126,8 @@ int cmd_read_tree(int argc, const char **argv, const char *unused_prefix)
 		  PARSE_OPT_NONEG, exclude_per_directory_cb },
 		OPT_SET_INT('i', NULL, &opts.index_only,
 			    "don't check the working tree after merging", 1),
+		OPT_SET_INT(0, "debug-unpack", &opts.debug_unpack,
+			    "debug unpack-trees", 1),
 		OPT_END()
 	};
 
@@ -165,6 +195,9 @@ int cmd_read_tree(int argc, const char **argv, const char *unused_prefix)
 			opts.head_idx = 1;
 	}
 
+	if (opts.debug_unpack)
+		opts.fn = debug_merge;
+
 	cache_tree_free(&active_cache_tree);
 	for (i = 0; i < nr_trees; i++) {
 		struct tree *tree = trees[i];
@@ -174,6 +207,9 @@ int cmd_read_tree(int argc, const char **argv, const char *unused_prefix)
 	if (unpack_trees(nr_trees, t, &opts))
 		return 128;
 
+	if (opts.debug_unpack)
+		return 0; /* do not write the index out */
+
 	/*
 	 * When reading only one tree (either the most basic form,
 	 * "-m ent" or "--reset ent" form), we can obtain a fully
diff --git a/unpack-trees.c b/unpack-trees.c
index 74cabc3..10e8871 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -501,6 +501,38 @@ static struct cache_entry *find_cache_entry(struct traverse_info *info,
 		return NULL;
 }
 
+static void debug_path(struct traverse_info *info)
+{
+	if (info->prev) {
+		debug_path(info->prev);
+		if (*info->prev->name.path)
+			putchar('/');
+	}
+	printf("%s", info->name.path);
+}
+
+static void debug_name_entry(int i, struct name_entry *n)
+{
+	printf("ent#%d %06o %s\n", i,
+	       n->path ? n->mode : 0,
+	       n->path ? n->path : "(missing)");
+}
+
+static void debug_unpack_callback(int n,
+				  unsigned long mask,
+				  unsigned long dirmask,
+				  struct name_entry *names,
+				  struct traverse_info *info)
+{
+	int i;
+	printf("* unpack mask %lu, dirmask %lu, cnt %d ",
+	       mask, dirmask, n);
+	debug_path(info);
+	putchar('\n');
+	for (i = 0; i < n; i++)
+		debug_name_entry(i, names + i);
+}
+
 static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, struct name_entry *names, struct traverse_info *info)
 {
 	struct cache_entry *src[MAX_UNPACK_TREES + 1] = { NULL, };
@@ -511,6 +543,9 @@ static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, str
 	while (!p->mode)
 		p++;
 
+	if (o->debug_unpack)
+		debug_unpack_callback(n, mask, dirmask, names, info);
+
 	/* Are we supposed to look at the index too? */
 	if (o->merge) {
 		while (1) {
diff --git a/unpack-trees.h b/unpack-trees.h
index 9a0733e..701dca5 100644
--- a/unpack-trees.h
+++ b/unpack-trees.h
@@ -28,6 +28,7 @@ struct unpack_trees_options {
 		     skip_unmerged,
 		     initial_checkout,
 		     diff_index_cached,
+		     debug_unpack,
 		     gently;
 	const char *prefix;
 	int cache_bottom;
-- 
cgit v0.10.2-6-g49f6