Javascinating

I was recently engaged to help debug and fix some code that was implemented as a Finite State Machine (FSM). There were no existing JUnit tests for the code, so I set about to write some. However, as one would expect with such an architecture, simple code coverage is not enough to verify that all the state transitions are exercised. Indeed, I had 100% code coverage with just a handful of tests, even though there were several hundred valid state transitions. (This was verified with the excellent EMMA based eclipse plugin – www.eclemma.org).

For those unfamiliar with this tool, it lights up your code in green and red showing executed/unexecuted lines; it also has some excellent reporting facilities.

I used a technique similar to the following to verify that I had covered all the allowable transitions.

In a future article (if there is sufficient interest), I will show how I used Apache POI to drive the JUnit from an Excel spreadsheet so I could solicit help from the user community to create all the test cases and their expected results. Please add a comment (or email me) if you would like to see an article on spreadsheet driven testing.

Using these two techniques, I quickly identified a number of issues which were corrected, resulting in another happy customer.

The following is a drastic simplification but, hopefully, it illustrates the technique.

Given the following simple state machine implementation…

package net.gprussell;

import java.util.HashMap;
import java.util.Map;

public class State {
	public static String STATE1 = "S1";
	public static String STATE2 = "S2";
	public static String STATE3 = "S3";
	public static String STATE4 = "S4";

	public static String TRANSITION1 = "T1";
	public static String TRANSITION2 = "T2";
	public static String TRANSITION3 = "T3";
	public static String TRANSITION4 = "T4";

	/*
	 * 		Valid transitions
	 *       S1 -> S2
	 *       S1 -> S3
	 *       S2 -> S3
	 *       S3 -> S4
	 */
	static Map<String , String> allowed;
	static {
		allowed = new HashMap<String , String>();
		allowed.put(STATE1 + TRANSITION1, STATE2);
		allowed.put(STATE1 + TRANSITION2, STATE3);
		allowed.put(STATE2 + TRANSITION3, STATE3);
		allowed.put(STATE3 + TRANSITION4, STATE4);
	}

	private String currentState;

	public State() {
		this.currentState = STATE1;
	}

	public State transition(String transition) {
		String newState = allowed.get(this.getCurrentState() + transition);
		if (newState == null)
			throw new RuntimeException("Invalid transition from " +
					this.getCurrentState() + " with transition " + transition);
		this.setCurrentState(newState);
		return this;
	}

	public String getCurrentState() {
		return currentState;
	}

	public void setCurrentState(String currentState) {
		this.currentState = currentState;
	}
}

It can be shown that the following test case executes 100% of the code.

package net.gprussell;

import junit.framework.TestCase;

public class NotGoodEnoughTest extends TestCase {

	public void testGoodTransition() {
		State state = new State();
		assertEquals(State.STATE2, state.transition(State.TRANSITION1).getCurrentState());
	}

	public void testBadTransition() {
		State state = new State();
		try {
			state.transition(State.TRANSITION4).getCurrentState();
			fail("Expected exception");
		} catch (RuntimeException e) {
			assertTrue(e.getMessage().startsWith("Invalid transition"));
		}
	}

}

Here is the EMMA report for this test.

However, we clearly have not exercised all the allowed state transitions.

The following test case ensures that all transitions are executed.

package net.gprussell;

import java.util.HashSet;
import java.util.Set;

import junit.framework.TestCase;

public class FullCoverage extends TestCase {

	private static Set<String> coverage;
	protected void setUp() throws Exception {
		if (coverage == null) {
			coverage = new HashSet<String>();
			for (String s : State.allowed.keySet())
				coverage.add(s);
		}
	}

	private State testing(State state, String trans, String newState) {
		coverage.remove(state.getCurrentState() + trans);
		state = state.transition(trans);
		assertEquals(newState, state.getCurrentState());
		return state;
	}

	public void testGoodPath1() {
		State state = new State();
		state = testing(state, State.TRANSITION1, State.STATE2);
		state = testing(state, State.TRANSITION3, State.STATE3);
		state = testing(state, State.TRANSITION4, State.STATE4);
	}

	public void testGoodPath2() {
		State state = new State();
		state = testing(state, State.TRANSITION2, State.STATE3);
		state = testing(state, State.TRANSITION4, State.STATE4);
	}

	public void testBadTransition() {
		State state = new State();
		try {
			state.transition(State.TRANSITION4).getCurrentState();
			fail("Expected exception");
		} catch (RuntimeException e) {
			assertTrue(e.getMessage().startsWith("Invalid transition"));
		}
	}

	// final test - ensure we covered all transitions
	public void testCoverage() {
		if (coverage.size() > 0) {
			for (String s : coverage) {
				System.out.println(s);
			}
		}
		assertEquals("Not all transitions covered", 0, coverage.size());
	}

}

First, before we execute any tests, we add all the allowable state transitions to a set. As each test is executed, it is removed from the set. At the end, we verify that the set is empty, ensuring that all allowable transitions have been exercised.

Simple, but effective.

Conclusion

It is important to realize that simple code coverage verification is not sufficient in many cases. While it is good to strive for 100% coverage, sometimes even that is not enough and we need to go a step further.

Gary
about