<commit_before># This file is part of NIT ( http://www.nitlanguage.org ).
#
# Copyright 2012 <NAME> <<EMAIL>>
#
# 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 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
		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]

	# 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)
		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

	# 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

			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<commit_msg>rta: consider type tests for covariant signatures<commit_after># This file is part of NIT ( http://www.nitlanguage.org ).
#
# Copyright 2012 <NAME> <<EMAIL>>
#
# 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 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
		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)
		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

	# 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
{'fraction_non_alphanumeric': 0.06640098787606646, 'fraction_numerical': 0.0025258194881005837, 'mean_word_length': 4.361721336142041, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 4, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3715886', 'n_tokens_mistral': 6130, 'n_tokens_neox': 5577, 'n_words': 1916}