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