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