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.
25 redef class ToolContext
26 var flow_phase
: Phase = new FlowPhase(self, [scope_phase
])
29 private class FlowPhase
32 redef fun process_npropdef
(npropdef
) do npropdef
.do_flow
(toolcontext
)
35 # The visitor that derermine flowcontext for nodes
36 private class FlowVisitor
39 var current_flow_context
: FlowContext
41 var toolcontext
: ToolContext
43 init(toolcontext
: ToolContext)
45 self.toolcontext
= toolcontext
46 current_flow_context
= new FlowContext
47 flows
.add
(current_flow_context
)
48 current_flow_context
.is_start
= true
51 var first
: nullable ANode
55 if first
== null then first
= node
57 if current_flow_context
.node
== null then current_flow_context
.node
= node
58 node
.accept_flow_visitor
(self)
59 if node
isa AExpr then
60 var flow
= self.current_flow_context
61 node
.after_flow_context
= flow
62 # Force the creation of a specific merge after the analysis of the node.
63 if flow
.when_true
!= flow
or flow
.when_false
!= flow
then
65 self.current_flow_context
.name
= "AUTOSUB"
74 fun visit_expr
(node
: AExpr): FlowContext
76 self.enter_visit
(node
)
77 return node
.after_flow_context
.as(not null)
80 var flows
: Array[FlowContext] = new Array[FlowContext]
84 var file
= new OFStream.open
("flow.dot")
85 file
.write
("digraph \{\n")
88 if f
.node
isa AExpr then
89 s
= "\\nmain={f.node.as(AExpr).after_flow_context.object_id}"
91 file
.write
"F{f.object_id} [label=\"{f.object_id}\\n
{f.node.location}\\n
{f.node.class_name}\\n
{f.name}{s}\
"];\n"
92 for p
in f
.previous
do
93 file
.write
"F{p.object_id} -> F{f.object_id};\n"
95 if f
.when_true
!= f
then
96 file
.write
"F{f.object_id} -> F{f.when_true.object_id}[label=TRUE, style=dotted];\n"
98 if f
.when_false
!= f
then
99 file
.write
"F{f.object_id} -> F{f.when_false.object_id}[label=FALSE,style=dotted];\n"
107 fun make_sub_flow
: FlowContext
109 var flow
= new FlowContext
111 flow
.node
= current_node
112 flow
.add_previous
(self.current_flow_context
)
113 self.current_flow_context
= flow
117 fun make_merge_flow
(flow1
, flow2
: FlowContext): FlowContext
119 var flow
= new FlowContext
121 flow
.node
= current_node
122 flow
.add_previous
(flow1
)
123 flow
.add_previous
(flow2
)
124 self.current_flow_context
= flow
128 fun make_true_false_flow
(true_flow
, false_flow
: FlowContext): FlowContext
130 var flow
= new FlowContext
132 flow
.node
= current_node
133 flow
.add_previous
(true_flow
)
134 flow
.add_previous
(false_flow
)
135 flow
.when_true
= true_flow
136 flow
.when_false
= false_flow
137 self.current_flow_context
= flow
141 fun make_sub_true_false_flow
: FlowContext
143 var orig_flow
= self.current_flow_context
144 var true_flow
= new FlowContext
146 true_flow
.node
= current_node
147 true_flow
.add_previous
(orig_flow
)
148 true_flow
.name
= "TRUE"
149 var false_flow
= new FlowContext
150 flows
.add
(false_flow
)
151 false_flow
.node
= current_node
152 false_flow
.add_previous
(orig_flow
)
153 false_flow
.name
= "FALSE"
154 return make_true_false_flow
(true_flow
, false_flow
)
157 fun make_unreachable_flow
: FlowContext
159 var flow
= new FlowContext
161 flow
.node
= current_node
162 flow
.add_previous
(self.current_flow_context
)
163 flow
.is_marked_unreachable
= true
164 self.current_flow_context
= flow
168 fun merge_continues_to
(before_loop
: FlowContext, escapemark
: nullable EscapeMark)
170 if escapemark
== null then return
171 for b
in escapemark
.continues
do
172 var before
= b
.before_flow_context
173 if before
== null then continue # Forward error
174 before_loop
.add_loop
(before
)
178 fun merge_breaks
(escapemark
: nullable EscapeMark)
180 if escapemark
== null then return
181 for b
in escapemark
.breaks
do
182 var before
= b
.before_flow_context
183 if before
== null then continue # Forward error
184 self.make_merge_flow
(self.current_flow_context
, before
)
189 # A Node in the static flow graph.
190 # A same `FlowContext` can be shared by more than one `ANode`.
192 # The reachable previous flow
193 var previous
: Array[FlowContext] = new Array[FlowContext]
195 # Additional reachable flow that loop up to self.
196 # Loops apears in `loop`, `while`, `for`, closure and with `continue`
197 var loops
: Array[FlowContext] = new Array[FlowContext]
199 private var is_marked_unreachable
: Bool = false
202 fun is_unreachable
: Bool
204 # Are we explicitely marked unreachable?
205 if self.is_marked_unreachable
then return true
207 # Are we the starting flow context?
208 if is_start
then return false
210 # De we have a reachable previous?
211 if previous
.length
== 0 then return true
215 # Flag to avoid repeaed errors
216 var is_already_unreachable
: Bool = false
218 # Mark that self is the starting flow context.
219 # Such a context is reachable even if there is no previous flow
220 var is_start
: Bool = false
222 # The node that introduce the flow (for debuging)
223 var node
: nullable ANode = null
225 # Additional information for the flor (for debuging)
226 var name
: String = ""
228 # The sub-flow to use if the associated expr is true
229 var when_true
: FlowContext = self
231 # The sub-flow to use if the associated expr is true
232 var when_false
: FlowContext = self
234 # Add a previous flow (iff it is reachable)
235 private fun add_previous
(flow
: FlowContext)
237 if not flow
.is_unreachable
and not previous
.has
(flow
) then
242 # Add a previous loop flow (iff it is reachable)
243 private fun add_loop
(flow
: FlowContext)
245 if not flow
.is_unreachable
and not previous
.has
(flow
) then
253 private fun accept_flow_visitor
(v
: FlowVisitor)
260 # The entry point of the whole flow analysis
261 fun do_flow
(toolcontext
: ToolContext)
263 var v
= new FlowVisitor(toolcontext
)
269 var before_flow_context
: nullable FlowContext
272 var after_flow_context
: nullable FlowContext
274 redef fun accept_flow_visitor
(v
)
276 self.before_flow_context
= v
.current_flow_context
278 self.after_flow_context
= v
.current_flow_context
283 # The flow after the full evaluation of the expression/statement
284 var after_flow_context
: nullable FlowContext
287 redef class AVarAssignExpr
288 redef fun accept_flow_visitor
(v
)
291 self.after_flow_context
= v
.make_sub_flow
295 redef class AReassignFormExpr
296 redef fun accept_flow_visitor
(v
)
299 self.after_flow_context
= v
.make_sub_flow
303 redef class ABlockExpr
304 redef fun accept_flow_visitor
(v
)
307 if not v
.current_flow_context
.is_unreachable
then
309 else if not v
.current_flow_context
.is_already_unreachable
then
310 v
.current_flow_context
.is_already_unreachable
= true
311 v
.toolcontext
.error
(e
.hot_location
, "Error: unreachable statement.")
317 redef class AReturnExpr
318 redef fun accept_flow_visitor
(v
)
321 v
.make_unreachable_flow
325 redef class AContinueExpr
326 # The flow just before it become unreachable
327 fun before_flow_context
: nullable FlowContext
329 var after
= self.after_flow_context
330 if after
== null then return null
331 return after
.previous
.first
333 redef fun accept_flow_visitor
(v
)
336 v
.make_unreachable_flow
340 redef class ABreakExpr
341 # The flow just before it become unreachable
342 fun before_flow_context
: nullable FlowContext
344 var after
= self.after_flow_context
345 if after
== null then return null
346 return after
.previous
.first
348 redef fun accept_flow_visitor
(v
)
351 v
.make_unreachable_flow
355 redef class AAbortExpr
356 redef fun accept_flow_visitor
(v
)
359 v
.make_unreachable_flow
364 redef fun accept_flow_visitor
(v
)
367 v
.merge_breaks
(self.escapemark
)
372 redef fun accept_flow_visitor
(v
)
374 var after_expr
= v
.visit_expr
(self.n_expr
)
376 v
.current_flow_context
= after_expr
.when_true
377 v
.enter_visit
(self.n_then
)
378 var after_then
= v
.current_flow_context
380 v
.current_flow_context
= after_expr
.when_false
381 v
.enter_visit
(self.n_else
)
382 var after_else
= v
.current_flow_context
384 v
.make_merge_flow
(after_then
, after_else
)
388 redef class AIfexprExpr
389 redef fun accept_flow_visitor
(v
)
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_then
)
395 var after_then
= v
.current_flow_context
397 v
.current_flow_context
= after_expr
.when_false
398 v
.enter_visit
(self.n_else
)
399 var after_else
= v
.current_flow_context
401 v
.make_merge_flow
(after_then
, after_else
)
405 redef class AWhileExpr
406 redef fun accept_flow_visitor
(v
)
408 var before_loop
= v
.make_sub_flow
410 var after_expr
= v
.visit_expr
(self.n_expr
)
412 v
.current_flow_context
= after_expr
.when_true
413 v
.enter_visit
(self.n_block
)
414 var after_block
= v
.current_flow_context
416 before_loop
.add_loop
(after_block
)
417 v
.merge_continues_to
(after_block
, self.escapemark
)
419 v
.current_flow_context
= after_expr
.when_false
420 v
.merge_breaks
(self.escapemark
)
424 redef class ALoopExpr
425 redef fun accept_flow_visitor
(v
)
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.escapemark
)
436 v
.make_unreachable_flow
437 v
.merge_breaks
(self.escapemark
)
442 redef fun accept_flow_visitor
(v
)
444 v
.enter_visit
(self.n_expr
)
446 var before_loop
= v
.make_sub_flow
448 v
.enter_visit
(self.n_block
)
450 var after_block
= v
.current_flow_context
452 before_loop
.add_loop
(after_block
)
453 v
.merge_continues_to
(after_block
, self.escapemark
)
455 v
.make_merge_flow
(v
.current_flow_context
, before_loop
)
456 v
.merge_breaks
(self.escapemark
)
460 redef class AAssertExpr
461 redef fun accept_flow_visitor
(v
)
463 var after_expr
= v
.visit_expr
(self.n_expr
)
465 v
.current_flow_context
= after_expr
.when_false
466 v
.enter_visit
(n_else
)
467 # the after context of n_else is a dead end, so we do not care
469 v
.current_flow_context
= after_expr
.when_true
474 redef fun accept_flow_visitor
(v
)
476 var after_expr
= v
.visit_expr
(self.n_expr
)
478 v
.current_flow_context
= after_expr
.when_false
479 var after_expr2
= v
.visit_expr
(self.n_expr2
)
481 var merge_true
= v
.make_merge_flow
(after_expr
.when_true
, after_expr2
.when_true
)
482 merge_true
.name
= "OR TRUE"
484 v
.make_true_false_flow
(merge_true
, after_expr2
.when_false
)
489 redef fun accept_flow_visitor
(v
)
491 var after_expr
= v
.visit_expr
(self.n_expr
)
493 v
.current_flow_context
= after_expr
.when_true
494 var after_expr2
= v
.visit_expr
(self.n_expr2
)
496 var merge_false
= v
.make_merge_flow
(after_expr
.when_false
, after_expr2
.when_false
)
497 merge_false
.name
= "AND FALSE"
499 v
.make_true_false_flow
(after_expr2
.when_true
, merge_false
)
504 redef fun accept_flow_visitor
(v
)
506 var after_expr
= v
.visit_expr
(self.n_expr
)
508 v
.make_true_false_flow
(after_expr
.when_false
, after_expr
.when_true
)
512 redef class AOrElseExpr
513 redef fun accept_flow_visitor
(v
)
520 redef fun accept_flow_visitor
(v
)
523 v
.make_sub_true_false_flow
529 redef fun accept_flow_visitor
(v
)
532 v
.make_sub_true_false_flow
536 redef class AClosureCallExpr
537 redef fun accept_flow_visitor
(v
)
540 # FIXME: break closure call?
541 # v.make_unreachable_flow
545 redef class AClosureDef
546 redef fun accept_flow_visitor
(v
)
548 var before_loop
= v
.make_sub_flow
550 v
.enter_visit
(self.n_expr
)
552 var after_block
= v
.current_flow_context
553 before_loop
.add_loop
(after_block
)
555 v
.make_merge_flow
(v
.current_flow_context
, before_loop
)
560 redef fun accept_flow_visitor
(v
)
563 v
.make_sub_true_false_flow
567 redef class AProxyExpr
568 redef fun accept_flow_visitor
(v
)
570 var after_expr
= v
.visit_expr
(self.n_expr
)
571 v
.current_flow_context
= after_expr