Merge branch 'jc/fix-tree-walk'

* jc/fix-tree-walk:
  read-tree --debug-unpack
  unpack-trees.c: look ahead in the index
  unpack-trees.c: prepare for looking ahead in the index
  Aggressive three-way merge: fix D/F case
  traverse_trees(): handle D/F conflict case sanely
  more D/F conflict tests
  tests: move convenience regexp to match object names to test-lib.sh

Conflicts:
	builtin-read-tree.c
	unpack-trees.c
	unpack-trees.h

19 files changed, 734 insertions, 140 deletions

diff --git a/builtin-read-tree.c b/builtin-read-tree.c
index 5fda9905fc..8bdcab1138 100644
--- a/builtin-read-tree.c
+++ b/builtin-read-tree.c
@@ -65,6 +65,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)
@@ -101,6 +129,8 @@ int cmd_read_tree(int argc, const char **argv, const char *unused_prefix)
 			    "don't check the working tree after merging", 1),
 		OPT_SET_INT(0, "no-sparse-checkout", &opts.skip_sparse_checkout,
 			    "skip applying sparse checkout filter", 1),
+		OPT_SET_INT(0, "debug-unpack", &opts.debug_unpack,
+			    "debug unpack-trees", 1),
 		OPT_END()
 	};
 
@@ -169,6 +199,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];
@@ -178,6 +211,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/cache.h b/cache.h
index 7d5c21e3f1..b3370eb41e 100644
--- a/cache.h
+++ b/cache.h
@@ -182,6 +182,8 @@ struct cache_entry {
 /* Only remove in work directory, not index */
 #define CE_WT_REMOVE (0x400000)
 
+#define CE_UNPACKED  (0x1000000)
+
 /*
  * Extended on-disk flags
  */
diff --git a/diff-lib.c b/diff-lib.c
index 23e180eed1..ec2e2ac005 100644
--- a/diff-lib.c
+++ b/diff-lib.c
@@ -380,21 +380,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
@@ -416,9 +401,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
@@ -464,6 +446,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 160dbfd718..f130a367dc 100644
--- a/diff.c
+++ b/diff.c
@@ -3678,6 +3678,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 968a8dce95..2ef3341fb0 100644
--- a/diff.h
+++ b/diff.h
@@ -210,6 +210,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/diff-lib.sh b/t/diff-lib.sh
index 4bddeb591e..75a35fcd06 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 22ba7a5442..4f171722d9 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 c2d408b461..6327d205cb 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 5e40cec530..0241329a08 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/t1012-read-tree-df.sh b/t/t1012-read-tree-df.sh
new file mode 100755
index 0000000000..9811d467da
--- /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_success '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_success '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
diff --git a/t/t3100-ls-tree-restrict.sh b/t/t3100-ls-tree-restrict.sh
index ee60d03fe8..eee0d344d2 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 8be9fb4112..06654c6f82 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 8c1b81e248..ff8c2f7532 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 510bb9679f..af34a1e817 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/t6035-merge-dir-to-symlink.sh b/t/t6035-merge-dir-to-symlink.sh
index 5b96fb0b37..d1b22871c4 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 &&
@@ -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/t/test-lib.sh b/t/test-lib.sh
index c1476f9a23..baa4093073 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...
diff --git a/tree-walk.c b/tree-walk.c
index 02e2aed773..08796c2322 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;
 }
 
diff --git a/unpack-trees.c b/unpack-trees.c
index 0ddbef3e63..75f54cac97 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -198,23 +198,142 @@ 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 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;
@@ -235,7 +354,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;
 }
 
 /*
@@ -284,6 +407,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);
@@ -360,6 +497,114 @@ 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 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, };
@@ -370,25 +615,38 @@ 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 (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) {
+			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);
 			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;
 					}
 				}
@@ -401,6 +659,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;
@@ -417,11 +682,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;
 			}
 		}
@@ -465,11 +732,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));
@@ -483,22 +749,38 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options
 		info.fn = unpack_callback;
 		info.data = o;
 
-		if (traverse_trees(len, t, &info) < 0) {
-			ret = unpack_failed(o, NULL);
-			goto done;
+		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)
+			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];
-			if (unpack_index_entry(ce, o) < 0) {
-				ret = unpack_failed(o, NULL);
-				goto done;
-			}
+		while (1) {
+			struct cache_entry *ce = next_cache_entry(o);
+			if (!ce)
+				break;
+			if (unpack_index_entry(ce, o) < 0)
+				goto return_failed;
 		}
 	}
+	mark_all_ce_unused(o->src_index);
 
 	if (o->trivial_merges_only && o->nontrivial_merge) {
 		ret = unpack_failed(o, "Merge requires file-level merging");
@@ -543,6 +825,11 @@ done:
 		free(el.excludes);
 
 	return ret;
+
+return_failed:
+	mark_all_ce_unused(o->src_index);
+	ret = unpack_failed(o, NULL);
+	goto done;
 }
 
 /* Here come the merge functions */
@@ -661,7 +948,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 ||
@@ -669,12 +958,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++;
 	}
@@ -731,7 +1022,6 @@ static int verify_absent_1(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;
 
@@ -759,28 +1049,8 @@ static int verify_absent_1(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;
 		}
 
@@ -927,7 +1197,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)) {
@@ -941,7 +1212,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.
 	 */
@@ -971,12 +1243,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)
diff --git a/unpack-trees.h b/unpack-trees.h
index 95ff36c824..ef70eab390 100644
--- a/unpack-trees.h
+++ b/unpack-trees.h
@@ -31,10 +31,11 @@ struct unpack_trees_options {
 		     skip_unmerged,
 		     initial_checkout,
 		     diff_index_cached,
+		     debug_unpack,
 		     skip_sparse_checkout,
 		     gently;
 	const char *prefix;
-	int pos;
+	int cache_bottom;
 	struct dir_struct *dir;
 	merge_fn_t fn;
 	struct unpack_trees_error_msgs msgs;