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