--- title: Theory Notes on Generic Programming date: 2024-11-25 excerpt: Introduce Variance in Generic Types, Type Erasure, and Related Concepts tags: [Java, Generics] updated: 2026-07-08 21:17:39 lang: en i18n: cn: /generic_theories translation: 2 --- ## Variance > Variance describes how subtyping relationships between more complex types (e.g., generics, collections, or function types.) relate to subtyping relationships between their component types. It determines whether a type system allows substitutability in specific contexts, especially in generic programming. - **Invariance**: The most restrictive relationship. If A is a subtype of B, `Container` and `Container` have no relationship at all. - **Covariance**: Preserves the subtype relationship. If A is a subtype of B, then `Container` is a subtype of `Container`. - **Contravariance**: Reverses the subtype relationship. If A is a subtype of B, then `Container` is a supertype of `Container`. Covariance and contravariance are closely related to polymorphism in OOP. For details, see this [StackOverflow answer](https://stackoverflow.com/questions/1078423/c-sharp-is-variance-covariance-contravariance-another-word-for-polymorphis) and Eric Lippert's [series of articles](https://ericlippert.com/category/covariance-and-contravariance/). ### Invariance Generics in Java are invariant. Whether or not A and B have an inheritance relationship, `Container` and `Container` never do. > - Arrays differ from generic type in two important ways. First arrays are covariant. Generics are invariant. > - Covariant simply means if `X` is subtype of `Y` then `X[]` will also be sub type of `Y[]`. Arrays are covariant As string is subtype of Object So `String[]` is subtype of `Object[]` > - Invariant simply means irrespective of `X` being subtype of `Y` or not ,`List` will not be subType of `List`. > > **《Effective Java》** Joshua Bloch To verify this, consider the following code. If `ArrayList` were a subtype of `ArrayList`, the code below would be legal. In fact, the compiler reports an error. ```java import java.util.ArrayList; public class Invariance { public static void main(String[] args) { // Get the Class object of ArrayList ArrayList list1 = new ArrayList<>(); ArrayList list2 = new ArrayList<>(); list1 = list2; } } [ERROR] Type mismatch: cannot convert from ArrayList to ArrayListJava(16777233) [Ln 8, Col 11] ``` The `A.isAssignableFrom(B)` method checks whether two classes have an inheritance relationship; it is mainly used inside the JDK source code. Note that because of type erasure, both `ArrayList` and `ArrayList` have the runtime type `ArrayList`, so they cannot be distinguished at runtime. Checking their relationship with the following code leads to the wrong conclusion. ```java import java.util.ArrayList; public class Invariance { public static void main(String[] args) { // Get the Class object of ArrayList ArrayList list1 = new ArrayList<>(); ArrayList list2 = new ArrayList<>(); if (list1.getClass().isAssignableFrom(list2.getClass())) { System.out.println("list1 is assignable from list2"); } else { System.out.println("list1 is not assignable from list2"); } } } [OUTPUT] list1 is assignable from list2 ``` ### Covariance Arrays in Java are covariant. Consider the following code: `String` is a subtype of `Object`, so `String[]` is a subtype of `Object[]`. ```java String[] strings = new String[10]; Object[] objects = strings; ``` Why did the JDK designers make arrays covariant but generics invariant? If you are curious, read ### Contravariance Contravariance is the reverse of covariance: a generic type over a subtype can stand in for the generic type over its supertype. > [!note] Wildcards > There are various reasons why generics were designed to be invariant, but it can feel awkward at first: an apple `IS A` fruit, yet a container of apples `IS NOT A` container of fruit. > > To use generics more flexibly and correctly, consider wildcards. Pay attention to upper and lower bounds on wildcards, and to the PECS principle. > > [[java_generic#Wildcards]] ## Erausre ### Releated Concepts **Reifiable type** A reifiable type is a type whose type information is fully available at runtime. This includes primitives, non-generic types, raw types, and invocations of unbound wildcards. | | examples | | ---------------- | -------------------------- | | Primitive types | `int`, `double`, `boolean` | | None-generic | `String`, `Integer` | | Raw types | `List`, `Set` | | Unbound wildcard | `List` | **Non-reifiable type** | | examples | | ------------------- | ------------------------------------------------------------ | | parameterized types | `List`, `Map` | | wildcard types | `List`, `List`, `List` | _Tips: reifiable = reify (vt. to make concrete) + able_ **Heap Pollution** Heap pollution in Java occurs when a variable of a parameterized type refers to an object that is not of that type. **Homogeneous/Heterogeneous translations** Java architect Brian Goetz explained the design philosophy behind generics, and why type erasure was chosen, in [Background: How We Got the Generics We Have](https://openjdk.org/projects/valhalla/design-notes/in-defense-of-erasure). In that article he described two approaches to translating parameterised types: > - Homogeneous translation: a generic class `Foo` is translated into a single artifact, such as `Foo.class` (and same for generic methods) > - Heterogeneous translation: each instantiation of a generic type or method (`Foo, Foo`) is treated as a separate entity, and generates separate artifacts. > > Releated paper:[《Two Ways to Bake Your Pizza— Translating Parameterised Types into Java》](https://pizzacompiler.sourceforge.net/doc/pizza-translation.pdf) ### Type Erasure in Java Generics were introduced to the Java language to provide tighter type checks at compile time and to support generic programming. To implement generics, the Java compiler applies type erasure to: - Replace all type parameters in generic types with their bounds or Object if the type parameters are unbounded.The produced bytecode, therefore, contains only ordinary classes, interfaces, and methods. ```java public class Box { private T value; public void set(T value) { this.value = value; } public T get() { return value; } } public class Foo { private T value; public void set(T value) { this.value = value; } public T get() { return value; } } ``` ```java public class Box { private Object value; public void set(Object value) { this.value = value; } public Object get() { return value; } } public class Foo { private Number value; public void set(Number value) { this.value = value; } public Number get() { return value; } } ``` - Insert type casts if necessary to preserve type safety. ```java Box integerBox = new Box<>(); integerBox.set(10); Integer value = integerBox.get(); ``` ```java Box integerBox = new Box(); integerBox.set(10); Integer value = (Integer) integerBox.get(); // insert type cast ``` - Generate bridge methods to preserve polymorphism in extended generic types. Type erasure keeps generics backward compatible, but it can also cause method signature conflicts that break polymorphism. A bridge method is a compiler-generated intermediate method that bridges the parent and child method implementations to preserve polymorphism. ```java class Parent { public T getValue() { return null; } } // Generic subclass class Child extends Parent { @Override public String getValue() { return "Child Value"; } } // Parent parent = new Child(); // Object value = parent.getValue(); // Call chain: // parent.getValue() // | // v // Child.bridge$getValue() // bridge method // | // v // Child.getValue() // the actual method returning String // | // v // "Child Value" (converted to Object) public class Main { public static void main(String[] args) { Parent parent = new Child(); Object value = parent.getValue(); // The JVM calls the bridge method, which routes to the subclass method System.out.println(value); } } [OUTPUT] Child Value // Inspect the compiled bytecode $ javap -c Child [OUTPUT] class Child extends Parent { Child(); Code: 0: aload_0 1: invokespecial #1 // Method Parent."":()V 4: return public java.lang.String getValue(); Code: 0: ldc #7 // String Child Value 2: areturn public java.lang.Object getValue(); Code: 0: aload_0 1: invokevirtual #9 // Method getValue:()Ljava/lang/String; 4: areturn } ``` ## Ref [docs.oracle.com/javase/tutorial/java/generics/erasure.html](https://docs.oracle.com/javase/tutorial/java/generics/erasure.html) [docs.oracle.com/javase/tutorial/java/generics/nonReifiableVarargsType.html](https://docs.oracle.com/javase/tutorial/java/generics/nonReifiableVarargsType.html) [An Expert‘s Guide to Generic Types in Java: Covariance, Contravariance, and Beyond](https://www.bomberbot.com/programming/an-experts-guide-to-generic-types-in-java-covariance-contravariance-and-beyond/) [Java Generics - Bridge method? —— StackOverflow](https://stackoverflow.com/questions/5007357/java-generics-bridge-method) [Java bridge methods explained —— STAS](https://stas-blogspot.blogspot.com/2010/03/java-bridge-methods-explained.html)