Don't introduce new redundant ancestor merges when auto-rebasing

[martinvonz]

Description

PR #3080 fixed issue #2600. In that bug, we started with something like this:

@    o martinvonz@google.com 2024-08-27 16:00:09 d7f841e7
├─╮  (empty) C
○ │  zu martinvonz@google.com 2024-08-27 15:59:50 6ef5d8e3
├─╯  (empty) B
○  q martinvonz@google.com 2024-08-27 15:56:34 57a04050
│  (empty) A
◆  zz root() 00000000

Now (before PR #3080), simply running jj describe -m A2 -r q would result in o losing q as parent. That's what the PR fixed.

However, perhaps we're too careful not to change the shape of the graph now. In particular, let's say we have this history:

@    t martinvonz@google.com 2024-08-27 16:02:39 616bc8fc
├─╮  (empty) (no description set)
│ ○  zu martinvonz@google.com 2024-08-27 15:59:50 6ef5d8e3
│ │  (empty) B
○ │  o martinvonz@google.com 2024-08-27 16:02:32 368b7414
├─╯  (empty) C
○  q martinvonz@google.com 2024-08-27 15:56:34 57a04050
│  (empty) A
◆  zz root() 00000000

If we now abandon zu, we end up with this:

@    t martinvonz@google.com 2024-08-27 16:02:57 27557d7d
├─╮  (empty) (no description set)
○ │  o martinvonz@google.com 2024-08-27 16:02:32 368b7414
├─╯  (empty) C
○  q martinvonz@google.com 2024-08-27 15:56:34 57a04050
│  (empty) A
◆  z root() 00000000

In this scenario, the auto-rebase code introduced a new redundant ancestor merge. Perhaps we should at least avoid that. We already avoid it if it results in multiple identical parents.

Specifications

• Platform: all
• Version: 0.20.0

[ilyagr]

I agree that this is annoying in practice. I find it difficult to define a behavior that would be consistent and would distinguish "new" redundant ancestor merges from "preexisting" ones.

The best I can do is this. If all of the following are true:

1. we are auto-rebasing A from parents X, Y, Z to parents X', Y', Z'
2. one of the parents, X, is rebased to X' where this is not an auto-rebase (X was not rewritten to X')
3. X' is the ancestor of one of the other new parents Y' or Z'

then we forget the ancestor X'.

This seems to do the "right" thing both in your example of abandoning zy and in the example of describing q, but it also seems a bit complex and unwieldy. Do you think it's worth solving the annoyance?

---

Another option would be to special-case rebases that happen because of jj abandon or jj rebase -r, to the children of the removed commits. At the moment, this seems like a better option to me. Both commands could get a --no-simplify-ancestry option to keep the current behavior (which I consider "correct" in the theoretical sense even for these commands, in spite of the fact that the user would usually not want it).

Yet another idea I had would be to have a special command to simplify ancestry, but hopefully we can avoid that.

[martinvonz]

I find it difficult to define a behavior that would be consistent and would distinguish "new" redundant ancestor merges from "preexisting" ones.

What I had in mind was simply to check if a given change has redundant ancestor merges after the rebase and did not have it before.

[ilyagr]

Ah, I see. It requires iterating over all the auto-rebased commits an extra time, I didn't think of that. You'd also have to be careful to do it in a way that doesn't break jj new X X----.

Some inconclusive thoughts: I do consider the current behavior more theoretically correct and in some ways easier to reason about. I'm mildly worried about side effects of trying to do a simplification everywhere, and I'm wondering about having an option to disable it. For these reasons, I'm still tempted to consider only doing this simplification for a small number of commands and only for the immediate parents of (say) the commits being abandoned by jj abandon, so that the behavior changes only locally around the commits we're explicitly touching.

I'm not sure which is best at the moment, and which would require fewer corner cases in the implementation. I haven't come up with a compelling example in either direction yet.

In any case, I don't necessarily think of this as a bug, but I do think that this is an inconvenience we should try to address if possible.

[martinvonz]

Some inconclusive thoughts: I do consider the current behavior more theoretically correct and in some ways easier to reason about. I'm mildly worried about side effects of trying to do a simplification everywhere, and I'm wondering about having an option to disable it.

I feel the same way, FWIW. I'm not at all sure we should make the change proposed here.

[msuozzo]

I just ran into this issue. My jj log set excluded the already-merged ancestors which led to the confusing situation of seeing a weird commit with 3 parents and a nonsensical diff on github and a jj state that looked like a normal single-parent change.

All that said, I definitely understand the current reticence here to do anything "automagical" during a rebase. The complexities of these cases certainly seems to warrant caution but, at the same time, it feels the common case should still be tractable to address.

I'm not that familiar with jj but would it be possible to use immutability as a factor in whether to dissociate a parent from a rebased commit? i.e. when A's parents B and C are linearized to A -> B -> C, C will now be immutable and could be removed as a parent of A.