# Graph coloring tools
module coloring
-intrude import modelbuilder
-
-redef class ModelBuilder
- private var core: OrderedSet[MClass] = new OrderedSet[MClass]
- private var crown: OrderedSet[MClass] = new OrderedSet[MClass]
- private var border: OrderedSet[MClass] = new OrderedSet[MClass]
-
- # Colorize classes and properties
- fun colorize_model(mainmodule: MModule) do
-
- # compute linear ext of each class and tag each class as core, crown or border
- for mclass in model.mclasses do
- mclass.compute_linear_ext(mainmodule)
- tag_class(mclass)
- end
-
- # sort by reverse linearization order
- var sorter = new ReverseLinearizationSorter(mainmodule)
- sorter.sort(core)
- sorter.sort(crown)
- sorter.sort(border)
-
- # compute conflicts graph for the whole class hierarchy
- compute_conflicts_graph
-
- # colorize graph
- colorize_classes(core)
- colorize_classes(border)
- colorize_classes(crown)
+import rapid_type_analysis # for type coloration
+
+abstract class AbstractColoring[E: Object]
+
+ private var core: Set[E] = new HashSet[E]
+ private var crown: Set[E] = new HashSet[E]
+ private var border: Set[E] = new HashSet[E]
+
+ private var coloration_result: Map[E, Int] = new HashMap[E, Int]
+
+ init do end
+
+ fun colorize(elements: Set[E]): Map[E, Int] do
+ tag_elements(elements)
+ build_conflicts_graph
+ colorize_elements(core)
+ colorize_elements(border)
+ colorize_elements(crown)
+ return coloration_result
+ end
+
+ # Colorize a collection of elements
+ private fun colorize_elements(elements: Set[E]) do
+ var min_color = 0
+
+ var lin = reverse_linearize(elements)
+ for element in lin 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: E, 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
+ for st in self.super_elements(element) do
+ if coloration_result.has_key(st) and coloration_result[st] == color then return false
+ end
+ return true
+ end
+
+ # Tag elements as core, crown or border
+ private fun tag_elements(elements: Set[E]) do
+ for element in elements do
+ # Check if sub elements are all in single inheritance
+ var all_subelements_si = true
+ for subelem in self.sub_elements(element) do
+ if self.is_element_mi(subelem) then
+ all_subelements_si = false
+ break
+ end
+ end
+
+ # Tag as core, crown or border
+ if self.is_element_mi(element) then
+ core.add_all(self.super_elements(element))
+ core.add(element)
+ if all_subelements_si then
+ border.add(element)
+ end
+ else if not all_subelements_si then
+ core.add_all(self.super_elements(element))
+ core.add(element)
+ else
+ crown.add(element)
+ end
+ end
+ end
+
+ # Conflicts graph of elements hierarchy (two types are in conflict if they have common subelements)
+ private fun build_conflicts_graph do
+ self.conflicts_graph = new HashMap[E, HashSet[E]]
+ var core = reverse_linearize(self.core)
+ for t in core do
+ for i in self.linear_extension(t) do
+ if t == i then continue
+
+ var lin_i = self.linear_extension(i)
+
+ for j in self.linear_extension(t) do
+ if i == j or j == t then continue
+ var lin_j = self.linear_extension(j)
+
+ var d_ij = lin_i - lin_j
+ var d_ji = lin_j - lin_i
+
+ for ed1 in d_ij do
+ if not conflicts_graph.has_key(ed1) then conflicts_graph[ed1] = new HashSet[E]
+ # add ed1 x ed2 to conflicts graph
+ for ed2 in d_ji do conflicts_graph[ed1].add(ed2)
+ end
+ for ed1 in d_ij do
+ if not conflicts_graph.has_key(ed1) then conflicts_graph[ed1] = new HashSet[E]
+ # add ed1 x ed2 to conflicts graph
+ for ed2 in d_ji do conflicts_graph[ed1].add(ed2)
+ end
+ end
+ end
+ end
+ end
+
+ 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): 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))
+ self.linear_extensions_cache[element] = self.linearize(supers)
+ end
+ return self.linear_extensions_cache[element]
+ end
+
+ private fun super_elements(element: E): Set[E] is abstract
+ private fun sub_elements(element: E): Set[E] is abstract
+ private fun is_element_mi(element: 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
+
+# MClassType coloring
+class TypeColoring
+ super AbstractColoring[MType]
+
+ type T: MType
+
+ private var mmodule: MModule
+ private var mtypes: Set[T]
+
+ init(mainmodule: MModule, mtypes: Set[T]) do
+ self.mmodule = mainmodule
+ self.mtypes = mtypes
+ end
+
+ # Build type tables
+ fun build_type_tables(mtypes: Set[T], colors: Map[T, Int]): Map[T, Array[nullable T]] do
+ var tables = new HashMap[T, Array[nullable T]]
+
+ for mtype in mtypes do
+ var table = new Array[nullable T]
+ var supers = new HashSet[T]
+ supers.add_all(self.super_elements(mtype))
+ supers.add(mtype)
+ for sup in supers do
+ var color = colors[sup]
+ if table.length <= color then
+ for i in [table.length .. color[ do
+ table[i] = null
+ end
+ end
+ table[color] = sup
+ end
+ tables[mtype] = table
+ end
+ return tables
+ end
+
+ redef fun super_elements(element) do return self.mmodule.super_mtypes(element, mtypes)
+ redef fun is_element_mi(element) do return self.super_elements(element).length > 1
+ redef fun sub_elements(element) do do return self.mmodule.sub_mtypes(element, mtypes)
+ 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 NaiveTypeColoring
+ super TypeColoring
+
+ init(mainmodule: MModule, mtypes: Set[T]) do
+ super(mainmodule, mtypes)
+ 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 TypePerfectHashing
+ super TypeColoring
+
+ init(mainmodule: MModule, mtypes: Set[T]) do
+ super(mainmodule, mtypes)
+ 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))
+ supers.add(e)
+ # Compute the hashing 'mask'
+ self.coloration_result[e] = compute_mask(supers, ids)
+ end
+ return self.coloration_result
+ end
+
+ # Build type tables
+ fun hash_type_tables(mtypes: Set[T], ids: Map[T, Int], masks: Map[T, Int]): Map[T, Array[nullable T]] do
+ var tables = new HashMap[T, Array[nullable T]]
+
+ for mtype in mtypes do
+ var table = new Array[nullable T]
+ var supers = new HashSet[T]
+ supers.add_all(self.super_elements(mtype))
+ supers.add(mtype)
+
+ for sup in supers do
+ var color = phash(ids[sup], masks[mtype])
+ if table.length <= color then
+ for i in [table.length .. color[ do
+ table[i] = null
+ end
+ end
+ table[color] = sup
+ end
+ tables[mtype] = table
+ end
+ return tables
+ 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 TypeModPerfectHashing
+ super TypePerfectHashing
+ init(mainmodule: MModule, mtypes: Set[T]) do
+ super(mainmodule, mtypes)
+ end
+ redef fun op(mask, id) do return mask % id
+end
+
+class TypeAndPerfectHashing
+ super TypePerfectHashing
+ init(mainmodule: MModule, mtypes: Set[T]) do
+ super(mainmodule, mtypes)
+ end
+ 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
+
+ # Build type tables
+ fun build_type_tables(mclasses: Array[T], colors: Map[T, Int]): Map[T, Array[nullable T]] do
+ var tables = new HashMap[T, Array[nullable T]]
+
+ for mclasse in mclasses do
+ var table = new Array[nullable T]
+ var supers = new HashSet[T]
+ supers.add_all(self.super_elements(mclasse))
+ supers.add(mclasse)
+ for sup in supers do
+ var color = colors[sup]
+ if table.length <= color then
+ for i in [table.length .. color[ do
+ table[i] = null
+ end
+ end
+ table[color] = sup
+ end
+ tables[mclasse] = table
+ end
+ return tables
+ end
+
+ redef fun super_elements(element) 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) do return self.parent_elements(element).length > 1
+ redef fun sub_elements(element) 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))
+ supers.add(e)
+ # Compute the hashing 'mask'
+ self.coloration_result[e] = compute_mask(supers, ids)
+ end
+ return self.coloration_result
+ end
+
+ # Build type tables
+ fun hash_type_tables(mtypes: Set[T], ids: Map[T, Int], masks: Map[T, Int]): Map[T, Array[nullable T]] do
+ var tables = new HashMap[T, Array[nullable T]]
+
+ for mtype in mtypes do
+ var table = new Array[nullable T]
+ var supers = new HashSet[T]
+ supers.add_all(self.super_elements(mtype))
+ supers.add(mtype)
+
+ for sup in supers do
+ var color = phash(ids[sup], masks[mtype])
+ if table.length <= color then
+ for i in [table.length .. color[ do
+ table[i] = null
+ end
+ end
+ table[color] = sup
+ end
+ tables[mtype] = table
+ end
+ return tables
+ 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]]
+
+ 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.super_elements(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.super_elements(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.super_elements(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
+ 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
- # Tag type as core, crown or border
- fun tag_class(mclass: MClass) do
-
- # Check if subclasses are all in single inheritance
- var all_subclasses_si = true
- for subclass in mclass.subclasses do
- for mclassdef in subclass.mclassdefs do
- if mclassdef.supertypes.length > 1 then
- all_subclasses_si = false
- break label all_subclasses
- end
- end
- end label all_subclasses
-
- # Tag class as core, crown or border
- if mclass.parents.length > 1 then
- core.add_all(mclass.linear_ext)
- if all_subclasses_si then
- border.add(mclass)
- end
- else if mclass.parents.length == 1 then
- if all_subclasses_si then crown.add(mclass)
- else
- if all_subclasses_si then crown.add(mclass)
- end
- end
-
- # Conflicts graph of hierarchy
- private var conflicts_graph: HashMap[MClass, OrderedSet[MClass]] = new HashMap[MClass, OrderedSet[MClass]]
-
- # Compute related classes (ie. classes that have common subclasses)
- private fun compute_conflicts_graph do
- for c in core do
- for i in c.linear_ext do
- if i == c then continue
-
- var lin_i = i.linear_ext
-
- for j in c.linear_ext do
- if i == j or j == c then continue
- var lin_j = j.linear_ext
+ # fts cache
+ private var fts_cache: Map[MClass, Set[MParameterType]] = new HashMap[MClass, Set[MParameterType]]
- var d_ij = lin_i - lin_j
- var d_ji = lin_j - lin_i
+ 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
- for ed1 in d_ij do
- if not conflicts_graph.has_key(ed1) then conflicts_graph[ed1] = new OrderedSet[MClass]
- # add ed1 x ed2 to conflicts graph
- for ed2 in d_ji do conflicts_graph[ed1].add(ed2)
+ 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
+ for parent in self.class_coloring.super_elements(mclass) 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
- for ed1 in d_ij do
- if not conflicts_graph.has_key(ed1) then conflicts_graph[ed1] = new OrderedSet[MClass]
- # add ed1 x ed2 to conflicts graph
- for ed2 in d_ji do conflicts_graph[ed1].add(ed2)
+ 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
-
- # Colorize properties of the core hierarchy
- private fun colorize_core_properties do
- var mclasses = core
+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
- if not mclass.is_colorized then
-
- var color = min_color
-
- # If the class is root, get the minimal color
- if mclass.super_classes.length == 0 then
- colorize_properties(mclass.methods, color) # Colorize methods
- colorize_properties(mclass.attributes, color) # Colorize attributes
+ 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]
+ for parent in self.class_coloring.super_elements(mclass) 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
- mclass.is_colorized = true
+ 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
- # Check last color used by parents
- color = max_color(color, mclass.parents)
-
- # check max color used in conflicts
- if conflicts_graph.has_key(mclass) then
- color = max_color(color, conflicts_graph[mclass])
+ 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
+ for parent in self.class_coloring.super_elements(mclass) 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
-
- # Colorize properties
- colorize_properties(mclass.methods, color) # Colorize methods
- colorize_properties(mclass.attributes, color) # Colorize attributes
- mclass.is_colorized = true
end
+ table[color] = ft
end
+ tables[mclass] = table
end
+ return tables
end
-
- # Colorize properties of the crown hierarchy
- private fun colorize_crown_properties do
- for mclass in crown do
- colorize_properties(mclass.methods, max_color(0, mclass.parents))
- colorize_properties(mclass.attributes, max_color(0, mclass.parents))
- mclass.is_colorized = true
+
+ 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
-
- # Colorize a collection of properties given a starting color
- private fun colorize_properties(elements: Collection[MProperty], start_color: Int) do
- for mproperty in elements do
- if mproperty.is_colorized then continue
- mproperty.color = start_color
- start_color += 1
+
+ # 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 classes
- fun colorize_classes(elements: Collection[MClass]) do
+
+ # Colorize a collection of elements
+ fun colorize_elements(elements: Collection[MType]) do
var min_color = 0
- var max_color = min_color
for element in elements do
var color = min_color
- while not color_free(element, color) do
+ while not self.is_color_free(element, color) do
color += 1
end
- element.color = color
- if color > max_color then
- max_color = color
- end
+ coloration_result[element] = color
color = min_color
end
end
-
- private fun max_color(min_color: Int, mclasses: OrderedSet[MClass]): Int do
- var max_color = min_color
-
- for mclass in mclasses do
- if not mclass.is_colorized then continue
- for mproperty in mclass.methods do
- if mproperty.color >= max_color then max_color = mproperty.color + 1
+
+ # 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 max_color
+ return true
end
-
- # Check if a related element to the element already use the color
- fun color_free(element: MClass, color: Int): Bool do
- if conflicts_graph.has_key(element) then
- for st in conflicts_graph[element] do if st.color == color then return false
+
+ # 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 st in element.linear_ext do
- if st == element then continue
- if st.color == color then return false
+
+ # 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
- return true
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
-redef class MClass
+class NaiveLiveEntryColoring
+ super LiveEntryColoring
- # The class color
- var color: nullable Int = null
+ init do end
- # Is the class already colorized
- private var is_colorized: Bool = false
-
- # Linear extension of the class
- private var linear_ext: OrderedSet[MClass] = new OrderedSet[MClass]
-
- # Compute linear extension of the class
- private fun compute_linear_ext(mmodule: MModule) do
- linear_ext.add(self)
- for sup_mclass in super_classes do
- linear_ext.add(sup_mclass)
+ redef fun colorize_elements(elements: Collection[MType]) do
+ var color = 0
+ for element in elements do
+ coloration_result[element] = color
+ color += 1
end
-
- var sorter = new LinearizationSorter(mmodule)
- sorter.sort(linear_ext)
end
+end
+
+# live unanchored coloring
+class UnanchoredTypeColoring
+
+ private var coloration_result: Map[MType, Int] = new HashMap[MType, Int]
+ private var conflicts_graph: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
+
+ init do end
+
+ fun colorize(elements: Map[MClassType, Set[MType]]): Map[MType, Int] do
+ build_conflicts_graph(elements)
+ colorize_elements(elements)
+ return coloration_result
+ end
+
+ fun build_tables(elements: Map[MClassType, Set[MType]]): Map[MClassType, Array[nullable MType]] do
+ var tables = new HashMap[MClassType, Array[nullable MType]]
- # Parents of the class (only direct super classes)
- private fun parents: OrderedSet[MClass] do
- if internal_parents == null then
- internal_parents = new OrderedSet[MClass]
- for mclassdef in mclassdefs do
- for sup_mclassdef in mclassdef.in_hierarchy.direct_greaters do
- if mclassdef.mclass != sup_mclassdef.mclass then internal_parents.add(sup_mclassdef.mclass)
+ for mclasstype, mtypes in elements do
+ var table = new Array[nullable MType]
+ for mtype in mtypes do
+ var color = self.coloration_result[mtype]
+ if table.length <= color then
+ for i in [table.length .. color[ do
+ table[i] = null
+ end
end
+ table[color] = mtype
end
+ tables[mclasstype] = table
end
- return internal_parents.as(not null)
+ return tables
end
- private var internal_parents: nullable OrderedSet[MClass]
-
- # Super classes of the class (direct and indirect super classes)
- private fun super_classes: OrderedSet[MClass] do
- if internal_super_classes == null then
- internal_super_classes = new OrderedSet[MClass]
- for mclassdef in mclassdefs do
- for sup_mclassdef in mclassdef.in_hierarchy.greaters do
- if mclassdef.mclass != sup_mclassdef.mclass then internal_super_classes.add(sup_mclassdef.mclass)
+
+ # 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 internal_super_classes.as(not null)
+ return true
end
- private var internal_super_classes: nullable OrderedSet[MClass]
-
- # Sub classes (direct and indirect)
- private fun subclasses: OrderedSet[MClass] do
- if internal_subclasses == null then
- internal_subclasses = new OrderedSet[MClass]
- for mclassdef in mclassdefs do
- for sub_mclassdef in mclassdef.in_hierarchy.smallers do
- if mclassdef.mclass != sub_mclassdef.mclass then internal_subclasses.add(sub_mclassdef.mclass)
+
+ # 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
- return internal_subclasses.as(not null)
end
- private var internal_subclasses: nullable OrderedSet[MClass]
-
- # All 'mmethod' associated to all 'mclassdefs' of the class
- private fun methods: OrderedSet[MMethod] do
- if internal_methods == null then
- internal_methods = new OrderedSet[MMethod]
- for mclassdef in mclassdefs do
- for mpropdef in mclassdef.mpropdefs do
- var mproperty = mpropdef.mproperty
- if mproperty isa MMethod then
- internal_methods.add(mproperty)
- end
+
+ 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
+
+class NaiveUnanchoredTypeColoring
+ super UnanchoredTypeColoring
+
+ init do end
+
+ redef fun colorize_elements(elements: Map[MClassType, Set[MType]]) do
+ var color = 0
+ for mclasstype, mclasstypes in elements do
+ for element in mclasstypes do
+ coloration_result[element] = color
+ color += 1
+ end
+ end
+ end
+end
+
+abstract class UnanchoredTypePerfectHashing
+ super NaiveUnanchoredTypeColoring
+
+ private var masks: Map[MClassType, Int] = new HashMap[MClassType, Int]
+
+ init do end
+
+ redef fun colorize_elements(elements: Map[MClassType, Set[MType]]) do
+ var color = 1
+ for mclasstype, mclasstypes in elements do
+ for element in mclasstypes do
+ coloration_result[element] = color
+ color += 1
+ end
+ end
+ end
+
+ fun compute_masks(elements: Map[MClassType, Set[MType]]): Map[MClassType, Int] do
+ for mclasstype, mtypes in elements do
+ self.masks[mclasstype] = compute_mask(mtypes)
+ end
+ return self.masks
+ end
+
+ private fun compute_mask(mtypes: Set[MType]): Int do
+ var mask = 0
+ loop
+ var used = new List[Int]
+ for mtype in mtypes do
+ var res = op(mask, self.coloration_result[mtype])
+ if used.has(res) then
+ break
+ else
+ used.add(res)
end
end
+ if used.length == mtypes.length then break
+ mask += 1
end
- return internal_methods.as(not null)
+ return mask
end
- private var internal_methods: nullable OrderedSet[MMethod]
-
- # All 'mattribute' associated to all 'mclassdefs' of the class
- private fun attributes: OrderedSet[MAttribute] do
- if internal_attributes == null then
- internal_attributes = new OrderedSet[MAttribute]
- for mclassdef in mclassdefs do
- for mpropdef in mclassdef.mpropdefs do
- var mproperty = mpropdef.mproperty
- if mproperty isa MAttribute then
- internal_attributes.add(mproperty)
+
+ redef fun build_tables(elements: Map[MClassType, Set[MType]]): Map[MClassType, Array[nullable MType]] do
+ var tables = new HashMap[MClassType, Array[nullable MType]]
+
+ for mclasstype, mtypes in elements do
+ var table = new Array[nullable MType]
+ for mtype in mtypes do
+ var color = phash(self.coloration_result[mtype], masks[mclasstype])
+ if table.length <= color then
+ for i in [table.length .. color[ do
+ table[i] = null
end
end
+ table[color] = mtype
end
+ tables[mclasstype] = table
end
- return internal_attributes.as(not null)
+ return tables
end
- private var internal_attributes: nullable OrderedSet[MAttribute]
+
+ 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 UnanchoredTypeModPerfectHashing
+ super UnanchoredTypePerfectHashing
+ init do end
+ redef fun op(mask, id) do return mask % id
+end
-# Add color index to all properties
-redef class MProperty
- # The property color
- var color: nullable Int = null
-
- # Is the property already colored ?
- fun is_colorized: Bool do return color != null
+class UnanchoredTypeAndPerfectHashing
+ super UnanchoredTypePerfectHashing
+ init do end
+ redef fun op(mask, id) do return mask.bin_and(id)
end
-#
# Utils
-#
-# Un ordered set
-private class OrderedSet[E]
- super Array[E]
-
- redef fun add(e) do
- if not self.has(e) then
- super(e)
- end
+redef class HashSet[E]
+ init from(elements: Collection[E]) do
+ init
+ self.add_all(elements)
+ end
+end
+
+redef class Array[E]
+ init from(elements: Collection[E]) do
+ init
+ self.add_all(elements)
end
-
- # Return a new OrderedSet with the elements only contened in 'self' and not in 'o'
- fun -(o: OrderedSet[E]): OrderedSet[E] do
- var res = new OrderedSet[E]
+
+ # Return a new Array with the elements only contened in 'self' and not in 'o'
+ fun -(o: Array[E]): Array[E] do
+ var res = new Array[E]
for e in self do if not o.has(e) then res.add(e)
return res
end
end
-
+
+redef class MModule
+
+ # Return a linearization of a set of mtypes
+ private fun linearize_mtypes(mtypes: Set[MType]): Array[MType] do
+ var lin = new Array[MType].from(mtypes)
+ var sorter = new TypeSorter(self)
+ sorter.sort(lin)
+ return lin
+ end
+
+ # Return a reverse linearization of a set of mtypes
+ private fun reverse_linearize_mtypes(mtypes: Set[MType]): Array[MType] do
+ var lin = new Array[MType].from(mtypes)
+ var sorter = new ReverseTypeSorter(self)
+ sorter.sort(lin)
+ return lin
+ end
+
+ # Return super types of a `mtype` in `self`
+ private fun super_mtypes(mtype: MType, mtypes: Set[MType]): Set[MType] do
+ if not self.super_mtypes_cache.has_key(mtype) then
+ var supers = new HashSet[MType]
+ for otype in mtypes do
+ if otype == mtype then continue
+ if mtype.is_subtype(self, null, otype) then
+ supers.add(otype)
+ end
+ end
+ self.super_mtypes_cache[mtype] = supers
+ end
+ return self.super_mtypes_cache[mtype]
+ end
+
+ private var super_mtypes_cache: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
+
+ # Return all sub mtypes (directs and indirects) of a `mtype` in `self`
+ private fun sub_mtypes(mtype: MType, mtypes: Set[MType]): Set[MType] do
+ if not self.sub_mtypes_cache.has_key(mtype) then
+ var subs = new HashSet[MType]
+ for otype in mtypes do
+ if otype == mtype then continue
+ if otype.is_subtype(self, null, mtype) then
+ subs.add(otype)
+ end
+ end
+ self.sub_mtypes_cache[mtype] = subs
+ end
+ return self.sub_mtypes_cache[mtype]
+ end
+
+ private var sub_mtypes_cache: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
+
+ # Return a linearization of a set of mclasses
+ private fun linearize_mclasses(mclasses: Set[MClass]): Array[MClass] do
+ var lin = new Array[MClass].from(mclasses)
+ var sorter = new ClassSorter(self)
+ sorter.sort(lin)
+ return lin
+ end
+
+ # Return a reverse linearization of a set of mtypes
+ private fun reverse_linearize_mclasses(mclasses: Set[MClass]): Array[MClass] do
+ var lin = new Array[MClass].from(mclasses)
+ var sorter = new ReverseClassSorter(self)
+ sorter.sort(lin)
+ return lin
+ end
+
+ # Return all super mclasses (directs and indirects) of a `mclass` in `self`
+ private fun super_mclasses(mclass: MClass): Set[MClass] do
+ if not self.super_mclasses_cache.has_key(mclass) then
+ var supers = new HashSet[MClass]
+ if self.flatten_mclass_hierarchy.has(mclass) then
+ for sup in self.flatten_mclass_hierarchy[mclass].greaters do
+ if sup == mclass then continue
+ supers.add(sup)
+ end
+ end
+ self.super_mclasses_cache[mclass] = supers
+ end
+ return self.super_mclasses_cache[mclass]
+ end
+
+ private var super_mclasses_cache: Map[MClass, Set[MClass]] = new HashMap[MClass, Set[MClass]]
+
+ # Return all parents of a `mclass` in `self`
+ private fun parent_mclasses(mclass: MClass): Set[MClass] do
+ if not self.parent_mclasses_cache.has_key(mclass) then
+ var parents = new HashSet[MClass]
+ if self.flatten_mclass_hierarchy.has(mclass) then
+ for sup in self.flatten_mclass_hierarchy[mclass].direct_greaters do
+ if sup == mclass then continue
+ parents.add(sup)
+ end
+ end
+ self.parent_mclasses_cache[mclass] = parents
+ end
+ return self.parent_mclasses_cache[mclass]
+ end
+
+ private var parent_mclasses_cache: Map[MClass, Set[MClass]] = new HashMap[MClass, Set[MClass]]
+
+ # Return all sub mclasses (directs and indirects) of a `mclass` in `self`
+ private fun sub_mclasses(mclass: MClass): Set[MClass] do
+ if not self.sub_mclasses_cache.has_key(mclass) then
+ var subs = new HashSet[MClass]
+ if self.flatten_mclass_hierarchy.has(mclass) then
+ for sub in self.flatten_mclass_hierarchy[mclass].smallers do
+ if sub == mclass then continue
+ subs.add(sub)
+ end
+ end
+ self.sub_mclasses_cache[mclass] = subs
+ end
+ return self.sub_mclasses_cache[mclass]
+ end
+
+ private var sub_mclasses_cache: Map[MClass, Set[MClass]] = new HashMap[MClass, Set[MClass]]
+
+ # All 'mproperties' associated to all 'mclassdefs' of `mclass`
+ private fun properties(mclass: MClass): Set[MProperty] do
+ if not self.properties_cache.has_key(mclass) then
+ var properties = new HashSet[MProperty]
+ var parents = self.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
+ properties.add(mpropdef.mproperty)
+ end
+ end
+ self.properties_cache[mclass] = properties
+ end
+ return properties_cache[mclass]
+ end
+
+ private var properties_cache: Map[MClass, Set[MProperty]] = new HashMap[MClass, Set[MProperty]]
+end
+
+# A sorter for linearize list of types
+class TypeSorter
+ super AbstractSorter[MType]
+
+ private var mmodule: MModule
+
+ init(mmodule: MModule) do self.mmodule = mmodule
+
+ redef fun compare(a, b) do
+ if a == b then
+ return 0
+ else if a.is_subtype(self.mmodule, null, b) then
+ return -1
+ end
+ return 1
+ end
+end
+
+# A sorter for reverse linearization
+class ReverseTypeSorter
+ super TypeSorter
+
+ init(mmodule: MModule) do end
+
+ redef fun compare(a, b) do
+ if a == b then
+ return 0
+ else if a.is_subtype(self.mmodule, null, b) then
+ return 1
+ end
+ return -1
+ end
+end
# A sorter for linearize list of classes
-private class LinearizationSorter
+private class ClassSorter
super AbstractSorter[MClass]
-
+
var mmodule: MModule
-
+
redef fun compare(a, b) do
if a == b then
return 0
- else if a.super_classes.has(b) then
+ else if self.mmodule.flatten_mclass_hierarchy.has(a) and self.mmodule.flatten_mclass_hierarchy[a].greaters.has(b) then
return -1
end
return 1
end
# A sorter for reverse linearization
-private class ReverseLinearizationSorter
+private class ReverseClassSorter
super AbstractSorter[MClass]
-
+
var mmodule: MModule
-
+
redef fun compare(a, b) do
if a == b then
return 0
- else if a.super_classes.has(b) then
+ else if self.mmodule.flatten_mclass_hierarchy.has(a) and self.mmodule.flatten_mclass_hierarchy[a].greaters.has(b) then
return 1
end
return -1
end
-end
\ No newline at end of file
+end
nitlanguage / nit.git / blobdiff