src/analysis/cha_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 module implements Class Hierarchy Analysis (CHA)
  18 package cha_analysis
  19
  20 import reachable_method_analysis
  21 import icode
  22 import program
  23
  24 class ChaContext
  25 special ReachableMethodAnalysis
  26         readable var _reachable_iroutines: HashSet[IRoutine] = new HashSet[IRoutine]
  27
  28         redef fun is_iroutine_reachable(ir: nullable IRoutine): Bool do
  29                 return ir != null and reachable_iroutines.has(ir)
  30         end
  31
  32         redef fun is_method_reachable(method: MMMethod): Bool do
  33                 return is_iroutine_reachable(method.iroutine)
  34         end
  35 end
  36
  37 class ChaBuilder
  38         readable var _iroutine_to_search: List[IRoutine] = new List[IRoutine]
  39         readable var _context: ChaContext
  40         readable var _program: Program
  41
  42         init(p: Program) do
  43                 _program = p
  44                 _context = new ChaContext
  45         end
  46
  47         private fun add_search(method: nullable MMMethod, iroutine: nullable IRoutine, is_static: Bool, is_super: Bool) do
  48                 # Add the exact method
  49                 if iroutine != null and not context.is_iroutine_reachable(iroutine) then
  50                         context.reachable_iroutines.add(iroutine)
  51                         _iroutine_to_search.add(iroutine)
  52                 end
  53
  54                 if method != null then
  55                         # Add every redefinition
  56                         if not is_static then
  57                                 for other in method.prhe.smallers do
  58                                         if other isa MMMethod then
  59                                                 add_search(other, other.iroutine, true, false)
  60                                         end
  61                                 end
  62                         end
  63
  64                         # Add all parents since we don't know which one will get called !
  65                         if is_super then
  66                                 for greater in method.prhe.greaters do
  67                                         if greater isa MMMethod then
  68                                                 add_search(greater, greater.iroutine, true, false)
  69                                         end
  70                                 end
  71                         end
  72                 end
  73         end
  74
  75         # Build the context associated with this builder
  76         fun work do
  77                 var main_method = program.main_method
  78                 if main_method == null then return
  79
  80                 add_search (main_method, main_method.iroutine, true, false)
  81
  82                 while not iroutine_to_search.is_empty do
  83                         var v = new ChaVisitor(self)
  84                         var iroutine = iroutine_to_search.pop
  85                         v.visit_icode(iroutine.body)
  86                 end
  87         end
  88 end
  89
  90 class ChaVisitor
  91 special ICodeVisitor
  92         readable var _builder: ChaBuilder
  93
  94         redef fun visit_icode(ic)
  95         do
  96                 if ic isa IStaticCall then
  97                         # FIXME: take only the last property on the redef. hierarchie
  98                         builder.add_search(ic.property, ic.property.iroutine, true, false)
  99                 else if ic isa INew then
 100                         # FIXME: take only the last property on the redef. hierarchie
 101                         var t = ic.stype
 102                         var cls = t.for_module(builder.program.main_module).local_class
 103                         var m = cls[ic.property.global].as(MMMethod)
 104                         var r = cls.new_instance_iroutine[m]
 105                         builder.add_search(ic.property, r, false, false)
 106                 else if ic isa ISuper then
 107                         builder.add_search(ic.property, ic.property.iroutine, false, true)
 108                 else if ic isa ICall then
 109                         builder.add_search(ic.property, ic.property.iroutine, false, false)
 110                 else if ic isa ICheckInstance then
 111                         var t = ic.stype
 112                         var cls = t.for_module(builder.program.main_module).local_class
 113                         var ir = cls.checknew_iroutine
 114                         builder.add_search(null, ir, true, false)
 115                 else if ic isa IInitAttributes then
 116                         var t = ic.stype
 117                         var cls = t.for_module(builder.program.main_module).local_class
 118                         var ir = cls.init_var_iroutine
 119                         builder.add_search(null, ir, true, false)
 120                 end
 121                 super
 122         end
 123
 124         init(b: ChaBuilder)
 125         do
 126                 _builder = b
 127         end
 128 end