---
tags: labs, spr22
---

# [ADVANCED VERSION] Lab 3b: Oracle Testing and Debugging

<!-- :::info
**Students Will Need to Know:** JUnit testing, BST structure
::: -->

## Setup

Before beginning this assignment, clone the source code from GitHub to make your personal repository for this lab. Here is the [GitHub Classroom link](https://classroom.github.com/a/OPYxavEu).

## Learning Goals
* Use concrete examples, invariants, hand tracing, and debugging to explore or explain how a program works
* Develop a collection of examples and tests that exercise key behavioral requirements aspects of a problem
* Practice using debugging diagrams in tandem with the IntelliJ debugger to find and fix bugs in a complex piece of code

## Oracle Testing - [I Write Tests Not Tragedies](https://youtu.be/vc6vs-l5dkc)

In your previous computer science experiences , you've probably only written unit tests. This is a test for functions where one particular input can only produce one correct output, i.e. there are not multiple solutions.

In this part of the lab, you'll learn how to test functions where there are many correct solutions. Let's suppose, for example, that we are sorting a list of pairs of numbers by the first number (note that you would have to make a class to package two numbers toether like this in Java - we omit this for simplicity):

``[(2, 3), (2, 2), (5, 1), (0, 5)]``

This could produce either of the following:

`[(0, 5), (2, 3), (2, 2), (5, 1)]`
`[(0, 5), (2, 2), (2, 3), (5, 1)]`

Both are correctly sorted! So using the testing methods we've worked with so far, you could (wrongly!) fail the test. Let's say our sorter gives us the first list, but our tester checks if the given list was the second list. If this is this case, then we would fail the test even though we had a correct answer. We need to change how we think about testing to account for multiple solutions.

In comes **oracle testing**. Oracle testing, rather than comparing your method's output with one correct solution, checks certain *characteristics* (or *invariants*) of your method's output and ensures they all hold true.

To create an oracle, we first need to know what invariants make for a correct output. You should try to find the minimum number of invariants, without allowing for any wrong output to fulfill those. Let's take our sorting example. The two invariants of a correct output are:

* The output list always contains exactly the same elements as the input list (including the correct count if there are duplicate elements).
* The output list is sorted according to our sorting scheme.

If these invariants hold, then we have a correct output, and if either one does not hold, our output is wrong by definition.

## Making an Oracle
For this lab, you will be writing an oracle to test whether a program that claims to generates binary search trees (*BST*) from a list of numbers produces a valid answer. We have provided you with two implementations (in different classes) of a method called `makeBST`. The method takes a list of `Integer`s and produces a binary search tree of `Integer`s. You will write a function that takes the original list and the output of `makeBST` and produces a boolean indicating whether the output is a valid answer.

In the source code that we've given you, you will find a large number of classes - we will run down how these will work together:
* `Node` and `Leaf` are abstract classes that implement the `IBST` interface for creating trees
* `BSTMaker1` makes binary search trees using `Node1` and `Leaf1`, which extend `Node` and `Leaf` respectively
* `BSTMaker2` makes binary search trees using `Node2` and `Leaf2`, which extend `Node` and `Leaf` respectively
* `Oracle` contains `sameElements` (which we've written for you) and `bstOracle` (which you'll need to fill out yourself); these two methods should be used to test that the BSTs are structured as you expect (i.e. if `bstOracle` returns `true`, your BST is a reasonable output for what you expected)

**Task 1:** Write the `isBST` method in the `Node` and `Leaf` classes. You will use this in your `bstOracle` method. The method takes in no input and checks that `this` is a valid representation of a BST.

**Hint:** You should use `allLess` and `allGreaterEq` in your solution in the `Node`. Read the code in the `allLess` and `allGreaterEq` methods to understand how they use recursion.

**Hint:** Is a `Leaf` a BST? Start writing `isBST` in the `Leaf` class.

**Task 2:** Write the `bstOracle` method in `Oracle.java`, which should make sure that the input `IBST` is actually a BST and that it contains the same elements as the input list.

**Hint:** Use `sameElements` and `isBST` in your solution!

**Task 3:** Check your implementation! Run the tests in the `BSTTest` class and edit and run the tests for the `OracleTest` class we've provided to make sure that your implementations of these methods are correct!

**Hint:** In the `OracleTest` class, there are a few `TODO`s that you should address. The way some of the tests are set up for you is buggy, too, so you should carefully read the tests and determine if they need to be changed.

## Using the Oracle

Now that you have your working oracle, it's time to use it to check whether the `BSTMaker` implementations we provided are buggy.

On a piece of paper, write down the various situations and edge cases that you think you should test. Remember that the input to the `makeBST` methods is a list of numbers, so your edge cases here should be various kinds of lists that you think make for a good collection of tests.

**Task 4:** In the `BSTMakerTest` class we provided, create `JUnit` tests (think `Assert.assertTrue`) for several of your edge cases. Your goal should be to write enough tests to determine whether each of the two `makeBST` methods produces valid BSTs. Your tests should check both of the `makeBST` implementations.

**Hint:** Look at our example test!

:::info
**Checkpoint!** Call over a TA to check over your testsuite **(even if some tests fail)** to ensure that you're catching the necessary test cases.
:::

## Testing and Domain Knowledge
Testing, edge cases, and debugging go beyond ensuring your code runs and functions as expected when passed a technical edge case like an empty list or a negative number. The context in which your code is deployed and types of users who interact with your program can alter its expected functionality and introduce vulnerability to context-dependent bugs. We call the specific knowledge of the rules, logic, and expectations of this context **domain knowledge**.

For example: Imagine you wrote a program to handle Brown student registrations for Spring Weekend. Everyone is excited to see the performers, so the event is expecting a huge turn out! You decided the simplest approach for registrations will be to create Student objects and add them to a list.

The registration form looks like this:

Your plan is to take input from this form and use it to create Student objects, which look like this:

class Student 
{
	String firstName;
	String lastName;
	String phoneNumber;
}

You plan to use the names of the students to create a simple to navigate registration list for check-ins. This list will be ordered by last name and printed out so security can confirm registrations efficiently to keep lines moving.

You will use the phone numbers to send out reminder text messages for performances.

Because the form takes in a full name as a String, you decide that you need two functions, _extractFirstName_ and _extractLastName_, to convert the full name to first and last name fields. Here are the documented functions:

/*
Looks for the first instance of a space in the fullName string
and returns the contents of the String before the space! 
If there is no space, it returns the input.
Ex: “John Smith” -> “John”
Ex: “My Name” -> “My”
Ex: “NoSpace” -> “NoSpace”
Ex: “” -> “”
*/
public String extractFirstName(String fullName) {...}
 
/*
Looks for the first instance of a space in the fullName string
and returns the contents of the String after the space! 
If there is no space, it returns the input.
Ex: “John Smith” -> “Smith”
Ex: “This Is My Name” -> “Is My Name”
Ex: “NoSpace” -> “NoSpace”
Ex: “” -> “”
*/
public String extractLastName(String fullName) {…}

A **user persona** is a fictional archetypical user whose goals and characteristics represent the needs of a larger group of users. Creating personas is a common industry practice that allows designers and engineers to ask “who are we building for?” and ensure the software they create meets the user's needs.

For each of the following user personas, go through the registration process using the code above.

  

**Task 3:** For each of the user personas above:
1) What would the program store for their first name and last name? Does this seem correct?
2) What assumptions were made by the programmer that led to these results?

