The Cause

Consider the following (ugly) implementation of singly linked lists, which represents empty lists as lists containing the null pointer in all of their fields. Just to show how insidious bugs of this pattern can be, we've already introduced a bug in the following code. See if you can spot it.

Listing 9-1: A Dangling Composite in a Singly Linked Implementation of Lists

import java.util.NoSuchElementException; public class LinkedList { private Object first; private LinkedList rest; /** * Constructs an empty LinkedList. */ public LinkedList() { this.first = null; this.rest = null; } /** * Constructs a LinkedList containing only the given element. */ public LinkedList(Object _first) { this.first = _first; this.rest = null; } /** * Constructs a LinkedList consisting of the given Object followed by * all the elements in the given LinkedList. */ public LinkedList(Object _first, LinkedList _rest) { this.first = _first; this.rest = _rest; } }

This code is truly awful . Instead of defining a separate class for empty lists, it represents empty lists by putting a null pointer in both fields.

It may at first appear that representing empty lists in this way makes the code simpler. After all, we've saved the effort of having to define an extra class just for empty lists. But, as we will demonstrate , this simplicity is an illusion.

Let's define some getter and setter methods for this class.

Notice that the action taken by both of the getters depends on whether the list is empty. This is exactly the sort of if-then-else chain that a properly constructed class hierarchy prevents . Because of these chains, we are prevented from considering the behavior of these getters on a single type of list in isolation. Furthermore, if at some future date we needed a third type of list (an immutable list, say), we would have to go into every one of these methods and change the code.

By this measure, this LinkedList implementation (in Listings 9-1 and 9-2) fails miserably. In fact, as mentioned earlier, our LinkedList class already contains a subtle but devastating bug-did you spot it?

Listing 9-2: Defining getter and setter Methods for LinkedList

public Object getFirst() { if (! (this.isEmpty())) { return this.first; } else { throw new NoSuchElementException(); } } public LinkedList getRest() { if (! (this.isEmpty())) { return this.rest; } else { throw new NoSuchElementException(); } } public void addFirst(Object o) { LinkedList oldThis = (LinkedList)this.clone(); this.first = o; this.rest = oldThis; } public boolean isEmpty() { return this.first == null && this.rest == null; } public Object clone() { return new LinkedList(this.first, this.rest); }

Exactly what is our representation of empty lists? We said earlier that an empty list is a LinkedList containing a null pointer in both fields. The zero-argument constructor sets up just such an empty list. But notice that the single-argument constructor does not place an empty list into the rest field, as would be necessary to construct a list of one argument. Instead, it places the null pointer into that field.

Because a Dangling Composite confuses null pointers with placeholders for base cases, mistakes like this are very easy to make. To see how this bug can manifest itself as a NullPointerException , let's write an equals() method for our lists:

Listing 9-3: Writing an equals() Method for the Linked Lists

