X-Git-Url: http://nitlanguage.org diff --git a/src/rapid_type_analysis.nit b/src/rapid_type_analysis.nit index eb14c94..17d5e0c 100644 --- a/src/rapid_type_analysis.nit +++ b/src/rapid_type_analysis.nit @@ -28,6 +28,11 @@ import modelbuilder import typing import auto_super_init +import csv # for live_types_to_csv +import ordered_tree # for live_methods_to_tree + +private import more_collections + redef class ModelBuilder fun do_rapid_type_analysis(mainmodule: MModule): RapidTypeAnalysis do @@ -60,7 +65,7 @@ class RapidTypeAnalysis var live_classes = new HashSet[MClass] # The pool of types used to perform type checks (isa and as). - var live_cast_types = new HashSet[MClassType] + 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 @@ -72,15 +77,109 @@ class RapidTypeAnalysis # Live methods. var live_methods = new HashSet[MMethod] + # 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.as_notnullable + assert mtype isa MClassType + 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] - # Methods that are are still candidate to the try_send + # 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.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_line(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 @@ -96,12 +195,15 @@ class RapidTypeAnalysis add_send(maintype, mainprop) end - # Force Bool - var classes = self.modelbuilder.model.get_mclasses_by_name("Bool") - if classes != null then for c in classes do self.add_new(c.mclass_type, c.mclass_type) + # Force primitive types + force_alive("Bool") + force_alive("Int") + force_alive("Float") + force_alive("Char") while not todo.is_empty do var mmethoddef = todo.shift + var mmeth = mmethoddef.mproperty #print "# visit {mmethoddef}" var v = new RapidTypeVisitor(self, mmethoddef.mclassdef.bound_mtype, mmethoddef) @@ -112,23 +214,23 @@ class RapidTypeAnalysis #elttype = elttype.anchor_to(self.mainmodule, v.receiver) var vararg = self.mainmodule.get_primitive_class("Array").get_mtype([elttype]) v.add_type(vararg) - v.add_monomorphic_send(vararg, self.modelbuilder.force_get_primitive_method(node, "with_native", vararg.mclass, self.mainmodule)) var native = self.mainmodule.get_primitive_class("NativeArray").get_mtype([elttype]) v.add_type(native) + v.add_monomorphic_send(vararg, self.modelbuilder.force_get_primitive_method(node, "with_native", vararg.mclass, self.mainmodule)) end - - for i in [0..mmethoddef.msignature.arity[ do - var origtype = mmethoddef.mproperty.intro.msignature.mparameters[i].mtype + var sig = mmethoddef.msignature.as(not null) + 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 = mmethoddef.msignature.mparameters[i].mtype - #paramtype = v.cleanup_type(paramtype).as(not null) + var paramtype = sig.mparameters[i].mtype add_cast(paramtype) end if not modelbuilder.mpropdef2npropdef.has_key(mmethoddef) then # It is an init for a class? - if mmethoddef.mproperty.name == "init" then + if mmeth.name == "init" then var nclassdef = self.modelbuilder.mclassdef2nclassdef[mmethoddef.mclassdef] var super_inits = nclassdef.super_inits if super_inits != null then @@ -146,23 +248,23 @@ class RapidTypeAnalysis var npropdef = modelbuilder.mpropdef2npropdef[mmethoddef] - if npropdef isa AConcreteMethPropdef 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 - v.add_monomorphic_send(v.receiver, auto_super_init) + v.add_callsite(auto_super_init) end end - else if npropdef isa AInternMethPropdef or npropdef isa AExternMethPropdef then + end + + if mmeth.is_new then + v.add_type(v.receiver) + else 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 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 - else if npropdef isa AExternInitPropdef then - v.add_type(v.receiver) - else - end v.enter_visit(npropdef) @@ -195,8 +297,6 @@ 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 rt isa MNullableType then rt = rt.mtype - assert rt isa MClassType live_cast_types.add(rt) #print " {ot}/{t} -> {rt}" end @@ -230,6 +330,10 @@ class RapidTypeAnalysis 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 @@ -249,11 +353,9 @@ class RapidTypeAnalysis fun add_cast(mtype: MType) do - if mtype isa MNullableType then mtype = mtype.mtype if mtype.need_anchor then live_open_cast_types.add(mtype) else - assert mtype isa MClassType live_cast_types.add(mtype) end end @@ -280,14 +382,15 @@ class RapidTypeAnalysis if not live_methoddefs.has(d) then return end #print "full property: {mpropdef.mproperty} for {mpropdef.mproperty.mpropdefs.length} definitions" - totry_methods.remove(mpropdef.mproperty) + totry_methods_to_remove.add(mpropdef.mproperty) end fun add_send(recv: MType, mproperty: MMethod) do - if live_methods.has(mproperty) then return + 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 @@ -338,7 +441,6 @@ class RapidTypeVisitor redef fun visit(n) do - if n == null then return n.accept_rapid_type_visitor(self) if n isa AExpr then var implicit_cast_to = n.implicit_cast_to @@ -355,7 +457,7 @@ class RapidTypeVisitor 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 + mtype = mtype.as_notnullable assert mtype isa MClassType assert not mtype.need_anchor return mtype @@ -375,11 +477,20 @@ class RapidTypeVisitor fun add_type(mtype: MClassType) do analysis.add_new(receiver, mtype) - fun add_monomorphic_send(mtype: MType, mproperty: MMethod) do analysis.try_send(mtype.as(MClassType), mproperty) + fun add_monomorphic_send(mtype: MType, mproperty: MMethod) + do + analysis.live_methods.add(mproperty) + analysis.try_send(mtype.as(MClassType), mproperty) + end fun add_send(mtype: MType, mproperty: MMethod) do analysis.add_send(mtype, mproperty) fun add_cast_type(mtype: MType) do analysis.add_cast(mtype) + + fun add_callsite(callsite: nullable CallSite) do if callsite != null then + analysis.add_send(callsite.recv, callsite.mproperty) + analysis.live_callsites.add(callsite) + end end ### @@ -427,12 +538,10 @@ end redef class AStringFormExpr redef fun accept_rapid_type_visitor(v) do - var mtype = self.mtype.as(MClassType) - 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) + var prop = v.get_method(native, "to_s_with_length") + v.add_monomorphic_send(native, prop) end end @@ -454,8 +563,7 @@ redef class ACrangeExpr do var mtype = self.mtype.as(MClassType) v.add_type(mtype) - var prop = v.get_method(mtype, "init") - v.add_monomorphic_send(mtype, prop) + v.add_callsite(init_callsite) end end @@ -464,8 +572,7 @@ redef class AOrangeExpr do var mtype = self.mtype.as(MClassType) v.add_type(mtype) - var prop = v.get_method(mtype, "without_last") - v.add_monomorphic_send(mtype, prop) + v.add_callsite(init_callsite) end end @@ -500,9 +607,7 @@ end redef class ASendExpr redef fun accept_rapid_type_visitor(v) do - var mproperty = self.mproperty.as(not null) - var recvtype = self.n_expr.mtype.as(not null) - v.add_send(recvtype, mproperty) + v.add_callsite(callsite) end end @@ -510,66 +615,53 @@ end redef class ASendReassignFormExpr redef fun accept_rapid_type_visitor(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 + v.add_callsite(callsite) + v.add_callsite(reassign_callsite) + v.add_callsite(write_callsite) end end redef class AVarReassignExpr redef fun accept_rapid_type_visitor(v) do - v.add_send(self.read_type.as(not null), self.reassign_property.mproperty) + v.add_callsite(reassign_callsite) end end redef class AAttrReassignExpr redef fun accept_rapid_type_visitor(v) do - v.add_send(self.read_type.as(not null), self.reassign_property.mproperty) + v.add_callsite(reassign_callsite) end end redef class ASuperExpr redef fun accept_rapid_type_visitor(v) do - var mproperty = self.mproperty - if mproperty != null then - v.add_monomorphic_send(v.receiver, mproperty) + var callsite = self.callsite + if callsite != null then + v.add_callsite(callsite) return end - v.analysis.add_super_send(v.receiver, v.mpropdef.as(MMethodDef)) + v.analysis.add_super_send(v.receiver, mpropdef.as(not null)) end end redef class AForExpr redef fun accept_rapid_type_visitor(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")) + v.add_callsite(self.method_iterator) + v.add_callsite(self.method_is_ok) if self.variables.length == 1 then - v.add_send(objtype, v.get_method(iteratortype, "item")) + v.add_callsite(self.method_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")) + v.add_callsite(self.method_key) + v.add_callsite(self.method_item) else abort end - v.add_send(objtype, v.get_method(iteratortype, "next")) + v.add_callsite(self.method_next) end end @@ -578,7 +670,6 @@ redef class ANewExpr do var mtype = self.mtype.as(MClassType) v.add_type(mtype) - var mproperty = self.mproperty.as(not null) - v.add_monomorphic_send(mtype, mproperty) + v.add_callsite(callsite) end end