Merge branch 'bench'

[nit.git] / src / rapid_type_analysis.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 and pollutes each call site.
#
# Heterogenous generics means that each intancied generic class is associated
# to a distinct rapid type.
# Heterogenous generics has the advantage to resolve the formal generic
# parameters types but increase the number of types.
# More important, heterogenous generics cannot deal with infinite number of rapid
# 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 rapid
# 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 has the disadvantage to explode the number of rapid method: each method
# definition for each rapid type that need it
module rapid_type_analysis

import model
import modelbuilder
import typing
import auto_super_init

redef class ModelBuilder
        fun do_rapid_type_analysis(mainmodule: MModule): RapidTypeAnalysis
        do
                var time0 = get_time
                self.toolcontext.info("*** RAPID TYPE ANALYSIS ***", 1)

                var model = self.model
                var analysis = new RapidTypeAnalysis(self, mainmodule)
                var nmodule = self.nmodules.first
                var maintype = mainmodule.sys_type
                if maintype == null then return analysis # No entry point
                analysis.add_type(maintype)
                var initprop = mainmodule.try_get_primitive_method("init", maintype)
                if initprop != null then
                        analysis.add_monomorphic_send(maintype, initprop)
                end
                var mainprop = mainmodule.try_get_primitive_method("main", maintype)
                if mainprop != null then
                        analysis.add_monomorphic_send(maintype, mainprop)
                end
                analysis.run_analysis

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

                return analysis
        end
end

