simplify

annotate.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 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, 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, type):   875    876         "For the given 'node', obtain an instance from the given 'type'."   877    878         if not type.has_instance(node):   879             instance = Instance()   880             instance.namespace = Namespace()   881             instance.namespace.store("__class__", [Attribute(None, type)])   882             type.add_instance(node, instance)   883         else:   884             instance = type.get_instance(node)   885    886         return instance   887    888     def invoke_subprogram(self, invoke, attribute):   889    890         """   891         Invoke using the given 'invoke' node the subprogram represented by the   892         given 'attribute'.   893         """   894    895         # Test for context information, making it into a real attribute.   896    897         if attribute.context is not None:   898             context = Attribute(None, attribute.context)   899             target = attribute.type   900         else:   901             context = None   902             target = attribute.type   903    904         # Test to see if anything has changed.   905    906         if hasattr(invoke, "syscount") and invoke.syscount.has_key(target) and invoke.syscount[target] == self.system.count:   907             return   908    909         # Remember the state of the system.   910    911         else:   912             if not hasattr(invoke, "syscount"):   913                 invoke.syscount = {}   914             invoke.syscount[target] = self.system.count   915    916         # Provide the correct namespace for the invocation.   917         # This may be a "shared" namespace...   918    919         if getattr(invoke, "share_locals", 0):   920             namespace = Namespace()   921             namespace.merge_namespace(self.namespace, everything=0)   922             using_module_namespace = self.namespace is self.module.namespace   923    924         # Or it may be a structure...   925    926         elif getattr(target, "structure", None):   927             namespace = Namespace()   928             using_module_namespace = 0   929    930         # Or it may be a new namespace populated with the supplied parameters.   931    932         else:   933             items = self.make_items(invoke, target, context)   934             namespace = Namespace()   935             namespace.merge_items(items)   936             using_module_namespace = 0   937    938             # NOTE: Avoid PEP 227 (nested scopes) whilst permitting references to a   939             # NOTE: subprogram within itself. Do not define the name of the function   940             # NOTE: within a method definition.   941    942             if getattr(target, "name", None) is not None and not getattr(target, "is_method", 0):   943                 namespace.store(target.name, [Attribute(None, target)])   944    945         # Process the subprogram.   946         # In order to keep global accesses working, the module namespace must be   947         # adjusted.   948    949         if using_module_namespace:   950             self.module.namespace = namespace   951    952         self.process_node(target, namespace)   953    954         # NOTE: Improve and verify this.   955         # If the invocation returns a value, acquire the return types.   956    957         if getattr(target, "returns_value", 0):   958             self.namespace.set_types(self.last_returns)   959             self.annotate(invoke)   960    961         # If it is a normal block, merge the locals.   962         # This can happen in addition to the above because for things like   963         # logical expressions, the namespace can be modified whilst values are   964         # returned as results.   965    966         if getattr(invoke, "share_locals", 0):   967             self.namespace.reset()   968    969             # Merge the locals snapshots.   970    971             for locals in self.returned_locals:   972    973                 # For blocks returning values (such as operations), do not merge   974                 # snapshots or results.   975    976                 if getattr(target, "returns_value", 0):   977                     self.namespace.merge_namespace(locals, everything=0)   978    979                 # For blocks not returning values (such as loops), merge   980                 # snapshots and results since they contain details of genuine   981                 # returns.   982    983                 else:   984                     self.namespace.merge_namespace(locals)   985    986         # Incorporate any raised exceptions.   987    988         combine(self.namespace.raises, self.last_raises)   989    990         # In order to keep global accesses working, the module namespace must be   991         # adjusted.   992    993         if using_module_namespace:   994             self.module.namespace = self.namespace   995    996     def process_args(self, invocation):   997    998         """   999         Process the arguments associated with an 'invocation'. Return whether  1000         any arguments were processed.  1001         """  1002   1003         invocation.pos_args = self.dispatches(invocation.pos_args)  1004         invocation.kw_args = self.dispatch_dict(invocation.kw_args)  1005   1006         # Get type information for star and dstar arguments.  1007   1008         if invocation.star is not None:  1009             param, default = invocation.star  1010             default = self.dispatch(default)  1011             invocation.star = param, default  1012   1013         if invocation.dstar is not None:  1014             param, default = invocation.dstar  1015             default = self.dispatch(default)  1016             invocation.dstar = param, default  1017   1018         if invocation.pos_args or invocation.kw_args or invocation.star or invocation.dstar:  1019             return 1  1020         else:  1021             return 0  1022   1023     def make_items(self, invocation, subprogram, context):  1024   1025         """  1026         Make an items mapping for the 'invocation' of the 'subprogram' using the  1027         given 'context' (which may be None).  1028         """  1029   1030         if context is not None:  1031             pos_args = [Self(context)] + invocation.pos_args  1032         else:  1033             pos_args = invocation.pos_args  1034   1035         # Duplicate the keyword arguments - we remove them in processing below.  1036   1037         kw_args = {}  1038         kw_args.update(invocation.kw_args)  1039   1040         # Sort the arguments into positional and keyword arguments.  1041   1042         params = subprogram.params  1043         items = []  1044         star_args = []  1045   1046         # Match each positional argument, taking excess arguments as star args.  1047   1048         for arg in pos_args:  1049             if params:  1050                 param, default = params[0]  1051                 if arg is None:  1052                     arg = default  1053                 if hasattr(arg, "types"):  1054                     items.append((param, arg.types))  1055                 else:  1056                     items.append((param, [])) # Annotation has not succeeded.  1057                 params = params[1:]  1058             else:  1059                 star_args.append(arg)  1060   1061         # Collect the remaining defaults.  1062   1063         while params:  1064             param, default = params[0]  1065             if kw_args.has_key(param):  1066                 arg = kw_args[param]  1067                 del kw_args[param]  1068             elif default is not None:  1069                 arg = self.dispatch(default)  1070             else:  1071                 raise AnnotationMessage, "No argument supplied in '%s' for parameter '%s'." % (subprogram, param)  1072             if hasattr(arg, "types"):  1073                 items.append((param, arg.types))  1074             else:  1075                 items.append((param, [])) # Annotation has not succeeded.  1076             params = params[1:]  1077   1078         dstar_args = kw_args.items()  1079   1080         # Construct temporary objects.  1081   1082         if star_args:  1083             star_invocation = self.make_star_args(invocation, subprogram, star_args)  1084             self.dispatch(star_invocation)  1085             star_types = star_invocation.types  1086         else:  1087             star_types = None  1088   1089         if dstar_args:  1090             dstar_invocation = self.make_dstar_args(invocation, subprogram, dstar_args)  1091             self.dispatch(dstar_invocation)  1092             dstar_types = dstar_invocation.types  1093         else:  1094             dstar_types = None  1095   1096         # NOTE: Merge the objects properly.  1097   1098         star_types = star_types or invocation.star and invocation.star.types  1099         dstar_types = dstar_types or invocation.dstar and invocation.dstar.types  1100   1101         # Add star and dstar.  1102   1103         if star_types is not None:  1104             if subprogram.star is not None:  1105                 param, default = subprogram.star  1106                 items.append((param, star_types))  1107             else:  1108                 raise AnnotationMessage, "Invocation provides unwanted *args."  1109         elif subprogram.star is not None:  1110             param, default = subprogram.star  1111             if not hasattr(default, "types"):  1112                 subprogram.star = param, self.dispatch(default) # NOTE: Review reprocessing.  1113             items.append((param, default.types))  1114   1115         if dstar_types is not None:  1116             if subprogram.dstar is not None:  1117                 param, default = subprogram.dstar  1118                 items.append((param, dstar_types))  1119             else:  1120                 raise AnnotationMessage, "Invocation provides unwanted **args."  1121         elif subprogram.dstar is not None:  1122             param, default = subprogram.dstar  1123             if not hasattr(default, "types"):  1124                 subprogram.dstar = param, self.dispatch(default) # NOTE: Review reprocessing.  1125             items.append((param, default.types))  1126   1127         # Record the parameter types.  1128   1129         self.annotate_parameters(subprogram, items)  1130         return subprogram.paramtypes.items()  1131   1132     def make_star_args(self, invocation, subprogram, star_args):  1133   1134         "Make a subprogram which initialises a list containing 'star_args'."  1135   1136         if not hasattr(invocation, "stars"):  1137             invocation.stars = {}  1138   1139         if not invocation.stars.has_key(subprogram.full_name()):  1140             code=[  1141                 StoreTemp(  1142                     expr=InvokeFunction(  1143                         invocation.original,  1144                         expr=LoadAttr(  1145                             expr=LoadRef(  1146                                 ref=self.builtins  1147                                 ),  1148                             name="list",  1149                             nstype="module",  1150                             ),  1151                         args=[],  1152                         star=None,  1153                         dstar=None  1154                         )  1155                     )  1156                 ]  1157   1158             for arg in star_args:  1159                 code.append(  1160                     InvokeFunction(  1161                         invocation.original,  1162                         expr=LoadAttr(  1163                             expr=LoadTemp(),  1164                             name="append"  1165                             ),  1166                         args=[arg],  1167                         star=None,  1168                         dstar=None  1169                         )  1170                     )  1171   1172             code += [  1173                 Return(expr=LoadTemp(release=1))  1174                 ]  1175   1176             invocation.stars[subprogram.full_name()] = InvokeBlock(  1177                 invocation.original,  1178                 produces_result=1,  1179                 expr=LoadRef(  1180                     ref=Subprogram(  1181                         name=None,  1182                         returns_value=1,  1183                         params=[],  1184                         star=None,  1185                         dstar=None,  1186                         code=code  1187                         )  1188                     )  1189                 )  1190   1191         return invocation.stars[subprogram.full_name()]  1192   1193     def make_dstar_args(self, invocation, subprogram, dstar_args):  1194   1195         """  1196         Make a subprogram which initialises a dictionary built from the given  1197         'dstar_args'.  1198         """  1199   1200         if not hasattr(invocation, "dstars"):  1201             invocation.dstars = {}  1202   1203         if not invocation.dstars.has_key(subprogram.full_name()):  1204             code=[  1205                 StoreTemp(  1206                     expr=InvokeFunction(  1207                         invocation.original,  1208                         expr=LoadAttr(  1209                             expr=LoadRef(  1210                                 ref=self.builtins  1211                                 ),  1212                             name="dict",  1213                             nstype="module",  1214                             )  1215                         )  1216                     )  1217                 ]  1218   1219             for arg, value in dstar_args:  1220   1221                 # NOTE: Constant not added to table.  1222   1223                 constant = Constant(name=repr(arg), value=arg, namespace=Namespace())  1224                 #constant.namespace.store("__class__", self.get_builtin_instances(invocation, constant.typename))  1225                 code += [  1226                     StoreTemp(  1227                         expr=LoadRef(  1228                             ref=constant  1229                             ),  1230                         index="const"  1231                         ),  1232                     StoreAttr(  1233                         lvalue=LoadTemp(  1234                             index="const"  1235                             ),  1236                         name="__class__",  1237                         expr=LoadAttr(  1238                             expr=LoadRef(  1239                                 ref=self.builtins  1240                                 ),  1241                             name=constant.typename,  1242                             nstype="module",  1243                             )  1244                         ),  1245                     InvokeFunction(  1246                         invocation.original,  1247                         expr=LoadAttr(  1248                             expr=LoadTemp(),  1249                             name="__setitem__"  1250                             ),  1251                         args=[  1252                             LoadTemp(  1253                                 index="const",  1254                                 release=1  1255                                 ),  1256                             value  1257                             ]  1258                         )  1259                     ]  1260   1261             code += [  1262                 Return(expr=LoadTemp(release=1))  1263                 ]  1264   1265             invocation.dstars[subprogram.full_name()] = InvokeBlock(  1266                 invocation.original,  1267                 produces_result=1,  1268                 expr=LoadRef(  1269                     ref=Subprogram(  1270                         name=None,  1271                         returns_value=1,  1272                         params=[],  1273                         star=None,  1274                         dstar=None,  1275                         code=code  1276                         )  1277                     )  1278                 )  1279   1280         return invocation.dstars[subprogram.full_name()]  1281   1282 # Namespace-related abstractions.  1283   1284 class Namespace:  1285   1286     """  1287     A local namespace which may either relate to a genuine set of function  1288     locals or the initialisation of a structure or module.  1289     """  1290   1291     def __init__(self):  1292   1293         """  1294         Initialise the namespace with a mapping of local names to possible  1295         types, a list of return values and of possible returned local  1296         namespaces. The namespace also tracks the "current" types and a mapping  1297         of temporary value names to types.  1298         """  1299   1300         self.names = {}  1301         self.returns = []  1302         self.return_locals = []  1303         self.raises = []  1304         self.temp = {}  1305         self.types = []  1306   1307     def set_types(self, types):  1308   1309         "Set the current collection of 'types'."  1310   1311         self.types = types  1312   1313     def add(self, name, types):  1314   1315         "Add to the entry with the given 'name' the specified 'types'."  1316   1317         if self.names.has_key(name):  1318             combine(self.names[name], types)  1319         else:  1320             self.store(name, types)  1321   1322     def store(self, name, types):  1323   1324         "Store in (or associate with) the given 'name' the specified 'types'."  1325   1326         self.names[name] = types  1327   1328     __setitem__ = store  1329   1330     def load(self, name):  1331   1332         "Load the types associated with the given 'name'."  1333   1334         return self.names[name]  1335   1336     __getitem__ = load  1337   1338     def revoke(self, name, type):  1339   1340         "Revoke from the entry for the given 'name' the specified 'type'."  1341   1342         new_types = self.names[name][:]  1343         new_types.remove(type)  1344         self.names[name] = new_types  1345   1346     def revoke_exception_type(self, type):  1347   1348         "Revoke the given 'type' from the collection of exception types."  1349   1350         self.raises.remove(type)  1351   1352     def revoke_temp_type(self, index, type):  1353   1354         "Revoke from the temporary variable 'index' the given 'type'."  1355   1356         new_types = self.temp[index][-1][:]  1357         new_types.remove(type)  1358         self.temp[index][-1] = new_types  1359   1360     def merge_namespace(self, namespace, everything=1):  1361   1362         """  1363         Merge items from the given 'namespace' with this namespace. When the  1364         optional 'everything' parameter is set to a false value (unlike the  1365         default), return values and locals snapshots will not be copied to this  1366         namespace.  1367         """  1368   1369         self.merge_items(namespace.names.items())  1370         if everything:  1371             combine(self.returns, namespace.returns)  1372             combine(self.return_locals, namespace.return_locals)  1373         combine(self.raises, namespace.raises)  1374         for name, values in namespace.temp.items():  1375             if values:  1376                 if not self.temp.has_key(name) or not self.temp[name]:  1377                     self.temp[name] = [[]]  1378                 combine(self.temp[name][-1], values[-1])  1379   1380     def merge_items(self, items):  1381   1382         "Merge the given 'items' with this namespace."  1383   1384         for name, types in items:  1385             self.merge(name, types)  1386   1387     def merge(self, name, types):  1388   1389         "Merge the entry for the given 'name' and 'types' with this namespace."  1390   1391         if not self.names.has_key(name):  1392             self.names[name] = types[:]  1393         else:  1394             existing = self.names[name]  1395             combine(existing, types)  1396   1397     def snapshot(self):  1398   1399         "Make a snapshot of the locals and remember them."  1400   1401         namespace = Namespace()  1402         namespace.merge_namespace(self)  1403         self.return_locals.append(namespace)  1404   1405     def reset(self):  1406   1407         "Reset a namespace in preparation for merging with returned locals."  1408   1409         self.names = {}  1410   1411     def __repr__(self):  1412         return repr(self.names)  1413   1414 class Importer:  1415   1416     "An import machine, searching for and loading modules."  1417   1418     def __init__(self, path=None):  1419   1420         """  1421         Initialise the importer with the given search 'path' - a list of  1422         directories to search for Python modules.  1423         """  1424   1425         self.path = path or [os.getcwd()]  1426         self.modules = {}  1427   1428     def find_in_path(self, name):  1429   1430         """  1431         Find the given module 'name' in the search path, returning None where no  1432         such module could be found, or a 2-tuple from the 'find' method  1433         otherwise.  1434         """  1435   1436         for d in self.path:  1437             m = self.find(d, name)  1438             if m: return m  1439         return None  1440   1441     def find(self, d, name):  1442   1443         """  1444         In the directory 'd', find the given module 'name', where 'name' can  1445         either refer to a single file module or to a package. Return None if the  1446         'name' cannot be associated with either a file or a package directory,  1447         or a 2-tuple from '_find_package' or '_find_module' otherwise.  1448         """  1449   1450         m = self._find_package(d, name)  1451         if m: return m  1452         m = self._find_module(d, name)  1453         if m: return m  1454         return None  1455   1456     def _find_module(self, d, name):  1457   1458         """  1459         In the directory 'd', find the given module 'name', returning None where  1460         no suitable file exists in the directory, or a 2-tuple consisting of  1461         None (indicating that no package directory is involved) and a filename  1462         indicating the location of the module.  1463         """  1464   1465         name_py = name + os.extsep + "py"  1466         filename = self._find_file(d, name_py)  1467         if filename:  1468             return None, filename  1469         return None  1470   1471     def _find_package(self, d, name):  1472   1473         """  1474         In the directory 'd', find the given package 'name', returning None  1475         where no suitable package directory exists, or a 2-tuple consisting of  1476         a directory (indicating the location of the package directory itself)  1477         and a filename indicating the location of the __init__.py module which  1478         declares the package's top-level contents.  1479         """  1480   1481         filename = self._find_file(d, name)  1482         if filename:  1483             init_py = "__init__" + os.path.extsep + "py"  1484             init_py_filename = self._find_file(filename, init_py)  1485             if init_py_filename:  1486                 return filename, init_py_filename  1487         return None  1488   1489     def _find_file(self, d, filename):  1490   1491         """  1492         Return the filename obtained when searching the directory 'd' for the  1493         given 'filename', or None if no actual file exists for the filename.  1494         """  1495   1496         filename = os.path.join(d, filename)  1497         if os.path.exists(filename):  1498             return filename  1499         else:  1500             return None  1501   1502     def load(self, name, builtins, alias=None):  1503   1504         """  1505         Load the module or package with the given 'name' and using the specified  1506         'builtins'. Return an Attribute object referencing the loaded module or  1507         package, or None if no such module or package exists.  1508         """  1509   1510         path = name.split(".")  1511         m = self.find_in_path(path[0])  1512         if not m:  1513             return None # NOTE: Import error.  1514         d, filename = m  1515         top = module = self.modules.get(path[0], load(filename, builtins, path[0], self))  1516         self.modules[path[0]] = module  1517   1518         if len(path) > 1:  1519             path_so_far = path[:1]  1520             for p in path[1:]:  1521                 path_so_far.append(p)  1522                 m = self.find(d, p)  1523                 if not m:  1524                     return None # NOTE: Import error.  1525                 d, filename = m  1526                 module_name = ".".join(path_so_far)  1527                 submodule = self.modules.get(module_name, load(filename, builtins, module_name, self))  1528                 self.modules[module_name] = submodule  1529   1530                 # Store the submodule within its parent module.  1531   1532                 module.namespace[p] = [Attribute(None, submodule)]  1533                 module = submodule  1534   1535         if alias:  1536             return Attribute(None, module)  1537         else:  1538             return Attribute(None, top)  1539   1540 def combine(target, additions):  1541   1542     """  1543     Merge into the 'target' sequence the given 'additions', preventing duplicate  1544     items.  1545     """  1546   1547     for addition in additions:  1548         if addition not in target:  1549             target.append(addition)  1550   1551 def find_attributes(structure, name):  1552   1553     """  1554     Find for the given 'structure' all attributes for the given 'name', visiting  1555     base classes where appropriate and returning the attributes in order of  1556     descending precedence for all possible base classes.  1557   1558     The elements in the result list are 2-tuples which contain the attribute and  1559     the structure involved in accessing the attribute.  1560     """  1561   1562     # First attempt to search the instance/class namespace.  1563   1564     try:  1565         l = structure.namespace.load(name)  1566         attributes = []  1567         for attribute in l:  1568             attributes.append((attribute, structure))  1569   1570     # If that does not work, attempt to investigate any class or base classes.  1571   1572     except KeyError:  1573         attributes = []  1574   1575         # Investigate any instance's implementing class.  1576   1577         if isinstance(structure, Instance):  1578             for attr in structure.namespace.load("__class__"):  1579                 cls = attr.type  1580                 l = get_attributes(cls, name)  1581                 combine(attributes, l)  1582   1583         # Investigate any class's base classes.  1584   1585         elif isinstance(structure, Class):  1586   1587             # If no base classes exist, return an indicator that no attribute  1588             # exists.  1589   1590             if not structure.base_refs:  1591                 return [(None, structure)]  1592   1593             # Otherwise, find all possible base classes.  1594   1595             for base_refs in structure.base_refs:  1596                 base_attributes = []  1597   1598                 # For each base class, find attributes either in the base  1599                 # class or its own base classes.  1600   1601                 for base_ref in base_refs:  1602                     l = get_attributes(base_ref, name)  1603                     combine(base_attributes, l)  1604   1605                 combine(attributes, base_attributes)  1606   1607     return attributes  1608   1609 def get_attributes(structure, name):  1610   1611     """  1612     Return all possible attributes for the given 'structure' having the given  1613     'name', wrapping each attribute in an Attribute object which includes  1614     context information for the attribute access.  1615   1616     The elements in the result list are 2-tuples which contain the attribute and  1617     the structure involved in accessing the attribute.  1618     """  1619   1620     if isinstance(structure, Attribute):  1621         structure = structure.type  1622     results = []  1623     for attribute, accessor in find_attributes(structure, name):  1624   1625         # Detect class attribute access via instances.  1626   1627         if attribute is not None and isinstance(structure, Instance) and isinstance(accessor, Class):  1628             attribute = accessor.get_attribute_for_instance(attribute, structure)  1629   1630         # Produce an attribute with the appropriate context.  1631   1632         if attribute is not None and isinstance(structure, Structure):  1633             results.append((Attribute(structure, attribute.type), accessor))  1634         else:  1635             results.append((attribute, accessor))  1636   1637     return results  1638   1639 # Convenience functions.  1640   1641 def load(name, builtins=None, module_name=None, importer=None):  1642   1643     """  1644     Load the module with the given 'name' (which may be a full module path),  1645     using the optional 'builtins' to resolve built-in names, and using the  1646     optional 'importer' to provide a means of finding and loading modules.  1647     """  1648   1649     module = simplify.simplify(name, builtins is None, module_name)  1650     fixnames.fix(module, builtins)  1651     annotate(module, builtins, importer)  1652     return module  1653   1654 def annotate(module, builtins=None, importer=None):  1655   1656     """  1657     Annotate the given 'module', also employing the optional 'builtins' module,  1658     if specified. If the optional 'importer' is given, use that to find and load  1659     modules.  1660     """  1661   1662     annotator = Annotator(importer)  1663     if builtins is not None:  1664         annotator.process(module, builtins)  1665     else:  1666         annotator.process(module)  1667   1668 # vim: tabstop=4 expandtab shiftwidth=4