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