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

diff --git a/src/compiler/coloring.nit b/src/compiler/coloring.nit
index 5a57774..80f29ec 100644
--- a/src/compiler/coloring.nit
+++ b/src/compiler/coloring.nit
@@ -160,9 +160,16 @@ end
 #
 # Possible colors:
 #
-# * A:0, B:1, C: 2, D: 1, E: 3, F:3, G:2, H:4
+# * A: 0
+# * B: 1
+# * C: 2
+# * D: 1
+# * E: 3
+# * F: 3
+# * G: 2
+# * H: 4
 #
-# see: Ducournau, R. (2011).
+# 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]
@@ -171,6 +178,9 @@ class POSetColorer[E: Object]
 	var is_colored = false
 
 	# Resulting ids
+	#
+	# All ids are strictly positive (`>= 1`).
+	#
 	# REQUIRE: is_colored
 	fun ids: Map[E, Int] do
 		assert is_colored
@@ -216,7 +226,7 @@ class POSetColorer[E: Object]
 		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
+			ids_cache[e] = ids_cache.length + 1
 		end
 	end
 
@@ -274,21 +284,186 @@ class POSetColorer[E: Object]
 	end
 end
 
+# Colorize elements `E` introduced by holders `H` in a `POSet`.
+#
+# Two elements cannot have the same color if they are introduced or inherited by a same holder.
+class POSetGroupColorer[H: Object, E: Object]
+
+	# The associated conflict graph containing the poset.
+	#
+	# The conflict graph is used instead of the original poset so that the conflict graph can be reused
+	# in different coloration based on the same poset.
+	var graph: POSetConflictGraph[H]
+
+	# The elements to color.
+	#
+	# For each holder, the collection of introduced elements is given.
+	#
+	# A single element must not be introduced in more than one holder.
+	var buckets: Map[H, Collection[E]]
+
+	# The associated poset.
+	#
+	# alias for `graph.poset`
+	fun poset: POSet[H] do return graph.poset
+
+	# The resulting coloring
+	#
+	# Each element from buckets is associated to its own color
+	var colors: Map[E, Int] is lazy do
+		for h in graph.poset do
+			used_colors[h] = new HashSet[Int]
+		end
+		compute_colors
+		return colors_cache
+	end
+
+	# Resulting colors
+	private var colors_cache = new HashMap[E, Int]
+
+	# Set of known used colors
+	private var used_colors = new HashMap[H, HashSet[Int]]
+
+	# Build table layout of elements `E` for the holder `h`.
+	#
+	# `null` is used to fill places without elements (holes).
+	fun build_layout(h: H): Array[nullable E]
+	do
+		var table = new Array[nullable E]
+		for s in poset[h].greaters do
+			var bucket = buckets.get_or_null(s)
+			if bucket == null then continue
+			for e in bucket do
+				var color = colors[e]
+				if table.length <= color then
+					for i in [table.length .. color[ do
+						table[i] = null
+					end
+				else
+					assert table[color] == null else print "in {h}, for {color}: {table[color] or else ""} vs {e}"
+				end
+				table[color] = e
+			end
+		end
+		return table
+	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 h in graph.order do
+			if not graph.core.has(h) then continue
+
+			var color = inherit_color(h)
+			var mincolor = color
+			var bucket = buckets.get_or_null(h)
+			if bucket == null then continue
+			var conflicts = graph.conflicts[h]
+			var parents = poset[h].greaters
+			for e in bucket do
+				color = next_free_color(color, parents)
+				color = next_free_color(color, conflicts)
+				colors_cache[e] = color
+				used_colors[h].add color
+				#print "{h}: color[{color}] <- {e}"
+				if mincolor == color then mincolor += 1
+				color += 1
+			end
+			min_colors[h] = mincolor
+		end
+	end
+
+	# Other elements inherit color from their direct parents
+	private fun colorize_set(set: Set[H]) do
+		for h in graph.order do
+			if not set.has(h) then continue
+
+			var color = inherit_color(h)
+			var mincolor = color
+			var bucket = buckets.get_or_null(h)
+			if bucket == null then continue
+			var parents = poset[h].greaters
+			for e in bucket do
+				color = next_free_color(color, parents)
+				colors_cache[e] = color
+				used_colors[h].add color
+				#print "{h}: color[{color}] <- {e} (set)"
+				if mincolor == color then mincolor += 1
+				color += 1
+			end
+			min_colors[h] = mincolor
+		end
+	end
+
+	# Get the first available free color.
+	private fun inherit_color(h: H): Int
+	do
+		var res = 0
+		for p in poset[h].direct_greaters do
+			var m = min_colors[p]
+			if m > res then res = m
+		end
+		min_colors[h] = res
+		return res
+	end
+
+	# The first available color for each holder.
+	#
+	# Is used by children to start their coloring.
+	#
+	# Is updated at the end of a coloring step.
+	private var min_colors = new HashMap[H, Int]
+
+	private fun next_free_color(color: Int, set: Collection[H]): Int do
+		loop
+			for h in set do
+				if used_colors[h].has(color) then
+					#print "\tin {h}, {color} is used"
+					color += 1
+					continue label
+				end
+			end
+			break
+		end label
+		return color
+	end
+
+	# Used for debugging only
+	fun pretty_print do
+		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}
+#
+# * 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}
+#
+# * x1: {x2, x3, x4}
+# * x2: {x1, x3}
+# * x3: {x1, x2, x4}
+# * x4: {x1, x3}
+#
 # Possible colors:
-#	x1: 0, x2: 1, x3: 2, x4: 1
+#
+# * 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]]