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 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 code_generator.code

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 += 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):
        """Gets the name of the given instruction's result variable."""

        if instruction not in self.result_value_dict:
            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))

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()
        self.if_clause.generate_python_def(code_generator)
        if if_has_result:
            code_generator.append_definition(self, self.if_clause)
        code_generator.decrease_indentation()
        if self.else_clause.has_definition() or if_has_result:
            code_generator.append_line('else:')
            code_generator.increase_indentation()
            self.else_clause.generate_python_def(code_generator)
            if if_has_result:
                code_generator.append_definition(self, self.else_clause)
            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 LoopInstruction(self.value.simplify())

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

        code_generator.append_line(
            'raise PrimitiveFinished(' +
            self.value.generate_python_use(code_generator) +
            ')')

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 True:')
        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)
        self.second.generate_python_def(code_generator)
        if self.has_result():
            code_generator.append_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)

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