1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # Copyright 2012 Alexandre Terrasa <alexandre@moz-concept.com>
5 # Licensed under the Apache License, Version 2.0 (the "License");
6 # you may not use this file except in compliance with the License.
7 # You may obtain a copy of the License at
9 # http://www.apache.org/licenses/LICENSE-2.0
11 # Unless required by applicable law or agreed to in writing, software
12 # distributed under the License is distributed on an "AS IS" BASIS,
13 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 # See the License for the specific language governing permissions and
15 # limitations under the License.
17 # Introduce incremental typing in naive interpreter
19 # * Legacy: default mode, using request to precomputed metamodel
22 # * PHAND: perfect hashing using binary AND
23 # * PHMOD: perfect hashing using modulo
24 module interpretor_type_test
26 intrude import naive_interpreter
28 # Add options for incremental typing
29 redef class ToolContext
30 # --ic-typing-mode BM | CL | PHMOD | PHAND
31 var opt_ic_typing_mode
= new OptionString("Incremental typing method. Possible values are:\n\t\t\t\t - BM: binary matrix\n\t\t\t\t - CL: coloration\n\t\t\t\t - PHAND: perfect hashing whith AND\n\t\t\t\t - PHMOD: perfect hashing whith MOD", "--ic-typing-mode")
33 var opt_ic_load_mode
= new OptionString("Dynamic loading mode. Possible values are:\n\t\t\t\t - type (default): load only the new type\n\t\t\t\t - module: load the module of new type", "--ic-load-mode")
35 var opt_ic_bootstrap
= new OptionBool("Bootstrap typing with standard library (default is no bootstrap)", "--ic-bootstrap")
36 # --ic-recompute-mode always | never | threshold | increment
37 var opt_ic_recompute_mode
= new OptionString("When to recompute typing. Possible values are:\n\t\t\t\t - always: recompute for each new type\n\t\t\t\t - never (default): never recompute, use fallback instead\n\t\t\t\t - threshold: recompute only when the threshold is reached, use fallback before\n\t\t\t\t - increment: try to update structures instead of recompute", "--ic-recompute-mode")
38 # --ic-threshold-mode increment | fallback
39 var opt_ic_threshold_mode
= new OptionString("Threshold mode. Possible values are:\n\t\t\t\t - increment: recompute when the number of new type reach the threshold count\n\t\t\t\t -fallback: recompute when the use number of fallback use reach the threshold count", "--ic-threshold-mode")
40 # --ic-threshold-count <int>
41 var opt_ic_threshold_count
= new OptionInt("Threshold count. Take an integer", 0, "--ic-threshold-count")
42 # --ic-cache-size <int>
43 var opt_ic_cache_size
= new OptionInt("Cache size. Take an integer", 0, "--ic-cache-size")
45 var opt_ic_show_stats
= new OptionBool("Show statistics about typing at the end of the interpretation", "--ic-show-stats")
50 self.option_context
.add_option
(self.opt_ic_typing_mode
)
51 self.option_context
.add_option
(self.opt_ic_load_mode
)
52 self.option_context
.add_option
(self.opt_ic_bootstrap
)
53 self.option_context
.add_option
(self.opt_ic_recompute_mode
)
54 self.option_context
.add_option
(self.opt_ic_threshold_mode
)
55 self.option_context
.add_option
(self.opt_ic_threshold_count
)
56 self.option_context
.add_option
(self.opt_ic_cache_size
)
57 self.option_context
.add_option
(self.opt_ic_show_stats
)
61 redef class ModelBuilder
62 # Add statistics display at the end of the interpretation
63 redef fun run_naive_interpreter
(mainmodule
, arguments
) do
65 self.toolcontext
.info
("*** START INTERPRETING ***", 1)
67 var interpreter
= new NaiveInterpreter(self, mainmodule
, arguments
)
68 init_naive_interpreter
(interpreter
, mainmodule
)
71 if interpreter
.show_stats
then
72 print
"# Interpretation statistics"
74 print
"## Dynamic loading"
75 print
" - nb dynamically lodaed types: {interpreter.typing.nb_loads} ({interpreter.typing.nb_gen_loads} were generic)"
76 print
" - nb dynamically lodaed modules: {interpreter.typing.nb_mod_loads}"
78 print
"## Typing structures"
79 print
" - nb increments: {interpreter.typing.nb_increment_loads} ({interpreter.typing.nb_gen_increment_loads} were generic)"
80 print
" - nb destructive increments: {interpreter.typing.nb_destructive_increments} ({interpreter.typing.nb_gen_destructive_increments} were generic)"
81 print
" - nb full structure recomputation: {interpreter.typing.nb_recomputes}"
82 print
" - overall max size table: {interpreter.typing.max_size_tables}"
83 print
" - total: size needed for tables: {interpreter.typing.sum_size_tables}"
86 print
" - nb isa: {interpreter.typing.nb_isas} ({interpreter.typing.nb_gen_isas} involving generic types)"
87 print
" - nb isa using fallback: {interpreter.typing.nb_fallbacks} ({interpreter.typing.nb_gen_fallbacks} involving generic types)"
88 print
" - nb isa using fallback responded from cache: {interpreter.typing.nb_cache_res}"
92 self.toolcontext
.info
("*** END INTERPRETING: {time1-time0} ***", 2)
96 # Add gestion handling for incremental typing mecanisms
97 redef class NaiveInterpreter
100 var module_increment
: Bool
101 var recompute_mode
: String
102 var threshold_mode
: String = "null"
103 var threshold_count
: Int = 0
104 var cache_size
: Int = 0
105 var show_stats
: Bool = false
107 # Add option handling
108 redef init(modelbuilder
, mainmodule
, arguments
) do
109 super(modelbuilder
, mainmodule
, arguments
)
111 # choose typing method
112 var mode
= modelbuilder
.toolcontext
.opt_ic_typing_mode
.value
114 self.modelbuilder
.toolcontext
.info
("IC-TYPING: Using BM typing", 1)
115 typing
= new BMTyping(self)
116 else if mode
== "CL" then
117 self.modelbuilder
.toolcontext
.info
("IC-TYPING: Using CL typing", 1)
118 typing
= new CLTyping(self)
119 else if mode
== "PHMOD" then
120 self.modelbuilder
.toolcontext
.info
("IC-TYPING: Using PH-MOD typing", 1)
121 typing
= new PHModTyping(self)
122 else if mode
== "PHAND" then
123 self.modelbuilder
.toolcontext
.info
("IC-TYPING: Using PH-AND typing", 1)
124 typing
= new PHAndTyping(self)
126 self.modelbuilder
.toolcontext
.info
("IC-TYPING: Using legacy typing", 1)
127 typing
= new LegacyTyping(self)
130 # load full module or juste the type ?
131 mode
= modelbuilder
.toolcontext
.opt_ic_load_mode
.value
132 if mode
== "module" then
133 self.modelbuilder
.toolcontext
.info
("IC-TYPING: Using load mode: module", 1)
134 module_increment
= true
136 self.modelbuilder
.toolcontext
.info
("IC-TYPING: Using load mode: type", 1)
137 module_increment
= false
140 # bootstrap type structures with stdlib types
141 if modelbuilder
.toolcontext
.opt_ic_bootstrap
.value
then
142 self.modelbuilder
.toolcontext
.info
("IC-TYPING: Using bootstrap", 1)
146 # typing recomputation mode
147 var recompute_mode
= modelbuilder
.toolcontext
.opt_ic_recompute_mode
.value
148 if recompute_mode
!= null then
149 self.recompute_mode
= recompute_mode
151 if recompute_mode
== "threshold" then
152 var threshold_mode
= modelbuilder
.toolcontext
.opt_ic_threshold_mode
.value
153 if threshold_mode
== null then
154 print
"IC-ERROR : Recompute mode 'threshold' need a threshold mode"
157 self.modelbuilder
.toolcontext
.info
("IC-TYPING: Using threshold mode: {threshold_mode}", 1)
158 self.threshold_mode
= threshold_mode
159 var threshold_count
= modelbuilder
.toolcontext
.opt_ic_threshold_count
.value
160 if threshold_count
== 0 then
161 print
"IC-ERROR : Recompute mode 'threshold' need a threshold count"
164 self.threshold_count
= threshold_count
165 self.modelbuilder
.toolcontext
.info
("IC-TYPING: Using threshold value: {threshold_count}", 1)
170 self.recompute_mode
= "never"
172 self.modelbuilder
.toolcontext
.info
("IC-TYPING: Using recompute mode: {self.recompute_mode}", 1)
175 cache_size
= modelbuilder
.toolcontext
.opt_ic_cache_size
.value
176 self.modelbuilder
.toolcontext
.info
("IC-TYPING: Using cache size: {cache_size}", 1)
179 if modelbuilder
.toolcontext
.opt_ic_show_stats
.value
then show_stats
= true
182 # Handle subtypes tests and redispatch to selected mode
183 redef fun is_subtype
(sub
, sup
) do
184 self.modelbuilder
.toolcontext
.info
("IC-TYPING[DEBUG]: {sub} ISA {sup}", 2)
188 if sup
isa MGenericType or sub
isa MGenericType then typing
.nb_gen_isas
+= 1
190 # special case of nullables types
191 if sub
isa MNullType and sup
isa MNullableType then
193 else if sub
isa MNullType and not sup
isa MNullableType then
196 if sub
isa MNullableType then sub
= sub
.mtype
197 if sup
isa MNullableType then sup
= sup
.mtype
200 var t1
= typing
.load_increment
(sub
.as(MClassType))
201 var t2
= typing
.load_increment
(sup
.as(MClassType))
204 if typing
.is_valid
then
205 res
= t1
.is_subtype
(t2
)
207 # recompute mode = thresold
208 if recompute_mode
== "threshold" then
209 if threshold_mode
== "fallback" then
210 typing
.increment_count
+= 1
211 # recompute instead fallback
212 if typing
.increment_count
> threshold_count
then
213 typing
.compute_typing
214 typing
.increment_count
= 0
215 return t1
.is_subtype
(t2
)
219 res
= t1
.is_subtype_fallback
(t2
)
227 # The base of incremental typing
228 private abstract class Typing
231 # List of already loaded types
232 var loaded_types
: HashMap[MType, T
] = new HashMap[MType, T
]
233 # List of already loaded modules
234 var loaded_modules
: HashSet[MModule] = new HashSet[MModule]
237 # Is the typing still valid (no destructive increment)
238 var is_valid
: Bool = false
239 # Increment count since the last full recomputation
240 var increment_count
= 0
242 private var interpreter
: NaiveInterpreter
248 var nb_increment_loads
= 0
249 var nb_gen_increment_loads
= 0
250 var nb_destructive_increments
= 0
251 var nb_gen_destructive_increments
= 0
254 var nb_recomputes
= 0
256 var nb_gen_fallbacks
= 0
258 var max_size_tables
= 0
259 var sum_size_tables
= 0
261 private init(interpreter
: NaiveInterpreter) do
262 self.interpreter
= interpreter
265 # Load the std lib types and compute typing
267 interpreter
.modelbuilder
.toolcontext
.info
("IC-TYPING[DEBUG]: bootstrap start", 2)
268 var mods
= interpreter
.mainmodule
.model
.get_mmodules_by_name
("standard")
271 for m
in std
.in_nesting
.direct_greaters
do
276 interpreter
.modelbuilder
.toolcontext
.info
("IC-TYPING[DEBUG]: bootstrap end", 2)
279 # Load all types contained in a module
280 fun load_module
(mmodule
: MModule) do
281 interpreter
.modelbuilder
.toolcontext
.info
("IC-TYPING[DEBUG]: load module {mmodule}", 2)
282 # import nested module first
283 for m
in mmodule
.in_nesting
.greaters
do
284 if mmodule
== m
then continue
288 # load classes in module
289 if loaded_modules
.has
(mmodule
) then return
294 for c
in mmodule
.intro_mclasses
do
295 # skip unanchored types (they will be handled by load_supertypes of anchored types
296 if c
.mclass_type
.need_anchor
then continue
297 load_type
(c
.mclass_type
)
299 loaded_modules
.add
(mmodule
)
302 # Load a MType and return its Type representation
303 fun load_type
(mtype
: MClassType): T
do
304 if is_loaded
(mtype
) then
305 return loaded_types
[mtype
]
309 if mtype
isa MGenericType then nb_gen_loads
+= 1
311 var supertypes
= load_supertypes
(mtype
)
312 var t
= init_type
(lastID
+ 1, mtype
, supertypes
, self)
314 loaded_types
[mtype
] = t
316 # load formal parameter types
317 if mtype
isa MGenericType then
318 for arg
in mtype
.arguments
do
319 if arg
isa MClassType then load_type
(arg
)
327 # Load compile time known super-types of a type
328 # supertypes are all known super classes at compile time and unresolved generic classes
329 fun load_supertypes
(child
: MClassType): Array[T
] do
330 var parents
= child
.mclass
.in_hierarchy
(interpreter
.mainmodule
).greaters
331 var plist
= new Array[T
]
335 # not a parent but the type itself
336 if p
.mclass_type
.mclass
== child
.mclass
then continue
338 if p
.mclass_type
.need_anchor
then
339 # the parent need to be anchored to the child (contains a formal type)
340 var anchor
= p
.mclass_type
.anchor_to
(interpreter
.mainmodule
, child
)
341 plist
.add
(load_type
(anchor
))
343 # already revolved type
344 plist
.add
(load_type
(p
.mclass_type
))
350 # Increment types structures with the new type
351 fun load_increment
(mtype
: MClassType): Type do
352 # old type, no need of recomputation
353 if is_loaded
(mtype
) then
354 return load_type
(mtype
)
356 # current structures are expired, a new type appeared
360 interpreter
.modelbuilder
.toolcontext
.info
("IC-TYPING[DEBUG]: load increment {mtype}", 2)
363 if interpreter
.module_increment
then
364 load_module
(mtype
.mclass
.intro_mmodule
)
367 var t
= load_type
(mtype
)
370 nb_increment_loads
+= 1
371 if mtype
isa MGenericType then nb_gen_increment_loads
+= 1
373 # recompute mode = always
374 if interpreter
.recompute_mode
== "always" then
378 # recompute mode = thresold
379 if interpreter
.recompute_mode
== "threshold" then
380 if interpreter
.threshold_mode
== "increment" then
383 if increment_count
> interpreter
.threshold_count
then
390 # recompute mode = increment
391 if interpreter
.recompute_mode
== "increment" then
393 if not is_valid
then compute_typing
399 # Factory for specializations of Type
400 fun init_type
(id
: Int, mtype
: MClassType, supertypes
: Array[T
], typing
: Typing): T
is abstract
402 # Is the type already loaded ?
403 fun is_loaded
(mtype
: MType): Bool do return loaded_types
.has_key
(mtype
)
405 # Run the typing full computation
406 # Do nothing, need to be redefined
407 fun compute_typing
do
409 interpreter
.modelbuilder
.toolcontext
.info
("IC-TYPING[DEBUG]: compute typing", 1)
413 # Compute typing with the increment
414 # if the increment is destructive, need to recompute the whole typing structure
415 # else just compute typing structure for the new type
416 fun compute_increment
(t
: T
) is abstract
418 # Is the increment destructive ?
419 # destructive increment depends on typing method used
420 fun is_destructive_increment
(t
: T
): Bool is abstract
423 # An incremental typing type representation
424 private abstract class Type
429 # all resolved super-types
430 var supertypes
: Array[T
]
432 var mtype
: MClassType
436 init(id
: Int, mtype
: MClassType, supertypes
: Array[T
], typing
: Typing) do
439 self.supertypes
= supertypes
441 self.cache
= new Cache(typing
.interpreter
.cache_size
)
442 self.supertypes
.add
(self)
445 # Subtyping using computed representation
446 fun is_subtype
(sup
: T
): Bool is abstract
448 # Subtyping for uncomputed types
449 # unefficient algorithme using linear probing in known super-types
450 fun is_subtype_fallback
(sup
: T
): Bool do
452 typing
.nb_fallbacks
+= 1
453 if self.mtype
isa MGenericType or sup
.mtype
isa MGenericType then typing
.nb_gen_fallbacks
+= 1
456 if cache
.contains
(sup
) then
457 typing
.nb_cache_res
+= 1
458 return cache
.response
(sup
)
461 # test implies generic typing
462 if sup
.mtype
isa MGenericType then
463 for p
in supertypes
do
465 # found the same type (ie. p = B[Int] = sup)
466 if not cache
.contains
(sup
) then cache
.add
(sup
, true)
468 else if p
.mtype
.mclass
== sup
.mtype
.mclass
then
469 # found the same class (ie. p.mclass = B[B#0] = sup.mclass)
470 # compare formal types arguments
471 for i
in [0..p
.mtype
.arguments
.length
[ do
472 # erase nullable annotation of p arg
473 var sarg
= p
.mtype
.arguments
[i
]
474 if sarg
isa MNullableType then sarg
= sarg
.mtype
475 var sft
= typing
.load_type
(sarg
.as(MClassType))
476 # erase nullable annotation of super arg
477 var suparg
= sup
.mtype
.arguments
[i
]
478 if suparg
isa MNullableType then suparg
= suparg
.mtype
479 var pft
= typing
.load_type
(suparg
.as(MClassType))
480 if not sft
.is_subtype_fallback
(pft
) then
481 if not cache
.contains
(sup
) then cache
.add
(sup
, false)
485 if not cache
.contains
(sup
) then cache
.add
(sup
, true)
489 if not cache
.contains
(sup
) then cache
.add
(sup
, false)
493 # for non generic type: look up in supertypes
494 # 0(n) where n = nb supertypes of the current type
495 for p
in supertypes
do
497 if not cache
.contains
(sup
) then cache
.add
(sup
, true)
501 if not cache
.contains
(sup
) then cache
.add
(sup
, false)
505 redef fun to_s
do return "{mtype.to_s} (id: {id})"
508 # Binary Matrix (BM) typing
509 private class BMTyping
514 init(interpreter
: NaiveInterpreter) do super(interpreter
)
516 redef fun init_type
(id
, mtype
, supertypes
, typing
) do return new BMType(id
, mtype
, supertypes
, typing
)
518 # Compute rows in the binary matrix for each loaded type
519 redef fun compute_typing
do
521 for t
in loaded_types
.values
do
522 t
.compute_row
(loaded_types
, interpreter
.mainmodule
)
526 # If the increment is destructive, the typing representation is invalidated
527 # else add a row to the matrix and compute it
528 redef fun compute_increment
(t
) do
529 #print "DEBUG: compute increment {t}: is destructive = {is_destructive_increment(t)}"
531 # compute increments of supertypes first
532 for st
in t
.supertypes
do
533 if t
== st
then continue
534 if st
.row
== null then compute_increment
(st
)
537 if is_destructive_increment
(t
) then
538 # increment is destructive, need to recompute the whole typing structure
541 # increment is additive, compute only the type (and newly added parents)
543 t
.compute_row
(loaded_types
, interpreter
.mainmodule
)
547 # For BM typing, destructive increments are only supertypes of already computed types
548 # This appends only when a new generic type on an already computed generic class appears
549 # ie. increment is GenericType[Something] and loaded-types already contains GenericType[SomethingElse]
550 redef fun is_destructive_increment
(t
) do
551 if t
.mtype
isa MGenericType then
552 for ot
in loaded_types
.values
do
553 if ot
.mtype
.mclass
== t
.mtype
.mclass
then
554 nb_destructive_increments
+= 1
555 nb_gen_destructive_increments
+= 1
569 # A row is an array of bits
570 var row
: nullable Array[Bool]
572 # For each other types, fill the cell with 1 if subtype else 0
573 fun compute_row
(types
: HashMap[MType, T
], mainmodule
: MModule) do
574 row
= new Array[Bool].filled_with
(false, types
.length
)
575 for t
in types
.values
do
576 if self.is_subtype_fallback
(t
) then
582 if row
.length
> typing
.max_size_tables
then typing
.max_size_tables
= row
.length
583 typing
.sum_size_tables
+= row
.length
587 # return self.row[t.id]
588 redef fun is_subtype
(t
) do
589 if t
.id
>= self.row
.length
then return false
590 return self.row
[t
.id
]
594 # Perfect Hashing (PH) typing
595 private abstract class PHTyping
600 init(interpreter
: NaiveInterpreter) do
605 redef fun compute_typing
do
607 for t
in loaded_types
.values
do
608 t
.compute_row
(loaded_types
, interpreter
.mainmodule
)
612 # If the increment is destructive, the typing representation is invalidated
613 # else compute the hashmap of the type
614 redef fun compute_increment
(t
) do
615 # compute increments of supertypes first
616 for st
in t
.supertypes
do
617 if t
== st
then continue
618 if st
.row
== null then compute_increment
(st
)
621 if is_destructive_increment
(t
) then
622 # increment is destructive, need to recompute the whole typing structure
625 # increment is additive, compute only the type (and newly added parents)
627 t
.compute_row
(loaded_types
, interpreter
.mainmodule
)
631 # For HP typing, destructive increments are only supertypes of already computed types
632 # This appends only when a new generic type on an already computed generic class appears
633 # ie. increment is GenericType[Something] and loaded-types already contains GenericType[SomethingElse]
634 redef fun is_destructive_increment
(t
) do
635 if t
.mtype
isa MGenericType then
636 for ot
in loaded_types
.values
do
637 if ot
.mtype
.mclass
== t
.mtype
.mclass
then
639 nb_destructive_increments
+= 1
640 nb_gen_destructive_increments
+= 1
649 private abstract class PHType
654 # Mask is used to hash an id
655 var mask
: nullable Int
656 # A row is an array of IDs (Int)
657 var row
: nullable Array[Int]
659 # First compute the mask needed to perfectly hash the parents list
660 # Then fill the hashmap
661 fun compute_row
(types
: HashMap[MType, T
], mainmodule
: MModule) do
662 # Create super type list
663 var stypes
= new List[Type]
664 for st
in types
.values
do
665 if self.is_subtype_fallback
(st
) then stypes
.add
(st
)
668 # Compute the hashing 'mask'
669 self.mask
= compute_mask
(stypes
)
674 var idx
= phash
(st
.id
)
675 if idx
> row
.length
then for i
in [row
.length
.. idx
[ do row
[i
] = 0
680 if row
.length
> typing
.max_size_tables
then typing
.max_size_tables
= row
.length
681 typing
.sum_size_tables
+= row
.length
685 fun phash
(id
: Int): Int is abstract
688 # return self.row[phash(t.id)] == t.id
689 redef fun is_subtype
(t
) do
690 if self.row
.length
<= phash
(t
.id
) then return false
691 return self.row
[phash
(t
.id
)] == t
.id
694 fun compute_mask
(stypes
: List[Type]): Int is abstract
697 private class PHModTyping
699 redef type T
: PHModType
700 redef fun init_type
(id
, mtype
, supertypes
, typing
) do return new PHModType(id
, mtype
, supertypes
, typing
)
703 private class PHModType
706 redef type T
: PHModType
710 redef fun phash
(id
: Int): Int do return mask
.as(not null) % id
712 # Look for the first mask allowing perfect hashing for stypes ids
713 # TODO: Look for a more efficien way to do this
714 redef fun compute_mask
(stypes
: List[Type]): Int do
717 var used
= new List[Int]
719 var res
= (mask
% st
.id
)
720 if used
.has
(res
) then
726 if used
.length
== stypes
.length
then break
733 private class PHAndTyping
735 redef type T
: PHAndType
736 redef fun init_type
(id
, mtype
, supertypes
, typing
) do return new PHAndType(id
, mtype
, supertypes
, typing
)
739 private class PHAndType
742 redef type T
: PHAndType
744 # Hash using binary and
746 redef fun phash
(id
: Int): Int do return mask
.as(not null).bin_and
(id
)
748 # Look for the first mask allowing perfect hashing for stypes ids
749 # TODO: Look for a more efficien way to do this
750 redef fun compute_mask
(stypes
: List[Type]): Int do
753 var used
= new List[Int]
755 var res
= (mask
.bin_and
(st
.id
))
756 if used
.has
(res
) then
762 if used
.length
== stypes
.length
then break
769 # Coloration (CL) typing
770 private class CLTyping
775 # Core of type hierarchy (types with at least two supertypes and their indirect supertypes)
776 var core
: Array[T
] = new Array[T
]
777 # All types in single inheritance that are not part of core
778 var crown
: Array[T
] = new Array[T
]
779 # All minimal classes of core
780 var border
: Array[T
] = new Array[T
]
782 # Conflicts graph of hierarchy
783 var conflict_graph
: HashMap[T
, HashSet[T
]] = new HashMap[T
, HashSet[T
]]
786 # Increments are colored with injective colors
789 var sorter
: TypeSorter = new TypeSorter
791 init(interpreter
: NaiveInterpreter) do
796 redef fun init_type
(id
, mtype
, supertypes
, typing
) do return new CLType(id
, mtype
, supertypes
, typing
)
798 # Colorize all known types and fill the type tables
799 redef fun compute_typing
do
809 # Compute a linear extension of parents of each types and tag each type as core, border or crown
815 # clear already build tables
816 for t
in loaded_types
.values
do
817 #t.parents = new HashSet[T]
819 t
.sub_types
= new HashSet[T
]
822 # compute linear ext of each type type
823 for t
in loaded_types
.values
do compute_linear_ext
(t
)
825 # tag each type as core, crown or border
826 for t
in loaded_types
.values
do tag_type
(t
)
828 # sort by reverse linearization order
834 # Compute linear extension of the type
835 fun compute_linear_ext
(t
: T
) do
836 var lin
= new Array[T
]
837 for st
in loaded_types
.values
do
838 if t
.is_subtype_fallback
(st
) then
840 t
.nb_parents
= t
.mtype
.mclass
.in_hierarchy
(interpreter
.mainmodule
).direct_greaters
.length
841 if t
!= st
then st
.sub_types
.add
(t
)
848 # Tag type as core, crown or border
849 fun tag_type
(t
: T
) do
850 if t
.nb_parents
> 1 then
851 if t
.sub_types
.length
<= 1 then
858 for st
in t
.lin
do if t
!= st
and not core
.has
(st
) then core
.add
(st
)
861 var subtypes_are_si
= true
862 for sub
in t
.sub_types
do if sub
.nb_parents
> 1 then subtypes_are_si
= false
863 if subtypes_are_si
then crown
.add
(t
)
867 # Compute related classes to detect coloring conflicts
868 fun compute_conflicts
do
870 var mi_types
= new Array[T
]
871 mi_types
.add_all
(core
)
872 mi_types
.add_all
(border
)
873 sorter
.sort
(mi_types
)
877 if i
== t
then continue
881 if i
== j
or j
== t
then continue
884 var d_ij
= lin_i
- lin_j
885 var d_ji
= lin_j
- lin_i
888 if not conflict_graph
.has_key
(ed1
) then conflict_graph
[ed1
] = new HashSet[T
]
889 # add ed1 x ed2 to conflicts graph
890 for ed2
in d_ji
do conflict_graph
[ed1
].add
(ed2
)
893 if not conflict_graph
.has_key
(ed1
) then conflict_graph
[ed1
] = new HashSet[T
]
894 # add ed1 x ed2 to conflicts graph
895 for ed2
in d_ji
do conflict_graph
[ed1
].add
(ed2
)
900 self.conflict_graph
= conflict_graph
903 # Colorize an array of types
904 fun colorize
(elts
: Array[T
]) do
908 var color
= min_color
909 while not color_free
(t
, color
) do
913 if color
> max_color
then max_color
= color
918 # Check if a related type to t already use the color
919 fun color_free
(t
: T
, color
: Int): Bool do
920 if conflict_graph
.has_key
(t
) then
921 for st
in conflict_graph
[t
] do if st
.color
== color
then return false
924 if st
== t
then continue
925 if st
.color
== color
then return false
930 # Fill de colored tables
931 fun fill_tables
do for t
in loaded_types
.values
do fill_table
(t
)
933 fun fill_table
(t
: T
) do
934 t
.row
= new Array[Int]
936 if t
.row
.length
<= st
.color
.as(not null) then
937 for i
in [t
.row
.length
..st
.color
.as(not null)[ do t
.row
.add
(0)
939 t
.row
[st
.color
.as(not null)] = st
.id
943 if t
.row
.length
> max_size_tables
then max_size_tables
= t
.row
.length
944 sum_size_tables
+= t
.row
.length
947 # Compute table for a type increment: compute linearization of parents and fill the table
948 fun compute_table_increment
(t
: T
) do
949 compute_linear_ext
(t
)
953 redef fun compute_increment
(t
) do
954 #print "DEBUG: compute increment {t}: is destructive = {is_destructive_increment(t)}"
961 for st
in t
.supertypes
do
962 if t
== st
then continue
963 if st
.row
== null then compute_increment
(st
)
966 if is_destructive_increment
(t
) then
969 # increment is additive, compute only the type (and newly added parents)
971 compute_table_increment
(t
)
975 # For CL typing, destructive increments are supertypes of already computed types and common types of two already computed types
976 redef fun is_destructive_increment
(t
) do
977 if t
.mtype
isa MGenericType then
978 for ot
in loaded_types
.values
do
979 if ot
.mtype
.mclass
== t
.mtype
.mclass
then
981 nb_destructive_increments
+= 1
982 nb_gen_destructive_increments
+= 1
988 compute_linear_ext
(t
)
989 if t
.nb_parents
> 1 then
991 nb_destructive_increments
+= 1
992 if t
.mtype
isa MGenericType then nb_gen_destructive_increments
= 0
1000 private class CLType
1003 redef type T
: CLType
1005 # Linearization of super-types including the type itself
1006 var lin
: Array[T
] = new Array[T
]
1007 # The color assignated to the type
1008 var color
: nullable Int
1009 # Number of direct super-types
1010 var nb_parents
: Int = 0
1012 var sub_types
: HashSet[T
] = new HashSet[T
]
1014 # A row is the an array of IDs
1015 var row
: nullable Array[Int]
1018 # return row[t.color] == t.id
1019 redef fun is_subtype
(t
) do
1020 if t
.color
>= row
.length
then return false
1021 return row
[t
.color
.as(not null)] == t
.id
1025 # Wrapper for interpretor legacy typing based on precomputed metalmodel
1026 private class LegacyTyping
1028 redef type T
: LegacyType
1029 init(interpreter
: NaiveInterpreter) do super(interpreter
)
1030 redef fun init_type
(id
, mtype
, supertypes
, typing
) do return new LegacyType(id
, mtype
, supertypes
, typing
)
1033 # Wrapper for interpretor legacy typing based on precomputed metalmodel
1034 private class LegacyType
1036 redef type T
: LegacyType
1037 redef fun is_subtype
(t
) do return self.mtype
.is_subtype
(typing
.interpreter
.mainmodule
, typing
.interpreter
.frame
.arguments
.first
.mtype
.as(MClassType), t
.mtype
)
1044 var elements
: Array[CachePair]
1046 var cache
: nullable CachePair
1050 self.elements
= new Array[CachePair].with_capacity
(size
)
1053 # Add a response to the cache
1054 fun add
(t
: Type, res
: Bool) do
1055 var pair
= new CachePair(t
, res
)
1056 elements
.insert
(pair
, 0)
1057 if elements
.length
> size
then elements
.pop
1060 # Check if the cache contains the subtype test response
1061 fun contains
(t
: Type): Bool do
1062 for e
in elements
do
1071 # Get a subtype test response from the cache
1072 # ensure contains before
1073 fun response
(t
: Type): Bool do
1074 if cache
!= null and cache
.t
== t
then return cache
.res
1076 for e
in elements
do if e
.t
== t
then return e
.res
1078 print
"IC-ERROR: Cache fault"
1083 private class CachePair
1088 # Add operator - to Array
1089 redef class Array[T
]
1090 # Return a new array with the elements only contened in 'self' and not in 'o'
1091 fun -(o
: Array[T
]): Array[T
] do
1092 var res
= new Array[T
]
1093 for e
in self do if not o
.has
(e
) then res
.add
(e
)
1098 # A sorter for reversed linearization of types
1099 private class TypeSorter
1100 super AbstractSorter[Type]
1102 redef fun compare
(a
, b
) do
1105 else if a
.is_subtype_fallback
(b
) then