<h1>Improved variance for generic classes and interfaces</h1>

<pre>
Title: Improved variance for generic classes and interfaces
Author: Daniel Smith
Organization: Oracle
Created: 2014/03/31
Type: Feature
State: Draft
Exposure: Open
Component: core/lang
Scope: SE
JSR: TBD
Discussion: compiler dash dev at openjdk dot java dot net
Start: 2014/Q2
Effort: L
Duration: L
Template: 1.0
</pre>

<h2>Summary</h2>

<p>Enhance the Java Programming Language so that generic class and interface declarations can indicate whether each type parameter is invariant, convariant, or contravariant.  The type system then interprets this metadata by supporting more flexible and intuitive widening reference conversions between different parameterizations of the class or interface (e.g., an <code>Iterator<String></code> can be assigned to the type <code>Iterator<CharSequence></code>).</p>

<h2>Goals</h2>

<p>The new language feature encompasses the following:</p>

<ul>
<li>New syntax (such as a symbol, modifier, or annotation) to indicate when a class type parameter is covariant or contravariant.</li>
<li>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.</li>
<li>Type checking that allows a type like <code>C<Foo></code> to be widened to <code>C<Bar></code> iff one of the following are true: i) the corresponding type parameter is invariant and <code>Foo</code> is equal to <code>Bar</code>; ii) the corresponding type parameter is covariant and <code>Foo</code> is a subtype of <code>Bar</code>; or iii) the corresponding type parameter is contravariant and <code>Foo</code> is a supertype of <code>Bar</code>.</li>
<li>Encoding the variance of type parameters in the class file.</li>
</ul>

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

<p>In a first phase, the following artifacts will be produced:</p>

<ul>
<li>An enhanced version of the <code>javac</code> compiler.</li>
<li>Other OpenJDK tools and APIs with minor enhancements, as necessary (reflection, <code>javadoc</code>, <code>pack200</code>, etc.)</li>
<li>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.</li>
<li>Documentation describing any source compatibility risks for changes to previously-published classes.</li>
</ul>

<p>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 compilance tests (for the <code>JCK-compiler</code> suite).</p>

<h2>Non-Goals</h2>

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

<p>A language might be designed to infer the variance of type parameters, rather than requiring explicit syntax <a href="#1">[1]</a>.  Such analysis is outside the scope of this JEP.</p>

<p>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.</p>

<h2>Motivation</h2>

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

<p>But there are problems:</p>

<ul>
<li><p>Everyone has to cooperate.  If a library needlessly expects a <code>Predicate<String></code>, and you've got a <code>Predicate<? super String></code>, you have to do an unchecked cast or allocate a new object.</p></li>
<li><p>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, <code>Function<Iterator<S>, Predicate<T>></code> expands to <code>Function<? super Iterator<? extends S>, ? extends Predicate<? super T>></code>.)</p></li>
<li><p>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 <em>need</em> 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.</p></li>
</ul>

<p>The solution is to shift this burden from programmers to compilers, allowing a class or interface type parameter to be declared covariant or contravariant.</p>

<pre><code>interface Predicate<? super T> {
  boolean test(T arg);
}
</code></pre>

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

<p>A 2011 PLDI paper <a href="#1">[1]</a> performed an analysis of some open-source Java libraries that make use of generics, including the Java core libraries, Guava, and Apache Commons.  Findings:</p>

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

<p>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).</p>

<h2>Description</h2>

<p>Details of the four components of the feature, as listed in "Goals":</p>

<p><strong>Type parameter syntax.</strong>  The strawman syntax is to use <code>? extends T</code> in the declaration of <code>T</code> in order to indicate that it is covariant; <code>? super T</code> indicates that <code>T</code> is contravariant.  Thus, the <code>Function</code> interface might be declared as:</p>

<pre><code>interface Function<? super T, ? extends R> {
    R apply(T arg);
}
</code></pre>

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

<p><strong>Well-formedness checking.</strong>  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 <code>T</code>, then <code>T</code> should be invariant or contravariant—not covariant.  For more complex types, the analysis recurs: if the type of a method's parameter is <code>Predicate<T></code>, then <code>T</code> should be invariant or <em>covariant</em>.  The rules governing appropriate usage of type variables must be developed and implemented for every context in which a type variable can appear.</p>

