1 #!/usr/bin/env python 2 3 """ 4 Deduce types for usage observations. 5 6 Copyright (C) 2014, 2015, 2016 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_attrname_from_location, get_attrnames, \ 23 get_invoked_attributes, get_name_path, init_item, \ 24 sorted_output, CommonOutput 25 from encoders import encode_attrnames, encode_access_location, \ 26 encode_constrained, encode_location, encode_usage, \ 27 get_kinds, test_for_kinds, test_for_type 28 from errors import DeduceError 29 from os.path import join 30 from referencing import combine_types, is_single_class_type, separate_types, \ 31 Reference 32 33 class Deducer(CommonOutput): 34 35 "Deduce types in a program." 36 37 def __init__(self, importer, output): 38 39 """ 40 Initialise an instance using the given 'importer' that will perform 41 deductions on the program information, writing the results to the given 42 'output' directory. 43 """ 44 45 self.importer = importer 46 self.output = output 47 48 # Descendants of classes. 49 50 self.descendants = {} 51 self.init_descendants() 52 self.init_special_attributes() 53 54 # Map locations to usage in order to determine specific types. 55 56 self.location_index = {} 57 58 # Map access locations to definition locations. 59 60 self.access_index = {} 61 62 # Map aliases to accesses that define them. 63 64 self.alias_index = {} 65 66 # Map constant accesses to redefined accesses. 67 68 self.const_accesses = {} 69 self.const_accesses_rev = {} 70 71 # Map usage observations to assigned attributes. 72 73 self.assigned_attrs = {} 74 75 # Map usage observations to objects. 76 77 self.attr_class_types = {} 78 self.attr_instance_types = {} 79 self.attr_module_types = {} 80 81 # Modified attributes from usage observations. 82 83 self.modified_attributes = {} 84 85 # Accesses that are assignments. 86 87 self.reference_assignments = set() 88 89 # Map locations to types, constrained indicators and attributes. 90 91 self.accessor_class_types = {} 92 self.accessor_instance_types = {} 93 self.accessor_module_types = {} 94 self.provider_class_types = {} 95 self.provider_instance_types = {} 96 self.provider_module_types = {} 97 self.accessor_constrained = set() 98 self.access_constrained = set() 99 self.referenced_attrs = {} 100 self.referenced_objects = {} 101 102 # Details of access operations. 103 104 self.access_plans = {} 105 106 # Accumulated information about accessors and providers. 107 108 self.accessor_general_class_types = {} 109 self.accessor_general_instance_types = {} 110 self.accessor_general_module_types = {} 111 self.accessor_all_types = {} 112 self.accessor_all_general_types = {} 113 self.provider_all_types = {} 114 self.accessor_guard_tests = {} 115 116 # Accumulated information about accessed attributes and 117 # access/attribute-specific accessor tests. 118 119 self.reference_all_attrs = {} 120 self.reference_all_attrtypes = {} 121 self.reference_all_accessor_types = {} 122 self.reference_all_accessor_general_types = {} 123 self.reference_test_types = {} 124 self.reference_test_accessor_type = {} 125 126 # The processing workflow itself. 127 128 self.init_usage_index() 129 self.init_accessors() 130 self.init_accesses() 131 self.init_aliases() 132 self.init_attr_type_indexes() 133 self.modify_mutated_attributes() 134 self.identify_references() 135 self.classify_accessors() 136 self.classify_accesses() 137 self.initialise_access_plans() 138 139 def to_output(self): 140 141 "Write the output files using deduction information." 142 143 self.check_output() 144 145 self.write_mutations() 146 self.write_accessors() 147 self.write_accesses() 148 self.write_access_plans() 149 150 def write_mutations(self): 151 152 """ 153 Write mutation-related output in the following format: 154 155 qualified name " " original object type 156 157 Object type can be "<class>", "<function>" or "<var>". 158 """ 159 160 f = open(join(self.output, "mutations"), "w") 161 try: 162 attrs = self.modified_attributes.items() 163 attrs.sort() 164 165 for attr, value in attrs: 166 print >>f, attr, value 167 finally: 168 f.close() 169 170 def write_accessors(self): 171 172 """ 173 Write reference-related output in the following format for types: 174 175 location " " ( "constrained" | "deduced" ) " " attribute type " " most general type names " " number of specific types 176 177 Note that multiple lines can be given for each location, one for each 178 attribute type. 179 180 Locations have the following format: 181 182 qualified name of scope "." local name ":" name version 183 184 The attribute type can be "<class>", "<instance>", "<module>" or "<>", 185 where the latter indicates an absence of suitable references. 186 187 Type names indicate the type providing the attributes, being either a 188 class or module qualified name. 189 190 ---- 191 192 A summary of accessor types is formatted as follows: 193 194 location " " ( "constrained" | "deduced" ) " " ( "specific" | "common" | "unguarded" ) " " most general type names " " number of specific types 195 196 This summary groups all attribute types (class, instance, module) into a 197 single line in order to determine the complexity of identifying an 198 accessor. 199 200 ---- 201 202 References that cannot be supported by any types are written to a 203 warnings file in the following format: 204 205 location 206 207 ---- 208 209 For each location where a guard would be asserted to guarantee the 210 nature of an object, the following format is employed: 211 212 location " " ( "specific" | "common" ) " " object kind " " object types 213 214 Object kind can be "<class>", "<instance>" or "<module>". 215 """ 216 217 f_type_summary = open(join(self.output, "type_summary"), "w") 218 f_types = open(join(self.output, "types"), "w") 219 f_warnings = open(join(self.output, "type_warnings"), "w") 220 f_guards = open(join(self.output, "guards"), "w") 221 222 try: 223 locations = self.accessor_class_types.keys() 224 locations.sort() 225 226 for location in locations: 227 constrained = location in self.accessor_constrained 228 229 # Accessor information. 230 231 class_types = self.accessor_class_types[location] 232 instance_types = self.accessor_instance_types[location] 233 module_types = self.accessor_module_types[location] 234 235 general_class_types = self.accessor_general_class_types[location] 236 general_instance_types = self.accessor_general_instance_types[location] 237 general_module_types = self.accessor_general_module_types[location] 238 239 all_types = self.accessor_all_types[location] 240 all_general_types = self.accessor_all_general_types[location] 241 242 if class_types: 243 print >>f_types, encode_location(location), encode_constrained(constrained), "<class>", \ 244 sorted_output(general_class_types), len(class_types) 245 246 if instance_types: 247 print >>f_types, encode_location(location), encode_constrained(constrained), "<instance>", \ 248 sorted_output(general_instance_types), len(instance_types) 249 250 if module_types: 251 print >>f_types, encode_location(location), encode_constrained(constrained), "<module>", \ 252 sorted_output(general_module_types), len(module_types) 253 254 if not all_types: 255 print >>f_types, encode_location(location), "deduced", "<>", 0 256 attrnames = list(self.location_index[location]) 257 attrnames.sort() 258 print >>f_warnings, encode_location(location), "; ".join(map(encode_usage, attrnames)) 259 260 guard_test = self.accessor_guard_tests.get(location) 261 262 # Write specific type guard details. 263 264 if guard_test and guard_test.startswith("specific"): 265 print >>f_guards, encode_location(location), guard_test, \ 266 get_kinds(all_types)[0], \ 267 sorted_output(all_types) 268 269 # Write common type guard details. 270 271 elif guard_test and guard_test.startswith("common"): 272 print >>f_guards, encode_location(location), guard_test, \ 273 get_kinds(all_general_types)[0], \ 274 sorted_output(all_general_types) 275 276 print >>f_type_summary, encode_location(location), encode_constrained(constrained), \ 277 guard_test or "unguarded", sorted_output(all_general_types), len(all_types) 278 279 finally: 280 f_type_summary.close() 281 f_types.close() 282 f_warnings.close() 283 f_guards.close() 284 285 def write_accesses(self): 286 287 """ 288 Specific attribute output is produced in the following format: 289 290 location " " ( "constrained" | "deduced" ) " " attribute type " " attribute references 291 292 Note that multiple lines can be given for each location and attribute 293 name, one for each attribute type. 294 295 Locations have the following format: 296 297 qualified name of scope "." local name " " attribute name ":" access number 298 299 The attribute type can be "<class>", "<instance>", "<module>" or "<>", 300 where the latter indicates an absence of suitable references. 301 302 Attribute references have the following format: 303 304 object type ":" qualified name 305 306 Object type can be "<class>", "<function>" or "<var>". 307 308 ---- 309 310 A summary of attributes is formatted as follows: 311 312 location " " attribute name " " ( "constrained" | "deduced" ) " " test " " attribute references 313 314 This summary groups all attribute types (class, instance, module) into a 315 single line in order to determine the complexity of each access. 316 317 Tests can be "validate", "specific", "untested", "guarded-validate" or "guarded-specific". 318 319 ---- 320 321 For each access where a test would be asserted to guarantee the 322 nature of an attribute, the following formats are employed: 323 324 location " " attribute name " " "validate" 325 location " " attribute name " " "specific" " " attribute type " " object type 326 327 ---- 328 329 References that cannot be supported by any types are written to a 330 warnings file in the following format: 331 332 location 333 """ 334 335 f_attr_summary = open(join(self.output, "attribute_summary"), "w") 336 f_attrs = open(join(self.output, "attributes"), "w") 337 f_tests = open(join(self.output, "tests"), "w") 338 f_warnings = open(join(self.output, "attribute_warnings"), "w") 339 340 try: 341 locations = self.referenced_attrs.keys() 342 locations.sort() 343 344 for location in locations: 345 constrained = location in self.access_constrained 346 347 # Attribute information, both name-based and anonymous. 348 349 referenced_attrs = self.referenced_attrs[location] 350 351 if referenced_attrs: 352 attrname = get_attrname_from_location(location) 353 354 all_accessed_attrs = self.reference_all_attrs[location] 355 356 for attrtype, attrs in self.get_referenced_attrs(location): 357 print >>f_attrs, encode_access_location(location), encode_constrained(constrained), attrtype, sorted_output(attrs) 358 359 test_type = self.reference_test_types.get(location) 360 361 # Write the need to test at run time. 362 363 if test_type == "validate": 364 print >>f_tests, encode_access_location(location), test_type 365 366 # Write any type checks for anonymous accesses. 367 368 elif test_type and self.reference_test_accessor_type.get(location): 369 print >>f_tests, encode_access_location(location), test_type, \ 370 sorted_output(all_accessed_attrs), \ 371 self.reference_test_accessor_type[location] 372 373 print >>f_attr_summary, encode_access_location(location), encode_constrained(constrained), \ 374 test_type or "untested", sorted_output(all_accessed_attrs) 375 376 else: 377 print >>f_warnings, encode_access_location(location) 378 379 finally: 380 f_attr_summary.close() 381 f_attrs.close() 382 f_tests.close() 383 f_warnings.close() 384 385 def write_access_plans(self): 386 387 """ 388 Each attribute access is written out as a plan of the following form: 389 390 location " " name " " test " " test type " " base " " traversed attributes 391 " " attributes to traverse " " context " " access method 392 " " static attribute 393 """ 394 395 f_attrs = open(join(self.output, "attribute_plans"), "w") 396 397 try: 398 locations = self.access_plans.keys() 399 locations.sort() 400 401 for location in locations: 402 name, test, test_type, base, traversed, traversal_modes, attrnames, \ 403 context, context_test, \ 404 first_method, final_method, attr = self.access_plans[location] 405 406 print >>f_attrs, encode_access_location(location), \ 407 name, test, test_type or "{}", \ 408 base or "{}", \ 409 ".".join(traversed) or "{}", \ 410 ".".join(traversal_modes) or "{}", \ 411 ".".join(attrnames) or "{}", \ 412 context, context_test, \ 413 first_method, final_method, attr or "{}" 414 415 finally: 416 f_attrs.close() 417 418 def classify_accessors(self): 419 420 "For each program location, classify accessors." 421 422 # Where instance and module types are defined, class types are also 423 # defined. See: init_definition_details 424 425 locations = self.accessor_class_types.keys() 426 427 for location in locations: 428 constrained = location in self.accessor_constrained 429 430 # Provider information. 431 432 class_types = self.provider_class_types[location] 433 instance_types = self.provider_instance_types[location] 434 module_types = self.provider_module_types[location] 435 436 # Collect specific and general type information. 437 438 self.provider_all_types[location] = \ 439 combine_types(class_types, instance_types, module_types) 440 441 # Accessor information. 442 443 class_types = self.accessor_class_types[location] 444 self.accessor_general_class_types[location] = \ 445 general_class_types = self.get_most_general_class_types(class_types) 446 447 instance_types = self.accessor_instance_types[location] 448 self.accessor_general_instance_types[location] = \ 449 general_instance_types = self.get_most_general_class_types(instance_types) 450 451 module_types = self.accessor_module_types[location] 452 self.accessor_general_module_types[location] = \ 453 general_module_types = self.get_most_general_module_types(module_types) 454 455 # Collect specific and general type information. 456 457 self.accessor_all_types[location] = all_types = \ 458 combine_types(class_types, instance_types, module_types) 459 460 self.accessor_all_general_types[location] = all_general_types = \ 461 combine_types(general_class_types, general_instance_types, general_module_types) 462 463 # Record guard information. 464 465 if not constrained: 466 467 # Record specific type guard details. 468 469 if len(all_types) == 1: 470 self.accessor_guard_tests[location] = test_for_type("specific", first(all_types)) 471 elif is_single_class_type(all_types): 472 self.accessor_guard_tests[location] = "specific-object" 473 474 # Record common type guard details. 475 476 elif len(all_general_types) == 1: 477 self.accessor_guard_tests[location] = test_for_type("common", first(all_types)) 478 elif is_single_class_type(all_general_types): 479 self.accessor_guard_tests[location] = "common-object" 480 481 # Otherwise, no convenient guard can be defined. 482 483 def classify_accesses(self): 484 485 "For each program location, classify accesses." 486 487 # Attribute accesses use potentially different locations to those of 488 # accessors. 489 490 locations = self.referenced_attrs.keys() 491 492 for location in locations: 493 constrained = location in self.access_constrained 494 495 # Combine type information from all accessors supplying the access. 496 497 accessor_locations = self.get_accessors_for_access(location) 498 499 all_provider_types = set() 500 all_accessor_types = set() 501 all_accessor_general_types = set() 502 503 for accessor_location in accessor_locations: 504 505 # Obtain the provider types for guard-related attribute access 506 # checks. 507 508 all_provider_types.update(self.provider_all_types.get(accessor_location)) 509 510 # Obtain the accessor guard types (specific and general). 511 512 all_accessor_types.update(self.accessor_all_types.get(accessor_location)) 513 all_accessor_general_types.update(self.accessor_all_general_types.get(accessor_location)) 514 515 # Obtain basic properties of the types involved in the access. 516 517 single_accessor_type = len(all_accessor_types) == 1 518 single_accessor_class_type = is_single_class_type(all_accessor_types) 519 single_accessor_general_type = len(all_accessor_general_types) == 1 520 single_accessor_general_class_type = is_single_class_type(all_accessor_general_types) 521 522 # Determine whether the attribute access is guarded or not. 523 524 guarded = ( 525 single_accessor_type or single_accessor_class_type or 526 single_accessor_general_type or single_accessor_general_class_type 527 ) 528 529 if guarded: 530 (guard_class_types, guard_instance_types, guard_module_types, 531 _function_types, _var_types) = separate_types(all_provider_types) 532 533 self.reference_all_accessor_types[location] = all_accessor_types 534 self.reference_all_accessor_general_types[location] = all_accessor_general_types 535 536 # Attribute information, both name-based and anonymous. 537 538 referenced_attrs = self.referenced_attrs[location] 539 540 if not referenced_attrs: 541 raise DeduceError, repr(location) 542 543 # Record attribute information for each name used on the 544 # accessor. 545 546 attrname = get_attrname_from_location(location) 547 548 all_accessed_attrs = set() 549 all_providers = set() 550 551 # Obtain provider and attribute details for this kind of 552 # object. 553 554 for attrtype, object_type, attr in referenced_attrs: 555 all_accessed_attrs.add(attr) 556 all_providers.add(object_type) 557 558 all_general_providers = self.get_most_general_types(all_providers) 559 560 # Determine which attributes would be provided by the 561 # accessor types upheld by a guard. 562 563 if guarded: 564 guard_attrs = set() 565 for _attrtype, object_type, attr in \ 566 self._identify_reference_attribute(attrname, guard_class_types, guard_instance_types, guard_module_types): 567 guard_attrs.add(attr) 568 else: 569 guard_attrs = None 570 571 self.reference_all_attrs[location] = all_accessed_attrs 572 573 # Constrained accesses guarantee the nature of the accessor. 574 # However, there may still be many types involved. 575 576 if constrained: 577 if single_accessor_type: 578 self.reference_test_types[location] = test_for_type("constrained-specific", first(all_accessor_types)) 579 elif single_accessor_class_type: 580 self.reference_test_types[location] = "constrained-specific-object" 581 elif single_accessor_general_type: 582 self.reference_test_types[location] = test_for_type("constrained-common", first(all_accessor_general_types)) 583 elif single_accessor_general_class_type: 584 self.reference_test_types[location] = "constrained-common-object" 585 else: 586 self.reference_test_types[location] = "constrained-many" 587 588 # Suitably guarded accesses, where the nature of the 589 # accessor can be guaranteed, do not require the attribute 590 # involved to be validated. Otherwise, for unguarded 591 # accesses, access-level tests are required. 592 593 elif guarded and all_accessed_attrs.issubset(guard_attrs): 594 if single_accessor_type: 595 self.reference_test_types[location] = test_for_type("guarded-specific", first(all_accessor_types)) 596 elif single_accessor_class_type: 597 self.reference_test_types[location] = "guarded-specific-object" 598 elif single_accessor_general_type: 599 self.reference_test_types[location] = test_for_type("guarded-common", first(all_accessor_general_types)) 600 elif single_accessor_general_class_type: 601 self.reference_test_types[location] = "guarded-common-object" 602 603 # Record the need to test the type of anonymous and 604 # unconstrained accessors. 605 606 elif len(all_providers) == 1: 607 provider = first(all_providers) 608 if provider != '__builtins__.object': 609 all_accessor_kinds = set(get_kinds(all_accessor_types)) 610 if len(all_accessor_kinds) == 1: 611 test_type = test_for_kinds("specific", all_accessor_kinds) 612 else: 613 test_type = "specific-object" 614 self.reference_test_types[location] = test_type 615 self.reference_test_accessor_type[location] = provider 616 617 elif len(all_general_providers) == 1: 618 provider = first(all_general_providers) 619 if provider != '__builtins__.object': 620 all_accessor_kinds = set(get_kinds(all_accessor_general_types)) 621 if len(all_accessor_kinds) == 1: 622 test_type = test_for_kinds("common", all_accessor_kinds) 623 else: 624 test_type = "common-object" 625 self.reference_test_types[location] = test_type 626 self.reference_test_accessor_type[location] = provider 627 628 # Record the need to test the identity of the attribute. 629 630 else: 631 self.reference_test_types[location] = "validate" 632 633 def initialise_access_plans(self): 634 635 "Define attribute access plans." 636 637 for location in self.referenced_attrs.keys(): 638 original_location = self.const_accesses_rev.get(location) 639 self.access_plans[original_location or location] = self.get_access_plan(location) 640 641 def get_referenced_attrs(self, location): 642 643 """ 644 Return attributes referenced at the given access 'location' by the given 645 'attrname' as a list of (attribute type, attribute set) tuples. 646 """ 647 648 d = {} 649 for attrtype, objtype, attr in self.referenced_attrs[location]: 650 init_item(d, attrtype, set) 651 d[attrtype].add(attr) 652 l = d.items() 653 l.sort() # class, module, instance 654 return l 655 656 # Initialisation methods. 657 658 def init_descendants(self): 659 660 "Identify descendants of each class." 661 662 for name in self.importer.classes.keys(): 663 self.get_descendants_for_class(name) 664 665 def get_descendants_for_class(self, name): 666 667 """ 668 Use subclass information to deduce the descendants for the class of the 669 given 'name'. 670 """ 671 672 if not self.descendants.has_key(name): 673 descendants = set() 674 675 for subclass in self.importer.subclasses[name]: 676 descendants.update(self.get_descendants_for_class(subclass)) 677 descendants.add(subclass) 678 679 self.descendants[name] = descendants 680 681 return self.descendants[name] 682 683 def init_special_attributes(self): 684 685 "Add special attributes to the classes for inheritance-related tests." 686 687 all_class_attrs = self.importer.all_class_attrs 688 689 for name, descendants in self.descendants.items(): 690 for descendant in descendants: 691 all_class_attrs[descendant]["#%s" % name] = name 692 693 for name in all_class_attrs.keys(): 694 all_class_attrs[name]["#%s" % name] = name 695 696 def init_usage_index(self): 697 698 """ 699 Create indexes for module and function attribute usage and for anonymous 700 accesses. 701 """ 702 703 for module in self.importer.get_modules(): 704 for path, assignments in module.attr_usage.items(): 705 self.add_usage(assignments, path) 706 707 for location, all_attrnames in self.importer.all_attr_accesses.items(): 708 for attrnames in all_attrnames: 709 attrname = get_attrnames(attrnames)[-1] 710 access_location = (location, None, attrnames, 0) 711 self.add_usage_term(access_location, ((attrname, False),)) 712 713 def add_usage(self, assignments, path): 714 715 """ 716 Collect usage from the given 'assignments', adding 'path' details to 717 each record if specified. Add the usage to an index mapping to location 718 information, as well as to an index mapping locations to usages. 719 """ 720 721 for name, versions in assignments.items(): 722 for i, usages in enumerate(versions): 723 location = (path, name, None, i) 724 725 for usage in usages: 726 self.add_usage_term(location, usage) 727 728 def add_usage_term(self, location, usage): 729 730 """ 731 For 'location' and using 'usage' as a description of usage, record 732 in the usage index a mapping from the usage to 'location', and record in 733 the location index a mapping from 'location' to the usage. 734 """ 735 736 init_item(self.location_index, location, set) 737 self.location_index[location].add(usage) 738 739 def init_accessors(self): 740 741 "Create indexes for module and function accessor information." 742 743 for module in self.importer.get_modules(): 744 for path, all_accesses in module.attr_accessors.items(): 745 self.add_accessors(all_accesses, path) 746 747 def add_accessors(self, all_accesses, path): 748 749 """ 750 For attribute accesses described by the mapping of 'all_accesses' from 751 name details to accessor details, record the locations of the accessors 752 for each access. 753 """ 754 755 # Get details for each access combining the given name and attribute. 756 757 for (name, attrnames), accesses in all_accesses.items(): 758 759 # Obtain the usage details using the access information. 760 761 for access_number, versions in enumerate(accesses): 762 access_location = (path, name, attrnames, access_number) 763 locations = [] 764 765 for version in versions: 766 location = (path, name, None, version) 767 locations.append(location) 768 769 self.access_index[access_location] = locations 770 771 def get_accessors_for_access(self, access_location): 772 773 "Find a definition providing accessor details, if necessary." 774 775 try: 776 return self.access_index[access_location] 777 except KeyError: 778 return [access_location] 779 780 def init_accesses(self): 781 782 """ 783 Initialise collections for accesses involving assignments. 784 """ 785 786 # For each scope, obtain access details. 787 788 for path, all_accesses in self.importer.all_attr_access_modifiers.items(): 789 790 # For each combination of name and attribute names, obtain 791 # applicable modifiers. 792 793 for (name, attrnames), modifiers in all_accesses.items(): 794 795 # For each access, determine the name versions affected by 796 # assignments. 797 798 for access_number, assignment in enumerate(modifiers): 799 if name: 800 access_location = (path, name, attrnames, access_number) 801 else: 802 access_location = (path, None, attrnames, 0) 803 804 if assignment: 805 self.reference_assignments.add(access_location) 806 807 # Associate assignments with usage. 808 809 accessor_locations = self.get_accessors_for_access(access_location) 810 811 for location in accessor_locations: 812 for usage in self.location_index[location]: 813 if assignment: 814 init_item(self.assigned_attrs, usage, set) 815 self.assigned_attrs[usage].add((path, name, attrnames)) 816 817 def init_aliases(self): 818 819 "Expand aliases so that alias-based accesses can be resolved." 820 821 # Get aliased names with details of their accesses. 822 823 for name_path, all_aliases in self.importer.all_aliased_names.items(): 824 path, name = name_path.rsplit(".", 1) 825 826 # For each version of the name, obtain the access location. 827 828 for version, (original_name, attrnames, access_number) in all_aliases.items(): 829 accessor_location = (path, name, None, version) 830 access_location = (path, original_name, attrnames, access_number) 831 init_item(self.alias_index, accessor_location, list) 832 self.alias_index[accessor_location].append(access_location) 833 834 # Get aliases in terms of non-aliases and accesses. 835 836 for accessor_location, access_locations in self.alias_index.items(): 837 self.update_aliases(accessor_location, access_locations) 838 839 def update_aliases(self, accessor_location, access_locations, visited=None): 840 841 """ 842 Update the given 'accessor_location' defining an alias, update 843 'access_locations' to refer to non-aliases, following name references 844 via the access index. 845 846 If 'visited' is specified, it contains a set of accessor locations (and 847 thus keys to the alias index) that are currently being defined. 848 """ 849 850 if visited is None: 851 visited = set() 852 853 updated_locations = set() 854 855 for access_location in access_locations: 856 (path, original_name, attrnames, access_number) = access_location 857 858 # Where an alias refers to a name access, obtain the original name 859 # version details. 860 861 if attrnames is None: 862 863 # For each name version, attempt to determine any accesses that 864 # initialise the name. 865 866 for name_accessor_location in self.access_index[access_location]: 867 868 # Already-visited aliases do not contribute details. 869 870 if name_accessor_location in visited: 871 continue 872 873 visited.add(name_accessor_location) 874 875 name_access_locations = self.alias_index.get(name_accessor_location) 876 if name_access_locations: 877 updated_locations.update(self.update_aliases(name_accessor_location, name_access_locations, visited)) 878 else: 879 updated_locations.add(name_accessor_location) 880 881 # Otherwise, record the access details. 882 883 else: 884 updated_locations.add(access_location) 885 886 self.alias_index[accessor_location] = updated_locations 887 return updated_locations 888 889 # Attribute mutation for types. 890 891 def modify_mutated_attributes(self): 892 893 "Identify known, mutated attributes and change their state." 894 895 # Usage-based accesses. 896 897 for usage, all_attrnames in self.assigned_attrs.items(): 898 if not usage: 899 continue 900 901 for path, name, attrnames in all_attrnames: 902 class_types = self.get_class_types_for_usage(usage) 903 only_instance_types = set(self.get_instance_types_for_usage(usage)).difference(class_types) 904 module_types = self.get_module_types_for_usage(usage) 905 906 # Detect self usage within methods in order to narrow the scope 907 # of the mutation. 908 909 t = name == "self" and self.constrain_self_reference(path, class_types, only_instance_types) 910 if t: 911 class_types, only_instance_types, module_types, constrained = t 912 objects = set(class_types).union(only_instance_types).union(module_types) 913 914 self.mutate_attribute(objects, attrnames) 915 916 def mutate_attribute(self, objects, attrnames): 917 918 "Mutate static 'objects' with the given 'attrnames'." 919 920 for name in objects: 921 attr = "%s.%s" % (name, attrnames) 922 value = self.importer.get_object(attr) 923 924 # If the value is None, the attribute is 925 # inherited and need not be set explicitly on 926 # the class concerned. 927 928 if value: 929 self.modified_attributes[attr] = value 930 self.importer.set_object(attr, value.as_var()) 931 932 # Simplification of types. 933 934 def get_most_general_types(self, types): 935 936 "Return the most general types for the given 'types'." 937 938 module_types = set() 939 class_types = set() 940 941 for type in types: 942 ref = self.importer.identify(type) 943 if ref.has_kind("<module>"): 944 module_types.add(type) 945 else: 946 class_types.add(type) 947 948 types = set(self.get_most_general_module_types(module_types)) 949 types.update(self.get_most_general_class_types(class_types)) 950 return types 951 952 def get_most_general_class_types(self, class_types): 953 954 "Return the most general types for the given 'class_types'." 955 956 class_types = set(class_types) 957 to_remove = set() 958 959 for class_type in class_types: 960 for base in self.importer.classes[class_type]: 961 base = base.get_origin() 962 descendants = self.descendants[base] 963 if base in class_types and descendants.issubset(class_types): 964 to_remove.update(descendants) 965 966 class_types.difference_update(to_remove) 967 return class_types 968 969 def get_most_general_module_types(self, module_types): 970 971 "Return the most general type for the given 'module_types'." 972 973 # Where all modules are provided, an object would provide the same 974 # attributes. 975 976 if len(module_types) == len(self.importer.modules): 977 return ["__builtins__.object"] 978 else: 979 return module_types 980 981 # More efficient usage-to-type indexing and retrieval. 982 983 def init_attr_type_indexes(self): 984 985 "Identify the types that can support each attribute name." 986 987 self._init_attr_type_index(self.attr_class_types, self.importer.all_class_attrs) 988 self._init_attr_type_index(self.attr_instance_types, self.importer.all_combined_attrs) 989 self._init_attr_type_index(self.attr_module_types, self.importer.all_module_attrs) 990 991 def _init_attr_type_index(self, attr_types, attrs): 992 993 """ 994 Initialise the 'attr_types' attribute-to-types mapping using the given 995 'attrs' type-to-attributes mapping. 996 """ 997 998 for name, attrnames in attrs.items(): 999 for attrname in attrnames: 1000 init_item(attr_types, attrname, set) 1001 attr_types[attrname].add(name) 1002 1003 def get_class_types_for_usage(self, usage): 1004 1005 "Return names of classes supporting the given 'usage'." 1006 1007 return self._get_types_for_usage(usage, self.attr_class_types, self.importer.all_class_attrs) 1008 1009 def get_instance_types_for_usage(self, usage): 1010 1011 """ 1012 Return names of classes whose instances support the given 'usage' 1013 (as either class or instance attributes). 1014 """ 1015 1016 return self._get_types_for_usage(usage, self.attr_instance_types, self.importer.all_combined_attrs) 1017 1018 def get_module_types_for_usage(self, usage): 1019 1020 "Return names of modules supporting the given 'usage'." 1021 1022 return self._get_types_for_usage(usage, self.attr_module_types, self.importer.all_module_attrs) 1023 1024 def _get_types_for_usage(self, usage, attr_types, attrs): 1025 1026 """ 1027 For the given 'usage' representing attribute usage, return types 1028 recorded in the 'attr_types' attribute-to-types mapping that support 1029 such usage, with the given 'attrs' type-to-attributes mapping used to 1030 quickly assess whether a type supports all of the stated attributes. 1031 """ 1032 1033 # Where no attributes are used, any type would be acceptable. 1034 1035 if not usage: 1036 return attrs.keys() 1037 1038 attrnames = [] 1039 for attrname, invocation in usage: 1040 attrnames.append(attrname) 1041 1042 types = [] 1043 1044 # Obtain types supporting the first attribute name... 1045 1046 for name in attr_types.get(attrnames[0]) or []: 1047 1048 # Record types that support all of the other attributes as well. 1049 1050 _attrnames = attrs[name] 1051 if set(attrnames).issubset(_attrnames): 1052 types.append(name) 1053 1054 return types 1055 1056 # Reference identification. 1057 1058 def identify_references(self): 1059 1060 "Identify references using usage and name reference information." 1061 1062 # Names with associated attribute usage. 1063 1064 for location, usages in self.location_index.items(): 1065 1066 # Obtain attribute usage associated with a name, deducing the nature 1067 # of the name. Obtain types only for branches involving attribute 1068 # usage. (In the absence of usage, any type could be involved, but 1069 # then no accesses exist to require knowledge of the type.) 1070 1071 have_usage = False 1072 have_no_usage_branch = False 1073 1074 for usage in usages: 1075 if not usage: 1076 have_no_usage_branch = True 1077 continue 1078 elif not have_usage: 1079 self.init_definition_details(location) 1080 have_usage = True 1081 self.record_types_for_usage(location, usage) 1082 1083 # Where some usage occurs, but where branches without usage also 1084 # occur, record the types for those branches anyway. 1085 1086 if have_usage and have_no_usage_branch: 1087 self.init_definition_details(location) 1088 self.record_types_for_usage(location, None) 1089 1090 # Specific name-based attribute accesses. 1091 1092 alias_accesses = set() 1093 1094 for access_location, accessor_locations in self.access_index.items(): 1095 self.record_types_for_access(access_location, accessor_locations, alias_accesses) 1096 1097 # Anonymous references with attribute chains. 1098 1099 for location, accesses in self.importer.all_attr_accesses.items(): 1100 1101 # Get distinct attribute names. 1102 1103 all_attrnames = set() 1104 1105 for attrnames in accesses: 1106 all_attrnames.update(get_attrnames(attrnames)) 1107 1108 # Get attribute and accessor details for each attribute name. 1109 1110 for attrname in all_attrnames: 1111 access_location = (location, None, attrname, 0) 1112 self.record_types_for_attribute(access_location, attrname) 1113 1114 # References via constant/identified objects. 1115 1116 for location, name_accesses in self.importer.all_const_accesses.items(): 1117 1118 # A mapping from the original name and attributes to resolved access 1119 # details. 1120 1121 for original_access, access in name_accesses.items(): 1122 original_name, original_attrnames = original_access 1123 objpath, ref, attrnames = access 1124 1125 # Build an accessor combining the name and attribute names used. 1126 1127 original_accessor = tuple([original_name] + original_attrnames.split(".")) 1128 1129 # Direct accesses to attributes. 1130 1131 if not attrnames: 1132 1133 # Build a descriptive location based on the original 1134 # details, exposing the final attribute name. 1135 1136 oa, attrname = original_accessor[:-1], original_accessor[-1] 1137 oa = ".".join(oa) 1138 1139 access_location = (location, oa, attrname, 0) 1140 accessor_location = (location, oa, None, 0) 1141 self.access_index[access_location] = [accessor_location] 1142 1143 self.init_access_details(access_location) 1144 self.init_definition_details(accessor_location) 1145 1146 # Obtain a reference for the accessor in order to properly 1147 # determine its type. 1148 1149 if ref.get_kind() != "<instance>": 1150 objpath = ref.get_origin() 1151 1152 objpath = objpath.rsplit(".", 1)[0] 1153 1154 # Where the object name conflicts with the module 1155 # providing it, obtain the module details. 1156 1157 if objpath in self.importer.modules: 1158 accessor = Reference("<module>", objpath) 1159 else: 1160 accessor = self.importer.get_object(objpath) 1161 1162 self.referenced_attrs[access_location] = [(accessor.get_kind(), accessor.get_origin(), ref)] 1163 self.access_constrained.add(access_location) 1164 1165 class_types, instance_types, module_types = accessor.get_types() 1166 self.record_reference_types(accessor_location, class_types, instance_types, module_types, True, True) 1167 1168 else: 1169 1170 # Build a descriptive location based on the original 1171 # details, employing the first remaining attribute name. 1172 1173 l = get_attrnames(attrnames) 1174 attrname = l[0] 1175 1176 oa = original_accessor[:-len(l)] 1177 oa = ".".join(oa) 1178 1179 access_location = (location, oa, attrnames, 0) 1180 accessor_location = (location, oa, None, 0) 1181 self.access_index[access_location] = [accessor_location] 1182 1183 self.init_access_details(access_location) 1184 self.init_definition_details(accessor_location) 1185 1186 class_types, instance_types, module_types = ref.get_types() 1187 1188 self.identify_reference_attributes(access_location, attrname, class_types, instance_types, module_types, True) 1189 self.record_reference_types(accessor_location, class_types, instance_types, module_types, True, True) 1190 1191 original_location = (location, original_name, original_attrnames, 0) 1192 1193 if original_location != access_location: 1194 self.const_accesses[original_location] = access_location 1195 self.const_accesses_rev[access_location] = original_location 1196 1197 # Aliased name definitions. All aliases with usage will have been 1198 # defined, but they may be refined according to referenced accesses. 1199 1200 for accessor_location in self.alias_index.keys(): 1201 self.record_types_for_alias(accessor_location) 1202 1203 # Update accesses employing aliases. 1204 1205 for access_location in alias_accesses: 1206 self.record_types_for_access(access_location, self.access_index[access_location]) 1207 1208 def constrain_types(self, path, class_types, instance_types, module_types): 1209 1210 """ 1211 Using the given 'path' to an object, constrain the given 'class_types', 1212 'instance_types' and 'module_types'. 1213 1214 Return the class, instance, module types plus whether the types are 1215 constrained to a specific kind of type. 1216 """ 1217 1218 ref = self.importer.identify(path) 1219 if ref: 1220 1221 # Constrain usage suggestions using the identified object. 1222 1223 if ref.has_kind("<class>"): 1224 return ( 1225 set(class_types).intersection([ref.get_origin()]), [], [], True 1226 ) 1227 elif ref.has_kind("<module>"): 1228 return ( 1229 [], [], set(module_types).intersection([ref.get_origin()]), True 1230 ) 1231 1232 return class_types, instance_types, module_types, False 1233 1234 def get_target_types(self, location, usage): 1235 1236 """ 1237 Return the class, instance and module types constrained for the name at 1238 the given 'location' exhibiting the given 'usage'. Whether the types 1239 have been constrained using contextual information is also indicated, 1240 plus whether the types have been constrained to a specific kind of type. 1241 """ 1242 1243 unit_path, name, attrnames, version = location 1244 1245 # Detect any initialised name for the location. 1246 1247 if name: 1248 ref = self.get_initialised_name(location) 1249 if ref: 1250 (class_types, only_instance_types, module_types, 1251 _function_types, _var_types) = separate_types([ref]) 1252 return class_types, only_instance_types, module_types, True, False 1253 1254 # Retrieve the recorded types for the usage. 1255 1256 class_types = self.get_class_types_for_usage(usage) 1257 only_instance_types = set(self.get_instance_types_for_usage(usage)).difference(class_types) 1258 module_types = self.get_module_types_for_usage(usage) 1259 1260 # Merge usage deductions with observations to obtain reference types 1261 # for names involved with attribute accesses. 1262 1263 if not name: 1264 return class_types, only_instance_types, module_types, False, False 1265 1266 # Obtain references to known objects. 1267 1268 path = get_name_path(unit_path, name) 1269 1270 class_types, only_instance_types, module_types, constrained_specific = \ 1271 self.constrain_types(path, class_types, only_instance_types, module_types) 1272 1273 if constrained_specific: 1274 return class_types, only_instance_types, module_types, constrained_specific, constrained_specific 1275 1276 # Constrain "self" references. 1277 1278 if name == "self": 1279 t = self.constrain_self_reference(unit_path, class_types, only_instance_types) 1280 if t: 1281 class_types, only_instance_types, module_types, constrained = t 1282 return class_types, only_instance_types, module_types, constrained, False 1283 1284 return class_types, only_instance_types, module_types, False, False 1285 1286 def constrain_self_reference(self, unit_path, class_types, only_instance_types): 1287 1288 """ 1289 Where the name "self" appears in a method, attempt to constrain the 1290 classes involved. 1291 1292 Return the class, instance, module types plus whether the types are 1293 constrained. 1294 """ 1295 1296 class_name = self.in_method(unit_path) 1297 1298 if not class_name: 1299 return None 1300 1301 classes = set([class_name]) 1302 classes.update(self.get_descendants_for_class(class_name)) 1303 1304 # Note that only instances will be expected for these references but 1305 # either classes or instances may provide the attributes. 1306 1307 return ( 1308 set(class_types).intersection(classes), 1309 set(only_instance_types).intersection(classes), 1310 [], True 1311 ) 1312 1313 def in_method(self, path): 1314 1315 "Return whether 'path' refers to a method." 1316 1317 class_name, method_name = path.rsplit(".", 1) 1318 return self.importer.classes.has_key(class_name) and class_name 1319 1320 def init_reference_details(self, location): 1321 1322 "Initialise reference-related details for 'location'." 1323 1324 self.init_definition_details(location) 1325 self.init_access_details(location) 1326 1327 def init_definition_details(self, location): 1328 1329 "Initialise name definition details for 'location'." 1330 1331 self.accessor_class_types[location] = set() 1332 self.accessor_instance_types[location] = set() 1333 self.accessor_module_types[location] = set() 1334 self.provider_class_types[location] = set() 1335 self.provider_instance_types[location] = set() 1336 self.provider_module_types[location] = set() 1337 1338 def init_access_details(self, location): 1339 1340 "Initialise access details at 'location'." 1341 1342 self.referenced_attrs[location] = {} 1343 1344 def record_types_for_access(self, access_location, accessor_locations, alias_accesses=None): 1345 1346 """ 1347 Define types for the 'access_location' associated with the given 1348 'accessor_locations'. 1349 """ 1350 1351 attrname = get_attrname_from_location(access_location) 1352 if not attrname: 1353 return 1354 1355 # Collect all suggested types for the accessors. Accesses may 1356 # require accessors from of a subset of the complete set of types. 1357 1358 class_types = set() 1359 module_types = set() 1360 instance_types = set() 1361 1362 constrained = True 1363 1364 for location in accessor_locations: 1365 1366 # Remember accesses employing aliases. 1367 1368 if alias_accesses is not None and self.alias_index.has_key(location): 1369 alias_accesses.add(access_location) 1370 1371 # Use the type information deduced for names from above. 1372 1373 if self.accessor_class_types.has_key(location): 1374 class_types.update(self.accessor_class_types[location]) 1375 module_types.update(self.accessor_module_types[location]) 1376 instance_types.update(self.accessor_instance_types[location]) 1377 1378 # Where accesses are associated with assignments but where no 1379 # attribute usage observations have caused such an association, 1380 # the attribute name is considered by itself. 1381 1382 else: 1383 self.init_definition_details(location) 1384 self.record_types_for_usage(location, [(attrname, False)]) 1385 1386 constrained = location in self.accessor_constrained and constrained 1387 1388 self.init_access_details(access_location) 1389 self.identify_reference_attributes(access_location, attrname, class_types, instance_types, module_types, constrained) 1390 1391 def record_types_for_usage(self, accessor_location, usage): 1392 1393 """ 1394 Record types for the given 'accessor_location' according to the given 1395 'usage' observations which may be None to indicate an absence of usage. 1396 """ 1397 1398 (class_types, 1399 instance_types, 1400 module_types, 1401 constrained, 1402 constrained_specific) = self.get_target_types(accessor_location, usage) 1403 1404 invocations = get_invoked_attributes(usage) 1405 1406 self.record_reference_types(accessor_location, class_types, instance_types, module_types, constrained, constrained_specific, invocations) 1407 1408 def record_types_for_attribute(self, access_location, attrname): 1409 1410 """ 1411 Record types for the 'access_location' employing only the given 1412 'attrname' for type deduction. 1413 """ 1414 1415 (class_types, 1416 only_instance_types, 1417 module_types) = self.get_types_for_attribute(attrname) 1418 1419 self.init_reference_details(access_location) 1420 1421 self.identify_reference_attributes(access_location, attrname, class_types, only_instance_types, module_types, False) 1422 self.record_reference_types(access_location, class_types, only_instance_types, module_types, False) 1423 1424 def get_types_for_attribute(self, attrname): 1425 1426 "Return class, instance-only and module types supporting 'attrname'." 1427 1428 usage = ((attrname, False),) 1429 1430 class_types = self.get_class_types_for_usage(usage) 1431 only_instance_types = set(self.get_instance_types_for_usage(usage)).difference(class_types) 1432 module_types = self.get_module_types_for_usage(usage) 1433 1434 return class_types, only_instance_types, module_types 1435 1436 def record_types_for_alias(self, accessor_location): 1437 1438 """ 1439 Define types for the 'accessor_location' not having associated usage. 1440 """ 1441 1442 have_access = self.provider_class_types.has_key(accessor_location) 1443 1444 # With an access, attempt to narrow the existing selection of provider 1445 # types. 1446 1447 if have_access: 1448 provider_class_types = self.provider_class_types[accessor_location] 1449 provider_instance_types = self.provider_instance_types[accessor_location] 1450 provider_module_types = self.provider_module_types[accessor_location] 1451 1452 # Find details for any corresponding access. 1453 1454 all_class_types = set() 1455 all_instance_types = set() 1456 all_module_types = set() 1457 1458 for access_location in self.alias_index[accessor_location]: 1459 location, name, attrnames, access_number = access_location 1460 1461 # Alias references an attribute access. 1462 1463 if attrnames: 1464 1465 # Obtain attribute references for the access. 1466 1467 attrs = [attr for _attrtype, object_type, attr in self.referenced_attrs[access_location]] 1468 1469 # Separate the different attribute types. 1470 1471 (class_types, instance_types, module_types, 1472 function_types, var_types) = separate_types(attrs) 1473 1474 # Where non-accessor types are found, do not attempt to refine 1475 # the defined accessor types. 1476 1477 if function_types or var_types: 1478 return 1479 1480 class_types = set(provider_class_types).intersection(class_types) 1481 instance_types = set(provider_instance_types).intersection(instance_types) 1482 module_types = set(provider_module_types).intersection(module_types) 1483 1484 # Alias references a name, not an access. 1485 1486 else: 1487 # Attempt to refine the types using initialised names. 1488 1489 attr = self.get_initialised_name(access_location) 1490 if attr: 1491 (class_types, instance_types, module_types, 1492 _function_types, _var_types) = separate_types([attr]) 1493 1494 # Where no further information is found, do not attempt to 1495 # refine the defined accessor types. 1496 1497 else: 1498 return 1499 1500 all_class_types.update(class_types) 1501 all_instance_types.update(instance_types) 1502 all_module_types.update(module_types) 1503 1504 # Record refined type details for the alias as an accessor. 1505 1506 self.init_definition_details(accessor_location) 1507 self.record_reference_types(accessor_location, all_class_types, all_instance_types, all_module_types, False) 1508 1509 # Without an access, attempt to identify references for the alias. 1510 1511 else: 1512 refs = set() 1513 1514 for access_location in self.alias_index[accessor_location]: 1515 1516 # Obtain any redefined constant access location. 1517 1518 if self.const_accesses.has_key(access_location): 1519 access_location = self.const_accesses[access_location] 1520 1521 location, name, attrnames, access_number = access_location 1522 1523 # Alias references an attribute access. 1524 1525 if attrnames: 1526 attrs = [attr for attrtype, object_type, attr in self.referenced_attrs[access_location]] 1527 refs.update(attrs) 1528 1529 # Alias references a name, not an access. 1530 1531 else: 1532 attr = self.get_initialised_name(access_location) 1533 attrs = attr and [attr] or [] 1534 if not attrs and self.provider_class_types.has_key(access_location): 1535 class_types = self.provider_class_types[access_location] 1536 instance_types = self.provider_instance_types[access_location] 1537 module_types = self.provider_module_types[access_location] 1538 attrs = combine_types(class_types, instance_types, module_types) 1539 if attrs: 1540 refs.update(attrs) 1541 1542 # Record reference details for the alias separately from accessors. 1543 1544 self.referenced_objects[accessor_location] = refs 1545 1546 def get_initialised_name(self, access_location): 1547 1548 """ 1549 Return references for any initialised names at 'access_location', or 1550 None if no such references exist. 1551 """ 1552 1553 location, name, attrnames, version = access_location 1554 path = get_name_path(location, name) 1555 1556 # Use initialiser information, if available. 1557 1558 refs = self.importer.all_initialised_names.get(path) 1559 if refs and refs.has_key(version): 1560 return refs[version] 1561 else: 1562 return None 1563 1564 def record_reference_types(self, location, class_types, instance_types, 1565 module_types, constrained, constrained_specific=False, invocations=None): 1566 1567 """ 1568 Associate attribute provider types with the given 'location', consisting 1569 of the given 'class_types', 'instance_types' and 'module_types'. 1570 1571 If 'constrained' is indicated, the constrained nature of the accessor is 1572 recorded for the location. 1573 1574 If 'constrained_specific' is indicated using a true value, instance types 1575 will not be added to class types to permit access via instances at the 1576 given location. This is only useful where a specific accessor is known 1577 to be a class. 1578 1579 Note that the specified types only indicate the provider types for 1580 attributes, whereas the recorded accessor types indicate the possible 1581 types of the actual objects used to access attributes. 1582 """ 1583 1584 # Update the type details for the location. 1585 1586 self.provider_class_types[location].update(class_types) 1587 self.provider_instance_types[location].update(instance_types) 1588 self.provider_module_types[location].update(module_types) 1589 1590 # Class types support classes and instances as accessors. 1591 # Instance-only and module types support only their own kinds as 1592 # accessors. 1593 1594 path, name, version, attrnames = location 1595 1596 if invocations: 1597 class_only_types = self.filter_for_invocations(class_types, invocations) 1598 else: 1599 class_only_types = class_types 1600 1601 # However, the nature of accessors can be further determined. 1602 # Any self variable may only refer to an instance. 1603 1604 if name != "self" or not self.in_method(path): 1605 self.accessor_class_types[location].update(class_only_types) 1606 1607 if not constrained_specific: 1608 self.accessor_instance_types[location].update(class_types) 1609 1610 self.accessor_instance_types[location].update(instance_types) 1611 1612 if name != "self" or not self.in_method(path): 1613 self.accessor_module_types[location].update(module_types) 1614 1615 if constrained: 1616 self.accessor_constrained.add(location) 1617 1618 def filter_for_invocations(self, class_types, attrnames): 1619 1620 """ 1621 From the given 'class_types', identify methods for the given 1622 'attrnames' that are being invoked, returning a filtered collection of 1623 class types. 1624 """ 1625 1626 to_filter = set() 1627 1628 for class_type in class_types: 1629 for attrname in attrnames: 1630 ref = self.importer.get_class_attribute(class_type, attrname) 1631 parent_class = ref and ref.parent() 1632 1633 if ref and ref.has_kind("<function>") and ( 1634 parent_class == class_type or 1635 class_type in self.descendants[parent_class]): 1636 1637 to_filter.add(class_type) 1638 break 1639 1640 return set(class_types).difference(to_filter) 1641 1642 def identify_reference_attributes(self, location, attrname, class_types, instance_types, module_types, constrained): 1643 1644 """ 1645 Identify reference attributes, associating them with the given 1646 'location', identifying the given 'attrname', employing the given 1647 'class_types', 'instance_types' and 'module_types'. 1648 1649 If 'constrained' is indicated, the constrained nature of the access is 1650 recorded for the location. 1651 """ 1652 1653 # Record the referenced objects. 1654 1655 self.referenced_attrs[location] = \ 1656 self._identify_reference_attribute(attrname, class_types, instance_types, module_types) 1657 1658 if constrained: 1659 self.access_constrained.add(location) 1660 1661 def _identify_reference_attribute(self, attrname, class_types, instance_types, module_types): 1662 1663 """ 1664 Identify the reference attribute with the given 'attrname', employing 1665 the given 'class_types', 'instance_types' and 'module_types'. 1666 """ 1667 1668 attrs = set() 1669 1670 # The class types expose class attributes either directly or via 1671 # instances. 1672 1673 for object_type in class_types: 1674 ref = self.importer.get_class_attribute(object_type, attrname) 1675 if ref: 1676 attrs.add(("<class>", object_type, ref)) 1677 1678 # Add any distinct instance attributes that would be provided 1679 # by instances also providing indirect class attribute access. 1680 1681 for ref in self.importer.get_instance_attributes(object_type, attrname): 1682 attrs.add(("<instance>", object_type, ref)) 1683 1684 # The instance-only types expose instance attributes, but although 1685 # classes are excluded as potential accessors (since they do not provide 1686 # the instance attributes), the class types may still provide some 1687 # attributes. 1688 1689 for object_type in instance_types: 1690 instance_attrs = self.importer.get_instance_attributes(object_type, attrname) 1691 1692 if instance_attrs: 1693 for ref in instance_attrs: 1694 attrs.add(("<instance>", object_type, ref)) 1695 else: 1696 ref = self.importer.get_class_attribute(object_type, attrname) 1697 if ref: 1698 attrs.add(("<class>", object_type, ref)) 1699 1700 # Module types expose module attributes for module accessors. 1701 1702 for object_type in module_types: 1703 ref = self.importer.get_module_attribute(object_type, attrname) 1704 if ref: 1705 attrs.add(("<module>", object_type, ref)) 1706 1707 return attrs 1708 1709 constrained_specific_tests = ( 1710 "constrained-specific-instance", 1711 "constrained-specific-type", 1712 "constrained-specific-object", 1713 ) 1714 1715 constrained_common_tests = ( 1716 "constrained-common-instance", 1717 "constrained-common-type", 1718 "constrained-common-object", 1719 ) 1720 1721 guarded_specific_tests = ( 1722 "guarded-specific-instance", 1723 "guarded-specific-type", 1724 "guarded-specific-object", 1725 ) 1726 1727 guarded_common_tests = ( 1728 "guarded-common-instance", 1729 "guarded-common-type", 1730 "guarded-common-object", 1731 ) 1732 1733 specific_tests = ( 1734 "specific-instance", 1735 "specific-type", 1736 "specific-object", 1737 ) 1738 1739 common_tests = ( 1740 "common-instance", 1741 "common-type", 1742 "common-object", 1743 ) 1744 1745 class_tests = ( 1746 "guarded-specific-type", 1747 "guarded-common-type", 1748 "specific-type", 1749 "common-type", 1750 ) 1751 1752 class_or_instance_tests = ( 1753 "guarded-specific-object", 1754 "guarded-common-object", 1755 "specific-object", 1756 "common-object", 1757 ) 1758 1759 def get_access_plan(self, location): 1760 1761 """ 1762 Return details of the access at the given 'location'. The details are as 1763 follows: 1764 1765 * the initial accessor (from which accesses will be performed if no 1766 computed static accessor is found) 1767 * details of any test required on the initial accessor 1768 * details of any type employed by the test 1769 * any static accessor (from which accesses will be performed in 1770 preference to the initial accessor) 1771 * attributes needing to be traversed from the base that yield 1772 unambiguous objects 1773 * access modes for each of the unambiguously-traversed attributes 1774 * remaining attributes needing to be tested and traversed 1775 * details of the context 1776 * any test to apply to the context 1777 * the method of obtaining the final attribute 1778 * any static final attribute 1779 """ 1780 1781 const_access = self.const_accesses_rev.has_key(location) 1782 1783 path, name, attrnames, version = location 1784 remaining = attrnames.split(".") 1785 attrname = remaining[0] 1786 1787 # Obtain reference and accessor information, retaining also distinct 1788 # provider kind details. 1789 1790 attrs = [] 1791 objtypes = [] 1792 provider_kinds = set() 1793 1794 for attrtype, objtype, attr in self.referenced_attrs[location]: 1795 attrs.append(attr) 1796 objtypes.append(objtype) 1797 provider_kinds.add(attrtype) 1798 1799 # Obtain accessor type and kind information. 1800 1801 accessor_types = self.reference_all_accessor_types[location] 1802 accessor_general_types = self.reference_all_accessor_general_types[location] 1803 accessor_kinds = get_kinds(accessor_general_types) 1804 1805 # Determine any guard or test requirements. 1806 1807 constrained = location in self.access_constrained 1808 test = self.reference_test_types[location] 1809 test_type = self.reference_test_accessor_type.get(location) 1810 1811 # Determine the accessor and provider properties. 1812 1813 class_accessor = "<class>" in accessor_kinds 1814 module_accessor = "<module>" in accessor_kinds 1815 instance_accessor = "<instance>" in accessor_kinds 1816 provided_by_class = "<class>" in provider_kinds 1817 provided_by_instance = "<instance>" in provider_kinds 1818 1819 # Determine how attributes may be accessed relative to the accessor. 1820 1821 object_relative = class_accessor or module_accessor or provided_by_instance 1822 class_relative = instance_accessor and provided_by_class 1823 1824 # Identify the last static attribute for context acquisition. 1825 1826 base = None 1827 dynamic_base = None 1828 1829 # Constant accesses have static accessors. 1830 1831 if const_access: 1832 base = len(objtypes) == 1 and first(objtypes) 1833 1834 # Constant accessors are static. 1835 1836 else: 1837 ref = self.importer.identify("%s.%s" % (path, name)) 1838 if ref: 1839 base = ref.get_origin() 1840 1841 # Usage of previously-generated guard and test details. 1842 1843 elif test in self.constrained_specific_tests: 1844 ref = first(accessor_types) 1845 1846 elif test in self.constrained_common_tests: 1847 ref = first(accessor_general_types) 1848 1849 elif test in self.guarded_specific_tests: 1850 ref = first(accessor_types) 1851 1852 elif test in self.guarded_common_tests: 1853 ref = first(accessor_general_types) 1854 1855 # For attribute-based tests, tentatively identify a dynamic base. 1856 # Such tests allow single or multiple kinds of a type. 1857 1858 elif test in self.common_tests or test in self.specific_tests: 1859 dynamic_base = test_type 1860 1861 # Static accessors. 1862 1863 if not base and test in self.class_tests: 1864 base = ref and ref.get_origin() or dynamic_base 1865 1866 # Accessors that are not static but whose nature is determined. 1867 1868 elif not base and ref: 1869 dynamic_base = ref.get_origin() 1870 1871 # Determine initial accessor details. 1872 1873 accessor = base or dynamic_base 1874 accessor_kind = len(accessor_kinds) == 1 and first(accessor_kinds) or None 1875 provider_kind = len(provider_kinds) == 1 and first(provider_kinds) or None 1876 1877 # Traverse remaining attributes. 1878 1879 traversed = [] 1880 traversal_modes = [] 1881 1882 while len(attrs) == 1: 1883 attr = first(attrs) 1884 1885 traversed.append(attrname) 1886 traversal_modes.append(accessor_kind == provider_kind and "object" or "class") 1887 1888 # Consume attribute names providing unambiguous attributes. 1889 1890 del remaining[0] 1891 1892 if not remaining: 1893 break 1894 1895 # Update the last static attribute. 1896 1897 if attr.static(): 1898 base = attr.get_origin() 1899 traversed = [] 1900 traversal_modes = [] 1901 1902 # Get the access details. 1903 1904 attrname = remaining[0] 1905 accessor = attr.get_origin() 1906 accessor_kind = attr.get_kind() 1907 provider_kind = self.importer.get_attribute_provider(attr, attrname) 1908 accessor_kinds = [accessor_kind] 1909 provider_kinds = [provider_kind] 1910 1911 # Get the next attribute. 1912 1913 attrs = self.importer.get_attributes(attr, attrname) 1914 1915 # Where many attributes are suggested, no single attribute identity can 1916 # be loaded. 1917 1918 else: 1919 attr = None 1920 1921 # Determine the method of access. 1922 1923 is_assignment = location in self.reference_assignments 1924 1925 # Identified attribute that must be accessed via its parent. 1926 1927 if attr and attr.get_name() and is_assignment: 1928 final_method = "static-assign"; origin = attr.get_name() 1929 1930 # Static, identified attribute. 1931 1932 elif attr and attr.static(): 1933 final_method = is_assignment and "static-assign" or "static" 1934 origin = attr.final() 1935 1936 # All other methods of access involve traversal. 1937 1938 else: 1939 final_method = is_assignment and "assign" or "access" 1940 origin = None 1941 1942 # First attribute accessed at a known position via the accessor. 1943 1944 if base or dynamic_base: 1945 first_method = "relative" + (object_relative and "-object" or "") + \ 1946 (class_relative and "-class" or "") 1947 1948 # The fallback case is always run-time testing and access. 1949 1950 else: 1951 first_method = "check" + (object_relative and "-object" or "") + \ 1952 (class_relative and "-class" or "") 1953 1954 # Determine whether an unbound method is being accessed via an instance, 1955 # requiring a context test. 1956 1957 context_test = "ignore" 1958 1959 # Assignments do not employ the context. 1960 1961 if is_assignment: 1962 pass 1963 1964 # Obtain a selection of possible attributes if no unambiguous attribute 1965 # was identified. 1966 1967 elif not attr: 1968 1969 # Use previously-deduced attributes for a simple ambiguous access. 1970 # Otherwise, use the final attribute name to obtain possible 1971 # attributes. 1972 1973 if len(remaining) > 1: 1974 attrname = remaining[-1] 1975 1976 (class_types, 1977 only_instance_types, 1978 module_types) = self.get_types_for_attribute(attrname) 1979 1980 all_accessor_kinds = set() 1981 all_provider_kinds = set() 1982 1983 if class_types: 1984 all_accessor_kinds.add("<class>") 1985 all_accessor_kinds.add("<instance>") 1986 all_provider_kinds.add("<class>") 1987 if only_instance_types: 1988 all_accessor_kinds.add("<instance>") 1989 all_provider_kinds.add("<instance>") 1990 if module_types: 1991 all_accessor_kinds.add("<module>") 1992 all_provider_kinds.add("<module>") 1993 1994 attrs = set() 1995 for type in combine_types(class_types, only_instance_types, module_types): 1996 attrs.update(self.importer.get_attributes(type, attrname)) 1997 1998 always_unbound = True 1999 have_function = False 2000 have_var = False 2001 2002 # Determine whether all attributes are unbound methods and whether 2003 # functions or unidentified attributes occur. 2004 2005 for attr in attrs: 2006 always_unbound = always_unbound and attr.has_kind("<function>") and attr.name_parent() == attr.parent() 2007 have_function = have_function or attr.has_kind("<function>") 2008 have_var = have_var or attr.has_kind("<var>") 2009 2010 # Test for class-via-instance accesses. 2011 2012 if accessor_kind == "<instance>" and \ 2013 provider_kind == "<class>": 2014 2015 if always_unbound: 2016 context_test = "replace" 2017 else: 2018 context_test = "test" 2019 2020 # Test for the presence of class-via-instance accesses. 2021 2022 elif "<instance>" in accessor_kinds and \ 2023 "<class>" in provider_kinds and \ 2024 (have_function or have_var): 2025 2026 context_test = "test" 2027 2028 # With an unambiguous attribute, determine whether a test is needed. 2029 2030 elif accessor_kind == "<instance>" and \ 2031 provider_kind == "<class>" and \ 2032 (attr.has_kind("<var>") or 2033 attr.has_kind("<function>") and 2034 attr.name_parent() == attr.parent()): 2035 2036 if attr.has_kind("<var>"): 2037 context_test = "test" 2038 else: 2039 context_test = "replace" 2040 2041 # With an unambiguous attribute with ambiguity in the access method, 2042 # generate a test. 2043 2044 elif "<instance>" in accessor_kinds and \ 2045 "<class>" in provider_kinds and \ 2046 (attr.has_kind("<var>") or 2047 attr.has_kind("<function>") and 2048 attr.name_parent() == attr.parent()): 2049 2050 context_test = "test" 2051 2052 # Determine the nature of the context. 2053 2054 context = context_test == "ignore" and "unset" or \ 2055 len(traversed + remaining) == 1 and \ 2056 (base and "base" or "original-accessor") or \ 2057 "final-accessor" 2058 2059 return name, test, test_type, base, traversed, traversal_modes, remaining, context, context_test, first_method, final_method, origin 2060 2061 # vim: tabstop=4 expandtab shiftwidth=4