rustc_passes/
liveness.rs

1//! A classic liveness analysis based on dataflow over the AST. Computes,
2//! for each local variable in a function, whether that variable is live
3//! at a given point. Program execution points are identified by their
4//! IDs.
5//!
6//! # Basic idea
7//!
8//! The basic model is that each local variable is assigned an index. We
9//! represent sets of local variables using a vector indexed by this
10//! index. The value in the vector is either 0, indicating the variable
11//! is dead, or the ID of an expression that uses the variable.
12//!
13//! We conceptually walk over the AST in reverse execution order. If we
14//! find a use of a variable, we add it to the set of live variables. If
15//! we find an assignment to a variable, we remove it from the set of live
16//! variables. When we have to merge two flows, we take the union of
17//! those two flows -- if the variable is live on both paths, we simply
18//! pick one ID. In the event of loops, we continue doing this until a
19//! fixed point is reached.
20//!
21//! ## Checking initialization
22//!
23//! At the function entry point, all variables must be dead. If this is
24//! not the case, we can report an error using the ID found in the set of
25//! live variables, which identifies a use of the variable which is not
26//! dominated by an assignment.
27//!
28//! ## Checking moves
29//!
30//! After each explicit move, the variable must be dead.
31//!
32//! ## Computing last uses
33//!
34//! Any use of the variable where the variable is dead afterwards is a
35//! last use.
36//!
37//! # Implementation details
38//!
39//! The actual implementation contains two (nested) walks over the AST.
40//! The outer walk has the job of building up the ir_maps instance for the
41//! enclosing function. On the way down the tree, it identifies those AST
42//! nodes and variable IDs that will be needed for the liveness analysis
43//! and assigns them contiguous IDs. The liveness ID for an AST node is
44//! called a `live_node` (it's a newtype'd `u32`) and the ID for a variable
45//! is called a `variable` (another newtype'd `u32`).
46//!
47//! On the way back up the tree, as we are about to exit from a function
48//! declaration we allocate a `liveness` instance. Now that we know
49//! precisely how many nodes and variables we need, we can allocate all
50//! the various arrays that we will need to precisely the right size. We then
51//! perform the actual propagation on the `liveness` instance.
52//!
53//! This propagation is encoded in the various `propagate_through_*()`
54//! methods. It effectively does a reverse walk of the AST; whenever we
55//! reach a loop node, we iterate until a fixed point is reached.
56//!
57//! ## The `RWU` struct
58//!
59//! At each live node `N`, we track three pieces of information for each
60//! variable `V` (these are encapsulated in the `RWU` struct):
61//!
62//! - `reader`: the `LiveNode` ID of some node which will read the value
63//!    that `V` holds on entry to `N`. Formally: a node `M` such
64//!    that there exists a path `P` from `N` to `M` where `P` does not
65//!    write `V`. If the `reader` is `None`, then the current
66//!    value will never be read (the variable is dead, essentially).
67//!
68//! - `writer`: the `LiveNode` ID of some node which will write the
69//!    variable `V` and which is reachable from `N`. Formally: a node `M`
70//!    such that there exists a path `P` from `N` to `M` and `M` writes
71//!    `V`. If the `writer` is `None`, then there is no writer
72//!    of `V` that follows `N`.
73//!
74//! - `used`: a boolean value indicating whether `V` is *used*. We
75//!   distinguish a *read* from a *use* in that a *use* is some read that
76//!   is not just used to generate a new value. For example, `x += 1` is
77//!   a read but not a use. This is used to generate better warnings.
78//!
79//! ## Special nodes and variables
80//!
81//! We generate various special nodes for various, well, special purposes.
82//! These are described in the `Liveness` struct.
83
84use std::io;
85use std::io::prelude::*;
86use std::rc::Rc;
87
88use rustc_data_structures::fx::FxIndexMap;
89use rustc_hir as hir;
90use rustc_hir::def::*;
91use rustc_hir::def_id::LocalDefId;
92use rustc_hir::intravisit::{self, Visitor};
93use rustc_hir::{Expr, HirId, HirIdMap, HirIdSet};
94use rustc_index::IndexVec;
95use rustc_middle::query::Providers;
96use rustc_middle::span_bug;
97use rustc_middle::ty::{self, RootVariableMinCaptureList, Ty, TyCtxt};
98use rustc_session::lint;
99use rustc_span::{BytePos, Span, Symbol, sym};
100use tracing::{debug, instrument};
101
102use self::LiveNodeKind::*;
103use self::VarKind::*;
104use crate::errors;
105
106mod rwu_table;
107
108rustc_index::newtype_index! {
109    #[debug_format = "v({})"]
110    pub struct Variable {}
111}
112
113rustc_index::newtype_index! {
114    #[debug_format = "ln({})"]
115    pub struct LiveNode {}
116}
117
118#[derive(Copy, Clone, PartialEq, Debug)]
119enum LiveNodeKind {
120    UpvarNode(Span),
121    ExprNode(Span, HirId),
122    VarDefNode(Span, HirId),
123    ClosureNode,
124    ExitNode,
125}
126
127fn live_node_kind_to_string(lnk: LiveNodeKind, tcx: TyCtxt<'_>) -> String {
128    let sm = tcx.sess.source_map();
129    match lnk {
130        UpvarNode(s) => format!("Upvar node [{}]", sm.span_to_diagnostic_string(s)),
131        ExprNode(s, _) => format!("Expr node [{}]", sm.span_to_diagnostic_string(s)),
132        VarDefNode(s, _) => format!("Var def node [{}]", sm.span_to_diagnostic_string(s)),
133        ClosureNode => "Closure node".to_owned(),
134        ExitNode => "Exit node".to_owned(),
135    }
136}
137
138fn check_liveness(tcx: TyCtxt<'_>, def_id: LocalDefId) {
139    // Don't run unused pass for #[derive()]
140    let parent = tcx.local_parent(def_id);
141    if let DefKind::Impl { .. } = tcx.def_kind(parent)
142        && tcx.has_attr(parent, sym::automatically_derived)
143    {
144        return;
145    }
146
147    // Don't run unused pass for #[naked]
148    if tcx.has_attr(def_id.to_def_id(), sym::naked) {
149        return;
150    }
151
152    let mut maps = IrMaps::new(tcx);
153    let body = tcx.hir_body_owned_by(def_id);
154    let hir_id = tcx.hir_body_owner(body.id());
155
156    if let Some(upvars) = tcx.upvars_mentioned(def_id) {
157        for &var_hir_id in upvars.keys() {
158            let var_name = tcx.hir_name(var_hir_id);
159            maps.add_variable(Upvar(var_hir_id, var_name));
160        }
161    }
162
163    // gather up the various local variables, significant expressions,
164    // and so forth:
165    maps.visit_body(&body);
166
167    // compute liveness
168    let mut lsets = Liveness::new(&mut maps, def_id);
169    let entry_ln = lsets.compute(&body, hir_id);
170    lsets.log_liveness(entry_ln, body.id().hir_id);
171
172    // check for various error conditions
173    lsets.visit_body(&body);
174    lsets.warn_about_unused_upvars(entry_ln);
175    lsets.warn_about_unused_args(&body, entry_ln);
176}
177
178pub(crate) fn provide(providers: &mut Providers) {
179    *providers = Providers { check_liveness, ..*providers };
180}
181
182// ______________________________________________________________________
183// Creating ir_maps
184//
185// This is the first pass and the one that drives the main
186// computation. It walks up and down the IR once. On the way down,
187// we count for each function the number of variables as well as
188// liveness nodes. A liveness node is basically an expression or
189// capture clause that does something of interest: either it has
190// interesting control flow or it uses/defines a local variable.
191//
192// On the way back up, at each function node we create liveness sets
193// (we now know precisely how big to make our various vectors and so
194// forth) and then do the data-flow propagation to compute the set
195// of live variables at each program point.
196//
197// Finally, we run back over the IR one last time and, using the
198// computed liveness, check various safety conditions. For example,
199// there must be no live nodes at the definition site for a variable
200// unless it has an initializer. Similarly, each non-mutable local
201// variable must not be assigned if there is some successor
202// assignment. And so forth.
203
204struct CaptureInfo {
205    ln: LiveNode,
206    var_hid: HirId,
207}
208
209#[derive(Copy, Clone, Debug)]
210struct LocalInfo {
211    id: HirId,
212    name: Symbol,
213    is_shorthand: bool,
214}
215
216#[derive(Copy, Clone, Debug)]
217enum VarKind {
218    Param(HirId, Symbol),
219    Local(LocalInfo),
220    Upvar(HirId, Symbol),
221}
222
223struct CollectLitsVisitor<'tcx> {
224    lit_exprs: Vec<&'tcx hir::Expr<'tcx>>,
225}
226
227impl<'tcx> Visitor<'tcx> for CollectLitsVisitor<'tcx> {
228    fn visit_expr(&mut self, expr: &'tcx Expr<'tcx>) {
229        if let hir::ExprKind::Lit(_) = expr.kind {
230            self.lit_exprs.push(expr);
231        }
232        intravisit::walk_expr(self, expr);
233    }
234}
235
236struct IrMaps<'tcx> {
237    tcx: TyCtxt<'tcx>,
238    live_node_map: HirIdMap<LiveNode>,
239    variable_map: HirIdMap<Variable>,
240    capture_info_map: HirIdMap<Rc<Vec<CaptureInfo>>>,
241    var_kinds: IndexVec<Variable, VarKind>,
242    lnks: IndexVec<LiveNode, LiveNodeKind>,
243}
244
245impl<'tcx> IrMaps<'tcx> {
246    fn new(tcx: TyCtxt<'tcx>) -> IrMaps<'tcx> {
247        IrMaps {
248            tcx,
249            live_node_map: HirIdMap::default(),
250            variable_map: HirIdMap::default(),
251            capture_info_map: Default::default(),
252            var_kinds: IndexVec::new(),
253            lnks: IndexVec::new(),
254        }
255    }
256
257    fn add_live_node(&mut self, lnk: LiveNodeKind) -> LiveNode {
258        let ln = self.lnks.push(lnk);
259
260        debug!("{:?} is of kind {}", ln, live_node_kind_to_string(lnk, self.tcx));
261
262        ln
263    }
264
265    fn add_live_node_for_node(&mut self, hir_id: HirId, lnk: LiveNodeKind) {
266        let ln = self.add_live_node(lnk);
267        self.live_node_map.insert(hir_id, ln);
268
269        debug!("{:?} is node {:?}", ln, hir_id);
270    }
271
272    fn add_variable(&mut self, vk: VarKind) -> Variable {
273        let v = self.var_kinds.push(vk);
274
275        match vk {
276            Local(LocalInfo { id: node_id, .. }) | Param(node_id, _) | Upvar(node_id, _) => {
277                self.variable_map.insert(node_id, v);
278            }
279        }
280
281        debug!("{:?} is {:?}", v, vk);
282
283        v
284    }
285
286    fn variable(&self, hir_id: HirId, span: Span) -> Variable {
287        match self.variable_map.get(&hir_id) {
288            Some(&var) => var,
289            None => {
290                span_bug!(span, "no variable registered for id {:?}", hir_id);
291            }
292        }
293    }
294
295    fn variable_name(&self, var: Variable) -> Symbol {
296        match self.var_kinds[var] {
297            Local(LocalInfo { name, .. }) | Param(_, name) | Upvar(_, name) => name,
298        }
299    }
300
301    fn variable_is_shorthand(&self, var: Variable) -> bool {
302        match self.var_kinds[var] {
303            Local(LocalInfo { is_shorthand, .. }) => is_shorthand,
304            Param(..) | Upvar(..) => false,
305        }
306    }
307
308    fn set_captures(&mut self, hir_id: HirId, cs: Vec<CaptureInfo>) {
309        self.capture_info_map.insert(hir_id, Rc::new(cs));
310    }
311
312    fn collect_shorthand_field_ids(&self, pat: &hir::Pat<'tcx>) -> HirIdSet {
313        // For struct patterns, take note of which fields used shorthand
314        // (`x` rather than `x: x`).
315        let mut shorthand_field_ids = HirIdSet::default();
316
317        pat.walk_always(|pat| {
318            if let hir::PatKind::Struct(_, fields, _) = pat.kind {
319                let short = fields.iter().filter(|f| f.is_shorthand);
320                shorthand_field_ids.extend(short.map(|f| f.pat.hir_id));
321            }
322        });
323
324        shorthand_field_ids
325    }
326
327    fn add_from_pat(&mut self, pat: &hir::Pat<'tcx>) {
328        let shorthand_field_ids = self.collect_shorthand_field_ids(pat);
329
330        pat.each_binding(|_, hir_id, _, ident| {
331            self.add_live_node_for_node(hir_id, VarDefNode(ident.span, hir_id));
332            self.add_variable(Local(LocalInfo {
333                id: hir_id,
334                name: ident.name,
335                is_shorthand: shorthand_field_ids.contains(&hir_id),
336            }));
337        });
338    }
339}
340
341impl<'tcx> Visitor<'tcx> for IrMaps<'tcx> {
342    fn visit_local(&mut self, local: &'tcx hir::LetStmt<'tcx>) {
343        self.add_from_pat(local.pat);
344        if local.els.is_some() {
345            self.add_live_node_for_node(local.hir_id, ExprNode(local.span, local.hir_id));
346        }
347        intravisit::walk_local(self, local);
348    }
349
350    fn visit_arm(&mut self, arm: &'tcx hir::Arm<'tcx>) {
351        self.add_from_pat(&arm.pat);
352        intravisit::walk_arm(self, arm);
353    }
354
355    fn visit_param(&mut self, param: &'tcx hir::Param<'tcx>) {
356        let shorthand_field_ids = self.collect_shorthand_field_ids(param.pat);
357        param.pat.each_binding(|_bm, hir_id, _x, ident| {
358            let var = match param.pat.kind {
359                rustc_hir::PatKind::Struct(..) => Local(LocalInfo {
360                    id: hir_id,
361                    name: ident.name,
362                    is_shorthand: shorthand_field_ids.contains(&hir_id),
363                }),
364                _ => Param(hir_id, ident.name),
365            };
366            self.add_variable(var);
367        });
368        intravisit::walk_param(self, param);
369    }
370
371    fn visit_expr(&mut self, expr: &'tcx Expr<'tcx>) {
372        match expr.kind {
373            // live nodes required for uses or definitions of variables:
374            hir::ExprKind::Path(hir::QPath::Resolved(_, path)) => {
375                debug!("expr {}: path that leads to {:?}", expr.hir_id, path.res);
376                if let Res::Local(_var_hir_id) = path.res {
377                    self.add_live_node_for_node(expr.hir_id, ExprNode(expr.span, expr.hir_id));
378                }
379            }
380            hir::ExprKind::Closure(closure) => {
381                // Interesting control flow (for loops can contain labeled
382                // breaks or continues)
383                self.add_live_node_for_node(expr.hir_id, ExprNode(expr.span, expr.hir_id));
384
385                // Make a live_node for each mentioned variable, with the span
386                // being the location that the variable is used. This results
387                // in better error messages than just pointing at the closure
388                // construction site.
389                let mut call_caps = Vec::new();
390                if let Some(upvars) = self.tcx.upvars_mentioned(closure.def_id) {
391                    call_caps.extend(upvars.keys().map(|var_id| {
392                        let upvar = upvars[var_id];
393                        let upvar_ln = self.add_live_node(UpvarNode(upvar.span));
394                        CaptureInfo { ln: upvar_ln, var_hid: *var_id }
395                    }));
396                }
397                self.set_captures(expr.hir_id, call_caps);
398            }
399
400            hir::ExprKind::Let(let_expr) => {
401                self.add_from_pat(let_expr.pat);
402            }
403
404            // live nodes required for interesting control flow:
405            hir::ExprKind::If(..)
406            | hir::ExprKind::Match(..)
407            | hir::ExprKind::Loop(..)
408            | hir::ExprKind::Yield(..) => {
409                self.add_live_node_for_node(expr.hir_id, ExprNode(expr.span, expr.hir_id));
410            }
411            hir::ExprKind::Binary(op, ..) if op.node.is_lazy() => {
412                self.add_live_node_for_node(expr.hir_id, ExprNode(expr.span, expr.hir_id));
413            }
414
415            // Inline assembly may contain labels.
416            hir::ExprKind::InlineAsm(asm) if asm.contains_label() => {
417                self.add_live_node_for_node(expr.hir_id, ExprNode(expr.span, expr.hir_id));
418                intravisit::walk_expr(self, expr);
419            }
420
421            // otherwise, live nodes are not required:
422            hir::ExprKind::Index(..)
423            | hir::ExprKind::Field(..)
424            | hir::ExprKind::Array(..)
425            | hir::ExprKind::Call(..)
426            | hir::ExprKind::MethodCall(..)
427            | hir::ExprKind::Use(..)
428            | hir::ExprKind::Tup(..)
429            | hir::ExprKind::Binary(..)
430            | hir::ExprKind::AddrOf(..)
431            | hir::ExprKind::Cast(..)
432            | hir::ExprKind::DropTemps(..)
433            | hir::ExprKind::Unary(..)
434            | hir::ExprKind::Break(..)
435            | hir::ExprKind::Continue(_)
436            | hir::ExprKind::Lit(_)
437            | hir::ExprKind::ConstBlock(..)
438            | hir::ExprKind::Ret(..)
439            | hir::ExprKind::Become(..)
440            | hir::ExprKind::Block(..)
441            | hir::ExprKind::Assign(..)
442            | hir::ExprKind::AssignOp(..)
443            | hir::ExprKind::Struct(..)
444            | hir::ExprKind::Repeat(..)
445            | hir::ExprKind::InlineAsm(..)
446            | hir::ExprKind::OffsetOf(..)
447            | hir::ExprKind::Type(..)
448            | hir::ExprKind::UnsafeBinderCast(..)
449            | hir::ExprKind::Err(_)
450            | hir::ExprKind::Path(hir::QPath::TypeRelative(..))
451            | hir::ExprKind::Path(hir::QPath::LangItem(..)) => {}
452        }
453        intravisit::walk_expr(self, expr);
454    }
455}
456
457// ______________________________________________________________________
458// Computing liveness sets
459//
460// Actually we compute just a bit more than just liveness, but we use
461// the same basic propagation framework in all cases.
462
463const ACC_READ: u32 = 1;
464const ACC_WRITE: u32 = 2;
465const ACC_USE: u32 = 4;
466
467struct Liveness<'a, 'tcx> {
468    ir: &'a mut IrMaps<'tcx>,
469    typeck_results: &'a ty::TypeckResults<'tcx>,
470    typing_env: ty::TypingEnv<'tcx>,
471    closure_min_captures: Option<&'tcx RootVariableMinCaptureList<'tcx>>,
472    successors: IndexVec<LiveNode, Option<LiveNode>>,
473    rwu_table: rwu_table::RWUTable,
474
475    /// A live node representing a point of execution before closure entry &
476    /// after closure exit. Used to calculate liveness of captured variables
477    /// through calls to the same closure. Used for Fn & FnMut closures only.
478    closure_ln: LiveNode,
479    /// A live node representing every 'exit' from the function, whether it be
480    /// by explicit return, panic, or other means.
481    exit_ln: LiveNode,
482
483    // mappings from loop node ID to LiveNode
484    // ("break" label should map to loop node ID,
485    // it probably doesn't now)
486    break_ln: HirIdMap<LiveNode>,
487    cont_ln: HirIdMap<LiveNode>,
488}
489
490impl<'a, 'tcx> Liveness<'a, 'tcx> {
491    fn new(ir: &'a mut IrMaps<'tcx>, body_owner: LocalDefId) -> Liveness<'a, 'tcx> {
492        let typeck_results = ir.tcx.typeck(body_owner);
493        // Liveness linting runs after building the THIR. We make several assumptions based on
494        // typeck succeeding, e.g. that breaks and continues are well-formed.
495        assert!(typeck_results.tainted_by_errors.is_none());
496        // FIXME(#132279): we're in a body here.
497        let typing_env = ty::TypingEnv::non_body_analysis(ir.tcx, body_owner);
498        let closure_min_captures = typeck_results.closure_min_captures.get(&body_owner);
499        let closure_ln = ir.add_live_node(ClosureNode);
500        let exit_ln = ir.add_live_node(ExitNode);
501
502        let num_live_nodes = ir.lnks.len();
503        let num_vars = ir.var_kinds.len();
504
505        Liveness {
506            ir,
507            typeck_results,
508            typing_env,
509            closure_min_captures,
510            successors: IndexVec::from_elem_n(None, num_live_nodes),
511            rwu_table: rwu_table::RWUTable::new(num_live_nodes, num_vars),
512            closure_ln,
513            exit_ln,
514            break_ln: Default::default(),
515            cont_ln: Default::default(),
516        }
517    }
518
519    fn live_node(&self, hir_id: HirId, span: Span) -> LiveNode {
520        match self.ir.live_node_map.get(&hir_id) {
521            Some(&ln) => ln,
522            None => {
523                // This must be a mismatch between the ir_map construction
524                // above and the propagation code below; the two sets of
525                // code have to agree about which AST nodes are worth
526                // creating liveness nodes for.
527                span_bug!(span, "no live node registered for node {:?}", hir_id);
528            }
529        }
530    }
531
532    fn variable(&self, hir_id: HirId, span: Span) -> Variable {
533        self.ir.variable(hir_id, span)
534    }
535
536    fn define_bindings_in_pat(&mut self, pat: &hir::Pat<'_>, mut succ: LiveNode) -> LiveNode {
537        // In an or-pattern, only consider the first non-never pattern; any later patterns
538        // must have the same bindings, and we also consider that pattern
539        // to be the "authoritative" set of ids.
540        pat.each_binding_or_first(&mut |_, hir_id, pat_sp, ident| {
541            let ln = self.live_node(hir_id, pat_sp);
542            let var = self.variable(hir_id, ident.span);
543            self.init_from_succ(ln, succ);
544            self.define(ln, var);
545            succ = ln;
546        });
547        succ
548    }
549
550    fn live_on_entry(&self, ln: LiveNode, var: Variable) -> bool {
551        self.rwu_table.get_reader(ln, var)
552    }
553
554    // Is this variable live on entry to any of its successor nodes?
555    fn live_on_exit(&self, ln: LiveNode, var: Variable) -> bool {
556        let successor = self.successors[ln].unwrap();
557        self.live_on_entry(successor, var)
558    }
559
560    fn used_on_entry(&self, ln: LiveNode, var: Variable) -> bool {
561        self.rwu_table.get_used(ln, var)
562    }
563
564    fn assigned_on_entry(&self, ln: LiveNode, var: Variable) -> bool {
565        self.rwu_table.get_writer(ln, var)
566    }
567
568    fn assigned_on_exit(&self, ln: LiveNode, var: Variable) -> bool {
569        match self.successors[ln] {
570            Some(successor) => self.assigned_on_entry(successor, var),
571            None => {
572                self.ir.tcx.dcx().delayed_bug("no successor");
573                true
574            }
575        }
576    }
577
578    fn write_vars<F>(&self, wr: &mut dyn Write, mut test: F) -> io::Result<()>
579    where
580        F: FnMut(Variable) -> bool,
581    {
582        for var in self.ir.var_kinds.indices() {
583            if test(var) {
584                write!(wr, " {var:?}")?;
585            }
586        }
587        Ok(())
588    }
589
590    #[allow(unused_must_use)]
591    fn ln_str(&self, ln: LiveNode) -> String {
592        let mut wr = Vec::new();
593        {
594            let wr = &mut wr as &mut dyn Write;
595            write!(wr, "[{:?} of kind {:?} reads", ln, self.ir.lnks[ln]);
596            self.write_vars(wr, |var| self.rwu_table.get_reader(ln, var));
597            write!(wr, "  writes");
598            self.write_vars(wr, |var| self.rwu_table.get_writer(ln, var));
599            write!(wr, "  uses");
600            self.write_vars(wr, |var| self.rwu_table.get_used(ln, var));
601
602            write!(wr, "  precedes {:?}]", self.successors[ln]);
603        }
604        String::from_utf8(wr).unwrap()
605    }
606
607    fn log_liveness(&self, entry_ln: LiveNode, hir_id: HirId) {
608        // hack to skip the loop unless debug! is enabled:
609        debug!(
610            "^^ liveness computation results for body {} (entry={:?})",
611            {
612                for ln_idx in self.ir.lnks.indices() {
613                    debug!("{:?}", self.ln_str(ln_idx));
614                }
615                hir_id
616            },
617            entry_ln
618        );
619    }
620
621    fn init_empty(&mut self, ln: LiveNode, succ_ln: LiveNode) {
622        self.successors[ln] = Some(succ_ln);
623
624        // It is not necessary to initialize the RWUs here because they are all
625        // empty when created, and the sets only grow during iterations.
626    }
627
628    fn init_from_succ(&mut self, ln: LiveNode, succ_ln: LiveNode) {
629        // more efficient version of init_empty() / merge_from_succ()
630        self.successors[ln] = Some(succ_ln);
631        self.rwu_table.copy(ln, succ_ln);
632        debug!("init_from_succ(ln={}, succ={})", self.ln_str(ln), self.ln_str(succ_ln));
633    }
634
635    fn merge_from_succ(&mut self, ln: LiveNode, succ_ln: LiveNode) -> bool {
636        if ln == succ_ln {
637            return false;
638        }
639
640        let changed = self.rwu_table.union(ln, succ_ln);
641        debug!("merge_from_succ(ln={:?}, succ={}, changed={})", ln, self.ln_str(succ_ln), changed);
642        changed
643    }
644
645    // Indicates that a local variable was *defined*; we know that no
646    // uses of the variable can precede the definition (resolve checks
647    // this) so we just clear out all the data.
648    fn define(&mut self, writer: LiveNode, var: Variable) {
649        let used = self.rwu_table.get_used(writer, var);
650        self.rwu_table.set(writer, var, rwu_table::RWU { reader: false, writer: false, used });
651        debug!("{:?} defines {:?}: {}", writer, var, self.ln_str(writer));
652    }
653
654    // Either read, write, or both depending on the acc bitset
655    fn acc(&mut self, ln: LiveNode, var: Variable, acc: u32) {
656        debug!("{:?} accesses[{:x}] {:?}: {}", ln, acc, var, self.ln_str(ln));
657
658        let mut rwu = self.rwu_table.get(ln, var);
659
660        if (acc & ACC_WRITE) != 0 {
661            rwu.reader = false;
662            rwu.writer = true;
663        }
664
665        // Important: if we both read/write, must do read second
666        // or else the write will override.
667        if (acc & ACC_READ) != 0 {
668            rwu.reader = true;
669        }
670
671        if (acc & ACC_USE) != 0 {
672            rwu.used = true;
673        }
674
675        self.rwu_table.set(ln, var, rwu);
676    }
677
678    fn compute(&mut self, body: &hir::Body<'_>, hir_id: HirId) -> LiveNode {
679        debug!("compute: for body {:?}", body.id().hir_id);
680
681        // # Liveness of captured variables
682        //
683        // When computing the liveness for captured variables we take into
684        // account how variable is captured (ByRef vs ByValue) and what is the
685        // closure kind (Coroutine / FnOnce vs Fn / FnMut).
686        //
687        // Variables captured by reference are assumed to be used on the exit
688        // from the closure.
689        //
690        // In FnOnce closures, variables captured by value are known to be dead
691        // on exit since it is impossible to call the closure again.
692        //
693        // In Fn / FnMut closures, variables captured by value are live on exit
694        // if they are live on the entry to the closure, since only the closure
695        // itself can access them on subsequent calls.
696
697        if let Some(closure_min_captures) = self.closure_min_captures {
698            // Mark upvars captured by reference as used after closure exits.
699            for (&var_hir_id, min_capture_list) in closure_min_captures {
700                for captured_place in min_capture_list {
701                    match captured_place.info.capture_kind {
702                        ty::UpvarCapture::ByRef(_) => {
703                            let var = self.variable(
704                                var_hir_id,
705                                captured_place.get_capture_kind_span(self.ir.tcx),
706                            );
707                            self.acc(self.exit_ln, var, ACC_READ | ACC_USE);
708                        }
709                        ty::UpvarCapture::ByValue | ty::UpvarCapture::ByUse => {}
710                    }
711                }
712            }
713        }
714
715        let succ = self.propagate_through_expr(body.value, self.exit_ln);
716
717        if self.closure_min_captures.is_none() {
718            // Either not a closure, or closure without any captured variables.
719            // No need to determine liveness of captured variables, since there
720            // are none.
721            return succ;
722        }
723
724        let ty = self.typeck_results.node_type(hir_id);
725        match ty.kind() {
726            ty::Closure(_def_id, args) => match args.as_closure().kind() {
727                ty::ClosureKind::Fn => {}
728                ty::ClosureKind::FnMut => {}
729                ty::ClosureKind::FnOnce => return succ,
730            },
731            ty::CoroutineClosure(_def_id, args) => match args.as_coroutine_closure().kind() {
732                ty::ClosureKind::Fn => {}
733                ty::ClosureKind::FnMut => {}
734                ty::ClosureKind::FnOnce => return succ,
735            },
736            ty::Coroutine(..) => return succ,
737            _ => {
738                span_bug!(
739                    body.value.span,
740                    "{} has upvars so it should have a closure type: {:?}",
741                    hir_id,
742                    ty
743                );
744            }
745        };
746
747        // Propagate through calls to the closure.
748        loop {
749            self.init_from_succ(self.closure_ln, succ);
750            for param in body.params {
751                param.pat.each_binding(|_bm, hir_id, _x, ident| {
752                    let var = self.variable(hir_id, ident.span);
753                    self.define(self.closure_ln, var);
754                })
755            }
756
757            if !self.merge_from_succ(self.exit_ln, self.closure_ln) {
758                break;
759            }
760            assert_eq!(succ, self.propagate_through_expr(body.value, self.exit_ln));
761        }
762
763        succ
764    }
765
766    fn propagate_through_block(&mut self, blk: &hir::Block<'_>, succ: LiveNode) -> LiveNode {
767        if blk.targeted_by_break {
768            self.break_ln.insert(blk.hir_id, succ);
769        }
770        let succ = self.propagate_through_opt_expr(blk.expr, succ);
771        blk.stmts.iter().rev().fold(succ, |succ, stmt| self.propagate_through_stmt(stmt, succ))
772    }
773
774    fn propagate_through_stmt(&mut self, stmt: &hir::Stmt<'_>, succ: LiveNode) -> LiveNode {
775        match stmt.kind {
776            hir::StmtKind::Let(local) => {
777                // Note: we mark the variable as defined regardless of whether
778                // there is an initializer. Initially I had thought to only mark
779                // the live variable as defined if it was initialized, and then we
780                // could check for uninit variables just by scanning what is live
781                // at the start of the function. But that doesn't work so well for
782                // immutable variables defined in a loop:
783                //     loop { let x; x = 5; }
784                // because the "assignment" loops back around and generates an error.
785                //
786                // So now we just check that variables defined w/o an
787                // initializer are not live at the point of their
788                // initialization, which is mildly more complex than checking
789                // once at the func header but otherwise equivalent.
790
791                if let Some(els) = local.els {
792                    // Eventually, `let pat: ty = init else { els };` is mostly equivalent to
793                    // `let (bindings, ...) = match init { pat => (bindings, ...), _ => els };`
794                    // except that extended lifetime applies at the `init` location.
795                    //
796                    //       (e)
797                    //        |
798                    //        v
799                    //      (expr)
800                    //      /   \
801                    //     |     |
802                    //     v     v
803                    // bindings  els
804                    //     |
805                    //     v
806                    // ( succ )
807                    //
808                    if let Some(init) = local.init {
809                        let else_ln = self.propagate_through_block(els, succ);
810                        let ln = self.live_node(local.hir_id, local.span);
811                        self.init_from_succ(ln, succ);
812                        self.merge_from_succ(ln, else_ln);
813                        let succ = self.propagate_through_expr(init, ln);
814                        self.define_bindings_in_pat(local.pat, succ)
815                    } else {
816                        span_bug!(
817                            stmt.span,
818                            "variable is uninitialized but an unexpected else branch is found"
819                        )
820                    }
821                } else {
822                    let succ = self.propagate_through_opt_expr(local.init, succ);
823                    self.define_bindings_in_pat(local.pat, succ)
824                }
825            }
826            hir::StmtKind::Item(..) => succ,
827            hir::StmtKind::Expr(ref expr) | hir::StmtKind::Semi(ref expr) => {
828                self.propagate_through_expr(expr, succ)
829            }
830        }
831    }
832
833    fn propagate_through_exprs(&mut self, exprs: &[Expr<'_>], succ: LiveNode) -> LiveNode {
834        exprs.iter().rev().fold(succ, |succ, expr| self.propagate_through_expr(expr, succ))
835    }
836
837    fn propagate_through_opt_expr(
838        &mut self,
839        opt_expr: Option<&Expr<'_>>,
840        succ: LiveNode,
841    ) -> LiveNode {
842        opt_expr.map_or(succ, |expr| self.propagate_through_expr(expr, succ))
843    }
844
845    fn propagate_through_expr(&mut self, expr: &Expr<'_>, succ: LiveNode) -> LiveNode {
846        debug!("propagate_through_expr: {:?}", expr);
847
848        match expr.kind {
849            // Interesting cases with control flow or which gen/kill
850            hir::ExprKind::Path(hir::QPath::Resolved(_, path)) => {
851                self.access_path(expr.hir_id, path, succ, ACC_READ | ACC_USE)
852            }
853
854            hir::ExprKind::Field(ref e, _) => self.propagate_through_expr(e, succ),
855
856            hir::ExprKind::Closure { .. } => {
857                debug!("{:?} is an ExprKind::Closure", expr);
858
859                // the construction of a closure itself is not important,
860                // but we have to consider the closed over variables.
861                let caps = self
862                    .ir
863                    .capture_info_map
864                    .get(&expr.hir_id)
865                    .cloned()
866                    .unwrap_or_else(|| span_bug!(expr.span, "no registered caps"));
867
868                caps.iter().rev().fold(succ, |succ, cap| {
869                    self.init_from_succ(cap.ln, succ);
870                    let var = self.variable(cap.var_hid, expr.span);
871                    self.acc(cap.ln, var, ACC_READ | ACC_USE);
872                    cap.ln
873                })
874            }
875
876            hir::ExprKind::Let(let_expr) => {
877                let succ = self.propagate_through_expr(let_expr.init, succ);
878                self.define_bindings_in_pat(let_expr.pat, succ)
879            }
880
881            // Note that labels have been resolved, so we don't need to look
882            // at the label ident
883            hir::ExprKind::Loop(ref blk, ..) => self.propagate_through_loop(expr, blk, succ),
884
885            hir::ExprKind::Yield(e, ..) => {
886                let yield_ln = self.live_node(expr.hir_id, expr.span);
887                self.init_from_succ(yield_ln, succ);
888                self.merge_from_succ(yield_ln, self.exit_ln);
889                self.propagate_through_expr(e, yield_ln)
890            }
891
892            hir::ExprKind::If(ref cond, ref then, ref else_opt) => {
893                //
894                //     (cond)
895                //       |
896                //       v
897                //     (expr)
898                //     /   \
899                //    |     |
900                //    v     v
901                //  (then)(els)
902                //    |     |
903                //    v     v
904                //   (  succ  )
905                //
906                let else_ln = self.propagate_through_opt_expr(else_opt.as_deref(), succ);
907                let then_ln = self.propagate_through_expr(then, succ);
908                let ln = self.live_node(expr.hir_id, expr.span);
909                self.init_from_succ(ln, else_ln);
910                self.merge_from_succ(ln, then_ln);
911                self.propagate_through_expr(cond, ln)
912            }
913
914            hir::ExprKind::Match(ref e, arms, _) => {
915                //
916                //      (e)
917                //       |
918                //       v
919                //     (expr)
920                //     / | \
921                //    |  |  |
922                //    v  v  v
923                //   (..arms..)
924                //    |  |  |
925                //    v  v  v
926                //   (  succ  )
927                //
928                //
929                let ln = self.live_node(expr.hir_id, expr.span);
930                self.init_empty(ln, succ);
931                for arm in arms {
932                    let body_succ = self.propagate_through_expr(arm.body, succ);
933
934                    let guard_succ = arm
935                        .guard
936                        .as_ref()
937                        .map_or(body_succ, |g| self.propagate_through_expr(g, body_succ));
938                    let arm_succ = self.define_bindings_in_pat(&arm.pat, guard_succ);
939                    self.merge_from_succ(ln, arm_succ);
940                }
941                self.propagate_through_expr(e, ln)
942            }
943
944            hir::ExprKind::Ret(ref o_e) => {
945                // Ignore succ and subst exit_ln.
946                self.propagate_through_opt_expr(o_e.as_deref(), self.exit_ln)
947            }
948
949            hir::ExprKind::Become(e) => {
950                // Ignore succ and subst exit_ln.
951                self.propagate_through_expr(e, self.exit_ln)
952            }
953
954            hir::ExprKind::Break(label, ref opt_expr) => {
955                // Find which label this break jumps to
956                let target = match label.target_id {
957                    Ok(hir_id) => self.break_ln.get(&hir_id),
958                    Err(err) => span_bug!(expr.span, "loop scope error: {}", err),
959                }
960                .cloned();
961
962                // Now that we know the label we're going to,
963                // look it up in the break loop nodes table
964
965                match target {
966                    Some(b) => self.propagate_through_opt_expr(opt_expr.as_deref(), b),
967                    None => span_bug!(expr.span, "`break` to unknown label"),
968                }
969            }
970
971            hir::ExprKind::Continue(label) => {
972                // Find which label this expr continues to
973                let sc = label
974                    .target_id
975                    .unwrap_or_else(|err| span_bug!(expr.span, "loop scope error: {}", err));
976
977                // Now that we know the label we're going to,
978                // look it up in the continue loop nodes table
979                self.cont_ln.get(&sc).cloned().unwrap_or_else(|| {
980                    // Liveness linting happens after building the THIR. Bad labels should already
981                    // have been caught.
982                    span_bug!(expr.span, "continue to unknown label");
983                })
984            }
985
986            hir::ExprKind::Assign(ref l, ref r, _) => {
987                // see comment on places in
988                // propagate_through_place_components()
989                let succ = self.write_place(l, succ, ACC_WRITE);
990                let succ = self.propagate_through_place_components(l, succ);
991                self.propagate_through_expr(r, succ)
992            }
993
994            hir::ExprKind::AssignOp(_, ref l, ref r) => {
995                // an overloaded assign op is like a method call
996                if self.typeck_results.is_method_call(expr) {
997                    let succ = self.propagate_through_expr(l, succ);
998                    self.propagate_through_expr(r, succ)
999                } else {
1000                    // see comment on places in
1001                    // propagate_through_place_components()
1002                    let succ = self.write_place(l, succ, ACC_WRITE | ACC_READ);
1003                    let succ = self.propagate_through_expr(r, succ);
1004                    self.propagate_through_place_components(l, succ)
1005                }
1006            }
1007
1008            // Uninteresting cases: just propagate in rev exec order
1009            hir::ExprKind::Array(exprs) => self.propagate_through_exprs(exprs, succ),
1010
1011            hir::ExprKind::Struct(_, fields, ref with_expr) => {
1012                let succ = match with_expr {
1013                    hir::StructTailExpr::Base(base) => {
1014                        self.propagate_through_opt_expr(Some(base), succ)
1015                    }
1016                    hir::StructTailExpr::None | hir::StructTailExpr::DefaultFields(_) => succ,
1017                };
1018                fields
1019                    .iter()
1020                    .rev()
1021                    .fold(succ, |succ, field| self.propagate_through_expr(field.expr, succ))
1022            }
1023
1024            hir::ExprKind::Call(ref f, args) => {
1025                let is_ctor = |f: &Expr<'_>| matches!(f.kind, hir::ExprKind::Path(hir::QPath::Resolved(_, path)) if matches!(path.res, rustc_hir::def::Res::Def(rustc_hir::def::DefKind::Ctor(_, _), _)));
1026                let succ =
1027                    if !is_ctor(f) { self.check_is_ty_uninhabited(expr, succ) } else { succ };
1028
1029                let succ = self.propagate_through_exprs(args, succ);
1030                self.propagate_through_expr(f, succ)
1031            }
1032
1033            hir::ExprKind::MethodCall(.., receiver, args, _) => {
1034                let succ = self.check_is_ty_uninhabited(expr, succ);
1035                let succ = self.propagate_through_exprs(args, succ);
1036                self.propagate_through_expr(receiver, succ)
1037            }
1038
1039            hir::ExprKind::Use(expr, _) => {
1040                let succ = self.check_is_ty_uninhabited(expr, succ);
1041                self.propagate_through_expr(expr, succ)
1042            }
1043
1044            hir::ExprKind::Tup(exprs) => self.propagate_through_exprs(exprs, succ),
1045
1046            hir::ExprKind::Binary(op, ref l, ref r) if op.node.is_lazy() => {
1047                let r_succ = self.propagate_through_expr(r, succ);
1048
1049                let ln = self.live_node(expr.hir_id, expr.span);
1050                self.init_from_succ(ln, succ);
1051                self.merge_from_succ(ln, r_succ);
1052
1053                self.propagate_through_expr(l, ln)
1054            }
1055
1056            hir::ExprKind::Index(ref l, ref r, _) | hir::ExprKind::Binary(_, ref l, ref r) => {
1057                let r_succ = self.propagate_through_expr(r, succ);
1058                self.propagate_through_expr(l, r_succ)
1059            }
1060
1061            hir::ExprKind::AddrOf(_, _, ref e)
1062            | hir::ExprKind::Cast(ref e, _)
1063            | hir::ExprKind::Type(ref e, _)
1064            | hir::ExprKind::UnsafeBinderCast(_, ref e, _)
1065            | hir::ExprKind::DropTemps(ref e)
1066            | hir::ExprKind::Unary(_, ref e)
1067            | hir::ExprKind::Repeat(ref e, _) => self.propagate_through_expr(e, succ),
1068
1069            hir::ExprKind::InlineAsm(asm) => {
1070                //
1071                //     (inputs)
1072                //        |
1073                //        v
1074                //     (outputs)
1075                //    /         \
1076                //    |         |
1077                //    v         v
1078                // (labels)(fallthrough)
1079                //    |         |
1080                //    v         v
1081                // ( succ / exit_ln )
1082
1083                // Handle non-returning asm
1084                let mut succ =
1085                    if self.typeck_results.expr_ty(expr).is_never() { self.exit_ln } else { succ };
1086
1087                // Do a first pass for labels only
1088                if asm.contains_label() {
1089                    let ln = self.live_node(expr.hir_id, expr.span);
1090                    self.init_from_succ(ln, succ);
1091                    for (op, _op_sp) in asm.operands.iter().rev() {
1092                        match op {
1093                            hir::InlineAsmOperand::Label { block } => {
1094                                let label_ln = self.propagate_through_block(block, succ);
1095                                self.merge_from_succ(ln, label_ln);
1096                            }
1097                            hir::InlineAsmOperand::In { .. }
1098                            | hir::InlineAsmOperand::Out { .. }
1099                            | hir::InlineAsmOperand::InOut { .. }
1100                            | hir::InlineAsmOperand::SplitInOut { .. }
1101                            | hir::InlineAsmOperand::Const { .. }
1102                            | hir::InlineAsmOperand::SymFn { .. }
1103                            | hir::InlineAsmOperand::SymStatic { .. } => {}
1104                        }
1105                    }
1106                    succ = ln;
1107                }
1108
1109                // Do a second pass for writing outputs only
1110                for (op, _op_sp) in asm.operands.iter().rev() {
1111                    match op {
1112                        hir::InlineAsmOperand::In { .. }
1113                        | hir::InlineAsmOperand::Const { .. }
1114                        | hir::InlineAsmOperand::SymFn { .. }
1115                        | hir::InlineAsmOperand::SymStatic { .. }
1116                        | hir::InlineAsmOperand::Label { .. } => {}
1117                        hir::InlineAsmOperand::Out { expr, .. } => {
1118                            if let Some(expr) = expr {
1119                                succ = self.write_place(expr, succ, ACC_WRITE);
1120                            }
1121                        }
1122                        hir::InlineAsmOperand::InOut { expr, .. } => {
1123                            succ = self.write_place(expr, succ, ACC_READ | ACC_WRITE | ACC_USE);
1124                        }
1125                        hir::InlineAsmOperand::SplitInOut { out_expr, .. } => {
1126                            if let Some(expr) = out_expr {
1127                                succ = self.write_place(expr, succ, ACC_WRITE);
1128                            }
1129                        }
1130                    }
1131                }
1132
1133                // Then do a third pass for inputs
1134                for (op, _op_sp) in asm.operands.iter().rev() {
1135                    match op {
1136                        hir::InlineAsmOperand::In { expr, .. } => {
1137                            succ = self.propagate_through_expr(expr, succ)
1138                        }
1139                        hir::InlineAsmOperand::Out { expr, .. } => {
1140                            if let Some(expr) = expr {
1141                                succ = self.propagate_through_place_components(expr, succ);
1142                            }
1143                        }
1144                        hir::InlineAsmOperand::InOut { expr, .. } => {
1145                            succ = self.propagate_through_place_components(expr, succ);
1146                        }
1147                        hir::InlineAsmOperand::SplitInOut { in_expr, out_expr, .. } => {
1148                            if let Some(expr) = out_expr {
1149                                succ = self.propagate_through_place_components(expr, succ);
1150                            }
1151                            succ = self.propagate_through_expr(in_expr, succ);
1152                        }
1153                        hir::InlineAsmOperand::Const { .. }
1154                        | hir::InlineAsmOperand::SymFn { .. }
1155                        | hir::InlineAsmOperand::SymStatic { .. }
1156                        | hir::InlineAsmOperand::Label { .. } => {}
1157                    }
1158                }
1159                succ
1160            }
1161
1162            hir::ExprKind::Lit(..)
1163            | hir::ExprKind::ConstBlock(..)
1164            | hir::ExprKind::Err(_)
1165            | hir::ExprKind::Path(hir::QPath::TypeRelative(..))
1166            | hir::ExprKind::Path(hir::QPath::LangItem(..))
1167            | hir::ExprKind::OffsetOf(..) => succ,
1168
1169            // Note that labels have been resolved, so we don't need to look
1170            // at the label ident
1171            hir::ExprKind::Block(ref blk, _) => self.propagate_through_block(blk, succ),
1172        }
1173    }
1174
1175    fn propagate_through_place_components(&mut self, expr: &Expr<'_>, succ: LiveNode) -> LiveNode {
1176        // # Places
1177        //
1178        // In general, the full flow graph structure for an
1179        // assignment/move/etc can be handled in one of two ways,
1180        // depending on whether what is being assigned is a "tracked
1181        // value" or not. A tracked value is basically a local
1182        // variable or argument.
1183        //
1184        // The two kinds of graphs are:
1185        //
1186        //    Tracked place          Untracked place
1187        // ----------------------++-----------------------
1188        //                       ||
1189        //         |             ||           |
1190        //         v             ||           v
1191        //     (rvalue)          ||       (rvalue)
1192        //         |             ||           |
1193        //         v             ||           v
1194        // (write of place)      ||   (place components)
1195        //         |             ||           |
1196        //         v             ||           v
1197        //      (succ)           ||        (succ)
1198        //                       ||
1199        // ----------------------++-----------------------
1200        //
1201        // I will cover the two cases in turn:
1202        //
1203        // # Tracked places
1204        //
1205        // A tracked place is a local variable/argument `x`. In
1206        // these cases, the link_node where the write occurs is linked
1207        // to node id of `x`. The `write_place()` routine generates
1208        // the contents of this node. There are no subcomponents to
1209        // consider.
1210        //
1211        // # Non-tracked places
1212        //
1213        // These are places like `x[5]` or `x.f`. In that case, we
1214        // basically ignore the value which is written to but generate
1215        // reads for the components---`x` in these two examples. The
1216        // components reads are generated by
1217        // `propagate_through_place_components()` (this fn).
1218        //
1219        // # Illegal places
1220        //
1221        // It is still possible to observe assignments to non-places;
1222        // these errors are detected in the later pass borrowck. We
1223        // just ignore such cases and treat them as reads.
1224
1225        match expr.kind {
1226            hir::ExprKind::Path(_) => succ,
1227            hir::ExprKind::Field(ref e, _) => self.propagate_through_expr(e, succ),
1228            _ => self.propagate_through_expr(expr, succ),
1229        }
1230    }
1231
1232    // see comment on propagate_through_place()
1233    fn write_place(&mut self, expr: &Expr<'_>, succ: LiveNode, acc: u32) -> LiveNode {
1234        match expr.kind {
1235            hir::ExprKind::Path(hir::QPath::Resolved(_, path)) => {
1236                self.access_path(expr.hir_id, path, succ, acc)
1237            }
1238
1239            // We do not track other places, so just propagate through
1240            // to their subcomponents. Also, it may happen that
1241            // non-places occur here, because those are detected in the
1242            // later pass borrowck.
1243            _ => succ,
1244        }
1245    }
1246
1247    fn access_var(
1248        &mut self,
1249        hir_id: HirId,
1250        var_hid: HirId,
1251        succ: LiveNode,
1252        acc: u32,
1253        span: Span,
1254    ) -> LiveNode {
1255        let ln = self.live_node(hir_id, span);
1256        if acc != 0 {
1257            self.init_from_succ(ln, succ);
1258            let var = self.variable(var_hid, span);
1259            self.acc(ln, var, acc);
1260        }
1261        ln
1262    }
1263
1264    fn access_path(
1265        &mut self,
1266        hir_id: HirId,
1267        path: &hir::Path<'_>,
1268        succ: LiveNode,
1269        acc: u32,
1270    ) -> LiveNode {
1271        match path.res {
1272            Res::Local(hid) => self.access_var(hir_id, hid, succ, acc, path.span),
1273            _ => succ,
1274        }
1275    }
1276
1277    fn propagate_through_loop(
1278        &mut self,
1279        expr: &Expr<'_>,
1280        body: &hir::Block<'_>,
1281        succ: LiveNode,
1282    ) -> LiveNode {
1283        /*
1284        We model control flow like this:
1285
1286              (expr) <-+
1287                |      |
1288                v      |
1289              (body) --+
1290
1291        Note that a `continue` expression targeting the `loop` will have a successor of `expr`.
1292        Meanwhile, a `break` expression will have a successor of `succ`.
1293        */
1294
1295        // first iteration:
1296        let ln = self.live_node(expr.hir_id, expr.span);
1297        self.init_empty(ln, succ);
1298        debug!("propagate_through_loop: using id for loop body {} {:?}", expr.hir_id, body);
1299
1300        self.break_ln.insert(expr.hir_id, succ);
1301
1302        self.cont_ln.insert(expr.hir_id, ln);
1303
1304        let body_ln = self.propagate_through_block(body, ln);
1305
1306        // repeat until fixed point is reached:
1307        while self.merge_from_succ(ln, body_ln) {
1308            assert_eq!(body_ln, self.propagate_through_block(body, ln));
1309        }
1310
1311        ln
1312    }
1313
1314    fn check_is_ty_uninhabited(&mut self, expr: &Expr<'_>, succ: LiveNode) -> LiveNode {
1315        let ty = self.typeck_results.expr_ty(expr);
1316        let m = self.ir.tcx.parent_module(expr.hir_id).to_def_id();
1317        if ty.is_inhabited_from(self.ir.tcx, m, self.typing_env) {
1318            return succ;
1319        }
1320        match self.ir.lnks[succ] {
1321            LiveNodeKind::ExprNode(succ_span, succ_id) => {
1322                self.warn_about_unreachable(expr.span, ty, succ_span, succ_id, "expression");
1323            }
1324            LiveNodeKind::VarDefNode(succ_span, succ_id) => {
1325                self.warn_about_unreachable(expr.span, ty, succ_span, succ_id, "definition");
1326            }
1327            _ => {}
1328        };
1329        self.exit_ln
1330    }
1331
1332    fn warn_about_unreachable<'desc>(
1333        &mut self,
1334        orig_span: Span,
1335        orig_ty: Ty<'tcx>,
1336        expr_span: Span,
1337        expr_id: HirId,
1338        descr: &'desc str,
1339    ) {
1340        if !orig_ty.is_never() {
1341            // Unreachable code warnings are already emitted during type checking.
1342            // However, during type checking, full type information is being
1343            // calculated but not yet available, so the check for diverging
1344            // expressions due to uninhabited result types is pretty crude and
1345            // only checks whether ty.is_never(). Here, we have full type
1346            // information available and can issue warnings for less obviously
1347            // uninhabited types (e.g. empty enums). The check above is used so
1348            // that we do not emit the same warning twice if the uninhabited type
1349            // is indeed `!`.
1350
1351            self.ir.tcx.emit_node_span_lint(
1352                lint::builtin::UNREACHABLE_CODE,
1353                expr_id,
1354                expr_span,
1355                errors::UnreachableDueToUninhabited {
1356                    expr: expr_span,
1357                    orig: orig_span,
1358                    descr,
1359                    ty: orig_ty,
1360                },
1361            );
1362        }
1363    }
1364}
1365
1366// _______________________________________________________________________
1367// Checking for error conditions
1368
1369impl<'a, 'tcx> Visitor<'tcx> for Liveness<'a, 'tcx> {
1370    fn visit_local(&mut self, local: &'tcx hir::LetStmt<'tcx>) {
1371        self.check_unused_vars_in_pat(local.pat, None, None, |spans, hir_id, ln, var| {
1372            if local.init.is_some() {
1373                self.warn_about_dead_assign(spans, hir_id, ln, var, None);
1374            }
1375        });
1376
1377        intravisit::walk_local(self, local);
1378    }
1379
1380    fn visit_expr(&mut self, ex: &'tcx Expr<'tcx>) {
1381        check_expr(self, ex);
1382        intravisit::walk_expr(self, ex);
1383    }
1384
1385    fn visit_arm(&mut self, arm: &'tcx hir::Arm<'tcx>) {
1386        self.check_unused_vars_in_pat(arm.pat, None, None, |_, _, _, _| {});
1387        intravisit::walk_arm(self, arm);
1388    }
1389}
1390
1391fn check_expr<'tcx>(this: &mut Liveness<'_, 'tcx>, expr: &'tcx Expr<'tcx>) {
1392    match expr.kind {
1393        hir::ExprKind::Assign(ref l, ..) => {
1394            this.check_place(l);
1395        }
1396
1397        hir::ExprKind::AssignOp(_, ref l, _) => {
1398            if !this.typeck_results.is_method_call(expr) {
1399                this.check_place(l);
1400            }
1401        }
1402
1403        hir::ExprKind::InlineAsm(asm) => {
1404            for (op, _op_sp) in asm.operands {
1405                match op {
1406                    hir::InlineAsmOperand::Out { expr, .. } => {
1407                        if let Some(expr) = expr {
1408                            this.check_place(expr);
1409                        }
1410                    }
1411                    hir::InlineAsmOperand::InOut { expr, .. } => {
1412                        this.check_place(expr);
1413                    }
1414                    hir::InlineAsmOperand::SplitInOut { out_expr, .. } => {
1415                        if let Some(out_expr) = out_expr {
1416                            this.check_place(out_expr);
1417                        }
1418                    }
1419                    _ => {}
1420                }
1421            }
1422        }
1423
1424        hir::ExprKind::Let(let_expr) => {
1425            this.check_unused_vars_in_pat(let_expr.pat, None, None, |_, _, _, _| {});
1426        }
1427
1428        // no correctness conditions related to liveness
1429        hir::ExprKind::Call(..)
1430        | hir::ExprKind::MethodCall(..)
1431        | hir::ExprKind::Use(..)
1432        | hir::ExprKind::Match(..)
1433        | hir::ExprKind::Loop(..)
1434        | hir::ExprKind::Index(..)
1435        | hir::ExprKind::Field(..)
1436        | hir::ExprKind::Array(..)
1437        | hir::ExprKind::Tup(..)
1438        | hir::ExprKind::Binary(..)
1439        | hir::ExprKind::Cast(..)
1440        | hir::ExprKind::If(..)
1441        | hir::ExprKind::DropTemps(..)
1442        | hir::ExprKind::Unary(..)
1443        | hir::ExprKind::Ret(..)
1444        | hir::ExprKind::Become(..)
1445        | hir::ExprKind::Break(..)
1446        | hir::ExprKind::Continue(..)
1447        | hir::ExprKind::Lit(_)
1448        | hir::ExprKind::ConstBlock(..)
1449        | hir::ExprKind::Block(..)
1450        | hir::ExprKind::AddrOf(..)
1451        | hir::ExprKind::OffsetOf(..)
1452        | hir::ExprKind::Struct(..)
1453        | hir::ExprKind::Repeat(..)
1454        | hir::ExprKind::Closure { .. }
1455        | hir::ExprKind::Path(_)
1456        | hir::ExprKind::Yield(..)
1457        | hir::ExprKind::Type(..)
1458        | hir::ExprKind::UnsafeBinderCast(..)
1459        | hir::ExprKind::Err(_) => {}
1460    }
1461}
1462
1463impl<'tcx> Liveness<'_, 'tcx> {
1464    fn check_place(&mut self, expr: &'tcx Expr<'tcx>) {
1465        match expr.kind {
1466            hir::ExprKind::Path(hir::QPath::Resolved(_, path)) => {
1467                if let Res::Local(var_hid) = path.res {
1468                    // Assignment to an immutable variable or argument: only legal
1469                    // if there is no later assignment. If this local is actually
1470                    // mutable, then check for a reassignment to flag the mutability
1471                    // as being used.
1472                    let ln = self.live_node(expr.hir_id, expr.span);
1473                    let var = self.variable(var_hid, expr.span);
1474                    let sugg = self.annotate_mut_binding_to_immutable_binding(var_hid, expr);
1475                    self.warn_about_dead_assign(vec![expr.span], expr.hir_id, ln, var, sugg);
1476                }
1477            }
1478            _ => {
1479                // For other kinds of places, no checks are required,
1480                // and any embedded expressions are actually rvalues
1481                intravisit::walk_expr(self, expr);
1482            }
1483        }
1484    }
1485
1486    fn should_warn(&self, var: Variable) -> Option<String> {
1487        let name = self.ir.variable_name(var);
1488        let name = name.as_str();
1489        if name.as_bytes()[0] == b'_' {
1490            return None;
1491        }
1492        Some(name.to_owned())
1493    }
1494
1495    fn warn_about_unused_upvars(&self, entry_ln: LiveNode) {
1496        let Some(closure_min_captures) = self.closure_min_captures else {
1497            return;
1498        };
1499
1500        // If closure_min_captures is Some(), upvars must be Some() too.
1501        for (&var_hir_id, min_capture_list) in closure_min_captures {
1502            for captured_place in min_capture_list {
1503                match captured_place.info.capture_kind {
1504                    ty::UpvarCapture::ByValue | ty::UpvarCapture::ByUse => {}
1505                    ty::UpvarCapture::ByRef(..) => continue,
1506                };
1507                let span = captured_place.get_capture_kind_span(self.ir.tcx);
1508                let var = self.variable(var_hir_id, span);
1509                if self.used_on_entry(entry_ln, var) {
1510                    if !self.live_on_entry(entry_ln, var) {
1511                        if let Some(name) = self.should_warn(var) {
1512                            self.ir.tcx.emit_node_span_lint(
1513                                lint::builtin::UNUSED_ASSIGNMENTS,
1514                                var_hir_id,
1515                                vec![span],
1516                                errors::UnusedCaptureMaybeCaptureRef { name },
1517                            );
1518                        }
1519                    }
1520                } else if let Some(name) = self.should_warn(var) {
1521                    self.ir.tcx.emit_node_span_lint(
1522                        lint::builtin::UNUSED_VARIABLES,
1523                        var_hir_id,
1524                        vec![span],
1525                        errors::UnusedVarMaybeCaptureRef { name },
1526                    );
1527                }
1528            }
1529        }
1530    }
1531
1532    fn warn_about_unused_args(&self, body: &hir::Body<'_>, entry_ln: LiveNode) {
1533        if let Some(intrinsic) = self.ir.tcx.intrinsic(self.ir.tcx.hir_body_owner_def_id(body.id()))
1534        {
1535            if intrinsic.must_be_overridden {
1536                return;
1537            }
1538        }
1539
1540        for p in body.params {
1541            self.check_unused_vars_in_pat(
1542                p.pat,
1543                Some(entry_ln),
1544                Some(body),
1545                |spans, hir_id, ln, var| {
1546                    if !self.live_on_entry(ln, var)
1547                        && let Some(name) = self.should_warn(var)
1548                    {
1549                        self.ir.tcx.emit_node_span_lint(
1550                            lint::builtin::UNUSED_ASSIGNMENTS,
1551                            hir_id,
1552                            spans,
1553                            errors::UnusedAssignPassed { name },
1554                        );
1555                    }
1556                },
1557            );
1558        }
1559    }
1560
1561    fn check_unused_vars_in_pat(
1562        &self,
1563        pat: &hir::Pat<'_>,
1564        entry_ln: Option<LiveNode>,
1565        opt_body: Option<&hir::Body<'_>>,
1566        on_used_on_entry: impl Fn(Vec<Span>, HirId, LiveNode, Variable),
1567    ) {
1568        // In an or-pattern, only consider the variable; any later patterns must have the same
1569        // bindings, and we also consider the first pattern to be the "authoritative" set of ids.
1570        // However, we should take the ids and spans of variables with the same name from the later
1571        // patterns so the suggestions to prefix with underscores will apply to those too.
1572        let mut vars: FxIndexMap<Symbol, (LiveNode, Variable, Vec<(HirId, Span, Span)>)> =
1573            <_>::default();
1574
1575        pat.each_binding(|_, hir_id, pat_sp, ident| {
1576            let ln = entry_ln.unwrap_or_else(|| self.live_node(hir_id, pat_sp));
1577            let var = self.variable(hir_id, ident.span);
1578            let id_and_sp = (hir_id, pat_sp, ident.span);
1579            vars.entry(self.ir.variable_name(var))
1580                .and_modify(|(.., hir_ids_and_spans)| hir_ids_and_spans.push(id_and_sp))
1581                .or_insert_with(|| (ln, var, vec![id_and_sp]));
1582        });
1583
1584        let can_remove = match pat.kind {
1585            hir::PatKind::Struct(_, fields, true) => {
1586                // if all fields are shorthand, remove the struct field, otherwise, mark with _ as prefix
1587                fields.iter().all(|f| f.is_shorthand)
1588            }
1589            _ => false,
1590        };
1591
1592        for (_, (ln, var, hir_ids_and_spans)) in vars {
1593            if self.used_on_entry(ln, var) {
1594                let id = hir_ids_and_spans[0].0;
1595                let spans =
1596                    hir_ids_and_spans.into_iter().map(|(_, _, ident_span)| ident_span).collect();
1597                on_used_on_entry(spans, id, ln, var);
1598            } else {
1599                self.report_unused(hir_ids_and_spans, ln, var, can_remove, pat, opt_body);
1600            }
1601        }
1602    }
1603
1604    /// Detect the following case
1605    ///
1606    /// ```text
1607    /// fn change_object(mut a: &Ty) {
1608    ///     let a = Ty::new();
1609    ///     b = &a;
1610    /// }
1611    /// ```
1612    ///
1613    /// where the user likely meant to modify the value behind there reference, use `a` as an out
1614    /// parameter, instead of mutating the local binding. When encountering this we suggest:
1615    ///
1616    /// ```text
1617    /// fn change_object(a: &'_ mut Ty) {
1618    ///     let a = Ty::new();
1619    ///     *b = a;
1620    /// }
1621    /// ```
1622    fn annotate_mut_binding_to_immutable_binding(
1623        &self,
1624        var_hid: HirId,
1625        expr: &'tcx Expr<'tcx>,
1626    ) -> Option<errors::UnusedAssignSuggestion> {
1627        if let hir::Node::Expr(parent) = self.ir.tcx.parent_hir_node(expr.hir_id)
1628            && let hir::ExprKind::Assign(_, rhs, _) = parent.kind
1629            && let hir::ExprKind::AddrOf(borrow_kind, _mut, inner) = rhs.kind
1630            && let hir::BorrowKind::Ref = borrow_kind
1631            && let hir::Node::Pat(pat) = self.ir.tcx.hir_node(var_hid)
1632            && let hir::Node::Param(hir::Param { ty_span, .. }) =
1633                self.ir.tcx.parent_hir_node(pat.hir_id)
1634            && let item_id = self.ir.tcx.hir_get_parent_item(pat.hir_id)
1635            && let item = self.ir.tcx.hir_owner_node(item_id)
1636            && let Some(fn_decl) = item.fn_decl()
1637            && let hir::PatKind::Binding(hir::BindingMode::MUT, _hir_id, ident, _) = pat.kind
1638            && let Some((lt, mut_ty)) = fn_decl
1639                .inputs
1640                .iter()
1641                .filter_map(|ty| {
1642                    if ty.span == *ty_span
1643                        && let hir::TyKind::Ref(lt, mut_ty) = ty.kind
1644                    {
1645                        Some((lt, mut_ty))
1646                    } else {
1647                        None
1648                    }
1649                })
1650                .next()
1651        {
1652            let ty_span = if mut_ty.mutbl.is_mut() {
1653                // Leave `&'name mut Ty` and `&mut Ty` as they are (#136028).
1654                None
1655            } else {
1656                // `&'name Ty` -> `&'name mut Ty` or `&Ty` -> `&mut Ty`
1657                Some(mut_ty.ty.span.shrink_to_lo())
1658            };
1659            let pre = if lt.ident.span.is_empty() { "" } else { " " };
1660            Some(errors::UnusedAssignSuggestion {
1661                ty_span,
1662                pre,
1663                ty_ref_span: pat.span.until(ident.span),
1664                ident_span: expr.span.shrink_to_lo(),
1665                expr_ref_span: rhs.span.until(inner.span),
1666            })
1667        } else {
1668            None
1669        }
1670    }
1671
1672    #[instrument(skip(self), level = "INFO")]
1673    fn report_unused(
1674        &self,
1675        hir_ids_and_spans: Vec<(HirId, Span, Span)>,
1676        ln: LiveNode,
1677        var: Variable,
1678        can_remove: bool,
1679        pat: &hir::Pat<'_>,
1680        opt_body: Option<&hir::Body<'_>>,
1681    ) {
1682        let first_hir_id = hir_ids_and_spans[0].0;
1683        if let Some(name) = self.should_warn(var).filter(|name| name != "self") {
1684            // annoying: for parameters in funcs like `fn(x: i32)
1685            // {ret}`, there is only one node, so asking about
1686            // assigned_on_exit() is not meaningful.
1687            let is_assigned =
1688                if ln == self.exit_ln { false } else { self.assigned_on_exit(ln, var) };
1689
1690            if is_assigned {
1691                self.ir.tcx.emit_node_span_lint(
1692                    lint::builtin::UNUSED_VARIABLES,
1693                    first_hir_id,
1694                    hir_ids_and_spans
1695                        .into_iter()
1696                        .map(|(_, _, ident_span)| ident_span)
1697                        .collect::<Vec<_>>(),
1698                    errors::UnusedVarAssignedOnly { name },
1699                )
1700            } else if can_remove {
1701                let spans = hir_ids_and_spans
1702                    .iter()
1703                    .map(|(_, pat_span, _)| {
1704                        let span = self
1705                            .ir
1706                            .tcx
1707                            .sess
1708                            .source_map()
1709                            .span_extend_to_next_char(*pat_span, ',', true);
1710                        span.with_hi(BytePos(span.hi().0 + 1))
1711                    })
1712                    .collect();
1713                self.ir.tcx.emit_node_span_lint(
1714                    lint::builtin::UNUSED_VARIABLES,
1715                    first_hir_id,
1716                    hir_ids_and_spans.iter().map(|(_, pat_span, _)| *pat_span).collect::<Vec<_>>(),
1717                    errors::UnusedVarRemoveField {
1718                        name,
1719                        sugg: errors::UnusedVarRemoveFieldSugg { spans },
1720                    },
1721                );
1722            } else {
1723                let (shorthands, non_shorthands): (Vec<_>, Vec<_>) =
1724                    hir_ids_and_spans.iter().copied().partition(|(hir_id, _, ident_span)| {
1725                        let var = self.variable(*hir_id, *ident_span);
1726                        self.ir.variable_is_shorthand(var)
1727                    });
1728
1729                // If we have both shorthand and non-shorthand, prefer the "try ignoring
1730                // the field" message, and suggest `_` for the non-shorthands. If we only
1731                // have non-shorthand, then prefix with an underscore instead.
1732                if !shorthands.is_empty() {
1733                    let shorthands =
1734                        shorthands.into_iter().map(|(_, pat_span, _)| pat_span).collect();
1735                    let non_shorthands =
1736                        non_shorthands.into_iter().map(|(_, pat_span, _)| pat_span).collect();
1737
1738                    self.ir.tcx.emit_node_span_lint(
1739                        lint::builtin::UNUSED_VARIABLES,
1740                        first_hir_id,
1741                        hir_ids_and_spans
1742                            .iter()
1743                            .map(|(_, pat_span, _)| *pat_span)
1744                            .collect::<Vec<_>>(),
1745                        errors::UnusedVarTryIgnore {
1746                            sugg: errors::UnusedVarTryIgnoreSugg {
1747                                shorthands,
1748                                non_shorthands,
1749                                name,
1750                            },
1751                        },
1752                    );
1753                } else {
1754                    // #117284, when `pat_span` and `ident_span` have different contexts
1755                    // we can't provide a good suggestion, instead we pointed out the spans from macro
1756                    let from_macro = non_shorthands
1757                        .iter()
1758                        .find(|(_, pat_span, ident_span)| {
1759                            !pat_span.eq_ctxt(*ident_span) && pat_span.from_expansion()
1760                        })
1761                        .map(|(_, pat_span, _)| *pat_span);
1762                    let non_shorthands = non_shorthands
1763                        .into_iter()
1764                        .map(|(_, _, ident_span)| ident_span)
1765                        .collect::<Vec<_>>();
1766
1767                    let suggestions = self.string_interp_suggestions(&name, opt_body);
1768                    let sugg = if let Some(span) = from_macro {
1769                        errors::UnusedVariableSugg::NoSugg { span, name: name.clone() }
1770                    } else {
1771                        errors::UnusedVariableSugg::TryPrefixSugg {
1772                            spans: non_shorthands,
1773                            name: name.clone(),
1774                        }
1775                    };
1776
1777                    self.ir.tcx.emit_node_span_lint(
1778                        lint::builtin::UNUSED_VARIABLES,
1779                        first_hir_id,
1780                        hir_ids_and_spans
1781                            .iter()
1782                            .map(|(_, _, ident_span)| *ident_span)
1783                            .collect::<Vec<_>>(),
1784                        errors::UnusedVariableTryPrefix {
1785                            label: if !suggestions.is_empty() { Some(pat.span) } else { None },
1786                            name,
1787                            sugg,
1788                            string_interp: suggestions,
1789                        },
1790                    );
1791                }
1792            }
1793        }
1794    }
1795
1796    fn string_interp_suggestions(
1797        &self,
1798        name: &str,
1799        opt_body: Option<&hir::Body<'_>>,
1800    ) -> Vec<errors::UnusedVariableStringInterp> {
1801        let mut suggs = Vec::new();
1802        let Some(opt_body) = opt_body else {
1803            return suggs;
1804        };
1805        let mut visitor = CollectLitsVisitor { lit_exprs: vec![] };
1806        intravisit::walk_body(&mut visitor, opt_body);
1807        for lit_expr in visitor.lit_exprs {
1808            let hir::ExprKind::Lit(litx) = &lit_expr.kind else { continue };
1809            let rustc_ast::LitKind::Str(syb, _) = litx.node else {
1810                continue;
1811            };
1812            let name_str: &str = syb.as_str();
1813            let name_pa = format!("{{{name}}}");
1814            if name_str.contains(&name_pa) {
1815                suggs.push(errors::UnusedVariableStringInterp {
1816                    lit: lit_expr.span,
1817                    lo: lit_expr.span.shrink_to_lo(),
1818                    hi: lit_expr.span.shrink_to_hi(),
1819                });
1820            }
1821        }
1822        suggs
1823    }
1824
1825    fn warn_about_dead_assign(
1826        &self,
1827        spans: Vec<Span>,
1828        hir_id: HirId,
1829        ln: LiveNode,
1830        var: Variable,
1831        suggestion: Option<errors::UnusedAssignSuggestion>,
1832    ) {
1833        if !self.live_on_exit(ln, var)
1834            && let Some(name) = self.should_warn(var)
1835        {
1836            let help = suggestion.is_none();
1837            self.ir.tcx.emit_node_span_lint(
1838                lint::builtin::UNUSED_ASSIGNMENTS,
1839                hir_id,
1840                spans,
1841                errors::UnusedAssign { name, suggestion, help },
1842            );
1843        }
1844    }
1845}