git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[PATCH v8 20/29] merge-recursive: add computation of collisions due to dir rename & merging

From
Elijah Newren <newren@gmail.com>
Date
Feb 14, 2018, 18:51 UTC
Message-ID
<20180214185206.15492-21-newren@gmail.com>
In-Reply-To
<20180214185206.15492-1-newren@gmail.com>

directory renaming and merging can cause one or more files to be moved to where an existing file is, or to cause several files to all be moved to the same (otherwise vacant) location. Add checking and reporting for such cases, falling back to no-directory-rename handling for such paths.

Reviewed-by: Stefan Beller <sbeller@google.com>
Signed-off-by: Elijah Newren <newren@gmail.com>
---
 merge-recursive.c | 146 ++++++++++++++++++++++++++++++++++++++++++++++++++++--
 merge-recursive.h |   7 +++
 2 files changed, 150 insertions(+), 3 deletions(-)
diff --git a/merge-recursive.c b/merge-recursive.c
index a9f1579d22..92f0d62f60 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -87,6 +87,29 @@ static void dir_rename_entry_init(struct dir_rename_entry *entry,
 	string_list_init(&entry->possible_new_dirs, 0);
 }
 
+static struct collision_entry *collision_find_entry(struct hashmap *hashmap,
+						    char *target_file)
+{
+	struct collision_entry key;
+
+	hashmap_entry_init(&key, strhash(target_file));
+	key.target_file = target_file;
+	return hashmap_get(hashmap, &key, NULL);
+}
+
+static int collision_cmp(void *unused_cmp_data,
+			 const struct collision_entry *e1,
+			 const struct collision_entry *e2,
+			 const void *unused_keydata)
+{
+	return strcmp(e1->target_file, e2->target_file);
+}
+
+static void collision_init(struct hashmap *map)
+{
+	hashmap_init(map, (hashmap_cmp_fn) collision_cmp, NULL, 0);
+}
+
 static void flush_output(struct merge_options *o)
 {
 	if (o->buffer_output < 2 && o->obuf.len) {
@@ -1403,6 +1426,31 @@ static int tree_has_path(struct tree *tree, const char *path)
 			       hashy, &mode_o);
 }
 
