src/saf/reaching_defs.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # Licensed under the Apache License, Version 2.0 (the "License");
   4 # you may not use this file except in compliance with the License.
   5 # You may obtain a copy of the License at
   6 #
   7 #     http://www.apache.org/licenses/LICENSE-2.0
   8 #
   9 # Unless required by applicable law or agreed to in writing, software
  10 # distributed under the License is distributed on an "AS IS" BASIS,
  11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12 # See the License for the specific language governing permissions and
  13 # limitations under the License.
  14
  15 # Analysis that determines which definitions may reach a given point in the code.
  16 import saf_base
  17
  18 import scope
  19
  20 # Determines wich variables definitions reach each statement.
  21 class ReachingDefsAnalysis
  22         super ForwardAnalysis
  23
  24         redef type FLOW: FlowHashSet[VarDef]
  25
  26         # New initial flows are empty (conservative analysis).
  27         redef fun new_initial_flow do return new FlowHashSet[VarDef]
  28
  29         # New initial flows for methods contains the parameters.
  30         redef fun new_initial_method_flow(n) do
  31                 var flow = new_initial_flow
  32                 var n_signature = n.n_signature
  33                 if n_signature == null then return flow
  34                 for n_param in n_signature.n_params do
  35                         var variable = n_param.variable
  36                         if variable == null then continue
  37                         flow.add(new VarDef(variable, n_param.location))
  38                 end
  39                 return flow
  40         end
  41
  42         # Perform set union (used for **some path** analysis).
  43         redef fun merge(s1, s2) do return s1.flow_union(s2)
  44
  45         redef fun visit(n) do n.accept_reaching_defs(self)
  46
  47         # Generate a new variable definition in the `current_outset`.
  48         fun gen(variable: Variable, location: Location) do
  49                 current_outset.add(new VarDef(variable, location))
  50         end
  51
  52         # Kill a variable definition in the `current_outset`.
  53         fun kill(variable: Variable) do
  54                 for vardef in current_outset.to_a do
  55                         if vardef.variable == variable then current_outset.remove(vardef)
  56                 end
  57         end
  58
  59         redef fun pretty_print do
  60                 for node, outset in outsets do
  61                         if outset.is_empty then continue
  62                         var values = outset.to_a
  63                         default_comparator.sort(values)
  64                         print "{node.location.line_end}: {values.join(", ")} out of {node.class_name}"
  65                 end
  66         end
  67 end
  68
  69 redef class ANode
  70
  71         # Apply a ReachingDefsAnalysis to `self`.
  72         fun accept_reaching_defs(v: ReachingDefsAnalysis) do accept_forward_analysis(v)
  73 end
  74
  75 redef class AVardeclExpr
  76         redef fun accept_reaching_defs(v) do
  77                 super
  78                 v.kill(variable.as(not null))
  79                 v.gen(variable.as(not null), location)
  80         end
  81 end
  82
  83 redef class AVarAssignExpr
  84         redef fun accept_reaching_defs(v) do
  85                 super
  86                 v.kill(variable.as(not null))
  87                 v.gen(variable.as(not null), location)
  88         end
  89 end
  90
  91 redef class AVarReassignExpr
  92         redef fun accept_reaching_defs(v) do
  93                 super
  94                 v.kill(variable.as(not null))
  95                 v.gen(variable.as(not null), location)
  96         end
  97 end
  98
  99 redef class AForExpr
 100         redef fun accept_reaching_defs(v) do
 101                 # add variables from `for` declaration
 102                 for n_group in n_groups do
 103                         var variables = n_group.variables
 104                         if variables == null then continue
 105                         for variable in variables do v.gen(variable, n_group.location)
 106                 end
 107                 super
 108                 # remove variables from `for` declaration
 109                 for n_group in n_groups do
 110                         var variables = n_group.variables
 111                         if variables == null then continue
 112                         for variable in variables do v.kill(variable)
 113                 end
 114         end
 115 end
 116
 117 # A Variable definition.
 118 #
 119 # Associates a variable to the location of its definition.
 120 class VarDef
 121         super Comparable
 122
 123         redef type OTHER: VarDef
 124
 125         # Variable this definition is about.
 126         var variable: Variable
 127
 128         # Location of this definition in the source code.
 129         var location: Location
 130
 131         redef fun ==(o) do
 132                 return o isa OTHER and variable == o.variable and location == o.location
 133         end
 134
 135         redef fun <=>(o) do
 136                 if variable.name == o.variable.name then
 137                         return location.line_start <=> o.location.line_start
 138                 else
 139                         return variable.name <=> o.variable.name
 140                 end
 141         end
 142
 143         redef fun hash do return variable.hash + location.hash
 144         redef fun to_s do return "\{{variable}: {location.line_start}\}"
 145 end