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         # The merge operation on sets for confluence.
  60         #
  61         # Depends on the analysis performed.
  62         fun merge(s1, s2: FLOW): FLOW is abstract
  63
  64         # ModelBuilder used to lookup AST nodes.
  65         var modelbuilder: ModelBuilder
  66
  67         # Run `self` on an AST `node`.
  68         fun start_analysis(node: ANode) do visit(node)
  69
  70         # Pretty print the outsets of this analysis.
  71         #
  72         # Mainly used for debug and testing.
  73         fun pretty_print is abstract
  74 end
  75
  76 # An analysis go forward from the entry point to the exit point.
  77 #
  78 # With a forward analysis, output properties are determined by the inputs.
  79 class ForwardAnalysis
  80         super StaticAnalysis
  81
  82         redef fun visit(n) do n.accept_forward_analysis(self)
  83 end
  84
  85 # FlowSet are used to represent data at the entry and exit of a statement.
  86 interface FlowSet
  87         super Cloneable
  88
  89         # Merge `self` with another flow set.
  90         fun flow_union(o: SELF): SELF is abstract
  91 end
  92
  93 # A FlowSet based on a HashMap.
  94 class FlowHashMap[K, V]
  95         super FlowSet
  96         super HashMap[K, V]
  97
  98         # Init `self` with the content of `map`.
  99         init from(map: Map[K, V]) do
 100                 init
 101                 for k, v in map do self[k] = v
 102         end
 103
 104         # Not a deep copy.
 105         redef fun clone do return new FlowHashMap[K, V].from(self)
 106 end
 107
 108 # A FlowSet based on a HashSet.
 109 class FlowHashSet[E]
 110         super FlowSet
 111         super HashSet[E]
 112
 113         redef fun clone do return new FlowHashSet[E].from(self)
 114
 115         # Remove all items found in `other` from `self`.
 116         fun remove_from(other: Collection[E]) do
 117                 for e in other do remove(e)
 118         end
 119
 120         redef fun flow_union(o) do return new FlowHashSet[E].from(union(o))
 121 end
 122
 123 redef class ANode
 124
 125         # Apply the forward analysis `v` to `self`.
 126         fun accept_forward_analysis(v: ForwardAnalysis) do
 127                 v.current_inset = v.current_outset.clone
 128                 v.current_outset = v.current_inset.clone
 129                 v.insets[self] = v.current_inset
 130                 visit_all(v)
 131                 v.outsets[self] = v.current_outset
 132         end
 133 end
 134
 135 redef class AIfExpr
 136
 137         # Merge flow on if .. else constructs.
 138         redef fun accept_forward_analysis(v) do
 139                 v.enter_visit(n_expr)
 140                 var inset = v.current_inset
 141                 var outset = v.current_outset
 142
 143                 if n_then != null then v.enter_visit(n_then)
 144                 var then_outset = v.current_outset
 145
 146                 v.current_inset = inset
 147                 v.current_outset = outset
 148
 149                 if n_else != null then
 150                         v.enter_visit(n_else)
 151                         outset = v.merge(then_outset, v.current_outset)
 152                 else
 153                         outset = v.merge(then_outset, v.current_inset)
 154                 end
 155                 v.current_inset = inset
 156                 v.current_outset = outset
 157         end
 158 end
 159
 160 # Represent all kind of `do .. end` blocks.
 161 #
 162 # Used to factorize implementations across do blocks, whiles, fors and loops.
 163 #
 164 # This factorization makes sense since all these contructs can be flow managed
 165 # through contine and breack statements.
 166 #
 167 # TODO move this up in the module hierarchy
 168 interface ADoBlockHelper
 169         # Lookup fix point for this loop.
 170         fun loop_fix_point(v: StaticAnalysis, node: ANode) do
 171                 var inset = v.current_inset.clone
 172                 var last: nullable FlowSet = null
 173                 while v.current_outset != last do
 174                         v.enter_visit(node)
 175                         v.current_inset = v.merge(inset, v.current_outset)
 176                         v.current_outset = v.current_inset.clone
 177                         last = v.current_outset.clone
 178                 end
 179                 v.current_inset = inset
 180                 v.current_outset = v.merge(inset, v.current_outset)
 181         end
 182
 183         # Factorize loop forward analysis.
 184         fun accept_loop_forward_analysis(v: StaticAnalysis) do
 185                 var n_block = loop_block
 186                 if not n_block == null then loop_fix_point(v, n_block)
 187         end
 188
 189         # The block contained by this loop.
 190         fun loop_block: nullable ANode is abstract
 191 end
 192
 193 redef class ADoExpr
 194         super ADoBlockHelper
 195
 196         redef fun loop_block do return self.n_block
 197         redef fun accept_forward_analysis(v) do accept_loop_forward_analysis(v)
 198 end
 199
 200 redef class ALoopExpr
 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 AWhileExpr
 208         super ADoBlockHelper
 209
 210         redef fun loop_block do return self.n_block
 211
 212         redef fun accept_forward_analysis(v) do
 213                 v.enter_visit(n_expr)
 214                 accept_loop_forward_analysis(v)
 215         end
 216 end
 217
 218 redef class AForExpr
 219         super ADoBlockHelper
 220
 221         redef fun loop_block do return self.n_block
 222
 223         redef fun accept_forward_analysis(v) do
 224                 for n_group in n_groups do
 225                         v.enter_visit(n_group.n_expr)
 226                 end
 227                 accept_loop_forward_analysis(v)
 228         end
 229 end