Representation of conflicts in the commit graph

[jonathantanmy2]

AFAIK, currently:

• A conflicted commit has a synthetic root tree with multiple subtrees that each point to a side of the conflict (plus one more subtree for the autoresolution), and extra commit headers that indicate that the root tree must be interpreted in this way.
• The user cannot git checkout directly, but must instead use an "Edit" feature in the GUI (not sure if there's an equivalent in the CLI).
• After using the "Edit" feature, the user must click something in the GUI to tell GitButler that they are done resolving the conflict.

As @Caleb-T-Owens , @krlvi , and I discussed, what we can do instead is:

• A conflicted commit has the autoresolution tree (with conflict markers) as its root tree. A mapping from commit ID to the trees representing the sides of the conflicts is stored elsewhere - maybe a reference or in a sqlite table. If in a sqlite table, the mapping can be provided to Git through the gc.recentObjectsHook (added sometime in 2023, but OSes and distributions are sometimes late to pick up new versions of Git) to prevent these trees from being GCed. No extra commit headers are necessary, since the mapping is already stored elsewhere.
• The user can git checkout directly.
• AFAIK there is an existing effort to reduce or eliminate the dependence on the "workspace commit" that is a merge of all branches. When Git branches can be operated on directly (by Git or other tools), the user can also resolve the conflicts directly (through git rebase -i or the still-in-progress techniques that Elijah Newren demoed in Git Merge 2025), without a separate step to tell GitButler that they are done resolving the conflict. When this happens, since the commit ID changes, the mapping (from commit IDs) mentioned above no longer applies. The commit is also "clean" in the sense that there are no extra irrelevant commit headers.

An interesting point in the solution space, but that probably doesn't work:

• Instead of storing a mapping from commit ID to the trees representing the sides of the conflicts, generate the autoresolution tree (with conflict markers) with enough information in it such that all sides can be generated from it. This is tricky, although probably not insurmountable, for file-directory conflicts, but I think we have a better solution as described above so we don't need the trickiness of this solution.

After the meeting, I thought of a possible way to proceed:

• Teach the "Edit" feature to support both the existing-style conflicted commits and the new-style conflicted commits - in the latter case, the "Edit" feature detects this situation and is a no-op.
• Teach whatever generates the commits (the rebase engine?) to generate new-style conflicted commits. We probably only need to be able to read existing-style conflicted commits, and not need to know how to generate them.
• Since the "Edit" feature is now a no-op, there is a benefit to the user that the user no longer needs to click "Edit", but the user still needs to tell GitButler that editing is done (so that the rebasing of descendant commits and the "workspace commit" etc. can be done).
• In parallel, we should reduce or eliminate the dependence on the "workspace commit". Once that is done, (hopefully) the user will also no longer need to tell GitButler that editing is done, creating a more seamless interoperability between Git and GitButler.

[krlvi]

This all sounds in line with my understanding as well.

In general, it would be neat if in the future it becomes possible to resolve conflicts without entering "edit mode".

I imagine if we were to look into implementing this, a point of integration is going to be the part of the code which performs "cherry pick" within the new graph based Rebase Engine. @Caleb-T-Owens would it be possible to point out / link to the relevant parts of the code?

[Caleb-T-Owens]

The main cherry pick implementation can be found here: https://github.com/gitbutlerapp/gitbutler/blob/master/crates/but-rebase/src/graph_rebase/cherry_pick.rs#L44.

For writing out either unconflicted we have the function commit_from_unconflicted_tree and for conflicted commit_from_conflicted_tree in the same file.

When we go to expand the conflicts we probably will do something around there.

There was also the case that we talked about a little bit where we fail to cherry-pick a merge commit but either the old or the new parents end up conflicting. This case you can see on line 66 of cherry_pick.rs. This is the kind of conflict that isn't currently represented by our system & the class of conflict the workspace commit would likely end up in.

---

I was thinking that it doesn't really make sense to start changing the conflict representation while we have two different rebase engines, primarily while the old one relies on functions like update_workspace_commit, since we're aiming to get rid of functions like that soon. To me it seems reasonable to first move to a non-legacy rebasing world & then work on improving conflicts.

For this reason I was wondering if it might make sense to paralleize working on rolling out & finalising test cases for the rebase engine, before we then change how conflicts are represented?

WDYT @jonathantanmy2 @krlvi

[jonathantanmy2]

I was thinking that it doesn't really make sense to start changing the conflict representation while we have two different rebase engines, primarily while the old one relies on functions like update_workspace_commit, since we're aiming to get rid of functions like that soon. To me it seems reasonable to first move to a non-legacy rebasing world & then work on improving conflicts.

For this reason I was wondering if it might make sense to paralleize working on rolling out & finalising test cases for the rebase engine, before we then change how conflicts are represented?

Yeah it makes sense to migrate to only one rebase engine, then work on a new conflict representation. Let me know if there are any tasks that I can look at in parallel to what you're doing.

[Byron]

It's awesome to see this kicked off! Super high value, and a feature that needs to work extremely well to prevent great surprises.

Some notes from me:

A conflicted commit has the autoresolution tree (with conflict markers) as its root tree.

That's interesting, as I at least imagined that JJ would make these go away so the user has something to work with. But maybe that's not the case and instead it makes it obvious that a conflict is now committed, and I realise that I really have to catch up on JJ here to get some intuition of its prior art. I'd be glad to receive some education here.

Storing metadata elsewhere should be easy with but-db, but I wonder why storing everything in commit-headers was discarded? Wouldn't that be the most robust way to keep the data we'd need to facilitate a resolution? Even when other tools are used, if they rewrite the commit we'd probably be able to tell and could clear our metadata, or deal with it gracefully UX wise.

This is still intermediate, for now I only read the PR text itself.

• Teach the "Edit" feature to support both the existing-style conflicted commits and the new-style conflicted commits - in the latter case, the "Edit" feature detects this situation and is a no-op.

This would require a new-style representation of conflicts to exist. When thinking about that, I remembered that conflicts from merges and cherry-picks typically have their own semantics, i.e. the method that the conflict was created with seems to matter. This seemed true when basing operations off one or more commits that are conflicted themselves.
In theory, and at least for now, there is only cherry-picks that create conflicts, as creating the workspace merge commit isn't allowed to do so.

In parallel, we should reduce or eliminate the dependence on the "workspace commit".

I can't yet fathom how that would look like, maybe we can sketch that in greater detail?

On gc.recentObjectsHook

gc.recentObjectsHook sounds great, and it will be interesting to find a way to return these in such a way that we don't accidentally hold on to them for too long. And I see how simply storing these in the database seems like a nice prospect in comparison to figuring out which branches to traverse to look at commits. The latter is still cheap as without a commit-graph cache (git standard feature), we'd have to partially decode the commit anyway to get the parents. Then it basically costs nothing to also look at the header information for conflict related metadata. But it would also mean that a commit-graph can't be used if the but-graph is created for the purpose of finding conflicted commits and their related objects.

On non-GitButler UX for conflict resolution

I still can't really imagine how that would work as the tools that I know would need an index to record the conflicts to resolve. Some tools might be able to help with conflict markers, but that doesn't ever extend to conflicts that happened to the tree itself, i.e. modification vs deletion. So without GitButler, I can't see how other tools can resolve anything.

On GitButler UX for conflict resolution

Right now, we depend on "Resolve Conflict" and "Resolution done" clicks in the UI. When resolving a conflict, in future it should be enough to checkout the conflicting commit and we set the index to match. This would allow tooling to work just like it does now. Once everything is resolved, the user currently clicks in the UI to trigger the rebase process and switching back to the workspace tip (which could be a normal branch in single-branch mode).
In future, it seems we should be able to respond to changes in Git itself and allow things like git commit to work as expected, as it's a filesystem event that GB could respond to.
While we are not particularly clever about it, it seems that we should be able to at least detect that a commit was made, and handle that gracefully. As it's basically just a commit on a detached HEAD, maybe GitButler could be helpful if it could remember the branch that that user was on. With that information the new commit could be re-integrated, after all the commit that it replaces will have the same parents.
To me it looks like there is a chance that the 'resolve conflicts' workflow can be done with only one click, the click the tells the UI to restore the conflicting index and possibly change HEAD.

(limited) JJ interop?

If JJ is backed by a Git repository, they also put conflicting commits in places that are visible from Git. How do these look like? Is there something we can just use for the sake of being more compatible with the only (Git-backed) tool we know that can do similar things?
Maybe it's complete nonsense, but I'd hope we don't miss an opportunity either.

[jonathantanmy2]

A conflicted commit has the autoresolution tree (with conflict markers) as its root tree.

That's interesting, as I at least imagined that JJ would make these go away so the user has something to work with. But maybe that's not the case and instead it makes it obvious that a conflict is now committed, and I realise that I really have to catch up on JJ here to get some intuition of its prior art. I'd be glad to receive some education here.

JJ does not make them go away and makes it obvious that a conflict is committed, but still gives the user something to work with. You can see how to resolve conflicts here: https://steveklabnik.github.io/jujutsu-tutorial/branching-merging-and-conflicts/conflicts.html#resolving-the-conflict (earlier in the article, Steve describes how JJ tells the user that there's a conflict).

Storing metadata elsewhere should be easy with but-db, but I wonder why storing everything in commit-headers was discarded? Wouldn't that be the most robust way to keep the data we'd need to facilitate a resolution? Even when other tools are used, if they rewrite the commit we'd probably be able to tell and could clear our metadata, or deal with it gracefully UX wise.

I think it's less robust to store them in the commit headers, actually. Storing in a db keyed by commit ID means that the information is automatically dropped when the commit ID changes, but storing in a commit header means that we need a resolution step if the commit changes from what it was originally.

• Teach the "Edit" feature to support both the existing-style conflicted commits and the new-style conflicted commits - in the latter case, the "Edit" feature detects this situation and is a no-op.

This would require a new-style representation of conflicts to exist. When thinking about that, I remembered that conflicts from merges and cherry-picks typically have their own semantics, i.e. the method that the conflict was created with seems to matter. This seemed true when basing operations off one or more commits that are conflicted themselves. In theory, and at least for now, there is only cherry-picks that create conflicts, as creating the workspace merge commit isn't allowed to do so.

IIRC mathematically, merges and cherry-picks are the same. To perform a merge, you need 2 sides and a base. In a merge, the sides are the merge arguments and the base is the youngest common ancestor of the sides. In a cherry-pick, the sides are the commit you're cherry-picking and the destination, and the base is the parent of the commit you're cherry-picking. I don't know if the information is presented differently to the user, though, depending on the type of operation.

In parallel, we should reduce or eliminate the dependence on the "workspace commit".

I can't yet fathom how that would look like, maybe we can sketch that in greater detail?

I was imagining a world where you could switch from a single branch to workspace commit and back repeatedly. So you could switch to a single branch, make changes there (e.g. add a commit or even git rebase -i), and then run a command like but checkout-workspace and it will create a new workspace commit that merges all the branches. When I said "dependence", I thought that maybe the list of branches was stored somewhere (so that we would not depend on the workspace commit - instead, we can recreate it at will), but if not, maybe we could check the existing workspace commit's commit message to see what the names of the branches are, and do a reconciliation step.

On gc.recentObjectsHook

gc.recentObjectsHook sounds great, and it will be interesting to find a way to return these in such a way that we don't accidentally hold on to them for too long. And I see how simply storing these in the database seems like a nice prospect in comparison to figuring out which branches to traverse to look at commits. The latter is still cheap as without a commit-graph cache (git standard feature), we'd have to partially decode the commit anyway to get the parents. Then it basically costs nothing to also look at the header information for conflict related metadata. But it would also mean that a commit-graph can't be used if the but-graph is created for the purpose of finding conflicted commits and their related objects.

Makes sense.

On non-GitButler UX for conflict resolution

I still can't really imagine how that would work as the tools that I know would need an index to record the conflicts to resolve. Some tools might be able to help with conflict markers, but that doesn't ever extend to conflicts that happened to the tree itself, i.e. modification vs deletion. So without GitButler, I can't see how other tools can resolve anything.

I was thinking of git rebase -i and manually editing the conflict marker-filled files in a text editor. I don't know offhand if merge resolution tools like Meld need the sides of the conflicts in the Git index somewhere, but if that's the case, we could also add a but rebase -i later that puts the sides of the conflicts in the Git index.

On GitButler UX for conflict resolution

(I haven't really looked at the UI so I won't comment)

If JJ is backed by a Git repository, they also put conflicting commits in places that are visible from Git. How do these look like? Is there something we can just use for the sake of being more compatible with the only (Git-backed) tool we know that can do similar things? Maybe it's complete nonsense, but I'd hope we don't miss an opportunity either.

IIRC the conflicting commit's root tree has a few subtrees representing the sides of the conflicts, which means that if you git checkout one of them, you won't get what you expect. That's not incompatible with the Git data format, but it's incompatible with Git and Git tools (well, unless first-class conflicts are adopted in Git itself, but I think it's only at the discussion phase https://lore.kernel.org/git/aOQV%2Fja9Ltw%2FbTP3@nand.local/ ).

[Byron]

Thank you!

JJ does not make them go away and makes it obvious that a conflict is committed, but still gives the user something to work with. You can see how to resolve conflicts here: https://steveklabnik.github.io/jujutsu-tutorial/branching-merging-and-conflicts/conflicts.html#resolving-the-conflict (earlier in the article, Steve describes how JJ tells the user that there's a conflict).

I think I will just have to try it myself and create a conflict in the middle of a branch. The example has it on top, and immediately goes to resolving it which might then make the conflict visible (if it wasn't visible before). What I want to find out is if a conflict happens in the middle of a branch, do we see conflict markers in the commits that follow?
And when we switch head to the conflicting commit, will it show the conflicts automatically? Or would it hide them until we enter 'resolve' mode?

I think it's less robust to store them in the commit headers, actually. Storing in a db keyed by commit ID means that the information is automatically dropped when the commit ID changes, but storing in a commit header means that we need a resolution step if the commit changes from what it was originally.

It is my understanding that we need an extra step to resolve a conflicting commit. The first step is to make the conflicts visible, and the second would be to tell it they are resolved.
But I think it's fine to leave it there as we could investigate this more on a higher-bandwidth channel and when the time is ripe.

IIRC mathematically, merges and cherry-picks are the same. To perform a merge, you need 2 sides and a base. In a merge, the sides are the merge arguments and the base is the youngest common ancestor of the sides. In a cherry-pick, the sides are the commit you're cherry-picking and the destination, and the base is the parent of the commit you're cherry-picking. I don't know if the information is presented differently to the user, though, depending on the type of operation.

When I was working on this a while ago, I noticed that it wasn't clear to me which side is the right side to pick when a conflicting commit was in one or more of the operands of a cherry-pick. It felt. I am super happy to just skip over this though as it was all vague and by now everything has changed.

I was imagining a world where you could switch from a single branch to workspace commit and back repeatedly. So you could switch to a single branch, make changes there (e.g. add a commit or even git rebase -i), and then run a command like but checkout-workspace and it will create a new workspace commit that merges all the branches. When I said "dependence", I thought that maybe the list of branches was stored somewhere (so that we would not depend on the workspace commit - instead, we can recreate it at will), but if not, maybe we could check the existing workspace commit's commit message to see what the names of the branches are, and do a reconciliation step.

Thanks so much, this is super interesting! With the metadata attached to the gitbutler/workspace, there is enough information to 'catch up' on stacks that have changed and merge them back in. This shouldn't be a problem, and the information needed to do that exists today.

I was thinking of git rebase -i and manually editing the conflict marker-filled files in a text editor. I don't know offhand if merge resolution tools like Meld need the sides of the conflicts in the Git index somewhere, but if that's the case, we could also add a but rebase -i later that puts the sides of the conflicts in the Git index.

I don't think this will work, unfortunately. While we can store the 'conflict' of a blob in the blob itself, we can't do the same for tree-based conflicts. So I think there is no way around having but support for reproducing the actual conflicts in the index as well as possible. This could also allow the user to select different auto-resolutions for instance.

IIRC the conflicting commit's root tree has a few subtrees representing the sides of the conflicts, which means that if you git checkout one of them, you won't get what you expect. That's not incompatible with the Git data format, but it's incompatible with Git and Git tools (well, unless first-class conflicts are adopted in Git itself, but I think it's only at the discussion phase https://lore.kernel.org/git/aOQV%2Fja9Ltw%2FbTP3@nand.local/ ).

I see, thanks a lot! My feeling is that they would have used headers for extra trees if they could have, but git gc was in the way.

The reference to the first-class conflicts discussion in Git is also very interesting, let's see if it ever happens (and then needs to be supported 😅).

[schacon]

Sorry to step backwards here, but can someone write up the problem that we're trying to solve with a new approach to the conflicted commit format?

My understanding is that it has to do with single-branch mode and having a conflicted commit at the tip, which can't be checked out in a good way. Is there another use case that becomes problematic with the current storage format?

The thing that's somewhat nice about the un-checkout-able format is that it's very clear that it's a special style of commit. If we store the partially-resolved tree as the root tree and metadata elsewhere then it seems like it's much more likely that people may accidentally push a partially resolved tree containing conflict markers somewhere and not realize that it's in a poor state and how to fix it. If it's a bunch of subtrees in a totally different format with a README that explains why it looks this way, then it's incredibly clear that this commit should not have been pushed somewhere.

I can go on, but it's possible that I'm missing some context. Before deciding on a new conflict format, can we write up what issues we're trying to solve with an evolution of the format?

[Byron]

Thanks for chiming in! For a moment I thought we were just running into a direction without really knowing why, and the issue doesn't necessarily provide strong motivational arguments.

My understanding is that it has to do with single-branch mode and having a conflicted commit at the tip, which can't be checked out in a good way. Is there another use case that becomes problematic with the current storage format?

That's a big one.
Another issue I noticed in interactions with users is that they are completely confused when this happens. It's more of a major surprise that prevents any clear thought. It's like being in a burning plane and having to read the manual to find the parachutes.

From that I learned that under no circumstances must users be able to checkout and ideally push such a conflicting tree.

Having a fully resolved tree seemed like the solution to at least have a less surprising variant of this, but… the plane is still going down, it's just neatly hidden from you.

And maybe here it's a great idea to take a step back and ask: is there a way to prevent users from interacting with conflicting commits without scaring them?

JJ solves this by having complete autonomy over what the user checks out. We don't have that luxury, and plain Git can always interact with conflicted commits.
But what if… it couldn't? What if it would refuse to check it out because the tree is malformed? What if, for instance, our metadata tree would contain an entry that is of type blob, but instead has a tree object linked to it, or vice versa. I believe that such a tree will not be accepted when it's pushed, nor will it be viable to check it out. Unless, of course, GitButler is used which just so happens to know how to deal with it.

I didn't validate that yet, but could if you think it's worthwhile.