ni_nitdoc: added fast copy past utility to signatures.

[nit.git] / src / interpretor_type_test.nit

# This file is part of NIT ( http://www.nitlanguage.org ).
#
# Copyright 2012 Alexandre Terrasa <alexandre@moz-concept.com>
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

# Introduce incremental typing in naive interpreter
# Typing modes are :
# * Legacy: default mode, using request to precomputed metamodel
# * BM: binary matrix
# * CL: coloration
# * PHAND: perfect hashing using binary AND
# * PHMOD: perfect hashing using modulo
module interpretor_type_test

intrude import naive_interpreter

# Add options for incremental typing
redef class ToolContext
        # --ic-typing-mode BM | CL | PHMOD | PHAND
        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")
        # --ic-load-mode
        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")
        # --ic-bootstrap
        var opt_ic_bootstrap = new OptionBool("Bootstrap typing with standard library (default is no bootstrap)", "--ic-bootstrap")
        # --ic-recompute-mode always | never | threshold | increment
        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")
        # --ic-threshold-mode increment | fallback
        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")
        # --ic-threshold-count <int>
        var opt_ic_threshold_count = new OptionInt("Threshold count. Take an integer", 0, "--ic-threshold-count")
        # --ic-cache-size <int>
        var opt_ic_cache_size = new OptionInt("Cache size. Take an integer", 0, "--ic-cache-size")
        # --ic-show-stats
        var opt_ic_show_stats = new OptionBool("Show statistics about typing at the end of the interpretation", "--ic-show-stats")

        redef init
        do
                super
                self.option_context.add_option(self.opt_ic_typing_mode)
                self.option_context.add_option(self.opt_ic_load_mode)
                self.option_context.add_option(self.opt_ic_bootstrap)
                self.option_context.add_option(self.opt_ic_recompute_mode)
                self.option_context.add_option(self.opt_ic_threshold_mode)
                self.option_context.add_option(self.opt_ic_threshold_count)
                self.option_context.add_option(self.opt_ic_cache_size)
                self.option_context.add_option(self.opt_ic_show_stats)
        end
end

redef class ModelBuilder
        # Add statistics display at the end of the interpretation
        redef fun run_naive_interpreter(mainmodule, arguments) do
                var time0 = get_time
                self.toolcontext.info("*** START INTERPRETING ***", 1)

                var interpreter = new NaiveInterpreter(self, mainmodule, arguments)
                init_naive_interpreter(interpreter, mainmodule)

                # stats
                if interpreter.show_stats then
                        print "# Interpretation statistics"

                        print "## Dynamic loading"
                        print " - nb dynamically lodaed types: {interpreter.typing.nb_loads} ({interpreter.typing.nb_gen_loads} were generic)"
                        print " - nb dynamically lodaed modules: {interpreter.typing.nb_mod_loads}"

                        print "## Typing structures"
                        print " - nb increments: {interpreter.typing.nb_increment_loads} ({interpreter.typing.nb_gen_increment_loads} were generic)"
                        print " - nb destructive increments: {interpreter.typing.nb_destructive_increments} ({interpreter.typing.nb_gen_destructive_increments} were generic)"
                        print " - nb full structure recomputation: {interpreter.typing.nb_recomputes}"
                        print " - overall max size table: {interpreter.typing.max_size_tables}"
                        print " - total: size needed for tables: {interpreter.typing.sum_size_tables}"

                        print "## Type test"
                        print " - nb isa: {interpreter.typing.nb_isas} ({interpreter.typing.nb_gen_isas} involving generic types)"
                        print " - nb isa using fallback: {interpreter.typing.nb_fallbacks} ({interpreter.typing.nb_gen_fallbacks} involving generic types)"
                        print " - nb isa using fallback responded from cache: {interpreter.typing.nb_cache_res}"
                end

                var time1 = get_time
                self.toolcontext.info("*** END INTERPRETING: {time1-time0} ***", 2)
        end
end

