Conway’s Game of Life and the Flyweight Pattern

flyweightConway’s Game of Life is fascinating, both from a functional and from a technical perspective.

This may explain why it’s often used for code retreats. Code retreats are a fun way to learn.

It’s amazing how working with new pairs gives you new insights virtually every time.

At the last code retreat that I attended, one of my pairs suggested we use the Flyweight pattern for cells:

A flyweight is a shared object that can be used in multiple contexts simultaneously. The flyweight acts as an independent object in each context — it’s indistinguishable from an instance of the objects that is not shared.

When the Design Patterns book (which contains the above quote) came out, I remember having many aha moments. It was so cool to see all these patterns that I had used before and finally have a name for them so I could discuss them with my peers more efficiently!

I did not have an aha moment when reading about flyweight, however. The example in the book, sharing character objects in a text editor, seemed a bit far fetched at the time. This example is not unlike the cells in a Game of Life grid, however, so I happily went along with my pair’s idea to explore the pattern’s applicability in this context.

After the code retreat was over, I gave this pattern some more thought. (This is usually where the code retreat really starts paying off.)

We actually use a potential flyweight all the time: booleans. A boolean is a class with only two instances, and those instances could easily be shared. In Java they are not: new Boolean(true) != new Boolean(true). However, the Boolean class does provide two constants, TRUE and FALSE, for the instances that you could use for sharing.

That got me thinking about using Enums for flyweights. Most of the time, I use enums for grouping related but mutually exclusive constants, like days of the week. However, Enums in Java can define methods:

  public enum Cell {

    ALIVE(true), DEAD(false);

    private final boolean alive;

    private Cell(boolean alive) {
      this.alive = alive;
    }

    public boolean isAlive() {
      return alive;
    }

    public Cell evolve(int numLiveNeighbors) {
      boolean aliveInNextGeneration = alive
          ? 2 <= numLiveNeighbors && numLiveNeighbors <= 3
          : numLiveNeighbors == 3;
      return aliveInNextGeneration ? ALIVE : DEAD;
    }

  }

One of the fun parts of code retreats is that in some sessions, you will have constraints on the way you work. Such constraints force you to be more creative and think beyond the techniques you would normally use.

One constraint that is interesting in this context is to not use any conditionals, like if or switch statements or ternary operators. The idea behind this constraint is to force you to replace conditionals with polymorphism, making your program more object oriented.

The only way that I see to keep the current Cell enum and not use conditionals, is to introduce a map:

  public enum Cell {

    ALIVE(true), DEAD(false);

    private final boolean alive;
    private static final Map<Boolean, Map<Integer, Cell>> 
        NEXT = new HashMap<>();

    static {
      Map<Integer, Cell> dead = new HashMap<>();
      dead.put(0, DEAD);
      dead.put(1, DEAD);
      dead.put(2, DEAD);
      dead.put(3, ALIVE);
      dead.put(4, DEAD);
      dead.put(5, DEAD);
      dead.put(6, DEAD);
      dead.put(7, DEAD);
      dead.put(8, DEAD);
      dead.put(9, DEAD);
      NEXT.put(false, dead);
      Map<Integer, Cell> alive = new HashMap<>();
      alive.put(0, DEAD);
      alive.put(1, DEAD);
      alive.put(2, ALIVE);
      alive.put(3, ALIVE);
      alive.put(4, DEAD);
      alive.put(5, DEAD);
      alive.put(6, DEAD);
      alive.put(7, DEAD);
      alive.put(8, DEAD);
      alive.put(9, DEAD);
      NEXT.put(true, alive);
    }

    private Cell(boolean alive) {
      this.alive = alive;
    }

    public boolean isAlive() {
      return alive;
    }

    public Cell evolve(int numLiveNeighbors) {
      return NEXT.get(alive).get(numLiveNeighbors);
    }

  }

This approach works, but is not very elegant and it breaks down when the number of possibilities grows. Clearly, we need a better alternative.

