Lichen

deducer.py

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