Don't cast that class!

Unlike the dreaded null-pointer exception (which says nothing about what was expected to occur instead of the null pointer), a class-cast exception is relatively easy to debug.

A class-cast exception often occurs in a program that is performing a recursive descent over a data structure, usually when some part of the code is descending two levels per method call and is not dispatching appropriately on the second descent. Programmers can identify the problem by learning about the Double Descent bug pattern.

Back to top

The Double Descent bug pattern

This week's special is the Double Descent bug pattern. It manifests itself as a class-cast exception. It is caused by recursively descending a composite data structure in such a way that, sometimes, more than one step in the descent is taken in a single recursive call. Doing so often necessitates the addition of casts to get the code to compile. But, in such a descent, it is easy to forget to check that appropriate invariants are satisfied to guarantee that these casts will succeed.

Consider the following class hierarchy for binary trees of ints. Because we want to allow for empty trees, we will not put a value field into the Leaf class. Because this decision makes all Leaves identical, we'll keep a singleton for Leaf in a static field.

abstract class Tree {
}

class Leaf extends Tree {
  public static final Leaf ONLY = new Leaf();
}

class Branch extends Tree {

  public int value;
  public Tree left;
  public Tree right;

  public Branch(int _value, Tree _left, Tree _right) {
    this.value = _value;
    this.left = _left;
    this.right = _right;
  }
}

		

Now, suppose we want to add a method on Trees that determines whether any two consecutive nodes (such as a branch and one of its children) both contain 0 as their value. We might add the following methods (notice that the last method will not compile in its current form):

  // in class Tree:
  public abstract boolean hasConsecutiveZeros();


  // in class Leaf: 
  public boolean hasConsecutiveZeros() {
    return false;
  }


  // in class Branch:
  public boolean hasConsecutiveZeros() {

    boolean foundOnLeft = false;
    boolean foundOnRight = false;

    if (this.value == 0) {
      foundOnLeft = this.left.value == 0;
      foundOnRight = this.right.value == 0;
    }
    if (foundOnLeft || foundOnRight) {
      return true;
    }
    else {
      foundOnLeft = this.left.hasConsecutiveZeros();
      foundOnRight = this.right.hasConsecutiveZeros();
      return foundOnLeft || foundOnRight;
    }
  }
		

The method in class Branch will not compile because this.left and this.right are not guaranteed to have value fields.

That we cannot compile strongly suggests that there is a logical problem with our manipulation of these data structures. But suppose we ignore this warning and simply cast this.left and this.right to Branches in the appropriate if statement, as follows:

  public boolean hasConsecutiveZeros() {

    boolean foundOnLeft = false;
    boolean foundOnRight = false;

    if (this.value == 0) {
      foundOnLeft = ((Branch)this.left).value == 0;
      foundOnRight = ((Branch)this.right).value == 0;
    }
    if (foundOnLeft || foundOnRight) {
      return true;
    }
    else {
      foundOnLeft = this.left.hasConsecutiveZeros();
      foundOnRight = this.right.hasConsecutiveZeros();
      return foundOnLeft || foundOnRight;
    }
  }
		

Back to top

The symptoms

Now the code will compile. In fact, it will succeed on many test cases. But suppose we were to run this code on the tree shown in Figure 1, where the branches are represented as circles, with their values in the center, and the leaves are represented as squares. Calling hasConsecutiveZeros on this tree causes a class-cast exception.

Back to top

The cause

The problem occurs with the left branch. Because the value of that branch is 0, hasConsecutiveZeros casts its children to type Branch, which, of course, fails.

Back to top

Cures and prevention

The way to fix the above problem is the same as the way to prevent it. Before I discuss this fix, however, I should discuss one way not to fix it.

The quick but incorrect way to remedy the problem would be to eliminate the Leaf class and represent Leaf nodes simply by putting null pointers in the left and right fields of a Branch. This approach would eliminate the need to cast in the above code, but it would not fix the bug.

Instead, the error signaled at run time would be a null-pointer exception instead of a class-cast exception. Because null-pointer exceptions are more difficult to diagnose, this "fix" would actually decrease the quality of the code. For more discussion on this issue, see my article The Null Flag bug pattern.

