Bug Patterns In Java - The Fictitious Implementation - Online Article

Overview

When an interface implementation doesn't satisfy all necessary invariants, you may have encountered the difficult-to-diagnose Fictitious Implementation bug pattern. We look at a double threat prevention method—assertions and unit tests.

Java interfaces are a great tool—they provide many of the advantages of multiple inheritance without all of the problems. By specifying an interface for all the services that a client expects to use, you make it possible to plug in various implementations of that interface as necessary.

Unfortunately, the only parts of an interface specification that can be expressed in code are method signatures. There may very well be other invariants that are expected to hold for any implementation, but the Java language provides no facility to check them. When an implementation of an interface fails to satisfy some of these unchecked invariants, we have an instance of the Fictitious Implementation bug pattern.

We can summarize this bug pattern as follows:

  • Pattern: Fictitious Implementation.
  • Symptoms: A client class that works with a specified interface breaks when a certain implementation of that interface is used.
  • Cause: The interface includes many intended invariants that aren't satisfied by the implementation.
  • Cures and Preventions: Fix the implementation to include those invariants. Make the invariants explicit in the documentation of the interface, if they aren't already.

About This Bug Pattern

Because Java checks only type signatures of interface implementations, it is possible to "implement" an interface without actually meeting its intended semantics. For example, consider the following interface for stacks:

An Interface for Stacks

public interface Stack
{
public Object pop();
public void push(Object top);
public boolean isEmpty();
}

Any class containing methods that match the above signatures would, from the perspective of the Java type checker, serve as a legal implementation of a Stack. But in practice there are several additional requirements we would expect a stack to fulfill. For instance:

  • If an object o is pushed on a stack s, and the next operation performed on the stack is pop, then the return value of that operation should be o.

  • If, for a given stack s, the return value of s.isEmpty() is true, and the next operation performed on the stack is pop, then that call to pop should throw a RuntimeException.

There are lots of other invariants we could specify, such as:

  • How do we expect a stack to handle multiple push operations?

  • What behavior do we expect with multiple threads?

It is difficult to enforce invariants such as these programmatically. We could (and should) mention them in the documentation, but a developer writing an implementation could easily ignore them. If that happens, then a client that relies on such invariants will not work with the implementation, and we'll have a bug.

I call bugs of this pattern Fictitious Implementations because I place the blame for them squarely on the implementation rather than on the client. Like any bug that deserves its own pattern, a Fictitious Implementation may not be immediately apparent, but can lurk hidden until some uncommon execution path uncovers it.

The Symptoms

A client class that works with a specified interface breaks when a certain implementation of that interface is used.

The Cause

The interface includes many intended invariants that aren't satisfied by the implementation.

Detecting Fictitious Implementations

The main problem with Fictitious Implementations is, of course, that they will pass compilation without incident. At runtime, the symptoms will often seem puzzling because the extra invariants that a programmer expects an interface to satisfy are often left unspoken—in fact, the programmer may not even be consciously aware that he is expecting them to be satisfied.

The process of correcting a bug often starts with a period of confusion. The programmer, tripped up by the Fictitious Implementation pattern, may at first try to convince himself that the problem he has observed cannot possibly have occurred.

If you find yourself in this situation, it's a good time to check your premises:

  • What hidden assumptions have you not stated?
  • How can you test these assumptions to thoroughly eliminate the possibility that they are faulty?

If you rely on an interface to another part of the system, and the implementation of that interface has been modified since the last release, then you might be running up against a Fictitious Implementation.

Cures and Preventions

Now let's examine various methods and techniques to fix and prevent this problem.

Some Ideas for Cures

In cases such as these, it is important that the maintainer of the interface document any invariants that may be assumed by a client programmer. If a client programmer discovers that an invariant he was relying on was not, in fact, documented, then the client programmer and the maintainer of the interface should sit down and discuss whether that invariant should be made explicit. Often, it will be easy to add an assumed invariant to the specification, saving the client programmer the trouble of modifying all the code that relied on it.

If the maintainer of the interface is not available, then the client programmer cannot rely on anything but the interface's documented invariants. If these are scant, then the interface is much less valuable than it could be. If the client programmer chooses to rely on undocumented invariants, the client code he writes can quickly lose value, since it may be incompatible with future releases of the interface implementation.

