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, get_attributes_and_sizes) 312 313 def populate_parameters(self): 314 315 "Populate parameter tables using parameter information." 316 317 self.arg_locations = [set()] + get_allocated_locations(self.importer.function_parameters, get_parameters_and_sizes) 318 319 def position_attributes(self): 320 321 "Position specific attribute references." 322 323 # Reverse the location mappings. 324 325 attr_locations = self.attr_locations = {} 326 327 for i, attrnames in enumerate(self.locations): 328 for attrname in attrnames: 329 attr_locations[attrname] = i 330 331 # Record the structures. 332 333 for (objkind, name), attrnames in self.all_attrs.items(): 334 key = Reference(objkind, name) 335 l = self.structures[key] = [None] * len(attrnames) 336 for attrname in attrnames: 337 position = attr_locations[attrname] 338 if position >= len(l): 339 l.extend([None] * (position - len(l) + 1)) 340 l[position] = attrname 341 342 def initialise_access_instructions(self): 343 344 "Expand access plans into instruction sequences." 345 346 for access_location, access_plan in self.deducer.access_plans.items(): 347 348 # Obtain the access details. 349 350 name, test, test_type, base, \ 351 traversed, traversal_modes, attrnames, \ 352 context, context_test, \ 353 first_method, final_method, \ 354 origin, accessor_kinds = access_plan 355 356 # Emit instructions by appending them to a list. 357 358 instructions = [] 359 emit = instructions.append 360 361 # Identify any static original accessor. 362 363 if base: 364 original_accessor = base 365 366 # Employ names as contexts unless the context needs testing and 367 # potentially updating. In such cases, temporary context storage is 368 # used instead. 369 370 elif name and not (context_test == "test" and 371 final_method in ("access-invoke", "static-invoke")): 372 original_accessor = "<name>" # refers to the name 373 374 # Use a generic placeholder representing the access expression in 375 # the general case. 376 377 else: 378 original_accessor = "<expr>" 379 380 # Prepare for any first attribute access. 381 382 if traversed: 383 attrname = traversed[0] 384 del traversed[0] 385 elif attrnames: 386 attrname = attrnames[0] 387 del attrnames[0] 388 389 # Perform the first access explicitly if at least one operation 390 # requires it. 391 392 access_first_attribute = final_method in ("access", "access-invoke", "assign") or traversed or attrnames 393 394 # Determine whether the first access involves assignment. 395 396 assigning = not traversed and not attrnames and final_method == "assign" 397 set_accessor = assigning and "<set_target_accessor>" or "<set_accessor>" 398 stored_accessor = assigning and "<target_accessor>" or "<accessor>" 399 400 # Set the context if already available. 401 402 context_var = None 403 404 if context == "base": 405 accessor = context_var = (base,) 406 elif context == "original-accessor": 407 408 # Prevent re-evaluation of any dynamic expression by storing it. 409 410 if original_accessor == "<expr>": 411 if final_method in ("access-invoke", "static-invoke"): 412 emit(("<set_context>", original_accessor)) 413 accessor = context_var = ("<context>",) 414 else: 415 emit((set_accessor, original_accessor)) 416 accessor = context_var = (stored_accessor,) 417 else: 418 accessor = context_var = (original_accessor,) 419 420 # Assigning does not set the context. 421 422 elif context in ("final-accessor", "unset") and access_first_attribute: 423 424 # Prevent re-evaluation of any dynamic expression by storing it. 425 426 if original_accessor == "<expr>": 427 emit((set_accessor, original_accessor)) 428 accessor = (stored_accessor,) 429 else: 430 accessor = (original_accessor,) 431 432 # Apply any test. 433 434 if test[0] == "test": 435 accessor = ("__%s_%s_%s" % test, accessor, test_type) 436 437 # Perform the first or final access. 438 # The access only needs performing if the resulting accessor is used. 439 440 remaining = len(traversed + attrnames) 441 442 if access_first_attribute: 443 444 if first_method == "relative-class": 445 if assigning: 446 emit(("__store_via_class", accessor, attrname, "<assexpr>")) 447 else: 448 accessor = ("__load_via_class", accessor, attrname) 449 450 elif first_method == "relative-object": 451 if assigning: 452 emit(("__store_via_object", accessor, attrname, "<assexpr>")) 453 else: 454 accessor = ("__load_via_object", accessor, attrname) 455 456 elif first_method == "relative-object-class": 457 if assigning: 458 emit(("__get_class_and_store", accessor, attrname, "<assexpr>")) 459 else: 460 accessor = ("__get_class_and_load", accessor, attrname) 461 462 elif first_method == "check-class": 463 if assigning: 464 emit(("__check_and_store_via_class", accessor, attrname, "<assexpr>")) 465 else: 466 accessor = ("__check_and_load_via_class", accessor, attrname) 467 468 elif first_method == "check-object": 469 if assigning: 470 emit(("__check_and_store_via_object", accessor, attrname, "<assexpr>")) 471 else: 472 accessor = ("__check_and_load_via_object", accessor, attrname) 473 474 elif first_method == "check-object-class": 475 if assigning: 476 emit(("__check_and_store_via_any", accessor, attrname, "<assexpr>")) 477 else: 478 accessor = ("__check_and_load_via_any", accessor, attrname) 479 480 # Traverse attributes using the accessor. 481 482 if traversed: 483 for attrname, traversal_mode in zip(traversed, traversal_modes): 484 assigning = remaining == 1 and final_method == "assign" 485 486 # Set the context, if appropriate. 487 488 if remaining == 1 and final_method != "assign" and context == "final-accessor": 489 490 # Invoked attributes employ a separate context accessed 491 # during invocation. 492 493 if final_method in ("access-invoke", "static-invoke"): 494 emit(("<set_context>", accessor)) 495 accessor = context_var = "<context>" 496 497 # A private context within the access is otherwise 498 # retained. 499 500 else: 501 emit(("<set_private_context>", accessor)) 502 accessor = context_var = "<private_context>" 503 504 # Perform the access only if not achieved directly. 505 506 if remaining > 1 or final_method in ("access", "access-invoke", "assign"): 507 508 if traversal_mode == "class": 509 if assigning: 510 emit(("__store_via_class", accessor, attrname, "<assexpr>")) 511 else: 512 accessor = ("__load_via_class", accessor, attrname) 513 else: 514 if assigning: 515 emit(("__store_via_object", accessor, attrname, "<assexpr>")) 516 else: 517 accessor = ("__load_via_object", accessor, attrname) 518 519 remaining -= 1 520 521 if attrnames: 522 for attrname in attrnames: 523 assigning = remaining == 1 and final_method == "assign" 524 525 # Set the context, if appropriate. 526 527 if remaining == 1 and final_method != "assign" and context == "final-accessor": 528 529 # Invoked attributes employ a separate context accessed 530 # during invocation. 531 532 if final_method in ("access-invoke", "static-invoke"): 533 emit(("<set_context>", accessor)) 534 accessor = context_var = "<context>" 535 536 # A private context within the access is otherwise 537 # retained. 538 539 else: 540 emit(("<set_private_context>", accessor)) 541 accessor = context_var = "<private_context>" 542 543 # Perform the access only if not achieved directly. 544 545 if remaining > 1 or final_method in ("access", "access-invoke", "assign"): 546 547 if assigning: 548 emit(("__check_and_store_via_any", accessor, attrname, "<assexpr>")) 549 else: 550 accessor = ("__check_and_load_via_any", accessor, attrname) 551 552 remaining -= 1 553 554 # Define or emit the means of accessing the actual target. 555 556 # Assignments to known attributes. 557 558 if final_method == "static-assign": 559 parent, attrname = origin.rsplit(".", 1) 560 emit(("__store_via_object", parent, attrname, "<assexpr>")) 561 562 # Invoked attributes employ a separate context. 563 564 elif final_method in ("static", "static-invoke"): 565 accessor = ("__load_static_ignore", origin) 566 567 # Wrap accesses in context operations. 568 569 if context_test == "test": 570 571 # Test and combine the context with static attribute details. 572 573 if final_method == "static": 574 emit(("__load_static_test", context_var, origin)) 575 576 # Test the context, storing it separately if required for the 577 # immediately invoked static attribute. 578 579 elif final_method == "static-invoke": 580 emit(("<test_context_static>", context_var, origin)) 581 582 # Test the context, storing it separately if required for an 583 # immediately invoked attribute. 584 585 elif final_method == "access-invoke": 586 emit(("<test_context_revert>", context_var, accessor)) 587 588 # Test the context and update the attribute details if 589 # appropriate. 590 591 else: 592 emit(("__test_context", context_var, accessor)) 593 594 elif context_test == "replace": 595 596 # Produce an object with updated context. 597 598 if final_method == "static": 599 emit(("__load_static_replace", context_var, origin)) 600 601 # Omit the context update operation where the target is static 602 # and the context is recorded separately. 603 604 elif final_method == "static-invoke": 605 pass 606 607 # If a separate context is used for an immediate invocation, 608 # produce the attribute details unchanged. 609 610 elif final_method == "access-invoke": 611 emit(accessor) 612 613 # Update the context in the attribute details. 614 615 else: 616 emit(("__update_context", context_var, accessor)) 617 618 # Omit the accessor for assignments and for invocations of static 619 # targets. 620 621 elif final_method not in ("assign", "static-assign", "static-invoke"): 622 emit(accessor) 623 624 # Produce an advisory instruction regarding the context. 625 626 if context_var: 627 emit(("<context_identity>", context_var)) 628 629 self.access_instructions[access_location] = instructions 630 self.accessor_kinds[access_location] = accessor_kinds 631 632 def get_ambiguity_for_attributes(self, attrnames): 633 634 """ 635 Return a list of attribute position alternatives corresponding to each 636 of the given 'attrnames'. 637 """ 638 639 ambiguity = [] 640 641 for attrname in attrnames: 642 position = self.attr_locations[attrname] 643 ambiguity.append(len(self.locations[position])) 644 645 return ambiguity 646 647 def position_parameters(self): 648 649 "Position the parameters for each function's parameter table." 650 651 # Reverse the location mappings. 652 653 param_locations = self.param_locations = {} 654 655 for i, argnames in enumerate(self.arg_locations): 656 657 # Position the arguments. 658 659 for argname in argnames: 660 param_locations[argname] = i 661 662 for name, argnames in self.importer.function_parameters.items(): 663 664 # Allocate an extra context parameter in the table. 665 666 l = self.parameters[name] = [None] + [None] * len(argnames) 667 668 # Store an entry for the name along with the name's position in the 669 # parameter list. 670 671 for pos, argname in enumerate(argnames): 672 673 # Position the argument in the table. 674 675 position = param_locations[argname] 676 if position >= len(l): 677 l.extend([None] * (position - len(l) + 1)) 678 679 # Indicate an argument list position starting from 1 (after the 680 # initial context argument). 681 682 l[position] = (argname, pos + 1) 683 684 def populate_tables(self): 685 686 """ 687 Assign identifiers to attributes and encode structure information using 688 these identifiers. 689 """ 690 691 self.all_attrnames, d = self._get_name_mapping(self.attr_locations) 692 693 # Record the numbers indicating the locations of the names. 694 695 for key, attrnames in self.structures.items(): 696 l = self.attr_table[key] = [] 697 for attrname in attrnames: 698 if attrname is None: 699 l.append(None) 700 else: 701 l.append(d[attrname]) 702 703 self.all_paramnames, d = self._get_name_mapping(self.param_locations) 704 705 # Record the numbers indicating the locations of the names. 706 707 for key, values in self.parameters.items(): 708 l = self.param_table[key] = [] 709 for value in values: 710 if value is None: 711 l.append(None) 712 else: 713 name, pos = value 714 l.append((d[name], pos)) 715 716 def _get_name_mapping(self, locations): 717 718 """ 719 Get a sorted list of names from 'locations', then map them to 720 identifying numbers. Return the list and the mapping. 721 """ 722 723 all_names = locations.keys() 724 all_names.sort() 725 d = {} 726 for i, name in enumerate(all_names): 727 d[name] = i 728 return all_names, d 729 730 def populate_constants(self): 731 732 """ 733 Obtain a collection of distinct constant literals, building a mapping 734 from constant references to those in this collection. 735 """ 736 737 # Obtain mappings from constant values to identifiers. 738 739 self.constants = {} 740 741 for path, constants in self.importer.all_constants.items(): 742 743 # Record constants and obtain a number for them. 744 # Each constant is actually (value, value_type, encoding). 745 746 for constant, n in constants.items(): 747 d = digest(constant) 748 self.constants[constant] = d 749 750 # Make sure the digests are really distinct for different 751 # constants. 752 753 if self.digests.has_key(d): 754 if self.digests[d] != constant: 755 raise OptimiseError, "Digest %s used for distinct constants %r and %r." % ( 756 d, self.digests[d], constant) 757 else: 758 self.digests[d] = constant 759 760 # Establish a mapping from local constant identifiers to consolidated 761 # constant identifiers. 762 763 self.constant_numbers = {} 764 765 for name, constant in self.importer.all_constant_values.items(): 766 self.constant_numbers[name] = self.constants[constant] 767 768 def combine_rows(a, b): 769 c = [] 770 for i, j in zip(a, b): 771 if i is None or j is None: 772 c.append(i or j) 773 else: 774 return None 775 return c 776 777 def get_attributes_and_sizes(d): 778 779 """ 780 Return a matrix of attributes, a list of type names corresponding to columns 781 in the matrix, and a list of ranked sizes each indicating... 782 783 * a weighted size depending on the kind of object 784 * the minimum size of an object employing an attribute 785 * the number of free columns in the matrix for the attribute 786 * the attribute name itself 787 """ 788 789 attrs = {} 790 sizes = {} 791 objkinds = {} 792 793 for name, attrnames in d.items(): 794 objkind, _name = name 795 796 for attrname in attrnames: 797 798 # Record each type supporting the attribute. 799 800 init_item(attrs, attrname, set) 801 attrs[attrname].add(name) 802 803 # Maintain a record of the smallest object size supporting the given 804 # attribute. 805 806 if not sizes.has_key(attrname): 807 sizes[attrname] = len(attrnames) 808 else: 809 sizes[attrname] = min(sizes[attrname], len(attrnames)) 810 811 # Record the object types/kinds supporting the attribute. 812 813 init_item(objkinds, attrname, set) 814 objkinds[attrname].add(objkind) 815 816 # Obtain attribute details in order of size and occupancy. 817 818 names = d.keys() 819 820 rsizes = [] 821 for attrname, size in sizes.items(): 822 priority = "<instance>" in objkinds[attrname] and 0.5 or 1 823 occupied = len(attrs[attrname]) 824 key = (priority * size, size, len(names) - occupied, attrname) 825 rsizes.append(key) 826 827 rsizes.sort() 828 829 # Make a matrix of attributes. 830 831 matrix = {} 832 for attrname, types in attrs.items(): 833 row = [] 834 for name in names: 835 if name in types: 836 row.append(attrname) 837 else: 838 row.append(None) 839 matrix[attrname] = row 840 841 return matrix, names, rsizes 842 843 def get_parameters_and_sizes(d): 844 845 """ 846 Return a matrix of parameters, a list of functions corresponding to columns 847 in the matrix, and a list of ranked sizes each indicating... 848 849 * a weighted size depending on the kind of object 850 * the minimum size of a parameter list employing a parameter 851 * the number of free columns in the matrix for the parameter 852 * the parameter name itself 853 854 This is a slightly simpler version of the above 'get_attributes_and_sizes' 855 function. 856 """ 857 858 params = {} 859 sizes = {} 860 861 for name, argnames in d.items(): 862 for argname in argnames: 863 864 # Record each function supporting the parameter. 865 866 init_item(params, argname, set) 867 params[argname].add(name) 868 869 # Maintain a record of the smallest parameter list supporting the 870 # given parameter. 871 872 if not sizes.has_key(argname): 873 sizes[argname] = len(argnames) 874 else: 875 sizes[argname] = min(sizes[argname], len(argnames)) 876 877 # Obtain attribute details in order of size and occupancy. 878 879 names = d.keys() 880 881 rsizes = [] 882 for argname, size in sizes.items(): 883 occupied = len(params[argname]) 884 key = (size, size, len(names) - occupied, argname) 885 rsizes.append(key) 886 887 rsizes.sort() 888 889 # Make a matrix of parameters. 890 891 matrix = {} 892 for argname, types in params.items(): 893 row = [] 894 for name in names: 895 if name in types: 896 row.append(argname) 897 else: 898 row.append(None) 899 matrix[argname] = row 900 901 return matrix, names, rsizes 902 903 def get_allocated_locations(d, fn): 904 905 """ 906 Return a list where each element corresponds to a structure location and 907 contains a set of attribute names that may be stored at that location, given 908 a mapping 'd' whose keys are (object kind, object name) tuples and whose 909 values are collections of attributes. 910 """ 911 912 matrix, names, rsizes = fn(d) 913 allocated = [] 914 915 x = 0 916 while x < len(rsizes): 917 weight, size, free, attrname = rsizes[x] 918 base = matrix[attrname] 919 y = x + 1 920 while y < len(rsizes): 921 _weight, _size, _free, _attrname = rsizes[y] 922 occupied = len(names) - _free 923 if occupied > free: 924 break 925 new = combine_rows(base, matrix[_attrname]) 926 if new: 927 del matrix[_attrname] 928 del rsizes[y] 929 base = new 930 free -= occupied 931 else: 932 y += 1 933 allocated.append(base) 934 x += 1 935 936 # Return the list of attribute names from each row of the allocated 937 # attributes table. 938 939 locations = [] 940 for attrnames in allocated: 941 l = set() 942 for attrname in attrnames: 943 if attrname: 944 l.add(attrname) 945 locations.append(l) 946 return locations 947 948 # vim: tabstop=4 expandtab shiftwidth=4