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 # Force the creation of a specific merge after the analysis of the node.
53 if flow
.when_true
!= flow
or flow
.when_false
!= flow
then
55 self.current_flow_context
.name
= "AUTOSUB"
65 fun visit_expr
(node
: AExpr): FlowContext
67 self.enter_visit
(node
)
68 return node
.after_flow_context
.as(not null)
71 var flows
: Array[FlowContext] = new Array[FlowContext]
75 var file
= new OFStream.open
("flow.dot")
76 file
.write
("digraph \{\n")
79 if f
.node
isa AExpr then
80 s
= "\\nmain={f.node.as(AExpr).after_flow_context.object_id}"
82 file
.write
"F{f.object_id} [label=\"{f.object_id}\\n
{f.node.location}\\n
{f.node.class_name}\\n
{f.name}{s}\
"];\n"
83 for p
in f
.previous
do
84 file
.write
"F{p.object_id} -> F{f.object_id};\n"
86 if f
.when_true
!= f
then
87 file
.write
"F{f.object_id} -> F{f.when_true.object_id}[label=TRUE, style=dotted];\n"
89 if f
.when_false
!= f
then
90 file
.write
"F{f.object_id} -> F{f.when_false.object_id}[label=FALSE,style=dotted];\n"
98 fun make_sub_flow
: FlowContext
100 var flow
= new FlowContext
102 flow
.node
= current_node
103 flow
.add_previous
(self.current_flow_context
)
104 self.current_flow_context
= flow
108 fun make_merge_flow
(flow1
, flow2
: FlowContext): FlowContext
110 var flow
= new FlowContext
112 flow
.node
= current_node
113 flow
.add_previous
(flow1
)
114 flow
.add_previous
(flow2
)
115 self.current_flow_context
= flow
119 fun make_true_false_flow
(true_flow
, false_flow
: FlowContext): FlowContext
121 var flow
= new FlowContext
123 flow
.node
= current_node
124 flow
.add_previous
(true_flow
)
125 flow
.add_previous
(false_flow
)
126 flow
.when_true
= true_flow
127 flow
.when_false
= false_flow
128 self.current_flow_context
= flow
132 fun make_sub_true_false_flow
: FlowContext
134 var orig_flow
= self.current_flow_context
135 var true_flow
= new FlowContext
137 true_flow
.node
= current_node
138 true_flow
.add_previous
(orig_flow
)
139 true_flow
.name
= "TRUE"
140 var false_flow
= new FlowContext
141 flows
.add
(false_flow
)
142 false_flow
.node
= current_node
143 false_flow
.add_previous
(orig_flow
)
144 false_flow
.name
= "FALSE"
145 return make_true_false_flow
(true_flow
, false_flow
)
148 fun make_unreachable_flow
: FlowContext
150 var flow
= new FlowContext
152 flow
.node
= current_node
153 flow
.add_previous
(self.current_flow_context
)
154 flow
.is_marked_unreachable
= true
155 self.current_flow_context
= flow
159 fun merge_continues_to
(before_loop
: FlowContext, escapemark
: nullable EscapeMark)
161 if escapemark
== null then return
162 for b
in escapemark
.continues
do
163 var before
= b
.before_flow_context
164 if before
== null then continue # Forward error
165 before_loop
.add_loop
(before
)
169 fun merge_breaks
(escapemark
: nullable EscapeMark)
171 if escapemark
== null then return
172 for b
in escapemark
.breaks
do
173 var before
= b
.before_flow_context
174 if before
== null then continue # Forward error
175 self.make_merge_flow
(self.current_flow_context
, before
)
180 # A Node in the static flow graph.
181 # A same FlowContext can be shared by more than one ANode.
183 # The reachable previous flow
184 var previous
: Array[FlowContext] = new Array[FlowContext]
186 # Additional reachable flow that loop up to self.
187 # Loops apears in 'loop', 'while', 'for', closure and with 'continue'
188 var loops
: Array[FlowContext] = new Array[FlowContext]
190 private var is_marked_unreachable
: Bool = false
193 fun is_unreachable
: Bool
195 # Are we explicitely marked unreachable?
196 if self.is_marked_unreachable
then return true
198 # Are we the starting flow context?
199 if is_start
then return false
201 # De we have a reachable previous?
202 if previous
.length
== 0 then return true
206 # Flag to avoid repeaed errors
207 var is_already_unreachable
: Bool = false
209 # Mark that self is the starting flow context.
210 # Such a context is reachable even if there is no previous flow
211 var is_start
: Bool = false
213 # The node that introduce the flow (for debuging)
214 var node
: nullable ANode = null
216 # Additional information for the flor (for debuging)
217 var name
: String = ""
219 # The sub-flow to use if the associated expr is true
220 var when_true
: FlowContext = self
222 # The sub-flow to use if the associated expr is true
223 var when_false
: FlowContext = self
225 # Add a previous flow (iff it is reachable)
226 private fun add_previous
(flow
: FlowContext)
228 if not flow
.is_unreachable
and not previous
.has
(flow
) then
233 # Add a previous loop flow (iff it is reachable)
234 private fun add_loop
(flow
: FlowContext)
236 if not flow
.is_unreachable
and not previous
.has
(flow
) then
244 private fun accept_flow_visitor
(v
: FlowVisitor)
251 # The entry point of the whole flow analysis
252 fun do_flow
(toolcontext
: ToolContext)
254 var v
= new FlowVisitor(toolcontext
)
260 var before_flow_context
: nullable FlowContext
263 var after_flow_context
: nullable FlowContext
265 redef fun accept_flow_visitor
(v
)
267 self.before_flow_context
= v
.current_flow_context
269 self.after_flow_context
= v
.current_flow_context
274 # The flow after the full evaluation of the expression/statement
275 var after_flow_context
: nullable FlowContext
278 redef class AVarAssignExpr
279 redef fun accept_flow_visitor
(v
)
282 self.after_flow_context
= v
.make_sub_flow
286 redef class AReassignFormExpr
287 redef fun accept_flow_visitor
(v
)
290 self.after_flow_context
= v
.make_sub_flow
294 redef class ABlockExpr
295 redef fun accept_flow_visitor
(v
)
298 if not v
.current_flow_context
.is_unreachable
then
300 else if not v
.current_flow_context
.is_already_unreachable
then
301 v
.current_flow_context
.is_already_unreachable
= true
302 v
.toolcontext
.error
(e
.hot_location
, "Error: unreachable statement.")
308 redef class AReturnExpr
309 redef fun accept_flow_visitor
(v
)
312 v
.make_unreachable_flow
316 redef class AContinueExpr
317 # The flow just before it become unreachable
318 fun before_flow_context
: nullable FlowContext
320 var after
= self.after_flow_context
321 if after
== null then return null
322 return after
.previous
.first
324 redef fun accept_flow_visitor
(v
)
327 v
.make_unreachable_flow
331 redef class ABreakExpr
332 # The flow just before it become unreachable
333 fun before_flow_context
: nullable FlowContext
335 var after
= self.after_flow_context
336 if after
== null then return null
337 return after
.previous
.first
339 redef fun accept_flow_visitor
(v
)
342 v
.make_unreachable_flow
346 redef class AAbortExpr
347 redef fun accept_flow_visitor
(v
)
350 v
.make_unreachable_flow
355 redef fun accept_flow_visitor
(v
)
358 v
.merge_breaks
(self.escapemark
)
363 redef fun accept_flow_visitor
(v
)
365 var after_expr
= v
.visit_expr
(self.n_expr
)
367 v
.current_flow_context
= after_expr
.when_true
368 v
.enter_visit
(self.n_then
)
369 var after_then
= v
.current_flow_context
371 v
.current_flow_context
= after_expr
.when_false
372 v
.enter_visit
(self.n_else
)
373 var after_else
= v
.current_flow_context
375 v
.make_merge_flow
(after_then
, after_else
)
379 redef class AIfexprExpr
380 redef fun accept_flow_visitor
(v
)
382 var after_expr
= v
.visit_expr
(self.n_expr
)
384 v
.current_flow_context
= after_expr
.when_true
385 v
.enter_visit
(self.n_then
)
386 var after_then
= v
.current_flow_context
388 v
.current_flow_context
= after_expr
.when_false
389 v
.enter_visit
(self.n_else
)
390 var after_else
= v
.current_flow_context
392 v
.make_merge_flow
(after_then
, after_else
)
396 redef class AWhileExpr
397 redef fun accept_flow_visitor
(v
)
399 var before_loop
= v
.make_sub_flow
401 var after_expr
= v
.visit_expr
(self.n_expr
)
403 v
.current_flow_context
= after_expr
.when_true
404 v
.enter_visit
(self.n_block
)
405 var after_block
= v
.current_flow_context
407 before_loop
.add_loop
(after_block
)
408 v
.merge_continues_to
(after_block
, self.escapemark
)
410 v
.current_flow_context
= after_expr
.when_false
411 v
.merge_breaks
(self.escapemark
)
415 redef class ALoopExpr
416 redef fun accept_flow_visitor
(v
)
418 var before_loop
= v
.make_sub_flow
420 v
.enter_visit
(self.n_block
)
422 var after_block
= v
.current_flow_context
424 before_loop
.add_loop
(after_block
)
425 v
.merge_continues_to
(after_block
, self.escapemark
)
427 v
.make_unreachable_flow
428 v
.merge_breaks
(self.escapemark
)
433 redef fun accept_flow_visitor
(v
)
435 v
.enter_visit
(self.n_expr
)
437 var before_loop
= v
.make_sub_flow
439 v
.enter_visit
(self.n_block
)
441 var after_block
= v
.current_flow_context
443 before_loop
.add_loop
(after_block
)
444 v
.merge_continues_to
(after_block
, self.escapemark
)
446 v
.make_merge_flow
(v
.current_flow_context
, before_loop
)
447 v
.merge_breaks
(self.escapemark
)
451 redef class AAssertExpr
452 redef fun accept_flow_visitor
(v
)
454 var after_expr
= v
.visit_expr
(self.n_expr
)
456 v
.current_flow_context
= after_expr
.when_false
457 v
.enter_visit
(n_else
)
458 # the after context of n_else is a dead end, so we do not care
460 v
.current_flow_context
= after_expr
.when_true
465 redef fun accept_flow_visitor
(v
)
467 var after_expr
= v
.visit_expr
(self.n_expr
)
469 v
.current_flow_context
= after_expr
.when_false
470 var after_expr2
= v
.visit_expr
(self.n_expr2
)
472 var merge_true
= v
.make_merge_flow
(after_expr
.when_true
, after_expr2
.when_true
)
473 merge_true
.name
= "OR TRUE"
475 v
.make_true_false_flow
(merge_true
, after_expr2
.when_false
)
480 redef fun accept_flow_visitor
(v
)
482 var after_expr
= v
.visit_expr
(self.n_expr
)
484 v
.current_flow_context
= after_expr
.when_true
485 var after_expr2
= v
.visit_expr
(self.n_expr2
)
487 var merge_false
= v
.make_merge_flow
(after_expr
.when_false
, after_expr2
.when_false
)
488 merge_false
.name
= "AND FALSE"
490 v
.make_true_false_flow
(after_expr2
.when_true
, merge_false
)
495 redef fun accept_flow_visitor
(v
)
497 var after_expr
= v
.visit_expr
(self.n_expr
)
499 v
.make_true_false_flow
(after_expr
.when_false
, after_expr
.when_true
)
503 redef class AOrElseExpr
504 redef fun accept_flow_visitor
(v
)
511 redef fun accept_flow_visitor
(v
)
514 v
.make_sub_true_false_flow
520 redef fun accept_flow_visitor
(v
)
523 v
.make_sub_true_false_flow
527 redef class AClosureCallExpr
528 redef fun accept_flow_visitor
(v
)
531 # FIXME: break closure call?
532 # v.make_unreachable_flow
536 redef class AClosureDef
537 redef fun accept_flow_visitor
(v
)
539 var before_loop
= v
.make_sub_flow
541 v
.enter_visit
(self.n_expr
)
543 var after_block
= v
.current_flow_context
544 before_loop
.add_loop
(after_block
)
546 v
.make_merge_flow
(v
.current_flow_context
, before_loop
)
551 redef fun accept_flow_visitor
(v
)
554 v
.make_sub_true_false_flow
558 redef class AProxyExpr
559 redef fun accept_flow_visitor
(v
)
561 var after_expr
= v
.visit_expr
(self.n_expr
)
562 v
.current_flow_context
= after_expr