JEP 300: Augment Use-Site Variance with Declaration-Site Defaults

Summary

Enhance the Java Programming Language so that a generic class or interface declaration can indicate whether each type parameter is, by default, invariant, covariant, or contravariant, thus allowing more intuitive subtyping relationships between parameterizations of the class or interface. This supplements the existing mechanism for variance, wildcards, which are written at type use sites.

Non-Goals

Any changes to the standard libraries in order to take advantage of the language enhancement would be performed under a separate JEP.

A language might be designed to infer the variance of type parameters, rather than requiring explicit syntax [1]. Such analysis is outside the scope of this JEP.

The feature is not a replacement for wildcards. It provides a less-verbose way to get the behavior of wildcards in certain cases, but is not intended to replace all common use cases.

Changes to the behavior of existing code—such as improvements to or simplifications of the behavior of existing wildcards—are outside the scope of this JEP.

Motivation

Certain class type parameters are used by the class declaration in such a way that they are inherently variant: for example, the type Iterator<Number> has no more functionality than the type Iterator<? extends Number>, both of which can be used to read Numbers; similarly, Predicate<String> has no more functionality than Predicate<? super String>, both of which can be used to test a String. Since invariant uses of these type arguments are less flexible than their wildcard equivalents, while providing no extra power, a reasonable practice is to always use a wildcard when mentioning the type. This strategy maximizes flexibility without compromising expressiveness.

But there are problems:

• Everyone has to cooperate. If a library needlessly expects a Predicate<String>, and you've got a Predicate<? super String>, you have to do an unchecked cast or allocate a new object.

• The practice is mechanical and verbose. Computers are good at mechanical transformations; people are not. And programmers reasonably push back when the "right" way to use a type requires a lot more characters and obfuscates intent. (For example, Function<Iterator<S>, Predicate<T>> expands to Function<? super Iterator<? extends S>, ? extends Predicate<? super T>>.)

• Error messages are harder to decipher. Wildcards and capture variables add a significant degree of complexity to error messages. If a programmer doesn't absolutely need to support variance, she might prefer to live in an invariant world just so that she doesn't have to figure out the error messages.

The solution is to shift this burden from programmers to compilers, allowing a class or interface type parameter, when appropriate, to be declared covariant or contravariant.

interface Predicate<contravariant T> {
  boolean test(T arg);
}

Then, the compiler can automatically treat every use of the type—e.g., Predicate<String>—as if it had wildcards—Predicate<? super String>. Clients get the benefit of more flexible types without having to do anything.

A 2011 PLDI paper [1] performed an analysis of some open-source Java libraries that make use of generics, including the Java core libraries, Guava, and Apache Commons. Findings:

• At least 27% of generic classes and 53% of generic interfaces in the examined libraries have an inherently variant type parameter.
• Inherently contravariant type parameters are almost as common as inherently covariant type parameters.
• At least 39% of wildcard uses in these libraries could be made unnecessary with declaration-site variance.

Presumably a large number of clients of these libraries would benefit from both a reduced need for wildcards and increased flexibility in their types (the paper does not examine library clients).

Description

The new language feature encompasses the following:

• New syntax (such as a symbol, modifier, or annotation) to indicate when a class type parameter is covariant or contravariant.
• Checking of class declarations to ensure consistent use of each covariant or contravariant type parameter; parameterizations of the class are possibly also checked for consistent use of wildcards.
• Type checking that allows a type like C<Foo> to be widened to C<Bar> iff one of the following are true: i) the corresponding type parameter is invariant and Foo is equal to Bar; ii) the corresponding type parameter is covariant and Foo is a subtype of Bar; or iii) the corresponding type parameter is contravariant and Foo is a supertype of Bar.
• Encoding the variance of type parameters in the class file.

(A note on terminology: for simplicity, throughout this JEP, the term class also refers to interfaces.)

Details of these four components:

Type parameter syntax. The strawman syntax is to use covariant T in the declaration of T in order to indicate that it is covariant; contravariant T indicates that T is contravariant. Thus, the Function interface might be declared as:

interface Function<contravariant T, covariant R> {
    R apply(T arg);
}

We may also consider some other syntax. Other languages use symbols (interface Function<-T,+R> { ... }) or keywords (interface Function<in T, out R> { ... }).

Well-formedness checking. A variant type parameter should only be used in certain contexts that support its variance. For example, if the type of a method's parameter is a type variable T, then T should be invariant or contravariant—not covariant. For more complex types, the analysis recurs: if the type of a method's parameter is Predicate<T>, then T should be invariant or covariant. The rules governing appropriate usage of type variables must be developed and implemented for every context in which a type variable can appear.

At the use site, a mismatch between the variance of a type parameter and the variance of a wildcard might also be detected—Iterator<? super String>, for example, is nonsensical. (We must take some care here, however, because such types—though useless—may exist in the wild, raising migration compatibility concerns.)

It is possible to define type-checking behavior without strictly enforcing these well-formedness rules, and there is some flexibility in their design. But being more permissive about well-formedness generally leads to unintuitive behavior at the use site.

Type checking. Two strategies may be used to specify and implement widening of reference types, consistent with the declared variance of type parameters.

