Discussion 3 (06-28)

Last time I talked about Vectors. It turns out we will be using ArrayLists in this class (in part because both of the books use them). But don't worry; In addition to similar external interfaces, Vector and ArrayList actually have similar internal implementations.

When working with arrays, the Arrays class (part of the Java standard library) and System.arraycopy() may be useful.

Why test? How important is it?

The standard intro - Studies show that testing accounts for 47% (I just made that up) of the total development time of large commercial software products.

My intro - So far you have written a couple 50-100 line programs. Maybe, if you have previous programming experience, you have written a program that is up to 500 lines long. In either case, consider how many bugs you encountered. Now consider what will happen when you write a 5,000 line program. What about when you work in a team on a 20,000-30,000 line program? These are all reasonable cases that you will likely encounter, even if you aren't a CS major.

Now, what if you are trained in CS and plan to become a software developer? You may very well work on that "large commercial software product". Consider all the bugs in a 1,000,000 line program, developed by hundreds of people. What if, instead of Java, you use a "less friendly" language like C or C++? What if you are writing systems code or networking code?

Further, what if, in addition to trying to write bug free code, you also have requirements on speed/efficiency? What about security? What if the specification of the program keeps changing as you develop? What about approaching deadlines?

It should be fairly clear, simply by extrapolating from the experience you already have, that there will be bugs, sometimes many of them, and you therefore need techniques for fixing them.

Ideally, the testing process begins with the verification of the fundamental components of the program: The methods and classes (the latter assumes we are doing Object Oriented Programming).

Testing a method generally involves feeding in all types of input, confirming that the internals of the method perform as expected, and checking that the output is correct.

int divide(int dividend, int divisor)
{
   return (dividend / divisor);
}

Input

It is generally impossible (even with the small divide method) to test the method with all possible inputs. Instead, we try to test with all classes/types of inputs. For divide, we might try all combinations for dividend and divisor of a "large" negative number (something less than or equal to -2), -1, 0, 1, and a large positivie number (something greater than or equal to 2). This can be applied generally as the 0, 1, many rule: Test a piece of code with the appropriate analogues of many (and negative many), 1 (and negative 1), and 0. The idea is that every input in the "many" class (whether it be 2 or 2,000,000) will behave the same, so testing one of them is sufficient to test the code path that will work for all of them. 0 and 1 (and -1) often follow a different, less often used code path. In general, such inputs bring out corner cases. Under a somewhat idealized view, component testing might be described as the testing of the general case and all corner cases.

For project 1, testing the corner cases will require you to literally test in the corners (and sides and out of bounds, etc). Look at how your implementation behaves with invalid indices (-many, -1, etc), in the corners and edges (0), near the corners and edges (1), and in the middle of the board (many).

Printouts

Debug printouts can be helpful in verifying and, as the name suggests, debugging, the code contained in the body of a method. Here we apply debug printouts to the divide method:

int divide(int dividend, int divisor)
{
   printDebug("Entering divide() with dividend = " +
              dividend + ", divisor = " + divisor);
   return (dividend / divisor);
}

final boolean DEBUG_ON = true;

void printDebug(String message)
{
   if (DEBUG_ON)
   {
      System.out.println(message);
   }
}

Again, I'll admit that this is a bit contrived. But imagine that you had many, more complicated methods. Each could provide information about its internal operation through these debug printouts. Further, all of this additional information could be turned off by simply setting the boolean DEBUG_ON to false.

For project 1, toStringMines() and toStringTiles() are debug printout methods that you must write. toStringBoard() serves both as a necessary part of the game (as the user inteface) and as a debug printout method.

Overview

     -------------    int divide(
     | COMPONENT |      int dividend,
     |  TESTING  |      int divisor)
     -------------

Harness testing is used to test a subset of the code in a program. Usually, this subset represents some conceptual portion or module of the program and has scope (in terms of size) beyond what can be tested using component testing.

The actual test code is contained in the harness, which "surrounds" the code being tested by simulating the parts of the program that the module normally interacts with. In other words, the harness should have the same interface as the part of the program that is not being tested. In this way, the harness can control all input to the module and see all output.

Harness testing is particularly useful when you have written, and want to test, some code that needs to fit into a larger, supplied program framework (as during many projects in the upper div classes and real world software development).

You can harness test project 1 by:
1. Replacing placeMines() with your own version that arranges mines in tricky and deterministic (repeatable) arrangements.
2. Creating a harness that calls markTile() and looks at the results using getBoard(), getMines(), and/or getTiles(). You might even have the harness verify the results automatically, by comparing them to answers that you have computed yourself beforehand.

Overview

     -------------    int divide(
     | COMPONENT |      int dividend,
     |  TESTING  |      int divisor)
     -------------   
           |           -----------
          \|/          | HARNESS |--
     -------------     ----------- |
     |  HARNESS  |     | /|\  |    |
     |  TESTING  |     |  |  \|/   |
     -------------     |  ------   |
                       -->|CODE|<---
                          ------

Integration testing focuses on discovering bugs that may arise from the interactions of modules.

Harness testing is actually a form of integration testing. Therefore, we often "integration test" by writing harnesses that work at different levels (all the way from testing a single class to testing the whole program).

