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