-
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 useful information about conflicts. It follows up on a discussion on Discord. Eventually, most of this document might find a better home and this discussion might be left with an unfinished draft of it.
Another discussion on a similar topic is #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').
-
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,Xand "removes"D,B. However, our notation keeps track of and preserves additional useful information. -
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".
This whole section is TODO. Thoughts?
See example at the end of the doc.
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")
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 is not necessary, but jj assumes it. Without it, reordering commits will result in a conflict at the end.
Obsolete paragraph I very much doubt that this is commutative. In other words, I think there are cases where we should consider (A->B, C->D, X) to be different from (C->D, A->B, X), but I haven't quite made up my mind. Whether this is true or not, Pijul's theory should explain it since it cares very much about "commuting patches".
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) =2b_and_C=
=(((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.