Merge branch 'cb/leading-path-removal'

* cb/leading-path-removal:
  use persistent memory for rejected paths
  do not overwrite files in leading path
  lstat_cache: optionally return match_len
  add function check_ok_to_remove()
  t7607: add leading-path tests
  t7607: use test-lib functions and check MERGE_HEAD

Conflicts:
	t/t7607-merge-overwrite.sh

6 files changed, 215 insertions, 135 deletions

diff --git a/cache.h b/cache.h
index 33decd942d..d85ce86f7f 100644
--- a/cache.h
+++ b/cache.h
@@ -859,7 +859,7 @@ struct cache_def {
 
 extern int has_symlink_leading_path(const char *name, int len);
 extern int threaded_has_symlink_leading_path(struct cache_def *, const char *, int);
-extern int has_symlink_or_noent_leading_path(const char *name, int len);
+extern int check_leading_path(const char *name, int len);
 extern int has_dirs_only_path(const char *name, int len, int prefix_len);
 extern void schedule_dir_for_removal(const char *name, int len);
 extern void remove_scheduled_dirs(void);
diff --git a/symlinks.c b/symlinks.c
index 8860120011..3cacebd91a 100644
--- a/symlinks.c
+++ b/symlinks.c
@@ -64,11 +64,13 @@ static inline void reset_lstat_cache(struct cache_def *cache)
  * of the prefix, where the cache should use the stat() function
  * instead of the lstat() function to test each path component.
  */
-static int lstat_cache(struct cache_def *cache, const char *name, int len,
-		       int track_flags, int prefix_len_stat_func)
+static int lstat_cache_matchlen(struct cache_def *cache,
+				const char *name, int len,
+				int *ret_flags, int track_flags,
+				int prefix_len_stat_func)
 {
 	int match_len, last_slash, last_slash_dir, previous_slash;
-	int match_flags, ret_flags, save_flags, max_len, ret;
+	int save_flags, max_len, ret;
 	struct stat st;
 
 	if (cache->track_flags != track_flags ||
@@ -90,13 +92,13 @@ static int lstat_cache(struct cache_def *cache, const char *name, int len,
 		match_len = last_slash =
 			longest_path_match(name, len, cache->path, cache->len,
 					   &previous_slash);
-		match_flags = cache->flags & track_flags & (FL_NOENT|FL_SYMLINK);
+		*ret_flags = cache->flags & track_flags & (FL_NOENT|FL_SYMLINK);
 
 		if (!(track_flags & FL_FULLPATH) && match_len == len)
 			match_len = last_slash = previous_slash;
 
-		if (match_flags && match_len == cache->len)
-			return match_flags;
+		if (*ret_flags && match_len == cache->len)
+			return match_len;
 		/*
 		 * If we now have match_len > 0, we would know that
 		 * the matched part will always be a directory.
@@ -105,16 +107,16 @@ static int lstat_cache(struct cache_def *cache, const char *name, int len,
 		 * a substring of the cache on a path component basis,
 		 * we can return immediately.
 		 */
-		match_flags = track_flags & FL_DIR;
-		if (match_flags && len == match_len)
-			return match_flags;
+		*ret_flags = track_flags & FL_DIR;
+		if (*ret_flags && len == match_len)
+			return match_len;
 	}
 
 	/*
 	 * Okay, no match from the cache so far, so now we have to
 	 * check the rest of the path components.
 	 */
-	ret_flags = FL_DIR;
+	*ret_flags = FL_DIR;
 	last_slash_dir = last_slash;
 	max_len = len < PATH_MAX ? len : PATH_MAX;
 	while (match_len < max_len) {
@@ -133,16 +135,16 @@ static int lstat_cache(struct cache_def *cache, const char *name, int len,
 			ret = lstat(cache->path, &st);
 
 		if (ret) {
-			ret_flags = FL_LSTATERR;
+			*ret_flags = FL_LSTATERR;
 			if (errno == ENOENT)
-				ret_flags |= FL_NOENT;
+				*ret_flags |= FL_NOENT;
 		} else if (S_ISDIR(st.st_mode)) {
 			last_slash_dir = last_slash;
 			continue;
 		} else if (S_ISLNK(st.st_mode)) {
-			ret_flags = FL_SYMLINK;
+			*ret_flags = FL_SYMLINK;
 		} else {
-			ret_flags = FL_ERR;
+			*ret_flags = FL_ERR;
 		}
 		break;
 	}
@@ -152,7 +154,7 @@ static int lstat_cache(struct cache_def *cache, const char *name, int len,
 	 * path types, FL_NOENT, FL_SYMLINK and FL_DIR, can be cached
 	 * for the moment!
 	 */
-	save_flags = ret_flags & track_flags & (FL_NOENT|FL_SYMLINK);
+	save_flags = *ret_flags & track_flags & (FL_NOENT|FL_SYMLINK);
 	if (save_flags && last_slash > 0 && last_slash <= PATH_MAX) {
 		cache->path[last_slash] = '\0';
 		cache->len = last_slash;
@@ -176,7 +178,16 @@ static int lstat_cache(struct cache_def *cache, const char *name, int len,
 	} else {
 		reset_lstat_cache(cache);
 	}
-	return ret_flags;
+	return match_len;
+}
+
+static int lstat_cache(struct cache_def *cache, const char *name, int len,
+		       int track_flags, int prefix_len_stat_func)
+{
+	int flags;
+	(void)lstat_cache_matchlen(cache, name, len, &flags, track_flags,
+			prefix_len_stat_func);
+	return flags;
 }
 
 #define USE_ONLY_LSTAT  0
@@ -198,15 +209,26 @@ int has_symlink_leading_path(const char *name, int len)
 }
 
 /*
- * Return non-zero if path 'name' has a leading symlink component or
+ * Return zero if path 'name' has a leading symlink component or
  * if some leading path component does not exists.
+ *
+ * Return -1 if leading path exists and is a directory.
+ *
+ * Return path length if leading path exists and is neither a
+ * directory nor a symlink.
  */
-int has_symlink_or_noent_leading_path(const char *name, int len)
+int check_leading_path(const char *name, int len)
 {
 	struct cache_def *cache = &default_cache;	/* FIXME */
-	return lstat_cache(cache, name, len,
-			   FL_SYMLINK|FL_NOENT|FL_DIR, USE_ONLY_LSTAT) &
-		(FL_SYMLINK|FL_NOENT);
+	int flags;
+	int match_len = lstat_cache_matchlen(cache, name, len, &flags,
+			   FL_SYMLINK|FL_NOENT|FL_DIR, USE_ONLY_LSTAT);
+	if (flags & (FL_SYMLINK|FL_NOENT))
+		return 0;
+	else if (flags & FL_DIR)
+		return -1;
+	else
+		return match_len;
 }
 
 /*
diff --git a/t/t7607-merge-overwrite.sh b/t/t7607-merge-overwrite.sh
index 3988900fc3..4d5ce4e682 100755
--- a/t/t7607-merge-overwrite.sh
+++ b/t/t7607-merge-overwrite.sh
@@ -7,48 +7,54 @@ Do not overwrite changes.'
 . ./test-lib.sh
 
 test_expect_success 'setup' '
-	echo c0 > c0.c &&
-	git add c0.c &&
-	git commit -m c0 &&
-	git tag c0 &&
-	echo c1 > c1.c &&
-	git add c1.c &&
-	git commit -m c1 &&
-	git tag c1 &&
+	test_commit c0 c0.c &&
+	test_commit c1 c1.c &&
+	test_commit c1a c1.c "c1 a" &&
 	git reset --hard c0 &&
-	echo c2 > c2.c &&
-	git add c2.c &&
-	git commit -m c2 &&
-	git tag c2 &&
-	git reset --hard c1 &&
-	echo "c1 a" > c1.c &&
-	git add c1.c &&
-	git commit -m "c1 a" &&
-	git tag c1a &&
+	test_commit c2 c2.c &&
+	git reset --hard c0 &&
+	mkdir sub &&
+	echo "sub/f" > sub/f &&
+	mkdir sub2 &&
+	echo "sub2/f" > sub2/f &&
+	git add sub/f sub2/f &&
+	git commit -m sub &&
+	git tag sub &&
 	echo "VERY IMPORTANT CHANGES" > important
 '
 
 test_expect_success 'will not overwrite untracked file' '
 	git reset --hard c1 &&
-	cat important > c2.c &&
+	cp important c2.c &&
 	test_must_fail git merge c2 &&
+	test_path_is_missing .git/MERGE_HEAD &&
 	test_cmp important c2.c
 '
 
+test_expect_success 'will overwrite tracked file' '
+	git reset --hard c1 &&
+	cp important c2.c &&
+	git add c2.c &&
+	git commit -m important &&
+	git checkout c2
+'
+
 test_expect_success 'will not overwrite new file' '
 	git reset --hard c1 &&
-	cat important > c2.c &&
+	cp important c2.c &&
 	git add c2.c &&
 	test_must_fail git merge c2 &&
+	test_path_is_missing .git/MERGE_HEAD &&
 	test_cmp important c2.c
 '
 
 test_expect_success 'will not overwrite staged changes' '
 	git reset --hard c1 &&
-	cat important > c2.c &&
+	cp important c2.c &&
 	git add c2.c &&
 	rm c2.c &&
 	test_must_fail git merge c2 &&
+	test_path_is_missing .git/MERGE_HEAD &&
 	git checkout c2.c &&
 	test_cmp important c2.c
 '
@@ -57,7 +63,7 @@ test_expect_success 'will not overwrite removed file' '
 	git reset --hard c1 &&
 	git rm c1.c &&
 	git commit -m "rm c1.c" &&
-	cat important > c1.c &&
+	cp important c1.c &&
 	test_must_fail git merge c1a &&
 	test_cmp important c1.c
 '
@@ -66,9 +72,10 @@ test_expect_success 'will not overwrite re-added file' '
 	git reset --hard c1 &&
 	git rm c1.c &&
 	git commit -m "rm c1.c" &&
-	cat important > c1.c &&
+	cp important c1.c &&
 	git add c1.c &&
 	test_must_fail git merge c1a &&
+	test_path_is_missing .git/MERGE_HEAD &&
 	test_cmp important c1.c
 '
 
@@ -76,14 +83,63 @@ test_expect_success 'will not overwrite removed file with staged changes' '
 	git reset --hard c1 &&
 	git rm c1.c &&
 	git commit -m "rm c1.c" &&
-	cat important > c1.c &&
+	cp important c1.c &&
 	git add c1.c &&
 	rm c1.c &&
 	test_must_fail git merge c1a &&
+	test_path_is_missing .git/MERGE_HEAD &&
 	git checkout c1.c &&
 	test_cmp important c1.c
 '
 
+test_expect_success 'will not overwrite untracked subtree' '
+	git reset --hard c0 &&
+	rm -rf sub &&
+	mkdir -p sub/f &&
+	cp important sub/f/important &&
+	test_must_fail git merge sub &&
+	test_path_is_missing .git/MERGE_HEAD &&
+	test_cmp important sub/f/important
+'
+
+cat >expect <<\EOF
+error: The following untracked working tree files would be overwritten by merge:
+	sub
+	sub2
+Please move or remove them before you can merge.
+EOF
+
+test_expect_success 'will not overwrite untracked file in leading path' '
+	git reset --hard c0 &&
+	rm -rf sub &&
+	cp important sub &&
+	cp important sub2 &&
+	test_must_fail git merge sub 2>out &&
+	test_cmp out expect &&
+	test_path_is_missing .git/MERGE_HEAD &&
+	test_cmp important sub &&
+	test_cmp important sub2 &&
+	rm -f sub sub2
+'
+
+test_expect_failure SYMLINKS 'will not overwrite untracked symlink in leading path' '
+	git reset --hard c0 &&
+	rm -rf sub &&
+	mkdir sub2 &&
+	ln -s sub2 sub &&
+	test_must_fail git merge sub &&
+	test_path_is_missing .git/MERGE_HEAD
+'
+
+test_expect_success SYMLINKS 'will not be confused by symlink in leading path' '
+	git reset --hard c0 &&
+	rm -rf sub &&
+	ln -s sub2 sub &&
+	git add sub &&
+	git commit -m ln &&
+	git checkout sub
+'
+
 cat >expect <<\EOF
 error: Untracked working tree file 'c0.c' would be overwritten by merge.
 fatal: read-tree failed
diff --git a/t/t7609-merge-co-error-msgs.sh b/t/t7609-merge-co-error-msgs.sh
index 114d2bd785..c994836c53 100755
--- a/t/t7609-merge-co-error-msgs.sh
+++ b/t/t7609-merge-co-error-msgs.sh
@@ -27,10 +27,10 @@ test_expect_success 'setup' '
 
 cat >expect <<\EOF
 error: The following untracked working tree files would be overwritten by merge:
-	two
-	three
-	four
 	five
+	four
+	three
+	two
 Please move or remove them before you can merge.
 EOF
 
@@ -49,9 +49,9 @@ test_expect_success 'untracked files overwritten by merge (fast and non-fast for
 
 cat >expect <<\EOF
 error: Your local changes to the following files would be overwritten by merge:
-	two
-	three
 	four
+	three
+	two
 Please, commit your changes or stash them before you can merge.
 error: The following untracked working tree files would be overwritten by merge:
 	five
@@ -68,8 +68,8 @@ test_expect_success 'untracked files or local changes ovewritten by merge' '
 
 cat >expect <<\EOF
 error: Your local changes to the following files would be overwritten by checkout:
-	rep/two
 	rep/one
+	rep/two
 Please, commit your changes or stash them before you can switch branches.
 EOF
 
@@ -89,8 +89,8 @@ test_expect_success 'cannot switch branches because of local changes' '
 
 cat >expect <<\EOF
 error: Your local changes to the following files would be overwritten by checkout:
-	rep/two
 	rep/one
+	rep/two
 Please, commit your changes or stash them before you can switch branches.
 EOF
 
@@ -102,8 +102,8 @@ test_expect_success 'not uptodate file porcelain checkout error' '
 
 cat >expect <<\EOF
 error: Updating the following directories would lose untracked files in it:
-	rep2
 	rep
+	rep2
 
 EOF
 
diff --git a/unpack-trees.c b/unpack-trees.c
index 803445aa7b..d5a453079a 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -53,6 +53,7 @@ const char *unpack_plumbing_errors[NB_UNPACK_TREES_ERROR_TYPES] = {
 void setup_unpack_trees_porcelain(struct unpack_trees_options *opts,
 				  const char *cmd)
 {
+	int i;
 	const char **msgs = opts->msgs;
 	const char *msg;
 	char *tmp;
@@ -96,6 +97,9 @@ void setup_unpack_trees_porcelain(struct unpack_trees_options *opts,
 		"The following Working tree files would be removed by sparse checkout update:\n%s";
 
 	opts->show_all_errors = 1;
+	/* rejected paths may not have a static buffer */
+	for (i = 0; i < ARRAY_SIZE(opts->unpack_rejects); i++)
+		opts->unpack_rejects[i].strdup_strings = 1;
 }
 
 static void add_entry(struct unpack_trees_options *o, struct cache_entry *ce,
@@ -124,7 +128,6 @@ static int add_rejected_path(struct unpack_trees_options *o,
 			     enum unpack_trees_error_types e,
 			     const char *path)
 {
-	struct rejected_paths_list *newentry;
 	if (!o->show_all_errors)
 		return error(ERRORMSG(o, e), path);
 
@@ -132,45 +135,28 @@ static int add_rejected_path(struct unpack_trees_options *o,
 	 * Otherwise, insert in a list for future display by
 	 * display_error_msgs()
 	 */
-	newentry = xmalloc(sizeof(struct rejected_paths_list));
-	newentry->path = (char *)path;
-	newentry->next = o->unpack_rejects[e];
-	o->unpack_rejects[e] = newentry;
+	string_list_append(&o->unpack_rejects[e], path);
 	return -1;
 }
 
 /*
- * free all the structures allocated for the error <e>
- */
-static void free_rejected_paths(struct unpack_trees_options *o,
-				enum unpack_trees_error_types e)
-{
-	while (o->unpack_rejects[e]) {
-		struct rejected_paths_list *del = o->unpack_rejects[e];
-		o->unpack_rejects[e] = o->unpack_rejects[e]->next;
-		free(del);
-	}
-	free(o->unpack_rejects[e]);
-}
-
-/*
  * display all the error messages stored in a nice way
  */
 static void display_error_msgs(struct unpack_trees_options *o)
 {
-	int e;
+	int e, i;
 	int something_displayed = 0;
 	for (e = 0; e < NB_UNPACK_TREES_ERROR_TYPES; e++) {
-		if (o->unpack_rejects[e]) {
-			struct rejected_paths_list *rp;
+		struct string_list *rejects = &o->unpack_rejects[e];
+		if (rejects->nr > 0) {
 			struct strbuf path = STRBUF_INIT;
 			something_displayed = 1;
-			for (rp = o->unpack_rejects[e]; rp; rp = rp->next)
-				strbuf_addf(&path, "\t%s\n", rp->path);
+			for (i = 0; i < rejects->nr; i++)
+				strbuf_addf(&path, "\t%s\n", rejects->items[i].string);
 			error(ERRORMSG(o, e), path.buf);
 			strbuf_release(&path);
-			free_rejected_paths(o, e);
 		}
+		string_list_clear(rejects, 0);
 	}
 	if (something_displayed)
 		printf("Aborting\n");
@@ -182,7 +168,7 @@ static void display_error_msgs(struct unpack_trees_options *o)
  */
 static void unlink_entry(struct cache_entry *ce)
 {
-	if (has_symlink_or_noent_leading_path(ce->name, ce_namelen(ce)))
+	if (!check_leading_path(ce->name, ce_namelen(ce)))
 		return;
 	if (remove_or_warn(ce->ce_mode, ce->name))
 		return;
@@ -1127,14 +1113,65 @@ static int verify_clean_subdirectory(struct cache_entry *ce,
  * See if we can find a case-insensitive match in the index that also
  * matches the stat information, and assume it's that other file!
  */
-static int icase_exists(struct unpack_trees_options *o, struct cache_entry *dst, struct stat *st)
+static int icase_exists(struct unpack_trees_options *o, const char *name, int len, struct stat *st)
 {
 	struct cache_entry *src;
 
-	src = index_name_exists(o->src_index, dst->name, ce_namelen(dst), 1);
+	src = index_name_exists(o->src_index, name, len, 1);
 	return src && !ie_match_stat(o->src_index, src, st, CE_MATCH_IGNORE_VALID|CE_MATCH_IGNORE_SKIP_WORKTREE);
 }
 
+static int check_ok_to_remove(const char *name, int len, int dtype,
+			      struct cache_entry *ce, struct stat *st,
+			      enum unpack_trees_error_types error_type,
+			      struct unpack_trees_options *o)
+{
+	struct cache_entry *result;
+
+	/*
+	 * It may be that the 'lstat()' succeeded even though
+	 * target 'ce' was absent, because there is an old
+	 * entry that is different only in case..
+	 *
+	 * Ignore that lstat() if it matches.
+	 */
+	if (ignore_case && icase_exists(o, name, len, st))
+		return 0;
+
+	if (o->dir && excluded(o->dir, name, &dtype))
+		/*
+		 * ce->name is explicitly excluded, so it is Ok to
+		 * overwrite it.
+		 */
+		return 0;
+	if (S_ISDIR(st->st_mode)) {
+		/*
+		 * We are checking out path "foo" and
+		 * found "foo/." in the working tree.
+		 * This is tricky -- if we have modified
+		 * files that are in "foo/" we would lose
+		 * them.
+		 */
+		if (verify_clean_subdirectory(ce, error_type, o) < 0)
+			return -1;
+		return 0;
+	}
+
+	/*
+	 * The previous round may already have decided to
+	 * delete this path, which is in a subdirectory that
+	 * is being replaced with a blob.
+	 */
+	result = index_name_exists(&o->result, name, len, 0);
+	if (result) {
+		if (result->ce_flags & CE_REMOVE)
+			return 0;
+	}
+
+	return o->gently ? -1 :
+		add_rejected_path(o, error_type, name);
+}
+
 /*
  * We do not want to remove or overwrite a working tree file that
  * is not tracked, unless it is ignored.
@@ -1143,63 +1180,31 @@ static int verify_absent_1(struct cache_entry *ce,
 				 enum unpack_trees_error_types error_type,
 				 struct unpack_trees_options *o)
 {
+	int len;
 	struct stat st;
 
 	if (o->index_only || o->reset || !o->update)
 		return 0;
 
-	if (has_symlink_or_noent_leading_path(ce->name, ce_namelen(ce)))
+	len = check_leading_path(ce->name, ce_namelen(ce));
+	if (!len)
 		return 0;
+	else if (len > 0) {
+		char path[PATH_MAX + 1];
+		memcpy(path, ce->name, len);
+		path[len] = 0;
+		lstat(path, &st);
+
+		return check_ok_to_remove(path, len, DT_UNKNOWN, NULL, &st,
+				error_type, o);
+	} else if (!lstat(ce->name, &st))
+		return check_ok_to_remove(ce->name, ce_namelen(ce),
+				ce_to_dtype(ce), ce, &st,
+				error_type, o);
 
-	if (!lstat(ce->name, &st)) {
-		int dtype = ce_to_dtype(ce);
-		struct cache_entry *result;
-
-		/*
-		 * It may be that the 'lstat()' succeeded even though
-		 * target 'ce' was absent, because there is an old
-		 * entry that is different only in case..
-		 *
-		 * Ignore that lstat() if it matches.
-		 */
-		if (ignore_case && icase_exists(o, ce, &st))
-			return 0;
-
-		if (o->dir && excluded(o->dir, ce->name, &dtype))
-			/*
-			 * ce->name is explicitly excluded, so it is Ok to
-			 * overwrite it.
-			 */
-			return 0;
-		if (S_ISDIR(st.st_mode)) {
-			/*
-			 * We are checking out path "foo" and
-			 * found "foo/." in the working tree.
-			 * This is tricky -- if we have modified
-			 * files that are in "foo/" we would lose
-			 * them.
-			 */
-			if (verify_clean_subdirectory(ce, error_type, o) < 0)
-				return -1;
-			return 0;
-		}
-
-		/*
-		 * The previous round may already have decided to
-		 * delete this path, which is in a subdirectory that
-		 * is being replaced with a blob.
-		 */
-		result = index_name_exists(&o->result, ce->name, ce_namelen(ce), 0);
-		if (result) {
-			if (result->ce_flags & CE_REMOVE)
-				return 0;
-		}
-
-		return o->gently ? -1 :
-			add_rejected_path(o, error_type, ce->name);
-	}
 	return 0;
 }
+
 static int verify_absent(struct cache_entry *ce,
 			 enum unpack_trees_error_types error_type,
 			 struct unpack_trees_options *o)
diff --git a/unpack-trees.h b/unpack-trees.h
index 7c0187d11a..cd11a08365 100644
--- a/unpack-trees.h
+++ b/unpack-trees.h
@@ -1,6 +1,8 @@
 #ifndef UNPACK_TREES_H
 #define UNPACK_TREES_H
 
+#include "string-list.h"
+
 #define MAX_UNPACK_TREES 8
 
 struct unpack_trees_options;
@@ -29,11 +31,6 @@ enum unpack_trees_error_types {
 void setup_unpack_trees_porcelain(struct unpack_trees_options *opts,
 				  const char *cmd);
 
-struct rejected_paths_list {
-	char *path;
-	struct rejected_paths_list *next;
-};
-
 struct unpack_trees_options {
 	unsigned int reset,
 		     merge,
@@ -59,7 +56,7 @@ struct unpack_trees_options {
 	 * Store error messages in an array, each case
 	 * corresponding to a error message type
 	 */
-	struct rejected_paths_list *unpack_rejects[NB_UNPACK_TREES_ERROR_TYPES];
+	struct string_list unpack_rejects[NB_UNPACK_TREES_ERROR_TYPES];
 
 	int head_idx;
 	int merge_size;