model: new metamodel

[nit.git] / src / runtime_type.nit

# This file is part of NIT ( http://www.nitlanguage.org ).
#
# Copyright 2012 Jean Privat <jean@pryen.org>
#
# 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.


# Rapid type analysis on the AST with heterogenous generics and customization
#
# Rapid type analysis is an analyse that aproximates the set of live classes
# and the set of live methods starting from the entry point of the program.
# These two sets are interdependant and computed together.
# It is quite efficient but the type set is global such pollute each call site.
#
# Heterogenous generics means that each intancied generic class is associated
# to a distinct runtime type.
# Heterogenous generics has the advantage to resolve the the formal generic
# parameters types but increase the number of types.
# More important, heterogenous generics cannot deal with infinite number of runtime
# types since the analyse tries to list them all (so some programs will be badly refused)
#
# Customization means that each method definition is analyzed one per runtime
# type of receiver.
# Customization have the following advantages:
#  * `self' is monomorphic
#  * virtual types are all resolved
#  * live attributes can be determined on each class
# But the big disavantage to explode the number of runtime method: each method
# definition for each runtime type that need it
module runtime_type

import model
import modelbuilder
import typing
import auto_super_init

redef class MModule
        var main_type: nullable MClassType
        var main_init: nullable MMethod
        var main_method: nullable MMethod
end

redef class ModelBuilder
        fun do_runtime_type(mainmodule: MModule): RuntimeTypeAnalysis
        do
                var model = self.model
                var analysis = new RuntimeTypeAnalysis(self, mainmodule)
                var nmodule = self.nmodules.first
                var mainclass = self.try_get_mclass_by_name(nmodule, mainmodule, "Sys")
                assert mainclass != null
                var props = model.get_mproperties_by_name("main")
                assert props.length == 1
                var methods = props.first.lookup_definitions(mainmodule, mainclass.mclass_type)
                assert methods.length == 1 else print methods.join(", ")
                var maintype = mainclass.mclass_type
                analysis.add_type(maintype)
                mainmodule.main_type = maintype
                var initprop = self.try_get_mproperty_by_name2(nmodule, mainmodule, maintype, "init")
                if initprop != null then
                        assert initprop isa MMethod
                        analysis.add_monomorphic_send(maintype, initprop)
                end
                mainmodule.main_init = initprop
                var mainprop = self.try_get_mproperty_by_name2(nmodule, mainmodule, maintype, "main")
                if mainprop != null then
                        assert mainprop isa MMethod
                        analysis.add_monomorphic_send(maintype, mainprop)
                end
                mainmodule.main_method = mainprop
                analysis.run_analysis
                return analysis
        end
end

