simplify

simplified.py

187:f883eee94852
2007-02-06 paulb Made functions and lambdas use "defining" Subprogram nodes. Changed _nodes construction to only use "defining" nodes.
     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 and node.defining:   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         if hasattr(other, "full_name"):   480             return self.full_name() == other.full_name()   481         else:   482             return NotImplemented   483    484     def __hash__(self):   485         return id(self)   486    487 class Module(Comparable):   488    489     "A Python module."   490    491     def full_name(self):   492         return "module %s" % self.name   493    494 # Special non-program nodes.   495    496 class Structure(Comparable): "A non-program node containing some kind of namespace."   497    498 class _Class(Structure, WithName):   499    500     "A Python class."   501    502     def __init__(self, *args, **kw):   503         Structure.__init__(self, *args, **kw)   504         WithName.__init__(self)   505    506     def full_name(self):   507         return "class %s" % self._full_name   508    509 class SingleInstanceClass(_Class):   510    511     "A Python class."   512    513     def __init__(self, *args, **kw):   514         _Class.__init__(self, *args, **kw)   515         self.instance = None   516    517     def has_instance(self, node):   518         return self.instance is not None   519    520     def add_instance(self, node, instance):   521         self.instance = instance   522    523     def get_instance(self, node):   524         return self.instance   525    526     def get_instance_name(self, instance):   527         return self._full_name   528    529     # Attribute propagation.   530    531     def get_attribute_for_instance(self, attribute, instance):   532         return attribute   533    534 class MultipleInstanceClass(_Class):   535    536     "A Python class."   537    538     def __init__(self, *args, **kw):   539         _Class.__init__(self, *args, **kw)   540         self.instances = {}   541         self.attributes_for_instances = {}   542    543     def _get_key(self, node):   544         return id(getattr(node, "original", None)) # self.module.original   545    546     def has_instance(self, node):   547         return self.instances.has_key(self._get_key(node))   548    549     def add_instance(self, node, instance):   550         self.instances[self._get_key(node)] = instance   551    552     def get_instance(self, node):   553         return self.instances[self._get_key(node)]   554    555     def get_instance_name(self, instance):   556         return name(instance, self._full_name)   557    558     # Attribute propagation.   559    560     def get_attribute_for_instance(self, attribute, instance):   561         if isinstance(attribute.type, Subprogram):   562             subprogram = attribute.type   563             key = (subprogram, instance)   564             if not self.attributes_for_instances.has_key(key):   565                 self.attributes_for_instances[key] = Attribute(attribute.context, subprogram.copy(subprogram.full_name()))   566             return self.attributes_for_instances[key]   567         else:   568             return attribute   569    570 class Instance(Structure):   571    572     "An instance."   573    574     def full_name(self):   575         return self.get_class().get_instance_name(self)   576    577     def get_class(self):   578         return self.namespace.load("__class__")[0].type   579    580     def __repr__(self):   581         return "Instance of type '%s'" % self.full_name()   582    583     def __eq__(self, other):   584         # NOTE: Single instance: all instances are the same   585         # NOTE: Multiple instances: all instances are different   586         return self.full_name() == other.full_name()   587    588     def __hash__(self):   589         return id(self)   590    591 class Constant(Instance):   592    593     "A constant initialised with a type name for future processing."   594    595     def __init__(self, *args, **kw):   596         Instance.__init__(self, *args, **kw)   597         self.typename = self.value.__class__.__name__   598    599     # NOTE: Hacked full_name avoiding instantiation ordering issues:   600     # NOTE: initialise built-in types, initialise built-in constants.   601    602     #def full_name(self):   603     #    return self.typename + "-c"   604    605 class Attribute:   606    607     """   608     An attribute abstraction, indicating the type of the attribute along with   609     its context or origin.   610     """   611    612     def __init__(self, context, type):   613         self.context = context   614         self.type = type   615    616     def __eq__(self, other):   617         return hasattr(other, "type") and other.type == self.type or other == self.type   618    619     def __repr__(self):   620         return "Attribute(%s, %s)" % (repr(self.context), repr(self.type))   621    622     def __hash__(self):   623         return id(self)   624    625 class Self:   626    627     """   628     A program node encapsulating object/context information in an argument list.   629     This is not particularly like Attribute, Class, Instance or other such   630     things, since it actually appears in the program representation.   631     """   632    633     def __init__(self, attribute):   634         self.types = [attribute]   635    636 # Configuration setting.   637    638 Class = SingleInstanceClass   639 #Class = MultipleInstanceClass   640    641 def set_single_instance_mode():   642     global Class   643     Class = SingleInstanceClass   644    645 def set_multiple_instance_mode():   646     global Class   647     Class = MultipleInstanceClass   648    649 # vim: tabstop=4 expandtab shiftwidth=4