jj unexpectedly simplifies ancestry when rewriting a commit that is both a direct child and an indirect descendant of another commit

[ilyagr]

Description

I have always assumed that we do not allow a commit to be a direct child and an indirect descendant of another commit at the same time. See, for example:

jj/cli/tests/test_rebase_command.rs

Lines 264 to 269 in 5186066

	// Descendants of the rebased commit "b" should be rebased onto parents. First
	// we test with a non-merge commit. Normally, the descendant "c" would still
	// have 2 parents afterwards: the parent of "b" -- the root commit -- and
	// "a". However, since the root commit is an ancestor of "a", we don't
	// actually want both to be parents of the same commit. So, only "a" becomes
	// a parent.

from #538. jj abandon has similar functionality, see #2601.

However, it is actually possible to create such commits. Even simple commands like jj describe misbehave in such situations.

I originally discovered this in ilyagr@rebase-bug (see the test), but that bug seemed less relevant after I realized describe is also affected.

Is this a recent change? What is the desired behavior here?

Steps to Reproduce the Problem

Start with this tree:

◉  MPVRWZ ilyagr@ 2023-11-19 15:21 -08 089239         
│  (empty) r                   
@  ZMKTYM ilyagr@ 2023-11-19 15:21 -08 default@ b94c44 
│  (empty) base   

1. Execute jj new mpv zmk -m test. (Aside: jj rebase -r another_commit -d mpv -d zmk produces a similar result.).

We get:

@    YOUOPL ilyagr@ 2023-11-19 15:22 -08 default@ 1c5b5a
├─╮  (empty) test              
│ ◉  MPVRWZ ilyagr@ 2023-11-19 15:21 -08 089239        
├─╯  (empty) r    
◉  ZMKTYM ilyagr@ 2023-11-19 15:21 -08 HEAD@git b94c44 
│  (empty) base  

2. Execute jj describe -r mpv -m newname (Aside: jj edit mpv; touch qq; jj status produces a similar result)

Actual Behavior

@  YOUOPL ilyagr@ 2023-11-19 15:23 -08 default@ 5ecf8e  
│  (empty) test                
◉  MPVRWZ ilyagr@ 2023-11-19 15:23 -08 HEAD@git 976459 
│  (empty) newname
◉  ZMKTYM ilyagr@ 2023-11-19 15:21 -08 b94c44          
│  (empty) base           

Expected Behavior

Either jj new results in a linear history after step 1 or jj describe keeps the shape of the graph after step 2.

Specifications

• Platform: Debian linux
• Version: jj 0.11.0+20231111-ac53e26183315bd4 (based on the state of the main branch on 11/11).

---

Update: From the discussion below up to #2600 (comment), it seems this is actually 2.5 issues:

• We should fix jj describe, jj edit messing up the shape and any similar bugs we can find.
• We should allow rebase and abandon (and others?) to create children that are also descendants
• We should test and fix the issue that will cause with rebase -r onto descendants and any similar issues.

Lots of fun tests to write!

[martinvonz]

Either jj new results in a linear history after step 1 or jj describe keeps the shape of the graph after step 2.

I was surprised that jj describe drops the merge. I consider that the bug.

@matts1, if you're thinking of working on #229, it's probably a good idea to keep this case in mind as well.

[ilyagr]

If so, should abandon and similar commands continue to avoid this outcome?

I'm guessing Git supports it, in which case we have to be able to pull such commits from a remote.

[martinvonz]

I'm guessing Git supports it, in which case we have to be able to pull such commits from a remote.

Yes, and GitHub (and probably GitLab and others) create these all the time. Projects that use GitHub's default way of integrating PRs (called "Merge", I think) will have lots of these merges.

If so, should abandon and similar commands continue to avoid this outcome?

I'm not sure. To me, it's surprising if commands like jj describe drop an edge because they don't normally change the shape of the DAG. It's less clear what jj abandon should do. Let's say we have this history:

D
|\
| C
B |
|/
A

If the user abandoned C, they would probably want D to become a child of only B, but it also seems reasonable to keep the shape of the history by making making D a child of B and A.

There's also this degenerate case:

D
|\
C |
|/
B
|
A

Here, I think it's clear that abandoning C should not leave B and B (duplicated) as parents of D. I think it's also clear that abandoning A should not change D's parents. I would also say that abandoning B should result in D having C and A as parents.

[ilyagr]

For the degenerate case, I'm guessing Git does not allow duplicated parents?

Here are a few thoughts about implementation difficulties.

Let's say that D had a child in your degenerate case, and we abandon D. I'll draw the example a little differently than you did (I find this layout easier to understand):

E
|
D
|\
| C
|/
B
|
A

Abandoning D should likely make C and B the parents of E.

