Lichen

deducer.py

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