The only way we can get rid of the conditional, is by getting rid of the boolean state of the cell. That means we need to have different classes for the two instances, so that the type implicitly embodies the state. That in turn means we need a factory to hide those classes from the client:

  public interface Cell {

    boolean isAlive();
    Cell evolve(int numLiveNeighbors);

  }

  public class CellFactory {

    private static final Map<Boolean, Cell> CELLS 
        = new HashMap<>();

    static {
      CELLS.put(false, new DeadCell());
      CELLS.put(true, new AliveCell());
    }

    public static Cell dead() {
      return cell(false);
    }

    public static Cell alive() {
      return cell(true);
    }

    static Cell cell(boolean alive) {
      return CELLS.get(alive);
    }

  }

  class DeadCell implements Cell {

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

    @Override
    public Cell evolve(int numLiveNeighbors) {
      return CellFactory.cell(numLiveNeighbors == 3);
    }

  }

  class AliveCell implements Cell {

    @Override
    public boolean isAlive() {
      return true;
    }

    @Override
    public Cell evolve(int numLiveNeighbors) {
      return CellFactory.cell(numLiveNeighbors == 2 
          || numLiveNeighbors == 3);
    }

  }

Indeed, when you look up the Flyweight pattern, you’ll see that the proposed structure contains a flyweight factory that creates instances of concrete flyweight classes that implement a common flyweight interface.

Thanks to the code retreat and my partner, I now know why.

Advertisements

Using Cryptography in Java Applications

This post describes how to use the Java Cryptography Architecture (JCA) that allows you to use cryptographic services in your applications.

Java Cryptography Architecture Services

The JCA provides a number of cryptographic services, like message digests and signatures. These services are accessible through service specific APIs, like MessageDigest and Signature. Cryptographic services abstract different algorithms. For digests, for instance, you could use MD5 or SHA1. You specify the algorithm as a parameter to the getInstance() method of the cryptographic service class:

MessageDigest digest = MessageDigest.getInstance("MD5");

You find the value of the parameter for your algorithm in the JCA Standard Algorithm Name Documentation. Some algorithms have parameters. For instance, an algorithm to generate a private/public key pair will take the key size as a parameter. You specify the parameter(s) using the initialize() method:

KeyPairGenerator generator = KeyPairGenerator.getInstance("DSA");
generator.initialize(1024);

If you don’t call the initialize() method, some default value will be used, which may or may not be what you want. Unfortunately, the API for initialization is not 100% consistent across services. For instance, the Cipher class uses init() with an argument indicating encryption or decryption, while the Signature class uses initSign() for signing and initVerify() for verification.

Java Cryptography Architecture Providers

The JCA keeps your code independent from a particular cryptographic algorithm’s implementation through the provider system. Providers are ranked according to a preference order, which is configurable (see below). The best preference is 1, the next best is 2, etc. The preference order allows the JCA to select the best available provider that implements a given algorithm. Alternatively, you can specify a specific provider in the second argument to getInstance():

Signature signature = Signature.getInstance("SHA1withDSA", "SUN");

The JRE comes with a bunch of providers from Oracle by default. However, due to historical export restrictions, these are not the most secure implementations. To get access to better algorithms and larger key sizes, install the Java Cryptography Extension Unlimited Strength Jurisdiction Policy Files. Update: Note that the above statement is true for the Oracle JRE. OpenJDK doesn’t have the same limitation.

Make Your Use of Cryptography Configurable

You should always make sure that the cryptographic services that your application uses are configurable. If you do that, you can change the cryptographic algorithm and/or implementation without issuing a patch. This is particularly valuable when a new attack on an (implementation of an) algorithm becomes available. The JCA makes it easy to configure the use of cryptography. The getInstance() method accepts both the name of the algorithm and the name of the provider implementing that algorithm. You should read both and any values for the algorithm’s parameters from some sort of configuration file. Also make sure you keep your code DRY and instantiate cryptographic services in a single place. Check that the requested algorithm and/or provider are actually available. The getInstance() method throws NoSuchAlgorithmException when a given algorithm or provider is not available, so you should catch that. The safest option then is to fail and have someone make sure the system is configured properly. If you continue despite a configuration error, you may end up with a system that is less secure than required. Note that Oracle recommends not specifying the provider. The reasons they provide is that not all providers may be available on all platforms, and that specifying a provider may mean that you miss out on optimizations. You should weigh those disadvantages against the risk of being vulnerable. Deploying specific providers with known characteristics with your application may neutralize the disadvantages that Oracle mentions.

Adding Cryptographic Service Providers

The provider system is extensible, so you can add providers. For example, you could use the open source Bouncy Castle or the commercial RSA BSAFE providers. In order to add a provider, you must make sure that its jar is available to the application. You can put it on the classpath for this purpose. Alternatively, you can make it an installed extension by placing it in the $JAVA_HOME/lib/ext directory, where $JAVA_HOME is the location of your JDK/JRE distribution. The major difference between the two approaches is that installed extensions are granted all permissions by default whereas code on the classpath is not. This is significant when (part of) your code runs in a sandbox. Some services, like Cipher, require the provider jar to be signed. The next step is to register the provider with the JCA provider system. The simplest way is to use Security.addProvider():

