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 try: 462 self.arg_locations = [set()] + get_allocated_locations( 463 self.importer.function_parameters, get_parameters_and_sizes, 464 self.existing_arg_locations[1:]) 465 466 # Uphold positioning conflicts only if the existing locations were 467 # explicitly specified. 468 469 except OptimiseError: 470 if self.parameter_locations_filename: 471 raise 472 473 # Otherwise, reposition parameters, causing the program to be 474 # regenerated. 475 476 self.arg_locations = [set()] + get_allocated_locations( 477 self.importer.function_parameters, get_parameters_and_sizes) 478 479 def position_attributes(self): 480 481 "Position specific attribute references." 482 483 # Reverse the location mappings, producing a mapping from attribute 484 # names to positions. 485 486 attr_locations = self.attr_locations = {} 487 self._position_attributes(attr_locations, self.locations) 488 489 # Add any previously-known attribute locations. This prevents attributes 490 # from being assigned different identifying codes by preserving obsolete 491 # attribute codes. 492 493 if self.existing_locations: 494 self._position_attributes(attr_locations, self.existing_locations) 495 496 # Record the structures. 497 498 for (objkind, name), attrnames in self.all_attrs.items(): 499 key = Reference(objkind, name) 500 l = self.structures[key] = [None] * len(attrnames) 501 502 for attrname in attrnames: 503 position = attr_locations[attrname] 504 if position >= len(l): 505 l.extend([None] * (position - len(l) + 1)) 506 l[position] = attrname 507 508 # Test the structure against any existing attributes. 509 510 if self.existing_structures: 511 if self.existing_structures.has_key(key) and self.existing_structures[key] != l: 512 self.differing_structures.append(key) 513 514 def _position_attributes(self, d, l): 515 516 """ 517 For each attribute, store a mapping in 'd' to the index in 'l' at which 518 it can be found. 519 """ 520 521 for i, attrnames in enumerate(l): 522 for attrname in attrnames: 523 if not d.has_key(attrname): 524 d[attrname] = i 525 526 def get_ambiguity_for_attributes(self, attrnames): 527 528 """ 529 Return a list of attribute position alternatives corresponding to each 530 of the given 'attrnames'. 531 """ 532 533 ambiguity = [] 534 535 for attrname in attrnames: 536 position = self.attr_locations[attrname] 537 ambiguity.append(len(self.locations[position])) 538 539 return ambiguity 540 541 def position_parameters(self): 542 543 "Position the parameters for each function's parameter table." 544 545 # Reverse the location mappings, producing a mapping from parameter 546 # names to positions. 547 548 param_locations = self.param_locations = {} 549 self._position_attributes(param_locations, self.arg_locations) 550 551 for name, argnames in self.importer.function_parameters.items(): 552 553 # Allocate an extra context parameter in the table. 554 555 l = self.parameters[name] = [None] + [None] * len(argnames) 556 557 # Store an entry for the name along with the name's position in the 558 # parameter list. 559 560 for pos, argname in enumerate(argnames): 561 562 # Position the argument in the table. 563 564 position = param_locations[argname] 565 if position >= len(l): 566 l.extend([None] * (position - len(l) + 1)) 567 568 # Indicate an argument list position starting from 1 (after the 569 # initial context argument). 570 571 l[position] = (argname, pos + 1) 572 573 # Test the structure against any existing parameters. 574 575 if self.existing_parameters: 576 if self.existing_parameters.has_key(name) and self.existing_parameters[name] != l: 577 self.differing_parameters.append(name) 578 579 def populate_tables(self): 580 581 """ 582 Assign identifiers to attributes and encode structure information using 583 these identifiers. 584 """ 585 586 # Initialise the mapping from attribute names to codes. 587 588 l = self.all_attrnames = []; d = {} 589 self._init_name_mapping(l, d, self.existing_attrnames) 590 if self.indicated_attrnames: 591 self._init_name_mapping(l, d, self.indicated_attrnames) 592 self._update_name_mapping(l, d, self.attr_locations) 593 594 # Record the numbers indicating the locations of the names. 595 596 for key, attrnames in self.structures.items(): 597 l = self.attr_table[key] = [] 598 for attrname in attrnames: 599 if attrname is None: 600 l.append(None) 601 else: 602 l.append(d[attrname]) 603 604 # Initialise the mapping from parameter names to codes. 605 606 l = self.all_paramnames = []; d = {} 607 self._init_name_mapping(l, d, self.existing_paramnames) 608 if self.indicated_paramnames: 609 self._init_name_mapping(l, d, self.indicated_paramnames) 610 self._update_name_mapping(l, d, self.param_locations) 611 612 # Record the numbers indicating the locations of the names. 613 614 for key, values in self.parameters.items(): 615 l = self.param_table[key] = [] 616 for value in values: 617 if value is None: 618 l.append(None) 619 else: 620 name, pos = value 621 l.append((d[name], pos)) 622 623 def _init_name_mapping(self, l, d, existing): 624 625 """ 626 Initialise the name collection 'l', with mapping 'd', using the 627 'existing' mapping. 628 """ 629 630 i = 0 631 632 for name in existing: 633 634 # Test for the name in another position. 635 636 if d.has_key(name): 637 if d[name] != i: 638 raise OptimiseError, "Name %s has conflicting codes: %d and %d." % \ 639 (name, d[name], i) 640 else: 641 642 # Test for other usage of the position. 643 644 if i < len(l): 645 if l[i] != name: 646 raise OptimiseError, "Position %d has conflicting names: %s and %s." % \ 647 (i, name, d[name]) 648 l[i] = name 649 else: 650 l.append(name) 651 652 d[name] = i 653 654 i += 1 655 656 def _update_name_mapping(self, l, d, locations): 657 658 """ 659 Using any existing identifiers supplied by 'l' and 'd', update the 660 identifiers using a sorted list of names from 'locations'. 661 """ 662 663 all_names = list(locations.keys()) 664 all_names.sort() 665 666 i = len(l) 667 668 for name in all_names: 669 if not d.has_key(name): 670 d[name] = i 671 l.append(name) 672 i += 1 673 674 def populate_constants(self): 675 676 """ 677 Obtain a collection of distinct constant literals, building a mapping 678 from constant references to those in this collection. 679 """ 680 681 # Obtain mappings from constant values to identifiers. 682 683 self.constants = {} 684 685 # Establish a mapping from local constant identifiers to consolidated 686 # constant identifiers. 687 688 self.constant_numbers = {} 689 690 for name, constant in self.importer.all_constant_values.items(): 691 692 # Each constant is actually (value, value_type, encoding). 693 694 d = digest(constant) 695 self.constants[constant] = d 696 697 # Make sure the digests are really distinct for different 698 # constants. 699 700 if self.digests.has_key(d): 701 if self.digests[d] != constant: 702 raise OptimiseError, "Digest %s used for distinct constants %r and %r." % ( 703 d, self.digests[d], constant) 704 else: 705 self.digests[d] = constant 706 707 self.constant_numbers[name] = self.constants[constant] 708 709 def combine_rows(a, b): 710 c = [] 711 for i, j in zip(a, b): 712 if i is None or j is None: 713 c.append(i or j) 714 else: 715 return None 716 return c 717 718 def get_attributes_and_sizes(d): 719 720 """ 721 Get attribute and size information for the object attributes defined by 'd' 722 providing a mapping from (object kind, type name) to attribute names. 723 724 Return a matrix of attributes (each row entry consisting of column values 725 providing attribute names, with value positions corresponding to types 726 providing such attributes), a list of the type names corresponding to the 727 columns in the matrix, and a list of ranked sizes each indicating... 728 729 * a weighted size depending on the kind of object 730 * the minimum size of an object employing an attribute 731 * the number of free columns in the matrix for the attribute 732 * the attribute name itself 733 """ 734 735 attrs = {} 736 sizes = {} 737 objkinds = {} 738 739 for objtype, attrnames in d.items(): 740 objkind, _name = objtype 741 742 for attrname in attrnames: 743 744 # Record each type supporting the attribute. 745 746 init_item(attrs, attrname, set) 747 attrs[attrname].add(objtype) 748 749 # Maintain a record of the smallest object size supporting the given 750 # attribute. 751 752 if not sizes.has_key(attrname): 753 sizes[attrname] = len(attrnames) 754 else: 755 sizes[attrname] = min(sizes[attrname], len(attrnames)) 756 757 # Record the object types/kinds supporting the attribute. 758 759 init_item(objkinds, attrname, set) 760 objkinds[attrname].add(objkind) 761 762 # Obtain attribute details in order of size and occupancy. 763 764 all_objtypes = d.keys() 765 766 rsizes = [] 767 for attrname, size in sizes.items(): 768 priority = "<instance>" in objkinds[attrname] and 0.5 or 1 769 occupied = len(attrs[attrname]) 770 key = (priority * size, size, len(all_objtypes) - occupied, attrname) 771 rsizes.append(key) 772 773 rsizes.sort() 774 775 # Make a matrix of attributes. 776 777 matrix = {} 778 for attrname, objtypes in attrs.items(): 779 780 # Traverse the object types, adding the attribute name if the object 781 # type supports the attribute, adding None otherwise. 782 783 row = [] 784 for objtype in all_objtypes: 785 if objtype in objtypes: 786 row.append(attrname) 787 else: 788 row.append(None) 789 matrix[attrname] = row 790 791 return matrix, all_objtypes, rsizes 792 793 def get_parameters_and_sizes(d): 794 795 """ 796 Return a matrix of parameters, a list of functions corresponding to columns 797 in the matrix, and a list of ranked sizes each indicating... 798 799 * a weighted size depending on the kind of object 800 * the minimum size of a parameter list employing a parameter 801 * the number of free columns in the matrix for the parameter 802 * the parameter name itself 803 804 This is a slightly simpler version of the above 'get_attributes_and_sizes' 805 function. 806 """ 807 808 params = {} 809 sizes = {} 810 811 for name, argnames in d.items(): 812 for argname in argnames: 813 814 # Record each function supporting the parameter. 815 816 init_item(params, argname, set) 817 params[argname].add(name) 818 819 # Maintain a record of the smallest parameter list supporting the 820 # given parameter. 821 822 if not sizes.has_key(argname): 823 sizes[argname] = len(argnames) 824 else: 825 sizes[argname] = min(sizes[argname], len(argnames)) 826 827 # Obtain attribute details in order of size and occupancy. 828 829 names = d.keys() 830 831 rsizes = [] 832 for argname, size in sizes.items(): 833 occupied = len(params[argname]) 834 key = (size, size, len(names) - occupied, argname) 835 rsizes.append(key) 836 837 rsizes.sort() 838 839 # Make a matrix of parameters. 840 841 matrix = {} 842 for argname, types in params.items(): 843 row = [] 844 for name in names: 845 if name in types: 846 row.append(argname) 847 else: 848 row.append(None) 849 matrix[argname] = row 850 851 return matrix, names, rsizes 852 853 def get_allocated_locations(d, fn, existing=None): 854 855 """ 856 Return a list where each element corresponds to a structure location and 857 contains a set of attribute names that may be stored at that location, given 858 a mapping 'd' whose keys are (object kind, object name) tuples and whose 859 values are collections of attributes. 860 """ 861 862 matrix, names, rsizes = fn(d) 863 allocated = [] 864 865 # Verify any existing allocation. 866 867 allocated_attrnames = set() 868 869 if existing: 870 for attrnames in existing: 871 872 # Handle empty positions. 873 874 if not attrnames: 875 allocated.append([None] * len(names)) 876 continue 877 878 base = None 879 880 for attrname in attrnames: 881 882 # Skip presumably-removed attribute names. 883 884 if not matrix.has_key(attrname): 885 continue 886 887 # Handle the first attribute name. 888 889 if base is None: 890 base = matrix[attrname] 891 allocated_attrnames.add(attrname) 892 continue 893 894 # Combine existing and new attribute positioning. 895 896 new = combine_rows(base, matrix[attrname]) 897 898 if new: 899 base = new 900 allocated_attrnames.add(attrname) 901 else: 902 raise OptimiseError, "Attribute %s cannot be explicitly positioned at %d." % \ 903 (attrname, len(allocated)) 904 905 # Handle empty positions. 906 907 if base: 908 allocated.append(base) 909 else: 910 allocated.append([None] * len(names)) 911 912 # Try to allocate each attribute name in turn. 913 914 x = 0 915 pos = 0 916 917 while x < len(rsizes): 918 919 # Obtain any previous allocation at the current position. Start at the 920 # current attribute looking for allocations to combine. 921 922 if pos < len(allocated): 923 base = allocated[pos] 924 free = base.count(None) 925 y = x 926 927 # Obtain the object information for the attribute name. 928 929 else: 930 weight, size, free, attrname = rsizes[x] 931 932 # Ignore allocated attribute names. 933 934 if attrname in allocated_attrnames: 935 x += 1 936 continue 937 938 # Start at the next attribute looking for allocations to combine. 939 940 base = matrix[attrname] 941 y = x + 1 942 943 # Examine attribute names that follow in the ranking, attempting to 944 # accumulate compatible attributes that can co-exist in the same 945 # position within structures. 946 947 while y < len(rsizes): 948 _weight, _size, _free, _attrname = rsizes[y] 949 950 # Ignore allocated attribute names. 951 952 if _attrname in allocated_attrnames: 953 y += 1 954 continue 955 956 # Determine whether this attribute is supported by too many types 957 # to co-exist. 958 959 occupied = len(names) - _free 960 if occupied > free: 961 break 962 963 # Merge the attribute support for both this and the currently 964 # considered attribute, testing for conflicts. Adopt the merged row 965 # details if they do not conflict. 966 967 new = combine_rows(base, matrix[_attrname]) 968 if new: 969 del matrix[_attrname] 970 del rsizes[y] 971 base = new 972 free -= occupied 973 974 # Otherwise, look for other compatible attributes. 975 976 else: 977 y += 1 978 979 # Allocate the merged details at the current position. 980 981 if pos < len(allocated): 982 allocated[pos] = base 983 pos += 1 984 else: 985 x += 1 986 allocated.append(base) 987 988 return allocations_to_sets(allocated) 989 990 def allocations_to_sets(allocated): 991 992 """ 993 Return the list of attribute names from each row of the 'allocated' 994 attributes table. 995 """ 996 997 locations = [] 998 999 for attrnames in allocated: 1000 l = set() 1001 1002 # Convert populated allocations. 1003 1004 if attrnames: 1005 for attrname in attrnames: 1006 if attrname: 1007 l.add(attrname) 1008 1009 locations.append(l) 1010 1011 return locations 1012 1013 # vim: tabstop=4 expandtab shiftwidth=4