+/*
+ * Return a new string that replaces the beginning portion (which matches
+ * entry->dir), with entry->new_dir.  In perl-speak:
+ *   new_path_name = (old_path =~ s/entry->dir/entry->new_dir/);
+ * NOTE:
+ *   Caller must ensure that old_path starts with entry->dir + '/'.
+ */
+static char *apply_dir_rename(struct dir_rename_entry *entry,
+			      const char *old_path)
+{
+	struct strbuf new_path = STRBUF_INIT;
+	int oldlen, newlen;
+
+	if (entry->non_unique_new_dir)
+		return NULL;
+
+	oldlen = strlen(entry->dir);
+	newlen = entry->new_dir.len + (strlen(old_path) - oldlen) + 1;
+	strbuf_grow(&new_path, newlen);
+	strbuf_addbuf(&new_path, &entry->new_dir);
+	strbuf_addstr(&new_path, &old_path[oldlen]);
+
+	return strbuf_detach(&new_path, NULL);
+}
+
 static void get_renamed_dir_portion(const char *old_path, const char *new_path,
 				    char **old_dir, char **new_dir)
 {
@@ -1672,6 +1720,84 @@ static struct hashmap *get_directory_renames(struct diff_queue_struct *pairs,
 	return dir_renames;
 }
 
+static struct dir_rename_entry *check_dir_renamed(const char *path,
+						  struct hashmap *dir_renames)
+{
+	char temp[PATH_MAX];
+	char *end;
+	struct dir_rename_entry *entry;
+
+	strcpy(temp, path);
+	while ((end = strrchr(temp, '/'))) {
+		*end = '\0';
+		entry = dir_rename_find_entry(dir_renames, temp);
+		if (entry)
+			return entry;
+	}
+	return NULL;
+}
+
+static void compute_collisions(struct hashmap *collisions,
+			       struct hashmap *dir_renames,
+			       struct diff_queue_struct *pairs)
+{
+	int i;
+
+	/*
+	 * Multiple files can be mapped to the same path due to directory
+	 * renames done by the other side of history.  Since that other
+	 * side of history could have merged multiple directories into one,
+	 * if our side of history added the same file basename to each of
+	 * those directories, then all N of them would get implicitly
+	 * renamed by the directory rename detection into the same path,
+	 * and we'd get an add/add/.../add conflict, and all those adds
+	 * from *this* side of history.  This is not representable in the
+	 * index, and users aren't going to easily be able to make sense of
+	 * it.  So we need to provide a good warning about what's
+	 * happening, and fall back to no-directory-rename detection
+	 * behavior for those paths.
+	 *
+	 * See testcases 9e and all of section 5 from t6043 for examples.
+	 */
+	collision_init(collisions);
+
+	for (i = 0; i < pairs->nr; ++i) {
+		struct dir_rename_entry *dir_rename_ent;
+		struct collision_entry *collision_ent;
+		char *new_path;
+		struct diff_filepair *pair = pairs->queue[i];
+
+		if (pair->status == 'D')
+			continue;
+		dir_rename_ent = check_dir_renamed(pair->two->path,
+						   dir_renames);
+		if (!dir_rename_ent)
+			continue;
+
+		new_path = apply_dir_rename(dir_rename_ent, pair->two->path);
+		if (!new_path)
+			/*
+			 * dir_rename_ent->non_unique_new_path is true, which
+			 * means there is no directory rename for us to use,
+			 * which means it won't cause us any additional
+			 * collisions.
+			 */
+			continue;
+		collision_ent = collision_find_entry(collisions, new_path);
+		if (!collision_ent) {
+			collision_ent = xcalloc(1,
+						sizeof(struct collision_entry));
+			hashmap_entry_init(collision_ent, strhash(new_path));
+			hashmap_put(collisions, collision_ent);
+			collision_ent->target_file = new_path;
+		} else {
+			free(new_path);
+		}
+		string_list_insert(&collision_ent->source_files,
+				   pair->two->path);
+	}
+}
+
 /*
  * Get information of all renames which occurred in 'pairs', making use of
  * any implicit directory renames inferred from the other side of history.
@@ -1681,6 +1807,7 @@ static struct hashmap *get_directory_renames(struct diff_queue_struct *pairs,
  */
 static struct string_list *get_renames(struct merge_options *o,
 				       struct diff_queue_struct *pairs,
+				       struct hashmap *dir_renames,
 				       struct tree *tree,
 				       struct tree *o_tree,
 				       struct tree *a_tree,
@@ -1688,8 +1815,12 @@ static struct string_list *get_renames(struct merge_options *o,
 				       struct string_list *entries)
 {
 	int i;
+	struct hashmap collisions;
+	struct hashmap_iter iter;
+	struct collision_entry *e;
 	struct string_list *renames;
 
+	compute_collisions(&collisions, dir_renames, pairs);
 	renames = xcalloc(1, sizeof(struct string_list));
 
 	for (i = 0; i < pairs->nr; ++i) {
@@ -1720,6 +1851,13 @@ static struct string_list *get_renames(struct merge_options *o,
 		item = string_list_insert(renames, pair->one->path);
 		item->util = re;
 	}
+
+	hashmap_iter_init(&collisions, &iter);
+	while ((e = hashmap_iter_next(&iter))) {
+		free(e->target_file);
+		string_list_clear(&e->source_files, 0);
+	}
+	hashmap_free(&collisions, 1);
 	return renames;
 }
 
@@ -2029,9 +2167,11 @@ static int handle_renames(struct merge_options *o,
 					 dir_re_head, head,
 					 dir_re_merge, merge);
 
-	ri->head_renames  = get_renames(o, head_pairs, head,
-					 common, head, merge, entries);
-	ri->merge_renames = get_renames(o, merge_pairs, merge,
+	ri->head_renames  = get_renames(o, head_pairs,
+					dir_re_merge, head,
+					common, head, merge, entries);
+	ri->merge_renames = get_renames(o, merge_pairs,
+					dir_re_head, merge,
 					 common, head, merge, entries);
 	clean = process_renames(o, ri->head_renames, ri->merge_renames);
 
diff --git a/merge-recursive.h b/merge-recursive.h
index fe64c78de4..50a4e6af4e 100644
--- a/merge-recursive.h
+++ b/merge-recursive.h
@@ -47,6 +47,13 @@ struct dir_rename_entry {
 	struct string_list possible_new_dirs;
 };
 
+struct collision_entry {
+	struct hashmap_entry ent; /* must be the first member! */
+	char *target_file;
+	struct string_list source_files;
+	unsigned reported_already:1;
+};
+
 /* merge_trees() but with recursive ancestor consolidation */
 int merge_recursive(struct merge_options *o,
 		    struct commit *h1,

-- 
2.16.1.232.g28d5be9217
Previous: Elijah NewrenNext: Elijah Newren
Message 24 of 31 in “Add directory rename detection to git”
  1. 00/29 Add directory rename detection to gitElijah Newren, Feb 14, 2018
  2. 02/29 directory rename detection: directory splitting testcasesElijah Newren, Feb 14, 2018
  3. 17/29 merge-recursive: make a helper function for cleanup for handle_renamesElijah Newren, Feb 14, 2018
  4. 26/29 merge-recursive: fix remaining directory rename + dirty overwrite casesElijah Newren, Feb 14, 2018
  5. 19/29 merge-recursive: check for directory level conflictsElijah Newren, Feb 14, 2018
  6. 18/29 merge-recursive: add get_directory_renames()Elijah Newren, Feb 14, 2018
  7. 05/29 directory rename detection: files/directories in the way of some renamesElijah Newren, Feb 14, 2018
  8. 09/29 directory rename detection: miscellaneous testcases to complete coverageElijah Newren, Feb 14, 2018
  9. 16/29 merge-recursive: split out code for determining diff_filepairsElijah Newren, Feb 14, 2018
  10. 12/29 merge-recursive: move the get_renames() functionElijah Newren, Feb 14, 2018
  11. 15/29 merge-recursive: make !o->detect_rename codepath more obviousElijah Newren, Feb 14, 2018
  12. 11/29 directory rename detection: tests for handling overwriting dirty filesElijah Newren, Feb 14, 2018
  13. 04/29 directory rename detection: partially renamed directory testcase/discussionElijah Newren, Feb 14, 2018
  14. 01/29 directory rename detection: basic testcasesElijah Newren, Feb 14, 2018
  15. 06/29 directory rename detection: testcases checking which side did the renameElijah Newren, Feb 14, 2018
  16. 29/29 merge-recursive: ensure we write updates for directory-renamed fileElijah Newren, Feb 14, 2018
  17. 22/29 merge-recursive: when comparing files, don't include treesElijah Newren, Feb 14, 2018
  18. 03/29 directory rename detection: testcases to avoid taking detection too farElijah Newren, Feb 14, 2018
  19. 07/29 directory rename detection: more involved edge/corner testcasesElijah Newren, Feb 14, 2018
  20. 13/29 merge-recursive: introduce new functions to handle rename logicElijah Newren, Feb 14, 2018
  21. 23/29 merge-recursive: apply necessary modifications for directory renamesElijah Newren, Feb 14, 2018
  22. 24/29 merge-recursive: avoid clobbering untracked files with directory renamesElijah Newren, Feb 14, 2018
  23. 14/29 merge-recursive: fix leaks of allocated renames and diff_filepairsElijah Newren, Feb 14, 2018
  24. 20/29 merge-recursive: add computation of collisions due to dir rename & mergingElijah Newren, Feb 14, 2018
  25. 27/29 directory rename detection: new testcases showcasing a pair of bugsElijah Newren, Feb 14, 2018
  26. 08/29 directory rename detection: testcases exploring possibly suboptimal mergesElijah Newren, Feb 14, 2018
  27. 28/29 merge-recursive: avoid spurious rename/rename conflict from dir renamesElijah Newren, Feb 14, 2018
  28. 25/29 merge-recursive: fix overwriting dirty files involved in renamesElijah Newren, Feb 14, 2018
  29. 10/29 directory rename detection: tests for handling overwriting untracked filesElijah Newren, Feb 14, 2018
  30. 21/29 merge-recursive: check for file level conflicts then get new nameElijah Newren, Feb 14, 2018
  31. Stefan BellerFeb 14, 2018

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.