timsort

[Martin Buchholz]

No one actually said NO, but both Alan and Andrew strongly hinted that
a backward compatibility mode would be good.
So I kept the old implementation and allow it to be selectable
via a system property.  There's nothing more compatible than
the legacy implementation.

    /**
     * Old merge sort implementation can be selected (for
     * compatibility with broken comparators) using a system property.
     * Cannot be a static boolean in the enclosing class due to
     * circular dependencies.  To be removed in a future release.
     */
    static final class LegacyMergeSort {
        private static final boolean userRequested =
            java.security.AccessController.doPrivileged(
                new sun.security.action.GetBooleanAction(
                    "java.util.Arrays.useLegacyMergeSort")).booleanValue();
    }

The sort method bodies now look like:

        if (LegacyMergeSort.userRequested)
            legacyMergeSort(a);
        else
            ComparableTimSort.sort(a);

New webrev at:
http://cr.openjdk.java.net/~martin/webrevs/openjdk7/timsort/

If I don't hear from anyone soon (e.g. for CCC approval)
I'll commit to the tl forest.

Martin

On Tue, Jun 30, 2009 at 11:28, Alan Bateman<Alan.Bateman at sun.com> wrote:
> Martin Buchholz wrote:
>>
>> :
>>
>> As you suggested, I added the Classpath exception wording
>> to TimSort.java and ComparableTimSort.java.
>>
>> I excised the old mergesort code from Arrays.java.
>>
>> webrev regenerated.
>
> Thanks for doing this.
>>
>> Adding all-or-nothing wording would be good to add,
>> perhaps to the class-level javadoc.  But it doesn't
>> have to be part of this change.
>
> I brought it up because it looks like (and you can correct me) that the IAE
> may be thrown after some reordering of the array has taken place. This might
> be unexpected.
>
>>
>> The JDK project has unusually high compatibility concerns.
>> I and Josh believe the introduction of a possible IAE if the
>> comparator doesn't satisfy its contract is the right thing,
>> but we'd also be willing to change the code to swallow the IAE
>> or to do so conditionally based on the value of a system property.
>> Keep in mind that a call to foreign code can throw any throwable at all,
>> so a rogue comparator can cause arbitrary behavior even today.
>
> I think most people would agree that that catching these otherwise-silent
> failures is a good thing. The problem is the customer that upgrades the JDK
> on a production system and gets burnt by some broken third party code that
> "used" to work. Having some way to restore existing behavior would make this
> an easier sell. The suggestion from Jason to change it to an assertion might
> be worth thinking about too but I suspect that few developers test with
> assertions enabled.
>
> -Alan.
>