Finishing touches, part 1

It's been almost three weeks since I started my series on writing a little test app for Java App Engine with GWT. When I started development, I had split up the work into four iterations:

The first one will be building a GWT application with a simple UI that has no server logic behind it (just to learn how layout in GWT works). Step two will be adding a fake servlet backend (not app engine, just in memory). While not exactly App Engine yet, I should have a completely specified client-server API by the end of this process that I can subsequently implement on App Engine (iteration 3). Iteration four will handle deployment, CSS and whatever I may screw up in iterations one and two.

With this post, "Schlüsselmeister" is now entering the fourth and last of these stages. At the end of iteration three (which can be downloaded as source from here), I identified the following TODOs:

• The url entry in the table should be a hyperlink.


• Add a way to select a row with an existing password entry, to show the password, and to edit it.


• Add a new field for the username.


• Add a delete button for passwords.


• Convert the landing page into a JSP that hides the app if no user is logged in. Right now, you have to press the login button, which is not quite intuitive.


• Making the app pretty using CSS (anyone know a good template I can use? Please post to this blog!)

The first two items are simple modifications in the GWT UI code, so that's not very interesting to write about. Adding a new field is not rocket science, either. First, I extend my protocol buffer definition by adding an optional field user_name:

package schluesselmeister;

option java_package = "com.appenginefan.schluesselmeister.server";
option java_outer_classname = "DataModel";
option optimize_for = SPEED;

message KeyData {
  required int64 id = 1;
  required string key = 2;
  required string password = 3;
  optional string description = 4;
  optional string url = 5;
  required string category_name = 6;
  optional string user_name = 7;
}

message KeyDatabase {
  required int64 last_id = 1;
  repeated KeyData data = 2;
}

I rebuilt the Java files so that the field is also represented in the server code. Since protocol buffers are very good regarding compatibilty, the new version can easily read the old data and vice versa (try it out: create a new password entry in this version of the app that contains the new field that already contains the new field. Then go back iteration 3: your new entry will still be readable.) Word of warning though: making any changes in version three and saving them to the store will nuke all username entries, since the old app is not aware of the newly created field.

After extending the data model, I do the same to my pojo-class PasswordData and add an additional input field to the EditPasswordDialog -- and that's pretty much it. Adding a delete button is not much harder either: the biggest work is extending the backend service with a new delete method (and adding enough unit tests to feel confident that it works fine):

  @Override
  public List<? extends ServerToClientCommand> delete(
      Long id) {

    // Deny access if no user is logged in
    final String user = getUserEmail();
    if (user == null) {
      return getMissingUserResponse();
    }

    // Do nothing if the client did not pass along an id
    if (id == null) {
      return getResponseList();
    }
    final long asPrimitive = id;

    // Modify the datastore. Keep track of all categories
    // that changed
    final List<String> categoriesToUpdate =
        Lists.newArrayList();
    final Set<String> allRemainingCategories =
        Sets.newHashSet();
    KeyDatabase database =
        store.mutate(user,
            new Function<KeyDatabase, KeyDatabase>() {
              @Override
              public KeyDatabase apply(KeyDatabase db) {
                if (db == null) {
                  return null;
                }
                Builder builder =
                    KeyDatabase.newBuilder().mergeFrom(db);
                for (int i = builder.getDataCount() - 1; i >= 0; i--) {
                  final KeyData data = builder.getData(i);
                  if (data.getId() == asPrimitive) {
                    ArrayList<KeyData> changeThis =
                        Lists.newArrayList(builder
                            .getDataList());
                    changeThis.remove(i);
                    builder.clearData();
                    builder.addAllData(changeThis);
                    categoriesToUpdate.add(data
                        .getCategoryName());
                  } else {
                    allRemainingCategories.add(data
                        .getCategoryName());
                  }
                }
                return builder.build();
              }
            });
    boolean listChanged = false;
    final List<ServerToClientCommand> result =
        getResponseList();
    for (String category : categoriesToUpdate) {
      result.add(getDataCommand(category, database));
      if (!allRemainingCategories.contains(category)) {
        listChanged = true;
      }
    }
    if (listChanged) {
      result.add(getCategoriesCommand(database));
    }
    return result;
  }

With this final modification to the Java code, my GWT client and App Engine backend are pretty much complete. What remains is focusing on the presentation. Since I am completely dreadful with regards to making UIs look pretty, I am going to push out the CSS stuff into another post ;-). Today, it's all going to be about JSP.

