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 element
24 var ids
: Map[E
, Int] = new HashMap[E
, Int]
25 # Fixed positions of each element in all tables
26 var pos
: Map[E
, Int] = new HashMap[E
, Int]
29 class PHTypingLayout[E
]
31 # Masks used by hash function
32 var masks
: Map[E
, Int] = new HashMap[E
, Int]
33 # Positions of each element for each tables
34 var hashes
: Map[E
, Map[E
, Int]] = new HashMap[E
, Map[E
, Int]]
37 class PropertyLayout[E
]
38 # Fixed positions of each element in all tables
39 var pos
: Map[E
, Int] = new HashMap[E
, Int]
44 abstract class TypingLayoutBuilder[E
]
46 type LAYOUT: TypingLayout[E
]
48 private var mmodule
: MModule
49 init(mmodule
: MModule) do self.mmodule
= mmodule
51 # Compute elements ids and position
52 fun build_layout
(elements
: Set[E
]): LAYOUT is abstract
54 # Give each MType a unic id using a descending linearization of the `mtypes` set
55 private fun compute_ids
(elements
: Set[E
]): Map[E
, Int] do
56 var ids
= new HashMap[E
, Int]
57 var lin
= self.reverse_linearize
(elements
)
59 ids
[element
] = ids
.length
64 private fun reverse_linearize
(elements
: Set[E
]): Array[E
] is abstract
67 # Layout builder for MType using Binary Matrix (BM)
68 class BMTypeLayoutBuilder
69 super TypingLayoutBuilder[MType]
71 init(mmodule
: MModule) do super
73 # Compute mtypes ids and position using BM
74 redef fun build_layout
(mtypes
) do
75 var result
= new TypingLayout[MType]
76 result
.ids
= self.compute_ids
(mtypes
)
77 result
.pos
= result
.ids
81 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mtypes
(elements
)
84 # Layout builder for MType using Coloring (CL)
85 class CLTypeLayoutBuilder
86 super TypingLayoutBuilder[MType]
88 private var colorer
: MTypeColorer
90 init(mmodule
: MModule) do
92 self.colorer
= new MTypeColorer(mmodule
)
95 # Compute mtypes ids and position using BM
96 redef fun build_layout
(mtypes
) do
97 var result
= new TypingLayout[MType]
98 result
.ids
= self.compute_ids
(mtypes
)
99 result
.pos
= self.colorer
.colorize
(mtypes
)
103 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mtypes
(elements
)
106 # Layout builder for MType using Perfect Hashing (PH)
107 class PHTypeLayoutBuilder
108 super TypingLayoutBuilder[MType]
110 redef type LAYOUT: PHTypingLayout[MType]
112 private var hasher
: MTypeHasher
114 init(mmodule
: MModule, operator
: PHOperator) do
116 self.hasher
= new MTypeHasher(mmodule
, operator
)
119 # Compute mtypes ids and position using BM
120 redef fun build_layout
(mtypes
) do
121 var result
= new PHTypingLayout[MType]
122 result
.ids
= self.compute_ids
(mtypes
)
123 result
.masks
= self.hasher
.compute_masks
(mtypes
, result
.ids
)
124 result
.hashes
= self.hasher
.compute_hashes
(mtypes
, result
.ids
, result
.masks
)
128 # Ids start from 1 instead of 0
129 redef fun compute_ids
(mtypes
) do
130 var ids
= new HashMap[MType, Int]
131 var lin
= self.mmodule
.reverse_linearize_mtypes
(mtypes
)
133 ids
[mtype
] = ids
.length
+ 1
138 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mtypes
(elements
)
141 # Layout builder for MClass using Binary Matrix (BM)
142 class BMClassLayoutBuilder
143 super TypingLayoutBuilder[MClass]
145 init(mmodule
: MModule) do super
147 # Compute mclasses ids and position using BM
148 redef fun build_layout
(mclasses
) do
149 var result
= new TypingLayout[MClass]
150 result
.ids
= self.compute_ids
(mclasses
)
151 result
.pos
= result
.ids
155 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mclasses
(elements
)
158 # Layout builder for MClass using Coloring (CL)
159 class CLClassLayoutBuilder
160 super TypingLayoutBuilder[MClass]
162 private var colorer
: MClassColorer
164 init(mmodule
: MModule) do
166 self.colorer
= new MClassColorer(mmodule
)
169 # Compute mclasses ids and position using BM
170 redef fun build_layout
(mclasses
) do
171 var result
= new TypingLayout[MClass]
172 result
.ids
= self.compute_ids
(mclasses
)
173 result
.pos
= self.colorer
.colorize
(mclasses
)
177 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mclasses
(elements
)
180 # Layout builder for MClass using Perfect Hashing (PH)
181 class PHClassLayoutBuilder
182 super TypingLayoutBuilder[MClass]
184 redef type LAYOUT: PHTypingLayout[MClass]
186 private var hasher
: MClassHasher
188 init(mmodule
: MModule, operator
: PHOperator) do
190 self.hasher
= new MClassHasher(mmodule
, operator
)
193 # Compute mclasses ids and position using BM
194 redef fun build_layout
(mclasses
) do
195 var result
= new PHTypingLayout[MClass]
196 result
.ids
= self.compute_ids
(mclasses
)
197 result
.masks
= self.hasher
.compute_masks
(mclasses
, result
.ids
)
198 result
.hashes
= self.hasher
.compute_hashes
(mclasses
, result
.ids
, result
.masks
)
202 # Ids start from 1 instead of 0
203 redef fun compute_ids
(mclasses
) do
204 var ids
= new HashMap[MClass, Int]
205 var lin
= self.mmodule
.reverse_linearize_mclasses
(mclasses
)
207 ids
[mclass
] = ids
.length
+ 1
212 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mclasses
(elements
)
215 abstract class PropertyLayoutBuilder[E
: MProperty]
217 type LAYOUT: PropertyLayout[E
]
219 private var mmodule
: MModule
220 init(mmodule
: MModule) do self.mmodule
= mmodule
222 # Compute properties ids and position
223 fun build_layout
(mclasses
: Set[MClass]): LAYOUT is abstract
226 # Layout builder for MProperty using Coloring (CL)
227 class CLPropertyLayoutBuilder[E
: MProperty]
228 super PropertyLayoutBuilder[E
]
230 private var colorer
: MPropertyColorer[E
]
232 init(mmodule
: MModule) do
234 self.colorer
= new MPropertyColorer[E
](mmodule
)
237 # Compute mclasses ids and position using BM
238 redef fun build_layout
(mclasses
) do
239 var result
= new PropertyLayout[E
]
240 result
.pos
= self.colorer
.colorize
(mclasses
)
247 abstract class AbstractColorer[E
: Object]
249 private var core
: Set[E
] = new HashSet[E
]
250 private var crown
: Set[E
] = new HashSet[E
]
251 private var border
: Set[E
] = new HashSet[E
]
253 private var coloration_result
: Map[E
, Int] = new HashMap[E
, Int]
257 fun colorize
(elements
: Set[E
]): Map[E
, Int] do
258 tag_elements
(elements
)
259 build_conflicts_graph
(elements
)
260 colorize_elements
(core
)
261 colorize_elements
(border
)
262 colorize_elements
(crown
)
263 return coloration_result
266 # Colorize a collection of elements
267 private fun colorize_elements
(elements
: Set[E
]) do
270 var lin
= reverse_linearize
(elements
)
271 for element
in lin
do
272 var color
= min_color
273 while not self.is_color_free
(element
, elements
, color
) do
276 coloration_result
[element
] = color
281 # Check if a related element to the element already use the color
282 private fun is_color_free
(element
: E
, elements
: Set[E
], color
: Int): Bool do
283 if conflicts_graph
.has_key
(element
) then
284 for st
in conflicts_graph
[element
] do
285 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
288 for st
in self.super_elements
(element
, elements
) do
289 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
294 # Tag elements as core, crown or border
295 private fun tag_elements
(elements
: Set[E
]) do
296 for element
in elements
do
297 # Check if sub elements are all in single inheritance
298 var all_subelements_si
= true
299 for subelem
in self.sub_elements
(element
, elements
) do
300 if self.is_element_mi
(subelem
, elements
) then
301 all_subelements_si
= false
306 # Tag as core, crown or border
307 if self.is_element_mi
(element
, elements
) then
308 core
.add_all
(self.super_elements
(element
, elements
))
310 if all_subelements_si
then
313 else if not all_subelements_si
then
314 core
.add_all
(self.super_elements
(element
, elements
))
322 # Conflicts graph of elements hierarchy (two types are in conflict if they have common subelements)
323 private fun build_conflicts_graph
(elements
: Set[E
]) do
324 self.conflicts_graph
= new HashMap[E
, HashSet[E
]]
325 var core
= reverse_linearize
(self.core
)
327 for i
in self.linear_extension
(t
, elements
) do
328 if t
== i
then continue
330 var lin_i
= self.linear_extension
(i
, elements
)
332 for j
in self.linear_extension
(t
, elements
) do
333 if i
== j
or j
== t
then continue
334 var lin_j
= self.linear_extension
(j
, elements
)
336 var d_ij
= lin_i
- lin_j
337 var d_ji
= lin_j
- lin_i
340 if not conflicts_graph
.has_key
(ed1
) then conflicts_graph
[ed1
] = new HashSet[E
]
341 # add ed1 x ed2 to conflicts graph
342 for ed2
in d_ji
do conflicts_graph
[ed1
].add
(ed2
)
345 if not conflicts_graph
.has_key
(ed1
) then conflicts_graph
[ed1
] = new HashSet[E
]
346 # add ed1 x ed2 to conflicts graph
347 for ed2
in d_ji
do conflicts_graph
[ed1
].add
(ed2
)
354 private var conflicts_graph
: nullable HashMap[E
, Set[E
]]
356 # cache for linear_extensions
357 private var linear_extensions_cache
: Map[E
, Array[E
]] = new HashMap[E
, Array[E
]]
359 # Return a linear_extension of super_elements of the element
360 private fun linear_extension
(element
: E
, elements
: Set[E
]): Array[E
] do
361 if not self.linear_extensions_cache
.has_key
(element
) then
362 var supers
= new HashSet[E
]
364 supers
.add_all
(self.super_elements
(element
, elements
))
365 self.linear_extensions_cache
[element
] = self.linearize
(supers
)
367 return self.linear_extensions_cache
[element
]
370 private fun super_elements
(element
: E
, elements
: Set[E
]): Set[E
] is abstract
371 private fun sub_elements
(element
: E
, elements
: Set[E
]): Set[E
] is abstract
372 private fun is_element_mi
(element
: E
, elements
: Set[E
]): Bool is abstract
373 private fun linearize
(elements
: Set[E
]): Array[E
] is abstract
374 private fun reverse_linearize
(elements
: Set[E
]): Array[E
] is abstract
378 private class MTypeColorer
379 super AbstractColorer[MType]
383 init(mmodule
: MModule) do self.mmodule
= mmodule
385 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mtypes
(element
, elements
)
386 redef fun is_element_mi
(element
, elements
) do return self.super_elements
(element
, elements
).length
> 1
387 redef fun sub_elements
(element
, elements
) do do return self.mmodule
.sub_mtypes
(element
, elements
)
388 redef fun linearize
(elements
) do return self.mmodule
.linearize_mtypes
(elements
)
389 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mtypes
(elements
)
393 private class MClassColorer
394 super AbstractColorer[MClass]
396 private var mmodule
: MModule
398 init(mmodule
: MModule) do self.mmodule
= mmodule
400 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mclasses
(element
)
401 fun parent_elements
(element
: MClass): Set[MClass] do return self.mmodule
.parent_mclasses
(element
)
402 redef fun is_element_mi
(element
, elements
) do return self.parent_elements
(element
).length
> 1
403 redef fun sub_elements
(element
, elements
) do do return self.mmodule
.sub_mclasses
(element
)
404 redef fun linearize
(elements
) do return self.mmodule
.linearize_mclasses
(elements
)
405 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mclasses
(elements
)
409 private class MPropertyColorer[E
: MProperty]
411 private var mmodule
: MModule
412 private var class_colorer
: MClassColorer
413 private var coloration_result
: Map[E
, Int] = new HashMap[E
, Int]
415 init(mmodule
: MModule) do
416 self.mmodule
= mmodule
417 self.class_colorer
= new MClassColorer(mmodule
)
420 fun colorize
(mclasses
: Set[MClass]): Map[E
, Int] do
421 self.class_colorer
.tag_elements
(mclasses
)
422 self.class_colorer
.build_conflicts_graph
(mclasses
)
423 self.colorize_core
(self.class_colorer
.core
)
424 self.colorize_crown
(self.class_colorer
.crown
)
425 return self.coloration_result
428 # Colorize properties of the core hierarchy
429 private fun colorize_core
(mclasses
: Set[MClass]) do
431 for mclass
in mclasses
do
432 var color
= min_color
434 # if the class is root, get the minimal color
435 if self.mmodule
.parent_mclasses
(mclass
).length
== 0 then
436 colorize_elements
(self.properties
(mclass
), color
)
438 # check last color used by parents
439 color
= max_color
(color
, self.mmodule
.parent_mclasses
(mclass
))
440 # check max color used in conflicts
441 if self.class_colorer
.conflicts_graph
.has_key
(mclass
) then
442 color
= max_color
(color
, self.class_colorer
.conflicts_graph
[mclass
])
444 colorize_elements
(self.properties
(mclass
), color
)
449 # Colorize properties of the crown hierarchy
450 private fun colorize_crown
(mclasses
: Set[MClass]) do
451 for mclass
in mclasses
do
452 colorize_elements
(self.properties
(mclass
), max_color
(0, self.mmodule
.parent_mclasses
(mclass
)))
456 # Colorize a collection of mproperties given a starting color
457 private fun colorize_elements
(elements
: Collection[E
], start_color
: Int) do
458 for element
in elements
do
459 if self.coloration_result
.has_key
(element
) then continue
460 self.coloration_result
[element
] = start_color
465 private fun max_color
(min_color
: Int, mclasses
: Collection[MClass]): Int do
466 var max_color
= min_color
468 for mclass
in mclasses
do
469 for mproperty
in self.properties
(mclass
) do
470 var color
= min_color
471 if self.coloration_result
.has_key
(mproperty
) then
472 color
= self.coloration_result
[mproperty
]
473 if color
>= max_color
then max_color
= color
+ 1
481 private fun properties
(mclass
: MClass): Set[E
] do
482 var properties
= new HashSet[E
]
483 for mprop
in self.mmodule
.properties
(mclass
) do
484 if mprop
isa E
then properties
.add
(mprop
)
492 # Abstract Perfect Hashing
493 private abstract class AbstractHasher[E
: Object]
495 var operator
: PHOperator
497 init(operator
: PHOperator) do self.operator
= operator
499 fun compute_masks
(elements
: Set[E
], ids
: Map[E
, Int]): Map[E
, Int] do
500 var masks
= new HashMap[E
, Int]
501 for element
in elements
do
502 var supers
= new HashSet[E
]
503 supers
.add_all
(self.super_elements
(element
, elements
))
505 masks
[element
] = compute_mask
(supers
, ids
)
510 fun compute_mask
(supers
: Set[E
], ids
: Map[E
, Int]): Int do
513 var used
= new List[Int]
515 var res
= operator
.op
(mask
, ids
[sup
])
516 if used
.has
(res
) then
522 if used
.length
== supers
.length
then break
528 fun compute_hashes
(elements
: Set[E
], ids
: Map[E
, Int], masks
: Map[E
, Int]): Map[E
, Map[E
, Int]] do
529 var hashes
= new HashMap[E
, Map[E
, Int]]
530 for element
in elements
do
531 var supers
= new HashSet[E
]
532 supers
.add_all
(self.super_elements
(element
, elements
))
534 var inhashes
= new HashMap[E
, Int]
535 var mask
= masks
[element
]
537 inhashes
[sup
] = operator
.op
(mask
, ids
[sup
])
539 hashes
[element
] = inhashes
544 fun super_elements
(element
: E
, elements
: Set[E
]): Set[E
] is abstract
547 # Abstract operator used for perfect hashing
548 abstract class PHOperator
549 fun op
(mask
: Int, id
:Int): Int is abstract
552 # Hashing using modulo (MOD) operator
557 redef fun op
(mask
, id
) do return mask
% id
560 # Hashing using binary and (AND) operator
565 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
568 # MType Perfect Hashing
569 private class MTypeHasher
570 super AbstractHasher[MType]
574 init(mmodule
: MModule, operator
: PHOperator) do
576 self.mmodule
= mmodule
579 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mtypes
(element
, elements
)
582 # MClass Perfect Hashing
583 private class MClassHasher
584 super AbstractHasher[MClass]
586 private var mmodule
: MModule
588 init(mmodule
: MModule, operator
: PHOperator) do
590 self.mmodule
= mmodule
593 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mclasses
(element
)
598 super AbstractColorer[MClass]
602 private var mmodule
: MModule
605 private var super_elements_cache
: Map[T
, Set[T
]] = new HashMap[T
, Set[T
]]
606 private var parent_elements_cache
: Map[T
, Set[T
]] = new HashMap[T
, Set[T
]]
607 private var sub_elements_cache
: Map[T
, Set[T
]] = new HashMap[T
, Set[T
]]
609 init(mainmodule
: MModule) do self.mmodule
= mainmodule
611 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mclasses
(element
)
612 fun parent_elements
(element
: MClass): Set[MClass] do return self.mmodule
.parent_mclasses
(element
)
613 redef fun is_element_mi
(element
, elements
) do return self.parent_elements
(element
).length
> 1
614 redef fun sub_elements
(element
, elements
) do do return self.mmodule
.sub_mclasses
(element
)
615 redef fun linearize
(elements
) do return self.mmodule
.linearize_mclasses
(elements
)
616 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mclasses
(elements
)
620 class PropertyColoring
622 type MPROP: MProperty
623 type MPROPDEF: MPropDef
625 private var mmodule
: MModule
626 private var class_coloring
: ClassColoring
627 private var coloration_result
: Map[MPROP, Int] = new HashMap[MPROP, Int]
629 init(mmodule
: MModule, class_coloring
: ClassColoring) do
630 self.mmodule
= mmodule
631 self.class_coloring
= class_coloring
634 fun colorize
: Map[MPROP, Int] do
635 colorize_core_properties
636 colorize_crown_properties
637 return self.coloration_result
640 # Colorize properties of the core hierarchy
641 private fun colorize_core_properties
do
642 var mclasses
= self.class_coloring
.core
645 for mclass
in mclasses
do
646 var color
= min_color
648 # if the class is root, get the minimal color
649 if self.class_coloring
.parent_elements
(mclass
).length
== 0 then
650 colorize_elements
(self.properties
(mclass
), color
)
652 # check last color used by parents
653 color
= max_color
(color
, self.class_coloring
.parent_elements
(mclass
))
654 # check max color used in conflicts
655 if self.class_coloring
.conflicts_graph
.has_key
(mclass
) then
656 color
= max_color
(color
, self.class_coloring
.conflicts_graph
[mclass
])
660 colorize_elements
(self.properties
(mclass
), color
)
665 # Colorize properties of the crown hierarchy
666 private fun colorize_crown_properties
do
667 for mclass
in self.class_coloring
.crown
do
668 colorize_elements
(self.properties
(mclass
), max_color
(0, self.class_coloring
.parent_elements
(mclass
)))
672 # Colorize a collection of properties given a starting color
673 private fun colorize_elements
(elements
: Collection[MPROP], start_color
: Int) do
674 for element
in elements
do
675 if self.coloration_result
.has_key
(element
) then continue
676 self.coloration_result
[element
] = start_color
681 private fun max_color
(min_color
: Int, mclasses
: Collection[MClass]): Int do
682 var max_color
= min_color
684 for mclass
in mclasses
do
685 for mproperty
in self.properties
(mclass
) do
686 var color
= min_color
687 if self.coloration_result
.has_key
(mproperty
) then
688 color
= self.coloration_result
[mproperty
]
689 if color
>= max_color
then max_color
= color
+ 1
696 # All 'mproperties' associated to all 'mclassdefs' of the class
697 private fun properties
(mclass
: MClass): Set[MPROP] do
698 var properties
= new HashSet[MPROP]
699 for mprop
in self.mmodule
.properties
(mclass
) do
700 if mprop
isa MPROP then properties
.add
(mprop
)
708 super PropertyColoring
710 redef type MPROP: MMethod
711 redef type MPROPDEF: MMethodDef
712 init(mmodule
: MModule, class_coloring
: ClassColoring) do super
715 # MAttribute coloring
716 class AttributeColoring
717 super PropertyColoring
719 redef type MPROP: MAttribute
720 redef type MPROPDEF: MAttributeDef
721 init(mmodule
: MModule, class_coloring
: ClassColoring) do super
724 # MVirtualTypeProp coloring
726 super PropertyColoring
728 redef type MPROP: MVirtualTypeProp
729 redef type MPROPDEF: MVirtualTypeDef
730 init(mmodule
: MModule, class_coloring
: ClassColoring) do super
733 class NaiveVTColoring
736 init(mmodule
: MModule, class_coloring
: ClassColoring) do super
738 redef fun colorize
: Map[MPROP, Int] do
739 var mclasses
= new HashSet[MClass]
740 mclasses
.add_all
(self.class_coloring
.core
)
741 mclasses
.add_all
(self.class_coloring
.crown
)
744 for mclass
in mclasses
do
745 min_color
= max_color
(min_color
, mclasses
)
746 colorize_elements
(self.properties
(mclass
), min_color
)
748 return self.coloration_result
752 abstract class VTPerfectHashing
755 private var masks
: Map[MClass, Int] = new HashMap[MClass, Int]
757 init(mmodule
: MModule, class_coloring
: ClassColoring) do super
759 redef fun colorize
: Map[MPROP, Int] do
760 var mclasses
= new HashSet[MClass]
761 mclasses
.add_all
(self.class_coloring
.core
)
762 mclasses
.add_all
(self.class_coloring
.crown
)
763 for mclass
in mclasses
do
764 var vts
= self.properties
(mclass
)
766 if coloration_result
.has_key
(vt
) then continue
767 coloration_result
[vt
] = coloration_result
.length
+ 1
770 return self.coloration_result
773 fun compute_masks
: Map[MClass, Int] do
774 var mclasses
= new HashSet[MClass]
775 mclasses
.add_all
(self.class_coloring
.core
)
776 mclasses
.add_all
(self.class_coloring
.crown
)
777 for mclass
in mclasses
do
778 self.masks
[mclass
] = compute_mask
(self.properties
(mclass
))
783 private fun compute_mask
(vts
: Set[MPROP]): Int do
786 var used
= new List[Int]
788 var res
= op
(mask
, self.coloration_result
[vt
])
789 if used
.has
(res
) then
795 if used
.length
== vts
.length
then break
801 fun build_property_tables
: Map[MClass, Array[nullable MPROPDEF]] do
802 var tables
= new HashMap[MClass, Array[nullable MPROPDEF]]
804 for mclass
in self.class_coloring
.coloration_result
.keys
do
805 var table
= new Array[nullable MPROPDEF]
806 # first, fill table from parents by reverse linearization order
807 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
808 var lin
= self.class_coloring
.reverse_linearize
(parents
)
810 for mproperty
in self.properties
(parent
) do
811 var color
= phash
(self.coloration_result
[mproperty
], masks
[mclass
])
812 if table
.length
<= color
then
813 for i
in [table
.length
.. color
[ do
817 for mpropdef
in mproperty
.mpropdefs
do
818 if mpropdef
.mclassdef
.mclass
== parent
then
819 table
[color
] = mpropdef
825 # then override with local properties
826 for mproperty
in self.properties
(mclass
) do
827 var color
= phash
(self.coloration_result
[mproperty
], masks
[mclass
])
828 if table
.length
<= color
then
829 for i
in [table
.length
.. color
[ do
833 for mpropdef
in mproperty
.mpropdefs
do
834 if mpropdef
.mclassdef
.mclass
== mclass
then
835 table
[color
] = mpropdef
839 tables
[mclass
] = table
844 private fun op
(mask
: Int, id
:Int): Int is abstract
845 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
849 class VTModPerfectHashing
850 super VTPerfectHashing
851 init(mmodule
: MModule, class_coloring
: ClassColoring) do super
852 redef fun op
(mask
, id
) do return mask
% id
855 class VTAndPerfectHashing
856 super VTPerfectHashing
857 init(mmodule
: MModule, class_coloring
: ClassColoring) do super
858 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
861 # live unanchored coloring
862 class UnanchoredTypeColoring
864 private var coloration_result
: Map[MType, Int] = new HashMap[MType, Int]
865 private var conflicts_graph
: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
869 fun colorize
(elements
: Map[MClassType, Set[MType]]): Map[MType, Int] do
870 build_conflicts_graph
(elements
)
871 colorize_elements
(elements
)
872 return coloration_result
875 fun build_tables
(elements
: Map[MClassType, Set[MType]]): Map[MClassType, Array[nullable MType]] do
876 var tables
= new HashMap[MClassType, Array[nullable MType]]
878 for mclasstype
, mtypes
in elements
do
879 var table
= new Array[nullable MType]
880 for mtype
in mtypes
do
881 var color
= self.coloration_result
[mtype
]
882 if table
.length
<= color
then
883 for i
in [table
.length
.. color
[ do
889 tables
[mclasstype
] = table
894 # Colorize a collection of elements
895 fun colorize_elements
(elements
: Map[MClassType, Set[MType]]) do
897 for mclasstype
, mclasstypes
in elements
do
898 for element
in mclasstypes
do
899 if self.coloration_result
.has_key
(element
) then continue
900 var color
= min_color
901 while not self.is_color_free
(element
, color
) do
904 coloration_result
[element
] = color
910 # Check if a related element to the element already use the color
911 private fun is_color_free
(element
: MType, color
: Int): Bool do
912 if conflicts_graph
.has_key
(element
) then
913 for st
in conflicts_graph
[element
] do
914 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
920 # look for unanchored types generated by the same type
921 private fun build_conflicts_graph
(elements
: Map[MClassType, Set[MType]]) do
922 for mclasstype
, mtypes
in elements
do
923 for mtype
in mtypes
do
924 for otype
in mtypes
do
925 if otype
== mtype
then continue
926 self.add_conflict
(mtype
, otype
)
932 private fun add_conflict
(mtype
: MType, otype
: MType) do
933 if mtype
== otype
then return
934 if not self.conflicts_graph
.has_key
(mtype
) then self.conflicts_graph
[mtype
] = new HashSet[MType]
935 self.conflicts_graph
[mtype
].add
(otype
)
936 if not self.conflicts_graph
.has_key
(otype
) then self.conflicts_graph
[otype
] = new HashSet[MType]
937 self.conflicts_graph
[otype
].add
(mtype
)
941 class NaiveUnanchoredTypeColoring
942 super UnanchoredTypeColoring
946 redef fun colorize_elements
(elements
: Map[MClassType, Set[MType]]) do
948 for mclasstype
, mclasstypes
in elements
do
949 for element
in mclasstypes
do
950 coloration_result
[element
] = color
957 abstract class UnanchoredTypePerfectHashing
958 super NaiveUnanchoredTypeColoring
960 private var masks
: Map[MClassType, Int] = new HashMap[MClassType, Int]
964 redef fun colorize_elements
(elements
: Map[MClassType, Set[MType]]) do
966 for mclasstype
, mclasstypes
in elements
do
967 for element
in mclasstypes
do
968 coloration_result
[element
] = color
974 fun compute_masks
(elements
: Map[MClassType, Set[MType]]): Map[MClassType, Int] do
975 for mclasstype
, mtypes
in elements
do
976 self.masks
[mclasstype
] = compute_mask
(mtypes
)
981 private fun compute_mask
(mtypes
: Set[MType]): Int do
984 var used
= new List[Int]
985 for mtype
in mtypes
do
986 var res
= op
(mask
, self.coloration_result
[mtype
])
987 if used
.has
(res
) then
993 if used
.length
== mtypes
.length
then break
999 redef fun build_tables
(elements
: Map[MClassType, Set[MType]]): Map[MClassType, Array[nullable MType]] do
1000 var tables
= new HashMap[MClassType, Array[nullable MType]]
1002 for mclasstype
, mtypes
in elements
do
1003 var table
= new Array[nullable MType]
1004 for mtype
in mtypes
do
1005 var color
= phash
(self.coloration_result
[mtype
], masks
[mclasstype
])
1006 if table
.length
<= color
then
1007 for i
in [table
.length
.. color
[ do
1011 table
[color
] = mtype
1013 tables
[mclasstype
] = table
1018 private fun op
(mask
: Int, id
:Int): Int is abstract
1019 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
1022 class UnanchoredTypeModPerfectHashing
1023 super UnanchoredTypePerfectHashing
1025 redef fun op
(mask
, id
) do return mask
% id
1028 class UnanchoredTypeAndPerfectHashing
1029 super UnanchoredTypePerfectHashing
1031 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
1037 redef class HashSet[E
]
1038 init from
(elements
: Collection[E
]) do
1040 self.add_all
(elements
)
1044 redef class Array[E
]
1045 init from
(elements
: Collection[E
]) do
1047 self.add_all
(elements
)
1050 # Return a new Array with the elements only contened in 'self' and not in 'o'
1051 fun -(o
: Array[E
]): Array[E
] do
1052 var res
= new Array[E
]
1053 for e
in self do if not o
.has
(e
) then res
.add
(e
)
1060 # Return a linearization of a set of mtypes
1061 private fun linearize_mtypes
(mtypes
: Set[MType]): Array[MType] do
1062 var lin
= new Array[MType].from
(mtypes
)
1063 var sorter
= new TypeSorter(self)
1068 # Return a reverse linearization of a set of mtypes
1069 private fun reverse_linearize_mtypes
(mtypes
: Set[MType]): Array[MType] do
1070 var lin
= new Array[MType].from
(mtypes
)
1071 var sorter
= new ReverseTypeSorter(self)
1076 # Return super types of a `mtype` in `self`
1077 private fun super_mtypes
(mtype
: MType, mtypes
: Set[MType]): Set[MType] do
1078 if not self.super_mtypes_cache
.has_key
(mtype
) then
1079 var supers
= new HashSet[MType]
1080 for otype
in mtypes
do
1081 if otype
== mtype
then continue
1082 if mtype
.is_subtype
(self, null, otype
) then
1086 self.super_mtypes_cache
[mtype
] = supers
1088 return self.super_mtypes_cache
[mtype
]
1091 private var super_mtypes_cache
: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
1093 # Return all sub mtypes (directs and indirects) of a `mtype` in `self`
1094 private fun sub_mtypes
(mtype
: MType, mtypes
: Set[MType]): Set[MType] do
1095 if not self.sub_mtypes_cache
.has_key
(mtype
) then
1096 var subs
= new HashSet[MType]
1097 for otype
in mtypes
do
1098 if otype
== mtype
then continue
1099 if otype
.is_subtype
(self, null, mtype
) then
1103 self.sub_mtypes_cache
[mtype
] = subs
1105 return self.sub_mtypes_cache
[mtype
]
1108 private var sub_mtypes_cache
: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
1110 # Return a linearization of a set of mclasses
1111 private fun linearize_mclasses
(mclasses
: Set[MClass]): Array[MClass] do
1112 var lin
= new Array[MClass].from
(mclasses
)
1113 var sorter
= new ClassSorter(self)
1118 # Return a reverse linearization of a set of mtypes
1119 private fun reverse_linearize_mclasses
(mclasses
: Set[MClass]): Array[MClass] do
1120 var lin
= new Array[MClass].from
(mclasses
)
1121 var sorter
= new ReverseClassSorter(self)
1126 # Return all super mclasses (directs and indirects) of a `mclass` in `self`
1127 private fun super_mclasses
(mclass
: MClass): Set[MClass] do
1128 if not self.super_mclasses_cache
.has_key
(mclass
) then
1129 var supers
= new HashSet[MClass]
1130 if self.flatten_mclass_hierarchy
.has
(mclass
) then
1131 for sup
in self.flatten_mclass_hierarchy
[mclass
].greaters
do
1132 if sup
== mclass
then continue
1136 self.super_mclasses_cache
[mclass
] = supers
1138 return self.super_mclasses_cache
[mclass
]
1141 private var super_mclasses_cache
: Map[MClass, Set[MClass]] = new HashMap[MClass, Set[MClass]]
1143 # Return all parents of a `mclass` in `self`
1144 private fun parent_mclasses
(mclass
: MClass): Set[MClass] do
1145 if not self.parent_mclasses_cache
.has_key
(mclass
) then
1146 var parents
= new HashSet[MClass]
1147 if self.flatten_mclass_hierarchy
.has
(mclass
) then
1148 for sup
in self.flatten_mclass_hierarchy
[mclass
].direct_greaters
do
1149 if sup
== mclass
then continue
1153 self.parent_mclasses_cache
[mclass
] = parents
1155 return self.parent_mclasses_cache
[mclass
]
1158 private var parent_mclasses_cache
: Map[MClass, Set[MClass]] = new HashMap[MClass, Set[MClass]]
1160 # Return all sub mclasses (directs and indirects) of a `mclass` in `self`
1161 private fun sub_mclasses
(mclass
: MClass): Set[MClass] do
1162 if not self.sub_mclasses_cache
.has_key
(mclass
) then
1163 var subs
= new HashSet[MClass]
1164 if self.flatten_mclass_hierarchy
.has
(mclass
) then
1165 for sub
in self.flatten_mclass_hierarchy
[mclass
].smallers
do
1166 if sub
== mclass
then continue
1170 self.sub_mclasses_cache
[mclass
] = subs
1172 return self.sub_mclasses_cache
[mclass
]
1175 private var sub_mclasses_cache
: Map[MClass, Set[MClass]] = new HashMap[MClass, Set[MClass]]
1177 # All 'mproperties' associated to all 'mclassdefs' of `mclass`
1178 private fun properties
(mclass
: MClass): Set[MProperty] do
1179 if not self.properties_cache
.has_key
(mclass
) then
1180 var properties
= new HashSet[MProperty]
1181 var parents
= self.super_mclasses
(mclass
)
1182 for parent
in parents
do
1183 properties
.add_all
(self.properties
(parent
))
1186 for mclassdef
in mclass
.mclassdefs
do
1187 for mpropdef
in mclassdef
.mpropdefs
do
1188 properties
.add
(mpropdef
.mproperty
)
1191 self.properties_cache
[mclass
] = properties
1193 return properties_cache
[mclass
]
1196 private var properties_cache
: Map[MClass, Set[MProperty]] = new HashMap[MClass, Set[MProperty]]
1199 # A sorter for linearize list of types
1201 super AbstractSorter[MType]
1203 private var mmodule
: MModule
1205 init(mmodule
: MModule) do self.mmodule
= mmodule
1207 redef fun compare
(a
, b
) do
1210 else if a
.is_subtype
(self.mmodule
, null, b
) then
1217 # A sorter for reverse linearization
1218 class ReverseTypeSorter
1221 init(mmodule
: MModule) do end
1223 redef fun compare
(a
, b
) do
1226 else if a
.is_subtype
(self.mmodule
, null, b
) then
1233 # A sorter for linearize list of classes
1234 private class ClassSorter
1235 super AbstractSorter[MClass]
1237 var mmodule
: MModule
1239 redef fun compare
(a
, b
) do
1242 else if self.mmodule
.flatten_mclass_hierarchy
.has
(a
) and self.mmodule
.flatten_mclass_hierarchy
[a
].greaters
.has
(b
) then
1249 # A sorter for reverse linearization
1250 private class ReverseClassSorter
1251 super AbstractSorter[MClass]
1253 var mmodule
: MModule
1255 redef fun compare
(a
, b
) do
1258 else if self.mmodule
.flatten_mclass_hierarchy
.has
(a
) and self.mmodule
.flatten_mclass_hierarchy
[a
].greaters
.has
(b
) then