src/analysis/rta_analysis.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # Copyright 2009 Jean-Sebastien Gelinas <calestar@gmail.com>
   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 # This package implements Reachable Type Analysis(RTA)
  18 package rta_analysis
  19
  20 import instantiated_type_analysis
  21 import reachable_method_analysis
  22 import icode
  23 import program
  24
  25 class RtaContext
  26 special ReachableMethodAnalysis
  27 special InstantiatedTypeAnalysis
  28         init do end
  29         readable var _instanciated_classes: HashSet[MMLocalClass] = new HashSet[MMLocalClass]
  30
  31         redef fun is_class_instantiated(local_class: MMLocalClass): Bool do return instanciated_classes.has(local_class)
  32
  33         readable var _reachable_iroutines: HashSet[IRoutine] = new HashSet[IRoutine]
  34
  35         redef fun is_iroutine_reachable(ir: nullable IRoutine): Bool do
  36                 return ir != null and reachable_iroutines.has(ir)
  37         end
  38
  39         redef fun is_method_reachable(method: MMMethod): Bool do
  40                 return is_iroutine_reachable(method.iroutine)
  41         end
  42 end
  43
  44 class RtaBuilder
  45         readable var _context : RtaContext
  46         readable var _program: Program
  47         readable var _iroutine_to_search: List[IRoutine] = new List[IRoutine]
  48         readable var _call_sites: HashSet[IAbsCall] = new HashSet[IAbsCall]
  49         readable var _called_methods: HashSet[MMMethod] = new HashSet[MMMethod]
  50
  51         init (p: Program) do
  52                 _context = new RtaContext()
  53                 _program = p
  54         end
  55
  56         # Check if the class where the method was introduced is instantiated
  57         # Also check every subclasses if they use the same 'version' of the
  58         # method
  59         fun check_method(m: MMMethod): Bool do
  60                 var m_cls = m.local_class.for_module(program.module)
  61
  62                 if context.is_class_instantiated(m_cls) then return true
  63
  64                 for cls in m_cls.cshe.smallers do
  65                         if context.is_class_instantiated(cls) then return true
  66                 end
  67                 return false
  68         end
  69
  70         # Check all call sites to find those that just became 'activated'
  71         # by some new type instantiation
  72         fun check_call_sites do
  73                 var calls_to_remove = new List[IAbsCall]
  74                 for call in call_sites do
  75                         var m = call.property
  76                         var all_added = true
  77
  78                         # Check for this method
  79                         if check_method(m) then
  80                                 add_reachable_iroutine(m.iroutine)
  81                         else
  82                                 all_added = false
  83                         end
  84
  85                         # Check all methods 'under' this one in the hierarchy
  86                         for other in m.prhe.smallers do
  87                                 if not other isa MMMethod then continue
  88                                 if check_method(other) then
  89                                         add_reachable_iroutine(other.iroutine)
  90                                 else
  91                                         all_added = false
  92                                 end
  93                         end
  94
  95                         if all_added then calls_to_remove.add(call)
  96                 end
  97
  98                 # If all sub-methods are added, no need to keep checking this call !
  99                 for call in calls_to_remove do
 100                         call_sites.remove(call)
 101                 end
 102         end
 103
 104         fun add_instantiated_class(cls: MMLocalClass) do
 105                 if context.is_class_instantiated(cls) then return
 106                 context.instanciated_classes.add(cls)
 107
 108                 check_call_sites
 109         end
 110
 111         fun add_reachable_call(call: IAbsCall) do
 112                 var m = call.property
 113                 if called_methods.has(m) then return
 114                 if call_sites.has(call) then return
 115
 116                 if m.global.is_init then
 117                         called_methods.add(m)
 118                         add_reachable_iroutine(m.iroutine)
 119
 120                         # No need to add the call site or to process other
 121                         # call sites when it is an initializer: we know
 122                         # exactly which one will get called
 123                 else
 124                         call_sites.add(call)
 125                         called_methods.add(m)
 126                         check_call_sites
 127                 end
 128         end
 129
 130         fun add_reachable_iroutine(ir: nullable IRoutine) do
 131                 if ir == null or context.is_iroutine_reachable(ir) then return
 132                 context.reachable_iroutines.add(ir)
 133                 iroutine_to_search.add(ir)
 134         end
 135
 136         # Need to hard-code some automaticaly instanciated types !
 137         private fun force_some_type_analysis do
 138                 var forced_types = ["Object", "Bool", "Float", "Int", "String", "NativeString", "Range", "Array", "ArrayIterator"]
 139
 140                 for some_type in forced_types do
 141                         if not program.module.has_global_class_named(some_type.to_symbol) then continue
 142                         var cls_type = program.module.class_by_name(some_type.to_symbol)
 143                         add_instantiated_class(cls_type)
 144                 end
 145
 146                 if program.module.has_global_class_named("Pointer".to_symbol) then
 147                         var ptr_class = program.module.class_by_name("Pointer".to_symbol)
 148                         # Assume that all classes that are subclasses of Pointer
 149                         # can be returned by the native interface
 150                         # and are always counted as instantiated
 151                         for ptr_sub_class in ptr_class.cshe.smallers do
 152                                 add_instantiated_class(ptr_sub_class)
 153                         end
 154                 end
 155
 156                 for cls in program.module.global_classes do
 157                         if not cls.is_universal then continue
 158                         add_instantiated_class(program.module[cls])
 159                 end
 160         end
 161
 162         # Build the context associated with this builder
 163         fun work do
 164                 if program.main_method == null then
 165                         # Add primitive type (so that compiling works)
 166                         for t in ["Int","Char","Bool"] do
 167                                 if program.module.has_global_class_named(t.to_symbol) then
 168                                         add_instantiated_class(program.module.class_by_name(t.to_symbol))
 169                                 end
 170                         end
 171                         return
 172                 end
 173
 174                 add_instantiated_class(program.main_class.as(not null))
 175                 add_reachable_iroutine(program.main_method.as(not null).iroutine)
 176                 force_some_type_analysis
 177
 178                 while not iroutine_to_search.is_empty do
 179                         var v = new RtaVisitor(self)
 180                         var iroutine = iroutine_to_search.pop
 181                         v.visit_icode(iroutine.body)
 182                 end
 183         end
 184 end
 185
 186 class RtaVisitor
 187 special ICodeVisitor
 188         readable var _builder: RtaBuilder
 189
 190         redef fun visit_icode(ic)
 191         do
 192                 if ic isa IStaticCall then
 193                         # FIXME: take only the last property on the redef. hierarchie
 194                         builder.add_reachable_iroutine(ic.property.iroutine)
 195                 else if ic isa INew then
 196                         # FIXME: take only the last property on the redef. hierarchie
 197                         var t = ic.stype
 198                         var cls = t.for_module(builder.program.module).local_class
 199                         var m = cls[ic.property.global].as(MMMethod)
 200                         var r = cls.new_instance_iroutine[m]
 201                         builder.add_instantiated_class(cls)
 202                         builder.add_reachable_iroutine(r)
 203                 else if ic isa ISuper then
 204                         # Add every parents ...
 205                         for p in ic.property.prhe.greaters_and_self do
 206                                 if p isa MMMethod then
 207                                         builder.add_reachable_iroutine(p.iroutine)
 208                                 end
 209                         end
 210                 else if ic isa ICall then
 211                         builder.add_reachable_call(ic)
 212                 else if ic isa ICheckInstance then
 213                         var t = ic.stype
 214                         var cls = t.for_module(builder.program.module).local_class
 215                         var ir = cls.checknew_iroutine
 216                         builder.add_reachable_iroutine(ir)
 217                 else if ic isa IInitAttributes then
 218                         var t = ic.stype
 219                         var cls = t.for_module(builder.program.module).local_class
 220                         var ir = cls.init_var_iroutine
 221                         builder.add_reachable_iroutine(ir)
 222                 end
 223                 super
 224         end
 225
 226         init(b: RtaBuilder)
 227         do
 228                 _builder = b
 229         end
 230 end