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 TypingLayout[E
: Object]
23 # Unic ids or each element
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 # Layout for resolution tables
43 class ResolutionLayout
44 # Unic ids for each resolved type
45 var ids
: Map[MType, Int] = new HashMap[MType, Int]
46 # Fixed positions of resolved type
47 var pos
: Map[MType, Int] = new HashMap[MType, Int]
50 class PHResolutionLayout
51 super ResolutionLayout
52 # Masks associated to each owner of a resolution table
53 var masks
: Map[MClassType, Int] = new HashMap[MClassType, Int]
54 # Positions of each resolvec type for resolution tables
55 var hashes
: Map[MClassType, Map[MType, Int]] = new HashMap[MClassType, Map[MType, Int]]
60 abstract class TypingLayoutBuilder[E
: Object]
62 type LAYOUT: TypingLayout[E
]
64 private var mmodule
: MModule
65 init(mmodule
: MModule) do self.mmodule
= mmodule
67 # Compute elements ids and position
68 fun build_layout
(elements
: Set[E
]): LAYOUT is abstract
70 # Give each MType a unic id using a descending linearization of the `mtypes` set
71 private fun compute_ids
(elements
: Set[E
]): Map[E
, Int] do
72 var ids
= new HashMap[E
, Int]
73 var lin
= self.reverse_linearize
(elements
)
75 ids
[element
] = ids
.length
80 private fun reverse_linearize
(elements
: Set[E
]): Array[E
] is abstract
83 # Layout builder for MType using Binary Matrix (BM)
84 class BMTypeLayoutBuilder
85 super TypingLayoutBuilder[MType]
87 init(mmodule
: MModule) do super
89 # Compute mtypes ids and position using BM
90 redef fun build_layout
(mtypes
) do
91 var result
= new TypingLayout[MType]
92 result
.ids
= self.compute_ids
(mtypes
)
93 result
.pos
= result
.ids
97 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mtypes
(elements
)
100 # Layout builder for MType using Coloring (CL)
101 class CLTypeLayoutBuilder
102 super TypingLayoutBuilder[MType]
104 private var colorer
: MTypeColorer
106 init(mmodule
: MModule) do
108 self.colorer
= new MTypeColorer(mmodule
)
111 # Compute mtypes ids and position using BM
112 redef fun build_layout
(mtypes
) do
113 var result
= new TypingLayout[MType]
114 result
.ids
= self.compute_ids
(mtypes
)
115 result
.pos
= self.colorer
.colorize
(mtypes
)
119 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mtypes
(elements
)
122 # Layout builder for MType using Perfect Hashing (PH)
123 class PHTypeLayoutBuilder
124 super TypingLayoutBuilder[MType]
126 redef type LAYOUT: PHTypingLayout[MType]
128 private var hasher
: PerfectHasher[MType, MType]
130 init(mmodule
: MModule, operator
: PHOperator) do
132 self.hasher
= new PerfectHasher[MType, MType](operator
)
135 private fun build_conflicts
(mtypes
: Set[MType]): Map[MType, Set[MType]] do
136 var conflicts
= new HashMap[MType, Set[MType]]
137 for mtype
in mtypes
do
138 var supers
= self.mmodule
.super_mtypes
(mtype
, mtypes
)
140 conflicts
[mtype
] = supers
145 # Compute mtypes ids and position using BM
146 redef fun build_layout
(mtypes
) do
147 var result
= new PHTypingLayout[MType]
148 var conflicts
= build_conflicts
(mtypes
)
149 result
.ids
= self.compute_ids
(mtypes
)
150 result
.masks
= self.hasher
.compute_masks
(conflicts
, result
.ids
)
151 result
.hashes
= self.hasher
.compute_hashes
(conflicts
, result
.ids
, result
.masks
)
155 # Ids start from 1 instead of 0
156 redef fun compute_ids
(mtypes
) do
157 var ids
= new HashMap[MType, Int]
158 var lin
= self.mmodule
.reverse_linearize_mtypes
(mtypes
)
160 ids
[mtype
] = ids
.length
+ 1
165 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mtypes
(elements
)
168 # Layout builder for MClass using Binary Matrix (BM)
169 class BMClassLayoutBuilder
170 super TypingLayoutBuilder[MClass]
172 init(mmodule
: MModule) do super
174 # Compute mclasses ids and position using BM
175 redef fun build_layout
(mclasses
) do
176 var result
= new TypingLayout[MClass]
177 result
.ids
= self.compute_ids
(mclasses
)
178 result
.pos
= result
.ids
182 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mclasses
(elements
)
185 # Layout builder for MClass using Coloring (CL)
186 class CLClassLayoutBuilder
187 super TypingLayoutBuilder[MClass]
189 private var colorer
: MClassColorer
191 init(mmodule
: MModule) do
193 self.colorer
= new MClassColorer(mmodule
)
196 # Compute mclasses ids and position using BM
197 redef fun build_layout
(mclasses
) do
198 var result
= new TypingLayout[MClass]
199 result
.ids
= self.compute_ids
(mclasses
)
200 result
.pos
= self.colorer
.colorize
(mclasses
)
204 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mclasses
(elements
)
207 # Layout builder for MClass using Perfect Hashing (PH)
208 class PHClassLayoutBuilder
209 super TypingLayoutBuilder[MClass]
211 redef type LAYOUT: PHTypingLayout[MClass]
213 private var hasher
: PerfectHasher[MClass, MClass]
215 init(mmodule
: MModule, operator
: PHOperator) do
217 self.hasher
= new PerfectHasher[MClass, MClass](operator
)
220 private fun build_conflicts
(mclasses
: Set[MClass]): Map[MClass, Set[MClass]] do
221 var conflicts
= new HashMap[MClass, Set[MClass]]
222 for mclass
in mclasses
do
223 var supers
= self.mmodule
.super_mclasses
(mclass
)
225 conflicts
[mclass
] = supers
230 # Compute mclasses ids and position using BM
231 redef fun build_layout
(mclasses
) do
232 var result
= new PHTypingLayout[MClass]
233 var conflicts
= build_conflicts
(mclasses
)
234 result
.ids
= self.compute_ids
(mclasses
)
235 result
.masks
= self.hasher
.compute_masks
(conflicts
, result
.ids
)
236 result
.hashes
= self.hasher
.compute_hashes
(conflicts
, result
.ids
, result
.masks
)
240 # Ids start from 1 instead of 0
241 redef fun compute_ids
(mclasses
) do
242 var ids
= new HashMap[MClass, Int]
243 var lin
= self.mmodule
.reverse_linearize_mclasses
(mclasses
)
245 ids
[mclass
] = ids
.length
+ 1
250 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mclasses
(elements
)
253 abstract class PropertyLayoutBuilder[E
: MProperty]
255 type LAYOUT: PropertyLayout[E
]
257 # Compute properties ids and position
258 fun build_layout
(mclasses
: Set[MClass]): LAYOUT is abstract
261 # Layout builder for MProperty using Coloring (CL)
262 class CLPropertyLayoutBuilder[E
: MProperty]
263 super PropertyLayoutBuilder[E
]
265 private var colorer
: MPropertyColorer[E
]
267 init(colorer
: MPropertyColorer[E
]) do
268 self.colorer
= colorer
271 # Compute mclasses ids and position using BM
272 redef fun build_layout
(mclasses
) do
273 var result
= new PropertyLayout[E
]
274 result
.pos
= self.colorer
.colorize
(mclasses
)
279 # Layout builder for MProperty using Perfect Hashing (PH)
280 # TODO implement this class without sublcassing CL builder
281 class PHPropertyLayoutBuilder[E
: MProperty]
282 super CLPropertyLayoutBuilder[E
]
285 abstract class ResolutionLayoutBuilder
287 type LAYOUT: ResolutionLayout
291 fun build_layout
(elements
: Map[MClassType, Set[MType]]): LAYOUT is abstract
293 fun compute_ids
(elements
: Map[MClassType, Set[MType]]): Map[MType, Int] do
294 var ids
= new HashMap[MType, Int]
296 for mclasstype
, mclasstypes
in elements
do
297 for element
in mclasstypes
do
298 if ids
.has_key
(element
) then continue
307 # Layout builder for MClass using Binary Matrix (BM)
308 class BMResolutionLayoutBuilder
309 super ResolutionLayoutBuilder
313 # Compute resolved types position using BM
314 redef fun build_layout
(elements
) do
315 var result
= new ResolutionLayout
316 result
.ids
= self.compute_ids
(elements
)
317 result
.pos
= result
.ids
322 # Layout builder for resolution tables using Coloring (CL)
323 class CLResolutionLayoutBuilder
324 super ResolutionLayoutBuilder
326 private var colorer
: ResolutionColorer = new ResolutionColorer
330 # Compute resolved types colors
331 redef fun build_layout
(elements
) do
332 var result
= new ResolutionLayout
333 result
.ids
= self.compute_ids
(elements
)
334 result
.pos
= self.colorer
.colorize
(elements
)
339 # Layout builder for resolution table using Perfect Hashing (PH)
340 class PHResolutionLayoutBuilder
341 super ResolutionLayoutBuilder
343 redef type LAYOUT: PHResolutionLayout
345 private var hasher
: PerfectHasher[MClassType, MType]
347 init(operator
: PHOperator) do self.hasher
= new PerfectHasher[MClassType, MType](operator
)
349 # Compute resolved types masks and hashes
350 redef fun build_layout
(elements
) do
351 var result
= new PHResolutionLayout
352 result
.ids
= self.compute_ids
(elements
)
353 result
.pos
= result
.ids
354 result
.masks
= self.hasher
.compute_masks
(elements
, result
.ids
)
355 result
.hashes
= self.hasher
.compute_hashes
(elements
, result
.ids
, result
.masks
)
359 redef fun compute_ids
(elements
) do
360 var ids
= new HashMap[MType, Int]
362 for mclasstype
, mclasstypes
in elements
do
363 for element
in mclasstypes
do
364 if ids
.has_key
(element
) then continue
375 abstract class AbstractColorer[E
: Object]
377 private var core
: Set[E
] = new HashSet[E
]
378 private var crown
: Set[E
] = new HashSet[E
]
379 private var border
: Set[E
] = new HashSet[E
]
381 private var coloration_result
: Map[E
, Int] = new HashMap[E
, Int]
385 fun colorize
(elements
: Set[E
]): Map[E
, Int] do
386 tag_elements
(elements
)
387 build_conflicts_graph
(elements
)
388 colorize_elements
(core
)
389 colorize_elements
(border
)
390 colorize_elements
(crown
)
391 return coloration_result
394 # Colorize a collection of elements
395 private fun colorize_elements
(elements
: Set[E
]) do
398 var lin
= reverse_linearize
(elements
)
399 for element
in lin
do
400 var color
= min_color
401 while not self.is_color_free
(element
, elements
, color
) do
404 coloration_result
[element
] = color
409 # Check if a related element to the element already use the color
410 private fun is_color_free
(element
: E
, elements
: Set[E
], color
: Int): Bool do
411 if conflicts_graph
.has_key
(element
) then
412 for st
in conflicts_graph
[element
] do
413 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
416 for st
in self.super_elements
(element
, elements
) do
417 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
422 # Tag elements as core, crown or border
423 private fun tag_elements
(elements
: Set[E
]) do
424 for element
in elements
do
425 # Check if sub elements are all in single inheritance
426 var all_subelements_si
= true
427 for subelem
in self.sub_elements
(element
, elements
) do
428 if self.is_element_mi
(subelem
, elements
) then
429 all_subelements_si
= false
434 # Tag as core, crown or border
435 if self.is_element_mi
(element
, elements
) then
436 core
.add_all
(self.super_elements
(element
, elements
))
438 if all_subelements_si
then
441 else if not all_subelements_si
then
442 core
.add_all
(self.super_elements
(element
, elements
))
450 # Conflicts graph of elements hierarchy (two types are in conflict if they have common subelements)
451 private fun build_conflicts_graph
(elements
: Set[E
]) do
452 self.conflicts_graph
= new HashMap[E
, HashSet[E
]]
453 var core
= reverse_linearize
(self.core
)
455 for i
in self.linear_extension
(t
, elements
) do
456 if t
== i
then continue
458 var lin_i
= self.linear_extension
(i
, elements
)
460 for j
in self.linear_extension
(t
, elements
) do
461 if i
== j
or j
== t
then continue
462 var lin_j
= self.linear_extension
(j
, elements
)
464 var d_ij
= lin_i
- lin_j
465 var d_ji
= lin_j
- lin_i
468 if not conflicts_graph
.has_key
(ed1
) then conflicts_graph
[ed1
] = new HashSet[E
]
469 # add ed1 x ed2 to conflicts graph
470 for ed2
in d_ji
do conflicts_graph
[ed1
].add
(ed2
)
473 if not conflicts_graph
.has_key
(ed1
) then conflicts_graph
[ed1
] = new HashSet[E
]
474 # add ed1 x ed2 to conflicts graph
475 for ed2
in d_ji
do conflicts_graph
[ed1
].add
(ed2
)
482 private var conflicts_graph
: nullable HashMap[E
, Set[E
]]
484 # cache for linear_extensions
485 private var linear_extensions_cache
: Map[E
, Array[E
]] = new HashMap[E
, Array[E
]]
487 # Return a linear_extension of super_elements of the element
488 private fun linear_extension
(element
: E
, elements
: Set[E
]): Array[E
] do
489 if not self.linear_extensions_cache
.has_key
(element
) then
490 var supers
= new HashSet[E
]
492 supers
.add_all
(self.super_elements
(element
, elements
))
493 self.linear_extensions_cache
[element
] = self.linearize
(supers
)
495 return self.linear_extensions_cache
[element
]
498 private fun super_elements
(element
: E
, elements
: Set[E
]): Set[E
] is abstract
499 private fun sub_elements
(element
: E
, elements
: Set[E
]): Set[E
] is abstract
500 private fun is_element_mi
(element
: E
, elements
: Set[E
]): Bool is abstract
501 private fun linearize
(elements
: Set[E
]): Array[E
] is abstract
502 private fun reverse_linearize
(elements
: Set[E
]): Array[E
] is abstract
506 private class MTypeColorer
507 super AbstractColorer[MType]
511 init(mmodule
: MModule) do self.mmodule
= mmodule
513 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mtypes
(element
, elements
)
514 redef fun is_element_mi
(element
, elements
) do return self.super_elements
(element
, elements
).length
> 1
515 redef fun sub_elements
(element
, elements
) do do return self.mmodule
.sub_mtypes
(element
, elements
)
516 redef fun linearize
(elements
) do return self.mmodule
.linearize_mtypes
(elements
)
517 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mtypes
(elements
)
521 private class MClassColorer
522 super AbstractColorer[MClass]
524 private var mmodule
: MModule
526 init(mmodule
: MModule) do self.mmodule
= mmodule
528 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mclasses
(element
)
529 fun parent_elements
(element
: MClass): Set[MClass] do return self.mmodule
.parent_mclasses
(element
)
530 redef fun is_element_mi
(element
, elements
) do return self.parent_elements
(element
).length
> 1
531 redef fun sub_elements
(element
, elements
) do do return self.mmodule
.sub_mclasses
(element
)
532 redef fun linearize
(elements
) do return self.mmodule
.linearize_mclasses
(elements
)
533 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mclasses
(elements
)
537 abstract class MPropertyColorer[E
: MProperty]
539 private var mmodule
: MModule
540 private var class_colorer
: MClassColorer
541 private var coloration_result
: Map[E
, Int] = new HashMap[E
, Int]
543 init(mmodule
: MModule) do
544 self.mmodule
= mmodule
545 self.class_colorer
= new MClassColorer(mmodule
)
548 fun colorize
(mclasses
: Set[MClass]): Map[E
, Int] do
549 self.class_colorer
.tag_elements
(mclasses
)
550 self.class_colorer
.build_conflicts_graph
(mclasses
)
551 self.colorize_core
(self.class_colorer
.core
)
552 self.colorize_crown
(self.class_colorer
.crown
)
553 return self.coloration_result
556 # Colorize properties of the core hierarchy
557 private fun colorize_core
(mclasses
: Set[MClass]) do
559 for mclass
in mclasses
do
560 var color
= min_color
562 # if the class is root, get the minimal color
563 if self.mmodule
.parent_mclasses
(mclass
).length
== 0 then
564 colorize_elements
(self.properties
(mclass
), color
)
566 # check last color used by parents
567 color
= max_color
(color
, self.mmodule
.parent_mclasses
(mclass
))
568 # check max color used in conflicts
569 if self.class_colorer
.conflicts_graph
.has_key
(mclass
) then
570 color
= max_color
(color
, self.class_colorer
.conflicts_graph
[mclass
])
572 colorize_elements
(self.properties
(mclass
), color
)
577 # Colorize properties of the crown hierarchy
578 private fun colorize_crown
(mclasses
: Set[MClass]) do
579 for mclass
in mclasses
do
580 colorize_elements
(self.properties
(mclass
), max_color
(0, self.mmodule
.parent_mclasses
(mclass
)))
584 # Colorize a collection of mproperties given a starting color
585 private fun colorize_elements
(elements
: Collection[E
], start_color
: Int) do
586 for element
in elements
do
587 if self.coloration_result
.has_key
(element
) then continue
588 self.coloration_result
[element
] = start_color
593 private fun max_color
(min_color
: Int, mclasses
: Collection[MClass]): Int do
594 var max_color
= min_color
596 for mclass
in mclasses
do
597 for mproperty
in self.properties
(mclass
) do
598 var color
= min_color
599 if self.coloration_result
.has_key
(mproperty
) then
600 color
= self.coloration_result
[mproperty
]
601 if color
>= max_color
then max_color
= color
+ 1
609 private fun properties
(mclass
: MClass): Set[E
] is abstract
612 # Coloring for MMethods
614 super MPropertyColorer[MMethod]
616 init(mmodule
: MModule) do super
618 redef fun properties
(mclass
) do
619 var properties
= new HashSet[MMethod]
620 for mprop
in self.mmodule
.properties
(mclass
) do
621 if mprop
isa MMethod then properties
.add
(mprop
)
627 # Coloring for MMAttributes
628 class MAttributeColorer
629 super MPropertyColorer[MAttribute]
631 init(mmodule
: MModule) do super
633 redef fun properties
(mclass
) do
634 var properties
= new HashSet[MAttribute]
635 for mprop
in self.mmodule
.properties
(mclass
) do
636 if mprop
isa MAttribute then properties
.add
(mprop
)
642 # Coloring for MVirtualTypeProps
643 class MVirtualTypePropColorer
644 super MPropertyColorer[MVirtualTypeProp]
646 init(mmodule
: MModule) do super
648 redef fun properties
(mclass
) do
649 var properties
= new HashSet[MVirtualTypeProp]
650 for mprop
in self.mmodule
.properties
(mclass
) do
651 if mprop
isa MVirtualTypeProp then properties
.add
(mprop
)
657 # Colorer for type resolution table
658 class ResolutionColorer
660 private var coloration_result
: Map[MType, Int] = new HashMap[MType, Int]
664 fun colorize
(elements
: Map[MClassType, Set[MType]]): Map[MType, Int] do
665 self.build_conflicts_graph
(elements
)
666 self.colorize_elements
(elements
)
667 return coloration_result
670 # Colorize a collection of elements
671 fun colorize_elements
(elements
: Map[MClassType, Set[MType]]) do
673 for mclasstype
, mclasstypes
in elements
do
674 for element
in mclasstypes
do
675 if self.coloration_result
.has_key
(element
) then continue
676 var color
= min_color
677 while not self.is_color_free
(element
, color
) do
680 coloration_result
[element
] = color
686 # Check if a related element to the element already use the color
687 private fun is_color_free
(element
: MType, color
: Int): Bool do
688 if conflicts_graph
.has_key
(element
) then
689 for st
in conflicts_graph
[element
] do
690 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
696 # look for unanchored types generated by the same type
697 private fun build_conflicts_graph
(elements
: Map[MClassType, Set[MType]]) do
698 for mclasstype
, mtypes
in elements
do
699 for mtype
in mtypes
do
700 for otype
in mtypes
do
701 if otype
== mtype
then continue
702 self.add_conflict
(mtype
, otype
)
708 private var conflicts_graph
: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
710 private fun add_conflict
(mtype
: MType, otype
: MType) do
711 if mtype
== otype
then return
712 if not self.conflicts_graph
.has_key
(mtype
) then self.conflicts_graph
[mtype
] = new HashSet[MType]
713 self.conflicts_graph
[mtype
].add
(otype
)
714 if not self.conflicts_graph
.has_key
(otype
) then self.conflicts_graph
[otype
] = new HashSet[MType]
715 self.conflicts_graph
[otype
].add
(mtype
)
719 # Perfect Hashing (PH)
721 # U = type of elements to hash
722 private class PerfectHasher[T
: Object, U
: Object]
724 var operator
: PHOperator
726 init(operator
: PHOperator) do self.operator
= operator
728 fun compute_masks
(conflicts
: Map[T
, Set[U
]], ids
: Map[U
, Int]): Map[T
, Int] do
729 var masks
= new HashMap[T
, Int]
730 for mclasstype
, mtypes
in conflicts
do
731 masks
[mclasstype
] = compute_mask
(mtypes
, ids
)
736 private fun compute_mask
(mtypes
: Set[U
], ids
: Map[U
, Int]): Int do
739 var used
= new List[Int]
740 for mtype
in mtypes
do
741 var res
= operator
.op
(mask
, ids
[mtype
])
742 if used
.has
(res
) then
748 if used
.length
== mtypes
.length
then break
754 fun compute_hashes
(elements
: Map[T
, Set[U
]], ids
: Map[U
, Int], masks
: Map[T
, Int]): Map[T
, Map[U
, Int]] do
755 var hashes
= new HashMap[T
, Map[U
, Int]]
756 for mclasstype
, mtypes
in elements
do
757 var mask
= masks
[mclasstype
]
758 var inhashes
= new HashMap[U
, Int]
759 for mtype
in mtypes
do
760 inhashes
[mtype
] = operator
.op
(mask
, ids
[mtype
])
762 hashes
[mclasstype
] = inhashes
768 # Abstract operator used for perfect hashing
769 abstract class PHOperator
770 fun op
(mask
: Int, id
:Int): Int is abstract
773 # Hashing using modulo (MOD) operator
778 redef fun op
(mask
, id
) do return mask
% id
781 # Hashing using binary and (AND) operator
786 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)