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