[darcs-users] Bounty on the conflict misery bug

[David Roundy]

On Sun, Aug 26, 2007 at 08:44:46AM +0900, Stephen J. Turnbull wrote:
> Salvatore Insalaco writes:
> > 2007/8/17, Alexander Staubo <alex at purefiction.net>:
> > > We have patiently been waiting for a fix, but there seems to be
> > > nothing on the horizon.
> > 
> > Actually there is. Jason is working on a Google Summer of Code project
> > about the conflict-handling in Darcs, and some code is already in
> > darcs-unstable (albeit not actually working for "real world" usage).
> 
> I've seen no reports that anybody understands it; there's no guarantee
> that Jason's work will really speed things up until there's a proof
> that what Darcs is trying to do isn't NP-hard (and preferably better
> than o(n^2)).

I've been pretty quiet, partly because I've been busy with other things (I
got married last month and moved across the country), and partly because
I've been busy hacking on darcs (and have only a limited amount of time).
Most recently it's been the latter.

Jason's SoC project didn't progress as far as either of us had hoped, but
I'm now working on this myself.  Although Jason didn't get much code
produced, we did have many productive (in-person) discussions of how to go
about this, and as a result I now have a pretty clear idea as to what needs
doing.

The algorithm we're looking at is definitely polynomial in scaling, and
without a particularly high exponent.  The precise scaling will depend on
how you define N.  Ordinarily, the number of actually-conflicting patches
is pretty small.  Normal (non-conflicting) darcs merges are currently
O(N^2) where N is the number of patches on each side of the merge (assuming
they're equal).  I'm not planning to change that (although there are some
approaches we could use to make them O(NlogN) in the limit that each change
is to a separate file).  The conflict handling *shouldn't* involve any
additional powers of N, but instead should only increase the cost by
factors involving the number of patches that actually conflict.

Right now, all I've got (just finished this afternoon) is a
conflict-handling algorithm that passes a few simple tests.  Next I need to
implement support for darcs to be able to decide which approach to use (new
or old) based on the _darcs/format file.  That'll probably take a day or
two, maybe more, since it'll touch many (most?) darcs commands.

The first version (note: not the first *released* version) of the new
conflict-handling code will actually be terribly inefficient, since I won't
implement the optimization of keeping track of how far back in the history
the last "live" conflict lives.  It's not a hard optimization, but since it
*is* an optimization, I'll start with getting the code right.

Once we've got this first round of conflict-handling in, we'll need to
support conflict resolution (which is distinct, in this approach).  I've
implemented (but not tested) the low-level core for this, and we've got a
"simple" approach that we can easily hack together for the UI which might
actually be beautifully elegant in practice--but some UI experimentation
will be needed.  Fortunately, the UI is distinct from the sematics and
internals, so we have as long as we want to take to get the UI right.

In particular, we envision the UI allowing you to select which conflicting
branch of development you prefer, which will allow you to avoid future
conflicts with that branch, after resolving away the conflict with the
previous branch.

> Don't take my word for it, I haven't been paying that close attention,
> so maybe there are assurances.  But all I've seen promised is that
> people will work on it, not that there is a know solution that will
> just take some hard work to implement.

It's actually looking pretty good.  We're using a pretty simple approach,
which *ought* to be "just work" to implement.
-- 
David Roundy
http://www.darcs.net