CSCI 104 - Fall 2019 Data Structures and Design

Note: Docker users need to rebuild their image to use Google Tests — check out this Piazza post for more info.

Unit Testing and Coding Practice

In the first part of this lab, we will give you an overview of how to use the Google Test framework to build and run test cases for any C++ project.

After we've gone over unit testing, you'll be working on some coding problems. You're free to work on them on at any pace you want, in any order, but try to work on your own, without discussing with classmates. The purpose of these problems is to prepare you for 1) technical interviews and 2) the programming problems that will be on the midterm exam.

Let's jump in to unit testing!

0 - Motivation

Testing is absolutely essential to a typical development process. Having a complete test suite can ensure that the code that you spent hours building works, fits specification, and is bug-free.

Suppose you have just finished homework and you think you have a pretty good implementation of a doubly linked list. How do you know, for sure, that this list behaves like how you intended it to be? You can manually read through the code a million times, but you might still miss something.

A good test case program should:

There are several advantages for having a well-crafted test program:

The Google Test documentation has further guidelines for what constitute good test suites.

1 - Testing a Fibonacci Program

1.1 - Introduction to Testing

Let's first begin writing tests for a simple function that computes the nth Fibonacci number. But before you open the code for the Fibonacci program, ask yourself - what are some test cases that we'll need to test?

Nominal cases - You can always start with the most basic cases - that 5th fibonacci should be 5, 7th should be 13. It's a good idea to include a few basic cases so to be sure you weren't just lucky, but you shouldn't need anything more than that.

Boundary or Special cases - What are the boundaries for this function? For a Fibonacci calculation, it seems that there is only a "lower-bound", namely when n = 1. For some data structures that are slightly more complex, there might be multiple boundaries, like the resize limit ("capacity") for ArrayList.

Off-nominal cases - Your program should be completely fool-proof. That means your program should handle even input that does not make sense. For example, asking for the -2th Fibonacci number, or asking to insert at the 5th position for a 2 element array. Note that things that do not compile are not part of off-nominal cases. If your compiler cannot compile the code, you won't even have an executable to run.

Notice that we came up with these cases without the need of looking at code - all we did was think about how a Fibonacci program should behave, and how a user would be using such a function. In fact, it's very common for industry software engineers to write the test cases first before writing a single line of code; they call this Test-Driven Development (TDD).

A very simple test program might include a long list of test cases made of if statements that looks like this:

Fibonacci fib;
if (fib.get(5) == 5) {
    std::cout << "OK" << std::endl;
} else {
    std::cerr << "FAIL | 5th Fibonacci number should be 5."
}

However, a long list of these cases can get out of hand very quickly - it's annoying to read and even more so to write repetitive code. We can use a library called Google Test to help us out.

What is enough, and how much is too much?

Generally speaking, there should be at least one test case for each code execution path in a function. For example, if a function has 3 branch conditions, test at least each path once, to ensure all use cases are covered. There is no need to test a single path more than a few times - it doesn't hurt, but it's generally unnecessary as it increases testing time. This is only a rule of thumb, as some edge cases just cannot be predicted by looking at the code.

When testing a class implementation, each public function should be tested. For example, an ArrayList should have test cases for each of add(), set(), remove(), get(), and so on. More on class testing in a little.

1.2 - Our First Google Test Case

Navigate to the part1 directory, and open the test.cpp file included for you. The meat of the test suite provided to you in this file is in these four lines:

TEST(FibTest, Nominal) {
    Fibonacci f;
    EXPECT_EQ(5, f.get(5));
    EXPECT_EQ(13, f.get(7));
}

You should notice that this is not standard C++ syntax. We're using a C++ Macro here that is supplied by the framework. C++, when compiling, will automatically replace this code with some appropriate C++ code defined in the framework. It is likely a much longer chunk of code that Google Test wants to hide and save the user from an unnecessary amount of copy pasting.

A test case is defined by calling this TEST macro. Two more things are important here: FibTest and Nominal, the two "parameters" that are "passed into" the Macro. The first parameter specifies the name of the test suite. As a rule of thumb, all tests in a file should belong to the same test suite, and in this case, FibTest. The second parameter is the name of this test. We're testing the trivial cases right now, so we're just going to call it the "Nominal" case. 

