Lichen

deducer.py

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