Why is the implicit cast of ArrayList> to Iterable> impossible?

Question

I would like to know the reason why Java can't cast ArrayList<ArrayList<T>> to Iterable<Iterable<T>> implicitly. My question is not about how to do it explicitly.

Why does the following code:

import java.util.Iterator;
import java.util.ArrayList;

public class Test {
  public Test() {
    ArrayList<ArrayList<Test>> arr = new ArrayList();
    Iterable<Iterable<Test>> casted = arr;
  }
}

raise the following error during compilation?

Test.java:7: error: incompatible types: ArrayList<ArrayList<Test>> cannot be converted to Iterable<Iterable<Test>>

Answer 1

ArrayList is Iterable, you're right, so ArrayList<ArrayList<Test>> is Iterable<ArrayList<Test>>.

BUT Iterable<Iterable<Test>> is not Iterable<ArrayList<Test>>, because in this case you, of course, can't explicitly add something to Iterable, but it's possible situation, that you can (with other examples), so you may add, for example, Set<Test> within it, so this would break arr.

You can work around this with using bounded generics:

Iterable <? extends Iterable<Test>> casted = arr;

So, when you run iterator() on casted you'll get Iterator<? extends Iterable<Test>> and withing every next() you'll get ? extends Iterable<Test>, which is Iterable<Test>.

You should read something about covariance and countervariance in Java to get this.

Answer 2

Because how Generics work. You would have to use:

ArrayList<ArrayList<Test>> arr = new ArrayList();
Iterable<? extends Iterable<Test>> casted = arr;

ArrayList<ArrayList> is not compatible with Iterable<Iterable> because generics are strict. ArrayList is not Iterable, but it is ? extends Iterable

However, this has limitations. Consider

ArrayList<? extends Iterable<Test>> casted = arr;

This work. But now, casted is bound to basically no type. You cannot call add on it, because no type is compatible.

Answer 3

Let's look at a few similar examples:

public final class Test {
  public Test() {
    final ArrayList<ArrayList<Test>> a1 = new ArrayList<>();
    final ArrayList<? extends Iterable<Test>> valueTypeRef = a1;
    final Iterable<? extends Iterable<Test>> spinalTypeRef = valueTypeRef;

    final ArrayList<Iterable<Test>> a2 = new ArrayList<>();
    final Iterable<Iterable<Test>> r2 = a2;
  }
}

In the first example with a1, you can see the valid references we can form, first generalizing the value type, and then generating the container's type (the "spine", when talking about a sequence). The second example (a2) shows how starting with a value type of Iterable allows the reference type you'd like to form without trouble.

Your question boils down to why valueTypeRef can't be of type ArrayList<Iterable<Test>>, and why we need to use an upper-bounded wildcard instead. In Java, type ArrayList<ArrayList<Test>> has no relationship with type ArrayList<Iterable<Test>>, even though ArrayList<Test>> is a subtype of Iterable<Test>. Forming the valueTypeRef looks for this would-be relationship for its implicit cast, but no such relationship exists, even if you as the programmer can see that it should exist.

The only way that Java allows you to take advantage of this subtype relationship is with wildcards, as explained here in Wildcards and Subtyping in The Java Tutorial. We need to introduce an upper-bounded wildcard (here, ArrayList<? extends Iterable<Test>>) to tell the type system that we expect our new reference's value type to be a subtype of its referent's value type.

Type parameters without a wildcard are neither covariant nor contravariant; even if function parameters and return types allow the normal substitutions along subtype and supertype axes, the generic types themselves (e.g. ArrayList<ArrayList<Test>> and ArrayList<Iterable<Test>>) can only participate in these substitutions with wildcards.

The resulting type (again, ArrayList<? extends Iterable<Test>>) precludes use of any mutating functions that would insert some value into the list that's indeed an Iterable<Test> but not an ArrayList<Test>. The resulting reference type is covariant with its referent, meaning loosely that it's safe to read through, but not safe to write through.

Answer 4

Bad solution

If anyone is interested, here is how I had solved my problem. But this is a workaround, that doesn't explain why the first snippet didn't work:

import java.util.Iterator;
import java.util.ArrayList;

public class Test {
  public Test() {
    ArrayList<ArrayList<Test>> arr = new ArrayList();
    Iterable<Iterable<Test>> casted = (Iterable<Iterable<Test>>)(Iterable<?>)arr;
  }
}

This is an unsafe operation. In this case, no harm will be made because Iterable are read-only, but this method allows you to cast an ArrayList<ArrayList> to an ArrayList<LinkedList> for instance, and thus it can break arr.

Good solution

There is no good solution to cast an ArrayList<ArrayList> to an Iterable<Iterable>, for the reason explained above. But you can safely (and implicitly) cast an ArrayList<ArrayList> to an Iterable<? extends Iterable>, and work on your variables of type Iterable<? extends Iterable> as you would have on an Iterable<Iterable>.

And you can implicitly an Iterable<Iterable> is an Iterable<? extends Iterable>.