+
+# 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