**Task 4:** Now that you have interacted with this system, each partner should come up with a proposed change to fix the system. You don't need to write any code, just think about how you might solve some of the problems you encountered.

Here the system has three main components: the form, the student object fields, and the name extraction methods. If you opt to alter the form as part of your proposed change, make sure you still collect full names and phone numbers in some capacity!

**Task 5:** Now think of a persona that would break your partner’s solution!

_(Hint: If you can’t think of one, take another look at the user personas above and think internationally. Are we making any assumptions about ordering? Check out [Falsehoods Programmers Believe About Names](https://shinesolutions.com/2018/01/08/falsehoods-programmers-believe-about-names-with-examples/) for some common assumptions.)_

Reflect on how thinking through user personas is similar to or different to the type of testing you did in Part 1 of this lab. It may help to think about the ways you think about coming up with JUnit assertions vs. how you came up with a persona to break your partner’s solution. In your opinion, how do you define the purpose of testing, keeping in mind both types of testing you’ve encountered in this lab?
:::info
Checkpoint! Call a TA over to talk through your answers.
:::

## Debugging - [Debug-A-Boo](https://youtu.be/9i-y0G8nNA8)
If you ran your test suite in the above task, you will have noticed that some tests failed. We will now try to debug those tests and figure out why they failed!

Before you begin debugging, it is imperative that you know what you are looking for. For the next task, you should draw some "Before and After" diagrams.

**Task 5:** Draw out some examples with different cases in mind for how adding to a BST should look. There should be separate drawings for each state of your tree, even if you are trying to work with the same elements. That is, you should not add elements to the tree you have already drawn out, but instead **redraw** the entire tree with the change that you expect to see. We call these drawing "Before and After" diagrams.

**Hint:** How should the BST look before you add an element to it in `BSTMaker`? How should the BST look after you add an element?
- **e.g.** What does adding an element to an empty BST (i.e. a `Leaf`) look like?
- **e.g.** What does adding an element to a tree with one element look like?

Once you know what to expect from your program, you can start to make use of debugging programs to trace the code that you have written!

Here's a quick overview of how the debugger in IntelliJ works (note that different IDEs have different debuggers).

:::success
If you want a more in-depth description, check out the [basic version of lab 3](https://hackmd.io/ObE_Zq8SSfivM_FY3aCzDQ?view#Debugging)!
:::

1. To **run the debugger**, use the little bug icon next to the green run button in the top rightcorner. As with the run button, clicking it will run the last program ran. Use the dropdown if you want to run something new!
-  *There's the bug!*
2. To insert a **breakpoint**, move your mouse to the left of the line you want to break on. If youhave line numbers enabled, it should be to the right of the line numbers. Then, single-click,and a red dot should appear. To remove it single-click on the breakpoint.
3. To **step over**, use the leftmost, arched blue arrow button.
4. To **step into**, use the second to the left blue arrow that points downward at a horizontal line.
5. To **force step into**, use the third to the left red arrow (you shouldn’t need to use this in this course).
6. To **step out**, use the fourth the left blue arrow that points upward.
7. To **run to cursor**, use the rightmost button among the arrow buttons that points at a cursor (this will run your program until the line where your cursor is currently located).
8. To **resume**, use the green play button on the left side of your window.

**Task 6:** Use the debugger to run your `BSTMakerTest` testsuite and figure out why the `BSTMaker`(s) fail. Draw a diagram of the BST as it is in the place where your code breaks, i.e., on the final line of your code before you reach the error and cannot step over any more. How does your diagram differ in comparison with the ones you drew in the prior task? Fix the spot(s) in the code that causes the tests to fail.

**Task 7:** In the `src` package, you may notice that there is `BSTMaker3` and `BSTMaker4`. You should now create tests in `BSTMakerTest` to test these `BSTMaker`s and try to understand why they are broken. You should fix them when you have figured out what is wrong!

**Hint:** `BSTMaker3` makes BSTs out of `Node3` and `Leaf3`, both of which can be found in the `src` package.
**Hint:** `BSTMaker4` makes BSTs out of `Node1` and `Leaf1`.

:::info
**Checkoff!** Congratulations! You've finished this week's lab. Call over a TA to get your lab checked off.
:::

## Just for fun: Debug a restaurant management system! - [Kathi's Diner](https://youtu.be/-26hsZqwveA)

Now, it's time for you to debug our project! First, we'll give you an outline of how it works.

At a high level, the project simulates a restaurant with a fixed number of tables, where parties of diners arrive and depart. We assume any party can eat at any table, and the maximum number of parties that can simultaneously be seated is, therefore, equal to the number of tables in the restaurant. Further, only parties on the list of upcoming reservations can be seated.

When a party (who is on the list of `upcomingReservations`) `arrives`, they are either seated (if there are open tables) or put on a queue of parties who are waiting to be seated. Since they've arrived, they are no longer an `upcomingReservation`. When a party `departs`, the next party waiting in the queue is seated immediately.

The following classes and descriptions are the parts of our project you should know:

1. `Party` - a class representing a group of people that can be seated at a restaurant. A party has only a name and no other characteristics.
2. `Restaurant` - a class representing the state of the restaurant. It has:
* Fields representing the name, number of tables, list of upcoming reservations, list of currently seated parties, queue of parties waiting to be seated, and manager. The following three fields have behaviors that may not be immediately clear, but are nonetheless important:
* `upcomingReservations` contains parties that we expect to show up at some point. When they are either waiting or seated, they are no longer an `upcomingReservation` and should not be in this list.
* `seatedParties` contains parties that are currently seated. The size of this should never exceed `numTables`.
* `waitingParties` are parties that have arrived, but are not yet seated. A party in `waitingParties` should not be in `upcomingReservations` or `seatedParties`.
* a constructor which takes the name of the restaurant, number of tables in the restaurant, and list of upcoming reservations for that night.
* `arrive` - a method that takes a party which has just arrived. The method checks the reservation list (and returns if the party isn't on it), then seats the party if there is available room; otherwise, it adds the party to the queue of parties waiting to be seated.
* `depart` - a method that takes the party which is departing. It removes the party from the list of seated parties, then checks the queue of waiting parties. If there's a waiting party, it seats that party.
* `hasSeatedParties` and `hasUpcomingReservations` methods that return `true` if the corresponding collection of parties is non-empty.
* `randomSeatedParty` and `randomReservationParty` methods that return a random party from the corresponding collection of parties.
* a `main` method that creates several parties and starts up a `Restaurant`.
3. `Manager` - a class that randomly decides when parties arrive at or depart from the restaurant. It has:
* `makeDecision` - a method that chooses at random whether to let a new party arrive or make a seated party depart.
* `partyArrives` - a method that tells the restaurant to let a new party arrive.
* `partyDeparts` - a method that tells the restaurant to let a seated party depart.

There are a few new things included in this restaurant simulation. You'll notice two Java interfaces: `Collection` and `Queue`. The `Collection` interface represents any group of elements, whereas the `Queue` interface is used for any data structure where elements are added (enqueued) and removed (dequeued) such as a `LinkedList`. Feel free to check out the Java documentation for [`Collection`](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/Collection.html) and [`Queue`](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/Queue.html) for more information.

Further, you'll notice that `Restaurant` has an instance of a `Manager` as a field, and `Manager` also has an instance of a `Restaurant` as a field. Circular references like this are common in OOP, and allow the two objects to interact by calling methods on each other.

If the restaurant simulation were working properly, you would see *interleaved arrival and departure messages*, sometimes multiple arrivals/departures in a row, etc. Critically, you should:

* Never see print statements indicating there are more seated parties than there are tables at any point in the output.
* Never see one particular party arrive or depart more than once.
* See that once a party departs, the party waiting the longest should be seated immediately.
* See that all parties eventually leave, and that the restaurant closes for the night once they do.

**Task 8:** Draw debugging diagrams and use the IntelliJ debugger to find the two bugs, and fix them! Be sure to be able to explain to a TA what you did and why the code wasn't working before, using your debugging diagrams. Use the hints below to help your search, as it's hard to look at all this code you didn't write and figure out what's even happening.

**Hint:** The bugs are *both found in methods we've outlined above*, not other unmentioned methods. Further, the bugs are not found in either `makeDecision` inside the `Manager` class or `randomSeatedParty`/`randomReservationParty` or `hasSeatedParties`/`hasUpcomingReservations` inside the `Restaurant` class.

**Hint:** Run the project before trying to debug it to see what's wrong with it and form an educated guess about where the bugs are originating. What is happening that shouldn't be?

**Hint:** look at the `main` method of the `Restaurant`. Based on your educated guess, draw some debugging of what the restaurant should be doing before and after some methods are called. You'll notice that there is some randomness in the code, so you may have to draw two (or more!) diagrams to encompass the possible scenarios.

**Hint:** We know you may not have seen all of these types before, and might be unfamiliar with their methods. Hover your mouse above any method name or any type declaration to get more information!

______________________________

*Please let us know if you find any mistakes, inconsistencies, or confusing language in this or any other CSCI0200 document by filling out the [anonymous feedback form](https://docs.google.com/forms/d/e/1FAIpQLSdFzM6mpDD_1tj-vS0SMYAohPAtBZ-oZZH0-TbMKv-_Bw5HeA/viewform?usp=sf_link).*