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 init_item, sorted_output, CommonOutput 23 from encoders import digest 24 from errors import OptimiseError 25 from os.path import exists, join 26 from os import makedirs 27 from referencing import decode_reference, Reference 28 29 class Optimiser(CommonOutput): 30 31 "Optimise objects in a program." 32 33 def __init__(self, importer, deducer, output, 34 attrnames_filename=None, locations_filename=None, 35 paramnames_filename=None, parameter_locations_filename=None): 36 37 """ 38 Initialise an instance using the given 'importer' and 'deducer' that 39 will perform the arrangement of attributes for program objects, writing 40 the results to the given 'output' directory. 41 42 If 'attrnames_filename', 'locations_filename', 'paramnames_filename', or 43 'parameter_locations_filename' are given, they will be used to 44 explicitly indicate existing attribute code, attribute position, 45 parameter code, and parameter position information respectively. 46 """ 47 48 self.importer = importer 49 self.deducer = deducer 50 self.output = output 51 52 # Explicitly-specified attribute and parameter sources. 53 54 self.attrnames_filename = attrnames_filename 55 self.locations_filename = locations_filename 56 self.paramnames_filename = paramnames_filename 57 self.parameter_locations_filename = parameter_locations_filename 58 59 # Detection of differences between any existing structure or signature 60 # information and the generated information. 61 62 self.differing_structures = [] 63 self.differing_parameters = [] 64 65 # Locations/offsets of attributes in objects. 66 67 self.locations = None 68 self.existing_locations = None 69 70 self.attr_locations = None 71 72 # Attribute code assignments. 73 74 self.all_attrnames = None 75 self.existing_attrnames = None 76 self.indicated_attrnames = None 77 78 # Locations of parameters in parameter tables. 79 80 self.arg_locations = None 81 self.existing_arg_locations = None 82 83 self.param_locations = None 84 85 # Parameter code assignments. 86 87 self.all_paramnames = None 88 self.existing_paramnames = None 89 self.indicated_paramnames = None 90 91 # Object structure information. 92 93 self.structures = {} 94 self.existing_structures = None 95 self.attr_table = {} 96 97 # Parameter list information. 98 99 self.parameters = {} 100 self.existing_parameters = None 101 self.param_table = {} 102 103 # Constant literal information. 104 105 self.constants = [] 106 self.constant_numbers = {} 107 self.digests = {} 108 109 # Optimiser activities. 110 111 self.from_output() 112 113 # Define or redefine structure information. 114 115 self.populate_objects() 116 self.position_attributes() 117 self.populate_parameters() 118 self.position_parameters() 119 self.populate_tables() 120 self.populate_constants() 121 122 def need_reset(self): 123 124 """ 125 Return whether attribute or parameter information has changed, requiring 126 the reset/recompilation of all source files. 127 """ 128 129 return self.differing_structures or self.differing_parameters 130 131 def from_output(self): 132 133 "Read input files that influence optimisation." 134 135 # Remove any output for a different program. 136 137 self.check_output() 138 139 # Existing attribute and parameter positioning information. This 140 # influences the positions of attributes and parameters found in the 141 # program. 142 143 locations_filename = self.locations_filename or \ 144 join(self.output, "locations") 145 146 parameter_locations_filename = self.parameter_locations_filename or \ 147 join(self.output, "parameter_locations") 148 149 self.existing_locations = self.read_data(locations_filename, self._line_to_list, list) 150 self.existing_arg_locations = self.read_data(parameter_locations_filename, self._line_to_list, list) 151 152 # Existing attribute and parameter code information. This is used to 153 # check the compatibility of the output against any assignments 154 # previously made. 155 156 identity = lambda x: x 157 none = lambda x: None 158 159 attrnames_filename = join(self.output, "attrnames") 160 paramnames_filename = join(self.output, "paramnames") 161 162 self.existing_attrnames = self.read_data(attrnames_filename, identity, none) 163 self.existing_paramnames = self.read_data(paramnames_filename, identity, none) 164 165 # Explicitly-specified attribute name and parameter name codes. These 166 # direct assignment of codes in the program. 167 168 self.indicated_attrnames = self.attrnames_filename and \ 169 self.read_data(self.attrnames_filename, identity, none) 170 171 self.indicated_paramnames = self.paramnames_filename and \ 172 self.read_data(self.paramnames_filename, identity, none) 173 174 # Existing structure and signature information. This is used to check 175 # the output and detect whether structures or signatures have changed. 176 177 structures_filename = join(self.output, "structures") 178 parameters_filename = join(self.output, "parameters") 179 180 self.existing_structures = dict(self.read_data(structures_filename, self._line_to_structure_pairs, list)) 181 self.existing_parameters = dict(self.read_data(parameters_filename, self._line_to_signature_pairs, list)) 182 183 def _line_to_list(self, line): 184 185 "Convert comma-separated values in 'line' to a list of values." 186 187 return line.split(", ") 188 189 def _line_to_signature_pairs(self, line): 190 191 "Convert comma-separated values in 'line' to a list of pairs of values." 192 193 l = [] 194 objpath, line = line.split(" ", 1) 195 for values in line.split(", "): 196 if values != "-": 197 name, pos = values.split(":") 198 l.append((name, int(pos))) 199 else: 200 l.append(None) 201 return (objpath, l) 202 203 def _line_to_structure_pairs(self, line): 204 205 "Convert comma-separated values in 'line' to a list of pairs of values." 206 207 l = [] 208 ref, line = line.split(" ", 1) 209 values = map(lambda x: x != '-' and x or None, line.split(", ")) 210 return (decode_reference(ref), values) 211 212 def read_data(self, filename, decode, empty): 213 214 """ 215 Read location details from 'filename', using 'decode' to convert each 216 line and 'empty' to produce an empty result where no data is given on a 217 line, returning a collection. 218 """ 219 220 collection = [] 221 222 if exists(filename): 223 f = open(filename) 224 try: 225 for line in f.readlines(): 226 line = line.rstrip() 227 if line: 228 attrnames = decode(line) 229 else: 230 attrnames = empty() 231 232 collection.append(attrnames) 233 finally: 234 f.close() 235 236 return collection 237 238 def to_output(self): 239 240 "Write the output files using optimisation information." 241 242 if not exists(self.output): 243 makedirs(self.output) 244 245 self.write_objects() 246 247 def write_objects(self): 248 249 """ 250 Write object-related output. 251 252 The locations are a list of positions indicating the attributes residing 253 at each position in the different structures in a program. 254 255 ---- 256 257 The parameter locations are a list of positions indicating the parameters 258 residing at each position in the different parameter lists in a program. 259 260 ---- 261 262 The structures are presented as a table in the following format: 263 264 qualified name " " attribute names 265 266 The attribute names are separated by ", " characters and indicate the 267 attribute provided at each position in the structure associated with the 268 given type. Where no attribute is provided at a particular location 269 within a structure, "-" is given. 270 271 ---- 272 273 The parameters are presented as a table in the following format: 274 275 qualified name " " parameter details 276 277 The parameter details are separated by ", " characters and indicate 278 the parameter name and list position for each parameter described at 279 each location in the parameter table associated with the given 280 function. Where no parameter details are provided at a particular 281 location within a parameter table, "-" is given. The name and list 282 position are separated by a colon (":"). 283 284 ---- 285 286 The attribute table is presented as a table in the following format: 287 288 qualified name " " attribute identifiers 289 290 Instead of attribute names, identifiers defined according to the order 291 given in the "attrnames" file are employed to denote the attributes 292 featured in each type's structure. Where no attribute is provided at a 293 particular location within a structure, "-" is given. 294 295 ---- 296 297 The parameter table is presented as a table in the following format: 298 299 qualified name " " parameter details 300 301 Instead of parameter names, identifiers defined according to the order 302 given in the "paramnames" file are employed to denote the parameters 303 featured in each function's parameter table. Where no parameter is 304 provided at a particular location within a table, "-" is given. 305 306 ---- 307 308 The ordered list of attribute names is given in the "attrnames" file. 309 310 ---- 311 312 The ordered list of parameter names is given in the "paramnames" file. 313 314 ---- 315 316 The ordered list of constant literals is given in the "constants" file. 317 """ 318 319 f = open(join(self.output, "locations"), "w") 320 try: 321 for attrnames in self.locations: 322 print >>f, sorted_output(attrnames) 323 324 finally: 325 f.close() 326 327 f = open(join(self.output, "parameter_locations"), "w") 328 try: 329 for argnames in self.arg_locations: 330 print >>f, sorted_output(argnames) 331 332 finally: 333 f.close() 334 335 f = open(join(self.output, "structures"), "w") 336 try: 337 structures = self.structures.items() 338 structures.sort() 339 340 for name, attrnames in structures: 341 print >>f, name, ", ".join([s or "-" for s in attrnames]) 342 343 finally: 344 f.close() 345 346 f = open(join(self.output, "parameters"), "w") 347 try: 348 parameters = self.parameters.items() 349 parameters.sort() 350 351 for name, argnames in parameters: 352 l = [] 353 for s in argnames: 354 l.append(s and ("%s:%d" % s) or "-") 355 print >>f, name, ", ".join(l) 356 357 finally: 358 f.close() 359 360 f = open(join(self.output, "attrtable"), "w") 361 try: 362 attr_table = self.attr_table.items() 363 attr_table.sort() 364 365 for name, attrcodes in attr_table: 366 l = [] 367 for i in attrcodes: 368 l.append(i is not None and str(i) or "-") 369 print >>f, name, ", ".join(l) 370 371 finally: 372 f.close() 373 374 f = open(join(self.output, "paramtable"), "w") 375 try: 376 param_table = self.param_table.items() 377 param_table.sort() 378 379 for name, paramcodes in param_table: 380 l = [] 381 for s in paramcodes: 382 l.append(s and ("%d:%d" % s) or "-") 383 print >>f, name, ", ".join(l) 384 385 finally: 386 f.close() 387 388 f = open(join(self.output, "attrnames"), "w") 389 try: 390 for name in self.all_attrnames: 391 print >>f, name 392 393 finally: 394 f.close() 395 396 f = open(join(self.output, "paramnames"), "w") 397 try: 398 for name in self.all_paramnames: 399 print >>f, name 400 401 finally: 402 f.close() 403 404 f = open(join(self.output, "constants"), "w") 405 try: 406 constants = [] 407 for (value, value_type, encoding), n in self.constants.items(): 408 constants.append((n, value_type, encoding, value)) 409 constants.sort() 410 for n, value_type, encoding, value in constants: 411 print >>f, value_type, encoding or "{}", repr(value) 412 413 finally: 414 f.close() 415 416 def populate_objects(self): 417 418 "Populate objects using attribute and usage information." 419 420 self.all_attrs = {} 421 422 # Partition attributes into separate sections so that class and instance 423 # attributes are treated separately. 424 425 for source, objkind in [ 426 (self.importer.all_class_attrs, "<class>"), 427 (self.importer.all_instance_attrs, "<instance>"), 428 (self.importer.all_module_attrs, "<module>") 429 ]: 430 431 for name, attrnames in source.items(): 432 433 # Remove temporary names from structures. 434 435 attrnames = filter(lambda x: not x.startswith("$t"), attrnames) 436 self.all_attrs[(objkind, name)] = attrnames 437 438 try: 439 self.locations = get_allocated_locations(self.all_attrs, 440 get_attributes_and_sizes, self.existing_locations) 441 442 # Uphold positioning conflicts only if the existing locations were 443 # explicitly specified. 444 445 except OptimiseError: 446 if self.locations_filename: 447 raise 448 449 # Otherwise, reposition attributes, causing the program to be 450 # regenerated. 451 452 self.locations = get_allocated_locations(self.all_attrs, 453 get_attributes_and_sizes) 454 455 def populate_parameters(self): 456 457 "Populate parameter tables using parameter information." 458 459 # Allocate positions from 1 onwards, ignoring the context argument. 460 461 self.arg_locations = [set()] + get_allocated_locations( 462 self.importer.function_parameters, get_parameters_and_sizes, 463 self.existing_arg_locations[1:]) 464 465 def position_attributes(self): 466 467 "Position specific attribute references." 468 469 # Reverse the location mappings, producing a mapping from attribute 470 # names to positions. 471 472 attr_locations = self.attr_locations = {} 473 self._position_attributes(attr_locations, self.locations) 474 475 # Add any previously-known attribute locations. This prevents attributes 476 # from being assigned different identifying codes by preserving obsolete 477 # attribute codes. 478 479 if self.existing_locations: 480 self._position_attributes(attr_locations, self.existing_locations) 481 482 # Record the structures. 483 484 for (objkind, name), attrnames in self.all_attrs.items(): 485 key = Reference(objkind, name) 486 l = self.structures[key] = [None] * len(attrnames) 487 488 for attrname in attrnames: 489 position = attr_locations[attrname] 490 if position >= len(l): 491 l.extend([None] * (position - len(l) + 1)) 492 l[position] = attrname 493 494 # Test the structure against any existing attributes. 495 496 if self.existing_structures: 497 if self.existing_structures.has_key(key) and self.existing_structures[key] != l: 498 self.differing_structures.append(key) 499 500 def _position_attributes(self, d, l): 501 502 """ 503 For each attribute, store a mapping in 'd' to the index in 'l' at which 504 it can be found. 505 """ 506 507 for i, attrnames in enumerate(l): 508 for attrname in attrnames: 509 if not d.has_key(attrname): 510 d[attrname] = i 511 512 def get_ambiguity_for_attributes(self, attrnames): 513 514 """ 515 Return a list of attribute position alternatives corresponding to each 516 of the given 'attrnames'. 517 """ 518 519 ambiguity = [] 520 521 for attrname in attrnames: 522 position = self.attr_locations[attrname] 523 ambiguity.append(len(self.locations[position])) 524 525 return ambiguity 526 527 def position_parameters(self): 528 529 "Position the parameters for each function's parameter table." 530 531 # Reverse the location mappings, producing a mapping from parameter 532 # names to positions. 533 534 param_locations = self.param_locations = {} 535 self._position_attributes(param_locations, self.arg_locations) 536 537 for name, argnames in self.importer.function_parameters.items(): 538 539 # Allocate an extra context parameter in the table. 540 541 l = self.parameters[name] = [None] + [None] * len(argnames) 542 543 # Store an entry for the name along with the name's position in the 544 # parameter list. 545 546 for pos, argname in enumerate(argnames): 547 548 # Position the argument in the table. 549 550 position = param_locations[argname] 551 if position >= len(l): 552 l.extend([None] * (position - len(l) + 1)) 553 554 # Indicate an argument list position starting from 1 (after the 555 # initial context argument). 556 557 l[position] = (argname, pos + 1) 558 559 # Test the structure against any existing parameters. 560 561 if self.existing_parameters: 562 if self.existing_parameters.has_key(name) and self.existing_parameters[name] != l: 563 self.differing_parameters.append(name) 564 565 def populate_tables(self): 566 567 """ 568 Assign identifiers to attributes and encode structure information using 569 these identifiers. 570 """ 571 572 # Initialise the mapping from attribute names to codes. 573 574 l = self.all_attrnames = []; d = {} 575 self._init_name_mapping(l, d, self.existing_attrnames) 576 if self.indicated_attrnames: 577 self._init_name_mapping(l, d, self.indicated_attrnames) 578 self._update_name_mapping(l, d, self.attr_locations) 579 580 # Record the numbers indicating the locations of the names. 581 582 for key, attrnames in self.structures.items(): 583 l = self.attr_table[key] = [] 584 for attrname in attrnames: 585 if attrname is None: 586 l.append(None) 587 else: 588 l.append(d[attrname]) 589 590 # Initialise the mapping from parameter names to codes. 591 592 l = self.all_paramnames = []; d = {} 593 self._init_name_mapping(l, d, self.existing_paramnames) 594 if self.indicated_paramnames: 595 self._init_name_mapping(l, d, self.indicated_paramnames) 596 self._update_name_mapping(l, d, self.param_locations) 597 598 # Record the numbers indicating the locations of the names. 599 600 for key, values in self.parameters.items(): 601 l = self.param_table[key] = [] 602 for value in values: 603 if value is None: 604 l.append(None) 605 else: 606 name, pos = value 607 l.append((d[name], pos)) 608 609 def _init_name_mapping(self, l, d, existing): 610 611 """ 612 Initialise the name collection 'l', with mapping 'd', using the 613 'existing' mapping. 614 """ 615 616 i = 0 617 618 for name in existing: 619 620 # Test for the name in another position. 621 622 if d.has_key(name): 623 if d[name] != i: 624 raise OptimiseError, "Name %s has conflicting codes: %d and %d." % \ 625 (name, d[name], i) 626 else: 627 628 # Test for other usage of the position. 629 630 if i < len(l): 631 if l[i] != name: 632 raise OptimiseError, "Position %d has conflicting names: %s and %s." % \ 633 (i, name, d[name]) 634 l[i] = name 635 else: 636 l.append(name) 637 638 d[name] = i 639 640 i += 1 641 642 def _update_name_mapping(self, l, d, locations): 643 644 """ 645 Using any existing identifiers supplied by 'l' and 'd', update the 646 identifiers using a sorted list of names from 'locations'. 647 """ 648 649 all_names = list(locations.keys()) 650 all_names.sort() 651 652 i = len(l) 653 654 for name in all_names: 655 if not d.has_key(name): 656 d[name] = i 657 l.append(name) 658 i += 1 659 660 def populate_constants(self): 661 662 """ 663 Obtain a collection of distinct constant literals, building a mapping 664 from constant references to those in this collection. 665 """ 666 667 # Obtain mappings from constant values to identifiers. 668 669 self.constants = {} 670 671 # Establish a mapping from local constant identifiers to consolidated 672 # constant identifiers. 673 674 self.constant_numbers = {} 675 676 for name, constant in self.importer.all_constant_values.items(): 677 678 # Each constant is actually (value, value_type, encoding). 679 680 d = digest(constant) 681 self.constants[constant] = d 682 683 # Make sure the digests are really distinct for different 684 # constants. 685 686 if self.digests.has_key(d): 687 if self.digests[d] != constant: 688 raise OptimiseError, "Digest %s used for distinct constants %r and %r." % ( 689 d, self.digests[d], constant) 690 else: 691 self.digests[d] = constant 692 693 self.constant_numbers[name] = self.constants[constant] 694 695 def combine_rows(a, b): 696 c = [] 697 for i, j in zip(a, b): 698 if i is None or j is None: 699 c.append(i or j) 700 else: 701 return None 702 return c 703 704 def get_attributes_and_sizes(d): 705 706 """ 707 Get attribute and size information for the object attributes defined by 'd' 708 providing a mapping from (object kind, type name) to attribute names. 709 710 Return a matrix of attributes (each row entry consisting of column values 711 providing attribute names, with value positions corresponding to types 712 providing such attributes), a list of the type names corresponding to the 713 columns in the matrix, and a list of ranked sizes each indicating... 714 715 * a weighted size depending on the kind of object 716 * the minimum size of an object employing an attribute 717 * the number of free columns in the matrix for the attribute 718 * the attribute name itself 719 """ 720 721 attrs = {} 722 sizes = {} 723 objkinds = {} 724 725 for objtype, attrnames in d.items(): 726 objkind, _name = objtype 727 728 for attrname in attrnames: 729 730 # Record each type supporting the attribute. 731 732 init_item(attrs, attrname, set) 733 attrs[attrname].add(objtype) 734 735 # Maintain a record of the smallest object size supporting the given 736 # attribute. 737 738 if not sizes.has_key(attrname): 739 sizes[attrname] = len(attrnames) 740 else: 741 sizes[attrname] = min(sizes[attrname], len(attrnames)) 742 743 # Record the object types/kinds supporting the attribute. 744 745 init_item(objkinds, attrname, set) 746 objkinds[attrname].add(objkind) 747 748 # Obtain attribute details in order of size and occupancy. 749 750 all_objtypes = d.keys() 751 752 rsizes = [] 753 for attrname, size in sizes.items(): 754 priority = "<instance>" in objkinds[attrname] and 0.5 or 1 755 occupied = len(attrs[attrname]) 756 key = (priority * size, size, len(all_objtypes) - occupied, attrname) 757 rsizes.append(key) 758 759 rsizes.sort() 760 761 # Make a matrix of attributes. 762 763 matrix = {} 764 for attrname, objtypes in attrs.items(): 765 766 # Traverse the object types, adding the attribute name if the object 767 # type supports the attribute, adding None otherwise. 768 769 row = [] 770 for objtype in all_objtypes: 771 if objtype in objtypes: 772 row.append(attrname) 773 else: 774 row.append(None) 775 matrix[attrname] = row 776 777 return matrix, all_objtypes, rsizes 778 779 def get_parameters_and_sizes(d): 780 781 """ 782 Return a matrix of parameters, a list of functions corresponding to columns 783 in the matrix, and a list of ranked sizes each indicating... 784 785 * a weighted size depending on the kind of object 786 * the minimum size of a parameter list employing a parameter 787 * the number of free columns in the matrix for the parameter 788 * the parameter name itself 789 790 This is a slightly simpler version of the above 'get_attributes_and_sizes' 791 function. 792 """ 793 794 params = {} 795 sizes = {} 796 797 for name, argnames in d.items(): 798 for argname in argnames: 799 800 # Record each function supporting the parameter. 801 802 init_item(params, argname, set) 803 params[argname].add(name) 804 805 # Maintain a record of the smallest parameter list supporting the 806 # given parameter. 807 808 if not sizes.has_key(argname): 809 sizes[argname] = len(argnames) 810 else: 811 sizes[argname] = min(sizes[argname], len(argnames)) 812 813 # Obtain attribute details in order of size and occupancy. 814 815 names = d.keys() 816 817 rsizes = [] 818 for argname, size in sizes.items(): 819 occupied = len(params[argname]) 820 key = (size, size, len(names) - occupied, argname) 821 rsizes.append(key) 822 823 rsizes.sort() 824 825 # Make a matrix of parameters. 826 827 matrix = {} 828 for argname, types in params.items(): 829 row = [] 830 for name in names: 831 if name in types: 832 row.append(argname) 833 else: 834 row.append(None) 835 matrix[argname] = row 836 837 return matrix, names, rsizes 838 839 def get_allocated_locations(d, fn, existing=None): 840 841 """ 842 Return a list where each element corresponds to a structure location and 843 contains a set of attribute names that may be stored at that location, given 844 a mapping 'd' whose keys are (object kind, object name) tuples and whose 845 values are collections of attributes. 846 """ 847 848 matrix, names, rsizes = fn(d) 849 allocated = [] 850 851 # Verify any existing allocation. 852 853 allocated_attrnames = set() 854 855 if existing: 856 for attrnames in existing: 857 858 # Handle empty positions. 859 860 if not attrnames: 861 allocated.append([None] * len(names)) 862 continue 863 864 base = None 865 866 for attrname in attrnames: 867 868 # Skip presumably-removed attribute names. 869 870 if not matrix.has_key(attrname): 871 continue 872 873 # Handle the first attribute name. 874 875 if base is None: 876 base = matrix[attrname] 877 allocated_attrnames.add(attrname) 878 continue 879 880 # Combine existing and new attribute positioning. 881 882 new = combine_rows(base, matrix[attrname]) 883 884 if new: 885 base = new 886 allocated_attrnames.add(attrname) 887 else: 888 raise OptimiseError, "Attribute %s cannot be explicitly positioned at %d." % \ 889 (attrname, len(allocated)) 890 891 # Handle empty positions. 892 893 if base: 894 allocated.append(base) 895 else: 896 allocated.append([None] * len(names)) 897 898 # Try to allocate each attribute name in turn. 899 900 x = 0 901 pos = 0 902 903 while x < len(rsizes): 904 905 # Obtain any previous allocation at the current position. Start at the 906 # current attribute looking for allocations to combine. 907 908 if pos < len(allocated): 909 base = allocated[pos] 910 free = base.count(None) 911 y = x 912 913 # Obtain the object information for the attribute name. 914 915 else: 916 weight, size, free, attrname = rsizes[x] 917 918 # Ignore allocated attribute names. 919 920 if attrname in allocated_attrnames: 921 x += 1 922 continue 923 924 # Start at the next attribute looking for allocations to combine. 925 926 base = matrix[attrname] 927 y = x + 1 928 929 # Examine attribute names that follow in the ranking, attempting to 930 # accumulate compatible attributes that can co-exist in the same 931 # position within structures. 932 933 while y < len(rsizes): 934 _weight, _size, _free, _attrname = rsizes[y] 935 936 # Ignore allocated attribute names. 937 938 if _attrname in allocated_attrnames: 939 y += 1 940 continue 941 942 # Determine whether this attribute is supported by too many types 943 # to co-exist. 944 945 occupied = len(names) - _free 946 if occupied > free: 947 break 948 949 # Merge the attribute support for both this and the currently 950 # considered attribute, testing for conflicts. Adopt the merged row 951 # details if they do not conflict. 952 953 new = combine_rows(base, matrix[_attrname]) 954 if new: 955 del matrix[_attrname] 956 del rsizes[y] 957 base = new 958 free -= occupied 959 960 # Otherwise, look for other compatible attributes. 961 962 else: 963 y += 1 964 965 # Allocate the merged details at the current position. 966 967 if pos < len(allocated): 968 allocated[pos] = base 969 pos += 1 970 else: 971 x += 1 972 allocated.append(base) 973 974 return allocations_to_sets(allocated) 975 976 def allocations_to_sets(allocated): 977 978 """ 979 Return the list of attribute names from each row of the 'allocated' 980 attributes table. 981 """ 982 983 locations = [] 984 985 for attrnames in allocated: 986 l = set() 987 988 # Convert populated allocations. 989 990 if attrnames: 991 for attrname in attrnames: 992 if attrname: 993 l.add(attrname) 994 995 locations.append(l) 996 997 return locations 998 999 # vim: tabstop=4 expandtab shiftwidth=4