1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # Licensed under the Apache License, Version 2.0 (the "License");
4 # you may not use this file except in compliance with the License.
5 # You may obtain a copy of the License at
7 # http://www.apache.org/licenses/LICENSE-2.0
9 # Unless required by applicable law or agreed to in writing, software
10 # distributed under the License is distributed on an "AS IS" BASIS,
11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 # See the License for the specific language governing permissions and
13 # limitations under the License.
15 # Graph coloring tools
20 abstract class AbstractColoring[E
: Object]
22 private var core
: Set[E
] = new HashSet[E
]
23 private var crown
: Set[E
] = new HashSet[E
]
24 private var border
: Set[E
] = new HashSet[E
]
26 private var coloration_result
: Map[E
, Int] = new HashMap[E
, Int]
30 fun colorize
(elements
: Set[E
]): Map[E
, Int] do
31 tag_elements
(elements
)
32 build_conflicts_graph
(elements
)
33 colorize_elements
(core
)
34 colorize_elements
(border
)
35 colorize_elements
(crown
)
36 return coloration_result
39 # Colorize a collection of elements
40 private fun colorize_elements
(elements
: Set[E
]) do
43 var lin
= reverse_linearize
(elements
)
46 while not self.is_color_free
(element
, elements
, color
) do
49 coloration_result
[element
] = color
54 # Check if a related element to the element already use the color
55 private fun is_color_free
(element
: E
, elements
: Set[E
], color
: Int): Bool do
56 if conflicts_graph
.has_key
(element
) then
57 for st
in conflicts_graph
[element
] do
58 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
61 for st
in self.super_elements
(element
, elements
) do
62 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
67 # Tag elements as core, crown or border
68 private fun tag_elements
(elements
: Set[E
]) do
69 for element
in elements
do
70 # Check if sub elements are all in single inheritance
71 var all_subelements_si
= true
72 for subelem
in self.sub_elements
(element
, elements
) do
73 if self.is_element_mi
(subelem
, elements
) then
74 all_subelements_si
= false
79 # Tag as core, crown or border
80 if self.is_element_mi
(element
, elements
) then
81 core
.add_all
(self.super_elements
(element
, elements
))
83 if all_subelements_si
then
86 else if not all_subelements_si
then
87 core
.add_all
(self.super_elements
(element
, elements
))
95 # Conflicts graph of elements hierarchy (two types are in conflict if they have common subelements)
96 private fun build_conflicts_graph
(elements
: Set[E
]) do
97 self.conflicts_graph
= new HashMap[E
, HashSet[E
]]
98 var core
= reverse_linearize
(self.core
)
100 for i
in self.linear_extension
(t
, elements
) do
101 if t
== i
then continue
103 var lin_i
= self.linear_extension
(i
, elements
)
105 for j
in self.linear_extension
(t
, elements
) do
106 if i
== j
or j
== t
then continue
107 var lin_j
= self.linear_extension
(j
, elements
)
109 var d_ij
= lin_i
- lin_j
110 var d_ji
= lin_j
- lin_i
113 if not conflicts_graph
.has_key
(ed1
) then conflicts_graph
[ed1
] = new HashSet[E
]
114 # add ed1 x ed2 to conflicts graph
115 for ed2
in d_ji
do conflicts_graph
[ed1
].add
(ed2
)
118 if not conflicts_graph
.has_key
(ed1
) then conflicts_graph
[ed1
] = new HashSet[E
]
119 # add ed1 x ed2 to conflicts graph
120 for ed2
in d_ji
do conflicts_graph
[ed1
].add
(ed2
)
127 private var conflicts_graph
: nullable HashMap[E
, Set[E
]]
129 # cache for linear_extensions
130 private var linear_extensions_cache
: Map[E
, Array[E
]] = new HashMap[E
, Array[E
]]
132 # Return a linear_extension of super_elements of the element
133 private fun linear_extension
(element
: E
, elements
: Set[E
]): Array[E
] do
134 if not self.linear_extensions_cache
.has_key
(element
) then
135 var supers
= new HashSet[E
]
137 supers
.add_all
(self.super_elements
(element
, elements
))
138 self.linear_extensions_cache
[element
] = self.linearize
(supers
)
140 return self.linear_extensions_cache
[element
]
143 private fun super_elements
(element
: E
, elements
: Set[E
]): Set[E
] is abstract
144 private fun sub_elements
(element
: E
, elements
: Set[E
]): Set[E
] is abstract
145 private fun is_element_mi
(element
: E
, elements
: Set[E
]): Bool is abstract
146 private fun linearize
(elements
: Set[E
]): Array[E
] is abstract
147 private fun reverse_linearize
(elements
: Set[E
]): Array[E
] is abstract
150 # MClassType coloring
152 super AbstractColoring[MType]
156 private var mmodule
: MModule
158 init(mainmodule
: MModule) do self.mmodule
= mainmodule
160 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mtypes
(element
, elements
)
161 redef fun is_element_mi
(element
, elements
) do return self.super_elements
(element
, elements
).length
> 1
162 redef fun sub_elements
(element
, elements
) do do return self.mmodule
.sub_mtypes
(element
, elements
)
163 redef fun linearize
(elements
) do return self.mmodule
.linearize_mtypes
(elements
)
164 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mtypes
(elements
)
167 class NaiveTypeColoring
170 init(mainmodule
: MModule) do super
172 # naive coloring that use incremental coloring
173 redef fun colorize_elements
(elements
) do
175 self.coloration_result
[e
] = self.coloration_result
.length
180 abstract class TypePerfectHashing
183 init(mainmodule
: MModule) do super
185 fun compute_masks
(elements
: Set[T
], ids
: Map[T
, Int]): Map[T
, Int] do
187 # Create super type list
188 var supers
= new HashSet[T
]
189 supers
.add_all
(self.super_elements
(e
, elements
))
191 # Compute the hashing 'mask'
192 self.coloration_result
[e
] = compute_mask
(supers
, ids
)
194 return self.coloration_result
197 private fun compute_mask
(mtypes
: Set[T
], ids
: Map[T
, Int]): Int do
200 var used
= new List[Int]
202 var res
= op
(mask
, ids
[sup
])
203 if used
.has
(res
) then
209 if used
.length
== mtypes
.length
then break
215 private fun op
(mask
: Int, id
:Int): Int is abstract
216 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
219 class TypeModPerfectHashing
220 super TypePerfectHashing
221 init(mainmodule
: MModule) do super
222 redef fun op
(mask
, id
) do return mask
% id
225 class TypeAndPerfectHashing
226 super TypePerfectHashing
227 init(mainmodule
: MModule) do super
228 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
233 super AbstractColoring[MClass]
237 private var mmodule
: MModule
240 private var super_elements_cache
: Map[T
, Set[T
]] = new HashMap[T
, Set[T
]]
241 private var parent_elements_cache
: Map[T
, Set[T
]] = new HashMap[T
, Set[T
]]
242 private var sub_elements_cache
: Map[T
, Set[T
]] = new HashMap[T
, Set[T
]]
244 init(mainmodule
: MModule) do self.mmodule
= mainmodule
246 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mclasses
(element
)
247 fun parent_elements
(element
: MClass): Set[MClass] do return self.mmodule
.parent_mclasses
(element
)
248 redef fun is_element_mi
(element
, elements
) do return self.parent_elements
(element
).length
> 1
249 redef fun sub_elements
(element
, elements
) do do return self.mmodule
.sub_mclasses
(element
)
250 redef fun linearize
(elements
) do return self.mmodule
.linearize_mclasses
(elements
)
251 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mclasses
(elements
)
254 # incremental coloring (very naive)
255 class NaiveClassColoring
258 init(mainmodule
: MModule) do
262 # naive coloring that use incremental coloring
263 redef fun colorize_elements
(elements
) do
265 self.coloration_result
[e
] = self.coloration_result
.length
270 abstract class ClassPerfectHashing
273 init(mainmodule
: MModule) do
277 fun compute_masks
(elements
: Set[T
], ids
: Map[T
, Int]): Map[T
, Int] do
279 # Create super type list
280 var supers
= new HashSet[T
]
281 supers
.add_all
(self.super_elements
(e
, elements
))
283 # Compute the hashing 'mask'
284 self.coloration_result
[e
] = compute_mask
(supers
, ids
)
286 return self.coloration_result
289 private fun compute_mask
(mtypes
: Set[T
], ids
: Map[T
, Int]): Int do
292 var used
= new List[Int]
294 var res
= op
(mask
, ids
[sup
])
295 if used
.has
(res
) then
301 if used
.length
== mtypes
.length
then break
307 private fun op
(mask
: Int, id
:Int): Int is abstract
308 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
311 class ClassModPerfectHashing
312 super ClassPerfectHashing
313 init(mainmodule
: MModule) do
316 redef fun op
(mask
, id
) do return mask
% id
319 class ClassAndPerfectHashing
320 super ClassPerfectHashing
321 init(mainmodule
: MModule) do
324 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
328 class PropertyColoring
330 type MPROP: MProperty
331 type MPROPDEF: MPropDef
333 private var class_coloring
: ClassColoring
334 private var coloration_result
: Map[MPROP, Int] = new HashMap[MPROP, Int]
336 init(class_coloring
: ClassColoring) do
337 self.class_coloring
= class_coloring
340 fun colorize
: Map[MPROP, Int] do
341 colorize_core_properties
342 colorize_crown_properties
343 return self.coloration_result
346 fun build_property_tables
: Map[MClass, Array[nullable MPROPDEF]] do
347 var tables
= new HashMap[MClass, Array[nullable MPROPDEF]]
348 var mclasses
= self.class_coloring
.coloration_result
.keys
349 for mclass
in mclasses
do
350 var table
= new Array[nullable MPROPDEF]
351 # first, fill table from parents by reverse linearization order
352 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
353 var lin
= self.class_coloring
.reverse_linearize
(parents
)
355 for mproperty
in self.properties
(parent
) do
356 var color
= self.coloration_result
[mproperty
]
357 if table
.length
<= color
then
358 for i
in [table
.length
.. color
[ do
362 for mpropdef
in mproperty
.mpropdefs
do
363 if mpropdef
.mclassdef
.mclass
== parent
then
364 table
[color
] = mpropdef
370 # then override with local properties
371 for mproperty
in self.properties
(mclass
) do
372 var color
= self.coloration_result
[mproperty
]
373 if table
.length
<= color
then
374 for i
in [table
.length
.. color
[ do
378 for mpropdef
in mproperty
.mpropdefs
do
379 if mpropdef
.mclassdef
.mclass
== mclass
then
380 table
[color
] = mpropdef
384 tables
[mclass
] = table
389 # Colorize properties of the core hierarchy
390 private fun colorize_core_properties
do
391 var mclasses
= self.class_coloring
.core
394 for mclass
in mclasses
do
395 var color
= min_color
397 # if the class is root, get the minimal color
398 if self.class_coloring
.parent_elements
(mclass
).length
== 0 then
399 colorize_elements
(self.properties
(mclass
), color
)
401 # check last color used by parents
402 color
= max_color
(color
, self.class_coloring
.parent_elements
(mclass
))
403 # check max color used in conflicts
404 if self.class_coloring
.conflicts_graph
.has_key
(mclass
) then
405 color
= max_color
(color
, self.class_coloring
.conflicts_graph
[mclass
])
409 colorize_elements
(self.properties
(mclass
), color
)
414 # Colorize properties of the crown hierarchy
415 private fun colorize_crown_properties
do
416 for mclass
in self.class_coloring
.crown
do
417 colorize_elements
(self.properties
(mclass
), max_color
(0, self.class_coloring
.parent_elements
(mclass
)))
421 # Colorize a collection of properties given a starting color
422 private fun colorize_elements
(elements
: Collection[MPROP], start_color
: Int) do
423 for element
in elements
do
424 if self.coloration_result
.has_key
(element
) then continue
425 self.coloration_result
[element
] = start_color
430 private fun max_color
(min_color
: Int, mclasses
: Collection[MClass]): Int do
431 var max_color
= min_color
433 for mclass
in mclasses
do
434 for mproperty
in self.properties
(mclass
) do
435 var color
= min_color
436 if self.coloration_result
.has_key
(mproperty
) then
437 color
= self.coloration_result
[mproperty
]
438 if color
>= max_color
then max_color
= color
+ 1
446 private var properties_cache
: Map[MClass, Set[MPROP]] = new HashMap[MClass, Set[MPROP]]
448 # All 'mproperties' associated to all 'mclassdefs' of the class
449 private fun properties
(mclass
: MClass): Set[MPROP] do
450 if not self.properties_cache
.has_key
(mclass
) then
451 var properties
= new HashSet[MPROP]
452 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
453 for parent
in parents
do
454 properties
.add_all
(self.properties
(parent
))
457 for mclassdef
in mclass
.mclassdefs
do
458 for mpropdef
in mclassdef
.mpropdefs
do
459 var mproperty
= mpropdef
.mproperty
460 if mproperty
isa MPROP then
461 properties
.add
(mproperty
)
465 self.properties_cache
[mclass
] = properties
467 return properties_cache
[mclass
]
473 super PropertyColoring
475 redef type MPROP: MMethod
476 redef type MPROPDEF: MMethodDef
477 init(class_coloring
: ClassColoring) do end
480 # MAttribute coloring
481 class AttributeColoring
482 super PropertyColoring
484 redef type MPROP: MAttribute
485 redef type MPROPDEF: MAttributeDef
486 init(class_coloring
: ClassColoring) do end
489 # MVirtualTypeProp coloring
491 super PropertyColoring
493 redef type MPROP: MVirtualTypeProp
494 redef type MPROPDEF: MVirtualTypeDef
495 init(class_coloring
: ClassColoring) do end
498 class NaiveVTColoring
501 init(class_coloring
: ClassColoring) do end
503 redef fun colorize
: Map[MPROP, Int] do
504 var mclasses
= new HashSet[MClass]
505 mclasses
.add_all
(self.class_coloring
.core
)
506 mclasses
.add_all
(self.class_coloring
.crown
)
509 for mclass
in mclasses
do
510 min_color
= max_color
(min_color
, mclasses
)
511 colorize_elements
(self.properties
(mclass
), min_color
)
513 return self.coloration_result
517 abstract class VTPerfectHashing
520 private var masks
: Map[MClass, Int] = new HashMap[MClass, Int]
522 init(class_coloring
: ClassColoring) do end
524 redef fun colorize
: Map[MPROP, Int] do
525 var mclasses
= new HashSet[MClass]
526 mclasses
.add_all
(self.class_coloring
.core
)
527 mclasses
.add_all
(self.class_coloring
.crown
)
528 for mclass
in mclasses
do
529 var vts
= self.properties
(mclass
)
531 if coloration_result
.has_key
(vt
) then continue
532 coloration_result
[vt
] = coloration_result
.length
+ 1
535 return self.coloration_result
538 fun compute_masks
: Map[MClass, Int] do
539 var mclasses
= new HashSet[MClass]
540 mclasses
.add_all
(self.class_coloring
.core
)
541 mclasses
.add_all
(self.class_coloring
.crown
)
542 for mclass
in mclasses
do
543 self.masks
[mclass
] = compute_mask
(self.properties
(mclass
))
548 private fun compute_mask
(vts
: Set[MPROP]): Int do
551 var used
= new List[Int]
553 var res
= op
(mask
, self.coloration_result
[vt
])
554 if used
.has
(res
) then
560 if used
.length
== vts
.length
then break
566 redef fun build_property_tables
do
567 var tables
= new HashMap[MClass, Array[nullable MPROPDEF]]
569 for mclass
in self.class_coloring
.coloration_result
.keys
do
570 var table
= new Array[nullable MPROPDEF]
571 # first, fill table from parents by reverse linearization order
572 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
573 var lin
= self.class_coloring
.reverse_linearize
(parents
)
575 for mproperty
in self.properties
(parent
) do
576 var color
= phash
(self.coloration_result
[mproperty
], masks
[mclass
])
577 if table
.length
<= color
then
578 for i
in [table
.length
.. color
[ do
582 for mpropdef
in mproperty
.mpropdefs
do
583 if mpropdef
.mclassdef
.mclass
== parent
then
584 table
[color
] = mpropdef
590 # then override with local properties
591 for mproperty
in self.properties
(mclass
) do
592 var color
= phash
(self.coloration_result
[mproperty
], masks
[mclass
])
593 if table
.length
<= color
then
594 for i
in [table
.length
.. color
[ do
598 for mpropdef
in mproperty
.mpropdefs
do
599 if mpropdef
.mclassdef
.mclass
== mclass
then
600 table
[color
] = mpropdef
604 tables
[mclass
] = table
609 private fun op
(mask
: Int, id
:Int): Int is abstract
610 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
614 class VTModPerfectHashing
615 super VTPerfectHashing
616 init(class_coloring
: ClassColoring) do end
617 redef fun op
(mask
, id
) do return mask
% id
620 class VTAndPerfectHashing
621 super VTPerfectHashing
622 init(class_coloring
: ClassColoring) do end
623 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
626 # MParameterType coloring
628 private var class_coloring
: ClassColoring
629 private var coloration_result
: Map[MParameterType, Int] = new HashMap[MParameterType, Int]
631 init(class_coloring
: ClassColoring) do
632 self.class_coloring
= class_coloring
635 fun colorize
: Map[MParameterType, Int] do
636 colorize_core_properties
637 colorize_crown_properties
638 return self.coloration_result
641 # Colorize properties of the core hierarchy
642 private fun colorize_core_properties
do
643 var mclasses
= self.class_coloring
.core
646 for mclass
in mclasses
do
647 var color
= min_color
649 # if the class is root, get the minimal color
650 if self.class_coloring
.parent_elements
(mclass
).length
== 0 then
651 colorize_elements
(self.fts
(mclass
), color
)
653 # check last color used by parents
654 color
= max_color
(color
, self.class_coloring
.parent_elements
(mclass
))
655 # check max color used in conflicts
656 if self.class_coloring
.conflicts_graph
.has_key
(mclass
) then
657 color
= max_color
(color
, self.class_coloring
.conflicts_graph
[mclass
])
660 colorize_elements
(self.fts
(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.fts
(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[MParameterType], 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 ft
in self.fts
(mclass
) do
686 var color
= min_color
687 if self.coloration_result
.has_key
(ft
) then
688 color
= self.coloration_result
[ft
]
689 if color
>= max_color
then max_color
= color
+ 1
697 private var fts_cache
: Map[MClass, Set[MParameterType]] = new HashMap[MClass, Set[MParameterType]]
699 private fun fts
(mclass
: MClass): Set[MParameterType] do
700 if not self.fts_cache
.has_key
(mclass
) then
701 var fts
= new HashSet[MParameterType]
702 var mclass_type
= mclass
.mclass_type
703 if mclass_type
isa MGenericType then
704 for ft
in mclass_type
.arguments
do
705 fts
.add
(ft
.as(MParameterType))
708 self.fts_cache
[mclass
] = fts
710 return fts_cache
[mclass
]
713 fun build_ft_tables
: Map[MClass, Array[nullable MParameterType]] do
714 var tables
= new HashMap[MClass, Array[nullable MParameterType]]
716 for mclass
in self.class_coloring
.coloration_result
.keys
do
717 var table
= new Array[nullable MParameterType]
719 # first, fill table from parents
720 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
721 for parent
in parents
do
722 for ft
in self.fts
(parent
) do
723 var color
= self.coloration_result
[ft
]
724 if table
.length
<= color
then
725 for i
in [table
.length
.. color
[ do
733 # then override with local properties
734 for ft
in self.fts
(mclass
) do
735 var color
= self.coloration_result
[ft
]
736 if table
.length
<= color
then
737 for i
in [table
.length
.. color
[ do
743 tables
[mclass
] = table
749 class NaiveFTColoring
752 init(class_coloring
: ClassColoring) do end
754 redef fun colorize
: Map[MParameterType, Int] do
755 var mclasses
= new HashSet[MClass]
756 mclasses
.add_all
(self.class_coloring
.core
)
757 mclasses
.add_all
(self.class_coloring
.crown
)
760 for mclass
in mclasses
do
761 min_color
= max_color
(min_color
, mclasses
)
762 colorize_elements
(self.fts
(mclass
), min_color
)
764 return self.coloration_result
768 abstract class FTPerfectHashing
771 private var masks
: Map[MClass, Int] = new HashMap[MClass, Int]
773 init(class_coloring
: ClassColoring) do end
775 redef fun colorize
: Map[MParameterType, Int] do
776 var mclasses
= new HashSet[MClass]
777 mclasses
.add_all
(self.class_coloring
.core
)
778 mclasses
.add_all
(self.class_coloring
.crown
)
779 for mclass
in mclasses
do
780 for ft
in self.fts
(mclass
) do
781 if coloration_result
.has_key
(ft
) then continue
782 coloration_result
[ft
] = coloration_result
.length
+ 1
785 return self.coloration_result
788 fun compute_masks
: Map[MClass, Int] do
789 var mclasses
= new HashSet[MClass]
790 mclasses
.add_all
(self.class_coloring
.core
)
791 mclasses
.add_all
(self.class_coloring
.crown
)
792 for mclass
in mclasses
do
793 var fts
= new HashSet[MParameterType]
794 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
795 for parent
in parents
do
796 fts
.add_all
(self.fts
(parent
))
798 fts
.add_all
(self.fts
(mclass
))
799 self.masks
[mclass
] = compute_mask
(fts
)
804 private fun compute_mask
(fts
: Set[MParameterType]): Int do
807 var used
= new List[Int]
809 var res
= op
(mask
, self.coloration_result
[ft
])
810 if used
.has
(res
) then
816 if used
.length
== fts
.length
then break
822 redef fun build_ft_tables
do
823 var tables
= new HashMap[MClass, Array[nullable MParameterType]]
825 for mclass
in self.class_coloring
.coloration_result
.keys
do
826 var table
= new Array[nullable MParameterType]
828 # first, fill table from parents
829 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
830 for parent
in parents
do
831 for ft
in self.fts
(parent
) do
832 var color
= phash
(self.coloration_result
[ft
], masks
[mclass
])
833 if table
.length
<= color
then
834 for i
in [table
.length
.. color
[ do
842 # then override with local properties
843 for ft
in self.fts
(mclass
) do
844 var color
= phash
(self.coloration_result
[ft
], masks
[mclass
])
845 if table
.length
<= color
then
846 for i
in [table
.length
.. color
[ do
852 tables
[mclass
] = table
857 private fun op
(mask
: Int, id
:Int): Int is abstract
858 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
861 class FTModPerfectHashing
862 super FTPerfectHashing
863 init(class_coloring
: ClassColoring) do end
864 redef fun op
(mask
, id
) do return mask
% id
867 class FTAndPerfectHashing
868 super FTPerfectHashing
869 init(class_coloring
: ClassColoring) do end
870 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
873 # Live Entries coloring
874 class LiveEntryColoring
876 private var coloration_result
: Map[MType, Int] = new HashMap[MType, Int]
877 private var conflicts_graph_cache
: nullable HashMap[MType, Set[MType]]
878 var livetypes_tables_sizes
: nullable Map[MClass, Array[Int]]
882 fun colorize
(elements
: Collection[MType]): Map[MType, Int] do
884 build_conflicts_graph
(elements
)
887 colorize_elements
(elements
)
889 return coloration_result
893 fun build_livetype_tables
(mtypes
: Set[MType]): Map[MClass, Array[nullable Object]] do
894 var livetypes_tables
= new HashMap[MClass, Array[nullable Object]]
895 self.livetypes_tables_sizes
= new HashMap[MClass, Array[Int]]
897 for mtype
in mtypes
do
898 if mtype
isa MGenericType then
899 var table
: Array[nullable Object]
900 var sizes
: Array[Int]
901 if livetypes_tables
.has_key
(mtype
.mclass
) then
902 table
= livetypes_tables
[mtype
.mclass
]
904 table
= new Array[nullable Object]
905 livetypes_tables
[mtype
.mclass
] = table
907 if livetypes_tables_sizes
.has_key
(mtype
.mclass
) then
908 sizes
= livetypes_tables_sizes
[mtype
.mclass
]
910 sizes
= new Array[Int]
911 livetypes_tables_sizes
[mtype
.mclass
] = sizes
913 build_livetype_table
(mtype
, 0, table
, sizes
)
917 return livetypes_tables
920 # Build live gentype table recursively
921 private fun build_livetype_table
(mtype
: MGenericType, current_rank
: Int, table
: Array[nullable Object], sizes
: Array[Int]) do
922 var ft
= mtype
.arguments
[current_rank
]
923 if not self.coloration_result
.has_key
(ft
) then return
924 var color
= self.coloration_result
[ft
]
926 if current_rank
>= sizes
.length
then
927 sizes
[current_rank
] = color
+ 1
928 else if color
>= sizes
[current_rank
] then
929 sizes
[current_rank
] = color
+ 1
932 if color
> table
.length
then
933 for i
in [table
.length
.. color
[ do table
[i
] = null
936 if current_rank
== mtype
.arguments
.length
- 1 then
939 var ft_table
: Array[nullable Object]
940 if color
< table
.length
and table
[color
] != null then
941 ft_table
= table
[color
].as(Array[nullable Object])
943 ft_table
= new Array[nullable Object]
945 table
[color
] = ft_table
946 build_livetype_table
(mtype
, current_rank
+ 1, ft_table
, sizes
)
950 # Colorize a collection of elements
951 fun colorize_elements
(elements
: Collection[MType]) do
954 for element
in elements
do
955 var color
= min_color
956 while not self.is_color_free
(element
, color
) do
959 coloration_result
[element
] = color
964 # Check if a related element to the element already use the color
965 private fun is_color_free
(element
: MType, color
: Int): Bool do
966 if conflicts_graph
.has_key
(element
) then
967 for st
in conflicts_graph
[element
] do
968 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
974 # look for types in the same generic signatures
975 private fun build_conflicts_graph
(elements
: Collection[MType]) do
976 # regroup types by classes
977 var genclasses
= new HashMap[MClass, Set[MType]]
979 if e
isa MGenericType then
980 if not genclasses
.has_key
(e
.mclass
) then
981 genclasses
[e
.mclass
] = new HashSet[MType]
983 genclasses
[e
.mclass
].add
(e
)
988 self.conflicts_graph_cache
= new HashMap[MType, Set[MType]]
989 for mclass
, mtypes
in genclasses
do
991 for rank
in [0..mclass
.arity
[ do
993 for mtype
in mtypes
do
994 var mclasstype
: MClassType
995 if mtype
isa MNullableType then
996 mclasstype
= mtype
.mtype
.as(MClassType)
998 mclasstype
= mtype
.as(MClassType)
1000 var ft
= mclasstype
.arguments
[rank
]
1001 for otype
in mtypes
do
1002 if mtype
== otype
then continue
1003 var oclasstype
: MClassType
1004 if otype
isa MNullableType then
1005 oclasstype
= otype
.mtype
.as(MClassType)
1007 oclasstype
= otype
.as(MClassType)
1009 var oft
= oclasstype
.arguments
[rank
]
1010 self.add_conflict
(ft
, oft
)
1017 private fun add_conflict
(mtype
: MType, otype
: MType) do
1018 if mtype
== otype
then return
1019 if not self.conflicts_graph_cache
.has_key
(mtype
) then self.conflicts_graph_cache
[mtype
] = new HashSet[MType]
1020 self.conflicts_graph_cache
[mtype
].add
(otype
)
1021 if not self.conflicts_graph_cache
.has_key
(otype
) then self.conflicts_graph_cache
[otype
] = new HashSet[MType]
1022 self.conflicts_graph_cache
[otype
].add
(mtype
)
1024 private fun conflicts_graph
: Map[MType, Set[MType]] do return conflicts_graph_cache
.as(not null)
1027 class NaiveLiveEntryColoring
1028 super LiveEntryColoring
1032 redef fun colorize_elements
(elements
: Collection[MType]) do
1034 for element
in elements
do
1035 coloration_result
[element
] = color
1041 # live unanchored coloring
1042 class UnanchoredTypeColoring
1044 private var coloration_result
: Map[MType, Int] = new HashMap[MType, Int]
1045 private var conflicts_graph
: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
1049 fun colorize
(elements
: Map[MClassType, Set[MType]]): Map[MType, Int] do
1050 build_conflicts_graph
(elements
)
1051 colorize_elements
(elements
)
1052 return coloration_result
1055 fun build_tables
(elements
: Map[MClassType, Set[MType]]): Map[MClassType, Array[nullable MType]] do
1056 var tables
= new HashMap[MClassType, Array[nullable MType]]
1058 for mclasstype
, mtypes
in elements
do
1059 var table
= new Array[nullable MType]
1060 for mtype
in mtypes
do
1061 var color
= self.coloration_result
[mtype
]
1062 if table
.length
<= color
then
1063 for i
in [table
.length
.. color
[ do
1067 table
[color
] = mtype
1069 tables
[mclasstype
] = table
1074 # Colorize a collection of elements
1075 fun colorize_elements
(elements
: Map[MClassType, Set[MType]]) do
1077 for mclasstype
, mclasstypes
in elements
do
1078 for element
in mclasstypes
do
1079 if self.coloration_result
.has_key
(element
) then continue
1080 var color
= min_color
1081 while not self.is_color_free
(element
, color
) do
1084 coloration_result
[element
] = color
1090 # Check if a related element to the element already use the color
1091 private fun is_color_free
(element
: MType, color
: Int): Bool do
1092 if conflicts_graph
.has_key
(element
) then
1093 for st
in conflicts_graph
[element
] do
1094 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
1100 # look for unanchored types generated by the same type
1101 private fun build_conflicts_graph
(elements
: Map[MClassType, Set[MType]]) do
1102 for mclasstype
, mtypes
in elements
do
1103 for mtype
in mtypes
do
1104 for otype
in mtypes
do
1105 if otype
== mtype
then continue
1106 self.add_conflict
(mtype
, otype
)
1112 private fun add_conflict
(mtype
: MType, otype
: MType) do
1113 if mtype
== otype
then return
1114 if not self.conflicts_graph
.has_key
(mtype
) then self.conflicts_graph
[mtype
] = new HashSet[MType]
1115 self.conflicts_graph
[mtype
].add
(otype
)
1116 if not self.conflicts_graph
.has_key
(otype
) then self.conflicts_graph
[otype
] = new HashSet[MType]
1117 self.conflicts_graph
[otype
].add
(mtype
)
1121 class NaiveUnanchoredTypeColoring
1122 super UnanchoredTypeColoring
1126 redef fun colorize_elements
(elements
: Map[MClassType, Set[MType]]) do
1128 for mclasstype
, mclasstypes
in elements
do
1129 for element
in mclasstypes
do
1130 coloration_result
[element
] = color
1137 abstract class UnanchoredTypePerfectHashing
1138 super NaiveUnanchoredTypeColoring
1140 private var masks
: Map[MClassType, Int] = new HashMap[MClassType, Int]
1144 redef fun colorize_elements
(elements
: Map[MClassType, Set[MType]]) do
1146 for mclasstype
, mclasstypes
in elements
do
1147 for element
in mclasstypes
do
1148 coloration_result
[element
] = color
1154 fun compute_masks
(elements
: Map[MClassType, Set[MType]]): Map[MClassType, Int] do
1155 for mclasstype
, mtypes
in elements
do
1156 self.masks
[mclasstype
] = compute_mask
(mtypes
)
1161 private fun compute_mask
(mtypes
: Set[MType]): Int do
1164 var used
= new List[Int]
1165 for mtype
in mtypes
do
1166 var res
= op
(mask
, self.coloration_result
[mtype
])
1167 if used
.has
(res
) then
1173 if used
.length
== mtypes
.length
then break
1179 redef 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
= phash
(self.coloration_result
[mtype
], masks
[mclasstype
])
1186 if table
.length
<= color
then
1187 for i
in [table
.length
.. color
[ do
1191 table
[color
] = mtype
1193 tables
[mclasstype
] = table
1198 private fun op
(mask
: Int, id
:Int): Int is abstract
1199 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
1202 class UnanchoredTypeModPerfectHashing
1203 super UnanchoredTypePerfectHashing
1205 redef fun op
(mask
, id
) do return mask
% id
1208 class UnanchoredTypeAndPerfectHashing
1209 super UnanchoredTypePerfectHashing
1211 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
1217 redef class HashSet[E
]
1218 init from
(elements
: Collection[E
]) do
1220 self.add_all
(elements
)
1224 redef class Array[E
]
1225 init from
(elements
: Collection[E
]) do
1227 self.add_all
(elements
)
1230 # Return a new Array with the elements only contened in 'self' and not in 'o'
1231 fun -(o
: Array[E
]): Array[E
] do
1232 var res
= new Array[E
]
1233 for e
in self do if not o
.has
(e
) then res
.add
(e
)
1240 # Return a linearization of a set of mtypes
1241 private fun linearize_mtypes
(mtypes
: Set[MType]): Array[MType] do
1242 var lin
= new Array[MType].from
(mtypes
)
1243 var sorter
= new TypeSorter(self)
1248 # Return a reverse linearization of a set of mtypes
1249 private fun reverse_linearize_mtypes
(mtypes
: Set[MType]): Array[MType] do
1250 var lin
= new Array[MType].from
(mtypes
)
1251 var sorter
= new ReverseTypeSorter(self)
1256 # Return super types of a `mtype` in `self`
1257 private fun super_mtypes
(mtype
: MType, mtypes
: Set[MType]): Set[MType] do
1258 if not self.super_mtypes_cache
.has_key
(mtype
) then
1259 var supers
= new HashSet[MType]
1260 for otype
in mtypes
do
1261 if otype
== mtype
then continue
1262 if mtype
.is_subtype
(self, null, otype
) then
1266 self.super_mtypes_cache
[mtype
] = supers
1268 return self.super_mtypes_cache
[mtype
]
1271 private var super_mtypes_cache
: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
1273 # Return all sub mtypes (directs and indirects) of a `mtype` in `self`
1274 private fun sub_mtypes
(mtype
: MType, mtypes
: Set[MType]): Set[MType] do
1275 if not self.sub_mtypes_cache
.has_key
(mtype
) then
1276 var subs
= new HashSet[MType]
1277 for otype
in mtypes
do
1278 if otype
== mtype
then continue
1279 if otype
.is_subtype
(self, null, mtype
) then
1283 self.sub_mtypes_cache
[mtype
] = subs
1285 return self.sub_mtypes_cache
[mtype
]
1288 private var sub_mtypes_cache
: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
1290 # Return a linearization of a set of mclasses
1291 private fun linearize_mclasses
(mclasses
: Set[MClass]): Array[MClass] do
1292 var lin
= new Array[MClass].from
(mclasses
)
1293 var sorter
= new ClassSorter(self)
1298 # Return a reverse linearization of a set of mtypes
1299 private fun reverse_linearize_mclasses
(mclasses
: Set[MClass]): Array[MClass] do
1300 var lin
= new Array[MClass].from
(mclasses
)
1301 var sorter
= new ReverseClassSorter(self)
1306 # Return all super mclasses (directs and indirects) of a `mclass` in `self`
1307 private fun super_mclasses
(mclass
: MClass): Set[MClass] do
1308 if not self.super_mclasses_cache
.has_key
(mclass
) then
1309 var supers
= new HashSet[MClass]
1310 if self.flatten_mclass_hierarchy
.has
(mclass
) then
1311 for sup
in self.flatten_mclass_hierarchy
[mclass
].greaters
do
1312 if sup
== mclass
then continue
1316 self.super_mclasses_cache
[mclass
] = supers
1318 return self.super_mclasses_cache
[mclass
]
1321 private var super_mclasses_cache
: Map[MClass, Set[MClass]] = new HashMap[MClass, Set[MClass]]
1323 # Return all parents of a `mclass` in `self`
1324 private fun parent_mclasses
(mclass
: MClass): Set[MClass] do
1325 if not self.parent_mclasses_cache
.has_key
(mclass
) then
1326 var parents
= new HashSet[MClass]
1327 if self.flatten_mclass_hierarchy
.has
(mclass
) then
1328 for sup
in self.flatten_mclass_hierarchy
[mclass
].direct_greaters
do
1329 if sup
== mclass
then continue
1333 self.parent_mclasses_cache
[mclass
] = parents
1335 return self.parent_mclasses_cache
[mclass
]
1338 private var parent_mclasses_cache
: Map[MClass, Set[MClass]] = new HashMap[MClass, Set[MClass]]
1340 # Return all sub mclasses (directs and indirects) of a `mclass` in `self`
1341 private fun sub_mclasses
(mclass
: MClass): Set[MClass] do
1342 if not self.sub_mclasses_cache
.has_key
(mclass
) then
1343 var subs
= new HashSet[MClass]
1344 if self.flatten_mclass_hierarchy
.has
(mclass
) then
1345 for sub
in self.flatten_mclass_hierarchy
[mclass
].smallers
do
1346 if sub
== mclass
then continue
1350 self.sub_mclasses_cache
[mclass
] = subs
1352 return self.sub_mclasses_cache
[mclass
]
1355 private var sub_mclasses_cache
: Map[MClass, Set[MClass]] = new HashMap[MClass, Set[MClass]]
1357 # All 'mproperties' associated to all 'mclassdefs' of `mclass`
1358 private fun properties
(mclass
: MClass): Set[MProperty] do
1359 if not self.properties_cache
.has_key
(mclass
) then
1360 var properties
= new HashSet[MProperty]
1361 var parents
= self.super_mclasses
(mclass
)
1362 for parent
in parents
do
1363 properties
.add_all
(self.properties
(parent
))
1366 for mclassdef
in mclass
.mclassdefs
do
1367 for mpropdef
in mclassdef
.mpropdefs
do
1368 properties
.add
(mpropdef
.mproperty
)
1371 self.properties_cache
[mclass
] = properties
1373 return properties_cache
[mclass
]
1376 private var properties_cache
: Map[MClass, Set[MProperty]] = new HashMap[MClass, Set[MProperty]]
1379 # A sorter for linearize list of types
1381 super AbstractSorter[MType]
1383 private var mmodule
: MModule
1385 init(mmodule
: MModule) do self.mmodule
= mmodule
1387 redef fun compare
(a
, b
) do
1390 else if a
.is_subtype
(self.mmodule
, null, b
) then
1397 # A sorter for reverse linearization
1398 class ReverseTypeSorter
1401 init(mmodule
: MModule) do end
1403 redef fun compare
(a
, b
) do
1406 else if a
.is_subtype
(self.mmodule
, null, b
) then
1413 # A sorter for linearize list of classes
1414 private class ClassSorter
1415 super AbstractSorter[MClass]
1417 var mmodule
: MModule
1419 redef fun compare
(a
, b
) do
1422 else if self.mmodule
.flatten_mclass_hierarchy
.has
(a
) and self.mmodule
.flatten_mclass_hierarchy
[a
].greaters
.has
(b
) then
1429 # A sorter for reverse linearization
1430 private class ReverseClassSorter
1431 super AbstractSorter[MClass]
1433 var mmodule
: MModule
1435 redef fun compare
(a
, b
) do
1438 else if self.mmodule
.flatten_mclass_hierarchy
.has
(a
) and self.mmodule
.flatten_mclass_hierarchy
[a
].greaters
.has
(b
) then