modelverse/kernel/modelverse_jit/tree_ir.py

# NOTE: NOP_LITERAL abuses a mechanic of the modelverse kernel. Specifically,
# whenever the `ModelverseKernel.execute_yields` method returns `None`, then
# the server built around it takes that as a hint that an instruction's phase
# has been completed. The server interrupts the kernel's thread of execution
# when it remarks that an instruction has completed a phase (i.e., when `None`
# is returned by `ModelverseKernel.execute_yields`) and proceeds to check for
# input and output.
#
# In assembly language, a nop is usually used as a point at which a thread of
# execution can be terminated. It follows from the paragraph above that what
# the interpreter does is more or less equivalent to placing nops after every
# instruction. It is worthwhile to remark that JIT-compiled code cannot rely
# on the kernel to interrupt the thread of execution automatically during a
# jitted function's execution -- jitted functions are considered equivalent
# to a single instruction as far as the kernel is concerned. A nop will be
# inserted _after_ the function call (if it is called from interpreted code)
# but that does not suffice for IO, which needs the input/output processing
# to be performed during function execution.
#
# For this reason, the JIT must strategically interrupt the execution of the
# functions it compiles. In other words, it must insert its own nops.
# Here comes the interesting part: a nop is equivalent to `yield None`,
# because that will persuade `ModelverseKernel.execute_yields` to relay the
# `None` marker value to the server, without terminating the current
# generator.

# Let's just agree to disagree on map vs list comprehensions, pylint.
# pylint: disable=I0011,W0141

NOP_LITERAL = None
"""A literal that results in a nop during which execution may be interrupted
   when yielded."""

UNKNOWN_RESULT_TYPE = 'unknown'
"""The result type for instructions that produce either primitive values or
   references to nodes."""

PRIMITIVE_RESULT_TYPE = 'primitive'
"""The result type for instructions that produce primitive values."""

NODE_RESULT_TYPE = 'node'
"""The result type for instructions that produce references to nodes."""

NO_RESULT_TYPE = 'nothing'
"""The result type for instructions that no result."""

def result_type_intersection(first_type, second_type):
    """Computes the intersection of the given result types."""
    if first_type == second_type:
        return first_type
    elif ((first_type == PRIMITIVE_RESULT_TYPE and second_type == UNKNOWN_RESULT_TYPE)
          or (first_type == UNKNOWN_RESULT_TYPE and second_type == PRIMITIVE_RESULT_TYPE)):
        return PRIMITIVE_RESULT_TYPE
    elif ((first_type == NODE_RESULT_TYPE and second_type == UNKNOWN_RESULT_TYPE)
          or (first_type == UNKNOWN_RESULT_TYPE and second_type == NODE_RESULT_TYPE)):
        return NODE_RESULT_TYPE
    else:
        return NO_RESULT_TYPE

def result_type_union(first_type, second_type):
    """Computes the union of the given result types."""
    if first_type == second_type:
        return first_type
    elif ((first_type == PRIMITIVE_RESULT_TYPE and second_type == NO_RESULT_TYPE)
          or (first_type == NO_RESULT_TYPE and second_type == PRIMITIVE_RESULT_TYPE)):
        return PRIMITIVE_RESULT_TYPE
    elif ((first_type == NODE_RESULT_TYPE and second_type == NO_RESULT_TYPE)
          or (first_type == NO_RESULT_TYPE and second_type == NODE_RESULT_TYPE)):
        return NODE_RESULT_TYPE
    else:
        return UNKNOWN_RESULT_TYPE

class Instruction(object):
    """A base class for instructions. An instruction is essentially a syntax
       node that must first be defined, and can only then be used."""

    def __init__(self):
        self.result_type_cache = None
        self.has_definition_cache = None

    def get_result_type(self):
        """Gets this instruction's result type."""
        if self.result_type_cache is None:
            self.result_type_cache = self.get_result_type_impl()
        return self.result_type_cache

    def has_result(self):
        """Tells if this instruction computes a result."""
        return self.get_result_type() != NO_RESULT_TYPE

    def has_definition(self):
        """Tells if this instruction requires a definition."""
        if self.has_definition_cache is None:
            self.has_definition_cache = self.has_definition_impl()
        return self.has_definition_cache

    def get_result_type_impl(self):
        """Gets this instruction's result type."""
        return PRIMITIVE_RESULT_TYPE

    def has_definition_impl(self):
        """Tells if this instruction requires a definition."""
        return True

    def get_result_name_override(self, code_generator):
        """Gets a value that overrides the code generator's result name for this
           instruction if it is not None."""
        return None

    def generate_python_def(self, code_generator):
        """Generates a Python statement that executes this instruction.
           The statement is appended immediately to the code generator."""
        if self.has_definition():
            raise NotImplementedError()
        else:
            code_generator.append_line('pass')

    def generate_python_use(self, code_generator):
        """Generates a Python expression that retrieves this instruction's
           result. The expression is returned as a string."""
        if self.has_result():
            return code_generator.get_result_name(self)
        else:
            return 'None'

    def get_children(self):
        """Gets this instruction's sequence of child instructions."""
        raise NotImplementedError()

    def create(self, new_children):
        """Creates a new instruction of this type from the given sequence of child instructions."""
        raise NotImplementedError()

    def simplify_node(self):
        """Applies basic simplification to this instruction only."""
        return self

    def simplify(self):
        """Applies basic simplification to this instruction and all of its children."""
        # This fairly convoluted one-liner first simplifies all children, then creates
        # an instruction from the simplified children, and finally simplifies that top-level
        # instruction.
        return self.create([c.simplify() for c in self.get_children()]).simplify_node()

    def __str__(self):
        code_generator = PythonGenerator()
        self.generate_python_def(code_generator)
        return str(code_generator)

