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