redef fun op(mask, id) do return mask.bin_and(id)
end
-# MParameterType coloring
-class FTColoring
- private var class_coloring: ClassColoring
- private var coloration_result: Map[MParameterType, Int] = new HashMap[MParameterType, Int]
-
- init(class_coloring: ClassColoring) do
- self.class_coloring = class_coloring
- end
-
- fun colorize: Map[MParameterType, Int] do
- colorize_core_properties
- colorize_crown_properties
- return self.coloration_result
- end
-
- # Colorize properties of the core hierarchy
- private fun colorize_core_properties do
- var mclasses = self.class_coloring.core
- var min_color = 0
-
- for mclass in mclasses do
- var color = min_color
-
- # if the class is root, get the minimal color
- if self.class_coloring.parent_elements(mclass).length == 0 then
- colorize_elements(self.fts(mclass), color)
- else
- # check last color used by parents
- color = max_color(color, self.class_coloring.parent_elements(mclass))
- # check max color used in conflicts
- if self.class_coloring.conflicts_graph.has_key(mclass) then
- color = max_color(color, self.class_coloring.conflicts_graph[mclass])
- end
- # colorize
- colorize_elements(self.fts(mclass), color)
- end
- end
- end
-
- # Colorize properties of the crown hierarchy
- private fun colorize_crown_properties do
- for mclass in self.class_coloring.crown do
- colorize_elements(self.fts(mclass), max_color(0, self.class_coloring.parent_elements(mclass)))
- end
- end
-
- # Colorize a collection of properties given a starting color
- private fun colorize_elements(elements: Collection[MParameterType], start_color: Int) do
- for element in elements do
- if self.coloration_result.has_key(element) then continue
- self.coloration_result[element] = start_color
- start_color += 1
- end
- end
-
- private fun max_color(min_color: Int, mclasses: Collection[MClass]): Int do
- var max_color = min_color
-
- for mclass in mclasses do
- for ft in self.fts(mclass) do
- var color = min_color
- if self.coloration_result.has_key(ft) then
- color = self.coloration_result[ft]
- if color >= max_color then max_color = color + 1
- end
- end
- end
- return max_color
- end
-
- # fts cache
- private var fts_cache: Map[MClass, Set[MParameterType]] = new HashMap[MClass, Set[MParameterType]]
-
- private fun fts(mclass: MClass): Set[MParameterType] do
- if not self.fts_cache.has_key(mclass) then
- var fts = new HashSet[MParameterType]
- var mclass_type = mclass.mclass_type
- if mclass_type isa MGenericType then
- for ft in mclass_type.arguments do
- fts.add(ft.as(MParameterType))
- end
- end
- self.fts_cache[mclass] = fts
- end
- return fts_cache[mclass]
- end
-
- fun build_ft_tables: Map[MClass, Array[nullable MParameterType]] do
- var tables = new HashMap[MClass, Array[nullable MParameterType]]
-
- for mclass in self.class_coloring.coloration_result.keys do
- var table = new Array[nullable MParameterType]
-
- # first, fill table from parents
- var parents = self.class_coloring.mmodule.super_mclasses(mclass)
- for parent in parents do
- for ft in self.fts(parent) do
- var color = self.coloration_result[ft]
- if table.length <= color then
- for i in [table.length .. color[ do
- table[i] = null
- end
- end
- table[color] = ft
- end
- end
-
- # then override with local properties
- for ft in self.fts(mclass) do
- var color = self.coloration_result[ft]
- if table.length <= color then
- for i in [table.length .. color[ do
- table[i] = null
- end
- end
- table[color] = ft
- end
- tables[mclass] = table
- end
- return tables
- end
-end
-
-class NaiveFTColoring
- super FTColoring
-
- init(class_coloring: ClassColoring) do end
-
- redef fun colorize: Map[MParameterType, Int] do
- var mclasses = new HashSet[MClass]
- mclasses.add_all(self.class_coloring.core)
- mclasses.add_all(self.class_coloring.crown)
- var min_color = 0
-
- for mclass in mclasses do
- min_color = max_color(min_color, mclasses)
- colorize_elements(self.fts(mclass), min_color)
- end
- return self.coloration_result
- end
-end
-
-abstract class FTPerfectHashing
- super FTColoring
-
- private var masks: Map[MClass, Int] = new HashMap[MClass, Int]
-
- init(class_coloring: ClassColoring) do end
-
- redef fun colorize: Map[MParameterType, Int] do
- var mclasses = new HashSet[MClass]
- mclasses.add_all(self.class_coloring.core)
- mclasses.add_all(self.class_coloring.crown)
- for mclass in mclasses do
- for ft in self.fts(mclass) do
- if coloration_result.has_key(ft) then continue
- coloration_result[ft] = coloration_result.length + 1
- end
- end
- return self.coloration_result
- end
-
- fun compute_masks: Map[MClass, Int] do
- var mclasses = new HashSet[MClass]
- mclasses.add_all(self.class_coloring.core)
- mclasses.add_all(self.class_coloring.crown)
- for mclass in mclasses do
- var fts = new HashSet[MParameterType]
- var parents = self.class_coloring.mmodule.super_mclasses(mclass)
- for parent in parents do
- fts.add_all(self.fts(parent))
- end
- fts.add_all(self.fts(mclass))
- self.masks[mclass] = compute_mask(fts)
- end
- return self.masks
- end
-
- private fun compute_mask(fts: Set[MParameterType]): Int do
- var mask = 0
- loop
- var used = new List[Int]
- for ft in fts do
- var res = op(mask, self.coloration_result[ft])
- if used.has(res) then
- break
- else
- used.add(res)
- end
- end
- if used.length == fts.length then break
- mask += 1
- end
- return mask
- end
-
- redef fun build_ft_tables do
- var tables = new HashMap[MClass, Array[nullable MParameterType]]
-
- for mclass in self.class_coloring.coloration_result.keys do
- var table = new Array[nullable MParameterType]
-
- # first, fill table from parents
- var parents = self.class_coloring.mmodule.super_mclasses(mclass)
- for parent in parents do
- for ft in self.fts(parent) do
- var color = phash(self.coloration_result[ft], masks[mclass])
- if table.length <= color then
- for i in [table.length .. color[ do
- table[i] = null
- end
- end
- table[color] = ft
- end
- end
-
- # then override with local properties
- for ft in self.fts(mclass) do
- var color = phash(self.coloration_result[ft], masks[mclass])
- if table.length <= color then
- for i in [table.length .. color[ do
- table[i] = null
- end
- end
- table[color] = ft
- end
- tables[mclass] = table
- end
- return tables
- end
-
- private fun op(mask: Int, id:Int): Int is abstract
- private fun phash(id: Int, mask: Int): Int do return op(mask, id)
-end
-
-class FTModPerfectHashing
- super FTPerfectHashing
- init(class_coloring: ClassColoring) do end
- redef fun op(mask, id) do return mask % id
-end
-
-class FTAndPerfectHashing
- super FTPerfectHashing
- init(class_coloring: ClassColoring) do end
- redef fun op(mask, id) do return mask.bin_and(id)
-end
-
# live unanchored coloring
class UnanchoredTypeColoring
nitlanguage / nit.git / commitdiff