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