simplify

simplified.py

185:bcff64bc6ffa
2007-01-26 paulb Consolidated original node information in the original attribute, adding it for all invocations so that instance lookup may still work. Renamed _new_instance to new_instance, removing the old new_instance method. Increased the recursion limit.
     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"   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):   289    290         """   291         Perform a deep copy of the node, optionally specifying a 'new_name',   292         returning a new unannotated copy.   293         """   294    295         # Copy the common attributes of this node.   296    297         common = {}   298         for attr in self.common_attributes:   299             if hasattr(self, attr):   300                 common[attr] = getattr(self, attr)   301    302         if new_name is not None:   303             common["name"] = new_name   304    305         # Instantiate the copy, avoiding side-effects with original and defining.   306    307         node = self.__class__(**common)   308         node.defining = self.defining   309    310         # Add links to copied nodes from original AST nodes.   311    312         if node.original is not None:   313             if not hasattr(node.original, "_nodes"):   314                 node.original._nodes = []   315             node.original._nodes.append(node)   316    317         # Copy attributes of different types.   318    319         for attr in self.expression_attributes:   320             if hasattr(self, attr):   321                 n = getattr(self, attr)   322                 if n is None:   323                     n2 = n   324                 else:   325                     n2 = n.copy()   326                 setattr(node, attr, n2)   327    328         for attr in self.invocation_attributes:   329             if hasattr(self, attr):   330                 l = getattr(self, attr)   331                 l2 = []   332                 for name, n in l:   333                     if n is None:   334                         l2.append((name, n))   335                     else:   336                         l2.append((name, n.copy()))   337                 setattr(node, attr, l2)   338    339         for attr in self.grouping_attributes:   340             if hasattr(self, attr):   341                 l = getattr(self, attr)   342                 setattr(node, attr, [n.copy() for n in l])   343    344         # Arguments are usually processed further - "args" is useless.   345    346         if hasattr(self, "pos_args"):   347             node.pos_args = [n.copy() for n in self.pos_args]   348    349         if hasattr(self, "kw_args"):   350             node.kw_args = {}   351             for name, n in self.kw_args.items():   352                 node.kw_args[name] = n.copy()   353    354         return node   355    356 # These are the supported "operations" described by simplified program nodes.   357    358 class Pass(Node): "A placeholder node corresponding to pass."   359 class Assign(Node): "A grouping node for assignment-related operations."   360 class Keyword(Node): "A grouping node for keyword arguments."   361 class Global(Node): "A global name designator."   362 class Import(Node): "A module import operation."   363 class LoadTemp(Node): "Load a previously-stored temporary value."   364 class LoadName(Node): "Load a named object."   365 class LoadAttr(Node): "Load an object attribute."   366 class LoadRef(Node): "Load a reference, typically a subprogram or a constant."   367 class LoadExc(Node): "Load a handled exception."   368 class CheckExc(Node): "Check a handled exception."   369 class StoreTemp(Node): "Store a temporary value."   370 class StoreName(Node): "Associate a name with an object."   371 class StoreAttr(Node): "Associate an object's attribute with a value."   372 class ReleaseTemp(Node): "Release a temporary value."   373 class Try(Node): "A try...except...else...finally grouping node."   374 class Raise(Node): "An exception raising node."   375 class Not(Node): "A negation of an expression."   376    377 # There are two types of return node: return from function and return from   378 # block.   379    380 class Return(Node):   381    382     "Return an evaluated expression."   383    384     pass   385    386 class ReturnFromFunction(Return):   387     pass   388    389 class ReturnFromBlock(Return):   390     pass   391    392 # Some behaviour is set as the default in conditional nodes but may be   393 # overridden.   394    395 class Conditional(Node):   396    397     "A conditional node consisting of a test and outcomes."   398    399     def __init__(self, *args, **kw):   400         self.isolate_test = 0   401         Node.__init__(self, *args, **kw)   402    403 # Invocations involve some more work to process calculated attributes.   404    405 class Invoke(Node):   406    407     "An invocation."   408    409     pass   410    411 class InvokeFunction(Invoke):   412    413     "A function or method invocation."   414    415     def __init__(self, *args, **kw):   416         self.args = []   417         self.star = None   418         self.dstar = None   419         Invoke.__init__(self, *args, **kw)   420         self.set_args(self.args)   421         self.share_locals = 0   422    423     def set_args(self, args):   424    425         "Sort the 'args' into positional and keyword arguments."   426    427         self.pos_args = []   428         self.kw_args = {}   429         add_kw = 0   430         for arg in args:   431             if not add_kw:   432                 if not isinstance(arg, Keyword):   433                     self.pos_args.append(arg)   434                 else:   435                     add_kw = 1   436             if add_kw:   437                 if isinstance(arg, Keyword):   438                     self.kw_args[arg.name] = arg.expr   439                 else:   440                     raise TypeError, "Positional argument appears after keyword arguments in '%s'." % self   441    442 class InvokeBlock(Invoke):   443    444     "A block or loop invocation."   445    446     def __init__(self, *args, **kw):   447         self.share_locals = 1   448         Invoke.__init__(self, *args, **kw)   449    450 # Named nodes are those which can be referenced in some way.   451    452 class WithName:   453    454     "Node naming."   455    456     def __init__(self):   457         self._full_name = name(self, self.name or "$untitled")   458    459     def full_name(self):   460         return self._full_name   461    462 # Program structure nodes.   463    464 class Subprogram(Node, WithName):   465    466     "A subprogram: functions, methods and loops."   467    468     def __init__(self, *args, **kw):   469         Node.__init__(self, *args, **kw)   470         WithName.__init__(self)   471    472 class Comparable(Node):   473    474     "Comparable nodes implementing the 'full_name' method."   475    476     def __eq__(self, other):   477         # NOTE: Single instance: all instances are the same   478         # NOTE: Multiple instances: all instances are different   479         return self.full_name() == other.full_name()   480    481     def __hash__(self):   482         return id(self)   483    484 class Module(Comparable):   485    486     "A Python module."   487    488     def full_name(self):   489         return "module %s" % self.name   490    491 # Special non-program nodes.   492    493 class Structure(Comparable): "A non-program node containing some kind of namespace."   494    495 class _Class(Structure, WithName):   496    497     "A Python class."   498    499     def __init__(self, *args, **kw):   500         Structure.__init__(self, *args, **kw)   501         WithName.__init__(self)   502    503     def full_name(self):   504         return "class %s" % self._full_name   505    506 class SingleInstanceClass(_Class):   507    508     "A Python class."   509    510     def __init__(self, *args, **kw):   511         _Class.__init__(self, *args, **kw)   512         self.instance = None   513    514     def has_instance(self, node):   515         return self.instance is not None   516    517     def add_instance(self, node, instance):   518         self.instance = instance   519    520     def get_instance(self, node):   521         return self.instance   522    523     def get_instance_name(self, instance):   524         return self._full_name   525    526     # Attribute propagation.   527    528     def get_attribute_for_instance(self, attribute, instance):   529         return attribute   530    531 class MultipleInstanceClass(_Class):   532    533     "A Python class."   534    535     def __init__(self, *args, **kw):   536         _Class.__init__(self, *args, **kw)   537         self.instances = {}   538         self.attributes_for_instances = {}   539    540     def _get_key(self, node):   541         return id(getattr(node, "original", None)) # self.module.original   542    543     def has_instance(self, node):   544         return self.instances.has_key(self._get_key(node))   545    546     def add_instance(self, node, instance):   547         self.instances[self._get_key(node)] = instance   548    549     def get_instance(self, node):   550         return self.instances[self._get_key(node)]   551    552     def get_instance_name(self, instance):   553         return name(instance, self._full_name)   554    555     # Attribute propagation.   556    557     def get_attribute_for_instance(self, attribute, instance):   558         if isinstance(attribute.type, Subprogram):   559             subprogram = attribute.type   560             key = (subprogram, instance)   561             if not self.attributes_for_instances.has_key(key):   562                 self.attributes_for_instances[key] = Attribute(attribute.context, subprogram.copy(subprogram.full_name()))   563             return self.attributes_for_instances[key]   564         else:   565             return attribute   566    567 class Instance(Structure):   568    569     "An instance."   570    571     def full_name(self):   572         return self.get_class().get_instance_name(self)   573    574     def get_class(self):   575         return self.namespace.load("__class__")[0].type   576    577     def __repr__(self):   578         return "Instance of type '%s'" % self.full_name()   579    580     def __eq__(self, other):   581         # NOTE: Single instance: all instances are the same   582         # NOTE: Multiple instances: all instances are different   583         return self.full_name() == other.full_name()   584    585     def __hash__(self):   586         return id(self)   587    588 class Constant(Instance):   589    590     "A constant initialised with a type name for future processing."   591    592     def __init__(self, *args, **kw):   593         Instance.__init__(self, *args, **kw)   594         self.typename = self.value.__class__.__name__   595    596     # NOTE: Hacked full_name avoiding instantiation ordering issues:   597     # NOTE: initialise built-in types, initialise built-in constants.   598    599     #def full_name(self):   600     #    return self.typename + "-c"   601    602 class Attribute:   603    604     """   605     An attribute abstraction, indicating the type of the attribute along with   606     its context or origin.   607     """   608    609     def __init__(self, context, type):   610         self.context = context   611         self.type = type   612    613     def __eq__(self, other):   614         return hasattr(other, "type") and other.type == self.type or other == self.type   615    616     def __repr__(self):   617         return "Attribute(%s, %s)" % (repr(self.context), repr(self.type))   618    619     def __hash__(self):   620         return id(self)   621    622 class Self:   623    624     """   625     A program node encapsulating object/context information in an argument list.   626     This is not particularly like Attribute, Class, Instance or other such   627     things, since it actually appears in the program representation.   628     """   629    630     def __init__(self, attribute):   631         self.types = [attribute]   632    633 # Configuration setting.   634    635 Class = SingleInstanceClass   636 #Class = MultipleInstanceClass   637    638 def set_single_instance_mode():   639     global Class   640     Class = SingleInstanceClass   641    642 def set_multiple_instance_mode():   643     global Class   644     Class = MultipleInstanceClass   645    646 # vim: tabstop=4 expandtab shiftwidth=4