class RuntimeTypeAnalysis
        var modelbuilder: ModelBuilder
        var mainmodule: MModule
        var live_types: HashSet[MClassType] = new HashSet[MClassType]
        var live_cast_types: HashSet[MClassType] = new HashSet[MClassType]
        var polymorphic_methods: HashSet[MMethod] = new HashSet[MMethod]
        var live_methoddefs: HashSet[MMethodDef] = new HashSet[MMethodDef]
        var runtime_methods: HashSet[RuntimeMethod] = new HashSet[RuntimeMethod]
        var live_send_site: HashSet[RuntimeSendSite] = new HashSet[RuntimeSendSite]

        private var todo: List[RuntimeMethod] = new List[RuntimeMethod]

        fun add_type(mtype: MClassType)
        do
                if self.live_types.has(mtype) then return

                assert not mtype.need_anchor
                self.live_types.add(mtype)

                for rss in self.live_send_site do
                        if not mtype.is_subtype(self.mainmodule, null, rss.receiver) then continue
                        if mtype.has_mproperty(self.mainmodule, rss.mmethod) then
                                self.add_monomorphic_send(mtype, rss.mmethod)
                        end
                end
        end

        fun add_send(mtype: MClassType, mmethod: MMethod)
        do
                var rss = new RuntimeSendSite(mmethod, mtype)
                if self.live_send_site.has(rss) then return

                self.live_send_site.add(rss)
                self.polymorphic_methods.add(mmethod)

                for mtype2 in self.live_types do
                        if not mtype2.is_subtype(self.mainmodule, null, mtype) then continue
                        if mtype2.has_mproperty(self.mainmodule, mmethod) then
                                self.add_monomorphic_send(mtype2, mmethod)
                        end
                end
        end

        fun add_monomorphic_send(mtype: MClassType, mmethod: MMethod)
        do
                assert self.live_types.has(mtype)
                var defs = mmethod.lookup_definitions(self.mainmodule, mtype)
                if defs.is_empty then return
                assert defs.length == 1 else print "conflict on {mtype} for {mmethod}: {defs.join(" ")}"
                self.add_static_call(mtype, defs.first)
        end

        fun add_static_call(mtype: MClassType, mmethoddef: MMethodDef)
        do
                assert self.live_types.has(mtype)
                var rm = new RuntimeMethod(mmethoddef, mtype)
                if self.runtime_methods.has(rm) then return
                self.runtime_methods.add(rm)
                self.todo.add(rm)
                self.live_methoddefs.add(mmethoddef)
        end

        fun add_cast_type(mtype: MClassType)
        do
                if self.live_cast_types.has(mtype) then return

                assert not mtype.need_anchor
                self.live_cast_types.add(mtype)
        end

        fun run_analysis
        do
                while not todo.is_empty do
                        var mr = todo.shift
                        if not self.modelbuilder.mpropdef2npropdef.has_key(mr.mmethoddef) then
                                # It is an init for a class?
                                if mr.mmethoddef.mproperty.name == "init" then
                                        var nclassdef = self.modelbuilder.mclassdef2nclassdef[mr.mmethoddef.mclassdef]
                                        var super_inits = nclassdef.super_inits
                                        if super_inits != null then
                                                #assert args.length == 1
                                                for su in super_inits do
                                                        self.add_monomorphic_send(mr.receiver, su)
                                                end
                                        end

                                else
                                        abort
                                end
                                continue
                        end
                        var npropdef = self.modelbuilder.mpropdef2npropdef[mr.mmethoddef]
                        if npropdef isa AConcreteMethPropdef then
                                #npropdef.debug("Visit {mr.mmethoddef} for {mr.receiver}")
                                var nclassdef = npropdef.parent.as(AClassdef)
                                var mmethoddef = npropdef.mpropdef.as(not null)
                                var auto_super_inits = npropdef.auto_super_inits
                                if auto_super_inits != null then
                                        for auto_super_init in auto_super_inits do
                                                self.add_monomorphic_send(mr.receiver, auto_super_init)
                                        end
                                end
                                var v = new RuntimeTypeVisitor(self, nclassdef, mmethoddef, mr.receiver)
                                v.enter_visit(npropdef.n_block)
                        else if npropdef isa ADeferredMethPropdef then
                                # nothing to do (maybe add a waring?)
                        else if npropdef isa AAttrPropdef then
                                # nothing to do
                        else if npropdef isa AInternMethPropdef or npropdef isa AExternMethPropdef then
                                # UGLY: We force the "instantation" of the concrete return type if any
                                var ret = mr.mmethoddef.msignature.return_mtype
                                if ret != null and ret isa MClassType and ret.mclass.kind != abstract_kind and ret.mclass.kind != interface_kind then
                                        ret = ret.anchor_to(self.mainmodule, mr.receiver)
                                        self.add_type(ret)
                                end
                        else if npropdef isa AExternInitPropdef then
                                self.add_type(mr.receiver)
                        else
                                npropdef.debug("Not yet implemented")
                                abort
                        end
                end
        end
end

class RuntimeMethod
        var mmethoddef: MMethodDef
        var receiver: MClassType

        redef fun ==(o)
        do
                return o isa RuntimeMethod and o.mmethoddef == self.mmethoddef and o.receiver == self.receiver
        end

        redef fun hash
        do
                return self.mmethoddef.hash + self.receiver.hash
        end
end

class RuntimeSendSite
        var mmethod: MMethod
        var receiver: MClassType

        redef fun ==(o)
        do
                return o isa RuntimeSendSite and o.mmethod == self.mmethod and o.receiver == self.receiver
        end

        redef fun hash
        do
                return self.mmethod.hash + self.receiver.hash
        end
end

private class RuntimeTypeVisitor
        super Visitor

        var analysis: RuntimeTypeAnalysis

        var nclassdef: AClassdef

        var mmethoddef: MMethodDef

        var receiver: MClassType

        init(analysis: RuntimeTypeAnalysis, nclassdef: AClassdef, mmethoddef: MMethodDef, receiver: MClassType)
        do
                self.analysis = analysis
                self.nclassdef = nclassdef
                self.mmethoddef = mmethoddef
                self.receiver = receiver
        end

        # Adapt and remove nullable
        # return null if we got the null type
        fun cleanup_type(mtype: MType): nullable MClassType
        do
                mtype = mtype.anchor_to(self.analysis.mainmodule, self.receiver)
                if mtype isa MNullType then return null
                if mtype isa MNullableType then mtype = mtype.mtype
                assert mtype isa MClassType
                assert not mtype.need_anchor
                return mtype
        end

        fun add_type(mtype: MType)
        do
                var runtimetype = cleanup_type(mtype)
                if runtimetype == null then return # we do not care about null

                self.analysis.add_type(runtimetype)
                #self.current_node.debug("add_type {runtimetype}")
        end

        fun add_send(mtype: MType, mproperty: MMethod)
        do
                var runtimetype = cleanup_type(mtype)
                if runtimetype == null then return # we do not care about null

                analysis.add_send(runtimetype, mproperty)
                #self.current_node.debug("add_send {mproperty}")
        end

        fun add_monomorphic_send(mtype: MType, mproperty: MMethod)
        do
                var runtimetype = cleanup_type(mtype)
                if runtimetype == null then return # we do not care about null

                self.analysis.add_monomorphic_send(runtimetype, mproperty)
                #self.current_node.debug("add_static call {runtimetype} {mproperty}")
        end

        fun add_cast_type(mtype: MType)
        do
                var runtimetype = cleanup_type(mtype)
                if runtimetype == null then return # we do not care about null

                self.analysis.add_cast_type(runtimetype)
                #self.current_node.debug("add_cast_type {runtimetype}")
        end

        redef fun visit(node)
        do
                if node == null then return
                node.accept_runtime_type_vistor(self)
                node.visit_all(self)
        end

        # Force to get the primitive class named `name' or abort
        fun get_class(name: String): MClass
        do
                var cla = analysis.mainmodule.model.get_mclasses_by_name(name)
                if cla == null then
                        if name == "Bool" then
                                var c = new MClass(analysis.mainmodule, name, 0, enum_kind, public_visibility)
                                var cladef = new MClassDef(analysis.mainmodule, c.mclass_type, new Location(null, 0,0,0,0), new Array[String])
                                return c
                        end
                        self.current_node.debug("Fatal Error: no primitive class {name}")
                        abort
                end
                assert cla.length == 1 else print cla.join(", ")
                return cla.first
        end

        # Force to get the primitive property named `name' in the instance `recv' or abort
        fun get_method(recv: MType, name: String): MMethod
        do
                var runtimetype = cleanup_type(recv)
                if runtimetype == null then abort

                var props = self.analysis.mainmodule.model.get_mproperties_by_name(name)
                if props == null then
                        self.current_node.debug("Fatal Error: no primitive property {name} on {runtimetype}")
                        abort
                end
                var res: nullable MMethod = null
                for mprop in props do
                        assert mprop isa MMethod
                        if not runtimetype.has_mproperty(self.analysis.mainmodule, mprop) then continue
                        if mprop.is_init and mprop.intro_mclassdef.mclass != runtimetype.mclass then continue
                        if res == null then
                                res = mprop
                        else
                                self.current_node.debug("Fatal Error: ambigous property name '{name}'; conflict between {mprop.full_name} and {res.full_name}")
                                abort
                        end
                end
                if res == null then
                        self.current_node.debug("Fatal Error: no primitive property {name} on {runtimetype}")
                        abort
                end
                return res
        end
end

###

redef class ANode
        private fun accept_runtime_type_vistor(v: RuntimeTypeVisitor)
        do
        end
end

redef class AIntExpr
        redef fun accept_runtime_type_vistor(v)
        do
                v.add_type(self.mtype.as(not null))
        end
end

redef class AFloatExpr
        redef fun accept_runtime_type_vistor(v)
        do
                v.add_type(self.mtype.as(not null))
        end
end

redef class ACharExpr
        redef fun accept_runtime_type_vistor(v)
        do
                v.add_type(self.mtype.as(not null))
        end
end

redef class AArrayExpr
        redef fun accept_runtime_type_vistor(v)
        do
                var mtype = self.mtype.as(not null)
                v.add_type(mtype)
                var native = v.get_class("NativeArray").get_mtype([mtype.as(MGenericType).arguments.first])
                v.add_type(native)
                var prop = v.get_method(mtype, "with_native")
                v.add_monomorphic_send(mtype, prop)
        end
end

redef class AStringFormExpr
        redef fun accept_runtime_type_vistor(v)
        do
                var mtype = self.mtype.as(not null)
                v.add_type(mtype)
                var native = v.get_class("NativeString").mclass_type
                v.add_type(native)
                var prop = v.get_method(mtype, "from_cstring")
                v.add_monomorphic_send(mtype, prop)
        end
end

redef class ASuperstringExpr
        redef fun accept_runtime_type_vistor(v)
        do
                var arraytype = v.get_class("Array").get_mtype([v.get_class("Object").mclass_type])
                v.add_type(arraytype)
                var prop = v.get_method(arraytype, "join")
                v.add_monomorphic_send(arraytype, prop)
        end
end

redef class ACrangeExpr
        redef fun accept_runtime_type_vistor(v)
        do
                var mtype = self.mtype.as(not null)
                v.add_type(mtype)
                var prop = v.get_method(mtype, "init")
                v.add_monomorphic_send(mtype, prop)
        end
end

redef class AOrangeExpr
        redef fun accept_runtime_type_vistor(v)
        do
                var mtype = self.mtype.as(not null)
                v.add_type(mtype)
                var prop = v.get_method(mtype, "without_last")
                v.add_monomorphic_send(mtype, prop)
        end
end

redef class ATrueExpr
        redef fun accept_runtime_type_vistor(v)
        do
                v.add_type(self.mtype.as(not null))
        end
end

redef class AFalseExpr
        redef fun accept_runtime_type_vistor(v)
        do
                v.add_type(self.mtype.as(not null))
        end
end

redef class AIsaExpr
        redef fun accept_runtime_type_vistor(v)
        do
                v.add_cast_type(self.cast_type.as(not null))
        end
end

redef class AAsCastExpr
        redef fun accept_runtime_type_vistor(v)
        do
                v.add_cast_type(self.mtype.as(not null))
        end
end

#

redef class ASendExpr
        redef fun accept_runtime_type_vistor(v)
        do
                var mproperty = self.mproperty.as(not null)
                if n_expr isa ASelfExpr then
                        v.add_monomorphic_send(v.receiver, mproperty)
                else
                        var recvtype = self.n_expr.mtype.as(not null)
                        v.add_send(recvtype, mproperty)
                end
        end
end

redef class ASendReassignFormExpr
        redef fun accept_runtime_type_vistor(v)
        do
                v.add_send(self.read_type.as(not null), self.reassign_property.mproperty)
                var mproperty = self.mproperty.as(not null)
                var write_mproperty = self.write_mproperty.as(not null)
                if n_expr isa ASelfExpr then
                        v.add_monomorphic_send(v.receiver, mproperty)
                        v.add_monomorphic_send(v.receiver, write_mproperty)
                else
                        var recvtype = self.n_expr.mtype.as(not null)
                        v.add_send(recvtype, mproperty)
                        v.add_send(recvtype, write_mproperty)
                end
        end
end

redef class AVarReassignExpr
        redef fun accept_runtime_type_vistor(v)
        do
                v.add_send(self.read_type.as(not null), self.reassign_property.mproperty)
        end
end

redef class AAttrReassignExpr
        redef fun accept_runtime_type_vistor(v)
        do
                v.add_send(self.read_type.as(not null), self.reassign_property.mproperty)
        end
end

redef class ASuperExpr
        redef fun accept_runtime_type_vistor(v)
        do
                var mproperty = self.mproperty
                if mproperty != null then
                        v.add_monomorphic_send(v.receiver, mproperty)
                        return
                end

                #FIXME: we do not want an ugly static call!
                var mpropdef = v.mmethoddef
                var mpropdefs = mpropdef.mproperty.lookup_super_definitions(mpropdef.mclassdef.mmodule, mpropdef.mclassdef.bound_mtype)
                if mpropdefs.length != 1 then
                        debug("MPRODFEFS for super {mpropdef} for {v.receiver}: {mpropdefs.join(", ")}")
                end
                var msuperpropdef = mpropdefs.first
                assert msuperpropdef isa MMethodDef
                v.analysis.add_static_call(v.receiver, msuperpropdef)
        end
end

redef class AForExpr
        redef fun accept_runtime_type_vistor(v)
        do
                var recvtype = self.n_expr.mtype.as(not null)
                var colltype = v.get_class("Collection").mclassdefs.first.bound_mtype
                v.add_send(recvtype, v.get_method(colltype, "iterator"))
                var iteratortype = v.get_class("Iterator").mclassdefs.first.bound_mtype
                var objtype = v.get_class("Object").mclass_type
                v.add_send(objtype, v.get_method(iteratortype, "is_ok"))
                v.add_send(objtype, v.get_method(iteratortype, "item"))
                v.add_send(objtype, v.get_method(iteratortype, "next"))
        end
end

redef class ANewExpr
        redef fun accept_runtime_type_vistor(v)
        do
                var recvtype = self.mtype.as(not null)
                v.add_type(recvtype)
                v.add_monomorphic_send(recvtype, mproperty.as(not null))
        end
end