[darcs-users] unique features + exponential time issue

[Tommy Pettersson]

On Wed, Oct 17, 2007 at 12:03:54PM -0700, Stephen J. Turnbull wrote:
> AFAIK, there are no simple examples of how to generate
> exponential merge problems.

Yes, there is. You just simply keep feeding conflicts to the
root of a beginning exponential explosion, and resolve them at
the top of it. This means each new conflicting patch from the
bottom will have the same complexity as its presider when it
reaches the latest resolve patch, and then double in complexity
when conflicting with it. Add a new resolve patch on top of that
and repeat... (There might be other ways too.)

It can be thought of as a fight where the "conflict supplier"
doesn't want the original conflicting seed at the bottom of the
exponential explosion. His changes will continue to be unaware
of the deviation in the exploding repo, and every time the
receiver tries to "fix" it with a resolving patch new conflicts
from the supplier will just grow worse.

This is why darcs currently doesn't always works so well for
keeping a "local branch" of some source. The local deviations
are likely to cause exponential conflicts after time. Local
deviations must either be isolated in some way (kept in separate
files) so they never conflict, or changes from upstream needs to
be merged in "by hand" and recorded as local patches that
doesn't conflict with the local changes.

If you are aware of how and when darcs breaks down it is not
very hard to avoid it, but that is a rather dark side of darcs'
otherwise being extremely easy to use.

The new cancellation patches that David is working on are, as
far as I understand it, indeed designed to stop this exponential
explosion literary at its root. :-)


-- 
Tommy Pettersson <ptp at lysator.liu.se>