So far, I have used a static html landing page for my application. That was fine so far, but I have a small additional requirement that static html cannot solve that easily: since Schlüsselmeister has to know the user's email address to persist data, I want to display the GWT application only if the user is already logged in. Rather than trying anything fancy in my Javascript, I figure I could just tie the application's fate to the div that the code is displayed at: if it's missing, my main class will simply not show anything:

package com.appenginefan.schluesselmeister.client;

import com.google.gwt.core.client.EntryPoint;
import com.google.gwt.core.client.GWT;
import com.google.gwt.user.client.ui.RootPanel;

/**
 * Entry point classes define <code>onModuleLoad()</code>.
 */
public class Schluesselmeister implements EntryPoint {

  @Override
  public void onModuleLoad() {
    
    // Only create an app if the right div is there.
    // This way, a JSP can be smart on whether or not to
    // show the program    
    RootPanel panel = RootPanel.get("program");
    if (panel != null) {
      
      // Wire all classes together
      final MainScreen display = new MainScreen();
      final Scrambler scrambler = new BlockTEAScrambler();
      final Store store = new Store(scrambler);
      final BackendAsync backend =
          (BackendAsync) GWT.create(Backend.class);
      final Controller controller =
          new Controller(display, backend, store, scrambler);
      
      // Make the display visible and start event processing
      panel.add(display);
      controller.start();
    }
  }
}

The landing page can now simply turn the program on or off by including (or not including) the div element. The following example page uses the user API to determine if someone is currently logged in. If that is the case, it will display the application. Otherwise, it will render a link to a login page instead:

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<%@page import="com.google.appengine.api.users.UserServiceFactory"%>
<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<link type="text/css" rel="stylesheet" href="Schluesselmeister.css">
<title>Schl&uuml;sselmeister</title>
<script type="text/javascript" language="javascript"
 src="schluesselmeister/schluesselmeister.nocache.js"></script>
</head>
<body>
<h1>App Engine Fan's <i>Schl&uuml;sselmeister</i></h1>
<h2>Password management software for the internets</h2>
<p>This password manager application is a piece of software 
[...]
framework come with. Use at your own risk, and don't try to hold me
liable for anything. That being said -- I hope you enjoy the program and
find it useful.</p>
<% if (UserServiceFactory.getUserService().getCurrentUser() != null) { %>
<div id="program" />
<% } else { %>
<p>To use this program, you have to <a
 href="<%= UserServiceFactory.getUserService().createLoginURL("/") %>">log
in with your Google account.</a></p>
<% } %>
</body>
</html>

That's it for today :-) You can find this version of the application at https://4.latest.vinz-clortho.appspot.com/. Let me know if there are any problems using it.

The last and final development step will have to be to make the page look nice. I have not started that work yet and (as mentioned earlier) I am not particularily good at it either. If anyone has a good suggestion for a stylesheet, just post it to this blog entry. I'll be more than happy to try it out and incorporate it into the application...

The keymaster is alive :-)