Using your program regularly is a good way to integration test it. This is called Dogfooding.

For project 1, integration testing can actually be pretty fun; Just play MineSweeper!

Overview

     -------------    int divide(
     | COMPONENT |      int dividend,
     |  TESTING  |      int divisor)
     -------------   
           |           -----------
          \|/          | HARNESS |--
     -------------     ----------- |
     |  HARNESS  |     | /|\  |    |
     |  TESTING  |     |  |  \|/   |
     -------------     |  ------   |
           |           -->|CODE|<---
          \|/             ------
     -------------   
     |INTEGRATION|         -----
     |  TESTING  |         |X2X|
     -------------         |132|
                           | 1X|
                           -----

Automated Testing, which can be applied at any of the levels discussed so far, is primarily designed to automate the checking of test results, such that less human interaction is required once the test code has been written. Certainly, writing this type of test code can be difficult or even impossible, in certain conditions. But doing so greatly eases the testing process and has particular benefits for regression testing (dicussed below).

Regression Testing is the retesting of code that was changed (either as part of a normal modification or to fix a bug), to ensure that the change has not broken that previously working code. Writing automated test code makes the process much less painful.

Overview

    -- REGRESSION TESTING
    |
 -----------       -- AUTOMATED TESTING
 |         |       |
/|\ *******|********
 | *      \|/       *
 | * -------------  * int divide(
 | * | COMPONENT |  *   int dividend,
 | * |  TESTING  |  *   int divisor)
 | * -------------  *
 | *       |        *  -----------
 | *      \|/       *  | HARNESS |--
 | * -------------  *  ----------- |
 ----|  HARNESS  |  *  | /|\  |    |
 | * |  TESTING  |  *  |  |  \|/   |
/|\* -------------  *  |  ------   |
 | *       |        *  -->|CODE|<---
 | *      \|/       *     ------
 | * -------------  *
 ----|INTEGRATION|  *      -----
   * |  TESTING  |  *      |X2X|
   * -------------  *      |132|
   *                *      | 1X|
    ****************       -----

Despite our best efforts, software with bugs will reach end-users. Although undesireable, users can serve as testers, finding (and hopefully reporting) those bugs that effect them the most.

Overview

    -- REGRESSION TESTING
    |
 -----------       -- AUTOMATED TESTING
 |         |       |
/|\ *******|********
 | *      \|/       *
 | * -------------  * int divide(
 | * | COMPONENT |  *   int dividend,
 | * |  TESTING  |  *   int divisor)
 | * -------------  *
 | *       |        *  -----------
 | *      \|/       *  | HARNESS |--
 | * -------------  *  ----------- |
 ----|  HARNESS  |  *  | /|\  |    |
 | * |  TESTING  |  *  |  |  \|/   |
/|\* -------------  *  |  ------   |
 | *       |        *  -->|CODE|<---
 | *      \|/       *     ------
 | * -------------  *
 ----|INTEGRATION|  *      -----
 | * |  TESTING  |  *      |X2X|
/|\* -------------  *      |132|
 | *       |        *      | 1X|
 |  *******|********       -----
 |        \|/
 |   -------------        O     O
 ----|WIDESPREAD/|       /|\   /|\
     |   USER    |        |     |
     |  TESTING  |       / \   / \
     -------------

Determinism Vs Non-Determinism

In general, the determinism (or lack thereof) of a test depends on its input, and not the test code. Therefore, a Deterministic test is repeatable and produces the same results because it is given the same input. Ideally, all input would be deterministic. However, many real world systems (such as networks and multithreaded operating systems) are so complex that their behavior appears Non-Deterministic. While we may eliminate the non-determinism during harness testing, we must eventually test the system itself. More advanced techniques (discussed elsewhere) can aid in dealing with these complexities.

Helpful Java Features

Java is a programmer-friendly language, especially when compared to languages like C or C++.

Array Index Out Of Bounds - For example, in Java, indexing outside of the bounds of an array leads to an ArrayIndexOutOfBoundsException and the termination of the program. While this may be unpleasant, it is generally more helpful than allowing the program to continue with the value found at the out-of-bounds index, eventually leading to an incorrect result or crash at some later point in the program, as in C/C++.

Memory Management - Besides the "new" keyword, Java programmers don't have to explicitlly worry about any of the complexities of memory management and access. On the other hand, this is one of the major responsibilities of a C/C++ programmer.

Why Use C/C++ - When you need more speed, control, and/or access, use C/C++.

Exceptions - Along with the automatic checking the JVM does, exceptions provide another nice feature. If an exception is thrown and causes your program to crash, you might want to look it up in the Java API for a description of the problem.

Backtrace - When a Java program crashes, the JVM will automatically print out a backtrace indicating the complete method call list that lead to the crash. Let's take a look at an example:

        Exception in thread "main" java.lang.NullPointerException

        at Backtrace.checkOut(Backtrace.java:19)

        at Backtrace.main(Backtrace.java:14)

The method call list reads from bottom to top. Here, main() called checkOut(), and so on.

It is generally good to start looking for the problem at the line and method indicated in the last or second-to-last call made before reaching the Java Standard Library (whre the problem is often detected and the Exception thrown).