Merge remote-tracking branch 'github-privat/master'

[nit.git] / src / coloring.nit

# This file is part of NIT ( http://www.nitlanguage.org ).
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

# Graph coloring tools
module coloring

import rapid_type_analysis # for type coloration

abstract class AbstractColoring[E: Object]

        private var sorter: AbstractSorter[E]
        private var reverse_sorter: AbstractSorter[E]

        private var core: OrderedSet[E] = new OrderedSet[E]
        private var crown: OrderedSet[E] = new OrderedSet[E]
        private var border: OrderedSet[E] = new OrderedSet[E]

        private var coloration_result: Map[E, Int] = new HashMap[E, Int]
        private var conflicts_graph_cache: nullable HashMap[E, Set[E]]

        init(sorter: AbstractSorter[E], reverse_sorter: AbstractSorter[E]) do
                self.sorter = sorter
                self.reverse_sorter = reverse_sorter
        end

        fun colorize(elements: Collection[E]): Map[E, Int] do
                # tag each element as part of group core, crown or border
                for e in elements do
                        tag_element(e)
                end

                #print "core: {core.join(", ")}"
                #print "border: {border.join(", ")}"
                #print "crown: {crown.join(", ")}"

                # sort by reverse linearization order
                reverse_sorter.sort(core)
                reverse_sorter.sort(border)
                reverse_sorter.sort(crown)

                #print "conflicts"
                #for k, v in conflicts_graph do
                #       if k isa MType then
                #               print "{k}: {v.join(", ")}"
                #       end
                #end

                # colorize graph
                colorize_elements(core)
                colorize_elements(border)
                colorize_elements(crown)

                return coloration_result
        end

        # Colorize a collection of elements
        private fun colorize_elements(elements: Collection[E]) do
                var min_color = 0

                for element in elements do
                        var color = min_color
                        while not self.is_color_free(element, color) do
                                color += 1
                        end
                        coloration_result[element] = color
                        color = min_color
                end
        end

        # Check if a related element to the element already use the color
        private fun is_color_free(element: E, color: Int): Bool do
                if conflicts_graph.has_key(element) then
                        for st in conflicts_graph[element] do
                                if coloration_result.has_key(st) and coloration_result[st] == color then return false
                        end
                end
                for st in self.super_elements(element) do
                        if coloration_result.has_key(st) and coloration_result[st] == color then return false
                end
                return true
        end

        # Tag element as core, crown or border
        private fun tag_element(element: E) do
                # Check if sub elements are all in single inheritance
                var all_subelements_si = true
                for subelem in self.sub_elements(element) do
                        if self.is_element_mi(subelem) then
                                all_subelements_si = false
                                break
                        end
                end

                # Tag as core, crown or border
                if self.is_element_mi(element) then
                        core.add_all(self.super_elements(element))
                        core.add(element)
                        if all_subelements_si then
                                border.add(element)
                        end
                else if not all_subelements_si then
                        core.add_all(self.super_elements(element))
                        core.add(element)
                else
                        crown.add(element)
                end
        end

        # Conflicts graph of elements hierarchy (two types are in conflict if they have common subelements)
        private fun conflicts_graph: Map[E, Set[E]] do
                if self.conflicts_graph_cache == null then
                        self.conflicts_graph_cache = new HashMap[E, HashSet[E]]
                        for t in self.core do
                                for i in self.linear_extension(t) do
                                        if t == i then continue

                                        var lin_i = self.linear_extension(i)

                                        for j in self.linear_extension(t) do
                                                if i == j or j == t then continue
                                                var lin_j = self.linear_extension(j)

                                                var d_ij = lin_i - lin_j
                                                var d_ji = lin_j - lin_i

                                                for ed1 in d_ij do
                                                        if not conflicts_graph_cache.has_key(ed1) then conflicts_graph_cache[ed1] = new HashSet[E]
                                                        # add ed1 x ed2 to conflicts graph
                                                        for ed2 in d_ji do conflicts_graph_cache[ed1].add(ed2)
                                                end
                                                for ed1 in d_ij do
                                                        if not conflicts_graph_cache.has_key(ed1) then conflicts_graph_cache[ed1] = new HashSet[E]
                                                        # add ed1 x ed2 to conflicts graph
                                                        for ed2 in d_ji do conflicts_graph_cache[ed1].add(ed2)
                                                end
                                        end
                                end
                        end
                end
                return conflicts_graph_cache.as(not null)
        end

        # cache for linear_extensions
        private var linear_extensions_cache: Map[E, OrderedSet[E]] = new HashMap[E, OrderedSet[E]]

        # Return a linear_extension of super_elements of the element
        private fun linear_extension(element: E): OrderedSet[E] do
                if not self.linear_extensions_cache.has_key(element) then
                        var lin = new OrderedSet[E]
                        lin.add(element)
                        lin.add_all(self.super_elements(element))
                        self.sorter.sort(lin)
                        self.linear_extensions_cache[element] = lin
                end
                return self.linear_extensions_cache[element]
        end

        # Return all super elements (directs and indirects) of an element
        private fun super_elements(element: E): Collection[E] is abstract

        # Return all sub elements (directs and indirects) of an element
        private fun sub_elements(element: E): Collection[E] is abstract

        # Is the element in multiple inheritance ?
        private fun is_element_mi(element: E): Bool is abstract