class PythonGenerator(object):
    """Generates Python code from instructions."""

    def __init__(self, combine_state_definitions=True):
        self.code = []
        self.state_definitions = []
        self.state_definition_names = set()
        self.indentation_string = ' ' * 4
        self.indentation = 0
        self.result_name_dict = {}
        self.combine_state_definitions = combine_state_definitions

    def append(self, text):
        """Appends the given string to this code generator."""
        self.flush_state_definitions()
        self.code.append(text)

    def append_indentation(self):
        """Appends indentation to the code generator."""
        self.append(self.indentation_string * self.indentation)

    def append_line(self, line=None):
        """Appends the indentation string followed by the given string (if any)
           and a newline to the code generator."""
        self.append_indentation()
        if line is not None:
            self.append(line)
        self.append('\n')

    def increase_indentation(self):
        """Increases the code generator's indentation by one indent."""
        self.flush_state_definitions()
        self.indentation += 1

    def decrease_indentation(self):
        """Decreases the code generator's indentation by one indent."""
        self.flush_state_definitions()
        self.indentation -= 1

    def get_result_name(self, instruction, advised_name=None):
        """Gets the name of the given instruction's result variable."""
        if instruction not in self.result_name_dict:
            override_name = instruction.get_result_name_override(self)
            if override_name is not None:
                self.result_name_dict[instruction] = override_name
            elif advised_name is not None:
                self.result_name_dict[instruction] = advised_name
            else:
                self.result_name_dict[instruction] = \
                    'tmp' + str(len(self.result_name_dict))

        result = self.result_name_dict[instruction]
        if result in self.state_definition_names:
            # This might mean that we're trying to access a name that is
            # defined by the current block of state definitions. So we need
            # to flush the state definitions now.
            self.flush_state_definitions()

        return result

    def append_definition(self, lhs, rhs):
        """Defines the first instruction's result variable as the second
           instruction's result."""
        self.append_line(
            self.get_result_name(lhs) + ' = ' + rhs.generate_python_use(self))

    def append_move_definition(self, lhs, rhs):
        """First defines the second instruction, then defines the first
           instruction as the result of the second."""
        if rhs.has_definition():
            # Retrieve the result name for the lhs.
            lhs_result_name = self.get_result_name(lhs)
            # Encourage the rhs to take on the same result name as the lhs.
            rhs_result_name = self.get_result_name(rhs, lhs_result_name)
            # Generate the rhs' definition.
            rhs.generate_python_def(self)
            # Only perform an assignment if it's truly necessary.
            if lhs_result_name != rhs_result_name:
                self.append_definition(lhs, rhs)
        else:
            self.append_definition(lhs, rhs)

    def append_state_definition(self, lhs, opcode, args):
        """Appends a definition that queries the modelverse state."""
        result_name = self.get_result_name(lhs)
        request_tuple = '(%s, [%s])' % (
            repr(opcode),
            ', '.join([arg_i.generate_python_use(self) for arg_i in args]))
        self.state_definitions.append((result_name, request_tuple))
        self.state_definition_names.add(result_name)
        if not self.combine_state_definitions:
            self.flush_state_definitions()

    def flush_state_definitions(self):
        """Flushes the list of state-access definitions to the generated code."""
        state_defs = self.state_definitions
        if len(state_defs) > 0:
            # Clear state_definitions _before_ calling append_line, because append_line
            # will call flush_state_definitions. Clearing state_definitions afterward
            # will result in infinite recursion.
            self.state_definitions = []
            self.state_definition_names = set()
            if len(state_defs) == 1:
                self.append_line('%s, = yield [%s]' % state_defs[0])
            else:
                self.append_line(
                    "%s = yield [%s]" % (
                        ', '.join([name for name, _ in state_defs]),
                        ', '.join([def_val for _, def_val in state_defs])))

    def __str__(self):
        self.flush_state_definitions()
        return ''.join(self.code)

class VoidInstruction(Instruction):
    """A base class for instructions that do not return a value."""

    def get_result_type_impl(self):
        """Gets this instruction's result type."""
        return NO_RESULT_TYPE

    def get_children(self):
        """Gets this instruction's sequence of child instructions."""
        return []

    def create(self, new_children):
        """Creates a new instruction of this type from the given sequence of child instructions."""
        return self

class EmptyInstruction(VoidInstruction):
    """Represents the empty instruction, which does nothing."""

    def has_definition_impl(self):
        """Tells if this instruction requires a definition."""
        return False

class SelectInstruction(Instruction):
    """Represents a select-instruction: an instruction that defines one of two
       child instructions, and sets its result to the defined child's result."""
    def __init__(self, condition, if_clause, else_clause):
        Instruction.__init__(self)
        self.condition = condition
        self.if_clause = if_clause
        self.else_clause = else_clause

    def get_result_type_impl(self):
        """Gets this instruction's result type."""
        return result_type_intersection(
            self.if_clause.get_result_type(),
            self.else_clause.get_result_type())

    def simplify_node(self):
        """Applies basic simplification to this instruction only."""
        if isinstance(self.condition, LiteralInstruction):
            return self.if_clause if self.condition.literal else self.else_clause
        else:
            return SelectInstruction(self.condition, self.if_clause, self.else_clause)

    def get_children(self):
        """Gets this instruction's sequence of child instructions."""
        return [self.condition, self.if_clause, self.else_clause]

    def create(self, new_children):
        """Creates a new instruction of this type from the given sequence of child instructions."""
        condition, if_clause, else_clause = new_children
        return SelectInstruction(condition, if_clause, else_clause)

    def generate_python_def(self, code_generator):
        """Generates Python code for this instruction."""
        if_has_result = self.has_result()
        if self.condition.has_definition():
            self.condition.generate_python_def(code_generator)

        code_generator.append_line(
            'if ' + self.condition.generate_python_use(code_generator) + ':')
        code_generator.increase_indentation()
        if if_has_result:
            code_generator.append_move_definition(self, self.if_clause)
        else:
            self.if_clause.generate_python_def(code_generator)
        code_generator.decrease_indentation()
        else_has_def = self.else_clause.has_definition()
        if else_has_def or if_has_result:
            code_generator.append_line('else:')
            code_generator.increase_indentation()
            if if_has_result:
                code_generator.append_move_definition(self, self.else_clause)
            else:
                self.else_clause.generate_python_def(code_generator)
            code_generator.decrease_indentation()

