Final Testing: QueueTestProgram.java

Ok, so you think you can code… We’ll see about that. :)

Description

This is a generative testing program that can run thousands of test cases that it generates pseudo-randomly. From a seed number (picked randomly), the testing program then executes the following actions:

The program generates a test case consisting of a series of method calls.
It runs an instance of ArrayQueue and an instance of a standard library queue through this series of method calls, making sure the two programs behave the same at each step.
If they don’t behave the same for a particular method call, the test code has found a bug!
The program then takes the series of method calls (called the "script") and tries to shrink it to as small a script as possible that still shows a bug.
- Shrinking is important because the script that originally found the bug may have been quite long and we want to produce a set of actions that can be replicated by the tester.

If you can run a million test cases without finding any bugs, you can feel reasonably confident that your code is correct.

Note

The QueueTestProgram has a constant defined as: static final int queue_max_size = 10; Hence, it only tests queues at a max capacity of 10 (the argument to the constructor). If you want to test other sizes, like 100, just change this constant. Perhaps some bugs can only be exposed at larger queue sizes.

Directions

You will be running the main method. We have provided code that you can use for all three classes in this recitation. Let’s talk about what’s there:

We have provided two variables to explicitly point out how many test runs (or scripts) the program will execute. Once you have have passed one hundred thousand test runs, you should test your program with a million.

Example

We introduced a bug into our implementation of the LinkedQueue class. This is the error message that was produced:

Testing queues with a maximum capacity of 10.
Tested: 0

RuntimeException
ArrayBlockingQueue.poll() => 13, but..
LinkedQueue.poll() => 27
Method calls that expose bug: [offer(11), offer(13), offer(27), fill-to(1)]

RuntimeException
ArrayBlockingQueue.contains(22) => true, but..
LinkedQueue.contains(22) => false
Method calls that expose bug: [offer(29), offer(22), add(7), contains(22)]

RuntimeException
ArrayBlockingQueue.contains(8) => true, but..
LinkedQueue.contains(8) => false
Method calls that expose bug: [offer(24), add(8), add(22), contains(8)]

RuntimeException
ArrayBlockingQueue.contains(12) => true, but..
LinkedQueue.contains(12) => false
Method calls that expose bug: [offer(3), add(12), offer(19), contains(12)]

RuntimeException
ArrayBlockingQueue.peek() => 7, but..
LinkedQueue.peek() => 19
Method calls that expose bug: [offer(13), add(7), offer(19), poll(), peek()]

The first line informs the user the maximum capacity of the queue.

Tested: 0 indicates that we found this bug right away. It’s a progress bar that prints how many test cases have been run.

Each block of code is a conceptual unit:

The first line shows the Exception that was the symptom.
The second line shows the output produced by the reference implementation (for each of these classes we’ll be using a corresponding Java implementation.
The third line shows the output produced by your class.
The fourth line gives a list of steps that were run to produce that bug.

You can translate the fourth line into something you can test:

Here is one test case from the output above: