RFR: 8303526: Changing "arbitrary" Name.compareTo() ordering breaks the regression suite [v2]

[Vicente Romero]

On Tue, 21 Mar 2023 23:06:48 GMT, Archie L. Cobbs <duke at openjdk.org> wrote:

>> This was discovered during investigation for [JDK-8268622](https://bugs.openjdk.org/browse/JDK-8268622).
>> 
>> The method `Name.compareTo()` looks like this:
>> 
>> /** An arbitrary but consistent complete order among all Names.
>>  */
>> public int compareTo(Name other) {
>>     return other.getIndex() - this.getIndex();
>> }
>> 
>> Note the "arbitrary but consistent" wording. Unfortunately, the ordering can be "arbitrary" only if you don't mind breaking the regression suite.
>> 
>> For example, if you apply this patch:
>> 
>> --- a/src/jdk.compiler/share/classes/com/sun/tools/javac/util/Name.java
>> +++ b/src/jdk.compiler/share/classes/com/sun/tools/javac/util/Name.java
>> @@ -105,7 +105,7 @@ public abstract class Name implements javax.lang.model.element.Name, PoolConstan
>>      /** An arbitrary but consistent complete order among all Names.
>>       */
>>      public int compareTo(Name other) {
>> -        return other.getIndex() - this.getIndex();
>> +        return this.getIndex() - other.getIndex();
>>      }
>> 
>>      /** Return true if this is the empty name.
>> 
>> then the following tests will fail:
>> ```TEST: tools/javac/8203436/T8203436b.java
>> TEST: tools/javac/generics/7034019/T7034019c.java
>> TEST: tools/javac/generics/7034019/T7034019d.java
>> TEST: tools/javac/generics/diamond/neg/Neg21.java
>> TEST: tools/javac/generics/diamond/neg/Neg22.java
>> TEST: tools/javac/generics/inference/EagerReturnTypeResolution/EagerReturnTypeResolutionTestb.java
>> TEST: tools/javac/patterns/InferenceUnitTest.java
>> TEST: tools/javac/T8187978/FilterOutCandidatesForDiagnosticsTest.java
>> TEST: tools/javac/varargs/6806876/T6806876.java
>> 
>> ==============================
>> Test summary
>> ==============================
>>    TEST                                              TOTAL  PASS  FAIL ERROR
>>>> jtreg:test/langtools:langtools_javac               3718  3709     9     0 <<
>> ==============================
>> 
>> The compiler behavior should be deterministic whenever possible, and the javac regression suite should be robust. So clearly "arbitrary" behavior by this method is not really supported.
>> 
>> It turns out there is only one user of `Name.compareTo()`, the method `TypeSymbol.precedes()`:
>> 
>> /**
>>  * A partial ordering between type symbols that refines the
>>  * class inheritance graph.
>>  *
>>  * Type variables always precede other kinds of symbols.
>>  */
>> public final boolean precedes(TypeSymbol that, Types types) {
>>     if (this == that)
>>         return false;
>>     if (type.hasTag(that.type.getTag())) {
>>         if (type.hasTag(CLASS)) {
>>             return
>>                 types.rank(that.type) < types.rank(this.type) ||
>>                 types.rank(that.type) == types.rank(this.type) &&
>>                 that.getQualifiedName().compareTo(this.getQualifiedName()) < 0;
>>         } else if (type.hasTag(TYPEVAR)) {
>>             return types.isSubtype(this.type, that.type);
>>         }
>>     }
>>     return type.hasTag(TYPEVAR);
>> }
>> 
>> If we want the above partial ordering to be stable, we need to specify deterministic behavior for `Name.compareTo()`.
>> 
>> An obvious choice would be to require that `Name.compareTo()` orders consistently with `String.compareTo()`, i.e., lexicographically on the Unicode characters in the name.
>> 
>> Fortunately, this comparison can be done efficiently, i.e., without actually converting the `Name` into a `String`, because UTF-8 is "lexicographically consistent" with the characters it encodes, except that Java's use of Modified UTF-8 means a special check for 0x0000 (which is encoded as two bytes) is required.
>> 
>> When you do this the tests are still broken... but notice that `TypeSymbol.precedes()` is actually using the _reverse_ of `Name.compareTo()`. So somehow, the current `Name.compareTo()` is ordering things "backwards", at least from the point of view of the expectation of the regression tests.
>> 
>> So replacing `Name.compareTo()` with a version that orders lexicographically, and also un-reversing its treatment in `TypeSymbol.precedes()`, makes things the tests succeed again.
>> 
>> That's what this patch does.
>
> Archie L. Cobbs has updated the pull request with a new target base due to a merge or a rebase. The pull request now contains two commits:
> 
>  - Merge branch 'master' into JDK-8303526
>  - Require Name.compareTo() to produce a lexicographic ordering.

looks good

-------------

Marked as reviewed by vromero (Reviewer).

PR Review: https://git.openjdk.org/jdk/pull/12843#pullrequestreview-1359792282