Tip

Client code that relies on undocumented interface invariants can quickly lose value since it may be incompatible with future releases of the interface implementation.

Two Prevention Concepts

If you're designing an interface, you have two very powerful tools to prevent bugs of this pattern: assertions and unit tests. Let's discuss how these technologies can be used as a sort of executable documentation to aid in enforcing interface invariants.

Assertions

The addition of assertions to a program is an old but good technique that is underused. The idea is to put in boolean checks for certain conditions at various stages in the execution of the program. According to the idea of design by contract.

Usually, assertions come in one of three varieties:

  • A precondition checks that some condition holds just before entering a code block.
  • A postcondition checks that some condition holds when exiting a code block.
  • An invariant checks that some condition holds during the execution of a code block.

Because of their expense, assertions of the last category are rarely supported in their most general form. Instead, the programmer is allowed to check that various conditions hold before and after the code block's execution.

In the case of interface specifications in which no implementation code is given, the first two categories are most useful.

With the introduction of Java-based preprocessors such as iContract, it is possible to place assertions into your source code and have them automatically converted into Java code that checks to ensure that the assertions are never violated. Unfortunately, iContract (and similar tools) do not catch all of the errors that can occur when using assertions in the context of an object-oriented language. In particular, iContract does not ensure that assertions in a class maintain the appropriate relationship with assertions in a superclass. This limitation often results in uninformative error messages during assertion violations. Although the theory behind the complete set of checks to perform is well understood, no production tools yet perform all of these checks correctly for Java. So, right now, we have no choice but to make do with iContract. See the Resources chapter for more information on this issue.

Leaving Assertions in Production Code

Because the assertions processed by iContract are specified as Javadoc comments in the original file, it is easy to compile this file without running the iContract preprocessor in order to make a "production" copy of the code in which none of the assertions are checked. But assertions are removed in this way too often.

In all but the most performance-critical sections of a program, the overhead of assertion checking will not be significant. By leaving in assertions, you make it easier to diagnose bug reports from end users (and there will be bug reports).

In our stack example, we could add an assertion to pop that ensures that it is never called on an empty stack:

An Assertion to Test a Stack's Interface

public interface Stack
{
/** *@pre ! this.isEmpty() */
public Object pop();
public void push(Object top);
public boolean isEmpty();
}

Adding assertions such as these to interface code can help ensure that such additional invariants hold when the methods of an implementation are called. Because the assertions can be compiled into the code, they are a powerful way to quickly diagnose the occurrence of fictitious implementations. What's more, they serve as added documentation for the interface.

But, because they are strictly functional boolean expressions, assertions are limited in their expressiveness. How would we encode our first rule for stacks into an assertion, for instance?

Like types, assertions are not expressive enough by themselves to capture all of the rules we may want to specify on an interface. For this reason, they are best used in tandem with unit tests.

Unit Tests

As discussed in Chapters 2 through 5, unit tests form a very precise form of documentation. Documentation in the form of unit tests also has the advantage of being executable. Using a unit testing framework such as JUnit (see Resources), you can easily check that such unit tests hold for any implementation of an interface.

Note

Unit tests are a precise form of documentation, documentation that has the added advantage of being executable.

The extent to which unit testing can aid in eliminating occurrences of fictitious implementations cannot be overemphasized. In fact, unit tests are an excellent way to provide limited specification of these extra invariants. An interface that comes with an accompanying set of unit tests gives the implementer a means to check that the extra invariants of the interface are satisfied.

I highly recommend providing such tests with any interface that will be used by outside clients. They'll thank you for it. Even in-house interfaces will be much easier to implement with an accompanying test suite.

Of course, unlike type declarations, a finite set of tests cannot check an implementation over all possible inputs. But unit tests can be thorough enough that we can reasonably expect them to catch most violations of the invariants. And they are, of course, much more expressive than type signatures.

When documenting an interface with unit tests, you can be much more precise in describing invariants than you can be in prose. For example, consider the following tests to check invariants on stacks:

Unit Tests for Stacks

