- private var conflicts_graph: nullable HashMap[E, Set[E]]
-
- # cache for linear_extensions
- 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
- 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))
- 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
-end
-
-# MType coloring
-private class MTypeColorer
- super AbstractColoring[MType]
-
- type T: 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)
-end
-
-abstract class TypePerfectHashing
- super TypeLayoutBuilder
- super AbstractColoring[MType]
-
- type T: MType
-
- init(mmodule: MModule) do self.mmodule = mmodule
-
- 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)
-
- 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)
-end
-
-class TypeModPerfectHashing
- super TypePerfectHashing
- init(mainmodule: MModule) do super
- redef fun op(mask, id) do return mask % id
-end
-
-class TypeAndPerfectHashing
- super TypePerfectHashing
- init(mainmodule: MModule) do super
- redef fun op(mask, id) do return mask.bin_and(id)
-end
-
-# MClass coloring
-class ClassColoring
- super AbstractColoring[MClass]
-
- type T: MClass
-
- private var mmodule: MModule
-
- # caches
- private var super_elements_cache: Map[T, Set[T]] = new HashMap[T, Set[T]]
- private var parent_elements_cache: Map[T, Set[T]] = new HashMap[T, Set[T]]
- private var sub_elements_cache: Map[T, Set[T]] = new HashMap[T, Set[T]]
-
- init(mainmodule: MModule) do self.mmodule = mainmodule
-
- 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
-
-# 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 class_coloring: ClassColoring
- private var coloration_result: Map[MPROP, Int] = new HashMap[MPROP, Int]
-
- init(class_coloring: ClassColoring) do
- self.class_coloring = class_coloring
- end
-
- fun colorize: Map[MPROP, Int] do
- colorize_core_properties
- colorize_crown_properties
- 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
- 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.properties(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.properties(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.properties(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[MPROP], 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
-
- # 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
- end
- return properties_cache[mclass]
- end
-end
-
-# MMethod coloring
-class MethodColoring
- super PropertyColoring
-
- redef type MPROP: MMethod
- redef type MPROPDEF: MMethodDef
- init(class_coloring: ClassColoring) do end
-end
-
-# MAttribute coloring
-class AttributeColoring
- super PropertyColoring
-
- redef type MPROP: MAttribute
- redef type MPROPDEF: MAttributeDef
- init(class_coloring: ClassColoring) do end
-end
-
-# MVirtualTypeProp coloring
-class VTColoring
- super PropertyColoring
-
- redef type MPROP: MVirtualTypeProp
- redef type MPROPDEF: MVirtualTypeDef
- init(class_coloring: ClassColoring) do end
-end
-
-class NaiveVTColoring
- super VTColoring
-
- init(class_coloring: ClassColoring) do end
-
- redef fun colorize: Map[MPROP, 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.properties(mclass), min_color)
- end
- return self.coloration_result
- end
-end
-
-abstract class VTPerfectHashing
- super VTColoring
-
- private var masks: Map[MClass, Int] = new HashMap[MClass, Int]
-
- init(class_coloring: ClassColoring) do end
-
- redef fun colorize: Map[MPROP, 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 vts = self.properties(mclass)
- for vt in vts do
- if coloration_result.has_key(vt) then continue
- coloration_result[vt] = 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
- self.masks[mclass] = compute_mask(self.properties(mclass))
- end
- return self.masks
- end
-
- private fun compute_mask(vts: Set[MPROP]): Int do
- var mask = 0
- loop
- var used = new List[Int]
- for vt in vts do
- var res = op(mask, self.coloration_result[vt])
- if used.has(res) then
- break
- else
- used.add(res)
- end
- end
- if used.length == vts.length then break
- mask += 1
- end
- return mask
- end
-
- redef fun build_property_tables do
- var tables = new HashMap[MClass, Array[nullable MPROPDEF]]
-
- for mclass in self.class_coloring.coloration_result.keys 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 = phash(self.coloration_result[mproperty], masks[mclass])
- 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 = phash(self.coloration_result[mproperty], masks[mclass])
- 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
-
- 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 VTModPerfectHashing
- super VTPerfectHashing
- init(class_coloring: ClassColoring) do end
- redef fun op(mask, id) do return mask % id
-end
-
-class VTAndPerfectHashing
- super VTPerfectHashing
- init(class_coloring: ClassColoring) do end
- 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