class ReturnInstruction(VoidInstruction):
    """Represents a return-instruction."""
    def __init__(self, value):
        VoidInstruction.__init__(self)
        self.value = value

    def get_children(self):
        """Gets this instruction's sequence of child instructions."""
        return [self.value]

    def create(self, new_children):
        """Creates a new instruction of this type from the given sequence of child instructions."""
        value, = new_children
        return ReturnInstruction(value)

    def simplify_node(self):
        """Applies basic simplification to this instruction only."""
        # If we have a return whose value is a call, then we can rewrite
        # that as a tail call and save us a stack frame.
        def rewrite_call(instruction):
            """Rewrites the given instruction in tail-call form, or returns
               None."""
            if isinstance(instruction, RunGeneratorFunctionInstruction):
                return RunTailGeneratorFunctionInstruction(*instruction.get_children())
            elif isinstance(instruction, CompoundInstruction):
                snd_rewritten = rewrite_call(instruction.second)
                if snd_rewritten is not None:
                    return CompoundInstruction(instruction.first, snd_rewritten)

            return None

        rewritten_value = rewrite_call(self.value)
        if rewritten_value is None:
            return self
        else:
            # We don't even need to create a return here, because tail calls terminate
            # the current stack frame anyway.
            return rewritten_value

    def generate_python_def(self, code_generator):
        """Generates Python code for this instruction."""
        if self.value.has_definition():
            self.value.generate_python_def(code_generator)
        code_generator.append_line(
            'raise PrimitiveFinished(' +
            self.value.generate_python_use(code_generator) +
            ')')

class RaiseInstruction(VoidInstruction):
    """An instruction that raises an error."""
    def __init__(self, value):
        VoidInstruction.__init__(self)
        self.value = value

    def get_children(self):
        """Gets this instruction's sequence of child instructions."""
        return [self.value]

    def create(self, new_children):
        """Creates a new instruction of this type from the given sequence of child instructions."""
        value, = new_children
        return RaiseInstruction(value)

    def generate_python_def(self, code_generator):
        """Generates Python code for this instruction."""
        self.value.generate_python_def(code_generator)
        code_generator.append_line(
            'raise ' + self.value.generate_python_use(code_generator))

class CallInstruction(Instruction):
    """An instruction that performs a simple call."""
    def __init__(self, target, argument_list):
        Instruction.__init__(self)
        self.target = target
        self.argument_list = argument_list

    def get_children(self):
        """Gets this instruction's sequence of child instructions."""
        return [self.target] + self.argument_list

    def create(self, new_children):
        """Creates a new instruction of this type from the given sequence of child instructions."""
        return CallInstruction(new_children[0], new_children[1:])

    def generate_python_def(self, code_generator):
        """Generates Python code for this instruction."""
        if self.target.has_definition():
            self.target.generate_python_def(code_generator)

        for arg in self.argument_list:
            if arg.has_definition():
                arg.generate_python_def(code_generator)

        code_generator.append_line(
            '%s = %s(%s)' % (
                code_generator.get_result_name(self),
                self.target.generate_python_use(code_generator),
                ', '.join([arg.generate_python_use(code_generator) for arg in self.argument_list])))

class PrintInstruction(VoidInstruction):
    """An instruction that prints a value."""
    def __init__(self, argument):
        VoidInstruction.__init__(self)
        self.argument = argument

    def get_children(self):
        """Gets this instruction's sequence of child instructions."""
        return [self.argument]

    def create(self, new_children):
        """Creates a new instruction of this type from the given sequence of child instructions."""
        arg, = new_children
        return PrintInstruction(arg)

    def generate_python_def(self, code_generator):
        """Generates Python code for this instruction."""
        if self.argument.has_definition():
            self.argument.generate_python_def(code_generator)

        code_generator.append_line(
            'print(%s)' % (
                self.argument.generate_python_use(code_generator)))

class BinaryInstruction(Instruction):
    """An instruction that performs a binary operation."""
    def __init__(self, lhs, operator, rhs):
        Instruction.__init__(self)
        self.lhs = lhs
        self.operator = operator
        self.rhs = rhs

    def has_definition_impl(self):
        """Tells if this instruction requires a definition."""
        return self.lhs.has_definition() or self.rhs.has_definition()

    def get_children(self):
        """Gets this instruction's sequence of child instructions."""
        return [self.lhs, self.rhs]

    def create(self, new_children):
        """Creates a new instruction of this type from the given sequence of child instructions."""
        lhs, rhs, = new_children
        return BinaryInstruction(lhs, self.operator, rhs)

    def simplify_node(self):
        """Applies basic simplification to this instruction only."""
        if isinstance(self.lhs, LiteralInstruction) and isinstance(self.rhs, LiteralInstruction):
            # TODO: there's probably a better way to do this than with eval.
            return LiteralInstruction(
                eval('%s %s %s' % (repr(self.lhs.literal), self.operator, repr(self.rhs.literal))))
        else:
            return self

    def generate_python_use(self, code_generator):
        """Generates a Python expression that retrieves this instruction's
           result. The expression is returned as a string."""
        return '(%s %s %s)' % (
            self.lhs.generate_python_use(code_generator),
            self.operator,
            self.rhs.generate_python_use(code_generator))

    def generate_python_def(self, code_generator):
        """Generates a Python statement that executes this instruction.
           The statement is appended immediately to the code generator."""
        if self.lhs.has_definition():
            self.lhs.generate_python_def(code_generator)
            if self.rhs.has_definition():
                self.rhs.generate_python_def(code_generator)
        elif self.rhs.has_definition():
            self.rhs.generate_python_def(code_generator)
        else:
            code_generator.append_line('pass')