Security.addProvider(new BouncyCastleProvider());

You can also set the provider’s preference order by using the Security.insertProviderAt() method:

Security.insertProviderAt (new JsafeJCE(), 1);

One downside of this approach is that it couples your code to the provider, since you have to import the provider class. This may not be an important issue in an modular system like OSGi. Another thing to look out for is that code requires SecurityPermission to add a provider programmatically. The provider can also be configured as part of your environment via static registration by adding an entry to the java.security properties file (found in $JAVA_HOME/jre/lib/security/java.security):

security.provider.1=com.rsa.jsafe.provider.JsafeJCE
security.provider.2=sun.security.provider.Sun

The property names in this file start with security.provider. and end with the provider’s preference. The property value is the fully qualified name of the class implementing Provider.

Implementing Your Own Cryptographic Service Provider

Don’t do it. You will get it wrong and be vulnerable to attacks.

Using Cryptographic Service Providers

The documentation for the provider should tell you what provider name to use as the second argument to getInstance(). For instance, Bouncy Castle uses BC, while RSA BSAFE uses JsafeJCE. Most providers have custom APIs as well as JCA conformant APIs. Do not use the custom APIs, since that will make it impossible to configure the algorithms and providers used.

Not All Algorithms and Implementations Are Created Equal

It’s important to note that different algorithms and implementations have different characteristics and that those may make them more or less suitable for your situation. For instance, some organizations will only allow algorithms and implementations that are FIPS 140-2 certified or are on the list of NSA Suite B cryptographic algorithms. Always make sure you understand your customer’s cryptographic needs and requirements.

Using JCA in an OSGi environment

The getInstance() method is a factory method that uses the Service Provider Interface (SPI). That is problematic in an OSGi world, since OSGi violates the SPI framework’s assumption that there is a single classpath. Another potential issue is that JCA requires some jars to be signed. If those jars are not valid OSGi bundles, you can’t run them through bnd to make them so, since that would make the signature invalid. Fortunately, you can kill both birds with one stone. Put your provider jars on the classpath of your main program, that is the program that starts the OSGi framework. Then export the provider package from the OSGi system bundle using the org.osgi.framework.system.packages.extra system property. This will make the system bundle export that package. Now you can simply use Import-Package on the provider package in your bundles. There are other options for resolving these problems if you can’t use the above solution.

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…

Using factory classes in Ant tasks

So you have this nice factory class that prevents your client code from knowing the implementation class of the instances it needs to create and that lets it program to an API only.

Of course, at some point somebody needs to know the implementation class. Since the factory is the one creating instances, it either needs to know itself or be told. And since the factory is probably in the same package as the API, it shouldn’t know the implementation class itself, since that would tie the API package to the implementation package. So the factory needs to be told:

public class MyFactory {

  private static Class implementationClass = null;

  private MyFactory() {
    // Utility class
  }

  /**
   * Create a new instance.
   * @param data Data needed to initialize the instance
   * @return The newly created instance
   */
  public static MyInterface newInstance(final Object data) {
      assertImplementationClass();
      final Class clazz = implementationClass;
      if (data == null) {
        try {
          final Constructor constructor = clazz.getConstructor();
          result = (MyInterface) constructor.newInstance(
              new Object[0]);
        } catch (final Exception e) {
          result = null;
        }
      } else {
        final Constructor[] constructors = clazz.getConstructors();
        for (int i = 0; result == null && i < constructors.length; 
            i++) {
          final Constructor constructor = constructors[i];
          if (constructor.getParameterTypes().length == 1
          && constructor.getParameterTypes()[0].isInstance(data)) {
            try {
              result = (MyInterface) constructor.newInstance(
                  new Object[]{data});
            } catch (final Exception e) {
              result = null;
            }
          }
        }
    }

    return result;
  }

  /**
   * Register a class that implements the interface.
   */
  public static void registerImplementation(
      final Class implementation) {
    implementationClass = implementation;
  }

  /**
   * Unregister the implementation class.
   */
  public static void unregisterImplementation() {
    implementationClass = null;
  }

