[PATCH v3 00/17] Add directory rename detection to merge-ort

This series depends on a merge of en/merge-ort-3 (en/merge-ort-recursive has since merged to master and need not be listed as a dependent series anymore).

This series mostly implements directory rename detection for merge-ort; ; I'll cover the "mostly" bit below. If one merges this series with en/ort-conflict-handling, then this series drops the number of failing tests in the testsuite under GIT_TEST_MERGE_ALGORITHM=ort from 60 down to 8.

As noted in the earlier submissions, most all the logic is copied from merge-recursive.c, with numerous but minor modifications due to differences in data structures. The final patch, however, is new and fixes a known bug in merge-recursive (showcased by testcase 12f of t6423).

Changes since v2:

 * numerous small fixups highlighted by Taylor in his reviews

Elijah Newren (17):
  merge-ort: add new data structures for directory rename detection
  merge-ort: initialize and free new directory rename data structures
  merge-ort: collect which directories are removed in dirs_removed
  merge-ort: add outline for computing directory renames
  merge-ort: add outline of get_provisional_directory_renames()
  merge-ort: copy get_renamed_dir_portion() from merge-recursive.c
  merge-ort: implement compute_rename_counts()
  merge-ort: implement handle_directory_level_conflicts()
  merge-ort: modify collect_renames() for directory rename handling
  merge-ort: implement compute_collisions()
  merge-ort: implement apply_dir_rename() and check_dir_renamed()
  merge-ort: implement check_for_directory_rename()
  merge-ort: implement handle_path_level_conflicts()
  merge-ort: add a new toplevel_dir field
  merge-ort: implement apply_directory_rename_modifications()
  merge-ort: process_renames() now needs more defensiveness
  merge-ort: fix a directory rename detection bug

 merge-ort.c | 830 ++++++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 811 insertions(+), 19 deletions(-)

base-commit: 8f894b22636d5d0cdfca0ae5fd88d327cc3349b3
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-835%2Fnewren%2Fort-directory-renames-v3
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-835/newren/ort-directory-renames-v3
Pull-Request: https://github.com/gitgitgadget/git/pull/835

