var pos: Map[E, Int] = new HashMap[E, Int]
end
+# 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]
+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]]
+end
+
# Builders
abstract class TypingLayoutBuilder[E]
end
end
+abstract class ResolutionLayoutBuilder
+
+ type LAYOUT: ResolutionLayout
+
+ 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
+ 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
+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
+ 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
+
+ redef type LAYOUT: PHResolutionLayout
+
+ private var hasher: ResolutionHasher
+
+ init(operator: PHOperator) do self.hasher = new ResolutionHasher(operator)
+
+ # 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)
+ 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
+ end
+ return ids
+ end
+end
+
# Colorers
abstract class AbstractColorer[E: Object]
end
end
+# Colorer for type resolution table
+class ResolutionColorer
+
+ 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
+ self.build_conflicts_graph(elements)
+ self.colorize_elements(elements)
+ return coloration_result
+ end
+
+ # Colorize a collection of elements
+ fun colorize_elements(elements: Map[MClassType, Set[MType]]) do
+ var min_color = 0
+ for mclasstype, mclasstypes in elements do
+ for element in mclasstypes do
+ if self.coloration_result.has_key(element) then continue
+ var color = min_color
+ while not self.is_color_free(element, color) do
+ color += 1
+ end
+ coloration_result[element] = color
+ color = min_color
+ end
+ end
+ end
+
+ # Check if a related element to the element already use the color
+ private fun is_color_free(element: MType, 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
+ return true
+ end
+
+ # look for unanchored types generated by the same type
+ private fun build_conflicts_graph(elements: Map[MClassType, Set[MType]]) do
+ for mclasstype, mtypes in elements do
+ for mtype in mtypes do
+ for otype in mtypes do
+ if otype == mtype then continue
+ self.add_conflict(mtype, otype)
+ end
+ end
+ end
+ end
+
+ private var conflicts_graph: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
+
+ private fun add_conflict(mtype: MType, otype: MType) do
+ if mtype == otype then return
+ if not self.conflicts_graph.has_key(mtype) then self.conflicts_graph[mtype] = new HashSet[MType]
+ self.conflicts_graph[mtype].add(otype)
+ if not self.conflicts_graph.has_key(otype) then self.conflicts_graph[otype] = new HashSet[MType]
+ self.conflicts_graph[otype].add(mtype)
+ end
+end
+
# Perfect hashers
# Abstract Perfect Hashing
redef fun super_elements(element, elements) do return self.mmodule.super_mclasses(element)
end
+# Resolution tables Perfect Hashing (PH)
+private class ResolutionHasher
+
+ var operator: PHOperator
+
+ init(operator: PHOperator) do self.operator = operator
+
+ fun compute_masks(elements: Map[MClassType, Set[MType]], ids: Map[MType, Int]): Map[MClassType, Int] do
+ var masks = new HashMap[MClassType, Int]
+ for mclasstype, mtypes in elements do
+ masks[mclasstype] = compute_mask(mtypes, ids)
+ end
+ return masks
+ end
+
+ private fun compute_mask(mtypes: Set[MType], ids: Map[MType, Int]): Int do
+ var mask = 0
+ loop
+ var used = new List[Int]
+ for mtype in mtypes do
+ var res = operator.op(mask, ids[mtype])
+ if used.has(res) then
+ break
+ else
+ used.add(res)
+ end
+ end
+ if used.length == mtypes.length then break
+ mask += 1
+ end
+ return mask
+ end
+
+ fun compute_hashes(elements: Map[MClassType, Set[MType]], ids: Map[MType, Int], masks: Map[MClassType, Int]): Map[MClassType, Map[MType, Int]] do
+ var hashes = new HashMap[MClassType, Map[MType, Int]]
+ for mclasstype, mtypes in elements do
+ var mask = masks[mclasstype]
+ var inhashes = new HashMap[MType, Int]
+ for mtype in mtypes do
+ inhashes[mtype] = operator.op(mask, ids[mtype])
+ end
+ hashes[mclasstype] = inhashes
+ end
+ return hashes
+ end
+end
+
# live unanchored coloring
class UnanchoredTypeColoring
nitlanguage / nit.git / commitdiff