out.println

Java collections class diagram

2011-06-10T00:00:00+00:00

Here's a quick reference diagram of the JDK collection classes.

I wanted something concise (just showing what's available, for more details there's the javadoc), user-oriented (the abstract implementations are not represented), and that could be printed on an A4 or US-letter paper sheet.

I've used yEd. If you want to tweak the diagram or export it to another format, the source is available on GitHub.

An offline webapp example with Play! and JQuery

2011-05-22T00:00:00+00:00

I've published a small prototype written to experiment with HTML5's offline webapp and local storage features. It's a simplistic note-taking application, with two list and detail pages:

Notes can be browsed, created, modified and deleted offline; they are stored locally and synchronized when the application goes back online. To keep the example reasonably short, I've simplified a few features:

conflict resolution is optimistic: when both a local and a server version of a note exist, the next synchronization will keep the most recent version;
removal is "soft": the note stays in the database, but gets flagged as "archived" so that future search requests ignore it.

On the technical side, the backend relies on Play! and JPA, and the frontend uses JQuery.

Here are a few thoughts gathered during development:

Writing the manifest

Making the list page cacheable

There is something counterintuitive about offline pages in a dynamic website. When I first learnt about the cache manifest and the fallback section, I thought my list page would use a "normal", server-generated version in online mode (query the database, feed the results to a Play! template that generates the HTML response), and would somehow fallback to a different, local-storage-enabled version in offline mode.

This is not how it works. The key point here is this sentence from the specification:

in practice the page that referenced the manifest is automatically cached even if it isn't explicitly mentioned.

Let's suppose that I navigate to / (the URI of my list page) while online; my server-side components generate the HTML response and send it back to my browser. Since this document declares a manifest, the browser stores it in its offline cache (along with any resource declared in the manifest), and uses this cached version for any subsequent request, be it online or offline. Which means that:

refreshing the page won't send a new request to the server. If the database changes, I will keep getting a stale version of the list;
when the application goes offline, I have no way to switch to my alternate version of the page. What gets served is the cached version of an earlier online request.

The bottom line is that there must be a single version of my list page, which works in both modes:

when online, it fetches data from the server using background Ajax requests;
when offline, it defaults to local storage.

This moves the solution towards a "single page"-style interface, where most of the application logic (fetching data, populating the list, pagination) is handled via client-side Javascript.

Keeping the detail page addressable

One thing we lose with client-side navigation is addressable URIs. I wanted to keep a RESTful-style URI for each note (/notes/7 in the second screenshot above).

I did that by keeping the detail page as a different resource. However, there is again a problem with the offline cache: each note URI is interpreted as a separate resource. Since IDs are assigned dynamically, I can't list each and every /notes/<id> URI in my cache manifest in advance. So, if I'm offline and try to access a note I've never opened before, the browser won't find it because it's not in the cache. I should be able to restore this page from the data I've synchronized in my local storage.

To address this problem, I've used the fallback section. All dynamic note URIs fallback to a static page:

NETWORK:
/notes/*

FALLBACK:
/notes/ /offline/detail

The fallback page uses Javascript to parse the URL and load the note (again, either with a background Ajax call or from the local storage, depending on network availability).

Testing

I've used Play's out-of-the box Selenium support.

The first question was: how to simulate loss of connectivity? Since Play's test runner is launched from the developement server, I couldn't just shut it down. The answer turned out to be quite simple: the way my client code detects offline mode is by the fact that Ajax requests fail. So I added a "hook" URI that makes all Ajax requests 404 (this is handled by setting a flag on the server). The Selenium tests just need to invoke that URI, and the application behaves as if it was offline.

Similarly, I've added other hook URIs to:

clear the local storage (by loading a page that runs a Javascript snippet);
touch the cache manifest, to force an offline cache update;
check the state of a note on the server without going through the normal UI (this is useful to check that the server is not updated when the client is supposed to be disconnected);
touch a server note (to test update conflicts).

Naturally, these URIs are only accessible when the server runs in development mode.

Conclusion

In my experience, taking a dynamic (as in database-driven) webapp offline naturally lead me to a single-page design. I've kept the list and detail page separate, but there is probably a way to keep everything in one page and still preserve addressability.

Things get complicated quickly. I've spent more time on this tiny example than I had originally anticipated. In particular, keeping the local and server databases synchronized introduces new corner cases.

Testing can be painful (now I understand why Dive into HTML5 has a section named "The fine art of debugging, A.K.A. Kill me! Kill me now!"). Locate your browser's "clear local data" and "clear cache" buttons, you're going to need them often.

Running the Selenium tests from the browser is probably not the best choice. Standalone tests (for instance, JUnit tests using Selenium's Java API) would have made it easier to simulate offline mode, simply by shutting down and restarting the development server.

With Firefox, I've sometimes observed erratic offline cache behavior: it would stop updating and I would have to clear it manually and restart the browser. It's not clear to me whether this is a Firefox bug or a problem with my configuration.

Feel free to comment or fork the GitHub project.

Moving feed to FeedBurner

2011-05-05T00:00:00+00:00

I've published my feed on FeedBurner.

If you had suscribed to the former URL (which will still work), I'd appreciate if you took a few seconds to change to http://feeds.feedburner.com/out-println. This will provide me with stats and take a little bit of load off my server.

The TOCTTOU attack

2011-03-25T00:00:00+00:00

The following class has a security flaw, can you spot it?

import java.util.Date;

/** An immutable class representing a time interval. */
public final class Interval {

