(Technical) Plan for rewrite API

[ilyagr]

Here is a draft my thoughts of where we could go with the rewrite API after #2737 and #2738. This is in a draft state right now, I wrote up my thoughts rather quickly.

The idea is to slowly move logic for the tricky parts of rewrites (especially edge cases like weird ancestry) to the lib crate. It's not entirely obvious what the primitives for the more complicated rewrite operations should be so that one can wrap their mind around them. This write-up is an attempt to pick such primitives.

I hope to reuse pieces of the DescendantRebaser implementation to decrease duplication.

WDYT, @yuja, @martinvonz? Is there a way to have a simpler mental model that this? Did I miss some important use-case?

Use cases to support

1. Normal rebase/abandon
2. jj split
3. jj rebase -r -d descendant
4. jj new --after or jj rebase -r --after
5. jj new --before or jj rebase -r --before (seems simple on second thought)

In all of these cases, the CLI crate should care as little as possible about the possible weird ancestry (#2600, #2650 ) in the commit graph.

Design

Step 1

I assume familiarity with the current MutRepo design.

I propose adding a bit of config to each rewritten commit, called RemainingRewriteActions below. Then, we add customized options of the current API:

impl MutRepo {
  // TODO: Rename all of these functions
  fn rewrite_commit(&mut self) -> CommitBuilder {
    rewrite_commit_customized(self, Default::default())
  }
  fn rewrite_commit_customized(&mut self, remaining_actions: RemainingRewriteActions) {
    // Use callback to be called by CommitBuilder::write()
    // as discussed in
    // https://github.com/martinvonz/jj/pull/2737#discussion_r1435614437
  }
  fn record_rewritten_commit_customized(&mut self, from: CommitId, to:CommitId, purposes: RemainingRewriteActions) {todo!() }
  fn record_abandoned_commit_customized(&mut self, commit: CommitId, purposes: RemainingRewriteActions) { todo!() }

  // The `set_rewritten_commit` function I introduced in a recent PR would be again removed. 

  // Rename to `finish_current_rewrite?`
  fn rebase_descendants(&mut self) {
    // Change DescendantRebaser to follow the config in `RemainingRewriteActions`
  }
}

// All default to `true`.
// If both are `false`, calling `record_rewritten_commit_customized` is a no-op.
pub struct RemainingRewriteActions {
  pub move_branches: bool,  // See UPDATE below
  pub rebase_descendants: bool,
}

UPDATE: Instead of move_branches, we probably want abandon_original: bool. This controls another essential piece of rebase_descendants functionality: if abandon_original is false, the original commit is not abandoned and branches are not moved. We could in principle allow moving branches without abandoning commit, but I don't think there's a need right now. The rest of this write-up should work unchanged with abandon_original replacing move_branches everywhere.

Normal rebase/abandon

No significant changes to their implementation

jj split

Rewrite jj split to use

rewrite_commit_customized(RemainingRewriteActions {
    move_branches: false,
    rebase_descendants: false
})

to make the parent commit. As a result, DescendantRebaser should ignore this rewrite. Then, split would use a normal rewrite_commit for the child commit.

jj rebase -r X -d descendant

Instead of the current custom code, use

record_abandoned_commit_customized(
  X,
  RemainingRewriteActions {
    move_branches: false,
    rebase_descendants: true
  }
);
rebase_descendants()

to rebase the descendants of X onto the parents of X before moving X itself (instead of current custom code).

The above code should change

graph BT
  A1 --> X
  A2 --> X
  X --> B1
  X --> B2

Loading

to

graph BT
  A1 --> X
  A2 --> X
  A1 --> B1
  A2 --> B1
  A1 --> B2
  A2 --> B2

Loading

without moving any branches at X.

Afterwards, rebase can actually rebase X to its destination.

rebase_descendants should ensure that this works even if B2 is a descendant of B1.

Step 2: --after

Change RemainingRewriteActions::rebase_descendants from a bool to and enum:

enum RebaseDescendants(
  All,
  None,
  AllExcept(Vec<CommitId>),
  // Only(Vec<CommitId>)  // Possibly; not sure I have an application at the moment.
)

Let's say we start with

graph BT
  X
  A1 --> B1
  A1 --> B2
  A2 --> B1

Loading

and try jj rebase -r X --after A1.

If X was not a descendant of A1, we could rewrite A1 to X if X is an ancestor, but troublesome if it is a descendant.

Instead, rebase X onto A1 as usual to get

graph BT
  A1 --> B1
  A1 --> B2
  A1 --> X
  A2 --> B1

Loading

Then use

record_rewritten_commit_customized(
  A1, X,
  RemainingRewriteActions {
    move_branches: false,
    rebase_descendants: RebaseDescendants::AllExcept(X)
});
rebase_descendants();

This should result in

graph BT
  A1
  A2
  B1
  B2
  A1 --> X
  X --> B1
  X --> B2
  A2 --> B1

Loading

(jj new --after A1 can be done similarly)

rebase_descendants should ensure that this works even if B2 is a descendant of B1.

--before

This seems much easier than --after and does not use the new APIs.

Let's start with the same graph,

graph BT
  A1 --> B1
  A1 --> B2
  A2 --> B1

Loading

and try jj new --before B1.

We'd create a new commit X with parents(X) = parents(B1):

graph BT
  A1 --> B1
  A1 --> B2
  A2 --> B1
  A1 --> X
  A2 --> X

Loading

Unless I missed something, we only need to now do a simple rebase of B1 onto X. (I was originally thinking about using RebaseDescendants::Only)

Step A (orthogonal to the above)

Extract the relevant MutRepo operations to a wrapper called IncompleteRewrite that holds an &mut MutRepo reference. IncompleteRewrite::drop calls an analogue of rebase_descendants.

As a result, when you have a MutRepo object, you can be sure it does not need a rebase_descendants to be in a consistent state.

This is my interpretation of @yuja's suggestion from #2737 (comment).

Step B (orthogonal to the above)

Remember parent_mapping in the rewrite API. Until this happens, the CLI crate would need to call rebase_descendants_return_map and keep track of the parent mapping.

Step C (orthogonal to the above)

Consider consolidating currently existing RebaseOptions and RemainingRewriteActions.

[joyously]

Does this include the case of undo after any of these scenarios?

[martinvonz]

Yes. undo is based on the operation log, which records a snapshot of the repo at various points in time. How individual commands work doesn't matter.

[martinvonz]

Thanks for starting this discussion!

We should also keep in mind the use case of parallelizing commits (#1079, #2274). Also, you didn't explicitly mention the pretty basic
case of jj rebase -b x -d y.

Another important use case that DescendantRebaser was designed for is to rebase descendants after fetching from a remote where some commits have been rewritten. There are lots of tests for cases like that in test_rewrite.rs.

The new API seems more complicated to me at first glance. It would be useful to explain how it makes things simpler. I think the main benefit is that the CLI crate will be able to simply call mut_repo.rebase_descendants() in each of the use cases. Or at least I think that would be a reasonable goal; it would nice to not have to manually rebase descendants and add the counts like we do here. Is that the main motivation for this work?

Actually, since your change to jj split to call set_rewritten_commit(), we can remove the manual rebase_descendants() there. However, that would mean printing the message about rebased descendants before the messages about the new commits, because otherwise the new commit would be divergent with the original commit until the rebase happens. Maybe it's okay to reorder the messages like that. Or maybe we would want to have a tx.rebase_descendants() separate from tx.finish(), so we can print the messages after resolving the divergence.

[yuja]

We'll also need to keep in mind that -r may be extended to accept multiple revisions (like X|Y|Z or X::Y.) I think it would probably work if the -r sets are virtually abandoned (as you mentioned in the jj rebase -r X -d descendant example.)

I'm dubious about AllExcept(), which might greatly increase the complexity? I think it's okay to do the rebase in multiple steps (e.g. virtual abandon, rebase_descendants(), rebase the -r revisions) if that helps to split it to smaller problems.

[ilyagr]

We'll also need to keep in mind that -r may be extended to accept multiple revisions (like X|Y|Z or X::Y.) I think it would probably work if the -r sets are virtually abandoned (as you mentioned in the jj rebase -r X -d descendant example.)

I think that should work, yes. If all goes to plan, jj abandon and this part jj -r multiple_commits could probably be made to look very similar, differing only in that the latter would use the abandon_originals: false option.

I'm dubious about AllExcept(), which might greatly increase the complexity?

From the perspective of the implementation, I don't see a reason that should be overly complex, but I might be missing something. This certainly does increase complexity from the perspective of having a simple API.

As I said, my problem with doing rebases in many steps and exposing this to the CLI crate is that then there are annoying edge cases that have to be dealt with every time. jj rebase --after seems full of them at a glance, so I wanted to share as much of its code as possible with similar functionality from DescendantRebaser. Maybe there's some better way, or just a simpler way to encapsulate that complexity.

I'm currently thinking AllExpect would be rarely used (only for --after?), but I'm not entirely sure.

[arxanas]

For what it's worth, git-branchless uses a multi-phase rewrite system. This is for a few reasons:

• Can be more efficient than doing multiple rebases in sequence (O(n) vs O(n^2) if you have to rewrite many of the same descendants).
• Rebases are not guaranteed to succeed, so we can't necessarily decompose the operation directly into simpler (commutative) steps.
• The rebase needs to execute in-memory, but also alternatively compile to Git's on-disk rebase format.

There are a few methods in the RebaseBuilder interface: https://github.com/arxanas/git-branchless/blob/81e298dad0bd0335c4d330816c97fab38a24524a/git-branchless-lib/src/core/rewrite/plan.rs#L1016-L1094

These eventually compile into a constraint graph (that operates on commits that will be rebased, but haven't been yet). There are three kinds of constraints at present: https://github.com/arxanas/git-branchless/blob/81e298dad0bd0335c4d330816c97fab38a24524a/git-branchless-lib/src/core/rewrite/plan.rs#L575-L596

Admittedly, I'm not sure that the design is good, for a few reasons:

• The constraint solver doesn't look at the DAG as much as it could. I think some of the implementation could be simplified if we moved some of the complexity to a lower abstraction level, as per the next point.
• Looking at it now, I think a constraint that specifies the new children of a node would be sensible. I think it didn't exist because I was thinking in overly-DAG-centric terms, so only rebasing/reparenting. It would be logical to express the children constraint at the top layer of abstraction and compile it to only rebasing relationships later as part of lowering.

[ilyagr]

@arxanas

Re older comment:

Perhaps the interface for rebasing should accept both any number of parent commits and any number of child commits? It looks like it only accepts a number of parent commits right now.

This is present in my suggestion, but looks a little awkward. It would look something like:

// Omitting details
let new_commit = mut_repo.rewrite_commit_customized(
    old_commit,
    parents,
    // `AllExcept` is slightly different from what you suggested, but we
    //  could also have `Only(list_of_children)` if we want/need.
    rebase_descendants: AllExcept(something)
).write();
mut_repo.rebase_descendants();

I currently only have one use-case in mind for this (--after), so I thought that would be OK to look awkward. @yuja was dubious about AllExcept, though.

Re newer comment:

Thanks, that's very interesting and helpful! I forgot that git-branchless has to deal with all the same issues!

I'm looking at it pretty slowly. Generally, your design seems to be quite parallel to what I was thinking, except for a nice and clean separation between to planning stage and the doing stage (👍 I definitely plan to look at that in more detail). It also adds a move_subtree primitive.

For everyone's reference, here's the CLI part of jj move --insert that would be analogous to jj rebase --after:

https://github.com/arxanas/git-branchless/blob/81e298dad0bd0335c4d330816c97fab38a24524a/git-branchless-move/src/lib.rs#L393-L400

https://github.com/arxanas/git-branchless/blob/81e298dad0bd0335c4d330816c97fab38a24524a/git-branchless-move/src/lib.rs#L416-L475

Some unbaked thoughts: I dislike the way the CLI code has to consider each special case separately (are we rebasing to a descendant? I would prefer for this complexity to also be hidden in a lib crate.). However, this allows a simpler API which could be worth it. I haven't yet thought about it enough to have an opinion on whether encapsulating such complexity is doable with git-branchless's design. I'm also curious how you deal with the "weird ancestry" cases, but haven't looked at that part yet.

[arxanas]

I agree that the CLI code shouldn't have to worry about it, and I think that it should eventually go into the lib code.

This is mostly a reiteration of what I said above, but I suspect that we'll want to transform the caller constraints through some number of phases.

• You can see in the git-branchless code that the caller can do a few calls in sequence on the RebasePlanBuilder. Thus, you can specify more complicated operations without explicitly needing a RebaseDescendants enum (of course, you can use one internally).
  • By default, if you move_subtree, it moves all the descendants as well, but if you follow up with move_subtree on a descendant of the original commit to rebase that descendant on top of its original parents, then both constraints should apply (and there will simply be an "abandoned" section of the resulting graph).
  • Conceivably some other primitives like preserve could be added to fix a specific commit in place, if we need something like that?
  • That level of abstraction doesn't let us address children directly; I guess move_range is most similar to excising a certain section of the graph.
• If we support moving children at the highest level of abstraction, then I would guess that a lower level of abstraction would convert the parent+children constraints into a set of parent-only constraints.

So maybe it would be a good first step to identify how many phases we'll have and what kind of level of abstraction each phase will operate on.

[yuja]

Step A (orthogonal to the above)

Extract the relevant MutRepo operations to a wrapper called IncompleteRewrite that holds an &mut MutRepo reference. IncompleteRewrite::drop calls an analogue of rebase_descendants.

As a result, when you have a MutRepo object, you can be sure it does not need a rebase_descendants to be in a consistent state.

This is my interpretation of @yuja's suggestion from #2737 (comment).

I wasn't considering about it that deeper. My point was just low-level pub methods could be hidden in that way if really needed.

[ilyagr]

I see, perhaps that's a separate direction then. It's optional: I think it'd be nice, but I'm not sure it's necessary for anything specific at this point. It might simplify the code using rebase_descendants, but I haven't thought it through entirely.

[ilyagr]

A note about how my plans relate to this. They are rather vague at the moment, so suggestions are welcome in this area as well.

• I feel like I already have some food for thought to digest before I start implementing anything, e.g. look at @arxanas 's design. It might take some time, so there's no rush.
• OTOH, I'm not sure how objective this feeling is, but I do feel blocked on either either jj rebase -r A -d descendant_of_A can panic if the graph has weird ancestry. #2650 or jj rebase -r should be able to rebase a commit onto its descendant, insert commits before or after another commit (now AKA better tools for reordering commits part 1) #1188 (rebase -r --after) by figuring this out.
• The cleanup in Refactor MutRepo to make DescendantRebaser private (pt 2) #2738 is probably going to be useful no matter what we do next, since it decreases the API complexity for now. It's a no-op, though, so there's also no rush.