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 var flow_phase
: Phase = new FlowPhase(self, [scope_phase
])
26 private class FlowPhase
29 redef fun process_npropdef
(npropdef
) do npropdef
.do_flow
(toolcontext
)
32 # The visitor that determine flowcontext for nodes
33 private class FlowVisitor
36 var current_flow_context
: FlowContext
38 var toolcontext
: ToolContext
40 init(toolcontext
: ToolContext)
42 self.toolcontext
= toolcontext
43 current_flow_context
= new FlowContext
44 flows
.add
(current_flow_context
)
45 current_flow_context
.is_start
= true
48 var first
: nullable ANode
52 if first
== null then first
= node
54 if current_flow_context
.node
== null then current_flow_context
.node
= node
55 node
.accept_flow_visitor
(self)
56 if node
isa AExpr then
57 var flow
= self.current_flow_context
58 node
.after_flow_context
= flow
59 # Force the creation of a specific merge after the analysis of the node.
60 if flow
.when_true
!= flow
or flow
.when_false
!= flow
then
62 self.current_flow_context
.name
= "AUTOSUB"
71 fun visit_expr
(node
: AExpr): FlowContext
73 self.enter_visit
(node
)
74 return node
.after_flow_context
.as(not null)
77 var flows
= new Array[FlowContext]
81 var file
= new OFStream.open
("flow.dot")
82 file
.write
("digraph \{\n")
85 if f
.node
isa AExpr then
86 s
= "\\nmain={f.node.as(AExpr).after_flow_context.object_id}"
88 file
.write
"F{f.object_id} [label=\"{f.object_id}\\n
{f.node.location}\\n
{f.node.class_name}\\n
{f.name}{s}\
"];\n"
89 for p
in f
.previous
do
90 file
.write
"F{p.object_id} -> F{f.object_id};\n"
92 if f
.when_true
!= f
then
93 file
.write
"F{f.object_id} -> F{f.when_true.object_id}[label=TRUE, style=dotted];\n"
95 if f
.when_false
!= f
then
96 file
.write
"F{f.object_id} -> F{f.when_false.object_id}[label=FALSE,style=dotted];\n"
104 fun make_sub_flow
: FlowContext
106 var flow
= new FlowContext
108 flow
.node
= current_node
109 flow
.add_previous
(self.current_flow_context
)
110 self.current_flow_context
= flow
114 fun make_merge_flow
(flow1
, flow2
: FlowContext): FlowContext
116 var flow
= new FlowContext
118 flow
.node
= current_node
119 flow
.add_previous
(flow1
)
120 flow
.add_previous
(flow2
)
121 self.current_flow_context
= flow
125 fun make_true_false_flow
(true_flow
, false_flow
: FlowContext): FlowContext
127 var flow
= new FlowContext
129 flow
.node
= current_node
130 flow
.add_previous
(true_flow
)
131 flow
.add_previous
(false_flow
)
132 flow
.when_true
= true_flow
133 flow
.when_false
= false_flow
134 self.current_flow_context
= flow
138 fun make_sub_true_false_flow
: FlowContext
140 var orig_flow
= self.current_flow_context
141 var true_flow
= new FlowContext
143 true_flow
.node
= current_node
144 true_flow
.add_previous
(orig_flow
)
145 true_flow
.name
= "TRUE"
146 var false_flow
= new FlowContext
147 flows
.add
(false_flow
)
148 false_flow
.node
= current_node
149 false_flow
.add_previous
(orig_flow
)
150 false_flow
.name
= "FALSE"
151 return make_true_false_flow
(true_flow
, false_flow
)
154 fun make_unreachable_flow
: FlowContext
156 var flow
= new FlowContext
158 flow
.node
= current_node
159 flow
.add_previous
(self.current_flow_context
)
160 flow
.is_marked_unreachable
= true
161 self.current_flow_context
= flow
165 fun merge_continues_to
(before_loop
: FlowContext, escapemark
: nullable EscapeMark)
167 if escapemark
== null then return
168 for b
in escapemark
.continues
do
169 var before
= b
.before_flow_context
170 if before
== null then continue # Forward error
171 before_loop
.add_loop
(before
)
175 fun merge_breaks
(escapemark
: nullable EscapeMark)
177 if escapemark
== null then return
178 for b
in escapemark
.breaks
do
179 var before
= b
.before_flow_context
180 if before
== null then continue # Forward error
181 self.make_merge_flow
(self.current_flow_context
, before
)
186 # A Node in the static flow graph.
187 # A same `FlowContext` can be shared by more than one `ANode`.
189 # The reachable previous flow
190 var previous
= new Array[FlowContext]
192 # Additional reachable flow that loop up to self.
193 # Loops appears in `loop`, `while`, `for`, and with `continue`
194 var loops
= new Array[FlowContext]
196 private var is_marked_unreachable
: Bool = false
199 fun is_unreachable
: Bool
201 # Are we explicitly marked unreachable?
202 if self.is_marked_unreachable
then return true
204 # Are we the starting flow context?
205 if is_start
then return false
207 # De we have a reachable previous?
208 if previous
.length
== 0 then return true
212 # Flag to avoid repeated errors
213 var is_already_unreachable
: Bool = false
215 # Mark that self is the starting flow context.
216 # Such a context is reachable even if there is no previous flow
217 var is_start
: Bool = false
219 # The node that introduce the flow (for debugging)
220 var node
: nullable ANode = null
222 # Additional information for the flow (for debugging)
223 var name
: String = ""
225 # The sub-flow to use if the associated expr is true
226 var when_true
: FlowContext = self
228 # The sub-flow to use if the associated expr is true
229 var when_false
: FlowContext = self
231 # Add a previous flow (iff it is reachable)
232 private fun add_previous
(flow
: FlowContext)
234 if not flow
.is_unreachable
and not previous
.has
(flow
) then
239 # Add a previous loop flow (iff it is reachable)
240 private fun add_loop
(flow
: FlowContext)
242 if not flow
.is_unreachable
and not previous
.has
(flow
) then
250 private fun accept_flow_visitor
(v
: FlowVisitor)
257 # The entry point of the whole flow analysis
258 fun do_flow
(toolcontext
: ToolContext)
260 var v
= new FlowVisitor(toolcontext
)
266 var before_flow_context
: nullable FlowContext
269 var after_flow_context
: nullable FlowContext
271 redef fun accept_flow_visitor
(v
)
273 self.before_flow_context
= v
.current_flow_context
275 self.after_flow_context
= v
.current_flow_context
280 # The flow after the full evaluation of the expression/statement
281 var after_flow_context
: nullable FlowContext
284 redef class AVarAssignExpr
285 redef fun accept_flow_visitor
(v
)
288 self.after_flow_context
= v
.make_sub_flow
292 redef class AReassignFormExpr
293 redef fun accept_flow_visitor
(v
)
296 self.after_flow_context
= v
.make_sub_flow
300 redef class ABlockExpr
301 redef fun accept_flow_visitor
(v
)
304 if not v
.current_flow_context
.is_unreachable
then
306 else if not v
.current_flow_context
.is_already_unreachable
then
307 v
.current_flow_context
.is_already_unreachable
= true
308 v
.toolcontext
.error
(e
.hot_location
, "Error: unreachable statement.")
314 redef class AReturnExpr
315 redef fun accept_flow_visitor
(v
)
318 v
.make_unreachable_flow
322 redef class AContinueExpr
323 # The flow just before it become unreachable
324 fun before_flow_context
: nullable FlowContext
326 var after
= self.after_flow_context
327 if after
== null then return null
328 return after
.previous
.first
330 redef fun accept_flow_visitor
(v
)
333 v
.make_unreachable_flow
337 redef class ABreakExpr
338 # The flow just before it become unreachable
339 fun before_flow_context
: nullable FlowContext
341 var after
= self.after_flow_context
342 if after
== null then return null
343 return after
.previous
.first
345 redef fun accept_flow_visitor
(v
)
348 v
.make_unreachable_flow
352 redef class AAbortExpr
353 redef fun accept_flow_visitor
(v
)
356 v
.make_unreachable_flow
361 redef fun accept_flow_visitor
(v
)
364 v
.merge_breaks
(self.escapemark
)
369 redef fun accept_flow_visitor
(v
)
371 var after_expr
= v
.visit_expr
(self.n_expr
)
373 v
.current_flow_context
= after_expr
.when_true
374 v
.enter_visit
(self.n_then
)
375 var after_then
= v
.current_flow_context
377 v
.current_flow_context
= after_expr
.when_false
378 v
.enter_visit
(self.n_else
)
379 var after_else
= v
.current_flow_context
381 v
.make_merge_flow
(after_then
, after_else
)
385 redef class AIfexprExpr
386 redef fun accept_flow_visitor
(v
)
388 var after_expr
= v
.visit_expr
(self.n_expr
)
390 v
.current_flow_context
= after_expr
.when_true
391 v
.enter_visit
(self.n_then
)
392 var after_then
= v
.current_flow_context
394 v
.current_flow_context
= after_expr
.when_false
395 v
.enter_visit
(self.n_else
)
396 var after_else
= v
.current_flow_context
398 v
.make_merge_flow
(after_then
, after_else
)
402 redef class AWhileExpr
403 redef fun accept_flow_visitor
(v
)
405 var before_loop
= v
.make_sub_flow
407 var after_expr
= v
.visit_expr
(self.n_expr
)
409 v
.current_flow_context
= after_expr
.when_true
410 v
.enter_visit
(self.n_block
)
411 var after_block
= v
.current_flow_context
413 before_loop
.add_loop
(after_block
)
414 v
.merge_continues_to
(after_block
, self.escapemark
)
416 v
.current_flow_context
= after_expr
.when_false
417 v
.merge_breaks
(self.escapemark
)
421 redef class ALoopExpr
422 redef fun accept_flow_visitor
(v
)
424 var before_loop
= v
.make_sub_flow
426 v
.enter_visit
(self.n_block
)
428 var after_block
= v
.current_flow_context
430 before_loop
.add_loop
(after_block
)
431 v
.merge_continues_to
(after_block
, self.escapemark
)
433 v
.make_unreachable_flow
434 v
.merge_breaks
(self.escapemark
)
439 redef fun accept_flow_visitor
(v
)
441 v
.enter_visit
(self.n_expr
)
443 var before_loop
= v
.make_sub_flow
445 v
.enter_visit
(self.n_block
)
447 var after_block
= v
.current_flow_context
449 before_loop
.add_loop
(after_block
)
450 v
.merge_continues_to
(after_block
, self.escapemark
)
452 v
.make_merge_flow
(v
.current_flow_context
, before_loop
)
453 v
.merge_breaks
(self.escapemark
)
457 redef class AAssertExpr
458 redef fun accept_flow_visitor
(v
)
460 var after_expr
= v
.visit_expr
(self.n_expr
)
462 v
.current_flow_context
= after_expr
.when_false
463 v
.enter_visit
(n_else
)
464 # the after context of n_else is a dead end, so we do not care
466 v
.current_flow_context
= after_expr
.when_true
471 redef fun accept_flow_visitor
(v
)
473 var after_expr
= v
.visit_expr
(self.n_expr
)
475 v
.current_flow_context
= after_expr
.when_false
476 var after_expr2
= v
.visit_expr
(self.n_expr2
)
478 var merge_true
= v
.make_merge_flow
(after_expr
.when_true
, after_expr2
.when_true
)
479 merge_true
.name
= "OR TRUE"
481 v
.make_true_false_flow
(merge_true
, after_expr2
.when_false
)
485 redef class AImpliesExpr
486 redef fun accept_flow_visitor
(v
)
488 var after_expr
= v
.visit_expr
(self.n_expr
)
490 v
.current_flow_context
= after_expr
.when_true
491 var after_expr2
= v
.visit_expr
(self.n_expr2
)
493 var merge_true
= v
.make_merge_flow
(after_expr
.when_false
, after_expr2
.when_true
)
494 merge_true
.name
= "OR TRUE"
496 v
.make_true_false_flow
(merge_true
, after_expr2
.when_false
)
501 redef fun accept_flow_visitor
(v
)
503 var after_expr
= v
.visit_expr
(self.n_expr
)
505 v
.current_flow_context
= after_expr
.when_true
506 var after_expr2
= v
.visit_expr
(self.n_expr2
)
508 var merge_false
= v
.make_merge_flow
(after_expr
.when_false
, after_expr2
.when_false
)
509 merge_false
.name
= "AND FALSE"
511 v
.make_true_false_flow
(after_expr2
.when_true
, merge_false
)
516 redef fun accept_flow_visitor
(v
)
518 var after_expr
= v
.visit_expr
(self.n_expr
)
520 v
.make_true_false_flow
(after_expr
.when_false
, after_expr
.when_true
)
524 redef class AOrElseExpr
525 redef fun accept_flow_visitor
(v
)
532 redef fun accept_flow_visitor
(v
)
535 v
.make_sub_true_false_flow
541 redef fun accept_flow_visitor
(v
)
544 v
.make_sub_true_false_flow
549 redef fun accept_flow_visitor
(v
)
552 v
.make_sub_true_false_flow
556 redef class AProxyExpr
557 redef fun accept_flow_visitor
(v
)
559 var after_expr
= v
.visit_expr
(self.n_expr
)
560 v
.current_flow_context
= after_expr