Why Is T Bounded by Object in the Collections.Max() Signature

Why is T bounded by Object in the Collections.max() signature?

The two have the same bounds but there is a subtle difference.

 <T extends Object & Comparable<? super T>> 

This will cause T to become an Object under erasure.

 <T extends Comparable<? super T>>

This will cause T to become Comparable under erasure.

---

In this case it is done because .max predates Java 5. We can see in this link Joachim kindly provided that the signature of .max in Java 1.4.2 is:

public static Object max(Collection coll)

Had we used <T extends Comparable<? super T>> as a bound, our signature would be

public static Comparable max(Collection coll)

Which would break the APIs. I've managed to find this page that discusses converting old APIs to generic ones and it gives .max as a specific example.

Here they explain why max is defined this way:

You also need to ensure that the revised API retains binary compatibility with old clients. This implies that the erasure of the API must be the same as the original, ungenerified API. In most cases, this falls out naturally, but there are some subtle cases. We'll examine one of the subtlest cases we've encountered, the method Collections.max(). As we saw in section More Fun with Wildcards, a plausible signature for max() is:

public static <T extends Comparable<? super T>> T max(Collection<T> coll) This is fine, except that the erasure of this signature is: public static Comparable max(Collection coll) which is different than the original signature of max(): public static Object max(Collection coll)

One could certainly have specified this signature for max(), but it was not done, and all the old binary class files that call Collections.max() depend on a signature that returns Object.

Why do we need bounded wilcard ? extends T in Collections.max() method

The difference is in the type returned, especially influenced by inference, whereby the type may be a type hierarchically between the Comparable type and the List type. Let me give an example:

class Top {
}
class Middle extends Top implements Comparable<Top> {
    @Override
    public int compareTo(Top o) {
        // 
    }
}
class Bottom extends Middle {
}

Using the signature you've provided:

public static <T extends Comparable<? super T>> T max(List<? extends T> list)

we can code this without errors, warnings or (importantly) casts:

List<Bottom> list;
Middle max = max(list); // T inferred to be Middle

And if you need a Middle result, without inference, you can explicitly type the call to Middle:

 Comparable<Top> max = MyClass.<Middle>max(list); // No cast

or to pass to a method that accepts Middle (where inference won't work)

someGenericMethodThatExpectsGenericBoundedToMiddle(MyClass.<Middle>max(list));

---

I don't know if this helps, but to illustrate the types the compiler as allowed/inferred, the signature would look like this (not that this compiles, of course):

public static <Middle extends Comparable<Top>> Middle max(List<Bottom> list)

T extends Object & E vs T extends E

To preserve binary compatibility: It's completely described here. The second signature actually changes the return type of the method to Comparable and it loses the generality of returning an Object. The original signature preserves both.

Signature of Collections.min/max method

One benefit of the ? is that it prohibits additions of items to the Collection

Searching the maximal element in an array with generics

I assume there are two questions here:

• Why the bounds Object is required
• Why to use Comparable<? super T> instead of Comparable<T>.

For the first question, it is not really required to give explicit Object bounds, but it may depend upon how you want the erasure of your method look like. With explicit Object bound, your type parameter will be erased to Object, and without that, it will be erased to Comparable. Most of the time, you won't find any need to give explicit bound, but this may be required for API compatibility as already explained in this post.

As for second question, using Comparable<? super T> is often a good idea, if you want to pass a list to List<T>, where T is comparable. Why? Suppose you have a class:

class Employee implements Comparable<Employee> { }

and a subclass:

class PartTimeEmployee extends Employee { }

and you want to pass a List<PartTimeEmployee> to a List<T>. It might seem straight-forward, and easy not before you realise that your PartTimeEmployee doesn't really implement a Comparable<PartTimeEmployee> but a Comparable<Employee>. So, what you do is, change the bounds of T to:

T extends Comparable<? super T>

.. and then you can pass a List<PartTimeEmployee>, as it satisfies the bound now.

The reason why you've to do this is to do with, erasure (Again?). Yes. On first seeing that error, you might jump off your chair and quickly make PartTimeEmployee comparable too by doing this:

class PartTimeEmployee extends Employee implements Comparable<PartTimeEmployee>

...but hey, you're doing wrong there. Java generics doesn't allow you to implement or extend from two different parameterized instantiation of same generic type. You're saying that, PartTimeEmployee implement both Comparable<Employee> and Comparable<PartTimeEmployee>. With this, you would have two methods in your PartTimeEmployee:

compareTo(PartTimeEmployee)
compareTo(Employee)

and after erasure, both of them will become:

compareTo(Object)
compareTo(Object)

and you've duplicate methods now. That is why it's illegal.

However in this case, since you have a List<? extends T> as parameter type, I think you might well do with Comparable<T>, because then when you pass a List<PartTimeEmployee>, T will be inferred as Employee, and hence will satisfy the bound.

Oracle java generics tutorial

The only reason I can find to have <T extends Object & Comparable<? super T>, as opposed to T extends Comparable<? super T>, is for backwards compatibility when generifying a method.

According to Angelika Langer's Java Generics FAQ:

Occasionally, one must pay attention to the fact that a generification might change the signature of some methods in the byte code. Changing the signature will break existing code that cannot be recompiled and relies on the binary compatibility of the old and new version of the .class file.

In this case, Java's own Collections.max used to return Object before 1.5, the arrival of generics. When generified, this method could be declared without extends Object, and it would work correctly in isolation.

public static <T extends Comparable<? super T>> T max(Collection <? extends T> coll)

However, the erasure of this method, for bytecode purposes, has this method returning Comparable, instead of Object, which is a backwards incompatibility.

To resolve this, extends Object was inserted as the first bound, so that the erasure of the return type of this method would remain Object.

This resolved the backwards incompatibility issue for Java generics in 1.5.

However, the question in the tutorial stated:

Write a generic method to find the maximal element in the range [begin, end) of a list.

You are writing your own new method, so there is no backwards compatibility to maintain yet. The extends Object in the answer to this tutorial question is unnecessary.

In addition

In the bytecode (javap -c Algorithm.class), all types undergo type erasure, even the local variable maxElem.

  public static <T extends java.lang.Comparable<? super T>> T max(java.util.List<? extends T>, int, int);
Code:
   0: aload_0
   1: iload_1
   2: invokeinterface #2,  2            // InterfaceMethod java/util/List.get:(I)Ljava/lang/Object;

The get method has returned an Object. Then how does it invoke compareTo in Comparable?

   7: astore_3
   8: iinc          1, 1
  11: iload_1
  12: iload_2
  13: if_icmpge     49
  16: aload_3
  17: checkcast     #3                  // class java/lang/Comparable
  20: aload_0
  21: iload_1
  22: invokeinterface #2,  2            // InterfaceMethod java/util/List.get:(I)Ljava/lang/Object;
  27: invokeinterface #4,  2            // InterfaceMethod java/lang/Comparable.compareTo:(Ljava/lang/Object;)I

The compiler has inserted an implicit cast to Comparable so that the compareTo method can be called. It has asserted that the objects in the list are Comparable because of the second upper bound, Comparable<? super T>.

  32: ifge          43
  35: aload_0
  36: iload_1
  37: invokeinterface #2,  2            // InterfaceMethod java/util/List.get:(I)Ljava/lang/Object;
  42: astore_3
  43: iinc          1, 1
  46: goto          11
  49: aload_3
  50: areturn
}