# Add gestion handling for incremental typing mecanisms
redef class NaiveInterpreter

        var typing: Typing
        var module_increment: Bool
        var recompute_mode: String
        var threshold_mode: String = "null"
        var threshold_count: Int = 0
        var cache_size: Int = 0
        var show_stats: Bool = false

        # Add option handling
        redef init(modelbuilder, mainmodule, arguments) do
                super(modelbuilder, mainmodule, arguments)

                # choose typing method
                var mode = modelbuilder.toolcontext.opt_ic_typing_mode.value
                if mode == "BM" then
                        self.modelbuilder.toolcontext.info("IC-TYPING: Using BM typing", 1)
                        typing = new BMTyping(self)
                else if mode == "CL" then
                        self.modelbuilder.toolcontext.info("IC-TYPING: Using CL typing", 1)
                        typing = new CLTyping(self)
                else if mode == "PHMOD" then
                        self.modelbuilder.toolcontext.info("IC-TYPING: Using PH-MOD typing", 1)
                        typing = new PHModTyping(self)
                else if mode == "PHAND" then
                        self.modelbuilder.toolcontext.info("IC-TYPING: Using PH-AND typing", 1)
                        typing = new PHAndTyping(self)
                else
                        self.modelbuilder.toolcontext.info("IC-TYPING: Using legacy typing", 1)
                        typing = new LegacyTyping(self)
                end

                # load full module or juste the type ?
                mode = modelbuilder.toolcontext.opt_ic_load_mode.value
                if mode == "module" then
                        self.modelbuilder.toolcontext.info("IC-TYPING: Using load mode: module", 1)
                        module_increment = true
                else
                        self.modelbuilder.toolcontext.info("IC-TYPING: Using load mode: type", 1)
                        module_increment = false
                end

                # bootstrap type structures with stdlib types
                if modelbuilder.toolcontext.opt_ic_bootstrap.value then
                        self.modelbuilder.toolcontext.info("IC-TYPING: Using bootstrap", 1)
                        typing.bootstrap
                end

                # typing recomputation mode
                var recompute_mode = modelbuilder.toolcontext.opt_ic_recompute_mode.value
                if recompute_mode != null then
                        self.recompute_mode = recompute_mode

                        if recompute_mode == "threshold" then
                                var threshold_mode = modelbuilder.toolcontext.opt_ic_threshold_mode.value
                                if threshold_mode == null then
                                        print "IC-ERROR : Recompute mode 'threshold' need a threshold mode"
                                        abort
                                else
                                        self.modelbuilder.toolcontext.info("IC-TYPING: Using threshold mode: {threshold_mode}", 1)
                                        self.threshold_mode = threshold_mode
                                        var threshold_count = modelbuilder.toolcontext.opt_ic_threshold_count.value
                                        if threshold_count == 0 then
                                                print "IC-ERROR : Recompute mode 'threshold' need a threshold count"
                                                abort
                                        else
                                                self.threshold_count = threshold_count
                                                self.modelbuilder.toolcontext.info("IC-TYPING: Using threshold value: {threshold_count}", 1)
                                        end
                                end
                        end
                else
                        self.recompute_mode = "never"
                end
                self.modelbuilder.toolcontext.info("IC-TYPING: Using recompute mode: {self.recompute_mode}", 1)

                # cache size
                cache_size = modelbuilder.toolcontext.opt_ic_cache_size.value
                self.modelbuilder.toolcontext.info("IC-TYPING: Using cache size: {cache_size}", 1)

                # stats
                if modelbuilder.toolcontext.opt_ic_show_stats.value then show_stats = true
        end

        # Handle subtypes tests and redispatch to selected mode
        redef fun is_subtype(sub, sup) do
                self.modelbuilder.toolcontext.info("IC-TYPING[DEBUG]: {sub} ISA {sup}", 2)

                # stats
                typing.nb_isas += 1
                if sup isa MGenericType or sub isa MGenericType then typing.nb_gen_isas += 1

                # special case of nullables types
                if sub isa MNullType and sup isa MNullableType then
                        return true
                else if sub isa MNullType and not sup isa MNullableType then
                        return false
                end
                if sub isa MNullableType then sub = sub.mtype
                if sup isa MNullableType then sup = sup.mtype

                # std case
                var t1 = typing.load_increment(sub.as(MClassType))
                var t2 = typing.load_increment(sup.as(MClassType))

                var res: Bool
                if typing.is_valid then
                        res = t1.is_subtype(t2)
                else
                        # recompute mode = thresold
                        if recompute_mode == "threshold" then
                                if threshold_mode == "fallback" then
                                        typing.increment_count += 1
                                        # recompute instead fallback
                                        if typing.increment_count > threshold_count then
                                                typing.compute_typing
                                                typing.increment_count = 0
                                                return t1.is_subtype(t2)
                                        end
                                end
                        end
                        res = t1.is_subtype_fallback(t2)
                end
                return res
        end