  private final Date min;
  private final Date max;

  public Interval(Date min, Date max) {
    if (min.after(max)) throw new IllegalArgumentException();
    this.min = (Date) min.clone();
    this.max = (Date) max.clone();
  }

  public Date min() { return (Date) min.clone(); }
  public Date max() { return (Date) max.clone(); }
}

The class fulfills the prerequisites for immutability:

all of its fields are final,
the reference to this does not escape during construction,
there is no way to modify its state afterwards: Date is mutable, but we were careful enough to use private fields and make defensive copies whenever we exchange data with the outside world. The constructor checks that its parameters respect the class's invariant, and immediately throws an exception if they don't.

However, there is still a way to build an Interval where min > max.

To explain the approach, here is an analogy: suppose I have just performed poorly at an important written exam. Afterwards, I go to my textbooks and find all the right answers, but it's too late: the teacher already has my paper. Unless... assuming the teacher won't grade the exam until tomorrow, I can write a fake paper, break into his house during the night, and swap the two copies!

This (very unethical) trick is made possible by a window of opportunity between the time I handed out my paper and the time my teacher actually reads it. Interval displays the same kind of weakness: the invariant check (line 10) is made before the defensive copies (lines 11 & 12). With appropriate timing, a malicious client can mutate a date after the check, but before the copy.

Here is the attacker class:

public class Attacker {
  volatile Date max = new Date();

  final Thread burglar = new Thread() {
    @Override public void run() {
      max.setTime(0);
    }
  };

  public Interval attack() {
    Date min = new Date();
    max.setTime(min.getTime());
    burglar.start();
    try {
      Interval i = new Interval(min, max);
      if (i.min().after(i.max())) {
        System.out.println("Success!");
        return i;
      } else System.out.println("Too late");
    }
    catch (final IllegalArgumentException e) {
      System.out.println("Too soon");
    }
    return null;
  }
}

We begin with both arguments to the current date (lines 11 & 12) but, before calling the constructor, we start a thread that will set the max in the past. I expected to have to tweak a wait time at the beginning of run(), but in fact that's not even necessary.

Since the attack depends on lucky timing, it won't work every time; we run it in a loop:

Interval corrupted;
long start = System.currentTimeMillis();
int count = 0;
while ((corrupted = (new Attacker()).attack()) == null) count += 1;

System.out.println("In " + (System.currentTimeMillis() - start) + " ms and " +
  count + " attacks, I have created a corrupt interval with min=" +
  corrupted.min() + " and max=" + corrupted.max());

On my machine, this generally succeeds in about 500 ms and 2500 attacks. My "worst" case was 2509 ms and 14393 attacks, and my "best" 14 ms and 26 attacks.

This attack is known as TOCTTOU, which stands for Time Of Check (collect the papers / check the invariant) To Time Of Use (grade the papers / make the defensive copy). If you work with untrusted client code and expose this kind of vulnerability, a malicious client can destroy your internal invariants (which generally sucks).

