Hacker News Reader

Comment by jmiskovic | Hacker News Reader

Would it be useful to consider code diffs as additions and subtractions from code base, and then implement source versioning using lattice structure?

View on HN

I don't think it's a lattice per se, but Darcs had a notion of an "algebra of patches": http://darcs.net/Theory/GaneshPatchAlgebra. Pijul does something similar, claiming to have "a formally correct version of Darcs' theory of patches" https://pijul.org/manual/why_pijul.html

I've never used Pijul, but I miss Darcs almost every day when interacting with Git.

Based on that description of Pijul, it does seem to be a semilattice: it has a merge operation that's associative and commutative, and while it doesn't explicitly state that it's idempotent it's hard to imagine merging two states and getting anything else back than the same state.

Not super familiar with Pijul though!

I am one of the authors of Pijul. It is indeed a semilattice, but not exactly "commutative": the only operations that commute are operations that could be done in parallel. For example, adding a file doesn't commute with editing it.

But unlike in Darcs, where conflicts are messy and not super well-defined in all cases (and not to mention, sometimes cause Darcs to run for a time exponential in the size of the repo's history), two conflicting edits always commute in Pijul.

The main points of Pijul were (1) to solve the soundness issues with conflicts and (2) to fix the exponential problems.

Firstly, you would only have a semilattice (ie you have join but not meet). It sort of gives you the notion of a merge but maybe not the best thing ever. One thing to note is that it isn’t a good model of common vc systems as join must be associative and those systems do not have associative merges.

I guess you could imagine your state to be the join of all its patches. That makes sense if you have an “add foo” patch and a “delete foo” patch and join them to get a “empty but remembering that foo was there once state” (which is required because joining “add foo” again must do nothing). But you also need to accept that “delete foo” on its own is a valid state (or any “resolve this merge conflict” patch) and it feels not great for that to be a valid state.

Generally I think you want slightly more constraints (than none) in which things may be merged or valid repo states.

Reply on news.ycombinator.com