class UnaryInstruction(Instruction):
    """An instruction that performs a unary operation."""
    def __init__(self, operator, operand):
        Instruction.__init__(self)
        self.operator = operator
        self.operand = operand

    def has_definition_impl(self):
        """Tells if this instruction requires a definition."""
        return self.operand.has_definition()

    def get_children(self):
        """Gets this instruction's sequence of child instructions."""
        return [self.operand]

    def create(self, new_children):
        """Creates a new instruction of this type from the given sequence of child instructions."""
        operand, = new_children
        return UnaryInstruction(self.operator, operand)

    def simplify_node(self):
        """Applies basic simplification to this instruction only."""
        if isinstance(self.operand, LiteralInstruction):
            # TODO: there's probably a better way to do this than with eval.
            return LiteralInstruction(
                eval('%s %s' % (self.operator, repr(self.operand.literal))))
        else:
            return self

    def generate_python_use(self, code_generator):
        """Generates a Python expression that retrieves this instruction's
           result. The expression is returned as a string."""
        return '(%s %s)' % (
            self.operator,
            self.operand.generate_python_use(code_generator))

    def generate_python_def(self, code_generator):
        """Generates a Python statement that executes this instruction.
           The statement is appended immediately to the code generator."""
        if self.operand.has_definition():
            self.operand.generate_python_def(code_generator)
        else:
            code_generator.append_line('pass')

class LoopInstruction(VoidInstruction):
    """Represents a loop-instruction, which loops until broken."""

    def __init__(self, body):
        VoidInstruction.__init__(self)
        self.body = body

    def get_children(self):
        """Gets this instruction's sequence of child instructions."""
        return [self.body]

    def create(self, new_children):
        """Creates a new instruction of this type from the given sequence of child instructions."""
        body, = new_children
        return LoopInstruction(body)

    def generate_python_def(self, code_generator):
        """Generates Python code for this instruction."""
        code_generator.append_line('while 1:')
        code_generator.increase_indentation()
        self.body.generate_python_def(code_generator)
        code_generator.decrease_indentation()

class BreakInstruction(VoidInstruction):
    """Represents a break-instruction."""
    def generate_python_def(self, code_generator):
        """Generates Python code for this instruction."""
        code_generator.append_line('break')

class ContinueInstruction(VoidInstruction):
    """Represents a continue-instruction."""
    def generate_python_def(self, code_generator):
        """Generates Python code for this instruction."""
        code_generator.append_line('continue')

class CompoundInstruction(Instruction):
    """Represents an instruction that evaluates two other instructions
       in order, and returns the second instruction's result."""
    def __init__(self, first, second):
        Instruction.__init__(self)
        self.first = first
        self.second = second

    def get_result_type_impl(self):
        """Gets this instruction's result type."""
        if self.second.has_result():
            return self.second.get_result_type()
        else:
            return self.first.get_result_type()

    def get_children(self):
        """Gets this instruction's sequence of child instructions."""
        return [self.first, self.second]

    def create(self, new_children):
        """Creates a new instruction of this type from the given sequence of child instructions."""
        first, second = new_children
        return CompoundInstruction(first, second)

    def simplify_node(self):
        """Applies basic simplification to this instruction and its children."""
        if not self.first.has_definition() and (
                not self.first.has_result() or self.second.has_result()):
            return self.second
        elif (not self.second.has_definition()) and (not self.second.has_result()):
            return self.first
        else:
            return self

    def generate_python_def(self, code_generator):
        """Generates Python code for this instruction."""
        if self.second.has_result():
            self.first.generate_python_def(code_generator)
            code_generator.append_move_definition(self, self.second)
        elif self.first.has_result():
            code_generator.append_move_definition(self, self.first)
            self.second.generate_python_def(code_generator)
        else:
            self.first.generate_python_def(code_generator)
            self.second.generate_python_def(code_generator)

class LiteralInstruction(Instruction):
    """Represents an integer, floating-point, string or Boolean literal."""
    def __init__(self, literal):
        Instruction.__init__(self)
        self.literal = literal

    def has_definition_impl(self):
        """Tells if this instruction requires a definition."""
        return False

    def get_children(self):
        """Gets this instruction's sequence of child instructions."""
        return []

    def create(self, new_children):
        """Creates a new instruction of this type from the given sequence of child instructions."""
        return self

    def generate_python_use(self, code_generator):
        """Generates a Python expression that retrieves this instruction's
           result. The expression is returned as a string."""
        return repr(self.literal)

class DictionaryLiteralInstruction(Instruction):
    """Constructs a dictionary literal."""
    def __init__(self, key_value_pairs):
        Instruction.__init__(self)
        self.key_value_pairs = key_value_pairs

    def get_children(self):
        """Gets this instruction's sequence of child instructions."""
        return [val for _, val in self.key_value_pairs]

    def create(self, new_children):
        """Creates a new instruction of this type from the given sequence of child instructions."""
        keys = [k for k, _ in self.key_value_pairs]
        return DictionaryLiteralInstruction(zip(keys, new_children))

    def has_definition_impl(self):
        """Tells if this instruction requires a definition."""
        return any(
            [key.has_definition() or val.has_definition()
             for key, val in self.key_value_pairs])

    def simplify(self):
        """Applies basic simplification to this instruction and its children."""
        return DictionaryLiteralInstruction(
            [(key.simplify(), val.simplify()) for key, val in self.key_value_pairs])

    def generate_dictionary_expr(self, code_generator):
        """Generates an expression that creates this dictionary."""
        return '{%s}' % ', '.join(
            ['%s : %s' % (
                key.generate_python_use(code_generator),
                val.generate_python_use(code_generator))
             for key, val in self.key_value_pairs])

    def generate_python_def(self, code_generator):
        """Generates a Python statement that executes this instruction.
            The statement is appended immediately to the code generator."""
        if self.has_definition():
            for key, val in self.key_value_pairs:
                if key.has_definition():
                    key.generate_python_def(code_generator)
                if val.has_definition():
                    val.generate_python_def(code_generator)

            code_generator.append_line('%s = %s' % (
                code_generator.get_result_name(self),
                self.generate_dictionary_expr(code_generator)))
        else:
            code_generator.append_line('pass')

    def generate_python_use(self, code_generator):
        """Generates a Python expression that retrieves this instruction's
           result. The expression is returned as a string."""
        if self.has_definition():
            return code_generator.get_result_name(self)
        else:
            return self.generate_dictionary_expr(code_generator)

