Lichen

deducer.py

769:00e902870a29
2017-03-25 Paul Boddie Merged changes from the normal-function-parameters branch, making it the default line of development from now on.
     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 module-level paths.   727    728             if self.importer.modules.has_key(path):   729                 module_name = path   730    731             # Identify the module containing other paths.   732    733             else:   734                 ref = self.importer.identify(path)   735                 for objpath in ref.ancestors():   736                     if self.importer.modules.has_key(objpath):   737                         module_name = objpath   738                         break   739                 else:   740                     raise DeduceError("Cannot find module for path %s." % path)   741    742             # Identify references providing dependencies.   743    744             for attrtype, objtype, attr in referenced_attrs:   745                 self.importer.add_dependency(path, attr.get_origin())   746    747     def get_referenced_attrs(self, location):   748    749         """   750         Return attributes referenced at the given access 'location' by the given   751         'attrname' as a list of (attribute type, attribute set) tuples.   752         """   753    754         d = {}   755         for attrtype, objtype, attr in self.referenced_attrs[location]:   756             init_item(d, attrtype, set)   757             d[attrtype].add(attr.unaliased())   758         l = d.items()   759         l.sort() # class, module, instance   760         return l   761    762     # Initialisation methods.   763    764     def init_descendants(self):   765    766         "Identify descendants of each class."   767    768         for name in self.importer.classes.keys():   769             self.get_descendants_for_class(name)   770    771     def get_descendants_for_class(self, name):   772    773         """   774         Use subclass information to deduce the descendants for the class of the   775         given 'name'.   776         """   777    778         if not self.descendants.has_key(name):   779             descendants = set()   780    781             for subclass in self.importer.subclasses[name]:   782                 descendants.update(self.get_descendants_for_class(subclass))   783                 descendants.add(subclass)   784    785             self.descendants[name] = descendants   786    787         return self.descendants[name]   788    789     def init_special_attributes(self):   790    791         "Add special attributes to the classes for inheritance-related tests."   792    793         all_class_attrs = self.importer.all_class_attrs   794    795         for name, descendants in self.descendants.items():   796             for descendant in descendants:   797                 all_class_attrs[descendant]["#%s" % name] = name   798    799         for name in all_class_attrs.keys():   800             all_class_attrs[name]["#%s" % name] = name   801    802     def init_usage_index(self):   803    804         """   805         Create indexes for module and function attribute usage and for anonymous   806         accesses.   807         """   808    809         for module in self.importer.get_modules():   810             for path, assignments in module.attr_usage.items():   811                 self.add_usage(assignments, path)   812    813         for location, all_attrnames in self.importer.all_attr_accesses.items():   814             for attrnames in all_attrnames:   815                 attrname = get_attrnames(attrnames)[-1]   816                 access_location = (location, None, attrnames, 0)   817                 self.add_usage_term(access_location, ((attrname, False, False),))   818    819     def add_usage(self, assignments, path):   820    821         """   822         Collect usage from the given 'assignments', adding 'path' details to   823         each record if specified. Add the usage to an index mapping to location   824         information, as well as to an index mapping locations to usages.   825         """   826    827         for name, versions in assignments.items():   828             for i, usages in enumerate(versions):   829                 location = (path, name, None, i)   830    831                 for usage in usages:   832                     self.add_usage_term(location, usage)   833    834     def add_usage_term(self, location, usage):   835    836         """   837         For 'location' and using 'usage' as a description of usage, record   838         in the usage index a mapping from the usage to 'location', and record in   839         the location index a mapping from 'location' to the usage.   840         """   841    842         init_item(self.location_index, location, set)   843         self.location_index[location].add(usage)   844    845     def init_accessors(self):   846    847         "Create indexes for module and function accessor information."   848    849         for module in self.importer.get_modules():   850             for path, all_accesses in module.attr_accessors.items():   851                 self.add_accessors(all_accesses, path)   852    853     def add_accessors(self, all_accesses, path):   854    855         """   856         For attribute accesses described by the mapping of 'all_accesses' from   857         name details to accessor details, record the locations of the accessors   858         for each access.   859         """   860    861         # Get details for each access combining the given name and attribute.   862    863         for (name, attrnames), accesses in all_accesses.items():   864    865             # Obtain the usage details using the access information.   866    867             for access_number, versions in enumerate(accesses):   868                 access_location = (path, name, attrnames, access_number)   869                 locations = []   870    871                 for version in versions:   872                     location = (path, name, None, version)   873                     locations.append(location)   874    875                     # Map accessors to affected accesses.   876    877                     l = init_item(self.access_index_rev, location, set)   878                     l.add(access_location)   879    880                 # Map accesses to supplying accessors.   881    882                 self.access_index[access_location] = locations   883    884     def get_accessors_for_access(self, access_location):   885    886         "Find a definition providing accessor details, if necessary."   887    888         try:   889             return self.access_index[access_location]   890         except KeyError:   891             return [access_location]   892    893     def init_accesses(self):   894    895         """   896         Check that attributes used in accesses are actually defined on some   897         object. This can be overlooked if unknown attributes are employed in   898         attribute chains.   899    900         Initialise collections for accesses involving assignments.   901         """   902    903         # For each scope, obtain access details.   904    905         for path, all_accesses in self.importer.all_attr_access_modifiers.items():   906    907             # For each combination of name and attribute names, obtain   908             # applicable modifiers.   909    910             for (name, attrname_str), modifiers in all_accesses.items():   911    912                 # For each access, determine the name versions affected by   913                 # assignments.   914    915                 for access_number, (assignment, invocation) in enumerate(modifiers):   916    917                     if name:   918                         access_location = (path, name, attrname_str, access_number)   919                     else:   920                         access_location = (path, None, attrname_str, 0)   921    922                     # Plain name accesses do not employ attributes and are   923                     # ignored. Whether they are invoked is of interest, however.   924    925                     if not attrname_str:   926                         if invocation:   927                             self.reference_invocations[access_location] = invocation   928                         continue   929    930                     attrnames = get_attrnames(attrname_str)   931    932                     # Check the attribute names.   933    934                     for attrname in attrnames:   935                         if not attrname in self.all_attrnames:   936                             raise DeduceError("In %s, attribute %s is not defined in the program." % (path, attrname))   937    938                     # Now only process assignments and invocations.   939    940                     if invocation:   941                         self.reference_invocations[access_location] = invocation   942                         continue   943                     elif not assignment:   944                         continue   945    946                     # Associate assignments with usage.   947    948                     self.reference_assignments.add(access_location)   949    950                     # Assignment occurs for the only attribute.   951    952                     if len(attrnames) == 1:   953                         accessor_locations = self.get_accessors_for_access(access_location)   954    955                         for location in accessor_locations:   956                             for usage in self.location_index[location]:   957                                 init_item(self.assigned_attrs, usage, set)   958                                 self.assigned_attrs[usage].add((path, name, attrnames[0]))   959    960                     # Assignment occurs for the final attribute.   961    962                     else:   963                         usage = ((attrnames[-1], False, False),)   964                         init_item(self.assigned_attrs, usage, set)   965                         self.assigned_attrs[usage].add((path, name, attrnames[-1]))   966    967     def init_aliases(self):   968    969         "Expand aliases so that alias-based accesses can be resolved."   970    971         # Get aliased names with details of their accesses.   972    973         for (path, name), all_aliases in self.importer.all_aliased_names.items():   974    975             # For each version of the name, obtain the access locations.   976    977             for version, aliases in all_aliases.items():   978                 for (original_path, original_name, attrnames, access_number) in aliases:   979                     accessor_location = (path, name, None, version)   980                     access_location = (original_path, original_name, attrnames, access_number)   981                     init_item(self.alias_index, accessor_location, list)   982                     self.alias_index[accessor_location].append(access_location)   983    984         # Get aliases in terms of non-aliases and accesses.   985    986         for accessor_location, access_locations in self.alias_index.items():   987             self.update_aliases(accessor_location, access_locations)   988    989         # Get a mapping from accesses to affected aliases.   990    991         for accessor_location, access_locations in self.alias_index.items():   992             for access_location in access_locations:   993                 init_item(self.alias_index_rev, access_location, set)   994                 self.alias_index_rev[access_location].add(accessor_location)   995    996     def update_aliases(self, accessor_location, access_locations, visited=None):   997    998         """   999         Update the given 'accessor_location' defining an alias, update  1000         'access_locations' to refer to non-aliases, following name references  1001         via the access index.  1002   1003         If 'visited' is specified, it contains a set of accessor locations (and  1004         thus keys to the alias index) that are currently being defined.  1005         """  1006   1007         if visited is None:  1008             visited = set()  1009   1010         updated_locations = set()  1011   1012         for access_location in access_locations:  1013             (path, original_name, attrnames, access_number) = access_location  1014   1015             # Locations may have been recorded for return values, but they may  1016             # not correspond to actual accesses.  1017   1018             if not self.access_index.has_key(access_location):  1019                 updated_locations.add(access_location)  1020   1021             # Where an alias refers to a name access, obtain the original name  1022             # version details.  1023   1024             elif attrnames is None:  1025   1026                 # For each name version, attempt to determine any accesses that  1027                 # initialise the name.  1028   1029                 for name_accessor_location in self.access_index[access_location]:  1030   1031                     # Already-visited aliases do not contribute details.  1032   1033                     if name_accessor_location in visited:  1034                         continue  1035   1036                     visited.add(name_accessor_location)  1037   1038                     name_access_locations = self.alias_index.get(name_accessor_location)  1039                     if name_access_locations:  1040                         updated_locations.update(self.update_aliases(name_accessor_location, name_access_locations, visited))  1041                     else:  1042                         updated_locations.add(name_accessor_location)  1043   1044             # Otherwise, record the access details.  1045   1046             else:  1047                 updated_locations.add(access_location)  1048   1049         self.alias_index[accessor_location] = updated_locations  1050         return updated_locations  1051   1052     # Attribute mutation for types.  1053   1054     def modify_mutated_attributes(self):  1055   1056         "Identify known, mutated attributes and change their state."  1057   1058         # Usage-based accesses.  1059   1060         for usage, all_attrnames in self.assigned_attrs.items():  1061             if not usage:  1062                 continue  1063   1064             for path, name, attrname in all_attrnames:  1065                 class_types = self.get_class_types_for_usage(usage)  1066                 only_instance_types = set(self.get_instance_types_for_usage(usage)).difference(class_types)  1067                 module_types = self.get_module_types_for_usage(usage)  1068   1069                 # Detect self usage within methods in order to narrow the scope  1070                 # of the mutation.  1071   1072                 t = name == "self" and self.constrain_self_reference(path, class_types, only_instance_types)  1073                 if t:  1074                     class_types, only_instance_types, module_types, constrained = t  1075                 objects = set(class_types).union(only_instance_types).union(module_types)  1076   1077                 self.mutate_attribute(objects, attrname)  1078   1079     def mutate_attribute(self, objects, attrname):  1080   1081         "Mutate static 'objects' with the given 'attrname'."  1082   1083         for name in objects:  1084             attr = "%s.%s" % (name, attrname)  1085             value = self.importer.get_object(attr)  1086   1087             # If the value is None, the attribute is  1088             # inherited and need not be set explicitly on  1089             # the class concerned.  1090   1091             if value:  1092                 self.modified_attributes[attr] = value  1093                 self.importer.set_object(attr, value.as_var())  1094   1095     # Simplification of types.  1096   1097     def get_most_general_types(self, types):  1098   1099         "Return the most general types for the given 'types'."  1100   1101         module_types = set()  1102         class_types = set()  1103   1104         for type in types:  1105             ref = self.importer.identify(type)  1106             if ref.has_kind("<module>"):  1107                 module_types.add(type)  1108             else:  1109                 class_types.add(type)  1110   1111         types = set(self.get_most_general_module_types(module_types))  1112         types.update(self.get_most_general_class_types(class_types))  1113         return types  1114   1115     def get_most_general_class_types(self, class_types):  1116   1117         "Return the most general types for the given 'class_types'."  1118   1119         class_types = set(class_types)  1120         to_remove = set()  1121   1122         for class_type in class_types:  1123             for base in self.importer.classes[class_type]:  1124                 base = base.get_origin()  1125                 descendants = self.descendants[base]  1126                 if base in class_types and descendants.issubset(class_types):  1127                     to_remove.update(descendants)  1128   1129         class_types.difference_update(to_remove)  1130         return class_types  1131   1132     def get_most_general_module_types(self, module_types):  1133   1134         "Return the most general type for the given 'module_types'."  1135   1136         # Where all modules are provided, an object would provide the same  1137         # attributes.  1138   1139         if len(module_types) == len(self.importer.modules):  1140             return [self.root_class_type]  1141         else:  1142             return module_types  1143   1144     # More efficient usage-to-type indexing and retrieval.  1145   1146     def init_attr_type_indexes(self):  1147   1148         "Identify the types that can support each attribute name."  1149   1150         self._init_attr_type_index(self.attr_class_types, self.importer.all_class_attrs)  1151         self._init_attr_type_index(self.attr_instance_types, self.importer.all_instance_attrs, True)  1152         self._init_attr_type_index(self.attr_instance_types, self.importer.all_combined_attrs, False)  1153         self._init_attr_type_index(self.attr_module_types, self.importer.all_module_attrs)  1154   1155     def _init_attr_type_index(self, attr_types, attrs, assignment=None):  1156   1157         """  1158         Initialise the 'attr_types' attribute-to-types mapping using the given  1159         'attrs' type-to-attributes mapping.  1160         """  1161   1162         for name, attrnames in attrs.items():  1163             for attrname in attrnames:  1164   1165                 # Permit general access for certain kinds of object.  1166   1167                 if assignment is None:  1168                     init_item(attr_types, (attrname, False), set)  1169                     init_item(attr_types, (attrname, True), set)  1170                     attr_types[(attrname, False)].add(name)  1171                     attr_types[(attrname, True)].add(name)  1172   1173                 # Restrict attribute assignment for instances.  1174   1175                 else:  1176                     init_item(attr_types, (attrname, assignment), set)  1177                     attr_types[(attrname, assignment)].add(name)  1178   1179     def get_class_types_for_usage(self, usage):  1180   1181         "Return names of classes supporting the given 'usage'."  1182   1183         return self._get_types_for_usage(usage, self.attr_class_types, self.importer.all_class_attrs)  1184   1185     def get_instance_types_for_usage(self, usage):  1186   1187         """  1188         Return names of classes whose instances support the given 'usage'  1189         (as either class or instance attributes).  1190         """  1191   1192         return self._get_types_for_usage(usage, self.attr_instance_types, self.importer.all_combined_attrs)  1193   1194     def get_module_types_for_usage(self, usage):  1195   1196         "Return names of modules supporting the given 'usage'."  1197   1198         return self._get_types_for_usage(usage, self.attr_module_types, self.importer.all_module_attrs)  1199   1200     def _get_types_for_usage(self, usage, attr_types, attrs):  1201   1202         """  1203         For the given 'usage' representing attribute usage, return types  1204         recorded in the 'attr_types' attribute-to-types mapping that support  1205         such usage, with the given 'attrs' type-to-attributes mapping used to  1206         quickly assess whether a type supports all of the stated attributes.  1207         """  1208   1209         # Where no attributes are used, any type would be acceptable.  1210   1211         if not usage:  1212             return attrs.keys()  1213   1214         keys = []  1215         for attrname, invocation, assignment in usage:  1216             keys.append((attrname, assignment))  1217   1218         # Obtain types supporting the first (attribute name, assignment) key...  1219   1220         types = set(attr_types.get(keys[0]) or [])  1221   1222         for key in keys[1:]:  1223               1224             # Record types that support all of the other attributes as well.  1225   1226             types.intersection_update(attr_types.get(key) or [])  1227   1228         return types  1229   1230     def init_combined_attribute_index(self):  1231   1232         "Initialise a combined index for the detection of invalid attributes."  1233   1234         self.all_attrnames = set()  1235         for attrs in (self.importer.all_combined_attrs, self.importer.all_module_attrs):  1236             for name, attrnames in attrs.items():  1237                 self.all_attrnames.update(attrnames)  1238   1239     # Reference identification.  1240   1241     def identify_references(self):  1242   1243         "Identify references using usage and name reference information."  1244   1245         # Names with associated attribute usage.  1246   1247         for location, usages in self.location_index.items():  1248   1249             # Obtain attribute usage associated with a name, deducing the nature  1250             # of the name. Obtain types only for branches involving attribute  1251             # usage. (In the absence of usage, any type could be involved, but  1252             # then no accesses exist to require knowledge of the type.)  1253   1254             have_usage = False  1255             have_no_usage_branch = False  1256   1257             for usage in usages:  1258                 if not usage:  1259                     have_no_usage_branch = True  1260                     continue  1261                 elif not have_usage:  1262                     self.init_definition_details(location)  1263                     have_usage = True  1264                 self.record_types_for_usage(location, usage)  1265   1266             # Where some usage occurs, but where branches without usage also  1267             # occur, record the types for those branches anyway.  1268   1269             if have_usage and have_no_usage_branch:  1270                 self.init_definition_details(location)  1271                 self.record_types_for_usage(location, None)  1272   1273         # Specific name-based attribute accesses.  1274   1275         for access_location, accessor_locations in self.access_index.items():  1276             self.record_types_for_access(access_location, accessor_locations)  1277   1278         # Anonymous references with attribute chains.  1279   1280         for location, accesses in self.importer.all_attr_accesses.items():  1281   1282             # Get distinct attribute names.  1283   1284             all_attrnames = set()  1285   1286             for attrnames in accesses:  1287                 all_attrnames.update(get_attrnames(attrnames))  1288   1289             # Get attribute and accessor details for each attribute name.  1290   1291             for attrname in all_attrnames:  1292                 access_location = (location, None, attrname, 0)  1293                 self.record_types_for_attribute(access_location, attrname)  1294   1295         # References via constant/identified objects.  1296   1297         for location, name_accesses in self.importer.all_const_accesses.items():  1298   1299             # A mapping from the original name and attributes to resolved access  1300             # details.  1301   1302             for original_access, access in name_accesses.items():  1303                 original_name, original_attrnames = original_access  1304                 objpath, ref, attrnames = access  1305   1306                 # Build an accessor combining the name and attribute names used.  1307   1308                 original_accessor = tuple([original_name] + original_attrnames.split("."))  1309   1310                 # Direct accesses to attributes.  1311   1312                 if not attrnames:  1313   1314                     # Build a descriptive location based on the original  1315                     # details, exposing the final attribute name.  1316   1317                     oa, attrname = original_accessor[:-1], original_accessor[-1]  1318                     oa = ".".join(oa)  1319   1320                     access_location = (location, oa, attrname, 0)  1321                     accessor_location = (location, oa, None, 0)  1322                     self.access_index[access_location] = [accessor_location]  1323   1324                     self.init_access_details(access_location)  1325                     self.init_definition_details(accessor_location)  1326   1327                     # Obtain a reference for the accessor in order to properly  1328                     # determine its type.  1329   1330                     if ref.get_kind() != "<instance>":  1331                         objpath = ref.get_origin()  1332   1333                     objpath = objpath.rsplit(".", 1)[0]  1334   1335                     # Where the object name conflicts with the module  1336                     # providing it, obtain the module details.  1337   1338                     if objpath in self.importer.modules:  1339                         accessor = Reference("<module>", objpath)  1340                     else:  1341                         accessor = self.importer.get_object(objpath)  1342   1343                     self.referenced_attrs[access_location] = [(accessor.get_kind(), accessor.get_origin(), ref)]  1344                     self.access_constrained.add(access_location)  1345   1346                     class_types, instance_types, module_types = accessor.get_types()  1347                     self.record_reference_types(accessor_location, class_types, instance_types, module_types, True, True)  1348   1349                 else:  1350   1351                     # Build a descriptive location based on the original  1352                     # details, employing the first remaining attribute name.  1353   1354                     l = get_attrnames(attrnames)  1355                     attrname = l[0]  1356   1357                     oa = original_accessor[:-len(l)]  1358                     oa = ".".join(oa)  1359   1360                     access_location = (location, oa, attrnames, 0)  1361                     accessor_location = (location, oa, None, 0)  1362                     self.access_index[access_location] = [accessor_location]  1363   1364                     self.init_access_details(access_location)  1365                     self.init_definition_details(accessor_location)  1366   1367                     class_types, instance_types, module_types = ref.get_types()  1368   1369                     self.identify_reference_attributes(access_location, attrname, class_types, instance_types, module_types, True)  1370                     self.record_reference_types(accessor_location, class_types, instance_types, module_types, True, True)  1371   1372                 # Define mappings between the original and access locations  1373                 # so that translation can work from the source details.  1374   1375                 original_location = (location, original_name, original_attrnames, 0)  1376   1377                 if original_location != access_location:  1378                     self.const_accesses[original_location] = access_location  1379                     self.const_accesses_rev[access_location] = original_location  1380   1381         # Propagate alias-related information.  1382   1383         affected_aliases = set(self.alias_index.keys())  1384   1385         while True:  1386   1387             # Aliased name definitions. All aliases with usage will have been  1388             # defined, but they may be refined according to referenced accesses.  1389   1390             updated_aliases = set()  1391   1392             for location in affected_aliases:  1393                 if self.record_types_for_alias(location):  1394                     updated_aliases.add(location)  1395   1396             # Define accesses employing aliases.  1397   1398             alias_accesses = set()  1399             affected_aliases = set()  1400   1401             for alias in updated_aliases:  1402   1403                 # Access affected by the alias.  1404   1405                 if self.access_index_rev.has_key(alias):  1406                     alias_accesses.update(self.access_index_rev[alias])  1407   1408                 # Another alias affected by the alias.  1409   1410                 elif self.alias_index_rev.has_key(alias):  1411                     affected_aliases.update(self.alias_index_rev[alias])  1412   1413             # Update accesses employing aliases.  1414   1415             updated_accesses = set()  1416   1417             for access_location in alias_accesses:  1418                 if self.record_types_for_access(access_location, self.access_index[access_location]):  1419                     updated_accesses.add(access_location)  1420   1421             # Determine which aliases are affected by the updated accesses.  1422   1423             for access_location in updated_accesses:  1424                 if self.alias_index_rev.has_key(access_location):  1425                     affected_aliases.update(self.alias_index_rev[access_location])  1426   1427             if not affected_aliases:  1428                 break  1429   1430     def constrain_types(self, path, class_types, instance_types, module_types):  1431   1432         """  1433         Using the given 'path' to an object, constrain the given 'class_types',  1434         'instance_types' and 'module_types'.  1435   1436         Return the class, instance, module types plus whether the types are  1437         constrained to a specific kind of type.  1438         """  1439   1440         ref = self.importer.identify(path)  1441         if ref:  1442   1443             # Constrain usage suggestions using the identified object.  1444   1445             if ref.has_kind("<class>"):  1446                 return (  1447                     set(class_types).intersection([ref.get_origin()]), [], [], True  1448                     )  1449             elif ref.has_kind("<module>"):  1450                 return (  1451                     [], [], set(module_types).intersection([ref.get_origin()]), True  1452                     )  1453   1454         return class_types, instance_types, module_types, False  1455   1456     def get_target_types(self, location, usage):  1457   1458         """  1459         Return the class, instance and module types constrained for the name at  1460         the given 'location' exhibiting the given 'usage'. Whether the types  1461         have been constrained using contextual information is also indicated,  1462         plus whether the types have been constrained to a specific kind of type.  1463         """  1464   1465         unit_path, name, attrnames, version = location  1466         have_assignments = get_assigned_attributes(usage)  1467   1468         # Detect any initialised name for the location.  1469   1470         if name:  1471             refs = self.get_initialised_name(location)  1472             if refs:  1473                 (class_types, only_instance_types, module_types,  1474                     _function_types, _var_types) = separate_types(refs)  1475                 return class_types, only_instance_types, module_types, True, have_assignments  1476   1477         # Retrieve the recorded types for the usage.  1478   1479         class_types = self.get_class_types_for_usage(usage)  1480         only_instance_types = set(self.get_instance_types_for_usage(usage)).difference(class_types)  1481         module_types = self.get_module_types_for_usage(usage)  1482   1483         # Merge usage deductions with observations to obtain reference types  1484         # for names involved with attribute accesses.  1485   1486         if not name:  1487             return class_types, only_instance_types, module_types, False, have_assignments  1488   1489         # Obtain references to known objects.  1490   1491         path = get_name_path(unit_path, name)  1492   1493         class_types, only_instance_types, module_types, constrained_specific = \  1494             self.constrain_types(path, class_types, only_instance_types, module_types)  1495   1496         if constrained_specific:  1497             return class_types, only_instance_types, module_types, constrained_specific, \  1498                 constrained_specific or have_assignments  1499   1500         # Constrain "self" references.  1501   1502         if name == "self":  1503   1504             # Test for the class of the method in the deduced types.  1505   1506             class_name = self.in_method(unit_path)  1507   1508             if class_name and class_name not in class_types and class_name not in only_instance_types:  1509                 raise DeduceError("In %s, usage {%s} is not directly supported by class %s or its instances." %  1510                                   (unit_path, encode_usage(usage), class_name))  1511   1512             # Constrain the types to the class's hierarchy.  1513   1514             t = self.constrain_self_reference(unit_path, class_types, only_instance_types)  1515             if t:  1516                 class_types, only_instance_types, module_types, constrained = t  1517                 return class_types, only_instance_types, module_types, constrained, have_assignments  1518   1519         return class_types, only_instance_types, module_types, False, have_assignments  1520   1521     def constrain_self_reference(self, unit_path, class_types, only_instance_types):  1522   1523         """  1524         Where the name "self" appears in a method, attempt to constrain the  1525         classes involved.  1526   1527         Return the class, instance, module types plus whether the types are  1528         constrained.  1529         """  1530   1531         class_name = self.in_method(unit_path)  1532   1533         if not class_name:  1534             return None  1535   1536         classes = set([class_name])  1537         classes.update(self.get_descendants_for_class(class_name))  1538   1539         # Note that only instances will be expected for these references but  1540         # either classes or instances may provide the attributes.  1541   1542         return (  1543             set(class_types).intersection(classes),  1544             set(only_instance_types).intersection(classes),  1545             [], True  1546             )  1547   1548     def in_method(self, path):  1549   1550         "Return whether 'path' refers to a method."  1551   1552         class_name, method_name = path.rsplit(".", 1)  1553         return class_name != "__builtins__.core.type" and self.importer.classes.has_key(class_name) and class_name  1554   1555     def init_reference_details(self, location):  1556   1557         "Initialise reference-related details for 'location'."  1558   1559         self.init_definition_details(location)  1560         self.init_access_details(location)  1561   1562     def init_definition_details(self, location):  1563   1564         "Initialise name definition details for 'location'."  1565   1566         self.accessor_class_types[location] = set()  1567         self.accessor_instance_types[location] = set()  1568         self.accessor_module_types[location] = set()  1569         self.provider_class_types[location] = set()  1570         self.provider_instance_types[location] = set()  1571         self.provider_module_types[location] = set()  1572   1573     def init_access_details(self, location):  1574   1575         "Initialise access details at 'location'."  1576   1577         self.referenced_attrs[location] = {}  1578   1579     def record_types_for_access(self, access_location, accessor_locations):  1580   1581         """  1582         Define types for the 'access_location' associated with the given  1583         'accessor_locations'. Return whether referenced attributes were updated.  1584         """  1585   1586         attrname = get_attrname_from_location(access_location)  1587         if not attrname:  1588             return False  1589   1590         invocation = access_location in self.reference_invocations  1591         assignment = access_location in self.reference_assignments  1592   1593         # Collect all suggested types for the accessors. Accesses may  1594         # require accessors from of a subset of the complete set of types.  1595   1596         class_types = set()  1597         module_types = set()  1598         instance_types = set()  1599   1600         constrained = True  1601   1602         old_referenced_attrs = self.referenced_attrs.get(access_location)  1603   1604         for location in accessor_locations:  1605   1606             # Use the type information deduced for names from above.  1607   1608             if self.accessor_class_types.has_key(location):  1609                 class_types.update(self.accessor_class_types[location])  1610                 module_types.update(self.accessor_module_types[location])  1611                 instance_types.update(self.accessor_instance_types[location])  1612   1613             # Where accesses are associated with assignments but where no  1614             # attribute usage observations have caused such an association,  1615             # the attribute name is considered by itself.  1616   1617             else:  1618                 self.init_definition_details(location)  1619                 self.record_types_for_usage(location, [(attrname, invocation, assignment)])  1620   1621             constrained = location in self.accessor_constrained and constrained  1622   1623         self.init_access_details(access_location)  1624         self.identify_reference_attributes(access_location, attrname, class_types, instance_types, module_types, constrained)  1625   1626         # Return whether the referenced attributes have changed.  1627   1628         return old_referenced_attrs != self.referenced_attrs.get(access_location)  1629   1630     def record_types_for_usage(self, accessor_location, usage):  1631   1632         """  1633         Record types for the given 'accessor_location' according to the given  1634         'usage' observations which may be None to indicate an absence of usage.  1635         """  1636   1637         (class_types,  1638          instance_types,  1639          module_types,  1640          constrained,  1641          constrained_specific) = self.get_target_types(accessor_location, usage)  1642   1643         invocations = get_invoked_attributes(usage)  1644   1645         self.record_reference_types(accessor_location, class_types, instance_types,  1646             module_types, constrained, constrained_specific, invocations)  1647   1648     def record_types_for_attribute(self, access_location, attrname):  1649   1650         """  1651         Record types for the 'access_location' employing only the given  1652         'attrname' for type deduction.  1653         """  1654   1655         (class_types,  1656          only_instance_types,  1657          module_types) = self.get_types_for_attribute(attrname)  1658   1659         self.init_reference_details(access_location)  1660   1661         self.identify_reference_attributes(access_location, attrname, class_types, only_instance_types, module_types, False)  1662         self.record_reference_types(access_location, class_types, only_instance_types, module_types, False)  1663   1664     def get_types_for_attribute(self, attrname):  1665   1666         "Return class, instance-only and module types supporting 'attrname'."  1667   1668         usage = ((attrname, False, False),)  1669   1670         class_types = self.get_class_types_for_usage(usage)  1671         only_instance_types = set(self.get_instance_types_for_usage(usage)).difference(class_types)  1672         module_types = self.get_module_types_for_usage(usage)  1673   1674         return class_types, only_instance_types, module_types  1675   1676     def record_types_for_alias(self, accessor_location):  1677   1678         """  1679         Define types for the 'accessor_location' not having associated usage.  1680         Return whether the types were updated.  1681         """  1682   1683         have_access = self.provider_class_types.has_key(accessor_location)  1684   1685         # With an access, attempt to narrow the existing selection of provider  1686         # types. Invocations attempt to find return value information, with  1687         # instance return values also yielding class providers (since attributes  1688         # on instances could be provided by classes).  1689   1690         if have_access:  1691             provider_class_types = self.provider_class_types[accessor_location]  1692             provider_instance_types = self.provider_instance_types[accessor_location]  1693             provider_module_types = self.provider_module_types[accessor_location]  1694   1695             accessor_class_types = self.accessor_class_types[accessor_location]  1696             accessor_instance_types = self.accessor_instance_types[accessor_location]  1697             accessor_module_types = self.accessor_module_types[accessor_location]  1698   1699             # Find details for any corresponding access.  1700   1701             new_provider_class_types = set()  1702             new_provider_instance_types = set()  1703             new_provider_module_types = set()  1704   1705             new_accessor_class_types = set()  1706             new_accessor_instance_types = set()  1707             new_accessor_module_types = set()  1708   1709             refs = set()  1710   1711             for access_location in self.alias_index[accessor_location]:  1712                 location, name, attrnames, access_number = access_location  1713                 invocation = self.reference_invocations.get(access_location)  1714   1715                 attrnames = attrnames and attrnames.split(".")  1716                 remaining = attrnames and len(attrnames) > 1  1717   1718                 # Alias has remaining attributes: reference details do not  1719                 # correspond to the accessor; the remaining attributes would  1720                 # need to be traversed first.  1721   1722                 if remaining:  1723                     return False  1724   1725                 # Alias references an attribute access.  1726   1727                 if attrnames:  1728   1729                     # Obtain references and attribute types for the access.  1730   1731                     attrs = self.get_references_for_access(access_location)  1732   1733                     if attrs:  1734   1735                         # Invocations converting class accessors to instances do  1736                         # not change the nature of class providers.  1737   1738                         provider_attrs = self.convert_invocation_providers(attrs, invocation)  1739   1740                         # Accessors are updated separately, employing invocation  1741                         # result details.  1742   1743                         accessor_attrs = self.convert_invocations(attrs, invocation)  1744   1745                 # Alias references a name, not an access.  1746   1747                 else:  1748                     # Attempt to refine the types using initialised names or  1749                     # accessors.  1750   1751                     attrs = self.get_initialised_name(access_location)  1752   1753                     if attrs:  1754                         provider_attrs = self.convert_invocation_providers(attrs, invocation)  1755                         accessor_attrs = self.convert_invocations(attrs, invocation)  1756                     else:  1757                         provider_attrs = self.get_provider_references(access_location)  1758                         attrs = accessor_attrs = self.get_accessor_references(access_location)  1759   1760                 # Where no specific attributes are defined, do not attempt  1761                 # to refine the alias's types.  1762   1763                 if not attrs:  1764                     return False  1765   1766                 (class_types, instance_types, module_types, function_types,  1767                     var_types) = separate_types(provider_attrs)  1768   1769                 # Where non-accessor types are found, do not attempt to refine  1770                 # the defined accessor types.  1771   1772                 if function_types or var_types:  1773                     return False  1774   1775                 class_types = set(provider_class_types).intersection(class_types)  1776                 instance_types = set(provider_instance_types).intersection(instance_types)  1777                 module_types = set(provider_module_types).intersection(module_types)  1778   1779                 new_provider_class_types.update(class_types)  1780                 new_provider_instance_types.update(instance_types)  1781                 new_provider_module_types.update(module_types)  1782   1783                 (class_types, instance_types, module_types, function_types,  1784                     var_types) = separate_types(accessor_attrs)  1785   1786                 class_types = set(accessor_class_types).intersection(class_types)  1787                 instance_types = set(accessor_instance_types).intersection(instance_types)  1788                 module_types = set(accessor_module_types).intersection(module_types)  1789   1790                 new_accessor_class_types.update(class_types)  1791                 new_accessor_instance_types.update(instance_types)  1792                 new_accessor_module_types.update(module_types)  1793   1794                 refs.update(accessor_attrs)  1795   1796                 # Update the alias relationships for invocations.  1797   1798                 self.update_alias_accesses(access_location, attrs)  1799   1800             # Record refined type details for the alias as an accessor.  1801   1802             self.init_definition_details(accessor_location)  1803             self.update_provider_types(accessor_location, new_provider_class_types, new_provider_instance_types, new_provider_module_types)  1804             self.update_accessor_types(accessor_location, new_accessor_class_types, new_accessor_instance_types, new_accessor_module_types)  1805   1806             # Record reference details for the alias separately from accessors.  1807   1808             self.referenced_objects[accessor_location] = refs  1809   1810             return new_accessor_class_types != accessor_class_types or \  1811                    new_accessor_instance_types != accessor_instance_types or \  1812                    new_accessor_module_types != accessor_module_types  1813   1814         # Without an access, attempt to identify references for the alias.  1815         # Invocations convert classes to instances and also attempt to find  1816         # return value information.  1817   1818         else:  1819             refs = set()  1820   1821             for access_location in self.alias_index[accessor_location]:  1822                 location, name, attrnames, access_number = access_location  1823                 invocation = self.reference_invocations.get(access_location)  1824   1825                 attrnames = attrnames and attrnames.split(".")  1826                 remaining = attrnames and len(attrnames) > 1  1827   1828                 # Alias has remaining attributes: reference details do not  1829                 # correspond to the accessor; the remaining attributes would  1830                 # need to be traversed first.  1831   1832                 if remaining:  1833                     return False  1834   1835                 # Alias references an attribute access.  1836   1837                 if attrnames:  1838   1839                     # Obtain references and attribute types for the access.  1840   1841                     attrs = self.get_references_for_access(access_location)  1842   1843                 # Alias references a name, not an access.  1844   1845                 else:  1846   1847                     # Obtain initialiser information.  1848   1849                     attrs = self.get_initialised_name(access_location)  1850   1851                     if attrs:  1852                         provider_attrs = self.convert_invocation_providers(attrs, invocation)  1853                         accessor_attrs = self.convert_invocations(attrs, invocation)  1854                     else:  1855                         provider_attrs = self.get_provider_references(access_location)  1856                         attrs = accessor_attrs = self.get_accessor_references(access_location)  1857   1858                 # Where no further information is found, do not attempt to  1859                 # refine the defined accessor types.  1860   1861                 if not attrs:  1862                     return False  1863   1864                 refs.update(self.convert_invocations(attrs, invocation))  1865   1866                 # Update the alias relationships for invocations.  1867   1868                 self.update_alias_accesses(access_location, attrs)  1869   1870             # Record refined type details for the alias as an accessor.  1871   1872             (class_types, instance_types, module_types, function_types,  1873                 var_types) = separate_types(refs)  1874   1875             # Where non-accessor types are found, do not attempt to refine  1876             # the defined accessor types.  1877   1878             if not function_types and not var_types:  1879                 self.init_definition_details(accessor_location)  1880                 self.update_provider_types(accessor_location, class_types + instance_types, class_types + instance_types, module_types)  1881                 self.update_accessor_types(accessor_location, class_types, instance_types, module_types)  1882   1883             # Record reference details for the alias separately from accessors.  1884   1885             self.referenced_objects[accessor_location] = refs  1886   1887             return True  1888   1889     def update_alias_accesses(self, access_location, refs):  1890   1891         """  1892         Record 'access_location' as a location affected by the return values of  1893         'refs' if an invocation is involved.  1894         """  1895   1896         if not self.reference_invocations.has_key(access_location):  1897             return  1898   1899         for ref in refs:  1900   1901             # Initialising accesses originate from the return values.  1902   1903             key = (ref.get_origin(), "$return")  1904             self._update_alias_accesses(access_location, key, self.importer.all_initialised_names)  1905             self._update_alias_accesses(access_location, key, self.importer.all_aliased_names)  1906   1907     def _update_alias_accesses(self, access_location, key, names):  1908   1909         """  1910         Make each return value provide information to the given  1911         'access_location', using 'key' to reference the return value and 'names'  1912         as the collection of definitions.  1913         """  1914   1915         versions = names.get(key)  1916         if not versions:  1917             return  1918   1919         for version in versions.keys():  1920             location = key + (None, version)  1921             l = init_item(self.alias_index_rev, location, set)  1922             l.add(access_location)  1923   1924             l = init_item(self.alias_index, access_location, set)  1925             l.add(location)  1926   1927     def get_references_for_access(self, access_location):  1928   1929         "Return the references identified for 'access_location'."  1930   1931         attrs = []  1932         for attrtype, object_type, attr in self.referenced_attrs[access_location]:  1933             attrs.append(attr)  1934         return attrs  1935   1936     def convert_invocation_providers(self, refs, invocation):  1937   1938         """  1939         Convert 'refs' to providers corresponding to the results of invoking  1940         each of the given references, if 'invocation' is set to a true value.  1941         """  1942   1943         if not invocation:  1944             return refs  1945   1946         providers = set()  1947   1948         for ref in refs:  1949             invocation_providers = self.convert_accessors_to_providers(self.convert_invocation_provider(ref))  1950             providers.update(invocation_providers)  1951   1952         return self.references_or_var(providers)  1953   1954     def convert_accessors_to_providers(self, refs):  1955   1956         "Convert accessor 'refs' to provider references."  1957   1958         providers = set()  1959         for ref in refs:  1960             if ref.has_kind("<instance>"):  1961                 providers.add(Reference("<class>", ref.get_origin()))  1962             providers.add(ref)  1963         return providers  1964   1965     def convert_invocation_provider(self, ref):  1966   1967         "Convert 'ref' to a provider appropriate to its invocation result."  1968   1969         if ref:  1970             if ref.has_kind("<class>"):  1971                 return [ref]  1972             elif ref.has_kind("<function>"):  1973                 return self.convert_function_invocation(ref)  1974   1975         return [Reference("<var>")]  1976   1977     def convert_invocations(self, refs, invocation):  1978   1979         """  1980         Convert 'refs' to invocation results if 'invocation' is set to a true  1981         value.  1982         """  1983   1984         if not invocation:  1985             return refs  1986   1987         invocation_refs = set()  1988   1989         for ref in refs:  1990             invocation_refs.update(self.convert_invocation(ref))  1991   1992         return self.references_or_var(invocation_refs)  1993   1994     def convert_invocation(self, ref):  1995   1996         "Convert 'ref' to its invocation result."  1997   1998         if ref:  1999             if ref.has_kind("<class>"):  2000                 return [ref.instance_of()]  2001             elif ref.has_kind("<function>"):  2002                 return self.convert_function_invocation(ref)  2003   2004         return [Reference("<var>")]  2005   2006     def convert_function_invocation(self, ref):  2007   2008         "Convert the function 'ref' to its return value reference."  2009   2010         initialisers = self.importer.all_initialised_names.get((ref.get_origin(), "$return"))  2011         aliases = self.importer.all_aliased_names.get((ref.get_origin(), "$return"))  2012   2013         if initialisers and not aliases:  2014             return set(initialisers.values())  2015   2016         return [Reference("<var>")]  2017   2018     def references_or_var(self, refs):  2019   2020         var = Reference("<var>")  2021   2022         if var in refs:  2023             return set([var])  2024         else:  2025             return refs  2026   2027     def get_initialised_name(self, access_location):  2028   2029         """  2030         Return references for any initialised names at 'access_location', or  2031         None if no such references exist.  2032         """  2033   2034         path, name, attrnames, version = access_location  2035   2036         # Use initialiser information, if available.  2037   2038         initialisers = self.importer.all_initialised_names.get((path, name))  2039         if initialisers and initialisers.has_key(version):  2040             return [initialisers[version]]  2041         else:  2042             return None  2043   2044     def get_accessor_references(self, access_location):  2045   2046         """  2047         Return references corresponding to accessor details at the given  2048         'access_location'.  2049         """  2050   2051         if self.accessor_class_types.has_key(access_location):  2052             class_types = self.accessor_class_types[access_location]  2053             instance_types = self.accessor_instance_types[access_location]  2054             module_types = self.accessor_module_types[access_location]  2055             return combine_types(class_types, instance_types, module_types)  2056         else:  2057             return None  2058   2059     def get_provider_references(self, access_location):  2060   2061         """  2062         Return references corresponding to provider details at the given  2063         'access_location'.  2064         """  2065   2066         if self.provider_class_types.has_key(access_location):  2067             class_types = self.provider_class_types[access_location]  2068             instance_types = self.provider_instance_types[access_location]  2069             module_types = self.provider_module_types[access_location]  2070             return combine_types(class_types, instance_types, module_types)  2071         else:  2072             return None  2073   2074     def record_reference_types(self, location, class_types, instance_types,  2075         module_types, constrained, constrained_specific=False, invocations=None):  2076   2077         """  2078         Associate attribute provider types with the given 'location', consisting  2079         of the given 'class_types', 'instance_types' and 'module_types'.  2080   2081         If 'constrained' is indicated, the constrained nature of the accessor is  2082         recorded for the location.  2083   2084         If 'constrained_specific' is indicated using a true value, instance types  2085         will not be added to class types to permit access via instances at the  2086         given location. This is only useful where a specific accessor is known  2087         to be a class.  2088   2089         If 'invocations' is given, the given attribute names indicate those  2090         which are involved in invocations. Such invocations, if involving  2091         functions, will employ those functions as bound methods and will  2092         therefore not support classes as accessors, only instances of such  2093         classes.  2094   2095         Note that the specified types only indicate the provider types for  2096         attributes, whereas the recorded accessor types indicate the possible  2097         types of the actual objects used to access attributes.  2098         """  2099   2100         # Update the type details for the location.  2101   2102         self.update_provider_types(location, class_types, instance_types, module_types)  2103   2104         # Class types support classes and instances as accessors.  2105         # Instance-only and module types support only their own kinds as  2106         # accessors.  2107   2108         path, name, attrnames, version = location  2109   2110         if invocations:  2111             class_only_types = self.filter_for_invocations(class_types, invocations)  2112         else:  2113             class_only_types = class_types  2114   2115         # However, the nature of accessors can be further determined.  2116         # Any self variable may only refer to an instance.  2117   2118         if name != "self" or not self.in_method(path):  2119             self.accessor_class_types[location].update(class_only_types)  2120   2121         if not constrained_specific:  2122             self.accessor_instance_types[location].update(class_types)  2123   2124         self.accessor_instance_types[location].update(instance_types)  2125   2126         if name != "self" or not self.in_method(path):  2127             self.accessor_module_types[location].update(module_types)  2128   2129         if constrained:  2130             self.accessor_constrained.add(location)  2131   2132     def update_provider_types(self, location, class_types, instance_types, module_types):  2133   2134         """  2135         Update provider types for the given 'location', adding 'class_types',  2136         'instance_types' and 'module_types' to those already stored.  2137         """  2138   2139         self.provider_class_types[location].update(class_types)  2140         self.provider_instance_types[location].update(instance_types)  2141         self.provider_module_types[location].update(module_types)  2142   2143     def update_accessor_types(self, location, class_types, instance_types, module_types):  2144   2145         """  2146         Update accessor types for the given 'location', adding 'class_types',  2147         'instance_types' and 'module_types' to those already stored.  2148         """  2149   2150         self.accessor_class_types[location].update(class_types)  2151         self.accessor_instance_types[location].update(instance_types)  2152         self.accessor_module_types[location].update(module_types)  2153   2154     def filter_for_invocations(self, class_types, attrnames):  2155   2156         """  2157         From the given 'class_types', identify methods for the given  2158         'attrnames' that are being invoked, returning a filtered collection of  2159         class types.  2160   2161         This method may be used to remove class types from consideration where  2162         their attributes are methods that are directly invoked: method  2163         invocations must involve instance accessors.  2164         """  2165   2166         to_filter = set()  2167   2168         for class_type in class_types:  2169             for attrname in attrnames:  2170   2171                 # Attempt to obtain a class attribute of the given name. This  2172                 # may return an attribute provided by an ancestor class.  2173   2174                 ref = self.importer.get_class_attribute(class_type, attrname)  2175                 parent_class = ref and ref.parent()  2176   2177                 # If such an attribute is a method and would be available on  2178                 # the given class, record the class for filtering.  2179   2180                 if ref and ref.has_kind("<function>") and (  2181                    parent_class == class_type or  2182                    class_type in self.descendants[parent_class]):  2183   2184                     to_filter.add(class_type)  2185                     break  2186   2187         return set(class_types).difference(to_filter)  2188   2189     def identify_reference_attributes(self, location, attrname, class_types, instance_types, module_types, constrained):  2190   2191         """  2192         Identify reference attributes, associating them with the given  2193         'location', identifying the given 'attrname', employing the given  2194         'class_types', 'instance_types' and 'module_types'.  2195   2196         If 'constrained' is indicated, the constrained nature of the access is  2197         recorded for the location.  2198         """  2199   2200         # Record the referenced objects.  2201   2202         self.referenced_attrs[location] = \  2203             self._identify_reference_attribute(location, attrname, class_types, instance_types, module_types)  2204   2205         if constrained:  2206             self.access_constrained.add(location)  2207   2208     def _identify_reference_attribute(self, location, attrname, class_types, instance_types, module_types):  2209   2210         """  2211         Identify the reference attribute at the given access 'location', using  2212         the given 'attrname', and employing the given 'class_types',  2213         'instance_types' and 'module_types'.  2214         """  2215   2216         attrs = set()  2217   2218         # The class types expose class attributes either directly or via  2219         # instances.  2220   2221         for object_type in class_types:  2222             ref = self.importer.get_class_attribute(object_type, attrname)  2223             if ref and self.is_compatible_callable(location, object_type, ref):  2224                 attrs.add(("<class>", object_type, ref))  2225   2226             # Add any distinct instance attributes that would be provided  2227             # by instances also providing indirect class attribute access.  2228   2229             for ref in self.importer.get_instance_attributes(object_type, attrname):  2230                 if self.is_compatible_callable(location, object_type, ref):  2231                     attrs.add(("<instance>", object_type, ref))  2232   2233         # The instance-only types expose instance attributes, but although  2234         # classes are excluded as potential accessors (since they do not provide  2235         # the instance attributes), the class types may still provide some  2236         # attributes.  2237   2238         for object_type in instance_types:  2239             instance_attrs = self.importer.get_instance_attributes(object_type, attrname)  2240   2241             if instance_attrs:  2242                 for ref in instance_attrs:  2243                     if self.is_compatible_callable(location, object_type, ref):  2244                         attrs.add(("<instance>", object_type, ref))  2245             else:  2246                 ref = self.importer.get_class_attribute(object_type, attrname)  2247                 if ref and self.is_compatible_callable(location, object_type, ref):  2248                     attrs.add(("<class>", object_type, ref))  2249   2250         # Module types expose module attributes for module accessors.  2251   2252         for object_type in module_types:  2253             ref = self.importer.get_module_attribute(object_type, attrname)  2254             if ref and self.is_compatible_callable(location, object_type, ref):  2255                 attrs.add(("<module>", object_type, ref))  2256   2257         return attrs  2258   2259     def is_compatible_callable(self, location, object_type, ref):  2260   2261         """  2262         Return whether any invocation at 'location' involving an attribute of  2263         'object_type' identified by 'ref' is compatible with any arguments used.  2264         """  2265   2266         invocation = self.reference_invocations.get(location)  2267         if invocation is None:  2268             return True  2269   2270         objpath = ref.get_origin()  2271         if not objpath:  2272             return True  2273   2274         parameters = self.importer.function_parameters.get(objpath)  2275         if not parameters:  2276             return True  2277   2278         defaults = self.importer.function_defaults.get(objpath)  2279         arguments, keywords = invocation  2280         names = set(parameters)  2281   2282         # Determine whether the specified arguments are  2283         # compatible with the callable signature.  2284   2285         if arguments >= len(parameters) - len(defaults) and \  2286            arguments <= len(parameters) and \  2287            names.issuperset(keywords):  2288   2289             return True  2290         else:  2291             init_item(self.reference_invocations_unsuitable, location, set)  2292             self.reference_invocations_unsuitable[location].add(ref)  2293             return False  2294   2295     # Attribute access plan formulation.  2296   2297     class_tests = (  2298         ("guarded", "specific", "type"),  2299         ("guarded", "common", "type"),  2300         ("test", "specific", "type"),  2301         ("test", "common", "type"),  2302         )  2303   2304     def get_access_plan(self, location):  2305   2306         """  2307         Return details of the access at the given 'location'. The details are as  2308         follows:  2309   2310          * the initial accessor (from which accesses will be performed if no  2311            computed static accessor is found)  2312          * details of any test required on the initial accessor  2313          * details of any type employed by the test  2314          * any static accessor (from which accesses will be performed in  2315            preference to the initial accessor)  2316          * attributes needing to be traversed from the base that yield  2317            unambiguous objects  2318          * access modes for each of the unambiguously-traversed attributes  2319          * remaining attributes needing to be tested and traversed  2320          * details of the context  2321          * any test to apply to the context  2322          * the method of obtaining the first attribute  2323          * the method of obtaining the final attribute  2324          * any static final attribute  2325          * the kinds of objects providing the final attribute  2326         """  2327   2328         const_access = self.const_accesses_rev.get(location)  2329   2330         path, name, attrnames, version = location  2331         remaining = attrnames.split(".")  2332         attrname = remaining[0]  2333   2334         # Obtain reference, provider and provider kind information.  2335   2336         attrs = self.reference_all_attrs[location]  2337         provider_types = self.reference_all_providers[location]  2338         provider_kinds = self.reference_all_provider_kinds[location]  2339   2340         # Obtain accessor type and kind information.  2341   2342         accessor_types = self.reference_all_accessor_types[location]  2343         accessor_general_types = self.reference_all_accessor_general_types[location]  2344         accessor_kinds = get_kinds(accessor_general_types)  2345   2346         # Determine any guard or test requirements.  2347   2348         constrained = location in self.access_constrained  2349         test = self.reference_test_types[location]  2350         test_type = self.reference_test_accessor_type.get(location)  2351   2352         # Determine the accessor and provider properties.  2353   2354         class_accessor = "<class>" in accessor_kinds  2355         module_accessor = "<module>" in accessor_kinds  2356         instance_accessor = "<instance>" in accessor_kinds  2357         provided_by_class = "<class>" in provider_kinds  2358         provided_by_instance = "<instance>" in provider_kinds  2359   2360         # Determine how attributes may be accessed relative to the accessor.  2361   2362         object_relative = class_accessor or module_accessor or provided_by_instance  2363         class_relative = instance_accessor and provided_by_class  2364   2365         # Identify the last static attribute for context acquisition.  2366   2367         base = None  2368         dynamic_base = None  2369   2370         # Constant accesses have static providers.  2371   2372         if const_access:  2373             base = len(provider_types) == 1 and first(provider_types)  2374   2375         # Name-based accesses.  2376   2377         elif name:  2378             ref = self.importer.identify("%s.%s" % (path, name))  2379   2380             # Constant accessors are static.  2381   2382             if ref and ref.static():  2383                 base = ref.get_origin()  2384   2385             # Usage of previously-generated guard and test details.  2386   2387             elif test[:2] == ("constrained", "specific"):  2388                 ref = first(accessor_types)  2389   2390             elif test[:2] == ("constrained", "common"):  2391                 ref = first(accessor_general_types)  2392   2393             elif test[:2] == ("guarded", "specific"):  2394                 ref = first(accessor_types)  2395   2396             elif test[:2] == ("guarded", "common"):  2397                 ref = first(accessor_general_types)  2398   2399             # For attribute-based tests, tentatively identify a dynamic base.  2400             # Such tests allow single or multiple kinds of a type.  2401   2402             elif test[0] == "test" and test[1] in ("common", "specific"):  2403                 dynamic_base = test_type  2404   2405             # Static accessors.  2406   2407             if not base and test in self.class_tests:  2408                 base = ref and ref.get_origin() or dynamic_base  2409   2410             # Accessors that are not static but whose nature is determined.  2411   2412             elif not base and ref:  2413                 dynamic_base = ref.get_origin()  2414   2415         # Determine initial accessor details.  2416   2417         accessor = base or dynamic_base  2418         accessor_kind = len(accessor_kinds) == 1 and first(accessor_kinds) or None  2419         provider_kind = len(provider_kinds) == 1 and first(provider_kinds) or None  2420   2421         # Traverse remaining attributes.  2422   2423         traversed = []  2424         traversal_modes = []  2425   2426         while len(attrs) == 1 and not first(attrs).has_kind("<var>"):  2427             attr = first(attrs)  2428   2429             traversed.append(attrname)  2430             traversal_modes.append(accessor_kind == provider_kind and "object" or "class")  2431   2432             # Consume attribute names providing unambiguous attributes.  2433   2434             del remaining[0]  2435   2436             if not remaining:  2437                 break  2438   2439             # Update the last static attribute.  2440   2441             if attr.static():  2442                 base = attr.get_origin()  2443                 traversed = []  2444                 traversal_modes = []  2445   2446             # Get the access details.  2447   2448             attrname = remaining[0]  2449             accessor = attr.get_origin()  2450             accessor_kind = attr.get_kind()  2451             provider_kind = self.importer.get_attribute_provider(attr, attrname)  2452             accessor_kinds = [accessor_kind]  2453             provider_kinds = [provider_kind]  2454   2455             # Get the next attribute.  2456   2457             attrs = self.importer.get_attributes(attr, attrname)  2458   2459         # Where many attributes are suggested, no single attribute identity can  2460         # be loaded.  2461   2462         else:  2463             attr = None  2464   2465         # Determine the method of access.  2466   2467         is_assignment = location in self.reference_assignments or const_access in self.reference_assignments  2468         is_invocation = location in self.reference_invocations or const_access in self.reference_invocations  2469   2470         # Identified attribute that must be accessed via its parent.  2471   2472         if attr and attr.get_name() and is_assignment:  2473             final_method = "static-assign"; origin = attr.get_name()  2474   2475         # Static, identified attribute.  2476   2477         elif attr and attr.static():  2478             final_method = is_assignment and "static-assign" or \  2479                            is_invocation and "static-invoke" or \  2480                            "static"  2481             origin = attr.final()  2482   2483         # All other methods of access involve traversal.  2484   2485         else:  2486             final_method = is_assignment and "assign" or \  2487                            is_invocation and "access-invoke" or \  2488                            "access"  2489             origin = None  2490   2491         # First attribute accessed at a known position via the accessor.  2492   2493         # Static bases support object-relative accesses only.  2494   2495         if base:  2496             first_method = "relative-object"  2497   2498         # Dynamic bases support either object- or class-relative accesses.  2499   2500         elif dynamic_base:  2501             first_method = "relative" + (object_relative and "-object" or "") + \  2502                                         (class_relative and "-class" or "")  2503   2504         # The fallback case is always run-time testing and access.  2505   2506         else:  2507             first_method = "check" + (object_relative and "-object" or "") + \  2508                                      (class_relative and "-class" or "")  2509   2510         # Determine whether an unbound method is being accessed via an instance,  2511         # requiring a context test.  2512   2513         context_test = "ignore"  2514   2515         # Assignments do not employ the context.  2516   2517         if is_assignment:  2518             pass  2519   2520         # Obtain a selection of possible attributes if no unambiguous attribute  2521         # was identified.  2522   2523         elif not attr:  2524   2525             # Use previously-deduced attributes for a simple ambiguous access.  2526             # Otherwise, use the final attribute name to obtain possible  2527             # attributes.  2528   2529             if len(remaining) > 1:  2530                 attrname = remaining[-1]  2531   2532                 (class_types,  2533                  only_instance_types,  2534                  module_types) = self.get_types_for_attribute(attrname)  2535   2536                 accessor_kinds = set()  2537                 provider_kinds = set()  2538   2539                 if class_types:  2540                     accessor_kinds.add("<class>")  2541                     accessor_kinds.add("<instance>")  2542                     provider_kinds.add("<class>")  2543                 if only_instance_types:  2544                     accessor_kinds.add("<instance>")  2545                     provider_kinds.add("<instance>")  2546                 if module_types:  2547                     accessor_kinds.add("<module>")  2548                     provider_kinds.add("<module>")  2549   2550                 attrs = set()  2551                 for type in combine_types(class_types, only_instance_types, module_types):  2552                     attrs.update(self.importer.get_attributes(type, attrname))  2553   2554             always_unbound = True  2555             have_function = False  2556             have_var = False  2557   2558             # Determine whether all attributes are unbound methods and whether  2559             # functions or unidentified attributes occur.  2560   2561             for attr in attrs:  2562                 always_unbound = always_unbound and attr.has_kind("<function>") and attr.name_parent() == attr.parent()  2563                 have_function = have_function or attr.has_kind("<function>")  2564                 have_var = have_var or attr.has_kind("<var>")  2565   2566             # Test for class-via-instance accesses.  2567   2568             if accessor_kind == "<instance>" and \  2569                provider_kind == "<class>":  2570   2571                 if always_unbound:  2572                     context_test = "replace"  2573                 else:  2574                     context_test = "test"  2575   2576             # Test for the presence of class-via-instance accesses.  2577   2578             elif "<instance>" in accessor_kinds and \  2579                  "<class>" in provider_kinds and \  2580                  (have_function or have_var):  2581   2582                 context_test = "test"  2583   2584         # With an unambiguous attribute, determine whether a test is needed.  2585   2586         elif accessor_kind == "<instance>" and \  2587              provider_kind == "<class>" and \  2588              (attr.has_kind("<var>") or  2589               attr.has_kind("<function>") and  2590               attr.name_parent() == attr.parent()):  2591   2592             if attr.has_kind("<var>"):  2593                 context_test = "test"  2594             else:  2595                 context_test = "replace"  2596   2597         # With an unambiguous attribute with ambiguity in the access method,  2598         # generate a test.  2599   2600         elif "<instance>" in accessor_kinds and \  2601              "<class>" in provider_kinds and \  2602              (attr.has_kind("<var>") or  2603               attr.has_kind("<function>") and  2604               attr.name_parent() == attr.parent()):  2605   2606             context_test = "test"  2607   2608         # Determine the nature of the context.  2609   2610         context = context_test == "ignore" and "unset" or \  2611                   len(traversed + remaining) == 1 and \  2612                       (base and "base" or "original-accessor") or \  2613                   "final-accessor"  2614   2615         return name, test, test_type, base, \  2616                traversed, traversal_modes, remaining, \  2617                context, context_test, \  2618                first_method, final_method, \  2619                origin, accessor_kinds  2620   2621     def initialise_access_instructions(self):  2622   2623         "Expand access plans into instruction sequences."  2624   2625         for access_location, access_plan in self.access_plans.items():  2626   2627             # Obtain the access details.  2628   2629             name, test, test_type, base, \  2630                 traversed, traversal_modes, attrnames, \  2631                 context, context_test, \  2632                 first_method, final_method, \  2633                 origin, accessor_kinds = access_plan  2634   2635             # Emit instructions by appending them to a list.  2636   2637             instructions = []  2638             emit = instructions.append  2639   2640             # Identify any static original accessor.  2641   2642             if base:  2643                 original_accessor = base  2644   2645             # Employ names as contexts unless the context needs testing and  2646             # potentially updating. In such cases, temporary context storage is  2647             # used instead.  2648   2649             elif name and not (context_test == "test" and  2650                                final_method in ("access-invoke", "static-invoke")):  2651                 original_accessor = "<name>" # refers to the name  2652   2653             # Use a generic placeholder representing the access expression in  2654             # the general case.  2655   2656             else:  2657                 original_accessor = "<expr>"  2658   2659             # Prepare for any first attribute access.  2660   2661             if traversed:  2662                 attrname = traversed[0]  2663                 del traversed[0]  2664             elif attrnames:  2665                 attrname = attrnames[0]  2666                 del attrnames[0]  2667   2668             # Perform the first access explicitly if at least one operation  2669             # requires it.  2670   2671             access_first_attribute = final_method in ("access", "access-invoke", "assign") or traversed or attrnames  2672   2673             # Determine whether the first access involves assignment.  2674   2675             assigning = not traversed and not attrnames and final_method == "assign"  2676             set_accessor = assigning and "<set_target_accessor>" or "<set_accessor>"  2677             stored_accessor = assigning and "<target_accessor>" or "<accessor>"  2678   2679             # Set the context if already available.  2680   2681             context_var = None  2682   2683             if context == "base":  2684                 accessor = context_var = (base,)  2685             elif context == "original-accessor":  2686   2687                 # Prevent re-evaluation of any dynamic expression by storing it.  2688   2689                 if original_accessor == "<expr>":  2690                     if final_method in ("access-invoke", "static-invoke"):  2691                         emit(("<set_context>", original_accessor))  2692                         accessor = context_var = ("<context>",)  2693                     else:  2694                         emit((set_accessor, original_accessor))  2695                         accessor = context_var = (stored_accessor,)  2696                 else:  2697                     accessor = context_var = (original_accessor,)  2698   2699             # Assigning does not set the context.  2700   2701             elif context in ("final-accessor", "unset") and access_first_attribute:  2702   2703                 # Prevent re-evaluation of any dynamic expression by storing it.  2704   2705                 if original_accessor == "<expr>":  2706                     emit((set_accessor, original_accessor))  2707                     accessor = (stored_accessor,)  2708                 else:  2709                     accessor = (original_accessor,)  2710   2711             # Apply any test.  2712   2713             if test[0] == "test":  2714                 accessor = ("__%s_%s_%s" % test, accessor, test_type)  2715   2716             # Perform the first or final access.  2717             # The access only needs performing if the resulting accessor is used.  2718   2719             remaining = len(traversed + attrnames)  2720   2721             if access_first_attribute:  2722   2723                 if first_method == "relative-class":  2724                     if assigning:  2725                         emit(("__store_via_class", accessor, attrname, "<assexpr>"))  2726                     else:  2727                         accessor = ("__load_via_class", accessor, attrname)  2728   2729                 elif first_method == "relative-object":  2730                     if assigning:  2731                         emit(("__store_via_object", accessor, attrname, "<assexpr>"))  2732                     else:  2733                         accessor = ("__load_via_object", accessor, attrname)  2734   2735                 elif first_method == "relative-object-class":  2736                     if assigning:  2737                         emit(("__get_class_and_store", accessor, attrname, "<assexpr>"))  2738                     else:  2739                         accessor = ("__get_class_and_load", accessor, attrname)  2740   2741                 elif first_method == "check-class":  2742                     if assigning:  2743                         emit(("__check_and_store_via_class", accessor, attrname, "<assexpr>"))  2744                     else:  2745                         accessor = ("__check_and_load_via_class", accessor, attrname)  2746   2747                 elif first_method == "check-object":  2748                     if assigning:  2749                         emit(("__check_and_store_via_object", accessor, attrname, "<assexpr>"))  2750                     else:  2751                         accessor = ("__check_and_load_via_object", accessor, attrname)  2752   2753                 elif first_method == "check-object-class":  2754                     if assigning:  2755                         emit(("__check_and_store_via_any", accessor, attrname, "<assexpr>"))  2756                     else:  2757                         accessor = ("__check_and_load_via_any", accessor, attrname)  2758   2759             # Traverse attributes using the accessor.  2760   2761             if traversed:  2762                 for attrname, traversal_mode in zip(traversed, traversal_modes):  2763                     assigning = remaining == 1 and final_method == "assign"  2764   2765                     # Set the context, if appropriate.  2766   2767                     if remaining == 1 and final_method != "assign" and context == "final-accessor":  2768   2769                         # Invoked attributes employ a separate context accessed  2770                         # during invocation.  2771   2772                         if final_method in ("access-invoke", "static-invoke"):  2773                             emit(("<set_context>", accessor))  2774                             accessor = context_var = "<context>"  2775   2776                         # A private context within the access is otherwise  2777                         # retained.  2778   2779                         else:  2780                             emit(("<set_private_context>", accessor))  2781                             accessor = context_var = "<private_context>"  2782   2783                     # Perform the access only if not achieved directly.  2784   2785                     if remaining > 1 or final_method in ("access", "access-invoke", "assign"):  2786   2787                         if traversal_mode == "class":  2788                             if assigning:  2789                                 emit(("__store_via_class", accessor, attrname, "<assexpr>"))  2790                             else:  2791                                 accessor = ("__load_via_class", accessor, attrname)  2792                         else:  2793                             if assigning:  2794                                 emit(("__store_via_object", accessor, attrname, "<assexpr>"))  2795                             else:  2796                                 accessor = ("__load_via_object", accessor, attrname)  2797   2798                     remaining -= 1  2799   2800             if attrnames:  2801                 for attrname in attrnames:  2802                     assigning = remaining == 1 and final_method == "assign"  2803   2804                     # Set the context, if appropriate.  2805   2806                     if remaining == 1 and final_method != "assign" and context == "final-accessor":  2807   2808                         # Invoked attributes employ a separate context accessed  2809                         # during invocation.  2810   2811                         if final_method in ("access-invoke", "static-invoke"):  2812                             emit(("<set_context>", accessor))  2813                             accessor = context_var = "<context>"  2814   2815                         # A private context within the access is otherwise  2816                         # retained.  2817   2818                         else:  2819                             emit(("<set_private_context>", accessor))  2820                             accessor = context_var = "<private_context>"  2821   2822                     # Perform the access only if not achieved directly.  2823   2824                     if remaining > 1 or final_method in ("access", "access-invoke", "assign"):  2825   2826                         # Constrain instructions involving certain special  2827                         # attribute names.  2828   2829                         to_search = attrname == "__data__" and "object" or "any"  2830   2831                         if assigning:  2832                             emit(("__check_and_store_via_%s" % to_search, accessor, attrname, "<assexpr>"))  2833                         else:  2834                             accessor = ("__check_and_load_via_%s" % to_search, accessor, attrname)  2835   2836                     remaining -= 1  2837   2838             # Define or emit the means of accessing the actual target.  2839   2840             # Assignments to known attributes.  2841   2842             if final_method == "static-assign":  2843                 parent, attrname = origin.rsplit(".", 1)  2844                 emit(("__store_via_object", parent, attrname, "<assexpr>"))  2845   2846             # Invoked attributes employ a separate context.  2847   2848             elif final_method in ("static", "static-invoke"):  2849                 accessor = ("__load_static_ignore", origin)  2850   2851             # Wrap accesses in context operations.  2852   2853             if context_test == "test":  2854   2855                 # Test and combine the context with static attribute details.  2856   2857                 if final_method == "static":  2858                     emit(("__load_static_test", context_var, origin))  2859   2860                 # Test the context, storing it separately if required for the  2861                 # immediately invoked static attribute.  2862   2863                 elif final_method == "static-invoke":  2864                     emit(("<test_context_static>", context_var, origin))  2865   2866                 # Test the context, storing it separately if required for an  2867                 # immediately invoked attribute.  2868   2869                 elif final_method == "access-invoke":  2870                     emit(("<test_context_revert>", context_var, accessor))  2871   2872                 # Test the context and update the attribute details if  2873                 # appropriate.  2874   2875                 else:  2876                     emit(("__test_context", context_var, accessor))  2877   2878             elif context_test == "replace":  2879   2880                 # Produce an object with updated context.  2881   2882                 if final_method == "static":  2883                     emit(("__load_static_replace", context_var, origin))  2884   2885                 # Omit the context update operation where the target is static  2886                 # and the context is recorded separately.  2887   2888                 elif final_method == "static-invoke":  2889                     pass  2890   2891                 # If a separate context is used for an immediate invocation,  2892                 # produce the attribute details unchanged.  2893   2894                 elif final_method == "access-invoke":  2895                     emit(accessor)  2896   2897                 # Update the context in the attribute details.  2898   2899                 else:  2900                     emit(("__update_context", context_var, accessor))  2901   2902             # Omit the accessor for assignments and for invocations of static  2903             # targets.  2904   2905             elif final_method not in ("assign", "static-assign", "static-invoke"):  2906                 emit(accessor)  2907   2908             # Produce an advisory instruction regarding the context.  2909   2910             if context_var:  2911                 emit(("<context_identity>", context_var))  2912   2913             # Produce an advisory instruction regarding the final attribute.  2914   2915             if origin:  2916                 emit(("<final_identity>", origin))  2917   2918             self.access_instructions[access_location] = instructions  2919             self.accessor_kinds[access_location] = accessor_kinds  2920   2921 # vim: tabstop=4 expandtab shiftwidth=4