A Hazard of Covariant Return Types and Bridge Methods

This week at JavaOne, Joe Darcy pointed out to me an interesting difficulty he ran into recently when trying to change various JDK classes to use covariant return types for clone(). It turns out that changing the return type of an overridden method on a class to be more specific can break behavior compatibility for child classes which themselves had already created an override of the same method. The original discussion is on the OpenJdk Core Libs Dev mailing list. To try to make it a touch easier to follow, I'll give a bit of background, and construct a stand-alone example.

Method invocation in the JVM

The Java language (as most OO languages) offers some flexibility when making method calls. Given the following class^[1]:

import java.util.*;

public class Wrapper {
  public Collection wrap(Object o) {
    List l = new ArrayList();
    l.add(o);
    return l;
  }
}

public class WrapperClient {
  public static void main(String args[]) {
    Object wrappped = new Wrapper().wrap("x");
  }
}

This is the Liskov Substitution Principal in action. While wrap is expecting an Object, it's fine to pass in a subtype of Object (in this case, String). Similarly, while the return type of wrapped is of type Object, it's fine to assign a subtype of Object to it. As we know, Java respects this, and makes it work. What is not as well known is exactly how Java makes this work.

To see what is happening under the hood, we need to understand how method calls look in the Java Virtual Machine. Rather than show disassembled byte code the way javap -c would, I'll introduce a bit of pseudocode syntax. When a method is called, I'm going to add the precise signature of the method after the method name, in brackets. In this pseudo code, the above call to wrap now looks like:

Object wrapped = new Wrapper().wrap[Object->Collection]("x");

The JVM honors Liskov Substution, in the sense that it is perfectly willing to invoke wrap[Object->Collection], even thought the type being passed in is not Object, but a subtype of Object. Similarly, it's willing to assign the result of this method invocation (declared to be a Collection) to a variable of type Object, a supertype of Collection.

There's a subtle issue here which is easy to overlook. While the JVM honors Liskov Substution perfectly well when it comes to accepting subtypes of what a method call or assignment operator expects, it will not look for method signatures that would work in the place of the signature asked for. To see this in action, recompile Wrapper.java with the following source code:

public class Wrapper {
  public Collection wrap(String o) {
    Collection c = new ArrayList();
    c.add(o);
    return c;
  }
}

If WrapperClient is run again against the newly compiled Wrapper class without also recompiling WrapperClient.java, a NoSuchMethodError will be thrown. This is because Wrapper is looking for a method with signature wrap[Object->Collection], but the only wrap method present in Wrapper is wrap[String->Collection]. While this would be an acceptable substitution, the JVM will not make it for us.

Covariant returns and Bridge methods

Prior to Java 5, overrides of a method in a subclass could not change the return type of the method. If WrapperChild were to extend Wrapper, it would only have one option for the return type of wrapper, namely Collection:

import java.util.*;
public class WrapperChild extends Wrapper {
  @Override
  public Collection wrap(Object o) {
    return super.wrap(o);
  }
}

Starting in Java 5, support for covariant return types was introduced added. This means that we can now subclass WrapperChild, and override the wrap method to return a type more specific than Collection:

import java.util.*;
public class WrapperGrandchild extends WrapperChild {
  @Override
  public List wrap(Object o) {
    return (List) (super.wrap(o));
  }
}

import java.util.*;
public class WrapperGrandchild extends WrapperChild {
  public List wrap(Object o) {
    return (List) (super.wrap[Object->Collection](o));
  }

  // bridge method created by javac
  public Collection wrap(Object o) {
    return this.wrap[Object->List].wrap(o));
  }
}

Thus, a client which has an instance with declared type WrapperChild, but actual type WrapperGrandchild, can still successfully invoke WrapperGrandchild.wrap[Object->Collection].

The Trap

Now that we understand covariant overrides and bridge methods, we can understand the problem that Joe ran into. Suppose that while Wrapper and WrapperChild are distributed in the same jar, WrapperGrandchild is distributed in a separate jar which has a separate release schedule. Suppose further that the maintainer of WrapperChild decides to change the signature of its wrap method to return List instead of Collection. Because the original Wrapper class still is defining wrap to return Collection, WrapperChild.class must now contain a bridge method:

import java.util.*;
public class WrapperChild extends Wrapper {
  public List wrap(Object o) {
    return (List) (super.wrap[Object->Collection](o));
  }

  // bridge method created by javac
  public Collection wrap(Object o) {
    return this.wrap[Object->List].wrap(o));
  }
}

Suppose that WrapperGrandchild is not recompiled against the new version of WrapperChild. Consider what happens if someone calls:

new WrapperGrandchild().wrap("x")

The good news is that this is a rather obscure edge case that most of us won't hit in practice. It requires three levels of inheritance for a method, with each child invoking super. It also requires a very specific combination of covariant return types at each inheritance level, and a specifc sequence of releases. The danger remains, however, especially for environments with multiple layers of dependencies which evolve on different time lines, or for widely used libraries (such as the core JDK libraries).