X-Git-Url: http://nitlanguage.org

diff --git a/src/layout_builders.nit b/src/layout_builders.nit
index 925e5e1..201ebc1 100644
--- a/src/layout_builders.nit
+++ b/src/layout_builders.nit
@@ -13,288 +13,156 @@
 # 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: MProperty]
+	# Build table layout for attributes, methods and virtual types
+	# elements: the set of classes containing the properties to use in table layout
+	fun build_layout(elements: Set[MClass]): Layout[E] is abstract
 end
 
-# Builders
-
-abstract class TypingLayoutBuilder[E]
+# 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
 
-	type LAYOUT: TypingLayout[E]
+# POSet builders
 
+# 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
-
-	# 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
-
-	private fun reverse_linearize(elements: Set[E]): Array[E] is abstract
-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)
+	# Build the poset from `elements`
+	private fun build_poset(elements: Set[E]): POSet[E] is abstract
 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)
-end
-
-# Layout builder for MType using Perfect Hashing (PH)
-class PHTypeLayoutBuilder
-	super TypingLayoutBuilder[MType]
-
-	redef type LAYOUT: PHTypingLayout[MType]
-
-	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
-
-	# 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]
+	redef fun poset do return poset_cache
 
-	private var hasher: PerfectHasher[MClass, MClass]
-
-	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
 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
+# 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 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
@@ -304,91 +172,111 @@ abstract class ResolutionLayoutBuilder
 				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
-
-	private var colorer: ResolutionColorer = new ResolutionColorer
-
-	init do super
-
-	# 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)
-		return result
-	end
-end
-
-# Layout builder for resolution table using Perfect Hashing (PH)
-class PHResolutionLayoutBuilder
-	super ResolutionLayoutBuilder
+# Abstract Layout builder for mproperties using Binary Matrix (BM)
+abstract class MPropertyBMizer[E: MProperty]
+	super PropertyLayoutBuilder[E]
 
-	redef type LAYOUT: PHResolutionLayout
+	type MPROP: MProperty
 
-	private var hasher: PerfectHasher[MClassType, MType]
+	var mmodule: MModule
 
-	init(operator: PHOperator) do self.hasher = new PerfectHasher[MClassType, MType](operator)
+	init(mmodule: MModule) do self.mmodule = mmodule
 
-	# 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)
+		var result = new Layout[E]
+		var ids = new HashMap[E, Int]
+		var lin = new Array[MClass]
+		lin.add_all(elements)
+		self.mmodule.linearize_mclasses(lin)
+		for mclass in lin do
+			for mproperty in properties(mclass) do
+				if ids.has_key(mproperty) then continue
+				ids[mproperty] = ids.length
+			end
+		end
+		result.pos = ids
 		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
+	# extract properties of a mclass
+	private fun properties(mclass: MClass): Set[E] do
+		var properties = new HashSet[E]
+		for mprop in self.mmodule.properties(mclass) do
+			if mprop isa MPROP then properties.add(mprop)
 		end
-		return ids
+		return properties
 	end
 end
 
+# Layout builder for vft using Binary Matrix (BM)
+class MMethodBMizer
+	super MPropertyBMizer[MMethod]
+	redef type MPROP: MMethod
+	init(mmodule: MModule) do super(mmodule)
+end
+
+# Layout builder for attribute tables using Binary Matrix (BM)
+class MAttributeBMizer
+	super MPropertyBMizer[MAttribute]
+	redef type MPROP: MAttribute
+	init(mmodule: MModule) do super(mmodule)
+end
+
+# BMizing for MVirtualTypeProps
+class MVirtualTypePropBMizer
+	super MPropertyBMizer[MVirtualTypeProp]
+	redef type MPROP: MVirtualTypeProp
+	init(mmodule: MModule) do super(mmodule)
+end
+
 # Colorers
 
-abstract class AbstractColorer[E: Object]
+# Abstract Layout builder for typing table using coloration (CL)
+abstract class TypingColorer[E: Object]
+	super TypingLayoutBuilder[E]
 
 	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
+	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]) 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
+
+	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
 
-	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)
@@ -417,7 +305,8 @@ abstract class AbstractColorer[E: Object]
 				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
@@ -428,23 +317,21 @@ abstract class AbstractColorer[E: Object]
 		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
@@ -452,18 +339,18 @@ abstract class AbstractColorer[E: Object]
 	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
@@ -489,69 +376,59 @@ abstract class AbstractColorer[E: Object]
 	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)
+abstract class MPropertyColorer[E: MProperty]
+	super PropertyLayoutBuilder[E]
+
+	type MPROP: MProperty
 
 	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
