On Tue, Apr 24, 2018 at 09:15:10PM +1000, Zenaan Harkness wrote:
Putting “mere patch management scripts” such as Git to shame…
So merging is the great VCS challenge, due to conflicts and more importantly the uncertainty of which of a number of conflict resolution strategies is required to resolve any particular merge conflict.
From the VCS point of view, redefining a from from a sequentce of lines, to a directed graph of lines, allows for endless automated merging, with preservation of the resultant graphs, for possible presentation to a user at some future time for "conflict resolution".
This sounds simple, but that's really only because it's so intuitive, yet has now been put into a logically coherent mathematical paper with fancy names which apparently establishes “a sound theory of patches” - which is a very good thing indeed for VCS boffins.
And the reason that a digle,
file => sequence of lines
digle => directed graph of lines
, is particularly useful, is that for one, merges can be done automatically even in the case of conflicts, and simplified presentation of conflicts and conflict resolution UIs is possible - witness the various diff (and merge) "heuristics" which are too often spoken of in Git land - which heuristics although very welcome, and entirely suprerior to the VCS's of yore, are by virtue of being heuristics and not "closed set" type functions, are naggingly and annoyingly unrobust, at least mathematically/ logically, which is doubly nagging due to Git's content-addressed data model design breakthrough - surely we can have it all?
Well yes grasshopper, that's where your intuition is right, yes you can, in the world of Version Control Systemes, have it all:
Teh paper: http://arxiv.org/abs/1311.3903
Teh model: https://pijul.org/model/#why-care-about-patch-theory
Teh easy description: https://jneem.github.io/merging/
“In retrospect, this is a pretty obvious solution: if we don’t know what order "shoes" and "garbage" [two lines each added in separate patches now being merged] should go in, we should just produce an output that doesn’t specify the order. What’s a bit less obvious (but is proved in the paper) is that when we work in the world of digles instead of the world of files, every pair of patches has a unique perfect merge. What’s even cooler is that the perfect merge is easy to compute. I’ll describe it in a second, but first I have to say how patches generalize to digles.” “the difference between flattening and manual merge resolution is that flattening is completely transparent to the VCS: it’s just a patch like any other. That means we can do fun things, like re-ordering or reverting patches, even in the presence of conflicting merges.” [and a "computed from a digle flattening patch" does not dispense with the digle - logically, the digle is a separate object which still remains, and is the primary object/ consideration - possible merges, flattening presentations, undo/redo/cherry pick etc, are secondary, and some things become a lot easier/simpler, apparently]
Easy description, part 2: https://jneem.github.io/pijul/
“pijul differs from other VCSes by not having merge conflicts. Instead, it has (what I call) digles, which are different from files in that their lines form a directed acyclic graph instead of a totally ordered list. The thing about digles is that you can’t really work with them (for example, by opening them in an editor), so pijul doesn’t let you actually see the digles: it stores them as digles internally, but renders them as files for you to edit.” [pijul appears to identify content by identifying lines, rather than files as Git does] “As an illustration of what pijul brings to the table, we’ll look at a situation where pijul’s conflict-avoidance saves the day (at least, compared to git; darcs also does ok here). We’ll start with the example merge from before, including our manual digle resolution… Then we’ll ask pijul to revert the “shoes” patch… The result? We didn’t have any conflicts while reverting the old patch, and the final file is exactly what we expected:… Let’s try the same thing with git:… That was expected: there’s a conflict, so we have to resolve it. So I edited todo.txt and manually resolved the conflict.… Since git can’t “see through” my manual merge resolution, it can’t handle reverting the patch by itself. I have to manually resolve the conflicting patches both when applying and reverting.” plus is associative (brackets don't matter) … perfect merging is likewise associative, the nice property here, “in the following sense: if I have multiple patches (let’s say three to keep the diagrams manageable) then there’s a unique way to perfectly merge them all together. That three-way merge can be written as combinations of two-way merges in multiple different ways, but every way that I write it gives the same [digle] result. Let’s have some pictures… … they also result in the same patches, meaning that everyone will always agree on which lines in the final file [I think he means digle again] came from where. we can say that the current state of a pijul branch is determined by a set of patches; this is in contrast to most existing VCSes, where the order in which patches are merged also matters”
A VCS being built on teh theory: https://pijul.org/
Coming soon to a "mere patch management script" near you :)