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