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 interface ResolutionLayoutBuilder
55 # Build resolution table layout
56 fun build_layout
(elements
: Map[MClassType, Set[MType]]): Layout[MType] is abstract
61 abstract class TypingBMizer[E
: Object]
62 super TypingLayoutBuilder[E
]
66 init(mmodule
: MModule) do
67 self.mmodule
= mmodule
70 # Compute mtypes ids and position using BM
71 redef fun build_layout
(elements
: Set[E
]): Layout[E
] do
72 var result
= new Layout[E
]
73 var ids
= new HashMap[E
, Int]
74 var lin
= self.reverse_linearize
(elements
)
76 ids
[element
] = ids
.length
83 private fun reverse_linearize
(elements
: Set[E
]): Array[E
] is abstract
87 super TypingBMizer[MType]
89 init(mmodule
: MModule) do super(mmodule
)
91 redef fun reverse_linearize
(elements
) do
92 return self.mmodule
.reverse_linearize_mtypes
(elements
)
97 super TypingBMizer[MClass]
99 init(mmodule
: MModule) do super(mmodule
)
101 redef fun reverse_linearize
(elements
) do
102 return self.mmodule
.reverse_linearize_mclasses
(elements
)
106 # Layout builder for resolution tables using Binary Matrix (BM)
107 class ResolutionBMizer
108 super ResolutionLayoutBuilder
112 redef fun build_layout
(elements
) do
113 var result
= new Layout[MType]
114 var ids
= new HashMap[MType, Int]
116 for mclasstype
, mclasstypes
in elements
do
117 for element
in mclasstypes
do
118 if ids
.has_key
(element
) then continue
129 # Abstract BMizing for MProperties
130 abstract class MPropertyBMizer[E
: MProperty]
131 super PropertyLayoutBuilder[E
]
133 type MPROP: MProperty
137 init(mmodule
: MModule) do self.mmodule
= mmodule
139 redef fun build_layout
(elements
) do
140 var result
= new Layout[E
]
141 var ids
= new HashMap[E
, Int]
142 var lin
= linearize_mclasses
(elements
)
144 for mproperty
in properties
(mclass
) do
145 if ids
.has_key
(mproperty
) then continue
146 ids
[mproperty
] = ids
.length
153 private fun properties
(mclass
: MClass): Set[E
] do
154 var properties
= new HashSet[E
]
155 for mprop
in self.mmodule
.properties
(mclass
) do
156 if mprop
isa MPROP then properties
.add
(mprop
)
161 private fun linearize_mclasses
(mclasses
: Set[MClass]): Array[MClass] is abstract
164 # BMizing for MMethods
166 super MPropertyBMizer[MMethod]
168 redef type MPROP: MMethod
169 init(mmodule
: MModule) do super(mmodule
)
170 # Less holes in tables with reverse linearization for method tables
171 redef fun linearize_mclasses
(mclasses
) do return self.mmodule
.reverse_linearize_mclasses
(mclasses
)
174 # BMizing for MMAttributes
175 class MAttributeBMizer
176 super MPropertyBMizer[MAttribute]
178 redef type MPROP: MAttribute
179 init(mmodule
: MModule) do super(mmodule
)
180 # Less holes in tables with linearization for attribute tables
181 redef fun linearize_mclasses
(mclasses
) do return self.mmodule
.linearize_mclasses_2
(mclasses
)
184 # BMizing for MVirtualTypeProps
185 class MVirtualTypePropBMizer
186 super MPropertyBMizer[MVirtualTypeProp]
188 redef type MPROP: MVirtualTypeProp
189 init(mmodule
: MModule) do super(mmodule
)
190 # Less holes in tables with reverse linearization for method tables
191 redef fun linearize_mclasses
(mclasses
) do return self.mmodule
.reverse_linearize_mclasses
(mclasses
)
196 abstract class TypingColorer[E
: Object]
197 super TypingLayoutBuilder[E
]
199 private var core
: Set[E
] = new HashSet[E
]
200 private var crown
: Set[E
] = new HashSet[E
]
201 private var border
: Set[E
] = new HashSet[E
]
203 private var coloration_result
: Map[E
, Int] = new HashMap[E
, Int]
207 # Compute the layout with coloring
208 redef fun build_layout
(elements
: Set[E
]): Layout[E
] do
209 var result
= new Layout[E
]
210 result
.ids
= compute_ids
(elements
)
211 result
.pos
= colorize
(elements
)
215 private fun compute_ids
(elements
: Set[E
]): Map[E
, Int] do
216 var ids
= new HashMap[E
, Int]
217 var lin
= reverse_linearize
(elements
)
218 for element
in lin
do
219 ids
[element
] = ids
.length
224 private fun colorize
(elements
: Set[E
]): Map[E
, Int] do
225 tag_elements
(elements
)
226 build_conflicts_graph
(elements
)
227 colorize_elements
(core
)
228 colorize_elements
(border
)
229 colorize_elements
(crown
)
230 return coloration_result
233 # Colorize a collection of elements
234 private fun colorize_elements
(elements
: Set[E
]) do
237 var lin
= reverse_linearize
(elements
)
238 for element
in lin
do
239 var color
= min_color
240 while not self.is_color_free
(element
, elements
, color
) do
243 coloration_result
[element
] = color
248 # Check if a related element to the element already use the color
249 private fun is_color_free
(element
: E
, elements
: Set[E
], color
: Int): Bool do
250 if conflicts_graph
.has_key
(element
) then
251 for st
in conflicts_graph
[element
] do
252 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
255 for st
in self.super_elements
(element
, elements
) do
256 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
261 # Tag elements as core, crown or border
262 private fun tag_elements
(elements
: Set[E
]) do
263 for element
in elements
do
264 # Check if sub elements are all in single inheritance
265 var all_subelements_si
= true
266 for subelem
in self.sub_elements
(element
, elements
) do
267 if self.is_element_mi
(subelem
, elements
) then
268 all_subelements_si
= false
273 # Tag as core, crown or border
274 if self.is_element_mi
(element
, elements
) then
275 core
.add_all
(self.super_elements
(element
, elements
))
277 if all_subelements_si
then
280 else if not all_subelements_si
then
281 core
.add_all
(self.super_elements
(element
, elements
))
289 # Conflicts graph of elements hierarchy (two types are in conflict if they have common subelements)
290 private fun build_conflicts_graph
(elements
: Set[E
]) do
291 self.conflicts_graph
= new HashMap[E
, HashSet[E
]]
292 var core
= reverse_linearize
(self.core
)
294 for i
in self.linear_extension
(t
, elements
) do
295 if t
== i
then continue
297 var lin_i
= self.linear_extension
(i
, elements
)
299 for j
in self.linear_extension
(t
, elements
) do
300 if i
== j
or j
== t
then continue
301 var lin_j
= self.linear_extension
(j
, elements
)
303 var d_ij
= lin_i
- lin_j
304 var d_ji
= lin_j
- lin_i
307 if not conflicts_graph
.has_key
(ed1
) then conflicts_graph
[ed1
] = new HashSet[E
]
308 # add ed1 x ed2 to conflicts graph
309 for ed2
in d_ji
do conflicts_graph
[ed1
].add
(ed2
)
312 if not conflicts_graph
.has_key
(ed1
) then conflicts_graph
[ed1
] = new HashSet[E
]
313 # add ed1 x ed2 to conflicts graph
314 for ed2
in d_ji
do conflicts_graph
[ed1
].add
(ed2
)
321 private var conflicts_graph
: nullable HashMap[E
, Set[E
]]
323 # cache for linear_extensions
324 private var linear_extensions_cache
: Map[E
, Array[E
]] = new HashMap[E
, Array[E
]]
326 # Return a linear_extension of super_elements of the element
327 private fun linear_extension
(element
: E
, elements
: Set[E
]): Array[E
] do
328 if not self.linear_extensions_cache
.has_key
(element
) then
329 var supers
= new HashSet[E
]
331 supers
.add_all
(self.super_elements
(element
, elements
))
332 self.linear_extensions_cache
[element
] = self.linearize
(supers
)
334 return self.linear_extensions_cache
[element
]
337 private fun super_elements
(element
: E
, elements
: Set[E
]): Set[E
] is abstract
338 private fun sub_elements
(element
: E
, elements
: Set[E
]): Set[E
] is abstract
339 private fun is_element_mi
(element
: E
, elements
: Set[E
]): Bool is abstract
340 private fun linearize
(elements
: Set[E
]): Array[E
] is abstract
341 private fun reverse_linearize
(elements
: Set[E
]): Array[E
] is abstract
346 super TypingColorer[MType]
350 init(mmodule
: MModule) do self.mmodule
= mmodule
352 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mtypes
(element
, elements
)
353 redef fun is_element_mi
(element
, elements
) do return self.super_elements
(element
, elements
).length
> 1
354 redef fun sub_elements
(element
, elements
) do do return self.mmodule
.sub_mtypes
(element
, elements
)
355 redef fun linearize
(elements
) do return self.mmodule
.linearize_mtypes
(elements
)
356 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mtypes
(elements
)
361 super TypingColorer[MClass]
363 private var mmodule
: MModule
365 init(mmodule
: MModule) do self.mmodule
= mmodule
367 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mclasses
(element
)
368 fun parent_elements
(element
: MClass): Set[MClass] do return self.mmodule
.parent_mclasses
(element
)
369 redef fun is_element_mi
(element
, elements
) do return self.parent_elements
(element
).length
> 1
370 redef fun sub_elements
(element
, elements
) do do return self.mmodule
.sub_mclasses
(element
)
371 redef fun linearize
(elements
) do return self.mmodule
.linearize_mclasses_2
(elements
)
372 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mclasses
(elements
)
376 abstract class MPropertyColorer[E
: MProperty]
377 super PropertyLayoutBuilder[E
]
379 type MPROP: MProperty
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) do
386 self.mmodule
= mmodule
387 self.class_colorer
= new MClassColorer(mmodule
)
390 # Compute mclasses ids and position using BM
391 redef fun build_layout
(mclasses
: Set[MClass]): Layout[E
] do
392 var result
= new Layout[E
]
393 result
.pos
= self.colorize
(mclasses
)
397 private fun colorize
(mclasses
: Set[MClass]): Map[E
, Int] do
398 self.class_colorer
.tag_elements
(mclasses
)
399 self.class_colorer
.build_conflicts_graph
(mclasses
)
400 self.colorize_core
(self.class_colorer
.core
)
401 self.colorize_crown
(self.class_colorer
.crown
)
402 return self.coloration_result
405 # Colorize properties of the core hierarchy
406 private fun colorize_core
(mclasses
: Set[MClass]) do
408 for mclass
in mclasses
do
409 var color
= min_color
411 # if the class is root, get the minimal color
412 if self.mmodule
.parent_mclasses
(mclass
).length
== 0 then
413 colorize_elements
(self.properties
(mclass
), color
)
415 # check last color used by parents
416 color
= max_color
(color
, self.mmodule
.parent_mclasses
(mclass
))
417 # check max color used in conflicts
418 if self.class_colorer
.conflicts_graph
.has_key
(mclass
) then
419 color
= max_color
(color
, self.class_colorer
.conflicts_graph
[mclass
])
421 colorize_elements
(self.properties
(mclass
), color
)
426 # Colorize properties of the crown hierarchy
427 private fun colorize_crown
(mclasses
: Set[MClass]) do
428 for mclass
in mclasses
do
429 colorize_elements
(self.properties
(mclass
), max_color
(0, self.mmodule
.parent_mclasses
(mclass
)))
433 # Colorize a collection of mproperties given a starting color
434 private fun colorize_elements
(elements
: Collection[E
], start_color
: Int) do
435 for element
in elements
do
436 if self.coloration_result
.has_key
(element
) then continue
437 self.coloration_result
[element
] = start_color
442 private fun max_color
(min_color
: Int, mclasses
: Collection[MClass]): Int do
443 var max_color
= min_color
445 for mclass
in mclasses
do
446 for mproperty
in self.properties
(mclass
) do
447 var color
= min_color
448 if self.coloration_result
.has_key
(mproperty
) then
449 color
= self.coloration_result
[mproperty
]
450 if color
>= max_color
then max_color
= color
+ 1
458 private fun properties
(mclass
: MClass): Set[E
] do
459 var properties
= new HashSet[E
]
460 for mprop
in self.mmodule
.properties
(mclass
) do
461 if mprop
isa MPROP then properties
.add
(mprop
)
467 # Coloring for MMethods
469 super MPropertyColorer[MMethod]
471 redef type MPROP: MMethod
472 init(mmodule
: MModule) do super
475 # Coloring for MMAttributes
476 class MAttributeColorer
477 super MPropertyColorer[MAttribute]
479 redef type MPROP: MAttribute
480 init(mmodule
: MModule) do super
483 # Coloring for MVirtualTypeProps
484 class MVirtualTypePropColorer
485 super MPropertyColorer[MVirtualTypeProp]
487 redef type MPROP: MVirtualTypeProp
488 init(mmodule
: MModule) do super
491 # Colorer for type resolution table
492 class ResolutionColorer
493 super ResolutionLayoutBuilder
495 private var coloration_result
: Map[MType, Int] = new HashMap[MType, Int]
499 # Compute resolved types colors
500 redef fun build_layout
(elements
) do
501 self.build_conflicts_graph
(elements
)
502 var result
= new Layout[MType]
503 result
.ids
= self.compute_ids
(elements
)
504 result
.pos
= self.colorize_elements
(elements
)
508 private fun compute_ids
(elements
: Map[MClassType, Set[MType]]): Map[MType, Int] do
509 var ids
= new HashMap[MType, Int]
511 for mclasstype
, mclasstypes
in elements
do
512 for element
in mclasstypes
do
513 if ids
.has_key
(element
) then continue
521 # Colorize a collection of elements
522 private fun colorize_elements
(elements
: Map[MClassType, Set[MType]]): Map[MType, Int] do
524 for mclasstype
, mclasstypes
in elements
do
525 for element
in mclasstypes
do
526 if self.coloration_result
.has_key
(element
) then continue
527 var color
= min_color
528 while not self.is_color_free
(element
, color
) do
531 coloration_result
[element
] = color
535 return self.coloration_result
538 # Check if a related element to the element already use the color
539 private fun is_color_free
(element
: MType, color
: Int): Bool do
540 if conflicts_graph
.has_key
(element
) then
541 for st
in conflicts_graph
[element
] do
542 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
548 # look for unanchored types generated by the same type
549 private fun build_conflicts_graph
(elements
: Map[MClassType, Set[MType]]) do
550 for mclasstype
, mtypes
in elements
do
551 for mtype
in mtypes
do
552 for otype
in mtypes
do
553 if otype
== mtype
then continue
554 self.add_conflict
(mtype
, otype
)
560 private var conflicts_graph
: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
562 private fun add_conflict
(mtype
: MType, otype
: MType) do
563 if mtype
== otype
then return
564 if not self.conflicts_graph
.has_key
(mtype
) then self.conflicts_graph
[mtype
] = new HashSet[MType]
565 self.conflicts_graph
[mtype
].add
(otype
)
566 if not self.conflicts_graph
.has_key
(otype
) then self.conflicts_graph
[otype
] = new HashSet[MType]
567 self.conflicts_graph
[otype
].add
(mtype
)
571 # Perfect Hashing (PH)
573 # U = type of elements to hash
574 private class PerfectHasher[T
: Object, U
: Object]
576 var operator
: PHOperator
578 init(operator
: PHOperator) do self.operator
= operator
580 fun compute_masks
(conflicts
: Map[T
, Set[U
]], ids
: Map[U
, Int]): Map[T
, Int] do
581 var masks
= new HashMap[T
, Int]
582 for mclasstype
, mtypes
in conflicts
do
583 masks
[mclasstype
] = compute_mask
(mtypes
, ids
)
588 private fun compute_mask
(mtypes
: Set[U
], ids
: Map[U
, Int]): Int do
591 var used
= new List[Int]
592 for mtype
in mtypes
do
593 var res
= operator
.op
(mask
, ids
[mtype
])
594 if used
.has
(res
) then
600 if used
.length
== mtypes
.length
then break
606 fun compute_hashes
(elements
: Map[T
, Set[U
]], ids
: Map[U
, Int], masks
: Map[T
, Int]): Map[T
, Map[U
, Int]] do
607 var hashes
= new HashMap[T
, Map[U
, Int]]
608 for mclasstype
, mtypes
in elements
do
609 var mask
= masks
[mclasstype
]
610 var inhashes
= new HashMap[U
, Int]
611 for mtype
in mtypes
do
612 inhashes
[mtype
] = operator
.op
(mask
, ids
[mtype
])
614 hashes
[mclasstype
] = inhashes
620 # Abstract operator used for perfect hashing
621 abstract class PHOperator
622 fun op
(mask
: Int, id
:Int): Int is abstract
625 # Hashing using modulo (MOD) operator
630 redef fun op
(mask
, id
) do return mask
% id
633 # Hashing using binary and (AND) operator
638 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
641 class TypingHasher[E
: Object]
642 super PerfectHasher[E
, E
]
643 super TypingLayoutBuilder[E
]
647 init(operator
: PHOperator, mmodule
: MModule) do
649 self.mmodule
= mmodule
652 redef fun build_layout
(elements
: Set[E
]): PHLayout[E
, E
] do
653 var result
= new PHLayout[E
, E
]
654 var conflicts
= self.build_conflicts
(elements
)
655 result
.ids
= self.compute_ids
(elements
)
656 result
.masks
= self.compute_masks
(conflicts
, result
.ids
)
657 result
.hashes
= self.compute_hashes
(conflicts
, result
.ids
, result
.masks
)
661 # Ids start from 1 instead of 0
662 private fun compute_ids
(elements
: Set[E
]): Map[E
, Int] do
663 var ids
= new HashMap[E
, Int]
664 var lin
= self.reverse_linearize
(elements
)
666 ids
[e
] = ids
.length
+ 1
671 private fun build_conflicts
(elements
: Set[E
]): Map[E
, Set[E
]] do
672 var conflicts
= new HashMap[E
, Set[E
]]
674 var supers
= self.super_elements
(e
, elements
)
676 conflicts
[e
] = supers
681 private fun super_elements
(element
: E
, elements
: Set[E
]): Set[E
] is abstract
682 private fun reverse_linearize
(elements
: Set[E
]): Array[E
] is abstract
686 super TypingHasher[MType]
688 init(operator
: PHOperator, mmodule
: MModule) do super(operator
, mmodule
)
690 redef fun super_elements
(element
, elements
) do
691 return self.mmodule
.super_mtypes
(element
, elements
)
694 redef fun reverse_linearize
(elements
) do
695 return self.mmodule
.reverse_linearize_mtypes
(elements
)
700 super TypingHasher[MClass]
702 init(operator
: PHOperator, mmodule
: MModule) do super(operator
, mmodule
)
704 redef fun super_elements
(element
, elements
) do
705 return self.mmodule
.super_mclasses
(element
)
708 redef fun reverse_linearize
(elements
) do
709 return self.mmodule
.reverse_linearize_mclasses
(elements
)
713 # Layout builder for MProperty using Perfect Hashing (PH)
714 # TODO implement this class without sublcassing CL builder
715 class MPropertyHasher[E
: MProperty]
716 super MPropertyColorer[E
]
719 class ResolutionHasher
720 super PerfectHasher[MClassType, MType]
721 super ResolutionLayoutBuilder
723 init(operator
: PHOperator) do super(operator
)
725 # Compute resolved types masks and hashes
726 redef fun build_layout
(elements
) do
727 var result
= new PHLayout[MClassType, MType]
728 var ids
= new HashMap[MType, Int]
730 for mclasstype
, mclasstypes
in elements
do
731 for element
in mclasstypes
do
732 if ids
.has_key
(element
) then continue
739 result
.masks
= self.compute_masks
(elements
, ids
)
740 result
.hashes
= self.compute_hashes
(elements
, ids
, result
.masks
)