class StateInstruction(Instruction):
    """An instruction that accesses the modelverse state."""
    def get_result_type_impl(self):
        """Gets the type of value produced by this instruction."""
        return NODE_RESULT_TYPE

    def get_opcode(self):
        """Gets the opcode for this state instruction."""
        raise NotImplementedError()

    def get_arguments(self):
        """Gets this state instruction's argument list."""
        raise NotImplementedError()

    def get_children(self):
        """Gets this instruction's sequence of child instructions."""
        return self.get_arguments()

    def create(self, new_children):
        """Creates a new instruction of this type from the given sequence of child instructions."""
        return type(self)(*new_children)

    def generate_python_def(self, code_generator):
        """Generates a Python statement that executes this instruction.
           The statement is appended immediately to the code generator."""

        args = self.get_arguments()
        for arg_i in args:
            if arg_i.has_definition():
                arg_i.generate_python_def(code_generator)

        code_generator.append_state_definition(self, self.get_opcode(), args)

class RunGeneratorFunctionInstruction(StateInstruction):
    """An instruction that runs a generator function."""
    def __init__(self, function, argument_dict, result_type=PRIMITIVE_RESULT_TYPE):
        StateInstruction.__init__(self)
        self.function = function
        self.argument_dict = argument_dict
        self.result_type_cache = result_type

    def get_opcode(self):
        """Gets the opcode for this state instruction."""
        return "CALL_KWARGS"

    def get_arguments(self):
        """Gets this state instruction's argument list."""
        return [self.function, self.argument_dict]

    def create(self, new_children):
        """Creates a new instruction of this type from the given sequence of child instructions."""
        func, arg_dict = new_children
        return RunGeneratorFunctionInstruction(func, arg_dict, self.get_result_type())

class RunTailGeneratorFunctionInstruction(StateInstruction):
    """An instruction that runs a generator function."""
    def __init__(self, function, argument_dict):
        StateInstruction.__init__(self)
        self.function = function
        self.argument_dict = argument_dict

    def get_result_type_impl(self):
        """Gets the type of value produced by this instruction."""
        return NO_RESULT_TYPE

    def get_opcode(self):
        """Gets the opcode for this state instruction."""
        return "TAIL_CALL_KWARGS"

    def get_arguments(self):
        """Gets this state instruction's argument list."""
        return [self.function, self.argument_dict]

class VariableName(object):
    """A data structure that unifies names across instructions that access the
       same variable."""
    def __init__(self, name):
        self.name = name

    def get_result_name_override(self, _):
        """Gets a value that overrides the code generator's result name for this
           instruction if it is not None."""
        return self.name

class VariableInstruction(Instruction):
    """A base class for instructions that access variables."""
    def __init__(self, name):
        Instruction.__init__(self)
        if isinstance(name, str) or isinstance(name, unicode) or name is None:
            self.name = VariableName(name)
        else:
            self.name = name

    def get_children(self):
        """Gets this instruction's sequence of child instructions."""
        raise NotImplementedError()

    def create(self, new_children):
        """Creates a new instruction of this type from the given sequence of child instructions."""
        raise NotImplementedError()

    def get_result_name_override(self, code_generator):
        """Gets a value that overrides the code generator's result name for this
           instruction if it is not None."""
        return code_generator.get_result_name(self.name)

class LocalInstruction(VariableInstruction):
    """A base class for instructions that access local variables."""
    def get_children(self):
        """Gets this instruction's sequence of child instructions."""
        raise NotImplementedError()

    def create(self, new_children):
        """Creates a new instruction of this type from the given sequence of child instructions."""
        raise NotImplementedError()

    def create_load(self):
        """Creates an instruction that loads the variable referenced by this instruction."""
        return LoadLocalInstruction(self.name)

    def create_store(self, value):
        """Creates an instruction that stores the given value in the variable referenced
           by this instruction."""
        return StoreLocalInstruction(self.name, value)

class StoreLocalInstruction(LocalInstruction):
    """An instruction that stores a value in a local variable."""
    def __init__(self, name, value):
        LocalInstruction.__init__(self, name)
        self.value = value

    def get_children(self):
        """Gets this instruction's sequence of child instructions."""
        return [self.value]

    def create(self, new_children):
        """Creates a new instruction of this type from the given sequence of child instructions."""
        val, = new_children
        return StoreLocalInstruction(self.name, val)

    def generate_python_def(self, code_generator):
        """Generates a Python statement that executes this instruction.
           The statement is appended immediately to the code generator."""
        code_generator.append_move_definition(self, self.value)

class LoadLocalInstruction(LocalInstruction):
    """An instruction that loads a value from a local variable."""
    def has_definition_impl(self):
        """Tells if this instruction requires a definition."""
        return False

    def get_children(self):
        """Gets this instruction's sequence of child instructions."""
        return []

    def create(self, new_children):
        """Creates a new instruction of this type from the given sequence of child instructions."""
        return self

class DefineFunctionInstruction(VariableInstruction):
    """An instruction that defines a function."""
    def __init__(self, name, parameter_list, body):
        VariableInstruction.__init__(self, name)
        self.parameter_list = parameter_list
        self.body = body

    def get_children(self):
        """Gets this instruction's sequence of child instructions."""
        return [self.body]

    def create(self, new_children):
        """Creates a new instruction of this type from the given sequence of child instructions."""
        body, = new_children
        return DefineFunctionInstruction(self.name, self.parameter_list, body)

    def generate_python_def(self, code_generator):
        """Generates a Python statement that executes this instruction.
           The statement is appended immediately to the code generator."""
        code_generator.append_line('def %s(%s):' % (
            code_generator.get_result_name(self), ', '.join(self.parameter_list)))
        code_generator.increase_indentation()
        self.body.generate_python_def(code_generator)
        code_generator.decrease_indentation()

class LocalExistsInstruction(LocalInstruction):
    """An instruction that checks if a local variable exists."""
    def has_definition_impl(self):
        """Tells if this instruction requires a definition."""
        return False

    def get_children(self):
        """Gets this instruction's sequence of child instructions."""
        return []

    def create(self, new_children):
        """Creates a new instruction of this type from the given sequence of child instructions."""
        return self

    def generate_python_use(self, code_generator):
        """Generates a Python expression that retrieves this instruction's
           result. The expression is returned as a string."""
        return "'%s' in locals()" % self.get_result_name_override(code_generator)

