# See the License for the specific language governing permissions and
# limitations under the License.
-
# Rapid type analysis on the AST
#
# Rapid type analysis is an analyse that aproximates the set of live classes
# It is quite efficient but the type set is global and pollutes each call site.
module rapid_type_analysis
-import model
-import modelbuilder
-import typing
-import auto_super_init
+import semantize
+private import explain_assert_api
import csv # for live_types_to_csv
-import ordered_tree # for live_methods_to_tree
+private import ordered_tree # for live_methods_to_tree
private import more_collections
redef class ModelBuilder
+ # Performs a rapid-type-analysis on the program associated with `mainmodule`.
fun do_rapid_type_analysis(mainmodule: MModule): RapidTypeAnalysis
do
var analysis = new RapidTypeAnalysis(self, mainmodule)
analysis.run_analysis
+
+ if toolcontext.opt_log.value then
+ var basename = toolcontext.log_directory / mainmodule.name
+ analysis.live_methods_to_tree.write_to_file(basename + ".rta_methods.txt")
+ analysis.live_types_to_csv.write_to_file(basename + ".rta_types.csv")
+ end
+
return analysis
end
end
# live_methods to determine new methoddefs to visit
var live_types = new HashSet[MClassType]
- # The pool of undesolved live types
+ # The pool of unresolved live types
# They are globally resolved at the end of the analaysis
var live_open_types = new HashSet[MClassType]
# Live methods.
var live_methods = new HashSet[MMethod]
+ # Live mmodules.
+ # Those with a live method definitions (see `live_methoddefs`)
+ var live_mmodules = new HashSet[MModule]
+
# Live callsites.
var live_callsites = new HashSet[CallSite]
var mtype = callsite.recv
var anchor = callsite.anchor
if anchor != null then mtype = mtype.anchor_to(callsite.mmodule, anchor)
- mtype = mtype.as_notnullable
- assert mtype isa MClassType
- mtype = mtype.mclass.intro.bound_mtype
+ mtype = mtype.undecorate
+ if mtype isa MClassType then mtype = mtype.mclass.intro.bound_mtype
var mproperty = callsite.mproperty
var res = live_targets_cache[mtype, mproperty]
if res != null then return res
# Return a ready-to-save CSV document objet that agregates informations about live types.
# Each discovered type is listed in a line, with its status: resolution, liveness, cast-liveness.
# Note: types are listed in an alphanumeric order to improve human reading.
- fun live_types_to_csv: CSVDocument
+ fun live_types_to_csv: CsvDocument
do
# Gather all kind of type
var typeset = new HashSet[MType]
typeset.add_all(live_open_cast_types)
var types = typeset.to_a
(new CachedAlphaComparator).sort(types)
- var res = new CSVDocument
+ var res = new CsvDocument
+ res.separator = ';'
res.header = ["Type", "Resolution", "Liveness", "Cast-liveness"]
for t in types do
var reso
if t isa MClassType and (live_types.has(t) or live_open_types.has(t)) then live = "LIVE" else live = "DEAD"
var cast
if live_cast_types.has(t) or live_open_cast_types.has(t) then cast = "CAST LIVE" else cast = "CAST DEAD"
- res.add_line(t, reso, live, cast)
+ res.add_record(t, reso, live, cast)
end
return res
end
# Force primitive types
force_alive("Bool")
- force_alive("Int")
force_alive("Float")
force_alive("Char")
+ force_alive("Pointer")
+ force_alive("Byte")
+ force_alive("Int")
+ force_alive("Int8")
+ force_alive("Int16")
+ force_alive("UInt16")
+ force_alive("Int32")
+ force_alive("UInt32")
while not todo.is_empty do
var mmethoddef = todo.shift
var mmeth = mmethoddef.mproperty
+ var msignature = mmethoddef.msignature
+ if msignature == null then continue # Skip broken method
+
#print "# visit {mmethoddef}"
var v = new RapidTypeVisitor(self, mmethoddef.mclassdef.bound_mtype, mmethoddef)
- var vararg_rank = mmethoddef.msignature.vararg_rank
+ var vararg_rank = msignature.vararg_rank
if vararg_rank > -1 then
- var node = self.modelbuilder.mpropdef2npropdef[mmethoddef]
- var elttype = mmethoddef.msignature.mparameters[vararg_rank].mtype
+ var node = self.modelbuilder.mpropdef2node(mmethoddef)
+ var elttype = msignature.mparameters[vararg_rank].mtype
#elttype = elttype.anchor_to(self.mainmodule, v.receiver)
- var vararg = self.mainmodule.get_primitive_class("Array").get_mtype([elttype])
+ var vararg = self.mainmodule.array_type(elttype)
v.add_type(vararg)
- var native = self.mainmodule.get_primitive_class("NativeArray").get_mtype([elttype])
+ var native = self.mainmodule.native_array_type(elttype)
v.add_type(native)
v.add_monomorphic_send(vararg, self.modelbuilder.force_get_primitive_method(node, "with_native", vararg.mclass, self.mainmodule))
end
# TODO? new_msignature
- var sig = mmethoddef.msignature.as(not null)
+ var sig = msignature
var osig = mmeth.intro.msignature.as(not null)
for i in [0..sig.arity[ do
var origtype = osig.mparameters[i].mtype
add_cast(paramtype)
end
- if not modelbuilder.mpropdef2npropdef.has_key(mmethoddef) then
- # It is an init for a class?
- if mmeth.name == "init" then
- var nclassdef = self.modelbuilder.mclassdef2nclassdef[mmethoddef.mclassdef]
- assert mmethoddef == nclassdef.mfree_init
- var super_inits = nclassdef.super_inits
- if super_inits != null then
- #assert args.length == 1
- for su in super_inits do
- v.add_monomorphic_send(v.receiver, su)
- end
- end
+ if mmethoddef.is_abstract then continue
+
+ var npropdef = modelbuilder.mpropdef2node(mmethoddef)
- if mmethoddef.mproperty.is_root_init and not mmethoddef.is_intro then
+ if npropdef isa AClassdef then
+ if mmethoddef.mproperty.is_root_init then
+ if not mmethoddef.is_intro then
self.add_super_send(v.receiver, mmethoddef)
end
else
+ npropdef.debug "cannot RTA {mmethoddef}"
abort
end
continue
+ else if mmethoddef.constant_value != null then
+ # Make the return type live
+ v.add_type(msignature.return_mtype.as(MClassType))
+ continue
+ else if npropdef == null then
+ abort
end
- var npropdef = modelbuilder.mpropdef2npropdef[mmethoddef]
-
- if npropdef isa AMethPropdef then
+ if npropdef isa AMethPropdef then
var auto_super_inits = npropdef.auto_super_inits
if auto_super_inits != null then
for auto_super_init in auto_super_inits do
end
end
- if mmeth.is_new then
- v.add_type(v.receiver)
- else if mmethoddef.is_intern or mmethoddef.is_extern then
+ if mmethoddef.is_intern or mmethoddef.is_extern then
# UGLY: We force the "instantation" of the concrete return type if any
- var ret = mmethoddef.msignature.return_mtype
+ var ret = msignature.return_mtype
if ret != null and ret isa MClassType and ret.mclass.kind != abstract_kind and ret.mclass.kind != interface_kind then
v.add_type(ret)
end
if not ot.can_resolve_for(t, t, mainmodule) then continue
var rt = ot.anchor_to(mainmodule, t)
if live_types.has(rt) then continue
+ if not rt.is_legal_in(mainmodule) then continue
+ if not check_depth(rt) then continue
#print "{ot}/{t} -> {rt}"
live_types.add(rt)
- todo_types.add(rt)
- check_depth(rt)
+ # unshift means a deep-first visit.
+ # So that the `check_depth` limit is reached sooner.
+ todo_types.unshift(rt)
end
end
#print "MType {live_types.length}: {live_types.join(", ")}"
for t in live_types do
if not ot.can_resolve_for(t, t, mainmodule) then continue
var rt = ot.anchor_to(mainmodule, t)
+ if not rt.is_legal_in(mainmodule) then continue
live_cast_types.add(rt)
#print " {ot}/{t} -> {rt}"
end
#print "cast MType {live_cast_types.length}: {live_cast_types.join(", ")}"
end
- private fun check_depth(mtype: MClassType)
+ private fun check_depth(mtype: MClassType): Bool
do
var d = mtype.length
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}.")
+ 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}`.")
+ return false
end
+ return true
end
fun add_new(recv: MClassType, mtype: MClassType)
var bound_mtype = mtype.anchor_to(mainmodule, recv)
for cd in bound_mtype.collect_mclassdefs(mainmodule)
do
- if not self.modelbuilder.mclassdef2nclassdef.has_key(cd) then continue
- 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 mpropdef = npropdef.mpropdef.as(not null)
+ for npropdef in modelbuilder.collect_attr_propdef(cd) do
+ if not npropdef.has_value then continue
+
+ var mpropdef = npropdef.mreadpropdef.as(not null)
var v = new RapidTypeVisitor(self, bound_mtype, mpropdef)
- v.enter_visit(nexpr)
+ v.enter_visit(npropdef.n_expr)
+ v.enter_visit(npropdef.n_block)
end
end
do
if live_methoddefs.has(mpropdef) then return
live_methoddefs.add(mpropdef)
+ live_mmodules.add(mpropdef.mclassdef.mmodule)
todo.add(mpropdef)
var mproperty = mpropdef.mproperty
if mproperty.mpropdefs.length <= 1 then return
# If all definitions of a method are live, we can remove the definition of the totry set
for d in mproperty.mpropdefs do
- if d.is_abstract then continue
if not live_methoddefs.has(d) then return
end
#print "full property: {mpropdef.mproperty} for {mpropdef.mproperty.mpropdefs.length} definitions"
var receiver: MClassType
var mpropdef: MPropDef
- init(analysis: RapidTypeAnalysis, receiver: MClassType, mpropdef: MPropDef)
+ init
do
- self.analysis = analysis
- self.receiver = receiver
- self.mpropdef = mpropdef
assert not receiver.need_anchor
end
redef fun visit(n)
do
- n.accept_rapid_type_visitor(self)
if n isa AExpr then
- var implicit_cast_to = n.implicit_cast_to
- if implicit_cast_to != null then self.add_cast_type(implicit_cast_to)
+ if n.mtype != null or n.is_typed then
+ n.accept_rapid_type_visitor(self)
+ var implicit_cast_to = n.implicit_cast_to
+ if implicit_cast_to != null then self.add_cast_type(implicit_cast_to)
+ end
+ else
+ n.accept_rapid_type_visitor(self)
end
# RTA does not enter in AAnnotations
do
mtype = mtype.anchor_to(self.analysis.mainmodule, self.receiver)
if mtype isa MNullType then return null
- mtype = mtype.as_notnullable
+ mtype = mtype.undecorate
assert mtype isa MClassType
assert not mtype.need_anchor
return mtype
end
- fun get_class(name: String): MClass
- do
- return analysis.mainmodule.get_primitive_class(name)
- end
-
fun get_method(recv: MType, name: String): MMethod
do
var mtype = cleanup_type(recv)
end
end
-redef class AIntExpr
- redef fun accept_rapid_type_visitor(v)
+redef class AExpr
+ # Make the `mtype` of the expression live
+ # Used by literals and instantiations
+ fun allocate_mtype(v: RapidTypeVisitor)
do
+ var mtype = self.mtype
+ if not mtype isa MClassType then return
v.add_type(self.mtype.as(MClassType))
end
end
+redef class AIntegerExpr
+ redef fun accept_rapid_type_visitor(v)
+ do
+ allocate_mtype(v)
+ end
+end
+
redef class AFloatExpr
redef fun accept_rapid_type_visitor(v)
do
- v.add_type(self.mtype.as(MClassType))
+ allocate_mtype(v)
end
end
redef class ACharExpr
redef fun accept_rapid_type_visitor(v)
do
- v.add_type(self.mtype.as(MClassType))
+ allocate_mtype(v)
end
end
do
var mtype = self.mtype.as(MClassType)
v.add_type(mtype)
- var native = v.analysis.mainmodule.get_primitive_class("NativeArray").get_mtype([mtype.arguments.first])
+ var native = v.analysis.mainmodule.native_array_type(mtype.arguments.first)
v.add_type(native)
mtype = v.cleanup_type(mtype).as(not null)
var prop = v.get_method(mtype, "with_native")
v.add_monomorphic_send(mtype, prop)
+ v.add_callsite(with_capacity_callsite)
+ v.add_callsite(push_callsite)
end
end
redef class AStringFormExpr
redef fun accept_rapid_type_visitor(v)
do
- var native = v.get_class("NativeString").mclass_type
+ var native = v.analysis.mainmodule.c_string_type
v.add_type(native)
- var prop = v.get_method(native, "to_s_with_length")
+ var prop = v.get_method(native, "to_s_unsafe")
v.add_monomorphic_send(native, prop)
+ v.add_callsite(to_re)
+ v.add_callsite(ignore_case)
+ v.add_callsite(newline)
+ v.add_callsite(extended)
+ v.add_callsite(to_bytes_with_copy)
end
end
redef class ASuperstringExpr
redef fun accept_rapid_type_visitor(v)
do
- var arraytype = v.get_class("Array").get_mtype([v.get_class("Object").mclass_type])
+ var mmodule = v.analysis.mainmodule
+ var object_type = mmodule.string_type
+ var arraytype = mmodule.array_type(object_type)
v.add_type(arraytype)
- v.add_type(v.get_class("NativeArray").get_mtype([v.get_class("Object").mclass_type]))
+ var nattype = mmodule.native_array_type(object_type)
+ v.add_type(nattype)
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)
+ v.add_monomorphic_send(nattype, v.get_method(nattype, "native_to_s"))
end
end
redef class ACrangeExpr
redef fun accept_rapid_type_visitor(v)
do
- var mtype = self.mtype.as(MClassType)
+ var mtype = self.mtype
+ if not mtype isa MClassType then return
v.add_type(mtype)
v.add_callsite(init_callsite)
end
redef class AOrangeExpr
redef fun accept_rapid_type_visitor(v)
do
- var mtype = self.mtype.as(MClassType)
+ var mtype = self.mtype
+ if not mtype isa MClassType then return
v.add_type(mtype)
v.add_callsite(init_callsite)
end
redef class ATrueExpr
redef fun accept_rapid_type_visitor(v)
do
- v.add_type(self.mtype.as(MClassType))
+ allocate_mtype(v)
end
end
redef class AFalseExpr
redef fun accept_rapid_type_visitor(v)
do
- v.add_type(self.mtype.as(MClassType))
+ allocate_mtype(v)
end
end
redef class AIsaExpr
redef fun accept_rapid_type_visitor(v)
do
- v.add_cast_type(self.cast_type.as(not null))
+ var cast_type = self.cast_type
+ if cast_type == null then return
+ v.add_cast_type(cast_type)
end
end
redef class AAsCastExpr
redef fun accept_rapid_type_visitor(v)
do
- v.add_cast_type(self.mtype.as(not null))
+ var mtype = self.mtype
+ if mtype == null then return
+ v.add_cast_type(mtype)
+ end
+end
+
+redef class AAssertExpr
+ redef fun accept_rapid_type_visitor(v)
+ do
+ if can_explain_assert(v.analysis.modelbuilder) then
+ var str = explain_assert_str
+ if str != null then str.accept_rapid_type_visitor(v)
+ end
+ end
+
+ # Does `modelbuilder` know the classes to build a superstring to explain a failed assert?
+ private fun can_explain_assert(modelbuilder: ModelBuilder): Bool
+ do
+ var nas = modelbuilder.model.get_mclasses_by_name("NativeArray")
+ if nas == null then return false
+
+ nas = modelbuilder.model.get_mclasses_by_name("Array")
+ if nas == null or nas.is_empty then return false
+
+ nas = modelbuilder.model.get_mclasses_by_name("String")
+ if nas == null or nas.is_empty then return false
+
+ return true
end
end
end
end
+redef class ACallrefExpr
+ redef fun accept_rapid_type_visitor(v)
+ do
+ super
+ v.add_type(mtype.as(MClassType))
+ end
+end
redef class ASendReassignFormExpr
redef fun accept_rapid_type_visitor(v)
end
end
-redef class AForExpr
+redef class AForGroup
redef fun accept_rapid_type_visitor(v)
do
v.add_callsite(self.method_iterator)
abort
end
v.add_callsite(self.method_next)
+ var mf = self.method_finish
+ if mf != null then v.add_callsite(mf)
end
end
redef class ANewExpr
redef fun accept_rapid_type_visitor(v)
do
- var mtype = self.mtype.as(MClassType)
+ var mtype = self.recvtype.as(not null)
v.add_type(mtype)
v.add_callsite(callsite)
end
nitlanguage / nit.git / blobdiff