1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # Licensed under the Apache License, Version 2.0 (the "License");
4 # you may not use this file except in compliance with the License.
5 # You may obtain a copy of the License at
7 # http://www.apache.org/licenses/LICENSE-2.0
9 # Unless required by applicable law or agreed to in writing, software
10 # distributed under the License is distributed on an "AS IS" BASIS,
11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 # See the License for the specific language governing permissions and
13 # limitations under the License.
15 # Graph coloring tools
23 # Unic ids or each Mtype
24 var ids
: Map[MType, Int] = new HashMap[MType, Int]
25 # Fixed positions of each MType in all tables
26 var pos
: Map[MType, Int] = new HashMap[MType, Int]
31 # Masks used by hash function
32 var masks
: Map[MType, Int] = new HashMap[MType, Int]
33 # Positions of each MType for each tables
34 var hashes
: Map[MType, Map[MType, Int]] = new HashMap[MType, Map[MType, Int]]
38 # Unic ids or each MClass
39 var ids
: Map[MClass, Int] = new HashMap[MClass, Int]
40 # Fixed positions of each MClass in all tables
41 var pos
: Map[MClass, Int] = new HashMap[MClass, Int]
46 # Masks used by hash function
47 var masks
: Map[MClass, Int] = new HashMap[MClass, Int]
48 # Positions of each MClass for each tables
49 var hashes
: Map[MClass, Map[MClass, Int]] = new HashMap[MClass, Map[MClass, Int]]
54 abstract class TypeLayoutBuilder
56 type LAYOUT: TypeLayout
58 private var mmodule
: MModule
59 init(mmodule
: MModule) do self.mmodule
= mmodule
61 # Compute mtypes ids and position
62 fun build_layout
(mtypes
: Set[MType]): LAYOUT is abstract
64 # Give each MType a unic id using a descending linearization of the `mtypes` set
65 private fun compute_ids
(mtypes
: Set[MType]): Map[MType, Int] do
66 var ids
= new HashMap[MType, Int]
67 var lin
= self.mmodule
.reverse_linearize_mtypes
(mtypes
)
69 ids
[mtype
] = ids
.length
75 # Layout builder for MType using Binary Matrix (BM)
76 class BMTypeLayoutBuilder
77 super TypeLayoutBuilder
79 init(mmodule
: MModule) do super
81 # Compute mtypes ids and position using BM
82 redef fun build_layout
(mtypes
: Set[MType]): TypeLayout do
83 var result
= new TypeLayout
84 result
.ids
= self.compute_ids
(mtypes
)
85 result
.pos
= result
.ids
90 # Layout builder for MType using Coloring (CL)
91 class CLTypeLayoutBuilder
92 super TypeLayoutBuilder
94 private var colorer
: MTypeColorer
96 init(mmodule
: MModule) do
98 self.colorer
= new MTypeColorer(mmodule
)
101 # Compute mtypes ids and position using BM
102 redef fun build_layout
(mtypes
) do
103 var result
= new TypeLayout
104 result
.ids
= self.compute_ids
(mtypes
)
105 result
.pos
= self.colorer
.colorize
(mtypes
)
110 # Layout builder for MType using Perfect Hashing (PH)
111 class PHTypeLayoutBuilder
112 super TypeLayoutBuilder
114 redef type LAYOUT: PHTypeLayout
116 private var hasher
: MTypeHasher
118 init(mmodule
: MModule, operator
: PHOperator) do
120 self.hasher
= new MTypeHasher(mmodule
, operator
)
123 # Compute mtypes ids and position using BM
124 redef fun build_layout
(mtypes
) do
125 var result
= new PHTypeLayout
126 result
.ids
= self.compute_ids
(mtypes
)
127 result
.masks
= self.hasher
.compute_masks
(mtypes
, result
.ids
)
128 result
.hashes
= self.hasher
.compute_hashes
(mtypes
, result
.ids
, result
.masks
)
132 # Ids start from 1 instead of 0
133 redef fun compute_ids
(mtypes
) do
134 var ids
= new HashMap[MType, Int]
135 var lin
= self.mmodule
.reverse_linearize_mtypes
(mtypes
)
137 ids
[mtype
] = ids
.length
+ 1
143 abstract class ClassLayoutBuilder
145 type LAYOUT: ClassLayout
147 private var mmodule
: MModule
148 init(mmodule
: MModule) do self.mmodule
= mmodule
150 # Compute mclasses ids and position
151 fun build_layout
(mclasses
: Set[MClass]): LAYOUT is abstract
153 # Give each MClass a unic id using a descending linearization of the `mclasses` set
154 private fun compute_ids
(mclasses
: Set[MClass]): Map[MClass, Int] do
155 var ids
= new HashMap[MClass, Int]
156 var lin
= self.mmodule
.reverse_linearize_mclasses
(mclasses
)
158 ids
[mclass
] = ids
.length
164 # Layout builder for MClass using Binary Matrix (BM)
165 class BMClassLayoutBuilder
166 super ClassLayoutBuilder
168 init(mmodule
: MModule) do super
170 # Compute mclasses ids and position using BM
171 redef fun build_layout
(mclasses
: Set[MClass]): LAYOUT do
172 var result
= new ClassLayout
173 result
.ids
= self.compute_ids
(mclasses
)
174 result
.pos
= result
.ids
179 # Layout builder for MClass using Coloring (CL)
180 class CLClassLayoutBuilder
181 super ClassLayoutBuilder
183 private var colorer
: MClassColorer
185 init(mmodule
: MModule) do
187 self.colorer
= new MClassColorer(mmodule
)
190 # Compute mclasses ids and position using BM
191 redef fun build_layout
(mclasses
) do
192 var result
= new ClassLayout
193 result
.ids
= self.compute_ids
(mclasses
)
194 result
.pos
= self.colorer
.colorize
(mclasses
)
199 # Layout builder for MClass using Perfect Hashing (PH)
200 class PHClassLayoutBuilder
201 super ClassLayoutBuilder
203 redef type LAYOUT: PHClassLayout
205 private var hasher
: MClassHasher
207 init(mmodule
: MModule, operator
: PHOperator) do
209 self.hasher
= new MClassHasher(mmodule
, operator
)
212 # Compute mclasses ids and position using BM
213 redef fun build_layout
(mclasses
) do
214 var result
= new PHClassLayout
215 result
.ids
= self.compute_ids
(mclasses
)
216 result
.masks
= self.hasher
.compute_masks
(mclasses
, result
.ids
)
217 result
.hashes
= self.hasher
.compute_hashes
(mclasses
, result
.ids
, result
.masks
)
221 # Ids start from 1 instead of 0
222 redef fun compute_ids
(mclasses
) do
223 var ids
= new HashMap[MClass, Int]
224 var lin
= self.mmodule
.reverse_linearize_mclasses
(mclasses
)
226 ids
[mclass
] = ids
.length
+ 1
234 abstract class AbstractColorer[E
: Object]
236 private var core
: Set[E
] = new HashSet[E
]
237 private var crown
: Set[E
] = new HashSet[E
]
238 private var border
: Set[E
] = new HashSet[E
]
240 private var coloration_result
: Map[E
, Int] = new HashMap[E
, Int]
244 fun colorize
(elements
: Set[E
]): Map[E
, Int] do
245 tag_elements
(elements
)
246 build_conflicts_graph
(elements
)
247 colorize_elements
(core
)
248 colorize_elements
(border
)
249 colorize_elements
(crown
)
250 return coloration_result
253 # Colorize a collection of elements
254 private fun colorize_elements
(elements
: Set[E
]) do
257 var lin
= reverse_linearize
(elements
)
258 for element
in lin
do
259 var color
= min_color
260 while not self.is_color_free
(element
, elements
, color
) do
263 coloration_result
[element
] = color
268 # Check if a related element to the element already use the color
269 private fun is_color_free
(element
: E
, elements
: Set[E
], color
: Int): Bool do
270 if conflicts_graph
.has_key
(element
) then
271 for st
in conflicts_graph
[element
] do
272 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
275 for st
in self.super_elements
(element
, elements
) do
276 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
281 # Tag elements as core, crown or border
282 private fun tag_elements
(elements
: Set[E
]) do
283 for element
in elements
do
284 # Check if sub elements are all in single inheritance
285 var all_subelements_si
= true
286 for subelem
in self.sub_elements
(element
, elements
) do
287 if self.is_element_mi
(subelem
, elements
) then
288 all_subelements_si
= false
293 # Tag as core, crown or border
294 if self.is_element_mi
(element
, elements
) then
295 core
.add_all
(self.super_elements
(element
, elements
))
297 if all_subelements_si
then
300 else if not all_subelements_si
then
301 core
.add_all
(self.super_elements
(element
, elements
))
309 # Conflicts graph of elements hierarchy (two types are in conflict if they have common subelements)
310 private fun build_conflicts_graph
(elements
: Set[E
]) do
311 self.conflicts_graph
= new HashMap[E
, HashSet[E
]]
312 var core
= reverse_linearize
(self.core
)
314 for i
in self.linear_extension
(t
, elements
) do
315 if t
== i
then continue
317 var lin_i
= self.linear_extension
(i
, elements
)
319 for j
in self.linear_extension
(t
, elements
) do
320 if i
== j
or j
== t
then continue
321 var lin_j
= self.linear_extension
(j
, elements
)
323 var d_ij
= lin_i
- lin_j
324 var d_ji
= lin_j
- lin_i
327 if not conflicts_graph
.has_key
(ed1
) then conflicts_graph
[ed1
] = new HashSet[E
]
328 # add ed1 x ed2 to conflicts graph
329 for ed2
in d_ji
do conflicts_graph
[ed1
].add
(ed2
)
332 if not conflicts_graph
.has_key
(ed1
) then conflicts_graph
[ed1
] = new HashSet[E
]
333 # add ed1 x ed2 to conflicts graph
334 for ed2
in d_ji
do conflicts_graph
[ed1
].add
(ed2
)
341 private var conflicts_graph
: nullable HashMap[E
, Set[E
]]
343 # cache for linear_extensions
344 private var linear_extensions_cache
: Map[E
, Array[E
]] = new HashMap[E
, Array[E
]]
346 # Return a linear_extension of super_elements of the element
347 private fun linear_extension
(element
: E
, elements
: Set[E
]): Array[E
] do
348 if not self.linear_extensions_cache
.has_key
(element
) then
349 var supers
= new HashSet[E
]
351 supers
.add_all
(self.super_elements
(element
, elements
))
352 self.linear_extensions_cache
[element
] = self.linearize
(supers
)
354 return self.linear_extensions_cache
[element
]
357 private fun super_elements
(element
: E
, elements
: Set[E
]): Set[E
] is abstract
358 private fun sub_elements
(element
: E
, elements
: Set[E
]): Set[E
] is abstract
359 private fun is_element_mi
(element
: E
, elements
: Set[E
]): Bool is abstract
360 private fun linearize
(elements
: Set[E
]): Array[E
] is abstract
361 private fun reverse_linearize
(elements
: Set[E
]): Array[E
] is abstract
365 private class MTypeColorer
366 super AbstractColorer[MType]
370 init(mmodule
: MModule) do self.mmodule
= mmodule
372 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mtypes
(element
, elements
)
373 redef fun is_element_mi
(element
, elements
) do return self.super_elements
(element
, elements
).length
> 1
374 redef fun sub_elements
(element
, elements
) do do return self.mmodule
.sub_mtypes
(element
, elements
)
375 redef fun linearize
(elements
) do return self.mmodule
.linearize_mtypes
(elements
)
376 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mtypes
(elements
)
380 private class MClassColorer
381 super AbstractColorer[MClass]
383 private var mmodule
: MModule
385 init(mmodule
: MModule) do self.mmodule
= mmodule
387 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mclasses
(element
)
388 fun parent_elements
(element
: MClass): Set[MClass] do return self.mmodule
.parent_mclasses
(element
)
389 redef fun is_element_mi
(element
, elements
) do return self.parent_elements
(element
).length
> 1
390 redef fun sub_elements
(element
, elements
) do do return self.mmodule
.sub_mclasses
(element
)
391 redef fun linearize
(elements
) do return self.mmodule
.linearize_mclasses
(elements
)
392 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mclasses
(elements
)
397 # Abstract Perfect Hashing
398 private abstract class AbstractHasher[E
: Object]
400 var operator
: PHOperator
402 init(operator
: PHOperator) do self.operator
= operator
404 fun compute_masks
(elements
: Set[E
], ids
: Map[E
, Int]): Map[E
, Int] do
405 var masks
= new HashMap[E
, Int]
406 for element
in elements
do
407 var supers
= new HashSet[E
]
408 supers
.add_all
(self.super_elements
(element
, elements
))
410 masks
[element
] = compute_mask
(supers
, ids
)
415 fun compute_mask
(supers
: Set[E
], ids
: Map[E
, Int]): Int do
418 var used
= new List[Int]
420 var res
= operator
.op
(mask
, ids
[sup
])
421 if used
.has
(res
) then
427 if used
.length
== supers
.length
then break
433 fun compute_hashes
(elements
: Set[E
], ids
: Map[E
, Int], masks
: Map[E
, Int]): Map[E
, Map[E
, Int]] do
434 var hashes
= new HashMap[E
, Map[E
, Int]]
435 for element
in elements
do
436 var supers
= new HashSet[E
]
437 supers
.add_all
(self.super_elements
(element
, elements
))
439 var inhashes
= new HashMap[E
, Int]
440 var mask
= masks
[element
]
442 inhashes
[sup
] = operator
.op
(mask
, ids
[sup
])
444 hashes
[element
] = inhashes
449 fun super_elements
(element
: E
, elements
: Set[E
]): Set[E
] is abstract
452 # Abstract operator used for perfect hashing
453 abstract class PHOperator
454 fun op
(mask
: Int, id
:Int): Int is abstract
457 # Hashing using modulo (MOD) operator
462 redef fun op
(mask
, id
) do return mask
% id
465 # Hashing using binary and (AND) operator
470 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
473 # MType Perfect Hashing
474 private class MTypeHasher
475 super AbstractHasher[MType]
479 init(mmodule
: MModule, operator
: PHOperator) do
481 self.mmodule
= mmodule
484 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mtypes
(element
, elements
)
487 # MClass Perfect Hashing
488 private class MClassHasher
489 super AbstractHasher[MClass]
491 private var mmodule
: MModule
493 init(mmodule
: MModule, operator
: PHOperator) do
495 self.mmodule
= mmodule
498 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mclasses
(element
)
503 super AbstractColorer[MClass]
507 private var mmodule
: MModule
510 private var super_elements_cache
: Map[T
, Set[T
]] = new HashMap[T
, Set[T
]]
511 private var parent_elements_cache
: Map[T
, Set[T
]] = new HashMap[T
, Set[T
]]
512 private var sub_elements_cache
: Map[T
, Set[T
]] = new HashMap[T
, Set[T
]]
514 init(mainmodule
: MModule) do self.mmodule
= mainmodule
516 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mclasses
(element
)
517 fun parent_elements
(element
: MClass): Set[MClass] do return self.mmodule
.parent_mclasses
(element
)
518 redef fun is_element_mi
(element
, elements
) do return self.parent_elements
(element
).length
> 1
519 redef fun sub_elements
(element
, elements
) do do return self.mmodule
.sub_mclasses
(element
)
520 redef fun linearize
(elements
) do return self.mmodule
.linearize_mclasses
(elements
)
521 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mclasses
(elements
)
524 # incremental coloring (very naive)
525 class NaiveClassColoring
528 init(mainmodule
: MModule) do
532 # naive coloring that use incremental coloring
533 redef fun colorize_elements
(elements
) do
535 self.coloration_result
[e
] = self.coloration_result
.length
540 abstract class ClassPerfectHashing
543 init(mainmodule
: MModule) do
547 fun compute_masks
(elements
: Set[T
], ids
: Map[T
, Int]): Map[T
, Int] do
549 # Create super type list
550 var supers
= new HashSet[T
]
551 supers
.add_all
(self.super_elements
(e
, elements
))
553 # Compute the hashing 'mask'
554 self.coloration_result
[e
] = compute_mask
(supers
, ids
)
556 return self.coloration_result
559 private fun compute_mask
(mtypes
: Set[T
], ids
: Map[T
, Int]): Int do
562 var used
= new List[Int]
564 var res
= op
(mask
, ids
[sup
])
565 if used
.has
(res
) then
571 if used
.length
== mtypes
.length
then break
577 private fun op
(mask
: Int, id
:Int): Int is abstract
578 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
581 class ClassModPerfectHashing
582 super ClassPerfectHashing
583 init(mainmodule
: MModule) do
586 redef fun op
(mask
, id
) do return mask
% id
589 class ClassAndPerfectHashing
590 super ClassPerfectHashing
591 init(mainmodule
: MModule) do
594 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
598 class PropertyColoring
600 type MPROP: MProperty
601 type MPROPDEF: MPropDef
603 private var class_coloring
: ClassColoring
604 private var coloration_result
: Map[MPROP, Int] = new HashMap[MPROP, Int]
606 init(class_coloring
: ClassColoring) do
607 self.class_coloring
= class_coloring
610 fun colorize
: Map[MPROP, Int] do
611 colorize_core_properties
612 colorize_crown_properties
613 return self.coloration_result
616 fun build_property_tables
: Map[MClass, Array[nullable MPROPDEF]] do
617 var tables
= new HashMap[MClass, Array[nullable MPROPDEF]]
618 var mclasses
= self.class_coloring
.coloration_result
.keys
619 for mclass
in mclasses
do
620 var table
= new Array[nullable MPROPDEF]
621 # first, fill table from parents by reverse linearization order
622 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
623 var lin
= self.class_coloring
.reverse_linearize
(parents
)
625 for mproperty
in self.properties
(parent
) do
626 var color
= self.coloration_result
[mproperty
]
627 if table
.length
<= color
then
628 for i
in [table
.length
.. color
[ do
632 for mpropdef
in mproperty
.mpropdefs
do
633 if mpropdef
.mclassdef
.mclass
== parent
then
634 table
[color
] = mpropdef
640 # then override with local properties
641 for mproperty
in self.properties
(mclass
) do
642 var color
= self.coloration_result
[mproperty
]
643 if table
.length
<= color
then
644 for i
in [table
.length
.. color
[ do
648 for mpropdef
in mproperty
.mpropdefs
do
649 if mpropdef
.mclassdef
.mclass
== mclass
then
650 table
[color
] = mpropdef
654 tables
[mclass
] = table
659 # Colorize properties of the core hierarchy
660 private fun colorize_core_properties
do
661 var mclasses
= self.class_coloring
.core
664 for mclass
in mclasses
do
665 var color
= min_color
667 # if the class is root, get the minimal color
668 if self.class_coloring
.parent_elements
(mclass
).length
== 0 then
669 colorize_elements
(self.properties
(mclass
), color
)
671 # check last color used by parents
672 color
= max_color
(color
, self.class_coloring
.parent_elements
(mclass
))
673 # check max color used in conflicts
674 if self.class_coloring
.conflicts_graph
.has_key
(mclass
) then
675 color
= max_color
(color
, self.class_coloring
.conflicts_graph
[mclass
])
679 colorize_elements
(self.properties
(mclass
), color
)
684 # Colorize properties of the crown hierarchy
685 private fun colorize_crown_properties
do
686 for mclass
in self.class_coloring
.crown
do
687 colorize_elements
(self.properties
(mclass
), max_color
(0, self.class_coloring
.parent_elements
(mclass
)))
691 # Colorize a collection of properties given a starting color
692 private fun colorize_elements
(elements
: Collection[MPROP], start_color
: Int) do
693 for element
in elements
do
694 if self.coloration_result
.has_key
(element
) then continue
695 self.coloration_result
[element
] = start_color
700 private fun max_color
(min_color
: Int, mclasses
: Collection[MClass]): Int do
701 var max_color
= min_color
703 for mclass
in mclasses
do
704 for mproperty
in self.properties
(mclass
) do
705 var color
= min_color
706 if self.coloration_result
.has_key
(mproperty
) then
707 color
= self.coloration_result
[mproperty
]
708 if color
>= max_color
then max_color
= color
+ 1
716 private var properties_cache
: Map[MClass, Set[MPROP]] = new HashMap[MClass, Set[MPROP]]
718 # All 'mproperties' associated to all 'mclassdefs' of the class
719 private fun properties
(mclass
: MClass): Set[MPROP] do
720 if not self.properties_cache
.has_key
(mclass
) then
721 var properties
= new HashSet[MPROP]
722 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
723 for parent
in parents
do
724 properties
.add_all
(self.properties
(parent
))
727 for mclassdef
in mclass
.mclassdefs
do
728 for mpropdef
in mclassdef
.mpropdefs
do
729 var mproperty
= mpropdef
.mproperty
730 if mproperty
isa MPROP then
731 properties
.add
(mproperty
)
735 self.properties_cache
[mclass
] = properties
737 return properties_cache
[mclass
]
743 super PropertyColoring
745 redef type MPROP: MMethod
746 redef type MPROPDEF: MMethodDef
747 init(class_coloring
: ClassColoring) do end
750 # MAttribute coloring
751 class AttributeColoring
752 super PropertyColoring
754 redef type MPROP: MAttribute
755 redef type MPROPDEF: MAttributeDef
756 init(class_coloring
: ClassColoring) do end
759 # MVirtualTypeProp coloring
761 super PropertyColoring
763 redef type MPROP: MVirtualTypeProp
764 redef type MPROPDEF: MVirtualTypeDef
765 init(class_coloring
: ClassColoring) do end
768 class NaiveVTColoring
771 init(class_coloring
: ClassColoring) do end
773 redef fun colorize
: Map[MPROP, Int] do
774 var mclasses
= new HashSet[MClass]
775 mclasses
.add_all
(self.class_coloring
.core
)
776 mclasses
.add_all
(self.class_coloring
.crown
)
779 for mclass
in mclasses
do
780 min_color
= max_color
(min_color
, mclasses
)
781 colorize_elements
(self.properties
(mclass
), min_color
)
783 return self.coloration_result
787 abstract class VTPerfectHashing
790 private var masks
: Map[MClass, Int] = new HashMap[MClass, Int]
792 init(class_coloring
: ClassColoring) do end
794 redef fun colorize
: Map[MPROP, Int] do
795 var mclasses
= new HashSet[MClass]
796 mclasses
.add_all
(self.class_coloring
.core
)
797 mclasses
.add_all
(self.class_coloring
.crown
)
798 for mclass
in mclasses
do
799 var vts
= self.properties
(mclass
)
801 if coloration_result
.has_key
(vt
) then continue
802 coloration_result
[vt
] = coloration_result
.length
+ 1
805 return self.coloration_result
808 fun compute_masks
: Map[MClass, Int] do
809 var mclasses
= new HashSet[MClass]
810 mclasses
.add_all
(self.class_coloring
.core
)
811 mclasses
.add_all
(self.class_coloring
.crown
)
812 for mclass
in mclasses
do
813 self.masks
[mclass
] = compute_mask
(self.properties
(mclass
))
818 private fun compute_mask
(vts
: Set[MPROP]): Int do
821 var used
= new List[Int]
823 var res
= op
(mask
, self.coloration_result
[vt
])
824 if used
.has
(res
) then
830 if used
.length
== vts
.length
then break
836 redef fun build_property_tables
do
837 var tables
= new HashMap[MClass, Array[nullable MPROPDEF]]
839 for mclass
in self.class_coloring
.coloration_result
.keys
do
840 var table
= new Array[nullable MPROPDEF]
841 # first, fill table from parents by reverse linearization order
842 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
843 var lin
= self.class_coloring
.reverse_linearize
(parents
)
845 for mproperty
in self.properties
(parent
) do
846 var color
= phash
(self.coloration_result
[mproperty
], masks
[mclass
])
847 if table
.length
<= color
then
848 for i
in [table
.length
.. color
[ do
852 for mpropdef
in mproperty
.mpropdefs
do
853 if mpropdef
.mclassdef
.mclass
== parent
then
854 table
[color
] = mpropdef
860 # then override with local properties
861 for mproperty
in self.properties
(mclass
) do
862 var color
= phash
(self.coloration_result
[mproperty
], masks
[mclass
])
863 if table
.length
<= color
then
864 for i
in [table
.length
.. color
[ do
868 for mpropdef
in mproperty
.mpropdefs
do
869 if mpropdef
.mclassdef
.mclass
== mclass
then
870 table
[color
] = mpropdef
874 tables
[mclass
] = table
879 private fun op
(mask
: Int, id
:Int): Int is abstract
880 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
884 class VTModPerfectHashing
885 super VTPerfectHashing
886 init(class_coloring
: ClassColoring) do end
887 redef fun op
(mask
, id
) do return mask
% id
890 class VTAndPerfectHashing
891 super VTPerfectHashing
892 init(class_coloring
: ClassColoring) do end
893 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
896 # MParameterType coloring
898 private var class_coloring
: ClassColoring
899 private var coloration_result
: Map[MParameterType, Int] = new HashMap[MParameterType, Int]
901 init(class_coloring
: ClassColoring) do
902 self.class_coloring
= class_coloring
905 fun colorize
: Map[MParameterType, Int] do
906 colorize_core_properties
907 colorize_crown_properties
908 return self.coloration_result
911 # Colorize properties of the core hierarchy
912 private fun colorize_core_properties
do
913 var mclasses
= self.class_coloring
.core
916 for mclass
in mclasses
do
917 var color
= min_color
919 # if the class is root, get the minimal color
920 if self.class_coloring
.parent_elements
(mclass
).length
== 0 then
921 colorize_elements
(self.fts
(mclass
), color
)
923 # check last color used by parents
924 color
= max_color
(color
, self.class_coloring
.parent_elements
(mclass
))
925 # check max color used in conflicts
926 if self.class_coloring
.conflicts_graph
.has_key
(mclass
) then
927 color
= max_color
(color
, self.class_coloring
.conflicts_graph
[mclass
])
930 colorize_elements
(self.fts
(mclass
), color
)
935 # Colorize properties of the crown hierarchy
936 private fun colorize_crown_properties
do
937 for mclass
in self.class_coloring
.crown
do
938 colorize_elements
(self.fts
(mclass
), max_color
(0, self.class_coloring
.parent_elements
(mclass
)))
942 # Colorize a collection of properties given a starting color
943 private fun colorize_elements
(elements
: Collection[MParameterType], start_color
: Int) do
944 for element
in elements
do
945 if self.coloration_result
.has_key
(element
) then continue
946 self.coloration_result
[element
] = start_color
951 private fun max_color
(min_color
: Int, mclasses
: Collection[MClass]): Int do
952 var max_color
= min_color
954 for mclass
in mclasses
do
955 for ft
in self.fts
(mclass
) do
956 var color
= min_color
957 if self.coloration_result
.has_key
(ft
) then
958 color
= self.coloration_result
[ft
]
959 if color
>= max_color
then max_color
= color
+ 1
967 private var fts_cache
: Map[MClass, Set[MParameterType]] = new HashMap[MClass, Set[MParameterType]]
969 private fun fts
(mclass
: MClass): Set[MParameterType] do
970 if not self.fts_cache
.has_key
(mclass
) then
971 var fts
= new HashSet[MParameterType]
972 var mclass_type
= mclass
.mclass_type
973 if mclass_type
isa MGenericType then
974 for ft
in mclass_type
.arguments
do
975 fts
.add
(ft
.as(MParameterType))
978 self.fts_cache
[mclass
] = fts
980 return fts_cache
[mclass
]
983 fun build_ft_tables
: Map[MClass, Array[nullable MParameterType]] do
984 var tables
= new HashMap[MClass, Array[nullable MParameterType]]
986 for mclass
in self.class_coloring
.coloration_result
.keys
do
987 var table
= new Array[nullable MParameterType]
989 # first, fill table from parents
990 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
991 for parent
in parents
do
992 for ft
in self.fts
(parent
) do
993 var color
= self.coloration_result
[ft
]
994 if table
.length
<= color
then
995 for i
in [table
.length
.. color
[ do
1003 # then override with local properties
1004 for ft
in self.fts
(mclass
) do
1005 var color
= self.coloration_result
[ft
]
1006 if table
.length
<= color
then
1007 for i
in [table
.length
.. color
[ do
1013 tables
[mclass
] = table
1019 class NaiveFTColoring
1022 init(class_coloring
: ClassColoring) do end
1024 redef fun colorize
: Map[MParameterType, Int] do
1025 var mclasses
= new HashSet[MClass]
1026 mclasses
.add_all
(self.class_coloring
.core
)
1027 mclasses
.add_all
(self.class_coloring
.crown
)
1030 for mclass
in mclasses
do
1031 min_color
= max_color
(min_color
, mclasses
)
1032 colorize_elements
(self.fts
(mclass
), min_color
)
1034 return self.coloration_result
1038 abstract class FTPerfectHashing
1041 private var masks
: Map[MClass, Int] = new HashMap[MClass, Int]
1043 init(class_coloring
: ClassColoring) do end
1045 redef fun colorize
: Map[MParameterType, Int] do
1046 var mclasses
= new HashSet[MClass]
1047 mclasses
.add_all
(self.class_coloring
.core
)
1048 mclasses
.add_all
(self.class_coloring
.crown
)
1049 for mclass
in mclasses
do
1050 for ft
in self.fts
(mclass
) do
1051 if coloration_result
.has_key
(ft
) then continue
1052 coloration_result
[ft
] = coloration_result
.length
+ 1
1055 return self.coloration_result
1058 fun compute_masks
: Map[MClass, Int] do
1059 var mclasses
= new HashSet[MClass]
1060 mclasses
.add_all
(self.class_coloring
.core
)
1061 mclasses
.add_all
(self.class_coloring
.crown
)
1062 for mclass
in mclasses
do
1063 var fts
= new HashSet[MParameterType]
1064 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
1065 for parent
in parents
do
1066 fts
.add_all
(self.fts
(parent
))
1068 fts
.add_all
(self.fts
(mclass
))
1069 self.masks
[mclass
] = compute_mask
(fts
)
1074 private fun compute_mask
(fts
: Set[MParameterType]): Int do
1077 var used
= new List[Int]
1079 var res
= op
(mask
, self.coloration_result
[ft
])
1080 if used
.has
(res
) then
1086 if used
.length
== fts
.length
then break
1092 redef fun build_ft_tables
do
1093 var tables
= new HashMap[MClass, Array[nullable MParameterType]]
1095 for mclass
in self.class_coloring
.coloration_result
.keys
do
1096 var table
= new Array[nullable MParameterType]
1098 # first, fill table from parents
1099 var parents
= self.class_coloring
.mmodule
.super_mclasses
(mclass
)
1100 for parent
in parents
do
1101 for ft
in self.fts
(parent
) do
1102 var color
= phash
(self.coloration_result
[ft
], masks
[mclass
])
1103 if table
.length
<= color
then
1104 for i
in [table
.length
.. color
[ do
1112 # then override with local properties
1113 for ft
in self.fts
(mclass
) do
1114 var color
= phash
(self.coloration_result
[ft
], masks
[mclass
])
1115 if table
.length
<= color
then
1116 for i
in [table
.length
.. color
[ do
1122 tables
[mclass
] = table
1127 private fun op
(mask
: Int, id
:Int): Int is abstract
1128 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
1131 class FTModPerfectHashing
1132 super FTPerfectHashing
1133 init(class_coloring
: ClassColoring) do end
1134 redef fun op
(mask
, id
) do return mask
% id
1137 class FTAndPerfectHashing
1138 super FTPerfectHashing
1139 init(class_coloring
: ClassColoring) do end
1140 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
1143 # Live Entries coloring
1144 class LiveEntryColoring
1146 private var coloration_result
: Map[MType, Int] = new HashMap[MType, Int]
1147 private var conflicts_graph_cache
: nullable HashMap[MType, Set[MType]]
1148 var livetypes_tables_sizes
: nullable Map[MClass, Array[Int]]
1152 fun colorize
(elements
: Collection[MType]): Map[MType, Int] do
1154 build_conflicts_graph
(elements
)
1157 colorize_elements
(elements
)
1159 return coloration_result
1163 fun build_livetype_tables
(mtypes
: Set[MType]): Map[MClass, Array[nullable Object]] do
1164 var livetypes_tables
= new HashMap[MClass, Array[nullable Object]]
1165 self.livetypes_tables_sizes
= new HashMap[MClass, Array[Int]]
1167 for mtype
in mtypes
do
1168 if mtype
isa MGenericType then
1169 var table
: Array[nullable Object]
1170 var sizes
: Array[Int]
1171 if livetypes_tables
.has_key
(mtype
.mclass
) then
1172 table
= livetypes_tables
[mtype
.mclass
]
1174 table
= new Array[nullable Object]
1175 livetypes_tables
[mtype
.mclass
] = table
1177 if livetypes_tables_sizes
.has_key
(mtype
.mclass
) then
1178 sizes
= livetypes_tables_sizes
[mtype
.mclass
]
1180 sizes
= new Array[Int]
1181 livetypes_tables_sizes
[mtype
.mclass
] = sizes
1183 build_livetype_table
(mtype
, 0, table
, sizes
)
1187 return livetypes_tables
1190 # Build live gentype table recursively
1191 private fun build_livetype_table
(mtype
: MGenericType, current_rank
: Int, table
: Array[nullable Object], sizes
: Array[Int]) do
1192 var ft
= mtype
.arguments
[current_rank
]
1193 if not self.coloration_result
.has_key
(ft
) then return
1194 var color
= self.coloration_result
[ft
]
1196 if current_rank
>= sizes
.length
then
1197 sizes
[current_rank
] = color
+ 1
1198 else if color
>= sizes
[current_rank
] then
1199 sizes
[current_rank
] = color
+ 1
1202 if color
> table
.length
then
1203 for i
in [table
.length
.. color
[ do table
[i
] = null
1206 if current_rank
== mtype
.arguments
.length
- 1 then
1207 table
[color
] = mtype
1209 var ft_table
: Array[nullable Object]
1210 if color
< table
.length
and table
[color
] != null then
1211 ft_table
= table
[color
].as(Array[nullable Object])
1213 ft_table
= new Array[nullable Object]
1215 table
[color
] = ft_table
1216 build_livetype_table
(mtype
, current_rank
+ 1, ft_table
, sizes
)
1220 # Colorize a collection of elements
1221 fun colorize_elements
(elements
: Collection[MType]) do
1224 for element
in elements
do
1225 var color
= min_color
1226 while not self.is_color_free
(element
, color
) do
1229 coloration_result
[element
] = color
1234 # Check if a related element to the element already use the color
1235 private fun is_color_free
(element
: MType, color
: Int): Bool do
1236 if conflicts_graph
.has_key
(element
) then
1237 for st
in conflicts_graph
[element
] do
1238 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
1244 # look for types in the same generic signatures
1245 private fun build_conflicts_graph
(elements
: Collection[MType]) do
1246 # regroup types by classes
1247 var genclasses
= new HashMap[MClass, Set[MType]]
1248 for e
in elements
do
1249 if e
isa MGenericType then
1250 if not genclasses
.has_key
(e
.mclass
) then
1251 genclasses
[e
.mclass
] = new HashSet[MType]
1253 genclasses
[e
.mclass
].add
(e
)
1258 self.conflicts_graph_cache
= new HashMap[MType, Set[MType]]
1259 for mclass
, mtypes
in genclasses
do
1261 for rank
in [0..mclass
.arity
[ do
1262 # for each live type
1263 for mtype
in mtypes
do
1264 var mclasstype
: MClassType
1265 if mtype
isa MNullableType then
1266 mclasstype
= mtype
.mtype
.as(MClassType)
1268 mclasstype
= mtype
.as(MClassType)
1270 var ft
= mclasstype
.arguments
[rank
]
1271 for otype
in mtypes
do
1272 if mtype
== otype
then continue
1273 var oclasstype
: MClassType
1274 if otype
isa MNullableType then
1275 oclasstype
= otype
.mtype
.as(MClassType)
1277 oclasstype
= otype
.as(MClassType)
1279 var oft
= oclasstype
.arguments
[rank
]
1280 self.add_conflict
(ft
, oft
)
1287 private fun add_conflict
(mtype
: MType, otype
: MType) do
1288 if mtype
== otype
then return
1289 if not self.conflicts_graph_cache
.has_key
(mtype
) then self.conflicts_graph_cache
[mtype
] = new HashSet[MType]
1290 self.conflicts_graph_cache
[mtype
].add
(otype
)
1291 if not self.conflicts_graph_cache
.has_key
(otype
) then self.conflicts_graph_cache
[otype
] = new HashSet[MType]
1292 self.conflicts_graph_cache
[otype
].add
(mtype
)
1294 private fun conflicts_graph
: Map[MType, Set[MType]] do return conflicts_graph_cache
.as(not null)
1297 class NaiveLiveEntryColoring
1298 super LiveEntryColoring
1302 redef fun colorize_elements
(elements
: Collection[MType]) do
1304 for element
in elements
do
1305 coloration_result
[element
] = color
1311 # live unanchored coloring
1312 class UnanchoredTypeColoring
1314 private var coloration_result
: Map[MType, Int] = new HashMap[MType, Int]
1315 private var conflicts_graph
: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
1319 fun colorize
(elements
: Map[MClassType, Set[MType]]): Map[MType, Int] do
1320 build_conflicts_graph
(elements
)
1321 colorize_elements
(elements
)
1322 return coloration_result
1325 fun build_tables
(elements
: Map[MClassType, Set[MType]]): Map[MClassType, Array[nullable MType]] do
1326 var tables
= new HashMap[MClassType, Array[nullable MType]]
1328 for mclasstype
, mtypes
in elements
do
1329 var table
= new Array[nullable MType]
1330 for mtype
in mtypes
do
1331 var color
= self.coloration_result
[mtype
]
1332 if table
.length
<= color
then
1333 for i
in [table
.length
.. color
[ do
1337 table
[color
] = mtype
1339 tables
[mclasstype
] = table
1344 # Colorize a collection of elements
1345 fun colorize_elements
(elements
: Map[MClassType, Set[MType]]) do
1347 for mclasstype
, mclasstypes
in elements
do
1348 for element
in mclasstypes
do
1349 if self.coloration_result
.has_key
(element
) then continue
1350 var color
= min_color
1351 while not self.is_color_free
(element
, color
) do
1354 coloration_result
[element
] = color
1360 # Check if a related element to the element already use the color
1361 private fun is_color_free
(element
: MType, color
: Int): Bool do
1362 if conflicts_graph
.has_key
(element
) then
1363 for st
in conflicts_graph
[element
] do
1364 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
1370 # look for unanchored types generated by the same type
1371 private fun build_conflicts_graph
(elements
: Map[MClassType, Set[MType]]) do
1372 for mclasstype
, mtypes
in elements
do
1373 for mtype
in mtypes
do
1374 for otype
in mtypes
do
1375 if otype
== mtype
then continue
1376 self.add_conflict
(mtype
, otype
)
1382 private fun add_conflict
(mtype
: MType, otype
: MType) do
1383 if mtype
== otype
then return
1384 if not self.conflicts_graph
.has_key
(mtype
) then self.conflicts_graph
[mtype
] = new HashSet[MType]
1385 self.conflicts_graph
[mtype
].add
(otype
)
1386 if not self.conflicts_graph
.has_key
(otype
) then self.conflicts_graph
[otype
] = new HashSet[MType]
1387 self.conflicts_graph
[otype
].add
(mtype
)
1391 class NaiveUnanchoredTypeColoring
1392 super UnanchoredTypeColoring
1396 redef fun colorize_elements
(elements
: Map[MClassType, Set[MType]]) do
1398 for mclasstype
, mclasstypes
in elements
do
1399 for element
in mclasstypes
do
1400 coloration_result
[element
] = color
1407 abstract class UnanchoredTypePerfectHashing
1408 super NaiveUnanchoredTypeColoring
1410 private var masks
: Map[MClassType, Int] = new HashMap[MClassType, Int]
1414 redef fun colorize_elements
(elements
: Map[MClassType, Set[MType]]) do
1416 for mclasstype
, mclasstypes
in elements
do
1417 for element
in mclasstypes
do
1418 coloration_result
[element
] = color
1424 fun compute_masks
(elements
: Map[MClassType, Set[MType]]): Map[MClassType, Int] do
1425 for mclasstype
, mtypes
in elements
do
1426 self.masks
[mclasstype
] = compute_mask
(mtypes
)
1431 private fun compute_mask
(mtypes
: Set[MType]): Int do
1434 var used
= new List[Int]
1435 for mtype
in mtypes
do
1436 var res
= op
(mask
, self.coloration_result
[mtype
])
1437 if used
.has
(res
) then
1443 if used
.length
== mtypes
.length
then break
1449 redef fun build_tables
(elements
: Map[MClassType, Set[MType]]): Map[MClassType, Array[nullable MType]] do
1450 var tables
= new HashMap[MClassType, Array[nullable MType]]
1452 for mclasstype
, mtypes
in elements
do
1453 var table
= new Array[nullable MType]
1454 for mtype
in mtypes
do
1455 var color
= phash
(self.coloration_result
[mtype
], masks
[mclasstype
])
1456 if table
.length
<= color
then
1457 for i
in [table
.length
.. color
[ do
1461 table
[color
] = mtype
1463 tables
[mclasstype
] = table
1468 private fun op
(mask
: Int, id
:Int): Int is abstract
1469 private fun phash
(id
: Int, mask
: Int): Int do return op
(mask
, id
)
1472 class UnanchoredTypeModPerfectHashing
1473 super UnanchoredTypePerfectHashing
1475 redef fun op
(mask
, id
) do return mask
% id
1478 class UnanchoredTypeAndPerfectHashing
1479 super UnanchoredTypePerfectHashing
1481 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
1487 redef class HashSet[E
]
1488 init from
(elements
: Collection[E
]) do
1490 self.add_all
(elements
)
1494 redef class Array[E
]
1495 init from
(elements
: Collection[E
]) do
1497 self.add_all
(elements
)
1500 # Return a new Array with the elements only contened in 'self' and not in 'o'
1501 fun -(o
: Array[E
]): Array[E
] do
1502 var res
= new Array[E
]
1503 for e
in self do if not o
.has
(e
) then res
.add
(e
)
1510 # Return a linearization of a set of mtypes
1511 private fun linearize_mtypes
(mtypes
: Set[MType]): Array[MType] do
1512 var lin
= new Array[MType].from
(mtypes
)
1513 var sorter
= new TypeSorter(self)
1518 # Return a reverse linearization of a set of mtypes
1519 private fun reverse_linearize_mtypes
(mtypes
: Set[MType]): Array[MType] do
1520 var lin
= new Array[MType].from
(mtypes
)
1521 var sorter
= new ReverseTypeSorter(self)
1526 # Return super types of a `mtype` in `self`
1527 private fun super_mtypes
(mtype
: MType, mtypes
: Set[MType]): Set[MType] do
1528 if not self.super_mtypes_cache
.has_key
(mtype
) then
1529 var supers
= new HashSet[MType]
1530 for otype
in mtypes
do
1531 if otype
== mtype
then continue
1532 if mtype
.is_subtype
(self, null, otype
) then
1536 self.super_mtypes_cache
[mtype
] = supers
1538 return self.super_mtypes_cache
[mtype
]
1541 private var super_mtypes_cache
: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
1543 # Return all sub mtypes (directs and indirects) of a `mtype` in `self`
1544 private fun sub_mtypes
(mtype
: MType, mtypes
: Set[MType]): Set[MType] do
1545 if not self.sub_mtypes_cache
.has_key
(mtype
) then
1546 var subs
= new HashSet[MType]
1547 for otype
in mtypes
do
1548 if otype
== mtype
then continue
1549 if otype
.is_subtype
(self, null, mtype
) then
1553 self.sub_mtypes_cache
[mtype
] = subs
1555 return self.sub_mtypes_cache
[mtype
]
1558 private var sub_mtypes_cache
: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
1560 # Return a linearization of a set of mclasses
1561 private fun linearize_mclasses
(mclasses
: Set[MClass]): Array[MClass] do
1562 var lin
= new Array[MClass].from
(mclasses
)
1563 var sorter
= new ClassSorter(self)
1568 # Return a reverse linearization of a set of mtypes
1569 private fun reverse_linearize_mclasses
(mclasses
: Set[MClass]): Array[MClass] do
1570 var lin
= new Array[MClass].from
(mclasses
)
1571 var sorter
= new ReverseClassSorter(self)
1576 # Return all super mclasses (directs and indirects) of a `mclass` in `self`
1577 private fun super_mclasses
(mclass
: MClass): Set[MClass] do
1578 if not self.super_mclasses_cache
.has_key
(mclass
) then
1579 var supers
= new HashSet[MClass]
1580 if self.flatten_mclass_hierarchy
.has
(mclass
) then
1581 for sup
in self.flatten_mclass_hierarchy
[mclass
].greaters
do
1582 if sup
== mclass
then continue
1586 self.super_mclasses_cache
[mclass
] = supers
1588 return self.super_mclasses_cache
[mclass
]
1591 private var super_mclasses_cache
: Map[MClass, Set[MClass]] = new HashMap[MClass, Set[MClass]]
1593 # Return all parents of a `mclass` in `self`
1594 private fun parent_mclasses
(mclass
: MClass): Set[MClass] do
1595 if not self.parent_mclasses_cache
.has_key
(mclass
) then
1596 var parents
= new HashSet[MClass]
1597 if self.flatten_mclass_hierarchy
.has
(mclass
) then
1598 for sup
in self.flatten_mclass_hierarchy
[mclass
].direct_greaters
do
1599 if sup
== mclass
then continue
1603 self.parent_mclasses_cache
[mclass
] = parents
1605 return self.parent_mclasses_cache
[mclass
]
1608 private var parent_mclasses_cache
: Map[MClass, Set[MClass]] = new HashMap[MClass, Set[MClass]]
1610 # Return all sub mclasses (directs and indirects) of a `mclass` in `self`
1611 private fun sub_mclasses
(mclass
: MClass): Set[MClass] do
1612 if not self.sub_mclasses_cache
.has_key
(mclass
) then
1613 var subs
= new HashSet[MClass]
1614 if self.flatten_mclass_hierarchy
.has
(mclass
) then
1615 for sub
in self.flatten_mclass_hierarchy
[mclass
].smallers
do
1616 if sub
== mclass
then continue
1620 self.sub_mclasses_cache
[mclass
] = subs
1622 return self.sub_mclasses_cache
[mclass
]
1625 private var sub_mclasses_cache
: Map[MClass, Set[MClass]] = new HashMap[MClass, Set[MClass]]
1627 # All 'mproperties' associated to all 'mclassdefs' of `mclass`
1628 private fun properties
(mclass
: MClass): Set[MProperty] do
1629 if not self.properties_cache
.has_key
(mclass
) then
1630 var properties
= new HashSet[MProperty]
1631 var parents
= self.super_mclasses
(mclass
)
1632 for parent
in parents
do
1633 properties
.add_all
(self.properties
(parent
))
1636 for mclassdef
in mclass
.mclassdefs
do
1637 for mpropdef
in mclassdef
.mpropdefs
do
1638 properties
.add
(mpropdef
.mproperty
)
1641 self.properties_cache
[mclass
] = properties
1643 return properties_cache
[mclass
]
1646 private var properties_cache
: Map[MClass, Set[MProperty]] = new HashMap[MClass, Set[MProperty]]
1649 # A sorter for linearize list of types
1651 super AbstractSorter[MType]
1653 private var mmodule
: MModule
1655 init(mmodule
: MModule) do self.mmodule
= mmodule
1657 redef fun compare
(a
, b
) do
1660 else if a
.is_subtype
(self.mmodule
, null, b
) then
1667 # A sorter for reverse linearization
1668 class ReverseTypeSorter
1671 init(mmodule
: MModule) do end
1673 redef fun compare
(a
, b
) do
1676 else if a
.is_subtype
(self.mmodule
, null, b
) then
1683 # A sorter for linearize list of classes
1684 private class ClassSorter
1685 super AbstractSorter[MClass]
1687 var mmodule
: MModule
1689 redef fun compare
(a
, b
) do
1692 else if self.mmodule
.flatten_mclass_hierarchy
.has
(a
) and self.mmodule
.flatten_mclass_hierarchy
[a
].greaters
.has
(b
) then
1699 # A sorter for reverse linearization
1700 private class ReverseClassSorter
1701 super AbstractSorter[MClass]
1703 var mmodule
: MModule
1705 redef fun compare
(a
, b
) do
1708 else if self.mmodule
.flatten_mclass_hierarchy
.has
(a
) and self.mmodule
.flatten_mclass_hierarchy
[a
].greaters
.has
(b
) then