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.

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

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.has_result_cache = None
        self.has_definition_cache = None

    def has_result(self):
        """Tells if this instruction computes a result."""
        if self.has_result_cache is None:
            self.has_result_cache = self.has_result_impl()
        return self.has_result_cache

    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 has_result_impl(self):
        """Tells if this instruction computes a result."""
        return True

    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 has_result_impl(self):
        """Tells if this instruction computes a result."""
        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 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 has_result_impl(self):
        """Tells if this instruction computes a result."""
        return self.if_clause.has_result() or self.else_clause.has_result()

    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(Instruction):
    """An instruction that prints a value."""
    def __init__(self, argument):
        Instruction.__init__(self)
        self.argument = argument

    def has_result_impl(self):
        """Tells if this instruction has a result."""
        return False

    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 has_result_impl(self):
        """Tells if this instruction has a result."""
        return self.second.has_result() or self.first.has_result()

    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_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):
        StateInstruction.__init__(self)
        self.function = function
        self.argument_dict = argument_dict

    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]

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_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(Instruction):
    """An instruction that stores a value in a container member."""
    def __init__(self, container, member_name, value):
        Instruction.__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 has_result_impl(self):
        """Tells if this instruction computes a result."""
        return False

    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(Instruction):
    """A nop instruction, which allows for the kernel's thread of execution to be interrupted."""
    def has_result_impl(self):
        """Tells if this instruction computes a result."""
        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_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 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_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_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 has_result(self):
        """Tells if this instruction computes a result."""
        return False

    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 has_result(self):
        """Tells if this instruction computes a result."""
        return False

    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()))

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_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.

       This is at least as powerful as first mapping and then simplifying, as
       maps and simplifications are interspersed."""
    # Let's just agree to disagree on map vs list comprehensions, pylint.
    # pylint: disable=I0011,W0141
    return function(
        instruction.create(
            map(map_and_simplify, instruction.get_children()))).simplify_node()

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