Not a lot of energy to blog right now (probably this Sunday again, maybe Monday), but I just wanted to report that the third stage of the Schlüsselmeister app is complete :-). Following the advice of a commenter on this blog, I used a native Javascript implementation of an encryption algorithm to scramble data that went to the server (other people's passwords are none of my business to read, after all!). GWT's native Javascript integration made it pretty easy, as shown in the following implementation (probably not the most effective way of doing it, but it works):

package com.appenginefan.schluesselmeister.client;

/**
 * A thin GWT wrapper around the native javascript BlockTEA
 * implementation as described in
 * http://www.movable-type.co.uk/scripts/tea-block.html
 */
public class BlockTEAScrambler
    extends Scrambler {

  @Override
  public String scramble(String s) {
    return TEAencrypt(s, scramblingSecret);
  }

  @Override
  public String unscramble(String s) {
    return TEAdecrypt(s, scramblingSecret);
  }

  // What follows is the native Javascript library
  // =============================================

  private static native String TEAencrypt(String plaintext,
      String password)/*-{
    function strToLongs(s) {  // convert string to array of longs, each containing 4 chars
    // note chars must be within ISO-8859-1 (with Unicode code-point < 256) to fit 4/long
    var l = new Array(Math.ceil(s.length/4));
    for (var i=0; i<l.length; i++) {
        // note little-endian encoding - endianness is irrelevant as long as 
        // it is the same in longsToStr() 
        l[i] = s.charCodeAt(i*4) + (s.charCodeAt(i*4+1)<<8) + 
               (s.charCodeAt(i*4+2)<<16) + (s.charCodeAt(i*4+3)<<24);
    }
    return l;  // note running off the end of the string generates nulls since 
    }              // bitwise operators treat NaN as 0
    function longsToStr(l) {  // convert array of longs back to string
    var a = new Array(l.length);
    for (var i=0; i<l.length; i++) {
        a[i] = String.fromCharCode(l[i] & 0xFF, l[i]>>>8 & 0xFF, 
                                   l[i]>>>16 & 0xFF, l[i]>>>24 & 0xFF);
    }
    return a.join('');  // use Array.join() rather than repeated string appends for efficiency
    }

    if (plaintext.length == 0) return('');  // nothing to encrypt
    // 'escape' plaintext so chars outside ISO-8859-1 work in single-byte packing, but keep
    // spaces as spaces (not '%20') so encrypted text doesn't grow too long (quick & dirty)
    var asciitext = escape(plaintext).replace(/%20/g,' ');
    var v = strToLongs(asciitext);  // convert string to array of longs
    if (v.length <= 1) v[1] = 0;  // algorithm doesn't work for n<2 so fudge by adding a null
    var k = strToLongs(password.slice(0,16));  // simply convert first 16 chars of password as key
    var n = v.length;

    var z = v[n-1], y = v[0], delta = 0x9E3779B9;
    var mx, e, q = Math.floor(6 + 52/n), sum = 0;

    while (q-- > 0) {  // 6 + 52/n operations gives between 6 & 32 mixes on each word
        sum += delta;
        e = sum>>>2 & 3;
        for (var p = 0; p < n; p++) {
            y = v[(p+1)%n];
            mx = (z>>>5 ^ y<<2) + (y>>>3 ^ z<<4) ^ (sum^y) + (k[p&3 ^ e] ^ z);
            z = v[p] += mx;
        }
    }

    var ciphertext = longsToStr(v);

    return ciphertext.replace(/[\0\t\n\v\f\r\xa0'"!]/g, function(c) { return '!' + c.charCodeAt(0) + '!'; });
  }-*/;

  private static native String TEAdecrypt(
      String ciphertext, String password)/*-{
    function strToLongs(s) {  // convert string to array of longs, each containing 4 chars
    // note chars must be within ISO-8859-1 (with Unicode code-point < 256) to fit 4/long
    var l = new Array(Math.ceil(s.length/4));
    for (var i=0; i<l.length; i++) {
        // note little-endian encoding - endianness is irrelevant as long as 
        // it is the same in longsToStr() 
        l[i] = s.charCodeAt(i*4) + (s.charCodeAt(i*4+1)<<8) + 
               (s.charCodeAt(i*4+2)<<16) + (s.charCodeAt(i*4+3)<<24);
    }
    return l;  // note running off the end of the string generates nulls since 
    }              // bitwise operators treat NaN as 0
    function longsToStr(l) {  // convert array of longs back to string
    var a = new Array(l.length);
    for (var i=0; i<l.length; i++) {
        a[i] = String.fromCharCode(l[i] & 0xFF, l[i]>>>8 & 0xFF, 
                                   l[i]>>>16 & 0xFF, l[i]>>>24 & 0xFF);
    }
    return a.join('');  // use Array.join() rather than repeated string appends for efficiency
    }

    if (ciphertext.length == 0) return('');
    var v = strToLongs(ciphertext.replace(/!\d\d?\d?!/g, function(c) { return String.fromCharCode(c.slice(1,-1)); }));
    var k = strToLongs(password.slice(0,16)); 
    var n = v.length;

    var z = v[n-1], y = v[0], delta = 0x9E3779B9;
    var mx, e, q = Math.floor(6 + 52/n), sum = q*delta;

    while (sum != 0) {
        e = sum>>>2 & 3;
        for (var p = n-1; p >= 0; p--) {
            z = v[p>0 ? p-1 : n-1];
            mx = (z>>>5 ^ y<<2) + (y>>>3 ^ z<<4) ^ (sum^y) + (k[p&3 ^ e] ^ z);
            y = v[p] -= mx;
        }
        sum -= delta;
    }

    var plaintext = longsToStr(v);

    // strip trailing null chars resulting from filling 4-char blocks:
    plaintext = plaintext.replace(/\0+$/,'');

    return unescape(plaintext);
  }-*/;

}

After that, it was mostly a matter of configuring the app to always use https, and then upload it into the cloud. You can look at the latest version at https://3.latest.vinz-clortho.appspot.com/. You need to have a gmail account to login; press the login button to connect to the server.

As you will start using the app, you will notice that there is still quite a lot of cleanup to be done -- which is what I am going to address in the fourth and last iteration. The things I intend to take care of are:

• Add a new field for the username (how could I forget?)


• Add a way to select a row with an existing password entry, to show the password, and to edit it


• A delete button for passwords would be nice.


• The url entry in the table should be a hyperlink


• Making the app pretty using CSS (anyone know a good template I can use? Please post to this forum!)


• Convert the landing page into a CSV that hides the app if no user is logged in. Right now, you have to press the login button, which is not quite intuitive.


• Maybe put some ads onto the main page ;-)

