# See the License for the specific language governing permissions and
# limitations under the License.
-# 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)
- colorize_core_properties
- colorize_crown_properties
- end
+import poset
- # 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
+# Build a conflict graph from a POSet
+class POSetConflictGraph[E: Object]
+
+ # 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]
+
+ # 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]
+
+ # 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]
+
+ # 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]]
+
+ var poset: POSet[E]
+
+ init(poset: POSet[E]) do
+ self.poset = poset
+ extract_core
+ extract_border
+ extract_crown
+ compute_conflicts
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
-
- 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 OrderedSet[MClass]
- # 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 OrderedSet[MClass]
- # add ed1 x ed2 to conflicts graph
- for ed2 in d_ji do conflicts_graph[ed1].add(ed2)
- end
- end
+
+ # 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
end
end
-
- # Colorize properties of the core hierarchy
- private fun colorize_core_properties do
- var mclasses = core
- 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
-
- mclass.is_colorized = true
- 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])
- end
-
- # Colorize properties
- colorize_properties(mclass.methods, color) # Colorize methods
- colorize_properties(mclass.attributes, color) # Colorize attributes
- mclass.is_colorized = true
- end
- end
+
+ # 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
-
- # 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 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 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
+
+ # 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 classes
- fun colorize_classes(elements: Collection[MClass]) 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
- color += 1
- end
- element.color = color
- if color > max_color then
- max_color = color
- end
- color = min_color
- 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: 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
- 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
-
- # 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
- end
- for st in element.linear_ext do
- if st == element then continue
- if st.color == color then return false
+
+ private fun add_conflicts(es: Collection[E]) do
+ for e1 in es do
+ for e2 in es do add_conflict(e1, e2)
end
- return true
+ end
+
+ # 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
-redef class MClass
-
- # The class color
- var color: nullable Int = null
-
- # 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)
+# 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]
+
+ # Is the poset already colored?
+ var is_colored = false
+
+ # Resulting ids
+ # REQUIRE: is_colored
+ fun ids: Map[E, Int] do
+ assert is_colored
+ return ids_cache
+ end
+ private var ids_cache = new HashMap[E, Int]
+
+ # 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]
+
+ # REQUIRE: is_colored
+ fun poset: POSet[E] do
+ assert is_colored
+ return poset_cache
+ end
+ private var poset_cache: POSet[E]
+
+ # 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]]
+
+ private var graph: POSetConflictGraph[E]
+
+ init do end
+
+ # 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
+
+ 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
-
- var sorter = new LinearizationSorter(mmodule)
- sorter.sort(linear_ext)
end
- # 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)
- 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
+
+ # 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
+ colors_cache[e] = color
end
- return internal_parents.as(not null)
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)
- end
- end
+
+ # 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
+
+ # 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 internal_super_classes.as(not null)
+ return max_color + 1
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)
+
+ 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
+
+ # 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
+
+# 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
+
+ # Start bucket coloring
+ fun colorize(buckets: Map[H, Set[E]]): Map[E, Int] do
+ compute_conflicts(buckets)
+ var min_color = 0
+ for holder, hbuckets in buckets do
+ for bucket in hbuckets do
+ if colors.has_key(bucket) then continue
+ var color = min_color
+ while not is_color_free(bucket, color) do
+ color += 1
end
+ colors[bucket] = color
+ color = min_color
end
end
- return internal_subclasses.as(not null)
+ return colors
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
- end
+
+ 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 internal_methods.as(not null)
+ return true
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)
- end
+
+ 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
- return internal_attributes.as(not null)
end
- private var internal_attributes: nullable OrderedSet[MAttribute]
-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
end
+# 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]]
-#
-# Utils
-#
+ init(poset: POSet[H], conflicts: Map[H, Set[H]]) do
+ self.poset = poset
+ self.conflicts = conflicts
+ end
-# Un ordered set
-private class OrderedSet[E]
- super Array[E]
-
- redef fun add(e) do
- if not self.has(e) then
- super(e)
+ # 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
-
- # 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]
- for e in self do if not o.has(e) then res.add(e)
- return res
+
+ # 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 min + 1
end
-end
-
-
-# A sorter for linearize list of classes
-private class LinearizationSorter
- 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
- return -1
+
+ # 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 1
+ return max
end
-end
-# A sorter for reverse linearization
-private class ReverseLinearizationSorter
- 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
- return 1
+ # 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
end
- return -1
+ return true
end
-end
\ No newline at end of file
+end
+
+
nitlanguage / nit.git / blobdiff