# See the License for the specific language governing permissions and
# limitations under the License.
-# Graph coloring tools
module coloring
-import rapid_type_analysis # for type coloration
+import poset
-abstract class AbstractColoring[E: Object]
+# Build a conflict graph from a POSet
+class POSetConflictGraph[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]
+ # Core is composed by:
+ # * elements that have mutiple direct parents
+ # * parents of elements that have multiple direct parents
+ # REQUIRE: is_colored
+ var core = new HashSet[E]
- private var coloration_result: Map[E, Int] = new HashMap[E, Int]
- private var conflicts_graph_cache: nullable HashMap[E, Set[E]]
+ # Border is composed by minimal elements of the core:
+ # * that have multiple direct parents
+ # * but whose subelements are all in single inheritance
+ # REQUIRE: is_colored
+ var border = new HashSet[E]
- init do 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(", ")}"
-
- #print "conflicts"
- #for k, v in conflicts_graph do
- # if k isa MType then
- # print "{k}: {v.join(", ")}"
- # end
- #end
-
- # colorize 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 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
- 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
-
- # 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]]
- 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_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
- end
- end
- end
- end
- return conflicts_graph_cache.as(not null)
- end
-
- # 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
+ # The crown is composed by the elements that are:
+ # * not part of the core nor the border
+ # * are in single inheritance
+ # REQUIRE: is_colored
+ var crown = new HashSet[E]
- 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
+ # Conflict graph of the POSet
+ # Elements X and Y are in conflict if either:
+ # * X and Y are the same element
+ # * Y is a subelement of X
+ # * X and Y have common sub elements
+ # REQUIRE: is_colored
+ var conflicts = new HashMap[E, Set[E]]
-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
+ var poset: POSet[E]
-class TypeAndPerfectHashing
- super TypePerfectHashing
- init(mainmodule: MModule, mtypes: Set[T]) do
- super(mainmodule, mtypes)
+ init(poset: POSet[E]) do
+ self.poset = poset
+ extract_core
+ extract_border
+ extract_crown
+ compute_conflicts
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
+ # Compute the set of elements forming the core of the poset hierarchy.
+ private fun extract_core do
+ core.clear
+ for e in poset do
+ if poset[e].direct_greaters.length > 1 then
+ core.add_all(poset[e].greaters)
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
+ # Compute the set of elements composing the border of the core
+ # Elements belonging to the `border` are removed from the `core`
+ private fun extract_border do
+ border.clear
+ for e in core do
+ if not is_border(e) then continue
+ border.add(e)
end
+ for e in border do core.remove(e)
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
+ private fun is_border(e: E): Bool do
+ for child in poset[e].direct_smallers do
+ if core.has(child) then return false
end
+ return true
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)))
+ # Compute the set of elements belonging to the crown of the inheritance hierarchy.
+ private fun extract_crown do
+ crown.clear
+ for e in poset do
+ if not core.has(e) and not border.has(e) then crown.add(e)
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
+ # Check for conflict in the core.
+ # Start from border and tag every ancestors
+ private fun compute_conflicts do
+ conflicts.clear
+ for e in border do add_conflicts(poset[e].greaters)
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
+ private fun add_conflict(e, o: E) do
+ if not conflicts.has_key(e) then conflicts[e] = new HashSet[E]
+ if not conflicts.has_key(o) then conflicts[o] = new HashSet[E]
+ conflicts[e].add(o)
+ conflicts[o].add(e)
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
+ private fun add_conflicts(es: Collection[E]) do
+ for e1 in es do
+ for e2 in es do add_conflict(e1, e2)
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
- 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
- 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
+ # Used for debugging only
+ fun pretty_print do
+ #print "core: {core.join(" ")} ({core.length})"
+ #print "border: {border.join(" ")} ({border.length})"
+ #print "crown: {crown.join(" ")} ({crown.length})"
+ print "conflicts:"
+ for e, c in conflicts do print " {e}: {c.join(" ")}"
end
end
-class NaiveFTColoring
- super FTColoring
-
- init(class_coloring: ClassColoring) do end
+# Colorize elements from a POSet
+# Two elements from a POSet cannot have the same color if they share common subelements
+#
+# Example:
+# A
+# / | \
+# / | \
+# B C D
+# | /| |
+# | / | |
+# |/ | |
+# E F G
+# |
+# H
+# Conflicts:
+# A: {B, C, D, E, F, G, H}
+# B: {A, C, E, H}
+# C: {A, E, H, F}
+# D: {A, G}
+# E: {A, B, C, H}
+# F: {A, C}
+# G: {A, D}
+# H: {A, B, C, E}
+# Possible colors:
+# A:0, B:1, C: 2, D: 1, E: 3, F:3, G:2, H:4
+#
+# see:
+# Ducournau, R. (2011).
+# Coloring, a versatile technique for implementing object-oriented languages.
+# Software: Practice and Experience, 41(6), 627–659.
+class POSetColorer[E: Object]
- 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
+ # Is the poset already colored?
+ var is_colored = false
- for mclass in mclasses do
- min_color = max_color(min_color, mclasses)
- colorize_elements(self.fts(mclass), min_color)
- end
- return self.coloration_result
+ # Resulting ids
+ # REQUIRE: is_colored
+ fun ids: Map[E, Int] do
+ assert is_colored
+ return ids_cache
end
-end
-
-abstract class FTPerfectHashing
- super FTColoring
+ private var ids_cache = new HashMap[E, Int]
- 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
+ # Resulting colors
+ # REQUIRE: is_colored
+ fun colors: Map[E, Int] do
+ assert is_colored
+ return colors_cache
end
+ private var colors_cache = new HashMap[E, Int]
- 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
+ # REQUIRE: is_colored
+ fun poset: POSet[E] do
+ assert is_colored
+ return poset_cache
end
+ private var poset_cache: POSet[E]
- 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
+ # REQUIRE: is_colored
+ fun conflicts: Map[E, Set[E]] do
+ assert is_colored
+ return conflicts_cache
end
+ private var conflicts_cache: Map[E, Set[E]]
- 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
- 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]]
+ private var graph: POSetConflictGraph[E]
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
+ # Start coloring on given POSet
+ fun colorize(poset: POSet[E]) do
+ poset_cache = poset
+ graph = new POSetConflictGraph[E](poset)
+ allocate_ids
+ compute_colors
+ conflicts_cache = graph.conflicts
+ is_colored = true
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
+ private fun allocate_ids do
+ ids_cache.clear
+ var elements = new HashSet[E].from(poset_cache.to_a)
+ for e in poset_cache.linearize(elements) do
+ ids_cache[e] = ids_cache.length
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
+ # Colorize core, border and crown in that order
+ private fun compute_colors do
+ colors_cache.clear
+ colorize_core
+ colorize_set(graph.border)
+ colorize_set(graph.crown)
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
+ # Core elements cannot have the same color than:
+ # * one of their parents
+ # * one of their conflicting elements
+ private fun colorize_core do
+ for e in poset_cache.linearize(graph.core) do
+ var color = min_color(e)
+ var conflicts = graph.conflicts[e]
+ while not is_color_free(color, conflicts) do
color += 1
end
- coloration_result[element] = color
- color = min_color
+ colors_cache[e] = 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
+ # Other elements inherit color fron their direct parents
+ private fun colorize_set(set: Set[E]) do
+ for e in poset_cache.linearize(set) do colors_cache[e] = min_color(e)
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
+ # Get the next minimal color from direct parents
+ private fun min_color(e: E): Int do
+ var max_color = -1
+ for p in poset_cache[e].direct_greaters do
+ if not colors_cache.has_key(p) then continue
+ var color = colors_cache[p]
+ if color > max_color then max_color = color
end
+ return max_color + 1
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)
+ private fun is_color_free(color: Int, set: Collection[E]): Bool do
+ for e in set do
+ if colors_cache.has_key(e) and colors_cache[e] == color then return false
+ end
+ return true
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
+ # Used for debugging only
+ fun pretty_print do
+ print "ids:"
+ for e, id in ids do print " {e}: {id}"
+ print "colors:"
+ for e, c in colors do print " {e}: {c}"
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]]
+# Colorize a collection of buckets
+# Two elements cannot have the same color if they both appear in the same bucket
+# No coloring order is garantied
+#
+# Example:
+# buckets[A] = {x1, x2}
+# buckets[B] = {x1, x3, x4}
+# buckets[C] = {x2, x3}
+# Conflicts:
+# x1: {x2, x3, x4}
+# x2: {x1, x3}
+# x3: {x1, x2, x4}
+# x4: {x1, x3}
+# Possible colors:
+# x1: 0, x2: 1, x3: 2, x4: 1
+class BucketsColorer[H: Object, E: Object]
+ private var colors = new HashMap[E, Int]
+ private var conflicts = new HashMap[E, Set[E]]
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]]
-
- 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 tables
- end
-
- # Colorize a collection of elements
- fun colorize_elements(elements: Map[MClassType, Set[MType]]) do
+ # Start bucket coloring
+ fun colorize(buckets: Map[H, Set[E]]): Map[E, Int] do
+ compute_conflicts(buckets)
var min_color = 0
- for mclasstype, mclasstypes in elements do
- for element in mclasstypes do
- if self.coloration_result.has_key(element) then continue
+ for holder, hbuckets in buckets do
+ for bucket in hbuckets do
+ if colors.has_key(bucket) then continue
var color = min_color
- while not self.is_color_free(element, color) do
+ while not is_color_free(bucket, color) do
color += 1
end
- coloration_result[element] = color
+ colors[bucket] = color
color = min_color
end
end
+ return colors
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
+ private fun is_color_free(bucket: E, color: Int): Bool do
+ if conflicts.has_key(bucket) then
+ for other in conflicts[bucket] do
+ if colors.has_key(other) and colors[other] == color then return false
end
end
return true
end
- # 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)
+ private fun compute_conflicts(buckets: Map[H, Set[E]]) do
+ conflicts.clear
+ for holder, hbuckets in buckets do
+ for bucket in hbuckets do
+ if not conflicts.has_key(bucket) then conflicts[bucket] = new HashSet[E]
+ for obucket in hbuckets do
+ if obucket == bucket then continue
+ if not conflicts.has_key(obucket) then conflicts[obucket] = new HashSet[E]
+ conflicts[bucket].add(obucket)
+ conflicts[obucket].add(bucket)
end
end
end
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
+# Colorize a collection of buckets using a poset and a conflict graph
+# Two elements cannot have the same color if they both appear in the same bucket
+# The use of a POSet hierarchy optimize the coloring
+# Buckets elements are colored using linearization order starting
+class POSetBucketsColorer[H: Object, E: Object]
+ private var colors = new HashMap[E, Int]
+ private var poset: POSet[H]
+ private var conflicts: Map[H, Set[H]]
- 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
+ init(poset: POSet[H], conflicts: Map[H, Set[H]]) do
+ self.poset = poset
+ self.conflicts = conflicts
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
+ # Colorize buckets using the POSet and conflict graph
+ fun colorize(buckets: Map[H, Set[E]]): Map[E, Int] do
+ colors.clear
+ for h in poset.linearize(buckets.keys) do
+ var color = min_color(poset[h].direct_greaters, buckets)
+ for bucket in buckets[h] do
+ if colors.has_key(bucket) then continue
+ while not is_color_free(color, h, buckets) do color += 1
+ colors[bucket] = color
color += 1
end
end
+ return colors
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)
+ # Get the next available color considering used colors by other buckets
+ private fun min_color(others: Collection[H], buckets: Map[H, Set[E]]): Int do
+ var min = -1
+ for holder in others do
+ var color = max_color(holder, buckets)
+ if color > min then min = color
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 mask
- end
-
- 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 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 UnanchoredTypeModPerfectHashing
- super UnanchoredTypePerfectHashing
- init do end
- redef fun op(mask, id) do return mask % id
-end
-
-class UnanchoredTypeAndPerfectHashing
- super UnanchoredTypePerfectHashing
- init do end
- redef fun op(mask, id) do return mask.bin_and(id)
-end
-
-
-# Utils
-
-redef class HashSet[E]
- init from(elements: Collection[E]) do
- init
- self.add_all(elements)
+ return min + 1
end
-end
-redef class Array[E]
- init from(elements: Collection[E]) do
- init
- self.add_all(elements)
- end
-
- # 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
+ # Return the max color used by a class
+ private fun max_color(holder: H, buckets: Map[H, Set[E]]): Int do
+ var max = -1
+ for bucket in buckets[holder] do
+ if not colors.has_key(bucket) then continue
+ var color = colors[bucket]
+ if color > max then max = color
end
- return self.super_mtypes_cache[mtype]
+ return max
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
+ # Check if the color is free for this holder
+ private fun is_color_free(color: Int, holder: H, buckets: Map[H, Set[E]]): Bool do
+ if not conflicts.has_key(holder) then return true
+ for conflict in conflicts[holder] do
+ for bucket in buckets[conflict] do
+ if not colors.has_key(bucket) then continue
+ if colors[bucket] == color then return false
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 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
+ return true
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