Sandboxing Java Code

In a previous post, we looked at securing mobile Java code. One of the options for doing so is to run the code in a cage or sandbox.

This post explores how to set up such a sandbox for Java applications.

Security Manager

The security facility in Java that supports sandboxing is the java.lang.SecurityManager.

By default, Java runs without a SecurityManager, so you should add code to your application to enable one:

System.setSecurityManager(new SecurityManager());

You can use the standard SecurityManager, or a descendant.

The SecurityManager has a bunch of checkXXX() methods that all forward to checkPermission(permission, context). This method calls upon the AccessController to do the actual work (see below).

[The checkXXX() methods are a relic from Java 1.1.]

If a requested access is allowed, checkPermission() returns quietly. If denied, a java.lang.SecurityException is thrown.

Code that implements the sandbox should call a checkXXX method before performing a sensitive operation:

SecurityManager securityManager = System.getSecurityManager();
if (securityManager != null) {
  Permission permission = ...;
  securityManager.checkPermission(permission);
}

The JRE contains code just like that in many places.

Permissions

A permission represents access to a system resource.

In order for such access to be allowed, the corresponding permission must be explicitly granted (see below) to the code attempting the access.

Permissions derive from java.security.Permission. They have a name and an optional list of actions (in the form of comma separated string values).

Java ships with a bunch of predefined permissions, like FilePermission. You can also add your own permissions.

The following is a permission to read the file /home/remon/thesis.pdf:

Permission readPermission = new java.io.FilePermission(
    "/home/remon/thesis.pdf", "read");

You can grant a piece of code permissions to do anything and everything by granting it AllPermission. This has the same effect as running it without SecurityManager.

Policies

Permissions are granted using policies. A Policy is responsible for determining whether code has permission to perform a security-sensitive operation.

The AccessController consults the Policy to see whether a Permission is granted.

There can only be one Policy object in use at any given time. Application code can subclass Policy to provide a custom implementation.

The default implementation of Policy uses configuration files to load grants. There is a single system-wide policy file, and a single (optional) user policy file.

You can create additional policy configuration files using the PolicyTool program. Each configuration file must be encoded in UTF-8.

By default, code is granted no permissions at all. Every grant statement adds some permissions. Permissions that are granted cannot be revoked.

The following policy fragment grants code that originates from the /home/remon/code/ directory read permission to the file /home/remon/thesis.pdf:

grant codeBase "file:/home/remon/code/-" {
    permission java.io.FilePermission "/home/remon/thesis.pdf",
        "read";
};

Note that the part following codeBase is a URL, so you should always use forward slashes, even on a Windows system.

