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

[PATCH v5 22/34] merge-recursive: add get_directory_renames()

From
Elijah Newren <newren@gmail.com>
Date
Dec 28, 2017, 04:13 UTC
Message-ID
<20171228041352.27880-23-newren@gmail.com>
In-Reply-To
<20171228041352.27880-1-newren@gmail.com>

This populates a list of directory renames for us. The list of directory renames is not yet used, but will be in subsequent commits.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 merge-recursive.c | 155 ++++++++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 152 insertions(+), 3 deletions(-)
diff --git a/merge-recursive.c b/merge-recursive.c
index c5932d5c5..6aef357e7 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -1384,6 +1384,138 @@ static struct diff_queue_struct *get_diffpairs(struct merge_options *o,
 	return ret;
 }
 
+static void get_renamed_dir_portion(const char *old_path, const char *new_path,
+				    char **old_dir, char **new_dir)
+{
+	char *end_of_old, *end_of_new;
+	int old_len, new_len;
+
+	*old_dir = NULL;
+	*new_dir = NULL;
+
+	/* For
+	 *    "a/b/c/d/foo.c" -> "a/b/something-else/d/foo.c"
+	 * the "d/foo.c" part is the same, we just want to know that
+	 *    "a/b/c" was renamed to "a/b/something-else"
+	 * so, for this example, this function returns "a/b/c" in
+	 * *old_dir and "a/b/something-else" in *new_dir.
+	 *
+	 * Also, if the basename of the file changed, we don't care.  We
+	 * want to know which portion of the directory, if any, changed.
+	 */
+	end_of_old = strrchr(old_path, '/');
+	end_of_new = strrchr(new_path, '/');
+
+	if (end_of_old == NULL || end_of_new == NULL)
+		return;
+	while (*--end_of_new == *--end_of_old &&
+	       end_of_old != old_path &&
+	       end_of_new != new_path)
+		; /* Do nothing; all in the while loop */
+	/*
+	 * We've found the first non-matching character in the directory
+	 * paths.  That means the current directory we were comparing
+	 * represents the rename.  Move end_of_old and end_of_new back
+	 * to the full directory name.
+	 */
+	if (*end_of_old == '/')
+		end_of_old++;
+	if (*end_of_old != '/')
+		end_of_new++;
+	end_of_old = strchr(end_of_old, '/');
+	end_of_new = strchr(end_of_new, '/');
+
+	/*
+	 * It may have been the case that old_path and new_path were the same
+	 * directory all along.  Don't claim a rename if they're the same.
+	 */
+	old_len = end_of_old - old_path;
+	new_len = end_of_new - new_path;
+
+	if (old_len != new_len || strncmp(old_path, new_path, old_len)) {
+		*old_dir = xstrndup(old_path, old_len);
+		*new_dir = xstrndup(new_path, new_len);
+	}
+}
+
+static struct hashmap *get_directory_renames(struct diff_queue_struct *pairs,
+					     struct tree *tree)
+{
+	struct hashmap *dir_renames;
+	struct hashmap_iter iter;
+	struct dir_rename_entry *entry;
+	int i;
+
+	dir_renames = malloc(sizeof(struct hashmap));
+	dir_rename_init(dir_renames);
+	for (i = 0; i < pairs->nr; ++i) {
+		struct string_list_item *item;
+		int *count;
+		struct diff_filepair *pair = pairs->queue[i];
+		char *old_dir, *new_dir;
+
+		/* File not part of directory rename if it wasn't renamed */
+		if (pair->status != 'R')
+			continue;
+
+		get_renamed_dir_portion(pair->one->path, pair->two->path,
+					&old_dir,        &new_dir);
+		if (!old_dir)
+			/* Directory didn't change at all; ignore this one. */
+			continue;
+
+		entry = dir_rename_find_entry(dir_renames, old_dir);
+		if (!entry) {
+			entry = xmalloc(sizeof(struct dir_rename_entry));
+			dir_rename_entry_init(entry, old_dir);
+			hashmap_put(dir_renames, entry);
+		} else {
+			free(old_dir);
+		}
+		item = string_list_lookup(&entry->possible_new_dirs, new_dir);
+		if (!item) {
+			item = string_list_insert(&entry->possible_new_dirs,
+						  new_dir);
+			item->util = xcalloc(1, sizeof(int));
+		} else {
+			free(new_dir);
+		}
+		count = item->util;
+		*count += 1;
+	}
+
+	hashmap_iter_init(dir_renames, &iter);
+	while ((entry = hashmap_iter_next(&iter))) {
+		int max = 0;
+		int bad_max = 0;
+		char *best = NULL;
+
+		for (i = 0; i < entry->possible_new_dirs.nr; i++) {
+			int *count = entry->possible_new_dirs.items[i].util;
+
+			if (*count == max)
+				bad_max = max;
+			else if (*count > max) {
+				max = *count;
+				best = entry->possible_new_dirs.items[i].string;
+			}
+		}
+		if (bad_max == max)
+			entry->non_unique_new_dir = 1;
+		else {
+			assert(entry->new_dir.len == 0);
+			strbuf_addstr(&entry->new_dir, best);
+		}
+		/* Strings were xstrndup'ed before inserting into string-list,
+		 * so ask string_list to remove the entries for us.
+		 */
+		entry->possible_new_dirs.strdup_strings = 1;
+		string_list_clear(&entry->possible_new_dirs, 1);
+	}
+
+	return dir_renames;
+}
+
 /*
  * Get information of all renames which occurred in 'pairs', making use of
  * any implicit directory renames inferred from the other side of history.
@@ -1695,8 +1827,21 @@ struct rename_info {
 	struct string_list *merge_renames;
 };
 
-static void initial_cleanup_rename(struct diff_queue_struct *pairs)
+static void initial_cleanup_rename(struct diff_queue_struct *pairs,
+				   struct hashmap *dir_renames)
 {
+	struct hashmap_iter iter;
+	struct dir_rename_entry *e;
+
+	hashmap_iter_init(dir_renames, &iter);
+	while ((e = hashmap_iter_next(&iter))) {
+		free(e->dir);
+		strbuf_release(&e->new_dir);
+		/* possible_new_dirs already cleared in get_directory_renames */
+	}
+	hashmap_free(dir_renames, 1);
+	free(dir_renames);
+
 	free(pairs->queue);
 	free(pairs);
 }
