Java: using a RuntimeException to escape from a Visitor

Question

I am being powerfully tempted to use an unchecked exception as a short-circuit control-flow construct in a Java program. I hope somebody here can advise me on a better, cleaner way to handle this problem.

The idea is that I want to cut short the recursive exploration of sub-trees by a visitor without having to check a "stop" flag in every method call. Specifically, I'm building a control-flow graph using a visitor over the abstract syntax tree. A return statement in the AST should stop exploration of the sub-tree and send the visitor back to the nearest enclosing if/then or loop block.

The Visitor superclass (from the XTC library) defines

Object dispatch(Node n)

which calls back via reflection methods of the form

Object visitNodeSubtype(Node n)

dispatch is not declared to throw any exceptions, so I declared a private class that extends RuntimeException

private static class ReturnException extends RuntimeException {
}

Now, the visitor method for a return statement looks like

Object visitReturnStatement(Node n) {
    // handle return value assignment...
    // add flow edge to exit node...
    throw new ReturnException();
}

and every compound statement needs to handle the ReturnException

Object visitIfElseStatement(Node n) {
  Node test = n.getChild(0);
  Node ifPart = n.getChild(1);
  Node elsePart = n.getChild(2);

  // add flow edges to if/else... 

  try{ dispatch(ifPart); } catch( ReturnException e ) { }
  try{ dispatch(elsePart); } catch( ReturnException e ) { }
}

This all works fine, except:

1. I may forget to catch a ReturnException somewhere and the compiler won't warn me.
2. I feel dirty.

Is there a better way to do this? Is there a Java pattern I am unaware of to implement this kind of non-local flow-of-control?

[UPDATE] This specific example turns out to be somewhat invalid: the Visitor superclass catches and wraps exceptions (even RuntimeExceptions), so the exception throwing doesn't really help. I've implemented the suggestion to return an enum type from visitReturnStatement. Luckily, this only needs to be checked in a small number of places (e.g., visitCompoundStatement), so it's actually a bit less hassle than throwing exceptions.

In general, I think this is still a valid question. Though perhaps, if you are not tied to a third-party library, the entire problem can be avoided with sensible design.

Answer 1

Is there a reason you aren't just returning a value? Such as NULL, if you really want to return nothing? That would be a lot simpler, and wouldn't risk throwing an unchecked runtime exception.

Answer 2

I see the following options for you:

1. Go ahead and define that RuntimeException subclass. Check for serious problems by catching your exception in the most general call to dispatch and reporting that one if it gets that far.
2. Have the node processing code return a special object if it thinks searching should end abruptly. This still forces you to check return values instead of catching exceptions, but you might like the look of the code better that way.
3. If the tree walk is to be stopped by some external factor, do it all inside a subthread, and set a synchronized field in that object in order to tell the thread to stop prematurely.

Answer 3

I think this is a reasonable approach for a few reasons:

• You are using a 3rd party and are unable to add the checked exception
• Checking return values everywhere in a large set of visitors when it's only necessary in a few is an unnecessary burden

Also, there are those that have argued that unchecked exceptions aren't all that bad. Your usage reminds me of Eclipse's OperationCanceledException which is used to blow out of long-running background tasks.

It's not perfect, but, if well documented, it seems ok to me.

Answer 4

Why are you returning a value from your visitor? The appropriate method of the visitor is called by classes that are being visited. All work done is encapsulated within the visitor class itself, it should return nothing and handle it's own errors. The only obligation required of the calling class is to call the appropriate visitXXX method, nothing more. (This assumes you are using overloaded methods as in your example as opposed to overriding the same visit() method for each type).

The visited class should not be changed by the visitor or have to have any knowledge of what it does, other than it allows the visit to happen. Returning a value or throwing an exception would violate this.

Visitor Pattern

Answer 5

Do you have to use Visitor from XTC? It's a pretty trivial interface, and you could implement your own which can throw checked ReturnException, which you would not forget to catch where needed.

Answer 6

I've not used the XTC library you mention. How does it supply the complementary part of the visitor pattern - the accept(visitor) method on nodes? Even if this is a reflection based dispatcher, there must still be something that handles recursion down the syntax tree?

If this structural iteration code is readily accessible, and you're not already using the return value from your visitXxx(node) methods, could you exploit a simple enumerated return value, or even a boolean flag, telling accept(visitor) not to recurse into child nodes?

If:

• accept(visitor) isn't explicitly implemented by nodes (there's some field or accessor reflection going on, or nodes just implement a child-getting interface for some standard control-flow logic, or for any other reason...), and

• you don't want to mess with the structural iterating part of the library, or it's not available, or it's not worth the effort...

then as a last resort I guess that exceptions might be your only option whilst still using the vanilla XTC library.

An interesting problem though, and I can understand why exception-based control flow makes you feel dirty...

Answer 7

Throwing a runtime exception as control logic is definitely a bad idea. The reason you feel dirty is that you're bypassing the type system, i.e. the return type of your methods is a lie.

You have several options that are considerably more clean.

1. The Exceptions Functor

A good technique to use, when you're restricted in the exceptions you may throw, if you can't throw a checked exception, return an object that will throw a checked exception. java.util.concurrent.Callable is an instance of this functor, for example.

See here for a detailed explanation of this technique.

For example, instead of this:

public Something visit(Node n) {
  if (n.someting())
     return new Something();
  else
     throw new Error("Remember to catch me!");
}

Do this:

public Callable<Something> visit(final Node n) {
  return new Callable<Something>() {
    public Something call() throws Exception {
      if (n.something())
         return new Something();
      else
         throw new Exception("Unforgettable!");
    }
  };
}

2. Disjoint Union (a.k.a. The Either Bifunctor)

This technique lets you return one of two different types from the same method. It's a little bit like the Tuple<A, B> technique that most people are familiar with for returning more than one value from a method. However, instead of returning values of both types A and B, this involves returning a single value of either type A or B.

For example, given an enumeration Fail, which could enumerate applicable error codes, the example becomes...

public Either<Fail, Something> visit(final Node n) {
  if (n.something())
    return Either.<Fail, Something>right(new Something());
  else
    return Either.<Fail, Something>left(Fail.DONE);
}

Making the call is now much cleaner because you don't need try/catch:

Either<Fail, Something> x = node.dispatch(visitor);
for (Something s : x.rightProjection()) {
  // Do something with Something
}
for (Fail f : x.leftProjection()) {
  // Handle failure
}

The Either class is not very difficult to write, but a full-featured implementation is provided by the Functional Java library.

3. The Option Monad

A little bit like a type-safe null, this is a good technique to use when you do not want to return a value for some inputs, but you don't need exceptions or error codes. Commonly, people will return what's called a "sentinel value", but Option is considerably cleaner.

You now have...

public Option<Something> visit(final Node n) {
  if (n.something())
    return Option.some(new Something());
  else
    return Option.<Something>none();
}

The call is nice and clean:

Option<Something> s = node.dispatch(visitor));
if (s.isSome()) {
  Something x = s.some();
  // Do something with x.
}
else {
  // Handle None.
}

And the fact that it's a monad lets you chain calls without handling the special None value:

public Option<Something> visit(final Node n) {
  return dispatch(getIfPart(n).orElse(dispatch(getElsePart(n)));
}

The Option class is even easier to write than Either, but again, a full-featured implementation is provided by the Functional Java library.

See here for a detailed discussion of Option and Either.