Skip to content

Conflicts

Ilya Grigoriev edited this page Jan 11, 2023 · 32 revisions

This is an outline of an idea of how jj could preserve some additional information about conflicts. We can think of a rebase as applying a diff of two revisions on top of a third revision. A conflict can then be thought of as a bunch of diffs and a revision we're trying to apply them to.

TLDR of this document is that it is possible to meaningfully track and preserve the relationship between the two revisions that form a diff through any further operations that happen to the conflict.

I'm still looking for a good use-case where this algebra of conflicts is clearly useful. The one example I came up with (at the end) is not as clear an improvement as I thought it would be.

This follows up on a discussion on Discord. Another discussion on a similar topic is https://github.com/martinvonz/jj/discussions/5.

Background

Currently, jj models a conflict as a number of "adds" and a number of "removes". Each "add" or "remove" is a version of the file. It doesn't try very hard to preserve the order of "adds" and "removes". This document is an attempt to design a system for jj to preserve some aspect of this order that are useful.

Notation

Let us use the notation A'=(A->B,X) to say that A' is the result of rebasing a revision A with parent B on top of X. This represents the idea that we are replaying the diff of A and B on top of X.

(I don't specify what "a revision" is. The word could mean a whole tree or a single line in a file without changing anything else in this document. It's easiest to think of a revision as a single file).

Conflicts can be rebased on top of other conflicts. We'll use the notation (C->D,A->B,X) for (C->D,(A->B,X)) = (C->D, A').

Summary

  1. Every conflict that can occur can be represented this way.

    In jj's notation, the conflict (C->D,A->B,X) would have "adds" C,A,X and "removes" D,B. However, our notation keeps track of and preserves additional useful information.

  2. There is a useful algebra of rebasing such conflicts. Two of the following are propositions that follow from some axioms (discussed below):

    a. By definition, (C->D, A') = (C->D,(A->B,X)) = (C->D,A->B,X).

    b. Rebases are associative in the sense that (A'->Y, Z) = ((A->B, X)->Y, Z) = (A->B, X->Y, Z).

    c. Most interestingly, (Y->A', Z) = (Y->(A->B,X),Z) = (Y->X, B->A, Z).

Aside: These rules can be thought of as rules about arrows (diffs) rather than revision. Sometimes they look simpler that way. For example, in this language, 2b for example would look like ((A->B, X)->Y) = (A->B, X->Y). A revision A can be thought of as an arrow A->0 where 0 is the empty revision or as an arrow 0->A (whichever is more useful in context). For concreteness and not to waste time on formalities, I don't do that much.

TODO: Add a note about how this is likely a portion of Pijul's "patch theory".

How is this useful?

This whole section is TODO. Thoughts?

To a large degree, this justifies things jj already does :).

Diffs for conflict resolutions

See example at the end of the doc. What this theory suggests is close to what jj does.

Know which side to show as a diff for any conflict

Don't show irrelevant diffs in a merge tool

Making the above precise

Statement #1

A way to state statement #1 more precisely is as follows:

Claim. Every conflict (defined as the result of any sequence of rebases of above objects) can be represented this way, as a sequence (A_1->B_1, ..., A_n -> B_n, X) for some revisions without conflicts A_i, B_i, X.

This claim follows immediately from the algebra in statement #2 above (which we discuss in more detail below). (TODO: If needed, explain the "follows immediately")

Merges

While the "Claim" above talks about rebases, it also covers merge conflicts. This is because a conflict arising from a merge can always be thought of as a result of a rebase.

A merge of A and C with base B can be represented in two different ways as a rebase: either (A->B,C) or (C->B, A). These are distinct in our algebra (they lead to different-looking diffs).

Note: If we consider (A->B,C) as equivalent to (C->B, A) and include the commutativity axiom (see below), then I'm pretty sure any reordering of the "adds" and "removes" will lead to an equivalent conflict. This exactly matches how jj treats conflicts today. So, this document is only interesting if there's a benefit to not considering these equivalent.

Statement #2

Let's state some axioms that should be true for rebases, and then derive statements 2a and 2b from them.

Axioms

TODO: Explain why they should hold in terms of rebases. Most of them have to do with the fact that we expect rebasing A from B to C, and then rebasing the result from C to D to be equivalent to rebasing directly from B to D.

Axiom A. (A->B,B)=A

Axiom B. (B->B,A)=A

Axiom C. (A->C,X) = (A->B, B->C,X). This can be thought of as a rule about composition of arrows: (A->C) = (A->B, B->C).

Axiom D. ((A->B,X)->X,Y) = (A->B, Y). When stated as a rule about arrows, this looks very similar to axiom B: (A->B,X)->X = A->B.

It is quite likely that there is a more elegant equivalent set of axioms, but this should do.

Commutativity

Commutativity in the sense of assuming that (A->B, C->D, X) = (C->D, A->B, X) would be an additional axiom. This document does not use it.

However, jj does essentially assume commutativity. We probably want to continue doing so for the purposes of applications to jj. Without commutativity, reordering commits would result in a conflict at the end: (B->A,C->B,A) would be different from C=(C->B,B->A,A).

Propositions

Statement 2b. Rebases are associative in the sense that ((A->B, X))->Y, Z) = (A->B, X->Y, Z).

Proof: I put the axiom used between equality signs.

((A->B, X))->Y, Z) =C= ((A->B, X))->X, X->Y, Z) =D= (A->B, X->Y, Z).

