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

[Jonathan Gibbons]

On Thu, 2 Mar 2023 23:29:42 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.

Looks OK to me, but I'll stop short of the "A" word so that someone on the javac team can review it as well.

The old code was for sure much simpler/faster, but maybe it was not called often enough for the change to be noticeable.
In a world with a String-based implementation of Name, I presume we would delegate to String.compareTo, although we might need to push the implementation to the enclosing NameTable.

`Name` is an abstract class, with two `NameImpl` implementations. While I might have suggested to test both, I guess the edits are in the common code and should not vary between the two.

src/jdk.compiler/share/classes/com/sun/tools/javac/util/Name.java line 41:

> 39:  *  deletion without notice.</b>
> 40:  */
> 41: public abstract class Name implements javax.lang.model.element.Name, PoolConstant, Comparable<Name> {

It's disappointing that we can't easily make `javax.lang.model.element.Name` implement `Comparable` as well.

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

PR: https://git.openjdk.org/jdk/pull/12843