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
23 # Unic ids or each Mtype
24 var ids
: Map[MType, Int] = new HashMap[MType, Int]
25 # Fixed positions of each MType in all tables
26 var pos
: Map[MType, Int] = new HashMap[MType, Int]
31 # Masks used by hash function
32 var masks
: Map[MType, Int] = new HashMap[MType, Int]
33 # Positions of each MType for each tables
34 var hashes
: Map[MType, Map[MType, Int]] = new HashMap[MType, Map[MType, Int]]
37 abstract class TypeLayoutBuilder
39 type LAYOUT: TypeLayout
41 private var mmodule
: MModule
42 init(mmodule
: MModule) do self.mmodule
= mmodule
44 # Compute mtypes ids and position
45 fun build_layout
(mtypes
: Set[MType]): LAYOUT is abstract
47 # Give each MType a unic id using a descending linearization of the `mtypes` set
48 private fun compute_ids
(mtypes
: Set[MType]): Map[MType, Int] do
49 var ids
= new HashMap[MType, Int]
50 var lin
= self.mmodule
.reverse_linearize_mtypes
(mtypes
)
52 ids
[mtype
] = ids
.length
58 # Layout builder for MType using Binary Matrix (BM)
59 class BMTypeLayoutBuilder
60 super TypeLayoutBuilder
62 init(mmodule
: MModule) do super
64 # Compute mtypes ids and position using BM
65 redef fun build_layout
(mtypes
: Set[MType]): TypeLayout do
66 var result
= new TypeLayout
67 result
.ids
= self.compute_ids
(mtypes
)
68 result
.pos
= result
.ids
73 # Layout builder for MType using Coloring (CL)
74 class CLTypeLayoutBuilder
75 super TypeLayoutBuilder
77 private var colorer
: MTypeColorer
79 init(mmodule
: MModule) do
81 self.colorer
= new MTypeColorer(mmodule
)
84 # Compute mtypes ids and position using BM
85 redef fun build_layout
(mtypes
) do
86 var result
= new TypeLayout
87 result
.ids
= self.compute_ids
(mtypes
)
88 result
.pos
= self.colorer
.colorize
(mtypes
)
93 # Layout builder for MType using Perfect Hashing (PH)
94 class PHTypeLayoutBuilder
95 super TypeLayoutBuilder
97 redef type LAYOUT: PHTypeLayout
99 private var hasher
: MTypeHasher
101 init(mmodule
: MModule, operator
: PHOperator) do
103 self.hasher
= new MTypeHasher(mmodule
, operator
)
106 # Compute mtypes ids and position using BM
107 redef fun build_layout
(mtypes
) do
108 var result
= new PHTypeLayout
109 result
.ids
= self.compute_ids
(mtypes
)
110 result
.masks
= self.hasher
.compute_masks
(mtypes
, result
.ids
)
111 result
.hashes
= self.hasher
.compute_hashes
(mtypes
, result
.ids
, result
.masks
)
115 # Ids start from 1 instead of 0
116 redef fun compute_ids
(mtypes
) do
117 var ids
= new HashMap[MType, Int]
118 var lin
= self.mmodule
.reverse_linearize_mtypes
(mtypes
)
120 ids
[mtype
] = ids
.length
+ 1
126 abstract class AbstractColoring[E
: Object]
128 private var core
: Set[E
] = new HashSet[E
]
129 private var crown
: Set[E
] = new HashSet[E
]
130 private var border
: Set[E
] = new HashSet[E
]
132 private var coloration_result
: Map[E
, Int] = new HashMap[E
, Int]
136 fun colorize
(elements
: Set[E
]): Map[E
, Int] do
137 tag_elements
(elements
)
138 build_conflicts_graph
(elements
)
139 colorize_elements
(core
)
140 colorize_elements
(border
)
141 colorize_elements
(crown
)
142 return coloration_result
145 # Colorize a collection of elements
146 private fun colorize_elements
(elements
: Set[E
]) do
149 var lin
= reverse_linearize
(elements
)
150 for element
in lin
do
151 var color
= min_color
152 while not self.is_color_free
(element
, elements
, color
) do
155 coloration_result
[element
] = color
160 # Check if a related element to the element already use the color
161 private fun is_color_free
(element
: E
, elements
: Set[E
], color
: Int): Bool do
162 if conflicts_graph
.has_key
(element
) then
163 for st
in conflicts_graph
[element
] do
164 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
167 for st
in self.super_elements
(element
, elements
) do
168 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
173 # Tag elements as core, crown or border
174 private fun tag_elements
(elements
: Set[E
]) do
175 for element
in elements
do
176 # Check if sub elements are all in single inheritance
177 var all_subelements_si
= true
178 for subelem
in self.sub_elements
(element
, elements
) do
179 if self.is_element_mi
(subelem
, elements
) then
180 all_subelements_si
= false
185 # Tag as core, crown or border
186 if self.is_element_mi
(element
, elements
) then
187 core
.add_all
(self.super_elements
(element
, elements
))
189 if all_subelements_si
then
192 else if not all_subelements_si
then
193 core
.add_all
(self.super_elements
(element
, elements
))
201 # Conflicts graph of elements hierarchy (two types are in conflict if they have common subelements)
202 private fun build_conflicts_graph
(elements
: Set[E
]) do
203 self.conflicts_graph
= new HashMap[E
, HashSet[E
]]
204 var core
= reverse_linearize
(self.core
)
206 for i
in self.linear_extension
(t
, elements
) do
207 if t
== i
then continue
209 var lin_i
= self.linear_extension
(i
, elements
)
211 for j
in self.linear_extension
(t
, elements
) do
212 if i
== j
or j
== t
then continue
213 var lin_j
= self.linear_extension
(j
, elements
)
215 var d_ij
= lin_i
- lin_j
216 var d_ji
= lin_j
- lin_i
219 if not conflicts_graph
.has_key
(ed1
) then conflicts_graph
[ed1
] = new HashSet[E
]
220 # add ed1 x ed2 to conflicts graph
221 for ed2
in d_ji
do conflicts_graph
[ed1
].add
(ed2
)
224 if not conflicts_graph
.has_key
(ed1
) then conflicts_graph
[ed1
] = new HashSet[E
]
225 # add ed1 x ed2 to conflicts graph
226 for ed2
in d_ji
do conflicts_graph
[ed1
].add
(ed2
)
233 private var conflicts_graph
: nullable HashMap[E
, Set[E
]]
235 # cache for linear_extensions
236 private var linear_extensions_cache
: Map[E
, Array[E
]] = new HashMap[E
, Array[E
]]
238 # Return a linear_extension of super_elements of the element
239 private fun linear_extension
(element
: E
, elements
: Set[E
]): Array[E
] do
240 if not self.linear_extensions_cache
.has_key
(element
) then
241 var supers
= new HashSet[E
]
243 supers
.add_all
(self.super_elements
(element
, elements
))
244 self.linear_extensions_cache
[element
] = self.linearize
(supers
)
246 return self.linear_extensions_cache
[element
]
249 private fun super_elements
(element
: E
, elements
: Set[E
]): Set[E
] is abstract
250 private fun sub_elements
(element
: E
, elements
: Set[E
]): Set[E
] is abstract
251 private fun is_element_mi
(element
: E
, elements
: Set[E
]): Bool is abstract
252 private fun linearize
(elements
: Set[E
]): Array[E
] is abstract
253 private fun reverse_linearize
(elements
: Set[E
]): Array[E
] is abstract
257 private class MTypeColorer
258 super AbstractColoring[MType]
264 init(mmodule
: MModule) do self.mmodule
= mmodule
266 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mtypes
(element
, elements
)
267 redef fun is_element_mi
(element
, elements
) do return self.super_elements
(element
, elements
).length
> 1
268 redef fun sub_elements
(element
, elements
) do do return self.mmodule
.sub_mtypes
(element
, elements
)
269 redef fun linearize
(elements
) do return self.mmodule
.linearize_mtypes
(elements
)
270 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mtypes
(elements
)
273 # MType Perfect Hashing
274 private class MTypeHasher
277 var operator
: PHOperator
279 init(mmodule
: MModule, operator
: PHOperator) do
280 self.mmodule
= mmodule
281 self.operator
= operator
284 fun compute_masks
(mtypes
: Set[MType], ids
: Map[MType, Int]): Map[MType, Int] do
285 var masks
= new HashMap[MType, Int]
286 for mtype
in mtypes
do
287 var supers
= new HashSet[MType]
288 supers
.add_all
(self.mmodule
.super_mtypes
(mtype
, mtypes
))
290 masks
[mtype
] = compute_mask
(supers
, ids
)
295 private fun compute_mask
(supers
: Set[MType], ids
: Map[MType, Int]): Int do
298 var used
= new List[Int]
300 var res
= operator
.op
(mask
, ids
[sup
])
301 if used
.has
(res
) then
307 if used
.length
== supers
.length
then break
313 fun compute_hashes
(mtypes
: Set[MType], ids
: Map[MType, Int], masks
: Map[MType, Int]): Map[MType, Map[MType, Int]] do
314 var hashes
= new HashMap[MType, Map[MType, Int]]
315 for mtype
in mtypes
do
316 var supers
= new HashSet[MType]
317 supers
.add_all
(self.mmodule
.super_mtypes
(mtype
, mtypes
))
319 var inhashes
= new HashMap[MType, Int]
320 var mask
= masks
[mtype
]
322 inhashes
[sup
] = operator
.op
(mask
, ids
[sup
])
324 hashes
[mtype
] = inhashes
330 # Abstract operator used for perfect hashing
331 abstract class PHOperator
332 fun op
(mask
: Int, id
:Int): Int is abstract
335 # Hashing using modulo (MOD) operator
340 redef fun op
(mask
, id
) do return mask
% id
343 # Hashing using binary and (AND) operator
348 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
353 super AbstractColoring[MClass]
357 private var mmodule
: MModule
360 private var super_elements_cache
: Map[T
, Set[T
]] = new HashMap[T
, Set[T
]]
361 private var parent_elements_cache
: Map[T
, Set[T
]] = new HashMap[T
, Set[T
]]
362 private var sub_elements_cache
: Map[T
, Set[T
]] = new HashMap[T
, Set[T
]]
364 init(mainmodule
: MModule) do self.mmodule
= mainmodule
366 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mclasses
(element
)
367 fun parent_elements
(element
: MClass): Set[MClass] do return self.mmodule
.parent_mclasses
(element
)
368 redef fun is_element_mi
(element
, elements
) do return self.parent_elements
(element
).length
> 1
369 redef fun sub_elements
(element
, elements
) do do return self.mmodule
.sub_mclasses
(element
)
370 redef fun linearize
(elements
) do return self.mmodule
.linearize_mclasses
(elements
)
371 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mclasses
(elements
)
374 # incremental coloring (very naive)
375 class NaiveClassColoring
378 init(mainmodule
: MModule) do
382 # naive coloring that use incremental coloring
383 redef fun colorize_elements
(elements
) do
385 self.coloration_result
[e
] = self.coloration_result
.length
390 abstract class ClassPerfectHashing
393 init(mainmodule
: MModule) do
397 fun compute_masks
(elements
: Set[T
], ids
: Map[T
, Int]): Map[T
, Int] do
399 # Create super type list
400 var supers
= new HashSet[T
]
401 supers
.add_all
(self.super_elements
(e
, elements
))
403 # Compute the hashing 'mask'
404 self.coloration_result
[e
] = compute_mask
(supers
, ids
)
406 return self.coloration_result
409 private fun compute_mask
(mtypes
: Set[T
], ids
: Map[T
, Int]): Int do
412 var used
= new List[Int]
414 var res
= op
(mask
, ids
[sup
])
415 if used
.has
(res
) then
421 if used
.length
== mtypes
.length
then break
427 private fun op
(mask
: Int, id
:Int): Int is abstract
428 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
431 class ClassModPerfectHashing
432 super ClassPerfectHashing
433 init(mainmodule
: MModule) do
436 redef fun op
(mask
, id
) do return mask
% id
439 class ClassAndPerfectHashing
440 super ClassPerfectHashing
441 init(mainmodule
: MModule) do
444 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
448 class PropertyColoring
450 type MPROP: MProperty
451 type MPROPDEF: MPropDef
453 private var class_coloring
: ClassColoring
454 private var coloration_result
: Map[MPROP, Int] = new HashMap[MPROP, Int]
456 init(class_coloring
: ClassColoring) do
457 self.class_coloring
= class_coloring
460 fun colorize
: Map[MPROP, Int] do
461 colorize_core_properties
462 colorize_crown_properties
463 return self.coloration_result
466 fun build_property_tables
: Map[MClass, Array[nullable MPROPDEF]] do
467 var tables
= new HashMap[MClass, Array[nullable MPROPDEF]]
468 var mclasses
= self.class_coloring
.coloration_result
.keys
469 for mclass
in mclasses
do
470 var table
= new Array[nullable MPROPDEF]
471 # first, fill table from parents by reverse linearization order
472 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
473 var lin
= self.class_coloring
.reverse_linearize
(parents
)
475 for mproperty
in self.properties
(parent
) do
476 var color
= self.coloration_result
[mproperty
]
477 if table
.length
<= color
then
478 for i
in [table
.length
.. color
[ do
482 for mpropdef
in mproperty
.mpropdefs
do
483 if mpropdef
.mclassdef
.mclass
== parent
then
484 table
[color
] = mpropdef
490 # then override with local properties
491 for mproperty
in self.properties
(mclass
) do
492 var color
= self.coloration_result
[mproperty
]
493 if table
.length
<= color
then
494 for i
in [table
.length
.. color
[ do
498 for mpropdef
in mproperty
.mpropdefs
do
499 if mpropdef
.mclassdef
.mclass
== mclass
then
500 table
[color
] = mpropdef
504 tables
[mclass
] = table
509 # Colorize properties of the core hierarchy
510 private fun colorize_core_properties
do
511 var mclasses
= self.class_coloring
.core
514 for mclass
in mclasses
do
515 var color
= min_color
517 # if the class is root, get the minimal color
518 if self.class_coloring
.parent_elements
(mclass
).length
== 0 then
519 colorize_elements
(self.properties
(mclass
), color
)
521 # check last color used by parents
522 color
= max_color
(color
, self.class_coloring
.parent_elements
(mclass
))
523 # check max color used in conflicts
524 if self.class_coloring
.conflicts_graph
.has_key
(mclass
) then
525 color
= max_color
(color
, self.class_coloring
.conflicts_graph
[mclass
])
529 colorize_elements
(self.properties
(mclass
), color
)
534 # Colorize properties of the crown hierarchy
535 private fun colorize_crown_properties
do
536 for mclass
in self.class_coloring
.crown
do
537 colorize_elements
(self.properties
(mclass
), max_color
(0, self.class_coloring
.parent_elements
(mclass
)))
541 # Colorize a collection of properties given a starting color
542 private fun colorize_elements
(elements
: Collection[MPROP], start_color
: Int) do
543 for element
in elements
do
544 if self.coloration_result
.has_key
(element
) then continue
545 self.coloration_result
[element
] = start_color
550 private fun max_color
(min_color
: Int, mclasses
: Collection[MClass]): Int do
551 var max_color
= min_color
553 for mclass
in mclasses
do
554 for mproperty
in self.properties
(mclass
) do
555 var color
= min_color
556 if self.coloration_result
.has_key
(mproperty
) then
557 color
= self.coloration_result
[mproperty
]
558 if color
>= max_color
then max_color
= color
+ 1
566 private var properties_cache
: Map[MClass, Set[MPROP]] = new HashMap[MClass, Set[MPROP]]
568 # All 'mproperties' associated to all 'mclassdefs' of the class
569 private fun properties
(mclass
: MClass): Set[MPROP] do
570 if not self.properties_cache
.has_key
(mclass
) then
571 var properties
= new HashSet[MPROP]
572 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
573 for parent
in parents
do
574 properties
.add_all
(self.properties
(parent
))
577 for mclassdef
in mclass
.mclassdefs
do
578 for mpropdef
in mclassdef
.mpropdefs
do
579 var mproperty
= mpropdef
.mproperty
580 if mproperty
isa MPROP then
581 properties
.add
(mproperty
)
585 self.properties_cache
[mclass
] = properties
587 return properties_cache
[mclass
]
593 super PropertyColoring
595 redef type MPROP: MMethod
596 redef type MPROPDEF: MMethodDef
597 init(class_coloring
: ClassColoring) do end
600 # MAttribute coloring
601 class AttributeColoring
602 super PropertyColoring
604 redef type MPROP: MAttribute
605 redef type MPROPDEF: MAttributeDef
606 init(class_coloring
: ClassColoring) do end
609 # MVirtualTypeProp coloring
611 super PropertyColoring
613 redef type MPROP: MVirtualTypeProp
614 redef type MPROPDEF: MVirtualTypeDef
615 init(class_coloring
: ClassColoring) do end
618 class NaiveVTColoring
621 init(class_coloring
: ClassColoring) do end
623 redef fun colorize
: Map[MPROP, Int] do
624 var mclasses
= new HashSet[MClass]
625 mclasses
.add_all
(self.class_coloring
.core
)
626 mclasses
.add_all
(self.class_coloring
.crown
)
629 for mclass
in mclasses
do
630 min_color
= max_color
(min_color
, mclasses
)
631 colorize_elements
(self.properties
(mclass
), min_color
)
633 return self.coloration_result
637 abstract class VTPerfectHashing
640 private var masks
: Map[MClass, Int] = new HashMap[MClass, Int]
642 init(class_coloring
: ClassColoring) do end
644 redef fun colorize
: Map[MPROP, Int] do
645 var mclasses
= new HashSet[MClass]
646 mclasses
.add_all
(self.class_coloring
.core
)
647 mclasses
.add_all
(self.class_coloring
.crown
)
648 for mclass
in mclasses
do
649 var vts
= self.properties
(mclass
)
651 if coloration_result
.has_key
(vt
) then continue
652 coloration_result
[vt
] = coloration_result
.length
+ 1
655 return self.coloration_result
658 fun compute_masks
: Map[MClass, Int] do
659 var mclasses
= new HashSet[MClass]
660 mclasses
.add_all
(self.class_coloring
.core
)
661 mclasses
.add_all
(self.class_coloring
.crown
)
662 for mclass
in mclasses
do
663 self.masks
[mclass
] = compute_mask
(self.properties
(mclass
))
668 private fun compute_mask
(vts
: Set[MPROP]): Int do
671 var used
= new List[Int]
673 var res
= op
(mask
, self.coloration_result
[vt
])
674 if used
.has
(res
) then
680 if used
.length
== vts
.length
then break
686 redef fun build_property_tables
do
687 var tables
= new HashMap[MClass, Array[nullable MPROPDEF]]
689 for mclass
in self.class_coloring
.coloration_result
.keys
do
690 var table
= new Array[nullable MPROPDEF]
691 # first, fill table from parents by reverse linearization order
692 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
693 var lin
= self.class_coloring
.reverse_linearize
(parents
)
695 for mproperty
in self.properties
(parent
) do
696 var color
= phash
(self.coloration_result
[mproperty
], masks
[mclass
])
697 if table
.length
<= color
then
698 for i
in [table
.length
.. color
[ do
702 for mpropdef
in mproperty
.mpropdefs
do
703 if mpropdef
.mclassdef
.mclass
== parent
then
704 table
[color
] = mpropdef
710 # then override with local properties
711 for mproperty
in self.properties
(mclass
) do
712 var color
= phash
(self.coloration_result
[mproperty
], masks
[mclass
])
713 if table
.length
<= color
then
714 for i
in [table
.length
.. color
[ do
718 for mpropdef
in mproperty
.mpropdefs
do
719 if mpropdef
.mclassdef
.mclass
== mclass
then
720 table
[color
] = mpropdef
724 tables
[mclass
] = table
729 private fun op
(mask
: Int, id
:Int): Int is abstract
730 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
734 class VTModPerfectHashing
735 super VTPerfectHashing
736 init(class_coloring
: ClassColoring) do end
737 redef fun op
(mask
, id
) do return mask
% id
740 class VTAndPerfectHashing
741 super VTPerfectHashing
742 init(class_coloring
: ClassColoring) do end
743 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
746 # MParameterType coloring
748 private var class_coloring
: ClassColoring
749 private var coloration_result
: Map[MParameterType, Int] = new HashMap[MParameterType, Int]
751 init(class_coloring
: ClassColoring) do
752 self.class_coloring
= class_coloring
755 fun colorize
: Map[MParameterType, Int] do
756 colorize_core_properties
757 colorize_crown_properties
758 return self.coloration_result
761 # Colorize properties of the core hierarchy
762 private fun colorize_core_properties
do
763 var mclasses
= self.class_coloring
.core
766 for mclass
in mclasses
do
767 var color
= min_color
769 # if the class is root, get the minimal color
770 if self.class_coloring
.parent_elements
(mclass
).length
== 0 then
771 colorize_elements
(self.fts
(mclass
), color
)
773 # check last color used by parents
774 color
= max_color
(color
, self.class_coloring
.parent_elements
(mclass
))
775 # check max color used in conflicts
776 if self.class_coloring
.conflicts_graph
.has_key
(mclass
) then
777 color
= max_color
(color
, self.class_coloring
.conflicts_graph
[mclass
])
780 colorize_elements
(self.fts
(mclass
), color
)
785 # Colorize properties of the crown hierarchy
786 private fun colorize_crown_properties
do
787 for mclass
in self.class_coloring
.crown
do
788 colorize_elements
(self.fts
(mclass
), max_color
(0, self.class_coloring
.parent_elements
(mclass
)))
792 # Colorize a collection of properties given a starting color
793 private fun colorize_elements
(elements
: Collection[MParameterType], start_color
: Int) do
794 for element
in elements
do
795 if self.coloration_result
.has_key
(element
) then continue
796 self.coloration_result
[element
] = start_color
801 private fun max_color
(min_color
: Int, mclasses
: Collection[MClass]): Int do
802 var max_color
= min_color
804 for mclass
in mclasses
do
805 for ft
in self.fts
(mclass
) do
806 var color
= min_color
807 if self.coloration_result
.has_key
(ft
) then
808 color
= self.coloration_result
[ft
]
809 if color
>= max_color
then max_color
= color
+ 1
817 private var fts_cache
: Map[MClass, Set[MParameterType]] = new HashMap[MClass, Set[MParameterType]]
819 private fun fts
(mclass
: MClass): Set[MParameterType] do
820 if not self.fts_cache
.has_key
(mclass
) then
821 var fts
= new HashSet[MParameterType]
822 var mclass_type
= mclass
.mclass_type
823 if mclass_type
isa MGenericType then
824 for ft
in mclass_type
.arguments
do
825 fts
.add
(ft
.as(MParameterType))
828 self.fts_cache
[mclass
] = fts
830 return fts_cache
[mclass
]
833 fun build_ft_tables
: Map[MClass, Array[nullable MParameterType]] do
834 var tables
= new HashMap[MClass, Array[nullable MParameterType]]
836 for mclass
in self.class_coloring
.coloration_result
.keys
do
837 var table
= new Array[nullable MParameterType]
839 # first, fill table from parents
840 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
841 for parent
in parents
do
842 for ft
in self.fts
(parent
) do
843 var color
= self.coloration_result
[ft
]
844 if table
.length
<= color
then
845 for i
in [table
.length
.. color
[ do
853 # then override with local properties
854 for ft
in self.fts
(mclass
) do
855 var color
= self.coloration_result
[ft
]
856 if table
.length
<= color
then
857 for i
in [table
.length
.. color
[ do
863 tables
[mclass
] = table
869 class NaiveFTColoring
872 init(class_coloring
: ClassColoring) do end
874 redef fun colorize
: Map[MParameterType, Int] do
875 var mclasses
= new HashSet[MClass]
876 mclasses
.add_all
(self.class_coloring
.core
)
877 mclasses
.add_all
(self.class_coloring
.crown
)
880 for mclass
in mclasses
do
881 min_color
= max_color
(min_color
, mclasses
)
882 colorize_elements
(self.fts
(mclass
), min_color
)
884 return self.coloration_result
888 abstract class FTPerfectHashing
891 private var masks
: Map[MClass, Int] = new HashMap[MClass, Int]
893 init(class_coloring
: ClassColoring) do end
895 redef fun colorize
: Map[MParameterType, Int] do
896 var mclasses
= new HashSet[MClass]
897 mclasses
.add_all
(self.class_coloring
.core
)
898 mclasses
.add_all
(self.class_coloring
.crown
)
899 for mclass
in mclasses
do
900 for ft
in self.fts
(mclass
) do
901 if coloration_result
.has_key
(ft
) then continue
902 coloration_result
[ft
] = coloration_result
.length
+ 1
905 return self.coloration_result
908 fun compute_masks
: Map[MClass, Int] do
909 var mclasses
= new HashSet[MClass]
910 mclasses
.add_all
(self.class_coloring
.core
)
911 mclasses
.add_all
(self.class_coloring
.crown
)
912 for mclass
in mclasses
do
913 var fts
= new HashSet[MParameterType]
914 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
915 for parent
in parents
do
916 fts
.add_all
(self.fts
(parent
))
918 fts
.add_all
(self.fts
(mclass
))
919 self.masks
[mclass
] = compute_mask
(fts
)
924 private fun compute_mask
(fts
: Set[MParameterType]): Int do
927 var used
= new List[Int]
929 var res
= op
(mask
, self.coloration_result
[ft
])
930 if used
.has
(res
) then
936 if used
.length
== fts
.length
then break
942 redef fun build_ft_tables
do
943 var tables
= new HashMap[MClass, Array[nullable MParameterType]]
945 for mclass
in self.class_coloring
.coloration_result
.keys
do
946 var table
= new Array[nullable MParameterType]
948 # first, fill table from parents
949 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
950 for parent
in parents
do
951 for ft
in self.fts
(parent
) do
952 var color
= phash
(self.coloration_result
[ft
], masks
[mclass
])
953 if table
.length
<= color
then
954 for i
in [table
.length
.. color
[ do
962 # then override with local properties
963 for ft
in self.fts
(mclass
) do
964 var color
= phash
(self.coloration_result
[ft
], masks
[mclass
])
965 if table
.length
<= color
then
966 for i
in [table
.length
.. color
[ do
972 tables
[mclass
] = table
977 private fun op
(mask
: Int, id
:Int): Int is abstract
978 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
981 class FTModPerfectHashing
982 super FTPerfectHashing
983 init(class_coloring
: ClassColoring) do end
984 redef fun op
(mask
, id
) do return mask
% id
987 class FTAndPerfectHashing
988 super FTPerfectHashing
989 init(class_coloring
: ClassColoring) do end
990 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
993 # Live Entries coloring
994 class LiveEntryColoring
996 private var coloration_result
: Map[MType, Int] = new HashMap[MType, Int]
997 private var conflicts_graph_cache
: nullable HashMap[MType, Set[MType]]
998 var livetypes_tables_sizes
: nullable Map[MClass, Array[Int]]
1002 fun colorize
(elements
: Collection[MType]): Map[MType, Int] do
1004 build_conflicts_graph
(elements
)
1007 colorize_elements
(elements
)
1009 return coloration_result
1013 fun build_livetype_tables
(mtypes
: Set[MType]): Map[MClass, Array[nullable Object]] do
1014 var livetypes_tables
= new HashMap[MClass, Array[nullable Object]]
1015 self.livetypes_tables_sizes
= new HashMap[MClass, Array[Int]]
1017 for mtype
in mtypes
do
1018 if mtype
isa MGenericType then
1019 var table
: Array[nullable Object]
1020 var sizes
: Array[Int]
1021 if livetypes_tables
.has_key
(mtype
.mclass
) then
1022 table
= livetypes_tables
[mtype
.mclass
]
1024 table
= new Array[nullable Object]
1025 livetypes_tables
[mtype
.mclass
] = table
1027 if livetypes_tables_sizes
.has_key
(mtype
.mclass
) then
1028 sizes
= livetypes_tables_sizes
[mtype
.mclass
]
1030 sizes
= new Array[Int]
1031 livetypes_tables_sizes
[mtype
.mclass
] = sizes
1033 build_livetype_table
(mtype
, 0, table
, sizes
)
1037 return livetypes_tables
1040 # Build live gentype table recursively
1041 private fun build_livetype_table
(mtype
: MGenericType, current_rank
: Int, table
: Array[nullable Object], sizes
: Array[Int]) do
1042 var ft
= mtype
.arguments
[current_rank
]
1043 if not self.coloration_result
.has_key
(ft
) then return
1044 var color
= self.coloration_result
[ft
]
1046 if current_rank
>= sizes
.length
then
1047 sizes
[current_rank
] = color
+ 1
1048 else if color
>= sizes
[current_rank
] then
1049 sizes
[current_rank
] = color
+ 1
1052 if color
> table
.length
then
1053 for i
in [table
.length
.. color
[ do table
[i
] = null
1056 if current_rank
== mtype
.arguments
.length
- 1 then
1057 table
[color
] = mtype
1059 var ft_table
: Array[nullable Object]
1060 if color
< table
.length
and table
[color
] != null then
1061 ft_table
= table
[color
].as(Array[nullable Object])
1063 ft_table
= new Array[nullable Object]
1065 table
[color
] = ft_table
1066 build_livetype_table
(mtype
, current_rank
+ 1, ft_table
, sizes
)
1070 # Colorize a collection of elements
1071 fun colorize_elements
(elements
: Collection[MType]) do
1074 for element
in elements
do
1075 var color
= min_color
1076 while not self.is_color_free
(element
, color
) do
1079 coloration_result
[element
] = color
1084 # Check if a related element to the element already use the color
1085 private fun is_color_free
(element
: MType, color
: Int): Bool do
1086 if conflicts_graph
.has_key
(element
) then
1087 for st
in conflicts_graph
[element
] do
1088 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
1094 # look for types in the same generic signatures
1095 private fun build_conflicts_graph
(elements
: Collection[MType]) do
1096 # regroup types by classes
1097 var genclasses
= new HashMap[MClass, Set[MType]]
1098 for e
in elements
do
1099 if e
isa MGenericType then
1100 if not genclasses
.has_key
(e
.mclass
) then
1101 genclasses
[e
.mclass
] = new HashSet[MType]
1103 genclasses
[e
.mclass
].add
(e
)
1108 self.conflicts_graph_cache
= new HashMap[MType, Set[MType]]
1109 for mclass
, mtypes
in genclasses
do
1111 for rank
in [0..mclass
.arity
[ do
1112 # for each live type
1113 for mtype
in mtypes
do
1114 var mclasstype
: MClassType
1115 if mtype
isa MNullableType then
1116 mclasstype
= mtype
.mtype
.as(MClassType)
1118 mclasstype
= mtype
.as(MClassType)
1120 var ft
= mclasstype
.arguments
[rank
]
1121 for otype
in mtypes
do
1122 if mtype
== otype
then continue
1123 var oclasstype
: MClassType
1124 if otype
isa MNullableType then
1125 oclasstype
= otype
.mtype
.as(MClassType)
1127 oclasstype
= otype
.as(MClassType)
1129 var oft
= oclasstype
.arguments
[rank
]
1130 self.add_conflict
(ft
, oft
)
1137 private fun add_conflict
(mtype
: MType, otype
: MType) do
1138 if mtype
== otype
then return
1139 if not self.conflicts_graph_cache
.has_key
(mtype
) then self.conflicts_graph_cache
[mtype
] = new HashSet[MType]
1140 self.conflicts_graph_cache
[mtype
].add
(otype
)
1141 if not self.conflicts_graph_cache
.has_key
(otype
) then self.conflicts_graph_cache
[otype
] = new HashSet[MType]
1142 self.conflicts_graph_cache
[otype
].add
(mtype
)
1144 private fun conflicts_graph
: Map[MType, Set[MType]] do return conflicts_graph_cache
.as(not null)
1147 class NaiveLiveEntryColoring
1148 super LiveEntryColoring
1152 redef fun colorize_elements
(elements
: Collection[MType]) do
1154 for element
in elements
do
1155 coloration_result
[element
] = color
1161 # live unanchored coloring
1162 class UnanchoredTypeColoring
1164 private var coloration_result
: Map[MType, Int] = new HashMap[MType, Int]
1165 private var conflicts_graph
: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
1169 fun colorize
(elements
: Map[MClassType, Set[MType]]): Map[MType, Int] do
1170 build_conflicts_graph
(elements
)
1171 colorize_elements
(elements
)
1172 return coloration_result
1175 fun build_tables
(elements
: Map[MClassType, Set[MType]]): Map[MClassType, Array[nullable MType]] do
1176 var tables
= new HashMap[MClassType, Array[nullable MType]]
1178 for mclasstype
, mtypes
in elements
do
1179 var table
= new Array[nullable MType]
1180 for mtype
in mtypes
do
1181 var color
= self.coloration_result
[mtype
]
1182 if table
.length
<= color
then
1183 for i
in [table
.length
.. color
[ do
1187 table
[color
] = mtype
1189 tables
[mclasstype
] = table
1194 # Colorize a collection of elements
1195 fun colorize_elements
(elements
: Map[MClassType, Set[MType]]) do
1197 for mclasstype
, mclasstypes
in elements
do
1198 for element
in mclasstypes
do
1199 if self.coloration_result
.has_key
(element
) then continue
1200 var color
= min_color
1201 while not self.is_color_free
(element
, color
) do
1204 coloration_result
[element
] = color
1210 # Check if a related element to the element already use the color
1211 private fun is_color_free
(element
: MType, color
: Int): Bool do
1212 if conflicts_graph
.has_key
(element
) then
1213 for st
in conflicts_graph
[element
] do
1214 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
1220 # look for unanchored types generated by the same type
1221 private fun build_conflicts_graph
(elements
: Map[MClassType, Set[MType]]) do
1222 for mclasstype
, mtypes
in elements
do
1223 for mtype
in mtypes
do
1224 for otype
in mtypes
do
1225 if otype
== mtype
then continue
1226 self.add_conflict
(mtype
, otype
)
1232 private fun add_conflict
(mtype
: MType, otype
: MType) do
1233 if mtype
== otype
then return
1234 if not self.conflicts_graph
.has_key
(mtype
) then self.conflicts_graph
[mtype
] = new HashSet[MType]
1235 self.conflicts_graph
[mtype
].add
(otype
)
1236 if not self.conflicts_graph
.has_key
(otype
) then self.conflicts_graph
[otype
] = new HashSet[MType]
1237 self.conflicts_graph
[otype
].add
(mtype
)
1241 class NaiveUnanchoredTypeColoring
1242 super UnanchoredTypeColoring
1246 redef fun colorize_elements
(elements
: Map[MClassType, Set[MType]]) do
1248 for mclasstype
, mclasstypes
in elements
do
1249 for element
in mclasstypes
do
1250 coloration_result
[element
] = color
1257 abstract class UnanchoredTypePerfectHashing
1258 super NaiveUnanchoredTypeColoring
1260 private var masks
: Map[MClassType, Int] = new HashMap[MClassType, Int]
1264 redef fun colorize_elements
(elements
: Map[MClassType, Set[MType]]) do
1266 for mclasstype
, mclasstypes
in elements
do
1267 for element
in mclasstypes
do
1268 coloration_result
[element
] = color
1274 fun compute_masks
(elements
: Map[MClassType, Set[MType]]): Map[MClassType, Int] do
1275 for mclasstype
, mtypes
in elements
do
1276 self.masks
[mclasstype
] = compute_mask
(mtypes
)
1281 private fun compute_mask
(mtypes
: Set[MType]): Int do
1284 var used
= new List[Int]
1285 for mtype
in mtypes
do
1286 var res
= op
(mask
, self.coloration_result
[mtype
])
1287 if used
.has
(res
) then
1293 if used
.length
== mtypes
.length
then break
1299 redef fun build_tables
(elements
: Map[MClassType, Set[MType]]): Map[MClassType, Array[nullable MType]] do
1300 var tables
= new HashMap[MClassType, Array[nullable MType]]
1302 for mclasstype
, mtypes
in elements
do
1303 var table
= new Array[nullable MType]
1304 for mtype
in mtypes
do
1305 var color
= phash
(self.coloration_result
[mtype
], masks
[mclasstype
])
1306 if table
.length
<= color
then
1307 for i
in [table
.length
.. color
[ do
1311 table
[color
] = mtype
1313 tables
[mclasstype
] = table
1318 private fun op
(mask
: Int, id
:Int): Int is abstract
1319 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
1322 class UnanchoredTypeModPerfectHashing
1323 super UnanchoredTypePerfectHashing
1325 redef fun op
(mask
, id
) do return mask
% id
1328 class UnanchoredTypeAndPerfectHashing
1329 super UnanchoredTypePerfectHashing
1331 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
1337 redef class HashSet[E
]
1338 init from
(elements
: Collection[E
]) do
1340 self.add_all
(elements
)
1344 redef class Array[E
]
1345 init from
(elements
: Collection[E
]) do
1347 self.add_all
(elements
)
1350 # Return a new Array with the elements only contened in 'self' and not in 'o'
1351 fun -(o
: Array[E
]): Array[E
] do
1352 var res
= new Array[E
]
1353 for e
in self do if not o
.has
(e
) then res
.add
(e
)
1360 # Return a linearization of a set of mtypes
1361 private fun linearize_mtypes
(mtypes
: Set[MType]): Array[MType] do
1362 var lin
= new Array[MType].from
(mtypes
)
1363 var sorter
= new TypeSorter(self)
1368 # Return a reverse linearization of a set of mtypes
1369 private fun reverse_linearize_mtypes
(mtypes
: Set[MType]): Array[MType] do
1370 var lin
= new Array[MType].from
(mtypes
)
1371 var sorter
= new ReverseTypeSorter(self)
1376 # Return super types of a `mtype` in `self`
1377 private fun super_mtypes
(mtype
: MType, mtypes
: Set[MType]): Set[MType] do
1378 if not self.super_mtypes_cache
.has_key
(mtype
) then
1379 var supers
= new HashSet[MType]
1380 for otype
in mtypes
do
1381 if otype
== mtype
then continue
1382 if mtype
.is_subtype
(self, null, otype
) then
1386 self.super_mtypes_cache
[mtype
] = supers
1388 return self.super_mtypes_cache
[mtype
]
1391 private var super_mtypes_cache
: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
1393 # Return all sub mtypes (directs and indirects) of a `mtype` in `self`
1394 private fun sub_mtypes
(mtype
: MType, mtypes
: Set[MType]): Set[MType] do
1395 if not self.sub_mtypes_cache
.has_key
(mtype
) then
1396 var subs
= new HashSet[MType]
1397 for otype
in mtypes
do
1398 if otype
== mtype
then continue
1399 if otype
.is_subtype
(self, null, mtype
) then
1403 self.sub_mtypes_cache
[mtype
] = subs
1405 return self.sub_mtypes_cache
[mtype
]
1408 private var sub_mtypes_cache
: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
1410 # Return a linearization of a set of mclasses
1411 private fun linearize_mclasses
(mclasses
: Set[MClass]): Array[MClass] do
1412 var lin
= new Array[MClass].from
(mclasses
)
1413 var sorter
= new ClassSorter(self)
1418 # Return a reverse linearization of a set of mtypes
1419 private fun reverse_linearize_mclasses
(mclasses
: Set[MClass]): Array[MClass] do
1420 var lin
= new Array[MClass].from
(mclasses
)
1421 var sorter
= new ReverseClassSorter(self)
1426 # Return all super mclasses (directs and indirects) of a `mclass` in `self`
1427 private fun super_mclasses
(mclass
: MClass): Set[MClass] do
1428 if not self.super_mclasses_cache
.has_key
(mclass
) then
1429 var supers
= new HashSet[MClass]
1430 if self.flatten_mclass_hierarchy
.has
(mclass
) then
1431 for sup
in self.flatten_mclass_hierarchy
[mclass
].greaters
do
1432 if sup
== mclass
then continue
1436 self.super_mclasses_cache
[mclass
] = supers
1438 return self.super_mclasses_cache
[mclass
]
1441 private var super_mclasses_cache
: Map[MClass, Set[MClass]] = new HashMap[MClass, Set[MClass]]
1443 # Return all parents of a `mclass` in `self`
1444 private fun parent_mclasses
(mclass
: MClass): Set[MClass] do
1445 if not self.parent_mclasses_cache
.has_key
(mclass
) then
1446 var parents
= new HashSet[MClass]
1447 if self.flatten_mclass_hierarchy
.has
(mclass
) then
1448 for sup
in self.flatten_mclass_hierarchy
[mclass
].direct_greaters
do
1449 if sup
== mclass
then continue
1453 self.parent_mclasses_cache
[mclass
] = parents
1455 return self.parent_mclasses_cache
[mclass
]
1458 private var parent_mclasses_cache
: Map[MClass, Set[MClass]] = new HashMap[MClass, Set[MClass]]
1460 # Return all sub mclasses (directs and indirects) of a `mclass` in `self`
1461 private fun sub_mclasses
(mclass
: MClass): Set[MClass] do
1462 if not self.sub_mclasses_cache
.has_key
(mclass
) then
1463 var subs
= new HashSet[MClass]
1464 if self.flatten_mclass_hierarchy
.has
(mclass
) then
1465 for sub
in self.flatten_mclass_hierarchy
[mclass
].smallers
do
1466 if sub
== mclass
then continue
1470 self.sub_mclasses_cache
[mclass
] = subs
1472 return self.sub_mclasses_cache
[mclass
]
1475 private var sub_mclasses_cache
: Map[MClass, Set[MClass]] = new HashMap[MClass, Set[MClass]]
1477 # All 'mproperties' associated to all 'mclassdefs' of `mclass`
1478 private fun properties
(mclass
: MClass): Set[MProperty] do
1479 if not self.properties_cache
.has_key
(mclass
) then
1480 var properties
= new HashSet[MProperty]
1481 var parents
= self.super_mclasses
(mclass
)
1482 for parent
in parents
do
1483 properties
.add_all
(self.properties
(parent
))
1486 for mclassdef
in mclass
.mclassdefs
do
1487 for mpropdef
in mclassdef
.mpropdefs
do
1488 properties
.add
(mpropdef
.mproperty
)
1491 self.properties_cache
[mclass
] = properties
1493 return properties_cache
[mclass
]
1496 private var properties_cache
: Map[MClass, Set[MProperty]] = new HashMap[MClass, Set[MProperty]]
1499 # A sorter for linearize list of types
1501 super AbstractSorter[MType]
1503 private var mmodule
: MModule
1505 init(mmodule
: MModule) do self.mmodule
= mmodule
1507 redef fun compare
(a
, b
) do
1510 else if a
.is_subtype
(self.mmodule
, null, b
) then
1517 # A sorter for reverse linearization
1518 class ReverseTypeSorter
1521 init(mmodule
: MModule) do end
1523 redef fun compare
(a
, b
) do
1526 else if a
.is_subtype
(self.mmodule
, null, b
) then
1533 # A sorter for linearize list of classes
1534 private class ClassSorter
1535 super AbstractSorter[MClass]
1537 var mmodule
: MModule
1539 redef fun compare
(a
, b
) do
1542 else if self.mmodule
.flatten_mclass_hierarchy
.has
(a
) and self.mmodule
.flatten_mclass_hierarchy
[a
].greaters
.has
(b
) then
1549 # A sorter for reverse linearization
1550 private class ReverseClassSorter
1551 super AbstractSorter[MClass]
1553 var mmodule
: MModule
1555 redef fun compare
(a
, b
) do
1558 else if self.mmodule
.flatten_mclass_hierarchy
.has
(a
) and self.mmodule
.flatten_mclass_hierarchy
[a
].greaters
.has
(b
) then