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 redef class ModelBuilder
32 fun do_rapid_type_analysis
(mainmodule
: MModule): RapidTypeAnalysis
34 var analysis
= new RapidTypeAnalysis(self, mainmodule
)
40 # RapidTypeAnalysis looks for alive rapid types in application.
41 # The entry point of the analysis is the mainmodule of the application.
42 class RapidTypeAnalysis
43 # The modelbuilder used to get the AST.
44 var modelbuilder
: ModelBuilder
46 # The main module of the analysis.
47 # Used to perform types operations.
48 var mainmodule
: MModule
50 # The pool to live types.
51 # During the analysis, new types are added and combined with
52 # live_methods to determine new methoddefs to visit
53 var live_types
= new HashSet[MClassType]
55 # The pool of undesolved live types
56 # They are globally resolved at the end of the analaysis
57 var live_open_types
= new HashSet[MClassType]
59 # Live (instantiated) classes.
60 var live_classes
= new HashSet[MClass]
62 # The pool of types used to perform type checks (isa and as).
63 var live_cast_types
= new HashSet[MClassType]
65 # The pool of undesolved types used to perform type checks (isa and as).
66 # They are globally resolved at the end of the analaysis
67 var live_open_cast_types
= new HashSet[MType]
69 # Live method definitions.
70 var live_methoddefs
= new HashSet[MMethodDef]
73 var live_methods
= new HashSet[MMethod]
76 var live_super_sends
= new HashSet[MMethodDef]
78 # Methods that are are still candidate to the try_send
79 private var totry_methods
= new HashSet[MMethod]
81 # The method definitions that remain to visit
82 private var todo
= new List[MMethodDef]
84 # Run the analysis until all visitable method definitions are visited.
87 var maintype
= mainmodule
.sys_type
88 if maintype
== null then return # No entry point
89 add_new
(maintype
, maintype
)
90 var initprop
= mainmodule
.try_get_primitive_method
("init", maintype
)
91 if initprop
!= null then
92 add_send
(maintype
, initprop
)
94 var mainprop
= mainmodule
.try_get_primitive_method
("main", maintype
)
95 if mainprop
!= null then
96 add_send
(maintype
, mainprop
)
100 var classes
= self.modelbuilder
.model
.get_mclasses_by_name
("Bool")
101 if classes
!= null then for c
in classes
do self.add_new
(c
.mclass_type
, c
.mclass_type
)
103 while not todo
.is_empty
do
104 var mmethoddef
= todo
.shift
105 #print "# visit {mmethoddef}"
106 var v
= new RapidTypeVisitor(self, mmethoddef
.mclassdef
.bound_mtype
, mmethoddef
)
108 var vararg_rank
= mmethoddef
.msignature
.vararg_rank
109 if vararg_rank
> -1 then
110 var node
= self.modelbuilder
.mpropdef2npropdef
[mmethoddef
]
111 var elttype
= mmethoddef
.msignature
.mparameters
[vararg_rank
].mtype
112 #elttype = elttype.anchor_to(self.mainmodule, v.receiver)
113 var vararg
= self.mainmodule
.get_primitive_class
("Array").get_mtype
([elttype
])
115 vararg
= v
.cleanup_type
(vararg
).as(not null)
116 v
.add_monomorphic_send
(vararg
, self.modelbuilder
.force_get_primitive_method
(node
, "with_native", vararg
, self.mainmodule
))
117 var native
= self.mainmodule
.get_primitive_class
("NativeArray").get_mtype
([elttype
])
122 for i
in [0..mmethoddef
.msignature
.arity
[ do
123 var origtype
= mmethoddef
.mproperty
.intro
.msignature
.mparameters
[i
].mtype
124 if not origtype
.need_anchor
then continue # skip non covariant stuff
125 var paramtype
= mmethoddef
.msignature
.mparameters
[i
].mtype
126 #paramtype = v.cleanup_type(paramtype).as(not null)
130 if not modelbuilder
.mpropdef2npropdef
.has_key
(mmethoddef
) then
131 # It is an init for a class?
132 if mmethoddef
.mproperty
.name
== "init" then
133 var nclassdef
= self.modelbuilder
.mclassdef2nclassdef
[mmethoddef
.mclassdef
]
134 var super_inits
= nclassdef
.super_inits
135 if super_inits
!= null then
136 #assert args.length == 1
137 for su
in super_inits
do
138 v
.add_monomorphic_send
(v
.receiver
, su
)
148 var npropdef
= modelbuilder
.mpropdef2npropdef
[mmethoddef
]
150 if npropdef
isa AConcreteMethPropdef then
151 var auto_super_inits
= npropdef
.auto_super_inits
152 if auto_super_inits
!= null then
153 for auto_super_init
in auto_super_inits
do
154 v
.add_monomorphic_send
(v
.receiver
, auto_super_init
)
157 else if npropdef
isa AInternMethPropdef or npropdef
isa AExternMethPropdef then
158 # UGLY: We force the "instantation" of the concrete return type if any
159 var ret
= mmethoddef
.msignature
.return_mtype
160 if ret
!= null and ret
isa MClassType and ret
.mclass
.kind
!= abstract_kind
and ret
.mclass
.kind
!= interface_kind
then
163 else if npropdef
isa AExternInitPropdef then
164 v
.add_type
(v
.receiver
)
169 v
.enter_visit
(npropdef
)
172 #print "MMethod {live_methods.length}: {live_methods.join(", ")}"
173 #print "MMethodDef {live_methoddefs.length}: {live_methoddefs.join(", ")}"
175 #print "open MType {live_open_types.length}: {live_open_types.join(", ")}"
176 var todo_types
= new List[MClassType]
177 todo_types
.add_all
(live_types
)
178 while not todo_types
.is_empty
do
179 var t
= todo_types
.shift
180 for ot
in live_open_types
do
182 if not ot
.can_resolve_for
(t
, t
, mainmodule
) then continue
183 var rt
= ot
.anchor_to
(mainmodule
, t
)
184 if live_types
.has
(rt
) then continue
185 #print "{ot}/{t} -> {rt}"
191 #print "MType {live_types.length}: {live_types.join(", ")}"
193 #print "open cast MType {live_open_cast_types.length}: {live_open_cast_types.join(", ")}"
194 for ot
in live_open_cast_types
do
195 #print "live_open_cast_type: {ot}"
196 for t
in live_types
do
197 if not ot
.can_resolve_for
(t
, t
, mainmodule
) then continue
198 var rt
= ot
.anchor_to
(mainmodule
, t
)
199 if rt
isa MNullableType then rt
= rt
.mtype
200 assert rt
isa MClassType
201 live_cast_types
.add
(rt
)
202 #print " {ot}/{t} -> {rt}"
205 #print "cast MType {live_cast_types.length}: {live_cast_types.join(", ")}"
208 private fun check_depth
(mtype
: MClassType)
212 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}.")
216 fun add_new
(recv
: MClassType, mtype
: MClassType)
218 assert not recv
.need_anchor
219 if mtype
.need_anchor
then
220 if live_open_types
.has
(mtype
) then return
221 live_open_types
.add
(mtype
)
223 if live_types
.has
(mtype
) then return
224 live_types
.add
(mtype
)
227 var mclass
= mtype
.mclass
228 if live_classes
.has
(mclass
) then return
229 live_classes
.add
(mclass
)
231 for p
in totry_methods
do try_send
(mtype
, p
)
232 for p
in live_super_sends
do try_super_send
(mtype
, p
)
234 var bound_mtype
= mtype
.anchor_to
(mainmodule
, recv
)
235 for cd
in bound_mtype
.collect_mclassdefs
(mainmodule
)
237 if not self.modelbuilder
.mclassdef2nclassdef
.has_key
(cd
) then continue
238 var nclassdef
= self.modelbuilder
.mclassdef2nclassdef
[cd
]
239 for npropdef
in nclassdef
.n_propdefs
do
240 if not npropdef
isa AAttrPropdef then continue
241 var nexpr
= npropdef
.n_expr
242 if nexpr
== null then continue
243 var mpropdef
= npropdef
.mpropdef
.as(not null)
244 var v
= new RapidTypeVisitor(self, bound_mtype
, mpropdef
)
251 fun add_cast
(mtype
: MType)
253 if mtype
isa MNullableType then mtype
= mtype
.mtype
254 if mtype
.need_anchor
then
255 live_open_cast_types
.add
(mtype
)
257 assert mtype
isa MClassType
258 live_cast_types
.add
(mtype
)
262 fun try_send
(recv
: MClassType, mproperty
: MMethod)
264 recv
= recv
.mclass
.intro
.bound_mtype
265 if not recv
.has_mproperty
(mainmodule
, mproperty
) then return
266 var d
= mproperty
.lookup_first_definition
(mainmodule
, recv
)
270 fun add_call
(mpropdef
: MMethodDef)
272 if live_methoddefs
.has
(mpropdef
) then return
273 live_methoddefs
.add
(mpropdef
)
276 var mproperty
= mpropdef
.mproperty
277 if mproperty
.mpropdefs
.length
<= 1 then return
278 # If all definitions of a method are live, we can remove the definition of the totry set
279 for d
in mproperty
.mpropdefs
do
280 if d
.is_abstract
then continue
281 if not live_methoddefs
.has
(d
) then return
283 #print "full property: {mpropdef.mproperty} for {mpropdef.mproperty.mpropdefs.length} definitions"
284 totry_methods
.remove
(mpropdef
.mproperty
)
287 fun add_send
(recv
: MType, mproperty
: MMethod)
289 if live_methods
.has
(mproperty
) then return
290 #print "new prop: {mproperty}"
291 live_methods
.add
(mproperty
)
292 if mproperty
.mpropdefs
.length
== 1 then
293 # If there is only one definition, just add the definition and do not try again the property
294 var d
= mproperty
.mpropdefs
.first
298 # Else, the property is potentially called with various reciever
299 # So just try the methods with existing receiver and register it for future receiver
300 totry_methods
.add
(mproperty
)
301 for c
in live_classes
do
302 try_send
(c
.intro
.bound_mtype
, mproperty
)
306 fun try_super_send
(recv
: MClassType, mpropdef
: MMethodDef)
308 recv
= recv
.mclass
.intro
.bound_mtype
309 if not recv
.collect_mclassdefs
(mainmodule
).has
(mpropdef
.mclassdef
) then return
310 var d
= mpropdef
.lookup_next_definition
(mainmodule
, recv
)
314 fun add_super_send
(recv
: MType, mpropdef
: MMethodDef)
316 if live_super_sends
.has
(mpropdef
) then return
317 #print "new super prop: {mpropdef}"
318 live_super_sends
.add
(mpropdef
)
319 for t
in live_types
do
320 try_super_send
(t
, mpropdef
)
325 class RapidTypeVisitor
328 var analysis
: RapidTypeAnalysis
329 var receiver
: MClassType
330 var mpropdef
: MPropDef
332 init(analysis
: RapidTypeAnalysis, receiver
: MClassType, mpropdef
: MPropDef)
334 self.analysis
= analysis
335 self.receiver
= receiver
336 self.mpropdef
= mpropdef
337 assert not receiver
.need_anchor
342 if n
== null then return
343 n
.accept_rapid_type_visitor
(self)
345 var implicit_cast_to
= n
.implicit_cast_to
346 if implicit_cast_to
!= null then self.add_cast_type
(implicit_cast_to
)
349 # RTA does not enter in AAnnotations
350 if not n
isa AAnnotations then
355 fun cleanup_type
(mtype
: MType): nullable MClassType
357 mtype
= mtype
.anchor_to
(self.analysis
.mainmodule
, self.receiver
)
358 if mtype
isa MNullType then return null
359 if mtype
isa MNullableType then mtype
= mtype
.mtype
360 assert mtype
isa MClassType
361 assert not mtype
.need_anchor
365 fun get_class
(name
: String): MClass
367 return analysis
.mainmodule
.get_primitive_class
(name
)
370 fun get_method
(recv
: MType, name
: String): MMethod
372 var mtype
= cleanup_type
(recv
)
374 return self.analysis
.modelbuilder
.force_get_primitive_method
(self.current_node
.as(not null), name
, mtype
, self.analysis
.mainmodule
)
377 fun add_type
(mtype
: MClassType) do analysis
.add_new
(receiver
, mtype
)
379 fun add_monomorphic_send
(mtype
: MType, mproperty
: MMethod) do analysis
.try_send
(mtype
.as(MClassType), mproperty
)
381 fun add_send
(mtype
: MType, mproperty
: MMethod) do analysis
.add_send
(mtype
, mproperty
)
383 fun add_cast_type
(mtype
: MType) do analysis
.add_cast
(mtype
)
389 private fun accept_rapid_type_visitor
(v
: RapidTypeVisitor)
395 redef fun accept_rapid_type_visitor
(v
)
397 v
.add_type
(self.mtype
.as(MClassType))
401 redef class AFloatExpr
402 redef fun accept_rapid_type_visitor
(v
)
404 v
.add_type
(self.mtype
.as(MClassType))
408 redef class ACharExpr
409 redef fun accept_rapid_type_visitor
(v
)
411 v
.add_type
(self.mtype
.as(MClassType))
415 redef class AArrayExpr
416 redef fun accept_rapid_type_visitor
(v
)
418 var mtype
= self.mtype
.as(MClassType)
420 var native
= v
.analysis
.mainmodule
.get_primitive_class
("NativeArray").get_mtype
([mtype
.arguments
.first
])
422 mtype
= v
.cleanup_type
(mtype
).as(not null)
423 var prop
= v
.get_method
(mtype
, "with_native")
424 v
.add_monomorphic_send
(mtype
, prop
)
428 redef class AStringFormExpr
429 redef fun accept_rapid_type_visitor
(v
)
431 var mtype
= self.mtype
.as(MClassType)
433 var native
= v
.get_class
("NativeString").mclass_type
435 var prop
= v
.get_method
(mtype
, "from_cstring")
436 v
.add_monomorphic_send
(mtype
, prop
)
440 redef class ASuperstringExpr
441 redef fun accept_rapid_type_visitor
(v
)
443 var arraytype
= v
.get_class
("Array").get_mtype
([v
.get_class
("Object").mclass_type
])
444 v
.add_type
(arraytype
)
445 v
.add_type
(v
.get_class
("NativeArray").get_mtype
([v
.get_class
("Object").mclass_type
]))
446 var prop
= v
.get_method
(arraytype
, "join")
447 v
.add_monomorphic_send
(arraytype
, prop
)
448 var prop2
= v
.get_method
(arraytype
, "with_native")
449 v
.add_monomorphic_send
(arraytype
, prop2
)
453 redef class ACrangeExpr
454 redef fun accept_rapid_type_visitor
(v
)
456 var mtype
= self.mtype
.as(MClassType)
458 var prop
= v
.get_method
(mtype
, "init")
459 v
.add_monomorphic_send
(mtype
, prop
)
463 redef class AOrangeExpr
464 redef fun accept_rapid_type_visitor
(v
)
466 var mtype
= self.mtype
.as(MClassType)
468 var prop
= v
.get_method
(mtype
, "without_last")
469 v
.add_monomorphic_send
(mtype
, prop
)
473 redef class ATrueExpr
474 redef fun accept_rapid_type_visitor
(v
)
476 v
.add_type
(self.mtype
.as(MClassType))
480 redef class AFalseExpr
481 redef fun accept_rapid_type_visitor
(v
)
483 v
.add_type
(self.mtype
.as(MClassType))
488 redef fun accept_rapid_type_visitor
(v
)
490 v
.add_cast_type
(self.cast_type
.as(not null))
494 redef class AAsCastExpr
495 redef fun accept_rapid_type_visitor
(v
)
497 v
.add_cast_type
(self.mtype
.as(not null))
501 redef class ASendExpr
502 redef fun accept_rapid_type_visitor
(v
)
504 var mproperty
= self.mproperty
.as(not null)
505 var recvtype
= self.n_expr
.mtype
.as(not null)
506 v
.add_send
(recvtype
, mproperty
)
511 redef class ASendReassignFormExpr
512 redef fun accept_rapid_type_visitor
(v
)
514 v
.add_send
(self.read_type
.as(not null), self.reassign_property
.mproperty
)
515 var mproperty
= self.mproperty
.as(not null)
516 var write_mproperty
= self.write_mproperty
.as(not null)
517 if n_expr
isa ASelfExpr then
518 v
.add_monomorphic_send
(v
.receiver
, mproperty
)
519 v
.add_monomorphic_send
(v
.receiver
, write_mproperty
)
521 var recvtype
= self.n_expr
.mtype
.as(not null)
522 v
.add_send
(recvtype
, mproperty
)
523 v
.add_send
(recvtype
, write_mproperty
)
528 redef class AVarReassignExpr
529 redef fun accept_rapid_type_visitor
(v
)
531 v
.add_send
(self.read_type
.as(not null), self.reassign_property
.mproperty
)
535 redef class AAttrReassignExpr
536 redef fun accept_rapid_type_visitor
(v
)
538 v
.add_send
(self.read_type
.as(not null), self.reassign_property
.mproperty
)
542 redef class ASuperExpr
543 redef fun accept_rapid_type_visitor
(v
)
545 var mproperty
= self.mproperty
546 if mproperty
!= null then
547 v
.add_monomorphic_send
(v
.receiver
, mproperty
)
551 v
.analysis
.add_super_send
(v
.receiver
, v
.mpropdef
.as(MMethodDef))
556 redef fun accept_rapid_type_visitor
(v
)
558 var recvtype
= self.n_expr
.mtype
.as(not null)
559 var colltype
= self.coltype
.as(not null)
560 var itmeth
= v
.get_method
(colltype
, "iterator")
561 v
.add_send
(recvtype
, itmeth
)
562 var iteratortype
= itmeth
.intro
.msignature
.return_mtype
.as(MClassType).mclass
.intro
.bound_mtype
563 var objtype
= v
.get_class
("Object").mclass_type
564 v
.add_send
(objtype
, v
.get_method
(iteratortype
, "is_ok"))
565 if self.variables
.length
== 1 then
566 v
.add_send
(objtype
, v
.get_method
(iteratortype
, "item"))
567 else if self.variables
.length
== 2 then
568 v
.add_send
(objtype
, v
.get_method
(iteratortype
, "key"))
569 v
.add_send
(objtype
, v
.get_method
(iteratortype
, "item"))
573 v
.add_send
(objtype
, v
.get_method
(iteratortype
, "next"))
578 redef fun accept_rapid_type_visitor
(v
)
580 var mtype
= self.mtype
.as(MClassType)
582 var mproperty
= self.mproperty
.as(not null)
583 v
.add_monomorphic_send
(mtype
, mproperty
)