<p>At the use site, a mismatch between the variance of a type parameter and the variance of a wildcard should also be avoided—<code>Iterator<? super String></code>, 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.)</p>

<p>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.</p>

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

<ul>
<li><p><em>Enhanced subtyping</em>: When subtyping encounters two parameterizations of the same class type, it performs a pairwise comparison of the type arguments using <em>type argument containment</em>.  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.</p>

<p>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.</p></li>
<li><p><em>Implicit wildcards</em>: Rather than making changes to subtyping, we preprocess the source code so that types like <code>Function<String, Number></code> are implicitly expanded to <code>Function<? super String, ? extends Number></code>.  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).</p></li>
</ul>

<p>There are advantages and disadvantages to each approach.  <em>Enhanced subtyping</em> is more direct and more closely aligned with users' intuition, while <em>implicit wildcards</em> 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.</p>

<p>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.</p>

<p><strong>Class file changes.</strong>  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 <code>Signature</code> attribute, introducing a new attribute, or piggybacking on an existing mechanism (like <code>RuntimeVisibleTypeAnnotations</code>).</p>

<p>Reflection APIs should probably understand this encoding and directly expose it to clients (e.g., a <code>TypeParameter.getVariance</code> method).</p>

<h2>Alternatives</h2>

<p>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.</p>

<p>There are good reasons for both use-site and declaration-site variance in a language; they are complementary <a href="#1">[1]</a> <a href="#2">[2]</a>.  Use-site gives users flexibility to tailor a type (like <code>List</code>) 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 <code>Iterator</code>).</p>

<p>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:</p>

<ul>
<li>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.</li>
<li>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.</li>
</ul>

<h2>Testing</h2>

<p>As a proposed language change, the enhancement should be accompanied by new <code>JCK-compiler</code> tests.</p>

<p>Behavior of existing compiler tests will be unchanged.</p>

<h2>Risks and Assumptions</h2>

<ul>
<li><p>Language enhancements are ultimately subject to the Java Community Process; this may influence the scope or design of the feature.</p></li>
<li><p>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 <em>any</em> 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.)</p></li>
<li><p>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.</p></li>
<li><p>If the <em>implicit wildcards</em> 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.</p></li>
</ul>

<h2>Dependencies</h2>

<p>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.</p>

<h2>Impact</h2>

<ul>
<li><p>Other JDK components: Minor changes may be necessary for <code>java.lang.reflect</code>, <code>javax.lang.model</code>, <code>javadoc</code>, <code>javap</code>, <code>pack200</code>, and ASM.  This is mostly to correctly process/expose the variance of type parameters, as encoded in class files.</p></li>
<li><p>Compatibility: Fully compatible with existing sources and binaries—the feature is irrelevant to code that does not use it.</p></li>
<li><p>Performance/scalability: We will experiment with <code>javac</code> compilation time, but it seems unlikely that there would be a significant impact.</p></li>
<li><p>Documentation: Language documentation and tutorials should explain and encourage use of the new feature.</p></li>
<li><p>Specification: Language changes will require proposing changes to JLS; minor class file format changes may also be proposed for JVMS.</p></li>
<li><p>TCK: New <code>JCK-compiler</code> tests will be necessary.</p></li>
</ul>

<h2>References</h2>

<p><a name="1">[1]</a> John Altidor, Shan Shan Huang, & Yannis Smaragdakis.  Taming the Wildcards: Combining Definition- and Use-Site Variance.  <a href="https://people.cs.umass.edu/~jaltidor/variance_pldi11.pdf">https://people.cs.umass.edu/~jaltidor/variance_pldi11.pdf</a>.</p>

<p><a name="2">[2]</a> Ross Tate.  Mixed-Site Variance.  <a href="http://www.cs.cornell.edu/~ross/publications/mixedsite/mixedsite-tate-fool13.pdf">http://www.cs.cornell.edu/~ross/publications/mixedsite/mixedsite-tate-fool13.pdf</a>.</p>