[PATCH 0/2] merge-ort: fix a crash in process_renames for a file transitively renamed to itself

[PATCH 0/2] merge-ort: fix a crash in process_renames for a file transitively renamed to itself

[Elijah Newren via GitGitGadget]

Maintainer note: this is not a recent regression; it need not be included in
v2.49.0.

This is a follow-up to Dmitry's report of a case where both merge-ort and
merge-recursive fail to properly handle a very specific type of conflict.
See
https://lore.kernel.org/git/20240921024533.15249-2-dgoncharov@users.sf.net/
for the earlier thread; the first patch is an adaptation of his
demonstrating the issue, and the second patch is my fix for it.

Dmitry Goncharov (1):
  t6423: add a testcase causing a failed assertion in process_renames

Elijah Newren (1):
  merge-ort: fix slightly overzealous assertion for rename-to-self

 merge-ort.c                         |  3 ++-
 t/t6423-merge-rename-directories.sh | 41 +++++++++++++++++++++++++++++
 2 files changed, 43 insertions(+), 1 deletion(-)


base-commit: f93ff170b93a1782659637824b25923245ac9dd1
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1873%2Fnewren%2Fendit-fix-funny-rename-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1873/newren/endit-fix-funny-rename-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/1873
-- 
gitgitgadget

[PATCH 1/2] t6423: add a testcase causing a failed assertion in process_renames

[Dmitry Goncharov via GitGitGadget]

From: Dmitry Goncharov <dgoncharov@users.sf.net>