@@ -1709,6 +1854,7 @@ static int handle_renames(struct merge_options *o,
 			  struct rename_info *ri)
 {
 	struct diff_queue_struct *head_pairs, *merge_pairs;
+	struct hashmap *dir_re_head, *dir_re_merge;
 	int clean;
 
 	ri->head_renames = NULL;
@@ -1720,6 +1866,9 @@ static int handle_renames(struct merge_options *o,
 	head_pairs = get_diffpairs(o, common, head);
 	merge_pairs = get_diffpairs(o, common, merge);
 
+	dir_re_head = get_directory_renames(head_pairs, head);
+	dir_re_merge = get_directory_renames(merge_pairs, merge);
+
 	ri->head_renames  = get_renames(o, head_pairs, head,
 					 common, head, merge, entries);
 	ri->merge_renames = get_renames(o, merge_pairs, merge,
@@ -1731,8 +1880,8 @@ static int handle_renames(struct merge_options *o,
 	 * data structures are still needed and referenced in
 	 * process_entry().  But there are a few things we can free now.
 	 */
-	initial_cleanup_rename(head_pairs);
-	initial_cleanup_rename(merge_pairs);
+	initial_cleanup_rename(head_pairs, dir_re_head);
+	initial_cleanup_rename(merge_pairs, dir_re_merge);
 
 	return clean;
 }

-- 
2.15.0.408.g8e199d483
Previous: Elijah NewrenNext: Elijah Newren
Message 12 of 46 in “Add directory rename detection to git”
  1. 00/34 Add directory rename detection to gitElijah Newren, Dec 28, 2017
  2. 03/34 merge-recursive: add explanation for src_entry and dst_entryElijah Newren, Dec 28, 2017
  3. 04/34 directory rename detection: basic testcasesElijah Newren, Dec 28, 2017
  4. SZEDER GáborJan 3, 2018
  5. Elijah NewrenJan 3, 2018
  6. 07/34 directory rename detection: partially renamed directory testcase/discussionElijah Newren, Dec 28, 2017
  7. 08/34 directory rename detection: files/directories in the way of some renamesElijah Newren, Dec 28, 2017
  8. 14/34 directory rename detection: tests for handling overwriting dirty filesElijah Newren, Dec 28, 2017
  9. 10/34 directory rename detection: more involved edge/corner testcasesElijah Newren, Dec 28, 2017
  10. 11/34 directory rename detection: testcases exploring possibly suboptimal mergesElijah Newren, Dec 28, 2017
  11. 19/34 merge-recursive: split out code for determining diff_filepairsElijah Newren, Dec 28, 2017
  12. 22/34 merge-recursive: add get_directory_renames()Elijah Newren, Dec 28, 2017
  13. 28/34 merge-recursive: apply necessary modifications for directory renamesElijah Newren, Dec 28, 2017
  14. 29/34 merge-recursive: avoid clobbering untracked files with directory renamesElijah Newren, Dec 28, 2017
  15. 32/34 directory rename detection: new testcases showcasing a pair of bugsElijah Newren, Dec 28, 2017
  16. 30/34 merge-recursive: fix overwriting dirty files involved in renamesElijah Newren, Dec 28, 2017
  17. 31/34 merge-recursive: fix remaining directory rename + dirty overwrite casesElijah Newren, Dec 28, 2017
  18. 34/34 merge-recursive: ensure we write updates for directory-renamed fileElijah Newren, Dec 28, 2017
  19. 33/34 merge-recursive: avoid spurious rename/rename conflict from dir renamesElijah Newren, Dec 28, 2017
  20. 23/34 merge-recursive: check for directory level conflictsElijah Newren, Dec 28, 2017
  21. 26/34 merge-recursive: check for file level conflicts then get new nameElijah Newren, Dec 28, 2017
  22. 25/34 merge-recursive: add computation of collisions due to dir rename & mergingElijah Newren, Dec 28, 2017
  23. 21/34 merge-recursive: make a helper function for cleanup for handle_renamesElijah Newren, Dec 28, 2017
  24. 20/34 merge-recursive: add a new hashmap for storing directory renamesElijah Newren, Dec 28, 2017
  25. 24/34 merge-recursive: add a new hashmap for storing file collisionsElijah Newren, Dec 28, 2017
  26. 27/34 merge-recursive: when comparing files, don't include treesElijah Newren, Dec 28, 2017
  27. 12/34 directory rename detection: miscellaneous testcases to complete coverageElijah Newren, Dec 28, 2017
  28. 18/34 merge-recursive: make !o->detect_rename codepath more obviousElijah Newren, Dec 28, 2017
  29. 16/34 merge-recursive: introduce new functions to handle rename logicElijah Newren, Dec 28, 2017
  30. 17/34 merge-recursive: fix leaks of allocated renames and diff_filepairsElijah Newren, Dec 28, 2017
  31. 13/34 directory rename detection: tests for handling overwriting untracked filesElijah Newren, Dec 28, 2017
  32. SZEDER GáborJan 4, 2018
  33. Elijah NewrenJan 4, 2018
  34. SZEDER GáborJan 5, 2018
  35. Thomas GummererJan 5, 2018
  36. Elijah NewrenJan 5, 2018
  37. 15/34 merge-recursive: move the get_renames() functionElijah Newren, Dec 28, 2017
  38. 09/34 directory rename detection: testcases checking which side did the renameElijah Newren, Dec 28, 2017
  39. 02/34 merge-recursive: fix logic ordering issueElijah Newren, Dec 28, 2017
  40. 06/34 directory rename detection: testcases to avoid taking detection too farElijah Newren, Dec 28, 2017
  41. 01/34 Tighten and correct a few testcases for merging and cherry-pickingElijah Newren, Dec 28, 2017
  42. 05/34 directory rename detection: directory splitting testcasesElijah Newren, Dec 28, 2017
  43. Elijah NewrenJan 3, 2018
  44. Johannes SixtJan 3, 2018
  45. Elijah NewrenJan 3, 2018
  46. Johannes SixtJan 3, 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.