[rustc.git] / src / librustc / middle / cfg / construct.rs

// Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
// file at the top-level directory of this distribution and at
// http://rust-lang.org/COPYRIGHT.
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.

use middle::cfg::*;
use middle::def;
use middle::graph;
use middle::region::CodeExtent;
use middle::ty;
use syntax::ast;
use syntax::ast_util;
use syntax::ptr::P;
use util::nodemap::NodeMap;

struct CFGBuilder<'a, 'tcx: 'a> {
    tcx: &'a ty::ctxt<'tcx>,
    exit_map: NodeMap<CFGIndex>,
    graph: CFGGraph,
    fn_exit: CFGIndex,
    loop_scopes: Vec<LoopScope>,
}

#[derive(Copy)]
struct LoopScope {
    loop_id: ast::NodeId,     // id of loop/while node
    continue_index: CFGIndex, // where to go on a `loop`
    break_index: CFGIndex,    // where to go on a `break
}

pub fn construct(tcx: &ty::ctxt,
                 blk: &ast::Block) -> CFG {
    let mut graph = graph::Graph::new();
    let entry = add_initial_dummy_node(&mut graph);

    // `fn_exit` is target of return exprs, which lies somewhere
    // outside input `blk`. (Distinguishing `fn_exit` and `block_exit`
    // also resolves chicken-and-egg problem that arises if you try to
    // have return exprs jump to `block_exit` during construction.)
    let fn_exit = add_initial_dummy_node(&mut graph);
    let block_exit;

    let mut cfg_builder = CFGBuilder {
        exit_map: NodeMap(),
        graph: graph,
        fn_exit: fn_exit,
        tcx: tcx,
        loop_scopes: Vec::new()
    };
    block_exit = cfg_builder.block(blk, entry);
    cfg_builder.add_contained_edge(block_exit, fn_exit);
    let CFGBuilder {exit_map, graph, ..} = cfg_builder;
    CFG {exit_map: exit_map,
         graph: graph,
         entry: entry,
         exit: fn_exit}
}

fn add_initial_dummy_node(g: &mut CFGGraph) -> CFGIndex {
    g.add_node(CFGNodeData { id: ast::DUMMY_NODE_ID })
}

impl<'a, 'tcx> CFGBuilder<'a, 'tcx> {
    fn block(&mut self, blk: &ast::Block, pred: CFGIndex) -> CFGIndex {
        let mut stmts_exit = pred;
        for stmt in &blk.stmts {
            stmts_exit = self.stmt(&**stmt, stmts_exit);
        }

        let expr_exit = self.opt_expr(&blk.expr, stmts_exit);

        self.add_node(blk.id, &[expr_exit])
    }

    fn stmt(&mut self, stmt: &ast::Stmt, pred: CFGIndex) -> CFGIndex {
        match stmt.node {
            ast::StmtDecl(ref decl, id) => {
                let exit = self.decl(&**decl, pred);
                self.add_node(id, &[exit])
            }

            ast::StmtExpr(ref expr, id) | ast::StmtSemi(ref expr, id) => {
                let exit = self.expr(&**expr, pred);
                self.add_node(id, &[exit])
            }

            ast::StmtMac(..) => {
                self.tcx.sess.span_bug(stmt.span, "unexpanded macro");
            }
        }
    }

    fn decl(&mut self, decl: &ast::Decl, pred: CFGIndex) -> CFGIndex {
        match decl.node {
            ast::DeclLocal(ref local) => {
                let init_exit = self.opt_expr(&local.init, pred);
                self.pat(&*local.pat, init_exit)
            }

            ast::DeclItem(_) => {
                pred
            }
        }
    }

    fn pat(&mut self, pat: &ast::Pat, pred: CFGIndex) -> CFGIndex {
        match pat.node {
            ast::PatIdent(_, _, None) |
            ast::PatEnum(_, None) |
            ast::PatLit(..) |
            ast::PatRange(..) |
            ast::PatWild(_) => {
                self.add_node(pat.id, &[pred])
            }

            ast::PatBox(ref subpat) |
            ast::PatRegion(ref subpat, _) |
            ast::PatIdent(_, _, Some(ref subpat)) => {
                let subpat_exit = self.pat(&**subpat, pred);
                self.add_node(pat.id, &[subpat_exit])
            }

            ast::PatEnum(_, Some(ref subpats)) |
            ast::PatTup(ref subpats) => {
                let pats_exit = self.pats_all(subpats.iter(), pred);
                self.add_node(pat.id, &[pats_exit])
            }

            ast::PatStruct(_, ref subpats, _) => {
                let pats_exit =
                    self.pats_all(subpats.iter().map(|f| &f.node.pat), pred);
                self.add_node(pat.id, &[pats_exit])
            }

            ast::PatVec(ref pre, ref vec, ref post) => {
                let pre_exit = self.pats_all(pre.iter(), pred);
                let vec_exit = self.pats_all(vec.iter(), pre_exit);
                let post_exit = self.pats_all(post.iter(), vec_exit);
                self.add_node(pat.id, &[post_exit])
            }

            ast::PatMac(_) => {
                self.tcx.sess.span_bug(pat.span, "unexpanded macro");
            }
        }
    }

    fn pats_all<'b, I: Iterator<Item=&'b P<ast::Pat>>>(&mut self,
                                          pats: I,
                                          pred: CFGIndex) -> CFGIndex {
        //! Handles case where all of the patterns must match.
        pats.fold(pred, |pred, pat| self.pat(&**pat, pred))
    }

