[darcs-devel] darcs patch: fix ordering mistyping in sift_for_pending. (and 2 more)

[David Roundy]

On Sun, Aug 12, 2007 at 05:11:42PM +0200, Eric Y. Kow wrote:
> Incidentally, this patch also 'solves' the issue494 stuff, although I
> don't know if it is an actual solution or just something which hides the
> problem.

I think it's probably an actual solution.  But in some sense, all the
sift_for_pending stuff is pretty hacky.  A "complete" solution would be
O(N^2) in the worst case, I believe--you'd need to check whether O(N^2)
pairs of patches can coalesce, and this is assuming you could order the
checks such that you also get by with the minimum O(N^2) commutes.

We could code up a rock-solid sift_for_pending, but it'd probably be *much*
slower than what we've got.  Maybe we should, at least for use as a testing
tool.  I'd feel better if we could eliminate these reordering heuristics.
We'd still like to keep the reordering, for human consumption, but it'd be
nice if our try_to_shrink didn't rely on the choice of ordering in patches
(which is why the alphabetic ordering of filenames in issue494 made a
difference).

> Anyway, my head is spinning now, but let me know if I've said anything
> silly.  The patch goes in.

Nothing silly... and I'm glad you're taking the time to look into this
stuff!
-- 
David Roundy
Department of Physics
Oregon State University
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://lists.osuosl.org/pipermail/darcs-devel/attachments/20070813/1e18a726/attachment.pgp