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

diff --git a/src/layout_builders.nit b/src/layout_builders.nit
index 105c52c..201ebc1 100644
--- a/src/layout_builders.nit
+++ b/src/layout_builders.nit
@@ -13,12 +13,23 @@
 # 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
 
+# 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]
@@ -26,6 +37,8 @@ class Layout[E: Object]
 	var pos: Map[E, Int] = new HashMap[E, Int]
 end
 
+# 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
@@ -34,163 +47,124 @@ class PHLayout[HOLDER: Object, E: Object]
 	var hashes: Map[HOLDER, Map[E, Int]] = new HashMap[HOLDER, Map[E, Int]]
 end
 
-class PropertyLayout[E: Object]
-	# Fixed positions of each element in all tables
-	var pos: Map[E, Int] = new HashMap[E, Int]
-end
-
 # Builders
 
-abstract class TypingLayoutBuilder[E: Object]
-
-	type LAYOUT: Layout[E]
-
-	# Compute elements ids and position
-	fun build_layout(elements: Set[E]): LAYOUT is abstract
+# 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
 
-# Typing Layout builder using binary matrix (BM)
-class BMTypingLayoutBuilder[E: Object]
-	super TypingLayoutBuilder[E]
-
-	private var bmizer: TypingBMizer[E]
-
-	init(bmizer: TypingBMizer[E]) do self.bmizer = bmizer
-
-	redef fun build_layout(elements) do return bmizer.build_layout(elements)
+# 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
 
-# Typing Layout builder using Coloring (CL)
-class CLTypingLayoutBuilder[E: Object]
-	super TypingLayoutBuilder[E]
-
-	private var colorer: TypingColorer[E]
-
-	init(colorer: TypingColorer[E]) do self.colorer = colorer
-
-	redef fun build_layout(elements) do return colorer.build_layout(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
 
-# Typing Layout builder using Perfect Hashing (PH)
-class PHTypingLayoutBuilder[E: Object]
-	super TypingLayoutBuilder[E]
-
-	private var hasher: TypingHasher[E]
-
-	init(hasher: TypingHasher[E]) do self.hasher = hasher
+# POSet builders
 
-	redef fun build_layout(elements) do return hasher.build_layout(elements)
-end
-
-abstract class PropertyLayoutBuilder[E: MProperty]
-
-	type LAYOUT: PropertyLayout[E]
-
-	# Compute properties ids and position
-	fun build_layout(mclasses: Set[MClass]): LAYOUT is abstract
+# 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
 
-# Layout builder for MProperty using Coloring (CL)
-class CLPropertyLayoutBuilder[E: MProperty]
-	super PropertyLayoutBuilder[E]
-
-	private var colorer: MPropertyColorer[E]
-
-	init(colorer: MPropertyColorer[E]) do
-		self.colorer = colorer
-	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
+# 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 poset
 	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]
+# 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
 
-abstract class ResolutionLayoutBuilder
-
-	type LAYOUT: Layout[MType]
+# Matrice computers
 
-	init do end
+# Abstract layout builder for resolution tables using Binary Matrix (BM)
+abstract class TypingBMizer[E: Object]
+	super TypingLayoutBuilder[E]
 
-	fun build_layout(elements: Map[MClassType, Set[MType]]): LAYOUT is abstract
+	private var mmodule: MModule
+	private var poset_builder: POSetBuilder[E]
+	private var poset_cache: nullable POSet[E]
 
-	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
+	private init(mmodule: MModule, poset_builder: POSetBuilder[E]) do
+		self.mmodule = mmodule
+		self.poset_builder = poset_builder
 	end
-end
 
-# Layout builder for MClass using Binary Matrix (BM)
-class BMResolutionLayoutBuilder
-	super ResolutionLayoutBuilder
-
-	init do super
+	redef fun poset do return poset_cache
 
-	# Compute resolved types position using BM
-	redef fun build_layout(elements) do
-		var result = new Layout[MType]
-		result.ids = self.compute_ids(elements)
-		result.pos = result.ids
+	# 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
+		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
+# 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
 
-	# Compute resolved types colors
-	redef fun build_layout(elements) do
-		var result = new Layout[MType]
-		result.ids = self.compute_ids(elements)
-		result.pos = self.colorer.colorize(elements)
-		return result
-	end
+# 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
 
-# Layout builder for resolution table using Perfect Hashing (PH)
-class PHResolutionLayoutBuilder
+# Layout builder for resolution tables using Binary Matrix (BM)
+class ResolutionBMizer
 	super ResolutionLayoutBuilder
 
