[PATCH v4 00/34] Add directory rename detection to git

[Elijah Newren <newren@gmail.com>]

This patchset introduces directory rename detection to merge-recursive.  See
  https://public-inbox.org/git/20171110190550.27059-1-newren@gmail.com/
for the first series (including design considerations, etc.), and follow-up
series can be found at
  https://public-inbox.org/git/20171120220209.15111-1-newren@gmail.com/
  https://public-inbox.org/git/20171121080059.32304-1-newren@gmail.com/

Changes since V3:
  * Rebased on latest master (no conflicts, but figured I might as well)
  * Addressed issues mentioned in reviews of V3:
    * Fixed style issues
    * Made use of strbuf (note: new function added to strbuf.[ch] that
      takes a string_list*; is that okay?)
    * Switched strndup to xstrndup for windows
  * Miscellaneous cleanups, perf, etc.:
    * Skip pair early in get_directory_renames() if pair is not a rename
    * Add helper cleanup functions to consolidate some code
    * Make it clear that directory rename detection only operates on
      add ('A') and rename ('R') filepairs

Full tbdiff against V3:
 1: a0abcb1378 =  1: d95d5fffea Tighten and correct a few testcases for merging and cherry-picking
 2: e8745c4f1b =  2: b177dccc28 merge-recursive: fix logic ordering issue
 3: 0ae4156994 =  3: fe3de710e3 merge-recursive: add explanation for src_entry and dst_entry
 4: f13686ea6a =  4: 19b82b795a directory rename detection: basic testcases
 5: 16e7dea569 =  5: 3d23af19e9 directory rename detection: directory splitting testcases
 6: 51d9a5b059 =  6: d997681a4d directory rename detection: testcases to avoid taking detection too far
 7: 4b39f6bea3 =  7: 152e3d5d81 directory rename detection: partially renamed directory testcase/discussion
 8: 0668e65864 =  8: 441211c842 directory rename detection: files/directories in the way of some renames
 9: fcce655243 =  9: c66d3fb8b4 directory rename detection: testcases checking which side did the rename
10: 04213cc213 = 10: 4542c5fee4 directory rename detection: more involved edge/corner testcases
11: 21992300aa ! 11: 771b551982 directory rename detection: testcases exploring possibly suboptimal merges
    @@ -36,7 +36,7 @@
     +#   Optimal:                  y/{a,b,e},   z/{c,d,f}
     +#
     +# Note: Both x and y got renamed and it'd be nice to detect both, and we do
    -+# better with directory rename detection than git did previously, but the
    ++# better with directory rename detection than git did without, but the
     +# simple rule from section 5 prevents me from handling this as optimally as
     +# we potentially could.
     +
    @@ -321,9 +321,11 @@
     +#   Commit B: w/{b,c}, z/d
     +#
     +# Possible Resolutions:
    -+#   Previous git: z/d, CONFLICT(z/b -> y/b vs. w/b), CONFLICT(z/c -> y/c vs. w/c)
    -+#   Expected:     y/d, CONFLICT(z/b -> y/b vs. w/b), CONFLICT(z/c -> y/c vs. w/c)
    -+#   Preferred:    ??
    ++#   w/o dir-rename detection: z/d, CONFLICT(z/b -> y/b vs. w/b),
    ++#                                  CONFLICT(z/c -> y/c vs. w/c)
    ++#   Currently expected:       y/d, CONFLICT(z/b -> y/b vs. w/b),
    ++#                                  CONFLICT(z/c -> y/c vs. w/c)
    ++#   Optimal:                  ??
     +#
     +# Notes: In commit A, directory z got renamed to y.  In commit B, directory z
     +#        did NOT get renamed; the directory is still present; instead it is
