Common Design Mistakes, Part I

I’m writing this column on the balcony of my hotel room in Kona, Hawai’i. I’m here for the ISO C++ standards meeting, which began last Wednesday and runs through Tuesday. We have the weekend off, of course, and many of us spent part of the day yesterday watching the Ironman Triathlon. That’s a 2.5 mile ocean swim followed by a 112 mile bicycle ride followed by a 26.4 mile run. The race started at 7:00 AM, and the winner finished in about eight hours, at around 3:00 PM. Stragglers finished as late as midnight. The hotel is about three miles from the turnaround point where the participants changed over from bicycling to running, so we’d see someone go by in one direction on a bicycle, and half an hour later we’d see them go by in the other direction on foot. As bicyclists they looked pretty strong -- they were feeling the psychological lift of being near the end of that leg of the race. When they came back as runners they more clearly showed the debilitation and, in some cases, the exhaustion that was beginning to overcome them after so many hours of continuous exertion. Although I have doubts about the wisdom of people who put themselves through such torture, I admire their endurance and their willpower.

In our work as programmers we sometimes have to rely on our endurance and willpower to get through a difficult task, and we are justly proud when we successfully finish something that raised a new challenge each time we thought we had the problems all solved. It’s easy to forget, though, in the heat of a late-night debugging session, that our goal is not to demonstrate our proficiency at debugging, but to produce working code. Unlike Rosie Ruiz, who won the Boston Marathon several years ago by skipping part of the run and taking the subway instead, we won’t be disqualified for finding a better way to get to the finish line.

Often the biggest obstacle to our success in a programming task is that we don’t understand what we’re doing. There’s no easy solution here -- we have to learn more about our task. Sometimes, though, the biggest obstacle is that we made a bad design decision early on, and the solution is to change that design decision. That may mean throwing out code that we’ve sweated over, and that can make it harder for us to accept that we made a mistake. But part of being a professional programmer is recognizing that we make mistakes, correcting those mistakes, and learning from them.

This month we’ll look at half a dozen examples of design mistakes, seeing how these mistakes affect programmers who have to work with these flawed designs, and seeing how to fix them. These examples are all taken from the Java standard libraries, but they are not peculiar to Java. Java is fertile ground for design mistakes because Sun is in too much of a hurry to push out new versions. That makes it easy to find the sort of mistakes that hurried programmers often make. But don’t make the mistake of thinking that these things occur only in Java. I’ve chosen these examples because they are typical of the sort of design mistakes that we all have to be careful not to make.

Inheriting Instead of Delegating

The Java standard library has a class, java.util.Date, that encapsulates both a calendar date and the time of day. In itself that’s fine -- we often work with both of these together, and the Date class, in conjunction with the Calendar class, allows setting and extracting the various components of a calendar date and the time of day.

The Java Database Connectivity library (JDBC) provides a set of abstractions for dealing with databases through the standard Structured Query Language (SQL). SQL has two distinct data types, DATE and TIME, for describing a calendar date and a time of day. So JDBC provides corresponding classes, java.sql.Date and java.sql.Time, to encapsulate a calendar date and a time of day for use with SQL. One obvious problem here is the reuse of the name Date. Code that uses both java.util.Date and java.sql.Date will have to use fully qualified names so that the compiler can tell which is which. But that’s not the biggest problem that these classes present.

The real problem with java.sql.Date and java.sql.Time is that they are both derived from java.util.Date, and throw exceptions if you call methods that are not appropriate for the particular derived type. Here’s an abbreviated definition of java.util.Date:


package java.util;
public class Date
{
public Date(long time)
    { /* ... */ }
public int getHours()
    { /* ... */ }
public int getYear()
    { /* ... */ }
}

And here’s an abbreviated definition of java.sql.Date:


package java.sql;
public class Date
    extends java.util.Date
{
public Date(long time)
    { super(time); }
public int getHours()
    { throw new IllegalArgumentException(); }
}

The danger with classes like this is that methods that take arguments of the base type will typically not be written so that they can safely deal with objects of the derived type. For example:


