Registrar, Part 1

Learning goals

• Understand how shared mutable state can create the potential for bugs
• Learn principles of defensive programming
• Practice defensive programming by using:
  • immutable collections
  • defensive copying
  • appropriate data structures
• Get more practice writing unit tests
• Learn about the Set data type

Step 0: Get some context

Study the API

In this activity, you’ll work with an object model for a hypothetical college registrar system. The system tracks which students are enrolled in which courses. Look at the Student and Course classes, and understand their API: What are the public methods? What do those methods do?

The registrar model has a strict API contract, which you will find in the README that comes with the activity starter code. Read and understand that API contract.

Study the tests

We have implemented tests that verify that the existing code satisfies this contract. Run RegistrarTest . All the tests should pass.

Spend a little time understanding the structure of RegistrarTest, which exercises the API:

• Note all the specific cases it tests.
• Note the createStudents and createCourses methods at the top, which run before each individual test case (because of the @BeforeEach annotation).
• Note also the checkInvariants method at the bottom, which runs after each individual test case (because of the @AfterEach annotation). What is this method’s job? It makes sure that all the invariants of the API still hold after each test case is done.

Study the enrollIn method of Student

This method is the API’s entry point for adding a student to a course. One uses it like this:

someStudent.enrollIn(someClass);

How does the method ensure that the first invariant holds (the bidirectional relationship between courses and students)?

How does the method ensure that the second invariant holds (a course never goes over its enrollment limit)?

Step 1: Identify the flaw

In the Student class, take a look at the getCourses() method. What is the runtime type of the object it returns? “Runtime type?!?” Here is an explanation of what that question means:

The method declaration says it returns a List. That means List is the compile-time type: the method promises to return something that is a List, and List is the type that Java uses to check the code at compile time (i.e. before the code runs).

However, List is an interface, and many different classes implement that interface. When the code actually runs, that code will return some specific object, and that object’s class will be some specific class that implements List. That specific class is the runtime type. What class is it? Discuss with your partner.

When you think you have the answer, check it here: ArrayList

Because of that runtime type, the list getCourses() returns is a mutable list. That means we can do this:

// Suppose:

// - comp127 is a Course
// - sally is a Student
// - comp127 has no students enrolled yet

List<Course> sallyCourses = sally.getCourses();
sallyCourses.add(comp127);
System.out.println(sallyCourses);        // (1) What will this print?
System.out.println(sally.getCourses());  // (2) How about this?

Discuss with your partner, then check your answers: Will comp127 show up in the print statement at (1)? Yes How about the one at (2)? Also yes (why?)

This is bad news. Why? To enroll a student in a course using the API, we are supposed to call the enrollIn method of Student. The enrollIn method carefully preserves the invariants. However, the Student code gives everyone a way of directly modifying the student’s list of courses, completely bypassing enrollIn.

After running the code above, what does this code print?

System.out.println(comp127.getStudents());

Answer: an empty list.

That violates the first invariant! Sally thinks she’s enrolled in COMP 127, but she’s not on the course’s roster.

The course’s getRoster method has exactly the same problem. We can use it to enroll students in courses they don’t know they’re enrolled in: the common recurring nightmare come to life! We can also do this:

comp127.setEnrollmentLimit(16);
comp127.getRoster().add(sally);
comp127.getRoster().add(marvin);
comp127.getRoster().add(diego);

…

…10000 more students here…

…
comp127.getRoster().add(sunita);
comp127.getRoster().add(lin);
comp127.getRoster().add(duc);

…and now we’ve violated the invariant about enrollment limits. Argh!

The problem here is that when getCourses and getRoster return an ArrayList, they are sharing the same ArrayList object they use for their own internal state with any external code that uses the API. After this line of code:

List<Student> whatever = sally.getCourses();

…the whatever variable and sally’s private courses instance variable both point to the same object. (This situation where two variables point to the same object is “ aliasing.”) Returning that ArrayList breaks encapsulation! Any code using our API can mess with the internal state of students and courses. This opens the door to insidious bugs. It might even lead to security flaws.

Step 2: Test the flaw

We are going to fix the flaw, but before we fix it, let’s write a test we can use to verify our fix. To be confident that our test verifies the fix, we first should verify that it fails before the fix is done. Add the following code to RegistrarTest:

    @Test
    void clientsCannotModifyCourses() {
       List<Course> courses = sally.getCourses();
       courses.add(comp127);
    }

Run the tests. This test should fail.

Usually tests fail because of an assertEquals() or other test assertion. Why does this test fail, even though there are no assertions in clientsCannotModifyCourses? (Hint: remember @AfterEach)

As of this writing, VS Code does a poor job of exposing the true error message from that test failure. You have to go digging for it:

Now we can see the true error:

Try it, and read the full error message. This error message is good news! The test is catching exactly the problem we wanted it to catch.

Did we need to create that local variable named courses? What if we do this instead?

    @Test
    void clientsCannotModifyCourses() {
       sally.getCourses().add(comp127);
    }

Does the test still fail? Why or why not? Discuss with your partner.

Step 3: Fix the flaw

One possible approach would be to modify the getCourses to return a mutable defensive copy of courses — a whole new ArrayList — instead of the original object. The Student object’s true list of courses stays private; clients can only see a copy, and it’s fine if they modify their own copy. (Why the word “defensive?” Because the API implementation is defending the API’s contract against bad behavior from API clients.)

Try doing that: make getCourses return a copy of the list of courses.

Hint: ArrayList has a copy constructor.

Hint: Use the copy constructor like this: new ArrayList<>(courses)

