modelverse/kernel/modelverse_kernel/main.py

import modelverse_kernel.primitives as primitive_functions
import modelverse_kernel.compiled as compiled_functions
import modelverse_jit.jit as jit
import modelverse_jit.intrinsics as jit_intrinsics
import sys
import time

if sys.version > '3': # pragma: no cover
    string_types = (str,)
else:
    string_types = (str, unicode)

class ModelverseKernel(object):
    def __init__(self, root):
        self.root = root
        self.returnvalue = None
        self.success = True
        self.generators = {}
        self.allow_compiled = True
        #self.allow_compiled = False

        # suggested_function_names maps body ids to suggested function names.
        # You tell the kernel to stop caring about getting the function names
        # right by setting this to `None`.
        self.suggested_function_names = {}

        # `self.jit` handles most JIT-related functionality.
        self.jit = jit.ModelverseJit()
        if self.allow_compiled:
            self.jit.compiled_function_lookup = lambda func_name: \
                getattr(compiled_functions, func_name, None)

        jit_intrinsics.register_intrinsics(self.jit)

        # To disable the JIT, uncomment the line below:
        #     self.jit.set_jit_enabled(False)
        self.debug_info = "(no debug information found)"

    def execute_yields(self, username, operation, params, reply):
        try:
            self.success = True
            if username not in self.generators:
                self.generators[username] = {}
            if operation not in self.generators[username]:
                # Create the generator for the function to execute
                self.generators[username][operation] = getattr(self, operation)(username, *params)

            if reply is not None:
                return self.generators[username][operation].send(reply)
            else:
                return self.generators[username][operation].next()
        except StopIteration:
            # Done, so remove the generator
            del self.generators[username][operation]
            return None
        except:
            print("Unknown error @ %s" % self.debug_info)
            raise

    def execute_rule(self, username):
        user_root, =    yield [("RD", [self.root, username])]
        user_frame, =   yield [("RD", [user_root, "frame"])]
        inst, phase =   yield [("RD", [user_frame, "IP"]),
                               ("RD", [user_frame, "phase"]),
                              ]
        self.new_debug, phase_v, inst_v = \
                        yield [("RD", [inst, "__debug"]),
                               ("RV", [phase]),
                               ("RV", [inst]),
                              ]
        if self.new_debug is not None:
            self.debug_info, = yield [("RV", [self.new_debug])]

        if phase_v == "finish":
            gen = self.helper_init(user_root)
        elif inst is None:
            raise Exception("Instruction pointer could not be found!")
        elif isinstance(phase_v, string_types):
            if phase_v == "init" and self.jit.is_jittable_entry_point(inst):
                #print("%-30s(%s)" % ("COMPILED " + str(self.jit.jitted_entry_points[inst]), phase_v))
                gen = self.execute_jit(user_root, inst, username)
            elif inst_v is None:
                raise Exception("%s: error understanding command (%s, %s)" % (self.debug_info, inst_v, phase_v))
            else:
                gen = self.get_inst_phase_generator(inst_v, phase_v, user_root)
        elif inst_v is None:
            raise Exception("%s: error understanding command (%s, %s)" % (self.debug_info, inst_v, phase_v))
        elif inst_v["value"] == "call":
            #print("%-30s(%s)" % ("call", "param"))
            gen = self.call_param(user_root)
        else:
            raise Exception("%s: error understanding command (%s, %s)" % (self.debug_info, inst_v, phase_v))

        try:
            inp = None
            while 1:
                inp = yield gen.send(inp)
        except StopIteration:
            pass
        except jit.JitCompilationFailedException as e:
            # Try again, but this time without the JIT.
            # print(e.message)
            gen = self.get_inst_phase_generator(inst_v, phase_v, user_root)
            try:
                inp = None
                while 1:
                    inp = yield gen.send(inp)
            except StopIteration:
                pass

    def get_inst_phase_generator(self, inst_v, phase_v, user_root):
        """Gets a generator for the given instruction in the given phase,
           for the specified user root."""
        #print("%-30s(%s) -- %s" % (inst_v["value"], phase_v, username))
        return getattr(self, "%s_%s" % (inst_v["value"], phase_v))(user_root)

    ##########################
    ### Process primitives ###
    ##########################
    def load_primitives(self, username):
        hierarchy, =     yield [("RD", [self.root, "__hierarchy"])]
        primitives, =    yield [("RD", [hierarchy, "primitives"])]
        keys, =          yield [("RDK", [primitives])]
        function_names = yield [("RV", [f]) for f in keys]
        signatures  =    yield [("RDN", [primitives, f]) for f in keys]
        bodies =         yield [("RD", [f, "body"]) for f in signatures]
        for i in range(len(keys)):
            self.jit.register_compiled(
                bodies[i], 
                getattr(primitive_functions, function_names[i]), 
                function_names[i])

    def execute_jit(self, user_root, inst, username):
        # execute_jit
        user_frame, =    yield [("RD", [user_root, "frame"])]
        symbols, =       yield [("RD", [user_frame, "symbols"])]
        all_links, =     yield [("RO", [symbols])]
        containers =    yield [("RE", [v]) for v in all_links]
        outgoings =     yield [("RO", [v]) for v in all_links]
        dict_values =   yield [("RD", [v[1], "value"]) for v in containers]
        formals_1 =     yield [("RE", [v[0]]) for v in outgoings]
        dict_keys_ref = yield [("RD", [v[1], "name"]) for v in formals_1]
        dict_keys =     yield [("RV", [v]) for v in dict_keys_ref]
        parameters = dict(zip(dict_keys, dict_values))

        parameters["root"] = self.root
        parameters["user_root"] = user_root
        parameters["username"] = username
        parameters["mvk"] = self

        # Try to retrieve the suggested name.
        if self.suggested_function_names is not None and inst in self.suggested_function_names:
            suggested_name = self.suggested_function_names[inst]
        else:
            suggested_name = None

        # Have the JIT compile the function.
        try:
            jit_gen = self.jit.jit_compile(user_root, inst, suggested_name)
            inp = None
            while 1:
                inp = yield jit_gen.send(inp)
        except primitive_functions.PrimitiveFinished as e:
            compiled_func = e.result

        # Run the compiled function.
        try:
            prim = compiled_func(**parameters)
            inp = None
            while 1:
                inp = yield prim.send(inp)
        except StopIteration:
            # Execution has ended without return value, so we have no idea what to do
            raise Exception("%s: primitive finished without returning a value!" % (self.debug_info))
        except primitive_functions.PrimitiveFinished as e:
            # Execution has ended with a returnvalue, so read it out from the exception being thrown
            result = e.result

            #if result is None:
            #    raise Exception("Primitive raised exception: value of None for operation %s with parameters %s" % (compiled_func, str(parameters)))

        # Clean up the current stack, as if a return happened
        old_frame, =    yield [("RD", [user_frame, "prev"])]
        lnk, =          yield [("RDE", [old_frame, "returnvalue"])]
        _, _, _, _ =    yield [("CD", [old_frame, "returnvalue", result]),
                               ("CD", [user_root, "frame", old_frame]),
                               ("DE", [lnk]),
                               ("DN", [user_frame]),
                              ]

    ########################################
    ### Execute input and output methods ###
    ########################################
    def get_output(self, username):
        user_root, =        yield [("RD", [self.root, username])]
        first_output, =     yield [("RD", [user_root, "output"])]
        next_output, rv =   yield [("RD", [first_output, "next"]),
                                   ("RD", [first_output, "value"]),
                                  ]
        if next_output is None:
            self.success = False
            self.returnvalue = None
        else:
            rv_value, =     yield [("RV", [rv])]
            _, _ =          yield [("CD", [user_root, "output", next_output]),
                                   ("DN", [first_output]),
                                  ]
            self.returnvalue = rv_value

    def set_input(self, username, value):
        user_root, =        yield [("RD", [self.root, username])]
        old_input, link =   yield [("RD", [user_root, "last_input"]),
                                   ("RDE", [user_root, "last_input"]),
                                  ]
        new_input, =        yield [("CN", [])]
        _, _ =              yield [("CD", [user_root, "last_input", new_input]),
                                   ("CD", [old_input, "next", new_input]),
                                  ]

        new_value, =        yield [("CNV", [value])]
        _, _ =              yield [("CD", [old_input, "value", new_value]),
                                   ("DE", [link])
                                  ]
        self.returnvalue = {"id": 100, "value": "success"}

    #############################################
    ### Transformation rules for instructions ###
    #############################################
    def break_init(self, user_root):
        user_frame, =       yield [("RD", [user_root, "frame"])]
        phase_link, ip_link = \
                            yield [("RDE", [user_frame, "phase"]),
                                   ("RDE", [user_frame, "IP"])
                                  ]
        inst, =             yield [("RD", [user_frame, "IP"])]
        while_inst, new_phase = \
                            yield [("RD", [inst, "while"]),
                                   ("CNV", ["finish"]),
                                  ]
        _, _, _, _ =        yield [("CD", [user_frame, "phase", new_phase]),
                                   ("CD", [user_frame, "IP", while_inst]),
                                   ("DE", [phase_link]),
                                   ("DE", [ip_link]),
                                  ]

    def continue_init(self, user_root):
        user_frame, =       yield [("RD", [user_root, "frame"])]
        ip_link, inst =     yield [("RDE", [user_frame, "IP"]),
                                   ("RD", [user_frame, "IP"]),
                                  ]
        while_inst, =       yield [("RD", [inst, "while"])]
        _, _ =              yield [("CD", [user_frame, "IP", while_inst]),
                                   ("DE", [ip_link]),
                                  ]

    def if_init(self, user_root):
        user_frame, =       yield [("RD", [user_root, "frame"])]
        evalstack, evalstack_link = \
                            yield [("RD", [user_frame, "evalstack"]),
                                   ("RDE", [user_frame, "evalstack"]),
                                  ]
        inst, ip_link =     yield [("RD", [user_frame, "IP"]),
                                   ("RDE", [user_frame, "IP"]),
                                  ]
        cond, =             yield [("RD", [inst, "cond"])]
        new_evalstack, new_phase = \
                            yield [("CN", []),
                                   ("CNV", ["cond"]),
                                  ]
        _, _, _, _, _, _, _ = \
                            yield [("CD", [user_frame, "evalstack", new_evalstack]),
                                   ("CD", [new_evalstack, "prev", evalstack]),
                                   ("CD", [user_frame, "IP", cond]),
                                   ("CD", [evalstack, "inst", inst]),
                                   ("CD", [evalstack, "phase", new_phase]),
                                   ("DE", [evalstack_link]),
                                   ("DE", [ip_link]),
                                  ]

    def if_cond(self, user_root):
        user_frame, =       yield [("RD", [user_root, "frame"])]
        returnvalue, inst = yield [("RD", [user_frame, "returnvalue"]),
                                   ("RD", [user_frame, "IP"]),
                                  ]
        returnvalue_v, =    yield [("RV", [returnvalue])]
        _else, =            yield [("RD", [inst, "else"])]

        if returnvalue_v:
            phase_link, evalstack, evalstack_link, ip_link, _then, new_evalstack, evalstack_phase, new_phase = \
                            yield [("RDE", [user_frame, "phase"]),
                                   ("RD", [user_frame, "evalstack"]),
                                   ("RDE", [user_frame, "evalstack"]),
                                   ("RDE", [user_frame, "IP"]),
                                   ("RD", [inst, "then"]),
                                   ("CN", []),
                                   ("CNV", ["finish"]),
                                   ("CNV", ["init"]),
                                  ]
            _, _, _, _, _, _, _, _, _ = \
                            yield [("CD", [user_frame, "evalstack", new_evalstack]),
                                   ("CD", [user_frame, "IP", _then]),
                                   ("CD", [new_evalstack, "prev", evalstack]),
                                   ("CD", [evalstack, "inst", inst]),
                                   ("CD", [evalstack, "phase", evalstack_phase]),
                                   ("CD", [user_frame, "phase", new_phase]),
                                   ("DE", [evalstack_link]),
                                   ("DE", [ip_link]),
                                   ("DE", [phase_link]),
                                  ]
        elif _else is None:
            phase_link, new_phase = \
                            yield [("RDE", [user_frame, "phase"]),
                                   ("CNV", ["finish"]),
                                  ]
            _, _ =          yield [("CD", [user_frame, "phase", new_phase]),
                                   ("DE", [phase_link]),
                                  ]
        else:
            phase_link, evalstack, evalstack_link, ip_link = \
                            yield [("RDE", [user_frame, "phase"]),
                                   ("RD", [user_frame, "evalstack"]),
                                   ("RDE", [user_frame, "evalstack"]),
                                   ("RDE", [user_frame, "IP"]),
                                  ]
            new_evalstack, new_phase, evalstack_phase = \
                            yield [("CN", []),
                                   ("CNV", ["init"]),
                                   ("CNV", ["finish"]),
                                  ]
            _, _, _, _, _, _, _, _, _ = \
                            yield [("CD", [user_frame, "evalstack", new_evalstack]),
                                   ("CD", [user_frame, "IP", _else]),
                                   ("CD", [new_evalstack, "prev", evalstack]),
                                   ("CD", [evalstack, "inst", inst]),
                                   ("CD", [evalstack, "phase", evalstack_phase]),
                                   ("CD", [user_frame, "phase", new_phase]),
                                   ("DE", [evalstack_link]),
                                   ("DE", [ip_link]),
                                   ("DE", [phase_link]),
                                  ]

    def while_init(self, user_root):
        user_frame, =       yield [("RD", [user_root, "frame"])]
        evalstack, evalstack_link, ip_link, inst = \
                            yield [("RD", [user_frame, "evalstack"]),
                                   ("RDE", [user_frame, "evalstack"]),
                                   ("RDE", [user_frame, "IP"]),
                                   ("RD", [user_frame, "IP"]),
                                  ]
        cond, new_evalstack, new_phase = \
                            yield [("RD", [inst, "cond"]),
                                   ("CN", []),
                                   ("CNV", ["cond"]),
                                  ]
        _, _, _, _, _, _, _ = \
                            yield [("CD", [user_frame, "evalstack", new_evalstack]),
                                   ("CD", [new_evalstack, "prev", evalstack]),
                                   ("CD", [user_frame, "IP", cond]),
                                   ("CD", [evalstack, "phase", new_phase]),
                                   ("CD", [evalstack, "inst", inst]),
                                   ("DE", [evalstack_link]),
                                   ("DE", [ip_link]),
                                  ]

    def while_cond(self, user_root):
        user_frame, =       yield [("RD", [user_root, "frame"])]
        returnvalue, =      yield [("RD", [user_frame, "returnvalue"])]
        returnvalue_v, =    yield [("RV", [returnvalue])]

        if returnvalue_v:
            phase_link, evalstack, evalstack_link, ip_link, inst = \
                            yield [("RDE", [user_frame, "phase"]),
                                   ("RD", [user_frame, "evalstack"]),
                                   ("RDE", [user_frame, "evalstack"]),
                                   ("RDE", [user_frame, "IP"]),
                                   ("RD", [user_frame, "IP"]),
                                  ]
            body, =         yield [("RD", [inst, "body"])]
            new_evalstack, new_phase, evalstack_phase = \
                            yield [("CN", []),
                                   ("CNV", ["init"]),
                                   ("CNV", ["init"]),
                                  ]
            _, _, _, _, _, _, _, _, _ = \
                            yield [("CD", [user_frame, "IP", body]),
                                   ("CD", [user_frame, "phase", new_phase]),
                                   ("CD", [user_frame, "evalstack", new_evalstack]),
                                   ("CD", [new_evalstack, "prev", evalstack]),
                                   ("CD", [evalstack, "inst", inst]),
                                   ("CD", [evalstack, "phase", evalstack_phase]),
                                   ("DE", [evalstack_link]),
                                   ("DE", [ip_link]),
                                   ("DE", [phase_link]),
                                  ]
        else:
            phase_link, new_phase = \
                            yield [("RDE", [user_frame, "phase"]),
                                   ("CNV", ["finish"]),
                                  ]
            _, _ =          yield [("CD", [user_frame, "phase", new_phase]),
                                   ("DE", [phase_link])
                                  ]

    def access_init(self, user_root):
        user_frame, =       yield [("RD", [user_root, "frame"])]
        evalstack, evalstack_link, inst, ip_link = \
                            yield [("RD", [user_frame, "evalstack"]),
                                   ("RDE", [user_frame, "evalstack"]),
                                   ("RD", [user_frame, "IP"]),
                                   ("RDE", [user_frame, "IP"]),
                                  ]
        var, new_evalstack, new_phase = \
                            yield [("RD", [inst, "var"]),
                                   ("CN", []),
                                   ("CNV", ["eval"]),
                                  ]
        _, _, _, _, _, _, _ = \
                            yield [("CD", [user_frame, "IP", var]),
                                   ("CD", [user_frame, "evalstack", new_evalstack]),
                                   ("CD", [new_evalstack, "prev", evalstack]),
                                   ("CD", [evalstack, "inst", inst]),
                                   ("CD", [evalstack, "phase", new_phase]),
                                   ("DE", [evalstack_link]),
                                   ("DE", [ip_link]),
                                  ]

    def access_eval(self, user_root):
        user_frame, =       yield [("RD", [user_root, "frame"])]
        phase_link, returnvalue_link, returnvalue = \
                            yield [("RDE", [user_frame, "phase"]),
                                   ("RDE", [user_frame, "returnvalue"]),
                                   ("RD", [user_frame, "returnvalue"]),
                                  ]
        value, new_phase =  yield [("RD", [returnvalue, "value"]),
                                   ("CNV", ["finish"]),
                                  ]
        _, _, _, _ =        yield [("CD", [user_frame, "phase", new_phase]),
                                   ("CD", [user_frame, "returnvalue", value]),
                                   ("DE", [phase_link]),
                                   ("DE", [returnvalue_link]),
                                  ]

    def resolve_init(self, user_root):
        user_frame, =       yield [("RD", [user_root, "frame"])]
        symbols, evalstack, evalstack_link, ip_link, inst = \
                            yield [("RD", [user_frame, "symbols"]),
                                   ("RD", [user_frame, "evalstack"]),
                                   ("RDE", [user_frame, "evalstack"]),
                                   ("RDE", [user_frame, "IP"]),
                                   ("RD", [user_frame, "IP"]),
                                  ]
        var, =              yield [("RD", [inst, "var"])]
        variable, =         yield [("RDN", [symbols, var])]

        if variable is None:
            phase_link, returnvalue_link, _globals, var_name = \
                            yield [("RDE", [user_frame, "phase"]),
                                   ("RDE", [user_frame, "returnvalue"]),
                                   ("RD", [user_root, "globals"]),
                                   ("RV", [var]),
                                  ]
            variable, new_phase = \
                            yield [("RD", [_globals, var_name]),
                                   ("CNV", ["finish"]),
                                  ]
            if variable is None:
                raise Exception("%s: not found as global: %s" % (self.debug_info, var_name))

            # Resolved a global, so this is a string
            # Potentially, this might even be a function that we have precompiled already!
            # So check whether this is the case or not
            if self.allow_compiled:
                compiled_function = getattr(compiled_functions, var_name, None)
                if compiled_function is not None:
                    # We have a compiled function ready!
                    # Now we have to bind the ID to the compiled functions
                    # For this, we read out the body of the resolved data
                    compiler_val, =  yield [("RD", [variable, "value"])]
                    compiler_body, = yield [("RD", [compiler_val, "body"])]
                    self.jit.register_compiled(compiler_body, compiled_function, var_name)

            # If we're dealing with a function, then we might want to figure out what its body id
            # is now so we can suggest a name to the JIT later.
            if self.suggested_function_names is not None:
                compiler_val, =  yield [("RD", [variable, "value"])]
                if compiler_val is not None:
                    compiler_body, = yield [("RD", [compiler_val, "body"])]
                    if compiler_body is not None:
                        self.suggested_function_names[compiler_body] = var_name

        else:
            phase_link, returnvalue_link, new_phase = \
                            yield [("RDE", [user_frame, "phase"]),
                                   ("RDE", [user_frame, "returnvalue"]),
                                   ("CNV", ["finish"]),
                                  ]
        _, _, _, _ =        yield [("CD", [user_frame, "phase", new_phase]),
                                   ("CD", [user_frame, "returnvalue", variable]),
                                   ("DE", [phase_link]),
                                   ("DE", [returnvalue_link]),
                                  ]

    def assign_init(self, user_root):
        user_frame, =       yield [("RD", [user_root, "frame"])]
        evalstack, evalstack_link, ip_link, inst = \
                            yield [("RD", [user_frame, "evalstack"]),
                                   ("RDE", [user_frame, "evalstack"]),
                                   ("RDE", [user_frame, "IP"]),
                                   ("RD", [user_frame, "IP"]),
                                  ]
        var, new_evalstack, new_phase = \
                            yield [("RD", [inst, "var"]),
                                   ("CN", []),
                                   ("CNV", ["value"]),
                                  ]
        _, _, _, _, _, _, _ = \
                            yield [("CD", [user_frame, "IP", var]),
                                   ("CD", [user_frame, "evalstack", new_evalstack]),
                                   ("CD", [new_evalstack, "prev", evalstack]),
                                   ("CD", [evalstack, "inst", inst]),
                                   ("CD", [evalstack, "phase", new_phase]),
                                   ("DE", [evalstack_link]),
                                   ("DE", [ip_link]),
                                  ]

    def assign_value(self, user_root):
        user_frame, =       yield [("RD", [user_root, "frame"])]
        phase_link, evalstack, returnvalue, evalstack_link, ip_link, inst = \
                            yield [("RDE", [user_frame, "phase"]),
                                   ("RD", [user_frame, "evalstack"]),
                                   ("RD", [user_frame, "returnvalue"]),
                                   ("RDE", [user_frame, "evalstack"]),
                                   ("RDE", [user_frame, "IP"]),
                                   ("RD", [user_frame, "IP"]),
                                  ]
        value, new_evalstack, new_phase, evalstack_phase = \
                            yield [("RD", [inst, "value"]),
                                   ("CN", []),
                                   ("CNV", ["init"]),
                                   ("CNV", ["assign"]),
                                  ]

        _, _, _, _, _, _, _, _, _, _ = \
                            yield [("CD", [user_frame, "variable", returnvalue]),
                                   ("CD", [user_frame, "phase", new_phase]),
                                   ("CD", [user_frame, "evalstack", new_evalstack]),
                                   ("CD", [new_evalstack, "prev", evalstack]),
                                   ("CD", [evalstack, "inst", inst]),
                                   ("CD", [evalstack, "phase", evalstack_phase]),
                                   ("CD", [user_frame, "IP", value]),
                                   ("DE", [evalstack_link]),
                                   ("DE", [phase_link]),
                                   ("DE", [ip_link]),
                                  ]

    def assign_assign(self, user_root):
        user_frame, =       yield [("RD", [user_root, "frame"])]
        phase_link, returnvalue, variable_link, variable = \
                            yield [("RDE", [user_frame, "phase"]),
                                   ("RD", [user_frame, "returnvalue"]),
                                   ("RDE", [user_frame, "variable"]),
                                   ("RD", [user_frame, "variable"]),
                                  ]
        value_link, new_phase = \
                            yield [("RDE", [variable, "value"]),
                                   ("CNV", ["finish"]),
                                  ]
        _, _, _, _, _ =     yield [("CD", [user_frame, "phase", new_phase]),
                                   ("CD", [variable, "value", returnvalue]),
                                   ("DE", [variable_link]),
                                   ("DE", [value_link]),
                                   ("DE", [phase_link]),
                                  ]
                    
    def return_init(self, user_root):
        user_frame, =       yield [("RD", [user_root, "frame"])]
        inst, =             yield [("RD", [user_frame, "IP"])]
        value, =            yield [("RD", [inst, "value"])]

        if value is None:
            prev_frame, =   yield [("RD", [user_frame, "prev"])]
            _, _ =          yield [("CD", [user_root, "frame", prev_frame]),
                                   ("DN", [user_frame]),
                                  ]

            # If the callee's frame is marked with the '__primitive_return' key, then
            # we need to throw an exception instead of just finishing here. This design
            # gives us O(1) state reads per jit-interpreter transition.
            exception_return, = yield [("RD", [user_frame, primitive_functions.PRIMITIVE_RETURN_KEY])]
            if exception_return is not None:
                raise primitive_functions.PrimitiveFinished(None)
        else:
            evalstack, evalstack_link, ip_link, new_evalstack, evalstack_phase = \
                            yield [("RD", [user_frame, "evalstack"]),
                                   ("RDE", [user_frame, "evalstack"]),
                                   ("RDE", [user_frame, "IP"]),
                                   ("CN", []),
                                   ("CNV", ["eval"]),
                                  ]
            _, _, _, _, _, _, _ = \
                            yield [("CD", [user_frame, "evalstack", new_evalstack]),
                                   ("CD", [new_evalstack, "prev", evalstack]),
                                   ("CD", [evalstack, "inst", inst]),
                                   ("CD", [evalstack, "phase", evalstack_phase]),
                                   ("CD", [user_frame, "IP", value]),
                                   ("DE", [evalstack_link]),
                                   ("DE", [ip_link]),
                                  ]

    def return_eval(self, user_root):
        user_frame, = yield [("RD", [user_root, "frame"])]
        prev_frame, exception_return, returnvalue = yield [
            ("RD", [user_frame, "prev"]),
            ("RD", [user_frame, primitive_functions.PRIMITIVE_RETURN_KEY]),
            ("RD", [user_frame, "returnvalue"])]

        # If the callee's frame is marked with the '__primitive_return' key, then
        # we need to throw an exception instead of just finishing here. This design
        # gives us O(1) state reads per jit-interpreter transition.
        if exception_return is not None:
            yield [
                ("CD", [user_root, "frame", prev_frame]),
                ("DN", [user_frame])]
            raise primitive_functions.PrimitiveFinished(returnvalue)
        else:
            old_returnvalue_link, = yield [("RDE", [prev_frame, "returnvalue"])]
            yield [
                ("CD", [user_root, "frame", prev_frame]),
                ("CD", [prev_frame, "returnvalue", returnvalue]),
                ("DE", [old_returnvalue_link]),
                ("DN", [user_frame])]

    def constant_init(self, user_root):
        user_frame, =       yield [("RD", [user_root, "frame"])]
        phase_link, returnvalue_link, inst = \
                            yield [("RDE", [user_frame, "phase"]),
                                   ("RDE", [user_frame, "returnvalue"]),
                                   ("RD", [user_frame, "IP"]),
                                  ]
        node, new_phase =   yield [("RD", [inst, "node"]),
                                   ("CNV", ["finish"]),
                                  ]
        _, _, _, _ =        yield [("CD", [user_frame, "phase", new_phase]),
                                   ("CD", [user_frame, "returnvalue", node]),
                                   ("DE", [returnvalue_link]),
                                   ("DE", [phase_link]),
                                  ]

    def helper_init(self, user_root):
        user_frame, =       yield [("RD", [user_root, "frame"])]
        inst, =             yield [("RD", [user_frame, "IP"])]
        next, =             yield [("RD", [inst, "next"])]

        if next is None:
            ip_link, phase_link, evalstack_top = \
                            yield [("RDE", [user_frame, "IP"]),
                                   ("RDE", [user_frame, "phase"]),
                                   ("RD", [user_frame, "evalstack"]),
                                  ]
            evalstack, =    yield [("RD", [evalstack_top, "prev"])]
            evalstack_inst, evalstack_phase, evalstack_inst_link, evalstack_phase_link = \
                            yield [("RD", [evalstack, "inst"]),
                                   ("RD", [evalstack, "phase"]),
                                   ("RDE", [evalstack, "inst"]),
                                   ("RDE", [evalstack, "phase"]),
                                  ]
            _, _, _, _, _, _, _, _ = \
                            yield [("CD", [user_frame, "evalstack", evalstack]),
                                   ("CD", [user_frame, "IP", evalstack_inst]),
                                   ("CD", [user_frame, "phase", evalstack_phase]),
                                   ("DE", [ip_link]),
                                   ("DE", [phase_link]),
                                   ("DE", [evalstack_inst_link]),
                                   ("DE", [evalstack_phase_link]),
                                   ("DN", [evalstack_top]),
                                  ]
        else:
            ip_link, phase_link, new_phase = \
                            yield [("RDE", [user_frame, "IP"]),
                                   ("RDE", [user_frame, "phase"]),
                                   ("CNV", ["init"]),
                                  ]
            _, _, _, _ =    yield [("CD", [user_frame, "IP", next]),
                                   ("CD", [user_frame, "phase", new_phase]),
                                   ("DE", [ip_link]),
                                   ("DE", [phase_link]),
                                  ]

    def call_init(self, user_root):
        user_frame, =       yield [("RD", [user_root, "frame"])]
        symbols, evalstack, evalstack_link, ip_link, inst = \
                            yield [("RD", [user_frame, "symbols"]),
                                   ("RD", [user_frame, "evalstack"]),
                                   ("RDE", [user_frame, "evalstack"]),
                                   ("RDE", [user_frame, "IP"]),
                                   ("RD", [user_frame, "IP"]),
                                  ]
        func, params =      yield [("RD", [inst, "func"]),
                                   ("RD", [inst, "params"]),
                                  ]
        
        if params is None:
            new_evalstack, evalstack_phase = \
                            yield [("CN", []),
                                   ("CNV", ["call"]),
                                  ]
            _, _, _, _, _, _, _ = \
                            yield [("CD", [user_frame, "evalstack", new_evalstack]),
                                   ("CD", [new_evalstack, "prev", evalstack]),
                                   ("CD", [evalstack, "inst", inst]),
                                   ("CD", [evalstack, "phase", evalstack_phase]),
                                   ("CD", [user_frame, "IP", func]),
                                   ("DE", [evalstack_link]),
                                   ("DE", [ip_link]),
                                  ]
        else:
            new_evalstack,= yield [("CN", [])]
            _, _, _, _, _, _, _ = \
                            yield [("CD", [user_frame, "evalstack", new_evalstack]),
                                   ("CD", [new_evalstack, "prev", evalstack]),
                                   ("CD", [evalstack, "inst", inst]),
                                   ("CD", [evalstack, "phase", params]),
                                   ("CD", [user_frame, "IP", func]),
                                   ("DE", [evalstack_link]),
                                   ("DE", [ip_link]),
                                  ]

    def call_call(self, user_root):
        user_frame, =       yield [("RD", [user_root, "frame"])]
        inst, =             yield [("RD", [user_frame, "IP"])]
        param, =            yield [("RD", [inst, "last_param"])]

        if param is None:
            returnvalue, =  yield [("RD", [user_frame, "returnvalue"])]
            body, =         yield [("RD", [returnvalue, "body"])]
            self.jit.mark_entry_point(body)

            phase_link, frame_link, prev_phase, new_phase, new_frame, new_evalstack, new_symbols, new_returnvalue = \
                            yield [("RDE", [user_frame, "phase"]),
                                   ("RDE", [user_root, "frame"]),
                                   ("CNV", ["finish"]),
                                   ("CNV", ["init"]),
                                   ("CN", []),
                                   ("CN", []),
                                   ("CN", []),
                                   ("CN", []),
                                  ]
            _, _, _, _, _, _, _, _, _, _, _ = \
                            yield [("CD", [user_root, "frame", new_frame]),
                                   ("CD", [new_frame, "evalstack", new_evalstack]),
                                   ("CD", [new_frame, "symbols", new_symbols]),
                                   ("CD", [new_frame, "returnvalue", new_returnvalue]),
                                   ("CD", [new_frame, "caller", inst]),
                                   ("CD", [new_frame, "phase", new_phase]),
                                   ("CD", [new_frame, "IP", body]),
                                   ("CD", [new_frame, "prev", user_frame]),
                                   ("CD", [user_frame, "phase", prev_phase]),
                                   ("DE", [phase_link]),
                                   ("DE", [frame_link]),
                                  ]
        else:
            newer_frames, invoking_frames = \
                            yield [("RRD", [user_frame, "prev"]),
                                   ("RRD", [inst, "caller"]),
                                  ]
            new_frame = self.find_overlapping(newer_frames, invoking_frames)
            phase_link, frame_link, new_symbols, new_IP = \
                            yield [("RDE", [user_frame, "phase"]),
                                   ("RDE", [user_root, "frame"]),
                                   ("RD", [new_frame, "symbols"]),
                                   ("RD", [new_frame, "IP"]),
                                  ]
            signature, =    yield [("RRD", [new_IP, "body"])]
            signature = signature[0]
            sig_params, last_param = \
                            yield [("RD", [signature, "params"]),
                                   ("RD", [inst, "last_param"]),
                                  ]

            body, =         yield [("RD", [new_IP, "body"])]
            self.jit.mark_entry_point(body)
            
            name, =         yield [("RD", [last_param, "name"])]
            name_value, =   yield [("RV", [name])]
            returnvalue, formal_parameter, new_phase, variable = \
                            yield [("RD", [user_frame, "returnvalue"]),
                                   ("RD", [sig_params, name_value]),
                                   ("CNV", ["finish"]),
                                   ("CN", []),
                                  ]
            _, _, _, t1 =   yield [("CD", [user_root, "frame", new_frame]),
                                   ("CD", [user_frame, "phase", new_phase]),
                                   ("CD", [variable, "value", returnvalue]),
                                   ("CE", [new_symbols, variable]),
                                  ]
            _, _, _ =       yield [("CE", [t1, formal_parameter]),
                                   ("DE", [frame_link]),
                                   ("DE", [phase_link]),
                                  ]

    def find_overlapping(self, a, b):
        newer_frames = set(a)
        invoking_frames = set(b)
        matches = list(newer_frames.intersection(invoking_frames))
        if len(matches) == 1:
            return matches[0]
        elif len(matches) > 1:
            raise Exception("%s: error: multiple overlapping elements" % self.debug_info)
        else:
            raise Exception("%s: error: could not find any overlap" % self.debug_info)

    def call_param(self, user_root):
        user_frame, =       yield [("RD", [user_root, "frame"])]
        inst, phase =       yield [("RD", [user_frame, "IP"]),
                                   ("RD", [user_frame, "phase"]),
                                  ]
        params, last_param = \
                            yield [("RD", [inst, "params"]),
                                   ("RD", [inst, "last_param"]),
                                  ]
        next_param, =       yield [("RD", [params, "next_param"])]

        if params == phase:
            phase_link, ip_link, returnvalue, param_value, evalstack, evalstack_link = \
                            yield [("RDE", [user_frame, "phase"]),
                                   ("RDE", [user_frame, "IP"]),
                                   ("RD", [user_frame, "returnvalue"]),
                                   ("RD", [params, "value"]),
                                   ("RD", [user_frame, "evalstack"]),
                                   ("RDE", [user_frame, "evalstack"]),
                                  ]
            body, =         yield [("RD", [returnvalue, "body"])]
            new_frame, prev_evalstack, new_phase, prev_phase, new_evalstack, new_symbols, new_returnvalue = \
                            yield [("CN", []),
                                   ("CN", []),
                                   ("CNV", ["init"]),
                                   ("CNV", ["init"]),
                                   ("CN", []),
                                   ("CN", []),
                                   ("CN", []),
                                  ]
            _, _, _, _, _, _, _, _, _, _, _, _, _, _, _ = \
                            yield [("CD", [new_frame, "evalstack", new_evalstack]),
                                   ("CD", [new_frame, "symbols", new_symbols]),
                                   ("CD", [new_frame, "returnvalue", new_returnvalue]),
                                   ("CD", [new_frame, "caller", inst]),
                                   ("CD", [new_frame, "phase", new_phase]),
                                   ("CD", [new_frame, "IP", body]),
                                   ("CD", [new_frame, "prev", user_frame]),
                                   ("CD", [user_frame, "phase", prev_phase]),
                                   ("CD", [user_frame, "IP", param_value]),
                                   ("CD", [prev_evalstack, "prev", evalstack]),
                                   ("CD", [evalstack, "inst", inst]),
                                   ("CD", [user_frame, "evalstack", prev_evalstack]),
                                   ("DE", [evalstack_link]),
                                   ("DE", [ip_link]),
                                   ("DE", [phase_link]),
                                  ]
            if next_param is not None:
                _ =         yield [("CD", [evalstack, "phase", next_param])]
            else:
                evalstack_phase, = \
                            yield [("CNV", ["call"])]
                _ =         yield [("CD", [evalstack, "phase", evalstack_phase])]
        else:
            frame_link, phase_link, newer_frames, invoking_frames = \
                            yield [("RDE", [user_root, "frame"]),
                                   ("RDE", [user_frame, "phase"]),
                                   ("RRD", [user_frame, "prev"]),
                                   ("RRD", [inst, "caller"]),
                                  ]
            new_frame = self.find_overlapping(newer_frames, invoking_frames)
            ip_link, evalstack, evalstack_link, new_symbols, new_IP = \
                            yield [("RDE", [user_frame, "IP"]),
                                   ("RD", [user_frame, "evalstack"]),
                                   ("RDE", [user_frame, "evalstack"]),
                                   ("RD", [new_frame, "symbols"]),
                                   ("RD", [new_frame, "IP"]),
                                  ]
            signature, =    yield [("RRD", [new_IP, "body"])]
            signature = signature[0]
            sig_params, =   yield [("RD", [signature, "params"])]

            if last_param == phase:
                prev_param, = \
                            yield [("RRD", [last_param, "next_param"])]
                prev_param = prev_param[0]
                name, =     yield [("RD", [prev_param, "name"])]
                name_value, = \
                            yield [("RV", [name])]
                evalstack_phase, = \
                            yield [("CNV", ["call"])]
                _ =         yield [("CD", [evalstack, "phase", evalstack_phase])]
                formal_parameter, param_value = \
                            yield [("RD", [sig_params, name_value]),
                                   ("RD", [last_param, "value"]),
                                  ]
            else:
                param_b, =  yield [("RD", [user_frame, "phase"])]
                param_c, param_a = \
                            yield [("RD", [param_b, "next_param"]),
                                   ("RRD", [param_b, "next_param"]),
                                  ]
                param_a = param_a[0]
                name, param_value = \
                            yield [("RD", [param_a, "name"]),
                                   ("RD", [param_b, "value"]),
                                  ]
                name_value, = \
                            yield [("RV", [name])]
                formal_parameter, _ = \
                            yield [("RD", [sig_params, name_value]),
                                   ("CD", [evalstack, "phase", param_c]),
                                  ]

            new_phase, new_evalstack, variable, returnvalue = \
                        yield [("CNV", ["init"]),
                               ("CN", []),
                               ("CN", []),
                               ("RD", [user_frame, "returnvalue"]),
                              ]
            _, _, _, _, _, _ = \
                        yield [("CD", [user_frame, "evalstack", new_evalstack]),
                               ("CD", [new_evalstack, "prev", evalstack]),
                               ("CD", [evalstack, "inst", inst]),
                               ("CD", [user_frame, "phase", new_phase]),
                               ("CD", [user_frame, "IP", param_value]),
                               ("CD", [variable, "value", returnvalue]),
                              ]

            t1, =       yield [("CE", [new_symbols, variable])]
            _, _, _, _ = \
                        yield [("CE", [t1, formal_parameter]),
                               ("DE", [phase_link]),
                               ("DE", [ip_link]),
                               ("DE", [evalstack_link]),
                              ]

    def input_init(self, user_root):
        user_frame, =   yield [("RD", [user_root, "frame"])]
        returnvalue_link, _input = \
                        yield [("RDE", [user_frame, "returnvalue"]),
                               ("RD", [user_root, "input"]),
                              ]
        value, next, phase_link = \
                        yield [("RD", [_input, "value"]),
                               ("RD", [_input, "next"]),
                               ("RDE", [user_frame, "phase"]),
                              ]

        if value is not None:
            v =         yield [("RV", [value])]
            _, _, finish = \
                        yield [("CD", [user_frame, "returnvalue", value]),
                               ("CD", [user_root, "input", next]),
                               ("CNV", ["finish"]),
                              ]
            _, _, _, _ = \
                        yield [("CD", [user_frame, "phase", finish]),
                               ("DN", [_input]),
                               ("DE", [returnvalue_link]),
                               ("DE", [phase_link]),
                              ]
            self.input_value = value
        else:
            # No input yet, so just wait and don't advance IP or phase
            self.input_value = None
            self.success = False

    def output_init(self, user_root):
        user_frame, =   yield [("RD", [user_root, "frame"])]
        evalstack, evalstack_link, ip_link, inst = \
                        yield [("RD", [user_frame, "evalstack"]),
                               ("RDE", [user_frame, "evalstack"]),
                               ("RDE", [user_frame, "IP"]),
                               ("RD", [user_frame, "IP"]),
                              ]
        value, new_evalstack, evalstack_phase = \
                        yield [("RD", [inst, "value"]),
                               ("CN", []),
                               ("CNV", ["output"]),
                              ]
        _, _, _, _, _, _, _ = \
                        yield [("CD", [user_frame, "evalstack", new_evalstack]),
                               ("CD", [new_evalstack, "prev", evalstack]),
                               ("CD", [evalstack, "inst", inst]),
                               ("CD", [evalstack, "phase", evalstack_phase]),
                               ("CD", [user_frame, "IP", value]),
                               ("DE", [evalstack_link]),
                               ("DE", [ip_link]),
                              ]

    def output_output(self, user_root):
        user_frame, =   yield [("RD", [user_root, "frame"])]
        returnvalue_link, returnvalue, last_output, phase_link, last_output_link, new_last_output, finish = \
                        yield [("RDE", [user_frame, "returnvalue"]),
                               ("RD", [user_frame, "returnvalue"]),
                               ("RD", [user_root, "last_output"]),
                               ("RDE", [user_frame, "phase"]),
                               ("RDE", [user_root, "last_output"]),
                               ("CN", []),
                               ("CNV", ["finish"]),
                              ]
        _, _, _, _, _, _ = \
                        yield [("CD", [last_output, "value", returnvalue]),
                               ("CD", [last_output, "next", new_last_output]),
                               ("CD", [user_root, "last_output", new_last_output]),
                               ("CD", [user_frame, "phase", finish]),
                               ("DE", [last_output_link]),
                               ("DE", [phase_link]),
                              ]

    def declare_init(self, user_root):
        user_frame, =   yield [("RD", [user_root, "frame"])]
        inst, =         yield [("RD", [user_frame, "IP"])]
        new_var, symbols, phase_link, empty_node, new_phase = \
                        yield [("RD", [inst, "var"]),
                               ("RD", [user_frame, "symbols"]),
                               ("RDE", [user_frame, "phase"]),
                               ("CN", []),
                               ("CNV", ["finish"]),
                              ]

        exists, =       yield [("RDN", [symbols, new_var])]
        if exists is None:
            new_edge, = yield [("CE", [symbols, empty_node])]
            _ =         yield [("CE", [new_edge, new_var])]

        _, _ =          yield [("CD", [user_frame, "phase", new_phase]),
                               ("DE", [phase_link]),
                              ]

    def global_init(self, user_root):
        user_frame, =   yield [("RD", [user_root, "frame"])]
        inst, =         yield [("RD", [user_frame, "IP"])]
        new_var, global_symbols, phase_link, empty_node, new_phase = \
                        yield [("RD", [inst, "var"]),
                               ("RD", [user_root, "globals"]),
                               ("RDE", [user_frame, "phase"]),
                               ("CN", []),
                               ("CNV", ["finish"]),
                              ]

        value, =        yield [("RV", [new_var])]
        exists, =       yield [("RD", [global_symbols, value])]

        if exists is None:
            yield [("CD", [global_symbols, value, empty_node])]

        _, _ =          yield [("CD", [user_frame, "phase", new_phase]),
                               ("DE", [phase_link])
                              ]