The fix is explained in Josh Bloch's excellent Effective Java, 2nd edition, item 39:

make the defensive copies first, and check the invariant on the copies, or better yet:
use immutable arguments (for dates, Joda Time or the upcoming JSR 310).

Here's the implementation of the first solution:

public Interval(Date min, Date max) {
  this.min = (Date) min.clone();
  this.max = (Date) max.clone();
  if (this.min.after(this.max)) throw new IllegalArgumentException();
}

The complete example is available on github.

Simplified varargs 101

2011-01-04T00:00:00+00:00

Simplified varargs is probably the most obscure of the small changes coming in Java 7 (maybe because it won't be that relevant for end developers). Here are a couple of examples I wrote to make sure I grokked what it was all about.

Reminder: arrays and generic types don't mix well

You can't create an array of a generic type

The compiler won't let you write:

AtomicReference<Integer>[] ris = { new AtomicReference<Integer>() }; // Compile error

If it did, that would lead to the following problem:

Object[] os = ris;
os[0] = new AtomicReference<String>("foo");
Integer i = ris[0].get(); // ClassCastException: String cannot be cast to Integer

With non-generic types, the runtime checks type safety at line 2 (throwing an ArrayStoreException if there is an inconsistency). This is not possible for generic types, because of type erasure: at runtime, both sides of the assignment are a raw AtomicReference. Therefore, if the compiler let us get this far, the runtime would only detect the error at the third line, which could be in a completely unrelated part of the code (imagine the debug headache).

But an array is created for a vararg argument

What the compiler will let you write is this:

static <T> T doEvilStuff(final T... ts) {
  Object[] os = ts;
  os[0] = new AtomicReference<String>("foo");
  return ts[0];
}
...
AtomicReference<Integer> ri = doEvilStuff(new AtomicReference<Integer>(0));
Integer i = ri.get(); // ClassCastException: String cannot be cast to Integer

This is known as heap pollution. The only thing the compiler does is raise a warning at line 7:

Type safety : A generic array of AtomicReference is created for a varargs parameter

Why just a warning? Because:

life would suck without generic varargs ;-)
in 99% of the cases, the method will just read the vararg elements (which is safe), not mutate them as in this convoluted example.

Java 6: why the current situation is not satisfying

The problem is that the warning is emitted at the call site, not at the declaration site.

There are examples in the JDK (for instance Arrays.asList), but, for the sake of originality, let's consider a custom example: an assertion method (à la JUnit) to verify that a map contains a set of entries.

import java.util.AbstractMap.SimpleEntry;
import java.util.Map.Entry;
...
static <K, V> void assertContains(final Map<K, V> m, final Entry<K, V>... entries) {
  for (Entry<K, V> e : entries) {
    K key = e.getKey();
    assert m.containsKey(key);
    V expected = e.getValue(), actual = m.get(key);
    assert expected == null ? actual == null : expected.equals(actual);
  }
}
// Just a helper method to write entries more concisely
static <K, V> Entry<K, V> entry(final K key, final V value) {
  return new SimpleEntry<K, V>(key, value);
}
...
// From the client code:
assertContains(someMap, entry("foo", 1), entry("bar", 2)); // Warning raised here

Now, imagine I provide assertContains as part of a library. Each and every time some client code invokes that method, it will get a warning, and I can't do anything about it, even though I know perfectly well that the method is safe.

Java 7: simplified varargs

As a library designer, I'd like a way to tell the compiler: "I take responsibility for the good behavior of assertContains. Leave my clients alone".

The @SafeVarargs annotation does just that. When applied to a method or constructor, it will suppress the warning at all call sites:

@SafeVarargs
static <K, V> void assertContains(final Map<K, V> m, final Entry<K, V>... entries)

You can download build b123 to try it yourself. Without the annotation, warnings are emitted at call and declaration sites:

