-
Notifications
You must be signed in to change notification settings - Fork 0
Conflicts
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.
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.
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').
We now usually ignore order and use the notation C-D+A-B+X for (C->D,A->B,X). See also <https://github.com/martinvonz/jj/blob/main/docs/technical/conflicts.md >.
Statement 1. Every conflict that can occur can be represented in the notation described above as a combination of unconflicted revisions.
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.
Statement 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.
This whole section is TODO. Thoughts?
See example at the end of the doc. What this theory suggests is close to what jj does.
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 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")
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.
Let's state some axioms that should be true for rebases, and then derive statements 2a and 2b from them.
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 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).
On the other hand, the fact that jj does not consider the tip of the reordered commits conflicted, while cute, has room for improvement: fixing the conflict in the middle commit inevitably creates a conflict at the tip. (TODO: draw a picture to clarify this).
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)
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.
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
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.
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.
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.