end

# MClassType coloring
class TypeColoring
        super AbstractColoring[MType]

        type T: MType

        private var mmodule: MModule
        private var mtypes: Set[T]

        # caches
        private var super_elements_cache: Map[T, Set[T]] = new HashMap[T, Set[T]]
        private var sub_elements_cache: Map[T, Set[T]] = new HashMap[T, Set[T]]

        init(mainmodule: MModule, mtypes: Set[T]) do
                super(new TypeSorter(mainmodule), new ReverseTypeSorter(mainmodule))
                self.mmodule = mainmodule
                self.mtypes = mtypes
        end

        # Build type tables
        fun build_type_tables(mtypes: Set[T], colors: Map[T, Int]): Map[T, Array[nullable T]] do
                var tables = new HashMap[T, Array[nullable T]]

                for mtype in mtypes do
                        var table = new Array[nullable T]
                        var supers = new HashSet[T]
                        supers.add_all(self.super_elements(mtype))
                        supers.add(mtype)
                        for sup in supers do
                                var color = colors[sup]
                                if table.length <= color then
                                        for i in [table.length .. color[ do
                                                table[i] = null
                                        end
                                end
                                table[color] = sup
                        end
                        tables[mtype] = table
                end
                return tables
        end

        redef fun super_elements(element) do
                if not self.super_elements_cache.has_key(element) then
                        var supers = new HashSet[T]
                        for mtype in self.mtypes do
                                if element == mtype then continue
                                if element.is_subtype(self.mmodule, null, mtype) then
                                        supers.add(mtype)
                                end
                        end
                        self.super_elements_cache[element] = supers
                end
                return self.super_elements_cache[element]
        end

        # Return all direct super elements of an element
        redef fun is_element_mi(element) do
                return self.super_elements(element).length > 1
        end

        # Return all sub elements (directs and indirects) of an element
        redef fun sub_elements(element) do
                if not self.sub_elements_cache.has_key(element) then
                        var subs = new HashSet[T]
                        for mtype in self.mtypes do
                                if element == mtype then continue
                                if mtype.is_subtype(self.mmodule, null, element) then
                                        subs.add(mtype)
                                end
                        end
                        self.sub_elements_cache[element] = subs
                end
                return self.sub_elements_cache[element]
        end
end

class NaiveTypeColoring
        super TypeColoring

        init(mainmodule: MModule, mtypes: Set[T]) do
                super(mainmodule, mtypes)
        end

        # naive coloring that use incremental coloring
        redef fun colorize_elements(elements) do
                for e in elements do
                        self.coloration_result[e] = self.coloration_result.length
                end
        end
end

abstract class TypePerfectHashing
        super TypeColoring

        init(mainmodule: MModule, mtypes: Set[T]) do
                super(mainmodule, mtypes)
        end

        fun compute_masks(elements: Set[T], ids: Map[T, Int]): Map[T, Int] do
                for e in elements do
                        # Create super type list
                        var supers = new HashSet[T]
                        supers.add_all(self.super_elements(e))
                        supers.add(e)
                        # Compute the hashing 'mask'
                        self.coloration_result[e] = compute_mask(supers, ids)
                end
                return self.coloration_result
        end

        # Build type tables
        fun hash_type_tables(mtypes: Set[T], ids: Map[T, Int], masks: Map[T, Int]): Map[T, Array[nullable T]] do
                var tables = new HashMap[T, Array[nullable T]]

                for mtype in mtypes do
                        var table = new Array[nullable T]
                        var supers = new HashSet[T]
                        supers.add_all(self.super_elements(mtype))
                        supers.add(mtype)

                        for sup in supers do
                                var color = phash(ids[sup], masks[mtype])
                                if table.length <= color then
                                        for i in [table.length .. color[ do
                                                table[i] = null
                                        end
                                end
                                table[color] = sup
                        end
                        tables[mtype] = table
                end
                return tables
        end

        private fun compute_mask(mtypes: Set[T], ids: Map[T, Int]): Int do
                var mask = 0
                loop
                        var used = new List[Int]
                        for sup in mtypes do
                                var res = op(mask, ids[sup])
                                if used.has(res) then
                                        break
                                else
                                        used.add(res)
                                end
                        end
                        if used.length == mtypes.length then break
                        mask += 1
                end
                return mask
        end

        private fun op(mask: Int, id:Int): Int is abstract
        private fun phash(id: Int, mask: Int): Int do return op(mask, id)
end

class TypeModPerfectHashing
        super TypePerfectHashing
        init(mainmodule: MModule, mtypes: Set[T]) do
                super(mainmodule, mtypes)
        end
        redef fun op(mask, id) do return mask % id
end

class TypeAndPerfectHashing
        super TypePerfectHashing
        init(mainmodule: MModule, mtypes: Set[T]) do
                super(mainmodule, mtypes)
        end
        redef fun op(mask, id) do return mask.bin_and(id)
end

# A sorter for linearize list of types
class TypeSorter
        super AbstractSorter[MType]

        private var mmodule: MModule

        init(mmodule: MModule) do self.mmodule = mmodule

        redef fun compare(a, b) do
                if a == b then
                        return 0
                else if a.is_subtype(self.mmodule, null, b) then
                        return -1
                end
                return 1
        end
end

# A sorter for reverse linearization
class ReverseTypeSorter
        super TypeSorter

        init(mmodule: MModule) do end

        redef fun compare(a, b) do
                if a == b then
                        return 0
                else if a.is_subtype(self.mmodule, null, b) then
                        return 1
                end
                return -1
        end
end

# MClass coloring
class ClassColoring
        super AbstractColoring[MClass]

        type T: MClass

        private var mmodule: MModule

        # caches
        private var super_elements_cache: Map[T, Set[T]] = new HashMap[T, Set[T]]
        private var parent_elements_cache: Map[T, Set[T]] = new HashMap[T, Set[T]]
        private var sub_elements_cache: Map[T, Set[T]] = new HashMap[T, Set[T]]

        init(mainmodule: MModule) do
                super(new ClassSorter(mainmodule), new ReverseClassSorter(mainmodule))
                self.mmodule = mainmodule
        end

        # Build type tables
        fun build_type_tables(mclasses: Array[T], colors: Map[T, Int]): Map[T, Array[nullable T]] do
                var tables = new HashMap[T, Array[nullable T]]

                for mclasse in mclasses do
                        var table = new Array[nullable T]
                        var supers = new HashSet[T]
                        supers.add_all(self.super_elements(mclasse))
                        supers.add(mclasse)
                        for sup in supers do
                                var color = colors[sup]
                                if table.length <= color then
                                        for i in [table.length .. color[ do
                                                table[i] = null
                                        end
                                end
                                table[color] = sup
                        end
                        tables[mclasse] = table
                end
                return tables
        end

        redef fun super_elements(element) do
                if not self.super_elements_cache.has_key(element) then
                        var supers = new HashSet[T]
                        if self.mmodule.flatten_mclass_hierarchy.has(element) then
                                for sup in self.mmodule.flatten_mclass_hierarchy[element].greaters do
                                        if element == sup then continue
                                        supers.add(sup)
                                end
                        end
                        self.super_elements_cache[element] = supers
                end
                return self.super_elements_cache[element]
        end

        private fun parent_elements(element: T): Set[T] do
                if not self.parent_elements_cache.has_key(element) then
                        var parents = new HashSet[T]
                        if self.mmodule.flatten_mclass_hierarchy.has(element) then
                                for parent in self.mmodule.flatten_mclass_hierarchy[element].direct_greaters do
                                        if element == parent then continue
                                        parents.add(parent)
                                end
                        end
                        self.parent_elements_cache[element] = parents
                end
                return self.parent_elements_cache[element]
        end

        # Return all sub elements (directs and indirects) of an element
        redef fun sub_elements(element) do
                if not self.sub_elements_cache.has_key(element) then
                        var subs = new HashSet[T]
                        if self.mmodule.flatten_mclass_hierarchy.has(element) then
                                for sub in self.mmodule.flatten_mclass_hierarchy[element].smallers do
                                        subs.add(sub)
                                end
                        end
                        self.sub_elements_cache[element] = subs
                end
                return self.sub_elements_cache[element]
        end

        # Return all direct super elements of an element
        redef fun is_element_mi(element) do
                if not self.mmodule.flatten_mclass_hierarchy.has(element) then return false
                return self.mmodule.flatten_mclass_hierarchy[element].direct_greaters.length > 1
        end
end

# incremental coloring (very naive)
class NaiveClassColoring
        super ClassColoring

        init(mainmodule: MModule) do
                super(mainmodule)
        end

        # naive coloring that use incremental coloring
        redef fun colorize_elements(elements: Collection[MClass]) do
                for e in elements do
                        self.coloration_result[e] = self.coloration_result.length
                end
        end
end

abstract class ClassPerfectHashing
        super ClassColoring

        init(mainmodule: MModule) do
                super(mainmodule)
        end

        fun compute_masks(elements: Set[T], ids: Map[T, Int]): Map[T, Int] do
                for e in elements do
                        # Create super type list
                        var supers = new HashSet[T]
                        supers.add_all(self.super_elements(e))
                        supers.add(e)
                        # Compute the hashing 'mask'
                        self.coloration_result[e] = compute_mask(supers, ids)
                end
                return self.coloration_result
        end

        # Build type tables
        fun hash_type_tables(mtypes: Set[T], ids: Map[T, Int], masks: Map[T, Int]): Map[T, Array[nullable T]] do
                var tables = new HashMap[T, Array[nullable T]]

                for mtype in mtypes do
                        var table = new Array[nullable T]
                        var supers = new HashSet[T]
                        supers.add_all(self.super_elements(mtype))
                        supers.add(mtype)

                        for sup in supers do
                                var color = phash(ids[sup], masks[mtype])
                                if table.length <= color then
                                        for i in [table.length .. color[ do
                                                table[i] = null
                                        end
                                end
                                table[color] = sup
                        end
                        tables[mtype] = table
                end
                return tables
        end

        private fun compute_mask(mtypes: Set[T], ids: Map[T, Int]): Int do
                var mask = 0
                loop
                        var used = new List[Int]
                        for sup in mtypes do
                                var res = op(mask, ids[sup])
                                if used.has(res) then
                                        break
                                else
                                        used.add(res)
                                end
                        end
                        if used.length == mtypes.length then break
                        mask += 1
                end
                return mask
        end

        private fun op(mask: Int, id:Int): Int is abstract
        private fun phash(id: Int, mask: Int): Int do return op(mask, id)
end

class ClassModPerfectHashing
        super ClassPerfectHashing
        init(mainmodule: MModule) do
                super(mainmodule)
        end
        redef fun op(mask, id) do return mask % id
end

class ClassAndPerfectHashing
        super ClassPerfectHashing
        init(mainmodule: MModule) do
                super(mainmodule)
        end
        redef fun op(mask, id) do return mask.bin_and(id)
end

# A sorter for linearize list of classes
private class ClassSorter
        super AbstractSorter[MClass]

        var mmodule: MModule

        redef fun compare(a, b) do
                if a == b then
                        return 0
                else if self.mmodule.flatten_mclass_hierarchy.has(a) and self.mmodule.flatten_mclass_hierarchy[a].greaters.has(b) then
                        return -1
                end
                return 1
        end
end

# A sorter for reverse linearization
private class ReverseClassSorter
        super AbstractSorter[MClass]

        var mmodule: MModule

        redef fun compare(a, b) do
                if a == b then
                        return 0
                else if self.mmodule.flatten_mclass_hierarchy.has(a) and self.mmodule.flatten_mclass_hierarchy[a].greaters.has(b) then
                        return 1
                end
                return -1
        end
end

# MProperty coloring
class PropertyColoring

        type MPROP: MProperty
        type MPROPDEF: MPropDef

        private var class_coloring: ClassColoring
        private var coloration_result: Map[MPROP, Int] = new HashMap[MPROP, Int]

        init(class_coloring: ClassColoring) do
                self.class_coloring = class_coloring
        end

        fun colorize: Map[MPROP, Int] do
                colorize_core_properties
                colorize_crown_properties
                return self.coloration_result
        end

        fun build_property_tables: Map[MClass, Array[nullable MPROPDEF]] do
                var tables = new HashMap[MClass, Array[nullable MPROPDEF]]

                for mclass in self.class_coloring.coloration_result.keys do
                        var table = new Array[nullable MPROPDEF]
                        # first, fill table from parents by reverse linearization order
                        var parents = new OrderedSet[MClass]
                        parents.add_all(self.class_coloring.super_elements(mclass))
                        self.class_coloring.reverse_sorter.sort(parents)
                        for parent in parents do
                                for mproperty in self.properties(parent) do
                                        var color = self.coloration_result[mproperty]
                                        if table.length <= color then
                                                for i in [table.length .. color[ do
                                                        table[i] = null
                                                end
                                        end
                                        for mpropdef in mproperty.mpropdefs do
                                                if mpropdef.mclassdef.mclass == parent then
                                                        table[color] = mpropdef
                                                end
                                        end
                                end
                        end

                        # then override with local properties
                        for mproperty in self.properties(mclass) do
                                var color = self.coloration_result[mproperty]
                                if table.length <= color then
                                        for i in [table.length .. color[ do
                                                table[i] = null
                                        end
                                end
                                for mpropdef in mproperty.mpropdefs do
                                        if mpropdef.mclassdef.mclass == mclass then
                                                table[color] = mpropdef
                                        end
                                end
                        end
                        tables[mclass] = table
                end
                return tables
        end

        # Colorize properties of the core hierarchy
        private fun colorize_core_properties do
                var mclasses = self.class_coloring.core
                var min_color = 0

                for mclass in mclasses do
                        var color = min_color

                        # if the class is root, get the minimal color
                        if self.class_coloring.parent_elements(mclass).length == 0 then
                                colorize_elements(self.properties(mclass), color)
                        else
                                # check last color used by parents
                                color = max_color(color, self.class_coloring.parent_elements(mclass))
                                # check max color used in conflicts
                                if self.class_coloring.conflicts_graph.has_key(mclass) then
                                        color = max_color(color, self.class_coloring.conflicts_graph[mclass])
                                end

                                # colorize
                                colorize_elements(self.properties(mclass), color)
                        end
                end
        end

        # Colorize properties of the crown hierarchy
        private fun colorize_crown_properties do
                for mclass in self.class_coloring.crown do
                        colorize_elements(self.properties(mclass), max_color(0, self.class_coloring.parent_elements(mclass)))
                end
        end

        # Colorize a collection of properties given a starting color
        private fun colorize_elements(elements: Collection[MPROP], start_color: Int) do
                for element in elements do
                        if self.coloration_result.has_key(element) then continue
                        self.coloration_result[element] = start_color
                        start_color += 1
                end
        end

        private fun max_color(min_color: Int, mclasses: Collection[MClass]): Int do
                var max_color = min_color

                for mclass in mclasses do
                        for mproperty in self.properties(mclass) do
                                var color = min_color
                                if self.coloration_result.has_key(mproperty) then
                                        color = self.coloration_result[mproperty]
                                        if color >= max_color then max_color = color + 1
                                end
                        end
                end
                return max_color
        end

        # properties cache
        private var properties_cache: Map[MClass, Set[MPROP]] = new HashMap[MClass, Set[MPROP]]

        # All 'mproperties' associated to all 'mclassdefs' of the class
        private fun properties(mclass: MClass): Set[MPROP] do
                if not self.properties_cache.has_key(mclass) then
                        var properties = new HashSet[MPROP]
                        var parents = self.class_coloring.super_elements(mclass)
                        for parent in parents do
                                properties.add_all(self.properties(parent))
                        end

                        for mclassdef in mclass.mclassdefs do
                                for mpropdef in mclassdef.mpropdefs do
                                        var mproperty = mpropdef.mproperty
                                        if mproperty isa MPROP then
                                                properties.add(mproperty)
                                        end
                                end
                        end
                        self.properties_cache[mclass] = properties
                end
                return properties_cache[mclass]
        end
end

# MMethod coloring
class MethodColoring
        super PropertyColoring

        redef type MPROP: MMethod
        redef type MPROPDEF: MMethodDef
        init(class_coloring: ClassColoring) do end
end

# MAttribute coloring
class AttributeColoring
        super PropertyColoring

        redef type MPROP: MAttribute
        redef type MPROPDEF: MAttributeDef
        init(class_coloring: ClassColoring) do end
end

# MVirtualTypeProp coloring
class VTColoring
        super PropertyColoring

        redef type MPROP: MVirtualTypeProp
        redef type MPROPDEF: MVirtualTypeDef
        init(class_coloring: ClassColoring) do end
end

class NaiveVTColoring
        super VTColoring

        init(class_coloring: ClassColoring) do end

        redef fun colorize: Map[MPROP, Int] do
                var mclasses = new HashSet[MClass]
                mclasses.add_all(self.class_coloring.core)
                mclasses.add_all(self.class_coloring.crown)
                var min_color = 0

                for mclass in mclasses do
                        min_color = max_color(min_color, mclasses)
                        colorize_elements(self.properties(mclass), min_color)
                end
                return self.coloration_result
        end
end

abstract class VTPerfectHashing
        super VTColoring

        private var masks: Map[MClass, Int] = new HashMap[MClass, Int]

        init(class_coloring: ClassColoring) do end

        redef fun colorize: Map[MPROP, Int] do
                var mclasses = new HashSet[MClass]
                mclasses.add_all(self.class_coloring.core)
                mclasses.add_all(self.class_coloring.crown)
                for mclass in mclasses do
                        var vts = self.properties(mclass)
                        for vt in vts do
                                if coloration_result.has_key(vt) then continue
                                coloration_result[vt] = coloration_result.length + 1
                        end
                end
                return self.coloration_result
        end

        fun compute_masks: Map[MClass, Int] do
                var mclasses = new HashSet[MClass]
                mclasses.add_all(self.class_coloring.core)
                mclasses.add_all(self.class_coloring.crown)
                for mclass in mclasses do
                        self.masks[mclass] = compute_mask(self.properties(mclass))
                end
                return self.masks
        end

        private fun compute_mask(vts: Set[MPROP]): Int do
                var mask = 0
                loop
                        var used = new List[Int]
                        for vt in vts do
                                var res = op(mask, self.coloration_result[vt])
                                if used.has(res) then
                                        break
                                else
                                        used.add(res)
                                end
                        end
                        if used.length == vts.length then break
                        mask += 1
                end
                return mask
        end

        redef fun build_property_tables do
                var tables = new HashMap[MClass, Array[nullable MPROPDEF]]

                for mclass in self.class_coloring.coloration_result.keys do
                        var table = new Array[nullable MPROPDEF]
                        # first, fill table from parents by reverse linearization order
                        var parents = new OrderedSet[MClass]
                        parents.add_all(self.class_coloring.super_elements(mclass))
                        self.class_coloring.reverse_sorter.sort(parents)
                        for parent in parents do
                                for mproperty in self.properties(parent) do
                                        var color = phash(self.coloration_result[mproperty], masks[mclass])
                                        if table.length <= color then
                                                for i in [table.length .. color[ do
                                                        table[i] = null
                                                end
                                        end
                                        for mpropdef in mproperty.mpropdefs do
                                                if mpropdef.mclassdef.mclass == parent then
                                                        table[color] = mpropdef
                                                end
                                        end
                                end
                        end

                        # then override with local properties
                        for mproperty in self.properties(mclass) do
                                var color = phash(self.coloration_result[mproperty], masks[mclass])
                                if table.length <= color then
                                        for i in [table.length .. color[ do
                                                table[i] = null
                                        end
                                end
                                for mpropdef in mproperty.mpropdefs do
                                        if mpropdef.mclassdef.mclass == mclass then
                                                table[color] = mpropdef
                                        end
                                end
                        end
                        tables[mclass] = table
                end
                return tables
        end

        private fun op(mask: Int, id:Int): Int is abstract
        private fun phash(id: Int, mask: Int): Int do return op(mask, id)

end

class VTModPerfectHashing
        super VTPerfectHashing
        init(class_coloring: ClassColoring) do end
        redef fun op(mask, id) do return mask % id
end

class VTAndPerfectHashing
        super VTPerfectHashing
        init(class_coloring: ClassColoring) do end
        redef fun op(mask, id) do return mask.bin_and(id)
end

# MParameterType coloring
class FTColoring
        private var class_coloring: ClassColoring
        private var coloration_result: Map[MParameterType, Int] = new HashMap[MParameterType, Int]

        init(class_coloring: ClassColoring) do
                self.class_coloring = class_coloring
        end

        fun colorize: Map[MParameterType, Int] do
                colorize_core_properties
                colorize_crown_properties
                return self.coloration_result
        end

        # Colorize properties of the core hierarchy
        private fun colorize_core_properties do
                var mclasses = self.class_coloring.core
                var min_color = 0

                for mclass in mclasses do
                        var color = min_color

                        # if the class is root, get the minimal color
                        if self.class_coloring.parent_elements(mclass).length == 0 then
                                colorize_elements(self.fts(mclass), color)
                        else
                                # check last color used by parents
                                color = max_color(color, self.class_coloring.parent_elements(mclass))
                                # check max color used in conflicts
                                if self.class_coloring.conflicts_graph.has_key(mclass) then
                                        color = max_color(color, self.class_coloring.conflicts_graph[mclass])
                                end
                                # colorize
                                colorize_elements(self.fts(mclass), color)
                        end
                end
        end

        # Colorize properties of the crown hierarchy
        private fun colorize_crown_properties do
                for mclass in self.class_coloring.crown do
                        colorize_elements(self.fts(mclass), max_color(0, self.class_coloring.parent_elements(mclass)))
                end
        end

        # Colorize a collection of properties given a starting color
        private fun colorize_elements(elements: Collection[MParameterType], start_color: Int) do
                for element in elements do
                        if self.coloration_result.has_key(element) then continue
                        self.coloration_result[element] = start_color
                        start_color += 1
                end
        end

        private fun max_color(min_color: Int, mclasses: Collection[MClass]): Int do
                var max_color = min_color

                for mclass in mclasses do
                        for ft in self.fts(mclass) do
                                var color = min_color
                                if self.coloration_result.has_key(ft) then
                                        color = self.coloration_result[ft]
                                        if color >= max_color then max_color = color + 1
                                end
                        end
                end
                return max_color
        end

        # fts cache
        private var fts_cache: Map[MClass, Set[MParameterType]] = new HashMap[MClass, Set[MParameterType]]

        private fun fts(mclass: MClass): Set[MParameterType] do
                if not self.fts_cache.has_key(mclass) then
                        var fts = new HashSet[MParameterType]
                        var mclass_type = mclass.mclass_type
                        if mclass_type isa MGenericType then
                                for ft in mclass_type.arguments do
                                        fts.add(ft.as(MParameterType))
                                end
                        end
                        self.fts_cache[mclass] = fts
                end
                return fts_cache[mclass]
        end

        fun build_ft_tables: Map[MClass, Array[nullable MParameterType]] do
                var tables = new HashMap[MClass, Array[nullable MParameterType]]

                for mclass in self.class_coloring.coloration_result.keys do
                        var table = new Array[nullable MParameterType]

                        # first, fill table from parents
                        for parent in self.class_coloring.super_elements(mclass) do
                                for ft in self.fts(parent) do
                                        var color = self.coloration_result[ft]
                                        if table.length <= color then
                                                for i in [table.length .. color[ do
                                                        table[i] = null
                                                end
                                        end
                                        table[color] = ft
                                end
                        end

                        # then override with local properties
                        for ft in self.fts(mclass) do
                                var color = self.coloration_result[ft]
                                if table.length <= color then
                                        for i in [table.length .. color[ do
                                                table[i] = null
                                        end
                                end
                                table[color] = ft
                        end
                        tables[mclass] = table
                end
                return tables
        end
end

class NaiveFTColoring
        super FTColoring

        init(class_coloring: ClassColoring) do end

        redef fun colorize: Map[MParameterType, Int] do
                var mclasses = new HashSet[MClass]
                mclasses.add_all(self.class_coloring.core)
                mclasses.add_all(self.class_coloring.crown)
                var min_color = 0

                for mclass in mclasses do
                        min_color = max_color(min_color, mclasses)
                        colorize_elements(self.fts(mclass), min_color)
                end
                return self.coloration_result
        end
end

abstract class FTPerfectHashing
        super FTColoring

        private var masks: Map[MClass, Int] = new HashMap[MClass, Int]

        init(class_coloring: ClassColoring) do end

        redef fun colorize: Map[MParameterType, Int] do
                var mclasses = new HashSet[MClass]
                mclasses.add_all(self.class_coloring.core)
                mclasses.add_all(self.class_coloring.crown)
                for mclass in mclasses do
                        for ft in self.fts(mclass) do
                                if coloration_result.has_key(ft) then continue
                                coloration_result[ft] = coloration_result.length + 1
                        end
                end
                return self.coloration_result
        end

        fun compute_masks: Map[MClass, Int] do
                var mclasses = new HashSet[MClass]
                mclasses.add_all(self.class_coloring.core)
                mclasses.add_all(self.class_coloring.crown)
                for mclass in mclasses do
                        var fts = new HashSet[MParameterType]
                        for parent in self.class_coloring.super_elements(mclass) do
                                fts.add_all(self.fts(parent))
                        end
                        fts.add_all(self.fts(mclass))
                        self.masks[mclass] = compute_mask(fts)
                end
                return self.masks
        end

        private fun compute_mask(fts: Set[MParameterType]): Int do
                var mask = 0
                loop
                        var used = new List[Int]
                        for ft in fts do
                                var res = op(mask, self.coloration_result[ft])
                                if used.has(res) then
                                        break
                                else
                                        used.add(res)
                                end
                        end
                        if used.length == fts.length then break
                        mask += 1
                end
                return mask
        end

        redef fun build_ft_tables do
                var tables = new HashMap[MClass, Array[nullable MParameterType]]

                for mclass in self.class_coloring.coloration_result.keys do
                        var table = new Array[nullable MParameterType]

                        # first, fill table from parents
                        for parent in self.class_coloring.super_elements(mclass) do
                                for ft in self.fts(parent) do
                                        var color = phash(self.coloration_result[ft], masks[mclass])
                                        if table.length <= color then
                                                for i in [table.length .. color[ do
                                                        table[i] = null
                                                end
                                        end
                                        table[color] = ft
                                end
                        end

                        # then override with local properties
                        for ft in self.fts(mclass) do
                                var color = phash(self.coloration_result[ft], masks[mclass])
                                if table.length <= color then
                                        for i in [table.length .. color[ do
                                                table[i] = null
                                        end
                                end
                                table[color] = ft
                        end
                        tables[mclass] = table
                end
                return tables
        end

        private fun op(mask: Int, id:Int): Int is abstract
        private fun phash(id: Int, mask: Int): Int do return op(mask, id)
end

class FTModPerfectHashing
        super FTPerfectHashing
        init(class_coloring: ClassColoring) do end
        redef fun op(mask, id) do return mask % id
end

class FTAndPerfectHashing
        super FTPerfectHashing
        init(class_coloring: ClassColoring) do end
        redef fun op(mask, id) do return mask.bin_and(id)
end

# Live Entries coloring
class LiveEntryColoring

        private var coloration_result: Map[MType, Int] = new HashMap[MType, Int]
        private var conflicts_graph_cache: nullable HashMap[MType, Set[MType]]
        var livetypes_tables_sizes: nullable Map[MClass, Array[Int]]

        init do end

        fun colorize(elements: Collection[MType]): Map[MType, Int] do
                # compute conflicts
                build_conflicts_graph(elements)

                # colorize graph
                colorize_elements(elements)

                return coloration_result
        end

        # Build type tables
        fun build_livetype_tables(mtypes: Set[MType]): Map[MClass, Array[nullable Object]] do
                var livetypes_tables = new HashMap[MClass, Array[nullable Object]]
                self.livetypes_tables_sizes = new HashMap[MClass, Array[Int]]

                for mtype in mtypes do
                        if mtype isa MGenericType then
                                var table: Array[nullable Object]
                                var sizes: Array[Int]
                                if livetypes_tables.has_key(mtype.mclass) then
                                        table = livetypes_tables[mtype.mclass]
                                else
                                        table = new Array[nullable Object]
                                        livetypes_tables[mtype.mclass] = table
                                end
                                if livetypes_tables_sizes.has_key(mtype.mclass) then
                                        sizes = livetypes_tables_sizes[mtype.mclass]
                                else
                                        sizes = new Array[Int]
                                        livetypes_tables_sizes[mtype.mclass] = sizes
                                end
                                build_livetype_table(mtype, 0, table, sizes)
                        end
                end

                return livetypes_tables
        end

        # Build live gentype table recursively
        private fun build_livetype_table(mtype: MGenericType, current_rank: Int, table: Array[nullable Object], sizes: Array[Int]) do
                var ft = mtype.arguments[current_rank]
                if not self.coloration_result.has_key(ft) then return
                var color = self.coloration_result[ft]

                if current_rank >= sizes.length then
                        sizes[current_rank] = color + 1
                else if color >= sizes[current_rank] then
                        sizes[current_rank] = color + 1
                end

                if color > table.length then
                        for i in [table.length .. color[ do table[i] = null
                end

                if current_rank == mtype.arguments.length - 1 then
                        table[color] = mtype
                else
                        var ft_table: Array[nullable Object]
                        if color < table.length and table[color] != null then
                                ft_table = table[color].as(Array[nullable Object])
                        else
                                ft_table = new Array[nullable Object]
                        end
                        table[color] = ft_table
                        build_livetype_table(mtype, current_rank + 1, ft_table, sizes)
                end
        end

        # Colorize a collection of elements
        fun colorize_elements(elements: Collection[MType]) do
                var min_color = 0

                for element in elements do
                        var color = min_color
                        while not self.is_color_free(element, color) do
                                color += 1
                        end
                        coloration_result[element] = color
                        color = min_color
                end
        end

        # Check if a related element to the element already use the color
        private fun is_color_free(element: MType, color: Int): Bool do
                if conflicts_graph.has_key(element) then
                        for st in conflicts_graph[element] do
                                if coloration_result.has_key(st) and coloration_result[st] == color then return false
                        end
                end
                return true
        end

        # look for types in the same generic signatures
        private fun build_conflicts_graph(elements: Collection[MType]) do
                # regroup types by classes
                var genclasses = new HashMap[MClass, Set[MType]]
                for e in elements do
                        if e isa MGenericType then
                                if not genclasses.has_key(e.mclass) then
                                        genclasses[e.mclass] = new HashSet[MType]
                                end
                                genclasses[e.mclass].add(e)
                        end
                end

                # for each class
                self.conflicts_graph_cache = new HashMap[MType, Set[MType]]
                for mclass, mtypes in genclasses do
                        # for each rank
                        for rank in [0..mclass.arity[ do
                                # for each live type
                                for mtype in mtypes do
                                        var mclasstype: MClassType
                                        if mtype isa MNullableType then
                                                mclasstype = mtype.mtype.as(MClassType)
                                        else
                                                mclasstype = mtype.as(MClassType)
                                        end
                                        var ft = mclasstype.arguments[rank]
                                        for otype in mtypes do
                                                if mtype == otype then continue
                                                var oclasstype: MClassType
                                                if otype isa MNullableType then
                                                        oclasstype = otype.mtype.as(MClassType)
                                                else
                                                        oclasstype = otype.as(MClassType)
                                                end
                                                var oft = oclasstype.arguments[rank]
                                                self.add_conflict(ft, oft)
                                        end
                                end
                        end
                end
        end

        private fun add_conflict(mtype: MType, otype: MType) do
                if mtype == otype then return
                if not self.conflicts_graph_cache.has_key(mtype) then  self.conflicts_graph_cache[mtype] = new HashSet[MType]
                self.conflicts_graph_cache[mtype].add(otype)
                if not self.conflicts_graph_cache.has_key(otype) then  self.conflicts_graph_cache[otype] = new HashSet[MType]
                self.conflicts_graph_cache[otype].add(mtype)
        end
        private fun conflicts_graph: Map[MType, Set[MType]] do return conflicts_graph_cache.as(not null)
end

class NaiveLiveEntryColoring
        super LiveEntryColoring

        init do end

        redef fun colorize_elements(elements: Collection[MType]) do
                var color = 0
                for element in elements do
                        coloration_result[element] = color
                        color += 1
                end
        end
end


# Utils

# An ordered set
class OrderedSet[E]
        super Array[E]

        init do end

        init from(elements: Set[E]) do
                self.add_all(elements)
        end

        redef fun add(e) do
                if not self.has(e) then
                        super(e)
                end
        end

        # Return a new OrderedSet with the elements only contened in 'self' and not in 'o'
        fun -(o: OrderedSet[E]): OrderedSet[E] do
                var res = new OrderedSet[E]
                for e in self do if not o.has(e) then res.add(e)
                return res
        end

        # Linearize a set of elements
        fun linearize(sorter: AbstractSorter[E]) do
                sorter.sort(self)
        end
end