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