The entry point of the analysis is the mainmodule of the application.
nitc :: RapidTypeAnalysis :: _live_callsites
Live callsites.nitc :: RapidTypeAnalysis :: _live_cast_types
The pool of types used to perform type checks (isa and as).nitc :: RapidTypeAnalysis :: _live_classes
Live (instantiated) classes.nitc :: RapidTypeAnalysis :: _live_methoddefs
Live method definitions.nitc :: RapidTypeAnalysis :: _live_methods
Live methods.nitc :: RapidTypeAnalysis :: _live_mmodules
Live mmodules.nitc :: RapidTypeAnalysis :: _live_open_cast_types
The pool of undesolved types used to perform type checks (isa and as).nitc :: RapidTypeAnalysis :: _live_open_types
The pool of unresolved live typesnitc :: RapidTypeAnalysis :: _live_super_sends
Live call-to-super.nitc :: RapidTypeAnalysis :: _live_types
The pool to live types.nitc :: RapidTypeAnalysis :: _mainmodule
The main module of the analysis.nitc :: RapidTypeAnalysis :: _modelbuilder
The modelbuilder used to get the AST.nitc :: RapidTypeAnalysis :: _todo
The method definitions that remain to visitnitc :: RapidTypeAnalysis :: _totry_methods
Methods that are still candidate to the try_sendnitc :: RapidTypeAnalysis :: _totry_methods_to_remove
Methods that are are no more candidate to the try_sendnitc :: RapidTypeAnalysis :: _try_methods
Methods that are or were candidate to the try_sendnitc :: RapidTypeAnalysis :: add_call
nitc :: RapidTypeAnalysis :: add_cast
nitc :: RapidTypeAnalysis :: add_new
nitc :: RapidTypeAnalysis :: check_depth
nitc :: RapidTypeAnalysis :: defaultinit
nitc :: RapidTypeAnalysis :: force_alive
nitc :: RapidTypeAnalysis :: live_callsites=
Live callsites.nitc :: RapidTypeAnalysis :: live_cast_types
The pool of types used to perform type checks (isa and as).nitc :: RapidTypeAnalysis :: live_cast_types=
The pool of types used to perform type checks (isa and as).nitc :: RapidTypeAnalysis :: live_classes
Live (instantiated) classes.nitc :: RapidTypeAnalysis :: live_classes=
Live (instantiated) classes.nitc :: RapidTypeAnalysis :: live_methoddefs
Live method definitions.nitc :: RapidTypeAnalysis :: live_methoddefs=
Live method definitions.nitc :: RapidTypeAnalysis :: live_methods=
Live methods.nitc :: RapidTypeAnalysis :: live_methods_to_tree
Return a ready-to-save OrderedTree object that agregates infomration about live methods.nitc :: RapidTypeAnalysis :: live_mmodules=
Live mmodules.nitc :: RapidTypeAnalysis :: live_open_cast_types
The pool of undesolved types used to perform type checks (isa and as).nitc :: RapidTypeAnalysis :: live_open_cast_types=
The pool of undesolved types used to perform type checks (isa and as).nitc :: RapidTypeAnalysis :: live_open_types
The pool of unresolved live typesnitc :: RapidTypeAnalysis :: live_open_types=
The pool of unresolved live typesnitc :: RapidTypeAnalysis :: live_super_sends
Live call-to-super.nitc :: RapidTypeAnalysis :: live_super_sends=
Live call-to-super.nitc :: RapidTypeAnalysis :: live_targets
The live targets of a specific callsite.nitc :: RapidTypeAnalysis :: live_types=
The pool to live types.nitc :: RapidTypeAnalysis :: live_types_to_csv
Return a ready-to-save CSV document objet that agregates informations about live types.nitc :: RapidTypeAnalysis :: mainmodule=
The main module of the analysis.nitc :: RapidTypeAnalysis :: modelbuilder
The modelbuilder used to get the AST.nitc :: RapidTypeAnalysis :: modelbuilder=
The modelbuilder used to get the AST.nitc :: RapidTypeAnalysis :: run_analysis
Run the analysis until all visitable method definitions are visited.nitc :: RapidTypeAnalysis :: todo
The method definitions that remain to visitnitc :: RapidTypeAnalysis :: todo=
The method definitions that remain to visitnitc :: RapidTypeAnalysis :: totry_methods
Methods that are still candidate to the try_sendnitc :: RapidTypeAnalysis :: totry_methods=
Methods that are still candidate to the try_sendnitc :: RapidTypeAnalysis :: totry_methods_to_remove
Methods that are are no more candidate to the try_sendnitc :: RapidTypeAnalysis :: totry_methods_to_remove=
Methods that are are no more candidate to the try_sendnitc :: RapidTypeAnalysis :: try_methods
Methods that are or were candidate to the try_sendnitc :: RapidTypeAnalysis :: try_methods=
Methods that are or were candidate to the try_sendnitc :: RapidTypeAnalysis :: try_send
nitc $ RapidTypeAnalysis :: SELF
Type of this instance, automatically specialized in every classnitc :: RapidTypeAnalysis :: _live_callsites
Live callsites.nitc :: RapidTypeAnalysis :: _live_cast_types
The pool of types used to perform type checks (isa and as).nitc :: RapidTypeAnalysis :: _live_classes
Live (instantiated) classes.nitc :: RapidTypeAnalysis :: _live_methoddefs
Live method definitions.nitc :: RapidTypeAnalysis :: _live_methods
Live methods.nitc :: RapidTypeAnalysis :: _live_mmodules
Live mmodules.nitc :: RapidTypeAnalysis :: _live_open_cast_types
The pool of undesolved types used to perform type checks (isa and as).nitc :: RapidTypeAnalysis :: _live_open_types
The pool of unresolved live typesnitc :: RapidTypeAnalysis :: _live_super_sends
Live call-to-super.nitc :: RapidTypeAnalysis :: _live_types
The pool to live types.nitc :: RapidTypeAnalysis :: _mainmodule
The main module of the analysis.nitc :: RapidTypeAnalysis :: _modelbuilder
The modelbuilder used to get the AST.nitc :: RapidTypeAnalysis :: _todo
The method definitions that remain to visitnitc :: RapidTypeAnalysis :: _totry_methods
Methods that are still candidate to the try_sendnitc :: RapidTypeAnalysis :: _totry_methods_to_remove
Methods that are are no more candidate to the try_sendnitc :: RapidTypeAnalysis :: _try_methods
Methods that are or were candidate to the try_sendnitc :: RapidTypeAnalysis :: add_call
nitc :: RapidTypeAnalysis :: add_cast
nitc :: RapidTypeAnalysis :: add_new
nitc :: RapidTypeAnalysis :: check_depth
core :: Object :: class_factory
Implementation used byget_class
to create the specific class.
nitc :: RapidTypeAnalysis :: defaultinit
core :: Object :: defaultinit
nitc :: RapidTypeAnalysis :: force_alive
core :: Object :: is_same_instance
Return true ifself
and other
are the same instance (i.e. same identity).
core :: Object :: is_same_serialized
Isself
the same as other
in a serialization context?
core :: Object :: is_same_type
Return true ifself
and other
have the same dynamic type.
nitc :: RapidTypeAnalysis :: live_callsites=
Live callsites.nitc :: RapidTypeAnalysis :: live_cast_types
The pool of types used to perform type checks (isa and as).nitc :: RapidTypeAnalysis :: live_cast_types=
The pool of types used to perform type checks (isa and as).nitc :: RapidTypeAnalysis :: live_classes
Live (instantiated) classes.nitc :: RapidTypeAnalysis :: live_classes=
Live (instantiated) classes.nitc :: RapidTypeAnalysis :: live_methoddefs
Live method definitions.nitc :: RapidTypeAnalysis :: live_methoddefs=
Live method definitions.nitc :: RapidTypeAnalysis :: live_methods=
Live methods.nitc :: RapidTypeAnalysis :: live_methods_to_tree
Return a ready-to-save OrderedTree object that agregates infomration about live methods.nitc :: RapidTypeAnalysis :: live_mmodules=
Live mmodules.nitc :: RapidTypeAnalysis :: live_open_cast_types
The pool of undesolved types used to perform type checks (isa and as).nitc :: RapidTypeAnalysis :: live_open_cast_types=
The pool of undesolved types used to perform type checks (isa and as).nitc :: RapidTypeAnalysis :: live_open_types
The pool of unresolved live typesnitc :: RapidTypeAnalysis :: live_open_types=
The pool of unresolved live typesnitc :: RapidTypeAnalysis :: live_super_sends
Live call-to-super.nitc :: RapidTypeAnalysis :: live_super_sends=
Live call-to-super.nitc :: RapidTypeAnalysis :: live_targets
The live targets of a specific callsite.nitc :: RapidTypeAnalysis :: live_types=
The pool to live types.nitc :: RapidTypeAnalysis :: live_types_to_csv
Return a ready-to-save CSV document objet that agregates informations about live types.nitc :: RapidTypeAnalysis :: mainmodule=
The main module of the analysis.nitc :: RapidTypeAnalysis :: modelbuilder
The modelbuilder used to get the AST.nitc :: RapidTypeAnalysis :: modelbuilder=
The modelbuilder used to get the AST.core :: Object :: native_class_name
The class name of the object in CString format.core :: Object :: output_class_name
Display class name on stdout (debug only).nitc :: RapidTypeAnalysis :: run_analysis
Run the analysis until all visitable method definitions are visited.nitc :: RapidTypeAnalysis :: todo
The method definitions that remain to visitnitc :: RapidTypeAnalysis :: todo=
The method definitions that remain to visitnitc :: RapidTypeAnalysis :: totry_methods
Methods that are still candidate to the try_sendnitc :: RapidTypeAnalysis :: totry_methods=
Methods that are still candidate to the try_sendnitc :: RapidTypeAnalysis :: totry_methods_to_remove
Methods that are are no more candidate to the try_sendnitc :: RapidTypeAnalysis :: totry_methods_to_remove=
Methods that are are no more candidate to the try_sendnitc :: RapidTypeAnalysis :: try_methods
Methods that are or were candidate to the try_sendnitc :: RapidTypeAnalysis :: try_methods=
Methods that are or were candidate to the try_sendnitc :: RapidTypeAnalysis :: try_send
# 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_methods to determine new methoddefs to visit
var live_types = new HashSet[MClassType]
# The pool of unresolved live types
# They are globally resolved at the end of the analaysis
var live_open_types = new HashSet[MClassType]
# Live (instantiated) classes.
var live_classes = new HashSet[MClass]
# The pool of types used to perform type checks (isa and as).
var live_cast_types = new HashSet[MType]
# The pool of undesolved types used to perform type checks (isa and as).
# They are globally resolved at the end of the analaysis
var live_open_cast_types = new HashSet[MType]
# Live method definitions.
var live_methoddefs = new HashSet[MMethodDef]
# 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]
private var live_targets_cache = new HashMap2[MType, MProperty, Set[MMethodDef]]
# The live targets of a specific callsite.
fun live_targets(callsite: CallSite): Set[MMethodDef]
do
var mtype = callsite.recv
var anchor = callsite.anchor
if anchor != null then mtype = mtype.anchor_to(callsite.mmodule, anchor)
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
res = new ArraySet[MMethodDef]
live_targets_cache[mtype, mproperty] = res
for c in live_classes do
var tc = c.intro.bound_mtype
if not tc.is_subtype(mainmodule, null, mtype) then continue
var d = mproperty.lookup_first_definition(mainmodule, tc)
res.add d
end
return res
end
# Live call-to-super.
var live_super_sends = new HashSet[MMethodDef]
# 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
do
# Gather all kind of type
var typeset = new HashSet[MType]
typeset.add_all(live_types)
typeset.add_all(live_open_types)
typeset.add_all(live_cast_types)
typeset.add_all(live_open_cast_types)
var types = typeset.to_a
(new CachedAlphaComparator).sort(types)
var res = new CsvDocument
res.separator = ';'
res.header = ["Type", "Resolution", "Liveness", "Cast-liveness"]
for t in types do
var reso
if t.need_anchor then reso = "OPEN " else reso = "CLOSED"
var live
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_record(t, reso, live, cast)
end
return res
end
# Return a ready-to-save OrderedTree object that agregates infomration about live methods.
# Note: methods are listed in an alphanumeric order to improve human reading.
fun live_methods_to_tree: OrderedTree[Object]
do
var tree = new OrderedTree[Object]
for x in live_methods do
var xn = x.full_name
tree.add(null, xn)
for z in x.mpropdefs do
var zn = z.to_s
if live_methoddefs.has(z) then
tree.add(xn, zn)
if live_super_sends.has(z) then
tree.add(zn, zn + "(super)")
end
else if live_super_sends.has(z) then
tree.add(xn, zn + "(super)")
end
end
end
tree.sort_with(alpha_comparator)
return tree
end
# Methods that are still candidate to the try_send
private var totry_methods = new HashSet[MMethod]
# Methods that are are no more candidate to the try_send
private var totry_methods_to_remove = new Array[MMethod]
# Methods that are or were candidate to the try_send
# Used to ensure that try_send is only used once
private var try_methods = new HashSet[MMethod]
# The method definitions that remain to visit
private var todo = new List[MMethodDef]
private fun force_alive(classname: String)
do
var classes = self.modelbuilder.model.get_mclasses_by_name(classname)
if classes != null then for c in classes do self.add_new(c.mclass_type, c.mclass_type)
end
# Run the analysis until all visitable method definitions are visited.
fun run_analysis
do
var maintype = mainmodule.sys_type
if maintype == null then return # No entry point
add_new(maintype, maintype)
var initprop = mainmodule.try_get_primitive_method("init", maintype.mclass)
if initprop != null then
add_send(maintype, initprop)
end
var mainprop = mainmodule.try_get_primitive_method("run", maintype.mclass) or else
mainmodule.try_get_primitive_method("main", maintype.mclass)
if mainprop != null then
add_send(maintype, mainprop)
end
var finalizable_type = mainmodule.finalizable_type
if finalizable_type != null then
var finalize_meth = mainmodule.try_get_primitive_method("finalize", finalizable_type.mclass)
if finalize_meth != null then add_send(finalizable_type, finalize_meth)
end
# Force primitive types
force_alive("Bool")
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 = msignature.vararg_rank
if vararg_rank > -1 then
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.array_type(elttype)
v.add_type(vararg)
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
var sig = msignature
var osig = mmeth.intro.msignature.as(not null)
for i in [0..sig.arity[ do
var origtype = osig.mparameters[i].mtype
if not origtype.need_anchor then continue # skip non covariant stuff
var paramtype = sig.mparameters[i].mtype
add_cast(paramtype)
end
if mmethoddef.is_abstract then continue
var npropdef = modelbuilder.mpropdef2node(mmethoddef)
if npropdef isa AClassdef then
if mmethoddef.mproperty.is_root_init then
# Final init call
if not mmethoddef.is_intro then
self.add_super_send(v.receiver, mmethoddef)
end
else if mmethoddef.mclassdef.default_init == mmethoddef then
# default_init call
for i in mmethoddef.initializers do
if i isa MMethod then self.add_send(v.receiver, i)
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
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
v.add_callsite(auto_super_init)
end
end
if npropdef.auto_super_call then
self.add_super_send(v.receiver, mmethoddef)
end
end
if mmethoddef.is_intern or mmethoddef.is_extern then
# UGLY: We force the "instantation" of the concrete return type if any
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
end
v.enter_visit(npropdef)
end
#print "MMethod {live_methods.length}: {live_methods.join(", ")}"
#print "MMethodDef {live_methoddefs.length}: {live_methoddefs.join(", ")}"
#print "open MType {live_open_types.length}: {live_open_types.join(", ")}"
var todo_types = new List[MClassType]
todo_types.add_all(live_types)
while not todo_types.is_empty do
var t = todo_types.shift
for ot in live_open_types do
#print "{ot}/{t} ?"
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)
# 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(", ")}"
#print "open cast MType {live_open_cast_types.length}: {live_open_cast_types.join(", ")}"
for ot in live_open_cast_types do
#print "live_open_cast_type: {ot}"
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
end
#print "cast MType {live_cast_types.length}: {live_cast_types.join(", ")}"
end
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}`.")
return false
end
return true
end
fun add_new(recv: MClassType, mtype: MClassType)
do
assert not recv.need_anchor
if mtype.need_anchor then
if live_open_types.has(mtype) then return
live_open_types.add(mtype)
else
if live_types.has(mtype) then return
live_types.add(mtype)
end
var mclass = mtype.mclass
if live_classes.has(mclass) then return
live_classes.add(mclass)
for p in totry_methods do try_send(mtype, p)
for p in live_super_sends do try_super_send(mtype, p)
# Remove cleared ones
for p in totry_methods_to_remove do totry_methods.remove(p)
totry_methods_to_remove.clear
var bound_mtype = mtype.anchor_to(mainmodule, recv)
for cd in bound_mtype.collect_mclassdefs(mainmodule)
do
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(npropdef.n_expr)
v.enter_visit(npropdef.n_block)
end
end
end
fun add_cast(mtype: MType)
do
if mtype.need_anchor then
live_open_cast_types.add(mtype)
else
live_cast_types.add(mtype)
end
end
fun try_send(recv: MClassType, mproperty: MMethod)
do
recv = recv.mclass.intro.bound_mtype
if not recv.has_mproperty(mainmodule, mproperty) then return
var d = mproperty.lookup_first_definition(mainmodule, recv)
add_call(d)
end
fun add_call(mpropdef: MMethodDef)
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 not live_methoddefs.has(d) then return
end
#print "full property: {mpropdef.mproperty} for {mpropdef.mproperty.mpropdefs.length} definitions"
totry_methods_to_remove.add(mpropdef.mproperty)
end
fun add_send(recv: MType, mproperty: MMethod)
do
if try_methods.has(mproperty) then return
#print "new prop: {mproperty}"
live_methods.add(mproperty)
try_methods.add(mproperty)
if mproperty.mpropdefs.length == 1 then
# If there is only one definition, just add the definition and do not try again the property
var d = mproperty.mpropdefs.first
add_call(d)
return
end
# Else, the property is potentially called with various reciever
# So just try the methods with existing receiver and register it for future receiver
totry_methods.add(mproperty)
for c in live_classes do
try_send(c.intro.bound_mtype, mproperty)
end
end
fun try_super_send(recv: MClassType, mpropdef: MMethodDef)
do
recv = recv.mclass.intro.bound_mtype
if not recv.collect_mclassdefs(mainmodule).has(mpropdef.mclassdef) then return
var d = mpropdef.lookup_next_definition(mainmodule, recv)
add_call(d)
end
fun add_super_send(recv: MType, mpropdef: MMethodDef)
do
assert mpropdef.has_supercall
if live_super_sends.has(mpropdef) then return
#print "new super prop: {mpropdef}"
live_super_sends.add(mpropdef)
for c in live_classes do
try_super_send(c.intro.bound_mtype, mpropdef)
end
end
end
src/rapid_type_analysis.nit:50,1--464,3