public void testPushAndPop()
{
Stack s = new MyStack();
Object o = new Object();
s.push(o);
assertTrue(o == s.pop());
}
public void testPopOnEmpty()
{
Stack s = new MyStack();
assertTrue(s.isEmpty());
try
{
s.pop();
}
catch (RuntimeException e)
{
return;
}
throw new RuntimeException("pop on empty stack does not fail");
}

Compare these tests to the invariants for stacks as we originally specified them in English. Unlike the unit tests, those English descriptions leave many things open for interpretation. For example, when the first rule states that "the return value of that operation will be o," does this mean that the return value will satisfy an equals test with the pushed object or that it will actually satisfy ==? The unit test makes this very clear.

A few more things to notice about these tests:

  • They are small and straightforward. Because the unit tests for an interface should also serve as documentation, it is essential that they be as easy to read as possible.
  • Because they can be arbitrary Java code, they allow us to test complex behaviors of an implementation. For example, notice that the second method actually tests that an exception is thrown when it should be; if the exception isn't thrown, the test fails!

The fact that unit tests are so expressive certainly has advantages. It allows us to capture the essence of any rule for an interface that we would want to specify. But this expressiveness also has a disadvantage—we can specify examples of a rule, but, as noted, we can't use unit tests to check that a rule holds for all possible inputs to a program.

Combining the Fixes

We can now consider the three languages for the specification of an interface—the unit-testing language, the assertion language, and the type system—to form a hierarchy of expressiveness. Each step up in the hierarchy is achieved at the expense of a decrease in the testability of the language.

This hierarchy captures the common and fundamental tension between expressiveness and testability. By incorporating several such specification languages for our interfaces, it is possible to get the best of both worlds.

As these examples have shown, assertions and unit tests are powerful ways to avoid Fictitious Implementations, providing checkable specifications for an interface. What's more, the kinds of invariants that they check are complementary. Ideally, an interface would include both.

Notice that the inclusion of such specifications doesn't just catch errors in completed implementations; it actually helps the would-be implementer to ensure that he is correctly implementing the interface while he is programming. Not only can this improve productivity, but it can also make for happier programmers. It's always nice to send your code through an automated checking tool—and watch it pass.

What We've Learned

In this article on the Fictitious Implementation bug pattern we've learned the following:

  • Specifying an interface for all the services that a client expects to use makes it possible to plug in various implementations of that interface as necessary.
  • The only parts of a specification that can be checked statically are method signatures.
  • When an implementation of an interface fails to satisfy some necessary invariants, we have an instance of the Fictitious Implementation bug pattern.
  • Fictitious Implementations may not be immediately apparent, but can lurk hidden until some uncommon execution path uncovers them. They may pass compilation without incident.
  • Because Java checks only the type signatures of interface implementations, it is possible to "implement" an interface without actually meeting its intended semantics.
  • A disadvantage: many invariants we would like to specify cannot be checked statically.
  • The addition of assertions—boolean checks for certain conditions at various stages in the execution of a program—is a potential method for preventing Fictitious Implementations. Because they can be compiled into the code, assertions are a fast and powerful diagnostic tool.
  • Assertions should be included in the agreement the implementation of an interface makes with outside clients.
  • The three kinds of assertions are: A invariant that checks that some condition holds during the execution of a code block. (Invariants are rarely supported in the general form due to expense.)
  • In all but the most performance-critical sections of a program, the overhead of assertion checking will not be significant. Leaving assertions in makes it easier to diagnose bug reports from users.
  • Like types, assertions are not expressive enough by themselves to capture all of the rules we may want to specify on an interface. For this reason, they are best used in tandem with unit tests.
  • Unit tests provide limited specification of extra invariants as a means for an implementer to check that the extra invariants of an interface are satisfied.
  • Unlike type declarations, unit tests cannot check an implementation over all possible inputs.
  • Unit tests should be small, straightforward, and easy to read. Because they can be arbitrary Java code, they allow us to test complex behaviors of an implementation.
  • It is important that the maintainer of the interface document any invariants that may be assumed by a client programmer.
  • Client code that relies on undocumented invariants can quickly lose value since it may be incompatible with future releases of the interface implementation.

About the Author:

No further information.




Comments

No comment yet. Be the first to post a comment.