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