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