>%JAVA_HOME%\bin\javac src\Test.java -d bin -Xlint:unchecked
src\Test.java:13: warning: [unchecked] Possible heap pollution from parameterized vararg type Entry<K,V>
  static <K, V> void assertContains(final Map<K, V> m, final Entry<K, V>... entries) {
                                                    ^
  where K,V are type-variables:
    K extends Object declared in method <K,V>assertContains(Map<K,V>,Entry<K,V>...)
    V extends Object declared in method <K,V>assertContains(Map<K,V>,Entry<K,V>...)
src\Test.java:24: warning: [unchecked] unchecked generic array creation for varargs parameter of type Entry<String,Integer>[]
    assertContains(someMap, entry("foo", 1), entry("bar", 2));
                  ^
2 warnings

With the annotation, both warnings go away.

The specification also mentions that:

Compilers are encouraged to issue warnings when this annotation type is applied to a method or constructor declaration where:

The variable-arity parameter has a reifiable element type, which includes primitive types, Object, and String. (The unchecked warnings this annotation type suppresses already do not occur for a reifiable element type.) [for instance, unnecessarily annotating static void doStuff(int... is)]

The body of the method or constructor declaration performs potentially unsafe operations, such as an assignment to an element of the variable-arity parameter's array that generates an unchecked warning.[this is the case of our doEvilStuff method]

I've tried both cases, but they don't seem to be implemented yet in b123: the compiler silently let me apply the annotation.

Breakpoint dependencies in Eclipse

2010-12-16T00:00:00+00:00

This post describes a hack to achieve the following behavior in the Eclipse debugger: stop at a given breakpoint only if another breakpoint has been reached before.

I'm not aware of an existing solution to do that (although IDEA seems to have that functionality) — and if I'm wrong, I've just lost a couple of hours of my life :-)

The problem

Suppose I'm debugging a unit test that runs the same assertion over and over with different parameters (I know unit tests should have few assertions, but sometimes this pattern is just more practical):

assertEquals(43, SomeClass.someMethod(1));
assertEquals(44, SomeClass.someMethod(2));
assertEquals(45, SomeClass.someMethod(3));
assertEquals(50, SomeClass.someMethod(4));

Suppose the last assertion is failing. I want to debug it, and I'm particularly interested in an internal method called indirectly by someMethod, deep down the call stack:

private static int internalMethod(int p) {
  return p + 42;
}

Basically, I have three options:

set a breakpoint on internalMethod. But the debugger will suspend every time the method is reached, including in the first N-1 calls to someMethod that I'm not interested in.
set the breakpoint on the assertion that fails. But when the debugger suspends, I still have to go down the call stack to reach internalMethod. This involves using Go into repeatedly, which may go into a lot of auxiliary code I'm not interested in (any method invoked to build parameters, class loads, etc.).
set the breakpoint on the outer method, and when it suspends, set the breakpoint on the inner method manually, and hit Continue to reach it directly. That's a bit better, but still involves manual work (to be undone and redone everytime I rerun the test).

Wouldn't it be nice to set both breakpoints, and configure the second one to "activate" only after the first one has been reached? Well that's possible: breakpoints can be conditioned by Java code, and that code can have side effects.

The solution

I drop a class named Breaks in my test folder (the source code of the class is available here). On the outer breakpoint, I add the following condition:

This sets a "marker" that is accessible from other breakpoints. The set method returns false, so the debugger will never suspend on that breakpoint (if I want it to, there is an equivalent setAndBreak method).

On the second breakpoint, the condition invokes a method that returns true only if the marker is set (alternatively, testAndClear also deletes the marker):

Voilà. As long as the outer breakpoint hasn't been reached, the inner breakpoint will not suspend.

This is portable to any debugger that supports conditions, and more elaborate strategies are possible (for instance, associating counters to the markers, instead of simple on / off state).

Update 2010/12/18: you will run into compile errors if Breaks and the debugged classes reside in different packages. To avoid this, put Breaks in a package with a short name, and use the fully qualified name in the breakpoint conditions (putting it in the default package doesn't seem to work, and import statements are not allowed in breakpoint conditions).

Remove boilerplate with Guava

2010-06-20T00:00:00+00:00

Guava is Google's core Libraries for Java 1.5+. It is a superset of the Google Collections framework, along with other utilities, released as an open-source project under the Apache 2.0 license.

This post won't cover Guava's major features, but rather some simple "shortcut" methods (each factoring a common Java idiom) that can make a developer's life easier.

To illustrate this, let's consider this simple method, that writes a character string to a file:

public void save(final String info, final File file) throws IOException {
  if (file == null) throw new NullPointerException("file should not be null");
  Writer writer = null;
  boolean threw = true;
  try {
    writer = new BufferedWriter(new OutputStreamWriter(
        new FileOutputStream(file), Charset.forName("UTF-8")));
    String data = info == null ? "Nothing" : info;
    writer.write(data);
    threw = false;
  } finally {
    if (writer != null)
      try {
        writer.close();
      } catch (IOException e) {
        // Do not swallow original exception
        if (!threw) throw e;
      }
  }
}

Here is a version with the corresponding Guava methods:

import com.google.common.base.Charsets;
import com.google.common.base.Objects;
import com.google.common.base.Preconditions;
import com.google.common.io.Closeables;
import com.google.common.io.Files;

public void save(final String info, final File file) throws IOException {
  Preconditions.checkNotNull(file, "file should not be null");
  Writer writer = null;
  boolean threw = true;
  try {
    writer = Files.newWriter(file, Charsets.UTF_8);
    writer.write(Objects.firstNonNull(info, "Nothing"));
    threw = false;
  } finally {
    Closeables.close(writer, threw);
  }
}

Actually, there is even simpler, since we are only writing one string to the file:

public void save(final String info, final File file) throws IOException {
  Preconditions.checkNotNull(file, "file should not be null");
  Files.write(Objects.firstNonNull(info, "Nothing"), file, Charsets.UTF_8);
}

Optionally, you can also statically import everything (which increases readability but makes the origin of the methods less obvious — the choice is a matter of personal taste):

public void save(final String info, final File file) throws IOException {
  checkNotNull(file, "file should not be null");
  write(firstNonNull(info, "Nothing"), file, UTF_8);
}

That's it. Nothing groundbreaking really, but I like how this makes the code more expressive, focusing on what you do rather than how you do it. Guava has a myriad of these utilities (look for static methods in the classes that have a plural name: Lists, Strings, Resources...).

Piggybacking on synchronization

2010-06-09T00:00:00+00:00

Sometimes you can take advantage of an existing synchronization to guarantee the visibility of the changes made to an object. In Java Concurrency In Practice, Brian Goetz calls this "piggybacking on synchronization".

A typical example is the publication of read-only resources that will be shared by all tasks in a thread pool: one of my projects at work parses and processes XML files in parallel. I use XStream for the parsing. The javadoc of XStream — the base class that lets you configure the framework and [de]serialize objects — states that it is safe to use by multiple threads once it has been configured. So it makes sense to share a single instance between various threads:

public class GoodPiggy {
  private ExecutorService executor;
  private XStream xstream;

  public void init() {
    executor = Executors.newFixedThreadPool(someSize);    
    final XStream xstream = new XStream();
    // configure xstream...
  }
  private class Task implements Runnable {
    public void run() {
      // do something with xstream... (threadsafe)
    }
  }
  public void submit() {
    executor.submit(new Task());
  }
}

But are the changes to xstream safely published? Do the worker threads running the tasks "see" the configuration performed in init()? This is where piggybacking comes into play: submitting a task to an executor happens-before the task begins execution, so the code using xstream in run() is guaranteed to see it in a consistent state (assuming of course that init() and submit() are run by the same thread).

JCIP warns that piggybacking on synchronization is a fragile construct, but I think this case is a reasonable use.

Of course, things don't work so well if the tasks modify the shared state. Here is a counter-example (adapted from item 66 of Effective Java):

public class BadPiggy { // DOESN'T WORK
  private static boolean stop;

  public static void main(final String[] args) throws InterruptedException {
    final ExecutorService executor = Executors.newFixedThreadPool(2);
    Runnable looping = new Runnable() {
      public void run() {
        int i = 0;
        while (!stop) i++;
      }
    };
    executor.submit(looping);
    Runnable stopper = new Runnable() {
      public void run() { stop = true; }
    };
    executor.submit(stopper);
    executor.shutdown();
  }
}

Here, the modification of stop is not safely published, because there is no happens-before relationship between the moment stopper sets it, and the moment looping is expected to see the change. I can get this example to loop forever on my machine (windows, Java 6u16 VM with -server option).

The solution here is to make the field volatile, which guarantees visibility of the changes. If we needed mutual exclusion as well (for instance, if the shared state was an incrementing counter), we would need synchronization, either explicitly, or through a higher-level construct (like an AtomicInteger).