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):
        pass

    def has_result(self):
        """Tells if this instruction computes a result."""
        return True

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

    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 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 simplify(self):
        """Applies basic simplification to this instruction and its children."""

        return self

    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):
        self.code = []
        self.indentation_string = ' ' * 4
        self.indentation = 0
        self.result_value_dict = {}

    def append(self, text):
        """Appends the given string to this code generator."""
        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.indentation += 1

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

        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_value_dict:
            override_name = instruction.get_result_name_override()
            if override_name is not None:
                self.result_value_dict[instruction] = override_name
            elif advised_name is not None:
                self.result_value_dict[instruction] = advised_name
            else:
                self.result_value_dict[instruction] = \
                    'tmp' + str(len(self.result_value_dict))

        return self.result_value_dict[instruction]

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

        self.append_line(
            "%s, = yield [('%s', [%s])]" % (
                self.get_result_name(lhs),
                opcode,
                ', '.join([arg_i.generate_python_use(self) for arg_i in args])))

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

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

    def has_result(self):
        """Tells if this instruction computes a result."""
        return False

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

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

    def simplify(self):
        """Applies basic simplification to this instruction and its children."""
        simple_cond = self.condition.simplify()
        simple_if = self.if_clause.simplify()
        simple_else = self.else_clause.simplify()
        if isinstance(simple_cond, LiteralInstruction):
            return simple_if if simple_cond.literal else simple_else
        else:
            return SelectInstruction(simple_cond, simple_if, simple_else)

    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 simplify(self):
        """Applies basic simplification to this instruction and its children."""
        return ReturnInstruction(self.value.simplify())

    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 simplify(self):
        """Applies basic simplification to this instruction and its children."""
        return RaiseInstruction(self.value.simplify())

    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 simplify(self):
        """Applies basic simplification to this instruction and its children."""
        return CallInstruction(
            self.target.simplify(),
            [arg.simplify() for arg in self.argument_list])

    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 JitCallInstruction(Instruction):
    """An instruction that calls a jitted function."""
    def __init__(self, target, argument_list, kwarg):
        Instruction.__init__(self)
        self.target = target
        self.argument_list = argument_list
        self.kwarg = kwarg

    def simplify(self):
        """Applies basic simplification to this instruction and its children."""
        return JitCallInstruction(
            self.target.simplify(),
            [arg.simplify() for arg in self.argument_list],
            self.kwarg.simplify())

    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)

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

        code_generator.append_line('try:')
        code_generator.increase_indentation()
        code_generator.append_line(
            'gen = %s(%s) ' % (
                self.target.generate_python_use(code_generator),
                ', '.join(
                    [arg.generate_python_use(code_generator) for arg in self.argument_list] +
                    ['**' + self.kwarg.generate_python_use(code_generator)])))
        code_generator.append_line('inp = None')
        code_generator.append_line('while 1:')
        code_generator.increase_indentation()
        code_generator.append_line('inp = yield gen.send(inp)')
        code_generator.decrease_indentation()
        code_generator.decrease_indentation()
        code_generator.append_line('except PrimitiveFinished as ex:')
        code_generator.increase_indentation()
        code_generator.append_line('%s = ex.result' % code_generator.get_result_name(self))
        code_generator.decrease_indentation()

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(self):
        """Tells if this instruction requires a definition."""
        return self.lhs.has_definition() or self.rhs.has_definition()

    def simplify(self):
        """Applies basic simplification to this instruction and its children."""
        simple_lhs, simple_rhs = self.lhs.simplify(), self.rhs.simplify()
        return BinaryInstruction(simple_lhs, self.operator, simple_rhs)

    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 LoopInstruction(VoidInstruction):
    """Represents a loop-instruction, which loops until broken."""

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

    def simplify(self):
        """Applies basic simplification to this instruction and its children."""

        return LoopInstruction(self.body.simplify())

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

    def simplify(self):
        """Applies basic simplification to this instruction and its children."""

        simple_fst, simple_snd = self.first.simplify(), self.second.simplify()
        if not simple_fst.has_definition():
            return simple_snd
        elif (not simple_snd.has_definition()) and (not simple_snd.has_result()):
            return simple_fst
        else:
            return CompoundInstruction(simple_fst, simple_snd)

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

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

    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 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 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 VariableInstruction(Instruction):
    """A base class for instructions that access variables."""
    def __init__(self, name):
        Instruction.__init__(self)
        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

    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 self.name

class LocalInstruction(VariableInstruction):
    """A base class for instructions that access local variables."""
    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 simplify(self):
        """Applies basic simplification to this instruction and its children."""
        return StoreLocalInstruction(self.name, self.value.simplify())

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

class DefineFunctionInstruction(LocalInstruction):
    """An instruction that defines a function."""
    def __init__(self, name, parameter_list, body):
        LocalInstruction.__init__(self, name)
        self.parameter_list = parameter_list
        self.body = 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):' % (self.name, ', '.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(self):
        """Tells if this instruction requires a definition."""
        return False

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

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

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

    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 NopInstruction(Instruction):
    """A nop instruction, which allows for the kernel's thread of execution to be interrupted."""

    def has_result(self):
        """Tells if this instruction computes a result."""
        return False

    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(self):
        """Applies basic simplification to this instruction and its children."""
        simplified_node_id = self.node_id.simplify()
        if isinstance(simplified_node_id, CreateNodeWithValueInstruction):
            return simplified_node_id.value
        else:
            return ReadValueInstruction(simplified_node_id)

    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 simplify(self):
        """Applies basic simplification to this instruction and its children."""
        return ReadDictionaryValueInstruction(
            self.node_id.simplify(),
            self.key.simplify())

    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 simplify(self):
        """Applies basic simplification to this instruction and its children."""
        return ReadDictionaryEdgeInstruction(
            self.node_id.simplify(),
            self.key.simplify())

    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 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 simplify(self):
        """Applies basic simplification to this instruction and its children."""
        return CreateNodeWithValueInstruction(self.value.simplify())

    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 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 simplify(self):
        """Applies basic simplification to this instruction and its children."""
        return CreateDictionaryEdgeInstruction(
            self.source_id.simplify(),
            self.key.simplify(),
            self.target_id.simplify())

    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 simplify(self):
        """Applies basic simplification to this instruction and its children."""
        return DeleteNodeInstruction(self.node_id.simplify())

    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 simplify(self):
        """Applies basic simplification to this instruction and its children."""
        return DeleteEdgeInstruction(self.edge_id.simplify())

    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:]))

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