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 core
: Set[E
] = new HashSet[E
]
23 private var crown
: Set[E
] = new HashSet[E
]
24 private var border
: Set[E
] = new HashSet[E
]
26 private var coloration_result
: Map[E
, Int] = new HashMap[E
, Int]
30 fun colorize
(elements
: Set[E
]): Map[E
, Int] do
31 tag_elements
(elements
)
32 build_conflicts_graph
(elements
)
33 colorize_elements
(core
)
34 colorize_elements
(border
)
35 colorize_elements
(crown
)
36 return coloration_result
39 # Colorize a collection of elements
40 private fun colorize_elements
(elements
: Set[E
]) do
43 var lin
= reverse_linearize
(elements
)
46 while not self.is_color_free
(element
, elements
, color
) do
49 coloration_result
[element
] = color
54 # Check if a related element to the element already use the color
55 private fun is_color_free
(element
: E
, elements
: Set[E
], color
: Int): Bool do
56 if conflicts_graph
.has_key
(element
) then
57 for st
in conflicts_graph
[element
] do
58 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
61 for st
in self.super_elements
(element
, elements
) do
62 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
67 # Tag elements as core, crown or border
68 private fun tag_elements
(elements
: Set[E
]) do
69 for element
in elements
do
70 # Check if sub elements are all in single inheritance
71 var all_subelements_si
= true
72 for subelem
in self.sub_elements
(element
, elements
) do
73 if self.is_element_mi
(subelem
, elements
) then
74 all_subelements_si
= false
79 # Tag as core, crown or border
80 if self.is_element_mi
(element
, elements
) then
81 core
.add_all
(self.super_elements
(element
, elements
))
83 if all_subelements_si
then
86 else if not all_subelements_si
then
87 core
.add_all
(self.super_elements
(element
, elements
))
95 # Conflicts graph of elements hierarchy (two types are in conflict if they have common subelements)
96 private fun build_conflicts_graph
(elements
: Set[E
]) do
97 self.conflicts_graph
= new HashMap[E
, HashSet[E
]]
98 var core
= reverse_linearize
(self.core
)
100 for i
in self.linear_extension
(t
, elements
) do
101 if t
== i
then continue
103 var lin_i
= self.linear_extension
(i
, elements
)
105 for j
in self.linear_extension
(t
, elements
) do
106 if i
== j
or j
== t
then continue
107 var lin_j
= self.linear_extension
(j
, elements
)
109 var d_ij
= lin_i
- lin_j
110 var d_ji
= lin_j
- lin_i
113 if not conflicts_graph
.has_key
(ed1
) then conflicts_graph
[ed1
] = new HashSet[E
]
114 # add ed1 x ed2 to conflicts graph
115 for ed2
in d_ji
do conflicts_graph
[ed1
].add
(ed2
)
118 if not conflicts_graph
.has_key
(ed1
) then conflicts_graph
[ed1
] = new HashSet[E
]
119 # add ed1 x ed2 to conflicts graph
120 for ed2
in d_ji
do conflicts_graph
[ed1
].add
(ed2
)
127 private var conflicts_graph
: nullable HashMap[E
, Set[E
]]
129 # cache for linear_extensions
130 private var linear_extensions_cache
: Map[E
, Array[E
]] = new HashMap[E
, Array[E
]]
132 # Return a linear_extension of super_elements of the element
133 private fun linear_extension
(element
: E
, elements
: Set[E
]): Array[E
] do
134 if not self.linear_extensions_cache
.has_key
(element
) then
135 var supers
= new HashSet[E
]
137 supers
.add_all
(self.super_elements
(element
, elements
))
138 self.linear_extensions_cache
[element
] = self.linearize
(supers
)
140 return self.linear_extensions_cache
[element
]
143 private fun super_elements
(element
: E
, elements
: Set[E
]): Set[E
] is abstract
144 private fun sub_elements
(element
: E
, elements
: Set[E
]): Set[E
] is abstract
145 private fun is_element_mi
(element
: E
, elements
: Set[E
]): Bool is abstract
146 private fun linearize
(elements
: Set[E
]): Array[E
] is abstract
147 private fun reverse_linearize
(elements
: Set[E
]): Array[E
] is abstract
150 # MClassType coloring
152 super AbstractColoring[MType]
156 private var mmodule
: MModule
158 init(mainmodule
: MModule) do self.mmodule
= mainmodule
161 fun build_type_tables
(mtypes
: Set[T
], colors
: Map[T
, Int]): Map[T
, Array[nullable T
]] do
162 var tables
= new HashMap[T
, Array[nullable T
]]
164 for mtype
in mtypes
do
165 var table
= new Array[nullable T
]
166 var supers
= new HashSet[T
]
167 supers
.add_all
(self.super_elements
(mtype
, mtypes
))
170 var color
= colors
[sup
]
171 if table
.length
<= color
then
172 for i
in [table
.length
.. color
[ do
178 tables
[mtype
] = table
183 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mtypes
(element
, elements
)
184 redef fun is_element_mi
(element
, elements
) do return self.super_elements
(element
, elements
).length
> 1
185 redef fun sub_elements
(element
, elements
) do do return self.mmodule
.sub_mtypes
(element
, elements
)
186 redef fun linearize
(elements
) do return self.mmodule
.linearize_mtypes
(elements
)
187 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mtypes
(elements
)
190 class NaiveTypeColoring
193 init(mainmodule
: MModule) do super
195 # naive coloring that use incremental coloring
196 redef fun colorize_elements
(elements
) do
198 self.coloration_result
[e
] = self.coloration_result
.length
203 abstract class TypePerfectHashing
206 init(mainmodule
: MModule) do super
208 fun compute_masks
(elements
: Set[T
], ids
: Map[T
, Int]): Map[T
, Int] do
210 # Create super type list
211 var supers
= new HashSet[T
]
212 supers
.add_all
(self.super_elements
(e
, elements
))
214 # Compute the hashing 'mask'
215 self.coloration_result
[e
] = compute_mask
(supers
, ids
)
217 return self.coloration_result
221 fun hash_type_tables
(mtypes
: Set[T
], ids
: Map[T
, Int], masks
: Map[T
, Int]): Map[T
, Array[nullable T
]] do
222 var tables
= new HashMap[T
, Array[nullable T
]]
224 for mtype
in mtypes
do
225 var table
= new Array[nullable T
]
226 var supers
= new HashSet[T
]
227 supers
.add_all
(self.super_elements
(mtype
, mtypes
))
231 var color
= phash
(ids
[sup
], masks
[mtype
])
232 if table
.length
<= color
then
233 for i
in [table
.length
.. color
[ do
239 tables
[mtype
] = table
244 private fun compute_mask
(mtypes
: Set[T
], ids
: Map[T
, Int]): Int do
247 var used
= new List[Int]
249 var res
= op
(mask
, ids
[sup
])
250 if used
.has
(res
) then
256 if used
.length
== mtypes
.length
then break
262 private fun op
(mask
: Int, id
:Int): Int is abstract
263 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
266 class TypeModPerfectHashing
267 super TypePerfectHashing
268 init(mainmodule
: MModule) do super
269 redef fun op
(mask
, id
) do return mask
% id
272 class TypeAndPerfectHashing
273 super TypePerfectHashing
274 init(mainmodule
: MModule) do super
275 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
280 super AbstractColoring[MClass]
284 private var mmodule
: MModule
287 private var super_elements_cache
: Map[T
, Set[T
]] = new HashMap[T
, Set[T
]]
288 private var parent_elements_cache
: Map[T
, Set[T
]] = new HashMap[T
, Set[T
]]
289 private var sub_elements_cache
: Map[T
, Set[T
]] = new HashMap[T
, Set[T
]]
291 init(mainmodule
: MModule) do self.mmodule
= mainmodule
294 fun build_type_tables
(mclasses
: Set[T
], colors
: Map[T
, Int]): Map[T
, Array[nullable T
]] do
295 var tables
= new HashMap[T
, Array[nullable T
]]
297 for mclasse
in mclasses
do
298 var table
= new Array[nullable T
]
299 var supers
= new HashSet[T
]
300 supers
.add_all
(self.super_elements
(mclasse
, mclasses
))
303 var color
= colors
[sup
]
304 if table
.length
<= color
then
305 for i
in [table
.length
.. color
[ do
311 tables
[mclasse
] = table
316 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mclasses
(element
)
317 fun parent_elements
(element
: MClass): Set[MClass] do return self.mmodule
.parent_mclasses
(element
)
318 redef fun is_element_mi
(element
, elements
) do return self.parent_elements
(element
).length
> 1
319 redef fun sub_elements
(element
, elements
) do do return self.mmodule
.sub_mclasses
(element
)
320 redef fun linearize
(elements
) do return self.mmodule
.linearize_mclasses
(elements
)
321 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mclasses
(elements
)
324 # incremental coloring (very naive)
325 class NaiveClassColoring
328 init(mainmodule
: MModule) do
332 # naive coloring that use incremental coloring
333 redef fun colorize_elements
(elements
) do
335 self.coloration_result
[e
] = self.coloration_result
.length
340 abstract class ClassPerfectHashing
343 init(mainmodule
: MModule) do
347 fun compute_masks
(elements
: Set[T
], ids
: Map[T
, Int]): Map[T
, Int] do
349 # Create super type list
350 var supers
= new HashSet[T
]
351 supers
.add_all
(self.super_elements
(e
, elements
))
353 # Compute the hashing 'mask'
354 self.coloration_result
[e
] = compute_mask
(supers
, ids
)
356 return self.coloration_result
360 fun hash_type_tables
(mtypes
: Set[T
], ids
: Map[T
, Int], masks
: Map[T
, Int]): Map[T
, Array[nullable T
]] do
361 var tables
= new HashMap[T
, Array[nullable T
]]
363 for mtype
in mtypes
do
364 var table
= new Array[nullable T
]
365 var supers
= new HashSet[T
]
366 supers
.add_all
(self.super_elements
(mtype
, mtypes
))
370 var color
= phash
(ids
[sup
], masks
[mtype
])
371 if table
.length
<= color
then
372 for i
in [table
.length
.. color
[ do
378 tables
[mtype
] = table
383 private fun compute_mask
(mtypes
: Set[T
], ids
: Map[T
, Int]): Int do
386 var used
= new List[Int]
388 var res
= op
(mask
, ids
[sup
])
389 if used
.has
(res
) then
395 if used
.length
== mtypes
.length
then break
401 private fun op
(mask
: Int, id
:Int): Int is abstract
402 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
405 class ClassModPerfectHashing
406 super ClassPerfectHashing
407 init(mainmodule
: MModule) do
410 redef fun op
(mask
, id
) do return mask
% id
413 class ClassAndPerfectHashing
414 super ClassPerfectHashing
415 init(mainmodule
: MModule) do
418 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
422 class PropertyColoring
424 type MPROP: MProperty
425 type MPROPDEF: MPropDef
427 private var class_coloring
: ClassColoring
428 private var coloration_result
: Map[MPROP, Int] = new HashMap[MPROP, Int]
430 init(class_coloring
: ClassColoring) do
431 self.class_coloring
= class_coloring
434 fun colorize
: Map[MPROP, Int] do
435 colorize_core_properties
436 colorize_crown_properties
437 return self.coloration_result
440 fun build_property_tables
: Map[MClass, Array[nullable MPROPDEF]] do
441 var tables
= new HashMap[MClass, Array[nullable MPROPDEF]]
442 var mclasses
= self.class_coloring
.coloration_result
.keys
443 for mclass
in mclasses
do
444 var table
= new Array[nullable MPROPDEF]
445 # first, fill table from parents by reverse linearization order
446 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
447 var lin
= self.class_coloring
.reverse_linearize
(parents
)
449 for mproperty
in self.properties
(parent
) do
450 var color
= self.coloration_result
[mproperty
]
451 if table
.length
<= color
then
452 for i
in [table
.length
.. color
[ do
456 for mpropdef
in mproperty
.mpropdefs
do
457 if mpropdef
.mclassdef
.mclass
== parent
then
458 table
[color
] = mpropdef
464 # then override with local properties
465 for mproperty
in self.properties
(mclass
) do
466 var color
= self.coloration_result
[mproperty
]
467 if table
.length
<= color
then
468 for i
in [table
.length
.. color
[ do
472 for mpropdef
in mproperty
.mpropdefs
do
473 if mpropdef
.mclassdef
.mclass
== mclass
then
474 table
[color
] = mpropdef
478 tables
[mclass
] = table
483 # Colorize properties of the core hierarchy
484 private fun colorize_core_properties
do
485 var mclasses
= self.class_coloring
.core
488 for mclass
in mclasses
do
489 var color
= min_color
491 # if the class is root, get the minimal color
492 if self.class_coloring
.parent_elements
(mclass
).length
== 0 then
493 colorize_elements
(self.properties
(mclass
), color
)
495 # check last color used by parents
496 color
= max_color
(color
, self.class_coloring
.parent_elements
(mclass
))
497 # check max color used in conflicts
498 if self.class_coloring
.conflicts_graph
.has_key
(mclass
) then
499 color
= max_color
(color
, self.class_coloring
.conflicts_graph
[mclass
])
503 colorize_elements
(self.properties
(mclass
), color
)
508 # Colorize properties of the crown hierarchy
509 private fun colorize_crown_properties
do
510 for mclass
in self.class_coloring
.crown
do
511 colorize_elements
(self.properties
(mclass
), max_color
(0, self.class_coloring
.parent_elements
(mclass
)))
515 # Colorize a collection of properties given a starting color
516 private fun colorize_elements
(elements
: Collection[MPROP], start_color
: Int) do
517 for element
in elements
do
518 if self.coloration_result
.has_key
(element
) then continue
519 self.coloration_result
[element
] = start_color
524 private fun max_color
(min_color
: Int, mclasses
: Collection[MClass]): Int do
525 var max_color
= min_color
527 for mclass
in mclasses
do
528 for mproperty
in self.properties
(mclass
) do
529 var color
= min_color
530 if self.coloration_result
.has_key
(mproperty
) then
531 color
= self.coloration_result
[mproperty
]
532 if color
>= max_color
then max_color
= color
+ 1
540 private var properties_cache
: Map[MClass, Set[MPROP]] = new HashMap[MClass, Set[MPROP]]
542 # All 'mproperties' associated to all 'mclassdefs' of the class
543 private fun properties
(mclass
: MClass): Set[MPROP] do
544 if not self.properties_cache
.has_key
(mclass
) then
545 var properties
= new HashSet[MPROP]
546 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
547 for parent
in parents
do
548 properties
.add_all
(self.properties
(parent
))
551 for mclassdef
in mclass
.mclassdefs
do
552 for mpropdef
in mclassdef
.mpropdefs
do
553 var mproperty
= mpropdef
.mproperty
554 if mproperty
isa MPROP then
555 properties
.add
(mproperty
)
559 self.properties_cache
[mclass
] = properties
561 return properties_cache
[mclass
]
567 super PropertyColoring
569 redef type MPROP: MMethod
570 redef type MPROPDEF: MMethodDef
571 init(class_coloring
: ClassColoring) do end
574 # MAttribute coloring
575 class AttributeColoring
576 super PropertyColoring
578 redef type MPROP: MAttribute
579 redef type MPROPDEF: MAttributeDef
580 init(class_coloring
: ClassColoring) do end
583 # MVirtualTypeProp coloring
585 super PropertyColoring
587 redef type MPROP: MVirtualTypeProp
588 redef type MPROPDEF: MVirtualTypeDef
589 init(class_coloring
: ClassColoring) do end
592 class NaiveVTColoring
595 init(class_coloring
: ClassColoring) do end
597 redef fun colorize
: Map[MPROP, Int] do
598 var mclasses
= new HashSet[MClass]
599 mclasses
.add_all
(self.class_coloring
.core
)
600 mclasses
.add_all
(self.class_coloring
.crown
)
603 for mclass
in mclasses
do
604 min_color
= max_color
(min_color
, mclasses
)
605 colorize_elements
(self.properties
(mclass
), min_color
)
607 return self.coloration_result
611 abstract class VTPerfectHashing
614 private var masks
: Map[MClass, Int] = new HashMap[MClass, Int]
616 init(class_coloring
: ClassColoring) do end
618 redef fun colorize
: Map[MPROP, Int] do
619 var mclasses
= new HashSet[MClass]
620 mclasses
.add_all
(self.class_coloring
.core
)
621 mclasses
.add_all
(self.class_coloring
.crown
)
622 for mclass
in mclasses
do
623 var vts
= self.properties
(mclass
)
625 if coloration_result
.has_key
(vt
) then continue
626 coloration_result
[vt
] = coloration_result
.length
+ 1
629 return self.coloration_result
632 fun compute_masks
: Map[MClass, Int] do
633 var mclasses
= new HashSet[MClass]
634 mclasses
.add_all
(self.class_coloring
.core
)
635 mclasses
.add_all
(self.class_coloring
.crown
)
636 for mclass
in mclasses
do
637 self.masks
[mclass
] = compute_mask
(self.properties
(mclass
))
642 private fun compute_mask
(vts
: Set[MPROP]): Int do
645 var used
= new List[Int]
647 var res
= op
(mask
, self.coloration_result
[vt
])
648 if used
.has
(res
) then
654 if used
.length
== vts
.length
then break
660 redef fun build_property_tables
do
661 var tables
= new HashMap[MClass, Array[nullable MPROPDEF]]
663 for mclass
in self.class_coloring
.coloration_result
.keys
do
664 var table
= new Array[nullable MPROPDEF]
665 # first, fill table from parents by reverse linearization order
666 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
667 var lin
= self.class_coloring
.reverse_linearize
(parents
)
669 for mproperty
in self.properties
(parent
) do
670 var color
= phash
(self.coloration_result
[mproperty
], masks
[mclass
])
671 if table
.length
<= color
then
672 for i
in [table
.length
.. color
[ do
676 for mpropdef
in mproperty
.mpropdefs
do
677 if mpropdef
.mclassdef
.mclass
== parent
then
678 table
[color
] = mpropdef
684 # then override with local properties
685 for mproperty
in self.properties
(mclass
) do
686 var color
= phash
(self.coloration_result
[mproperty
], masks
[mclass
])
687 if table
.length
<= color
then
688 for i
in [table
.length
.. color
[ do
692 for mpropdef
in mproperty
.mpropdefs
do
693 if mpropdef
.mclassdef
.mclass
== mclass
then
694 table
[color
] = mpropdef
698 tables
[mclass
] = table
703 private fun op
(mask
: Int, id
:Int): Int is abstract
704 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
708 class VTModPerfectHashing
709 super VTPerfectHashing
710 init(class_coloring
: ClassColoring) do end
711 redef fun op
(mask
, id
) do return mask
% id
714 class VTAndPerfectHashing
715 super VTPerfectHashing
716 init(class_coloring
: ClassColoring) do end
717 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
720 # MParameterType coloring
722 private var class_coloring
: ClassColoring
723 private var coloration_result
: Map[MParameterType, Int] = new HashMap[MParameterType, Int]
725 init(class_coloring
: ClassColoring) do
726 self.class_coloring
= class_coloring
729 fun colorize
: Map[MParameterType, Int] do
730 colorize_core_properties
731 colorize_crown_properties
732 return self.coloration_result
735 # Colorize properties of the core hierarchy
736 private fun colorize_core_properties
do
737 var mclasses
= self.class_coloring
.core
740 for mclass
in mclasses
do
741 var color
= min_color
743 # if the class is root, get the minimal color
744 if self.class_coloring
.parent_elements
(mclass
).length
== 0 then
745 colorize_elements
(self.fts
(mclass
), color
)
747 # check last color used by parents
748 color
= max_color
(color
, self.class_coloring
.parent_elements
(mclass
))
749 # check max color used in conflicts
750 if self.class_coloring
.conflicts_graph
.has_key
(mclass
) then
751 color
= max_color
(color
, self.class_coloring
.conflicts_graph
[mclass
])
754 colorize_elements
(self.fts
(mclass
), color
)
759 # Colorize properties of the crown hierarchy
760 private fun colorize_crown_properties
do
761 for mclass
in self.class_coloring
.crown
do
762 colorize_elements
(self.fts
(mclass
), max_color
(0, self.class_coloring
.parent_elements
(mclass
)))
766 # Colorize a collection of properties given a starting color
767 private fun colorize_elements
(elements
: Collection[MParameterType], start_color
: Int) do
768 for element
in elements
do
769 if self.coloration_result
.has_key
(element
) then continue
770 self.coloration_result
[element
] = start_color
775 private fun max_color
(min_color
: Int, mclasses
: Collection[MClass]): Int do
776 var max_color
= min_color
778 for mclass
in mclasses
do
779 for ft
in self.fts
(mclass
) do
780 var color
= min_color
781 if self.coloration_result
.has_key
(ft
) then
782 color
= self.coloration_result
[ft
]
783 if color
>= max_color
then max_color
= color
+ 1
791 private var fts_cache
: Map[MClass, Set[MParameterType]] = new HashMap[MClass, Set[MParameterType]]
793 private fun fts
(mclass
: MClass): Set[MParameterType] do
794 if not self.fts_cache
.has_key
(mclass
) then
795 var fts
= new HashSet[MParameterType]
796 var mclass_type
= mclass
.mclass_type
797 if mclass_type
isa MGenericType then
798 for ft
in mclass_type
.arguments
do
799 fts
.add
(ft
.as(MParameterType))
802 self.fts_cache
[mclass
] = fts
804 return fts_cache
[mclass
]
807 fun build_ft_tables
: Map[MClass, Array[nullable MParameterType]] do
808 var tables
= new HashMap[MClass, Array[nullable MParameterType]]
810 for mclass
in self.class_coloring
.coloration_result
.keys
do
811 var table
= new Array[nullable MParameterType]
813 # first, fill table from parents
814 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
815 for parent
in parents
do
816 for ft
in self.fts
(parent
) do
817 var color
= self.coloration_result
[ft
]
818 if table
.length
<= color
then
819 for i
in [table
.length
.. color
[ do
827 # then override with local properties
828 for ft
in self.fts
(mclass
) do
829 var color
= self.coloration_result
[ft
]
830 if table
.length
<= color
then
831 for i
in [table
.length
.. color
[ do
837 tables
[mclass
] = table
843 class NaiveFTColoring
846 init(class_coloring
: ClassColoring) do end
848 redef fun colorize
: Map[MParameterType, Int] do
849 var mclasses
= new HashSet[MClass]
850 mclasses
.add_all
(self.class_coloring
.core
)
851 mclasses
.add_all
(self.class_coloring
.crown
)
854 for mclass
in mclasses
do
855 min_color
= max_color
(min_color
, mclasses
)
856 colorize_elements
(self.fts
(mclass
), min_color
)
858 return self.coloration_result
862 abstract class FTPerfectHashing
865 private var masks
: Map[MClass, Int] = new HashMap[MClass, Int]
867 init(class_coloring
: ClassColoring) do end
869 redef fun colorize
: Map[MParameterType, Int] do
870 var mclasses
= new HashSet[MClass]
871 mclasses
.add_all
(self.class_coloring
.core
)
872 mclasses
.add_all
(self.class_coloring
.crown
)
873 for mclass
in mclasses
do
874 for ft
in self.fts
(mclass
) do
875 if coloration_result
.has_key
(ft
) then continue
876 coloration_result
[ft
] = coloration_result
.length
+ 1
879 return self.coloration_result
882 fun compute_masks
: Map[MClass, Int] do
883 var mclasses
= new HashSet[MClass]
884 mclasses
.add_all
(self.class_coloring
.core
)
885 mclasses
.add_all
(self.class_coloring
.crown
)
886 for mclass
in mclasses
do
887 var fts
= new HashSet[MParameterType]
888 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
889 for parent
in parents
do
890 fts
.add_all
(self.fts
(parent
))
892 fts
.add_all
(self.fts
(mclass
))
893 self.masks
[mclass
] = compute_mask
(fts
)
898 private fun compute_mask
(fts
: Set[MParameterType]): Int do
901 var used
= new List[Int]
903 var res
= op
(mask
, self.coloration_result
[ft
])
904 if used
.has
(res
) then
910 if used
.length
== fts
.length
then break
916 redef fun build_ft_tables
do
917 var tables
= new HashMap[MClass, Array[nullable MParameterType]]
919 for mclass
in self.class_coloring
.coloration_result
.keys
do
920 var table
= new Array[nullable MParameterType]
922 # first, fill table from parents
923 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
924 for parent
in parents
do
925 for ft
in self.fts
(parent
) do
926 var color
= phash
(self.coloration_result
[ft
], masks
[mclass
])
927 if table
.length
<= color
then
928 for i
in [table
.length
.. color
[ do
936 # then override with local properties
937 for ft
in self.fts
(mclass
) do
938 var color
= phash
(self.coloration_result
[ft
], masks
[mclass
])
939 if table
.length
<= color
then
940 for i
in [table
.length
.. color
[ do
946 tables
[mclass
] = table
951 private fun op
(mask
: Int, id
:Int): Int is abstract
952 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
955 class FTModPerfectHashing
956 super FTPerfectHashing
957 init(class_coloring
: ClassColoring) do end
958 redef fun op
(mask
, id
) do return mask
% id
961 class FTAndPerfectHashing
962 super FTPerfectHashing
963 init(class_coloring
: ClassColoring) do end
964 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
967 # Live Entries coloring
968 class LiveEntryColoring
970 private var coloration_result
: Map[MType, Int] = new HashMap[MType, Int]
971 private var conflicts_graph_cache
: nullable HashMap[MType, Set[MType]]
972 var livetypes_tables_sizes
: nullable Map[MClass, Array[Int]]
976 fun colorize
(elements
: Collection[MType]): Map[MType, Int] do
978 build_conflicts_graph
(elements
)
981 colorize_elements
(elements
)
983 return coloration_result
987 fun build_livetype_tables
(mtypes
: Set[MType]): Map[MClass, Array[nullable Object]] do
988 var livetypes_tables
= new HashMap[MClass, Array[nullable Object]]
989 self.livetypes_tables_sizes
= new HashMap[MClass, Array[Int]]
991 for mtype
in mtypes
do
992 if mtype
isa MGenericType then
993 var table
: Array[nullable Object]
994 var sizes
: Array[Int]
995 if livetypes_tables
.has_key
(mtype
.mclass
) then
996 table
= livetypes_tables
[mtype
.mclass
]
998 table
= new Array[nullable Object]
999 livetypes_tables
[mtype
.mclass
] = table
1001 if livetypes_tables_sizes
.has_key
(mtype
.mclass
) then
1002 sizes
= livetypes_tables_sizes
[mtype
.mclass
]
1004 sizes
= new Array[Int]
1005 livetypes_tables_sizes
[mtype
.mclass
] = sizes
1007 build_livetype_table
(mtype
, 0, table
, sizes
)
1011 return livetypes_tables
1014 # Build live gentype table recursively
1015 private fun build_livetype_table
(mtype
: MGenericType, current_rank
: Int, table
: Array[nullable Object], sizes
: Array[Int]) do
1016 var ft
= mtype
.arguments
[current_rank
]
1017 if not self.coloration_result
.has_key
(ft
) then return
1018 var color
= self.coloration_result
[ft
]
1020 if current_rank
>= sizes
.length
then
1021 sizes
[current_rank
] = color
+ 1
1022 else if color
>= sizes
[current_rank
] then
1023 sizes
[current_rank
] = color
+ 1
1026 if color
> table
.length
then
1027 for i
in [table
.length
.. color
[ do table
[i
] = null
1030 if current_rank
== mtype
.arguments
.length
- 1 then
1031 table
[color
] = mtype
1033 var ft_table
: Array[nullable Object]
1034 if color
< table
.length
and table
[color
] != null then
1035 ft_table
= table
[color
].as(Array[nullable Object])
1037 ft_table
= new Array[nullable Object]
1039 table
[color
] = ft_table
1040 build_livetype_table
(mtype
, current_rank
+ 1, ft_table
, sizes
)
1044 # Colorize a collection of elements
1045 fun colorize_elements
(elements
: Collection[MType]) do
1048 for element
in elements
do
1049 var color
= min_color
1050 while not self.is_color_free
(element
, color
) do
1053 coloration_result
[element
] = color
1058 # Check if a related element to the element already use the color
1059 private fun is_color_free
(element
: MType, color
: Int): Bool do
1060 if conflicts_graph
.has_key
(element
) then
1061 for st
in conflicts_graph
[element
] do
1062 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
1068 # look for types in the same generic signatures
1069 private fun build_conflicts_graph
(elements
: Collection[MType]) do
1070 # regroup types by classes
1071 var genclasses
= new HashMap[MClass, Set[MType]]
1072 for e
in elements
do
1073 if e
isa MGenericType then
1074 if not genclasses
.has_key
(e
.mclass
) then
1075 genclasses
[e
.mclass
] = new HashSet[MType]
1077 genclasses
[e
.mclass
].add
(e
)
1082 self.conflicts_graph_cache
= new HashMap[MType, Set[MType]]
1083 for mclass
, mtypes
in genclasses
do
1085 for rank
in [0..mclass
.arity
[ do
1086 # for each live type
1087 for mtype
in mtypes
do
1088 var mclasstype
: MClassType
1089 if mtype
isa MNullableType then
1090 mclasstype
= mtype
.mtype
.as(MClassType)
1092 mclasstype
= mtype
.as(MClassType)
1094 var ft
= mclasstype
.arguments
[rank
]
1095 for otype
in mtypes
do
1096 if mtype
== otype
then continue
1097 var oclasstype
: MClassType
1098 if otype
isa MNullableType then
1099 oclasstype
= otype
.mtype
.as(MClassType)
1101 oclasstype
= otype
.as(MClassType)
1103 var oft
= oclasstype
.arguments
[rank
]
1104 self.add_conflict
(ft
, oft
)
1111 private fun add_conflict
(mtype
: MType, otype
: MType) do
1112 if mtype
== otype
then return
1113 if not self.conflicts_graph_cache
.has_key
(mtype
) then self.conflicts_graph_cache
[mtype
] = new HashSet[MType]
1114 self.conflicts_graph_cache
[mtype
].add
(otype
)
1115 if not self.conflicts_graph_cache
.has_key
(otype
) then self.conflicts_graph_cache
[otype
] = new HashSet[MType]
1116 self.conflicts_graph_cache
[otype
].add
(mtype
)
1118 private fun conflicts_graph
: Map[MType, Set[MType]] do return conflicts_graph_cache
.as(not null)
1121 class NaiveLiveEntryColoring
1122 super LiveEntryColoring
1126 redef fun colorize_elements
(elements
: Collection[MType]) do
1128 for element
in elements
do
1129 coloration_result
[element
] = color
1135 # live unanchored coloring
1136 class UnanchoredTypeColoring
1138 private var coloration_result
: Map[MType, Int] = new HashMap[MType, Int]
1139 private var conflicts_graph
: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
1143 fun colorize
(elements
: Map[MClassType, Set[MType]]): Map[MType, Int] do
1144 build_conflicts_graph
(elements
)
1145 colorize_elements
(elements
)
1146 return coloration_result
1149 fun build_tables
(elements
: Map[MClassType, Set[MType]]): Map[MClassType, Array[nullable MType]] do
1150 var tables
= new HashMap[MClassType, Array[nullable MType]]
1152 for mclasstype
, mtypes
in elements
do
1153 var table
= new Array[nullable MType]
1154 for mtype
in mtypes
do
1155 var color
= self.coloration_result
[mtype
]
1156 if table
.length
<= color
then
1157 for i
in [table
.length
.. color
[ do
1161 table
[color
] = mtype
1163 tables
[mclasstype
] = table
1168 # Colorize a collection of elements
1169 fun colorize_elements
(elements
: Map[MClassType, Set[MType]]) do
1171 for mclasstype
, mclasstypes
in elements
do
1172 for element
in mclasstypes
do
1173 if self.coloration_result
.has_key
(element
) then continue
1174 var color
= min_color
1175 while not self.is_color_free
(element
, color
) do
1178 coloration_result
[element
] = color
1184 # Check if a related element to the element already use the color
1185 private fun is_color_free
(element
: MType, color
: Int): Bool do
1186 if conflicts_graph
.has_key
(element
) then
1187 for st
in conflicts_graph
[element
] do
1188 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
1194 # look for unanchored types generated by the same type
1195 private fun build_conflicts_graph
(elements
: Map[MClassType, Set[MType]]) do
1196 for mclasstype
, mtypes
in elements
do
1197 for mtype
in mtypes
do
1198 for otype
in mtypes
do
1199 if otype
== mtype
then continue
1200 self.add_conflict
(mtype
, otype
)
1206 private fun add_conflict
(mtype
: MType, otype
: MType) do
1207 if mtype
== otype
then return
1208 if not self.conflicts_graph
.has_key
(mtype
) then self.conflicts_graph
[mtype
] = new HashSet[MType]
1209 self.conflicts_graph
[mtype
].add
(otype
)
1210 if not self.conflicts_graph
.has_key
(otype
) then self.conflicts_graph
[otype
] = new HashSet[MType]
1211 self.conflicts_graph
[otype
].add
(mtype
)
1215 class NaiveUnanchoredTypeColoring
1216 super UnanchoredTypeColoring
1220 redef fun colorize_elements
(elements
: Map[MClassType, Set[MType]]) do
1222 for mclasstype
, mclasstypes
in elements
do
1223 for element
in mclasstypes
do
1224 coloration_result
[element
] = color
1231 abstract class UnanchoredTypePerfectHashing
1232 super NaiveUnanchoredTypeColoring
1234 private var masks
: Map[MClassType, Int] = new HashMap[MClassType, Int]
1238 redef fun colorize_elements
(elements
: Map[MClassType, Set[MType]]) do
1240 for mclasstype
, mclasstypes
in elements
do
1241 for element
in mclasstypes
do
1242 coloration_result
[element
] = color
1248 fun compute_masks
(elements
: Map[MClassType, Set[MType]]): Map[MClassType, Int] do
1249 for mclasstype
, mtypes
in elements
do
1250 self.masks
[mclasstype
] = compute_mask
(mtypes
)
1255 private fun compute_mask
(mtypes
: Set[MType]): Int do
1258 var used
= new List[Int]
1259 for mtype
in mtypes
do
1260 var res
= op
(mask
, self.coloration_result
[mtype
])
1261 if used
.has
(res
) then
1267 if used
.length
== mtypes
.length
then break
1273 redef fun build_tables
(elements
: Map[MClassType, Set[MType]]): Map[MClassType, Array[nullable MType]] do
1274 var tables
= new HashMap[MClassType, Array[nullable MType]]
1276 for mclasstype
, mtypes
in elements
do
1277 var table
= new Array[nullable MType]
1278 for mtype
in mtypes
do
1279 var color
= phash
(self.coloration_result
[mtype
], masks
[mclasstype
])
1280 if table
.length
<= color
then
1281 for i
in [table
.length
.. color
[ do
1285 table
[color
] = mtype
1287 tables
[mclasstype
] = table
1292 private fun op
(mask
: Int, id
:Int): Int is abstract
1293 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
1296 class UnanchoredTypeModPerfectHashing
1297 super UnanchoredTypePerfectHashing
1299 redef fun op
(mask
, id
) do return mask
% id
1302 class UnanchoredTypeAndPerfectHashing
1303 super UnanchoredTypePerfectHashing
1305 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
1311 redef class HashSet[E
]
1312 init from
(elements
: Collection[E
]) do
1314 self.add_all
(elements
)
1318 redef class Array[E
]
1319 init from
(elements
: Collection[E
]) do
1321 self.add_all
(elements
)
1324 # Return a new Array with the elements only contened in 'self' and not in 'o'
1325 fun -(o
: Array[E
]): Array[E
] do
1326 var res
= new Array[E
]
1327 for e
in self do if not o
.has
(e
) then res
.add
(e
)
1334 # Return a linearization of a set of mtypes
1335 private fun linearize_mtypes
(mtypes
: Set[MType]): Array[MType] do
1336 var lin
= new Array[MType].from
(mtypes
)
1337 var sorter
= new TypeSorter(self)
1342 # Return a reverse linearization of a set of mtypes
1343 private fun reverse_linearize_mtypes
(mtypes
: Set[MType]): Array[MType] do
1344 var lin
= new Array[MType].from
(mtypes
)
1345 var sorter
= new ReverseTypeSorter(self)
1350 # Return super types of a `mtype` in `self`
1351 private fun super_mtypes
(mtype
: MType, mtypes
: Set[MType]): Set[MType] do
1352 if not self.super_mtypes_cache
.has_key
(mtype
) then
1353 var supers
= new HashSet[MType]
1354 for otype
in mtypes
do
1355 if otype
== mtype
then continue
1356 if mtype
.is_subtype
(self, null, otype
) then
1360 self.super_mtypes_cache
[mtype
] = supers
1362 return self.super_mtypes_cache
[mtype
]
1365 private var super_mtypes_cache
: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
1367 # Return all sub mtypes (directs and indirects) of a `mtype` in `self`
1368 private fun sub_mtypes
(mtype
: MType, mtypes
: Set[MType]): Set[MType] do
1369 if not self.sub_mtypes_cache
.has_key
(mtype
) then
1370 var subs
= new HashSet[MType]
1371 for otype
in mtypes
do
1372 if otype
== mtype
then continue
1373 if otype
.is_subtype
(self, null, mtype
) then
1377 self.sub_mtypes_cache
[mtype
] = subs
1379 return self.sub_mtypes_cache
[mtype
]
1382 private var sub_mtypes_cache
: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
1384 # Return a linearization of a set of mclasses
1385 private fun linearize_mclasses
(mclasses
: Set[MClass]): Array[MClass] do
1386 var lin
= new Array[MClass].from
(mclasses
)
1387 var sorter
= new ClassSorter(self)
1392 # Return a reverse linearization of a set of mtypes
1393 private fun reverse_linearize_mclasses
(mclasses
: Set[MClass]): Array[MClass] do
1394 var lin
= new Array[MClass].from
(mclasses
)
1395 var sorter
= new ReverseClassSorter(self)
1400 # Return all super mclasses (directs and indirects) of a `mclass` in `self`
1401 private fun super_mclasses
(mclass
: MClass): Set[MClass] do
1402 if not self.super_mclasses_cache
.has_key
(mclass
) then
1403 var supers
= new HashSet[MClass]
1404 if self.flatten_mclass_hierarchy
.has
(mclass
) then
1405 for sup
in self.flatten_mclass_hierarchy
[mclass
].greaters
do
1406 if sup
== mclass
then continue
1410 self.super_mclasses_cache
[mclass
] = supers
1412 return self.super_mclasses_cache
[mclass
]
1415 private var super_mclasses_cache
: Map[MClass, Set[MClass]] = new HashMap[MClass, Set[MClass]]
1417 # Return all parents of a `mclass` in `self`
1418 private fun parent_mclasses
(mclass
: MClass): Set[MClass] do
1419 if not self.parent_mclasses_cache
.has_key
(mclass
) then
1420 var parents
= new HashSet[MClass]
1421 if self.flatten_mclass_hierarchy
.has
(mclass
) then
1422 for sup
in self.flatten_mclass_hierarchy
[mclass
].direct_greaters
do
1423 if sup
== mclass
then continue
1427 self.parent_mclasses_cache
[mclass
] = parents
1429 return self.parent_mclasses_cache
[mclass
]
1432 private var parent_mclasses_cache
: Map[MClass, Set[MClass]] = new HashMap[MClass, Set[MClass]]
1434 # Return all sub mclasses (directs and indirects) of a `mclass` in `self`
1435 private fun sub_mclasses
(mclass
: MClass): Set[MClass] do
1436 if not self.sub_mclasses_cache
.has_key
(mclass
) then
1437 var subs
= new HashSet[MClass]
1438 if self.flatten_mclass_hierarchy
.has
(mclass
) then
1439 for sub
in self.flatten_mclass_hierarchy
[mclass
].smallers
do
1440 if sub
== mclass
then continue
1444 self.sub_mclasses_cache
[mclass
] = subs
1446 return self.sub_mclasses_cache
[mclass
]
1449 private var sub_mclasses_cache
: Map[MClass, Set[MClass]] = new HashMap[MClass, Set[MClass]]
1451 # All 'mproperties' associated to all 'mclassdefs' of `mclass`
1452 private fun properties
(mclass
: MClass): Set[MProperty] do
1453 if not self.properties_cache
.has_key
(mclass
) then
1454 var properties
= new HashSet[MProperty]
1455 var parents
= self.super_mclasses
(mclass
)
1456 for parent
in parents
do
1457 properties
.add_all
(self.properties
(parent
))
1460 for mclassdef
in mclass
.mclassdefs
do
1461 for mpropdef
in mclassdef
.mpropdefs
do
1462 properties
.add
(mpropdef
.mproperty
)
1465 self.properties_cache
[mclass
] = properties
1467 return properties_cache
[mclass
]
1470 private var properties_cache
: Map[MClass, Set[MProperty]] = new HashMap[MClass, Set[MProperty]]
1473 # A sorter for linearize list of types
1475 super AbstractSorter[MType]
1477 private var mmodule
: MModule
1479 init(mmodule
: MModule) do self.mmodule
= mmodule
1481 redef fun compare
(a
, b
) do
1484 else if a
.is_subtype
(self.mmodule
, null, b
) then
1491 # A sorter for reverse linearization
1492 class ReverseTypeSorter
1495 init(mmodule
: MModule) do end
1497 redef fun compare
(a
, b
) do
1500 else if a
.is_subtype
(self.mmodule
, null, b
) then
1507 # A sorter for linearize list of classes
1508 private class ClassSorter
1509 super AbstractSorter[MClass]
1511 var mmodule
: MModule
1513 redef fun compare
(a
, b
) do
1516 else if self.mmodule
.flatten_mclass_hierarchy
.has
(a
) and self.mmodule
.flatten_mclass_hierarchy
[a
].greaters
.has
(b
) then
1523 # A sorter for reverse linearization
1524 private class ReverseClassSorter
1525 super AbstractSorter[MClass]
1527 var mmodule
: MModule
1529 redef fun compare
(a
, b
) do
1532 else if self.mmodule
.flatten_mclass_hierarchy
.has
(a
) and self.mmodule
.flatten_mclass_hierarchy
[a
].greaters
.has
(b
) then