end

# Incremental typing

# The base of incremental typing
private abstract class Typing
        type T: Type

        # List of already loaded types
        var loaded_types: HashMap[MType, T] = new HashMap[MType, T]
        # List of already loaded modules
        var loaded_modules: HashSet[MModule] = new HashSet[MModule]
        # Last type ID used
        var lastID: Int = -1
        # Is the typing still valid (no destructive increment)
        var is_valid: Bool = false
        # Increment count since the last full recomputation
        var increment_count = 0

        private var interpreter: NaiveInterpreter

        # stats
        var nb_loads = 0
        var nb_gen_loads = 0
        var nb_mod_loads = 0
        var nb_increment_loads = 0
        var nb_gen_increment_loads = 0
        var nb_destructive_increments = 0
        var nb_gen_destructive_increments = 0
        var nb_isas = 0
        var nb_gen_isas = 0
        var nb_recomputes = 0
        var nb_fallbacks = 0
        var nb_gen_fallbacks = 0
        var nb_cache_res = 0
        var max_size_tables = 0
        var sum_size_tables = 0

        private init(interpreter: NaiveInterpreter) do
                self.interpreter = interpreter
        end

        # Load the std lib types and compute typing
        fun bootstrap do
                interpreter.modelbuilder.toolcontext.info("IC-TYPING[DEBUG]: bootstrap start", 2)
                var mods = interpreter.mainmodule.model.get_mmodules_by_name("standard")
                if mods != null then
                        var std = mods.first
                        for m in std.in_nesting.direct_greaters do
                                load_module(m)
                        end
                end
                compute_typing
                interpreter.modelbuilder.toolcontext.info("IC-TYPING[DEBUG]: bootstrap end", 2)
        end

        # Load all types contained in a module
        fun load_module(mmodule: MModule) do
                interpreter.modelbuilder.toolcontext.info("IC-TYPING[DEBUG]: load module {mmodule}", 2)
                # import nested module first
                for m in mmodule.in_nesting.greaters do
                        if mmodule == m then continue
                        load_module(m)
                end

                # load classes in module
                if loaded_modules.has(mmodule) then return

                # stats
                nb_mod_loads += 1

                for c in mmodule.intro_mclasses do
                        # skip unanchored types (they will be handled by load_supertypes of anchored types
                        if c.mclass_type.need_anchor then continue
                        load_type(c.mclass_type)
                end
                loaded_modules.add(mmodule)
        end

        # Load a MType and return its Type representation
        fun load_type(mtype: MClassType): T do
                if is_loaded(mtype) then
                        return loaded_types[mtype]
                else
                        # stats
                        nb_loads += 1
                        if mtype isa MGenericType then nb_gen_loads += 1

                        var supertypes = load_supertypes(mtype)
                        var t = init_type(lastID + 1, mtype, supertypes, self)
                        lastID = t.id
                        loaded_types[mtype] = t

                        # load formal parameter types
                        if mtype isa MGenericType then
                                for arg in mtype.arguments do
                                        if arg isa MClassType then load_type(arg)
                                end
                        end

                        return t
                end
        end

        # Load compile time known super-types of a type
        # supertypes are all known super classes at compile time and unresolved generic classes
        fun load_supertypes(child: MClassType): Array[T] do
                var parents = child.mclass.in_hierarchy(interpreter.mainmodule).greaters
                var plist = new Array[T]

                # load each parent
                for p in parents do
                        # not a parent but the type itself
                        if p.mclass_type.mclass == child.mclass then continue

                        if p.mclass_type.need_anchor then
                                # the parent need to be anchored to the child (contains a formal type)
                                var anchor = p.mclass_type.anchor_to(interpreter.mainmodule, child)
                                plist.add(load_type(anchor))
                        else
                                # already revolved type
                                plist.add(load_type(p.mclass_type))
                        end
                end
                return plist
        end

        # Increment types structures with the new type
        fun load_increment(mtype: MClassType): Type do
                # old type, no need of recomputation
                if is_loaded(mtype) then
                        return load_type(mtype)
                else
                        # current structures are expired, a new type appeared
                        is_valid = false
                end

                interpreter.modelbuilder.toolcontext.info("IC-TYPING[DEBUG]: load increment {mtype}", 2)

                # load the module
                if interpreter.module_increment then
                        load_module(mtype.mclass.intro_mmodule)
                end

                var t = load_type(mtype)

                # stats
                nb_increment_loads += 1
                if mtype isa MGenericType then nb_gen_increment_loads += 1

                # recompute mode = always
                if interpreter.recompute_mode == "always" then
                        compute_typing
                end

                # recompute mode = thresold
                if interpreter.recompute_mode == "threshold" then
                        if interpreter.threshold_mode == "increment" then
                                increment_count += 1

                                if increment_count > interpreter.threshold_count then
                                        compute_typing
                                        increment_count = 0
                                end
                        end
                end

                # recompute mode = increment
                if interpreter.recompute_mode == "increment" then
                        compute_increment(t)
                        if not is_valid then compute_typing
                end

                return t
        end

        # Factory for specializations of Type
        fun init_type(id: Int, mtype: MClassType, supertypes: Array[T], typing: Typing): T is abstract

        # Is the type already loaded ?
        fun is_loaded(mtype: MType): Bool do return loaded_types.has_key(mtype)

        # Run the typing full computation
        # Do nothing, need to be redefined
        fun compute_typing do
                nb_recomputes += 1
                interpreter.modelbuilder.toolcontext.info("IC-TYPING[DEBUG]: compute typing", 1)
                is_valid = true
        end

        # Compute typing with the increment
        # if the increment is destructive, need to recompute the whole typing structure
        # else just compute typing structure for the new type
        fun compute_increment(t: T) is abstract

        # Is the increment destructive ?
        # destructive increment depends on typing method used
        fun is_destructive_increment(t: T): Bool is abstract
