[darcs-users] unique features + exponential time issue

[Johan Tibell]

On 10/18/07, Tommy Pettersson <ptp at lysator.liu.se> wrote:
> 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. :-)

A wiki that explains to do in what case would be great. i.e. if you
get a conflict, unrecord local and amend or something like that.

I don't know enough to write one but it seems like you do. :)

-- Johan