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
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
160 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mtypes
(element
, elements
)
161 redef fun is_element_mi
(element
, elements
) do return self.super_elements
(element
, elements
).length
> 1
162 redef fun sub_elements
(element
, elements
) do do return self.mmodule
.sub_mtypes
(element
, elements
)
163 redef fun linearize
(elements
) do return self.mmodule
.linearize_mtypes
(elements
)
164 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mtypes
(elements
)
167 class NaiveTypeColoring
170 init(mainmodule
: MModule) do super
172 # naive coloring that use incremental coloring
173 redef fun colorize_elements
(elements
) do
175 self.coloration_result
[e
] = self.coloration_result
.length
180 abstract class TypePerfectHashing
183 init(mainmodule
: MModule) do super
185 fun compute_masks
(elements
: Set[T
], ids
: Map[T
, Int]): Map[T
, Int] do
187 # Create super type list
188 var supers
= new HashSet[T
]
189 supers
.add_all
(self.super_elements
(e
, elements
))
191 # Compute the hashing 'mask'
192 self.coloration_result
[e
] = compute_mask
(supers
, ids
)
194 return self.coloration_result
197 private fun compute_mask
(mtypes
: Set[T
], ids
: Map[T
, Int]): Int do
200 var used
= new List[Int]
202 var res
= op
(mask
, ids
[sup
])
203 if used
.has
(res
) then
209 if used
.length
== mtypes
.length
then break
215 private fun op
(mask
: Int, id
:Int): Int is abstract
216 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
219 class TypeModPerfectHashing
220 super TypePerfectHashing
221 init(mainmodule
: MModule) do super
222 redef fun op
(mask
, id
) do return mask
% id
225 class TypeAndPerfectHashing
226 super TypePerfectHashing
227 init(mainmodule
: MModule) do super
228 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
233 super AbstractColoring[MClass]
237 private var mmodule
: MModule
240 private var super_elements_cache
: Map[T
, Set[T
]] = new HashMap[T
, Set[T
]]
241 private var parent_elements_cache
: Map[T
, Set[T
]] = new HashMap[T
, Set[T
]]
242 private var sub_elements_cache
: Map[T
, Set[T
]] = new HashMap[T
, Set[T
]]
244 init(mainmodule
: MModule) do self.mmodule
= mainmodule
247 fun build_type_tables
(mclasses
: Set[T
], colors
: Map[T
, Int]): Map[T
, Array[nullable T
]] do
248 var tables
= new HashMap[T
, Array[nullable T
]]
250 for mclasse
in mclasses
do
251 var table
= new Array[nullable T
]
252 var supers
= new HashSet[T
]
253 supers
.add_all
(self.super_elements
(mclasse
, mclasses
))
256 var color
= colors
[sup
]
257 if table
.length
<= color
then
258 for i
in [table
.length
.. color
[ do
264 tables
[mclasse
] = table
269 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mclasses
(element
)
270 fun parent_elements
(element
: MClass): Set[MClass] do return self.mmodule
.parent_mclasses
(element
)
271 redef fun is_element_mi
(element
, elements
) do return self.parent_elements
(element
).length
> 1
272 redef fun sub_elements
(element
, elements
) do do return self.mmodule
.sub_mclasses
(element
)
273 redef fun linearize
(elements
) do return self.mmodule
.linearize_mclasses
(elements
)
274 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mclasses
(elements
)
277 # incremental coloring (very naive)
278 class NaiveClassColoring
281 init(mainmodule
: MModule) do
285 # naive coloring that use incremental coloring
286 redef fun colorize_elements
(elements
) do
288 self.coloration_result
[e
] = self.coloration_result
.length
293 abstract class ClassPerfectHashing
296 init(mainmodule
: MModule) do
300 fun compute_masks
(elements
: Set[T
], ids
: Map[T
, Int]): Map[T
, Int] do
302 # Create super type list
303 var supers
= new HashSet[T
]
304 supers
.add_all
(self.super_elements
(e
, elements
))
306 # Compute the hashing 'mask'
307 self.coloration_result
[e
] = compute_mask
(supers
, ids
)
309 return self.coloration_result
313 fun hash_type_tables
(mtypes
: Set[T
], ids
: Map[T
, Int], masks
: Map[T
, Int]): Map[T
, Array[nullable T
]] do
314 var tables
= new HashMap[T
, Array[nullable T
]]
316 for mtype
in mtypes
do
317 var table
= new Array[nullable T
]
318 var supers
= new HashSet[T
]
319 supers
.add_all
(self.super_elements
(mtype
, mtypes
))
323 var color
= phash
(ids
[sup
], masks
[mtype
])
324 if table
.length
<= color
then
325 for i
in [table
.length
.. color
[ do
331 tables
[mtype
] = table
336 private fun compute_mask
(mtypes
: Set[T
], ids
: Map[T
, Int]): Int do
339 var used
= new List[Int]
341 var res
= op
(mask
, ids
[sup
])
342 if used
.has
(res
) then
348 if used
.length
== mtypes
.length
then break
354 private fun op
(mask
: Int, id
:Int): Int is abstract
355 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
358 class ClassModPerfectHashing
359 super ClassPerfectHashing
360 init(mainmodule
: MModule) do
363 redef fun op
(mask
, id
) do return mask
% id
366 class ClassAndPerfectHashing
367 super ClassPerfectHashing
368 init(mainmodule
: MModule) do
371 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
375 class PropertyColoring
377 type MPROP: MProperty
378 type MPROPDEF: MPropDef
380 private var class_coloring
: ClassColoring
381 private var coloration_result
: Map[MPROP, Int] = new HashMap[MPROP, Int]
383 init(class_coloring
: ClassColoring) do
384 self.class_coloring
= class_coloring
387 fun colorize
: Map[MPROP, Int] do
388 colorize_core_properties
389 colorize_crown_properties
390 return self.coloration_result
393 fun build_property_tables
: Map[MClass, Array[nullable MPROPDEF]] do
394 var tables
= new HashMap[MClass, Array[nullable MPROPDEF]]
395 var mclasses
= self.class_coloring
.coloration_result
.keys
396 for mclass
in mclasses
do
397 var table
= new Array[nullable MPROPDEF]
398 # first, fill table from parents by reverse linearization order
399 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
400 var lin
= self.class_coloring
.reverse_linearize
(parents
)
402 for mproperty
in self.properties
(parent
) do
403 var color
= self.coloration_result
[mproperty
]
404 if table
.length
<= color
then
405 for i
in [table
.length
.. color
[ do
409 for mpropdef
in mproperty
.mpropdefs
do
410 if mpropdef
.mclassdef
.mclass
== parent
then
411 table
[color
] = mpropdef
417 # then override with local properties
418 for mproperty
in self.properties
(mclass
) do
419 var color
= self.coloration_result
[mproperty
]
420 if table
.length
<= color
then
421 for i
in [table
.length
.. color
[ do
425 for mpropdef
in mproperty
.mpropdefs
do
426 if mpropdef
.mclassdef
.mclass
== mclass
then
427 table
[color
] = mpropdef
431 tables
[mclass
] = table
436 # Colorize properties of the core hierarchy
437 private fun colorize_core_properties
do
438 var mclasses
= self.class_coloring
.core
441 for mclass
in mclasses
do
442 var color
= min_color
444 # if the class is root, get the minimal color
445 if self.class_coloring
.parent_elements
(mclass
).length
== 0 then
446 colorize_elements
(self.properties
(mclass
), color
)
448 # check last color used by parents
449 color
= max_color
(color
, self.class_coloring
.parent_elements
(mclass
))
450 # check max color used in conflicts
451 if self.class_coloring
.conflicts_graph
.has_key
(mclass
) then
452 color
= max_color
(color
, self.class_coloring
.conflicts_graph
[mclass
])
456 colorize_elements
(self.properties
(mclass
), color
)
461 # Colorize properties of the crown hierarchy
462 private fun colorize_crown_properties
do
463 for mclass
in self.class_coloring
.crown
do
464 colorize_elements
(self.properties
(mclass
), max_color
(0, self.class_coloring
.parent_elements
(mclass
)))
468 # Colorize a collection of properties given a starting color
469 private fun colorize_elements
(elements
: Collection[MPROP], start_color
: Int) do
470 for element
in elements
do
471 if self.coloration_result
.has_key
(element
) then continue
472 self.coloration_result
[element
] = start_color
477 private fun max_color
(min_color
: Int, mclasses
: Collection[MClass]): Int do
478 var max_color
= min_color
480 for mclass
in mclasses
do
481 for mproperty
in self.properties
(mclass
) do
482 var color
= min_color
483 if self.coloration_result
.has_key
(mproperty
) then
484 color
= self.coloration_result
[mproperty
]
485 if color
>= max_color
then max_color
= color
+ 1
493 private var properties_cache
: Map[MClass, Set[MPROP]] = new HashMap[MClass, Set[MPROP]]
495 # All 'mproperties' associated to all 'mclassdefs' of the class
496 private fun properties
(mclass
: MClass): Set[MPROP] do
497 if not self.properties_cache
.has_key
(mclass
) then
498 var properties
= new HashSet[MPROP]
499 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
500 for parent
in parents
do
501 properties
.add_all
(self.properties
(parent
))
504 for mclassdef
in mclass
.mclassdefs
do
505 for mpropdef
in mclassdef
.mpropdefs
do
506 var mproperty
= mpropdef
.mproperty
507 if mproperty
isa MPROP then
508 properties
.add
(mproperty
)
512 self.properties_cache
[mclass
] = properties
514 return properties_cache
[mclass
]
520 super PropertyColoring
522 redef type MPROP: MMethod
523 redef type MPROPDEF: MMethodDef
524 init(class_coloring
: ClassColoring) do end
527 # MAttribute coloring
528 class AttributeColoring
529 super PropertyColoring
531 redef type MPROP: MAttribute
532 redef type MPROPDEF: MAttributeDef
533 init(class_coloring
: ClassColoring) do end
536 # MVirtualTypeProp coloring
538 super PropertyColoring
540 redef type MPROP: MVirtualTypeProp
541 redef type MPROPDEF: MVirtualTypeDef
542 init(class_coloring
: ClassColoring) do end
545 class NaiveVTColoring
548 init(class_coloring
: ClassColoring) do end
550 redef fun colorize
: Map[MPROP, Int] do
551 var mclasses
= new HashSet[MClass]
552 mclasses
.add_all
(self.class_coloring
.core
)
553 mclasses
.add_all
(self.class_coloring
.crown
)
556 for mclass
in mclasses
do
557 min_color
= max_color
(min_color
, mclasses
)
558 colorize_elements
(self.properties
(mclass
), min_color
)
560 return self.coloration_result
564 abstract class VTPerfectHashing
567 private var masks
: Map[MClass, Int] = new HashMap[MClass, Int]
569 init(class_coloring
: ClassColoring) do end
571 redef fun colorize
: Map[MPROP, Int] do
572 var mclasses
= new HashSet[MClass]
573 mclasses
.add_all
(self.class_coloring
.core
)
574 mclasses
.add_all
(self.class_coloring
.crown
)
575 for mclass
in mclasses
do
576 var vts
= self.properties
(mclass
)
578 if coloration_result
.has_key
(vt
) then continue
579 coloration_result
[vt
] = coloration_result
.length
+ 1
582 return self.coloration_result
585 fun compute_masks
: Map[MClass, Int] do
586 var mclasses
= new HashSet[MClass]
587 mclasses
.add_all
(self.class_coloring
.core
)
588 mclasses
.add_all
(self.class_coloring
.crown
)
589 for mclass
in mclasses
do
590 self.masks
[mclass
] = compute_mask
(self.properties
(mclass
))
595 private fun compute_mask
(vts
: Set[MPROP]): Int do
598 var used
= new List[Int]
600 var res
= op
(mask
, self.coloration_result
[vt
])
601 if used
.has
(res
) then
607 if used
.length
== vts
.length
then break
613 redef fun build_property_tables
do
614 var tables
= new HashMap[MClass, Array[nullable MPROPDEF]]
616 for mclass
in self.class_coloring
.coloration_result
.keys
do
617 var table
= new Array[nullable MPROPDEF]
618 # first, fill table from parents by reverse linearization order
619 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
620 var lin
= self.class_coloring
.reverse_linearize
(parents
)
622 for mproperty
in self.properties
(parent
) do
623 var color
= phash
(self.coloration_result
[mproperty
], masks
[mclass
])
624 if table
.length
<= color
then
625 for i
in [table
.length
.. color
[ do
629 for mpropdef
in mproperty
.mpropdefs
do
630 if mpropdef
.mclassdef
.mclass
== parent
then
631 table
[color
] = mpropdef
637 # then override with local properties
638 for mproperty
in self.properties
(mclass
) do
639 var color
= phash
(self.coloration_result
[mproperty
], masks
[mclass
])
640 if table
.length
<= color
then
641 for i
in [table
.length
.. color
[ do
645 for mpropdef
in mproperty
.mpropdefs
do
646 if mpropdef
.mclassdef
.mclass
== mclass
then
647 table
[color
] = mpropdef
651 tables
[mclass
] = table
656 private fun op
(mask
: Int, id
:Int): Int is abstract
657 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
661 class VTModPerfectHashing
662 super VTPerfectHashing
663 init(class_coloring
: ClassColoring) do end
664 redef fun op
(mask
, id
) do return mask
% id
667 class VTAndPerfectHashing
668 super VTPerfectHashing
669 init(class_coloring
: ClassColoring) do end
670 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
673 # MParameterType coloring
675 private var class_coloring
: ClassColoring
676 private var coloration_result
: Map[MParameterType, Int] = new HashMap[MParameterType, Int]
678 init(class_coloring
: ClassColoring) do
679 self.class_coloring
= class_coloring
682 fun colorize
: Map[MParameterType, Int] do
683 colorize_core_properties
684 colorize_crown_properties
685 return self.coloration_result
688 # Colorize properties of the core hierarchy
689 private fun colorize_core_properties
do
690 var mclasses
= self.class_coloring
.core
693 for mclass
in mclasses
do
694 var color
= min_color
696 # if the class is root, get the minimal color
697 if self.class_coloring
.parent_elements
(mclass
).length
== 0 then
698 colorize_elements
(self.fts
(mclass
), color
)
700 # check last color used by parents
701 color
= max_color
(color
, self.class_coloring
.parent_elements
(mclass
))
702 # check max color used in conflicts
703 if self.class_coloring
.conflicts_graph
.has_key
(mclass
) then
704 color
= max_color
(color
, self.class_coloring
.conflicts_graph
[mclass
])
707 colorize_elements
(self.fts
(mclass
), color
)
712 # Colorize properties of the crown hierarchy
713 private fun colorize_crown_properties
do
714 for mclass
in self.class_coloring
.crown
do
715 colorize_elements
(self.fts
(mclass
), max_color
(0, self.class_coloring
.parent_elements
(mclass
)))
719 # Colorize a collection of properties given a starting color
720 private fun colorize_elements
(elements
: Collection[MParameterType], start_color
: Int) do
721 for element
in elements
do
722 if self.coloration_result
.has_key
(element
) then continue
723 self.coloration_result
[element
] = start_color
728 private fun max_color
(min_color
: Int, mclasses
: Collection[MClass]): Int do
729 var max_color
= min_color
731 for mclass
in mclasses
do
732 for ft
in self.fts
(mclass
) do
733 var color
= min_color
734 if self.coloration_result
.has_key
(ft
) then
735 color
= self.coloration_result
[ft
]
736 if color
>= max_color
then max_color
= color
+ 1
744 private var fts_cache
: Map[MClass, Set[MParameterType]] = new HashMap[MClass, Set[MParameterType]]
746 private fun fts
(mclass
: MClass): Set[MParameterType] do
747 if not self.fts_cache
.has_key
(mclass
) then
748 var fts
= new HashSet[MParameterType]
749 var mclass_type
= mclass
.mclass_type
750 if mclass_type
isa MGenericType then
751 for ft
in mclass_type
.arguments
do
752 fts
.add
(ft
.as(MParameterType))
755 self.fts_cache
[mclass
] = fts
757 return fts_cache
[mclass
]
760 fun build_ft_tables
: Map[MClass, Array[nullable MParameterType]] do
761 var tables
= new HashMap[MClass, Array[nullable MParameterType]]
763 for mclass
in self.class_coloring
.coloration_result
.keys
do
764 var table
= new Array[nullable MParameterType]
766 # first, fill table from parents
767 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
768 for parent
in parents
do
769 for ft
in self.fts
(parent
) do
770 var color
= self.coloration_result
[ft
]
771 if table
.length
<= color
then
772 for i
in [table
.length
.. color
[ do
780 # then override with local properties
781 for ft
in self.fts
(mclass
) do
782 var color
= self.coloration_result
[ft
]
783 if table
.length
<= color
then
784 for i
in [table
.length
.. color
[ do
790 tables
[mclass
] = table
796 class NaiveFTColoring
799 init(class_coloring
: ClassColoring) do end
801 redef fun colorize
: Map[MParameterType, Int] do
802 var mclasses
= new HashSet[MClass]
803 mclasses
.add_all
(self.class_coloring
.core
)
804 mclasses
.add_all
(self.class_coloring
.crown
)
807 for mclass
in mclasses
do
808 min_color
= max_color
(min_color
, mclasses
)
809 colorize_elements
(self.fts
(mclass
), min_color
)
811 return self.coloration_result
815 abstract class FTPerfectHashing
818 private var masks
: Map[MClass, Int] = new HashMap[MClass, Int]
820 init(class_coloring
: ClassColoring) do end
822 redef fun colorize
: Map[MParameterType, Int] do
823 var mclasses
= new HashSet[MClass]
824 mclasses
.add_all
(self.class_coloring
.core
)
825 mclasses
.add_all
(self.class_coloring
.crown
)
826 for mclass
in mclasses
do
827 for ft
in self.fts
(mclass
) do
828 if coloration_result
.has_key
(ft
) then continue
829 coloration_result
[ft
] = coloration_result
.length
+ 1
832 return self.coloration_result
835 fun compute_masks
: Map[MClass, Int] do
836 var mclasses
= new HashSet[MClass]
837 mclasses
.add_all
(self.class_coloring
.core
)
838 mclasses
.add_all
(self.class_coloring
.crown
)
839 for mclass
in mclasses
do
840 var fts
= new HashSet[MParameterType]
841 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
842 for parent
in parents
do
843 fts
.add_all
(self.fts
(parent
))
845 fts
.add_all
(self.fts
(mclass
))
846 self.masks
[mclass
] = compute_mask
(fts
)
851 private fun compute_mask
(fts
: Set[MParameterType]): Int do
854 var used
= new List[Int]
856 var res
= op
(mask
, self.coloration_result
[ft
])
857 if used
.has
(res
) then
863 if used
.length
== fts
.length
then break
869 redef fun build_ft_tables
do
870 var tables
= new HashMap[MClass, Array[nullable MParameterType]]
872 for mclass
in self.class_coloring
.coloration_result
.keys
do
873 var table
= new Array[nullable MParameterType]
875 # first, fill table from parents
876 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
877 for parent
in parents
do
878 for ft
in self.fts
(parent
) do
879 var color
= phash
(self.coloration_result
[ft
], masks
[mclass
])
880 if table
.length
<= color
then
881 for i
in [table
.length
.. color
[ do
889 # then override with local properties
890 for ft
in self.fts
(mclass
) do
891 var color
= phash
(self.coloration_result
[ft
], masks
[mclass
])
892 if table
.length
<= color
then
893 for i
in [table
.length
.. color
[ do
899 tables
[mclass
] = table
904 private fun op
(mask
: Int, id
:Int): Int is abstract
905 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
908 class FTModPerfectHashing
909 super FTPerfectHashing
910 init(class_coloring
: ClassColoring) do end
911 redef fun op
(mask
, id
) do return mask
% id
914 class FTAndPerfectHashing
915 super FTPerfectHashing
916 init(class_coloring
: ClassColoring) do end
917 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
920 # Live Entries coloring
921 class LiveEntryColoring
923 private var coloration_result
: Map[MType, Int] = new HashMap[MType, Int]
924 private var conflicts_graph_cache
: nullable HashMap[MType, Set[MType]]
925 var livetypes_tables_sizes
: nullable Map[MClass, Array[Int]]
929 fun colorize
(elements
: Collection[MType]): Map[MType, Int] do
931 build_conflicts_graph
(elements
)
934 colorize_elements
(elements
)
936 return coloration_result
940 fun build_livetype_tables
(mtypes
: Set[MType]): Map[MClass, Array[nullable Object]] do
941 var livetypes_tables
= new HashMap[MClass, Array[nullable Object]]
942 self.livetypes_tables_sizes
= new HashMap[MClass, Array[Int]]
944 for mtype
in mtypes
do
945 if mtype
isa MGenericType then
946 var table
: Array[nullable Object]
947 var sizes
: Array[Int]
948 if livetypes_tables
.has_key
(mtype
.mclass
) then
949 table
= livetypes_tables
[mtype
.mclass
]
951 table
= new Array[nullable Object]
952 livetypes_tables
[mtype
.mclass
] = table
954 if livetypes_tables_sizes
.has_key
(mtype
.mclass
) then
955 sizes
= livetypes_tables_sizes
[mtype
.mclass
]
957 sizes
= new Array[Int]
958 livetypes_tables_sizes
[mtype
.mclass
] = sizes
960 build_livetype_table
(mtype
, 0, table
, sizes
)
964 return livetypes_tables
967 # Build live gentype table recursively
968 private fun build_livetype_table
(mtype
: MGenericType, current_rank
: Int, table
: Array[nullable Object], sizes
: Array[Int]) do
969 var ft
= mtype
.arguments
[current_rank
]
970 if not self.coloration_result
.has_key
(ft
) then return
971 var color
= self.coloration_result
[ft
]
973 if current_rank
>= sizes
.length
then
974 sizes
[current_rank
] = color
+ 1
975 else if color
>= sizes
[current_rank
] then
976 sizes
[current_rank
] = color
+ 1
979 if color
> table
.length
then
980 for i
in [table
.length
.. color
[ do table
[i
] = null
983 if current_rank
== mtype
.arguments
.length
- 1 then
986 var ft_table
: Array[nullable Object]
987 if color
< table
.length
and table
[color
] != null then
988 ft_table
= table
[color
].as(Array[nullable Object])
990 ft_table
= new Array[nullable Object]
992 table
[color
] = ft_table
993 build_livetype_table
(mtype
, current_rank
+ 1, ft_table
, sizes
)
997 # Colorize a collection of elements
998 fun colorize_elements
(elements
: Collection[MType]) do
1001 for element
in elements
do
1002 var color
= min_color
1003 while not self.is_color_free
(element
, color
) do
1006 coloration_result
[element
] = color
1011 # Check if a related element to the element already use the color
1012 private fun is_color_free
(element
: MType, color
: Int): Bool do
1013 if conflicts_graph
.has_key
(element
) then
1014 for st
in conflicts_graph
[element
] do
1015 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
1021 # look for types in the same generic signatures
1022 private fun build_conflicts_graph
(elements
: Collection[MType]) do
1023 # regroup types by classes
1024 var genclasses
= new HashMap[MClass, Set[MType]]
1025 for e
in elements
do
1026 if e
isa MGenericType then
1027 if not genclasses
.has_key
(e
.mclass
) then
1028 genclasses
[e
.mclass
] = new HashSet[MType]
1030 genclasses
[e
.mclass
].add
(e
)
1035 self.conflicts_graph_cache
= new HashMap[MType, Set[MType]]
1036 for mclass
, mtypes
in genclasses
do
1038 for rank
in [0..mclass
.arity
[ do
1039 # for each live type
1040 for mtype
in mtypes
do
1041 var mclasstype
: MClassType
1042 if mtype
isa MNullableType then
1043 mclasstype
= mtype
.mtype
.as(MClassType)
1045 mclasstype
= mtype
.as(MClassType)
1047 var ft
= mclasstype
.arguments
[rank
]
1048 for otype
in mtypes
do
1049 if mtype
== otype
then continue
1050 var oclasstype
: MClassType
1051 if otype
isa MNullableType then
1052 oclasstype
= otype
.mtype
.as(MClassType)
1054 oclasstype
= otype
.as(MClassType)
1056 var oft
= oclasstype
.arguments
[rank
]
1057 self.add_conflict
(ft
, oft
)
1064 private fun add_conflict
(mtype
: MType, otype
: MType) do
1065 if mtype
== otype
then return
1066 if not self.conflicts_graph_cache
.has_key
(mtype
) then self.conflicts_graph_cache
[mtype
] = new HashSet[MType]
1067 self.conflicts_graph_cache
[mtype
].add
(otype
)
1068 if not self.conflicts_graph_cache
.has_key
(otype
) then self.conflicts_graph_cache
[otype
] = new HashSet[MType]
1069 self.conflicts_graph_cache
[otype
].add
(mtype
)
1071 private fun conflicts_graph
: Map[MType, Set[MType]] do return conflicts_graph_cache
.as(not null)
1074 class NaiveLiveEntryColoring
1075 super LiveEntryColoring
1079 redef fun colorize_elements
(elements
: Collection[MType]) do
1081 for element
in elements
do
1082 coloration_result
[element
] = color
1088 # live unanchored coloring
1089 class UnanchoredTypeColoring
1091 private var coloration_result
: Map[MType, Int] = new HashMap[MType, Int]
1092 private var conflicts_graph
: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
1096 fun colorize
(elements
: Map[MClassType, Set[MType]]): Map[MType, Int] do
1097 build_conflicts_graph
(elements
)
1098 colorize_elements
(elements
)
1099 return coloration_result
1102 fun build_tables
(elements
: Map[MClassType, Set[MType]]): Map[MClassType, Array[nullable MType]] do
1103 var tables
= new HashMap[MClassType, Array[nullable MType]]
1105 for mclasstype
, mtypes
in elements
do
1106 var table
= new Array[nullable MType]
1107 for mtype
in mtypes
do
1108 var color
= self.coloration_result
[mtype
]
1109 if table
.length
<= color
then
1110 for i
in [table
.length
.. color
[ do
1114 table
[color
] = mtype
1116 tables
[mclasstype
] = table
1121 # Colorize a collection of elements
1122 fun colorize_elements
(elements
: Map[MClassType, Set[MType]]) do
1124 for mclasstype
, mclasstypes
in elements
do
1125 for element
in mclasstypes
do
1126 if self.coloration_result
.has_key
(element
) then continue
1127 var color
= min_color
1128 while not self.is_color_free
(element
, color
) do
1131 coloration_result
[element
] = color
1137 # Check if a related element to the element already use the color
1138 private fun is_color_free
(element
: MType, color
: Int): Bool do
1139 if conflicts_graph
.has_key
(element
) then
1140 for st
in conflicts_graph
[element
] do
1141 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
1147 # look for unanchored types generated by the same type
1148 private fun build_conflicts_graph
(elements
: Map[MClassType, Set[MType]]) do
1149 for mclasstype
, mtypes
in elements
do
1150 for mtype
in mtypes
do
1151 for otype
in mtypes
do
1152 if otype
== mtype
then continue
1153 self.add_conflict
(mtype
, otype
)
1159 private fun add_conflict
(mtype
: MType, otype
: MType) do
1160 if mtype
== otype
then return
1161 if not self.conflicts_graph
.has_key
(mtype
) then self.conflicts_graph
[mtype
] = new HashSet[MType]
1162 self.conflicts_graph
[mtype
].add
(otype
)
1163 if not self.conflicts_graph
.has_key
(otype
) then self.conflicts_graph
[otype
] = new HashSet[MType]
1164 self.conflicts_graph
[otype
].add
(mtype
)
1168 class NaiveUnanchoredTypeColoring
1169 super UnanchoredTypeColoring
1173 redef fun colorize_elements
(elements
: Map[MClassType, Set[MType]]) do
1175 for mclasstype
, mclasstypes
in elements
do
1176 for element
in mclasstypes
do
1177 coloration_result
[element
] = color
1184 abstract class UnanchoredTypePerfectHashing
1185 super NaiveUnanchoredTypeColoring
1187 private var masks
: Map[MClassType, Int] = new HashMap[MClassType, Int]
1191 redef fun colorize_elements
(elements
: Map[MClassType, Set[MType]]) do
1193 for mclasstype
, mclasstypes
in elements
do
1194 for element
in mclasstypes
do
1195 coloration_result
[element
] = color
1201 fun compute_masks
(elements
: Map[MClassType, Set[MType]]): Map[MClassType, Int] do
1202 for mclasstype
, mtypes
in elements
do
1203 self.masks
[mclasstype
] = compute_mask
(mtypes
)
1208 private fun compute_mask
(mtypes
: Set[MType]): Int do
1211 var used
= new List[Int]
1212 for mtype
in mtypes
do
1213 var res
= op
(mask
, self.coloration_result
[mtype
])
1214 if used
.has
(res
) then
1220 if used
.length
== mtypes
.length
then break
1226 redef fun build_tables
(elements
: Map[MClassType, Set[MType]]): Map[MClassType, Array[nullable MType]] do
1227 var tables
= new HashMap[MClassType, Array[nullable MType]]
1229 for mclasstype
, mtypes
in elements
do
1230 var table
= new Array[nullable MType]
1231 for mtype
in mtypes
do
1232 var color
= phash
(self.coloration_result
[mtype
], masks
[mclasstype
])
1233 if table
.length
<= color
then
1234 for i
in [table
.length
.. color
[ do
1238 table
[color
] = mtype
1240 tables
[mclasstype
] = table
1245 private fun op
(mask
: Int, id
:Int): Int is abstract
1246 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
1249 class UnanchoredTypeModPerfectHashing
1250 super UnanchoredTypePerfectHashing
1252 redef fun op
(mask
, id
) do return mask
% id
1255 class UnanchoredTypeAndPerfectHashing
1256 super UnanchoredTypePerfectHashing
1258 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
1264 redef class HashSet[E
]
1265 init from
(elements
: Collection[E
]) do
1267 self.add_all
(elements
)
1271 redef class Array[E
]
1272 init from
(elements
: Collection[E
]) do
1274 self.add_all
(elements
)
1277 # Return a new Array with the elements only contened in 'self' and not in 'o'
1278 fun -(o
: Array[E
]): Array[E
] do
1279 var res
= new Array[E
]
1280 for e
in self do if not o
.has
(e
) then res
.add
(e
)
1287 # Return a linearization of a set of mtypes
1288 private fun linearize_mtypes
(mtypes
: Set[MType]): Array[MType] do
1289 var lin
= new Array[MType].from
(mtypes
)
1290 var sorter
= new TypeSorter(self)
1295 # Return a reverse linearization of a set of mtypes
1296 private fun reverse_linearize_mtypes
(mtypes
: Set[MType]): Array[MType] do
1297 var lin
= new Array[MType].from
(mtypes
)
1298 var sorter
= new ReverseTypeSorter(self)
1303 # Return super types of a `mtype` in `self`
1304 private fun super_mtypes
(mtype
: MType, mtypes
: Set[MType]): Set[MType] do
1305 if not self.super_mtypes_cache
.has_key
(mtype
) then
1306 var supers
= new HashSet[MType]
1307 for otype
in mtypes
do
1308 if otype
== mtype
then continue
1309 if mtype
.is_subtype
(self, null, otype
) then
1313 self.super_mtypes_cache
[mtype
] = supers
1315 return self.super_mtypes_cache
[mtype
]
1318 private var super_mtypes_cache
: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
1320 # Return all sub mtypes (directs and indirects) of a `mtype` in `self`
1321 private fun sub_mtypes
(mtype
: MType, mtypes
: Set[MType]): Set[MType] do
1322 if not self.sub_mtypes_cache
.has_key
(mtype
) then
1323 var subs
= new HashSet[MType]
1324 for otype
in mtypes
do
1325 if otype
== mtype
then continue
1326 if otype
.is_subtype
(self, null, mtype
) then
1330 self.sub_mtypes_cache
[mtype
] = subs
1332 return self.sub_mtypes_cache
[mtype
]
1335 private var sub_mtypes_cache
: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
1337 # Return a linearization of a set of mclasses
1338 private fun linearize_mclasses
(mclasses
: Set[MClass]): Array[MClass] do
1339 var lin
= new Array[MClass].from
(mclasses
)
1340 var sorter
= new ClassSorter(self)
1345 # Return a reverse linearization of a set of mtypes
1346 private fun reverse_linearize_mclasses
(mclasses
: Set[MClass]): Array[MClass] do
1347 var lin
= new Array[MClass].from
(mclasses
)
1348 var sorter
= new ReverseClassSorter(self)
1353 # Return all super mclasses (directs and indirects) of a `mclass` in `self`
1354 private fun super_mclasses
(mclass
: MClass): Set[MClass] do
1355 if not self.super_mclasses_cache
.has_key
(mclass
) then
1356 var supers
= new HashSet[MClass]
1357 if self.flatten_mclass_hierarchy
.has
(mclass
) then
1358 for sup
in self.flatten_mclass_hierarchy
[mclass
].greaters
do
1359 if sup
== mclass
then continue
1363 self.super_mclasses_cache
[mclass
] = supers
1365 return self.super_mclasses_cache
[mclass
]
1368 private var super_mclasses_cache
: Map[MClass, Set[MClass]] = new HashMap[MClass, Set[MClass]]
1370 # Return all parents of a `mclass` in `self`
1371 private fun parent_mclasses
(mclass
: MClass): Set[MClass] do
1372 if not self.parent_mclasses_cache
.has_key
(mclass
) then
1373 var parents
= new HashSet[MClass]
1374 if self.flatten_mclass_hierarchy
.has
(mclass
) then
1375 for sup
in self.flatten_mclass_hierarchy
[mclass
].direct_greaters
do
1376 if sup
== mclass
then continue
1380 self.parent_mclasses_cache
[mclass
] = parents
1382 return self.parent_mclasses_cache
[mclass
]
1385 private var parent_mclasses_cache
: Map[MClass, Set[MClass]] = new HashMap[MClass, Set[MClass]]
1387 # Return all sub mclasses (directs and indirects) of a `mclass` in `self`
1388 private fun sub_mclasses
(mclass
: MClass): Set[MClass] do
1389 if not self.sub_mclasses_cache
.has_key
(mclass
) then
1390 var subs
= new HashSet[MClass]
1391 if self.flatten_mclass_hierarchy
.has
(mclass
) then
1392 for sub
in self.flatten_mclass_hierarchy
[mclass
].smallers
do
1393 if sub
== mclass
then continue
1397 self.sub_mclasses_cache
[mclass
] = subs
1399 return self.sub_mclasses_cache
[mclass
]
1402 private var sub_mclasses_cache
: Map[MClass, Set[MClass]] = new HashMap[MClass, Set[MClass]]
1404 # All 'mproperties' associated to all 'mclassdefs' of `mclass`
1405 private fun properties
(mclass
: MClass): Set[MProperty] do
1406 if not self.properties_cache
.has_key
(mclass
) then
1407 var properties
= new HashSet[MProperty]
1408 var parents
= self.super_mclasses
(mclass
)
1409 for parent
in parents
do
1410 properties
.add_all
(self.properties
(parent
))
1413 for mclassdef
in mclass
.mclassdefs
do
1414 for mpropdef
in mclassdef
.mpropdefs
do
1415 properties
.add
(mpropdef
.mproperty
)
1418 self.properties_cache
[mclass
] = properties
1420 return properties_cache
[mclass
]
1423 private var properties_cache
: Map[MClass, Set[MProperty]] = new HashMap[MClass, Set[MProperty]]
1426 # A sorter for linearize list of types
1428 super AbstractSorter[MType]
1430 private var mmodule
: MModule
1432 init(mmodule
: MModule) do self.mmodule
= mmodule
1434 redef fun compare
(a
, b
) do
1437 else if a
.is_subtype
(self.mmodule
, null, b
) then
1444 # A sorter for reverse linearization
1445 class ReverseTypeSorter
1448 init(mmodule
: MModule) do end
1450 redef fun compare
(a
, b
) do
1453 else if a
.is_subtype
(self.mmodule
, null, b
) then
1460 # A sorter for linearize list of classes
1461 private class ClassSorter
1462 super AbstractSorter[MClass]
1464 var mmodule
: MModule
1466 redef fun compare
(a
, b
) do
1469 else if self.mmodule
.flatten_mclass_hierarchy
.has
(a
) and self.mmodule
.flatten_mclass_hierarchy
[a
].greaters
.has
(b
) then
1476 # A sorter for reverse linearization
1477 private class ReverseClassSorter
1478 super AbstractSorter[MClass]
1480 var mmodule
: MModule
1482 redef fun compare
(a
, b
) do
1485 else if self.mmodule
.flatten_mclass_hierarchy
.has
(a
) and self.mmodule
.flatten_mclass_hierarchy
[a
].greaters
.has
(b
) then