Re: [PATCH 6/6] merge-ort: fix directory rename on top of source of other rename/delete

[Patrick Steinhardt <ps@pks.im>]

On Tue, Jul 22, 2025 at 03:23:11PM +0000, Elijah Newren via GitGitGadget wrote:

What a massive commit message. It almost felt like a blog post rather
than a commit message, but I certainly don't mind the additional
context.

> From: Elijah Newren <newren@gmail.com>
> 
> At GitHub, we've got a real-world repository that has been triggering
> failures of the form:
> 
>     git: merge-ort.c:3007: process_renames: Assertion `newinfo && !newinfo->merged.clean' failed.
> 
> which comes from the line:
> 
>     VERIFY_CI(newinfo);
> 
> Unfortunately, this one has been quite complex to unravel, and is a
> bit complex to explain.  So, I'm going to carefully try to explain each
> relevant piece needed to understand the fix, then carefully build up
> from a simple testcase to some of the relevant testcases.
> 
> == New special case we need to consider ==
> 
> Rename pairs in the diffcore machinery connect the source path of a
> rename with the destination path of a rename.  Since we have rename
> pairs to consider on both sides of history since the merge base,
> merging has to consider a few special cases of possible overlap:
> 
>   A) two rename pairs having the same target path
>   B) two rename pairs having the same source path
>   C) the source path of one rename pair being the target path of a
>      different rename pair

So basically file A get's moved somewhere else and then replaced by a
different file B?

> Some of these came up often enough that we gave them names:
>   A) a rename/rename(2to1) conflict (looks similar to an add/add conflict)
>   B) a rename/rename(1to2) conflict, which represents the same path being
>      renamed differently on the two sides of history
>   C) not yet named
> 
> merge-ort is well-prepared to handle cases (A) and (B), as was
> merge-recursive (which was merge-ort's predecessor).  Case (C) was
> briefly considered during the years of merge-recursive maintenance,
> but the full extent of support it got was a few FIXME/TODO comments
> littered around the code highlighting some of the places that would
> probably need to be fixed to support it.  When I wrote merge-ort I
> ignored case (C) entirely, since I believed that case (C) was only
> possible if we were to support break detection during merges.  Not
> only had break detection never been supported by any merge algorithm,
> I thought break detection wasn't worth the effort to support in a
> merge algorithm.  However, it turns out that case (C) can be triggered
> without break detection, if there's enough moving pieces.
> 
> Before I dive into how to trigger case (C) with directory renames plus
> other renames, it might be helpful to use a simpler example with break
> detection first.  And before we get to that it may help to explain
> some more basics of handling renames in the merge algorithm.  So, let
> me first backup and provide a quick refresher on on each of

s/on on/on/

[snip]
> == Directory rename detection ==
> 
> If one side of history renames directory D/ -> E/, and the other side of
> history adds new files to E/, then directory rename detection notices

Did you mean to say "D/" here?

[snip]
> == Testcases 8+ ==
> 
> Another bonus bug, found via understanding our final solution (and the
> failure of our first attempted solution)!

s/solution/solutions/ as there are multiple attempted solutions that
were discarded?

> diff --git a/merge-ort.c b/merge-ort.c
> index feb06720c7e1..f1ecccee940b 100644
> --- a/merge-ort.c
> +++ b/merge-ort.c
> @@ -2313,14 +2313,20 @@ static char *apply_dir_rename(struct strmap_entry *rename_info,
>  	return strbuf_detach(&new_path, NULL);
>  }
>  
> -static int path_in_way(struct strmap *paths, const char *path, unsigned side_mask)
> +static int path_in_way(struct strmap *paths,
> +		       const char *path,
> +		       unsigned side_mask,
> +		       struct diff_filepair *p)
>  {
>  	struct merged_info *mi = strmap_get(paths, path);
>  	struct conflict_info *ci;
>  	if (!mi)
>  		return 0;
>  	INITIALIZE_CI(ci, mi);
> -	return mi->clean || (side_mask & (ci->filemask | ci->dirmask));
> +	return mi->clean || (side_mask & (ci->filemask | ci->dirmask))
> +	  // See testcases 12n, 12p, 12q for more details on this next condition

This should use `/* */`-style comments.

> +			 || ((ci->filemask & 0x01) &&
> +			     strcmp(p->one->path, path));

So if we have a stage 1 index entry and the path is the same due to a
transitive rename we can say that the path is not in the way?

Patrick