# HG changeset patch
# User Paul Boddie <paul@boddie.org.uk>
# Date 1476196190 -7200
# Node ID 4dfeb117f7f90c192ff56b23b1fb244e3bb7fb7c
# Parent  068688ccb8187dbe6a69ab2ac3be3da35c8ff8b9
Introduced the optimiser module again, changing attribute access output to
employ an augmented version of the deducer's access plan format, adding
attribute ambiguity information.

diff -r 068688ccb818 -r 4dfeb117f7f9 lplc
--- a/lplc	Tue Oct 11 16:27:24 2016 +0200
+++ b/lplc	Tue Oct 11 16:29:50 2016 +0200
@@ -3,7 +3,7 @@
 from errors import *
 from os.path import abspath, exists, join, split
 from time import time
-import importer, deducer
+import importer, deducer, optimiser
 import sys
 
 libdirs = [
@@ -65,6 +65,11 @@
 
         now = stopwatch("Deduction", now)
 
+        o = optimiser.Optimiser(i, d, "_output")
+        o.to_output()
+
+        now = stopwatch("Optimisation", now)
+
     # Report any errors.
 
     except ProcessingError, exc:
diff -r 068688ccb818 -r 4dfeb117f7f9 optimiser.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/optimiser.py	Tue Oct 11 16:29:50 2016 +0200
@@ -0,0 +1,637 @@
+#!/usr/bin/env python
+
+"""
+Optimise object layouts.
+
+Copyright (C) 2014, 2015, 2016 Paul Boddie <paul@boddie.org.uk>
+
+This program is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free Software
+Foundation; either version 3 of the License, or (at your option) any later
+version.
+
+This program is distributed in the hope that it will be useful, but WITHOUT
+ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
+details.
+
+You should have received a copy of the GNU General Public License along with
+this program.  If not, see <http://www.gnu.org/licenses/>.
+"""
+
+from common import add_counter_item, get_attrname_from_location, init_item, \
+                   sorted_output
+from encoders import encode_access_location, get_kinds
+from os.path import exists, join
+from os import makedirs
+from referencing import Reference
+
+class Optimiser:
+
+    "Optimise objects in a program."
+
+    def __init__(self, importer, deducer, output):
+
+        """
+        Initialise an instance using the given 'importer' and 'deducer' that
+        will perform the arrangement of attributes for program objects, writing
+        the results to the given 'output' directory.
+        """
+
+        self.importer = importer
+        self.deducer = deducer
+        self.output = output
+
+        # Locations/offsets of attributes in objects.
+
+        self.locations = None
+        self.attr_locations = None
+        self.all_attrnames = None
+
+        # Locations of parameters in parameter tables.
+
+        self.arg_locations = None
+        self.param_locations = None
+        self.all_paramnames = None
+
+        # Specific attribute access information.
+
+        self.access_plans = {}
+
+        # Object structure information.
+
+        self.structures = {}
+        self.attr_table = {}
+
+        # Parameter list information.
+
+        self.parameters = {}
+        self.param_table = {}
+
+        # Constant literal information.
+
+        self.constants = []
+        self.constant_numbers = {}
+
+        # Optimiser activities.
+
+        self.populate_objects()
+        self.position_attributes()
+        self.populate_parameters()
+        self.position_parameters()
+        self.populate_tables()
+        self.populate_constants()
+        self.refine_access_plans()
+
+    def to_output(self):
+
+        "Write the output files using optimisation information."
+
+        if not exists(self.output):
+            makedirs(self.output)
+
+        self.write_objects()
+
+    def write_objects(self):
+
+        """
+        Write object-related output.
+
+        The locations are a list of positions indicating the attributes residing
+        at each position in the different structures in a program.
+
+        ----
+
+        The parameter locations are a list of positions indicating the parameters
+        residing at each position in the different parameter lists in a program.
+
+        ----
+
+        Each attribute plan provides attribute details in the following format:
+
+        location " " name " " test " " test type " " base
+                 " " traversed attributes " " traversed attribute ambiguity
+                 " " attributes to traverse " " attribute ambiguity
+                 " " context " " access method " " static attribute
+
+        Locations have the following format:
+
+        qualified name of scope "." local name ":" name version
+
+        ----
+
+        The structures are presented as a table in the following format:
+
+        qualified name " " attribute names
+
+        The attribute names are separated by ", " characters and indicate the
+        attribute provided at each position in the structure associated with the
+        given type. Where no attribute is provided at a particular location
+        within a structure, "-" is given.
+
+        ----
+
+        The parameters are presented as a table in the following format:
+
+        qualified name " " parameter details
+
+        The parameter details are separated by ", " characters and indicate
+        the parameter name and list position for each parameter described at
+        each location in the parameter table associated with the given
+        function. Where no parameter details are provided at a particular
+        location within a parameter table, "-" is given. The name and list
+        position are separated by a colon (":").
+
+        ----
+
+        The attribute table is presented as a table in the following format:
+
+        qualified name " " attribute identifiers
+
+        Instead of attribute names, identifiers defined according to the order
+        given in the "attrnames" file are employed to denote the attributes
+        featured in each type's structure. Where no attribute is provided at a
+        particular location within a structure, "-" is given.
+
+        ----
+
+        The parameter table is presented as a table in the following format:
+
+        qualified name " " parameter details
+
+        Instead of parameter names, identifiers defined according to the order
+        given in the "paramnames" file are employed to denote the parameters
+        featured in each function's parameter table. Where no parameter is
+        provided at a particular location within a table, "-" is given.
+
+        ----
+
+        The ordered list of attribute names is given in the "attrnames" file.
+
+        ----
+
+        The ordered list of parameter names is given in the "paramnames" file.
+
+        ----
+
+        The ordered list of constant literals is given in the "constants" file.
+        """
+
+        f = open(join(self.output, "locations"), "w")
+        try:
+            for attrnames in self.locations:
+                print >>f, sorted_output(attrnames)
+
+        finally:
+            f.close()
+
+        f = open(join(self.output, "parameter_locations"), "w")
+        try:
+            for argnames in self.arg_locations:
+                print >>f, sorted_output(argnames)
+
+        finally:
+            f.close()
+
+        f = open(join(self.output, "attribute_plans"), "w")
+        try:
+            access_plans = self.access_plans.items()
+            access_plans.sort()
+
+            for location, (name, test, test_type, base,
+                traversed, traversed_ambiguity,
+                attrnames, attrnames_ambiguity, context, method, attr) in access_plans:
+
+                print >>f, encode_access_location(location), \
+                           name, test, test_type or "{}", \
+                           base or "{}", \
+                           ".".join(traversed) or "{}", \
+                           ".".join(map(str, traversed_ambiguity)) or "{}", \
+                           ".".join(map(str, attrnames_ambiguity)) or "{}", \
+                           ".".join(attrnames) or "{}", \
+                           context, method, attr or "{}"
+
+        finally:
+            f.close()
+
+        f = open(join(self.output, "structures"), "w")
+        try:
+            structures = self.structures.items()
+            structures.sort()
+
+            for name, attrnames in structures:
+                print >>f, name, ", ".join([s or "-" for s in attrnames])
+
+        finally:
+            f.close()
+
+        f = open(join(self.output, "parameters"), "w")
+        try:
+            parameters = self.parameters.items()
+            parameters.sort()
+
+            for name, argnames in parameters:
+                print >>f, name, ", ".join([s and ("%s:%d" % s) or "-" for s in argnames])
+
+        finally:
+            f.close()
+
+        f = open(join(self.output, "attrtable"), "w")
+        try:
+            attr_table = self.attr_table.items()
+            attr_table.sort()
+
+            for name, attrcodes in attr_table:
+                print >>f, name, ", ".join([i is not None and str(i) or "-" for i in attrcodes])
+
+        finally:
+            f.close()
+
+        f = open(join(self.output, "paramtable"), "w")
+        try:
+            param_table = self.param_table.items()
+            param_table.sort()
+
+            for name, paramcodes in param_table:
+                print >>f, name, ", ".join([s and ("%d:%d" % s) or "-" for s in paramcodes])
+
+        finally:
+            f.close()
+
+        f = open(join(self.output, "attrnames"), "w")
+        try:
+            for name in self.all_attrnames:
+                print >>f, name
+
+        finally:
+            f.close()
+
+        f = open(join(self.output, "paramnames"), "w")
+        try:
+            for name in self.all_paramnames:
+                print >>f, name
+
+        finally:
+            f.close()
+
+        f = open(join(self.output, "constants"), "w")
+        try:
+            constants = [(n, value) for (value, n) in self.constants.items()]
+            constants.sort()
+            for n, value in constants:
+                print >>f, repr(value)
+
+        finally:
+            f.close()
+
+    def populate_objects(self):
+
+        "Populate objects using attribute and usage information."
+
+        all_attrs = {}
+
+        # Partition attributes into separate sections so that class and instance
+        # attributes are treated separately.
+
+        for source, objtype in [
+            (self.importer.all_class_attrs, "<class>"),
+            (self.importer.all_instance_attrs, "<instance>"),
+            (self.importer.all_module_attrs, "<module>")
+            ]:
+            for name, attrs in source.items():
+                all_attrs[(objtype, name)] = attrs
+
+        self.locations = get_allocated_locations(all_attrs, get_attributes_and_sizes)
+
+    def populate_parameters(self):
+
+        "Populate parameter tables using parameter information."
+
+        self.arg_locations = get_allocated_locations(self.importer.function_parameters, get_parameters_and_sizes)
+
+    def position_attributes(self):
+
+        "Position specific attribute references."
+
+        # Reverse the location mappings.
+
+        attr_locations = self.attr_locations = {}
+
+        for i, attrnames in enumerate(self.locations):
+            for attrname in attrnames:
+                attr_locations[attrname] = i
+
+        # Record the structures.
+
+        for source, objtype in [
+            (self.importer.all_class_attrs, "<class>"),
+            (self.importer.all_instance_attrs, "<instance>"),
+            (self.importer.all_module_attrs, "<module>")
+            ]:
+
+            for name, attrnames in source.items():
+                key = Reference(objtype, name)
+                l = self.structures[key] = [None] * len(attrnames)
+                for attrname in attrnames:
+                    position = attr_locations[attrname]
+                    if position >= len(l):
+                        l.extend([None] * (position - len(l) + 1))
+                    l[position] = attrname
+
+    def refine_access_plans(self):
+
+        "Augment deduced access plans with attribute position information."
+
+        for access_location, access_plan in self.deducer.access_plans.items():
+
+            # Obtain the access details.
+
+            name, test, test_type, base, traversed, attrnames, \
+                context, method, attr = access_plan
+
+            traversed_ambiguity = self.get_ambiguity_for_attributes(traversed)
+            attrnames_ambiguity = self.get_ambiguity_for_attributes(attrnames)
+
+            self.access_plans[access_location] = \
+                name, test, test_type, base, traversed, traversed_ambiguity, \
+                attrnames, attrnames_ambiguity, context, method, attr
+
+    def get_ambiguity_for_attributes(self, attrnames):
+
+        """
+        Return a list of attribute position alternatives corresponding to each
+        of the given 'attrnames'.
+        """
+
+        ambiguity = []
+
+        for attrname in attrnames:
+            position = self.attr_locations[attrname]
+            ambiguity.append(len(self.locations[position]))
+
+        return ambiguity
+
+    def position_parameters(self):
+
+        "Position the parameters for each function's parameter table."
+
+        # Reverse the location mappings.
+
+        param_locations = self.param_locations = {}
+
+        for i, argnames in enumerate(self.arg_locations):
+            for argname in argnames:
+                param_locations[argname] = i
+
+        for name, argnames in self.importer.function_parameters.items():
+            l = self.parameters[name] = [None] * len(argnames)
+
+            # Store an entry for the name along with the name's position in the
+            # parameter list.
+
+            for pos, argname in enumerate(argnames):
+                position = param_locations[argname]
+                if position >= len(l):
+                    l.extend([None] * (position - len(l) + 1))
+                l[position] = (argname, pos)
+
+    def populate_tables(self):
+
+        """
+        Assign identifiers to attributes and encode structure information using
+        these identifiers.
+        """
+
+        self.all_attrnames, d = self._get_name_mapping(self.attr_locations)
+
+        # Record the numbers indicating the locations of the names.
+
+        for key, attrnames in self.structures.items():
+            l = self.attr_table[key] = []
+            for attrname in attrnames:
+                if attrname is None:
+                    l.append(None)
+                else:
+                    l.append(d[attrname])
+
+        self.all_paramnames, d = self._get_name_mapping(self.param_locations)
+
+        # Record the numbers indicating the locations of the names.
+
+        for key, values in self.parameters.items():
+            l = self.param_table[key] = []
+            for value in values:
+                if value is None:
+                    l.append(None)
+                else:
+                    name, pos = value
+                    l.append((d[name], pos))
+
+    def _get_name_mapping(self, locations):
+
+        """
+        Get a sorted list of names from 'locations', then map them to
+        identifying numbers. Return the list and the mapping.
+        """
+
+        all_names = locations.keys()
+        all_names.sort()
+        return all_names, dict([(name, i) for i, name in enumerate(all_names)])
+
+    def populate_constants(self):
+
+        """
+        Obtain a collection of distinct constant literals, building a mapping
+        from constant references to those in this collection.
+        """
+
+        # Obtain mappings from constant values to identifiers.
+
+        self.constants = {}
+
+        for path, constants in self.importer.all_constants.items():
+            for constant, n in constants.items():
+
+                # Record constants and obtain a number for them.
+
+                add_counter_item(self.constants, constant)
+
+        self.constant_numbers = {}
+
+        for name, (value, value_type) in self.importer.all_constant_values.items():
+            self.constant_numbers[name] = self.constants[value]
+
+def combine_rows(a, b):
+    c = []
+    for i, j in zip(a, b):
+        if i is None or j is None:
+            c.append(i or j)
+        else:
+            return None
+    return c
+
+def get_attributes_and_sizes(d):
+
+    """
+    Return a matrix of attributes, a list of type names corresponding to columns
+    in the matrix, and a list of ranked sizes each indicating...
+
+     * a weighted size depending on the kind of object
+     * the minimum size of an object employing an attribute
+     * the number of free columns in the matrix for the attribute
+     * the attribute name itself
+    """
+
+    attrs = {}
+    sizes = {}
+    objtypes = {}
+
+    for name, attrnames in d.items():
+        objtype, _name = name
+
+        for attrname in attrnames:
+
+            # Record each type supporting the attribute.
+
+            init_item(attrs, attrname, set)
+            attrs[attrname].add(name)
+
+            # Maintain a record of the smallest object size supporting the given
+            # attribute.
+
+            if not sizes.has_key(attrname):
+                sizes[attrname] = len(attrnames)
+            else:
+                sizes[attrname] = min(sizes[attrname], len(attrnames))
+
+            # Record the object types/kinds supporting the attribute.
+
+            init_item(objtypes, attrname, set)
+            objtypes[attrname].add(objtype)
+
+    # Obtain attribute details in order of size and occupancy.
+
+    names = d.keys()
+
+    rsizes = []
+    for attrname, size in sizes.items():
+        priority = "<instance>" in objtypes[attrname] and 0.5 or 1
+        occupied = len(attrs[attrname])
+        key = (priority * size, size, len(names) - occupied, attrname)
+        rsizes.append(key)
+
+    rsizes.sort()
+
+    # Make a matrix of attributes.
+
+    matrix = {}
+    for attrname, types in attrs.items():
+        row = []
+        for name in names:
+            if name in types:
+                row.append(attrname)
+            else:
+                row.append(None)
+        matrix[attrname] = row
+
+    return matrix, names, rsizes
+
+def get_parameters_and_sizes(d):
+
+    """
+    Return a matrix of parameters, a list of functions corresponding to columns
+    in the matrix, and a list of ranked sizes each indicating...
+
+     * a weighted size depending on the kind of object
+     * the minimum size of a parameter list employing a parameter
+     * the number of free columns in the matrix for the parameter
+     * the parameter name itself
+
+    This is a slightly simpler version of the above 'get_attributes_and_sizes'
+    function.
+    """
+
+    params = {}
+    sizes = {}
+
+    for name, argnames in d.items():
+        for argname in argnames:
+
+            # Record each function supporting the parameter.
+
+            init_item(params, argname, set)
+            params[argname].add(name)
+
+            # Maintain a record of the smallest parameter list supporting the
+            # given parameter.
+
+            if not sizes.has_key(argname):
+                sizes[argname] = len(argnames)
+            else:
+                sizes[argname] = min(sizes[argname], len(argnames))
+
+    # Obtain attribute details in order of size and occupancy.
+
+    names = d.keys()
+
+    rsizes = []
+    for argname, size in sizes.items():
+        occupied = len(params[argname])
+        key = (size, size, len(names) - occupied, argname)
+        rsizes.append(key)
+
+    rsizes.sort()
+
+    # Make a matrix of parameters.
+
+    matrix = {}
+    for argname, types in params.items():
+        row = []
+        for name in names:
+            if name in types:
+                row.append(argname)
+            else:
+                row.append(None)
+        matrix[argname] = row
+
+    return matrix, names, rsizes
+
+def get_allocated_locations(d, fn):
+
+    """
+    Return a list where each element corresponds to a structure location and
+    contains a set of attribute names that may be stored at that location, given
+    a mapping 'd' whose keys are (object type, object name) tuples and whose
+    values are collections of attributes.
+    """
+
+    matrix, names, rsizes = fn(d)
+    allocated = []
+
+    x = 0
+    while x < len(rsizes):
+        weight, size, free, attrname = rsizes[x]
+        base = matrix[attrname]
+        y = x + 1
+        while y < len(rsizes):
+            _weight, _size, _free, _attrname = rsizes[y]
+            occupied = len(names) - _free
+            if occupied > free:
+                break
+            new = combine_rows(base, matrix[_attrname])
+            if new:
+                del matrix[_attrname]
+                del rsizes[y]
+                base = new
+                free -= occupied
+            else:
+                y += 1
+        allocated.append(base)
+        x += 1
+
+    # Return the list of attribute names from each row of the allocated
+    # attributes table.
+
+    return [set([attrname for attrname in attrnames if attrname]) for attrnames in allocated]
+
+# vim: tabstop=4 expandtab shiftwidth=4