12: 727238bf64 = 12: f1f8b2e0bc directory rename detection: miscellaneous testcases to complete coverage
13: 44b25c31e2 = 13: 595905c828 directory rename detection: tests for handling overwriting untracked files
14: fa05a0240c = 14: 71ae85d203 directory rename detection: tests for handling overwriting dirty files
15: 131af0e3f2 = 15: e9ca40cf6a merge-recursive: move the get_renames() function
16: c7d1d15bec = 16: f4ff2a3c8b merge-recursive: introduce new functions to handle rename logic
17: 1ca5c22551 = 17: 84b57b2495 merge-recursive: fix leaks of allocated renames and diff_filepairs
18: 57288cf7b1 = 18: 03c1d06592 merge-recursive: make !o->detect_rename codepath more obvious
19: fd6602a327 = 19: cf9d708f1d merge-recursive: split out code for determining diff_filepairs
20: 8828dd4093 ! 20: ed33e1221f merge-recursive: add a new hashmap for storing directory renames
    @@ -45,7 +45,7 @@
     +	hashmap_entry_init(entry, strhash(directory));
     +	entry->dir = directory;
     +	entry->non_unique_new_dir = 0;
    -+	entry->new_dir = NULL;
    ++	strbuf_init(&entry->new_dir, 0);
     +	string_list_init(&entry->possible_new_dirs, 0);
     +}
     +
    @@ -64,7 +64,7 @@
     +	struct hashmap_entry ent; /* must be the first member! */
     +	char *dir;
     +	unsigned non_unique_new_dir:1;
    -+	char *new_dir;
    ++	struct strbuf new_dir;
     +	struct string_list possible_new_dirs;
     +};
     +
--:  ------- > 21: 9b88f735c2 merge-recursive: make a helper function for cleanup for handle_renames
21: f1d3b1f7ab ! 22: 20c94136af merge-recursive: add get_directory_renames()
    @@ -63,8 +63,8 @@
     +	new_len = end_of_new - new_path;
     +
     +	if (old_len != new_len || strncmp(old_path, new_path, old_len)) {
    -+		*old_dir = strndup(old_path, old_len);
    -+		*new_dir = strndup(new_path, new_len);
    ++		*old_dir = xstrndup(old_path, old_len);
    ++		*new_dir = xstrndup(new_path, new_len);
     +	}
     +}
     +
    @@ -84,6 +84,10 @@
     +		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)
    @@ -128,9 +132,11 @@
     +		}
     +		if (bad_max == max)
     +			entry->non_unique_new_dir = 1;
    -+		else
    -+			entry->new_dir = strdup(best);
    -+		/* Strings were strndup'ed before inserting into string-list,
    ++		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;
    @@ -144,12 +150,33 @@
       * Get information of all renames which occurred in 'pairs', making use of
       * any implicit directory renames inferred from the other side of history.
     @@
    + 	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);
    + }
    +@@
      			  struct rename_info *ri)
      {
      	struct diff_queue_struct *head_pairs, *merge_pairs;
     +	struct hashmap *dir_re_head, *dir_re_merge;
    -+	struct hashmap_iter iter;
    -+	struct dir_rename_entry *e;
      	int clean;
      
      	ri->head_renames = NULL;
    @@ -164,29 +191,13 @@
      					 common, head, merge, entries);
      	ri->merge_renames = get_renames(o, merge_pairs, merge,
     @@
    + 	 * data structures are still needed and referenced in
      	 * process_entry().  But there are a few things we can free now.
      	 */
    - 
    -+	hashmap_iter_init(dir_re_head, &iter);
    -+	while ((e = hashmap_iter_next(&iter))) {
    -+		free(e->dir);
    -+		if (e->new_dir)
    -+			free(e->new_dir);
    -+		/* possible_new_dirs already cleared in get_directory_renames */
    -+	}
    -+	hashmap_free(dir_re_head, 1);
    -+	free(dir_re_head);
    -+
    -+	hashmap_iter_init(dir_re_merge, &iter);
    -+	while ((e = hashmap_iter_next(&iter))) {
    -+		free(e->dir);
    -+		if (e->new_dir)
    -+			free(e->new_dir);
    -+		/* possible_new_dirs already cleared in get_directory_renames */
    -+	}
    -+	hashmap_free(dir_re_merge, 1);
    -+	free(dir_re_merge);
    -+
    - 	free(head_pairs->queue);
    - 	free(head_pairs);
    - 	free(merge_pairs->queue);
    +-	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;
    + }
