graggle

Order-independent merge engine based on pijul's patch algebra.

Files are directed acyclic graphs of lines ("graggles"), patches are graph morphisms, and merging is a categorical pushout. This guarantees that merging patches A and B produces the same result regardless of the order they're applied.

Based on the theory from Mimram & Di Giusto's work on a categorical theory of patches.

Usage

use graggle::{Graggle, merge};

let base = Graggle::from_text("hello\nworld\n");

let result = merge(&base, &[
    "hello\nbeautiful\nworld\n",  // branch 1: insert "beautiful"
    "hello\nworld\ngoodbye\n",    // branch 2: append "goodbye"
]);

assert!(!result.output.has_conflicts);
assert_eq!(result.output.content, "hello\nbeautiful\nworld\ngoodbye\n");

Concepts

• Graggle: A DAG of lines. A normal file is a graggle that happens to be a total order. When lines have no prescribed order (parallel in the DAG), that's a conflict.

• Patch: Transforms one graggle into another by inserting new vertices between context vertices or marking vertices as deleted ("ghost" lines).

• Merge: The categorical pushout of two diverged graggles — the smallest graggle containing both sets of changes. Unique, associative, and commutative up to isomorphism.

License

MIT