end

# An incremental typing type representation
private abstract class Type
        type T: Type

        # The unique type id
        var id: Int
        # all resolved super-types
        var supertypes: Array[T]

        var mtype: MClassType
        var typing: Typing
        var cache: Cache

        init(id: Int, mtype: MClassType, supertypes: Array[T], typing: Typing) do
                self.id = id
                self.mtype = mtype
                self.supertypes = supertypes
                self.typing = typing
                self.cache = new Cache(typing.interpreter.cache_size)
                self.supertypes.add(self)
        end

        # Subtyping using computed representation
        fun is_subtype(sup: T): Bool is abstract

        # Subtyping for uncomputed types
        # unefficient algorithme using linear probing in known super-types
        fun is_subtype_fallback(sup: T): Bool do
                # stats
                typing.nb_fallbacks += 1
                if self.mtype isa MGenericType or sup.mtype isa MGenericType then typing.nb_gen_fallbacks += 1

                # try in cache cache
                if cache.contains(sup) then
                        typing.nb_cache_res += 1
                        return cache.response(sup)
                end

                # test implies generic typing
                if sup.mtype isa MGenericType then
                        for p in supertypes do
                                if p == sup then
                                        # found the same type (ie. p = B[Int] = sup)
                                        if not cache.contains(sup) then cache.add(sup, true)
                                        return true
                                else if p.mtype.mclass == sup.mtype.mclass then
                                        # found the same class (ie. p.mclass = B[B#0] = sup.mclass)
                                        # compare formal types arguments
                                        for i in [0..p.mtype.arguments.length[ do
                                                # erase nullable annotation of p arg
                                                var sarg = p.mtype.arguments[i]
                                                if sarg isa MNullableType then sarg = sarg.mtype
                                                var sft = typing.load_type(sarg.as(MClassType))
                                                # erase nullable annotation of super arg
                                                var suparg = sup.mtype.arguments[i]
                                                if suparg isa MNullableType then suparg = suparg.mtype
                                                var pft = typing.load_type(suparg.as(MClassType))
                                                if not sft.is_subtype_fallback(pft) then
                                                        if not cache.contains(sup) then cache.add(sup, false)
                                                        return false
                                                end
                                        end
                                        if not cache.contains(sup) then cache.add(sup, true)
                                        return true
                                end
                        end
                        if not cache.contains(sup) then cache.add(sup, false)
                        return false
                end

                # for non generic type: look up in supertypes
                # 0(n) where n = nb supertypes of the current type
                for p in supertypes do
                        if p == sup then
                                if not cache.contains(sup) then cache.add(sup, true)
                                return true
                        end
                end
                if not cache.contains(sup) then cache.add(sup, false)
                return false
        end

        redef fun to_s do return "{mtype.to_s} (id: {id})"
end

# Binary Matrix (BM) typing
private class BMTyping
        super Typing

        redef type T: BMType

        init(interpreter: NaiveInterpreter) do super(interpreter)

        redef fun init_type(id, mtype, supertypes, typing) do return new BMType(id, mtype, supertypes, typing)

        # Compute rows in the binary matrix for each loaded type
        redef fun compute_typing do
                super
                for t in loaded_types.values do
                        t.compute_row(loaded_types, interpreter.mainmodule)
                end
        end

        # If the increment is destructive, the typing representation is invalidated
        # else add a row to the matrix and compute it
        redef fun compute_increment(t) do
                #print "DEBUG: compute increment {t}: is destructive = {is_destructive_increment(t)}"

                # compute increments of supertypes first
                for st in t.supertypes do
                        if t == st then continue
                        if st.row == null then compute_increment(st)
                end

                if is_destructive_increment(t) then
                        # increment is destructive, need to recompute the whole typing structure
                        is_valid = false
                else
                        # increment is additive, compute only the type (and newly added parents)
                        is_valid = true
                        t.compute_row(loaded_types, interpreter.mainmodule)
                end
        end

        # For BM typing, destructive increments are only supertypes of already computed types
        # This appends only when a new generic type on an already computed generic class appears
        # ie. increment is GenericType[Something] and loaded-types already contains GenericType[SomethingElse]
        redef fun is_destructive_increment(t) do
                if t.mtype isa MGenericType then
                        for ot in loaded_types.values do
                                if ot.mtype.mclass == t.mtype.mclass then
                                        nb_destructive_increments += 1
                                        nb_gen_destructive_increments += 1
                                        return true
                                end
                        end
                end
                return false
        end
end

private class BMType
        super Type

        redef type T: BMType

        # A row is an array of bits
        var row: nullable Array[Bool]

        # For each other types, fill the cell with 1 if subtype else 0
        fun compute_row(types: HashMap[MType, T], mainmodule: MModule) do
                row = new Array[Bool].filled_with(false, types.length)
                for t in types.values do
                        if self.is_subtype_fallback(t) then
                                row[t.id] = true
                        end
                end

                # stats
                if row.length > typing.max_size_tables then typing.max_size_tables = row.length
                typing.sum_size_tables += row.length
        end

        # O(1)
        # return self.row[t.id]
        redef fun is_subtype(t) do
                if t.id >= self.row.length then return false
                return self.row[t.id]
        end
end

# Perfect Hashing (PH) typing
private abstract class PHTyping
        super Typing

        redef type T: PHType

        init(interpreter: NaiveInterpreter) do
                super(interpreter)
                lastID = 0
        end

        redef fun compute_typing do
                super
                for t in loaded_types.values do
                        t.compute_row(loaded_types, interpreter.mainmodule)
                end
        end

        # If the increment is destructive, the typing representation is invalidated
        # else compute the hashmap of the type
        redef fun compute_increment(t) do
                # compute increments of supertypes first
                for st in t.supertypes do
                        if t == st then continue
                        if st.row == null then compute_increment(st)
                end

                if is_destructive_increment(t) then
                        # increment is destructive, need to recompute the whole typing structure
                        is_valid = false
                else
                        # increment is additive, compute only the type (and newly added parents)
                        is_valid = true
                        t.compute_row(loaded_types, interpreter.mainmodule)
                end
        end

        # For HP typing, destructive increments are only supertypes of already computed types
        # This appends only when a new generic type on an already computed generic class appears
        # ie. increment is GenericType[Something] and loaded-types already contains GenericType[SomethingElse]
        redef fun is_destructive_increment(t) do
                if t.mtype isa MGenericType then
                        for ot in loaded_types.values do
                                if ot.mtype.mclass == t.mtype.mclass then
                                        # stats
                                        nb_destructive_increments += 1
                                        nb_gen_destructive_increments += 1
                                        return true
                                end
                        end
                end
                return false
        end
end

private abstract class PHType
        super Type

        redef type T: PHType

        # Mask is used to hash an id
        var mask: nullable Int
        # A row is an array of IDs (Int)
        var row: nullable Array[Int]

        # First compute the mask needed to perfectly hash the parents list
        # Then fill the hashmap
        fun compute_row(types: HashMap[MType, T], mainmodule: MModule) do
                # Create super type list
                var stypes = new List[Type]
                for st in types.values do
                        if self.is_subtype_fallback(st) then stypes.add(st)
                end

                # Compute the hashing 'mask'
                self.mask = compute_mask(stypes)

                # Fill the row
                row = new Array[Int]
                for st in stypes do
                        var idx = phash(st.id)
                        if idx > row.length then for i in [row.length .. idx[ do row[i] = 0
                        row[idx] = st.id
                end

                # stats
                if row.length > typing.max_size_tables then typing.max_size_tables = row.length
                typing.sum_size_tables += row.length
        end

        # Hash IDs
        fun phash(id: Int): Int is abstract

        # O(1)
        # return self.row[phash(t.id)] == t.id
        redef fun is_subtype(t) do
                if self.row.length <= phash(t.id) then return false
                return self.row[phash(t.id)] == t.id
        end

        fun compute_mask(stypes: List[Type]): Int is abstract
end

private class PHModTyping
        super PHTyping
        redef type T: PHModType
        redef fun init_type(id, mtype, supertypes, typing) do return new PHModType(id, mtype, supertypes, typing)
end

private class PHModType
        super PHType

        redef type T: PHModType

        # Hash using modulo
        # return mask % id
        redef fun phash(id: Int): Int do return mask.as(not null) % id

        # Look for the first mask allowing perfect hashing for stypes ids
        # TODO: Look for a more efficien way to do this
        redef fun compute_mask(stypes: List[Type]): Int do
                var mask = 0
                loop
                        var used = new List[Int]
                        for st in stypes do
                                var res = (mask % st.id)
                                if used.has(res) then
                                        break
                                else
                                        used.add(res)
                                end
                        end
                        if used.length == stypes.length then break
                        mask += 1
                end
                return mask
        end
end

private class PHAndTyping
        super PHTyping
        redef type T: PHAndType
        redef fun init_type(id, mtype, supertypes, typing) do return new PHAndType(id, mtype, supertypes, typing)
end

private class PHAndType
        super PHType

        redef type T: PHAndType

        # Hash using binary and
        # return mask & id
        redef fun phash(id: Int): Int do return mask.as(not null).bin_and(id)

        # Look for the first mask allowing perfect hashing for stypes ids
        # TODO: Look for a more efficien way to do this
        redef fun compute_mask(stypes: List[Type]): Int do
                var mask = 0
                loop
                        var used = new List[Int]
                        for st in stypes do
                                var res = (mask.bin_and(st.id))
                                if used.has(res) then
                                        break
                                else
                                        used.add(res)
                                end
                        end
                        if used.length == stypes.length then break
                        mask += 1
                end
                return mask
        end
end

# Coloration (CL) typing
private class CLTyping
        super Typing

        redef type T: CLType

        # Core of type hierarchy (types with at least two supertypes and their indirect supertypes)
        var core: Array[T] = new Array[T]
        # All types in single inheritance that are not part of core
        var crown: Array[T] = new Array[T]
        # All minimal classes of core
        var border: Array[T] = new Array[T]

        # Conflicts graph of hierarchy
        var conflict_graph: HashMap[T, HashSet[T]] = new HashMap[T, HashSet[T]]

        # Max color used
        # Increments are colored with injective colors
        var max_color = 0

        var sorter: TypeSorter = new TypeSorter

        init(interpreter: NaiveInterpreter) do
                super(interpreter)
                lastID = 0
        end

        redef fun init_type(id, mtype, supertypes, typing) do return new CLType(id, mtype, supertypes, typing)

        # Colorize all known types and fill the type tables
        redef fun compute_typing do
                super
                compute_init
                compute_conflicts
                colorize(core)
                colorize(border)
                colorize(crown)
                fill_tables
        end

        # Compute a linear extension of parents of each types and tag each type as core, border or crown
        fun compute_init do
                core.clear
                crown.clear
                border.clear

                # clear already build tables
                for t in loaded_types.values do
                        #t.parents = new HashSet[T]
                        t.nb_parents = 0
                        t.sub_types = new HashSet[T]
                end

                # compute linear ext of each type type
                for t in loaded_types.values do compute_linear_ext(t)

                # tag each type as core, crown or border
                for t in loaded_types.values do tag_type(t)

                # sort by reverse linearization order
                sorter.sort(core)
                sorter.sort(crown)
                sorter.sort(border)
        end

        # Compute linear extension of the type
        fun compute_linear_ext(t: T) do
                var lin = new Array[T]
                for st in loaded_types.values do
                        if t.is_subtype_fallback(st) then
                                lin.add(st)
                                t.nb_parents = t.mtype.mclass.in_hierarchy(interpreter.mainmodule).direct_greaters.length
                                if t != st then st.sub_types.add(t)
                        end
                end
                sorter.sort(lin)
                t.lin = lin
        end

        # Tag type as core, crown or border
        fun tag_type(t: T) do
                if t.nb_parents > 1 then
                        if t.sub_types.length <= 1 then
                                # border
                                border.add(t)
                        else
                                # core
                                core.add(t)
                        end
                        for st in t.lin do if t != st and not core.has(st) then core.add(st)
                else
                        # crown
                        var subtypes_are_si = true
                        for sub in t.sub_types do if sub.nb_parents > 1 then subtypes_are_si = false
                        if subtypes_are_si then crown.add(t)
                end
        end

        # Compute related classes to detect coloring conflicts
        fun compute_conflicts do
                conflict_graph.clear
                var mi_types = new Array[T]
                mi_types.add_all(core)
                mi_types.add_all(border)
                sorter.sort(mi_types)

                for t in mi_types do
                        for i in t.lin do
                                if i == t then continue
                                var lin_i = i.lin

                                for j in t.lin do
                                        if i == j or j == t then continue
                                        var lin_j = j.lin

                                        var d_ij = lin_i - lin_j
                                        var d_ji = lin_j - lin_i

                                        for ed1 in d_ij do
                                                if not conflict_graph.has_key(ed1) then conflict_graph[ed1] = new HashSet[T]
                                                # add ed1 x ed2 to conflicts graph
                                                for ed2 in d_ji do conflict_graph[ed1].add(ed2)
                                        end
                                        for ed1 in d_ij do
                                                if not conflict_graph.has_key(ed1) then conflict_graph[ed1] = new HashSet[T]
                                                # add ed1 x ed2 to conflicts graph
                                                for ed2 in d_ji do conflict_graph[ed1].add(ed2)
                                        end
                                end
                        end
                end
                self.conflict_graph = conflict_graph
        end

        # Colorize an array of types
        fun colorize(elts: Array[T]) do
                var min_color = 0

                for t in elts do
                        var color = min_color
                        while not color_free(t, color) do
                                color += 1
                        end
                        t.color = color
                        if color > max_color then max_color = color
                        color = min_color
                end
        end

        # Check if a related type to t already use the color
        fun color_free(t: T, color: Int): Bool do
                if conflict_graph.has_key(t) then
                        for st in conflict_graph[t] do if st.color == color then return false
                end
                for st in t.lin do
                        if st == t then continue
                        if st.color == color then return false
                end
                return true
        end

        # Fill de colored tables
        fun fill_tables do for t in loaded_types.values do fill_table(t)

        fun fill_table(t: T) do
                t.row = new Array[Int]
                for st in t.lin do
                        if t.row.length <= st.color.as(not null) then
                                for i in [t.row.length..st.color.as(not null)[ do t.row.add(0)
                        end
                        t.row[st.color.as(not null)] = st.id
                end

                # stats
                if t.row.length > max_size_tables then max_size_tables = t.row.length
                sum_size_tables += t.row.length
        end

        # Compute table for a type increment: compute linearization of parents and fill the table
        fun compute_table_increment(t: T) do
                compute_linear_ext(t)
                fill_table(t)
        end

        redef fun compute_increment(t) do
                #print "DEBUG: compute increment {t}: is destructive = {is_destructive_increment(t)}"

                # injective color
                max_color += 1
                t.color = max_color

                # parents first
                for st in t.supertypes do
                        if t == st then continue
                        if st.row == null then compute_increment(st)
                end

                if is_destructive_increment(t) then
                        is_valid = false
                else
                        # increment is additive, compute only the type (and newly added parents)
                        is_valid = true
                        compute_table_increment(t)
                end
        end

        # For CL typing, destructive increments are supertypes of already computed types and common types of two already computed types
        redef fun is_destructive_increment(t) do
                if t.mtype isa MGenericType then
                        for ot in loaded_types.values do
                                if ot.mtype.mclass == t.mtype.mclass then
                                        # stats
                                        nb_destructive_increments += 1
                                        nb_gen_destructive_increments += 1
                                        return true
                                end
                        end
                end

                compute_linear_ext(t)
                if t.nb_parents > 1 then
                        # stats
                        nb_destructive_increments += 1
                        if t.mtype isa MGenericType then nb_gen_destructive_increments = 0
                        return true
                end

                return false
        end
end

private class CLType
        super Type

        redef type T: CLType

        # Linearization of super-types including the type itself
        var lin: Array[T] = new Array[T]
        # The color assignated to the type
        var color: nullable Int
        # Number of direct super-types
        var nb_parents: Int = 0
        # All sub types
        var sub_types: HashSet[T] = new HashSet[T]

        # A row is the an array of IDs
        var row: nullable Array[Int]

        # O(1)
        # return row[t.color] == t.id
        redef fun is_subtype(t) do
                if t.color >= row.length then return false
                return row[t.color.as(not null)] == t.id
        end
end

# Wrapper for interpretor legacy typing based on precomputed metalmodel
private class LegacyTyping
        super Typing
        redef type T: LegacyType
        init(interpreter: NaiveInterpreter) do super(interpreter)
        redef fun init_type(id, mtype, supertypes, typing) do return new LegacyType(id, mtype, supertypes, typing)
end

# Wrapper for interpretor legacy typing based on precomputed metalmodel
private class LegacyType
        super Type
        redef type T: LegacyType
        redef fun is_subtype(t) do return self.mtype.is_subtype(typing.interpreter.mainmodule, typing.interpreter.frame.arguments.first.mtype.as(MClassType), t.mtype)
end

# Tools

private class Cache

        var elements: Array[CachePair]
        var size: Int
        var cache: nullable CachePair

        init(size: Int) do
                self.size = size
                self.elements = new Array[CachePair].with_capacity(size)
        end

        # Add a response to the cache
        fun add(t: Type, res: Bool) do
                var pair = new CachePair(t, res)
                elements.insert(pair, 0)
                if elements.length > size then elements.pop
        end

        # Check if the cache contains the subtype test response
        fun contains(t: Type): Bool do
                for e in elements do
                        if e.t == t then
                                cache = e
                                return true
                        end
                end
                return false
        end

        # Get a subtype test response from the cache
        # ensure contains before
        fun response(t: Type): Bool do
                if cache != null and cache.t == t then return cache.res

                for e in elements do if e.t == t then return e.res

                print "IC-ERROR: Cache fault"
                abort
        end
end

private class CachePair
        var t: Type
        var res: Bool
end

# Add operator - to Array
redef class Array[T]
        # Return a new array with the elements only contened in 'self' and not in 'o'
        fun -(o: Array[T]): Array[T] do
                var res = new Array[T]
                for e in self do if not o.has(e) then res.add(e)
                return res
        end
end

# A sorter for reversed linearization of types
private class TypeSorter
        super AbstractSorter[Type]

        redef fun compare(a, b) do
                if a == b then
                        return 0
                else if a.is_subtype_fallback(b) then
                        return 1
                end
                return -1
        end
end