Anything I forgot? Post it to this blog!

Efficient Global Counters, revisited

Although it is almost a year old, the post on efficient global counters from last June is still the third most frequently visited page on my blog. That makes me kindof feel bad: not only am I mostly rehashing a tech talk by Brett Slatkin without adding much to it, the technology described in the post is not even up to "code" any more. Sure the code still works, but since the introduction of memcache, there are even more efficient ways to achive the same goal. The following post is an attempt to outline those ways and to provide a more efficient implementation for Java App Engine. It is based on some discussions I had with Brett on this subject, whom I'd like to give a big thanks! You can also take a look at the Javdoc or get the source code from the open source project. If you need a python version: this open source implementation is actually very close to what I am doing in this blog post :-).

Reliable counters have many different uses, from statistics for the hits on a web page to creating ids for pagination (key ids and timestamps are good approximations in App Engine, but they are not 100% guaranteed to yield the right results). The problem is that building a reliable counter is hard -- especially if it is supposed to be fast! My previous implementation of counters was suggesting to keep memcache to store a snapshot of the counter (for a minute) and then reload from the database as needed. Turns out that this is not ideal: not only is the result of the counter up to 60 seconds old, it also requires me to hit the database once a minute at least to re-compute the value.

One of the many cool things that memache has is a transaction API. Amongst other things, I can

• Get a numeric value out of memcache


• Write a value to memcache, but only if it does not already exist. Let's call this optional set for now.


• atomically fetch, increment, and store a given integer (or long) value that is stored in memcache. It's almost like running in a transaction :-)

So, if memcache can do transactions for me, why not use it for computing the new value of a counter? The idea is as following:

• Instead of sharding the counter on the store and adding up the results, we only shard the current counter value. Assumed that the counter can never decrease, all we have to do to load it from the store is run over all shards and compute the maximum persisted value.


• Whenever we need to access the counter, we check if the counter is populated in memcache. If that is not the case, we do the maximum computation mentioned before and update memcache. It is important to use the optional set mechanism for that, since a second parallel App Engine request could have done the same process and is already overwriting the cached value.


• Whenever we increase the counter, we store the new maximum in a random shard. If we do not need 100% reliability (in other words, it is ok to loose a count every now and then), we can also write to the store less often.

So, how do we implement this in Java? Let's take a look at a class with the following fields and constructor:

public class Counter {

  private static final String PARTITION = "common:counter";
  private final Random random;
  private final Persistence<Long> persistence;
  private final MemcacheService memcache;
  private final double chanceToWrite;
  private final String prefix;
  private final String memcacheKey;
  private final int numShards;

