Using Exceptions to Escape from Third-Party Libraries

While this point is not strictly speaking related to zen-level (as it is not about preventing programming errors) it remains a useful tool in the software designer’s toolbox:

Unchecked typed exceptions found in Java and many other languages can be used as a very powerful break statement. Common wisdom says that using exceptions for control flow is inefficient and confusing, and defeats the original purpose of exceptions. I will show that, when certain basic principles are followed, they can be efficient and easy to read. (About the last point, if you have read my previous articles you should know that I use programming constructs in unusual ways in almost all of my articles, because I assume you already know how to use them in the standard way)

Suppose you have a collection of objects that somehow stand on a line and need to detect if two are too close together for some definition of “too close”. For instance you need to know if two timed events are less than five minutes apart, if two Strings in a collection have the same length, if two intervals in a collection overlap. Focusing on the last example, provide an implementation of the following method signature:

/* Assume the bounds of an Interval "i" are int "i.from" and int "i.to". Assume Interval.overlaps(Interval) is done already. */
public boolean hasOverlap(Collection<Interval> collection);

A naive approach is to use two nested loops, the innermost one looking for an intersection of the outer one

for (Interval left: collection) {
  for (Interval right: collection) {
    if (left.overlaps(right)) {
      return true;
    }
  }
}
return false; // not found

Of course you’ll quickly notice that this doesn’t work – any non-empty collection will wrongly return true because each item overlaps with itself. What about this:

for (Interval left: collection) {
  for (Interval right: collection) {
    if (left != right && left.overlaps(right)) {
      return true;
    }
  }
}
return false; // not found

Nope, still doesn’t work – a collection containing the same item twice will wrongly return false. The problem is that, using Iterators.iterable() we have no way of recognising in the nested loop that we’re looking at the outer loop element.
Having no knowledge of what kind of Collection we have, it seems unavoidable to create a copy, then use indexes:

List<Interval> copy = ImmutableList.copyOf(collection); // using Guava's ImmutableList here
for (int left=1; left<copy.size(); left++) {
   for (int right=0; right<left; right++) {
     if (copy.get(left).overlaps(copy.get(right))) {
       return true;
     }
   }
 }
 return false; // not found
 [/java]
 This option works but note that it's a rather clumsy use of indexes, with the risk of using the wrong < versus <=, and confusion about whether we should start iterating at zero or one. Also, it has complexity O(n²).
 
 If we are seeking to detect if two elements of the collection share some property we can also use a Set to record the lengths seen during iteration. In the example of finding if two Strings have the same length:
 [java]
 Set<Integer> lengthsSoFar = new HashSet<>();
for (String item : collection) {
  if (!lengthsSoFar.add(item.length())) {
    return true; // set did not change: duplicate length
  }
}
return false; // no duplicate

This option works, has complexity O(n) (for a set that has sufficient capacity. Otherwise O(n log n) may be more accurate to take regular rehashing into account). We could also use a boolean array where lengthsSoFar[n] is true if we’ve seen a String of length n before and keep complexity O(n), again if it has a sufficient initial capacity. Regular capacity increases may be modeled as O(n log n).

However, again, readability is not ideal. The meaning of the conditional inside the loop is not immediately obvious and I had to add a comment to make sure it is understood.

What library function exists that compares some magnitude of collection elements? Collections.sort() comes to mind. That method will inevitably detect collection items that are close to each other in order to decide how to order them, and this will be known to the Comparator we pass to it. Using an Exception allows us to have the Comparator transmit the information outside:

class OverlapFound extends RuntimeException {}
try {
  List<Interval> copy = new ArrayList<>(collection); // Collections.sort requires a modifiable List
  Collections.sort(copy, new Comparator<Interval>() { public int compareTo(Interval left, Interval right) {
    if (left.overlaps(right)) {
        throw new OverlapFound();  // if we want to communicate which are 'left' and 'right', pass them to the exception constructor
    } else {
      return left.from - right.from;
    }
  }});
} catch (OverlapFound d) {
  return true;
}
return false;

Or, using Java 8 APIs and lambdas:

class OverlapFound extends RuntimeException {}
try {
  collections.stream().sorted((left, right) -> {
    if (left.overlaps(right)) {
        throw new OverlapFound();  // if we want to communicate which are 'left' and 'right', pass them to the exception constructor
    } else {
      return left.from - right.from;
    }
  });
} catch (OverlapFound d) {
  return true;
}
return false;

Visitors

Another situation where we may want to use Exceptions for control flow is Visitor-style APIs. Suppose you have a tree structure such as the representation of an arithmetic expression or a structured document. Suppose the only API offered by the object to navigate the tree is a visitor API. (I believe QueryDSL Expressions are one example) Then we want to know if a tree instance contains a node having a particular property. The standard way would be to carry the information from parent to parent, or to record it in an instance variable, then (if this is even offered by the API) abort traversal when the value has been found, effectively simulating the behaviour of an exception.

Performance

It has been widely repeated that throwing exceptions in Java is “slow”. A quick Google search returns this study with benchmarks: Exceptions are slow in Java. Despite the scary title, note the time scales involved are nanoseconds, sometimes microseconds. Unless your code is pure calculation, the bottleneck is I/O (with a database, with the disk, with the network, with the user), not the exception throwing.

From the article linked above, two points to keep in mind when working with exceptions for control flow:

  • If the exception carries no information (as is the case above), use a single instance in a static final field and throw that:

    private static final OverlapFound OVERLAP_FOUND = new OverlapFound();
    //...
    throw OVERLAP_FOUND;
    
  • If the exception does carry information (such as the items causing a conflict), override the fillInStackTrace method to do nothing. When using exceptions for control flow you do not need the stack trace, and stack trace is responsible for most of exception creation overhead:
    class OverlapFound extends RuntimeException {
      public void fillInStackTrace() {}
    }
    

Readability

A second common objection too using exceptions as control flow is that it harms readability. Follow the following simple principle, reminicent of Level three, to ensure it is not less readable than the common break statement used to escape control structures like loops.

The throw statement(s) must be in the same method as the corresponding catch statement.

Furthermore, to make it explicit that the exception is being used for control flow, the word “Exception” or “Error” shall not appear in the name of the control flow exception.

As the exception is used for escaping from callbacks, it must derive RuntimeException ; if it were a checked exception deriving Exception, its use would be very severely limited. For instance, in the above example Comparator.compareTo is not allowed to throw any checked exception.