# RapidTypeAnalysis looks for alive rapid types in application.
# The entry point of the analysis is the mainmodule of the application.
class RapidTypeAnalysis
        # The modelbuilder used to get the AST.
        var modelbuilder: ModelBuilder

        # The main module of the analysis.
        # Used to perform types operations.
        var mainmodule: MModule

        # The pool to live types.
        # During the analysis, new types are added and combined with
        # live_send_sites to determine new customized_methoddefs to visit
        var live_types: HashSet[MClassType] = new HashSet[MClassType]

        # The pool of types used to perform type checks (isa and as).
        var live_cast_types: HashSet[MClassType] = new HashSet[MClassType]

        # Live method definitions.
        # These method definitions are:
        #  * visited trough a add_send on an already known live_type
        #  * visited trough a add_type for an already known live_send_sites
        #  * visided by a add_monomorphic_send or a add_static_call
        var live_methoddefs: HashSet[MMethodDef] = new HashSet[MMethodDef]

        # The pool of live customized method definitions
        var live_customized_methoddefs: HashSet[CustomizedMethodDef] = new HashSet[CustomizedMethodDef]

        # The pool of live RTA send site
        # During the analysis, new live_send_sites are added and combined with
        # live_types to determine new live_customized_methoddefs to visit
        var live_send_sites: HashSet[RTASendSite] = new HashSet[RTASendSite]

        # The customized method definitions that remain to visit
        private var todo: List[CustomizedMethodDef] = new List[CustomizedMethodDef]

        # Adapt and remove nullable
        # return null if we got the null type
        fun cleanup_type(mtype: MType, recvtype: MClassType): nullable MClassType
        do
                mtype = mtype.anchor_to(self.mainmodule, recvtype)
                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

        # Add a live type to the pool
        #
        # If the types is already live, then do nothing.
        #
        # REQUIRE: not mtype.need_anchor
        fun add_type(mtype: MClassType)
        do
                if self.live_types.has(mtype) then return

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

                # Collect default attributes
                for cd in mtype.collect_mclassdefs(self.mainmodule)
                do
                        var nclassdef = self.modelbuilder.mclassdef2nclassdef[cd]
                        for npropdef in nclassdef.n_propdefs do
                                if not npropdef isa AAttrPropdef then continue
                                var nexpr = npropdef.n_expr
                                if nexpr == null then continue
                                var v = new RapidTypeVisitor(self, nclassdef, npropdef.mpropdef.as(not null), mtype)
                                v.enter_visit(nexpr)
                        end
                end

                for rss in self.live_send_sites 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

        # Add a send site to the pool
        #
        # If the send site is already live, then do nothing.
        fun add_send(mtype: MClassType, mmethod: MMethod)
        do
                var rss = new RTASendSite(mmethod, mtype)
                if self.live_send_sites.has(rss) then return

                self.live_send_sites.add(rss)

                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

        # Add a monomoprhic send.
        # The send site is not added to the pool.
        # The method just determine the associated method definition then
        # performs a static_call
        fun add_monomorphic_send(mtype: MClassType, mmethod: MMethod)
        do
                assert self.live_types.has(mtype)
                if not mtype.has_mproperty(self.mainmodule, mmethod) then return
                var def = mmethod.lookup_first_definition(self.mainmodule, mtype)
                self.add_static_call(mtype, def)
        end

        # Add a customized_methoddefs to the pool
        # Is the customized_methoddefs is already live, then do nothing
        fun add_static_call(mtype: MClassType, mmethoddef: MMethodDef)
        do
                assert self.live_types.has(mtype)
                var rm = new CustomizedMethodDef(mmethoddef, mtype)
                if self.live_customized_methoddefs.has(rm) then return
                self.live_customized_methoddefs.add(rm)
                self.todo.add(rm)
                self.live_methoddefs.add(mmethoddef)
        end

        # Add mtype to the cast pool.
        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)
                self.check_depth(mtype)
        end

        fun check_depth(mtype: MClassType)
        do
                var d = mtype.depth
                if d > 255 then
                        self.modelbuilder.toolcontext.fatal_error(null, "Fatal error: limitation in the rapidtype analysis engine: a type depth of {d} is too important, the problematic type is {mtype}.")
                end
        end

        # Run the analysis until all visitable method definitions are visited.
        fun run_analysis
        do
                # Force Bool
                var classes = self.modelbuilder.model.get_mclasses_by_name("Bool")
                if classes != null then for c in classes do self.add_type(c.mclass_type)

                while not todo.is_empty do
                        var mr = todo.shift

                        var vararg_rank = mr.mmethoddef.msignature.vararg_rank
                        if vararg_rank > -1 then
                                var node = self.modelbuilder.mpropdef2npropdef[mr.mmethoddef]
                                var elttype = mr.mmethoddef.msignature.mparameters[vararg_rank].mtype
                                elttype = elttype.anchor_to(self.mainmodule, mr.receiver)
                                var vararg = self.mainmodule.get_primitive_class("Array").get_mtype([elttype])
                                self.add_type(vararg)
                                self.add_monomorphic_send(vararg, self.modelbuilder.force_get_primitive_method(node, "with_native", vararg, self.mainmodule))
                                var native = self.mainmodule.get_primitive_class("NativeArray").get_mtype([elttype])
                                self.add_type(native)
                        end

                        for i in [0..mr.mmethoddef.msignature.arity[ do
                                var origtype = mr.mmethoddef.mproperty.intro.msignature.mparameters[i].mtype
                                if not origtype.need_anchor then continue # skip non covariant stuff
                                var paramtype = mr.mmethoddef.msignature.mparameters[i].mtype
                                paramtype = self.cleanup_type(paramtype, mr.receiver).as(not null)
                                self.add_cast_type(paramtype)
                        end

                        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 RapidTypeVisitor(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

# A method definitions customized to a specific receiver
class CustomizedMethodDef
        var mmethoddef: MMethodDef
        var receiver: MClassType

        redef fun to_s
        do
                return "{self.mmethoddef}({receiver})"
        end

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

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

# A method invokation site bounded by a specific receiver
class RTASendSite
        var mmethod: MMethod
        var receiver: MClassType

        redef fun ==(o)
        do
                return o isa RTASendSite 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 RapidTypeVisitor
        super Visitor

        var analysis: RapidTypeAnalysis

        var nclassdef: AClassdef

        var mpropdef: MPropDef

        var receiver: MClassType

        init(analysis: RapidTypeAnalysis, nclassdef: AClassdef, mpropdef: MPropDef, receiver: MClassType)
        do
                self.analysis = analysis
                self.nclassdef = nclassdef
                self.mpropdef = mpropdef
                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 rapidtype = cleanup_type(mtype)
                if rapidtype == null then return # we do not care about null

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

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

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

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

                self.analysis.add_monomorphic_send(rapidtype, mproperty)
                #self.current_node.debug("add_monomorphic_send {rapidtype} {mproperty}")
        end

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

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

        redef fun visit(node)
        do
                if node == null then return
                node.accept_rapid_type_vistor(self)
                if node isa AExpr then
                        var implicit_cast_to = node.implicit_cast_to
                        if implicit_cast_to != null then self.add_cast_type(implicit_cast_to)
                end
                # RTA does not enter in AAnnotations
                if not node isa AAnnotations then
                        node.visit_all(self)
                end
        end

        # Force to get the primitive class named `name' or abort
        fun get_class(name: String): MClass
        do
                return self.analysis.mainmodule.get_primitive_class(name)
        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 rapidtype = cleanup_type(recv)
                if rapidtype == null then abort

                return self.analysis.modelbuilder.force_get_primitive_method(self.current_node.as(not null), name, rapidtype, self.analysis.mainmodule)
        end
end

###

redef class ANode
        private fun accept_rapid_type_vistor(v: RapidTypeVisitor)
        do
        end
end

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

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

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

redef class AArrayExpr
        redef fun accept_rapid_type_vistor(v)
        do
                var mtype = self.mtype.as(MClassType)
                v.add_type(mtype)
                var native = v.get_class("NativeArray").get_mtype([mtype.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_rapid_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_rapid_type_vistor(v)
        do
                var arraytype = v.get_class("Array").get_mtype([v.get_class("Object").mclass_type])
                v.add_type(arraytype)
                v.add_type(v.get_class("NativeArray").get_mtype([v.get_class("Object").mclass_type]))
                var prop = v.get_method(arraytype, "join")
                v.add_monomorphic_send(arraytype, prop)
                var prop2 = v.get_method(arraytype, "with_native")
                v.add_monomorphic_send(arraytype, prop2)
        end
end

redef class ACrangeExpr
        redef fun accept_rapid_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_rapid_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_rapid_type_vistor(v)
        do
                v.add_type(self.mtype.as(not null))
        end
end

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

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

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

#

redef class ASendExpr
        redef fun accept_rapid_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_rapid_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_rapid_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_rapid_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_rapid_type_vistor(v)
        do
                var mproperty = self.mproperty
                if mproperty != null then
                        v.add_monomorphic_send(v.receiver, mproperty)
                        return
                end

                var mpropdef = v.mpropdef.lookup_next_definition(v.analysis.mainmodule, v.receiver)
                assert mpropdef isa MMethodDef
                v.analysis.add_static_call(v.receiver, mpropdef)
        end
end

redef class AForExpr
        redef fun accept_rapid_type_vistor(v)
        do
                var recvtype = self.n_expr.mtype.as(not null)
                var colltype = self.coltype.as(not null)
                var itmeth = v.get_method(colltype, "iterator")
                v.add_send(recvtype, itmeth)
                var iteratortype = itmeth.intro.msignature.return_mtype.as(MClassType).mclass.intro.bound_mtype
                var objtype = v.get_class("Object").mclass_type
                v.add_send(objtype, v.get_method(iteratortype, "is_ok"))
                if self.variables.length == 1 then
                        v.add_send(objtype, v.get_method(iteratortype, "item"))
                else if self.variables.length == 2 then
                        v.add_send(objtype, v.get_method(iteratortype, "key"))
                        v.add_send(objtype, v.get_method(iteratortype, "item"))
                else
                        abort
                end
                v.add_send(objtype, v.get_method(iteratortype, "next"))
        end
end

redef class ANewExpr
        redef fun accept_rapid_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