+
+	# Compute mclasses ids and position using BM
+	redef fun build_layout(mclasses: Set[MClass]): Layout[E] do
+		var result = new Layout[E]
+		result.pos = self.colorize(mclasses)
+		return result
 	end
 
-	fun colorize(mclasses: Set[MClass]): Map[E, Int] do
-		self.class_colorer.tag_elements(mclasses)
-		self.class_colorer.build_conflicts_graph(mclasses)
+	private fun colorize(mclasses: Set[MClass]): Map[E, Int] do
 		self.colorize_core(self.class_colorer.core)
 		self.colorize_crown(self.class_colorer.crown)
 		return self.coloration_result
@@ -562,26 +439,24 @@ private class MPropertyColorer[E: MProperty]
 		var min_color = 0
 		for mclass in mclasses 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)
+			# 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)
 		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)))
+			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(self.properties(mclass), max_color(0, parents))
 		end
 	end
 
@@ -613,27 +488,68 @@ private class MPropertyColorer[E: MProperty]
 	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)
+			if mprop isa MPROP then properties.add(mprop)
 		end
 		return properties
 	end
 end
 
-# Colorer for type resolution table
+# Layout builder for vft using coloration (CL)
+class MMethodColorer
+	super MPropertyColorer[MMethod]
+
+	redef type MPROP: MMethod
+	init(mmodule: MModule, class_colorer: MClassColorer) do super(mmodule, class_colorer)
+end
+
+# Layout builder for attributes using coloration (CL)
+class MAttributeColorer
+	super MPropertyColorer[MAttribute]
+
+	redef type MPROP: MAttribute
+	init(mmodule: MModule, class_colorer: MClassColorer) do super(mmodule, class_colorer)
+end
+
+# Layout builder for virtual types using coloration (CL)
+class MVirtualTypePropColorer
+	super MPropertyColorer[MVirtualTypeProp]
+
+	redef type MPROP: MVirtualTypeProp
+	init(mmodule: MModule, class_colorer: MClassColorer) do super(mmodule, class_colorer)
+end
+
+# 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
@@ -646,6 +562,7 @@ class ResolutionColorer
 				color = min_color
 			end
 		end
+		return self.coloration_result
 	end
 
 	# Check if a related element to the element already use the color
@@ -684,12 +601,13 @@ end
 # 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
@@ -716,6 +634,7 @@ private class PerfectHasher[T, U]
 		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
@@ -732,6 +651,7 @@ end
 
 # Abstract operator used for perfect hashing
 abstract class PHOperator
+	# hash `id` using `mask`
 	fun op(mask: Int, id:Int): Int is abstract
 end
 
@@ -750,3 +670,169 @@ class PHAndOperator
 	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: MProperty]
+	super PerfectHasher[MClass, E]
+	super PropertyLayoutBuilder[E]
+
+	type MPROP: MProperty
+
+	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(mclasses) do
+		var result = new PHLayout[MClass, E]
+		var ids = new HashMap[E, Int]
+		var elements = new HashMap[MClass, Set[E]]
+		var poset = build_poset(mclasses)
+		var lin = poset.to_a
+		poset.sort(lin)
+		for mclass in lin.reversed do
+			var mproperties = properties(mclass)
+			for mproperty in mproperties do
+				if ids.has_key(mproperty) then continue
+				ids[mproperty] = ids.length + 1
+			end
+			elements[mclass] = mproperties
+		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
+
+	# extract set of properties from mclass
+	private fun properties(mclass: MClass): Set[E] do
+		var properties = new HashSet[E]
+		for mprop in self.mmodule.properties(mclass) do
+			if mprop isa MPROP then properties.add(mprop)
+		end
+		return properties
+	end
+end
+
+# Layout builder for vft using perfect hashing (PH)
+class MMethodHasher
+	super MPropertyHasher[MMethod]
+	redef type MPROP: MMethod
+	init(operator: PHOperator, mmodule: MModule) do super(operator, mmodule)
+end
+
+# Layout builder for attributes tables using perfect hashing (PH)
+class MAttributeHasher
+	super MPropertyHasher[MAttribute]
+	redef type MPROP: MAttribute
+	init(operator: PHOperator, mmodule: MModule) do super(operator, mmodule)
+end
+
+# Layout builder for virtual types tables using perfect hashing (PH)
+class MVirtualTypePropHasher
+	super MPropertyHasher[MVirtualTypeProp]
+	redef type MPROP: MVirtualTypeProp
+	init(operator: PHOperator, mmodule: MModule) do super(operator, mmodule)
+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