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