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 # Run `APropdef::do_flow` on each propdef
24 var flow_phase
: Phase = new FlowPhase(self, [scope_phase
])
27 private class FlowPhase
30 redef fun process_npropdef
(npropdef
) do npropdef
.do_flow
(toolcontext
)
33 # The visitor that determine flowcontext for nodes
34 private class FlowVisitor
37 var current_flow_context
= new FlowContext
39 var toolcontext
: ToolContext
43 flows
.add
(current_flow_context
)
44 current_flow_context
.is_start
= true
47 var first
: nullable ANode = null
51 if first
== null then first
= node
53 if current_flow_context
.node
== null then current_flow_context
.node
= node
54 node
.accept_flow_visitor
(self)
55 if node
isa AExpr then
56 var flow
= self.current_flow_context
57 node
.after_flow_context
= flow
58 # Force the creation of a specific merge after the analysis of the node.
59 if flow
.when_true
!= flow
or flow
.when_false
!= flow
then
61 self.current_flow_context
.name
= "AUTOSUB"
70 fun visit_expr
(node
: AExpr): FlowContext
72 self.enter_visit
(node
)
73 return node
.after_flow_context
.as(not null)
76 var flows
= new Array[FlowContext]
80 var file
= new FileWriter.open
("flow.dot")
81 file
.write
("digraph \{\nnode[shape=box];")
84 if f
.node
isa AExpr then
85 s
= "\\nmain={f.node.as(AExpr).after_flow_context.object_id}"
87 file
.write
"F{f.object_id} [label=\"{f.object_id}\\n
{f.node.location}\\n
{f.node.class_name}\\n
{f.name}{s}\
"];\n"
88 for p
in f
.previous
do
90 if f
.when_true
== p
then s
= "[label=TRUE, style=dotted]"
91 if f
.when_false
== p
then s
= "[label=FALSE, style=dotted]"
92 if f
.when_true
== p
and f
.when_false
== p
then s
= "[label=TRUE_FALSE, style=dotted]"
93 file
.write
"F{p.object_id} -> F{f.object_id}{s};\n"
96 file
.write
"F{p.object_id} -> F{f.object_id}[label=LOOP, style=dashed, constraint=false];\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
.escapes
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
.escapes
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 is noautoinit
269 var after_flow_context
: nullable FlowContext is noautoinit
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 AEscapeExpr
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 AAbortExpr
338 redef fun accept_flow_visitor
(v
)
341 v
.make_unreachable_flow
346 redef fun accept_flow_visitor
(v
)
348 # FlowContext before the block
349 var before_block
= v
.make_sub_flow
351 # Visit the bloc, then merge the breaks
352 v
.enter_visit
(self.n_block
)
353 v
.merge_breaks
(self.break_mark
)
354 var after_block
= v
.current_flow_context
356 # Visit the catch if there is one
357 if self.n_catch
!= null then
358 var before_catch
= v
.make_sub_flow
359 v
.make_merge_flow
(before_block
, after_block
)
360 v
.enter_visit
(self.n_catch
)
361 var after_catch
= v
.current_flow_context
362 v
.make_merge_flow
(before_catch
, after_catch
)
368 redef fun accept_flow_visitor
(v
)
370 var after_expr
= v
.visit_expr
(self.n_expr
)
372 v
.current_flow_context
= after_expr
.when_true
373 v
.enter_visit
(self.n_then
)
374 var after_then
= v
.current_flow_context
376 v
.current_flow_context
= after_expr
.when_false
377 v
.enter_visit
(self.n_else
)
378 var after_else
= v
.current_flow_context
380 v
.make_merge_flow
(after_then
, after_else
)
384 redef class AIfexprExpr
385 redef fun accept_flow_visitor
(v
)
387 var after_expr
= v
.visit_expr
(self.n_expr
)
389 v
.current_flow_context
= after_expr
.when_true
390 v
.enter_visit
(self.n_then
)
391 var after_then
= v
.current_flow_context
393 v
.current_flow_context
= after_expr
.when_false
394 v
.enter_visit
(self.n_else
)
395 var after_else
= v
.current_flow_context
397 v
.make_merge_flow
(after_then
, after_else
)
401 redef class AWhileExpr
402 redef fun accept_flow_visitor
(v
)
404 var before_loop
= v
.make_sub_flow
406 var after_expr
= v
.visit_expr
(self.n_expr
)
408 v
.current_flow_context
= after_expr
.when_true
409 v
.enter_visit
(self.n_block
)
410 var after_block
= v
.current_flow_context
412 before_loop
.add_loop
(after_block
)
413 v
.merge_continues_to
(before_loop
, self.continue_mark
)
415 v
.current_flow_context
= after_expr
.when_false
416 v
.merge_breaks
(self.break_mark
)
420 redef class ALoopExpr
421 redef fun accept_flow_visitor
(v
)
423 var before_loop
= v
.make_sub_flow
425 v
.enter_visit
(self.n_block
)
427 var after_block
= v
.current_flow_context
429 before_loop
.add_loop
(after_block
)
430 v
.merge_continues_to
(before_loop
, self.continue_mark
)
432 v
.make_unreachable_flow
433 v
.merge_breaks
(self.break_mark
)
438 redef fun accept_flow_visitor
(v
)
441 v
.enter_visit
(g
.n_expr
)
444 var before_loop
= v
.make_sub_flow
446 v
.enter_visit
(self.n_block
)
448 var after_block
= v
.current_flow_context
450 before_loop
.add_loop
(after_block
)
451 v
.merge_continues_to
(before_loop
, self.continue_mark
)
453 v
.make_merge_flow
(v
.current_flow_context
, before_loop
)
454 v
.merge_breaks
(self.break_mark
)
458 redef class AWithExpr
459 redef fun accept_flow_visitor
(v
)
462 v
.merge_breaks
(self.break_mark
)
466 redef class AAssertExpr
467 redef fun accept_flow_visitor
(v
)
469 var after_expr
= v
.visit_expr
(self.n_expr
)
471 v
.current_flow_context
= after_expr
.when_false
472 v
.enter_visit
(n_else
)
473 # the after context of n_else is a dead end, so we do not care
475 v
.current_flow_context
= after_expr
.when_true
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_false
485 var after_expr2
= v
.visit_expr
(self.n_expr2
)
487 var merge_true
= v
.make_merge_flow
(after_expr
.when_true
, after_expr2
.when_true
)
488 merge_true
.name
= "OR TRUE"
490 v
.make_true_false_flow
(merge_true
, after_expr2
.when_false
)
494 redef class AImpliesExpr
495 redef fun accept_flow_visitor
(v
)
497 var after_expr
= v
.visit_expr
(self.n_expr
)
499 v
.current_flow_context
= after_expr
.when_true
500 var after_expr2
= v
.visit_expr
(self.n_expr2
)
502 var merge_true
= v
.make_merge_flow
(after_expr
.when_false
, after_expr2
.when_true
)
503 merge_true
.name
= "OR TRUE"
505 v
.make_true_false_flow
(merge_true
, after_expr2
.when_false
)
510 redef fun accept_flow_visitor
(v
)
512 var after_expr
= v
.visit_expr
(self.n_expr
)
514 v
.current_flow_context
= after_expr
.when_true
515 var after_expr2
= v
.visit_expr
(self.n_expr2
)
517 var merge_false
= v
.make_merge_flow
(after_expr
.when_false
, after_expr2
.when_false
)
518 merge_false
.name
= "AND FALSE"
520 v
.make_true_false_flow
(after_expr2
.when_true
, merge_false
)
525 redef fun accept_flow_visitor
(v
)
527 var after_expr
= v
.visit_expr
(self.n_expr
)
529 v
.make_true_false_flow
(after_expr
.when_false
, after_expr
.when_true
)
533 redef class AOrElseExpr
534 redef fun accept_flow_visitor
(v
)
541 redef fun accept_flow_visitor
(v
)
544 v
.make_sub_true_false_flow
550 redef fun accept_flow_visitor
(v
)
553 v
.make_sub_true_false_flow
558 redef fun accept_flow_visitor
(v
)
561 v
.make_sub_true_false_flow
566 redef fun accept_flow_visitor
(v
)
568 var after_expr
= v
.visit_expr
(self.n_expr
)
569 v
.current_flow_context
= after_expr
573 redef class AOnceExpr
574 redef fun accept_flow_visitor
(v
)
576 var after_expr
= v
.visit_expr
(self.n_expr
)
577 v
.current_flow_context
= after_expr