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
57 # Get the poset used for table layout construction
58 # REQUIRE: build_layout
59 fun poset
: nullable POSet[E
] is abstract
62 # Layout builder dedicated to vft, attribute & VT tables
63 interface PropertyLayoutBuilder[E
: MProperty]
64 # Build table layout for attributes, methods and virtual types
65 # elements: the set of classes containing the properties to use in table layout
66 fun build_layout
(elements
: Set[MClass]): Layout[E
] is abstract
69 # For resolution tables (generics)
70 interface ResolutionLayoutBuilder
71 # Build resolution table layout
72 # elements: association between classes and resolved types
73 fun build_layout
(elements
: Map[MClassType, Set[MType]]): Layout[MType] is abstract
78 # A POSet builder build a poset for a set of MType or MClass
79 # the resulting poset is used by the layout builders
80 private abstract class POSetBuilder[E
: Object]
81 private var mmodule
: MModule
82 init(mmodule
: MModule) do self.mmodule
= mmodule
83 # Build the poset from `elements`
84 private fun build_poset
(elements
: Set[E
]): POSet[E
] is abstract
87 # A TypingLayoutBuilder used for MType based typing
88 # such as in separate compilers
89 private class MTypePOSetBuilder
90 super POSetBuilder[MType]
91 redef fun build_poset
(elements
) do
92 var poset
= new POSet[MType]
96 if e
== o
then continue
97 if e
.is_subtype
(mmodule
, null, o
) then
106 # A TypingLayoutBuilder used for MClass based typing
107 # such as in erased compilers or used in property coloring
108 private class MClassPOSetBuilder
109 super POSetBuilder[MClass]
110 redef fun build_poset
(elements
) do return mmodule
.flatten_mclass_hierarchy
115 # Abstract layout builder for resolution tables using Binary Matrix (BM)
116 abstract class TypingBMizer[E
: Object]
117 super TypingLayoutBuilder[E
]
119 private var mmodule
: MModule
120 private var poset_builder
: POSetBuilder[E
]
121 private var poset_cache
: nullable POSet[E
]
123 private init(mmodule
: MModule, poset_builder
: POSetBuilder[E
]) do
124 self.mmodule
= mmodule
125 self.poset_builder
= poset_builder
128 redef fun poset
do return poset_cache
130 # Compute mtypes ids and position using BM
131 redef fun build_layout
(elements
: Set[E
]): Layout[E
] do
132 var result
= new Layout[E
]
133 var ids
= new HashMap[E
, Int]
134 poset_cache
= poset_builder
.build_poset
(elements
)
137 for element
in lin
do
138 ids
[element
] = ids
.length
146 # Layout builder for typing tables based on classes using Binary Matrix (BM)
148 super TypingBMizer[MType]
149 init(mmodule
: MModule) do super(mmodule
, new MTypePOSetBuilder(mmodule
))
152 # Layout builder for typing tables based on types using Binary Matrix (BM)
154 super TypingBMizer[MClass]
155 init(mmodule
: MModule) do super(mmodule
, new MClassPOSetBuilder(mmodule
))
158 # Layout builder for resolution tables using Binary Matrix (BM)
159 class ResolutionBMizer
160 super ResolutionLayoutBuilder
164 redef fun build_layout
(elements
) do
165 var result
= new Layout[MType]
166 var ids
= new HashMap[MType, Int]
168 for mclasstype
, mclasstypes
in elements
do
169 for element
in mclasstypes
do
170 if ids
.has_key
(element
) then continue
181 # Abstract Layout builder for mproperties using Binary Matrix (BM)
182 abstract class MPropertyBMizer[E
: MProperty]
183 super PropertyLayoutBuilder[E
]
185 type MPROP: MProperty
189 init(mmodule
: MModule) do self.mmodule
= mmodule
191 redef fun build_layout
(elements
) do
192 var result
= new Layout[E
]
193 var ids
= new HashMap[E
, Int]
194 var lin
= new Array[MClass]
195 lin
.add_all
(elements
)
196 self.mmodule
.linearize_mclasses
(lin
)
198 for mproperty
in properties
(mclass
) do
199 if ids
.has_key
(mproperty
) then continue
200 ids
[mproperty
] = ids
.length
207 # extract properties of a mclass
208 private fun properties
(mclass
: MClass): Set[E
] do
209 var properties
= new HashSet[E
]
210 for mprop
in self.mmodule
.properties
(mclass
) do
211 if mprop
isa MPROP then properties
.add
(mprop
)
217 # Layout builder for vft using Binary Matrix (BM)
219 super MPropertyBMizer[MMethod]
220 redef type MPROP: MMethod
221 init(mmodule
: MModule) do super(mmodule
)
224 # Layout builder for attribute tables using Binary Matrix (BM)
225 class MAttributeBMizer
226 super MPropertyBMizer[MAttribute]
227 redef type MPROP: MAttribute
228 init(mmodule
: MModule) do super(mmodule
)
231 # BMizing for MVirtualTypeProps
232 class MVirtualTypePropBMizer
233 super MPropertyBMizer[MVirtualTypeProp]
234 redef type MPROP: MVirtualTypeProp
235 init(mmodule
: MModule) do super(mmodule
)
240 # Abstract Layout builder for typing table using coloration (CL)
241 abstract class TypingColorer[E
: Object]
242 super TypingLayoutBuilder[E
]
244 private var core
: Set[E
] = new HashSet[E
]
245 private var crown
: Set[E
] = new HashSet[E
]
246 private var border
: Set[E
] = new HashSet[E
]
247 private var coloration_result
: Map[E
, Int] = new HashMap[E
, Int]
249 private var mmodule
: MModule
250 private var poset_builder
: POSetBuilder[E
]
251 private var poset_cache
: nullable POSet[E
]
253 private init(mmodule
: MModule, poset_builder
: POSetBuilder[E
]) do
254 self.mmodule
= mmodule
255 self.poset_builder
= poset_builder
258 redef fun poset
do return poset_cache
260 # Compute the layout with coloring
261 redef fun build_layout
(elements
: Set[E
]): Layout[E
] do
262 poset_cache
= poset_builder
.build_poset
(elements
)
263 var result
= new Layout[E
]
264 result
.ids
= compute_ids
(elements
)
265 result
.pos
= colorize
(elements
)
269 private fun compute_ids
(elements
: Set[E
]): Map[E
, Int] do
270 var ids
= new HashMap[E
, Int]
271 for element
in reverse_linearize
(elements
) do
272 ids
[element
] = ids
.length
277 private fun colorize
(elements
: Set[E
]): Map[E
, Int] do
278 tag_elements
(elements
)
279 build_conflicts_graph
280 colorize_elements
(core
)
281 colorize_elements
(border
)
282 colorize_elements
(crown
)
283 return coloration_result
286 # Colorize a collection of elements
287 private fun colorize_elements
(elements
: Set[E
]) do
290 var lin
= reverse_linearize
(elements
)
291 for element
in lin
do
292 var color
= min_color
293 while not self.is_color_free
(element
, elements
, color
) do
296 coloration_result
[element
] = color
301 # Check if a related element to the element already use the color
302 private fun is_color_free
(element
: E
, elements
: Set[E
], color
: Int): Bool do
303 if conflicts_graph
.has_key
(element
) then
304 for st
in conflicts_graph
[element
] do
305 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
308 for st
in self.poset
[element
].greaters
do
309 if st
== element
then continue
310 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
315 # Tag elements as core, crown or border
316 private fun tag_elements
(elements
: Set[E
]) do
317 for element
in elements
do
318 # Check if sub elements are all in single inheritance
319 var all_subelements_si
= true
320 for subelem
in self.poset
[element
].smallers
do
321 if self.poset
[subelem
].direct_greaters
.length
> 1 then
322 all_subelements_si
= false
327 # Tag as core, crown or border
328 if self.poset
[element
].direct_greaters
.length
> 1 then
329 core
.add_all
(self.poset
[element
].greaters
)
330 if all_subelements_si
then
333 else if not all_subelements_si
then
334 core
.add_all
(self.poset
[element
].greaters
)
341 # Conflicts graph of elements hierarchy (two types are in conflict if they have common subelements)
342 private fun build_conflicts_graph
do
343 self.conflicts_graph
= new HashMap[E
, HashSet[E
]]
344 var core
= reverse_linearize
(self.core
)
346 for i
in self.linear_extension
(t
) do
347 if t
== i
then continue
349 var lin_i
= self.linear_extension
(i
)
351 for j
in self.linear_extension
(t
) do
352 if i
== j
or j
== t
then continue
353 var lin_j
= self.linear_extension
(j
)
355 var d_ij
= lin_i
- lin_j
356 var d_ji
= lin_j
- lin_i
359 if not conflicts_graph
.has_key
(ed1
) then conflicts_graph
[ed1
] = new HashSet[E
]
360 # add ed1 x ed2 to conflicts graph
361 for ed2
in d_ji
do conflicts_graph
[ed1
].add
(ed2
)
364 if not conflicts_graph
.has_key
(ed1
) then conflicts_graph
[ed1
] = new HashSet[E
]
365 # add ed1 x ed2 to conflicts graph
366 for ed2
in d_ji
do conflicts_graph
[ed1
].add
(ed2
)
373 private var conflicts_graph
: nullable HashMap[E
, Set[E
]]
375 # cache for linear_extensions
376 private var linear_extensions_cache
: Map[E
, Array[E
]] = new HashMap[E
, Array[E
]]
378 # Return a linear_extension of super_elements of the element
379 private fun linear_extension
(element
: E
): Array[E
] do
380 if not self.linear_extensions_cache
.has_key
(element
) then
381 var supers
= new HashSet[E
]
382 supers
.add_all
(self.poset
[element
].greaters
)
383 self.linear_extensions_cache
[element
] = self.linearize
(supers
)
385 return self.linear_extensions_cache
[element
]
388 private fun reverse_linearize
(elements
: Set[E
]): Array[E
] do
389 var lin
= new Array[E
]
390 lin
.add_all
(elements
)
394 private fun linearize
(elements
: Set[E
]): Array[E
] do return reverse_linearize
(elements
).reversed
397 # Layout builder for typing tables based on types using coloration (CL)
399 super TypingColorer[MType]
400 init(mmodule
: MModule) do super(mmodule
, new MTypePOSetBuilder(mmodule
))
403 # Layout builder for typing tables based on classes using coloration (CL)
405 super TypingColorer[MClass]
406 init(mmodule
: MModule) do super(mmodule
, new MClassPOSetBuilder(mmodule
))
409 # Abstract Layout builder for properties tables using coloration (CL)
410 abstract class MPropertyColorer[E
: MProperty]
411 super PropertyLayoutBuilder[E
]
413 type MPROP: MProperty
415 private var mmodule
: MModule
416 private var class_colorer
: MClassColorer
417 private var coloration_result
: Map[E
, Int] = new HashMap[E
, Int]
419 init(mmodule
: MModule, class_colorer
: MClassColorer) do
420 self.mmodule
= mmodule
421 self.class_colorer
= class_colorer
424 # Compute mclasses ids and position using BM
425 redef fun build_layout
(mclasses
: Set[MClass]): Layout[E
] do
426 var result
= new Layout[E
]
427 result
.pos
= self.colorize
(mclasses
)
431 private fun colorize
(mclasses
: Set[MClass]): Map[E
, Int] do
432 self.colorize_core
(self.class_colorer
.core
)
433 self.colorize_crown
(self.class_colorer
.crown
)
434 return self.coloration_result
437 # Colorize properties of the core hierarchy
438 private fun colorize_core
(mclasses
: Set[MClass]) do
440 for mclass
in mclasses
do
441 var color
= min_color
442 # check last color used by parents
443 color
= max_color
(color
, mclass
.in_hierarchy
(mmodule
).direct_greaters
)
444 # check max color used in conflicts
445 if self.class_colorer
.conflicts_graph
.has_key
(mclass
) then
446 color
= max_color
(color
, self.class_colorer
.conflicts_graph
[mclass
])
448 colorize_elements
(self.properties
(mclass
), color
)
452 # Colorize properties of the crown hierarchy
453 private fun colorize_crown
(mclasses
: Set[MClass]) do
454 for mclass
in mclasses
do
455 var parents
= new HashSet[MClass]
456 if mmodule
.flatten_mclass_hierarchy
.has
(mclass
) then
457 parents
.add_all
(mclass
.in_hierarchy
(mmodule
).direct_greaters
)
459 colorize_elements
(self.properties
(mclass
), max_color
(0, parents
))
463 # Colorize a collection of mproperties given a starting color
464 private fun colorize_elements
(elements
: Collection[E
], start_color
: Int) do
465 for element
in elements
do
466 if self.coloration_result
.has_key
(element
) then continue
467 self.coloration_result
[element
] = start_color
472 private fun max_color
(min_color
: Int, mclasses
: Collection[MClass]): Int do
473 var max_color
= min_color
475 for mclass
in mclasses
do
476 for mproperty
in self.properties
(mclass
) do
477 var color
= min_color
478 if self.coloration_result
.has_key
(mproperty
) then
479 color
= self.coloration_result
[mproperty
]
480 if color
>= max_color
then max_color
= color
+ 1
488 private fun properties
(mclass
: MClass): Set[E
] do
489 var properties
= new HashSet[E
]
490 for mprop
in self.mmodule
.properties
(mclass
) do
491 if mprop
isa MPROP then properties
.add
(mprop
)
497 # Layout builder for vft using coloration (CL)
499 super MPropertyColorer[MMethod]
501 redef type MPROP: MMethod
502 init(mmodule
: MModule, class_colorer
: MClassColorer) do super(mmodule
, class_colorer
)
505 # Layout builder for attributes using coloration (CL)
506 class MAttributeColorer
507 super MPropertyColorer[MAttribute]
509 redef type MPROP: MAttribute
510 init(mmodule
: MModule, class_colorer
: MClassColorer) do super(mmodule
, class_colorer
)
513 # Layout builder for virtual types using coloration (CL)
514 class MVirtualTypePropColorer
515 super MPropertyColorer[MVirtualTypeProp]
517 redef type MPROP: MVirtualTypeProp
518 init(mmodule
: MModule, class_colorer
: MClassColorer) do super(mmodule
, class_colorer
)
521 # Layout builder for resolution tables using coloration (CL)
522 class ResolutionColorer
523 super ResolutionLayoutBuilder
525 private var coloration_result
: Map[MType, Int] = new HashMap[MType, Int]
529 # Compute resolved types colors
530 redef fun build_layout
(elements
) do
531 self.build_conflicts_graph
(elements
)
532 var result
= new Layout[MType]
533 result
.ids
= self.compute_ids
(elements
)
534 result
.pos
= self.colorize_elements
(elements
)
538 private fun compute_ids
(elements
: Map[MClassType, Set[MType]]): Map[MType, Int] do
539 var ids
= new HashMap[MType, Int]
541 for mclasstype
, mclasstypes
in elements
do
542 for element
in mclasstypes
do
543 if ids
.has_key
(element
) then continue
551 # Colorize a collection of elements
552 private fun colorize_elements
(elements
: Map[MClassType, Set[MType]]): Map[MType, Int] do
554 for mclasstype
, mclasstypes
in elements
do
555 for element
in mclasstypes
do
556 if self.coloration_result
.has_key
(element
) then continue
557 var color
= min_color
558 while not self.is_color_free
(element
, color
) do
561 coloration_result
[element
] = color
565 return self.coloration_result
568 # Check if a related element to the element already use the color
569 private fun is_color_free
(element
: MType, color
: Int): Bool do
570 if conflicts_graph
.has_key
(element
) then
571 for st
in conflicts_graph
[element
] do
572 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
578 # look for unanchored types generated by the same type
579 private fun build_conflicts_graph
(elements
: Map[MClassType, Set[MType]]) do
580 for mclasstype
, mtypes
in elements
do
581 for mtype
in mtypes
do
582 for otype
in mtypes
do
583 if otype
== mtype
then continue
584 self.add_conflict
(mtype
, otype
)
590 private var conflicts_graph
: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
592 private fun add_conflict
(mtype
: MType, otype
: MType) do
593 if mtype
== otype
then return
594 if not self.conflicts_graph
.has_key
(mtype
) then self.conflicts_graph
[mtype
] = new HashSet[MType]
595 self.conflicts_graph
[mtype
].add
(otype
)
596 if not self.conflicts_graph
.has_key
(otype
) then self.conflicts_graph
[otype
] = new HashSet[MType]
597 self.conflicts_graph
[otype
].add
(mtype
)
601 # Perfect Hashing (PH)
603 # U = type of elements to hash
604 private class PerfectHasher[T
: Object, U
: Object]
606 var operator
: PHOperator
610 # Compute mask for each holders
611 fun compute_masks
(conflicts
: Map[T
, Set[U
]], ids
: Map[U
, Int]): Map[T
, Int] do
612 var masks
= new HashMap[T
, Int]
613 for mclasstype
, mtypes
in conflicts
do
614 masks
[mclasstype
] = compute_mask
(mtypes
, ids
)
619 private fun compute_mask
(mtypes
: Set[U
], ids
: Map[U
, Int]): Int do
622 var used
= new List[Int]
623 for mtype
in mtypes
do
624 var res
= operator
.op
(mask
, ids
[mtype
])
625 if used
.has
(res
) then
631 if used
.length
== mtypes
.length
then break
637 # Compute hash for each element in each holder
638 fun compute_hashes
(elements
: Map[T
, Set[U
]], ids
: Map[U
, Int], masks
: Map[T
, Int]): Map[T
, Map[U
, Int]] do
639 var hashes
= new HashMap[T
, Map[U
, Int]]
640 for mclasstype
, mtypes
in elements
do
641 var mask
= masks
[mclasstype
]
642 var inhashes
= new HashMap[U
, Int]
643 for mtype
in mtypes
do
644 inhashes
[mtype
] = operator
.op
(mask
, ids
[mtype
])
646 hashes
[mclasstype
] = inhashes
652 # Abstract operator used for perfect hashing
653 abstract class PHOperator
654 # hash `id` using `mask`
655 fun op
(mask
: Int, id
:Int): Int is abstract
658 # Hashing using modulo (MOD) operator
663 redef fun op
(mask
, id
) do return mask
% id
666 # Hashing using binary and (AND) operator
671 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
674 # Layout builder for typing tables using perfect hashing (PH)
675 class TypingHasher[E
: Object]
676 super PerfectHasher[E
, E
]
677 super TypingLayoutBuilder[E
]
679 private var mmodule
: MModule
680 private var poset_builder
: POSetBuilder[E
]
681 private var poset_cache
: nullable POSet[E
]
683 private init(mmodule
: MModule, poset_builder
: POSetBuilder[E
], operator
: PHOperator) do
684 self.operator
= operator
685 self.mmodule
= mmodule
686 self.poset_builder
= poset_builder
689 redef fun build_layout
(elements
: Set[E
]): PHLayout[E
, E
] do
690 poset_cache
= poset_builder
.build_poset
(elements
)
691 var result
= new PHLayout[E
, E
]
692 var conflicts
= self.build_conflicts
(elements
)
693 result
.ids
= self.compute_ids
694 result
.masks
= self.compute_masks
(conflicts
, result
.ids
)
695 result
.hashes
= self.compute_hashes
(conflicts
, result
.ids
, result
.masks
)
699 # Ids start from 1 instead of 0
700 private fun compute_ids
: Map[E
, Int] do
701 var ids
= new HashMap[E
, Int]
705 ids
[e
] = ids
.length
+ 1
710 private fun build_conflicts
(elements
: Set[E
]): Map[E
, Set[E
]] do
711 var conflicts
= new HashMap[E
, Set[E
]]
713 var supers
= new HashSet[E
]
714 supers
.add_all
(self.poset
[e
].greaters
)
716 conflicts
[e
] = supers
722 # Layout builder for typing tables with types using perfect hashing (PH)
724 super TypingHasher[MType]
725 init(operator
: PHOperator, mmodule
: MModule) do super(mmodule
, new MTypePOSetBuilder(mmodule
), operator
)
728 # Layout builder for typing tables with classes using perfect hashing (PH)
730 super TypingHasher[MClass]
731 init(operator
: PHOperator, mmodule
: MModule) do super(mmodule
, new MClassPOSetBuilder(mmodule
), operator
)
734 # Abstract layout builder for properties tables using perfect hashing (PH)
735 class MPropertyHasher[E
: MProperty]
736 super PerfectHasher[MClass, E
]
737 super PropertyLayoutBuilder[E
]
739 type MPROP: MProperty
743 init(operator
: PHOperator, mmodule
: MModule) do
744 self.operator
= operator
745 self.mmodule
= mmodule
748 fun build_poset
(mclasses
: Set[MClass]): POSet[MClass] do
749 var poset
= new POSet[MClass]
753 if e
== o
or not mmodule
.flatten_mclass_hierarchy
.has
(e
) then continue
754 if e
.in_hierarchy
(mmodule
) < o
then poset
.add_edge
(e
, o
)
760 redef fun build_layout
(mclasses
) do
761 var result
= new PHLayout[MClass, E
]
762 var ids
= new HashMap[E
, Int]
763 var elements
= new HashMap[MClass, Set[E
]]
764 var poset
= build_poset
(mclasses
)
767 for mclass
in lin
.reversed
do
768 var mproperties
= properties
(mclass
)
769 for mproperty
in mproperties
do
770 if ids
.has_key
(mproperty
) then continue
771 ids
[mproperty
] = ids
.length
+ 1
773 elements
[mclass
] = mproperties
777 result
.masks
= self.compute_masks
(elements
, ids
)
778 result
.hashes
= self.compute_hashes
(elements
, ids
, result
.masks
)
782 # extract set of properties from mclass
783 private fun properties
(mclass
: MClass): Set[E
] do
784 var properties
= new HashSet[E
]
785 for mprop
in self.mmodule
.properties
(mclass
) do
786 if mprop
isa MPROP then properties
.add
(mprop
)
792 # Layout builder for vft using perfect hashing (PH)
794 super MPropertyHasher[MMethod]
795 redef type MPROP: MMethod
796 init(operator
: PHOperator, mmodule
: MModule) do super(operator
, mmodule
)
799 # Layout builder for attributes tables using perfect hashing (PH)
800 class MAttributeHasher
801 super MPropertyHasher[MAttribute]
802 redef type MPROP: MAttribute
803 init(operator
: PHOperator, mmodule
: MModule) do super(operator
, mmodule
)
806 # Layout builder for virtual types tables using perfect hashing (PH)
807 class MVirtualTypePropHasher
808 super MPropertyHasher[MVirtualTypeProp]
809 redef type MPROP: MVirtualTypeProp
810 init(operator
: PHOperator, mmodule
: MModule) do super(operator
, mmodule
)
813 # Layout builder for resolution tables using perfect hashing (PH)
814 class ResolutionHasher
815 super PerfectHasher[MClassType, MType]
816 super ResolutionLayoutBuilder
818 init(operator
: PHOperator) do self.operator
= operator
820 # Compute resolved types masks and hashes
821 redef fun build_layout
(elements
) do
822 var result
= new PHLayout[MClassType, MType]
823 var ids
= new HashMap[MType, Int]
825 for mclasstype
, mclasstypes
in elements
do
826 for element
in mclasstypes
do
827 if ids
.has_key
(element
) then continue
834 result
.masks
= self.compute_masks
(elements
, ids
)
835 result
.hashes
= self.compute_hashes
(elements
, ids
, result
.masks
)