• Enhanced subtyping: When subtyping encounters two parameterizations of the same class type, it performs a pairwise comparison of the type arguments using type argument containment. The intuition is that a wildcard can "contain" a range of types, while a type can only "contain" itself. By enhancing this relation, we might allow one type to "contain" another if the corresponding type parameter is variant and an appropriate subtyping relationship holds between the two types.

  With this approach, it might also be useful to define type equality such that a wildcard-parameterized type is considered the same as that type with the wildcards removed.

• Implicit wildcards: Rather than making changes to subtyping, we preprocess the source code so that types like Function<String, Number> are implicitly expanded to Function<? super String, ? extends Number>. This expansion occurs at most use sites of a type (in a few contexts—like class instance creation—wildcards do not make sense, so the expansion does not occur there).

There are advantages and disadvantages to each approach. Enhanced subtyping is more direct and more closely aligned with users' intuition, while implicit wildcards is more flexible, placing fewer constraints on the well-formedness rules. In principle, they are likely equivalent, and if desired it might be possible for the specification and implementation to use different approaches.

Note that many other aspects of type checking are orthogonal to this feature. For example: raw types continue to behave as currently specified; "diamond" class instance creation expressions use the same inference algorithm as before; generic array creation is still prohibited.

Class file changes. To allow separate compilation, variance of type parameters must be encoded in the class file. There are a variety of possible approaches, including modifying the Signature attribute, introducing a new attribute, or piggybacking on an existing mechanism (like RuntimeVisibleTypeAnnotations).

Reflection APIs should probably understand this encoding and directly expose it to clients (e.g., a TypeVariable.getVariance method).

Development plan

In a first phase, the following artifacts will be produced:

• An enhanced version of the javac compiler.
• Other JDK tools and APIs with minor enhancements, as necessary (reflection, javadoc, pack200, etc.)
• Specification: proposed changes to the Java Language Specification, along with any necessary supporting changes to the Java Virtual Machine Specification and/or standardized reflection APIs.
• Documentation describing any source compatibility risks for changes to previously-published classes.

After the first phase, we will reevaluate whether the proposed feature is in accordance with initial expectations, and if so, proceed to a second phase, formally changing the language via the Java Community Process. This will involve i) making adjustments to the behavior of the first milestone as proposed by the consensus of an Expert Group, and ii) producing compliance tests (for the JCK-compiler suite).

Alternatives

The existing alternative in the Java language is use-site variance (wildcards). This is a useful feature, but has its limitations, as noted in the "Motivation" section.

There are good reasons for both use-site and declaration-site variance in a language; they are complementary [1] [2]. Use-site gives users flexibility to tailor a type (like List) to their particular needs, while declaration-site relieves users of a clerical burden when there is only one reasonable variant usage of a type (like Iterator).

There are various ways in which the scope of the feature could be limited, although the problem is so general that these limited approaches seem inadequate:

• The language could give special treatment to certain known classes or interfaces in the standard library, thus avoiding a need for declaration-site syntax and checking.
• The feature could be allowed only in interfaces, or could otherwise be restricted to certain simple contexts, avoiding some extra work for well-formedness-checking—e.g., checking fields and method body declarations.

Testing

As a proposed language change, the enhancement should be accompanied by new JCK-compiler tests.

Behavior of existing compiler tests will be unchanged.

Risks and Assumptions

• Language enhancements are ultimately subject to the Java Community Process; this may influence the scope or design of the feature.

• To be successful, the feature must be designed to allow migration of existing classes, both in the Java Class Library and in users' code. While we have reasonable confidence that this will be possible with very little source incompatibility, there is a risk that this will turn out not to be the case. (Note that any change to method invocation compatibility is likely to cause subtle changes in overload resolution and type inference behavior, but these are typically harmless in real code.)

• The theoretical underpinnings of subtyping in the Java language are somewhat unstable; anything that perturbs this space carries a degree of risk that it will exacerbate the problem. Given that there is a straightforward mapping from a subtyping model with declaration-site variance to one with only use-site variance, however, this feature does not seem to introduce any new theoretical problems.

• If the implicit wildcards implementation strategy is used and a number of common classes are enhanced, we risk overwhelming users with error messages involving wildcards. It is possible that these messages could be simplified, but further exploration would be necessary.

Dependencies

JDK-8154901 identifies various problems with the design of generics in the Java Language Specification and javac. These problems should be addressed, or at least carefully considered, before making further language changes in this area.

JEP 218 proposes other enhancements to generics, both in the language and the JVM. Design decisions should be made with both JEPs in mind.

It would be disappointing for users if this feature were delivered without accompanying changes to existing classes in the Java Class Library. These library changes will need to be handled in a subsequent JEP.

Minor changes may be necessary for java.lang.reflect, javax.lang.model, javadoc, javap, pack200, and ASM. This is mostly to correctly process/expose the variance of type parameters, as encoded in class files.

Language documentation and tutorials should explain and encourage use of the new feature.

References

[1] John Altidor, Shan Shan Huang, & Yannis Smaragdakis. Taming the Wildcards: Combining Definition- and Use-Site Variance. http://jgaltidor.github.io/variance_pldi11.pdf.

[2] Ross Tate. Mixed-Site Variance. http://www.cs.cornell.edu/~ross/publications/mixedsite/mixedsite-tate-fool13.pdf.