[darcs-users] darcs cannot apply some patch bundles

Michael Hendricks michael at ndrix.org
Tue Mar 6 15:12:53 UTC 2012


On Mon, Mar 5, 2012 at 11:15 PM, Ganesh Sittampalam <ganesh at earth.li> wrote:
> It's also that, whether or not you have the patch data, the naive
> algorithm is O(n^2) to commute the minimal context of a single patch,
> and I don't know a more sophisticated one (though I have some vague ideas).

That makes sense.  I wonder if Eric's suggestion to only consider
patches not in a tag makes O(n^2) feasible.  Roughly how many commutes
per second can Darcs handle?  100, thousand, ten thousand?  If n were
too large, Darcs could always fall back to the current behavior.

> Consider a repo ABCDEF, and you want to calculate the minimal context of
> F. First you commute F past E, and that succeeds so you can drop E. I'm
> ignoring the fact that the representation changes as you do it:
>
> ABCDF
>
> Now you try D. That fails. Now you need to try C. But to try C, you
> first have to commute it past D. So now what we really have is a list of
> patches we need to try to commute everything else past:

When generating a patch bundle, it seems that minimal context is more
aggressive than we need.  A "reduced context" might be sufficient.  I
imagine just commuting F backwards until it fails to commute or it
reaches a tag.  That would be O(n) and probably removes most patches
that are obviously not relevant to the context.

In my typical workflow (with Darcs or other VCS), my local repository
is only a couple dozen patches ahead of the upstream repository.  Most
of those patches are entirely independent of each other.  In that
scenario, the "reduced context" sounds quite effective.

--
Michael


More information about the darcs-users mailing list