Run the tests again. Your new test (and all the old ones) should pass now!

Step 4: Try a better fix

You’ve patched the flaw, but it’s not ideal to make defensive copies of lists all the time. Why not? Because lists take memory, and copying them takes time.

Fortunately, Java gives us an alternative: unmodifiable collections. Read the few paragraphs in the “Unmodifiable View Collections” section at that link, then try making getCourses() return the appropriate unmodifiable collection view.

Hint: The one you want is Collections.unmodifiableList().

Hint: Use it like this: return Collections.unmodifiableList(courses);

When you do this, instead of copying the whole list, Java will return a tiny (and cheap) wrapper object that forwards only read operations to the real course list, and refuses to forward write operations. Instead of giving callers a modifiable copy, the method now gives them an unmodifiable view.

This will cause the existing test to fail again. (Why?) Modify the test so that it checks for the correct error. You can use the following code pattern in a test to say, “I expect an error to happen! The test fails if the error doesn’t happen.”

assertThrows(TypeOfExceptionYouExpect.class, () -> {
   // code that should cause the exception
});

Run all your tests. They should all pass now.

Step 5: Fix getRoster too

The getRoster method in Course has exactly the same problem. Fix it in the same way:

• Write a test that attempts to modify the list returned by getRoster. (It is OK to jump straight to using assertThrows in your test now that you know what kind of exception you expect.)
• Run the tests. Make sure the new test fails.
• Make getRoster return an unmodifiable view collection, just as before.
• Run the tests. Make sure they pass.

Step 6 (if time allows): Fix a different kind of flaw

It is not essential for you to do this step if you are short on time; you’ll learn about this topic sooner or later. If you do have time, however, this is a good opportunity to learn about one of the alternatives to List in Java.

Here is something terrible that the current API lets us do:

comp127.setEnrollmentLimit(16);
for (int n = 0; n < 16; n++) {
    sally.enrollIn(comp127);
}

Now the course is full! Sally has singlehandedly filled COMP 127 by registering herself for it multiple times. The course roster is now Sally, Sally, Sally, Sally, Sally, Sally…. Note that this does not violate any of our API invariants. It sure does seem wrong, though, doesn’t it? We probably need two new invariants in our API:

Any given student can appear in a course roster at most once.

Any given course can only appear in a student’s collection of courses at most once.

We could enforce this invariant by modifying the enroll method of Course so that it checks whether a student is already enrolled, and doesn’t re-add them. However, there’s an interesting alternative: using Set instead of List.

A quick introduction to Set

In Java, Set is another collection type like List. There are two major differences between the List and Set interfaces:

• A List can contain duplicate elements, but every element in a Set is unique. If you have an empty Set<String> and you call add("Hello") a million times, the set will still only contain a single "Hello" and its size will be 1.
• A List preserves the order of elements added to it; a Set does not. This means that, unlike a list, you cannot get an element of a set by numeric index. You can iterate over a set with a for-each loop just like a list, but you might get the elements back in a different order than you put them in. The order in which you see the elements might even change the next time you loop over the set!

###

Basic usage of Set closely parallels List:

This should be enough information to get you through the activity. You can consult the Javadoc for List and Set if you need more information.

Using Set in our API

Let’s change a course’s roster and a student’s courses to both be sets instead of lists:

• Change the roster instance variable of Course:

` private Set roster = new HashSet<>();` - Change the `courses` instance variable of `Student`:

` private Set courses = new HashSet<>();` - Change the return types of the `getRoster` and `getCourses` methods to both be `Set` instead of `List`.

Note that because this is a breaking change, you’ll need to update code that uses the API. That means lots of compile errors in the tests! Fix those compile errors, and get the tests passing again.

Add a test where you try to add a student to a course many times, and make sure that (1) they still only appear in the course’s roster once and (2) the course only appears in their enrollments once.

Epilogue: Do unmodifiable collection views fix everything?

The answer: no!

In this activity, we fixed security flaws caused by methods returning mutable collections. But what about methods accepting mutable collections as parameters?

Consider the following code:

class Professor {
   ...
   public void setAdvisees(Set<Student> advisees) {
       // establish advisor-student relationship
       for (Student student : advisees) {
           student.setAdvisor(this);
       }
       this.advisees = advisees;  // security flaw here
   }
}

This code tries to establish an advisor-student relationship, but whoever passed in that advisees collection could hold on to it, and modify it after passing it to us:

    students.add(sally);
    susan.setAdvisees(students);
    students.add(marvin);

After this code runs, Susan will think Marvin is her advisee, but Marvin won’t think Susan is their advisor. (Why?)

Unfortunately, an unmodifiable view will not help us this time. Suppose we change the “security flaw here” line above to this:

    this.advisees = Collections.unmodifiableSet(advisees);

It doesn’t help. We’re saying, “we can’t modify the advisees list pointed to by the instance variable of Professor, but we don’t care if somebody else changes the object we were originally passed as a parameter.” And remember, unmodifiable view collections reflect changes to the underlying collection! Our unmodifiable set holds on to the set we were originally passed, and reflects changes to that original set. That means the Susan / Marvin example above fails exactly as before.

The correct solution here is to make a defensive copy, as the upcoming reading assignment discusses:

    this.advisees = new HashSet<>(advisees);

…or better yet, use the handy Set.copyOf() method, which does not make a whole new copy if the set you give it is already immutable:

    this.advisees = Set.copyOf(advisees);

What’s the essential difference between this and the getter methods you fixed above? Why do unmodifiableSet / unmodifiableList work up above when they don’t work here? That’s a good one to ponder!