1 #!/usr/bin/env python 2 3 """ 4 Optimise object layouts and generate access instruction plans. 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 add_counter_item, get_attrname_from_location, init_item, \ 23 sorted_output, CommonOutput 24 from encoders import digest, encode_access_location, encode_instruction, get_kinds 25 from errors import OptimiseError 26 from os.path import exists, join 27 from os import makedirs 28 from referencing import decode_reference, Reference 29 30 class Optimiser(CommonOutput): 31 32 "Optimise objects in a program." 33 34 def __init__(self, importer, deducer, output, 35 attrnames_filename=None, locations_filename=None, 36 paramnames_filename=None, parameter_locations_filename=None): 37 38 """ 39 Initialise an instance using the given 'importer' and 'deducer' that 40 will perform the arrangement of attributes for program objects, writing 41 the results to the given 'output' directory. 42 43 If 'attrnames_filename', 'locations_filename', 'paramnames_filename', or 44 'parameter_locations_filename' are given, they will be used to 45 explicitly indicate existing attribute code, attribute position, 46 parameter code, and parameter position information respectively. 47 """ 48 49 self.importer = importer 50 self.deducer = deducer 51 self.output = output 52 53 # Explicitly-specified attribute and parameter sources. 54 55 self.attrnames_filename = attrnames_filename 56 self.locations_filename = locations_filename 57 self.paramnames_filename = paramnames_filename 58 self.parameter_locations_filename = parameter_locations_filename 59 60 # Detection of differences between any existing structure or signature 61 # information and the generated information. 62 63 self.differing_structures = [] 64 self.differing_parameters = [] 65 66 # Locations/offsets of attributes in objects. 67 68 self.locations = None 69 self.existing_locations = None 70 71 self.attr_locations = None 72 73 # Attribute code assignments. 74 75 self.all_attrnames = None 76 self.existing_attrnames = None 77 self.indicated_attrnames = None 78 79 # Locations of parameters in parameter tables. 80 81 self.arg_locations = None 82 self.existing_arg_locations = None 83 84 self.param_locations = None 85 86 # Parameter code assignments. 87 88 self.all_paramnames = None 89 self.existing_paramnames = None 90 self.indicated_paramnames = None 91 92 # Specific attribute access information. 93 94 self.access_instructions = {} 95 self.accessor_kinds = {} 96 97 # Object structure information. 98 99 self.structures = {} 100 self.existing_structures = None 101 self.attr_table = {} 102 103 # Parameter list information. 104 105 self.parameters = {} 106 self.existing_parameters = None 107 self.param_table = {} 108 109 # Constant literal information. 110 111 self.constants = [] 112 self.constant_numbers = {} 113 self.digests = {} 114 115 # Optimiser activities. 116 117 self.from_output() 118 119 # Define or redefine structure information. 120 121 self.populate_objects() 122 self.position_attributes() 123 self.populate_parameters() 124 self.position_parameters() 125 self.populate_tables() 126 self.populate_constants() 127 self.initialise_access_instructions() 128 129 def need_reset(self): 130 131 """ 132 Return whether attribute or parameter information has changed, requiring 133 the reset/recompilation of all source files. 134 """ 135 136 return self.differing_structures or self.differing_parameters 137 138 def from_output(self): 139 140 "Read input files that influence optimisation." 141 142 # Remove any output for a different program. 143 144 self.check_output() 145 146 # Existing attribute and parameter positioning information. This 147 # influences the positions of attributes and parameters found in the 148 # program. 149 150 locations_filename = self.locations_filename or \ 151 join(self.output, "locations") 152 153 parameter_locations_filename = self.parameter_locations_filename or \ 154 join(self.output, "parameter_locations") 155 156 self.existing_locations = self.read_data(locations_filename, self._line_to_list, list) 157 self.existing_arg_locations = self.read_data(parameter_locations_filename, self._line_to_list, list) 158 159 # Existing attribute and parameter code information. This is used to 160 # check the compatibility of the output against any assignments 161 # previously made. 162 163 identity = lambda x: x 164 none = lambda x: None 165 166 attrnames_filename = join(self.output, "attrnames") 167 paramnames_filename = join(self.output, "paramnames") 168 169 self.existing_attrnames = self.read_data(attrnames_filename, identity, none) 170 self.existing_paramnames = self.read_data(paramnames_filename, identity, none) 171 172 # Explicitly-specified attribute name and parameter name codes. These 173 # direct assignment of codes in the program. 174 175 self.indicated_attrnames = self.attrnames_filename and \ 176 self.read_data(self.attrnames_filename, identity, none) 177 178 self.indicated_paramnames = self.paramnames_filename and \ 179 self.read_data(self.paramnames_filename, identity, none) 180 181 # Existing structure and signature information. This is used to check 182 # the output and detect whether structures or signatures have changed. 183 184 structures_filename = join(self.output, "structures") 185 parameters_filename = join(self.output, "parameters") 186 187 self.existing_structures = dict(self.read_data(structures_filename, self._line_to_structure_pairs, list)) 188 self.existing_parameters = dict(self.read_data(parameters_filename, self._line_to_signature_pairs, list)) 189 190 def _line_to_list(self, line): 191 192 "Convert comma-separated values in 'line' to a list of values." 193 194 return line.split(", ") 195 196 def _line_to_signature_pairs(self, line): 197 198 "Convert comma-separated values in 'line' to a list of pairs of values." 199 200 l = [] 201 objpath, line = line.split(" ", 1) 202 for values in line.split(", "): 203 if values != "-": 204 name, pos = values.split(":") 205 l.append((name, int(pos))) 206 else: 207 l.append(None) 208 return (objpath, l) 209 210 def _line_to_structure_pairs(self, line): 211 212 "Convert comma-separated values in 'line' to a list of pairs of values." 213 214 l = [] 215 ref, line = line.split(" ", 1) 216 values = map(lambda x: x != '-' and x or None, line.split(", ")) 217 return (decode_reference(ref), values) 218 219 def read_data(self, filename, decode, empty): 220 221 """ 222 Read location details from 'filename', using 'decode' to convert each 223 line and 'empty' to produce an empty result where no data is given on a 224 line, returning a collection. 225 """ 226 227 collection = [] 228 229 if exists(filename): 230 f = open(filename) 231 try: 232 for line in f.readlines(): 233 line = line.rstrip() 234 if line: 235 attrnames = decode(line) 236 else: 237 attrnames = empty() 238 239 collection.append(attrnames) 240 finally: 241 f.close() 242 243 return collection 244 245 def to_output(self): 246 247 "Write the output files using optimisation information." 248 249 if not exists(self.output): 250 makedirs(self.output) 251 252 self.write_objects() 253 254 def write_objects(self): 255 256 """ 257 Write object-related output. 258 259 The locations are a list of positions indicating the attributes residing 260 at each position in the different structures in a program. 261 262 ---- 263 264 The parameter locations are a list of positions indicating the parameters 265 residing at each position in the different parameter lists in a program. 266 267 ---- 268 269 Each attribute plan provides attribute details in the following format: 270 271 location " " name " " test " " test type " " base 272 " " traversed attributes " " traversed attribute ambiguity 273 " " traversal access modes 274 " " attributes to traverse " " attribute ambiguity 275 " " context " " access method " " static attribute 276 277 Locations have the following format: 278 279 qualified name of scope "." local name ":" name version 280 281 Traversal access modes are either "class" (obtain accessor class to 282 access attribute) or "object" (obtain attribute directly from accessor). 283 284 ---- 285 286 The structures are presented as a table in the following format: 287 288 qualified name " " attribute names 289 290 The attribute names are separated by ", " characters and indicate the 291 attribute provided at each position in the structure associated with the 292 given type. Where no attribute is provided at a particular location 293 within a structure, "-" is given. 294 295 ---- 296 297 The parameters are presented as a table in the following format: 298 299 qualified name " " parameter details 300 301 The parameter details are separated by ", " characters and indicate 302 the parameter name and list position for each parameter described at 303 each location in the parameter table associated with the given 304 function. Where no parameter details are provided at a particular 305 location within a parameter table, "-" is given. The name and list 306 position are separated by a colon (":"). 307 308 ---- 309 310 The attribute table is presented as a table in the following format: 311 312 qualified name " " attribute identifiers 313 314 Instead of attribute names, identifiers defined according to the order 315 given in the "attrnames" file are employed to denote the attributes 316 featured in each type's structure. Where no attribute is provided at a 317 particular location within a structure, "-" is given. 318 319 ---- 320 321 The parameter table is presented as a table in the following format: 322 323 qualified name " " parameter details 324 325 Instead of parameter names, identifiers defined according to the order 326 given in the "paramnames" file are employed to denote the parameters 327 featured in each function's parameter table. Where no parameter is 328 provided at a particular location within a table, "-" is given. 329 330 ---- 331 332 The ordered list of attribute names is given in the "attrnames" file. 333 334 ---- 335 336 The ordered list of parameter names is given in the "paramnames" file. 337 338 ---- 339 340 The ordered list of constant literals is given in the "constants" file. 341 """ 342 343 f = open(join(self.output, "locations"), "w") 344 try: 345 for attrnames in self.locations: 346 print >>f, sorted_output(attrnames) 347 348 finally: 349 f.close() 350 351 f = open(join(self.output, "parameter_locations"), "w") 352 try: 353 for argnames in self.arg_locations: 354 print >>f, sorted_output(argnames) 355 356 finally: 357 f.close() 358 359 f = open(join(self.output, "instruction_plans"), "w") 360 try: 361 access_instructions = self.access_instructions.items() 362 access_instructions.sort() 363 364 for location, instructions in access_instructions: 365 print >>f, encode_access_location(location), "..." 366 for instruction in instructions: 367 print >>f, encode_instruction(instruction) 368 print >>f 369 370 finally: 371 f.close() 372 373 f = open(join(self.output, "structures"), "w") 374 try: 375 structures = self.structures.items() 376 structures.sort() 377 378 for name, attrnames in structures: 379 print >>f, name, ", ".join([s or "-" for s in attrnames]) 380 381 finally: 382 f.close() 383 384 f = open(join(self.output, "parameters"), "w") 385 try: 386 parameters = self.parameters.items() 387 parameters.sort() 388 389 for name, argnames in parameters: 390 l = [] 391 for s in argnames: 392 l.append(s and ("%s:%d" % s) or "-") 393 print >>f, name, ", ".join(l) 394 395 finally: 396 f.close() 397 398 f = open(join(self.output, "attrtable"), "w") 399 try: 400 attr_table = self.attr_table.items() 401 attr_table.sort() 402 403 for name, attrcodes in attr_table: 404 l = [] 405 for i in attrcodes: 406 l.append(i is not None and str(i) or "-") 407 print >>f, name, ", ".join(l) 408 409 finally: 410 f.close() 411 412 f = open(join(self.output, "paramtable"), "w") 413 try: 414 param_table = self.param_table.items() 415 param_table.sort() 416 417 for name, paramcodes in param_table: 418 l = [] 419 for s in paramcodes: 420 l.append(s and ("%d:%d" % s) or "-") 421 print >>f, name, ", ".join(l) 422 423 finally: 424 f.close() 425 426 f = open(join(self.output, "attrnames"), "w") 427 try: 428 for name in self.all_attrnames: 429 print >>f, name 430 431 finally: 432 f.close() 433 434 f = open(join(self.output, "paramnames"), "w") 435 try: 436 for name in self.all_paramnames: 437 print >>f, name 438 439 finally: 440 f.close() 441 442 f = open(join(self.output, "constants"), "w") 443 try: 444 constants = [] 445 for (value, value_type, encoding), n in self.constants.items(): 446 constants.append((n, value_type, encoding, value)) 447 constants.sort() 448 for n, value_type, encoding, value in constants: 449 print >>f, value_type, encoding or "{}", repr(value) 450 451 finally: 452 f.close() 453 454 def populate_objects(self): 455 456 "Populate objects using attribute and usage information." 457 458 self.all_attrs = {} 459 460 # Partition attributes into separate sections so that class and instance 461 # attributes are treated separately. 462 463 for source, objkind in [ 464 (self.importer.all_class_attrs, "<class>"), 465 (self.importer.all_instance_attrs, "<instance>"), 466 (self.importer.all_module_attrs, "<module>") 467 ]: 468 469 for name, attrnames in source.items(): 470 471 # Remove temporary names from structures. 472 473 attrnames = filter(lambda x: not x.startswith("$t"), attrnames) 474 self.all_attrs[(objkind, name)] = attrnames 475 476 self.locations = get_allocated_locations(self.all_attrs, 477 get_attributes_and_sizes, self.existing_locations) 478 479 def populate_parameters(self): 480 481 "Populate parameter tables using parameter information." 482 483 # Allocate positions from 1 onwards, ignoring the context argument. 484 485 self.arg_locations = [set()] + get_allocated_locations( 486 self.importer.function_parameters, get_parameters_and_sizes, 487 self.existing_arg_locations[1:]) 488 489 def position_attributes(self): 490 491 "Position specific attribute references." 492 493 # Reverse the location mappings, producing a mapping from attribute 494 # names to positions. 495 496 attr_locations = self.attr_locations = {} 497 self._position_attributes(attr_locations, self.locations) 498 499 # Add any previously-known attribute locations. This prevents attributes 500 # from being assigned different identifying codes by preserving obsolete 501 # attribute codes. 502 503 if self.existing_locations: 504 self._position_attributes(attr_locations, self.existing_locations) 505 506 # Record the structures. 507 508 for (objkind, name), attrnames in self.all_attrs.items(): 509 key = Reference(objkind, name) 510 l = self.structures[key] = [None] * len(attrnames) 511 512 for attrname in attrnames: 513 position = attr_locations[attrname] 514 if position >= len(l): 515 l.extend([None] * (position - len(l) + 1)) 516 l[position] = attrname 517 518 # Test the structure against any existing attributes. 519 520 if self.existing_structures: 521 if self.existing_structures.has_key(key) and self.existing_structures[key] != l: 522 self.differing_structures.append(key) 523 524 def _position_attributes(self, d, l): 525 526 """ 527 For each attribute, store a mapping in 'd' to the index in 'l' at which 528 it can be found. 529 """ 530 531 for i, attrnames in enumerate(l): 532 for attrname in attrnames: 533 if not d.has_key(attrname): 534 d[attrname] = i 535 536 def initialise_access_instructions(self): 537 538 "Expand access plans into instruction sequences." 539 540 for access_location, access_plan in self.deducer.access_plans.items(): 541 542 # Obtain the access details. 543 544 name, test, test_type, base, \ 545 traversed, traversal_modes, attrnames, \ 546 context, context_test, \ 547 first_method, final_method, \ 548 origin, accessor_kinds = access_plan 549 550 # Emit instructions by appending them to a list. 551 552 instructions = [] 553 emit = instructions.append 554 555 # Identify any static original accessor. 556 557 if base: 558 original_accessor = base 559 560 # Employ names as contexts unless the context needs testing and 561 # potentially updating. In such cases, temporary context storage is 562 # used instead. 563 564 elif name and not (context_test == "test" and 565 final_method in ("access-invoke", "static-invoke")): 566 original_accessor = "<name>" # refers to the name 567 568 # Use a generic placeholder representing the access expression in 569 # the general case. 570 571 else: 572 original_accessor = "<expr>" 573 574 # Prepare for any first attribute access. 575 576 if traversed: 577 attrname = traversed[0] 578 del traversed[0] 579 elif attrnames: 580 attrname = attrnames[0] 581 del attrnames[0] 582 583 # Perform the first access explicitly if at least one operation 584 # requires it. 585 586 access_first_attribute = final_method in ("access", "access-invoke", "assign") or traversed or attrnames 587 588 # Determine whether the first access involves assignment. 589 590 assigning = not traversed and not attrnames and final_method == "assign" 591 set_accessor = assigning and "<set_target_accessor>" or "<set_accessor>" 592 stored_accessor = assigning and "<target_accessor>" or "<accessor>" 593 594 # Set the context if already available. 595 596 context_var = None 597 598 if context == "base": 599 accessor = context_var = (base,) 600 elif context == "original-accessor": 601 602 # Prevent re-evaluation of any dynamic expression by storing it. 603 604 if original_accessor == "<expr>": 605 if final_method in ("access-invoke", "static-invoke"): 606 emit(("<set_context>", original_accessor)) 607 accessor = context_var = ("<context>",) 608 else: 609 emit((set_accessor, original_accessor)) 610 accessor = context_var = (stored_accessor,) 611 else: 612 accessor = context_var = (original_accessor,) 613 614 # Assigning does not set the context. 615 616 elif context in ("final-accessor", "unset") and access_first_attribute: 617 618 # Prevent re-evaluation of any dynamic expression by storing it. 619 620 if original_accessor == "<expr>": 621 emit((set_accessor, original_accessor)) 622 accessor = (stored_accessor,) 623 else: 624 accessor = (original_accessor,) 625 626 # Apply any test. 627 628 if test[0] == "test": 629 accessor = ("__%s_%s_%s" % test, accessor, test_type) 630 631 # Perform the first or final access. 632 # The access only needs performing if the resulting accessor is used. 633 634 remaining = len(traversed + attrnames) 635 636 if access_first_attribute: 637 638 if first_method == "relative-class": 639 if assigning: 640 emit(("__store_via_class", accessor, attrname, "<assexpr>")) 641 else: 642 accessor = ("__load_via_class", accessor, attrname) 643 644 elif first_method == "relative-object": 645 if assigning: 646 emit(("__store_via_object", accessor, attrname, "<assexpr>")) 647 else: 648 accessor = ("__load_via_object", accessor, attrname) 649 650 elif first_method == "relative-object-class": 651 if assigning: 652 emit(("__get_class_and_store", accessor, attrname, "<assexpr>")) 653 else: 654 accessor = ("__get_class_and_load", accessor, attrname) 655 656 elif first_method == "check-class": 657 if assigning: 658 emit(("__check_and_store_via_class", accessor, attrname, "<assexpr>")) 659 else: 660 accessor = ("__check_and_load_via_class", accessor, attrname) 661 662 elif first_method == "check-object": 663 if assigning: 664 emit(("__check_and_store_via_object", accessor, attrname, "<assexpr>")) 665 else: 666 accessor = ("__check_and_load_via_object", accessor, attrname) 667 668 elif first_method == "check-object-class": 669 if assigning: 670 emit(("__check_and_store_via_any", accessor, attrname, "<assexpr>")) 671 else: 672 accessor = ("__check_and_load_via_any", accessor, attrname) 673 674 # Traverse attributes using the accessor. 675 676 if traversed: 677 for attrname, traversal_mode in zip(traversed, traversal_modes): 678 assigning = remaining == 1 and final_method == "assign" 679 680 # Set the context, if appropriate. 681 682 if remaining == 1 and final_method != "assign" and context == "final-accessor": 683 684 # Invoked attributes employ a separate context accessed 685 # during invocation. 686 687 if final_method in ("access-invoke", "static-invoke"): 688 emit(("<set_context>", accessor)) 689 accessor = context_var = "<context>" 690 691 # A private context within the access is otherwise 692 # retained. 693 694 else: 695 emit(("<set_private_context>", accessor)) 696 accessor = context_var = "<private_context>" 697 698 # Perform the access only if not achieved directly. 699 700 if remaining > 1 or final_method in ("access", "access-invoke", "assign"): 701 702 if traversal_mode == "class": 703 if assigning: 704 emit(("__store_via_class", accessor, attrname, "<assexpr>")) 705 else: 706 accessor = ("__load_via_class", accessor, attrname) 707 else: 708 if assigning: 709 emit(("__store_via_object", accessor, attrname, "<assexpr>")) 710 else: 711 accessor = ("__load_via_object", accessor, attrname) 712 713 remaining -= 1 714 715 if attrnames: 716 for attrname in attrnames: 717 assigning = remaining == 1 and final_method == "assign" 718 719 # Set the context, if appropriate. 720 721 if remaining == 1 and final_method != "assign" and context == "final-accessor": 722 723 # Invoked attributes employ a separate context accessed 724 # during invocation. 725 726 if final_method in ("access-invoke", "static-invoke"): 727 emit(("<set_context>", accessor)) 728 accessor = context_var = "<context>" 729 730 # A private context within the access is otherwise 731 # retained. 732 733 else: 734 emit(("<set_private_context>", accessor)) 735 accessor = context_var = "<private_context>" 736 737 # Perform the access only if not achieved directly. 738 739 if remaining > 1 or final_method in ("access", "access-invoke", "assign"): 740 741 if assigning: 742 emit(("__check_and_store_via_any", accessor, attrname, "<assexpr>")) 743 else: 744 accessor = ("__check_and_load_via_any", accessor, attrname) 745 746 remaining -= 1 747 748 # Define or emit the means of accessing the actual target. 749 750 # Assignments to known attributes. 751 752 if final_method == "static-assign": 753 parent, attrname = origin.rsplit(".", 1) 754 emit(("__store_via_object", parent, attrname, "<assexpr>")) 755 756 # Invoked attributes employ a separate context. 757 758 elif final_method in ("static", "static-invoke"): 759 accessor = ("__load_static_ignore", origin) 760 761 # Wrap accesses in context operations. 762 763 if context_test == "test": 764 765 # Test and combine the context with static attribute details. 766 767 if final_method == "static": 768 emit(("__load_static_test", context_var, origin)) 769 770 # Test the context, storing it separately if required for the 771 # immediately invoked static attribute. 772 773 elif final_method == "static-invoke": 774 emit(("<test_context_static>", context_var, origin)) 775 776 # Test the context, storing it separately if required for an 777 # immediately invoked attribute. 778 779 elif final_method == "access-invoke": 780 emit(("<test_context_revert>", context_var, accessor)) 781 782 # Test the context and update the attribute details if 783 # appropriate. 784 785 else: 786 emit(("__test_context", context_var, accessor)) 787 788 elif context_test == "replace": 789 790 # Produce an object with updated context. 791 792 if final_method == "static": 793 emit(("__load_static_replace", context_var, origin)) 794 795 # Omit the context update operation where the target is static 796 # and the context is recorded separately. 797 798 elif final_method == "static-invoke": 799 pass 800 801 # If a separate context is used for an immediate invocation, 802 # produce the attribute details unchanged. 803 804 elif final_method == "access-invoke": 805 emit(accessor) 806 807 # Update the context in the attribute details. 808 809 else: 810 emit(("__update_context", context_var, accessor)) 811 812 # Omit the accessor for assignments and for invocations of static 813 # targets. 814 815 elif final_method not in ("assign", "static-assign", "static-invoke"): 816 emit(accessor) 817 818 # Produce an advisory instruction regarding the context. 819 820 if context_var: 821 emit(("<context_identity>", context_var)) 822 823 self.access_instructions[access_location] = instructions 824 self.accessor_kinds[access_location] = accessor_kinds 825 826 def get_ambiguity_for_attributes(self, attrnames): 827 828 """ 829 Return a list of attribute position alternatives corresponding to each 830 of the given 'attrnames'. 831 """ 832 833 ambiguity = [] 834 835 for attrname in attrnames: 836 position = self.attr_locations[attrname] 837 ambiguity.append(len(self.locations[position])) 838 839 return ambiguity 840 841 def position_parameters(self): 842 843 "Position the parameters for each function's parameter table." 844 845 # Reverse the location mappings, producing a mapping from parameter 846 # names to positions. 847 848 param_locations = self.param_locations = {} 849 self._position_attributes(param_locations, self.arg_locations) 850 851 for name, argnames in self.importer.function_parameters.items(): 852 853 # Allocate an extra context parameter in the table. 854 855 l = self.parameters[name] = [None] + [None] * len(argnames) 856 857 # Store an entry for the name along with the name's position in the 858 # parameter list. 859 860 for pos, argname in enumerate(argnames): 861 862 # Position the argument in the table. 863 864 position = param_locations[argname] 865 if position >= len(l): 866 l.extend([None] * (position - len(l) + 1)) 867 868 # Indicate an argument list position starting from 1 (after the 869 # initial context argument). 870 871 l[position] = (argname, pos + 1) 872 873 # Test the structure against any existing parameters. 874 875 if self.existing_parameters: 876 if self.existing_parameters.has_key(name) and self.existing_parameters[name] != l: 877 self.differing_parameters.append(name) 878 879 def populate_tables(self): 880 881 """ 882 Assign identifiers to attributes and encode structure information using 883 these identifiers. 884 """ 885 886 # Initialise the mapping from attribute names to codes. 887 888 l = self.all_attrnames = []; d = {} 889 self._init_name_mapping(l, d, self.existing_attrnames) 890 if self.indicated_attrnames: 891 self._init_name_mapping(l, d, self.indicated_attrnames) 892 self._update_name_mapping(l, d, self.attr_locations) 893 894 # Record the numbers indicating the locations of the names. 895 896 for key, attrnames in self.structures.items(): 897 l = self.attr_table[key] = [] 898 for attrname in attrnames: 899 if attrname is None: 900 l.append(None) 901 else: 902 l.append(d[attrname]) 903 904 # Initialise the mapping from parameter names to codes. 905 906 l = self.all_paramnames = []; d = {} 907 self._init_name_mapping(l, d, self.existing_paramnames) 908 if self.indicated_paramnames: 909 self._init_name_mapping(l, d, self.indicated_paramnames) 910 self._update_name_mapping(l, d, self.param_locations) 911 912 # Record the numbers indicating the locations of the names. 913 914 for key, values in self.parameters.items(): 915 l = self.param_table[key] = [] 916 for value in values: 917 if value is None: 918 l.append(None) 919 else: 920 name, pos = value 921 l.append((d[name], pos)) 922 923 def _init_name_mapping(self, l, d, existing): 924 925 """ 926 Initialise the name collection 'l', with mapping 'd', using the 927 'existing' mapping. 928 """ 929 930 i = 0 931 932 for name in existing: 933 934 # Test for the name in another position. 935 936 if d.has_key(name): 937 if d[name] != i: 938 raise OptimiseError, "Name %s has conflicting codes: %d and %d." % \ 939 (name, d[name], i) 940 else: 941 942 # Test for other usage of the position. 943 944 if i < len(l): 945 if l[i] != name: 946 raise OptimiseError, "Position %d has conflicting names: %s and %s." % \ 947 (i, name, d[name]) 948 l[i] = name 949 else: 950 l.append(name) 951 952 d[name] = i 953 954 i += 1 955 956 def _update_name_mapping(self, l, d, locations): 957 958 """ 959 Using any existing identifiers supplied by 'l' and 'd', update the 960 identifiers using a sorted list of names from 'locations'. 961 """ 962 963 all_names = list(locations.keys()) 964 all_names.sort() 965 966 i = len(l) 967 968 for name in all_names: 969 if not d.has_key(name): 970 d[name] = i 971 l.append(name) 972 i += 1 973 974 def populate_constants(self): 975 976 """ 977 Obtain a collection of distinct constant literals, building a mapping 978 from constant references to those in this collection. 979 """ 980 981 # Obtain mappings from constant values to identifiers. 982 983 self.constants = {} 984 985 # Establish a mapping from local constant identifiers to consolidated 986 # constant identifiers. 987 988 self.constant_numbers = {} 989 990 for name, constant in self.importer.all_constant_values.items(): 991 992 # Each constant is actually (value, value_type, encoding). 993 994 d = digest(constant) 995 self.constants[constant] = d 996 997 # Make sure the digests are really distinct for different 998 # constants. 999 1000 if self.digests.has_key(d): 1001 if self.digests[d] != constant: 1002 raise OptimiseError, "Digest %s used for distinct constants %r and %r." % ( 1003 d, self.digests[d], constant) 1004 else: 1005 self.digests[d] = constant 1006 1007 self.constant_numbers[name] = self.constants[constant] 1008 1009 def combine_rows(a, b): 1010 c = [] 1011 for i, j in zip(a, b): 1012 if i is None or j is None: 1013 c.append(i or j) 1014 else: 1015 return None 1016 return c 1017 1018 def get_attributes_and_sizes(d): 1019 1020 """ 1021 Get attribute and size information for the object attributes defined by 'd' 1022 providing a mapping from (object kind, type name) to attribute names. 1023 1024 Return a matrix of attributes (each row entry consisting of column values 1025 providing attribute names, with value positions corresponding to types 1026 providing such attributes), a list of the type names corresponding to the 1027 columns in the matrix, and a list of ranked sizes each indicating... 1028 1029 * a weighted size depending on the kind of object 1030 * the minimum size of an object employing an attribute 1031 * the number of free columns in the matrix for the attribute 1032 * the attribute name itself 1033 """ 1034 1035 attrs = {} 1036 sizes = {} 1037 objkinds = {} 1038 1039 for objtype, attrnames in d.items(): 1040 objkind, _name = objtype 1041 1042 for attrname in attrnames: 1043 1044 # Record each type supporting the attribute. 1045 1046 init_item(attrs, attrname, set) 1047 attrs[attrname].add(objtype) 1048 1049 # Maintain a record of the smallest object size supporting the given 1050 # attribute. 1051 1052 if not sizes.has_key(attrname): 1053 sizes[attrname] = len(attrnames) 1054 else: 1055 sizes[attrname] = min(sizes[attrname], len(attrnames)) 1056 1057 # Record the object types/kinds supporting the attribute. 1058 1059 init_item(objkinds, attrname, set) 1060 objkinds[attrname].add(objkind) 1061 1062 # Obtain attribute details in order of size and occupancy. 1063 1064 all_objtypes = d.keys() 1065 1066 rsizes = [] 1067 for attrname, size in sizes.items(): 1068 priority = "<instance>" in objkinds[attrname] and 0.5 or 1 1069 occupied = len(attrs[attrname]) 1070 key = (priority * size, size, len(all_objtypes) - occupied, attrname) 1071 rsizes.append(key) 1072 1073 rsizes.sort() 1074 1075 # Make a matrix of attributes. 1076 1077 matrix = {} 1078 for attrname, objtypes in attrs.items(): 1079 1080 # Traverse the object types, adding the attribute name if the object 1081 # type supports the attribute, adding None otherwise. 1082 1083 row = [] 1084 for objtype in all_objtypes: 1085 if objtype in objtypes: 1086 row.append(attrname) 1087 else: 1088 row.append(None) 1089 matrix[attrname] = row 1090 1091 return matrix, all_objtypes, rsizes 1092 1093 def get_parameters_and_sizes(d): 1094 1095 """ 1096 Return a matrix of parameters, a list of functions corresponding to columns 1097 in the matrix, and a list of ranked sizes each indicating... 1098 1099 * a weighted size depending on the kind of object 1100 * the minimum size of a parameter list employing a parameter 1101 * the number of free columns in the matrix for the parameter 1102 * the parameter name itself 1103 1104 This is a slightly simpler version of the above 'get_attributes_and_sizes' 1105 function. 1106 """ 1107 1108 params = {} 1109 sizes = {} 1110 1111 for name, argnames in d.items(): 1112 for argname in argnames: 1113 1114 # Record each function supporting the parameter. 1115 1116 init_item(params, argname, set) 1117 params[argname].add(name) 1118 1119 # Maintain a record of the smallest parameter list supporting the 1120 # given parameter. 1121 1122 if not sizes.has_key(argname): 1123 sizes[argname] = len(argnames) 1124 else: 1125 sizes[argname] = min(sizes[argname], len(argnames)) 1126 1127 # Obtain attribute details in order of size and occupancy. 1128 1129 names = d.keys() 1130 1131 rsizes = [] 1132 for argname, size in sizes.items(): 1133 occupied = len(params[argname]) 1134 key = (size, size, len(names) - occupied, argname) 1135 rsizes.append(key) 1136 1137 rsizes.sort() 1138 1139 # Make a matrix of parameters. 1140 1141 matrix = {} 1142 for argname, types in params.items(): 1143 row = [] 1144 for name in names: 1145 if name in types: 1146 row.append(argname) 1147 else: 1148 row.append(None) 1149 matrix[argname] = row 1150 1151 return matrix, names, rsizes 1152 1153 def get_allocated_locations(d, fn, existing=None): 1154 1155 """ 1156 Return a list where each element corresponds to a structure location and 1157 contains a set of attribute names that may be stored at that location, given 1158 a mapping 'd' whose keys are (object kind, object name) tuples and whose 1159 values are collections of attributes. 1160 """ 1161 1162 matrix, names, rsizes = fn(d) 1163 allocated = [] 1164 1165 # Verify any existing allocation. 1166 1167 allocated_attrnames = set() 1168 1169 if existing: 1170 for attrnames in existing: 1171 1172 # Handle empty positions. 1173 1174 if not attrnames: 1175 allocated.append([None] * len(names)) 1176 continue 1177 1178 base = None 1179 1180 for attrname in attrnames: 1181 1182 # Skip presumably-removed attribute names. 1183 1184 if not matrix.has_key(attrname): 1185 continue 1186 1187 # Handle the first attribute name. 1188 1189 if base is None: 1190 base = matrix[attrname] 1191 allocated_attrnames.add(attrname) 1192 continue 1193 1194 # Combine existing and new attribute positioning. 1195 1196 new = combine_rows(base, matrix[attrname]) 1197 1198 if new: 1199 base = new 1200 allocated_attrnames.add(attrname) 1201 else: 1202 raise OptimiseError, "Attribute %s cannot be explicitly positioned at %d." % \ 1203 (attrname, len(allocated)) 1204 1205 # Handle empty positions. 1206 1207 if base: 1208 allocated.append(base) 1209 else: 1210 allocated.append([None] * len(names)) 1211 1212 # Try to allocate each attribute name in turn. 1213 1214 x = 0 1215 pos = 0 1216 1217 while x < len(rsizes): 1218 1219 # Obtain any previous allocation at the current position. Start at the 1220 # current attribute looking for allocations to combine. 1221 1222 if pos < len(allocated): 1223 base = allocated[pos] 1224 free = base.count(None) 1225 y = x 1226 1227 # Obtain the object information for the attribute name. 1228 1229 else: 1230 weight, size, free, attrname = rsizes[x] 1231 1232 # Ignore allocated attribute names. 1233 1234 if attrname in allocated_attrnames: 1235 x += 1 1236 continue 1237 1238 # Start at the next attribute looking for allocations to combine. 1239 1240 base = matrix[attrname] 1241 y = x + 1 1242 1243 # Examine attribute names that follow in the ranking, attempting to 1244 # accumulate compatible attributes that can co-exist in the same 1245 # position within structures. 1246 1247 while y < len(rsizes): 1248 _weight, _size, _free, _attrname = rsizes[y] 1249 1250 # Ignore allocated attribute names. 1251 1252 if _attrname in allocated_attrnames: 1253 y += 1 1254 continue 1255 1256 # Determine whether this attribute is supported by too many types 1257 # to co-exist. 1258 1259 occupied = len(names) - _free 1260 if occupied > free: 1261 break 1262 1263 # Merge the attribute support for both this and the currently 1264 # considered attribute, testing for conflicts. Adopt the merged row 1265 # details if they do not conflict. 1266 1267 new = combine_rows(base, matrix[_attrname]) 1268 if new: 1269 del matrix[_attrname] 1270 del rsizes[y] 1271 base = new 1272 free -= occupied 1273 1274 # Otherwise, look for other compatible attributes. 1275 1276 else: 1277 y += 1 1278 1279 # Allocate the merged details at the current position. 1280 1281 if pos < len(allocated): 1282 allocated[pos] = base 1283 pos += 1 1284 else: 1285 x += 1 1286 allocated.append(base) 1287 1288 return allocations_to_sets(allocated) 1289 1290 def allocations_to_sets(allocated): 1291 1292 """ 1293 Return the list of attribute names from each row of the 'allocated' 1294 attributes table. 1295 """ 1296 1297 locations = [] 1298 1299 for attrnames in allocated: 1300 l = set() 1301 1302 # Convert populated allocations. 1303 1304 if attrnames: 1305 for attrname in attrnames: 1306 if attrname: 1307 l.add(attrname) 1308 1309 locations.append(l) 1310 1311 return locations 1312 1313 # vim: tabstop=4 expandtab shiftwidth=4