public boolean equals(Object that) { // If the objects are not of the same class, then they are not equal. // Reflection is used in case this method is called from an instance of a // subclass. if (this.getClass() != that.getClass()) { return false; } else { // that instanceof LinkedList LinkedList _that = (LinkedList)that; return (this.isEmpty() && _that.isEmpty())  ((this.getFirst().equals(_that.getFirst())) && (this.getRest().equals(_that.getRest()))); } }

First, a brief aside. The first thing that can go wrong with this equals() method is that we will get a NullPointerException if it is ever called on null . Now, that might be what you'd expect to happen; after all, null.equals(x) will signal an error for any x , so shouldn't x.equals(null) signal the same error in order to preserve symmetry? In fact, the API for equals() specifies that equals() should form an equivalence relation on all "reference values" ( implying symmetry). And the Java Language Specification is pretty clear on the fact that reference values include null .

But the plot thickens. As developerWorks reader Paul Lewis has pointed out in the "Diagnosing Java Code" discussion forum, Sun has declared that x.equals(null) should return false for any non-null x . But this is in direct conflict with that part of the spec indicating that equals() should form an equivalence relation! What are we to do? It's impossible to implement an inconsistent specification; so, in a very real sense, we can't eliminate all bugs from our equals() method. This is a great example of the strong interdependence between bugs and specifications.

After I discussed this issue with Corky, he decided to inform Sun of the inconsistency in the equals() specification. In conversation, Guy Steele of Sun Microsystems has acknowledged the problem, and has proposed fixing it in Java 1.4.2. The fix he proposes is to stipulate that equals() should form an equivalence relation only on non-null reference values, and will continue requiring that equals() return false for non-null x .

If it were possible to start over, it would be preferable to stipulate that equals() implements a true equivalence relation for all reference values. Clients should be responsible for checking that they're not passing in null pointers to equals() methods, just as they are responsible for not calling equals() on null pointers. However, given the tremendous amount of legacy Java codes currently in production use, Sun's planned conservative fix to the spec is well justified.

So let's try to rewrite our equals() method to match the planned specification of equals() in 1.4.2. The first thing we have to do to fix our method is put a test at the beginning:

Listing 9-4: Fixing the equals() Method with a Preemptive Test

// The semantics for equals specified in the Sun JDK 1.3 API require that // we return false for x.equals(null), x non-null. if (that == null) { return false; }

If control flows past this test, then, because neither this nor that is empty, the equals() method correctly expects that it can call getFirst() and getRest() on both of them without an error signal. But if either of these lists contains any part that was constructed using the bug-laden single-argument constructor, then the recursive call will eventually uncover a null pointer where an empty list should have been waiting. If the null pointer is encountered in this.getRest() , it will cause a NullPointerException .

But perhaps the worse case occurs when a null pointer is discovered in that.getRest() . Here, the method will simply return false as if nothing were wrong at all! Then we'd have to wait even longer for some subsequent error to be signaled before we had a clue that there was a problem.

One potential solution might be to simply represent empty lists directly as null pointers. However, this would be wholly inadequate, because it would then be impossible to remove the last element of a list or to insert an element into an empty list. Furthermore, it would make a .equals call on an empty list signal a NullPointerException .

On the other hand, the bug could be fixed by rewriting the single-argument constructor as follows :

Listing 9-5: A Fix That Rewrites the Single-Argument Constructor

public LinkedList(Object _first) { this.first = _first; this.rest = new LinkedList(); }

But, as is the case with most bug patterns, it is much better to prevent bugs of this kind rather than to fix them. The fact that the code broke so easily and that even simple getters , setters , and the equals() method were all so bloated, suggests that there is a better design.

Cures and Prevention

In fact, there is a simple way to avoid Dangling Composite bugs: give each base case of the data type its own class. Instead of implementing singly linked lists as we did earlier, implement such lists with a class LinkedList that contains a field holding either an Empty or a Cons class. These classes implement a common interface, as shown in Figure 9-1.

Figure 9-1: Classes implementing a common interface

To implement mutator() methods, the new LinkedList class serves as a container for an internal, immutable list, as shown in Listing 9-6. This approach is necessary because truly empty lists have no fields to mutate and are therefore immutable.

Listing 9-6: The LinkedList Class Acts as a Container for an Immutable List

import java.util.NoSuchElementException; public class LinkedList { private List value; /** * Constructs an empty LinkedList. */ public LinkedList() { this.value = new Empty(); } /** * Constructs a LinkedList containing only the given element. */ public LinkedList(Object _first) { this.value = new Cons(_first); } /** * Constructs a LinkedList consisting of the given Object followed by * all the elements in the given LinkedList. */ public LinkedList(Object _first, LinkedList _rest) { this.value = new Cons(_first, _rest.value); } private LinkedList(List _value) { this.value = _value; } public Object getFirst() { return this.value.getFirst(); } public LinkedList getRest() { return new LinkedList(this.value.getRest()); } public void addFirst(Object o) { this.value = new Cons(o, this.value); } public boolean isEmpty() { return this.value instanceof Empty; } public boolean equals(Object that) { // The semantics for equals specified in the Sun JDK 1.3 API require that // we return false for x.equals(null), x non-null. if (that == null) { return false; } if (this.getClass() != that.getClass()) { return false; } else { // that instanceof LinkedList return this.value.equals(((LinkedList)that).value); } } }

Implementation of the immutable lists is then straightforward, as shown in Listing 9-7.

Listing 9-7: Implementing the Immutable Lists

interface List {} class Empty implements List { public boolean equals(Object that) { return (that != null) && (this.getClass() == that.getClass()); } } class Cons implements List { Object first; List rest; Cons(Object _first) { this.first = _first; this.rest = new Empty(); } Cons(Object _first, List _rest) { this.first = _first; this.rest = _rest; } public Object getFirst() { return this.first; } public List getRest() { return this.rest; } public boolean equals(Object that) { // The semantics for equals specified in the Sun JDK 1.3 API require that // we return false for x.equals(null), x non-null. if (that == null) { return false; } if (this.getClass() != that.getClass()) { return false; } else { // that instanceof Cons Cons _that = (Cons)that; return (this.getFirst().equals(_that.getFirst())) && (this.getRest().equals(_that.getRest())); } } }