just playing with tangled
ilyagr.bsky.social
1# First-class conflicts
2
3## Introduction
4
5Conflicts can happen when two changes are applied to some state. This document
6is about conflicts between changes to files (not about [conflicts between
7changes to bookmark targets](concurrency.md), for example).
8
9For example, if you merge two branches in a repo, there may be conflicting
10changes between the two branches. Most DVCSs require you to resolve those
11conflicts before you can finish the merge operation. Jujutsu instead records
12the conflicts in the commit and lets you resolve the conflict when you feel like
13it.
14
15## Data model
16
17When a merge conflict happens, it is recorded as an ordered list of tree objects
18linked from the commit (instead of the usual single tree per commit). There will
19always be an odd number of trees linked from the commit. You can think of the
20first tree as a start tree, and the subsequent pairs of trees to apply the diff
21between onto the start. Examples:
22
23* If the commit has trees A, B, C, D, and E it means that the contents should be
24 calculated as A+(C-B)+(E-D).
25* A three-way merge between A and C with B as base can be represented as a
26commit with trees A, B, and C, also known as A+(C-B).
27
28The resulting tree contents is calculated on demand. Note that we often don't
29need to merge the entire tree. For example, when checking out a commit in the
30working copy, we only need to merge parts of the tree that differs from the
31tree that was previously checked out in the working copy. As another example,
32when listing paths with conflicts, we only need to traverse parts of the tree
33that cannot be trivially resolved; if only one side modified `lib/`, then we
34don't need to look for conflicts in that sub-tree.
35
36When merging trees, if we can't resolve a sub-tree conflict trivially by looking
37at just the tree id, we recurse into the sub-tree. Similarly, if we can't
38resolve a file conflict trivially by looking at just the id, we recursive into
39the hunks within the file.
40
41See [here](../git-compatibility.md#format-mapping-details) for how conflicts are
42stored when using the Git commit backend.
43
44## Conflict simplification
45
46Remember that a 3-way merge can be written `A+C-B`. If one of those states is
47itself a conflict, then we simply insert the conflict expression there. Then we
48simplify by removing canceling terms. These two steps are implemented in
49`Merge::flatten()` and `Merge::simplify()` in [`merge.rs`][merge-rs].
50
51For example, let's say commit B is based on A and is rebased to C, where it
52results in conflicts (`B+C-A`), which the user leaves unresolved. If the commit
53is then rebased to D, the result will be `(B+C-A)+(D-C)` (`D-C` comes from
54changing the base from C to D). That expression can be simplified to `B+D-A`,
55which is a regular 3-way merge between B and D with A as base (no trace of C).
56This is what lets the user keep old commits rebased to head without resolving
57conflicts and still not get messy recursive conflicts.
58
59As another example, let's go through what happens when you back out a conflicted
60commit. Let's say we have the usual `B+C-A` conflict on top of non-conflict
61state C. We then back out that change. Backing out ("reverting" in Git-speak) a
62change means applying its reverse diff, so the result is `(B+C-A)+(A-(B+C-A))`,
63which we can simplify to just `A` (i.e. no conflict).
64
65[merge-rs]: https://github.com/jj-vcs/jj/blob/main/lib/src/merge.rs