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