#!/usr/bin/env python  """ Annotate program node structures. The code in this module operates upon nodes which are produced when simplifying AST node trees originating from the compiler module.  Copyright (C) 2006, 2007 Paul Boddie <paul@boddie.org.uk>  This software is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.  This software is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more details.  You should have received a copy of the GNU General Public License along with this library; see the file LICENCE.txt If not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA  --------  To use this module, the easiest approach is to use the load function:  load(filename, builtins)  To control module importing, an importer should be constructed and employed. Here, the standard path for module searching is used:  importer = Importer(sys.path) load(filename, builtins, importer)  Underneath the load function, the annotate function provides support for annotating modules already processed by simplify and fixnames:  annotate(module, builtins)  And at the most basic level, the most intricate approach involves obtaining an Annotator object:  annotator = Annotator()  Then, processing an existing module with it:  annotator.process(module)  If a module containing built-in classes and functions has already been annotated, such a module should be passed in as an additional argument:  annotator.process(module, builtins) """  from simplified import * import simplify, fixnames # for the load function import compiler import os  class System:      """     A class maintaining the state of the annotation system. When the system     counter can no longer be incremented by any annotation operation, the     system may be considered stable and fully annotated.     """      def __init__(self):         self.count = 0      def init(self, node):          "Initialise a 'node' for annotation."          if not hasattr(node, "types"):             node.types = []      def annotate(self, node, types):          "Annotate the given 'node' with the given 'types'."          self.init(node)         self.combine(node.types, types)      def combine(self, target, types):          """         Combine the 'target' list with the given 'types', counting new members.         """          for type in types:             if type not in target:                 target.append(type)                 self.count += 1  system = System()  # Exceptions.  class AnnotationError(SimplifiedError):      "An error in the annotation process."      pass  class AnnotationMessage(Exception):      "A lesser annotation error."      pass  # Annotation.  class Annotator(Visitor):      """     The type annotator which traverses the program nodes, typically depth-first,     and maintains a record of the current set of types applying to the currently     considered operation. Such types are also recorded on the nodes, and a     special "system" record is maintained to monitor the level of annotation     activity with a view to recognising when no more annotations are possible.      Throughout the annotation activity, type information consists of lists of     Attribute objects where such objects retain information about the context of     the type (since a value in the program may be associated with an object or     class) and the actual type of the value being manipulated. Upon accessing     attribute information on namespaces, additional accessor information is also     exchanged - this provides a means of distinguishing between the different     types possible when the means of constructing the namespace may depend on     run-time behaviour.      Covered: Assign, CheckExc, Conditional, Global, Import, InvokeBlock,              InvokeFunction, LoadAttr, LoadExc, LoadName, LoadRef, LoadTemp,              Module, Not, Pass, Raise, ReleaseTemp, ReturnFromBlock,              ReturnFromFunction, StoreAttr, StoreName, StoreTemp, Subprogram,              Try.     """      def __init__(self, importer=None):          "Initialise the visitor with an optional 'importer'."          Visitor.__init__(self)         self.system = system         self.importer = importer or Importer()          # Satisfy visitor issues.          self.visitor = self      def process(self, module, builtins=None):          """         Process the given 'module', using the optional 'builtins' to access         built-in classes and functions.         """          self.subprograms = []         self.current_subprograms = []         self.current_namespaces = []         self.namespace = None         self.module = module          # Give constants their own namespace.          for value, constant in module.simplifier.constants.items():             constant.namespace = Namespace()          # Process the module, supplying builtins if possible.          self.builtins = builtins         self.global_namespace = Namespace()          if builtins is not None:             self.builtins_namespace = builtins.namespace         else:             self.builtins_namespace = self.global_namespace          return self.process_node(module, self.global_namespace)      def process_node(self, node, locals):          """         Process a subprogram or module 'node', indicating the initial 'locals'.         Return an annotated subprogram or module. Note that this method may         mutate nodes in the original program.         """          # Record the current subprogram and namespace.          self.current_subprograms.append(node)          # Determine the namespace.          self.current_namespaces.append(self.namespace)         self.namespace = locals          # Add namespace details to any structure involved.          if getattr(node, "structure", None) is not None:             node.structure.namespace = Namespace()              # Initialise bases where appropriate.              if hasattr(node.structure, "bases"):                 base_refs = []                 for base in node.structure.bases:                     self.dispatch(base)                     base_refs.append(self.namespace.types)                 node.structure.base_refs = base_refs          # Dispatch to the code itself.          node.namespace = self.namespace         result = self.dispatch(node)         result.namespace = self.namespace          # Obtain the return values.          self.last_returns = self.namespace.returns         self.last_raises = self.namespace.raises         self.returned_locals = self.namespace.return_locals          # Restore the previous subprogram and namespace.          self.namespace = self.current_namespaces.pop()         self.current_subprograms.pop()          return result      def annotate(self, node, types=None):          """         Annotate the given 'node' in the system, using either the optional         'types' or the namespace's current type information.         """          self.system.annotate(node, types or self.namespace.types)      def annotate_parameters(self, node, items):          """         Annotate the given 'node' using the given 'items' and updating the         system's annotation counter.         """          if not hasattr(node, "paramtypes"):             node.paramtypes = {}          for param, types in items:             if not node.paramtypes.has_key(param):                 node.paramtypes[param] = []             self.system.combine(node.paramtypes[param], types)      # Visitor methods.      def default(self, node):          """         Process the given 'node', given that it does not have a specific         handler.         """          raise AnnotationMessage, "Node '%s' not supported." % node      def dispatch(self, node, *args):         try:             return Visitor.dispatch(self, node, *args)         except AnnotationError, exc:             exc.add(node)             raise         except AnnotationMessage, exc:             raise AnnotationError(exc, node)      # Specific node methods.      def visitAssign(self, assign):          """         Return the 'assign' node whose contents (merely a group of nodes) have         been processed.         """          assign.code = self.dispatches(assign.code)         return assign      def visitCheckExc(self, checkexc):          """         Return the 'checkexc' node, processing the expression to find the         possible types of the exception, and processing each choice to build a         list of checked types for the exception.         """          checkexc.expr = self.dispatch(checkexc.expr)         expr_types = self.namespace.types         choice_types = []         choices = []         for choice in checkexc.choices:             choices.append(self.dispatch(choice))             choice_types += self.namespace.types         for expr_type in expr_types:             if expr_type.type.get_class() not in choice_types:                 self._prune_non_accesses(checkexc.expr, expr_type)         return checkexc      def visitConditional(self, conditional):          """         Return the 'conditional' node, processing the test, body and else         clauses and recording their processed forms. The body and else clauses         are processed within their own namespaces, and the test is also         processed in its own namespace if 'isolate_test' is set on the         'conditional' node.         """          # Conditionals keep local namespace changes isolated.         # With Return nodes inside the body/else sections, the changes are         # communicated to the caller.          is_module = self.namespace is self.module.namespace          # Where the test is closely associated with the body, save the namespace         # before entering the test.          if conditional.isolate_test:             saved_namespace = self.namespace             self.namespace = Namespace()             if is_module:                 self.module.namespace = self.namespace             self.namespace.merge_namespace(saved_namespace)          conditional.test = self.dispatch(conditional.test)          # Where the test may affect the body and the else clause, save the         # namespace after processing the test.          if not conditional.isolate_test:             saved_namespace = self.namespace             self.namespace = Namespace()             if is_module:                 self.module.namespace = self.namespace             self.namespace.merge_namespace(saved_namespace)          # Process the body clause.          conditional.body = self.dispatches(conditional.body)         body_namespace = self.namespace          # Use the saved namespace as a template for the else clause.          self.namespace = Namespace()         if is_module:             self.module.namespace = self.namespace         self.namespace.merge_namespace(saved_namespace)          # Process the else clause.          conditional.else_ = self.dispatches(conditional.else_)         else_namespace = self.namespace          # Merge the body and else namespaces.          self.namespace = Namespace()         if is_module:             self.module.namespace = self.namespace         self.namespace.merge_namespace(body_namespace)         self.namespace.merge_namespace(else_namespace)          # NOTE: Test of exception type pruning based on the test/body.          if conditional.isolate_test:             for exc_type in body_namespace.raises:                 self.namespace.revoke_exception_type(exc_type)          return conditional      def visitGlobal(self, global_):          """         Return the 'global_' node unprocessed since namespaces should have         already been altered to take global names into consideration.         """          return global_      def visitImport(self, import_):          """         Return the 'import_' node, importing the module with the stated name         and storing details on the node.         """          module = self.importer.load(import_.name, self.builtins, getattr(import_, "alias", None))         if module is not None:             self.namespace.set_types([module])         else:             self.namespace.set_types([])         self.annotate(import_) # mainly for viewing purposes         return import_      def _visitInvoke(self, invoke, invocation_types, have_args):          """         Return the processed 'invoke' node, using the given 'invocation_types'         as the list of callables to be investigated for instantiation or for the         invocation of functions or blocks. If 'have_args' is a true value, any         invocation or instantiation will involve arguments.         """          # Now locate and invoke the subprogram. This can be complicated because         # the target may be a class or object, and there may be many different         # related subprograms.          invocations = []          # Visit each callable in turn, finding subprograms.          for attr in invocation_types:              # Deal with class invocations by providing instance objects.             # Here, each class is queried for the __init__ method, which may             # exist for some combinations of classes in a hierarchy but not for             # others.              if isinstance(attr.type, Class):                 attributes = get_attributes(attr.type, "__init__")              # Deal with object invocations by using __call__ methods.              elif isinstance(attr.type, Instance):                 attributes = get_attributes(attr.type, "__call__")              # Normal functions or methods are more straightforward.             # Here, we model them using an attribute with no context and with             # no associated accessor.              else:                 attributes = [(attr, None)]              # Inspect each attribute and extract the subprogram.              for attribute, accessor in attributes:                  # If a class is involved, presume that it must create a new                 # object.                  if isinstance(attr.type, Class):                      # Instantiate the class.                      instance = self.new_instance(invoke, attr.type)                      # For instantiations, switch the context.                      if attribute is not None:                         attribute = Attribute(instance, attribute.type)                  # Skip cases where no callable is found.                  if attribute is not None:                      # If a subprogram is defined, invoke it.                      self.invoke_subprogram(invoke, attribute)                     if attribute.type not in invocations:                         invocations.append(attribute.type)                  elif not isinstance(attr.type, Class):                     print "Invocation type is None for", accessor                  else:                      # Test to see if no arguments were supplied in cases where no                     # initialiser was found.                      if have_args:                         raise AnnotationMessage, "No initialiser found for '%s' with arguments." % attr.type              # Special case: initialisation.              if isinstance(attr.type, Class):                  # Associate the instance with the result of this invocation.                  self.namespace.set_types([Attribute(None, instance)])                 self.annotate(invoke)          # Remember the invocations that were found, along with the return type         # information.          invoke.invocations = invocations         self.namespace.set_types(getattr(invoke, "types", []))         return invoke      def visitInvokeBlock(self, invoke):          """         Return the processed 'invoke' node, first finding the callables         indicated by the expression.         """          invoke.expr = self.dispatch(invoke.expr)         invocation_types = self.namespace.types         return self._visitInvoke(invoke, invocation_types, have_args=0)      def visitInvokeFunction(self, invoke):          """         Return the processed 'invoke' node, first finding the callables         indicated by the expression.         """          invoke.expr = self.dispatch(invoke.expr)         invocation_types = self.namespace.types          # Invocation processing starts with making sure that the arguments have         # been processed.          return self._visitInvoke(invoke, invocation_types, have_args=self.process_args(invoke))      def visitLoadAttr(self, loadattr):          """         Return the 'loadattr' node, processing and storing the expression, and         using the expression's types to construct records of accesses and         non-accesses using the stated attribute name.         """          loadattr.expr = self.dispatch(loadattr.expr)         types = []         non_accesses = []         accesses = {}         for attr in self.namespace.types:             attributes = get_attributes(attr.type, loadattr.name)             if not attributes:                 if not attr in non_accesses:                     non_accesses.append(attr)                     combine(self.namespace.raises, self.get_builtin_instances(loadattr, "AttributeError"))                      # Revoke this type from any name involved.                      self._prune_non_accesses(loadattr.expr, attr)              for attribute, accessor in attributes:                 if attribute is not None:                     types.append(attribute)                     if not accesses.has_key(attr.type):                         accesses[attr.type] = []                     if not (attribute, accessor) in accesses[attr.type]:                         accesses[attr.type].append((attribute, accessor))                 else:                     if not attr in non_accesses:                         non_accesses.append(attr)                         combine(self.namespace.raises, self.get_builtin_instances(loadattr, "AttributeError"))                          # Revoke this type from any name involved.                          self._prune_non_accesses(loadattr.expr, attr)          if not types:             print "No attribute found for", loadattr.name, "given", self.namespace.types         self.namespace.set_types(types)         loadattr.non_accesses = non_accesses         loadattr.accesses = accesses         self.annotate(loadattr)         return loadattr      def _prune_non_accesses(self, expr, attr):          """         Prune type information from 'expr' where the given 'attr' has been         shown to be a non-access.         """          if isinstance(expr, LoadName):             self.namespace.revoke(expr.name, attr)         elif isinstance(expr, LoadExc):             self.namespace.revoke_exception_type(attr)         elif isinstance(expr, LoadTemp):             self.namespace.revoke_temp_type(getattr(expr, "index", None), attr)          # LoadAttr cannot be pruned since this might unintentionally prune         # legitimate types from other applications of the referenced type, it         # almost certainly doesn't take "concurrent" mutation into         # consideration (where in a running program, the pruned type is actually         # reintroduced, making the pruning invalid), and there is no easy way of         # preserving the meaning of a namespace without either creating lots of         # specialised instances, and even then...          #elif isinstance(expr, LoadAttr):         #    for expr_attr in expr.expr.types:         #        if hasattr(expr_attr.type, "namespace"):         #            expr_attr.type.namespace.revoke(expr.name, attr)      def visitLoadExc(self, loadexc):          """         Return the 'loadexc' node, discovering the possible exception types         raised.         """          self.namespace.set_types(self.namespace.raises[:])         self.annotate(loadexc)         return loadexc      def visitLoadName(self, loadname):          """         Return the 'loadname' node, processing the name information on the node         to determine which types are involved with the name.         """          self.namespace.set_types(self.namespace.load(loadname.name))         result = loadname         self.annotate(result)         return result      def visitLoadRef(self, loadref):          """         Return the 'loadref' node, obtaining type information about the         reference stated on the node.         """          self.namespace.set_types([Attribute(None, loadref.ref)])         self.annotate(loadref)         return loadref      def visitLoadTemp(self, loadtemp):          """         Return the 'loadtemp' node, obtaining type information about the         temporary variable accessed, and removing variable information where the         'release' attribute has been set on the node.         """          index = getattr(loadtemp, "index", None)         try:             if getattr(loadtemp, "release", 0):                 self.namespace.set_types(self.namespace.temp[index].pop())             else:                 self.namespace.set_types(self.namespace.temp[index][-1])         except KeyError:             raise AnnotationMessage, "Temporary store index '%s' not defined." % index         self.annotate(loadtemp)         return loadtemp      def visitModule(self, module):          """         Return the processed 'module' whose contents (merely a group of nodes)         are processed.         """          module.code = self.dispatches(module.code)         return module      def visitNot(self, not_):          "Return the 'not_' node whose expression is processed."          not_.expr = self.dispatch(not_.expr)         return not_      def visitPass(self, pass_):          "Return the unprocessed 'pass_' node."          return pass_      def visitRaise(self, raise_):          """         Return the 'raise_' node, processing any traceback information along         with the raised exception expression, converting the node into a kind of         invocation where the expression is found not to be an invocation itself.         This node affects the namespace, adding exception types to the list of         those raised in the namespace.         """          if getattr(raise_, "traceback", None) is not None:             raise_.traceback = self.dispatch(raise_.traceback)         raise_.expr = self.dispatch(raise_.expr)          # Handle bare name exceptions by converting any classes to instances.          if not isinstance(raise_.expr, InvokeFunction):             raise_.pos_args = []             raise_.kw_args = {}             raise_.star = None             raise_.dstar = None             types = []             for attr in self.namespace.types:                 if isinstance(attr.type, Class):                     self._visitInvoke(raise_, [attr], have_args=0)                 types += self.namespace.types         else:             types = self.namespace.types                      combine(self.namespace.raises, types)         return raise_      def visitReleaseTemp(self, releasetemp):          """         Return the 'releasetemp' node, removing temporary variable information         from the current namespace.         """          index = getattr(releasetemp, "index", None)         try:             self.namespace.temp[index].pop()         except KeyError:             raise AnnotationMessage, "Temporary store index '%s' not defined." % index         except IndexError:             pass #raise AnnotationMessage, "Temporary store index '%s' is empty." % index         return releasetemp      def visitReturn(self, return_):          """         Return the 'return_' node, processing any expression and obtaining type         information to be accumulated in the current namespace's list of return         types. A snapshot of the namespace is taken for the purposes of         reconciling or merging namespaces where subprograms actually share         locals with their callers.         """          if hasattr(return_, "expr"):             return_.expr = self.dispatch(return_.expr)             combine(self.namespace.returns, self.namespace.types)             self.annotate(return_)         self.namespace.snapshot()         return return_      visitReturnFromBlock = visitReturn     visitReturnFromFunction = visitReturn      def visitStoreAttr(self, storeattr):          """         Return the 'storeattr' node, processing the expression and target, and         using the type information obtained to build records of legitimate         writes to the stated attribute, along with "impossible" non-writes to         the attribute.         """          storeattr.expr = self.dispatch(storeattr.expr)         expr = self.namespace.types         storeattr.lvalue = self.dispatch(storeattr.lvalue)         writes = {}         non_writes = []         for attr in self.namespace.types:             # NOTE: Impose "atomic" constraints on certain types.             if attr is None:                 if not attr in non_writes:                     non_writes.append(attr)                 continue             attr.type.namespace.add(storeattr.name, expr)             writes[attr.type] = attr.type.namespace.load(storeattr.name)         if not writes:             print "Unable to store attribute", storeattr.name, "given", self.namespace.types         storeattr.writes = writes         storeattr.non_writes = non_writes         return storeattr      def visitStoreName(self, storename):          """         Return the 'storename' node, processing the expression on the node and         associating the type information obtained with the stated name in the         current namespace.         """          storename.expr = self.dispatch(storename.expr)         self.namespace.store(storename.name, self.namespace.types)         return storename      def visitStoreTemp(self, storetemp):          """         Return the 'storetemp' node, processing the expression on the node and         associating the type information obtained with a temporary variable in         the current namespace.         """          storetemp.expr = self.dispatch(storetemp.expr)         index = getattr(storetemp, "index", None)         if not self.namespace.temp.has_key(index):             self.namespace.temp[index] = []         self.namespace.temp[index].append(self.namespace.types)         return storetemp      def visitSubprogram(self, subprogram):          """         Return the 'subprogram' node, processing its contents (a group of nodes         comprising the subprogram).         """          subprogram.code = self.dispatches(subprogram.code)         return subprogram      def visitTry(self, try_):          """         Return the 'try_' node, processing the body clause in its own namespace         derived from the current namespace, processing any handler clause using         the namespace information accumulated in the body, and processing any         else and finally clauses, attempting to supply each with appropriate         namespace information.         """          is_module = self.namespace is self.module.namespace          try_.body = self.dispatches(try_.body)          # Save the namespace from the body.          body_namespace = Namespace()         body_namespace.merge_namespace(self.namespace)          # Process the handler.          if hasattr(try_, "handler"):             try_.handler = self.dispatches(try_.handler)          # Save the namespace from the handler.          handler_namespace = Namespace()         handler_namespace.merge_namespace(self.namespace)          # Remember the raised exceptions encountered so far.          raises = self.namespace.raises          # Process the else clause.          if hasattr(try_, "else_"):              # Restore the body namespace for the else clause.              self.namespace = body_namespace             if is_module:                 self.module.namespace = self.namespace              # Empty the raised exceptions for the else clause.              self.namespace.raises = []             try_.else_ = self.dispatches(try_.else_)             self.namespace.raises = raises          # Merge the namespaces.          self.namespace = Namespace()         if is_module:             self.module.namespace = self.namespace         self.namespace.merge_namespace(body_namespace)         self.namespace.merge_namespace(handler_namespace)          # Process the finally clause, if any.          try_.finally_ = self.dispatches(try_.finally_)         return try_      # Utility methods.      def get_builtin_instances(self, node, name):         return [Attribute(None, self.new_instance(node, attr.type)) for attr in self.builtins.namespace[name]]      def new_instance(self, node, type):          "For the given 'node', obtain an instance from the given 'type'."          if not type.has_instance(node):             instance = Instance()             instance.namespace = Namespace()             instance.namespace.store("__class__", [Attribute(None, type)])             type.add_instance(node, instance)         else:             instance = type.get_instance(node)          return instance      def invoke_subprogram(self, invoke, attribute):          """         Invoke using the given 'invoke' node the subprogram represented by the         given 'attribute'.         """          # Test for context information, making it into a real attribute.          if attribute.context is not None:             context = Attribute(None, attribute.context)             target = attribute.type         else:             context = None             target = attribute.type          # Test to see if anything has changed.          if hasattr(invoke, "syscount") and invoke.syscount.has_key(target) and invoke.syscount[target] == self.system.count:             return          # Remember the state of the system.          else:             if not hasattr(invoke, "syscount"):                 invoke.syscount = {}             invoke.syscount[target] = self.system.count          # Provide the correct namespace for the invocation.         # This may be a "shared" namespace...          if getattr(invoke, "share_locals", 0):             namespace = Namespace()             namespace.merge_namespace(self.namespace, everything=0)             using_module_namespace = self.namespace is self.module.namespace          # Or it may be a structure...          elif getattr(target, "structure", None):             namespace = Namespace()             using_module_namespace = 0          # Or it may be a new namespace populated with the supplied parameters.          else:             items = self.make_items(invoke, target, context)             namespace = Namespace()             namespace.merge_items(items)             using_module_namespace = 0              # NOTE: Avoid PEP 227 (nested scopes) whilst permitting references to a             # NOTE: subprogram within itself. Do not define the name of the function             # NOTE: within a method definition.              if getattr(target, "name", None) is not None and not getattr(target, "is_method", 0):                 namespace.store(target.name, [Attribute(None, target)])          # Process the subprogram.         # In order to keep global accesses working, the module namespace must be         # adjusted.          if using_module_namespace:             self.module.namespace = namespace          self.process_node(target, namespace)          # NOTE: Improve and verify this.         # If the invocation returns a value, acquire the return types.          if getattr(target, "returns_value", 0):             self.namespace.set_types(self.last_returns)             self.annotate(invoke)          # If it is a normal block, merge the locals.         # This can happen in addition to the above because for things like         # logical expressions, the namespace can be modified whilst values are         # returned as results.          if getattr(invoke, "share_locals", 0):             self.namespace.reset()              # Merge the locals snapshots.              for locals in self.returned_locals:                  # For blocks returning values (such as operations), do not merge                 # snapshots or results.                  if getattr(target, "returns_value", 0):                     self.namespace.merge_namespace(locals, everything=0)                  # For blocks not returning values (such as loops), merge                 # snapshots and results since they contain details of genuine                 # returns.                  else:                     self.namespace.merge_namespace(locals)          # Incorporate any raised exceptions.          combine(self.namespace.raises, self.last_raises)          # In order to keep global accesses working, the module namespace must be         # adjusted.          if using_module_namespace:             self.module.namespace = self.namespace      def process_args(self, invocation):          """         Process the arguments associated with an 'invocation'. Return whether         any arguments were processed.         """          invocation.pos_args = self.dispatches(invocation.pos_args)         invocation.kw_args = self.dispatch_dict(invocation.kw_args)          # Get type information for star and dstar arguments.          if invocation.star is not None:             param, default = invocation.star             default = self.dispatch(default)             invocation.star = param, default          if invocation.dstar is not None:             param, default = invocation.dstar             default = self.dispatch(default)             invocation.dstar = param, default          if invocation.pos_args or invocation.kw_args or invocation.star or invocation.dstar:             return 1         else:             return 0      def make_items(self, invocation, subprogram, context):          """         Make an items mapping for the 'invocation' of the 'subprogram' using the         given 'context' (which may be None).         """          if context is not None:             pos_args = [Self(context)] + invocation.pos_args         else:             pos_args = invocation.pos_args          # Duplicate the keyword arguments - we remove them in processing below.          kw_args = {}         kw_args.update(invocation.kw_args)          # Sort the arguments into positional and keyword arguments.          params = subprogram.params         items = []         star_args = []          # Match each positional argument, taking excess arguments as star args.          for arg in pos_args:             if params:                 param, default = params[0]                 if arg is None:                     arg = default                 if hasattr(arg, "types"):                     items.append((param, arg.types))                 else:                     items.append((param, [])) # Annotation has not succeeded.                 params = params[1:]             else:                 star_args.append(arg)          # Collect the remaining defaults.          while params:             param, default = params[0]             if kw_args.has_key(param):                 arg = kw_args[param]                 del kw_args[param]             elif default is not None:                 arg = self.dispatch(default)             else:                 raise AnnotationMessage, "No argument supplied in '%s' for parameter '%s'." % (subprogram, param)             if hasattr(arg, "types"):                 items.append((param, arg.types))             else:                 items.append((param, [])) # Annotation has not succeeded.             params = params[1:]          dstar_args = kw_args.items()          # Construct temporary objects.          if star_args:             star_invocation = self.make_star_args(invocation, subprogram, star_args)             self.dispatch(star_invocation)             star_types = star_invocation.types         else:             star_types = None          if dstar_args:             dstar_invocation = self.make_dstar_args(invocation, subprogram, dstar_args)             self.dispatch(dstar_invocation)             dstar_types = dstar_invocation.types         else:             dstar_types = None          # NOTE: Merge the objects properly.          star_types = star_types or invocation.star and invocation.star.types         dstar_types = dstar_types or invocation.dstar and invocation.dstar.types          # Add star and dstar.          if star_types is not None:             if subprogram.star is not None:                 param, default = subprogram.star                 items.append((param, star_types))             else:                 raise AnnotationMessage, "Invocation provides unwanted *args."         elif subprogram.star is not None:             param, default = subprogram.star             if not hasattr(default, "types"):                 subprogram.star = param, self.dispatch(default) # NOTE: Review reprocessing.             items.append((param, default.types))          if dstar_types is not None:             if subprogram.dstar is not None:                 param, default = subprogram.dstar                 items.append((param, dstar_types))             else:                 raise AnnotationMessage, "Invocation provides unwanted **args."         elif subprogram.dstar is not None:             param, default = subprogram.dstar             if not hasattr(default, "types"):                 subprogram.dstar = param, self.dispatch(default) # NOTE: Review reprocessing.             items.append((param, default.types))          # Record the parameter types.          self.annotate_parameters(subprogram, items)         return subprogram.paramtypes.items()      def make_star_args(self, invocation, subprogram, star_args):          "Make a subprogram which initialises a list containing 'star_args'."          if not hasattr(invocation, "stars"):             invocation.stars = {}          if not invocation.stars.has_key(subprogram.full_name()):             code=[                 StoreTemp(                     expr=InvokeFunction(                         invocation.original,                         expr=LoadAttr(                             expr=LoadRef(                                 ref=self.builtins                                 ),                             name="list",                             nstype="module",                             ),                         args=[],                         star=None,                         dstar=None                         )                     )                 ]              for arg in star_args:                 code.append(                     InvokeFunction(                         invocation.original,                         expr=LoadAttr(                             expr=LoadTemp(),                             name="append"                             ),                         args=[arg],                         star=None,                         dstar=None                         )                     )              code += [                 Return(expr=LoadTemp(release=1))                 ]              invocation.stars[subprogram.full_name()] = InvokeBlock(                 invocation.original,                 produces_result=1,                 expr=LoadRef(                     ref=Subprogram(                         name=None,                         returns_value=1,                         params=[],                         star=None,                         dstar=None,                         code=code                         )                     )                 )          return invocation.stars[subprogram.full_name()]      def make_dstar_args(self, invocation, subprogram, dstar_args):          """         Make a subprogram which initialises a dictionary built from the given         'dstar_args'.         """          if not hasattr(invocation, "dstars"):             invocation.dstars = {}          if not invocation.dstars.has_key(subprogram.full_name()):             code=[                 StoreTemp(                     expr=InvokeFunction(                         invocation.original,                         expr=LoadAttr(                             expr=LoadRef(                                 ref=self.builtins                                 ),                             name="dict",                             nstype="module",                             )                         )                     )                 ]              for arg, value in dstar_args:                  # NOTE: Constant not added to table.                  constant = Constant(name=repr(arg), value=arg, namespace=Namespace())                 #constant.namespace.store("__class__", self.get_builtin_instances(invocation, constant.typename))                 code += [                     StoreTemp(                         expr=LoadRef(                             ref=constant                             ),                         index="const"                         ),                     StoreAttr(                         lvalue=LoadTemp(                             index="const"                             ),                         name="__class__",                         expr=LoadAttr(                             expr=LoadRef(                                 ref=self.builtins                                 ),                             name=constant.typename,                             nstype="module",                             )                         ),                     InvokeFunction(                         invocation.original,                         expr=LoadAttr(                             expr=LoadTemp(),                             name="__setitem__"                             ),                         args=[                             LoadTemp(                                 index="const",                                 release=1                                 ),                             value                             ]                         )                     ]              code += [                 Return(expr=LoadTemp(release=1))                 ]              invocation.dstars[subprogram.full_name()] = InvokeBlock(                 invocation.original,                 produces_result=1,                 expr=LoadRef(                     ref=Subprogram(                         name=None,                         returns_value=1,                         params=[],                         star=None,                         dstar=None,                         code=code                         )                     )                 )          return invocation.dstars[subprogram.full_name()]  # Namespace-related abstractions.  class Namespace:      """     A local namespace which may either relate to a genuine set of function     locals or the initialisation of a structure or module.     """      def __init__(self):          """         Initialise the namespace with a mapping of local names to possible         types, a list of return values and of possible returned local         namespaces. The namespace also tracks the "current" types and a mapping         of temporary value names to types.         """          self.names = {}         self.returns = []         self.return_locals = []         self.raises = []         self.temp = {}         self.types = []      def set_types(self, types):          "Set the current collection of 'types'."          self.types = types      def add(self, name, types):          "Add to the entry with the given 'name' the specified 'types'."          if self.names.has_key(name):             combine(self.names[name], types)         else:             self.store(name, types)      def store(self, name, types):          "Store in (or associate with) the given 'name' the specified 'types'."          self.names[name] = types      __setitem__ = store      def load(self, name):          "Load the types associated with the given 'name'."          return self.names[name]      __getitem__ = load      def revoke(self, name, type):          "Revoke from the entry for the given 'name' the specified 'type'."          new_types = self.names[name][:]         new_types.remove(type)         self.names[name] = new_types      def revoke_exception_type(self, type):          "Revoke the given 'type' from the collection of exception types."          self.raises.remove(type)      def revoke_temp_type(self, index, type):          "Revoke from the temporary variable 'index' the given 'type'."          new_types = self.temp[index][-1][:]         new_types.remove(type)         self.temp[index][-1] = new_types      def merge_namespace(self, namespace, everything=1):          """         Merge items from the given 'namespace' with this namespace. When the         optional 'everything' parameter is set to a false value (unlike the         default), return values and locals snapshots will not be copied to this         namespace.         """          self.merge_items(namespace.names.items())         if everything:             combine(self.returns, namespace.returns)             combine(self.return_locals, namespace.return_locals)         combine(self.raises, namespace.raises)         for name, values in namespace.temp.items():             if values:                 if not self.temp.has_key(name) or not self.temp[name]:                     self.temp[name] = [[]]                 combine(self.temp[name][-1], values[-1])      def merge_items(self, items):          "Merge the given 'items' with this namespace."          for name, types in items:             self.merge(name, types)      def merge(self, name, types):          "Merge the entry for the given 'name' and 'types' with this namespace."          if not self.names.has_key(name):             self.names[name] = types[:]         else:             existing = self.names[name]             combine(existing, types)      def snapshot(self):          "Make a snapshot of the locals and remember them."          namespace = Namespace()         namespace.merge_namespace(self)         self.return_locals.append(namespace)      def reset(self):          "Reset a namespace in preparation for merging with returned locals."          self.names = {}      def __repr__(self):         return repr(self.names)  class Importer:      "An import machine, searching for and loading modules."      def __init__(self, path=None):          """         Initialise the importer with the given search 'path' - a list of         directories to search for Python modules.         """          self.path = path or [os.getcwd()]         self.modules = {}      def find_in_path(self, name):          """         Find the given module 'name' in the search path, returning None where no         such module could be found, or a 2-tuple from the 'find' method         otherwise.         """          for d in self.path:             m = self.find(d, name)             if m: return m         return None      def find(self, d, name):          """         In the directory 'd', find the given module 'name', where 'name' can         either refer to a single file module or to a package. Return None if the         'name' cannot be associated with either a file or a package directory,         or a 2-tuple from '_find_package' or '_find_module' otherwise.         """          m = self._find_package(d, name)         if m: return m         m = self._find_module(d, name)         if m: return m         return None      def _find_module(self, d, name):          """         In the directory 'd', find the given module 'name', returning None where         no suitable file exists in the directory, or a 2-tuple consisting of         None (indicating that no package directory is involved) and a filename         indicating the location of the module.         """          name_py = name + os.extsep + "py"         filename = self._find_file(d, name_py)         if filename:             return None, filename         return None      def _find_package(self, d, name):          """         In the directory 'd', find the given package 'name', returning None         where no suitable package directory exists, or a 2-tuple consisting of         a directory (indicating the location of the package directory itself)         and a filename indicating the location of the __init__.py module which         declares the package's top-level contents.         """          filename = self._find_file(d, name)         if filename:             init_py = "__init__" + os.path.extsep + "py"             init_py_filename = self._find_file(filename, init_py)             if init_py_filename:                 return filename, init_py_filename         return None      def _find_file(self, d, filename):          """         Return the filename obtained when searching the directory 'd' for the         given 'filename', or None if no actual file exists for the filename.         """          filename = os.path.join(d, filename)         if os.path.exists(filename):             return filename         else:             return None      def load(self, name, builtins, alias=None):          """         Load the module or package with the given 'name' and using the specified         'builtins'. Return an Attribute object referencing the loaded module or         package, or None if no such module or package exists.         """          path = name.split(".")         m = self.find_in_path(path[0])         if not m:             return None # NOTE: Import error.         d, filename = m         top = module = self.modules.get(path[0], load(filename, builtins, path[0], self))         self.modules[path[0]] = module          if len(path) > 1:             path_so_far = path[:1]             for p in path[1:]:                 path_so_far.append(p)                 m = self.find(d, p)                 if not m:                     return None # NOTE: Import error.                 d, filename = m                 module_name = ".".join(path_so_far)                 submodule = self.modules.get(module_name, load(filename, builtins, module_name, self))                 self.modules[module_name] = submodule                  # Store the submodule within its parent module.                  module.namespace[p] = [Attribute(None, submodule)]                 module = submodule          if alias:             return Attribute(None, module)         else:             return Attribute(None, top)  def combine(target, additions):      """     Merge into the 'target' sequence the given 'additions', preventing duplicate     items.     """      for addition in additions:         if addition not in target:             target.append(addition)  def find_attributes(structure, name):      """     Find for the given 'structure' all attributes for the given 'name', visiting     base classes where appropriate and returning the attributes in order of     descending precedence for all possible base classes.      The elements in the result list are 2-tuples which contain the attribute and     the structure involved in accessing the attribute.     """      # First attempt to search the instance/class namespace.      try:         l = structure.namespace.load(name)         attributes = []         for attribute in l:             attributes.append((attribute, structure))      # If that does not work, attempt to investigate any class or base classes.      except KeyError:         attributes = []          # Investigate any instance's implementing class.          if isinstance(structure, Instance):             for attr in structure.namespace.load("__class__"):                 cls = attr.type                 l = get_attributes(cls, name)                 combine(attributes, l)          # Investigate any class's base classes.          elif isinstance(structure, Class):              # If no base classes exist, return an indicator that no attribute             # exists.              if not structure.base_refs:                 return [(None, structure)]              # Otherwise, find all possible base classes.              for base_refs in structure.base_refs:                 base_attributes = []                  # For each base class, find attributes either in the base                 # class or its own base classes.                  for base_ref in base_refs:                     l = get_attributes(base_ref, name)                     combine(base_attributes, l)                  combine(attributes, base_attributes)      return attributes  def get_attributes(structure, name):      """     Return all possible attributes for the given 'structure' having the given     'name', wrapping each attribute in an Attribute object which includes     context information for the attribute access.      The elements in the result list are 2-tuples which contain the attribute and     the structure involved in accessing the attribute.     """      if isinstance(structure, Attribute):         structure = structure.type     results = []     for attribute, accessor in find_attributes(structure, name):          # Detect class attribute access via instances.          if attribute is not None and isinstance(structure, Instance) and isinstance(accessor, Class):             attribute = accessor.get_attribute_for_instance(attribute, structure)          # Produce an attribute with the appropriate context.          if attribute is not None and isinstance(structure, Structure):             results.append((Attribute(structure, attribute.type), accessor))         else:             results.append((attribute, accessor))      return results  # Convenience functions.  def load(name, builtins=None, module_name=None, importer=None):      """     Load the module with the given 'name' (which may be a full module path),     using the optional 'builtins' to resolve built-in names, and using the     optional 'importer' to provide a means of finding and loading modules.     """      module = simplify.simplify(name, builtins is None, module_name)     fixnames.fix(module, builtins)     annotate(module, builtins, importer)     return module  def annotate(module, builtins=None, importer=None):      """     Annotate the given 'module', also employing the optional 'builtins' module,     if specified. If the optional 'importer' is given, use that to find and load     modules.     """      annotator = Annotator(importer)     if builtins is not None:         annotator.process(module, builtins)     else:         annotator.process(module)  # vim: tabstop=4 expandtab shiftwidth=4