Typesspec

Variance: Why `List<Dog>` Is Not a `List<Animal>`

A function is contravariant in its argument and covariant in its result; a mutable container must be invariant in its element. Java made arrays covariant anyway, and pays for it with a runtime check on every array store — `ArrayStoreException` is that decision, visible.

The question

If Dog <: Animal, is List<Dog> <: List<Animal> — and why is the answer usually no?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute

What the program is here

A per-parameter annotation on a type constructor, recording how the constructor propagates the subtyping relation of its argument. Given S <: T, variance is what determines the relation between F<S> and F<T>. Without it a checker cannot decide any assignment involving a generic type, so the annotation — written or inferred — is a required part of every generic type’s definition.

What this phase may assume or do

A type parameter may be covariant only if it appears in output positions, contravariant only if it appears in input positions, and must be invariant if it appears in both. A mutable container puts its parameter in both positions by construction — the getter returns it, the setter accepts it — so the parameter must be invariant, or the language must insert a runtime check to close the hole it opened.

Key points

Variance answers: given S <: T, what is the relation between F<S> and F<T>?
Covariant if the parameter appears only in output positions; contravariant if only in input positions; invariant if in both.
Functions are contravariant in the argument and covariant in the result: accept more, return less.
A mutable container has its parameter in both positions, so it must be invariant. Mutability and covariance cannot coexist soundly.
Java arrays are covariant and mutable, which is unsound, and the hole is closed by a runtime check on every array store — ArrayStoreException.
Java generics, added nine years later, are invariant instead. One language, two answers, and the difference is hindsight.
Declaration-site variance (Kotlin, C#, Scala) states it once; use-site variance (Java wildcards) states it at every use; Rust infers it and never writes it.
PECS — Producer Extends, Consumer Super — is the position rule with a mnemonic attached.
Immutability buys variance. That is a benefit of immutable types that has nothing to do with concurrency.

Three answers, and one unsound fourth

specKotlin’s out/in, C#’s out/in on interface type parameters and Scala’s +/- are declaration-site annotations checked by the compiler: it rejects out T used in an input position. Java has no declaration-site variance and provides use-site wildcards instead. Rust never writes variance at all — it is inferred structurally from where the parameter appears, and PhantomData is the mechanism for forcing a variance when the parameter appears nowhere.

Given Dog <: Animal, there are exactly three sound possibilities for Box<Dog> versus Box<Animal>, and which one holds is decided by *where the parameter appears in the type*, not by anything about boxes.

The position rule is the whole of the theory: a value of type T can come *out* of a structure or go *in*. If it can only come out, the structure is safe to widen — everything you can read from a Producer<Dog> is an Animal. If it can only go in, the structure is safe to *narrow* — anything that can consume any Animal can certainly consume a Dog. If it can do both, neither direction is safe.

Given S <: T, what is the relation between F<S> and F<T>?spec

Variance	Relation	Parameter may appear	Written as	Canonical example
Covariantspec	`F<S> <: F<T>` — same direction	Output positions only: return types, readable fields	Kotlin `out T`, C# `out T`, Java use-site `? extends T`, Scala `+T`	`Iterable<out T>`, `IEnumerable<out T>`, an immutable list — a producer
Contravariantspec	`F<T> <: F<S>` — reversed	Input positions only: parameter types, writable-only sinks	Kotlin `in T`, C# `in T`, Java use-site `? super T`, Scala `-T`	`Comparator<in T>`, `Action<in T>`, a logging sink — a consumer
Invariantspec	No relation in either direction	Both input and output positions	The default everywhere	`MutableList<T>`, Java’s `List<T>`, Rust’s `&mut T` and `Cell<T>`
Bivariant (unsound)implementation	Both directions accepted	Anywhere — the rule is simply not enforced	Not written; it is a hole	Java and C# arrays, TypeScript method parameters. Each is a documented, deliberate hole.

The function rule, which is the one to memorise

Function types are where variance is least intuitive and most useful, because both directions appear in one rule.

The rule says a function is a subtype of another if it accepts more and returns less. Contravariant in the argument, covariant in the result. Put concretely: if a caller has been promised a (Dog) -> Animal, you may hand them an (Animal) -> Dog. It handles any Dog, because it handles any Animal at all. And its result is a Dog, which is an Animal, so the caller gets what it was promised. Every substitution works out.

Try it the other way and it breaks immediately. If the caller has a (Dog) -> Animal and you hand them a (Poodle) -> Animal, the caller may pass a Beagle and your function cannot handle it. Argument positions must go the other way. This is Postel’s “be liberal in what you accept, conservative in what you send” arriving as a typing rule rather than as advice.

The function subtyping rule, and how to read it

      T₁ <: S₁          S₂ <: T₂
     ──────────────────────────────
      (S₁) → S₂    <:    (T₁) → T₂

Notice the FIRST premise runs backwards:
   T₁ <: S₁     the argument relation is REVERSED
   S₂ <: T₂     the result relation runs forwards

Concretely, with  Dog <: Animal:

   (Animal) → Dog     <:     (Dog) → Animal      ✓
   ^ accepts MORE            ^ what was promised
          ^ returns LESS

   (Dog) → Animal     <:     (Animal) → Dog       ✗
   cannot handle a Cat, and does not promise a Dog

Mnemonic:  a function that is HARDER TO BREAK and
           MORE SPECIFIC in what it gives back is
           always an acceptable substitute.

This is also why an override may widen its return type
(Java allows it) and may NOT widen its parameter types
(Java would treat that as a new overload).

Java’s covariant arrays: the hole, made concrete

specArray covariance is JLS 4.10.3 and ArrayStoreException is JLS 10.5 — both required behaviour, not implementation choices, and both unchanged since Java 1.0. Java generics are invariant by specification, with wildcards providing use-site variance. C# has the same array covariance with ArrayTypeMismatchException, and invariant generics with opt-in in/out on interface and delegate type parameters only.

Java specifies that if S <: T then S[] <: T[]. Arrays are covariant. An array is also mutable, so its element type appears in both an output position (reading an element) and an input position (storing one). By the position rule this is unsound, and it is: the four lines below type-check completely and throw.

Java could not simply reject the store at compile time, because the compiler sees objs as an Object[] and storing an Integer into an Object[] is entirely legal. The information that the array is *actually* a String[] exists only at runtime. So the language closes the hole where the information is available: every array store carries a runtime check of the value’s type against the array’s actual component type, and throws ArrayStoreException when it fails.

Why accept this? History, and it is worth knowing because it explains the shape of the whole language. Java 1.0 had no generics. Without covariant arrays there would have been no way to write Arrays.sort(Object[]) and call it on a String[], or System.arraycopy usefully, or any general-purpose array utility at all. Covariance was the pragmatic choice available in 1995, and the runtime check was the price. When generics arrived in Java 5 the designers had the option again and took the other one: generics are invariant, so List<String> is not a List<Object>, and the corresponding mistake is a compile error instead.

So Java contains both answers to the same question, and the difference between them is nine years of hindsight. C# repeated the array decision — ArrayTypeMismatchException is its equivalent — and also made generics invariant with opt-in in/out annotations on interfaces.

Java: the same mistake, twice, with two different outcomes

1// ARRAYS — covariant by specification (JLS 4.10.3)
2Object[] objs = new String[1];   // legal: String[] <: Object[]
3objs[0] = 42;                    // COMPILES.
4                                 // throws java.lang.ArrayStoreException
5                                 //   at run time, per JLS 10.5
6 
7// GENERICS — invariant by specification
8List<Object> list = new ArrayList<String>();   // COMPILE ERROR:
9//   incompatible types: ArrayList<String> cannot be converted
10//   to List<Object>
11 
12// Use-site variance recovers the safe half:
13List<? extends Number> nums = new ArrayList<Integer>();  // ok
14Number n = nums.get(0);          // reading is fine — covariant
15// nums.add(1);                  // COMPILE ERROR — writing is not

The last block is the position rule enforced syntactically. ? extends Number says “I will only read”, so the compiler permits the widening and then refuses every write. ? super Number says the opposite. That is the PECS mnemonic — Producer Extends, Consumer Super — and it is the position rule with a different name.

Declaration-site, use-site, and the languages that never write it

Once a language decides that variance exists, it must decide who states it and where.

Declaration-site — Kotlin, C#, Scala. The library author writes interface Iterable<out T> once, and the compiler verifies that T is used only in output positions. Every use site then gets the variance for free. The costs are that the author must get it right, that some types genuinely cannot be annotated (anything read-write), and that adding an annotation later is a compatible change while removing one is not.

Use-site — Java wildcards. The library declares List<T> invariantly; each consumer writes List<? extends Animal> or List<? super Dog> at the point of use. This is more flexible — one type serves both roles depending on how you use it — and the cost is that wildcards spread through every signature, that PECS becomes something people memorise, and that the resulting errors ("capture of ?") are among the least readable messages the language produces.

Inferred, never written — Rust. Variance is computed structurally from where the parameter occurs: &'a T is covariant in both, &'a mut T is covariant in the lifetime and *invariant* in T, fn(T) is contravariant in T, and Cell<T>/UnsafeCell<T> are invariant. Nothing is annotated, which means nothing can be got wrong — and also that when a lifetime error is really a variance error, there is no annotation to point at, which is why those errors are the hard ones.

Deliberately unsound — TypeScript. Function type parameters are checked contravariantly under strictFunctionTypes, and *method* parameters remain bivariant even with the flag on. That exception is documented and deliberate: Array<T>’s methods and most of the DOM would fail to type-check under a sound rule, and the compatibility cost was judged higher than the soundness benefit. It is the same trade Java made with arrays, made knowingly and much later.

Who states the variance, and what that costsimplementation

Approach	Languages	Written where	Advantage	Cost
Declaration-sitespec	Kotlin, C#, Scala	Once, on the type parameter	Every use site benefits; the compiler verifies positions once	Read-write types cannot be annotated at all; the author carries the burden
Use-sitespec	Java wildcards	At each use, in each signature	One invariant type serves as producer or consumer depending on the use	Wildcards propagate through signatures; capture errors are notoriously unreadable
Inferred structurallyspec	Rust	Nowhere — computed from occurrence	Impossible to state incorrectly; `PhantomData` forces it where needed	No annotation exists to blame when a variance error surfaces as a lifetime error
Unsound by choiceimplementation	Java/C# arrays, TypeScript methods	Nowhere	Compatibility with a large existing ecosystem	A runtime check on every store (Java), or a silent hole (TypeScript)
No variance at allspec	Go generics	Nowhere	Nothing to learn; `[]Dog` is simply not a `[]Animal`	Conversions must be written by hand, element by element

The rule behind all of it

Every case above is one principle applied to different syntax: mutability and covariance cannot coexist soundly. A container you can only read may be widened. A container you can only write may be narrowed. A container you can do both to may be neither.

That is why immutable collections in Scala and Kotlin are covariant and their mutable siblings are not; why &T in Rust is covariant and &mut T is not; why Java’s wildcard that permits reading forbids writing; and why arrays — mutable and covariant — need a runtime check to stay sound.

It also connects directly to immutability as a design tool. Making a type immutable is not only about shared mutable state and concurrency; it *buys variance*, and with it the ability to write List<Dog> where List<Animal> is wanted, with no wildcards, no annotations and no runtime check. That is a concrete, checkable benefit of immutability that has nothing to do with threads and is rarely mentioned alongside the usual ones.

Making a parameter covariant by narrowing what the function may do

Before

void feedAll(List<Animal> animals) {
    for (Animal a : animals) a.eat();
}
// callers cannot pass a List<Dog>: generics are invariant

After

void feedAll(List<? extends Animal> animals) {
    for (Animal a : animals) a.eat();
}
// callers may now pass List<Dog>, List<Cat>, List<Animal>

Legal only when

Widening a parameter to a covariant wildcard is legal only if the body never writes to the collection. The compiler enforces this: with ? extends Animal, every mutating method that takes an element is rejected, because the actual element type is unknown and could be narrower than Animal. Under that restriction the widening is sound and every existing caller still compiles.

Illegal when

When the body adds to the collection. animals.add(new Cat()) is a compile error under ? extends Animal, and rightly: the list may actually be a List<Dog>, and a Cat in it would be read back as a Dog later. If you need to both read and write, the parameter must stay invariant — this is precisely the position rule, and the compile error is the language refusing to reproduce Java’s array mistake.

How it works

The steps, in the order the compiler takes them.

For each type parameter of a generic type, determine every position in which it occurs across the type’s members.
Classify each occurrence: a return type or readable field is an output position; a parameter type or writable field is an input position; a mutable field is both.
Assign covariance if all occurrences are outputs, contravariance if all are inputs, invariance otherwise. Nested function types flip the classification, so a parameter of a parameter is an output.
In a declaration-site language, verify the author’s written annotation against this analysis and reject a mismatch. In Rust, take the computed answer as the definition.
When checking an assignment F<S> to F<T>, consult the variance of each parameter and require S <: T, T <: S, or S = T accordingly.
For use-site variance, treat each wildcard as introducing a fresh bounded type variable (capture), and reject any member use whose signature would need to name it in a forbidden position.
Where the language chose unsoundness, the back end must emit the compensating runtime check — for Java arrays, a component-type test on every aastore.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

An array store throws ArrayStoreException at a line that contains no cast and looks completely ordinary; the actual mistake was the covariant assignment several functions earlier.
An assignment between two generic types is rejected with “incompatible types” and both sides look obviously compatible; the answer is invariance, and the fix is a wildcard or an out annotation rather than a cast.
A cast is used to silence the invariance error, the collection is then written to through the widened alias, and a value of the wrong type is read back later as the wrong type — the array bug reproduced by hand.
A Java signature grows wildcards until it is unreadable, and a “capture of ?” error appears that names a type variable the compiler invented and the programmer cannot write.
In TypeScript, a callback with a narrower parameter type is accepted because method parameters are bivariant, and a value the callback cannot handle reaches it at runtime.
In Rust, a lifetime error appears on a &mut that the programmer expected to be covariant, with no annotation anywhere to point at, because the invariance was inferred.
A hot loop is slower than expected because every array store carries a component-type check that the JIT could not eliminate — invisible in the source, visible only in the disassembly.

When it helps

Reading a rejected generic assignment. The three-way question — is this parameter read, written, or both — resolves almost all of them without consulting documentation.
Designing a generic API: deciding read-only, write-only or both up front determines whether callers will need wildcards on every call, and that decision is much cheaper before publication than after.
Explaining why immutable collections are more pleasant to pass around than mutable ones, in a way that is checkable rather than aesthetic.
Diagnosing ArrayStoreException, which is otherwise one of the more baffling exceptions in Java because the throwing line is innocent.

When it hurts

When wildcards spread. A signature with three wildcards has stopped communicating, and the usual fix — an extra type parameter with a bound — trades one kind of noise for another.
When variance is used to avoid designing the API. If a collection genuinely needs to be read and written, no annotation will make it covariant, and reaching for a cast recreates the array hole by hand.
In languages with unsound variance, where the rule you learned does not apply and the compiler will accept something that fails later.
When reasoning about Rust lifetimes as if they were invariant. They are not, and &'a mut T being covariant in 'a while invariant in T is the specific fact behind a great many confusing errors.

What it costs

Every one of these is paid by something.

Declaration-site variance buys correctness once and for all use sites, and pays in expressiveness — a read-write type cannot be annotated at all — and in a burden placed entirely on the library author.
Use-site variance buys per-use flexibility from one invariant declaration, and pays in wildcards propagating through every signature, in a mnemonic every user must learn, and in capture errors that are genuinely hard to read.
Unsound covariance buys compatibility with code that predates generics, and pays with a runtime check on every store — a real, permanent cost on every array write in Java, whether or not any program depends on the covariance.
Invariance by default buys soundness with no annotations and no runtime cost, and pays in assignments that look obviously fine being rejected, which is a recurring source of friction and of casts added to make it go away.
Inferring variance structurally buys the impossibility of stating it wrongly, and pays in diagnosability: there is no annotation to blame, so a variance failure surfaces as a lifetime or borrow error at a distance from its cause.

What else you could do

What a different compiler or language does instead, and when that is better.

No variance at all, as in Go generics: []Dog is not a []Animal and never will be, so conversions are written explicitly. Nothing to learn and nothing to get wrong, at the cost of hand-written copies.
Separate read-only and read-write types, as Kotlin does with List<out T> and MutableList<T>. This gets covariance where it is safe and invariance where it is not, by making the distinction visible in the type name.
Immutable collections throughout, which makes covariance sound by construction and removes the question; the Concurrency domain covers the other reasons to want it.
Runtime checks in place of static rules, which is what Java arrays and every dynamically typed language do: allow the assignment and verify each operation on the values involved.
Row polymorphism instead of subtyping over containers, expressing “a collection of at least these things” with a type variable rather than a variance annotation — keeps principal types and avoids the question entirely.

See it for yourself

The flag, dump or tool that shows you this directly.

Java: javap -c on an array store shows aastore, which is where the runtime component-type check happens. Compare with List.add, compiled to an invokeinterface with no such check.
Run the four-line Object[] objs = new String[1] example. It compiles without a warning and throws immediately, which is more convincing than any explanation.
Kotlin: try to declare interface Box<out T> { fun set(v: T) } — the compiler rejects it, naming the position. That error message is the position rule stated by the tool.
Rust: rustc --explain E0308 and the variance section of the Rustonomicon; adding PhantomData<fn(T)> versus PhantomData<T> to a struct changes its variance, which is the cleanest way to see the mechanism.
TypeScript: compile a callback assignment with and without strictFunctionTypes, and then try the same thing with the callback declared as a method rather than a property — the method version is accepted either way, which demonstrates the deliberate bivariance.
C#: object[] a = new string[1]; a[0] = 42; throws ArrayTypeMismatchException — the same decision, in a second language, with a different exception name.

Plausible wrong readings

Stated the way a confident engineer states them.

“List<Dog> should obviously be a List<Animal>.” Only if you never write to it. The moment you can add a Cat, the widening is unsound, and Java’s arrays demonstrate exactly what goes wrong.
“Contravariance is a rare edge case.” It is the rule for every function parameter, which means it applies to every callback, comparator, event handler and visitor you pass anywhere.
“ArrayStoreException means someone made a mistake with casts.” It means someone used array covariance, which the language permits without a cast or a warning.
“Variance is a Java wildcards problem.” Java made it visible. The rule applies in Kotlin, C#, Scala, Rust and TypeScript, and each solved it differently.
“Rust has no variance because you never write it.” Rust has full variance rules, inferred structurally. &mut T being invariant in T is why a great many borrow errors happen.

Misconceptions

The claim, and what is actually true.

Covariance is the natural default and invariance is the compiler being fussy.

Covariance is sound only for read-only structures. Invariance is the correct default for anything mutable, and the languages that made covariance the default had to add a runtime check to stay sound.

Wildcards are Java boilerplate that a better language would not need.

They are use-site variance, and they buy something declaration-site variance cannot: one invariant type usable as producer or consumer depending on the call. The tradeoff is real in both directions.

ArrayStoreException is a bug in the JVM.

It is the specification working as designed. The language permits an unsound assignment and closes the hole at the only point where the necessary information exists — the store.

Making a class immutable is only about thread safety.

It also makes the type parameter covariant, which removes wildcards from every signature that consumes it. That is a type-system benefit with no concurrency content.

Function types are covariant in everything, like other generic types.

They are contravariant in their parameters. This is the rule that decides whether a callback, comparator or handler can be substituted, and it is backwards from most people’s first guess.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

If a Dog is an Animal, is a list of dogs a list of animals? Only if you promise not to put anything into it. If you can add to the list, someone could add a Cat through the animal-shaped view, and the original owner would later read a Cat where they expected a Dog. So read-only containers may be widened, write-only containers may be narrowed, and anything you can both read and write may be neither. Java made arrays an exception, allowed the widening anyway, and pays for it by checking the type of every value stored into an array at runtime — that is what ArrayStoreException is.

practical

When a generic assignment is rejected and both sides look compatible, ask one question: does this code read from the value, write to it, or both? Read-only means you want the covariant form — ? extends T in Java, out T in Kotlin and C#. Write-only means the contravariant form — ? super T, in T. Both means it must stay invariant, and any cast you add to get around that is recreating the array bug by hand. For callbacks and comparators, remember the direction flips: a handler that accepts a broader type is a valid substitute for one that accepts a narrower one. And if you own the type, consider whether it needs to be mutable at all — an immutable collection is covariant for free, and that removes wildcards from every signature that touches it.

advanced

Variance is where the interaction of three features — subtyping, generics and mutation — produces an unsoundness that every language has had to patch, and comparing the patches is instructive. Java patched arrays with a runtime check and made generics invariant, so the same language demonstrates both the mistake and the correction. C# repeated the array mistake and then added declaration-site in/out, but only on interfaces and delegates, because a class can have mutable fields and could not be annotated soundly. Scala and Kotlin split the hierarchy so that immutable and mutable collections are different types with different variance. Rust sidestepped annotation entirely by inferring variance from structure, which makes it impossible to state wrongly and impossible to point at when it goes wrong. TypeScript reproduced the hole knowingly, for compatibility, and documented it. Underneath all five is one theorem: a type parameter may be covariant only in output positions, and mutation puts it in an input position. Everything else is a negotiation about who pays — the library author, the caller, the runtime, or the user who eventually hits the exception.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

specJava array covariance is JLS 4.10.3 and ArrayStoreException is JLS 10.5, both required since Java 1.0 and both unchanged. Java generics are invariant by specification with use-site wildcards; there is no declaration-site variance in the language. C# mirrors the array decision with ArrayTypeMismatchException and provides declaration-site in/out on interface and delegate type parameters only — not on classes.

specKotlin and Scala check declaration-site variance annotations against occurrence positions and reject a covariant parameter used in an input position. Rust specifies variance as inferred from structure: &'a T covariant in both, &'a mut T covariant in 'a and invariant in T, fn(T) -> U contravariant in T and covariant in U, Cell<T> and UnsafeCell<T> invariant. None of these is written by the programmer.

implementationTypeScript’s strictFunctionTypes makes standalone function-type parameters contravariant and deliberately leaves *method* parameters bivariant, because Array<T> and much of the DOM would not type-check otherwise. This is documented as intentional and has been stable since TypeScript 2.6; it means a sound-variance mental model will predict rejections that do not happen.

typicalThe claim that the JIT can eliminate an array-store check describes HotSpot behaviour when the exact array type is provably known at the store, which is common in monomorphic loops and not guaranteed. Whether a particular store retains its check is an optimization outcome — see [[speculative-optimization]] and [[devirtualization]] — and must be read from the generated code rather than assumed.

If you were asked this in an interview

If Dog <: Animal, is List<Dog> <: List<Animal>? Explain your answer in terms of read and write positions.
State the subtyping rule for function types and explain why the argument position is reversed.
Java arrays are covariant. Show me the four lines that break, and say what the JVM does about it.
Why are Java generics invariant when Java arrays are not?
What is the difference between declaration-site and use-site variance, and what does each cost?
Explain how making a collection immutable changes its variance.

Connections

DSAhash-table

Concurrencyimmutability shared-mutable-state copy-vs-share

API Designbackward-compatibility enum-evolution

Domains that do not exist yet

Programming Languages & Runtime Internals — The runtime component-type check on an array store, and when a JIT can remove it
Java’s covariance hole is closed by a check the JVM performs on every aastore. Whether that check survives optimization is a runtime and JIT question; this lesson establishes only why the check must exist.
Software Design — Designing read-only and read-write views of the same data as separate types
Splitting a collection interface so the read-only half can be covariant is a design decision with API consequences. The type-system reason to do it is here; whether to reorganise an API around it belongs there.

Runtime gain2

Compile cost2

Debuggability2

Implementation4

Context dependence5

Runtime cost is normally zero — variance is a compile-time relation — except where a language chose unsoundness and must compensate, which is why Java pays a component-type check on every array store forever. Debuggability is low: variance failures surface as confusing assignment errors, unreadable capture messages, or a runtime exception on an innocent-looking line. Context dependence is maximal, because every language answers this question differently and two of them answer it unsoundly.