Assign2: ADT test and debug warmup

Throughout this course, you will strengthen your programming chops by writing a lot of C++ code. Having effective strategies for testing and debugging this code is a huge help when solving challenging programs along the way. Knowing your way around the debugger is key, so let's get cracking on learning how to make good use of it!

"How I got better at debugging" from Julia Evans

This exercise demonstrates use of the debugger and unit tests on the ADT types.

In this page, there are a few highlighted questions you are to write answers for in the file short_answer.txt. These answers are the only deliverable from the warmup, you do not need to write or submit warmup code.

1) Observe ADTs in debugger

Start by looking over the provided code. The program has three simple ADTs functions. We also provided some companion unit tests to help you find and diagnose the bugs that lurk within.

The reverse function operates correctly. It uses a Stack to reverse the contents of a Queue. Run tests on adtwarmup.cpp and you'll see that this function passes its single test case. We will use this function as practice for examining ADTs in the debugger.

Set a breakpoint within the reverse function and run the program in Debug mode. When the debugger stops at your breakpoint, the Variables pane in the upper-right of debugger window shows the variables in scope and their values. You should see the value of val, and the variables q and s. A nice feature of the Qt Creator debugger is that it can display the internal contents of a collection. Expand q to find a data member named _elements and expand that to see the current queue elements. Do the same for s. The contents of a collection look something like the following screenshot:

Once you have both the stack and queue expanded, step line-by-line using the Step Over button. As you step, watch the top-right pane and observe elements being added and removed.

On some systems the debugger labels elements with indexes from [0] to [size-1], but remember these ADTs do not allow access to elements by index. Step to the half-way point (after the first while loop has completed but before the second while loop has begun) and look at the contents of s and q.

Answer these questions in short_answer.txt:

• Q1. Is the first queue element displayed in debugger pane (element [0]) the element at front of queue or the back? Is the first stack element displayed on the top of stack or the bottom?

2) Test stutterNegative

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 function stutterNegative is a variant of the stutter problem from last week's section. stutterNegative is intended to modify a Queue<int> to double 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.

There are some provided SimpleTest unit tests that demonstrate a few of the inputs that are problematic. Run those tests and observe which ones pass and which do not. The provided test cases include an input with no negative numbers, one with a single negative number, and another with mixed negative numbers. There is no test for a Queue of all negative numbers, so you decide to add one. Add a STUDENT_TEST for this case.

Run the tests again. When running, it seems this new case is taking a really, really long time. In fact what has happened is that the program has entered an infinite loop and is never coming back. You will have to manually stop it. You can exit a stuck program by closing the console window or choosing "Quit" from the menu bar.

Some of the inputs works correctly, others complete and yet produce wrong output, and your new test shows there is also a third category, where some inputs go into an infinite loop.

When constructing tests and analyzing buggy code, it is important to really understand what kind of inputs cause specific problems, as that can help focus the debugging process. You predict that the infinite loop is triggered exactly if all numbers in the queue are negative, but aren't entirely confident. You wonder if it might instead be specific to simply starting or ending with a negative number, or having an even or odd count of negative numbers. What additional test cases can you add that allow you to confirm the precise trigger for the infinite loop?

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

• Q2: What must be true about the input for the function to produce correct output?
• Q3: For which type of inputs does the function go into an infinite loop?

Rather than identify a specific input, we would like you to describe the general characteristics of the respective inputs.

3) Debug stutterNegative

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 in the code. (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.)

Identify one of the failing tests from above (in particular, one that causes an infinite loop may be particularly insightful). Set a breakpoint on the call to stutterNegative inside the test case and then run the tests in Debug mode. If you need to break out of an infinite loop along the way, you can use the Pause/Interrupt button of the debugger.

When the breakpoint is hit, step into the stutterNegative function call and then step until you are at the beginning of the for loop. At this point, expand the variable q to see its contents. Run through a few loop iterations and pay attention to the changing values for i and q. Can you use this information to explain why the loop never reaches its intended termination condition?

Answer the following question in short_answer.txt:

• Q4. What is the bug within stutterNegative that causes it to get stuck in a loop?

Given the above detective work, you may have a fix in mind to apply to the stutterNegative code. Try out that fix and see that it resolves the problem with the infinite loop inputs. As a followup, re-test inputs that previously terminated but with incorrect output. 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!

4) Recognizing error

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

The function removeMatchPair is intended to modify a Map<string, string> to remove any pair where key == value.

Run the provided unit tests. It passes the first test that makes no change, but the subsequent test goes down in flames. The Map remove operation is raising an error because it is disallowed to add/remove elements in the midst of iterating over that collection. (If you think it through, you can see why this would be problematic….) Students very commonly run afoul of this restriction so we thought we'd get it on your radar before it trips you up.

When an error is raised by your code in the middle of a unit test, SimpleTest will report it with a message like the following:

Exception
    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.

    Error: Collection modified during iteration. Iterator is now invalid.
Do not modify a collection during a for-each loop or iterator traversal.

When you see this message, it means a fatal error was raised when running the test and that error prevented the test from completing. The error was not expected. An error generally indicates a bug in your code where it attempts to perform an illegal operation such as accessing an out of bounds index or reading a non-existent file.

You follow the same debugging process for an error condition as a failing test case, set a breakpoint and step through the test to see what has gone wrong. There is one added twist that you can step up to, but not over, the actual crashing operation. If you step over an operation that crashes, the program exits and you lose all of your debugging information. You must re-start the program and step up to the crash again to regain that insightful debugging information.

After you've played around with the tests and encountered this error, go ahead and put a breakpoint on the fateful line that crashes the program. Run the tests in debugger mode and step through a couple iterations of the loop until you get to the point right before the test crashes.

• Q5: What is the state of the variables (as reported in the debugger variable pane) right before the program crashes? What happens if you try to step over the line where the program crashes?

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