Lichen

deducer.py

785:1f07b0aa675e
2017-03-26 Paul Boddie Simplified the tuple instantiator.
     1 #!/usr/bin/env python     2      3 """     4 Deduce types for usage observations.     5      6 Copyright (C) 2014, 2015, 2016, 2017 Paul Boddie <paul@boddie.org.uk>     7      8 This program is free software; you can redistribute it and/or modify it under     9 the terms of the GNU General Public License as published by the Free Software    10 Foundation; either version 3 of the License, or (at your option) any later    11 version.    12     13 This program is distributed in the hope that it will be useful, but WITHOUT    14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS    15 FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more    16 details.    17     18 You should have received a copy of the GNU General Public License along with    19 this program.  If not, see <http://www.gnu.org/licenses/>.    20 """    21     22 from common import first, get_assigned_attributes, \    23                    get_attrname_from_location, get_attrnames, \    24                    get_invoked_attributes, get_name_path, init_item, \    25                    order_dependencies_partial, sorted_output, CommonOutput    26 from encoders import encode_access_location, encode_constrained, \    27                      encode_instruction, encode_location, encode_usage, \    28                      get_kinds, test_label_for_kind, test_label_for_type    29 from errors import DeduceError    30 from os.path import join    31 from referencing import combine_types, is_single_class_type, separate_types, \    32                         Reference    33     34 class Deducer(CommonOutput):    35     36     "Deduce types in a program."    37     38     root_class_type = "__builtins__.object"    39     40     def __init__(self, importer, output):    41     42         """    43         Initialise an instance using the given 'importer' that will perform    44         deductions on the program information, writing the results to the given    45         'output' directory.    46         """    47     48         self.importer = importer    49         self.output = output    50     51         # Descendants of classes.    52     53         self.descendants = {}    54         self.init_descendants()    55         self.init_special_attributes()    56     57         # Map locations to usage in order to determine specific types.    58     59         self.location_index = {}    60     61         # Map access locations to definition locations.    62     63         self.access_index = {}    64     65         # Map definition locations to affected accesses.    66     67         self.access_index_rev = {}    68     69         # Map aliases to accesses that define them.    70     71         self.alias_index = {}    72     73         # Map accesses to aliases whose initial values are influenced by them.    74     75         self.alias_index_rev = {}    76     77         # Map constant accesses to redefined accesses.    78     79         self.const_accesses = {}    80         self.const_accesses_rev = {}    81     82         # Map usage observations to assigned attributes.    83     84         self.assigned_attrs = {}    85     86         # Map usage observations to objects.    87     88         self.attr_class_types = {}    89         self.attr_instance_types = {}    90         self.attr_module_types = {}    91     92         # All known attribute names.    93     94         self.all_attrnames = set()    95     96         # Modified attributes from usage observations.    97     98         self.modified_attributes = {}    99    100         # Accesses that are assignments or invocations.   101    102         self.reference_assignments = set()   103         self.reference_invocations = {}   104         self.reference_invocations_unsuitable = {}   105    106         # Map locations to types, constrained indicators and attributes.   107    108         self.accessor_class_types = {}   109         self.accessor_instance_types = {}   110         self.accessor_module_types = {}   111         self.provider_class_types = {}   112         self.provider_instance_types = {}   113         self.provider_module_types = {}   114         self.accessor_constrained = set()   115         self.access_constrained = set()   116         self.referenced_attrs = {}   117         self.referenced_objects = {}   118    119         # Details of access operations.   120    121         self.access_plans = {}   122    123         # Specific attribute access information.   124    125         self.access_instructions = {}   126         self.accessor_kinds = {}   127    128         # Accumulated information about accessors and providers.   129    130         self.accessor_general_class_types = {}   131         self.accessor_general_instance_types = {}   132         self.accessor_general_module_types = {}   133         self.accessor_all_types = {}   134         self.accessor_all_general_types = {}   135         self.provider_all_types = {}   136         self.accessor_guard_tests = {}   137    138         # Accumulated information about accessed attributes and   139         # access/attribute-specific accessor tests.   140    141         self.reference_all_attrs = {}   142         self.reference_all_providers = {}   143         self.reference_all_provider_kinds = {}   144         self.reference_all_accessor_types = {}   145         self.reference_all_accessor_general_types = {}   146         self.reference_test_types = {}   147         self.reference_test_accessor_type = {}   148    149         # The processing workflow itself.   150    151         self.init_usage_index()   152         self.init_attr_type_indexes()   153         self.init_combined_attribute_index()   154         self.init_accessors()   155         self.init_accesses()   156         self.init_aliases()   157         self.modify_mutated_attributes()   158         self.identify_references()   159         self.classify_accessors()   160         self.classify_accesses()   161         self.initialise_access_plans()   162         self.initialise_access_instructions()   163         self.identify_dependencies()   164    165     def to_output(self):   166    167         "Write the output files using deduction information."   168    169         self.check_output()   170    171         self.write_mutations()   172         self.write_accessors()   173         self.write_accesses()   174         self.write_access_plans()   175    176     def write_mutations(self):   177    178         """   179         Write mutation-related output in the following format:   180    181         qualified name " " original object type   182    183         Object type can be "<class>", "<function>" or "<var>".   184         """   185    186         f = open(join(self.output, "mutations"), "w")   187         try:   188             attrs = self.modified_attributes.items()   189             attrs.sort()   190    191             for attr, value in attrs:   192                 print >>f, attr, value   193         finally:   194             f.close()   195    196     def write_accessors(self):   197    198         """   199         Write reference-related output in the following format for types:   200    201         location " " ( "constrained" | "deduced" ) " " attribute type " " most general type names " " number of specific types   202    203         Note that multiple lines can be given for each location, one for each   204         attribute type.   205    206         Locations have the following format:   207    208         qualified name of scope "." local name ":" name version   209    210         The attribute type can be "<class>", "<instance>", "<module>" or "<>",   211         where the latter indicates an absence of suitable references.   212    213         Type names indicate the type providing the attributes, being either a   214         class or module qualified name.   215    216         ----   217    218         A summary of accessor types is formatted as follows:   219    220         location " " ( "constrained" | "deduced" ) " " ( "specific" | "common" | "unguarded" ) " " most general type names " " number of specific types   221    222         This summary groups all attribute types (class, instance, module) into a   223         single line in order to determine the complexity of identifying an   224         accessor.   225    226         ----   227    228         References that cannot be supported by any types are written to a   229         warnings file in the following format:   230    231         location   232    233         ----   234    235         For each location where a guard would be asserted to guarantee the   236         nature of an object, the following format is employed:   237    238         location " " ( "specific" | "common" ) " " object kind " " object types   239    240         Object kind can be "<class>", "<instance>" or "<module>".   241         """   242    243         f_type_summary = open(join(self.output, "type_summary"), "w")   244         f_types = open(join(self.output, "types"), "w")   245         f_warnings = open(join(self.output, "type_warnings"), "w")   246         f_guards = open(join(self.output, "guards"), "w")   247    248         try:   249             locations = self.accessor_class_types.keys()   250             locations.sort()   251    252             for location in locations:   253                 constrained = location in self.accessor_constrained   254    255                 # Accessor information.   256    257                 class_types = self.accessor_class_types[location]   258                 instance_types = self.accessor_instance_types[location]   259                 module_types = self.accessor_module_types[location]   260    261                 general_class_types = self.accessor_general_class_types[location]   262                 general_instance_types = self.accessor_general_instance_types[location]   263                 general_module_types = self.accessor_general_module_types[location]   264    265                 all_types = self.accessor_all_types[location]   266                 all_general_types = self.accessor_all_general_types[location]   267    268                 if class_types:   269                     print >>f_types, encode_location(location), encode_constrained(constrained), "<class>", \   270                         sorted_output(general_class_types), len(class_types)   271    272                 if instance_types:   273                     print >>f_types, encode_location(location), encode_constrained(constrained), "<instance>", \   274                         sorted_output(general_instance_types), len(instance_types)   275    276                 if module_types:   277                     print >>f_types, encode_location(location), encode_constrained(constrained), "<module>", \   278                         sorted_output(general_module_types), len(module_types)   279    280                 if not all_types:   281                     print >>f_types, encode_location(location), "deduced", "<>", 0   282                     attrnames = list(self.location_index[location])   283                     attrnames.sort()   284                     print >>f_warnings, encode_location(location), "; ".join(map(encode_usage, attrnames))   285    286                 guard_test = self.accessor_guard_tests.get(location)   287                 if guard_test:   288                     guard_test_type, guard_test_arg = guard_test   289    290                 # Write specific type guard details.   291    292                 if guard_test and guard_test_type == "specific":   293                     print >>f_guards, encode_location(location), "-".join(guard_test), \   294                         first(get_kinds(all_types)), \   295                         sorted_output(all_types)   296    297                 # Write common type guard details.   298    299                 elif guard_test and guard_test_type == "common":   300                     print >>f_guards, encode_location(location), "-".join(guard_test), \   301                         first(get_kinds(all_general_types)), \   302                         sorted_output(all_general_types)   303    304                 print >>f_type_summary, encode_location(location), encode_constrained(constrained), \   305                     guard_test and "-".join(guard_test) or "unguarded", sorted_output(all_general_types), len(all_types)   306    307         finally:   308             f_type_summary.close()   309             f_types.close()   310             f_warnings.close()   311             f_guards.close()   312    313     def write_accesses(self):   314    315         """   316         Specific attribute output is produced in the following format:   317    318         location " " ( "constrained" | "deduced" ) " " attribute type " " attribute references   319    320         Note that multiple lines can be given for each location and attribute   321         name, one for each attribute type.   322    323         Locations have the following format:   324    325         qualified name of scope "." local name " " attribute name ":" access number   326    327         The attribute type can be "<class>", "<instance>", "<module>" or "<>",   328         where the latter indicates an absence of suitable references.   329    330         Attribute references have the following format:   331    332         object type ":" qualified name   333    334         Object type can be "<class>", "<function>" or "<var>".   335    336         ----   337    338         A summary of attributes is formatted as follows:   339    340         location " " attribute name " " ( "constrained" | "deduced" ) " " test " " attribute references   341    342         This summary groups all attribute types (class, instance, module) into a   343         single line in order to determine the complexity of each access.   344    345         Tests can be "validate", "specific", "untested", "guarded-validate" or "guarded-specific".   346    347         ----   348    349         For each access where a test would be asserted to guarantee the   350         nature of an attribute, the following formats are employed:   351    352         location " " attribute name " " "validate"   353         location " " attribute name " " "specific" " " attribute type " " object type   354    355         ----   356    357         References that cannot be supported by any types are written to a   358         warnings file in the following format:   359    360         location   361         """   362    363         f_attr_summary = open(join(self.output, "attribute_summary"), "w")   364         f_attrs = open(join(self.output, "attributes"), "w")   365         f_tests = open(join(self.output, "tests"), "w")   366         f_warnings = open(join(self.output, "attribute_warnings"), "w")   367         f_unsuitable = open(join(self.output, "invocation_warnings"), "w")   368    369         try:   370             locations = self.referenced_attrs.keys()   371             locations.sort()   372    373             for location in locations:   374                 constrained = location in self.access_constrained   375    376                 # Attribute information, both name-based and anonymous.   377    378                 referenced_attrs = self.referenced_attrs[location]   379    380                 if referenced_attrs:   381                     attrname = get_attrname_from_location(location)   382    383                     all_accessed_attrs = list(set(self.reference_all_attrs[location]))   384                     all_accessed_attrs.sort()   385    386                     for attrtype, attrs in self.get_referenced_attrs(location):   387                         print >>f_attrs, encode_access_location(location), encode_constrained(constrained), attrtype, sorted_output(attrs)   388    389                     test_type = self.reference_test_types.get(location)   390    391                     # Write the need to test at run time.   392    393                     if test_type[0] == "validate":   394                         print >>f_tests, encode_access_location(location), "-".join(test_type)   395    396                     # Write any type checks for anonymous accesses.   397    398                     elif test_type and self.reference_test_accessor_type.get(location):   399                         print >>f_tests, encode_access_location(location), "-".join(test_type), \   400                             sorted_output(all_accessed_attrs), \   401                             self.reference_test_accessor_type[location]   402    403                     print >>f_attr_summary, encode_access_location(location), encode_constrained(constrained), \   404                         test_type and "-".join(test_type) or "untested", sorted_output(all_accessed_attrs)   405    406                     # Write details of potentially unsuitable invocation   407                     # occurrences.   408    409                     unsuitable = self.reference_invocations_unsuitable.get(location)   410                     if unsuitable:   411                         unsuitable = map(str, unsuitable)   412                         unsuitable.sort()   413                         print >>f_unsuitable, encode_access_location(location), ", ".join(unsuitable)   414    415                 else:   416                     print >>f_warnings, encode_access_location(location)   417    418         finally:   419             f_attr_summary.close()   420             f_attrs.close()   421             f_tests.close()   422             f_warnings.close()   423             f_unsuitable.close()   424    425     def write_access_plans(self):   426    427         """   428         Write access and instruction plans.   429    430         Each attribute access is written out as a plan of the following form:   431    432         location " " name " " test " " test type " " base " " traversed attributes   433                  " " traversal access modes " " attributes to traverse   434                  " " context " " context test " " first access method   435                  " " final access method " " static attribute " " accessor kinds   436    437         Locations have the following format:   438    439         qualified name of scope "." local name ":" name version   440    441         Traversal access modes are either "class" (obtain accessor class to   442         access attribute) or "object" (obtain attribute directly from accessor).   443         """   444    445         f_attrs = open(join(self.output, "attribute_plans"), "w")   446    447         try:   448             locations = self.access_plans.keys()   449             locations.sort()   450    451             for location in locations:   452                 name, test, test_type, base, \   453                     traversed, traversal_modes, attrnames, \   454                     context, context_test, \   455                     first_method, final_method, \   456                     attr, accessor_kinds = self.access_plans[location]   457    458                 print >>f_attrs, encode_access_location(location), \   459                                  name or "{}", \   460                                  test and "-".join(test) or "{}", \   461                                  test_type or "{}", \   462                                  base or "{}", \   463                                  ".".join(traversed) or "{}", \   464                                  ".".join(traversal_modes) or "{}", \   465                                  ".".join(attrnames) or "{}", \   466                                  context, context_test, \   467                                  first_method, final_method, attr or "{}", \   468                                  ",".join(accessor_kinds)   469    470         finally:   471             f_attrs.close()   472    473         f = open(join(self.output, "instruction_plans"), "w")   474         try:   475             access_instructions = self.access_instructions.items()   476             access_instructions.sort()   477    478             for location, instructions in access_instructions:   479                 print >>f, encode_access_location(location), "..."   480                 for instruction in instructions:   481                     print >>f, encode_instruction(instruction)   482                 print >>f   483    484         finally:   485             f.close()   486    487     def classify_accessors(self):   488    489         "For each program location, classify accessors."   490    491         # Where instance and module types are defined, class types are also   492         # defined. See: init_definition_details   493    494         locations = self.accessor_class_types.keys()   495    496         for location in locations:   497             constrained = location in self.accessor_constrained   498    499             # Provider information.   500    501             class_types = self.provider_class_types[location]   502             instance_types = self.provider_instance_types[location]   503             module_types = self.provider_module_types[location]   504    505             # Collect specific and general type information.   506    507             self.provider_all_types[location] = \   508                 combine_types(class_types, instance_types, module_types)   509    510             # Accessor information.   511    512             class_types = self.accessor_class_types[location]   513             self.accessor_general_class_types[location] = \   514                 general_class_types = self.get_most_general_class_types(class_types)   515    516             instance_types = self.accessor_instance_types[location]   517             self.accessor_general_instance_types[location] = \   518                 general_instance_types = self.get_most_general_class_types(instance_types)   519    520             module_types = self.accessor_module_types[location]   521             self.accessor_general_module_types[location] = \   522                 general_module_types = self.get_most_general_module_types(module_types)   523    524             # Collect specific and general type information.   525    526             self.accessor_all_types[location] = all_types = \   527                 combine_types(class_types, instance_types, module_types)   528    529             self.accessor_all_general_types[location] = all_general_types = \   530                 combine_types(general_class_types, general_instance_types, general_module_types)   531    532             # Record guard information but only for accessors employed by   533             # accesses. There are no attribute accesses to guard, otherwise.   534    535             if not constrained and self.access_index_rev.get(location):   536    537                 # Record specific type guard details.   538    539                 if len(all_types) == 1:   540                     self.accessor_guard_tests[location] = ("specific", test_label_for_type(first(all_types)))   541                 elif is_single_class_type(all_types):   542                     self.accessor_guard_tests[location] = ("specific", "object")   543    544                 # Record common type guard details.   545    546                 elif len(all_general_types) == 1:   547                     self.accessor_guard_tests[location] = ("common", test_label_for_type(first(all_types)))   548                 elif is_single_class_type(all_general_types):   549                     self.accessor_guard_tests[location] = ("common", "object")   550    551                 # Otherwise, no convenient guard can be defined.   552    553     def classify_accesses(self):   554    555         "For each program location, classify accesses."   556    557         # Attribute accesses use potentially different locations to those of   558         # accessors.   559    560         locations = self.referenced_attrs.keys()   561    562         for location in locations:   563             constrained = location in self.access_constrained   564    565             # Combine type information from all accessors supplying the access.   566    567             accessor_locations = self.get_accessors_for_access(location)   568    569             all_provider_types = set()   570             all_accessor_types = set()   571             all_accessor_general_types = set()   572    573             for accessor_location in accessor_locations:   574    575                 # Obtain the provider types for guard-related attribute access   576                 # checks.   577    578                 all_provider_types.update(self.provider_all_types.get(accessor_location))   579    580                 # Obtain the accessor guard types (specific and general).   581    582                 all_accessor_types.update(self.accessor_all_types.get(accessor_location))   583                 all_accessor_general_types.update(self.accessor_all_general_types.get(accessor_location))   584    585             # Obtain basic properties of the types involved in the access.   586    587             single_accessor_type = len(all_accessor_types) == 1   588             single_accessor_class_type = is_single_class_type(all_accessor_types)   589             single_accessor_general_type = len(all_accessor_general_types) == 1   590             single_accessor_general_class_type = is_single_class_type(all_accessor_general_types)   591    592             # Determine whether the attribute access is guarded or not.   593    594             guarded = (   595                 single_accessor_type or single_accessor_class_type or   596                 single_accessor_general_type or single_accessor_general_class_type   597                 )   598    599             if guarded:   600                 (guard_class_types, guard_instance_types, guard_module_types,   601                     _function_types, _var_types) = separate_types(all_provider_types)   602    603             self.reference_all_accessor_types[location] = all_accessor_types   604             self.reference_all_accessor_general_types[location] = all_accessor_general_types   605    606             # Attribute information, both name-based and anonymous.   607    608             referenced_attrs = self.referenced_attrs[location]   609    610             if not referenced_attrs:   611                 raise DeduceError("In %s, access via %s to attribute %s (occurrence %d) cannot be identified." % location)   612    613             # Record attribute information for each name used on the   614             # accessor.   615    616             attrname = get_attrname_from_location(location)   617    618             self.reference_all_attrs[location] = all_accessed_attrs = []   619             self.reference_all_providers[location] = all_providers = []   620             self.reference_all_provider_kinds[location] = all_provider_kinds = set()   621    622             # Obtain provider and attribute details for this kind of   623             # object.   624    625             for attrtype, object_type, attr in referenced_attrs:   626                 all_accessed_attrs.append(attr)   627                 all_providers.append(object_type)   628                 all_provider_kinds.add(attrtype)   629    630             # Obtain reference and provider information as sets for the   631             # operations below, retaining the list forms for use with   632             # instruction plan preparation.   633    634             all_accessed_attrs = set(all_accessed_attrs)   635             all_providers = set(all_providers)   636             all_general_providers = self.get_most_general_types(all_providers)   637    638             # Determine which attributes would be provided by the   639             # accessor types upheld by a guard.   640    641             if guarded:   642                 guard_attrs = set()   643    644                 for _attrtype, object_type, attr in \   645                     self._identify_reference_attribute(location, attrname, guard_class_types, guard_instance_types, guard_module_types):   646    647                     guard_attrs.add(attr)   648             else:   649                 guard_attrs = None   650    651             # Constrained accesses guarantee the nature of the accessor.   652             # However, there may still be many types involved.   653    654             if constrained:   655                 if single_accessor_type:   656                     self.reference_test_types[location] = ("constrained", "specific", test_label_for_type(first(all_accessor_types)))   657                 elif single_accessor_class_type:   658                     self.reference_test_types[location] = ("constrained", "specific", "object")   659                 elif single_accessor_general_type:   660                     self.reference_test_types[location] = ("constrained", "common", test_label_for_type(first(all_accessor_general_types)))   661                 elif single_accessor_general_class_type:   662                     self.reference_test_types[location] = ("constrained", "common", "object")   663                 else:   664                     self.reference_test_types[location] = ("constrained", "many")   665    666             # Suitably guarded accesses, where the nature of the   667             # accessor can be guaranteed, do not require the attribute   668             # involved to be validated. Otherwise, for unguarded   669             # accesses, access-level tests are required.   670    671             elif guarded and all_accessed_attrs.issubset(guard_attrs):   672                 if single_accessor_type:   673                     self.reference_test_types[location] = ("guarded", "specific", test_label_for_type(first(all_accessor_types)))   674                 elif single_accessor_class_type:   675                     self.reference_test_types[location] = ("guarded", "specific", "object")   676                 elif single_accessor_general_type:   677                     self.reference_test_types[location] = ("guarded", "common", test_label_for_type(first(all_accessor_general_types)))   678                 elif single_accessor_general_class_type:   679                     self.reference_test_types[location] = ("guarded", "common", "object")   680    681             # Record the need to test the type of anonymous and   682             # unconstrained accessors.   683    684             elif len(all_providers) == 1:   685                 provider = first(all_providers)   686                 if provider != self.root_class_type:   687                     all_accessor_kinds = set(get_kinds(all_accessor_types))   688                     if len(all_accessor_kinds) == 1:   689                         test_type = ("test", "specific", test_label_for_kind(first(all_accessor_kinds)))   690                     else:   691                         test_type = ("test", "specific", "object")   692                     self.reference_test_types[location] = test_type   693                     self.reference_test_accessor_type[location] = provider   694    695             elif len(all_general_providers) == 1:   696                 provider = first(all_general_providers)   697                 if provider != self.root_class_type:   698                     all_accessor_kinds = set(get_kinds(all_accessor_general_types))   699                     if len(all_accessor_kinds) == 1:   700                         test_type = ("test", "common", test_label_for_kind(first(all_accessor_kinds)))   701                     else:   702                         test_type = ("test", "common", "object")   703                     self.reference_test_types[location] = test_type   704                     self.reference_test_accessor_type[location] = provider   705    706             # Record the need to test the identity of the attribute.   707    708             else:   709                 self.reference_test_types[location] = ("validate",)   710    711     def initialise_access_plans(self):   712    713         "Define attribute access plans."   714    715         for location in self.referenced_attrs.keys():   716             original_location = self.const_accesses_rev.get(location)   717             self.access_plans[original_location or location] = self.get_access_plan(location)   718    719     def identify_dependencies(self):   720    721         "Introduce more module dependencies to the importer."   722    723         for location, referenced_attrs in self.referenced_attrs.items():   724             path, name, attrnames, version = location   725    726             # Identify references providing dependencies.   727    728             for attrtype, objtype, attr in referenced_attrs:   729                 self.importer.add_dependency(path, attr.get_origin())   730    731     def get_referenced_attrs(self, location):   732    733         """   734         Return attributes referenced at the given access 'location' by the given   735         'attrname' as a list of (attribute type, attribute set) tuples.   736         """   737    738         d = {}   739         for attrtype, objtype, attr in self.referenced_attrs[location]:   740             init_item(d, attrtype, set)   741             d[attrtype].add(attr.unaliased())   742         l = d.items()   743         l.sort() # class, module, instance   744         return l   745    746     # Initialisation methods.   747    748     def init_descendants(self):   749    750         "Identify descendants of each class."   751    752         for name in self.importer.classes.keys():   753             self.get_descendants_for_class(name)   754    755     def get_descendants_for_class(self, name):   756    757         """   758         Use subclass information to deduce the descendants for the class of the   759         given 'name'.   760         """   761    762         if not self.descendants.has_key(name):   763             descendants = set()   764    765             for subclass in self.importer.subclasses[name]:   766                 descendants.update(self.get_descendants_for_class(subclass))   767                 descendants.add(subclass)   768    769             self.descendants[name] = descendants   770    771         return self.descendants[name]   772    773     def init_special_attributes(self):   774    775         "Add special attributes to the classes for inheritance-related tests."   776    777         all_class_attrs = self.importer.all_class_attrs   778    779         for name, descendants in self.descendants.items():   780             for descendant in descendants:   781                 all_class_attrs[descendant]["#%s" % name] = name   782    783         for name in all_class_attrs.keys():   784             all_class_attrs[name]["#%s" % name] = name   785    786     def init_usage_index(self):   787    788         """   789         Create indexes for module and function attribute usage and for anonymous   790         accesses.   791         """   792    793         for module in self.importer.get_modules():   794             for path, assignments in module.attr_usage.items():   795                 self.add_usage(assignments, path)   796    797         for location, all_attrnames in self.importer.all_attr_accesses.items():   798             for attrnames in all_attrnames:   799                 attrname = get_attrnames(attrnames)[-1]   800                 access_location = (location, None, attrnames, 0)   801                 self.add_usage_term(access_location, ((attrname, False, False),))   802    803     def add_usage(self, assignments, path):   804    805         """   806         Collect usage from the given 'assignments', adding 'path' details to   807         each record if specified. Add the usage to an index mapping to location   808         information, as well as to an index mapping locations to usages.   809         """   810    811         for name, versions in assignments.items():   812             for i, usages in enumerate(versions):   813                 location = (path, name, None, i)   814    815                 for usage in usages:   816                     self.add_usage_term(location, usage)   817    818     def add_usage_term(self, location, usage):   819    820         """   821         For 'location' and using 'usage' as a description of usage, record   822         in the usage index a mapping from the usage to 'location', and record in   823         the location index a mapping from 'location' to the usage.   824         """   825    826         init_item(self.location_index, location, set)   827         self.location_index[location].add(usage)   828    829     def init_accessors(self):   830    831         "Create indexes for module and function accessor information."   832    833         for module in self.importer.get_modules():   834             for path, all_accesses in module.attr_accessors.items():   835                 self.add_accessors(all_accesses, path)   836    837     def add_accessors(self, all_accesses, path):   838    839         """   840         For attribute accesses described by the mapping of 'all_accesses' from   841         name details to accessor details, record the locations of the accessors   842         for each access.   843         """   844    845         # Get details for each access combining the given name and attribute.   846    847         for (name, attrnames), accesses in all_accesses.items():   848    849             # Obtain the usage details using the access information.   850    851             for access_number, versions in enumerate(accesses):   852                 access_location = (path, name, attrnames, access_number)   853                 locations = []   854    855                 for version in versions:   856                     location = (path, name, None, version)   857                     locations.append(location)   858    859                     # Map accessors to affected accesses.   860    861                     l = init_item(self.access_index_rev, location, set)   862                     l.add(access_location)   863    864                 # Map accesses to supplying accessors.   865    866                 self.access_index[access_location] = locations   867    868     def get_accessors_for_access(self, access_location):   869    870         "Find a definition providing accessor details, if necessary."   871    872         try:   873             return self.access_index[access_location]   874         except KeyError:   875             return [access_location]   876    877     def init_accesses(self):   878    879         """   880         Check that attributes used in accesses are actually defined on some   881         object. This can be overlooked if unknown attributes are employed in   882         attribute chains.   883    884         Initialise collections for accesses involving assignments.   885         """   886    887         # For each scope, obtain access details.   888    889         for path, all_accesses in self.importer.all_attr_access_modifiers.items():   890    891             # For each combination of name and attribute names, obtain   892             # applicable modifiers.   893    894             for (name, attrname_str), modifiers in all_accesses.items():   895    896                 # For each access, determine the name versions affected by   897                 # assignments.   898    899                 for access_number, (assignment, invocation) in enumerate(modifiers):   900    901                     if name:   902                         access_location = (path, name, attrname_str, access_number)   903                     else:   904                         access_location = (path, None, attrname_str, 0)   905    906                     # Plain name accesses do not employ attributes and are   907                     # ignored. Whether they are invoked is of interest, however.   908    909                     if not attrname_str:   910                         if invocation:   911                             self.reference_invocations[access_location] = invocation   912                         continue   913    914                     attrnames = get_attrnames(attrname_str)   915    916                     # Check the attribute names.   917    918                     for attrname in attrnames:   919                         if not attrname in self.all_attrnames:   920                             raise DeduceError("In %s, attribute %s is not defined in the program." % (path, attrname))   921    922                     # Now only process assignments and invocations.   923    924                     if invocation:   925                         self.reference_invocations[access_location] = invocation   926                         continue   927                     elif not assignment:   928                         continue   929    930                     # Associate assignments with usage.   931    932                     self.reference_assignments.add(access_location)   933    934                     # Assignment occurs for the only attribute.   935    936                     if len(attrnames) == 1:   937                         accessor_locations = self.get_accessors_for_access(access_location)   938    939                         for location in accessor_locations:   940                             for usage in self.location_index[location]:   941                                 init_item(self.assigned_attrs, usage, set)   942                                 self.assigned_attrs[usage].add((path, name, attrnames[0]))   943    944                     # Assignment occurs for the final attribute.   945    946                     else:   947                         usage = ((attrnames[-1], False, False),)   948                         init_item(self.assigned_attrs, usage, set)   949                         self.assigned_attrs[usage].add((path, name, attrnames[-1]))   950    951     def init_aliases(self):   952    953         "Expand aliases so that alias-based accesses can be resolved."   954    955         # Get aliased names with details of their accesses.   956    957         for (path, name), all_aliases in self.importer.all_aliased_names.items():   958    959             # For each version of the name, obtain the access locations.   960    961             for version, aliases in all_aliases.items():   962                 for (original_path, original_name, attrnames, access_number) in aliases:   963                     accessor_location = (path, name, None, version)   964                     access_location = (original_path, original_name, attrnames, access_number)   965                     init_item(self.alias_index, accessor_location, list)   966                     self.alias_index[accessor_location].append(access_location)   967    968         # Get aliases in terms of non-aliases and accesses.   969    970         for accessor_location, access_locations in self.alias_index.items():   971             self.update_aliases(accessor_location, access_locations)   972    973         # Get a mapping from accesses to affected aliases.   974    975         for accessor_location, access_locations in self.alias_index.items():   976             for access_location in access_locations:   977                 init_item(self.alias_index_rev, access_location, set)   978                 self.alias_index_rev[access_location].add(accessor_location)   979    980     def update_aliases(self, accessor_location, access_locations, visited=None):   981    982         """   983         Update the given 'accessor_location' defining an alias, update   984         'access_locations' to refer to non-aliases, following name references   985         via the access index.   986    987         If 'visited' is specified, it contains a set of accessor locations (and   988         thus keys to the alias index) that are currently being defined.   989         """   990    991         if visited is None:   992             visited = set()   993    994         updated_locations = set()   995    996         for access_location in access_locations:   997             (path, original_name, attrnames, access_number) = access_location   998    999             # Locations may have been recorded for return values, but they may  1000             # not correspond to actual accesses.  1001   1002             if not self.access_index.has_key(access_location):  1003                 updated_locations.add(access_location)  1004   1005             # Where an alias refers to a name access, obtain the original name  1006             # version details.  1007   1008             elif attrnames is None:  1009   1010                 # For each name version, attempt to determine any accesses that  1011                 # initialise the name.  1012   1013                 for name_accessor_location in self.access_index[access_location]:  1014   1015                     # Already-visited aliases do not contribute details.  1016   1017                     if name_accessor_location in visited:  1018                         continue  1019   1020                     visited.add(name_accessor_location)  1021   1022                     name_access_locations = self.alias_index.get(name_accessor_location)  1023                     if name_access_locations:  1024                         updated_locations.update(self.update_aliases(name_accessor_location, name_access_locations, visited))  1025                     else:  1026                         updated_locations.add(name_accessor_location)  1027   1028             # Otherwise, record the access details.  1029   1030             else:  1031                 updated_locations.add(access_location)  1032   1033         self.alias_index[accessor_location] = updated_locations  1034         return updated_locations  1035   1036     # Attribute mutation for types.  1037   1038     def modify_mutated_attributes(self):  1039   1040         "Identify known, mutated attributes and change their state."  1041   1042         # Usage-based accesses.  1043   1044         for usage, all_attrnames in self.assigned_attrs.items():  1045             if not usage:  1046                 continue  1047   1048             for path, name, attrname in all_attrnames:  1049                 class_types = self.get_class_types_for_usage(usage)  1050                 only_instance_types = set(self.get_instance_types_for_usage(usage)).difference(class_types)  1051                 module_types = self.get_module_types_for_usage(usage)  1052   1053                 # Detect self usage within methods in order to narrow the scope  1054                 # of the mutation.  1055   1056                 t = name == "self" and self.constrain_self_reference(path, class_types, only_instance_types)  1057                 if t:  1058                     class_types, only_instance_types, module_types, constrained = t  1059                 objects = set(class_types).union(only_instance_types).union(module_types)  1060   1061                 self.mutate_attribute(objects, attrname)  1062   1063     def mutate_attribute(self, objects, attrname):  1064   1065         "Mutate static 'objects' with the given 'attrname'."  1066   1067         for name in objects:  1068             attr = "%s.%s" % (name, attrname)  1069             value = self.importer.get_object(attr)  1070   1071             # If the value is None, the attribute is  1072             # inherited and need not be set explicitly on  1073             # the class concerned.  1074   1075             if value:  1076                 self.modified_attributes[attr] = value  1077                 self.importer.set_object(attr, value.as_var())  1078   1079     # Simplification of types.  1080   1081     def get_most_general_types(self, types):  1082   1083         "Return the most general types for the given 'types'."  1084   1085         module_types = set()  1086         class_types = set()  1087   1088         for type in types:  1089             ref = self.importer.identify(type)  1090             if ref.has_kind("<module>"):  1091                 module_types.add(type)  1092             else:  1093                 class_types.add(type)  1094   1095         types = set(self.get_most_general_module_types(module_types))  1096         types.update(self.get_most_general_class_types(class_types))  1097         return types  1098   1099     def get_most_general_class_types(self, class_types):  1100   1101         "Return the most general types for the given 'class_types'."  1102   1103         class_types = set(class_types)  1104         to_remove = set()  1105   1106         for class_type in class_types:  1107             for base in self.importer.classes[class_type]:  1108                 base = base.get_origin()  1109                 descendants = self.descendants[base]  1110                 if base in class_types and descendants.issubset(class_types):  1111                     to_remove.update(descendants)  1112   1113         class_types.difference_update(to_remove)  1114         return class_types  1115   1116     def get_most_general_module_types(self, module_types):  1117   1118         "Return the most general type for the given 'module_types'."  1119   1120         # Where all modules are provided, an object would provide the same  1121         # attributes.  1122   1123         if len(module_types) == len(self.importer.modules):  1124             return [self.root_class_type]  1125         else:  1126             return module_types  1127   1128     # More efficient usage-to-type indexing and retrieval.  1129   1130     def init_attr_type_indexes(self):  1131   1132         "Identify the types that can support each attribute name."  1133   1134         self._init_attr_type_index(self.attr_class_types, self.importer.all_class_attrs)  1135         self._init_attr_type_index(self.attr_instance_types, self.importer.all_instance_attrs, True)  1136         self._init_attr_type_index(self.attr_instance_types, self.importer.all_combined_attrs, False)  1137         self._init_attr_type_index(self.attr_module_types, self.importer.all_module_attrs)  1138   1139     def _init_attr_type_index(self, attr_types, attrs, assignment=None):  1140   1141         """  1142         Initialise the 'attr_types' attribute-to-types mapping using the given  1143         'attrs' type-to-attributes mapping.  1144         """  1145   1146         for name, attrnames in attrs.items():  1147             for attrname in attrnames:  1148   1149                 # Permit general access for certain kinds of object.  1150   1151                 if assignment is None:  1152                     init_item(attr_types, (attrname, False), set)  1153                     init_item(attr_types, (attrname, True), set)  1154                     attr_types[(attrname, False)].add(name)  1155                     attr_types[(attrname, True)].add(name)  1156   1157                 # Restrict attribute assignment for instances.  1158   1159                 else:  1160                     init_item(attr_types, (attrname, assignment), set)  1161                     attr_types[(attrname, assignment)].add(name)  1162   1163     def get_class_types_for_usage(self, usage):  1164   1165         "Return names of classes supporting the given 'usage'."  1166   1167         return self._get_types_for_usage(usage, self.attr_class_types, self.importer.all_class_attrs)  1168   1169     def get_instance_types_for_usage(self, usage):  1170   1171         """  1172         Return names of classes whose instances support the given 'usage'  1173         (as either class or instance attributes).  1174         """  1175   1176         return self._get_types_for_usage(usage, self.attr_instance_types, self.importer.all_combined_attrs)  1177   1178     def get_module_types_for_usage(self, usage):  1179   1180         "Return names of modules supporting the given 'usage'."  1181   1182         return self._get_types_for_usage(usage, self.attr_module_types, self.importer.all_module_attrs)  1183   1184     def _get_types_for_usage(self, usage, attr_types, attrs):  1185   1186         """  1187         For the given 'usage' representing attribute usage, return types  1188         recorded in the 'attr_types' attribute-to-types mapping that support  1189         such usage, with the given 'attrs' type-to-attributes mapping used to  1190         quickly assess whether a type supports all of the stated attributes.  1191         """  1192   1193         # Where no attributes are used, any type would be acceptable.  1194   1195         if not usage:  1196             return attrs.keys()  1197   1198         keys = []  1199         for attrname, invocation, assignment in usage:  1200             keys.append((attrname, assignment))  1201   1202         # Obtain types supporting the first (attribute name, assignment) key...  1203   1204         types = set(attr_types.get(keys[0]) or [])  1205   1206         for key in keys[1:]:  1207               1208             # Record types that support all of the other attributes as well.  1209   1210             types.intersection_update(attr_types.get(key) or [])  1211   1212         return types  1213   1214     def init_combined_attribute_index(self):  1215   1216         "Initialise a combined index for the detection of invalid attributes."  1217   1218         self.all_attrnames = set()  1219         for attrs in (self.importer.all_combined_attrs, self.importer.all_module_attrs):  1220             for name, attrnames in attrs.items():  1221                 self.all_attrnames.update(attrnames)  1222   1223     # Reference identification.  1224   1225     def identify_references(self):  1226   1227         "Identify references using usage and name reference information."  1228   1229         # Names with associated attribute usage.  1230   1231         for location, usages in self.location_index.items():  1232   1233             # Obtain attribute usage associated with a name, deducing the nature  1234             # of the name. Obtain types only for branches involving attribute  1235             # usage. (In the absence of usage, any type could be involved, but  1236             # then no accesses exist to require knowledge of the type.)  1237   1238             have_usage = False  1239             have_no_usage_branch = False  1240   1241             for usage in usages:  1242                 if not usage:  1243                     have_no_usage_branch = True  1244                     continue  1245                 elif not have_usage:  1246                     self.init_definition_details(location)  1247                     have_usage = True  1248                 self.record_types_for_usage(location, usage)  1249   1250             # Where some usage occurs, but where branches without usage also  1251             # occur, record the types for those branches anyway.  1252   1253             if have_usage and have_no_usage_branch:  1254                 self.init_definition_details(location)  1255                 self.record_types_for_usage(location, None)  1256   1257         # Specific name-based attribute accesses.  1258   1259         for access_location, accessor_locations in self.access_index.items():  1260             self.record_types_for_access(access_location, accessor_locations)  1261   1262         # Anonymous references with attribute chains.  1263   1264         for location, accesses in self.importer.all_attr_accesses.items():  1265   1266             # Get distinct attribute names.  1267   1268             all_attrnames = set()  1269   1270             for attrnames in accesses:  1271                 all_attrnames.update(get_attrnames(attrnames))  1272   1273             # Get attribute and accessor details for each attribute name.  1274   1275             for attrname in all_attrnames:  1276                 access_location = (location, None, attrname, 0)  1277                 self.record_types_for_attribute(access_location, attrname)  1278   1279         # References via constant/identified objects.  1280   1281         for location, name_accesses in self.importer.all_const_accesses.items():  1282   1283             # A mapping from the original name and attributes to resolved access  1284             # details.  1285   1286             for original_access, access in name_accesses.items():  1287                 original_name, original_attrnames = original_access  1288                 objpath, ref, attrnames = access  1289   1290                 # Build an accessor combining the name and attribute names used.  1291   1292                 original_accessor = tuple([original_name] + original_attrnames.split("."))  1293   1294                 # Direct accesses to attributes.  1295   1296                 if not attrnames:  1297   1298                     # Build a descriptive location based on the original  1299                     # details, exposing the final attribute name.  1300   1301                     oa, attrname = original_accessor[:-1], original_accessor[-1]  1302                     oa = ".".join(oa)  1303   1304                     access_location = (location, oa, attrname, 0)  1305                     accessor_location = (location, oa, None, 0)  1306                     self.access_index[access_location] = [accessor_location]  1307   1308                     self.init_access_details(access_location)  1309                     self.init_definition_details(accessor_location)  1310   1311                     # Obtain a reference for the accessor in order to properly  1312                     # determine its type.  1313   1314                     if ref.get_kind() != "<instance>":  1315                         objpath = ref.get_origin()  1316   1317                     objpath = objpath.rsplit(".", 1)[0]  1318   1319                     # Where the object name conflicts with the module  1320                     # providing it, obtain the module details.  1321   1322                     if objpath in self.importer.modules:  1323                         accessor = Reference("<module>", objpath)  1324                     else:  1325                         accessor = self.importer.get_object(objpath)  1326   1327                     self.referenced_attrs[access_location] = [(accessor.get_kind(), accessor.get_origin(), ref)]  1328                     self.access_constrained.add(access_location)  1329   1330                     class_types, instance_types, module_types = accessor.get_types()  1331                     self.record_reference_types(accessor_location, class_types, instance_types, module_types, True, True)  1332   1333                 else:  1334   1335                     # Build a descriptive location based on the original  1336                     # details, employing the first remaining attribute name.  1337   1338                     l = get_attrnames(attrnames)  1339                     attrname = l[0]  1340   1341                     oa = original_accessor[:-len(l)]  1342                     oa = ".".join(oa)  1343   1344                     access_location = (location, oa, attrnames, 0)  1345                     accessor_location = (location, oa, None, 0)  1346                     self.access_index[access_location] = [accessor_location]  1347   1348                     self.init_access_details(access_location)  1349                     self.init_definition_details(accessor_location)  1350   1351                     class_types, instance_types, module_types = ref.get_types()  1352   1353                     self.identify_reference_attributes(access_location, attrname, class_types, instance_types, module_types, True)  1354                     self.record_reference_types(accessor_location, class_types, instance_types, module_types, True, True)  1355   1356                 # Define mappings between the original and access locations  1357                 # so that translation can work from the source details.  1358   1359                 original_location = (location, original_name, original_attrnames, 0)  1360   1361                 if original_location != access_location:  1362                     self.const_accesses[original_location] = access_location  1363                     self.const_accesses_rev[access_location] = original_location  1364   1365         # Propagate alias-related information.  1366   1367         affected_aliases = set(self.alias_index.keys())  1368   1369         while True:  1370   1371             # Aliased name definitions. All aliases with usage will have been  1372             # defined, but they may be refined according to referenced accesses.  1373   1374             updated_aliases = set()  1375   1376             for location in affected_aliases:  1377                 if self.record_types_for_alias(location):  1378                     updated_aliases.add(location)  1379   1380             # Define accesses employing aliases.  1381   1382             alias_accesses = set()  1383             affected_aliases = set()  1384   1385             for alias in updated_aliases:  1386   1387                 # Access affected by the alias.  1388   1389                 if self.access_index_rev.has_key(alias):  1390                     alias_accesses.update(self.access_index_rev[alias])  1391   1392                 # Another alias affected by the alias.  1393   1394                 elif self.alias_index_rev.has_key(alias):  1395                     affected_aliases.update(self.alias_index_rev[alias])  1396   1397             # Update accesses employing aliases.  1398   1399             updated_accesses = set()  1400   1401             for access_location in alias_accesses:  1402                 if self.record_types_for_access(access_location, self.access_index[access_location]):  1403                     updated_accesses.add(access_location)  1404   1405             # Determine which aliases are affected by the updated accesses.  1406   1407             for access_location in updated_accesses:  1408                 if self.alias_index_rev.has_key(access_location):  1409                     affected_aliases.update(self.alias_index_rev[access_location])  1410   1411             if not affected_aliases:  1412                 break  1413   1414     def constrain_types(self, path, class_types, instance_types, module_types):  1415   1416         """  1417         Using the given 'path' to an object, constrain the given 'class_types',  1418         'instance_types' and 'module_types'.  1419   1420         Return the class, instance, module types plus whether the types are  1421         constrained to a specific kind of type.  1422         """  1423   1424         ref = self.importer.identify(path)  1425         if ref:  1426   1427             # Constrain usage suggestions using the identified object.  1428   1429             if ref.has_kind("<class>"):  1430                 return (  1431                     set(class_types).intersection([ref.get_origin()]), [], [], True  1432                     )  1433             elif ref.has_kind("<module>"):  1434                 return (  1435                     [], [], set(module_types).intersection([ref.get_origin()]), True  1436                     )  1437   1438         return class_types, instance_types, module_types, False  1439   1440     def get_target_types(self, location, usage):  1441   1442         """  1443         Return the class, instance and module types constrained for the name at  1444         the given 'location' exhibiting the given 'usage'. Whether the types  1445         have been constrained using contextual information is also indicated,  1446         plus whether the types have been constrained to a specific kind of type.  1447         """  1448   1449         unit_path, name, attrnames, version = location  1450         have_assignments = get_assigned_attributes(usage)  1451   1452         # Detect any initialised name for the location.  1453   1454         if name:  1455             refs = self.get_initialised_name(location)  1456             if refs:  1457                 (class_types, only_instance_types, module_types,  1458                     _function_types, _var_types) = separate_types(refs)  1459                 return class_types, only_instance_types, module_types, True, have_assignments  1460   1461         # Retrieve the recorded types for the usage.  1462   1463         class_types = self.get_class_types_for_usage(usage)  1464         only_instance_types = set(self.get_instance_types_for_usage(usage)).difference(class_types)  1465         module_types = self.get_module_types_for_usage(usage)  1466   1467         # Merge usage deductions with observations to obtain reference types  1468         # for names involved with attribute accesses.  1469   1470         if not name:  1471             return class_types, only_instance_types, module_types, False, have_assignments  1472   1473         # Obtain references to known objects.  1474   1475         path = get_name_path(unit_path, name)  1476   1477         class_types, only_instance_types, module_types, constrained_specific = \  1478             self.constrain_types(path, class_types, only_instance_types, module_types)  1479   1480         if constrained_specific:  1481             return class_types, only_instance_types, module_types, constrained_specific, \  1482                 constrained_specific or have_assignments  1483   1484         # Constrain "self" references.  1485   1486         if name == "self":  1487   1488             # Test for the class of the method in the deduced types.  1489   1490             class_name = self.in_method(unit_path)  1491   1492             if class_name and class_name not in class_types and class_name not in only_instance_types:  1493                 raise DeduceError("In %s, usage {%s} is not directly supported by class %s or its instances." %  1494                                   (unit_path, encode_usage(usage), class_name))  1495   1496             # Constrain the types to the class's hierarchy.  1497   1498             t = self.constrain_self_reference(unit_path, class_types, only_instance_types)  1499             if t:  1500                 class_types, only_instance_types, module_types, constrained = t  1501                 return class_types, only_instance_types, module_types, constrained, have_assignments  1502   1503         return class_types, only_instance_types, module_types, False, have_assignments  1504   1505     def constrain_self_reference(self, unit_path, class_types, only_instance_types):  1506   1507         """  1508         Where the name "self" appears in a method, attempt to constrain the  1509         classes involved.  1510   1511         Return the class, instance, module types plus whether the types are  1512         constrained.  1513         """  1514   1515         class_name = self.in_method(unit_path)  1516   1517         if not class_name:  1518             return None  1519   1520         classes = set([class_name])  1521         classes.update(self.get_descendants_for_class(class_name))  1522   1523         # Note that only instances will be expected for these references but  1524         # either classes or instances may provide the attributes.  1525   1526         return (  1527             set(class_types).intersection(classes),  1528             set(only_instance_types).intersection(classes),  1529             [], True  1530             )  1531   1532     def in_method(self, path):  1533   1534         "Return whether 'path' refers to a method."  1535   1536         class_name, method_name = path.rsplit(".", 1)  1537         return class_name != "__builtins__.core.type" and self.importer.classes.has_key(class_name) and class_name  1538   1539     def init_reference_details(self, location):  1540   1541         "Initialise reference-related details for 'location'."  1542   1543         self.init_definition_details(location)  1544         self.init_access_details(location)  1545   1546     def init_definition_details(self, location):  1547   1548         "Initialise name definition details for 'location'."  1549   1550         self.accessor_class_types[location] = set()  1551         self.accessor_instance_types[location] = set()  1552         self.accessor_module_types[location] = set()  1553         self.provider_class_types[location] = set()  1554         self.provider_instance_types[location] = set()  1555         self.provider_module_types[location] = set()  1556   1557     def init_access_details(self, location):  1558   1559         "Initialise access details at 'location'."  1560   1561         self.referenced_attrs[location] = {}  1562   1563     def record_types_for_access(self, access_location, accessor_locations):  1564   1565         """  1566         Define types for the 'access_location' associated with the given  1567         'accessor_locations'. Return whether referenced attributes were updated.  1568         """  1569   1570         attrname = get_attrname_from_location(access_location)  1571         if not attrname:  1572             return False  1573   1574         invocation = access_location in self.reference_invocations  1575         assignment = access_location in self.reference_assignments  1576   1577         # Collect all suggested types for the accessors. Accesses may  1578         # require accessors from of a subset of the complete set of types.  1579   1580         class_types = set()  1581         module_types = set()  1582         instance_types = set()  1583   1584         constrained = True  1585   1586         old_referenced_attrs = self.referenced_attrs.get(access_location)  1587   1588         for location in accessor_locations:  1589   1590             # Use the type information deduced for names from above.  1591   1592             if self.accessor_class_types.has_key(location):  1593                 class_types.update(self.accessor_class_types[location])  1594                 module_types.update(self.accessor_module_types[location])  1595                 instance_types.update(self.accessor_instance_types[location])  1596   1597             # Where accesses are associated with assignments but where no  1598             # attribute usage observations have caused such an association,  1599             # the attribute name is considered by itself.  1600   1601             else:  1602                 self.init_definition_details(location)  1603                 self.record_types_for_usage(location, [(attrname, invocation, assignment)])  1604   1605             constrained = location in self.accessor_constrained and constrained  1606   1607         self.init_access_details(access_location)  1608         self.identify_reference_attributes(access_location, attrname, class_types, instance_types, module_types, constrained)  1609   1610         # Return whether the referenced attributes have changed.  1611   1612         return old_referenced_attrs != self.referenced_attrs.get(access_location)  1613   1614     def record_types_for_usage(self, accessor_location, usage):  1615   1616         """  1617         Record types for the given 'accessor_location' according to the given  1618         'usage' observations which may be None to indicate an absence of usage.  1619         """  1620   1621         (class_types,  1622          instance_types,  1623          module_types,  1624          constrained,  1625          constrained_specific) = self.get_target_types(accessor_location, usage)  1626   1627         invocations = get_invoked_attributes(usage)  1628   1629         self.record_reference_types(accessor_location, class_types, instance_types,  1630             module_types, constrained, constrained_specific, invocations)  1631   1632     def record_types_for_attribute(self, access_location, attrname):  1633   1634         """  1635         Record types for the 'access_location' employing only the given  1636         'attrname' for type deduction.  1637         """  1638   1639         (class_types,  1640          only_instance_types,  1641          module_types) = self.get_types_for_attribute(attrname)  1642   1643         self.init_reference_details(access_location)  1644   1645         self.identify_reference_attributes(access_location, attrname, class_types, only_instance_types, module_types, False)  1646         self.record_reference_types(access_location, class_types, only_instance_types, module_types, False)  1647   1648     def get_types_for_attribute(self, attrname):  1649   1650         "Return class, instance-only and module types supporting 'attrname'."  1651   1652         usage = ((attrname, False, False),)  1653   1654         class_types = self.get_class_types_for_usage(usage)  1655         only_instance_types = set(self.get_instance_types_for_usage(usage)).difference(class_types)  1656         module_types = self.get_module_types_for_usage(usage)  1657   1658         return class_types, only_instance_types, module_types  1659   1660     def record_types_for_alias(self, accessor_location):  1661   1662         """  1663         Define types for the 'accessor_location' not having associated usage.  1664         Return whether the types were updated.  1665         """  1666   1667         have_access = self.provider_class_types.has_key(accessor_location)  1668   1669         # With an access, attempt to narrow the existing selection of provider  1670         # types. Invocations attempt to find return value information, with  1671         # instance return values also yielding class providers (since attributes  1672         # on instances could be provided by classes).  1673   1674         if have_access:  1675             provider_class_types = self.provider_class_types[accessor_location]  1676             provider_instance_types = self.provider_instance_types[accessor_location]  1677             provider_module_types = self.provider_module_types[accessor_location]  1678   1679             accessor_class_types = self.accessor_class_types[accessor_location]  1680             accessor_instance_types = self.accessor_instance_types[accessor_location]  1681             accessor_module_types = self.accessor_module_types[accessor_location]  1682   1683             # Find details for any corresponding access.  1684   1685             new_provider_class_types = set()  1686             new_provider_instance_types = set()  1687             new_provider_module_types = set()  1688   1689             new_accessor_class_types = set()  1690             new_accessor_instance_types = set()  1691             new_accessor_module_types = set()  1692   1693             refs = set()  1694   1695             for access_location in self.alias_index[accessor_location]:  1696                 location, name, attrnames, access_number = access_location  1697                 invocation = self.reference_invocations.get(access_location)  1698   1699                 attrnames = attrnames and attrnames.split(".")  1700                 remaining = attrnames and len(attrnames) > 1  1701   1702                 # Alias has remaining attributes: reference details do not  1703                 # correspond to the accessor; the remaining attributes would  1704                 # need to be traversed first.  1705   1706                 if remaining:  1707                     return False  1708   1709                 # Alias references an attribute access.  1710   1711                 if attrnames:  1712   1713                     # Obtain references and attribute types for the access.  1714   1715                     attrs = self.get_references_for_access(access_location)  1716   1717                     if attrs:  1718   1719                         # Invocations converting class accessors to instances do  1720                         # not change the nature of class providers.  1721   1722                         provider_attrs = self.convert_invocation_providers(attrs, invocation)  1723   1724                         # Accessors are updated separately, employing invocation  1725                         # result details.  1726   1727                         accessor_attrs = self.convert_invocations(attrs, invocation)  1728   1729                 # Alias references a name, not an access.  1730   1731                 else:  1732                     # Attempt to refine the types using initialised names or  1733                     # accessors.  1734   1735                     attrs = self.get_initialised_name(access_location)  1736   1737                     if attrs:  1738                         provider_attrs = self.convert_invocation_providers(attrs, invocation)  1739                         accessor_attrs = self.convert_invocations(attrs, invocation)  1740                     else:  1741                         provider_attrs = self.get_provider_references(access_location)  1742                         attrs = accessor_attrs = self.get_accessor_references(access_location)  1743   1744                 # Where no specific attributes are defined, do not attempt  1745                 # to refine the alias's types.  1746   1747                 if not attrs:  1748                     return False  1749   1750                 (class_types, instance_types, module_types, function_types,  1751                     var_types) = separate_types(provider_attrs)  1752   1753                 # Where non-accessor types are found, do not attempt to refine  1754                 # the defined accessor types.  1755   1756                 if function_types or var_types:  1757                     return False  1758   1759                 class_types = set(provider_class_types).intersection(class_types)  1760                 instance_types = set(provider_instance_types).intersection(instance_types)  1761                 module_types = set(provider_module_types).intersection(module_types)  1762   1763                 new_provider_class_types.update(class_types)  1764                 new_provider_instance_types.update(instance_types)  1765                 new_provider_module_types.update(module_types)  1766   1767                 (class_types, instance_types, module_types, function_types,  1768                     var_types) = separate_types(accessor_attrs)  1769   1770                 class_types = set(accessor_class_types).intersection(class_types)  1771                 instance_types = set(accessor_instance_types).intersection(instance_types)  1772                 module_types = set(accessor_module_types).intersection(module_types)  1773   1774                 new_accessor_class_types.update(class_types)  1775                 new_accessor_instance_types.update(instance_types)  1776                 new_accessor_module_types.update(module_types)  1777   1778                 refs.update(accessor_attrs)  1779   1780                 # Update the alias relationships for invocations.  1781   1782                 self.update_alias_accesses(access_location, attrs)  1783   1784             # Record refined type details for the alias as an accessor.  1785   1786             self.init_definition_details(accessor_location)  1787             self.update_provider_types(accessor_location, new_provider_class_types, new_provider_instance_types, new_provider_module_types)  1788             self.update_accessor_types(accessor_location, new_accessor_class_types, new_accessor_instance_types, new_accessor_module_types)  1789   1790             # Record reference details for the alias separately from accessors.  1791   1792             self.referenced_objects[accessor_location] = refs  1793   1794             return new_accessor_class_types != accessor_class_types or \  1795                    new_accessor_instance_types != accessor_instance_types or \  1796                    new_accessor_module_types != accessor_module_types  1797   1798         # Without an access, attempt to identify references for the alias.  1799         # Invocations convert classes to instances and also attempt to find  1800         # return value information.  1801   1802         else:  1803             refs = set()  1804   1805             for access_location in self.alias_index[accessor_location]:  1806                 location, name, attrnames, access_number = access_location  1807                 invocation = self.reference_invocations.get(access_location)  1808   1809                 attrnames = attrnames and attrnames.split(".")  1810                 remaining = attrnames and len(attrnames) > 1  1811   1812                 # Alias has remaining attributes: reference details do not  1813                 # correspond to the accessor; the remaining attributes would  1814                 # need to be traversed first.  1815   1816                 if remaining:  1817                     return False  1818   1819                 # Alias references an attribute access.  1820   1821                 if attrnames:  1822   1823                     # Obtain references and attribute types for the access.  1824   1825                     attrs = self.get_references_for_access(access_location)  1826   1827                 # Alias references a name, not an access.  1828   1829                 else:  1830   1831                     # Obtain initialiser information.  1832   1833                     attrs = self.get_initialised_name(access_location)  1834   1835                     if attrs:  1836                         provider_attrs = self.convert_invocation_providers(attrs, invocation)  1837                         accessor_attrs = self.convert_invocations(attrs, invocation)  1838                     else:  1839                         provider_attrs = self.get_provider_references(access_location)  1840                         attrs = accessor_attrs = self.get_accessor_references(access_location)  1841   1842                 # Where no further information is found, do not attempt to  1843                 # refine the defined accessor types.  1844   1845                 if not attrs:  1846                     return False  1847   1848                 refs.update(self.convert_invocations(attrs, invocation))  1849   1850                 # Update the alias relationships for invocations.  1851   1852                 self.update_alias_accesses(access_location, attrs)  1853   1854             # Record refined type details for the alias as an accessor.  1855   1856             (class_types, instance_types, module_types, function_types,  1857                 var_types) = separate_types(refs)  1858   1859             # Where non-accessor types are found, do not attempt to refine  1860             # the defined accessor types.  1861   1862             if not function_types and not var_types:  1863                 self.init_definition_details(accessor_location)  1864                 self.update_provider_types(accessor_location, class_types + instance_types, class_types + instance_types, module_types)  1865                 self.update_accessor_types(accessor_location, class_types, instance_types, module_types)  1866   1867             # Record reference details for the alias separately from accessors.  1868   1869             self.referenced_objects[accessor_location] = refs  1870   1871             return True  1872   1873     def update_alias_accesses(self, access_location, refs):  1874   1875         """  1876         Record 'access_location' as a location affected by the return values of  1877         'refs' if an invocation is involved.  1878         """  1879   1880         if not self.reference_invocations.has_key(access_location):  1881             return  1882   1883         for ref in refs:  1884   1885             # Initialising accesses originate from the return values.  1886   1887             key = (ref.get_origin(), "$return")  1888             self._update_alias_accesses(access_location, key, self.importer.all_initialised_names)  1889             self._update_alias_accesses(access_location, key, self.importer.all_aliased_names)  1890   1891     def _update_alias_accesses(self, access_location, key, names):  1892   1893         """  1894         Make each return value provide information to the given  1895         'access_location', using 'key' to reference the return value and 'names'  1896         as the collection of definitions.  1897         """  1898   1899         versions = names.get(key)  1900         if not versions:  1901             return  1902   1903         for version in versions.keys():  1904             location = key + (None, version)  1905             l = init_item(self.alias_index_rev, location, set)  1906             l.add(access_location)  1907   1908             l = init_item(self.alias_index, access_location, set)  1909             l.add(location)  1910   1911     def get_references_for_access(self, access_location):  1912   1913         "Return the references identified for 'access_location'."  1914   1915         attrs = []  1916         for attrtype, object_type, attr in self.referenced_attrs[access_location]:  1917             attrs.append(attr)  1918         return attrs  1919   1920     def convert_invocation_providers(self, refs, invocation):  1921   1922         """  1923         Convert 'refs' to providers corresponding to the results of invoking  1924         each of the given references, if 'invocation' is set to a true value.  1925         """  1926   1927         if not invocation:  1928             return refs  1929   1930         providers = set()  1931   1932         for ref in refs:  1933             invocation_providers = self.convert_accessors_to_providers(self.convert_invocation_provider(ref))  1934             providers.update(invocation_providers)  1935   1936         return self.references_or_var(providers)  1937   1938     def convert_accessors_to_providers(self, refs):  1939   1940         "Convert accessor 'refs' to provider references."  1941   1942         providers = set()  1943         for ref in refs:  1944             if ref.has_kind("<instance>"):  1945                 providers.add(Reference("<class>", ref.get_origin()))  1946             providers.add(ref)  1947         return providers  1948   1949     def convert_invocation_provider(self, ref):  1950   1951         "Convert 'ref' to a provider appropriate to its invocation result."  1952   1953         if ref:  1954             if ref.has_kind("<class>"):  1955                 return [ref]  1956             elif ref.has_kind("<function>"):  1957                 return self.convert_function_invocation(ref)  1958   1959         return [Reference("<var>")]  1960   1961     def convert_invocations(self, refs, invocation):  1962   1963         """  1964         Convert 'refs' to invocation results if 'invocation' is set to a true  1965         value.  1966         """  1967   1968         if not invocation:  1969             return refs  1970   1971         invocation_refs = set()  1972   1973         for ref in refs:  1974             invocation_refs.update(self.convert_invocation(ref))  1975   1976         return self.references_or_var(invocation_refs)  1977   1978     def convert_invocation(self, ref):  1979   1980         "Convert 'ref' to its invocation result."  1981   1982         if ref:  1983             if ref.has_kind("<class>"):  1984                 return [ref.instance_of()]  1985             elif ref.has_kind("<function>"):  1986                 return self.convert_function_invocation(ref)  1987   1988         return [Reference("<var>")]  1989   1990     def convert_function_invocation(self, ref):  1991   1992         "Convert the function 'ref' to its return value reference."  1993   1994         initialisers = self.importer.all_initialised_names.get((ref.get_origin(), "$return"))  1995         aliases = self.importer.all_aliased_names.get((ref.get_origin(), "$return"))  1996   1997         if initialisers and not aliases:  1998             return set(initialisers.values())  1999   2000         return [Reference("<var>")]  2001   2002     def references_or_var(self, refs):  2003   2004         var = Reference("<var>")  2005   2006         if var in refs:  2007             return set([var])  2008         else:  2009             return refs  2010   2011     def get_initialised_name(self, access_location):  2012   2013         """  2014         Return references for any initialised names at 'access_location', or  2015         None if no such references exist.  2016         """  2017   2018         path, name, attrnames, version = access_location  2019   2020         # Use initialiser information, if available.  2021   2022         initialisers = self.importer.all_initialised_names.get((path, name))  2023         if initialisers and initialisers.has_key(version):  2024             return [initialisers[version]]  2025         else:  2026             return None  2027   2028     def get_accessor_references(self, access_location):  2029   2030         """  2031         Return references corresponding to accessor details at the given  2032         'access_location'.  2033         """  2034   2035         if self.accessor_class_types.has_key(access_location):  2036             class_types = self.accessor_class_types[access_location]  2037             instance_types = self.accessor_instance_types[access_location]  2038             module_types = self.accessor_module_types[access_location]  2039             return combine_types(class_types, instance_types, module_types)  2040         else:  2041             return None  2042   2043     def get_provider_references(self, access_location):  2044   2045         """  2046         Return references corresponding to provider details at the given  2047         'access_location'.  2048         """  2049   2050         if self.provider_class_types.has_key(access_location):  2051             class_types = self.provider_class_types[access_location]  2052             instance_types = self.provider_instance_types[access_location]  2053             module_types = self.provider_module_types[access_location]  2054             return combine_types(class_types, instance_types, module_types)  2055         else:  2056             return None  2057   2058     def record_reference_types(self, location, class_types, instance_types,  2059         module_types, constrained, constrained_specific=False, invocations=None):  2060   2061         """  2062         Associate attribute provider types with the given 'location', consisting  2063         of the given 'class_types', 'instance_types' and 'module_types'.  2064   2065         If 'constrained' is indicated, the constrained nature of the accessor is  2066         recorded for the location.  2067   2068         If 'constrained_specific' is indicated using a true value, instance types  2069         will not be added to class types to permit access via instances at the  2070         given location. This is only useful where a specific accessor is known  2071         to be a class.  2072   2073         If 'invocations' is given, the given attribute names indicate those  2074         which are involved in invocations. Such invocations, if involving  2075         functions, will employ those functions as bound methods and will  2076         therefore not support classes as accessors, only instances of such  2077         classes.  2078   2079         Note that the specified types only indicate the provider types for  2080         attributes, whereas the recorded accessor types indicate the possible  2081         types of the actual objects used to access attributes.  2082         """  2083   2084         # Update the type details for the location.  2085   2086         self.update_provider_types(location, class_types, instance_types, module_types)  2087   2088         # Class types support classes and instances as accessors.  2089         # Instance-only and module types support only their own kinds as  2090         # accessors.  2091   2092         path, name, attrnames, version = location  2093   2094         if invocations:  2095             class_only_types = self.filter_for_invocations(class_types, invocations)  2096         else:  2097             class_only_types = class_types  2098   2099         # However, the nature of accessors can be further determined.  2100         # Any self variable may only refer to an instance.  2101   2102         if name != "self" or not self.in_method(path):  2103             self.accessor_class_types[location].update(class_only_types)  2104   2105         if not constrained_specific:  2106             self.accessor_instance_types[location].update(class_types)  2107   2108         self.accessor_instance_types[location].update(instance_types)  2109   2110         if name != "self" or not self.in_method(path):  2111             self.accessor_module_types[location].update(module_types)  2112   2113         if constrained:  2114             self.accessor_constrained.add(location)  2115   2116     def update_provider_types(self, location, class_types, instance_types, module_types):  2117   2118         """  2119         Update provider types for the given 'location', adding 'class_types',  2120         'instance_types' and 'module_types' to those already stored.  2121         """  2122   2123         self.provider_class_types[location].update(class_types)  2124         self.provider_instance_types[location].update(instance_types)  2125         self.provider_module_types[location].update(module_types)  2126   2127     def update_accessor_types(self, location, class_types, instance_types, module_types):  2128   2129         """  2130         Update accessor types for the given 'location', adding 'class_types',  2131         'instance_types' and 'module_types' to those already stored.  2132         """  2133   2134         self.accessor_class_types[location].update(class_types)  2135         self.accessor_instance_types[location].update(instance_types)  2136         self.accessor_module_types[location].update(module_types)  2137   2138     def filter_for_invocations(self, class_types, attrnames):  2139   2140         """  2141         From the given 'class_types', identify methods for the given  2142         'attrnames' that are being invoked, returning a filtered collection of  2143         class types.  2144   2145         This method may be used to remove class types from consideration where  2146         their attributes are methods that are directly invoked: method  2147         invocations must involve instance accessors.  2148         """  2149   2150         to_filter = set()  2151   2152         for class_type in class_types:  2153             for attrname in attrnames:  2154   2155                 # Attempt to obtain a class attribute of the given name. This  2156                 # may return an attribute provided by an ancestor class.  2157   2158                 ref = self.importer.get_class_attribute(class_type, attrname)  2159                 parent_class = ref and ref.parent()  2160   2161                 # If such an attribute is a method and would be available on  2162                 # the given class, record the class for filtering.  2163   2164                 if ref and ref.has_kind("<function>") and (  2165                    parent_class == class_type or  2166                    class_type in self.descendants[parent_class]):  2167   2168                     to_filter.add(class_type)  2169                     break  2170   2171         return set(class_types).difference(to_filter)  2172   2173     def identify_reference_attributes(self, location, attrname, class_types, instance_types, module_types, constrained):  2174   2175         """  2176         Identify reference attributes, associating them with the given  2177         'location', identifying the given 'attrname', employing the given  2178         'class_types', 'instance_types' and 'module_types'.  2179   2180         If 'constrained' is indicated, the constrained nature of the access is  2181         recorded for the location.  2182         """  2183   2184         # Record the referenced objects.  2185   2186         self.referenced_attrs[location] = \  2187             self._identify_reference_attribute(location, attrname, class_types, instance_types, module_types)  2188   2189         if constrained:  2190             self.access_constrained.add(location)  2191   2192     def _identify_reference_attribute(self, location, attrname, class_types, instance_types, module_types):  2193   2194         """  2195         Identify the reference attribute at the given access 'location', using  2196         the given 'attrname', and employing the given 'class_types',  2197         'instance_types' and 'module_types'.  2198         """  2199   2200         attrs = set()  2201   2202         # The class types expose class attributes either directly or via  2203         # instances.  2204   2205         for object_type in class_types:  2206             ref = self.importer.get_class_attribute(object_type, attrname)  2207             if ref and self.is_compatible_callable(location, object_type, ref):  2208                 attrs.add(("<class>", object_type, ref))  2209   2210             # Add any distinct instance attributes that would be provided  2211             # by instances also providing indirect class attribute access.  2212   2213             for ref in self.importer.get_instance_attributes(object_type, attrname):  2214                 if self.is_compatible_callable(location, object_type, ref):  2215                     attrs.add(("<instance>", object_type, ref))  2216   2217         # The instance-only types expose instance attributes, but although  2218         # classes are excluded as potential accessors (since they do not provide  2219         # the instance attributes), the class types may still provide some  2220         # attributes.  2221   2222         for object_type in instance_types:  2223             instance_attrs = self.importer.get_instance_attributes(object_type, attrname)  2224   2225             if instance_attrs:  2226                 for ref in instance_attrs:  2227                     if self.is_compatible_callable(location, object_type, ref):  2228                         attrs.add(("<instance>", object_type, ref))  2229             else:  2230                 ref = self.importer.get_class_attribute(object_type, attrname)  2231                 if ref and self.is_compatible_callable(location, object_type, ref):  2232                     attrs.add(("<class>", object_type, ref))  2233   2234         # Module types expose module attributes for module accessors.  2235   2236         for object_type in module_types:  2237             ref = self.importer.get_module_attribute(object_type, attrname)  2238             if ref and self.is_compatible_callable(location, object_type, ref):  2239                 attrs.add(("<module>", object_type, ref))  2240   2241         return attrs  2242   2243     def is_compatible_callable(self, location, object_type, ref):  2244   2245         """  2246         Return whether any invocation at 'location' involving an attribute of  2247         'object_type' identified by 'ref' is compatible with any arguments used.  2248         """  2249   2250         invocation = self.reference_invocations.get(location)  2251         if invocation is None:  2252             return True  2253   2254         objpath = ref.get_origin()  2255         if not objpath:  2256             return True  2257   2258         parameters = self.importer.function_parameters.get(objpath)  2259         if not parameters:  2260             return True  2261   2262         defaults = self.importer.function_defaults.get(objpath)  2263         arguments, keywords = invocation  2264         names = set(parameters)  2265   2266         # Determine whether the specified arguments are  2267         # compatible with the callable signature.  2268   2269         if arguments >= len(parameters) - len(defaults) and \  2270            arguments <= len(parameters) and \  2271            names.issuperset(keywords):  2272   2273             return True  2274         else:  2275             init_item(self.reference_invocations_unsuitable, location, set)  2276             self.reference_invocations_unsuitable[location].add(ref)  2277             return False  2278   2279     # Attribute access plan formulation.  2280   2281     class_tests = (  2282         ("guarded", "specific", "type"),  2283         ("guarded", "common", "type"),  2284         ("test", "specific", "type"),  2285         ("test", "common", "type"),  2286         )  2287   2288     def get_access_plan(self, location):  2289   2290         """  2291         Return details of the access at the given 'location'. The details are as  2292         follows:  2293   2294          * the initial accessor (from which accesses will be performed if no  2295            computed static accessor is found)  2296          * details of any test required on the initial accessor  2297          * details of any type employed by the test  2298          * any static accessor (from which accesses will be performed in  2299            preference to the initial accessor)  2300          * attributes needing to be traversed from the base that yield  2301            unambiguous objects  2302          * access modes for each of the unambiguously-traversed attributes  2303          * remaining attributes needing to be tested and traversed  2304          * details of the context  2305          * any test to apply to the context  2306          * the method of obtaining the first attribute  2307          * the method of obtaining the final attribute  2308          * any static final attribute  2309          * the kinds of objects providing the final attribute  2310         """  2311   2312         const_access = self.const_accesses_rev.get(location)  2313   2314         path, name, attrnames, version = location  2315         remaining = attrnames.split(".")  2316         attrname = remaining[0]  2317   2318         # Obtain reference, provider and provider kind information.  2319   2320         attrs = self.reference_all_attrs[location]  2321         provider_types = self.reference_all_providers[location]  2322         provider_kinds = self.reference_all_provider_kinds[location]  2323   2324         # Obtain accessor type and kind information.  2325   2326         accessor_types = self.reference_all_accessor_types[location]  2327         accessor_general_types = self.reference_all_accessor_general_types[location]  2328         accessor_kinds = get_kinds(accessor_general_types)  2329   2330         # Determine any guard or test requirements.  2331   2332         constrained = location in self.access_constrained  2333         test = self.reference_test_types[location]  2334         test_type = self.reference_test_accessor_type.get(location)  2335   2336         # Determine the accessor and provider properties.  2337   2338         class_accessor = "<class>" in accessor_kinds  2339         module_accessor = "<module>" in accessor_kinds  2340         instance_accessor = "<instance>" in accessor_kinds  2341         provided_by_class = "<class>" in provider_kinds  2342         provided_by_instance = "<instance>" in provider_kinds  2343   2344         # Determine how attributes may be accessed relative to the accessor.  2345   2346         object_relative = class_accessor or module_accessor or provided_by_instance  2347         class_relative = instance_accessor and provided_by_class  2348   2349         # Identify the last static attribute for context acquisition.  2350   2351         base = None  2352         dynamic_base = None  2353   2354         # Constant accesses have static providers.  2355   2356         if const_access:  2357             base = len(provider_types) == 1 and first(provider_types)  2358   2359         # Name-based accesses.  2360   2361         elif name:  2362             ref = self.importer.identify("%s.%s" % (path, name))  2363   2364             # Constant accessors are static.  2365   2366             if ref and ref.static():  2367                 base = ref.get_origin()  2368   2369             # Usage of previously-generated guard and test details.  2370   2371             elif test[:2] == ("constrained", "specific"):  2372                 ref = first(accessor_types)  2373   2374             elif test[:2] == ("constrained", "common"):  2375                 ref = first(accessor_general_types)  2376   2377             elif test[:2] == ("guarded", "specific"):  2378                 ref = first(accessor_types)  2379   2380             elif test[:2] == ("guarded", "common"):  2381                 ref = first(accessor_general_types)  2382   2383             # For attribute-based tests, tentatively identify a dynamic base.  2384             # Such tests allow single or multiple kinds of a type.  2385   2386             elif test[0] == "test" and test[1] in ("common", "specific"):  2387                 dynamic_base = test_type  2388   2389             # Static accessors.  2390   2391             if not base and test in self.class_tests:  2392                 base = ref and ref.get_origin() or dynamic_base  2393   2394             # Accessors that are not static but whose nature is determined.  2395   2396             elif not base and ref:  2397                 dynamic_base = ref.get_origin()  2398   2399         # Determine initial accessor details.  2400   2401         accessor = base or dynamic_base  2402         accessor_kind = len(accessor_kinds) == 1 and first(accessor_kinds) or None  2403         provider_kind = len(provider_kinds) == 1 and first(provider_kinds) or None  2404   2405         # Traverse remaining attributes.  2406   2407         traversed = []  2408         traversal_modes = []  2409   2410         while len(attrs) == 1 and not first(attrs).has_kind("<var>"):  2411             attr = first(attrs)  2412   2413             traversed.append(attrname)  2414             traversal_modes.append(accessor_kind == provider_kind and "object" or "class")  2415   2416             # Consume attribute names providing unambiguous attributes.  2417   2418             del remaining[0]  2419   2420             if not remaining:  2421                 break  2422   2423             # Update the last static attribute.  2424   2425             if attr.static():  2426                 base = attr.get_origin()  2427                 traversed = []  2428                 traversal_modes = []  2429   2430             # Get the access details.  2431   2432             attrname = remaining[0]  2433             accessor = attr.get_origin()  2434             accessor_kind = attr.get_kind()  2435             provider_kind = self.importer.get_attribute_provider(attr, attrname)  2436             accessor_kinds = [accessor_kind]  2437             provider_kinds = [provider_kind]  2438   2439             # Get the next attribute.  2440   2441             attrs = self.importer.get_attributes(attr, attrname)  2442   2443         # Where many attributes are suggested, no single attribute identity can  2444         # be loaded.  2445   2446         else:  2447             attr = None  2448   2449         # Determine the method of access.  2450   2451         is_assignment = location in self.reference_assignments or const_access in self.reference_assignments  2452         is_invocation = location in self.reference_invocations or const_access in self.reference_invocations  2453   2454         # Identified attribute that must be accessed via its parent.  2455   2456         if attr and attr.get_name() and is_assignment:  2457             final_method = "static-assign"; origin = attr.get_name()  2458   2459         # Static, identified attribute.  2460   2461         elif attr and attr.static():  2462             final_method = is_assignment and "static-assign" or \  2463                            is_invocation and "static-invoke" or \  2464                            "static"  2465             origin = attr.final()  2466   2467         # All other methods of access involve traversal.  2468   2469         else:  2470             final_method = is_assignment and "assign" or \  2471                            is_invocation and "access-invoke" or \  2472                            "access"  2473             origin = None  2474   2475         # First attribute accessed at a known position via the accessor.  2476   2477         # Static bases support object-relative accesses only.  2478   2479         if base:  2480             first_method = "relative-object"  2481   2482         # Dynamic bases support either object- or class-relative accesses.  2483   2484         elif dynamic_base:  2485             first_method = "relative" + (object_relative and "-object" or "") + \  2486                                         (class_relative and "-class" or "")  2487   2488         # The fallback case is always run-time testing and access.  2489   2490         else:  2491             first_method = "check" + (object_relative and "-object" or "") + \  2492                                      (class_relative and "-class" or "")  2493   2494         # Determine whether an unbound method is being accessed via an instance,  2495         # requiring a context test.  2496   2497         context_test = "ignore"  2498   2499         # Assignments do not employ the context.  2500   2501         if is_assignment:  2502             pass  2503   2504         # Obtain a selection of possible attributes if no unambiguous attribute  2505         # was identified.  2506   2507         elif not attr:  2508   2509             # Use previously-deduced attributes for a simple ambiguous access.  2510             # Otherwise, use the final attribute name to obtain possible  2511             # attributes.  2512   2513             if len(remaining) > 1:  2514                 attrname = remaining[-1]  2515   2516                 (class_types,  2517                  only_instance_types,  2518                  module_types) = self.get_types_for_attribute(attrname)  2519   2520                 accessor_kinds = set()  2521                 provider_kinds = set()  2522   2523                 if class_types:  2524                     accessor_kinds.add("<class>")  2525                     accessor_kinds.add("<instance>")  2526                     provider_kinds.add("<class>")  2527                 if only_instance_types:  2528                     accessor_kinds.add("<instance>")  2529                     provider_kinds.add("<instance>")  2530                 if module_types:  2531                     accessor_kinds.add("<module>")  2532                     provider_kinds.add("<module>")  2533   2534                 attrs = set()  2535                 for type in combine_types(class_types, only_instance_types, module_types):  2536                     attrs.update(self.importer.get_attributes(type, attrname))  2537   2538             always_unbound = True  2539             have_function = False  2540             have_var = False  2541   2542             # Determine whether all attributes are unbound methods and whether  2543             # functions or unidentified attributes occur.  2544   2545             for attr in attrs:  2546                 always_unbound = always_unbound and attr.has_kind("<function>") and attr.name_parent() == attr.parent()  2547                 have_function = have_function or attr.has_kind("<function>")  2548                 have_var = have_var or attr.has_kind("<var>")  2549   2550             # Test for class-via-instance accesses.  2551   2552             if accessor_kind == "<instance>" and \  2553                provider_kind == "<class>":  2554   2555                 if always_unbound:  2556                     context_test = "replace"  2557                 else:  2558                     context_test = "test"  2559   2560             # Test for the presence of class-via-instance accesses.  2561   2562             elif "<instance>" in accessor_kinds and \  2563                  "<class>" in provider_kinds and \  2564                  (have_function or have_var):  2565   2566                 context_test = "test"  2567   2568         # With an unambiguous attribute, determine whether a test is needed.  2569   2570         elif accessor_kind == "<instance>" and \  2571              provider_kind == "<class>" and \  2572              (attr.has_kind("<var>") or  2573               attr.has_kind("<function>") and  2574               attr.name_parent() == attr.parent()):  2575   2576             if attr.has_kind("<var>"):  2577                 context_test = "test"  2578             else:  2579                 context_test = "replace"  2580   2581         # With an unambiguous attribute with ambiguity in the access method,  2582         # generate a test.  2583   2584         elif "<instance>" in accessor_kinds and \  2585              "<class>" in provider_kinds and \  2586              (attr.has_kind("<var>") or  2587               attr.has_kind("<function>") and  2588               attr.name_parent() == attr.parent()):  2589   2590             context_test = "test"  2591   2592         # Determine the nature of the context.  2593   2594         context = context_test == "ignore" and "unset" or \  2595                   len(traversed + remaining) == 1 and \  2596                       (base and "base" or "original-accessor") or \  2597                   "final-accessor"  2598   2599         return name, test, test_type, base, \  2600                traversed, traversal_modes, remaining, \  2601                context, context_test, \  2602                first_method, final_method, \  2603                origin, accessor_kinds  2604   2605     def initialise_access_instructions(self):  2606   2607         "Expand access plans into instruction sequences."  2608   2609         for access_location, access_plan in self.access_plans.items():  2610   2611             # Obtain the access details.  2612   2613             name, test, test_type, base, \  2614                 traversed, traversal_modes, attrnames, \  2615                 context, context_test, \  2616                 first_method, final_method, \  2617                 origin, accessor_kinds = access_plan  2618   2619             # Emit instructions by appending them to a list.  2620   2621             instructions = []  2622             emit = instructions.append  2623   2624             # Identify any static original accessor.  2625   2626             if base:  2627                 original_accessor = base  2628   2629             # Employ names as contexts unless the context needs testing and  2630             # potentially updating. In such cases, temporary context storage is  2631             # used instead.  2632   2633             elif name and not (context_test == "test" and  2634                                final_method in ("access-invoke", "static-invoke")):  2635                 original_accessor = "<name>" # refers to the name  2636   2637             # Use a generic placeholder representing the access expression in  2638             # the general case.  2639   2640             else:  2641                 original_accessor = "<expr>"  2642   2643             # Prepare for any first attribute access.  2644   2645             if traversed:  2646                 attrname = traversed[0]  2647                 del traversed[0]  2648             elif attrnames:  2649                 attrname = attrnames[0]  2650                 del attrnames[0]  2651   2652             # Perform the first access explicitly if at least one operation  2653             # requires it.  2654   2655             access_first_attribute = final_method in ("access", "access-invoke", "assign") or traversed or attrnames  2656   2657             # Determine whether the first access involves assignment.  2658   2659             assigning = not traversed and not attrnames and final_method == "assign"  2660             set_accessor = assigning and "<set_target_accessor>" or "<set_accessor>"  2661             stored_accessor = assigning and "<target_accessor>" or "<accessor>"  2662   2663             # Set the context if already available.  2664   2665             context_var = None  2666   2667             if context == "base":  2668                 accessor = context_var = (base,)  2669             elif context == "original-accessor":  2670   2671                 # Prevent re-evaluation of any dynamic expression by storing it.  2672   2673                 if original_accessor == "<expr>":  2674                     if final_method in ("access-invoke", "static-invoke"):  2675                         emit(("<set_context>", original_accessor))  2676                         accessor = context_var = ("<context>",)  2677                     else:  2678                         emit((set_accessor, original_accessor))  2679                         accessor = context_var = (stored_accessor,)  2680                 else:  2681                     accessor = context_var = (original_accessor,)  2682   2683             # Assigning does not set the context.  2684   2685             elif context in ("final-accessor", "unset") and access_first_attribute:  2686   2687                 # Prevent re-evaluation of any dynamic expression by storing it.  2688   2689                 if original_accessor == "<expr>":  2690                     emit((set_accessor, original_accessor))  2691                     accessor = (stored_accessor,)  2692                 else:  2693                     accessor = (original_accessor,)  2694   2695             # Apply any test.  2696   2697             if test[0] == "test":  2698                 accessor = ("__%s_%s_%s" % test, accessor, test_type)  2699   2700             # Perform the first or final access.  2701             # The access only needs performing if the resulting accessor is used.  2702   2703             remaining = len(traversed + attrnames)  2704   2705             if access_first_attribute:  2706   2707                 if first_method == "relative-class":  2708                     if assigning:  2709                         emit(("__store_via_class", accessor, attrname, "<assexpr>"))  2710                     else:  2711                         accessor = ("__load_via_class", accessor, attrname)  2712   2713                 elif first_method == "relative-object":  2714                     if assigning:  2715                         emit(("__store_via_object", accessor, attrname, "<assexpr>"))  2716                     else:  2717                         accessor = ("__load_via_object", accessor, attrname)  2718   2719                 elif first_method == "relative-object-class":  2720                     if assigning:  2721                         emit(("__get_class_and_store", accessor, attrname, "<assexpr>"))  2722                     else:  2723                         accessor = ("__get_class_and_load", accessor, attrname)  2724   2725                 elif first_method == "check-class":  2726                     if assigning:  2727                         emit(("__check_and_store_via_class", accessor, attrname, "<assexpr>"))  2728                     else:  2729                         accessor = ("__check_and_load_via_class", accessor, attrname)  2730   2731                 elif first_method == "check-object":  2732                     if assigning:  2733                         emit(("__check_and_store_via_object", accessor, attrname, "<assexpr>"))  2734                     else:  2735                         accessor = ("__check_and_load_via_object", accessor, attrname)  2736   2737                 elif first_method == "check-object-class":  2738                     if assigning:  2739                         emit(("__check_and_store_via_any", accessor, attrname, "<assexpr>"))  2740                     else:  2741                         accessor = ("__check_and_load_via_any", accessor, attrname)  2742   2743             # Traverse attributes using the accessor.  2744   2745             if traversed:  2746                 for attrname, traversal_mode in zip(traversed, traversal_modes):  2747                     assigning = remaining == 1 and final_method == "assign"  2748   2749                     # Set the context, if appropriate.  2750   2751                     if remaining == 1 and final_method != "assign" and context == "final-accessor":  2752   2753                         # Invoked attributes employ a separate context accessed  2754                         # during invocation.  2755   2756                         if final_method in ("access-invoke", "static-invoke"):  2757                             emit(("<set_context>", accessor))  2758                             accessor = context_var = "<context>"  2759   2760                         # A private context within the access is otherwise  2761                         # retained.  2762   2763                         else:  2764                             emit(("<set_private_context>", accessor))  2765                             accessor = context_var = "<private_context>"  2766   2767                     # Perform the access only if not achieved directly.  2768   2769                     if remaining > 1 or final_method in ("access", "access-invoke", "assign"):  2770   2771                         if traversal_mode == "class":  2772                             if assigning:  2773                                 emit(("__store_via_class", accessor, attrname, "<assexpr>"))  2774                             else:  2775                                 accessor = ("__load_via_class", accessor, attrname)  2776                         else:  2777                             if assigning:  2778                                 emit(("__store_via_object", accessor, attrname, "<assexpr>"))  2779                             else:  2780                                 accessor = ("__load_via_object", accessor, attrname)  2781   2782                     remaining -= 1  2783   2784             if attrnames:  2785                 for attrname in attrnames:  2786                     assigning = remaining == 1 and final_method == "assign"  2787   2788                     # Set the context, if appropriate.  2789   2790                     if remaining == 1 and final_method != "assign" and context == "final-accessor":  2791   2792                         # Invoked attributes employ a separate context accessed  2793                         # during invocation.  2794   2795                         if final_method in ("access-invoke", "static-invoke"):  2796                             emit(("<set_context>", accessor))  2797                             accessor = context_var = "<context>"  2798   2799                         # A private context within the access is otherwise  2800                         # retained.  2801   2802                         else:  2803                             emit(("<set_private_context>", accessor))  2804                             accessor = context_var = "<private_context>"  2805   2806                     # Perform the access only if not achieved directly.  2807   2808                     if remaining > 1 or final_method in ("access", "access-invoke", "assign"):  2809   2810                         # Constrain instructions involving certain special  2811                         # attribute names.  2812   2813                         to_search = attrname == "__data__" and "object" or "any"  2814   2815                         if assigning:  2816                             emit(("__check_and_store_via_%s" % to_search, accessor, attrname, "<assexpr>"))  2817                         else:  2818                             accessor = ("__check_and_load_via_%s" % to_search, accessor, attrname)  2819   2820                     remaining -= 1  2821   2822             # Define or emit the means of accessing the actual target.  2823   2824             # Assignments to known attributes.  2825   2826             if final_method == "static-assign":  2827                 parent, attrname = origin.rsplit(".", 1)  2828                 emit(("__store_via_object", parent, attrname, "<assexpr>"))  2829   2830             # Invoked attributes employ a separate context.  2831   2832             elif final_method in ("static", "static-invoke"):  2833                 accessor = ("__load_static_ignore", origin)  2834   2835             # Wrap accesses in context operations.  2836   2837             if context_test == "test":  2838   2839                 # Test and combine the context with static attribute details.  2840   2841                 if final_method == "static":  2842                     emit(("__load_static_test", context_var, origin))  2843   2844                 # Test the context, storing it separately if required for the  2845                 # immediately invoked static attribute.  2846   2847                 elif final_method == "static-invoke":  2848                     emit(("<test_context_static>", context_var, origin))  2849   2850                 # Test the context, storing it separately if required for an  2851                 # immediately invoked attribute.  2852   2853                 elif final_method == "access-invoke":  2854                     emit(("<test_context_revert>", context_var, accessor))  2855   2856                 # Test the context and update the attribute details if  2857                 # appropriate.  2858   2859                 else:  2860                     emit(("__test_context", context_var, accessor))  2861   2862             elif context_test == "replace":  2863   2864                 # Produce an object with updated context.  2865   2866                 if final_method == "static":  2867                     emit(("__load_static_replace", context_var, origin))  2868   2869                 # Omit the context update operation where the target is static  2870                 # and the context is recorded separately.  2871   2872                 elif final_method == "static-invoke":  2873                     pass  2874   2875                 # If a separate context is used for an immediate invocation,  2876                 # produce the attribute details unchanged.  2877   2878                 elif final_method == "access-invoke":  2879                     emit(accessor)  2880   2881                 # Update the context in the attribute details.  2882   2883                 else:  2884                     emit(("__update_context", context_var, accessor))  2885   2886             # Omit the accessor for assignments and for invocations of static  2887             # targets.  2888   2889             elif final_method not in ("assign", "static-assign", "static-invoke"):  2890                 emit(accessor)  2891   2892             # Produce an advisory instruction regarding the context.  2893   2894             if context_var:  2895                 if context_test in ("ignore", "replace"):  2896                     emit(("<context_identity_verified>", context_var))  2897                 else:  2898                     emit(("<context_identity>", context_var))  2899   2900             # Produce an advisory instruction regarding the final attribute.  2901   2902             if origin:  2903                 emit(("<final_identity>", origin))  2904   2905             self.access_instructions[access_location] = instructions  2906             self.accessor_kinds[access_location] = accessor_kinds  2907   2908 # vim: tabstop=4 expandtab shiftwidth=4