    fn pats_any(&mut self,
                pats: &[P<ast::Pat>],
                pred: CFGIndex) -> CFGIndex {
        //! Handles case where just one of the patterns must match.

        if pats.len() == 1 {
            self.pat(&*pats[0], pred)
        } else {
            let collect = self.add_dummy_node(&[]);
            for pat in pats {
                let pat_exit = self.pat(&**pat, pred);
                self.add_contained_edge(pat_exit, collect);
            }
            collect
        }
    }

    fn expr(&mut self, expr: &ast::Expr, pred: CFGIndex) -> CFGIndex {
        match expr.node {
            ast::ExprBlock(ref blk) => {
                let blk_exit = self.block(&**blk, pred);
                self.add_node(expr.id, &[blk_exit])
            }

            ast::ExprIf(ref cond, ref then, None) => {
                //
                //     [pred]
                //       |
                //       v 1
                //     [cond]
                //       |
                //      / \
                //     /   \
                //    v 2   *
                //  [then]  |
                //    |     |
                //    v 3   v 4
                //   [..expr..]
                //
                let cond_exit = self.expr(&**cond, pred);                // 1
                let then_exit = self.block(&**then, cond_exit);          // 2
                self.add_node(expr.id, &[cond_exit, then_exit])          // 3,4
            }

            ast::ExprIf(ref cond, ref then, Some(ref otherwise)) => {
                //
                //     [pred]
                //       |
                //       v 1
                //     [cond]
                //       |
                //      / \
                //     /   \
                //    v 2   v 3
                //  [then][otherwise]
                //    |     |
                //    v 4   v 5
                //   [..expr..]
                //
                let cond_exit = self.expr(&**cond, pred);                // 1
                let then_exit = self.block(&**then, cond_exit);          // 2
                let else_exit = self.expr(&**otherwise, cond_exit);      // 3
                self.add_node(expr.id, &[then_exit, else_exit])          // 4, 5
            }

            ast::ExprIfLet(..) => {
                self.tcx.sess.span_bug(expr.span, "non-desugared ExprIfLet");
            }

            ast::ExprWhile(ref cond, ref body, _) => {
                //
                //         [pred]
                //           |
                //           v 1
                //       [loopback] <--+ 5
                //           |         |
                //           v 2       |
                //   +-----[cond]      |
                //   |       |         |
                //   |       v 4       |
                //   |     [body] -----+
                //   v 3
                // [expr]
                //
                // Note that `break` and `continue` statements
                // may cause additional edges.

                // Is the condition considered part of the loop?
                let loopback = self.add_dummy_node(&[pred]);              // 1
                let cond_exit = self.expr(&**cond, loopback);             // 2
                let expr_exit = self.add_node(expr.id, &[cond_exit]);     // 3
                self.loop_scopes.push(LoopScope {
                    loop_id: expr.id,
                    continue_index: loopback,
                    break_index: expr_exit
                });
                let body_exit = self.block(&**body, cond_exit);          // 4
                self.add_contained_edge(body_exit, loopback);            // 5
                self.loop_scopes.pop();
                expr_exit
            }

            ast::ExprWhileLet(..) => {
                self.tcx.sess.span_bug(expr.span, "non-desugared ExprWhileLet");
            }

            ast::ExprForLoop(..) => {
                self.tcx.sess.span_bug(expr.span, "non-desugared ExprForLoop");
            }

            ast::ExprLoop(ref body, _) => {
                //
                //     [pred]
                //       |
                //       v 1
                //   [loopback] <---+
                //       |      4   |
                //       v 3        |
                //     [body] ------+
                //
                //     [expr] 2
                //
                // Note that `break` and `loop` statements
                // may cause additional edges.

                let loopback = self.add_dummy_node(&[pred]);              // 1
                let expr_exit = self.add_node(expr.id, &[]);              // 2
                self.loop_scopes.push(LoopScope {
                    loop_id: expr.id,
                    continue_index: loopback,
                    break_index: expr_exit,
                });
                let body_exit = self.block(&**body, loopback);           // 3
                self.add_contained_edge(body_exit, loopback);            // 4
                self.loop_scopes.pop();
                expr_exit
            }

            ast::ExprMatch(ref discr, ref arms, _) => {
                //
                //     [pred]
                //       |
                //       v 1
                //    [discr]
                //       |
                //       v 2
                //    [cond1]
                //      /  \
                //     |    \
                //     v 3   \
                //  [pat1]    \
                //     |       |
                //     v 4     |
                //  [guard1]   |
                //     |       |
                //     |       |
                //     v 5     v
                //  [body1]  [cond2]
                //     |      /  \
                //     |    ...  ...
                //     |     |    |
                //     v 6   v    v
                //  [.....expr.....]
                //
                let discr_exit = self.expr(&**discr, pred);              // 1

                let expr_exit = self.add_node(expr.id, &[]);
                let mut cond_exit = discr_exit;
                for arm in arms {
                    cond_exit = self.add_dummy_node(&[cond_exit]);        // 2
                    let pats_exit = self.pats_any(&arm.pats[],
                                                  cond_exit);            // 3
                    let guard_exit = self.opt_expr(&arm.guard,
                                                   pats_exit);           // 4
                    let body_exit = self.expr(&*arm.body, guard_exit);   // 5
                    self.add_contained_edge(body_exit, expr_exit);       // 6
                }
                expr_exit
            }

            ast::ExprBinary(op, ref l, ref r) if ast_util::lazy_binop(op.node) => {
                //
                //     [pred]
                //       |
                //       v 1
                //      [l]
                //       |
                //      / \
                //     /   \
                //    v 2  *
                //   [r]   |
                //    |    |
                //    v 3  v 4
                //   [..exit..]
                //
                let l_exit = self.expr(&**l, pred);                      // 1
                let r_exit = self.expr(&**r, l_exit);                    // 2
                self.add_node(expr.id, &[l_exit, r_exit])                 // 3,4
            }

            ast::ExprRet(ref v) => {
                let v_exit = self.opt_expr(v, pred);
                let b = self.add_node(expr.id, &[v_exit]);
                self.add_returning_edge(expr, b);
                self.add_node(ast::DUMMY_NODE_ID, &[])
            }

            ast::ExprBreak(label) => {
                let loop_scope = self.find_scope(expr, label);
                let b = self.add_node(expr.id, &[pred]);
                self.add_exiting_edge(expr, b,
                                      loop_scope, loop_scope.break_index);
                self.add_node(ast::DUMMY_NODE_ID, &[])
            }

            ast::ExprAgain(label) => {
                let loop_scope = self.find_scope(expr, label);
                let a = self.add_node(expr.id, &[pred]);
                self.add_exiting_edge(expr, a,
                                      loop_scope, loop_scope.continue_index);
                self.add_node(ast::DUMMY_NODE_ID, &[])
            }

            ast::ExprVec(ref elems) => {
                self.straightline(expr, pred, elems.iter().map(|e| &**e))
            }

            ast::ExprCall(ref func, ref args) => {
                self.call(expr, pred, &**func, args.iter().map(|e| &**e))
            }

            ast::ExprMethodCall(_, _, ref args) => {
                self.call(expr, pred, &*args[0], args[1..].iter().map(|e| &**e))
            }

            ast::ExprIndex(ref l, ref r) |
            ast::ExprBinary(_, ref l, ref r) if self.is_method_call(expr) => {
                self.call(expr, pred, &**l, Some(&**r).into_iter())
            }

            ast::ExprRange(ref start, ref end) => {
                let fields = start.as_ref().map(|e| &**e).into_iter()
                    .chain(end.as_ref().map(|e| &**e).into_iter());
                self.straightline(expr, pred, fields)
            }

            ast::ExprUnary(_, ref e) if self.is_method_call(expr) => {
                self.call(expr, pred, &**e, None::<ast::Expr>.iter())
            }

            ast::ExprTup(ref exprs) => {
                self.straightline(expr, pred, exprs.iter().map(|e| &**e))
            }

            ast::ExprStruct(_, ref fields, ref base) => {
                let field_cfg = self.straightline(expr, pred, fields.iter().map(|f| &*f.expr));
                self.opt_expr(base, field_cfg)
            }

            ast::ExprRepeat(ref elem, ref count) => {
                self.straightline(expr, pred, [elem, count].iter().map(|&e| &**e))
            }

            ast::ExprAssign(ref l, ref r) |
            ast::ExprAssignOp(_, ref l, ref r) => {
                self.straightline(expr, pred, [r, l].iter().map(|&e| &**e))
            }

            ast::ExprBox(Some(ref l), ref r) |
            ast::ExprIndex(ref l, ref r) |
            ast::ExprBinary(_, ref l, ref r) => { // NB: && and || handled earlier
                self.straightline(expr, pred, [l, r].iter().map(|&e| &**e))
            }

            ast::ExprBox(None, ref e) |
            ast::ExprAddrOf(_, ref e) |
            ast::ExprCast(ref e, _) |
            ast::ExprUnary(_, ref e) |
            ast::ExprParen(ref e) |
            ast::ExprField(ref e, _) |
            ast::ExprTupField(ref e, _) => {
                self.straightline(expr, pred, Some(&**e).into_iter())
            }

            ast::ExprInlineAsm(ref inline_asm) => {
                let inputs = inline_asm.inputs.iter();
                let outputs = inline_asm.outputs.iter();
                let post_inputs = self.exprs(inputs.map(|a| {
                    debug!("cfg::construct InlineAsm id:{} input:{:?}", expr.id, a);
                    let &(_, ref expr) = a;
                    &**expr
                }), pred);
                let post_outputs = self.exprs(outputs.map(|a| {
                    debug!("cfg::construct InlineAsm id:{} output:{:?}", expr.id, a);
                    let &(_, ref expr, _) = a;
                    &**expr
                }), post_inputs);
                self.add_node(expr.id, &[post_outputs])
            }

            ast::ExprMac(..) |
            ast::ExprClosure(..) |
            ast::ExprLit(..) |
            ast::ExprPath(..) |
            ast::ExprQPath(..) => {
                self.straightline(expr, pred, None::<ast::Expr>.iter())
            }
        }
    }

