X-Git-Url: http://nitlanguage.org diff --git a/src/rapid_type_analysis.nit b/src/rapid_type_analysis.nit index 7881db0..5b8d41b 100644 --- a/src/rapid_type_analysis.nit +++ b/src/rapid_type_analysis.nit @@ -14,7 +14,6 @@ # 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 @@ -24,8 +23,9 @@ module rapid_type_analysis import semantize +private import explain_assert_api -private import csv # for live_types_to_csv +import csv # for live_types_to_csv private import ordered_tree # for live_methods_to_tree private import more_collections @@ -36,6 +36,13 @@ redef class ModelBuilder 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 @@ -55,7 +62,7 @@ class RapidTypeAnalysis # 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] @@ -75,6 +82,10 @@ class RapidTypeAnalysis # 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] @@ -86,9 +97,8 @@ class RapidTypeAnalysis 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 @@ -122,7 +132,7 @@ class RapidTypeAnalysis var types = typeset.to_a (new CachedAlphaComparator).sort(types) var res = new CsvDocument - res.format = new CsvFormat('"', ';', "\n") + res.separator = ';' res.header = ["Type", "Resolution", "Liveness", "Cast-liveness"] for t in types do var reso @@ -203,31 +213,40 @@ class RapidTypeAnalysis # 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.mpropdef2node(mmethoddef) - var elttype = mmethoddef.msignature.mparameters[vararg_rank].mtype + 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 @@ -236,19 +255,23 @@ class RapidTypeAnalysis add_cast(paramtype) end + if mmethoddef.is_abstract then continue + var npropdef = modelbuilder.mpropdef2node(mmethoddef) if npropdef isa AClassdef then - # It is an init for a class - assert mmethoddef == npropdef.mfree_init - - if mmethoddef.mproperty.is_root_init and not mmethoddef.is_intro then - self.add_super_send(v.receiver, mmethoddef) + 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(mmethoddef.msignature.return_mtype.as(MClassType)) + v.add_type(msignature.return_mtype.as(MClassType)) continue else if npropdef == null then abort @@ -268,7 +291,7 @@ class RapidTypeAnalysis 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 @@ -290,10 +313,13 @@ class RapidTypeAnalysis 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(", ")}" @@ -304,6 +330,7 @@ class RapidTypeAnalysis 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 @@ -311,12 +338,14 @@ class RapidTypeAnalysis #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) @@ -347,7 +376,7 @@ class RapidTypeAnalysis for npropdef in modelbuilder.collect_attr_propdef(cd) do if not npropdef.has_value then continue - var mpropdef = npropdef.mpropdef.as(not null) + 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) @@ -377,13 +406,13 @@ class RapidTypeAnalysis 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" @@ -444,10 +473,14 @@ class RapidTypeVisitor 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 @@ -460,17 +493,12 @@ class RapidTypeVisitor 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) @@ -509,24 +537,35 @@ redef class ANode 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 @@ -535,41 +574,53 @@ redef class AArrayExpr 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 @@ -578,7 +629,8 @@ 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 @@ -587,28 +639,57 @@ 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 @@ -619,6 +700,13 @@ redef class ASendExpr 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) @@ -656,7 +744,7 @@ redef class ASuperExpr end end -redef class AForExpr +redef class AForGroup redef fun accept_rapid_type_visitor(v) do v.add_callsite(self.method_iterator)