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 abstract class PropertyLayoutBuilder[E
: MProperty]
51 type LAYOUT: PropertyLayout[E
]
53 # Compute properties ids and position
54 fun build_layout
(mclasses
: Set[MClass]): LAYOUT is abstract
57 # Layout builder for MProperty using Coloring (CL)
58 class CLPropertyLayoutBuilder[E
: MProperty]
59 super PropertyLayoutBuilder[E
]
61 private var colorer
: MPropertyColorer[E
]
63 init(colorer
: MPropertyColorer[E
]) do
64 self.colorer
= colorer
67 # Compute mclasses ids and position using BM
68 redef fun build_layout
(mclasses
) do
69 var result
= new PropertyLayout[E
]
70 result
.pos
= self.colorer
.colorize
(mclasses
)
75 # Layout builder for MProperty using Perfect Hashing (PH)
76 # TODO implement this class without sublcassing CL builder
77 class PHPropertyLayoutBuilder[E
: MProperty]
78 super CLPropertyLayoutBuilder[E
]
81 abstract class ResolutionLayoutBuilder
82 type LAYOUT: Layout[MType]
84 fun build_layout
(elements
: Map[MClassType, Set[MType]]): LAYOUT is abstract
87 # Layout builder for MClass using Binary Matrix (BM)
88 class BMResolutionLayoutBuilder
89 super ResolutionLayoutBuilder
93 # Compute resolved types position using BM
94 redef fun build_layout
(elements
) do
95 var result
= new Layout[MType]
96 result
.ids
= self.compute_ids
(elements
)
97 result
.pos
= result
.ids
101 fun compute_ids
(elements
: Map[MClassType, Set[MType]]): Map[MType, Int] do
102 var ids
= new HashMap[MType, Int]
104 for mclasstype
, mclasstypes
in elements
do
105 for element
in mclasstypes
do
106 if ids
.has_key
(element
) then continue
115 # Layout builder for resolution tables using Coloring (CL)
116 class CLResolutionLayoutBuilder
117 super ResolutionLayoutBuilder
119 private var colorer
: ResolutionColorer = new ResolutionColorer
123 # Compute resolved types colors
124 redef fun build_layout
(elements
) do
125 var result
= new Layout[MType]
126 result
.ids
= self.compute_ids
(elements
)
127 result
.pos
= self.colorer
.colorize
(elements
)
131 fun compute_ids
(elements
: Map[MClassType, Set[MType]]): Map[MType, Int] do
132 var ids
= new HashMap[MType, Int]
134 for mclasstype
, mclasstypes
in elements
do
135 for element
in mclasstypes
do
136 if ids
.has_key
(element
) then continue
145 # Layout builder for resolution table using Perfect Hashing (PH)
146 class PHResolutionLayoutBuilder
147 super ResolutionLayoutBuilder
149 redef type LAYOUT: PHLayout[MClassType, MType]
151 private var hasher
: PerfectHasher[MClassType, MType]
153 init(operator
: PHOperator) do self.hasher
= new PerfectHasher[MClassType, MType](operator
)
155 # Compute resolved types masks and hashes
156 redef fun build_layout
(elements
) do
157 var result
= new PHLayout[MClassType, MType]
158 result
.ids
= self.compute_ids
(elements
)
159 result
.pos
= result
.ids
160 result
.masks
= self.hasher
.compute_masks
(elements
, result
.ids
)
161 result
.hashes
= self.hasher
.compute_hashes
(elements
, result
.ids
, result
.masks
)
165 fun compute_ids
(elements
: Map[MClassType, Set[MType]]): Map[MType, Int] do
166 var ids
= new HashMap[MType, Int]
168 for mclasstype
, mclasstypes
in elements
do
169 for element
in mclasstypes
do
170 if ids
.has_key
(element
) then continue
181 abstract class TypingBMizer[E
: Object]
182 super TypingLayoutBuilder[E
]
186 init(mmodule
: MModule) do
187 self.mmodule
= mmodule
190 # Compute mtypes ids and position using BM
191 redef fun build_layout
(elements
: Set[E
]): Layout[E
] do
192 var result
= new Layout[E
]
193 var ids
= new HashMap[E
, Int]
194 var lin
= self.reverse_linearize
(elements
)
195 for element
in lin
do
196 ids
[element
] = ids
.length
203 private fun reverse_linearize
(elements
: Set[E
]): Array[E
] is abstract
207 super TypingBMizer[MType]
209 init(mmodule
: MModule) do super(mmodule
)
211 redef fun reverse_linearize
(elements
) do
212 return self.mmodule
.reverse_linearize_mtypes
(elements
)
217 super TypingBMizer[MClass]
219 init(mmodule
: MModule) do super(mmodule
)
221 redef fun reverse_linearize
(elements
) do
222 return self.mmodule
.reverse_linearize_mclasses
(elements
)
228 abstract class TypingColorer[E
: Object]
229 super TypingLayoutBuilder[E
]
231 private var core
: Set[E
] = new HashSet[E
]
232 private var crown
: Set[E
] = new HashSet[E
]
233 private var border
: Set[E
] = new HashSet[E
]
235 private var coloration_result
: Map[E
, Int] = new HashMap[E
, Int]
239 # Compute the layout with coloring
240 redef fun build_layout
(elements
: Set[E
]): Layout[E
] do
241 var result
= new Layout[E
]
242 result
.ids
= compute_ids
(elements
)
243 result
.pos
= colorize
(elements
)
247 private fun compute_ids
(elements
: Set[E
]): Map[E
, Int] do
248 var ids
= new HashMap[E
, Int]
249 var lin
= reverse_linearize
(elements
)
250 for element
in lin
do
251 ids
[element
] = ids
.length
256 private fun colorize
(elements
: Set[E
]): Map[E
, Int] do
257 tag_elements
(elements
)
258 build_conflicts_graph
(elements
)
259 colorize_elements
(core
)
260 colorize_elements
(border
)
261 colorize_elements
(crown
)
262 return coloration_result
265 # Colorize a collection of elements
266 private fun colorize_elements
(elements
: Set[E
]) do
269 var lin
= reverse_linearize
(elements
)
270 for element
in lin
do
271 var color
= min_color
272 while not self.is_color_free
(element
, elements
, color
) do
275 coloration_result
[element
] = color
280 # Check if a related element to the element already use the color
281 private fun is_color_free
(element
: E
, elements
: Set[E
], color
: Int): Bool do
282 if conflicts_graph
.has_key
(element
) then
283 for st
in conflicts_graph
[element
] do
284 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
287 for st
in self.super_elements
(element
, elements
) do
288 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
293 # Tag elements as core, crown or border
294 private fun tag_elements
(elements
: Set[E
]) do
295 for element
in elements
do
296 # Check if sub elements are all in single inheritance
297 var all_subelements_si
= true
298 for subelem
in self.sub_elements
(element
, elements
) do
299 if self.is_element_mi
(subelem
, elements
) then
300 all_subelements_si
= false
305 # Tag as core, crown or border
306 if self.is_element_mi
(element
, elements
) then
307 core
.add_all
(self.super_elements
(element
, elements
))
309 if all_subelements_si
then
312 else if not all_subelements_si
then
313 core
.add_all
(self.super_elements
(element
, elements
))
321 # Conflicts graph of elements hierarchy (two types are in conflict if they have common subelements)
322 private fun build_conflicts_graph
(elements
: Set[E
]) do
323 self.conflicts_graph
= new HashMap[E
, HashSet[E
]]
324 var core
= reverse_linearize
(self.core
)
326 for i
in self.linear_extension
(t
, elements
) do
327 if t
== i
then continue
329 var lin_i
= self.linear_extension
(i
, elements
)
331 for j
in self.linear_extension
(t
, elements
) do
332 if i
== j
or j
== t
then continue
333 var lin_j
= self.linear_extension
(j
, elements
)
335 var d_ij
= lin_i
- lin_j
336 var d_ji
= lin_j
- lin_i
339 if not conflicts_graph
.has_key
(ed1
) then conflicts_graph
[ed1
] = new HashSet[E
]
340 # add ed1 x ed2 to conflicts graph
341 for ed2
in d_ji
do conflicts_graph
[ed1
].add
(ed2
)
344 if not conflicts_graph
.has_key
(ed1
) then conflicts_graph
[ed1
] = new HashSet[E
]
345 # add ed1 x ed2 to conflicts graph
346 for ed2
in d_ji
do conflicts_graph
[ed1
].add
(ed2
)
353 private var conflicts_graph
: nullable HashMap[E
, Set[E
]]
355 # cache for linear_extensions
356 private var linear_extensions_cache
: Map[E
, Array[E
]] = new HashMap[E
, Array[E
]]
358 # Return a linear_extension of super_elements of the element
359 private fun linear_extension
(element
: E
, elements
: Set[E
]): Array[E
] do
360 if not self.linear_extensions_cache
.has_key
(element
) then
361 var supers
= new HashSet[E
]
363 supers
.add_all
(self.super_elements
(element
, elements
))
364 self.linear_extensions_cache
[element
] = self.linearize
(supers
)
366 return self.linear_extensions_cache
[element
]
369 private fun super_elements
(element
: E
, elements
: Set[E
]): Set[E
] is abstract
370 private fun sub_elements
(element
: E
, elements
: Set[E
]): Set[E
] is abstract
371 private fun is_element_mi
(element
: E
, elements
: Set[E
]): Bool is abstract
372 private fun linearize
(elements
: Set[E
]): Array[E
] is abstract
373 private fun reverse_linearize
(elements
: Set[E
]): Array[E
] is abstract
378 super TypingColorer[MType]
382 init(mmodule
: MModule) do self.mmodule
= mmodule
384 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mtypes
(element
, elements
)
385 redef fun is_element_mi
(element
, elements
) do return self.super_elements
(element
, elements
).length
> 1
386 redef fun sub_elements
(element
, elements
) do do return self.mmodule
.sub_mtypes
(element
, elements
)
387 redef fun linearize
(elements
) do return self.mmodule
.linearize_mtypes
(elements
)
388 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mtypes
(elements
)
393 super TypingColorer[MClass]
395 private var mmodule
: MModule
397 init(mmodule
: MModule) do self.mmodule
= mmodule
399 redef fun super_elements
(element
, elements
) do return self.mmodule
.super_mclasses
(element
)
400 fun parent_elements
(element
: MClass): Set[MClass] do return self.mmodule
.parent_mclasses
(element
)
401 redef fun is_element_mi
(element
, elements
) do return self.parent_elements
(element
).length
> 1
402 redef fun sub_elements
(element
, elements
) do do return self.mmodule
.sub_mclasses
(element
)
403 redef fun linearize
(elements
) do return self.mmodule
.linearize_mclasses
(elements
)
404 redef fun reverse_linearize
(elements
) do return self.mmodule
.reverse_linearize_mclasses
(elements
)
408 abstract class MPropertyColorer[E
: MProperty]
410 private var mmodule
: MModule
411 private var class_colorer
: MClassColorer
412 private var coloration_result
: Map[E
, Int] = new HashMap[E
, Int]
414 init(mmodule
: MModule) do
415 self.mmodule
= mmodule
416 self.class_colorer
= new MClassColorer(mmodule
)
419 fun colorize
(mclasses
: Set[MClass]): Map[E
, Int] do
420 self.class_colorer
.tag_elements
(mclasses
)
421 self.class_colorer
.build_conflicts_graph
(mclasses
)
422 self.colorize_core
(self.class_colorer
.core
)
423 self.colorize_crown
(self.class_colorer
.crown
)
424 return self.coloration_result
427 # Colorize properties of the core hierarchy
428 private fun colorize_core
(mclasses
: Set[MClass]) do
430 for mclass
in mclasses
do
431 var color
= min_color
433 # if the class is root, get the minimal color
434 if self.mmodule
.parent_mclasses
(mclass
).length
== 0 then
435 colorize_elements
(self.properties
(mclass
), color
)
437 # check last color used by parents
438 color
= max_color
(color
, self.mmodule
.parent_mclasses
(mclass
))
439 # check max color used in conflicts
440 if self.class_colorer
.conflicts_graph
.has_key
(mclass
) then
441 color
= max_color
(color
, self.class_colorer
.conflicts_graph
[mclass
])
443 colorize_elements
(self.properties
(mclass
), color
)
448 # Colorize properties of the crown hierarchy
449 private fun colorize_crown
(mclasses
: Set[MClass]) do
450 for mclass
in mclasses
do
451 colorize_elements
(self.properties
(mclass
), max_color
(0, self.mmodule
.parent_mclasses
(mclass
)))
455 # Colorize a collection of mproperties given a starting color
456 private fun colorize_elements
(elements
: Collection[E
], start_color
: Int) do
457 for element
in elements
do
458 if self.coloration_result
.has_key
(element
) then continue
459 self.coloration_result
[element
] = start_color
464 private fun max_color
(min_color
: Int, mclasses
: Collection[MClass]): Int do
465 var max_color
= min_color
467 for mclass
in mclasses
do
468 for mproperty
in self.properties
(mclass
) do
469 var color
= min_color
470 if self.coloration_result
.has_key
(mproperty
) then
471 color
= self.coloration_result
[mproperty
]
472 if color
>= max_color
then max_color
= color
+ 1
480 private fun properties
(mclass
: MClass): Set[E
] is abstract
483 # Coloring for MMethods
485 super MPropertyColorer[MMethod]
487 init(mmodule
: MModule) do super
489 redef fun properties
(mclass
) do
490 var properties
= new HashSet[MMethod]
491 for mprop
in self.mmodule
.properties
(mclass
) do
492 if mprop
isa MMethod then properties
.add
(mprop
)
498 # Coloring for MMAttributes
499 class MAttributeColorer
500 super MPropertyColorer[MAttribute]
502 init(mmodule
: MModule) do super
504 redef fun properties
(mclass
) do
505 var properties
= new HashSet[MAttribute]
506 for mprop
in self.mmodule
.properties
(mclass
) do
507 if mprop
isa MAttribute then properties
.add
(mprop
)
513 # Coloring for MVirtualTypeProps
514 class MVirtualTypePropColorer
515 super MPropertyColorer[MVirtualTypeProp]
517 init(mmodule
: MModule) do super
519 redef fun properties
(mclass
) do
520 var properties
= new HashSet[MVirtualTypeProp]
521 for mprop
in self.mmodule
.properties
(mclass
) do
522 if mprop
isa MVirtualTypeProp then properties
.add
(mprop
)
528 # Colorer for type resolution table
529 class ResolutionColorer
531 private var coloration_result
: Map[MType, Int] = new HashMap[MType, Int]
535 fun colorize
(elements
: Map[MClassType, Set[MType]]): Map[MType, Int] do
536 self.build_conflicts_graph
(elements
)
537 self.colorize_elements
(elements
)
538 return coloration_result
541 # Colorize a collection of elements
542 fun colorize_elements
(elements
: Map[MClassType, Set[MType]]) do
544 for mclasstype
, mclasstypes
in elements
do
545 for element
in mclasstypes
do
546 if self.coloration_result
.has_key
(element
) then continue
547 var color
= min_color
548 while not self.is_color_free
(element
, color
) do
551 coloration_result
[element
] = color
557 # Check if a related element to the element already use the color
558 private fun is_color_free
(element
: MType, color
: Int): Bool do
559 if conflicts_graph
.has_key
(element
) then
560 for st
in conflicts_graph
[element
] do
561 if coloration_result
.has_key
(st
) and coloration_result
[st
] == color
then return false
567 # look for unanchored types generated by the same type
568 private fun build_conflicts_graph
(elements
: Map[MClassType, Set[MType]]) do
569 for mclasstype
, mtypes
in elements
do
570 for mtype
in mtypes
do
571 for otype
in mtypes
do
572 if otype
== mtype
then continue
573 self.add_conflict
(mtype
, otype
)
579 private var conflicts_graph
: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
581 private fun add_conflict
(mtype
: MType, otype
: MType) do
582 if mtype
== otype
then return
583 if not self.conflicts_graph
.has_key
(mtype
) then self.conflicts_graph
[mtype
] = new HashSet[MType]
584 self.conflicts_graph
[mtype
].add
(otype
)
585 if not self.conflicts_graph
.has_key
(otype
) then self.conflicts_graph
[otype
] = new HashSet[MType]
586 self.conflicts_graph
[otype
].add
(mtype
)
590 # Perfect Hashing (PH)
592 # U = type of elements to hash
593 private class PerfectHasher[T
: Object, U
: Object]
595 var operator
: PHOperator
597 init(operator
: PHOperator) do self.operator
= operator
599 fun compute_masks
(conflicts
: Map[T
, Set[U
]], ids
: Map[U
, Int]): Map[T
, Int] do
600 var masks
= new HashMap[T
, Int]
601 for mclasstype
, mtypes
in conflicts
do
602 masks
[mclasstype
] = compute_mask
(mtypes
, ids
)
607 private fun compute_mask
(mtypes
: Set[U
], ids
: Map[U
, Int]): Int do
610 var used
= new List[Int]
611 for mtype
in mtypes
do
612 var res
= operator
.op
(mask
, ids
[mtype
])
613 if used
.has
(res
) then
619 if used
.length
== mtypes
.length
then break
625 fun compute_hashes
(elements
: Map[T
, Set[U
]], ids
: Map[U
, Int], masks
: Map[T
, Int]): Map[T
, Map[U
, Int]] do
626 var hashes
= new HashMap[T
, Map[U
, Int]]
627 for mclasstype
, mtypes
in elements
do
628 var mask
= masks
[mclasstype
]
629 var inhashes
= new HashMap[U
, Int]
630 for mtype
in mtypes
do
631 inhashes
[mtype
] = operator
.op
(mask
, ids
[mtype
])
633 hashes
[mclasstype
] = inhashes
639 # Abstract operator used for perfect hashing
640 abstract class PHOperator
641 fun op
(mask
: Int, id
:Int): Int is abstract
644 # Hashing using modulo (MOD) operator
649 redef fun op
(mask
, id
) do return mask
% id
652 # Hashing using binary and (AND) operator
657 redef fun op
(mask
, id
) do return mask
.bin_and
(id
)
660 class TypingHasher[E
: Object]
661 super PerfectHasher[E
, E
]
662 super TypingLayoutBuilder[E
]
666 init(operator
: PHOperator, mmodule
: MModule) do
668 self.mmodule
= mmodule
671 redef fun build_layout
(elements
: Set[E
]): PHLayout[E
, E
] do
672 var result
= new PHLayout[E
, E
]
673 var conflicts
= self.build_conflicts
(elements
)
674 result
.ids
= self.compute_ids
(elements
)
675 result
.masks
= self.compute_masks
(conflicts
, result
.ids
)
676 result
.hashes
= self.compute_hashes
(conflicts
, result
.ids
, result
.masks
)
680 # Ids start from 1 instead of 0
681 private fun compute_ids
(elements
: Set[E
]): Map[E
, Int] do
682 var ids
= new HashMap[E
, Int]
683 var lin
= self.reverse_linearize
(elements
)
685 ids
[e
] = ids
.length
+ 1
690 private fun build_conflicts
(elements
: Set[E
]): Map[E
, Set[E
]] do
691 var conflicts
= new HashMap[E
, Set[E
]]
693 var supers
= self.super_elements
(e
, elements
)
695 conflicts
[e
] = supers
700 private fun super_elements
(element
: E
, elements
: Set[E
]): Set[E
] is abstract
701 private fun reverse_linearize
(elements
: Set[E
]): Array[E
] is abstract
705 super TypingHasher[MType]
707 init(operator
: PHOperator, mmodule
: MModule) do super(operator
, mmodule
)
709 redef fun super_elements
(element
, elements
) do
710 return self.mmodule
.super_mtypes
(element
, elements
)
713 redef fun reverse_linearize
(elements
) do
714 return self.mmodule
.reverse_linearize_mtypes
(elements
)
719 super TypingHasher[MClass]
721 init(operator
: PHOperator, mmodule
: MModule) do super(operator
, mmodule
)
723 redef fun super_elements
(element
, elements
) do
724 return self.mmodule
.super_mclasses
(element
)
727 redef fun reverse_linearize
(elements
) do
728 return self.mmodule
.reverse_linearize_mclasses
(elements
)