    fn call<'b, I: Iterator<Item=&'b ast::Expr>>(&mut self,
            call_expr: &ast::Expr,
            pred: CFGIndex,
            func_or_rcvr: &ast::Expr,
            args: I) -> CFGIndex {
        let method_call = ty::MethodCall::expr(call_expr.id);
        let return_ty = ty::ty_fn_ret(match self.tcx.method_map.borrow().get(&method_call) {
            Some(method) => method.ty,
            None => ty::expr_ty_adjusted(self.tcx, func_or_rcvr)
        });

        let func_or_rcvr_exit = self.expr(func_or_rcvr, pred);
        let ret = self.straightline(call_expr, func_or_rcvr_exit, args);
        if return_ty.diverges() {
            self.add_node(ast::DUMMY_NODE_ID, &[])
        } else {
            ret
        }
    }

    fn exprs<'b, I: Iterator<Item=&'b ast::Expr>>(&mut self,
                                             exprs: I,
                                             pred: CFGIndex) -> CFGIndex {
        //! Constructs graph for `exprs` evaluated in order
        exprs.fold(pred, |p, e| self.expr(e, p))
    }

    fn opt_expr(&mut self,
                opt_expr: &Option<P<ast::Expr>>,
                pred: CFGIndex) -> CFGIndex {
        //! Constructs graph for `opt_expr` evaluated, if Some
        opt_expr.iter().fold(pred, |p, e| self.expr(&**e, p))
    }