class LoadGlobalInstruction(VariableInstruction):
    """An instruction that loads a value from a global variable."""
    def has_definition_impl(self):
        """Tells if this instruction requires a definition."""
        return False

    def get_children(self):
        """Gets this instruction's sequence of child instructions."""
        return []

    def create(self, new_children):
        """Creates a new instruction of this type from the given sequence of child instructions."""
        return self

class LoadIndexInstruction(Instruction):
    """An instruction that produces a value by indexing a specified expression with
       a given key."""
    def __init__(self, indexed, key):
        Instruction.__init__(self)
        self.indexed = indexed
        self.key = key

    def has_definition_impl(self):
        """Tells if this instruction requires a definition."""
        return False

    def get_children(self):
        """Gets this instruction's sequence of child instructions."""
        return [self.indexed, self.key]

    def create(self, new_children):
        """Creates a new instruction of this type from the given sequence of child instructions."""
        indexed, key = new_children
        return LoadIndexInstruction(indexed, key)

    def generate_python_use(self, code_generator):
        """Generates a Python expression that retrieves this instruction's
           result. The expression is returned as a string."""
        if self.indexed.has_definition():
            self.indexed.generate_python_def(code_generator)

        if self.key.has_definition():
            self.key.generate_python_def(code_generator)

        return "%s[%s]" % (
            self.indexed.generate_python_use(code_generator),
            self.key.generate_python_use(code_generator))

class LoadMemberInstruction(Instruction):
    """An instruction that produces a value by loading a member from a container."""
    def __init__(self, container, member_name):
        Instruction.__init__(self)
        self.container = container
        self.member_name = member_name

    def has_definition_impl(self):
        """Tells if this instruction requires a definition."""
        return self.container.has_definition()

    def get_children(self):
        """Gets this instruction's sequence of child instructions."""
        return [self.container]

    def create(self, new_children):
        """Creates a new instruction of this type from the given sequence of child instructions."""
        container, = new_children
        return LoadMemberInstruction(container, self.member_name)

    def generate_python_def(self, code_generator):
        """Generates a Python statement that executes this instruction.
           The statement is appended immediately to the code generator."""
        self.container.generate_python_def(code_generator)

    def generate_python_use(self, code_generator):
        """Generates a Python expression that retrieves this instruction's
           result. The expression is returned as a string."""
        return "%s.%s" % (
            self.container.generate_python_use(code_generator),
            self.member_name)

class StoreMemberInstruction(VoidInstruction):
    """An instruction that stores a value in a container member."""
    def __init__(self, container, member_name, value):
        VoidInstruction.__init__(self)
        self.container = container
        self.member_name = member_name
        self.value = value

    def has_definition_impl(self):
        """Tells if this instruction requires a definition."""
        return True

    def get_children(self):
        """Gets this instruction's sequence of child instructions."""
        return [self.container, self.value]

    def create(self, new_children):
        """Creates a new instruction of this type from the given sequence of child instructions."""
        container, value = new_children
        return StoreMemberInstruction(container, self.member_name, value)

    def generate_python_def(self, code_generator):
        """Generates a Python statement that executes this instruction.
           The statement is appended immediately to the code generator."""
        if self.container.has_definition():
            self.container.generate_python_def(code_generator)
        code_generator.append_line('%s.%s = %s' % (
            self.container.generate_python_use(code_generator),
            self.member_name,
            self.value.generate_python_use(code_generator)))

class NopInstruction(VoidInstruction):
    """A nop instruction, which allows for the kernel's thread of execution to be interrupted."""
    def generate_python_def(self, code_generator):
        """Generates a Python statement that executes this instruction.
           The statement is appended immediately to the code generator."""
        code_generator.append_line('yield %s' % repr(NOP_LITERAL))

class ReadValueInstruction(StateInstruction):
    """An instruction that reads a value from a node."""
    def __init__(self, node_id):
        StateInstruction.__init__(self)
        self.node_id = node_id

    def get_result_type_impl(self):
        """Gets the type of value produced by this instruction."""
        return PRIMITIVE_RESULT_TYPE

    def simplify_node(self):
        """Applies basic simplification to this instruction only."""
        if isinstance(self.node_id, CreateNodeWithValueInstruction):
            return self.node_id.value
        else:
            return self

    def get_opcode(self):
        """Gets the opcode for this state instruction."""
        return "RV"

    def get_arguments(self):
        """Gets this state instruction's argument list."""
        return [self.node_id]

class ReadDictionaryValueInstruction(StateInstruction):
    """An instruction that reads a dictionary value."""
    def __init__(self, node_id, key):
        StateInstruction.__init__(self)
        self.node_id = node_id
        self.key = key

    def get_opcode(self):
        """Gets the opcode for this state instruction."""
        return "RD"

    def get_arguments(self):
        """Gets this state instruction's argument list."""
        return [self.node_id, self.key]

class ReadDictionaryEdgeInstruction(StateInstruction):
    """An instruction that reads a dictionary edge."""
    def __init__(self, node_id, key):
        StateInstruction.__init__(self)
        self.node_id = node_id
        self.key = key

    def get_opcode(self):
        """Gets the opcode for this state instruction."""
        return "RDE"

    def get_arguments(self):
        """Gets this state instruction's argument list."""
        return [self.node_id, self.key]

class ReadEdgeInstruction(StateInstruction):
    """An instruction that reads an edge."""
    def __init__(self, node_id):
        StateInstruction.__init__(self)
        self.node_id = node_id

    def get_opcode(self):
        """Gets the opcode for this state instruction."""
        return "RE"

    def get_arguments(self):
        """Gets this state instruction's argument list."""
        return [self.node_id]

