On 04/21/2016 04:24 PM, Paul Sandoz wrote:
> Please review:
>
> http://cr.openjdk.java.net/~psandoz/jdk9/JDK-8154049-dual-pivot-sort-one-off-error/webrev/
Ew. It is a complete brain-twister to understand the original code, the
original improvement, the bug, and the fix -- all four! This is a
manifestation of Kernigan's "Everyone knows that debugging is twice as
hard as writing a program in the first place. So if you're as clever as
you can be when you write it, how will you ever debug it?"
In constructive vein, I think the comment needs to be expanded to:
// These invariants should hold true:
// run[0] = 0
// run[<last>] = right + 1; (terminator)
if (count == 0) {
// A single run of equal elements.
return;
} else if (count == 1 && run[count] > right) {
// Either a single ascending or a transformed descending run.
// Always check that a final run is a proper terminator, otherwise
// we have an unterminated trailing run, to handle downstream.
return;
}
right++;
if (run[count] < right) {
// Corner case: the final run is not a terminator. This may happen
// if a final run is an equals run, or there is a single-element run
// at the end. Fix up by adding a proper terminator at the end.
// Note that we terminate with (right + 1), incremented earlier.
run[++count] = right;
}
...or somehow rewire the "equals" run logic to add a proper terminator
before breaking from the loop. But this is beyond my capacity this fine
evening.
Thanks,
-Aleksey
