Re: [PATCH 3/3] merge-ort: implement merge_incore_recursive()

From: Junio C Hamano <gitster@pobox.com>
Date: Dec 16, 2020, 02:07 UTC
Message-ID: <xmqqbleu5wrs.fsf@gitster.c.googlers.com>
In-Reply-To: <82a773d8972b6641a25b3c84121dd38703a9286c.1608054807.git.gitgitgadget@gmail.com>

"Elijah Newren via GitGitGadget" <gitgitgadget@gmail.com> writes:

Show 17 quoted lines

> +/*
> + * Originally from merge_recursive_internal(); somewhat adapted, though.
> + */
> +static void merge_ort_internal(struct merge_options *opt,
> +			       struct commit_list *merge_bases,
> +			       struct commit *h1,
> +			       struct commit *h2,
> +			       struct merge_result *result)
> +{
> +	struct commit_list *iter;
> +	struct commit *merged_merge_bases;
> +	const char *ancestor_name;
> +	struct strbuf merge_base_abbrev = STRBUF_INIT;
> +
> +	if (!merge_bases) {
> +		merge_bases = get_merge_bases(h1, h2);
> +		merge_bases = reverse_commit_list(merge_bases);

Do we want to say why we reverse here, or is the reason so well known why in the original merge-recursive case?

Show 21 quoted lines

> +	}
> +
> +	merged_merge_bases = pop_commit(&merge_bases);
> +	if (merged_merge_bases == NULL) {
> +		/* if there is no common ancestor, use an empty tree */
> +		struct tree *tree;
> +
> +		tree = lookup_tree(opt->repo, opt->repo->hash_algo->empty_tree);
> +		merged_merge_bases = make_virtual_commit(opt->repo, tree,
> +							 "ancestor");
> +		ancestor_name = "empty tree";
> +	} else if (opt->ancestor && !opt->priv->call_depth) {
> +		ancestor_name = opt->ancestor;
> +	} else if (merge_bases) {
> +		ancestor_name = "merged common ancestors";
> +	} else {
> +		strbuf_add_unique_abbrev(&merge_base_abbrev,
> +					 &merged_merge_bases->object.oid,
> +					 DEFAULT_ABBREV);
> +		ancestor_name = merge_base_abbrev.buf;
> +	}

So, up to this point we learned:

 - merge bases either given by the caller, or computed from h1 and
   h2 when the caller just told us to figure it out ourselves.

 - if we have

   - 0 merge base between h1 and h2, in which case we would use an
     empty tree as an imaginary common

   - 1 merge base between h1 and h2, in which case the common
     ancestor of the resuting merge between h1 and h2 is that single
     merge base

   - 2 or more bases, in which case we'd use that would eventually
     come back when we merged recursively all bases.

and the primary products of the above procedure are

 - ancestor_name (the string used when presenting conflicts while
   merging h1 and h2)

 - merged_merge_bases (one starting commit among the merge bases)

And then the loop will iterate over the remaining merge bases, merging one popped from it in the current merged_merge_bases, until we run out. At that point when we leave the loop, we'd have merged_merge_bases that is a virtual commit to be used as a single merge base to use while merging trees of h1 and h2.

Show 30 quoted lines

> +	for (iter = merge_bases; iter; iter = iter->next) {
> +		const char *saved_b1, *saved_b2;
> +		struct commit *prev = merged_merge_bases;
> +
> +		opt->priv->call_depth++;
> +		/*
> +		 * When the merge fails, the result contains files
> +		 * with conflict markers. The cleanness flag is
> +		 * ignored (unless indicating an error), it was never
> +		 * actually used, as result of merge_trees has always
> +		 * overwritten it: the committed "conflicts" were
> +		 * already resolved.
> +		 */
> +		saved_b1 = opt->branch1;
> +		saved_b2 = opt->branch2;
> +		opt->branch1 = "Temporary merge branch 1";
> +		opt->branch2 = "Temporary merge branch 2";
> +		merge_ort_internal(opt, NULL, prev, iter->item, result);
> +		if (result->clean < 0)
> +			return;
> +		opt->branch1 = saved_b1;
> +		opt->branch2 = saved_b2;
> +		opt->priv->call_depth--;
> +
> +		merged_merge_bases = make_virtual_commit(opt->repo,
> +							 result->tree,
> +							 "merged tree");
> +		commit_list_insert(prev, &merged_merge_bases->parents);
> +		commit_list_insert(iter->item,
> +				   &merged_merge_bases->parents->next);

We need to record these parents because...? When merged_merge_bases we just created is used as one side of a merge in the next iteration, we'd need to compute the merge base between it and the one we'd pop out of merge_bases, and that is why.

> +		clear_or_reinit_internal_opts(opt->priv, 1);
> +	}

OK.  I think I understood this loop.  It looks mostly straight-forward.

> +	opt->ancestor = ancestor_name;

And the label to be used, that was computed before the above loop, is used here...

Show 6 quoted lines

> +	merge_ort_nonrecursive_internal(opt,
> +					repo_get_commit_tree(opt->repo,
> +							     merged_merge_bases),
> +					repo_get_commit_tree(opt->repo, h1),
> +					repo_get_commit_tree(opt->repo, h2),
> +					result);

... to finally compute the 3-way merge between h1 and h2.

> +	strbuf_release(&merge_base_abbrev);

And the storage that may have been holding the .ancestor name is cleared, as we no longer need it.

Show 15 quoted lines

> +	opt->ancestor = NULL;  /* avoid accidental re-use of opt->ancestor */
> +}
> +
>  void merge_incore_nonrecursive(struct merge_options *opt,
>  			       struct tree *merge_base,
>  			       struct tree *side1,
> @@ -1493,7 +1577,9 @@ void merge_incore_recursive(struct merge_options *opt,
>  			    struct commit *side2,
>  			    struct merge_result *result)
>  {
> -	(void)reverse_commit_list;
> -	(void)make_virtual_commit;
> -	die("Not yet implemented");
> +	assert(opt->ancestor == NULL ||
> +	       !strcmp(opt->ancestor, "constructed merge base"));

Where does this string come from? The recursive backend does asssign a fixed string with that value to opt->ancestor, but we don't expect that string to come here, no?

> +	merge_start(opt, result);
> +	merge_ort_internal(opt, merge_bases, side1, side2, result);
>  }