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 abstract class TypingLayoutBuilder[E
: Object]
46 type LAYOUT: Layout[E
]
48 private var mmodule
: MModule
49 init(mmodule
: MModule) do self.mmodule
= mmodule
51 # Compute elements ids and position
52 fun build_layout
(elements
: Set[E
]): LAYOUT is abstract
54 # Give each MType a unic id using a descending linearization of the `mtypes` set
55 private fun compute_ids
(elements
: Set[E
]): Map[E
, Int] do
56 var ids
= new HashMap[E
, Int]
57 var lin
= self.reverse_linearize
(elements
)
59 ids
[element
] = ids
.length
64 private fun reverse_linearize
(elements
: Set[E
]): Array[E
] is abstract
67 # Layout builder for MType using Binary Matrix (BM)
68 class BMTypeLayoutBuilder
69 super TypingLayoutBuilder[MType]
71 init(mmodule
: MModule) do super
73 # Compute mtypes ids and position using BM
74 redef fun build_layout
(mtypes
) do
75 var result
= new Layout[MType]
76 result
.ids
= self.compute_ids
(mtypes
)
77 result
.pos
= result
.ids
81 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mtypes
(elements
)
84 # Layout builder for MType using Coloring (CL)
85 class CLTypeLayoutBuilder
86 super TypingLayoutBuilder[MType]
88 private var colorer
: MTypeColorer
90 init(mmodule
: MModule) do
92 self.colorer
= new MTypeColorer(mmodule
)
95 # Compute mtypes ids and position using BM
96 redef fun build_layout
(mtypes
) do
97 var result
= new Layout[MType]
98 result
.ids
= self.compute_ids
(mtypes
)
99 result
.pos
= self.colorer
.colorize
(mtypes
)
103 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mtypes
(elements
)
106 # Layout builder for MType using Perfect Hashing (PH)
107 class PHTypeLayoutBuilder
108 super TypingLayoutBuilder[MType]
110 redef type LAYOUT: PHLayout[MType, MType]
112 private var hasher
: PerfectHasher[MType, MType]
114 init(mmodule
: MModule, operator
: PHOperator) do
116 self.hasher
= new PerfectHasher[MType, MType](operator
)
119 private fun build_conflicts
(mtypes
: Set[MType]): Map[MType, Set[MType]] do
120 var conflicts
= new HashMap[MType, Set[MType]]
121 for mtype
in mtypes
do
122 var supers
= self.mmodule
.super_mtypes
(mtype
, mtypes
)
124 conflicts
[mtype
] = supers
129 # Compute mtypes ids and position using BM
130 redef fun build_layout
(mtypes
) do
131 var result
= new PHLayout[MType, MType]
132 var conflicts
= build_conflicts
(mtypes
)
133 result
.ids
= self.compute_ids
(mtypes
)
134 result
.masks
= self.hasher
.compute_masks
(conflicts
, result
.ids
)
135 result
.hashes
= self.hasher
.compute_hashes
(conflicts
, result
.ids
, result
.masks
)
139 # Ids start from 1 instead of 0
140 redef fun compute_ids
(mtypes
) do
141 var ids
= new HashMap[MType, Int]
142 var lin
= self.mmodule
.reverse_linearize_mtypes
(mtypes
)
144 ids
[mtype
] = ids
.length
+ 1
149 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mtypes
(elements
)
152 # Layout builder for MClass using Binary Matrix (BM)
153 class BMClassLayoutBuilder
154 super TypingLayoutBuilder[MClass]
156 init(mmodule
: MModule) do super
158 # Compute mclasses ids and position using BM
159 redef fun build_layout
(mclasses
) do
160 var result
= new Layout[MClass]
161 result
.ids
= self.compute_ids
(mclasses
)
162 result
.pos
= result
.ids
166 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mclasses
(elements
)
169 # Layout builder for MClass using Coloring (CL)
170 class CLClassLayoutBuilder
171 super TypingLayoutBuilder[MClass]
173 private var colorer
: MClassColorer
175 init(mmodule
: MModule) do
177 self.colorer
= new MClassColorer(mmodule
)
180 # Compute mclasses ids and position using BM
181 redef fun build_layout
(mclasses
) do
182 var result
= new Layout[MClass]
183 result
.ids
= self.compute_ids
(mclasses
)
184 result
.pos
= self.colorer
.colorize
(mclasses
)
188 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mclasses
(elements
)
191 # Layout builder for MClass using Perfect Hashing (PH)
192 class PHClassLayoutBuilder
193 super TypingLayoutBuilder[MClass]
195 redef type LAYOUT: PHLayout[MClass, MClass]
197 private var hasher
: PerfectHasher[MClass, MClass]
199 init(mmodule
: MModule, operator
: PHOperator) do
201 self.hasher
= new PerfectHasher[MClass, MClass](operator
)
204 private fun build_conflicts
(mclasses
: Set[MClass]): Map[MClass, Set[MClass]] do
205 var conflicts
= new HashMap[MClass, Set[MClass]]
206 for mclass
in mclasses
do
207 var supers
= self.mmodule
.super_mclasses
(mclass
)
209 conflicts
[mclass
] = supers
214 # Compute mclasses ids and position using BM
215 redef fun build_layout
(mclasses
) do
216 var result
= new PHLayout[MClass, MClass]
217 var conflicts
= build_conflicts
(mclasses
)
218 result
.ids
= self.compute_ids
(mclasses
)
219 result
.masks
= self.hasher
.compute_masks
(conflicts
, result
.ids
)
220 result
.hashes
= self.hasher
.compute_hashes
(conflicts
, result
.ids
, result
.masks
)
224 # Ids start from 1 instead of 0
225 redef fun compute_ids
(mclasses
) do
226 var ids
= new HashMap[MClass, Int]
227 var lin
= self.mmodule
.reverse_linearize_mclasses
(mclasses
)
229 ids
[mclass
] = ids
.length
+ 1
234 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mclasses
(elements
)
237 abstract class PropertyLayoutBuilder[E
: MProperty]
239 type LAYOUT: PropertyLayout[E
]
241 # Compute properties ids and position
242 fun build_layout
(mclasses
: Set[MClass]): LAYOUT is abstract
245 # Layout builder for MProperty using Coloring (CL)
246 class CLPropertyLayoutBuilder[E
: MProperty]
247 super PropertyLayoutBuilder[E
]
249 private var colorer
: MPropertyColorer[E
]
251 init(colorer
: MPropertyColorer[E
]) do
252 self.colorer
= colorer
255 # Compute mclasses ids and position using BM
256 redef fun build_layout
(mclasses
) do
257 var result
= new PropertyLayout[E
]
258 result
.pos
= self.colorer
.colorize
(mclasses
)
263 # Layout builder for MProperty using Perfect Hashing (PH)
264 # TODO implement this class without sublcassing CL builder
265 class PHPropertyLayoutBuilder[E
: MProperty]
266 super CLPropertyLayoutBuilder[E
]
269 abstract class ResolutionLayoutBuilder
271 type LAYOUT: Layout[MType]
275 fun build_layout
(elements
: Map[MClassType, Set[MType]]): LAYOUT is abstract
277 fun compute_ids
(elements
: Map[MClassType, Set[MType]]): Map[MType, Int] do
278 var ids
= new HashMap[MType, Int]
280 for mclasstype
, mclasstypes
in elements
do
281 for element
in mclasstypes
do
282 if ids
.has_key
(element
) then continue
291 # Layout builder for MClass using Binary Matrix (BM)
292 class BMResolutionLayoutBuilder
293 super ResolutionLayoutBuilder
297 # Compute resolved types position using BM
298 redef fun build_layout
(elements
) do
299 var result
= new Layout[MType]
300 result
.ids
= self.compute_ids
(elements
)
301 result
.pos
= result
.ids
306 # Layout builder for resolution tables using Coloring (CL)
307 class CLResolutionLayoutBuilder
308 super ResolutionLayoutBuilder
310 private var colorer
: ResolutionColorer = new ResolutionColorer
314 # Compute resolved types colors
315 redef fun build_layout
(elements
) do
316 var result
= new Layout[MType]
317 result
.ids
= self.compute_ids
(elements
)
318 result
.pos
= self.colorer
.colorize
(elements
)
323 # Layout builder for resolution table using Perfect Hashing (PH)
324 class PHResolutionLayoutBuilder
325 super ResolutionLayoutBuilder
327 redef type LAYOUT: PHLayout[MClassType, MType]
329 private var hasher
: PerfectHasher[MClassType, MType]
331 init(operator
: PHOperator) do self.hasher
= new PerfectHasher[MClassType, MType](operator
)
333 # Compute resolved types masks and hashes
334 redef fun build_layout
(elements
) do
335 var result
= new PHLayout[MClassType, MType]
336 result
.ids
= self.compute_ids
(elements
)
337 result
.pos
= result
.ids
338 result
.masks
= self.hasher
.compute_masks
(elements
, result
.ids
)
339 result
.hashes
= self.hasher
.compute_hashes
(elements
, result
.ids
, result
.masks
)
343 redef fun compute_ids
(elements
) do
344 var ids
= new HashMap[MType, Int]
346 for mclasstype
, mclasstypes
in elements
do
347 for element
in mclasstypes
do
348 if ids
.has_key
(element
) then continue
359 abstract class AbstractColorer[E
: Object]
361 private var core
: Set[E
] = new HashSet[E
]
362 private var crown
: Set[E
] = new HashSet[E
]
363 private var border
: Set[E
] = new HashSet[E
]
365 private var coloration_result
: Map[E
, Int] = new HashMap[E
, Int]
369 fun colorize
(elements
: Set[E
]): Map[E
, Int] do
370 tag_elements
(elements
)
371 build_conflicts_graph
(elements
)
372 colorize_elements
(core
)
373 colorize_elements
(border
)
374 colorize_elements
(crown
)
375 return coloration_result
378 # Colorize a collection of elements
379 private fun colorize_elements
(elements
: Set[E
]) do
382 var lin
= reverse_linearize
(elements
)
383 for element
in lin
do
384 var color
= min_color
385 while not self.is_color_free
(element
, elements
, color
) do
388 coloration_result
[element
] = color
393 # Check if a related element to the element already use the color
394 private fun is_color_free
(element
: E
, elements
: Set[E
], color
: Int): Bool do
395 if conflicts_graph
.has_key
(element
) then
396 for st
in conflicts_graph
[element
] do
397 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
400 for st
in self.super_elements
(element
, elements
) do
401 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
406 # Tag elements as core, crown or border
407 private fun tag_elements
(elements
: Set[E
]) do
408 for element
in elements
do
409 # Check if sub elements are all in single inheritance
410 var all_subelements_si
= true
411 for subelem
in self.sub_elements
(element
, elements
) do
412 if self.is_element_mi
(subelem
, elements
) then
413 all_subelements_si
= false
418 # Tag as core, crown or border
419 if self.is_element_mi
(element
, elements
) then
420 core
.add_all
(self.super_elements
(element
, elements
))
422 if all_subelements_si
then
425 else if not all_subelements_si
then
426 core
.add_all
(self.super_elements
(element
, elements
))
434 # Conflicts graph of elements hierarchy (two types are in conflict if they have common subelements)
435 private fun build_conflicts_graph
(elements
: Set[E
]) do
436 self.conflicts_graph
= new HashMap[E
, HashSet[E
]]
437 var core
= reverse_linearize
(self.core
)
439 for i
in self.linear_extension
(t
, elements
) do
440 if t
== i
then continue
442 var lin_i
= self.linear_extension
(i
, elements
)
444 for j
in self.linear_extension
(t
, elements
) do
445 if i
== j
or j
== t
then continue
446 var lin_j
= self.linear_extension
(j
, elements
)
448 var d_ij
= lin_i
- lin_j
449 var d_ji
= lin_j
- lin_i
452 if not conflicts_graph
.has_key
(ed1
) then conflicts_graph
[ed1
] = new HashSet[E
]
453 # add ed1 x ed2 to conflicts graph
454 for ed2
in d_ji
do conflicts_graph
[ed1
].add
(ed2
)
457 if not conflicts_graph
.has_key
(ed1
) then conflicts_graph
[ed1
] = new HashSet[E
]
458 # add ed1 x ed2 to conflicts graph
459 for ed2
in d_ji
do conflicts_graph
[ed1
].add
(ed2
)
466 private var conflicts_graph
: nullable HashMap[E
, Set[E
]]
468 # cache for linear_extensions
469 private var linear_extensions_cache
: Map[E
, Array[E
]] = new HashMap[E
, Array[E
]]
471 # Return a linear_extension of super_elements of the element
472 private fun linear_extension
(element
: E
, elements
: Set[E
]): Array[E
] do
473 if not self.linear_extensions_cache
.has_key
(element
) then
474 var supers
= new HashSet[E
]
476 supers
.add_all
(self.super_elements
(element
, elements
))
477 self.linear_extensions_cache
[element
] = self.linearize
(supers
)
479 return self.linear_extensions_cache
[element
]
482 private fun super_elements
(element
: E
, elements
: Set[E
]): Set[E
] is abstract
483 private fun sub_elements
(element
: E
, elements
: Set[E
]): Set[E
] is abstract
484 private fun is_element_mi
(element
: E
, elements
: Set[E
]): Bool is abstract
485 private fun linearize
(elements
: Set[E
]): Array[E
] is abstract
486 private fun reverse_linearize
(elements
: Set[E
]): Array[E
] is abstract
490 private class MTypeColorer
491 super AbstractColorer[MType]
495 init(mmodule
: MModule) do self.mmodule
= mmodule
497 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mtypes
(element
, elements
)
498 redef fun is_element_mi
(element
, elements
) do return self.super_elements
(element
, elements
).length
> 1
499 redef fun sub_elements
(element
, elements
) do do return self.mmodule
.sub_mtypes
(element
, elements
)
500 redef fun linearize
(elements
) do return self.mmodule
.linearize_mtypes
(elements
)
501 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mtypes
(elements
)
505 private class MClassColorer
506 super AbstractColorer[MClass]
508 private var mmodule
: MModule
510 init(mmodule
: MModule) do self.mmodule
= mmodule
512 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mclasses
(element
)
513 fun parent_elements
(element
: MClass): Set[MClass] do return self.mmodule
.parent_mclasses
(element
)
514 redef fun is_element_mi
(element
, elements
) do return self.parent_elements
(element
).length
> 1
515 redef fun sub_elements
(element
, elements
) do do return self.mmodule
.sub_mclasses
(element
)
516 redef fun linearize
(elements
) do return self.mmodule
.linearize_mclasses
(elements
)
517 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mclasses
(elements
)
521 abstract class MPropertyColorer[E
: MProperty]
523 private var mmodule
: MModule
524 private var class_colorer
: MClassColorer
525 private var coloration_result
: Map[E
, Int] = new HashMap[E
, Int]
527 init(mmodule
: MModule) do
528 self.mmodule
= mmodule
529 self.class_colorer
= new MClassColorer(mmodule
)
532 fun colorize
(mclasses
: Set[MClass]): Map[E
, Int] do
533 self.class_colorer
.tag_elements
(mclasses
)
534 self.class_colorer
.build_conflicts_graph
(mclasses
)
535 self.colorize_core
(self.class_colorer
.core
)
536 self.colorize_crown
(self.class_colorer
.crown
)
537 return self.coloration_result
540 # Colorize properties of the core hierarchy
541 private fun colorize_core
(mclasses
: Set[MClass]) do
543 for mclass
in mclasses
do
544 var color
= min_color
546 # if the class is root, get the minimal color
547 if self.mmodule
.parent_mclasses
(mclass
).length
== 0 then
548 colorize_elements
(self.properties
(mclass
), color
)
550 # check last color used by parents
551 color
= max_color
(color
, self.mmodule
.parent_mclasses
(mclass
))
552 # check max color used in conflicts
553 if self.class_colorer
.conflicts_graph
.has_key
(mclass
) then
554 color
= max_color
(color
, self.class_colorer
.conflicts_graph
[mclass
])
556 colorize_elements
(self.properties
(mclass
), color
)
561 # Colorize properties of the crown hierarchy
562 private fun colorize_crown
(mclasses
: Set[MClass]) do
563 for mclass
in mclasses
do
564 colorize_elements
(self.properties
(mclass
), max_color
(0, self.mmodule
.parent_mclasses
(mclass
)))
568 # Colorize a collection of mproperties given a starting color
569 private fun colorize_elements
(elements
: Collection[E
], start_color
: Int) do
570 for element
in elements
do
571 if self.coloration_result
.has_key
(element
) then continue
572 self.coloration_result
[element
] = start_color
577 private fun max_color
(min_color
: Int, mclasses
: Collection[MClass]): Int do
578 var max_color
= min_color
580 for mclass
in mclasses
do
581 for mproperty
in self.properties
(mclass
) do
582 var color
= min_color
583 if self.coloration_result
.has_key
(mproperty
) then
584 color
= self.coloration_result
[mproperty
]
585 if color
>= max_color
then max_color
= color
+ 1
593 private fun properties
(mclass
: MClass): Set[E
] is abstract
596 # Coloring for MMethods
598 super MPropertyColorer[MMethod]
600 init(mmodule
: MModule) do super
602 redef fun properties
(mclass
) do
603 var properties
= new HashSet[MMethod]
604 for mprop
in self.mmodule
.properties
(mclass
) do
605 if mprop
isa MMethod then properties
.add
(mprop
)
611 # Coloring for MMAttributes
612 class MAttributeColorer
613 super MPropertyColorer[MAttribute]
615 init(mmodule
: MModule) do super
617 redef fun properties
(mclass
) do
618 var properties
= new HashSet[MAttribute]
619 for mprop
in self.mmodule
.properties
(mclass
) do
620 if mprop
isa MAttribute then properties
.add
(mprop
)
626 # Coloring for MVirtualTypeProps
627 class MVirtualTypePropColorer
628 super MPropertyColorer[MVirtualTypeProp]
630 init(mmodule
: MModule) do super
632 redef fun properties
(mclass
) do
633 var properties
= new HashSet[MVirtualTypeProp]
634 for mprop
in self.mmodule
.properties
(mclass
) do
635 if mprop
isa MVirtualTypeProp then properties
.add
(mprop
)
641 # Colorer for type resolution table
642 class ResolutionColorer
644 private var coloration_result
: Map[MType, Int] = new HashMap[MType, Int]
648 fun colorize
(elements
: Map[MClassType, Set[MType]]): Map[MType, Int] do
649 self.build_conflicts_graph
(elements
)
650 self.colorize_elements
(elements
)
651 return coloration_result
654 # Colorize a collection of elements
655 fun colorize_elements
(elements
: Map[MClassType, Set[MType]]) do
657 for mclasstype
, mclasstypes
in elements
do
658 for element
in mclasstypes
do
659 if self.coloration_result
.has_key
(element
) then continue
660 var color
= min_color
661 while not self.is_color_free
(element
, color
) do
664 coloration_result
[element
] = color
670 # Check if a related element to the element already use the color
671 private fun is_color_free
(element
: MType, color
: Int): Bool do
672 if conflicts_graph
.has_key
(element
) then
673 for st
in conflicts_graph
[element
] do
674 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
680 # look for unanchored types generated by the same type
681 private fun build_conflicts_graph
(elements
: Map[MClassType, Set[MType]]) do
682 for mclasstype
, mtypes
in elements
do
683 for mtype
in mtypes
do
684 for otype
in mtypes
do
685 if otype
== mtype
then continue
686 self.add_conflict
(mtype
, otype
)
692 private var conflicts_graph
: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
694 private fun add_conflict
(mtype
: MType, otype
: MType) do
695 if mtype
== otype
then return
696 if not self.conflicts_graph
.has_key
(mtype
) then self.conflicts_graph
[mtype
] = new HashSet[MType]
697 self.conflicts_graph
[mtype
].add
(otype
)
698 if not self.conflicts_graph
.has_key
(otype
) then self.conflicts_graph
[otype
] = new HashSet[MType]
699 self.conflicts_graph
[otype
].add
(mtype
)
703 # Perfect Hashing (PH)
705 # U = type of elements to hash
706 private class PerfectHasher[T
: Object, U
: Object]
708 var operator
: PHOperator
710 init(operator
: PHOperator) do self.operator
= operator
712 fun compute_masks
(conflicts
: Map[T
, Set[U
]], ids
: Map[U
, Int]): Map[T
, Int] do
713 var masks
= new HashMap[T
, Int]
714 for mclasstype
, mtypes
in conflicts
do
715 masks
[mclasstype
] = compute_mask
(mtypes
, ids
)
720 private fun compute_mask
(mtypes
: Set[U
], ids
: Map[U
, Int]): Int do
723 var used
= new List[Int]
724 for mtype
in mtypes
do
725 var res
= operator
.op
(mask
, ids
[mtype
])
726 if used
.has
(res
) then
732 if used
.length
== mtypes
.length
then break
738 fun compute_hashes
(elements
: Map[T
, Set[U
]], ids
: Map[U
, Int], masks
: Map[T
, Int]): Map[T
, Map[U
, Int]] do
739 var hashes
= new HashMap[T
, Map[U
, Int]]
740 for mclasstype
, mtypes
in elements
do
741 var mask
= masks
[mclasstype
]
742 var inhashes
= new HashMap[U
, Int]
743 for mtype
in mtypes
do
744 inhashes
[mtype
] = operator
.op
(mask
, ids
[mtype
])
746 hashes
[mclasstype
] = inhashes
752 # Abstract operator used for perfect hashing
753 abstract class PHOperator
754 fun op
(mask
: Int, id
:Int): Int is abstract
757 # Hashing using modulo (MOD) operator
762 redef fun op
(mask
, id
) do return mask
% id
765 # Hashing using binary and (AND) operator
770 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)