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
= new FlowContext
38 var toolcontext
: ToolContext
42 flows
.add
(current_flow_context
)
43 current_flow_context
.is_start
= true
46 var first
: nullable ANode = null
50 if first
== null then first
= node
52 if current_flow_context
.node
== null then current_flow_context
.node
= node
53 node
.accept_flow_visitor
(self)
54 if node
isa AExpr then
55 var flow
= self.current_flow_context
56 node
.after_flow_context
= flow
57 # Force the creation of a specific merge after the analysis of the node.
58 if flow
.when_true
!= flow
or flow
.when_false
!= flow
then
60 self.current_flow_context
.name
= "AUTOSUB"
69 fun visit_expr
(node
: AExpr): FlowContext
71 self.enter_visit
(node
)
72 return node
.after_flow_context
.as(not null)
75 var flows
= new Array[FlowContext]
79 var file
= new OFStream.open
("flow.dot")
80 file
.write
("digraph \{\n")
83 if f
.node
isa AExpr then
84 s
= "\\nmain={f.node.as(AExpr).after_flow_context.object_id}"
86 file
.write
"F{f.object_id} [label=\"{f.object_id}\\n
{f.node.location}\\n
{f.node.class_name}\\n
{f.name}{s}\
"];\n"
87 for p
in f
.previous
do
88 file
.write
"F{p.object_id} -> F{f.object_id};\n"
90 if f
.when_true
!= f
then
91 file
.write
"F{f.object_id} -> F{f.when_true.object_id}[label=TRUE, style=dotted];\n"
93 if f
.when_false
!= f
then
94 file
.write
"F{f.object_id} -> F{f.when_false.object_id}[label=FALSE,style=dotted];\n"
102 fun make_sub_flow
: FlowContext
104 var flow
= new FlowContext
106 flow
.node
= current_node
107 flow
.add_previous
(self.current_flow_context
)
108 self.current_flow_context
= flow
112 fun make_merge_flow
(flow1
, flow2
: FlowContext): FlowContext
114 var flow
= new FlowContext
116 flow
.node
= current_node
117 flow
.add_previous
(flow1
)
118 flow
.add_previous
(flow2
)
119 self.current_flow_context
= flow
123 fun make_true_false_flow
(true_flow
, false_flow
: FlowContext): FlowContext
125 var flow
= new FlowContext
127 flow
.node
= current_node
128 flow
.add_previous
(true_flow
)
129 flow
.add_previous
(false_flow
)
130 flow
.when_true
= true_flow
131 flow
.when_false
= false_flow
132 self.current_flow_context
= flow
136 fun make_sub_true_false_flow
: FlowContext
138 var orig_flow
= self.current_flow_context
139 var true_flow
= new FlowContext
141 true_flow
.node
= current_node
142 true_flow
.add_previous
(orig_flow
)
143 true_flow
.name
= "TRUE"
144 var false_flow
= new FlowContext
145 flows
.add
(false_flow
)
146 false_flow
.node
= current_node
147 false_flow
.add_previous
(orig_flow
)
148 false_flow
.name
= "FALSE"
149 return make_true_false_flow
(true_flow
, false_flow
)
152 fun make_unreachable_flow
: FlowContext
154 var flow
= new FlowContext
156 flow
.node
= current_node
157 flow
.add_previous
(self.current_flow_context
)
158 flow
.is_marked_unreachable
= true
159 self.current_flow_context
= flow
163 fun merge_continues_to
(before_loop
: FlowContext, escapemark
: nullable EscapeMark)
165 if escapemark
== null then return
166 for b
in escapemark
.escapes
do
167 var before
= b
.before_flow_context
168 if before
== null then continue # Forward error
169 before_loop
.add_loop
(before
)
173 fun merge_breaks
(escapemark
: nullable EscapeMark)
175 if escapemark
== null then return
176 for b
in escapemark
.escapes
do
177 var before
= b
.before_flow_context
178 if before
== null then continue # Forward error
179 self.make_merge_flow
(self.current_flow_context
, before
)
184 # A Node in the static flow graph.
185 # A same `FlowContext` can be shared by more than one `ANode`.
187 # The reachable previous flow
188 var previous
= new Array[FlowContext]
190 # Additional reachable flow that loop up to self.
191 # Loops appears in `loop`, `while`, `for`, and with `continue`
192 var loops
= new Array[FlowContext]
194 private var is_marked_unreachable
: Bool = false
197 fun is_unreachable
: Bool
199 # Are we explicitly marked unreachable?
200 if self.is_marked_unreachable
then return true
202 # Are we the starting flow context?
203 if is_start
then return false
205 # De we have a reachable previous?
206 if previous
.length
== 0 then return true
210 # Flag to avoid repeated errors
211 var is_already_unreachable
: Bool = false
213 # Mark that self is the starting flow context.
214 # Such a context is reachable even if there is no previous flow
215 var is_start
: Bool = false
217 # The node that introduce the flow (for debugging)
218 var node
: nullable ANode = null
220 # Additional information for the flow (for debugging)
221 var name
: String = ""
223 # The sub-flow to use if the associated expr is true
224 var when_true
: FlowContext = self
226 # The sub-flow to use if the associated expr is true
227 var when_false
: FlowContext = self
229 # Add a previous flow (iff it is reachable)
230 private fun add_previous
(flow
: FlowContext)
232 if not flow
.is_unreachable
and not previous
.has
(flow
) then
237 # Add a previous loop flow (iff it is reachable)
238 private fun add_loop
(flow
: FlowContext)
240 if not flow
.is_unreachable
and not previous
.has
(flow
) then
248 private fun accept_flow_visitor
(v
: FlowVisitor)
255 # The entry point of the whole flow analysis
256 fun do_flow
(toolcontext
: ToolContext)
258 var v
= new FlowVisitor(toolcontext
)
264 var before_flow_context
: nullable FlowContext
267 var after_flow_context
: nullable FlowContext
269 redef fun accept_flow_visitor
(v
)
271 self.before_flow_context
= v
.current_flow_context
273 self.after_flow_context
= v
.current_flow_context
278 # The flow after the full evaluation of the expression/statement
279 var after_flow_context
: nullable FlowContext
282 redef class AVarAssignExpr
283 redef fun accept_flow_visitor
(v
)
286 self.after_flow_context
= v
.make_sub_flow
290 redef class AReassignFormExpr
291 redef fun accept_flow_visitor
(v
)
294 self.after_flow_context
= v
.make_sub_flow
298 redef class ABlockExpr
299 redef fun accept_flow_visitor
(v
)
302 if not v
.current_flow_context
.is_unreachable
then
304 else if not v
.current_flow_context
.is_already_unreachable
then
305 v
.current_flow_context
.is_already_unreachable
= true
306 v
.toolcontext
.error
(e
.hot_location
, "Error: unreachable statement.")
312 redef class AReturnExpr
313 redef fun accept_flow_visitor
(v
)
316 v
.make_unreachable_flow
320 redef class AEscapeExpr
321 # The flow just before it become unreachable
322 fun before_flow_context
: nullable FlowContext
324 var after
= self.after_flow_context
325 if after
== null then return null
326 return after
.previous
.first
328 redef fun accept_flow_visitor
(v
)
331 v
.make_unreachable_flow
335 redef class AAbortExpr
336 redef fun accept_flow_visitor
(v
)
339 v
.make_unreachable_flow
344 redef fun accept_flow_visitor
(v
)
347 v
.merge_breaks
(self.break_mark
)
352 redef fun accept_flow_visitor
(v
)
354 var after_expr
= v
.visit_expr
(self.n_expr
)
356 v
.current_flow_context
= after_expr
.when_true
357 v
.enter_visit
(self.n_then
)
358 var after_then
= v
.current_flow_context
360 v
.current_flow_context
= after_expr
.when_false
361 v
.enter_visit
(self.n_else
)
362 var after_else
= v
.current_flow_context
364 v
.make_merge_flow
(after_then
, after_else
)
368 redef class AIfexprExpr
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 AWhileExpr
386 redef fun accept_flow_visitor
(v
)
388 var before_loop
= v
.make_sub_flow
390 var after_expr
= v
.visit_expr
(self.n_expr
)
392 v
.current_flow_context
= after_expr
.when_true
393 v
.enter_visit
(self.n_block
)
394 var after_block
= v
.current_flow_context
396 before_loop
.add_loop
(after_block
)
397 v
.merge_continues_to
(after_block
, self.continue_mark
)
399 v
.current_flow_context
= after_expr
.when_false
400 v
.merge_breaks
(self.break_mark
)
404 redef class ALoopExpr
405 redef fun accept_flow_visitor
(v
)
407 var before_loop
= v
.make_sub_flow
409 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.continue_mark
)
416 v
.make_unreachable_flow
417 v
.merge_breaks
(self.break_mark
)
422 redef fun accept_flow_visitor
(v
)
424 v
.enter_visit
(self.n_expr
)
426 var before_loop
= v
.make_sub_flow
428 v
.enter_visit
(self.n_block
)
430 var after_block
= v
.current_flow_context
432 before_loop
.add_loop
(after_block
)
433 v
.merge_continues_to
(after_block
, self.continue_mark
)
435 v
.make_merge_flow
(v
.current_flow_context
, before_loop
)
436 v
.merge_breaks
(self.break_mark
)
440 redef class AAssertExpr
441 redef fun accept_flow_visitor
(v
)
443 var after_expr
= v
.visit_expr
(self.n_expr
)
445 v
.current_flow_context
= after_expr
.when_false
446 v
.enter_visit
(n_else
)
447 # the after context of n_else is a dead end, so we do not care
449 v
.current_flow_context
= after_expr
.when_true
454 redef fun accept_flow_visitor
(v
)
456 var after_expr
= v
.visit_expr
(self.n_expr
)
458 v
.current_flow_context
= after_expr
.when_false
459 var after_expr2
= v
.visit_expr
(self.n_expr2
)
461 var merge_true
= v
.make_merge_flow
(after_expr
.when_true
, after_expr2
.when_true
)
462 merge_true
.name
= "OR TRUE"
464 v
.make_true_false_flow
(merge_true
, after_expr2
.when_false
)
468 redef class AImpliesExpr
469 redef fun accept_flow_visitor
(v
)
471 var after_expr
= v
.visit_expr
(self.n_expr
)
473 v
.current_flow_context
= after_expr
.when_true
474 var after_expr2
= v
.visit_expr
(self.n_expr2
)
476 var merge_true
= v
.make_merge_flow
(after_expr
.when_false
, after_expr2
.when_true
)
477 merge_true
.name
= "OR TRUE"
479 v
.make_true_false_flow
(merge_true
, after_expr2
.when_false
)
484 redef fun accept_flow_visitor
(v
)
486 var after_expr
= v
.visit_expr
(self.n_expr
)
488 v
.current_flow_context
= after_expr
.when_true
489 var after_expr2
= v
.visit_expr
(self.n_expr2
)
491 var merge_false
= v
.make_merge_flow
(after_expr
.when_false
, after_expr2
.when_false
)
492 merge_false
.name
= "AND FALSE"
494 v
.make_true_false_flow
(after_expr2
.when_true
, merge_false
)
499 redef fun accept_flow_visitor
(v
)
501 var after_expr
= v
.visit_expr
(self.n_expr
)
503 v
.make_true_false_flow
(after_expr
.when_false
, after_expr
.when_true
)
507 redef class AOrElseExpr
508 redef fun accept_flow_visitor
(v
)
515 redef fun accept_flow_visitor
(v
)
518 v
.make_sub_true_false_flow
524 redef fun accept_flow_visitor
(v
)
527 v
.make_sub_true_false_flow
532 redef fun accept_flow_visitor
(v
)
535 v
.make_sub_true_false_flow
540 redef fun accept_flow_visitor
(v
)
542 var after_expr
= v
.visit_expr
(self.n_expr
)
543 v
.current_flow_context
= after_expr
547 redef class AOnceExpr
548 redef fun accept_flow_visitor
(v
)
550 var after_expr
= v
.visit_expr
(self.n_expr
)
551 v
.current_flow_context
= after_expr