Merge pull request #2085 from libgit2/rb/index-tree-blob-collision

Index tree-bob collision

6 files changed, 263 insertions, 23 deletions

diff --git a/src/checkout.c b/src/checkout.c
index f11ab8d46..72fe5368f 100644
--- a/src/checkout.c
+++ b/src/checkout.c
@@ -246,6 +246,8 @@ static int checkout_action_no_wd(
 			*action = CHECKOUT_ACTION_IF(SAFE, UPDATE_BLOB, NONE);
 		break;
 	case GIT_DELTA_DELETED: /* case 8 or 25 */
+		*action = CHECKOUT_ACTION_IF(SAFE, REMOVE, NONE);
+		break;
 	default: /* impossible */
 		break;
 	}
diff --git a/src/index.c b/src/index.c
index d58968454..7bc5d5b24 100644
--- a/src/index.c
+++ b/src/index.c
@@ -90,6 +90,7 @@ struct entry_long {
 
 struct entry_srch_key {
 	const char *path;
+	int path_len;
 	int stage;
 };
 
@@ -109,28 +110,49 @@ static int index_srch(const void *key, const void *array_member)
 {
 	const struct entry_srch_key *srch_key = key;
 	const git_index_entry *entry = array_member;
-	int ret;
+	int cmp, len1, len2, len;
 
-	ret = strcmp(srch_key->path, entry->path);
+	len1 = srch_key->path_len;
+	len2 = strlen(entry->path);
+	len = len1 < len2 ? len1 : len2;
 
-	if (ret == 0 && srch_key->stage != GIT_INDEX_STAGE_ANY)
-		ret = srch_key->stage - GIT_IDXENTRY_STAGE(entry);
+	cmp = memcmp(srch_key->path, entry->path, len);
+	if (cmp)
+		return cmp;
+	if (len1 < len2)
+		return -1;
+	if (len1 > len2)
+		return 1;
 
-	return ret;
+	if (srch_key->stage != GIT_INDEX_STAGE_ANY)
+		return srch_key->stage - GIT_IDXENTRY_STAGE(entry);
+
+	return 0;
 }
 
 static int index_isrch(const void *key, const void *array_member)
 {
 	const struct entry_srch_key *srch_key = key;
 	const git_index_entry *entry = array_member;
-	int ret;
+	int cmp, len1, len2, len;
 
-	ret = strcasecmp(srch_key->path, entry->path);
+	len1 = srch_key->path_len;
+	len2 = strlen(entry->path);
+	len = len1 < len2 ? len1 : len2;
 
-	if (ret == 0 && srch_key->stage != GIT_INDEX_STAGE_ANY)
-		ret = srch_key->stage - GIT_IDXENTRY_STAGE(entry);
+	cmp = strncasecmp(srch_key->path, entry->path, len);
 
-	return ret;
+	if (cmp)
+		return cmp;
+	if (len1 < len2)
+		return -1;
+	if (len1 > len2)
+		return 1;
+
+	if (srch_key->stage != GIT_INDEX_STAGE_ANY)
+		return srch_key->stage - GIT_IDXENTRY_STAGE(entry);
+
+	return 0;
 }
 
 static int index_cmp_path(const void *a, const void *b)
@@ -579,7 +601,7 @@ const git_index_entry *git_index_get_bypath(
 
 	git_vector_sort(&index->entries);
 
-	if (git_index__find(&pos, index, path, stage) < 0) {
+	if (git_index__find(&pos, index, path, strlen(path), stage) < 0) {
 		giterr_set(GITERR_INDEX, "Index does not contain %s", path);
 		return NULL;
 	}
@@ -701,6 +723,101 @@ static git_index_entry *index_entry_dup(const git_index_entry *source_entry)
 	return entry;
 }
 
+static int has_file_name(git_index *index,
+	 const git_index_entry *entry, size_t pos, int ok_to_replace)
+{
+	int retval = 0;
+	size_t len = strlen(entry->path);
+	int stage = GIT_IDXENTRY_STAGE(entry);
+	const char *name = entry->path;
+
+	while (pos < index->entries.length) {
+		git_index_entry *p = index->entries.contents[pos++];
+
+		if (len >= strlen(p->path))
+			break;
+		if (memcmp(name, p->path, len))
+			break;
+		if (GIT_IDXENTRY_STAGE(p) != stage)
+			continue;
+		if (p->path[len] != '/')
+			continue;
+		retval = -1;
+		if (!ok_to_replace)
+			break;
+		git_vector_remove(&index->entries, --pos);
+	}
+	return retval;
+}
+
+/*
+ * Do we have another file with a pathname that is a proper
+ * subset of the name we're trying to add?
+ */
+static int has_dir_name(git_index *index,
+		const git_index_entry *entry, int ok_to_replace)
+{
+	int retval = 0;
+	int stage = GIT_IDXENTRY_STAGE(entry);
+	const char *name = entry->path;
+	const char *slash = name + strlen(name);
+
+	for (;;) {
+		size_t len, position;
+
+		for (;;) {
+			if (*--slash == '/')
+				break;
+			if (slash <= entry->path)
+				return retval;
+		}
+		len = slash - name;
+
+		if (git_index__find(&position, index, name, len, stage) == 0) {
+			retval = -1;
+			if (!ok_to_replace)
+				break;
+
+			git_vector_remove(&index->entries, position);
+			continue;
+		}
+
+		/*
+		 * Trivial optimization: if we find an entry that
+		 * already matches the sub-directory, then we know
+		 * we're ok, and we can exit.
+		 */
+		while (position < index->entries.length) {
+			git_index_entry *p = index->entries.contents[position];
+
+			if ((strlen(p->path) <= len) ||
+			    (p->path[len] != '/') ||
+			    memcmp(p->path, name, len))
+				break; /* not our subdirectory */
+
+			if (GIT_IDXENTRY_STAGE(p) == stage)
+				return retval;
+
+			position++;
+		}
+	}
+	return retval;
+}
+
+static int check_file_directory_collision(git_index *index,
+		git_index_entry *entry, size_t pos, int ok_to_replace)
+{
+	int retval = has_file_name(index, entry, pos, ok_to_replace);
+	retval = retval + has_dir_name(index, entry, ok_to_replace);
+
+	if (retval) {
+		giterr_set(GITERR_INDEX, "'%s' appears as both a file an a directory", entry->path);
+		return -1;
+	}
+
+	return 0;
+}
+
 static int index_insert(git_index *index, git_index_entry *entry, int replace)
 {
 	size_t path_length, position;
@@ -720,13 +837,16 @@ static int index_insert(git_index *index, git_index_entry *entry, int replace)
 
 	/* look if an entry with this path already exists */
 	if (!git_index__find(
-			&position, index, entry->path, GIT_IDXENTRY_STAGE(entry))) {
+			&position, index, entry->path, strlen(entry->path),
+			GIT_IDXENTRY_STAGE(entry))) {
 		existing = (git_index_entry **)&index->entries.contents[position];
-
 		/* update filemode to existing values if stat is not trusted */
 		entry->mode = index_merge_mode(index, *existing, entry->mode);
 	}
 
+	if (check_file_directory_collision(index, entry, position, replace) < 0)
+		return -1;
+
 	/* if replacing is not requested or no existing entry exists, just
 	 * insert entry at the end; the index is no longer sorted
 	 */
@@ -832,7 +952,7 @@ int git_index_remove(git_index *index, const char *path, int stage)
 
 	git_vector_sort(&index->entries);
 
-	if (git_index__find(&position, index, path, stage) < 0) {
+	if (git_index__find(&position, index, path, strlen(path), stage) < 0) {
 		giterr_set(GITERR_INDEX, "Index does not contain %s at stage %d",
 			path, stage);
 		return GIT_ENOTFOUND;
@@ -889,13 +1009,14 @@ int git_index_remove_directory(git_index *index, const char *dir, int stage)
 }
 
 int git_index__find(
-	size_t *at_pos, git_index *index, const char *path, int stage)
+	size_t *at_pos, git_index *index, const char *path, int path_len, int stage)
 {
 	struct entry_srch_key srch_key;
 
 	assert(path);
 
 	srch_key.path = path;
+	srch_key.path_len = path_len;
 	srch_key.stage = stage;
 
 	return git_vector_bsearch2(
@@ -937,6 +1058,7 @@ size_t git_index__prefix_position(git_index *index, const char *path)
 	size_t pos;
 
 	srch_key.path = path;
+	srch_key.path_len = strlen(path);
 	srch_key.stage = 0;
 
 	git_vector_sort(&index->entries);
@@ -1991,6 +2113,7 @@ static int read_tree_cb(
 		struct entry_srch_key skey;
 
 		skey.path = path.ptr;
+		skey.path_len = strlen(path.ptr);
 		skey.stage = 0;
 
 		if (!git_vector_bsearch2(
@@ -2109,7 +2232,7 @@ int git_index_add_all(
 		/* skip ignored items that are not already in the index */
 		if ((flags & GIT_INDEX_ADD_FORCE) == 0 &&
 			git_iterator_current_is_ignored(wditer) &&
-			git_index__find(&existing, index, wd->path, 0) < 0)
+			git_index__find(&existing, index, wd->path, strlen(wd->path), 0) < 0)
 			continue;
 
 		/* issue notification callback if requested */
diff --git a/src/index.h b/src/index.h
index 4c448fabf..3dea4aa14 100644
--- a/src/index.h
+++ b/src/index.h
@@ -56,7 +56,7 @@ extern int git_index_entry__cmp(const void *a, const void *b);
 extern int git_index_entry__cmp_icase(const void *a, const void *b);
 
 extern int git_index__find(
-	size_t *at_pos, git_index *index, const char *path, int stage);
+	size_t *at_pos, git_index *index, const char *path, int path_len, int stage);
 
 extern void git_index__set_ignore_case(git_index *index, bool ignore_case);
 
diff --git a/src/merge.c b/src/merge.c
index f4224955a..20cfc0e23 100644
--- a/src/merge.c
+++ b/src/merge.c
@@ -2398,12 +2398,21 @@ int git_merge__indexes(git_repository *repo, git_index *index_new)
 		goto done;
 	}
 
-	/* Update the new index */
+	/* Remove removed items from the index */
 	git_vector_foreach(&paths, i, path) {
-		if ((e = git_index_get_bypath(index_new, path, 0)) != NULL)
-			error = git_index_add(index_repo, e);
-		else
-			error = git_index_remove(index_repo, path, 0);
+		if ((e = git_index_get_bypath(index_new, path, 0)) == NULL) {
+			if ((error = git_index_remove(index_repo, path, 0)) < 0 &&
+				error != GIT_ENOTFOUND)
+				goto done;
+		}
+	}
+
+	/* Add updated items to the index */
+	git_vector_foreach(&paths, i, path) {
+		if ((e = git_index_get_bypath(index_new, path, 0)) != NULL) {
+			if ((error = git_index_add(index_repo, e)) < 0)
+				goto done;
+		}
 	}
 
 	/* Add conflicts */
diff --git a/src/pathspec.c b/src/pathspec.c
index d6ce09c02..bee320576 100644
--- a/src/pathspec.c
+++ b/src/pathspec.c
@@ -445,7 +445,7 @@ static int pathspec_match_from_iterator(
 		/* check if path is ignored and untracked */
 		if (index != NULL &&
 			git_iterator_current_is_ignored(iter) &&
-			git_index__find(NULL, index, entry->path, GIT_INDEX_STAGE_ANY) < 0)
+			git_index__find(NULL, index, entry->path, strlen(entry->path), GIT_INDEX_STAGE_ANY) < 0)
 			continue;
 
 		/* mark the matched pattern as used */
diff --git a/tests/index/collision.c b/tests/index/collision.c
new file mode 100644
index 000000000..1f002e8d3
--- /dev/null
+++ b/tests/index/collision.c
@@ -0,0 +1,106 @@
+#include "clar_libgit2.h"
+#include "git2/repository.h"
+#include "git2/index.h"
+
+git_repository *repo = NULL;
+
+void test_index_collision__cleanup(void)
+{
+	cl_git_sandbox_cleanup();
+	repo = NULL;
+}
+
+void test_index_collision__add(void)
+{
+	git_index *index;
+	git_index_entry entry;
+	git_oid tree_id;
+	git_tree *tree;
+
+	repo = cl_git_sandbox_init("empty_standard_repo");
+	cl_git_pass(git_repository_index(&index, repo));
+
+	memset(&entry, 0, sizeof(entry));
+	entry.ctime.seconds = 12346789;
+	entry.mtime.seconds = 12346789;
+	entry.mode  = 0100644;
+	entry.file_size = 0;
+	git_oid_fromstr(&entry.id, "e69de29bb2d1d6434b8b29ae775ad8c2e48c5391");
+
+	entry.path = "a/b";
+	cl_git_pass(git_index_add(index, &entry));
+
+	/* create a tree/blob collision */
+	entry.path = "a/b/c";
+	cl_git_fail(git_index_add(index, &entry));
+
+	cl_git_pass(git_index_write_tree(&tree_id, index));
+	cl_git_pass(git_tree_lookup(&tree, repo, &tree_id));
+
+	git_tree_free(tree);
+	git_index_free(index);
+}
+
+void test_index_collision__add_with_highstage_1(void)
+{
+	git_index *index;
+	git_index_entry entry;
+
+	repo = cl_git_sandbox_init("empty_standard_repo");
+	cl_git_pass(git_repository_index(&index, repo));
+
+	memset(&entry, 0, sizeof(entry));
+	entry.ctime.seconds = 12346789;
+	entry.mtime.seconds = 12346789;
+	entry.mode  = 0100644;
+	entry.file_size = 0;
+	git_oid_fromstr(&entry.id, "e69de29bb2d1d6434b8b29ae775ad8c2e48c5391");
+
+	entry.path = "a/b";
+	entry.flags = (2 << GIT_IDXENTRY_STAGESHIFT);
+	cl_git_pass(git_index_add(index, &entry));
+
+	/* create a blob beneath the previous tree entry */
+	entry.path = "a/b/c";
+	entry.flags = 0;
+	cl_git_pass(git_index_add(index, &entry));
+
+	/* create another tree entry above the blob */
+	entry.path = "a/b";
+	entry.flags = (1 << GIT_IDXENTRY_STAGESHIFT);
+	cl_git_pass(git_index_add(index, &entry));
+
+	git_index_free(index);
+}
+
+void test_index_collision__add_with_highstage_2(void)
+{
+	git_index *index;
+	git_index_entry entry;
+
+	repo = cl_git_sandbox_init("empty_standard_repo");
+	cl_git_pass(git_repository_index(&index, repo));
+
+	memset(&entry, 0, sizeof(entry));
+	entry.ctime.seconds = 12346789;
+	entry.mtime.seconds = 12346789;
+	entry.mode  = 0100644;
+	entry.file_size = 0;
+	git_oid_fromstr(&entry.id, "e69de29bb2d1d6434b8b29ae775ad8c2e48c5391");
+
+	entry.path = "a/b/c";
+	entry.flags = (1 << GIT_IDXENTRY_STAGESHIFT);
+	cl_git_pass(git_index_add(index, &entry));
+
+	/* create a blob beneath the previous tree entry */
+	entry.path = "a/b/c";
+	entry.flags = (2 << GIT_IDXENTRY_STAGESHIFT);
+	cl_git_pass(git_index_add(index, &entry));
+
+	/* create another tree entry above the blob */
+	entry.path = "a/b";
+	entry.flags = (3 << GIT_IDXENTRY_STAGESHIFT);
+	cl_git_pass(git_index_add(index, &entry));
+
+	git_index_free(index);
+}