[darcs-devel] new approach to conflicts

[David Roundy]

Hi all,

We've been having some rather exciting discussions, starting over in
darcs-conflicts, and continuing on IRC, regarding a new
non-conflictor-based approach to handling conflicts.  This approach
involves storing either a tree or a DAG of primitive patches, instead
of a simple sequence of patches.  It strikes several of us as very
promising, but requires a rewrite of much of darcs' machinery (oddly
enough, not including the commute function).

So I'm thinking we should bring this into the open (or more
open... the irc channel isn't exactly closed), since it'll affect many
of you (fellow darcs developers), more than the conflictor approach
would have.

We're right now in the second day of discussion, which has been going
on between Arjan (who originally had this idea, although it's now been
refined a bit), me (who finally was convinced of it just this week,
when my conflictor approach started causing me to do work that would
much more easily be applied to this approach), Ganesh (Heffalump) and
Ian (Igloo).  I'll be off the channel pretty soon and for most of my
afternoon (between church and an ultimate frisbee game), and after
that it'll probably be very late in Europe (where the rest are)... so
I'm not sure how the discussion will go.

I'm figuring to move the discussion back to darcs-devel for a while
anyways, since we're talking about things like reorganizing how darcs
stores patches.

The basic idea is to store a tree of primitive patches, where each
branching point represents a conflict.  When a conflict happens, you
can resolve it by creating a new (resolution) patch that somehow marks
those other branches as "dead".  If new patches get pulled onto them,
the result is you've got more than one "live end", which means you've
got a conflict to resolve.  I think it's pretty certain that this
approach will "work", the questions are how to do it efficiently and
so that we provide a nice user interface.

The big issue is that now a composite named patch can end up having
primitive patches on more than one branch of the conflict tree, which
means storing each composite named patch in a single file would be
awkward.  Which is one of the reasons this'll affect everyone.

I've toyed with the idea (disgusting to everyone else) of eliminating
composite patches entirely at the core level.  We'd still name our
patches as usual, but the result would be to add a name and primitive
patch number to each of the primitive patches.  This has a degree of
elegance that I love, since we'd have one less patch type.  It also
would open up the possibility of pulling just part of a named patch
or obliterating just part of a named patch.  This might be a UI
nightmare, and might make Juliusz' signed patches goal even more
scarier than it already is.  On the other hand, it might make that
goal loftier, since signing one named patch versus two together would
be almost equivalent, which I think would be nice, since you might
have an intermediate patch you don't want to sign because it opens a
security hole closed later, so you want to sign the two together
only.  This idea also has potentially serious efficiency effects, as
it'll probably increase by an order of magnitude the number of
"patches" in a repository, so we'll need to be more aggressive about
breaking the inventory up or grouping primitive patches together, or
something.

Hmmm.  I'm starting to ramble, and suspect I've not covered all the
important features of the new idea.  Hopefully others will correct me
and/or expand this explanation.

I'm afraid that I probably won't have as much time as I'd like for
this work, as I'm moving to a new job at Oregon State University in
just a couple of months, and have a class to prepare, and papers to
finish up here at Cornell...
-- 
David Roundy