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]]
39 abstract class TypeLayoutBuilder
41 type LAYOUT: TypeLayout
43 private var mmodule
: MModule
44 init(mmodule
: MModule) do self.mmodule
= mmodule
46 # Compute mtypes ids and position
47 fun build_layout
(mtypes
: Set[MType]): LAYOUT is abstract
49 # Give each MType a unic id using a descending linearization of the `mtypes` set
50 private fun compute_ids
(mtypes
: Set[MType]): Map[MType, Int] do
51 var ids
= new HashMap[MType, Int]
52 var lin
= self.mmodule
.reverse_linearize_mtypes
(mtypes
)
54 ids
[mtype
] = ids
.length
60 # Layout builder for MType using Binary Matrix (BM)
61 class BMTypeLayoutBuilder
62 super TypeLayoutBuilder
64 init(mmodule
: MModule) do super
66 # Compute mtypes ids and position using BM
67 redef fun build_layout
(mtypes
: Set[MType]): TypeLayout do
68 var result
= new TypeLayout
69 result
.ids
= self.compute_ids
(mtypes
)
70 result
.pos
= result
.ids
75 # Layout builder for MType using Coloring (CL)
76 class CLTypeLayoutBuilder
77 super TypeLayoutBuilder
79 private var colorer
: MTypeColorer
81 init(mmodule
: MModule) do
83 self.colorer
= new MTypeColorer(mmodule
)
86 # Compute mtypes ids and position using BM
87 redef fun build_layout
(mtypes
) do
88 var result
= new TypeLayout
89 result
.ids
= self.compute_ids
(mtypes
)
90 result
.pos
= self.colorer
.colorize
(mtypes
)
95 # Layout builder for MType using Perfect Hashing (PH)
96 class PHTypeLayoutBuilder
97 super TypeLayoutBuilder
99 redef type LAYOUT: PHTypeLayout
101 private var hasher
: MTypeHasher
103 init(mmodule
: MModule, operator
: PHOperator) do
105 self.hasher
= new MTypeHasher(mmodule
, operator
)
108 # Compute mtypes ids and position using BM
109 redef fun build_layout
(mtypes
) do
110 var result
= new PHTypeLayout
111 result
.ids
= self.compute_ids
(mtypes
)
112 result
.masks
= self.hasher
.compute_masks
(mtypes
, result
.ids
)
113 result
.hashes
= self.hasher
.compute_hashes
(mtypes
, result
.ids
, result
.masks
)
117 # Ids start from 1 instead of 0
118 redef fun compute_ids
(mtypes
) do
119 var ids
= new HashMap[MType, Int]
120 var lin
= self.mmodule
.reverse_linearize_mtypes
(mtypes
)
122 ids
[mtype
] = ids
.length
+ 1
130 abstract class AbstractColorer[E
: Object]
132 private var core
: Set[E
] = new HashSet[E
]
133 private var crown
: Set[E
] = new HashSet[E
]
134 private var border
: Set[E
] = new HashSet[E
]
136 private var coloration_result
: Map[E
, Int] = new HashMap[E
, Int]
140 fun colorize
(elements
: Set[E
]): Map[E
, Int] do
141 tag_elements
(elements
)
142 build_conflicts_graph
(elements
)
143 colorize_elements
(core
)
144 colorize_elements
(border
)
145 colorize_elements
(crown
)
146 return coloration_result
149 # Colorize a collection of elements
150 private fun colorize_elements
(elements
: Set[E
]) do
153 var lin
= reverse_linearize
(elements
)
154 for element
in lin
do
155 var color
= min_color
156 while not self.is_color_free
(element
, elements
, color
) do
159 coloration_result
[element
] = color
164 # Check if a related element to the element already use the color
165 private fun is_color_free
(element
: E
, elements
: Set[E
], color
: Int): Bool do
166 if conflicts_graph
.has_key
(element
) then
167 for st
in conflicts_graph
[element
] do
168 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
171 for st
in self.super_elements
(element
, elements
) do
172 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
177 # Tag elements as core, crown or border
178 private fun tag_elements
(elements
: Set[E
]) do
179 for element
in elements
do
180 # Check if sub elements are all in single inheritance
181 var all_subelements_si
= true
182 for subelem
in self.sub_elements
(element
, elements
) do
183 if self.is_element_mi
(subelem
, elements
) then
184 all_subelements_si
= false
189 # Tag as core, crown or border
190 if self.is_element_mi
(element
, elements
) then
191 core
.add_all
(self.super_elements
(element
, elements
))
193 if all_subelements_si
then
196 else if not all_subelements_si
then
197 core
.add_all
(self.super_elements
(element
, elements
))
205 # Conflicts graph of elements hierarchy (two types are in conflict if they have common subelements)
206 private fun build_conflicts_graph
(elements
: Set[E
]) do
207 self.conflicts_graph
= new HashMap[E
, HashSet[E
]]
208 var core
= reverse_linearize
(self.core
)
210 for i
in self.linear_extension
(t
, elements
) do
211 if t
== i
then continue
213 var lin_i
= self.linear_extension
(i
, elements
)
215 for j
in self.linear_extension
(t
, elements
) do
216 if i
== j
or j
== t
then continue
217 var lin_j
= self.linear_extension
(j
, elements
)
219 var d_ij
= lin_i
- lin_j
220 var d_ji
= lin_j
- lin_i
223 if not conflicts_graph
.has_key
(ed1
) then conflicts_graph
[ed1
] = new HashSet[E
]
224 # add ed1 x ed2 to conflicts graph
225 for ed2
in d_ji
do conflicts_graph
[ed1
].add
(ed2
)
228 if not conflicts_graph
.has_key
(ed1
) then conflicts_graph
[ed1
] = new HashSet[E
]
229 # add ed1 x ed2 to conflicts graph
230 for ed2
in d_ji
do conflicts_graph
[ed1
].add
(ed2
)
237 private var conflicts_graph
: nullable HashMap[E
, Set[E
]]
239 # cache for linear_extensions
240 private var linear_extensions_cache
: Map[E
, Array[E
]] = new HashMap[E
, Array[E
]]
242 # Return a linear_extension of super_elements of the element
243 private fun linear_extension
(element
: E
, elements
: Set[E
]): Array[E
] do
244 if not self.linear_extensions_cache
.has_key
(element
) then
245 var supers
= new HashSet[E
]
247 supers
.add_all
(self.super_elements
(element
, elements
))
248 self.linear_extensions_cache
[element
] = self.linearize
(supers
)
250 return self.linear_extensions_cache
[element
]
253 private fun super_elements
(element
: E
, elements
: Set[E
]): Set[E
] is abstract
254 private fun sub_elements
(element
: E
, elements
: Set[E
]): Set[E
] is abstract
255 private fun is_element_mi
(element
: E
, elements
: Set[E
]): Bool is abstract
256 private fun linearize
(elements
: Set[E
]): Array[E
] is abstract
257 private fun reverse_linearize
(elements
: Set[E
]): Array[E
] is abstract
261 private class MTypeColorer
262 super AbstractColorer[MType]
266 init(mmodule
: MModule) do self.mmodule
= mmodule
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
)
277 # MType Perfect Hashing
278 private class MTypeHasher
281 var operator
: PHOperator
283 init(mmodule
: MModule, operator
: PHOperator) do
284 self.mmodule
= mmodule
285 self.operator
= operator
288 fun compute_masks
(mtypes
: Set[MType], ids
: Map[MType, Int]): Map[MType, Int] do
289 var masks
= new HashMap[MType, Int]
290 for mtype
in mtypes
do
291 var supers
= new HashSet[MType]
292 supers
.add_all
(self.mmodule
.super_mtypes
(mtype
, mtypes
))
294 masks
[mtype
] = compute_mask
(supers
, ids
)
299 private fun compute_mask
(supers
: Set[MType], ids
: Map[MType, Int]): Int do
302 var used
= new List[Int]
304 var res
= operator
.op
(mask
, ids
[sup
])
305 if used
.has
(res
) then
311 if used
.length
== supers
.length
then break
317 fun compute_hashes
(mtypes
: Set[MType], ids
: Map[MType, Int], masks
: Map[MType, Int]): Map[MType, Map[MType, Int]] do
318 var hashes
= new HashMap[MType, Map[MType, Int]]
319 for mtype
in mtypes
do
320 var supers
= new HashSet[MType]
321 supers
.add_all
(self.mmodule
.super_mtypes
(mtype
, mtypes
))
323 var inhashes
= new HashMap[MType, Int]
324 var mask
= masks
[mtype
]
326 inhashes
[sup
] = operator
.op
(mask
, ids
[sup
])
328 hashes
[mtype
] = inhashes
334 # Abstract operator used for perfect hashing
335 abstract class PHOperator
336 fun op
(mask
: Int, id
:Int): Int is abstract
339 # Hashing using modulo (MOD) operator
344 redef fun op
(mask
, id
) do return mask
% id
347 # Hashing using binary and (AND) operator
352 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
357 super AbstractColorer[MClass]
361 private var mmodule
: MModule
364 private var super_elements_cache
: Map[T
, Set[T
]] = new HashMap[T
, Set[T
]]
365 private var parent_elements_cache
: Map[T
, Set[T
]] = new HashMap[T
, Set[T
]]
366 private var sub_elements_cache
: Map[T
, Set[T
]] = new HashMap[T
, Set[T
]]
368 init(mainmodule
: MModule) do self.mmodule
= mainmodule
370 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mclasses
(element
)
371 fun parent_elements
(element
: MClass): Set[MClass] do return self.mmodule
.parent_mclasses
(element
)
372 redef fun is_element_mi
(element
, elements
) do return self.parent_elements
(element
).length
> 1
373 redef fun sub_elements
(element
, elements
) do do return self.mmodule
.sub_mclasses
(element
)
374 redef fun linearize
(elements
) do return self.mmodule
.linearize_mclasses
(elements
)
375 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mclasses
(elements
)
378 # incremental coloring (very naive)
379 class NaiveClassColoring
382 init(mainmodule
: MModule) do
386 # naive coloring that use incremental coloring
387 redef fun colorize_elements
(elements
) do
389 self.coloration_result
[e
] = self.coloration_result
.length
394 abstract class ClassPerfectHashing
397 init(mainmodule
: MModule) do
401 fun compute_masks
(elements
: Set[T
], ids
: Map[T
, Int]): Map[T
, Int] do
403 # Create super type list
404 var supers
= new HashSet[T
]
405 supers
.add_all
(self.super_elements
(e
, elements
))
407 # Compute the hashing 'mask'
408 self.coloration_result
[e
] = compute_mask
(supers
, ids
)
410 return self.coloration_result
413 private fun compute_mask
(mtypes
: Set[T
], ids
: Map[T
, Int]): Int do
416 var used
= new List[Int]
418 var res
= op
(mask
, ids
[sup
])
419 if used
.has
(res
) then
425 if used
.length
== mtypes
.length
then break
431 private fun op
(mask
: Int, id
:Int): Int is abstract
432 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
435 class ClassModPerfectHashing
436 super ClassPerfectHashing
437 init(mainmodule
: MModule) do
440 redef fun op
(mask
, id
) do return mask
% id
443 class ClassAndPerfectHashing
444 super ClassPerfectHashing
445 init(mainmodule
: MModule) do
448 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
452 class PropertyColoring
454 type MPROP: MProperty
455 type MPROPDEF: MPropDef
457 private var class_coloring
: ClassColoring
458 private var coloration_result
: Map[MPROP, Int] = new HashMap[MPROP, Int]
460 init(class_coloring
: ClassColoring) do
461 self.class_coloring
= class_coloring
464 fun colorize
: Map[MPROP, Int] do
465 colorize_core_properties
466 colorize_crown_properties
467 return self.coloration_result
470 fun build_property_tables
: Map[MClass, Array[nullable MPROPDEF]] do
471 var tables
= new HashMap[MClass, Array[nullable MPROPDEF]]
472 var mclasses
= self.class_coloring
.coloration_result
.keys
473 for mclass
in mclasses
do
474 var table
= new Array[nullable MPROPDEF]
475 # first, fill table from parents by reverse linearization order
476 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
477 var lin
= self.class_coloring
.reverse_linearize
(parents
)
479 for mproperty
in self.properties
(parent
) do
480 var color
= self.coloration_result
[mproperty
]
481 if table
.length
<= color
then
482 for i
in [table
.length
.. color
[ do
486 for mpropdef
in mproperty
.mpropdefs
do
487 if mpropdef
.mclassdef
.mclass
== parent
then
488 table
[color
] = mpropdef
494 # then override with local properties
495 for mproperty
in self.properties
(mclass
) do
496 var color
= self.coloration_result
[mproperty
]
497 if table
.length
<= color
then
498 for i
in [table
.length
.. color
[ do
502 for mpropdef
in mproperty
.mpropdefs
do
503 if mpropdef
.mclassdef
.mclass
== mclass
then
504 table
[color
] = mpropdef
508 tables
[mclass
] = table
513 # Colorize properties of the core hierarchy
514 private fun colorize_core_properties
do
515 var mclasses
= self.class_coloring
.core
518 for mclass
in mclasses
do
519 var color
= min_color
521 # if the class is root, get the minimal color
522 if self.class_coloring
.parent_elements
(mclass
).length
== 0 then
523 colorize_elements
(self.properties
(mclass
), color
)
525 # check last color used by parents
526 color
= max_color
(color
, self.class_coloring
.parent_elements
(mclass
))
527 # check max color used in conflicts
528 if self.class_coloring
.conflicts_graph
.has_key
(mclass
) then
529 color
= max_color
(color
, self.class_coloring
.conflicts_graph
[mclass
])
533 colorize_elements
(self.properties
(mclass
), color
)
538 # Colorize properties of the crown hierarchy
539 private fun colorize_crown_properties
do
540 for mclass
in self.class_coloring
.crown
do
541 colorize_elements
(self.properties
(mclass
), max_color
(0, self.class_coloring
.parent_elements
(mclass
)))
545 # Colorize a collection of properties given a starting color
546 private fun colorize_elements
(elements
: Collection[MPROP], start_color
: Int) do
547 for element
in elements
do
548 if self.coloration_result
.has_key
(element
) then continue
549 self.coloration_result
[element
] = start_color
554 private fun max_color
(min_color
: Int, mclasses
: Collection[MClass]): Int do
555 var max_color
= min_color
557 for mclass
in mclasses
do
558 for mproperty
in self.properties
(mclass
) do
559 var color
= min_color
560 if self.coloration_result
.has_key
(mproperty
) then
561 color
= self.coloration_result
[mproperty
]
562 if color
>= max_color
then max_color
= color
+ 1
570 private var properties_cache
: Map[MClass, Set[MPROP]] = new HashMap[MClass, Set[MPROP]]
572 # All 'mproperties' associated to all 'mclassdefs' of the class
573 private fun properties
(mclass
: MClass): Set[MPROP] do
574 if not self.properties_cache
.has_key
(mclass
) then
575 var properties
= new HashSet[MPROP]
576 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
577 for parent
in parents
do
578 properties
.add_all
(self.properties
(parent
))
581 for mclassdef
in mclass
.mclassdefs
do
582 for mpropdef
in mclassdef
.mpropdefs
do
583 var mproperty
= mpropdef
.mproperty
584 if mproperty
isa MPROP then
585 properties
.add
(mproperty
)
589 self.properties_cache
[mclass
] = properties
591 return properties_cache
[mclass
]
597 super PropertyColoring
599 redef type MPROP: MMethod
600 redef type MPROPDEF: MMethodDef
601 init(class_coloring
: ClassColoring) do end
604 # MAttribute coloring
605 class AttributeColoring
606 super PropertyColoring
608 redef type MPROP: MAttribute
609 redef type MPROPDEF: MAttributeDef
610 init(class_coloring
: ClassColoring) do end
613 # MVirtualTypeProp coloring
615 super PropertyColoring
617 redef type MPROP: MVirtualTypeProp
618 redef type MPROPDEF: MVirtualTypeDef
619 init(class_coloring
: ClassColoring) do end
622 class NaiveVTColoring
625 init(class_coloring
: ClassColoring) do end
627 redef fun colorize
: Map[MPROP, Int] do
628 var mclasses
= new HashSet[MClass]
629 mclasses
.add_all
(self.class_coloring
.core
)
630 mclasses
.add_all
(self.class_coloring
.crown
)
633 for mclass
in mclasses
do
634 min_color
= max_color
(min_color
, mclasses
)
635 colorize_elements
(self.properties
(mclass
), min_color
)
637 return self.coloration_result
641 abstract class VTPerfectHashing
644 private var masks
: Map[MClass, Int] = new HashMap[MClass, Int]
646 init(class_coloring
: ClassColoring) do end
648 redef fun colorize
: Map[MPROP, Int] do
649 var mclasses
= new HashSet[MClass]
650 mclasses
.add_all
(self.class_coloring
.core
)
651 mclasses
.add_all
(self.class_coloring
.crown
)
652 for mclass
in mclasses
do
653 var vts
= self.properties
(mclass
)
655 if coloration_result
.has_key
(vt
) then continue
656 coloration_result
[vt
] = coloration_result
.length
+ 1
659 return self.coloration_result
662 fun compute_masks
: Map[MClass, Int] do
663 var mclasses
= new HashSet[MClass]
664 mclasses
.add_all
(self.class_coloring
.core
)
665 mclasses
.add_all
(self.class_coloring
.crown
)
666 for mclass
in mclasses
do
667 self.masks
[mclass
] = compute_mask
(self.properties
(mclass
))
672 private fun compute_mask
(vts
: Set[MPROP]): Int do
675 var used
= new List[Int]
677 var res
= op
(mask
, self.coloration_result
[vt
])
678 if used
.has
(res
) then
684 if used
.length
== vts
.length
then break
690 redef fun build_property_tables
do
691 var tables
= new HashMap[MClass, Array[nullable MPROPDEF]]
693 for mclass
in self.class_coloring
.coloration_result
.keys
do
694 var table
= new Array[nullable MPROPDEF]
695 # first, fill table from parents by reverse linearization order
696 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
697 var lin
= self.class_coloring
.reverse_linearize
(parents
)
699 for mproperty
in self.properties
(parent
) do
700 var color
= phash
(self.coloration_result
[mproperty
], masks
[mclass
])
701 if table
.length
<= color
then
702 for i
in [table
.length
.. color
[ do
706 for mpropdef
in mproperty
.mpropdefs
do
707 if mpropdef
.mclassdef
.mclass
== parent
then
708 table
[color
] = mpropdef
714 # then override with local properties
715 for mproperty
in self.properties
(mclass
) do
716 var color
= phash
(self.coloration_result
[mproperty
], masks
[mclass
])
717 if table
.length
<= color
then
718 for i
in [table
.length
.. color
[ do
722 for mpropdef
in mproperty
.mpropdefs
do
723 if mpropdef
.mclassdef
.mclass
== mclass
then
724 table
[color
] = mpropdef
728 tables
[mclass
] = table
733 private fun op
(mask
: Int, id
:Int): Int is abstract
734 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
738 class VTModPerfectHashing
739 super VTPerfectHashing
740 init(class_coloring
: ClassColoring) do end
741 redef fun op
(mask
, id
) do return mask
% id
744 class VTAndPerfectHashing
745 super VTPerfectHashing
746 init(class_coloring
: ClassColoring) do end
747 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
750 # MParameterType coloring
752 private var class_coloring
: ClassColoring
753 private var coloration_result
: Map[MParameterType, Int] = new HashMap[MParameterType, Int]
755 init(class_coloring
: ClassColoring) do
756 self.class_coloring
= class_coloring
759 fun colorize
: Map[MParameterType, Int] do
760 colorize_core_properties
761 colorize_crown_properties
762 return self.coloration_result
765 # Colorize properties of the core hierarchy
766 private fun colorize_core_properties
do
767 var mclasses
= self.class_coloring
.core
770 for mclass
in mclasses
do
771 var color
= min_color
773 # if the class is root, get the minimal color
774 if self.class_coloring
.parent_elements
(mclass
).length
== 0 then
775 colorize_elements
(self.fts
(mclass
), color
)
777 # check last color used by parents
778 color
= max_color
(color
, self.class_coloring
.parent_elements
(mclass
))
779 # check max color used in conflicts
780 if self.class_coloring
.conflicts_graph
.has_key
(mclass
) then
781 color
= max_color
(color
, self.class_coloring
.conflicts_graph
[mclass
])
784 colorize_elements
(self.fts
(mclass
), color
)
789 # Colorize properties of the crown hierarchy
790 private fun colorize_crown_properties
do
791 for mclass
in self.class_coloring
.crown
do
792 colorize_elements
(self.fts
(mclass
), max_color
(0, self.class_coloring
.parent_elements
(mclass
)))
796 # Colorize a collection of properties given a starting color
797 private fun colorize_elements
(elements
: Collection[MParameterType], start_color
: Int) do
798 for element
in elements
do
799 if self.coloration_result
.has_key
(element
) then continue
800 self.coloration_result
[element
] = start_color
805 private fun max_color
(min_color
: Int, mclasses
: Collection[MClass]): Int do
806 var max_color
= min_color
808 for mclass
in mclasses
do
809 for ft
in self.fts
(mclass
) do
810 var color
= min_color
811 if self.coloration_result
.has_key
(ft
) then
812 color
= self.coloration_result
[ft
]
813 if color
>= max_color
then max_color
= color
+ 1
821 private var fts_cache
: Map[MClass, Set[MParameterType]] = new HashMap[MClass, Set[MParameterType]]
823 private fun fts
(mclass
: MClass): Set[MParameterType] do
824 if not self.fts_cache
.has_key
(mclass
) then
825 var fts
= new HashSet[MParameterType]
826 var mclass_type
= mclass
.mclass_type
827 if mclass_type
isa MGenericType then
828 for ft
in mclass_type
.arguments
do
829 fts
.add
(ft
.as(MParameterType))
832 self.fts_cache
[mclass
] = fts
834 return fts_cache
[mclass
]
837 fun build_ft_tables
: Map[MClass, Array[nullable MParameterType]] do
838 var tables
= new HashMap[MClass, Array[nullable MParameterType]]
840 for mclass
in self.class_coloring
.coloration_result
.keys
do
841 var table
= new Array[nullable MParameterType]
843 # first, fill table from parents
844 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
845 for parent
in parents
do
846 for ft
in self.fts
(parent
) do
847 var color
= self.coloration_result
[ft
]
848 if table
.length
<= color
then
849 for i
in [table
.length
.. color
[ do
857 # then override with local properties
858 for ft
in self.fts
(mclass
) do
859 var color
= self.coloration_result
[ft
]
860 if table
.length
<= color
then
861 for i
in [table
.length
.. color
[ do
867 tables
[mclass
] = table
873 class NaiveFTColoring
876 init(class_coloring
: ClassColoring) do end
878 redef fun colorize
: Map[MParameterType, Int] do
879 var mclasses
= new HashSet[MClass]
880 mclasses
.add_all
(self.class_coloring
.core
)
881 mclasses
.add_all
(self.class_coloring
.crown
)
884 for mclass
in mclasses
do
885 min_color
= max_color
(min_color
, mclasses
)
886 colorize_elements
(self.fts
(mclass
), min_color
)
888 return self.coloration_result
892 abstract class FTPerfectHashing
895 private var masks
: Map[MClass, Int] = new HashMap[MClass, Int]
897 init(class_coloring
: ClassColoring) do end
899 redef fun colorize
: Map[MParameterType, Int] do
900 var mclasses
= new HashSet[MClass]
901 mclasses
.add_all
(self.class_coloring
.core
)
902 mclasses
.add_all
(self.class_coloring
.crown
)
903 for mclass
in mclasses
do
904 for ft
in self.fts
(mclass
) do
905 if coloration_result
.has_key
(ft
) then continue
906 coloration_result
[ft
] = coloration_result
.length
+ 1
909 return self.coloration_result
912 fun compute_masks
: Map[MClass, Int] do
913 var mclasses
= new HashSet[MClass]
914 mclasses
.add_all
(self.class_coloring
.core
)
915 mclasses
.add_all
(self.class_coloring
.crown
)
916 for mclass
in mclasses
do
917 var fts
= new HashSet[MParameterType]
918 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
919 for parent
in parents
do
920 fts
.add_all
(self.fts
(parent
))
922 fts
.add_all
(self.fts
(mclass
))
923 self.masks
[mclass
] = compute_mask
(fts
)
928 private fun compute_mask
(fts
: Set[MParameterType]): Int do
931 var used
= new List[Int]
933 var res
= op
(mask
, self.coloration_result
[ft
])
934 if used
.has
(res
) then
940 if used
.length
== fts
.length
then break
946 redef fun build_ft_tables
do
947 var tables
= new HashMap[MClass, Array[nullable MParameterType]]
949 for mclass
in self.class_coloring
.coloration_result
.keys
do
950 var table
= new Array[nullable MParameterType]
952 # first, fill table from parents
953 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
954 for parent
in parents
do
955 for ft
in self.fts
(parent
) do
956 var color
= phash
(self.coloration_result
[ft
], masks
[mclass
])
957 if table
.length
<= color
then
958 for i
in [table
.length
.. color
[ do
966 # then override with local properties
967 for ft
in self.fts
(mclass
) do
968 var color
= phash
(self.coloration_result
[ft
], masks
[mclass
])
969 if table
.length
<= color
then
970 for i
in [table
.length
.. color
[ do
976 tables
[mclass
] = table
981 private fun op
(mask
: Int, id
:Int): Int is abstract
982 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
985 class FTModPerfectHashing
986 super FTPerfectHashing
987 init(class_coloring
: ClassColoring) do end
988 redef fun op
(mask
, id
) do return mask
% id
991 class FTAndPerfectHashing
992 super FTPerfectHashing
993 init(class_coloring
: ClassColoring) do end
994 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
997 # Live Entries coloring
998 class LiveEntryColoring
1000 private var coloration_result
: Map[MType, Int] = new HashMap[MType, Int]
1001 private var conflicts_graph_cache
: nullable HashMap[MType, Set[MType]]
1002 var livetypes_tables_sizes
: nullable Map[MClass, Array[Int]]
1006 fun colorize
(elements
: Collection[MType]): Map[MType, Int] do
1008 build_conflicts_graph
(elements
)
1011 colorize_elements
(elements
)
1013 return coloration_result
1017 fun build_livetype_tables
(mtypes
: Set[MType]): Map[MClass, Array[nullable Object]] do
1018 var livetypes_tables
= new HashMap[MClass, Array[nullable Object]]
1019 self.livetypes_tables_sizes
= new HashMap[MClass, Array[Int]]
1021 for mtype
in mtypes
do
1022 if mtype
isa MGenericType then
1023 var table
: Array[nullable Object]
1024 var sizes
: Array[Int]
1025 if livetypes_tables
.has_key
(mtype
.mclass
) then
1026 table
= livetypes_tables
[mtype
.mclass
]
1028 table
= new Array[nullable Object]
1029 livetypes_tables
[mtype
.mclass
] = table
1031 if livetypes_tables_sizes
.has_key
(mtype
.mclass
) then
1032 sizes
= livetypes_tables_sizes
[mtype
.mclass
]
1034 sizes
= new Array[Int]
1035 livetypes_tables_sizes
[mtype
.mclass
] = sizes
1037 build_livetype_table
(mtype
, 0, table
, sizes
)
1041 return livetypes_tables
1044 # Build live gentype table recursively
1045 private fun build_livetype_table
(mtype
: MGenericType, current_rank
: Int, table
: Array[nullable Object], sizes
: Array[Int]) do
1046 var ft
= mtype
.arguments
[current_rank
]
1047 if not self.coloration_result
.has_key
(ft
) then return
1048 var color
= self.coloration_result
[ft
]
1050 if current_rank
>= sizes
.length
then
1051 sizes
[current_rank
] = color
+ 1
1052 else if color
>= sizes
[current_rank
] then
1053 sizes
[current_rank
] = color
+ 1
1056 if color
> table
.length
then
1057 for i
in [table
.length
.. color
[ do table
[i
] = null
1060 if current_rank
== mtype
.arguments
.length
- 1 then
1061 table
[color
] = mtype
1063 var ft_table
: Array[nullable Object]
1064 if color
< table
.length
and table
[color
] != null then
1065 ft_table
= table
[color
].as(Array[nullable Object])
1067 ft_table
= new Array[nullable Object]
1069 table
[color
] = ft_table
1070 build_livetype_table
(mtype
, current_rank
+ 1, ft_table
, sizes
)
1074 # Colorize a collection of elements
1075 fun colorize_elements
(elements
: Collection[MType]) do
1078 for element
in elements
do
1079 var color
= min_color
1080 while not self.is_color_free
(element
, color
) do
1083 coloration_result
[element
] = color
1088 # Check if a related element to the element already use the color
1089 private fun is_color_free
(element
: MType, color
: Int): Bool do
1090 if conflicts_graph
.has_key
(element
) then
1091 for st
in conflicts_graph
[element
] do
1092 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
1098 # look for types in the same generic signatures
1099 private fun build_conflicts_graph
(elements
: Collection[MType]) do
1100 # regroup types by classes
1101 var genclasses
= new HashMap[MClass, Set[MType]]
1102 for e
in elements
do
1103 if e
isa MGenericType then
1104 if not genclasses
.has_key
(e
.mclass
) then
1105 genclasses
[e
.mclass
] = new HashSet[MType]
1107 genclasses
[e
.mclass
].add
(e
)
1112 self.conflicts_graph_cache
= new HashMap[MType, Set[MType]]
1113 for mclass
, mtypes
in genclasses
do
1115 for rank
in [0..mclass
.arity
[ do
1116 # for each live type
1117 for mtype
in mtypes
do
1118 var mclasstype
: MClassType
1119 if mtype
isa MNullableType then
1120 mclasstype
= mtype
.mtype
.as(MClassType)
1122 mclasstype
= mtype
.as(MClassType)
1124 var ft
= mclasstype
.arguments
[rank
]
1125 for otype
in mtypes
do
1126 if mtype
== otype
then continue
1127 var oclasstype
: MClassType
1128 if otype
isa MNullableType then
1129 oclasstype
= otype
.mtype
.as(MClassType)
1131 oclasstype
= otype
.as(MClassType)
1133 var oft
= oclasstype
.arguments
[rank
]
1134 self.add_conflict
(ft
, oft
)
1141 private fun add_conflict
(mtype
: MType, otype
: MType) do
1142 if mtype
== otype
then return
1143 if not self.conflicts_graph_cache
.has_key
(mtype
) then self.conflicts_graph_cache
[mtype
] = new HashSet[MType]
1144 self.conflicts_graph_cache
[mtype
].add
(otype
)
1145 if not self.conflicts_graph_cache
.has_key
(otype
) then self.conflicts_graph_cache
[otype
] = new HashSet[MType]
1146 self.conflicts_graph_cache
[otype
].add
(mtype
)
1148 private fun conflicts_graph
: Map[MType, Set[MType]] do return conflicts_graph_cache
.as(not null)
1151 class NaiveLiveEntryColoring
1152 super LiveEntryColoring
1156 redef fun colorize_elements
(elements
: Collection[MType]) do
1158 for element
in elements
do
1159 coloration_result
[element
] = color
1165 # live unanchored coloring
1166 class UnanchoredTypeColoring
1168 private var coloration_result
: Map[MType, Int] = new HashMap[MType, Int]
1169 private var conflicts_graph
: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
1173 fun colorize
(elements
: Map[MClassType, Set[MType]]): Map[MType, Int] do
1174 build_conflicts_graph
(elements
)
1175 colorize_elements
(elements
)
1176 return coloration_result
1179 fun build_tables
(elements
: Map[MClassType, Set[MType]]): Map[MClassType, Array[nullable MType]] do
1180 var tables
= new HashMap[MClassType, Array[nullable MType]]
1182 for mclasstype
, mtypes
in elements
do
1183 var table
= new Array[nullable MType]
1184 for mtype
in mtypes
do
1185 var color
= self.coloration_result
[mtype
]
1186 if table
.length
<= color
then
1187 for i
in [table
.length
.. color
[ do
1191 table
[color
] = mtype
1193 tables
[mclasstype
] = table
1198 # Colorize a collection of elements
1199 fun colorize_elements
(elements
: Map[MClassType, Set[MType]]) do
1201 for mclasstype
, mclasstypes
in elements
do
1202 for element
in mclasstypes
do
1203 if self.coloration_result
.has_key
(element
) then continue
1204 var color
= min_color
1205 while not self.is_color_free
(element
, color
) do
1208 coloration_result
[element
] = color
1214 # Check if a related element to the element already use the color
1215 private fun is_color_free
(element
: MType, color
: Int): Bool do
1216 if conflicts_graph
.has_key
(element
) then
1217 for st
in conflicts_graph
[element
] do
1218 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
1224 # look for unanchored types generated by the same type
1225 private fun build_conflicts_graph
(elements
: Map[MClassType, Set[MType]]) do
1226 for mclasstype
, mtypes
in elements
do
1227 for mtype
in mtypes
do
1228 for otype
in mtypes
do
1229 if otype
== mtype
then continue
1230 self.add_conflict
(mtype
, otype
)
1236 private fun add_conflict
(mtype
: MType, otype
: MType) do
1237 if mtype
== otype
then return
1238 if not self.conflicts_graph
.has_key
(mtype
) then self.conflicts_graph
[mtype
] = new HashSet[MType]
1239 self.conflicts_graph
[mtype
].add
(otype
)
1240 if not self.conflicts_graph
.has_key
(otype
) then self.conflicts_graph
[otype
] = new HashSet[MType]
1241 self.conflicts_graph
[otype
].add
(mtype
)
1245 class NaiveUnanchoredTypeColoring
1246 super UnanchoredTypeColoring
1250 redef fun colorize_elements
(elements
: Map[MClassType, Set[MType]]) do
1252 for mclasstype
, mclasstypes
in elements
do
1253 for element
in mclasstypes
do
1254 coloration_result
[element
] = color
1261 abstract class UnanchoredTypePerfectHashing
1262 super NaiveUnanchoredTypeColoring
1264 private var masks
: Map[MClassType, Int] = new HashMap[MClassType, Int]
1268 redef fun colorize_elements
(elements
: Map[MClassType, Set[MType]]) do
1270 for mclasstype
, mclasstypes
in elements
do
1271 for element
in mclasstypes
do
1272 coloration_result
[element
] = color
1278 fun compute_masks
(elements
: Map[MClassType, Set[MType]]): Map[MClassType, Int] do
1279 for mclasstype
, mtypes
in elements
do
1280 self.masks
[mclasstype
] = compute_mask
(mtypes
)
1285 private fun compute_mask
(mtypes
: Set[MType]): Int do
1288 var used
= new List[Int]
1289 for mtype
in mtypes
do
1290 var res
= op
(mask
, self.coloration_result
[mtype
])
1291 if used
.has
(res
) then
1297 if used
.length
== mtypes
.length
then break
1303 redef fun build_tables
(elements
: Map[MClassType, Set[MType]]): Map[MClassType, Array[nullable MType]] do
1304 var tables
= new HashMap[MClassType, Array[nullable MType]]
1306 for mclasstype
, mtypes
in elements
do
1307 var table
= new Array[nullable MType]
1308 for mtype
in mtypes
do
1309 var color
= phash
(self.coloration_result
[mtype
], masks
[mclasstype
])
1310 if table
.length
<= color
then
1311 for i
in [table
.length
.. color
[ do
1315 table
[color
] = mtype
1317 tables
[mclasstype
] = table
1322 private fun op
(mask
: Int, id
:Int): Int is abstract
1323 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
1326 class UnanchoredTypeModPerfectHashing
1327 super UnanchoredTypePerfectHashing
1329 redef fun op
(mask
, id
) do return mask
% id
1332 class UnanchoredTypeAndPerfectHashing
1333 super UnanchoredTypePerfectHashing
1335 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
1341 redef class HashSet[E
]
1342 init from
(elements
: Collection[E
]) do
1344 self.add_all
(elements
)
1348 redef class Array[E
]
1349 init from
(elements
: Collection[E
]) do
1351 self.add_all
(elements
)
1354 # Return a new Array with the elements only contened in 'self' and not in 'o'
1355 fun -(o
: Array[E
]): Array[E
] do
1356 var res
= new Array[E
]
1357 for e
in self do if not o
.has
(e
) then res
.add
(e
)
1364 # Return a linearization of a set of mtypes
1365 private fun linearize_mtypes
(mtypes
: Set[MType]): Array[MType] do
1366 var lin
= new Array[MType].from
(mtypes
)
1367 var sorter
= new TypeSorter(self)
1372 # Return a reverse linearization of a set of mtypes
1373 private fun reverse_linearize_mtypes
(mtypes
: Set[MType]): Array[MType] do
1374 var lin
= new Array[MType].from
(mtypes
)
1375 var sorter
= new ReverseTypeSorter(self)
1380 # Return super types of a `mtype` in `self`
1381 private fun super_mtypes
(mtype
: MType, mtypes
: Set[MType]): Set[MType] do
1382 if not self.super_mtypes_cache
.has_key
(mtype
) then
1383 var supers
= new HashSet[MType]
1384 for otype
in mtypes
do
1385 if otype
== mtype
then continue
1386 if mtype
.is_subtype
(self, null, otype
) then
1390 self.super_mtypes_cache
[mtype
] = supers
1392 return self.super_mtypes_cache
[mtype
]
1395 private var super_mtypes_cache
: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
1397 # Return all sub mtypes (directs and indirects) of a `mtype` in `self`
1398 private fun sub_mtypes
(mtype
: MType, mtypes
: Set[MType]): Set[MType] do
1399 if not self.sub_mtypes_cache
.has_key
(mtype
) then
1400 var subs
= new HashSet[MType]
1401 for otype
in mtypes
do
1402 if otype
== mtype
then continue
1403 if otype
.is_subtype
(self, null, mtype
) then
1407 self.sub_mtypes_cache
[mtype
] = subs
1409 return self.sub_mtypes_cache
[mtype
]
1412 private var sub_mtypes_cache
: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
1414 # Return a linearization of a set of mclasses
1415 private fun linearize_mclasses
(mclasses
: Set[MClass]): Array[MClass] do
1416 var lin
= new Array[MClass].from
(mclasses
)
1417 var sorter
= new ClassSorter(self)
1422 # Return a reverse linearization of a set of mtypes
1423 private fun reverse_linearize_mclasses
(mclasses
: Set[MClass]): Array[MClass] do
1424 var lin
= new Array[MClass].from
(mclasses
)
1425 var sorter
= new ReverseClassSorter(self)
1430 # Return all super mclasses (directs and indirects) of a `mclass` in `self`
1431 private fun super_mclasses
(mclass
: MClass): Set[MClass] do
1432 if not self.super_mclasses_cache
.has_key
(mclass
) then
1433 var supers
= new HashSet[MClass]
1434 if self.flatten_mclass_hierarchy
.has
(mclass
) then
1435 for sup
in self.flatten_mclass_hierarchy
[mclass
].greaters
do
1436 if sup
== mclass
then continue
1440 self.super_mclasses_cache
[mclass
] = supers
1442 return self.super_mclasses_cache
[mclass
]
1445 private var super_mclasses_cache
: Map[MClass, Set[MClass]] = new HashMap[MClass, Set[MClass]]
1447 # Return all parents of a `mclass` in `self`
1448 private fun parent_mclasses
(mclass
: MClass): Set[MClass] do
1449 if not self.parent_mclasses_cache
.has_key
(mclass
) then
1450 var parents
= new HashSet[MClass]
1451 if self.flatten_mclass_hierarchy
.has
(mclass
) then
1452 for sup
in self.flatten_mclass_hierarchy
[mclass
].direct_greaters
do
1453 if sup
== mclass
then continue
1457 self.parent_mclasses_cache
[mclass
] = parents
1459 return self.parent_mclasses_cache
[mclass
]
1462 private var parent_mclasses_cache
: Map[MClass, Set[MClass]] = new HashMap[MClass, Set[MClass]]
1464 # Return all sub mclasses (directs and indirects) of a `mclass` in `self`
1465 private fun sub_mclasses
(mclass
: MClass): Set[MClass] do
1466 if not self.sub_mclasses_cache
.has_key
(mclass
) then
1467 var subs
= new HashSet[MClass]
1468 if self.flatten_mclass_hierarchy
.has
(mclass
) then
1469 for sub
in self.flatten_mclass_hierarchy
[mclass
].smallers
do
1470 if sub
== mclass
then continue
1474 self.sub_mclasses_cache
[mclass
] = subs
1476 return self.sub_mclasses_cache
[mclass
]
1479 private var sub_mclasses_cache
: Map[MClass, Set[MClass]] = new HashMap[MClass, Set[MClass]]
1481 # All 'mproperties' associated to all 'mclassdefs' of `mclass`
1482 private fun properties
(mclass
: MClass): Set[MProperty] do
1483 if not self.properties_cache
.has_key
(mclass
) then
1484 var properties
= new HashSet[MProperty]
1485 var parents
= self.super_mclasses
(mclass
)
1486 for parent
in parents
do
1487 properties
.add_all
(self.properties
(parent
))
1490 for mclassdef
in mclass
.mclassdefs
do
1491 for mpropdef
in mclassdef
.mpropdefs
do
1492 properties
.add
(mpropdef
.mproperty
)
1495 self.properties_cache
[mclass
] = properties
1497 return properties_cache
[mclass
]
1500 private var properties_cache
: Map[MClass, Set[MProperty]] = new HashMap[MClass, Set[MProperty]]
1503 # A sorter for linearize list of types
1505 super AbstractSorter[MType]
1507 private var mmodule
: MModule
1509 init(mmodule
: MModule) do self.mmodule
= mmodule
1511 redef fun compare
(a
, b
) do
1514 else if a
.is_subtype
(self.mmodule
, null, b
) then
1521 # A sorter for reverse linearization
1522 class ReverseTypeSorter
1525 init(mmodule
: MModule) do end
1527 redef fun compare
(a
, b
) do
1530 else if a
.is_subtype
(self.mmodule
, null, b
) then
1537 # A sorter for linearize list of classes
1538 private class ClassSorter
1539 super AbstractSorter[MClass]
1541 var mmodule
: MModule
1543 redef fun compare
(a
, b
) do
1546 else if self.mmodule
.flatten_mclass_hierarchy
.has
(a
) and self.mmodule
.flatten_mclass_hierarchy
[a
].greaters
.has
(b
) then
1553 # A sorter for reverse linearization
1554 private class ReverseClassSorter
1555 super AbstractSorter[MClass]
1557 var mmodule
: MModule
1559 redef fun compare
(a
, b
) do
1562 else if self.mmodule
.flatten_mclass_hierarchy
.has
(a
) and self.mmodule
.flatten_mclass_hierarchy
[a
].greaters
.has
(b
) then