# Layouts
-class TypeLayout
- # Unic ids or each Mtype
- var ids: Map[MType, Int] = new HashMap[MType, Int]
- # Fixed positions of each MType in all tables
- var pos: Map[MType, Int] = new HashMap[MType, Int]
+class TypingLayout[E]
+ # Unic 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 PHTypeLayout
- super TypeLayout
+class PHTypingLayout[E]
+ super TypingLayout[E]
# Masks used by hash function
- var masks: Map[MType, Int] = new HashMap[MType, Int]
- # Positions of each MType for each tables
- var hashes: Map[MType, Map[MType, Int]] = new HashMap[MType, Map[MType, Int]]
+ var masks: Map[E, Int] = new HashMap[E, Int]
+ # Positions of each element for each tables
+ var hashes: Map[E, Map[E, Int]] = new HashMap[E, 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
-abstract class TypeLayoutBuilder
+abstract class TypingLayoutBuilder[E]
- type LAYOUT: TypeLayout
+ type LAYOUT: TypingLayout[E]
private var mmodule: MModule
init(mmodule: MModule) do self.mmodule = mmodule
- # Compute mtypes ids and position
- fun build_layout(mtypes: Set[MType]): LAYOUT is abstract
+ # 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(mtypes: Set[MType]): Map[MType, Int] do
- var ids = new HashMap[MType, Int]
- var lin = self.mmodule.reverse_linearize_mtypes(mtypes)
- for mtype in lin do
- ids[mtype] = ids.length
+ 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 TypeLayoutBuilder
+ super TypingLayoutBuilder[MType]
init(mmodule: MModule) do super
# Compute mtypes ids and position using BM
- redef fun build_layout(mtypes: Set[MType]): TypeLayout do
- var result = new TypeLayout
+ 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)
end
# Layout builder for MType using Coloring (CL)
class CLTypeLayoutBuilder
- super TypeLayoutBuilder
+ super TypingLayoutBuilder[MType]
private var colorer: MTypeColorer
# Compute mtypes ids and position using BM
redef fun build_layout(mtypes) do
- var result = new TypeLayout
+ 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 TypeLayoutBuilder
+ super TypingLayoutBuilder[MType]
- redef type LAYOUT: PHTypeLayout
+ redef type LAYOUT: PHTypingLayout[MType]
private var hasher: MTypeHasher
# Compute mtypes ids and position using BM
redef fun build_layout(mtypes) do
- var result = new PHTypeLayout
+ var result = new PHTypingLayout[MType]
result.ids = self.compute_ids(mtypes)
result.masks = self.hasher.compute_masks(mtypes, result.ids)
result.hashes = self.hasher.compute_hashes(mtypes, result.ids, result.masks)
end
return ids
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)
+end
+
+# Layout builder for MClass using Coloring (CL)
+class CLClassLayoutBuilder
+ super TypingLayoutBuilder[MClass]
+
+ private var colorer: MClassColorer
+
+ init(mmodule: MModule) do
+ super
+ self.colorer = new MClassColorer(mmodule)
+ end
+
+ # 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
+ 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]
+
+ private var hasher: MClassHasher
+
+ init(mmodule: MModule, operator: PHOperator) do
+ super
+ self.hasher = new MClassHasher(mmodule, operator)
+ end
+
+ # Compute mclasses ids and position using BM
+ redef fun build_layout(mclasses) do
+ var result = new PHTypingLayout[MClass]
+ result.ids = self.compute_ids(mclasses)
+ result.masks = self.hasher.compute_masks(mclasses, result.ids)
+ result.hashes = self.hasher.compute_hashes(mclasses, result.ids, result.masks)
+ 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
end
# Colorers
redef fun reverse_linearize(elements) do return self.mmodule.reverse_linearize_mtypes(elements)
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)
+end
+
+# MProperty coloring
+private class MPropertyColorer[E: 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
+ self.mmodule = mmodule
+ self.class_colorer = new MClassColorer(mmodule)
+ end
+
+ fun colorize(mclasses: Set[MClass]): Map[E, Int] do
+ self.class_colorer.tag_elements(mclasses)
+ self.class_colorer.build_conflicts_graph(mclasses)
+ self.colorize_core(self.class_colorer.core)
+ self.colorize_crown(self.class_colorer.crown)
+ return self.coloration_result
+ end
+
+ # Colorize properties of the core hierarchy
+ private fun colorize_core(mclasses: Set[MClass]) do
+ 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)
+ end
+ 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)))
+ end
+ end
+
+ # Colorize a collection of mproperties given a starting color
+ private fun colorize_elements(elements: Collection[E], 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 mproperty in self.properties(mclass) do
+ var color = min_color
+ if self.coloration_result.has_key(mproperty) then
+ color = self.coloration_result[mproperty]
+ if color >= max_color then max_color = color + 1
+ end
+ end
+ end
+ return max_color
+ end
+
+ # Filter properties
+ 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)
+ end
+ return properties
+ end
+end
+
# Perfect hashers
# Abstract Perfect Hashing
redef fun super_elements(element, elements) do return self.mmodule.super_mtypes(element, elements)
end
+# MClass Perfect Hashing
+private class MClassHasher
+ super AbstractHasher[MClass]
+
+ private var mmodule: MModule
+
+ init(mmodule: MModule, operator: PHOperator) do
+ super(operator)
+ self.mmodule = mmodule
+ end
+
+ redef fun super_elements(element, elements) do return self.mmodule.super_mclasses(element)
+end
+
# MClass coloring
class ClassColoring
super AbstractColorer[MClass]
redef fun reverse_linearize(elements) do return self.mmodule.reverse_linearize_mclasses(elements)
end
-# incremental coloring (very naive)
-class NaiveClassColoring
- super ClassColoring
-
- init(mainmodule: MModule) do
- super(mainmodule)
- end
-
- # naive coloring that use incremental coloring
- redef fun colorize_elements(elements) do
- for e in elements do
- self.coloration_result[e] = self.coloration_result.length
- end
- end
-end
-
-abstract class ClassPerfectHashing
- super ClassColoring
-
- init(mainmodule: MModule) do
- super(mainmodule)
- end
-
- fun compute_masks(elements: Set[T], ids: Map[T, Int]): Map[T, Int] do
- for e in elements do
- # Create super type list
- var supers = new HashSet[T]
- supers.add_all(self.super_elements(e, elements))
- supers.add(e)
- # Compute the hashing 'mask'
- self.coloration_result[e] = compute_mask(supers, ids)
- end
- return self.coloration_result
- end
-
- private fun compute_mask(mtypes: Set[T], ids: Map[T, Int]): Int do
- var mask = 0
- loop
- var used = new List[Int]
- for sup in mtypes do
- var res = op(mask, ids[sup])
- 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
-
- 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 ClassModPerfectHashing
- super ClassPerfectHashing
- init(mainmodule: MModule) do
- super(mainmodule)
- end
- redef fun op(mask, id) do return mask % id
-end
-
-class ClassAndPerfectHashing
- super ClassPerfectHashing
- init(mainmodule: MModule) do
- super(mainmodule)
- end
- redef fun op(mask, id) do return mask.bin_and(id)
-end
-
# MProperty coloring
class PropertyColoring
type MPROP: MProperty
type MPROPDEF: MPropDef
+ private var mmodule: MModule
private var class_coloring: ClassColoring
private var coloration_result: Map[MPROP, Int] = new HashMap[MPROP, Int]
- init(class_coloring: ClassColoring) do
+ init(mmodule: MModule, class_coloring: ClassColoring) do
+ self.mmodule = mmodule
self.class_coloring = class_coloring
end
return self.coloration_result
end
- fun build_property_tables: Map[MClass, Array[nullable MPROPDEF]] do
- var tables = new HashMap[MClass, Array[nullable MPROPDEF]]
- var mclasses = self.class_coloring.coloration_result.keys
- for mclass in mclasses do
- var table = new Array[nullable MPROPDEF]
- # first, fill table from parents by reverse linearization order
- var parents = self.class_coloring.mmodule.super_mclasses(mclass)
- var lin = self.class_coloring.reverse_linearize(parents)
- for parent in lin do
- for mproperty in self.properties(parent) do
- var color = self.coloration_result[mproperty]
- if table.length <= color then
- for i in [table.length .. color[ do
- table[i] = null
- end
- end
- for mpropdef in mproperty.mpropdefs do
- if mpropdef.mclassdef.mclass == parent then
- table[color] = mpropdef
- end
- end
- end
- end
-
- # then override with local properties
- for mproperty in self.properties(mclass) do
- var color = self.coloration_result[mproperty]
- if table.length <= color then
- for i in [table.length .. color[ do
- table[i] = null
- end
- end
- for mpropdef in mproperty.mpropdefs do
- if mpropdef.mclassdef.mclass == mclass then
- table[color] = mpropdef
- end
- end
- end
- tables[mclass] = table
- end
- return tables
- end
-
# Colorize properties of the core hierarchy
private fun colorize_core_properties do
var mclasses = self.class_coloring.core
return max_color
end
- # properties cache
- private var properties_cache: Map[MClass, Set[MPROP]] = new HashMap[MClass, Set[MPROP]]
-
# All 'mproperties' associated to all 'mclassdefs' of the class
private fun properties(mclass: MClass): Set[MPROP] do
- if not self.properties_cache.has_key(mclass) then
- var properties = new HashSet[MPROP]
- var parents = self.class_coloring.mmodule.super_mclasses(mclass)
- for parent in parents do
- properties.add_all(self.properties(parent))
- end
-
- for mclassdef in mclass.mclassdefs do
- for mpropdef in mclassdef.mpropdefs do
- var mproperty = mpropdef.mproperty
- if mproperty isa MPROP then
- properties.add(mproperty)
- end
- end
- end
- self.properties_cache[mclass] = properties
+ var properties = new HashSet[MPROP]
+ for mprop in self.mmodule.properties(mclass) do
+ if mprop isa MPROP then properties.add(mprop)
end
- return properties_cache[mclass]
+ return properties
end
end
redef type MPROP: MMethod
redef type MPROPDEF: MMethodDef
- init(class_coloring: ClassColoring) do end
+ init(mmodule: MModule, class_coloring: ClassColoring) do super
end
# MAttribute coloring
redef type MPROP: MAttribute
redef type MPROPDEF: MAttributeDef
- init(class_coloring: ClassColoring) do end
+ init(mmodule: MModule, class_coloring: ClassColoring) do super
end
# MVirtualTypeProp coloring
redef type MPROP: MVirtualTypeProp
redef type MPROPDEF: MVirtualTypeDef
- init(class_coloring: ClassColoring) do end
+ init(mmodule: MModule, class_coloring: ClassColoring) do super
end
class NaiveVTColoring
super VTColoring
- init(class_coloring: ClassColoring) do end
+ init(mmodule: MModule, class_coloring: ClassColoring) do super
redef fun colorize: Map[MPROP, Int] do
var mclasses = new HashSet[MClass]
private var masks: Map[MClass, Int] = new HashMap[MClass, Int]
- init(class_coloring: ClassColoring) do end
+ init(mmodule: MModule, class_coloring: ClassColoring) do super
redef fun colorize: Map[MPROP, Int] do
var mclasses = new HashSet[MClass]
return mask
end
- redef fun build_property_tables do
+ fun build_property_tables: Map[MClass, Array[nullable MPROPDEF]] do
var tables = new HashMap[MClass, Array[nullable MPROPDEF]]
for mclass in self.class_coloring.coloration_result.keys do
class VTModPerfectHashing
super VTPerfectHashing
- init(class_coloring: ClassColoring) do end
+ init(mmodule: MModule, class_coloring: ClassColoring) do super
redef fun op(mask, id) do return mask % id
end
class VTAndPerfectHashing
super VTPerfectHashing
- init(class_coloring: ClassColoring) do end
+ init(mmodule: MModule, class_coloring: ClassColoring) do super
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 Entries coloring
-class LiveEntryColoring
-
- private var coloration_result: Map[MType, Int] = new HashMap[MType, Int]
- private var conflicts_graph_cache: nullable HashMap[MType, Set[MType]]
- var livetypes_tables_sizes: nullable Map[MClass, Array[Int]]
-
- init do end
-
- fun colorize(elements: Collection[MType]): Map[MType, Int] do
- # compute conflicts
- build_conflicts_graph(elements)
-
- # colorize graph
- colorize_elements(elements)
-
- return coloration_result
- end
-
- # Build type tables
- fun build_livetype_tables(mtypes: Set[MType]): Map[MClass, Array[nullable Object]] do
- var livetypes_tables = new HashMap[MClass, Array[nullable Object]]
- self.livetypes_tables_sizes = new HashMap[MClass, Array[Int]]
-
- for mtype in mtypes do
- if mtype isa MGenericType then
- var table: Array[nullable Object]
- var sizes: Array[Int]
- if livetypes_tables.has_key(mtype.mclass) then
- table = livetypes_tables[mtype.mclass]
- else
- table = new Array[nullable Object]
- livetypes_tables[mtype.mclass] = table
- end
- if livetypes_tables_sizes.has_key(mtype.mclass) then
- sizes = livetypes_tables_sizes[mtype.mclass]
- else
- sizes = new Array[Int]
- livetypes_tables_sizes[mtype.mclass] = sizes
- end
- build_livetype_table(mtype, 0, table, sizes)
- end
- end
-
- return livetypes_tables
- end
-
- # Build live gentype table recursively
- private fun build_livetype_table(mtype: MGenericType, current_rank: Int, table: Array[nullable Object], sizes: Array[Int]) do
- var ft = mtype.arguments[current_rank]
- if not self.coloration_result.has_key(ft) then return
- var color = self.coloration_result[ft]
-
- if current_rank >= sizes.length then
- sizes[current_rank] = color + 1
- else if color >= sizes[current_rank] then
- sizes[current_rank] = color + 1
- end
-
- if color > table.length then
- for i in [table.length .. color[ do table[i] = null
- end
-
- if current_rank == mtype.arguments.length - 1 then
- table[color] = mtype
- else
- var ft_table: Array[nullable Object]
- if color < table.length and table[color] != null then
- ft_table = table[color].as(Array[nullable Object])
- else
- ft_table = new Array[nullable Object]
- end
- table[color] = ft_table
- build_livetype_table(mtype, current_rank + 1, ft_table, sizes)
- end
- end
-
- # Colorize a collection of elements
- fun colorize_elements(elements: Collection[MType]) do
- var min_color = 0
-
- for element in elements do
- 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
-
- # 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 types in the same generic signatures
- private fun build_conflicts_graph(elements: Collection[MType]) do
- # regroup types by classes
- var genclasses = new HashMap[MClass, Set[MType]]
- for e in elements do
- if e isa MGenericType then
- if not genclasses.has_key(e.mclass) then
- genclasses[e.mclass] = new HashSet[MType]
- end
- genclasses[e.mclass].add(e)
- end
- end
-
- # for each class
- self.conflicts_graph_cache = new HashMap[MType, Set[MType]]
- for mclass, mtypes in genclasses do
- # for each rank
- for rank in [0..mclass.arity[ do
- # for each live type
- for mtype in mtypes do
- var mclasstype: MClassType
- if mtype isa MNullableType then
- mclasstype = mtype.mtype.as(MClassType)
- else
- mclasstype = mtype.as(MClassType)
- end
- var ft = mclasstype.arguments[rank]
- for otype in mtypes do
- if mtype == otype then continue
- var oclasstype: MClassType
- if otype isa MNullableType then
- oclasstype = otype.mtype.as(MClassType)
- else
- oclasstype = otype.as(MClassType)
- end
- var oft = oclasstype.arguments[rank]
- self.add_conflict(ft, oft)
- end
- end
- end
- end
- end
-
- private fun add_conflict(mtype: MType, otype: MType) do
- if mtype == otype then return
- if not self.conflicts_graph_cache.has_key(mtype) then self.conflicts_graph_cache[mtype] = new HashSet[MType]
- self.conflicts_graph_cache[mtype].add(otype)
- if not self.conflicts_graph_cache.has_key(otype) then self.conflicts_graph_cache[otype] = new HashSet[MType]
- self.conflicts_graph_cache[otype].add(mtype)
- end
- private fun conflicts_graph: Map[MType, Set[MType]] do return conflicts_graph_cache.as(not null)
-end
-
-class NaiveLiveEntryColoring
- super LiveEntryColoring
-
- init do end
-
- redef fun colorize_elements(elements: Collection[MType]) do
- var color = 0
- for element in elements do
- coloration_result[element] = color
- color += 1
- end
- end
-end
-
# live unanchored coloring
class UnanchoredTypeColoring
nitlanguage / nit.git / blobdiff