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.
18 # Rapid type analysis on the AST
20 # Rapid type analysis is an analyse that aproximates the set of live classes
21 # and the set of live methods starting from the entry point of the program.
22 # These two sets are interdependant and computed together.
23 # It is quite efficient but the type set is global and pollutes each call site.
24 module rapid_type_analysis
29 import auto_super_init
31 import csv
# for live_types_to_csv
32 import ordered_tree
# for live_methods_to_tree
34 private import more_collections
36 redef class ModelBuilder
37 fun do_rapid_type_analysis
(mainmodule
: MModule): RapidTypeAnalysis
39 var analysis
= new RapidTypeAnalysis(self, mainmodule
)
45 # RapidTypeAnalysis looks for alive rapid types in application.
46 # The entry point of the analysis is the mainmodule of the application.
47 class RapidTypeAnalysis
48 # The modelbuilder used to get the AST.
49 var modelbuilder
: ModelBuilder
51 # The main module of the analysis.
52 # Used to perform types operations.
53 var mainmodule
: MModule
55 # The pool to live types.
56 # During the analysis, new types are added and combined with
57 # live_methods to determine new methoddefs to visit
58 var live_types
= new HashSet[MClassType]
60 # The pool of undesolved live types
61 # They are globally resolved at the end of the analaysis
62 var live_open_types
= new HashSet[MClassType]
64 # Live (instantiated) classes.
65 var live_classes
= new HashSet[MClass]
67 # The pool of types used to perform type checks (isa and as).
68 var live_cast_types
= new HashSet[MType]
70 # The pool of undesolved types used to perform type checks (isa and as).
71 # They are globally resolved at the end of the analaysis
72 var live_open_cast_types
= new HashSet[MType]
74 # Live method definitions.
75 var live_methoddefs
= new HashSet[MMethodDef]
78 var live_methods
= new HashSet[MMethod]
81 var live_callsites
= new HashSet[CallSite]
83 private var live_targets_cache
= new HashMap2[MType, MProperty, Set[MMethodDef]]
85 # The live targets of a specific callsite.
86 fun live_targets
(callsite
: CallSite): Set[MMethodDef]
88 var mtype
= callsite
.recv
89 var anchor
= callsite
.anchor
90 if anchor
!= null then mtype
= mtype
.anchor_to
(callsite
.mmodule
, anchor
)
91 mtype
= mtype
.as_notnullable
92 assert mtype
isa MClassType
93 mtype
= mtype
.mclass
.intro
.bound_mtype
94 var mproperty
= callsite
.mproperty
95 var res
= live_targets_cache
[mtype
, mproperty
]
96 if res
!= null then return res
97 res
= new ArraySet[MMethodDef]
98 live_targets_cache
[mtype
, mproperty
] = res
100 for c
in live_classes
do
101 var tc
= c
.intro
.bound_mtype
102 if not tc
.is_subtype
(mainmodule
, null, mtype
) then continue
103 var d
= mproperty
.lookup_first_definition
(mainmodule
, tc
)
110 # Live call-to-super.
111 var live_super_sends
= new HashSet[MMethodDef]
113 # Return a ready-to-save CSV document objet that agregates informations about live types.
114 # Each discovered type is listed in a line, with its status: resolution, liveness, cast-liveness.
115 # Note: types are listed in an alphanumeric order to improve human reading.
116 fun live_types_to_csv
: CSVDocument
118 # Gather all kind of type
119 var typeset
= new HashSet[MType]
120 typeset
.add_all
(live_types
)
121 typeset
.add_all
(live_open_types
)
122 typeset
.add_all
(live_cast_types
)
123 typeset
.add_all
(live_open_cast_types
)
124 var types
= typeset
.to_a
125 (new CachedAlphaComparator).sort
(types
)
126 var res
= new CSVDocument
127 res
.header
= ["Type", "Resolution", "Liveness", "Cast-liveness"]
130 if t
.need_anchor
then reso
= "OPEN " else reso
= "CLOSED"
132 if t
isa MClassType and (live_types
.has
(t
) or live_open_types
.has
(t
)) then live
= "LIVE" else live
= "DEAD"
134 if live_cast_types
.has
(t
) or live_open_cast_types
.has
(t
) then cast
= "CAST LIVE" else cast
= "CAST DEAD"
135 res
.add_line
(t
, reso
, live
, cast
)
140 # Return a ready-to-save OrderedTree object that agregates infomration about live methods.
141 # Note: methods are listed in an alphanumeric order to improve human reading.
142 fun live_methods_to_tree
: OrderedTree[Object]
144 var tree
= new OrderedTree[Object]
145 for x
in live_methods
do
148 for z
in x
.mpropdefs
do
150 if live_methoddefs
.has
(z
) then
152 if live_super_sends
.has
(z
) then
153 tree
.add
(zn
, zn
+ "(super)")
155 else if live_super_sends
.has
(z
) then
156 tree
.add
(xn
, zn
+ "(super)")
160 tree
.sort_with
(alpha_comparator
)
164 # Methods that are still candidate to the try_send
165 private var totry_methods
= new HashSet[MMethod]
167 # Methods that are are no more candidate to the try_send
168 private var totry_methods_to_remove
= new Array[MMethod]
170 # Methods that are or were candidate to the try_send
171 # Used to ensure that try_send is only used once
172 private var try_methods
= new HashSet[MMethod]
174 # The method definitions that remain to visit
175 private var todo
= new List[MMethodDef]
177 private fun force_alive
(classname
: String)
179 var classes
= self.modelbuilder
.model
.get_mclasses_by_name
(classname
)
180 if classes
!= null then for c
in classes
do self.add_new
(c
.mclass_type
, c
.mclass_type
)
183 # Run the analysis until all visitable method definitions are visited.
186 var maintype
= mainmodule
.sys_type
187 if maintype
== null then return # No entry point
188 add_new
(maintype
, maintype
)
189 var initprop
= mainmodule
.try_get_primitive_method
("init", maintype
.mclass
)
190 if initprop
!= null then
191 add_send
(maintype
, initprop
)
193 var mainprop
= mainmodule
.try_get_primitive_method
("run", maintype
.mclass
) or else
194 mainmodule
.try_get_primitive_method
("main", maintype
.mclass
)
195 if mainprop
!= null then
196 add_send
(maintype
, mainprop
)
199 # Force primitive types
205 while not todo
.is_empty
do
206 var mmethoddef
= todo
.shift
207 var mmeth
= mmethoddef
.mproperty
208 #print "# visit {mmethoddef}"
209 var v
= new RapidTypeVisitor(self, mmethoddef
.mclassdef
.bound_mtype
, mmethoddef
)
211 var vararg_rank
= mmethoddef
.msignature
.vararg_rank
212 if vararg_rank
> -1 then
213 var node
= self.modelbuilder
.mpropdef2npropdef
[mmethoddef
]
214 var elttype
= mmethoddef
.msignature
.mparameters
[vararg_rank
].mtype
215 #elttype = elttype.anchor_to(self.mainmodule, v.receiver)
216 var vararg
= self.mainmodule
.get_primitive_class
("Array").get_mtype
([elttype
])
218 var native
= self.mainmodule
.get_primitive_class
("NativeArray").get_mtype
([elttype
])
220 v
.add_monomorphic_send
(vararg
, self.modelbuilder
.force_get_primitive_method
(node
, "with_native", vararg
.mclass
, self.mainmodule
))
223 var sig
= mmethoddef
.msignature
.as(not null)
224 var osig
= mmeth
.intro
.msignature
.as(not null)
225 for i
in [0..sig
.arity
[ do
226 var origtype
= osig
.mparameters
[i
].mtype
227 if not origtype
.need_anchor
then continue # skip non covariant stuff
228 var paramtype
= sig
.mparameters
[i
].mtype
232 if not modelbuilder
.mpropdef2npropdef
.has_key
(mmethoddef
) then
233 # It is an init for a class?
234 if mmeth
.name
== "init" then
235 var nclassdef
= self.modelbuilder
.mclassdef2nclassdef
[mmethoddef
.mclassdef
]
236 var super_inits
= nclassdef
.super_inits
237 if super_inits
!= null then
238 #assert args.length == 1
239 for su
in super_inits
do
240 v
.add_monomorphic_send
(v
.receiver
, su
)
250 var npropdef
= modelbuilder
.mpropdef2npropdef
[mmethoddef
]
252 if npropdef
isa AMethPropdef then
253 var auto_super_inits
= npropdef
.auto_super_inits
254 if auto_super_inits
!= null then
255 for auto_super_init
in auto_super_inits
do
256 v
.add_callsite
(auto_super_init
)
262 v
.add_type
(v
.receiver
)
263 else if mmethoddef
.is_intern
or mmethoddef
.is_extern
then
264 # UGLY: We force the "instantation" of the concrete return type if any
265 var ret
= mmethoddef
.msignature
.return_mtype
266 if ret
!= null and ret
isa MClassType and ret
.mclass
.kind
!= abstract_kind
and ret
.mclass
.kind
!= interface_kind
then
271 v
.enter_visit
(npropdef
)
274 #print "MMethod {live_methods.length}: {live_methods.join(", ")}"
275 #print "MMethodDef {live_methoddefs.length}: {live_methoddefs.join(", ")}"
277 #print "open MType {live_open_types.length}: {live_open_types.join(", ")}"
278 var todo_types
= new List[MClassType]
279 todo_types
.add_all
(live_types
)
280 while not todo_types
.is_empty
do
281 var t
= todo_types
.shift
282 for ot
in live_open_types
do
284 if not ot
.can_resolve_for
(t
, t
, mainmodule
) then continue
285 var rt
= ot
.anchor_to
(mainmodule
, t
)
286 if live_types
.has
(rt
) then continue
287 #print "{ot}/{t} -> {rt}"
293 #print "MType {live_types.length}: {live_types.join(", ")}"
295 #print "open cast MType {live_open_cast_types.length}: {live_open_cast_types.join(", ")}"
296 for ot
in live_open_cast_types
do
297 #print "live_open_cast_type: {ot}"
298 for t
in live_types
do
299 if not ot
.can_resolve_for
(t
, t
, mainmodule
) then continue
300 var rt
= ot
.anchor_to
(mainmodule
, t
)
301 live_cast_types
.add
(rt
)
302 #print " {ot}/{t} -> {rt}"
305 #print "cast MType {live_cast_types.length}: {live_cast_types.join(", ")}"
308 private fun check_depth
(mtype
: MClassType)
312 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}.")
316 fun add_new
(recv
: MClassType, mtype
: MClassType)
318 assert not recv
.need_anchor
319 if mtype
.need_anchor
then
320 if live_open_types
.has
(mtype
) then return
321 live_open_types
.add
(mtype
)
323 if live_types
.has
(mtype
) then return
324 live_types
.add
(mtype
)
327 var mclass
= mtype
.mclass
328 if live_classes
.has
(mclass
) then return
329 live_classes
.add
(mclass
)
331 for p
in totry_methods
do try_send
(mtype
, p
)
332 for p
in live_super_sends
do try_super_send
(mtype
, p
)
334 # Remove cleared ones
335 for p
in totry_methods_to_remove
do totry_methods
.remove
(p
)
336 totry_methods_to_remove
.clear
338 var bound_mtype
= mtype
.anchor_to
(mainmodule
, recv
)
339 for cd
in bound_mtype
.collect_mclassdefs
(mainmodule
)
341 if not self.modelbuilder
.mclassdef2nclassdef
.has_key
(cd
) then continue
342 var nclassdef
= self.modelbuilder
.mclassdef2nclassdef
[cd
]
343 for npropdef
in nclassdef
.n_propdefs
do
344 if not npropdef
isa AAttrPropdef then continue
345 var nexpr
= npropdef
.n_expr
346 if nexpr
== null then continue
347 var mpropdef
= npropdef
.mpropdef
.as(not null)
348 var v
= new RapidTypeVisitor(self, bound_mtype
, mpropdef
)
355 fun add_cast
(mtype
: MType)
357 if mtype
.need_anchor
then
358 live_open_cast_types
.add
(mtype
)
360 live_cast_types
.add
(mtype
)
364 fun try_send
(recv
: MClassType, mproperty
: MMethod)
366 recv
= recv
.mclass
.intro
.bound_mtype
367 if not recv
.has_mproperty
(mainmodule
, mproperty
) then return
368 var d
= mproperty
.lookup_first_definition
(mainmodule
, recv
)
372 fun add_call
(mpropdef
: MMethodDef)
374 if live_methoddefs
.has
(mpropdef
) then return
375 live_methoddefs
.add
(mpropdef
)
378 var mproperty
= mpropdef
.mproperty
379 if mproperty
.mpropdefs
.length
<= 1 then return
380 # If all definitions of a method are live, we can remove the definition of the totry set
381 for d
in mproperty
.mpropdefs
do
382 if d
.is_abstract
then continue
383 if not live_methoddefs
.has
(d
) then return
385 #print "full property: {mpropdef.mproperty} for {mpropdef.mproperty.mpropdefs.length} definitions"
386 totry_methods_to_remove
.add
(mpropdef
.mproperty
)
389 fun add_send
(recv
: MType, mproperty
: MMethod)
391 if try_methods
.has
(mproperty
) then return
392 #print "new prop: {mproperty}"
393 live_methods
.add
(mproperty
)
394 try_methods
.add
(mproperty
)
395 if mproperty
.mpropdefs
.length
== 1 then
396 # If there is only one definition, just add the definition and do not try again the property
397 var d
= mproperty
.mpropdefs
.first
401 # Else, the property is potentially called with various reciever
402 # So just try the methods with existing receiver and register it for future receiver
403 totry_methods
.add
(mproperty
)
404 for c
in live_classes
do
405 try_send
(c
.intro
.bound_mtype
, mproperty
)
409 fun try_super_send
(recv
: MClassType, mpropdef
: MMethodDef)
411 recv
= recv
.mclass
.intro
.bound_mtype
412 if not recv
.collect_mclassdefs
(mainmodule
).has
(mpropdef
.mclassdef
) then return
413 var d
= mpropdef
.lookup_next_definition
(mainmodule
, recv
)
417 fun add_super_send
(recv
: MType, mpropdef
: MMethodDef)
419 if live_super_sends
.has
(mpropdef
) then return
420 #print "new super prop: {mpropdef}"
421 live_super_sends
.add
(mpropdef
)
422 for t
in live_types
do
423 try_super_send
(t
, mpropdef
)
428 class RapidTypeVisitor
431 var analysis
: RapidTypeAnalysis
432 var receiver
: MClassType
433 var mpropdef
: MPropDef
435 init(analysis
: RapidTypeAnalysis, receiver
: MClassType, mpropdef
: MPropDef)
437 self.analysis
= analysis
438 self.receiver
= receiver
439 self.mpropdef
= mpropdef
440 assert not receiver
.need_anchor
445 n
.accept_rapid_type_visitor
(self)
447 var implicit_cast_to
= n
.implicit_cast_to
448 if implicit_cast_to
!= null then self.add_cast_type
(implicit_cast_to
)
451 # RTA does not enter in AAnnotations
452 if not n
isa AAnnotations then
457 fun cleanup_type
(mtype
: MType): nullable MClassType
459 mtype
= mtype
.anchor_to
(self.analysis
.mainmodule
, self.receiver
)
460 if mtype
isa MNullType then return null
461 mtype
= mtype
.as_notnullable
462 assert mtype
isa MClassType
463 assert not mtype
.need_anchor
467 fun get_class
(name
: String): MClass
469 return analysis
.mainmodule
.get_primitive_class
(name
)
472 fun get_method
(recv
: MType, name
: String): MMethod
474 var mtype
= cleanup_type
(recv
)
476 return self.analysis
.modelbuilder
.force_get_primitive_method
(self.current_node
.as(not null), name
, mtype
.mclass
, self.analysis
.mainmodule
)
479 fun add_type
(mtype
: MClassType) do analysis
.add_new
(receiver
, mtype
)
481 fun add_monomorphic_send
(mtype
: MType, mproperty
: MMethod)
483 analysis
.live_methods
.add
(mproperty
)
484 analysis
.try_send
(mtype
.as(MClassType), mproperty
)
487 fun add_send
(mtype
: MType, mproperty
: MMethod) do analysis
.add_send
(mtype
, mproperty
)
489 fun add_cast_type
(mtype
: MType) do analysis
.add_cast
(mtype
)
491 fun add_callsite
(callsite
: nullable CallSite) do if callsite
!= null then
492 analysis
.add_send
(callsite
.recv
, callsite
.mproperty
)
493 analysis
.live_callsites
.add
(callsite
)
500 private fun accept_rapid_type_visitor
(v
: RapidTypeVisitor)
506 redef fun accept_rapid_type_visitor
(v
)
508 v
.add_type
(self.mtype
.as(MClassType))
512 redef class AFloatExpr
513 redef fun accept_rapid_type_visitor
(v
)
515 v
.add_type
(self.mtype
.as(MClassType))
519 redef class ACharExpr
520 redef fun accept_rapid_type_visitor
(v
)
522 v
.add_type
(self.mtype
.as(MClassType))
526 redef class AArrayExpr
527 redef fun accept_rapid_type_visitor
(v
)
529 var mtype
= self.mtype
.as(MClassType)
531 var native
= v
.analysis
.mainmodule
.get_primitive_class
("NativeArray").get_mtype
([mtype
.arguments
.first
])
533 mtype
= v
.cleanup_type
(mtype
).as(not null)
534 var prop
= v
.get_method
(mtype
, "with_native")
535 v
.add_monomorphic_send
(mtype
, prop
)
539 redef class AStringFormExpr
540 redef fun accept_rapid_type_visitor
(v
)
542 var native
= v
.get_class
("NativeString").mclass_type
544 var prop
= v
.get_method
(native
, "to_s_with_length")
545 v
.add_monomorphic_send
(native
, prop
)
549 redef class ASuperstringExpr
550 redef fun accept_rapid_type_visitor
(v
)
552 var arraytype
= v
.get_class
("Array").get_mtype
([v
.get_class
("Object").mclass_type
])
553 v
.add_type
(arraytype
)
554 v
.add_type
(v
.get_class
("NativeArray").get_mtype
([v
.get_class
("Object").mclass_type
]))
555 var prop
= v
.get_method
(arraytype
, "join")
556 v
.add_monomorphic_send
(arraytype
, prop
)
557 var prop2
= v
.get_method
(arraytype
, "with_native")
558 v
.add_monomorphic_send
(arraytype
, prop2
)
562 redef class ACrangeExpr
563 redef fun accept_rapid_type_visitor
(v
)
565 var mtype
= self.mtype
.as(MClassType)
567 v
.add_callsite
(init_callsite
)
571 redef class AOrangeExpr
572 redef fun accept_rapid_type_visitor
(v
)
574 var mtype
= self.mtype
.as(MClassType)
576 v
.add_callsite
(init_callsite
)
580 redef class ATrueExpr
581 redef fun accept_rapid_type_visitor
(v
)
583 v
.add_type
(self.mtype
.as(MClassType))
587 redef class AFalseExpr
588 redef fun accept_rapid_type_visitor
(v
)
590 v
.add_type
(self.mtype
.as(MClassType))
595 redef fun accept_rapid_type_visitor
(v
)
597 v
.add_cast_type
(self.cast_type
.as(not null))
601 redef class AAsCastExpr
602 redef fun accept_rapid_type_visitor
(v
)
604 v
.add_cast_type
(self.mtype
.as(not null))
608 redef class ASendExpr
609 redef fun accept_rapid_type_visitor
(v
)
611 v
.add_callsite
(callsite
)
616 redef class ASendReassignFormExpr
617 redef fun accept_rapid_type_visitor
(v
)
619 v
.add_callsite
(callsite
)
620 v
.add_callsite
(reassign_callsite
)
621 v
.add_callsite
(write_callsite
)
625 redef class AVarReassignExpr
626 redef fun accept_rapid_type_visitor
(v
)
628 v
.add_callsite
(reassign_callsite
)
632 redef class AAttrReassignExpr
633 redef fun accept_rapid_type_visitor
(v
)
635 v
.add_callsite
(reassign_callsite
)
639 redef class ASuperExpr
640 redef fun accept_rapid_type_visitor
(v
)
642 var callsite
= self.callsite
643 if callsite
!= null then
644 v
.add_callsite
(callsite
)
648 v
.analysis
.add_super_send
(v
.receiver
, mpropdef
.as(not null))
653 redef fun accept_rapid_type_visitor
(v
)
655 v
.add_callsite
(self.method_iterator
)
656 v
.add_callsite
(self.method_is_ok
)
657 if self.variables
.length
== 1 then
658 v
.add_callsite
(self.method_item
)
659 else if self.variables
.length
== 2 then
660 v
.add_callsite
(self.method_key
)
661 v
.add_callsite
(self.method_item
)
665 v
.add_callsite
(self.method_next
)
670 redef fun accept_rapid_type_visitor
(v
)
672 var mtype
= self.mtype
.as(MClassType)
674 v
.add_callsite
(callsite
)