ADT warmup

During this course, you will write quite a lot of C++ code. But writing the code is only the first step; you also need strong skills in testing and debugging to bring a program to successful completion. Knowing your way around the debugger is key. Our assignments will feature warmup exercises that are designed to give you guided practice with the skills and tools for effective testing and debugging.

This warmup exercise demonstrates use of the debugger and testing on the ADT types. You are to answer the questions posed below by writing your answers in the file short_answer.txt. This file is submitted with your assignment.

1) View ADTs in debugger (manually configure if needed)

Look over the provided code in adtwarmup.cpp that operates on Stacks, Queues, and Sets. Some of this code is buggy and provided for the purpose of practicing your testing and debugging skills.

The reverse function is implemented correctly and does not have bugs. It uses a Stack to reverse the contents of a Queue. Build and run the program. When prompted, enter the choice to run tests from adtwarmup.cpp. The reverse function should pass its single test case. (Ignore the test failures reported for the other functions, we'll get to those in a bit).

Use the reverse function to practice debugging an ADT. Set a breakpoint on the first while loop in reverse and run the program in Debug mode. Choose to run the tests for adtwarmup.cpp again and when the debugger stops at your breakpoint, look at the Variables pane in the upper-right of the Qt window.

You should see the variables q , s and val. Expand q by clicking the triangle to the left of its name. The expanded contents of the Queue should look like this:

IMPORTANT: If the Queue contents in your debugger look very different than the screenshot above, this likely means that your debugger is not configured to properly display variables of Stanford collection type. Stop here and follow the instructions to configure your Qt debugger.

The Queue q was passed as an argument to reverse; its contents were initialized in the calling function to {1, 2, 3, 4, 5}. The Stack s and integer val were declared as local variables in reverse. Neither of these variables was assigned an initial value.

In the debugger variables pane, s is displayed as a Stack containing <0 items>. The Stack class has a "default" initializer that configures a new stack that is not otherwise initialized. The default initializer for Stack makes an empty stack. In fact, all of the Stanford collection classes have a default initializer that creates an empty collection.

Compare that behavior to what you see for the integer variable val. Like s, the variable val was declared without an explicit initialization. Unlike the collection types, the int type does not have a default initializer. This means the int variable is left uninitialized. The debugger displays the variable's "value," but that value is merely the leftover contents in the memory location where val is being stored. In the screenshot above, the leftover value happened to be 28672, but you may see something different on your system. Using the value of a variable that has not been initialized will lead to erratic results. For now, just file this fact away. If at some later point in debugging, you observe a variable holding a nonsensical value, check to see if what's wrong is a missing initialization.

Use the Step Over button to single-step through the first iteration of the while loop. After executing the assignment to val, the uninitialized garbage value now becomes sensible. Single-stepping the next line pushes the value onto the stack. Expand the Stack s by clicking the triangle to the left of its name. You should now have both the stack and queue expanded. Continue single-stepping through the loop. As you step, keep your eye on the Variables pane and watch values being moved on and off the stack and queue.

You now know how to inspect and interpret ADTs in the debugger. We hope that you will find this a useful skill when working on the rest of the assignment.

2) Test duplicateNegatives

Testing and debugging are closely related. After writing a piece of code, you will want to test it to verify its behavior. If you uncover a problem, you run your test case under the debugger to further diagnose the bug.

The intention of the function duplicateNegatives is to modify a Queue<int> to duplicate each negative number, i.e. turning the queue {3, -5, 10} into {3, -5, -5, 10}. The given code is buggy and does not behave correctly on all inputs.

The provided test cases try inputs with varying combinations of negative and positive numbers. Run those tests and take note of which tests pass and which do not.

The test results show that the function works correctly only the input without negative numbers. Your hypothesis is that it is the presence of any negative number that triggers the bug. Before you start on debugging, you want to winnow down to the most minimal case. Thus you decide to try a length-1 queue containing a single negative number. Write your own STUDENT_TEST for this case.

Run the tests again. This new case seems to be taking a really, really long time to run. In fact what has happened is that the program has entered an infinite loop. A infinite loop is one that never reaches its stopping condition. Use the interrupt button on the debugger to stop the program.

