1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # Copyright 2012 Jean Privat <jean@pryen.org>
5 # Licensed under the Apache License, Version 2.0 (the "License");
6 # you may not use this file except in compliance with the License.
7 # You may obtain a copy of the License at
9 # http://www.apache.org/licenses/LICENSE-2.0
11 # Unless required by applicable law or agreed to in writing, software
12 # distributed under the License is distributed on an "AS IS" BASIS,
13 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 # See the License for the specific language governing permissions and
15 # limitations under the License.
17 # Rapid type analysis on the AST
19 # Rapid type analysis is an analyse that aproximates the set of live classes
20 # and the set of live methods starting from the entry point of the program.
21 # These two sets are interdependant and computed together.
22 # It is quite efficient but the type set is global and pollutes each call site.
23 module rapid_type_analysis
26 private import explain_assert_api
28 import csv
# for live_types_to_csv
29 private import ordered_tree
# for live_methods_to_tree
31 private import more_collections
33 redef class ModelBuilder
34 # Performs a rapid-type-analysis on the program associated with `mainmodule`.
35 fun do_rapid_type_analysis
(mainmodule
: MModule): RapidTypeAnalysis
37 var analysis
= new RapidTypeAnalysis(self, mainmodule
)
40 if toolcontext
.opt_log
.value
then
41 var basename
= toolcontext
.log_directory
/ mainmodule
.name
42 analysis
.live_methods_to_tree
.write_to_file
(basename
+ ".rta_methods.txt")
43 analysis
.live_types_to_csv
.write_to_file
(basename
+ ".rta_types.csv")
50 # RapidTypeAnalysis looks for alive rapid types in application.
51 # The entry point of the analysis is the mainmodule of the application.
52 class RapidTypeAnalysis
53 # The modelbuilder used to get the AST.
54 var modelbuilder
: ModelBuilder
56 # The main module of the analysis.
57 # Used to perform types operations.
58 var mainmodule
: MModule
60 # The pool to live types.
61 # During the analysis, new types are added and combined with
62 # live_methods to determine new methoddefs to visit
63 var live_types
= new HashSet[MClassType]
65 # The pool of unresolved live types
66 # They are globally resolved at the end of the analaysis
67 var live_open_types
= new HashSet[MClassType]
69 # Live (instantiated) classes.
70 var live_classes
= new HashSet[MClass]
72 # The pool of types used to perform type checks (isa and as).
73 var live_cast_types
= new HashSet[MType]
75 # The pool of undesolved types used to perform type checks (isa and as).
76 # They are globally resolved at the end of the analaysis
77 var live_open_cast_types
= new HashSet[MType]
79 # Live method definitions.
80 var live_methoddefs
= new HashSet[MMethodDef]
83 var live_methods
= new HashSet[MMethod]
86 # Those with a live method definitions (see `live_methoddefs`)
87 var live_mmodules
= new HashSet[MModule]
90 var live_callsites
= new HashSet[CallSite]
92 private var live_targets_cache
= new HashMap2[MType, MProperty, Set[MMethodDef]]
94 # The live targets of a specific callsite.
95 fun live_targets
(callsite
: CallSite): Set[MMethodDef]
97 var mtype
= callsite
.recv
98 var anchor
= callsite
.anchor
99 if anchor
!= null then mtype
= mtype
.anchor_to
(callsite
.mmodule
, anchor
)
100 mtype
= mtype
.undecorate
101 if mtype
isa MClassType then mtype
= mtype
.mclass
.intro
.bound_mtype
102 var mproperty
= callsite
.mproperty
103 var res
= live_targets_cache
[mtype
, mproperty
]
104 if res
!= null then return res
105 res
= new ArraySet[MMethodDef]
106 live_targets_cache
[mtype
, mproperty
] = res
108 for c
in live_classes
do
109 var tc
= c
.intro
.bound_mtype
110 if not tc
.is_subtype
(mainmodule
, null, mtype
) then continue
111 var d
= mproperty
.lookup_first_definition
(mainmodule
, tc
)
118 # Live call-to-super.
119 var live_super_sends
= new HashSet[MMethodDef]
121 # Return a ready-to-save CSV document objet that agregates informations about live types.
122 # Each discovered type is listed in a line, with its status: resolution, liveness, cast-liveness.
123 # Note: types are listed in an alphanumeric order to improve human reading.
124 fun live_types_to_csv
: CsvDocument
126 # Gather all kind of type
127 var typeset
= new HashSet[MType]
128 typeset
.add_all
(live_types
)
129 typeset
.add_all
(live_open_types
)
130 typeset
.add_all
(live_cast_types
)
131 typeset
.add_all
(live_open_cast_types
)
132 var types
= typeset
.to_a
133 (new CachedAlphaComparator).sort
(types
)
134 var res
= new CsvDocument
136 res
.header
= ["Type", "Resolution", "Liveness", "Cast-liveness"]
139 if t
.need_anchor
then reso
= "OPEN " else reso
= "CLOSED"
141 if t
isa MClassType and (live_types
.has
(t
) or live_open_types
.has
(t
)) then live
= "LIVE" else live
= "DEAD"
143 if live_cast_types
.has
(t
) or live_open_cast_types
.has
(t
) then cast
= "CAST LIVE" else cast
= "CAST DEAD"
144 res
.add_record
(t
, reso
, live
, cast
)
149 # Return a ready-to-save OrderedTree object that agregates infomration about live methods.
150 # Note: methods are listed in an alphanumeric order to improve human reading.
151 fun live_methods_to_tree
: OrderedTree[Object]
153 var tree
= new OrderedTree[Object]
154 for x
in live_methods
do
157 for z
in x
.mpropdefs
do
159 if live_methoddefs
.has
(z
) then
161 if live_super_sends
.has
(z
) then
162 tree
.add
(zn
, zn
+ "(super)")
164 else if live_super_sends
.has
(z
) then
165 tree
.add
(xn
, zn
+ "(super)")
169 tree
.sort_with
(alpha_comparator
)
173 # Methods that are still candidate to the try_send
174 private var totry_methods
= new HashSet[MMethod]
176 # Methods that are are no more candidate to the try_send
177 private var totry_methods_to_remove
= new Array[MMethod]
179 # Methods that are or were candidate to the try_send
180 # Used to ensure that try_send is only used once
181 private var try_methods
= new HashSet[MMethod]
183 # The method definitions that remain to visit
184 private var todo
= new List[MMethodDef]
186 private fun force_alive
(classname
: String)
188 var classes
= self.modelbuilder
.model
.get_mclasses_by_name
(classname
)
189 if classes
!= null then for c
in classes
do self.add_new
(c
.mclass_type
, c
.mclass_type
)
192 # Run the analysis until all visitable method definitions are visited.
195 var maintype
= mainmodule
.sys_type
196 if maintype
== null then return # No entry point
197 add_new
(maintype
, maintype
)
198 var initprop
= mainmodule
.try_get_primitive_method
("init", maintype
.mclass
)
199 if initprop
!= null then
200 add_send
(maintype
, initprop
)
202 var mainprop
= mainmodule
.try_get_primitive_method
("run", maintype
.mclass
) or else
203 mainmodule
.try_get_primitive_method
("main", maintype
.mclass
)
204 if mainprop
!= null then
205 add_send
(maintype
, mainprop
)
208 var finalizable_type
= mainmodule
.finalizable_type
209 if finalizable_type
!= null then
210 var finalize_meth
= mainmodule
.try_get_primitive_method
("finalize", finalizable_type
.mclass
)
211 if finalize_meth
!= null then add_send
(finalizable_type
, finalize_meth
)
214 # Force primitive types
218 force_alive
("Pointer")
223 force_alive
("UInt16")
225 force_alive
("UInt32")
227 while not todo
.is_empty
do
228 var mmethoddef
= todo
.shift
229 var mmeth
= mmethoddef
.mproperty
230 var msignature
= mmethoddef
.msignature
231 if msignature
== null then continue # Skip broken method
233 #print "# visit {mmethoddef}"
234 var v
= new RapidTypeVisitor(self, mmethoddef
.mclassdef
.bound_mtype
, mmethoddef
)
236 var vararg_rank
= msignature
.vararg_rank
237 if vararg_rank
> -1 then
238 var node
= self.modelbuilder
.mpropdef2node
(mmethoddef
)
239 var elttype
= msignature
.mparameters
[vararg_rank
].mtype
240 #elttype = elttype.anchor_to(self.mainmodule, v.receiver)
241 var vararg
= self.mainmodule
.array_type
(elttype
)
243 var native
= self.mainmodule
.native_array_type
(elttype
)
245 v
.add_monomorphic_send
(vararg
, self.modelbuilder
.force_get_primitive_method
(node
, "with_native", vararg
.mclass
, self.mainmodule
))
249 var osig
= mmeth
.intro
.msignature
.as(not null)
250 for i
in [0..sig
.arity
[ do
251 var origtype
= osig
.mparameters
[i
].mtype
252 if not origtype
.need_anchor
then continue # skip non covariant stuff
253 var paramtype
= sig
.mparameters
[i
].mtype
257 if mmethoddef
.is_abstract
then continue
259 var npropdef
= modelbuilder
.mpropdef2node
(mmethoddef
)
261 if npropdef
isa AClassdef then
262 if mmethoddef
.mproperty
.is_root_init
then
264 if not mmethoddef
.is_intro
then
265 self.add_super_send
(v
.receiver
, mmethoddef
)
267 else if mmethoddef
.mclassdef
.default_init
== mmethoddef
then
269 for i
in mmethoddef
.initializers
do
270 if i
isa MMethod then self.add_send
(v
.receiver
, i
)
273 npropdef
.debug
"cannot RTA {mmethoddef}"
277 else if mmethoddef
.constant_value
!= null then
278 # Make the return type live
279 v
.add_type
(msignature
.return_mtype
.as(MClassType))
281 else if npropdef
== null then
285 if npropdef
isa AMethPropdef then
286 var auto_super_inits
= npropdef
.auto_super_inits
287 if auto_super_inits
!= null then
288 for auto_super_init
in auto_super_inits
do
289 v
.add_callsite
(auto_super_init
)
292 if npropdef
.auto_super_call
then
293 self.add_super_send
(v
.receiver
, mmethoddef
)
297 if mmethoddef
.is_intern
or mmethoddef
.is_extern
then
298 # UGLY: We force the "instantation" of the concrete return type if any
299 var ret
= msignature
.return_mtype
300 if ret
!= null and ret
isa MClassType and ret
.mclass
.kind
!= abstract_kind
and ret
.mclass
.kind
!= interface_kind
then
305 v
.enter_visit
(npropdef
)
308 #print "MMethod {live_methods.length}: {live_methods.join(", ")}"
309 #print "MMethodDef {live_methoddefs.length}: {live_methoddefs.join(", ")}"
311 #print "open MType {live_open_types.length}: {live_open_types.join(", ")}"
312 var todo_types
= new List[MClassType]
313 todo_types
.add_all
(live_types
)
314 while not todo_types
.is_empty
do
315 var t
= todo_types
.shift
316 for ot
in live_open_types
do
318 if not ot
.can_resolve_for
(t
, t
, mainmodule
) then continue
319 var rt
= ot
.anchor_to
(mainmodule
, t
)
320 if live_types
.has
(rt
) then continue
321 if not rt
.is_legal_in
(mainmodule
) then continue
322 if not check_depth
(rt
) then continue
323 #print "{ot}/{t} -> {rt}"
325 # unshift means a deep-first visit.
326 # So that the `check_depth` limit is reached sooner.
327 todo_types
.unshift
(rt
)
330 #print "MType {live_types.length}: {live_types.join(", ")}"
332 #print "open cast MType {live_open_cast_types.length}: {live_open_cast_types.join(", ")}"
333 for ot
in live_open_cast_types
do
334 #print "live_open_cast_type: {ot}"
335 for t
in live_types
do
336 if not ot
.can_resolve_for
(t
, t
, mainmodule
) then continue
337 var rt
= ot
.anchor_to
(mainmodule
, t
)
338 if not rt
.is_legal_in
(mainmodule
) then continue
339 live_cast_types
.add
(rt
)
340 #print " {ot}/{t} -> {rt}"
343 #print "cast MType {live_cast_types.length}: {live_cast_types.join(", ")}"
346 private fun check_depth
(mtype
: MClassType): Bool
350 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}`.")
356 fun add_new
(recv
: MClassType, mtype
: MClassType)
358 assert not recv
.need_anchor
359 if mtype
.need_anchor
then
360 if live_open_types
.has
(mtype
) then return
361 live_open_types
.add
(mtype
)
363 if live_types
.has
(mtype
) then return
364 live_types
.add
(mtype
)
367 var mclass
= mtype
.mclass
368 if live_classes
.has
(mclass
) then return
369 live_classes
.add
(mclass
)
371 for p
in totry_methods
do try_send
(mtype
, p
)
372 for p
in live_super_sends
do try_super_send
(mtype
, p
)
374 # Remove cleared ones
375 for p
in totry_methods_to_remove
do totry_methods
.remove
(p
)
376 totry_methods_to_remove
.clear
378 var bound_mtype
= mtype
.anchor_to
(mainmodule
, recv
)
379 for cd
in bound_mtype
.collect_mclassdefs
(mainmodule
)
381 for npropdef
in modelbuilder
.collect_attr_propdef
(cd
) do
382 if not npropdef
.has_value
then continue
384 var mpropdef
= npropdef
.mreadpropdef
.as(not null)
385 var v
= new RapidTypeVisitor(self, bound_mtype
, mpropdef
)
386 v
.enter_visit
(npropdef
.n_expr
)
387 v
.enter_visit
(npropdef
.n_block
)
393 fun add_cast
(mtype
: MType)
395 if mtype
.need_anchor
then
396 live_open_cast_types
.add
(mtype
)
398 live_cast_types
.add
(mtype
)
402 fun try_send
(recv
: MClassType, mproperty
: MMethod)
404 recv
= recv
.mclass
.intro
.bound_mtype
405 if not recv
.has_mproperty
(mainmodule
, mproperty
) then return
406 var d
= mproperty
.lookup_first_definition
(mainmodule
, recv
)
410 fun add_call
(mpropdef
: MMethodDef)
412 if live_methoddefs
.has
(mpropdef
) then return
413 live_methoddefs
.add
(mpropdef
)
414 live_mmodules
.add
(mpropdef
.mclassdef
.mmodule
)
417 var mproperty
= mpropdef
.mproperty
418 if mproperty
.mpropdefs
.length
<= 1 then return
419 # If all definitions of a method are live, we can remove the definition of the totry set
420 for d
in mproperty
.mpropdefs
do
421 if not live_methoddefs
.has
(d
) then return
423 #print "full property: {mpropdef.mproperty} for {mpropdef.mproperty.mpropdefs.length} definitions"
424 totry_methods_to_remove
.add
(mpropdef
.mproperty
)
427 fun add_send
(recv
: MType, mproperty
: MMethod)
429 if try_methods
.has
(mproperty
) then return
430 #print "new prop: {mproperty}"
431 live_methods
.add
(mproperty
)
432 try_methods
.add
(mproperty
)
433 if mproperty
.mpropdefs
.length
== 1 then
434 # If there is only one definition, just add the definition and do not try again the property
435 var d
= mproperty
.mpropdefs
.first
439 # Else, the property is potentially called with various reciever
440 # So just try the methods with existing receiver and register it for future receiver
441 totry_methods
.add
(mproperty
)
442 for c
in live_classes
do
443 try_send
(c
.intro
.bound_mtype
, mproperty
)
447 fun try_super_send
(recv
: MClassType, mpropdef
: MMethodDef)
449 recv
= recv
.mclass
.intro
.bound_mtype
450 if not recv
.collect_mclassdefs
(mainmodule
).has
(mpropdef
.mclassdef
) then return
451 var d
= mpropdef
.lookup_next_definition
(mainmodule
, recv
)
455 fun add_super_send
(recv
: MType, mpropdef
: MMethodDef)
457 assert mpropdef
.has_supercall
458 if live_super_sends
.has
(mpropdef
) then return
459 #print "new super prop: {mpropdef}"
460 live_super_sends
.add
(mpropdef
)
461 for c
in live_classes
do
462 try_super_send
(c
.intro
.bound_mtype
, mpropdef
)
467 class RapidTypeVisitor
470 var analysis
: RapidTypeAnalysis
471 var receiver
: MClassType
472 var mpropdef
: MPropDef
476 assert not receiver
.need_anchor
482 if n
.mtype
!= null or n
.is_typed
then
483 n
.accept_rapid_type_visitor
(self)
484 var implicit_cast_to
= n
.implicit_cast_to
485 if implicit_cast_to
!= null then self.add_cast_type
(implicit_cast_to
)
488 n
.accept_rapid_type_visitor
(self)
491 # RTA does not enter in AAnnotations
492 if not n
isa AAnnotations then
497 fun cleanup_type
(mtype
: MType): nullable MClassType
499 mtype
= mtype
.anchor_to
(self.analysis
.mainmodule
, self.receiver
)
500 if mtype
isa MNullType then return null
501 mtype
= mtype
.undecorate
502 assert mtype
isa MClassType
503 assert not mtype
.need_anchor
507 fun get_method
(recv
: MType, name
: String): MMethod
509 var mtype
= cleanup_type
(recv
)
511 return self.analysis
.modelbuilder
.force_get_primitive_method
(self.current_node
.as(not null), name
, mtype
.mclass
, self.analysis
.mainmodule
)
514 fun add_type
(mtype
: MClassType) do analysis
.add_new
(receiver
, mtype
)
516 fun add_monomorphic_send
(mtype
: MType, mproperty
: MMethod)
518 analysis
.live_methods
.add
(mproperty
)
519 analysis
.try_send
(mtype
.as(MClassType), mproperty
)
522 fun add_send
(mtype
: MType, mproperty
: MMethod) do analysis
.add_send
(mtype
, mproperty
)
524 fun add_cast_type
(mtype
: MType) do analysis
.add_cast
(mtype
)
526 fun add_callsite
(callsite
: nullable CallSite) do if callsite
!= null then
527 for m
in callsite
.mpropdef
.initializers
do
528 if m
isa MMethod then
529 analysis
.add_send
(callsite
.recv
, m
)
532 analysis
.add_send
(callsite
.recv
, callsite
.mproperty
)
533 analysis
.live_callsites
.add
(callsite
)
540 private fun accept_rapid_type_visitor
(v
: RapidTypeVisitor)
546 # Make the `mtype` of the expression live
547 # Used by literals and instantiations
548 fun allocate_mtype
(v
: RapidTypeVisitor)
550 var mtype
= self.mtype
551 if not mtype
isa MClassType then return
552 v
.add_type
(self.mtype
.as(MClassType))
556 redef class AIntegerExpr
557 redef fun accept_rapid_type_visitor
(v
)
563 redef class AFloatExpr
564 redef fun accept_rapid_type_visitor
(v
)
570 redef class ACharExpr
571 redef fun accept_rapid_type_visitor
(v
)
577 redef class AArrayExpr
578 redef fun accept_rapid_type_visitor
(v
)
580 var mtype
= self.mtype
.as(MClassType)
582 var native
= v
.analysis
.mainmodule
.native_array_type
(mtype
.arguments
.first
)
584 mtype
= v
.cleanup_type
(mtype
).as(not null)
585 var prop
= v
.get_method
(mtype
, "with_native")
586 v
.add_monomorphic_send
(mtype
, prop
)
587 v
.add_callsite
(with_capacity_callsite
)
588 v
.add_callsite
(push_callsite
)
592 redef class AStringFormExpr
593 redef fun accept_rapid_type_visitor
(v
)
595 var native
= v
.analysis
.mainmodule
.c_string_type
597 var prop
= v
.get_method
(native
, "to_s_unsafe")
598 v
.add_monomorphic_send
(native
, prop
)
599 v
.add_callsite
(to_re
)
600 v
.add_callsite
(ignore_case
)
601 v
.add_callsite
(newline
)
602 v
.add_callsite
(extended
)
603 v
.add_callsite
(to_bytes_with_copy
)
607 redef class ASuperstringExpr
608 redef fun accept_rapid_type_visitor
(v
)
610 var mmodule
= v
.analysis
.mainmodule
611 var object_type
= mmodule
.string_type
612 var arraytype
= mmodule
.array_type
(object_type
)
613 v
.add_type
(arraytype
)
614 var nattype
= mmodule
.native_array_type
(object_type
)
616 var prop
= v
.get_method
(arraytype
, "join")
617 v
.add_monomorphic_send
(arraytype
, prop
)
618 var prop2
= v
.get_method
(arraytype
, "with_native")
619 v
.add_monomorphic_send
(arraytype
, prop2
)
620 v
.add_monomorphic_send
(nattype
, v
.get_method
(nattype
, "native_to_s"))
624 redef class ACrangeExpr
625 redef fun accept_rapid_type_visitor
(v
)
627 var mtype
= self.mtype
628 if not mtype
isa MClassType then return
630 v
.add_callsite
(init_callsite
)
634 redef class AOrangeExpr
635 redef fun accept_rapid_type_visitor
(v
)
637 var mtype
= self.mtype
638 if not mtype
isa MClassType then return
640 v
.add_callsite
(init_callsite
)
644 redef class ATrueExpr
645 redef fun accept_rapid_type_visitor
(v
)
651 redef class AFalseExpr
652 redef fun accept_rapid_type_visitor
(v
)
659 redef fun accept_rapid_type_visitor
(v
)
661 var cast_type
= self.cast_type
662 if cast_type
== null then return
663 v
.add_cast_type
(cast_type
)
667 redef class AAsCastExpr
668 redef fun accept_rapid_type_visitor
(v
)
670 var mtype
= self.mtype
671 if mtype
== null then return
672 v
.add_cast_type
(mtype
)
676 redef class AAssertExpr
677 redef fun accept_rapid_type_visitor
(v
)
679 if can_explain_assert
(v
.analysis
.modelbuilder
) then
680 var str
= explain_assert_str
681 if str
!= null then str
.accept_rapid_type_visitor
(v
)
685 # Does `modelbuilder` know the classes to build a superstring to explain a failed assert?
686 private fun can_explain_assert
(modelbuilder
: ModelBuilder): Bool
688 var nas
= modelbuilder
.model
.get_mclasses_by_name
("NativeArray")
689 if nas
== null then return false
691 nas
= modelbuilder
.model
.get_mclasses_by_name
("Array")
692 if nas
== null or nas
.is_empty
then return false
694 nas
= modelbuilder
.model
.get_mclasses_by_name
("String")
695 if nas
== null or nas
.is_empty
then return false
701 redef class ASendExpr
702 redef fun accept_rapid_type_visitor
(v
)
704 v
.add_callsite
(callsite
)
708 redef class ACallrefExpr
709 redef fun accept_rapid_type_visitor
(v
)
712 v
.add_type
(mtype
.as(MClassType))
716 redef class ASendReassignFormExpr
717 redef fun accept_rapid_type_visitor
(v
)
719 v
.add_callsite
(callsite
)
720 v
.add_callsite
(reassign_callsite
)
721 v
.add_callsite
(write_callsite
)
725 redef class AVarReassignExpr
726 redef fun accept_rapid_type_visitor
(v
)
728 v
.add_callsite
(reassign_callsite
)
732 redef class AAttrReassignExpr
733 redef fun accept_rapid_type_visitor
(v
)
735 v
.add_callsite
(reassign_callsite
)
739 redef class ASuperExpr
740 redef fun accept_rapid_type_visitor
(v
)
742 var callsite
= self.callsite
743 if callsite
!= null then
744 v
.add_callsite
(callsite
)
748 v
.analysis
.add_super_send
(v
.receiver
, mpropdef
.as(not null))
752 redef class AForGroup
753 redef fun accept_rapid_type_visitor
(v
)
755 v
.add_callsite
(self.method_iterator
)
756 v
.add_callsite
(self.method_is_ok
)
757 if self.variables
.length
== 1 then
758 v
.add_callsite
(self.method_item
)
759 else if self.variables
.length
== 2 then
760 v
.add_callsite
(self.method_key
)
761 v
.add_callsite
(self.method_item
)
765 v
.add_callsite
(self.method_next
)
766 var mf
= self.method_finish
767 if mf
!= null then v
.add_callsite
(mf
)
772 redef fun accept_rapid_type_visitor
(v
)
774 var mtype
= self.recvtype
.as(not null)
776 v
.add_callsite
(callsite
)