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