Lichen

deducer.py

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