A codeBase with a trailing / matches all class files (not JAR files) in the specified directory. A codeBase with a trailing /* matches all files (both class and JAR files) contained in that directory. A codeBase with a trailing /- matches all files (both class and JAR files) in the directory and recursively all files in subdirectories contained in that directory.

For paths in file permissions on Windows systems, you need to use double backslashes (\\), since the \ is an escape character:

grant codeBase "file:/C:/Users/remon/code/-" {
    permission java.io.FilePermission
        "C:\\Users\\remon\\thesis.pdf", "read";
};

For more flexibility, you can write grants with variable parts. We already saw the codeBase wildcards. You can also substitute system properties:

grant codeBase "file:/${user.home}/code/-" {
    permission java.io.FilePermission
        "${user.home}${/}thesis.pdf", "read";
};

Note that ${/} is replaced with the path separator for your system. There is no need to use that in codeBase, since that’s a URL.

Signed Code

Of course, we should make sure that the code we use is signed, so that we know that it actually came from who we think it came from.

We can test for signatures in our policies using the signedBy clause:

keystore "my.keystore";
grant signedBy "signer.alias", codeBase ... {
  ...
};

This policy fragment uses the keystore with alias my.keystore to look up the public key certificate with alias signer.alias.

It then verifies that the executing code was signed by the private key corresponding to the public key in the found certificate.

There can be only one keystore entry.

The combination of codeBase and signedBy clauses specifies a ProtectionDomain. All classes in the same ProtectionDomain have the same permissions.

Privileged Code

Whenever a resource access is attempted, all code on the stack must have permission for that resource access, unless some code on the stack has been marked as privileged.

Marking code as privileged enables a piece of trusted code to temporarily enable access to more resources than are available directly to the code that called it. In other words, the security system will treat all callers as if they originated from the ProtectionDomain of the class that issues the privileged call, but only for the duration of the privileged call.

You make code privileged by running it inside an AccessController.doPrivileged() call:

AccessController.doPrivileged(new PrivilegedAction() {
  public Object run() {
    // ...privileged code goes here...
    return null;
  }
});

Assembling the Sandbox

Now we have all the pieces we need to assemble our sandbox:

  1. Install a SecurityManager
  2. Sign the application jars
  3. Grant all code signed by us AllPermission
  4. Add permission checks in places that mobile code may call
  5. Run the code after the permission checks in a doPrivileged() block

I’ve created a simple example on GitHub.

Signing Java Code

In a previous post, we discussed how to secure mobile code.

One of the measures mentioned was signing code. This post explores how that works for Java programs.

Digital Signatures

The basis for digital signatures is cryptography, specifically, public key cryptography. We use a set of cryptographic keys: a private and a public key.

The private key is used to sign a file and must remain a secret. The public key is used to verify the signature that was generated with the private key. This is possible because of the special mathematical relationship between the keys.

Both the signature and the public key need to be transferred to the recipient.

Certificates

In order to trust a file, one needs to verify the signature on that file. For this, one needs the public key that corresponds to the private key that was used to sign the file. So how can we trust the public key?

This is where certificates come in. A certificate contains a public key and the distinguished name that identifies the owner of that key.

The trust comes from the fact that the certificate is itself signed. So the certificate also contains a signature and the distinguished name of the signer.

When we control both ends of the communication, we can just provide both with the certificate and be done with it. This works well for mobile apps you write that connect to a server you control, for instance.

If you don’t control both ends, then we need an alternative. The distinguished name of the signer can be used to look up the signer’s certificate. With the public key from that certificate, the signature in the original certificate can be verified.

We can continue in this manner, creating a certificate chain, until we reach a signer that we explicitly trust. This is usually a well-established Certificate Authority (CA), like VeriSign or Thawte.

Keystores

In Java, private keys and certificates are stored in a password-protected database called a keystore.

Each key/certificate combination is identified by a string known as the alias.

Code Signing Tools

Java comes with two tools for code signing: keytool and jarsigner.

Use the jarsigner program to sign jar files using certificates stored in a keystore.

Use the keytool program to create private keys and the corresponding public key certificates, to retrieve/store those from/to a keystore, and to manage the keystore.

The keytool program is not capable of creating a certificate signed by someone else. It can create a Certificate Signing Request, however, that you can send to a CA. It can also import the CA’s response into the keystore.

The alternative is to use tools like OpenSSL or BSAFE, which support such CA capabilities.

Code Signing Environment

Code signing should happen in a secure environment, since private keys are involved and those need to remain secret. If a private key falls into the wrong hands, a third party could sign their code with your key, tricking your customers into trusting that code.

This means that you probably don’t want to maintain the keystore on the build machine, since that machine is likely available to many people. A more secure approach is to introduce a dedicated signing server:

You should also use different signing certificates for development and production.

Timestamping

Certificates are valid for a limited time period only. Any files signed with a private key for which the public key certificate has expired, should no longer be trusted, since it may have been signed after the certificate expired.

We can alleviate this problem by timestamping the file. By adding a trusted timestamp to the file, we can trust it even after the signing certificate expires.

But then how do we trust the timestamp? Well, by signing it using a Time Stamping Authority, of course! The OpenSSL program can help you with that as well.

Beyond Code Signing

When you sign your code, you only prove that the code came from you. For a customer to be able to trust your code, it needs to be trustworthy. You probably want to set up a full-blown Security Development Lifecycle (SDL) to make sure that it is as much as possible.

Another thing to consider in this area is third-party code. Most software packages embed commercial and/or open source libraries. Ideally, those libraries are signed by their authors. But no matter what, you need to take ownership, since customers don’t care whether a vulnerability is found in code you wrote yourself or in a library you used.

Securing Mobile Java Code

Mobile Code is code sourced from remote, possibly untrusted systems, that are executed on your local system. Mobile code is an optional constraint in the REST architectural style.

This post investigates our options for securely running mobile code in general, and for Java in particular.

Mobile Code

Examples of mobile code range from JavaScript fragments found in web pages to plug-ins for applications like FireFox and Eclipse.

Plug-ins turn a simple application into an extensible platform, which is one reason they are so popular. If you are going to support plug-ins in your application, then you should understand the security implications of doing so.

Types of Mobile Code

Mobile code comes in different forms. Some mobile code is source code, like JavaScript.

Mobile code in source form requires an interpreter to execute, like JägerMonkey in FireFox.

Mobile code can also be found in the form of executable code.

This can either be intermediate code, like Java applets, or native binary code, like Adobe’s Flash Player.

Active Content Delivers Mobile Code

A concept that is related to mobile code is active content, which is defined by NIST as

Electronic documents that can carry out or trigger actions automatically on a computer platform without the intervention of a user.

Examples of active content are HTML pages or PDF documents containing scripts and Office documents containing macros.

Active content is a vehicle for delivering mobile code, which makes it a popular technology for use in phishing attacks.

Security Issues With Mobile Code

There are two classes of security problems associated with mobile code.

The first deals with getting the code safely from the remote to the local system. We need to control who may initiate the code transfer, for example, and we must ensure the confidentiality and integrity of the transferred code.

From the point of view of this class of issues, mobile code is just data, and we can rely on the usual solutions for securing the transfer. For instance, XACML may be used to control who may initiate the transfer, and SSL/TLS may be used to protect the actual transfer.

It gets more interesting with the second class of issues, where we deal with executing the mobile code. Since the remote source is potentially untrusted, we’d like to limit what the code can do. For instance, we probably don’t want to allow mobile code to send credit card data to its developer.

However, it’s not just malicious code we want to protect ourselves from.

A simple bug that causes the mobile code to go into an infinite loop will threaten your application’s availability.

The bottom line is that if you want your application to maintain a certain level of security, then you must make sure that any third-party code meets that same standard. This includes mobile code and embedded libraries and components.

That’s why third-party code should get a prominent place in a Security Development Lifecycle (SDL).

Safely Executing Mobile Code

In general, we have four types of safeguards at our disposal to ensure the safe execution of mobile code:

  • Proofs
  • Signatures
  • Filters
  • Cages (sandboxes)

We will look at each of those in the context of mobile Java code.

Proofs

It’s theoretically possible to present a formal proof that some piece of code possesses certain safety properties. This proof could be tied to the code and the combination is then proof carrying code.

After download, the code could be checked against the code by a verifier. Only code that passes the verification check would be allowed to execute.

Updated for Bas’ comment:
Since Java 6, the StackMapTable attribute implements a limited form of proof carrying code where the type safety of the Java code is verified. However, this is certainly not enough to guarantee that the code is secure, and other approaches remain necessary.

Signatures

One of those approaches is to verify that the mobile code is made by a trusted source and that it has not been tampered with.

For Java code, this means wrapping the code in a jar file and signing and verifying the jar.

Filters

We can limit what mobile content can be downloaded. Since we want to use signatures, we should only accept jar files. Other media types, including individual .class files, can simply be filtered out.

Next, we can filter out downloaded jar files that are not signed, or signed with a certificate that we don’t trust.

We can also use anti-virus software to scan the verified jars for known malware.

Finally, we can use a firewall to filter out any outbound requests using protocols/ports/hosts that we know our code will never need. That limits what any code can do, including the mobile code.

Cages/Sandboxes

After restricting what mobile code may run at all, we should take the next step: prevent the running code from doing harm by restricting what it can do.

We can intercept calls at run-time and block any that would violate our security policy. In other words, we put the mobile code in a cage or sandbox.

In Java, cages can be implemented using the Security Manager. In a future post, we’ll take a closer look at how to do this.

Top-Down Test-Driven Development

In Test-Driven Development (TDD), I have a tendency to dive right in at the level of some class that I am sure I’m gonna need for this cool new feature that I’m working on. This has bitten me a few times in the past, where I would start bottom-up and work my way up, only to discover that the design should be a little different and the class I started out with is either not needed, or not needed in the way I envisioned. So today I wanted to try a top-down approach.

I’m running this experiment on a fresh new project that targets developers. I’m going to start with a feature that removes some of the mundane tasks of development. Specifically, when I practice TDD in Java, I start out with writing a test class. In that class, I create an instance of the Class Under Test (CUT). Since the CUT doesn’t exist at this point in time, my code doesn’t compile. So I need to create the CUT to make it compile. In Java, that consists of a couple of actions that are pretty uninteresting, but that need to be done anyway. This takes away my focus from the test, so it would be kinda cool if it somehow could be automated.

In work mostly in Eclipse, and Eclipse has the notion of Quick Fixes. So that seems like a perfect fit. However, I don’t want my project code to be completely dependent on Eclipse, if only because independent code is easier to test.

So I start out with a top-down test that shows how all of this is accomplished:

public class FixesFactoryTest {

  @Test
  public void missingClassUnderTest() {
    FixesFactory fixesFactory = new FixesFactory();
    Issues issues = new Issues().add(Issue
        .newProblem(new MissingType(new FullyQualifiedName("Bar")))
        .at(new FileLocation(
            new Path("src/test/java/com/acme/foo/BarTest.java"),
            new FilePosition(new LineNumber(11), new ColumnNumber(5)))));
    Fixes fixes = fixesFactory.newInstance(issues);

    Assert.assertNotNull("Missing fixes", fixes);
    Assert.assertEquals("# Fixes", 1, fixes.size());

    Fix fix = fixes.iterator().next();
    Assert.assertNotNull("Missing fix", fix);
    Assert.assertEquals("Fix", CreateClassFix.class, fix.getClass());

    CreateClassFix createClassFix = (CreateClassFix) fix;
    Assert.assertEquals("Name of new class", new FullyQualifiedName("com.acme.foo.Bar"),
        createClassFix.nameOfClass());
    Assert.assertEquals("Path of new class", new Path("src/main/java/com/acme/foo/Bar.java"),
        createClassFix.pathOfClass());
  }

}

This test captures my intented design: a FixesFactory gives Fixes for Issues, where an Issue is a Problem at a given Location. This will usually be a FileLocation, but I envision there could be problems between files as well, like a test class whose name doesn’t match the name of its CUT. For this particular issue, I expect one fix: to create the missing CUT at the right place.

I’m trying to follow the rules of Object Calistenics here, hence the classes like LineNumber where one may have expected a simple int. Partly because of that, I need a whole bunch of classes and methods before I can get this test to even compile. This feels awkward, because it’s too big a step for my taste. I want my green bar!

Obviously, I can’t make this pass with a few lines of code. So I add a @Ignore to this test, and shift focus to one of the smaller classes. Let’s see, LineNumber is a good candidate. I have no clue as to how I’ll be using this class, though. All I know at this point, is that it should be a value object:

public class LineNumberTest {

  @Test
  public void valueObject() {
    LineNumber lineNumber1a = new LineNumber(313);
    LineNumber lineNumber1b = new LineNumber(313);
    LineNumber lineNumber2 = new LineNumber(42);

    Assert.assertTrue("1a == 1b", lineNumber1a.equals(lineNumber1b));
    Assert.assertFalse("1a == 2", lineNumber1a.equals(lineNumber2));

    Assert.assertTrue("# 1a == 1b", lineNumber1a.hashCode() == lineNumber1b.hashCode());
    Assert.assertFalse("# 1a == 2", lineNumber1a.hashCode() == lineNumber2.hashCode());

    Assert.assertEquals("1a", "313", lineNumber1a.toString());
    Assert.assertEquals("1b", "313", lineNumber1b.toString());
    Assert.assertEquals("2", "42", lineNumber2.toString());
  }

}

This is very easy to implement in Eclipse: just select the Quick Fix to Assign Parameter To Field on the constructor’s single parameter and then select Generate hashCode() and equals()…:

public class LineNumber {

  private final int lineNumber;

  public LineNumber(int lineNumber) {
    this.lineNumber = lineNumber;
  }

  @Override
  public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + lineNumber;
    return result;
  }

  @Override
  public boolean equals(Object obj) {
    if (this == obj) {
      return true;
    }
    if (obj == null) {
      return false;
    }
    if (getClass() != obj.getClass()) {
      return false;
    }
    LineNumber other = (LineNumber) obj;
    if (lineNumber != other.lineNumber) {
      return false;
    }
    return true;
  }

}

This is not the world’s most elegant code, so we’ll refactor this once we’re green. But first we need to add the trivial toString():

  @Override
  public String toString() {
    return Integer.toString(lineNumber);
  }

And we’re green.

EclEmma tells me that some code in LineNumber.equals() is not covered. I can easily fix that by removing the if statements. But the remainder should clearly be refactored, and so should hashCode():

  @Override
  public int hashCode() {
    return 31 + lineNumber;
  }

  @Override
  public boolean equals(Object object) {
    LineNumber other = (LineNumber) object;
    return lineNumber == other.lineNumber;
  }

The other classes are pretty straightforward as well. The only issue I ran into was a bug in EclEmma when I changed an empty class to an interface. But I can work around that by restarting Eclipse.

If you are interested to see where this project is going, feel free to take a look at SourceForge. Maybe you’d even like to join in!

Retrospective

So what does this exercise teach me? I noted earlier that it felt awkward to be writing a big test that I can’t get to green. But I now realize that I felt that way because I’ve trained myself to be thinking about getting to green quickly. After all, that was always the purpose of writing a test.

But it wasn’t this time. This time it was really about writing down the design. That part I usually did in my head, or on a piece of paper or whiteboard before I would write my first test. By writing the design down as a test, I’m making it more concrete than UML could ever hope to be. So that’s definitely a win from my perspective.

The other thing I noted was not so good: I set out to write a top-down test, yet I didn’t. I didn’t start at the bottom either, but somewhere in the middle. I was quick to dismiss the Eclipse part, because I wanted at least part of the code to be independent from Eclipse. Instead, I should have coded all of that up in a test. That would have forced me to consider whether I can actually make the design work in an Eclipse plug-in. So I guess I have to practice a bit more at this top-down TDD stuff…

Bowling Again

It’s been a while since I’ve done the bowling game scoring exercise. For those of you who don’t know it, the bowling game (ten-pin) is almost the Hello, world! of TDD. I want to learn Groovy, but I’m going to re-do it in Java first, so that I have recent code and feelings to compare when I sink my teeth in Groovy.

Here’s the goal for this exercise: write a program that can score a bowling game. Inputs are the rolls, output the score.

The first thing to note is that the inputs are rolls (number of pins knocked down), while the score depends on frames. A frame consists of up to two rolls: if the first roll knocks all 10 pins down, then we’re talking about a strike and the frame consist of just the one roll. Otherwise, the frame consists of two rolls. If the second roll knocks down all pins, the frame is called a spare, else it’s a regular frame. The only exception is the last frame. If that is a strike or a spare, it will consist of three rolls. We call those bonus frames.

Frames

So our first task is to distinguish the several types of frames. Let’s start simple, with a regular frame:

public class RegularFrameTest {

  @Test
  public void frame() {
    final Frame frame = new RegularFrame(2, 5);
    Assert.assertEquals("# rolls", 2, frame.numRolls());
    Assert.assertEquals("First", 2, frame.pins(0));
    Assert.assertEquals("Second", 5, frame.pins(1));
  }

}

This forces me to write the Frame interface:

public interface Frame {

  int numRolls();
  int pins(int index);

}

The implementation is straightforward:

public class RegularFrame implements Frame {

  private final int first;
  private final int second;

  public RegularFrame(final int first, final int second) {
    this.first = first;
    this.second = second;
  }

  @Override
  public int numRolls() {
    return 2;
  }

  @Override
  public int pins(final int index) {
    return index == 0 ? first : second;
  }

}

Now, let’s do a spare:

public class SpareTest {

  @Test
  public void frame() {
    final Frame frame = new Spare(3);
    Assert.assertEquals("# rolls", 2, frame.numRolls());
    Assert.assertEquals("First", 3, frame.pins(0));
    Assert.assertEquals("Second", 7, frame.pins(1));
  }

}

Again, pretty easy:

public class Spare implements Frame {

  private final int first;

  public Spare(final int first) {
    this.first = first;
  }

  @Override
  public int numRolls() {
    return 2;
  }

  @Override
  public int pins(final int index) {
    return index == 0 ? first : 10 - first;
  }

}

OK, so by now, strike should be familiar territory:

public class StrikeTest {

  @Test
  public void frame() {
    final Frame frame = new Strike();
    Assert.assertEquals("# rolls", 1, frame.numRolls());
    Assert.assertEquals("first", 10, frame.pins(0));
  }

}
public class Strike implements Frame {

  @Override
  public int numRolls() {
    return 1;
  }

  @Override
  public int pins(final int index) {
    return 10;
  }

}

And finally, the bonus frame:

public class BonusFrameTest {

  @Test
  public void frame() {
    final Frame frame = new BonusFrame(10, 3, 5);
    Assert.assertEquals("# rolls", 3, frame.numRolls());
    Assert.assertEquals("first", 10, frame.pins(0));
    Assert.assertEquals("second", 3, frame.pins(1));
    Assert.assertEquals("third", 5, frame.pins(2));
  }

}
public class BonusFrame implements Frame {

  private final int first;
  private final int second;
  private final int third;

  public BonusFrame(final int first, final int second, final int third) {
    this.first = first;
    this.second = second;
    this.third = third;
  }

  @Override
  public int numRolls() {
    return 3;
  }

  @Override
  public int pins(final int index) {
    switch (index) {
      case 0: return first;
      case 1: return second;
      default: return third;
    }
  }

}

Note that I never bothered to specify what pins should return for an invalid index.

Now, there is a lot of duplication in these classes, so let’s extract a common base class. First, I’m going to focus on BonusFrame, since that one has the most code.

I’m going to take baby steps, keeping the code green as much as possible. First, I introduce a list to hold the three separate values:

public class BonusFrame implements Frame {

  private final List<Integer> pins = new ArrayList<Integer>();

  public BonusFrame(final int first, final int second, final int third) {
    this.first = first;
    this.second = second;
    this.third = third;
    pins.add(first);
    pins.add(second);
    pins.add(third);
  }

  // ...
}

Next, I implement numRolls using the new list:

public class BonusFrame implements Frame {

  @Override
  public int numRolls() {
    return pins.size();
  }

  // ...
}

Then the pins method:

public class BonusFrame implements Frame {

  @Override
  public int pins(final int index) {
    return pins.get(index);
  }

  // ...
}

Now the original fields are unused, and I can delete them safely. Never in this refactoring did I break the tests, not even for a second.

The second stage of this refactoring is to extract a base class that will hold the list of pins. Since the constructor is using the fields, I need to change it slightly, so that I can safely move the list. First I’ll introduce a new constructor that accepts a list of pins:

public class BonusFrame implements Frame {

  protected BonusFrame(final List<Integer> pins) {
    this.pins.addAll(pins);
  }

  // ..
}

Then I change the original constructor to call the new one:

public class BonusFrame implements Frame {

  public BonusFrame(final int first, final int second, final int third) {
    this(Arrays.asList(first, second, third));
  }

  // ...
}

Now I can do an automated Extract Superclass refactoring to get my coveted base class:

public class BonusFrame extends BaseFrame implements Frame {

  public BonusFrame(final int first, final int second, final int third) {
    this(Arrays.asList(first, second, third));
  }

  protected BonusFrame(final List<Integer> pins) {
    this.pins.addAll(pins);
  }

}

Unfortunately, there is no way to have Eclipse also move the constructor that I had prepared 😦 Also, the BaseFrame class doesn’t implement Frame yet:

public class BaseFrame {

  protected final List<Integer> pins = new ArrayList<Integer>();

  public BaseFrame() {
    super();
  }

  @Override
  public int numRolls() {
    return pins.size();
  }

  @Override
  public int pins(final int index) {
    return pins.get(index);
  }

}

This is bad, since now the code doesn’t even compile anymore, thanks to the @Override! Let’s add the missing implements, so we’re back to green. The public no-arg constructor can also go, it will be generated for us.

Now to clean up the mess. Eclipse doesn’t offer to Pull Up constructors, which is a shame. So let’s move it by hand:

public class BonusFrame extends BaseFrame implements Frame {

  public BonusFrame(final int first, final int second, final int third) {
    super(Arrays.asList(first, second, third));
  }

}
public class BaseFrame implements Frame {

  protected BaseFrame(final List<Integer> pins) {
    this.pins.addAll(pins);
  }

  // ...
}

The list should be private, and the implements Frame on BonusFrame can go.

We can now use BaseFrame as a base class for the other classes as wel:

public class Strike extends BaseFrame {

  public Strike() {
    super(Arrays.asList(10));
  }

}
public class Spare extends BaseFrame {

  public Spare(final int first) {
    super(Arrays.asList(first, 10 - first));
  }

}
public class RegularFrame extends BaseFrame {

  public RegularFrame(final int first, final int second) {
    super(Arrays.asList(first, second));
  }

}

I’m happy with the result, so let’s move on.

From Rolls To Frames

Now that we have the different kinds of frames in place, we need a way to create them from the rolls that are our input. We basically need to convert a series of rolls into a series of frames. This series idea we can capture in an Iterator:

public class FrameIteratorTest {

  @Test
  public void regular() {
    final Iterator<Frame> frames = new FrameIterator(Arrays.asList(1, 2));
    Assert.assertTrue("Missing frame", frames.hasNext());

    final Frame frame = frames.next();
    Assert.assertEquals("Frame", new RegularFrame(1, 2), frame);
    Assert.assertFalse("Extra frame", frames.hasNext());
  }

}

But for this to work, we need to implement equals on BaseFrame:

public class BaseFrameTest {

  @Test
  public void equality() {
    final Frame frame1 = new BaseFrame(Arrays.asList(4, 2));
    Assert.assertTrue("Same", frame1.equals(new BaseFrame(Arrays.asList(4, 2))));
    Assert.assertFalse("Different", frame1.equals(new BaseFrame(Arrays.asList(2, 4))));
  }

}

This is easy to implement, since Eclipse can generate the equals and hashCode for us:

public class BaseFrame implements Frame {

  @Override
  public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + ((pins == null) ? 0 : pins.hashCode());
    return result;
  }

  @Override
  public boolean equals(final Object obj) {
    if (this == obj) {
      return true;
    }
    if (obj == null) {
      return false;
    }
    if (getClass() != obj.getClass()) {
      return false;
    }
    final BaseFrame other = (BaseFrame) obj;
    if (pins == null) {
      if (other.pins != null) {
        return false;
      }
    } else if (!pins.equals(other.pins)) {
      return false;
    }
    return true;
  }

  // ...
}

Now we can return to our FrameIterator:

public class FrameIterator implements Iterator<Frame> {

  private final Iterator<Integer> rolls;

  public FrameIterator(final List<Integer> rolls) {
    this.rolls = rolls.iterator();
  }

  @Override
  public boolean hasNext() {
    return rolls.hasNext();
  }

  @Override
  public Frame next() {
    final int first = rolls.next();
    final int second = rolls.next();
    return new RegularFrame(first, second);
  }

  @Override
  public void remove() {
    throw new UnsupportedOperationException();
  }

}

OK, so how about a spare?

public class FrameIteratorTest {

  @Test
  public void spare() {
    final Iterator<Frame> frames = new FrameIterator(Arrays.asList(8, 2));
    Assert.assertTrue("Missing frame", frames.hasNext());

    final Frame frame = frames.next();
    Assert.assertEquals("Frame", new Spare(8), frame);
  }

  // ...
}
public class FrameIterator implements Iterator<Frame> {

  @Override
  public Frame next() {
    final int first = rolls.next();
    final int second = rolls.next();
    final Frame result;
    if (first + second == 10) {
      result = new Spare(first);
    } else {
      result = new RegularFrame(first, second);
    }
    return result;
  }

  // ...
}

OK, then a strike shouldn’t be too hard:

public class FrameIteratorTest {

  @Test
  public void strike() {
    final Iterator<Frame> frames = new FrameIterator(Arrays.asList(10));
    Assert.assertTrue("Missing frame", frames.hasNext());

    final Frame frame = frames.next();
    Assert.assertEquals("Frame", new Strike(), frame);
  }

  // ...
}

This test doesn’t just fail, but it throws a NoSuchElementException, since we only provide one roll. Not too hard to fix, though:

public class FrameIterator implements Iterator<Frame> {

  @Override
  public Frame next() {
    final Frame result;
    final int first = rolls.next();
    if (first == 10) {
      result = new Strike();
    } else {
      final int second = rolls.next();
      if (first + second == 10) {
        result = new Spare(first);
      } else {
        result = new RegularFrame(first, second);
      }
    }
    return result;
  }

  // ...
}

OK, that works, but the code is a bit messy. Not only do we have a magic constant, we now have it in two places! So let’s get rid of that:

public class FrameIterator implements Iterator<Frame> {

  private static final int PINS_PER_LANE = 10;

  @Override
  public Frame next() {
    final Frame result;
    final int first = rolls.next();
    if (isAllDown(first)) {
      result = new Strike();
    } else {
      final int second = rolls.next();
      if (isAllDown(first + second)) {
        result = new Spare(first);
      } else {
        result = new RegularFrame(first, second);
      }
    }
    return result;
  }

  private boolean isAllDown(final int pins) {
    return pins == PINS_PER_LANE;
  }

  // ...
}

I’m still not all that happy with this code, although I guess it does state the rules quite clearly now. Maybe the messyness of the code follows the messyness of the rules? I dont know, so let’s let our background processor think that over some more while I continue.

We now have all the normal frames in place, but we still lack the bonus frames. First a spare:

public class FrameIteratorTest {

  @Test
  public void bonusSpare() {
    final Iterator<Frame> frames = new FrameIterator(Arrays.asList(10, 10, 10, 10, 10, 10, 10, 10, 10, 2, 8, 3));
    for (int i = 0; i < 9; i++) {
      Assert.assertTrue("Missing frame " + i, frames.hasNext());

      final Frame frame = frames.next();
      Assert.assertEquals("Frame " + i, new Strike(), frame);
    }

    Assert.assertTrue("Missing bonus frame", frames.hasNext());

    final Frame frame = frames.next();
    Assert.assertEquals("Bonus frame", new BonusFrame(2, 8, 3), frame);
  }

  // ...
}
public class FrameIterator implements Iterator<Frame> {

  private static final int NUM_FRAMES_PER_GAME = 10;

  private int numFrames;

  @Override
  public Frame next() {
    numFrames++;
    final Frame result;
    final int first = rolls.next();
    if (isAllDown(first)) {
      result = new Strike();
    } else {
      final int second = rolls.next();
      if (isAllDown(first + second)) {
        if (isFinalFrame()) {
          result = new BonusFrame(first, second, rolls.next());
        } else {
          result = new Spare(first);
        }
      } else {
        result = new RegularFrame(first, second);
      }
    }
    return result;
  }

  private boolean isFinalFrame() {
    return numFrames == NUM_FRAMES_PER_GAME;
  }

  // ...
}

And then the strike:

public class FrameIteratorTest {

  @Test
  public void bonusStrike() {
    final Iterator<Frame> frames = new FrameIterator(Arrays.asList(10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 7, 2));
    for (int i = 0; i < 9; i++) {
      Assert.assertTrue("Missing frame " + i, frames.hasNext());

      final Frame frame = frames.next();
      Assert.assertEquals("Frame " + i, new Strike(), frame);
    }

    Assert.assertTrue("Missing bonus frame", frames.hasNext());

    final Frame frame = frames.next();
    Assert.assertEquals("Bonus frame", new BonusFrame(10, 7, 2), frame);
  }

  // ...
}
public class FrameIterator implements Iterator<Frame> {

  @Override
  public Frame next() {
    numFrames++;
    final Frame result;
    final int first = rolls.next();
    if (isAllDown(first)) {
      if (isFinalFrame()) {
        final int second = rolls.next();
        result = new BonusFrame(first, second, rolls.next());
      } else {
        result = new Strike();
      }
    } else {
      final int second = rolls.next();
      if (isAllDown(first + second)) {
        if (isFinalFrame()) {
          result = new BonusFrame(first, second, rolls.next());
        } else {
          result = new Spare(first);
        }
      } else {
        result = new RegularFrame(first, second);
      }
    }
    return result;
  }

  // ...
}

OK, now we really have to simplify the code! Let’s extract all the strike and spare stuff:

public class FrameIterator implements Iterator<Frame> {

  @Override
  public Frame next() {
    numFrames++;
    final Frame result;
    final int first = rolls.next();
    if (isAllDown(first)) {
      result = newStrike(first);
    } else {
      final int second = rolls.next();
      if (isAllDown(first + second)) {
        result = newSpare(first, second);
      } else {
        result = new RegularFrame(first, second);
      }
    }
    return result;
  }

  private Frame newStrike(final int first) {
    final Frame result;
    if (isFinalFrame()) {
      final int second = rolls.next();
      result = new BonusFrame(first, second, rolls.next());
    } else {
      result = new Strike();
    }
    return result;
  }

  private Frame newSpare(final int first, final int second) {
    final Frame result;
    if (isFinalFrame()) {
      result = new BonusFrame(first, second, rolls.next());
    } else {
      result = new Spare(first);
    }
    return result;
  }

  // ...
}

I think I could further simplify the code by refactoring to a Strategy pattern and then do a Replace Conditional With Polymorphism to get rid of all those pesky if statements. But although that would make the individual methods easier to read, we would lose the overview, and it may just make the rules harder to retrieve from the code. So, I’m inclined to leave it as it is.

On to scoring then!

Scoring

This is where the fun begins.

The basic score for a frame is just the number of pins that were knocked down:

public class BaseFrameTest {

  @Test
  public void baseScore() {
    final Frame frame = new BaseFrame(Arrays.asList(3, 6));
    Assert.assertEquals("Base score", 9, frame.getBaseScore());
  }

  // ...
}
public interface Frame {

  int getBaseScore();

  // ...
}
public class BaseFrame implements Frame {

  @Override
  public int getBaseScore() {
    int result = 0;
    for (final int pins : this.pins) {
      result += pins;
    }
    return result;
  }

  // ...
}

Writing that only now makes me realize that I named the list of rolls pins. But it’s not the pins knocked down, but the list of pins per roll that were knocked down:

public class BaseFrame implements Frame {

  private final List<Integer> rolls = new ArrayList<Integer>();

  protected BaseFrame(final List<Integer> rolls) {
    this.rolls.addAll(rolls);
  }

  @Override
  public int numRolls() {
    return rolls.size();
  }

  @Override
  public int pins(final int index) {
    return rolls.get(index);
  }

  @Override
  public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + ((rolls == null) ? 0 : rolls.hashCode());
    return result;
  }

  @Override
  public boolean equals(final Object obj) {
    if (this == obj) {
      return true;
    }
    if (obj == null) {
      return false;
    }
    if (getClass() != obj.getClass()) {
      return false;
    }
    final BaseFrame other = (BaseFrame) obj;
    if (rolls == null) {
      if (other.rolls != null) {
        return false;
      }
    } else if (!rolls.equals(other.rolls)) {
      return false;
    }
    return true;
  }

  @Override
  public int getBaseScore() {
    int result = 0;
    for (final int pins : rolls) {
      result += pins;
    }
    return result;
  }

}

Now, that was the easy part of scoring. Apart from the base score, strikes and spares also have extra scores. We don’t want to deal with exceptions, though. That will just lead to code littered with if statements. Instead, we can use polymorphism and the Null Object pattern:

public class BaseFrameTest {

  @Test
  public void extraScore() {
    final Frame frame = new BaseFrame(Arrays.asList(3, 4));
    Assert.assertTrue("Extra score", frame.getExtraScore() instanceof NoExtraScore);
  }

  // ...
}
public interface Frame {

  ExtraScore getExtraScore();

  // ...
}
public interface ExtraScore {

}
public class NoExtraScore implements ExtraScore {

}

Note that the ExtraScore interface is empty for now. We will get to that in a minute. First let’s make the test pass:

public class BaseFrame implements Frame {

  @Override
  public ExtraScore getExtraScore() {
    return new NoExtraScore();
  }

  // ...
}

For spares, the extra score is one roll:

public class SpareTest {

  @Test
  public void extraScore() {
    final Frame frame = new Spare(4);
    Assert.assertTrue("Extra score", frame.getExtraScore() instanceof OneRollExtraScore);
  }

  // ...
}
public class OneRollExtraScore implements ExtraScore {

}
public class Spare extends BaseFrame {

  @Override
  public ExtraScore getExtraScore() {
    return new OneRollExtraScore();
  }

  // ...
}

For strikes, the extra score is two rolls:

public class StrikeTest {

  @Test
  public void extraScore() {
    final Frame frame = new Strike();
    Assert.assertTrue("Extra score", frame.getExtraScore() instanceof TwoRollsExtraScore);
  }

  // ...
}
public class TwoRollsExtraScore implements ExtraScore {

}
public class Strike extends BaseFrame {

  @Override
  public ExtraScore getExtraScore() {
    return new TwoRollsExtraScore();
  }

  // ...
}

Allright, what about that ExtraScore interface? We don’t want to go back to dealing with rolls, since we have our lovely FrameIterator that gives us frames. So the extra score must deal with frames. First, it must tells us whether it needs any at all:

public class NoExtraScoreTest {

  @Test
  public void needFrame() {
    final ExtraScore extraScore = new NoExtraScore();
    Assert.assertFalse("Need more", extraScore.needFrame());
  }

}
public interface ExtraScore {

  boolean needFrame();

}
public class NoExtraScore implements ExtraScore {

  @Override
  public boolean needFrame() {
    return false;
  }

}

We have a little bit more work for the one roll extra score:

public class OneRollExtraScoreTest {

  @Test
  public void extraScore() {
    final ExtraScore extraScore = new OneRollExtraScore();
    Assert.assertTrue("Need more", extraScore.needFrame());

    final Frame frame = new RegularFrame(3, 4);
    final int score = extraScore.getScore(frame);
    Assert.assertEquals("Extra score", 3, score);
    Assert.assertFalse("Need still more", extraScore.needFrame());
  }

}
public interface ExtraScore {

  int getScore(Frame frame);

  // ...
}
public class OneRollExtraScore implements ExtraScore {

  private boolean needMore = true;

  @Override
  public boolean needFrame() {
    return needMore;
  }

  @Override
  public int getScore(final Frame frame) {
    needMore = false;
    return frame.pins(0);
  }

}

And the extra score for a strike is the most complex:

public class TwoRollsExtraScoreTest {

  @Test
  public void regular() {
    final ExtraScore extraScore = new TwoRollsExtraScore();
    Assert.assertTrue("Need more", extraScore.needFrame());

    final Frame frame = new RegularFrame(6, 3);
    final int score = extraScore.getScore(frame);
    Assert.assertEquals("Extra score", 9, score);
    Assert.assertFalse("Still need more", extraScore.needFrame());
  }

  @Test
  public void strike() {
    final ExtraScore extraScore = new TwoRollsExtraScore();
    Assert.assertTrue("Need more", extraScore.needFrame());

    Frame frame = new Strike();
    int score = extraScore.getScore(frame);
    Assert.assertEquals("Extra score", 10, score);
    Assert.assertTrue("Still need more", extraScore.needFrame());

    frame = new RegularFrame(6, 3);
    score = extraScore.getScore(frame);
    Assert.assertEquals("Extra score 2", 6, score);
    Assert.assertFalse("Still need more 2", extraScore.needFrame());
  }

}
public class TwoRollsExtraScore implements ExtraScore {

  private int numNeeded = 2;

  @Override
  public boolean needFrame() {
    return numNeeded > 0;
  }

  @Override
  public int getScore(final Frame frame) {
    int result = 0;
    final int numGotten = Math.min(numNeeded, frame.numRolls());
    for (int i = 0; i < numGotten; i++) {
      result += frame.pins(i);
    }
    numNeeded -= numGotten;
    return result;
  }

}

Now we need to glue all the previous together to calculate the game’s score:

public class FramesScorerTest {

  @Test
  public void score() {
    final FramesScorer scorer = new FramesScorer();
    Frame frame = new FakeFrame(2);
    scorer.add(frame);
    Assert.assertEquals("Score", 9, scorer.getScore());

    List<ExtraScore> extraScores = scorer.getExtraScores();
    Assert.assertNotNull("Missing extra scores", extraScores);
    Assert.assertEquals("# Extra scores", 1, extraScores.size());
    Assert.assertTrue("Extra score", extraScores.get(0) instanceof FakeExtraScore);

    frame = new FakeFrame(1);
    scorer.add(frame);
    Assert.assertEquals("Score 2", 19, scorer.getScore());
    extraScores = scorer.getExtraScores();
    Assert.assertEquals("# Extra scores 2", 2, extraScores.size());

    frame = new FakeFrame(0);
    scorer.add(frame);
    Assert.assertEquals("Score 3", 30, scorer.getScore());
    extraScores = scorer.getExtraScores();
    Assert.assertEquals("# Extra scores 3", 3, extraScores.size());

    scorer.add(frame);
    Assert.assertEquals("Score 4", 41, scorer.getScore());
    extraScores = scorer.getExtraScores();
    Assert.assertEquals("# Extra scores 4", 3, extraScores.size());
  }


  private static class FakeFrame extends BaseFrame {

    protected FakeFrame(final int pins) {
      super(Arrays.asList(pins, 9 - pins));
    }

    @Override
    public ExtraScore getExtraScore() {
      return new FakeExtraScore(pins(0));
    }

  }


  private static class FakeExtraScore implements ExtraScore {

    private final int numNeeded;

    public FakeExtraScore(final int numNeeds) {
      numNeeded = numNeeds;
    }

    @Override
    public boolean needFrame() {
      return numNeeded  > 0;
    }

    @Override
    public int getScore(final Frame frame) {
      return 1;
    }

  }

}

This test is a lot more involved than normal, and it took some time to get it right. This is because it’s really the sequence of steps that we want to test, as all the individual steps are already tested.

Let’s implement this assert by assert. First, the base score:

public class FramesScorer {

  private int score;

  public void add(final Frame frame) {
    score += frame.getBaseScore();
  }

  public int getScore() {
    return score;
  }

  public List<ExtraScore> getExtraScores() {
    return null;
  }

}

Next, we need to remember the extra score object:

public class FramesScorer {

  private final List<ExtraScore> extraScores = new ArrayList<ExtraScore>();

  public void add(final Frame frame) {
    score += frame.getBaseScore();
    extraScores.add(frame.getExtraScore());
  }

  public List<ExtraScore> getExtraScores() {
    return extraScores;
  }

  // ...
}

Then we need to add the collected extra scores:

public class FramesScorer {

  public void add(final Frame frame) {
    score += frame.getBaseScore();
    final Iterator<ExtraScore> iterator = extraScores.listIterator();
    while (iterator.hasNext()) {
      final ExtraScore extraScore = iterator.next();
      score += extraScore.getScore(frame);
    }
    extraScores.add(frame.getExtraScore());
  }

  // ...
}

And we must not forget to remove extra scores that are done:

public class FramesScorer {

  public void add(final Frame frame) {
    score += frame.getBaseScore();
    final Iterator<ExtraScore> iterator = extraScores.listIterator();
    while (iterator.hasNext()) {
      final ExtraScore extraScore = iterator.next();
      if (extraScore.needFrame()) {
        score += extraScore.getScore(frame);
      } else {
        iterator.remove();
      }
    }
    extraScores.add(frame.getExtraScore());
  }

  // ...
}

Actually, the way I implemented this puts the ExtraScore object on the list even if it is a NoExtraScore object, which seems a bit wasteful. So let’s fix that:

public class FramesScorerTest {

  @Test
  public void score() {
    final FramesScorer scorer = new FramesScorer();
    Frame frame = new FakeFrame(2);
    scorer.add(frame);
    Assert.assertEquals("Score", 9, scorer.getScore());

    List<ExtraScore> extraScores = scorer.getExtraScores();
    Assert.assertNotNull("Missing extra scores", extraScores);
    Assert.assertEquals("# Extra scores", 1, extraScores.size());
    Assert.assertTrue("Extra score", extraScores.get(0) instanceof FakeExtraScore);

    frame = new FakeFrame(1);
    scorer.add(frame);
    Assert.assertEquals("Score 2", 19, scorer.getScore());
    extraScores = scorer.getExtraScores();
    Assert.assertEquals("# Extra scores 2", 2, extraScores.size());

    frame = new FakeFrame(0);
    scorer.add(frame);
    Assert.assertEquals("Score 3", 30, scorer.getScore());
    extraScores = scorer.getExtraScores();
    Assert.assertEquals("# Extra scores 3", 2, extraScores.size());

    scorer.add(frame);
    Assert.assertEquals("Score 4", 41, scorer.getScore());
    extraScores = scorer.getExtraScores();
    Assert.assertEquals("# Extra scores 4", 2, extraScores.size());
  }

  // ...
}
public class FramesScorer {

  public void add(final Frame frame) {
    score += frame.getBaseScore();
    final Iterator<ExtraScore> iterator = extraScores.listIterator();
    while (iterator.hasNext()) {
      final ExtraScore extraScore = iterator.next();
      score += extraScore.getScore(frame);
      if (!extraScore.needFrame()) {
        iterator.remove();
      }
    }

    final ExtraScore extraScore = frame.getExtraScore();
    if (extraScore.needFrame()) {
      extraScores.add(extraScore);
    }
  }

  //  ...
}

Now we need to clean this up a bit:

public class FramesScorer {

  private int score;
  private final List<ExtraScore> extraScores = new ArrayList<ExtraScore>();

  public void add(final Frame frame) {
    score += frame.getBaseScore() + extraScore(frame);
    rememberExtraScore(frame);
  }

  private int extraScore(final Frame frame) {
    int result = 0;
    final Iterator<ExtraScore> iterator = extraScores.listIterator();
    while (iterator.hasNext()) {
      final ExtraScore extraScore = iterator.next();
      result += extraScore.getScore(frame);
      if (!extraScore.needFrame()) {
        iterator.remove();
      }
    }
    return result;
  }

  private void rememberExtraScore(final Frame frame) {
    final ExtraScore extraScore = frame.getExtraScore();
    if (extraScore.needFrame()) {
      extraScores.add(extraScore);
    }
  }

  // ...
}

All that’s left to do, is collect the rolls and provide them to the scorer. First the collecting:

public class GameTest {

  @Test
  public void rolls() {
    final Game game = new Game();
    game.roll(3);
    game.roll(1);
    game.roll(3);
    Assert.assertEquals("Rolls", Arrays.asList(3, 1, 3), game.getRolls());
  }

}
public class Game {

  private final List<Integer> rolls = new ArrayList<Integer>();

  public void roll(final int pins) {
    rolls.add(pins);
  }

  protected List<Integer> getRolls() {
    return rolls;
  }

}

And finally the glue that ties the scoring together:

public class GameTest {

  @Test
  public void score() {
    final Game game = new Game();
    game.roll(1);
    game.roll(1);
    game.roll(1);
    game.roll(1);
    game.roll(1);
    game.roll(1);
    game.roll(1);
    game.roll(1);
    game.roll(1);
    game.roll(1);
    game.roll(1);
    game.roll(1);
    game.roll(1);
    game.roll(1);
    game.roll(1);
    game.roll(1);
    game.roll(1);
    game.roll(1);
    game.roll(1);
    game.roll(1);
    Assert.assertEquals("Score", 20, game.getScore());
  }

}
public class Game {

  public int getScore() {
    final FramesScorer scorer = new FramesScorer();
    final FrameIterator frames = new FrameIterator(getRolls());
    while (frames.hasNext()) {
      scorer.add(frames.next());
    }
    return scorer.getScore();
  }

  // ...
}

I’m confident that the code works, but let’s make sure by adding some tests with well-known answers:

public class GameTest {

  @Test
  public void perfect() {
    final Game game = new Game();
    game.roll(10);
    game.roll(10);
    game.roll(10);
    game.roll(10);
    game.roll(10);
    game.roll(10);
    game.roll(10);
    game.roll(10);
    game.roll(10);
    game.roll(10);
    game.roll(10);
    game.roll(10);
    Assert.assertEquals("Score", 300, game.getScore());
  }

  @Test
  public void alternateStrikesAndSpares() {
    final Game game = new Game();
    for (int i = 0; i < 5; i++) {
      game.roll(10);
      game.roll(4);
      game.roll(6);
    }
    game.roll(10);
    Assert.assertEquals("Score", 200, game.getScore());
  }

}

All green, so I guess we’re done!

Reflection

Let’s take another look at all the code to see if there is anything that needs some more attention.

One thing I notice, is that the code for TwoRollsExtraScore is a generalization for the other extra scores, so we could extract a base class. First, I introduce a constructor to set the private field:

public class TwoRollsExtraScore implements ExtraScore {

  private int numNeeded;

  public TwoRollsExtraScore() {
    this(2);
  }

  protected TwoRollsExtraScore(final int numNeeded) {
    this.numNeeded = numNeeded;
  }

  // ...
}

Then use Extract Superclass (again with manual cleanup of the errors that Eclipse introduces):

public class TwoRollsExtraScore extends BaseExtraScore {

  public TwoRollsExtraScore() {
    super(2);
  }

}
public class BaseExtraScore implements ExtraScore {

  private int numNeeded;

  protected BaseExtraScore(final int numNeeded) {
    this.numNeeded = numNeeded;
  }

  @Override
  public boolean needFrame() {
    return numNeeded > 0;
  }

  @Override
  public int getScore(final Frame frame) {
    int result = 0;
    final int numGotten = Math.min(numNeeded, frame.numRolls());
    for (int i = 0; i < numGotten; i++) {
      result += frame.pins(i);
    }
    numNeeded -= numGotten;
    return result;
  }

}

And now we can use the base class to derive the other extra score classes from:

public class OneRollExtraScore extends BaseExtraScore {

  protected OneRollExtraScore() {
    super(1);
  }

}
public class NoExtraScore extends BaseExtraScore {

  protected NoExtraScore() {
    super(0);
  }

}

With that little code in the classes, one may wonder wether they are still pulling their weight. I like to think so, since they express the concepts in the game well. I introduced them because of that, after all. So I’m keeping them.

I also find a “bug” in FakeExtraScore: the numNeeded field is never decreased, so basically it will always keep requesting new frames. Here’s the fix:

public class FramesScorerTest {

  @Test
  public void score() {
    final FramesScorer scorer = new FramesScorer();
    Frame frame = new FakeFrame(2);
    scorer.add(frame);
    Assert.assertEquals("Score", 9, scorer.getScore());

    List<ExtraScore> extraScores = scorer.getExtraScores();
    Assert.assertNotNull("Missing extra scores", extraScores);
    Assert.assertEquals("# Extra scores", 1, extraScores.size());
    Assert.assertTrue("Extra score", extraScores.get(0) instanceof FakeExtraScore);

    frame = new FakeFrame(1);
    scorer.add(frame);
    Assert.assertEquals("Score 2", 19, scorer.getScore());
    extraScores = scorer.getExtraScores();
    Assert.assertEquals("# Extra scores 2", 2, extraScores.size());

    frame = new FakeFrame(0);
    scorer.add(frame);
    Assert.assertEquals("Score 3", 30, scorer.getScore());
    extraScores = scorer.getExtraScores();
    Assert.assertEquals("# Extra scores 3", 0, extraScores.size());
  }


  private static class FakeFrame extends BaseFrame {

    protected FakeFrame(final int pins) {
      super(Arrays.asList(pins, 9 - pins));
    }

    @Override
    public ExtraScore getExtraScore() {
      return new FakeExtraScore(pins(0));
    }

  }


  private static class FakeExtraScore implements ExtraScore {

    private int numNeeded;

    public FakeExtraScore(final int numNeeds) {
      numNeeded = numNeeds;
    }

    @Override
    public boolean needFrame() {
      return numNeeded  > 0;
    }

    @Override
    public int getScore(final Frame frame) {
      numNeeded--;
      return 1;
    }

  }

}

The rest of the code seems fine.

I must say that of all the times I’ve done this exercise, this time I ended up with the most classes/interfaces: 14 all together! But these total just 356 lines, or about 25 lines per type. Between all the syntactic cruft that Java makes me write and the generous use of blank lines that I prefer, I’d say that’s a pretty good score. I wonder how that will turn out in Groovy. Stay tuned.