public class DateDemo
{
static void showHour(java.util.Date date)
    {
    System.out.println(date.getHours());
    }
static void main(String args[])
    {
    long time = System.currentTimeMillis();
    showHour(new java.util.Date(time));
    showHour(new java.sql.Date(time));
    }
}

The first call to showHour works as expected: it displays the hour of the time when the program is run. The second call aborts program execution with an exception, thrown by the function java.sql.Date.getHours, because java.sql.Date does not support extracting an hour.

This creates a problem because one of the fundamental principles for designing inheritance hierarchies is that you ought to be able to supply a derived class¹ in any place where a base class is expected and still have a working program. This is known as the "Liskov substitution principle," and it is a handy guide for deciding whether inheritance is appropriate. In this case, java.sql.Date does not do everything that java.util.Date does, so it should not be derived from java.util.Date. This appears to be a case where the designer used inheritance because it saved having to write half a dozen functions. That convenience comes at a high price, though: it prevents the compiler from detecting that an object of type java.sql.Date is being passed to a function that will call illegal methods on it. Rather than expose users to this danger, the class should have been written to use an object of type java.util.Date as its implementation, but have its own distinct interface:


package java.sql;
public class Date
{
public Date(long time)
    { date = new Date(time); }
public int getYear()
    { return date.getYear(); }
private java.util.Date date;
}

With this definition, the runtime error in the example program above becomes a compile- time error, making it much easier to find.

If you find yourself tempted to write a derived class that doesn’t support all of the operations of its base, you should probably delegate to an object of that base type instead.

Factoring Bases Badly

The class java.io.Reader is a base class for character-oriented input streams. It has two methods, mark and reset, that can be used to mark the current position in a stream and to return to that position later. Derived classes, however, are not required to support mark and reset -- they can throw an exception if either of these methods is called. The class does give you a little help, though: there’s also a method, markSupported, which will tell you whether you can call mark and reset. If you religiously call markSupported before trying to call mark or reset on an object whose type is derived from Reader you can avoid exceptions. If you’re writing a method that needs to be able to mark a position and return to it, though, that doesn’t help much. Your method can’t do its job, and there’s nothing you can do about it. For example:


public class ReaderDemo
{
static boolean maybeRead(Reader r)
    {
    if (!r.markSupported())
        return false;
    // code that relies on mark and reset
    return true;
    }
}

Here we’ve used the return value to indicate whether the method was able to perform any processing, rather than letting mark or reset throw an exception. That doesn’t really accomplish anything, though: if the programmer who wrote the function that called maybeRead didn’t know that it required a Reader that supported mark and reset, why would he check the return value for success?

Just as in our previous example, we face the possibility of calling a method with an object that does not support all of the methods that its type indicates it should. This, too, violates the Liskov substitution principle, but the violation here is the result of a decision by the designer of the base class rather than the designer of the derived class. The solution is to recognize that there are really two different classes here, one that simply performs input from streams, and one that also provides mark and reset. By writing two classes instead of one we eliminate the problem:


public class Reader
{
// various methods for reading
}

public class ReaderM
    extends Reader
{
public void mark()
    { /* ... */ }
public void reset()
    { /* ... */ }
}

Classes that support mark and reset should be derived from ReaderM. Classes that do not support them should be derived from Reader.

With these definitions of Reader and ReaderM, we can rewrite our example code like this:


public class ReaderDemo
{
static void maybeRead(ReaderM r)
    {
    // code that relies on mark and reset
    }
}

Now we don’t have to test whether mark and reset are supported. The compiler won’t let us call maybeRead with a class that doesn’t support them.

If you find yourself tempted to write a base class with optional methods, you should probably write two base classes instead.

Overburdening a Class

The class java.util.TimeZone is an abstract class for dealing with a time zone. The derived class java.util.SimpleTimeZone was originally written to support the form of time zone used throughout the United States, namely, time zones where daylight savings time begins and ends on some particular day of the week in some particular week of some particular month. For example, in the U.S., daylight savings time begins on the first Sunday in April. In addition, it supports time zones which do not have daylight savings time. In order to do this it has two flavors of constructor, one that takes no information about daylight savings time and one that takes arguments to specify the month, week, and day of the week when daylight savings time begins and ends. For example, the following code produces a time zone object for Eastern Time:


import java.util;

public class TZDemo
{
public static void main(String args[])
    {
    TimeZone tz =
        new SimpleTimeZone(
            -5*60*60*1000L, // offset in milliseconds
            "EST",          // name

            Calendar.APRIL, // start month
            1,              // first week
            Calendar.SUNDAY,    // Sunday
            2*60*60*1000L,  // starting time in ms.
                            // (2 AM)

            Calendar.OCTOBER,   // end month
            -1,         // last week
            Calendar.SUNDAY,    // Sunday
            2*60*60*1000L)  // ending time in ms.
                            // (2 AM)
    }
}

This creates an object of type SimpleTimeZone, with a time that’s ordinarily five hours ahead of GMT, and daylight savings time starting on the first Sunday of April and ending on the last Sunday of October, at 2:00 AM.

There’s a problem with this approach, though: there are time zones in the world that don’t follow either of the two schemes supported by this version of SimpleTimeZone. Some use fixed dates for the start and end, and some use a particular day of the week following some fixed date. So beginning with JDK 1.2, SimpleTimeZone became much less simple. Now if the day of the week (Calendar.SUNDAY in both the start and end dates above) is zero, then the month and date don’t specify which week in the month, but which date in the month. If the day of the week is negative then its absolute value specifies the day of the week following the date given by the month and day. If you have trouble following that, you see why it’s a design mistake. This constructor is being asked to do too many things. It would have been much better to have added a new class, say, FixedDateTimeZone, to handle these forms of rules.

If you find yourself tempted to use magic flags to change the interpretation of arguments to a function, think about writing a separate function or perhaps a separate class.

Exposing Implementation Details

An object of the class java.io.PipedInputStream can be used to read data written to an object of the class java.io.PipedOutputStream. Most of the work is done in PipedInputStream. It contains a buffer that holds characters that have been written into the pipe but not yet read. The buffer is a circular buffer, that is, the index of the current write position is incremented each time a character is written, until it reaches the end of the buffer, and then it is wrapped around to point to the beginning of the buffer. Similarly, the index of the current read position is incremented each time a character is read, until it reaches the end of the buffer, and then it is wrapped around to point to the beginning of the buffer. As long as the read and write indexes have different values, the characters from the read index up to the write index are characters that have been written into the buffer but not yet read.

The major design decision in implementing a circular buffer is deciding how to indicate that the buffer is empty and how to indicate that it is full. There are two possible approaches. In the first, the buffer is empty when the read index and the write index are equal, and it is full when the write index is just before the read index. In the second, the buffer is empty when the read index holds an illegal value, and full when the read index and the write index are equal. With the first approach, the read and write methods look like this:


public int read()
    {
    if (readIndex == writeIndex)
        {
        // buffer empty, block until
        // someone writes to the buffer
        }
    int val = buffer[readIndex++];
    if (readIndex == bufSize)
        readIndex = 0;
    return val;
    }

    public void write(int val)
    {
    if ((writeIndex == bufSize-1 && readIndex == 0)
        || writeIndex == readIndex-1)
        {
        // buffer full, block until
        // someone reads from the buffer
        }
    buffer[writeIndex++] = val;
    if (writeIndex == bufSize)
        writeIndex = 0;
    }

With the second approach, they look like this:


public int read()
    {
    if (readIndex == -1)
        {
        // buffer empty, block until
        // someone writes to the buffer
        }
    int val = buffer[readIndex++];
    if (readIndex == bufSize)
        readIndex = 0;
    return val;
    }

    public void write(int val)
    {
    if (writeIndex == readIndex)
        {
        // buffer full, block until
        // someone reads from the buffer
        }
    else if (readIndex == -1)
        {
        readIndex = 0;
        writeIndex = 0;
        }
    buffer[writeIndex++] = val;
    if (writeIndex == bufSize)
        writeIndex = 0;
    }

