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 # Table layout builders
16 # Tables are used to implement objects mecanisms like:
18 # * attribute accessing
20 # * resolution (for generic types)
21 # This module provides various layout for object tables:
24 # * perfect hashing (and & mod operators)
25 module layout_builders
27 import abstract_compiler
31 # A layout is the result of computation by builders
32 # it contains necessary informations for basic table creation
33 class Layout[E
: Object]
35 var ids
: Map[E
, Int] = new HashMap[E
, Int]
36 # Fixed positions of each element in all tables
37 var pos
: Map[E
, Int] = new HashMap[E
, Int]
40 # A PHLayout is used everywere the builder used perfect hashing
41 # it adds masks and hashes informations to std layout
42 class PHLayout[HOLDER: Object, E
: Object]
44 # Masks used by hash function
45 var masks
: Map[HOLDER, Int] = new HashMap[HOLDER, Int]
46 # Positions of each element for each tables
47 var hashes
: Map[HOLDER, Map[E
, Int]] = new HashMap[HOLDER, Map[E
, Int]]
52 # TypingLayoutBuilder is used to build a layout for typing tables (by type or by class)
53 interface TypingLayoutBuilder[E
: Object]
54 # Build typing table layout
55 # elements: the set of elements (classes or types) used in typing tables
56 fun build_layout
(elements
: Set[E
]): Layout[E
] is abstract
59 # Layout builder dedicated to vft, attribute & VT tables
60 interface PropertyLayoutBuilder[E
: MProperty]
61 # Build table layout for attributes, methods and virtual types
62 # elements: the set of classes containing the properties to use in table layout
63 fun build_layout
(elements
: Set[MClass]): Layout[E
] is abstract
66 # For resolution tables (generics)
67 interface ResolutionLayoutBuilder
68 # Build resolution table layout
69 # elements: association between classes and resolved types
70 fun build_layout
(elements
: Map[MClassType, Set[MType]]): Layout[MType] is abstract
75 # Abstract layout builder for resolution tables using Binary Matrix (BM)
76 abstract class TypingBMizer[E
: Object]
77 super TypingLayoutBuilder[E
]
81 init(mmodule
: MModule) do
82 self.mmodule
= mmodule
85 # Compute mtypes ids and position using BM
86 redef fun build_layout
(elements
: Set[E
]): Layout[E
] do
87 var result
= new Layout[E
]
88 var ids
= new HashMap[E
, Int]
89 var lin
= self.reverse_linearize
(elements
)
91 ids
[element
] = ids
.length
98 private fun reverse_linearize
(elements
: Set[E
]): Array[E
] is abstract
101 # Layout builder for typing tables based on classes using Binary Matrix (BM)
103 super TypingBMizer[MType]
105 init(mmodule
: MModule) do super(mmodule
)
107 redef fun reverse_linearize
(elements
) do
108 return self.mmodule
.reverse_linearize_mtypes
(elements
)
112 # Layout builder for typing tables based on types using Binary Matrix (BM)
114 super TypingBMizer[MClass]
116 init(mmodule
: MModule) do super(mmodule
)
118 redef fun reverse_linearize
(elements
) do
119 return self.mmodule
.reverse_linearize_mclasses
(elements
)
123 # Layout builder for resolution tables using Binary Matrix (BM)
124 class ResolutionBMizer
125 super ResolutionLayoutBuilder
129 redef fun build_layout
(elements
) do
130 var result
= new Layout[MType]
131 var ids
= new HashMap[MType, Int]
133 for mclasstype
, mclasstypes
in elements
do
134 for element
in mclasstypes
do
135 if ids
.has_key
(element
) then continue
146 # Abstract Layout builder for mproperties using Binary Matrix (BM)
147 abstract class MPropertyBMizer[E
: MProperty]
148 super PropertyLayoutBuilder[E
]
150 type MPROP: MProperty
154 init(mmodule
: MModule) do self.mmodule
= mmodule
156 redef fun build_layout
(elements
) do
157 var result
= new Layout[E
]
158 var ids
= new HashMap[E
, Int]
159 var lin
= linearize_mclasses
(elements
)
161 for mproperty
in properties
(mclass
) do
162 if ids
.has_key
(mproperty
) then continue
163 ids
[mproperty
] = ids
.length
170 # extract properties of a mclass
171 private fun properties
(mclass
: MClass): Set[E
] do
172 var properties
= new HashSet[E
]
173 for mprop
in self.mmodule
.properties
(mclass
) do
174 if mprop
isa MPROP then properties
.add
(mprop
)
179 private fun linearize_mclasses
(mclasses
: Set[MClass]): Array[MClass] is abstract
182 # Layout builder for vft using Binary Matrix (BM)
184 super MPropertyBMizer[MMethod]
186 redef type MPROP: MMethod
187 init(mmodule
: MModule) do super(mmodule
)
188 # Less holes in tables with reverse linearization for method tables
189 redef fun linearize_mclasses
(mclasses
) do return self.mmodule
.reverse_linearize_mclasses
(mclasses
)
192 # Layout builder for attribute tables using Binary Matrix (BM)
193 class MAttributeBMizer
194 super MPropertyBMizer[MAttribute]
196 redef type MPROP: MAttribute
197 init(mmodule
: MModule) do super(mmodule
)
198 # Less holes in tables with linearization for attribute tables
199 redef fun linearize_mclasses
(mclasses
) do return self.mmodule
.linearize_mclasses_2
(mclasses
)
202 # BMizing for MVirtualTypeProps
203 class MVirtualTypePropBMizer
204 super MPropertyBMizer[MVirtualTypeProp]
206 redef type MPROP: MVirtualTypeProp
207 init(mmodule
: MModule) do super(mmodule
)
208 # Less holes in tables with reverse linearization for method tables
209 redef fun linearize_mclasses
(mclasses
) do return self.mmodule
.reverse_linearize_mclasses
(mclasses
)
214 # Abstract Layout builder for typing table using coloration (CL)
215 abstract class TypingColorer[E
: Object]
216 super TypingLayoutBuilder[E
]
218 private var core
: Set[E
] = new HashSet[E
]
219 private var crown
: Set[E
] = new HashSet[E
]
220 private var border
: Set[E
] = new HashSet[E
]
222 private var coloration_result
: Map[E
, Int] = new HashMap[E
, Int]
226 # Compute the layout with coloring
227 redef fun build_layout
(elements
: Set[E
]): Layout[E
] do
228 var result
= new Layout[E
]
229 result
.ids
= compute_ids
(elements
)
230 result
.pos
= colorize
(elements
)
234 private fun compute_ids
(elements
: Set[E
]): Map[E
, Int] do
235 var ids
= new HashMap[E
, Int]
236 var lin
= reverse_linearize
(elements
)
237 for element
in lin
do
238 ids
[element
] = ids
.length
243 private fun colorize
(elements
: Set[E
]): Map[E
, Int] do
244 tag_elements
(elements
)
245 build_conflicts_graph
(elements
)
246 colorize_elements
(core
)
247 colorize_elements
(border
)
248 colorize_elements
(crown
)
249 return coloration_result
252 # Colorize a collection of elements
253 private fun colorize_elements
(elements
: Set[E
]) do
256 var lin
= reverse_linearize
(elements
)
257 for element
in lin
do
258 var color
= min_color
259 while not self.is_color_free
(element
, elements
, color
) do
262 coloration_result
[element
] = color
267 # Check if a related element to the element already use the color
268 private fun is_color_free
(element
: E
, elements
: Set[E
], color
: Int): Bool do
269 if conflicts_graph
.has_key
(element
) then
270 for st
in conflicts_graph
[element
] do
271 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
274 for st
in self.super_elements
(element
, elements
) do
275 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
280 # Tag elements as core, crown or border
281 private fun tag_elements
(elements
: Set[E
]) do
282 for element
in elements
do
283 # Check if sub elements are all in single inheritance
284 var all_subelements_si
= true
285 for subelem
in self.sub_elements
(element
, elements
) do
286 if self.is_element_mi
(subelem
, elements
) then
287 all_subelements_si
= false
292 # Tag as core, crown or border
293 if self.is_element_mi
(element
, elements
) then
294 core
.add_all
(self.super_elements
(element
, elements
))
296 if all_subelements_si
then
299 else if not all_subelements_si
then
300 core
.add_all
(self.super_elements
(element
, elements
))
308 # Conflicts graph of elements hierarchy (two types are in conflict if they have common subelements)
309 private fun build_conflicts_graph
(elements
: Set[E
]) do
310 self.conflicts_graph
= new HashMap[E
, HashSet[E
]]
311 var core
= reverse_linearize
(self.core
)
313 for i
in self.linear_extension
(t
, elements
) do
314 if t
== i
then continue
316 var lin_i
= self.linear_extension
(i
, elements
)
318 for j
in self.linear_extension
(t
, elements
) do
319 if i
== j
or j
== t
then continue
320 var lin_j
= self.linear_extension
(j
, elements
)
322 var d_ij
= lin_i
- lin_j
323 var d_ji
= lin_j
- lin_i
326 if not conflicts_graph
.has_key
(ed1
) then conflicts_graph
[ed1
] = new HashSet[E
]
327 # add ed1 x ed2 to conflicts graph
328 for ed2
in d_ji
do conflicts_graph
[ed1
].add
(ed2
)
331 if not conflicts_graph
.has_key
(ed1
) then conflicts_graph
[ed1
] = new HashSet[E
]
332 # add ed1 x ed2 to conflicts graph
333 for ed2
in d_ji
do conflicts_graph
[ed1
].add
(ed2
)
340 private var conflicts_graph
: nullable HashMap[E
, Set[E
]]
342 # cache for linear_extensions
343 private var linear_extensions_cache
: Map[E
, Array[E
]] = new HashMap[E
, Array[E
]]
345 # Return a linear_extension of super_elements of the element
346 private fun linear_extension
(element
: E
, elements
: Set[E
]): Array[E
] do
347 if not self.linear_extensions_cache
.has_key
(element
) then
348 var supers
= new HashSet[E
]
350 supers
.add_all
(self.super_elements
(element
, elements
))
351 self.linear_extensions_cache
[element
] = self.linearize
(supers
)
353 return self.linear_extensions_cache
[element
]
356 private fun super_elements
(element
: E
, elements
: Set[E
]): Set[E
] is abstract
357 private fun sub_elements
(element
: E
, elements
: Set[E
]): Set[E
] is abstract
358 private fun is_element_mi
(element
: E
, elements
: Set[E
]): Bool is abstract
359 private fun linearize
(elements
: Set[E
]): Array[E
] is abstract
360 private fun reverse_linearize
(elements
: Set[E
]): Array[E
] is abstract
363 # Layout builder for typing tables based on types using coloration (CL)
365 super TypingColorer[MType]
369 init(mmodule
: MModule) do self.mmodule
= mmodule
371 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mtypes
(element
, elements
)
372 redef fun is_element_mi
(element
, elements
) do return self.super_elements
(element
, elements
).length
> 1
373 redef fun sub_elements
(element
, elements
) do do return self.mmodule
.sub_mtypes
(element
, elements
)
374 redef fun linearize
(elements
) do return self.mmodule
.linearize_mtypes
(elements
)
375 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mtypes
(elements
)
378 # Layout builder for typing tables based on classes using coloration (CL)
380 super TypingColorer[MClass]
382 private var mmodule
: MModule
384 init(mmodule
: MModule) do self.mmodule
= mmodule
386 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mclasses
(element
)
387 fun parent_elements
(element
: MClass): Set[MClass] do return self.mmodule
.parent_mclasses
(element
)
388 redef fun is_element_mi
(element
, elements
) do return self.parent_elements
(element
).length
> 1
389 redef fun sub_elements
(element
, elements
) do do return self.mmodule
.sub_mclasses
(element
)
390 redef fun linearize
(elements
) do return self.mmodule
.linearize_mclasses_2
(elements
)
391 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mclasses
(elements
)
394 # Abstract Layout builder for properties tables using coloration (CL)
395 abstract class MPropertyColorer[E
: MProperty]
396 super PropertyLayoutBuilder[E
]
398 type MPROP: MProperty
400 private var mmodule
: MModule
401 private var class_colorer
: MClassColorer
402 private var coloration_result
: Map[E
, Int] = new HashMap[E
, Int]
404 init(mmodule
: MModule) do
405 self.mmodule
= mmodule
406 self.class_colorer
= new MClassColorer(mmodule
)
409 # Compute mclasses ids and position using BM
410 redef fun build_layout
(mclasses
: Set[MClass]): Layout[E
] do
411 var result
= new Layout[E
]
412 result
.pos
= self.colorize
(mclasses
)
416 private fun colorize
(mclasses
: Set[MClass]): Map[E
, Int] do
417 self.class_colorer
.tag_elements
(mclasses
)
418 self.class_colorer
.build_conflicts_graph
(mclasses
)
419 self.colorize_core
(self.class_colorer
.core
)
420 self.colorize_crown
(self.class_colorer
.crown
)
421 return self.coloration_result
424 # Colorize properties of the core hierarchy
425 private fun colorize_core
(mclasses
: Set[MClass]) do
427 for mclass
in mclasses
do
428 var color
= min_color
430 # if the class is root, get the minimal color
431 if self.mmodule
.parent_mclasses
(mclass
).length
== 0 then
432 colorize_elements
(self.properties
(mclass
), color
)
434 # check last color used by parents
435 color
= max_color
(color
, self.mmodule
.parent_mclasses
(mclass
))
436 # check max color used in conflicts
437 if self.class_colorer
.conflicts_graph
.has_key
(mclass
) then
438 color
= max_color
(color
, self.class_colorer
.conflicts_graph
[mclass
])
440 colorize_elements
(self.properties
(mclass
), color
)
445 # Colorize properties of the crown hierarchy
446 private fun colorize_crown
(mclasses
: Set[MClass]) do
447 for mclass
in mclasses
do
448 colorize_elements
(self.properties
(mclass
), max_color
(0, self.mmodule
.parent_mclasses
(mclass
)))
452 # Colorize a collection of mproperties given a starting color
453 private fun colorize_elements
(elements
: Collection[E
], start_color
: Int) do
454 for element
in elements
do
455 if self.coloration_result
.has_key
(element
) then continue
456 self.coloration_result
[element
] = start_color
461 private fun max_color
(min_color
: Int, mclasses
: Collection[MClass]): Int do
462 var max_color
= min_color
464 for mclass
in mclasses
do
465 for mproperty
in self.properties
(mclass
) do
466 var color
= min_color
467 if self.coloration_result
.has_key
(mproperty
) then
468 color
= self.coloration_result
[mproperty
]
469 if color
>= max_color
then max_color
= color
+ 1
477 private fun properties
(mclass
: MClass): Set[E
] do
478 var properties
= new HashSet[E
]
479 for mprop
in self.mmodule
.properties
(mclass
) do
480 if mprop
isa MPROP then properties
.add
(mprop
)
486 # Layout builder for vft using coloration (CL)
488 super MPropertyColorer[MMethod]
490 redef type MPROP: MMethod
491 init(mmodule
: MModule) do super
494 # Layout builder for attributes using coloration (CL)
495 class MAttributeColorer
496 super MPropertyColorer[MAttribute]
498 redef type MPROP: MAttribute
499 init(mmodule
: MModule) do super
502 # Layout builder for virtual types using coloration (CL)
503 class MVirtualTypePropColorer
504 super MPropertyColorer[MVirtualTypeProp]
506 redef type MPROP: MVirtualTypeProp
507 init(mmodule
: MModule) do super
510 # Layout builder for resolution tables using coloration (CL)
511 class ResolutionColorer
512 super ResolutionLayoutBuilder
514 private var coloration_result
: Map[MType, Int] = new HashMap[MType, Int]
518 # Compute resolved types colors
519 redef fun build_layout
(elements
) do
520 self.build_conflicts_graph
(elements
)
521 var result
= new Layout[MType]
522 result
.ids
= self.compute_ids
(elements
)
523 result
.pos
= self.colorize_elements
(elements
)
527 private fun compute_ids
(elements
: Map[MClassType, Set[MType]]): Map[MType, Int] do
528 var ids
= new HashMap[MType, Int]
530 for mclasstype
, mclasstypes
in elements
do
531 for element
in mclasstypes
do
532 if ids
.has_key
(element
) then continue
540 # Colorize a collection of elements
541 private fun colorize_elements
(elements
: Map[MClassType, Set[MType]]): Map[MType, Int] do
543 for mclasstype
, mclasstypes
in elements
do
544 for element
in mclasstypes
do
545 if self.coloration_result
.has_key
(element
) then continue
546 var color
= min_color
547 while not self.is_color_free
(element
, color
) do
550 coloration_result
[element
] = color
554 return self.coloration_result
557 # Check if a related element to the element already use the color
558 private fun is_color_free
(element
: MType, color
: Int): Bool do
559 if conflicts_graph
.has_key
(element
) then
560 for st
in conflicts_graph
[element
] do
561 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
567 # look for unanchored types generated by the same type
568 private fun build_conflicts_graph
(elements
: Map[MClassType, Set[MType]]) do
569 for mclasstype
, mtypes
in elements
do
570 for mtype
in mtypes
do
571 for otype
in mtypes
do
572 if otype
== mtype
then continue
573 self.add_conflict
(mtype
, otype
)
579 private var conflicts_graph
: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
581 private fun add_conflict
(mtype
: MType, otype
: MType) do
582 if mtype
== otype
then return
583 if not self.conflicts_graph
.has_key
(mtype
) then self.conflicts_graph
[mtype
] = new HashSet[MType]
584 self.conflicts_graph
[mtype
].add
(otype
)
585 if not self.conflicts_graph
.has_key
(otype
) then self.conflicts_graph
[otype
] = new HashSet[MType]
586 self.conflicts_graph
[otype
].add
(mtype
)
590 # Perfect Hashing (PH)
592 # U = type of elements to hash
593 private class PerfectHasher[T
: Object, U
: Object]
595 var operator
: PHOperator
597 init(operator
: PHOperator) do self.operator
= operator
599 # Compute mask for each holders
600 fun compute_masks
(conflicts
: Map[T
, Set[U
]], ids
: Map[U
, Int]): Map[T
, Int] do
601 var masks
= new HashMap[T
, Int]
602 for mclasstype
, mtypes
in conflicts
do
603 masks
[mclasstype
] = compute_mask
(mtypes
, ids
)
608 private fun compute_mask
(mtypes
: Set[U
], ids
: Map[U
, Int]): Int do
611 var used
= new List[Int]
612 for mtype
in mtypes
do
613 var res
= operator
.op
(mask
, ids
[mtype
])
614 if used
.has
(res
) then
620 if used
.length
== mtypes
.length
then break
626 # Compute hash for each element in each holder
627 fun compute_hashes
(elements
: Map[T
, Set[U
]], ids
: Map[U
, Int], masks
: Map[T
, Int]): Map[T
, Map[U
, Int]] do
628 var hashes
= new HashMap[T
, Map[U
, Int]]
629 for mclasstype
, mtypes
in elements
do
630 var mask
= masks
[mclasstype
]
631 var inhashes
= new HashMap[U
, Int]
632 for mtype
in mtypes
do
633 inhashes
[mtype
] = operator
.op
(mask
, ids
[mtype
])
635 hashes
[mclasstype
] = inhashes
641 # Abstract operator used for perfect hashing
642 abstract class PHOperator
643 # hash `id` using `mask`
644 fun op
(mask
: Int, id
:Int): Int is abstract
647 # Hashing using modulo (MOD) operator
652 redef fun op
(mask
, id
) do return mask
% id
655 # Hashing using binary and (AND) operator
660 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
663 # Layout builder for typing tables using perfect hashing (PH)
664 class TypingHasher[E
: Object]
665 super PerfectHasher[E
, E
]
666 super TypingLayoutBuilder[E
]
670 init(operator
: PHOperator, mmodule
: MModule) do
672 self.mmodule
= mmodule
675 redef fun build_layout
(elements
: Set[E
]): PHLayout[E
, E
] do
676 var result
= new PHLayout[E
, E
]
677 var conflicts
= self.build_conflicts
(elements
)
678 result
.ids
= self.compute_ids
(elements
)
679 result
.masks
= self.compute_masks
(conflicts
, result
.ids
)
680 result
.hashes
= self.compute_hashes
(conflicts
, result
.ids
, result
.masks
)
684 # Ids start from 1 instead of 0
685 private fun compute_ids
(elements
: Set[E
]): Map[E
, Int] do
686 var ids
= new HashMap[E
, Int]
687 var lin
= self.reverse_linearize
(elements
)
689 ids
[e
] = ids
.length
+ 1
694 private fun build_conflicts
(elements
: Set[E
]): Map[E
, Set[E
]] do
695 var conflicts
= new HashMap[E
, Set[E
]]
697 var supers
= self.super_elements
(e
, elements
)
699 conflicts
[e
] = supers
704 private fun super_elements
(element
: E
, elements
: Set[E
]): Set[E
] is abstract
705 private fun reverse_linearize
(elements
: Set[E
]): Array[E
] is abstract
708 # Layout builder for typing tables with types using perfect hashing (PH)
710 super TypingHasher[MType]
712 init(operator
: PHOperator, mmodule
: MModule) do super(operator
, mmodule
)
714 redef fun super_elements
(element
, elements
) do
715 return self.mmodule
.super_mtypes
(element
, elements
)
718 redef fun reverse_linearize
(elements
) do
719 return self.mmodule
.reverse_linearize_mtypes
(elements
)
723 # Layout builder for typing tables with classes using perfect hashing (PH)
725 super TypingHasher[MClass]
727 init(operator
: PHOperator, mmodule
: MModule) do super(operator
, mmodule
)
729 redef fun super_elements
(element
, elements
) do
730 return self.mmodule
.super_mclasses
(element
)
733 redef fun reverse_linearize
(elements
) do
734 return self.mmodule
.reverse_linearize_mclasses
(elements
)
738 # Abstract layout builder for properties tables using perfect hashing (PH)
739 class MPropertyHasher[E
: MProperty]
740 super PerfectHasher[MClass, E
]
741 super PropertyLayoutBuilder[E
]
743 type MPROP: MProperty
747 init(operator
: PHOperator, mmodule
: MModule) do
749 self.mmodule
= mmodule
752 redef fun build_layout
(mclasses
) do
753 var result
= new PHLayout[MClass, E
]
754 var ids
= new HashMap[E
, Int]
755 var elements
= new HashMap[MClass, Set[E
]]
756 var lin
= linearize_mclasses
(mclasses
)
758 var mproperties
= properties
(mclass
)
759 for mproperty
in mproperties
do
760 if ids
.has_key
(mproperty
) then continue
761 ids
[mproperty
] = ids
.length
+ 1
763 elements
[mclass
] = mproperties
767 result
.masks
= self.compute_masks
(elements
, ids
)
768 result
.hashes
= self.compute_hashes
(elements
, ids
, result
.masks
)
772 # extract set of properties from mclass
773 private fun properties
(mclass
: MClass): Set[E
] do
774 var properties
= new HashSet[E
]
775 for mprop
in self.mmodule
.properties
(mclass
) do
776 if mprop
isa MPROP then properties
.add
(mprop
)
781 private fun linearize_mclasses
(mclasses
: Set[MClass]): Array[MClass] is abstract
784 # Layout builder for vft using perfect hashing (PH)
786 super MPropertyHasher[MMethod]
788 redef type MPROP: MMethod
789 init(operator
: PHOperator, mmodule
: MModule) do super(operator
, mmodule
)
790 redef fun linearize_mclasses
(mclasses
) do return self.mmodule
.reverse_linearize_mclasses
(mclasses
)
793 # Layout builder for attributes tables using perfect hashing (PH)
794 class MAttributeHasher
795 super MPropertyHasher[MAttribute]
797 redef type MPROP: MAttribute
798 init(operator
: PHOperator, mmodule
: MModule) do super(operator
, mmodule
)
799 redef fun linearize_mclasses
(mclasses
) do return self.mmodule
.linearize_mclasses_2
(mclasses
)
802 # Layout builder for virtual types tables using perfect hashing (PH)
803 class MVirtualTypePropHasher
804 super MPropertyHasher[MVirtualTypeProp]
806 redef type MPROP: MVirtualTypeProp
807 init(operator
: PHOperator, mmodule
: MModule) do super(operator
, mmodule
)
808 redef fun linearize_mclasses
(mclasses
) do return self.mmodule
.reverse_linearize_mclasses
(mclasses
)
811 # Layout builder for resolution tables using perfect hashing (PH)
812 class ResolutionHasher
813 super PerfectHasher[MClassType, MType]
814 super ResolutionLayoutBuilder
816 init(operator
: PHOperator) do super(operator
)
818 # Compute resolved types masks and hashes
819 redef fun build_layout
(elements
) do
820 var result
= new PHLayout[MClassType, MType]
821 var ids
= new HashMap[MType, Int]
823 for mclasstype
, mclasstypes
in elements
do
824 for element
in mclasstypes
do
825 if ids
.has_key
(element
) then continue
832 result
.masks
= self.compute_masks
(elements
, ids
)
833 result
.hashes
= self.compute_hashes
(elements
, ids
, result
.masks
)