  private static void assertImplementationClass() {
    if (implementationClass == null) {
      throw new IllegalStateException(
          "Implementation class not set");
    }
  }

}

Now, who’s going to tell the factory what class to instantiate? There must be some entry point in the application where this happens. In your tests (you do write tests, right?), you can do that in the set up method. In a web application, you can do that in the ServletContextListener.

Ant

But what about in Ant tasks? You could create an Ant task that does just that and call it from a dependent target:

  <target name="--init-factory" unless="factory.inited">
    <property name="impl.class" 
        value="com.mycompany.myapp.MyImplementation"/>
    <taskdef name="register-impl"
        classname="com.mycompany.myapp.ant.RegisterTask" 
        classpath="..."/>
    <register-impl classname="${impl.class}"/>
    <property name="factory.inited" value="true"/>
  </target>

However, that doesn’t work. So what’s up?

Debugging Ant tasks

Our Ant task seems so simple that it is hard to see what could be wrong with it. So we want to debug it and find out.

You can debug Ant tasks by setting the environment variable ANT_OPTS:

SET ANT_OPTS=-Xdebug -Xrunjdwp:transport=dt_socket,address=6000,server=y,suspend=n

Now when you run your Ant script, you can attach your debugger on port 6000. You may want to use the input task to have the build wait while you attach your debugger.

Debugging reveals something interesting: The registerImplementation method does get called with the right parameter, but when newInstance is called, implementationClass is still null. Apparently Ant is doing some fancy classloader stuff that gets in our way.

The solution is to have the Ant task set a system property that the factory uses:

  private static void assertImplementationClass() {
    if (implementationClass == null) {
      final String className = (String) 
          System.getProperties().get(IMPLEMENTATION_CLASS_PROPERTY);
      if (StringUtils.isBlank(className)) {
        throw new IllegalStateException("Implementation class not set");
      }
      try {
        registerImplementation(Class.forName(className));
      } catch (final ClassNotFoundException e) {
        throw new IllegalStateException("Invalid implementation class: " 
            + className + "\n" + e.getLocalizedMessage());
      }
    }
  }

Supporting multiple versions of a data model

As an application evolves, its data model often does too. If you control both, this usually isn’t a problem. However, sometimes your power to change the data model is restricted. This happens, for instance, when the data model is published, and others may depend on it. An extreme case of this is when the data model is defined by another organization as, for example, with S1000D.

Having no absolute control over the data model isn’t much of a problem if you can leave one version behind completely, and move on to the next. But often you won’t be so lucky. I know I’m not: we need to support both S1000D 3.0 and 4.0.

There’s different ways in which you can support multiple data model versions. The one I’m concerned with here, is when your application needs to support multiple data models at the same time with the same code. That leaves out alternatives like having multiple branches of your code for the different data model versions.

One trick that can come to the rescue here is the Once And Only Once rule (also called the DRY principle). When applied to creating instances, this leads to the Factory pattern. If you have all your instances created by a factory, then there’s only one place where you need to decide which class (e.g. the 3.0 or 4.0 version) to instantiate. If those decisions are similar for all the classes in your model, then you could even extract them into a common base class for your factories.

Most of the time, the different versions of the data model will share a lot of similarities. It is tempting to extract those into a common base class. For example, in S1000D there is a type called descriptive data module, and you could derive DescriptiveDataModule30 and DescriptiveDataModule40 from DecriptiveDataModule.

But when the objects in your data model have inheritance relationships themselves, that can get ugly very fast. For instance, a descriptive data module is one of many kinds of data modules, and these data modules share a lot of characteristics. So in code, DescriptiveDataModule would descend from DataModule, and both would have aspects that differ in the 3.0 and 4.0 versions. This spells trouble.

Therefore, it is usually better to use composition instead. So DataModule would have a reference to a DataModuleIssue (where “issue” is used in the sense of the various issues of the S1000D specification, i.e. what I’ve been calling “versions” so far), which the DescriptiveDataModule would inherit. The factory would inject either a DescriptiveDataModuleIssue30 or a DescriptiveDataModuleIssue40 into the DescriptiveDataModule, where DescriptiveDataModuleIssue30 would descend from DataModuleIssue30, and DescriptiveDataModuleIssue40 from DataModuleIssue40.

The idea is to make the Issue classes very bare, dealing only with the stuff that differs between issues, so there is no need for a common base class (although both do implement the same interface). The things that are the same in all issues, go into the core model objects (DescriptiveDataModule and DataModule in our example).