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 with heterogenous generics and customization
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.
25 # Heterogenous generics means that each intancied generic class is associated
26 # to a distinct rapid type.
27 # Heterogenous generics has the advantage to resolve the formal generic
28 # parameters types but increase the number of types.
29 # More important, heterogenous generics cannot deal with infinite number of rapid
30 # types since the analyse tries to list them all (so some programs will be badly refused)
32 # Customization means that each method definition is analyzed one per rapid
34 # Customization have the following advantages:
35 # * `self' is monomorphic
36 # * virtual types are all resolved
37 # * live attributes can be determined on each class
38 # But has the disadvantage to explode the number of rapid method: each method
39 # definition for each rapid type that need it
40 module rapid_type_analysis
45 import auto_super_init
47 redef class ModelBuilder
48 fun do_rapid_type_analysis
(mainmodule
: MModule): RapidTypeAnalysis
50 var model
= self.model
51 var analysis
= new RapidTypeAnalysis(self, mainmodule
)
52 var nmodule
= self.nmodules
.first
53 var maintype
= mainmodule
.sys_type
54 if maintype
== null then return analysis
# No entry point
55 analysis
.add_type
(maintype
)
56 var initprop
= mainmodule
.try_get_primitive_method
("init", maintype
)
57 if initprop
!= null then
58 analysis
.add_monomorphic_send
(maintype
, initprop
)
60 var mainprop
= mainmodule
.try_get_primitive_method
("main", maintype
)
61 if mainprop
!= null then
62 analysis
.add_monomorphic_send
(maintype
, mainprop
)
69 # RapidTypeAnalysis looks for alive rapid types in application.
70 # The entry point of the analysis is the mainmodule of the application.
71 class RapidTypeAnalysis
72 # The modelbuilder used to get the AST.
73 var modelbuilder
: ModelBuilder
75 # The main module of the analysis.
76 # Used to perform types operations.
77 var mainmodule
: MModule
79 # The pool to live types.
80 # During the analysis, new types are added and combined with
81 # live_send_sites to determine new customized_methoddefs to visit
82 var live_types
: HashSet[MClassType] = new HashSet[MClassType]
84 # The pool of types used to perform type checks (isa and as).
85 var live_cast_types
: HashSet[MClassType] = new HashSet[MClassType]
87 # Live method definitions.
88 # These method definitions are:
89 # * visited trough a add_send on an already known live_type
90 # * visited trough a add_type for an already known live_send_sites
91 # * visided by a add_monomorphic_send or a add_static_call
92 var live_methoddefs
: HashSet[MMethodDef] = new HashSet[MMethodDef]
94 # The pool of live customized method definitions
95 var live_customized_methoddefs
: HashSet[CustomizedMethodDef] = new HashSet[CustomizedMethodDef]
97 # The pool of live RTA send site
98 # During the analysis, new live_send_sites are added and combined with
99 # live_types to determine new live_customized_methoddefs to visit
100 var live_send_sites
: HashSet[RTASendSite] = new HashSet[RTASendSite]
102 # The customized method definitions that remain to visit
103 private var todo
: List[CustomizedMethodDef] = new List[CustomizedMethodDef]
105 # Add a live type to the pool
107 # If the types is already live, then do nothing.
109 # REQUIRE: not mtype.need_anchor
110 fun add_type
(mtype
: MClassType)
112 if self.live_types
.has
(mtype
) then return
114 assert not mtype
.need_anchor
115 self.live_types
.add
(mtype
)
117 # Collect default attributes
118 for cd
in mtype
.collect_mclassdefs
(self.mainmodule
)
120 var nclassdef
= self.modelbuilder
.mclassdef2nclassdef
[cd
]
121 for npropdef
in nclassdef
.n_propdefs
do
122 if not npropdef
isa AAttrPropdef then continue
123 var nexpr
= npropdef
.n_expr
124 if nexpr
== null then continue
125 var v
= new RapidTypeVisitor(self, nclassdef
, npropdef
.mpropdef
.as(not null), mtype
)
130 for rss
in self.live_send_sites
do
131 if not mtype
.is_subtype
(self.mainmodule
, null, rss
.receiver
) then continue
132 if mtype
.has_mproperty
(self.mainmodule
, rss
.mmethod
) then
133 self.add_monomorphic_send
(mtype
, rss
.mmethod
)
138 # Add a send site to the pool
140 # If the send site is already live, then do nothing.
141 fun add_send
(mtype
: MClassType, mmethod
: MMethod)
143 var rss
= new RTASendSite(mmethod
, mtype
)
144 if self.live_send_sites
.has
(rss
) then return
146 self.live_send_sites
.add
(rss
)
148 for mtype2
in self.live_types
do
149 if not mtype2
.is_subtype
(self.mainmodule
, null, mtype
) then continue
150 if mtype2
.has_mproperty
(self.mainmodule
, mmethod
) then
151 self.add_monomorphic_send
(mtype2
, mmethod
)
156 # Add a monomoprhic send.
157 # The send site is not added to the pool.
158 # The method just determine the associated method definition then
159 # performs a static_call
160 fun add_monomorphic_send
(mtype
: MClassType, mmethod
: MMethod)
162 assert self.live_types
.has
(mtype
)
163 var defs
= mmethod
.lookup_definitions
(self.mainmodule
, mtype
)
164 if defs
.is_empty
then return
165 assert defs
.length
== 1 else print
"conflict on {mtype} for {mmethod}: {defs.join(" ")}"
166 self.add_static_call
(mtype
, defs
.first
)
169 # Add a customized_methoddefs to the pool
170 # Is the customized_methoddefs is already live, then do nothing
171 fun add_static_call
(mtype
: MClassType, mmethoddef
: MMethodDef)
173 assert self.live_types
.has
(mtype
)
174 var rm
= new CustomizedMethodDef(mmethoddef
, mtype
)
175 if self.live_customized_methoddefs
.has
(rm
) then return
176 self.live_customized_methoddefs
.add
(rm
)
178 self.live_methoddefs
.add
(mmethoddef
)
181 # Add mtype to the cast pool.
182 fun add_cast_type
(mtype
: MClassType)
184 if self.live_cast_types
.has
(mtype
) then return
186 assert not mtype
.need_anchor
187 self.live_cast_types
.add
(mtype
)
190 # Run the analysis until all visitable method definitions are visited.
194 var classes
= self.modelbuilder
.model
.get_mclasses_by_name
("Bool")
195 if classes
!= null then for c
in classes
do self.add_type
(c
.mclass_type
)
197 while not todo
.is_empty
do
200 var vararg_rank
= mr
.mmethoddef
.msignature
.vararg_rank
201 if vararg_rank
> -1 then
202 var elttype
= mr
.mmethoddef
.msignature
.parameter_mtypes
[vararg_rank
]
203 elttype
= elttype
.anchor_to
(self.mainmodule
, mr
.receiver
)
204 var vararg
= self.mainmodule
.get_primitive_class
("Array").get_mtype
([elttype
])
205 self.add_type
(vararg
)
206 self.add_monomorphic_send
(vararg
, self.mainmodule
.force_get_primitive_method
("with_native", vararg
))
207 var native
= self.mainmodule
.get_primitive_class
("NativeArray").get_mtype
([elttype
])
208 self.add_type
(native
)
211 if not self.modelbuilder
.mpropdef2npropdef
.has_key
(mr
.mmethoddef
) then
212 # It is an init for a class?
213 if mr
.mmethoddef
.mproperty
.name
== "init" then
214 var nclassdef
= self.modelbuilder
.mclassdef2nclassdef
[mr
.mmethoddef
.mclassdef
]
215 var super_inits
= nclassdef
.super_inits
216 if super_inits
!= null then
217 #assert args.length == 1
218 for su
in super_inits
do
219 self.add_monomorphic_send
(mr
.receiver
, su
)
228 var npropdef
= self.modelbuilder
.mpropdef2npropdef
[mr
.mmethoddef
]
229 if npropdef
isa AConcreteMethPropdef then
230 #npropdef.debug("Visit {mr.mmethoddef} for {mr.receiver}")
231 var nclassdef
= npropdef
.parent
.as(AClassdef)
232 var mmethoddef
= npropdef
.mpropdef
.as(not null)
233 var auto_super_inits
= npropdef
.auto_super_inits
234 if auto_super_inits
!= null then
235 for auto_super_init
in auto_super_inits
do
236 self.add_monomorphic_send
(mr
.receiver
, auto_super_init
)
239 var v
= new RapidTypeVisitor(self, nclassdef
, mmethoddef
, mr
.receiver
)
240 v
.enter_visit
(npropdef
.n_block
)
241 else if npropdef
isa ADeferredMethPropdef then
242 # nothing to do (maybe add a waring?)
243 else if npropdef
isa AAttrPropdef then
245 else if npropdef
isa AInternMethPropdef or npropdef
isa AExternMethPropdef then
246 # UGLY: We force the "instantation" of the concrete return type if any
247 var ret
= mr
.mmethoddef
.msignature
.return_mtype
248 if ret
!= null and ret
isa MClassType and ret
.mclass
.kind
!= abstract_kind
and ret
.mclass
.kind
!= interface_kind
then
249 ret
= ret
.anchor_to
(self.mainmodule
, mr
.receiver
)
252 else if npropdef
isa AExternInitPropdef then
253 self.add_type
(mr
.receiver
)
255 npropdef
.debug
("Not yet implemented")
262 # A method definitions customized to a specific receiver
263 class CustomizedMethodDef
264 var mmethoddef
: MMethodDef
265 var receiver
: MClassType
269 return "{self.mmethoddef}({receiver})"
274 return o
isa CustomizedMethodDef and o
.mmethoddef
== self.mmethoddef
and o
.receiver
== self.receiver
279 return self.mmethoddef
.hash
+ self.receiver
.hash
283 # A method invokation site bounded by a specific receiver
286 var receiver
: MClassType
290 return o
isa RTASendSite and o
.mmethod
== self.mmethod
and o
.receiver
== self.receiver
295 return self.mmethod
.hash
+ self.receiver
.hash
299 private class RapidTypeVisitor
302 var analysis
: RapidTypeAnalysis
304 var nclassdef
: AClassdef
306 var mpropdef
: MPropDef
308 var receiver
: MClassType
310 init(analysis
: RapidTypeAnalysis, nclassdef
: AClassdef, mpropdef
: MPropDef, receiver
: MClassType)
312 self.analysis
= analysis
313 self.nclassdef
= nclassdef
314 self.mpropdef
= mpropdef
315 self.receiver
= receiver
318 # Adapt and remove nullable
319 # return null if we got the null type
320 fun cleanup_type
(mtype
: MType): nullable MClassType
322 mtype
= mtype
.anchor_to
(self.analysis
.mainmodule
, self.receiver
)
323 if mtype
isa MNullType then return null
324 if mtype
isa MNullableType then mtype
= mtype
.mtype
325 assert mtype
isa MClassType
326 assert not mtype
.need_anchor
330 fun add_type
(mtype
: MType)
332 var rapidtype
= cleanup_type
(mtype
)
333 if rapidtype
== null then return # we do not care about null
335 self.analysis
.add_type
(rapidtype
)
336 #self.current_node.debug("add_type {rapidtype}")
339 fun add_send
(mtype
: MType, mproperty
: MMethod)
341 var rapidtype
= cleanup_type
(mtype
)
342 if rapidtype
== null then return # we do not care about null
344 analysis
.add_send
(rapidtype
, mproperty
)
345 #self.current_node.debug("add_send {mproperty}")
348 fun add_monomorphic_send
(mtype
: MType, mproperty
: MMethod)
350 var rapidtype
= cleanup_type
(mtype
)
351 if rapidtype
== null then return # we do not care about null
353 self.analysis
.add_monomorphic_send
(rapidtype
, mproperty
)
354 #self.current_node.debug("add_monomorphic_send {rapidtype} {mproperty}")
357 fun add_cast_type
(mtype
: MType)
359 var rapidtype
= cleanup_type
(mtype
)
360 if rapidtype
== null then return # we do not care about null
362 self.analysis
.add_cast_type
(rapidtype
)
363 #self.current_node.debug("add_cast_type {rapidtype}")
366 redef fun visit
(node
)
368 if node
== null then return
369 node
.accept_rapid_type_vistor
(self)
373 # Force to get the primitive class named `name' or abort
374 fun get_class
(name
: String): MClass
376 return self.analysis
.mainmodule
.get_primitive_class
(name
)
379 # Force to get the primitive property named `name' in the instance `recv' or abort
380 fun get_method
(recv
: MType, name
: String): MMethod
382 var rapidtype
= cleanup_type
(recv
)
383 if rapidtype
== null then abort
385 return self.analysis
.mainmodule
.force_get_primitive_method
(name
, rapidtype
)
392 private fun accept_rapid_type_vistor
(v
: RapidTypeVisitor)
398 redef fun accept_rapid_type_vistor
(v
)
400 v
.add_type
(self.mtype
.as(not null))
404 redef class AFloatExpr
405 redef fun accept_rapid_type_vistor
(v
)
407 v
.add_type
(self.mtype
.as(not null))
411 redef class ACharExpr
412 redef fun accept_rapid_type_vistor
(v
)
414 v
.add_type
(self.mtype
.as(not null))
418 redef class AArrayExpr
419 redef fun accept_rapid_type_vistor
(v
)
421 var mtype
= self.mtype
.as(not null)
423 var native
= v
.get_class
("NativeArray").get_mtype
([mtype
.as(MGenericType).arguments
.first
])
425 var prop
= v
.get_method
(mtype
, "with_native")
426 v
.add_monomorphic_send
(mtype
, prop
)
430 redef class AStringFormExpr
431 redef fun accept_rapid_type_vistor
(v
)
433 var mtype
= self.mtype
.as(not null)
435 var native
= v
.get_class
("NativeString").mclass_type
437 var prop
= v
.get_method
(mtype
, "from_cstring")
438 v
.add_monomorphic_send
(mtype
, prop
)
442 redef class ASuperstringExpr
443 redef fun accept_rapid_type_vistor
(v
)
445 var arraytype
= v
.get_class
("Array").get_mtype
([v
.get_class
("Object").mclass_type
])
446 v
.add_type
(arraytype
)
447 v
.add_type
(v
.get_class
("NativeArray").get_mtype
([v
.get_class
("Object").mclass_type
]))
448 var prop
= v
.get_method
(arraytype
, "join")
449 v
.add_monomorphic_send
(arraytype
, prop
)
453 redef class ACrangeExpr
454 redef fun accept_rapid_type_vistor
(v
)
456 var mtype
= self.mtype
.as(not null)
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_vistor
(v
)
466 var mtype
= self.mtype
.as(not null)
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_vistor
(v
)
476 v
.add_type
(self.mtype
.as(not null))
480 redef class AFalseExpr
481 redef fun accept_rapid_type_vistor
(v
)
483 v
.add_type
(self.mtype
.as(not null))
488 redef fun accept_rapid_type_vistor
(v
)
490 v
.add_cast_type
(self.cast_type
.as(not null))
494 redef class AAsCastExpr
495 redef fun accept_rapid_type_vistor
(v
)
497 v
.add_cast_type
(self.mtype
.as(not null))
503 redef class ASendExpr
504 redef fun accept_rapid_type_vistor
(v
)
506 var mproperty
= self.mproperty
.as(not null)
507 if n_expr
isa ASelfExpr then
508 v
.add_monomorphic_send
(v
.receiver
, mproperty
)
510 var recvtype
= self.n_expr
.mtype
.as(not null)
511 v
.add_send
(recvtype
, mproperty
)
516 redef class ASendReassignFormExpr
517 redef fun accept_rapid_type_vistor
(v
)
519 v
.add_send
(self.read_type
.as(not null), self.reassign_property
.mproperty
)
520 var mproperty
= self.mproperty
.as(not null)
521 var write_mproperty
= self.write_mproperty
.as(not null)
522 if n_expr
isa ASelfExpr then
523 v
.add_monomorphic_send
(v
.receiver
, mproperty
)
524 v
.add_monomorphic_send
(v
.receiver
, write_mproperty
)
526 var recvtype
= self.n_expr
.mtype
.as(not null)
527 v
.add_send
(recvtype
, mproperty
)
528 v
.add_send
(recvtype
, write_mproperty
)
533 redef class AVarReassignExpr
534 redef fun accept_rapid_type_vistor
(v
)
536 v
.add_send
(self.read_type
.as(not null), self.reassign_property
.mproperty
)
540 redef class AAttrReassignExpr
541 redef fun accept_rapid_type_vistor
(v
)
543 v
.add_send
(self.read_type
.as(not null), self.reassign_property
.mproperty
)
547 redef class ASuperExpr
548 redef fun accept_rapid_type_vistor
(v
)
550 var mproperty
= self.mproperty
551 if mproperty
!= null then
552 v
.add_monomorphic_send
(v
.receiver
, mproperty
)
556 #FIXME: we do not want an ugly static call!
557 var mpropdef
= v
.mpropdef
558 var mpropdefs
= mpropdef
.mproperty
.lookup_super_definitions
(mpropdef
.mclassdef
.mmodule
, mpropdef
.mclassdef
.bound_mtype
)
559 if mpropdefs
.length
!= 1 then
560 debug
("MPRODFEFS for super {mpropdef} for {v.receiver}: {mpropdefs.join(", ")}")
562 var msuperpropdef
= mpropdefs
.first
563 assert msuperpropdef
isa MMethodDef
564 v
.analysis
.add_static_call
(v
.receiver
, msuperpropdef
)
569 redef fun accept_rapid_type_vistor
(v
)
571 var recvtype
= self.n_expr
.mtype
.as(not null)
572 var colltype
= v
.get_class
("Collection").mclassdefs
.first
.bound_mtype
573 v
.add_send
(recvtype
, v
.get_method
(colltype
, "iterator"))
574 var iteratortype
= v
.get_class
("Iterator").mclassdefs
.first
.bound_mtype
575 var objtype
= v
.get_class
("Object").mclass_type
576 v
.add_send
(objtype
, v
.get_method
(iteratortype
, "is_ok"))
577 v
.add_send
(objtype
, v
.get_method
(iteratortype
, "item"))
578 v
.add_send
(objtype
, v
.get_method
(iteratortype
, "next"))
583 redef fun accept_rapid_type_vistor
(v
)
585 var recvtype
= self.mtype
.as(not null)
587 v
.add_monomorphic_send
(recvtype
, mproperty
.as(not null))