From the implementation standpoint, however, the above behavior is not trivial to reconcile with the current behavior of abandoning C in your non-degenerate example:

D
|\
| C
B |
|/
A

leaving D with one parent.

If we change the behavior and make abandoning C leave D with two parents, the logic at

jj/cli/src/commands/rebase.rs

Lines 345 to 348 in 22ad4d7

	// To make the update simpler, we assume that each commit was rewritten only
	// once; we don't have a situation where both `(A,B)` and `(B,C)` are in
	// `rebased_commit_ids`. This assumption relies on the fact that a descendant of
	// a child of `old_commit` cannot also be a direct child of `old_commit`.

will probably need reworking. The assumption there is already false, but the fact that rebase itself does not create such incestuous commits is probably good enough to make the logic work. I wonder what other fun test cases we'd need to add.

[martinvonz]

From the implementation standpoint, however, the above behavior is not trivial to reconcile with the current behavior of abandoning C in your non-degenerate example

Good point. I think that's a good argument for not having too much smarts in the auto-rebasing code. If the user wants to linearize history, they can manually update D to have just one parent with jj rebase -s D -d B.

[ilyagr]

Instead of jj describe, a better demo of the bug is to jj edit the commit, touch qq, and run any jj command to import the working copy. I updated the bug description to mention that. The problem is somewhere in DescendantRebaser, I'd guess.

[ilyagr]

Specifically, I think it's this section that reshapes the graph in the case of edit or describe:

jj/lib/src/rewrite.rs

Lines 445 to 456 in 16620e0

	// Don't create commit where one parent is an ancestor of another.
	let head_set: HashSet<_> = self
	.mut_repo
	.index()
	.heads(&mut new_parent_ids.iter())
	.into_iter()
	.collect();
	let new_parents: Vec<_> = new_parent_ids
	.iter()
	.filter(|new_parent| head_set.contains(new_parent))
	.map(|new_parent_id| self.mut_repo.store().get_commit(new_parent_id))
	.try_collect()?;

It dates back all the way to 4e0a89b, together with the test:

jj/lib/tests/test_rewrite.rs

Lines 525 to 537 in 16620e0

	fn test_rebase_descendants_abandon_degenerate_merge() {
	let settings = testutils::user_settings();
	let test_repo = TestRepo::init();
	let repo = &test_repo.repo;
	// Commit B was abandoned. Commit D should get rebased to have only C as parent
	// (not A and C).
	//
	// D
	// |\
	// B C
	// |/
	// A

[ilyagr]

Here's a fun edge case I found. Let's say we decide we want to simplify ancestry as little as possible.

Here's little puzzle (answer below): why would jj have trouble doing jj rebase -r base -d root for the following tree?

    @  c
    ◉    b
    ├─╮
    │ ◉  a
    ├─╯
    ◉  base
    ◉  root

Answer (there are also spoilers below)

Because b would then be a child of both a and the root commit. With the Git backend, at least, that is not allowed.

I can see two options of what to do here:

• Print an error message. This seems like it would be surprising and annoying, since it takes a puzzle to figure out what was wrong in the first place.
• Simplify ancestry like we do now. Then, b will be a parent of a only.

Either way, the behavior will be surprisingly different from what happens in the following tree, where the same command can work fine.

    @  c
    ◉    b
    ├─╮
    │ ◉  a
    ├─╯
    ◉  base
    ◉  notroot
    ◉  root

I ran into this with the tests I wrote for #2650 once I tried fixing that bug.

Update: This is now tested in #2656. Right now, the behavior is independent of whether notroot exists, but the expected behavior is different.

[martinvonz]

Good find. I think the current error from the Git backend seems appropriate in this case. It's only a limitation of the Git backend after all. It's also a rare case even when using the Git backend. I don't think it should affect our decision. I don't mind answering questions from the presumably few users who run into it. What do you think?

[ilyagr]

Right now, I don't really know, but your vote for an error message is helpful.

I agree that this will be rare for users doing real work. However, I can think of two situations where this seems unfortunate and likely to confuse people: when writing tests, and when somebody experiments with jj in a toy repo.

I think a more detailed hint with the error message might help, but I'm not sure what it should say.

This also affects jj abandon, of course.

[ilyagr]

Also, right now, the error looks extra-scary. We'd probably want to make it look friendlier.

Internal error: Merge failed: Backend error: Error: The Git backend does not support creating merge commits with the root commit as one of the parents.

It shouldn't be too hard to special-case this specific error. I'm not sure if it's worth it to try to do something more elegant to do with it.

[bnjmnt4n]

Following #3551, can this issue be closed? It looks like all the todo items have been addressed, unless I'm mistaken.

[martinvonz]

I think so, yes. Ilya can reopen if he feels differently.