X-Git-Url: http://nitlanguage.org

diff --git a/src/coloring.nit b/src/coloring.nit
index 00b7880..0b4532d 100644
--- a/src/coloring.nit
+++ b/src/coloring.nit
@@ -12,358 +12,381 @@
 # 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
+
+