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 PHTypingLayout[E
: Object]
31 # Masks used by hash function
32 var masks
: Map[E
, Int] = new HashMap[E
, Int]
33 # Positions of each element for each tables
34 var hashes
: Map[E
, Map[E
, Int]] = new HashMap[E
, 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]
42 class PHResolutionLayout
44 # Masks associated to each owner of a resolution table
45 var masks
: Map[MClassType, Int] = new HashMap[MClassType, Int]
46 # Positions of each resolvec type for resolution tables
47 var hashes
: Map[MClassType, Map[MType, Int]] = new HashMap[MClassType, Map[MType, Int]]
52 abstract class TypingLayoutBuilder[E
: Object]
54 type LAYOUT: Layout[E
]
56 private var mmodule
: MModule
57 init(mmodule
: MModule) do self.mmodule
= mmodule
59 # Compute elements ids and position
60 fun build_layout
(elements
: Set[E
]): LAYOUT is abstract
62 # Give each MType a unic id using a descending linearization of the `mtypes` set
63 private fun compute_ids
(elements
: Set[E
]): Map[E
, Int] do
64 var ids
= new HashMap[E
, Int]
65 var lin
= self.reverse_linearize
(elements
)
67 ids
[element
] = ids
.length
72 private fun reverse_linearize
(elements
: Set[E
]): Array[E
] is abstract
75 # Layout builder for MType using Binary Matrix (BM)
76 class BMTypeLayoutBuilder
77 super TypingLayoutBuilder[MType]
79 init(mmodule
: MModule) do super
81 # Compute mtypes ids and position using BM
82 redef fun build_layout
(mtypes
) do
83 var result
= new Layout[MType]
84 result
.ids
= self.compute_ids
(mtypes
)
85 result
.pos
= result
.ids
89 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mtypes
(elements
)
92 # Layout builder for MType using Coloring (CL)
93 class CLTypeLayoutBuilder
94 super TypingLayoutBuilder[MType]
96 private var colorer
: MTypeColorer
98 init(mmodule
: MModule) do
100 self.colorer
= new MTypeColorer(mmodule
)
103 # Compute mtypes ids and position using BM
104 redef fun build_layout
(mtypes
) do
105 var result
= new Layout[MType]
106 result
.ids
= self.compute_ids
(mtypes
)
107 result
.pos
= self.colorer
.colorize
(mtypes
)
111 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mtypes
(elements
)
114 # Layout builder for MType using Perfect Hashing (PH)
115 class PHTypeLayoutBuilder
116 super TypingLayoutBuilder[MType]
118 redef type LAYOUT: PHTypingLayout[MType]
120 private var hasher
: PerfectHasher[MType, MType]
122 init(mmodule
: MModule, operator
: PHOperator) do
124 self.hasher
= new PerfectHasher[MType, MType](operator
)
127 private fun build_conflicts
(mtypes
: Set[MType]): Map[MType, Set[MType]] do
128 var conflicts
= new HashMap[MType, Set[MType]]
129 for mtype
in mtypes
do
130 var supers
= self.mmodule
.super_mtypes
(mtype
, mtypes
)
132 conflicts
[mtype
] = supers
137 # Compute mtypes ids and position using BM
138 redef fun build_layout
(mtypes
) do
139 var result
= new PHTypingLayout[MType]
140 var conflicts
= build_conflicts
(mtypes
)
141 result
.ids
= self.compute_ids
(mtypes
)
142 result
.masks
= self.hasher
.compute_masks
(conflicts
, result
.ids
)
143 result
.hashes
= self.hasher
.compute_hashes
(conflicts
, result
.ids
, result
.masks
)
147 # Ids start from 1 instead of 0
148 redef fun compute_ids
(mtypes
) do
149 var ids
= new HashMap[MType, Int]
150 var lin
= self.mmodule
.reverse_linearize_mtypes
(mtypes
)
152 ids
[mtype
] = ids
.length
+ 1
157 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mtypes
(elements
)
160 # Layout builder for MClass using Binary Matrix (BM)
161 class BMClassLayoutBuilder
162 super TypingLayoutBuilder[MClass]
164 init(mmodule
: MModule) do super
166 # Compute mclasses ids and position using BM
167 redef fun build_layout
(mclasses
) do
168 var result
= new Layout[MClass]
169 result
.ids
= self.compute_ids
(mclasses
)
170 result
.pos
= result
.ids
174 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mclasses
(elements
)
177 # Layout builder for MClass using Coloring (CL)
178 class CLClassLayoutBuilder
179 super TypingLayoutBuilder[MClass]
181 private var colorer
: MClassColorer
183 init(mmodule
: MModule) do
185 self.colorer
= new MClassColorer(mmodule
)
188 # Compute mclasses ids and position using BM
189 redef fun build_layout
(mclasses
) do
190 var result
= new Layout[MClass]
191 result
.ids
= self.compute_ids
(mclasses
)
192 result
.pos
= self.colorer
.colorize
(mclasses
)
196 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mclasses
(elements
)
199 # Layout builder for MClass using Perfect Hashing (PH)
200 class PHClassLayoutBuilder
201 super TypingLayoutBuilder[MClass]
203 redef type LAYOUT: PHTypingLayout[MClass]
205 private var hasher
: PerfectHasher[MClass, MClass]
207 init(mmodule
: MModule, operator
: PHOperator) do
209 self.hasher
= new PerfectHasher[MClass, MClass](operator
)
212 private fun build_conflicts
(mclasses
: Set[MClass]): Map[MClass, Set[MClass]] do
213 var conflicts
= new HashMap[MClass, Set[MClass]]
214 for mclass
in mclasses
do
215 var supers
= self.mmodule
.super_mclasses
(mclass
)
217 conflicts
[mclass
] = supers
222 # Compute mclasses ids and position using BM
223 redef fun build_layout
(mclasses
) do
224 var result
= new PHTypingLayout[MClass]
225 var conflicts
= build_conflicts
(mclasses
)
226 result
.ids
= self.compute_ids
(mclasses
)
227 result
.masks
= self.hasher
.compute_masks
(conflicts
, result
.ids
)
228 result
.hashes
= self.hasher
.compute_hashes
(conflicts
, result
.ids
, result
.masks
)
232 # Ids start from 1 instead of 0
233 redef fun compute_ids
(mclasses
) do
234 var ids
= new HashMap[MClass, Int]
235 var lin
= self.mmodule
.reverse_linearize_mclasses
(mclasses
)
237 ids
[mclass
] = ids
.length
+ 1
242 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mclasses
(elements
)
245 abstract class PropertyLayoutBuilder[E
: MProperty]
247 type LAYOUT: PropertyLayout[E
]
249 # Compute properties ids and position
250 fun build_layout
(mclasses
: Set[MClass]): LAYOUT is abstract
253 # Layout builder for MProperty using Coloring (CL)
254 class CLPropertyLayoutBuilder[E
: MProperty]
255 super PropertyLayoutBuilder[E
]
257 private var colorer
: MPropertyColorer[E
]
259 init(colorer
: MPropertyColorer[E
]) do
260 self.colorer
= colorer
263 # Compute mclasses ids and position using BM
264 redef fun build_layout
(mclasses
) do
265 var result
= new PropertyLayout[E
]
266 result
.pos
= self.colorer
.colorize
(mclasses
)
271 # Layout builder for MProperty using Perfect Hashing (PH)
272 # TODO implement this class without sublcassing CL builder
273 class PHPropertyLayoutBuilder[E
: MProperty]
274 super CLPropertyLayoutBuilder[E
]
277 abstract class ResolutionLayoutBuilder
279 type LAYOUT: Layout[MType]
283 fun build_layout
(elements
: Map[MClassType, Set[MType]]): LAYOUT is abstract
285 fun compute_ids
(elements
: Map[MClassType, Set[MType]]): Map[MType, Int] do
286 var ids
= new HashMap[MType, Int]
288 for mclasstype
, mclasstypes
in elements
do
289 for element
in mclasstypes
do
290 if ids
.has_key
(element
) then continue
299 # Layout builder for MClass using Binary Matrix (BM)
300 class BMResolutionLayoutBuilder
301 super ResolutionLayoutBuilder
305 # Compute resolved types position using BM
306 redef fun build_layout
(elements
) do
307 var result
= new Layout[MType]
308 result
.ids
= self.compute_ids
(elements
)
309 result
.pos
= result
.ids
314 # Layout builder for resolution tables using Coloring (CL)
315 class CLResolutionLayoutBuilder
316 super ResolutionLayoutBuilder
318 private var colorer
: ResolutionColorer = new ResolutionColorer
322 # Compute resolved types colors
323 redef fun build_layout
(elements
) do
324 var result
= new Layout[MType]
325 result
.ids
= self.compute_ids
(elements
)
326 result
.pos
= self.colorer
.colorize
(elements
)
331 # Layout builder for resolution table using Perfect Hashing (PH)
332 class PHResolutionLayoutBuilder
333 super ResolutionLayoutBuilder
335 redef type LAYOUT: PHResolutionLayout
337 private var hasher
: PerfectHasher[MClassType, MType]
339 init(operator
: PHOperator) do self.hasher
= new PerfectHasher[MClassType, MType](operator
)
341 # Compute resolved types masks and hashes
342 redef fun build_layout
(elements
) do
343 var result
= new PHResolutionLayout
344 result
.ids
= self.compute_ids
(elements
)
345 result
.pos
= result
.ids
346 result
.masks
= self.hasher
.compute_masks
(elements
, result
.ids
)
347 result
.hashes
= self.hasher
.compute_hashes
(elements
, result
.ids
, result
.masks
)
351 redef fun compute_ids
(elements
) do
352 var ids
= new HashMap[MType, Int]
354 for mclasstype
, mclasstypes
in elements
do
355 for element
in mclasstypes
do
356 if ids
.has_key
(element
) then continue
367 abstract class AbstractColorer[E
: Object]
369 private var core
: Set[E
] = new HashSet[E
]
370 private var crown
: Set[E
] = new HashSet[E
]
371 private var border
: Set[E
] = new HashSet[E
]
373 private var coloration_result
: Map[E
, Int] = new HashMap[E
, Int]
377 fun colorize
(elements
: Set[E
]): Map[E
, Int] do
378 tag_elements
(elements
)
379 build_conflicts_graph
(elements
)
380 colorize_elements
(core
)
381 colorize_elements
(border
)
382 colorize_elements
(crown
)
383 return coloration_result
386 # Colorize a collection of elements
387 private fun colorize_elements
(elements
: Set[E
]) do
390 var lin
= reverse_linearize
(elements
)
391 for element
in lin
do
392 var color
= min_color
393 while not self.is_color_free
(element
, elements
, color
) do
396 coloration_result
[element
] = color
401 # Check if a related element to the element already use the color
402 private fun is_color_free
(element
: E
, elements
: Set[E
], color
: Int): Bool do
403 if conflicts_graph
.has_key
(element
) then
404 for st
in conflicts_graph
[element
] do
405 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
408 for st
in self.super_elements
(element
, elements
) do
409 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
414 # Tag elements as core, crown or border
415 private fun tag_elements
(elements
: Set[E
]) do
416 for element
in elements
do
417 # Check if sub elements are all in single inheritance
418 var all_subelements_si
= true
419 for subelem
in self.sub_elements
(element
, elements
) do
420 if self.is_element_mi
(subelem
, elements
) then
421 all_subelements_si
= false
426 # Tag as core, crown or border
427 if self.is_element_mi
(element
, elements
) then
428 core
.add_all
(self.super_elements
(element
, elements
))
430 if all_subelements_si
then
433 else if not all_subelements_si
then
434 core
.add_all
(self.super_elements
(element
, elements
))
442 # Conflicts graph of elements hierarchy (two types are in conflict if they have common subelements)
443 private fun build_conflicts_graph
(elements
: Set[E
]) do
444 self.conflicts_graph
= new HashMap[E
, HashSet[E
]]
445 var core
= reverse_linearize
(self.core
)
447 for i
in self.linear_extension
(t
, elements
) do
448 if t
== i
then continue
450 var lin_i
= self.linear_extension
(i
, elements
)
452 for j
in self.linear_extension
(t
, elements
) do
453 if i
== j
or j
== t
then continue
454 var lin_j
= self.linear_extension
(j
, elements
)
456 var d_ij
= lin_i
- lin_j
457 var d_ji
= lin_j
- lin_i
460 if not conflicts_graph
.has_key
(ed1
) then conflicts_graph
[ed1
] = new HashSet[E
]
461 # add ed1 x ed2 to conflicts graph
462 for ed2
in d_ji
do conflicts_graph
[ed1
].add
(ed2
)
465 if not conflicts_graph
.has_key
(ed1
) then conflicts_graph
[ed1
] = new HashSet[E
]
466 # add ed1 x ed2 to conflicts graph
467 for ed2
in d_ji
do conflicts_graph
[ed1
].add
(ed2
)
474 private var conflicts_graph
: nullable HashMap[E
, Set[E
]]
476 # cache for linear_extensions
477 private var linear_extensions_cache
: Map[E
, Array[E
]] = new HashMap[E
, Array[E
]]
479 # Return a linear_extension of super_elements of the element
480 private fun linear_extension
(element
: E
, elements
: Set[E
]): Array[E
] do
481 if not self.linear_extensions_cache
.has_key
(element
) then
482 var supers
= new HashSet[E
]
484 supers
.add_all
(self.super_elements
(element
, elements
))
485 self.linear_extensions_cache
[element
] = self.linearize
(supers
)
487 return self.linear_extensions_cache
[element
]
490 private fun super_elements
(element
: E
, elements
: Set[E
]): Set[E
] is abstract
491 private fun sub_elements
(element
: E
, elements
: Set[E
]): Set[E
] is abstract
492 private fun is_element_mi
(element
: E
, elements
: Set[E
]): Bool is abstract
493 private fun linearize
(elements
: Set[E
]): Array[E
] is abstract
494 private fun reverse_linearize
(elements
: Set[E
]): Array[E
] is abstract
498 private class MTypeColorer
499 super AbstractColorer[MType]
503 init(mmodule
: MModule) do self.mmodule
= mmodule
505 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mtypes
(element
, elements
)
506 redef fun is_element_mi
(element
, elements
) do return self.super_elements
(element
, elements
).length
> 1
507 redef fun sub_elements
(element
, elements
) do do return self.mmodule
.sub_mtypes
(element
, elements
)
508 redef fun linearize
(elements
) do return self.mmodule
.linearize_mtypes
(elements
)
509 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mtypes
(elements
)
513 private class MClassColorer
514 super AbstractColorer[MClass]
516 private var mmodule
: MModule
518 init(mmodule
: MModule) do self.mmodule
= mmodule
520 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mclasses
(element
)
521 fun parent_elements
(element
: MClass): Set[MClass] do return self.mmodule
.parent_mclasses
(element
)
522 redef fun is_element_mi
(element
, elements
) do return self.parent_elements
(element
).length
> 1
523 redef fun sub_elements
(element
, elements
) do do return self.mmodule
.sub_mclasses
(element
)
524 redef fun linearize
(elements
) do return self.mmodule
.linearize_mclasses
(elements
)
525 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mclasses
(elements
)
529 abstract class MPropertyColorer[E
: MProperty]
531 private var mmodule
: MModule
532 private var class_colorer
: MClassColorer
533 private var coloration_result
: Map[E
, Int] = new HashMap[E
, Int]
535 init(mmodule
: MModule) do
536 self.mmodule
= mmodule
537 self.class_colorer
= new MClassColorer(mmodule
)
540 fun colorize
(mclasses
: Set[MClass]): Map[E
, Int] do
541 self.class_colorer
.tag_elements
(mclasses
)
542 self.class_colorer
.build_conflicts_graph
(mclasses
)
543 self.colorize_core
(self.class_colorer
.core
)
544 self.colorize_crown
(self.class_colorer
.crown
)
545 return self.coloration_result
548 # Colorize properties of the core hierarchy
549 private fun colorize_core
(mclasses
: Set[MClass]) do
551 for mclass
in mclasses
do
552 var color
= min_color
554 # if the class is root, get the minimal color
555 if self.mmodule
.parent_mclasses
(mclass
).length
== 0 then
556 colorize_elements
(self.properties
(mclass
), color
)
558 # check last color used by parents
559 color
= max_color
(color
, self.mmodule
.parent_mclasses
(mclass
))
560 # check max color used in conflicts
561 if self.class_colorer
.conflicts_graph
.has_key
(mclass
) then
562 color
= max_color
(color
, self.class_colorer
.conflicts_graph
[mclass
])
564 colorize_elements
(self.properties
(mclass
), color
)
569 # Colorize properties of the crown hierarchy
570 private fun colorize_crown
(mclasses
: Set[MClass]) do
571 for mclass
in mclasses
do
572 colorize_elements
(self.properties
(mclass
), max_color
(0, self.mmodule
.parent_mclasses
(mclass
)))
576 # Colorize a collection of mproperties given a starting color
577 private fun colorize_elements
(elements
: Collection[E
], start_color
: Int) do
578 for element
in elements
do
579 if self.coloration_result
.has_key
(element
) then continue
580 self.coloration_result
[element
] = start_color
585 private fun max_color
(min_color
: Int, mclasses
: Collection[MClass]): Int do
586 var max_color
= min_color
588 for mclass
in mclasses
do
589 for mproperty
in self.properties
(mclass
) do
590 var color
= min_color
591 if self.coloration_result
.has_key
(mproperty
) then
592 color
= self.coloration_result
[mproperty
]
593 if color
>= max_color
then max_color
= color
+ 1
601 private fun properties
(mclass
: MClass): Set[E
] is abstract
604 # Coloring for MMethods
606 super MPropertyColorer[MMethod]
608 init(mmodule
: MModule) do super
610 redef fun properties
(mclass
) do
611 var properties
= new HashSet[MMethod]
612 for mprop
in self.mmodule
.properties
(mclass
) do
613 if mprop
isa MMethod then properties
.add
(mprop
)
619 # Coloring for MMAttributes
620 class MAttributeColorer
621 super MPropertyColorer[MAttribute]
623 init(mmodule
: MModule) do super
625 redef fun properties
(mclass
) do
626 var properties
= new HashSet[MAttribute]
627 for mprop
in self.mmodule
.properties
(mclass
) do
628 if mprop
isa MAttribute then properties
.add
(mprop
)
634 # Coloring for MVirtualTypeProps
635 class MVirtualTypePropColorer
636 super MPropertyColorer[MVirtualTypeProp]
638 init(mmodule
: MModule) do super
640 redef fun properties
(mclass
) do
641 var properties
= new HashSet[MVirtualTypeProp]
642 for mprop
in self.mmodule
.properties
(mclass
) do
643 if mprop
isa MVirtualTypeProp then properties
.add
(mprop
)
649 # Colorer for type resolution table
650 class ResolutionColorer
652 private var coloration_result
: Map[MType, Int] = new HashMap[MType, Int]
656 fun colorize
(elements
: Map[MClassType, Set[MType]]): Map[MType, Int] do
657 self.build_conflicts_graph
(elements
)
658 self.colorize_elements
(elements
)
659 return coloration_result
662 # Colorize a collection of elements
663 fun colorize_elements
(elements
: Map[MClassType, Set[MType]]) do
665 for mclasstype
, mclasstypes
in elements
do
666 for element
in mclasstypes
do
667 if self.coloration_result
.has_key
(element
) then continue
668 var color
= min_color
669 while not self.is_color_free
(element
, color
) do
672 coloration_result
[element
] = color
678 # Check if a related element to the element already use the color
679 private fun is_color_free
(element
: MType, color
: Int): Bool do
680 if conflicts_graph
.has_key
(element
) then
681 for st
in conflicts_graph
[element
] do
682 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
688 # look for unanchored types generated by the same type
689 private fun build_conflicts_graph
(elements
: Map[MClassType, Set[MType]]) do
690 for mclasstype
, mtypes
in elements
do
691 for mtype
in mtypes
do
692 for otype
in mtypes
do
693 if otype
== mtype
then continue
694 self.add_conflict
(mtype
, otype
)
700 private var conflicts_graph
: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
702 private fun add_conflict
(mtype
: MType, otype
: MType) do
703 if mtype
== otype
then return
704 if not self.conflicts_graph
.has_key
(mtype
) then self.conflicts_graph
[mtype
] = new HashSet[MType]
705 self.conflicts_graph
[mtype
].add
(otype
)
706 if not self.conflicts_graph
.has_key
(otype
) then self.conflicts_graph
[otype
] = new HashSet[MType]
707 self.conflicts_graph
[otype
].add
(mtype
)
711 # Perfect Hashing (PH)
713 # U = type of elements to hash
714 private class PerfectHasher[T
: Object, U
: Object]
716 var operator
: PHOperator
718 init(operator
: PHOperator) do self.operator
= operator
720 fun compute_masks
(conflicts
: Map[T
, Set[U
]], ids
: Map[U
, Int]): Map[T
, Int] do
721 var masks
= new HashMap[T
, Int]
722 for mclasstype
, mtypes
in conflicts
do
723 masks
[mclasstype
] = compute_mask
(mtypes
, ids
)
728 private fun compute_mask
(mtypes
: Set[U
], ids
: Map[U
, Int]): Int do
731 var used
= new List[Int]
732 for mtype
in mtypes
do
733 var res
= operator
.op
(mask
, ids
[mtype
])
734 if used
.has
(res
) then
740 if used
.length
== mtypes
.length
then break
746 fun compute_hashes
(elements
: Map[T
, Set[U
]], ids
: Map[U
, Int], masks
: Map[T
, Int]): Map[T
, Map[U
, Int]] do
747 var hashes
= new HashMap[T
, Map[U
, Int]]
748 for mclasstype
, mtypes
in elements
do
749 var mask
= masks
[mclasstype
]
750 var inhashes
= new HashMap[U
, Int]
751 for mtype
in mtypes
do
752 inhashes
[mtype
] = operator
.op
(mask
, ids
[mtype
])
754 hashes
[mclasstype
] = inhashes
760 # Abstract operator used for perfect hashing
761 abstract class PHOperator
762 fun op
(mask
: Int, id
:Int): Int is abstract
765 # Hashing using modulo (MOD) operator
770 redef fun op
(mask
, id
) do return mask
% id
773 # Hashing using binary and (AND) operator
778 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)