Lab 2: Working with Self-Referential Data; Testing
Goals: The goals of this lab are to practice designing self-referential classes and data, then develop sufficient tests to detect broken implementations.
For this lab, there are no starter files. For each problem, start a new project and build the files from scratch.
2.1 Designing methods on Lists
2.1.1 Developing methods on lists
Start a new project called ListMethodPractice, and add the Tester library to it. Define the interface ILoInt, and define the two classes MtLoInt and ConsLoInt that implement it. Design the following two methods:
length(), that returns the number of items in the list
contains(int value), that determines if the list contains the requested value
2.1.1.1 Guided example
Our initial data definition would be something like
;; A List of Numbers (LON) is one of ;; - '() ;; - (cons Number LON)
Following Lecture 2, we can translate this into Java as follows:
// Represents a list of numbers interface ILoInt {} // Represents an empty list of numbers class MtLoInt implements ILoInt {} // Represents a non-empty list of numbers class ConsLoInt implements ILoInt { int first; ILoInt rest; ConsLoInt(int first, ILoInt rest) { this.first = first; this.rest = rest; } }
We would then construct examples of lists:
class ExamplesLists { ILoInt empty = new MtLoInt(); ILoInt fundies = new ConsLoInt(2, new ConsLoInt(5, new ConsLoInt(1, new ConsLoInt(0, new MtLoInt())))); }
As we add the methods length() and contains(int value) to our interface, we will need to add them to our classes.
Do Now!
Write out the resulting template for ConsLoInt.
Let’s work through boolean contains(int value): how would you write such a function in BSL?
;; contains : LON Num -> Bool ;; Does the given list contain the given value? (define (contains l v) (cond [(empty? l) ...] [(cons? l) ... (first l) ... (rest l) ...]))
Each branch of the cond goes into the respective classes in Java. The base case is easy: an empty list contains no values. For the ConsLoInt case, either the first value is the desired one, or the rest of the list might contain the value:
// In MtLoInt: public boolean contains(int value) { return false; } // In ConsLoInt: public boolean contains(int value) { return (this.first == value) || this.rest.contains(value); }
Do Now!
Write out test cases for this method.
Do Now!
Repeat the process for length().
2.1.2 Working with Examplar
Examplar is a research project out of Brown University, that provides a tool that aims to encourage students to write more comprehensive and more effective test cases. The instructor has written several implementations of the desired functionality: some of which are wheat, or good implementations; some of which are chaff, or bad implementations. It is your job to write sufficient test cases to separate the wheat from the chaff.
When you submit a test suite to an Examplar assignment on Handins, the autograder will show you four test outputs, as described on the Examplar page. Your goal is to drive all four scores up to 100%, but for now, focus on the first two:
Correctness: You want to ensure that your tests do not reject any of the wheat implementations, since they are (by definition) behaving correctly. It’s trivial to do this if you don’t test anything at all, though! So the challenge is to write tests that are correct, and reject none of the wheats. If you do reject some wheats, you will have a lower-than-100% score for Correctness, and the autograder will tell you (a) which of the wheats were "not yet rejected by any valid tests", and (b) which of your test methods incorrectly rejected which wheats. Use this information to clean up your tests until they are all valid.
Thoroughness: How many chaffs did your test cases correctly reject as broken? If you do not catch all the chaffs, this score will be lower than 100%. Use the test matrix table at the bottom of the grading results to see which chaffs are not caught by any of your tests (i.e., which rows are completely blank).
We’ll practice working with this using the two list methods defined above. Start another project, called ListMethodsExamplar. Download the lists.zip file above, and unzip it into your src/ directory of your ListMethodsExamplar project. It should create a src/lists subdirectory containing three files. Make sure that you have this subdirectory! Otherwise, the next steps will not work properly. You will also likely need to ask Eclipse to refresh its file listing, to show you those files in your project: right click on the project itself, and choose Refresh.
Add a new file to your project, src/ExamplesLists.java, and insert the following code:
import lists.*; import tester.*; class ExamplesLists { // your test methods go here }
This code looks almost identical to the code you have above, except for
the import lists.*; line —
Note: There’s not much point in trying to run your test cases right now: the provided stub code doesn’t actually run properly. The only reason we provided the stub implementations is to ensure that Eclipse doesn’t flag any of your code as containing any obvious type-errors, that would prevent the next steps from running.
Try each of the following scenarios. For each one, first predict what output you expect to see from the autograder, and second submit the file and see whether it matches your expectations. You will submit the new ExamplesLists.java file (and only this file!) each time:
Submit an empty class that defines no tests.
Submit a class that contains a single incorrect test for length(), and nothing else.
Submit a class that contains an incorrect test for length(), and an incorrect test for contains(int value).
Submit a class that contains a correct test for length(), and an incorrect test for contains(int value).
Submit all the test cases you wrote in part 1 of the lab above.
Improve your test cases until you have 100% Correctness and Thoroughness coverage.
Once you have a thorough-enough test suite, copy the tests back into the ListMethodPractice project, and see whether your implementations of length() and contains(int value) pass all your tests. If not, fix your implementations until they do.
(Extra for lab; required for homework:) Refine your tests further to have 100% Precision and Usefulness as well as Correctness and Thoroughness. Read the Examplar page again to understand what those two measures are telling you. Compare notes with your classmates, and formulate hypotheses about what bugs are actually present in each chaff.
2.2 Designing a Shopping Cart
Today, we’re going to be working with the following interface:
interface IShoppingCart { // How many items are in this shopping cart? int numItems(); // How many items of the given name are in this shopping cart? int itemCount(String itemName); // What is the total cost of all the items in this shopping cart, // in cents? int totalPrice(); // Produce a shopping cart containing all the items of this one, // plus one item of the given name and price in cents IShoppingCart add(String itemName, int price); // Remove the given quantity of items of the given name from this shopping // cart, and produce a new cart of the remaining items IShoppingCart removeItem(String itemName, int count); // Produces a new, empty shopping cart IShoppingCart removeEverything(); }
Start by copying this interface into a new project.
Its methods break into two groups: observations, the first three methods that let you find out what’s in the shopping cart; and operations, the second three methods that let you manipulate the contents of the cart.
You might also find the following partial data definitions helpful:
class Item { String name; int cost; // Construct a new cart item with the given name and cost in cents Item(String name, int cost) { this.name = name; this.cost = cost; } // Is this item named the given name? boolean isNamed(String searchedName) { return this.name.equals(searchedName); } // Add this item's cost to the given cost int addCost(int runningCost) { return runningCost + this.cost; } } interface ILoItem { } class MtLoItem implements ILoItem { } class ConsLoItem implements ILoItem { Item first; ILoItem rest; // Construct a new cons with the given first item and rest list ConsLoItem(Item first, ILoItem rest) { this.first = first; this.rest = rest; } }
Feel free to add to these definitions any methods you might need in your design.
Problem 1
Design a class called ShoppingCart that implements the IShoppingCart interface.
There are a few important considerations we need to take to make this lab work properly.
The file you put all your code in must not be called ShoppingCart.java. Name it after your examples class, i.e. ExamplesShoppingCart.java.
You may implement your ShoppingCart class however you see fit, but it must have at least a zero-argument constructor that initializes an empty cart. This almost certainly won’t be the only constructor you’ll have, but it’s necessary to get this lab to work.
When creating examples of your implementation, you may only use the zero-argument constructor and the methods on IShoppingCart to do so. In other words, your examples class should not explicitly use your other constructors. You may, however, use your other constructors in your implemented methods.
You must only test the output of the observation methods (numItems, itemCount, and totalPrice) rather than if two objects are explicitly equal with checkExpect. The interface defines the only interactions you can have with these objects; checkExpect will break this facade by peering behind the curtain to decide if its two arguments are equal. That’s usually helpful, but for this lab it’s cheating.
Here’s a sample examples class for this lab:
// In an examples class IShoppingCart empty = new ShoppingCart(); IShoppingCart withCarrot = empty.add("carrot", 50); IShoppingCart bluth = withCarrot.add("banana", 1000); IShoppingCart minusBanana = bluth.removeItem("banana", 1); IShoppingCart bluthCleared = bluth.removeEverything(); // Good test! boolean testRemoveItem(Tester t) { return t.checkExpect(minusBanana.itemCount("banana"), 0); } // Good test! boolean testRemoveEverything(Tester t) { return t.checkExpect(bluthCleared.numItems(), 0); } // !!!!! WARNING !!!!! BAD TEST (for this lab)!!!!! boolean testBADLY(Tester t) { return t.checkExpect(bluthCleared, empty); }
The first two test methods are formatted correctly for this lab; they compare values of the observation methods on different objects. The third test is bad (in the context of this lab). It tries to compare two carts directly, rather than testing if they behave the same. We want to focus on the behavior of our carts for this lab.
Be sure to write interesting tests that really put your implementation through its paces. Where are the interesting edge and corner cases in your design? Where do you think other students might have slipped up?
Problem 2
Copy your current implementation into a text file somewhere for safe keeping. Then, to make the test swap intersting, introduce a bug into your implementation.
It could be anything; totalCost always returns 0, removeEverything keeps one thing in the list, etc. Get creative, and keep your bug a secret from the other teams!
We’ll move on to the next section once everyone is ready. Keep thinking of weird examples and tests you can write while you wait.
2.2.1 Switch It Up
You will exchange your examples files with other partners near you. Rename your examples class to include your names in it (e.g. ExamplesKyleMatt). Copy that examples class into a separate file with your names in it (e.g. ExamplesKyleMatt.java) and email it to the partners nearest to you in the lab.
Problem 3
Add the file you received in email to your project (by moving it into the src/ directory of your current project).
Add a new run configuration that points to this new examples class and run it.
Did their examples and tests find the bug you introduced? Did they reveal a bug that you hadn’t even realized was there? Examine their examples and tests; did they test any interesting edge cases you hadn’t considered?
Repeat this with at least one other team’s examples class.
Problem 4
Talk with the team you’ve exchanged code with. Each team should have both run other teams’ tests against their own buggy implementation, and had their own tests run against other teams’ buggy implementations. To make this discussion run smoothly, each team should first announce whose examples they downloaded and tested, and tell that other team which tests passed and which failed on your buggy implementation.
You now should have received feedback from other teams about how good your tests were at finding bugs in their code. Brainstorm a bit and make a guess what the bugs were that other teams had in their code. Talk about the things you each considered in your testing, and why you thought those tests were interesting to write.
It’s also possible that the other teams’ tests found other accidental bugs in your code! With this extra knowledge, fix those bugs the other team found in your implementation (except for the one you purposefully introduced). Then, update your examples class with examples and test cases that you might not have considered before.
2.2.2 Extension: Putting Your Tests to the Test
Your examples class should now include a veritable cornucopia of interesting examples and test cases. Let’s see if it’s as bulletproof as you think.
Setup
First, refactor your test cases slightly. You likely have test methods that look something like
class Examples { boolean testSomething(Tester t) { IShoppingCart c = new ShoppingCart(); ... do stuff to c ... return t.checkExpect(c.something(), expectedAns); } }
Revise this code to look like
class Examples { boolean helper_testSomething(Tester t, IShoppingCart c) { ... do stuff to c ... return t.checkExpect(c.something(), expectedAns); } boolean testSomething_yours(Tester t) { return helper_testSomething(t, new ShoppingCart()); } }
This lets the helper method test multiple different implementations of IShoppingCart, rather than only your own ShoppingCart class.
There are thirty buggy implementations of shopping carts for you to experiment with: you can download them at the following schematic URL:
https://course.khoury.northeastern.edu/cs2510a/files/ShoppingCart_badX_Y.jar
...where X is between 1 and 6, and Y is between 1 and 5. As a hint, X refers to one of the six methods in the interface, and Y is one of several bugs for that implementation.
Download this jar file into your EclipseJars folder that you keep tester.jar in. Add it to your project like you would any other library.
These libraries have added two implementations of IShoppingCart into your project, named ShoppingCart_badX_Y and ShoppingCart_good. The bad implementation has a bug in exactly one of its methods; the good implementation should be 100% correct.
Problem 5
Duplicate the code for testSomething_yours to two more methods:
boolean testSomething_bad(Tester t) { return helper_testSomething(t, new ShoppingCart_badX_Y()); } boolean testSomething_good(Tester t) { return helper_testSomething(t, new ShoppingCart_good()); }
When you run your program now, you should simultaneously test your own implementation, the good implementation, and the bad implementation you were given. What do you think should happen, if your tests are thorough enough? Make a prediction and write it down, before you actually do run your tests!
Now run your tests. In a comment near your examples class, describe what happened. Did all of your tests pass? If they didn’t, which tests failed? Make a note of what you think the bug in the bad implementation is.
If all of your tests did pass, do you think this is because the implementation isn’t actually buggy or because your examples and tests didn’t find the bug? Can we tell the difference?
Try this exercise on as many of the thirty bugs as you’d like – see how many of them you can find without needing to update your tests: the more you find, the more thorough your test suite was. Additionally, see how many bugs are caught by exactly one of your tests: this is an indicator of how sensitive your test cases are, and how precisely they pinpoint individual mistakes. If a single test case fails on many, many bugs, then it is not a very useful diagnostic tool to help you narrow down the cause of the bug.