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
21 private var mmodule
: MModule
22 init(mmodule
: MModule) do self.mmodule
= mmodule
24 # Compute mtypes ids and position
25 fun build_layout
(mtypes
: Set[MType]): TypeLayout is abstract
27 # Give each MType a unic id using a descending linearization of the `mtypes` set
28 private fun compute_ids
(mtypes
: Set[MType]): Map[MType, Int] do
29 var ids
= new HashMap[MType, Int]
30 var lin
= self.mmodule
.reverse_linearize_mtypes
(mtypes
)
32 ids
[mtype
] = ids
.length
39 # Unic ids or each Mtype
40 var ids
: Map[MType, Int] = new HashMap[MType, Int]
41 # Fixed positions of each MType in all tables
42 var pos
: Map[MType, Int] = new HashMap[MType, Int]
45 # Layout builder for MType using Binary Matrix (BM)
46 class BMTypeLayoutBuilder
47 super TypeLayoutBuilder
49 init(mmodule
: MModule) do super
51 # Compute mtypes ids and position using BM
52 redef fun build_layout
(mtypes
: Set[MType]): TypeLayout do
53 var result
= new TypeLayout
54 result
.ids
= self.compute_ids
(mtypes
)
55 result
.pos
= result
.ids
60 # Layout builder for MType using Coloring (CL)
61 class CLTypeLayoutBuilder
62 super TypeLayoutBuilder
64 private var colorer
: MTypeColorer
66 init(mmodule
: MModule) do
68 self.colorer
= new MTypeColorer(mmodule
)
71 # Compute mtypes ids and position using BM
72 redef fun build_layout
(mtypes
: Set[MType]): TypeLayout do
73 var result
= new TypeLayout
74 result
.ids
= self.compute_ids
(mtypes
)
75 result
.pos
= self.colorer
.colorize
(mtypes
)
80 abstract class AbstractColoring[E
: Object]
82 private var core
: Set[E
] = new HashSet[E
]
83 private var crown
: Set[E
] = new HashSet[E
]
84 private var border
: Set[E
] = new HashSet[E
]
86 private var coloration_result
: Map[E
, Int] = new HashMap[E
, Int]
90 fun colorize
(elements
: Set[E
]): Map[E
, Int] do
91 tag_elements
(elements
)
92 build_conflicts_graph
(elements
)
93 colorize_elements
(core
)
94 colorize_elements
(border
)
95 colorize_elements
(crown
)
96 return coloration_result
99 # Colorize a collection of elements
100 private fun colorize_elements
(elements
: Set[E
]) do
103 var lin
= reverse_linearize
(elements
)
104 for element
in lin
do
105 var color
= min_color
106 while not self.is_color_free
(element
, elements
, color
) do
109 coloration_result
[element
] = color
114 # Check if a related element to the element already use the color
115 private fun is_color_free
(element
: E
, elements
: Set[E
], color
: Int): Bool do
116 if conflicts_graph
.has_key
(element
) then
117 for st
in conflicts_graph
[element
] do
118 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
121 for st
in self.super_elements
(element
, elements
) do
122 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
127 # Tag elements as core, crown or border
128 private fun tag_elements
(elements
: Set[E
]) do
129 for element
in elements
do
130 # Check if sub elements are all in single inheritance
131 var all_subelements_si
= true
132 for subelem
in self.sub_elements
(element
, elements
) do
133 if self.is_element_mi
(subelem
, elements
) then
134 all_subelements_si
= false
139 # Tag as core, crown or border
140 if self.is_element_mi
(element
, elements
) then
141 core
.add_all
(self.super_elements
(element
, elements
))
143 if all_subelements_si
then
146 else if not all_subelements_si
then
147 core
.add_all
(self.super_elements
(element
, elements
))
155 # Conflicts graph of elements hierarchy (two types are in conflict if they have common subelements)
156 private fun build_conflicts_graph
(elements
: Set[E
]) do
157 self.conflicts_graph
= new HashMap[E
, HashSet[E
]]
158 var core
= reverse_linearize
(self.core
)
160 for i
in self.linear_extension
(t
, elements
) do
161 if t
== i
then continue
163 var lin_i
= self.linear_extension
(i
, elements
)
165 for j
in self.linear_extension
(t
, elements
) do
166 if i
== j
or j
== t
then continue
167 var lin_j
= self.linear_extension
(j
, elements
)
169 var d_ij
= lin_i
- lin_j
170 var d_ji
= lin_j
- lin_i
173 if not conflicts_graph
.has_key
(ed1
) then conflicts_graph
[ed1
] = new HashSet[E
]
174 # add ed1 x ed2 to conflicts graph
175 for ed2
in d_ji
do conflicts_graph
[ed1
].add
(ed2
)
178 if not conflicts_graph
.has_key
(ed1
) then conflicts_graph
[ed1
] = new HashSet[E
]
179 # add ed1 x ed2 to conflicts graph
180 for ed2
in d_ji
do conflicts_graph
[ed1
].add
(ed2
)
187 private var conflicts_graph
: nullable HashMap[E
, Set[E
]]
189 # cache for linear_extensions
190 private var linear_extensions_cache
: Map[E
, Array[E
]] = new HashMap[E
, Array[E
]]
192 # Return a linear_extension of super_elements of the element
193 private fun linear_extension
(element
: E
, elements
: Set[E
]): Array[E
] do
194 if not self.linear_extensions_cache
.has_key
(element
) then
195 var supers
= new HashSet[E
]
197 supers
.add_all
(self.super_elements
(element
, elements
))
198 self.linear_extensions_cache
[element
] = self.linearize
(supers
)
200 return self.linear_extensions_cache
[element
]
203 private fun super_elements
(element
: E
, elements
: Set[E
]): Set[E
] is abstract
204 private fun sub_elements
(element
: E
, elements
: Set[E
]): Set[E
] is abstract
205 private fun is_element_mi
(element
: E
, elements
: Set[E
]): Bool is abstract
206 private fun linearize
(elements
: Set[E
]): Array[E
] is abstract
207 private fun reverse_linearize
(elements
: Set[E
]): Array[E
] is abstract
211 private class MTypeColorer
212 super AbstractColoring[MType]
218 init(mmodule
: MModule) do self.mmodule
= mmodule
220 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mtypes
(element
, elements
)
221 redef fun is_element_mi
(element
, elements
) do return self.super_elements
(element
, elements
).length
> 1
222 redef fun sub_elements
(element
, elements
) do do return self.mmodule
.sub_mtypes
(element
, elements
)
223 redef fun linearize
(elements
) do return self.mmodule
.linearize_mtypes
(elements
)
224 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mtypes
(elements
)
227 abstract class TypePerfectHashing
228 super TypeLayoutBuilder
229 super AbstractColoring[MType]
233 init(mmodule
: MModule) do self.mmodule
= mmodule
235 fun compute_masks
(elements
: Set[T
], ids
: Map[T
, Int]): Map[T
, Int] do
237 # Create super type list
238 var supers
= new HashSet[T
]
239 supers
.add_all
(self.super_elements
(e
, elements
))
241 # Compute the hashing 'mask'
242 self.coloration_result
[e
] = compute_mask
(supers
, ids
)
244 return self.coloration_result
247 private fun compute_mask
(mtypes
: Set[T
], ids
: Map[T
, Int]): Int do
250 var used
= new List[Int]
252 var res
= op
(mask
, ids
[sup
])
253 if used
.has
(res
) then
259 if used
.length
== mtypes
.length
then break
265 private fun op
(mask
: Int, id
:Int): Int is abstract
266 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
268 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mtypes
(element
, elements
)
269 redef fun is_element_mi
(element
, elements
) do return self.super_elements
(element
, elements
).length
> 1
270 redef fun sub_elements
(element
, elements
) do do return self.mmodule
.sub_mtypes
(element
, elements
)
271 redef fun linearize
(elements
) do return self.mmodule
.linearize_mtypes
(elements
)
272 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mtypes
(elements
)
275 class TypeModPerfectHashing
276 super TypePerfectHashing
277 init(mainmodule
: MModule) do super
278 redef fun op
(mask
, id
) do return mask
% id
281 class TypeAndPerfectHashing
282 super TypePerfectHashing
283 init(mainmodule
: MModule) do super
284 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
289 super AbstractColoring[MClass]
293 private var mmodule
: MModule
296 private var super_elements_cache
: Map[T
, Set[T
]] = new HashMap[T
, Set[T
]]
297 private var parent_elements_cache
: Map[T
, Set[T
]] = new HashMap[T
, Set[T
]]
298 private var sub_elements_cache
: Map[T
, Set[T
]] = new HashMap[T
, Set[T
]]
300 init(mainmodule
: MModule) do self.mmodule
= mainmodule
302 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mclasses
(element
)
303 fun parent_elements
(element
: MClass): Set[MClass] do return self.mmodule
.parent_mclasses
(element
)
304 redef fun is_element_mi
(element
, elements
) do return self.parent_elements
(element
).length
> 1
305 redef fun sub_elements
(element
, elements
) do do return self.mmodule
.sub_mclasses
(element
)
306 redef fun linearize
(elements
) do return self.mmodule
.linearize_mclasses
(elements
)
307 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mclasses
(elements
)
310 # incremental coloring (very naive)
311 class NaiveClassColoring
314 init(mainmodule
: MModule) do
318 # naive coloring that use incremental coloring
319 redef fun colorize_elements
(elements
) do
321 self.coloration_result
[e
] = self.coloration_result
.length
326 abstract class ClassPerfectHashing
329 init(mainmodule
: MModule) do
333 fun compute_masks
(elements
: Set[T
], ids
: Map[T
, Int]): Map[T
, Int] do
335 # Create super type list
336 var supers
= new HashSet[T
]
337 supers
.add_all
(self.super_elements
(e
, elements
))
339 # Compute the hashing 'mask'
340 self.coloration_result
[e
] = compute_mask
(supers
, ids
)
342 return self.coloration_result
345 private fun compute_mask
(mtypes
: Set[T
], ids
: Map[T
, Int]): Int do
348 var used
= new List[Int]
350 var res
= op
(mask
, ids
[sup
])
351 if used
.has
(res
) then
357 if used
.length
== mtypes
.length
then break
363 private fun op
(mask
: Int, id
:Int): Int is abstract
364 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
367 class ClassModPerfectHashing
368 super ClassPerfectHashing
369 init(mainmodule
: MModule) do
372 redef fun op
(mask
, id
) do return mask
% id
375 class ClassAndPerfectHashing
376 super ClassPerfectHashing
377 init(mainmodule
: MModule) do
380 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
384 class PropertyColoring
386 type MPROP: MProperty
387 type MPROPDEF: MPropDef
389 private var class_coloring
: ClassColoring
390 private var coloration_result
: Map[MPROP, Int] = new HashMap[MPROP, Int]
392 init(class_coloring
: ClassColoring) do
393 self.class_coloring
= class_coloring
396 fun colorize
: Map[MPROP, Int] do
397 colorize_core_properties
398 colorize_crown_properties
399 return self.coloration_result
402 fun build_property_tables
: Map[MClass, Array[nullable MPROPDEF]] do
403 var tables
= new HashMap[MClass, Array[nullable MPROPDEF]]
404 var mclasses
= self.class_coloring
.coloration_result
.keys
405 for mclass
in mclasses
do
406 var table
= new Array[nullable MPROPDEF]
407 # first, fill table from parents by reverse linearization order
408 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
409 var lin
= self.class_coloring
.reverse_linearize
(parents
)
411 for mproperty
in self.properties
(parent
) do
412 var color
= self.coloration_result
[mproperty
]
413 if table
.length
<= color
then
414 for i
in [table
.length
.. color
[ do
418 for mpropdef
in mproperty
.mpropdefs
do
419 if mpropdef
.mclassdef
.mclass
== parent
then
420 table
[color
] = mpropdef
426 # then override with local properties
427 for mproperty
in self.properties
(mclass
) do
428 var color
= self.coloration_result
[mproperty
]
429 if table
.length
<= color
then
430 for i
in [table
.length
.. color
[ do
434 for mpropdef
in mproperty
.mpropdefs
do
435 if mpropdef
.mclassdef
.mclass
== mclass
then
436 table
[color
] = mpropdef
440 tables
[mclass
] = table
445 # Colorize properties of the core hierarchy
446 private fun colorize_core_properties
do
447 var mclasses
= self.class_coloring
.core
450 for mclass
in mclasses
do
451 var color
= min_color
453 # if the class is root, get the minimal color
454 if self.class_coloring
.parent_elements
(mclass
).length
== 0 then
455 colorize_elements
(self.properties
(mclass
), color
)
457 # check last color used by parents
458 color
= max_color
(color
, self.class_coloring
.parent_elements
(mclass
))
459 # check max color used in conflicts
460 if self.class_coloring
.conflicts_graph
.has_key
(mclass
) then
461 color
= max_color
(color
, self.class_coloring
.conflicts_graph
[mclass
])
465 colorize_elements
(self.properties
(mclass
), color
)
470 # Colorize properties of the crown hierarchy
471 private fun colorize_crown_properties
do
472 for mclass
in self.class_coloring
.crown
do
473 colorize_elements
(self.properties
(mclass
), max_color
(0, self.class_coloring
.parent_elements
(mclass
)))
477 # Colorize a collection of properties given a starting color
478 private fun colorize_elements
(elements
: Collection[MPROP], start_color
: Int) do
479 for element
in elements
do
480 if self.coloration_result
.has_key
(element
) then continue
481 self.coloration_result
[element
] = start_color
486 private fun max_color
(min_color
: Int, mclasses
: Collection[MClass]): Int do
487 var max_color
= min_color
489 for mclass
in mclasses
do
490 for mproperty
in self.properties
(mclass
) do
491 var color
= min_color
492 if self.coloration_result
.has_key
(mproperty
) then
493 color
= self.coloration_result
[mproperty
]
494 if color
>= max_color
then max_color
= color
+ 1
502 private var properties_cache
: Map[MClass, Set[MPROP]] = new HashMap[MClass, Set[MPROP]]
504 # All 'mproperties' associated to all 'mclassdefs' of the class
505 private fun properties
(mclass
: MClass): Set[MPROP] do
506 if not self.properties_cache
.has_key
(mclass
) then
507 var properties
= new HashSet[MPROP]
508 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
509 for parent
in parents
do
510 properties
.add_all
(self.properties
(parent
))
513 for mclassdef
in mclass
.mclassdefs
do
514 for mpropdef
in mclassdef
.mpropdefs
do
515 var mproperty
= mpropdef
.mproperty
516 if mproperty
isa MPROP then
517 properties
.add
(mproperty
)
521 self.properties_cache
[mclass
] = properties
523 return properties_cache
[mclass
]
529 super PropertyColoring
531 redef type MPROP: MMethod
532 redef type MPROPDEF: MMethodDef
533 init(class_coloring
: ClassColoring) do end
536 # MAttribute coloring
537 class AttributeColoring
538 super PropertyColoring
540 redef type MPROP: MAttribute
541 redef type MPROPDEF: MAttributeDef
542 init(class_coloring
: ClassColoring) do end
545 # MVirtualTypeProp coloring
547 super PropertyColoring
549 redef type MPROP: MVirtualTypeProp
550 redef type MPROPDEF: MVirtualTypeDef
551 init(class_coloring
: ClassColoring) do end
554 class NaiveVTColoring
557 init(class_coloring
: ClassColoring) do end
559 redef fun colorize
: Map[MPROP, Int] do
560 var mclasses
= new HashSet[MClass]
561 mclasses
.add_all
(self.class_coloring
.core
)
562 mclasses
.add_all
(self.class_coloring
.crown
)
565 for mclass
in mclasses
do
566 min_color
= max_color
(min_color
, mclasses
)
567 colorize_elements
(self.properties
(mclass
), min_color
)
569 return self.coloration_result
573 abstract class VTPerfectHashing
576 private var masks
: Map[MClass, Int] = new HashMap[MClass, Int]
578 init(class_coloring
: ClassColoring) do end
580 redef fun colorize
: Map[MPROP, Int] do
581 var mclasses
= new HashSet[MClass]
582 mclasses
.add_all
(self.class_coloring
.core
)
583 mclasses
.add_all
(self.class_coloring
.crown
)
584 for mclass
in mclasses
do
585 var vts
= self.properties
(mclass
)
587 if coloration_result
.has_key
(vt
) then continue
588 coloration_result
[vt
] = coloration_result
.length
+ 1
591 return self.coloration_result
594 fun compute_masks
: Map[MClass, Int] do
595 var mclasses
= new HashSet[MClass]
596 mclasses
.add_all
(self.class_coloring
.core
)
597 mclasses
.add_all
(self.class_coloring
.crown
)
598 for mclass
in mclasses
do
599 self.masks
[mclass
] = compute_mask
(self.properties
(mclass
))
604 private fun compute_mask
(vts
: Set[MPROP]): Int do
607 var used
= new List[Int]
609 var res
= op
(mask
, self.coloration_result
[vt
])
610 if used
.has
(res
) then
616 if used
.length
== vts
.length
then break
622 redef fun build_property_tables
do
623 var tables
= new HashMap[MClass, Array[nullable MPROPDEF]]
625 for mclass
in self.class_coloring
.coloration_result
.keys
do
626 var table
= new Array[nullable MPROPDEF]
627 # first, fill table from parents by reverse linearization order
628 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
629 var lin
= self.class_coloring
.reverse_linearize
(parents
)
631 for mproperty
in self.properties
(parent
) do
632 var color
= phash
(self.coloration_result
[mproperty
], masks
[mclass
])
633 if table
.length
<= color
then
634 for i
in [table
.length
.. color
[ do
638 for mpropdef
in mproperty
.mpropdefs
do
639 if mpropdef
.mclassdef
.mclass
== parent
then
640 table
[color
] = mpropdef
646 # then override with local properties
647 for mproperty
in self.properties
(mclass
) do
648 var color
= phash
(self.coloration_result
[mproperty
], masks
[mclass
])
649 if table
.length
<= color
then
650 for i
in [table
.length
.. color
[ do
654 for mpropdef
in mproperty
.mpropdefs
do
655 if mpropdef
.mclassdef
.mclass
== mclass
then
656 table
[color
] = mpropdef
660 tables
[mclass
] = table
665 private fun op
(mask
: Int, id
:Int): Int is abstract
666 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
670 class VTModPerfectHashing
671 super VTPerfectHashing
672 init(class_coloring
: ClassColoring) do end
673 redef fun op
(mask
, id
) do return mask
% id
676 class VTAndPerfectHashing
677 super VTPerfectHashing
678 init(class_coloring
: ClassColoring) do end
679 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
682 # MParameterType coloring
684 private var class_coloring
: ClassColoring
685 private var coloration_result
: Map[MParameterType, Int] = new HashMap[MParameterType, Int]
687 init(class_coloring
: ClassColoring) do
688 self.class_coloring
= class_coloring
691 fun colorize
: Map[MParameterType, Int] do
692 colorize_core_properties
693 colorize_crown_properties
694 return self.coloration_result
697 # Colorize properties of the core hierarchy
698 private fun colorize_core_properties
do
699 var mclasses
= self.class_coloring
.core
702 for mclass
in mclasses
do
703 var color
= min_color
705 # if the class is root, get the minimal color
706 if self.class_coloring
.parent_elements
(mclass
).length
== 0 then
707 colorize_elements
(self.fts
(mclass
), color
)
709 # check last color used by parents
710 color
= max_color
(color
, self.class_coloring
.parent_elements
(mclass
))
711 # check max color used in conflicts
712 if self.class_coloring
.conflicts_graph
.has_key
(mclass
) then
713 color
= max_color
(color
, self.class_coloring
.conflicts_graph
[mclass
])
716 colorize_elements
(self.fts
(mclass
), color
)
721 # Colorize properties of the crown hierarchy
722 private fun colorize_crown_properties
do
723 for mclass
in self.class_coloring
.crown
do
724 colorize_elements
(self.fts
(mclass
), max_color
(0, self.class_coloring
.parent_elements
(mclass
)))
728 # Colorize a collection of properties given a starting color
729 private fun colorize_elements
(elements
: Collection[MParameterType], start_color
: Int) do
730 for element
in elements
do
731 if self.coloration_result
.has_key
(element
) then continue
732 self.coloration_result
[element
] = start_color
737 private fun max_color
(min_color
: Int, mclasses
: Collection[MClass]): Int do
738 var max_color
= min_color
740 for mclass
in mclasses
do
741 for ft
in self.fts
(mclass
) do
742 var color
= min_color
743 if self.coloration_result
.has_key
(ft
) then
744 color
= self.coloration_result
[ft
]
745 if color
>= max_color
then max_color
= color
+ 1
753 private var fts_cache
: Map[MClass, Set[MParameterType]] = new HashMap[MClass, Set[MParameterType]]
755 private fun fts
(mclass
: MClass): Set[MParameterType] do
756 if not self.fts_cache
.has_key
(mclass
) then
757 var fts
= new HashSet[MParameterType]
758 var mclass_type
= mclass
.mclass_type
759 if mclass_type
isa MGenericType then
760 for ft
in mclass_type
.arguments
do
761 fts
.add
(ft
.as(MParameterType))
764 self.fts_cache
[mclass
] = fts
766 return fts_cache
[mclass
]
769 fun build_ft_tables
: Map[MClass, Array[nullable MParameterType]] do
770 var tables
= new HashMap[MClass, Array[nullable MParameterType]]
772 for mclass
in self.class_coloring
.coloration_result
.keys
do
773 var table
= new Array[nullable MParameterType]
775 # first, fill table from parents
776 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
777 for parent
in parents
do
778 for ft
in self.fts
(parent
) do
779 var color
= self.coloration_result
[ft
]
780 if table
.length
<= color
then
781 for i
in [table
.length
.. color
[ do
789 # then override with local properties
790 for ft
in self.fts
(mclass
) do
791 var color
= self.coloration_result
[ft
]
792 if table
.length
<= color
then
793 for i
in [table
.length
.. color
[ do
799 tables
[mclass
] = table
805 class NaiveFTColoring
808 init(class_coloring
: ClassColoring) do end
810 redef fun colorize
: Map[MParameterType, Int] do
811 var mclasses
= new HashSet[MClass]
812 mclasses
.add_all
(self.class_coloring
.core
)
813 mclasses
.add_all
(self.class_coloring
.crown
)
816 for mclass
in mclasses
do
817 min_color
= max_color
(min_color
, mclasses
)
818 colorize_elements
(self.fts
(mclass
), min_color
)
820 return self.coloration_result
824 abstract class FTPerfectHashing
827 private var masks
: Map[MClass, Int] = new HashMap[MClass, Int]
829 init(class_coloring
: ClassColoring) do end
831 redef fun colorize
: Map[MParameterType, Int] do
832 var mclasses
= new HashSet[MClass]
833 mclasses
.add_all
(self.class_coloring
.core
)
834 mclasses
.add_all
(self.class_coloring
.crown
)
835 for mclass
in mclasses
do
836 for ft
in self.fts
(mclass
) do
837 if coloration_result
.has_key
(ft
) then continue
838 coloration_result
[ft
] = coloration_result
.length
+ 1
841 return self.coloration_result
844 fun compute_masks
: Map[MClass, Int] do
845 var mclasses
= new HashSet[MClass]
846 mclasses
.add_all
(self.class_coloring
.core
)
847 mclasses
.add_all
(self.class_coloring
.crown
)
848 for mclass
in mclasses
do
849 var fts
= new HashSet[MParameterType]
850 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
851 for parent
in parents
do
852 fts
.add_all
(self.fts
(parent
))
854 fts
.add_all
(self.fts
(mclass
))
855 self.masks
[mclass
] = compute_mask
(fts
)
860 private fun compute_mask
(fts
: Set[MParameterType]): Int do
863 var used
= new List[Int]
865 var res
= op
(mask
, self.coloration_result
[ft
])
866 if used
.has
(res
) then
872 if used
.length
== fts
.length
then break
878 redef fun build_ft_tables
do
879 var tables
= new HashMap[MClass, Array[nullable MParameterType]]
881 for mclass
in self.class_coloring
.coloration_result
.keys
do
882 var table
= new Array[nullable MParameterType]
884 # first, fill table from parents
885 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
886 for parent
in parents
do
887 for ft
in self.fts
(parent
) do
888 var color
= phash
(self.coloration_result
[ft
], masks
[mclass
])
889 if table
.length
<= color
then
890 for i
in [table
.length
.. color
[ do
898 # then override with local properties
899 for ft
in self.fts
(mclass
) do
900 var color
= phash
(self.coloration_result
[ft
], masks
[mclass
])
901 if table
.length
<= color
then
902 for i
in [table
.length
.. color
[ do
908 tables
[mclass
] = table
913 private fun op
(mask
: Int, id
:Int): Int is abstract
914 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
917 class FTModPerfectHashing
918 super FTPerfectHashing
919 init(class_coloring
: ClassColoring) do end
920 redef fun op
(mask
, id
) do return mask
% id
923 class FTAndPerfectHashing
924 super FTPerfectHashing
925 init(class_coloring
: ClassColoring) do end
926 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
929 # Live Entries coloring
930 class LiveEntryColoring
932 private var coloration_result
: Map[MType, Int] = new HashMap[MType, Int]
933 private var conflicts_graph_cache
: nullable HashMap[MType, Set[MType]]
934 var livetypes_tables_sizes
: nullable Map[MClass, Array[Int]]
938 fun colorize
(elements
: Collection[MType]): Map[MType, Int] do
940 build_conflicts_graph
(elements
)
943 colorize_elements
(elements
)
945 return coloration_result
949 fun build_livetype_tables
(mtypes
: Set[MType]): Map[MClass, Array[nullable Object]] do
950 var livetypes_tables
= new HashMap[MClass, Array[nullable Object]]
951 self.livetypes_tables_sizes
= new HashMap[MClass, Array[Int]]
953 for mtype
in mtypes
do
954 if mtype
isa MGenericType then
955 var table
: Array[nullable Object]
956 var sizes
: Array[Int]
957 if livetypes_tables
.has_key
(mtype
.mclass
) then
958 table
= livetypes_tables
[mtype
.mclass
]
960 table
= new Array[nullable Object]
961 livetypes_tables
[mtype
.mclass
] = table
963 if livetypes_tables_sizes
.has_key
(mtype
.mclass
) then
964 sizes
= livetypes_tables_sizes
[mtype
.mclass
]
966 sizes
= new Array[Int]
967 livetypes_tables_sizes
[mtype
.mclass
] = sizes
969 build_livetype_table
(mtype
, 0, table
, sizes
)
973 return livetypes_tables
976 # Build live gentype table recursively
977 private fun build_livetype_table
(mtype
: MGenericType, current_rank
: Int, table
: Array[nullable Object], sizes
: Array[Int]) do
978 var ft
= mtype
.arguments
[current_rank
]
979 if not self.coloration_result
.has_key
(ft
) then return
980 var color
= self.coloration_result
[ft
]
982 if current_rank
>= sizes
.length
then
983 sizes
[current_rank
] = color
+ 1
984 else if color
>= sizes
[current_rank
] then
985 sizes
[current_rank
] = color
+ 1
988 if color
> table
.length
then
989 for i
in [table
.length
.. color
[ do table
[i
] = null
992 if current_rank
== mtype
.arguments
.length
- 1 then
995 var ft_table
: Array[nullable Object]
996 if color
< table
.length
and table
[color
] != null then
997 ft_table
= table
[color
].as(Array[nullable Object])
999 ft_table
= new Array[nullable Object]
1001 table
[color
] = ft_table
1002 build_livetype_table
(mtype
, current_rank
+ 1, ft_table
, sizes
)
1006 # Colorize a collection of elements
1007 fun colorize_elements
(elements
: Collection[MType]) do
1010 for element
in elements
do
1011 var color
= min_color
1012 while not self.is_color_free
(element
, color
) do
1015 coloration_result
[element
] = color
1020 # Check if a related element to the element already use the color
1021 private fun is_color_free
(element
: MType, color
: Int): Bool do
1022 if conflicts_graph
.has_key
(element
) then
1023 for st
in conflicts_graph
[element
] do
1024 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
1030 # look for types in the same generic signatures
1031 private fun build_conflicts_graph
(elements
: Collection[MType]) do
1032 # regroup types by classes
1033 var genclasses
= new HashMap[MClass, Set[MType]]
1034 for e
in elements
do
1035 if e
isa MGenericType then
1036 if not genclasses
.has_key
(e
.mclass
) then
1037 genclasses
[e
.mclass
] = new HashSet[MType]
1039 genclasses
[e
.mclass
].add
(e
)
1044 self.conflicts_graph_cache
= new HashMap[MType, Set[MType]]
1045 for mclass
, mtypes
in genclasses
do
1047 for rank
in [0..mclass
.arity
[ do
1048 # for each live type
1049 for mtype
in mtypes
do
1050 var mclasstype
: MClassType
1051 if mtype
isa MNullableType then
1052 mclasstype
= mtype
.mtype
.as(MClassType)
1054 mclasstype
= mtype
.as(MClassType)
1056 var ft
= mclasstype
.arguments
[rank
]
1057 for otype
in mtypes
do
1058 if mtype
== otype
then continue
1059 var oclasstype
: MClassType
1060 if otype
isa MNullableType then
1061 oclasstype
= otype
.mtype
.as(MClassType)
1063 oclasstype
= otype
.as(MClassType)
1065 var oft
= oclasstype
.arguments
[rank
]
1066 self.add_conflict
(ft
, oft
)
1073 private fun add_conflict
(mtype
: MType, otype
: MType) do
1074 if mtype
== otype
then return
1075 if not self.conflicts_graph_cache
.has_key
(mtype
) then self.conflicts_graph_cache
[mtype
] = new HashSet[MType]
1076 self.conflicts_graph_cache
[mtype
].add
(otype
)
1077 if not self.conflicts_graph_cache
.has_key
(otype
) then self.conflicts_graph_cache
[otype
] = new HashSet[MType]
1078 self.conflicts_graph_cache
[otype
].add
(mtype
)
1080 private fun conflicts_graph
: Map[MType, Set[MType]] do return conflicts_graph_cache
.as(not null)
1083 class NaiveLiveEntryColoring
1084 super LiveEntryColoring
1088 redef fun colorize_elements
(elements
: Collection[MType]) do
1090 for element
in elements
do
1091 coloration_result
[element
] = color
1097 # live unanchored coloring
1098 class UnanchoredTypeColoring
1100 private var coloration_result
: Map[MType, Int] = new HashMap[MType, Int]
1101 private var conflicts_graph
: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
1105 fun colorize
(elements
: Map[MClassType, Set[MType]]): Map[MType, Int] do
1106 build_conflicts_graph
(elements
)
1107 colorize_elements
(elements
)
1108 return coloration_result
1111 fun build_tables
(elements
: Map[MClassType, Set[MType]]): Map[MClassType, Array[nullable MType]] do
1112 var tables
= new HashMap[MClassType, Array[nullable MType]]
1114 for mclasstype
, mtypes
in elements
do
1115 var table
= new Array[nullable MType]
1116 for mtype
in mtypes
do
1117 var color
= self.coloration_result
[mtype
]
1118 if table
.length
<= color
then
1119 for i
in [table
.length
.. color
[ do
1123 table
[color
] = mtype
1125 tables
[mclasstype
] = table
1130 # Colorize a collection of elements
1131 fun colorize_elements
(elements
: Map[MClassType, Set[MType]]) do
1133 for mclasstype
, mclasstypes
in elements
do
1134 for element
in mclasstypes
do
1135 if self.coloration_result
.has_key
(element
) then continue
1136 var color
= min_color
1137 while not self.is_color_free
(element
, color
) do
1140 coloration_result
[element
] = color
1146 # Check if a related element to the element already use the color
1147 private fun is_color_free
(element
: MType, color
: Int): Bool do
1148 if conflicts_graph
.has_key
(element
) then
1149 for st
in conflicts_graph
[element
] do
1150 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
1156 # look for unanchored types generated by the same type
1157 private fun build_conflicts_graph
(elements
: Map[MClassType, Set[MType]]) do
1158 for mclasstype
, mtypes
in elements
do
1159 for mtype
in mtypes
do
1160 for otype
in mtypes
do
1161 if otype
== mtype
then continue
1162 self.add_conflict
(mtype
, otype
)
1168 private fun add_conflict
(mtype
: MType, otype
: MType) do
1169 if mtype
== otype
then return
1170 if not self.conflicts_graph
.has_key
(mtype
) then self.conflicts_graph
[mtype
] = new HashSet[MType]
1171 self.conflicts_graph
[mtype
].add
(otype
)
1172 if not self.conflicts_graph
.has_key
(otype
) then self.conflicts_graph
[otype
] = new HashSet[MType]
1173 self.conflicts_graph
[otype
].add
(mtype
)
1177 class NaiveUnanchoredTypeColoring
1178 super UnanchoredTypeColoring
1182 redef fun colorize_elements
(elements
: Map[MClassType, Set[MType]]) do
1184 for mclasstype
, mclasstypes
in elements
do
1185 for element
in mclasstypes
do
1186 coloration_result
[element
] = color
1193 abstract class UnanchoredTypePerfectHashing
1194 super NaiveUnanchoredTypeColoring
1196 private var masks
: Map[MClassType, Int] = new HashMap[MClassType, Int]
1200 redef fun colorize_elements
(elements
: Map[MClassType, Set[MType]]) do
1202 for mclasstype
, mclasstypes
in elements
do
1203 for element
in mclasstypes
do
1204 coloration_result
[element
] = color
1210 fun compute_masks
(elements
: Map[MClassType, Set[MType]]): Map[MClassType, Int] do
1211 for mclasstype
, mtypes
in elements
do
1212 self.masks
[mclasstype
] = compute_mask
(mtypes
)
1217 private fun compute_mask
(mtypes
: Set[MType]): Int do
1220 var used
= new List[Int]
1221 for mtype
in mtypes
do
1222 var res
= op
(mask
, self.coloration_result
[mtype
])
1223 if used
.has
(res
) then
1229 if used
.length
== mtypes
.length
then break
1235 redef fun build_tables
(elements
: Map[MClassType, Set[MType]]): Map[MClassType, Array[nullable MType]] do
1236 var tables
= new HashMap[MClassType, Array[nullable MType]]
1238 for mclasstype
, mtypes
in elements
do
1239 var table
= new Array[nullable MType]
1240 for mtype
in mtypes
do
1241 var color
= phash
(self.coloration_result
[mtype
], masks
[mclasstype
])
1242 if table
.length
<= color
then
1243 for i
in [table
.length
.. color
[ do
1247 table
[color
] = mtype
1249 tables
[mclasstype
] = table
1254 private fun op
(mask
: Int, id
:Int): Int is abstract
1255 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
1258 class UnanchoredTypeModPerfectHashing
1259 super UnanchoredTypePerfectHashing
1261 redef fun op
(mask
, id
) do return mask
% id
1264 class UnanchoredTypeAndPerfectHashing
1265 super UnanchoredTypePerfectHashing
1267 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
1273 redef class HashSet[E
]
1274 init from
(elements
: Collection[E
]) do
1276 self.add_all
(elements
)
1280 redef class Array[E
]
1281 init from
(elements
: Collection[E
]) do
1283 self.add_all
(elements
)
1286 # Return a new Array with the elements only contened in 'self' and not in 'o'
1287 fun -(o
: Array[E
]): Array[E
] do
1288 var res
= new Array[E
]
1289 for e
in self do if not o
.has
(e
) then res
.add
(e
)
1296 # Return a linearization of a set of mtypes
1297 private fun linearize_mtypes
(mtypes
: Set[MType]): Array[MType] do
1298 var lin
= new Array[MType].from
(mtypes
)
1299 var sorter
= new TypeSorter(self)
1304 # Return a reverse linearization of a set of mtypes
1305 private fun reverse_linearize_mtypes
(mtypes
: Set[MType]): Array[MType] do
1306 var lin
= new Array[MType].from
(mtypes
)
1307 var sorter
= new ReverseTypeSorter(self)
1312 # Return super types of a `mtype` in `self`
1313 private fun super_mtypes
(mtype
: MType, mtypes
: Set[MType]): Set[MType] do
1314 if not self.super_mtypes_cache
.has_key
(mtype
) then
1315 var supers
= new HashSet[MType]
1316 for otype
in mtypes
do
1317 if otype
== mtype
then continue
1318 if mtype
.is_subtype
(self, null, otype
) then
1322 self.super_mtypes_cache
[mtype
] = supers
1324 return self.super_mtypes_cache
[mtype
]
1327 private var super_mtypes_cache
: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
1329 # Return all sub mtypes (directs and indirects) of a `mtype` in `self`
1330 private fun sub_mtypes
(mtype
: MType, mtypes
: Set[MType]): Set[MType] do
1331 if not self.sub_mtypes_cache
.has_key
(mtype
) then
1332 var subs
= new HashSet[MType]
1333 for otype
in mtypes
do
1334 if otype
== mtype
then continue
1335 if otype
.is_subtype
(self, null, mtype
) then
1339 self.sub_mtypes_cache
[mtype
] = subs
1341 return self.sub_mtypes_cache
[mtype
]
1344 private var sub_mtypes_cache
: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
1346 # Return a linearization of a set of mclasses
1347 private fun linearize_mclasses
(mclasses
: Set[MClass]): Array[MClass] do
1348 var lin
= new Array[MClass].from
(mclasses
)
1349 var sorter
= new ClassSorter(self)
1354 # Return a reverse linearization of a set of mtypes
1355 private fun reverse_linearize_mclasses
(mclasses
: Set[MClass]): Array[MClass] do
1356 var lin
= new Array[MClass].from
(mclasses
)
1357 var sorter
= new ReverseClassSorter(self)
1362 # Return all super mclasses (directs and indirects) of a `mclass` in `self`
1363 private fun super_mclasses
(mclass
: MClass): Set[MClass] do
1364 if not self.super_mclasses_cache
.has_key
(mclass
) then
1365 var supers
= new HashSet[MClass]
1366 if self.flatten_mclass_hierarchy
.has
(mclass
) then
1367 for sup
in self.flatten_mclass_hierarchy
[mclass
].greaters
do
1368 if sup
== mclass
then continue
1372 self.super_mclasses_cache
[mclass
] = supers
1374 return self.super_mclasses_cache
[mclass
]
1377 private var super_mclasses_cache
: Map[MClass, Set[MClass]] = new HashMap[MClass, Set[MClass]]
1379 # Return all parents of a `mclass` in `self`
1380 private fun parent_mclasses
(mclass
: MClass): Set[MClass] do
1381 if not self.parent_mclasses_cache
.has_key
(mclass
) then
1382 var parents
= new HashSet[MClass]
1383 if self.flatten_mclass_hierarchy
.has
(mclass
) then
1384 for sup
in self.flatten_mclass_hierarchy
[mclass
].direct_greaters
do
1385 if sup
== mclass
then continue
1389 self.parent_mclasses_cache
[mclass
] = parents
1391 return self.parent_mclasses_cache
[mclass
]
1394 private var parent_mclasses_cache
: Map[MClass, Set[MClass]] = new HashMap[MClass, Set[MClass]]
1396 # Return all sub mclasses (directs and indirects) of a `mclass` in `self`
1397 private fun sub_mclasses
(mclass
: MClass): Set[MClass] do
1398 if not self.sub_mclasses_cache
.has_key
(mclass
) then
1399 var subs
= new HashSet[MClass]
1400 if self.flatten_mclass_hierarchy
.has
(mclass
) then
1401 for sub
in self.flatten_mclass_hierarchy
[mclass
].smallers
do
1402 if sub
== mclass
then continue
1406 self.sub_mclasses_cache
[mclass
] = subs
1408 return self.sub_mclasses_cache
[mclass
]
1411 private var sub_mclasses_cache
: Map[MClass, Set[MClass]] = new HashMap[MClass, Set[MClass]]
1413 # All 'mproperties' associated to all 'mclassdefs' of `mclass`
1414 private fun properties
(mclass
: MClass): Set[MProperty] do
1415 if not self.properties_cache
.has_key
(mclass
) then
1416 var properties
= new HashSet[MProperty]
1417 var parents
= self.super_mclasses
(mclass
)
1418 for parent
in parents
do
1419 properties
.add_all
(self.properties
(parent
))
1422 for mclassdef
in mclass
.mclassdefs
do
1423 for mpropdef
in mclassdef
.mpropdefs
do
1424 properties
.add
(mpropdef
.mproperty
)
1427 self.properties_cache
[mclass
] = properties
1429 return properties_cache
[mclass
]
1432 private var properties_cache
: Map[MClass, Set[MProperty]] = new HashMap[MClass, Set[MProperty]]
1435 # A sorter for linearize list of types
1437 super AbstractSorter[MType]
1439 private var mmodule
: MModule
1441 init(mmodule
: MModule) do self.mmodule
= mmodule
1443 redef fun compare
(a
, b
) do
1446 else if a
.is_subtype
(self.mmodule
, null, b
) then
1453 # A sorter for reverse linearization
1454 class ReverseTypeSorter
1457 init(mmodule
: MModule) do end
1459 redef fun compare
(a
, b
) do
1462 else if a
.is_subtype
(self.mmodule
, null, b
) then
1469 # A sorter for linearize list of classes
1470 private class ClassSorter
1471 super AbstractSorter[MClass]
1473 var mmodule
: MModule
1475 redef fun compare
(a
, b
) do
1478 else if self.mmodule
.flatten_mclass_hierarchy
.has
(a
) and self.mmodule
.flatten_mclass_hierarchy
[a
].greaters
.has
(b
) then
1485 # A sorter for reverse linearization
1486 private class ReverseClassSorter
1487 super AbstractSorter[MClass]
1489 var mmodule
: MModule
1491 redef fun compare
(a
, b
) do
1494 else if self.mmodule
.flatten_mclass_hierarchy
.has
(a
) and self.mmodule
.flatten_mclass_hierarchy
[a
].greaters
.has
(b
) then