Lichen

optimiser.py

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