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