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