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 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 # 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 class MPropertyBMizer[E
: MProperty]
183 super PropertyLayoutBuilder[E
]
187 init(mmodule
: MModule) do self.mmodule
= mmodule
189 redef fun build_layout
(elements
) do
190 var result
= new Layout[E
]
191 var ids
= new HashMap[E
, Int]
192 var lin
= new Array[MClass]
193 lin
.add_all
(elements
.keys
)
194 self.mmodule
.linearize_mclasses
(lin
)
196 for mproperty
in elements
[mclass
] do
197 if ids
.has_key
(mproperty
) then continue
198 ids
[mproperty
] = ids
.length
208 # Abstract Layout builder for typing table using coloration (CL)
209 abstract class TypingColorer[E
: Object]
210 super TypingLayoutBuilder[E
]
212 private var core
: Set[E
] = new HashSet[E
]
213 private var crown
: Set[E
] = new HashSet[E
]
214 private var border
: Set[E
] = new HashSet[E
]
215 private var coloration_result
: Map[E
, Int] = new HashMap[E
, Int]
217 private var mmodule
: MModule
218 private var poset_builder
: POSetBuilder[E
]
219 private var poset_cache
: nullable POSet[E
]
221 private init(mmodule
: MModule, poset_builder
: POSetBuilder[E
]) do
222 self.mmodule
= mmodule
223 self.poset_builder
= poset_builder
226 redef fun poset
do return poset_cache
228 # Compute the layout with coloring
229 redef fun build_layout
(elements
: Set[E
]): Layout[E
] do
230 poset_cache
= poset_builder
.build_poset
(elements
)
231 var result
= new Layout[E
]
232 result
.ids
= compute_ids
(elements
)
233 result
.pos
= colorize
(elements
)
237 private fun compute_ids
(elements
: Set[E
]): Map[E
, Int] do
238 var ids
= new HashMap[E
, Int]
239 for element
in reverse_linearize
(elements
) do
240 ids
[element
] = ids
.length
245 private fun colorize
(elements
: Set[E
]): Map[E
, Int] do
246 tag_elements
(elements
)
247 build_conflicts_graph
248 colorize_elements
(core
)
249 colorize_elements
(border
)
250 colorize_elements
(crown
)
251 return coloration_result
254 # Colorize a collection of elements
255 private fun colorize_elements
(elements
: Set[E
]) do
258 var lin
= reverse_linearize
(elements
)
259 for element
in lin
do
260 var color
= min_color
261 while not self.is_color_free
(element
, elements
, color
) do
264 coloration_result
[element
] = color
269 # Check if a related element to the element already use the color
270 private fun is_color_free
(element
: E
, elements
: Set[E
], color
: Int): Bool do
271 if conflicts_graph
.has_key
(element
) then
272 for st
in conflicts_graph
[element
] do
273 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
276 for st
in self.poset
[element
].greaters
do
277 if st
== element
then continue
278 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
283 # Tag elements as core, crown or border
284 private fun tag_elements
(elements
: Set[E
]) do
285 for element
in elements
do
286 # Check if sub elements are all in single inheritance
287 var all_subelements_si
= true
288 for subelem
in self.poset
[element
].smallers
do
289 if self.poset
[subelem
].direct_greaters
.length
> 1 then
290 all_subelements_si
= false
295 # Tag as core, crown or border
296 if self.poset
[element
].direct_greaters
.length
> 1 then
297 core
.add_all
(self.poset
[element
].greaters
)
298 if all_subelements_si
then
301 else if not all_subelements_si
then
302 core
.add_all
(self.poset
[element
].greaters
)
309 # Conflicts graph of elements hierarchy (two types are in conflict if they have common subelements)
310 private fun build_conflicts_graph
do
311 self.conflicts_graph
= new HashMap[E
, HashSet[E
]]
312 var core
= reverse_linearize
(self.core
)
314 for i
in self.linear_extension
(t
) do
315 if t
== i
then continue
317 var lin_i
= self.linear_extension
(i
)
319 for j
in self.linear_extension
(t
) do
320 if i
== j
or j
== t
then continue
321 var lin_j
= self.linear_extension
(j
)
323 var d_ij
= lin_i
- lin_j
324 var d_ji
= lin_j
- lin_i
327 if not conflicts_graph
.has_key
(ed1
) then conflicts_graph
[ed1
] = new HashSet[E
]
328 # add ed1 x ed2 to conflicts graph
329 for ed2
in d_ji
do conflicts_graph
[ed1
].add
(ed2
)
332 if not conflicts_graph
.has_key
(ed1
) then conflicts_graph
[ed1
] = new HashSet[E
]
333 # add ed1 x ed2 to conflicts graph
334 for ed2
in d_ji
do conflicts_graph
[ed1
].add
(ed2
)
341 private var conflicts_graph
: nullable HashMap[E
, Set[E
]]
343 # cache for linear_extensions
344 private var linear_extensions_cache
: Map[E
, Array[E
]] = new HashMap[E
, Array[E
]]
346 # Return a linear_extension of super_elements of the element
347 private fun linear_extension
(element
: E
): Array[E
] do
348 if not self.linear_extensions_cache
.has_key
(element
) then
349 var supers
= new HashSet[E
]
350 supers
.add_all
(self.poset
[element
].greaters
)
351 self.linear_extensions_cache
[element
] = self.linearize
(supers
)
353 return self.linear_extensions_cache
[element
]
356 private fun reverse_linearize
(elements
: Set[E
]): Array[E
] do
357 var lin
= new Array[E
]
358 lin
.add_all
(elements
)
362 private fun linearize
(elements
: Set[E
]): Array[E
] do return reverse_linearize
(elements
).reversed
365 # Layout builder for typing tables based on types using coloration (CL)
367 super TypingColorer[MType]
368 init(mmodule
: MModule) do super(mmodule
, new MTypePOSetBuilder(mmodule
))
371 # Layout builder for typing tables based on classes using coloration (CL)
373 super TypingColorer[MClass]
374 init(mmodule
: MModule) do super(mmodule
, new MClassPOSetBuilder(mmodule
))
377 # Abstract Layout builder for properties tables using coloration (CL)
378 class MPropertyColorer[E
: MProperty]
379 super PropertyLayoutBuilder[E
]
381 private var mmodule
: MModule
382 private var class_colorer
: MClassColorer
383 private var coloration_result
: Map[E
, Int] = new HashMap[E
, Int]
385 init(mmodule
: MModule, class_colorer
: MClassColorer) do
386 self.mmodule
= mmodule
387 self.class_colorer
= class_colorer
390 # Compute mclasses ids and position using BM
391 redef fun build_layout
(elements
: Map[MClass, Set[E
]]): Layout[E
] do
392 var result
= new Layout[E
]
393 result
.pos
= self.colorize
(elements
)
397 private fun colorize
(elements
: Map[MClass, Set[E
]]): Map[E
, Int] do
398 self.colorize_core
(elements
)
399 self.colorize_crown
(elements
)
400 return self.coloration_result
403 # Colorize properties of the core hierarchy
404 private fun colorize_core
(elements
: Map[MClass, Set[E
]]) do
406 for mclass
in self.class_colorer
.core
do
407 var color
= min_color
408 # check last color used by parents
409 color
= max_color
(color
, mclass
.in_hierarchy
(mmodule
).direct_greaters
, elements
)
410 # check max color used in conflicts
411 if self.class_colorer
.conflicts_graph
.has_key
(mclass
) then
412 color
= max_color
(color
, self.class_colorer
.conflicts_graph
[mclass
], elements
)
414 colorize_elements
(elements
[mclass
], color
)
418 # Colorize properties of the crown hierarchy
419 private fun colorize_crown
(elements
: Map[MClass, Set[E
]]) do
420 for mclass
in self.class_colorer
.crown
do
421 var parents
= new HashSet[MClass]
422 if mmodule
.flatten_mclass_hierarchy
.has
(mclass
) then
423 parents
.add_all
(mclass
.in_hierarchy
(mmodule
).direct_greaters
)
425 colorize_elements
(elements
[mclass
], max_color
(0, parents
, elements
))
429 # Colorize a collection of mproperties given a starting color
430 private fun colorize_elements
(elements
: Collection[E
], start_color
: Int) do
431 for element
in elements
do
432 if self.coloration_result
.has_key
(element
) then continue
433 self.coloration_result
[element
] = start_color
438 private fun max_color
(min_color
: Int, mclasses
: Collection[MClass], elements
: Map[MClass, Set[E
]]): Int do
439 var max_color
= min_color
441 for mclass
in mclasses
do
442 for mproperty
in elements
[mclass
] do
443 var color
= min_color
444 if self.coloration_result
.has_key
(mproperty
) then
445 color
= self.coloration_result
[mproperty
]
446 if color
>= max_color
then max_color
= color
+ 1
454 # Layout builder for resolution tables using coloration (CL)
455 class ResolutionColorer
456 super ResolutionLayoutBuilder
458 private var coloration_result
: Map[MType, Int] = new HashMap[MType, Int]
462 # Compute resolved types colors
463 redef fun build_layout
(elements
) do
464 self.build_conflicts_graph
(elements
)
465 var result
= new Layout[MType]
466 result
.ids
= self.compute_ids
(elements
)
467 result
.pos
= self.colorize_elements
(elements
)
471 private fun compute_ids
(elements
: Map[MClassType, Set[MType]]): Map[MType, Int] do
472 var ids
= new HashMap[MType, Int]
474 for mclasstype
, mclasstypes
in elements
do
475 for element
in mclasstypes
do
476 if ids
.has_key
(element
) then continue
484 # Colorize a collection of elements
485 private fun colorize_elements
(elements
: Map[MClassType, Set[MType]]): Map[MType, Int] do
487 for mclasstype
, mclasstypes
in elements
do
488 for element
in mclasstypes
do
489 if self.coloration_result
.has_key
(element
) then continue
490 var color
= min_color
491 while not self.is_color_free
(element
, color
) do
494 coloration_result
[element
] = color
498 return self.coloration_result
501 # Check if a related element to the element already use the color
502 private fun is_color_free
(element
: MType, color
: Int): Bool do
503 if conflicts_graph
.has_key
(element
) then
504 for st
in conflicts_graph
[element
] do
505 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
511 # look for unanchored types generated by the same type
512 private fun build_conflicts_graph
(elements
: Map[MClassType, Set[MType]]) do
513 for mclasstype
, mtypes
in elements
do
514 for mtype
in mtypes
do
515 for otype
in mtypes
do
516 if otype
== mtype
then continue
517 self.add_conflict
(mtype
, otype
)
523 private var conflicts_graph
: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
525 private fun add_conflict
(mtype
: MType, otype
: MType) do
526 if mtype
== otype
then return
527 if not self.conflicts_graph
.has_key
(mtype
) then self.conflicts_graph
[mtype
] = new HashSet[MType]
528 self.conflicts_graph
[mtype
].add
(otype
)
529 if not self.conflicts_graph
.has_key
(otype
) then self.conflicts_graph
[otype
] = new HashSet[MType]
530 self.conflicts_graph
[otype
].add
(mtype
)
534 # Perfect Hashing (PH)
536 # U = type of elements to hash
537 private class PerfectHasher[T
: Object, U
: Object]
539 var operator
: PHOperator
543 # Compute mask for each holders
544 fun compute_masks
(conflicts
: Map[T
, Set[U
]], ids
: Map[U
, Int]): Map[T
, Int] do
545 var masks
= new HashMap[T
, Int]
546 for mclasstype
, mtypes
in conflicts
do
547 masks
[mclasstype
] = compute_mask
(mtypes
, ids
)
552 private fun compute_mask
(mtypes
: Set[U
], ids
: Map[U
, Int]): Int do
555 var used
= new List[Int]
556 for mtype
in mtypes
do
557 var res
= operator
.op
(mask
, ids
[mtype
])
558 if used
.has
(res
) then
564 if used
.length
== mtypes
.length
then break
570 # Compute hash for each element in each holder
571 fun compute_hashes
(elements
: Map[T
, Set[U
]], ids
: Map[U
, Int], masks
: Map[T
, Int]): Map[T
, Map[U
, Int]] do
572 var hashes
= new HashMap[T
, Map[U
, Int]]
573 for mclasstype
, mtypes
in elements
do
574 var mask
= masks
[mclasstype
]
575 var inhashes
= new HashMap[U
, Int]
576 for mtype
in mtypes
do
577 inhashes
[mtype
] = operator
.op
(mask
, ids
[mtype
])
579 hashes
[mclasstype
] = inhashes
585 # Abstract operator used for perfect hashing
586 abstract class PHOperator
587 # hash `id` using `mask`
588 fun op
(mask
: Int, id
:Int): Int is abstract
591 # Hashing using modulo (MOD) operator
596 redef fun op
(mask
, id
) do return mask
% id
599 # Hashing using binary and (AND) operator
604 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
607 # Layout builder for typing tables using perfect hashing (PH)
608 class TypingHasher[E
: Object]
609 super PerfectHasher[E
, E
]
610 super TypingLayoutBuilder[E
]
612 private var mmodule
: MModule
613 private var poset_builder
: POSetBuilder[E
]
614 private var poset_cache
: nullable POSet[E
]
616 private init(mmodule
: MModule, poset_builder
: POSetBuilder[E
], operator
: PHOperator) do
617 self.operator
= operator
618 self.mmodule
= mmodule
619 self.poset_builder
= poset_builder
622 redef fun build_layout
(elements
: Set[E
]): PHLayout[E
, E
] do
623 poset_cache
= poset_builder
.build_poset
(elements
)
624 var result
= new PHLayout[E
, E
]
625 var conflicts
= self.build_conflicts
(elements
)
626 result
.ids
= self.compute_ids
627 result
.masks
= self.compute_masks
(conflicts
, result
.ids
)
628 result
.hashes
= self.compute_hashes
(conflicts
, result
.ids
, result
.masks
)
632 # Ids start from 1 instead of 0
633 private fun compute_ids
: Map[E
, Int] do
634 var ids
= new HashMap[E
, Int]
638 ids
[e
] = ids
.length
+ 1
643 private fun build_conflicts
(elements
: Set[E
]): Map[E
, Set[E
]] do
644 var conflicts
= new HashMap[E
, Set[E
]]
646 var supers
= new HashSet[E
]
647 supers
.add_all
(self.poset
[e
].greaters
)
649 conflicts
[e
] = supers
655 # Layout builder for typing tables with types using perfect hashing (PH)
657 super TypingHasher[MType]
658 init(operator
: PHOperator, mmodule
: MModule) do super(mmodule
, new MTypePOSetBuilder(mmodule
), operator
)
661 # Layout builder for typing tables with classes using perfect hashing (PH)
663 super TypingHasher[MClass]
664 init(operator
: PHOperator, mmodule
: MModule) do super(mmodule
, new MClassPOSetBuilder(mmodule
), operator
)
667 # Abstract layout builder for properties tables using perfect hashing (PH)
668 class MPropertyHasher[E
: MProperty]
669 super PerfectHasher[MClass, E
]
670 super PropertyLayoutBuilder[E
]
674 init(operator
: PHOperator, mmodule
: MModule) do
675 self.operator
= operator
676 self.mmodule
= mmodule
679 fun build_poset
(mclasses
: Set[MClass]): POSet[MClass] do
680 var poset
= new POSet[MClass]
684 if e
== o
or not mmodule
.flatten_mclass_hierarchy
.has
(e
) then continue
685 if e
.in_hierarchy
(mmodule
) < o
then poset
.add_edge
(e
, o
)
691 redef fun build_layout
(elements
) do
692 var result
= new PHLayout[MClass, E
]
693 var ids
= new HashMap[E
, Int]
694 var mclasses
= new HashSet[MClass]
695 mclasses
.add_all
(elements
.keys
)
696 var poset
= build_poset
(mclasses
)
699 for mclass
in lin
.reversed
do
700 for mproperty
in elements
[mclass
] do
701 if ids
.has_key
(mproperty
) then continue
702 ids
[mproperty
] = ids
.length
+ 1
707 result
.masks
= self.compute_masks
(elements
, ids
)
708 result
.hashes
= self.compute_hashes
(elements
, ids
, result
.masks
)
713 # Layout builder for resolution tables using perfect hashing (PH)
714 class ResolutionHasher
715 super PerfectHasher[MClassType, MType]
716 super ResolutionLayoutBuilder
718 init(operator
: PHOperator) do self.operator
= operator
720 # Compute resolved types masks and hashes
721 redef fun build_layout
(elements
) do
722 var result
= new PHLayout[MClassType, MType]
723 var ids
= new HashMap[MType, Int]
725 for mclasstype
, mclasstypes
in elements
do
726 for element
in mclasstypes
do
727 if ids
.has_key
(element
) then continue
734 result
.masks
= self.compute_masks
(elements
, ids
)
735 result
.hashes
= self.compute_hashes
(elements
, ids
, result
.masks
)