[PATCH v2 0/3] merge-ort: implement recursive merges

This series depends on en/merge-ort-2 (it does NOT depend on en/merge-ort-3 and can thus be reviewed/merged independently of it).

This short series adds handling of recursive merges (merging of multiple merge-bases to create a virtual merge base) to merge-ort. With this short series the number of test failures under GIT_TEST_MERGE_ALGORITHM=ort drops by 801 (from 1448 to 647).

Changes since v1 (based on review comments from Junio):

 * add documentation on why we reverse the commit_list of merge bases
 * modify the special override for allowing opt->ancestor to be set before
   merge_incore_recursive() and document its rationale

Elijah Newren (3):
  merge-ort: copy a few small helper functions from merge-recursive.c
  merge-ort: make clear_internal_opts() aware of partial clearing
  merge-ort: implement merge_incore_recursive()

 merge-ort.c | 149 +++++++++++++++++++++++++++++++++++++++++++++++++---
 merge-ort.h |  10 ++++
 2 files changed, 152 insertions(+), 7 deletions(-)

base-commit: c5a6f65527aa3b6f5d7cf25437a88d8727ab0646
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-814%2Fnewren%2Fort-recursive-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-814/newren/ort-recursive-v2
Pull-Request: https://github.com/gitgitgadget/git/pull/814

Range-diff vs v1:

 1:  0b455bd6fe7 = 1:  0b455bd6fe7 merge-ort: copy a few small helper functions from merge-recursive.c
 2:  fc26c1a11db = 2:  fc26c1a11db merge-ort: make clear_internal_opts() aware of partial clearing
 3:  82a773d8972 ! 3:  d8f79450a40 merge-ort: implement merge_incore_recursive()
     @@ merge-ort.c: static void merge_ort_nonrecursive_internal(struct merge_options *o
      +
      +	if (!merge_bases) {
      +		merge_bases = get_merge_bases(h1, h2);
     ++		/* See merge-ort.h:merge_incore_recursive() declaration NOTE */
      +		merge_bases = reverse_commit_list(merge_bases);
      +	}
      +
     @@ merge-ort.c: void merge_incore_recursive(struct merge_options *opt,
      -	(void)reverse_commit_list;
      -	(void)make_virtual_commit;
      -	die("Not yet implemented");
     -+	assert(opt->ancestor == NULL ||
     -+	       !strcmp(opt->ancestor, "constructed merge base"));
     ++	/*
     ++	 * merge_incore_nonrecursive() exists for cases where we always
     ++	 * know there is a well-defined single merge base.  However,
     ++	 * despite a similar structure, merge-recursive.c noted that some
     ++	 * callers preferred to call the recursive logic anyway and still
     ++	 * set a special name for opt->ancestor that would appear in
     ++	 * merge.conflictStyle=diff3 output.
     ++	 *
     ++	 * git-am was one such example (it wanted to set opt->ancestor to
     ++	 * "constructed merge base", since it created a fake merge base);
     ++	 * it called the recursive merge logic through a special
     ++	 * merge_recursive_generic() wrapper.
     ++	 *
     ++	 * Allow the same kind of special case here.
     ++	 */
     ++	int num_merge_bases_is_1 = (merge_bases && !merge_bases->next);
     ++	assert(opt->ancestor == NULL || num_merge_bases_is_1);
      +
      +	merge_start(opt, result);
      +	merge_ort_internal(opt, merge_bases, side1, side2, result);
       }
     +
     + ## merge-ort.h ##
     +@@ merge-ort.h: struct merge_result {
     + /*
     +  * rename-detecting three-way merge with recursive ancestor consolidation.
     +  * working tree and index are untouched.
     ++ *
     ++ * merge_bases will be consumed (emptied) so make a copy if you need it.
     ++ *
     ++ * NOTE: empirically, the recursive algorithm will perform better if you
     ++ *       pass the merge_bases in the order of oldest commit to the
     ++ *       newest[1][2].
     ++ *
     ++ *       [1] https://lore.kernel.org/git/nycvar.QRO.7.76.6.1907252055500.21907@tvgsbejvaqbjf.bet/
     ++ *       [2] commit 8918b0c9c2 ("merge-recur: try to merge older merge bases
     ++ *           first", 2006-08-09)
     +  */
     + void merge_incore_recursive(struct merge_options *opt,
     + 			    struct commit_list *merge_bases,