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