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