1 # This file is part of NIT ( http://www.nitlanguage.org ).
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
7 # http://www.apache.org/licenses/LICENSE-2.0
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.
15 # Static Analysis Framework base
17 # A lot of TODOs still missing:
18 # * flow breaks (AReturnExpr, AEscapeExpr, AAbortExpr)
19 # * other conditionnals (AIfexprExpr, AAssertExpr, ABonBoolExpr)
20 # * flow through AAttrPropDef
25 # The base of all analysis performed statically.
26 abstract class StaticAnalysis
29 # Type of FlowSet representation used by the StaticAnalysis.
32 # "in" set for the currently visited node.
33 var current_inset
: FLOW is noinit
, writable
35 # 'out' set for the currently visited node.
36 var current_outset
: FLOW is noinit
, writable
38 # Sets at the entry of each node.
40 # Each node is associated with the `current_inset` it got.
41 var insets
= new HashMap[ANode, FLOW]
43 # Sets at the exit of each node.
45 # Each node is associated with the `current_outset` it got.
46 var outsets
= new HashMap[ANode, FLOW]
49 current_inset
= new_initial_flow
50 current_outset
= new_initial_flow
53 # Initial flow set to use.
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
59 # Initial flow set to use within methods.
61 # Returns `new_initial_flow` by default.
62 # Redefine this method to inject things in the inset like parameters from
64 fun new_initial_method_flow
(v
: AMethPropdef): FLOW do return new_initial_flow
66 # The merge operation on sets for confluence.
68 # Depends on the analysis performed.
69 fun merge
(s1
, s2
: FLOW): FLOW is abstract
71 # ModelBuilder used to lookup AST nodes.
72 var modelbuilder
: ModelBuilder
74 # Run `self` on an AST `node`.
75 fun start_analysis
(node
: ANode) do visit
(node
)
77 # Pretty print the outsets of this analysis.
79 # Mainly used for debug and testing.
80 fun pretty_print
is abstract
83 # An analysis go forward from the entry point to the exit point.
85 # With a forward analysis, output properties are determined by the inputs.
89 redef fun visit
(n
) do n
.accept_forward_analysis
(self)
92 # FlowSet are used to represent data at the entry and exit of a statement.
96 # Merge `self` with another flow set.
97 fun flow_union
(o
: SELF): SELF is abstract
100 # A FlowSet based on a HashMap.
101 class FlowHashMap[K
, V
]
105 # Init `self` with the content of `map`.
106 init from
(map
: Map[K
, V
]) do
108 for k
, v
in map
do self[k
] = v
112 redef fun clone
do return new FlowHashMap[K
, V
].from
(self)
115 # A FlowSet based on a HashSet.
120 redef fun clone
do return new FlowHashSet[E
].from
(self)
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
)
127 redef fun flow_union
(o
) do return new FlowHashSet[E
].from
(union
(o
))
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
138 v
.outsets
[self] = v
.current_outset
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
150 if n_then
!= null then v
.enter_visit
(n_then
)
151 var then_outset
= v
.current_outset
153 v
.current_inset
= inset
154 v
.current_outset
= outset
156 if n_else
!= null then
157 v
.enter_visit
(n_else
)
158 outset
= v
.merge
(then_outset
, v
.current_outset
)
160 outset
= v
.merge
(then_outset
, v
.current_inset
)
162 v
.current_inset
= inset
163 v
.current_outset
= outset
167 # Represent all kind of `do .. end` blocks.
169 # Used to factorize implementations across do blocks, whiles, fors and loops.
171 # This factorization makes sense since all these contructs can be flow managed
172 # through contine and breack statements.
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
182 v
.current_inset
= v
.merge
(inset
, v
.current_outset
)
183 v
.current_outset
= v
.current_inset
.clone
184 last
= v
.current_outset
.clone
186 v
.current_inset
= inset
187 v
.current_outset
= v
.merge
(inset
, v
.current_outset
)
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
)
196 # The block contained by this loop.
197 fun loop_block
: nullable ANode is abstract
203 redef fun loop_block
do return self.n_block
204 redef fun accept_forward_analysis
(v
) do accept_loop_forward_analysis
(v
)
207 redef class ALoopExpr
210 redef fun loop_block
do return self.n_block
211 redef fun accept_forward_analysis
(v
) do accept_loop_forward_analysis
(v
)
214 redef class AWhileExpr
217 redef fun loop_block
do return self.n_block
219 redef fun accept_forward_analysis
(v
) do
220 v
.enter_visit
(n_expr
)
221 accept_loop_forward_analysis
(v
)
228 redef fun loop_block
do return self.n_block
230 redef fun accept_forward_analysis
(v
) do
231 for n_group
in n_groups
do
232 v
.enter_visit
(n_group
.n_expr
)
234 accept_loop_forward_analysis
(v
)
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
244 v
.outsets
[self] = v
.current_outset