abstract class AbstractColoring[E: Object]
- private var sorter: AbstractSorter[E]
- private var reverse_sorter: AbstractSorter[E]
-
- private var core: OrderedSet[E] = new OrderedSet[E]
- private var crown: OrderedSet[E] = new OrderedSet[E]
- private var border: OrderedSet[E] = new OrderedSet[E]
+ 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]
- private var conflicts_graph_cache: nullable HashMap[E, Set[E]]
-
- init(sorter: AbstractSorter[E], reverse_sorter: AbstractSorter[E]) do
- self.sorter = sorter
- self.reverse_sorter = reverse_sorter
- end
- fun colorize(elements: Collection[E]): Map[E, Int] do
- # tag each element as part of group core, crown or border
- for e in elements do
- tag_element(e)
- end
-
- #print "core: {core.join(", ")}"
- #print "border: {border.join(", ")}"
- #print "crown: {crown.join(", ")}"
-
- # sort by reverse linearization order
- reverse_sorter.sort(core)
- reverse_sorter.sort(border)
- reverse_sorter.sort(crown)
-
- #print "conflicts"
- #for k, v in conflicts_graph do
- # if k isa MType then
- # print "{k}: {v.join(", ")}"
- # end
- #end
+ init do end
- # colorize graph
+ 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: Collection[E]) do
+ private fun colorize_elements(elements: Set[E]) do
var min_color = 0
- for element in elements do
+ 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
return true
end
- # Tag element as core, crown or border
- private fun tag_element(element: E) 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
+ # 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
- 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)
+ # 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
- else if not all_subelements_si then
- core.add_all(self.super_elements(element))
- core.add(element)
- else
- crown.add(element)
end
end
# Conflicts graph of elements hierarchy (two types are in conflict if they have common subelements)
- private fun conflicts_graph: Map[E, Set[E]] do
- if self.conflicts_graph_cache == null then
- self.conflicts_graph_cache = new HashMap[E, HashSet[E]]
- for t in self.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_cache.has_key(ed1) then conflicts_graph_cache[ed1] = new HashSet[E]
- # add ed1 x ed2 to conflicts graph
- for ed2 in d_ji do conflicts_graph_cache[ed1].add(ed2)
- end
- for ed1 in d_ij do
- if not conflicts_graph_cache.has_key(ed1) then conflicts_graph_cache[ed1] = new HashSet[E]
- # add ed1 x ed2 to conflicts graph
- for ed2 in d_ji do conflicts_graph_cache[ed1].add(ed2)
- end
+ 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
- return conflicts_graph_cache.as(not null)
end
+ private var conflicts_graph: nullable HashMap[E, Set[E]]
+
# cache for linear_extensions
- private var linear_extensions_cache: Map[E, OrderedSet[E]] = new HashMap[E, OrderedSet[E]]
+ 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): OrderedSet[E] do
+ private fun linear_extension(element: E): Array[E] do
if not self.linear_extensions_cache.has_key(element) then
- var lin = new OrderedSet[E]
- lin.add(element)
- lin.add_all(self.super_elements(element))
- self.sorter.sort(lin)
- self.linear_extensions_cache[element] = lin
+ 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
- # Return all super elements (directs and indirects) of an element
- private fun super_elements(element: E): Collection[E] is abstract
-
- # Return all sub elements (directs and indirects) of an element
- private fun sub_elements(element: E): Collection[E] is abstract
-
- # Is the element in multiple inheritance ?
+ 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
private var mmodule: MModule
private var mtypes: Set[T]
- # caches
- private var super_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, mtypes: Set[T]) do
- super(new TypeSorter(mainmodule), new ReverseTypeSorter(mainmodule))
self.mmodule = mainmodule
self.mtypes = mtypes
end
return tables
end
- redef fun super_elements(element) do
- if not self.super_elements_cache.has_key(element) then
- var supers = new HashSet[T]
- for mtype in self.mtypes do
- if element == mtype then continue
- if element.is_subtype(self.mmodule, null, mtype) then
- supers.add(mtype)
- end
- end
- self.super_elements_cache[element] = supers
- end
- return self.super_elements_cache[element]
- end
-
- # Return all direct super elements of an element
- redef fun is_element_mi(element) do
- return self.super_elements(element).length > 1
- end
-
- # Return all sub elements (directs and indirects) of an element
- redef fun sub_elements(element) do
- if not self.sub_elements_cache.has_key(element) then
- var subs = new HashSet[T]
- for mtype in self.mtypes do
- if element == mtype then continue
- if mtype.is_subtype(self.mmodule, null, element) then
- subs.add(mtype)
- end
- end
- self.sub_elements_cache[element] = subs
- end
- return self.sub_elements_cache[element]
- 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
redef fun op(mask, id) do return mask.bin_and(id)
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
-
# MClass coloring
class ClassColoring
super AbstractColoring[MClass]
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
- super(new ClassSorter(mainmodule), new ReverseClassSorter(mainmodule))
- self.mmodule = mainmodule
- end
+ 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
return tables
end
- redef fun super_elements(element) do
- if not self.super_elements_cache.has_key(element) then
- var supers = new HashSet[T]
- if self.mmodule.flatten_mclass_hierarchy.has(element) then
- for sup in self.mmodule.flatten_mclass_hierarchy[element].greaters do
- if element == sup then continue
- supers.add(sup)
- end
- end
- self.super_elements_cache[element] = supers
- end
- return self.super_elements_cache[element]
- end
-
- private fun parent_elements(element: T): Set[T] do
- if not self.parent_elements_cache.has_key(element) then
- var parents = new HashSet[T]
- if self.mmodule.flatten_mclass_hierarchy.has(element) then
- for parent in self.mmodule.flatten_mclass_hierarchy[element].direct_greaters do
- if element == parent then continue
- parents.add(parent)
- end
- end
- self.parent_elements_cache[element] = parents
- end
- return self.parent_elements_cache[element]
- end
-
- # Return all sub elements (directs and indirects) of an element
- redef fun sub_elements(element) do
- if not self.sub_elements_cache.has_key(element) then
- var subs = new HashSet[T]
- if self.mmodule.flatten_mclass_hierarchy.has(element) then
- for sub in self.mmodule.flatten_mclass_hierarchy[element].smallers do
- subs.add(sub)
- end
- end
- self.sub_elements_cache[element] = subs
- end
- return self.sub_elements_cache[element]
- end
-
- # Return all direct super elements of an element
- redef fun is_element_mi(element) do
- if not self.mmodule.flatten_mclass_hierarchy.has(element) then return false
- return self.mmodule.flatten_mclass_hierarchy[element].direct_greaters.length > 1
- 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)
end
# naive coloring that use incremental coloring
- redef fun colorize_elements(elements: Collection[MClass]) do
+ redef fun colorize_elements(elements) do
for e in elements do
self.coloration_result[e] = self.coloration_result.length
end
redef fun op(mask, id) do return mask.bin_and(id)
end
-# A sorter for linearize list of classes
-private class ClassSorter
- super AbstractSorter[MClass]
-
- var mmodule: MModule
-
- redef fun compare(a, b) do
- if a == b then
- return 0
- 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
-
-# A sorter for reverse linearization
-private class ReverseClassSorter
- super AbstractSorter[MClass]
-
- var mmodule: MModule
-
- redef fun compare(a, b) do
- if a == b then
- return 0
- 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
-
# MProperty coloring
class PropertyColoring
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 = new OrderedSet[MClass]
- parents.add_all(self.class_coloring.super_elements(mclass))
- self.class_coloring.reverse_sorter.sort(parents)
- for parent in parents do
+ 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 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 = new OrderedSet[MClass]
- parents.add_all(self.class_coloring.super_elements(mclass))
- self.class_coloring.reverse_sorter.sort(parents)
- for parent in parents do
+ 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
# live unanchored coloring
class UnanchoredTypeColoring
- private var coloration_result: Map[MClassType, Int] = new HashMap[MClassType, Int]
- private var conflicts_graph: Map[MClassType, Set[MClassType]] = new HashMap[MClassType, Set[MClassType]]
+ 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[MClassType]]): Map[MClassType, Int] do
+ 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[MClassType]]): Map[MClassType, Array[nullable MClassType]] do
- var tables = new HashMap[MClassType, Array[nullable MClassType]]
+ 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 MClassType]
+ var table = new Array[nullable MType]
for mtype in mtypes do
- var color = self.coloration_result[mtype.mclass.mclass_type]
+ var color = self.coloration_result[mtype]
if table.length <= color then
for i in [table.length .. color[ do
table[i] = null
end
# Colorize a collection of elements
- fun colorize_elements(elements: Map[MClassType, Set[MClassType]]) do
+ 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.mclass.mclass_type) then continue
+ if self.coloration_result.has_key(element) then continue
var color = min_color
- while not self.is_color_free(element.mclass.mclass_type, color) do
+ while not self.is_color_free(element, color) do
color += 1
end
- coloration_result[element.mclass.mclass_type] = color
+ 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: MClassType, color: Int): Bool do
+ 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
# look for unanchored types generated by the same type
- private fun build_conflicts_graph(elements: Map[MClassType, Set[MClassType]]) do
+ 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.mclass.mclass_type, otype.mclass.mclass_type)
+ self.add_conflict(mtype, otype)
end
end
end
end
- private fun add_conflict(mtype: MClassType, otype: MClassType) do
+ 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[MClassType]
+ 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[MClassType]
+ if not self.conflicts_graph.has_key(otype) then self.conflicts_graph[otype] = new HashSet[MType]
self.conflicts_graph[otype].add(mtype)
end
end
init do end
- redef fun colorize_elements(elements: Map[MClassType, Set[MClassType]]) do
+ 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.mclass.mclass_type] = color
+ coloration_result[element] = color
color += 1
end
end
init do end
- redef fun colorize_elements(elements: Map[MClassType, Set[MClassType]]) do
+ 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.mclass.mclass_type] = color
+ coloration_result[element] = color
color += 1
end
end
end
- fun compute_masks(elements: Map[MClassType, Set[MClassType]]): Map[MClassType, Int] do
+ 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[MClassType]): Int do
+ 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.mclass.mclass_type])
+ var res = op(mask, self.coloration_result[mtype])
if used.has(res) then
break
else
return mask
end
- redef fun build_tables(elements: Map[MClassType, Set[MClassType]]): Map[MClassType, Array[nullable MClassType]] do
- var tables = new HashMap[MClassType, Array[nullable MClassType]]
+ 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 MClassType]
+ var table = new Array[nullable MType]
for mtype in mtypes do
- var color = phash(self.coloration_result[mtype.mclass.mclass_type], masks[mclasstype])
+ var color = phash(self.coloration_result[mtype], masks[mclasstype])
if table.length <= color then
for i in [table.length .. color[ do
table[i] = null
# Utils
-# An ordered set
-class OrderedSet[E: Object]
- super Array[E]
-
- init do end
-
- init from(elements: Set[E]) do
+redef class HashSet[E]
+ init from(elements: Collection[E]) do
+ init
self.add_all(elements)
end
+end
- redef fun add(e) do
- if not self.has(e) then
- super(e)
- 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
- # Linearize a set of elements
- fun linearize(sorter: AbstractSorter[E]) do
- sorter.sort(self)
+ 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
\ No newline at end of file
+end
+
+# A sorter for linearize list of classes
+private class ClassSorter
+ super AbstractSorter[MClass]
+
+ var mmodule: MModule
+
+ redef fun compare(a, b) do
+ if a == b then
+ return 0
+ 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
+
+# A sorter for reverse linearization
+private class ReverseClassSorter
+ super AbstractSorter[MClass]
+
+ var mmodule: MModule
+
+ redef fun compare(a, b) do
+ if a == b then
+ return 0
+ 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
nitlanguage / nit.git / blobdiff