Lichen

optimiser.py

821:ed27b57be1df
2018-01-15 Paul Boddie Introduced parameter-based attribute initialisation for broader testing.
     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