[darcs-users] darcs hang: infinite recursion?

[David Roundy]

On Mon, Jun 13, 2005 at 11:06:36AM +0000, Felix Breuer wrote:
> On Mon, 13 Jun 2005 08:30:30 -0400
> David Roundy <droundy at darcs.net> wrote:
> 
> > Alas, I *can* help explain the scenario.  What you've run into is the
> > infamous O(2^N) behavior of darcs when it encounters certain sorts of
> > conflicts. The code should eventually complete, but it's possible that our
> > sun will become a red giant before that happens (which would most likely
> > cause darcs to fail).  :(
> 
> Will that problem (hopefully) solve itself when you have developed this
> new formalism?
> 
> Any way we can help solving this issue? Or can it only be explained to
> someone who is up to his neck in patch theory? (I only read the chapter
> in the manual :)

There's a darcs-conflicts list which I created for discussion of the issue.
A few months back we had quite a bit of traffic discussion possibilities,
but recently the list has been mostly silent (and I've been working alone
on this).  I like to think that this is largely because I now know what I'm
doing, and just need to do it.

The new formalism won't eliminate all exponential difficulties, but should
eliminate them when there are only two threads of history being merged,
which I believe is the most common case.  And I *think* that it'll only be
exponential in the number of parallel conflicting histories, which is much
better than the current situation, which is exponential in the number of
conflicting patches.

Another major improvement (should the new formalism work as expected--it's
not complete) would be the elimination of merger-related "bug in
reconcile_unwindings"

(see http://bugs.darcs.net//Ticket/Display.html?id=267).

> > I am in the process of working out a new formalism for handling conflicts,
> > but it'll be a while before it's finished.  On the plus side, I *am* making
> > progress, and have a nice framework for generating test scenarios upon
> > which to test my merge and commute code.
> 
> When you have worked it out and if you have time to spare, please write
> a bit on this formalism in the "Theory of Patches" chapter. I am
> curious!

I'll definitely do so when the code is finished.  Until then, you can get
occasional updates on the darcs-conflicts mailing list, and could ask
questions there.

Jason wrote:
> David, have you ever checked if you're solving an NP-Complete problem
> with your conflict code?  I'm hoping the answer is that someone has
> checked and that this problem should indeed have a polynomial time
> algorithm, but I thought I'd ask anyway ;)

No, I don't know how one would check.  But I *am* sure that certain common
cases can be solved in polynomial time (in the number of patches involved).
The hard part (algorithm-wise) is making it work in all the uncommon cases.
-- 
David Roundy
http://www.darcs.net