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