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 module layout_builders
18 import abstract_compiler
22 class Layout[E
: Object]
24 var ids
: Map[E
, Int] = new HashMap[E
, Int]
25 # Fixed positions of each element in all tables
26 var pos
: Map[E
, Int] = new HashMap[E
, Int]
29 class PHLayout[HOLDER: Object, E
: Object]
31 # Masks used by hash function
32 var masks
: Map[HOLDER, Int] = new HashMap[HOLDER, Int]
33 # Positions of each element for each tables
34 var hashes
: Map[HOLDER, Map[E
, Int]] = new HashMap[HOLDER, Map[E
, Int]]
37 class PropertyLayout[E
: Object]
38 # Fixed positions of each element in all tables
39 var pos
: Map[E
, Int] = new HashMap[E
, Int]
44 interface TypingLayoutBuilder[E
: Object]
45 # Build typing table layout
46 fun build_layout
(elements
: Set[E
]): Layout[E
] is abstract
49 interface PropertyLayoutBuilder[E
: MProperty]
50 # Build table layout for attributes, methods and virtual types
51 fun build_layout
(elements
: Set[MClass]): Layout[E
] is abstract
54 # Layout builder for MProperty using Coloring (CL)
55 class CLPropertyLayoutBuilder[E
: MProperty]
56 super PropertyLayoutBuilder[E
]
58 private var colorer
: MPropertyColorer[E
]
60 init(colorer
: MPropertyColorer[E
]) do
61 self.colorer
= colorer
64 # Compute mclasses ids and position using BM
65 redef fun build_layout
(mclasses
) do
66 return self.colorer
.build_layout
(mclasses
)
70 # Layout builder for MProperty using Perfect Hashing (PH)
71 # TODO implement this class without sublcassing CL builder
72 class PHPropertyLayoutBuilder[E
: MProperty]
73 super CLPropertyLayoutBuilder[E
]
76 interface ResolutionLayoutBuilder
77 # Build resolution table layout
78 fun build_layout
(elements
: Map[MClassType, Set[MType]]): Layout[MType] is abstract
83 abstract class TypingBMizer[E
: Object]
84 super TypingLayoutBuilder[E
]
88 init(mmodule
: MModule) do
89 self.mmodule
= mmodule
92 # Compute mtypes ids and position using BM
93 redef fun build_layout
(elements
: Set[E
]): Layout[E
] do
94 var result
= new Layout[E
]
95 var ids
= new HashMap[E
, Int]
96 var lin
= self.reverse_linearize
(elements
)
98 ids
[element
] = ids
.length
105 private fun reverse_linearize
(elements
: Set[E
]): Array[E
] is abstract
109 super TypingBMizer[MType]
111 init(mmodule
: MModule) do super(mmodule
)
113 redef fun reverse_linearize
(elements
) do
114 return self.mmodule
.reverse_linearize_mtypes
(elements
)
119 super TypingBMizer[MClass]
121 init(mmodule
: MModule) do super(mmodule
)
123 redef fun reverse_linearize
(elements
) do
124 return self.mmodule
.reverse_linearize_mclasses
(elements
)
128 # Layout builder for resolution tables using Binary Matrix (BM)
129 class ResolutionBMizer
130 super ResolutionLayoutBuilder
134 redef fun build_layout
(elements
) do
135 var result
= new Layout[MType]
136 var ids
= new HashMap[MType, Int]
138 for mclasstype
, mclasstypes
in elements
do
139 for element
in mclasstypes
do
140 if ids
.has_key
(element
) then continue
153 abstract class TypingColorer[E
: Object]
154 super TypingLayoutBuilder[E
]
156 private var core
: Set[E
] = new HashSet[E
]
157 private var crown
: Set[E
] = new HashSet[E
]
158 private var border
: Set[E
] = new HashSet[E
]
160 private var coloration_result
: Map[E
, Int] = new HashMap[E
, Int]
164 # Compute the layout with coloring
165 redef fun build_layout
(elements
: Set[E
]): Layout[E
] do
166 var result
= new Layout[E
]
167 result
.ids
= compute_ids
(elements
)
168 result
.pos
= colorize
(elements
)
172 private fun compute_ids
(elements
: Set[E
]): Map[E
, Int] do
173 var ids
= new HashMap[E
, Int]
174 var lin
= reverse_linearize
(elements
)
175 for element
in lin
do
176 ids
[element
] = ids
.length
181 private fun colorize
(elements
: Set[E
]): Map[E
, Int] do
182 tag_elements
(elements
)
183 build_conflicts_graph
(elements
)
184 colorize_elements
(core
)
185 colorize_elements
(border
)
186 colorize_elements
(crown
)
187 return coloration_result
190 # Colorize a collection of elements
191 private fun colorize_elements
(elements
: Set[E
]) do
194 var lin
= reverse_linearize
(elements
)
195 for element
in lin
do
196 var color
= min_color
197 while not self.is_color_free
(element
, elements
, color
) do
200 coloration_result
[element
] = color
205 # Check if a related element to the element already use the color
206 private fun is_color_free
(element
: E
, elements
: Set[E
], color
: Int): Bool do
207 if conflicts_graph
.has_key
(element
) then
208 for st
in conflicts_graph
[element
] do
209 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
212 for st
in self.super_elements
(element
, elements
) do
213 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
218 # Tag elements as core, crown or border
219 private fun tag_elements
(elements
: Set[E
]) do
220 for element
in elements
do
221 # Check if sub elements are all in single inheritance
222 var all_subelements_si
= true
223 for subelem
in self.sub_elements
(element
, elements
) do
224 if self.is_element_mi
(subelem
, elements
) then
225 all_subelements_si
= false
230 # Tag as core, crown or border
231 if self.is_element_mi
(element
, elements
) then
232 core
.add_all
(self.super_elements
(element
, elements
))
234 if all_subelements_si
then
237 else if not all_subelements_si
then
238 core
.add_all
(self.super_elements
(element
, elements
))
246 # Conflicts graph of elements hierarchy (two types are in conflict if they have common subelements)
247 private fun build_conflicts_graph
(elements
: Set[E
]) do
248 self.conflicts_graph
= new HashMap[E
, HashSet[E
]]
249 var core
= reverse_linearize
(self.core
)
251 for i
in self.linear_extension
(t
, elements
) do
252 if t
== i
then continue
254 var lin_i
= self.linear_extension
(i
, elements
)
256 for j
in self.linear_extension
(t
, elements
) do
257 if i
== j
or j
== t
then continue
258 var lin_j
= self.linear_extension
(j
, elements
)
260 var d_ij
= lin_i
- lin_j
261 var d_ji
= lin_j
- lin_i
264 if not conflicts_graph
.has_key
(ed1
) then conflicts_graph
[ed1
] = new HashSet[E
]
265 # add ed1 x ed2 to conflicts graph
266 for ed2
in d_ji
do conflicts_graph
[ed1
].add
(ed2
)
269 if not conflicts_graph
.has_key
(ed1
) then conflicts_graph
[ed1
] = new HashSet[E
]
270 # add ed1 x ed2 to conflicts graph
271 for ed2
in d_ji
do conflicts_graph
[ed1
].add
(ed2
)
278 private var conflicts_graph
: nullable HashMap[E
, Set[E
]]
280 # cache for linear_extensions
281 private var linear_extensions_cache
: Map[E
, Array[E
]] = new HashMap[E
, Array[E
]]
283 # Return a linear_extension of super_elements of the element
284 private fun linear_extension
(element
: E
, elements
: Set[E
]): Array[E
] do
285 if not self.linear_extensions_cache
.has_key
(element
) then
286 var supers
= new HashSet[E
]
288 supers
.add_all
(self.super_elements
(element
, elements
))
289 self.linear_extensions_cache
[element
] = self.linearize
(supers
)
291 return self.linear_extensions_cache
[element
]
294 private fun super_elements
(element
: E
, elements
: Set[E
]): Set[E
] is abstract
295 private fun sub_elements
(element
: E
, elements
: Set[E
]): Set[E
] is abstract
296 private fun is_element_mi
(element
: E
, elements
: Set[E
]): Bool is abstract
297 private fun linearize
(elements
: Set[E
]): Array[E
] is abstract
298 private fun reverse_linearize
(elements
: Set[E
]): Array[E
] is abstract
303 super TypingColorer[MType]
307 init(mmodule
: MModule) do self.mmodule
= mmodule
309 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mtypes
(element
, elements
)
310 redef fun is_element_mi
(element
, elements
) do return self.super_elements
(element
, elements
).length
> 1
311 redef fun sub_elements
(element
, elements
) do do return self.mmodule
.sub_mtypes
(element
, elements
)
312 redef fun linearize
(elements
) do return self.mmodule
.linearize_mtypes
(elements
)
313 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mtypes
(elements
)
318 super TypingColorer[MClass]
320 private var mmodule
: MModule
322 init(mmodule
: MModule) do self.mmodule
= mmodule
324 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mclasses
(element
)
325 fun parent_elements
(element
: MClass): Set[MClass] do return self.mmodule
.parent_mclasses
(element
)
326 redef fun is_element_mi
(element
, elements
) do return self.parent_elements
(element
).length
> 1
327 redef fun sub_elements
(element
, elements
) do do return self.mmodule
.sub_mclasses
(element
)
328 redef fun linearize
(elements
) do return self.mmodule
.linearize_mclasses
(elements
)
329 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mclasses
(elements
)
333 abstract class MPropertyColorer[E
: MProperty]
334 super PropertyLayoutBuilder[E
]
336 private var mmodule
: MModule
337 private var class_colorer
: MClassColorer
338 private var coloration_result
: Map[E
, Int] = new HashMap[E
, Int]
340 init(mmodule
: MModule) do
341 self.mmodule
= mmodule
342 self.class_colorer
= new MClassColorer(mmodule
)
345 # Compute mclasses ids and position using BM
346 redef fun build_layout
(mclasses
: Set[MClass]): Layout[E
] do
347 var result
= new Layout[E
]
348 result
.pos
= self.colorize
(mclasses
)
352 private fun colorize
(mclasses
: Set[MClass]): Map[E
, Int] do
353 self.class_colorer
.tag_elements
(mclasses
)
354 self.class_colorer
.build_conflicts_graph
(mclasses
)
355 self.colorize_core
(self.class_colorer
.core
)
356 self.colorize_crown
(self.class_colorer
.crown
)
357 return self.coloration_result
360 # Colorize properties of the core hierarchy
361 private fun colorize_core
(mclasses
: Set[MClass]) do
363 for mclass
in mclasses
do
364 var color
= min_color
366 # if the class is root, get the minimal color
367 if self.mmodule
.parent_mclasses
(mclass
).length
== 0 then
368 colorize_elements
(self.properties
(mclass
), color
)
370 # check last color used by parents
371 color
= max_color
(color
, self.mmodule
.parent_mclasses
(mclass
))
372 # check max color used in conflicts
373 if self.class_colorer
.conflicts_graph
.has_key
(mclass
) then
374 color
= max_color
(color
, self.class_colorer
.conflicts_graph
[mclass
])
376 colorize_elements
(self.properties
(mclass
), color
)
381 # Colorize properties of the crown hierarchy
382 private fun colorize_crown
(mclasses
: Set[MClass]) do
383 for mclass
in mclasses
do
384 colorize_elements
(self.properties
(mclass
), max_color
(0, self.mmodule
.parent_mclasses
(mclass
)))
388 # Colorize a collection of mproperties given a starting color
389 private fun colorize_elements
(elements
: Collection[E
], start_color
: Int) do
390 for element
in elements
do
391 if self.coloration_result
.has_key
(element
) then continue
392 self.coloration_result
[element
] = start_color
397 private fun max_color
(min_color
: Int, mclasses
: Collection[MClass]): Int do
398 var max_color
= min_color
400 for mclass
in mclasses
do
401 for mproperty
in self.properties
(mclass
) do
402 var color
= min_color
403 if self.coloration_result
.has_key
(mproperty
) then
404 color
= self.coloration_result
[mproperty
]
405 if color
>= max_color
then max_color
= color
+ 1
413 private fun properties
(mclass
: MClass): Set[E
] is abstract
416 # Coloring for MMethods
418 super MPropertyColorer[MMethod]
420 init(mmodule
: MModule) do super
422 redef fun properties
(mclass
) do
423 var properties
= new HashSet[MMethod]
424 for mprop
in self.mmodule
.properties
(mclass
) do
425 if mprop
isa MMethod then properties
.add
(mprop
)
431 # Coloring for MMAttributes
432 class MAttributeColorer
433 super MPropertyColorer[MAttribute]
435 init(mmodule
: MModule) do super
437 redef fun properties
(mclass
) do
438 var properties
= new HashSet[MAttribute]
439 for mprop
in self.mmodule
.properties
(mclass
) do
440 if mprop
isa MAttribute then properties
.add
(mprop
)
446 # Coloring for MVirtualTypeProps
447 class MVirtualTypePropColorer
448 super MPropertyColorer[MVirtualTypeProp]
450 init(mmodule
: MModule) do super
452 redef fun properties
(mclass
) do
453 var properties
= new HashSet[MVirtualTypeProp]
454 for mprop
in self.mmodule
.properties
(mclass
) do
455 if mprop
isa MVirtualTypeProp then properties
.add
(mprop
)
461 # Colorer for type resolution table
462 class ResolutionColorer
463 super ResolutionLayoutBuilder
465 private var coloration_result
: Map[MType, Int] = new HashMap[MType, Int]
469 # Compute resolved types colors
470 redef fun build_layout
(elements
) do
471 self.build_conflicts_graph
(elements
)
472 var result
= new Layout[MType]
473 result
.ids
= self.compute_ids
(elements
)
474 result
.pos
= self.colorize_elements
(elements
)
478 private fun compute_ids
(elements
: Map[MClassType, Set[MType]]): Map[MType, Int] do
479 var ids
= new HashMap[MType, Int]
481 for mclasstype
, mclasstypes
in elements
do
482 for element
in mclasstypes
do
483 if ids
.has_key
(element
) then continue
491 # Colorize a collection of elements
492 private fun colorize_elements
(elements
: Map[MClassType, Set[MType]]): Map[MType, Int] do
494 for mclasstype
, mclasstypes
in elements
do
495 for element
in mclasstypes
do
496 if self.coloration_result
.has_key
(element
) then continue
497 var color
= min_color
498 while not self.is_color_free
(element
, color
) do
501 coloration_result
[element
] = color
505 return self.coloration_result
508 # Check if a related element to the element already use the color
509 private fun is_color_free
(element
: MType, color
: Int): Bool do
510 if conflicts_graph
.has_key
(element
) then
511 for st
in conflicts_graph
[element
] do
512 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
518 # look for unanchored types generated by the same type
519 private fun build_conflicts_graph
(elements
: Map[MClassType, Set[MType]]) do
520 for mclasstype
, mtypes
in elements
do
521 for mtype
in mtypes
do
522 for otype
in mtypes
do
523 if otype
== mtype
then continue
524 self.add_conflict
(mtype
, otype
)
530 private var conflicts_graph
: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
532 private fun add_conflict
(mtype
: MType, otype
: MType) do
533 if mtype
== otype
then return
534 if not self.conflicts_graph
.has_key
(mtype
) then self.conflicts_graph
[mtype
] = new HashSet[MType]
535 self.conflicts_graph
[mtype
].add
(otype
)
536 if not self.conflicts_graph
.has_key
(otype
) then self.conflicts_graph
[otype
] = new HashSet[MType]
537 self.conflicts_graph
[otype
].add
(mtype
)
541 # Perfect Hashing (PH)
543 # U = type of elements to hash
544 private class PerfectHasher[T
: Object, U
: Object]
546 var operator
: PHOperator
548 init(operator
: PHOperator) do self.operator
= operator
550 fun compute_masks
(conflicts
: Map[T
, Set[U
]], ids
: Map[U
, Int]): Map[T
, Int] do
551 var masks
= new HashMap[T
, Int]
552 for mclasstype
, mtypes
in conflicts
do
553 masks
[mclasstype
] = compute_mask
(mtypes
, ids
)
558 private fun compute_mask
(mtypes
: Set[U
], ids
: Map[U
, Int]): Int do
561 var used
= new List[Int]
562 for mtype
in mtypes
do
563 var res
= operator
.op
(mask
, ids
[mtype
])
564 if used
.has
(res
) then
570 if used
.length
== mtypes
.length
then break
576 fun compute_hashes
(elements
: Map[T
, Set[U
]], ids
: Map[U
, Int], masks
: Map[T
, Int]): Map[T
, Map[U
, Int]] do
577 var hashes
= new HashMap[T
, Map[U
, Int]]
578 for mclasstype
, mtypes
in elements
do
579 var mask
= masks
[mclasstype
]
580 var inhashes
= new HashMap[U
, Int]
581 for mtype
in mtypes
do
582 inhashes
[mtype
] = operator
.op
(mask
, ids
[mtype
])
584 hashes
[mclasstype
] = inhashes
590 # Abstract operator used for perfect hashing
591 abstract class PHOperator
592 fun op
(mask
: Int, id
:Int): Int is abstract
595 # Hashing using modulo (MOD) operator
600 redef fun op
(mask
, id
) do return mask
% id
603 # Hashing using binary and (AND) operator
608 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
611 class TypingHasher[E
: Object]
612 super PerfectHasher[E
, E
]
613 super TypingLayoutBuilder[E
]
617 init(operator
: PHOperator, mmodule
: MModule) do
619 self.mmodule
= mmodule
622 redef fun build_layout
(elements
: Set[E
]): PHLayout[E
, E
] do
623 var result
= new PHLayout[E
, E
]
624 var conflicts
= self.build_conflicts
(elements
)
625 result
.ids
= self.compute_ids
(elements
)
626 result
.masks
= self.compute_masks
(conflicts
, result
.ids
)
627 result
.hashes
= self.compute_hashes
(conflicts
, result
.ids
, result
.masks
)
631 # Ids start from 1 instead of 0
632 private fun compute_ids
(elements
: Set[E
]): Map[E
, Int] do
633 var ids
= new HashMap[E
, Int]
634 var lin
= self.reverse_linearize
(elements
)
636 ids
[e
] = ids
.length
+ 1
641 private fun build_conflicts
(elements
: Set[E
]): Map[E
, Set[E
]] do
642 var conflicts
= new HashMap[E
, Set[E
]]
644 var supers
= self.super_elements
(e
, elements
)
646 conflicts
[e
] = supers
651 private fun super_elements
(element
: E
, elements
: Set[E
]): Set[E
] is abstract
652 private fun reverse_linearize
(elements
: Set[E
]): Array[E
] is abstract
656 super TypingHasher[MType]
658 init(operator
: PHOperator, mmodule
: MModule) do super(operator
, mmodule
)
660 redef fun super_elements
(element
, elements
) do
661 return self.mmodule
.super_mtypes
(element
, elements
)
664 redef fun reverse_linearize
(elements
) do
665 return self.mmodule
.reverse_linearize_mtypes
(elements
)
670 super TypingHasher[MClass]
672 init(operator
: PHOperator, mmodule
: MModule) do super(operator
, mmodule
)
674 redef fun super_elements
(element
, elements
) do
675 return self.mmodule
.super_mclasses
(element
)
678 redef fun reverse_linearize
(elements
) do
679 return self.mmodule
.reverse_linearize_mclasses
(elements
)
683 class ResolutionHasher
684 super PerfectHasher[MClassType, MType]
685 super ResolutionLayoutBuilder
687 init(operator
: PHOperator) do super(operator
)
689 # Compute resolved types masks and hashes
690 redef fun build_layout
(elements
) do
691 var result
= new PHLayout[MClassType, MType]
692 var ids
= new HashMap[MType, Int]
694 for mclasstype
, mclasstypes
in elements
do
695 for element
in mclasstypes
do
696 if ids
.has_key
(element
) then continue
703 result
.masks
= self.compute_masks
(elements
, ids
)
704 result
.hashes
= self.compute_hashes
(elements
, ids
, result
.masks
)