#!/usr/bin/env python  """ Simplified program nodes for easier type propagation and analysis. This module contains nodes representing program instructions or operations, program structure or organisation, and abstract program data.  Copyright (C) 2006, 2007 Paul Boddie <paul@boddie.org.uk>  This software 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 2 of the License, or (at your option) any later version.  This software 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 library; see the file LICENCE.txt If not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA """  from compiler.visitor import ASTVisitor import sys  # Exceptions.  class SimplifiedError(Exception):      "An error in the annotation process."      def __init__(self, exc, node, *args):          """         Initialise the error with an existing exception 'exc', the 'node' at         which this error occurs, along with additional optional arguments.         """          Exception.__init__(self, *args)         self.nodes = [node]         self.exc = exc      def add(self, node):          "Add the given 'node' to the path of nodes leading from the exception."          self.nodes.append(node)      def __str__(self):          "Return a string showing the principal exception details."          return "%s, %s" % (self.exc, self.nodes)  # Unique name registration.  class Naming:      "Maintain records of unique names for each simple name."      index_separator = "-"      def __init__(self):         self.obj_to_name = {}         self.names = {}      def get(self, obj):         return self.obj_to_name[obj]      def set(self, obj, name):         if self.obj_to_name.has_key(obj):             return         if not self.names.has_key(name):             self.names[name] = 0         n = self.names[name] + 1         self.names[name] = n         self.obj_to_name[obj] = "%s%s%d" % (name, self.index_separator, n)  naming = Naming()  def name(obj, name):      "Return a unique name for the given 'obj', indicating the base 'name'."      naming.set(obj, name)     return naming.get(obj)  # Elementary visitor support.  class Visitor(ASTVisitor):      "A visitor base class."      def __init__(self):         ASTVisitor.__init__(self)      def default(self, node, *args):         raise ValueError, node.__class__      def dispatch(self, node, *args):         return ASTVisitor.dispatch(self, node, *args)      def dispatches(self, nodes, *args):         results = []         for node in nodes:             results.append(self.dispatch(node, *args))         return results      def dispatch_dict(self, d, *args):         results = {}         for name, node in d.items():             results[name] = self.dispatch(node, *args)         return results  # Simplified program nodes.  class Node:      """     A result node with common attributes:      original    The original node from which this node was created.     defining    Whether the node defines something in the original program.     name        Any name involved (variable or attribute).     index       Any index involved (temporary variable name).     value       Any constant value.     ref         Any reference to (for example) subprograms.     nstype      Any indication of the namespace type involved in a name access.      Expression-related attributes:      expr        Any contributing expression.     lvalue      Any target expression.     test        Any test expression in a conditional instruction.      Invocation and subprogram attributes:      args        Any collection of argument nodes.     params      Any collection of parameter nodes and defaults.      Statement-grouping attributes:      body        Any conditional code depending on the success of a test.     else_       Any conditional code depending on the failure of a test.     handler     Any exception handler code.     finally_    Any code which will be executed regardless.     code        Any unconditional code.     choices     Any choices which may be included in the final program.     """      common_attributes = "name", "index", "value", "nstype", "internal", "returns_value", "is_method", "ref", "module", "structures", "original_def"     expression_attributes = "expr", "lvalue", "test", "star", "dstar"     invocation_attributes = "params", # not "args" - see "pos_args", "kw_args"     grouping_attributes = "code", "body", "else_", "handler", "finally_", "choices"      def __init__(self, original=None, defining=0, **kw):          """         Initialise a program node with a link to an optional 'original' AST         node. An optional 'defining' parameter (if set to a true value), sets         this node as the defining node in the original.         """          self.original = original         self.defining = defining          if self.original is not None and defining:             self.original._node = self         for name, value in kw.items():             setattr(self, name, value)      def __repr__(self):          "Return a readable representation."          if hasattr(self, "full_name"):             s = "%s '%s'" % (self.__class__.__name__, self.full_name())         elif hasattr(self, "name"):             s = "%s '%s'" % (self.__class__.__name__, self.name)         elif hasattr(self, "index"):             s = "%s (%s)" % (self.__class__.__name__, self.index)         elif hasattr(self, "value"):             s = "%s %s" % (self.__class__.__name__, repr(self.value))         elif hasattr(self, "ref"):             s = "%s '%s'" % (self.__class__.__name__, name(self.ref, self.ref.name))         else:             s = "%s" % (self.__class__.__name__,)          # Annotations.          if hasattr(self, "types"):             return "%s -> %s" % (s, self.types)         else:             return s      def _pprint(self, indent, continuation, s, stream=None):          """         Print, at the given 'indent' level, with the given 'continuation' text,         the string 's', either to the given, optional 'stream' or to standard         output, this node's "pretty" representation.         """          stream = stream or sys.stdout         if continuation:             print >>stream, (" " * max(0, indent - len(continuation))) + continuation + s         else:             print >>stream, (" " * indent) + s      def pprint(self, indent=0, continuation=None, stream=None):          """         Print, at the given, optional 'indent', with the given optional         'continuation' text, either to the given, optional 'stream' or to         standard output, this node's "pretty" representation along with its         children and their "pretty" representation (and so on).         """          stream = stream or sys.stdout         self._pprint(indent, continuation, repr(self), stream)          # Subprogram-related details.          if hasattr(self, "params"):             for name, default in self.params:                 self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream)             if hasattr(self, "star") and self.star:                 name, default = self.star                 self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream)             if hasattr(self, "dstar") and self.dstar:                 name, default = self.dstar                 self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream)         if getattr(self, "internal", 0):             self._pprint(indent + 2, "( ", "internal", stream=stream)         if getattr(self, "structure", 0):             self._pprint(indent + 2, "( ", "structure '%s'" % self.structure.name, stream=stream)          # Expression-related details.          if hasattr(self, "expr"):             self.expr.pprint(indent + 2, "- ", stream=stream)         if hasattr(self, "nodes"):             for node in self.nodes:                 node.pprint(indent + 2, "- ", stream=stream)         if hasattr(self, "lvalue"):             self.lvalue.pprint(indent + 2, "->", stream=stream)         if hasattr(self, "nstype"):             self._pprint(indent + 2, "", self.nstype, stream=stream)         if hasattr(self, "args"):             for arg in self.pos_args:                 arg.pprint(indent + 2, "( ", stream=stream)             for name, arg in self.kw_args.items():                 arg.pprint(indent + 2, "( ", stream=stream)             if hasattr(self, "star") and self.star:                 self.star.pprint(indent + 2, "( ", stream=stream)             if hasattr(self, "dstar") and self.dstar:                 self.dstar.pprint(indent + 2, "( ", stream=stream)          # Statement-related details.          if hasattr(self, "test"):             self.test.pprint(indent + 2, "? ", stream=stream)         for attr in self.grouping_attributes:             if hasattr(self, attr) and getattr(self, attr):                 self._pprint(indent, "", "%s {" % attr, stream=stream)                 for node in getattr(self, attr):                     node.pprint(indent + 2, stream=stream)                 self._pprint(indent, "", "}", stream=stream)          # Annotations.          if hasattr(self, "accesses"):             self._pprint(indent, "", "--------", stream=stream)             for ref, attributes in self.accesses.items():                 self._pprint(indent + 2, "| ", "when %s: %s" % (ref, ", ".join([("%s via %s" % attr_acc) for attr_acc in attributes])), stream=stream)             self._pprint(indent, "", "--------", stream=stream)         if hasattr(self, "writes"):             self._pprint(indent, "", "--------", stream=stream)             for ref, attribute in self.writes.items():                 self._pprint(indent + 2, "| ", "when %s: %s" % (ref, attribute), stream=stream)             self._pprint(indent, "", "--------", stream=stream)      # Node manipulation functions.      def copy(self, new_name=None, original_def=None):          """         Perform a deep copy of the node, optionally specifying a 'new_name',         returning a new unannotated copy.          The 'original_def' parameter is used to assign a particular AST node to         copied regions of the simplified node tree.         """          # Obtain an AST node to be assigned to the copied nodes.          original_def = getattr(self, "original", None) or original_def or getattr(self, "original_def", None)          # Copy the common attributes of this node.          common = {}         for attr in self.common_attributes:             if hasattr(self, attr):                 common[attr] = getattr(self, attr)          if new_name is not None:             common["name"] = new_name          if original_def is not None:             common["original_def"] = original_def          # Instantiate the copy, avoiding side-effects with original and defining.          node = self.__class__(**common)         node.original = self.original         node.defining = self.defining          # Add links to copied nodes from original AST nodes.          if node.original is not None:             if not hasattr(node.original, "_nodes"):                 node.original._nodes = []             node.original._nodes.append(node)          # Copy attributes of different types.          for attr in self.expression_attributes:             if hasattr(self, attr):                 n = getattr(self, attr)                 if n is None:                     n2 = n                 else:                     n2 = n.copy(original_def=original_def)                 setattr(node, attr, n2)          for attr in self.invocation_attributes:             if hasattr(self, attr):                 l = getattr(self, attr)                 l2 = []                 for name, n in l:                     if n is None:                         l2.append((name, n))                     else:                         l2.append((name, n.copy(original_def=original_def)))                 setattr(node, attr, l2)          for attr in self.grouping_attributes:             if hasattr(self, attr):                 l = getattr(self, attr)                 setattr(node, attr, [n.copy(original_def=original_def) for n in l])          # Arguments are usually processed further - "args" is useless.          if hasattr(self, "pos_args"):             node.pos_args = [n.copy(original_def=original_def) for n in self.pos_args]          if hasattr(self, "kw_args"):             node.kw_args = {}             for name, n in self.kw_args.items():                 node.kw_args[name] = n.copy(original_def=original_def)          return node  # These are the supported "operations" described by simplified program nodes.  class Pass(Node): "A placeholder node corresponding to pass." class Assign(Node): "A grouping node for assignment-related operations." class Keyword(Node): "A grouping node for keyword arguments." class Global(Node): "A global name designator." class Import(Node): "A module import operation." class LoadTemp(Node): "Load a previously-stored temporary value." class LoadName(Node): "Load a named object." class LoadAttr(Node): "Load an object attribute." class LoadRef(Node): "Load a reference, typically a subprogram or a constant." class LoadExc(Node): "Load a handled exception." class CheckExc(Node): "Check a handled exception." class StoreTemp(Node): "Store a temporary value." class StoreName(Node): "Associate a name with an object." class StoreAttr(Node): "Associate an object's attribute with a value." class ReleaseTemp(Node): "Release a temporary value." class Try(Node): "A try...except...else...finally grouping node." class Raise(Node): "An exception raising node." class Not(Node): "A negation of an expression."  # There are two types of return node: return from function and return from # block.  class Return(Node):      "Return an evaluated expression."      pass  class ReturnFromFunction(Return):     pass  class ReturnFromBlock(Return):     pass  # Some behaviour is set as the default in conditional nodes but may be # overridden.  class Conditional(Node):      "A conditional node consisting of a test and outcomes."      def __init__(self, *args, **kw):         self.isolate_test = 0         Node.__init__(self, *args, **kw)  # Invocations involve some more work to process calculated attributes.  class Invoke(Node):      "An invocation."      pass  class InvokeFunction(Invoke):      "A function or method invocation."      def __init__(self, *args, **kw):         self.args = []         self.star = None         self.dstar = None         Invoke.__init__(self, *args, **kw)         self.set_args(self.args)         self.share_locals = 0      def set_args(self, args):          "Sort the 'args' into positional and keyword arguments."          self.pos_args = []         self.kw_args = {}         add_kw = 0         for arg in args:             if not add_kw:                 if not isinstance(arg, Keyword):                     self.pos_args.append(arg)                 else:                     add_kw = 1             if add_kw:                 if isinstance(arg, Keyword):                     self.kw_args[arg.name] = arg.expr                 else:                     raise TypeError, "Positional argument appears after keyword arguments in '%s'." % self  class InvokeBlock(Invoke):      "A block or loop invocation."      def __init__(self, *args, **kw):         self.share_locals = 1         Invoke.__init__(self, *args, **kw)  # Named nodes are those which can be referenced in some way.  class WithName:      "Node naming."      def __init__(self):         self._full_name = name(self, self.name or "$untitled")      def full_name(self):         return self._full_name  # Program structure nodes.  class Module(Node):      "A Python module."      def full_name(self):         return "module %s" % self.name  class Subprogram(Node, WithName):      "A subprogram: functions, methods and loops."      def __init__(self, *args, **kw):         Node.__init__(self, *args, **kw)         WithName.__init__(self)  # Special non-program nodes.  class Structure(Node): "A non-program node containing some kind of namespace."  class _Class(Structure, WithName):      "A Python class."      def __init__(self, *args, **kw):         Structure.__init__(self, *args, **kw)         WithName.__init__(self)      def full_name(self):         return "class %s" % self._full_name  class SingleInstanceClass(_Class):      "A Python class."      def __init__(self, *args, **kw):         _Class.__init__(self, *args, **kw)         self.instance = None      def has_instance(self, node):         return self.instance is not None      def add_instance(self, node, instance):         self.instance = instance      def get_instance(self, node):         return self.instance      def get_instance_name(self, instance):         return self._full_name      # Attribute propagation.      def get_attribute_for_instance(self, attribute, instance):         return attribute  class MultipleInstanceClass(_Class):      "A Python class."      def __init__(self, *args, **kw):         _Class.__init__(self, *args, **kw)         self.instances = {}         self.attributes_for_instances = {}      def _get_key(self, node):         return getattr(node, "original_def", node)      def has_instance(self, node):         return self.instances.has_key(self._get_key(node))      def add_instance(self, node, instance):         self.instances[self._get_key(node)] = instance      def get_instance(self, node):         return self.instances[self._get_key(node)]      def get_instance_name(self, instance):         return name(instance, self._full_name)      # Attribute propagation.      def get_attribute_for_instance(self, attribute, instance):         if isinstance(attribute.type, Subprogram):             subprogram = attribute.type             key = (subprogram, instance)             if not self.attributes_for_instances.has_key(key):                 self.attributes_for_instances[key] = Attribute(attribute.context, subprogram.copy(subprogram.full_name()))             return self.attributes_for_instances[key]         else:             return attribute  class Instance(Structure):      "An instance."      def full_name(self):         return self.get_class().get_instance_name(self)      def get_class(self):         return self.namespace.load("__class__")[0].type      def __repr__(self):         return "Instance of type '%s'" % self.full_name()      def __eq__(self, other):         # NOTE: Single instance: all instances are the same         # NOTE: Multiple instances: all instances are different         return self.full_name() == other.full_name()      def __hash__(self):         return id(self)  class Constant(Instance):      "A constant initialised with a type name for future processing."      def __init__(self, *args, **kw):         Instance.__init__(self, *args, **kw)         self.typename = self.value.__class__.__name__  class Attribute:      """     An attribute abstraction, indicating the type of the attribute along with     its context or origin.     """      def __init__(self, context, type):         self.context = context         self.type = type      def __eq__(self, other):         return hasattr(other, "type") and other.type == self.type or other == self.type      def __repr__(self):         return "Attribute(%s, %s)" % (repr(self.context), repr(self.type))  class Self:      """     A program node encapsulating object/context information in an argument list.     This is not particularly like Attribute, Class, Instance or other such     things, since it actually appears in the program representation.     """      def __init__(self, attribute):         self.types = [attribute]  # Configuration setting.  Class = SingleInstanceClass #Class = MultipleInstanceClass  def set_single_instance_mode():     global Class     Class = SingleInstanceClass  def set_multiple_instance_mode():     global Class     Class = MultipleInstanceClass  # vim: tabstop=4 expandtab shiftwidth=4