Max element - Sun's answer VS mine

There are two separate generics questions here.

Why use an intersection type used?

That is, why does the solution use T extends Object & Comparable<T> instead of the more straightforward T extends Comparable<T>? (I've elided the wildcards in this section; I'll cover them below.)

I don't believe that Object & Comparable<T> is any different from Comparable<T> within the type system, since every object extends Object. That is, there is no type T that extends Comparable<T> that doesn't also extend Object & Comparable<T>.

There is a difference, though. An intersection type erases to the first component of the intersection, so T extends Object & Comparable<T> erases to Object whereas T extends Comparable<T> erases to Comparable. Consider two alternative declarations of the max method:

<T extends Comparable<T>> T max1(List<T> list) { ... }

<T extends Object & Comparable<T>> T max2(List<T> list) { ... }

If you dump the signatures of these methods using javap -s you can see the internal signatures showing the erased types:

<T extends java/lang/Comparable<T>> T max1(java.util.List<T>);
  Signature: (Ljava/util/List;)Ljava/lang/Comparable;

<T extends java/lang/Object & java/lang/Comparable<T>> T max2(java.util.List<T>);
  Signature: (Ljava/util/List;)Ljava/lang/Object;

Who cares about the erased type? The JVM does. The JVM finds methods based on matching the argument types and the return type. So the erased return type is potentially significant.

And in fact, it is significant from a binary compatibility standpoint. Prior to Java SE 5, when generics were introduced, the Collections.max method was declared and had the erased signature as follows:

public static Object max(Collection coll)
  Signature: (Ljava/util/Collection;)Ljava/lang/Object;

In Java SE 5 and later, the declaration and erased signature were:

public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll)
  Signature: (Ljava/util/Collection;)Ljava/lang/Object;

Crucially, the erased signature is the same.

If instead the Java SE 5 declaration weren't declared using an intersection type, it would look like this:

public static <T extends Comparable<? super T>> T max(Collection<? extends T> coll)
  Signature: (Ljava/util/Collection;)Ljava/lang/Comparable;

This would be a binary incompatibility. Binaries compiled against old versions of the JDK would refer to a version of max that returns Object. If run against a JDK with this alternate, incompatible declaration, the only version of max would return Comparable instead, resulting in a NoSuchMethodError being thrown at link time.

Thus, the use of <T extends Object & Comparable<T>> is really to control the erasure of this declaration, which is driven by binary compatibility considerations. The tutorial seems somewhat misleading on this point. The actual declaration of Collections.max in Java SE is this way for binary compatibility. But if you were declaring this method for the first time, I don't believe that it would be useful to use an intersection type this way.

Why are wildcards used in the declaration?

That is, instead of:

static <T extends Comparable<T>> T max(List<T> list)

why are wildcards used:

static <T extends Comparable<? super T>> T max(List<? extends T> list)

Here, wildcards are necessary for the method to be used more flexibly in the presence of subtyping. Consider the following:

class A implements Comparable<A> { ... }

class B extends A { }

List<B> bList = ...;
B bMax = max(bList);

If the non-wildcarded declaration were used, there would be no T that matches. In order to make this work, Comparable<? super T> is necessary. This allows T to be inferred as B and everything works.

I must admit that I haven't been able to find an example that shows why List<? extends T> is required in this case. This example works fine if the parameter is declared simply List<T>. It may be that List<? extends T> is used for documentation purposes, to indicate that elements are only retrieved from the list, and that the list is not modified. (For more information on this, see Bloch's Effective Java in the generics chapter where he discusses PECS -- "Producer Extends, Consumer Super"; or Naftalin and Wadler's Java Generics and Collections where they discuss the "Put and Get Principle".)

---

Links:

Why is T bound by Object in the Collections.max() signature?

Angelika Langer's FAQ entry

Java Generics: What is PECS?

Why do we need bounded wilcard in Collections.max() method

---

Related Topics