Example: DBC + white-box unit testing
The following example demonstrates the potency of combining concepts from Design by Contract with unit testing. It shows a small first-in, first-out (FIFO) queue class that is implemented as a “circular” array—that is, an array used in a circular fashion. When the end of the array is reached, the class wraps back around to the beginning.
We can make a number of contractual definitions for this queue:
- Precondition (for a put( )): Null elements are not allowed to be
added to the queue.
- Precondition (for a put( )): It is illegal to put elements into
a full queue.
- Precondition (for a get( )): It is illegal to try to get
elements from an empty queue.
- Postcondition (for a get( )): Null elements cannot be produced
from the array.
- Invariant: The region in the array that contains objects cannot contain any
null elements.
- Invariant: The region in the array that doesn’t contain objects must
have only null
values.
Here is one way you could implement these rules, using explicit method calls for each type of DBC element:
//: c15:Queue.java
// Demonstration of Design by Contract (DBC) combined
// with white-box unit testing.
// {Depends: junit.jar}
import junit.framework.*;
import java.util.*;
public class Queue {
private Object[] data;
private int
in = 0, // Next available storage space
out = 0; // Next gettable object
// Has it wrapped around the circular queue?
private boolean wrapped = false;
public static class
QueueException extends RuntimeException {
public QueueException(String why) { super(why); }
}
public Queue(int size) {
data = new Object[size];
assert invariant(); // Must be true after construction
}
public boolean empty() {
return !wrapped && in == out;
}
public boolean full() {
return wrapped && in == out;
}
public void put(Object item) {
precondition(item != null, "put() null item");
precondition(!full(), "put() into full Queue");
assert invariant();
data[in++] = item;
if(in >= data.length) {
in = 0;
wrapped = true;
}
assert invariant();
}
public Object get() {
precondition(!empty(), "get() from empty Queue");
assert invariant();
Object returnVal = data[out];
data[out] = null;
out++;
if(out >= data.length) {
out = 0;
wrapped = false;
}
assert postcondition(
returnVal != null, "Null item in Queue");
assert invariant();
return returnVal;
}
// Design-by-contract support methods:
private static void
precondition(boolean cond, String msg) {
if(!cond) throw new QueueException(msg);
}
private static boolean
postcondition(boolean cond, String msg) {
if(!cond) throw new QueueException(msg);
return true;
}
private boolean invariant() {
// Guarantee that no null values are in the
// region of 'data' that holds objects:
for(int i = out; i != in; i = (i + 1) % data.length)
if(data[i] == null)
throw new QueueException("null in queue");
// Guarantee that only null values are outside the
// region of 'data' that holds objects:
if(full()) return true;
for(int i = in; i != out; i = (i + 1) % data.length)
if(data[i] != null)
throw new QueueException(
"non-null outside of queue range: " + dump());
return true;
}
private String dump() {
return "in = " + in +
", out = " + out +
", full() = " + full() +
", empty() = " + empty() +
", queue = " + Arrays.asList(data);
}
// JUnit testing.
// As an inner class, this has access to privates:
public static class WhiteBoxTest extends TestCase {
private Queue queue = new Queue(10);
private int i = 0;
public WhiteBoxTest(String name) {
super(name);
while(i < 5) // Preload with some data
queue.put("" + i++);
}
// Support methods:
private void showFullness() {
assertTrue(queue.full());
assertFalse(queue.empty());
// Dump is private, white-box testing allows access:
System.out.println(queue.dump());
}
private void showEmptiness() {
assertFalse(queue.full());
assertTrue(queue.empty());
System.out.println(queue.dump());
}
public void testFull() {
System.out.println("testFull");
System.out.println(queue.dump());
System.out.println(queue.get());
System.out.println(queue.get());
while(!queue.full())
queue.put("" + i++);
String msg = "";
try {
queue.put("");
} catch(QueueException e) {
msg = e.getMessage();
System.out.println(msg);
}
assertEquals(msg, "put() into full Queue");
showFullness();
}
public void testEmpty() {
System.out.println("testEmpty");
while(!queue.empty())
System.out.println(queue.get());
String msg = "";
try {
queue.get();
} catch(QueueException e) {
msg = e.getMessage();
System.out.println(msg);
}
assertEquals(msg, "get() from empty Queue");
showEmptiness();
}
public void testNullPut() {
System.out.println("testNullPut");
String msg = "";
try {
queue.put(null);
} catch(QueueException e) {
msg = e.getMessage();
System.out.println(msg);
}
assertEquals(msg, "put() null item");
}
public void testCircularity() {
System.out.println("testCircularity");
while(!queue.full())
queue.put("" + i++);
showFullness();
// White-box testing accesses private field:
assertTrue(queue.wrapped);
while(!queue.empty())
System.out.println(queue.get());
showEmptiness();
while(!queue.full())
queue.put("" + i++);
showFullness();
while(!queue.empty())
System.out.println(queue.get());
showEmptiness();
}
}
public static void main(String[] args) {
junit.textui.TestRunner.run(Queue.WhiteBoxTest.class);
}
} ///:~
The in counter indicates the place in the array where the next object will go into, and the out counter indicates where the next object will come from. The wrapped flag shows that in has gone “around the circle” and is now coming up from behind out. When in and out coincide, the queue is empty (if wrapped is false) or full (if wrapped is true).
You can see that the put( ) and get( ) methods call the methods precondition( ), postcondition( ), and invariant( ), which are private methods defined further down in the class. precondition( ) and postcondition( ) are helper methods designed to clarify the code. Note that precondition( ) returns void, because it is not used with assert. As previously noted, you’ll generally want to keep preconditions in your code; however, by wrapping them in a precondition( ) method call, you have better options if you are reduced to the dire move of turning them off.
postcondition( ) and invariant( ) return a Boolean value so that they can be used in assert statements. Then, if assertions are disabled for performance reasons, there will be no method calls at all.
invariant( ) performs internal validity checks on the object. You can see that this is an expensive operation to do at both the beginning and ending of every method call, as Meyer suggests. However, it’s very valuable to have this clearly represented in code, and it helped me get the implementation to be correct. In addition, if you make any changes to the implementation, the invariant( ) will ensure that you haven’t broken the code. But you can see that it would be fairly trivial to move the invariant tests from the method calls into the unit test code. If your unit tests are reasonably thorough, you can have a reasonable level of confidence that the invariants will be respected.
Notice that the dump( ) helper method returns a string containing all the data rather than printing the data directly. This approach allows many more options as to how the information can be used.
The TestCase subclass WhiteBoxTest is created as an inner class so that it has access to the private elements of Queue and is thus able to validate the underlying implementation, not just the behavior of the class as in a white-box test. The constructor adds some data so that the Queue is partially full for each test. The support methods showFullness( ) and showEmptiness( ) are meant to be called to verify that the Queue is full or empty, respectively. Each of the four test methods ensures that a different aspect of the Queue operation functions correctly.
Note that by combining DBC with unit testing, you not only get the best of both worlds, but you also have a migration path—you can move DBC tests to unit tests rather than simply disabling them, so you still have some level of testing.
