1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # Copyright 2012 Jean Privat <jean@pryen.org>
5 # Licensed under the Apache License, Version 2.0 (the "License");
6 # you may not use this file except in compliance with the License.
7 # You may obtain a copy of the License at
9 # http://www.apache.org/licenses/LICENSE-2.0
11 # Unless required by applicable law or agreed to in writing, software
12 # distributed under the License is distributed on an "AS IS" BASIS,
13 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 # See the License for the specific language governing permissions and
15 # limitations under the License.
17 # Intraprocedural static flow.
24 # The visitor that derermine flowcontext for nodes
25 private class FlowVisitor
28 var current_flow_context
: FlowContext
30 var toolcontext
: ToolContext
32 init(toolcontext
: ToolContext)
34 self.toolcontext
= toolcontext
35 current_flow_context
= new FlowContext
36 flows
.add
(current_flow_context
)
37 current_flow_context
.is_start
= true
40 var first
: nullable ANode
45 if first
== null then first
= node
47 if current_flow_context
.node
== null then current_flow_context
.node
= node
48 node
.accept_flow_visitor
(self)
49 if node
isa AExpr then
50 var flow
= self.current_flow_context
51 node
.after_flow_context
= flow
52 if flow
.when_true
!= flow
or flow
.when_false
!= flow
then
63 fun visit_expr
(node
: AExpr): FlowContext
66 return node
.after_flow_context
.as(not null)
69 var flows
: Array[FlowContext] = new Array[FlowContext]
73 var file
= new OFStream.open
("flow.dot")
74 file
.write
("digraph \{\n")
77 if f
.node
isa AExpr then
78 s
= "\\nmain={f.node.as(AExpr).after_flow_context.object_id}"
80 file
.write
"F{f.object_id} [label=\"{f.object_id}\\n
{f.node.location}\\n
{f.node.class_name}\\n
{f.name}{s}\
"];\n"
81 for p
in f
.previous
do
82 file
.write
"F{p.object_id} -> F{f.object_id};\n"
84 if f
.when_true
!= f
then
85 file
.write
"F{f.object_id} -> F{f.when_true.object_id}[label=TRUE, style=dotted];\n"
87 if f
.when_false
!= f
then
88 file
.write
"F{f.object_id} -> F{f.when_false.object_id}[label=FALSE,style=dotted];\n"
96 fun make_sub_flow
: FlowContext
98 var flow
= new FlowContext
100 flow
.node
= current_node
101 flow
.add_previous
(self.current_flow_context
)
102 self.current_flow_context
= flow
106 fun make_merge_flow
(flow1
, flow2
: FlowContext): FlowContext
108 var flow
= new FlowContext
110 flow
.node
= current_node
111 flow
.add_previous
(flow1
)
112 flow
.add_previous
(flow2
)
113 self.current_flow_context
= flow
117 fun make_true_false_flow
(true_flow
, false_flow
: FlowContext): FlowContext
119 var flow
= new FlowContext
121 flow
.node
= current_node
122 flow
.add_previous
(true_flow
)
123 flow
.add_previous
(false_flow
)
124 flow
.when_true
= true_flow
125 flow
.when_false
= false_flow
126 self.current_flow_context
= flow
130 fun make_sub_true_false_flow
: FlowContext
132 var orig_flow
= self.current_flow_context
133 var true_flow
= new FlowContext
135 true_flow
.node
= current_node
136 true_flow
.add_previous
(orig_flow
)
137 true_flow
.name
= "TRUE"
138 var false_flow
= new FlowContext
139 flows
.add
(false_flow
)
140 false_flow
.node
= current_node
141 false_flow
.add_previous
(orig_flow
)
142 false_flow
.name
= "FALSE"
143 return make_true_false_flow
(true_flow
, false_flow
)
146 fun make_unreachable_flow
: FlowContext
148 var flow
= new FlowContext
150 flow
.node
= current_node
151 flow
.add_previous
(self.current_flow_context
)
152 flow
.is_marked_unreachable
= true
153 self.current_flow_context
= flow
157 fun merge_continues_to
(before_loop
: FlowContext, escapemark
: nullable EscapeMark)
159 if escapemark
== null then return
160 for b
in escapemark
.continues
do
161 var before
= b
.before_flow_context
162 if before
== null then continue # Forward error
163 before_loop
.add_loop
(before
)
167 fun merge_breaks
(escapemark
: nullable EscapeMark)
169 if escapemark
== null then return
170 for b
in escapemark
.breaks
do
171 var before
= b
.before_flow_context
172 if before
== null then continue # Forward error
173 self.make_merge_flow
(self.current_flow_context
, before
)
178 # A Node in the static flow graph.
179 # A same FlowContext can be shared by more than one ANode.
181 # The reachable previous flow
182 var previous
: Array[FlowContext] = new Array[FlowContext]
184 # Additional reachable flow that loop up to self.
185 # Loops apears in 'loop', 'while', 'for', closure and with 'continue'
186 var loops
: Array[FlowContext] = new Array[FlowContext]
188 private var is_marked_unreachable
: Bool = false
191 fun is_unreachable
: Bool
193 # Are we explicitely marked unreachable?
194 if self.is_marked_unreachable
then return true
196 # Are we the starting flow context?
197 if is_start
then return false
199 # De we have a reachable previous?
200 if previous
.length
== 0 then return true
204 # Flag to avoid repeaed errors
205 var is_already_unreachable
: Bool = false
207 # Mark that self is the starting flow context.
208 # Such a context is reachable even if there is no previous flow
209 var is_start
: Bool = false
211 # The node that introduce the flow (for debuging)
212 var node
: nullable ANode = null
214 # Additional information for the flor (for debuging)
215 var name
: String = ""
217 # The sub-flow to use if the associated expr is true
218 var when_true
: FlowContext = self
220 # The sub-flow to use if the associated expr is true
221 var when_false
: FlowContext = self
223 # Add a previous flow (iff it is reachable)
224 private fun add_previous
(flow
: FlowContext)
226 if not flow
.is_unreachable
and not previous
.has
(flow
) then
231 # Add a previous loop flow (iff it is reachable)
232 private fun add_loop
(flow
: FlowContext)
234 if not flow
.is_unreachable
and not previous
.has
(flow
) then
242 private fun accept_flow_visitor
(v
: FlowVisitor)
249 # The entry point of the whole flow analysis
250 fun do_flow
(toolcontext
: ToolContext)
252 var v
= new FlowVisitor(toolcontext
)
258 var before_flow_context
: nullable FlowContext
261 var after_flow_context
: nullable FlowContext
263 redef fun accept_flow_visitor
(v
)
265 self.before_flow_context
= v
.current_flow_context
267 self.after_flow_context
= v
.current_flow_context
272 # The flow after the full evaluation of the expression/statement
273 var after_flow_context
: nullable FlowContext
276 redef class AVarAssignExpr
277 redef fun accept_flow_visitor
(v
)
280 self.after_flow_context
= v
.make_sub_flow
284 redef class AReassignFormExpr
285 redef fun accept_flow_visitor
(v
)
288 self.after_flow_context
= v
.make_sub_flow
292 redef class ABlockExpr
293 redef fun accept_flow_visitor
(v
)
296 if not v
.current_flow_context
.is_unreachable
then
298 else if not v
.current_flow_context
.is_already_unreachable
then
299 v
.current_flow_context
.is_already_unreachable
= true
300 v
.toolcontext
.error
(e
.hot_location
, "Error: unreachable statement.")
306 redef class AReturnExpr
307 redef fun accept_flow_visitor
(v
)
310 v
.make_unreachable_flow
314 redef class AContinueExpr
315 # The flow just before it become unreachable
316 fun before_flow_context
: nullable FlowContext
318 var after
= self.after_flow_context
319 if after
== null then return null
320 return after
.previous
.first
322 redef fun accept_flow_visitor
(v
)
325 v
.make_unreachable_flow
329 redef class ABreakExpr
330 # The flow just before it become unreachable
331 fun before_flow_context
: nullable FlowContext
333 var after
= self.after_flow_context
334 if after
== null then return null
335 return after
.previous
.first
337 redef fun accept_flow_visitor
(v
)
340 v
.make_unreachable_flow
344 redef class AAbortExpr
345 redef fun accept_flow_visitor
(v
)
348 v
.make_unreachable_flow
353 redef fun accept_flow_visitor
(v
)
356 v
.merge_breaks
(self.escapemark
)
361 redef fun accept_flow_visitor
(v
)
363 var after_expr
= v
.visit_expr
(self.n_expr
)
365 v
.current_flow_context
= after_expr
.when_true
366 v
.enter_visit
(self.n_then
)
367 var after_then
= v
.current_flow_context
369 v
.current_flow_context
= after_expr
.when_false
370 v
.enter_visit
(self.n_else
)
371 var after_else
= v
.current_flow_context
373 v
.make_merge_flow
(after_then
, after_else
)
377 redef class AIfexprExpr
378 redef fun accept_flow_visitor
(v
)
380 var after_expr
= v
.visit_expr
(self.n_expr
)
382 v
.current_flow_context
= after_expr
.when_true
383 v
.enter_visit
(self.n_then
)
384 var after_then
= v
.current_flow_context
386 v
.current_flow_context
= after_expr
.when_false
387 v
.enter_visit
(self.n_else
)
388 var after_else
= v
.current_flow_context
390 v
.make_merge_flow
(after_then
, after_else
)
394 redef class AWhileExpr
395 redef fun accept_flow_visitor
(v
)
397 var before_loop
= v
.make_sub_flow
399 var after_expr
= v
.visit_expr
(self.n_expr
)
401 v
.current_flow_context
= after_expr
.when_true
402 v
.enter_visit
(self.n_block
)
403 var after_block
= v
.current_flow_context
405 before_loop
.add_loop
(after_block
)
406 v
.merge_continues_to
(after_block
, self.escapemark
)
408 v
.current_flow_context
= after_expr
.when_false
409 v
.merge_breaks
(self.escapemark
)
413 redef class ALoopExpr
414 redef fun accept_flow_visitor
(v
)
416 var before_loop
= v
.make_sub_flow
418 v
.enter_visit
(self.n_block
)
420 var after_block
= v
.current_flow_context
422 before_loop
.add_loop
(after_block
)
423 v
.merge_continues_to
(after_block
, self.escapemark
)
425 v
.make_unreachable_flow
426 v
.merge_breaks
(self.escapemark
)
431 redef fun accept_flow_visitor
(v
)
433 v
.enter_visit
(self.n_expr
)
435 var before_loop
= v
.make_sub_flow
437 v
.enter_visit
(self.n_block
)
439 var after_block
= v
.current_flow_context
441 before_loop
.add_loop
(after_block
)
442 v
.merge_continues_to
(after_block
, self.escapemark
)
444 v
.make_merge_flow
(v
.current_flow_context
, before_loop
)
445 v
.merge_breaks
(self.escapemark
)
449 redef class AAssertExpr
450 redef fun accept_flow_visitor
(v
)
452 v
.enter_visit
(self.n_expr
)
453 var after_expr
= v
.current_flow_context
455 v
.current_flow_context
= after_expr
.when_false
456 v
.enter_visit
(n_else
)
457 # the after context of n_else is a dead end, so we do not care
459 v
.current_flow_context
= after_expr
.when_true
464 redef fun accept_flow_visitor
(v
)
466 var after_expr
= v
.visit_expr
(self.n_expr
)
468 v
.current_flow_context
= after_expr
.when_false
469 var after_expr2
= v
.visit_expr
(self.n_expr2
)
471 v
.make_true_false_flow
(v
.make_merge_flow
(after_expr
.when_true
, after_expr2
.when_true
), after_expr2
.when_false
)
476 redef fun accept_flow_visitor
(v
)
478 var after_expr
= v
.visit_expr
(self.n_expr
)
480 v
.current_flow_context
= after_expr
.when_true
481 var after_expr2
= v
.visit_expr
(self.n_expr2
)
483 var merge_false
= v
.make_merge_flow
(after_expr
.when_false
, after_expr2
.when_false
)
484 merge_false
.name
= "AND FALSE"
486 v
.make_true_false_flow
(after_expr2
.when_true
, merge_false
)
491 redef fun accept_flow_visitor
(v
)
493 var after_expr
= v
.visit_expr
(self.n_expr
)
495 v
.make_true_false_flow
(after_expr
.when_false
, after_expr
.when_true
)
499 redef class AOrElseExpr
500 redef fun accept_flow_visitor
(v
)
507 redef fun accept_flow_visitor
(v
)
510 v
.make_sub_true_false_flow
516 redef fun accept_flow_visitor
(v
)
519 v
.make_sub_true_false_flow
523 redef class AClosureCallExpr
524 redef fun accept_flow_visitor
(v
)
527 # FIXME: break closure call?
528 # v.make_unreachable_flow
532 redef class AClosureDef
533 redef fun accept_flow_visitor
(v
)
535 var before_loop
= v
.make_sub_flow
537 v
.enter_visit
(self.n_expr
)
539 var after_block
= v
.current_flow_context
540 before_loop
.add_loop
(after_block
)
542 v
.make_merge_flow
(v
.current_flow_context
, before_loop
)
547 redef fun accept_flow_visitor
(v
)
550 v
.make_sub_true_false_flow