1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 use rustc_data_structures
::graph
;
15 use ty
::{self, TyCtxt}
;
19 use hir
::{self, PatKind}
;
21 struct CFGBuilder
<'a
, 'tcx
: 'a
> {
22 tcx
: &'a TyCtxt
<'tcx
>,
25 loop_scopes
: Vec
<LoopScope
>,
28 #[derive(Copy, Clone)]
30 loop_id
: ast
::NodeId
, // id of loop/while node
31 continue_index
: CFGIndex
, // where to go on a `loop`
32 break_index
: CFGIndex
, // where to go on a `break
35 pub fn construct(tcx
: &TyCtxt
,
36 blk
: &hir
::Block
) -> CFG
{
37 let mut graph
= graph
::Graph
::new();
38 let entry
= graph
.add_node(CFGNodeData
::Entry
);
40 // `fn_exit` is target of return exprs, which lies somewhere
41 // outside input `blk`. (Distinguishing `fn_exit` and `block_exit`
42 // also resolves chicken-and-egg problem that arises if you try to
43 // have return exprs jump to `block_exit` during construction.)
44 let fn_exit
= graph
.add_node(CFGNodeData
::Exit
);
47 let mut cfg_builder
= CFGBuilder
{
51 loop_scopes
: Vec
::new()
53 block_exit
= cfg_builder
.block(blk
, entry
);
54 cfg_builder
.add_contained_edge(block_exit
, fn_exit
);
55 let CFGBuilder {graph, ..}
= cfg_builder
;
61 impl<'a
, 'tcx
> CFGBuilder
<'a
, 'tcx
> {
62 fn block(&mut self, blk
: &hir
::Block
, pred
: CFGIndex
) -> CFGIndex
{
63 let mut stmts_exit
= pred
;
64 for stmt
in &blk
.stmts
{
65 stmts_exit
= self.stmt(stmt
, stmts_exit
);
68 let expr_exit
= self.opt_expr(&blk
.expr
, stmts_exit
);
70 self.add_ast_node(blk
.id
, &[expr_exit
])
73 fn stmt(&mut self, stmt
: &hir
::Stmt
, pred
: CFGIndex
) -> CFGIndex
{
75 hir
::StmtDecl(ref decl
, id
) => {
76 let exit
= self.decl(&decl
, pred
);
77 self.add_ast_node(id
, &[exit
])
80 hir
::StmtExpr(ref expr
, id
) | hir
::StmtSemi(ref expr
, id
) => {
81 let exit
= self.expr(&expr
, pred
);
82 self.add_ast_node(id
, &[exit
])
87 fn decl(&mut self, decl
: &hir
::Decl
, pred
: CFGIndex
) -> CFGIndex
{
89 hir
::DeclLocal(ref local
) => {
90 let init_exit
= self.opt_expr(&local
.init
, pred
);
91 self.pat(&local
.pat
, init_exit
)
100 fn pat(&mut self, pat
: &hir
::Pat
, pred
: CFGIndex
) -> CFGIndex
{
102 PatKind
::Ident(_
, _
, None
) |
103 PatKind
::TupleStruct(_
, None
) |
109 self.add_ast_node(pat
.id
, &[pred
])
112 PatKind
::Box(ref subpat
) |
113 PatKind
::Ref(ref subpat
, _
) |
114 PatKind
::Ident(_
, _
, Some(ref subpat
)) => {
115 let subpat_exit
= self.pat(&subpat
, pred
);
116 self.add_ast_node(pat
.id
, &[subpat_exit
])
119 PatKind
::TupleStruct(_
, Some(ref subpats
)) |
120 PatKind
::Tup(ref subpats
) => {
121 let pats_exit
= self.pats_all(subpats
.iter(), pred
);
122 self.add_ast_node(pat
.id
, &[pats_exit
])
125 PatKind
::Struct(_
, ref subpats
, _
) => {
127 self.pats_all(subpats
.iter().map(|f
| &f
.node
.pat
), pred
);
128 self.add_ast_node(pat
.id
, &[pats_exit
])
131 PatKind
::Vec(ref pre
, ref vec
, ref post
) => {
132 let pre_exit
= self.pats_all(pre
.iter(), pred
);
133 let vec_exit
= self.pats_all(vec
.iter(), pre_exit
);
134 let post_exit
= self.pats_all(post
.iter(), vec_exit
);
135 self.add_ast_node(pat
.id
, &[post_exit
])
140 fn pats_all
<'b
, I
: Iterator
<Item
=&'b P
<hir
::Pat
>>>(&mut self,
142 pred
: CFGIndex
) -> CFGIndex
{
143 //! Handles case where all of the patterns must match.
144 pats
.fold(pred
, |pred
, pat
| self.pat(&pat
, pred
))
147 fn expr(&mut self, expr
: &hir
::Expr
, pred
: CFGIndex
) -> CFGIndex
{
149 hir
::ExprBlock(ref blk
) => {
150 let blk_exit
= self.block(&blk
, pred
);
151 self.add_ast_node(expr
.id
, &[blk_exit
])
154 hir
::ExprIf(ref cond
, ref then
, None
) => {
169 let cond_exit
= self.expr(&cond
, pred
); // 1
170 let then_exit
= self.block(&then
, cond_exit
); // 2
171 self.add_ast_node(expr
.id
, &[cond_exit
, then_exit
]) // 3,4
174 hir
::ExprIf(ref cond
, ref then
, Some(ref otherwise
)) => {
189 let cond_exit
= self.expr(&cond
, pred
); // 1
190 let then_exit
= self.block(&then
, cond_exit
); // 2
191 let else_exit
= self.expr(&otherwise
, cond_exit
); // 3
192 self.add_ast_node(expr
.id
, &[then_exit
, else_exit
]) // 4, 5
195 hir
::ExprWhile(ref cond
, ref body
, _
) => {
210 // Note that `break` and `continue` statements
211 // may cause additional edges.
213 // Is the condition considered part of the loop?
214 let loopback
= self.add_dummy_node(&[pred
]); // 1
215 let cond_exit
= self.expr(&cond
, loopback
); // 2
216 let expr_exit
= self.add_ast_node(expr
.id
, &[cond_exit
]); // 3
217 self.loop_scopes
.push(LoopScope
{
219 continue_index
: loopback
,
220 break_index
: expr_exit
222 let body_exit
= self.block(&body
, cond_exit
); // 4
223 self.add_contained_edge(body_exit
, loopback
); // 5
224 self.loop_scopes
.pop();
228 hir
::ExprLoop(ref body
, _
) => {
240 // Note that `break` and `loop` statements
241 // may cause additional edges.
243 let loopback
= self.add_dummy_node(&[pred
]); // 1
244 let expr_exit
= self.add_ast_node(expr
.id
, &[]); // 2
245 self.loop_scopes
.push(LoopScope
{
247 continue_index
: loopback
,
248 break_index
: expr_exit
,
250 let body_exit
= self.block(&body
, loopback
); // 3
251 self.add_contained_edge(body_exit
, loopback
); // 4
252 self.loop_scopes
.pop();
256 hir
::ExprMatch(ref discr
, ref arms
, _
) => {
257 self.match_(expr
.id
, &discr
, &arms
, pred
)
260 hir
::ExprBinary(op
, ref l
, ref r
) if op
.node
.is_lazy() => {
275 let l_exit
= self.expr(&l
, pred
); // 1
276 let r_exit
= self.expr(&r
, l_exit
); // 2
277 self.add_ast_node(expr
.id
, &[l_exit
, r_exit
]) // 3,4
280 hir
::ExprRet(ref v
) => {
281 let v_exit
= self.opt_expr(v
, pred
);
282 let b
= self.add_ast_node(expr
.id
, &[v_exit
]);
283 self.add_returning_edge(expr
, b
);
284 self.add_unreachable_node()
287 hir
::ExprBreak(label
) => {
288 let loop_scope
= self.find_scope(expr
, label
.map(|l
| l
.node
.name
));
289 let b
= self.add_ast_node(expr
.id
, &[pred
]);
290 self.add_exiting_edge(expr
, b
,
291 loop_scope
, loop_scope
.break_index
);
292 self.add_unreachable_node()
295 hir
::ExprAgain(label
) => {
296 let loop_scope
= self.find_scope(expr
, label
.map(|l
| l
.node
.name
));
297 let a
= self.add_ast_node(expr
.id
, &[pred
]);
298 self.add_exiting_edge(expr
, a
,
299 loop_scope
, loop_scope
.continue_index
);
300 self.add_unreachable_node()
303 hir
::ExprVec(ref elems
) => {
304 self.straightline(expr
, pred
, elems
.iter().map(|e
| &**e
))
307 hir
::ExprCall(ref func
, ref args
) => {
308 self.call(expr
, pred
, &func
, args
.iter().map(|e
| &**e
))
311 hir
::ExprMethodCall(_
, _
, ref args
) => {
312 self.call(expr
, pred
, &args
[0], args
[1..].iter().map(|e
| &**e
))
315 hir
::ExprIndex(ref l
, ref r
) |
316 hir
::ExprBinary(_
, ref l
, ref r
) if self.tcx
.is_method_call(expr
.id
) => {
317 self.call(expr
, pred
, &l
, Some(&**r
).into_iter())
320 hir
::ExprUnary(_
, ref e
) if self.tcx
.is_method_call(expr
.id
) => {
321 self.call(expr
, pred
, &e
, None
::<hir
::Expr
>.iter())
324 hir
::ExprTup(ref exprs
) => {
325 self.straightline(expr
, pred
, exprs
.iter().map(|e
| &**e
))
328 hir
::ExprStruct(_
, ref fields
, ref base
) => {
329 let field_cfg
= self.straightline(expr
, pred
, fields
.iter().map(|f
| &*f
.expr
));
330 self.opt_expr(base
, field_cfg
)
333 hir
::ExprRepeat(ref elem
, ref count
) => {
334 self.straightline(expr
, pred
, [elem
, count
].iter().map(|&e
| &**e
))
337 hir
::ExprAssign(ref l
, ref r
) |
338 hir
::ExprAssignOp(_
, ref l
, ref r
) => {
339 self.straightline(expr
, pred
, [r
, l
].iter().map(|&e
| &**e
))
342 hir
::ExprIndex(ref l
, ref r
) |
343 hir
::ExprBinary(_
, ref l
, ref r
) => { // NB: && and || handled earlier
344 self.straightline(expr
, pred
, [l
, r
].iter().map(|&e
| &**e
))
347 hir
::ExprBox(ref e
) |
348 hir
::ExprAddrOf(_
, ref e
) |
349 hir
::ExprCast(ref e
, _
) |
350 hir
::ExprType(ref e
, _
) |
351 hir
::ExprUnary(_
, ref e
) |
352 hir
::ExprField(ref e
, _
) |
353 hir
::ExprTupField(ref e
, _
) => {
354 self.straightline(expr
, pred
, Some(&**e
).into_iter())
357 hir
::ExprInlineAsm(_
, ref outputs
, ref inputs
) => {
358 let post_outputs
= self.exprs(outputs
.iter().map(|e
| &**e
), pred
);
359 let post_inputs
= self.exprs(inputs
.iter().map(|e
| &**e
), post_outputs
);
360 self.add_ast_node(expr
.id
, &[post_inputs
])
363 hir
::ExprClosure(..) |
365 hir
::ExprPath(..) => {
366 self.straightline(expr
, pred
, None
::<hir
::Expr
>.iter())
371 fn call
<'b
, I
: Iterator
<Item
=&'b hir
::Expr
>>(&mut self,
372 call_expr
: &hir
::Expr
,
374 func_or_rcvr
: &hir
::Expr
,
375 args
: I
) -> CFGIndex
{
376 let method_call
= ty
::MethodCall
::expr(call_expr
.id
);
377 let fn_ty
= match self.tcx
.tables
.borrow().method_map
.get(&method_call
) {
378 Some(method
) => method
.ty
,
379 None
=> self.tcx
.expr_ty_adjusted(func_or_rcvr
)
382 let func_or_rcvr_exit
= self.expr(func_or_rcvr
, pred
);
383 let ret
= self.straightline(call_expr
, func_or_rcvr_exit
, args
);
384 if fn_ty
.fn_ret().diverges() {
385 self.add_unreachable_node()
391 fn exprs
<'b
, I
: Iterator
<Item
=&'b hir
::Expr
>>(&mut self,
393 pred
: CFGIndex
) -> CFGIndex
{
394 //! Constructs graph for `exprs` evaluated in order
395 exprs
.fold(pred
, |p
, e
| self.expr(e
, p
))
398 fn opt_expr(&mut self,
399 opt_expr
: &Option
<P
<hir
::Expr
>>,
400 pred
: CFGIndex
) -> CFGIndex
{
401 //! Constructs graph for `opt_expr` evaluated, if Some
402 opt_expr
.iter().fold(pred
, |p
, e
| self.expr(&e
, p
))
405 fn straightline
<'b
, I
: Iterator
<Item
=&'b hir
::Expr
>>(&mut self,
408 subexprs
: I
) -> CFGIndex
{
409 //! Handles case of an expression that evaluates `subexprs` in order
411 let subexprs_exit
= self.exprs(subexprs
, pred
);
412 self.add_ast_node(expr
.id
, &[subexprs_exit
])
415 fn match_(&mut self, id
: ast
::NodeId
, discr
: &hir
::Expr
,
416 arms
: &[hir
::Arm
], pred
: CFGIndex
) -> CFGIndex
{
417 // The CFG for match expression is quite complex, so no ASCII
420 // The CFG generated below matches roughly what trans puts
421 // out. Each pattern and guard is visited in parallel, with
422 // arms containing multiple patterns generating multiple nodes
423 // for the same guard expression. The guard expressions chain
424 // into each other from top to bottom, with a specific
425 // exception to allow some additional valid programs
426 // (explained below). Trans differs slightly in that the
427 // pattern matching may continue after a guard but the visible
428 // behaviour should be the same.
430 // What is going on is explained in further comments.
432 // Visit the discriminant expression
433 let discr_exit
= self.expr(discr
, pred
);
435 // Add a node for the exit of the match expression as a whole.
436 let expr_exit
= self.add_ast_node(id
, &[]);
438 // Keep track of the previous guard expressions
439 let mut prev_guards
= Vec
::new();
440 // Track if the previous pattern contained bindings or wildcards
441 let mut prev_has_bindings
= false;
444 // Add an exit node for when we've visited all the
445 // patterns and the guard (if there is one) in the arm.
446 let arm_exit
= self.add_dummy_node(&[]);
448 for pat
in &arm
.pats
{
449 // Visit the pattern, coming from the discriminant exit
450 let mut pat_exit
= self.pat(&pat
, discr_exit
);
452 // If there is a guard expression, handle it here
453 if let Some(ref guard
) = arm
.guard
{
454 // Add a dummy node for the previous guard
455 // expression to target
456 let guard_start
= self.add_dummy_node(&[pat_exit
]);
457 // Visit the guard expression
458 let guard_exit
= self.expr(&guard
, guard_start
);
460 let this_has_bindings
= pat_util
::pat_contains_bindings_or_wild(
461 &self.tcx
.def_map
.borrow(), &pat
);
463 // If both this pattern and the previous pattern
464 // were free of bindings, they must consist only
465 // of "constant" patterns. Note we cannot match an
466 // all-constant pattern, fail the guard, and then
467 // match *another* all-constant pattern. This is
468 // because if the previous pattern matches, then
469 // we *cannot* match this one, unless all the
470 // constants are the same (which is rejected by
473 // We can use this to be smarter about the flow
474 // along guards. If the previous pattern matched,
475 // then we know we will not visit the guard in
476 // this one (whether or not the guard succeeded),
477 // if the previous pattern failed, then we know
478 // the guard for that pattern will not have been
479 // visited. Thus, it is not possible to visit both
480 // the previous guard and the current one when
481 // both patterns consist only of constant
484 // However, if the above does not hold, then all
485 // previous guards need to be wired to visit the
486 // current guard pattern.
487 if prev_has_bindings
|| this_has_bindings
{
488 while let Some(prev
) = prev_guards
.pop() {
489 self.add_contained_edge(prev
, guard_start
);
493 prev_has_bindings
= this_has_bindings
;
495 // Push the guard onto the list of previous guards
496 prev_guards
.push(guard_exit
);
498 // Update the exit node for the pattern
499 pat_exit
= guard_exit
;
502 // Add an edge from the exit of this pattern to the
504 self.add_contained_edge(pat_exit
, arm_exit
);
507 // Visit the body of this arm
508 let body_exit
= self.expr(&arm
.body
, arm_exit
);
510 // Link the body to the exit of the expression
511 self.add_contained_edge(body_exit
, expr_exit
);
517 fn add_dummy_node(&mut self, preds
: &[CFGIndex
]) -> CFGIndex
{
518 self.add_node(CFGNodeData
::Dummy
, preds
)
521 fn add_ast_node(&mut self, id
: ast
::NodeId
, preds
: &[CFGIndex
]) -> CFGIndex
{
522 assert
!(id
!= ast
::DUMMY_NODE_ID
);
523 self.add_node(CFGNodeData
::AST(id
), preds
)
526 fn add_unreachable_node(&mut self) -> CFGIndex
{
527 self.add_node(CFGNodeData
::Unreachable
, &[])
530 fn add_node(&mut self, data
: CFGNodeData
, preds
: &[CFGIndex
]) -> CFGIndex
{
531 let node
= self.graph
.add_node(data
);
533 self.add_contained_edge(pred
, node
);
538 fn add_contained_edge(&mut self,
541 let data
= CFGEdgeData {exiting_scopes: vec!() }
;
542 self.graph
.add_edge(source
, target
, data
);
545 fn add_exiting_edge(&mut self,
546 from_expr
: &hir
::Expr
,
547 from_index
: CFGIndex
,
549 to_index
: CFGIndex
) {
550 let mut data
= CFGEdgeData {exiting_scopes: vec!() }
;
551 let mut scope
= self.tcx
.region_maps
.node_extent(from_expr
.id
);
552 let target_scope
= self.tcx
.region_maps
.node_extent(to_loop
.loop_id
);
553 while scope
!= target_scope
{
554 data
.exiting_scopes
.push(scope
.node_id(&self.tcx
.region_maps
));
555 scope
= self.tcx
.region_maps
.encl_scope(scope
);
557 self.graph
.add_edge(from_index
, to_index
, data
);
560 fn add_returning_edge(&mut self,
561 _from_expr
: &hir
::Expr
,
562 from_index
: CFGIndex
) {
563 let mut data
= CFGEdgeData
{
564 exiting_scopes
: vec
!(),
566 for &LoopScope { loop_id: id, .. }
in self.loop_scopes
.iter().rev() {
567 data
.exiting_scopes
.push(id
);
569 self.graph
.add_edge(from_index
, self.fn_exit
, data
);
574 label
: Option
<ast
::Name
>) -> LoopScope
{
576 return *self.loop_scopes
.last().unwrap();
579 match self.tcx
.def_map
.borrow().get(&expr
.id
).map(|d
| d
.full_def()) {
580 Some(Def
::Label(loop_id
)) => {
581 for l
in &self.loop_scopes
{
582 if l
.loop_id
== loop_id
{
586 span_bug
!(expr
.span
, "no loop scope for id {}", loop_id
);
590 span_bug
!(expr
.span
, "bad entry `{:?}` in def_map for label", r
);