-class TypeLayout
- # Unic ids or each Mtype
- var ids: Map[MType, Int] = new HashMap[MType, Int]
- # Fixed positions of each MType in all tables
- var pos: Map[MType, Int] = new HashMap[MType, Int]
-end
-
-class PHTypeLayout
- super TypeLayout
- # Masks used by hash function
- var masks: Map[MType, Int] = new HashMap[MType, Int]
- # Positions of each MType for each tables
- var hashes: Map[MType, Map[MType, Int]] = new HashMap[MType, Map[MType, Int]]
-end
-
-class ClassLayout
- # Unic ids or each MClass
- var ids: Map[MClass, Int] = new HashMap[MClass, Int]
- # Fixed positions of each MClass in all tables
- var pos: Map[MClass, Int] = new HashMap[MClass, Int]
-end
-
-class PHClassLayout
- super ClassLayout
- # Masks used by hash function
- var masks: Map[MClass, Int] = new HashMap[MClass, Int]
- # Positions of each MClass for each tables
- var hashes: Map[MClass, Map[MClass, Int]] = new HashMap[MClass, Map[MClass, Int]]
-end
-
-# Builders
-
-abstract class TypeLayoutBuilder
-
- type LAYOUT: TypeLayout
-
- private var mmodule: MModule
- init(mmodule: MModule) do self.mmodule = mmodule
-
- # Compute mtypes ids and position
- fun build_layout(mtypes: Set[MType]): LAYOUT is abstract
-
- # Give each MType a unic id using a descending linearization of the `mtypes` set
- private fun compute_ids(mtypes: Set[MType]): Map[MType, Int] do
- var ids = new HashMap[MType, Int]
- var lin = self.mmodule.reverse_linearize_mtypes(mtypes)
- for mtype in lin do
- ids[mtype] = ids.length
- end
- return ids
- end
-end
-
-# Layout builder for MType using Binary Matrix (BM)
-class BMTypeLayoutBuilder
- super TypeLayoutBuilder
-
- init(mmodule: MModule) do super
-
- # Compute mtypes ids and position using BM
- redef fun build_layout(mtypes: Set[MType]): TypeLayout do
- var result = new TypeLayout
- result.ids = self.compute_ids(mtypes)
- result.pos = result.ids
- return result
- end
-end
-
-# Layout builder for MType using Coloring (CL)
-class CLTypeLayoutBuilder
- super TypeLayoutBuilder
-
- 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 TypeLayout
- result.ids = self.compute_ids(mtypes)
- result.pos = self.colorer.colorize(mtypes)
- return result
- end
-end
-
-# Layout builder for MType using Perfect Hashing (PH)
-class PHTypeLayoutBuilder
- super TypeLayoutBuilder
-
- redef type LAYOUT: PHTypeLayout
-
- private var hasher: MTypeHasher
-
- init(mmodule: MModule, operator: PHOperator) do
- super
- self.hasher = new MTypeHasher(mmodule, operator)
- end
-
- # Compute mtypes ids and position using BM
- redef fun build_layout(mtypes) do
- var result = new PHTypeLayout
- result.ids = self.compute_ids(mtypes)
- result.masks = self.hasher.compute_masks(mtypes, result.ids)
- result.hashes = self.hasher.compute_hashes(mtypes, result.ids, result.masks)
- return result
- 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
- end
- return ids
- end
-end
-
-abstract class ClassLayoutBuilder
-
- type LAYOUT: ClassLayout
-
- private var mmodule: MModule
- init(mmodule: MModule) do self.mmodule = mmodule
-
- # Compute mclasses ids and position
- fun build_layout(mclasses: Set[MClass]): LAYOUT is abstract
-
- # Give each MClass a unic id using a descending linearization of the `mclasses` set
- private fun compute_ids(mclasses: Set[MClass]): Map[MClass, Int] do
- var ids = new HashMap[MClass, Int]
- var lin = self.mmodule.reverse_linearize_mclasses(mclasses)
- for mclass in lin do
- ids[mclass] = ids.length
- end
- return ids
- end
-end
-
-# Layout builder for MClass using Binary Matrix (BM)
-class BMClassLayoutBuilder
- super ClassLayoutBuilder
-
- init(mmodule: MModule) do super
-
- # Compute mclasses ids and position using BM
- redef fun build_layout(mclasses: Set[MClass]): LAYOUT do
- var result = new ClassLayout
- result.ids = self.compute_ids(mclasses)
- result.pos = result.ids
- return result
- end
-end
-
-# Layout builder for MClass using Coloring (CL)
-class CLClassLayoutBuilder
- super ClassLayoutBuilder
-
- private var colorer: MClassColorer
-
- init(mmodule: MModule) do
- super
- self.colorer = new MClassColorer(mmodule)
- end
-
- # Compute mclasses ids and position using BM
- redef fun build_layout(mclasses) do
- var result = new ClassLayout
- result.ids = self.compute_ids(mclasses)
- result.pos = self.colorer.colorize(mclasses)
- return result
- end
-end
-
-# Layout builder for MClass using Perfect Hashing (PH)
-class PHClassLayoutBuilder
- super ClassLayoutBuilder
-
- redef type LAYOUT: PHClassLayout
-
- private var hasher: MClassHasher
-
- init(mmodule: MModule, operator: PHOperator) do
- super
- self.hasher = new MClassHasher(mmodule, operator)
- end
-
- # Compute mclasses ids and position using BM
- redef fun build_layout(mclasses) do
- var result = new PHClassLayout
- result.ids = self.compute_ids(mclasses)
- result.masks = self.hasher.compute_masks(mclasses, result.ids)
- result.hashes = self.hasher.compute_hashes(mclasses, result.ids, result.masks)
- 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
-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
- tag_elements(elements)
- build_conflicts_graph(elements)
- colorize_elements(core)
- colorize_elements(border)
- colorize_elements(crown)
- return coloration_result
- end
-
- # Colorize a collection of elements
- private fun colorize_elements(elements: Set[E]) do
- var min_color = 0
-
- var lin = reverse_linearize(elements)
- for element in lin do
- var color = min_color
- while not self.is_color_free(element, elements, 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, elements: Set[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, elements) do
- if coloration_result.has_key(st) and coloration_result[st] == color then return false
- end
- return true
- end
-
- # Tag elements as core, crown or border
- private fun tag_elements(elements: Set[E]) do
- 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
- 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 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)
- else
- crown.add(element)
- end
- 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
- 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
- if t == i then continue
-
- var lin_i = self.linear_extension(i, elements)
-
- for j in self.linear_extension(t, elements) do
- if i == j or j == t then continue
- var lin_j = self.linear_extension(j, elements)
-
- var d_ij = lin_i - lin_j
- var d_ji = lin_j - lin_i
-
- for ed1 in d_ij do
- if not conflicts_graph.has_key(ed1) then conflicts_graph[ed1] = new HashSet[E]
- # add ed1 x ed2 to conflicts graph
- for ed2 in d_ji do conflicts_graph[ed1].add(ed2)
- end
- for ed1 in d_ij do
- if not conflicts_graph.has_key(ed1) then conflicts_graph[ed1] = new HashSet[E]
- # add ed1 x ed2 to conflicts graph
- for ed2 in d_ji do conflicts_graph[ed1].add(ed2)
- end
- end
- end
- end
- end
-
- private var conflicts_graph: nullable HashMap[E, Set[E]]
-
- # cache for linear_extensions
- 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
- 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))
- 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
-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)
-end
-
-# MClass coloring
-private class MClassColorer
- super AbstractColorer[MClass]
-
- private var mmodule: MModule