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]]
38 # Unic ids or each MClass
39 var ids
: Map[MClass, Int] = new HashMap[MClass, Int]
40 # Fixed positions of each MClass in all tables
41 var pos
: Map[MClass, Int] = new HashMap[MClass, Int]
46 # Masks used by hash function
47 var masks
: Map[MClass, Int] = new HashMap[MClass, Int]
48 # Positions of each MClass for each tables
49 var hashes
: Map[MClass, Map[MClass, Int]] = new HashMap[MClass, Map[MClass, Int]]
54 abstract class TypeLayoutBuilder
56 type LAYOUT: TypeLayout
58 private var mmodule
: MModule
59 init(mmodule
: MModule) do self.mmodule
= mmodule
61 # Compute mtypes ids and position
62 fun build_layout
(mtypes
: Set[MType]): LAYOUT is abstract
64 # Give each MType a unic id using a descending linearization of the `mtypes` set
65 private fun compute_ids
(mtypes
: Set[MType]): Map[MType, Int] do
66 var ids
= new HashMap[MType, Int]
67 var lin
= self.mmodule
.reverse_linearize_mtypes
(mtypes
)
69 ids
[mtype
] = ids
.length
75 # Layout builder for MType using Binary Matrix (BM)
76 class BMTypeLayoutBuilder
77 super TypeLayoutBuilder
79 init(mmodule
: MModule) do super
81 # Compute mtypes ids and position using BM
82 redef fun build_layout
(mtypes
: Set[MType]): TypeLayout do
83 var result
= new TypeLayout
84 result
.ids
= self.compute_ids
(mtypes
)
85 result
.pos
= result
.ids
90 # Layout builder for MType using Coloring (CL)
91 class CLTypeLayoutBuilder
92 super TypeLayoutBuilder
94 private var colorer
: MTypeColorer
96 init(mmodule
: MModule) do
98 self.colorer
= new MTypeColorer(mmodule
)
101 # Compute mtypes ids and position using BM
102 redef fun build_layout
(mtypes
) do
103 var result
= new TypeLayout
104 result
.ids
= self.compute_ids
(mtypes
)
105 result
.pos
= self.colorer
.colorize
(mtypes
)
110 # Layout builder for MType using Perfect Hashing (PH)
111 class PHTypeLayoutBuilder
112 super TypeLayoutBuilder
114 redef type LAYOUT: PHTypeLayout
116 private var hasher
: MTypeHasher
118 init(mmodule
: MModule, operator
: PHOperator) do
120 self.hasher
= new MTypeHasher(mmodule
, operator
)
123 # Compute mtypes ids and position using BM
124 redef fun build_layout
(mtypes
) do
125 var result
= new PHTypeLayout
126 result
.ids
= self.compute_ids
(mtypes
)
127 result
.masks
= self.hasher
.compute_masks
(mtypes
, result
.ids
)
128 result
.hashes
= self.hasher
.compute_hashes
(mtypes
, result
.ids
, result
.masks
)
132 # Ids start from 1 instead of 0
133 redef fun compute_ids
(mtypes
) do
134 var ids
= new HashMap[MType, Int]
135 var lin
= self.mmodule
.reverse_linearize_mtypes
(mtypes
)
137 ids
[mtype
] = ids
.length
+ 1
143 abstract class ClassLayoutBuilder
145 type LAYOUT: ClassLayout
147 private var mmodule
: MModule
148 init(mmodule
: MModule) do self.mmodule
= mmodule
150 # Compute mclasses ids and position
151 fun build_layout
(mclasses
: Set[MClass]): LAYOUT is abstract
153 # Give each MClass a unic id using a descending linearization of the `mclasses` set
154 private fun compute_ids
(mclasses
: Set[MClass]): Map[MClass, Int] do
155 var ids
= new HashMap[MClass, Int]
156 var lin
= self.mmodule
.reverse_linearize_mclasses
(mclasses
)
158 ids
[mclass
] = ids
.length
164 # Layout builder for MClass using Binary Matrix (BM)
165 class BMClassLayoutBuilder
166 super ClassLayoutBuilder
168 init(mmodule
: MModule) do super
170 # Compute mclasses ids and position using BM
171 redef fun build_layout
(mclasses
: Set[MClass]): LAYOUT do
172 var result
= new ClassLayout
173 result
.ids
= self.compute_ids
(mclasses
)
174 result
.pos
= result
.ids
179 # Layout builder for MClass using Coloring (CL)
180 class CLClassLayoutBuilder
181 super ClassLayoutBuilder
183 private var colorer
: MClassColorer
185 init(mmodule
: MModule) do
187 self.colorer
= new MClassColorer(mmodule
)
190 # Compute mclasses ids and position using BM
191 redef fun build_layout
(mclasses
) do
192 var result
= new ClassLayout
193 result
.ids
= self.compute_ids
(mclasses
)
194 result
.pos
= self.colorer
.colorize
(mclasses
)
199 # Layout builder for MClass using Perfect Hashing (PH)
200 class PHClassLayoutBuilder
201 super ClassLayoutBuilder
203 redef type LAYOUT: PHClassLayout
205 private var hasher
: MClassHasher
207 init(mmodule
: MModule, operator
: PHOperator) do
209 self.hasher
= new MClassHasher(mmodule
, operator
)
212 # Compute mclasses ids and position using BM
213 redef fun build_layout
(mclasses
) do
214 var result
= new PHClassLayout
215 result
.ids
= self.compute_ids
(mclasses
)
216 result
.masks
= self.hasher
.compute_masks
(mclasses
, result
.ids
)
217 result
.hashes
= self.hasher
.compute_hashes
(mclasses
, result
.ids
, result
.masks
)
221 # Ids start from 1 instead of 0
222 redef fun compute_ids
(mclasses
) do
223 var ids
= new HashMap[MClass, Int]
224 var lin
= self.mmodule
.reverse_linearize_mclasses
(mclasses
)
226 ids
[mclass
] = ids
.length
+ 1
234 abstract class AbstractColorer[E
: Object]
236 private var core
: Set[E
] = new HashSet[E
]
237 private var crown
: Set[E
] = new HashSet[E
]
238 private var border
: Set[E
] = new HashSet[E
]
240 private var coloration_result
: Map[E
, Int] = new HashMap[E
, Int]
244 fun colorize
(elements
: Set[E
]): Map[E
, Int] do
245 tag_elements
(elements
)
246 build_conflicts_graph
(elements
)
247 colorize_elements
(core
)
248 colorize_elements
(border
)
249 colorize_elements
(crown
)
250 return coloration_result
253 # Colorize a collection of elements
254 private fun colorize_elements
(elements
: Set[E
]) do
257 var lin
= reverse_linearize
(elements
)
258 for element
in lin
do
259 var color
= min_color
260 while not self.is_color_free
(element
, elements
, color
) do
263 coloration_result
[element
] = color
268 # Check if a related element to the element already use the color
269 private fun is_color_free
(element
: E
, elements
: Set[E
], color
: Int): Bool do
270 if conflicts_graph
.has_key
(element
) then
271 for st
in conflicts_graph
[element
] do
272 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
275 for st
in self.super_elements
(element
, elements
) do
276 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
281 # Tag elements as core, crown or border
282 private fun tag_elements
(elements
: Set[E
]) do
283 for element
in elements
do
284 # Check if sub elements are all in single inheritance
285 var all_subelements_si
= true
286 for subelem
in self.sub_elements
(element
, elements
) do
287 if self.is_element_mi
(subelem
, elements
) then
288 all_subelements_si
= false
293 # Tag as core, crown or border
294 if self.is_element_mi
(element
, elements
) then
295 core
.add_all
(self.super_elements
(element
, elements
))
297 if all_subelements_si
then
300 else if not all_subelements_si
then
301 core
.add_all
(self.super_elements
(element
, elements
))
309 # Conflicts graph of elements hierarchy (two types are in conflict if they have common subelements)
310 private fun build_conflicts_graph
(elements
: Set[E
]) do
311 self.conflicts_graph
= new HashMap[E
, HashSet[E
]]
312 var core
= reverse_linearize
(self.core
)
314 for i
in self.linear_extension
(t
, elements
) do
315 if t
== i
then continue
317 var lin_i
= self.linear_extension
(i
, elements
)
319 for j
in self.linear_extension
(t
, elements
) do
320 if i
== j
or j
== t
then continue
321 var lin_j
= self.linear_extension
(j
, elements
)
323 var d_ij
= lin_i
- lin_j
324 var d_ji
= lin_j
- lin_i
327 if not conflicts_graph
.has_key
(ed1
) then conflicts_graph
[ed1
] = new HashSet[E
]
328 # add ed1 x ed2 to conflicts graph
329 for ed2
in d_ji
do conflicts_graph
[ed1
].add
(ed2
)
332 if not conflicts_graph
.has_key
(ed1
) then conflicts_graph
[ed1
] = new HashSet[E
]
333 # add ed1 x ed2 to conflicts graph
334 for ed2
in d_ji
do conflicts_graph
[ed1
].add
(ed2
)
341 private var conflicts_graph
: nullable HashMap[E
, Set[E
]]
343 # cache for linear_extensions
344 private var linear_extensions_cache
: Map[E
, Array[E
]] = new HashMap[E
, Array[E
]]
346 # Return a linear_extension of super_elements of the element
347 private fun linear_extension
(element
: E
, elements
: Set[E
]): Array[E
] do
348 if not self.linear_extensions_cache
.has_key
(element
) then
349 var supers
= new HashSet[E
]
351 supers
.add_all
(self.super_elements
(element
, elements
))
352 self.linear_extensions_cache
[element
] = self.linearize
(supers
)
354 return self.linear_extensions_cache
[element
]
357 private fun super_elements
(element
: E
, elements
: Set[E
]): Set[E
] is abstract
358 private fun sub_elements
(element
: E
, elements
: Set[E
]): Set[E
] is abstract
359 private fun is_element_mi
(element
: E
, elements
: Set[E
]): Bool is abstract
360 private fun linearize
(elements
: Set[E
]): Array[E
] is abstract
361 private fun reverse_linearize
(elements
: Set[E
]): Array[E
] is abstract
365 private class MTypeColorer
366 super AbstractColorer[MType]
370 init(mmodule
: MModule) do self.mmodule
= mmodule
372 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mtypes
(element
, elements
)
373 redef fun is_element_mi
(element
, elements
) do return self.super_elements
(element
, elements
).length
> 1
374 redef fun sub_elements
(element
, elements
) do do return self.mmodule
.sub_mtypes
(element
, elements
)
375 redef fun linearize
(elements
) do return self.mmodule
.linearize_mtypes
(elements
)
376 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mtypes
(elements
)
380 private class MClassColorer
381 super AbstractColorer[MClass]
383 private var mmodule
: MModule
385 init(mmodule
: MModule) do self.mmodule
= mmodule
387 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mclasses
(element
)
388 fun parent_elements
(element
: MClass): Set[MClass] do return self.mmodule
.parent_mclasses
(element
)
389 redef fun is_element_mi
(element
, elements
) do return self.parent_elements
(element
).length
> 1
390 redef fun sub_elements
(element
, elements
) do do return self.mmodule
.sub_mclasses
(element
)
391 redef fun linearize
(elements
) do return self.mmodule
.linearize_mclasses
(elements
)
392 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mclasses
(elements
)
397 # Abstract Perfect Hashing
398 private abstract class AbstractHasher[E
: Object]
400 var operator
: PHOperator
402 init(operator
: PHOperator) do self.operator
= operator
404 fun compute_masks
(elements
: Set[E
], ids
: Map[E
, Int]): Map[E
, Int] do
405 var masks
= new HashMap[E
, Int]
406 for element
in elements
do
407 var supers
= new HashSet[E
]
408 supers
.add_all
(self.super_elements
(element
, elements
))
410 masks
[element
] = compute_mask
(supers
, ids
)
415 fun compute_mask
(supers
: Set[E
], ids
: Map[E
, Int]): Int do
418 var used
= new List[Int]
420 var res
= operator
.op
(mask
, ids
[sup
])
421 if used
.has
(res
) then
427 if used
.length
== supers
.length
then break
433 fun compute_hashes
(elements
: Set[E
], ids
: Map[E
, Int], masks
: Map[E
, Int]): Map[E
, Map[E
, Int]] do
434 var hashes
= new HashMap[E
, Map[E
, Int]]
435 for element
in elements
do
436 var supers
= new HashSet[E
]
437 supers
.add_all
(self.super_elements
(element
, elements
))
439 var inhashes
= new HashMap[E
, Int]
440 var mask
= masks
[element
]
442 inhashes
[sup
] = operator
.op
(mask
, ids
[sup
])
444 hashes
[element
] = inhashes
449 fun super_elements
(element
: E
, elements
: Set[E
]): Set[E
] is abstract
452 # Abstract operator used for perfect hashing
453 abstract class PHOperator
454 fun op
(mask
: Int, id
:Int): Int is abstract
457 # Hashing using modulo (MOD) operator
462 redef fun op
(mask
, id
) do return mask
% id
465 # Hashing using binary and (AND) operator
470 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
473 # MType Perfect Hashing
474 private class MTypeHasher
475 super AbstractHasher[MType]
479 init(mmodule
: MModule, operator
: PHOperator) do
481 self.mmodule
= mmodule
484 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mtypes
(element
, elements
)
487 # MClass Perfect Hashing
488 private class MClassHasher
489 super AbstractHasher[MClass]
491 private var mmodule
: MModule
493 init(mmodule
: MModule, operator
: PHOperator) do
495 self.mmodule
= mmodule
498 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mclasses
(element
)
503 super AbstractColorer[MClass]
507 private var mmodule
: MModule
510 private var super_elements_cache
: Map[T
, Set[T
]] = new HashMap[T
, Set[T
]]
511 private var parent_elements_cache
: Map[T
, Set[T
]] = new HashMap[T
, Set[T
]]
512 private var sub_elements_cache
: Map[T
, Set[T
]] = new HashMap[T
, Set[T
]]
514 init(mainmodule
: MModule) do self.mmodule
= mainmodule
516 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mclasses
(element
)
517 fun parent_elements
(element
: MClass): Set[MClass] do return self.mmodule
.parent_mclasses
(element
)
518 redef fun is_element_mi
(element
, elements
) do return self.parent_elements
(element
).length
> 1
519 redef fun sub_elements
(element
, elements
) do do return self.mmodule
.sub_mclasses
(element
)
520 redef fun linearize
(elements
) do return self.mmodule
.linearize_mclasses
(elements
)
521 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mclasses
(elements
)
525 class PropertyColoring
527 type MPROP: MProperty
528 type MPROPDEF: MPropDef
530 private var mmodule
: MModule
531 private var class_coloring
: ClassColoring
532 private var coloration_result
: Map[MPROP, Int] = new HashMap[MPROP, Int]
534 init(mmodule
: MModule, class_coloring
: ClassColoring) do
535 self.mmodule
= mmodule
536 self.class_coloring
= class_coloring
539 fun colorize
: Map[MPROP, Int] do
540 colorize_core_properties
541 colorize_crown_properties
542 return self.coloration_result
545 fun build_property_tables
: Map[MClass, Array[nullable MPROPDEF]] do
546 var tables
= new HashMap[MClass, Array[nullable MPROPDEF]]
547 var mclasses
= self.class_coloring
.coloration_result
.keys
548 for mclass
in mclasses
do
549 var table
= new Array[nullable MPROPDEF]
550 # first, fill table from parents by reverse linearization order
551 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
552 var lin
= self.class_coloring
.reverse_linearize
(parents
)
554 for mproperty
in self.properties
(parent
) do
555 var color
= self.coloration_result
[mproperty
]
556 if table
.length
<= color
then
557 for i
in [table
.length
.. color
[ do
561 for mpropdef
in mproperty
.mpropdefs
do
562 if mpropdef
.mclassdef
.mclass
== parent
then
563 table
[color
] = mpropdef
569 # then override with local properties
570 for mproperty
in self.properties
(mclass
) do
571 var color
= self.coloration_result
[mproperty
]
572 if table
.length
<= color
then
573 for i
in [table
.length
.. color
[ do
577 for mpropdef
in mproperty
.mpropdefs
do
578 if mpropdef
.mclassdef
.mclass
== mclass
then
579 table
[color
] = mpropdef
583 tables
[mclass
] = table
588 # Colorize properties of the core hierarchy
589 private fun colorize_core_properties
do
590 var mclasses
= self.class_coloring
.core
593 for mclass
in mclasses
do
594 var color
= min_color
596 # if the class is root, get the minimal color
597 if self.class_coloring
.parent_elements
(mclass
).length
== 0 then
598 colorize_elements
(self.properties
(mclass
), color
)
600 # check last color used by parents
601 color
= max_color
(color
, self.class_coloring
.parent_elements
(mclass
))
602 # check max color used in conflicts
603 if self.class_coloring
.conflicts_graph
.has_key
(mclass
) then
604 color
= max_color
(color
, self.class_coloring
.conflicts_graph
[mclass
])
608 colorize_elements
(self.properties
(mclass
), color
)
613 # Colorize properties of the crown hierarchy
614 private fun colorize_crown_properties
do
615 for mclass
in self.class_coloring
.crown
do
616 colorize_elements
(self.properties
(mclass
), max_color
(0, self.class_coloring
.parent_elements
(mclass
)))
620 # Colorize a collection of properties given a starting color
621 private fun colorize_elements
(elements
: Collection[MPROP], start_color
: Int) do
622 for element
in elements
do
623 if self.coloration_result
.has_key
(element
) then continue
624 self.coloration_result
[element
] = start_color
629 private fun max_color
(min_color
: Int, mclasses
: Collection[MClass]): Int do
630 var max_color
= min_color
632 for mclass
in mclasses
do
633 for mproperty
in self.properties
(mclass
) do
634 var color
= min_color
635 if self.coloration_result
.has_key
(mproperty
) then
636 color
= self.coloration_result
[mproperty
]
637 if color
>= max_color
then max_color
= color
+ 1
644 # All 'mproperties' associated to all 'mclassdefs' of the class
645 private fun properties
(mclass
: MClass): Set[MPROP] do
646 var properties
= new HashSet[MPROP]
647 for mprop
in self.mmodule
.properties
(mclass
) do
648 if mprop
isa MPROP then properties
.add
(mprop
)
656 super PropertyColoring
658 redef type MPROP: MMethod
659 redef type MPROPDEF: MMethodDef
660 init(mmodule
: MModule, class_coloring
: ClassColoring) do super
663 # MAttribute coloring
664 class AttributeColoring
665 super PropertyColoring
667 redef type MPROP: MAttribute
668 redef type MPROPDEF: MAttributeDef
669 init(mmodule
: MModule, class_coloring
: ClassColoring) do super
672 # MVirtualTypeProp coloring
674 super PropertyColoring
676 redef type MPROP: MVirtualTypeProp
677 redef type MPROPDEF: MVirtualTypeDef
678 init(mmodule
: MModule, class_coloring
: ClassColoring) do super
681 class NaiveVTColoring
684 init(mmodule
: MModule, class_coloring
: ClassColoring) do super
686 redef fun colorize
: Map[MPROP, Int] do
687 var mclasses
= new HashSet[MClass]
688 mclasses
.add_all
(self.class_coloring
.core
)
689 mclasses
.add_all
(self.class_coloring
.crown
)
692 for mclass
in mclasses
do
693 min_color
= max_color
(min_color
, mclasses
)
694 colorize_elements
(self.properties
(mclass
), min_color
)
696 return self.coloration_result
700 abstract class VTPerfectHashing
703 private var masks
: Map[MClass, Int] = new HashMap[MClass, Int]
705 init(mmodule
: MModule, class_coloring
: ClassColoring) do super
707 redef fun colorize
: Map[MPROP, Int] do
708 var mclasses
= new HashSet[MClass]
709 mclasses
.add_all
(self.class_coloring
.core
)
710 mclasses
.add_all
(self.class_coloring
.crown
)
711 for mclass
in mclasses
do
712 var vts
= self.properties
(mclass
)
714 if coloration_result
.has_key
(vt
) then continue
715 coloration_result
[vt
] = coloration_result
.length
+ 1
718 return self.coloration_result
721 fun compute_masks
: Map[MClass, Int] do
722 var mclasses
= new HashSet[MClass]
723 mclasses
.add_all
(self.class_coloring
.core
)
724 mclasses
.add_all
(self.class_coloring
.crown
)
725 for mclass
in mclasses
do
726 self.masks
[mclass
] = compute_mask
(self.properties
(mclass
))
731 private fun compute_mask
(vts
: Set[MPROP]): Int do
734 var used
= new List[Int]
736 var res
= op
(mask
, self.coloration_result
[vt
])
737 if used
.has
(res
) then
743 if used
.length
== vts
.length
then break
749 redef fun build_property_tables
do
750 var tables
= new HashMap[MClass, Array[nullable MPROPDEF]]
752 for mclass
in self.class_coloring
.coloration_result
.keys
do
753 var table
= new Array[nullable MPROPDEF]
754 # first, fill table from parents by reverse linearization order
755 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
756 var lin
= self.class_coloring
.reverse_linearize
(parents
)
758 for mproperty
in self.properties
(parent
) do
759 var color
= phash
(self.coloration_result
[mproperty
], masks
[mclass
])
760 if table
.length
<= color
then
761 for i
in [table
.length
.. color
[ do
765 for mpropdef
in mproperty
.mpropdefs
do
766 if mpropdef
.mclassdef
.mclass
== parent
then
767 table
[color
] = mpropdef
773 # then override with local properties
774 for mproperty
in self.properties
(mclass
) do
775 var color
= phash
(self.coloration_result
[mproperty
], masks
[mclass
])
776 if table
.length
<= color
then
777 for i
in [table
.length
.. color
[ do
781 for mpropdef
in mproperty
.mpropdefs
do
782 if mpropdef
.mclassdef
.mclass
== mclass
then
783 table
[color
] = mpropdef
787 tables
[mclass
] = table
792 private fun op
(mask
: Int, id
:Int): Int is abstract
793 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
797 class VTModPerfectHashing
798 super VTPerfectHashing
799 init(mmodule
: MModule, class_coloring
: ClassColoring) do super
800 redef fun op
(mask
, id
) do return mask
% id
803 class VTAndPerfectHashing
804 super VTPerfectHashing
805 init(mmodule
: MModule, class_coloring
: ClassColoring) do super
806 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
809 # MParameterType coloring
811 private var class_coloring
: ClassColoring
812 private var coloration_result
: Map[MParameterType, Int] = new HashMap[MParameterType, Int]
814 init(class_coloring
: ClassColoring) do
815 self.class_coloring
= class_coloring
818 fun colorize
: Map[MParameterType, Int] do
819 colorize_core_properties
820 colorize_crown_properties
821 return self.coloration_result
824 # Colorize properties of the core hierarchy
825 private fun colorize_core_properties
do
826 var mclasses
= self.class_coloring
.core
829 for mclass
in mclasses
do
830 var color
= min_color
832 # if the class is root, get the minimal color
833 if self.class_coloring
.parent_elements
(mclass
).length
== 0 then
834 colorize_elements
(self.fts
(mclass
), color
)
836 # check last color used by parents
837 color
= max_color
(color
, self.class_coloring
.parent_elements
(mclass
))
838 # check max color used in conflicts
839 if self.class_coloring
.conflicts_graph
.has_key
(mclass
) then
840 color
= max_color
(color
, self.class_coloring
.conflicts_graph
[mclass
])
843 colorize_elements
(self.fts
(mclass
), color
)
848 # Colorize properties of the crown hierarchy
849 private fun colorize_crown_properties
do
850 for mclass
in self.class_coloring
.crown
do
851 colorize_elements
(self.fts
(mclass
), max_color
(0, self.class_coloring
.parent_elements
(mclass
)))
855 # Colorize a collection of properties given a starting color
856 private fun colorize_elements
(elements
: Collection[MParameterType], start_color
: Int) do
857 for element
in elements
do
858 if self.coloration_result
.has_key
(element
) then continue
859 self.coloration_result
[element
] = start_color
864 private fun max_color
(min_color
: Int, mclasses
: Collection[MClass]): Int do
865 var max_color
= min_color
867 for mclass
in mclasses
do
868 for ft
in self.fts
(mclass
) do
869 var color
= min_color
870 if self.coloration_result
.has_key
(ft
) then
871 color
= self.coloration_result
[ft
]
872 if color
>= max_color
then max_color
= color
+ 1
880 private var fts_cache
: Map[MClass, Set[MParameterType]] = new HashMap[MClass, Set[MParameterType]]
882 private fun fts
(mclass
: MClass): Set[MParameterType] do
883 if not self.fts_cache
.has_key
(mclass
) then
884 var fts
= new HashSet[MParameterType]
885 var mclass_type
= mclass
.mclass_type
886 if mclass_type
isa MGenericType then
887 for ft
in mclass_type
.arguments
do
888 fts
.add
(ft
.as(MParameterType))
891 self.fts_cache
[mclass
] = fts
893 return fts_cache
[mclass
]
896 fun build_ft_tables
: Map[MClass, Array[nullable MParameterType]] do
897 var tables
= new HashMap[MClass, Array[nullable MParameterType]]
899 for mclass
in self.class_coloring
.coloration_result
.keys
do
900 var table
= new Array[nullable MParameterType]
902 # first, fill table from parents
903 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
904 for parent
in parents
do
905 for ft
in self.fts
(parent
) do
906 var color
= self.coloration_result
[ft
]
907 if table
.length
<= color
then
908 for i
in [table
.length
.. color
[ do
916 # then override with local properties
917 for ft
in self.fts
(mclass
) do
918 var color
= self.coloration_result
[ft
]
919 if table
.length
<= color
then
920 for i
in [table
.length
.. color
[ do
926 tables
[mclass
] = table
932 class NaiveFTColoring
935 init(class_coloring
: ClassColoring) do end
937 redef fun colorize
: Map[MParameterType, Int] do
938 var mclasses
= new HashSet[MClass]
939 mclasses
.add_all
(self.class_coloring
.core
)
940 mclasses
.add_all
(self.class_coloring
.crown
)
943 for mclass
in mclasses
do
944 min_color
= max_color
(min_color
, mclasses
)
945 colorize_elements
(self.fts
(mclass
), min_color
)
947 return self.coloration_result
951 abstract class FTPerfectHashing
954 private var masks
: Map[MClass, Int] = new HashMap[MClass, Int]
956 init(class_coloring
: ClassColoring) do end
958 redef fun colorize
: Map[MParameterType, Int] do
959 var mclasses
= new HashSet[MClass]
960 mclasses
.add_all
(self.class_coloring
.core
)
961 mclasses
.add_all
(self.class_coloring
.crown
)
962 for mclass
in mclasses
do
963 for ft
in self.fts
(mclass
) do
964 if coloration_result
.has_key
(ft
) then continue
965 coloration_result
[ft
] = coloration_result
.length
+ 1
968 return self.coloration_result
971 fun compute_masks
: Map[MClass, Int] do
972 var mclasses
= new HashSet[MClass]
973 mclasses
.add_all
(self.class_coloring
.core
)
974 mclasses
.add_all
(self.class_coloring
.crown
)
975 for mclass
in mclasses
do
976 var fts
= new HashSet[MParameterType]
977 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
978 for parent
in parents
do
979 fts
.add_all
(self.fts
(parent
))
981 fts
.add_all
(self.fts
(mclass
))
982 self.masks
[mclass
] = compute_mask
(fts
)
987 private fun compute_mask
(fts
: Set[MParameterType]): Int do
990 var used
= new List[Int]
992 var res
= op
(mask
, self.coloration_result
[ft
])
993 if used
.has
(res
) then
999 if used
.length
== fts
.length
then break
1005 redef fun build_ft_tables
do
1006 var tables
= new HashMap[MClass, Array[nullable MParameterType]]
1008 for mclass
in self.class_coloring
.coloration_result
.keys
do
1009 var table
= new Array[nullable MParameterType]
1011 # first, fill table from parents
1012 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
1013 for parent
in parents
do
1014 for ft
in self.fts
(parent
) do
1015 var color
= phash
(self.coloration_result
[ft
], masks
[mclass
])
1016 if table
.length
<= color
then
1017 for i
in [table
.length
.. color
[ do
1025 # then override with local properties
1026 for ft
in self.fts
(mclass
) do
1027 var color
= phash
(self.coloration_result
[ft
], masks
[mclass
])
1028 if table
.length
<= color
then
1029 for i
in [table
.length
.. color
[ do
1035 tables
[mclass
] = table
1040 private fun op
(mask
: Int, id
:Int): Int is abstract
1041 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
1044 class FTModPerfectHashing
1045 super FTPerfectHashing
1046 init(class_coloring
: ClassColoring) do end
1047 redef fun op
(mask
, id
) do return mask
% id
1050 class FTAndPerfectHashing
1051 super FTPerfectHashing
1052 init(class_coloring
: ClassColoring) do end
1053 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
1056 # Live Entries coloring
1057 class LiveEntryColoring
1059 private var coloration_result
: Map[MType, Int] = new HashMap[MType, Int]
1060 private var conflicts_graph_cache
: nullable HashMap[MType, Set[MType]]
1061 var livetypes_tables_sizes
: nullable Map[MClass, Array[Int]]
1065 fun colorize
(elements
: Collection[MType]): Map[MType, Int] do
1067 build_conflicts_graph
(elements
)
1070 colorize_elements
(elements
)
1072 return coloration_result
1076 fun build_livetype_tables
(mtypes
: Set[MType]): Map[MClass, Array[nullable Object]] do
1077 var livetypes_tables
= new HashMap[MClass, Array[nullable Object]]
1078 self.livetypes_tables_sizes
= new HashMap[MClass, Array[Int]]
1080 for mtype
in mtypes
do
1081 if mtype
isa MGenericType then
1082 var table
: Array[nullable Object]
1083 var sizes
: Array[Int]
1084 if livetypes_tables
.has_key
(mtype
.mclass
) then
1085 table
= livetypes_tables
[mtype
.mclass
]
1087 table
= new Array[nullable Object]
1088 livetypes_tables
[mtype
.mclass
] = table
1090 if livetypes_tables_sizes
.has_key
(mtype
.mclass
) then
1091 sizes
= livetypes_tables_sizes
[mtype
.mclass
]
1093 sizes
= new Array[Int]
1094 livetypes_tables_sizes
[mtype
.mclass
] = sizes
1096 build_livetype_table
(mtype
, 0, table
, sizes
)
1100 return livetypes_tables
1103 # Build live gentype table recursively
1104 private fun build_livetype_table
(mtype
: MGenericType, current_rank
: Int, table
: Array[nullable Object], sizes
: Array[Int]) do
1105 var ft
= mtype
.arguments
[current_rank
]
1106 if not self.coloration_result
.has_key
(ft
) then return
1107 var color
= self.coloration_result
[ft
]
1109 if current_rank
>= sizes
.length
then
1110 sizes
[current_rank
] = color
+ 1
1111 else if color
>= sizes
[current_rank
] then
1112 sizes
[current_rank
] = color
+ 1
1115 if color
> table
.length
then
1116 for i
in [table
.length
.. color
[ do table
[i
] = null
1119 if current_rank
== mtype
.arguments
.length
- 1 then
1120 table
[color
] = mtype
1122 var ft_table
: Array[nullable Object]
1123 if color
< table
.length
and table
[color
] != null then
1124 ft_table
= table
[color
].as(Array[nullable Object])
1126 ft_table
= new Array[nullable Object]
1128 table
[color
] = ft_table
1129 build_livetype_table
(mtype
, current_rank
+ 1, ft_table
, sizes
)
1133 # Colorize a collection of elements
1134 fun colorize_elements
(elements
: Collection[MType]) do
1137 for element
in elements
do
1138 var color
= min_color
1139 while not self.is_color_free
(element
, color
) do
1142 coloration_result
[element
] = color
1147 # Check if a related element to the element already use the color
1148 private fun is_color_free
(element
: MType, color
: Int): Bool do
1149 if conflicts_graph
.has_key
(element
) then
1150 for st
in conflicts_graph
[element
] do
1151 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
1157 # look for types in the same generic signatures
1158 private fun build_conflicts_graph
(elements
: Collection[MType]) do
1159 # regroup types by classes
1160 var genclasses
= new HashMap[MClass, Set[MType]]
1161 for e
in elements
do
1162 if e
isa MGenericType then
1163 if not genclasses
.has_key
(e
.mclass
) then
1164 genclasses
[e
.mclass
] = new HashSet[MType]
1166 genclasses
[e
.mclass
].add
(e
)
1171 self.conflicts_graph_cache
= new HashMap[MType, Set[MType]]
1172 for mclass
, mtypes
in genclasses
do
1174 for rank
in [0..mclass
.arity
[ do
1175 # for each live type
1176 for mtype
in mtypes
do
1177 var mclasstype
: MClassType
1178 if mtype
isa MNullableType then
1179 mclasstype
= mtype
.mtype
.as(MClassType)
1181 mclasstype
= mtype
.as(MClassType)
1183 var ft
= mclasstype
.arguments
[rank
]
1184 for otype
in mtypes
do
1185 if mtype
== otype
then continue
1186 var oclasstype
: MClassType
1187 if otype
isa MNullableType then
1188 oclasstype
= otype
.mtype
.as(MClassType)
1190 oclasstype
= otype
.as(MClassType)
1192 var oft
= oclasstype
.arguments
[rank
]
1193 self.add_conflict
(ft
, oft
)
1200 private fun add_conflict
(mtype
: MType, otype
: MType) do
1201 if mtype
== otype
then return
1202 if not self.conflicts_graph_cache
.has_key
(mtype
) then self.conflicts_graph_cache
[mtype
] = new HashSet[MType]
1203 self.conflicts_graph_cache
[mtype
].add
(otype
)
1204 if not self.conflicts_graph_cache
.has_key
(otype
) then self.conflicts_graph_cache
[otype
] = new HashSet[MType]
1205 self.conflicts_graph_cache
[otype
].add
(mtype
)
1207 private fun conflicts_graph
: Map[MType, Set[MType]] do return conflicts_graph_cache
.as(not null)
1210 class NaiveLiveEntryColoring
1211 super LiveEntryColoring
1215 redef fun colorize_elements
(elements
: Collection[MType]) do
1217 for element
in elements
do
1218 coloration_result
[element
] = color
1224 # live unanchored coloring
1225 class UnanchoredTypeColoring
1227 private var coloration_result
: Map[MType, Int] = new HashMap[MType, Int]
1228 private var conflicts_graph
: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
1232 fun colorize
(elements
: Map[MClassType, Set[MType]]): Map[MType, Int] do
1233 build_conflicts_graph
(elements
)
1234 colorize_elements
(elements
)
1235 return coloration_result
1238 fun build_tables
(elements
: Map[MClassType, Set[MType]]): Map[MClassType, Array[nullable MType]] do
1239 var tables
= new HashMap[MClassType, Array[nullable MType]]
1241 for mclasstype
, mtypes
in elements
do
1242 var table
= new Array[nullable MType]
1243 for mtype
in mtypes
do
1244 var color
= self.coloration_result
[mtype
]
1245 if table
.length
<= color
then
1246 for i
in [table
.length
.. color
[ do
1250 table
[color
] = mtype
1252 tables
[mclasstype
] = table
1257 # Colorize a collection of elements
1258 fun colorize_elements
(elements
: Map[MClassType, Set[MType]]) do
1260 for mclasstype
, mclasstypes
in elements
do
1261 for element
in mclasstypes
do
1262 if self.coloration_result
.has_key
(element
) then continue
1263 var color
= min_color
1264 while not self.is_color_free
(element
, color
) do
1267 coloration_result
[element
] = color
1273 # Check if a related element to the element already use the color
1274 private fun is_color_free
(element
: MType, color
: Int): Bool do
1275 if conflicts_graph
.has_key
(element
) then
1276 for st
in conflicts_graph
[element
] do
1277 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
1283 # look for unanchored types generated by the same type
1284 private fun build_conflicts_graph
(elements
: Map[MClassType, Set[MType]]) do
1285 for mclasstype
, mtypes
in elements
do
1286 for mtype
in mtypes
do
1287 for otype
in mtypes
do
1288 if otype
== mtype
then continue
1289 self.add_conflict
(mtype
, otype
)
1295 private fun add_conflict
(mtype
: MType, otype
: MType) do
1296 if mtype
== otype
then return
1297 if not self.conflicts_graph
.has_key
(mtype
) then self.conflicts_graph
[mtype
] = new HashSet[MType]
1298 self.conflicts_graph
[mtype
].add
(otype
)
1299 if not self.conflicts_graph
.has_key
(otype
) then self.conflicts_graph
[otype
] = new HashSet[MType]
1300 self.conflicts_graph
[otype
].add
(mtype
)
1304 class NaiveUnanchoredTypeColoring
1305 super UnanchoredTypeColoring
1309 redef fun colorize_elements
(elements
: Map[MClassType, Set[MType]]) do
1311 for mclasstype
, mclasstypes
in elements
do
1312 for element
in mclasstypes
do
1313 coloration_result
[element
] = color
1320 abstract class UnanchoredTypePerfectHashing
1321 super NaiveUnanchoredTypeColoring
1323 private var masks
: Map[MClassType, Int] = new HashMap[MClassType, Int]
1327 redef fun colorize_elements
(elements
: Map[MClassType, Set[MType]]) do
1329 for mclasstype
, mclasstypes
in elements
do
1330 for element
in mclasstypes
do
1331 coloration_result
[element
] = color
1337 fun compute_masks
(elements
: Map[MClassType, Set[MType]]): Map[MClassType, Int] do
1338 for mclasstype
, mtypes
in elements
do
1339 self.masks
[mclasstype
] = compute_mask
(mtypes
)
1344 private fun compute_mask
(mtypes
: Set[MType]): Int do
1347 var used
= new List[Int]
1348 for mtype
in mtypes
do
1349 var res
= op
(mask
, self.coloration_result
[mtype
])
1350 if used
.has
(res
) then
1356 if used
.length
== mtypes
.length
then break
1362 redef fun build_tables
(elements
: Map[MClassType, Set[MType]]): Map[MClassType, Array[nullable MType]] do
1363 var tables
= new HashMap[MClassType, Array[nullable MType]]
1365 for mclasstype
, mtypes
in elements
do
1366 var table
= new Array[nullable MType]
1367 for mtype
in mtypes
do
1368 var color
= phash
(self.coloration_result
[mtype
], masks
[mclasstype
])
1369 if table
.length
<= color
then
1370 for i
in [table
.length
.. color
[ do
1374 table
[color
] = mtype
1376 tables
[mclasstype
] = table
1381 private fun op
(mask
: Int, id
:Int): Int is abstract
1382 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
1385 class UnanchoredTypeModPerfectHashing
1386 super UnanchoredTypePerfectHashing
1388 redef fun op
(mask
, id
) do return mask
% id
1391 class UnanchoredTypeAndPerfectHashing
1392 super UnanchoredTypePerfectHashing
1394 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
1400 redef class HashSet[E
]
1401 init from
(elements
: Collection[E
]) do
1403 self.add_all
(elements
)
1407 redef class Array[E
]
1408 init from
(elements
: Collection[E
]) do
1410 self.add_all
(elements
)
1413 # Return a new Array with the elements only contened in 'self' and not in 'o'
1414 fun -(o
: Array[E
]): Array[E
] do
1415 var res
= new Array[E
]
1416 for e
in self do if not o
.has
(e
) then res
.add
(e
)
1423 # Return a linearization of a set of mtypes
1424 private fun linearize_mtypes
(mtypes
: Set[MType]): Array[MType] do
1425 var lin
= new Array[MType].from
(mtypes
)
1426 var sorter
= new TypeSorter(self)
1431 # Return a reverse linearization of a set of mtypes
1432 private fun reverse_linearize_mtypes
(mtypes
: Set[MType]): Array[MType] do
1433 var lin
= new Array[MType].from
(mtypes
)
1434 var sorter
= new ReverseTypeSorter(self)
1439 # Return super types of a `mtype` in `self`
1440 private fun super_mtypes
(mtype
: MType, mtypes
: Set[MType]): Set[MType] do
1441 if not self.super_mtypes_cache
.has_key
(mtype
) then
1442 var supers
= new HashSet[MType]
1443 for otype
in mtypes
do
1444 if otype
== mtype
then continue
1445 if mtype
.is_subtype
(self, null, otype
) then
1449 self.super_mtypes_cache
[mtype
] = supers
1451 return self.super_mtypes_cache
[mtype
]
1454 private var super_mtypes_cache
: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
1456 # Return all sub mtypes (directs and indirects) of a `mtype` in `self`
1457 private fun sub_mtypes
(mtype
: MType, mtypes
: Set[MType]): Set[MType] do
1458 if not self.sub_mtypes_cache
.has_key
(mtype
) then
1459 var subs
= new HashSet[MType]
1460 for otype
in mtypes
do
1461 if otype
== mtype
then continue
1462 if otype
.is_subtype
(self, null, mtype
) then
1466 self.sub_mtypes_cache
[mtype
] = subs
1468 return self.sub_mtypes_cache
[mtype
]
1471 private var sub_mtypes_cache
: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
1473 # Return a linearization of a set of mclasses
1474 private fun linearize_mclasses
(mclasses
: Set[MClass]): Array[MClass] do
1475 var lin
= new Array[MClass].from
(mclasses
)
1476 var sorter
= new ClassSorter(self)
1481 # Return a reverse linearization of a set of mtypes
1482 private fun reverse_linearize_mclasses
(mclasses
: Set[MClass]): Array[MClass] do
1483 var lin
= new Array[MClass].from
(mclasses
)
1484 var sorter
= new ReverseClassSorter(self)
1489 # Return all super mclasses (directs and indirects) of a `mclass` in `self`
1490 private fun super_mclasses
(mclass
: MClass): Set[MClass] do
1491 if not self.super_mclasses_cache
.has_key
(mclass
) then
1492 var supers
= new HashSet[MClass]
1493 if self.flatten_mclass_hierarchy
.has
(mclass
) then
1494 for sup
in self.flatten_mclass_hierarchy
[mclass
].greaters
do
1495 if sup
== mclass
then continue
1499 self.super_mclasses_cache
[mclass
] = supers
1501 return self.super_mclasses_cache
[mclass
]
1504 private var super_mclasses_cache
: Map[MClass, Set[MClass]] = new HashMap[MClass, Set[MClass]]
1506 # Return all parents of a `mclass` in `self`
1507 private fun parent_mclasses
(mclass
: MClass): Set[MClass] do
1508 if not self.parent_mclasses_cache
.has_key
(mclass
) then
1509 var parents
= new HashSet[MClass]
1510 if self.flatten_mclass_hierarchy
.has
(mclass
) then
1511 for sup
in self.flatten_mclass_hierarchy
[mclass
].direct_greaters
do
1512 if sup
== mclass
then continue
1516 self.parent_mclasses_cache
[mclass
] = parents
1518 return self.parent_mclasses_cache
[mclass
]
1521 private var parent_mclasses_cache
: Map[MClass, Set[MClass]] = new HashMap[MClass, Set[MClass]]
1523 # Return all sub mclasses (directs and indirects) of a `mclass` in `self`
1524 private fun sub_mclasses
(mclass
: MClass): Set[MClass] do
1525 if not self.sub_mclasses_cache
.has_key
(mclass
) then
1526 var subs
= new HashSet[MClass]
1527 if self.flatten_mclass_hierarchy
.has
(mclass
) then
1528 for sub
in self.flatten_mclass_hierarchy
[mclass
].smallers
do
1529 if sub
== mclass
then continue
1533 self.sub_mclasses_cache
[mclass
] = subs
1535 return self.sub_mclasses_cache
[mclass
]
1538 private var sub_mclasses_cache
: Map[MClass, Set[MClass]] = new HashMap[MClass, Set[MClass]]
1540 # All 'mproperties' associated to all 'mclassdefs' of `mclass`
1541 private fun properties
(mclass
: MClass): Set[MProperty] do
1542 if not self.properties_cache
.has_key
(mclass
) then
1543 var properties
= new HashSet[MProperty]
1544 var parents
= self.super_mclasses
(mclass
)
1545 for parent
in parents
do
1546 properties
.add_all
(self.properties
(parent
))
1549 for mclassdef
in mclass
.mclassdefs
do
1550 for mpropdef
in mclassdef
.mpropdefs
do
1551 properties
.add
(mpropdef
.mproperty
)
1554 self.properties_cache
[mclass
] = properties
1556 return properties_cache
[mclass
]
1559 private var properties_cache
: Map[MClass, Set[MProperty]] = new HashMap[MClass, Set[MProperty]]
1562 # A sorter for linearize list of types
1564 super AbstractSorter[MType]
1566 private var mmodule
: MModule
1568 init(mmodule
: MModule) do self.mmodule
= mmodule
1570 redef fun compare
(a
, b
) do
1573 else if a
.is_subtype
(self.mmodule
, null, b
) then
1580 # A sorter for reverse linearization
1581 class ReverseTypeSorter
1584 init(mmodule
: MModule) do end
1586 redef fun compare
(a
, b
) do
1589 else if a
.is_subtype
(self.mmodule
, null, b
) then
1596 # A sorter for linearize list of classes
1597 private class ClassSorter
1598 super AbstractSorter[MClass]
1600 var mmodule
: MModule
1602 redef fun compare
(a
, b
) do
1605 else if self.mmodule
.flatten_mclass_hierarchy
.has
(a
) and self.mmodule
.flatten_mclass_hierarchy
[a
].greaters
.has
(b
) then
1612 # A sorter for reverse linearization
1613 private class ReverseClassSorter
1614 super AbstractSorter[MClass]
1616 var mmodule
: MModule
1618 redef fun compare
(a
, b
) do
1621 else if self.mmodule
.flatten_mclass_hierarchy
.has
(a
) and self.mmodule
.flatten_mclass_hierarchy
[a
].greaters
.has
(b
) then