src/saf/saf_base.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 # Static Analysis Framework base
  16 #
  17 # A lot of TODOs still missing:
  18 # * flow breaks (AReturnExpr, AEscapeExpr, AAbortExpr)
  19 # * other conditionnals (AIfexprExpr, AAssertExpr, ABonBoolExpr)
  20 # * flow through AAttrPropDef
  21 module saf_base
  22
  23 import modelbuilder
  24
  25 # The base of all analysis performed statically.
  26 abstract class StaticAnalysis
  27         super Visitor
  28
  29         # Type of FlowSet representation used by the StaticAnalysis.
  30         type FLOW: FlowSet
  31
  32         # "in" set for the currently visited node.
  33         var current_inset: FLOW is noinit, writable
  34
  35         # 'out' set for the currently visited node.
  36         var current_outset: FLOW is noinit, writable
  37
  38         # Sets at the entry of each node.
  39         #
  40         # Each node is associated with the `current_inset` it got.
  41         var insets = new HashMap[ANode, FLOW]
  42
  43         # Sets at the exit of each node.
  44         #
  45         # Each node is associated with the `current_outset` it got.
  46         var outsets = new HashMap[ANode, FLOW]
  47
  48         init do
  49                 current_inset = new_initial_flow
  50                 current_outset = new_initial_flow
  51         end
  52
  53         # Initial flow set to use.
  54         #
  55         # Because the initial flow set depends on the analysis performed, the
  56         # implementation of this method is the responsability the subclass.
  57         fun new_initial_flow: FLOW is abstract
  58
  59         # Initial flow set to use within methods.
  60         #
  61         # Returns `new_initial_flow` by default.
  62         # Redefine this method to inject things in the inset like parameters from
  63         # the signature.
  64         fun new_initial_method_flow(v: AMethPropdef): FLOW do return new_initial_flow
  65
  66         # The merge operation on sets for confluence.
  67         #
  68         # Depends on the analysis performed.
  69         fun merge(s1, s2: FLOW): FLOW is abstract
  70
  71         # ModelBuilder used to lookup AST nodes.
  72         var modelbuilder: ModelBuilder
  73
  74         # Run `self` on an AST `node`.
  75         fun start_analysis(node: ANode) do visit(node)
  76
  77         # Pretty print the outsets of this analysis.
  78         #
  79         # Mainly used for debug and testing.
  80         fun pretty_print is abstract
  81 end
  82
  83 # An analysis go forward from the entry point to the exit point.
  84 #
  85 # With a forward analysis, output properties are determined by the inputs.
  86 class ForwardAnalysis
  87         super StaticAnalysis
  88
  89         redef fun visit(n) do n.accept_forward_analysis(self)
  90 end
  91
  92 # FlowSet are used to represent data at the entry and exit of a statement.
  93 interface FlowSet
  94         super Cloneable
  95
  96         # Merge `self` with another flow set.
  97         fun flow_union(o: SELF): SELF is abstract
  98 end
  99
 100 # A FlowSet based on a HashMap.
 101 class FlowHashMap[K, V]
 102         super FlowSet
 103         super HashMap[K, V]
 104
 105         # Init `self` with the content of `map`.
 106         init from(map: Map[K, V]) do
 107                 init
 108                 for k, v in map do self[k] = v
 109         end
 110
 111         # Not a deep copy.
 112         redef fun clone do return new FlowHashMap[K, V].from(self)
 113 end
 114
 115 # A FlowSet based on a HashSet.
 116 class FlowHashSet[E]
 117         super FlowSet
 118         super HashSet[E]
 119
 120         redef fun clone do return new FlowHashSet[E].from(self)
 121
 122         # Remove all items found in `other` from `self`.
 123         fun remove_from(other: Collection[E]) do
 124                 for e in other do remove(e)
 125         end
 126
 127         redef fun flow_union(o) do return new FlowHashSet[E].from(union(o))
 128 end
 129
 130 redef class ANode
 131
 132         # Apply the forward analysis `v` to `self`.
 133         fun accept_forward_analysis(v: ForwardAnalysis) do
 134                 v.current_inset = v.current_outset.clone
 135                 v.current_outset = v.current_inset.clone
 136                 v.insets[self] = v.current_inset
 137                 visit_all(v)
 138                 v.outsets[self] = v.current_outset
 139         end
 140 end
 141
 142 redef class AIfExpr
 143
 144         # Merge flow on if .. else constructs.
 145         redef fun accept_forward_analysis(v) do
 146                 v.enter_visit(n_expr)
 147                 var inset = v.current_inset
 148                 var outset = v.current_outset
 149
 150                 if n_then != null then v.enter_visit(n_then)
 151                 var then_outset = v.current_outset
 152
 153                 v.current_inset = inset
 154                 v.current_outset = outset
 155
 156                 if n_else != null then
 157                         v.enter_visit(n_else)
 158                         outset = v.merge(then_outset, v.current_outset)
 159                 else
 160                         outset = v.merge(then_outset, v.current_inset)
 161                 end
 162                 v.current_inset = inset
 163                 v.current_outset = outset
 164         end
 165 end
 166
 167 # Represent all kind of `do .. end` blocks.
 168 #
 169 # Used to factorize implementations across do blocks, whiles, fors and loops.
 170 #
 171 # This factorization makes sense since all these contructs can be flow managed
 172 # through contine and breack statements.
 173 #
 174 # TODO move this up in the module hierarchy
 175 interface ADoBlockHelper
 176         # Lookup fix point for this loop.
 177         fun loop_fix_point(v: StaticAnalysis, node: ANode) do
 178                 var inset = v.current_inset.clone
 179                 var last: nullable FlowSet = null
 180                 while v.current_outset != last do
 181                         v.enter_visit(node)
 182                         v.current_inset = v.merge(inset, v.current_outset)
 183                         v.current_outset = v.current_inset.clone
 184                         last = v.current_outset.clone
 185                 end
 186                 v.current_inset = inset
 187                 v.current_outset = v.merge(inset, v.current_outset)
 188         end
 189
 190         # Factorize loop forward analysis.
 191         fun accept_loop_forward_analysis(v: StaticAnalysis) do
 192                 var n_block = loop_block
 193                 if not n_block == null then loop_fix_point(v, n_block)
 194         end
 195
 196         # The block contained by this loop.
 197         fun loop_block: nullable ANode is abstract
 198 end
 199
 200 redef class ADoExpr
 201         super ADoBlockHelper
 202
 203         redef fun loop_block do return self.n_block
 204         redef fun accept_forward_analysis(v) do accept_loop_forward_analysis(v)
 205 end
 206
 207 redef class ALoopExpr
 208         super ADoBlockHelper
 209
 210         redef fun loop_block do return self.n_block
 211         redef fun accept_forward_analysis(v) do accept_loop_forward_analysis(v)
 212 end
 213
 214 redef class AWhileExpr
 215         super ADoBlockHelper
 216
 217         redef fun loop_block do return self.n_block
 218
 219         redef fun accept_forward_analysis(v) do
 220                 v.enter_visit(n_expr)
 221                 accept_loop_forward_analysis(v)
 222         end
 223 end
 224
 225 redef class AForExpr
 226         super ADoBlockHelper
 227
 228         redef fun loop_block do return self.n_block
 229
 230         redef fun accept_forward_analysis(v) do
 231                 for n_group in n_groups do
 232                         v.enter_visit(n_group.n_expr)
 233                 end
 234                 accept_loop_forward_analysis(v)
 235         end
 236 end
 237
 238 redef class AMethPropdef
 239         redef fun accept_forward_analysis(v) do
 240                 v.current_inset = v.new_initial_method_flow(self)
 241                 v.current_outset = v.current_inset.clone
 242                 v.insets[self] = v.current_inset
 243                 visit_all(v)
 244                 v.outsets[self] = v.current_outset
 245         end
 246 end