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
: PropertyLayoutElement]
64 # Build table layout for attributes, methods and virtual types
65 # elements: the associative map between classes and properties to use in table layout
66 fun build_layout
(elements
: Map[MClass, Set[E
]]): Layout[E
] is abstract
69 # Used to create a common ancestors to MProperty and MPropDef
70 # Required for polymorphic calls
71 # FIXME: there should be a better way
72 interface PropertyLayoutElement end
75 super PropertyLayoutElement
79 super PropertyLayoutElement
82 # For resolution tables (generics)
83 interface ResolutionLayoutBuilder
84 # Build resolution table layout
85 # elements: association between classes and resolved types
86 fun build_layout
(elements
: Map[MClassType, Set[MType]]): Layout[MType] is abstract
91 # A POSet builder build a poset for a set of MType or MClass
92 # the resulting poset is used by the layout builders
93 private abstract class POSetBuilder[E
: Object]
94 private var mmodule
: MModule
95 init(mmodule
: MModule) do self.mmodule
= mmodule
96 # Build the poset from `elements`
97 private fun build_poset
(elements
: Set[E
]): POSet[E
] is abstract
100 # A TypingLayoutBuilder used for MType based typing
101 # such as in separate compilers
102 private class MTypePOSetBuilder
103 super POSetBuilder[MType]
104 redef fun build_poset
(elements
) do
105 var poset
= new POSet[MType]
109 if e
== o
then continue
110 if e
.is_subtype
(mmodule
, null, o
) then
119 # A TypingLayoutBuilder used for MClass based typing
120 # such as in erased compilers or used in property coloring
121 private class MClassPOSetBuilder
122 super POSetBuilder[MClass]
123 redef fun build_poset
(elements
) do return mmodule
.flatten_mclass_hierarchy
128 # Abstract layout builder for resolution tables using Binary Matrix (BM)
129 abstract class TypingBMizer[E
: Object]
130 super TypingLayoutBuilder[E
]
132 private var mmodule
: MModule
133 private var poset_builder
: POSetBuilder[E
]
134 private var poset_cache
: nullable POSet[E
]
136 private init(mmodule
: MModule, poset_builder
: POSetBuilder[E
]) do
137 self.mmodule
= mmodule
138 self.poset_builder
= poset_builder
141 redef fun poset
do return poset_cache
143 # Compute mtypes ids and position using BM
144 redef fun build_layout
(elements
: Set[E
]): Layout[E
] do
145 var result
= new Layout[E
]
146 var ids
= new HashMap[E
, Int]
147 poset_cache
= poset_builder
.build_poset
(elements
)
150 for element
in lin
do
151 ids
[element
] = ids
.length
159 # Layout builder for typing tables based on classes using Binary Matrix (BM)
161 super TypingBMizer[MType]
162 init(mmodule
: MModule) do super(mmodule
, new MTypePOSetBuilder(mmodule
))
165 # Layout builder for typing tables based on types using Binary Matrix (BM)
167 super TypingBMizer[MClass]
168 init(mmodule
: MModule) do super(mmodule
, new MClassPOSetBuilder(mmodule
))
171 # Layout builder for resolution tables using Binary Matrix (BM)
172 class ResolutionBMizer
173 super ResolutionLayoutBuilder
177 redef fun build_layout
(elements
) do
178 var result
= new Layout[MType]
179 var ids
= new HashMap[MType, Int]
181 for mclasstype
, mclasstypes
in elements
do
182 for element
in mclasstypes
do
183 if ids
.has_key
(element
) then continue
194 # Abstract Layout builder for mproperties using Binary Matrix (BM)
195 class MPropertyBMizer[E
: PropertyLayoutElement]
196 super PropertyLayoutBuilder[E
]
200 init(mmodule
: MModule) do self.mmodule
= mmodule
202 redef fun build_layout
(elements
) do
203 var result
= new Layout[E
]
204 var ids
= new HashMap[E
, Int]
205 var lin
= new Array[MClass]
206 lin
.add_all
(elements
.keys
)
207 self.mmodule
.linearize_mclasses
(lin
)
209 for mproperty
in elements
[mclass
] do
210 if ids
.has_key
(mproperty
) then continue
211 ids
[mproperty
] = ids
.length
221 # Abstract Layout builder for typing table using coloration (CL)
222 abstract class TypingColorer[E
: Object]
223 super TypingLayoutBuilder[E
]
225 private var core
: Set[E
] = new HashSet[E
]
226 private var crown
: Set[E
] = new HashSet[E
]
227 private var border
: Set[E
] = new HashSet[E
]
228 private var coloration_result
: Map[E
, Int] = new HashMap[E
, Int]
230 private var mmodule
: MModule
231 private var poset_builder
: POSetBuilder[E
]
232 private var poset_cache
: nullable POSet[E
]
234 private init(mmodule
: MModule, poset_builder
: POSetBuilder[E
]) do
235 self.mmodule
= mmodule
236 self.poset_builder
= poset_builder
239 redef fun poset
do return poset_cache
241 # Compute the layout with coloring
242 redef fun build_layout
(elements
: Set[E
]): Layout[E
] do
243 poset_cache
= poset_builder
.build_poset
(elements
)
244 var result
= new Layout[E
]
245 result
.ids
= compute_ids
(elements
)
246 result
.pos
= colorize
(elements
)
250 private fun compute_ids
(elements
: Set[E
]): Map[E
, Int] do
251 var ids
= new HashMap[E
, Int]
252 for element
in reverse_linearize
(elements
) do
253 ids
[element
] = ids
.length
258 private fun colorize
(elements
: Set[E
]): Map[E
, Int] do
259 tag_elements
(elements
)
260 build_conflicts_graph
261 colorize_elements
(core
)
262 colorize_elements
(border
)
263 colorize_elements
(crown
)
264 return coloration_result
267 # Colorize a collection of elements
268 private fun colorize_elements
(elements
: Set[E
]) do
271 var lin
= reverse_linearize
(elements
)
272 for element
in lin
do
273 var color
= min_color
274 while not self.is_color_free
(element
, elements
, color
) do
277 coloration_result
[element
] = color
282 # Check if a related element to the element already use the color
283 private fun is_color_free
(element
: E
, elements
: Set[E
], color
: Int): Bool do
284 if conflicts_graph
.has_key
(element
) then
285 for st
in conflicts_graph
[element
] do
286 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
289 for st
in self.poset
[element
].greaters
do
290 if st
== element
then continue
291 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
296 # Tag elements as core, crown or border
297 private fun tag_elements
(elements
: Set[E
]) do
298 for element
in elements
do
299 # Check if sub elements are all in single inheritance
300 var all_subelements_si
= true
301 for subelem
in self.poset
[element
].smallers
do
302 if self.poset
[subelem
].direct_greaters
.length
> 1 then
303 all_subelements_si
= false
308 # Tag as core, crown or border
309 if self.poset
[element
].direct_greaters
.length
> 1 then
310 core
.add_all
(self.poset
[element
].greaters
)
311 if all_subelements_si
then
314 else if not all_subelements_si
then
315 core
.add_all
(self.poset
[element
].greaters
)
322 # Conflicts graph of elements hierarchy (two types are in conflict if they have common subelements)
323 private fun build_conflicts_graph
do
324 self.conflicts_graph
= new HashMap[E
, HashSet[E
]]
325 var core
= reverse_linearize
(self.core
)
327 for i
in self.linear_extension
(t
) do
328 if t
== i
then continue
330 var lin_i
= self.linear_extension
(i
)
332 for j
in self.linear_extension
(t
) do
333 if i
== j
or j
== t
then continue
334 var lin_j
= self.linear_extension
(j
)
336 var d_ij
= lin_i
- lin_j
337 var d_ji
= lin_j
- lin_i
340 if not conflicts_graph
.has_key
(ed1
) then conflicts_graph
[ed1
] = new HashSet[E
]
341 # add ed1 x ed2 to conflicts graph
342 for ed2
in d_ji
do conflicts_graph
[ed1
].add
(ed2
)
345 if not conflicts_graph
.has_key
(ed1
) then conflicts_graph
[ed1
] = new HashSet[E
]
346 # add ed1 x ed2 to conflicts graph
347 for ed2
in d_ji
do conflicts_graph
[ed1
].add
(ed2
)
354 private var conflicts_graph
: nullable HashMap[E
, Set[E
]]
356 # cache for linear_extensions
357 private var linear_extensions_cache
: Map[E
, Array[E
]] = new HashMap[E
, Array[E
]]
359 # Return a linear_extension of super_elements of the element
360 private fun linear_extension
(element
: E
): Array[E
] do
361 if not self.linear_extensions_cache
.has_key
(element
) then
362 var supers
= new HashSet[E
]
363 supers
.add_all
(self.poset
[element
].greaters
)
364 self.linear_extensions_cache
[element
] = self.linearize
(supers
)
366 return self.linear_extensions_cache
[element
]
369 private fun reverse_linearize
(elements
: Set[E
]): Array[E
] do
370 var lin
= new Array[E
]
371 lin
.add_all
(elements
)
375 private fun linearize
(elements
: Set[E
]): Array[E
] do return reverse_linearize
(elements
).reversed
378 # Layout builder for typing tables based on types using coloration (CL)
380 super TypingColorer[MType]
381 init(mmodule
: MModule) do super(mmodule
, new MTypePOSetBuilder(mmodule
))
384 # Layout builder for typing tables based on classes using coloration (CL)
386 super TypingColorer[MClass]
387 init(mmodule
: MModule) do super(mmodule
, new MClassPOSetBuilder(mmodule
))
390 # Abstract Layout builder for properties tables using coloration (CL)
391 class MPropertyColorer[E
: PropertyLayoutElement]
392 super PropertyLayoutBuilder[E
]
394 private var mmodule
: MModule
395 private var class_colorer
: MClassColorer
396 private var coloration_result
: Map[E
, Int] = new HashMap[E
, Int]
398 init(mmodule
: MModule, class_colorer
: MClassColorer) do
399 self.mmodule
= mmodule
400 self.class_colorer
= class_colorer
403 # Compute mclasses ids and position using BM
404 redef fun build_layout
(elements
: Map[MClass, Set[E
]]): Layout[E
] do
405 var result
= new Layout[E
]
406 result
.pos
= self.colorize
(elements
)
410 private fun colorize
(elements
: Map[MClass, Set[E
]]): Map[E
, Int] do
411 self.colorize_core
(elements
)
412 self.colorize_crown
(elements
)
413 return self.coloration_result
416 # Colorize properties of the core hierarchy
417 private fun colorize_core
(elements
: Map[MClass, Set[E
]]) do
419 for mclass
in self.class_colorer
.core
do
420 var color
= min_color
421 # check last color used by parents
422 color
= max_color
(color
, mclass
.in_hierarchy
(mmodule
).direct_greaters
, elements
)
423 # check max color used in conflicts
424 if self.class_colorer
.conflicts_graph
.has_key
(mclass
) then
425 color
= max_color
(color
, self.class_colorer
.conflicts_graph
[mclass
], elements
)
427 colorize_elements
(elements
[mclass
], color
)
431 # Colorize properties of the crown hierarchy
432 private fun colorize_crown
(elements
: Map[MClass, Set[E
]]) do
433 for mclass
in self.class_colorer
.crown
do
434 var parents
= new HashSet[MClass]
435 if mmodule
.flatten_mclass_hierarchy
.has
(mclass
) then
436 parents
.add_all
(mclass
.in_hierarchy
(mmodule
).direct_greaters
)
438 colorize_elements
(elements
[mclass
], max_color
(0, parents
, elements
))
442 # Colorize a collection of mproperties given a starting color
443 private fun colorize_elements
(elements
: Collection[E
], start_color
: Int) do
444 for element
in elements
do
445 if self.coloration_result
.has_key
(element
) then continue
446 self.coloration_result
[element
] = start_color
451 private fun max_color
(min_color
: Int, mclasses
: Collection[MClass], elements
: Map[MClass, Set[E
]]): Int do
452 var max_color
= min_color
454 for mclass
in mclasses
do
455 for mproperty
in elements
[mclass
] do
456 var color
= min_color
457 if self.coloration_result
.has_key
(mproperty
) then
458 color
= self.coloration_result
[mproperty
]
459 if color
>= max_color
then max_color
= color
+ 1
467 # Layout builder for resolution tables using coloration (CL)
468 class ResolutionColorer
469 super ResolutionLayoutBuilder
471 private var coloration_result
: Map[MType, Int] = new HashMap[MType, Int]
475 # Compute resolved types colors
476 redef fun build_layout
(elements
) do
477 self.build_conflicts_graph
(elements
)
478 var result
= new Layout[MType]
479 result
.ids
= self.compute_ids
(elements
)
480 result
.pos
= self.colorize_elements
(elements
)
484 private fun compute_ids
(elements
: Map[MClassType, Set[MType]]): Map[MType, Int] do
485 var ids
= new HashMap[MType, Int]
487 for mclasstype
, mclasstypes
in elements
do
488 for element
in mclasstypes
do
489 if ids
.has_key
(element
) then continue
497 # Colorize a collection of elements
498 private fun colorize_elements
(elements
: Map[MClassType, Set[MType]]): Map[MType, Int] do
500 for mclasstype
, mclasstypes
in elements
do
501 for element
in mclasstypes
do
502 if self.coloration_result
.has_key
(element
) then continue
503 var color
= min_color
504 while not self.is_color_free
(element
, color
) do
507 coloration_result
[element
] = color
511 return self.coloration_result
514 # Check if a related element to the element already use the color
515 private fun is_color_free
(element
: MType, color
: Int): Bool do
516 if conflicts_graph
.has_key
(element
) then
517 for st
in conflicts_graph
[element
] do
518 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
524 # look for unanchored types generated by the same type
525 private fun build_conflicts_graph
(elements
: Map[MClassType, Set[MType]]) do
526 for mclasstype
, mtypes
in elements
do
527 for mtype
in mtypes
do
528 for otype
in mtypes
do
529 if otype
== mtype
then continue
530 self.add_conflict
(mtype
, otype
)
536 private var conflicts_graph
: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
538 private fun add_conflict
(mtype
: MType, otype
: MType) do
539 if mtype
== otype
then return
540 if not self.conflicts_graph
.has_key
(mtype
) then self.conflicts_graph
[mtype
] = new HashSet[MType]
541 self.conflicts_graph
[mtype
].add
(otype
)
542 if not self.conflicts_graph
.has_key
(otype
) then self.conflicts_graph
[otype
] = new HashSet[MType]
543 self.conflicts_graph
[otype
].add
(mtype
)
547 # Perfect Hashing (PH)
549 # U = type of elements to hash
550 private class PerfectHasher[T
: Object, U
: Object]
552 var operator
: PHOperator
556 # Compute mask for each holders
557 fun compute_masks
(conflicts
: Map[T
, Set[U
]], ids
: Map[U
, Int]): Map[T
, Int] do
558 var masks
= new HashMap[T
, Int]
559 for mclasstype
, mtypes
in conflicts
do
560 masks
[mclasstype
] = compute_mask
(mtypes
, ids
)
565 private fun compute_mask
(mtypes
: Set[U
], ids
: Map[U
, Int]): Int do
568 var used
= new List[Int]
569 for mtype
in mtypes
do
570 var res
= operator
.op
(mask
, ids
[mtype
])
571 if used
.has
(res
) then
577 if used
.length
== mtypes
.length
then break
583 # Compute hash for each element in each holder
584 fun compute_hashes
(elements
: Map[T
, Set[U
]], ids
: Map[U
, Int], masks
: Map[T
, Int]): Map[T
, Map[U
, Int]] do
585 var hashes
= new HashMap[T
, Map[U
, Int]]
586 for mclasstype
, mtypes
in elements
do
587 var mask
= masks
[mclasstype
]
588 var inhashes
= new HashMap[U
, Int]
589 for mtype
in mtypes
do
590 inhashes
[mtype
] = operator
.op
(mask
, ids
[mtype
])
592 hashes
[mclasstype
] = inhashes
598 # Abstract operator used for perfect hashing
599 abstract class PHOperator
600 # hash `id` using `mask`
601 fun op
(mask
: Int, id
:Int): Int is abstract
604 # Hashing using modulo (MOD) operator
609 redef fun op
(mask
, id
) do return mask
% id
612 # Hashing using binary and (AND) operator
617 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
620 # Layout builder for typing tables using perfect hashing (PH)
621 class TypingHasher[E
: Object]
622 super PerfectHasher[E
, E
]
623 super TypingLayoutBuilder[E
]
625 private var mmodule
: MModule
626 private var poset_builder
: POSetBuilder[E
]
627 private var poset_cache
: nullable POSet[E
]
629 private init(mmodule
: MModule, poset_builder
: POSetBuilder[E
], operator
: PHOperator) do
630 self.operator
= operator
631 self.mmodule
= mmodule
632 self.poset_builder
= poset_builder
635 redef fun build_layout
(elements
: Set[E
]): PHLayout[E
, E
] do
636 poset_cache
= poset_builder
.build_poset
(elements
)
637 var result
= new PHLayout[E
, E
]
638 var conflicts
= self.build_conflicts
(elements
)
639 result
.ids
= self.compute_ids
640 result
.masks
= self.compute_masks
(conflicts
, result
.ids
)
641 result
.hashes
= self.compute_hashes
(conflicts
, result
.ids
, result
.masks
)
645 # Ids start from 1 instead of 0
646 private fun compute_ids
: Map[E
, Int] do
647 var ids
= new HashMap[E
, Int]
651 ids
[e
] = ids
.length
+ 1
656 private fun build_conflicts
(elements
: Set[E
]): Map[E
, Set[E
]] do
657 var conflicts
= new HashMap[E
, Set[E
]]
659 var supers
= new HashSet[E
]
660 supers
.add_all
(self.poset
[e
].greaters
)
662 conflicts
[e
] = supers
668 # Layout builder for typing tables with types using perfect hashing (PH)
670 super TypingHasher[MType]
671 init(operator
: PHOperator, mmodule
: MModule) do super(mmodule
, new MTypePOSetBuilder(mmodule
), operator
)
674 # Layout builder for typing tables with classes using perfect hashing (PH)
676 super TypingHasher[MClass]
677 init(operator
: PHOperator, mmodule
: MModule) do super(mmodule
, new MClassPOSetBuilder(mmodule
), operator
)
680 # Abstract layout builder for properties tables using perfect hashing (PH)
681 class MPropertyHasher[E
: PropertyLayoutElement]
682 super PerfectHasher[MClass, E
]
683 super PropertyLayoutBuilder[E
]
687 init(operator
: PHOperator, mmodule
: MModule) do
688 self.operator
= operator
689 self.mmodule
= mmodule
692 fun build_poset
(mclasses
: Set[MClass]): POSet[MClass] do
693 var poset
= new POSet[MClass]
697 if e
== o
or not mmodule
.flatten_mclass_hierarchy
.has
(e
) then continue
698 if e
.in_hierarchy
(mmodule
) < o
then poset
.add_edge
(e
, o
)
704 redef fun build_layout
(elements
) do
705 var result
= new PHLayout[MClass, E
]
706 var ids
= new HashMap[E
, Int]
707 var mclasses
= new HashSet[MClass]
708 mclasses
.add_all
(elements
.keys
)
709 var poset
= build_poset
(mclasses
)
712 for mclass
in lin
.reversed
do
713 for mproperty
in elements
[mclass
] do
714 if ids
.has_key
(mproperty
) then continue
715 ids
[mproperty
] = ids
.length
+ 1
720 result
.masks
= self.compute_masks
(elements
, ids
)
721 result
.hashes
= self.compute_hashes
(elements
, ids
, result
.masks
)
726 # Layout builder for resolution tables using perfect hashing (PH)
727 class ResolutionHasher
728 super PerfectHasher[MClassType, MType]
729 super ResolutionLayoutBuilder
731 init(operator
: PHOperator) do self.operator
= operator
733 # Compute resolved types masks and hashes
734 redef fun build_layout
(elements
) do
735 var result
= new PHLayout[MClassType, MType]
736 var ids
= new HashMap[MType, Int]
738 for mclasstype
, mclasstypes
in elements
do
739 for element
in mclasstypes
do
740 if ids
.has_key
(element
) then continue
747 result
.masks
= self.compute_masks
(elements
, ids
)
748 result
.hashes
= self.compute_hashes
(elements
, ids
, result
.masks
)