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