redef fun op(mask, id) do return mask.bin_and(id)
end
-# Live Entries coloring
-class LiveEntryColoring
-
- private var coloration_result: Map[MType, Int] = new HashMap[MType, Int]
- private var conflicts_graph_cache: nullable HashMap[MType, Set[MType]]
- var livetypes_tables_sizes: nullable Map[MClass, Array[Int]]
-
- init do end
-
- fun colorize(elements: Collection[MType]): Map[MType, Int] do
- # compute conflicts
- build_conflicts_graph(elements)
-
- # colorize graph
- colorize_elements(elements)
-
- return coloration_result
- end
-
- # Build type tables
- fun build_livetype_tables(mtypes: Set[MType]): Map[MClass, Array[nullable Object]] do
- var livetypes_tables = new HashMap[MClass, Array[nullable Object]]
- self.livetypes_tables_sizes = new HashMap[MClass, Array[Int]]
-
- for mtype in mtypes do
- if mtype isa MGenericType then
- var table: Array[nullable Object]
- var sizes: Array[Int]
- if livetypes_tables.has_key(mtype.mclass) then
- table = livetypes_tables[mtype.mclass]
- else
- table = new Array[nullable Object]
- livetypes_tables[mtype.mclass] = table
- end
- if livetypes_tables_sizes.has_key(mtype.mclass) then
- sizes = livetypes_tables_sizes[mtype.mclass]
- else
- sizes = new Array[Int]
- livetypes_tables_sizes[mtype.mclass] = sizes
- end
- build_livetype_table(mtype, 0, table, sizes)
- end
- end
-
- return livetypes_tables
- end
-
- # Build live gentype table recursively
- private fun build_livetype_table(mtype: MGenericType, current_rank: Int, table: Array[nullable Object], sizes: Array[Int]) do
- var ft = mtype.arguments[current_rank]
- if not self.coloration_result.has_key(ft) then return
- var color = self.coloration_result[ft]
-
- if current_rank >= sizes.length then
- sizes[current_rank] = color + 1
- else if color >= sizes[current_rank] then
- sizes[current_rank] = color + 1
- end
-
- if color > table.length then
- for i in [table.length .. color[ do table[i] = null
- end
-
- if current_rank == mtype.arguments.length - 1 then
- table[color] = mtype
- else
- var ft_table: Array[nullable Object]
- if color < table.length and table[color] != null then
- ft_table = table[color].as(Array[nullable Object])
- else
- ft_table = new Array[nullable Object]
- end
- table[color] = ft_table
- build_livetype_table(mtype, current_rank + 1, ft_table, sizes)
- end
- end
-
- # Colorize a collection of elements
- fun colorize_elements(elements: Collection[MType]) do
- var min_color = 0
-
- for element in elements do
- var color = min_color
- while not self.is_color_free(element, color) do
- color += 1
- end
- coloration_result[element] = color
- color = min_color
- end
- end
-
- # Check if a related element to the element already use the color
- private fun is_color_free(element: MType, color: Int): Bool do
- if conflicts_graph.has_key(element) then
- for st in conflicts_graph[element] do
- if coloration_result.has_key(st) and coloration_result[st] == color then return false
- end
- end
- return true
- end
-
- # look for types in the same generic signatures
- private fun build_conflicts_graph(elements: Collection[MType]) do
- # regroup types by classes
- var genclasses = new HashMap[MClass, Set[MType]]
- for e in elements do
- if e isa MGenericType then
- if not genclasses.has_key(e.mclass) then
- genclasses[e.mclass] = new HashSet[MType]
- end
- genclasses[e.mclass].add(e)
- end
- end
-
- # for each class
- self.conflicts_graph_cache = new HashMap[MType, Set[MType]]
- for mclass, mtypes in genclasses do
- # for each rank
- for rank in [0..mclass.arity[ do
- # for each live type
- for mtype in mtypes do
- var mclasstype: MClassType
- if mtype isa MNullableType then
- mclasstype = mtype.mtype.as(MClassType)
- else
- mclasstype = mtype.as(MClassType)
- end
- var ft = mclasstype.arguments[rank]
- for otype in mtypes do
- if mtype == otype then continue
- var oclasstype: MClassType
- if otype isa MNullableType then
- oclasstype = otype.mtype.as(MClassType)
- else
- oclasstype = otype.as(MClassType)
- end
- var oft = oclasstype.arguments[rank]
- self.add_conflict(ft, oft)
- end
- end
- end
- end
- end
-
- private fun add_conflict(mtype: MType, otype: MType) do
- if mtype == otype then return
- if not self.conflicts_graph_cache.has_key(mtype) then self.conflicts_graph_cache[mtype] = new HashSet[MType]
- self.conflicts_graph_cache[mtype].add(otype)
- if not self.conflicts_graph_cache.has_key(otype) then self.conflicts_graph_cache[otype] = new HashSet[MType]
- self.conflicts_graph_cache[otype].add(mtype)
- end
- private fun conflicts_graph: Map[MType, Set[MType]] do return conflicts_graph_cache.as(not null)
-end
-
-class NaiveLiveEntryColoring
- super LiveEntryColoring
-
- init do end
-
- redef fun colorize_elements(elements: Collection[MType]) do
- var color = 0
- for element in elements do
- coloration_result[element] = color
- color += 1
- end
- end
-end
-
# live unanchored coloring
class UnanchoredTypeColoring
nitlanguage / nit.git / commitdiff