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
56 if first
== null then first
= node
58 if current_flow_context
.node
== null then current_flow_context
.node
= node
59 node
.accept_flow_visitor
(self)
60 if node
isa AExpr then
61 var flow
= self.current_flow_context
62 node
.after_flow_context
= flow
63 # Force the creation of a specific merge after the analysis of the node.
64 if flow
.when_true
!= flow
or flow
.when_false
!= flow
then
66 self.current_flow_context
.name
= "AUTOSUB"
76 fun visit_expr
(node
: AExpr): FlowContext
78 self.enter_visit
(node
)
79 return node
.after_flow_context
.as(not null)
82 var flows
: Array[FlowContext] = new Array[FlowContext]
86 var file
= new OFStream.open
("flow.dot")
87 file
.write
("digraph \{\n")
90 if f
.node
isa AExpr then
91 s
= "\\nmain={f.node.as(AExpr).after_flow_context.object_id}"
93 file
.write
"F{f.object_id} [label=\"{f.object_id}\\n
{f.node.location}\\n
{f.node.class_name}\\n
{f.name}{s}\
"];\n"
94 for p
in f
.previous
do
95 file
.write
"F{p.object_id} -> F{f.object_id};\n"
97 if f
.when_true
!= f
then
98 file
.write
"F{f.object_id} -> F{f.when_true.object_id}[label=TRUE, style=dotted];\n"
100 if f
.when_false
!= f
then
101 file
.write
"F{f.object_id} -> F{f.when_false.object_id}[label=FALSE,style=dotted];\n"
109 fun make_sub_flow
: FlowContext
111 var flow
= new FlowContext
113 flow
.node
= current_node
114 flow
.add_previous
(self.current_flow_context
)
115 self.current_flow_context
= flow
119 fun make_merge_flow
(flow1
, flow2
: FlowContext): FlowContext
121 var flow
= new FlowContext
123 flow
.node
= current_node
124 flow
.add_previous
(flow1
)
125 flow
.add_previous
(flow2
)
126 self.current_flow_context
= flow
130 fun make_true_false_flow
(true_flow
, false_flow
: FlowContext): FlowContext
132 var flow
= new FlowContext
134 flow
.node
= current_node
135 flow
.add_previous
(true_flow
)
136 flow
.add_previous
(false_flow
)
137 flow
.when_true
= true_flow
138 flow
.when_false
= false_flow
139 self.current_flow_context
= flow
143 fun make_sub_true_false_flow
: FlowContext
145 var orig_flow
= self.current_flow_context
146 var true_flow
= new FlowContext
148 true_flow
.node
= current_node
149 true_flow
.add_previous
(orig_flow
)
150 true_flow
.name
= "TRUE"
151 var false_flow
= new FlowContext
152 flows
.add
(false_flow
)
153 false_flow
.node
= current_node
154 false_flow
.add_previous
(orig_flow
)
155 false_flow
.name
= "FALSE"
156 return make_true_false_flow
(true_flow
, false_flow
)
159 fun make_unreachable_flow
: FlowContext
161 var flow
= new FlowContext
163 flow
.node
= current_node
164 flow
.add_previous
(self.current_flow_context
)
165 flow
.is_marked_unreachable
= true
166 self.current_flow_context
= flow
170 fun merge_continues_to
(before_loop
: FlowContext, escapemark
: nullable EscapeMark)
172 if escapemark
== null then return
173 for b
in escapemark
.continues
do
174 var before
= b
.before_flow_context
175 if before
== null then continue # Forward error
176 before_loop
.add_loop
(before
)
180 fun merge_breaks
(escapemark
: nullable EscapeMark)
182 if escapemark
== null then return
183 for b
in escapemark
.breaks
do
184 var before
= b
.before_flow_context
185 if before
== null then continue # Forward error
186 self.make_merge_flow
(self.current_flow_context
, before
)
191 # A Node in the static flow graph.
192 # A same FlowContext can be shared by more than one ANode.
194 # The reachable previous flow
195 var previous
: Array[FlowContext] = new Array[FlowContext]
197 # Additional reachable flow that loop up to self.
198 # Loops apears in 'loop', 'while', 'for', closure and with 'continue'
199 var loops
: Array[FlowContext] = new Array[FlowContext]
201 private var is_marked_unreachable
: Bool = false
204 fun is_unreachable
: Bool
206 # Are we explicitely marked unreachable?
207 if self.is_marked_unreachable
then return true
209 # Are we the starting flow context?
210 if is_start
then return false
212 # De we have a reachable previous?
213 if previous
.length
== 0 then return true
217 # Flag to avoid repeaed errors
218 var is_already_unreachable
: Bool = false
220 # Mark that self is the starting flow context.
221 # Such a context is reachable even if there is no previous flow
222 var is_start
: Bool = false
224 # The node that introduce the flow (for debuging)
225 var node
: nullable ANode = null
227 # Additional information for the flor (for debuging)
228 var name
: String = ""
230 # The sub-flow to use if the associated expr is true
231 var when_true
: FlowContext = self
233 # The sub-flow to use if the associated expr is true
234 var when_false
: FlowContext = self
236 # Add a previous flow (iff it is reachable)
237 private fun add_previous
(flow
: FlowContext)
239 if not flow
.is_unreachable
and not previous
.has
(flow
) then
244 # Add a previous loop flow (iff it is reachable)
245 private fun add_loop
(flow
: FlowContext)
247 if not flow
.is_unreachable
and not previous
.has
(flow
) then
255 private fun accept_flow_visitor
(v
: FlowVisitor)
262 # The entry point of the whole flow analysis
263 fun do_flow
(toolcontext
: ToolContext)
265 var v
= new FlowVisitor(toolcontext
)
271 var before_flow_context
: nullable FlowContext
274 var after_flow_context
: nullable FlowContext
276 redef fun accept_flow_visitor
(v
)
278 self.before_flow_context
= v
.current_flow_context
280 self.after_flow_context
= v
.current_flow_context
285 # The flow after the full evaluation of the expression/statement
286 var after_flow_context
: nullable FlowContext
289 redef class AVarAssignExpr
290 redef fun accept_flow_visitor
(v
)
293 self.after_flow_context
= v
.make_sub_flow
297 redef class AReassignFormExpr
298 redef fun accept_flow_visitor
(v
)
301 self.after_flow_context
= v
.make_sub_flow
305 redef class ABlockExpr
306 redef fun accept_flow_visitor
(v
)
309 if not v
.current_flow_context
.is_unreachable
then
311 else if not v
.current_flow_context
.is_already_unreachable
then
312 v
.current_flow_context
.is_already_unreachable
= true
313 v
.toolcontext
.error
(e
.hot_location
, "Error: unreachable statement.")
319 redef class AReturnExpr
320 redef fun accept_flow_visitor
(v
)
323 v
.make_unreachable_flow
327 redef class AContinueExpr
328 # The flow just before it become unreachable
329 fun before_flow_context
: nullable FlowContext
331 var after
= self.after_flow_context
332 if after
== null then return null
333 return after
.previous
.first
335 redef fun accept_flow_visitor
(v
)
338 v
.make_unreachable_flow
342 redef class ABreakExpr
343 # The flow just before it become unreachable
344 fun before_flow_context
: nullable FlowContext
346 var after
= self.after_flow_context
347 if after
== null then return null
348 return after
.previous
.first
350 redef fun accept_flow_visitor
(v
)
353 v
.make_unreachable_flow
357 redef class AAbortExpr
358 redef fun accept_flow_visitor
(v
)
361 v
.make_unreachable_flow
366 redef fun accept_flow_visitor
(v
)
369 v
.merge_breaks
(self.escapemark
)
374 redef fun accept_flow_visitor
(v
)
376 var after_expr
= v
.visit_expr
(self.n_expr
)
378 v
.current_flow_context
= after_expr
.when_true
379 v
.enter_visit
(self.n_then
)
380 var after_then
= v
.current_flow_context
382 v
.current_flow_context
= after_expr
.when_false
383 v
.enter_visit
(self.n_else
)
384 var after_else
= v
.current_flow_context
386 v
.make_merge_flow
(after_then
, after_else
)
390 redef class AIfexprExpr
391 redef fun accept_flow_visitor
(v
)
393 var after_expr
= v
.visit_expr
(self.n_expr
)
395 v
.current_flow_context
= after_expr
.when_true
396 v
.enter_visit
(self.n_then
)
397 var after_then
= v
.current_flow_context
399 v
.current_flow_context
= after_expr
.when_false
400 v
.enter_visit
(self.n_else
)
401 var after_else
= v
.current_flow_context
403 v
.make_merge_flow
(after_then
, after_else
)
407 redef class AWhileExpr
408 redef fun accept_flow_visitor
(v
)
410 var before_loop
= v
.make_sub_flow
412 var after_expr
= v
.visit_expr
(self.n_expr
)
414 v
.current_flow_context
= after_expr
.when_true
415 v
.enter_visit
(self.n_block
)
416 var after_block
= v
.current_flow_context
418 before_loop
.add_loop
(after_block
)
419 v
.merge_continues_to
(after_block
, self.escapemark
)
421 v
.current_flow_context
= after_expr
.when_false
422 v
.merge_breaks
(self.escapemark
)
426 redef class ALoopExpr
427 redef fun accept_flow_visitor
(v
)
429 var before_loop
= v
.make_sub_flow
431 v
.enter_visit
(self.n_block
)
433 var after_block
= v
.current_flow_context
435 before_loop
.add_loop
(after_block
)
436 v
.merge_continues_to
(after_block
, self.escapemark
)
438 v
.make_unreachable_flow
439 v
.merge_breaks
(self.escapemark
)
444 redef fun accept_flow_visitor
(v
)
446 v
.enter_visit
(self.n_expr
)
448 var before_loop
= v
.make_sub_flow
450 v
.enter_visit
(self.n_block
)
452 var after_block
= v
.current_flow_context
454 before_loop
.add_loop
(after_block
)
455 v
.merge_continues_to
(after_block
, self.escapemark
)
457 v
.make_merge_flow
(v
.current_flow_context
, before_loop
)
458 v
.merge_breaks
(self.escapemark
)
462 redef class AAssertExpr
463 redef fun accept_flow_visitor
(v
)
465 var after_expr
= v
.visit_expr
(self.n_expr
)
467 v
.current_flow_context
= after_expr
.when_false
468 v
.enter_visit
(n_else
)
469 # the after context of n_else is a dead end, so we do not care
471 v
.current_flow_context
= after_expr
.when_true
476 redef fun accept_flow_visitor
(v
)
478 var after_expr
= v
.visit_expr
(self.n_expr
)
480 v
.current_flow_context
= after_expr
.when_false
481 var after_expr2
= v
.visit_expr
(self.n_expr2
)
483 var merge_true
= v
.make_merge_flow
(after_expr
.when_true
, after_expr2
.when_true
)
484 merge_true
.name
= "OR TRUE"
486 v
.make_true_false_flow
(merge_true
, after_expr2
.when_false
)
491 redef fun accept_flow_visitor
(v
)
493 var after_expr
= v
.visit_expr
(self.n_expr
)
495 v
.current_flow_context
= after_expr
.when_true
496 var after_expr2
= v
.visit_expr
(self.n_expr2
)
498 var merge_false
= v
.make_merge_flow
(after_expr
.when_false
, after_expr2
.when_false
)
499 merge_false
.name
= "AND FALSE"
501 v
.make_true_false_flow
(after_expr2
.when_true
, merge_false
)
506 redef fun accept_flow_visitor
(v
)
508 var after_expr
= v
.visit_expr
(self.n_expr
)
510 v
.make_true_false_flow
(after_expr
.when_false
, after_expr
.when_true
)
514 redef class AOrElseExpr
515 redef fun accept_flow_visitor
(v
)
522 redef fun accept_flow_visitor
(v
)
525 v
.make_sub_true_false_flow
531 redef fun accept_flow_visitor
(v
)
534 v
.make_sub_true_false_flow
538 redef class AClosureCallExpr
539 redef fun accept_flow_visitor
(v
)
542 # FIXME: break closure call?
543 # v.make_unreachable_flow
547 redef class AClosureDef
548 redef fun accept_flow_visitor
(v
)
550 var before_loop
= v
.make_sub_flow
552 v
.enter_visit
(self.n_expr
)
554 var after_block
= v
.current_flow_context
555 before_loop
.add_loop
(after_block
)
557 v
.make_merge_flow
(v
.current_flow_context
, before_loop
)
562 redef fun accept_flow_visitor
(v
)
565 v
.make_sub_true_false_flow
569 redef class AProxyExpr
570 redef fun accept_flow_visitor
(v
)
572 var after_expr
= v
.visit_expr
(self.n_expr
)
573 v
.current_flow_context
= after_expr