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