[darcs-users] darcs cannot apply some patch bundles

[Ganesh Sittampalam]

On 06/03/2012 15:12, Michael Hendricks wrote:
> 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.

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

Yes, I agree it would be fine just to consider some subset of patches
for this use case using whatever heuristic, and I think that e.g. 100
patches would be absolutely fine. The only difficulty is picking a
heuristic that won't cause fresh confusion when it doesn't work out.

Ganesh