Range-diff vs v2:

  1:  41a99640cc5 =  1:  3b14afd4129 merge-ort: add new data structures for directory rename detection
  2:  762151802be =  2:  9da04816c3b merge-ort: initialize and free new directory rename data structures
  3:  bb4b6d20480 =  3:  3061a6ae69c merge-ort: collect which directories are removed in dirs_removed
  4:  ccb30dfc3c4 !  4:  0dd6e83d2b0 merge-ort: add outline for computing directory renames
     @@ merge-ort.c: static int detect_and_process_renames(struct merge_options *opt,
      +	   opt->detect_directory_renames == MERGE_DIRECTORY_RENAMES_CONFLICT);
      +
      +	if (need_dir_renames) {
     -+		for (s = MERGE_SIDE1; s <= MERGE_SIDE2; s++)
     -+			get_provisional_directory_renames(opt, s, &clean);
     ++		get_provisional_directory_renames(opt, MERGE_SIDE1, &clean);
     ++		get_provisional_directory_renames(opt, MERGE_SIDE2, &clean);
      +		handle_directory_level_conflicts(opt);
      +	}
      +
  5:  bb4285250cd !  5:  b008ba35712 merge-ort: add outline of get_provisional_directory_renames()
     @@ merge-ort.c: static int handle_content_merge(struct merge_options *opt,
      +			}
      +		}
      +
     -+		if (max == 0)
     -+			continue;
     -+
      +		if (bad_max == max) {
      +			path_msg(opt, source_dir, 0,
      +			       _("CONFLICT (directory rename split): "
     @@ merge-ort.c: static int handle_content_merge(struct merge_options *opt,
      +				 "no destination getting a majority of the "
      +				 "files."),
      +			       source_dir);
     -+			*clean &= 0;
     ++			*clean = 0;
      +		} else {
      +			strmap_put(&renames->dir_renames[side],
      +				   source_dir, (void*)best);
  6:  4e79a96ba1c =  6:  54c18505706 merge-ort: copy get_renamed_dir_portion() from merge-recursive.c
  7:  1e48cde01b9 !  7:  5b5c8368174 merge-ort: implement compute_rename_counts()
     @@ Commit message
          merge-ort: implement compute_rename_counts()
      
          This function is based on the first half of get_directory_renames() from
     -    merge-recursive.c
     +    merge-recursive.c; as part of the implementation, factor out a routine,
     +    increment_count(), to update the bookkeeping to track the number of
     +    items renamed into new directories.
      
          Signed-off-by: Elijah Newren <newren@gmail.com>
      
     @@ merge-ort.c: static void get_renamed_dir_portion(const char *old_path, const cha
      +		char *old_dir, *new_dir;
      +		struct diff_filepair *pair = pairs->queue[i];
      +
     ++		/* File not part of directory rename if it wasn't renamed */
      +		if (pair->status != 'R')
      +			continue;
      +
  8:  f6efa4350d6 !  8:  cafff61893a merge-ort: implement handle_directory_level_conflicts()
     @@ Commit message
          This is modelled on the version of handle_directory_level_conflicts()
          from merge-recursive.c, but is massively simplified due to the following
          factors:
     -      * strmap API provides simplifications over using direct hashamp
     +      * strmap API provides simplifications over using direct hashmap
            * we have a dirs_removed field in struct rename_info that we have an
              easy way to populate from collect_merge_info(); this was already
              used in compute_rename_counts() and thus we do not need to check
     @@ merge-ort.c: static void get_provisional_directory_renames(struct merge_options
      +	struct hashmap_iter iter;
      +	struct strmap_entry *entry;
      +	struct string_list duplicated = STRING_LIST_INIT_NODUP;
     -+	struct strmap *side1_dir_renames = &opt->priv->renames.dir_renames[1];
     -+	struct strmap *side2_dir_renames = &opt->priv->renames.dir_renames[2];
     ++	struct rename_info *renames = &opt->priv->renames;
     ++	struct strmap *side1_dir_renames = &renames->dir_renames[MERGE_SIDE1];
     ++	struct strmap *side2_dir_renames = &renames->dir_renames[MERGE_SIDE2];
      +	int i;
      +
      +	strmap_for_each_entry(side1_dir_renames, &iter, entry) {
     @@ merge-ort.c: static void get_provisional_directory_renames(struct merge_options
      +			string_list_append(&duplicated, entry->key);
      +	}
      +
     -+	for (i=0; i<duplicated.nr; ++i) {
     ++	for (i = 0; i < duplicated.nr; i++) {
      +		strmap_remove(side1_dir_renames, duplicated.items[i].string, 0);
      +		strmap_remove(side2_dir_renames, duplicated.items[i].string, 0);
      +	}
  9:  bdd9d6cd702 =  9:  e9e621a0b70 merge-ort: modify collect_renames() for directory rename handling
 10:  9a06c698857 = 10:  28ae21bcb46 merge-ort: implement compute_collisions()
 11:  2ffb93c37ac = 11:  95f6e119072 merge-ort: implement apply_dir_rename() and check_dir_renamed()
 12:  cbfdf4d9ba0 = 12:  ad08c6ece4d merge-ort: implement check_for_directory_rename()
 13:  734891cb315 = 13:  1bece72e37a merge-ort: implement handle_path_level_conflicts()
 14:  4b912f2c025 = 14:  ee1398e3793 merge-ort: add a new toplevel_dir field
 15:  d74417e86c5 = 15:  ef86b7c07e3 merge-ort: implement apply_directory_rename_modifications()
 16:  11e45af831d = 16:  f1c7ce8123f merge-ort: process_renames() now needs more defensiveness
 17:  551878bd84d ! 17:  7c24f9f7aed merge-ort: fix a directory rename detection bug
     @@ merge-ort.c: static void compute_rename_counts(struct diff_queue_struct *pairs,
      -		char *old_dir, *new_dir;
       		struct diff_filepair *pair = pairs->queue[i];
       
     + 		/* File not part of directory rename if it wasn't renamed */
       		if (pair->status != 'R')
       			continue;