perfect merges always → digle ≡ (file redefined as) DAG of lines

[Zenaan Harkness]

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 :)
>