Interpreter Exception Handling, Part 2

Today’s post is all about the try/catch block, ignoring finally for now – that’s coming in part 3. If you haven’t read part 1, then this will make no sense without it. I think you should read it first, but it’s your call.

The try/catch blocks will have the following syntax:

try {
    doSomething();
} catch (Exception as ex) {
    print ex.stacktrace;
}

The try/catch blocks implementation when I first imagined it, I would search through the code of the current Chunk until I found an exception handler. But that has scope issues – it’s entirely possible for the exception handler in question not to have been triggered inside its adjoining try block, as well as our byte code not being a linear sequence – we can jump all over the place and never even enter the try block because of runtime conditions.

I was clearly having trouble visualising it, so as mentioned in part 1, I had a look at the Python code and found how they do it. As far as I can tell, every single block in Python code gets its own stack frame (which I don’t entirely get, because Tracebacks only include function calls) and the interpreter unwinds each block until it finds one that’s an exception handler, which it then loads into context.

So aside from not entirely understanding the mechanics, I understood enough to realise that that approach wouldn’t work for clox. That’s the point where I stopped looking, but it did give me enough clues to realise that the essence was the relationship with the callstack. Exception handlers are active during the time that their enclosing Chunk is on the callstack and they have been entered, but not exited. Hmmm, that sounds a lot like how functions are handled – pushed onto and popped from a stack, neatly leaving the right things in place during execution. Of course it’s not entirely as simple as adding an ‘active’ handler to the CallFrame because they can be nested indefinitely (sort of) meaning there is a many-to-one exception handler to call frame relationship in play here.

After that revelation, it’s a matter of adding a stack of exception handlers to each CallFrame and ensuring they’re pushed and popped in the right places. There is a small amount of complexity to deal with regarding only executing the catch block if an exception is thrown (and indeed it’s the type being caught) but we can leave that for later, because we can always crib off the if implementation for that.

Let’s start with the keyword handling, which is just plumbing work by now.

