Lichen

deducer.py

303:c07a749f5bd0
2016-12-02 Paul Boddie Use __data__ attributes with native functions apart from when __data__ needs replacing (such as in the list append and concatenation functions).
     1 #!/usr/bin/env python     2      3 """     4 Deduce types for usage observations.     5      6 Copyright (C) 2014, 2015, 2016 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                    sorted_output, CommonOutput    26 from encoders import encode_attrnames, encode_access_location, \    27                      encode_constrained, 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     def __init__(self, importer, output):    39     40         """    41         Initialise an instance using the given 'importer' that will perform    42         deductions on the program information, writing the results to the given    43         'output' directory.    44         """    45     46         self.importer = importer    47         self.output = output    48     49         # Descendants of classes.    50     51         self.descendants = {}    52         self.init_descendants()    53         self.init_special_attributes()    54     55         # Map locations to usage in order to determine specific types.    56     57         self.location_index = {}    58     59         # Map access locations to definition locations.    60     61         self.access_index = {}    62     63         # Map aliases to accesses that define them.    64     65         self.alias_index = {}    66     67         # Map constant accesses to redefined accesses.    68     69         self.const_accesses = {}    70         self.const_accesses_rev = {}    71     72         # Map usage observations to assigned attributes.    73     74         self.assigned_attrs = {}    75     76         # Map usage observations to objects.    77     78         self.attr_class_types = {}    79         self.attr_instance_types = {}    80         self.attr_module_types = {}    81     82         # Modified attributes from usage observations.    83     84         self.modified_attributes = {}    85     86         # Accesses that are assignments or invocations.    87     88         self.reference_assignments = set()    89         self.reference_invocations = set()    90     91         # Map locations to types, constrained indicators and attributes.    92     93         self.accessor_class_types = {}    94         self.accessor_instance_types = {}    95         self.accessor_module_types = {}    96         self.provider_class_types = {}    97         self.provider_instance_types = {}    98         self.provider_module_types = {}    99         self.accessor_constrained = set()   100         self.access_constrained = set()   101         self.referenced_attrs = {}   102         self.referenced_objects = {}   103    104         # Details of access operations.   105    106         self.access_plans = {}   107    108         # Accumulated information about accessors and providers.   109    110         self.accessor_general_class_types = {}   111         self.accessor_general_instance_types = {}   112         self.accessor_general_module_types = {}   113         self.accessor_all_types = {}   114         self.accessor_all_general_types = {}   115         self.provider_all_types = {}   116         self.accessor_guard_tests = {}   117    118         # Accumulated information about accessed attributes and   119         # access/attribute-specific accessor tests.   120    121         self.reference_all_attrs = {}   122         self.reference_all_attrtypes = {}   123         self.reference_all_accessor_types = {}   124         self.reference_all_accessor_general_types = {}   125         self.reference_test_types = {}   126         self.reference_test_accessor_type = {}   127    128         # The processing workflow itself.   129    130         self.init_usage_index()   131         self.init_accessors()   132         self.init_accesses()   133         self.init_aliases()   134         self.init_attr_type_indexes()   135         self.modify_mutated_attributes()   136         self.identify_references()   137         self.classify_accessors()   138         self.classify_accesses()   139         self.initialise_access_plans()   140    141     def to_output(self):   142    143         "Write the output files using deduction information."   144    145         self.check_output()   146    147         self.write_mutations()   148         self.write_accessors()   149         self.write_accesses()   150         self.write_access_plans()   151    152     def write_mutations(self):   153    154         """   155         Write mutation-related output in the following format:   156    157         qualified name " " original object type   158    159         Object type can be "<class>", "<function>" or "<var>".   160         """   161    162         f = open(join(self.output, "mutations"), "w")   163         try:   164             attrs = self.modified_attributes.items()   165             attrs.sort()   166    167             for attr, value in attrs:   168                 print >>f, attr, value   169         finally:   170             f.close()   171    172     def write_accessors(self):   173    174         """   175         Write reference-related output in the following format for types:   176    177         location " " ( "constrained" | "deduced" ) " " attribute type " " most general type names " " number of specific types   178    179         Note that multiple lines can be given for each location, one for each   180         attribute type.   181    182         Locations have the following format:   183    184         qualified name of scope "." local name ":" name version   185    186         The attribute type can be "<class>", "<instance>", "<module>" or "<>",   187         where the latter indicates an absence of suitable references.   188    189         Type names indicate the type providing the attributes, being either a   190         class or module qualified name.   191    192         ----   193    194         A summary of accessor types is formatted as follows:   195    196         location " " ( "constrained" | "deduced" ) " " ( "specific" | "common" | "unguarded" ) " " most general type names " " number of specific types   197    198         This summary groups all attribute types (class, instance, module) into a   199         single line in order to determine the complexity of identifying an   200         accessor.   201    202         ----   203    204         References that cannot be supported by any types are written to a   205         warnings file in the following format:   206    207         location   208    209         ----   210    211         For each location where a guard would be asserted to guarantee the   212         nature of an object, the following format is employed:   213    214         location " " ( "specific" | "common" ) " " object kind " " object types   215    216         Object kind can be "<class>", "<instance>" or "<module>".   217         """   218    219         f_type_summary = open(join(self.output, "type_summary"), "w")   220         f_types = open(join(self.output, "types"), "w")   221         f_warnings = open(join(self.output, "type_warnings"), "w")   222         f_guards = open(join(self.output, "guards"), "w")   223    224         try:   225             locations = self.accessor_class_types.keys()   226             locations.sort()   227    228             for location in locations:   229                 constrained = location in self.accessor_constrained   230    231                 # Accessor information.   232    233                 class_types = self.accessor_class_types[location]   234                 instance_types = self.accessor_instance_types[location]   235                 module_types = self.accessor_module_types[location]   236    237                 general_class_types = self.accessor_general_class_types[location]   238                 general_instance_types = self.accessor_general_instance_types[location]   239                 general_module_types = self.accessor_general_module_types[location]   240    241                 all_types = self.accessor_all_types[location]   242                 all_general_types = self.accessor_all_general_types[location]   243    244                 if class_types:   245                     print >>f_types, encode_location(location), encode_constrained(constrained), "<class>", \   246                         sorted_output(general_class_types), len(class_types)   247    248                 if instance_types:   249                     print >>f_types, encode_location(location), encode_constrained(constrained), "<instance>", \   250                         sorted_output(general_instance_types), len(instance_types)   251    252                 if module_types:   253                     print >>f_types, encode_location(location), encode_constrained(constrained), "<module>", \   254                         sorted_output(general_module_types), len(module_types)   255    256                 if not all_types:   257                     print >>f_types, encode_location(location), "deduced", "<>", 0   258                     attrnames = list(self.location_index[location])   259                     attrnames.sort()   260                     print >>f_warnings, encode_location(location), "; ".join(map(encode_usage, attrnames))   261    262                 guard_test = self.accessor_guard_tests.get(location)   263                 if guard_test:   264                     guard_test_type, guard_test_arg = guard_test   265    266                 # Write specific type guard details.   267    268                 if guard_test and guard_test_type == "specific":   269                     print >>f_guards, encode_location(location), "-".join(guard_test), \   270                         first(get_kinds(all_types)), \   271                         sorted_output(all_types)   272    273                 # Write common type guard details.   274    275                 elif guard_test and guard_test_type == "common":   276                     print >>f_guards, encode_location(location), "-".join(guard_test), \   277                         first(get_kinds(all_general_types)), \   278                         sorted_output(all_general_types)   279    280                 print >>f_type_summary, encode_location(location), encode_constrained(constrained), \   281                     guard_test and "-".join(guard_test) or "unguarded", sorted_output(all_general_types), len(all_types)   282    283         finally:   284             f_type_summary.close()   285             f_types.close()   286             f_warnings.close()   287             f_guards.close()   288    289     def write_accesses(self):   290    291         """   292         Specific attribute output is produced in the following format:   293    294         location " " ( "constrained" | "deduced" ) " " attribute type " " attribute references   295    296         Note that multiple lines can be given for each location and attribute   297         name, one for each attribute type.   298    299         Locations have the following format:   300    301         qualified name of scope "." local name " " attribute name ":" access number   302    303         The attribute type can be "<class>", "<instance>", "<module>" or "<>",   304         where the latter indicates an absence of suitable references.   305    306         Attribute references have the following format:   307    308         object type ":" qualified name   309    310         Object type can be "<class>", "<function>" or "<var>".   311    312         ----   313    314         A summary of attributes is formatted as follows:   315    316         location " " attribute name " " ( "constrained" | "deduced" ) " " test " " attribute references   317    318         This summary groups all attribute types (class, instance, module) into a   319         single line in order to determine the complexity of each access.   320    321         Tests can be "validate", "specific", "untested", "guarded-validate" or "guarded-specific".   322    323         ----   324    325         For each access where a test would be asserted to guarantee the   326         nature of an attribute, the following formats are employed:   327    328         location " " attribute name " " "validate"   329         location " " attribute name " " "specific" " " attribute type " " object type   330    331         ----   332    333         References that cannot be supported by any types are written to a   334         warnings file in the following format:   335    336         location   337         """   338    339         f_attr_summary = open(join(self.output, "attribute_summary"), "w")   340         f_attrs = open(join(self.output, "attributes"), "w")   341         f_tests = open(join(self.output, "tests"), "w")   342         f_warnings = open(join(self.output, "attribute_warnings"), "w")   343    344         try:   345             locations = self.referenced_attrs.keys()   346             locations.sort()   347    348             for location in locations:   349                 constrained = location in self.access_constrained   350    351                 # Attribute information, both name-based and anonymous.   352    353                 referenced_attrs = self.referenced_attrs[location]   354    355                 if referenced_attrs:   356                     attrname = get_attrname_from_location(location)   357    358                     all_accessed_attrs = self.reference_all_attrs[location]   359    360                     for attrtype, attrs in self.get_referenced_attrs(location):   361                         print >>f_attrs, encode_access_location(location), encode_constrained(constrained), attrtype, sorted_output(attrs)   362    363                     test_type = self.reference_test_types.get(location)   364    365                     # Write the need to test at run time.   366    367                     if test_type[0] == "validate":   368                         print >>f_tests, encode_access_location(location), "-".join(test_type)   369    370                     # Write any type checks for anonymous accesses.   371    372                     elif test_type and self.reference_test_accessor_type.get(location):   373                         print >>f_tests, encode_access_location(location), "-".join(test_type), \   374                             sorted_output(all_accessed_attrs), \   375                             self.reference_test_accessor_type[location]   376    377                     print >>f_attr_summary, encode_access_location(location), encode_constrained(constrained), \   378                         test_type and "-".join(test_type) or "untested", sorted_output(all_accessed_attrs)   379    380                 else:   381                     print >>f_warnings, encode_access_location(location)   382    383         finally:   384             f_attr_summary.close()   385             f_attrs.close()   386             f_tests.close()   387             f_warnings.close()   388    389     def write_access_plans(self):   390    391         """   392         Each attribute access is written out as a plan of the following form:   393    394         location " " name " " test " " test type " " base " " traversed attributes   395                  " " attributes to traverse " " context " " access method   396                  " " static attribute " " accessor kinds   397         """   398    399         f_attrs = open(join(self.output, "attribute_plans"), "w")   400    401         try:   402             locations = self.access_plans.keys()   403             locations.sort()   404    405             for location in locations:   406                 name, test, test_type, base, \   407                     traversed, traversal_modes, attrnames, \   408                     context, context_test, \   409                     first_method, final_method, \   410                     attr, accessor_kinds = self.access_plans[location]   411    412                 print >>f_attrs, encode_access_location(location), \   413                                  name or "{}", \   414                                  test and "-".join(test) or "{}", \   415                                  test_type or "{}", \   416                                  base or "{}", \   417                                  ".".join(traversed) or "{}", \   418                                  ".".join(traversal_modes) or "{}", \   419                                  ".".join(attrnames) or "{}", \   420                                  context, context_test, \   421                                  first_method, final_method, attr or "{}", \   422                                  ",".join(accessor_kinds)   423    424         finally:   425             f_attrs.close()   426    427     def classify_accessors(self):   428    429         "For each program location, classify accessors."   430    431         # Where instance and module types are defined, class types are also   432         # defined. See: init_definition_details   433    434         locations = self.accessor_class_types.keys()   435    436         for location in locations:   437             constrained = location in self.accessor_constrained   438    439             # Provider information.   440    441             class_types = self.provider_class_types[location]   442             instance_types = self.provider_instance_types[location]   443             module_types = self.provider_module_types[location]   444    445             # Collect specific and general type information.   446    447             self.provider_all_types[location] = \   448                 combine_types(class_types, instance_types, module_types)   449    450             # Accessor information.   451    452             class_types = self.accessor_class_types[location]   453             self.accessor_general_class_types[location] = \   454                 general_class_types = self.get_most_general_class_types(class_types)   455    456             instance_types = self.accessor_instance_types[location]   457             self.accessor_general_instance_types[location] = \   458                 general_instance_types = self.get_most_general_class_types(instance_types)   459    460             module_types = self.accessor_module_types[location]   461             self.accessor_general_module_types[location] = \   462                 general_module_types = self.get_most_general_module_types(module_types)   463    464             # Collect specific and general type information.   465    466             self.accessor_all_types[location] = all_types = \   467                 combine_types(class_types, instance_types, module_types)   468    469             self.accessor_all_general_types[location] = all_general_types = \   470                 combine_types(general_class_types, general_instance_types, general_module_types)   471    472             # Record guard information.   473    474             if not constrained:   475    476                 # Record specific type guard details.   477    478                 if len(all_types) == 1:   479                     self.accessor_guard_tests[location] = ("specific", test_label_for_type(first(all_types)))   480                 elif is_single_class_type(all_types):   481                     self.accessor_guard_tests[location] = ("specific", "object")   482    483                 # Record common type guard details.   484    485                 elif len(all_general_types) == 1:   486                     self.accessor_guard_tests[location] = ("common", test_label_for_type(first(all_types)))   487                 elif is_single_class_type(all_general_types):   488                     self.accessor_guard_tests[location] = ("common", "object")   489    490                 # Otherwise, no convenient guard can be defined.   491    492     def classify_accesses(self):   493    494         "For each program location, classify accesses."   495    496         # Attribute accesses use potentially different locations to those of   497         # accessors.   498    499         locations = self.referenced_attrs.keys()   500    501         for location in locations:   502             constrained = location in self.access_constrained   503    504             # Combine type information from all accessors supplying the access.   505    506             accessor_locations = self.get_accessors_for_access(location)   507    508             all_provider_types = set()   509             all_accessor_types = set()   510             all_accessor_general_types = set()   511    512             for accessor_location in accessor_locations:   513    514                 # Obtain the provider types for guard-related attribute access   515                 # checks.   516    517                 all_provider_types.update(self.provider_all_types.get(accessor_location))   518    519                 # Obtain the accessor guard types (specific and general).   520    521                 all_accessor_types.update(self.accessor_all_types.get(accessor_location))   522                 all_accessor_general_types.update(self.accessor_all_general_types.get(accessor_location))   523    524             # Obtain basic properties of the types involved in the access.   525    526             single_accessor_type = len(all_accessor_types) == 1   527             single_accessor_class_type = is_single_class_type(all_accessor_types)   528             single_accessor_general_type = len(all_accessor_general_types) == 1   529             single_accessor_general_class_type = is_single_class_type(all_accessor_general_types)   530    531             # Determine whether the attribute access is guarded or not.   532    533             guarded = (   534                 single_accessor_type or single_accessor_class_type or   535                 single_accessor_general_type or single_accessor_general_class_type   536                 )   537    538             if guarded:   539                 (guard_class_types, guard_instance_types, guard_module_types,   540                     _function_types, _var_types) = separate_types(all_provider_types)   541    542             self.reference_all_accessor_types[location] = all_accessor_types   543             self.reference_all_accessor_general_types[location] = all_accessor_general_types   544    545             # Attribute information, both name-based and anonymous.   546    547             referenced_attrs = self.referenced_attrs[location]   548    549             if not referenced_attrs:   550                 raise DeduceError("In %s, access via %s to attribute %s (occurrence %d) cannot be identified." % location)   551    552             # Record attribute information for each name used on the   553             # accessor.   554    555             attrname = get_attrname_from_location(location)   556    557             all_accessed_attrs = set()   558             all_providers = set()   559    560             # Obtain provider and attribute details for this kind of   561             # object.   562    563             for attrtype, object_type, attr in referenced_attrs:   564                 all_accessed_attrs.add(attr)   565                 all_providers.add(object_type)   566    567             all_general_providers = self.get_most_general_types(all_providers)   568    569             # Determine which attributes would be provided by the   570             # accessor types upheld by a guard.   571    572             if guarded:   573                 guard_attrs = set()   574                 for _attrtype, object_type, attr in \   575                     self._identify_reference_attribute(attrname, guard_class_types, guard_instance_types, guard_module_types):   576                     guard_attrs.add(attr)   577             else:   578                 guard_attrs = None   579    580             self.reference_all_attrs[location] = all_accessed_attrs   581    582             # Constrained accesses guarantee the nature of the accessor.   583             # However, there may still be many types involved.   584    585             if constrained:   586                 if single_accessor_type:   587                     self.reference_test_types[location] = ("constrained", "specific", test_label_for_type(first(all_accessor_types)))   588                 elif single_accessor_class_type:   589                     self.reference_test_types[location] = ("constrained", "specific", "object")   590                 elif single_accessor_general_type:   591                     self.reference_test_types[location] = ("constrained", "common", test_label_for_type(first(all_accessor_general_types)))   592                 elif single_accessor_general_class_type:   593                     self.reference_test_types[location] = ("constrained", "common", "object")   594                 else:   595                     self.reference_test_types[location] = ("constrained", "many")   596    597             # Suitably guarded accesses, where the nature of the   598             # accessor can be guaranteed, do not require the attribute   599             # involved to be validated. Otherwise, for unguarded   600             # accesses, access-level tests are required.   601    602             elif guarded and all_accessed_attrs.issubset(guard_attrs):   603                 if single_accessor_type:   604                     self.reference_test_types[location] = ("guarded", "specific", test_label_for_type(first(all_accessor_types)))   605                 elif single_accessor_class_type:   606                     self.reference_test_types[location] = ("guarded", "specific", "object")   607                 elif single_accessor_general_type:   608                     self.reference_test_types[location] = ("guarded", "common", test_label_for_type(first(all_accessor_general_types)))   609                 elif single_accessor_general_class_type:   610                     self.reference_test_types[location] = ("guarded", "common", "object")   611    612             # Record the need to test the type of anonymous and   613             # unconstrained accessors.   614    615             elif len(all_providers) == 1:   616                 provider = first(all_providers)   617                 if provider != '__builtins__.object':   618                     all_accessor_kinds = set(get_kinds(all_accessor_types))   619                     if len(all_accessor_kinds) == 1:   620                         test_type = ("test", "specific", first(all_accessor_kinds))   621                     else:   622                         test_type = ("test", "specific", "object")   623                     self.reference_test_types[location] = test_type   624                     self.reference_test_accessor_type[location] = provider   625    626             elif len(all_general_providers) == 1:   627                 provider = first(all_general_providers)   628                 if provider != '__builtins__.object':   629                     all_accessor_kinds = set(get_kinds(all_accessor_general_types))   630                     if len(all_accessor_kinds) == 1:   631                         test_type = ("test", "common", first(all_accessor_kinds))   632                     else:   633                         test_type = ("test", "common", "object")   634                     self.reference_test_types[location] = test_type   635                     self.reference_test_accessor_type[location] = provider   636    637             # Record the need to test the identity of the attribute.   638    639             else:   640                 self.reference_test_types[location] = ("validate",)   641    642     def initialise_access_plans(self):   643    644         "Define attribute access plans."   645    646         for location in self.referenced_attrs.keys():   647             original_location = self.const_accesses_rev.get(location)   648             self.access_plans[original_location or location] = self.get_access_plan(location)   649    650     def get_referenced_attrs(self, location):   651    652         """   653         Return attributes referenced at the given access 'location' by the given   654         'attrname' as a list of (attribute type, attribute set) tuples.   655         """   656    657         d = {}   658         for attrtype, objtype, attr in self.referenced_attrs[location]:   659             init_item(d, attrtype, set)   660             d[attrtype].add(attr.unaliased())   661         l = d.items()   662         l.sort() # class, module, instance   663         return l   664    665     # Initialisation methods.   666    667     def init_descendants(self):   668    669         "Identify descendants of each class."   670    671         for name in self.importer.classes.keys():   672             self.get_descendants_for_class(name)   673    674     def get_descendants_for_class(self, name):   675    676         """   677         Use subclass information to deduce the descendants for the class of the   678         given 'name'.   679         """   680    681         if not self.descendants.has_key(name):   682             descendants = set()   683    684             for subclass in self.importer.subclasses[name]:   685                 descendants.update(self.get_descendants_for_class(subclass))   686                 descendants.add(subclass)   687    688             self.descendants[name] = descendants   689    690         return self.descendants[name]   691    692     def init_special_attributes(self):   693    694         "Add special attributes to the classes for inheritance-related tests."   695    696         all_class_attrs = self.importer.all_class_attrs   697    698         for name, descendants in self.descendants.items():   699             for descendant in descendants:   700                 all_class_attrs[descendant]["#%s" % name] = name   701    702         for name in all_class_attrs.keys():   703             all_class_attrs[name]["#%s" % name] = name   704    705     def init_usage_index(self):   706    707         """   708         Create indexes for module and function attribute usage and for anonymous   709         accesses.   710         """   711    712         for module in self.importer.get_modules():   713             for path, assignments in module.attr_usage.items():   714                 self.add_usage(assignments, path)   715    716         for location, all_attrnames in self.importer.all_attr_accesses.items():   717             for attrnames in all_attrnames:   718                 attrname = get_attrnames(attrnames)[-1]   719                 access_location = (location, None, attrnames, 0)   720                 self.add_usage_term(access_location, ((attrname, False, False),))   721    722     def add_usage(self, assignments, path):   723    724         """   725         Collect usage from the given 'assignments', adding 'path' details to   726         each record if specified. Add the usage to an index mapping to location   727         information, as well as to an index mapping locations to usages.   728         """   729    730         for name, versions in assignments.items():   731             for i, usages in enumerate(versions):   732                 location = (path, name, None, i)   733    734                 for usage in usages:   735                     self.add_usage_term(location, usage)   736    737     def add_usage_term(self, location, usage):   738    739         """   740         For 'location' and using 'usage' as a description of usage, record   741         in the usage index a mapping from the usage to 'location', and record in   742         the location index a mapping from 'location' to the usage.   743         """   744    745         init_item(self.location_index, location, set)   746         self.location_index[location].add(usage)   747    748     def init_accessors(self):   749    750         "Create indexes for module and function accessor information."   751    752         for module in self.importer.get_modules():   753             for path, all_accesses in module.attr_accessors.items():   754                 self.add_accessors(all_accesses, path)   755    756     def add_accessors(self, all_accesses, path):   757    758         """   759         For attribute accesses described by the mapping of 'all_accesses' from   760         name details to accessor details, record the locations of the accessors   761         for each access.   762         """   763    764         # Get details for each access combining the given name and attribute.   765    766         for (name, attrnames), accesses in all_accesses.items():   767    768             # Obtain the usage details using the access information.   769    770             for access_number, versions in enumerate(accesses):   771                 access_location = (path, name, attrnames, access_number)   772                 locations = []   773    774                 for version in versions:   775                     location = (path, name, None, version)   776                     locations.append(location)   777    778                 self.access_index[access_location] = locations   779    780     def get_accessors_for_access(self, access_location):   781    782         "Find a definition providing accessor details, if necessary."   783    784         try:   785             return self.access_index[access_location]   786         except KeyError:   787             return [access_location]   788    789     def init_accesses(self):   790    791         """   792         Initialise collections for accesses involving assignments.   793         """   794    795         # For each scope, obtain access details.   796    797         for path, all_accesses in self.importer.all_attr_access_modifiers.items():   798    799             # For each combination of name and attribute names, obtain   800             # applicable modifiers.   801    802             for (name, attrname_str), modifiers in all_accesses.items():   803    804                 # For each access, determine the name versions affected by   805                 # assignments.   806    807                 for access_number, (assignment, invocation) in enumerate(modifiers):   808                     if not assignment and not invocation:   809                         continue   810    811                     if name:   812                         access_location = (path, name, attrname_str, access_number)   813                     else:   814                         access_location = (path, None, attrname_str, 0)   815    816                     if invocation:   817                         self.reference_invocations.add(access_location)   818                         continue   819    820                     self.reference_assignments.add(access_location)   821    822                     # Associate assignments with usage.   823    824                     attrnames = get_attrnames(attrname_str)   825    826                     # Assignment occurs for the only attribute.   827    828                     if len(attrnames) == 1:   829                         accessor_locations = self.get_accessors_for_access(access_location)   830    831                         for location in accessor_locations:   832                             for usage in self.location_index[location]:   833                                 init_item(self.assigned_attrs, usage, set)   834                                 self.assigned_attrs[usage].add((path, name, attrnames[0]))   835    836                     # Assignment occurs for the final attribute.   837    838                     else:   839                         usage = ((attrnames[-1], False, False),)   840                         init_item(self.assigned_attrs, usage, set)   841                         self.assigned_attrs[usage].add((path, name, attrnames[-1]))   842    843     def init_aliases(self):   844    845         "Expand aliases so that alias-based accesses can be resolved."   846    847         # Get aliased names with details of their accesses.   848    849         for name_path, all_aliases in self.importer.all_aliased_names.items():   850             path, name = name_path.rsplit(".", 1)   851    852             # For each version of the name, obtain the access location.   853    854             for version, (original_name, attrnames, access_number) in all_aliases.items():   855                 accessor_location = (path, name, None, version)   856                 access_location = (path, original_name, attrnames, access_number)   857                 init_item(self.alias_index, accessor_location, list)   858                 self.alias_index[accessor_location].append(access_location)   859    860         # Get aliases in terms of non-aliases and accesses.   861    862         for accessor_location, access_locations in self.alias_index.items():   863             self.update_aliases(accessor_location, access_locations)   864    865     def update_aliases(self, accessor_location, access_locations, visited=None):   866    867         """   868         Update the given 'accessor_location' defining an alias, update   869         'access_locations' to refer to non-aliases, following name references   870         via the access index.   871    872         If 'visited' is specified, it contains a set of accessor locations (and   873         thus keys to the alias index) that are currently being defined.   874         """   875    876         if visited is None:   877             visited = set()   878    879         updated_locations = set()   880    881         for access_location in access_locations:   882             (path, original_name, attrnames, access_number) = access_location   883    884             # Where an alias refers to a name access, obtain the original name   885             # version details.   886    887             if attrnames is None:   888    889                 # For each name version, attempt to determine any accesses that   890                 # initialise the name.   891    892                 for name_accessor_location in self.access_index[access_location]:   893    894                     # Already-visited aliases do not contribute details.   895    896                     if name_accessor_location in visited:   897                         continue   898    899                     visited.add(name_accessor_location)   900    901                     name_access_locations = self.alias_index.get(name_accessor_location)   902                     if name_access_locations:   903                         updated_locations.update(self.update_aliases(name_accessor_location, name_access_locations, visited))   904                     else:   905                         updated_locations.add(name_accessor_location)   906    907             # Otherwise, record the access details.   908    909             else:   910                 updated_locations.add(access_location)   911    912         self.alias_index[accessor_location] = updated_locations   913         return updated_locations   914    915     # Attribute mutation for types.   916    917     def modify_mutated_attributes(self):   918    919         "Identify known, mutated attributes and change their state."   920    921         # Usage-based accesses.   922    923         for usage, all_attrnames in self.assigned_attrs.items():   924             if not usage:   925                 continue   926    927             for path, name, attrname in all_attrnames:   928                 class_types = self.get_class_types_for_usage(usage)   929                 only_instance_types = set(self.get_instance_types_for_usage(usage)).difference(class_types)   930                 module_types = self.get_module_types_for_usage(usage)   931    932                 # Detect self usage within methods in order to narrow the scope   933                 # of the mutation.   934    935                 t = name == "self" and self.constrain_self_reference(path, class_types, only_instance_types)   936                 if t:   937                     class_types, only_instance_types, module_types, constrained = t   938                 objects = set(class_types).union(only_instance_types).union(module_types)   939    940                 self.mutate_attribute(objects, attrname)   941    942     def mutate_attribute(self, objects, attrname):   943    944         "Mutate static 'objects' with the given 'attrname'."   945    946         for name in objects:   947             attr = "%s.%s" % (name, attrname)   948             value = self.importer.get_object(attr)   949    950             # If the value is None, the attribute is   951             # inherited and need not be set explicitly on   952             # the class concerned.   953    954             if value:   955                 self.modified_attributes[attr] = value   956                 self.importer.set_object(attr, value.as_var())   957    958     # Simplification of types.   959    960     def get_most_general_types(self, types):   961    962         "Return the most general types for the given 'types'."   963    964         module_types = set()   965         class_types = set()   966    967         for type in types:   968             ref = self.importer.identify(type)   969             if ref.has_kind("<module>"):   970                 module_types.add(type)   971             else:   972                 class_types.add(type)   973    974         types = set(self.get_most_general_module_types(module_types))   975         types.update(self.get_most_general_class_types(class_types))   976         return types   977    978     def get_most_general_class_types(self, class_types):   979    980         "Return the most general types for the given 'class_types'."   981    982         class_types = set(class_types)   983         to_remove = set()   984    985         for class_type in class_types:   986             for base in self.importer.classes[class_type]:   987                 base = base.get_origin()   988                 descendants = self.descendants[base]   989                 if base in class_types and descendants.issubset(class_types):   990                     to_remove.update(descendants)   991    992         class_types.difference_update(to_remove)   993         return class_types   994    995     def get_most_general_module_types(self, module_types):   996    997         "Return the most general type for the given 'module_types'."   998    999         # Where all modules are provided, an object would provide the same  1000         # attributes.  1001   1002         if len(module_types) == len(self.importer.modules):  1003             return ["__builtins__.object"]  1004         else:  1005             return module_types  1006   1007     # More efficient usage-to-type indexing and retrieval.  1008   1009     def init_attr_type_indexes(self):  1010   1011         "Identify the types that can support each attribute name."  1012   1013         self._init_attr_type_index(self.attr_class_types, self.importer.all_class_attrs)  1014         self._init_attr_type_index(self.attr_instance_types, self.importer.all_instance_attrs, True)  1015         self._init_attr_type_index(self.attr_instance_types, self.importer.all_combined_attrs, False)  1016         self._init_attr_type_index(self.attr_module_types, self.importer.all_module_attrs)  1017   1018     def _init_attr_type_index(self, attr_types, attrs, assignment=None):  1019   1020         """  1021         Initialise the 'attr_types' attribute-to-types mapping using the given  1022         'attrs' type-to-attributes mapping.  1023         """  1024   1025         for name, attrnames in attrs.items():  1026             for attrname in attrnames:  1027   1028                 # Permit general access for certain kinds of object.  1029   1030                 if assignment is None:  1031                     init_item(attr_types, (attrname, False), set)  1032                     init_item(attr_types, (attrname, True), set)  1033                     attr_types[(attrname, False)].add(name)  1034                     attr_types[(attrname, True)].add(name)  1035   1036                 # Restrict attribute assignment for instances.  1037   1038                 else:  1039                     init_item(attr_types, (attrname, assignment), set)  1040                     attr_types[(attrname, assignment)].add(name)  1041   1042     def get_class_types_for_usage(self, usage):  1043   1044         "Return names of classes supporting the given 'usage'."  1045   1046         return self._get_types_for_usage(usage, self.attr_class_types, self.importer.all_class_attrs)  1047   1048     def get_instance_types_for_usage(self, usage):  1049   1050         """  1051         Return names of classes whose instances support the given 'usage'  1052         (as either class or instance attributes).  1053         """  1054   1055         return self._get_types_for_usage(usage, self.attr_instance_types, self.importer.all_combined_attrs)  1056   1057     def get_module_types_for_usage(self, usage):  1058   1059         "Return names of modules supporting the given 'usage'."  1060   1061         return self._get_types_for_usage(usage, self.attr_module_types, self.importer.all_module_attrs)  1062   1063     def _get_types_for_usage(self, usage, attr_types, attrs):  1064   1065         """  1066         For the given 'usage' representing attribute usage, return types  1067         recorded in the 'attr_types' attribute-to-types mapping that support  1068         such usage, with the given 'attrs' type-to-attributes mapping used to  1069         quickly assess whether a type supports all of the stated attributes.  1070         """  1071   1072         # Where no attributes are used, any type would be acceptable.  1073   1074         if not usage:  1075             return attrs.keys()  1076   1077         keys = []  1078         for attrname, invocation, assignment in usage:  1079             keys.append((attrname, assignment))  1080   1081         # Obtain types supporting the first (attribute name, assignment) key...  1082   1083         types = set(attr_types.get(keys[0]) or [])  1084   1085         for key in keys[1:]:  1086               1087             # Record types that support all of the other attributes as well.  1088   1089             types.intersection_update(attr_types.get(key) or [])  1090   1091         return types  1092   1093     # Reference identification.  1094   1095     def identify_references(self):  1096   1097         "Identify references using usage and name reference information."  1098   1099         # Names with associated attribute usage.  1100   1101         for location, usages in self.location_index.items():  1102   1103             # Obtain attribute usage associated with a name, deducing the nature  1104             # of the name. Obtain types only for branches involving attribute  1105             # usage. (In the absence of usage, any type could be involved, but  1106             # then no accesses exist to require knowledge of the type.)  1107   1108             have_usage = False  1109             have_no_usage_branch = False  1110   1111             for usage in usages:  1112                 if not usage:  1113                     have_no_usage_branch = True  1114                     continue  1115                 elif not have_usage:  1116                     self.init_definition_details(location)  1117                     have_usage = True  1118                 self.record_types_for_usage(location, usage)  1119   1120             # Where some usage occurs, but where branches without usage also  1121             # occur, record the types for those branches anyway.  1122   1123             if have_usage and have_no_usage_branch:  1124                 self.init_definition_details(location)  1125                 self.record_types_for_usage(location, None)  1126   1127         # Specific name-based attribute accesses.  1128   1129         alias_accesses = set()  1130   1131         for access_location, accessor_locations in self.access_index.items():  1132             self.record_types_for_access(access_location, accessor_locations, alias_accesses)  1133   1134         # Anonymous references with attribute chains.  1135   1136         for location, accesses in self.importer.all_attr_accesses.items():  1137   1138             # Get distinct attribute names.  1139   1140             all_attrnames = set()  1141   1142             for attrnames in accesses:  1143                 all_attrnames.update(get_attrnames(attrnames))  1144   1145             # Get attribute and accessor details for each attribute name.  1146   1147             for attrname in all_attrnames:  1148                 access_location = (location, None, attrname, 0)  1149                 self.record_types_for_attribute(access_location, attrname)  1150   1151         # References via constant/identified objects.  1152   1153         for location, name_accesses in self.importer.all_const_accesses.items():  1154   1155             # A mapping from the original name and attributes to resolved access  1156             # details.  1157   1158             for original_access, access in name_accesses.items():  1159                 original_name, original_attrnames = original_access  1160                 objpath, ref, attrnames = access  1161   1162                 # Build an accessor combining the name and attribute names used.  1163   1164                 original_accessor = tuple([original_name] + original_attrnames.split("."))  1165   1166                 # Direct accesses to attributes.  1167   1168                 if not attrnames:  1169   1170                     # Build a descriptive location based on the original  1171                     # details, exposing the final attribute name.  1172   1173                     oa, attrname = original_accessor[:-1], original_accessor[-1]  1174                     oa = ".".join(oa)  1175   1176                     access_location = (location, oa, attrname, 0)  1177                     accessor_location = (location, oa, None, 0)  1178                     self.access_index[access_location] = [accessor_location]  1179   1180                     self.init_access_details(access_location)  1181                     self.init_definition_details(accessor_location)  1182   1183                     # Obtain a reference for the accessor in order to properly  1184                     # determine its type.  1185   1186                     if ref.get_kind() != "<instance>":  1187                         objpath = ref.get_origin()  1188   1189                     objpath = objpath.rsplit(".", 1)[0]  1190   1191                     # Where the object name conflicts with the module  1192                     # providing it, obtain the module details.  1193   1194                     if objpath in self.importer.modules:  1195                         accessor = Reference("<module>", objpath)  1196                     else:  1197                         accessor = self.importer.get_object(objpath)  1198   1199                     self.referenced_attrs[access_location] = [(accessor.get_kind(), accessor.get_origin(), ref)]  1200                     self.access_constrained.add(access_location)  1201   1202                     class_types, instance_types, module_types = accessor.get_types()  1203                     self.record_reference_types(accessor_location, class_types, instance_types, module_types, True, True)  1204   1205                 else:  1206   1207                     # Build a descriptive location based on the original  1208                     # details, employing the first remaining attribute name.  1209   1210                     l = get_attrnames(attrnames)  1211                     attrname = l[0]  1212   1213                     oa = original_accessor[:-len(l)]  1214                     oa = ".".join(oa)  1215   1216                     access_location = (location, oa, attrnames, 0)  1217                     accessor_location = (location, oa, None, 0)  1218                     self.access_index[access_location] = [accessor_location]  1219   1220                     self.init_access_details(access_location)  1221                     self.init_definition_details(accessor_location)  1222   1223                     class_types, instance_types, module_types = ref.get_types()  1224   1225                     self.identify_reference_attributes(access_location, attrname, class_types, instance_types, module_types, True)  1226                     self.record_reference_types(accessor_location, class_types, instance_types, module_types, True, True)  1227   1228                 original_location = (location, original_name, original_attrnames, 0)  1229   1230                 if original_location != access_location:  1231                     self.const_accesses[original_location] = access_location  1232                     self.const_accesses_rev[access_location] = original_location  1233   1234         # Aliased name definitions. All aliases with usage will have been  1235         # defined, but they may be refined according to referenced accesses.  1236   1237         for accessor_location in self.alias_index.keys():  1238             self.record_types_for_alias(accessor_location)  1239   1240         # Update accesses employing aliases.  1241   1242         for access_location in alias_accesses:  1243             self.record_types_for_access(access_location, self.access_index[access_location])  1244   1245     def constrain_types(self, path, class_types, instance_types, module_types):  1246   1247         """  1248         Using the given 'path' to an object, constrain the given 'class_types',  1249         'instance_types' and 'module_types'.  1250   1251         Return the class, instance, module types plus whether the types are  1252         constrained to a specific kind of type.  1253         """  1254   1255         ref = self.importer.identify(path)  1256         if ref:  1257   1258             # Constrain usage suggestions using the identified object.  1259   1260             if ref.has_kind("<class>"):  1261                 return (  1262                     set(class_types).intersection([ref.get_origin()]), [], [], True  1263                     )  1264             elif ref.has_kind("<module>"):  1265                 return (  1266                     [], [], set(module_types).intersection([ref.get_origin()]), True  1267                     )  1268   1269         return class_types, instance_types, module_types, False  1270   1271     def get_target_types(self, location, usage):  1272   1273         """  1274         Return the class, instance and module types constrained for the name at  1275         the given 'location' exhibiting the given 'usage'. Whether the types  1276         have been constrained using contextual information is also indicated,  1277         plus whether the types have been constrained to a specific kind of type.  1278         """  1279   1280         unit_path, name, attrnames, version = location  1281         have_assignments = get_assigned_attributes(usage)  1282   1283         # Detect any initialised name for the location.  1284   1285         if name:  1286             ref = self.get_initialised_name(location)  1287             if ref:  1288                 (class_types, only_instance_types, module_types,  1289                     _function_types, _var_types) = separate_types([ref])  1290                 return class_types, only_instance_types, module_types, True, have_assignments  1291   1292         # Retrieve the recorded types for the usage.  1293   1294         class_types = self.get_class_types_for_usage(usage)  1295         only_instance_types = set(self.get_instance_types_for_usage(usage)).difference(class_types)  1296         module_types = self.get_module_types_for_usage(usage)  1297   1298         # Merge usage deductions with observations to obtain reference types  1299         # for names involved with attribute accesses.  1300   1301         if not name:  1302             return class_types, only_instance_types, module_types, False, have_assignments  1303   1304         # Obtain references to known objects.  1305   1306         path = get_name_path(unit_path, name)  1307   1308         class_types, only_instance_types, module_types, constrained_specific = \  1309             self.constrain_types(path, class_types, only_instance_types, module_types)  1310   1311         if constrained_specific:  1312             return class_types, only_instance_types, module_types, constrained_specific, \  1313                 constrained_specific or have_assignments  1314   1315         # Constrain "self" references.  1316   1317         if name == "self":  1318             t = self.constrain_self_reference(unit_path, class_types, only_instance_types)  1319             if t:  1320                 class_types, only_instance_types, module_types, constrained = t  1321                 return class_types, only_instance_types, module_types, constrained, have_assignments  1322   1323         return class_types, only_instance_types, module_types, False, have_assignments  1324   1325     def constrain_self_reference(self, unit_path, class_types, only_instance_types):  1326   1327         """  1328         Where the name "self" appears in a method, attempt to constrain the  1329         classes involved.  1330   1331         Return the class, instance, module types plus whether the types are  1332         constrained.  1333         """  1334   1335         class_name = self.in_method(unit_path)  1336   1337         if not class_name:  1338             return None  1339   1340         classes = set([class_name])  1341         classes.update(self.get_descendants_for_class(class_name))  1342   1343         # Note that only instances will be expected for these references but  1344         # either classes or instances may provide the attributes.  1345   1346         return (  1347             set(class_types).intersection(classes),  1348             set(only_instance_types).intersection(classes),  1349             [], True  1350             )  1351   1352     def in_method(self, path):  1353   1354         "Return whether 'path' refers to a method."  1355   1356         class_name, method_name = path.rsplit(".", 1)  1357         return class_name != "__builtins__.core.type" and self.importer.classes.has_key(class_name) and class_name  1358   1359     def init_reference_details(self, location):  1360   1361         "Initialise reference-related details for 'location'."  1362   1363         self.init_definition_details(location)  1364         self.init_access_details(location)  1365   1366     def init_definition_details(self, location):  1367   1368         "Initialise name definition details for 'location'."  1369   1370         self.accessor_class_types[location] = set()  1371         self.accessor_instance_types[location] = set()  1372         self.accessor_module_types[location] = set()  1373         self.provider_class_types[location] = set()  1374         self.provider_instance_types[location] = set()  1375         self.provider_module_types[location] = set()  1376   1377     def init_access_details(self, location):  1378   1379         "Initialise access details at 'location'."  1380   1381         self.referenced_attrs[location] = {}  1382   1383     def record_types_for_access(self, access_location, accessor_locations, alias_accesses=None):  1384   1385         """  1386         Define types for the 'access_location' associated with the given  1387         'accessor_locations'.  1388         """  1389   1390         attrname = get_attrname_from_location(access_location)  1391         if not attrname:  1392             return  1393   1394         # Collect all suggested types for the accessors. Accesses may  1395         # require accessors from of a subset of the complete set of types.  1396   1397         class_types = set()  1398         module_types = set()  1399         instance_types = set()  1400   1401         constrained = True  1402   1403         for location in accessor_locations:  1404   1405             # Remember accesses employing aliases.  1406   1407             if alias_accesses is not None and self.alias_index.has_key(location):  1408                 alias_accesses.add(access_location)  1409   1410             # Use the type information deduced for names from above.  1411   1412             if self.accessor_class_types.has_key(location):  1413                 class_types.update(self.accessor_class_types[location])  1414                 module_types.update(self.accessor_module_types[location])  1415                 instance_types.update(self.accessor_instance_types[location])  1416   1417             # Where accesses are associated with assignments but where no  1418             # attribute usage observations have caused such an association,  1419             # the attribute name is considered by itself.  1420   1421             else:  1422                 self.init_definition_details(location)  1423                 self.record_types_for_usage(location, [(attrname, False, False)])  1424   1425             constrained = location in self.accessor_constrained and constrained  1426   1427         self.init_access_details(access_location)  1428         self.identify_reference_attributes(access_location, attrname, class_types, instance_types, module_types, constrained)  1429   1430     def record_types_for_usage(self, accessor_location, usage):  1431   1432         """  1433         Record types for the given 'accessor_location' according to the given  1434         'usage' observations which may be None to indicate an absence of usage.  1435         """  1436   1437         (class_types,  1438          instance_types,  1439          module_types,  1440          constrained,  1441          constrained_specific) = self.get_target_types(accessor_location, usage)  1442   1443         invocations = get_invoked_attributes(usage)  1444   1445         self.record_reference_types(accessor_location, class_types, instance_types,  1446             module_types, constrained, constrained_specific, invocations)  1447   1448     def record_types_for_attribute(self, access_location, attrname):  1449   1450         """  1451         Record types for the 'access_location' employing only the given  1452         'attrname' for type deduction.  1453         """  1454   1455         (class_types,  1456          only_instance_types,  1457          module_types) = self.get_types_for_attribute(attrname)  1458   1459         self.init_reference_details(access_location)  1460   1461         self.identify_reference_attributes(access_location, attrname, class_types, only_instance_types, module_types, False)  1462         self.record_reference_types(access_location, class_types, only_instance_types, module_types, False)  1463   1464     def get_types_for_attribute(self, attrname):  1465   1466         "Return class, instance-only and module types supporting 'attrname'."  1467   1468         usage = ((attrname, False, False),)  1469   1470         class_types = self.get_class_types_for_usage(usage)  1471         only_instance_types = set(self.get_instance_types_for_usage(usage)).difference(class_types)  1472         module_types = self.get_module_types_for_usage(usage)  1473   1474         return class_types, only_instance_types, module_types  1475   1476     def record_types_for_alias(self, accessor_location):  1477   1478         """  1479         Define types for the 'accessor_location' not having associated usage.  1480         """  1481   1482         have_access = self.provider_class_types.has_key(accessor_location)  1483   1484         # With an access, attempt to narrow the existing selection of provider  1485         # types.  1486   1487         if have_access:  1488             provider_class_types = self.provider_class_types[accessor_location]  1489             provider_instance_types = self.provider_instance_types[accessor_location]  1490             provider_module_types = self.provider_module_types[accessor_location]  1491   1492             # Find details for any corresponding access.  1493   1494             all_class_types = set()  1495             all_instance_types = set()  1496             all_module_types = set()  1497   1498             for access_location in self.alias_index[accessor_location]:  1499                 location, name, attrnames, access_number = access_location  1500   1501                 # Alias references an attribute access.  1502   1503                 if attrnames:  1504   1505                     # Obtain attribute references for the access.  1506   1507                     attrs = [attr for _attrtype, object_type, attr in self.referenced_attrs[access_location]]  1508   1509                     # Separate the different attribute types.  1510   1511                     (class_types, instance_types, module_types,  1512                         function_types, var_types) = separate_types(attrs)  1513   1514                     # Where non-accessor types are found, do not attempt to refine  1515                     # the defined accessor types.  1516   1517                     if function_types or var_types:  1518                         return  1519   1520                     class_types = set(provider_class_types).intersection(class_types)  1521                     instance_types = set(provider_instance_types).intersection(instance_types)  1522                     module_types = set(provider_module_types).intersection(module_types)  1523   1524                 # Alias references a name, not an access.  1525   1526                 else:  1527                     # Attempt to refine the types using initialised names.  1528   1529                     attr = self.get_initialised_name(access_location)  1530                     if attr:  1531                         (class_types, instance_types, module_types,  1532                             _function_types, _var_types) = separate_types([attr])  1533   1534                     # Where no further information is found, do not attempt to  1535                     # refine the defined accessor types.  1536   1537                     else:  1538                         return  1539   1540                 all_class_types.update(class_types)  1541                 all_instance_types.update(instance_types)  1542                 all_module_types.update(module_types)  1543   1544             # Record refined type details for the alias as an accessor.  1545   1546             self.init_definition_details(accessor_location)  1547             self.record_reference_types(accessor_location, all_class_types, all_instance_types, all_module_types, False)  1548   1549         # Without an access, attempt to identify references for the alias.  1550   1551         else:  1552             refs = set()  1553   1554             for access_location in self.alias_index[accessor_location]:  1555   1556                 # Obtain any redefined constant access location.  1557   1558                 if self.const_accesses.has_key(access_location):  1559                     access_location = self.const_accesses[access_location]  1560   1561                 location, name, attrnames, access_number = access_location  1562   1563                 # Alias references an attribute access.  1564   1565                 if attrnames:  1566                     attrs = [attr for attrtype, object_type, attr in self.referenced_attrs[access_location]]  1567                     refs.update(attrs)  1568   1569                 # Alias references a name, not an access.  1570   1571                 else:  1572                     attr = self.get_initialised_name(access_location)  1573                     attrs = attr and [attr] or []  1574                     if not attrs and self.provider_class_types.has_key(access_location):  1575                         class_types = self.provider_class_types[access_location]  1576                         instance_types = self.provider_instance_types[access_location]  1577                         module_types = self.provider_module_types[access_location]  1578                         attrs = combine_types(class_types, instance_types, module_types)  1579                     if attrs:  1580                         refs.update(attrs)  1581   1582             # Record reference details for the alias separately from accessors.  1583   1584             self.referenced_objects[accessor_location] = refs  1585   1586     def get_initialised_name(self, access_location):  1587   1588         """  1589         Return references for any initialised names at 'access_location', or  1590         None if no such references exist.  1591         """  1592   1593         location, name, attrnames, version = access_location  1594         path = get_name_path(location, name)  1595   1596         # Use initialiser information, if available.  1597   1598         refs = self.importer.all_initialised_names.get(path)  1599         if refs and refs.has_key(version):  1600             return refs[version]  1601         else:  1602             return None  1603   1604     def record_reference_types(self, location, class_types, instance_types,  1605         module_types, constrained, constrained_specific=False, invocations=None):  1606   1607         """  1608         Associate attribute provider types with the given 'location', consisting  1609         of the given 'class_types', 'instance_types' and 'module_types'.  1610   1611         If 'constrained' is indicated, the constrained nature of the accessor is  1612         recorded for the location.  1613   1614         If 'constrained_specific' is indicated using a true value, instance types  1615         will not be added to class types to permit access via instances at the  1616         given location. This is only useful where a specific accessor is known  1617         to be a class.  1618   1619         If 'invocations' is given, the given attribute names indicate those  1620         which are involved in invocations. Such invocations, if involving  1621         functions, will employ those functions as bound methods and will  1622         therefore not support classes as accessors, only instances of such  1623         classes.  1624   1625         Note that the specified types only indicate the provider types for  1626         attributes, whereas the recorded accessor types indicate the possible  1627         types of the actual objects used to access attributes.  1628         """  1629   1630         # Update the type details for the location.  1631   1632         self.provider_class_types[location].update(class_types)  1633         self.provider_instance_types[location].update(instance_types)  1634         self.provider_module_types[location].update(module_types)  1635   1636         # Class types support classes and instances as accessors.  1637         # Instance-only and module types support only their own kinds as  1638         # accessors.  1639   1640         path, name, version, attrnames = location  1641   1642         if invocations:  1643             class_only_types = self.filter_for_invocations(class_types, invocations)  1644         else:  1645             class_only_types = class_types  1646   1647         # However, the nature of accessors can be further determined.  1648         # Any self variable may only refer to an instance.  1649   1650         if name != "self" or not self.in_method(path):  1651             self.accessor_class_types[location].update(class_only_types)  1652   1653         if not constrained_specific:  1654             self.accessor_instance_types[location].update(class_types)  1655   1656         self.accessor_instance_types[location].update(instance_types)  1657   1658         if name != "self" or not self.in_method(path):  1659             self.accessor_module_types[location].update(module_types)  1660   1661         if constrained:  1662             self.accessor_constrained.add(location)  1663   1664     def filter_for_invocations(self, class_types, attrnames):  1665   1666         """  1667         From the given 'class_types', identify methods for the given  1668         'attrnames' that are being invoked, returning a filtered collection of  1669         class types.  1670         """  1671   1672         to_filter = set()  1673   1674         for class_type in class_types:  1675             for attrname in attrnames:  1676                 ref = self.importer.get_class_attribute(class_type, attrname)  1677                 parent_class = ref and ref.parent()  1678   1679                 if ref and ref.has_kind("<function>") and (  1680                    parent_class == class_type or  1681                    class_type in self.descendants[parent_class]):  1682   1683                     to_filter.add(class_type)  1684                     break  1685   1686         return set(class_types).difference(to_filter)  1687   1688     def identify_reference_attributes(self, location, attrname, class_types, instance_types, module_types, constrained):  1689   1690         """  1691         Identify reference attributes, associating them with the given  1692         'location', identifying the given 'attrname', employing the given  1693         'class_types', 'instance_types' and 'module_types'.  1694   1695         If 'constrained' is indicated, the constrained nature of the access is  1696         recorded for the location.  1697         """  1698   1699         # Record the referenced objects.  1700   1701         self.referenced_attrs[location] = \  1702             self._identify_reference_attribute(attrname, class_types, instance_types, module_types)  1703   1704         if constrained:  1705             self.access_constrained.add(location)  1706   1707     def _identify_reference_attribute(self, attrname, class_types, instance_types, module_types):  1708   1709         """  1710         Identify the reference attribute with the given 'attrname', employing  1711         the given 'class_types', 'instance_types' and 'module_types'.  1712         """  1713   1714         attrs = set()  1715   1716         # The class types expose class attributes either directly or via  1717         # instances.  1718   1719         for object_type in class_types:  1720             ref = self.importer.get_class_attribute(object_type, attrname)  1721             if ref:  1722                 attrs.add(("<class>", object_type, ref))  1723   1724             # Add any distinct instance attributes that would be provided  1725             # by instances also providing indirect class attribute access.  1726   1727             for ref in self.importer.get_instance_attributes(object_type, attrname):  1728                 attrs.add(("<instance>", object_type, ref))  1729   1730         # The instance-only types expose instance attributes, but although  1731         # classes are excluded as potential accessors (since they do not provide  1732         # the instance attributes), the class types may still provide some  1733         # attributes.  1734   1735         for object_type in instance_types:  1736             instance_attrs = self.importer.get_instance_attributes(object_type, attrname)  1737   1738             if instance_attrs:  1739                 for ref in instance_attrs:  1740                     attrs.add(("<instance>", object_type, ref))  1741             else:  1742                 ref = self.importer.get_class_attribute(object_type, attrname)  1743                 if ref:  1744                     attrs.add(("<class>", object_type, ref))  1745   1746         # Module types expose module attributes for module accessors.  1747   1748         for object_type in module_types:  1749             ref = self.importer.get_module_attribute(object_type, attrname)  1750             if ref:  1751                 attrs.add(("<module>", object_type, ref))  1752   1753         return attrs  1754   1755     class_tests = (  1756         ("guarded", "specific", "type"),  1757         ("guarded", "common", "type"),  1758         ("test", "specific", "type"),  1759         ("test", "common", "type"),  1760         )  1761   1762     def get_access_plan(self, location):  1763   1764         """  1765         Return details of the access at the given 'location'. The details are as  1766         follows:  1767   1768          * the initial accessor (from which accesses will be performed if no  1769            computed static accessor is found)  1770          * details of any test required on the initial accessor  1771          * details of any type employed by the test  1772          * any static accessor (from which accesses will be performed in  1773            preference to the initial accessor)  1774          * attributes needing to be traversed from the base that yield  1775            unambiguous objects  1776          * access modes for each of the unambiguously-traversed attributes  1777          * remaining attributes needing to be tested and traversed  1778          * details of the context  1779          * any test to apply to the context  1780          * the method of obtaining the final attribute  1781          * any static final attribute  1782         """  1783   1784         const_access = self.const_accesses_rev.get(location)  1785   1786         path, name, attrnames, version = location  1787         remaining = attrnames.split(".")  1788         attrname = remaining[0]  1789   1790         # Obtain reference and accessor information, retaining also distinct  1791         # provider kind details.  1792   1793         attrs = []  1794         objtypes = []  1795         provider_kinds = set()  1796   1797         for attrtype, objtype, attr in self.referenced_attrs[location]:  1798             attrs.append(attr)  1799             objtypes.append(objtype)  1800             provider_kinds.add(attrtype)  1801   1802         # Obtain accessor type and kind information.  1803   1804         accessor_types = self.reference_all_accessor_types[location]  1805         accessor_general_types = self.reference_all_accessor_general_types[location]  1806         accessor_kinds = get_kinds(accessor_general_types)  1807   1808         # Determine any guard or test requirements.  1809   1810         constrained = location in self.access_constrained  1811         test = self.reference_test_types[location]  1812         test_type = self.reference_test_accessor_type.get(location)  1813   1814         # Determine the accessor and provider properties.  1815   1816         class_accessor = "<class>" in accessor_kinds  1817         module_accessor = "<module>" in accessor_kinds  1818         instance_accessor = "<instance>" in accessor_kinds  1819         provided_by_class = "<class>" in provider_kinds  1820         provided_by_instance = "<instance>" in provider_kinds  1821   1822         # Determine how attributes may be accessed relative to the accessor.  1823   1824         object_relative = class_accessor or module_accessor or provided_by_instance  1825         class_relative = instance_accessor and provided_by_class  1826   1827         # Identify the last static attribute for context acquisition.  1828   1829         base = None  1830         dynamic_base = None  1831   1832         # Constant accesses have static accessors.  1833   1834         if const_access:  1835             base = len(objtypes) == 1 and first(objtypes)  1836   1837         # Name-based accesses.  1838   1839         elif name:  1840             ref = self.importer.identify("%s.%s" % (path, name))  1841   1842             # Constant accessors are static.  1843   1844             if ref and ref.static():  1845                 base = ref.get_origin()  1846   1847             # Usage of previously-generated guard and test details.  1848   1849             elif test[:2] == ("constrained", "specific"):  1850                 ref = first(accessor_types)  1851   1852             elif test[:2] == ("constrained", "common"):  1853                 ref = first(accessor_general_types)  1854   1855             elif test[:2] == ("guarded", "specific"):  1856                 ref = first(accessor_types)  1857   1858             elif test[:2] == ("guarded", "common"):  1859                 ref = first(accessor_general_types)  1860   1861             # For attribute-based tests, tentatively identify a dynamic base.  1862             # Such tests allow single or multiple kinds of a type.  1863   1864             elif test[0] == "test" and test[1] in ("common", "specific"):  1865                 dynamic_base = test_type  1866   1867             # Static accessors.  1868   1869             if not base and test in self.class_tests:  1870                 base = ref and ref.get_origin() or dynamic_base  1871   1872             # Accessors that are not static but whose nature is determined.  1873   1874             elif not base and ref:  1875                 dynamic_base = ref.get_origin()  1876   1877         # Determine initial accessor details.  1878   1879         accessor = base or dynamic_base  1880         accessor_kind = len(accessor_kinds) == 1 and first(accessor_kinds) or None  1881         provider_kind = len(provider_kinds) == 1 and first(provider_kinds) or None  1882   1883         # Traverse remaining attributes.  1884   1885         traversed = []  1886         traversal_modes = []  1887   1888         while len(attrs) == 1 and not first(attrs).has_kind("<var>"):  1889             attr = first(attrs)  1890   1891             traversed.append(attrname)  1892             traversal_modes.append(accessor_kind == provider_kind and "object" or "class")  1893   1894             # Consume attribute names providing unambiguous attributes.  1895   1896             del remaining[0]  1897   1898             if not remaining:  1899                 break  1900   1901             # Update the last static attribute.  1902   1903             if attr.static():  1904                 base = attr.get_origin()  1905                 traversed = []  1906                 traversal_modes = []  1907   1908             # Get the access details.  1909   1910             attrname = remaining[0]  1911             accessor = attr.get_origin()  1912             accessor_kind = attr.get_kind()  1913             provider_kind = self.importer.get_attribute_provider(attr, attrname)  1914             accessor_kinds = [accessor_kind]  1915             provider_kinds = [provider_kind]  1916   1917             # Get the next attribute.  1918   1919             attrs = self.importer.get_attributes(attr, attrname)  1920   1921         # Where many attributes are suggested, no single attribute identity can  1922         # be loaded.  1923   1924         else:  1925             attr = None  1926   1927         # Determine the method of access.  1928   1929         is_assignment = location in self.reference_assignments or const_access in self.reference_assignments  1930         is_invocation = location in self.reference_invocations or const_access in self.reference_invocations  1931   1932         # Identified attribute that must be accessed via its parent.  1933   1934         if attr and attr.get_name() and is_assignment:  1935             final_method = "static-assign"; origin = attr.get_name()  1936   1937         # Static, identified attribute.  1938   1939         elif attr and attr.static():  1940             final_method = is_assignment and "static-assign" or \  1941                            is_invocation and "static-invoke" or \  1942                            "static"  1943             origin = attr.final()  1944   1945         # All other methods of access involve traversal.  1946   1947         else:  1948             final_method = is_assignment and "assign" or "access"  1949             origin = None  1950   1951         # First attribute accessed at a known position via the accessor.  1952   1953         if base or dynamic_base:  1954             first_method = "relative" + (object_relative and "-object" or "") + \  1955                                         (class_relative and "-class" or "")  1956   1957         # The fallback case is always run-time testing and access.  1958   1959         else:  1960             first_method = "check" + (object_relative and "-object" or "") + \  1961                                      (class_relative and "-class" or "")  1962   1963         # Determine whether an unbound method is being accessed via an instance,  1964         # requiring a context test.  1965   1966         context_test = "ignore"  1967   1968         # Assignments do not employ the context.  1969   1970         if is_assignment:  1971             pass  1972   1973         # Obtain a selection of possible attributes if no unambiguous attribute  1974         # was identified.  1975   1976         elif not attr:  1977   1978             # Use previously-deduced attributes for a simple ambiguous access.  1979             # Otherwise, use the final attribute name to obtain possible  1980             # attributes.  1981   1982             if len(remaining) > 1:  1983                 attrname = remaining[-1]  1984   1985                 (class_types,  1986                  only_instance_types,  1987                  module_types) = self.get_types_for_attribute(attrname)  1988   1989                 accessor_kinds = set()  1990                 provider_kinds = set()  1991   1992                 if class_types:  1993                     accessor_kinds.add("<class>")  1994                     accessor_kinds.add("<instance>")  1995                     provider_kinds.add("<class>")  1996                 if only_instance_types:  1997                     accessor_kinds.add("<instance>")  1998                     provider_kinds.add("<instance>")  1999                 if module_types:  2000                     accessor_kinds.add("<module>")  2001                     provider_kinds.add("<module>")  2002   2003                 attrs = set()  2004                 for type in combine_types(class_types, only_instance_types, module_types):  2005                     attrs.update(self.importer.get_attributes(type, attrname))  2006   2007             always_unbound = True  2008             have_function = False  2009             have_var = False  2010   2011             # Determine whether all attributes are unbound methods and whether  2012             # functions or unidentified attributes occur.  2013   2014             for attr in attrs:  2015                 always_unbound = always_unbound and attr.has_kind("<function>") and attr.name_parent() == attr.parent()  2016                 have_function = have_function or attr.has_kind("<function>")  2017                 have_var = have_var or attr.has_kind("<var>")  2018   2019             # Test for class-via-instance accesses.  2020   2021             if accessor_kind == "<instance>" and \  2022                provider_kind == "<class>":  2023   2024                 if always_unbound:  2025                     context_test = "replace"  2026                 else:  2027                     context_test = "test"  2028   2029             # Test for the presence of class-via-instance accesses.  2030   2031             elif "<instance>" in accessor_kinds and \  2032                  "<class>" in provider_kinds and \  2033                  (have_function or have_var):  2034   2035                 context_test = "test"  2036   2037         # With an unambiguous attribute, determine whether a test is needed.  2038   2039         elif accessor_kind == "<instance>" and \  2040              provider_kind == "<class>" and \  2041              (attr.has_kind("<var>") or  2042               attr.has_kind("<function>") and  2043               attr.name_parent() == attr.parent()):  2044   2045             if attr.has_kind("<var>"):  2046                 context_test = "test"  2047             else:  2048                 context_test = "replace"  2049   2050         # With an unambiguous attribute with ambiguity in the access method,  2051         # generate a test.  2052   2053         elif "<instance>" in accessor_kinds and \  2054              "<class>" in provider_kinds and \  2055              (attr.has_kind("<var>") or  2056               attr.has_kind("<function>") and  2057               attr.name_parent() == attr.parent()):  2058   2059             context_test = "test"  2060   2061         # Determine the nature of the context.  2062   2063         context = context_test == "ignore" and "unset" or \  2064                   len(traversed + remaining) == 1 and \  2065                       (base and "base" or "original-accessor") or \  2066                   "final-accessor"  2067   2068         return name, test, test_type, base, \  2069                traversed, traversal_modes, remaining, \  2070                context, context_test, \  2071                first_method, final_method, \  2072                origin, accessor_kinds  2073   2074 # vim: tabstop=4 expandtab shiftwidth=4