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 TypeLayoutBuilder
23 abstract class AbstractColoring[E
: Object]
25 private var core
: Set[E
] = new HashSet[E
]
26 private var crown
: Set[E
] = new HashSet[E
]
27 private var border
: Set[E
] = new HashSet[E
]
29 private var coloration_result
: Map[E
, Int] = new HashMap[E
, Int]
33 fun colorize
(elements
: Set[E
]): Map[E
, Int] do
34 tag_elements
(elements
)
35 build_conflicts_graph
(elements
)
36 colorize_elements
(core
)
37 colorize_elements
(border
)
38 colorize_elements
(crown
)
39 return coloration_result
42 # Colorize a collection of elements
43 private fun colorize_elements
(elements
: Set[E
]) do
46 var lin
= reverse_linearize
(elements
)
49 while not self.is_color_free
(element
, elements
, color
) do
52 coloration_result
[element
] = color
57 # Check if a related element to the element already use the color
58 private fun is_color_free
(element
: E
, elements
: Set[E
], color
: Int): Bool do
59 if conflicts_graph
.has_key
(element
) then
60 for st
in conflicts_graph
[element
] do
61 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
64 for st
in self.super_elements
(element
, elements
) do
65 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
70 # Tag elements as core, crown or border
71 private fun tag_elements
(elements
: Set[E
]) do
72 for element
in elements
do
73 # Check if sub elements are all in single inheritance
74 var all_subelements_si
= true
75 for subelem
in self.sub_elements
(element
, elements
) do
76 if self.is_element_mi
(subelem
, elements
) then
77 all_subelements_si
= false
82 # Tag as core, crown or border
83 if self.is_element_mi
(element
, elements
) then
84 core
.add_all
(self.super_elements
(element
, elements
))
86 if all_subelements_si
then
89 else if not all_subelements_si
then
90 core
.add_all
(self.super_elements
(element
, elements
))
98 # Conflicts graph of elements hierarchy (two types are in conflict if they have common subelements)
99 private fun build_conflicts_graph
(elements
: Set[E
]) do
100 self.conflicts_graph
= new HashMap[E
, HashSet[E
]]
101 var core
= reverse_linearize
(self.core
)
103 for i
in self.linear_extension
(t
, elements
) do
104 if t
== i
then continue
106 var lin_i
= self.linear_extension
(i
, elements
)
108 for j
in self.linear_extension
(t
, elements
) do
109 if i
== j
or j
== t
then continue
110 var lin_j
= self.linear_extension
(j
, elements
)
112 var d_ij
= lin_i
- lin_j
113 var d_ji
= lin_j
- lin_i
116 if not conflicts_graph
.has_key
(ed1
) then conflicts_graph
[ed1
] = new HashSet[E
]
117 # add ed1 x ed2 to conflicts graph
118 for ed2
in d_ji
do conflicts_graph
[ed1
].add
(ed2
)
121 if not conflicts_graph
.has_key
(ed1
) then conflicts_graph
[ed1
] = new HashSet[E
]
122 # add ed1 x ed2 to conflicts graph
123 for ed2
in d_ji
do conflicts_graph
[ed1
].add
(ed2
)
130 private var conflicts_graph
: nullable HashMap[E
, Set[E
]]
132 # cache for linear_extensions
133 private var linear_extensions_cache
: Map[E
, Array[E
]] = new HashMap[E
, Array[E
]]
135 # Return a linear_extension of super_elements of the element
136 private fun linear_extension
(element
: E
, elements
: Set[E
]): Array[E
] do
137 if not self.linear_extensions_cache
.has_key
(element
) then
138 var supers
= new HashSet[E
]
140 supers
.add_all
(self.super_elements
(element
, elements
))
141 self.linear_extensions_cache
[element
] = self.linearize
(supers
)
143 return self.linear_extensions_cache
[element
]
146 private fun super_elements
(element
: E
, elements
: Set[E
]): Set[E
] is abstract
147 private fun sub_elements
(element
: E
, elements
: Set[E
]): Set[E
] is abstract
148 private fun is_element_mi
(element
: E
, elements
: Set[E
]): Bool is abstract
149 private fun linearize
(elements
: Set[E
]): Array[E
] is abstract
150 private fun reverse_linearize
(elements
: Set[E
]): Array[E
] is abstract
153 # MClassType coloring
155 super AbstractColoring[MType]
156 super TypeLayoutBuilder
160 private var mmodule
: MModule
162 init(mainmodule
: MModule) do self.mmodule
= mainmodule
164 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mtypes
(element
, elements
)
165 redef fun is_element_mi
(element
, elements
) do return self.super_elements
(element
, elements
).length
> 1
166 redef fun sub_elements
(element
, elements
) do do return self.mmodule
.sub_mtypes
(element
, elements
)
167 redef fun linearize
(elements
) do return self.mmodule
.linearize_mtypes
(elements
)
168 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mtypes
(elements
)
171 class NaiveTypeColoring
174 init(mainmodule
: MModule) do super
176 # naive coloring that use incremental coloring
177 redef fun colorize_elements
(elements
) do
179 self.coloration_result
[e
] = self.coloration_result
.length
184 abstract class TypePerfectHashing
187 init(mainmodule
: MModule) do super
189 fun compute_masks
(elements
: Set[T
], ids
: Map[T
, Int]): Map[T
, Int] do
191 # Create super type list
192 var supers
= new HashSet[T
]
193 supers
.add_all
(self.super_elements
(e
, elements
))
195 # Compute the hashing 'mask'
196 self.coloration_result
[e
] = compute_mask
(supers
, ids
)
198 return self.coloration_result
201 private fun compute_mask
(mtypes
: Set[T
], ids
: Map[T
, Int]): Int do
204 var used
= new List[Int]
206 var res
= op
(mask
, ids
[sup
])
207 if used
.has
(res
) then
213 if used
.length
== mtypes
.length
then break
219 private fun op
(mask
: Int, id
:Int): Int is abstract
220 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
223 class TypeModPerfectHashing
224 super TypePerfectHashing
225 init(mainmodule
: MModule) do super
226 redef fun op
(mask
, id
) do return mask
% id
229 class TypeAndPerfectHashing
230 super TypePerfectHashing
231 init(mainmodule
: MModule) do super
232 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
237 super AbstractColoring[MClass]
241 private var mmodule
: MModule
244 private var super_elements_cache
: Map[T
, Set[T
]] = new HashMap[T
, Set[T
]]
245 private var parent_elements_cache
: Map[T
, Set[T
]] = new HashMap[T
, Set[T
]]
246 private var sub_elements_cache
: Map[T
, Set[T
]] = new HashMap[T
, Set[T
]]
248 init(mainmodule
: MModule) do self.mmodule
= mainmodule
250 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mclasses
(element
)
251 fun parent_elements
(element
: MClass): Set[MClass] do return self.mmodule
.parent_mclasses
(element
)
252 redef fun is_element_mi
(element
, elements
) do return self.parent_elements
(element
).length
> 1
253 redef fun sub_elements
(element
, elements
) do do return self.mmodule
.sub_mclasses
(element
)
254 redef fun linearize
(elements
) do return self.mmodule
.linearize_mclasses
(elements
)
255 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mclasses
(elements
)
258 # incremental coloring (very naive)
259 class NaiveClassColoring
262 init(mainmodule
: MModule) do
266 # naive coloring that use incremental coloring
267 redef fun colorize_elements
(elements
) do
269 self.coloration_result
[e
] = self.coloration_result
.length
274 abstract class ClassPerfectHashing
277 init(mainmodule
: MModule) do
281 fun compute_masks
(elements
: Set[T
], ids
: Map[T
, Int]): Map[T
, Int] do
283 # Create super type list
284 var supers
= new HashSet[T
]
285 supers
.add_all
(self.super_elements
(e
, elements
))
287 # Compute the hashing 'mask'
288 self.coloration_result
[e
] = compute_mask
(supers
, ids
)
290 return self.coloration_result
293 private fun compute_mask
(mtypes
: Set[T
], ids
: Map[T
, Int]): Int do
296 var used
= new List[Int]
298 var res
= op
(mask
, ids
[sup
])
299 if used
.has
(res
) then
305 if used
.length
== mtypes
.length
then break
311 private fun op
(mask
: Int, id
:Int): Int is abstract
312 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
315 class ClassModPerfectHashing
316 super ClassPerfectHashing
317 init(mainmodule
: MModule) do
320 redef fun op
(mask
, id
) do return mask
% id
323 class ClassAndPerfectHashing
324 super ClassPerfectHashing
325 init(mainmodule
: MModule) do
328 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
332 class PropertyColoring
334 type MPROP: MProperty
335 type MPROPDEF: MPropDef
337 private var class_coloring
: ClassColoring
338 private var coloration_result
: Map[MPROP, Int] = new HashMap[MPROP, Int]
340 init(class_coloring
: ClassColoring) do
341 self.class_coloring
= class_coloring
344 fun colorize
: Map[MPROP, Int] do
345 colorize_core_properties
346 colorize_crown_properties
347 return self.coloration_result
350 fun build_property_tables
: Map[MClass, Array[nullable MPROPDEF]] do
351 var tables
= new HashMap[MClass, Array[nullable MPROPDEF]]
352 var mclasses
= self.class_coloring
.coloration_result
.keys
353 for mclass
in mclasses
do
354 var table
= new Array[nullable MPROPDEF]
355 # first, fill table from parents by reverse linearization order
356 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
357 var lin
= self.class_coloring
.reverse_linearize
(parents
)
359 for mproperty
in self.properties
(parent
) do
360 var color
= self.coloration_result
[mproperty
]
361 if table
.length
<= color
then
362 for i
in [table
.length
.. color
[ do
366 for mpropdef
in mproperty
.mpropdefs
do
367 if mpropdef
.mclassdef
.mclass
== parent
then
368 table
[color
] = mpropdef
374 # then override with local properties
375 for mproperty
in self.properties
(mclass
) do
376 var color
= self.coloration_result
[mproperty
]
377 if table
.length
<= color
then
378 for i
in [table
.length
.. color
[ do
382 for mpropdef
in mproperty
.mpropdefs
do
383 if mpropdef
.mclassdef
.mclass
== mclass
then
384 table
[color
] = mpropdef
388 tables
[mclass
] = table
393 # Colorize properties of the core hierarchy
394 private fun colorize_core_properties
do
395 var mclasses
= self.class_coloring
.core
398 for mclass
in mclasses
do
399 var color
= min_color
401 # if the class is root, get the minimal color
402 if self.class_coloring
.parent_elements
(mclass
).length
== 0 then
403 colorize_elements
(self.properties
(mclass
), color
)
405 # check last color used by parents
406 color
= max_color
(color
, self.class_coloring
.parent_elements
(mclass
))
407 # check max color used in conflicts
408 if self.class_coloring
.conflicts_graph
.has_key
(mclass
) then
409 color
= max_color
(color
, self.class_coloring
.conflicts_graph
[mclass
])
413 colorize_elements
(self.properties
(mclass
), color
)
418 # Colorize properties of the crown hierarchy
419 private fun colorize_crown_properties
do
420 for mclass
in self.class_coloring
.crown
do
421 colorize_elements
(self.properties
(mclass
), max_color
(0, self.class_coloring
.parent_elements
(mclass
)))
425 # Colorize a collection of properties given a starting color
426 private fun colorize_elements
(elements
: Collection[MPROP], start_color
: Int) do
427 for element
in elements
do
428 if self.coloration_result
.has_key
(element
) then continue
429 self.coloration_result
[element
] = start_color
434 private fun max_color
(min_color
: Int, mclasses
: Collection[MClass]): Int do
435 var max_color
= min_color
437 for mclass
in mclasses
do
438 for mproperty
in self.properties
(mclass
) do
439 var color
= min_color
440 if self.coloration_result
.has_key
(mproperty
) then
441 color
= self.coloration_result
[mproperty
]
442 if color
>= max_color
then max_color
= color
+ 1
450 private var properties_cache
: Map[MClass, Set[MPROP]] = new HashMap[MClass, Set[MPROP]]
452 # All 'mproperties' associated to all 'mclassdefs' of the class
453 private fun properties
(mclass
: MClass): Set[MPROP] do
454 if not self.properties_cache
.has_key
(mclass
) then
455 var properties
= new HashSet[MPROP]
456 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
457 for parent
in parents
do
458 properties
.add_all
(self.properties
(parent
))
461 for mclassdef
in mclass
.mclassdefs
do
462 for mpropdef
in mclassdef
.mpropdefs
do
463 var mproperty
= mpropdef
.mproperty
464 if mproperty
isa MPROP then
465 properties
.add
(mproperty
)
469 self.properties_cache
[mclass
] = properties
471 return properties_cache
[mclass
]
477 super PropertyColoring
479 redef type MPROP: MMethod
480 redef type MPROPDEF: MMethodDef
481 init(class_coloring
: ClassColoring) do end
484 # MAttribute coloring
485 class AttributeColoring
486 super PropertyColoring
488 redef type MPROP: MAttribute
489 redef type MPROPDEF: MAttributeDef
490 init(class_coloring
: ClassColoring) do end
493 # MVirtualTypeProp coloring
495 super PropertyColoring
497 redef type MPROP: MVirtualTypeProp
498 redef type MPROPDEF: MVirtualTypeDef
499 init(class_coloring
: ClassColoring) do end
502 class NaiveVTColoring
505 init(class_coloring
: ClassColoring) do end
507 redef fun colorize
: Map[MPROP, Int] do
508 var mclasses
= new HashSet[MClass]
509 mclasses
.add_all
(self.class_coloring
.core
)
510 mclasses
.add_all
(self.class_coloring
.crown
)
513 for mclass
in mclasses
do
514 min_color
= max_color
(min_color
, mclasses
)
515 colorize_elements
(self.properties
(mclass
), min_color
)
517 return self.coloration_result
521 abstract class VTPerfectHashing
524 private var masks
: Map[MClass, Int] = new HashMap[MClass, Int]
526 init(class_coloring
: ClassColoring) do end
528 redef fun colorize
: Map[MPROP, Int] do
529 var mclasses
= new HashSet[MClass]
530 mclasses
.add_all
(self.class_coloring
.core
)
531 mclasses
.add_all
(self.class_coloring
.crown
)
532 for mclass
in mclasses
do
533 var vts
= self.properties
(mclass
)
535 if coloration_result
.has_key
(vt
) then continue
536 coloration_result
[vt
] = coloration_result
.length
+ 1
539 return self.coloration_result
542 fun compute_masks
: Map[MClass, Int] do
543 var mclasses
= new HashSet[MClass]
544 mclasses
.add_all
(self.class_coloring
.core
)
545 mclasses
.add_all
(self.class_coloring
.crown
)
546 for mclass
in mclasses
do
547 self.masks
[mclass
] = compute_mask
(self.properties
(mclass
))
552 private fun compute_mask
(vts
: Set[MPROP]): Int do
555 var used
= new List[Int]
557 var res
= op
(mask
, self.coloration_result
[vt
])
558 if used
.has
(res
) then
564 if used
.length
== vts
.length
then break
570 redef fun build_property_tables
do
571 var tables
= new HashMap[MClass, Array[nullable MPROPDEF]]
573 for mclass
in self.class_coloring
.coloration_result
.keys
do
574 var table
= new Array[nullable MPROPDEF]
575 # first, fill table from parents by reverse linearization order
576 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
577 var lin
= self.class_coloring
.reverse_linearize
(parents
)
579 for mproperty
in self.properties
(parent
) do
580 var color
= phash
(self.coloration_result
[mproperty
], masks
[mclass
])
581 if table
.length
<= color
then
582 for i
in [table
.length
.. color
[ do
586 for mpropdef
in mproperty
.mpropdefs
do
587 if mpropdef
.mclassdef
.mclass
== parent
then
588 table
[color
] = mpropdef
594 # then override with local properties
595 for mproperty
in self.properties
(mclass
) do
596 var color
= phash
(self.coloration_result
[mproperty
], masks
[mclass
])
597 if table
.length
<= color
then
598 for i
in [table
.length
.. color
[ do
602 for mpropdef
in mproperty
.mpropdefs
do
603 if mpropdef
.mclassdef
.mclass
== mclass
then
604 table
[color
] = mpropdef
608 tables
[mclass
] = table
613 private fun op
(mask
: Int, id
:Int): Int is abstract
614 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
618 class VTModPerfectHashing
619 super VTPerfectHashing
620 init(class_coloring
: ClassColoring) do end
621 redef fun op
(mask
, id
) do return mask
% id
624 class VTAndPerfectHashing
625 super VTPerfectHashing
626 init(class_coloring
: ClassColoring) do end
627 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
630 # MParameterType coloring
632 private var class_coloring
: ClassColoring
633 private var coloration_result
: Map[MParameterType, Int] = new HashMap[MParameterType, Int]
635 init(class_coloring
: ClassColoring) do
636 self.class_coloring
= class_coloring
639 fun colorize
: Map[MParameterType, Int] do
640 colorize_core_properties
641 colorize_crown_properties
642 return self.coloration_result
645 # Colorize properties of the core hierarchy
646 private fun colorize_core_properties
do
647 var mclasses
= self.class_coloring
.core
650 for mclass
in mclasses
do
651 var color
= min_color
653 # if the class is root, get the minimal color
654 if self.class_coloring
.parent_elements
(mclass
).length
== 0 then
655 colorize_elements
(self.fts
(mclass
), color
)
657 # check last color used by parents
658 color
= max_color
(color
, self.class_coloring
.parent_elements
(mclass
))
659 # check max color used in conflicts
660 if self.class_coloring
.conflicts_graph
.has_key
(mclass
) then
661 color
= max_color
(color
, self.class_coloring
.conflicts_graph
[mclass
])
664 colorize_elements
(self.fts
(mclass
), color
)
669 # Colorize properties of the crown hierarchy
670 private fun colorize_crown_properties
do
671 for mclass
in self.class_coloring
.crown
do
672 colorize_elements
(self.fts
(mclass
), max_color
(0, self.class_coloring
.parent_elements
(mclass
)))
676 # Colorize a collection of properties given a starting color
677 private fun colorize_elements
(elements
: Collection[MParameterType], start_color
: Int) do
678 for element
in elements
do
679 if self.coloration_result
.has_key
(element
) then continue
680 self.coloration_result
[element
] = start_color
685 private fun max_color
(min_color
: Int, mclasses
: Collection[MClass]): Int do
686 var max_color
= min_color
688 for mclass
in mclasses
do
689 for ft
in self.fts
(mclass
) do
690 var color
= min_color
691 if self.coloration_result
.has_key
(ft
) then
692 color
= self.coloration_result
[ft
]
693 if color
>= max_color
then max_color
= color
+ 1
701 private var fts_cache
: Map[MClass, Set[MParameterType]] = new HashMap[MClass, Set[MParameterType]]
703 private fun fts
(mclass
: MClass): Set[MParameterType] do
704 if not self.fts_cache
.has_key
(mclass
) then
705 var fts
= new HashSet[MParameterType]
706 var mclass_type
= mclass
.mclass_type
707 if mclass_type
isa MGenericType then
708 for ft
in mclass_type
.arguments
do
709 fts
.add
(ft
.as(MParameterType))
712 self.fts_cache
[mclass
] = fts
714 return fts_cache
[mclass
]
717 fun build_ft_tables
: Map[MClass, Array[nullable MParameterType]] do
718 var tables
= new HashMap[MClass, Array[nullable MParameterType]]
720 for mclass
in self.class_coloring
.coloration_result
.keys
do
721 var table
= new Array[nullable MParameterType]
723 # first, fill table from parents
724 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
725 for parent
in parents
do
726 for ft
in self.fts
(parent
) do
727 var color
= self.coloration_result
[ft
]
728 if table
.length
<= color
then
729 for i
in [table
.length
.. color
[ do
737 # then override with local properties
738 for ft
in self.fts
(mclass
) do
739 var color
= self.coloration_result
[ft
]
740 if table
.length
<= color
then
741 for i
in [table
.length
.. color
[ do
747 tables
[mclass
] = table
753 class NaiveFTColoring
756 init(class_coloring
: ClassColoring) do end
758 redef fun colorize
: Map[MParameterType, Int] do
759 var mclasses
= new HashSet[MClass]
760 mclasses
.add_all
(self.class_coloring
.core
)
761 mclasses
.add_all
(self.class_coloring
.crown
)
764 for mclass
in mclasses
do
765 min_color
= max_color
(min_color
, mclasses
)
766 colorize_elements
(self.fts
(mclass
), min_color
)
768 return self.coloration_result
772 abstract class FTPerfectHashing
775 private var masks
: Map[MClass, Int] = new HashMap[MClass, Int]
777 init(class_coloring
: ClassColoring) do end
779 redef fun colorize
: Map[MParameterType, Int] do
780 var mclasses
= new HashSet[MClass]
781 mclasses
.add_all
(self.class_coloring
.core
)
782 mclasses
.add_all
(self.class_coloring
.crown
)
783 for mclass
in mclasses
do
784 for ft
in self.fts
(mclass
) do
785 if coloration_result
.has_key
(ft
) then continue
786 coloration_result
[ft
] = coloration_result
.length
+ 1
789 return self.coloration_result
792 fun compute_masks
: Map[MClass, Int] do
793 var mclasses
= new HashSet[MClass]
794 mclasses
.add_all
(self.class_coloring
.core
)
795 mclasses
.add_all
(self.class_coloring
.crown
)
796 for mclass
in mclasses
do
797 var fts
= new HashSet[MParameterType]
798 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
799 for parent
in parents
do
800 fts
.add_all
(self.fts
(parent
))
802 fts
.add_all
(self.fts
(mclass
))
803 self.masks
[mclass
] = compute_mask
(fts
)
808 private fun compute_mask
(fts
: Set[MParameterType]): Int do
811 var used
= new List[Int]
813 var res
= op
(mask
, self.coloration_result
[ft
])
814 if used
.has
(res
) then
820 if used
.length
== fts
.length
then break
826 redef fun build_ft_tables
do
827 var tables
= new HashMap[MClass, Array[nullable MParameterType]]
829 for mclass
in self.class_coloring
.coloration_result
.keys
do
830 var table
= new Array[nullable MParameterType]
832 # first, fill table from parents
833 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
834 for parent
in parents
do
835 for ft
in self.fts
(parent
) do
836 var color
= phash
(self.coloration_result
[ft
], masks
[mclass
])
837 if table
.length
<= color
then
838 for i
in [table
.length
.. color
[ do
846 # then override with local properties
847 for ft
in self.fts
(mclass
) do
848 var color
= phash
(self.coloration_result
[ft
], masks
[mclass
])
849 if table
.length
<= color
then
850 for i
in [table
.length
.. color
[ do
856 tables
[mclass
] = table
861 private fun op
(mask
: Int, id
:Int): Int is abstract
862 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
865 class FTModPerfectHashing
866 super FTPerfectHashing
867 init(class_coloring
: ClassColoring) do end
868 redef fun op
(mask
, id
) do return mask
% id
871 class FTAndPerfectHashing
872 super FTPerfectHashing
873 init(class_coloring
: ClassColoring) do end
874 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
877 # Live Entries coloring
878 class LiveEntryColoring
880 private var coloration_result
: Map[MType, Int] = new HashMap[MType, Int]
881 private var conflicts_graph_cache
: nullable HashMap[MType, Set[MType]]
882 var livetypes_tables_sizes
: nullable Map[MClass, Array[Int]]
886 fun colorize
(elements
: Collection[MType]): Map[MType, Int] do
888 build_conflicts_graph
(elements
)
891 colorize_elements
(elements
)
893 return coloration_result
897 fun build_livetype_tables
(mtypes
: Set[MType]): Map[MClass, Array[nullable Object]] do
898 var livetypes_tables
= new HashMap[MClass, Array[nullable Object]]
899 self.livetypes_tables_sizes
= new HashMap[MClass, Array[Int]]
901 for mtype
in mtypes
do
902 if mtype
isa MGenericType then
903 var table
: Array[nullable Object]
904 var sizes
: Array[Int]
905 if livetypes_tables
.has_key
(mtype
.mclass
) then
906 table
= livetypes_tables
[mtype
.mclass
]
908 table
= new Array[nullable Object]
909 livetypes_tables
[mtype
.mclass
] = table
911 if livetypes_tables_sizes
.has_key
(mtype
.mclass
) then
912 sizes
= livetypes_tables_sizes
[mtype
.mclass
]
914 sizes
= new Array[Int]
915 livetypes_tables_sizes
[mtype
.mclass
] = sizes
917 build_livetype_table
(mtype
, 0, table
, sizes
)
921 return livetypes_tables
924 # Build live gentype table recursively
925 private fun build_livetype_table
(mtype
: MGenericType, current_rank
: Int, table
: Array[nullable Object], sizes
: Array[Int]) do
926 var ft
= mtype
.arguments
[current_rank
]
927 if not self.coloration_result
.has_key
(ft
) then return
928 var color
= self.coloration_result
[ft
]
930 if current_rank
>= sizes
.length
then
931 sizes
[current_rank
] = color
+ 1
932 else if color
>= sizes
[current_rank
] then
933 sizes
[current_rank
] = color
+ 1
936 if color
> table
.length
then
937 for i
in [table
.length
.. color
[ do table
[i
] = null
940 if current_rank
== mtype
.arguments
.length
- 1 then
943 var ft_table
: Array[nullable Object]
944 if color
< table
.length
and table
[color
] != null then
945 ft_table
= table
[color
].as(Array[nullable Object])
947 ft_table
= new Array[nullable Object]
949 table
[color
] = ft_table
950 build_livetype_table
(mtype
, current_rank
+ 1, ft_table
, sizes
)
954 # Colorize a collection of elements
955 fun colorize_elements
(elements
: Collection[MType]) do
958 for element
in elements
do
959 var color
= min_color
960 while not self.is_color_free
(element
, color
) do
963 coloration_result
[element
] = color
968 # Check if a related element to the element already use the color
969 private fun is_color_free
(element
: MType, color
: Int): Bool do
970 if conflicts_graph
.has_key
(element
) then
971 for st
in conflicts_graph
[element
] do
972 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
978 # look for types in the same generic signatures
979 private fun build_conflicts_graph
(elements
: Collection[MType]) do
980 # regroup types by classes
981 var genclasses
= new HashMap[MClass, Set[MType]]
983 if e
isa MGenericType then
984 if not genclasses
.has_key
(e
.mclass
) then
985 genclasses
[e
.mclass
] = new HashSet[MType]
987 genclasses
[e
.mclass
].add
(e
)
992 self.conflicts_graph_cache
= new HashMap[MType, Set[MType]]
993 for mclass
, mtypes
in genclasses
do
995 for rank
in [0..mclass
.arity
[ do
997 for mtype
in mtypes
do
998 var mclasstype
: MClassType
999 if mtype
isa MNullableType then
1000 mclasstype
= mtype
.mtype
.as(MClassType)
1002 mclasstype
= mtype
.as(MClassType)
1004 var ft
= mclasstype
.arguments
[rank
]
1005 for otype
in mtypes
do
1006 if mtype
== otype
then continue
1007 var oclasstype
: MClassType
1008 if otype
isa MNullableType then
1009 oclasstype
= otype
.mtype
.as(MClassType)
1011 oclasstype
= otype
.as(MClassType)
1013 var oft
= oclasstype
.arguments
[rank
]
1014 self.add_conflict
(ft
, oft
)
1021 private fun add_conflict
(mtype
: MType, otype
: MType) do
1022 if mtype
== otype
then return
1023 if not self.conflicts_graph_cache
.has_key
(mtype
) then self.conflicts_graph_cache
[mtype
] = new HashSet[MType]
1024 self.conflicts_graph_cache
[mtype
].add
(otype
)
1025 if not self.conflicts_graph_cache
.has_key
(otype
) then self.conflicts_graph_cache
[otype
] = new HashSet[MType]
1026 self.conflicts_graph_cache
[otype
].add
(mtype
)
1028 private fun conflicts_graph
: Map[MType, Set[MType]] do return conflicts_graph_cache
.as(not null)
1031 class NaiveLiveEntryColoring
1032 super LiveEntryColoring
1036 redef fun colorize_elements
(elements
: Collection[MType]) do
1038 for element
in elements
do
1039 coloration_result
[element
] = color
1045 # live unanchored coloring
1046 class UnanchoredTypeColoring
1048 private var coloration_result
: Map[MType, Int] = new HashMap[MType, Int]
1049 private var conflicts_graph
: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
1053 fun colorize
(elements
: Map[MClassType, Set[MType]]): Map[MType, Int] do
1054 build_conflicts_graph
(elements
)
1055 colorize_elements
(elements
)
1056 return coloration_result
1059 fun build_tables
(elements
: Map[MClassType, Set[MType]]): Map[MClassType, Array[nullable MType]] do
1060 var tables
= new HashMap[MClassType, Array[nullable MType]]
1062 for mclasstype
, mtypes
in elements
do
1063 var table
= new Array[nullable MType]
1064 for mtype
in mtypes
do
1065 var color
= self.coloration_result
[mtype
]
1066 if table
.length
<= color
then
1067 for i
in [table
.length
.. color
[ do
1071 table
[color
] = mtype
1073 tables
[mclasstype
] = table
1078 # Colorize a collection of elements
1079 fun colorize_elements
(elements
: Map[MClassType, Set[MType]]) do
1081 for mclasstype
, mclasstypes
in elements
do
1082 for element
in mclasstypes
do
1083 if self.coloration_result
.has_key
(element
) then continue
1084 var color
= min_color
1085 while not self.is_color_free
(element
, color
) do
1088 coloration_result
[element
] = color
1094 # Check if a related element to the element already use the color
1095 private fun is_color_free
(element
: MType, color
: Int): Bool do
1096 if conflicts_graph
.has_key
(element
) then
1097 for st
in conflicts_graph
[element
] do
1098 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
1104 # look for unanchored types generated by the same type
1105 private fun build_conflicts_graph
(elements
: Map[MClassType, Set[MType]]) do
1106 for mclasstype
, mtypes
in elements
do
1107 for mtype
in mtypes
do
1108 for otype
in mtypes
do
1109 if otype
== mtype
then continue
1110 self.add_conflict
(mtype
, otype
)
1116 private fun add_conflict
(mtype
: MType, otype
: MType) do
1117 if mtype
== otype
then return
1118 if not self.conflicts_graph
.has_key
(mtype
) then self.conflicts_graph
[mtype
] = new HashSet[MType]
1119 self.conflicts_graph
[mtype
].add
(otype
)
1120 if not self.conflicts_graph
.has_key
(otype
) then self.conflicts_graph
[otype
] = new HashSet[MType]
1121 self.conflicts_graph
[otype
].add
(mtype
)
1125 class NaiveUnanchoredTypeColoring
1126 super UnanchoredTypeColoring
1130 redef fun colorize_elements
(elements
: Map[MClassType, Set[MType]]) do
1132 for mclasstype
, mclasstypes
in elements
do
1133 for element
in mclasstypes
do
1134 coloration_result
[element
] = color
1141 abstract class UnanchoredTypePerfectHashing
1142 super NaiveUnanchoredTypeColoring
1144 private var masks
: Map[MClassType, Int] = new HashMap[MClassType, Int]
1148 redef fun colorize_elements
(elements
: Map[MClassType, Set[MType]]) do
1150 for mclasstype
, mclasstypes
in elements
do
1151 for element
in mclasstypes
do
1152 coloration_result
[element
] = color
1158 fun compute_masks
(elements
: Map[MClassType, Set[MType]]): Map[MClassType, Int] do
1159 for mclasstype
, mtypes
in elements
do
1160 self.masks
[mclasstype
] = compute_mask
(mtypes
)
1165 private fun compute_mask
(mtypes
: Set[MType]): Int do
1168 var used
= new List[Int]
1169 for mtype
in mtypes
do
1170 var res
= op
(mask
, self.coloration_result
[mtype
])
1171 if used
.has
(res
) then
1177 if used
.length
== mtypes
.length
then break
1183 redef fun build_tables
(elements
: Map[MClassType, Set[MType]]): Map[MClassType, Array[nullable MType]] do
1184 var tables
= new HashMap[MClassType, Array[nullable MType]]
1186 for mclasstype
, mtypes
in elements
do
1187 var table
= new Array[nullable MType]
1188 for mtype
in mtypes
do
1189 var color
= phash
(self.coloration_result
[mtype
], masks
[mclasstype
])
1190 if table
.length
<= color
then
1191 for i
in [table
.length
.. color
[ do
1195 table
[color
] = mtype
1197 tables
[mclasstype
] = table
1202 private fun op
(mask
: Int, id
:Int): Int is abstract
1203 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
1206 class UnanchoredTypeModPerfectHashing
1207 super UnanchoredTypePerfectHashing
1209 redef fun op
(mask
, id
) do return mask
% id
1212 class UnanchoredTypeAndPerfectHashing
1213 super UnanchoredTypePerfectHashing
1215 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
1221 redef class HashSet[E
]
1222 init from
(elements
: Collection[E
]) do
1224 self.add_all
(elements
)
1228 redef class Array[E
]
1229 init from
(elements
: Collection[E
]) do
1231 self.add_all
(elements
)
1234 # Return a new Array with the elements only contened in 'self' and not in 'o'
1235 fun -(o
: Array[E
]): Array[E
] do
1236 var res
= new Array[E
]
1237 for e
in self do if not o
.has
(e
) then res
.add
(e
)
1244 # Return a linearization of a set of mtypes
1245 private fun linearize_mtypes
(mtypes
: Set[MType]): Array[MType] do
1246 var lin
= new Array[MType].from
(mtypes
)
1247 var sorter
= new TypeSorter(self)
1252 # Return a reverse linearization of a set of mtypes
1253 private fun reverse_linearize_mtypes
(mtypes
: Set[MType]): Array[MType] do
1254 var lin
= new Array[MType].from
(mtypes
)
1255 var sorter
= new ReverseTypeSorter(self)
1260 # Return super types of a `mtype` in `self`
1261 private fun super_mtypes
(mtype
: MType, mtypes
: Set[MType]): Set[MType] do
1262 if not self.super_mtypes_cache
.has_key
(mtype
) then
1263 var supers
= new HashSet[MType]
1264 for otype
in mtypes
do
1265 if otype
== mtype
then continue
1266 if mtype
.is_subtype
(self, null, otype
) then
1270 self.super_mtypes_cache
[mtype
] = supers
1272 return self.super_mtypes_cache
[mtype
]
1275 private var super_mtypes_cache
: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
1277 # Return all sub mtypes (directs and indirects) of a `mtype` in `self`
1278 private fun sub_mtypes
(mtype
: MType, mtypes
: Set[MType]): Set[MType] do
1279 if not self.sub_mtypes_cache
.has_key
(mtype
) then
1280 var subs
= new HashSet[MType]
1281 for otype
in mtypes
do
1282 if otype
== mtype
then continue
1283 if otype
.is_subtype
(self, null, mtype
) then
1287 self.sub_mtypes_cache
[mtype
] = subs
1289 return self.sub_mtypes_cache
[mtype
]
1292 private var sub_mtypes_cache
: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
1294 # Return a linearization of a set of mclasses
1295 private fun linearize_mclasses
(mclasses
: Set[MClass]): Array[MClass] do
1296 var lin
= new Array[MClass].from
(mclasses
)
1297 var sorter
= new ClassSorter(self)
1302 # Return a reverse linearization of a set of mtypes
1303 private fun reverse_linearize_mclasses
(mclasses
: Set[MClass]): Array[MClass] do
1304 var lin
= new Array[MClass].from
(mclasses
)
1305 var sorter
= new ReverseClassSorter(self)
1310 # Return all super mclasses (directs and indirects) of a `mclass` in `self`
1311 private fun super_mclasses
(mclass
: MClass): Set[MClass] do
1312 if not self.super_mclasses_cache
.has_key
(mclass
) then
1313 var supers
= new HashSet[MClass]
1314 if self.flatten_mclass_hierarchy
.has
(mclass
) then
1315 for sup
in self.flatten_mclass_hierarchy
[mclass
].greaters
do
1316 if sup
== mclass
then continue
1320 self.super_mclasses_cache
[mclass
] = supers
1322 return self.super_mclasses_cache
[mclass
]
1325 private var super_mclasses_cache
: Map[MClass, Set[MClass]] = new HashMap[MClass, Set[MClass]]
1327 # Return all parents of a `mclass` in `self`
1328 private fun parent_mclasses
(mclass
: MClass): Set[MClass] do
1329 if not self.parent_mclasses_cache
.has_key
(mclass
) then
1330 var parents
= new HashSet[MClass]
1331 if self.flatten_mclass_hierarchy
.has
(mclass
) then
1332 for sup
in self.flatten_mclass_hierarchy
[mclass
].direct_greaters
do
1333 if sup
== mclass
then continue
1337 self.parent_mclasses_cache
[mclass
] = parents
1339 return self.parent_mclasses_cache
[mclass
]
1342 private var parent_mclasses_cache
: Map[MClass, Set[MClass]] = new HashMap[MClass, Set[MClass]]
1344 # Return all sub mclasses (directs and indirects) of a `mclass` in `self`
1345 private fun sub_mclasses
(mclass
: MClass): Set[MClass] do
1346 if not self.sub_mclasses_cache
.has_key
(mclass
) then
1347 var subs
= new HashSet[MClass]
1348 if self.flatten_mclass_hierarchy
.has
(mclass
) then
1349 for sub
in self.flatten_mclass_hierarchy
[mclass
].smallers
do
1350 if sub
== mclass
then continue
1354 self.sub_mclasses_cache
[mclass
] = subs
1356 return self.sub_mclasses_cache
[mclass
]
1359 private var sub_mclasses_cache
: Map[MClass, Set[MClass]] = new HashMap[MClass, Set[MClass]]
1361 # All 'mproperties' associated to all 'mclassdefs' of `mclass`
1362 private fun properties
(mclass
: MClass): Set[MProperty] do
1363 if not self.properties_cache
.has_key
(mclass
) then
1364 var properties
= new HashSet[MProperty]
1365 var parents
= self.super_mclasses
(mclass
)
1366 for parent
in parents
do
1367 properties
.add_all
(self.properties
(parent
))
1370 for mclassdef
in mclass
.mclassdefs
do
1371 for mpropdef
in mclassdef
.mpropdefs
do
1372 properties
.add
(mpropdef
.mproperty
)
1375 self.properties_cache
[mclass
] = properties
1377 return properties_cache
[mclass
]
1380 private var properties_cache
: Map[MClass, Set[MProperty]] = new HashMap[MClass, Set[MProperty]]
1383 # A sorter for linearize list of types
1385 super AbstractSorter[MType]
1387 private var mmodule
: MModule
1389 init(mmodule
: MModule) do self.mmodule
= mmodule
1391 redef fun compare
(a
, b
) do
1394 else if a
.is_subtype
(self.mmodule
, null, b
) then
1401 # A sorter for reverse linearization
1402 class ReverseTypeSorter
1405 init(mmodule
: MModule) do end
1407 redef fun compare
(a
, b
) do
1410 else if a
.is_subtype
(self.mmodule
, null, b
) then
1417 # A sorter for linearize list of classes
1418 private class ClassSorter
1419 super AbstractSorter[MClass]
1421 var mmodule
: MModule
1423 redef fun compare
(a
, b
) do
1426 else if self.mmodule
.flatten_mclass_hierarchy
.has
(a
) and self.mmodule
.flatten_mclass_hierarchy
[a
].greaters
.has
(b
) then
1433 # A sorter for reverse linearization
1434 private class ReverseClassSorter
1435 super AbstractSorter[MClass]
1437 var mmodule
: MModule
1439 redef fun compare
(a
, b
) do
1442 else if self.mmodule
.flatten_mclass_hierarchy
.has
(a
) and self.mmodule
.flatten_mclass_hierarchy
[a
].greaters
.has
(b
) then