class ReadOutgoingEdgesInstruction(StateInstruction):
    """An instruction that reads all outgoing edges for a node."""
    def __init__(self, node_id):
        StateInstruction.__init__(self)
        self.node_id = node_id

    def get_result_type_impl(self):
        """Gets the type of value produced by this instruction."""
        return PRIMITIVE_RESULT_TYPE

    def get_opcode(self):
        """Gets the opcode for this state instruction."""
        return "RO"

    def get_arguments(self):
        """Gets this state instruction's argument list."""
        return [self.node_id]

class ReadIncomingEdgesInstruction(StateInstruction):
    """An instruction that reads all incoming edges for a node."""
    def __init__(self, node_id):
        StateInstruction.__init__(self)
        self.node_id = node_id

    def get_result_type_impl(self):
        """Gets the type of value produced by this instruction."""
        return PRIMITIVE_RESULT_TYPE

    def get_opcode(self):
        """Gets the opcode for this state instruction."""
        return "RI"

    def get_arguments(self):
        """Gets this state instruction's argument list."""
        return [self.node_id]

class CreateNodeInstruction(StateInstruction):
    """An instruction that creates an empty node."""
    def get_opcode(self):
        """Gets the opcode for this state instruction."""
        return "CN"

    def get_arguments(self):
        """Gets this state instruction's argument list."""
        return []

class CreateNodeWithValueInstruction(StateInstruction):
    """An instruction that creates a node with a given value."""
    def __init__(self, value):
        StateInstruction.__init__(self)
        self.value = value

    def get_opcode(self):
        """Gets the opcode for this state instruction."""
        return "CNV"

    def get_arguments(self):
        """Gets this state instruction's argument list."""
        return [self.value]

class CreateEdgeInstruction(StateInstruction):
    """An instruction that creates an edge."""
    def __init__(self, source_id, target_id):
        StateInstruction.__init__(self)
        self.source_id = source_id
        self.target_id = target_id

    def get_opcode(self):
        """Gets the opcode for this state instruction."""
        return "CE"

    def get_arguments(self):
        """Gets this state instruction's argument list."""
        return [self.source_id, self.target_id]

class CreateDictionaryEdgeInstruction(StateInstruction):
    """An instruction that creates a dictionary edge."""
    def __init__(self, source_id, key, target_id):
        StateInstruction.__init__(self)
        self.source_id = source_id
        self.key = key
        self.target_id = target_id

    def get_opcode(self):
        """Gets the opcode for this state instruction."""
        return "CD"

    def get_arguments(self):
        """Gets this state instruction's argument list."""
        return [self.source_id, self.key, self.target_id]

class DeleteNodeInstruction(StateInstruction):
    """An instruction that deletes a node."""
    def __init__(self, node_id):
        StateInstruction.__init__(self)
        self.node_id = node_id

    def get_result_type_impl(self):
        """Gets the type of value produced by this instruction."""
        return NO_RESULT_TYPE

    def get_opcode(self):
        """Gets the opcode for this state instruction."""
        return "DN"

    def get_arguments(self):
        """Gets this state instruction's argument list."""
        return [self.node_id]

class DeleteEdgeInstruction(StateInstruction):
    """An instruction that deletes an edge."""
    def __init__(self, edge_id):
        StateInstruction.__init__(self)
        self.edge_id = edge_id

    def get_result_type_impl(self):
        """Gets the type of value produced by this instruction."""
        return NO_RESULT_TYPE

    def get_opcode(self):
        """Gets the opcode for this state instruction."""
        return "DE"

    def get_arguments(self):
        """Gets this state instruction's argument list."""
        return [self.edge_id]

def create_block(*statements):
    """Creates a block-statement from the given list of statements."""
    length = len(statements)
    if length == 0:
        return EmptyInstruction()
    elif length == 1:
        return statements[0]
    else:
        return CompoundInstruction(
            statements[0],
            create_block(*statements[1:]))

def create_jit_call(target, named_arguments, kwargs):
    """Creates a call that abides by the JIT's calling convention."""
    # A JIT call looks like this:
    #
    # target = ...
    # arg_dict = { ... }
    # arg_dict.update(kwargs)
    # result, = yield [("CALL_KWARGS", [target, arg_dict])]

    results = []
    if target.has_definition():
        target_tmp = StoreLocalInstruction(None, target)
        results.append(target_tmp)
        target = target_tmp.create_load()

    arg_dict = StoreLocalInstruction(
        None,
        DictionaryLiteralInstruction(
            [(LiteralInstruction(key), val) for key, val in named_arguments]))
    results.append(arg_dict)
    results.append(
        CallInstruction(
            LoadMemberInstruction(arg_dict.create_load(), 'update'),
            [kwargs]))
    return CompoundInstruction(
        create_block(*results),
        RunGeneratorFunctionInstruction(
            target, arg_dict.create_load(), NODE_RESULT_TYPE))

def create_new_local_node(local_variable, connected_node, edge_variable=None):
    """Creates a local node that is the backing storage for a local variable.
       This node is connected to a given node to make sure it's not perceived
       as dead by the GC. The newly created node is stored in the given
       local variable. The edge's id can also optionally be stored in a variable."""
    local_store = StoreLocalInstruction(local_variable, CreateNodeInstruction())
    create_edge = CreateEdgeInstruction(connected_node, local_store.create_load())
    if edge_variable is not None:
        create_edge = StoreLocalInstruction(edge_variable, create_edge)

    return create_block(local_store, create_edge)

def with_debug_info_trace(instruction, debug_info, function_name):
    """Prepends the given instruction with a tracing instruction that prints
       the given debug information and function name."""
    if debug_info is None and function_name is None:
        return instruction
    else:
        if debug_info is None:
            debug_info = 'unknown location '
        if function_name is None:
            function_name = 'unknown function'
        return create_block(
            PrintInstruction(
                LiteralInstruction('TRACE: %s(%s, JIT)' % (debug_info, function_name))),
            instruction)

def map_instruction_tree_top_down(function, instruction):
    """Applies the given mapping function to every instruction in the tree
       that has the given instruction as root. The map is applied in a top-down
       fashion."""
    mapped_instruction = function(instruction)
    return mapped_instruction.create(
        [map_instruction_tree_top_down(function, child)
         for child in mapped_instruction.get_children()])