Proposition E. (A->B, B->A, X) = X.

Proof: (A->B, B->A, X) =2b= ((A->B,B)->A,X) =A= (A->A,X) =B= X.

Proposition F. (X->(A->B,X),Z) = (B->A, Z). This is a special case of Statement 2c which we'll use to prove the whole thing.

Proof:

(X->(A->B,X),Z) =E= (B->A,A->B,X->(A->B,X),Z) =2b= (B->A,(A->B,X)->(A->B,X),Z) =B= (B->A,Z)

Now, we finally get to the most interesting statement:

Statement 2c. (Y->(A->B,X),Z) = (Y->X, B->A, Z).

(Y->(A->B,X), Z) =2b= (((Y->(A->B))->X), Z) =E= (((Y->X, X->Y, Y->(A->B), X), Z) =C_and_2b=
    =(((Y->X, (X->(A->B),X)), Z) =F_and_2b= (Y->X, B->A, Z)

Example

Change A

diff --git a/Conflicts.md b/Conflicts.md
index 50af10eb81...c936bee9dc 100644
--- a/Conflicts.md
+++ b/Conflicts.md
@@ -8,8 +8,9 @@

 ## Background

-Currently, `jj` models a conflict as a number of "adds" and a number of
-"removes". Each "add" or "remove" is a version of the file. It doesn't try very
+Currently, `jj` does some things.
+Each "add" or "remove" is a version of the file.
+It doesn't try very
 hard to preserve the order of "adds" and "removes". This document is an attempt
 to design a system for `jj` to preserve some aspect of this order that are
 useful.

Change B

diff --git a/Conflicts.md b/Conflicts.md
index 50af10eb81...09ec75bc9c 100644
--- a/Conflicts.md
+++ b/Conflicts.md
@@ -8,10 +8,10 @@

 ## Background

-Currently, `jj` models a conflict as a number of "adds" and a number of
+Currently, `qq` models a conflict as a number of "adds" and a number of
 "removes". Each "add" or "remove" is a version of the file. It doesn't try very
 hard to preserve the order of "adds" and "removes". This document is an attempt
-to design a system for `jj` to preserve some aspect of this order that are
+to design a system for `qq` to preserve some aspect of this order that are
 useful.

 ## Notation

Both rebases

good for B'

## Background

<<<<<<<
%%%%%%%
-Currently, `jj` models a conflict as a number of "adds" and a number of
+Currently, `qq` models a conflict as a number of "adds" and a number of
 "removes". Each "add" or "remove" is a version of the file. It doesn't try very
+++++++
Currently, `jj` does some things.
Each "add" or "remove" is a version of the file.
It doesn't try very
>>>>>>>
hard to preserve the order of "adds" and "removes". This document is an attempt
to design a system for `qq` to preserve some aspect of this order that are
useful.

Better rebase for A'

The following could be nicer to see if one wanted to apply the changes of A on top of B.

<<<<<<<
%%%%%%%
 ## Background

-Currently, `jj` models a conflict as a number of "adds" and a number of
-"removes". Each "add" or "remove" is a version of the file. It doesn't try very
+Currently, `jj` does some things.
+Each "add" or "remove" is a version of the file.
+It doesn't try very
 hard to preserve the order of "adds" and "removes". This document is an attempt
 to design a system for `jj` to preserve some aspect of this order that are
 useful.
+++++++
## Background

Currently, `qq` models a conflict as a number of "adds" and a number of
"removes". Each "add" or "remove" is a version of the file. It doesn't try very
hard to preserve the order of "adds" and "removes". This document is an attempt
to design a system for `qq` to preserve some aspect of this order that are
useful.
>>>>>>>

In this example, this may or may not seem like an improvement.

TODO: Try to improve this example. For instance, try adding more stuff in between of A' and B.

Resolution

diff --git a/Conflicts.md b/Conflicts.md
index a70a8caa6d...483745d425 100644
--- a/Conflicts.md
+++ b/Conflicts.md
@@ -8,16 +8,9 @@

 ## Background

-<<<<<<<
-%%%%%%%
--Currently, `jj` models a conflict as a number of "adds" and a number of
-+Currently, `qq` models a conflict as a number of "adds" and a number of
- "removes". Each "add" or "remove" is a version of the file. It doesn't try very
-+++++++
-Currently, `jj` does some things.
+Currently, `qq` does some things.
 Each "add" or "remove" is a version of the file.
 It doesn't try very
->>>>>>>
 hard to preserve the order of "adds" and "removes". This document is an attempt
 to design a system for `qq` to preserve some aspect of this order that are
 useful.

jj.wiki.tar.gz

Clone this wiki locally