]> git.proxmox.com Git - rustc.git/blob - src/librustc/cfg/construct.rs
Imported Upstream version 1.9.0+dfsg1
[rustc.git] / src / librustc / cfg / construct.rs
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 rustc_data_structures::graph;
12 use cfg::*;
13 use hir::def::Def;
14 use hir::pat_util;
15 use ty::{self, TyCtxt};
16 use syntax::ast;
17 use syntax::ptr::P;
18
19 use hir::{self, PatKind};
20
21 struct CFGBuilder<'a, 'tcx: 'a> {
22 tcx: &'a TyCtxt<'tcx>,
23 graph: CFGGraph,
24 fn_exit: CFGIndex,
25 loop_scopes: Vec<LoopScope>,
26 }
27
28 #[derive(Copy, Clone)]
29 struct LoopScope {
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
33 }
34
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);
39
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);
45 let block_exit;
46
47 let mut cfg_builder = CFGBuilder {
48 graph: graph,
49 fn_exit: fn_exit,
50 tcx: tcx,
51 loop_scopes: Vec::new()
52 };
53 block_exit = cfg_builder.block(blk, entry);
54 cfg_builder.add_contained_edge(block_exit, fn_exit);
55 let CFGBuilder {graph, ..} = cfg_builder;
56 CFG {graph: graph,
57 entry: entry,
58 exit: fn_exit}
59 }
60
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);
66 }
67
68 let expr_exit = self.opt_expr(&blk.expr, stmts_exit);
69
70 self.add_ast_node(blk.id, &[expr_exit])
71 }
72
73 fn stmt(&mut self, stmt: &hir::Stmt, pred: CFGIndex) -> CFGIndex {
74 match stmt.node {
75 hir::StmtDecl(ref decl, id) => {
76 let exit = self.decl(&decl, pred);
77 self.add_ast_node(id, &[exit])
78 }
79
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])
83 }
84 }
85 }
86
87 fn decl(&mut self, decl: &hir::Decl, pred: CFGIndex) -> CFGIndex {
88 match decl.node {
89 hir::DeclLocal(ref local) => {
90 let init_exit = self.opt_expr(&local.init, pred);
91 self.pat(&local.pat, init_exit)
92 }
93
94 hir::DeclItem(_) => {
95 pred
96 }
97 }
98 }
99
100 fn pat(&mut self, pat: &hir::Pat, pred: CFGIndex) -> CFGIndex {
101 match pat.node {
102 PatKind::Ident(_, _, None) |
103 PatKind::TupleStruct(_, None) |
104 PatKind::Path(..) |
105 PatKind::QPath(..) |
106 PatKind::Lit(..) |
107 PatKind::Range(..) |
108 PatKind::Wild => {
109 self.add_ast_node(pat.id, &[pred])
110 }
111
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])
117 }
118
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])
123 }
124
125 PatKind::Struct(_, ref subpats, _) => {
126 let pats_exit =
127 self.pats_all(subpats.iter().map(|f| &f.node.pat), pred);
128 self.add_ast_node(pat.id, &[pats_exit])
129 }
130
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])
136 }
137 }
138 }
139
140 fn pats_all<'b, I: Iterator<Item=&'b P<hir::Pat>>>(&mut self,
141 pats: I,
142 pred: CFGIndex) -> CFGIndex {
143 //! Handles case where all of the patterns must match.
144 pats.fold(pred, |pred, pat| self.pat(&pat, pred))
145 }
146
147 fn expr(&mut self, expr: &hir::Expr, pred: CFGIndex) -> CFGIndex {
148 match expr.node {
149 hir::ExprBlock(ref blk) => {
150 let blk_exit = self.block(&blk, pred);
151 self.add_ast_node(expr.id, &[blk_exit])
152 }
153
154 hir::ExprIf(ref cond, ref then, None) => {
155 //
156 // [pred]
157 // |
158 // v 1
159 // [cond]
160 // |
161 // / \
162 // / \
163 // v 2 *
164 // [then] |
165 // | |
166 // v 3 v 4
167 // [..expr..]
168 //
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
172 }
173
174 hir::ExprIf(ref cond, ref then, Some(ref otherwise)) => {
175 //
176 // [pred]
177 // |
178 // v 1
179 // [cond]
180 // |
181 // / \
182 // / \
183 // v 2 v 3
184 // [then][otherwise]
185 // | |
186 // v 4 v 5
187 // [..expr..]
188 //
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
193 }
194
195 hir::ExprWhile(ref cond, ref body, _) => {
196 //
197 // [pred]
198 // |
199 // v 1
200 // [loopback] <--+ 5
201 // | |
202 // v 2 |
203 // +-----[cond] |
204 // | | |
205 // | v 4 |
206 // | [body] -----+
207 // v 3
208 // [expr]
209 //
210 // Note that `break` and `continue` statements
211 // may cause additional edges.
212
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 {
218 loop_id: expr.id,
219 continue_index: loopback,
220 break_index: expr_exit
221 });
222 let body_exit = self.block(&body, cond_exit); // 4
223 self.add_contained_edge(body_exit, loopback); // 5
224 self.loop_scopes.pop();
225 expr_exit
226 }
227
228 hir::ExprLoop(ref body, _) => {
229 //
230 // [pred]
231 // |
232 // v 1
233 // [loopback] <---+
234 // | 4 |
235 // v 3 |
236 // [body] ------+
237 //
238 // [expr] 2
239 //
240 // Note that `break` and `loop` statements
241 // may cause additional edges.
242
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 {
246 loop_id: expr.id,
247 continue_index: loopback,
248 break_index: expr_exit,
249 });
250 let body_exit = self.block(&body, loopback); // 3
251 self.add_contained_edge(body_exit, loopback); // 4
252 self.loop_scopes.pop();
253 expr_exit
254 }
255
256 hir::ExprMatch(ref discr, ref arms, _) => {
257 self.match_(expr.id, &discr, &arms, pred)
258 }
259
260 hir::ExprBinary(op, ref l, ref r) if op.node.is_lazy() => {
261 //
262 // [pred]
263 // |
264 // v 1
265 // [l]
266 // |
267 // / \
268 // / \
269 // v 2 *
270 // [r] |
271 // | |
272 // v 3 v 4
273 // [..exit..]
274 //
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
278 }
279
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()
285 }
286
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()
293 }
294
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()
301 }
302
303 hir::ExprVec(ref elems) => {
304 self.straightline(expr, pred, elems.iter().map(|e| &**e))
305 }
306
307 hir::ExprCall(ref func, ref args) => {
308 self.call(expr, pred, &func, args.iter().map(|e| &**e))
309 }
310
311 hir::ExprMethodCall(_, _, ref args) => {
312 self.call(expr, pred, &args[0], args[1..].iter().map(|e| &**e))
313 }
314
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())
318 }
319
320 hir::ExprUnary(_, ref e) if self.tcx.is_method_call(expr.id) => {
321 self.call(expr, pred, &e, None::<hir::Expr>.iter())
322 }
323
324 hir::ExprTup(ref exprs) => {
325 self.straightline(expr, pred, exprs.iter().map(|e| &**e))
326 }
327
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)
331 }
332
333 hir::ExprRepeat(ref elem, ref count) => {
334 self.straightline(expr, pred, [elem, count].iter().map(|&e| &**e))
335 }
336
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))
340 }
341
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))
345 }
346
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())
355 }
356
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])
361 }
362
363 hir::ExprClosure(..) |
364 hir::ExprLit(..) |
365 hir::ExprPath(..) => {
366 self.straightline(expr, pred, None::<hir::Expr>.iter())
367 }
368 }
369 }
370
371 fn call<'b, I: Iterator<Item=&'b hir::Expr>>(&mut self,
372 call_expr: &hir::Expr,
373 pred: CFGIndex,
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)
380 };
381
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()
386 } else {
387 ret
388 }
389 }
390
391 fn exprs<'b, I: Iterator<Item=&'b hir::Expr>>(&mut self,
392 exprs: I,
393 pred: CFGIndex) -> CFGIndex {
394 //! Constructs graph for `exprs` evaluated in order
395 exprs.fold(pred, |p, e| self.expr(e, p))
396 }
397
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))
403 }
404
405 fn straightline<'b, I: Iterator<Item=&'b hir::Expr>>(&mut self,
406 expr: &hir::Expr,
407 pred: CFGIndex,
408 subexprs: I) -> CFGIndex {
409 //! Handles case of an expression that evaluates `subexprs` in order
410
411 let subexprs_exit = self.exprs(subexprs, pred);
412 self.add_ast_node(expr.id, &[subexprs_exit])
413 }
414
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
418 // art for it (yet).
419 //
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.
429 //
430 // What is going on is explained in further comments.
431
432 // Visit the discriminant expression
433 let discr_exit = self.expr(discr, pred);
434
435 // Add a node for the exit of the match expression as a whole.
436 let expr_exit = self.add_ast_node(id, &[]);
437
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;
442
443 for arm in arms {
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(&[]);
447
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);
451
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);
459
460 let this_has_bindings = pat_util::pat_contains_bindings_or_wild(
461 &self.tcx.def_map.borrow(), &pat);
462
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
471 // `check_match`).
472 //
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
482 // sub-patterns.
483 //
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);
490 }
491 }
492
493 prev_has_bindings = this_has_bindings;
494
495 // Push the guard onto the list of previous guards
496 prev_guards.push(guard_exit);
497
498 // Update the exit node for the pattern
499 pat_exit = guard_exit;
500 }
501
502 // Add an edge from the exit of this pattern to the
503 // exit of the arm
504 self.add_contained_edge(pat_exit, arm_exit);
505 }
506
507 // Visit the body of this arm
508 let body_exit = self.expr(&arm.body, arm_exit);
509
510 // Link the body to the exit of the expression
511 self.add_contained_edge(body_exit, expr_exit);
512 }
513
514 expr_exit
515 }
516
517 fn add_dummy_node(&mut self, preds: &[CFGIndex]) -> CFGIndex {
518 self.add_node(CFGNodeData::Dummy, preds)
519 }
520
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)
524 }
525
526 fn add_unreachable_node(&mut self) -> CFGIndex {
527 self.add_node(CFGNodeData::Unreachable, &[])
528 }
529
530 fn add_node(&mut self, data: CFGNodeData, preds: &[CFGIndex]) -> CFGIndex {
531 let node = self.graph.add_node(data);
532 for &pred in preds {
533 self.add_contained_edge(pred, node);
534 }
535 node
536 }
537
538 fn add_contained_edge(&mut self,
539 source: CFGIndex,
540 target: CFGIndex) {
541 let data = CFGEdgeData {exiting_scopes: vec!() };
542 self.graph.add_edge(source, target, data);
543 }
544
545 fn add_exiting_edge(&mut self,
546 from_expr: &hir::Expr,
547 from_index: CFGIndex,
548 to_loop: LoopScope,
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);
556 }
557 self.graph.add_edge(from_index, to_index, data);
558 }
559
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!(),
565 };
566 for &LoopScope { loop_id: id, .. } in self.loop_scopes.iter().rev() {
567 data.exiting_scopes.push(id);
568 }
569 self.graph.add_edge(from_index, self.fn_exit, data);
570 }
571
572 fn find_scope(&self,
573 expr: &hir::Expr,
574 label: Option<ast::Name>) -> LoopScope {
575 if label.is_none() {
576 return *self.loop_scopes.last().unwrap();
577 }
578
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 {
583 return *l;
584 }
585 }
586 span_bug!(expr.span, "no loop scope for id {}", loop_id);
587 }
588
589 r => {
590 span_bug!(expr.span, "bad entry `{:?}` in def_map for label", r);
591 }
592 }
593 }
594 }