Interpreter Exception Handling, Part 3

Today we tackle the finally block. The trick with the finally block, is that it must always run. That’s not a surprise in and of itself, but remember, that doesn’t just apply to the exception handler that’s currently in scope, it applies to every single exception handler that has a finally block above the place where the exception is eventually handled.

This post is part 3 of 3 of Interpreter Exception Handling – here is part 1 and part 2.

So we need to know which exception handlers currently in scope have a finally block attached. We already know which handlers are in scope for each stack frame, but haven’t made any allowance for ‘finally’ stuff. Let’s fix that. First we need to detect the syntax, so here are the normal bits:

--- a/c/compiler.c
+++ b/c/compiler.c
@@ -956,6 +956,7 @@ ParseRule rules[] = {
 //> Types of Values table-false
   [TOKEN_FALSE]         = {literal,  NULL,   PREC_NONE},
 //< Types of Values table-false
+  [TOKEN_FINALLY]       = {NULL,     NULL,   PREC_NONE},
   [TOKEN_FOR]           = {NULL,     NULL,   PREC_NONE},
   [TOKEN_FUN]           = {NULL,     NULL,   PREC_NONE},
   [TOKEN_IF]            = {NULL,     NULL,   PREC_NONE},
--- a/c/scanner.c
+++ b/c/scanner.c
@@ -162,6 +162,7 @@ static TokenType identifierType() {
       if (scanner.current - scanner.start > 1) {
         switch (scanner.start[1]) {
           case 'a': return checkKeyword(2, 3, "lse", TOKEN_FALSE);
+          case 'i': return checkKeyword(2, 5, "nally", TOKEN_FINALLY);
           case 'o': return checkKeyword(2, 1, "r", TOKEN_FOR);
           case 'u': return checkKeyword(2, 1, "n", TOKEN_FUN);
         }
--- a/c/scanner.h
+++ b/c/scanner.h
@@ -21,7 +21,7 @@ typedef enum {
 
   // Keywords.
   TOKEN_AND, TOKEN_AS, TOKEN_CATCH, TOKEN_CLASS, TOKEN_ELSE, TOKEN_FALSE,
-  TOKEN_FOR, TOKEN_FUN, TOKEN_IF, TOKEN_NIL, TOKEN_OR,
+  TOKEN_FINALLY, TOKEN_FOR, TOKEN_FUN, TOKEN_IF, TOKEN_NIL, TOKEN_OR,
   TOKEN_PRINT, TOKEN_RETURN, TOKEN_SUPER, TOKEN_THIS,
   TOKEN_THROW, TOKEN_TRUE, TOKEN_TRY, TOKEN_VAR, TOKEN_WHILE,

Previously I said that the propagate exception function would come in handy during this post. And it’s kind of pivotal to the finally block. Because as we move through the stack frames, we need to check for the finally block, execute it – and here’s the catch (pun intended) – continue stepping through the stack exactly after the finally block, even if there is more code in the function. To make that happen, I’m going to introduce an instruction to continue the exception propagation. Unsurprisingly, I will call it: OP_PROPAGATE_EXCEPTION

--- a/c/chunk.h
+++ b/c/chunk.h
@@ -103,6 +103,7 @@ typedef enum {
   OP_THROW,
   OP_PUSH_EXCEPTION_HANDLER,
   OP_POP_EXCEPTION_HANDLER,
+  OP_PROPAGATE_EXCEPTION,
 } OpCode;
 //< op-enum
 //> chunk-struct
--- a/c/debug.c
+++ b/c/debug.c
@@ -68,8 +68,10 @@ static int exceptionHandlerInstruction(const char *name, Chunk *chunk, int offse
     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;
+    uint16_t finallyAddress = (uint16_t)(chunk->code[offset + 4] << 8);
+    finallyAddress |= chunk->code[offset + 5];
+    printf("%-16s %4d -> %d, %d\n", name, type, handlerAddress, finallyAddress);
+    return offset + 6;
 }
 //> disassemble-instruction
 int disassembleInstruction(Chunk* chunk, int offset) {
@@ -234,6 +236,8 @@ int disassembleInstruction(Chunk* chunk, int offset) {
       return exceptionHandlerInstruction("OP_PUSH_EXCEPTION_HANDLER", chunk, offset);
     case OP_POP_EXCEPTION_HANDLER:
       return simpleInstruction("OP_POP_EXCEPTION_HANDLER", offset);
+    case OP_PROPAGATE_EXCEPTION:
+      return simpleInstruction("OP_PROPAGATE_EXCEPTION", offset);
     default:
       printf("Unknown opcode %d\n", instruction);
       return offset + 1;

Then in the compiler, first we find the finally block, we make sure the runtime knows where to find it, in case it needs to be executed outside of the normal flow. There’s a little trick in there that means we will only execute the OP_PROPAGATE_EXCEPTION under the right conditions (which depend on how we enter the block). Then it’s the statement to actually be the block – which can be either a single statement or a whole block. Crucially, a statement doesn’t leave any result left on the stack (unlike an expression), so we know that there’s nothing on the top of the stack after the execution of that statement except for the boolean we placed there, earlier.

--- a/c/compiler.c
+++ b/c/compiler.c
@@ -1404,6 +1405,8 @@ static void tryCatchStatement() {
   emitByte(0xff);
   int handlerAddress = currentChunk(current)->count;
   emitBytes(0xff, 0xff);
+  int finallyAddress = currentChunk(current)->count;
+  emitBytes(0xff, 0xff);
 
   statement();
 
@@ -1419,14 +1422,34 @@ static void tryCatchStatement() {
       emitByte(OP_POP_EXCEPTION_HANDLER);
       statement();
   }
   patchJump(successJump);
+
+  if (match(TOKEN_FINALLY))
+  {
+    // If we arrive here from either the try or handler blocks, then we don't
+    // want to continue propagating the exception
+    emitByte(OP_FALSE);
+
+    patchAddress(finallyAddress);
+    statement();
+
+    int continueExecution = emitJump(OP_JUMP_IF_FALSE);
+    emitByte(OP_POP); // Pop the bool off the stack
+    emitByte(OP_PROPAGATE_EXCEPTION);
+    patchJump(continueExecution);
+    emitByte(OP_POP);
+  }
 }
 
 //> Global Variables synchronize

And now we hook it all together. Teach the runtime to add the finally address to the exception handler stack, and then add the very humble propagate exception implementation, which essentially just calls the propagateException() function.

--- a/c/vm.h
+++ b/c/vm.h
@@ -29,6 +29,7 @@
 
 typedef struct {
     uint16_t handlerAddress;
+    uint16_t finallyAddress;
     Value klass;
 } ExceptionHandler;
 
--- a/c/vm.c
+++ b/c/vm.c
@@ -197,6 +197,7 @@ bool instanceof(ObjInstance *instance, Value klass)
 }
 
 bool propagateException(void) {
+  #define PLACEHOLDER_ADDRESS 0xffff
   ObjInstance *exception = AS_INSTANCE(peek(0));
   while (vm.frameCount > 0) {
     CallFrame *frame = &vm.frames[vm.frameCount - 1];
@@ -206,6 +207,12 @@ bool propagateException(void) {
         frame->ip = &frame->closure->function->chunk.code[handler.handlerAddress];
         return true;
       }
+      else if (handler.finallyAddress != PLACEHOLDER_ADDRESS)
+      {
+        push(TRUE_VAL); // continue propagating once the finally block completes
+        frame->ip = &frame->closure->function->chunk.code[handler.finallyAddress];
+        return true;
+      }
     }
     vm.frameCount--;
   }
@@ -218,13 +225,14 @@ bool propagateException(void) {
   return false;
 }
 
-void pushExceptionHandler(Value type, uint16_t handlerAddress) {
+void pushExceptionHandler(Value type, uint16_t handlerAddress, uint16_t finallyAddress) {
   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].finallyAddress = finallyAddress;
   frame->handlerStack[frame->handlerCount].klass = type;
   frame->handlerCount++;
 }
@@ -962,19 +970,29 @@ static InterpretResult run() {
       case OP_PUSH_EXCEPTION_HANDLER: {
         ObjString *typeName = READ_STRING();
         uint16_t handlerAddress = READ_SHORT();
+        uint16_t finallyAddress = 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);
+        pushExceptionHandler(value, handlerAddress, finallyAddress);
         break;
       }
       case OP_POP_EXCEPTION_HANDLER: {
         frame->handlerCount--;
         break;
       }
+      case OP_PROPAGATE_EXCEPTION: {
+        frame->handlerCount--;
+        if (propagateException())
+        {
+          frame = &vm.frames[vm.frameCount - 1];
+          break;
+        }
+        return INTERPRET_RUNTIME_ERROR;
+      }
     }
   }
 

So that’s it. Deceptively simple, but it took me a bunch of work and rework to get there. I hope you found this helpful, and a big congratulations to anyone who made it this far. If you have any questions, or feel like I didn’t explain things well enough, feel free to comment below.

Advertisement

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?

Interpreter Exception Handling Implementation, Part 1

Recently, I read the book crafting interpreters by Bob Nystrom (@munificent) and like many other interpreter tutorials it stops short of implementing exception handling, citing complexity. Given that the book already implements its target language twice, and after implementing it, I will break this into three posts, I can agree that it would make the book a bit too long. I mean, the Dragon Book doesn’t even cover it. However, there’s nothing stopping me from writing these posts, so I’m gonna do that.

I am assuming you’ve read the book and have an otherwise vanilla copy of the C implementation of the ‘lox’ language. I’ve used a clone from the book’s repo, which includes book markup in the code, and might yet be further updated. The code snippets are patches, which in theory will apply cleanly if so desired, but I recommend doing it The Hard Way. I’m keeping with the book’s tenet of including every line of code, so these posts will be code-heavy.

disclaimer:
This should not be considered a reference implementation, it’s the first thing I came up with after reading the Python interpreter’s source code and discovering that their approach wouldn’t fit the clox implementation directly, but clearly inspires the result. It therefore might not be super efficient or even a good way of doing it, but it is a way that works.

When I talk about exception handling, I intend to mimic the behaviour of most other languages that support such a feature (C++ being the notable exception). So let’s start with the throw keyword – it should signify that the result of the following expression is to be thrown like an exception.

--- a/c/scanner.h
+++ b/c/scanner.h
@@ -23,7 +23,7 @@ typedef enum {
   TOKEN_AND, 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_TRUE, TOKEN_VAR, TOKEN_WHILE,
+  TOKEN_THROW, TOKEN_TRUE, TOKEN_VAR, TOKEN_WHILE,
 
   TOKEN_ERROR,
   TOKEN_EOF
--- a/c/scanner.c
+++ b/c/scanner.c
@@ -158,7 +158,18 @@ static TokenType identifierType() {
     case 't':
       if (scanner.current - scanner.start > 1) {
         switch (scanner.start[1]) {
-          case 'h': return checkKeyword(2, 2, "is", TOKEN_THIS);
+          case 'h': {
+            if (scanner.current - scanner.start > 2)
+            {
+              switch (scanner.start[2]) {
+                case 'i':
+                  return checkKeyword(3, 1, "s", TOKEN_THIS);
+                case 'r':
+                  return checkKeyword(3, 2, "ow", TOKEN_THROW);
+              }
+            }
+            break;
+          }
           case 'r': return checkKeyword(2, 2, "ue", TOKEN_TRUE);
         }
       }
--- a/c/compiler.c
+++ b/c/compiler.c
@@ -980,6 +980,7 @@ ParseRule rules[] = {
 /* Compiling Expressions rules < Types of Values table-true
   [TOKEN_TRUE]          = {NULL,     NULL,   PREC_NONE},
 */
+  [TOKEN_THROW]         = {NULL,     NULL,   PREC_NONE},
 //> Types of Values table-true
   [TOKEN_TRUE]          = {literal,  NULL,   PREC_NONE},
 //< Types of Values table-true

That covers the normal process of adding a new token – adding the token type, scanner support and ensuring that the Pratt Parser table is updated.

Now that we know about the token, we should handle it in the compiler. This also means a new VM operation which we will output to do the actual throwing.

--- a/c/chunk.h
+++ b/c/chunk.h
@@ -98,8 +98,9 @@ typedef enum {
   OP_INHERIT,
 //< Superclasses inherit-op
 //> Methods and Initializers method-op
-  OP_METHOD
+  OP_METHOD,
 //< Methods and Initializers method-op
+  OP_THROW,
 } OpCode;
 //< op-enum
 //> chunk-struct
--- a/c/compiler.c
+++ b/c/compiler.c
@@ -1381,6 +1382,13 @@ static void whileStatement() {
   emitByte(OP_POP);
 }
 //< Jumping Back and Forth while-statement
+
+static void throwStatement() {
+  expression();
+  consume(TOKEN_SEMICOLON, "Expect ';' after value.");
+  emitByte(OP_THROW);
+}
+
 //> Global Variables synchronize
 static void synchronize() {
   parser.panicMode = false;
@@ -1397,6 +1405,7 @@ static void synchronize() {
       case TOKEN_WHILE:
       case TOKEN_PRINT:
       case TOKEN_RETURN:
+      case TOKEN_THROW:
         return;
 
       default:
@@ -1466,6 +1475,8 @@ static void statement() {
     block();
     endScope();
 //< Local Variables parse-block
+  } else if (match(TOKEN_THROW)) {
+    throwStatement();
 //> parse-expressions-statement
   } else {
     expressionStatement();

It’s pretty straight-forward. Find a throw and output an OP_THROW once the expression forming the argument is complete and the result is on top of the stack. Of course the lox language finishes statements with semi-colons, so expect one of those, too. The throw statement is also a convenient place to synchronize, so we’ll go ahead and put it there, too.

Once we have the instruction output to the vm, it’d be pretty useful to see what’s happening in the debug output, so let’s add that.

--- a/c/debug.c
+++ b/c/debug.c
@@ -220,6 +220,8 @@ int disassembleInstruction(Chunk* chunk, int offset) {
     case OP_METHOD:
       return constantInstruction("OP_METHOD", chunk, offset);
 //< Methods and Initializers disassemble-method
+    case OP_THROW:
+      return simpleInstruction("OP_THROW", offset);
     default:
       printf("Unknown opcode %d\n", instruction);
       return offset + 1;

We have to deal with the actual functionality of that in the virtual machine. I’ve added two functions to do this, which each use a little foresight from the complete implementation. Getting the stacktrace from the exact place the exception is thrown is pretty important for tracing the exceptions, so we’ll do that as a separate task that doesn’t alter the call stack. Lox doesn’t have arrays (or lists) so we’re returning a newline-separated string. It’s pretty heavy on allocations, so don’t expect to be able to throw an out-of-memory exception and have the interpreter behave sensibly. Of course the functions you can safely call in such a scenario are pretty limited, and printf is not on that list. Allowing the program to crash in that scenario is a reasonable approach.

--- a/c/vm.c
+++ b/c/vm.c
@@ -165,6 +165,42 @@ static Value peek(int distance) {
   return vm.stackTop[-1 - distance];
 }
 //< Types of Values peek
+
+static Value getStackTrace(void)
+{
+#define MAX_LINE_LENGTH 512
+  int maxStackTraceLength = vm.frameCount * MAX_LINE_LENGTH;
+  char *stacktrace = ALLOCATE(char, maxStackTraceLength);
+  uint16_t index = 0;
+  for (int i = vm.frameCount - 1; i >= 0; i--)
+  {
+      CallFrame *frame = &vm.frames[i];
+      ObjFunction *function = frame->closure->function;
+      // -1 because the IP is sitting on the next instruction to be executed.
+      size_t instruction = frame->ip - function->chunk.code - 1;
+      uint32_t lineno = function->chunk.lines[instruction];
+      index += snprintf(
+          &stacktrace[index],
+          MAX_LINE_LENGTH,
+          "[line %d] in %s()\n",
+          lineno,
+          function->name == NULL ? "script" : function->name->chars);
+  }
+  stacktrace = GROW_ARRAY(char, stacktrace, maxStackTraceLength, index);
+  return OBJ_VAL(takeString(stacktrace, index));
+#undef MAX_LINE_LENGTH
+}
+
+void propagateException(void) {
+  ObjInstance *exception = AS_INSTANCE(peek(0));
+  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);
+  }
+}
+
 /* Calls and Functions call < Closures call-signature
 static bool call(ObjFunction* function, int argCount) {
 */

The getStackTrace function walks the call stack and traces the path to how we got where we are, noting the function names and line numbers as we go. We’ve made a concession that a line will never be more than 512 characters long, which is probably long enough. We do resize the string to the exact space used at the end of the function, so at least we aren’t wasting space eventually.

propagateException is pretty simple at this stage. It tells the user which type was thrown and attempts to get a field called stacktrace that is a string, and prints that out. In practice, because this is a dynamic language, this means we can throw any object type and we’ll set that during the OP_THROW handling. I haven’t included guards for attempting to throw a value-type like a bool or number.

--- a/c/vm.c
+++ b/c/vm.c
@@ -884,6 +920,13 @@ static InterpretResult run() {
         defineMethod(READ_STRING());
         break;
 //< Methods and Initializers interpret-method
+      case OP_THROW: {
+        Value stacktrace = getStackTrace();
+        ObjInstance* instance = AS_INSTANCE(peek(0));
+        tableSet(&instance->fields, copyString("stacktrace", 10), stacktrace);
+        propagateException();
+        return INTERPRET_RUNTIME_ERROR;
+      }
     }
   }

And that’s throwing exceptions. Because we can’t catch exceptions, yet, we always return an error once we encounter an instruction to throw an exception.

While this doesn’t introduce full exception handling, this on its own is still useful. We can now exit lox programs early with an error condition if we detect something has gone wrong, giving an insight to the user as to how we got where the problem occurred.

Futher challenges:

  • How could we minimise the amount of memory allocated for the stacktrace string? What are the trade-offs imposed?
  • What should we do in the case that a user attempts to throw a value-type?

Stay tuned for part 2 and part 3.

Linux Conf Au – 2019

The yearly reminder that we need to question our values as programmers has come and gone again. That’s right – the far left of the programming world has come to remind us of the Four Freedoms and how most of us there like the idea of them, but fundamentally earn a paycheck either not respecting them, or outright disregarding them. Aside from cognitive dissonance, I did learn some very interesting things – some of which are even applicable to my day-to-day job!

The best one-liner of the conference goes to Stewart Smith, who was describing how boot loaders were becoming much more complex, how they have to verify a signed image over a constrained bus before the main memory was brought up, and how that was a difficult problem. Upon being asked why he didn’t just use UEFI as it was a solved problem, he replied “because everyone who holds UEFI finds that it doesn’t spark joy”.

The most applicable talk that I went to, was given by Katie McLaughlin – an Operations Engineer who has learned through experience how to “Be kind to 3am you”. This is, of course, a talk on the lessons learned to help you resolve issues in production when the pager goes off at 3am when few people are at their best.

She explains that where the documentation lives is important – it should be the default place that you go to every day. If your fingers “just know” from muscle memory how to search the documentation when you are both desperately in need of coffee, but stubbornly refusing it in the hope that the issue will be resolved soon and sleep might be an option in the near future, then your life is infinitely better. The instructions also need to be clear for similar reasons.

The theme of the talk was that generally lowering the cognitive load required to address the situation was the main objective. Having commands that you can copy and paste from a document and run without any change is ideal. For example, docker –stats is subtly different to docker –status ”Don’t run with scissors” was the advice – don’t do dangerous things because you feel like you need to get somewhere fast.

The piece of learning that I thought would be useful, was that when we are setting up alerts in our monitoring software, that we should include a link to the documentation that helps to resolve it in the alert itself. If it doesn’t exist, we should create it – we are alerting for a known reason, so we should know ways to mitigate / resolve the issue.

Oh and I almost forgot – we should consider saving a sanitized bash history directly in the post mortems – it gives a clearer idea of what we did (human memory is terribly unreliable) and gives juniors / new employees a starting point for learning how to handle things.

The talk that was the most interesting gedankenexperiment was where Peter Chubb played with the idea of writing a distributed filesystem using an RDBMS as the underlying storage. The idea is relatively simple – configure the database to use raw disk (rather than pay the penalty for a filesystem layered on a filesystem) and then implement the POSIX interfaces with a combination of FUSE and SQL. Simple, right? Well, the performance was fairly poor, but yes, he managed to have it more or less work and be more or less POSIX compatible.

The two talks that encouraged the most self-reflection we “I’m sorry Dave, I can’t do that – ethics in software development” by Dr Morgan Leigh and “Facebook, Dynamite, Uber, Bombs and you” by Lana Brindley. Each were reminding us that we, as software professionals, wield a large amount of power and could we please try to grow our morality glands. Software basically gets away with anything because there is neither a governing organization holding us to specific standards (such as the FAA for aviation) nor the understanding that software can be held accountable for such things. It didn’t take too many bridge collapses before engineers got oversight, so why is it that software is getting away with so much? These are the philosophical questions posed alongside the plea to realise that each of us can make moral choices – walking away from a job is not nearly as much of a burden to us as it might be for other professions.

A special mention should go to “Autopsy of a Browser” by Erin Zimmer, which detailed the history of browsers from the very first one written by Sir Tim Berners-Lee at Cern to the modern day, where everyone seems to be converging on using the <blink> HTML engine from the chromium project (with a couple of notable exceptions) with the warning that we’re repeating the history of 2001-2006 where Internet Explorer 6 dominated and the web stagnated as a consequence. Personally, I think the talk was much closer to a homicide investigation, or possibly a war crimes tribunal. Autopsy just doesn’t have the grand scale that she talked about. Her talk did, however, nicely explain why some of the HTML today is the way it is (most notably the img tag). Market share and stubbornness.

But the two stand-out talks that I didn’t expect to be so well presented or approachable were “The Kernel Report” by Jon Corbet and “The tragedy of Systemd” by Benno Rice. I have seen each of them give conference talks before, so I shouldn’t be surprised that they were skilled presenters, but I was mostly surprised given their topics. With tech that would have been very tempting to wander off into the deep bowels of linux as their subjects, each of them managed to make their talks approachable to the likes of me, who has never contributed a patch to either system, and found a great sense of pride in being able to just compile a kernel in my younger days, when I had the time and energy for such whimsy.

Both talks were approached with similar levels of empathy to the aforementioned philosophical discussions, which feel like they would somehow be easier to approach in that manner. Though I can’t actually explain why, and I wonder if that’s me being biased, given that each of those two were presented by women, whereas these two were presented by men and perhaps they should get some sort of bonus for not acting like unsympathetic techno-philes.

I guess now is the time I wrap up, but before I do, I will mention the organisers – they did a fantastic job. There were some things that I would have done differently, but differently is not necessarily better, and I’m sure they did what they could with the resources they had. Overall it was a well-oiled machine, with the ultimate proof being that all the talks (as far as I’m aware) happened at the time specified, were recorded and began appearing online with less than 24 hour lags. As far as conference metrics go, you can’t do much better than that. So I enjoyed being reminded that I have a morality gland and I should choose to wield the incredible amount of power that I have for good. I am a straight white male in software, after all.

State of the Nation

Well, it’s been more than a whole year since we last spoke – can you believe that?  I guess it’s time for a round up.

So what have I been up to?  Well, last time, I was telling you how I left my first job.  Since then, I’ve also left my second.  Yes, I know.  It was a bit of a mis-step on my behalf, but I learned an awful lot about how to interview a company and as such I am perfectly happy where I am.

Moving back half a step – I want to explain why I left my other job.  It seemed so full of promise – I was getting paid roughly one and a half times the salary for slightly less responsibility doing what I thought was going to be more or less the same thing.  I was wrong.  So very, very wrong.  Turns out there was a miscommunication.  There was a small portion of ASP.NET (which is what I was primarily looking for) but it was WebForms, on .NET v3.0 (we didn’t even have linq!).  I didn’t realise WebForms even fell under the ASP.NET umbrella until then.  But the core product that I had been hired to work on was, again .NET v3.0, and WinForms this time (see a pattern here?).  Yes, I can do a bunch more with WinForms now that I couldn’t before, out of necessity.  But it was so awful.  Theoretically, the code was structured as MVP, except it had one fatal flaw – there was a static dependency in the constructor of the base Presenter that we weren’t allowed to refactor, because it was part of the security system and the whole product security would need to be retested because of it.  Manually tested, I mean, because this particular design flaw meant that unit tests were near impossible.  Let that sink in for a second.  Unit Tests were near-impossible on a Presenter.  Can anyone tell me one of the major reasons we go to such lengths to structure our code such that the logic isn’t in the View?  That’s right, it’s because Views are notoriously difficult and fragile to test.  A couple of us were quite unhappy with that situation and started extracting our logic into “helper” classes and also dumping it directly into the view, because somewhat paradoxically, they were easier to unit test.  Of course, the boss was unhappy with this sort of pattern emerging and we were discouraged from doing it.  It was that systemic style of thinking and a the “everything stops for 6 weeks when we release because the whole app needs to be manually tested” (and inevitably fixed) problem that they couldn’t see would be extremely mitigated by allowing the most basic unit testing that made me just want to get out of there as soon as possible.

What did I learn about interviewing at a new company?  Trust your instincts.  There were a couple of moments in the interview process that made me somewhat uncomfortable for the level I was being hired at.  Notably, they gave me a written C# test.  A. Written. Test. For an intermediate position (I shouldn’t have accepted anything less than senior, but ignore that).  It wasn’t coding to see how I solved the problem, it was literally a checklist for feature knowledge of C#.  In comparison, the company I am at now gave me a problem on a piece of paper and asked me to have a think about it, produce a design for a solution, and come and talk about it.  They are one of those vanishingly rare companies who hire developers comfortable that a half-way decent developer will pick up the language / technologies as they go.

There was also a moment during the interviews for the “old” job where I asked to meet the potential team I would be working with – a totally reasonable request – and I was very skillfully brushed aside.  So skillfully that I didn’t notice until I got home, but by then I had already been sold on the business.  Never mind.

Ok, maybe I’ve blathered on about that particular part of my career long enough.  It only lasted 6 months in the end – I made myself wait 3 months before I started looking elsewhere; took 2 months to find a new job, and then 1 month of notice period.  I’ve now been at my “new” job more than one and a half times the entire tenure at my “old” job and it still seems a much shorter time.

So about my new job.  It’s all a bit weird – I have become one of the things I swore I never would: A Web Developer.  I live in ES2015+ (new JavaScript for the layperson) for much of the time, writing a heavy-weight front end that loads just shy of 2MB before it does anything useful.  When I say heavy-weight, I mean my perceptions on how much code should be loaded over the network to run a site.  It’s actually positively average.  Being a software blog, I’ll share some of the gory details:

  • SPA written in ES2015+
  • Uses the Aurelia js framework for the front end (node / gulp / babel / jspm stack)
  • bootstrap based CSS
  • ASP.NET Web Api / NServiceBus / RavenDB / MSSQLServer for the backend.

I’ve learned an awful lot about JavaScript, browsers, CSS and even some of the more intricate features of recent versions of SQLServer.  I’ve had to learn so much about Aurelia (often by reading the source code) that I frequently hang out in the Gitter channel helping other people out.  Often learning things myself just by being there.

Which brings me to the other thing I like about this job – it’s more actively encouraging Open Source use, to the point where I have produced a plugin for the Aurelia framework.  And people actually use it!!  The company itself has a couple of plugins which it has open-sourced, but I have no idea whether people are using it – no one is raising issues or pull requests.  Doesn’t matter, we use them extensively.

It’s not to say that this new place doesn’t have its own problems.  I’m not wandering around with permanent rose-tinted glasses.  Unfortunately I can’t go into those details, on account of most of them being commercially sensitive.  Maybe once this current kerfuffle has blown over.

Also, personally this has been an exciting time for me – I’ve bought a house, adopted a kitten, and got engaged (she takes up the spare time I would have otherwise spent on blogging – if you want to complain that I don’t write much anymore, please direct all correspondence to her).  But again, software blog, so I’ll leave it at that.