def map_and_simplify(function, instruction):
    """Applies the given mapping function to every instruction in the tree
       that has the given instruction as root, and simplifies it on-the-fly.
       The map is applied in a bottom-up fashion.

       This is at least as powerful as first mapping and then simplifying, as
       maps and simplifications are interspersed."""
    return function(
        instruction.create(
            [map_and_simplify(function, child)
             for child in instruction.get_children()])).simplify_node()

def iterate_as_stack(instruction, stack_iterator):
    """Iterates over the given instruction and its children in the order in which temporaries are
    'pushed' on and 'popped' from a virtual evaluation stack."""
    if isinstance(instruction, SelectInstruction):
        iterate_as_stack(instruction.condition, stack_iterator)
        stack_iterator.pop()
        if_iterator, else_iterator = stack_iterator.branch(), stack_iterator.branch()
        iterate_as_stack(instruction.if_clause, if_iterator)
        iterate_as_stack(instruction.else_clause, else_iterator)
        stack_iterator.merge(if_iterator, else_iterator)
    elif isinstance(instruction, CompoundInstruction):
        iterate_as_stack(instruction.first, stack_iterator)
        if instruction.second.has_result():
            stack_iterator.pop()
        iterate_as_stack(instruction.second, stack_iterator)
        if not instruction.second.has_result():
            stack_iterator.pop()
    else:
        children = instruction.get_children()
        for child in children:
            # Push all children onto the stack.
            iterate_as_stack(child, stack_iterator)
        for child in children:
            # Pop all children from the stack.
            stack_iterator.pop()
        # Push the instruction.
        stack_iterator.push(instruction)

class StackIterator(object):
    """A base class for stack iterators."""
    def __init__(self, stack=None):
        self.stack = [] if stack is None else stack

    def pop(self):
        """Pops an instruction from the stack."""
        self.stack.pop()

    def push(self, instruction):
        """Pushes an instruction onto the stack."""
        self.stack.append(set([instruction]))

    def branch(self):
        """Creates a copy of this stack iterator."""
        return self.create(self.copy_stack())

    def merge(self, *branches):
        """Sets this stack iterator's stack to the union of the given branches."""
        self.__init__(self.merge_stacks(*branches))

    def copy_stack(self):
        """Creates a copy of this stack iterator's stack."""
        return [set(vals) for vals in self.stack]

    def create(self, new_stack):
        """Creates a stack iterator from the given stack"""
        return type(self)(new_stack)

    def merge_stacks(self, *branches):
        """Computes the union of the stacks of the given branches."""
        results = None
        for branch in branches:
            if results is None:
                results = branch.copy_stack()
            else:
                assert len(branch.stack) == len(results)
                results = [set.union(*t) for t in zip(branch.stack, results)]

        return results

def protect_temporaries_from_gc(instruction, connected_node):
    """Protects temporaries from the garbage collector by connecting them to the given node."""
    # # The reasoning behind this function
    #
    # A nop instruction (`yield None`) may trigger the garbage collector, which will delete
    # unreachable ("dead") vertices and edges. Now take into account that a bare temporary node
    # is actually unreachable from the root node. The consequence is that temporary nodes
    # may be garbage-collected if a nop instruction is executed while they are on the evaluation
    # "stack." This is _never_ what we want.
    #
    # To counter this, we can connect temporary nodes to a node that is reachable from the root.
    # However, we only want to create edges between edges and a known reachable node if we really
    # have to, because creating edges incurs some overhead.
    #
    # We will create an edge between a temporary and the known reachable node if and only if the
    # temporary is on the "stack" when either a nop or a call instruction is executed.

    class GCStackIterator(StackIterator):
        """A stack iterator that detects which instructions might be at risk of getting garbage
           collected."""
        def __init__(self, stack=None, gc_temporaries=None):
            StackIterator.__init__(self, stack)
            self.gc_temporaries = set() if gc_temporaries is None else gc_temporaries

        def push(self, instruction):
            """Pushes an instruction onto the stack."""
            if isinstance(instruction, (
                    NopInstruction,
                    RunGeneratorFunctionInstruction,
                    RunTailGeneratorFunctionInstruction)):
                # All values currently on the stack are at risk. Mark them as such.
                for instruction_set in self.stack:
                    self.gc_temporaries.update(instruction_set)

            # Proceed.
            StackIterator.push(self, instruction)

        def merge(self, *branches):
            """Sets this stack iterator's stack to the union of the given branches."""
            self.__init__(
                self.merge_stacks(*branches),
                set.union(*[br.gc_temporaries for br in branches]))

        def create(self, new_stack):
            """Creates a stack iterator from the given stack"""
            return GCStackIterator(new_stack, self.gc_temporaries)

    # Find out which instructions are at risk.
    gc_iterator = GCStackIterator()
    iterate_as_stack(instruction, gc_iterator)
    # These temporaries need to be protected from the GC.
    gc_temporaries = gc_iterator.gc_temporaries

    def protect_result(instruction):
        """Protects the given instruction's (temporary) result."""
        if instruction in gc_temporaries and instruction.get_result_type() == NODE_RESULT_TYPE:
            gc_temporaries.remove(instruction)
            store_instr = StoreLocalInstruction(None, instruction)
            return CompoundInstruction(
                store_instr,
                CompoundInstruction(
                    SelectInstruction(
                        BinaryInstruction(
                            store_instr.create_load(), 'is not', LiteralInstruction(None)),
                        CreateEdgeInstruction(connected_node, store_instr.create_load()),
                        EmptyInstruction()),
                    store_instr.create_load()))
        else:
            return instruction

    return map_instruction_tree_top_down(protect_result, instruction)

if __name__ == "__main__":
    example_tree = SelectInstruction(
        LiteralInstruction(True),
        LoopInstruction(
            CompoundInstruction(
                BreakInstruction(),
                CompoundInstruction(
                    EmptyInstruction(),
                    ContinueInstruction()
                )
            )
        ),
        ReturnInstruction(
            EmptyInstruction()))
    print(example_tree.simplify())