The two read methods are pretty much the same. They differ only in the test that’s used to determine whether there is data in the buffer waiting to be read. The two write methods have less in common. The test for a full buffer in the first version is more complex. The second version modifies the value of the read index in the course of writing to an empty buffer. Now, personally, I find it disturbing for the write method to have to change the value of the read index. For that reason, I’d choose the first approach. However, there’s a cost associated with that approach: when the buffer is full there is actually one character position in the buffer that isn’t used. So I wouldn’t argue too strenuously with someone who chose the second approach, choosing more complex code over a small amount of wasted space. There’s a legitimate engineering choice to be made there.

In the Java library, though, there’s no choice allowed. The specification for java.io.PipedInputStream includes two protected integer values named in and out, indicating the current read position and write position. The specification also says that in has a value that is less than 0 when the buffer is empty, and that in and out are equal when the buffer is full. That is, the Java library specification requires the second approach. The only possible reason for doing that is to permit derived classes to modify the contents of the buffer, but that can’t be done safely because such changes can’t be properly synchronized with reads and writes by other threads. Exposing these internal data members imposes a particular algorithm on the implementer of this class.

If you find yourself tempted to make data members protected, ask yourself whether there is anything sensible that derived classes could do with that data, and if there isn’t a clear and compelling need to make them available, don’t.

Underestimating the Costs of Thread Safety

One of the interesting features of Java is its emphasis on thread safety. In the early versions most classes were thread safe, either because, like String, objects of those types could not be modified once created, or because, like StringBuffer, all of their methods were synchronized^2,3. The biggest problem with this approach is that it imposes the costs of thread safety on every object in every program, whether those costs are necessary or not.

For example, the class java.util.BitSet stores a sequence of bits, which can be accessed through an index and individually set, cleared, and queried. The decision to use a BitSet rather than an array of boolean values involves a tradeoff between speed and space: packing and unpacking the bits in a BitSet takes time, but makes it possible to use a great deal less space when storing a collection of bits. Most application designers understand that tradeoff well enough to make a reasonable choice.

Imposing synchronization on all BitSet objects shifts the balance, though, by making them significantly slower, in some implementations by a factor of nearly thirty. If an application doesn’t share a BitSet object between threads this overhead is wasted, and a BitSet will usually be prohibitively slow. The decision to synchronize an object’s methods should be made by the application developer, not the library designer⁴.

If you find yourself tempted to add expensive features to your classes, think about ways to make using those features optional.

Underestimating the Complexity of Thread Safety

The class java.util.Vector encapsulates an array of objects, increasing the size of the array as necessary when objects are added. It provides a method named elements that returns an object of type Enumeration that lets you examine the contents of the Vector without having to access individual elements through an index. An object of type Enumeration provides two methods, hasMoreElements and nextElement, to support these operations. These are typically used by calling hasMoreElements to determine whether there are objects remaining in the Vector that haven’t been examined yet, and if so, calling nextElement to get the next object. Like this:


void showAll(Enumeration e)
    {
    while (e.hasMoreElements())
        System.out.println(e.nextElement());
    }

An Enumeration produced by a Vector tracks changes in the Vector. That is, if we had added an object to the underlying Vector object in the middle of our loop, that object would affect the behavior of the Enumeration object. If we add an object to a position that we haven’t yet visited with the Enumeration object, then that new object will show up when we reach its position in the Vector. If we add an object to a position that we’ve already visited with the Enumeration object, then we’ll see the Enumeration’s current object for a second time the next time through the loop. That’s all understandable if you think about how a Vector is represented internally. But it can cause problems.

The danger here is that if the Enumeration object was created from a Vector that is shared between threads, changes to the underlying Vector can disrupt our control loop in rather drastic ways. A thread switch can occur between the call to hasMoreElements and the call to nextElement, and the intervening thread can remove an object from the Vector. If e happens to be pointing to the last element in the Vector, removing an element leaves e with nothing to point to, and the call to nextElement will throw an exception instead of returning a valid object. This behavior is not obvious from looking at the loop itself, and it is not documented. Enumeration objects that refer to Vector objects are not thread-safe⁵.

When you’re programming in a multi-threaded environment, think carefully about the implications of threads for your data structures. Make sure you understand and document the ways in which threads can affect the behavior of your code.

Continuation

We’ll continue this next month. Aloha!