    fn straightline<'b, I: Iterator<Item=&'b ast::Expr>>(&mut self,
                    expr: &ast::Expr,
                    pred: CFGIndex,
                    subexprs: I) -> CFGIndex {
        //! Handles case of an expression that evaluates `subexprs` in order

        let subexprs_exit = self.exprs(subexprs, pred);
        self.add_node(expr.id, &[subexprs_exit])
    }

    fn add_dummy_node(&mut self, preds: &[CFGIndex]) -> CFGIndex {
        self.add_node(ast::DUMMY_NODE_ID, preds)
    }

    fn add_node(&mut self, id: ast::NodeId, preds: &[CFGIndex]) -> CFGIndex {
        assert!(!self.exit_map.contains_key(&id));
        let node = self.graph.add_node(CFGNodeData {id: id});
        if id != ast::DUMMY_NODE_ID {
            assert!(!self.exit_map.contains_key(&id));
            self.exit_map.insert(id, node);
        }
        for &pred in preds {
            self.add_contained_edge(pred, node);
        }
        node
    }

    fn add_contained_edge(&mut self,
                          source: CFGIndex,
                          target: CFGIndex) {
        let data = CFGEdgeData {exiting_scopes: vec!() };
        self.graph.add_edge(source, target, data);
    }

    fn add_exiting_edge(&mut self,
                        from_expr: &ast::Expr,
                        from_index: CFGIndex,
                        to_loop: LoopScope,
                        to_index: CFGIndex) {
        let mut data = CFGEdgeData {exiting_scopes: vec!() };
        let mut scope = CodeExtent::from_node_id(from_expr.id);
        let target_scope = CodeExtent::from_node_id(to_loop.loop_id);
        while scope != target_scope {

            data.exiting_scopes.push(scope.node_id());
            scope = self.tcx.region_maps.encl_scope(scope);
        }
        self.graph.add_edge(from_index, to_index, data);
    }

    fn add_returning_edge(&mut self,
                          _from_expr: &ast::Expr,
                          from_index: CFGIndex) {
        let mut data = CFGEdgeData {
            exiting_scopes: vec!(),
        };
        for &LoopScope { loop_id: id, .. } in self.loop_scopes.iter().rev() {
            data.exiting_scopes.push(id);
        }
        self.graph.add_edge(from_index, self.fn_exit, data);
    }

    fn find_scope(&self,
                  expr: &ast::Expr,
                  label: Option<ast::Ident>) -> LoopScope {
        match label {
            None => {
                return *self.loop_scopes.last().unwrap();
            }

            Some(_) => {
                match self.tcx.def_map.borrow().get(&expr.id) {
                    Some(&def::DefLabel(loop_id)) => {
                        for l in &self.loop_scopes {
                            if l.loop_id == loop_id {
                                return *l;
                            }
                        }
                        self.tcx.sess.span_bug(
                            expr.span,
                            &format!("no loop scope for id {}",
                                    loop_id)[]);
                    }

                    r => {
                        self.tcx.sess.span_bug(
                            expr.span,
                            &format!("bad entry `{:?}` in def_map for label",
                                    r)[]);
                    }
                }
            }
        }
    }

