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
18 import rapid_type_analysis
# for type coloration
20 abstract class AbstractColoring[E
: Object]
22 private var sorter
: AbstractSorter[E
]
23 private var reverse_sorter
: AbstractSorter[E
]
25 private var core
: Set[E
] = new HashSet[E
]
26 private var crown
: Set[E
] = new HashSet[E
]
27 private var border
: Set[E
] = new HashSet[E
]
29 private var coloration_result
: Map[E
, Int] = new HashMap[E
, Int]
30 private var conflicts_graph_cache
: nullable HashMap[E
, Set[E
]]
32 init(sorter
: AbstractSorter[E
], reverse_sorter
: AbstractSorter[E
]) do
34 self.reverse_sorter
= reverse_sorter
37 fun colorize
(elements
: Collection[E
]): Map[E
, Int] do
38 # tag each element as part of group core, crown or border
43 #print "core: {core.join(", ")}"
44 #print "border: {border.join(", ")}"
45 #print "crown: {crown.join(", ")}"
47 # sort by reverse linearization order
48 var core
= new Array[E
].from
(self.core
)
49 reverse_sorter
.sort
(core
)
50 var border
= new Array[E
].from
(self.border
)
51 reverse_sorter
.sort
(border
)
52 var crown
= new Array[E
].from
(self.crown
)
53 reverse_sorter
.sort
(crown
)
56 #for k, v in conflicts_graph do
58 # print "{k}: {v.join(", ")}"
63 colorize_elements
(core
)
64 colorize_elements
(border
)
65 colorize_elements
(crown
)
67 return coloration_result
70 # Colorize a collection of elements
71 private fun colorize_elements
(elements
: Collection[E
]) do
74 for element
in elements
do
76 while not self.is_color_free
(element
, color
) do
79 coloration_result
[element
] = color
84 # Check if a related element to the element already use the color
85 private fun is_color_free
(element
: E
, color
: Int): Bool do
86 if conflicts_graph
.has_key
(element
) then
87 for st
in conflicts_graph
[element
] do
88 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
91 for st
in self.super_elements
(element
) do
92 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
97 # Tag element as core, crown or border
98 private fun tag_element
(element
: E
) do
99 # Check if sub elements are all in single inheritance
100 var all_subelements_si
= true
101 for subelem
in self.sub_elements
(element
) do
102 if self.is_element_mi
(subelem
) then
103 all_subelements_si
= false
108 # Tag as core, crown or border
109 if self.is_element_mi
(element
) then
110 core
.add_all
(self.super_elements
(element
))
112 if all_subelements_si
then
115 else if not all_subelements_si
then
116 core
.add_all
(self.super_elements
(element
))
123 # Conflicts graph of elements hierarchy (two types are in conflict if they have common subelements)
124 private fun conflicts_graph
: Map[E
, Set[E
]] do
125 if self.conflicts_graph_cache
== null then
126 self.conflicts_graph_cache
= new HashMap[E
, HashSet[E
]]
127 for t
in self.core
do
128 for i
in self.linear_extension
(t
) do
129 if t
== i
then continue
131 var lin_i
= self.linear_extension
(i
)
133 for j
in self.linear_extension
(t
) do
134 if i
== j
or j
== t
then continue
135 var lin_j
= self.linear_extension
(j
)
137 var d_ij
= lin_i
- lin_j
138 var d_ji
= lin_j
- lin_i
141 if not conflicts_graph_cache
.has_key
(ed1
) then conflicts_graph_cache
[ed1
] = new HashSet[E
]
142 # add ed1 x ed2 to conflicts graph
143 for ed2
in d_ji
do conflicts_graph_cache
[ed1
].add
(ed2
)
146 if not conflicts_graph_cache
.has_key
(ed1
) then conflicts_graph_cache
[ed1
] = new HashSet[E
]
147 # add ed1 x ed2 to conflicts graph
148 for ed2
in d_ji
do conflicts_graph_cache
[ed1
].add
(ed2
)
154 return conflicts_graph_cache
.as(not null)
157 # cache for linear_extensions
158 private var linear_extensions_cache
: Map[E
, Array[E
]] = new HashMap[E
, Array[E
]]
160 # Return a linear_extension of super_elements of the element
161 private fun linear_extension
(element
: E
): Array[E
] do
162 if not self.linear_extensions_cache
.has_key
(element
) then
163 var lin
= new Array[E
]
165 lin
.add_all
(self.super_elements
(element
))
166 self.sorter
.sort
(lin
)
167 self.linear_extensions_cache
[element
] = lin
169 return self.linear_extensions_cache
[element
]
172 # Return all super elements (directs and indirects) of an element
173 private fun super_elements
(element
: E
): Collection[E
] is abstract
175 # Return all sub elements (directs and indirects) of an element
176 private fun sub_elements
(element
: E
): Collection[E
] is abstract
178 # Is the element in multiple inheritance ?
179 private fun is_element_mi
(element
: E
): Bool is abstract
182 # MClassType coloring
184 super AbstractColoring[MType]
188 private var mmodule
: MModule
189 private var mtypes
: Set[T
]
192 private var super_elements_cache
: Map[T
, Set[T
]] = new HashMap[T
, Set[T
]]
193 private var sub_elements_cache
: Map[T
, Set[T
]] = new HashMap[T
, Set[T
]]
195 init(mainmodule
: MModule, mtypes
: Set[T
]) do
196 super(new TypeSorter(mainmodule
), new ReverseTypeSorter(mainmodule
))
197 self.mmodule
= mainmodule
202 fun build_type_tables
(mtypes
: Set[T
], colors
: Map[T
, Int]): Map[T
, Array[nullable T
]] do
203 var tables
= new HashMap[T
, Array[nullable T
]]
205 for mtype
in mtypes
do
206 var table
= new Array[nullable T
]
207 var supers
= new HashSet[T
]
208 supers
.add_all
(self.super_elements
(mtype
))
211 var color
= colors
[sup
]
212 if table
.length
<= color
then
213 for i
in [table
.length
.. color
[ do
219 tables
[mtype
] = table
224 redef fun super_elements
(element
) do
225 if not self.super_elements_cache
.has_key
(element
) then
226 var supers
= new HashSet[T
]
227 for mtype
in self.mtypes
do
228 if element
== mtype
then continue
229 if element
.is_subtype
(self.mmodule
, null, mtype
) then
233 self.super_elements_cache
[element
] = supers
235 return self.super_elements_cache
[element
]
238 # Return all direct super elements of an element
239 redef fun is_element_mi
(element
) do
240 return self.super_elements
(element
).length
> 1
243 # Return all sub elements (directs and indirects) of an element
244 redef fun sub_elements
(element
) do
245 if not self.sub_elements_cache
.has_key
(element
) then
246 var subs
= new HashSet[T
]
247 for mtype
in self.mtypes
do
248 if element
== mtype
then continue
249 if mtype
.is_subtype
(self.mmodule
, null, element
) then
253 self.sub_elements_cache
[element
] = subs
255 return self.sub_elements_cache
[element
]
259 class NaiveTypeColoring
262 init(mainmodule
: MModule, mtypes
: Set[T
]) do
263 super(mainmodule
, mtypes
)
266 # naive coloring that use incremental coloring
267 redef fun colorize_elements
(elements
) do
269 self.coloration_result
[e
] = self.coloration_result
.length
274 abstract class TypePerfectHashing
277 init(mainmodule
: MModule, mtypes
: Set[T
]) do
278 super(mainmodule
, mtypes
)
281 fun compute_masks
(elements
: Set[T
], ids
: Map[T
, Int]): Map[T
, Int] do
283 # Create super type list
284 var supers
= new HashSet[T
]
285 supers
.add_all
(self.super_elements
(e
))
287 # Compute the hashing 'mask'
288 self.coloration_result
[e
] = compute_mask
(supers
, ids
)
290 return self.coloration_result
294 fun hash_type_tables
(mtypes
: Set[T
], ids
: Map[T
, Int], masks
: Map[T
, Int]): Map[T
, Array[nullable T
]] do
295 var tables
= new HashMap[T
, Array[nullable T
]]
297 for mtype
in mtypes
do
298 var table
= new Array[nullable T
]
299 var supers
= new HashSet[T
]
300 supers
.add_all
(self.super_elements
(mtype
))
304 var color
= phash
(ids
[sup
], masks
[mtype
])
305 if table
.length
<= color
then
306 for i
in [table
.length
.. color
[ do
312 tables
[mtype
] = table
317 private fun compute_mask
(mtypes
: Set[T
], ids
: Map[T
, Int]): Int do
320 var used
= new List[Int]
322 var res
= op
(mask
, ids
[sup
])
323 if used
.has
(res
) then
329 if used
.length
== mtypes
.length
then break
335 private fun op
(mask
: Int, id
:Int): Int is abstract
336 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
339 class TypeModPerfectHashing
340 super TypePerfectHashing
341 init(mainmodule
: MModule, mtypes
: Set[T
]) do
342 super(mainmodule
, mtypes
)
344 redef fun op
(mask
, id
) do return mask
% id
347 class TypeAndPerfectHashing
348 super TypePerfectHashing
349 init(mainmodule
: MModule, mtypes
: Set[T
]) do
350 super(mainmodule
, mtypes
)
352 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
355 # A sorter for linearize list of types
357 super AbstractSorter[MType]
359 private var mmodule
: MModule
361 init(mmodule
: MModule) do self.mmodule
= mmodule
363 redef fun compare
(a
, b
) do
366 else if a
.is_subtype
(self.mmodule
, null, b
) then
373 # A sorter for reverse linearization
374 class ReverseTypeSorter
377 init(mmodule
: MModule) do end
379 redef fun compare
(a
, b
) do
382 else if a
.is_subtype
(self.mmodule
, null, b
) then
391 super AbstractColoring[MClass]
395 private var mmodule
: MModule
398 private var super_elements_cache
: Map[T
, Set[T
]] = new HashMap[T
, Set[T
]]
399 private var parent_elements_cache
: Map[T
, Set[T
]] = new HashMap[T
, Set[T
]]
400 private var sub_elements_cache
: Map[T
, Set[T
]] = new HashMap[T
, Set[T
]]
402 init(mainmodule
: MModule) do
403 super(new ClassSorter(mainmodule
), new ReverseClassSorter(mainmodule
))
404 self.mmodule
= mainmodule
408 fun build_type_tables
(mclasses
: Array[T
], colors
: Map[T
, Int]): Map[T
, Array[nullable T
]] do
409 var tables
= new HashMap[T
, Array[nullable T
]]
411 for mclasse
in mclasses
do
412 var table
= new Array[nullable T
]
413 var supers
= new HashSet[T
]
414 supers
.add_all
(self.super_elements
(mclasse
))
417 var color
= colors
[sup
]
418 if table
.length
<= color
then
419 for i
in [table
.length
.. color
[ do
425 tables
[mclasse
] = table
430 redef fun super_elements
(element
) do
431 if not self.super_elements_cache
.has_key
(element
) then
432 var supers
= new HashSet[T
]
433 if self.mmodule
.flatten_mclass_hierarchy
.has
(element
) then
434 for sup
in self.mmodule
.flatten_mclass_hierarchy
[element
].greaters
do
435 if element
== sup
then continue
439 self.super_elements_cache
[element
] = supers
441 return self.super_elements_cache
[element
]
444 private fun parent_elements
(element
: T
): Set[T
] do
445 if not self.parent_elements_cache
.has_key
(element
) then
446 var parents
= new HashSet[T
]
447 if self.mmodule
.flatten_mclass_hierarchy
.has
(element
) then
448 for parent
in self.mmodule
.flatten_mclass_hierarchy
[element
].direct_greaters
do
449 if element
== parent
then continue
453 self.parent_elements_cache
[element
] = parents
455 return self.parent_elements_cache
[element
]
458 # Return all sub elements (directs and indirects) of an element
459 redef fun sub_elements
(element
) do
460 if not self.sub_elements_cache
.has_key
(element
) then
461 var subs
= new HashSet[T
]
462 if self.mmodule
.flatten_mclass_hierarchy
.has
(element
) then
463 for sub
in self.mmodule
.flatten_mclass_hierarchy
[element
].smallers
do
467 self.sub_elements_cache
[element
] = subs
469 return self.sub_elements_cache
[element
]
472 # Return all direct super elements of an element
473 redef fun is_element_mi
(element
) do
474 if not self.mmodule
.flatten_mclass_hierarchy
.has
(element
) then return false
475 return self.mmodule
.flatten_mclass_hierarchy
[element
].direct_greaters
.length
> 1
479 # incremental coloring (very naive)
480 class NaiveClassColoring
483 init(mainmodule
: MModule) do
487 # naive coloring that use incremental coloring
488 redef fun colorize_elements
(elements
: Collection[MClass]) do
490 self.coloration_result
[e
] = self.coloration_result
.length
495 abstract class ClassPerfectHashing
498 init(mainmodule
: MModule) do
502 fun compute_masks
(elements
: Set[T
], ids
: Map[T
, Int]): Map[T
, Int] do
504 # Create super type list
505 var supers
= new HashSet[T
]
506 supers
.add_all
(self.super_elements
(e
))
508 # Compute the hashing 'mask'
509 self.coloration_result
[e
] = compute_mask
(supers
, ids
)
511 return self.coloration_result
515 fun hash_type_tables
(mtypes
: Set[T
], ids
: Map[T
, Int], masks
: Map[T
, Int]): Map[T
, Array[nullable T
]] do
516 var tables
= new HashMap[T
, Array[nullable T
]]
518 for mtype
in mtypes
do
519 var table
= new Array[nullable T
]
520 var supers
= new HashSet[T
]
521 supers
.add_all
(self.super_elements
(mtype
))
525 var color
= phash
(ids
[sup
], masks
[mtype
])
526 if table
.length
<= color
then
527 for i
in [table
.length
.. color
[ do
533 tables
[mtype
] = table
538 private fun compute_mask
(mtypes
: Set[T
], ids
: Map[T
, Int]): Int do
541 var used
= new List[Int]
543 var res
= op
(mask
, ids
[sup
])
544 if used
.has
(res
) then
550 if used
.length
== mtypes
.length
then break
556 private fun op
(mask
: Int, id
:Int): Int is abstract
557 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
560 class ClassModPerfectHashing
561 super ClassPerfectHashing
562 init(mainmodule
: MModule) do
565 redef fun op
(mask
, id
) do return mask
% id
568 class ClassAndPerfectHashing
569 super ClassPerfectHashing
570 init(mainmodule
: MModule) do
573 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
576 # A sorter for linearize list of classes
577 private class ClassSorter
578 super AbstractSorter[MClass]
582 redef fun compare
(a
, b
) do
585 else if self.mmodule
.flatten_mclass_hierarchy
.has
(a
) and self.mmodule
.flatten_mclass_hierarchy
[a
].greaters
.has
(b
) then
592 # A sorter for reverse linearization
593 private class ReverseClassSorter
594 super AbstractSorter[MClass]
598 redef fun compare
(a
, b
) do
601 else if self.mmodule
.flatten_mclass_hierarchy
.has
(a
) and self.mmodule
.flatten_mclass_hierarchy
[a
].greaters
.has
(b
) then
609 class PropertyColoring
611 type MPROP: MProperty
612 type MPROPDEF: MPropDef
614 private var class_coloring
: ClassColoring
615 private var coloration_result
: Map[MPROP, Int] = new HashMap[MPROP, Int]
617 init(class_coloring
: ClassColoring) do
618 self.class_coloring
= class_coloring
621 fun colorize
: Map[MPROP, Int] do
622 colorize_core_properties
623 colorize_crown_properties
624 return self.coloration_result
627 fun build_property_tables
: Map[MClass, Array[nullable MPROPDEF]] do
628 var tables
= new HashMap[MClass, Array[nullable MPROPDEF]]
630 for mclass
in self.class_coloring
.coloration_result
.keys
do
631 var table
= new Array[nullable MPROPDEF]
632 # first, fill table from parents by reverse linearization order
633 var parents
= new Array[MClass]
634 parents
.add_all
(self.class_coloring
.super_elements
(mclass
))
635 self.class_coloring
.reverse_sorter
.sort
(parents
)
636 for parent
in parents
do
637 for mproperty
in self.properties
(parent
) do
638 var color
= self.coloration_result
[mproperty
]
639 if table
.length
<= color
then
640 for i
in [table
.length
.. color
[ do
644 for mpropdef
in mproperty
.mpropdefs
do
645 if mpropdef
.mclassdef
.mclass
== parent
then
646 table
[color
] = mpropdef
652 # then override with local properties
653 for mproperty
in self.properties
(mclass
) do
654 var color
= self.coloration_result
[mproperty
]
655 if table
.length
<= color
then
656 for i
in [table
.length
.. color
[ do
660 for mpropdef
in mproperty
.mpropdefs
do
661 if mpropdef
.mclassdef
.mclass
== mclass
then
662 table
[color
] = mpropdef
666 tables
[mclass
] = table
671 # Colorize properties of the core hierarchy
672 private fun colorize_core_properties
do
673 var mclasses
= self.class_coloring
.core
676 for mclass
in mclasses
do
677 var color
= min_color
679 # if the class is root, get the minimal color
680 if self.class_coloring
.parent_elements
(mclass
).length
== 0 then
681 colorize_elements
(self.properties
(mclass
), color
)
683 # check last color used by parents
684 color
= max_color
(color
, self.class_coloring
.parent_elements
(mclass
))
685 # check max color used in conflicts
686 if self.class_coloring
.conflicts_graph
.has_key
(mclass
) then
687 color
= max_color
(color
, self.class_coloring
.conflicts_graph
[mclass
])
691 colorize_elements
(self.properties
(mclass
), color
)
696 # Colorize properties of the crown hierarchy
697 private fun colorize_crown_properties
do
698 for mclass
in self.class_coloring
.crown
do
699 colorize_elements
(self.properties
(mclass
), max_color
(0, self.class_coloring
.parent_elements
(mclass
)))
703 # Colorize a collection of properties given a starting color
704 private fun colorize_elements
(elements
: Collection[MPROP], start_color
: Int) do
705 for element
in elements
do
706 if self.coloration_result
.has_key
(element
) then continue
707 self.coloration_result
[element
] = start_color
712 private fun max_color
(min_color
: Int, mclasses
: Collection[MClass]): Int do
713 var max_color
= min_color
715 for mclass
in mclasses
do
716 for mproperty
in self.properties
(mclass
) do
717 var color
= min_color
718 if self.coloration_result
.has_key
(mproperty
) then
719 color
= self.coloration_result
[mproperty
]
720 if color
>= max_color
then max_color
= color
+ 1
728 private var properties_cache
: Map[MClass, Set[MPROP]] = new HashMap[MClass, Set[MPROP]]
730 # All 'mproperties' associated to all 'mclassdefs' of the class
731 private fun properties
(mclass
: MClass): Set[MPROP] do
732 if not self.properties_cache
.has_key
(mclass
) then
733 var properties
= new HashSet[MPROP]
734 var parents
= self.class_coloring
.super_elements
(mclass
)
735 for parent
in parents
do
736 properties
.add_all
(self.properties
(parent
))
739 for mclassdef
in mclass
.mclassdefs
do
740 for mpropdef
in mclassdef
.mpropdefs
do
741 var mproperty
= mpropdef
.mproperty
742 if mproperty
isa MPROP then
743 properties
.add
(mproperty
)
747 self.properties_cache
[mclass
] = properties
749 return properties_cache
[mclass
]
755 super PropertyColoring
757 redef type MPROP: MMethod
758 redef type MPROPDEF: MMethodDef
759 init(class_coloring
: ClassColoring) do end
762 # MAttribute coloring
763 class AttributeColoring
764 super PropertyColoring
766 redef type MPROP: MAttribute
767 redef type MPROPDEF: MAttributeDef
768 init(class_coloring
: ClassColoring) do end
771 # MVirtualTypeProp coloring
773 super PropertyColoring
775 redef type MPROP: MVirtualTypeProp
776 redef type MPROPDEF: MVirtualTypeDef
777 init(class_coloring
: ClassColoring) do end
780 class NaiveVTColoring
783 init(class_coloring
: ClassColoring) do end
785 redef fun colorize
: Map[MPROP, Int] do
786 var mclasses
= new HashSet[MClass]
787 mclasses
.add_all
(self.class_coloring
.core
)
788 mclasses
.add_all
(self.class_coloring
.crown
)
791 for mclass
in mclasses
do
792 min_color
= max_color
(min_color
, mclasses
)
793 colorize_elements
(self.properties
(mclass
), min_color
)
795 return self.coloration_result
799 abstract class VTPerfectHashing
802 private var masks
: Map[MClass, Int] = new HashMap[MClass, Int]
804 init(class_coloring
: ClassColoring) do end
806 redef fun colorize
: Map[MPROP, Int] do
807 var mclasses
= new HashSet[MClass]
808 mclasses
.add_all
(self.class_coloring
.core
)
809 mclasses
.add_all
(self.class_coloring
.crown
)
810 for mclass
in mclasses
do
811 var vts
= self.properties
(mclass
)
813 if coloration_result
.has_key
(vt
) then continue
814 coloration_result
[vt
] = coloration_result
.length
+ 1
817 return self.coloration_result
820 fun compute_masks
: Map[MClass, Int] do
821 var mclasses
= new HashSet[MClass]
822 mclasses
.add_all
(self.class_coloring
.core
)
823 mclasses
.add_all
(self.class_coloring
.crown
)
824 for mclass
in mclasses
do
825 self.masks
[mclass
] = compute_mask
(self.properties
(mclass
))
830 private fun compute_mask
(vts
: Set[MPROP]): Int do
833 var used
= new List[Int]
835 var res
= op
(mask
, self.coloration_result
[vt
])
836 if used
.has
(res
) then
842 if used
.length
== vts
.length
then break
848 redef fun build_property_tables
do
849 var tables
= new HashMap[MClass, Array[nullable MPROPDEF]]
851 for mclass
in self.class_coloring
.coloration_result
.keys
do
852 var table
= new Array[nullable MPROPDEF]
853 # first, fill table from parents by reverse linearization order
854 var parents
= new Array[MClass]
855 parents
.add_all
(self.class_coloring
.super_elements
(mclass
))
856 self.class_coloring
.reverse_sorter
.sort
(parents
)
857 for parent
in parents
do
858 for mproperty
in self.properties
(parent
) do
859 var color
= phash
(self.coloration_result
[mproperty
], masks
[mclass
])
860 if table
.length
<= color
then
861 for i
in [table
.length
.. color
[ do
865 for mpropdef
in mproperty
.mpropdefs
do
866 if mpropdef
.mclassdef
.mclass
== parent
then
867 table
[color
] = mpropdef
873 # then override with local properties
874 for mproperty
in self.properties
(mclass
) do
875 var color
= phash
(self.coloration_result
[mproperty
], masks
[mclass
])
876 if table
.length
<= color
then
877 for i
in [table
.length
.. color
[ do
881 for mpropdef
in mproperty
.mpropdefs
do
882 if mpropdef
.mclassdef
.mclass
== mclass
then
883 table
[color
] = mpropdef
887 tables
[mclass
] = table
892 private fun op
(mask
: Int, id
:Int): Int is abstract
893 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
897 class VTModPerfectHashing
898 super VTPerfectHashing
899 init(class_coloring
: ClassColoring) do end
900 redef fun op
(mask
, id
) do return mask
% id
903 class VTAndPerfectHashing
904 super VTPerfectHashing
905 init(class_coloring
: ClassColoring) do end
906 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
909 # MParameterType coloring
911 private var class_coloring
: ClassColoring
912 private var coloration_result
: Map[MParameterType, Int] = new HashMap[MParameterType, Int]
914 init(class_coloring
: ClassColoring) do
915 self.class_coloring
= class_coloring
918 fun colorize
: Map[MParameterType, Int] do
919 colorize_core_properties
920 colorize_crown_properties
921 return self.coloration_result
924 # Colorize properties of the core hierarchy
925 private fun colorize_core_properties
do
926 var mclasses
= self.class_coloring
.core
929 for mclass
in mclasses
do
930 var color
= min_color
932 # if the class is root, get the minimal color
933 if self.class_coloring
.parent_elements
(mclass
).length
== 0 then
934 colorize_elements
(self.fts
(mclass
), color
)
936 # check last color used by parents
937 color
= max_color
(color
, self.class_coloring
.parent_elements
(mclass
))
938 # check max color used in conflicts
939 if self.class_coloring
.conflicts_graph
.has_key
(mclass
) then
940 color
= max_color
(color
, self.class_coloring
.conflicts_graph
[mclass
])
943 colorize_elements
(self.fts
(mclass
), color
)
948 # Colorize properties of the crown hierarchy
949 private fun colorize_crown_properties
do
950 for mclass
in self.class_coloring
.crown
do
951 colorize_elements
(self.fts
(mclass
), max_color
(0, self.class_coloring
.parent_elements
(mclass
)))
955 # Colorize a collection of properties given a starting color
956 private fun colorize_elements
(elements
: Collection[MParameterType], start_color
: Int) do
957 for element
in elements
do
958 if self.coloration_result
.has_key
(element
) then continue
959 self.coloration_result
[element
] = start_color
964 private fun max_color
(min_color
: Int, mclasses
: Collection[MClass]): Int do
965 var max_color
= min_color
967 for mclass
in mclasses
do
968 for ft
in self.fts
(mclass
) do
969 var color
= min_color
970 if self.coloration_result
.has_key
(ft
) then
971 color
= self.coloration_result
[ft
]
972 if color
>= max_color
then max_color
= color
+ 1
980 private var fts_cache
: Map[MClass, Set[MParameterType]] = new HashMap[MClass, Set[MParameterType]]
982 private fun fts
(mclass
: MClass): Set[MParameterType] do
983 if not self.fts_cache
.has_key
(mclass
) then
984 var fts
= new HashSet[MParameterType]
985 var mclass_type
= mclass
.mclass_type
986 if mclass_type
isa MGenericType then
987 for ft
in mclass_type
.arguments
do
988 fts
.add
(ft
.as(MParameterType))
991 self.fts_cache
[mclass
] = fts
993 return fts_cache
[mclass
]
996 fun build_ft_tables
: Map[MClass, Array[nullable MParameterType]] do
997 var tables
= new HashMap[MClass, Array[nullable MParameterType]]
999 for mclass
in self.class_coloring
.coloration_result
.keys
do
1000 var table
= new Array[nullable MParameterType]
1002 # first, fill table from parents
1003 for parent
in self.class_coloring
.super_elements
(mclass
) do
1004 for ft
in self.fts
(parent
) do
1005 var color
= self.coloration_result
[ft
]
1006 if table
.length
<= color
then
1007 for i
in [table
.length
.. color
[ do
1015 # then override with local properties
1016 for ft
in self.fts
(mclass
) do
1017 var color
= self.coloration_result
[ft
]
1018 if table
.length
<= color
then
1019 for i
in [table
.length
.. color
[ do
1025 tables
[mclass
] = table
1031 class NaiveFTColoring
1034 init(class_coloring
: ClassColoring) do end
1036 redef fun colorize
: Map[MParameterType, Int] do
1037 var mclasses
= new HashSet[MClass]
1038 mclasses
.add_all
(self.class_coloring
.core
)
1039 mclasses
.add_all
(self.class_coloring
.crown
)
1042 for mclass
in mclasses
do
1043 min_color
= max_color
(min_color
, mclasses
)
1044 colorize_elements
(self.fts
(mclass
), min_color
)
1046 return self.coloration_result
1050 abstract class FTPerfectHashing
1053 private var masks
: Map[MClass, Int] = new HashMap[MClass, Int]
1055 init(class_coloring
: ClassColoring) do end
1057 redef fun colorize
: Map[MParameterType, Int] do
1058 var mclasses
= new HashSet[MClass]
1059 mclasses
.add_all
(self.class_coloring
.core
)
1060 mclasses
.add_all
(self.class_coloring
.crown
)
1061 for mclass
in mclasses
do
1062 for ft
in self.fts
(mclass
) do
1063 if coloration_result
.has_key
(ft
) then continue
1064 coloration_result
[ft
] = coloration_result
.length
+ 1
1067 return self.coloration_result
1070 fun compute_masks
: Map[MClass, Int] do
1071 var mclasses
= new HashSet[MClass]
1072 mclasses
.add_all
(self.class_coloring
.core
)
1073 mclasses
.add_all
(self.class_coloring
.crown
)
1074 for mclass
in mclasses
do
1075 var fts
= new HashSet[MParameterType]
1076 for parent
in self.class_coloring
.super_elements
(mclass
) do
1077 fts
.add_all
(self.fts
(parent
))
1079 fts
.add_all
(self.fts
(mclass
))
1080 self.masks
[mclass
] = compute_mask
(fts
)
1085 private fun compute_mask
(fts
: Set[MParameterType]): Int do
1088 var used
= new List[Int]
1090 var res
= op
(mask
, self.coloration_result
[ft
])
1091 if used
.has
(res
) then
1097 if used
.length
== fts
.length
then break
1103 redef fun build_ft_tables
do
1104 var tables
= new HashMap[MClass, Array[nullable MParameterType]]
1106 for mclass
in self.class_coloring
.coloration_result
.keys
do
1107 var table
= new Array[nullable MParameterType]
1109 # first, fill table from parents
1110 for parent
in self.class_coloring
.super_elements
(mclass
) do
1111 for ft
in self.fts
(parent
) do
1112 var color
= phash
(self.coloration_result
[ft
], masks
[mclass
])
1113 if table
.length
<= color
then
1114 for i
in [table
.length
.. color
[ do
1122 # then override with local properties
1123 for ft
in self.fts
(mclass
) do
1124 var color
= phash
(self.coloration_result
[ft
], masks
[mclass
])
1125 if table
.length
<= color
then
1126 for i
in [table
.length
.. color
[ do
1132 tables
[mclass
] = table
1137 private fun op
(mask
: Int, id
:Int): Int is abstract
1138 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
1141 class FTModPerfectHashing
1142 super FTPerfectHashing
1143 init(class_coloring
: ClassColoring) do end
1144 redef fun op
(mask
, id
) do return mask
% id
1147 class FTAndPerfectHashing
1148 super FTPerfectHashing
1149 init(class_coloring
: ClassColoring) do end
1150 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
1153 # Live Entries coloring
1154 class LiveEntryColoring
1156 private var coloration_result
: Map[MType, Int] = new HashMap[MType, Int]
1157 private var conflicts_graph_cache
: nullable HashMap[MType, Set[MType]]
1158 var livetypes_tables_sizes
: nullable Map[MClass, Array[Int]]
1162 fun colorize
(elements
: Collection[MType]): Map[MType, Int] do
1164 build_conflicts_graph
(elements
)
1167 colorize_elements
(elements
)
1169 return coloration_result
1173 fun build_livetype_tables
(mtypes
: Set[MType]): Map[MClass, Array[nullable Object]] do
1174 var livetypes_tables
= new HashMap[MClass, Array[nullable Object]]
1175 self.livetypes_tables_sizes
= new HashMap[MClass, Array[Int]]
1177 for mtype
in mtypes
do
1178 if mtype
isa MGenericType then
1179 var table
: Array[nullable Object]
1180 var sizes
: Array[Int]
1181 if livetypes_tables
.has_key
(mtype
.mclass
) then
1182 table
= livetypes_tables
[mtype
.mclass
]
1184 table
= new Array[nullable Object]
1185 livetypes_tables
[mtype
.mclass
] = table
1187 if livetypes_tables_sizes
.has_key
(mtype
.mclass
) then
1188 sizes
= livetypes_tables_sizes
[mtype
.mclass
]
1190 sizes
= new Array[Int]
1191 livetypes_tables_sizes
[mtype
.mclass
] = sizes
1193 build_livetype_table
(mtype
, 0, table
, sizes
)
1197 return livetypes_tables
1200 # Build live gentype table recursively
1201 private fun build_livetype_table
(mtype
: MGenericType, current_rank
: Int, table
: Array[nullable Object], sizes
: Array[Int]) do
1202 var ft
= mtype
.arguments
[current_rank
]
1203 if not self.coloration_result
.has_key
(ft
) then return
1204 var color
= self.coloration_result
[ft
]
1206 if current_rank
>= sizes
.length
then
1207 sizes
[current_rank
] = color
+ 1
1208 else if color
>= sizes
[current_rank
] then
1209 sizes
[current_rank
] = color
+ 1
1212 if color
> table
.length
then
1213 for i
in [table
.length
.. color
[ do table
[i
] = null
1216 if current_rank
== mtype
.arguments
.length
- 1 then
1217 table
[color
] = mtype
1219 var ft_table
: Array[nullable Object]
1220 if color
< table
.length
and table
[color
] != null then
1221 ft_table
= table
[color
].as(Array[nullable Object])
1223 ft_table
= new Array[nullable Object]
1225 table
[color
] = ft_table
1226 build_livetype_table
(mtype
, current_rank
+ 1, ft_table
, sizes
)
1230 # Colorize a collection of elements
1231 fun colorize_elements
(elements
: Collection[MType]) do
1234 for element
in elements
do
1235 var color
= min_color
1236 while not self.is_color_free
(element
, color
) do
1239 coloration_result
[element
] = color
1244 # Check if a related element to the element already use the color
1245 private fun is_color_free
(element
: MType, color
: Int): Bool do
1246 if conflicts_graph
.has_key
(element
) then
1247 for st
in conflicts_graph
[element
] do
1248 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
1254 # look for types in the same generic signatures
1255 private fun build_conflicts_graph
(elements
: Collection[MType]) do
1256 # regroup types by classes
1257 var genclasses
= new HashMap[MClass, Set[MType]]
1258 for e
in elements
do
1259 if e
isa MGenericType then
1260 if not genclasses
.has_key
(e
.mclass
) then
1261 genclasses
[e
.mclass
] = new HashSet[MType]
1263 genclasses
[e
.mclass
].add
(e
)
1268 self.conflicts_graph_cache
= new HashMap[MType, Set[MType]]
1269 for mclass
, mtypes
in genclasses
do
1271 for rank
in [0..mclass
.arity
[ do
1272 # for each live type
1273 for mtype
in mtypes
do
1274 var mclasstype
: MClassType
1275 if mtype
isa MNullableType then
1276 mclasstype
= mtype
.mtype
.as(MClassType)
1278 mclasstype
= mtype
.as(MClassType)
1280 var ft
= mclasstype
.arguments
[rank
]
1281 for otype
in mtypes
do
1282 if mtype
== otype
then continue
1283 var oclasstype
: MClassType
1284 if otype
isa MNullableType then
1285 oclasstype
= otype
.mtype
.as(MClassType)
1287 oclasstype
= otype
.as(MClassType)
1289 var oft
= oclasstype
.arguments
[rank
]
1290 self.add_conflict
(ft
, oft
)
1297 private fun add_conflict
(mtype
: MType, otype
: MType) do
1298 if mtype
== otype
then return
1299 if not self.conflicts_graph_cache
.has_key
(mtype
) then self.conflicts_graph_cache
[mtype
] = new HashSet[MType]
1300 self.conflicts_graph_cache
[mtype
].add
(otype
)
1301 if not self.conflicts_graph_cache
.has_key
(otype
) then self.conflicts_graph_cache
[otype
] = new HashSet[MType]
1302 self.conflicts_graph_cache
[otype
].add
(mtype
)
1304 private fun conflicts_graph
: Map[MType, Set[MType]] do return conflicts_graph_cache
.as(not null)
1307 class NaiveLiveEntryColoring
1308 super LiveEntryColoring
1312 redef fun colorize_elements
(elements
: Collection[MType]) do
1314 for element
in elements
do
1315 coloration_result
[element
] = color
1321 # live unanchored coloring
1322 class UnanchoredTypeColoring
1324 private var coloration_result
: Map[MType, Int] = new HashMap[MType, Int]
1325 private var conflicts_graph
: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
1329 fun colorize
(elements
: Map[MClassType, Set[MType]]): Map[MType, Int] do
1330 build_conflicts_graph
(elements
)
1331 colorize_elements
(elements
)
1332 return coloration_result
1335 fun build_tables
(elements
: Map[MClassType, Set[MType]]): Map[MClassType, Array[nullable MType]] do
1336 var tables
= new HashMap[MClassType, Array[nullable MType]]
1338 for mclasstype
, mtypes
in elements
do
1339 var table
= new Array[nullable MType]
1340 for mtype
in mtypes
do
1341 var color
= self.coloration_result
[mtype
]
1342 if table
.length
<= color
then
1343 for i
in [table
.length
.. color
[ do
1347 table
[color
] = mtype
1349 tables
[mclasstype
] = table
1354 # Colorize a collection of elements
1355 fun colorize_elements
(elements
: Map[MClassType, Set[MType]]) do
1357 for mclasstype
, mclasstypes
in elements
do
1358 for element
in mclasstypes
do
1359 if self.coloration_result
.has_key
(element
) then continue
1360 var color
= min_color
1361 while not self.is_color_free
(element
, color
) do
1364 coloration_result
[element
] = color
1370 # Check if a related element to the element already use the color
1371 private fun is_color_free
(element
: MType, color
: Int): Bool do
1372 if conflicts_graph
.has_key
(element
) then
1373 for st
in conflicts_graph
[element
] do
1374 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
1380 # look for unanchored types generated by the same type
1381 private fun build_conflicts_graph
(elements
: Map[MClassType, Set[MType]]) do
1382 for mclasstype
, mtypes
in elements
do
1383 for mtype
in mtypes
do
1384 for otype
in mtypes
do
1385 if otype
== mtype
then continue
1386 self.add_conflict
(mtype
, otype
)
1392 private fun add_conflict
(mtype
: MType, otype
: MType) do
1393 if mtype
== otype
then return
1394 if not self.conflicts_graph
.has_key
(mtype
) then self.conflicts_graph
[mtype
] = new HashSet[MType]
1395 self.conflicts_graph
[mtype
].add
(otype
)
1396 if not self.conflicts_graph
.has_key
(otype
) then self.conflicts_graph
[otype
] = new HashSet[MType]
1397 self.conflicts_graph
[otype
].add
(mtype
)
1401 class NaiveUnanchoredTypeColoring
1402 super UnanchoredTypeColoring
1406 redef fun colorize_elements
(elements
: Map[MClassType, Set[MType]]) do
1408 for mclasstype
, mclasstypes
in elements
do
1409 for element
in mclasstypes
do
1410 coloration_result
[element
] = color
1417 abstract class UnanchoredTypePerfectHashing
1418 super NaiveUnanchoredTypeColoring
1420 private var masks
: Map[MClassType, Int] = new HashMap[MClassType, Int]
1424 redef fun colorize_elements
(elements
: Map[MClassType, Set[MType]]) do
1426 for mclasstype
, mclasstypes
in elements
do
1427 for element
in mclasstypes
do
1428 coloration_result
[element
] = color
1434 fun compute_masks
(elements
: Map[MClassType, Set[MType]]): Map[MClassType, Int] do
1435 for mclasstype
, mtypes
in elements
do
1436 self.masks
[mclasstype
] = compute_mask
(mtypes
)
1441 private fun compute_mask
(mtypes
: Set[MType]): Int do
1444 var used
= new List[Int]
1445 for mtype
in mtypes
do
1446 var res
= op
(mask
, self.coloration_result
[mtype
])
1447 if used
.has
(res
) then
1453 if used
.length
== mtypes
.length
then break
1459 redef fun build_tables
(elements
: Map[MClassType, Set[MType]]): Map[MClassType, Array[nullable MType]] do
1460 var tables
= new HashMap[MClassType, Array[nullable MType]]
1462 for mclasstype
, mtypes
in elements
do
1463 var table
= new Array[nullable MType]
1464 for mtype
in mtypes
do
1465 var color
= phash
(self.coloration_result
[mtype
], masks
[mclasstype
])
1466 if table
.length
<= color
then
1467 for i
in [table
.length
.. color
[ do
1471 table
[color
] = mtype
1473 tables
[mclasstype
] = table
1478 private fun op
(mask
: Int, id
:Int): Int is abstract
1479 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
1482 class UnanchoredTypeModPerfectHashing
1483 super UnanchoredTypePerfectHashing
1485 redef fun op
(mask
, id
) do return mask
% id
1488 class UnanchoredTypeAndPerfectHashing
1489 super UnanchoredTypePerfectHashing
1491 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
1497 redef class HashSet[E
]
1498 init from
(elements
: Collection[E
]) do
1499 self.add_all
(elements
)
1503 redef class Array[E
]
1504 init from
(elements
: Collection[E
]) do
1505 self.add_all
(elements
)
1508 # Return a new Array with the elements only contened in 'self' and not in 'o'
1509 fun -(o
: Array[E
]): Array[E
] do
1510 var res
= new Array[E
]
1511 for e
in self do if not o
.has
(e
) then res
.add
(e
)