#!/usr/bin/env python  """ Translate the AST of a Python program into a more interpretable representation.  Copyright (C) 2007, 2008, 2009 Paul Boddie <paul@boddie.org.uk>  This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.  This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more details.  You should have received a copy of the GNU General Public License along with this program.  If not, see <http://www.gnu.org/licenses/>. """  from micropython.opt import Optimiser from micropython.common import * from micropython.data import * from micropython.rsvp import * from micropython.trans import Helper import compiler.ast from compiler.visitor import ASTVisitor  # Program visitors.  class Translation(ASTVisitor, Helper):      "A translated module."      # Attribute access instructions, for use with the appropriate handlers.      attribute_load_instructions = (         LoadAddress, LoadAddressContext, LoadAddressContextCond,         LoadAttr, LoadAttrIndex, LoadAttrIndexContextCond         )     attribute_store_instructions = (         None, None, None,         StoreAttr, StoreAttrIndex, None         )      # Name access instructions, for use with the appropriate handlers.      name_load_instructions = (LoadName, LoadAddress, None)     name_store_instructions = (StoreName, StoreAddress, StoreAddressContext)      def __init__(self, module, program):          """         Initialise the translation with an inspected 'module' and the 'program'         container.         """          ASTVisitor.__init__(self)         self.visitor = self         self.module = module          # Global program dependencies.          self.program = program         self.objtable = self.program.get_object_table()         self.paramtable = self.program.get_parameter_table()         self.importer = self.program.get_importer()         self.builtins = self.importer.modules.get("__builtins__")          # Optimisation.          self.optimiser = Optimiser(self, program.optimisations)          # The current unit being translated.          self.unit = None          # The temporary storage used by the current assignment expression.          self.expr_temp = []          # Wiring within the code.          self.labels = {}         self.label_number = 0         self.loop_blocks = []         self.exception_blocks = []         self.in_exception_handler = 0          self.reset()      def __repr__(self):         return "Translation(%r)" % self.module      def reset(self):          "Reset the state of the translator."          # The code itself. This is limited to the code for a particular block         # being processed.          self.blocks = []          # Information about temporary values.          self.temp_positions = set()         self.max_temp_position = -1          # Information about instructions which construct frames.          self.frame_makers = []          # Optimiser state must be reset for each unit.          self.optimiser.reset()      def get_module_code(self, final=0):          """         Return the top-level module code including finalising code if 'final' is         set to a true value.         """          self.unit = self.module         self.reset()          block = self.new_block()         self.set_block(block)          if self.module.module is not None:             self.dispatch(self.module.module)          # Finish off the translated program if appropriate.          if final:             self.new_op(Return())          self.unit.temp_usage = self.max_temp_position + 1         self.unit.blocks = self.blocks         return self.blocks      def get_code(self, unit):          "Return the code for the given 'unit'."          self.unit = unit         self.reset()          block = self.new_block()         self.set_block(block)          if unit.astnode is not None:             self.dispatch(unit.astnode)          self.unit.temp_usage = self.max_temp_position + 2 # include space for instantiators to expand backwards         self.unit.blocks = self.blocks         return self.blocks      def get_instantiator_code(self, cls):          "Return the code for the given class 'cls'."          self.unit = cls.get_instantiator()         self.reset()          block = self.new_block()         self.set_block(block)          init_method = cls.get_init_method()          # Make an object and store it in the unused first slot.          self.make_instance(cls, len(cls.instance_attributes()))         self.new_op(StoreTemp(0))          # Invoke the appropriate initialiser.          self.new_op(LoadFunction(init_method))         self.new_op(LoadCallable())         self.new_op(JumpInFrame())          # Store the object as the result.          self.new_op(LoadTemp(0)) # load the context from the locals         self.new_op(StoreResult())         self.new_op(Return())          self.unit.blocks = self.blocks         return self.blocks      # Visitor methods.      def default(self, node, *args):         raise TranslateError(self.module.full_name(), node, "Node class %r is not supported." % node.__class__)      def dispatch(self, node, *args):         return ASTVisitor.dispatch(self, node, *args)      # Concrete visitor methods.      # Binary operators.      visitAdd        = Helper._visitBinary     visitBitand     = Helper._visitBinary     visitBitor      = Helper._visitBinary     visitBitxor     = Helper._visitBinary     visitDiv        = Helper._visitBinary     visitFloorDiv   = Helper._visitBinary     visitLeftShift  = Helper._visitBinary     visitMod        = Helper._visitBinary     visitMul        = Helper._visitBinary     visitPower      = Helper._visitBinary     visitRightShift = Helper._visitBinary     visitSub        = Helper._visitBinary      # Unary operators.      visitInvert     = Helper._visitUnary     visitUnaryAdd   = Helper._visitUnary     visitUnarySub   = Helper._visitUnary      # Logical operators.      def visitAnd(self, node):         end_block = self.new_block()         temp_pos = self.reserve_temp()         temp = LoadTemp(temp_pos)          for n in node.nodes[:-1]:             self.dispatch(n)             self.new_op(StoreTemp(temp_pos))              self._generateTestBoolean(n, temp)             self.new_op(JumpIfFalse(end_block))          self.dispatch(node.nodes[-1])         self.new_op(StoreTemp(temp_pos))          self.set_block(end_block)          self.new_op(temp)         self.discard_temp(temp)      def visitNot(self, node):         self.dispatch(node.expr)          temp = self.optimiser.optimise_temp_storage()         self._generateTestBoolean(node.expr, temp)         self.discard_temp(temp)          self.new_op(InvertBoolean())         self._generateLoadBoolean(node)      def visitOr(self, node):         end_block = self.new_block()         temp_pos = self.reserve_temp()         temp = LoadTemp(temp_pos)          for n in node.nodes[:-1]:             self.dispatch(n)             self.new_op(StoreTemp(temp_pos))              self._generateTestBoolean(n, temp)             self.new_op(JumpIfTrue(end_block))          self.dispatch(node.nodes[-1])         self.new_op(StoreTemp(temp_pos))          self.set_block(end_block)          self.new_op(temp)         self.discard_temp(temp)      # Comparisons.      def visitCompare(self, node):          """         _t1 = node.expr         _t1 op1 _t2 and _t2 op2 _t3 and ...         """          end_block = self.new_block()          self.dispatch(node.expr)         temp2 = self.optimiser.optimise_temp_storage()          # NOTE: Replicated by some code in micropython.inspect.visitCompare.          last_op = node.ops[-1]          for op in node.ops:             op_name, next_node = op             methods = comparison_methods[op_name]              # Propagate the arguments as we traverse the construct.              temp1 = temp2             self.dispatch(next_node)             temp2 = self.optimiser.optimise_temp_storage()              # Use the appropriate mechanism, setting the boolean status for the             # comparison.              if methods is not None:                 left_method, right_method = methods                  # Generate method call using evaluated argument and next node.                  temp_result = self._generateBinary(node, temp1, temp2, left_method, right_method)                 self.new_op(temp_result)                 self._generateTestBoolean(node, temp_result)                 self.discard_temp(temp_result)              else:                 # Deal with the special operators.                  if op_name.startswith("is"):                     self.new_op(temp1)                     self.record_value()                     self.new_op(temp2)                     self.new_op(TestIdentity())                     self.set_source()                     self.discard_value()                  elif op_name.endswith("in"):                     self.new_op(temp2)                      # Get method on temp2.                      self._generateAttr(node, "__contains__", self.attribute_load_instructions)                     temp_method = self.optimiser.optimise_temp_storage()                      # Add arguments.                     # NOTE: No support for defaults.                      self._startCallFunc()                     self.new_op(temp2)                     self.new_op(StoreFrame(0))                     self.new_op(temp1)                     self.new_op(StoreFrame(1))                     self._endCallFuncArgs(2)                     self._doCallFunc(temp_method)                     self._endCallFunc(temp_method)                      temp_result = self.get_temp()                     self._generateTestBoolean(node, temp_result)                     self.discard_temp(temp_result)                  if op_name.find("not") != -1:                     self.new_op(InvertBoolean())              # Test the result and jump to the end block if false.              if op is not last_op:                 self.new_op(JumpIfFalse(end_block))              # Compilation duties...              self.discard_temp(temp1)          self.discard_temp(temp2)          # With the status set above, produce a boolean result.          self.set_block(end_block)          # Yield the appropriate value.          self._generateLoadBoolean(node)      # Expressions.      def visitBackquote(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "Backquote")      def visitCallFunc(self, node):          """         Evaluate positional arguments, evaluate and store keyword arguments in         the correct location, then invoke the function.         """          # Mark the frame, evaluate the target, generate the call.          self._startCallFunc()         self.dispatch(node.node)         temp_target, target, temp_context = self._generateCallFunc(node.args, node)         self._doCallFunc(temp_target, target)         self._endCallFunc(temp_target, target, temp_context)      def visitConst(self, node):         const = self.importer.get_constant(node.value)         self.new_op(LoadConst(const))      def visitDict(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "Dict")      def visitEllipsis(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "Ellipsis")      def visitExec(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "Exec")      def visitExpression(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "Expression")      def visitGenExpr(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "GenExpr")      def visitGenExprFor(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "GenExprFor")      def visitGenExprIf(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "GenExprIf")      def visitGenExprInner(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "GenExprInner")      def visitGetattr(self, node):         self._visitAttr(node, self.attribute_load_instructions)      def visitList(self, node):         self._generateSequence("list", node)      def visitListComp(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "ListComp")      def visitListCompFor(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "ListCompFor")      def visitListCompIf(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "ListCompIf")      def visitName(self, node):         if self.importer.predefined_constants.has_key(node.name):             const = self.importer.get_predefined_constant(node.name)             self.new_op(LoadConst(const))         else:             self._visitName(node, self.name_load_instructions)      def visitSlice(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "Slice")      def visitSubscript(self, node):         self.dispatch(node.expr)         self._startCallFunc()         self._generateAttr(node, "__getitem__", self.attribute_load_instructions)         temp_target, target, temp_context = self._generateCallFunc(node.subs, node)         self._doCallFunc(temp_target, target)         self._endCallFunc(temp_target, target, temp_context)      def visitTuple(self, node):         self._generateSequence("tuple", node)      # Definitions.      def visitAssign(self, node):          """         Evaluate the expression from the given 'node' and assign it to the         associated recipients.         """          self.dispatch(node.expr)          # Record the value and then dispatch to the assignment targets.          self.record_value(self.has_immediate_usage(node.nodes))          for n in node.nodes:             self.dispatch(n)          self.discard_value()      def visitAssAttr(self, node):          "Assign the assignment expression to the recipient 'node'."          self._visitAttr(node, self.attribute_store_instructions)         self.set_source()      def visitAssList(self, node):          """         Assign items from the assignment expression to each of the recipients         found within the given 'node'.         """          for i, n in enumerate(node.nodes):             self._startCallFunc()             self.new_op(self.expr_temp[-1])             self._generateAttr(node, "__getitem__", self.attribute_load_instructions)             temp_target, target, temp_context = self._generateCallFunc([compiler.ast.Const(i)], node)             self._doCallFunc(temp_target, target)             self._endCallFunc(temp_target, target, temp_context)              # Provide a different source value.             # NOTE: Permitting immediate usage given that neither name nor             # NOTE: attribute accesses should involve a function call             # NOTE: overwriting the above result.              self.record_value(self.is_immediate_user(n))             self.dispatch(n)             self.discard_value()      def visitAssName(self, node):          "Assign the assignment expression to the recipient 'node'."          self._visitName(node, self.name_store_instructions)         self.set_source()      visitAssTuple = visitAssList      def visitAugAssign(self, node):         use_binary_block = self.new_block()         end_block = self.new_block()          # Evaluate the expression.          self.dispatch(node.expr)         temp2 = self.optimiser.optimise_temp_storage()          # Evaluate the target.          self.dispatch(node.node)         temp1 = self.optimiser.optimise_temp_storage()          # Find the augmented assignment method and attempt to use it.          aug_method, (left_method, right_method) = augassign_methods[node.op]         temp_out = self._generateOpMethod(node, temp1, temp2, aug_method, use_binary_block, end_block)         self.discard_temp(temp_out) # NOTE: Will re-use the same storage.          # Where no such method exists, use the binary operator methods.          self.set_block(use_binary_block)         temp_out = self._generateBinary(node, temp1, temp2, left_method, right_method)          # Assign the result to the name.          self.set_block(end_block)         self.new_op(temp_out)         self.record_value(1)          if isinstance(node.node, compiler.ast.Name):             self.visitAssName(node.node)         elif isinstance(node.node, compiler.ast.Getattr):             self.visitAssAttr(node.node)         else:             raise TranslationNotImplementedError(self.module.full_name(), node, "AugAssign(Slice or Subscript)")          self.discard_value()          # Compilation duties...          self.discard_temp(temp1)         self.discard_temp(temp2)      def visitClass(self, node):         if not node.unit.referenced:             return          # Store the name.          self.new_op(LoadConst(node.unit))         self.record_value()         self._visitName(node, self.name_store_instructions)         self.set_source()         self.discard_value()          # Visit the code.          unit = self.unit         self.unit = node.unit         self.dispatch(node.code)         self.unit = unit      def visitDecorators(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "Decorators")      def visitFrom(self, node): pass      def visitFunction(self, node):         if not node.unit.referenced and (not node.unit.is_method() or not node.unit.parent.has_key(node.unit.name)):             return          # Only store the name when visiting this node from outside.          if self.unit is not node.unit:             self.new_op(LoadFunction(node.unit))             self.record_value()              self._visitName(node, self.name_store_instructions) # AssName equivalent             self.set_source()             self.discard_value()              self._generateFunctionDefaults(node.unit)          # Visiting of the code occurs when get_code is invoked on this node.          else:             # Check frames using the function's details.              fn = node.unit             nparams = len(fn.positional_names)             ndefaults = len(fn.defaults)              fn.body_block = self.new_block()              # Check the number of parameters and defaults.              self.new_op(CheckFrame((nparams, ndefaults, fn.has_star)))             if ndefaults > 0:                 self.new_op(LoadFunction(fn))                 self.new_op(FillDefaults((nparams, ndefaults)))              # Produce the body.              self.set_block(fn.body_block)              extend = ExtendFrame()             self.new_op(extend)              self.dispatch(node.code)              if not isinstance(self.last_op(), Return):                 self.dispatch(compiler.ast.Name("None"))                 self.new_op(StoreResult())                 self.new_op(Return())              # Make sure that enough frame space is reserved from the start.              self.set_frame_usage(node, extend)      def visitGlobal(self, node): pass      def visitImport(self, node): pass      def visitKeyword(self, node): pass      def visitLambda(self, node):          """         Lambda functions can be represented as globally defined functions         provided they do not define any default parameter values, since these         may defined in a non-global scope.          Where defaults are defined, an object must be created and its content         defined: the callable member of the object's structure must be set to         the lambda function definition; each default must be attached to the         object as an attribute, as is the case with normal functions and         methods.         """          # Produce the reference to this function when visiting this node from         # outside.          if self.unit is not node.unit:             fn = node.unit             ndefaults = len(fn.defaults)             temp = self._generateFunctionDefaults(fn)              if ndefaults > 0:                 self.new_op(LoadConst(fn))             else:                 self.new_op(LoadFunction(fn))              # Populate the new object required for the function.              if temp is not None:                 self.new_op(LoadCallable())                 self.new_op(temp)                 self.new_op(StoreCallable())                  self.new_op(temp)                 #self.discard_temp(temp)          # Visiting of the code occurs when get_code is invoked on this node.          else:             # Check frames using the function's details.              fn = node.unit             nparams = len(fn.positional_names)             ndefaults = len(fn.defaults)              fn.body_block = self.new_block()              # Check the number of parameters and defaults.              self.new_op(CheckFrame((nparams, ndefaults, fn.has_star)))             if ndefaults > 0:                 self.new_op(LoadTemp(0)) # context provides storage                 self.new_op(FillDefaults((nparams, ndefaults)))              # Produce the body.              self.set_block(fn.body_block)              extend = ExtendFrame()             self.new_op(extend)              self.dispatch(node.code)              self.new_op(StoreResult())             self.new_op(Return())              # Make sure that enough frame space is reserved from the start.              self.set_frame_usage(node, extend)      def visitModule(self, node):         extend = ExtendFrame()         self.new_op(extend)         self.dispatch(node.node)         self.set_frame_usage(node, extend)      # Statements.      def visitStmt(self, node):          "Process the collection of statements provided by 'node'."          for n in node.nodes:              # Process the statement.              self.dispatch(n)              # Discard temporary storage.              if self.temp_positions:                 #print "Had temp", self.temp_positions                 self.temp_positions = set()              # Prevent incorrect optimisation by resetting the optimiser after             # each statement.              self.optimiser.reset()      def visitAssert(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "Assert")      def visitBreak(self, node):         next_block, exit_block = self.get_loop_blocks()         self.new_op(Jump(exit_block))      def visitContinue(self, node):         next_block, exit_block = self.get_loop_blocks()         self.new_op(Jump(next_block))      def visitDiscard(self, node):         self.dispatch(node.expr)         self.optimiser.optimise_unused_results()      def visitFor(self, node):         next_handler_block = self.new_block()         end_handler_block = self.new_block()         exit_block = self.new_block()         next_block = self.new_block()         else_block = self.new_block()          # Get the "list" to be iterated over, obtain its iterator.          self._startCallFunc()         self.dispatch(node.list)         self._generateAttr(node, "__iter__", self.attribute_load_instructions)         temp_target, target, temp_context = self._generateCallFunc([], node)         self._doCallFunc(temp_target, target)         self._endCallFunc(temp_target, target, temp_context)          temp_iterator = self.optimiser.optimise_temp_storage()          # In the loop...          self.set_block(next_block)          # Handle exceptions when calling "next"...          self.new_op(PushHandler(next_handler_block))          # Use the iterator to get the next value.          self._startCallFunc()         self.new_op(temp_iterator)         self._generateAttr(node, "next", self.attribute_load_instructions)         temp_target, target, temp_context = self._generateCallFunc([], node)         self._doCallFunc(temp_target, target)         self._endCallFunc(temp_target, target, temp_context)          # Record the value to be assigned.          self.record_value()          # Skip the handler where the call was successful.          self.new_op(PopHandler())         self.new_op(Jump(end_handler_block))          # Enter the exception handler.          self.set_block(next_handler_block)         self.new_op(PopHandler())          # Test for StopIteration.          self.load_builtin("StopIteration", node)         self.new_op(CheckException())         if node.else_ is not None:             self.new_op(JumpIfTrue(else_block))         else:             self.new_op(JumpIfTrue(exit_block))          # Re-raise the exception otherwise.          self.new_op(RaiseException())          # After the handler, clear the exception.          self.set_block(end_handler_block)         self.new_op(ClearException())          # Assign to the target.          self.dispatch(node.assign)         self.discard_value()          # Process the body with the current next and exit points.          self.add_loop_blocks(next_block, exit_block)         self.dispatch(node.body)         self.drop_loop_blocks()          # Repeat the loop.          self.new_op(Jump(next_block))          # Produce the "else" section.          if node.else_ is not None:             self.set_block(exit_block)              self.dispatch(node.else_)          # After the loop...          self.set_block(exit_block)          # Compilation duties...          self.discard_temp(temp_iterator)      def visitIf(self, node):         first = 1         next_block = None         exit_block = self.new_block()          clauses = node.tests + [(None, node.else_)]          for clause in clauses:             test, body = clause             if body is None:                 break              if not first:                 self.new_op(Jump(exit_block)) # finish last body                 self.set_block(next_block)    # start next test                 next_block = None              if test is not None:                 self.dispatch(test)                  temp = self.optimiser.optimise_temp_storage()                 self._generateTestBoolean(node, temp)                  next_block = self.new_block()                 self.new_op(JumpIfFalse(next_block))              self.dispatch(body)             first = 0          if next_block is not None:             self.set_block(next_block)          self.set_block(exit_block)      def visitPass(self, node): pass      def visitPrint(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "Print")      def visitPrintnl(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "Printnl")      def visitRaise(self, node):         # NOTE: expr1 only => instance provided         self.dispatch(node.expr1)          if node.expr2 is not None:             temp = self.optimiser.optimise_temp_storage()              self.dispatch(node.expr2)             temp_arg = self.optimiser.optimise_temp_storage()              self._startCallFunc()             self.new_op(temp_arg)             self.new_op(StoreFrame(0))             self._endCallFuncArgs(1)             self._doCallFunc(temp)             self._endCallFunc(temp)              self.discard_temp(temp_arg)          self.new_op(StoreException())         self.new_op(RaiseException())      def visitReturn(self, node):         if node.value is not None:             self.dispatch(node.value)         else:             self.dispatch(compiler.ast.Name("None"))          self.new_op(StoreResult())          if self.in_exception_handler:             self.new_op(ClearException())          self.new_op(Return())      def visitTryExcept(self, node):         exit_block = self.new_block()         else_block = self.new_block()         handler_block = self.new_block()          self.add_exception_blocks(handler_block, exit_block)          # Try...         # Produce the code, then jump to the exit.          self.new_op(PushHandler(handler_block))         self.dispatch(node.body)         self.new_op(PopHandler())          if node.else_ is not None:             self.new_op(Jump(else_block))         else:             self.new_op(Jump(exit_block))          # Start of handlers.          self.set_block(handler_block)         self.new_op(PopHandler())          for name, assignment, handler in node.handlers:             next_block = self.new_block()              # Test the given exception against the current exception.              if name is not None:                 self.dispatch(name)                  self.new_op(CheckException())                 self.new_op(JumpIfFalse(next_block))                  # Handle assignment to exception variable.                  if assignment is not None:                     self.new_op(LoadException())                      # Record the value to be assigned.                      self.record_value()                     self.dispatch(assignment)                     self.discard_value()              # Produce the handler code, then jump to the exit.              self.in_exception_handler = 1             self.dispatch(handler)             self.in_exception_handler = 0              self.new_op(Jump(exit_block))              self.set_block(next_block)          # Unhandled exceptions.          self.new_op(RaiseException())          # Optional else clause.          if node.else_ is not None:             self.set_block(else_block)             self.dispatch(node.else_)          # Clear the exception.          self.set_block(exit_block)         self.new_op(ClearException())         self.drop_exception_blocks()      def visitTryFinally(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "TryFinally")      def visitWhile(self, node):         exit_block = self.new_block()         next_block = self.new_block()         else_block = self.new_block()          self.set_block(next_block)         self.dispatch(node.test)         if node.else_ is not None:             self.new_op(JumpIfFalse(else_block))         else:             self.new_op(JumpIfFalse(exit_block))          self.add_loop_blocks(next_block, exit_block)          self.dispatch(node.body)         self.new_op(Jump(next_block))          if node.else_ is not None:             self.set_block(else_block)              self.dispatch(node.else_)          self.set_block(exit_block)          self.drop_loop_blocks()      def visitWith(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "With")      def visitYield(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "Yield")  # vim: tabstop=4 expandtab shiftwidth=4