nitlanguage / nit.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
history | raw | HEAD
nitg-s: added model exploration facilities in redef MModule
[nit.git] / src / coloring.nit
1 # This file is part of NIT ( http://www.nitlanguage.org ).
2 #
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
6 #
7 # http://www.apache.org/licenses/LICENSE-2.0
8 #
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.
14
15 # Graph coloring tools
16 module coloring
17
18 import rapid_type_analysis # for type coloration
19
20 abstract class AbstractColoring[E: Object]
21
22 private var sorter: AbstractSorter[E]
23 private var reverse_sorter: AbstractSorter[E]
24
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]
28
29 private var coloration_result: Map[E, Int] = new HashMap[E, Int]
30 private var conflicts_graph_cache: nullable HashMap[E, Set[E]]
31
32 init(sorter: AbstractSorter[E], reverse_sorter: AbstractSorter[E]) do
33 self.sorter = sorter
34 self.reverse_sorter = reverse_sorter
35 end
36
37 fun colorize(elements: Collection[E]): Map[E, Int] do
38 # tag each element as part of group core, crown or border
39 for e in elements do
40 tag_element(e)
41 end
42
43 #print "core: {core.join(", ")}"
44 #print "border: {border.join(", ")}"
45 #print "crown: {crown.join(", ")}"
46
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)
54
55 #print "conflicts"
56 #for k, v in conflicts_graph do
57 # if k isa MType then
58 # print "{k}: {v.join(", ")}"
59 # end
60 #end
61
62 # colorize graph
63 colorize_elements(core)
64 colorize_elements(border)
65 colorize_elements(crown)
66
67 return coloration_result
68 end
69
70 # Colorize a collection of elements
71 private fun colorize_elements(elements: Collection[E]) do
72 var min_color = 0
73
74 for element in elements do
75 var color = min_color
76 while not self.is_color_free(element, color) do
77 color += 1
78 end
79 coloration_result[element] = color
80 color = min_color
81 end
82 end
83
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
89 end
90 end
91 for st in self.super_elements(element) do
92 if coloration_result.has_key(st) and coloration_result[st] == color then return false
93 end
94 return true
95 end
96
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
104 break
105 end
106 end
107
108 # Tag as core, crown or border
109 if self.is_element_mi(element) then
110 core.add_all(self.super_elements(element))
111 core.add(element)
112 if all_subelements_si then
113 border.add(element)
114 end
115 else if not all_subelements_si then
116 core.add_all(self.super_elements(element))
117 core.add(element)
118 else
119 crown.add(element)
120 end
121 end
122
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
130
131 var lin_i = self.linear_extension(i)
132
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)
136
137 var d_ij = lin_i - lin_j
138 var d_ji = lin_j - lin_i
139
140 for ed1 in d_ij do
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)
144 end
145 for ed1 in d_ij do
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)
149 end
150 end
151 end
152 end
153 end
154 return conflicts_graph_cache.as(not null)
155 end
156
157 # cache for linear_extensions
158 private var linear_extensions_cache: Map[E, Array[E]] = new HashMap[E, Array[E]]
159
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]
164 lin.add(element)
165 lin.add_all(self.super_elements(element))
166 self.sorter.sort(lin)
167 self.linear_extensions_cache[element] = lin
168 end
169 return self.linear_extensions_cache[element]
170 end
171
172 # Return all super elements (directs and indirects) of an element
173 private fun super_elements(element: E): Collection[E] is abstract
174
175 # Return all sub elements (directs and indirects) of an element
176 private fun sub_elements(element: E): Collection[E] is abstract
177
178 # Is the element in multiple inheritance ?
179 private fun is_element_mi(element: E): Bool is abstract
180 end
181
182 # MClassType coloring
183 class TypeColoring
184 super AbstractColoring[MType]
185
186 type T: MType
187
188 private var mmodule: MModule
189 private var mtypes: Set[T]
190
191 # caches
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]]
194
195 init(mainmodule: MModule, mtypes: Set[T]) do
196 super(new TypeSorter(mainmodule), new ReverseTypeSorter(mainmodule))
197 self.mmodule = mainmodule
198 self.mtypes = mtypes
199 end
200
201 # Build type tables
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]]
204
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))
209 supers.add(mtype)
210 for sup in supers do
211 var color = colors[sup]
212 if table.length <= color then
213 for i in [table.length .. color[ do
214 table[i] = null
215 end
216 end
217 table[color] = sup
218 end
219 tables[mtype] = table
220 end
221 return tables
222 end
223
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
230 supers.add(mtype)
231 end
232 end
233 self.super_elements_cache[element] = supers
234 end
235 return self.super_elements_cache[element]
236 end
237
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
241 end
242
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
250 subs.add(mtype)
251 end
252 end
253 self.sub_elements_cache[element] = subs
254 end
255 return self.sub_elements_cache[element]
256 end
257 end
258
259 class NaiveTypeColoring
260 super TypeColoring
261
262 init(mainmodule: MModule, mtypes: Set[T]) do
263 super(mainmodule, mtypes)
264 end
265
266 # naive coloring that use incremental coloring
267 redef fun colorize_elements(elements) do
268 for e in elements do
269 self.coloration_result[e] = self.coloration_result.length
270 end
271 end
272 end
273
274 abstract class TypePerfectHashing
275 super TypeColoring
276
277 init(mainmodule: MModule, mtypes: Set[T]) do
278 super(mainmodule, mtypes)
279 end
280
281 fun compute_masks(elements: Set[T], ids: Map[T, Int]): Map[T, Int] do
282 for e in elements do
283 # Create super type list
284 var supers = new HashSet[T]
285 supers.add_all(self.super_elements(e))
286 supers.add(e)
287 # Compute the hashing 'mask'
288 self.coloration_result[e] = compute_mask(supers, ids)
289 end
290 return self.coloration_result
291 end
292
293 # Build type tables
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]]
296
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))
301 supers.add(mtype)
302
303 for sup in supers do
304 var color = phash(ids[sup], masks[mtype])
305 if table.length <= color then
306 for i in [table.length .. color[ do
307 table[i] = null
308 end
309 end
310 table[color] = sup
311 end
312 tables[mtype] = table
313 end
314 return tables
315 end
316
317 private fun compute_mask(mtypes: Set[T], ids: Map[T, Int]): Int do
318 var mask = 0
319 loop
320 var used = new List[Int]
321 for sup in mtypes do
322 var res = op(mask, ids[sup])
323 if used.has(res) then
324 break
325 else
326 used.add(res)
327 end
328 end
329 if used.length == mtypes.length then break
330 mask += 1
331 end
332 return mask
333 end
334
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)
337 end
338
339 class TypeModPerfectHashing
340 super TypePerfectHashing
341 init(mainmodule: MModule, mtypes: Set[T]) do
342 super(mainmodule, mtypes)
343 end
344 redef fun op(mask, id) do return mask % id
345 end
346
347 class TypeAndPerfectHashing
348 super TypePerfectHashing
349 init(mainmodule: MModule, mtypes: Set[T]) do
350 super(mainmodule, mtypes)
351 end
352 redef fun op(mask, id) do return mask.bin_and(id)
353 end
354
355 # MClass coloring
356 class ClassColoring
357 super AbstractColoring[MClass]
358
359 type T: MClass
360
361 private var mmodule: MModule
362
363 # caches
364 private var super_elements_cache: Map[T, Set[T]] = new HashMap[T, Set[T]]
365 private var parent_elements_cache: Map[T, Set[T]] = new HashMap[T, Set[T]]
366 private var sub_elements_cache: Map[T, Set[T]] = new HashMap[T, Set[T]]
367
368 init(mainmodule: MModule) do
369 super(new ClassSorter(mainmodule), new ReverseClassSorter(mainmodule))
370 self.mmodule = mainmodule
371 end
372
373 # Build type tables
374 fun build_type_tables(mclasses: Array[T], colors: Map[T, Int]): Map[T, Array[nullable T]] do
375 var tables = new HashMap[T, Array[nullable T]]
376
377 for mclasse in mclasses do
378 var table = new Array[nullable T]
379 var supers = new HashSet[T]
380 supers.add_all(self.super_elements(mclasse))
381 supers.add(mclasse)
382 for sup in supers do
383 var color = colors[sup]
384 if table.length <= color then
385 for i in [table.length .. color[ do
386 table[i] = null
387 end
388 end
389 table[color] = sup
390 end
391 tables[mclasse] = table
392 end
393 return tables
394 end
395
396 redef fun super_elements(element) do
397 if not self.super_elements_cache.has_key(element) then
398 var supers = new HashSet[T]
399 if self.mmodule.flatten_mclass_hierarchy.has(element) then
400 for sup in self.mmodule.flatten_mclass_hierarchy[element].greaters do
401 if element == sup then continue
402 supers.add(sup)
403 end
404 end
405 self.super_elements_cache[element] = supers
406 end
407 return self.super_elements_cache[element]
408 end
409
410 private fun parent_elements(element: T): Set[T] do
411 if not self.parent_elements_cache.has_key(element) then
412 var parents = new HashSet[T]
413 if self.mmodule.flatten_mclass_hierarchy.has(element) then
414 for parent in self.mmodule.flatten_mclass_hierarchy[element].direct_greaters do
415 if element == parent then continue
416 parents.add(parent)
417 end
418 end
419 self.parent_elements_cache[element] = parents
420 end
421 return self.parent_elements_cache[element]
422 end
423
424 # Return all sub elements (directs and indirects) of an element
425 redef fun sub_elements(element) do
426 if not self.sub_elements_cache.has_key(element) then
427 var subs = new HashSet[T]
428 if self.mmodule.flatten_mclass_hierarchy.has(element) then
429 for sub in self.mmodule.flatten_mclass_hierarchy[element].smallers do
430 subs.add(sub)
431 end
432 end
433 self.sub_elements_cache[element] = subs
434 end
435 return self.sub_elements_cache[element]
436 end
437
438 # Return all direct super elements of an element
439 redef fun is_element_mi(element) do
440 if not self.mmodule.flatten_mclass_hierarchy.has(element) then return false
441 return self.mmodule.flatten_mclass_hierarchy[element].direct_greaters.length > 1
442 end
443 end
444
445 # incremental coloring (very naive)
446 class NaiveClassColoring
447 super ClassColoring
448
449 init(mainmodule: MModule) do
450 super(mainmodule)
451 end
452
453 # naive coloring that use incremental coloring
454 redef fun colorize_elements(elements: Collection[MClass]) do
455 for e in elements do
456 self.coloration_result[e] = self.coloration_result.length
457 end
458 end
459 end
460
461 abstract class ClassPerfectHashing
462 super ClassColoring
463
464 init(mainmodule: MModule) do
465 super(mainmodule)
466 end
467
468 fun compute_masks(elements: Set[T], ids: Map[T, Int]): Map[T, Int] do
469 for e in elements do
470 # Create super type list
471 var supers = new HashSet[T]
472 supers.add_all(self.super_elements(e))
473 supers.add(e)
474 # Compute the hashing 'mask'
475 self.coloration_result[e] = compute_mask(supers, ids)
476 end
477 return self.coloration_result
478 end
479
480 # Build type tables
481 fun hash_type_tables(mtypes: Set[T], ids: Map[T, Int], masks: Map[T, Int]): Map[T, Array[nullable T]] do
482 var tables = new HashMap[T, Array[nullable T]]
483
484 for mtype in mtypes do
485 var table = new Array[nullable T]
486 var supers = new HashSet[T]
487 supers.add_all(self.super_elements(mtype))
488 supers.add(mtype)
489
490 for sup in supers do
491 var color = phash(ids[sup], masks[mtype])
492 if table.length <= color then
493 for i in [table.length .. color[ do
494 table[i] = null
495 end
496 end
497 table[color] = sup
498 end
499 tables[mtype] = table
500 end
501 return tables
502 end
503
504 private fun compute_mask(mtypes: Set[T], ids: Map[T, Int]): Int do
505 var mask = 0
506 loop
507 var used = new List[Int]
508 for sup in mtypes do
509 var res = op(mask, ids[sup])
510 if used.has(res) then
511 break
512 else
513 used.add(res)
514 end
515 end
516 if used.length == mtypes.length then break
517 mask += 1
518 end
519 return mask
520 end
521
522 private fun op(mask: Int, id:Int): Int is abstract
523 private fun phash(id: Int, mask: Int): Int do return op(mask, id)
524 end
525
526 class ClassModPerfectHashing
527 super ClassPerfectHashing
528 init(mainmodule: MModule) do
529 super(mainmodule)
530 end
531 redef fun op(mask, id) do return mask % id
532 end
533
534 class ClassAndPerfectHashing
535 super ClassPerfectHashing
536 init(mainmodule: MModule) do
537 super(mainmodule)
538 end
539 redef fun op(mask, id) do return mask.bin_and(id)
540 end
541
542 # MProperty coloring
543 class PropertyColoring
544
545 type MPROP: MProperty
546 type MPROPDEF: MPropDef
547
548 private var class_coloring: ClassColoring
549 private var coloration_result: Map[MPROP, Int] = new HashMap[MPROP, Int]
550
551 init(class_coloring: ClassColoring) do
552 self.class_coloring = class_coloring
553 end
554
555 fun colorize: Map[MPROP, Int] do
556 colorize_core_properties
557 colorize_crown_properties
558 return self.coloration_result
559 end
560
561 fun build_property_tables: Map[MClass, Array[nullable MPROPDEF]] do
562 var tables = new HashMap[MClass, Array[nullable MPROPDEF]]
563
564 for mclass in self.class_coloring.coloration_result.keys do
565 var table = new Array[nullable MPROPDEF]
566 # first, fill table from parents by reverse linearization order
567 var parents = new Array[MClass]
568 parents.add_all(self.class_coloring.super_elements(mclass))
569 self.class_coloring.reverse_sorter.sort(parents)
570 for parent in parents do
571 for mproperty in self.properties(parent) do
572 var color = self.coloration_result[mproperty]
573 if table.length <= color then
574 for i in [table.length .. color[ do
575 table[i] = null
576 end
577 end
578 for mpropdef in mproperty.mpropdefs do
579 if mpropdef.mclassdef.mclass == parent then
580 table[color] = mpropdef
581 end
582 end
583 end
584 end
585
586 # then override with local properties
587 for mproperty in self.properties(mclass) do
588 var color = self.coloration_result[mproperty]
589 if table.length <= color then
590 for i in [table.length .. color[ do
591 table[i] = null
592 end
593 end
594 for mpropdef in mproperty.mpropdefs do
595 if mpropdef.mclassdef.mclass == mclass then
596 table[color] = mpropdef
597 end
598 end
599 end
600 tables[mclass] = table
601 end
602 return tables
603 end
604
605 # Colorize properties of the core hierarchy
606 private fun colorize_core_properties do
607 var mclasses = self.class_coloring.core
608 var min_color = 0
609
610 for mclass in mclasses do
611 var color = min_color
612
613 # if the class is root, get the minimal color
614 if self.class_coloring.parent_elements(mclass).length == 0 then
615 colorize_elements(self.properties(mclass), color)
616 else
617 # check last color used by parents
618 color = max_color(color, self.class_coloring.parent_elements(mclass))
619 # check max color used in conflicts
620 if self.class_coloring.conflicts_graph.has_key(mclass) then
621 color = max_color(color, self.class_coloring.conflicts_graph[mclass])
622 end
623
624 # colorize
625 colorize_elements(self.properties(mclass), color)
626 end
627 end
628 end
629
630 # Colorize properties of the crown hierarchy
631 private fun colorize_crown_properties do
632 for mclass in self.class_coloring.crown do
633 colorize_elements(self.properties(mclass), max_color(0, self.class_coloring.parent_elements(mclass)))
634 end
635 end
636
637 # Colorize a collection of properties given a starting color
638 private fun colorize_elements(elements: Collection[MPROP], start_color: Int) do
639 for element in elements do
640 if self.coloration_result.has_key(element) then continue
641 self.coloration_result[element] = start_color
642 start_color += 1
643 end
644 end
645
646 private fun max_color(min_color: Int, mclasses: Collection[MClass]): Int do
647 var max_color = min_color
648
649 for mclass in mclasses do
650 for mproperty in self.properties(mclass) do
651 var color = min_color
652 if self.coloration_result.has_key(mproperty) then
653 color = self.coloration_result[mproperty]
654 if color >= max_color then max_color = color + 1
655 end
656 end
657 end
658 return max_color
659 end
660
661 # properties cache
662 private var properties_cache: Map[MClass, Set[MPROP]] = new HashMap[MClass, Set[MPROP]]
663
664 # All 'mproperties' associated to all 'mclassdefs' of the class
665 private fun properties(mclass: MClass): Set[MPROP] do
666 if not self.properties_cache.has_key(mclass) then
667 var properties = new HashSet[MPROP]
668 var parents = self.class_coloring.super_elements(mclass)
669 for parent in parents do
670 properties.add_all(self.properties(parent))
671 end
672
673 for mclassdef in mclass.mclassdefs do
674 for mpropdef in mclassdef.mpropdefs do
675 var mproperty = mpropdef.mproperty
676 if mproperty isa MPROP then
677 properties.add(mproperty)
678 end
679 end
680 end
681 self.properties_cache[mclass] = properties
682 end
683 return properties_cache[mclass]
684 end
685 end
686
687 # MMethod coloring
688 class MethodColoring
689 super PropertyColoring
690
691 redef type MPROP: MMethod
692 redef type MPROPDEF: MMethodDef
693 init(class_coloring: ClassColoring) do end
694 end
695
696 # MAttribute coloring
697 class AttributeColoring
698 super PropertyColoring
699
700 redef type MPROP: MAttribute
701 redef type MPROPDEF: MAttributeDef
702 init(class_coloring: ClassColoring) do end
703 end
704
705 # MVirtualTypeProp coloring
706 class VTColoring
707 super PropertyColoring
708
709 redef type MPROP: MVirtualTypeProp
710 redef type MPROPDEF: MVirtualTypeDef
711 init(class_coloring: ClassColoring) do end
712 end
713
714 class NaiveVTColoring
715 super VTColoring
716
717 init(class_coloring: ClassColoring) do end
718
719 redef fun colorize: Map[MPROP, Int] do
720 var mclasses = new HashSet[MClass]
721 mclasses.add_all(self.class_coloring.core)
722 mclasses.add_all(self.class_coloring.crown)
723 var min_color = 0
724
725 for mclass in mclasses do
726 min_color = max_color(min_color, mclasses)
727 colorize_elements(self.properties(mclass), min_color)
728 end
729 return self.coloration_result
730 end
731 end
732
733 abstract class VTPerfectHashing
734 super VTColoring
735
736 private var masks: Map[MClass, Int] = new HashMap[MClass, Int]
737
738 init(class_coloring: ClassColoring) do end
739
740 redef fun colorize: Map[MPROP, Int] do
741 var mclasses = new HashSet[MClass]
742 mclasses.add_all(self.class_coloring.core)
743 mclasses.add_all(self.class_coloring.crown)
744 for mclass in mclasses do
745 var vts = self.properties(mclass)
746 for vt in vts do
747 if coloration_result.has_key(vt) then continue
748 coloration_result[vt] = coloration_result.length + 1
749 end
750 end
751 return self.coloration_result
752 end
753
754 fun compute_masks: Map[MClass, Int] do
755 var mclasses = new HashSet[MClass]
756 mclasses.add_all(self.class_coloring.core)
757 mclasses.add_all(self.class_coloring.crown)
758 for mclass in mclasses do
759 self.masks[mclass] = compute_mask(self.properties(mclass))
760 end
761 return self.masks
762 end
763
764 private fun compute_mask(vts: Set[MPROP]): Int do
765 var mask = 0
766 loop
767 var used = new List[Int]
768 for vt in vts do
769 var res = op(mask, self.coloration_result[vt])
770 if used.has(res) then
771 break
772 else
773 used.add(res)
774 end
775 end
776 if used.length == vts.length then break
777 mask += 1
778 end
779 return mask
780 end
781
782 redef fun build_property_tables do
783 var tables = new HashMap[MClass, Array[nullable MPROPDEF]]
784
785 for mclass in self.class_coloring.coloration_result.keys do
786 var table = new Array[nullable MPROPDEF]
787 # first, fill table from parents by reverse linearization order
788 var parents = new Array[MClass]
789 parents.add_all(self.class_coloring.super_elements(mclass))
790 self.class_coloring.reverse_sorter.sort(parents)
791 for parent in parents do
792 for mproperty in self.properties(parent) do
793 var color = phash(self.coloration_result[mproperty], masks[mclass])
794 if table.length <= color then
795 for i in [table.length .. color[ do
796 table[i] = null
797 end
798 end
799 for mpropdef in mproperty.mpropdefs do
800 if mpropdef.mclassdef.mclass == parent then
801 table[color] = mpropdef
802 end
803 end
804 end
805 end
806
807 # then override with local properties
808 for mproperty in self.properties(mclass) do
809 var color = phash(self.coloration_result[mproperty], masks[mclass])
810 if table.length <= color then
811 for i in [table.length .. color[ do
812 table[i] = null
813 end
814 end
815 for mpropdef in mproperty.mpropdefs do
816 if mpropdef.mclassdef.mclass == mclass then
817 table[color] = mpropdef
818 end
819 end
820 end
821 tables[mclass] = table
822 end
823 return tables
824 end
825
826 private fun op(mask: Int, id:Int): Int is abstract
827 private fun phash(id: Int, mask: Int): Int do return op(mask, id)
828
829 end
830
831 class VTModPerfectHashing
832 super VTPerfectHashing
833 init(class_coloring: ClassColoring) do end
834 redef fun op(mask, id) do return mask % id
835 end
836
837 class VTAndPerfectHashing
838 super VTPerfectHashing
839 init(class_coloring: ClassColoring) do end
840 redef fun op(mask, id) do return mask.bin_and(id)
841 end
842
843 # MParameterType coloring
844 class FTColoring
845 private var class_coloring: ClassColoring
846 private var coloration_result: Map[MParameterType, Int] = new HashMap[MParameterType, Int]
847
848 init(class_coloring: ClassColoring) do
849 self.class_coloring = class_coloring
850 end
851
852 fun colorize: Map[MParameterType, Int] do
853 colorize_core_properties
854 colorize_crown_properties
855 return self.coloration_result
856 end
857
858 # Colorize properties of the core hierarchy
859 private fun colorize_core_properties do
860 var mclasses = self.class_coloring.core
861 var min_color = 0
862
863 for mclass in mclasses do
864 var color = min_color
865
866 # if the class is root, get the minimal color
867 if self.class_coloring.parent_elements(mclass).length == 0 then
868 colorize_elements(self.fts(mclass), color)
869 else
870 # check last color used by parents
871 color = max_color(color, self.class_coloring.parent_elements(mclass))
872 # check max color used in conflicts
873 if self.class_coloring.conflicts_graph.has_key(mclass) then
874 color = max_color(color, self.class_coloring.conflicts_graph[mclass])
875 end
876 # colorize
877 colorize_elements(self.fts(mclass), color)
878 end
879 end
880 end
881
882 # Colorize properties of the crown hierarchy
883 private fun colorize_crown_properties do
884 for mclass in self.class_coloring.crown do
885 colorize_elements(self.fts(mclass), max_color(0, self.class_coloring.parent_elements(mclass)))
886 end
887 end
888
889 # Colorize a collection of properties given a starting color
890 private fun colorize_elements(elements: Collection[MParameterType], start_color: Int) do
891 for element in elements do
892 if self.coloration_result.has_key(element) then continue
893 self.coloration_result[element] = start_color
894 start_color += 1
895 end
896 end
897
898 private fun max_color(min_color: Int, mclasses: Collection[MClass]): Int do
899 var max_color = min_color
900
901 for mclass in mclasses do
902 for ft in self.fts(mclass) do
903 var color = min_color
904 if self.coloration_result.has_key(ft) then
905 color = self.coloration_result[ft]
906 if color >= max_color then max_color = color + 1
907 end
908 end
909 end
910 return max_color
911 end
912
913 # fts cache
914 private var fts_cache: Map[MClass, Set[MParameterType]] = new HashMap[MClass, Set[MParameterType]]
915
916 private fun fts(mclass: MClass): Set[MParameterType] do
917 if not self.fts_cache.has_key(mclass) then
918 var fts = new HashSet[MParameterType]
919 var mclass_type = mclass.mclass_type
920 if mclass_type isa MGenericType then
921 for ft in mclass_type.arguments do
922 fts.add(ft.as(MParameterType))
923 end
924 end
925 self.fts_cache[mclass] = fts
926 end
927 return fts_cache[mclass]
928 end
929
930 fun build_ft_tables: Map[MClass, Array[nullable MParameterType]] do
931 var tables = new HashMap[MClass, Array[nullable MParameterType]]
932
933 for mclass in self.class_coloring.coloration_result.keys do
934 var table = new Array[nullable MParameterType]
935
936 # first, fill table from parents
937 for parent in self.class_coloring.super_elements(mclass) do
938 for ft in self.fts(parent) do
939 var color = self.coloration_result[ft]
940 if table.length <= color then
941 for i in [table.length .. color[ do
942 table[i] = null
943 end
944 end
945 table[color] = ft
946 end
947 end
948
949 # then override with local properties
950 for ft in self.fts(mclass) do
951 var color = self.coloration_result[ft]
952 if table.length <= color then
953 for i in [table.length .. color[ do
954 table[i] = null
955 end
956 end
957 table[color] = ft
958 end
959 tables[mclass] = table
960 end
961 return tables
962 end
963 end
964
965 class NaiveFTColoring
966 super FTColoring
967
968 init(class_coloring: ClassColoring) do end
969
970 redef fun colorize: Map[MParameterType, Int] do
971 var mclasses = new HashSet[MClass]
972 mclasses.add_all(self.class_coloring.core)
973 mclasses.add_all(self.class_coloring.crown)
974 var min_color = 0
975
976 for mclass in mclasses do
977 min_color = max_color(min_color, mclasses)
978 colorize_elements(self.fts(mclass), min_color)
979 end
980 return self.coloration_result
981 end
982 end
983
984 abstract class FTPerfectHashing
985 super FTColoring
986
987 private var masks: Map[MClass, Int] = new HashMap[MClass, Int]
988
989 init(class_coloring: ClassColoring) do end
990
991 redef fun colorize: Map[MParameterType, Int] do
992 var mclasses = new HashSet[MClass]
993 mclasses.add_all(self.class_coloring.core)
994 mclasses.add_all(self.class_coloring.crown)
995 for mclass in mclasses do
996 for ft in self.fts(mclass) do
997 if coloration_result.has_key(ft) then continue
998 coloration_result[ft] = coloration_result.length + 1
999 end
1000 end
1001 return self.coloration_result
1002 end
1003
1004 fun compute_masks: Map[MClass, Int] do
1005 var mclasses = new HashSet[MClass]
1006 mclasses.add_all(self.class_coloring.core)
1007 mclasses.add_all(self.class_coloring.crown)
1008 for mclass in mclasses do
1009 var fts = new HashSet[MParameterType]
1010 for parent in self.class_coloring.super_elements(mclass) do
1011 fts.add_all(self.fts(parent))
1012 end
1013 fts.add_all(self.fts(mclass))
1014 self.masks[mclass] = compute_mask(fts)
1015 end
1016 return self.masks
1017 end
1018
1019 private fun compute_mask(fts: Set[MParameterType]): Int do
1020 var mask = 0
1021 loop
1022 var used = new List[Int]
1023 for ft in fts do
1024 var res = op(mask, self.coloration_result[ft])
1025 if used.has(res) then
1026 break
1027 else
1028 used.add(res)
1029 end
1030 end
1031 if used.length == fts.length then break
1032 mask += 1
1033 end
1034 return mask
1035 end
1036
1037 redef fun build_ft_tables do
1038 var tables = new HashMap[MClass, Array[nullable MParameterType]]
1039
1040 for mclass in self.class_coloring.coloration_result.keys do
1041 var table = new Array[nullable MParameterType]
1042
1043 # first, fill table from parents
1044 for parent in self.class_coloring.super_elements(mclass) do
1045 for ft in self.fts(parent) do
1046 var color = phash(self.coloration_result[ft], masks[mclass])
1047 if table.length <= color then
1048 for i in [table.length .. color[ do
1049 table[i] = null
1050 end
1051 end
1052 table[color] = ft
1053 end
1054 end
1055
1056 # then override with local properties
1057 for ft in self.fts(mclass) do
1058 var color = phash(self.coloration_result[ft], masks[mclass])
1059 if table.length <= color then
1060 for i in [table.length .. color[ do
1061 table[i] = null
1062 end
1063 end
1064 table[color] = ft
1065 end
1066 tables[mclass] = table
1067 end
1068 return tables
1069 end
1070
1071 private fun op(mask: Int, id:Int): Int is abstract
1072 private fun phash(id: Int, mask: Int): Int do return op(mask, id)
1073 end
1074
1075 class FTModPerfectHashing
1076 super FTPerfectHashing
1077 init(class_coloring: ClassColoring) do end
1078 redef fun op(mask, id) do return mask % id
1079 end
1080
1081 class FTAndPerfectHashing
1082 super FTPerfectHashing
1083 init(class_coloring: ClassColoring) do end
1084 redef fun op(mask, id) do return mask.bin_and(id)
1085 end
1086
1087 # Live Entries coloring
1088 class LiveEntryColoring
1089
1090 private var coloration_result: Map[MType, Int] = new HashMap[MType, Int]
1091 private var conflicts_graph_cache: nullable HashMap[MType, Set[MType]]
1092 var livetypes_tables_sizes: nullable Map[MClass, Array[Int]]
1093
1094 init do end
1095
1096 fun colorize(elements: Collection[MType]): Map[MType, Int] do
1097 # compute conflicts
1098 build_conflicts_graph(elements)
1099
1100 # colorize graph
1101 colorize_elements(elements)
1102
1103 return coloration_result
1104 end
1105
1106 # Build type tables
1107 fun build_livetype_tables(mtypes: Set[MType]): Map[MClass, Array[nullable Object]] do
1108 var livetypes_tables = new HashMap[MClass, Array[nullable Object]]
1109 self.livetypes_tables_sizes = new HashMap[MClass, Array[Int]]
1110
1111 for mtype in mtypes do
1112 if mtype isa MGenericType then
1113 var table: Array[nullable Object]
1114 var sizes: Array[Int]
1115 if livetypes_tables.has_key(mtype.mclass) then
1116 table = livetypes_tables[mtype.mclass]
1117 else
1118 table = new Array[nullable Object]
1119 livetypes_tables[mtype.mclass] = table
1120 end
1121 if livetypes_tables_sizes.has_key(mtype.mclass) then
1122 sizes = livetypes_tables_sizes[mtype.mclass]
1123 else
1124 sizes = new Array[Int]
1125 livetypes_tables_sizes[mtype.mclass] = sizes
1126 end
1127 build_livetype_table(mtype, 0, table, sizes)
1128 end
1129 end
1130
1131 return livetypes_tables
1132 end
1133
1134 # Build live gentype table recursively
1135 private fun build_livetype_table(mtype: MGenericType, current_rank: Int, table: Array[nullable Object], sizes: Array[Int]) do
1136 var ft = mtype.arguments[current_rank]
1137 if not self.coloration_result.has_key(ft) then return
1138 var color = self.coloration_result[ft]
1139
1140 if current_rank >= sizes.length then
1141 sizes[current_rank] = color + 1
1142 else if color >= sizes[current_rank] then
1143 sizes[current_rank] = color + 1
1144 end
1145
1146 if color > table.length then
1147 for i in [table.length .. color[ do table[i] = null
1148 end
1149
1150 if current_rank == mtype.arguments.length - 1 then
1151 table[color] = mtype
1152 else
1153 var ft_table: Array[nullable Object]
1154 if color < table.length and table[color] != null then
1155 ft_table = table[color].as(Array[nullable Object])
1156 else
1157 ft_table = new Array[nullable Object]
1158 end
1159 table[color] = ft_table
1160 build_livetype_table(mtype, current_rank + 1, ft_table, sizes)
1161 end
1162 end
1163
1164 # Colorize a collection of elements
1165 fun colorize_elements(elements: Collection[MType]) do
1166 var min_color = 0
1167
1168 for element in elements do
1169 var color = min_color
1170 while not self.is_color_free(element, color) do
1171 color += 1
1172 end
1173 coloration_result[element] = color
1174 color = min_color
1175 end
1176 end
1177
1178 # Check if a related element to the element already use the color
1179 private fun is_color_free(element: MType, color: Int): Bool do
1180 if conflicts_graph.has_key(element) then
1181 for st in conflicts_graph[element] do
1182 if coloration_result.has_key(st) and coloration_result[st] == color then return false
1183 end
1184 end
1185 return true
1186 end
1187
1188 # look for types in the same generic signatures
1189 private fun build_conflicts_graph(elements: Collection[MType]) do
1190 # regroup types by classes
1191 var genclasses = new HashMap[MClass, Set[MType]]
1192 for e in elements do
1193 if e isa MGenericType then
1194 if not genclasses.has_key(e.mclass) then
1195 genclasses[e.mclass] = new HashSet[MType]
1196 end
1197 genclasses[e.mclass].add(e)
1198 end
1199 end
1200
1201 # for each class
1202 self.conflicts_graph_cache = new HashMap[MType, Set[MType]]
1203 for mclass, mtypes in genclasses do
1204 # for each rank
1205 for rank in [0..mclass.arity[ do
1206 # for each live type
1207 for mtype in mtypes do
1208 var mclasstype: MClassType
1209 if mtype isa MNullableType then
1210 mclasstype = mtype.mtype.as(MClassType)
1211 else
1212 mclasstype = mtype.as(MClassType)
1213 end
1214 var ft = mclasstype.arguments[rank]
1215 for otype in mtypes do
1216 if mtype == otype then continue
1217 var oclasstype: MClassType
1218 if otype isa MNullableType then
1219 oclasstype = otype.mtype.as(MClassType)
1220 else
1221 oclasstype = otype.as(MClassType)
1222 end
1223 var oft = oclasstype.arguments[rank]
1224 self.add_conflict(ft, oft)
1225 end
1226 end
1227 end
1228 end
1229 end
1230
1231 private fun add_conflict(mtype: MType, otype: MType) do
1232 if mtype == otype then return
1233 if not self.conflicts_graph_cache.has_key(mtype) then self.conflicts_graph_cache[mtype] = new HashSet[MType]
1234 self.conflicts_graph_cache[mtype].add(otype)
1235 if not self.conflicts_graph_cache.has_key(otype) then self.conflicts_graph_cache[otype] = new HashSet[MType]
1236 self.conflicts_graph_cache[otype].add(mtype)
1237 end
1238 private fun conflicts_graph: Map[MType, Set[MType]] do return conflicts_graph_cache.as(not null)
1239 end
1240
1241 class NaiveLiveEntryColoring
1242 super LiveEntryColoring
1243
1244 init do end
1245
1246 redef fun colorize_elements(elements: Collection[MType]) do
1247 var color = 0
1248 for element in elements do
1249 coloration_result[element] = color
1250 color += 1
1251 end
1252 end
1253 end
1254
1255 # live unanchored coloring
1256 class UnanchoredTypeColoring
1257
1258 private var coloration_result: Map[MType, Int] = new HashMap[MType, Int]
1259 private var conflicts_graph: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
1260
1261 init do end
1262
1263 fun colorize(elements: Map[MClassType, Set[MType]]): Map[MType, Int] do
1264 build_conflicts_graph(elements)
1265 colorize_elements(elements)
1266 return coloration_result
1267 end
1268
1269 fun build_tables(elements: Map[MClassType, Set[MType]]): Map[MClassType, Array[nullable MType]] do
1270 var tables = new HashMap[MClassType, Array[nullable MType]]
1271
1272 for mclasstype, mtypes in elements do
1273 var table = new Array[nullable MType]
1274 for mtype in mtypes do
1275 var color = self.coloration_result[mtype]
1276 if table.length <= color then
1277 for i in [table.length .. color[ do
1278 table[i] = null
1279 end
1280 end
1281 table[color] = mtype
1282 end
1283 tables[mclasstype] = table
1284 end
1285 return tables
1286 end
1287
1288 # Colorize a collection of elements
1289 fun colorize_elements(elements: Map[MClassType, Set[MType]]) do
1290 var min_color = 0
1291 for mclasstype, mclasstypes in elements do
1292 for element in mclasstypes do
1293 if self.coloration_result.has_key(element) then continue
1294 var color = min_color
1295 while not self.is_color_free(element, color) do
1296 color += 1
1297 end
1298 coloration_result[element] = color
1299 color = min_color
1300 end
1301 end
1302 end
1303
1304 # Check if a related element to the element already use the color
1305 private fun is_color_free(element: MType, color: Int): Bool do
1306 if conflicts_graph.has_key(element) then
1307 for st in conflicts_graph[element] do
1308 if coloration_result.has_key(st) and coloration_result[st] == color then return false
1309 end
1310 end
1311 return true
1312 end
1313
1314 # look for unanchored types generated by the same type
1315 private fun build_conflicts_graph(elements: Map[MClassType, Set[MType]]) do
1316 for mclasstype, mtypes in elements do
1317 for mtype in mtypes do
1318 for otype in mtypes do
1319 if otype == mtype then continue
1320 self.add_conflict(mtype, otype)
1321 end
1322 end
1323 end
1324 end
1325
1326 private fun add_conflict(mtype: MType, otype: MType) do
1327 if mtype == otype then return
1328 if not self.conflicts_graph.has_key(mtype) then self.conflicts_graph[mtype] = new HashSet[MType]
1329 self.conflicts_graph[mtype].add(otype)
1330 if not self.conflicts_graph.has_key(otype) then self.conflicts_graph[otype] = new HashSet[MType]
1331 self.conflicts_graph[otype].add(mtype)
1332 end
1333 end
1334
1335 class NaiveUnanchoredTypeColoring
1336 super UnanchoredTypeColoring
1337
1338 init do end
1339
1340 redef fun colorize_elements(elements: Map[MClassType, Set[MType]]) do
1341 var color = 0
1342 for mclasstype, mclasstypes in elements do
1343 for element in mclasstypes do
1344 coloration_result[element] = color
1345 color += 1
1346 end
1347 end
1348 end
1349 end
1350
1351 abstract class UnanchoredTypePerfectHashing
1352 super NaiveUnanchoredTypeColoring
1353
1354 private var masks: Map[MClassType, Int] = new HashMap[MClassType, Int]
1355
1356 init do end
1357
1358 redef fun colorize_elements(elements: Map[MClassType, Set[MType]]) do
1359 var color = 1
1360 for mclasstype, mclasstypes in elements do
1361 for element in mclasstypes do
1362 coloration_result[element] = color
1363 color += 1
1364 end
1365 end
1366 end
1367
1368 fun compute_masks(elements: Map[MClassType, Set[MType]]): Map[MClassType, Int] do
1369 for mclasstype, mtypes in elements do
1370 self.masks[mclasstype] = compute_mask(mtypes)
1371 end
1372 return self.masks
1373 end
1374
1375 private fun compute_mask(mtypes: Set[MType]): Int do
1376 var mask = 0
1377 loop
1378 var used = new List[Int]
1379 for mtype in mtypes do
1380 var res = op(mask, self.coloration_result[mtype])
1381 if used.has(res) then
1382 break
1383 else
1384 used.add(res)
1385 end
1386 end
1387 if used.length == mtypes.length then break
1388 mask += 1
1389 end
1390 return mask
1391 end
1392
1393 redef fun build_tables(elements: Map[MClassType, Set[MType]]): Map[MClassType, Array[nullable MType]] do
1394 var tables = new HashMap[MClassType, Array[nullable MType]]
1395
1396 for mclasstype, mtypes in elements do
1397 var table = new Array[nullable MType]
1398 for mtype in mtypes do
1399 var color = phash(self.coloration_result[mtype], masks[mclasstype])
1400 if table.length <= color then
1401 for i in [table.length .. color[ do
1402 table[i] = null
1403 end
1404 end
1405 table[color] = mtype
1406 end
1407 tables[mclasstype] = table
1408 end
1409 return tables
1410 end
1411
1412 private fun op(mask: Int, id:Int): Int is abstract
1413 private fun phash(id: Int, mask: Int): Int do return op(mask, id)
1414 end
1415
1416 class UnanchoredTypeModPerfectHashing
1417 super UnanchoredTypePerfectHashing
1418 init do end
1419 redef fun op(mask, id) do return mask % id
1420 end
1421
1422 class UnanchoredTypeAndPerfectHashing
1423 super UnanchoredTypePerfectHashing
1424 init do end
1425 redef fun op(mask, id) do return mask.bin_and(id)
1426 end
1427
1428
1429 # Utils
1430
1431 redef class HashSet[E]
1432 init from(elements: Collection[E]) do
1433 init
1434 self.add_all(elements)
1435 end
1436 end
1437
1438 redef class Array[E]
1439 init from(elements: Collection[E]) do
1440 init
1441 self.add_all(elements)
1442 end
1443
1444 # Return a new Array with the elements only contened in 'self' and not in 'o'
1445 fun -(o: Array[E]): Array[E] do
1446 var res = new Array[E]
1447 for e in self do if not o.has(e) then res.add(e)
1448 return res
1449 end
1450 end
1451
1452 redef class MModule
1453
1454 # Return a linearization of a set of mtypes
1455 private fun linearize_mtypes(mtypes: Set[MType]): Array[MType] do
1456 var lin = new Array[MType].from(mtypes)
1457 var sorter = new TypeSorter(self)
1458 sorter.sort(lin)
1459 return lin
1460 end
1461
1462 # Return a reverse linearization of a set of mtypes
1463 private fun reverse_linearize_mtypes(mtypes: Set[MType]): Array[MType] do
1464 var lin = new Array[MType].from(mtypes)
1465 var sorter = new ReverseTypeSorter(self)
1466 sorter.sort(lin)
1467 return lin
1468 end
1469
1470 # Return super types of a `mtype` in `self`
1471 private fun super_mtypes(mtype: MType, mtypes: Set[MType]): Set[MType] do
1472 if not self.super_mtypes_cache.has_key(mtype) then
1473 var supers = new HashSet[MType]
1474 for otype in mtypes do
1475 if otype == mtype then continue
1476 if mtype.is_subtype(self, null, otype) then
1477 supers.add(otype)
1478 end
1479 end
1480 self.super_mtypes_cache[mtype] = supers
1481 end
1482 return self.super_mtypes_cache[mtype]
1483 end
1484
1485 private var super_mtypes_cache: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
1486
1487 # Return all sub mtypes (directs and indirects) of a `mtype` in `self`
1488 private fun sub_mtypes(mtype: MType, mtypes: Set[MType]): Set[MType] do
1489 if not self.sub_mtypes_cache.has_key(mtype) then
1490 var subs = new HashSet[MType]
1491 for otype in mtypes do
1492 if otype == mtype then continue
1493 if otype.is_subtype(self, null, mtype) then
1494 subs.add(otype)
1495 end
1496 end
1497 self.sub_mtypes_cache[mtype] = subs
1498 end
1499 return self.sub_mtypes_cache[mtype]
1500 end
1501
1502 private var sub_mtypes_cache: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
1503
1504 # Return a linearization of a set of mclasses
1505 private fun linearize_mclasses(mclasses: Set[MClass]): Array[MClass] do
1506 var lin = new Array[MClass].from(mclasses)
1507 var sorter = new ClassSorter(self)
1508 sorter.sort(lin)
1509 return lin
1510 end
1511
1512 # Return a reverse linearization of a set of mtypes
1513 private fun reverse_linearize_mclasses(mclasses: Set[MClass]): Array[MClass] do
1514 var lin = new Array[MClass].from(mclasses)
1515 var sorter = new ReverseClassSorter(self)
1516 sorter.sort(lin)
1517 return lin
1518 end
1519
1520 # Return all super mclasses (directs and indirects) of a `mclass` in `self`
1521 private fun super_mclasses(mclass: MClass): Set[MClass] do
1522 if not self.super_mclasses_cache.has_key(mclass) then
1523 var supers = new HashSet[MClass]
1524 if self.flatten_mclass_hierarchy.has(mclass) then
1525 for sup in self.flatten_mclass_hierarchy[mclass].greaters do
1526 if sup == mclass then continue
1527 supers.add(sup)
1528 end
1529 end
1530 self.super_mclasses_cache[mclass] = supers
1531 end
1532 return self.super_mclasses_cache[mclass]
1533 end
1534
1535 private var super_mclasses_cache: Map[MClass, Set[MClass]] = new HashMap[MClass, Set[MClass]]
1536
1537 # Return all parents of a `mclass` in `self`
1538 private fun parent_mclasses(mclass: MClass): Set[MClass] do
1539 if not self.parent_mclasses_cache.has_key(mclass) then
1540 var parents = new HashSet[MClass]
1541 if self.flatten_mclass_hierarchy.has(mclass) then
1542 for sup in self.flatten_mclass_hierarchy[mclass].direct_greaters do
1543 if sup == mclass then continue
1544 parents.add(sup)
1545 end
1546 end
1547 self.parent_mclasses_cache[mclass] = parents
1548 end
1549 return self.parent_mclasses_cache[mclass]
1550 end
1551
1552 private var parent_mclasses_cache: Map[MClass, Set[MClass]] = new HashMap[MClass, Set[MClass]]
1553
1554 # Return all sub mclasses (directs and indirects) of a `mclass` in `self`
1555 private fun sub_mclasses(mclass: MClass): Set[MClass] do
1556 if not self.sub_mclasses_cache.has_key(mclass) then
1557 var subs = new HashSet[MClass]
1558 if self.flatten_mclass_hierarchy.has(mclass) then
1559 for sub in self.flatten_mclass_hierarchy[mclass].smallers do
1560 if sub == mclass then continue
1561 subs.add(sub)
1562 end
1563 end
1564 self.sub_mclasses_cache[mclass] = subs
1565 end
1566 return self.sub_mclasses_cache[mclass]
1567 end
1568
1569 private var sub_mclasses_cache: Map[MClass, Set[MClass]] = new HashMap[MClass, Set[MClass]]
1570
1571 # All 'mproperties' associated to all 'mclassdefs' of `mclass`
1572 private fun properties(mclass: MClass): Set[MProperty] do
1573 if not self.properties_cache.has_key(mclass) then
1574 var properties = new HashSet[MProperty]
1575 var parents = self.super_mclasses(mclass)
1576 for parent in parents do
1577 properties.add_all(self.properties(parent))
1578 end
1579
1580 for mclassdef in mclass.mclassdefs do
1581 for mpropdef in mclassdef.mpropdefs do
1582 properties.add(mpropdef.mproperty)
1583 end
1584 end
1585 self.properties_cache[mclass] = properties
1586 end
1587 return properties_cache[mclass]
1588 end
1589
1590 private var properties_cache: Map[MClass, Set[MProperty]] = new HashMap[MClass, Set[MProperty]]
1591 end
1592
1593 # A sorter for linearize list of types
1594 class TypeSorter
1595 super AbstractSorter[MType]
1596
1597 private var mmodule: MModule
1598
1599 init(mmodule: MModule) do self.mmodule = mmodule
1600
1601 redef fun compare(a, b) do
1602 if a == b then
1603 return 0
1604 else if a.is_subtype(self.mmodule, null, b) then
1605 return -1
1606 end
1607 return 1
1608 end
1609 end
1610
1611 # A sorter for reverse linearization
1612 class ReverseTypeSorter
1613 super TypeSorter
1614
1615 init(mmodule: MModule) do end
1616
1617 redef fun compare(a, b) do
1618 if a == b then
1619 return 0
1620 else if a.is_subtype(self.mmodule, null, b) then
1621 return 1
1622 end
1623 return -1
1624 end
1625 end
1626
1627 # A sorter for linearize list of classes
1628 private class ClassSorter
1629 super AbstractSorter[MClass]
1630
1631 var mmodule: MModule
1632
1633 redef fun compare(a, b) do
1634 if a == b then
1635 return 0
1636 else if self.mmodule.flatten_mclass_hierarchy.has(a) and self.mmodule.flatten_mclass_hierarchy[a].greaters.has(b) then
1637 return -1
1638 end
1639 return 1
1640 end
1641 end
1642
1643 # A sorter for reverse linearization
1644 private class ReverseClassSorter
1645 super AbstractSorter[MClass]
1646
1647 var mmodule: MModule
1648
1649 redef fun compare(a, b) do
1650 if a == b then
1651 return 0
1652 else if self.mmodule.flatten_mclass_hierarchy.has(a) and self.mmodule.flatten_mclass_hierarchy[a].greaters.has(b) then
1653 return 1
1654 end
1655 return -1
1656 end
1657 end
Nit language project; an oo programing language and its tool suite.