So, how can we fix this bug? One way would be to wrap each cast in an instanceof check.

        if (! (this.left instanceof Leaf)) {  
	  // this.left instanceof Branch
	  foundOnLeft = ((Branch)this.left).value == 0;
	}
	if (! (this.right instanceof Leaf)) { 
	  // this.right instanceof Branch
	  foundOnRight = ((Branch)this.right).value == 0;
	}
		

By the way, notice the comments asserting what invariant we expect to hold in the body of each if statement. It's good practice to add comments like this in your code. It is an especially helpful practice for else clauses. Because there is rarely an explicit check on the invariants that are expected to be held in an else clause, it's a good idea to make that clear in your code.

Think of a cast as a kind of assertion and the invariants as arguments for why the assertion is true.

The disadvantage of using instanceof checks in this fashion is that, if we were to add another subclass of Tree (such as, a LeafWithValue class), we would have to revise these instanceof checks. For this reason, I try to avoid instanceof checks whenever possible.

Instead, I add extra methods to the subclasses that perform the appropriate action for each subclass. After all, the ability to add such polymorphic methods is one of the key advantages of an object-oriented language.

In the current example, we could do this by adding a valueIs method to the Tree class, as follows:

  // in class Tree:
  public abstract boolean valueIs(int n);

  // in class Leaf:
  public boolean valueIs(int n) { return false; }

  // in class Branch:
  public boolean valueIs(int n) {
    return value == n;
  }
 
  // in class Branch, method hasConsecutiveZeros
  if (this.valueIs(0)) {
    foundOnLeft = this.left.valueIs(0);
    foundOnRight = this.right.valueIs(0);
  }
		

Notice that I've added a valueIs method as opposed to a getValue method. If we had added a getValue method to class Leaf, we would either have to return some sort of flag value indicating that the method application is non-sensical or actually throw an exception.

Returning a flag value would have many of the same problems as the Null Flag bug pattern we discussed last time. Throwing an exception would not help in our case because we would then have to add instanceof checks in hasConsecutiveZeros to ensure that we didn't trigger the exception. And that is exactly what we are trying to avoid with the new method.

valueIs avoids all of these problems by encapsulating what we really want each class to handle separately: checking whether an instance of the class contains the given value.

Back to top

Wrapup

Here's the breakdown of this week's bug pattern:

• Pattern: Double Descent
• Symptoms: A program that performs a recursive descent over a data structure throws a class-cast exception.
• Cause: Some part of the code is descending two levels per method call without dispatching appropriately on the second descent.
• Cures and preventions: Factor the casting code out into separate methods for each class. Alternatively, examine the invariants to ensure that the casts will succeed.

In short, the moral to this story is to always convince yourself that the invariants inside a code block ensure that any casts in the block will always succeed. When each cast is held to this level of scrutiny, you may find yourself factoring out many of these casts by adding methods to the relevant subclasses.

In the next article, I will discuss bug patterns related to the mishandling of complex input data.

Resources

• Set-based analysis is one method that could automatically determine the possibility of many class-cast exceptions before the program is ever run. The Carnegie Mellon School of Computer Science Web site provides a short introduction to this approach, along with links to several technical publications on the topic.
  
  
• Visit the Patterns Home Page for a good introduction to design patterns and how they are used.
  
  
• Check out JUnit and catch more errors by making your code "test-infested."
  
  
• Read Eric's complete series on Diagnosing Java code.
  
  

About the author

Comments (Undergoing maintenance)

Back to top

Trademarks  |  My developerWorks terms and conditions

Table of contents

• Don't cast that class!
• The Double Descent bug pattern
• The symptoms
• The cause
• Cures and prevention
• Wrapup
• Resources
• About the author
• Comments

Next steps from IBM

Spring, JRuby, and Ajax development is easier with WebSphere Application Server - a smart Java 5 and J2EE Web services-based application server.

---

• Try: The no-charge WebSphere Application Server Community Edition is a pre-integrated, lightweight Java 5 application server built on Apache Tomcat and other best-of-breed open source software such as OpenEJB, Apache Axis, and Apache Derby.
• Article: The article leverage the Spring Framework and the WebSphere Application Server to improve your J2EE project productivity.
• Tutorial: See how the free WebSphere Application Server and XML can improve the efficiency of your JRuby on Rails and Ajax development.
• Buy: WebSphere Application Server - Express

My developerWorks community

Dig deeper into Java on developerWorks

Rate a product. Write a review.

Write a review for Rational products today!

Special offers