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