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
33 redef class ModelBuilder
34 fun do_rapid_type_analysis
(mainmodule
: MModule): RapidTypeAnalysis
36 var analysis
= new RapidTypeAnalysis(self, mainmodule
)
42 # RapidTypeAnalysis looks for alive rapid types in application.
43 # The entry point of the analysis is the mainmodule of the application.
44 class RapidTypeAnalysis
45 # The modelbuilder used to get the AST.
46 var modelbuilder
: ModelBuilder
48 # The main module of the analysis.
49 # Used to perform types operations.
50 var mainmodule
: MModule
52 # The pool to live types.
53 # During the analysis, new types are added and combined with
54 # live_methods to determine new methoddefs to visit
55 var live_types
= new HashSet[MClassType]
57 # The pool of undesolved live types
58 # They are globally resolved at the end of the analaysis
59 var live_open_types
= new HashSet[MClassType]
61 # Live (instantiated) classes.
62 var live_classes
= new HashSet[MClass]
64 # The pool of types used to perform type checks (isa and as).
65 var live_cast_types
= new HashSet[MType]
67 # The pool of undesolved types used to perform type checks (isa and as).
68 # They are globally resolved at the end of the analaysis
69 var live_open_cast_types
= new HashSet[MType]
71 # Live method definitions.
72 var live_methoddefs
= new HashSet[MMethodDef]
75 var live_methods
= new HashSet[MMethod]
78 var live_super_sends
= new HashSet[MMethodDef]
80 # Return a ready-to-save CSV document objet that agregates informations about live types.
81 # Each discovered type is listed in a line, with its status: resolution, liveness, cast-liveness.
82 # Note: types are listed in an alphanumeric order to improve human reading.
83 fun live_types_to_csv
: CSVDocument
85 # Gather all kind of type
86 var typeset
= new HashSet[MType]
87 typeset
.add_all
(live_types
)
88 typeset
.add_all
(live_open_types
)
89 typeset
.add_all
(live_cast_types
)
90 typeset
.add_all
(live_open_cast_types
)
91 var types
= typeset
.to_a
92 (new CachedAlphaComparator).sort
(types
)
93 var res
= new CSVDocument
94 res
.header
= ["Type", "Resolution", "Liveness", "Cast-liveness"]
97 if t
.need_anchor
then reso
= "OPEN " else reso
= "CLOSED"
99 if t
isa MClassType and (live_types
.has
(t
) or live_open_types
.has
(t
)) then live
= "LIVE" else live
= "DEAD"
101 if live_cast_types
.has
(t
) or live_open_cast_types
.has
(t
) then cast
= "CAST LIVE" else cast
= "CAST DEAD"
102 res
.add_line
(t
, reso
, live
, cast
)
107 # Methods that are are still candidate to the try_send
108 private var totry_methods
= new HashSet[MMethod]
110 # The method definitions that remain to visit
111 private var todo
= new List[MMethodDef]
113 private fun force_alive
(classname
: String)
115 var classes
= self.modelbuilder
.model
.get_mclasses_by_name
(classname
)
116 if classes
!= null then for c
in classes
do self.add_new
(c
.mclass_type
, c
.mclass_type
)
119 # Run the analysis until all visitable method definitions are visited.
122 var maintype
= mainmodule
.sys_type
123 if maintype
== null then return # No entry point
124 add_new
(maintype
, maintype
)
125 var initprop
= mainmodule
.try_get_primitive_method
("init", maintype
.mclass
)
126 if initprop
!= null then
127 add_send
(maintype
, initprop
)
129 var mainprop
= mainmodule
.try_get_primitive_method
("main", maintype
.mclass
)
130 if mainprop
!= null then
131 add_send
(maintype
, mainprop
)
134 # Force primitive types
140 while not todo
.is_empty
do
141 var mmethoddef
= todo
.shift
142 #print "# visit {mmethoddef}"
143 var v
= new RapidTypeVisitor(self, mmethoddef
.mclassdef
.bound_mtype
, mmethoddef
)
145 var vararg_rank
= mmethoddef
.msignature
.vararg_rank
146 if vararg_rank
> -1 then
147 var node
= self.modelbuilder
.mpropdef2npropdef
[mmethoddef
]
148 var elttype
= mmethoddef
.msignature
.mparameters
[vararg_rank
].mtype
149 #elttype = elttype.anchor_to(self.mainmodule, v.receiver)
150 var vararg
= self.mainmodule
.get_primitive_class
("Array").get_mtype
([elttype
])
152 var native
= self.mainmodule
.get_primitive_class
("NativeArray").get_mtype
([elttype
])
154 v
.add_monomorphic_send
(vararg
, self.modelbuilder
.force_get_primitive_method
(node
, "with_native", vararg
.mclass
, self.mainmodule
))
158 for i
in [0..mmethoddef
.msignature
.arity
[ do
159 var origtype
= mmethoddef
.mproperty
.intro
.msignature
.mparameters
[i
].mtype
160 if not origtype
.need_anchor
then continue # skip non covariant stuff
161 var paramtype
= mmethoddef
.msignature
.mparameters
[i
].mtype
162 #paramtype = v.cleanup_type(paramtype).as(not null)
166 if not modelbuilder
.mpropdef2npropdef
.has_key
(mmethoddef
) then
167 # It is an init for a class?
168 if mmethoddef
.mproperty
.name
== "init" then
169 var nclassdef
= self.modelbuilder
.mclassdef2nclassdef
[mmethoddef
.mclassdef
]
170 var super_inits
= nclassdef
.super_inits
171 if super_inits
!= null then
172 #assert args.length == 1
173 for su
in super_inits
do
174 v
.add_monomorphic_send
(v
.receiver
, su
)
184 var npropdef
= modelbuilder
.mpropdef2npropdef
[mmethoddef
]
186 if npropdef
isa AConcreteMethPropdef then
187 var auto_super_inits
= npropdef
.auto_super_inits
188 if auto_super_inits
!= null then
189 for auto_super_init
in auto_super_inits
do
190 v
.add_callsite
(auto_super_init
)
193 else if npropdef
isa AInternMethPropdef or
194 (npropdef
isa AExternMethPropdef and npropdef
.n_extern
!= null) then
195 # UGLY: We force the "instantation" of the concrete return type if any
196 var ret
= mmethoddef
.msignature
.return_mtype
197 if ret
!= null and ret
isa MClassType and ret
.mclass
.kind
!= abstract_kind
and ret
.mclass
.kind
!= interface_kind
then
200 else if npropdef
isa AExternMethPropdef then
201 var nclassdef
= npropdef
.parent
.as(AClassdef)
202 v
.enter_visit
(npropdef
)
203 else if npropdef
isa AExternInitPropdef then
204 v
.add_type
(v
.receiver
)
209 v
.enter_visit
(npropdef
)
212 #print "MMethod {live_methods.length}: {live_methods.join(", ")}"
213 #print "MMethodDef {live_methoddefs.length}: {live_methoddefs.join(", ")}"
215 #print "open MType {live_open_types.length}: {live_open_types.join(", ")}"
216 var todo_types
= new List[MClassType]
217 todo_types
.add_all
(live_types
)
218 while not todo_types
.is_empty
do
219 var t
= todo_types
.shift
220 for ot
in live_open_types
do
222 if not ot
.can_resolve_for
(t
, t
, mainmodule
) then continue
223 var rt
= ot
.anchor_to
(mainmodule
, t
)
224 if live_types
.has
(rt
) then continue
225 #print "{ot}/{t} -> {rt}"
231 #print "MType {live_types.length}: {live_types.join(", ")}"
233 #print "open cast MType {live_open_cast_types.length}: {live_open_cast_types.join(", ")}"
234 for ot
in live_open_cast_types
do
235 #print "live_open_cast_type: {ot}"
236 for t
in live_types
do
237 if not ot
.can_resolve_for
(t
, t
, mainmodule
) then continue
238 var rt
= ot
.anchor_to
(mainmodule
, t
)
239 live_cast_types
.add
(rt
)
240 #print " {ot}/{t} -> {rt}"
243 #print "cast MType {live_cast_types.length}: {live_cast_types.join(", ")}"
246 private fun check_depth
(mtype
: MClassType)
250 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}.")
254 fun add_new
(recv
: MClassType, mtype
: MClassType)
256 assert not recv
.need_anchor
257 if mtype
.need_anchor
then
258 if live_open_types
.has
(mtype
) then return
259 live_open_types
.add
(mtype
)
261 if live_types
.has
(mtype
) then return
262 live_types
.add
(mtype
)
265 var mclass
= mtype
.mclass
266 if live_classes
.has
(mclass
) then return
267 live_classes
.add
(mclass
)
269 for p
in totry_methods
do try_send
(mtype
, p
)
270 for p
in live_super_sends
do try_super_send
(mtype
, p
)
272 var bound_mtype
= mtype
.anchor_to
(mainmodule
, recv
)
273 for cd
in bound_mtype
.collect_mclassdefs
(mainmodule
)
275 if not self.modelbuilder
.mclassdef2nclassdef
.has_key
(cd
) then continue
276 var nclassdef
= self.modelbuilder
.mclassdef2nclassdef
[cd
]
277 for npropdef
in nclassdef
.n_propdefs
do
278 if not npropdef
isa AAttrPropdef then continue
279 var nexpr
= npropdef
.n_expr
280 if nexpr
== null then continue
281 var mpropdef
= npropdef
.mpropdef
.as(not null)
282 var v
= new RapidTypeVisitor(self, bound_mtype
, mpropdef
)
289 fun add_cast
(mtype
: MType)
291 if mtype
.need_anchor
then
292 live_open_cast_types
.add
(mtype
)
294 live_cast_types
.add
(mtype
)
298 fun try_send
(recv
: MClassType, mproperty
: MMethod)
300 recv
= recv
.mclass
.intro
.bound_mtype
301 if not recv
.has_mproperty
(mainmodule
, mproperty
) then return
302 var d
= mproperty
.lookup_first_definition
(mainmodule
, recv
)
306 fun add_call
(mpropdef
: MMethodDef)
308 if live_methoddefs
.has
(mpropdef
) then return
309 live_methoddefs
.add
(mpropdef
)
312 var mproperty
= mpropdef
.mproperty
313 if mproperty
.mpropdefs
.length
<= 1 then return
314 # If all definitions of a method are live, we can remove the definition of the totry set
315 for d
in mproperty
.mpropdefs
do
316 if d
.is_abstract
then continue
317 if not live_methoddefs
.has
(d
) then return
319 #print "full property: {mpropdef.mproperty} for {mpropdef.mproperty.mpropdefs.length} definitions"
320 totry_methods
.remove
(mpropdef
.mproperty
)
323 fun add_send
(recv
: MType, mproperty
: MMethod)
325 if live_methods
.has
(mproperty
) then return
326 #print "new prop: {mproperty}"
327 live_methods
.add
(mproperty
)
328 if mproperty
.mpropdefs
.length
== 1 then
329 # If there is only one definition, just add the definition and do not try again the property
330 var d
= mproperty
.mpropdefs
.first
334 # Else, the property is potentially called with various reciever
335 # So just try the methods with existing receiver and register it for future receiver
336 totry_methods
.add
(mproperty
)
337 for c
in live_classes
do
338 try_send
(c
.intro
.bound_mtype
, mproperty
)
342 fun try_super_send
(recv
: MClassType, mpropdef
: MMethodDef)
344 recv
= recv
.mclass
.intro
.bound_mtype
345 if not recv
.collect_mclassdefs
(mainmodule
).has
(mpropdef
.mclassdef
) then return
346 var d
= mpropdef
.lookup_next_definition
(mainmodule
, recv
)
350 fun add_super_send
(recv
: MType, mpropdef
: MMethodDef)
352 if live_super_sends
.has
(mpropdef
) then return
353 #print "new super prop: {mpropdef}"
354 live_super_sends
.add
(mpropdef
)
355 for t
in live_types
do
356 try_super_send
(t
, mpropdef
)
361 class RapidTypeVisitor
364 var analysis
: RapidTypeAnalysis
365 var receiver
: MClassType
366 var mpropdef
: MPropDef
368 init(analysis
: RapidTypeAnalysis, receiver
: MClassType, mpropdef
: MPropDef)
370 self.analysis
= analysis
371 self.receiver
= receiver
372 self.mpropdef
= mpropdef
373 assert not receiver
.need_anchor
378 n
.accept_rapid_type_visitor
(self)
380 var implicit_cast_to
= n
.implicit_cast_to
381 if implicit_cast_to
!= null then self.add_cast_type
(implicit_cast_to
)
384 # RTA does not enter in AAnnotations
385 if not n
isa AAnnotations then
390 fun cleanup_type
(mtype
: MType): nullable MClassType
392 mtype
= mtype
.anchor_to
(self.analysis
.mainmodule
, self.receiver
)
393 if mtype
isa MNullType then return null
394 if mtype
isa MNullableType then mtype
= mtype
.mtype
395 assert mtype
isa MClassType
396 assert not mtype
.need_anchor
400 fun get_class
(name
: String): MClass
402 return analysis
.mainmodule
.get_primitive_class
(name
)
405 fun get_method
(recv
: MType, name
: String): MMethod
407 var mtype
= cleanup_type
(recv
)
409 return self.analysis
.modelbuilder
.force_get_primitive_method
(self.current_node
.as(not null), name
, mtype
.mclass
, self.analysis
.mainmodule
)
412 fun add_type
(mtype
: MClassType) do analysis
.add_new
(receiver
, mtype
)
414 fun add_monomorphic_send
(mtype
: MType, mproperty
: MMethod) do analysis
.try_send
(mtype
.as(MClassType), mproperty
)
416 fun add_send
(mtype
: MType, mproperty
: MMethod) do analysis
.add_send
(mtype
, mproperty
)
418 fun add_cast_type
(mtype
: MType) do analysis
.add_cast
(mtype
)
420 fun add_callsite
(callsite
: nullable CallSite) do if callsite
!= null then analysis
.add_send
(callsite
.recv
, callsite
.mproperty
)
426 private fun accept_rapid_type_visitor
(v
: RapidTypeVisitor)
432 redef fun accept_rapid_type_visitor
(v
)
434 v
.add_type
(self.mtype
.as(MClassType))
438 redef class AFloatExpr
439 redef fun accept_rapid_type_visitor
(v
)
441 v
.add_type
(self.mtype
.as(MClassType))
445 redef class ACharExpr
446 redef fun accept_rapid_type_visitor
(v
)
448 v
.add_type
(self.mtype
.as(MClassType))
452 redef class AArrayExpr
453 redef fun accept_rapid_type_visitor
(v
)
455 var mtype
= self.mtype
.as(MClassType)
457 var native
= v
.analysis
.mainmodule
.get_primitive_class
("NativeArray").get_mtype
([mtype
.arguments
.first
])
459 mtype
= v
.cleanup_type
(mtype
).as(not null)
460 var prop
= v
.get_method
(mtype
, "with_native")
461 v
.add_monomorphic_send
(mtype
, prop
)
465 redef class AStringFormExpr
466 redef fun accept_rapid_type_visitor
(v
)
468 var native
= v
.get_class
("NativeString").mclass_type
470 var prop
= v
.get_method
(native
, "to_s_with_length")
471 v
.add_monomorphic_send
(native
, prop
)
475 redef class ASuperstringExpr
476 redef fun accept_rapid_type_visitor
(v
)
478 var arraytype
= v
.get_class
("Array").get_mtype
([v
.get_class
("Object").mclass_type
])
479 v
.add_type
(arraytype
)
480 v
.add_type
(v
.get_class
("NativeArray").get_mtype
([v
.get_class
("Object").mclass_type
]))
481 var prop
= v
.get_method
(arraytype
, "join")
482 v
.add_monomorphic_send
(arraytype
, prop
)
483 var prop2
= v
.get_method
(arraytype
, "with_native")
484 v
.add_monomorphic_send
(arraytype
, prop2
)
488 redef class ACrangeExpr
489 redef fun accept_rapid_type_visitor
(v
)
491 var mtype
= self.mtype
.as(MClassType)
493 var prop
= v
.get_method
(mtype
, "init")
494 v
.add_monomorphic_send
(mtype
, prop
)
498 redef class AOrangeExpr
499 redef fun accept_rapid_type_visitor
(v
)
501 var mtype
= self.mtype
.as(MClassType)
503 var prop
= v
.get_method
(mtype
, "without_last")
504 v
.add_monomorphic_send
(mtype
, prop
)
508 redef class ATrueExpr
509 redef fun accept_rapid_type_visitor
(v
)
511 v
.add_type
(self.mtype
.as(MClassType))
515 redef class AFalseExpr
516 redef fun accept_rapid_type_visitor
(v
)
518 v
.add_type
(self.mtype
.as(MClassType))
523 redef fun accept_rapid_type_visitor
(v
)
525 v
.add_cast_type
(self.cast_type
.as(not null))
529 redef class AAsCastExpr
530 redef fun accept_rapid_type_visitor
(v
)
532 v
.add_cast_type
(self.mtype
.as(not null))
536 redef class ASendExpr
537 redef fun accept_rapid_type_visitor
(v
)
539 v
.add_callsite
(callsite
)
544 redef class ASendReassignFormExpr
545 redef fun accept_rapid_type_visitor
(v
)
547 v
.add_callsite
(callsite
)
548 v
.add_callsite
(reassign_callsite
)
549 v
.add_callsite
(write_callsite
)
553 redef class AVarReassignExpr
554 redef fun accept_rapid_type_visitor
(v
)
556 v
.add_callsite
(reassign_callsite
)
560 redef class AAttrReassignExpr
561 redef fun accept_rapid_type_visitor
(v
)
563 v
.add_callsite
(reassign_callsite
)
567 redef class ASuperExpr
568 redef fun accept_rapid_type_visitor
(v
)
570 var callsite
= self.callsite
571 if callsite
!= null then
572 v
.add_callsite
(callsite
)
576 v
.analysis
.add_super_send
(v
.receiver
, v
.mpropdef
.as(MMethodDef))
581 redef fun accept_rapid_type_visitor
(v
)
583 var recvtype
= self.n_expr
.mtype
.as(not null)
584 var colltype
= self.coltype
.as(not null)
585 var itmeth
= v
.get_method
(colltype
, "iterator")
586 v
.add_send
(recvtype
, itmeth
)
587 var iteratortype
= itmeth
.intro
.msignature
.return_mtype
.as(MClassType).mclass
.intro
.bound_mtype
588 var objtype
= v
.get_class
("Object").mclass_type
589 v
.add_send
(objtype
, v
.get_method
(iteratortype
, "is_ok"))
590 if self.variables
.length
== 1 then
591 v
.add_send
(objtype
, v
.get_method
(iteratortype
, "item"))
592 else if self.variables
.length
== 2 then
593 v
.add_send
(objtype
, v
.get_method
(iteratortype
, "key"))
594 v
.add_send
(objtype
, v
.get_method
(iteratortype
, "item"))
598 v
.add_send
(objtype
, v
.get_method
(iteratortype
, "next"))
603 redef fun accept_rapid_type_visitor
(v
)
605 var mtype
= self.mtype
.as(MClassType)
607 v
.add_callsite
(callsite
)