Lichen

deducer.py

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