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 /*!
12 * A classic liveness analysis based on dataflow over the AST. Computes,
13 * for each local variable in a function, whether that variable is live
14 * at a given point. Program execution points are identified by their
15 * id.
16 *
17 * # Basic idea
18 *
19 * The basic model is that each local variable is assigned an index. We
20 * represent sets of local variables using a vector indexed by this
21 * index. The value in the vector is either 0, indicating the variable
22 * is dead, or the id of an expression that uses the variable.
23 *
24 * We conceptually walk over the AST in reverse execution order. If we
25 * find a use of a variable, we add it to the set of live variables. If
26 * we find an assignment to a variable, we remove it from the set of live
27 * variables. When we have to merge two flows, we take the union of
28 * those two flows---if the variable is live on both paths, we simply
29 * pick one id. In the event of loops, we continue doing this until a
30 * fixed point is reached.
31 *
32 * ## Checking initialization
33 *
34 * At the function entry point, all variables must be dead. If this is
35 * not the case, we can report an error using the id found in the set of
36 * live variables, which identifies a use of the variable which is not
37 * dominated by an assignment.
38 *
39 * ## Checking moves
40 *
41 * After each explicit move, the variable must be dead.
42 *
43 * ## Computing last uses
44 *
45 * Any use of the variable where the variable is dead afterwards is a
46 * last use.
47 *
48 * # Implementation details
49 *
50 * The actual implementation contains two (nested) walks over the AST.
51 * The outer walk has the job of building up the ir_maps instance for the
52 * enclosing function. On the way down the tree, it identifies those AST
53 * nodes and variable IDs that will be needed for the liveness analysis
54 * and assigns them contiguous IDs. The liveness id for an AST node is
55 * called a `live_node` (it's a newtype'd uint) and the id for a variable
56 * is called a `variable` (another newtype'd uint).
57 *
58 * On the way back up the tree, as we are about to exit from a function
59 * declaration we allocate a `liveness` instance. Now that we know
60 * precisely how many nodes and variables we need, we can allocate all
61 * the various arrays that we will need to precisely the right size. We then
62 * perform the actual propagation on the `liveness` instance.
63 *
64 * This propagation is encoded in the various `propagate_through_*()`
65 * methods. It effectively does a reverse walk of the AST; whenever we
66 * reach a loop node, we iterate until a fixed point is reached.
67 *
68 * ## The `Users` struct
69 *
70 * At each live node `N`, we track three pieces of information for each
71 * variable `V` (these are encapsulated in the `Users` struct):
72 *
73 * - `reader`: the `LiveNode` ID of some node which will read the value
74 * that `V` holds on entry to `N`. Formally: a node `M` such
75 * that there exists a path `P` from `N` to `M` where `P` does not
76 * write `V`. If the `reader` is `invalid_node()`, then the current
77 * value will never be read (the variable is dead, essentially).
78 *
79 * - `writer`: the `LiveNode` ID of some node which will write the
80 * variable `V` and which is reachable from `N`. Formally: a node `M`
81 * such that there exists a path `P` from `N` to `M` and `M` writes
82 * `V`. If the `writer` is `invalid_node()`, then there is no writer
83 * of `V` that follows `N`.
84 *
85 * - `used`: a boolean value indicating whether `V` is *used*. We
86 * distinguish a *read* from a *use* in that a *use* is some read that
87 * is not just used to generate a new value. For example, `x += 1` is
88 * a read but not a use. This is used to generate better warnings.
89 *
90 * ## Special Variables
91 *
92 * We generate various special variables for various, well, special purposes.
93 * These are described in the `specials` struct:
94 *
95 * - `exit_ln`: a live node that is generated to represent every 'exit' from
96 * the function, whether it be by explicit return, fail, or other means.
97 *
98 * - `fallthrough_ln`: a live node that represents a fallthrough
99 *
100 * - `no_ret_var`: a synthetic variable that is only 'read' from, the
101 * fallthrough node. This allows us to detect functions where we fail
102 * to return explicitly.
103 */
104
105
106 use middle::freevars;
107 use middle::lint::{UnusedVariable, DeadAssignment};
108 use middle::pat_util;
109 use middle::ty;
110 use util::nodemap::NodeMap;
111
112 use std::cast::transmute;
113 use std::fmt;
114 use std::io;
115 use std::rc::Rc;
116 use std::str;
117 use std::uint;
118 use syntax::ast::*;
119 use syntax::codemap::{BytePos, original_sp, Span};
120 use syntax::parse::token::special_idents;
121 use syntax::parse::token;
122 use syntax::print::pprust::{expr_to_str, block_to_str};
123 use syntax::{visit, ast_util};
124 use syntax::visit::{Visitor, FnKind};
125
126 #[deriving(Eq)]
127 struct Variable(uint);
128 #[deriving(Eq)]
129 struct LiveNode(uint);
130
131 impl Variable {
132 fn get(&self) -> uint { let Variable(v) = *self; v }
133 }
134
135 impl LiveNode {
136 fn get(&self) -> uint { let LiveNode(v) = *self; v }
137 }
138
139 impl Clone for LiveNode {
140 fn clone(&self) -> LiveNode {
141 LiveNode(self.get())
142 }
143 }
144
145 #[deriving(Eq)]
146 enum LiveNodeKind {
147 FreeVarNode(Span),
148 ExprNode(Span),
149 VarDefNode(Span),
150 ExitNode
151 }
152
153 fn live_node_kind_to_str(lnk: LiveNodeKind, cx: &ty::ctxt) -> ~str {
154 let cm = cx.sess.codemap();
155 match lnk {
156 FreeVarNode(s) => format!("Free var node [{}]", cm.span_to_str(s)),
157 ExprNode(s) => format!("Expr node [{}]", cm.span_to_str(s)),
158 VarDefNode(s) => format!("Var def node [{}]", cm.span_to_str(s)),
159 ExitNode => "Exit node".to_owned()
160 }
161 }
162
163 impl<'a> Visitor<()> for IrMaps<'a> {
164 fn visit_fn(&mut self, fk: &FnKind, fd: &FnDecl, b: &Block, s: Span, n: NodeId, _: ()) {
165 visit_fn(self, fk, fd, b, s, n);
166 }
167 fn visit_local(&mut self, l: &Local, _: ()) { visit_local(self, l); }
168 fn visit_expr(&mut self, ex: &Expr, _: ()) { visit_expr(self, ex); }
169 fn visit_arm(&mut self, a: &Arm, _: ()) { visit_arm(self, a); }
170 }
171
172 pub fn check_crate(tcx: &ty::ctxt,
173 krate: &Crate) {
174 visit::walk_crate(&mut IrMaps(tcx), krate, ());
175 tcx.sess.abort_if_errors();
176 }
177
178 impl fmt::Show for LiveNode {
179 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
180 write!(f.buf, "ln({})", self.get())
181 }
182 }
183
184 impl fmt::Show for Variable {
185 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
186 write!(f.buf, "v({})", self.get())
187 }
188 }
189
190 // ______________________________________________________________________
191 // Creating ir_maps
192 //
193 // This is the first pass and the one that drives the main
194 // computation. It walks up and down the IR once. On the way down,
195 // we count for each function the number of variables as well as
196 // liveness nodes. A liveness node is basically an expression or
197 // capture clause that does something of interest: either it has
198 // interesting control flow or it uses/defines a local variable.
199 //
200 // On the way back up, at each function node we create liveness sets
201 // (we now know precisely how big to make our various vectors and so
202 // forth) and then do the data-flow propagation to compute the set
203 // of live variables at each program point.
204 //
205 // Finally, we run back over the IR one last time and, using the
206 // computed liveness, check various safety conditions. For example,
207 // there must be no live nodes at the definition site for a variable
208 // unless it has an initializer. Similarly, each non-mutable local
209 // variable must not be assigned if there is some successor
210 // assignment. And so forth.
211
212 impl LiveNode {
213 fn is_valid(&self) -> bool {
214 self.get() != uint::MAX
215 }
216 }
217
218 fn invalid_node() -> LiveNode { LiveNode(uint::MAX) }
219
220 struct CaptureInfo {
221 ln: LiveNode,
222 is_move: bool,
223 var_nid: NodeId
224 }
225
226 enum LocalKind {
227 FromMatch(BindingMode),
228 FromLetWithInitializer,
229 FromLetNoInitializer
230 }
231
232 struct LocalInfo {
233 id: NodeId,
234 ident: Ident,
235 is_mutbl: bool,
236 kind: LocalKind,
237 }
238
239 enum VarKind {
240 Arg(NodeId, Ident),
241 Local(LocalInfo),
242 ImplicitRet
243 }
244
245 struct IrMaps<'a> {
246 tcx: &'a ty::ctxt,
247
248 num_live_nodes: uint,
249 num_vars: uint,
250 live_node_map: NodeMap<LiveNode>,
251 variable_map: NodeMap<Variable>,
252 capture_info_map: NodeMap<Rc<Vec<CaptureInfo>>>,
253 var_kinds: Vec<VarKind>,
254 lnks: Vec<LiveNodeKind>,
255 }
256
257 fn IrMaps<'a>(tcx: &'a ty::ctxt)
258 -> IrMaps<'a> {
259 IrMaps {
260 tcx: tcx,
261 num_live_nodes: 0,
262 num_vars: 0,
263 live_node_map: NodeMap::new(),
264 variable_map: NodeMap::new(),
265 capture_info_map: NodeMap::new(),
266 var_kinds: Vec::new(),
267 lnks: Vec::new(),
268 }
269 }
270
271 impl<'a> IrMaps<'a> {
272 fn add_live_node(&mut self, lnk: LiveNodeKind) -> LiveNode {
273 let ln = LiveNode(self.num_live_nodes);
274 self.lnks.push(lnk);
275 self.num_live_nodes += 1;
276
277 debug!("{} is of kind {}", ln.to_str(),
278 live_node_kind_to_str(lnk, self.tcx));
279
280 ln
281 }
282
283 fn add_live_node_for_node(&mut self, node_id: NodeId, lnk: LiveNodeKind) {
284 let ln = self.add_live_node(lnk);
285 self.live_node_map.insert(node_id, ln);
286
287 debug!("{} is node {}", ln.to_str(), node_id);
288 }
289
290 fn add_variable(&mut self, vk: VarKind) -> Variable {
291 let v = Variable(self.num_vars);
292 self.var_kinds.push(vk);
293 self.num_vars += 1;
294
295 match vk {
296 Local(LocalInfo { id: node_id, .. }) | Arg(node_id, _) => {
297 self.variable_map.insert(node_id, v);
298 },
299 ImplicitRet => {}
300 }
301
302 debug!("{} is {:?}", v.to_str(), vk);
303
304 v
305 }
306
307 fn variable(&self, node_id: NodeId, span: Span) -> Variable {
308 match self.variable_map.find(&node_id) {
309 Some(&var) => var,
310 None => {
311 self.tcx.sess.span_bug(
312 span, format!("no variable registered for id {}", node_id));
313 }
314 }
315 }
316
317 fn variable_name(&self, var: Variable) -> ~str {
318 match self.var_kinds.get(var.get()) {
319 &Local(LocalInfo { ident: nm, .. }) | &Arg(_, nm) => {
320 token::get_ident(nm).get().to_str()
321 },
322 &ImplicitRet => "<implicit-ret>".to_owned()
323 }
324 }
325
326 fn set_captures(&mut self, node_id: NodeId, cs: Vec<CaptureInfo>) {
327 self.capture_info_map.insert(node_id, Rc::new(cs));
328 }
329
330 fn lnk(&self, ln: LiveNode) -> LiveNodeKind {
331 *self.lnks.get(ln.get())
332 }
333 }
334
335 impl<'a> Visitor<()> for Liveness<'a> {
336 fn visit_fn(&mut self, fk: &FnKind, fd: &FnDecl, b: &Block, s: Span, n: NodeId, _: ()) {
337 check_fn(self, fk, fd, b, s, n);
338 }
339 fn visit_local(&mut self, l: &Local, _: ()) {
340 check_local(self, l);
341 }
342 fn visit_expr(&mut self, ex: &Expr, _: ()) {
343 check_expr(self, ex);
344 }
345 fn visit_arm(&mut self, a: &Arm, _: ()) {
346 check_arm(self, a);
347 }
348 }
349
350 fn visit_fn(ir: &mut IrMaps,
351 fk: &FnKind,
352 decl: &FnDecl,
353 body: &Block,
354 sp: Span,
355 id: NodeId) {
356 debug!("visit_fn: id={}", id);
357 let _i = ::util::common::indenter();
358
359 // swap in a new set of IR maps for this function body:
360 let mut fn_maps = IrMaps(ir.tcx);
361
362 unsafe {
363 debug!("creating fn_maps: {}", transmute::<&IrMaps, *IrMaps>(&fn_maps));
364 }
365
366 for arg in decl.inputs.iter() {
367 pat_util::pat_bindings(&ir.tcx.def_map,
368 arg.pat,
369 |_bm, arg_id, _x, path| {
370 debug!("adding argument {}", arg_id);
371 let ident = ast_util::path_to_ident(path);
372 fn_maps.add_variable(Arg(arg_id, ident));
373 })
374 };
375
376 // gather up the various local variables, significant expressions,
377 // and so forth:
378 visit::walk_fn(&mut fn_maps, fk, decl, body, sp, id, ());
379
380 // Special nodes and variables:
381 // - exit_ln represents the end of the fn, either by return or fail
382 // - implicit_ret_var is a pseudo-variable that represents
383 // an implicit return
384 let specials = Specials {
385 exit_ln: fn_maps.add_live_node(ExitNode),
386 fallthrough_ln: fn_maps.add_live_node(ExitNode),
387 no_ret_var: fn_maps.add_variable(ImplicitRet)
388 };
389
390 // compute liveness
391 let mut lsets = Liveness(&mut fn_maps, specials);
392 let entry_ln = lsets.compute(decl, body);
393
394 // check for various error conditions
395 lsets.visit_block(body, ());
396 lsets.check_ret(id, sp, fk, entry_ln, body);
397 lsets.warn_about_unused_args(decl, entry_ln);
398 }
399
400 fn visit_local(ir: &mut IrMaps, local: &Local) {
401 pat_util::pat_bindings(&ir.tcx.def_map, local.pat, |bm, p_id, sp, path| {
402 debug!("adding local variable {}", p_id);
403 let name = ast_util::path_to_ident(path);
404 ir.add_live_node_for_node(p_id, VarDefNode(sp));
405 let kind = match local.init {
406 Some(_) => FromLetWithInitializer,
407 None => FromLetNoInitializer
408 };
409 let mutbl = match bm {
410 BindByValue(MutMutable) => true,
411 _ => false
412 };
413 ir.add_variable(Local(LocalInfo {
414 id: p_id,
415 ident: name,
416 is_mutbl: mutbl,
417 kind: kind
418 }));
419 });
420 visit::walk_local(ir, local, ());
421 }
422
423 fn visit_arm(ir: &mut IrMaps, arm: &Arm) {
424 for pat in arm.pats.iter() {
425 pat_util::pat_bindings(&ir.tcx.def_map, *pat, |bm, p_id, sp, path| {
426 debug!("adding local variable {} from match with bm {:?}",
427 p_id, bm);
428 let name = ast_util::path_to_ident(path);
429 let mutbl = match bm {
430 BindByValue(MutMutable) => true,
431 _ => false
432 };
433 ir.add_live_node_for_node(p_id, VarDefNode(sp));
434 ir.add_variable(Local(LocalInfo {
435 id: p_id,
436 ident: name,
437 is_mutbl: mutbl,
438 kind: FromMatch(bm)
439 }));
440 })
441 }
442 visit::walk_arm(ir, arm, ());
443 }
444
445 fn moved_variable_node_id_from_def(def: Def) -> Option<NodeId> {
446 match def {
447 DefBinding(nid, _) |
448 DefArg(nid, _) |
449 DefLocal(nid, _) => Some(nid),
450
451 _ => None
452 }
453 }
454
455 fn visit_expr(ir: &mut IrMaps, expr: &Expr) {
456 match expr.node {
457 // live nodes required for uses or definitions of variables:
458 ExprPath(_) => {
459 let def = ir.tcx.def_map.borrow().get_copy(&expr.id);
460 debug!("expr {}: path that leads to {:?}", expr.id, def);
461 if moved_variable_node_id_from_def(def).is_some() {
462 ir.add_live_node_for_node(expr.id, ExprNode(expr.span));
463 }
464 visit::walk_expr(ir, expr, ());
465 }
466 ExprFnBlock(..) | ExprProc(..) => {
467 // Interesting control flow (for loops can contain labeled
468 // breaks or continues)
469 ir.add_live_node_for_node(expr.id, ExprNode(expr.span));
470
471 // Make a live_node for each captured variable, with the span
472 // being the location that the variable is used. This results
473 // in better error messages than just pointing at the closure
474 // construction site.
475 let mut call_caps = Vec::new();
476 let fv_mode = freevars::get_capture_mode(ir.tcx, expr.id);
477 freevars::with_freevars(ir.tcx, expr.id, |freevars| {
478 for fv in freevars.iter() {
479 match moved_variable_node_id_from_def(fv.def) {
480 Some(rv) => {
481 let fv_ln = ir.add_live_node(FreeVarNode(fv.span));
482 let fv_id = ast_util::def_id_of_def(fv.def).node;
483 let fv_ty = ty::node_id_to_type(ir.tcx, fv_id);
484 let is_move = match fv_mode {
485 // var must be dead afterwards
486 freevars::CaptureByValue => {
487 ty::type_moves_by_default(ir.tcx, fv_ty)
488 }
489
490 // var can still be used
491 freevars::CaptureByRef => {
492 false
493 }
494 };
495 call_caps.push(CaptureInfo {ln: fv_ln,
496 is_move: is_move,
497 var_nid: rv});
498 }
499 None => {}
500 }
501 }
502 });
503 ir.set_captures(expr.id, call_caps);
504
505 visit::walk_expr(ir, expr, ());
506 }
507
508 // live nodes required for interesting control flow:
509 ExprIf(..) | ExprMatch(..) | ExprWhile(..) | ExprLoop(..) => {
510 ir.add_live_node_for_node(expr.id, ExprNode(expr.span));
511 visit::walk_expr(ir, expr, ());
512 }
513 ExprForLoop(..) => fail!("non-desugared expr_for_loop"),
514 ExprBinary(op, _, _) if ast_util::lazy_binop(op) => {
515 ir.add_live_node_for_node(expr.id, ExprNode(expr.span));
516 visit::walk_expr(ir, expr, ());
517 }
518
519 // otherwise, live nodes are not required:
520 ExprIndex(..) | ExprField(..) | ExprVstore(..) | ExprVec(..) |
521 ExprCall(..) | ExprMethodCall(..) | ExprTup(..) |
522 ExprBinary(..) | ExprAddrOf(..) |
523 ExprCast(..) | ExprUnary(..) | ExprBreak(_) |
524 ExprAgain(_) | ExprLit(_) | ExprRet(..) | ExprBlock(..) |
525 ExprAssign(..) | ExprAssignOp(..) | ExprMac(..) |
526 ExprStruct(..) | ExprRepeat(..) | ExprParen(..) |
527 ExprInlineAsm(..) | ExprBox(..) => {
528 visit::walk_expr(ir, expr, ());
529 }
530 }
531 }
532
533 // ______________________________________________________________________
534 // Computing liveness sets
535 //
536 // Actually we compute just a bit more than just liveness, but we use
537 // the same basic propagation framework in all cases.
538
539 #[deriving(Clone)]
540 struct Users {
541 reader: LiveNode,
542 writer: LiveNode,
543 used: bool
544 }
545
546 fn invalid_users() -> Users {
547 Users {
548 reader: invalid_node(),
549 writer: invalid_node(),
550 used: false
551 }
552 }
553
554 struct Specials {
555 exit_ln: LiveNode,
556 fallthrough_ln: LiveNode,
557 no_ret_var: Variable
558 }
559
560 static ACC_READ: uint = 1u;
561 static ACC_WRITE: uint = 2u;
562 static ACC_USE: uint = 4u;
563
564 struct Liveness<'a> {
565 ir: &'a mut IrMaps<'a>,
566 s: Specials,
567 successors: Vec<LiveNode>,
568 users: Vec<Users>,
569 // The list of node IDs for the nested loop scopes
570 // we're in.
571 loop_scope: Vec<NodeId>,
572 // mappings from loop node ID to LiveNode
573 // ("break" label should map to loop node ID,
574 // it probably doesn't now)
575 break_ln: NodeMap<LiveNode>,
576 cont_ln: NodeMap<LiveNode>
577 }
578
579 fn Liveness<'a>(ir: &'a mut IrMaps<'a>, specials: Specials) -> Liveness<'a> {
580 Liveness {
581 ir: ir,
582 s: specials,
583 successors: Vec::from_elem(ir.num_live_nodes, invalid_node()),
584 users: Vec::from_elem(ir.num_live_nodes * ir.num_vars, invalid_users()),
585 loop_scope: Vec::new(),
586 break_ln: NodeMap::new(),
587 cont_ln: NodeMap::new(),
588 }
589 }
590
591 impl<'a> Liveness<'a> {
592 fn live_node(&self, node_id: NodeId, span: Span) -> LiveNode {
593 match self.ir.live_node_map.find(&node_id) {
594 Some(&ln) => ln,
595 None => {
596 // This must be a mismatch between the ir_map construction
597 // above and the propagation code below; the two sets of
598 // code have to agree about which AST nodes are worth
599 // creating liveness nodes for.
600 self.ir.tcx.sess.span_bug(
601 span, format!("no live node registered for node {}",
602 node_id));
603 }
604 }
605 }
606
607 fn variable(&self, node_id: NodeId, span: Span) -> Variable {
608 self.ir.variable(node_id, span)
609 }
610
611 fn pat_bindings(&mut self,
612 pat: &Pat,
613 f: |&mut Liveness<'a>, LiveNode, Variable, Span, NodeId|) {
614 pat_util::pat_bindings(&self.ir.tcx.def_map, pat, |_bm, p_id, sp, _n| {
615 let ln = self.live_node(p_id, sp);
616 let var = self.variable(p_id, sp);
617 f(self, ln, var, sp, p_id);
618 })
619 }
620
621 fn arm_pats_bindings(&mut self,
622 pats: &[@Pat],
623 f: |&mut Liveness<'a>, LiveNode, Variable, Span, NodeId|) {
624 // only consider the first pattern; any later patterns must have
625 // the same bindings, and we also consider the first pattern to be
626 // the "authoritative" set of ids
627 if !pats.is_empty() {
628 self.pat_bindings(pats[0], f)
629 }
630 }
631
632 fn define_bindings_in_pat(&mut self, pat: @Pat, succ: LiveNode)
633 -> LiveNode {
634 self.define_bindings_in_arm_pats([pat], succ)
635 }
636
637 fn define_bindings_in_arm_pats(&mut self, pats: &[@Pat], succ: LiveNode)
638 -> LiveNode {
639 let mut succ = succ;
640 self.arm_pats_bindings(pats, |this, ln, var, _sp, _id| {
641 this.init_from_succ(ln, succ);
642 this.define(ln, var);
643 succ = ln;
644 });
645 succ
646 }
647
648 fn idx(&self, ln: LiveNode, var: Variable) -> uint {
649 ln.get() * self.ir.num_vars + var.get()
650 }
651
652 fn live_on_entry(&self, ln: LiveNode, var: Variable)
653 -> Option<LiveNodeKind> {
654 assert!(ln.is_valid());
655 let reader = self.users.get(self.idx(ln, var)).reader;
656 if reader.is_valid() {Some(self.ir.lnk(reader))} else {None}
657 }
658
659 /*
660 Is this variable live on entry to any of its successor nodes?
661 */
662 fn live_on_exit(&self, ln: LiveNode, var: Variable)
663 -> Option<LiveNodeKind> {
664 let successor = *self.successors.get(ln.get());
665 self.live_on_entry(successor, var)
666 }
667
668 fn used_on_entry(&self, ln: LiveNode, var: Variable) -> bool {
669 assert!(ln.is_valid());
670 self.users.get(self.idx(ln, var)).used
671 }
672
673 fn assigned_on_entry(&self, ln: LiveNode, var: Variable)
674 -> Option<LiveNodeKind> {
675 assert!(ln.is_valid());
676 let writer = self.users.get(self.idx(ln, var)).writer;
677 if writer.is_valid() {Some(self.ir.lnk(writer))} else {None}
678 }
679
680 fn assigned_on_exit(&self, ln: LiveNode, var: Variable)
681 -> Option<LiveNodeKind> {
682 let successor = *self.successors.get(ln.get());
683 self.assigned_on_entry(successor, var)
684 }
685
686 fn indices2(&mut self,
687 ln: LiveNode,
688 succ_ln: LiveNode,
689 op: |&mut Liveness<'a>, uint, uint|) {
690 let node_base_idx = self.idx(ln, Variable(0u));
691 let succ_base_idx = self.idx(succ_ln, Variable(0u));
692 for var_idx in range(0u, self.ir.num_vars) {
693 op(self, node_base_idx + var_idx, succ_base_idx + var_idx);
694 }
695 }
696
697 fn write_vars(&self,
698 wr: &mut io::Writer,
699 ln: LiveNode,
700 test: |uint| -> LiveNode) -> io::IoResult<()> {
701 let node_base_idx = self.idx(ln, Variable(0));
702 for var_idx in range(0u, self.ir.num_vars) {
703 let idx = node_base_idx + var_idx;
704 if test(idx).is_valid() {
705 try!(write!(wr, " {}", Variable(var_idx).to_str()));
706 }
707 }
708 Ok(())
709 }
710
711 fn find_loop_scope(&self,
712 opt_label: Option<Ident>,
713 id: NodeId,
714 sp: Span)
715 -> NodeId {
716 match opt_label {
717 Some(_) => {
718 // Refers to a labeled loop. Use the results of resolve
719 // to find with one
720 match self.ir.tcx.def_map.borrow().find(&id) {
721 Some(&DefLabel(loop_id)) => loop_id,
722 _ => self.ir.tcx.sess.span_bug(sp, "label on break/loop \
723 doesn't refer to a loop")
724 }
725 }
726 None => {
727 // Vanilla 'break' or 'loop', so use the enclosing
728 // loop scope
729 if self.loop_scope.len() == 0 {
730 self.ir.tcx.sess.span_bug(sp, "break outside loop");
731 } else {
732 // FIXME(#5275): this shouldn't have to be a method...
733 self.last_loop_scope()
734 }
735 }
736 }
737 }
738
739 fn last_loop_scope(&self) -> NodeId {
740 *self.loop_scope.last().unwrap()
741 }
742
743 #[allow(unused_must_use)]
744 fn ln_str(&self, ln: LiveNode) -> ~str {
745 let mut wr = io::MemWriter::new();
746 {
747 let wr = &mut wr as &mut io::Writer;
748 write!(wr, "[ln({}) of kind {:?} reads", ln.get(), self.ir.lnk(ln));
749 self.write_vars(wr, ln, |idx| self.users.get(idx).reader);
750 write!(wr, " writes");
751 self.write_vars(wr, ln, |idx| self.users.get(idx).writer);
752 write!(wr, " precedes {}]", self.successors.get(ln.get()).to_str());
753 }
754 str::from_utf8(wr.unwrap().as_slice()).unwrap().to_owned()
755 }
756
757 fn init_empty(&mut self, ln: LiveNode, succ_ln: LiveNode) {
758 *self.successors.get_mut(ln.get()) = succ_ln;
759
760 // It is not necessary to initialize the
761 // values to empty because this is the value
762 // they have when they are created, and the sets
763 // only grow during iterations.
764 //
765 // self.indices(ln) { |idx|
766 // self.users[idx] = invalid_users();
767 // }
768 }
769
770 fn init_from_succ(&mut self, ln: LiveNode, succ_ln: LiveNode) {
771 // more efficient version of init_empty() / merge_from_succ()
772 *self.successors.get_mut(ln.get()) = succ_ln;
773
774 self.indices2(ln, succ_ln, |this, idx, succ_idx| {
775 *this.users.get_mut(idx) = *this.users.get(succ_idx)
776 });
777 debug!("init_from_succ(ln={}, succ={})",
778 self.ln_str(ln), self.ln_str(succ_ln));
779 }
780
781 fn merge_from_succ(&mut self,
782 ln: LiveNode,
783 succ_ln: LiveNode,
784 first_merge: bool)
785 -> bool {
786 if ln == succ_ln { return false; }
787
788 let mut changed = false;
789 self.indices2(ln, succ_ln, |this, idx, succ_idx| {
790 changed |= copy_if_invalid(this.users.get(succ_idx).reader,
791 &mut this.users.get_mut(idx).reader);
792 changed |= copy_if_invalid(this.users.get(succ_idx).writer,
793 &mut this.users.get_mut(idx).writer);
794 if this.users.get(succ_idx).used && !this.users.get(idx).used {
795 this.users.get_mut(idx).used = true;
796 changed = true;
797 }
798 });
799
800 debug!("merge_from_succ(ln={}, succ={}, first_merge={}, changed={})",
801 ln.to_str(), self.ln_str(succ_ln), first_merge, changed);
802 return changed;
803
804 fn copy_if_invalid(src: LiveNode, dst: &mut LiveNode) -> bool {
805 if src.is_valid() && !dst.is_valid() {
806 *dst = src;
807 true
808 } else {
809 false
810 }
811 }
812 }
813
814 // Indicates that a local variable was *defined*; we know that no
815 // uses of the variable can precede the definition (resolve checks
816 // this) so we just clear out all the data.
817 fn define(&mut self, writer: LiveNode, var: Variable) {
818 let idx = self.idx(writer, var);
819 self.users.get_mut(idx).reader = invalid_node();
820 self.users.get_mut(idx).writer = invalid_node();
821
822 debug!("{} defines {} (idx={}): {}", writer.to_str(), var.to_str(),
823 idx, self.ln_str(writer));
824 }
825
826 // Either read, write, or both depending on the acc bitset
827 fn acc(&mut self, ln: LiveNode, var: Variable, acc: uint) {
828 debug!("{} accesses[{:x}] {}: {}",
829 ln.to_str(), acc, var.to_str(), self.ln_str(ln));
830
831 let idx = self.idx(ln, var);
832 let user = self.users.get_mut(idx);
833
834 if (acc & ACC_WRITE) != 0 {
835 user.reader = invalid_node();
836 user.writer = ln;
837 }
838
839 // Important: if we both read/write, must do read second
840 // or else the write will override.
841 if (acc & ACC_READ) != 0 {
842 user.reader = ln;
843 }
844
845 if (acc & ACC_USE) != 0 {
846 user.used = true;
847 }
848 }
849
850 // _______________________________________________________________________
851
852 fn compute(&mut self, decl: &FnDecl, body: &Block) -> LiveNode {
853 // if there is a `break` or `again` at the top level, then it's
854 // effectively a return---this only occurs in `for` loops,
855 // where the body is really a closure.
856
857 debug!("compute: using id for block, {}", block_to_str(body));
858
859 let entry_ln: LiveNode =
860 self.with_loop_nodes(body.id, self.s.exit_ln, self.s.exit_ln,
861 |this| this.propagate_through_fn_block(decl, body));
862
863 // hack to skip the loop unless debug! is enabled:
864 debug!("^^ liveness computation results for body {} (entry={})",
865 {
866 for ln_idx in range(0u, self.ir.num_live_nodes) {
867 debug!("{}", self.ln_str(LiveNode(ln_idx)));
868 }
869 body.id
870 },
871 entry_ln.to_str());
872
873 entry_ln
874 }
875
876 fn propagate_through_fn_block(&mut self, _: &FnDecl, blk: &Block)
877 -> LiveNode {
878 // the fallthrough exit is only for those cases where we do not
879 // explicitly return:
880 self.init_from_succ(self.s.fallthrough_ln, self.s.exit_ln);
881 if blk.expr.is_none() {
882 self.acc(self.s.fallthrough_ln, self.s.no_ret_var, ACC_READ)
883 }
884
885 self.propagate_through_block(blk, self.s.fallthrough_ln)
886 }
887
888 fn propagate_through_block(&mut self, blk: &Block, succ: LiveNode)
889 -> LiveNode {
890 let succ = self.propagate_through_opt_expr(blk.expr, succ);
891 blk.stmts.iter().rev().fold(succ, |succ, stmt| {
892 self.propagate_through_stmt(*stmt, succ)
893 })
894 }
895
896 fn propagate_through_stmt(&mut self, stmt: &Stmt, succ: LiveNode)
897 -> LiveNode {
898 match stmt.node {
899 StmtDecl(decl, _) => {
900 self.propagate_through_decl(decl, succ)
901 }
902
903 StmtExpr(expr, _) | StmtSemi(expr, _) => {
904 self.propagate_through_expr(expr, succ)
905 }
906
907 StmtMac(..) => {
908 self.ir.tcx.sess.span_bug(stmt.span, "unexpanded macro");
909 }
910 }
911 }
912
913 fn propagate_through_decl(&mut self, decl: &Decl, succ: LiveNode)
914 -> LiveNode {
915 match decl.node {
916 DeclLocal(ref local) => {
917 self.propagate_through_local(*local, succ)
918 }
919 DeclItem(_) => succ,
920 }
921 }
922
923 fn propagate_through_local(&mut self, local: &Local, succ: LiveNode)
924 -> LiveNode {
925 // Note: we mark the variable as defined regardless of whether
926 // there is an initializer. Initially I had thought to only mark
927 // the live variable as defined if it was initialized, and then we
928 // could check for uninit variables just by scanning what is live
929 // at the start of the function. But that doesn't work so well for
930 // immutable variables defined in a loop:
931 // loop { let x; x = 5; }
932 // because the "assignment" loops back around and generates an error.
933 //
934 // So now we just check that variables defined w/o an
935 // initializer are not live at the point of their
936 // initialization, which is mildly more complex than checking
937 // once at the func header but otherwise equivalent.
938
939 let succ = self.propagate_through_opt_expr(local.init, succ);
940 self.define_bindings_in_pat(local.pat, succ)
941 }
942
943 fn propagate_through_exprs(&mut self, exprs: &[@Expr], succ: LiveNode)
944 -> LiveNode {
945 exprs.iter().rev().fold(succ, |succ, expr| {
946 self.propagate_through_expr(*expr, succ)
947 })
948 }
949
950 fn propagate_through_opt_expr(&mut self,
951 opt_expr: Option<@Expr>,
952 succ: LiveNode)
953 -> LiveNode {
954 opt_expr.iter().fold(succ, |succ, expr| {
955 self.propagate_through_expr(*expr, succ)
956 })
957 }
958
959 fn propagate_through_expr(&mut self, expr: &Expr, succ: LiveNode)
960 -> LiveNode {
961 debug!("propagate_through_expr: {}", expr_to_str(expr));
962
963 match expr.node {
964 // Interesting cases with control flow or which gen/kill
965
966 ExprPath(_) => {
967 self.access_path(expr, succ, ACC_READ | ACC_USE)
968 }
969
970 ExprField(e, _, _) => {
971 self.propagate_through_expr(e, succ)
972 }
973
974 ExprFnBlock(_, blk) | ExprProc(_, blk) => {
975 debug!("{} is an ExprFnBlock or ExprProc", expr_to_str(expr));
976
977 /*
978 The next-node for a break is the successor of the entire
979 loop. The next-node for a continue is the top of this loop.
980 */
981 let node = self.live_node(expr.id, expr.span);
982 self.with_loop_nodes(blk.id, succ, node, |this| {
983
984 // the construction of a closure itself is not important,
985 // but we have to consider the closed over variables.
986 let caps = match this.ir.capture_info_map.find(&expr.id) {
987 Some(caps) => caps.clone(),
988 None => {
989 this.ir.tcx.sess.span_bug(expr.span, "no registered caps");
990 }
991 };
992 caps.iter().rev().fold(succ, |succ, cap| {
993 this.init_from_succ(cap.ln, succ);
994 let var = this.variable(cap.var_nid, expr.span);
995 this.acc(cap.ln, var, ACC_READ | ACC_USE);
996 cap.ln
997 })
998 })
999 }
1000
1001 ExprIf(cond, then, els) => {
1002 //
1003 // (cond)
1004 // |
1005 // v
1006 // (expr)
1007 // / \
1008 // | |
1009 // v v
1010 // (then)(els)
1011 // | |
1012 // v v
1013 // ( succ )
1014 //
1015 let else_ln = self.propagate_through_opt_expr(els, succ);
1016 let then_ln = self.propagate_through_block(then, succ);
1017 let ln = self.live_node(expr.id, expr.span);
1018 self.init_from_succ(ln, else_ln);
1019 self.merge_from_succ(ln, then_ln, false);
1020 self.propagate_through_expr(cond, ln)
1021 }
1022
1023 ExprWhile(cond, blk) => {
1024 self.propagate_through_loop(expr, Some(cond), blk, succ)
1025 }
1026
1027 ExprForLoop(..) => fail!("non-desugared expr_for_loop"),
1028
1029 // Note that labels have been resolved, so we don't need to look
1030 // at the label ident
1031 ExprLoop(blk, _) => {
1032 self.propagate_through_loop(expr, None, blk, succ)
1033 }
1034
1035 ExprMatch(e, ref arms) => {
1036 //
1037 // (e)
1038 // |
1039 // v
1040 // (expr)
1041 // / | \
1042 // | | |
1043 // v v v
1044 // (..arms..)
1045 // | | |
1046 // v v v
1047 // ( succ )
1048 //
1049 //
1050 let ln = self.live_node(expr.id, expr.span);
1051 self.init_empty(ln, succ);
1052 let mut first_merge = true;
1053 for arm in arms.iter() {
1054 let body_succ =
1055 self.propagate_through_expr(arm.body, succ);
1056 let guard_succ =
1057 self.propagate_through_opt_expr(arm.guard, body_succ);
1058 let arm_succ =
1059 self.define_bindings_in_arm_pats(arm.pats.as_slice(),
1060 guard_succ);
1061 self.merge_from_succ(ln, arm_succ, first_merge);
1062 first_merge = false;
1063 };
1064 self.propagate_through_expr(e, ln)
1065 }
1066
1067 ExprRet(o_e) => {
1068 // ignore succ and subst exit_ln:
1069 self.propagate_through_opt_expr(o_e, self.s.exit_ln)
1070 }
1071
1072 ExprBreak(opt_label) => {
1073 // Find which label this break jumps to
1074 let sc = self.find_loop_scope(opt_label, expr.id, expr.span);
1075
1076 // Now that we know the label we're going to,
1077 // look it up in the break loop nodes table
1078
1079 match self.break_ln.find(&sc) {
1080 Some(&b) => b,
1081 None => self.ir.tcx.sess.span_bug(expr.span,
1082 "break to unknown label")
1083 }
1084 }
1085
1086 ExprAgain(opt_label) => {
1087 // Find which label this expr continues to
1088 let sc = self.find_loop_scope(opt_label, expr.id, expr.span);
1089
1090 // Now that we know the label we're going to,
1091 // look it up in the continue loop nodes table
1092
1093 match self.cont_ln.find(&sc) {
1094 Some(&b) => b,
1095 None => self.ir.tcx.sess.span_bug(expr.span,
1096 "loop to unknown label")
1097 }
1098 }
1099
1100 ExprAssign(l, r) => {
1101 // see comment on lvalues in
1102 // propagate_through_lvalue_components()
1103 let succ = self.write_lvalue(l, succ, ACC_WRITE);
1104 let succ = self.propagate_through_lvalue_components(l, succ);
1105 self.propagate_through_expr(r, succ)
1106 }
1107
1108 ExprAssignOp(_, l, r) => {
1109 // see comment on lvalues in
1110 // propagate_through_lvalue_components()
1111 let succ = self.write_lvalue(l, succ, ACC_WRITE|ACC_READ);
1112 let succ = self.propagate_through_expr(r, succ);
1113 self.propagate_through_lvalue_components(l, succ)
1114 }
1115
1116 // Uninteresting cases: just propagate in rev exec order
1117
1118 ExprVstore(expr, _) => {
1119 self.propagate_through_expr(expr, succ)
1120 }
1121
1122 ExprVec(ref exprs) => {
1123 self.propagate_through_exprs(exprs.as_slice(), succ)
1124 }
1125
1126 ExprRepeat(element, count) => {
1127 let succ = self.propagate_through_expr(count, succ);
1128 self.propagate_through_expr(element, succ)
1129 }
1130
1131 ExprStruct(_, ref fields, with_expr) => {
1132 let succ = self.propagate_through_opt_expr(with_expr, succ);
1133 fields.iter().rev().fold(succ, |succ, field| {
1134 self.propagate_through_expr(field.expr, succ)
1135 })
1136 }
1137
1138 ExprCall(f, ref args) => {
1139 // calling a fn with bot return type means that the fn
1140 // will fail, and hence the successors can be ignored
1141 let t_ret = ty::ty_fn_ret(ty::expr_ty(self.ir.tcx, f));
1142 let succ = if ty::type_is_bot(t_ret) {self.s.exit_ln}
1143 else {succ};
1144 let succ = self.propagate_through_exprs(args.as_slice(), succ);
1145 self.propagate_through_expr(f, succ)
1146 }
1147
1148 ExprMethodCall(_, _, ref args) => {
1149 // calling a method with bot return type means that the method
1150 // will fail, and hence the successors can be ignored
1151 let t_ret = ty::node_id_to_type(self.ir.tcx, expr.id);
1152 let succ = if ty::type_is_bot(t_ret) {self.s.exit_ln}
1153 else {succ};
1154 self.propagate_through_exprs(args.as_slice(), succ)
1155 }
1156
1157 ExprTup(ref exprs) => {
1158 self.propagate_through_exprs(exprs.as_slice(), succ)
1159 }
1160
1161 ExprBinary(op, l, r) if ast_util::lazy_binop(op) => {
1162 let r_succ = self.propagate_through_expr(r, succ);
1163
1164 let ln = self.live_node(expr.id, expr.span);
1165 self.init_from_succ(ln, succ);
1166 self.merge_from_succ(ln, r_succ, false);
1167
1168 self.propagate_through_expr(l, ln)
1169 }
1170
1171 ExprIndex(l, r) |
1172 ExprBinary(_, l, r) |
1173 ExprBox(l, r) => {
1174 self.propagate_through_exprs([l, r], succ)
1175 }
1176
1177 ExprAddrOf(_, e) |
1178 ExprCast(e, _) |
1179 ExprUnary(_, e) |
1180 ExprParen(e) => {
1181 self.propagate_through_expr(e, succ)
1182 }
1183
1184 ExprInlineAsm(ref ia) => {
1185 let succ = ia.outputs.iter().rev().fold(succ, |succ, &(_, expr)| {
1186 // see comment on lvalues in
1187 // propagate_through_lvalue_components()
1188 let succ = self.write_lvalue(expr, succ, ACC_WRITE);
1189 self.propagate_through_lvalue_components(expr, succ)
1190 });
1191 // Inputs are executed first. Propagate last because of rev order
1192 ia.inputs.iter().rev().fold(succ, |succ, &(_, expr)| {
1193 self.propagate_through_expr(expr, succ)
1194 })
1195 }
1196
1197 ExprLit(..) => {
1198 succ
1199 }
1200
1201 ExprBlock(blk) => {
1202 self.propagate_through_block(blk, succ)
1203 }
1204
1205 ExprMac(..) => {
1206 self.ir.tcx.sess.span_bug(expr.span, "unexpanded macro");
1207 }
1208 }
1209 }
1210
1211 fn propagate_through_lvalue_components(&mut self,
1212 expr: &Expr,
1213 succ: LiveNode)
1214 -> LiveNode {
1215 // # Lvalues
1216 //
1217 // In general, the full flow graph structure for an
1218 // assignment/move/etc can be handled in one of two ways,
1219 // depending on whether what is being assigned is a "tracked
1220 // value" or not. A tracked value is basically a local
1221 // variable or argument.
1222 //
1223 // The two kinds of graphs are:
1224 //
1225 // Tracked lvalue Untracked lvalue
1226 // ----------------------++-----------------------
1227 // ||
1228 // | || |
1229 // v || v
1230 // (rvalue) || (rvalue)
1231 // | || |
1232 // v || v
1233 // (write of lvalue) || (lvalue components)
1234 // | || |
1235 // v || v
1236 // (succ) || (succ)
1237 // ||
1238 // ----------------------++-----------------------
1239 //
1240 // I will cover the two cases in turn:
1241 //
1242 // # Tracked lvalues
1243 //
1244 // A tracked lvalue is a local variable/argument `x`. In
1245 // these cases, the link_node where the write occurs is linked
1246 // to node id of `x`. The `write_lvalue()` routine generates
1247 // the contents of this node. There are no subcomponents to
1248 // consider.
1249 //
1250 // # Non-tracked lvalues
1251 //
1252 // These are lvalues like `x[5]` or `x.f`. In that case, we
1253 // basically ignore the value which is written to but generate
1254 // reads for the components---`x` in these two examples. The
1255 // components reads are generated by
1256 // `propagate_through_lvalue_components()` (this fn).
1257 //
1258 // # Illegal lvalues
1259 //
1260 // It is still possible to observe assignments to non-lvalues;
1261 // these errors are detected in the later pass borrowck. We
1262 // just ignore such cases and treat them as reads.
1263
1264 match expr.node {
1265 ExprPath(_) => succ,
1266 ExprField(e, _, _) => self.propagate_through_expr(e, succ),
1267 _ => self.propagate_through_expr(expr, succ)
1268 }
1269 }
1270
1271 // see comment on propagate_through_lvalue()
1272 fn write_lvalue(&mut self, expr: &Expr, succ: LiveNode, acc: uint)
1273 -> LiveNode {
1274 match expr.node {
1275 ExprPath(_) => self.access_path(expr, succ, acc),
1276
1277 // We do not track other lvalues, so just propagate through
1278 // to their subcomponents. Also, it may happen that
1279 // non-lvalues occur here, because those are detected in the
1280 // later pass borrowck.
1281 _ => succ
1282 }
1283 }
1284
1285 fn access_path(&mut self, expr: &Expr, succ: LiveNode, acc: uint)
1286 -> LiveNode {
1287 let def = self.ir.tcx.def_map.borrow().get_copy(&expr.id);
1288 match moved_variable_node_id_from_def(def) {
1289 Some(nid) => {
1290 let ln = self.live_node(expr.id, expr.span);
1291 if acc != 0u {
1292 self.init_from_succ(ln, succ);
1293 let var = self.variable(nid, expr.span);
1294 self.acc(ln, var, acc);
1295 }
1296 ln
1297 }
1298 None => succ
1299 }
1300 }
1301
1302 fn propagate_through_loop(&mut self,
1303 expr: &Expr,
1304 cond: Option<@Expr>,
1305 body: &Block,
1306 succ: LiveNode)
1307 -> LiveNode {
1308
1309 /*
1310
1311 We model control flow like this:
1312
1313 (cond) <--+
1314 | |
1315 v |
1316 +-- (expr) |
1317 | | |
1318 | v |
1319 | (body) ---+
1320 |
1321 |
1322 v
1323 (succ)
1324
1325 */
1326
1327
1328 // first iteration:
1329 let mut first_merge = true;
1330 let ln = self.live_node(expr.id, expr.span);
1331 self.init_empty(ln, succ);
1332 if cond.is_some() {
1333 // if there is a condition, then it's possible we bypass
1334 // the body altogether. otherwise, the only way is via a
1335 // break in the loop body.
1336 self.merge_from_succ(ln, succ, first_merge);
1337 first_merge = false;
1338 }
1339 debug!("propagate_through_loop: using id for loop body {} {}",
1340 expr.id, block_to_str(body));
1341
1342 let cond_ln = self.propagate_through_opt_expr(cond, ln);
1343 let body_ln = self.with_loop_nodes(expr.id, succ, ln, |this| {
1344 this.propagate_through_block(body, cond_ln)
1345 });
1346
1347 // repeat until fixed point is reached:
1348 while self.merge_from_succ(ln, body_ln, first_merge) {
1349 first_merge = false;
1350 assert!(cond_ln == self.propagate_through_opt_expr(cond,
1351 ln));
1352 assert!(body_ln == self.with_loop_nodes(expr.id, succ, ln,
1353 |this| this.propagate_through_block(body, cond_ln)));
1354 }
1355
1356 cond_ln
1357 }
1358
1359 fn with_loop_nodes<R>(&mut self,
1360 loop_node_id: NodeId,
1361 break_ln: LiveNode,
1362 cont_ln: LiveNode,
1363 f: |&mut Liveness<'a>| -> R)
1364 -> R {
1365 debug!("with_loop_nodes: {} {}", loop_node_id, break_ln.get());
1366 self.loop_scope.push(loop_node_id);
1367 self.break_ln.insert(loop_node_id, break_ln);
1368 self.cont_ln.insert(loop_node_id, cont_ln);
1369 let r = f(self);
1370 self.loop_scope.pop();
1371 r
1372 }
1373 }
1374
1375 // _______________________________________________________________________
1376 // Checking for error conditions
1377
1378 fn check_local(this: &mut Liveness, local: &Local) {
1379 match local.init {
1380 Some(_) => {
1381 this.warn_about_unused_or_dead_vars_in_pat(local.pat);
1382 },
1383 None => {
1384 this.pat_bindings(local.pat, |this, ln, var, sp, id| {
1385 this.warn_about_unused(sp, id, ln, var);
1386 })
1387 }
1388 }
1389
1390 visit::walk_local(this, local, ());
1391 }
1392
1393 fn check_arm(this: &mut Liveness, arm: &Arm) {
1394 this.arm_pats_bindings(arm.pats.as_slice(), |this, ln, var, sp, id| {
1395 this.warn_about_unused(sp, id, ln, var);
1396 });
1397 visit::walk_arm(this, arm, ());
1398 }
1399
1400 fn check_expr(this: &mut Liveness, expr: &Expr) {
1401 match expr.node {
1402 ExprAssign(l, r) => {
1403 this.check_lvalue(l);
1404 this.visit_expr(r, ());
1405
1406 visit::walk_expr(this, expr, ());
1407 }
1408
1409 ExprAssignOp(_, l, _) => {
1410 this.check_lvalue(l);
1411
1412 visit::walk_expr(this, expr, ());
1413 }
1414
1415 ExprInlineAsm(ref ia) => {
1416 for &(_, input) in ia.inputs.iter() {
1417 this.visit_expr(input, ());
1418 }
1419
1420 // Output operands must be lvalues
1421 for &(_, out) in ia.outputs.iter() {
1422 this.check_lvalue(out);
1423 this.visit_expr(out, ());
1424 }
1425
1426 visit::walk_expr(this, expr, ());
1427 }
1428
1429 // no correctness conditions related to liveness
1430 ExprCall(..) | ExprMethodCall(..) | ExprIf(..) | ExprMatch(..) |
1431 ExprWhile(..) | ExprLoop(..) | ExprIndex(..) | ExprField(..) |
1432 ExprVstore(..) | ExprVec(..) | ExprTup(..) |
1433 ExprBinary(..) |
1434 ExprCast(..) | ExprUnary(..) | ExprRet(..) | ExprBreak(..) |
1435 ExprAgain(..) | ExprLit(_) | ExprBlock(..) |
1436 ExprMac(..) | ExprAddrOf(..) | ExprStruct(..) | ExprRepeat(..) |
1437 ExprParen(..) | ExprFnBlock(..) | ExprProc(..) | ExprPath(..) |
1438 ExprBox(..) => {
1439 visit::walk_expr(this, expr, ());
1440 }
1441 ExprForLoop(..) => fail!("non-desugared expr_for_loop")
1442 }
1443 }
1444
1445 fn check_fn(_v: &Liveness,
1446 _fk: &FnKind,
1447 _decl: &FnDecl,
1448 _body: &Block,
1449 _sp: Span,
1450 _id: NodeId) {
1451 // do not check contents of nested fns
1452 }
1453
1454 impl<'a> Liveness<'a> {
1455 fn check_ret(&self,
1456 id: NodeId,
1457 sp: Span,
1458 _fk: &FnKind,
1459 entry_ln: LiveNode,
1460 body: &Block) {
1461 if self.live_on_entry(entry_ln, self.s.no_ret_var).is_some() {
1462 // if no_ret_var is live, then we fall off the end of the
1463 // function without any kind of return expression:
1464
1465 let t_ret = ty::ty_fn_ret(ty::node_id_to_type(self.ir.tcx, id));
1466 if ty::type_is_nil(t_ret) {
1467 // for nil return types, it is ok to not return a value expl.
1468 } else if ty::type_is_bot(t_ret) {
1469 // for bot return types, not ok. Function should fail.
1470 self.ir.tcx.sess.span_err(
1471 sp, "some control paths may return");
1472 } else {
1473 let ends_with_stmt = match body.expr {
1474 None if body.stmts.len() > 0 =>
1475 match body.stmts.last().unwrap().node {
1476 StmtSemi(e, _) => {
1477 let t_stmt = ty::expr_ty(self.ir.tcx, e);
1478 ty::get(t_stmt).sty == ty::get(t_ret).sty
1479 },
1480 _ => false
1481 },
1482 _ => false
1483 };
1484 if ends_with_stmt {
1485 let last_stmt = body.stmts.last().unwrap();
1486 let original_span = original_sp(last_stmt.span, sp);
1487 let span_semicolon = Span {
1488 lo: original_span.hi - BytePos(1),
1489 hi: original_span.hi,
1490 expn_info: original_span.expn_info
1491 };
1492 self.ir.tcx.sess.span_note(
1493 span_semicolon, "consider removing this semicolon:");
1494 }
1495 self.ir.tcx.sess.span_err(
1496 sp, "not all control paths return a value");
1497 }
1498 }
1499 }
1500
1501 fn check_lvalue(&mut self, expr: &Expr) {
1502 match expr.node {
1503 ExprPath(_) => {
1504 match self.ir.tcx.def_map.borrow().get_copy(&expr.id) {
1505 DefLocal(nid, _) => {
1506 // Assignment to an immutable variable or argument: only legal
1507 // if there is no later assignment. If this local is actually
1508 // mutable, then check for a reassignment to flag the mutability
1509 // as being used.
1510 let ln = self.live_node(expr.id, expr.span);
1511 let var = self.variable(nid, expr.span);
1512 self.warn_about_dead_assign(expr.span, expr.id, ln, var);
1513 }
1514 def => {
1515 match moved_variable_node_id_from_def(def) {
1516 Some(nid) => {
1517 let ln = self.live_node(expr.id, expr.span);
1518 let var = self.variable(nid, expr.span);
1519 self.warn_about_dead_assign(expr.span, expr.id, ln, var);
1520 }
1521 None => {}
1522 }
1523 }
1524 }
1525 }
1526
1527 _ => {
1528 // For other kinds of lvalues, no checks are required,
1529 // and any embedded expressions are actually rvalues
1530 visit::walk_expr(self, expr, ());
1531 }
1532 }
1533 }
1534
1535 fn should_warn(&self, var: Variable) -> Option<~str> {
1536 let name = self.ir.variable_name(var);
1537 if name.len() == 0 || name[0] == ('_' as u8) { None } else { Some(name) }
1538 }
1539
1540 fn warn_about_unused_args(&self, decl: &FnDecl, entry_ln: LiveNode) {
1541 for arg in decl.inputs.iter() {
1542 pat_util::pat_bindings(&self.ir.tcx.def_map,
1543 arg.pat,
1544 |_bm, p_id, sp, path| {
1545 let var = self.variable(p_id, sp);
1546 // Ignore unused self.
1547 let ident = ast_util::path_to_ident(path);
1548 if ident.name != special_idents::self_.name {
1549 self.warn_about_unused(sp, p_id, entry_ln, var);
1550 }
1551 })
1552 }
1553 }
1554
1555 fn warn_about_unused_or_dead_vars_in_pat(&mut self, pat: &Pat) {
1556 self.pat_bindings(pat, |this, ln, var, sp, id| {
1557 if !this.warn_about_unused(sp, id, ln, var) {
1558 this.warn_about_dead_assign(sp, id, ln, var);
1559 }
1560 })
1561 }
1562
1563 fn warn_about_unused(&self,
1564 sp: Span,
1565 id: NodeId,
1566 ln: LiveNode,
1567 var: Variable)
1568 -> bool {
1569 if !self.used_on_entry(ln, var) {
1570 let r = self.should_warn(var);
1571 for name in r.iter() {
1572
1573 // annoying: for parameters in funcs like `fn(x: int)
1574 // {ret}`, there is only one node, so asking about
1575 // assigned_on_exit() is not meaningful.
1576 let is_assigned = if ln == self.s.exit_ln {
1577 false
1578 } else {
1579 self.assigned_on_exit(ln, var).is_some()
1580 };
1581
1582 if is_assigned {
1583 self.ir.tcx.sess.add_lint(UnusedVariable, id, sp,
1584 format!("variable `{}` is assigned to, \
1585 but never used", *name));
1586 } else {
1587 self.ir.tcx.sess.add_lint(UnusedVariable, id, sp,
1588 format!("unused variable: `{}`", *name));
1589 }
1590 }
1591 true
1592 } else {
1593 false
1594 }
1595 }
1596
1597 fn warn_about_dead_assign(&self,
1598 sp: Span,
1599 id: NodeId,
1600 ln: LiveNode,
1601 var: Variable) {
1602 if self.live_on_exit(ln, var).is_none() {
1603 let r = self.should_warn(var);
1604 for name in r.iter() {
1605 self.ir.tcx.sess.add_lint(DeadAssignment, id, sp,
1606 format!("value assigned to `{}` is never read", *name));
1607 }
1608 }
1609 }
1610 }
librustc/middle/liveness.rs:553:1-553:1 -struct- definition:
struct Specials {
exit_ln: LiveNode,
fallthrough_ln: LiveNode,
references:- 3565: ir: &'a mut IrMaps<'a>,
566: s: Specials,
567: successors: Vec<LiveNode>,
--
579: fn Liveness<'a>(ir: &'a mut IrMaps<'a>, specials: Specials) -> Liveness<'a> {
580: Liveness {
librustc/middle/liveness.rs:145:16-145:16 -enum- definition:
enum LiveNodeKind {
FreeVarNode(Span),
ExprNode(Span),
references:- 12680: fn assigned_on_exit(&self, ln: LiveNode, var: Variable)
681: -> Option<LiveNodeKind> {
682: let successor = *self.successors.get(ln.get());
librustc/middle/liveness.rs:217:1-217:1 -fn- definition:
fn invalid_node() -> LiveNode { LiveNode(uint::MAX) }
struct CaptureInfo {
ln: LiveNode,
references:- 6818: let idx = self.idx(writer, var);
819: self.users.get_mut(idx).reader = invalid_node();
820: self.users.get_mut(idx).writer = invalid_node();
--
834: if (acc & ACC_WRITE) != 0 {
835: user.reader = invalid_node();
836: user.writer = ln;
librustc/middle/liveness.rs:231:1-231:1 -struct- definition:
struct LocalInfo {
id: NodeId,
ident: Ident,
references:- 5412: };
413: ir.add_variable(Local(LocalInfo {
414: id: p_id,
--
433: ir.add_live_node_for_node(p_id, VarDefNode(sp));
434: ir.add_variable(Local(LocalInfo {
435: id: p_id,
librustc/middle/liveness.rs:219:1-219:1 -struct- definition:
struct CaptureInfo {
ln: LiveNode,
is_move: bool,
references:- 3494: };
495: call_caps.push(CaptureInfo {ln: fv_ln,
496: is_move: is_move,
librustc/middle/liveness.rs:256:1-256:1 -fn- definition:
fn IrMaps<'a>(tcx: &'a ty::ctxt)
-> IrMaps<'a> {
IrMaps {
references:- 2359: // swap in a new set of IR maps for this function body:
360: let mut fn_maps = IrMaps(ir.tcx);
librustc/middle/liveness.rs:126:16-126:16 -struct- definition:
struct Variable(uint);
struct LiveNode(uint);
impl Variable {
references:- 24612: pat: &Pat,
613: f: |&mut Liveness<'a>, LiveNode, Variable, Span, NodeId|) {
614: pat_util::pat_bindings(&self.ir.tcx.def_map, pat, |_bm, p_id, sp, _n| {
--
661: */
662: fn live_on_exit(&self, ln: LiveNode, var: Variable)
663: -> Option<LiveNodeKind> {
--
826: // Either read, write, or both depending on the acc bitset
827: fn acc(&mut self, ln: LiveNode, var: Variable, acc: uint) {
828: debug!("{} accesses[{:x}] {}: {}",
--
1600: ln: LiveNode,
1601: var: Variable) {
1602: if self.live_on_exit(ln, var).is_none() {
librustc/middle/liveness.rs:563:1-563:1 -struct- definition:
struct Liveness<'a> {
ir: &'a mut IrMaps<'a>,
s: Specials,
references:- 13591: impl<'a> Liveness<'a> {
592: fn live_node(&self, node_id: NodeId, span: Span) -> LiveNode {
--
1362: cont_ln: LiveNode,
1363: f: |&mut Liveness<'a>| -> R)
1364: -> R {
--
1445: fn check_fn(_v: &Liveness,
1446: _fk: &FnKind,
--
1454: impl<'a> Liveness<'a> {
1455: fn check_ret(&self,
librustc/middle/liveness.rs:539:19-539:19 -struct- definition:
struct Users {
reader: LiveNode,
writer: LiveNode,
references:- 7546: fn invalid_users() -> Users {
547: Users {
548: reader: invalid_node(),
--
567: successors: Vec<LiveNode>,
568: users: Vec<Users>,
569: // The list of node IDs for the nested loop scopes
librustc/middle/liveness.rs:444:1-444:1 -fn- definition:
fn moved_variable_node_id_from_def(def: Def) -> Option<NodeId> {
match def {
DefBinding(nid, _) |
references:- 41514: def => {
1515: match moved_variable_node_id_from_def(def) {
1516: Some(nid) => {
librustc/middle/liveness.rs:128:16-128:16 -struct- definition:
struct LiveNode(uint);
impl Variable {
fn get(&self) -> uint { let Variable(v) = *self; v }
references:- 79librustc/middle/liveness.rs:804:8-804:8 -fn- definition:
fn copy_if_invalid(src: LiveNode, dst: &mut LiveNode) -> bool {
if src.is_valid() && !dst.is_valid() {
*dst = src;
references:- 2789: self.indices2(ln, succ_ln, |this, idx, succ_idx| {
790: changed |= copy_if_invalid(this.users.get(succ_idx).reader,
791: &mut this.users.get_mut(idx).reader);
792: changed |= copy_if_invalid(this.users.get(succ_idx).writer,
793: &mut this.users.get_mut(idx).writer);
librustc/middle/liveness.rs:238:1-238:1 -enum- definition:
enum VarKind {
Arg(NodeId, Ident),
Local(LocalInfo),
references:- 2290: fn add_variable(&mut self, vk: VarKind) -> Variable {
291: let v = Variable(self.num_vars);
librustc/middle/liveness.rs:244:1-244:1 -struct- definition:
struct IrMaps<'a> {
tcx: &'a ty::ctxt,
num_live_nodes: uint,
references:- 12400: fn visit_local(ir: &mut IrMaps, local: &Local) {
401: pat_util::pat_bindings(&ir.tcx.def_map, local.pat, |bm, p_id, sp, path| {
--
455: fn visit_expr(ir: &mut IrMaps, expr: &Expr) {
456: match expr.node {
--
579: fn Liveness<'a>(ir: &'a mut IrMaps<'a>, specials: Specials) -> Liveness<'a> {
580: Liveness {