Lichen

deducer.py

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