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