--- a/c/scanner.h
+++ b/c/scanner.h
@@ -20,10 +20,10 @@ typedef enum {
   TOKEN_IDENTIFIER, TOKEN_STRING, TOKEN_NUMBER,
 
   // Keywords.
-  TOKEN_AND, TOKEN_CLASS, TOKEN_ELSE, TOKEN_FALSE,
+  TOKEN_AND, TOKEN_AS, TOKEN_CATCH, TOKEN_CLASS, TOKEN_ELSE, TOKEN_FALSE,
   TOKEN_FOR, TOKEN_FUN, TOKEN_IF, TOKEN_NIL, TOKEN_OR,
   TOKEN_PRINT, TOKEN_RETURN, TOKEN_SUPER, TOKEN_THIS,
-  TOKEN_THROW, TOKEN_TRUE, TOKEN_VAR, TOKEN_WHILE,
+  TOKEN_THROW, TOKEN_TRUE, TOKEN_TRY, TOKEN_VAR, TOKEN_WHILE,
 
   TOKEN_ERROR,
   TOKEN_EOF

--- a/c/compiler.c
+++ b/c/compiler.c
@@ -940,6 +946,8 @@ ParseRule rules[] = {
 //> Jumping Back and Forth table-and
   [TOKEN_AND]           = {NULL,     and_,   PREC_AND},
 //< Jumping Back and Forth table-and
+  [TOKEN_AS]            = {NULL,     NULL,   PREC_NONE},
+  [TOKEN_CATCH]         = {NULL,     NULL,   PREC_NONE},
   [TOKEN_CLASS]         = {NULL,     NULL,   PREC_NONE},
   [TOKEN_ELSE]          = {NULL,     NULL,   PREC_NONE},
 /* Compiling Expressions rules < Types of Values table-false
@@ -984,6 +991,7 @@ ParseRule rules[] = {
 //> Types of Values table-true
   [TOKEN_TRUE]          = {literal,  NULL,   PREC_NONE},
 //< Types of Values table-true
+  [TOKEN_TRY]           = {NULL,     NULL,   PREC_NONE},
   [TOKEN_VAR]           = {NULL,     NULL,   PREC_NONE},
   [TOKEN_WHILE]         = {NULL,     NULL,   PREC_NONE},
   [TOKEN_ERROR]         = {NULL,     NULL,   PREC_NONE},
--- a/c/scanner.c
+++ b/c/scanner.c
@@ -134,8 +134,28 @@ static TokenType checkKeyword(int start, int length,
 static TokenType identifierType() {
 //> keywords
   switch (scanner.start[0]) {
-    case 'a': return checkKeyword(1, 2, "nd", TOKEN_AND);
-    case 'c': return checkKeyword(1, 4, "lass", TOKEN_CLASS);
+    case 'a': {
+      if (scanner.current - scanner.start > 1) {
+        switch (scanner.start[1]) {
+          case 'n':
+            return checkKeyword(2, 1, "d", TOKEN_AND);
+          case 's':
+            return checkKeyword(2, 0, "", TOKEN_AS);
+        }
+      }
+      break;
+    }
+    case 'c': {
+      if (scanner.current - scanner.start > 1) {
+        switch (scanner.start[1]) {
+          case 'l':
+            return checkKeyword(2, 3, "ass", TOKEN_CLASS);
+          case 'a':
+            return checkKeyword(2, 3, "tch", TOKEN_CATCH);
+        }
+      }
+      break;
+    }
     case 'e': return checkKeyword(1, 3, "lse", TOKEN_ELSE);
 //> keyword-f
     case 'f':
@@ -170,7 +190,18 @@ static TokenType identifierType() {
             }
             break;
           }
-          case 'r': return checkKeyword(2, 2, "ue", TOKEN_TRUE);
+          case 'r': {
+            if (scanner.current - scanner.start > 2)
+            {
+              switch (scanner.start[2]) {
+                case 'u':
+                  return checkKeyword(3, 1, "e", TOKEN_TRUE);
+                case 'y':
+                  return checkKeyword(3, 0, "", TOKEN_TRY);
+              }
+            }
+            break;
+          }
         }
       }
       break;

And then comes the compiler changes to handle those blocks. As mentioned, we’re going to push and pop the exception handlers onto the stack, so let’s add the OPs for that.

--- a/c/chunk.h
+++ b/c/chunk.h
@@ -101,6 +101,8 @@ typedef enum {
   OP_METHOD,
 //< Methods and Initializers method-op
   OP_THROW,
+  OP_PUSH_EXCEPTION_HANDLER,
+  OP_POP_EXCEPTION_HANDLER,
 } OpCode;
 //< op-enum
 //> chunk-struct

And the compiler itself. This sets aside a byte for the constant representing the Exception type being handled, along with two bytes for the code address of the catch block. These will need to be patched later, which is why we’ve saved their offsets. Then it’s a normal statement, which means that the scope rules for variables will be consistent in our new kind of block, too. If the code execution reaches the end of the statement, that means we’ve successfully reached the end of the scope for the handler and can pop it off the stack. Should the statement have exited the function, then we needn’t worry about the pop, because the CallFrame will have been popped off the stack and we won’t have a reference to the handler anymore, anyway.

--- a/c/compiler.c
+++ b/c/compiler.c
@@ -294,6 +294,12 @@ static void patchJump(int offset) {
   currentChunk()->code[offset + 1] = jump & 0xff;
 }
 //< Jumping Back and Forth patch-jump
+
+static void patchAddress(int offset) {
+  currentChunk(current)->code[offset] = (currentChunk(current)->count >> 8) & 0xff;
+  currentChunk(current)->code[offset + 1] = currentChunk(current)->count & 0xff;
+}
+
 //> Local Variables init-compiler
 /* Local Variables init-compiler < Calls and Functions init-compiler
 static void initCompiler(Compiler* compiler) {
@@ -1389,6 +1398,42 @@ static void throwStatement() {
   emitByte(OP_THROW);
 }
 
+static void tryCatchStatement() {
+  emitByte(OP_PUSH_EXCEPTION_HANDLER);
+  int exceptionType = currentChunk(current)->count;
+  emitByte(0xff);
+  int handlerAddress = currentChunk(current)->count;
+  emitBytes(0xff, 0xff);
+
+  statement();
+
+  emitByte(OP_POP_EXCEPTION_HANDLER);
+  int successJump = emitJump(OP_JUMP);
+
+  if (match(TOKEN_CATCH))
+  {
+      beginScope();
+      consume(TOKEN_LEFT_PAREN, "Expect '(' after catch");
+      consume(TOKEN_IDENTIFIER, "Expect type name to catch");
+      uint8_t name = identifierConstant(&parser.previous);
+      currentChunk(current)->code[exceptionType] = name;
+      patchAddress(handlerAddress);
+      if (match(TOKEN_AS))
+      {
+        consume(TOKEN_IDENTIFIER, "Expect identifier for exception instance");
+        addLocal(parser.previous);
+        markInitialized();
+        uint8_t ex_var = resolveLocal(current, &parser.previous);
+        emitBytes(OP_SET_LOCAL, ex_var);
+      }
+      consume(TOKEN_RIGHT_PAREN, "Expect ')' after catch statement");
+      emitByte(OP_POP_EXCEPTION_HANDLER);
+      statement();
+      endScope();
+  }
+  patchJump(successJump);
+}
+
 //> Global Variables synchronize
 static void synchronize() {
   parser.panicMode = false;
@@ -1477,6 +1517,8 @@ static void statement() {
 //< Local Variables parse-block
   } else if (match(TOKEN_THROW)) {
     throwStatement();
+  } else if (match(TOKEN_TRY)) {
+    tryCatchStatement();
 //> parse-expressions-statement
   } else {
     expressionStatement();

The catch block stores the exception type, along with setting the value at the top of the stack as the named variable in the as clause. This part I’ve gone back and forth on, and I’m a little unsure about it. I know that adding a local variable is the right thing to do, so that the scope of it doesn’t escape the catch block, but I feel like I’m doing too much explicitly here, and not letting the parser choose what needs to happen. If you have any insight into this, feel free to leave a comment.

We’ll also add the debug output for the push / pop handler instructions

--- a/c/debug.c
+++ b/c/debug.c
@@ -63,6 +63,14 @@ static int jumpInstruction(const char* name, int sign,
   return offset + 3;
 }
 //< Jumping Back and Forth jump-instruction
+static int exceptionHandlerInstruction(const char *name, Chunk *chunk, int offset)
+{
+    uint8_t type = chunk->code[offset + 1];
+    uint16_t handlerAddress = (uint16_t)(chunk->code[offset + 2] << 8);
+    handlerAddress |= chunk->code[offset + 3];
+    printf("%-16s %4d -> %d\n", name, type, handlerAddress);
+    return offset + 4;
+}
 //> disassemble-instruction
 int disassembleInstruction(Chunk* chunk, int offset) {
   printf("%04d ", offset);
@@ -222,6 +230,10 @@ int disassembleInstruction(Chunk* chunk, int offset) {
 //< Methods and Initializers disassemble-method
     case OP_THROW:
       return simpleInstruction("OP_THROW", offset);
+    case OP_PUSH_EXCEPTION_HANDLER:
+      return exceptionHandlerInstruction("OP_PUSH_EXCEPTION_HANDLER", chunk, offset);
+    case OP_POP_EXCEPTION_HANDLER:
+      return simpleInstruction("OP_POP_EXCEPTION_HANDLER", offset);
     default:
       printf("Unknown opcode %d\n", instruction);
       return offset + 1;

And after that, we need to implement the runtime behaviour. This is predominantly managing the exception handler stack state, with a small addition to the propagateException function to jump to the handler if its required, telling the main run loop whether the exception has been handled, and it should refresh the frame it’s executing, or exit with an error as before.

--- a/c/vm.h
+++ b/c/vm.h
@@ -23,9 +23,15 @@
 //> Calls and Functions frame-max
 #define FRAMES_MAX 64
 #define STACK_MAX (FRAMES_MAX * UINT8_COUNT)
+#define MAX_HANDLER_FRAMES 16
 //< Calls and Functions frame-max
 //> Calls and Functions call-frame
 
+typedef struct {
+    uint16_t handlerAddress;
+    Value klass;
+} ExceptionHandler;
+
 typedef struct {
 /* Calls and Functions call-frame < Closures call-frame-closure
   ObjFunction* function;
@@ -35,6 +41,8 @@ typedef struct {
 //< Closures call-frame-closure
   uint8_t* ip;
   Value* slots;
+  uint8_t handlerCount;
+  ExceptionHandler handlerStack[MAX_HANDLER_FRAMES];
 } CallFrame;
 //< Calls and Functions call-frame
 
--- a/c/vm.c
+++ b/c/vm.c
@@ -191,14 +191,42 @@ static Value getStackTrace(void)
 #undef MAX_LINE_LENGTH
 }
 
-void propagateException(void) {
+bool instanceof(ObjInstance *instance, Value klass)
+{
+  return IS_CLASS(klass) && instance->klass == AS_CLASS(klass);
+}
+
+bool propagateException(void) {
   ObjInstance *exception = AS_INSTANCE(peek(0));
+  while (vm.frameCount > 0) {
+    CallFrame *frame = &vm.frames[vm.frameCount - 1];
+    for (int numHandlers = frame->handlerCount; numHandlers > 0; numHandlers--) {
+      ExceptionHandler handler = frame->handlerStack[numHandlers - 1];
+      if (instanceof(exception, handler.klass)) {
+        frame->ip = &frame->closure->function->chunk.code[handler.handlerAddress];
+        return true;
+      }
+    }
+    vm.frameCount--;
+  }
   fprintf(stderr, "Unhandled %s\n", exception->klass->name->chars);
   Value stacktrace;
   if (tableGet(&exception->fields, copyString("stacktrace", 10), &stacktrace)) {
     fprintf(stderr, "%s", AS_CSTRING(stacktrace));
     fflush(stderr);
   }
+  return false;
+}
+
+void pushExceptionHandler(Value type, uint16_t handlerAddress) {
+  CallFrame *frame = &vm.frames[vm.frameCount - 1];
+  if (frame->handlerCount == MAX_HANDLER_FRAMES) {
+    runtimeError("Too many nested exception handlers in one function");
+    return;
+  }
+  frame->handlerStack[frame->handlerCount].handlerAddress = handlerAddress;
+  frame->handlerStack[frame->handlerCount].klass = type;
+  frame->handlerCount++;
 }
 
 /* Calls and Functions call < Closures call-signature
@@ -924,9 +952,29 @@ static InterpretResult run() {
         Value stacktrace = getStackTrace();
         ObjInstance* instance = AS_INSTANCE(peek(0));
         tableSet(&instance->fields, copyString("stacktrace", 10), stacktrace);
-        propagateException();
+        if (propagateException())
+        {
+          frame = &vm.frames[vm.frameCount - 1];
+          break;
+        }
         return INTERPRET_RUNTIME_ERROR;
       }
+      case OP_PUSH_EXCEPTION_HANDLER: {
+        ObjString *typeName = READ_STRING();
+        uint16_t handlerAddress = READ_SHORT();
+        Value value;
+        if (!tableGet(&vm.globals, typeName, &value) || !IS_CLASS(value))
+        {
+            runtimeError("'%s' is not a type to catch", typeName->chars);
+            return INTERPRET_RUNTIME_ERROR;
+        }
+        pushExceptionHandler(value, handlerAddress);
+        break;
+      }
+      case OP_POP_EXCEPTION_HANDLER: {
+        frame->handlerCount--;
+        break;
+      }
     }
   }
 

As I was implementing this, I realised that the object model is not especially sophisticated – I don’t have easy access to the super class, so I have made a concession to exception handling, where it can only handle the exact class being thrown. A better implementation of the instanceof method is all that’s required to allow us to catch all subclasses of an exception’s type, too.

The magic is in the propagateException changes – we walk through the call stack, looking for exception handlers for our exception. If we find one, we set the handler address as the next instruction to be executed and return true to signal that the exception has been handled, and the run function should update the stack frame, which will contain the correct state already, and we’re off to the races.

With that, we can now handle exceptions as well as throw them – we’re almost all the way there. This is also useful functionality in its own right – it’s most of what we require from exception handling. Seeing what goes into handling them in a fairly simple case, I can understand pretty intimately why the standard advice is to avoid using them for flow control! Stay tuned for part 3 to complete the functionality.

Further Challenges:

  • We’ve statically defined the handler stack, trading off memory for simplicity at the end of the function. Could we change that to be dynamic memory?
  • We can only catch a single exception type in each handler – what would we need to do to catch multiple types in a single statement?
  • We haven’t implemented a re-throw statement (i.e. an empty throw inside an exception handler) how could we go about doing that?

The Serial Killer

A little over a year ago, I decided to write my own Serial Terminal.  Most people’s reaction to this is “why?”  Serial comms is a technology well on its way out, and what they see as the critical hit, a bunch of terminal programs already exist.  Many of which are even open source.  So why would I bother?

Read more of this post

Yours, sincerely embarrassed

Last week a ghost of christmas coding past came to haunt me.  Some code that I wrote two years ago was found to be broken.  I’m not surprised.  When I first heard about the issue, despite the fact that I no longer work in that team (or indeed on that code base, language or even CPU instruction set) one of the first things I did was pull up the code to take a look.

This particular area of code is quite neglected and I knew for a fact that other people had only touched it in passing, without needing to make the modifications needed for real understanding.  I’m not saying that other people couldn’t understand it, but as a release was due to happen the following day and that, despite the bug being two years old, when the symptoms are described, it sounds quite scary and speed was going to be important for fixing it.  About 1 in 20 times our security handshake would fail.  The legitimate user would be temporarily unable to configure the product.  Because of this, an impending release (due to be finalised the following day) would be put at risk.  So my experience in this area meant that I could immediately narrow the bug to two or three files in the whole repository and I knew more or less how they fitted together.  Speed boost, achieved.

Read more of this post