1. 28

  2. 4

    Is there a compare / contrast between pijul and the origin of patch theory darcs ?

    I’ve read much about darcs patch theory, and would find it easier to jump into pijul if I had such a document.

    1. 14

      I’m one of the authors.

      The answer to your question is no, but we’d happily accept contributions to our manual, if you can make sense of the following and help us write it up (we don’t mind images at all, especially in SVG and/or TikZ).

      The main differences are:

      • Soundness: I don’t believe much is known about what Darcs does on conflicts. I’m not sure the algebra rules still apply between conflicting patches, conflict fights, etc. Pijul has the same algebraic rules all the time, including on conflicts.

      • Applying a patch in Pijul is in time O(p * c * log(h)), where p is the size of the patch, c the size of the largest conflict, and h the size of history (number of lines since the beginning). In contrast, Darcs can be in O(2^h) in the worst case.

      • Pijul can only model patch adding or deleting lines, and adding, deleting or renaming files. Darcs can model arbitrary patches, as long as you provide the commutation rules to detect conflicts. The downside of that (very cool) feature of Darcs is, of course, that conflicts are not properly represented internally, which causes big UI/UX issues.

      • Darcs tests patch commutation (to detect conflicts), whereas in Pijul, for any two patches A and B, either A references B explicitly (possibly transitively), or B references A explicitly (possibly transitively), or A and B commute (even if A and B are in conflict).

      • Darcs works mostly on patches + a text pristine, whereas Pijul works on patches, plus a more complex datastructure to represent the pristine. Actually Pijul’s pristine is a CRDT (but that’s not how it was found).

      • Speaking of that, Pijul represents conflicts internally, which Darcs doesn’t do. In fact we even need to run quite a non-trivial algorithm to detect them after applying a patch.