[darcs-users] unique features + exponential time issue

[Stephen J. Turnbull]

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.)

"Just keep feeding" is not concrete enough to be simple.  Do you
mean this "ChangeLog" process?

A prepends 1 line -> conflict <- B prepends 1 line
                          |
                         V
                    resolve patch
                          |
                         V
A prepends 1 line -> conflict <- B prepends 1 line
                          |
                         V
                    resolve patch
                          |
                         V
A prepends 1 line -> conflict <- B prepends 1 line
                          |
                         V
                    resolve patch
                          |
                         V


Or does it need to be something else?