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.
22 redef class ToolContext
23 # Run `APropdef::do_flow` on each propdef
24 var flow_phase
: Phase = new FlowPhase(self, [scope_phase
])
27 private class FlowPhase
30 redef fun process_npropdef
(npropdef
) do npropdef
.do_flow
(toolcontext
)
33 # The visitor that determine flowcontext for nodes
34 private class FlowVisitor
37 var current_flow_context
= new FlowContext
39 var toolcontext
: ToolContext
43 flows
.add
(current_flow_context
)
44 current_flow_context
.is_start
= true
47 var first
: nullable ANode = null
51 if first
== null then first
= node
53 if current_flow_context
.node
== null then current_flow_context
.node
= node
54 node
.accept_flow_visitor
(self)
55 if node
isa AExpr then
56 var flow
= self.current_flow_context
57 node
.after_flow_context
= flow
58 # Force the creation of a specific merge after the analysis of the node.
59 if flow
.when_true
!= flow
or flow
.when_false
!= flow
then
61 self.current_flow_context
.name
= "AUTOSUB"
70 fun visit_expr
(node
: AExpr): FlowContext
72 self.enter_visit
(node
)
73 return node
.after_flow_context
.as(not null)
76 var flows
= new Array[FlowContext]
80 var file
= new FileWriter.open
("flow.dot")
81 file
.write
("digraph \{\n")
84 if f
.node
isa AExpr then
85 s
= "\\nmain={f.node.as(AExpr).after_flow_context.object_id}"
87 file
.write
"F{f.object_id} [label=\"{f.object_id}\\n
{f.node.location}\\n
{f.node.class_name}\\n
{f.name}{s}\
"];\n"
88 for p
in f
.previous
do
89 file
.write
"F{p.object_id} -> F{f.object_id};\n"
91 if f
.when_true
!= f
then
92 file
.write
"F{f.object_id} -> F{f.when_true.object_id}[label=TRUE, style=dotted];\n"
94 if f
.when_false
!= f
then
95 file
.write
"F{f.object_id} -> F{f.when_false.object_id}[label=FALSE,style=dotted];\n"
103 fun make_sub_flow
: FlowContext
105 var flow
= new FlowContext
107 flow
.node
= current_node
108 flow
.add_previous
(self.current_flow_context
)
109 self.current_flow_context
= flow
113 fun make_merge_flow
(flow1
, flow2
: FlowContext): FlowContext
115 var flow
= new FlowContext
117 flow
.node
= current_node
118 flow
.add_previous
(flow1
)
119 flow
.add_previous
(flow2
)
120 self.current_flow_context
= flow
124 fun make_true_false_flow
(true_flow
, false_flow
: FlowContext): FlowContext
126 var flow
= new FlowContext
128 flow
.node
= current_node
129 flow
.add_previous
(true_flow
)
130 flow
.add_previous
(false_flow
)
131 flow
.when_true
= true_flow
132 flow
.when_false
= false_flow
133 self.current_flow_context
= flow
137 fun make_sub_true_false_flow
: FlowContext
139 var orig_flow
= self.current_flow_context
140 var true_flow
= new FlowContext
142 true_flow
.node
= current_node
143 true_flow
.add_previous
(orig_flow
)
144 true_flow
.name
= "TRUE"
145 var false_flow
= new FlowContext
146 flows
.add
(false_flow
)
147 false_flow
.node
= current_node
148 false_flow
.add_previous
(orig_flow
)
149 false_flow
.name
= "FALSE"
150 return make_true_false_flow
(true_flow
, false_flow
)
153 fun make_unreachable_flow
: FlowContext
155 var flow
= new FlowContext
157 flow
.node
= current_node
158 flow
.add_previous
(self.current_flow_context
)
159 flow
.is_marked_unreachable
= true
160 self.current_flow_context
= flow
164 fun merge_continues_to
(before_loop
: FlowContext, escapemark
: nullable EscapeMark)
166 if escapemark
== null then return
167 for b
in escapemark
.escapes
do
168 var before
= b
.before_flow_context
169 if before
== null then continue # Forward error
170 before_loop
.add_loop
(before
)
174 fun merge_breaks
(escapemark
: nullable EscapeMark)
176 if escapemark
== null then return
177 for b
in escapemark
.escapes
do
178 var before
= b
.before_flow_context
179 if before
== null then continue # Forward error
180 self.make_merge_flow
(self.current_flow_context
, before
)
185 # A Node in the static flow graph.
186 # A same `FlowContext` can be shared by more than one `ANode`.
188 # The reachable previous flow
189 var previous
= new Array[FlowContext]
191 # Additional reachable flow that loop up to self.
192 # Loops appears in `loop`, `while`, `for`, and with `continue`
193 var loops
= new Array[FlowContext]
195 private var is_marked_unreachable
: Bool = false
198 fun is_unreachable
: Bool
200 # Are we explicitly marked unreachable?
201 if self.is_marked_unreachable
then return true
203 # Are we the starting flow context?
204 if is_start
then return false
206 # De we have a reachable previous?
207 if previous
.length
== 0 then return true
211 # Flag to avoid repeated errors
212 var is_already_unreachable
: Bool = false
214 # Mark that self is the starting flow context.
215 # Such a context is reachable even if there is no previous flow
216 var is_start
: Bool = false
218 # The node that introduce the flow (for debugging)
219 var node
: nullable ANode = null
221 # Additional information for the flow (for debugging)
222 var name
: String = ""
224 # The sub-flow to use if the associated expr is true
225 var when_true
: FlowContext = self
227 # The sub-flow to use if the associated expr is true
228 var when_false
: FlowContext = self
230 # Add a previous flow (iff it is reachable)
231 private fun add_previous
(flow
: FlowContext)
233 if not flow
.is_unreachable
and not previous
.has
(flow
) then
238 # Add a previous loop flow (iff it is reachable)
239 private fun add_loop
(flow
: FlowContext)
241 if not flow
.is_unreachable
and not previous
.has
(flow
) then
249 private fun accept_flow_visitor
(v
: FlowVisitor)
256 # The entry point of the whole flow analysis
257 fun do_flow
(toolcontext
: ToolContext)
259 var v
= new FlowVisitor(toolcontext
)
265 var before_flow_context
: nullable FlowContext
268 var after_flow_context
: nullable FlowContext
270 redef fun accept_flow_visitor
(v
)
272 self.before_flow_context
= v
.current_flow_context
274 self.after_flow_context
= v
.current_flow_context
279 # The flow after the full evaluation of the expression/statement
280 var after_flow_context
: nullable FlowContext
283 redef class AVarAssignExpr
284 redef fun accept_flow_visitor
(v
)
287 self.after_flow_context
= v
.make_sub_flow
291 redef class AReassignFormExpr
292 redef fun accept_flow_visitor
(v
)
295 self.after_flow_context
= v
.make_sub_flow
299 redef class ABlockExpr
300 redef fun accept_flow_visitor
(v
)
303 if not v
.current_flow_context
.is_unreachable
then
305 else if not v
.current_flow_context
.is_already_unreachable
then
306 v
.current_flow_context
.is_already_unreachable
= true
307 v
.toolcontext
.error
(e
.hot_location
, "Error: unreachable statement.")
313 redef class AReturnExpr
314 redef fun accept_flow_visitor
(v
)
317 v
.make_unreachable_flow
321 redef class AEscapeExpr
322 # The flow just before it become unreachable
323 fun before_flow_context
: nullable FlowContext
325 var after
= self.after_flow_context
326 if after
== null then return null
327 return after
.previous
.first
329 redef fun accept_flow_visitor
(v
)
332 v
.make_unreachable_flow
336 redef class AAbortExpr
337 redef fun accept_flow_visitor
(v
)
340 v
.make_unreachable_flow
345 redef fun accept_flow_visitor
(v
)
348 v
.merge_breaks
(self.break_mark
)
353 redef fun accept_flow_visitor
(v
)
355 var after_expr
= v
.visit_expr
(self.n_expr
)
357 v
.current_flow_context
= after_expr
.when_true
358 v
.enter_visit
(self.n_then
)
359 var after_then
= v
.current_flow_context
361 v
.current_flow_context
= after_expr
.when_false
362 v
.enter_visit
(self.n_else
)
363 var after_else
= v
.current_flow_context
365 v
.make_merge_flow
(after_then
, after_else
)
369 redef class AIfexprExpr
370 redef fun accept_flow_visitor
(v
)
372 var after_expr
= v
.visit_expr
(self.n_expr
)
374 v
.current_flow_context
= after_expr
.when_true
375 v
.enter_visit
(self.n_then
)
376 var after_then
= v
.current_flow_context
378 v
.current_flow_context
= after_expr
.when_false
379 v
.enter_visit
(self.n_else
)
380 var after_else
= v
.current_flow_context
382 v
.make_merge_flow
(after_then
, after_else
)
386 redef class AWhileExpr
387 redef fun accept_flow_visitor
(v
)
389 var before_loop
= v
.make_sub_flow
391 var after_expr
= v
.visit_expr
(self.n_expr
)
393 v
.current_flow_context
= after_expr
.when_true
394 v
.enter_visit
(self.n_block
)
395 var after_block
= v
.current_flow_context
397 before_loop
.add_loop
(after_block
)
398 v
.merge_continues_to
(after_block
, self.continue_mark
)
400 v
.current_flow_context
= after_expr
.when_false
401 v
.merge_breaks
(self.break_mark
)
405 redef class ALoopExpr
406 redef fun accept_flow_visitor
(v
)
408 var before_loop
= v
.make_sub_flow
410 v
.enter_visit
(self.n_block
)
412 var after_block
= v
.current_flow_context
414 before_loop
.add_loop
(after_block
)
415 v
.merge_continues_to
(after_block
, self.continue_mark
)
417 v
.make_unreachable_flow
418 v
.merge_breaks
(self.break_mark
)
423 redef fun accept_flow_visitor
(v
)
425 v
.enter_visit
(self.n_expr
)
427 var before_loop
= v
.make_sub_flow
429 v
.enter_visit
(self.n_block
)
431 var after_block
= v
.current_flow_context
433 before_loop
.add_loop
(after_block
)
434 v
.merge_continues_to
(after_block
, self.continue_mark
)
436 v
.make_merge_flow
(v
.current_flow_context
, before_loop
)
437 v
.merge_breaks
(self.break_mark
)
441 redef class AAssertExpr
442 redef fun accept_flow_visitor
(v
)
444 var after_expr
= v
.visit_expr
(self.n_expr
)
446 v
.current_flow_context
= after_expr
.when_false
447 v
.enter_visit
(n_else
)
448 # the after context of n_else is a dead end, so we do not care
450 v
.current_flow_context
= after_expr
.when_true
455 redef fun accept_flow_visitor
(v
)
457 var after_expr
= v
.visit_expr
(self.n_expr
)
459 v
.current_flow_context
= after_expr
.when_false
460 var after_expr2
= v
.visit_expr
(self.n_expr2
)
462 var merge_true
= v
.make_merge_flow
(after_expr
.when_true
, after_expr2
.when_true
)
463 merge_true
.name
= "OR TRUE"
465 v
.make_true_false_flow
(merge_true
, after_expr2
.when_false
)
469 redef class AImpliesExpr
470 redef fun accept_flow_visitor
(v
)
472 var after_expr
= v
.visit_expr
(self.n_expr
)
474 v
.current_flow_context
= after_expr
.when_true
475 var after_expr2
= v
.visit_expr
(self.n_expr2
)
477 var merge_true
= v
.make_merge_flow
(after_expr
.when_false
, after_expr2
.when_true
)
478 merge_true
.name
= "OR TRUE"
480 v
.make_true_false_flow
(merge_true
, after_expr2
.when_false
)
485 redef fun accept_flow_visitor
(v
)
487 var after_expr
= v
.visit_expr
(self.n_expr
)
489 v
.current_flow_context
= after_expr
.when_true
490 var after_expr2
= v
.visit_expr
(self.n_expr2
)
492 var merge_false
= v
.make_merge_flow
(after_expr
.when_false
, after_expr2
.when_false
)
493 merge_false
.name
= "AND FALSE"
495 v
.make_true_false_flow
(after_expr2
.when_true
, merge_false
)
500 redef fun accept_flow_visitor
(v
)
502 var after_expr
= v
.visit_expr
(self.n_expr
)
504 v
.make_true_false_flow
(after_expr
.when_false
, after_expr
.when_true
)
508 redef class AOrElseExpr
509 redef fun accept_flow_visitor
(v
)
516 redef fun accept_flow_visitor
(v
)
519 v
.make_sub_true_false_flow
525 redef fun accept_flow_visitor
(v
)
528 v
.make_sub_true_false_flow
533 redef fun accept_flow_visitor
(v
)
536 v
.make_sub_true_false_flow
541 redef fun accept_flow_visitor
(v
)
543 var after_expr
= v
.visit_expr
(self.n_expr
)
544 v
.current_flow_context
= after_expr
548 redef class AOnceExpr
549 redef fun accept_flow_visitor
(v
)
551 var after_expr
= v
.visit_expr
(self.n_expr
)
552 v
.current_flow_context
= after_expr