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