1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # Licensed under the Apache License, Version 2.0 (the "License");
4 # you may not use this file except in compliance with the License.
5 # You may obtain a copy of the License at
7 # http://www.apache.org/licenses/LICENSE-2.0
9 # Unless required by applicable law or agreed to in writing, software
10 # distributed under the License is distributed on an "AS IS" BASIS,
11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 # See the License for the specific language governing permissions and
13 # limitations under the License.
19 # Build a conflict graph from a POSet
20 class POSetConflictGraph[E
]
22 # Core is composed by:
23 # * elements that have mutiple direct parents
24 # * parents of elements that have multiple direct parents
26 var core
= new HashSet[E
]
28 # Border is composed by minimal elements of the core:
29 # * that have multiple direct parents
30 # * but whose subelements are all in single inheritance
32 var border
= new HashSet[E
]
34 # The crown is composed by the elements that are:
35 # * not part of the core nor the border
36 # * are in single inheritance
38 var crown
= new HashSet[E
]
40 # Conflict graph of the POSet
41 # Elements X and Y are in conflict if either:
42 # * X and Y are the same element
43 # * Y is a subelement of X
44 # * X and Y have common sub elements
46 var conflicts
= new HashMap[E
, Set[E
]]
48 # The associated poset
51 # The linearisation order to visit elements in the poset
52 var order
: Array[E
] is noinit
59 order
= poset
.linearize
(poset
)
62 # Compute the set of elements forming the core of the poset hierarchy.
63 private fun extract_core
do
66 if poset
[e
].direct_greaters
.length
> 1 then
67 core
.add_all
(poset
[e
].greaters
)
72 # Compute the set of elements composing the border of the core
73 # Elements belonging to the `border` are removed from the `core`
74 private fun extract_border
do
77 if not is_border
(e
) then continue
80 for e
in border
do core
.remove
(e
)
83 private fun is_border
(e
: E
): Bool do
84 for child
in poset
[e
].direct_smallers
do
85 if core
.has
(child
) then return false
90 # Compute the set of elements belonging to the crown of the inheritance hierarchy.
91 private fun extract_crown
do
94 if not core
.has
(e
) and not border
.has
(e
) then crown
.add
(e
)
98 # Check for conflict in the core.
99 # Start from border and tag every ancestors
100 private fun compute_conflicts
do
102 for e
in border
do add_conflicts
(poset
[e
].greaters
)
105 private fun add_conflict
(e
, o
: E
) do
106 if not conflicts
.has_key
(e
) then conflicts
[e
] = new HashSet[E
]
107 if not conflicts
.has_key
(o
) then conflicts
[o
] = new HashSet[E
]
112 private fun add_conflicts
(es
: Collection[E
]) do
114 for e2
in es
do add_conflict
(e1
, e2
)
118 # Used for debugging only
120 #print "core: {core.join(" ")} ({core.length})"
121 #print "border: {border.join(" ")} ({border.length})"
122 #print "crown: {crown.join(" ")} ({crown.length})"
124 for e
, c
in conflicts
do print
" {e or else "NULL"}: {c.join(" ")}"
129 fun to_conflict_graph
: POSetConflictGraph[E
] do return new POSetConflictGraph[E
](self)
132 # Colorize elements from a POSet
133 # Two elements from a POSet cannot have the same color if they share common subelements
152 # * A: {B, C, D, E, F, G, H}
172 # SEE: Ducournau, R. (2011).
173 # Coloring, a versatile technique for implementing object-oriented languages.
174 # Software: Practice and Experience, 41(6), 627–659.
175 class POSetColorer[E
: Object]
177 # Is the poset already colored?
178 var is_colored
= false
182 # All ids are strictly positive (`>= 1`).
184 # REQUIRE: is_colored
185 fun ids
: Map[E
, Int] do
189 private var ids_cache
= new HashMap[E
, Int]
192 # REQUIRE: is_colored
193 fun colors
: Map[E
, Int] do
197 private var colors_cache
= new HashMap[E
, Int]
199 # REQUIRE: is_colored
200 fun poset
: POSet[E
] do
204 private var poset_cache
: POSet[E
] is noinit
206 # REQUIRE: is_colored
207 fun conflicts
: Map[E
, Set[E
]] do
209 return conflicts_cache
211 private var conflicts_cache
: Map[E
, Set[E
]] is noinit
213 private var graph
: POSetConflictGraph[E
] is noinit
215 # Start coloring on given POSet
216 fun colorize
(poset
: POSet[E
]) do
218 graph
= new POSetConflictGraph[E
](poset
)
221 conflicts_cache
= graph
.conflicts
225 private fun allocate_ids
do
227 var elements
= new HashSet[E
].from
(poset_cache
.to_a
)
228 for e
in poset_cache
.linearize
(elements
) do
229 ids_cache
[e
] = ids_cache
.length
+ 1
233 # Colorize core, border and crown in that order
234 private fun compute_colors
do
237 colorize_set
(graph
.border
)
238 colorize_set
(graph
.crown
)
241 # Core elements cannot have the same color than:
242 # * one of their parents
243 # * one of their conflicting elements
244 private fun colorize_core
do
245 for e
in poset_cache
.linearize
(graph
.core
) do
246 var color
= min_color
(e
)
247 var conflicts
= graph
.conflicts
[e
]
248 while not is_color_free
(color
, conflicts
) do
251 colors_cache
[e
] = color
255 # Other elements inherit color fron their direct parents
256 private fun colorize_set
(set
: Set[E
]) do
257 for e
in poset_cache
.linearize
(set
) do colors_cache
[e
] = min_color
(e
)
260 # Get the next minimal color from direct parents
261 private fun min_color
(e
: E
): Int do
263 for p
in poset_cache
[e
].direct_greaters
do
264 if not colors_cache
.has_key
(p
) then continue
265 var color
= colors_cache
[p
]
266 if color
> max_color
then max_color
= color
271 private fun is_color_free
(color
: Int, set
: Collection[E
]): Bool do
273 if colors_cache
.has_key
(e
) and colors_cache
[e
] == color
then return false
278 # Used for debugging only
281 for e
, id
in ids
do print
" {e}: {id}"
283 for e
, c
in colors
do print
" {e}: {c}"
287 # Colorize elements `E` introduced by holders `H` in a `POSet`.
289 # Two elements cannot have the same color if they are introduced or inherited by a same holder.
290 class POSetGroupColorer[H
: Object, E
: Object]
292 # The associated conflict graph containing the poset.
294 # The conflict graph is used instead of the original poset so that the conflict graph can be reused
295 # in different coloration based on the same poset.
296 var graph
: POSetConflictGraph[H
]
298 # The elements to color.
300 # For each holder, the collection of introduced elements is given.
302 # A single element must not be introduced in more than one holder.
303 var buckets
: Map[H
, Collection[E
]]
305 # The associated poset.
307 # alias for `graph.poset`
308 fun poset
: POSet[H
] do return graph
.poset
310 # The resulting coloring
312 # Each element from buckets is associated to its own color
313 var colors
: Map[E
, Int] is lazy
do
314 for h
in graph
.poset
do
315 used_colors
[h
] = new HashSet[Int]
322 private var colors_cache
= new HashMap[E
, Int]
324 # Set of known used colors
325 private var used_colors
= new HashMap[H
, HashSet[Int]]
327 # Build table layout of elements `E` for the holder `h`.
329 # `null` is used to fill places without elements (holes).
330 fun build_layout
(h
: H
): Array[nullable E
]
332 var table
= new Array[nullable E
]
333 for s
in poset
[h
].greaters
do
334 var bucket
= buckets
.get_or_null
(s
)
335 if bucket
== null then continue
337 var color
= colors
[e
]
338 if table
.length
<= color
then
339 for i
in [table
.length
.. color
[ do
343 assert table
[color
] == null else print
"in {h}, for {color}: {table[color] or else ""} vs {e}"
351 # Colorize core, border and crown in that order
352 private fun compute_colors
do
355 colorize_set
(graph
.border
)
356 colorize_set
(graph
.crown
)
359 # Core elements cannot have the same color than:
360 # * one of their parents
361 # * one of their conflicting elements
362 private fun colorize_core
do
363 for h
in graph
.order
do
364 if not graph
.core
.has
(h
) then continue
366 var color
= inherit_color
(h
)
368 var bucket
= buckets
.get_or_null
(h
)
369 if bucket
== null then continue
370 var conflicts
= graph
.conflicts
[h
]
371 var parents
= poset
[h
].greaters
373 color
= next_free_color
(color
, parents
)
374 color
= next_free_color
(color
, conflicts
)
375 colors_cache
[e
] = color
376 used_colors
[h
].add color
377 #print "{h}: color[{color}] <- {e}"
378 if mincolor
== color
then mincolor
+= 1
381 min_colors
[h
] = mincolor
385 # Other elements inherit color from their direct parents
386 private fun colorize_set
(set
: Set[H
]) do
387 for h
in graph
.order
do
388 if not set
.has
(h
) then continue
390 var color
= inherit_color
(h
)
392 var bucket
= buckets
.get_or_null
(h
)
393 if bucket
== null then continue
394 var parents
= poset
[h
].greaters
396 color
= next_free_color
(color
, parents
)
397 colors_cache
[e
] = color
398 used_colors
[h
].add color
399 #print "{h}: color[{color}] <- {e} (set)"
400 if mincolor
== color
then mincolor
+= 1
403 min_colors
[h
] = mincolor
407 # Get the first available free color.
408 private fun inherit_color
(h
: H
): Int
411 for p
in poset
[h
].direct_greaters
do
412 var m
= min_colors
[p
]
413 if m
> res
then res
= m
419 # The first available color for each holder.
421 # Is used by children to start their coloring.
423 # Is updated at the end of a coloring step.
424 private var min_colors
= new HashMap[H
, Int]
426 private fun next_free_color
(color
: Int, set
: Collection[H
]): Int do
429 if used_colors
[h
].has
(color
) then
430 #print "\tin {h}, {color} is used"
440 # Used for debugging only
443 for e
, c
in colors
do print
" {e}: {c}"
447 # Colorize a collection of buckets
448 # Two elements cannot have the same color if they both appear in the same bucket
449 # No coloring order is garantied
453 # * buckets[A] = {x1, x2}
454 # * buckets[B] = {x1, x3, x4}
455 # * buckets[C] = {x2, x3}
466 # * x1: 0, x2: 1, x3: 2, x4: 1
467 class BucketsColorer[H
: Object, E
: Object]
468 private var colors
= new HashMap[E
, Int]
469 private var conflicts
= new HashMap[E
, Set[E
]]
471 # Start bucket coloring
472 fun colorize
(buckets
: Map[H
, Set[E
]]): Map[E
, Int] do
473 compute_conflicts
(buckets
)
475 for holder
, hbuckets
in buckets
do
476 for bucket
in hbuckets
do
477 if colors
.has_key
(bucket
) then continue
478 var color
= min_color
479 while not is_color_free
(bucket
, color
) do
482 colors
[bucket
] = color
489 private fun is_color_free
(bucket
: E
, color
: Int): Bool do
490 if conflicts
.has_key
(bucket
) then
491 for other
in conflicts
[bucket
] do
492 if colors
.has_key
(other
) and colors
[other
] == color
then return false
498 private fun compute_conflicts
(buckets
: Map[H
, Set[E
]]) do
500 for holder
, hbuckets
in buckets
do
501 for bucket
in hbuckets
do
502 if not conflicts
.has_key
(bucket
) then conflicts
[bucket
] = new HashSet[E
]
503 for obucket
in hbuckets
do
504 if obucket
== bucket
then continue
505 if not conflicts
.has_key
(obucket
) then conflicts
[obucket
] = new HashSet[E
]
506 conflicts
[bucket
].add
(obucket
)
507 conflicts
[obucket
].add
(bucket
)
514 # Colorize a collection of buckets using a poset and a conflict graph
515 # Two elements cannot have the same color if they both appear in the same bucket
516 # The use of a POSet hierarchy optimize the coloring
517 # Buckets elements are colored using linearization order starting
518 class POSetBucketsColorer[H
: Object, E
: Object]
519 private var colors
= new HashMap[E
, Int]
520 private var poset
: POSet[H
]
521 private var conflicts
: Map[H
, Set[H
]]
523 # Colorize buckets using the POSet and conflict graph
524 fun colorize
(buckets
: Map[H
, Set[E
]]): Map[E
, Int] do
526 for h
in poset
.linearize
(buckets
.keys
) do
527 var color
= min_color
(poset
[h
].direct_greaters
, buckets
)
528 for bucket
in buckets
[h
] do
529 if colors
.has_key
(bucket
) then continue
530 while not is_color_free
(color
, h
, buckets
) do color
+= 1
531 colors
[bucket
] = color
538 # Get the next available color considering used colors by other buckets
539 private fun min_color
(others
: Collection[H
], buckets
: Map[H
, Set[E
]]): Int do
541 for holder
in others
do
542 var color
= max_color
(holder
, buckets
)
543 if color
> min
then min
= color
548 # Return the max color used by a class
549 private fun max_color
(holder
: H
, buckets
: Map[H
, Set[E
]]): Int do
551 for bucket
in buckets
[holder
] do
552 if not colors
.has_key
(bucket
) then continue
553 var color
= colors
[bucket
]
554 if color
> max
then max
= color
559 # Check if the color is free for this holder
560 private fun is_color_free
(color
: Int, holder
: H
, buckets
: Map[H
, Set[E
]]): Bool do
561 if not conflicts
.has_key
(holder
) then return true
562 for conflict
in conflicts
[holder
] do
563 for bucket
in buckets
[conflict
] do
564 if not colors
.has_key
(bucket
) then continue
565 if colors
[bucket
] == color
then return false