# limitations under the License.
# Table layout builders
+# Tables are used to implement objects mecanisms like:
+# * message sending
+# * attribute accessing
+# * typing
+# * resolution (for generic types)
+# This module provides various layout for object tables:
+# * coloring
+# * binary matrix
+# * perfect hashing (and & mod operators)
module layout_builders
import abstract_compiler
# Layouts
-class TypingLayout[E]
- # Unic ids or each element
+# A layout is the result of computation by builders
+# it contains necessary informations for basic table creation
+class Layout[E: Object]
+ # Ids or each element
var ids: Map[E, Int] = new HashMap[E, Int]
# Fixed positions of each element in all tables
var pos: Map[E, Int] = new HashMap[E, Int]
end
-class PHTypingLayout[E]
- super TypingLayout[E]
+# A PHLayout is used everywere the builder used perfect hashing
+# it adds masks and hashes informations to std layout
+class PHLayout[HOLDER: Object, E: Object]
+ super Layout[E]
# Masks used by hash function
- var masks: Map[E, Int] = new HashMap[E, Int]
+ var masks: Map[HOLDER, Int] = new HashMap[HOLDER, Int]
# Positions of each element for each tables
- var hashes: Map[E, Map[E, Int]] = new HashMap[E, Map[E, Int]]
+ var hashes: Map[HOLDER, Map[E, Int]] = new HashMap[HOLDER, Map[E, Int]]
end
-class PropertyLayout[E]
- # Fixed positions of each element in all tables
- var pos: Map[E, Int] = new HashMap[E, Int]
-end
+# Builders
-# Layout for resolution tables
-class ResolutionLayout
- # Unic ids for each resolved type
- var ids: Map[MType, Int] = new HashMap[MType, Int]
- # Fixed positions of resolved type
- var pos: Map[MType, Int] = new HashMap[MType, Int]
+# TypingLayoutBuilder is used to build a layout for typing tables (by type or by class)
+interface TypingLayoutBuilder[E: Object]
+ # Build typing table layout
+ # elements: the set of elements (classes or types) used in typing tables
+ fun build_layout(elements: Set[E]): Layout[E] is abstract
+ # Get the poset used for table layout construction
+ # REQUIRE: build_layout
+ fun poset: nullable POSet[E] is abstract
end
-class PHResolutionLayout
- super ResolutionLayout
- # Masks associated to each owner of a resolution table
- var masks: Map[MClassType, Int] = new HashMap[MClassType, Int]
- # Positions of each resolvec type for resolution tables
- var hashes: Map[MClassType, Map[MType, Int]] = new HashMap[MClassType, Map[MType, Int]]
+# Layout builder dedicated to vft, attribute & VT tables
+interface PropertyLayoutBuilder[E: PropertyLayoutElement]
+ # Build table layout for attributes, methods and virtual types
+ # elements: the associative map between classes and properties to use in table layout
+ fun build_layout(elements: Map[MClass, Set[E]]): Layout[E] is abstract
end
-# Builders
-
-abstract class TypingLayoutBuilder[E]
-
- type LAYOUT: TypingLayout[E]
-
- private var mmodule: MModule
- init(mmodule: MModule) do self.mmodule = mmodule
-
- # Compute elements ids and position
- fun build_layout(elements: Set[E]): LAYOUT is abstract
-
- # Give each MType a unic id using a descending linearization of the `mtypes` set
- private fun compute_ids(elements: Set[E]): Map[E, Int] do
- var ids = new HashMap[E, Int]
- var lin = self.reverse_linearize(elements)
- for element in lin do
- ids[element] = ids.length
- end
- return ids
- end
+# Used to create a common ancestors to MProperty and MPropDef
+# Required for polymorphic calls
+# FIXME: there should be a better way
+interface PropertyLayoutElement end
- private fun reverse_linearize(elements: Set[E]): Array[E] is abstract
+redef class MProperty
+ super PropertyLayoutElement
end
-# Layout builder for MType using Binary Matrix (BM)
-class BMTypeLayoutBuilder
- super TypingLayoutBuilder[MType]
-
- init(mmodule: MModule) do super
-
- # Compute mtypes ids and position using BM
- redef fun build_layout(mtypes) do
- var result = new TypingLayout[MType]
- result.ids = self.compute_ids(mtypes)
- result.pos = result.ids
- return result
- end
-
- redef fun reverse_linearize(elements) do return self.mmodule.reverse_linearize_mtypes(elements)
+redef class MPropDef
+ super PropertyLayoutElement
end
-# Layout builder for MType using Coloring (CL)
-class CLTypeLayoutBuilder
- super TypingLayoutBuilder[MType]
-
- private var colorer: MTypeColorer
-
- init(mmodule: MModule) do
- super
- self.colorer = new MTypeColorer(mmodule)
- end
-
- # Compute mtypes ids and position using BM
- redef fun build_layout(mtypes) do
- var result = new TypingLayout[MType]
- result.ids = self.compute_ids(mtypes)
- result.pos = self.colorer.colorize(mtypes)
- return result
- end
-
- redef fun reverse_linearize(elements) do return self.mmodule.reverse_linearize_mtypes(elements)
+# For resolution tables (generics)
+interface ResolutionLayoutBuilder
+ # Build resolution table layout
+ # elements: association between classes and resolved types
+ fun build_layout(elements: Map[MClassType, Set[MType]]): Layout[MType] is abstract
end
-# Layout builder for MType using Perfect Hashing (PH)
-class PHTypeLayoutBuilder
- super TypingLayoutBuilder[MType]
-
- redef type LAYOUT: PHTypingLayout[MType]
+# POSet builders
- private var hasher: PerfectHasher[MType, MType]
-
- init(mmodule: MModule, operator: PHOperator) do
- super
- self.hasher = new PerfectHasher[MType, MType](operator)
- end
-
- private fun build_conflicts(mtypes: Set[MType]): Map[MType, Set[MType]] do
- var conflicts = new HashMap[MType, Set[MType]]
- for mtype in mtypes do
- var supers = self.mmodule.super_mtypes(mtype, mtypes)
- supers.add(mtype)
- conflicts[mtype] = supers
- end
- return conflicts
- end
-
- # Compute mtypes ids and position using BM
- redef fun build_layout(mtypes) do
- var result = new PHTypingLayout[MType]
- var conflicts = build_conflicts(mtypes)
- result.ids = self.compute_ids(mtypes)
- result.masks = self.hasher.compute_masks(conflicts, result.ids)
- result.hashes = self.hasher.compute_hashes(conflicts, result.ids, result.masks)
- return result
- end
+# A POSet builder build a poset for a set of MType or MClass
+# the resulting poset is used by the layout builders
+private abstract class POSetBuilder[E: Object]
+ private var mmodule: MModule
+ init(mmodule: MModule) do self.mmodule = mmodule
+ # Build the poset from `elements`
+ private fun build_poset(elements: Set[E]): POSet[E] is abstract
+end
- # Ids start from 1 instead of 0
- redef fun compute_ids(mtypes) do
- var ids = new HashMap[MType, Int]
- var lin = self.mmodule.reverse_linearize_mtypes(mtypes)
- for mtype in lin do
- ids[mtype] = ids.length + 1
+# A TypingLayoutBuilder used for MType based typing
+# such as in separate compilers
+private class MTypePOSetBuilder
+ super POSetBuilder[MType]
+ redef fun build_poset(elements) do
+ var poset = new POSet[MType]
+ for e in elements do
+ poset.add_node(e)
+ for o in elements do
+ if e == o then continue
+ if e.is_subtype(mmodule, null, o) then
+ poset.add_edge(e, o)
+ end
+ end
end
- return ids
+ return poset
end
-
- redef fun reverse_linearize(elements) do return self.mmodule.reverse_linearize_mtypes(elements)
end
-# Layout builder for MClass using Binary Matrix (BM)
-class BMClassLayoutBuilder
- super TypingLayoutBuilder[MClass]
-
- init(mmodule: MModule) do super
-
- # Compute mclasses ids and position using BM
- redef fun build_layout(mclasses) do
- var result = new TypingLayout[MClass]
- result.ids = self.compute_ids(mclasses)
- result.pos = result.ids
- return result
- end
-
- redef fun reverse_linearize(elements) do return self.mmodule.reverse_linearize_mclasses(elements)
+# A TypingLayoutBuilder used for MClass based typing
+# such as in erased compilers or used in property coloring
+private class MClassPOSetBuilder
+ super POSetBuilder[MClass]
+ redef fun build_poset(elements) do return mmodule.flatten_mclass_hierarchy
end
-# Layout builder for MClass using Coloring (CL)
-class CLClassLayoutBuilder
- super TypingLayoutBuilder[MClass]
+# Matrice computers
- private var colorer: MClassColorer
+# Abstract layout builder for resolution tables using Binary Matrix (BM)
+abstract class TypingBMizer[E: Object]
+ super TypingLayoutBuilder[E]
- init(mmodule: MModule) do
- super
- self.colorer = new MClassColorer(mmodule)
- end
+ private var mmodule: MModule
+ private var poset_builder: POSetBuilder[E]
+ private var poset_cache: nullable POSet[E]
- # Compute mclasses ids and position using BM
- redef fun build_layout(mclasses) do
- var result = new TypingLayout[MClass]
- result.ids = self.compute_ids(mclasses)
- result.pos = self.colorer.colorize(mclasses)
- return result
+ private init(mmodule: MModule, poset_builder: POSetBuilder[E]) do
+ self.mmodule = mmodule
+ self.poset_builder = poset_builder
end
- redef fun reverse_linearize(elements) do return self.mmodule.reverse_linearize_mclasses(elements)
-end
-
-# Layout builder for MClass using Perfect Hashing (PH)
-class PHClassLayoutBuilder
- super TypingLayoutBuilder[MClass]
-
- redef type LAYOUT: PHTypingLayout[MClass]
-
- private var hasher: PerfectHasher[MClass, MClass]
+ redef fun poset do return poset_cache
- init(mmodule: MModule, operator: PHOperator) do
- super
- self.hasher = new PerfectHasher[MClass, MClass](operator)
- end
-
- private fun build_conflicts(mclasses: Set[MClass]): Map[MClass, Set[MClass]] do
- var conflicts = new HashMap[MClass, Set[MClass]]
- for mclass in mclasses do
- var supers = self.mmodule.super_mclasses(mclass)
- supers.add(mclass)
- conflicts[mclass] = supers
+ # Compute mtypes ids and position using BM
+ redef fun build_layout(elements: Set[E]): Layout[E] do
+ var result = new Layout[E]
+ var ids = new HashMap[E, Int]
+ poset_cache = poset_builder.build_poset(elements)
+ var lin = poset.to_a
+ poset.sort(lin)
+ for element in lin do
+ ids[element] = ids.length
end
- return conflicts
- end
-
- # Compute mclasses ids and position using BM
- redef fun build_layout(mclasses) do
- var result = new PHTypingLayout[MClass]
- var conflicts = build_conflicts(mclasses)
- result.ids = self.compute_ids(mclasses)
- result.masks = self.hasher.compute_masks(conflicts, result.ids)
- result.hashes = self.hasher.compute_hashes(conflicts, result.ids, result.masks)
+ result.ids = ids
+ result.pos = ids
return result
end
-
- # Ids start from 1 instead of 0
- redef fun compute_ids(mclasses) do
- var ids = new HashMap[MClass, Int]
- var lin = self.mmodule.reverse_linearize_mclasses(mclasses)
- for mclass in lin do
- ids[mclass] = ids.length + 1
- end
- return ids
- end
-
- redef fun reverse_linearize(elements) do return self.mmodule.reverse_linearize_mclasses(elements)
end
-abstract class PropertyLayoutBuilder[E: MProperty]
-
- type LAYOUT: PropertyLayout[E]
-
- private var mmodule: MModule
- init(mmodule: MModule) do self.mmodule = mmodule
-
- # Compute properties ids and position
- fun build_layout(mclasses: Set[MClass]): LAYOUT is abstract
+# Layout builder for typing tables based on classes using Binary Matrix (BM)
+class MTypeBMizer
+ super TypingBMizer[MType]
+ init(mmodule: MModule) do super(mmodule, new MTypePOSetBuilder(mmodule))
end
-# Layout builder for MProperty using Coloring (CL)
-class CLPropertyLayoutBuilder[E: MProperty]
- super PropertyLayoutBuilder[E]
-
- private var colorer: MPropertyColorer[E]
-
- init(mmodule: MModule) do
- super
- self.colorer = new MPropertyColorer[E](mmodule)
- end
-
- # Compute mclasses ids and position using BM
- redef fun build_layout(mclasses) do
- var result = new PropertyLayout[E]
- result.pos = self.colorer.colorize(mclasses)
- return result
- end
-end
-
-# Layout builder for MProperty using Perfect Hashing (PH)
-# TODO implement this class without sublcassing CL builder
-class PHPropertyLayoutBuilder[E: MProperty]
- super CLPropertyLayoutBuilder[E]
+# Layout builder for typing tables based on types using Binary Matrix (BM)
+class MClassBMizer
+ super TypingBMizer[MClass]
+ init(mmodule: MModule) do super(mmodule, new MClassPOSetBuilder(mmodule))
end
-abstract class ResolutionLayoutBuilder
-
- type LAYOUT: ResolutionLayout
+# Layout builder for resolution tables using Binary Matrix (BM)
+class ResolutionBMizer
+ super ResolutionLayoutBuilder
init do end
- fun build_layout(elements: Map[MClassType, Set[MType]]): LAYOUT is abstract
-
- fun compute_ids(elements: Map[MClassType, Set[MType]]): Map[MType, Int] do
+ redef fun build_layout(elements) do
+ var result = new Layout[MType]
var ids = new HashMap[MType, Int]
var color = 0
for mclasstype, mclasstypes in elements do
color += 1
end
end
- return ids
- end
-end
-
-# Layout builder for MClass using Binary Matrix (BM)
-class BMResolutionLayoutBuilder
- super ResolutionLayoutBuilder
-
- init do super
-
- # Compute resolved types position using BM
- redef fun build_layout(elements) do
- var result = new ResolutionLayout
- result.ids = self.compute_ids(elements)
- result.pos = result.ids
+ result.ids = ids
+ result.pos = ids
return result
end
end
-# Layout builder for resolution tables using Coloring (CL)
-class CLResolutionLayoutBuilder
- super ResolutionLayoutBuilder
+# Abstract Layout builder for mproperties using Binary Matrix (BM)
+class MPropertyBMizer[E: PropertyLayoutElement]
+ super PropertyLayoutBuilder[E]
- private var colorer: ResolutionColorer = new ResolutionColorer
+ var mmodule: MModule
- init do super
+ init(mmodule: MModule) do self.mmodule = mmodule
- # Compute resolved types colors
redef fun build_layout(elements) do
- var result = new ResolutionLayout
- result.ids = self.compute_ids(elements)
- result.pos = self.colorer.colorize(elements)
+ var result = new Layout[E]
+ var ids = new HashMap[E, Int]
+ var lin = new Array[MClass]
+ lin.add_all(elements.keys)
+ self.mmodule.linearize_mclasses(lin)
+ for mclass in lin do
+ for mproperty in elements[mclass] do
+ if ids.has_key(mproperty) then continue
+ ids[mproperty] = ids.length
+ end
+ end
+ result.pos = ids
return result
end
end
-# Layout builder for resolution table using Perfect Hashing (PH)
-class PHResolutionLayoutBuilder
- super ResolutionLayoutBuilder
+# Colorers
- redef type LAYOUT: PHResolutionLayout
+# Abstract Layout builder for typing table using coloration (CL)
+abstract class TypingColorer[E: Object]
+ super TypingLayoutBuilder[E]
- private var hasher: PerfectHasher[MClassType, MType]
+ private var core: Set[E] = new HashSet[E]
+ private var crown: Set[E] = new HashSet[E]
+ private var border: Set[E] = new HashSet[E]
+ private var coloration_result: Map[E, Int] = new HashMap[E, Int]
- init(operator: PHOperator) do self.hasher = new PerfectHasher[MClassType, MType](operator)
+ private var mmodule: MModule
+ private var poset_builder: POSetBuilder[E]
+ private var poset_cache: nullable POSet[E]
- # Compute resolved types masks and hashes
- redef fun build_layout(elements) do
- var result = new PHResolutionLayout
- result.ids = self.compute_ids(elements)
- result.pos = result.ids
- result.masks = self.hasher.compute_masks(elements, result.ids)
- result.hashes = self.hasher.compute_hashes(elements, result.ids, result.masks)
+ private init(mmodule: MModule, poset_builder: POSetBuilder[E]) do
+ self.mmodule = mmodule
+ self.poset_builder = poset_builder
+ end
+
+ redef fun poset do return poset_cache
+
+ # Compute the layout with coloring
+ redef fun build_layout(elements: Set[E]): Layout[E] do
+ poset_cache = poset_builder.build_poset(elements)
+ var result = new Layout[E]
+ result.ids = compute_ids(elements)
+ result.pos = colorize(elements)
return result
end
- redef fun compute_ids(elements) do
- var ids = new HashMap[MType, Int]
- var color = 1
- for mclasstype, mclasstypes in elements do
- for element in mclasstypes do
- if ids.has_key(element) then continue
- ids[element] = color
- color += 1
- end
+ private fun compute_ids(elements: Set[E]): Map[E, Int] do
+ var ids = new HashMap[E, Int]
+ for element in reverse_linearize(elements) do
+ ids[element] = ids.length
end
return ids
end
-end
-
-# Colorers
-abstract class AbstractColorer[E: Object]
-
- private var core: Set[E] = new HashSet[E]
- private var crown: Set[E] = new HashSet[E]
- private var border: Set[E] = new HashSet[E]
-
- private var coloration_result: Map[E, Int] = new HashMap[E, Int]
-
- init do end
-
- fun colorize(elements: Set[E]): Map[E, Int] do
+ private fun colorize(elements: Set[E]): Map[E, Int] do
tag_elements(elements)
- build_conflicts_graph(elements)
+ build_conflicts_graph
colorize_elements(core)
colorize_elements(border)
colorize_elements(crown)
if coloration_result.has_key(st) and coloration_result[st] == color then return false
end
end
- for st in self.super_elements(element, elements) do
+ for st in self.poset[element].greaters do
+ if st == element then continue
if coloration_result.has_key(st) and coloration_result[st] == color then return false
end
return true
for element in elements do
# Check if sub elements are all in single inheritance
var all_subelements_si = true
- for subelem in self.sub_elements(element, elements) do
- if self.is_element_mi(subelem, elements) then
+ for subelem in self.poset[element].smallers do
+ if self.poset[subelem].direct_greaters.length > 1 then
all_subelements_si = false
break
end
end
# Tag as core, crown or border
- if self.is_element_mi(element, elements) then
- core.add_all(self.super_elements(element, elements))
- core.add(element)
+ if self.poset[element].direct_greaters.length > 1 then
+ core.add_all(self.poset[element].greaters)
if all_subelements_si then
border.add(element)
end
else if not all_subelements_si then
- core.add_all(self.super_elements(element, elements))
- core.add(element)
+ core.add_all(self.poset[element].greaters)
else
crown.add(element)
end
end
# Conflicts graph of elements hierarchy (two types are in conflict if they have common subelements)
- private fun build_conflicts_graph(elements: Set[E]) do
+ private fun build_conflicts_graph do
self.conflicts_graph = new HashMap[E, HashSet[E]]
var core = reverse_linearize(self.core)
for t in core do
- for i in self.linear_extension(t, elements) do
+ for i in self.linear_extension(t) do
if t == i then continue
- var lin_i = self.linear_extension(i, elements)
+ var lin_i = self.linear_extension(i)
- for j in self.linear_extension(t, elements) do
+ for j in self.linear_extension(t) do
if i == j or j == t then continue
- var lin_j = self.linear_extension(j, elements)
+ var lin_j = self.linear_extension(j)
var d_ij = lin_i - lin_j
var d_ji = lin_j - lin_i
private var linear_extensions_cache: Map[E, Array[E]] = new HashMap[E, Array[E]]
# Return a linear_extension of super_elements of the element
- private fun linear_extension(element: E, elements: Set[E]): Array[E] do
+ private fun linear_extension(element: E): Array[E] do
if not self.linear_extensions_cache.has_key(element) then
var supers = new HashSet[E]
- supers.add(element)
- supers.add_all(self.super_elements(element, elements))
+ supers.add_all(self.poset[element].greaters)
self.linear_extensions_cache[element] = self.linearize(supers)
end
return self.linear_extensions_cache[element]
end
- private fun super_elements(element: E, elements: Set[E]): Set[E] is abstract
- private fun sub_elements(element: E, elements: Set[E]): Set[E] is abstract
- private fun is_element_mi(element: E, elements: Set[E]): Bool is abstract
- private fun linearize(elements: Set[E]): Array[E] is abstract
- private fun reverse_linearize(elements: Set[E]): Array[E] is abstract
+ private fun reverse_linearize(elements: Set[E]): Array[E] do
+ var lin = new Array[E]
+ lin.add_all(elements)
+ poset.sort(lin)
+ return lin
+ end
+ private fun linearize(elements: Set[E]): Array[E] do return reverse_linearize(elements).reversed
end
-# MType coloring
-private class MTypeColorer
- super AbstractColorer[MType]
-
- var mmodule: MModule
-
- init(mmodule: MModule) do self.mmodule = mmodule
-
- redef fun super_elements(element, elements) do return self.mmodule.super_mtypes(element, elements)
- redef fun is_element_mi(element, elements) do return self.super_elements(element, elements).length > 1
- redef fun sub_elements(element, elements) do do return self.mmodule.sub_mtypes(element, elements)
- redef fun linearize(elements) do return self.mmodule.linearize_mtypes(elements)
- redef fun reverse_linearize(elements) do return self.mmodule.reverse_linearize_mtypes(elements)
+# Layout builder for typing tables based on types using coloration (CL)
+class MTypeColorer
+ super TypingColorer[MType]
+ init(mmodule: MModule) do super(mmodule, new MTypePOSetBuilder(mmodule))
end
-# MClass coloring
-private class MClassColorer
- super AbstractColorer[MClass]
-
- private var mmodule: MModule
-
- init(mmodule: MModule) do self.mmodule = mmodule
-
- redef fun super_elements(element, elements) do return self.mmodule.super_mclasses(element)
- fun parent_elements(element: MClass): Set[MClass] do return self.mmodule.parent_mclasses(element)
- redef fun is_element_mi(element, elements) do return self.parent_elements(element).length > 1
- redef fun sub_elements(element, elements) do do return self.mmodule.sub_mclasses(element)
- redef fun linearize(elements) do return self.mmodule.linearize_mclasses(elements)
- redef fun reverse_linearize(elements) do return self.mmodule.reverse_linearize_mclasses(elements)
+# Layout builder for typing tables based on classes using coloration (CL)
+class MClassColorer
+ super TypingColorer[MClass]
+ init(mmodule: MModule) do super(mmodule, new MClassPOSetBuilder(mmodule))
end
-# MProperty coloring
-private class MPropertyColorer[E: MProperty]
+# Abstract Layout builder for properties tables using coloration (CL)
+class MPropertyColorer[E: PropertyLayoutElement]
+ super PropertyLayoutBuilder[E]
private var mmodule: MModule
private var class_colorer: MClassColorer
private var coloration_result: Map[E, Int] = new HashMap[E, Int]
- init(mmodule: MModule) do
+ init(mmodule: MModule, class_colorer: MClassColorer) do
self.mmodule = mmodule
- self.class_colorer = new MClassColorer(mmodule)
+ self.class_colorer = class_colorer
end
- fun colorize(mclasses: Set[MClass]): Map[E, Int] do
- self.class_colorer.tag_elements(mclasses)
- self.class_colorer.build_conflicts_graph(mclasses)
- self.colorize_core(self.class_colorer.core)
- self.colorize_crown(self.class_colorer.crown)
+ # Compute mclasses ids and position using BM
+ redef fun build_layout(elements: Map[MClass, Set[E]]): Layout[E] do
+ var result = new Layout[E]
+ result.pos = self.colorize(elements)
+ return result
+ end
+
+ private fun colorize(elements: Map[MClass, Set[E]]): Map[E, Int] do
+ self.colorize_core(elements)
+ self.colorize_crown(elements)
return self.coloration_result
end
# Colorize properties of the core hierarchy
- private fun colorize_core(mclasses: Set[MClass]) do
+ private fun colorize_core(elements: Map[MClass, Set[E]]) do
var min_color = 0
- for mclass in mclasses do
+ for mclass in self.class_colorer.core do
var color = min_color
-
- # if the class is root, get the minimal color
- if self.mmodule.parent_mclasses(mclass).length == 0 then
- colorize_elements(self.properties(mclass), color)
- else
- # check last color used by parents
- color = max_color(color, self.mmodule.parent_mclasses(mclass))
- # check max color used in conflicts
- if self.class_colorer.conflicts_graph.has_key(mclass) then
- color = max_color(color, self.class_colorer.conflicts_graph[mclass])
- end
- colorize_elements(self.properties(mclass), color)
+ # check last color used by parents
+ color = max_color(color, mclass.in_hierarchy(mmodule).direct_greaters, elements)
+ # check max color used in conflicts
+ if self.class_colorer.conflicts_graph.has_key(mclass) then
+ color = max_color(color, self.class_colorer.conflicts_graph[mclass], elements)
end
+ colorize_elements(elements[mclass], color)
end
end
# Colorize properties of the crown hierarchy
- private fun colorize_crown(mclasses: Set[MClass]) do
- for mclass in mclasses do
- colorize_elements(self.properties(mclass), max_color(0, self.mmodule.parent_mclasses(mclass)))
+ private fun colorize_crown(elements: Map[MClass, Set[E]]) do
+ for mclass in self.class_colorer.crown do
+ var parents = new HashSet[MClass]
+ if mmodule.flatten_mclass_hierarchy.has(mclass) then
+ parents.add_all(mclass.in_hierarchy(mmodule).direct_greaters)
+ end
+ colorize_elements(elements[mclass], max_color(0, parents, elements))
end
end
end
end
- private fun max_color(min_color: Int, mclasses: Collection[MClass]): Int do
+ private fun max_color(min_color: Int, mclasses: Collection[MClass], elements: Map[MClass, Set[E]]): Int do
var max_color = min_color
for mclass in mclasses do
- for mproperty in self.properties(mclass) do
+ for mproperty in elements[mclass] do
var color = min_color
if self.coloration_result.has_key(mproperty) then
color = self.coloration_result[mproperty]
end
return max_color
end
-
- # Filter properties
- private fun properties(mclass: MClass): Set[E] do
- var properties = new HashSet[E]
- for mprop in self.mmodule.properties(mclass) do
- if mprop isa E then properties.add(mprop)
- end
- return properties
- end
end
-# Colorer for type resolution table
+# Layout builder for resolution tables using coloration (CL)
class ResolutionColorer
+ super ResolutionLayoutBuilder
private var coloration_result: Map[MType, Int] = new HashMap[MType, Int]
init do end
- fun colorize(elements: Map[MClassType, Set[MType]]): Map[MType, Int] do
+ # Compute resolved types colors
+ redef fun build_layout(elements) do
self.build_conflicts_graph(elements)
- self.colorize_elements(elements)
- return coloration_result
+ var result = new Layout[MType]
+ result.ids = self.compute_ids(elements)
+ result.pos = self.colorize_elements(elements)
+ return result
+ end
+
+ private fun compute_ids(elements: Map[MClassType, Set[MType]]): Map[MType, Int] do
+ var ids = new HashMap[MType, Int]
+ var color = 0
+ for mclasstype, mclasstypes in elements do
+ for element in mclasstypes do
+ if ids.has_key(element) then continue
+ ids[element] = color
+ color += 1
+ end
+ end
+ return ids
end
# Colorize a collection of elements
- fun colorize_elements(elements: Map[MClassType, Set[MType]]) do
+ private fun colorize_elements(elements: Map[MClassType, Set[MType]]): Map[MType, Int] do
var min_color = 0
for mclasstype, mclasstypes in elements do
for element in mclasstypes do
color = min_color
end
end
+ return self.coloration_result
end
# Check if a related element to the element already use the color
# Perfect Hashing (PH)
# T = type of holder
# U = type of elements to hash
-private class PerfectHasher[T, U]
+private class PerfectHasher[T: Object, U: Object]
var operator: PHOperator
- init(operator: PHOperator) do self.operator = operator
+ init do end
+ # Compute mask for each holders
fun compute_masks(conflicts: Map[T, Set[U]], ids: Map[U, Int]): Map[T, Int] do
var masks = new HashMap[T, Int]
for mclasstype, mtypes in conflicts do
return mask
end
+ # Compute hash for each element in each holder
fun compute_hashes(elements: Map[T, Set[U]], ids: Map[U, Int], masks: Map[T, Int]): Map[T, Map[U, Int]] do
var hashes = new HashMap[T, Map[U, Int]]
for mclasstype, mtypes in elements do
# Abstract operator used for perfect hashing
abstract class PHOperator
+ # hash `id` using `mask`
fun op(mask: Int, id:Int): Int is abstract
end
init do end
redef fun op(mask, id) do return mask.bin_and(id)
end
+
+# Layout builder for typing tables using perfect hashing (PH)
+class TypingHasher[E: Object]
+ super PerfectHasher[E, E]
+ super TypingLayoutBuilder[E]
+
+ private var mmodule: MModule
+ private var poset_builder: POSetBuilder[E]
+ private var poset_cache: nullable POSet[E]
+
+ private init(mmodule: MModule, poset_builder: POSetBuilder[E], operator: PHOperator) do
+ self.operator = operator
+ self.mmodule = mmodule
+ self.poset_builder = poset_builder
+ end
+
+ redef fun build_layout(elements: Set[E]): PHLayout[E, E] do
+ poset_cache = poset_builder.build_poset(elements)
+ var result = new PHLayout[E, E]
+ var conflicts = self.build_conflicts(elements)
+ result.ids = self.compute_ids
+ result.masks = self.compute_masks(conflicts, result.ids)
+ result.hashes = self.compute_hashes(conflicts, result.ids, result.masks)
+ return result
+ end
+
+ # Ids start from 1 instead of 0
+ private fun compute_ids: Map[E, Int] do
+ var ids = new HashMap[E, Int]
+ var lin = poset.to_a
+ poset.sort(lin)
+ for e in lin do
+ ids[e] = ids.length + 1
+ end
+ return ids
+ end
+
+ private fun build_conflicts(elements: Set[E]): Map[E, Set[E]] do
+ var conflicts = new HashMap[E, Set[E]]
+ for e in elements do
+ var supers = new HashSet[E]
+ supers.add_all(self.poset[e].greaters)
+ supers.add(e)
+ conflicts[e] = supers
+ end
+ return conflicts
+ end
+end
+
+# Layout builder for typing tables with types using perfect hashing (PH)
+class MTypeHasher
+ super TypingHasher[MType]
+ init(operator: PHOperator, mmodule: MModule) do super(mmodule, new MTypePOSetBuilder(mmodule), operator)
+end
+
+# Layout builder for typing tables with classes using perfect hashing (PH)
+class MClassHasher
+ super TypingHasher[MClass]
+ init(operator: PHOperator, mmodule: MModule) do super(mmodule, new MClassPOSetBuilder(mmodule), operator)
+end
+
+# Abstract layout builder for properties tables using perfect hashing (PH)
+class MPropertyHasher[E: PropertyLayoutElement]
+ super PerfectHasher[MClass, E]
+ super PropertyLayoutBuilder[E]
+
+ var mmodule: MModule
+
+ init(operator: PHOperator, mmodule: MModule) do
+ self.operator = operator
+ self.mmodule = mmodule
+ end
+
+ fun build_poset(mclasses: Set[MClass]): POSet[MClass] do
+ var poset = new POSet[MClass]
+ for e in mclasses do
+ poset.add_node(e)
+ for o in mclasses do
+ if e == o or not mmodule.flatten_mclass_hierarchy.has(e) then continue
+ if e.in_hierarchy(mmodule) < o then poset.add_edge(e, o)
+ end
+ end
+ return poset
+ end
+
+ redef fun build_layout(elements) do
+ var result = new PHLayout[MClass, E]
+ var ids = new HashMap[E, Int]
+ var mclasses = new HashSet[MClass]
+ mclasses.add_all(elements.keys)
+ var poset = build_poset(mclasses)
+ var lin = poset.to_a
+ poset.sort(lin)
+ for mclass in lin.reversed do
+ for mproperty in elements[mclass] do
+ if ids.has_key(mproperty) then continue
+ ids[mproperty] = ids.length + 1
+ end
+ end
+ result.ids = ids
+ result.pos = ids
+ result.masks = self.compute_masks(elements, ids)
+ result.hashes = self.compute_hashes(elements, ids, result.masks)
+ return result
+ end
+end
+
+# Layout builder for resolution tables using perfect hashing (PH)
+class ResolutionHasher
+ super PerfectHasher[MClassType, MType]
+ super ResolutionLayoutBuilder
+
+ init(operator: PHOperator) do self.operator = operator
+
+ # Compute resolved types masks and hashes
+ redef fun build_layout(elements) do
+ var result = new PHLayout[MClassType, MType]
+ var ids = new HashMap[MType, Int]
+ var color = 1
+ for mclasstype, mclasstypes in elements do
+ for element in mclasstypes do
+ if ids.has_key(element) then continue
+ ids[element] = color
+ color += 1
+ end
+ end
+ result.ids = ids
+ result.pos = ids
+ result.masks = self.compute_masks(elements, ids)
+ result.hashes = self.compute_hashes(elements, ids, result.masks)
+ return result
+ end
+end
nitlanguage / nit.git / blobdiff