If one side of history renames a directory A/ -> B/, and the other side
of history adds new files to A/, then directory rename detection notices
and moves or suggests moving those new files to B/.  A similar thing is
done for paths renamed into A/, causing them to be transitively renamed
into B/.  But, if the file originally came from B/, then this can end up
causing a file to be renamed back to itself.  merge-ort crashes under
this special case, due to a slightly overzealous assertion:

    git: merge-ort.c:3051: process_renames: Assertion `source_deleted || oldinfo->filemask & old_sidemask' failed.
    Aborted (core dumped)

Add a testcase demonstrating this.

Signed-off-by: Dmitry Goncharov <dgoncharov@users.sf.net>
[en: Instead of adding a new testsuite, place it near similar tests in
 t6423, adjusting to match the style of those tests.  Tweak the commit
 message to not repeat the entire testcase, but just describe the bug.
 Also update the line number in the error message.]
Signed-off-by: Elijah Newren <newren@gmail.com>
---
 t/t6423-merge-rename-directories.sh | 41 +++++++++++++++++++++++++++++
 1 file changed, 41 insertions(+)

diff --git a/t/t6423-merge-rename-directories.sh b/t/t6423-merge-rename-directories.sh
index 88d1cf2cde9..259ee9628e4 100755
--- a/t/t6423-merge-rename-directories.sh
+++ b/t/t6423-merge-rename-directories.sh
@@ -5360,6 +5360,47 @@ test_expect_merge_algorithm failure success '12m: Change parent of renamed-dir t
 	)
 '
 
+test_setup_12n () {
+	git init 12n &&
+	(
+		cd 12n &&
+
+		mkdir tools &&
+		echo hello >tools/hello &&
+		git add tools/hello &&
+		git commit -m "O" &&
+
+		git branch O &&
+		git branch A &&
+		git branch B &&
+
+		git switch A &&
+		echo world >world &&
+		git add world &&
+		git commit -q world -m 'Add world' &&
+
+		git mv world tools/world &&
+		git commit -m "Move world into tools/" &&
+
+		git switch B &&
+		git mv tools/hello hello &&
+		git commit -m "Move hello from tools/ to toplevel"
+	)
+}
+
+test_expect_failure '12n: Directory rename transitively makes rename back to self' '
+	test_setup_12n &&
+	(
+		cd 12n &&
+
+		git checkout -q B^0 &&
+
+		test_must_fail git cherry-pick A^0 >out &&
+		grep "CONFLICT (file location).*should perhaps be moved" out
+	)
+'
+
+
 ###########################################################################
 # SECTION 13: Checking informational and conflict messages
 #
-- 
gitgitgadget

[PATCH 2/2] merge-ort: fix slightly overzealous assertion for rename-to-self

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

merge-ort has a number of sanity checks on the file it is processing in
process_renames().  One of these sanity checks was slightly overzealous
because it indirectly assumed that a renamed file always ended up at a
different path than where it started.  That is normally an entirely fair
assumption, but directory rename detection can make things interesting.

As a quick refresher, if one side of history renames directory A/ -> B/,
and the other side of history adds new files to A/, then directory
rename detection notices and suggests moving those new files to B/.  A
similar thing is done for paths renamed into A/, causing them to be
transitively renamed into B/.  But, if the file originally came from B/,
then this can end up causing a file to be renamed back to itself.

It turns out the rest of the code following this assertion handled the
case fine; the assertion was just an extra sanity check, not a rigid
precondition.  Therefore, simply adjust the assertion to pass under this
special case as well.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 merge-ort.c                         | 3 ++-
 t/t6423-merge-rename-directories.sh | 2 +-
 2 files changed, 3 insertions(+), 2 deletions(-)

diff --git a/merge-ort.c b/merge-ort.c
index 46e78c3ffa6..b0ff2236af0 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -3048,7 +3048,8 @@ static int process_renames(struct merge_options *opt,
 			}
 		}
 
-		assert(source_deleted || oldinfo->filemask & old_sidemask);
+		assert(source_deleted || oldinfo->filemask & old_sidemask ||
+		       !strcmp(pair->one->path, pair->two->path));
 
 		/* Need to check for special types of rename conflicts... */
 		if (collision && !source_deleted) {
diff --git a/t/t6423-merge-rename-directories.sh b/t/t6423-merge-rename-directories.sh
index 259ee9628e4..9cbd41d3c69 100755
--- a/t/t6423-merge-rename-directories.sh
+++ b/t/t6423-merge-rename-directories.sh
@@ -5388,7 +5388,7 @@ test_setup_12n () {
 	)
 }
 
-test_expect_failure '12n: Directory rename transitively makes rename back to self' '
+test_expect_success '12n: Directory rename transitively makes rename back to self' '
 	test_setup_12n &&
 	(
 		cd 12n &&
-- 
gitgitgadget

Re: [PATCH 2/2] merge-ort: fix slightly overzealous assertion for rename-to-self

[Taylor Blau]

On Thu, Mar 06, 2025 at 03:30:27PM +0000, Elijah Newren via GitGitGadget wrote:
> From: Elijah Newren <newren@gmail.com>
>
> merge-ort has a number of sanity checks on the file it is processing in
> process_renames().  One of these sanity checks was slightly overzealous
> because it indirectly assumed that a renamed file always ended up at a
> different path than where it started.  That is normally an entirely fair
> assumption, but directory rename detection can make things interesting.
>
> As a quick refresher, if one side of history renames directory A/ -> B/,
> and the other side of history adds new files to A/, then directory
> rename detection notices and suggests moving those new files to B/.  A
> similar thing is done for paths renamed into A/, causing them to be
> transitively renamed into B/.  But, if the file originally came from B/,
> then this can end up causing a file to be renamed back to itself.
>
> It turns out the rest of the code following this assertion handled the
> case fine; the assertion was just an extra sanity check, not a rigid
> precondition.  Therefore, simply adjust the assertion to pass under this
> special case as well.

Wow, that is a very interesting edge case from Dmitry. The explanation
and fix makes sense, and yeah, looks like just an over-zealous
assertion.

As a meta-comment, I vaguely remember past discussions on the list about
when to assert() versus when to BUG(). I recall that where we landed was
that:

    if (foo)
        BUG("something");

was preferable to:

    assert(foo);

I know that we don't usually define NDEBUG, but I think there are a
couple of cases where we do, like for nedmalloc stuff when building with
USE_NED_ALLOCATOR, and in Windows builds if DEBUG is undefined.

So I don't think it makes a huge practical difference, but it might be
nice to put in CodingGuidelines or similar.

Thanks,
Taylor

Re: [PATCH 2/2] merge-ort: fix slightly overzealous assertion for rename-to-self

[Elijah Newren]

On Wed, Mar 12, 2025 at 3:00 PM Taylor Blau <me@ttaylorr.com> wrote:
>
> On Thu, Mar 06, 2025 at 03:30:27PM +0000, Elijah Newren via GitGitGadget wrote:
> > From: Elijah Newren <newren@gmail.com>
> >
> > merge-ort has a number of sanity checks on the file it is processing in
> > process_renames().  One of these sanity checks was slightly overzealous
> > because it indirectly assumed that a renamed file always ended up at a
> > different path than where it started.  That is normally an entirely fair
> > assumption, but directory rename detection can make things interesting.
> >
> > As a quick refresher, if one side of history renames directory A/ -> B/,
> > and the other side of history adds new files to A/, then directory
> > rename detection notices and suggests moving those new files to B/.  A
> > similar thing is done for paths renamed into A/, causing them to be
> > transitively renamed into B/.  But, if the file originally came from B/,
> > then this can end up causing a file to be renamed back to itself.
> >
> > It turns out the rest of the code following this assertion handled the
> > case fine; the assertion was just an extra sanity check, not a rigid
> > precondition.  Therefore, simply adjust the assertion to pass under this
> > special case as well.
>
> Wow, that is a very interesting edge case from Dmitry. The explanation
> and fix makes sense, and yeah, looks like just an over-zealous
> assertion.
>
> As a meta-comment, I vaguely remember past discussions on the list about
> when to assert() versus when to BUG(). I recall that where we landed was
> that:
>
>     if (foo)
>         BUG("something");
>
> was preferable to:
>
>     assert(foo);

I disagree that we landed on that; at least the last time it was
brought up to me there was no ending statement of such --
https://lore.kernel.org/git/CABPp-BFLyYTboiGkP=sc7S+stRZvozAqnJPnza+M0q2nakvD2Q@mail.gmail.com/,
and then I proceeded to continue submitting and getting merged several
more assert statements.

If there was a project-wide directive to remove assert() statements,
then I'd quickly create something else (e.g. "BUG_ON(foo)") and
convert to that rather than "if (foo) BUG(bar)".  And I'd probably
make it depend on NDEBUG too...

> I know that we don't usually define NDEBUG, but I think there are a
> couple of cases where we do, like for nedmalloc stuff when building with
> USE_NED_ALLOCATOR, and in Windows builds if DEBUG is undefined.

If the statement is important to have in production builds, I have
used "if (foo) BUG(bar)", including in merge-ort.c.  But I think there
are different classes of notes-for-other-developers.  Code comments
for the lightest end, if (foo) BUG (bar) for the heavier end, and
assertions for somewhere in the middle.  I think I've used a higher
density of checks in merge-ort than tend to be used elsewhere, in part
because of the number of optimizations added to the code and the
difficulty of keeping track of all the preconditions and assumptions
with the extra data structures feeding those.  Lots of those checks
might have just been code comments somewhere else; they aren't
necessarily worth a real if-check.  They'd be fine to compile out
generally.  In some cases, they might go to the full "if (foo)
BUG(bar)", but I think there's a reasonable middle ground.  assert()
statements survive and are kept up-to-date better than a code comment,
they tend to be clearer than a code comment, and they catch more bugs
while refactoring (or originally developing the code) than code
comments.  And they are much more brief and ergonomic than the "if
(foo) BUG(bar)" construct (why do I have to come up with a separate
bar, when it's already embedded in foo?)

> So I don't think it makes a huge practical difference, but it might be
> nice to put in CodingGuidelines or similar.

Maybe I should put something in there so I don't have to look up the
old conversations and point out my disagreements with this suggestion
yet again...  ;-)

But it might be worth mentioning that having side-effects in
assertions is a huge no-no, and I understand that when folks have to
debug one of those (I had to in a separate project years ago which was
kind of nasty), that they sometimes jump to the conclusion that
assertions are bad.  I understand being bitten, but disagree with the
conclusion.

Re: [PATCH 2/2] merge-ort: fix slightly overzealous assertion for rename-to-self

[Junio C Hamano]

Elijah Newren <newren@gmail.com> writes:

> But it might be worth mentioning that having side-effects in
> assertions is a huge no-no, and I understand that when folks have to
> debug one of those (I had to in a separate project years ago which was
> kind of nasty), that they sometimes jump to the conclusion that
> assertions are bad.

Yes, assert() invites such mistakes.  Why not avoid them when there
are better alternatives like "if (condition) BUG()"?

Re: [PATCH 2/2] merge-ort: fix slightly overzealous assertion for rename-to-self

[Elijah Newren]

On Wed, Mar 12, 2025 at 4:18 PM Junio C Hamano <gitster@pobox.com> wrote:
>
> Elijah Newren <newren@gmail.com> writes:
>
> > But it might be worth mentioning that having side-effects in
> > assertions is a huge no-no, and I understand that when folks have to
> > debug one of those (I had to in a separate project years ago which was
> > kind of nasty), that they sometimes jump to the conclusion that
> > assertions are bad.
>
> Yes, assert() invites such mistakes.  Why not avoid them when there
> are better alternatives like "if (condition) BUG()"?

I mean, I just gave my reasons above which you snipped out.  But if
you feel it is important for folks to move away from assert(), would
you like to see someone create a better alternative to assert, such as
BUG_ON(condition), so that they have reason to want to switch?

Re: [PATCH 2/2] merge-ort: fix slightly overzealous assertion for rename-to-self

[Junio C Hamano]

Elijah Newren <newren@gmail.com> writes:

> On Wed, Mar 12, 2025 at 4:18 PM Junio C Hamano <gitster@pobox.com> wrote:
>>
>> Elijah Newren <newren@gmail.com> writes:
>>
>> > But it might be worth mentioning that having side-effects in
>> > assertions is a huge no-no, and I understand that when folks have to
>> > debug one of those (I had to in a separate project years ago which was
>> > kind of nasty), that they sometimes jump to the conclusion that
>> > assertions are bad.
>>
>> Yes, assert() invites such mistakes.  Why not avoid them when there
>> are better alternatives like "if (condition) BUG()"?
>
> I mean, I just gave my reasons above which you snipped out.  But if
> you feel it is important for folks to move away from assert(), would
> you like to see someone create a better alternative to assert, such as
> BUG_ON(condition), so that they have reason to want to switch?

You said "BUG_ON()" is better than "if (condition) BUG()", but I do
not see a reason why.  It also shares the same problem with assert()
if we make it honor NDEBUG.

Thanks.

Re: [PATCH 2/2] merge-ort: fix slightly overzealous assertion for rename-to-self

[Elijah Newren]

On Thu, Mar 13, 2025 at 9:55 AM Junio C Hamano <gitster@pobox.com> wrote:
>
> Elijah Newren <newren@gmail.com> writes:
>
> > On Wed, Mar 12, 2025 at 4:18 PM Junio C Hamano <gitster@pobox.com> wrote:
> >>
> >> Elijah Newren <newren@gmail.com> writes:
> >>
> >> > But it might be worth mentioning that having side-effects in
> >> > assertions is a huge no-no, and I understand that when folks have to
> >> > debug one of those (I had to in a separate project years ago which was
> >> > kind of nasty), that they sometimes jump to the conclusion that
> >> > assertions are bad.
> >>
> >> Yes, assert() invites such mistakes.  Why not avoid them when there
> >> are better alternatives like "if (condition) BUG()"?
> >
> > I mean, I just gave my reasons above which you snipped out.  But if
> > you feel it is important for folks to move away from assert(), would
> > you like to see someone create a better alternative to assert, such as
> > BUG_ON(condition), so that they have reason to want to switch?
>
> You said "BUG_ON()" is better than "if (condition) BUG()", but I do
> not see a reason why.  It also shares the same problem with assert()
> if we make it honor NDEBUG.

"if (condition) BUG()" is invalid; it needs more arguments.  "if
(condition) BUG(something)" requires a separate "something", which
requires awkward additional wording and/or is needlessly duplicative.

If you don't want to see assert in the codebase because of NDEBUG,
then obviously we'd leave NDEBUG out of BUG_ON().

Such a BUG_ON() would be an improvement because it maintains the
ergonomics of assert() while avoiding the potential mistake of
accidentally including something with side-effects.  "If (condition)
BUG(something)" doesn't preserve the ergonomics and is thus worse,
IMO.  (Personally, I still like having cheap checks that are okay to
compile out, but if we want a project directive against those, then I
think a BUG_ON() that doesn't depend on NDEBUG would be the way to
move in that direction.)

Re: [PATCH 2/2] merge-ort: fix slightly overzealous assertion for rename-to-self

[Junio C Hamano]

Elijah Newren <newren@gmail.com> writes:

> "if (condition) BUG()" is invalid; it needs more arguments.  "if
> (condition) BUG(something)" requires a separate "something", which
> requires awkward additional wording and/or is needlessly duplicative.

Ah, obviously we differ on that point.

I consider it an advantage that <something> can be more descriptive
in a developer friendly way than <condition> expression alone.  If
you wrote

	if (istate->cache_nr < i)
		BUG("ran past the end of the istate->cache[] array?");

you can spot a bug of the assertion, because the human-readable part
tells us the intention that the condition is supposed to be the
usual array bounds check, and should be checking with "<=".  In
contrast

	BUG_ON(istate->cache_nr < i);

does not give us the extra information we can use to double check
what the developer who wrote it, who may not be with us anymore,
wanted to really check.  Is it a misspelt "<=", or does this code
path use 'i' not just as a variable to iterate over the array but
also allows it to go one past its end, so "<" is the condition it
really wants to validate?

> If you don't want to see assert in the codebase because of NDEBUG,
> then obviously we'd leave NDEBUG out of BUG_ON().

Absolutely, because the largest problem with assert() is that the
condition can be compiled away while the compiler does not help
ensure that the condition part is free of side effects.  If we drop
NDEBUG, that problem goes away.

> Such a BUG_ON() would be an improvement because it maintains the
> ergonomics of assert() while avoiding the potential mistake of
> accidentally including something with side-effects.  

Yes, we are half on the same page (as I disagree that assert() that
does not give a room to explain why we are checking the condition is
ergonomic at all) and agree that discarding NDEBUG gives us safer
variant than assert().

> "If (condition)
> BUG(something)" doesn't preserve the ergonomics and is thus worse,

Again, this is philosophical difference between us.  It gives us the
same safety as NDEBUG-less BUG_ON() but allows us to be more
descriptive to help developers.  While I understand sometimes the
condition may be self evident (especially while developing new code,
where the developer thought the problem long and deep) and people
may find it tedious to have to explain the reasoning behind the
check, I find it highly problematic not to give room to explain to
those who want to.  And /* comments */ is not the same thing, as I
think it is important to explain your BUG() well, just like it is
good practice to explain your commit well in the log message.

One thing I view as a downside of "if (condition) BUG(message)" is
that it does not make it clear syntactically that (condition) is
about assertion, and you can write

	if (condition) {
		do something;
		BUG(message);
	}

which probably is not what you want.  I am OK with

	BUG_ON(<condition>, <message>);

which would make such a construct impossible.

Thanks.

Re: [PATCH 2/2] merge-ort: fix slightly overzealous assertion for rename-to-self

[Elijah Newren]

On Thu, Mar 13, 2025 at 11:34 AM Junio C Hamano <gitster@pobox.com> wrote:
>
> Elijah Newren <newren@gmail.com> writes:
>
> > "if (condition) BUG()" is invalid; it needs more arguments.  "if
> > (condition) BUG(something)" requires a separate "something", which
> > requires awkward additional wording and/or is needlessly duplicative.
>
> Ah, obviously we differ on that point.
>
> I consider it an advantage that <something> can be more descriptive
> in a developer friendly way than <condition> expression alone.

I think there's been a communication disconnect.  I too like "if
(condition) BUG (something)" and often use it, as I pointed out
earlier in this thread.  The fact that it _can_ be more descriptive is
an advantage in some situations (and you provided a great example.)

The problem is that some situations != all situations, and I find it
worse when trying to force it for all the other cases.  If we still
disagree on that point, that's fine, but I wanted to make it clear
that I am a fan of and use "if (condition) BUG (something)" where it
fits.

[...]
> > If you don't want to see assert in the codebase because of NDEBUG,
> > then obviously we'd leave NDEBUG out of BUG_ON().
>
> Absolutely, because the largest problem with assert() is that the
> condition can be compiled away while the compiler does not help
> ensure that the condition part is free of side effects.  If we drop
> NDEBUG, that problem goes away.

Or we can just add a static analysis job that will error whenever the
compiler/linker can't prove that assertions have no side effects, and
suggest folks use an alternative macro for those instances.   I just
submitted a series to do that over here:
https://lore.kernel.org/git/pull.1881.git.1741911652.gitgitgadget@gmail.com/

That should be far more thorough than any CodingGuideline at making
sure we don't have asserts with side effects, be far less effort than
attempting to change our several hundred existing assert() invocations
in the code base, and should be enough to consider the problem solved
and let us move on to something more interesting.