  /**
   * Constructor
   * 
   * @param random
   *          a random number generator
   * @param persistence
   *          a persistence that can be used to write to the
   *          datastore
   * @param memcache
   *          a memcache service for quick access to shared
   *          transactional numbers
   * @param chanceToWrite
   *          a value between 0.0 and 1.0 (inclusive). Each
   *          time the counter gets increased, a random
   *          throw of the dice decides whether to write to
   *          the store. A chanceToWrite of 1.0 means that
   *          every change in the counter will be persisted;
   *          a chanceToWrite of 0.0 means that no change
   *          will be persisted
   * @param key
   *          a key that is used to persist the counter shards
   *          in the datastore and memcache. must not
   *          contain any slashes
   * @param numShards
   *          the number of shards that should be used to
   *          store the value. The more shards the less the
   *          chance of collision on writes, but the longer
   *          it will take to load shards from the store if
   *          memcache has been evicted
   */
  public Counter(Random random,
      Persistence<byte[]> persistence,
      MemcacheService memcache, double chanceToWrite,
      String key, int numShards) {
    super();
    Preconditions.checkNotNull(random);
    Preconditions.checkNotNull(memcache);
    Preconditions.checkNotNull(memcache);
    Preconditions.checkArgument(chanceToWrite >= 0.0
        && chanceToWrite <= 1.0,
        "chanceToWrite must be bewteen 0.0 and 1.0");
    Preconditions.checkArgument(key.indexOf('/') < 0,
        "key must not contain any slashes: " + key);
    Preconditions
        .checkArgument(numShards > 0 && numShards < 1000,
            "there must be at least one shard, but no more than 999");
    this.random = random;
    this.persistence = new LongPersistence(persistence);
    this.memcache = memcache;
    this.chanceToWrite = chanceToWrite;
    this.prefix = '/' + key + '/';
    this.memcacheKey = "aef/c/" + key;
    this.numShards = numShards;
  }

We inject all objects the Counter depends on in the constructor to make it easier to replace any of them with mocks for unit tests (if you're interested in the how, look at the test class). Access to the datastore is wrapped in a simple Persistence interface (see my previous post for details).

Let's take a look at how the memcache is populated:

  /**
   * Makes sure that the memcache is populated. If the
   * memcache is prepopulated, or this process was
   * successful in updating memcache from the datastore,
   * return the known value. Otherwise, return null.
   */
  private Long populateMemcache() {
    Long result = (Long) memcache.get(memcacheKey);
    if (result == null) {
      long max = 0;
      for (Entry<String, Long> shard : Utilities
          .scanByPrefix(persistence, prefix, 1000)) {
        max = Math.max(max, shard.getValue());
      }
      boolean changed =
          memcache.put(memcacheKey, max, null,
              SetPolicy.ADD_ONLY_IF_NOT_PRESENT);
      if (changed) {
        result = max;
      }
    }
    return result;
  }

The method checks if there is currently a value in the cache. If that is the case, it will return the current value (no need to do a second lookup later on if we don't have to) If the value is not there, it will load all shards from the store and compute the maximum value. If it can compute and set the value in memcache, it returns that result. Otherwise, it assumes that the data in memcache has already changed and returns null instead.

With this tool method implemented, getting the current value for the counter is easy:

  public long get() {
    Long prepopulated = populateMemcache();
    return (prepopulated != null) ? prepopulated
        : (Long) memcache.get(memcacheKey);
  }

How about setting the value, though? Well, we just peform the steps alrady outlined above:

• Make sure that memcache is initialized (by calling populateMemcache).


• Increment the value in memcache and store the result


• If we decide to write the data to the store, select a random shard and persist the data. Since we are working in a transaction, another server process could have picked the same shard to write an updated value, so be sure to do a maximum-computation before writing the data.

Here's the method in code:

  public long increment(long delta) {
    Preconditions.checkArgument(delta > 0,
        "delta must be a positive value");
    populateMemcache();
    final Long result =
        memcache.increment(memcacheKey, delta);
    if (random.nextDouble() <= chanceToWrite) {
      String shardKey = prefix + random.nextInt(numShards);
      persistence.mutate(shardKey,
          new Function<Long, Long>() {
            @Override
            public Long apply(Long oldValue) {
              if (oldValue == null) {
                return result;
              }
              return Math.max(oldValue, result);
            }
          });
    }
    return result;
  }

As always, take what I am writing here with a huge grain of salt. There is always the possibility that I have not considered all edge cases, or that I simply have a bug in this implementation. In other words, please do not hesitate to post comments to this blog with questions or errors you may find! If you'd like to take a look at the entire source or use the code in a project of your own, you can find it all in this open source project.

Writing a unit testable backend

This is another post in the Schlüsselmeister series, in which I try to build a GWT/App Engine based key store application from scratch. This entry should hopefully be readable and interesting on its own, but it might still be worthwhile to check out the previous posts.

Over the next two or three posts, I will focus on iteration three of my little key store application. The previous two iterations were about implementing a GWT based client and establishing a protocol that the client could use to communicate with the server. The major emphasis in the following stage of development is getting the application fully functional (but not pretty -- I am saving stuff like CSS and a nicer landing page for the final iteration). The things I have to target are:

• Build a backend on App Engine that handles incoming requests properly.


• Implement a Scrambler class in GWT that encrypts data in the browser before it gets sent to the server.


• Enable and enforce https access to protect encryption on the wire.

This post will be about the App Engine backend class, AppEngineBackendImpl. Like in the previous iterations, I will post the source for download once the stage is code complete, so I will shorten the code a little bit for brevity (like imports, or some of the methods not essential for this post). As mentioned in my alternative approach to using the data store, I am not going to make use of JPA or JDO for designing my data model. My theory is that any given key database is so small that it easily fits into a a single entity in the data store. Therefore, I am using Protocol buffers to specify my data, and a ProtocolBufferPersistence to store each entity in the store. The data model definition goes something like this:

package schluesselmeister;

option java_package = "com.appenginefan.schluesselmeister.server";
option java_outer_classname = "DataModel";
option optimize_for = SPEED;

message KeyData {
  required int64 id = 1;
  required string key = 2;
  required string password = 3;
  optional string description = 4;
  optional string url = 5;
  required string category_name = 6;
}

message KeyDatabase {
  required int64 last_id = 1;
  repeated KeyData data = 2;
}

Using the code generator application, this data model gets compiled into two new classes, KeyData and KeyDatabase. KeyDatabase -- which is the top level class I am going to persist -- is essentially a list of KeyData entries, plus a marker that remembers the last integer id being used for storing a key object. Remember, all string components are encrypted, so the id is the only piece of data the server can identify the key entries by. I had also experimented with having key data stored in a set of Category objects but decided that the added complexity in code was probably not worth the effort.

The following abreviated server class demonstrates how the backend handles a request to save new data in the Persistence:

@SuppressWarnings("serial")
public class AppEngineBackendImpl
    extends RemoteServiceServlet implements Backend {

  private final Persistence<KeyDatabase> store;
  private final UserService userService;
  private final String redirectPath;
  
  // Constructor
  // [...]

  /**
   * @return the email of the current user, or null if
   *         nobody is logged in
   */
  private String getUserEmail() {
    User user = userService.getCurrentUser();
    if (user != null) {
      return user.getEmail();
    }
    return null;
  }

  /**
   * Returns commands that should be sent to the client if
   * no user is logged in
   * 
   * @return a singleton list with a properly build login
   *         command
   */
  private List<LoginRequiredCommand> getMissingUserResponse() {
    // [...]
  }

  /**
   * @return a list prepopulated with some standard
   *         commands, like "access granted"
   */
  private List<ServerToClientCommand> getResponseList() {
    // [...]
  }

  /**
   * Creates a command that sets a list of categories on the
   * client
   * 
   * @param database
   *          the database to work on or null
   * @return a properly initialized SetCategoriesCommand
   */
  private SetCategoriesCommand getCategoriesCommand(
      KeyDatabase database) {
    // [...]
  }

  /**
   * Creates a command that updates data for a particular
   * category on the client
   * 
   * @param categoryName
   *          the name of the category to work on
   * @param database
   *          the database to work on or null
   * @return a properly initialized SetDataCommand
   */
  private SetDataCommand getDataCommand(
      String categoryName, KeyDatabase database) {
    // [...]
  }

  @Override
  public List<? extends ServerToClientCommand> requestCategories() {
    // [...]
  }

  @Override
  public List<? extends ServerToClientCommand> requestData(
      String category) {
    // [...]
  }

  @Override
  public List<? extends ServerToClientCommand> save(
      final PasswordData data) {
    
    // Deny access if no user is logged in
    final String user = getUserEmail();
    if (user == null) {
      return getMissingUserResponse();
    }
    
    // Otherwise, modify the store in a transaction
    final List<String> categoriesToUpdate =
        Lists.newArrayList();
    KeyDatabase database =
        store.mutate(user,
            new Function<KeyDatabase, KeyDatabase>() {
              @Override
              public KeyDatabase apply(KeyDatabase database) {
                
                // Strictly speaking, a function is no longer a function
                // when it has side effects like manipulating this
                // list, but I don't care ;-)
                categoriesToUpdate.clear();

                // Is the data currently persistent?
                KeyData.Builder keyData = null;
                KeyDatabase.Builder builder;
                int index = 0;
                boolean addNewEntity = true;
                if (database != null
                    && data.getId() != null) {

                  // if we ever get performance issues,
                  // this could be replaced with binary
                  // search,
                  // but we would need to order the content
                  // of the list
                  // first
                  final long id = data.getId();
                  for (KeyData candidate : database
                      .getDataList()) {
                    if (candidate.getId() == id) {
                      keyData =
                          KeyData.newBuilder(candidate);
                      addNewEntity = false;
                      break;
                    }
                    index++;
                  }
                }

                // If there is nothing at all in the
                // database, start from scratch
                if (database == null) {
                  builder = KeyDatabase.newBuilder();
                  builder.setLastId(0);
                } else {
                  builder =
                      KeyDatabase.newBuilder(database);
                }

                // Do we have to create a new entry?
                if (keyData == null) {
                  keyData = KeyData.newBuilder();
                  keyData.setId(builder.getLastId() + 1);
                  builder.setLastId(keyData.getId());
                }

                // Are we changing categories?
                else if (!keyData.getCategoryName().equals(
                    data.getCategory())) {
                  categoriesToUpdate.add(keyData
                      .getCategoryName());
                }

                // Transfer the data
                keyData.setCategoryName(data.getCategory());
                keyData.setDescription(data
                    .getDescription());
                keyData.setKey(data.getKey());
                keyData.setPassword(data.getPassword());
                keyData.setUrl(data.getUrl());
                categoriesToUpdate.add(keyData
                    .getCategoryName());

                // Add the data to the datastore
                if (addNewEntity) {
                  builder.addData(keyData.build());
                } else {
                  builder.setData(index, keyData.build());
                }

                // Done :-)
                return builder.build();
              }
            });

    List<ServerToClientCommand> result = getResponseList();
    result.add(getCategoriesCommand(database));
    for (String category : categoriesToUpdate) {
      result.add(getDataCommand(category, database));
    }
    return result;
  }

}

The save command is by far the most complex server action, because it has to make manipulations to the data model and consider a lot of different cases (new key store, new entry vs overwriting an old entry, an entry changed categories, ...). Needless to say that I did not get it right the first time: I plugged my new backend in, and everything went kaboom! New data did not appear properly on the screen; old entries got overwritten with new data. However, trying to debug those issues from the GUI would be a lot of effort. Unit tests would need to come to the rescue!

The first thing in building a unit test is finding out how to make a class testable in the first place. Do I need to set up an App Engine backend with a datastore, as described in the SDK documentation? How much plumbing code do I need?

Fortunately, this application was coded with testing in mind. One of my principle coding practices is to build my classes in an injectable fashion -- that means at a minimum that whatever external dependencies a class might have to the rest of the system, it needs to be possible to push these dependencies into the class (instead of the class fetching them by itself). For the backend, the conclusion is that it

• should not have to control how the Persistence is instantiated


• should not fetch the UserService itself


• should not have to fetch any configuration details (like a redirect path for login urls) from an external configuration

AppEngineBackendImpl has a constructor that fulfills these requirements, as shown below:

  /**
   * Useful constructor for unit tests, makes the backend
   * injectable
   */
  public AppEngineBackendImpl(
      Persistence<byte[]> datastore,
      final UserService service, String redirectPath) {
    this.store =
        new ProtocolBufferPersistence<KeyDatabase>(
            datastore, KeyDatabase.getDefaultInstance());
    this.userService = service;
    this.redirectPath = redirectPath;
  }

  /**
   * Standard constructor for the servlet context
   */
  public AppEngineBackendImpl() {
    this(new DatastorePersistence("KeyDatabase"),
        UserServiceFactory.getUserService(),
        "/Schluesselmeister.html");
  }

Using this constructor, it is easily possible to unit test without ever having to set up a fake App Engine environment, by simply using an in-memory persistence implementation plus a mock for the UserService:

public class AppEngineBackendImplTest
    extends TestCase {

  private static final String USER = "user@example.com";

  private Persistence<byte[]> persistence;

  private UserService userService;

  private String redirectPath;

  private AppEngineBackendImpl backend;

  private User user;

  private byte[] database;

  private PasswordData data;

  @Override
  protected void setUp() throws Exception {
    super.setUp();
    persistence = new MapBasedPersistence<byte[]>();
    userService = EasyMock.createMock(UserService.class);
    redirectPath = "/anywhere.html";
    backend =
        new AppEngineBackendImpl(persistence, userService,
            redirectPath);
            
    // At this point, our backend is completely set up.
    // The rest is just some test data we want to use
    // for our unit tests :-)
    user = new User(USER, "example.com");
    KeyData entry1 =
        KeyData.newBuilder().setCategoryName("c1")
            .setDescription("").setId(-1L).setKey("k1")
            .setPassword("p").setUrl("").build();
    KeyData entry2 =
        KeyData.newBuilder().setCategoryName("c2")
            .setDescription("").setId(-2L).setKey("k1")
            .setPassword("p").setUrl("").build();
    database =
        KeyDatabase.newBuilder().setLastId(1).addData(
            entry1).addData(entry2).build().toByteArray();
    data = new PasswordData();
    data.setCategory("c1");
    data.setDescription("d");
    data.setId(-1L);
    data.setKey("k2");
    data.setPassword("p3");
    data.setUrl("foo");
  }

With this setup, we have full control about how the environment behaves for a particular test case, without having to actually simulate logins or persisting data in a store. The following excerpt shows a relatively comprehensive list of unit tests I used to eventually get my implementation of save right. Well, at least I got it to the point where I spotted no more bugs ;-)

  private void setLoggedIn(boolean isLoggedIn) {
    if (isLoggedIn) {
      EasyMock.expect(userService.getCurrentUser())
          .andReturn(user).once();
      EasyMock.expect(
          userService.createLogoutURL(redirectPath))
          .andReturn("foo").anyTimes();
    } else {
      EasyMock.expect(userService.getCurrentUser())
          .andReturn(null).once();
      EasyMock.expect(
          userService.createLoginURL(redirectPath))
          .andReturn("foo").anyTimes();
    }
    EasyMock.replay(userService);
  }

  private void setData() {
    persistence.mutate(USER, Functions.constant(database));
  }

  public void testSaveNotLoggedIn() {
    setLoggedIn(false);
    List<? extends ServerToClientCommand> response =
        backend.save(data);
    assertEquals(1, response.size());
    assertTrue(response.get(0) instanceof LoginRequiredCommand);
  }

  public void testSaveNoData() {
    setLoggedIn(true);
    List<? extends ServerToClientCommand> response =
        backend.save(data);
    assertEquals(3, response.size());
    assertTrue(response.get(0) instanceof AccessGrantedCommand);
    assertEquals(1,
        ((SetCategoriesCommand) response.get(1))
            .countCategories());
    assertEquals(1, ((SetDataCommand) response.get(2))
        .countEntities());
  }

  public void testOverwriteData() {
    setLoggedIn(true);
    setData();
    List<? extends ServerToClientCommand> response =
        backend.save(data);
    assertEquals(3, response.size());
    assertTrue(response.get(0) instanceof AccessGrantedCommand);
    assertEquals(2,
        ((SetCategoriesCommand) response.get(1))
            .countCategories());
    assertEquals(1, ((SetDataCommand) response.get(2))
        .countEntities());
  }

  public void testAddData() {
    setLoggedIn(true);
    setData();
    data.setId(null);
    List<? extends ServerToClientCommand> response =
        backend.save(data);
    assertEquals(3, response.size());
    assertTrue(response.get(0) instanceof AccessGrantedCommand);
    assertEquals(2,
        ((SetCategoriesCommand) response.get(1))
            .countCategories());
    assertEquals(2, ((SetDataCommand) response.get(2))
        .countEntities());
  }

  public void testMoveDataToDifferentCategory() {
    setLoggedIn(true);
    setData();
    data.setCategory("c3");
    List<? extends ServerToClientCommand> response =
        backend.save(data);
    assertEquals(4, response.size());
    assertTrue(response.get(0) instanceof AccessGrantedCommand);
    assertEquals(2,
        ((SetCategoriesCommand) response.get(1))
            .countCategories());
    assertEquals(0, ((SetDataCommand) response.get(2))
        .countEntities());
    assertEquals(1, ((SetDataCommand) response.get(3))
        .countEntities());
  }

  public void testDataInNewCategory() {
    setLoggedIn(true);
    setData();
    data.setId(null);
    data.setCategory("c3");
    List<? extends ServerToClientCommand> response =
        backend.save(data);
    assertEquals(3, response.size());
    assertTrue(response.get(0) instanceof AccessGrantedCommand);
    assertEquals(3,
        ((SetCategoriesCommand) response.get(1))
            .countCategories());
    assertEquals(1, ((SetDataCommand) response.get(2))
        .countEntities());
  }

That's it for today. Feel free to post questions and comments to this blog post :-)