Lichen

optimiser.py

785:1f07b0aa675e
2017-03-26 Paul Boddie Simplified the tuple instantiator.
     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