rta: rename and document runtime_type.nit
[nit.git] / src / rapid_type_analysis.nit
1 # This file is part of NIT ( http://www.nitlanguage.org ).
2 #
3 # Copyright 2012 Jean Privat <jean@pryen.org>
4 #
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
8 #
9 # http://www.apache.org/licenses/LICENSE-2.0
10 #
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.
16
17
18 # Rapid type analysis on the AST with heterogenous generics and customization
19 #
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 #
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)
31 #
32 # Customization means that each method definition is analyzed one per rapid
33 # type of receiver.
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
41
42 import model
43 import modelbuilder
44 import typing
45 import auto_super_init
46
47 redef class MModule
48 var main_type: nullable MClassType
49 var main_init: nullable MMethod
50 var main_method: nullable MMethod
51 end
52
53 redef class ModelBuilder
54 fun do_rapid_type_analysis(mainmodule: MModule): RapidTypeAnalysis
55 do
56 var model = self.model
57 var analysis = new RapidTypeAnalysis(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)
68 end
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)
74 end
75 mainmodule.main_method = mainprop
76 analysis.run_analysis
77 return analysis
78 end
79 end
80
81 # RapidTypeAnalysis looks for alive rapid types in application.
82 # The entry point of the analysis is the mainmodule of the application.
83 class RapidTypeAnalysis
84 # The modelbuilder used to get the AST.
85 var modelbuilder: ModelBuilder
86
87 # The main module of the analysis.
88 # Used to perform types operations.
89 var mainmodule: MModule
90
91 # The pool to live types.
92 # During the analysis, new types are added and combined with
93 # live_send_sites to determine new customized_methoddefs to visit
94 var live_types: HashSet[MClassType] = new HashSet[MClassType]
95
96 # The pool of types used to perform type checks (isa and as).
97 var live_cast_types: HashSet[MClassType] = new HashSet[MClassType]
98
99 # Live method definitions.
100 # These method definitions are:
101 # * visited trough a add_send on an already known live_type
102 # * visited trough a add_type for an already known live_send_sites
103 # * visided by a add_monomorphic_send or a add_static_call
104 var live_methoddefs: HashSet[MMethodDef] = new HashSet[MMethodDef]
105
106 # The pool of live customized method definitions
107 var live_customized_methoddefs: HashSet[CustomizedMethodDef] = new HashSet[CustomizedMethodDef]
108
109 # The pool of live RTA send site
110 # During the analysis, new live_send_sites are added and combined with
111 # live_types to determine new live_customized_methoddefs to visit
112 var live_send_sites: HashSet[RTASendSite] = new HashSet[RTASendSite]
113
114 # The customized method definitions that remain to visit
115 private var todo: List[CustomizedMethodDef] = new List[CustomizedMethodDef]
116
117 # Add a live type to the pool
118 #
119 # If the types is already live, then do nothing.
120 #
121 # REQUIRE: not mtype.need_anchor
122 fun add_type(mtype: MClassType)
123 do
124 if self.live_types.has(mtype) then return
125
126 assert not mtype.need_anchor
127 self.live_types.add(mtype)
128
129 # Collect default attributes
130 for cd in mtype.collect_mclassdefs(self.mainmodule)
131 do
132 var nclassdef = self.modelbuilder.mclassdef2nclassdef[cd]
133 for npropdef in nclassdef.n_propdefs do
134 if not npropdef isa AAttrPropdef then continue
135 var nexpr = npropdef.n_expr
136 if nexpr == null then continue
137 var v = new RapidTypeVisitor(self, nclassdef, npropdef.mpropdef.as(not null), mtype)
138 v.enter_visit(nexpr)
139 end
140 end
141
142 for rss in self.live_send_sites do
143 if not mtype.is_subtype(self.mainmodule, null, rss.receiver) then continue
144 if mtype.has_mproperty(self.mainmodule, rss.mmethod) then
145 self.add_monomorphic_send(mtype, rss.mmethod)
146 end
147 end
148 end
149
150 # Add a send site to the pool
151 #
152 # If the send site is already live, then do nothing.
153 fun add_send(mtype: MClassType, mmethod: MMethod)
154 do
155 var rss = new RTASendSite(mmethod, mtype)
156 if self.live_send_sites.has(rss) then return
157
158 self.live_send_sites.add(rss)
159
160 for mtype2 in self.live_types do
161 if not mtype2.is_subtype(self.mainmodule, null, mtype) then continue
162 if mtype2.has_mproperty(self.mainmodule, mmethod) then
163 self.add_monomorphic_send(mtype2, mmethod)
164 end
165 end
166 end
167
168 # Add a monomoprhic send.
169 # The send site is not added to the pool.
170 # The method just determine the associated method definition then
171 # performs a static_call
172 fun add_monomorphic_send(mtype: MClassType, mmethod: MMethod)
173 do
174 assert self.live_types.has(mtype)
175 var defs = mmethod.lookup_definitions(self.mainmodule, mtype)
176 if defs.is_empty then return
177 assert defs.length == 1 else print "conflict on {mtype} for {mmethod}: {defs.join(" ")}"
178 self.add_static_call(mtype, defs.first)
179 end
180
181 # Add a customized_methoddefs to the pool
182 # Is the customized_methoddefs is already live, then do nothing
183 fun add_static_call(mtype: MClassType, mmethoddef: MMethodDef)
184 do
185 assert self.live_types.has(mtype)
186 var rm = new CustomizedMethodDef(mmethoddef, mtype)
187 if self.live_customized_methoddefs.has(rm) then return
188 self.live_customized_methoddefs.add(rm)
189 self.todo.add(rm)
190 self.live_methoddefs.add(mmethoddef)
191 end
192
193 # Add mtype to the cast pool.
194 fun add_cast_type(mtype: MClassType)
195 do
196 if self.live_cast_types.has(mtype) then return
197
198 assert not mtype.need_anchor
199 self.live_cast_types.add(mtype)
200 end
201
202 # Run the analysis until all visitable method definitions are visited.
203 fun run_analysis
204 do
205 # Force Bool
206 var classes = self.modelbuilder.model.get_mclasses_by_name("Bool")
207 if classes != null then for c in classes do self.add_type(c.mclass_type)
208
209 while not todo.is_empty do
210 var mr = todo.shift
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)
220 end
221 end
222
223 else
224 abort
225 end
226 continue
227 end
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)
237 end
238 end
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
244 # nothing to do
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)
250 self.add_type(ret)
251 end
252 else if npropdef isa AExternInitPropdef then
253 self.add_type(mr.receiver)
254 else
255 npropdef.debug("Not yet implemented")
256 abort
257 end
258 end
259 end
260 end
261
262 # A method definitions customized to a specific receiver
263 class CustomizedMethodDef
264 var mmethoddef: MMethodDef
265 var receiver: MClassType
266
267 redef fun to_s
268 do
269 return "{self.mmethoddef}({receiver})"
270 end
271
272 redef fun ==(o)
273 do
274 return o isa CustomizedMethodDef and o.mmethoddef == self.mmethoddef and o.receiver == self.receiver
275 end
276
277 redef fun hash
278 do
279 return self.mmethoddef.hash + self.receiver.hash
280 end
281 end
282
283 # A method invokation site bounded by a specific receiver
284 class RTASendSite
285 var mmethod: MMethod
286 var receiver: MClassType
287
288 redef fun ==(o)
289 do
290 return o isa RTASendSite and o.mmethod == self.mmethod and o.receiver == self.receiver
291 end
292
293 redef fun hash
294 do
295 return self.mmethod.hash + self.receiver.hash
296 end
297 end
298
299 private class RapidTypeVisitor
300 super Visitor
301
302 var analysis: RapidTypeAnalysis
303
304 var nclassdef: AClassdef
305
306 var mpropdef: MPropDef
307
308 var receiver: MClassType
309
310 init(analysis: RapidTypeAnalysis, nclassdef: AClassdef, mpropdef: MPropDef, receiver: MClassType)
311 do
312 self.analysis = analysis
313 self.nclassdef = nclassdef
314 self.mpropdef = mpropdef
315 self.receiver = receiver
316 end
317
318 # Adapt and remove nullable
319 # return null if we got the null type
320 fun cleanup_type(mtype: MType): nullable MClassType
321 do
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
327 return mtype
328 end
329
330 fun add_type(mtype: MType)
331 do
332 var rapidtype = cleanup_type(mtype)
333 if rapidtype == null then return # we do not care about null
334
335 self.analysis.add_type(rapidtype)
336 #self.current_node.debug("add_type {rapidtype}")
337 end
338
339 fun add_send(mtype: MType, mproperty: MMethod)
340 do
341 var rapidtype = cleanup_type(mtype)
342 if rapidtype == null then return # we do not care about null
343
344 analysis.add_send(rapidtype, mproperty)
345 #self.current_node.debug("add_send {mproperty}")
346 end
347
348 fun add_monomorphic_send(mtype: MType, mproperty: MMethod)
349 do
350 var rapidtype = cleanup_type(mtype)
351 if rapidtype == null then return # we do not care about null
352
353 self.analysis.add_monomorphic_send(rapidtype, mproperty)
354 #self.current_node.debug("add_monomorphic_send {rapidtype} {mproperty}")
355 end
356
357 fun add_cast_type(mtype: MType)
358 do
359 var rapidtype = cleanup_type(mtype)
360 if rapidtype == null then return # we do not care about null
361
362 self.analysis.add_cast_type(rapidtype)
363 #self.current_node.debug("add_cast_type {rapidtype}")
364 end
365
366 redef fun visit(node)
367 do
368 if node == null then return
369 node.accept_rapid_type_vistor(self)
370 node.visit_all(self)
371 end
372
373 # Force to get the primitive class named `name' or abort
374 fun get_class(name: String): MClass
375 do
376 var cla = analysis.mainmodule.model.get_mclasses_by_name(name)
377 if cla == null then
378 if name == "Bool" then
379 var c = new MClass(analysis.mainmodule, name, 0, enum_kind, public_visibility)
380 var cladef = new MClassDef(analysis.mainmodule, c.mclass_type, new Location(null, 0,0,0,0), new Array[String])
381 self.add_type(c.mclass_type)
382 return c
383 end
384 self.current_node.debug("Fatal Error: no primitive class {name}")
385 abort
386 end
387 assert cla.length == 1 else print cla.join(", ")
388 return cla.first
389 end
390
391 # Force to get the primitive property named `name' in the instance `recv' or abort
392 fun get_method(recv: MType, name: String): MMethod
393 do
394 var rapidtype = cleanup_type(recv)
395 if rapidtype == null then abort
396
397 var props = self.analysis.mainmodule.model.get_mproperties_by_name(name)
398 if props == null then
399 self.current_node.debug("Fatal Error: no primitive property {name} on {rapidtype}")
400 abort
401 end
402 var res: nullable MMethod = null
403 for mprop in props do
404 assert mprop isa MMethod
405 if not rapidtype.has_mproperty(self.analysis.mainmodule, mprop) then continue
406 if mprop.is_init and mprop.intro_mclassdef.mclass != rapidtype.mclass then continue
407 if res == null then
408 res = mprop
409 else
410 self.current_node.debug("Fatal Error: ambigous property name '{name}'; conflict between {mprop.full_name} and {res.full_name}")
411 abort
412 end
413 end
414 if res == null then
415 self.current_node.debug("Fatal Error: no primitive property {name} on {rapidtype}")
416 abort
417 end
418 return res
419 end
420 end
421
422 ###
423
424 redef class ANode
425 private fun accept_rapid_type_vistor(v: RapidTypeVisitor)
426 do
427 end
428 end
429
430 redef class AIntExpr
431 redef fun accept_rapid_type_vistor(v)
432 do
433 v.add_type(self.mtype.as(not null))
434 end
435 end
436
437 redef class AFloatExpr
438 redef fun accept_rapid_type_vistor(v)
439 do
440 v.add_type(self.mtype.as(not null))
441 end
442 end
443
444 redef class ACharExpr
445 redef fun accept_rapid_type_vistor(v)
446 do
447 v.add_type(self.mtype.as(not null))
448 end
449 end
450
451 redef class AArrayExpr
452 redef fun accept_rapid_type_vistor(v)
453 do
454 var mtype = self.mtype.as(not null)
455 v.add_type(mtype)
456 var native = v.get_class("NativeArray").get_mtype([mtype.as(MGenericType).arguments.first])
457 v.add_type(native)
458 var prop = v.get_method(mtype, "with_native")
459 v.add_monomorphic_send(mtype, prop)
460 end
461 end
462
463 redef class AStringFormExpr
464 redef fun accept_rapid_type_vistor(v)
465 do
466 var mtype = self.mtype.as(not null)
467 v.add_type(mtype)
468 var native = v.get_class("NativeString").mclass_type
469 v.add_type(native)
470 var prop = v.get_method(mtype, "from_cstring")
471 v.add_monomorphic_send(mtype, prop)
472 end
473 end
474
475 redef class ASuperstringExpr
476 redef fun accept_rapid_type_vistor(v)
477 do
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 end
484 end
485
486 redef class ACrangeExpr
487 redef fun accept_rapid_type_vistor(v)
488 do
489 var mtype = self.mtype.as(not null)
490 v.add_type(mtype)
491 var prop = v.get_method(mtype, "init")
492 v.add_monomorphic_send(mtype, prop)
493 end
494 end
495
496 redef class AOrangeExpr
497 redef fun accept_rapid_type_vistor(v)
498 do
499 var mtype = self.mtype.as(not null)
500 v.add_type(mtype)
501 var prop = v.get_method(mtype, "without_last")
502 v.add_monomorphic_send(mtype, prop)
503 end
504 end
505
506 redef class ATrueExpr
507 redef fun accept_rapid_type_vistor(v)
508 do
509 v.add_type(self.mtype.as(not null))
510 end
511 end
512
513 redef class AFalseExpr
514 redef fun accept_rapid_type_vistor(v)
515 do
516 v.add_type(self.mtype.as(not null))
517 end
518 end
519
520 redef class AIsaExpr
521 redef fun accept_rapid_type_vistor(v)
522 do
523 v.add_cast_type(self.cast_type.as(not null))
524 end
525 end
526
527 redef class AAsCastExpr
528 redef fun accept_rapid_type_vistor(v)
529 do
530 v.add_cast_type(self.mtype.as(not null))
531 end
532 end
533
534 #
535
536 redef class ASendExpr
537 redef fun accept_rapid_type_vistor(v)
538 do
539 var mproperty = self.mproperty.as(not null)
540 if n_expr isa ASelfExpr then
541 v.add_monomorphic_send(v.receiver, mproperty)
542 else
543 var recvtype = self.n_expr.mtype.as(not null)
544 v.add_send(recvtype, mproperty)
545 end
546 end
547 end
548
549 redef class ASendReassignFormExpr
550 redef fun accept_rapid_type_vistor(v)
551 do
552 v.add_send(self.read_type.as(not null), self.reassign_property.mproperty)
553 var mproperty = self.mproperty.as(not null)
554 var write_mproperty = self.write_mproperty.as(not null)
555 if n_expr isa ASelfExpr then
556 v.add_monomorphic_send(v.receiver, mproperty)
557 v.add_monomorphic_send(v.receiver, write_mproperty)
558 else
559 var recvtype = self.n_expr.mtype.as(not null)
560 v.add_send(recvtype, mproperty)
561 v.add_send(recvtype, write_mproperty)
562 end
563 end
564 end
565
566 redef class AVarReassignExpr
567 redef fun accept_rapid_type_vistor(v)
568 do
569 v.add_send(self.read_type.as(not null), self.reassign_property.mproperty)
570 end
571 end
572
573 redef class AAttrReassignExpr
574 redef fun accept_rapid_type_vistor(v)
575 do
576 v.add_send(self.read_type.as(not null), self.reassign_property.mproperty)
577 end
578 end
579
580 redef class ASuperExpr
581 redef fun accept_rapid_type_vistor(v)
582 do
583 var mproperty = self.mproperty
584 if mproperty != null then
585 v.add_monomorphic_send(v.receiver, mproperty)
586 return
587 end
588
589 #FIXME: we do not want an ugly static call!
590 var mpropdef = v.mpropdef
591 var mpropdefs = mpropdef.mproperty.lookup_super_definitions(mpropdef.mclassdef.mmodule, mpropdef.mclassdef.bound_mtype)
592 if mpropdefs.length != 1 then
593 debug("MPRODFEFS for super {mpropdef} for {v.receiver}: {mpropdefs.join(", ")}")
594 end
595 var msuperpropdef = mpropdefs.first
596 assert msuperpropdef isa MMethodDef
597 v.analysis.add_static_call(v.receiver, msuperpropdef)
598 end
599 end
600
601 redef class AForExpr
602 redef fun accept_rapid_type_vistor(v)
603 do
604 var recvtype = self.n_expr.mtype.as(not null)
605 var colltype = v.get_class("Collection").mclassdefs.first.bound_mtype
606 v.add_send(recvtype, v.get_method(colltype, "iterator"))
607 var iteratortype = v.get_class("Iterator").mclassdefs.first.bound_mtype
608 var objtype = v.get_class("Object").mclass_type
609 v.add_send(objtype, v.get_method(iteratortype, "is_ok"))
610 v.add_send(objtype, v.get_method(iteratortype, "item"))
611 v.add_send(objtype, v.get_method(iteratortype, "next"))
612 end
613 end
614
615 redef class ANewExpr
616 redef fun accept_rapid_type_vistor(v)
617 do
618 var recvtype = self.mtype.as(not null)
619 v.add_type(recvtype)
620 v.add_monomorphic_send(recvtype, mproperty.as(not null))
621 end
622 end