-	redef type LAYOUT: PHLayout[MClassType, MType]
-
-	private var hasher: PerfectHasher[MClassType, MType]
-
-	init(operator: PHOperator) do self.hasher = new PerfectHasher[MClassType, MType](operator)
+	init do end
 
-	# Compute resolved types masks and hashes
 	redef fun build_layout(elements) do
-		var result = new PHLayout[MClassType, MType]
-		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)
-		return result
-	end
-
-	redef fun compute_ids(elements) do
+		var result = new Layout[MType]
 		var ids = new HashMap[MType, Int]
-		var color = 1
+		var color = 0
 		for mclasstype, mclasstypes in elements do
 			for element in mclasstypes do
 				if ids.has_key(element) then continue
@@ -198,70 +172,94 @@ class PHResolutionLayoutBuilder
 				color += 1
 			end
 		end
-		return ids
+		result.ids = ids
+		result.pos = ids
+		return result
 	end
 end
 
-# Matrice computers
+# Abstract Layout builder for mproperties using Binary Matrix (BM)
+abstract class MPropertyBMizer[E: MProperty]
+	super PropertyLayoutBuilder[E]
 
-abstract class TypingBMizer[E: Object]
+	type MPROP: MProperty
 
 	var mmodule: MModule
 
-	init(mmodule: MModule) do
-		self.mmodule = mmodule
-	end
+	init(mmodule: MModule) do self.mmodule = mmodule
 
-	# Compute mtypes ids and position using BM
-	fun build_layout(elements: Set[E]): Layout[E] do
+	redef fun build_layout(elements) do
 		var result = new Layout[E]
 		var ids = new HashMap[E, Int]
-		var lin = self.reverse_linearize(elements)
-		for element in lin do
-			ids[element] = ids.length
+		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.ids = ids
 		result.pos = ids
 		return result
 	end
 
-	private fun reverse_linearize(elements: Set[E]): Array[E] is abstract
+	# 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 properties
+	end
 end
 
-class MTypeBMizer
-	super TypingBMizer[MType]
-
+# Layout builder for vft using Binary Matrix (BM)
+class MMethodBMizer
+	super MPropertyBMizer[MMethod]
+	redef type MPROP: MMethod
 	init(mmodule: MModule) do super(mmodule)
-
-	redef fun reverse_linearize(elements) do
-		return self.mmodule.reverse_linearize_mtypes(elements)
-	end
 end
 
-class MClassBMizer
-	super TypingBMizer[MClass]
-
+# 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
 
-	redef fun reverse_linearize(elements) do
-		return self.mmodule.reverse_linearize_mclasses(elements)
-	end
+# BMizing for MVirtualTypeProps
+class MVirtualTypePropBMizer
+	super MPropertyBMizer[MVirtualTypeProp]
+	redef type MPROP: MVirtualTypeProp
+	init(mmodule: MModule) do super(mmodule)
 end
 
 # Colorers
 
+# 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
-	fun build_layout(elements: Set[E]): Layout[E] do
+	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)
@@ -270,8 +268,7 @@ abstract class TypingColorer[E: Object]
 
 	private fun compute_ids(elements: Set[E]): Map[E, Int] do
 		var ids = new HashMap[E, Int]
-		var lin = reverse_linearize(elements)
-		for element in lin do
+		for element in reverse_linearize(elements) do
 			ids[element] = ids.length
 		end
 		return ids
@@ -279,7 +276,7 @@ abstract class TypingColorer[E: Object]
 
 	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)
