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