Covariant structure fails with capture-of error in Java

Question

Consider the following Java class definitions:

class Animal {}
class Lion extends Animal {}

When defining a covariant Cage for Animals I use this code in Java:

class Cage<T extends Animal> {
void add(T animal) { System.out.println("Adding animal..."); }
}

But the following Java example ...

public static void main(String... args) {
    Cage<? extends Animal> animals = null;
    Cage<Lion> lions = null;
    animals = lions;         // Works!
    animals.add(new Lion()); // Error!
}

... fails to compile with the following error:

The method add(capture#2-of ? extends Animal) in the type Cage is not applicable to for the arguments (Lion)

Is this done because otherwise a different type like Tiger could be added after animals = lions and fail at runtime?

Could a special (hypothetical) rule be made that would not rejected it iff there would be only one sub-type of Animal?

(I know that I could replace add's T with Animal.)

Answer 1

In java :

Cage<? extends Animal> animals = null;

This is a cage, but you don't know what kind of animals it accepts.

animals = lions;         // Works!

Ok, you add no opinion about what sort of cage animals was, so lion violates no expectation.

animals.add(new Lion()); // Error!

You don't know what sort of cage animals is. In this particular case, it happens to be a cage for lions you put a lion in, fine, but the rule that would allow that would just allow putting any sort of animal into any cage. It is properly disallowed.

In Scala : Cage[+T] : if B extends A, then a Cage[B] should be considered a Cage[A].

Given that, animals = lions is allowed.

But this is different from java, the type parameter is definitely Animal, not the wildcard ? extends Animal. You are allowed to put an animal in a Cage[Animal], a lion is an animal, so you can put a lion in a Cage[Animal] that could possibly be a Cage[Bird]. This is quite bad.

Except that it is in fact not allowed (fortunately). Your code should not compile (if it compiled for you, you observed a compiler bug). A covariant generic parameter is not allowed to appear as an argument to a method. The reason being precisely that allowing it would allow putting lions in a bird cage. It T appears as +T in the definition of Cage, it cannot appears as an argument to method add.

So both language disallow putting lions in birdcages.

---

Regarding your updated questions.

Is it done because otherwise a tiger could be added?

Yes, this is of course the reason, the point of the type system is to make that impossible. Would that cause un runtime error? In all likelihood, it would at some point, but not at the moment you call add, as actual type of generic is not checked at run time (type erasure). But the type system usually rejects every program for which it cannot prove that (some kind of) errors will not happen, not just program where it can prove that they do happen.

Could a special (hypothetical) rule be made that would not rejected it iff there would be only one sub-type of Animal?

Maybe. Note that you still have two types of animals, namely Animal and Lion. So the important fact is that a Lion instance belongs to both types. On the other hand, an Animal instance does not belong to type Lion. animals.add(new Lion()) could be allowed (the cage is either a cage for any animals, or for lions only, both ok) , but animals.add(new Animal()) should not (as animals could be a cage for lions only).

But anyway, it sounds like a very bad idea. The point of inheritance in object oriented system is that sometime later, someone else working somewhere else can add subtype, and that will not cause a correct system to become incorrect. In fact, the old code does not even need to be recompiled (maybe you do not have the source). With such a rule, that would not be true any more

Answer 2

I think this question might answer that for you:

java generics covariance

Basically, Java generics are not covariant.

The best explanation I know for this comes, of course, from Effective Java 2nd Edition.

You can read about it here:

http://java.sun.com/docs/books/effective/generics.pdf

I think the hypothetical rule would be quite hard to enforce in runtime. The compiler could theoretically check if all objects explicitly added to the list are indeed of the same type of animal, but I'm sure that there are conditions that could break this in runtime.

Answer 3

When you declare your variable with this type: Cage<? extends Animal>; you're basically saying that your variable is a cage with some unkown class that inherits from Animal. It could be a Tiger or a Whale; so the compiler doesn't have enough information to let you add a Lion to it. To have what you want, you declare your variable either as a Cage<Animal> or a Cage<Lion>.

Answer 4

If so, that is likely a bug in the Scala compiler. Odersky et al. write in An Overview of the Scala Programming Language:

Scala’s type system ensures that variance annotations are sound by keeping track of the positions where a type pa- rameter is used. These positions are classied as covariant for the types of immutable elds and method results, and contravariant for method argument types and upper type parameter bounds. Type arguments to a non-variant type parameter are always in non-variant position. The position ips between contra- and co-variant inside a type argument that corresponds to a contravariant parameter. The type system enforces that covariant (respectively, contravariant) type parameters are only used in covariant (contravariant) positions.

Therefore, the covariant type parameter T must not appear as method argument, because that is a contravariant position.

A similar rule (with more special cases, none of which matter in this case) is also present in the the Scala Language Specification (version 2.9), section 4.5.