simplify

annotate.py

184:7ea581069c2e
2007-01-25 paulb Fixed nested scopes workaround to only add function names to namespaces - not module names as well.
     1 #!/usr/bin/env python     2      3 """     4 Annotate program node structures. The code in this module operates upon nodes     5 which are produced when simplifying AST node trees originating from the compiler     6 module.     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     27 To use this module, the easiest approach is to use the load function:    28     29 load(filename, builtins)    30     31 To control module importing, an importer should be constructed and employed.    32 Here, the standard path for module searching is used:    33     34 importer = Importer(sys.path)    35 load(filename, builtins, importer)    36     37 Underneath the load function, the annotate function provides support for    38 annotating modules already processed by simplify and fixnames:    39     40 annotate(module, builtins)    41     42 And at the most basic level, the most intricate approach involves obtaining an    43 Annotator object:    44     45 annotator = Annotator()    46     47 Then, processing an existing module with it:    48     49 annotator.process(module)    50     51 If a module containing built-in classes and functions has already been    52 annotated, such a module should be passed in as an additional argument:    53     54 annotator.process(module, builtins)    55 """    56     57 from simplified import *    58 import simplify, fixnames # for the load function    59 import compiler    60 import os    61     62 class System:    63     64     """    65     A class maintaining the state of the annotation system. When the system    66     counter can no longer be incremented by any annotation operation, the    67     system may be considered stable and fully annotated.    68     """    69     70     def __init__(self):    71         self.count = 0    72     73     def init(self, node):    74     75         "Initialise a 'node' for annotation."    76     77         if not hasattr(node, "types"):    78             node.types = []    79     80     def annotate(self, node, types):    81     82         "Annotate the given 'node' with the given 'types'."    83     84         self.init(node)    85         self.combine(node.types, types)    86     87     def combine(self, target, types):    88     89         """    90         Combine the 'target' list with the given 'types', counting new members.    91         """    92     93         for type in types:    94             if type not in target:    95                 target.append(type)    96                 self.count += 1    97     98 system = System()    99    100 # Exceptions.   101    102 class AnnotationError(SimplifiedError):   103    104     "An error in the annotation process."   105    106     pass   107    108 class AnnotationMessage(Exception):   109    110     "A lesser annotation error."   111    112     pass   113    114 # Annotation.   115    116 class Annotator(Visitor):   117    118     """   119     The type annotator which traverses the program nodes, typically depth-first,   120     and maintains a record of the current set of types applying to the currently   121     considered operation. Such types are also recorded on the nodes, and a   122     special "system" record is maintained to monitor the level of annotation   123     activity with a view to recognising when no more annotations are possible.   124    125     Throughout the annotation activity, type information consists of lists of   126     Attribute objects where such objects retain information about the context of   127     the type (since a value in the program may be associated with an object or   128     class) and the actual type of the value being manipulated. Upon accessing   129     attribute information on namespaces, additional accessor information is also   130     exchanged - this provides a means of distinguishing between the different   131     types possible when the means of constructing the namespace may depend on   132     run-time behaviour.   133    134     Covered: Assign, CheckExc, Conditional, Global, Import, InvokeBlock,   135              InvokeFunction, LoadAttr, LoadExc, LoadName, LoadRef, LoadTemp,   136              Module, Not, Pass, Raise, ReleaseTemp, ReturnFromBlock,   137              ReturnFromFunction, StoreAttr, StoreName, StoreTemp, Subprogram,   138              Try.   139     """   140    141     def __init__(self, importer=None):   142    143         "Initialise the visitor with an optional 'importer'."   144    145         Visitor.__init__(self)   146         self.system = system   147         self.importer = importer or Importer()   148    149         # Satisfy visitor issues.   150    151         self.visitor = self   152    153     def process(self, module, builtins=None):   154    155         """   156         Process the given 'module', using the optional 'builtins' to access   157         built-in classes and functions.   158         """   159    160         self.subprograms = []   161         self.current_subprograms = []   162         self.current_namespaces = []   163         self.namespace = None   164         self.module = module   165    166         # Give constants their own namespace.   167    168         for value, constant in module.simplifier.constants.items():   169             constant.namespace = Namespace()   170    171         # Process the module, supplying builtins if possible.   172    173         self.builtins = builtins   174         self.global_namespace = Namespace()   175    176         if builtins is not None:   177             self.builtins_namespace = builtins.namespace   178         else:   179             self.builtins_namespace = self.global_namespace   180    181         return self.process_node(module, self.global_namespace)   182    183     def process_node(self, node, locals):   184    185         """   186         Process a subprogram or module 'node', indicating the initial 'locals'.   187         Return an annotated subprogram or module. Note that this method may   188         mutate nodes in the original program.   189         """   190    191         # Record the current subprogram and namespace.   192    193         self.current_subprograms.append(node)   194    195         # Determine the namespace.   196    197         self.current_namespaces.append(self.namespace)   198         self.namespace = locals   199    200         # Add namespace details to any structure involved.   201    202         if getattr(node, "structure", None) is not None:   203             node.structure.namespace = Namespace()   204    205             # Initialise bases where appropriate.   206    207             if hasattr(node.structure, "bases"):   208                 base_refs = []   209                 for base in node.structure.bases:   210                     self.dispatch(base)   211                     base_refs.append(self.namespace.types)   212                 node.structure.base_refs = base_refs   213    214         # Dispatch to the code itself.   215    216         node.namespace = self.namespace   217         result = self.dispatch(node)   218         result.namespace = self.namespace   219    220         # Obtain the return values.   221    222         self.last_returns = self.namespace.returns   223         self.last_raises = self.namespace.raises   224         self.returned_locals = self.namespace.return_locals   225    226         # Restore the previous subprogram and namespace.   227    228         self.namespace = self.current_namespaces.pop()   229         self.current_subprograms.pop()   230    231         return result   232    233     def annotate(self, node, types=None):   234    235         """   236         Annotate the given 'node' in the system, using either the optional   237         'types' or the namespace's current type information.   238         """   239    240         self.system.annotate(node, types or self.namespace.types)   241    242     def annotate_parameters(self, node, items):   243    244         """   245         Annotate the given 'node' using the given 'items' and updating the   246         system's annotation counter.   247         """   248    249         if not hasattr(node, "paramtypes"):   250             node.paramtypes = {}   251    252         for param, types in items:   253             if not node.paramtypes.has_key(param):   254                 node.paramtypes[param] = []   255             self.system.combine(node.paramtypes[param], types)   256    257     # Visitor methods.   258    259     def default(self, node):   260    261         """   262         Process the given 'node', given that it does not have a specific   263         handler.   264         """   265    266         raise AnnotationMessage, "Node '%s' not supported." % node   267    268     def dispatch(self, node, *args):   269         try:   270             return Visitor.dispatch(self, node, *args)   271         except AnnotationError, exc:   272             exc.add(node)   273             raise   274         except AnnotationMessage, exc:   275             raise AnnotationError(exc, node)   276    277     # Specific node methods.   278    279     def visitAssign(self, assign):   280    281         """   282         Return the 'assign' node whose contents (merely a group of nodes) have   283         been processed.   284         """   285    286         assign.code = self.dispatches(assign.code)   287         return assign   288    289     def visitCheckExc(self, checkexc):   290    291         """   292         Return the 'checkexc' node, processing the expression to find the   293         possible types of the exception, and processing each choice to build a   294         list of checked types for the exception.   295         """   296    297         checkexc.expr = self.dispatch(checkexc.expr)   298         expr_types = self.namespace.types   299         choice_types = []   300         choices = []   301         for choice in checkexc.choices:   302             choices.append(self.dispatch(choice))   303             choice_types += self.namespace.types   304         for expr_type in expr_types:   305             if expr_type.type.get_class() not in choice_types:   306                 self._prune_non_accesses(checkexc.expr, expr_type)   307         return checkexc   308    309     def visitConditional(self, conditional):   310    311         """   312         Return the 'conditional' node, processing the test, body and else   313         clauses and recording their processed forms. The body and else clauses   314         are processed within their own namespaces, and the test is also   315         processed in its own namespace if 'isolate_test' is set on the   316         'conditional' node.   317         """   318    319         # Conditionals keep local namespace changes isolated.   320         # With Return nodes inside the body/else sections, the changes are   321         # communicated to the caller.   322    323         is_module = self.namespace is self.module.namespace   324    325         # Where the test is closely associated with the body, save the namespace   326         # before entering the test.   327    328         if conditional.isolate_test:   329             saved_namespace = self.namespace   330             self.namespace = Namespace()   331             if is_module:   332                 self.module.namespace = self.namespace   333             self.namespace.merge_namespace(saved_namespace)   334    335         conditional.test = self.dispatch(conditional.test)   336    337         # Where the test may affect the body and the else clause, save the   338         # namespace after processing the test.   339    340         if not conditional.isolate_test:   341             saved_namespace = self.namespace   342             self.namespace = Namespace()   343             if is_module:   344                 self.module.namespace = self.namespace   345             self.namespace.merge_namespace(saved_namespace)   346    347         # Process the body clause.   348    349         conditional.body = self.dispatches(conditional.body)   350         body_namespace = self.namespace   351    352         # Use the saved namespace as a template for the else clause.   353    354         self.namespace = Namespace()   355         if is_module:   356             self.module.namespace = self.namespace   357         self.namespace.merge_namespace(saved_namespace)   358    359         # Process the else clause.   360    361         conditional.else_ = self.dispatches(conditional.else_)   362         else_namespace = self.namespace   363    364         # Merge the body and else namespaces.   365    366         self.namespace = Namespace()   367         if is_module:   368             self.module.namespace = self.namespace   369         self.namespace.merge_namespace(body_namespace)   370         self.namespace.merge_namespace(else_namespace)   371    372         # NOTE: Test of exception type pruning based on the test/body.   373    374         if conditional.isolate_test:   375             for exc_type in body_namespace.raises:   376                 self.namespace.revoke_exception_type(exc_type)   377    378         return conditional   379    380     def visitGlobal(self, global_):   381    382         """   383         Return the 'global_' node unprocessed since namespaces should have   384         already been altered to take global names into consideration.   385         """   386    387         return global_   388    389     def visitImport(self, import_):   390    391         """   392         Return the 'import_' node, importing the module with the stated name   393         and storing details on the node.   394         """   395    396         module = self.importer.load(import_.name, self.builtins, getattr(import_, "alias", None))   397         if module is not None:   398             self.namespace.set_types([module])   399         else:   400             self.namespace.set_types([])   401         self.annotate(import_) # mainly for viewing purposes   402         return import_   403    404     def _visitInvoke(self, invoke, invocation_types, have_args):   405    406         """   407         Return the processed 'invoke' node, using the given 'invocation_types'   408         as the list of callables to be investigated for instantiation or for the   409         invocation of functions or blocks. If 'have_args' is a true value, any   410         invocation or instantiation will involve arguments.   411         """   412    413         # Now locate and invoke the subprogram. This can be complicated because   414         # the target may be a class or object, and there may be many different   415         # related subprograms.   416    417         invocations = []   418    419         # Visit each callable in turn, finding subprograms.   420    421         for attr in invocation_types:   422    423             # Deal with class invocations by providing instance objects.   424             # Here, each class is queried for the __init__ method, which may   425             # exist for some combinations of classes in a hierarchy but not for   426             # others.   427    428             if isinstance(attr.type, Class):   429                 attributes = get_attributes(attr.type, "__init__")   430    431             # Deal with object invocations by using __call__ methods.   432    433             elif isinstance(attr.type, Instance):   434                 attributes = get_attributes(attr.type, "__call__")   435    436             # Normal functions or methods are more straightforward.   437             # Here, we model them using an attribute with no context and with   438             # no associated accessor.   439    440             else:   441                 attributes = [(attr, None)]   442    443             # Inspect each attribute and extract the subprogram.   444    445             for attribute, accessor in attributes:   446    447                 # If a class is involved, presume that it must create a new   448                 # object.   449    450                 if isinstance(attr.type, Class):   451    452                     # Instantiate the class.   453    454                     instance = self.new_instance(invoke, "new", attr.type.full_name(), attr.type)   455    456                     # For instantiations, switch the context.   457    458                     if attribute is not None:   459                         attribute = Attribute(instance, attribute.type)   460    461                 # Skip cases where no callable is found.   462    463                 if attribute is not None:   464    465                     # If a subprogram is defined, invoke it.   466    467                     self.invoke_subprogram(invoke, attribute)   468                     if attribute.type not in invocations:   469                         invocations.append(attribute.type)   470    471                 elif not isinstance(attr.type, Class):   472                     print "Invocation type is None for", accessor   473    474                 else:   475    476                     # Test to see if no arguments were supplied in cases where no   477                     # initialiser was found.   478    479                     if have_args:   480                         raise AnnotationMessage, "No initialiser found for '%s' with arguments." % attr.type   481    482             # Special case: initialisation.   483    484             if isinstance(attr.type, Class):   485    486                 # Associate the instance with the result of this invocation.   487    488                 self.namespace.set_types([Attribute(None, instance)])   489                 self.annotate(invoke)   490    491         # Remember the invocations that were found, along with the return type   492         # information.   493    494         invoke.invocations = invocations   495         self.namespace.set_types(getattr(invoke, "types", []))   496         return invoke   497    498     def visitInvokeBlock(self, invoke):   499    500         """   501         Return the processed 'invoke' node, first finding the callables   502         indicated by the expression.   503         """   504    505         invoke.expr = self.dispatch(invoke.expr)   506         invocation_types = self.namespace.types   507         return self._visitInvoke(invoke, invocation_types, have_args=0)   508    509     def visitInvokeFunction(self, invoke):   510    511         """   512         Return the processed 'invoke' node, first finding the callables   513         indicated by the expression.   514         """   515    516         invoke.expr = self.dispatch(invoke.expr)   517         invocation_types = self.namespace.types   518    519         # Invocation processing starts with making sure that the arguments have   520         # been processed.   521    522         return self._visitInvoke(invoke, invocation_types, have_args=self.process_args(invoke))   523    524     def visitLoadAttr(self, loadattr):   525    526         """   527         Return the 'loadattr' node, processing and storing the expression, and   528         using the expression's types to construct records of accesses and   529         non-accesses using the stated attribute name.   530         """   531    532         loadattr.expr = self.dispatch(loadattr.expr)   533         types = []   534         non_accesses = []   535         accesses = {}   536         for attr in self.namespace.types:   537             attributes = get_attributes(attr.type, loadattr.name)   538             if not attributes:   539                 if not attr in non_accesses:   540                     non_accesses.append(attr)   541                     combine(self.namespace.raises, self.get_builtin_instances(loadattr, "AttributeError"))   542    543                     # Revoke this type from any name involved.   544    545                     self._prune_non_accesses(loadattr.expr, attr)   546    547             for attribute, accessor in attributes:   548                 if attribute is not None:   549                     types.append(attribute)   550                     if not accesses.has_key(attr.type):   551                         accesses[attr.type] = []   552                     if not (attribute, accessor) in accesses[attr.type]:   553                         accesses[attr.type].append((attribute, accessor))   554                 else:   555                     if not attr in non_accesses:   556                         non_accesses.append(attr)   557                         combine(self.namespace.raises, self.get_builtin_instances(loadattr, "AttributeError"))   558    559                         # Revoke this type from any name involved.   560    561                         self._prune_non_accesses(loadattr.expr, attr)   562    563         if not types:   564             print "No attribute found for", loadattr.name, "given", self.namespace.types   565         self.namespace.set_types(types)   566         loadattr.non_accesses = non_accesses   567         loadattr.accesses = accesses   568         self.annotate(loadattr)   569         return loadattr   570    571     def _prune_non_accesses(self, expr, attr):   572    573         """   574         Prune type information from 'expr' where the given 'attr' has been   575         shown to be a non-access.   576         """   577    578         if isinstance(expr, LoadName):   579             self.namespace.revoke(expr.name, attr)   580         elif isinstance(expr, LoadExc):   581             self.namespace.revoke_exception_type(attr)   582         elif isinstance(expr, LoadTemp):   583             self.namespace.revoke_temp_type(getattr(expr, "index", None), attr)   584    585         # LoadAttr cannot be pruned since this might unintentionally prune   586         # legitimate types from other applications of the referenced type, it   587         # almost certainly doesn't take "concurrent" mutation into   588         # consideration (where in a running program, the pruned type is actually   589         # reintroduced, making the pruning invalid), and there is no easy way of   590         # preserving the meaning of a namespace without either creating lots of   591         # specialised instances, and even then...   592    593         #elif isinstance(expr, LoadAttr):   594         #    for expr_attr in expr.expr.types:   595         #        if hasattr(expr_attr.type, "namespace"):   596         #            expr_attr.type.namespace.revoke(expr.name, attr)   597    598     def visitLoadExc(self, loadexc):   599    600         """   601         Return the 'loadexc' node, discovering the possible exception types   602         raised.   603         """   604    605         self.namespace.set_types(self.namespace.raises[:])   606         self.annotate(loadexc)   607         return loadexc   608    609     def visitLoadName(self, loadname):   610    611         """   612         Return the 'loadname' node, processing the name information on the node   613         to determine which types are involved with the name.   614         """   615    616         self.namespace.set_types(self.namespace.load(loadname.name))   617         result = loadname   618         self.annotate(result)   619         return result   620    621     def visitLoadRef(self, loadref):   622    623         """   624         Return the 'loadref' node, obtaining type information about the   625         reference stated on the node.   626         """   627    628         self.namespace.set_types([Attribute(None, loadref.ref)])   629         self.annotate(loadref)   630         return loadref   631    632     def visitLoadTemp(self, loadtemp):   633    634         """   635         Return the 'loadtemp' node, obtaining type information about the   636         temporary variable accessed, and removing variable information where the   637         'release' attribute has been set on the node.   638         """   639    640         index = getattr(loadtemp, "index", None)   641         try:   642             if getattr(loadtemp, "release", 0):   643                 self.namespace.set_types(self.namespace.temp[index].pop())   644             else:   645                 self.namespace.set_types(self.namespace.temp[index][-1])   646         except KeyError:   647             raise AnnotationMessage, "Temporary store index '%s' not defined." % index   648         self.annotate(loadtemp)   649         return loadtemp   650    651     def visitModule(self, module):   652    653         """   654         Return the processed 'module' whose contents (merely a group of nodes)   655         are processed.   656         """   657    658         module.code = self.dispatches(module.code)   659         return module   660    661     def visitNot(self, not_):   662    663         "Return the 'not_' node whose expression is processed."   664    665         not_.expr = self.dispatch(not_.expr)   666         return not_   667    668     def visitPass(self, pass_):   669    670         "Return the unprocessed 'pass_' node."   671    672         return pass_   673    674     def visitRaise(self, raise_):   675    676         """   677         Return the 'raise_' node, processing any traceback information along   678         with the raised exception expression, converting the node into a kind of   679         invocation where the expression is found not to be an invocation itself.   680         This node affects the namespace, adding exception types to the list of   681         those raised in the namespace.   682         """   683    684         if getattr(raise_, "traceback", None) is not None:   685             raise_.traceback = self.dispatch(raise_.traceback)   686         raise_.expr = self.dispatch(raise_.expr)   687    688         # Handle bare name exceptions by converting any classes to instances.   689    690         if not isinstance(raise_.expr, InvokeFunction):   691             raise_.pos_args = []   692             raise_.kw_args = {}   693             raise_.star = None   694             raise_.dstar = None   695             types = []   696             for attr in self.namespace.types:   697                 if isinstance(attr.type, Class):   698                     self._visitInvoke(raise_, [attr], have_args=0)   699                 types += self.namespace.types   700         else:   701             types = self.namespace.types   702                703         combine(self.namespace.raises, types)   704         return raise_   705    706     def visitReleaseTemp(self, releasetemp):   707    708         """   709         Return the 'releasetemp' node, removing temporary variable information   710         from the current namespace.   711         """   712    713         index = getattr(releasetemp, "index", None)   714         try:   715             self.namespace.temp[index].pop()   716         except KeyError:   717             raise AnnotationMessage, "Temporary store index '%s' not defined." % index   718         except IndexError:   719             pass #raise AnnotationMessage, "Temporary store index '%s' is empty." % index   720         return releasetemp   721    722     def visitReturn(self, return_):   723    724         """   725         Return the 'return_' node, processing any expression and obtaining type   726         information to be accumulated in the current namespace's list of return   727         types. A snapshot of the namespace is taken for the purposes of   728         reconciling or merging namespaces where subprograms actually share   729         locals with their callers.   730         """   731    732         if hasattr(return_, "expr"):   733             return_.expr = self.dispatch(return_.expr)   734             combine(self.namespace.returns, self.namespace.types)   735             self.annotate(return_)   736         self.namespace.snapshot()   737         return return_   738    739     visitReturnFromBlock = visitReturn   740     visitReturnFromFunction = visitReturn   741    742     def visitStoreAttr(self, storeattr):   743    744         """   745         Return the 'storeattr' node, processing the expression and target, and   746         using the type information obtained to build records of legitimate   747         writes to the stated attribute, along with "impossible" non-writes to   748         the attribute.   749         """   750    751         storeattr.expr = self.dispatch(storeattr.expr)   752         expr = self.namespace.types   753         storeattr.lvalue = self.dispatch(storeattr.lvalue)   754         writes = {}   755         non_writes = []   756         for attr in self.namespace.types:   757             # NOTE: Impose "atomic" constraints on certain types.   758             if attr is None:   759                 if not attr in non_writes:   760                     non_writes.append(attr)   761                 continue   762             attr.type.namespace.add(storeattr.name, expr)   763             writes[attr.type] = attr.type.namespace.load(storeattr.name)   764         if not writes:   765             print "Unable to store attribute", storeattr.name, "given", self.namespace.types   766         storeattr.writes = writes   767         storeattr.non_writes = non_writes   768         return storeattr   769    770     def visitStoreName(self, storename):   771    772         """   773         Return the 'storename' node, processing the expression on the node and   774         associating the type information obtained with the stated name in the   775         current namespace.   776         """   777    778         storename.expr = self.dispatch(storename.expr)   779         self.namespace.store(storename.name, self.namespace.types)   780         return storename   781    782     def visitStoreTemp(self, storetemp):   783    784         """   785         Return the 'storetemp' node, processing the expression on the node and   786         associating the type information obtained with a temporary variable in   787         the current namespace.   788         """   789    790         storetemp.expr = self.dispatch(storetemp.expr)   791         index = getattr(storetemp, "index", None)   792         if not self.namespace.temp.has_key(index):   793             self.namespace.temp[index] = []   794         self.namespace.temp[index].append(self.namespace.types)   795         return storetemp   796    797     def visitSubprogram(self, subprogram):   798    799         """   800         Return the 'subprogram' node, processing its contents (a group of nodes   801         comprising the subprogram).   802         """   803    804         subprogram.code = self.dispatches(subprogram.code)   805         return subprogram   806    807     def visitTry(self, try_):   808    809         """   810         Return the 'try_' node, processing the body clause in its own namespace   811         derived from the current namespace, processing any handler clause using   812         the namespace information accumulated in the body, and processing any   813         else and finally clauses, attempting to supply each with appropriate   814         namespace information.   815         """   816    817         is_module = self.namespace is self.module.namespace   818    819         try_.body = self.dispatches(try_.body)   820    821         # Save the namespace from the body.   822    823         body_namespace = Namespace()   824         body_namespace.merge_namespace(self.namespace)   825    826         # Process the handler.   827    828         if hasattr(try_, "handler"):   829             try_.handler = self.dispatches(try_.handler)   830    831         # Save the namespace from the handler.   832    833         handler_namespace = Namespace()   834         handler_namespace.merge_namespace(self.namespace)   835    836         # Remember the raised exceptions encountered so far.   837    838         raises = self.namespace.raises   839    840         # Process the else clause.   841    842         if hasattr(try_, "else_"):   843    844             # Restore the body namespace for the else clause.   845    846             self.namespace = body_namespace   847             if is_module:   848                 self.module.namespace = self.namespace   849    850             # Empty the raised exceptions for the else clause.   851    852             self.namespace.raises = []   853             try_.else_ = self.dispatches(try_.else_)   854             self.namespace.raises = raises   855    856         # Merge the namespaces.   857    858         self.namespace = Namespace()   859         if is_module:   860             self.module.namespace = self.namespace   861         self.namespace.merge_namespace(body_namespace)   862         self.namespace.merge_namespace(handler_namespace)   863    864         # Process the finally clause, if any.   865    866         try_.finally_ = self.dispatches(try_.finally_)   867         return try_   868    869     # Utility methods.   870    871     def get_builtin_instances(self, node, name):   872         return [Attribute(None, self._new_instance(node, attr.type)) for attr in self.builtins.namespace[name]]   873    874     def new_instance(self, node, reason, target, type):   875    876         "Create, on the given 'node', a new instance with the given 'type'."   877    878         if not hasattr(node, "instances"):   879             node.instances = {}   880    881         if not node.instances.has_key((reason, target, type)):   882             instance = self._new_instance(node, type)   883             node.instances[(reason, target, type)] = instance   884    885         return node.instances[(reason, target, type)]   886    887     def _new_instance(self, node, type):   888    889         "For the given 'node', obtain an instance from the given 'type'."   890    891         if not type.has_instance(node):   892             instance = Instance()   893             instance.namespace = Namespace()   894             instance.namespace.store("__class__", [Attribute(None, type)])   895             type.add_instance(node, instance)   896         else:   897             instance = type.get_instance(node)   898    899         return instance   900    901     def invoke_subprogram(self, invoke, attribute):   902    903         """   904         Invoke using the given 'invoke' node the subprogram represented by the   905         given 'attribute'.   906         """   907    908         # Test for context information, making it into a real attribute.   909    910         if attribute.context is not None:   911             context = Attribute(None, attribute.context)   912             target = attribute.type   913         else:   914             context = None   915             target = attribute.type   916    917         # Test to see if anything has changed.   918    919         if hasattr(invoke, "syscount") and invoke.syscount.has_key(target) and invoke.syscount[target] == self.system.count:   920             return   921    922         # Remember the state of the system.   923    924         else:   925             if not hasattr(invoke, "syscount"):   926                 invoke.syscount = {}   927             invoke.syscount[target] = self.system.count   928    929         # Provide the correct namespace for the invocation.   930         # This may be a "shared" namespace...   931    932         if getattr(invoke, "share_locals", 0):   933             namespace = Namespace()   934             namespace.merge_namespace(self.namespace, everything=0)   935             using_module_namespace = self.namespace is self.module.namespace   936    937         # Or it may be a structure...   938    939         elif getattr(target, "structure", None):   940             namespace = Namespace()   941             using_module_namespace = 0   942    943         # Or it may be a new namespace populated with the supplied parameters.   944    945         else:   946             items = self.make_items(invoke, target, context)   947             namespace = Namespace()   948             namespace.merge_items(items)   949             using_module_namespace = 0   950    951             # NOTE: Avoid PEP 227 (nested scopes) whilst permitting references to a   952             # NOTE: subprogram within itself. Do not define the name of the function   953             # NOTE: within a method definition.   954    955             if getattr(target, "name", None) is not None and not getattr(target, "is_method", 0):   956                 namespace.store(target.name, [Attribute(None, target)])   957    958         # Process the subprogram.   959         # In order to keep global accesses working, the module namespace must be   960         # adjusted.   961    962         if using_module_namespace:   963             self.module.namespace = namespace   964    965         self.process_node(target, namespace)   966    967         # NOTE: Improve and verify this.   968         # If the invocation returns a value, acquire the return types.   969    970         if getattr(target, "returns_value", 0):   971             self.namespace.set_types(self.last_returns)   972             self.annotate(invoke)   973    974         # If it is a normal block, merge the locals.   975         # This can happen in addition to the above because for things like   976         # logical expressions, the namespace can be modified whilst values are   977         # returned as results.   978    979         if getattr(invoke, "share_locals", 0):   980             self.namespace.reset()   981    982             # Merge the locals snapshots.   983    984             for locals in self.returned_locals:   985    986                 # For blocks returning values (such as operations), do not merge   987                 # snapshots or results.   988    989                 if getattr(target, "returns_value", 0):   990                     self.namespace.merge_namespace(locals, everything=0)   991    992                 # For blocks not returning values (such as loops), merge   993                 # snapshots and results since they contain details of genuine   994                 # returns.   995    996                 else:   997                     self.namespace.merge_namespace(locals)   998    999         # Incorporate any raised exceptions.  1000   1001         combine(self.namespace.raises, self.last_raises)  1002   1003         # In order to keep global accesses working, the module namespace must be  1004         # adjusted.  1005   1006         if using_module_namespace:  1007             self.module.namespace = self.namespace  1008   1009     def process_args(self, invocation):  1010   1011         """  1012         Process the arguments associated with an 'invocation'. Return whether  1013         any arguments were processed.  1014         """  1015   1016         invocation.pos_args = self.dispatches(invocation.pos_args)  1017         invocation.kw_args = self.dispatch_dict(invocation.kw_args)  1018   1019         # Get type information for star and dstar arguments.  1020   1021         if invocation.star is not None:  1022             param, default = invocation.star  1023             default = self.dispatch(default)  1024             invocation.star = param, default  1025   1026         if invocation.dstar is not None:  1027             param, default = invocation.dstar  1028             default = self.dispatch(default)  1029             invocation.dstar = param, default  1030   1031         if invocation.pos_args or invocation.kw_args or invocation.star or invocation.dstar:  1032             return 1  1033         else:  1034             return 0  1035   1036     def make_items(self, invocation, subprogram, context):  1037   1038         """  1039         Make an items mapping for the 'invocation' of the 'subprogram' using the  1040         given 'context' (which may be None).  1041         """  1042   1043         if context is not None:  1044             pos_args = [Self(context)] + invocation.pos_args  1045         else:  1046             pos_args = invocation.pos_args  1047   1048         # Duplicate the keyword arguments - we remove them in processing below.  1049   1050         kw_args = {}  1051         kw_args.update(invocation.kw_args)  1052   1053         # Sort the arguments into positional and keyword arguments.  1054   1055         params = subprogram.params  1056         items = []  1057         star_args = []  1058   1059         # Match each positional argument, taking excess arguments as star args.  1060   1061         for arg in pos_args:  1062             if params:  1063                 param, default = params[0]  1064                 if arg is None:  1065                     arg = default  1066                 if hasattr(arg, "types"):  1067                     items.append((param, arg.types))  1068                 else:  1069                     items.append((param, [])) # Annotation has not succeeded.  1070                 params = params[1:]  1071             else:  1072                 star_args.append(arg)  1073   1074         # Collect the remaining defaults.  1075   1076         while params:  1077             param, default = params[0]  1078             if kw_args.has_key(param):  1079                 arg = kw_args[param]  1080                 del kw_args[param]  1081             elif default is not None:  1082                 arg = self.dispatch(default)  1083             else:  1084                 raise AnnotationMessage, "No argument supplied in '%s' for parameter '%s'." % (subprogram, param)  1085             if hasattr(arg, "types"):  1086                 items.append((param, arg.types))  1087             else:  1088                 items.append((param, [])) # Annotation has not succeeded.  1089             params = params[1:]  1090   1091         dstar_args = kw_args.items()  1092   1093         # Construct temporary objects.  1094   1095         if star_args:  1096             star_invocation = self.make_star_args(invocation, subprogram, star_args)  1097             self.dispatch(star_invocation)  1098             star_types = star_invocation.types  1099         else:  1100             star_types = None  1101   1102         if dstar_args:  1103             dstar_invocation = self.make_dstar_args(invocation, subprogram, dstar_args)  1104             self.dispatch(dstar_invocation)  1105             dstar_types = dstar_invocation.types  1106         else:  1107             dstar_types = None  1108   1109         # NOTE: Merge the objects properly.  1110   1111         star_types = star_types or invocation.star and invocation.star.types  1112         dstar_types = dstar_types or invocation.dstar and invocation.dstar.types  1113   1114         # Add star and dstar.  1115   1116         if star_types is not None:  1117             if subprogram.star is not None:  1118                 param, default = subprogram.star  1119                 items.append((param, star_types))  1120             else:  1121                 raise AnnotationMessage, "Invocation provides unwanted *args."  1122         elif subprogram.star is not None:  1123             param, default = subprogram.star  1124             if not hasattr(default, "types"):  1125                 subprogram.star = param, self.dispatch(default) # NOTE: Review reprocessing.  1126             items.append((param, default.types))  1127   1128         if dstar_types is not None:  1129             if subprogram.dstar is not None:  1130                 param, default = subprogram.dstar  1131                 items.append((param, dstar_types))  1132             else:  1133                 raise AnnotationMessage, "Invocation provides unwanted **args."  1134         elif subprogram.dstar is not None:  1135             param, default = subprogram.dstar  1136             if not hasattr(default, "types"):  1137                 subprogram.dstar = param, self.dispatch(default) # NOTE: Review reprocessing.  1138             items.append((param, default.types))  1139   1140         # Record the parameter types.  1141   1142         self.annotate_parameters(subprogram, items)  1143         return subprogram.paramtypes.items()  1144   1145     def make_star_args(self, invocation, subprogram, star_args):  1146   1147         "Make a subprogram which initialises a list containing 'star_args'."  1148   1149         if not hasattr(invocation, "stars"):  1150             invocation.stars = {}  1151   1152         if not invocation.stars.has_key(subprogram.full_name()):  1153             code=[  1154                 StoreTemp(  1155                     expr=InvokeFunction(  1156                         expr=LoadAttr(  1157                             expr=LoadRef(  1158                                 ref=self.builtins  1159                                 ),  1160                             name="list",  1161                             nstype="module",  1162                             ),  1163                         args=[],  1164                         star=None,  1165                         dstar=None  1166                         )  1167                     )  1168                 ]  1169   1170             for arg in star_args:  1171                 code.append(  1172                     InvokeFunction(  1173                         expr=LoadAttr(  1174                             expr=LoadTemp(),  1175                             name="append"  1176                             ),  1177                         args=[arg],  1178                         star=None,  1179                         dstar=None  1180                         )  1181                     )  1182   1183             code += [  1184                 Return(expr=LoadTemp(release=1))  1185                 ]  1186   1187             invocation.stars[subprogram.full_name()] = InvokeBlock(  1188                 produces_result=1,  1189                 expr=LoadRef(  1190                     ref=Subprogram(  1191                         name=None,  1192                         returns_value=1,  1193                         params=[],  1194                         star=None,  1195                         dstar=None,  1196                         code=code  1197                         )  1198                     )  1199                 )  1200   1201         return invocation.stars[subprogram.full_name()]  1202   1203     def make_dstar_args(self, invocation, subprogram, dstar_args):  1204   1205         """  1206         Make a subprogram which initialises a dictionary built from the given  1207         'dstar_args'.  1208         """  1209   1210         if not hasattr(invocation, "dstars"):  1211             invocation.dstars = {}  1212   1213         if not invocation.dstars.has_key(subprogram.full_name()):  1214             code=[  1215                 StoreTemp(  1216                     expr=InvokeFunction(  1217                         expr=LoadAttr(  1218                             expr=LoadRef(  1219                                 ref=self.builtins  1220                                 ),  1221                             name="dict",  1222                             nstype="module",  1223                             )  1224                         )  1225                     )  1226                 ]  1227   1228             for arg, value in dstar_args:  1229   1230                 # NOTE: Constant not added to table.  1231   1232                 constant = Constant(name=repr(arg), value=arg, namespace=Namespace())  1233                 #constant.namespace.store("__class__", self.get_builtin_instances(invocation, constant.typename))  1234                 code += [  1235                     StoreTemp(  1236                         expr=LoadRef(  1237                             ref=constant  1238                             ),  1239                         index="const"  1240                         ),  1241                     StoreAttr(  1242                         lvalue=LoadTemp(  1243                             index="const"  1244                             ),  1245                         name="__class__",  1246                         expr=LoadAttr(  1247                             expr=LoadRef(  1248                                 ref=self.builtins  1249                                 ),  1250                             name=constant.typename,  1251                             nstype="module",  1252                             )  1253                         ),  1254                     InvokeFunction(  1255                         expr=LoadAttr(  1256                             expr=LoadTemp(),  1257                             name="__setitem__"  1258                             ),  1259                         args=[  1260                             LoadTemp(  1261                                 index="const",  1262                                 release=1  1263                                 ),  1264                             value  1265                             ]  1266                         )  1267                     ]  1268   1269             code += [  1270                 Return(expr=LoadTemp(release=1))  1271                 ]  1272   1273             invocation.dstars[subprogram.full_name()] = InvokeBlock(  1274                 produces_result=1,  1275                 expr=LoadRef(  1276                     ref=Subprogram(  1277                         name=None,  1278                         returns_value=1,  1279                         params=[],  1280                         star=None,  1281                         dstar=None,  1282                         code=code  1283                         )  1284                     )  1285                 )  1286   1287         return invocation.dstars[subprogram.full_name()]  1288   1289 # Namespace-related abstractions.  1290   1291 class Namespace:  1292   1293     """  1294     A local namespace which may either relate to a genuine set of function  1295     locals or the initialisation of a structure or module.  1296     """  1297   1298     def __init__(self):  1299   1300         """  1301         Initialise the namespace with a mapping of local names to possible  1302         types, a list of return values and of possible returned local  1303         namespaces. The namespace also tracks the "current" types and a mapping  1304         of temporary value names to types.  1305         """  1306   1307         self.names = {}  1308         self.returns = []  1309         self.return_locals = []  1310         self.raises = []  1311         self.temp = {}  1312         self.types = []  1313   1314     def set_types(self, types):  1315   1316         "Set the current collection of 'types'."  1317   1318         self.types = types  1319   1320     def add(self, name, types):  1321   1322         "Add to the entry with the given 'name' the specified 'types'."  1323   1324         if self.names.has_key(name):  1325             combine(self.names[name], types)  1326         else:  1327             self.store(name, types)  1328   1329     def store(self, name, types):  1330   1331         "Store in (or associate with) the given 'name' the specified 'types'."  1332   1333         self.names[name] = types  1334   1335     __setitem__ = store  1336   1337     def load(self, name):  1338   1339         "Load the types associated with the given 'name'."  1340   1341         return self.names[name]  1342   1343     __getitem__ = load  1344   1345     def revoke(self, name, type):  1346   1347         "Revoke from the entry for the given 'name' the specified 'type'."  1348   1349         new_types = self.names[name][:]  1350         new_types.remove(type)  1351         self.names[name] = new_types  1352   1353     def revoke_exception_type(self, type):  1354   1355         "Revoke the given 'type' from the collection of exception types."  1356   1357         self.raises.remove(type)  1358   1359     def revoke_temp_type(self, index, type):  1360   1361         "Revoke from the temporary variable 'index' the given 'type'."  1362   1363         new_types = self.temp[index][-1][:]  1364         new_types.remove(type)  1365         self.temp[index][-1] = new_types  1366   1367     def merge_namespace(self, namespace, everything=1):  1368   1369         """  1370         Merge items from the given 'namespace' with this namespace. When the  1371         optional 'everything' parameter is set to a false value (unlike the  1372         default), return values and locals snapshots will not be copied to this  1373         namespace.  1374         """  1375   1376         self.merge_items(namespace.names.items())  1377         if everything:  1378             combine(self.returns, namespace.returns)  1379             combine(self.return_locals, namespace.return_locals)  1380         combine(self.raises, namespace.raises)  1381         for name, values in namespace.temp.items():  1382             if values:  1383                 if not self.temp.has_key(name) or not self.temp[name]:  1384                     self.temp[name] = [[]]  1385                 combine(self.temp[name][-1], values[-1])  1386   1387     def merge_items(self, items):  1388   1389         "Merge the given 'items' with this namespace."  1390   1391         for name, types in items:  1392             self.merge(name, types)  1393   1394     def merge(self, name, types):  1395   1396         "Merge the entry for the given 'name' and 'types' with this namespace."  1397   1398         if not self.names.has_key(name):  1399             self.names[name] = types[:]  1400         else:  1401             existing = self.names[name]  1402             combine(existing, types)  1403   1404     def snapshot(self):  1405   1406         "Make a snapshot of the locals and remember them."  1407   1408         namespace = Namespace()  1409         namespace.merge_namespace(self)  1410         self.return_locals.append(namespace)  1411   1412     def reset(self):  1413   1414         "Reset a namespace in preparation for merging with returned locals."  1415   1416         self.names = {}  1417   1418     def __repr__(self):  1419         return repr(self.names)  1420   1421 class Importer:  1422   1423     "An import machine, searching for and loading modules."  1424   1425     def __init__(self, path=None):  1426   1427         """  1428         Initialise the importer with the given search 'path' - a list of  1429         directories to search for Python modules.  1430         """  1431   1432         self.path = path or [os.getcwd()]  1433         self.modules = {}  1434   1435     def find_in_path(self, name):  1436   1437         """  1438         Find the given module 'name' in the search path, returning None where no  1439         such module could be found, or a 2-tuple from the 'find' method  1440         otherwise.  1441         """  1442   1443         for d in self.path:  1444             m = self.find(d, name)  1445             if m: return m  1446         return None  1447   1448     def find(self, d, name):  1449   1450         """  1451         In the directory 'd', find the given module 'name', where 'name' can  1452         either refer to a single file module or to a package. Return None if the  1453         'name' cannot be associated with either a file or a package directory,  1454         or a 2-tuple from '_find_package' or '_find_module' otherwise.  1455         """  1456   1457         m = self._find_package(d, name)  1458         if m: return m  1459         m = self._find_module(d, name)  1460         if m: return m  1461         return None  1462   1463     def _find_module(self, d, name):  1464   1465         """  1466         In the directory 'd', find the given module 'name', returning None where  1467         no suitable file exists in the directory, or a 2-tuple consisting of  1468         None (indicating that no package directory is involved) and a filename  1469         indicating the location of the module.  1470         """  1471   1472         name_py = name + os.extsep + "py"  1473         filename = self._find_file(d, name_py)  1474         if filename:  1475             return None, filename  1476         return None  1477   1478     def _find_package(self, d, name):  1479   1480         """  1481         In the directory 'd', find the given package 'name', returning None  1482         where no suitable package directory exists, or a 2-tuple consisting of  1483         a directory (indicating the location of the package directory itself)  1484         and a filename indicating the location of the __init__.py module which  1485         declares the package's top-level contents.  1486         """  1487   1488         filename = self._find_file(d, name)  1489         if filename:  1490             init_py = "__init__" + os.path.extsep + "py"  1491             init_py_filename = self._find_file(filename, init_py)  1492             if init_py_filename:  1493                 return filename, init_py_filename  1494         return None  1495   1496     def _find_file(self, d, filename):  1497   1498         """  1499         Return the filename obtained when searching the directory 'd' for the  1500         given 'filename', or None if no actual file exists for the filename.  1501         """  1502   1503         filename = os.path.join(d, filename)  1504         if os.path.exists(filename):  1505             return filename  1506         else:  1507             return None  1508   1509     def load(self, name, builtins, alias=None):  1510   1511         """  1512         Load the module or package with the given 'name' and using the specified  1513         'builtins'. Return an Attribute object referencing the loaded module or  1514         package, or None if no such module or package exists.  1515         """  1516   1517         path = name.split(".")  1518         m = self.find_in_path(path[0])  1519         if not m:  1520             return None # NOTE: Import error.  1521         d, filename = m  1522         top = module = self.modules.get(path[0], load(filename, builtins, path[0], self))  1523         self.modules[path[0]] = module  1524   1525         if len(path) > 1:  1526             path_so_far = path[:1]  1527             for p in path[1:]:  1528                 path_so_far.append(p)  1529                 m = self.find(d, p)  1530                 if not m:  1531                     return None # NOTE: Import error.  1532                 d, filename = m  1533                 module_name = ".".join(path_so_far)  1534                 submodule = self.modules.get(module_name, load(filename, builtins, module_name, self))  1535                 self.modules[module_name] = submodule  1536   1537                 # Store the submodule within its parent module.  1538   1539                 module.namespace[p] = [Attribute(None, submodule)]  1540                 module = submodule  1541   1542         if alias:  1543             return Attribute(None, module)  1544         else:  1545             return Attribute(None, top)  1546   1547 def combine(target, additions):  1548   1549     """  1550     Merge into the 'target' sequence the given 'additions', preventing duplicate  1551     items.  1552     """  1553   1554     for addition in additions:  1555         if addition not in target:  1556             target.append(addition)  1557   1558 def find_attributes(structure, name):  1559   1560     """  1561     Find for the given 'structure' all attributes for the given 'name', visiting  1562     base classes where appropriate and returning the attributes in order of  1563     descending precedence for all possible base classes.  1564   1565     The elements in the result list are 2-tuples which contain the attribute and  1566     the structure involved in accessing the attribute.  1567     """  1568   1569     # First attempt to search the instance/class namespace.  1570   1571     try:  1572         l = structure.namespace.load(name)  1573         attributes = []  1574         for attribute in l:  1575             attributes.append((attribute, structure))  1576   1577     # If that does not work, attempt to investigate any class or base classes.  1578   1579     except KeyError:  1580         attributes = []  1581   1582         # Investigate any instance's implementing class.  1583   1584         if isinstance(structure, Instance):  1585             for attr in structure.namespace.load("__class__"):  1586                 cls = attr.type  1587                 l = get_attributes(cls, name)  1588                 combine(attributes, l)  1589   1590         # Investigate any class's base classes.  1591   1592         elif isinstance(structure, Class):  1593   1594             # If no base classes exist, return an indicator that no attribute  1595             # exists.  1596   1597             if not structure.base_refs:  1598                 return [(None, structure)]  1599   1600             # Otherwise, find all possible base classes.  1601   1602             for base_refs in structure.base_refs:  1603                 base_attributes = []  1604   1605                 # For each base class, find attributes either in the base  1606                 # class or its own base classes.  1607   1608                 for base_ref in base_refs:  1609                     l = get_attributes(base_ref, name)  1610                     combine(base_attributes, l)  1611   1612                 combine(attributes, base_attributes)  1613   1614     return attributes  1615   1616 def get_attributes(structure, name):  1617   1618     """  1619     Return all possible attributes for the given 'structure' having the given  1620     'name', wrapping each attribute in an Attribute object which includes  1621     context information for the attribute access.  1622   1623     The elements in the result list are 2-tuples which contain the attribute and  1624     the structure involved in accessing the attribute.  1625     """  1626   1627     if isinstance(structure, Attribute):  1628         structure = structure.type  1629     results = []  1630     for attribute, accessor in find_attributes(structure, name):  1631   1632         # Detect class attribute access via instances.  1633   1634         if attribute is not None and isinstance(structure, Instance) and isinstance(accessor, Class):  1635             attribute = accessor.get_attribute_for_instance(attribute, structure)  1636   1637         # Produce an attribute with the appropriate context.  1638   1639         if attribute is not None and isinstance(structure, Structure):  1640             results.append((Attribute(structure, attribute.type), accessor))  1641         else:  1642             results.append((attribute, accessor))  1643   1644     return results  1645   1646 # Convenience functions.  1647   1648 def load(name, builtins=None, module_name=None, importer=None):  1649   1650     """  1651     Load the module with the given 'name' (which may be a full module path),  1652     using the optional 'builtins' to resolve built-in names, and using the  1653     optional 'importer' to provide a means of finding and loading modules.  1654     """  1655   1656     module = simplify.simplify(name, builtins is None, module_name)  1657     fixnames.fix(module, builtins)  1658     annotate(module, builtins, importer)  1659     return module  1660   1661 def annotate(module, builtins=None, importer=None):  1662   1663     """  1664     Annotate the given 'module', also employing the optional 'builtins' module,  1665     if specified. If the optional 'importer' is given, use that to find and load  1666     modules.  1667     """  1668   1669     annotator = Annotator(importer)  1670     if builtins is not None:  1671         annotator.process(module, builtins)  1672     else:  1673         annotator.process(module)  1674   1675 # vim: tabstop=4 expandtab shiftwidth=4