From 36900363c857a1e84700688bb3cf2f64cb334922 Mon Sep 17 00:00:00 2001 From: Jean Privat Date: Mon, 3 Feb 2014 14:36:35 -0500 Subject: [PATCH] remove bit-rotting interpretor_type_test.nit Change-Id: I72b1ad766adcfad1eb00d58167af2346c2ed84f4 Signed-off-by: Jean Privat --- src/interpretor_type_test.nit | 1110 ----------------------------------------- 1 file changed, 1110 deletions(-) delete mode 100644 src/interpretor_type_test.nit diff --git a/src/interpretor_type_test.nit b/src/interpretor_type_test.nit deleted file mode 100644 index b023130..0000000 --- a/src/interpretor_type_test.nit +++ /dev/null @@ -1,1110 +0,0 @@ -# This file is part of NIT ( http://www.nitlanguage.org ). -# -# Copyright 2012 Alexandre Terrasa -# -# 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 - var opt_ic_threshold_count = new OptionInt("Threshold count. Take an integer", 0, "--ic-threshold-count") - # --ic-cache-size - 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 -- 1.7.9.5