3/4 Recitation 5

1. Top-Down vs. Bottom-Up Testing
2. Blackbox vs. Glassbox Testing
3. Exceptions
4. Catching Exceptions
5. Exception Abuse

1. Top-Down vs. Bottom-Up Testing

Bottom-Up Testing is when you test the modules that have no dependencies first and then test the modules on which they depend. Bottom-up testing is often much easier to implment in Java than top-down testing because you can create a unit test for classes at the bottom of the hierarchy, such as D and E, and then use those modules (once they've passed their tests) to test an upper-level modules such as C.

Given the topologically sorted nature of this example, here are implementations of the two testing strategies:

• Top-Down
  • test A first
  • test B sometime after A passes its tests
  • test C sometime after A passes its tests
  • test D sometime after A and C pass their tests
  • test E sometime after C passes its tests
• Bottom-Up
  • test B, D and E independently first
  • test C after D and E pass their tests
  • test A after B, C, and D pass their tests

By introducing interface H, we have eliminated the circular dependency from our design. In the event that a redesign is not possible, we could make a stub for F and G and use the stub to test the other module. If we tested F and G together without stubs, then a failure in the test suite would be able to localize the bug to neither F nor G. What's worse is that F and G may pass the test suite together because they have some mutually beneficial (yet independently deficient) behavior that is not realized until F and G are shippied out and used independently by another client. This is another motivation for eschewing circular dependencies in your design.

2. Blackbox vs. Glassbox Testing

Glassbox Testing is when you test a module's internal program structure. With a glassbox test, you should test different flows of control through the program as well as subdomains that may not have been discoverable from the specification alone.

Let's look at how we would test the example below. Recently, I had to augment a jabber chat client so that it would keep track of the ten messages that you sent most frequently. Thus, I needed to create a data structure that would keep track of the frequency of everything that I sent, but that could also return the top 10 mostly frequent messages quickly.

Thus, I decided upon the following interface. From its specification, you might consider creating a blackbox test that would check the following:

• null sentences get ignored
• the length of the array returned by getTopTen is always 10
• the empty spaces in the string array are null
• the elements in the array are the top 10 messages sent
• the elements in the array are sorted from most frequently sent to least
• if two elements have the same frequency, the one sent more recently comes first

TopTen.java:

/**
 * Keeps track of each sentence that has been sent and
 * can return the 10 sentences that have been used most often.
 */
public interface TopTen {

  /**
   * Records that the sentence has been sent.
   * @param sentence the sentence sent, ignored if null
   */
  public void recordSentenceSent(String sentence);

  /**
   * @returns an array of length 10 with the sentences
   * ordered from most frequent to least frequent
   * If fewer than 10 phrases have been used, the empty
   * spaces in the array are null
   * If two sentences have the same frequency, then the one
   * that was used more recently is listed first.
   */
  public String[] getTopTen();

}

But such an implementation would be unlikely to have the boundary case that TopTenImpl has at 10 elements. With this implementation, it is important to test what happens when the size of the Map is 9, 10, and 11. We must ensure that the top 10 is updated correctly when elements get swapped in and out of it. Further, consider the case where there are only 11 sentences that get added to this ADT – in this situation, TopTen will be doing its maximum computation for each call to recordSentenceSent.

These details are only revealed by looking at the implementation of TopTenImpl. Thus, a blackbox test for TopTenImpl may not have caught bugs (if there were any :) that occurred with 9, 10, or 11 elements. Be sure to consider glassbox as well as blackbox tests when designing your own test suites.

At the bottom of TopTenImpl, you will can see the (non-rigorous) tests that I ran to convince myself that TopTenImpl worked as advertised.

TopTenImpl.java:

/**
 * An ADT that implements TopTen in Java
 */
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class TopTenImpl implements TopTen {

  /*
   * This ADT works by storing the frequency for each
   * sentence in a Map and by keeping track of the
   * frequency of the 10th member of the top 10.
   * Thus, the top 10 is only sorted when the frequency
   * of a sentence meets the value of minFreq.
   */

  /** the size of the top 10: should be 10, but can be changed here */
  protected static final int SIZE = 10;

  /** maps a sentence(String) to its frequency of use (Integer) */
  private Map/*<String,Integer>*/ sentMap = new HashMap();

  /** the current top 10 */
  private List topTen = new ArrayList();

  /** the frequency to meet to be in the top 10 */
  private int minFreq = 0;

  /**
   * Records that the sentence has been sent.
   * @param sentence the sentence sent, ignored if null
   */
  public void recordSentenceSent(String sentence) {
    if (sentence == null) return;
    int freq = 1;
    Object val = sentMap.get(sentence);
    if (val != null) freq = ((Integer)val).intValue() + 1;
    sentMap.put(sentence, new Integer(freq));
    // if does not exceed minFreq, then does not belong in top 10
    if (freq < minFreq) return;
    // starts searching at index for placement in top 10
    int index = topTen.indexOf(sentence);
    if (index >= 0) {
      topTen.remove(sentence);
    } else {
      index = topTen.size();
    }
    // traverse top 10 until higher freq is found or beginning of list reached
    while (index > 0) {
      String phraseAhead = (String)topTen.get(index - 1);
      int otherFreq = ((Integer)sentMap.get(phraseAhead)).intValue();
      if (freq < otherFreq) break;
      index--;
    }
    // add sentence at new position in top 10
    topTen.add(index, sentence);
    int ttSize = topTen.size();
    // remove 11th member, if applicable
    if (ttSize > SIZE) {
      topTen.remove(SIZE);
      ttSize--;
    }
    // update the minimum frequency required to be in the top 10
    if (ttSize == SIZE) {
      minFreq = ((Integer)sentMap.get(topTen.get(ttSize - 1))).intValue();
    } else {
      minFreq = 0;
    }
  }

  /**
   * @returns an array of length 10 with the sentences
   * ordered from most frequent to least frequent
   * If fewer than 10 phrases have been used, the empty
   * spaces in the array are null
   * If two sentences have the same frequency, then the one
   * that was used more recently is listed first.
   */
  public String[] getTopTen() {
    String[] tt = new String[SIZE];
    tt = (String[])topTen.toArray(tt);
    return tt;
  }

  /** returns the non-null members of the top 10 */
  public String toString() {
    return topTen.toString();
  }

  /** used for testing */
  public static void main(String[] argv) {

    // test to make sure frequency rules are preserved
    TopTen t1 = new TopTenImpl();
    String[] strings1 = {
      "foo", // foo (1)
      "foo", // foo (2)
      "foo", // foo (3)
      "bar", // foo (3), bar (1)
      "bar", // foo (3), bar (2)
      "foo", // foo (4), bar (2)
      "bar", // foo (4), bar (3)
      "bar", // bar (4), foo (4)
      "bar", // bar (5), foo (4)
      "foo"  // foo (5), bar (5)
    };
    TopTenImpl.addAndPrint(strings1, t1);
    
    // test to make sure works past 10 args
    TopTen t2 = new TopTenImpl();
    String[] strings2 = {
      "one",    // 1
      "two",    // 2, 1
      "three",  // 3, 2, 1
      "four",   // 4, 3, 2, 1
      "five",   // 5, 4, 3, 2, 1
      "six",    // 6, 5, 4, 3, 2, 1
      "seven",  // 7, 6, 5, 4, 3, 2, 1
      "eight",  // 8, 7, 6, 5, 4, 3, 2, 1
      "nine",   // 9, 8, 7, 6, 5, 4, 3, 2, 1
      "ten",    // 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
      "one",    // 1, 10, 9, 8, 7, 6, 5, 4, 3, 2
      "two",    // 2, 1, 10, 9, 8, 7, 6, 5, 4, 3
      "two",    // 2, 1, 10, 9, 8, 7, 6, 5, 4, 3
      "eleven", // 2, 1, 11, 10, 9, 8, 7, 6, 5, 4
      "eleven", // 2, 11, 1, 10, 9, 8, 7, 6, 5, 4
      "eleven"  // 11, 2, 1, 10, 9, 8, 7, 6, 5, 4
    };
    TopTenImpl.addAndPrint(strings2, t2);
  }

  /** adds strings to t and prints intermediate top 10 lists */
  private static void addAndPrint(String[] strings, TopTen t) {
    for (int i = 0; i < strings.length; i++) {
      t.recordSentenceSent(strings[i]);
      System.out.println(t.toString());
    }
  }

}

3. Exceptions

• Checked Exceptions which in Java manifest themselves as objects that extend Exception but not RuntimeException
• Unchecked Exceptions which in Java manifest themselves as objects that extend RuntimeException in addition to Exception

• returning null or -1 or some other value that fits the return type of a method, but is reserved as an "error code"
• System.exit(-1) which will terminate the program and return a value of -1. Note that a return value of 0 is used to indicate that a program exited cleanly

Calling System.exit() will terminate your program which means that responding to an error in this fashion will not give your program a chance to recover. This is a very dramatic response to an error and should probably never be used in practice to respond to an error. Unless your choices are "push the big red button with the mushroom cloud icon" and invoke System.exit(-1), avoid System.exit().

Thus, you should respond to "exceptional situations" by throwing exceptions. Let's compare the two types of exceptions in Java:

Exception

RuntimeException

methods that throw an Exception must declare it in their signature methods that throw an Exception should also declare it in a @throws clause along with the conditions under which it is thrown a method that calls a method that throws an Exception must either respond to the method by catching it, or by also declaring that it throws the exception it is appropriate to throw an Exception when an error occurs that is beyond the client's control, such as an IOException that occurred while writing a file – perhaps a hard disk failed or a floppy disk was ejected: these are rare occurrences that are beyond the client's control that he must decide how to deal with

a RuntimeException that is thrown by a method need not be declared in it signature, but it should be declared in a @throws clause in its specification along with the conditions under which it is thrown it is appropriate to use a RuntimeException for situations that the client can avoid, such as ArrayIndexOutOfBoundsException and NullPointerException

Another benefit of exceptions is that you can bundle information with them (such as an error message, or anything you want, really if you extend Exception and create your own class). This information can be passed to the client and will potentially help him recover from an error. For an example, consider a SQLException that is thrown while interacting with a database. It is important for the client to know if the error occurred before or after his data was written to the database. Thus, this is a checked exception that forces the programmer to deal with a problem, such as the database connection going down, and gives him the information he needs to get his database back to a consistent state.

But don't go overboard because throwing an Exception is expensive. Further, if you can deal with the error within your own method, then there is no need to burden the client with an exception. Consider the following example:

String someString; // suppose someString = "fireEngine"
int index = someString.indexOf("z"); //returns -1

4. Catching Exceptions

You can catch a variety of exceptions with a sequence of try-catch blocks (as shown below). The exception will be caught by the first catch clause that includes it. Note that the boldface code below should be removed because it prevents the blocks below it from ever being reached.

Also, notice how the exceptions are caught and rethrown as a DatabaseException. Because the code in the try block may throw any of four checked exceptions, it would be tedious for every caller of getConnection() to declare these four exceptions as well. Instead, they are wrapped into one exception; namely, DatabaseException. Now clients of getConnection() only have to declare one exception.

If a client wishes to know which exception DatabaseException is wrapping, he or she can call its getCause() method. The getCause() method is a method of Throwable (an interface that Exception implements), so you can always trace a chain of wrapped exceptions, if necessary.

public static Connection getConnection(String driver, String parameters)
  throws DatabaseException {
  try {
    Class.forName(driver).newInstance();
    Connection connection =
    DriverManager.getConnection(parameters);
    return connection;
  } catch (Exception e) {
    // this is an error because:
    // (1) every Exception is an instanceof Exception,
    //     so this will catch every Exception and the clauses
    //     below will never be reached
    // (2) nothing is done with the Exception here
    //     at a minimum, you should call e.printStackTrace()
    //     to let the client know that something has gone wrong
  } catch (IllegalAccessException e) {
    throw new DatabaseException(e);
  } catch (ClassNotFoundException e) {
    throw new DatabaseException(e);
  } catch (InstantiationException e) {
    throw new DatabaseException(e);
  } catch (SQLException e) {
    throw new DatabaseException(e);
  }
}

5. Exception Abuse

/**
 * @requires strings is not null
 * @effects prints each string in strings to the standard output
 */ 
public static void printStrings(String[] strings) {
  int i = 0;
  while (true) {
    try {
      System.out.println(strings[i++]);
    } catch (ArrayIndexOutOfBoundsException ex) {
      break;
    }
  }
}