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.
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.
11 //! A classic liveness analysis based on dataflow over the AST. Computes,
12 //! for each local variable in a function, whether that variable is live
13 //! at a given point. Program execution points are identified by their
18 //! The basic model is that each local variable is assigned an index. We
19 //! represent sets of local variables using a vector indexed by this
20 //! index. The value in the vector is either 0, indicating the variable
21 //! is dead, or the id of an expression that uses the variable.
23 //! We conceptually walk over the AST in reverse execution order. If we
24 //! find a use of a variable, we add it to the set of live variables. If
25 //! we find an assignment to a variable, we remove it from the set of live
26 //! variables. When we have to merge two flows, we take the union of
27 //! those two flows---if the variable is live on both paths, we simply
28 //! pick one id. In the event of loops, we continue doing this until a
29 //! fixed point is reached.
31 //! ## Checking initialization
33 //! At the function entry point, all variables must be dead. If this is
34 //! not the case, we can report an error using the id found in the set of
35 //! live variables, which identifies a use of the variable which is not
36 //! dominated by an assignment.
40 //! After each explicit move, the variable must be dead.
42 //! ## Computing last uses
44 //! Any use of the variable where the variable is dead afterwards is a
47 //! # Implementation details
49 //! The actual implementation contains two (nested) walks over the AST.
50 //! The outer walk has the job of building up the ir_maps instance for the
51 //! enclosing function. On the way down the tree, it identifies those AST
52 //! nodes and variable IDs that will be needed for the liveness analysis
53 //! and assigns them contiguous IDs. The liveness id for an AST node is
54 //! called a `live_node` (it's a newtype'd usize) and the id for a variable
55 //! is called a `variable` (another newtype'd usize).
57 //! On the way back up the tree, as we are about to exit from a function
58 //! declaration we allocate a `liveness` instance. Now that we know
59 //! precisely how many nodes and variables we need, we can allocate all
60 //! the various arrays that we will need to precisely the right size. We then
61 //! perform the actual propagation on the `liveness` instance.
63 //! This propagation is encoded in the various `propagate_through_*()`
64 //! methods. It effectively does a reverse walk of the AST; whenever we
65 //! reach a loop node, we iterate until a fixed point is reached.
67 //! ## The `Users` struct
69 //! At each live node `N`, we track three pieces of information for each
70 //! variable `V` (these are encapsulated in the `Users` struct):
72 //! - `reader`: the `LiveNode` ID of some node which will read the value
73 //! that `V` holds on entry to `N`. Formally: a node `M` such
74 //! that there exists a path `P` from `N` to `M` where `P` does not
75 //! write `V`. If the `reader` is `invalid_node()`, then the current
76 //! value will never be read (the variable is dead, essentially).
78 //! - `writer`: the `LiveNode` ID of some node which will write the
79 //! variable `V` and which is reachable from `N`. Formally: a node `M`
80 //! such that there exists a path `P` from `N` to `M` and `M` writes
81 //! `V`. If the `writer` is `invalid_node()`, then there is no writer
82 //! of `V` that follows `N`.
84 //! - `used`: a boolean value indicating whether `V` is *used*. We
85 //! distinguish a *read* from a *use* in that a *use* is some read that
86 //! is not just used to generate a new value. For example, `x += 1` is
87 //! a read but not a use. This is used to generate better warnings.
89 //! ## Special Variables
91 //! We generate various special variables for various, well, special purposes.
92 //! These are described in the `specials` struct:
94 //! - `exit_ln`: a live node that is generated to represent every 'exit' from
95 //! the function, whether it be by explicit return, panic, or other means.
97 //! - `fallthrough_ln`: a live node that represents a fallthrough
99 //! - `no_ret_var`: a synthetic variable that is only 'read' from, the
100 //! fallthrough node. This allows us to detect functions where we fail
101 //! to return explicitly.
102 //! - `clean_exit_var`: a synthetic variable that is only 'read' from the
103 //! fallthrough node. It is only live if the function could converge
104 //! via means other than an explicit `return` expression. That is, it is
105 //! only dead if the end of the function's block can never be reached.
106 //! It is the responsibility of typeck to ensure that there are no
107 //! `return` expressions in a function declared as diverging.
108 use self::LoopKind
::*;
109 use self::LiveNodeKind
::*;
110 use self::VarKind
::*;
113 use middle
::mem_categorization
::Typer
;
114 use middle
::pat_util
;
117 use middle
::ty
::ClosureTyper
;
119 use util
::nodemap
::NodeMap
;
121 use std
::{fmt, usize}
;
122 use std
::io
::prelude
::*;
124 use std
::iter
::repeat
;
126 use syntax
::ast
::{self, NodeId, Expr}
;
127 use syntax
::codemap
::{BytePos, original_sp, Span}
;
128 use syntax
::parse
::token
::{self, special_idents}
;
129 use syntax
::print
::pprust
::{expr_to_string, block_to_string}
;
131 use syntax
::ast_util
;
132 use syntax
::visit
::{self, Visitor, FnKind}
;
134 /// For use with `propagate_through_loop`.
136 /// An endless `loop` loop.
138 /// A `while` loop, with the given expression as condition.
142 #[derive(Copy, Clone, PartialEq)]
143 struct Variable(usize);
145 #[derive(Copy, PartialEq)]
146 struct LiveNode(usize);
149 fn get(&self) -> usize { let Variable(v) = *self; v }
153 fn get(&self) -> usize { let LiveNode(v) = *self; v }
156 impl Clone
for LiveNode
{
157 fn clone(&self) -> LiveNode
{
162 #[derive(Copy, Clone, PartialEq, Debug)]
170 fn live_node_kind_to_string(lnk
: LiveNodeKind
, cx
: &ty
::ctxt
) -> String
{
171 let cm
= cx
.sess
.codemap();
174 format
!("Free var node [{}]", cm
.span_to_string(s
))
177 format
!("Expr node [{}]", cm
.span_to_string(s
))
180 format
!("Var def node [{}]", cm
.span_to_string(s
))
182 ExitNode
=> "Exit node".to_string(),
186 impl<'a
, 'tcx
, 'v
> Visitor
<'v
> for IrMaps
<'a
, 'tcx
> {
187 fn visit_fn(&mut self, fk
: FnKind
<'v
>, fd
: &'v ast
::FnDecl
,
188 b
: &'v ast
::Block
, s
: Span
, id
: NodeId
) {
189 visit_fn(self, fk
, fd
, b
, s
, id
);
191 fn visit_local(&mut self, l
: &ast
::Local
) { visit_local(self, l); }
192 fn visit_expr(&mut self, ex
: &Expr
) { visit_expr(self, ex); }
193 fn visit_arm(&mut self, a
: &ast
::Arm
) { visit_arm(self, a); }
196 pub fn check_crate(tcx
: &ty
::ctxt
) {
197 visit
::walk_crate(&mut IrMaps
::new(tcx
), tcx
.map
.krate());
198 tcx
.sess
.abort_if_errors();
201 impl fmt
::Debug
for LiveNode
{
202 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
203 write
!(f
, "ln({})", self.get())
207 impl fmt
::Debug
for Variable
{
208 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
209 write
!(f
, "v({})", self.get())
213 // ______________________________________________________________________
216 // This is the first pass and the one that drives the main
217 // computation. It walks up and down the IR once. On the way down,
218 // we count for each function the number of variables as well as
219 // liveness nodes. A liveness node is basically an expression or
220 // capture clause that does something of interest: either it has
221 // interesting control flow or it uses/defines a local variable.
223 // On the way back up, at each function node we create liveness sets
224 // (we now know precisely how big to make our various vectors and so
225 // forth) and then do the data-flow propagation to compute the set
226 // of live variables at each program point.
228 // Finally, we run back over the IR one last time and, using the
229 // computed liveness, check various safety conditions. For example,
230 // there must be no live nodes at the definition site for a variable
231 // unless it has an initializer. Similarly, each non-mutable local
232 // variable must not be assigned if there is some successor
233 // assignment. And so forth.
236 fn is_valid(&self) -> bool
{
237 self.get() != usize::MAX
241 fn invalid_node() -> LiveNode { LiveNode(usize::MAX) }
248 #[derive(Copy, Clone, Debug)]
254 #[derive(Copy, Clone, Debug)]
256 Arg(NodeId
, ast
::Name
),
262 struct IrMaps
<'a
, 'tcx
: 'a
> {
263 tcx
: &'a ty
::ctxt
<'tcx
>,
265 num_live_nodes
: usize,
267 live_node_map
: NodeMap
<LiveNode
>,
268 variable_map
: NodeMap
<Variable
>,
269 capture_info_map
: NodeMap
<Rc
<Vec
<CaptureInfo
>>>,
270 var_kinds
: Vec
<VarKind
>,
271 lnks
: Vec
<LiveNodeKind
>,
274 impl<'a
, 'tcx
> IrMaps
<'a
, 'tcx
> {
275 fn new(tcx
: &'a ty
::ctxt
<'tcx
>) -> IrMaps
<'a
, 'tcx
> {
280 live_node_map
: NodeMap(),
281 variable_map
: NodeMap(),
282 capture_info_map
: NodeMap(),
283 var_kinds
: Vec
::new(),
288 fn add_live_node(&mut self, lnk
: LiveNodeKind
) -> LiveNode
{
289 let ln
= LiveNode(self.num_live_nodes
);
291 self.num_live_nodes
+= 1;
293 debug
!("{:?} is of kind {}", ln
,
294 live_node_kind_to_string(lnk
, self.tcx
));
299 fn add_live_node_for_node(&mut self, node_id
: NodeId
, lnk
: LiveNodeKind
) {
300 let ln
= self.add_live_node(lnk
);
301 self.live_node_map
.insert(node_id
, ln
);
303 debug
!("{:?} is node {}", ln
, node_id
);
306 fn add_variable(&mut self, vk
: VarKind
) -> Variable
{
307 let v
= Variable(self.num_vars
);
308 self.var_kinds
.push(vk
);
312 Local(LocalInfo { id: node_id, .. }
) | Arg(node_id
, _
) => {
313 self.variable_map
.insert(node_id
, v
);
315 ImplicitRet
| CleanExit
=> {}
318 debug
!("{:?} is {:?}", v
, vk
);
323 fn variable(&self, node_id
: NodeId
, span
: Span
) -> Variable
{
324 match self.variable_map
.get(&node_id
) {
329 .span_bug(span
, &format
!("no variable registered for id {}",
335 fn variable_name(&self, var
: Variable
) -> String
{
336 match self.var_kinds
[var
.get()] {
337 Local(LocalInfo { name, .. }
) | Arg(_
, name
) => {
338 token
::get_name(name
).to_string()
340 ImplicitRet
=> "<implicit-ret>".to_string(),
341 CleanExit
=> "<clean-exit>".to_string()
345 fn set_captures(&mut self, node_id
: NodeId
, cs
: Vec
<CaptureInfo
>) {
346 self.capture_info_map
.insert(node_id
, Rc
::new(cs
));
349 fn lnk(&self, ln
: LiveNode
) -> LiveNodeKind
{
354 impl<'a
, 'tcx
, 'v
> Visitor
<'v
> for Liveness
<'a
, 'tcx
> {
355 fn visit_fn(&mut self, fk
: FnKind
<'v
>, fd
: &'v ast
::FnDecl
,
356 b
: &'v ast
::Block
, s
: Span
, n
: NodeId
) {
357 check_fn(self, fk
, fd
, b
, s
, n
);
359 fn visit_local(&mut self, l
: &ast
::Local
) {
360 check_local(self, l
);
362 fn visit_expr(&mut self, ex
: &Expr
) {
363 check_expr(self, ex
);
365 fn visit_arm(&mut self, a
: &ast
::Arm
) {
370 fn visit_fn(ir
: &mut IrMaps
,
378 // swap in a new set of IR maps for this function body:
379 let mut fn_maps
= IrMaps
::new(ir
.tcx
);
381 debug
!("creating fn_maps: {:?}", &fn_maps
as *const IrMaps
);
383 for arg
in &decl
.inputs
{
384 pat_util
::pat_bindings(&ir
.tcx
.def_map
,
386 |_bm
, arg_id
, _x
, path1
| {
387 debug
!("adding argument {}", arg_id
);
388 let name
= path1
.node
.name
;
389 fn_maps
.add_variable(Arg(arg_id
, name
));
393 // gather up the various local variables, significant expressions,
395 visit
::walk_fn(&mut fn_maps
, fk
, decl
, body
, sp
);
397 // Special nodes and variables:
398 // - exit_ln represents the end of the fn, either by return or panic
399 // - implicit_ret_var is a pseudo-variable that represents
400 // an implicit return
401 let specials
= Specials
{
402 exit_ln
: fn_maps
.add_live_node(ExitNode
),
403 fallthrough_ln
: fn_maps
.add_live_node(ExitNode
),
404 no_ret_var
: fn_maps
.add_variable(ImplicitRet
),
405 clean_exit_var
: fn_maps
.add_variable(CleanExit
)
409 let mut lsets
= Liveness
::new(&mut fn_maps
, specials
);
410 let entry_ln
= lsets
.compute(decl
, body
);
412 // check for various error conditions
413 lsets
.visit_block(body
);
414 lsets
.check_ret(id
, sp
, fk
, entry_ln
, body
);
415 lsets
.warn_about_unused_args(decl
, entry_ln
);
418 fn visit_local(ir
: &mut IrMaps
, local
: &ast
::Local
) {
419 pat_util
::pat_bindings(&ir
.tcx
.def_map
, &*local
.pat
, |_
, p_id
, sp
, path1
| {
420 debug
!("adding local variable {}", p_id
);
421 let name
= path1
.node
.name
;
422 ir
.add_live_node_for_node(p_id
, VarDefNode(sp
));
423 ir
.add_variable(Local(LocalInfo
{
428 visit
::walk_local(ir
, local
);
431 fn visit_arm(ir
: &mut IrMaps
, arm
: &ast
::Arm
) {
432 for pat
in &arm
.pats
{
433 pat_util
::pat_bindings(&ir
.tcx
.def_map
, &**pat
, |bm
, p_id
, sp
, path1
| {
434 debug
!("adding local variable {} from match with bm {:?}",
436 let name
= path1
.node
.name
;
437 ir
.add_live_node_for_node(p_id
, VarDefNode(sp
));
438 ir
.add_variable(Local(LocalInfo
{
444 visit
::walk_arm(ir
, arm
);
447 fn visit_expr(ir
: &mut IrMaps
, expr
: &Expr
) {
449 // live nodes required for uses or definitions of variables:
450 ast
::ExprPath(..) => {
451 let def
= ir
.tcx
.def_map
.borrow().get(&expr
.id
).unwrap().full_def();
452 debug
!("expr {}: path that leads to {:?}", expr
.id
, def
);
453 if let DefLocal(..) = def
{
454 ir
.add_live_node_for_node(expr
.id
, ExprNode(expr
.span
));
456 visit
::walk_expr(ir
, expr
);
458 ast
::ExprClosure(..) => {
459 // Interesting control flow (for loops can contain labeled
460 // breaks or continues)
461 ir
.add_live_node_for_node(expr
.id
, ExprNode(expr
.span
));
463 // Make a live_node for each captured variable, with the span
464 // being the location that the variable is used. This results
465 // in better error messages than just pointing at the closure
466 // construction site.
467 let mut call_caps
= Vec
::new();
468 ty
::with_freevars(ir
.tcx
, expr
.id
, |freevars
| {
470 if let DefLocal(rv
) = fv
.def
{
471 let fv_ln
= ir
.add_live_node(FreeVarNode(fv
.span
));
472 call_caps
.push(CaptureInfo
{ln
: fv_ln
,
477 ir
.set_captures(expr
.id
, call_caps
);
479 visit
::walk_expr(ir
, expr
);
482 // live nodes required for interesting control flow:
483 ast
::ExprIf(..) | ast
::ExprMatch(..) | ast
::ExprWhile(..) | ast
::ExprLoop(..) => {
484 ir
.add_live_node_for_node(expr
.id
, ExprNode(expr
.span
));
485 visit
::walk_expr(ir
, expr
);
487 ast
::ExprIfLet(..) => {
488 ir
.tcx
.sess
.span_bug(expr
.span
, "non-desugared ExprIfLet");
490 ast
::ExprWhileLet(..) => {
491 ir
.tcx
.sess
.span_bug(expr
.span
, "non-desugared ExprWhileLet");
493 ast
::ExprForLoop(..) => {
494 ir
.tcx
.sess
.span_bug(expr
.span
, "non-desugared ExprForLoop");
496 ast
::ExprBinary(op
, _
, _
) if ast_util
::lazy_binop(op
.node
) => {
497 ir
.add_live_node_for_node(expr
.id
, ExprNode(expr
.span
));
498 visit
::walk_expr(ir
, expr
);
501 // otherwise, live nodes are not required:
502 ast
::ExprIndex(..) | ast
::ExprField(..) | ast
::ExprTupField(..) |
503 ast
::ExprVec(..) | ast
::ExprCall(..) | ast
::ExprMethodCall(..) |
504 ast
::ExprTup(..) | ast
::ExprBinary(..) | ast
::ExprAddrOf(..) |
505 ast
::ExprCast(..) | ast
::ExprUnary(..) | ast
::ExprBreak(_
) |
506 ast
::ExprAgain(_
) | ast
::ExprLit(_
) | ast
::ExprRet(..) |
507 ast
::ExprBlock(..) | ast
::ExprAssign(..) | ast
::ExprAssignOp(..) |
508 ast
::ExprMac(..) | ast
::ExprStruct(..) | ast
::ExprRepeat(..) |
509 ast
::ExprParen(..) | ast
::ExprInlineAsm(..) | ast
::ExprBox(..) |
510 ast
::ExprRange(..) => {
511 visit
::walk_expr(ir
, expr
);
516 // ______________________________________________________________________
517 // Computing liveness sets
519 // Actually we compute just a bit more than just liveness, but we use
520 // the same basic propagation framework in all cases.
522 #[derive(Clone, Copy)]
529 fn invalid_users() -> Users
{
531 reader
: invalid_node(),
532 writer
: invalid_node(),
537 #[derive(Copy, Clone)]
540 fallthrough_ln
: LiveNode
,
541 no_ret_var
: Variable
,
542 clean_exit_var
: Variable
545 const ACC_READ
: u32 = 1;
546 const ACC_WRITE
: u32 = 2;
547 const ACC_USE
: u32 = 4;
549 struct Liveness
<'a
, 'tcx
: 'a
> {
550 ir
: &'a
mut IrMaps
<'a
, 'tcx
>,
552 successors
: Vec
<LiveNode
>,
554 // The list of node IDs for the nested loop scopes
556 loop_scope
: Vec
<NodeId
>,
557 // mappings from loop node ID to LiveNode
558 // ("break" label should map to loop node ID,
559 // it probably doesn't now)
560 break_ln
: NodeMap
<LiveNode
>,
561 cont_ln
: NodeMap
<LiveNode
>
564 impl<'a
, 'tcx
> Liveness
<'a
, 'tcx
> {
565 fn new(ir
: &'a
mut IrMaps
<'a
, 'tcx
>, specials
: Specials
) -> Liveness
<'a
, 'tcx
> {
566 let num_live_nodes
= ir
.num_live_nodes
;
567 let num_vars
= ir
.num_vars
;
571 successors
: repeat(invalid_node()).take(num_live_nodes
).collect(),
572 users
: repeat(invalid_users()).take(num_live_nodes
* num_vars
).collect(),
573 loop_scope
: Vec
::new(),
579 fn live_node(&self, node_id
: NodeId
, span
: Span
) -> LiveNode
{
580 match self.ir
.live_node_map
.get(&node_id
) {
583 // This must be a mismatch between the ir_map construction
584 // above and the propagation code below; the two sets of
585 // code have to agree about which AST nodes are worth
586 // creating liveness nodes for.
587 self.ir
.tcx
.sess
.span_bug(
589 &format
!("no live node registered for node {}",
595 fn variable(&self, node_id
: NodeId
, span
: Span
) -> Variable
{
596 self.ir
.variable(node_id
, span
)
599 fn pat_bindings
<F
>(&mut self, pat
: &ast
::Pat
, mut f
: F
) where
600 F
: FnMut(&mut Liveness
<'a
, 'tcx
>, LiveNode
, Variable
, Span
, NodeId
),
602 pat_util
::pat_bindings(&self.ir
.tcx
.def_map
, pat
, |_bm
, p_id
, sp
, _n
| {
603 let ln
= self.live_node(p_id
, sp
);
604 let var
= self.variable(p_id
, sp
);
605 f(self, ln
, var
, sp
, p_id
);
609 fn arm_pats_bindings
<F
>(&mut self, pat
: Option
<&ast
::Pat
>, f
: F
) where
610 F
: FnMut(&mut Liveness
<'a
, 'tcx
>, LiveNode
, Variable
, Span
, NodeId
),
614 self.pat_bindings(pat
, f
);
620 fn define_bindings_in_pat(&mut self, pat
: &ast
::Pat
, succ
: LiveNode
)
622 self.define_bindings_in_arm_pats(Some(pat
), succ
)
625 fn define_bindings_in_arm_pats(&mut self, pat
: Option
<&ast
::Pat
>, succ
: LiveNode
)
628 self.arm_pats_bindings(pat
, |this
, ln
, var
, _sp
, _id
| {
629 this
.init_from_succ(ln
, succ
);
630 this
.define(ln
, var
);
636 fn idx(&self, ln
: LiveNode
, var
: Variable
) -> usize {
637 ln
.get() * self.ir
.num_vars
+ var
.get()
640 fn live_on_entry(&self, ln
: LiveNode
, var
: Variable
)
641 -> Option
<LiveNodeKind
> {
642 assert
!(ln
.is_valid());
643 let reader
= self.users
[self.idx(ln
, var
)].reader
;
644 if reader
.is_valid() {Some(self.ir.lnk(reader))}
else {None}
648 Is this variable live on entry to any of its successor nodes?
650 fn live_on_exit(&self, ln
: LiveNode
, var
: Variable
)
651 -> Option
<LiveNodeKind
> {
652 let successor
= self.successors
[ln
.get()];
653 self.live_on_entry(successor
, var
)
656 fn used_on_entry(&self, ln
: LiveNode
, var
: Variable
) -> bool
{
657 assert
!(ln
.is_valid());
658 self.users
[self.idx(ln
, var
)].used
661 fn assigned_on_entry(&self, ln
: LiveNode
, var
: Variable
)
662 -> Option
<LiveNodeKind
> {
663 assert
!(ln
.is_valid());
664 let writer
= self.users
[self.idx(ln
, var
)].writer
;
665 if writer
.is_valid() {Some(self.ir.lnk(writer))}
else {None}
668 fn assigned_on_exit(&self, ln
: LiveNode
, var
: Variable
)
669 -> Option
<LiveNodeKind
> {
670 let successor
= self.successors
[ln
.get()];
671 self.assigned_on_entry(successor
, var
)
674 fn indices2
<F
>(&mut self, ln
: LiveNode
, succ_ln
: LiveNode
, mut op
: F
) where
675 F
: FnMut(&mut Liveness
<'a
, 'tcx
>, usize, usize),
677 let node_base_idx
= self.idx(ln
, Variable(0));
678 let succ_base_idx
= self.idx(succ_ln
, Variable(0));
679 for var_idx
in 0..self.ir
.num_vars
{
680 op(self, node_base_idx
+ var_idx
, succ_base_idx
+ var_idx
);
684 fn write_vars
<F
>(&self,
688 -> io
::Result
<()> where
689 F
: FnMut(usize) -> LiveNode
,
691 let node_base_idx
= self.idx(ln
, Variable(0));
692 for var_idx
in 0..self.ir
.num_vars
{
693 let idx
= node_base_idx
+ var_idx
;
694 if test(idx
).is_valid() {
695 try
!(write
!(wr
, " {:?}", Variable(var_idx
)));
701 fn find_loop_scope(&self,
702 opt_label
: Option
<ast
::Ident
>,
708 // Refers to a labeled loop. Use the results of resolve
710 match self.ir
.tcx
.def_map
.borrow().get(&id
).map(|d
| d
.full_def()) {
711 Some(DefLabel(loop_id
)) => loop_id
,
712 _
=> self.ir
.tcx
.sess
.span_bug(sp
, "label on break/loop \
713 doesn't refer to a loop")
717 // Vanilla 'break' or 'loop', so use the enclosing
719 if self.loop_scope
.is_empty() {
720 self.ir
.tcx
.sess
.span_bug(sp
, "break outside loop");
722 *self.loop_scope
.last().unwrap()
728 #[allow(unused_must_use)]
729 fn ln_str(&self, ln
: LiveNode
) -> String
{
730 let mut wr
= Vec
::new();
732 let wr
= &mut wr
as &mut Write
;
733 write
!(wr
, "[ln({:?}) of kind {:?} reads", ln
.get(), self.ir
.lnk(ln
));
734 self.write_vars(wr
, ln
, |idx
| self.users
[idx
].reader
);
735 write
!(wr
, " writes");
736 self.write_vars(wr
, ln
, |idx
| self.users
[idx
].writer
);
737 write
!(wr
, " precedes {:?}]", self.successors
[ln
.get()]);
739 String
::from_utf8(wr
).unwrap()
742 fn init_empty(&mut self, ln
: LiveNode
, succ_ln
: LiveNode
) {
743 self.successors
[ln
.get()] = succ_ln
;
745 // It is not necessary to initialize the
746 // values to empty because this is the value
747 // they have when they are created, and the sets
748 // only grow during iterations.
750 // self.indices(ln) { |idx|
751 // self.users[idx] = invalid_users();
755 fn init_from_succ(&mut self, ln
: LiveNode
, succ_ln
: LiveNode
) {
756 // more efficient version of init_empty() / merge_from_succ()
757 self.successors
[ln
.get()] = succ_ln
;
759 self.indices2(ln
, succ_ln
, |this
, idx
, succ_idx
| {
760 this
.users
[idx
] = this
.users
[succ_idx
]
762 debug
!("init_from_succ(ln={}, succ={})",
763 self.ln_str(ln
), self.ln_str(succ_ln
));
766 fn merge_from_succ(&mut self,
771 if ln
== succ_ln { return false; }
773 let mut changed
= false;
774 self.indices2(ln
, succ_ln
, |this
, idx
, succ_idx
| {
775 changed
|= copy_if_invalid(this
.users
[succ_idx
].reader
,
776 &mut this
.users
[idx
].reader
);
777 changed
|= copy_if_invalid(this
.users
[succ_idx
].writer
,
778 &mut this
.users
[idx
].writer
);
779 if this
.users
[succ_idx
].used
&& !this
.users
[idx
].used
{
780 this
.users
[idx
].used
= true;
785 debug
!("merge_from_succ(ln={:?}, succ={}, first_merge={}, changed={})",
786 ln
, self.ln_str(succ_ln
), first_merge
, changed
);
789 fn copy_if_invalid(src
: LiveNode
, dst
: &mut LiveNode
) -> bool
{
790 if src
.is_valid() && !dst
.is_valid() {
799 // Indicates that a local variable was *defined*; we know that no
800 // uses of the variable can precede the definition (resolve checks
801 // this) so we just clear out all the data.
802 fn define(&mut self, writer
: LiveNode
, var
: Variable
) {
803 let idx
= self.idx(writer
, var
);
804 self.users
[idx
].reader
= invalid_node();
805 self.users
[idx
].writer
= invalid_node();
807 debug
!("{:?} defines {:?} (idx={}): {}", writer
, var
,
808 idx
, self.ln_str(writer
));
811 // Either read, write, or both depending on the acc bitset
812 fn acc(&mut self, ln
: LiveNode
, var
: Variable
, acc
: u32) {
813 debug
!("{:?} accesses[{:x}] {:?}: {}",
814 ln
, acc
, var
, self.ln_str(ln
));
816 let idx
= self.idx(ln
, var
);
817 let user
= &mut self.users
[idx
];
819 if (acc
& ACC_WRITE
) != 0 {
820 user
.reader
= invalid_node();
824 // Important: if we both read/write, must do read second
825 // or else the write will override.
826 if (acc
& ACC_READ
) != 0 {
830 if (acc
& ACC_USE
) != 0 {
835 // _______________________________________________________________________
837 fn compute(&mut self, decl
: &ast
::FnDecl
, body
: &ast
::Block
) -> LiveNode
{
838 // if there is a `break` or `again` at the top level, then it's
839 // effectively a return---this only occurs in `for` loops,
840 // where the body is really a closure.
842 debug
!("compute: using id for block, {}", block_to_string(body
));
844 let exit_ln
= self.s
.exit_ln
;
845 let entry_ln
: LiveNode
=
846 self.with_loop_nodes(body
.id
, exit_ln
, exit_ln
,
847 |this
| this
.propagate_through_fn_block(decl
, body
));
849 // hack to skip the loop unless debug! is enabled:
850 debug
!("^^ liveness computation results for body {} (entry={:?})",
852 for ln_idx
in 0..self.ir
.num_live_nodes
{
853 debug
!("{:?}", self.ln_str(LiveNode(ln_idx
)));
862 fn propagate_through_fn_block(&mut self, _
: &ast
::FnDecl
, blk
: &ast
::Block
)
864 // the fallthrough exit is only for those cases where we do not
865 // explicitly return:
867 self.init_from_succ(s
.fallthrough_ln
, s
.exit_ln
);
868 if blk
.expr
.is_none() {
869 self.acc(s
.fallthrough_ln
, s
.no_ret_var
, ACC_READ
)
871 self.acc(s
.fallthrough_ln
, s
.clean_exit_var
, ACC_READ
);
873 self.propagate_through_block(blk
, s
.fallthrough_ln
)
876 fn propagate_through_block(&mut self, blk
: &ast
::Block
, succ
: LiveNode
)
878 let succ
= self.propagate_through_opt_expr(blk
.expr
.as_ref().map(|e
| &**e
), succ
);
879 blk
.stmts
.iter().rev().fold(succ
, |succ
, stmt
| {
880 self.propagate_through_stmt(&**stmt
, succ
)
884 fn propagate_through_stmt(&mut self, stmt
: &ast
::Stmt
, succ
: LiveNode
)
887 ast
::StmtDecl(ref decl
, _
) => {
888 self.propagate_through_decl(&**decl
, succ
)
891 ast
::StmtExpr(ref expr
, _
) | ast
::StmtSemi(ref expr
, _
) => {
892 self.propagate_through_expr(&**expr
, succ
)
895 ast
::StmtMac(..) => {
896 self.ir
.tcx
.sess
.span_bug(stmt
.span
, "unexpanded macro");
901 fn propagate_through_decl(&mut self, decl
: &ast
::Decl
, succ
: LiveNode
)
904 ast
::DeclLocal(ref local
) => {
905 self.propagate_through_local(&**local
, succ
)
907 ast
::DeclItem(_
) => succ
,
911 fn propagate_through_local(&mut self, local
: &ast
::Local
, succ
: LiveNode
)
913 // Note: we mark the variable as defined regardless of whether
914 // there is an initializer. Initially I had thought to only mark
915 // the live variable as defined if it was initialized, and then we
916 // could check for uninit variables just by scanning what is live
917 // at the start of the function. But that doesn't work so well for
918 // immutable variables defined in a loop:
919 // loop { let x; x = 5; }
920 // because the "assignment" loops back around and generates an error.
922 // So now we just check that variables defined w/o an
923 // initializer are not live at the point of their
924 // initialization, which is mildly more complex than checking
925 // once at the func header but otherwise equivalent.
927 let succ
= self.propagate_through_opt_expr(local
.init
.as_ref().map(|e
| &**e
), succ
);
928 self.define_bindings_in_pat(&*local
.pat
, succ
)
931 fn propagate_through_exprs(&mut self, exprs
: &[P
<Expr
>], succ
: LiveNode
)
933 exprs
.iter().rev().fold(succ
, |succ
, expr
| {
934 self.propagate_through_expr(&**expr
, succ
)
938 fn propagate_through_opt_expr(&mut self,
939 opt_expr
: Option
<&Expr
>,
942 opt_expr
.map_or(succ
, |expr
| self.propagate_through_expr(expr
, succ
))
945 fn propagate_through_expr(&mut self, expr
: &Expr
, succ
: LiveNode
)
947 debug
!("propagate_through_expr: {}", expr_to_string(expr
));
950 // Interesting cases with control flow or which gen/kill
952 ast
::ExprPath(..) => {
953 self.access_path(expr
, succ
, ACC_READ
| ACC_USE
)
956 ast
::ExprField(ref e
, _
) => {
957 self.propagate_through_expr(&**e
, succ
)
960 ast
::ExprTupField(ref e
, _
) => {
961 self.propagate_through_expr(&**e
, succ
)
964 ast
::ExprClosure(_
, _
, ref blk
) => {
965 debug
!("{} is an ExprClosure",
966 expr_to_string(expr
));
969 The next-node for a break is the successor of the entire
970 loop. The next-node for a continue is the top of this loop.
972 let node
= self.live_node(expr
.id
, expr
.span
);
973 self.with_loop_nodes(blk
.id
, succ
, node
, |this
| {
975 // the construction of a closure itself is not important,
976 // but we have to consider the closed over variables.
977 let caps
= match this
.ir
.capture_info_map
.get(&expr
.id
) {
978 Some(caps
) => caps
.clone(),
980 this
.ir
.tcx
.sess
.span_bug(expr
.span
, "no registered caps");
983 caps
.iter().rev().fold(succ
, |succ
, cap
| {
984 this
.init_from_succ(cap
.ln
, succ
);
985 let var
= this
.variable(cap
.var_nid
, expr
.span
);
986 this
.acc(cap
.ln
, var
, ACC_READ
| ACC_USE
);
992 ast
::ExprIf(ref cond
, ref then
, ref els
) => {
1006 let else_ln
= self.propagate_through_opt_expr(els
.as_ref().map(|e
| &**e
), succ
);
1007 let then_ln
= self.propagate_through_block(&**then
, succ
);
1008 let ln
= self.live_node(expr
.id
, expr
.span
);
1009 self.init_from_succ(ln
, else_ln
);
1010 self.merge_from_succ(ln
, then_ln
, false);
1011 self.propagate_through_expr(&**cond
, ln
)
1014 ast
::ExprIfLet(..) => {
1015 self.ir
.tcx
.sess
.span_bug(expr
.span
, "non-desugared ExprIfLet");
1018 ast
::ExprWhile(ref cond
, ref blk
, _
) => {
1019 self.propagate_through_loop(expr
, WhileLoop(&**cond
), &**blk
, succ
)
1022 ast
::ExprWhileLet(..) => {
1023 self.ir
.tcx
.sess
.span_bug(expr
.span
, "non-desugared ExprWhileLet");
1026 ast
::ExprForLoop(..) => {
1027 self.ir
.tcx
.sess
.span_bug(expr
.span
, "non-desugared ExprForLoop");
1030 // Note that labels have been resolved, so we don't need to look
1031 // at the label ident
1032 ast
::ExprLoop(ref blk
, _
) => {
1033 self.propagate_through_loop(expr
, LoopLoop
, &**blk
, succ
)
1036 ast
::ExprMatch(ref e
, ref arms
, _
) => {
1051 let ln
= self.live_node(expr
.id
, expr
.span
);
1052 self.init_empty(ln
, succ
);
1053 let mut first_merge
= true;
1056 self.propagate_through_expr(&*arm
.body
, succ
);
1058 self.propagate_through_opt_expr(arm
.guard
.as_ref().map(|e
| &**e
), body_succ
);
1059 // only consider the first pattern; any later patterns must have
1060 // the same bindings, and we also consider the first pattern to be
1061 // the "authoritative" set of ids
1063 self.define_bindings_in_arm_pats(arm
.pats
.first().map(|p
| &**p
),
1065 self.merge_from_succ(ln
, arm_succ
, first_merge
);
1066 first_merge
= false;
1068 self.propagate_through_expr(&**e
, ln
)
1071 ast
::ExprRet(ref o_e
) => {
1072 // ignore succ and subst exit_ln:
1073 let exit_ln
= self.s
.exit_ln
;
1074 self.propagate_through_opt_expr(o_e
.as_ref().map(|e
| &**e
), exit_ln
)
1077 ast
::ExprBreak(opt_label
) => {
1078 // Find which label this break jumps to
1079 let sc
= self.find_loop_scope(opt_label
, expr
.id
, expr
.span
);
1081 // Now that we know the label we're going to,
1082 // look it up in the break loop nodes table
1084 match self.break_ln
.get(&sc
) {
1086 None
=> self.ir
.tcx
.sess
.span_bug(expr
.span
,
1087 "break to unknown label")
1091 ast
::ExprAgain(opt_label
) => {
1092 // Find which label this expr continues to
1093 let sc
= self.find_loop_scope(opt_label
, expr
.id
, expr
.span
);
1095 // Now that we know the label we're going to,
1096 // look it up in the continue loop nodes table
1098 match self.cont_ln
.get(&sc
) {
1100 None
=> self.ir
.tcx
.sess
.span_bug(expr
.span
,
1101 "loop to unknown label")
1105 ast
::ExprAssign(ref l
, ref r
) => {
1106 // see comment on lvalues in
1107 // propagate_through_lvalue_components()
1108 let succ
= self.write_lvalue(&**l
, succ
, ACC_WRITE
);
1109 let succ
= self.propagate_through_lvalue_components(&**l
, succ
);
1110 self.propagate_through_expr(&**r
, succ
)
1113 ast
::ExprAssignOp(_
, ref l
, ref r
) => {
1114 // see comment on lvalues in
1115 // propagate_through_lvalue_components()
1116 let succ
= self.write_lvalue(&**l
, succ
, ACC_WRITE
|ACC_READ
);
1117 let succ
= self.propagate_through_expr(&**r
, succ
);
1118 self.propagate_through_lvalue_components(&**l
, succ
)
1121 // Uninteresting cases: just propagate in rev exec order
1123 ast
::ExprVec(ref exprs
) => {
1124 self.propagate_through_exprs(&exprs
[..], succ
)
1127 ast
::ExprRepeat(ref element
, ref count
) => {
1128 let succ
= self.propagate_through_expr(&**count
, succ
);
1129 self.propagate_through_expr(&**element
, succ
)
1132 ast
::ExprStruct(_
, ref fields
, ref with_expr
) => {
1133 let succ
= self.propagate_through_opt_expr(with_expr
.as_ref().map(|e
| &**e
), succ
);
1134 fields
.iter().rev().fold(succ
, |succ
, field
| {
1135 self.propagate_through_expr(&*field
.expr
, succ
)
1139 ast
::ExprCall(ref f
, ref args
) => {
1140 let diverges
= !self.ir
.tcx
.is_method_call(expr
.id
) && {
1141 ty
::ty_fn_ret(ty
::expr_ty_adjusted(self.ir
.tcx
, &**f
)).diverges()
1143 let succ
= if diverges
{
1148 let succ
= self.propagate_through_exprs(&args
[..], succ
);
1149 self.propagate_through_expr(&**f
, succ
)
1152 ast
::ExprMethodCall(_
, _
, ref args
) => {
1153 let method_call
= ty
::MethodCall
::expr(expr
.id
);
1154 let method_ty
= self.ir
.tcx
.method_map
.borrow().get(&method_call
).unwrap().ty
;
1155 let diverges
= ty
::ty_fn_ret(method_ty
).diverges();
1156 let succ
= if diverges
{
1161 self.propagate_through_exprs(&args
[..], succ
)
1164 ast
::ExprTup(ref exprs
) => {
1165 self.propagate_through_exprs(&exprs
[..], succ
)
1168 ast
::ExprBinary(op
, ref l
, ref r
) if ast_util
::lazy_binop(op
.node
) => {
1169 let r_succ
= self.propagate_through_expr(&**r
, succ
);
1171 let ln
= self.live_node(expr
.id
, expr
.span
);
1172 self.init_from_succ(ln
, succ
);
1173 self.merge_from_succ(ln
, r_succ
, false);
1175 self.propagate_through_expr(&**l
, ln
)
1178 ast
::ExprIndex(ref l
, ref r
) |
1179 ast
::ExprBinary(_
, ref l
, ref r
) |
1180 ast
::ExprBox(Some(ref l
), ref r
) => {
1181 let r_succ
= self.propagate_through_expr(&**r
, succ
);
1182 self.propagate_through_expr(&**l
, r_succ
)
1185 ast
::ExprRange(ref e1
, ref e2
) => {
1186 let succ
= e2
.as_ref().map_or(succ
, |e
| self.propagate_through_expr(&**e
, succ
));
1187 e1
.as_ref().map_or(succ
, |e
| self.propagate_through_expr(&**e
, succ
))
1190 ast
::ExprBox(None
, ref e
) |
1191 ast
::ExprAddrOf(_
, ref e
) |
1192 ast
::ExprCast(ref e
, _
) |
1193 ast
::ExprUnary(_
, ref e
) |
1194 ast
::ExprParen(ref e
) => {
1195 self.propagate_through_expr(&**e
, succ
)
1198 ast
::ExprInlineAsm(ref ia
) => {
1200 let succ
= ia
.outputs
.iter().rev().fold(succ
, |succ
, &(_
, ref expr
, _
)| {
1201 // see comment on lvalues
1202 // in propagate_through_lvalue_components()
1203 let succ
= self.write_lvalue(&**expr
, succ
, ACC_WRITE
);
1204 self.propagate_through_lvalue_components(&**expr
, succ
)
1206 // Inputs are executed first. Propagate last because of rev order
1207 ia
.inputs
.iter().rev().fold(succ
, |succ
, &(_
, ref expr
)| {
1208 self.propagate_through_expr(&**expr
, succ
)
1212 ast
::ExprLit(..) => {
1216 ast
::ExprBlock(ref blk
) => {
1217 self.propagate_through_block(&**blk
, succ
)
1220 ast
::ExprMac(..) => {
1221 self.ir
.tcx
.sess
.span_bug(expr
.span
, "unexpanded macro");
1226 fn propagate_through_lvalue_components(&mut self,
1232 // In general, the full flow graph structure for an
1233 // assignment/move/etc can be handled in one of two ways,
1234 // depending on whether what is being assigned is a "tracked
1235 // value" or not. A tracked value is basically a local
1236 // variable or argument.
1238 // The two kinds of graphs are:
1240 // Tracked lvalue Untracked lvalue
1241 // ----------------------++-----------------------
1245 // (rvalue) || (rvalue)
1248 // (write of lvalue) || (lvalue components)
1253 // ----------------------++-----------------------
1255 // I will cover the two cases in turn:
1257 // # Tracked lvalues
1259 // A tracked lvalue is a local variable/argument `x`. In
1260 // these cases, the link_node where the write occurs is linked
1261 // to node id of `x`. The `write_lvalue()` routine generates
1262 // the contents of this node. There are no subcomponents to
1265 // # Non-tracked lvalues
1267 // These are lvalues like `x[5]` or `x.f`. In that case, we
1268 // basically ignore the value which is written to but generate
1269 // reads for the components---`x` in these two examples. The
1270 // components reads are generated by
1271 // `propagate_through_lvalue_components()` (this fn).
1273 // # Illegal lvalues
1275 // It is still possible to observe assignments to non-lvalues;
1276 // these errors are detected in the later pass borrowck. We
1277 // just ignore such cases and treat them as reads.
1280 ast
::ExprPath(..) => succ
,
1281 ast
::ExprField(ref e
, _
) => self.propagate_through_expr(&**e
, succ
),
1282 ast
::ExprTupField(ref e
, _
) => self.propagate_through_expr(&**e
, succ
),
1283 _
=> self.propagate_through_expr(expr
, succ
)
1287 // see comment on propagate_through_lvalue()
1288 fn write_lvalue(&mut self, expr
: &Expr
, succ
: LiveNode
, acc
: u32)
1291 ast
::ExprPath(..) => {
1292 self.access_path(expr
, succ
, acc
)
1295 // We do not track other lvalues, so just propagate through
1296 // to their subcomponents. Also, it may happen that
1297 // non-lvalues occur here, because those are detected in the
1298 // later pass borrowck.
1303 fn access_path(&mut self, expr
: &Expr
, succ
: LiveNode
, acc
: u32)
1305 match self.ir
.tcx
.def_map
.borrow().get(&expr
.id
).unwrap().full_def() {
1307 let ln
= self.live_node(expr
.id
, expr
.span
);
1309 self.init_from_succ(ln
, succ
);
1310 let var
= self.variable(nid
, expr
.span
);
1311 self.acc(ln
, var
, acc
);
1319 fn propagate_through_loop(&mut self,
1328 We model control flow like this:
1346 let mut first_merge
= true;
1347 let ln
= self.live_node(expr
.id
, expr
.span
);
1348 self.init_empty(ln
, succ
);
1352 // If this is not a `loop` loop, then it's possible we bypass
1353 // the body altogether. Otherwise, the only way is via a `break`
1354 // in the loop body.
1355 self.merge_from_succ(ln
, succ
, first_merge
);
1356 first_merge
= false;
1359 debug
!("propagate_through_loop: using id for loop body {} {}",
1360 expr
.id
, block_to_string(body
));
1362 let cond_ln
= match kind
{
1364 WhileLoop(ref cond
) => self.propagate_through_expr(&**cond
, ln
),
1366 let body_ln
= self.with_loop_nodes(expr
.id
, succ
, ln
, |this
| {
1367 this
.propagate_through_block(body
, cond_ln
)
1370 // repeat until fixed point is reached:
1371 while self.merge_from_succ(ln
, body_ln
, first_merge
) {
1372 first_merge
= false;
1374 let new_cond_ln
= match kind
{
1376 WhileLoop(ref cond
) => {
1377 self.propagate_through_expr(&**cond
, ln
)
1380 assert
!(cond_ln
== new_cond_ln
);
1381 assert
!(body_ln
== self.with_loop_nodes(expr
.id
, succ
, ln
,
1382 |this
| this
.propagate_through_block(body
, cond_ln
)));
1388 fn with_loop_nodes
<R
, F
>(&mut self,
1389 loop_node_id
: NodeId
,
1394 F
: FnOnce(&mut Liveness
<'a
, 'tcx
>) -> R
,
1396 debug
!("with_loop_nodes: {} {}", loop_node_id
, break_ln
.get());
1397 self.loop_scope
.push(loop_node_id
);
1398 self.break_ln
.insert(loop_node_id
, break_ln
);
1399 self.cont_ln
.insert(loop_node_id
, cont_ln
);
1401 self.loop_scope
.pop();
1406 // _______________________________________________________________________
1407 // Checking for error conditions
1409 fn check_local(this
: &mut Liveness
, local
: &ast
::Local
) {
1412 this
.warn_about_unused_or_dead_vars_in_pat(&*local
.pat
);
1415 this
.pat_bindings(&*local
.pat
, |this
, ln
, var
, sp
, id
| {
1416 this
.warn_about_unused(sp
, id
, ln
, var
);
1421 visit
::walk_local(this
, local
);
1424 fn check_arm(this
: &mut Liveness
, arm
: &ast
::Arm
) {
1425 // only consider the first pattern; any later patterns must have
1426 // the same bindings, and we also consider the first pattern to be
1427 // the "authoritative" set of ids
1428 this
.arm_pats_bindings(arm
.pats
.first().map(|p
| &**p
), |this
, ln
, var
, sp
, id
| {
1429 this
.warn_about_unused(sp
, id
, ln
, var
);
1431 visit
::walk_arm(this
, arm
);
1434 fn check_expr(this
: &mut Liveness
, expr
: &Expr
) {
1436 ast
::ExprAssign(ref l
, ref r
) => {
1437 this
.check_lvalue(&**l
);
1438 this
.visit_expr(&**r
);
1440 visit
::walk_expr(this
, expr
);
1443 ast
::ExprAssignOp(_
, ref l
, _
) => {
1444 this
.check_lvalue(&**l
);
1446 visit
::walk_expr(this
, expr
);
1449 ast
::ExprInlineAsm(ref ia
) => {
1450 for &(_
, ref input
) in &ia
.inputs
{
1451 this
.visit_expr(&**input
);
1454 // Output operands must be lvalues
1455 for &(_
, ref out
, _
) in &ia
.outputs
{
1456 this
.check_lvalue(&**out
);
1457 this
.visit_expr(&**out
);
1460 visit
::walk_expr(this
, expr
);
1463 // no correctness conditions related to liveness
1464 ast
::ExprCall(..) | ast
::ExprMethodCall(..) | ast
::ExprIf(..) |
1465 ast
::ExprMatch(..) | ast
::ExprWhile(..) | ast
::ExprLoop(..) |
1466 ast
::ExprIndex(..) | ast
::ExprField(..) | ast
::ExprTupField(..) |
1467 ast
::ExprVec(..) | ast
::ExprTup(..) | ast
::ExprBinary(..) |
1468 ast
::ExprCast(..) | ast
::ExprUnary(..) | ast
::ExprRet(..) |
1469 ast
::ExprBreak(..) | ast
::ExprAgain(..) | ast
::ExprLit(_
) |
1470 ast
::ExprBlock(..) | ast
::ExprMac(..) | ast
::ExprAddrOf(..) |
1471 ast
::ExprStruct(..) | ast
::ExprRepeat(..) | ast
::ExprParen(..) |
1472 ast
::ExprClosure(..) | ast
::ExprPath(..) | ast
::ExprBox(..) |
1473 ast
::ExprRange(..) => {
1474 visit
::walk_expr(this
, expr
);
1476 ast
::ExprIfLet(..) => {
1477 this
.ir
.tcx
.sess
.span_bug(expr
.span
, "non-desugared ExprIfLet");
1479 ast
::ExprWhileLet(..) => {
1480 this
.ir
.tcx
.sess
.span_bug(expr
.span
, "non-desugared ExprWhileLet");
1482 ast
::ExprForLoop(..) => {
1483 this
.ir
.tcx
.sess
.span_bug(expr
.span
, "non-desugared ExprForLoop");
1488 fn check_fn(_v
: &Liveness
,
1490 _decl
: &ast
::FnDecl
,
1494 // do not check contents of nested fns
1497 impl<'a
, 'tcx
> Liveness
<'a
, 'tcx
> {
1498 fn fn_ret(&self, id
: NodeId
) -> ty
::PolyFnOutput
<'tcx
> {
1499 let fn_ty
= ty
::node_id_to_type(self.ir
.tcx
, id
);
1501 ty
::ty_closure(closure_def_id
, substs
) =>
1502 self.ir
.tcx
.closure_type(closure_def_id
, substs
).sig
.output(),
1504 ty
::ty_fn_ret(fn_ty
),
1515 // within the fn body, late-bound regions are liberated:
1517 ty
::liberate_late_bound_regions(
1519 region
::DestructionScopeData
::new(body
.id
),
1523 ty
::FnConverging(t_ret
)
1524 if self.live_on_entry(entry_ln
, self.s
.no_ret_var
).is_some() => {
1526 if ty
::type_is_nil(t_ret
) {
1527 // for nil return types, it is ok to not return a value expl.
1529 let ends_with_stmt
= match body
.expr
{
1530 None
if !body
.stmts
.is_empty() =>
1531 match body
.stmts
.first().unwrap().node
{
1532 ast
::StmtSemi(ref e
, _
) => {
1533 ty
::expr_ty(self.ir
.tcx
, &**e
) == t_ret
1539 span_err
!(self.ir
.tcx
.sess
, sp
, E0269
, "not all control paths return a value");
1541 let last_stmt
= body
.stmts
.first().unwrap();
1542 let original_span
= original_sp(self.ir
.tcx
.sess
.codemap(),
1543 last_stmt
.span
, sp
);
1544 let span_semicolon
= Span
{
1545 lo
: original_span
.hi
- BytePos(1),
1546 hi
: original_span
.hi
,
1547 expn_id
: original_span
.expn_id
1549 self.ir
.tcx
.sess
.span_help(
1550 span_semicolon
, "consider removing this semicolon:");
1555 if self.live_on_entry(entry_ln
, self.s
.clean_exit_var
).is_some() => {
1556 span_err
!(self.ir
.tcx
.sess
, sp
, E0270
,
1557 "computation may converge in a function marked as diverging");
1564 fn check_lvalue(&mut self, expr
: &Expr
) {
1566 ast
::ExprPath(..) => {
1567 if let DefLocal(nid
) = self.ir
.tcx
.def_map
.borrow().get(&expr
.id
)
1570 // Assignment to an immutable variable or argument: only legal
1571 // if there is no later assignment. If this local is actually
1572 // mutable, then check for a reassignment to flag the mutability
1574 let ln
= self.live_node(expr
.id
, expr
.span
);
1575 let var
= self.variable(nid
, expr
.span
);
1576 self.warn_about_dead_assign(expr
.span
, expr
.id
, ln
, var
);
1580 // For other kinds of lvalues, no checks are required,
1581 // and any embedded expressions are actually rvalues
1582 visit
::walk_expr(self, expr
);
1587 fn should_warn(&self, var
: Variable
) -> Option
<String
> {
1588 let name
= self.ir
.variable_name(var
);
1589 if name
.is_empty() || name
.as_bytes()[0] == ('_'
as u8) {
1596 fn warn_about_unused_args(&self, decl
: &ast
::FnDecl
, entry_ln
: LiveNode
) {
1597 for arg
in &decl
.inputs
{
1598 pat_util
::pat_bindings(&self.ir
.tcx
.def_map
,
1600 |_bm
, p_id
, sp
, path1
| {
1601 let var
= self.variable(p_id
, sp
);
1602 // Ignore unused self.
1603 let ident
= path1
.node
;
1604 if ident
.name
!= special_idents
::self_
.name
{
1605 self.warn_about_unused(sp
, p_id
, entry_ln
, var
);
1611 fn warn_about_unused_or_dead_vars_in_pat(&mut self, pat
: &ast
::Pat
) {
1612 self.pat_bindings(pat
, |this
, ln
, var
, sp
, id
| {
1613 if !this
.warn_about_unused(sp
, id
, ln
, var
) {
1614 this
.warn_about_dead_assign(sp
, id
, ln
, var
);
1619 fn warn_about_unused(&self,
1625 if !self.used_on_entry(ln
, var
) {
1626 let r
= self.should_warn(var
);
1627 if let Some(name
) = r
{
1629 // annoying: for parameters in funcs like `fn(x: int)
1630 // {ret}`, there is only one node, so asking about
1631 // assigned_on_exit() is not meaningful.
1632 let is_assigned
= if ln
== self.s
.exit_ln
{
1635 self.assigned_on_exit(ln
, var
).is_some()
1639 self.ir
.tcx
.sess
.add_lint(lint
::builtin
::UNUSED_VARIABLES
, id
, sp
,
1640 format
!("variable `{}` is assigned to, but never used",
1643 self.ir
.tcx
.sess
.add_lint(lint
::builtin
::UNUSED_VARIABLES
, id
, sp
,
1644 format
!("unused variable: `{}`", name
));
1653 fn warn_about_dead_assign(&self,
1658 if self.live_on_exit(ln
, var
).is_none() {
1659 let r
= self.should_warn(var
);
1660 if let Some(name
) = r
{
1661 self.ir
.tcx
.sess
.add_lint(lint
::builtin
::UNUSED_ASSIGNMENTS
, id
, sp
,
1662 format
!("value assigned to `{}` is never read", name
));