Rework exception handling in the VM (#10544)

* Rework exception handling in the VM

Make the safepoint handling more precise and less forgiving.
The new code is clearer and more commented.
Perform cleanup on `return`.
The no-exception-thrown case in a try block should be slightly faster
since we don't parse the whole set of exceptions every time.
More tests.

* Fix silly error that broke a few tests

* Testament doesn't like files having the same name

* Remove test case that failed compilation to js

1 files changed, 156 insertions, 101 deletions

diff --git a/compiler/vm.nim b/compiler/vm.nim
index 71fd2722b..f855da0cc 100644
--- a/compiler/vm.nim
+++ b/compiler/vm.nim
@@ -23,7 +23,7 @@ from evaltempl import evalTemplate
 from modulegraphs import ModuleGraph, PPassContext
 
 const
-  traceCode = debugEchoCode
+  traceCode = defined(nimVMDebug)
 
 when hasFFI:
   import evalffi
@@ -259,64 +259,101 @@ proc pushSafePoint(f: PStackFrame; pc: int) =
   f.safePoints.add(pc)
 
 proc popSafePoint(f: PStackFrame) =
-  # XXX this needs a proper fix!
-  if f.safePoints.len > 0:
-    discard f.safePoints.pop()
-
-proc cleanUpOnException(c: PCtx; tos: PStackFrame):
-                                              tuple[pc: int, f: PStackFrame] =
-  let raisedType = c.currentExceptionA.typ.skipTypes(abstractPtrs)
-  var f = tos
-  while true:
-    while f.safePoints.len == 0:
-      f = f.next
-      if f.isNil: return (-1, nil)
-    var pc2 = f.safePoints[f.safePoints.high]
-
-    var nextExceptOrFinally = -1
-    if c.code[pc2].opcode == opcExcept:
-      nextExceptOrFinally = pc2 + c.code[pc2].regBx - wordExcess
-      inc pc2
-    while c.code[pc2].opcode == opcExcept:
-      let excIndex = c.code[pc2].regBx-wordExcess
-      let exceptType = if excIndex > 0: c.types[excIndex].skipTypes(
-                          abstractPtrs)
-                       else: nil
-      #echo typeToString(exceptType), " ", typeToString(raisedType)
-      if exceptType.isNil or inheritanceDiff(raisedType, exceptType) <= 0:
-        # mark exception as handled but keep it in B for
-        # the getCurrentException() builtin:
-        c.currentExceptionB = c.currentExceptionA
-        c.currentExceptionA = nil
-        # execute the corresponding handler:
-        while c.code[pc2].opcode == opcExcept: inc pc2
-        discard f.safePoints.pop
-        return (pc2, f)
-      inc pc2
-      if c.code[pc2].opcode != opcExcept and nextExceptOrFinally >= 0:
-        # we're at the end of the *except list*, but maybe there is another
-        # *except branch*?
-        pc2 = nextExceptOrFinally+1
-        if c.code[pc2].opcode == opcExcept:
-          nextExceptOrFinally = pc2 + c.code[pc2].regBx - wordExcess
-
-    if nextExceptOrFinally >= 0:
-      pc2 = nextExceptOrFinally
-    if c.code[pc2].opcode == opcFinally:
-      # execute the corresponding handler, but don't quit walking the stack:
-      discard f.safePoints.pop
-      return (pc2+1, f)
-    # not the right one:
-    discard f.safePoints.pop
+  discard f.safePoints.pop()
+
+type
+  ExceptionGoto = enum
+    ExceptionGotoHandler,
+    ExceptionGotoFinally,
+    ExceptionGotoUnhandled
+
+proc findExceptionHandler(c: PCtx, f: PStackFrame, exc: PNode):
+  tuple[why: ExceptionGoto, where: int] =
+  let raisedType = exc.typ.skipTypes(abstractPtrs)
+
+  while f.safePoints.len > 0:
+    var pc = f.safePoints.pop()
+
+    var matched = false
+    var pcEndExcept = pc
+
+    # Scan the chain of exceptions starting at pc.
+    # The structure is the following:
+    # pc - opcExcept, <end of this block>
+    #      - opcExcept, <pattern1>
+    #      - opcExcept, <pattern2>
+    #        ...
+    #      - opcExcept, <patternN>
+    #      - Exception handler body
+    #    - ... more opcExcept blocks may follow
+    #    - ... an optional opcFinally block may follow
+    #
+    # Note that the exception handler body already contains a jump to the
+    # finally block or, if that's not present, to the point where the execution
+    # should continue.
+    # Also note that opcFinally blocks are the last in the chain.
+    while c.code[pc].opcode == opcExcept:
+      # Where this Except block ends
+      pcEndExcept = pc + c.code[pc].regBx - wordExcess
+      inc pc
+
+      # A series of opcExcept follows for each exception type matched
+      while c.code[pc].opcode == opcExcept:
+        let excIndex = c.code[pc].regBx - wordExcess
+        let exceptType =
+          if excIndex > 0: c.types[excIndex].skipTypes(abstractPtrs)
+          else: nil
+
+        # echo typeToString(exceptType), " ", typeToString(raisedType)
+
+        # Determine if the exception type matches the pattern
+        if exceptType.isNil or inheritanceDiff(raisedType, exceptType) <= 0:
+          matched = true
+          break
+
+        inc pc
+
+      # Skip any further ``except`` pattern and find the first instruction of
+      # the handler body
+      while c.code[pc].opcode == opcExcept:
+        inc pc
+
+      if matched:
+        break
+
+      # If no handler in this chain is able to catch this exception we check if
+      # the "parent" chains are able to. If this chain ends with a `finally`
+      # block we must execute it before continuing.
+      pc = pcEndExcept
+
+    # Where the handler body starts
+    let pcBody = pc
+
+    if matched:
+      return (ExceptionGotoHandler, pcBody)
+    elif c.code[pc].opcode == opcFinally:
+      # The +1 here is here because we don't want to execute it since we've
+      # already pop'd this statepoint from the stack.
+      return (ExceptionGotoFinally, pc + 1)
+
+  return (ExceptionGotoUnhandled, 0)
 
 proc cleanUpOnReturn(c: PCtx; f: PStackFrame): int =
-  for s in f.safePoints:
-    var pc = s
+  # Walk up the chain of safepoints and return the PC of the first `finally`
+  # block we find or -1 if no such block is found.
+  # Note that the safepoint is removed once the function returns!
+  result = -1
+
+  # Traverse the stack starting from the end in order to execute the blocks in
+  # the inteded order
+  for i in 1 .. f.safePoints.len:
+    var pc = f.safePoints[^i]
+    # Skip the `except` blocks
     while c.code[pc].opcode == opcExcept:
-      pc = pc + c.code[pc].regBx - wordExcess
+      pc += c.code[pc].regBx - wordExcess
     if c.code[pc].opcode == opcFinally:
-      return pc
-  return -1
+      discard f.safePoints.pop
+      return pc + 1
 
 proc opConv(c: PCtx; dest: var TFullReg, src: TFullReg, desttyp, srctyp: PType): bool =
   if desttyp.kind == tyString:
@@ -449,6 +486,9 @@ const
 proc rawExecute(c: PCtx, start: int, tos: PStackFrame): TFullReg =
   var pc = start
   var tos = tos
+  # Used to keep track of where the execution is resumed.
+  var savedPC = -1
+  var savedFrame: PStackFrame
   var regs: seq[TFullReg] # alias to tos.slots for performance
   move(regs, tos.slots)
   #echo "NEW RUN ------------------------"
@@ -456,27 +496,31 @@ proc rawExecute(c: PCtx, start: int, tos: PStackFrame): TFullReg =
     #{.computedGoto.}
     let instr = c.code[pc]
     let ra = instr.regA
-    #if c.traceActive:
+
     when traceCode:
       echo "PC ", pc, " ", c.code[pc].opcode, " ra ", ra, " rb ", instr.regB, " rc ", instr.regC
-      # message(c.config, c.debug[pc], warnUser, "Trace")
 
     case instr.opcode
     of opcEof: return regs[ra]
     of opcRet:
-      # XXX perform any cleanup actions
-      pc = tos.comesFrom
-      tos = tos.next
-      let retVal = regs[0]
-      if tos.isNil:
-        #echo "RET ", retVal.rendertree
-        return retVal
-
-      move(regs, tos.slots)
-      assert c.code[pc].opcode in {opcIndCall, opcIndCallAsgn}
-      if c.code[pc].opcode == opcIndCallAsgn:
-        regs[c.code[pc].regA] = retVal
-        #echo "RET2 ", retVal.rendertree, " ", c.code[pc].regA
+      let newPc = c.cleanUpOnReturn(tos)
+      # Perform any cleanup action before returning
+      if newPc < 0:
+        pc = tos.comesFrom
+        tos = tos.next
+        let retVal = regs[0]
+        if tos.isNil:
+          return retVal
+
+        move(regs, tos.slots)
+        assert c.code[pc].opcode in {opcIndCall, opcIndCallAsgn}
+        if c.code[pc].opcode == opcIndCallAsgn:
+          regs[c.code[pc].regA] = retVal
+      else:
+        savedPC = pc
+        savedFrame = tos
+        # The -1 is needed because at the end of the loop we increment `pc`
+        pc = newPc - 1
     of opcYldYoid: assert false
     of opcYldVal: assert false
     of opcAsgnInt:
@@ -1025,7 +1069,7 @@ proc rawExecute(c: PCtx, start: int, tos: PStackFrame): TFullReg =
         # it's a callback:
         c.callbacks[-prc.offset-2].value(
           VmArgs(ra: ra, rb: rb, rc: rc, slots: cast[pointer](regs),
-                 currentException: c.currentExceptionB,
+                 currentException: c.currentExceptionA,
                  currentLineInfo: c.debug[pc]))
       elif sfImportc in prc.flags:
         if allowFFI notin c.features:
@@ -1118,44 +1162,55 @@ proc rawExecute(c: PCtx, start: int, tos: PStackFrame): TFullReg =
       tos.pushSafePoint(pc + rbx)
       assert c.code[pc+rbx].opcode in {opcExcept, opcFinally}
     of opcExcept:
-      # just skip it; it's followed by a jump;
-      # we'll execute in the 'raise' handler
-      let rbx = instr.regBx - wordExcess - 1 # -1 for the following 'inc pc'
-      inc pc, rbx
-      while c.code[pc+1].opcode == opcExcept:
-        let rbx = c.code[pc+1].regBx - wordExcess - 1
-        inc pc, rbx
-      #assert c.code[pc+1].opcode in {opcExcept, opcFinally}
-      if c.code[pc+1].opcode != opcFinally:
-        # in an except handler there is no active safe point for the 'try':
-        tos.popSafePoint()
+      # This opcode is never executed, it only holds informations for the
+      # exception handling routines.
+      doAssert(false)
     of opcFinally:
-      # just skip it; it's followed by the code we need to execute anyway
+      # Pop the last safepoint introduced by a opcTry. This opcode is only
+      # executed _iff_ no exception was raised in the body of the `try`
+      # statement hence the need to pop the safepoint here.
+      doAssert(savedPC < 0)
       tos.popSafePoint()
     of opcFinallyEnd:
-      if c.currentExceptionA != nil:
-        # we are in a cleanup run:
-        let (newPc, newTos) = cleanUpOnException(c, tos)
-        if newPc-1 < 0:
-          bailOut(c, tos)
-          return
-        pc = newPc-1
-        if tos != newTos:
-          tos = newTos
+      # The control flow may not resume at the next instruction since we may be
+      # raising an exception or performing a cleanup.
+      if not savedPC < 0:
+        pc = savedPC - 1
+        savedPC = -1
+        if tos != savedFrame:
+          tos = savedFrame
           move(regs, tos.slots)
     of opcRaise:
       let raised = regs[ra].node
       c.currentExceptionA = raised
       c.exceptionInstr = pc
-      let (newPc, newTos) = cleanUpOnException(c, tos)
-      # -1 because of the following 'inc'
-      if newPc-1 < 0:
+
+      var frame = tos
+      var jumpTo = findExceptionHandler(c, frame, raised)
+      while jumpTo.why == ExceptionGotoUnhandled and not frame.next.isNil:
+        frame = frame.next
+        jumpTo = findExceptionHandler(c, frame, raised)
+
+      case jumpTo.why:
+      of ExceptionGotoHandler:
+        # Jump to the handler, do nothing when the `finally` block ends.
+        savedPC = -1
+        pc = jumpTo.where - 1
+        if tos != frame:
+          tos = frame
+          move(regs, tos.slots)
+      of ExceptionGotoFinally:
+        # Jump to the `finally` block first then re-jump here to continue the
+        # traversal of the exception chain
+        savedPC = pc
+        savedFrame = tos
+        pc = jumpTo.where - 1
+        if tos != frame:
+          tos = frame
+          move(regs, tos.slots)
+      of ExceptionGotoUnhandled:
+        # Nobody handled this exception, error out.
         bailOut(c, tos)
-        return
-      pc = newPc-1
-      if tos != newTos:
-        tos = newTos
-        move(regs, tos.slots)
     of opcNew:
       ensureKind(rkNode)
       let typ = c.types[instr.regBx - wordExcess]
@@ -1295,7 +1350,7 @@ proc rawExecute(c: PCtx, start: int, tos: PStackFrame): TFullReg =
         idx = int(regs[rb+rc-1].intVal)
         callback = c.callbacks[idx].value
         args = VmArgs(ra: ra, rb: rb, rc: rc, slots: cast[pointer](regs),
-                currentException: c.currentExceptionB,
+                currentException: c.currentExceptionA,
                 currentLineInfo: c.debug[pc])
       callback(args)
       regs[ra].node.flags.incl nfIsRef