22: ba1aa81d38 ! 23: da6b0646d1 merge-recursive: check for directory level conflicts
    @@ -32,6 +32,19 @@
      	}
      }
      
    ++static void remove_hashmap_entries(struct hashmap *dir_renames,
    ++				   struct string_list *items_to_remove)
    ++{
    ++	int i;
    ++	struct dir_rename_entry *entry;
    ++
    ++	for (i = 0; i < items_to_remove->nr; i++) {
    ++		entry = items_to_remove->items[i].util;
    ++		hashmap_remove(dir_renames, entry, NULL);
    ++	}
    ++	string_list_clear(items_to_remove, 0);
    ++}
    ++
     +/*
     + * There are a couple things we want to do at the directory level:
     + *   1. Check for both sides renaming to the same thing, in order to avoid
    @@ -61,7 +74,6 @@
     +	struct hashmap_iter iter;
     +	struct dir_rename_entry *head_ent;
     +	struct dir_rename_entry *merge_ent;
    -+	int i;
     +
     +	struct string_list remove_from_head = STRING_LIST_INIT_NODUP;
     +	struct string_list remove_from_merge = STRING_LIST_INIT_NODUP;
    @@ -72,21 +84,24 @@
     +		if (merge_ent &&
     +		    !head_ent->non_unique_new_dir &&
     +		    !merge_ent->non_unique_new_dir &&
    -+		    !strcmp(head_ent->new_dir, merge_ent->new_dir)) {
    ++		    !strbuf_cmp(&head_ent->new_dir, &merge_ent->new_dir)) {
     +			/* 1. Renamed identically; remove it from both sides */
     +			string_list_append(&remove_from_head,
     +					   head_ent->dir)->util = head_ent;
    -+			free(head_ent->new_dir);
    ++			strbuf_release(&head_ent->new_dir);
     +			string_list_append(&remove_from_merge,
     +					   merge_ent->dir)->util = merge_ent;
    -+			free(merge_ent->new_dir);
    ++			strbuf_release(&merge_ent->new_dir);
     +		} else if (tree_has_path(head, head_ent->dir)) {
     +			/* 2. This wasn't a directory rename after all */
     +			string_list_append(&remove_from_head,
     +					   head_ent->dir)->util = head_ent;
    -+			free(head_ent->new_dir);
    ++			strbuf_release(&head_ent->new_dir);
     +		}
     +	}
    ++
    ++	remove_hashmap_entries(dir_re_head, &remove_from_head);
    ++	remove_hashmap_entries(dir_re_merge, &remove_from_merge);
     +
     +	hashmap_iter_init(dir_re_merge, &iter);
     +	while ((merge_ent = hashmap_iter_next(&iter))) {
    @@ -99,7 +114,8 @@
     +			   !head_ent->non_unique_new_dir &&
     +			   !merge_ent->non_unique_new_dir) {
     +			/* 3. rename/rename(1to2) */
    -+			/* We can assume it's not rename/rename(1to1) because
    ++			/*
    ++			 * We can assume it's not rename/rename(1to1) because
     +			 * that was case (1), already checked above.  So we
     +			 * know that head_ent->new_dir and merge_ent->new_dir
     +			 * are different strings.
    @@ -107,28 +123,19 @@
     +			output(o, 1, _("CONFLICT (rename/rename): "
     +				       "Rename directory %s->%s in %s. "
     +				       "Rename directory %s->%s in %s"),
    -+			       head_ent->dir, head_ent->new_dir, o->branch1,
    -+			       head_ent->dir, merge_ent->new_dir, o->branch2);
    ++			       head_ent->dir, head_ent->new_dir.buf, o->branch1,
    ++			       head_ent->dir, merge_ent->new_dir.buf, o->branch2);
     +			string_list_append(&remove_from_head,
     +					   head_ent->dir)->util = head_ent;
    -+			free(head_ent->new_dir);
    ++			strbuf_release(&head_ent->new_dir);
     +			string_list_append(&remove_from_merge,
     +					   merge_ent->dir)->util = merge_ent;
    -+			free(merge_ent->new_dir);
    ++			strbuf_release(&merge_ent->new_dir);
     +		}
     +	}
     +
    -+	for (i = 0; i < remove_from_head.nr; i++) {
    -+		head_ent = remove_from_head.items[i].util;
    -+		hashmap_remove(dir_re_head, head_ent, NULL);
    -+	}
    -+	for (i = 0; i < remove_from_merge.nr; i++) {
    -+		merge_ent = remove_from_merge.items[i].util;
    -+		hashmap_remove(dir_re_merge, merge_ent, NULL);
    -+	}
    -+
    -+	string_list_clear(&remove_from_head, 0);
    -+	string_list_clear(&remove_from_merge, 0);
    ++	remove_hashmap_entries(dir_re_head, &remove_from_head);
    ++	remove_hashmap_entries(dir_re_merge, &remove_from_merge);
     +}
     +
      static struct hashmap *get_directory_renames(struct diff_queue_struct *pairs,
23: 96534fe595 = 24: 93162a9b56 merge-recursive: add a new hashmap for storing file collisions
24: 66ada0e7c0 ! 25: 53b26a0d61 merge-recursive: add computation of collisions due to dir rename & merging
    @@ -26,20 +26,19 @@
     +static char *apply_dir_rename(struct dir_rename_entry *entry,
     +			      const char *old_path)
     +{
    -+	char *new_path;
    -+	int entrylen, oldlen, newlen;
    ++	struct strbuf new_path = STRBUF_INIT;
    ++	int oldlen, newlen;
     +
     +	if (entry->non_unique_new_dir)
     +		return NULL;
     +
    -+	entrylen = strlen(entry->new_dir);
     +	oldlen = strlen(entry->dir);
    -+	newlen = entrylen + (strlen(old_path) - oldlen) + 1;
    -+	new_path = malloc(newlen);
    -+	strcpy(new_path, entry->new_dir);
    -+	strcpy(&new_path[entrylen], &old_path[oldlen]);
    ++	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 new_path;
    ++	return strbuf_detach(&new_path, NULL);
     +}
     +
      static void get_renamed_dir_portion(const char *old_path, const char *new_path,
25: 0f49ea9449 ! 26: 26d4c78d67 merge-recursive: check for file level conflicts then get new name
    @@ -13,25 +13,9 @@
     --- a/merge-recursive.c
     +++ b/merge-recursive.c
     @@
    - 	}
    + 	string_list_clear(items_to_remove, 0);
      }
      
    -+/*
    -+ * Write:
    -+ *   element1, element2, element3, ..., elementN
    -+ * to str.  If only one element, just write "element1" to str.
    -+ */
    -+static void comma_separated_list(char *str, struct string_list *slist)
    -+{
    -+	int i;
    -+
    -+	for (i = 0; i < slist->nr; i++) {
    -+		str += sprintf(str, "%s", slist->items[i].string);
    -+		if (i < slist->nr-1)
    -+			str += sprintf(str, ", ");
    -+	}
    -+}
    -+
     +/*
     + * See if there is a directory rename for path, and if there are any file
     + * level conflicts for the renamed location.  If there is a rename and
    @@ -46,7 +30,7 @@
     +	char *new_path = NULL;
     +	struct collision_entry *collision_ent;
     +	int clean = 1;
    -+	char *collision_paths;
    ++	struct strbuf collision_paths = STRBUF_INIT;
     +
     +	/*
     +	 * entry has the mapping of old directory name to new directory name
    @@ -84,33 +68,31 @@
     +	 * to put multiple paths into the same location.  Warn
     +	 * and bail on directory renames for such paths.
     +	 */
    -+	collision_paths = malloc((PATH_MAX+2) * collision_ent->source_files.nr);
    -+
     +	if (collision_ent->reported_already) {
     +		clean = 0;
     +	} else if (tree_has_path(tree, new_path)) {
     +		collision_ent->reported_already = 1;
    -+		comma_separated_list(collision_paths,
    -+				     &collision_ent->source_files);
    ++		strbuf_add_separated_string_list(&collision_paths, ", ",
    ++						 &collision_ent->source_files);
     +		output(o, 1, _("CONFLICT (implicit dir rename): Existing "
     +			       "file/dir at %s in the way of implicit "
     +			       "directory rename(s) putting the following "
     +			       "path(s) there: %s."),
    -+		       new_path, collision_paths);
    ++		       new_path, collision_paths.buf);
     +		clean = 0;
     +	} else if (collision_ent->source_files.nr > 1) {
     +		collision_ent->reported_already = 1;
    -+		comma_separated_list(collision_paths,
    -+				     &collision_ent->source_files);
    ++		strbuf_add_separated_string_list(&collision_paths, ", ",
    ++						 &collision_ent->source_files);
     +		output(o, 1, _("CONFLICT (implicit dir rename): Cannot map "
     +			       "more than one path to %s; implicit directory "
     +			       "renames tried to put these paths there: %s"),
    -+		       new_path, collision_paths);
    ++		       new_path, collision_paths.buf);
     +		clean = 0;
     +	}
     +
     +	/* Free memory we no longer need */
    -+	free(collision_paths);
    ++	strbuf_release(&collision_paths);
     +	if (!clean && new_path) {
     +		free(new_path);
     +		return NULL;
    @@ -165,11 +147,11 @@
     +	 * As it turns out, this also prevents N-way transient rename
     +	 * confusion; See testcases 9c and 9d of t6043.
     +	 */
    -+	oentry = dir_rename_find_entry(dir_rename_exclusions, entry->new_dir);
    ++	oentry = dir_rename_find_entry(dir_rename_exclusions, entry->new_dir.buf);
     +	if (oentry) {
     +		output(o, 1, _("WARNING: Avoiding applying %s -> %s rename "
     +			       "to %s, because %s itself was renamed."),
    -+		       entry->dir, entry->new_dir, path, entry->new_dir);
    ++		       entry->dir, entry->new_dir.buf, path, entry->new_dir.buf);
     +	} else {
     +		new_path = handle_path_level_conflicts(o, path, entry,
     +						       collisions, tree);
    @@ -222,9 +204,9 @@
      		re->processed = 0;
      		re->pair = pair;
     @@
    + {
    + 	struct diff_queue_struct *head_pairs, *merge_pairs;
      	struct hashmap *dir_re_head, *dir_re_merge;
    - 	struct hashmap_iter iter;
    - 	struct dir_rename_entry *e;
     -	int clean;
     +	int clean = 1;
      
    @@ -257,6 +239,73 @@
      	 * Some cleanup is deferred until cleanup_renames() because the
      	 * data structures are still needed and referenced in
     
    +diff --git a/strbuf.c b/strbuf.c
    +--- a/strbuf.c
    ++++ b/strbuf.c
    +@@
    + #include "cache.h"
    + #include "refs.h"
    ++#include "string-list.h"
    + #include "utf8.h"
    + 
    + int starts_with(const char *str, const char *prefix)
    +@@
    + 	return ret;
    + }
    + 
    ++void strbuf_add_separated_string_list(struct strbuf *str,
    ++				      const char *sep,
    ++				      struct string_list *slist)
    ++{
    ++	struct string_list_item *item;
    ++	int sep_needed = 0;
    ++
    ++	for_each_string_list_item(item, slist) {
    ++		if (sep_needed)
    ++			strbuf_addstr(str, sep);
    ++		strbuf_addstr(str, item->string);
    ++		sep_needed = 1;
    ++	}
    ++}
    ++
    + void strbuf_list_free(struct strbuf **sbs)
    + {
    + 	struct strbuf **s = sbs;
    +
    +diff --git a/strbuf.h b/strbuf.h
    +--- a/strbuf.h
    ++++ b/strbuf.h
    +@@
    + #ifndef STRBUF_H
    + #define STRBUF_H
    + 
    ++struct string_list;
    ++
    + /**
    +  * strbuf's are meant to be used with all the usual C string and memory
    +  * APIs. Given that the length of the buffer is known, it's often better to
    +@@
    + 	return strbuf_split_max(sb, terminator, 0);
    + }
    + 
    ++/*
    ++ * Adds all strings of a string list to the strbuf, separated by the given
    ++ * separator.  For example, if sep is
    ++ *   ', '
    ++ * and slist contains
    ++ *   ['element1', 'element2', ..., 'elementN'],
    ++ * then write:
    ++ *   'element1, element2, ..., elementN'
    ++ * to str.  If only one element, just write "element1" to str.
    ++ */
    ++extern void strbuf_add_separated_string_list(struct strbuf *str,
    ++					     const char *sep,
    ++					     struct string_list *slist);
    ++
    + /**
    +  * Free a NULL-terminated list of strbufs (for example, the return
    +  * values of the strbuf_split*() functions).
    +
     diff --git a/t/t6043-merge-rename-directories.sh b/t/t6043-merge-rename-directories.sh
     --- a/t/t6043-merge-rename-directories.sh
     +++ b/t/t6043-merge-rename-directories.sh
26: 996de01e67 = 27: 0bbb741e1d merge-recursive: when comparing files, don't include trees
27: 07401ad0ff = 28: 6c398f0278 merge-recursive: apply necessary modifications for directory renames
28: fafa66de08 = 29: 4de6b08124 merge-recursive: avoid clobbering untracked files with directory renames
29: 9ab0339ebb = 30: b710627ca6 merge-recursive: fix overwriting dirty files involved in renames
30: feb4781c7a = 31: 7f56715998 merge-recursive: fix remaining directory rename + dirty overwrite cases
31: 29975384e0 = 32: a51698e630 directory rename detection: new testcases showcasing a pair of bugs
32: b084ea16ac ! 33: c27b89922e merge-recursive: avoid spurious rename/rename conflict from dir renames
    @@ -21,7 +21,7 @@
      		struct diff_filepair *pair = pairs->queue[i];
      
     -		if (pair->status == 'D')
    -+		if (pair->status == 'D' || pair->status == 'M')
    ++		if (pair->status != 'A' && pair->status != 'R')
      			continue;
      		dir_rename_ent = check_dir_renamed(pair->two->path,
      						   dir_renames);
    @@ -30,7 +30,7 @@
      		char *new_path; /* non-NULL only with directory renames */
      
     -		if (pair->status == 'D') {
    -+		if (pair->status == 'D' || pair->status == 'M') {
    ++		if (pair->status != 'A' && pair->status != 'R') {
      			diff_free_filepair(pair);
      			continue;
      		}
33: 62ce55426d = 34: 850bc54b15 merge-recursive: ensure we write updates for directory-renamed file

Elijah Newren (34):
  Tighten and correct a few testcases for merging and cherry-picking
  merge-recursive: fix logic ordering issue
  merge-recursive: add explanation for src_entry and dst_entry
  directory rename detection: basic testcases
  directory rename detection: directory splitting testcases
  directory rename detection: testcases to avoid taking detection too
    far
  directory rename detection: partially renamed directory
    testcase/discussion
  directory rename detection: files/directories in the way of some
    renames
  directory rename detection: testcases checking which side did the
    rename
  directory rename detection: more involved edge/corner testcases
  directory rename detection: testcases exploring possibly suboptimal
    merges
  directory rename detection: miscellaneous testcases to complete
    coverage
  directory rename detection: tests for handling overwriting untracked
    files
  directory rename detection: tests for handling overwriting dirty files
  merge-recursive: move the get_renames() function
  merge-recursive: introduce new functions to handle rename logic
  merge-recursive: fix leaks of allocated renames and diff_filepairs
  merge-recursive: make !o->detect_rename codepath more obvious
  merge-recursive: split out code for determining diff_filepairs
  merge-recursive: add a new hashmap for storing directory renames
  merge-recursive: make a helper function for cleanup for handle_renames
  merge-recursive: add get_directory_renames()
  merge-recursive: check for directory level conflicts
  merge-recursive: add a new hashmap for storing file collisions
  merge-recursive: add computation of collisions due to dir rename &
    merging
  merge-recursive: check for file level conflicts then get new name
  merge-recursive: when comparing files, don't include trees
  merge-recursive: apply necessary modifications for directory renames
  merge-recursive: avoid clobbering untracked files with directory
    renames
  merge-recursive: fix overwriting dirty files involved in renames
  merge-recursive: fix remaining directory rename + dirty overwrite
    cases
  directory rename detection: new testcases showcasing a pair of bugs
  merge-recursive: avoid spurious rename/rename conflict from dir
    renames
  merge-recursive: ensure we write updates for directory-renamed file

 merge-recursive.c                   | 1231 ++++++++++-
 merge-recursive.h                   |   17 +
 strbuf.c                            |   16 +
 strbuf.h                            |   16 +
 t/t3501-revert-cherry-pick.sh       |    5 +-
 t/t6043-merge-rename-directories.sh | 3823 +++++++++++++++++++++++++++++++++++
 t/t7607-merge-overwrite.sh          |    7 +-
 unpack-trees.c                      |    4 +-
 unpack-trees.h                      |    4 +
 9 files changed, 5007 insertions(+), 116 deletions(-)
 create mode 100755 t/t6043-merge-rename-directories.sh

-- 
2.15.0.408.g850bc54b15