Java Generics Wildcard capture in a generic method

Question

I'm studying Java Generics and I'm reading the (very good) book by Naftalin and Wadler, and I got where he's talking about capturing the wildcard in a generic method like the implementation in Collections.reverse :

public static <T> void reverse(List<T> list){
    List<T> temp=new ArrayList<>(list);
    for(int i=0;i<list.size();i++)
        list.set(i,temp.get(list.size()-1-i));
}

he says that the method in the Collections class is implemented using a wildcard for simplicity:

public static void reverse(List<?> list){
    //code..
}

but using the first method body wouldn't work:

public static void reverse(List<?> list){
    List<Object> temp=new ArrayList<Object>(list);  //legal
    for(int i=0;i<list.size();i++)
        list.set(temp.get(list.size()-1-i));        //illegal
}

it doesn't work because it attempts to put a Object type element in a list whose type is unknown(?) and it could be everything extending Object (which is ..well,everything)

so calling the first method from the second should do the trick:

 public static void reverse1(List<?> list){
    reverse2(list);
 }

 public static <T> void reverse2(List<T> list){
    List<T> temp=new ArrayList<T>(list);
    for(int i=0;i<list.size();i++)
        list.set(i,temp.get(list.size()-1-i));
}

now,following what happens on method call,for example passing a

 List<String> myList  

1) List<String> myList is up-casted to a local variable String<?> list (String extending Object, which is the upper bound of the wildcard, makes List<String> subtype of List<?>)

2) list is now passed to reverse2() and the parameter T is inferred to be ? extends Object,now how could I use this as a parameter when I instantiate new ArrayList<T>() ??? this is something clearly illegal in Java code, so something else must be happening,please can youtell me what is it??

thanks

Luca

Answer 1

list is now passed to reverse2() and the parameter T is inferred to be ? extends Object, […].

When reverse2 is called, the wildcard is captured to a fresh type variable which is no longer a wildcard.* The type of T is inferred to be this captured type.

The type system ensures that we can only use this feature in a safe manner.

For example, suppose we had a method which accepted two lists:

static <T> void swap2(List<T> list1, List<T> list2) {
    List<T> temp = new ArrayList<>(list1);
    list1.clear();
    list1.addAll(list2);
    list2.clear();
    list2.addAll(temp);
}

If we tried to call this with wildcard captures:

static void swap(List<?> list1, List<?> list2) {
    swap2(list1, list2); // <- doesn't compile
}

This will fail to compile, because the compiler knows that it cannot deduce that list1 and list2 had the same type before they were passed to swap.

reverse2 is type-safe because it adds elements to the list which were originally in the list to begin with.

---

* Technical proof is 5.1.10 Capture Conversion:

If Ti is a wildcard type argument of the form ?, then Si is a fresh type variable […].

Answer 2

The T parameter in reverse2() isn't inferred to be ? extends Object, and no instantiation is performed using the wildcard, ?.

Inference would only occur in a method that calls reverse2(). For example, if you call Collections.emptyList(), what is the type parameter? In that example, it's unknown, but it can usually be inferred at the calling site:

List<String> empty = Collections.emptyList();

is inferred to be a call to Collections.<String>emptyList() (the explicit form).

In your case, T has no restriction, so any type is compatible. If the type variable were declared as T extends String, however, the wildcard ? would be too general to satisfy that restriction, and the call would be illegal.

---

ok, I got it,so what is it T then? I mean, what does T is inferred to be?

T is a type variable in reverse2(), and as I explained above, type inference happens in the caller, not the callee, so T isn't "inferred" to be anything.

Maybe what you mean is what type shows up in the compiled byte code? In this case, no variables of type T are declared; T is never used, and no type checking is done. So, consider the following contrived example:

final class Reverse {

  static <T extends String> void reverse(List<T> list) {
    List<T> tmp = new ArrayList<>(list);
    for (int i = 0; i < list.size(); ++i)
      list.set(i, tmp.get(list.size() - 1 - i));
  }

}

Now a client that calls that method:

final class Test {

  public static void main(String... argv) {
    List<String> list = Arrays.asList("A", "B", "C");
    Reverse.reverse(list);
    System.out.println(list);
  }

}

Compile these classes together and run Test, and you'll get [C, B, A], as expected. Now, without recompiling Test, change the signature of the reverse() method and recompile only the Reverse class:

static <T extends Integer> void reverse(List<T> list)

Re-running Test will produce the same result, not a failure!

Now change the implementation of the reverse() method, and again, recompile only the Reverse class:

static <T extends Integer> void reverse(List<T> list) {
  List<T> tmp = new ArrayList<>(list);
  for (int i = 0; i < list.size(); ++i) {
    T el = tmp.get(list.size() - 1 - i);
    list.set(i, el);
  }
}

This time, running Test will produce the failure you might have expected last time:

Exception in thread "main" java.lang.ClassCastException: java.lang.String cannot be cast to java.lang.Integer

That's because T was actually referenced now:

T el = tmp.get(list.size() - 1 - i);

Into this assignment the compiler will insert a cast to the upper bound of the type parameter, which in this case is Integer:

T el = (Integer) tmp.get(list.size() - 1 - i);

If the type T is unrestricted (its upper bound is Object) no cast is performed, since it could never fail.