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