@@ -308,7 +305,8 @@ abstract class TypingColorer[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
@@ -319,23 +317,21 @@ abstract class TypingColorer[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
@@ -343,18 +339,18 @@ abstract class TypingColorer[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
@@ -380,69 +376,59 @@ abstract class TypingColorer[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
+# Layout builder for typing tables based on types using coloration (CL)
 class MTypeColorer
 	super TypingColorer[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)
+	init(mmodule: MModule) do super(mmodule, new MTypePOSetBuilder(mmodule))
 end
 
-# MClass coloring
+# Layout builder for typing tables based on classes using coloration (CL)
 class MClassColorer
 	super TypingColorer[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)
+	init(mmodule: MModule) do super(mmodule, new MClassPOSetBuilder(mmodule))
 end
 
-# MProperty coloring
+# 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
 
-	fun colorize(mclasses: Set[MClass]): Map[E, Int] do
-		self.class_colorer.tag_elements(mclasses)
-		self.class_colorer.build_conflicts_graph(mclasses)
+	# 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
+
+	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
@@ -453,26 +439,24 @@ abstract 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
 
@@ -501,69 +485,71 @@ abstract class MPropertyColorer[E: MProperty]
 	end
 
 	# Filter properties
-	private fun properties(mclass: MClass): Set[E] is abstract
+	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
 
-# Coloring for MMethods
+# Layout builder for vft using coloration (CL)
 class MMethodColorer
 	super MPropertyColorer[MMethod]
 
-	init(mmodule: MModule) do super
-
-	redef fun properties(mclass) do
-		var properties = new HashSet[MMethod]
-		for mprop in self.mmodule.properties(mclass) do
-			if mprop isa MMethod then properties.add(mprop)
-		end
-		return properties
-	end
+	redef type MPROP: MMethod
+	init(mmodule: MModule, class_colorer: MClassColorer) do super(mmodule, class_colorer)
 end
 
-# Coloring for MMAttributes
+# Layout builder for attributes using coloration (CL)
 class MAttributeColorer
 	super MPropertyColorer[MAttribute]
 
-	init(mmodule: MModule) do super
-
-	redef fun properties(mclass) do
-		var properties = new HashSet[MAttribute]
-		for mprop in self.mmodule.properties(mclass) do
-			if mprop isa MAttribute then properties.add(mprop)
-		end
-		return properties
-	end
+	redef type MPROP: MAttribute
+	init(mmodule: MModule, class_colorer: MClassColorer) do super(mmodule, class_colorer)
 end
 
-# Coloring for MVirtualTypeProps
+# Layout builder for virtual types using coloration (CL)
 class MVirtualTypePropColorer
 	super MPropertyColorer[MVirtualTypeProp]
 
-	init(mmodule: MModule) do super
-
-	redef fun properties(mclass) do
-		var properties = new HashSet[MVirtualTypeProp]
-		for mprop in self.mmodule.properties(mclass) do
-			if mprop isa MVirtualTypeProp then properties.add(mprop)
-		end
-		return properties
-	end
+	redef type MPROP: MVirtualTypeProp
+	init(mmodule: MModule, class_colorer: MClassColorer) do super(mmodule, class_colorer)
 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
@@ -576,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
@@ -618,8 +605,9 @@ 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
@@ -646,6 +634,7 @@ private class PerfectHasher[T: Object, U: Object]
 		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
@@ -662,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
 
@@ -681,29 +671,36 @@ class PHAndOperator
 	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]
 
-	var mmodule: MModule
+	private var mmodule: MModule
+	private var poset_builder: POSetBuilder[E]
+	private var poset_cache: nullable POSet[E]
 
-	init(operator: PHOperator, mmodule: MModule) do
-		super(operator)
+	private init(mmodule: MModule, poset_builder: POSetBuilder[E], operator: PHOperator) do
+		self.operator = operator
 		self.mmodule = mmodule
+		self.poset_builder = poset_builder
 	end
 
-	fun build_layout(elements: Set[E]): PHLayout[E, E] do
+	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(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(elements: Set[E]): Map[E, Int] do
+	private fun compute_ids: Map[E, Int] do
 		var ids = new HashMap[E, Int]
-		var lin = self.reverse_linearize(elements)
+		var lin = poset.to_a
+		poset.sort(lin)
 		for e in lin do
 			ids[e] = ids.length + 1
 		end
@@ -713,41 +710,129 @@ class TypingHasher[E: Object]
 	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 = self.super_elements(e, elements)
+			var supers = new HashSet[E]
+			supers.add_all(self.poset[e].greaters)
 			supers.add(e)
 			conflicts[e] = supers
 		end
 		return conflicts
 	end
-
-	private fun super_elements(element: E, elements: Set[E]): Set[E] is abstract
-	private fun reverse_linearize(elements: Set[E]): Array[E] is abstract
 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
 
-	init(operator: PHOperator, mmodule: MModule) do super(operator, mmodule)
+# 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]
 
-	redef fun super_elements(element, elements) do
-		return self.mmodule.super_mtypes(element, elements)
+	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
 
-	redef fun reverse_linearize(elements) do
-		return self.mmodule.reverse_linearize_mtypes(elements)
+	# 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
 
-class MClassHasher
-	super TypingHasher[MClass]
+# 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
 
-	redef fun super_elements(element, elements) do
-		return self.mmodule.super_mclasses(element)
-	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
 
-	redef fun reverse_linearize(elements) do
-		return self.mmodule.reverse_linearize_mclasses(elements)
+	# 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