simplify

simplified.py

178:81c7b9708818
2007-01-22 paulb Added node copying, used when accessing class attributes for instances where such attributes refer to subprograms (ie. methods); added the acquisition of such copied method attributes in the get_attributes function. Added the original_def attribute for certain kinds of subprograms (functions, lambda expressions) which is used to "paint" copied sections of the simplified node tree with an AST node which can help identify distinct sites for object instantiation. Moved the Self and Attribute classes to the simplified module.
     1 #!/usr/bin/env python     2      3 """     4 Simplified program nodes for easier type propagation and analysis. This module     5 contains nodes representing program instructions or operations, program     6 structure or organisation, and abstract program data.     7      8 Copyright (C) 2006, 2007 Paul Boddie <paul@boddie.org.uk>     9     10 This software is free software; you can redistribute it and/or    11 modify it under the terms of the GNU General Public License as    12 published by the Free Software Foundation; either version 2 of    13 the License, or (at your option) any later version.    14     15 This software is distributed in the hope that it will be useful,    16 but WITHOUT ANY WARRANTY; without even the implied warranty of    17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the    18 GNU General Public License for more details.    19     20 You should have received a copy of the GNU General Public    21 License along with this library; see the file LICENCE.txt    22 If not, write to the Free Software Foundation, Inc.,    23 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA    24 """    25     26 from compiler.visitor import ASTVisitor    27 import sys    28     29 # Exceptions.    30     31 class SimplifiedError(Exception):    32     33     "An error in the annotation process."    34     35     def __init__(self, exc, node, *args):    36     37         """    38         Initialise the error with an existing exception 'exc', the 'node' at    39         which this error occurs, along with additional optional arguments.    40         """    41     42         Exception.__init__(self, *args)    43         self.nodes = [node]    44         self.exc = exc    45     46     def add(self, node):    47     48         "Add the given 'node' to the path of nodes leading from the exception."    49     50         self.nodes.append(node)    51     52     def __str__(self):    53     54         "Return a string showing the principal exception details."    55     56         return "%s, %s" % (self.exc, self.nodes)    57     58 # Unique name registration.    59     60 class Naming:    61     62     "Maintain records of unique names for each simple name."    63     64     index_separator = "-"    65     66     def __init__(self):    67         self.obj_to_name = {}    68         self.names = {}    69     70     def get(self, obj):    71         return self.obj_to_name[obj]    72     73     def set(self, obj, name):    74         if self.obj_to_name.has_key(obj):    75             return    76         if not self.names.has_key(name):    77             self.names[name] = 0    78         n = self.names[name] + 1    79         self.names[name] = n    80         self.obj_to_name[obj] = "%s%s%d" % (name, self.index_separator, n)    81     82 naming = Naming()    83     84 def name(obj, name):    85     86     "Return a unique name for the given 'obj', indicating the base 'name'."    87     88     naming.set(obj, name)    89     return naming.get(obj)    90     91 # Elementary visitor support.    92     93 class Visitor(ASTVisitor):    94     95     "A visitor base class."    96     97     def __init__(self):    98         ASTVisitor.__init__(self)    99    100     def default(self, node, *args):   101         raise ValueError, node.__class__   102    103     def dispatch(self, node, *args):   104         return ASTVisitor.dispatch(self, node, *args)   105    106     def dispatches(self, nodes, *args):   107         results = []   108         for node in nodes:   109             results.append(self.dispatch(node, *args))   110         return results   111    112     def dispatch_dict(self, d, *args):   113         results = {}   114         for name, node in d.items():   115             results[name] = self.dispatch(node, *args)   116         return results   117    118 # Simplified program nodes.   119    120 class Node:   121    122     """   123     A result node with common attributes:   124    125     original    The original node from which this node was created.   126     defining    Whether the node defines something in the original program.   127     name        Any name involved (variable or attribute).   128     index       Any index involved (temporary variable name).   129     value       Any constant value.   130     ref         Any reference to (for example) subprograms.   131     nstype      Any indication of the namespace type involved in a name access.   132    133     Expression-related attributes:   134    135     expr        Any contributing expression.   136     lvalue      Any target expression.   137     test        Any test expression in a conditional instruction.   138    139     Invocation and subprogram attributes:   140    141     args        Any collection of argument nodes.   142     params      Any collection of parameter nodes and defaults.   143    144     Statement-grouping attributes:   145    146     body        Any conditional code depending on the success of a test.   147     else_       Any conditional code depending on the failure of a test.   148     handler     Any exception handler code.   149     finally_    Any code which will be executed regardless.   150     code        Any unconditional code.   151     choices     Any choices which may be included in the final program.   152     """   153    154     common_attributes = "name", "index", "value", "nstype", "internal", "returns_value", "is_method", "ref", "module", "structures", "original_def"   155     expression_attributes = "expr", "lvalue", "test", "star", "dstar"   156     invocation_attributes = "params", # not "args" - see "pos_args", "kw_args"   157     grouping_attributes = "code", "body", "else_", "handler", "finally_", "choices"   158    159     def __init__(self, original=None, defining=0, **kw):   160    161         """   162         Initialise a program node with a link to an optional 'original' AST   163         node. An optional 'defining' parameter (if set to a true value), sets   164         this node as the defining node in the original.   165         """   166    167         self.original = original   168         self.defining = defining   169    170         if self.original is not None and defining:   171             self.original._node = self   172         for name, value in kw.items():   173             setattr(self, name, value)   174    175     def __repr__(self):   176    177         "Return a readable representation."   178    179         if hasattr(self, "full_name"):   180             s = "%s '%s'" % (self.__class__.__name__, self.full_name())   181         elif hasattr(self, "name"):   182             s = "%s '%s'" % (self.__class__.__name__, self.name)   183         elif hasattr(self, "index"):   184             s = "%s (%s)" % (self.__class__.__name__, self.index)   185         elif hasattr(self, "value"):   186             s = "%s %s" % (self.__class__.__name__, repr(self.value))   187         elif hasattr(self, "ref"):   188             s = "%s '%s'" % (self.__class__.__name__, name(self.ref, self.ref.name))   189         else:   190             s = "%s" % (self.__class__.__name__,)   191    192         # Annotations.   193    194         if hasattr(self, "types"):   195             return "%s -> %s" % (s, self.types)   196         else:   197             return s   198    199     def _pprint(self, indent, continuation, s, stream=None):   200    201         """   202         Print, at the given 'indent' level, with the given 'continuation' text,   203         the string 's', either to the given, optional 'stream' or to standard   204         output, this node's "pretty" representation.   205         """   206    207         stream = stream or sys.stdout   208         if continuation:   209             print >>stream, (" " * max(0, indent - len(continuation))) + continuation + s   210         else:   211             print >>stream, (" " * indent) + s   212    213     def pprint(self, indent=0, continuation=None, stream=None):   214    215         """   216         Print, at the given, optional 'indent', with the given optional   217         'continuation' text, either to the given, optional 'stream' or to   218         standard output, this node's "pretty" representation along with its   219         children and their "pretty" representation (and so on).   220         """   221    222         stream = stream or sys.stdout   223         self._pprint(indent, continuation, repr(self), stream)   224    225         # Subprogram-related details.   226    227         if hasattr(self, "params"):   228             for name, default in self.params:   229                 self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream)   230             if hasattr(self, "star") and self.star:   231                 name, default = self.star   232                 self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream)   233             if hasattr(self, "dstar") and self.dstar:   234                 name, default = self.dstar   235                 self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream)   236         if getattr(self, "internal", 0):   237             self._pprint(indent + 2, "( ", "internal", stream=stream)   238         if getattr(self, "structure", 0):   239             self._pprint(indent + 2, "( ", "structure '%s'" % self.structure.name, stream=stream)   240    241         # Expression-related details.   242    243         if hasattr(self, "expr"):   244             self.expr.pprint(indent + 2, "- ", stream=stream)   245         if hasattr(self, "nodes"):   246             for node in self.nodes:   247                 node.pprint(indent + 2, "- ", stream=stream)   248         if hasattr(self, "lvalue"):   249             self.lvalue.pprint(indent + 2, "->", stream=stream)   250         if hasattr(self, "nstype"):   251             self._pprint(indent + 2, "", self.nstype, stream=stream)   252         if hasattr(self, "args"):   253             for arg in self.pos_args:   254                 arg.pprint(indent + 2, "( ", stream=stream)   255             for name, arg in self.kw_args.items():   256                 arg.pprint(indent + 2, "( ", stream=stream)   257             if hasattr(self, "star") and self.star:   258                 self.star.pprint(indent + 2, "( ", stream=stream)   259             if hasattr(self, "dstar") and self.dstar:   260                 self.dstar.pprint(indent + 2, "( ", stream=stream)   261    262         # Statement-related details.   263    264         if hasattr(self, "test"):   265             self.test.pprint(indent + 2, "? ", stream=stream)   266         for attr in self.grouping_attributes:   267             if hasattr(self, attr) and getattr(self, attr):   268                 self._pprint(indent, "", "%s {" % attr, stream=stream)   269                 for node in getattr(self, attr):   270                     node.pprint(indent + 2, stream=stream)   271                 self._pprint(indent, "", "}", stream=stream)   272    273         # Annotations.   274    275         if hasattr(self, "accesses"):   276             self._pprint(indent, "", "--------", stream=stream)   277             for ref, attributes in self.accesses.items():   278                 self._pprint(indent + 2, "| ", "when %s: %s" % (ref, ", ".join([("%s via %s" % attr_acc) for attr_acc in attributes])), stream=stream)   279             self._pprint(indent, "", "--------", stream=stream)   280         if hasattr(self, "writes"):   281             self._pprint(indent, "", "--------", stream=stream)   282             for ref, attribute in self.writes.items():   283                 self._pprint(indent + 2, "| ", "when %s: %s" % (ref, attribute), stream=stream)   284             self._pprint(indent, "", "--------", stream=stream)   285    286     # Node manipulation functions.   287    288     def copy(self, new_name=None, original_def=None):   289    290         """   291         Perform a deep copy of the node, optionally specifying a 'new_name',   292         returning a new unannotated copy.   293    294         The 'original_def' parameter is used to assign a particular AST node to   295         copied regions of the simplified node tree.   296         """   297    298         # Obtain an AST node to be assigned to the copied nodes.   299    300         original_def = getattr(self, "original", None) or original_def or getattr(self, "original_def", None)   301    302         # Copy the common attributes of this node.   303    304         common = {}   305         for attr in self.common_attributes:   306             if hasattr(self, attr):   307                 common[attr] = getattr(self, attr)   308    309         if new_name is not None:   310             common["name"] = new_name   311    312         if original_def is not None:   313             common["original_def"] = original_def   314    315         # Instantiate the copy, avoiding side-effects with original and defining.   316    317         node = self.__class__(**common)   318         node.original = self.original   319         node.defining = self.defining   320    321         # Add links to copied nodes from original AST nodes.   322    323         if node.original is not None:   324             if not hasattr(node.original, "_nodes"):   325                 node.original._nodes = []   326             node.original._nodes.append(node)   327    328         # Copy attributes of different types.   329    330         for attr in self.expression_attributes:   331             if hasattr(self, attr):   332                 n = getattr(self, attr)   333                 if n is None:   334                     n2 = n   335                 else:   336                     n2 = n.copy(original_def=original_def)   337                 setattr(node, attr, n2)   338    339         for attr in self.invocation_attributes:   340             if hasattr(self, attr):   341                 l = getattr(self, attr)   342                 l2 = []   343                 for name, n in l:   344                     if n is None:   345                         l2.append((name, n))   346                     else:   347                         l2.append((name, n.copy(original_def=original_def)))   348                 setattr(node, attr, l2)   349    350         for attr in self.grouping_attributes:   351             if hasattr(self, attr):   352                 l = getattr(self, attr)   353                 setattr(node, attr, [n.copy(original_def=original_def) for n in l])   354    355         # Arguments are usually processed further - "args" is useless.   356    357         if hasattr(self, "pos_args"):   358             node.pos_args = [n.copy(original_def=original_def) for n in self.pos_args]   359    360         if hasattr(self, "kw_args"):   361             node.kw_args = {}   362             for name, n in self.kw_args.items():   363                 node.kw_args[name] = n.copy(original_def=original_def)   364    365         return node   366    367 # These are the supported "operations" described by simplified program nodes.   368    369 class Pass(Node): "A placeholder node corresponding to pass."   370 class Assign(Node): "A grouping node for assignment-related operations."   371 class Keyword(Node): "A grouping node for keyword arguments."   372 class Global(Node): "A global name designator."   373 class Import(Node): "A module import operation."   374 class LoadTemp(Node): "Load a previously-stored temporary value."   375 class LoadName(Node): "Load a named object."   376 class LoadAttr(Node): "Load an object attribute."   377 class LoadRef(Node): "Load a reference, typically a subprogram or a constant."   378 class LoadExc(Node): "Load a handled exception."   379 class CheckExc(Node): "Check a handled exception."   380 class StoreTemp(Node): "Store a temporary value."   381 class StoreName(Node): "Associate a name with an object."   382 class StoreAttr(Node): "Associate an object's attribute with a value."   383 class ReleaseTemp(Node): "Release a temporary value."   384 class Try(Node): "A try...except...else...finally grouping node."   385 class Raise(Node): "An exception raising node."   386 class Not(Node): "A negation of an expression."   387    388 # There are two types of return node: return from function and return from   389 # block.   390    391 class Return(Node):   392    393     "Return an evaluated expression."   394    395     pass   396    397 class ReturnFromFunction(Return):   398     pass   399    400 class ReturnFromBlock(Return):   401     pass   402    403 # Some behaviour is set as the default in conditional nodes but may be   404 # overridden.   405    406 class Conditional(Node):   407    408     "A conditional node consisting of a test and outcomes."   409    410     def __init__(self, *args, **kw):   411         self.isolate_test = 0   412         Node.__init__(self, *args, **kw)   413    414 # Invocations involve some more work to process calculated attributes.   415    416 class Invoke(Node):   417    418     "An invocation."   419    420     pass   421    422 class InvokeFunction(Invoke):   423    424     "A function or method invocation."   425    426     def __init__(self, *args, **kw):   427         self.args = []   428         self.star = None   429         self.dstar = None   430         Invoke.__init__(self, *args, **kw)   431         self.set_args(self.args)   432         self.share_locals = 0   433    434     def set_args(self, args):   435    436         "Sort the 'args' into positional and keyword arguments."   437    438         self.pos_args = []   439         self.kw_args = {}   440         add_kw = 0   441         for arg in args:   442             if not add_kw:   443                 if not isinstance(arg, Keyword):   444                     self.pos_args.append(arg)   445                 else:   446                     add_kw = 1   447             if add_kw:   448                 if isinstance(arg, Keyword):   449                     self.kw_args[arg.name] = arg.expr   450                 else:   451                     raise TypeError, "Positional argument appears after keyword arguments in '%s'." % self   452    453 class InvokeBlock(Invoke):   454    455     "A block or loop invocation."   456    457     def __init__(self, *args, **kw):   458         self.share_locals = 1   459         Invoke.__init__(self, *args, **kw)   460    461 # Named nodes are those which can be referenced in some way.   462    463 class WithName:   464    465     "Node naming."   466    467     def __init__(self):   468         self._full_name = name(self, self.name or "$untitled")   469    470     def full_name(self):   471         return self._full_name   472    473 # Program structure nodes.   474    475 class Module(Node):   476    477     "A Python module."   478    479     def full_name(self):   480         return "module %s" % self.name   481    482 class Subprogram(Node, WithName):   483    484     "A subprogram: functions, methods and loops."   485    486     def __init__(self, *args, **kw):   487         Node.__init__(self, *args, **kw)   488         WithName.__init__(self)   489    490 # Special non-program nodes.   491    492 class Structure(Node): "A non-program node containing some kind of namespace."   493    494 class _Class(Structure, WithName):   495    496     "A Python class."   497    498     def __init__(self, *args, **kw):   499         Structure.__init__(self, *args, **kw)   500         WithName.__init__(self)   501    502     def full_name(self):   503         return "class %s" % self._full_name   504    505 class SingleInstanceClass(_Class):   506    507     "A Python class."   508    509     def __init__(self, *args, **kw):   510         _Class.__init__(self, *args, **kw)   511         self.instance = None   512    513     def has_instance(self, node):   514         return self.instance is not None   515    516     def add_instance(self, node, instance):   517         self.instance = instance   518    519     def get_instance(self, node):   520         return self.instance   521    522     def get_instance_name(self, instance):   523         return self._full_name   524    525     # Attribute propagation.   526    527     def get_attribute_for_instance(self, attribute, instance):   528         return attribute   529    530 class MultipleInstanceClass(_Class):   531    532     "A Python class."   533    534     def __init__(self, *args, **kw):   535         _Class.__init__(self, *args, **kw)   536         self.instances = {}   537         self.attributes_for_instances = {}   538    539     def _get_key(self, node):   540         return getattr(node, "original_def", node)   541    542     def has_instance(self, node):   543         return self.instances.has_key(self._get_key(node))   544    545     def add_instance(self, node, instance):   546         self.instances[self._get_key(node)] = instance   547    548     def get_instance(self, node):   549         return self.instances[self._get_key(node)]   550    551     def get_instance_name(self, instance):   552         return name(instance, self._full_name)   553    554     # Attribute propagation.   555    556     def get_attribute_for_instance(self, attribute, instance):   557         if isinstance(attribute.type, Subprogram):   558             subprogram = attribute.type   559             key = (subprogram, instance)   560             if not self.attributes_for_instances.has_key(key):   561                 self.attributes_for_instances[key] = Attribute(attribute.context, subprogram.copy(subprogram.full_name()))   562             return self.attributes_for_instances[key]   563         else:   564             return attribute   565    566 class Instance(Structure):   567    568     "An instance."   569    570     def full_name(self):   571         return self.get_class().get_instance_name(self)   572    573     def get_class(self):   574         return self.namespace.load("__class__")[0].type   575    576     def __repr__(self):   577         return "Instance of type '%s'" % self.full_name()   578    579     def __eq__(self, other):   580         # NOTE: Single instance: all instances are the same   581         # NOTE: Multiple instances: all instances are different   582         return self.full_name() == other.full_name()   583    584     def __hash__(self):   585         return id(self)   586    587 class Constant(Instance):   588    589     "A constant initialised with a type name for future processing."   590    591     def __init__(self, *args, **kw):   592         Instance.__init__(self, *args, **kw)   593         self.typename = self.value.__class__.__name__   594    595 class Attribute:   596    597     """   598     An attribute abstraction, indicating the type of the attribute along with   599     its context or origin.   600     """   601    602     def __init__(self, context, type):   603         self.context = context   604         self.type = type   605    606     def __eq__(self, other):   607         return hasattr(other, "type") and other.type == self.type or other == self.type   608    609     def __repr__(self):   610         return "Attribute(%s, %s)" % (repr(self.context), repr(self.type))   611    612 class Self:   613    614     """   615     A program node encapsulating object/context information in an argument list.   616     This is not particularly like Attribute, Class, Instance or other such   617     things, since it actually appears in the program representation.   618     """   619    620     def __init__(self, attribute):   621         self.types = [attribute]   622    623 # Configuration setting.   624    625 Class = SingleInstanceClass   626 #Class = MultipleInstanceClass   627    628 def set_single_instance_mode():   629     global Class   630     Class = SingleInstanceClass   631    632 def set_multiple_instance_mode():   633     global Class   634     Class = MultipleInstanceClass   635    636 # vim: tabstop=4 expandtab shiftwidth=4