EXPECT_EQ(5, f.get(5));

Another macro here - EXPECT_EQ. The name of this macro is not too surprising - test cases are but a long list of expected results under different circumstances. In here, by calling EXPECT_EQ, you're saying: "When I call f.get(5), the value it returns should equal to 5."

You can find the list of GTest Macros here.

1.3 - Adding some more test cases

As we've mentioned, there are more test cases worthy to be tested. Let's add them together to our test.cpp file.

Boundary or Special Case

In our Fibonacci calculation, we have a base case of "1" and "2" - they return special values unlike the nominal cases. We should add a test that makes sure this happens.

We first start with a call to the macro, with the test suite name staying the same (FibTest), and the test case name something like ("Boundary").

TEST(FibTest, Boundary) {
    Fibonacci f;
    ...
}

What goes inside? Expectation statements. What do you expect f.get(1) return? f.get(2)?

    EXPECT_EQ(??, ??)
    EXPECT_EQ(??, ??)

When you're done - don't run the tests yet! Finish the entire test suite first, before you try to see if anything's wrong. This is to prevent us tailoring our test cases to the code - you would be able to think about edge cases much more easily from a different perspective.

Off-Nominal Case

What else can go wrong? A rule of thumb is: never trust the user. If something can go wrong, it will; so it's essential that your program handles correctly.

For the sake of this testing demonstration, let's assume that any invalid input should return a value of 0. Some invalid inputs in this case could be 0, -1.

Write a test case for this and include it in test.cpp.

Bonus: There is one more edge case. Can you think what it is? (Hint: What's the type of the input?)

1.4 - Run the tests now

Now that we have a complete test suite, we can see if our program works fully to our specs by running make tests on the terminal. Because our dependencies are set up properly, this will attempt to compile the fib object, and then the test executable. After all the compiling is done, it will then attempt to run the test executable.

You should now see a fancy test runner output, that says the output is unexpected, followed by a segfault. It's okay, we'll fix them one by one.

// Line 5: Change from:
return 0;
// to:
return 1;

Run the tests again by calling make tests. That nominal test case now passes successful, but the segfaults are still there in the Off-Nominal Case. Well, that's unexpected. As always, try to debug using gdb.

gdb bin/fibTest

Run until the segfault happens, and then run bt to see how the error occurred. It seems that the program crashed because we ran out of stack space by calling too many recursions. Fix this by modifying our fib.cpp:

// Add after Line 3:
if (n <= 0) { 
    return 0;
}

Run the test again, and it should now pass with flying colors - green, that is.

2 - More about Testing

A common mistake students make is that they write tests for their program to pass. This is wrong. Your job, when writing test cases, is to try as hard as you can to break your code. Try to think of all possible ways that your program can misbehave. When designing test cases, ask yourself these questions:

Remember - the harsher you are when testing your own program, the less bugs will make it to the hands of your end users.

3 - Coding Problems

You'll find four programming problems in lab5/part2. Each will have a brief description of the problem and a empty function for you to fill out. If you're able to pass all the tests for three out of the four problems, you're free to get checked off (but we strongly encourage you to work on all four)!

Take a look at the makefile to see how to run the tests one at a time (e.g. make sequenceTest).

The difficulty level is probably LinkedList < Sequence < BinCombos < Search, but they're all doable with the knowledge you have now, and don't require any data structures you haven't learned yet (except for the bonus in Sequence).

Good luck!

Appendix: A little bit more on the Makefile

You might be a little more confused about the GTEST_LL variable and how we are able to use Google Test. There are several key parts to understand here:

You can probably safely copy this variable everywhere.

bin/fib.o - This is the rule to compile the Fibonacci class by itself. Notice that the -c flag is used - when we compile the class by itself, we can include the compiled object everywhere - in an actual program, or in the test suite.

bin/fibTest - The main test rule. It has two dependencies: the compiled fib object, and the test suite itself. For the command, we simply take all the dependencies and compile them, with the GTEST_LL variable. It's important that the libraries are loaded after the source files, or else the linker will likely throw an error.

tests - A rule that just runs the tests. Optional. Notice that this is a phony rule, because it doesn't actually create any file.