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