    fn is_method_call(&self, expr: &ast::Expr) -> bool {
        let method_call = ty::MethodCall::expr(expr.id);
        self.tcx.method_map.borrow().contains_key(&method_call)
    }
}
Commit	Line	Data
1a4d82fc JJ	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.
	4	//
	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.
	10
	11	use middle::cfg::*;
	12	use middle::def;
	13	use middle::graph;
	14	use middle::region::CodeExtent;
	15	use middle::ty;
	16	use syntax::ast;
	17	use syntax::ast_util;
	18	use syntax::ptr::P;
	19	use util::nodemap::NodeMap;
	20
	21	struct CFGBuilder<'a, 'tcx: 'a> {
	22	tcx: &'a ty::ctxt<'tcx>,
	23	exit_map: NodeMap<CFGIndex>,
	24	graph: CFGGraph,
	25	fn_exit: CFGIndex,
	26	loop_scopes: Vec<LoopScope>,
	27	}
	28
	29	#[derive(Copy)]
	30	struct LoopScope {
	31	loop_id: ast::NodeId, // id of loop/while node
	32	continue_index: CFGIndex, // where to go on a `loop`
	33	break_index: CFGIndex, // where to go on a `break
	34	}
	35
	36	pub fn construct(tcx: &ty::ctxt,
	37	blk: &ast::Block) -> CFG {
	38	let mut graph = graph::Graph::new();
	39	let entry = add_initial_dummy_node(&mut graph);
	40
	41	// `fn_exit` is target of return exprs, which lies somewhere
	42	// outside input `blk`. (Distinguishing `fn_exit` and `block_exit`
	43	// also resolves chicken-and-egg problem that arises if you try to
	44	// have return exprs jump to `block_exit` during construction.)
	45	let fn_exit = add_initial_dummy_node(&mut graph);
	46	let block_exit;
	47
	48	let mut cfg_builder = CFGBuilder {
85aaf69f	49	exit_map: NodeMap(),
1a4d82fc JJ	50	graph: graph,
	51	fn_exit: fn_exit,
	52	tcx: tcx,
	53	loop_scopes: Vec::new()
	54	};
	55	block_exit = cfg_builder.block(blk, entry);
	56	cfg_builder.add_contained_edge(block_exit, fn_exit);
	57	let CFGBuilder {exit_map, graph, ..} = cfg_builder;
	58	CFG {exit_map: exit_map,
	59	graph: graph,
	60	entry: entry,
	61	exit: fn_exit}
	62	}
	63
	64	fn add_initial_dummy_node(g: &mut CFGGraph) -> CFGIndex {
	65	g.add_node(CFGNodeData { id: ast::DUMMY_NODE_ID })
	66	}
	67
	68	impl<'a, 'tcx> CFGBuilder<'a, 'tcx> {
	69	fn block(&mut self, blk: &ast::Block, pred: CFGIndex) -> CFGIndex {
	70	let mut stmts_exit = pred;
85aaf69f	71	for stmt in &blk.stmts {
1a4d82fc JJ	72	stmts_exit = self.stmt(&**stmt, stmts_exit);
	73	}
	74
	75	let expr_exit = self.opt_expr(&blk.expr, stmts_exit);
	76
	77	self.add_node(blk.id, &[expr_exit])
	78	}
	79
	80	fn stmt(&mut self, stmt: &ast::Stmt, pred: CFGIndex) -> CFGIndex {
	81	match stmt.node {
	82	ast::StmtDecl(ref decl, id) => {
	83	let exit = self.decl(&**decl, pred);
	84	self.add_node(id, &[exit])
	85	}
	86
	87	ast::StmtExpr(ref expr, id) \| ast::StmtSemi(ref expr, id) => {
	88	let exit = self.expr(&**expr, pred);
	89	self.add_node(id, &[exit])
	90	}
	91
	92	ast::StmtMac(..) => {
	93	self.tcx.sess.span_bug(stmt.span, "unexpanded macro");
	94	}
	95	}
	96	}
	97
	98	fn decl(&mut self, decl: &ast::Decl, pred: CFGIndex) -> CFGIndex {
	99	match decl.node {
	100	ast::DeclLocal(ref local) => {
	101	let init_exit = self.opt_expr(&local.init, pred);
	102	self.pat(&*local.pat, init_exit)
	103	}
	104
	105	ast::DeclItem(_) => {
	106	pred
	107	}
	108	}
	109	}
	110
	111	fn pat(&mut self, pat: &ast::Pat, pred: CFGIndex) -> CFGIndex {
	112	match pat.node {
	113	ast::PatIdent(_, _, None) \|
	114	ast::PatEnum(_, None) \|
	115	ast::PatLit(..) \|
	116	ast::PatRange(..) \|
	117	ast::PatWild(_) => {
	118	self.add_node(pat.id, &[pred])
	119	}
	120
	121	ast::PatBox(ref subpat) \|
	122	ast::PatRegion(ref subpat, _) \|
	123	ast::PatIdent(_, _, Some(ref subpat)) => {
	124	let subpat_exit = self.pat(&**subpat, pred);
	125	self.add_node(pat.id, &[subpat_exit])
	126	}
	127
	128	ast::PatEnum(_, Some(ref subpats)) \|
	129	ast::PatTup(ref subpats) => {
	130	let pats_exit = self.pats_all(subpats.iter(), pred);
	131	self.add_node(pat.id, &[pats_exit])
	132	}
	133
	134	ast::PatStruct(_, ref subpats, _) => {
	135	let pats_exit =
136	self.pats_all(subpats.iter().map(\|f\| &f.node.pat), pred);
137	self.add_node(pat.id, &[pats_exit])
138	}
139
140	ast::PatVec(ref pre, ref vec, ref post) => {
141	let pre_exit = self.pats_all(pre.iter(), pred);
142	let vec_exit = self.pats_all(vec.iter(), pre_exit);
143	let post_exit = self.pats_all(post.iter(), vec_exit);
144	self.add_node(pat.id, &[post_exit])
145	}
146
147	ast::PatMac(_) => {
148	self.tcx.sess.span_bug(pat.span, "unexpanded macro");
149	}
150	}
151	}
152
153	fn pats_all<'b, I: Iterator<Item=&'b P<ast::Pat>>>(&mut self,
154	pats: I,
155	pred: CFGIndex) -> CFGIndex {
156	//! Handles case where all of the patterns must match.
157	pats.fold(pred, \|pred, pat\| self.pat(&**pat, pred))
158	}
159
160	fn pats_any(&mut self,
161	pats: &[P<ast::Pat>],
162	pred: CFGIndex) -> CFGIndex {
163	//! Handles case where just one of the patterns must match.
164
165	if pats.len() == 1 {
166	self.pat(&*pats[0], pred)
167	} else {
168	let collect = self.add_dummy_node(&[]);
85aaf69f	169	for pat in pats {
1a4d82fc JJ	170	let pat_exit = self.pat(&**pat, pred);
	171	self.add_contained_edge(pat_exit, collect);
	172	}
	173	collect
	174	}
	175	}
	176
	177	fn expr(&mut self, expr: &ast::Expr, pred: CFGIndex) -> CFGIndex {
	178	match expr.node {
	179	ast::ExprBlock(ref blk) => {
	180	let blk_exit = self.block(&**blk, pred);
	181	self.add_node(expr.id, &[blk_exit])
	182	}
	183
	184	ast::ExprIf(ref cond, ref then, None) => {
	185	//
	186	// [pred]
	187	// \|
	188	// v 1
	189	// [cond]
	190	// \|
	191	// / \
	192	// / \
	193	// v 2 *
	194	// [then] \|
	195	// \| \|
	196	// v 3 v 4
	197	// [..expr..]
	198	//
	199	let cond_exit = self.expr(&**cond, pred); // 1
	200	let then_exit = self.block(&**then, cond_exit); // 2
	201	self.add_node(expr.id, &[cond_exit, then_exit]) // 3,4
	202	}
	203
	204	ast::ExprIf(ref cond, ref then, Some(ref otherwise)) => {
	205	//
	206	// [pred]
	207	// \|
	208	// v 1
	209	// [cond]
	210	// \|
	211	// / \
	212	// / \
	213	// v 2 v 3
	214	// [then][otherwise]
	215	// \| \|
	216	// v 4 v 5
	217	// [..expr..]
	218	//
	219	let cond_exit = self.expr(&**cond, pred); // 1
	220	let then_exit = self.block(&**then, cond_exit); // 2
	221	let else_exit = self.expr(&**otherwise, cond_exit); // 3
	222	self.add_node(expr.id, &[then_exit, else_exit]) // 4, 5
	223	}
	224
	225	ast::ExprIfLet(..) => {
	226	self.tcx.sess.span_bug(expr.span, "non-desugared ExprIfLet");
	227	}
	228
	229	ast::ExprWhile(ref cond, ref body, _) => {
	230	//
	231	// [pred]
	232	// \|
	233	// v 1
234	// [loopback] <--+ 5
235	// \| \|
236	// v 2 \|
237	// +-----[cond] \|
238	// \| \| \|
239	// \| v 4 \|
240	// \| [body] -----+
241	// v 3
242	// [expr]
243	//
244	// Note that `break` and `continue` statements
245	// may cause additional edges.
246
247	// Is the condition considered part of the loop?
248	let loopback = self.add_dummy_node(&[pred]); // 1
249	let cond_exit = self.expr(&**cond, loopback); // 2
250	let expr_exit = self.add_node(expr.id, &[cond_exit]); // 3
251	self.loop_scopes.push(LoopScope {
252	loop_id: expr.id,
253	continue_index: loopback,
254	break_index: expr_exit
255	});
256	let body_exit = self.block(&**body, cond_exit); // 4
257	self.add_contained_edge(body_exit, loopback); // 5
258	self.loop_scopes.pop();
259	expr_exit
260	}
261
262	ast::ExprWhileLet(..) => {
263	self.tcx.sess.span_bug(expr.span, "non-desugared ExprWhileLet");
264	}
265
85aaf69f SL	266	ast::ExprForLoop(..) => {
85aaf69f SL	267	self.tcx.sess.span_bug(expr.span, "non-desugared ExprForLoop");
1a4d82fc JJ	268	}
	269
	270	ast::ExprLoop(ref body, _) => {
	271	//
	272	// [pred]
	273	// \|
	274	// v 1
	275	// [loopback] <---+
	276	// \| 4 \|
	277	// v 3 \|
	278	// [body] ------+
	279	//
	280	// [expr] 2
	281	//
	282	// Note that `break` and `loop` statements
	283	// may cause additional edges.
	284
	285	let loopback = self.add_dummy_node(&[pred]); // 1
	286	let expr_exit = self.add_node(expr.id, &[]); // 2
	287	self.loop_scopes.push(LoopScope {
	288	loop_id: expr.id,
	289	continue_index: loopback,
	290	break_index: expr_exit,
	291	});
	292	let body_exit = self.block(&**body, loopback); // 3
	293	self.add_contained_edge(body_exit, loopback); // 4
	294	self.loop_scopes.pop();
	295	expr_exit
	296	}
	297
	298	ast::ExprMatch(ref discr, ref arms, _) => {
	299	//
	300	// [pred]
	301	// \|
	302	// v 1
	303	// [discr]
	304	// \|
	305	// v 2
	306	// [cond1]
	307	// / \
	308	// \| \
	309	// v 3 \
	310	// [pat1] \
	311	// \| \|
	312	// v 4 \|
	313	// [guard1] \|
	314	// \| \|
	315	// \| \|
	316	// v 5 v
	317	// [body1] [cond2]
	318	// \| / \
	319	// \| ... ...
	320	// \| \| \|
	321	// v 6 v v
	322	// [.....expr.....]
	323	//
	324	let discr_exit = self.expr(&**discr, pred); // 1
	325
	326	let expr_exit = self.add_node(expr.id, &[]);
	327	let mut cond_exit = discr_exit;
85aaf69f	328	for arm in arms {
1a4d82fc JJ	329	cond_exit = self.add_dummy_node(&[cond_exit]); // 2
	330	let pats_exit = self.pats_any(&arm.pats[],
	331	cond_exit); // 3
	332	let guard_exit = self.opt_expr(&arm.guard,
	333	pats_exit); // 4
	334	let body_exit = self.expr(&*arm.body, guard_exit); // 5
	335	self.add_contained_edge(body_exit, expr_exit); // 6
	336	}
	337	expr_exit
	338	}
	339
85aaf69f	340	ast::ExprBinary(op, ref l, ref r) if ast_util::lazy_binop(op.node) => {
1a4d82fc JJ	341	//
	342	// [pred]
	343	// \|
	344	// v 1
	345	// [l]
	346	// \|
	347	// / \
	348	// / \
	349	// v 2 *
	350	// [r] \|
	351	// \| \|
	352	// v 3 v 4
	353	// [..exit..]
	354	//
	355	let l_exit = self.expr(&**l, pred); // 1
	356	let r_exit = self.expr(&**r, l_exit); // 2
	357	self.add_node(expr.id, &[l_exit, r_exit]) // 3,4
	358	}
	359
	360	ast::ExprRet(ref v) => {
	361	let v_exit = self.opt_expr(v, pred);
	362	let b = self.add_node(expr.id, &[v_exit]);
	363	self.add_returning_edge(expr, b);
	364	self.add_node(ast::DUMMY_NODE_ID, &[])
	365	}
	366
	367	ast::ExprBreak(label) => {
	368	let loop_scope = self.find_scope(expr, label);
	369	let b = self.add_node(expr.id, &[pred]);
	370	self.add_exiting_edge(expr, b,
	371	loop_scope, loop_scope.break_index);
	372	self.add_node(ast::DUMMY_NODE_ID, &[])
	373	}
	374
	375	ast::ExprAgain(label) => {
	376	let loop_scope = self.find_scope(expr, label);
	377	let a = self.add_node(expr.id, &[pred]);
	378	self.add_exiting_edge(expr, a,
	379	loop_scope, loop_scope.continue_index);
	380	self.add_node(ast::DUMMY_NODE_ID, &[])
	381	}
	382
	383	ast::ExprVec(ref elems) => {
	384	self.straightline(expr, pred, elems.iter().map(\|e\| &**e))
	385	}
	386
	387	ast::ExprCall(ref func, ref args) => {
	388	self.call(expr, pred, &func, args.iter().map(\|e\| &e))
	389	}
	390
	391	ast::ExprMethodCall(_, _, ref args) => {
85aaf69f	392	self.call(expr, pred, &args[0], args[1..].iter().map(\|e\| &*e))
1a4d82fc JJ	393	}
	394
	395	ast::ExprIndex(ref l, ref r) \|
	396	ast::ExprBinary(_, ref l, ref r) if self.is_method_call(expr) => {
	397	self.call(expr, pred, &l, Some(&r).into_iter())
	398	}
	399
	400	ast::ExprRange(ref start, ref end) => {
	401	let fields = start.as_ref().map(\|e\| &**e).into_iter()
	402	.chain(end.as_ref().map(\|e\| &**e).into_iter());
	403	self.straightline(expr, pred, fields)
	404	}
	405
	406	ast::ExprUnary(_, ref e) if self.is_method_call(expr) => {
	407	self.call(expr, pred, &**e, None::<ast::Expr>.iter())
	408	}
	409
	410	ast::ExprTup(ref exprs) => {
	411	self.straightline(expr, pred, exprs.iter().map(\|e\| &**e))
	412	}
	413
	414	ast::ExprStruct(_, ref fields, ref base) => {
	415	let field_cfg = self.straightline(expr, pred, fields.iter().map(\|f\| &*f.expr));
	416	self.opt_expr(base, field_cfg)
	417	}
	418
	419	ast::ExprRepeat(ref elem, ref count) => {
	420	self.straightline(expr, pred, [elem, count].iter().map(\|&e\| &**e))
	421	}
	422
	423	ast::ExprAssign(ref l, ref r) \|
	424	ast::ExprAssignOp(_, ref l, ref r) => {
	425	self.straightline(expr, pred, [r, l].iter().map(\|&e\| &**e))
	426	}
	427
	428	ast::ExprBox(Some(ref l), ref r) \|
	429	ast::ExprIndex(ref l, ref r) \|
	430	ast::ExprBinary(_, ref l, ref r) => { // NB: && and \|\| handled earlier
	431	self.straightline(expr, pred, [l, r].iter().map(\|&e\| &**e))
	432	}
	433
	434	ast::ExprBox(None, ref e) \|
	435	ast::ExprAddrOf(_, ref e) \|
	436	ast::ExprCast(ref e, _) \|
	437	ast::ExprUnary(_, ref e) \|
	438	ast::ExprParen(ref e) \|
	439	ast::ExprField(ref e, _) \|
	440	ast::ExprTupField(ref e, _) => {
	441	self.straightline(expr, pred, Some(&**e).into_iter())
	442	}
	443
	444	ast::ExprInlineAsm(ref inline_asm) => {
	445	let inputs = inline_asm.inputs.iter();
	446	let outputs = inline_asm.outputs.iter();
	447	let post_inputs = self.exprs(inputs.map(\|a\| {
	448	debug!("cfg::construct InlineAsm id:{} input:{:?}", expr.id, a);
	449	let &(_, ref expr) = a;
	450	&**expr
	451	}), pred);
	452	let post_outputs = self.exprs(outputs.map(\|a\| {
	453	debug!("cfg::construct InlineAsm id:{} output:{:?}", expr.id, a);
	454	let &(_, ref expr, _) = a;
	455	&**expr
	456	}), post_inputs);
457	self.add_node(expr.id, &[post_outputs])
458	}
459
460	ast::ExprMac(..) \|
461	ast::ExprClosure(..) \|
462	ast::ExprLit(..) \|
85aaf69f SL	463	ast::ExprPath(..) \|
85aaf69f SL	464	ast::ExprQPath(..) => {
1a4d82fc JJ	465	self.straightline(expr, pred, None::<ast::Expr>.iter())
	466	}
	467	}
	468	}
	469
	470	fn call<'b, I: Iterator<Item=&'b ast::Expr>>(&mut self,
	471	call_expr: &ast::Expr,
	472	pred: CFGIndex,
	473	func_or_rcvr: &ast::Expr,
	474	args: I) -> CFGIndex {
	475	let method_call = ty::MethodCall::expr(call_expr.id);
	476	let return_ty = ty::ty_fn_ret(match self.tcx.method_map.borrow().get(&method_call) {
	477	Some(method) => method.ty,
	478	None => ty::expr_ty_adjusted(self.tcx, func_or_rcvr)
	479	});
	480
	481	let func_or_rcvr_exit = self.expr(func_or_rcvr, pred);
	482	let ret = self.straightline(call_expr, func_or_rcvr_exit, args);
	483	if return_ty.diverges() {
	484	self.add_node(ast::DUMMY_NODE_ID, &[])
	485	} else {
	486	ret
	487	}
	488	}
	489
	490	fn exprs<'b, I: Iterator<Item=&'b ast::Expr>>(&mut self,
	491	exprs: I,
	492	pred: CFGIndex) -> CFGIndex {
	493	//! Constructs graph for `exprs` evaluated in order
	494	exprs.fold(pred, \|p, e\| self.expr(e, p))
	495	}
	496
	497	fn opt_expr(&mut self,
	498	opt_expr: &Option<P<ast::Expr>>,
	499	pred: CFGIndex) -> CFGIndex {
	500	//! Constructs graph for `opt_expr` evaluated, if Some
	501	opt_expr.iter().fold(pred, \|p, e\| self.expr(&**e, p))
	502	}
	503
	504	fn straightline<'b, I: Iterator<Item=&'b ast::Expr>>(&mut self,
	505	expr: &ast::Expr,
	506	pred: CFGIndex,
	507	subexprs: I) -> CFGIndex {
	508	//! Handles case of an expression that evaluates `subexprs` in order
	509
	510	let subexprs_exit = self.exprs(subexprs, pred);
	511	self.add_node(expr.id, &[subexprs_exit])
	512	}
	513
	514	fn add_dummy_node(&mut self, preds: &[CFGIndex]) -> CFGIndex {
	515	self.add_node(ast::DUMMY_NODE_ID, preds)
	516	}
	517
	518	fn add_node(&mut self, id: ast::NodeId, preds: &[CFGIndex]) -> CFGIndex {
	519	assert!(!self.exit_map.contains_key(&id));
	520	let node = self.graph.add_node(CFGNodeData {id: id});
	521	if id != ast::DUMMY_NODE_ID {
	522	assert!(!self.exit_map.contains_key(&id));
	523	self.exit_map.insert(id, node);
	524	}
85aaf69f	525	for &pred in preds {
1a4d82fc JJ	526	self.add_contained_edge(pred, node);
	527	}
	528	node
	529	}
	530
	531	fn add_contained_edge(&mut self,
	532	source: CFGIndex,
	533	target: CFGIndex) {
	534	let data = CFGEdgeData {exiting_scopes: vec!() };
	535	self.graph.add_edge(source, target, data);
	536	}
	537
	538	fn add_exiting_edge(&mut self,
	539	from_expr: &ast::Expr,
	540	from_index: CFGIndex,
	541	to_loop: LoopScope,
	542	to_index: CFGIndex) {
	543	let mut data = CFGEdgeData {exiting_scopes: vec!() };
	544	let mut scope = CodeExtent::from_node_id(from_expr.id);
	545	let target_scope = CodeExtent::from_node_id(to_loop.loop_id);
	546	while scope != target_scope {
	547
	548	data.exiting_scopes.push(scope.node_id());
	549	scope = self.tcx.region_maps.encl_scope(scope);
	550	}
	551	self.graph.add_edge(from_index, to_index, data);
	552	}
	553
	554	fn add_returning_edge(&mut self,
	555	_from_expr: &ast::Expr,
	556	from_index: CFGIndex) {
	557	let mut data = CFGEdgeData {
	558	exiting_scopes: vec!(),
	559	};
	560	for &LoopScope { loop_id: id, .. } in self.loop_scopes.iter().rev() {
	561	data.exiting_scopes.push(id);
	562	}
	563	self.graph.add_edge(from_index, self.fn_exit, data);
	564	}
	565
	566	fn find_scope(&self,
	567	expr: &ast::Expr,
	568	label: Option<ast::Ident>) -> LoopScope {
	569	match label {
	570	None => {
	571	return *self.loop_scopes.last().unwrap();
	572	}
	573
	574	Some(_) => {
	575	match self.tcx.def_map.borrow().get(&expr.id) {
	576	Some(&def::DefLabel(loop_id)) => {
85aaf69f	577	for l in &self.loop_scopes {
1a4d82fc JJ	578	if l.loop_id == loop_id {
	579	return *l;
	580	}
	581	}
	582	self.tcx.sess.span_bug(
	583	expr.span,
	584	&format!("no loop scope for id {}",
	585	loop_id)[]);
	586	}
	587
	588	r => {
	589	self.tcx.sess.span_bug(
	590	expr.span,
	591	&format!("bad entry `{:?}` in def_map for label",
	592	r)[]);
	593	}
	594	}
	595	}
	596	}
	597	}
	598
	599	fn is_method_call(&self, expr: &ast::Expr) -> bool {
	600	let method_call = ty::MethodCall::expr(expr.id);
	601	self.tcx.method_map.borrow().contains_key(&method_call)
	602	}
	603	}