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.
15 # Graph coloring tools
18 import rapid_type_analysis
# for type coloration
20 abstract class AbstractColoring[E
: Object]
22 private var sorter
: AbstractSorter[E
]
23 private var reverse_sorter
: AbstractSorter[E
]
25 private var core
: OrderedSet[E
] = new OrderedSet[E
]
26 private var crown
: OrderedSet[E
] = new OrderedSet[E
]
27 private var border
: OrderedSet[E
] = new OrderedSet[E
]
29 private var coloration_result
: Map[E
, Int] = new HashMap[E
, Int]
30 private var conflicts_graph_cache
: nullable HashMap[E
, Set[E
]]
32 init(sorter
: AbstractSorter[E
], reverse_sorter
: AbstractSorter[E
]) do
34 self.reverse_sorter
= reverse_sorter
37 fun colorize
(elements
: Collection[E
]): Map[E
, Int] do
38 # tag each element as part of group core, crown or border
43 #print "core: {core.join(", ")}"
44 #print "border: {border.join(", ")}"
45 #print "crown: {crown.join(", ")}"
47 # sort by reverse linearization order
48 reverse_sorter
.sort
(core
)
49 reverse_sorter
.sort
(border
)
50 reverse_sorter
.sort
(crown
)
53 #for k, v in conflicts_graph do
55 # print "{k}: {v.join(", ")}"
60 colorize_elements
(core
)
61 colorize_elements
(border
)
62 colorize_elements
(crown
)
64 return coloration_result
67 # Colorize a collection of elements
68 private fun colorize_elements
(elements
: Collection[E
]) do
71 for element
in elements
do
73 while not self.is_color_free
(element
, color
) do
76 coloration_result
[element
] = color
81 # Check if a related element to the element already use the color
82 private fun is_color_free
(element
: E
, color
: Int): Bool do
83 if conflicts_graph
.has_key
(element
) then
84 for st
in conflicts_graph
[element
] do
85 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
88 for st
in self.super_elements
(element
) do
89 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
94 # Tag element as core, crown or border
95 private fun tag_element
(element
: E
) do
96 # Check if sub elements are all in single inheritance
97 var all_subelements_si
= true
98 for subelem
in self.sub_elements
(element
) do
99 if self.is_element_mi
(subelem
) then
100 all_subelements_si
= false
105 # Tag as core, crown or border
106 if self.is_element_mi
(element
) then
107 core
.add_all
(self.super_elements
(element
))
109 if all_subelements_si
then
112 else if not all_subelements_si
then
113 core
.add_all
(self.super_elements
(element
))
120 # Conflicts graph of elements hierarchy (two types are in conflict if they have common subelements)
121 private fun conflicts_graph
: Map[E
, Set[E
]] do
122 if self.conflicts_graph_cache
== null then
123 self.conflicts_graph_cache
= new HashMap[E
, HashSet[E
]]
124 for t
in self.core
do
125 for i
in self.linear_extension
(t
) do
126 if t
== i
then continue
128 var lin_i
= self.linear_extension
(i
)
130 for j
in self.linear_extension
(t
) do
131 if i
== j
or j
== t
then continue
132 var lin_j
= self.linear_extension
(j
)
134 var d_ij
= lin_i
- lin_j
135 var d_ji
= lin_j
- lin_i
138 if not conflicts_graph_cache
.has_key
(ed1
) then conflicts_graph_cache
[ed1
] = new HashSet[E
]
139 # add ed1 x ed2 to conflicts graph
140 for ed2
in d_ji
do conflicts_graph_cache
[ed1
].add
(ed2
)
143 if not conflicts_graph_cache
.has_key
(ed1
) then conflicts_graph_cache
[ed1
] = new HashSet[E
]
144 # add ed1 x ed2 to conflicts graph
145 for ed2
in d_ji
do conflicts_graph_cache
[ed1
].add
(ed2
)
151 return conflicts_graph_cache
.as(not null)
154 # cache for linear_extensions
155 private var linear_extensions_cache
: Map[E
, OrderedSet[E
]] = new HashMap[E
, OrderedSet[E
]]
157 # Return a linear_extension of super_elements of the element
158 private fun linear_extension
(element
: E
): OrderedSet[E
] do
159 if not self.linear_extensions_cache
.has_key
(element
) then
160 var lin
= new OrderedSet[E
]
162 lin
.add_all
(self.super_elements
(element
))
163 self.sorter
.sort
(lin
)
164 self.linear_extensions_cache
[element
] = lin
166 return self.linear_extensions_cache
[element
]
169 # Return all super elements (directs and indirects) of an element
170 private fun super_elements
(element
: E
): Collection[E
] is abstract
172 # Return all sub elements (directs and indirects) of an element
173 private fun sub_elements
(element
: E
): Collection[E
] is abstract
175 # Is the element in multiple inheritance ?
176 private fun is_element_mi
(element
: E
): Bool is abstract
179 # MClassType coloring
181 super AbstractColoring[MClassType]
185 private var mmodule
: MModule
186 private var mtypes
: Set[MClassType] = new HashSet[MClassType]
189 private var super_elements_cache
: Map[T
, Set[T
]] = new HashMap[T
, Set[T
]]
190 private var sub_elements_cache
: Map[T
, Set[T
]] = new HashMap[T
, Set[T
]]
192 init(mainmodule
: MModule, runtime_type_analysis
: RapidTypeAnalysis) do
193 super(new TypeSorter(mainmodule
), new ReverseTypeSorter(mainmodule
))
194 self.mmodule
= mainmodule
195 self.mtypes
.add_all
(runtime_type_analysis
.live_types
)
196 self.mtypes
.add_all
(runtime_type_analysis
.live_cast_types
)
200 private fun build_type_tables
(mtypes
: Set[T
], colors
: Map[T
, Int]): Map[T
, Array[nullable T
]] do
201 var tables
= new HashMap[T
, Array[nullable T
]]
203 for mtype
in mtypes
do
204 var table
= new Array[nullable T
]
205 var supers
= new HashSet[T
]
206 supers
.add_all
(self.super_elements
(mtype
))
209 var color
= colors
[sup
]
210 if table
.length
<= color
then
211 for i
in [table
.length
.. color
[ do
217 tables
[mtype
] = table
222 redef fun super_elements
(element
) do
223 if not self.super_elements_cache
.has_key
(element
) then
224 var supers
= new HashSet[T
]
225 for mtype
in self.mtypes
do
226 if element
== mtype
then continue
227 if element
.is_subtype
(self.mmodule
, null, mtype
) then
231 self.super_elements_cache
[element
] = supers
233 return self.super_elements_cache
[element
]
236 # Return all direct super elements of an element
237 redef fun is_element_mi
(element
) do
238 return self.mmodule
.flatten_mclass_hierarchy
[element
.mclass
].direct_greaters
.length
> 1
241 # Return all sub elements (directs and indirects) of an element
242 redef fun sub_elements
(element
) do
243 if not self.sub_elements_cache
.has_key
(element
) then
244 var subs
= new HashSet[T
]
245 for mtype
in self.mtypes
do
246 if element
== mtype
then continue
247 if mtype
.is_subtype
(self.mmodule
, null, element
) then
251 self.sub_elements_cache
[element
] = subs
253 return self.sub_elements_cache
[element
]
257 # A sorter for linearize list of types
258 private class TypeSorter
259 super AbstractSorter[MClassType]
261 private var mmodule
: MModule
263 init(mmodule
: MModule) do self.mmodule
= mmodule
265 redef fun compare
(a
, b
) do
268 else if a
.is_subtype
(self.mmodule
, null, b
) then
275 # A sorter for reverse linearization
276 private class ReverseTypeSorter
279 redef fun compare
(a
, b
) do
282 else if a
.is_subtype
(self.mmodule
, null, b
) then
291 super AbstractColoring[MClass]
295 private var mmodule
: MModule
298 private var super_elements_cache
: Map[T
, Set[T
]] = new HashMap[T
, Set[T
]]
299 private var parent_elements_cache
: Map[T
, Set[T
]] = new HashMap[T
, Set[T
]]
300 private var sub_elements_cache
: Map[T
, Set[T
]] = new HashMap[T
, Set[T
]]
302 init(mainmodule
: MModule) do
303 super(new ClassSorter(mainmodule
), new ReverseClassSorter(mainmodule
))
304 self.mmodule
= mainmodule
308 private fun build_type_tables
(mclasses
: Array[T
], colors
: Map[T
, Int]): Map[T
, Array[nullable T
]] do
309 var tables
= new HashMap[T
, Array[nullable T
]]
311 for mclasse
in mclasses
do
312 var table
= new Array[nullable T
]
313 var supers
= new HashSet[T
]
314 supers
.add_all
(self.super_elements
(mclasse
))
317 var color
= colors
[sup
]
318 if table
.length
<= color
then
319 for i
in [table
.length
.. color
[ do
325 tables
[mclasse
] = table
330 redef fun super_elements
(element
) do
331 if not self.super_elements_cache
.has_key
(element
) then
332 var supers
= new HashSet[T
]
333 if self.mmodule
.flatten_mclass_hierarchy
.has
(element
) then
334 for sup
in self.mmodule
.flatten_mclass_hierarchy
[element
].greaters
do
335 if element
== sup
then continue
339 self.super_elements_cache
[element
] = supers
341 return self.super_elements_cache
[element
]
344 private fun parent_elements
(element
: T
): Set[T
] do
345 if not self.parent_elements_cache
.has_key
(element
) then
346 var parents
= new HashSet[T
]
347 if self.mmodule
.flatten_mclass_hierarchy
.has
(element
) then
348 for parent
in self.mmodule
.flatten_mclass_hierarchy
[element
].direct_greaters
do
349 if element
== parent
then continue
353 self.parent_elements_cache
[element
] = parents
355 return self.parent_elements_cache
[element
]
358 # Return all sub elements (directs and indirects) of an element
359 redef fun sub_elements
(element
) do
360 if not self.sub_elements_cache
.has_key
(element
) then
361 var subs
= new HashSet[T
]
362 if self.mmodule
.flatten_mclass_hierarchy
.has
(element
) then
363 for sub
in self.mmodule
.flatten_mclass_hierarchy
[element
].smallers
do
367 self.sub_elements_cache
[element
] = subs
369 return self.sub_elements_cache
[element
]
372 # Return all direct super elements of an element
373 redef fun is_element_mi
(element
) do
374 if not self.mmodule
.flatten_mclass_hierarchy
.has
(element
) then return false
375 return self.mmodule
.flatten_mclass_hierarchy
[element
].direct_greaters
.length
> 1
379 # A sorter for linearize list of classes
380 private class ClassSorter
381 super AbstractSorter[MClass]
385 redef fun compare
(a
, b
) do
388 else if self.mmodule
.flatten_mclass_hierarchy
.has
(a
) and self.mmodule
.flatten_mclass_hierarchy
[a
].greaters
.has
(b
) then
395 # A sorter for reverse linearization
396 private class ReverseClassSorter
397 super AbstractSorter[MClass]
401 redef fun compare
(a
, b
) do
404 else if self.mmodule
.flatten_mclass_hierarchy
.has
(a
) and self.mmodule
.flatten_mclass_hierarchy
[a
].greaters
.has
(b
) then
412 class PropertyColoring
414 type MPROP: MProperty
415 type MPROPDEF: MPropDef
417 private var class_coloring
: ClassColoring
418 private var coloration_result
: Map[MPROP, Int] = new HashMap[MPROP, Int]
420 init(class_coloring
: ClassColoring) do
421 self.class_coloring
= class_coloring
424 private fun colorize
: Map[MPROP, Int] do
425 colorize_core_properties
426 colorize_crown_properties
427 return self.coloration_result
430 private fun build_property_tables
: Map[MClass, Array[nullable MPROPDEF]] do
431 var tables
= new HashMap[MClass, Array[nullable MPROPDEF]]
433 for mclass
in self.class_coloring
.coloration_result
.keys
do
434 var table
= new Array[nullable MPROPDEF]
435 # first, fill table from parents by reverse linearization order
436 var parents
= new OrderedSet[MClass]
437 parents
.add_all
(self.class_coloring
.super_elements
(mclass
))
438 self.class_coloring
.reverse_sorter
.sort
(parents
)
439 for parent
in parents
do
440 for mproperty
in self.properties
(parent
) do
441 var color
= self.coloration_result
[mproperty
]
442 if table
.length
<= color
then
443 for i
in [table
.length
.. color
[ do
447 for mpropdef
in mproperty
.mpropdefs
do
448 if mpropdef
.mclassdef
.mclass
== parent
then
449 table
[color
] = mpropdef
455 # then override with local properties
456 for mproperty
in self.properties
(mclass
) do
457 var color
= self.coloration_result
[mproperty
]
458 if table
.length
<= color
then
459 for i
in [table
.length
.. color
[ do
463 for mpropdef
in mproperty
.mpropdefs
do
464 if mpropdef
.mclassdef
.mclass
== mclass
then
465 table
[color
] = mpropdef
469 tables
[mclass
] = table
474 # Colorize properties of the core hierarchy
475 private fun colorize_core_properties
do
476 var mclasses
= self.class_coloring
.core
479 for mclass
in mclasses
do
480 var color
= min_color
482 # if the class is root, get the minimal color
483 if self.class_coloring
.parent_elements
(mclass
).length
== 0 then
484 colorize_elements
(self.properties
(mclass
), color
)
486 # check last color used by parents
487 color
= max_color
(color
, self.class_coloring
.parent_elements
(mclass
))
488 # check max color used in conflicts
489 if self.class_coloring
.conflicts_graph
.has_key
(mclass
) then
490 color
= max_color
(color
, self.class_coloring
.conflicts_graph
[mclass
])
494 colorize_elements
(self.properties
(mclass
), color
)
499 # Colorize properties of the crown hierarchy
500 private fun colorize_crown_properties
do
501 for mclass
in self.class_coloring
.crown
do
502 colorize_elements
(self.properties
(mclass
), max_color
(0, self.class_coloring
.parent_elements
(mclass
)))
506 # Colorize a collection of properties given a starting color
507 private fun colorize_elements
(elements
: Collection[MPROP], start_color
: Int) do
508 for element
in elements
do
509 if self.coloration_result
.has_key
(element
) then continue
510 self.coloration_result
[element
] = start_color
515 private fun max_color
(min_color
: Int, mclasses
: Collection[MClass]): Int do
516 var max_color
= min_color
518 for mclass
in mclasses
do
519 for mproperty
in self.properties
(mclass
) do
520 var color
= min_color
521 if self.coloration_result
.has_key
(mproperty
) then
522 color
= self.coloration_result
[mproperty
]
523 if color
>= max_color
then max_color
= color
+ 1
531 private var properties_cache
: Map[MClass, Set[MPROP]] = new HashMap[MClass, Set[MPROP]]
533 # All 'mproperties' associated to all 'mclassdefs' of the class
534 private fun properties
(mclass
: MClass): Set[MPROP] do
535 if not self.properties_cache
.has_key
(mclass
) then
536 var properties
= new HashSet[MPROP]
537 var parents
= self.class_coloring
.super_elements
(mclass
)
538 for parent
in parents
do
539 properties
.add_all
(self.properties
(parent
))
542 for mclassdef
in mclass
.mclassdefs
do
543 for mpropdef
in mclassdef
.mpropdefs
do
544 var mproperty
= mpropdef
.mproperty
545 if mproperty
isa MPROP then
546 properties
.add
(mproperty
)
550 self.properties_cache
[mclass
] = properties
552 return properties_cache
[mclass
]
558 super PropertyColoring
560 redef type MPROP: MMethod
561 redef type MPROPDEF: MMethodDef
564 # MAttribute coloring
565 class AttributeColoring
566 super PropertyColoring
568 redef type MPROP: MAttribute
569 redef type MPROPDEF: MAttributeDef
572 # MVirtualTypeProp coloring
574 super PropertyColoring
576 redef type MPROP: MVirtualTypeProp
577 redef type MPROPDEF: MVirtualTypeDef
580 # MParameterType coloring
582 private var class_coloring
: ClassColoring
583 private var coloration_result
: Map[MParameterType, Int] = new HashMap[MParameterType, Int]
585 init(class_coloring
: ClassColoring) do
586 self.class_coloring
= class_coloring
589 private fun colorize
: Map[MParameterType, Int] do
590 colorize_core_properties
591 colorize_crown_properties
592 return self.coloration_result
595 # Colorize properties of the core hierarchy
596 private fun colorize_core_properties
do
597 var mclasses
= self.class_coloring
.core
600 for mclass
in mclasses
do
601 var color
= min_color
603 # if the class is root, get the minimal color
604 if self.class_coloring
.parent_elements
(mclass
).length
== 0 then
605 colorize_elements
(self.fts
(mclass
), color
)
607 # check last color used by parents
608 color
= max_color
(color
, self.class_coloring
.parent_elements
(mclass
))
609 # check max color used in conflicts
610 if self.class_coloring
.conflicts_graph
.has_key
(mclass
) then
611 color
= max_color
(color
, self.class_coloring
.conflicts_graph
[mclass
])
614 colorize_elements
(self.fts
(mclass
), color
)
619 # Colorize properties of the crown hierarchy
620 private fun colorize_crown_properties
do
621 for mclass
in self.class_coloring
.crown
do
622 colorize_elements
(self.fts
(mclass
), max_color
(0, self.class_coloring
.parent_elements
(mclass
)))
626 # Colorize a collection of properties given a starting color
627 private fun colorize_elements
(elements
: Collection[MParameterType], start_color
: Int) do
628 for element
in elements
do
629 if self.coloration_result
.has_key
(element
) then continue
630 self.coloration_result
[element
] = start_color
635 private fun max_color
(min_color
: Int, mclasses
: Collection[MClass]): Int do
636 var max_color
= min_color
638 for mclass
in mclasses
do
639 for ft
in self.fts
(mclass
) do
640 var color
= min_color
641 if self.coloration_result
.has_key
(ft
) then
642 color
= self.coloration_result
[ft
]
643 if color
>= max_color
then max_color
= color
+ 1
651 private var fts_cache
: Map[MClass, Set[MParameterType]] = new HashMap[MClass, Set[MParameterType]]
653 private fun fts
(mclass
: MClass): Set[MParameterType] do
654 if not self.fts_cache
.has_key
(mclass
) then
655 var fts
= new HashSet[MParameterType]
656 var mclass_type
= mclass
.mclass_type
657 if mclass_type
isa MGenericType then
658 for ft
in mclass_type
.arguments
do
659 fts
.add
(ft
.as(MParameterType))
662 self.fts_cache
[mclass
] = fts
664 return fts_cache
[mclass
]
667 private fun build_ft_tables
: Map[MClass, Array[nullable MParameterType]] do
668 var tables
= new HashMap[MClass, Array[nullable MParameterType]]
670 for mclass
in self.class_coloring
.coloration_result
.keys
do
671 var table
= new Array[nullable MParameterType]
673 # first, fill table from parents
674 for parent
in self.class_coloring
.super_elements
(mclass
) do
675 for ft
in self.fts
(parent
) do
676 var color
= self.coloration_result
[ft
]
677 if table
.length
<= color
then
678 for i
in [table
.length
.. color
[ do
686 # then override with local properties
687 for ft
in self.fts
(mclass
) do
688 var color
= self.coloration_result
[ft
]
689 if table
.length
<= color
then
690 for i
in [table
.length
.. color
[ do
696 tables
[mclass
] = table
702 # Live Entries coloring
703 class LiveEntryColoring
705 private var coloration_result
: Map[MType, Int] = new HashMap[MType, Int]
706 private var conflicts_graph_cache
: nullable HashMap[MType, Set[MType]]
707 var livetypes_tables_sizes
: nullable Map[MClass, Array[Int]]
711 fun colorize
(elements
: Collection[MType]): Map[MType, Int] do
713 build_conflicts_graph
(elements
)
716 colorize_elements
(elements
)
718 return coloration_result
722 private fun build_livetype_tables
(mtypes
: Set[MType]): Map[MClass, Array[nullable Object]] do
723 var livetypes_tables
= new HashMap[MClass, Array[nullable Object]]
724 self.livetypes_tables_sizes
= new HashMap[MClass, Array[Int]]
726 for mtype
in mtypes
do
727 if mtype
isa MGenericType then
728 var table
: Array[nullable Object]
729 var sizes
: Array[Int]
730 if livetypes_tables
.has_key
(mtype
.mclass
) then
731 table
= livetypes_tables
[mtype
.mclass
]
733 table
= new Array[nullable Object]
734 livetypes_tables
[mtype
.mclass
] = table
736 if livetypes_tables_sizes
.has_key
(mtype
.mclass
) then
737 sizes
= livetypes_tables_sizes
[mtype
.mclass
]
739 sizes
= new Array[Int]
740 livetypes_tables_sizes
[mtype
.mclass
] = sizes
742 build_livetype_table
(mtype
, 0, table
, sizes
)
746 return livetypes_tables
749 # Build live gentype table recursively
750 private fun build_livetype_table
(mtype
: MGenericType, current_rank
: Int, table
: Array[nullable Object], sizes
: Array[Int]) do
751 var ft
= mtype
.arguments
[current_rank
]
752 if not self.coloration_result
.has_key
(ft
) then return
753 var color
= self.coloration_result
[ft
]
755 if current_rank
>= sizes
.length
then
756 sizes
[current_rank
] = color
+ 1
757 else if color
>= sizes
[current_rank
] then
758 sizes
[current_rank
] = color
+ 1
761 if color
> table
.length
then
762 for i
in [table
.length
.. color
[ do table
[i
] = null
765 if current_rank
== mtype
.arguments
.length
- 1 then
768 var ft_table
: Array[nullable Object]
769 if color
< table
.length
and table
[color
] != null then
770 ft_table
= table
[color
].as(Array[nullable Object])
772 ft_table
= new Array[nullable Object]
774 table
[color
] = ft_table
775 build_livetype_table
(mtype
, current_rank
+ 1, ft_table
, sizes
)
779 # Colorize a collection of elements
780 fun colorize_elements
(elements
: Collection[MType]) do
783 for element
in elements
do
784 var color
= min_color
785 while not self.is_color_free
(element
, color
) do
788 coloration_result
[element
] = color
793 # Check if a related element to the element already use the color
794 private fun is_color_free
(element
: MType, color
: Int): Bool do
795 if conflicts_graph
.has_key
(element
) then
796 for st
in conflicts_graph
[element
] do
797 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
803 # look for types in the same generic signatures
804 private fun build_conflicts_graph
(elements
: Collection[MType]) do
805 # regroup types by classes
806 var genclasses
= new HashMap[MClass, Set[MType]]
808 if e
isa MGenericType then
809 if not genclasses
.has_key
(e
.mclass
) then
810 genclasses
[e
.mclass
] = new HashSet[MType]
812 genclasses
[e
.mclass
].add
(e
)
817 self.conflicts_graph_cache
= new HashMap[MType, Set[MType]]
818 for mclass
, mtypes
in genclasses
do
820 for rank
in [0..mclass
.arity
[ do
822 for mtype
in mtypes
do
823 var mclasstype
: MClassType
824 if mtype
isa MNullableType then
825 mclasstype
= mtype
.mtype
.as(MClassType)
827 mclasstype
= mtype
.as(MClassType)
829 var ft
= mclasstype
.arguments
[rank
]
830 for otype
in mtypes
do
831 if mtype
== otype
then continue
832 var oclasstype
: MClassType
833 if otype
isa MNullableType then
834 oclasstype
= otype
.mtype
.as(MClassType)
836 oclasstype
= otype
.as(MClassType)
838 var oft
= oclasstype
.arguments
[rank
]
839 self.add_conflict
(ft
, oft
)
846 private fun add_conflict
(mtype
: MType, otype
: MType) do
847 if mtype
== otype
then return
848 if not self.conflicts_graph_cache
.has_key
(mtype
) then self.conflicts_graph_cache
[mtype
] = new HashSet[MClassType]
849 self.conflicts_graph_cache
[mtype
].add
(otype
)
850 if not self.conflicts_graph_cache
.has_key
(otype
) then self.conflicts_graph_cache
[otype
] = new HashSet[MClassType]
851 self.conflicts_graph_cache
[otype
].add
(mtype
)
853 private fun conflicts_graph
: Map[MType, Set[MType]] do return conflicts_graph_cache
.as(not null)
859 private class OrderedSet[E
]
863 if not self.has
(e
) then
868 # Return a new OrderedSet with the elements only contened in 'self' and not in 'o'
869 fun -(o
: OrderedSet[E
]): OrderedSet[E
] do
870 var res
= new OrderedSet[E
]
871 for e
in self do if not o
.has
(e
) then res
.add
(e
)