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 runtime 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 runtime
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 runtime
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 runtime method: each method
39 # definition for each runtime type that need it
45 import auto_super_init
48 var main_type
: nullable MClassType
49 var main_init
: nullable MMethod
50 var main_method
: nullable MMethod
53 redef class ModelBuilder
54 fun do_runtime_type
(mainmodule
: MModule): RuntimeTypeAnalysis
56 var model
= self.model
57 var analysis
= new RuntimeTypeAnalysis(self, mainmodule
)
58 var nmodule
= self.nmodules
.first
59 var mainclass
= self.try_get_mclass_by_name
(nmodule
, mainmodule
, "Sys")
60 if mainclass
== null then return analysis
# No entry point
61 var maintype
= mainclass
.mclass_type
62 analysis
.add_type
(maintype
)
63 mainmodule
.main_type
= maintype
64 var initprop
= self.try_get_mproperty_by_name2
(nmodule
, mainmodule
, maintype
, "init")
65 if initprop
!= null then
66 assert initprop
isa MMethod
67 analysis
.add_monomorphic_send
(maintype
, initprop
)
69 mainmodule
.main_init
= initprop
70 var mainprop
= self.try_get_mproperty_by_name2
(nmodule
, mainmodule
, maintype
, "main")
71 if mainprop
!= null then
72 assert mainprop
isa MMethod
73 analysis
.add_monomorphic_send
(maintype
, mainprop
)
75 mainmodule
.main_method
= mainprop
81 # RuntimeTypeAnalysis looks for alive runtime types in application.
82 # The entry point of the analysis is the mainmodule of the application.
83 class RuntimeTypeAnalysis
84 var modelbuilder
: ModelBuilder
85 var mainmodule
: MModule
86 var live_types
: HashSet[MClassType] = new HashSet[MClassType]
87 var live_cast_types
: HashSet[MClassType] = new HashSet[MClassType]
88 var polymorphic_methods
: HashSet[MMethod] = new HashSet[MMethod]
89 var live_methoddefs
: HashSet[MMethodDef] = new HashSet[MMethodDef]
90 var runtime_methods
: HashSet[RuntimeMethod] = new HashSet[RuntimeMethod]
91 var live_send_site
: HashSet[RuntimeSendSite] = new HashSet[RuntimeSendSite]
93 private var todo
: List[RuntimeMethod] = new List[RuntimeMethod]
95 fun add_type
(mtype
: MClassType)
97 if self.live_types
.has
(mtype
) then return
99 assert not mtype
.need_anchor
100 self.live_types
.add
(mtype
)
102 # Collect default attributes
103 for cd
in mtype
.collect_mclassdefs
(self.mainmodule
)
105 var nclassdef
= self.modelbuilder
.mclassdef2nclassdef
[cd
]
106 for npropdef
in nclassdef
.n_propdefs
do
107 if not npropdef
isa AAttrPropdef then continue
108 var nexpr
= npropdef
.n_expr
109 if nexpr
== null then continue
110 var v
= new RuntimeTypeVisitor(self, nclassdef
, npropdef
.mpropdef
.as(not null), mtype
)
116 for rss
in self.live_send_site
do
117 if not mtype
.is_subtype
(self.mainmodule
, null, rss
.receiver
) then continue
118 if mtype
.has_mproperty
(self.mainmodule
, rss
.mmethod
) then
119 self.add_monomorphic_send
(mtype
, rss
.mmethod
)
124 fun add_send
(mtype
: MClassType, mmethod
: MMethod)
126 var rss
= new RuntimeSendSite(mmethod
, mtype
)
127 if self.live_send_site
.has
(rss
) then return
129 self.live_send_site
.add
(rss
)
130 self.polymorphic_methods
.add
(mmethod
)
132 for mtype2
in self.live_types
do
133 if not mtype2
.is_subtype
(self.mainmodule
, null, mtype
) then continue
134 if mtype2
.has_mproperty
(self.mainmodule
, mmethod
) then
135 self.add_monomorphic_send
(mtype2
, mmethod
)
140 fun add_monomorphic_send
(mtype
: MClassType, mmethod
: MMethod)
142 assert self.live_types
.has
(mtype
)
143 var defs
= mmethod
.lookup_definitions
(self.mainmodule
, mtype
)
144 if defs
.is_empty
then return
145 assert defs
.length
== 1 else print
"conflict on {mtype} for {mmethod}: {defs.join(" ")}"
146 self.add_static_call
(mtype
, defs
.first
)
149 fun add_static_call
(mtype
: MClassType, mmethoddef
: MMethodDef)
151 assert self.live_types
.has
(mtype
)
152 var rm
= new RuntimeMethod(mmethoddef
, mtype
)
153 if self.runtime_methods
.has
(rm
) then return
154 self.runtime_methods
.add
(rm
)
156 self.live_methoddefs
.add
(mmethoddef
)
159 fun add_cast_type
(mtype
: MClassType)
161 if self.live_cast_types
.has
(mtype
) then return
163 assert not mtype
.need_anchor
164 self.live_cast_types
.add
(mtype
)
167 # Start the analysis.
171 var classes
= self.modelbuilder
.model
.get_mclasses_by_name
("Bool")
172 if classes
!= null then for c
in classes
do self.add_type
(c
.mclass_type
)
174 while not todo
.is_empty
do
176 if not self.modelbuilder
.mpropdef2npropdef
.has_key
(mr
.mmethoddef
) then
177 # It is an init for a class?
178 if mr
.mmethoddef
.mproperty
.name
== "init" then
179 var nclassdef
= self.modelbuilder
.mclassdef2nclassdef
[mr
.mmethoddef
.mclassdef
]
180 var super_inits
= nclassdef
.super_inits
181 if super_inits
!= null then
182 #assert args.length == 1
183 for su
in super_inits
do
184 self.add_monomorphic_send
(mr
.receiver
, su
)
193 var npropdef
= self.modelbuilder
.mpropdef2npropdef
[mr
.mmethoddef
]
194 if npropdef
isa AConcreteMethPropdef then
195 #npropdef.debug("Visit {mr.mmethoddef} for {mr.receiver}")
196 var nclassdef
= npropdef
.parent
.as(AClassdef)
197 var mmethoddef
= npropdef
.mpropdef
.as(not null)
198 var auto_super_inits
= npropdef
.auto_super_inits
199 if auto_super_inits
!= null then
200 for auto_super_init
in auto_super_inits
do
201 self.add_monomorphic_send
(mr
.receiver
, auto_super_init
)
204 var v
= new RuntimeTypeVisitor(self, nclassdef
, mmethoddef
, mr
.receiver
)
205 v
.enter_visit
(npropdef
.n_block
)
206 else if npropdef
isa ADeferredMethPropdef then
207 # nothing to do (maybe add a waring?)
208 else if npropdef
isa AAttrPropdef then
210 else if npropdef
isa AInternMethPropdef or npropdef
isa AExternMethPropdef then
211 # UGLY: We force the "instantation" of the concrete return type if any
212 var ret
= mr
.mmethoddef
.msignature
.return_mtype
213 if ret
!= null and ret
isa MClassType and ret
.mclass
.kind
!= abstract_kind
and ret
.mclass
.kind
!= interface_kind
then
214 ret
= ret
.anchor_to
(self.mainmodule
, mr
.receiver
)
217 else if npropdef
isa AExternInitPropdef then
218 self.add_type
(mr
.receiver
)
220 npropdef
.debug
("Not yet implemented")
228 var mmethoddef
: MMethodDef
229 var receiver
: MClassType
233 return "{self.mmethoddef}({receiver})"
238 return o
isa RuntimeMethod and o
.mmethoddef
== self.mmethoddef
and o
.receiver
== self.receiver
243 return self.mmethoddef
.hash
+ self.receiver
.hash
247 class RuntimeSendSite
249 var receiver
: MClassType
253 return o
isa RuntimeSendSite and o
.mmethod
== self.mmethod
and o
.receiver
== self.receiver
258 return self.mmethod
.hash
+ self.receiver
.hash
262 private class RuntimeTypeVisitor
265 var analysis
: RuntimeTypeAnalysis
267 var nclassdef
: AClassdef
269 var mpropdef
: MPropDef
271 var receiver
: MClassType
273 init(analysis
: RuntimeTypeAnalysis, nclassdef
: AClassdef, mpropdef
: MPropDef, receiver
: MClassType)
275 self.analysis
= analysis
276 self.nclassdef
= nclassdef
277 self.mpropdef
= mpropdef
278 self.receiver
= receiver
281 # Adapt and remove nullable
282 # return null if we got the null type
283 fun cleanup_type
(mtype
: MType): nullable MClassType
285 mtype
= mtype
.anchor_to
(self.analysis
.mainmodule
, self.receiver
)
286 if mtype
isa MNullType then return null
287 if mtype
isa MNullableType then mtype
= mtype
.mtype
288 assert mtype
isa MClassType
289 assert not mtype
.need_anchor
293 fun add_type
(mtype
: MType)
295 var runtimetype
= cleanup_type
(mtype
)
296 if runtimetype
== null then return # we do not care about null
298 self.analysis
.add_type
(runtimetype
)
299 #self.current_node.debug("add_type {runtimetype}")
302 fun add_send
(mtype
: MType, mproperty
: MMethod)
304 var runtimetype
= cleanup_type
(mtype
)
305 if runtimetype
== null then return # we do not care about null
307 analysis
.add_send
(runtimetype
, mproperty
)
308 #self.current_node.debug("add_send {mproperty}")
311 fun add_monomorphic_send
(mtype
: MType, mproperty
: MMethod)
313 var runtimetype
= cleanup_type
(mtype
)
314 if runtimetype
== null then return # we do not care about null
316 self.analysis
.add_monomorphic_send
(runtimetype
, mproperty
)
317 #self.current_node.debug("add_static call {runtimetype} {mproperty}")
320 fun add_cast_type
(mtype
: MType)
322 var runtimetype
= cleanup_type
(mtype
)
323 if runtimetype
== null then return # we do not care about null
325 self.analysis
.add_cast_type
(runtimetype
)
326 #self.current_node.debug("add_cast_type {runtimetype}")
329 redef fun visit
(node
)
331 if node
== null then return
332 node
.accept_runtime_type_vistor
(self)
336 # Force to get the primitive class named `name' or abort
337 fun get_class
(name
: String): MClass
339 var cla
= analysis
.mainmodule
.model
.get_mclasses_by_name
(name
)
341 if name
== "Bool" then
342 var c
= new MClass(analysis
.mainmodule
, name
, 0, enum_kind
, public_visibility
)
343 var cladef
= new MClassDef(analysis
.mainmodule
, c
.mclass_type
, new Location(null, 0,0,0,0), new Array[String])
344 self.add_type
(c
.mclass_type
)
347 self.current_node
.debug
("Fatal Error: no primitive class {name}")
350 assert cla
.length
== 1 else print cla
.join
(", ")
354 # Force to get the primitive property named `name' in the instance `recv' or abort
355 fun get_method
(recv
: MType, name
: String): MMethod
357 var runtimetype
= cleanup_type
(recv
)
358 if runtimetype
== null then abort
360 var props
= self.analysis
.mainmodule
.model
.get_mproperties_by_name
(name
)
361 if props
== null then
362 self.current_node
.debug
("Fatal Error: no primitive property {name} on {runtimetype}")
365 var res
: nullable MMethod = null
366 for mprop
in props
do
367 assert mprop
isa MMethod
368 if not runtimetype
.has_mproperty
(self.analysis
.mainmodule
, mprop
) then continue
369 if mprop
.is_init
and mprop
.intro_mclassdef
.mclass
!= runtimetype
.mclass
then continue
373 self.current_node
.debug
("Fatal Error: ambigous property name '{name}'; conflict between {mprop.full_name} and {res.full_name}")
378 self.current_node
.debug
("Fatal Error: no primitive property {name} on {runtimetype}")
388 private fun accept_runtime_type_vistor
(v
: RuntimeTypeVisitor)
394 redef fun accept_runtime_type_vistor
(v
)
396 v
.add_type
(self.mtype
.as(not null))
400 redef class AFloatExpr
401 redef fun accept_runtime_type_vistor
(v
)
403 v
.add_type
(self.mtype
.as(not null))
407 redef class ACharExpr
408 redef fun accept_runtime_type_vistor
(v
)
410 v
.add_type
(self.mtype
.as(not null))
414 redef class AArrayExpr
415 redef fun accept_runtime_type_vistor
(v
)
417 var mtype
= self.mtype
.as(not null)
419 var native
= v
.get_class
("NativeArray").get_mtype
([mtype
.as(MGenericType).arguments
.first
])
421 var prop
= v
.get_method
(mtype
, "with_native")
422 v
.add_monomorphic_send
(mtype
, prop
)
426 redef class AStringFormExpr
427 redef fun accept_runtime_type_vistor
(v
)
429 var mtype
= self.mtype
.as(not null)
431 var native
= v
.get_class
("NativeString").mclass_type
433 var prop
= v
.get_method
(mtype
, "from_cstring")
434 v
.add_monomorphic_send
(mtype
, prop
)
438 redef class ASuperstringExpr
439 redef fun accept_runtime_type_vistor
(v
)
441 var arraytype
= v
.get_class
("Array").get_mtype
([v
.get_class
("Object").mclass_type
])
442 v
.add_type
(arraytype
)
443 var prop
= v
.get_method
(arraytype
, "join")
444 v
.add_monomorphic_send
(arraytype
, prop
)
448 redef class ACrangeExpr
449 redef fun accept_runtime_type_vistor
(v
)
451 var mtype
= self.mtype
.as(not null)
453 var prop
= v
.get_method
(mtype
, "init")
454 v
.add_monomorphic_send
(mtype
, prop
)
458 redef class AOrangeExpr
459 redef fun accept_runtime_type_vistor
(v
)
461 var mtype
= self.mtype
.as(not null)
463 var prop
= v
.get_method
(mtype
, "without_last")
464 v
.add_monomorphic_send
(mtype
, prop
)
468 redef class ATrueExpr
469 redef fun accept_runtime_type_vistor
(v
)
471 v
.add_type
(self.mtype
.as(not null))
475 redef class AFalseExpr
476 redef fun accept_runtime_type_vistor
(v
)
478 v
.add_type
(self.mtype
.as(not null))
483 redef fun accept_runtime_type_vistor
(v
)
485 v
.add_cast_type
(self.cast_type
.as(not null))
489 redef class AAsCastExpr
490 redef fun accept_runtime_type_vistor
(v
)
492 v
.add_cast_type
(self.mtype
.as(not null))
498 redef class ASendExpr
499 redef fun accept_runtime_type_vistor
(v
)
501 var mproperty
= self.mproperty
.as(not null)
502 if n_expr
isa ASelfExpr then
503 v
.add_monomorphic_send
(v
.receiver
, mproperty
)
505 var recvtype
= self.n_expr
.mtype
.as(not null)
506 v
.add_send
(recvtype
, mproperty
)
511 redef class ASendReassignFormExpr
512 redef fun accept_runtime_type_vistor
(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_runtime_type_vistor
(v
)
531 v
.add_send
(self.read_type
.as(not null), self.reassign_property
.mproperty
)
535 redef class AAttrReassignExpr
536 redef fun accept_runtime_type_vistor
(v
)
538 v
.add_send
(self.read_type
.as(not null), self.reassign_property
.mproperty
)
542 redef class ASuperExpr
543 redef fun accept_runtime_type_vistor
(v
)
545 var mproperty
= self.mproperty
546 if mproperty
!= null then
547 v
.add_monomorphic_send
(v
.receiver
, mproperty
)
551 #FIXME: we do not want an ugly static call!
552 var mpropdef
= v
.mpropdef
553 var mpropdefs
= mpropdef
.mproperty
.lookup_super_definitions
(mpropdef
.mclassdef
.mmodule
, mpropdef
.mclassdef
.bound_mtype
)
554 if mpropdefs
.length
!= 1 then
555 debug
("MPRODFEFS for super {mpropdef} for {v.receiver}: {mpropdefs.join(", ")}")
557 var msuperpropdef
= mpropdefs
.first
558 assert msuperpropdef
isa MMethodDef
559 v
.analysis
.add_static_call
(v
.receiver
, msuperpropdef
)
564 redef fun accept_runtime_type_vistor
(v
)
566 var recvtype
= self.n_expr
.mtype
.as(not null)
567 var colltype
= v
.get_class
("Collection").mclassdefs
.first
.bound_mtype
568 v
.add_send
(recvtype
, v
.get_method
(colltype
, "iterator"))
569 var iteratortype
= v
.get_class
("Iterator").mclassdefs
.first
.bound_mtype
570 var objtype
= v
.get_class
("Object").mclass_type
571 v
.add_send
(objtype
, v
.get_method
(iteratortype
, "is_ok"))
572 v
.add_send
(objtype
, v
.get_method
(iteratortype
, "item"))
573 v
.add_send
(objtype
, v
.get_method
(iteratortype
, "next"))
578 redef fun accept_runtime_type_vistor
(v
)
580 var recvtype
= self.mtype
.as(not null)
582 v
.add_monomorphic_send
(recvtype
, mproperty
.as(not null))