What have we learned so far from testing duplicateNegatives? The function works correctly for non-negative inputs. For other inputs, the function completes but produces the wrong result. Your new test shows there is also a third category, where some inputs go into an infinite loop.

Precisely identifying what kind of inputs trigger a problem is very helpful, as this will focus the debugging process. You have observed that an input of a single negative number results in an infinite loop. Is there more to the pattern? Could it be specific to where the negative number occurs in the input, such as being the first or last ? Add more student test cases and re-run until you narrow in on the precise trigger for the infinite loop.

Gather the results of your observations and answer the following questions in short_answer.txt:

Rather than identify one specific input, describe the general characteristics of all such inputs.

3) Debug duplicateNegatives

Now that you've observed the buggy behavior and know what kind of input triggers it, let's use the debugger to diagnose the flaw. (You may have already seen the bug when reading over the code; if so, great! But the purpose of this exercise is to show you a methodology for using the debugger that will help you in later times when you cannot spot the bug just from reading the code.)

Start with your test case that goes into a infinite loop. Set a breakpoint on the call to duplicateNegatives inside the test case and run in Debug mode.

When the breakpoint is hit, Step Into the call to duplicateNegatives and then use Step Over to single step through a few iterations of the for loop. Expand the variable q to see its contents and pay attention to the changing values for i and q. Trace out what is happening and work through why the loop never reaches its intended termination condition.

Given the above detective work, come up with a fix to apply to the duplicateNegatives code. Try out that fix and see that it resolves the problem with the infinite loop inputs. As a followup, re-test the inputs that terminated but produced incorrect results. You should find they are also working correctly now. In this case, the same underlying flaw was producing two seemingly unrelated symptoms. Debugger use for the win!

Answer the following question in short_answer.txt:

4) Diagnose a test that raises an error

The last part of the warmup is learning how to recognize when a test case fails due to raising an error.

The function sumStack is intended to return the sum of the values in the Stack<int>.

Run the provided test cases. It passes the first test that makes no change, but the subsequent test goes down in flames. An error is raised during the test execution.

When an error is raised in the middle of a test, SimpleTest reports it like this:

    Test failed due to the program triggering an ErrorException.

    This means that the test did not fail because of a call
    to EXPECT() or EXPECT_ERROR() failing, but rather because
    some code explicitly called the error() function.

When you see this message, it means a fatal error was raised when running the test and that the error prevented the test from completing. The error was not expected. It is due is a bug in your code that attempts an illegal operation. Sometimes there is additional commentary which further explains what made the operation illegal, e.g. index out of bounds, attempt to pop from an empty stack, or modification of a collection while iterating over it.

You follow the same debugging process for an error as a failing test case: add a breakpoint to stop during the test case and step through to see where it goes wrong. If you put a breakpoint inside the test case code before the call to sumStack, your stepping will go through the behind-the-scenes code that sets up for the function call, including make a copy of the stack (the parameter is pass-by-value). This code is a bit goopy, so if instead set breakpoint on the first line of sumStack, this will stop after those function call shenanigans and you can get on to stepping through the operation of sumStack.

There is one added twist to be aware of when stepping through code that has an error — you can step up to, but cannot step through the actual operation that crashes or raises an error. When executing that error or crash, a clever bit of C++ "hyperjumps" control to an error-handling routine (or your program may terminate if the error is more catastrophic). You must restart the program and step over until the crash again to regain the context at the point of the crash.

Looking at the code and stepping in the debugger, you will see that the bug with sumStack is mishandling the input of an empty stack. One possible fix to sumStack would be to add a special case, i.e. inserting this code at the top of the function:

    int sumStack(Stack<int> s) {
        if (s.isEmpty()) {
            return 0;
        }
        ...

However, there is a better fix to the existing code that would make it work correctly for both empty and non-empty stacks, without adding a special case.

That's it. Now that you've made it through the debugging warmup, you should be prepared with all the skills you need to attack the rest of this assignment. Go to it!