From 91a096a9b8c05011c1a76e7ceb578000ce1e91f6 Mon Sep 17 00:00:00 2001 From: Mark Rousskov Date: Fri, 4 Oct 2019 10:31:28 -0400 Subject: move middle::liveness to rustc_passes --- src/librustc/lib.rs | 1 - src/librustc/middle/liveness.rs | 1568 -------------------------------------- src/librustc_interface/passes.rs | 1 - src/librustc_passes/lib.rs | 2 + src/librustc_passes/liveness.rs | 1568 ++++++++++++++++++++++++++++++++++++++ 5 files changed, 1570 insertions(+), 1570 deletions(-) delete mode 100644 src/librustc/middle/liveness.rs create mode 100644 src/librustc_passes/liveness.rs diff --git a/src/librustc/lib.rs b/src/librustc/lib.rs index bd9899b644b..b522de7d43d 100644 --- a/src/librustc/lib.rs +++ b/src/librustc/lib.rs @@ -111,7 +111,6 @@ pub mod middle { pub mod intrinsicck; pub mod lib_features; pub mod lang_items; - pub mod liveness; pub mod mem_categorization; pub mod privacy; pub mod reachable; diff --git a/src/librustc/middle/liveness.rs b/src/librustc/middle/liveness.rs deleted file mode 100644 index a654a26eb0b..00000000000 --- a/src/librustc/middle/liveness.rs +++ /dev/null @@ -1,1568 +0,0 @@ -//! A classic liveness analysis based on dataflow over the AST. Computes, -//! for each local variable in a function, whether that variable is live -//! at a given point. Program execution points are identified by their -//! IDs. -//! -//! # Basic idea -//! -//! The basic model is that each local variable is assigned an index. We -//! represent sets of local variables using a vector indexed by this -//! index. The value in the vector is either 0, indicating the variable -//! is dead, or the ID of an expression that uses the variable. -//! -//! We conceptually walk over the AST in reverse execution order. If we -//! find a use of a variable, we add it to the set of live variables. If -//! we find an assignment to a variable, we remove it from the set of live -//! variables. When we have to merge two flows, we take the union of -//! those two flows -- if the variable is live on both paths, we simply -//! pick one ID. In the event of loops, we continue doing this until a -//! fixed point is reached. -//! -//! ## Checking initialization -//! -//! At the function entry point, all variables must be dead. If this is -//! not the case, we can report an error using the ID found in the set of -//! live variables, which identifies a use of the variable which is not -//! dominated by an assignment. -//! -//! ## Checking moves -//! -//! After each explicit move, the variable must be dead. -//! -//! ## Computing last uses -//! -//! Any use of the variable where the variable is dead afterwards is a -//! last use. -//! -//! # Implementation details -//! -//! The actual implementation contains two (nested) walks over the AST. -//! The outer walk has the job of building up the ir_maps instance for the -//! enclosing function. On the way down the tree, it identifies those AST -//! nodes and variable IDs that will be needed for the liveness analysis -//! and assigns them contiguous IDs. The liveness ID for an AST node is -//! called a `live_node` (it's a newtype'd `u32`) and the ID for a variable -//! is called a `variable` (another newtype'd `u32`). -//! -//! On the way back up the tree, as we are about to exit from a function -//! declaration we allocate a `liveness` instance. Now that we know -//! precisely how many nodes and variables we need, we can allocate all -//! the various arrays that we will need to precisely the right size. We then -//! perform the actual propagation on the `liveness` instance. -//! -//! This propagation is encoded in the various `propagate_through_*()` -//! methods. It effectively does a reverse walk of the AST; whenever we -//! reach a loop node, we iterate until a fixed point is reached. -//! -//! ## The `RWU` struct -//! -//! At each live node `N`, we track three pieces of information for each -//! variable `V` (these are encapsulated in the `RWU` struct): -//! -//! - `reader`: the `LiveNode` ID of some node which will read the value -//! that `V` holds on entry to `N`. Formally: a node `M` such -//! that there exists a path `P` from `N` to `M` where `P` does not -//! write `V`. If the `reader` is `invalid_node()`, then the current -//! value will never be read (the variable is dead, essentially). -//! -//! - `writer`: the `LiveNode` ID of some node which will write the -//! variable `V` and which is reachable from `N`. Formally: a node `M` -//! such that there exists a path `P` from `N` to `M` and `M` writes -//! `V`. If the `writer` is `invalid_node()`, then there is no writer -//! of `V` that follows `N`. -//! -//! - `used`: a boolean value indicating whether `V` is *used*. We -//! distinguish a *read* from a *use* in that a *use* is some read that -//! is not just used to generate a new value. For example, `x += 1` is -//! a read but not a use. This is used to generate better warnings. -//! -//! ## Special Variables -//! -//! We generate various special variables for various, well, special purposes. -//! These are described in the `specials` struct: -//! -//! - `exit_ln`: a live node that is generated to represent every 'exit' from -//! the function, whether it be by explicit return, panic, or other means. -//! -//! - `fallthrough_ln`: a live node that represents a fallthrough -//! -//! - `clean_exit_var`: a synthetic variable that is only 'read' from the -//! fallthrough node. It is only live if the function could converge -//! via means other than an explicit `return` expression. That is, it is -//! only dead if the end of the function's block can never be reached. -//! It is the responsibility of typeck to ensure that there are no -//! `return` expressions in a function declared as diverging. - -use self::LiveNodeKind::*; -use self::VarKind::*; - -use crate::hir; -use crate::hir::{Expr, HirId}; -use crate::hir::def::*; -use crate::hir::def_id::DefId; -use crate::hir::intravisit::{self, Visitor, FnKind, NestedVisitorMap}; -use crate::hir::Node; -use crate::hir::ptr::P; -use crate::ty::{self, TyCtxt}; -use crate::ty::query::Providers; -use crate::lint; -use crate::util::nodemap::{HirIdMap, HirIdSet}; - -use errors::Applicability; -use rustc_data_structures::fx::FxIndexMap; -use std::collections::VecDeque; -use std::{fmt, u32}; -use std::io::prelude::*; -use std::io; -use std::rc::Rc; -use syntax::ast; -use syntax::symbol::sym; -use syntax_pos::Span; - -#[derive(Copy, Clone, PartialEq)] -struct Variable(u32); - -#[derive(Copy, Clone, PartialEq)] -struct LiveNode(u32); - -impl Variable { - fn get(&self) -> usize { self.0 as usize } -} - -impl LiveNode { - fn get(&self) -> usize { self.0 as usize } -} - -#[derive(Copy, Clone, PartialEq, Debug)] -enum LiveNodeKind { - UpvarNode(Span), - ExprNode(Span), - VarDefNode(Span), - ExitNode -} - -fn live_node_kind_to_string(lnk: LiveNodeKind, tcx: TyCtxt<'_>) -> String { - let cm = tcx.sess.source_map(); - match lnk { - UpvarNode(s) => { - format!("Upvar node [{}]", cm.span_to_string(s)) - } - ExprNode(s) => { - format!("Expr node [{}]", cm.span_to_string(s)) - } - VarDefNode(s) => { - format!("Var def node [{}]", cm.span_to_string(s)) - } - ExitNode => "Exit node".to_owned(), - } -} - -impl<'tcx> Visitor<'tcx> for IrMaps<'tcx> { - fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> { - NestedVisitorMap::OnlyBodies(&self.tcx.hir()) - } - - fn visit_fn(&mut self, fk: FnKind<'tcx>, fd: &'tcx hir::FnDecl, - b: hir::BodyId, s: Span, id: HirId) { - visit_fn(self, fk, fd, b, s, id); - } - - fn visit_local(&mut self, l: &'tcx hir::Local) { visit_local(self, l); } - fn visit_expr(&mut self, ex: &'tcx Expr) { visit_expr(self, ex); } - fn visit_arm(&mut self, a: &'tcx hir::Arm) { visit_arm(self, a); } -} - -fn check_mod_liveness(tcx: TyCtxt<'_>, module_def_id: DefId) { - tcx.hir().visit_item_likes_in_module( - module_def_id, - &mut IrMaps::new(tcx, module_def_id).as_deep_visitor(), - ); -} - -pub fn provide(providers: &mut Providers<'_>) { - *providers = Providers { - check_mod_liveness, - ..*providers - }; -} - -impl fmt::Debug for LiveNode { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - write!(f, "ln({})", self.get()) - } -} - -impl fmt::Debug for Variable { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - write!(f, "v({})", self.get()) - } -} - -// ______________________________________________________________________ -// Creating ir_maps -// -// This is the first pass and the one that drives the main -// computation. It walks up and down the IR once. On the way down, -// we count for each function the number of variables as well as -// liveness nodes. A liveness node is basically an expression or -// capture clause that does something of interest: either it has -// interesting control flow or it uses/defines a local variable. -// -// On the way back up, at each function node we create liveness sets -// (we now know precisely how big to make our various vectors and so -// forth) and then do the data-flow propagation to compute the set -// of live variables at each program point. -// -// Finally, we run back over the IR one last time and, using the -// computed liveness, check various safety conditions. For example, -// there must be no live nodes at the definition site for a variable -// unless it has an initializer. Similarly, each non-mutable local -// variable must not be assigned if there is some successor -// assignment. And so forth. - -impl LiveNode { - fn is_valid(&self) -> bool { - self.0 != u32::MAX - } -} - -fn invalid_node() -> LiveNode { LiveNode(u32::MAX) } - -struct CaptureInfo { - ln: LiveNode, - var_hid: HirId -} - -#[derive(Copy, Clone, Debug)] -struct LocalInfo { - id: HirId, - name: ast::Name, - is_shorthand: bool, -} - -#[derive(Copy, Clone, Debug)] -enum VarKind { - Param(HirId, ast::Name), - Local(LocalInfo), - CleanExit -} - -struct IrMaps<'tcx> { - tcx: TyCtxt<'tcx>, - body_owner: DefId, - num_live_nodes: usize, - num_vars: usize, - live_node_map: HirIdMap, - variable_map: HirIdMap, - capture_info_map: HirIdMap>>, - var_kinds: Vec, - lnks: Vec, -} - -impl IrMaps<'tcx> { - fn new(tcx: TyCtxt<'tcx>, body_owner: DefId) -> IrMaps<'tcx> { - IrMaps { - tcx, - body_owner, - num_live_nodes: 0, - num_vars: 0, - live_node_map: HirIdMap::default(), - variable_map: HirIdMap::default(), - capture_info_map: Default::default(), - var_kinds: Vec::new(), - lnks: Vec::new(), - } - } - - fn add_live_node(&mut self, lnk: LiveNodeKind) -> LiveNode { - let ln = LiveNode(self.num_live_nodes as u32); - self.lnks.push(lnk); - self.num_live_nodes += 1; - - debug!("{:?} is of kind {}", ln, - live_node_kind_to_string(lnk, self.tcx)); - - ln - } - - fn add_live_node_for_node(&mut self, hir_id: HirId, lnk: LiveNodeKind) { - let ln = self.add_live_node(lnk); - self.live_node_map.insert(hir_id, ln); - - debug!("{:?} is node {:?}", ln, hir_id); - } - - fn add_variable(&mut self, vk: VarKind) -> Variable { - let v = Variable(self.num_vars as u32); - self.var_kinds.push(vk); - self.num_vars += 1; - - match vk { - Local(LocalInfo { id: node_id, .. }) | Param(node_id, _) => { - self.variable_map.insert(node_id, v); - }, - CleanExit => {} - } - - debug!("{:?} is {:?}", v, vk); - - v - } - - fn variable(&self, hir_id: HirId, span: Span) -> Variable { - match self.variable_map.get(&hir_id) { - Some(&var) => var, - None => { - span_bug!(span, "no variable registered for id {:?}", hir_id); - } - } - } - - fn variable_name(&self, var: Variable) -> String { - match self.var_kinds[var.get()] { - Local(LocalInfo { name, .. }) | Param(_, name) => { - name.to_string() - }, - CleanExit => "".to_owned() - } - } - - fn variable_is_shorthand(&self, var: Variable) -> bool { - match self.var_kinds[var.get()] { - Local(LocalInfo { is_shorthand, .. }) => is_shorthand, - Param(..) | CleanExit => false - } - } - - fn set_captures(&mut self, hir_id: HirId, cs: Vec) { - self.capture_info_map.insert(hir_id, Rc::new(cs)); - } - - fn lnk(&self, ln: LiveNode) -> LiveNodeKind { - self.lnks[ln.get()] - } -} - -fn visit_fn<'tcx>( - ir: &mut IrMaps<'tcx>, - fk: FnKind<'tcx>, - decl: &'tcx hir::FnDecl, - body_id: hir::BodyId, - sp: Span, - id: hir::HirId, -) { - debug!("visit_fn"); - - // swap in a new set of IR maps for this function body: - let def_id = ir.tcx.hir().local_def_id(id); - let mut fn_maps = IrMaps::new(ir.tcx, def_id); - - // Don't run unused pass for #[derive()] - if let FnKind::Method(..) = fk { - let parent = ir.tcx.hir().get_parent_item(id); - if let Some(Node::Item(i)) = ir.tcx.hir().find(parent) { - if i.attrs.iter().any(|a| a.check_name(sym::automatically_derived)) { - return; - } - } - } - - debug!("creating fn_maps: {:p}", &fn_maps); - - let body = ir.tcx.hir().body(body_id); - - for param in &body.params { - let is_shorthand = match param.pat.kind { - crate::hir::PatKind::Struct(..) => true, - _ => false, - }; - param.pat.each_binding(|_bm, hir_id, _x, ident| { - debug!("adding parameters {:?}", hir_id); - let var = if is_shorthand { - Local(LocalInfo { - id: hir_id, - name: ident.name, - is_shorthand: true, - }) - } else { - Param(hir_id, ident.name) - }; - fn_maps.add_variable(var); - }) - }; - - // gather up the various local variables, significant expressions, - // and so forth: - intravisit::walk_fn(&mut fn_maps, fk, decl, body_id, sp, id); - - // compute liveness - let mut lsets = Liveness::new(&mut fn_maps, body_id); - let entry_ln = lsets.compute(&body.value); - - // check for various error conditions - lsets.visit_body(body); - lsets.warn_about_unused_args(body, entry_ln); -} - -fn add_from_pat(ir: &mut IrMaps<'_>, pat: &P) { - // For struct patterns, take note of which fields used shorthand - // (`x` rather than `x: x`). - let mut shorthand_field_ids = HirIdSet::default(); - let mut pats = VecDeque::new(); - pats.push_back(pat); - while let Some(pat) = pats.pop_front() { - use crate::hir::PatKind::*; - match &pat.kind { - Binding(.., inner_pat) => { - pats.extend(inner_pat.iter()); - } - Struct(_, fields, _) => { - let ids = fields.iter().filter(|f| f.is_shorthand).map(|f| f.pat.hir_id); - shorthand_field_ids.extend(ids); - } - Ref(inner_pat, _) | Box(inner_pat) => { - pats.push_back(inner_pat); - } - TupleStruct(_, inner_pats, _) | Tuple(inner_pats, _) | Or(inner_pats) => { - pats.extend(inner_pats.iter()); - } - Slice(pre_pats, inner_pat, post_pats) => { - pats.extend(pre_pats.iter()); - pats.extend(inner_pat.iter()); - pats.extend(post_pats.iter()); - } - _ => {} - } - } - - pat.each_binding(|_, hir_id, _, ident| { - ir.add_live_node_for_node(hir_id, VarDefNode(ident.span)); - ir.add_variable(Local(LocalInfo { - id: hir_id, - name: ident.name, - is_shorthand: shorthand_field_ids.contains(&hir_id) - })); - }); -} - -fn visit_local<'tcx>(ir: &mut IrMaps<'tcx>, local: &'tcx hir::Local) { - add_from_pat(ir, &local.pat); - intravisit::walk_local(ir, local); -} - -fn visit_arm<'tcx>(ir: &mut IrMaps<'tcx>, arm: &'tcx hir::Arm) { - add_from_pat(ir, &arm.pat); - intravisit::walk_arm(ir, arm); -} - -fn visit_expr<'tcx>(ir: &mut IrMaps<'tcx>, expr: &'tcx Expr) { - match expr.kind { - // live nodes required for uses or definitions of variables: - hir::ExprKind::Path(hir::QPath::Resolved(_, ref path)) => { - debug!("expr {}: path that leads to {:?}", expr.hir_id, path.res); - if let Res::Local(var_hir_id) = path.res { - let upvars = ir.tcx.upvars(ir.body_owner); - if !upvars.map_or(false, |upvars| upvars.contains_key(&var_hir_id)) { - ir.add_live_node_for_node(expr.hir_id, ExprNode(expr.span)); - } - } - intravisit::walk_expr(ir, expr); - } - hir::ExprKind::Closure(..) => { - // Interesting control flow (for loops can contain labeled - // breaks or continues) - ir.add_live_node_for_node(expr.hir_id, ExprNode(expr.span)); - - // Make a live_node for each captured variable, with the span - // being the location that the variable is used. This results - // in better error messages than just pointing at the closure - // construction site. - let mut call_caps = Vec::new(); - let closure_def_id = ir.tcx.hir().local_def_id(expr.hir_id); - if let Some(upvars) = ir.tcx.upvars(closure_def_id) { - let parent_upvars = ir.tcx.upvars(ir.body_owner); - call_caps.extend(upvars.iter().filter_map(|(&var_id, upvar)| { - let has_parent = parent_upvars - .map_or(false, |upvars| upvars.contains_key(&var_id)); - if !has_parent { - let upvar_ln = ir.add_live_node(UpvarNode(upvar.span)); - Some(CaptureInfo { ln: upvar_ln, var_hid: var_id }) - } else { - None - } - })); - } - ir.set_captures(expr.hir_id, call_caps); - let old_body_owner = ir.body_owner; - ir.body_owner = closure_def_id; - intravisit::walk_expr(ir, expr); - ir.body_owner = old_body_owner; - } - - // live nodes required for interesting control flow: - hir::ExprKind::Match(..) | - hir::ExprKind::Loop(..) => { - ir.add_live_node_for_node(expr.hir_id, ExprNode(expr.span)); - intravisit::walk_expr(ir, expr); - } - hir::ExprKind::Binary(op, ..) if op.node.is_lazy() => { - ir.add_live_node_for_node(expr.hir_id, ExprNode(expr.span)); - intravisit::walk_expr(ir, expr); - } - - // otherwise, live nodes are not required: - hir::ExprKind::Index(..) | - hir::ExprKind::Field(..) | - hir::ExprKind::Array(..) | - hir::ExprKind::Call(..) | - hir::ExprKind::MethodCall(..) | - hir::ExprKind::Tup(..) | - hir::ExprKind::Binary(..) | - hir::ExprKind::AddrOf(..) | - hir::ExprKind::Cast(..) | - hir::ExprKind::DropTemps(..) | - hir::ExprKind::Unary(..) | - hir::ExprKind::Break(..) | - hir::ExprKind::Continue(_) | - hir::ExprKind::Lit(_) | - hir::ExprKind::Ret(..) | - hir::ExprKind::Block(..) | - hir::ExprKind::Assign(..) | - hir::ExprKind::AssignOp(..) | - hir::ExprKind::Struct(..) | - hir::ExprKind::Repeat(..) | - hir::ExprKind::InlineAsm(..) | - hir::ExprKind::Box(..) | - hir::ExprKind::Yield(..) | - hir::ExprKind::Type(..) | - hir::ExprKind::Err | - hir::ExprKind::Path(hir::QPath::TypeRelative(..)) => { - intravisit::walk_expr(ir, expr); - } - } -} - -// ______________________________________________________________________ -// Computing liveness sets -// -// Actually we compute just a bit more than just liveness, but we use -// the same basic propagation framework in all cases. - -#[derive(Clone, Copy)] -struct RWU { - reader: LiveNode, - writer: LiveNode, - used: bool -} - -/// Conceptually, this is like a `Vec`. But the number of `RWU`s can get -/// very large, so it uses a more compact representation that takes advantage -/// of the fact that when the number of `RWU`s is large, most of them have an -/// invalid reader and an invalid writer. -struct RWUTable { - /// Each entry in `packed_rwus` is either INV_INV_FALSE, INV_INV_TRUE, or - /// an index into `unpacked_rwus`. In the common cases, this compacts the - /// 65 bits of data into 32; in the uncommon cases, it expands the 65 bits - /// in 96. - /// - /// More compact representations are possible -- e.g., use only 2 bits per - /// packed `RWU` and make the secondary table a HashMap that maps from - /// indices to `RWU`s -- but this one strikes a good balance between size - /// and speed. - packed_rwus: Vec, - unpacked_rwus: Vec, -} - -// A constant representing `RWU { reader: invalid_node(); writer: invalid_node(); used: false }`. -const INV_INV_FALSE: u32 = u32::MAX; - -// A constant representing `RWU { reader: invalid_node(); writer: invalid_node(); used: true }`. -const INV_INV_TRUE: u32 = u32::MAX - 1; - -impl RWUTable { - fn new(num_rwus: usize) -> RWUTable { - Self { - packed_rwus: vec![INV_INV_FALSE; num_rwus], - unpacked_rwus: vec![], - } - } - - fn get(&self, idx: usize) -> RWU { - let packed_rwu = self.packed_rwus[idx]; - match packed_rwu { - INV_INV_FALSE => RWU { reader: invalid_node(), writer: invalid_node(), used: false }, - INV_INV_TRUE => RWU { reader: invalid_node(), writer: invalid_node(), used: true }, - _ => self.unpacked_rwus[packed_rwu as usize], - } - } - - fn get_reader(&self, idx: usize) -> LiveNode { - let packed_rwu = self.packed_rwus[idx]; - match packed_rwu { - INV_INV_FALSE | INV_INV_TRUE => invalid_node(), - _ => self.unpacked_rwus[packed_rwu as usize].reader, - } - } - - fn get_writer(&self, idx: usize) -> LiveNode { - let packed_rwu = self.packed_rwus[idx]; - match packed_rwu { - INV_INV_FALSE | INV_INV_TRUE => invalid_node(), - _ => self.unpacked_rwus[packed_rwu as usize].writer, - } - } - - fn get_used(&self, idx: usize) -> bool { - let packed_rwu = self.packed_rwus[idx]; - match packed_rwu { - INV_INV_FALSE => false, - INV_INV_TRUE => true, - _ => self.unpacked_rwus[packed_rwu as usize].used, - } - } - - #[inline] - fn copy_packed(&mut self, dst_idx: usize, src_idx: usize) { - self.packed_rwus[dst_idx] = self.packed_rwus[src_idx]; - } - - fn assign_unpacked(&mut self, idx: usize, rwu: RWU) { - if rwu.reader == invalid_node() && rwu.writer == invalid_node() { - // When we overwrite an indexing entry in `self.packed_rwus` with - // `INV_INV_{TRUE,FALSE}` we don't remove the corresponding entry - // from `self.unpacked_rwus`; it's not worth the effort, and we - // can't have entries shifting around anyway. - self.packed_rwus[idx] = if rwu.used { - INV_INV_TRUE - } else { - INV_INV_FALSE - } - } else { - // Add a new RWU to `unpacked_rwus` and make `packed_rwus[idx]` - // point to it. - self.packed_rwus[idx] = self.unpacked_rwus.len() as u32; - self.unpacked_rwus.push(rwu); - } - } - - fn assign_inv_inv(&mut self, idx: usize) { - self.packed_rwus[idx] = if self.get_used(idx) { - INV_INV_TRUE - } else { - INV_INV_FALSE - }; - } -} - -#[derive(Copy, Clone)] -struct Specials { - exit_ln: LiveNode, - fallthrough_ln: LiveNode, - clean_exit_var: Variable -} - -const ACC_READ: u32 = 1; -const ACC_WRITE: u32 = 2; -const ACC_USE: u32 = 4; - -struct Liveness<'a, 'tcx> { - ir: &'a mut IrMaps<'tcx>, - tables: &'a ty::TypeckTables<'tcx>, - s: Specials, - successors: Vec, - rwu_table: RWUTable, - - // mappings from loop node ID to LiveNode - // ("break" label should map to loop node ID, - // it probably doesn't now) - break_ln: HirIdMap, - cont_ln: HirIdMap, -} - -impl<'a, 'tcx> Liveness<'a, 'tcx> { - fn new(ir: &'a mut IrMaps<'tcx>, body: hir::BodyId) -> Liveness<'a, 'tcx> { - // Special nodes and variables: - // - exit_ln represents the end of the fn, either by return or panic - // - implicit_ret_var is a pseudo-variable that represents - // an implicit return - let specials = Specials { - exit_ln: ir.add_live_node(ExitNode), - fallthrough_ln: ir.add_live_node(ExitNode), - clean_exit_var: ir.add_variable(CleanExit) - }; - - let tables = ir.tcx.body_tables(body); - - let num_live_nodes = ir.num_live_nodes; - let num_vars = ir.num_vars; - - Liveness { - ir, - tables, - s: specials, - successors: vec![invalid_node(); num_live_nodes], - rwu_table: RWUTable::new(num_live_nodes * num_vars), - break_ln: Default::default(), - cont_ln: Default::default(), - } - } - - fn live_node(&self, hir_id: HirId, span: Span) -> LiveNode { - match self.ir.live_node_map.get(&hir_id) { - Some(&ln) => ln, - None => { - // This must be a mismatch between the ir_map construction - // above and the propagation code below; the two sets of - // code have to agree about which AST nodes are worth - // creating liveness nodes for. - span_bug!( - span, - "no live node registered for node {:?}", - hir_id); - } - } - } - - fn variable(&self, hir_id: HirId, span: Span) -> Variable { - self.ir.variable(hir_id, span) - } - - fn define_bindings_in_pat(&mut self, pat: &hir::Pat, mut succ: LiveNode) -> LiveNode { - // In an or-pattern, only consider the first pattern; any later patterns - // must have the same bindings, and we also consider the first pattern - // to be the "authoritative" set of ids. - pat.each_binding_or_first(&mut |_, hir_id, pat_sp, ident| { - let ln = self.live_node(hir_id, pat_sp); - let var = self.variable(hir_id, ident.span); - self.init_from_succ(ln, succ); - self.define(ln, var); - succ = ln; - }); - succ - } - - fn idx(&self, ln: LiveNode, var: Variable) -> usize { - ln.get() * self.ir.num_vars + var.get() - } - - fn live_on_entry(&self, ln: LiveNode, var: Variable) -> Option { - assert!(ln.is_valid()); - let reader = self.rwu_table.get_reader(self.idx(ln, var)); - if reader.is_valid() { Some(self.ir.lnk(reader)) } else { None } - } - - // Is this variable live on entry to any of its successor nodes? - fn live_on_exit(&self, ln: LiveNode, var: Variable) - -> Option { - let successor = self.successors[ln.get()]; - self.live_on_entry(successor, var) - } - - fn used_on_entry(&self, ln: LiveNode, var: Variable) -> bool { - assert!(ln.is_valid()); - self.rwu_table.get_used(self.idx(ln, var)) - } - - fn assigned_on_entry(&self, ln: LiveNode, var: Variable) - -> Option { - assert!(ln.is_valid()); - let writer = self.rwu_table.get_writer(self.idx(ln, var)); - if writer.is_valid() { Some(self.ir.lnk(writer)) } else { None } - } - - fn assigned_on_exit(&self, ln: LiveNode, var: Variable) - -> Option { - let successor = self.successors[ln.get()]; - self.assigned_on_entry(successor, var) - } - - fn indices2(&mut self, ln: LiveNode, succ_ln: LiveNode, mut op: F) where - F: FnMut(&mut Liveness<'a, 'tcx>, usize, usize), - { - let node_base_idx = self.idx(ln, Variable(0)); - let succ_base_idx = self.idx(succ_ln, Variable(0)); - for var_idx in 0..self.ir.num_vars { - op(self, node_base_idx + var_idx, succ_base_idx + var_idx); - } - } - - fn write_vars(&self, - wr: &mut dyn Write, - ln: LiveNode, - mut test: F) - -> io::Result<()> where - F: FnMut(usize) -> LiveNode, - { - let node_base_idx = self.idx(ln, Variable(0)); - for var_idx in 0..self.ir.num_vars { - let idx = node_base_idx + var_idx; - if test(idx).is_valid() { - write!(wr, " {:?}", Variable(var_idx as u32))?; - } - } - Ok(()) - } - - - #[allow(unused_must_use)] - fn ln_str(&self, ln: LiveNode) -> String { - let mut wr = Vec::new(); - { - let wr = &mut wr as &mut dyn Write; - write!(wr, "[ln({:?}) of kind {:?} reads", ln.get(), self.ir.lnk(ln)); - self.write_vars(wr, ln, |idx| self.rwu_table.get_reader(idx)); - write!(wr, " writes"); - self.write_vars(wr, ln, |idx| self.rwu_table.get_writer(idx)); - write!(wr, " precedes {:?}]", self.successors[ln.get()]); - } - String::from_utf8(wr).unwrap() - } - - fn init_empty(&mut self, ln: LiveNode, succ_ln: LiveNode) { - self.successors[ln.get()] = succ_ln; - - // It is not necessary to initialize the RWUs here because they are all - // set to INV_INV_FALSE when they are created, and the sets only grow - // during iterations. - } - - fn init_from_succ(&mut self, ln: LiveNode, succ_ln: LiveNode) { - // more efficient version of init_empty() / merge_from_succ() - self.successors[ln.get()] = succ_ln; - - self.indices2(ln, succ_ln, |this, idx, succ_idx| { - this.rwu_table.copy_packed(idx, succ_idx); - }); - debug!("init_from_succ(ln={}, succ={})", - self.ln_str(ln), self.ln_str(succ_ln)); - } - - fn merge_from_succ(&mut self, - ln: LiveNode, - succ_ln: LiveNode, - first_merge: bool) - -> bool { - if ln == succ_ln { return false; } - - let mut changed = false; - self.indices2(ln, succ_ln, |this, idx, succ_idx| { - let mut rwu = this.rwu_table.get(idx); - let succ_rwu = this.rwu_table.get(succ_idx); - if succ_rwu.reader.is_valid() && !rwu.reader.is_valid() { - rwu.reader = succ_rwu.reader; - changed = true - } - - if succ_rwu.writer.is_valid() && !rwu.writer.is_valid() { - rwu.writer = succ_rwu.writer; - changed = true - } - - if succ_rwu.used && !rwu.used { - rwu.used = true; - changed = true; - } - - if changed { - this.rwu_table.assign_unpacked(idx, rwu); - } - }); - - debug!("merge_from_succ(ln={:?}, succ={}, first_merge={}, changed={})", - ln, self.ln_str(succ_ln), first_merge, changed); - return changed; - } - - // Indicates that a local variable was *defined*; we know that no - // uses of the variable can precede the definition (resolve checks - // this) so we just clear out all the data. - fn define(&mut self, writer: LiveNode, var: Variable) { - let idx = self.idx(writer, var); - self.rwu_table.assign_inv_inv(idx); - - debug!("{:?} defines {:?} (idx={}): {}", writer, var, - idx, self.ln_str(writer)); - } - - // Either read, write, or both depending on the acc bitset - fn acc(&mut self, ln: LiveNode, var: Variable, acc: u32) { - debug!("{:?} accesses[{:x}] {:?}: {}", - ln, acc, var, self.ln_str(ln)); - - let idx = self.idx(ln, var); - let mut rwu = self.rwu_table.get(idx); - - if (acc & ACC_WRITE) != 0 { - rwu.reader = invalid_node(); - rwu.writer = ln; - } - - // Important: if we both read/write, must do read second - // or else the write will override. - if (acc & ACC_READ) != 0 { - rwu.reader = ln; - } - - if (acc & ACC_USE) != 0 { - rwu.used = true; - } - - self.rwu_table.assign_unpacked(idx, rwu); - } - - fn compute(&mut self, body: &hir::Expr) -> LiveNode { - debug!("compute: using id for body, {}", - self.ir.tcx.hir().hir_to_pretty_string(body.hir_id)); - - // the fallthrough exit is only for those cases where we do not - // explicitly return: - let s = self.s; - self.init_from_succ(s.fallthrough_ln, s.exit_ln); - self.acc(s.fallthrough_ln, s.clean_exit_var, ACC_READ); - - let entry_ln = self.propagate_through_expr(body, s.fallthrough_ln); - - // hack to skip the loop unless debug! is enabled: - debug!("^^ liveness computation results for body {} (entry={:?})", { - for ln_idx in 0..self.ir.num_live_nodes { - debug!("{:?}", self.ln_str(LiveNode(ln_idx as u32))); - } - body.hir_id - }, - entry_ln); - - entry_ln - } - - fn propagate_through_block(&mut self, blk: &hir::Block, succ: LiveNode) - -> LiveNode { - if blk.targeted_by_break { - self.break_ln.insert(blk.hir_id, succ); - } - let succ = self.propagate_through_opt_expr(blk.expr.as_ref().map(|e| &**e), succ); - blk.stmts.iter().rev().fold(succ, |succ, stmt| { - self.propagate_through_stmt(stmt, succ) - }) - } - - fn propagate_through_stmt(&mut self, stmt: &hir::Stmt, succ: LiveNode) - -> LiveNode { - match stmt.kind { - hir::StmtKind::Local(ref local) => { - // Note: we mark the variable as defined regardless of whether - // there is an initializer. Initially I had thought to only mark - // the live variable as defined if it was initialized, and then we - // could check for uninit variables just by scanning what is live - // at the start of the function. But that doesn't work so well for - // immutable variables defined in a loop: - // loop { let x; x = 5; } - // because the "assignment" loops back around and generates an error. - // - // So now we just check that variables defined w/o an - // initializer are not live at the point of their - // initialization, which is mildly more complex than checking - // once at the func header but otherwise equivalent. - - let succ = self.propagate_through_opt_expr(local.init.as_ref().map(|e| &**e), succ); - self.define_bindings_in_pat(&local.pat, succ) - } - hir::StmtKind::Item(..) => succ, - hir::StmtKind::Expr(ref expr) | hir::StmtKind::Semi(ref expr) => { - self.propagate_through_expr(&expr, succ) - } - } - } - - fn propagate_through_exprs(&mut self, exprs: &[Expr], succ: LiveNode) - -> LiveNode { - exprs.iter().rev().fold(succ, |succ, expr| { - self.propagate_through_expr(&expr, succ) - }) - } - - fn propagate_through_opt_expr(&mut self, - opt_expr: Option<&Expr>, - succ: LiveNode) - -> LiveNode { - opt_expr.map_or(succ, |expr| self.propagate_through_expr(expr, succ)) - } - - fn propagate_through_expr(&mut self, expr: &Expr, succ: LiveNode) - -> LiveNode { - debug!("propagate_through_expr: {}", self.ir.tcx.hir().hir_to_pretty_string(expr.hir_id)); - - match expr.kind { - // Interesting cases with control flow or which gen/kill - hir::ExprKind::Path(hir::QPath::Resolved(_, ref path)) => { - self.access_path(expr.hir_id, path, succ, ACC_READ | ACC_USE) - } - - hir::ExprKind::Field(ref e, _) => { - self.propagate_through_expr(&e, succ) - } - - hir::ExprKind::Closure(..) => { - debug!("{} is an ExprKind::Closure", - self.ir.tcx.hir().hir_to_pretty_string(expr.hir_id)); - - // the construction of a closure itself is not important, - // but we have to consider the closed over variables. - let caps = self.ir.capture_info_map.get(&expr.hir_id).cloned().unwrap_or_else(|| - span_bug!(expr.span, "no registered caps")); - - caps.iter().rev().fold(succ, |succ, cap| { - self.init_from_succ(cap.ln, succ); - let var = self.variable(cap.var_hid, expr.span); - self.acc(cap.ln, var, ACC_READ | ACC_USE); - cap.ln - }) - } - - // Note that labels have been resolved, so we don't need to look - // at the label ident - hir::ExprKind::Loop(ref blk, _, _) => { - self.propagate_through_loop(expr, &blk, succ) - } - - hir::ExprKind::Match(ref e, ref arms, _) => { - // - // (e) - // | - // v - // (expr) - // / | \ - // | | | - // v v v - // (..arms..) - // | | | - // v v v - // ( succ ) - // - // - let ln = self.live_node(expr.hir_id, expr.span); - self.init_empty(ln, succ); - let mut first_merge = true; - for arm in arms { - let body_succ = self.propagate_through_expr(&arm.body, succ); - - let guard_succ = self.propagate_through_opt_expr( - arm.guard.as_ref().map(|hir::Guard::If(e)| &**e), - body_succ - ); - let arm_succ = self.define_bindings_in_pat(&arm.pat, guard_succ); - self.merge_from_succ(ln, arm_succ, first_merge); - first_merge = false; - }; - self.propagate_through_expr(&e, ln) - } - - hir::ExprKind::Ret(ref o_e) => { - // ignore succ and subst exit_ln: - let exit_ln = self.s.exit_ln; - self.propagate_through_opt_expr(o_e.as_ref().map(|e| &**e), exit_ln) - } - - hir::ExprKind::Break(label, ref opt_expr) => { - // Find which label this break jumps to - let target = match label.target_id { - Ok(hir_id) => self.break_ln.get(&hir_id), - Err(err) => span_bug!(expr.span, "loop scope error: {}", err), - }.cloned(); - - // Now that we know the label we're going to, - // look it up in the break loop nodes table - - match target { - Some(b) => self.propagate_through_opt_expr(opt_expr.as_ref().map(|e| &**e), b), - None => span_bug!(expr.span, "break to unknown label") - } - } - - hir::ExprKind::Continue(label) => { - // Find which label this expr continues to - let sc = label.target_id.unwrap_or_else(|err| - span_bug!(expr.span, "loop scope error: {}", err)); - - // Now that we know the label we're going to, - // look it up in the continue loop nodes table - self.cont_ln.get(&sc).cloned().unwrap_or_else(|| - span_bug!(expr.span, "continue to unknown label")) - } - - hir::ExprKind::Assign(ref l, ref r) => { - // see comment on places in - // propagate_through_place_components() - let succ = self.write_place(&l, succ, ACC_WRITE); - let succ = self.propagate_through_place_components(&l, succ); - self.propagate_through_expr(&r, succ) - } - - hir::ExprKind::AssignOp(_, ref l, ref r) => { - // an overloaded assign op is like a method call - if self.tables.is_method_call(expr) { - let succ = self.propagate_through_expr(&l, succ); - self.propagate_through_expr(&r, succ) - } else { - // see comment on places in - // propagate_through_place_components() - let succ = self.write_place(&l, succ, ACC_WRITE|ACC_READ); - let succ = self.propagate_through_expr(&r, succ); - self.propagate_through_place_components(&l, succ) - } - } - - // Uninteresting cases: just propagate in rev exec order - - hir::ExprKind::Array(ref exprs) => { - self.propagate_through_exprs(exprs, succ) - } - - hir::ExprKind::Struct(_, ref fields, ref with_expr) => { - let succ = self.propagate_through_opt_expr(with_expr.as_ref().map(|e| &**e), succ); - fields.iter().rev().fold(succ, |succ, field| { - self.propagate_through_expr(&field.expr, succ) - }) - } - - hir::ExprKind::Call(ref f, ref args) => { - let m = self.ir.tcx.hir().get_module_parent(expr.hir_id); - let succ = if self.ir.tcx.is_ty_uninhabited_from(m, self.tables.expr_ty(expr)) { - self.s.exit_ln - } else { - succ - }; - let succ = self.propagate_through_exprs(args, succ); - self.propagate_through_expr(&f, succ) - } - - hir::ExprKind::MethodCall(.., ref args) => { - let m = self.ir.tcx.hir().get_module_parent(expr.hir_id); - let succ = if self.ir.tcx.is_ty_uninhabited_from(m, self.tables.expr_ty(expr)) { - self.s.exit_ln - } else { - succ - }; - - self.propagate_through_exprs(args, succ) - } - - hir::ExprKind::Tup(ref exprs) => { - self.propagate_through_exprs(exprs, succ) - } - - hir::ExprKind::Binary(op, ref l, ref r) if op.node.is_lazy() => { - let r_succ = self.propagate_through_expr(&r, succ); - - let ln = self.live_node(expr.hir_id, expr.span); - self.init_from_succ(ln, succ); - self.merge_from_succ(ln, r_succ, false); - - self.propagate_through_expr(&l, ln) - } - - hir::ExprKind::Index(ref l, ref r) | - hir::ExprKind::Binary(_, ref l, ref r) => { - let r_succ = self.propagate_through_expr(&r, succ); - self.propagate_through_expr(&l, r_succ) - } - - hir::ExprKind::Box(ref e) | - hir::ExprKind::AddrOf(_, ref e) | - hir::ExprKind::Cast(ref e, _) | - hir::ExprKind::Type(ref e, _) | - hir::ExprKind::DropTemps(ref e) | - hir::ExprKind::Unary(_, ref e) | - hir::ExprKind::Yield(ref e, _) | - hir::ExprKind::Repeat(ref e, _) => { - self.propagate_through_expr(&e, succ) - } - - hir::ExprKind::InlineAsm(ref ia, ref outputs, ref inputs) => { - let succ = ia.outputs.iter().zip(outputs).rev().fold(succ, |succ, (o, output)| { - // see comment on places - // in propagate_through_place_components() - if o.is_indirect { - self.propagate_through_expr(output, succ) - } else { - let acc = if o.is_rw { ACC_WRITE|ACC_READ } else { ACC_WRITE }; - let succ = self.write_place(output, succ, acc); - self.propagate_through_place_components(output, succ) - }}); - - // Inputs are executed first. Propagate last because of rev order - self.propagate_through_exprs(inputs, succ) - } - - hir::ExprKind::Lit(..) | hir::ExprKind::Err | - hir::ExprKind::Path(hir::QPath::TypeRelative(..)) => { - succ - } - - // Note that labels have been resolved, so we don't need to look - // at the label ident - hir::ExprKind::Block(ref blk, _) => { - self.propagate_through_block(&blk, succ) - } - } - } - - fn propagate_through_place_components(&mut self, - expr: &Expr, - succ: LiveNode) - -> LiveNode { - // # Places - // - // In general, the full flow graph structure for an - // assignment/move/etc can be handled in one of two ways, - // depending on whether what is being assigned is a "tracked - // value" or not. A tracked value is basically a local - // variable or argument. - // - // The two kinds of graphs are: - // - // Tracked place Untracked place - // ----------------------++----------------------- - // || - // | || | - // v || v - // (rvalue) || (rvalue) - // | || | - // v || v - // (write of place) || (place components) - // | || | - // v || v - // (succ) || (succ) - // || - // ----------------------++----------------------- - // - // I will cover the two cases in turn: - // - // # Tracked places - // - // A tracked place is a local variable/argument `x`. In - // these cases, the link_node where the write occurs is linked - // to node id of `x`. The `write_place()` routine generates - // the contents of this node. There are no subcomponents to - // consider. - // - // # Non-tracked places - // - // These are places like `x[5]` or `x.f`. In that case, we - // basically ignore the value which is written to but generate - // reads for the components---`x` in these two examples. The - // components reads are generated by - // `propagate_through_place_components()` (this fn). - // - // # Illegal places - // - // It is still possible to observe assignments to non-places; - // these errors are detected in the later pass borrowck. We - // just ignore such cases and treat them as reads. - - match expr.kind { - hir::ExprKind::Path(_) => succ, - hir::ExprKind::Field(ref e, _) => self.propagate_through_expr(&e, succ), - _ => self.propagate_through_expr(expr, succ) - } - } - - // see comment on propagate_through_place() - fn write_place(&mut self, expr: &Expr, succ: LiveNode, acc: u32) -> LiveNode { - match expr.kind { - hir::ExprKind::Path(hir::QPath::Resolved(_, ref path)) => { - self.access_path(expr.hir_id, path, succ, acc) - } - - // We do not track other places, so just propagate through - // to their subcomponents. Also, it may happen that - // non-places occur here, because those are detected in the - // later pass borrowck. - _ => succ - } - } - - fn access_var(&mut self, hir_id: HirId, var_hid: HirId, succ: LiveNode, acc: u32, span: Span) - -> LiveNode { - let ln = self.live_node(hir_id, span); - if acc != 0 { - self.init_from_succ(ln, succ); - let var = self.variable(var_hid, span); - self.acc(ln, var, acc); - } - ln - } - - fn access_path(&mut self, hir_id: HirId, path: &hir::Path, succ: LiveNode, acc: u32) - -> LiveNode { - match path.res { - Res::Local(hid) => { - let upvars = self.ir.tcx.upvars(self.ir.body_owner); - if !upvars.map_or(false, |upvars| upvars.contains_key(&hid)) { - self.access_var(hir_id, hid, succ, acc, path.span) - } else { - succ - } - } - _ => succ - } - } - - fn propagate_through_loop( - &mut self, - expr: &Expr, - body: &hir::Block, - succ: LiveNode - ) -> LiveNode { - /* - We model control flow like this: - - (expr) <-+ - | | - v | - (body) --+ - - Note that a `continue` expression targeting the `loop` will have a successor of `expr`. - Meanwhile, a `break` expression will have a successor of `succ`. - */ - - // first iteration: - let mut first_merge = true; - let ln = self.live_node(expr.hir_id, expr.span); - self.init_empty(ln, succ); - debug!("propagate_through_loop: using id for loop body {} {}", - expr.hir_id, self.ir.tcx.hir().hir_to_pretty_string(body.hir_id)); - - self.break_ln.insert(expr.hir_id, succ); - - self.cont_ln.insert(expr.hir_id, ln); - - let body_ln = self.propagate_through_block(body, ln); - - // repeat until fixed point is reached: - while self.merge_from_succ(ln, body_ln, first_merge) { - first_merge = false; - assert_eq!(body_ln, self.propagate_through_block(body, ln)); - } - - ln - } -} - -// _______________________________________________________________________ -// Checking for error conditions - -impl<'a, 'tcx> Visitor<'tcx> for Liveness<'a, 'tcx> { - fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> { - NestedVisitorMap::None - } - - fn visit_local(&mut self, local: &'tcx hir::Local) { - self.check_unused_vars_in_pat(&local.pat, None, |spans, hir_id, ln, var| { - if local.init.is_some() { - self.warn_about_dead_assign(spans, hir_id, ln, var); - } - }); - - intravisit::walk_local(self, local); - } - - fn visit_expr(&mut self, ex: &'tcx Expr) { - check_expr(self, ex); - } - - fn visit_arm(&mut self, arm: &'tcx hir::Arm) { - self.check_unused_vars_in_pat(&arm.pat, None, |_, _, _, _| {}); - intravisit::walk_arm(self, arm); - } -} - -fn check_expr<'tcx>(this: &mut Liveness<'_, 'tcx>, expr: &'tcx Expr) { - match expr.kind { - hir::ExprKind::Assign(ref l, _) => { - this.check_place(&l); - } - - hir::ExprKind::AssignOp(_, ref l, _) => { - if !this.tables.is_method_call(expr) { - this.check_place(&l); - } - } - - hir::ExprKind::InlineAsm(ref ia, ref outputs, ref inputs) => { - for input in inputs { - this.visit_expr(input); - } - - // Output operands must be places - for (o, output) in ia.outputs.iter().zip(outputs) { - if !o.is_indirect { - this.check_place(output); - } - this.visit_expr(output); - } - } - - // no correctness conditions related to liveness - hir::ExprKind::Call(..) | hir::ExprKind::MethodCall(..) | - hir::ExprKind::Match(..) | hir::ExprKind::Loop(..) | - hir::ExprKind::Index(..) | hir::ExprKind::Field(..) | - hir::ExprKind::Array(..) | hir::ExprKind::Tup(..) | hir::ExprKind::Binary(..) | - hir::ExprKind::Cast(..) | hir::ExprKind::DropTemps(..) | hir::ExprKind::Unary(..) | - hir::ExprKind::Ret(..) | hir::ExprKind::Break(..) | hir::ExprKind::Continue(..) | - hir::ExprKind::Lit(_) | hir::ExprKind::Block(..) | hir::ExprKind::AddrOf(..) | - hir::ExprKind::Struct(..) | hir::ExprKind::Repeat(..) | - hir::ExprKind::Closure(..) | hir::ExprKind::Path(_) | hir::ExprKind::Yield(..) | - hir::ExprKind::Box(..) | hir::ExprKind::Type(..) | hir::ExprKind::Err => {} - } - - intravisit::walk_expr(this, expr); -} - -impl<'tcx> Liveness<'_, 'tcx> { - fn check_place(&mut self, expr: &'tcx Expr) { - match expr.kind { - hir::ExprKind::Path(hir::QPath::Resolved(_, ref path)) => { - if let Res::Local(var_hid) = path.res { - let upvars = self.ir.tcx.upvars(self.ir.body_owner); - if !upvars.map_or(false, |upvars| upvars.contains_key(&var_hid)) { - // Assignment to an immutable variable or argument: only legal - // if there is no later assignment. If this local is actually - // mutable, then check for a reassignment to flag the mutability - // as being used. - let ln = self.live_node(expr.hir_id, expr.span); - let var = self.variable(var_hid, expr.span); - self.warn_about_dead_assign(vec![expr.span], expr.hir_id, ln, var); - } - } - } - _ => { - // For other kinds of places, no checks are required, - // and any embedded expressions are actually rvalues - intravisit::walk_expr(self, expr); - } - } - } - - fn should_warn(&self, var: Variable) -> Option { - let name = self.ir.variable_name(var); - if name.is_empty() || name.as_bytes()[0] == b'_' { - None - } else { - Some(name) - } - } - - fn warn_about_unused_args(&self, body: &hir::Body, entry_ln: LiveNode) { - for p in &body.params { - self.check_unused_vars_in_pat(&p.pat, Some(entry_ln), |spans, hir_id, ln, var| { - if self.live_on_entry(ln, var).is_none() { - self.report_dead_assign(hir_id, spans, var, true); - } - }); - } - } - - fn check_unused_vars_in_pat( - &self, - pat: &hir::Pat, - entry_ln: Option, - on_used_on_entry: impl Fn(Vec, HirId, LiveNode, Variable), - ) { - // In an or-pattern, only consider the variable; any later patterns must have the same - // bindings, and we also consider the first pattern to be the "authoritative" set of ids. - // However, we should take the spans of variables with the same name from the later - // patterns so the suggestions to prefix with underscores will apply to those too. - let mut vars: FxIndexMap)> = <_>::default(); - - pat.each_binding(|_, hir_id, pat_sp, ident| { - let ln = entry_ln.unwrap_or_else(|| self.live_node(hir_id, pat_sp)); - let var = self.variable(hir_id, ident.span); - vars.entry(self.ir.variable_name(var)) - .and_modify(|(.., spans)| spans.push(ident.span)) - .or_insert_with(|| (ln, var, hir_id, vec![ident.span])); - }); - - for (_, (ln, var, id, spans)) in vars { - if self.used_on_entry(ln, var) { - on_used_on_entry(spans, id, ln, var); - } else { - self.report_unused(spans, id, ln, var); - } - } - } - - fn report_unused(&self, spans: Vec, hir_id: HirId, ln: LiveNode, var: Variable) { - if let Some(name) = self.should_warn(var).filter(|name| name != "self") { - // annoying: for parameters in funcs like `fn(x: i32) - // {ret}`, there is only one node, so asking about - // assigned_on_exit() is not meaningful. - let is_assigned = if ln == self.s.exit_ln { - false - } else { - self.assigned_on_exit(ln, var).is_some() - }; - - if is_assigned { - self.ir.tcx.lint_hir_note( - lint::builtin::UNUSED_VARIABLES, - hir_id, - spans, - &format!("variable `{}` is assigned to, but never used", name), - &format!("consider using `_{}` instead", name), - ); - } else { - let mut err = self.ir.tcx.struct_span_lint_hir( - lint::builtin::UNUSED_VARIABLES, - hir_id, - spans.clone(), - &format!("unused variable: `{}`", name), - ); - - if self.ir.variable_is_shorthand(var) { - if let Node::Binding(pat) = self.ir.tcx.hir().get(hir_id) { - // Handle `ref` and `ref mut`. - let spans = spans.iter() - .map(|_span| (pat.span, format!("{}: _", name))) - .collect(); - - err.multipart_suggestion( - "try ignoring the field", - spans, - Applicability::MachineApplicable, - ); - } - } else { - err.multipart_suggestion( - "consider prefixing with an underscore", - spans.iter().map(|span| (*span, format!("_{}", name))).collect(), - Applicability::MachineApplicable, - ); - } - - err.emit() - } - } - } - - fn warn_about_dead_assign(&self, spans: Vec, hir_id: HirId, ln: LiveNode, var: Variable) { - if self.live_on_exit(ln, var).is_none() { - self.report_dead_assign(hir_id, spans, var, false); - } - } - - fn report_dead_assign(&self, hir_id: HirId, spans: Vec, var: Variable, is_param: bool) { - if let Some(name) = self.should_warn(var) { - if is_param { - self.ir.tcx.struct_span_lint_hir(lint::builtin::UNUSED_ASSIGNMENTS, hir_id, spans, - &format!("value passed to `{}` is never read", name)) - .help("maybe it is overwritten before being read?") - .emit(); - } else { - self.ir.tcx.struct_span_lint_hir(lint::builtin::UNUSED_ASSIGNMENTS, hir_id, spans, - &format!("value assigned to `{}` is never read", name)) - .help("maybe it is overwritten before being read?") - .emit(); - } - } - } -} diff --git a/src/librustc_interface/passes.rs b/src/librustc_interface/passes.rs index bf5e86017fc..ef9da5c2bde 100644 --- a/src/librustc_interface/passes.rs +++ b/src/librustc_interface/passes.rs @@ -781,7 +781,6 @@ pub fn default_provide(providers: &mut ty::query::Providers<'_>) { traits::provide(providers); stability::provide(providers); middle::intrinsicck::provide(providers); - middle::liveness::provide(providers); reachable::provide(providers); rustc_passes::provide(providers); rustc_traits::provide(providers); diff --git a/src/librustc_passes/lib.rs b/src/librustc_passes/lib.rs index 6c7958fb365..7aa353cec08 100644 --- a/src/librustc_passes/lib.rs +++ b/src/librustc_passes/lib.rs @@ -22,7 +22,9 @@ pub mod ast_validation; pub mod hir_stats; pub mod layout_test; pub mod loops; +mod liveness; pub fn provide(providers: &mut Providers<'_>) { loops::provide(providers); + liveness::provide(providers); } diff --git a/src/librustc_passes/liveness.rs b/src/librustc_passes/liveness.rs new file mode 100644 index 00000000000..fb06808619f --- /dev/null +++ b/src/librustc_passes/liveness.rs @@ -0,0 +1,1568 @@ +//! A classic liveness analysis based on dataflow over the AST. Computes, +//! for each local variable in a function, whether that variable is live +//! at a given point. Program execution points are identified by their +//! IDs. +//! +//! # Basic idea +//! +//! The basic model is that each local variable is assigned an index. We +//! represent sets of local variables using a vector indexed by this +//! index. The value in the vector is either 0, indicating the variable +//! is dead, or the ID of an expression that uses the variable. +//! +//! We conceptually walk over the AST in reverse execution order. If we +//! find a use of a variable, we add it to the set of live variables. If +//! we find an assignment to a variable, we remove it from the set of live +//! variables. When we have to merge two flows, we take the union of +//! those two flows -- if the variable is live on both paths, we simply +//! pick one ID. In the event of loops, we continue doing this until a +//! fixed point is reached. +//! +//! ## Checking initialization +//! +//! At the function entry point, all variables must be dead. If this is +//! not the case, we can report an error using the ID found in the set of +//! live variables, which identifies a use of the variable which is not +//! dominated by an assignment. +//! +//! ## Checking moves +//! +//! After each explicit move, the variable must be dead. +//! +//! ## Computing last uses +//! +//! Any use of the variable where the variable is dead afterwards is a +//! last use. +//! +//! # Implementation details +//! +//! The actual implementation contains two (nested) walks over the AST. +//! The outer walk has the job of building up the ir_maps instance for the +//! enclosing function. On the way down the tree, it identifies those AST +//! nodes and variable IDs that will be needed for the liveness analysis +//! and assigns them contiguous IDs. The liveness ID for an AST node is +//! called a `live_node` (it's a newtype'd `u32`) and the ID for a variable +//! is called a `variable` (another newtype'd `u32`). +//! +//! On the way back up the tree, as we are about to exit from a function +//! declaration we allocate a `liveness` instance. Now that we know +//! precisely how many nodes and variables we need, we can allocate all +//! the various arrays that we will need to precisely the right size. We then +//! perform the actual propagation on the `liveness` instance. +//! +//! This propagation is encoded in the various `propagate_through_*()` +//! methods. It effectively does a reverse walk of the AST; whenever we +//! reach a loop node, we iterate until a fixed point is reached. +//! +//! ## The `RWU` struct +//! +//! At each live node `N`, we track three pieces of information for each +//! variable `V` (these are encapsulated in the `RWU` struct): +//! +//! - `reader`: the `LiveNode` ID of some node which will read the value +//! that `V` holds on entry to `N`. Formally: a node `M` such +//! that there exists a path `P` from `N` to `M` where `P` does not +//! write `V`. If the `reader` is `invalid_node()`, then the current +//! value will never be read (the variable is dead, essentially). +//! +//! - `writer`: the `LiveNode` ID of some node which will write the +//! variable `V` and which is reachable from `N`. Formally: a node `M` +//! such that there exists a path `P` from `N` to `M` and `M` writes +//! `V`. If the `writer` is `invalid_node()`, then there is no writer +//! of `V` that follows `N`. +//! +//! - `used`: a boolean value indicating whether `V` is *used*. We +//! distinguish a *read* from a *use* in that a *use* is some read that +//! is not just used to generate a new value. For example, `x += 1` is +//! a read but not a use. This is used to generate better warnings. +//! +//! ## Special Variables +//! +//! We generate various special variables for various, well, special purposes. +//! These are described in the `specials` struct: +//! +//! - `exit_ln`: a live node that is generated to represent every 'exit' from +//! the function, whether it be by explicit return, panic, or other means. +//! +//! - `fallthrough_ln`: a live node that represents a fallthrough +//! +//! - `clean_exit_var`: a synthetic variable that is only 'read' from the +//! fallthrough node. It is only live if the function could converge +//! via means other than an explicit `return` expression. That is, it is +//! only dead if the end of the function's block can never be reached. +//! It is the responsibility of typeck to ensure that there are no +//! `return` expressions in a function declared as diverging. + +use self::LiveNodeKind::*; +use self::VarKind::*; + +use rustc::hir; +use rustc::hir::{Expr, HirId}; +use rustc::hir::def::*; +use rustc::hir::def_id::DefId; +use rustc::hir::intravisit::{self, Visitor, FnKind, NestedVisitorMap}; +use rustc::hir::Node; +use rustc::hir::ptr::P; +use rustc::ty::{self, TyCtxt}; +use rustc::ty::query::Providers; +use rustc::lint; +use rustc::util::nodemap::{HirIdMap, HirIdSet}; + +use errors::Applicability; +use rustc_data_structures::fx::FxIndexMap; +use std::collections::VecDeque; +use std::{fmt, u32}; +use std::io::prelude::*; +use std::io; +use std::rc::Rc; +use syntax::ast; +use syntax::symbol::sym; +use syntax_pos::Span; + +#[derive(Copy, Clone, PartialEq)] +struct Variable(u32); + +#[derive(Copy, Clone, PartialEq)] +struct LiveNode(u32); + +impl Variable { + fn get(&self) -> usize { self.0 as usize } +} + +impl LiveNode { + fn get(&self) -> usize { self.0 as usize } +} + +#[derive(Copy, Clone, PartialEq, Debug)] +enum LiveNodeKind { + UpvarNode(Span), + ExprNode(Span), + VarDefNode(Span), + ExitNode +} + +fn live_node_kind_to_string(lnk: LiveNodeKind, tcx: TyCtxt<'_>) -> String { + let cm = tcx.sess.source_map(); + match lnk { + UpvarNode(s) => { + format!("Upvar node [{}]", cm.span_to_string(s)) + } + ExprNode(s) => { + format!("Expr node [{}]", cm.span_to_string(s)) + } + VarDefNode(s) => { + format!("Var def node [{}]", cm.span_to_string(s)) + } + ExitNode => "Exit node".to_owned(), + } +} + +impl<'tcx> Visitor<'tcx> for IrMaps<'tcx> { + fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> { + NestedVisitorMap::OnlyBodies(&self.tcx.hir()) + } + + fn visit_fn(&mut self, fk: FnKind<'tcx>, fd: &'tcx hir::FnDecl, + b: hir::BodyId, s: Span, id: HirId) { + visit_fn(self, fk, fd, b, s, id); + } + + fn visit_local(&mut self, l: &'tcx hir::Local) { visit_local(self, l); } + fn visit_expr(&mut self, ex: &'tcx Expr) { visit_expr(self, ex); } + fn visit_arm(&mut self, a: &'tcx hir::Arm) { visit_arm(self, a); } +} + +fn check_mod_liveness(tcx: TyCtxt<'_>, module_def_id: DefId) { + tcx.hir().visit_item_likes_in_module( + module_def_id, + &mut IrMaps::new(tcx, module_def_id).as_deep_visitor(), + ); +} + +pub fn provide(providers: &mut Providers<'_>) { + *providers = Providers { + check_mod_liveness, + ..*providers + }; +} + +impl fmt::Debug for LiveNode { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "ln({})", self.get()) + } +} + +impl fmt::Debug for Variable { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "v({})", self.get()) + } +} + +// ______________________________________________________________________ +// Creating ir_maps +// +// This is the first pass and the one that drives the main +// computation. It walks up and down the IR once. On the way down, +// we count for each function the number of variables as well as +// liveness nodes. A liveness node is basically an expression or +// capture clause that does something of interest: either it has +// interesting control flow or it uses/defines a local variable. +// +// On the way back up, at each function node we create liveness sets +// (we now know precisely how big to make our various vectors and so +// forth) and then do the data-flow propagation to compute the set +// of live variables at each program point. +// +// Finally, we run back over the IR one last time and, using the +// computed liveness, check various safety conditions. For example, +// there must be no live nodes at the definition site for a variable +// unless it has an initializer. Similarly, each non-mutable local +// variable must not be assigned if there is some successor +// assignment. And so forth. + +impl LiveNode { + fn is_valid(&self) -> bool { + self.0 != u32::MAX + } +} + +fn invalid_node() -> LiveNode { LiveNode(u32::MAX) } + +struct CaptureInfo { + ln: LiveNode, + var_hid: HirId +} + +#[derive(Copy, Clone, Debug)] +struct LocalInfo { + id: HirId, + name: ast::Name, + is_shorthand: bool, +} + +#[derive(Copy, Clone, Debug)] +enum VarKind { + Param(HirId, ast::Name), + Local(LocalInfo), + CleanExit +} + +struct IrMaps<'tcx> { + tcx: TyCtxt<'tcx>, + body_owner: DefId, + num_live_nodes: usize, + num_vars: usize, + live_node_map: HirIdMap, + variable_map: HirIdMap, + capture_info_map: HirIdMap>>, + var_kinds: Vec, + lnks: Vec, +} + +impl IrMaps<'tcx> { + fn new(tcx: TyCtxt<'tcx>, body_owner: DefId) -> IrMaps<'tcx> { + IrMaps { + tcx, + body_owner, + num_live_nodes: 0, + num_vars: 0, + live_node_map: HirIdMap::default(), + variable_map: HirIdMap::default(), + capture_info_map: Default::default(), + var_kinds: Vec::new(), + lnks: Vec::new(), + } + } + + fn add_live_node(&mut self, lnk: LiveNodeKind) -> LiveNode { + let ln = LiveNode(self.num_live_nodes as u32); + self.lnks.push(lnk); + self.num_live_nodes += 1; + + debug!("{:?} is of kind {}", ln, + live_node_kind_to_string(lnk, self.tcx)); + + ln + } + + fn add_live_node_for_node(&mut self, hir_id: HirId, lnk: LiveNodeKind) { + let ln = self.add_live_node(lnk); + self.live_node_map.insert(hir_id, ln); + + debug!("{:?} is node {:?}", ln, hir_id); + } + + fn add_variable(&mut self, vk: VarKind) -> Variable { + let v = Variable(self.num_vars as u32); + self.var_kinds.push(vk); + self.num_vars += 1; + + match vk { + Local(LocalInfo { id: node_id, .. }) | Param(node_id, _) => { + self.variable_map.insert(node_id, v); + }, + CleanExit => {} + } + + debug!("{:?} is {:?}", v, vk); + + v + } + + fn variable(&self, hir_id: HirId, span: Span) -> Variable { + match self.variable_map.get(&hir_id) { + Some(&var) => var, + None => { + span_bug!(span, "no variable registered for id {:?}", hir_id); + } + } + } + + fn variable_name(&self, var: Variable) -> String { + match self.var_kinds[var.get()] { + Local(LocalInfo { name, .. }) | Param(_, name) => { + name.to_string() + }, + CleanExit => "".to_owned() + } + } + + fn variable_is_shorthand(&self, var: Variable) -> bool { + match self.var_kinds[var.get()] { + Local(LocalInfo { is_shorthand, .. }) => is_shorthand, + Param(..) | CleanExit => false + } + } + + fn set_captures(&mut self, hir_id: HirId, cs: Vec) { + self.capture_info_map.insert(hir_id, Rc::new(cs)); + } + + fn lnk(&self, ln: LiveNode) -> LiveNodeKind { + self.lnks[ln.get()] + } +} + +fn visit_fn<'tcx>( + ir: &mut IrMaps<'tcx>, + fk: FnKind<'tcx>, + decl: &'tcx hir::FnDecl, + body_id: hir::BodyId, + sp: Span, + id: hir::HirId, +) { + debug!("visit_fn"); + + // swap in a new set of IR maps for this function body: + let def_id = ir.tcx.hir().local_def_id(id); + let mut fn_maps = IrMaps::new(ir.tcx, def_id); + + // Don't run unused pass for #[derive()] + if let FnKind::Method(..) = fk { + let parent = ir.tcx.hir().get_parent_item(id); + if let Some(Node::Item(i)) = ir.tcx.hir().find(parent) { + if i.attrs.iter().any(|a| a.check_name(sym::automatically_derived)) { + return; + } + } + } + + debug!("creating fn_maps: {:p}", &fn_maps); + + let body = ir.tcx.hir().body(body_id); + + for param in &body.params { + let is_shorthand = match param.pat.kind { + rustc::hir::PatKind::Struct(..) => true, + _ => false, + }; + param.pat.each_binding(|_bm, hir_id, _x, ident| { + debug!("adding parameters {:?}", hir_id); + let var = if is_shorthand { + Local(LocalInfo { + id: hir_id, + name: ident.name, + is_shorthand: true, + }) + } else { + Param(hir_id, ident.name) + }; + fn_maps.add_variable(var); + }) + }; + + // gather up the various local variables, significant expressions, + // and so forth: + intravisit::walk_fn(&mut fn_maps, fk, decl, body_id, sp, id); + + // compute liveness + let mut lsets = Liveness::new(&mut fn_maps, body_id); + let entry_ln = lsets.compute(&body.value); + + // check for various error conditions + lsets.visit_body(body); + lsets.warn_about_unused_args(body, entry_ln); +} + +fn add_from_pat(ir: &mut IrMaps<'_>, pat: &P) { + // For struct patterns, take note of which fields used shorthand + // (`x` rather than `x: x`). + let mut shorthand_field_ids = HirIdSet::default(); + let mut pats = VecDeque::new(); + pats.push_back(pat); + while let Some(pat) = pats.pop_front() { + use rustc::hir::PatKind::*; + match &pat.kind { + Binding(.., inner_pat) => { + pats.extend(inner_pat.iter()); + } + Struct(_, fields, _) => { + let ids = fields.iter().filter(|f| f.is_shorthand).map(|f| f.pat.hir_id); + shorthand_field_ids.extend(ids); + } + Ref(inner_pat, _) | Box(inner_pat) => { + pats.push_back(inner_pat); + } + TupleStruct(_, inner_pats, _) | Tuple(inner_pats, _) | Or(inner_pats) => { + pats.extend(inner_pats.iter()); + } + Slice(pre_pats, inner_pat, post_pats) => { + pats.extend(pre_pats.iter()); + pats.extend(inner_pat.iter()); + pats.extend(post_pats.iter()); + } + _ => {} + } + } + + pat.each_binding(|_, hir_id, _, ident| { + ir.add_live_node_for_node(hir_id, VarDefNode(ident.span)); + ir.add_variable(Local(LocalInfo { + id: hir_id, + name: ident.name, + is_shorthand: shorthand_field_ids.contains(&hir_id) + })); + }); +} + +fn visit_local<'tcx>(ir: &mut IrMaps<'tcx>, local: &'tcx hir::Local) { + add_from_pat(ir, &local.pat); + intravisit::walk_local(ir, local); +} + +fn visit_arm<'tcx>(ir: &mut IrMaps<'tcx>, arm: &'tcx hir::Arm) { + add_from_pat(ir, &arm.pat); + intravisit::walk_arm(ir, arm); +} + +fn visit_expr<'tcx>(ir: &mut IrMaps<'tcx>, expr: &'tcx Expr) { + match expr.kind { + // live nodes required for uses or definitions of variables: + hir::ExprKind::Path(hir::QPath::Resolved(_, ref path)) => { + debug!("expr {}: path that leads to {:?}", expr.hir_id, path.res); + if let Res::Local(var_hir_id) = path.res { + let upvars = ir.tcx.upvars(ir.body_owner); + if !upvars.map_or(false, |upvars| upvars.contains_key(&var_hir_id)) { + ir.add_live_node_for_node(expr.hir_id, ExprNode(expr.span)); + } + } + intravisit::walk_expr(ir, expr); + } + hir::ExprKind::Closure(..) => { + // Interesting control flow (for loops can contain labeled + // breaks or continues) + ir.add_live_node_for_node(expr.hir_id, ExprNode(expr.span)); + + // Make a live_node for each captured variable, with the span + // being the location that the variable is used. This results + // in better error messages than just pointing at the closure + // construction site. + let mut call_caps = Vec::new(); + let closure_def_id = ir.tcx.hir().local_def_id(expr.hir_id); + if let Some(upvars) = ir.tcx.upvars(closure_def_id) { + let parent_upvars = ir.tcx.upvars(ir.body_owner); + call_caps.extend(upvars.iter().filter_map(|(&var_id, upvar)| { + let has_parent = parent_upvars + .map_or(false, |upvars| upvars.contains_key(&var_id)); + if !has_parent { + let upvar_ln = ir.add_live_node(UpvarNode(upvar.span)); + Some(CaptureInfo { ln: upvar_ln, var_hid: var_id }) + } else { + None + } + })); + } + ir.set_captures(expr.hir_id, call_caps); + let old_body_owner = ir.body_owner; + ir.body_owner = closure_def_id; + intravisit::walk_expr(ir, expr); + ir.body_owner = old_body_owner; + } + + // live nodes required for interesting control flow: + hir::ExprKind::Match(..) | + hir::ExprKind::Loop(..) => { + ir.add_live_node_for_node(expr.hir_id, ExprNode(expr.span)); + intravisit::walk_expr(ir, expr); + } + hir::ExprKind::Binary(op, ..) if op.node.is_lazy() => { + ir.add_live_node_for_node(expr.hir_id, ExprNode(expr.span)); + intravisit::walk_expr(ir, expr); + } + + // otherwise, live nodes are not required: + hir::ExprKind::Index(..) | + hir::ExprKind::Field(..) | + hir::ExprKind::Array(..) | + hir::ExprKind::Call(..) | + hir::ExprKind::MethodCall(..) | + hir::ExprKind::Tup(..) | + hir::ExprKind::Binary(..) | + hir::ExprKind::AddrOf(..) | + hir::ExprKind::Cast(..) | + hir::ExprKind::DropTemps(..) | + hir::ExprKind::Unary(..) | + hir::ExprKind::Break(..) | + hir::ExprKind::Continue(_) | + hir::ExprKind::Lit(_) | + hir::ExprKind::Ret(..) | + hir::ExprKind::Block(..) | + hir::ExprKind::Assign(..) | + hir::ExprKind::AssignOp(..) | + hir::ExprKind::Struct(..) | + hir::ExprKind::Repeat(..) | + hir::ExprKind::InlineAsm(..) | + hir::ExprKind::Box(..) | + hir::ExprKind::Yield(..) | + hir::ExprKind::Type(..) | + hir::ExprKind::Err | + hir::ExprKind::Path(hir::QPath::TypeRelative(..)) => { + intravisit::walk_expr(ir, expr); + } + } +} + +// ______________________________________________________________________ +// Computing liveness sets +// +// Actually we compute just a bit more than just liveness, but we use +// the same basic propagation framework in all cases. + +#[derive(Clone, Copy)] +struct RWU { + reader: LiveNode, + writer: LiveNode, + used: bool +} + +/// Conceptually, this is like a `Vec`. But the number of `RWU`s can get +/// very large, so it uses a more compact representation that takes advantage +/// of the fact that when the number of `RWU`s is large, most of them have an +/// invalid reader and an invalid writer. +struct RWUTable { + /// Each entry in `packed_rwus` is either INV_INV_FALSE, INV_INV_TRUE, or + /// an index into `unpacked_rwus`. In the common cases, this compacts the + /// 65 bits of data into 32; in the uncommon cases, it expands the 65 bits + /// in 96. + /// + /// More compact representations are possible -- e.g., use only 2 bits per + /// packed `RWU` and make the secondary table a HashMap that maps from + /// indices to `RWU`s -- but this one strikes a good balance between size + /// and speed. + packed_rwus: Vec, + unpacked_rwus: Vec, +} + +// A constant representing `RWU { reader: invalid_node(); writer: invalid_node(); used: false }`. +const INV_INV_FALSE: u32 = u32::MAX; + +// A constant representing `RWU { reader: invalid_node(); writer: invalid_node(); used: true }`. +const INV_INV_TRUE: u32 = u32::MAX - 1; + +impl RWUTable { + fn new(num_rwus: usize) -> RWUTable { + Self { + packed_rwus: vec![INV_INV_FALSE; num_rwus], + unpacked_rwus: vec![], + } + } + + fn get(&self, idx: usize) -> RWU { + let packed_rwu = self.packed_rwus[idx]; + match packed_rwu { + INV_INV_FALSE => RWU { reader: invalid_node(), writer: invalid_node(), used: false }, + INV_INV_TRUE => RWU { reader: invalid_node(), writer: invalid_node(), used: true }, + _ => self.unpacked_rwus[packed_rwu as usize], + } + } + + fn get_reader(&self, idx: usize) -> LiveNode { + let packed_rwu = self.packed_rwus[idx]; + match packed_rwu { + INV_INV_FALSE | INV_INV_TRUE => invalid_node(), + _ => self.unpacked_rwus[packed_rwu as usize].reader, + } + } + + fn get_writer(&self, idx: usize) -> LiveNode { + let packed_rwu = self.packed_rwus[idx]; + match packed_rwu { + INV_INV_FALSE | INV_INV_TRUE => invalid_node(), + _ => self.unpacked_rwus[packed_rwu as usize].writer, + } + } + + fn get_used(&self, idx: usize) -> bool { + let packed_rwu = self.packed_rwus[idx]; + match packed_rwu { + INV_INV_FALSE => false, + INV_INV_TRUE => true, + _ => self.unpacked_rwus[packed_rwu as usize].used, + } + } + + #[inline] + fn copy_packed(&mut self, dst_idx: usize, src_idx: usize) { + self.packed_rwus[dst_idx] = self.packed_rwus[src_idx]; + } + + fn assign_unpacked(&mut self, idx: usize, rwu: RWU) { + if rwu.reader == invalid_node() && rwu.writer == invalid_node() { + // When we overwrite an indexing entry in `self.packed_rwus` with + // `INV_INV_{TRUE,FALSE}` we don't remove the corresponding entry + // from `self.unpacked_rwus`; it's not worth the effort, and we + // can't have entries shifting around anyway. + self.packed_rwus[idx] = if rwu.used { + INV_INV_TRUE + } else { + INV_INV_FALSE + } + } else { + // Add a new RWU to `unpacked_rwus` and make `packed_rwus[idx]` + // point to it. + self.packed_rwus[idx] = self.unpacked_rwus.len() as u32; + self.unpacked_rwus.push(rwu); + } + } + + fn assign_inv_inv(&mut self, idx: usize) { + self.packed_rwus[idx] = if self.get_used(idx) { + INV_INV_TRUE + } else { + INV_INV_FALSE + }; + } +} + +#[derive(Copy, Clone)] +struct Specials { + exit_ln: LiveNode, + fallthrough_ln: LiveNode, + clean_exit_var: Variable +} + +const ACC_READ: u32 = 1; +const ACC_WRITE: u32 = 2; +const ACC_USE: u32 = 4; + +struct Liveness<'a, 'tcx> { + ir: &'a mut IrMaps<'tcx>, + tables: &'a ty::TypeckTables<'tcx>, + s: Specials, + successors: Vec, + rwu_table: RWUTable, + + // mappings from loop node ID to LiveNode + // ("break" label should map to loop node ID, + // it probably doesn't now) + break_ln: HirIdMap, + cont_ln: HirIdMap, +} + +impl<'a, 'tcx> Liveness<'a, 'tcx> { + fn new(ir: &'a mut IrMaps<'tcx>, body: hir::BodyId) -> Liveness<'a, 'tcx> { + // Special nodes and variables: + // - exit_ln represents the end of the fn, either by return or panic + // - implicit_ret_var is a pseudo-variable that represents + // an implicit return + let specials = Specials { + exit_ln: ir.add_live_node(ExitNode), + fallthrough_ln: ir.add_live_node(ExitNode), + clean_exit_var: ir.add_variable(CleanExit) + }; + + let tables = ir.tcx.body_tables(body); + + let num_live_nodes = ir.num_live_nodes; + let num_vars = ir.num_vars; + + Liveness { + ir, + tables, + s: specials, + successors: vec![invalid_node(); num_live_nodes], + rwu_table: RWUTable::new(num_live_nodes * num_vars), + break_ln: Default::default(), + cont_ln: Default::default(), + } + } + + fn live_node(&self, hir_id: HirId, span: Span) -> LiveNode { + match self.ir.live_node_map.get(&hir_id) { + Some(&ln) => ln, + None => { + // This must be a mismatch between the ir_map construction + // above and the propagation code below; the two sets of + // code have to agree about which AST nodes are worth + // creating liveness nodes for. + span_bug!( + span, + "no live node registered for node {:?}", + hir_id); + } + } + } + + fn variable(&self, hir_id: HirId, span: Span) -> Variable { + self.ir.variable(hir_id, span) + } + + fn define_bindings_in_pat(&mut self, pat: &hir::Pat, mut succ: LiveNode) -> LiveNode { + // In an or-pattern, only consider the first pattern; any later patterns + // must have the same bindings, and we also consider the first pattern + // to be the "authoritative" set of ids. + pat.each_binding_or_first(&mut |_, hir_id, pat_sp, ident| { + let ln = self.live_node(hir_id, pat_sp); + let var = self.variable(hir_id, ident.span); + self.init_from_succ(ln, succ); + self.define(ln, var); + succ = ln; + }); + succ + } + + fn idx(&self, ln: LiveNode, var: Variable) -> usize { + ln.get() * self.ir.num_vars + var.get() + } + + fn live_on_entry(&self, ln: LiveNode, var: Variable) -> Option { + assert!(ln.is_valid()); + let reader = self.rwu_table.get_reader(self.idx(ln, var)); + if reader.is_valid() { Some(self.ir.lnk(reader)) } else { None } + } + + // Is this variable live on entry to any of its successor nodes? + fn live_on_exit(&self, ln: LiveNode, var: Variable) + -> Option { + let successor = self.successors[ln.get()]; + self.live_on_entry(successor, var) + } + + fn used_on_entry(&self, ln: LiveNode, var: Variable) -> bool { + assert!(ln.is_valid()); + self.rwu_table.get_used(self.idx(ln, var)) + } + + fn assigned_on_entry(&self, ln: LiveNode, var: Variable) + -> Option { + assert!(ln.is_valid()); + let writer = self.rwu_table.get_writer(self.idx(ln, var)); + if writer.is_valid() { Some(self.ir.lnk(writer)) } else { None } + } + + fn assigned_on_exit(&self, ln: LiveNode, var: Variable) + -> Option { + let successor = self.successors[ln.get()]; + self.assigned_on_entry(successor, var) + } + + fn indices2(&mut self, ln: LiveNode, succ_ln: LiveNode, mut op: F) where + F: FnMut(&mut Liveness<'a, 'tcx>, usize, usize), + { + let node_base_idx = self.idx(ln, Variable(0)); + let succ_base_idx = self.idx(succ_ln, Variable(0)); + for var_idx in 0..self.ir.num_vars { + op(self, node_base_idx + var_idx, succ_base_idx + var_idx); + } + } + + fn write_vars(&self, + wr: &mut dyn Write, + ln: LiveNode, + mut test: F) + -> io::Result<()> where + F: FnMut(usize) -> LiveNode, + { + let node_base_idx = self.idx(ln, Variable(0)); + for var_idx in 0..self.ir.num_vars { + let idx = node_base_idx + var_idx; + if test(idx).is_valid() { + write!(wr, " {:?}", Variable(var_idx as u32))?; + } + } + Ok(()) + } + + + #[allow(unused_must_use)] + fn ln_str(&self, ln: LiveNode) -> String { + let mut wr = Vec::new(); + { + let wr = &mut wr as &mut dyn Write; + write!(wr, "[ln({:?}) of kind {:?} reads", ln.get(), self.ir.lnk(ln)); + self.write_vars(wr, ln, |idx| self.rwu_table.get_reader(idx)); + write!(wr, " writes"); + self.write_vars(wr, ln, |idx| self.rwu_table.get_writer(idx)); + write!(wr, " precedes {:?}]", self.successors[ln.get()]); + } + String::from_utf8(wr).unwrap() + } + + fn init_empty(&mut self, ln: LiveNode, succ_ln: LiveNode) { + self.successors[ln.get()] = succ_ln; + + // It is not necessary to initialize the RWUs here because they are all + // set to INV_INV_FALSE when they are created, and the sets only grow + // during iterations. + } + + fn init_from_succ(&mut self, ln: LiveNode, succ_ln: LiveNode) { + // more efficient version of init_empty() / merge_from_succ() + self.successors[ln.get()] = succ_ln; + + self.indices2(ln, succ_ln, |this, idx, succ_idx| { + this.rwu_table.copy_packed(idx, succ_idx); + }); + debug!("init_from_succ(ln={}, succ={})", + self.ln_str(ln), self.ln_str(succ_ln)); + } + + fn merge_from_succ(&mut self, + ln: LiveNode, + succ_ln: LiveNode, + first_merge: bool) + -> bool { + if ln == succ_ln { return false; } + + let mut changed = false; + self.indices2(ln, succ_ln, |this, idx, succ_idx| { + let mut rwu = this.rwu_table.get(idx); + let succ_rwu = this.rwu_table.get(succ_idx); + if succ_rwu.reader.is_valid() && !rwu.reader.is_valid() { + rwu.reader = succ_rwu.reader; + changed = true + } + + if succ_rwu.writer.is_valid() && !rwu.writer.is_valid() { + rwu.writer = succ_rwu.writer; + changed = true + } + + if succ_rwu.used && !rwu.used { + rwu.used = true; + changed = true; + } + + if changed { + this.rwu_table.assign_unpacked(idx, rwu); + } + }); + + debug!("merge_from_succ(ln={:?}, succ={}, first_merge={}, changed={})", + ln, self.ln_str(succ_ln), first_merge, changed); + return changed; + } + + // Indicates that a local variable was *defined*; we know that no + // uses of the variable can precede the definition (resolve checks + // this) so we just clear out all the data. + fn define(&mut self, writer: LiveNode, var: Variable) { + let idx = self.idx(writer, var); + self.rwu_table.assign_inv_inv(idx); + + debug!("{:?} defines {:?} (idx={}): {}", writer, var, + idx, self.ln_str(writer)); + } + + // Either read, write, or both depending on the acc bitset + fn acc(&mut self, ln: LiveNode, var: Variable, acc: u32) { + debug!("{:?} accesses[{:x}] {:?}: {}", + ln, acc, var, self.ln_str(ln)); + + let idx = self.idx(ln, var); + let mut rwu = self.rwu_table.get(idx); + + if (acc & ACC_WRITE) != 0 { + rwu.reader = invalid_node(); + rwu.writer = ln; + } + + // Important: if we both read/write, must do read second + // or else the write will override. + if (acc & ACC_READ) != 0 { + rwu.reader = ln; + } + + if (acc & ACC_USE) != 0 { + rwu.used = true; + } + + self.rwu_table.assign_unpacked(idx, rwu); + } + + fn compute(&mut self, body: &hir::Expr) -> LiveNode { + debug!("compute: using id for body, {}", + self.ir.tcx.hir().hir_to_pretty_string(body.hir_id)); + + // the fallthrough exit is only for those cases where we do not + // explicitly return: + let s = self.s; + self.init_from_succ(s.fallthrough_ln, s.exit_ln); + self.acc(s.fallthrough_ln, s.clean_exit_var, ACC_READ); + + let entry_ln = self.propagate_through_expr(body, s.fallthrough_ln); + + // hack to skip the loop unless debug! is enabled: + debug!("^^ liveness computation results for body {} (entry={:?})", { + for ln_idx in 0..self.ir.num_live_nodes { + debug!("{:?}", self.ln_str(LiveNode(ln_idx as u32))); + } + body.hir_id + }, + entry_ln); + + entry_ln + } + + fn propagate_through_block(&mut self, blk: &hir::Block, succ: LiveNode) + -> LiveNode { + if blk.targeted_by_break { + self.break_ln.insert(blk.hir_id, succ); + } + let succ = self.propagate_through_opt_expr(blk.expr.as_ref().map(|e| &**e), succ); + blk.stmts.iter().rev().fold(succ, |succ, stmt| { + self.propagate_through_stmt(stmt, succ) + }) + } + + fn propagate_through_stmt(&mut self, stmt: &hir::Stmt, succ: LiveNode) + -> LiveNode { + match stmt.kind { + hir::StmtKind::Local(ref local) => { + // Note: we mark the variable as defined regardless of whether + // there is an initializer. Initially I had thought to only mark + // the live variable as defined if it was initialized, and then we + // could check for uninit variables just by scanning what is live + // at the start of the function. But that doesn't work so well for + // immutable variables defined in a loop: + // loop { let x; x = 5; } + // because the "assignment" loops back around and generates an error. + // + // So now we just check that variables defined w/o an + // initializer are not live at the point of their + // initialization, which is mildly more complex than checking + // once at the func header but otherwise equivalent. + + let succ = self.propagate_through_opt_expr(local.init.as_ref().map(|e| &**e), succ); + self.define_bindings_in_pat(&local.pat, succ) + } + hir::StmtKind::Item(..) => succ, + hir::StmtKind::Expr(ref expr) | hir::StmtKind::Semi(ref expr) => { + self.propagate_through_expr(&expr, succ) + } + } + } + + fn propagate_through_exprs(&mut self, exprs: &[Expr], succ: LiveNode) + -> LiveNode { + exprs.iter().rev().fold(succ, |succ, expr| { + self.propagate_through_expr(&expr, succ) + }) + } + + fn propagate_through_opt_expr(&mut self, + opt_expr: Option<&Expr>, + succ: LiveNode) + -> LiveNode { + opt_expr.map_or(succ, |expr| self.propagate_through_expr(expr, succ)) + } + + fn propagate_through_expr(&mut self, expr: &Expr, succ: LiveNode) + -> LiveNode { + debug!("propagate_through_expr: {}", self.ir.tcx.hir().hir_to_pretty_string(expr.hir_id)); + + match expr.kind { + // Interesting cases with control flow or which gen/kill + hir::ExprKind::Path(hir::QPath::Resolved(_, ref path)) => { + self.access_path(expr.hir_id, path, succ, ACC_READ | ACC_USE) + } + + hir::ExprKind::Field(ref e, _) => { + self.propagate_through_expr(&e, succ) + } + + hir::ExprKind::Closure(..) => { + debug!("{} is an ExprKind::Closure", + self.ir.tcx.hir().hir_to_pretty_string(expr.hir_id)); + + // the construction of a closure itself is not important, + // but we have to consider the closed over variables. + let caps = self.ir.capture_info_map.get(&expr.hir_id).cloned().unwrap_or_else(|| + span_bug!(expr.span, "no registered caps")); + + caps.iter().rev().fold(succ, |succ, cap| { + self.init_from_succ(cap.ln, succ); + let var = self.variable(cap.var_hid, expr.span); + self.acc(cap.ln, var, ACC_READ | ACC_USE); + cap.ln + }) + } + + // Note that labels have been resolved, so we don't need to look + // at the label ident + hir::ExprKind::Loop(ref blk, _, _) => { + self.propagate_through_loop(expr, &blk, succ) + } + + hir::ExprKind::Match(ref e, ref arms, _) => { + // + // (e) + // | + // v + // (expr) + // / | \ + // | | | + // v v v + // (..arms..) + // | | | + // v v v + // ( succ ) + // + // + let ln = self.live_node(expr.hir_id, expr.span); + self.init_empty(ln, succ); + let mut first_merge = true; + for arm in arms { + let body_succ = self.propagate_through_expr(&arm.body, succ); + + let guard_succ = self.propagate_through_opt_expr( + arm.guard.as_ref().map(|hir::Guard::If(e)| &**e), + body_succ + ); + let arm_succ = self.define_bindings_in_pat(&arm.pat, guard_succ); + self.merge_from_succ(ln, arm_succ, first_merge); + first_merge = false; + }; + self.propagate_through_expr(&e, ln) + } + + hir::ExprKind::Ret(ref o_e) => { + // ignore succ and subst exit_ln: + let exit_ln = self.s.exit_ln; + self.propagate_through_opt_expr(o_e.as_ref().map(|e| &**e), exit_ln) + } + + hir::ExprKind::Break(label, ref opt_expr) => { + // Find which label this break jumps to + let target = match label.target_id { + Ok(hir_id) => self.break_ln.get(&hir_id), + Err(err) => span_bug!(expr.span, "loop scope error: {}", err), + }.cloned(); + + // Now that we know the label we're going to, + // look it up in the break loop nodes table + + match target { + Some(b) => self.propagate_through_opt_expr(opt_expr.as_ref().map(|e| &**e), b), + None => span_bug!(expr.span, "break to unknown label") + } + } + + hir::ExprKind::Continue(label) => { + // Find which label this expr continues to + let sc = label.target_id.unwrap_or_else(|err| + span_bug!(expr.span, "loop scope error: {}", err)); + + // Now that we know the label we're going to, + // look it up in the continue loop nodes table + self.cont_ln.get(&sc).cloned().unwrap_or_else(|| + span_bug!(expr.span, "continue to unknown label")) + } + + hir::ExprKind::Assign(ref l, ref r) => { + // see comment on places in + // propagate_through_place_components() + let succ = self.write_place(&l, succ, ACC_WRITE); + let succ = self.propagate_through_place_components(&l, succ); + self.propagate_through_expr(&r, succ) + } + + hir::ExprKind::AssignOp(_, ref l, ref r) => { + // an overloaded assign op is like a method call + if self.tables.is_method_call(expr) { + let succ = self.propagate_through_expr(&l, succ); + self.propagate_through_expr(&r, succ) + } else { + // see comment on places in + // propagate_through_place_components() + let succ = self.write_place(&l, succ, ACC_WRITE|ACC_READ); + let succ = self.propagate_through_expr(&r, succ); + self.propagate_through_place_components(&l, succ) + } + } + + // Uninteresting cases: just propagate in rev exec order + + hir::ExprKind::Array(ref exprs) => { + self.propagate_through_exprs(exprs, succ) + } + + hir::ExprKind::Struct(_, ref fields, ref with_expr) => { + let succ = self.propagate_through_opt_expr(with_expr.as_ref().map(|e| &**e), succ); + fields.iter().rev().fold(succ, |succ, field| { + self.propagate_through_expr(&field.expr, succ) + }) + } + + hir::ExprKind::Call(ref f, ref args) => { + let m = self.ir.tcx.hir().get_module_parent(expr.hir_id); + let succ = if self.ir.tcx.is_ty_uninhabited_from(m, self.tables.expr_ty(expr)) { + self.s.exit_ln + } else { + succ + }; + let succ = self.propagate_through_exprs(args, succ); + self.propagate_through_expr(&f, succ) + } + + hir::ExprKind::MethodCall(.., ref args) => { + let m = self.ir.tcx.hir().get_module_parent(expr.hir_id); + let succ = if self.ir.tcx.is_ty_uninhabited_from(m, self.tables.expr_ty(expr)) { + self.s.exit_ln + } else { + succ + }; + + self.propagate_through_exprs(args, succ) + } + + hir::ExprKind::Tup(ref exprs) => { + self.propagate_through_exprs(exprs, succ) + } + + hir::ExprKind::Binary(op, ref l, ref r) if op.node.is_lazy() => { + let r_succ = self.propagate_through_expr(&r, succ); + + let ln = self.live_node(expr.hir_id, expr.span); + self.init_from_succ(ln, succ); + self.merge_from_succ(ln, r_succ, false); + + self.propagate_through_expr(&l, ln) + } + + hir::ExprKind::Index(ref l, ref r) | + hir::ExprKind::Binary(_, ref l, ref r) => { + let r_succ = self.propagate_through_expr(&r, succ); + self.propagate_through_expr(&l, r_succ) + } + + hir::ExprKind::Box(ref e) | + hir::ExprKind::AddrOf(_, ref e) | + hir::ExprKind::Cast(ref e, _) | + hir::ExprKind::Type(ref e, _) | + hir::ExprKind::DropTemps(ref e) | + hir::ExprKind::Unary(_, ref e) | + hir::ExprKind::Yield(ref e, _) | + hir::ExprKind::Repeat(ref e, _) => { + self.propagate_through_expr(&e, succ) + } + + hir::ExprKind::InlineAsm(ref ia, ref outputs, ref inputs) => { + let succ = ia.outputs.iter().zip(outputs).rev().fold(succ, |succ, (o, output)| { + // see comment on places + // in propagate_through_place_components() + if o.is_indirect { + self.propagate_through_expr(output, succ) + } else { + let acc = if o.is_rw { ACC_WRITE|ACC_READ } else { ACC_WRITE }; + let succ = self.write_place(output, succ, acc); + self.propagate_through_place_components(output, succ) + }}); + + // Inputs are executed first. Propagate last because of rev order + self.propagate_through_exprs(inputs, succ) + } + + hir::ExprKind::Lit(..) | hir::ExprKind::Err | + hir::ExprKind::Path(hir::QPath::TypeRelative(..)) => { + succ + } + + // Note that labels have been resolved, so we don't need to look + // at the label ident + hir::ExprKind::Block(ref blk, _) => { + self.propagate_through_block(&blk, succ) + } + } + } + + fn propagate_through_place_components(&mut self, + expr: &Expr, + succ: LiveNode) + -> LiveNode { + // # Places + // + // In general, the full flow graph structure for an + // assignment/move/etc can be handled in one of two ways, + // depending on whether what is being assigned is a "tracked + // value" or not. A tracked value is basically a local + // variable or argument. + // + // The two kinds of graphs are: + // + // Tracked place Untracked place + // ----------------------++----------------------- + // || + // | || | + // v || v + // (rvalue) || (rvalue) + // | || | + // v || v + // (write of place) || (place components) + // | || | + // v || v + // (succ) || (succ) + // || + // ----------------------++----------------------- + // + // I will cover the two cases in turn: + // + // # Tracked places + // + // A tracked place is a local variable/argument `x`. In + // these cases, the link_node where the write occurs is linked + // to node id of `x`. The `write_place()` routine generates + // the contents of this node. There are no subcomponents to + // consider. + // + // # Non-tracked places + // + // These are places like `x[5]` or `x.f`. In that case, we + // basically ignore the value which is written to but generate + // reads for the components---`x` in these two examples. The + // components reads are generated by + // `propagate_through_place_components()` (this fn). + // + // # Illegal places + // + // It is still possible to observe assignments to non-places; + // these errors are detected in the later pass borrowck. We + // just ignore such cases and treat them as reads. + + match expr.kind { + hir::ExprKind::Path(_) => succ, + hir::ExprKind::Field(ref e, _) => self.propagate_through_expr(&e, succ), + _ => self.propagate_through_expr(expr, succ) + } + } + + // see comment on propagate_through_place() + fn write_place(&mut self, expr: &Expr, succ: LiveNode, acc: u32) -> LiveNode { + match expr.kind { + hir::ExprKind::Path(hir::QPath::Resolved(_, ref path)) => { + self.access_path(expr.hir_id, path, succ, acc) + } + + // We do not track other places, so just propagate through + // to their subcomponents. Also, it may happen that + // non-places occur here, because those are detected in the + // later pass borrowck. + _ => succ + } + } + + fn access_var(&mut self, hir_id: HirId, var_hid: HirId, succ: LiveNode, acc: u32, span: Span) + -> LiveNode { + let ln = self.live_node(hir_id, span); + if acc != 0 { + self.init_from_succ(ln, succ); + let var = self.variable(var_hid, span); + self.acc(ln, var, acc); + } + ln + } + + fn access_path(&mut self, hir_id: HirId, path: &hir::Path, succ: LiveNode, acc: u32) + -> LiveNode { + match path.res { + Res::Local(hid) => { + let upvars = self.ir.tcx.upvars(self.ir.body_owner); + if !upvars.map_or(false, |upvars| upvars.contains_key(&hid)) { + self.access_var(hir_id, hid, succ, acc, path.span) + } else { + succ + } + } + _ => succ + } + } + + fn propagate_through_loop( + &mut self, + expr: &Expr, + body: &hir::Block, + succ: LiveNode + ) -> LiveNode { + /* + We model control flow like this: + + (expr) <-+ + | | + v | + (body) --+ + + Note that a `continue` expression targeting the `loop` will have a successor of `expr`. + Meanwhile, a `break` expression will have a successor of `succ`. + */ + + // first iteration: + let mut first_merge = true; + let ln = self.live_node(expr.hir_id, expr.span); + self.init_empty(ln, succ); + debug!("propagate_through_loop: using id for loop body {} {}", + expr.hir_id, self.ir.tcx.hir().hir_to_pretty_string(body.hir_id)); + + self.break_ln.insert(expr.hir_id, succ); + + self.cont_ln.insert(expr.hir_id, ln); + + let body_ln = self.propagate_through_block(body, ln); + + // repeat until fixed point is reached: + while self.merge_from_succ(ln, body_ln, first_merge) { + first_merge = false; + assert_eq!(body_ln, self.propagate_through_block(body, ln)); + } + + ln + } +} + +// _______________________________________________________________________ +// Checking for error conditions + +impl<'a, 'tcx> Visitor<'tcx> for Liveness<'a, 'tcx> { + fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> { + NestedVisitorMap::None + } + + fn visit_local(&mut self, local: &'tcx hir::Local) { + self.check_unused_vars_in_pat(&local.pat, None, |spans, hir_id, ln, var| { + if local.init.is_some() { + self.warn_about_dead_assign(spans, hir_id, ln, var); + } + }); + + intravisit::walk_local(self, local); + } + + fn visit_expr(&mut self, ex: &'tcx Expr) { + check_expr(self, ex); + } + + fn visit_arm(&mut self, arm: &'tcx hir::Arm) { + self.check_unused_vars_in_pat(&arm.pat, None, |_, _, _, _| {}); + intravisit::walk_arm(self, arm); + } +} + +fn check_expr<'tcx>(this: &mut Liveness<'_, 'tcx>, expr: &'tcx Expr) { + match expr.kind { + hir::ExprKind::Assign(ref l, _) => { + this.check_place(&l); + } + + hir::ExprKind::AssignOp(_, ref l, _) => { + if !this.tables.is_method_call(expr) { + this.check_place(&l); + } + } + + hir::ExprKind::InlineAsm(ref ia, ref outputs, ref inputs) => { + for input in inputs { + this.visit_expr(input); + } + + // Output operands must be places + for (o, output) in ia.outputs.iter().zip(outputs) { + if !o.is_indirect { + this.check_place(output); + } + this.visit_expr(output); + } + } + + // no correctness conditions related to liveness + hir::ExprKind::Call(..) | hir::ExprKind::MethodCall(..) | + hir::ExprKind::Match(..) | hir::ExprKind::Loop(..) | + hir::ExprKind::Index(..) | hir::ExprKind::Field(..) | + hir::ExprKind::Array(..) | hir::ExprKind::Tup(..) | hir::ExprKind::Binary(..) | + hir::ExprKind::Cast(..) | hir::ExprKind::DropTemps(..) | hir::ExprKind::Unary(..) | + hir::ExprKind::Ret(..) | hir::ExprKind::Break(..) | hir::ExprKind::Continue(..) | + hir::ExprKind::Lit(_) | hir::ExprKind::Block(..) | hir::ExprKind::AddrOf(..) | + hir::ExprKind::Struct(..) | hir::ExprKind::Repeat(..) | + hir::ExprKind::Closure(..) | hir::ExprKind::Path(_) | hir::ExprKind::Yield(..) | + hir::ExprKind::Box(..) | hir::ExprKind::Type(..) | hir::ExprKind::Err => {} + } + + intravisit::walk_expr(this, expr); +} + +impl<'tcx> Liveness<'_, 'tcx> { + fn check_place(&mut self, expr: &'tcx Expr) { + match expr.kind { + hir::ExprKind::Path(hir::QPath::Resolved(_, ref path)) => { + if let Res::Local(var_hid) = path.res { + let upvars = self.ir.tcx.upvars(self.ir.body_owner); + if !upvars.map_or(false, |upvars| upvars.contains_key(&var_hid)) { + // Assignment to an immutable variable or argument: only legal + // if there is no later assignment. If this local is actually + // mutable, then check for a reassignment to flag the mutability + // as being used. + let ln = self.live_node(expr.hir_id, expr.span); + let var = self.variable(var_hid, expr.span); + self.warn_about_dead_assign(vec![expr.span], expr.hir_id, ln, var); + } + } + } + _ => { + // For other kinds of places, no checks are required, + // and any embedded expressions are actually rvalues + intravisit::walk_expr(self, expr); + } + } + } + + fn should_warn(&self, var: Variable) -> Option { + let name = self.ir.variable_name(var); + if name.is_empty() || name.as_bytes()[0] == b'_' { + None + } else { + Some(name) + } + } + + fn warn_about_unused_args(&self, body: &hir::Body, entry_ln: LiveNode) { + for p in &body.params { + self.check_unused_vars_in_pat(&p.pat, Some(entry_ln), |spans, hir_id, ln, var| { + if self.live_on_entry(ln, var).is_none() { + self.report_dead_assign(hir_id, spans, var, true); + } + }); + } + } + + fn check_unused_vars_in_pat( + &self, + pat: &hir::Pat, + entry_ln: Option, + on_used_on_entry: impl Fn(Vec, HirId, LiveNode, Variable), + ) { + // In an or-pattern, only consider the variable; any later patterns must have the same + // bindings, and we also consider the first pattern to be the "authoritative" set of ids. + // However, we should take the spans of variables with the same name from the later + // patterns so the suggestions to prefix with underscores will apply to those too. + let mut vars: FxIndexMap)> = <_>::default(); + + pat.each_binding(|_, hir_id, pat_sp, ident| { + let ln = entry_ln.unwrap_or_else(|| self.live_node(hir_id, pat_sp)); + let var = self.variable(hir_id, ident.span); + vars.entry(self.ir.variable_name(var)) + .and_modify(|(.., spans)| spans.push(ident.span)) + .or_insert_with(|| (ln, var, hir_id, vec![ident.span])); + }); + + for (_, (ln, var, id, spans)) in vars { + if self.used_on_entry(ln, var) { + on_used_on_entry(spans, id, ln, var); + } else { + self.report_unused(spans, id, ln, var); + } + } + } + + fn report_unused(&self, spans: Vec, hir_id: HirId, ln: LiveNode, var: Variable) { + if let Some(name) = self.should_warn(var).filter(|name| name != "self") { + // annoying: for parameters in funcs like `fn(x: i32) + // {ret}`, there is only one node, so asking about + // assigned_on_exit() is not meaningful. + let is_assigned = if ln == self.s.exit_ln { + false + } else { + self.assigned_on_exit(ln, var).is_some() + }; + + if is_assigned { + self.ir.tcx.lint_hir_note( + lint::builtin::UNUSED_VARIABLES, + hir_id, + spans, + &format!("variable `{}` is assigned to, but never used", name), + &format!("consider using `_{}` instead", name), + ); + } else { + let mut err = self.ir.tcx.struct_span_lint_hir( + lint::builtin::UNUSED_VARIABLES, + hir_id, + spans.clone(), + &format!("unused variable: `{}`", name), + ); + + if self.ir.variable_is_shorthand(var) { + if let Node::Binding(pat) = self.ir.tcx.hir().get(hir_id) { + // Handle `ref` and `ref mut`. + let spans = spans.iter() + .map(|_span| (pat.span, format!("{}: _", name))) + .collect(); + + err.multipart_suggestion( + "try ignoring the field", + spans, + Applicability::MachineApplicable, + ); + } + } else { + err.multipart_suggestion( + "consider prefixing with an underscore", + spans.iter().map(|span| (*span, format!("_{}", name))).collect(), + Applicability::MachineApplicable, + ); + } + + err.emit() + } + } + } + + fn warn_about_dead_assign(&self, spans: Vec, hir_id: HirId, ln: LiveNode, var: Variable) { + if self.live_on_exit(ln, var).is_none() { + self.report_dead_assign(hir_id, spans, var, false); + } + } + + fn report_dead_assign(&self, hir_id: HirId, spans: Vec, var: Variable, is_param: bool) { + if let Some(name) = self.should_warn(var) { + if is_param { + self.ir.tcx.struct_span_lint_hir(lint::builtin::UNUSED_ASSIGNMENTS, hir_id, spans, + &format!("value passed to `{}` is never read", name)) + .help("maybe it is overwritten before being read?") + .emit(); + } else { + self.ir.tcx.struct_span_lint_hir(lint::builtin::UNUSED_ASSIGNMENTS, hir_id, spans, + &format!("value assigned to `{}` is never read", name)) + .help("maybe it is overwritten before being read?") + .emit(); + } + } + } +} -- cgit 1.4.1-3-g733a5 From bb707824d0f8b55a3f8552dd0326d0ae11fefcf6 Mon Sep 17 00:00:00 2001 From: Mark Rousskov Date: Fri, 4 Oct 2019 10:33:11 -0400 Subject: middle::dead -> rustc_passes --- src/librustc/lib.rs | 1 - src/librustc/middle/dead.rs | 676 --------------------------------------- src/librustc_interface/passes.rs | 2 +- src/librustc_passes/dead.rs | 676 +++++++++++++++++++++++++++++++++++++++ src/librustc_passes/lib.rs | 1 + 5 files changed, 678 insertions(+), 678 deletions(-) delete mode 100644 src/librustc/middle/dead.rs create mode 100644 src/librustc_passes/dead.rs diff --git a/src/librustc/lib.rs b/src/librustc/lib.rs index b522de7d43d..46e39bec324 100644 --- a/src/librustc/lib.rs +++ b/src/librustc/lib.rs @@ -102,7 +102,6 @@ pub mod lint; pub mod middle { pub mod expr_use_visitor; pub mod cstore; - pub mod dead; pub mod dependency_format; pub mod diagnostic_items; pub mod entry; diff --git a/src/librustc/middle/dead.rs b/src/librustc/middle/dead.rs deleted file mode 100644 index 7c75a1447e2..00000000000 --- a/src/librustc/middle/dead.rs +++ /dev/null @@ -1,676 +0,0 @@ -// This implements the dead-code warning pass. It follows middle::reachable -// closely. The idea is that all reachable symbols are live, codes called -// from live codes are live, and everything else is dead. - -use crate::hir::Node; -use crate::hir::{self, PatKind, TyKind}; -use crate::hir::intravisit::{self, Visitor, NestedVisitorMap}; -use crate::hir::itemlikevisit::ItemLikeVisitor; - -use crate::hir::def::{CtorOf, Res, DefKind}; -use crate::hir::CodegenFnAttrFlags; -use crate::hir::def_id::{DefId, LOCAL_CRATE}; -use crate::lint; -use crate::middle::privacy; -use crate::ty::{self, DefIdTree, TyCtxt}; -use crate::util::nodemap::FxHashSet; - -use rustc_data_structures::fx::FxHashMap; - -use syntax::{ast, attr}; -use syntax::symbol::sym; -use syntax_pos; - -// Any local node that may call something in its body block should be -// explored. For example, if it's a live Node::Item that is a -// function, then we should explore its block to check for codes that -// may need to be marked as live. -fn should_explore(tcx: TyCtxt<'_>, hir_id: hir::HirId) -> bool { - match tcx.hir().find(hir_id) { - Some(Node::Item(..)) | - Some(Node::ImplItem(..)) | - Some(Node::ForeignItem(..)) | - Some(Node::TraitItem(..)) | - Some(Node::Variant(..)) | - Some(Node::AnonConst(..)) | - Some(Node::Pat(..)) => true, - _ => false - } -} - -struct MarkSymbolVisitor<'a, 'tcx> { - worklist: Vec, - tcx: TyCtxt<'tcx>, - tables: &'a ty::TypeckTables<'tcx>, - live_symbols: FxHashSet, - repr_has_repr_c: bool, - in_pat: bool, - inherited_pub_visibility: bool, - ignore_variant_stack: Vec, - // maps from tuple struct constructors to tuple struct items - struct_constructors: FxHashMap, -} - -impl<'a, 'tcx> MarkSymbolVisitor<'a, 'tcx> { - fn check_def_id(&mut self, def_id: DefId) { - if let Some(hir_id) = self.tcx.hir().as_local_hir_id(def_id) { - if should_explore(self.tcx, hir_id) || self.struct_constructors.contains_key(&hir_id) { - self.worklist.push(hir_id); - } - self.live_symbols.insert(hir_id); - } - } - - fn insert_def_id(&mut self, def_id: DefId) { - if let Some(hir_id) = self.tcx.hir().as_local_hir_id(def_id) { - debug_assert!(!should_explore(self.tcx, hir_id)); - self.live_symbols.insert(hir_id); - } - } - - fn handle_res(&mut self, res: Res) { - match res { - Res::Def(DefKind::Const, _) - | Res::Def(DefKind::AssocConst, _) - | Res::Def(DefKind::TyAlias, _) => { - self.check_def_id(res.def_id()); - } - _ if self.in_pat => {}, - Res::PrimTy(..) | Res::SelfCtor(..) | - Res::Local(..) => {} - Res::Def(DefKind::Ctor(CtorOf::Variant, ..), ctor_def_id) => { - let variant_id = self.tcx.parent(ctor_def_id).unwrap(); - let enum_id = self.tcx.parent(variant_id).unwrap(); - self.check_def_id(enum_id); - if !self.ignore_variant_stack.contains(&ctor_def_id) { - self.check_def_id(variant_id); - } - } - Res::Def(DefKind::Variant, variant_id) => { - let enum_id = self.tcx.parent(variant_id).unwrap(); - self.check_def_id(enum_id); - if !self.ignore_variant_stack.contains(&variant_id) { - self.check_def_id(variant_id); - } - } - Res::SelfTy(t, i) => { - if let Some(t) = t { - self.check_def_id(t); - } - if let Some(i) = i { - self.check_def_id(i); - } - } - Res::ToolMod | Res::NonMacroAttr(..) | Res::Err => {} - _ => { - self.check_def_id(res.def_id()); - } - } - } - - fn lookup_and_handle_method(&mut self, id: hir::HirId) { - if let Some(def_id) = self.tables.type_dependent_def_id(id) { - self.check_def_id(def_id); - } else { - bug!("no type-dependent def for method"); - } - } - - fn handle_field_access(&mut self, lhs: &hir::Expr, hir_id: hir::HirId) { - match self.tables.expr_ty_adjusted(lhs).kind { - ty::Adt(def, _) => { - let index = self.tcx.field_index(hir_id, self.tables); - self.insert_def_id(def.non_enum_variant().fields[index].did); - } - ty::Tuple(..) => {} - _ => span_bug!(lhs.span, "named field access on non-ADT"), - } - } - - fn handle_field_pattern_match(&mut self, lhs: &hir::Pat, res: Res, pats: &[hir::FieldPat]) { - let variant = match self.tables.node_type(lhs.hir_id).kind { - ty::Adt(adt, _) => adt.variant_of_res(res), - _ => span_bug!(lhs.span, "non-ADT in struct pattern") - }; - for pat in pats { - if let PatKind::Wild = pat.pat.kind { - continue; - } - let index = self.tcx.field_index(pat.hir_id, self.tables); - self.insert_def_id(variant.fields[index].did); - } - } - - fn mark_live_symbols(&mut self) { - let mut scanned = FxHashSet::default(); - while let Some(id) = self.worklist.pop() { - if !scanned.insert(id) { - continue - } - - // in the case of tuple struct constructors we want to check the item, not the generated - // tuple struct constructor function - let id = self.struct_constructors.get(&id).cloned().unwrap_or(id); - - if let Some(node) = self.tcx.hir().find(id) { - self.live_symbols.insert(id); - self.visit_node(node); - } - } - } - - fn visit_node(&mut self, node: Node<'tcx>) { - let had_repr_c = self.repr_has_repr_c; - self.repr_has_repr_c = false; - let had_inherited_pub_visibility = self.inherited_pub_visibility; - self.inherited_pub_visibility = false; - match node { - Node::Item(item) => { - match item.kind { - hir::ItemKind::Struct(..) | hir::ItemKind::Union(..) => { - let def_id = self.tcx.hir().local_def_id(item.hir_id); - let def = self.tcx.adt_def(def_id); - self.repr_has_repr_c = def.repr.c(); - - intravisit::walk_item(self, &item); - } - hir::ItemKind::Enum(..) => { - self.inherited_pub_visibility = item.vis.node.is_pub(); - - intravisit::walk_item(self, &item); - } - hir::ItemKind::ForeignMod(..) => {} - _ => { - intravisit::walk_item(self, &item); - } - } - } - Node::TraitItem(trait_item) => { - intravisit::walk_trait_item(self, trait_item); - } - Node::ImplItem(impl_item) => { - intravisit::walk_impl_item(self, impl_item); - } - Node::ForeignItem(foreign_item) => { - intravisit::walk_foreign_item(self, &foreign_item); - } - _ => {} - } - self.repr_has_repr_c = had_repr_c; - self.inherited_pub_visibility = had_inherited_pub_visibility; - } - - fn mark_as_used_if_union(&mut self, adt: &ty::AdtDef, fields: &hir::HirVec) { - if adt.is_union() && adt.non_enum_variant().fields.len() > 1 && adt.did.is_local() { - for field in fields { - let index = self.tcx.field_index(field.hir_id, self.tables); - self.insert_def_id(adt.non_enum_variant().fields[index].did); - } - } - } -} - -impl<'a, 'tcx> Visitor<'tcx> for MarkSymbolVisitor<'a, 'tcx> { - fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> { - NestedVisitorMap::None - } - - fn visit_nested_body(&mut self, body: hir::BodyId) { - let old_tables = self.tables; - self.tables = self.tcx.body_tables(body); - let body = self.tcx.hir().body(body); - self.visit_body(body); - self.tables = old_tables; - } - - fn visit_variant_data(&mut self, def: &'tcx hir::VariantData, _: ast::Name, - _: &hir::Generics, _: hir::HirId, _: syntax_pos::Span) { - let has_repr_c = self.repr_has_repr_c; - let inherited_pub_visibility = self.inherited_pub_visibility; - let live_fields = def.fields().iter().filter(|f| { - has_repr_c || inherited_pub_visibility || f.vis.node.is_pub() - }); - self.live_symbols.extend(live_fields.map(|f| f.hir_id)); - - intravisit::walk_struct_def(self, def); - } - - fn visit_expr(&mut self, expr: &'tcx hir::Expr) { - match expr.kind { - hir::ExprKind::Path(ref qpath @ hir::QPath::TypeRelative(..)) => { - let res = self.tables.qpath_res(qpath, expr.hir_id); - self.handle_res(res); - } - hir::ExprKind::MethodCall(..) => { - self.lookup_and_handle_method(expr.hir_id); - } - hir::ExprKind::Field(ref lhs, ..) => { - self.handle_field_access(&lhs, expr.hir_id); - } - hir::ExprKind::Struct(_, ref fields, _) => { - if let ty::Adt(ref adt, _) = self.tables.expr_ty(expr).kind { - self.mark_as_used_if_union(adt, fields); - } - } - _ => () - } - - intravisit::walk_expr(self, expr); - } - - fn visit_arm(&mut self, arm: &'tcx hir::Arm) { - // Inside the body, ignore constructions of variants - // necessary for the pattern to match. Those construction sites - // can't be reached unless the variant is constructed elsewhere. - let len = self.ignore_variant_stack.len(); - self.ignore_variant_stack.extend(arm.pat.necessary_variants()); - intravisit::walk_arm(self, arm); - self.ignore_variant_stack.truncate(len); - } - - fn visit_pat(&mut self, pat: &'tcx hir::Pat) { - match pat.kind { - PatKind::Struct(ref path, ref fields, _) => { - let res = self.tables.qpath_res(path, pat.hir_id); - self.handle_field_pattern_match(pat, res, fields); - } - PatKind::Path(ref qpath) => { - let res = self.tables.qpath_res(qpath, pat.hir_id); - self.handle_res(res); - } - _ => () - } - - self.in_pat = true; - intravisit::walk_pat(self, pat); - self.in_pat = false; - } - - fn visit_path(&mut self, path: &'tcx hir::Path, _: hir::HirId) { - self.handle_res(path.res); - intravisit::walk_path(self, path); - } - - fn visit_ty(&mut self, ty: &'tcx hir::Ty) { - match ty.kind { - TyKind::Def(item_id, _) => { - let item = self.tcx.hir().expect_item(item_id.id); - intravisit::walk_item(self, item); - } - _ => () - } - intravisit::walk_ty(self, ty); - } - - fn visit_anon_const(&mut self, c: &'tcx hir::AnonConst) { - self.live_symbols.insert(c.hir_id); - intravisit::walk_anon_const(self, c); - } -} - -fn has_allow_dead_code_or_lang_attr( - tcx: TyCtxt<'_>, - id: hir::HirId, - attrs: &[ast::Attribute], -) -> bool { - if attr::contains_name(attrs, sym::lang) { - return true; - } - - // Stable attribute for #[lang = "panic_impl"] - if attr::contains_name(attrs, sym::panic_handler) { - return true; - } - - // (To be) stable attribute for #[lang = "oom"] - if attr::contains_name(attrs, sym::alloc_error_handler) { - return true; - } - - let def_id = tcx.hir().local_def_id(id); - let cg_attrs = tcx.codegen_fn_attrs(def_id); - - // #[used], #[no_mangle], #[export_name], etc also keeps the item alive - // forcefully, e.g., for placing it in a specific section. - if cg_attrs.contains_extern_indicator() || - cg_attrs.flags.contains(CodegenFnAttrFlags::USED) { - return true; - } - - tcx.lint_level_at_node(lint::builtin::DEAD_CODE, id).0 == lint::Allow -} - -// This visitor seeds items that -// 1) We want to explicitly consider as live: -// * Item annotated with #[allow(dead_code)] -// - This is done so that if we want to suppress warnings for a -// group of dead functions, we only have to annotate the "root". -// For example, if both `f` and `g` are dead and `f` calls `g`, -// then annotating `f` with `#[allow(dead_code)]` will suppress -// warning for both `f` and `g`. -// * Item annotated with #[lang=".."] -// - This is because lang items are always callable from elsewhere. -// or -// 2) We are not sure to be live or not -// * Implementation of a trait method -struct LifeSeeder<'k, 'tcx> { - worklist: Vec, - krate: &'k hir::Crate, - tcx: TyCtxt<'tcx>, - // see `MarkSymbolVisitor::struct_constructors` - struct_constructors: FxHashMap, -} - -impl<'v, 'k, 'tcx> ItemLikeVisitor<'v> for LifeSeeder<'k, 'tcx> { - fn visit_item(&mut self, item: &hir::Item) { - let allow_dead_code = has_allow_dead_code_or_lang_attr(self.tcx, - item.hir_id, - &item.attrs); - if allow_dead_code { - self.worklist.push(item.hir_id); - } - match item.kind { - hir::ItemKind::Enum(ref enum_def, _) => { - if allow_dead_code { - self.worklist.extend(enum_def.variants.iter().map(|variant| variant.id)); - } - - for variant in &enum_def.variants { - if let Some(ctor_hir_id) = variant.data.ctor_hir_id() { - self.struct_constructors.insert(ctor_hir_id, variant.id); - } - } - } - hir::ItemKind::Trait(.., ref trait_item_refs) => { - for trait_item_ref in trait_item_refs { - let trait_item = self.krate.trait_item(trait_item_ref.id); - match trait_item.kind { - hir::TraitItemKind::Const(_, Some(_)) | - hir::TraitItemKind::Method(_, hir::TraitMethod::Provided(_)) => { - if has_allow_dead_code_or_lang_attr(self.tcx, - trait_item.hir_id, - &trait_item.attrs) { - self.worklist.push(trait_item.hir_id); - } - } - _ => {} - } - } - } - hir::ItemKind::Impl(.., ref opt_trait, _, ref impl_item_refs) => { - for impl_item_ref in impl_item_refs { - let impl_item = self.krate.impl_item(impl_item_ref.id); - if opt_trait.is_some() || - has_allow_dead_code_or_lang_attr(self.tcx, - impl_item.hir_id, - &impl_item.attrs) { - self.worklist.push(impl_item_ref.id.hir_id); - } - } - } - hir::ItemKind::Struct(ref variant_data, _) => { - if let Some(ctor_hir_id) = variant_data.ctor_hir_id() { - self.struct_constructors.insert(ctor_hir_id, item.hir_id); - } - } - _ => () - } - } - - fn visit_trait_item(&mut self, _item: &hir::TraitItem) { - // ignore: we are handling this in `visit_item` above - } - - fn visit_impl_item(&mut self, _item: &hir::ImplItem) { - // ignore: we are handling this in `visit_item` above - } -} - -fn create_and_seed_worklist<'tcx>( - tcx: TyCtxt<'tcx>, - access_levels: &privacy::AccessLevels, - krate: &hir::Crate, -) -> (Vec, FxHashMap) { - let worklist = access_levels.map.iter().filter_map(|(&id, level)| { - if level >= &privacy::AccessLevel::Reachable { - Some(id) - } else { - None - } - }).chain( - // Seed entry point - tcx.entry_fn(LOCAL_CRATE).map(|(def_id, _)| tcx.hir().as_local_hir_id(def_id).unwrap()) - ).collect::>(); - - // Seed implemented trait items - let mut life_seeder = LifeSeeder { - worklist, - krate, - tcx, - struct_constructors: Default::default(), - }; - krate.visit_all_item_likes(&mut life_seeder); - - (life_seeder.worklist, life_seeder.struct_constructors) -} - -fn find_live<'tcx>( - tcx: TyCtxt<'tcx>, - access_levels: &privacy::AccessLevels, - krate: &hir::Crate, -) -> FxHashSet { - let (worklist, struct_constructors) = create_and_seed_worklist(tcx, access_levels, krate); - let mut symbol_visitor = MarkSymbolVisitor { - worklist, - tcx, - tables: &ty::TypeckTables::empty(None), - live_symbols: Default::default(), - repr_has_repr_c: false, - in_pat: false, - inherited_pub_visibility: false, - ignore_variant_stack: vec![], - struct_constructors, - }; - symbol_visitor.mark_live_symbols(); - symbol_visitor.live_symbols -} - -struct DeadVisitor<'tcx> { - tcx: TyCtxt<'tcx>, - live_symbols: FxHashSet, -} - -impl DeadVisitor<'tcx> { - fn should_warn_about_item(&mut self, item: &hir::Item) -> bool { - let should_warn = match item.kind { - hir::ItemKind::Static(..) - | hir::ItemKind::Const(..) - | hir::ItemKind::Fn(..) - | hir::ItemKind::TyAlias(..) - | hir::ItemKind::Enum(..) - | hir::ItemKind::Struct(..) - | hir::ItemKind::Union(..) => true, - _ => false - }; - should_warn && !self.symbol_is_live(item.hir_id) - } - - fn should_warn_about_field(&mut self, field: &hir::StructField) -> bool { - let field_type = self.tcx.type_of(self.tcx.hir().local_def_id(field.hir_id)); - !field.is_positional() - && !self.symbol_is_live(field.hir_id) - && !field_type.is_phantom_data() - && !has_allow_dead_code_or_lang_attr(self.tcx, field.hir_id, &field.attrs) - } - - fn should_warn_about_variant(&mut self, variant: &hir::Variant) -> bool { - !self.symbol_is_live(variant.id) - && !has_allow_dead_code_or_lang_attr(self.tcx, - variant.id, - &variant.attrs) - } - - fn should_warn_about_foreign_item(&mut self, fi: &hir::ForeignItem) -> bool { - !self.symbol_is_live(fi.hir_id) - && !has_allow_dead_code_or_lang_attr(self.tcx, fi.hir_id, &fi.attrs) - } - - // id := HIR id of an item's definition. - fn symbol_is_live( - &mut self, - id: hir::HirId, - ) -> bool { - if self.live_symbols.contains(&id) { - return true; - } - // If it's a type whose items are live, then it's live, too. - // This is done to handle the case where, for example, the static - // method of a private type is used, but the type itself is never - // called directly. - let def_id = self.tcx.hir().local_def_id(id); - let inherent_impls = self.tcx.inherent_impls(def_id); - for &impl_did in inherent_impls.iter() { - for &item_did in &self.tcx.associated_item_def_ids(impl_did)[..] { - if let Some(item_hir_id) = self.tcx.hir().as_local_hir_id(item_did) { - if self.live_symbols.contains(&item_hir_id) { - return true; - } - } - } - } - false - } - - fn warn_dead_code(&mut self, - id: hir::HirId, - span: syntax_pos::Span, - name: ast::Name, - node_type: &str, - participle: &str) { - if !name.as_str().starts_with("_") { - self.tcx - .lint_hir(lint::builtin::DEAD_CODE, - id, - span, - &format!("{} is never {}: `{}`", - node_type, participle, name)); - } - } -} - -impl Visitor<'tcx> for DeadVisitor<'tcx> { - /// Walk nested items in place so that we don't report dead-code - /// on inner functions when the outer function is already getting - /// an error. We could do this also by checking the parents, but - /// this is how the code is setup and it seems harmless enough. - fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> { - NestedVisitorMap::All(&self.tcx.hir()) - } - - fn visit_item(&mut self, item: &'tcx hir::Item) { - if self.should_warn_about_item(item) { - // For items that have a definition with a signature followed by a - // block, point only at the signature. - let span = match item.kind { - hir::ItemKind::Fn(..) | - hir::ItemKind::Mod(..) | - hir::ItemKind::Enum(..) | - hir::ItemKind::Struct(..) | - hir::ItemKind::Union(..) | - hir::ItemKind::Trait(..) | - hir::ItemKind::Impl(..) => self.tcx.sess.source_map().def_span(item.span), - _ => item.span, - }; - let participle = match item.kind { - hir::ItemKind::Struct(..) => "constructed", // Issue #52325 - _ => "used" - }; - self.warn_dead_code( - item.hir_id, - span, - item.ident.name, - item.kind.descriptive_variant(), - participle, - ); - } else { - // Only continue if we didn't warn - intravisit::walk_item(self, item); - } - } - - fn visit_variant(&mut self, - variant: &'tcx hir::Variant, - g: &'tcx hir::Generics, - id: hir::HirId) { - if self.should_warn_about_variant(&variant) { - self.warn_dead_code(variant.id, variant.span, variant.ident.name, - "variant", "constructed"); - } else { - intravisit::walk_variant(self, variant, g, id); - } - } - - fn visit_foreign_item(&mut self, fi: &'tcx hir::ForeignItem) { - if self.should_warn_about_foreign_item(fi) { - self.warn_dead_code(fi.hir_id, fi.span, fi.ident.name, - fi.kind.descriptive_variant(), "used"); - } - intravisit::walk_foreign_item(self, fi); - } - - fn visit_struct_field(&mut self, field: &'tcx hir::StructField) { - if self.should_warn_about_field(&field) { - self.warn_dead_code(field.hir_id, field.span, field.ident.name, "field", "used"); - } - intravisit::walk_struct_field(self, field); - } - - fn visit_impl_item(&mut self, impl_item: &'tcx hir::ImplItem) { - match impl_item.kind { - hir::ImplItemKind::Const(_, body_id) => { - if !self.symbol_is_live(impl_item.hir_id) { - self.warn_dead_code(impl_item.hir_id, - impl_item.span, - impl_item.ident.name, - "associated const", - "used"); - } - self.visit_nested_body(body_id) - } - hir::ImplItemKind::Method(_, body_id) => { - if !self.symbol_is_live(impl_item.hir_id) { - let span = self.tcx.sess.source_map().def_span(impl_item.span); - self.warn_dead_code(impl_item.hir_id, span, impl_item.ident.name, "method", - "used"); - } - self.visit_nested_body(body_id) - } - hir::ImplItemKind::OpaqueTy(..) | - hir::ImplItemKind::TyAlias(..) => {} - } - } - - // Overwrite so that we don't warn the trait item itself. - fn visit_trait_item(&mut self, trait_item: &'tcx hir::TraitItem) { - match trait_item.kind { - hir::TraitItemKind::Const(_, Some(body_id)) | - hir::TraitItemKind::Method(_, hir::TraitMethod::Provided(body_id)) => { - self.visit_nested_body(body_id) - } - hir::TraitItemKind::Const(_, None) | - hir::TraitItemKind::Method(_, hir::TraitMethod::Required(_)) | - hir::TraitItemKind::Type(..) => {} - } - } -} - -pub fn check_crate(tcx: TyCtxt<'_>) { - let access_levels = &tcx.privacy_access_levels(LOCAL_CRATE); - let krate = tcx.hir().krate(); - let live_symbols = find_live(tcx, access_levels, krate); - let mut visitor = DeadVisitor { - tcx, - live_symbols, - }; - intravisit::walk_crate(&mut visitor, krate); -} diff --git a/src/librustc_interface/passes.rs b/src/librustc_interface/passes.rs index ef9da5c2bde..2fa6edb46b1 100644 --- a/src/librustc_interface/passes.rs +++ b/src/librustc_interface/passes.rs @@ -972,7 +972,7 @@ fn analysis(tcx: TyCtxt<'_>, cnum: CrateNum) -> Result<()> { tcx.ensure().check_private_in_public(LOCAL_CRATE); }); }, { - time(sess, "death checking", || middle::dead::check_crate(tcx)); + time(sess, "death checking", || rustc_passes::dead::check_crate(tcx)); }, { time(sess, "unused lib feature checking", || { stability::check_unused_or_stable_features(tcx) diff --git a/src/librustc_passes/dead.rs b/src/librustc_passes/dead.rs new file mode 100644 index 00000000000..f2aef2c12c7 --- /dev/null +++ b/src/librustc_passes/dead.rs @@ -0,0 +1,676 @@ +// This implements the dead-code warning pass. It follows middle::reachable +// closely. The idea is that all reachable symbols are live, codes called +// from live codes are live, and everything else is dead. + +use rustc::hir::Node; +use rustc::hir::{self, PatKind, TyKind}; +use rustc::hir::intravisit::{self, Visitor, NestedVisitorMap}; +use rustc::hir::itemlikevisit::ItemLikeVisitor; + +use rustc::hir::def::{CtorOf, Res, DefKind}; +use rustc::hir::CodegenFnAttrFlags; +use rustc::hir::def_id::{DefId, LOCAL_CRATE}; +use rustc::lint; +use rustc::middle::privacy; +use rustc::ty::{self, DefIdTree, TyCtxt}; +use rustc::util::nodemap::FxHashSet; + +use rustc_data_structures::fx::FxHashMap; + +use syntax::{ast, attr}; +use syntax::symbol::sym; +use syntax_pos; + +// Any local node that may call something in its body block should be +// explored. For example, if it's a live Node::Item that is a +// function, then we should explore its block to check for codes that +// may need to be marked as live. +fn should_explore(tcx: TyCtxt<'_>, hir_id: hir::HirId) -> bool { + match tcx.hir().find(hir_id) { + Some(Node::Item(..)) | + Some(Node::ImplItem(..)) | + Some(Node::ForeignItem(..)) | + Some(Node::TraitItem(..)) | + Some(Node::Variant(..)) | + Some(Node::AnonConst(..)) | + Some(Node::Pat(..)) => true, + _ => false + } +} + +struct MarkSymbolVisitor<'a, 'tcx> { + worklist: Vec, + tcx: TyCtxt<'tcx>, + tables: &'a ty::TypeckTables<'tcx>, + live_symbols: FxHashSet, + repr_has_repr_c: bool, + in_pat: bool, + inherited_pub_visibility: bool, + ignore_variant_stack: Vec, + // maps from tuple struct constructors to tuple struct items + struct_constructors: FxHashMap, +} + +impl<'a, 'tcx> MarkSymbolVisitor<'a, 'tcx> { + fn check_def_id(&mut self, def_id: DefId) { + if let Some(hir_id) = self.tcx.hir().as_local_hir_id(def_id) { + if should_explore(self.tcx, hir_id) || self.struct_constructors.contains_key(&hir_id) { + self.worklist.push(hir_id); + } + self.live_symbols.insert(hir_id); + } + } + + fn insert_def_id(&mut self, def_id: DefId) { + if let Some(hir_id) = self.tcx.hir().as_local_hir_id(def_id) { + debug_assert!(!should_explore(self.tcx, hir_id)); + self.live_symbols.insert(hir_id); + } + } + + fn handle_res(&mut self, res: Res) { + match res { + Res::Def(DefKind::Const, _) + | Res::Def(DefKind::AssocConst, _) + | Res::Def(DefKind::TyAlias, _) => { + self.check_def_id(res.def_id()); + } + _ if self.in_pat => {}, + Res::PrimTy(..) | Res::SelfCtor(..) | + Res::Local(..) => {} + Res::Def(DefKind::Ctor(CtorOf::Variant, ..), ctor_def_id) => { + let variant_id = self.tcx.parent(ctor_def_id).unwrap(); + let enum_id = self.tcx.parent(variant_id).unwrap(); + self.check_def_id(enum_id); + if !self.ignore_variant_stack.contains(&ctor_def_id) { + self.check_def_id(variant_id); + } + } + Res::Def(DefKind::Variant, variant_id) => { + let enum_id = self.tcx.parent(variant_id).unwrap(); + self.check_def_id(enum_id); + if !self.ignore_variant_stack.contains(&variant_id) { + self.check_def_id(variant_id); + } + } + Res::SelfTy(t, i) => { + if let Some(t) = t { + self.check_def_id(t); + } + if let Some(i) = i { + self.check_def_id(i); + } + } + Res::ToolMod | Res::NonMacroAttr(..) | Res::Err => {} + _ => { + self.check_def_id(res.def_id()); + } + } + } + + fn lookup_and_handle_method(&mut self, id: hir::HirId) { + if let Some(def_id) = self.tables.type_dependent_def_id(id) { + self.check_def_id(def_id); + } else { + bug!("no type-dependent def for method"); + } + } + + fn handle_field_access(&mut self, lhs: &hir::Expr, hir_id: hir::HirId) { + match self.tables.expr_ty_adjusted(lhs).kind { + ty::Adt(def, _) => { + let index = self.tcx.field_index(hir_id, self.tables); + self.insert_def_id(def.non_enum_variant().fields[index].did); + } + ty::Tuple(..) => {} + _ => span_bug!(lhs.span, "named field access on non-ADT"), + } + } + + fn handle_field_pattern_match(&mut self, lhs: &hir::Pat, res: Res, pats: &[hir::FieldPat]) { + let variant = match self.tables.node_type(lhs.hir_id).kind { + ty::Adt(adt, _) => adt.variant_of_res(res), + _ => span_bug!(lhs.span, "non-ADT in struct pattern") + }; + for pat in pats { + if let PatKind::Wild = pat.pat.kind { + continue; + } + let index = self.tcx.field_index(pat.hir_id, self.tables); + self.insert_def_id(variant.fields[index].did); + } + } + + fn mark_live_symbols(&mut self) { + let mut scanned = FxHashSet::default(); + while let Some(id) = self.worklist.pop() { + if !scanned.insert(id) { + continue + } + + // in the case of tuple struct constructors we want to check the item, not the generated + // tuple struct constructor function + let id = self.struct_constructors.get(&id).cloned().unwrap_or(id); + + if let Some(node) = self.tcx.hir().find(id) { + self.live_symbols.insert(id); + self.visit_node(node); + } + } + } + + fn visit_node(&mut self, node: Node<'tcx>) { + let had_repr_c = self.repr_has_repr_c; + self.repr_has_repr_c = false; + let had_inherited_pub_visibility = self.inherited_pub_visibility; + self.inherited_pub_visibility = false; + match node { + Node::Item(item) => { + match item.kind { + hir::ItemKind::Struct(..) | hir::ItemKind::Union(..) => { + let def_id = self.tcx.hir().local_def_id(item.hir_id); + let def = self.tcx.adt_def(def_id); + self.repr_has_repr_c = def.repr.c(); + + intravisit::walk_item(self, &item); + } + hir::ItemKind::Enum(..) => { + self.inherited_pub_visibility = item.vis.node.is_pub(); + + intravisit::walk_item(self, &item); + } + hir::ItemKind::ForeignMod(..) => {} + _ => { + intravisit::walk_item(self, &item); + } + } + } + Node::TraitItem(trait_item) => { + intravisit::walk_trait_item(self, trait_item); + } + Node::ImplItem(impl_item) => { + intravisit::walk_impl_item(self, impl_item); + } + Node::ForeignItem(foreign_item) => { + intravisit::walk_foreign_item(self, &foreign_item); + } + _ => {} + } + self.repr_has_repr_c = had_repr_c; + self.inherited_pub_visibility = had_inherited_pub_visibility; + } + + fn mark_as_used_if_union(&mut self, adt: &ty::AdtDef, fields: &hir::HirVec) { + if adt.is_union() && adt.non_enum_variant().fields.len() > 1 && adt.did.is_local() { + for field in fields { + let index = self.tcx.field_index(field.hir_id, self.tables); + self.insert_def_id(adt.non_enum_variant().fields[index].did); + } + } + } +} + +impl<'a, 'tcx> Visitor<'tcx> for MarkSymbolVisitor<'a, 'tcx> { + fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> { + NestedVisitorMap::None + } + + fn visit_nested_body(&mut self, body: hir::BodyId) { + let old_tables = self.tables; + self.tables = self.tcx.body_tables(body); + let body = self.tcx.hir().body(body); + self.visit_body(body); + self.tables = old_tables; + } + + fn visit_variant_data(&mut self, def: &'tcx hir::VariantData, _: ast::Name, + _: &hir::Generics, _: hir::HirId, _: syntax_pos::Span) { + let has_repr_c = self.repr_has_repr_c; + let inherited_pub_visibility = self.inherited_pub_visibility; + let live_fields = def.fields().iter().filter(|f| { + has_repr_c || inherited_pub_visibility || f.vis.node.is_pub() + }); + self.live_symbols.extend(live_fields.map(|f| f.hir_id)); + + intravisit::walk_struct_def(self, def); + } + + fn visit_expr(&mut self, expr: &'tcx hir::Expr) { + match expr.kind { + hir::ExprKind::Path(ref qpath @ hir::QPath::TypeRelative(..)) => { + let res = self.tables.qpath_res(qpath, expr.hir_id); + self.handle_res(res); + } + hir::ExprKind::MethodCall(..) => { + self.lookup_and_handle_method(expr.hir_id); + } + hir::ExprKind::Field(ref lhs, ..) => { + self.handle_field_access(&lhs, expr.hir_id); + } + hir::ExprKind::Struct(_, ref fields, _) => { + if let ty::Adt(ref adt, _) = self.tables.expr_ty(expr).kind { + self.mark_as_used_if_union(adt, fields); + } + } + _ => () + } + + intravisit::walk_expr(self, expr); + } + + fn visit_arm(&mut self, arm: &'tcx hir::Arm) { + // Inside the body, ignore constructions of variants + // necessary for the pattern to match. Those construction sites + // can't be reached unless the variant is constructed elsewhere. + let len = self.ignore_variant_stack.len(); + self.ignore_variant_stack.extend(arm.pat.necessary_variants()); + intravisit::walk_arm(self, arm); + self.ignore_variant_stack.truncate(len); + } + + fn visit_pat(&mut self, pat: &'tcx hir::Pat) { + match pat.kind { + PatKind::Struct(ref path, ref fields, _) => { + let res = self.tables.qpath_res(path, pat.hir_id); + self.handle_field_pattern_match(pat, res, fields); + } + PatKind::Path(ref qpath) => { + let res = self.tables.qpath_res(qpath, pat.hir_id); + self.handle_res(res); + } + _ => () + } + + self.in_pat = true; + intravisit::walk_pat(self, pat); + self.in_pat = false; + } + + fn visit_path(&mut self, path: &'tcx hir::Path, _: hir::HirId) { + self.handle_res(path.res); + intravisit::walk_path(self, path); + } + + fn visit_ty(&mut self, ty: &'tcx hir::Ty) { + match ty.kind { + TyKind::Def(item_id, _) => { + let item = self.tcx.hir().expect_item(item_id.id); + intravisit::walk_item(self, item); + } + _ => () + } + intravisit::walk_ty(self, ty); + } + + fn visit_anon_const(&mut self, c: &'tcx hir::AnonConst) { + self.live_symbols.insert(c.hir_id); + intravisit::walk_anon_const(self, c); + } +} + +fn has_allow_dead_code_or_lang_attr( + tcx: TyCtxt<'_>, + id: hir::HirId, + attrs: &[ast::Attribute], +) -> bool { + if attr::contains_name(attrs, sym::lang) { + return true; + } + + // Stable attribute for #[lang = "panic_impl"] + if attr::contains_name(attrs, sym::panic_handler) { + return true; + } + + // (To be) stable attribute for #[lang = "oom"] + if attr::contains_name(attrs, sym::alloc_error_handler) { + return true; + } + + let def_id = tcx.hir().local_def_id(id); + let cg_attrs = tcx.codegen_fn_attrs(def_id); + + // #[used], #[no_mangle], #[export_name], etc also keeps the item alive + // forcefully, e.g., for placing it in a specific section. + if cg_attrs.contains_extern_indicator() || + cg_attrs.flags.contains(CodegenFnAttrFlags::USED) { + return true; + } + + tcx.lint_level_at_node(lint::builtin::DEAD_CODE, id).0 == lint::Allow +} + +// This visitor seeds items that +// 1) We want to explicitly consider as live: +// * Item annotated with #[allow(dead_code)] +// - This is done so that if we want to suppress warnings for a +// group of dead functions, we only have to annotate the "root". +// For example, if both `f` and `g` are dead and `f` calls `g`, +// then annotating `f` with `#[allow(dead_code)]` will suppress +// warning for both `f` and `g`. +// * Item annotated with #[lang=".."] +// - This is because lang items are always callable from elsewhere. +// or +// 2) We are not sure to be live or not +// * Implementation of a trait method +struct LifeSeeder<'k, 'tcx> { + worklist: Vec, + krate: &'k hir::Crate, + tcx: TyCtxt<'tcx>, + // see `MarkSymbolVisitor::struct_constructors` + struct_constructors: FxHashMap, +} + +impl<'v, 'k, 'tcx> ItemLikeVisitor<'v> for LifeSeeder<'k, 'tcx> { + fn visit_item(&mut self, item: &hir::Item) { + let allow_dead_code = has_allow_dead_code_or_lang_attr(self.tcx, + item.hir_id, + &item.attrs); + if allow_dead_code { + self.worklist.push(item.hir_id); + } + match item.kind { + hir::ItemKind::Enum(ref enum_def, _) => { + if allow_dead_code { + self.worklist.extend(enum_def.variants.iter().map(|variant| variant.id)); + } + + for variant in &enum_def.variants { + if let Some(ctor_hir_id) = variant.data.ctor_hir_id() { + self.struct_constructors.insert(ctor_hir_id, variant.id); + } + } + } + hir::ItemKind::Trait(.., ref trait_item_refs) => { + for trait_item_ref in trait_item_refs { + let trait_item = self.krate.trait_item(trait_item_ref.id); + match trait_item.kind { + hir::TraitItemKind::Const(_, Some(_)) | + hir::TraitItemKind::Method(_, hir::TraitMethod::Provided(_)) => { + if has_allow_dead_code_or_lang_attr(self.tcx, + trait_item.hir_id, + &trait_item.attrs) { + self.worklist.push(trait_item.hir_id); + } + } + _ => {} + } + } + } + hir::ItemKind::Impl(.., ref opt_trait, _, ref impl_item_refs) => { + for impl_item_ref in impl_item_refs { + let impl_item = self.krate.impl_item(impl_item_ref.id); + if opt_trait.is_some() || + has_allow_dead_code_or_lang_attr(self.tcx, + impl_item.hir_id, + &impl_item.attrs) { + self.worklist.push(impl_item_ref.id.hir_id); + } + } + } + hir::ItemKind::Struct(ref variant_data, _) => { + if let Some(ctor_hir_id) = variant_data.ctor_hir_id() { + self.struct_constructors.insert(ctor_hir_id, item.hir_id); + } + } + _ => () + } + } + + fn visit_trait_item(&mut self, _item: &hir::TraitItem) { + // ignore: we are handling this in `visit_item` above + } + + fn visit_impl_item(&mut self, _item: &hir::ImplItem) { + // ignore: we are handling this in `visit_item` above + } +} + +fn create_and_seed_worklist<'tcx>( + tcx: TyCtxt<'tcx>, + access_levels: &privacy::AccessLevels, + krate: &hir::Crate, +) -> (Vec, FxHashMap) { + let worklist = access_levels.map.iter().filter_map(|(&id, level)| { + if level >= &privacy::AccessLevel::Reachable { + Some(id) + } else { + None + } + }).chain( + // Seed entry point + tcx.entry_fn(LOCAL_CRATE).map(|(def_id, _)| tcx.hir().as_local_hir_id(def_id).unwrap()) + ).collect::>(); + + // Seed implemented trait items + let mut life_seeder = LifeSeeder { + worklist, + krate, + tcx, + struct_constructors: Default::default(), + }; + krate.visit_all_item_likes(&mut life_seeder); + + (life_seeder.worklist, life_seeder.struct_constructors) +} + +fn find_live<'tcx>( + tcx: TyCtxt<'tcx>, + access_levels: &privacy::AccessLevels, + krate: &hir::Crate, +) -> FxHashSet { + let (worklist, struct_constructors) = create_and_seed_worklist(tcx, access_levels, krate); + let mut symbol_visitor = MarkSymbolVisitor { + worklist, + tcx, + tables: &ty::TypeckTables::empty(None), + live_symbols: Default::default(), + repr_has_repr_c: false, + in_pat: false, + inherited_pub_visibility: false, + ignore_variant_stack: vec![], + struct_constructors, + }; + symbol_visitor.mark_live_symbols(); + symbol_visitor.live_symbols +} + +struct DeadVisitor<'tcx> { + tcx: TyCtxt<'tcx>, + live_symbols: FxHashSet, +} + +impl DeadVisitor<'tcx> { + fn should_warn_about_item(&mut self, item: &hir::Item) -> bool { + let should_warn = match item.kind { + hir::ItemKind::Static(..) + | hir::ItemKind::Const(..) + | hir::ItemKind::Fn(..) + | hir::ItemKind::TyAlias(..) + | hir::ItemKind::Enum(..) + | hir::ItemKind::Struct(..) + | hir::ItemKind::Union(..) => true, + _ => false + }; + should_warn && !self.symbol_is_live(item.hir_id) + } + + fn should_warn_about_field(&mut self, field: &hir::StructField) -> bool { + let field_type = self.tcx.type_of(self.tcx.hir().local_def_id(field.hir_id)); + !field.is_positional() + && !self.symbol_is_live(field.hir_id) + && !field_type.is_phantom_data() + && !has_allow_dead_code_or_lang_attr(self.tcx, field.hir_id, &field.attrs) + } + + fn should_warn_about_variant(&mut self, variant: &hir::Variant) -> bool { + !self.symbol_is_live(variant.id) + && !has_allow_dead_code_or_lang_attr(self.tcx, + variant.id, + &variant.attrs) + } + + fn should_warn_about_foreign_item(&mut self, fi: &hir::ForeignItem) -> bool { + !self.symbol_is_live(fi.hir_id) + && !has_allow_dead_code_or_lang_attr(self.tcx, fi.hir_id, &fi.attrs) + } + + // id := HIR id of an item's definition. + fn symbol_is_live( + &mut self, + id: hir::HirId, + ) -> bool { + if self.live_symbols.contains(&id) { + return true; + } + // If it's a type whose items are live, then it's live, too. + // This is done to handle the case where, for example, the static + // method of a private type is used, but the type itself is never + // called directly. + let def_id = self.tcx.hir().local_def_id(id); + let inherent_impls = self.tcx.inherent_impls(def_id); + for &impl_did in inherent_impls.iter() { + for &item_did in &self.tcx.associated_item_def_ids(impl_did)[..] { + if let Some(item_hir_id) = self.tcx.hir().as_local_hir_id(item_did) { + if self.live_symbols.contains(&item_hir_id) { + return true; + } + } + } + } + false + } + + fn warn_dead_code(&mut self, + id: hir::HirId, + span: syntax_pos::Span, + name: ast::Name, + node_type: &str, + participle: &str) { + if !name.as_str().starts_with("_") { + self.tcx + .lint_hir(lint::builtin::DEAD_CODE, + id, + span, + &format!("{} is never {}: `{}`", + node_type, participle, name)); + } + } +} + +impl Visitor<'tcx> for DeadVisitor<'tcx> { + /// Walk nested items in place so that we don't report dead-code + /// on inner functions when the outer function is already getting + /// an error. We could do this also by checking the parents, but + /// this is how the code is setup and it seems harmless enough. + fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> { + NestedVisitorMap::All(&self.tcx.hir()) + } + + fn visit_item(&mut self, item: &'tcx hir::Item) { + if self.should_warn_about_item(item) { + // For items that have a definition with a signature followed by a + // block, point only at the signature. + let span = match item.kind { + hir::ItemKind::Fn(..) | + hir::ItemKind::Mod(..) | + hir::ItemKind::Enum(..) | + hir::ItemKind::Struct(..) | + hir::ItemKind::Union(..) | + hir::ItemKind::Trait(..) | + hir::ItemKind::Impl(..) => self.tcx.sess.source_map().def_span(item.span), + _ => item.span, + }; + let participle = match item.kind { + hir::ItemKind::Struct(..) => "constructed", // Issue #52325 + _ => "used" + }; + self.warn_dead_code( + item.hir_id, + span, + item.ident.name, + item.kind.descriptive_variant(), + participle, + ); + } else { + // Only continue if we didn't warn + intravisit::walk_item(self, item); + } + } + + fn visit_variant(&mut self, + variant: &'tcx hir::Variant, + g: &'tcx hir::Generics, + id: hir::HirId) { + if self.should_warn_about_variant(&variant) { + self.warn_dead_code(variant.id, variant.span, variant.ident.name, + "variant", "constructed"); + } else { + intravisit::walk_variant(self, variant, g, id); + } + } + + fn visit_foreign_item(&mut self, fi: &'tcx hir::ForeignItem) { + if self.should_warn_about_foreign_item(fi) { + self.warn_dead_code(fi.hir_id, fi.span, fi.ident.name, + fi.kind.descriptive_variant(), "used"); + } + intravisit::walk_foreign_item(self, fi); + } + + fn visit_struct_field(&mut self, field: &'tcx hir::StructField) { + if self.should_warn_about_field(&field) { + self.warn_dead_code(field.hir_id, field.span, field.ident.name, "field", "used"); + } + intravisit::walk_struct_field(self, field); + } + + fn visit_impl_item(&mut self, impl_item: &'tcx hir::ImplItem) { + match impl_item.kind { + hir::ImplItemKind::Const(_, body_id) => { + if !self.symbol_is_live(impl_item.hir_id) { + self.warn_dead_code(impl_item.hir_id, + impl_item.span, + impl_item.ident.name, + "associated const", + "used"); + } + self.visit_nested_body(body_id) + } + hir::ImplItemKind::Method(_, body_id) => { + if !self.symbol_is_live(impl_item.hir_id) { + let span = self.tcx.sess.source_map().def_span(impl_item.span); + self.warn_dead_code(impl_item.hir_id, span, impl_item.ident.name, "method", + "used"); + } + self.visit_nested_body(body_id) + } + hir::ImplItemKind::OpaqueTy(..) | + hir::ImplItemKind::TyAlias(..) => {} + } + } + + // Overwrite so that we don't warn the trait item itself. + fn visit_trait_item(&mut self, trait_item: &'tcx hir::TraitItem) { + match trait_item.kind { + hir::TraitItemKind::Const(_, Some(body_id)) | + hir::TraitItemKind::Method(_, hir::TraitMethod::Provided(body_id)) => { + self.visit_nested_body(body_id) + } + hir::TraitItemKind::Const(_, None) | + hir::TraitItemKind::Method(_, hir::TraitMethod::Required(_)) | + hir::TraitItemKind::Type(..) => {} + } + } +} + +pub fn check_crate(tcx: TyCtxt<'_>) { + let access_levels = &tcx.privacy_access_levels(LOCAL_CRATE); + let krate = tcx.hir().krate(); + let live_symbols = find_live(tcx, access_levels, krate); + let mut visitor = DeadVisitor { + tcx, + live_symbols, + }; + intravisit::walk_crate(&mut visitor, krate); +} diff --git a/src/librustc_passes/lib.rs b/src/librustc_passes/lib.rs index 7aa353cec08..c0b4a317cf9 100644 --- a/src/librustc_passes/lib.rs +++ b/src/librustc_passes/lib.rs @@ -22,6 +22,7 @@ pub mod ast_validation; pub mod hir_stats; pub mod layout_test; pub mod loops; +pub mod dead; mod liveness; pub fn provide(providers: &mut Providers<'_>) { -- cgit 1.4.1-3-g733a5 From 82bfd8eb0dc8edcf7e231b9d998270a745f9a9c4 Mon Sep 17 00:00:00 2001 From: Mark Rousskov Date: Fri, 4 Oct 2019 10:37:40 -0400 Subject: middle::entry -> rustc_passes --- src/librustc/error_codes.rs | 75 -------------- src/librustc/lib.rs | 1 - src/librustc/middle/entry.rs | 202 ------------------------------------- src/librustc_interface/passes.rs | 3 +- src/librustc_passes/entry.rs | 202 +++++++++++++++++++++++++++++++++++++ src/librustc_passes/error_codes.rs | 77 ++++++++++++++ src/librustc_passes/lib.rs | 6 ++ 7 files changed, 286 insertions(+), 280 deletions(-) delete mode 100644 src/librustc/middle/entry.rs create mode 100644 src/librustc_passes/entry.rs diff --git a/src/librustc/error_codes.rs b/src/librustc/error_codes.rs index 968b0b9f2f2..9b04c2db9ff 100644 --- a/src/librustc/error_codes.rs +++ b/src/librustc/error_codes.rs @@ -466,66 +466,6 @@ fn main() { ``` "##, -// This shouldn't really ever trigger since the repeated value error comes first -E0136: r##" -A binary can only have one entry point, and by default that entry point is the -function `main()`. If there are multiple such functions, please rename one. -"##, - -E0137: r##" -More than one function was declared with the `#[main]` attribute. - -Erroneous code example: - -```compile_fail,E0137 -#![feature(main)] - -#[main] -fn foo() {} - -#[main] -fn f() {} // error: multiple functions with a `#[main]` attribute -``` - -This error indicates that the compiler found multiple functions with the -`#[main]` attribute. This is an error because there must be a unique entry -point into a Rust program. Example: - -``` -#![feature(main)] - -#[main] -fn f() {} // ok! -``` -"##, - -E0138: r##" -More than one function was declared with the `#[start]` attribute. - -Erroneous code example: - -```compile_fail,E0138 -#![feature(start)] - -#[start] -fn foo(argc: isize, argv: *const *const u8) -> isize {} - -#[start] -fn f(argc: isize, argv: *const *const u8) -> isize {} -// error: multiple 'start' functions -``` - -This error indicates that the compiler found multiple functions with the -`#[start]` attribute. This is an error because there must be a unique entry -point into a Rust program. Example: - -``` -#![feature(start)] - -#[start] -fn foo(argc: isize, argv: *const *const u8) -> isize { 0 } // ok! -``` -"##, E0139: r##" #### Note: this error code is no longer emitted by the compiler. @@ -1941,21 +1881,6 @@ fn main() { ``` "##, -E0601: r##" -No `main` function was found in a binary crate. To fix this error, add a -`main` function. For example: - -``` -fn main() { - // Your program will start here. - println!("Hello world!"); -} -``` - -If you don't know the basics of Rust, you can go look to the Rust Book to get -started: https://doc.rust-lang.org/book/ -"##, - E0602: r##" An unknown lint was used on the command line. diff --git a/src/librustc/lib.rs b/src/librustc/lib.rs index 46e39bec324..197792eebb3 100644 --- a/src/librustc/lib.rs +++ b/src/librustc/lib.rs @@ -104,7 +104,6 @@ pub mod middle { pub mod cstore; pub mod dependency_format; pub mod diagnostic_items; - pub mod entry; pub mod exported_symbols; pub mod free_region; pub mod intrinsicck; diff --git a/src/librustc/middle/entry.rs b/src/librustc/middle/entry.rs deleted file mode 100644 index 660fe14ba07..00000000000 --- a/src/librustc/middle/entry.rs +++ /dev/null @@ -1,202 +0,0 @@ -use crate::hir::map as hir_map; -use crate::hir::def_id::{CrateNum, CRATE_DEF_INDEX, DefId, LOCAL_CRATE}; -use crate::session::{config, Session}; -use crate::session::config::EntryFnType; -use syntax::attr; -use syntax::entry::EntryPointType; -use syntax::symbol::sym; -use syntax_pos::Span; -use crate::hir::{HirId, Item, ItemKind, ImplItem, TraitItem}; -use crate::hir::itemlikevisit::ItemLikeVisitor; -use crate::ty::TyCtxt; -use crate::ty::query::Providers; - -struct EntryContext<'a, 'tcx> { - session: &'a Session, - - map: &'a hir_map::Map<'tcx>, - - /// The top-level function called `main`. - main_fn: Option<(HirId, Span)>, - - /// The function that has attribute named `main`. - attr_main_fn: Option<(HirId, Span)>, - - /// The function that has the attribute 'start' on it. - start_fn: Option<(HirId, Span)>, - - /// The functions that one might think are `main` but aren't, e.g. - /// main functions not defined at the top level. For diagnostics. - non_main_fns: Vec<(HirId, Span)> , -} - -impl<'a, 'tcx> ItemLikeVisitor<'tcx> for EntryContext<'a, 'tcx> { - fn visit_item(&mut self, item: &'tcx Item) { - let def_id = self.map.local_def_id(item.hir_id); - let def_key = self.map.def_key(def_id); - let at_root = def_key.parent == Some(CRATE_DEF_INDEX); - find_item(item, self, at_root); - } - - fn visit_trait_item(&mut self, _trait_item: &'tcx TraitItem) { - // Entry fn is never a trait item. - } - - fn visit_impl_item(&mut self, _impl_item: &'tcx ImplItem) { - // Entry fn is never a trait item. - } -} - -fn entry_fn(tcx: TyCtxt<'_>, cnum: CrateNum) -> Option<(DefId, EntryFnType)> { - assert_eq!(cnum, LOCAL_CRATE); - - let any_exe = tcx.sess.crate_types.borrow().iter().any(|ty| { - *ty == config::CrateType::Executable - }); - if !any_exe { - // No need to find a main function. - return None; - } - - // If the user wants no main function at all, then stop here. - if attr::contains_name(&tcx.hir().krate().attrs, sym::no_main) { - return None; - } - - let mut ctxt = EntryContext { - session: tcx.sess, - map: tcx.hir(), - main_fn: None, - attr_main_fn: None, - start_fn: None, - non_main_fns: Vec::new(), - }; - - tcx.hir().krate().visit_all_item_likes(&mut ctxt); - - configure_main(tcx, &ctxt) -} - -// Beware, this is duplicated in `libsyntax/entry.rs`, so make sure to keep -// them in sync. -fn entry_point_type(item: &Item, at_root: bool) -> EntryPointType { - match item.kind { - ItemKind::Fn(..) => { - if attr::contains_name(&item.attrs, sym::start) { - EntryPointType::Start - } else if attr::contains_name(&item.attrs, sym::main) { - EntryPointType::MainAttr - } else if item.ident.name == sym::main { - if at_root { - // This is a top-level function so can be `main`. - EntryPointType::MainNamed - } else { - EntryPointType::OtherMain - } - } else { - EntryPointType::None - } - } - _ => EntryPointType::None, - } -} - - -fn find_item(item: &Item, ctxt: &mut EntryContext<'_, '_>, at_root: bool) { - match entry_point_type(item, at_root) { - EntryPointType::MainNamed => { - if ctxt.main_fn.is_none() { - ctxt.main_fn = Some((item.hir_id, item.span)); - } else { - span_err!(ctxt.session, item.span, E0136, - "multiple `main` functions"); - } - }, - EntryPointType::OtherMain => { - ctxt.non_main_fns.push((item.hir_id, item.span)); - }, - EntryPointType::MainAttr => { - if ctxt.attr_main_fn.is_none() { - ctxt.attr_main_fn = Some((item.hir_id, item.span)); - } else { - struct_span_err!(ctxt.session, item.span, E0137, - "multiple functions with a `#[main]` attribute") - .span_label(item.span, "additional `#[main]` function") - .span_label(ctxt.attr_main_fn.unwrap().1, "first `#[main]` function") - .emit(); - } - }, - EntryPointType::Start => { - if ctxt.start_fn.is_none() { - ctxt.start_fn = Some((item.hir_id, item.span)); - } else { - struct_span_err!(ctxt.session, item.span, E0138, "multiple `start` functions") - .span_label(ctxt.start_fn.unwrap().1, "previous `start` function here") - .span_label(item.span, "multiple `start` functions") - .emit(); - } - } - EntryPointType::None => (), - } -} - -fn configure_main(tcx: TyCtxt<'_>, visitor: &EntryContext<'_, '_>) -> Option<(DefId, EntryFnType)> { - if let Some((hir_id, _)) = visitor.start_fn { - Some((tcx.hir().local_def_id(hir_id), EntryFnType::Start)) - } else if let Some((hir_id, _)) = visitor.attr_main_fn { - Some((tcx.hir().local_def_id(hir_id), EntryFnType::Main)) - } else if let Some((hir_id, _)) = visitor.main_fn { - Some((tcx.hir().local_def_id(hir_id), EntryFnType::Main)) - } else { - no_main_err(tcx, visitor); - None - } -} - -fn no_main_err(tcx: TyCtxt<'_>, visitor: &EntryContext<'_, '_>) { - // There is no main function. - let mut err = struct_err!(tcx.sess, E0601, - "`main` function not found in crate `{}`", tcx.crate_name(LOCAL_CRATE)); - let filename = &tcx.sess.local_crate_source_file; - let note = if !visitor.non_main_fns.is_empty() { - for &(_, span) in &visitor.non_main_fns { - err.span_note(span, "here is a function named `main`"); - } - err.note("you have one or more functions named `main` not defined at the crate level"); - err.help("either move the `main` function definitions or attach the `#[main]` attribute \ - to one of them"); - // There were some functions named `main` though. Try to give the user a hint. - format!("the main function must be defined at the crate level{}", - filename.as_ref().map(|f| format!(" (in `{}`)", f.display())).unwrap_or_default()) - } else if let Some(filename) = filename { - format!("consider adding a `main` function to `{}`", filename.display()) - } else { - String::from("consider adding a `main` function at the crate level") - }; - let sp = tcx.hir().krate().span; - // The file may be empty, which leads to the diagnostic machinery not emitting this - // note. This is a relatively simple way to detect that case and emit a span-less - // note instead. - if let Ok(_) = tcx.sess.source_map().lookup_line(sp.lo()) { - err.set_span(sp); - err.span_label(sp, ¬e); - } else { - err.note(¬e); - } - if tcx.sess.teach(&err.get_code().unwrap()) { - err.note("If you don't know the basics of Rust, you can go look to the Rust Book \ - to get started: https://doc.rust-lang.org/book/"); - } - err.emit(); -} - -pub fn find_entry_point(tcx: TyCtxt<'_>) -> Option<(DefId, EntryFnType)> { - tcx.entry_fn(LOCAL_CRATE) -} - -pub fn provide(providers: &mut Providers<'_>) { - *providers = Providers { - entry_fn, - ..*providers - }; -} diff --git a/src/librustc_interface/passes.rs b/src/librustc_interface/passes.rs index 2fa6edb46b1..6d90d1c839f 100644 --- a/src/librustc_interface/passes.rs +++ b/src/librustc_interface/passes.rs @@ -785,7 +785,6 @@ pub fn default_provide(providers: &mut ty::query::Providers<'_>) { rustc_passes::provide(providers); rustc_traits::provide(providers); middle::region::provide(providers); - middle::entry::provide(providers); cstore::provide(providers); lint::provide(providers); rustc_lint::provide(providers); @@ -891,7 +890,7 @@ fn analysis(tcx: TyCtxt<'_>, cnum: CrateNum) -> Result<()> { time(sess, "misc checking 1", || { parallel!({ entry_point = time(sess, "looking for entry point", || { - middle::entry::find_entry_point(tcx) + rustc_passes::entry::find_entry_point(tcx) }); time(sess, "looking for plugin registrar", || { diff --git a/src/librustc_passes/entry.rs b/src/librustc_passes/entry.rs new file mode 100644 index 00000000000..bf68807a0c2 --- /dev/null +++ b/src/librustc_passes/entry.rs @@ -0,0 +1,202 @@ +use rustc::hir::map as hir_map; +use rustc::hir::def_id::{CrateNum, CRATE_DEF_INDEX, DefId, LOCAL_CRATE}; +use rustc::session::{config, Session}; +use rustc::session::config::EntryFnType; +use syntax::attr; +use syntax::entry::EntryPointType; +use syntax::symbol::sym; +use syntax_pos::Span; +use rustc::hir::{HirId, Item, ItemKind, ImplItem, TraitItem}; +use rustc::hir::itemlikevisit::ItemLikeVisitor; +use rustc::ty::TyCtxt; +use rustc::ty::query::Providers; + +struct EntryContext<'a, 'tcx> { + session: &'a Session, + + map: &'a hir_map::Map<'tcx>, + + /// The top-level function called `main`. + main_fn: Option<(HirId, Span)>, + + /// The function that has attribute named `main`. + attr_main_fn: Option<(HirId, Span)>, + + /// The function that has the attribute 'start' on it. + start_fn: Option<(HirId, Span)>, + + /// The functions that one might think are `main` but aren't, e.g. + /// main functions not defined at the top level. For diagnostics. + non_main_fns: Vec<(HirId, Span)> , +} + +impl<'a, 'tcx> ItemLikeVisitor<'tcx> for EntryContext<'a, 'tcx> { + fn visit_item(&mut self, item: &'tcx Item) { + let def_id = self.map.local_def_id(item.hir_id); + let def_key = self.map.def_key(def_id); + let at_root = def_key.parent == Some(CRATE_DEF_INDEX); + find_item(item, self, at_root); + } + + fn visit_trait_item(&mut self, _trait_item: &'tcx TraitItem) { + // Entry fn is never a trait item. + } + + fn visit_impl_item(&mut self, _impl_item: &'tcx ImplItem) { + // Entry fn is never a trait item. + } +} + +fn entry_fn(tcx: TyCtxt<'_>, cnum: CrateNum) -> Option<(DefId, EntryFnType)> { + assert_eq!(cnum, LOCAL_CRATE); + + let any_exe = tcx.sess.crate_types.borrow().iter().any(|ty| { + *ty == config::CrateType::Executable + }); + if !any_exe { + // No need to find a main function. + return None; + } + + // If the user wants no main function at all, then stop here. + if attr::contains_name(&tcx.hir().krate().attrs, sym::no_main) { + return None; + } + + let mut ctxt = EntryContext { + session: tcx.sess, + map: tcx.hir(), + main_fn: None, + attr_main_fn: None, + start_fn: None, + non_main_fns: Vec::new(), + }; + + tcx.hir().krate().visit_all_item_likes(&mut ctxt); + + configure_main(tcx, &ctxt) +} + +// Beware, this is duplicated in `libsyntax/entry.rs`, so make sure to keep +// them in sync. +fn entry_point_type(item: &Item, at_root: bool) -> EntryPointType { + match item.kind { + ItemKind::Fn(..) => { + if attr::contains_name(&item.attrs, sym::start) { + EntryPointType::Start + } else if attr::contains_name(&item.attrs, sym::main) { + EntryPointType::MainAttr + } else if item.ident.name == sym::main { + if at_root { + // This is a top-level function so can be `main`. + EntryPointType::MainNamed + } else { + EntryPointType::OtherMain + } + } else { + EntryPointType::None + } + } + _ => EntryPointType::None, + } +} + + +fn find_item(item: &Item, ctxt: &mut EntryContext<'_, '_>, at_root: bool) { + match entry_point_type(item, at_root) { + EntryPointType::MainNamed => { + if ctxt.main_fn.is_none() { + ctxt.main_fn = Some((item.hir_id, item.span)); + } else { + span_err!(ctxt.session, item.span, E0136, + "multiple `main` functions"); + } + }, + EntryPointType::OtherMain => { + ctxt.non_main_fns.push((item.hir_id, item.span)); + }, + EntryPointType::MainAttr => { + if ctxt.attr_main_fn.is_none() { + ctxt.attr_main_fn = Some((item.hir_id, item.span)); + } else { + struct_span_err!(ctxt.session, item.span, E0137, + "multiple functions with a `#[main]` attribute") + .span_label(item.span, "additional `#[main]` function") + .span_label(ctxt.attr_main_fn.unwrap().1, "first `#[main]` function") + .emit(); + } + }, + EntryPointType::Start => { + if ctxt.start_fn.is_none() { + ctxt.start_fn = Some((item.hir_id, item.span)); + } else { + struct_span_err!(ctxt.session, item.span, E0138, "multiple `start` functions") + .span_label(ctxt.start_fn.unwrap().1, "previous `start` function here") + .span_label(item.span, "multiple `start` functions") + .emit(); + } + } + EntryPointType::None => (), + } +} + +fn configure_main(tcx: TyCtxt<'_>, visitor: &EntryContext<'_, '_>) -> Option<(DefId, EntryFnType)> { + if let Some((hir_id, _)) = visitor.start_fn { + Some((tcx.hir().local_def_id(hir_id), EntryFnType::Start)) + } else if let Some((hir_id, _)) = visitor.attr_main_fn { + Some((tcx.hir().local_def_id(hir_id), EntryFnType::Main)) + } else if let Some((hir_id, _)) = visitor.main_fn { + Some((tcx.hir().local_def_id(hir_id), EntryFnType::Main)) + } else { + no_main_err(tcx, visitor); + None + } +} + +fn no_main_err(tcx: TyCtxt<'_>, visitor: &EntryContext<'_, '_>) { + // There is no main function. + let mut err = struct_err!(tcx.sess, E0601, + "`main` function not found in crate `{}`", tcx.crate_name(LOCAL_CRATE)); + let filename = &tcx.sess.local_crate_source_file; + let note = if !visitor.non_main_fns.is_empty() { + for &(_, span) in &visitor.non_main_fns { + err.span_note(span, "here is a function named `main`"); + } + err.note("you have one or more functions named `main` not defined at the crate level"); + err.help("either move the `main` function definitions or attach the `#[main]` attribute \ + to one of them"); + // There were some functions named `main` though. Try to give the user a hint. + format!("the main function must be defined at the crate level{}", + filename.as_ref().map(|f| format!(" (in `{}`)", f.display())).unwrap_or_default()) + } else if let Some(filename) = filename { + format!("consider adding a `main` function to `{}`", filename.display()) + } else { + String::from("consider adding a `main` function at the crate level") + }; + let sp = tcx.hir().krate().span; + // The file may be empty, which leads to the diagnostic machinery not emitting this + // note. This is a relatively simple way to detect that case and emit a span-less + // note instead. + if let Ok(_) = tcx.sess.source_map().lookup_line(sp.lo()) { + err.set_span(sp); + err.span_label(sp, ¬e); + } else { + err.note(¬e); + } + if tcx.sess.teach(&err.get_code().unwrap()) { + err.note("If you don't know the basics of Rust, you can go look to the Rust Book \ + to get started: https://doc.rust-lang.org/book/"); + } + err.emit(); +} + +pub fn find_entry_point(tcx: TyCtxt<'_>) -> Option<(DefId, EntryFnType)> { + tcx.entry_fn(LOCAL_CRATE) +} + +pub fn provide(providers: &mut Providers<'_>) { + *providers = Providers { + entry_fn, + ..*providers + }; +} diff --git a/src/librustc_passes/error_codes.rs b/src/librustc_passes/error_codes.rs index af07c790e2a..78260bd8245 100644 --- a/src/librustc_passes/error_codes.rs +++ b/src/librustc_passes/error_codes.rs @@ -319,6 +319,83 @@ async fn foo() {} Switch to the Rust 2018 edition to use `async fn`. "##, + +// This shouldn't really ever trigger since the repeated value error comes first +E0136: r##" +A binary can only have one entry point, and by default that entry point is the +function `main()`. If there are multiple such functions, please rename one. +"##, + +E0137: r##" +More than one function was declared with the `#[main]` attribute. + +Erroneous code example: + +```compile_fail,E0137 +#![feature(main)] + +#[main] +fn foo() {} + +#[main] +fn f() {} // error: multiple functions with a `#[main]` attribute +``` + +This error indicates that the compiler found multiple functions with the +`#[main]` attribute. This is an error because there must be a unique entry +point into a Rust program. Example: + +``` +#![feature(main)] + +#[main] +fn f() {} // ok! +``` +"##, + +E0138: r##" +More than one function was declared with the `#[start]` attribute. + +Erroneous code example: + +```compile_fail,E0138 +#![feature(start)] + +#[start] +fn foo(argc: isize, argv: *const *const u8) -> isize {} + +#[start] +fn f(argc: isize, argv: *const *const u8) -> isize {} +// error: multiple 'start' functions +``` + +This error indicates that the compiler found multiple functions with the +`#[start]` attribute. This is an error because there must be a unique entry +point into a Rust program. Example: + +``` +#![feature(start)] + +#[start] +fn foo(argc: isize, argv: *const *const u8) -> isize { 0 } // ok! +``` +"##, + +E0601: r##" +No `main` function was found in a binary crate. To fix this error, add a +`main` function. For example: + +``` +fn main() { + // Your program will start here. + println!("Hello world!"); +} +``` + +If you don't know the basics of Rust, you can go look to the Rust Book to get +started: https://doc.rust-lang.org/book/ +"##, + ; E0226, // only a single explicit lifetime bound is permitted E0472, // asm! is unsupported on this target diff --git a/src/librustc_passes/lib.rs b/src/librustc_passes/lib.rs index c0b4a317cf9..1000770fb41 100644 --- a/src/librustc_passes/lib.rs +++ b/src/librustc_passes/lib.rs @@ -13,6 +13,10 @@ #[macro_use] extern crate rustc; +#[macro_use] +extern crate log; +#[macro_use] +extern crate syntax; use rustc::ty::query::Providers; @@ -23,9 +27,11 @@ pub mod hir_stats; pub mod layout_test; pub mod loops; pub mod dead; +pub mod entry; mod liveness; pub fn provide(providers: &mut Providers<'_>) { + entry::provide(providers); loops::provide(providers); liveness::provide(providers); } -- cgit 1.4.1-3-g733a5 From 7c3f65b3c4691ff0df270505ebfab89f171c0d28 Mon Sep 17 00:00:00 2001 From: Mark Rousskov Date: Fri, 4 Oct 2019 10:46:57 -0400 Subject: middle::intrinsicck -> rustc_passes --- Cargo.lock | 2 + src/librustc/error_codes.rs | 105 ----------------------- src/librustc/lib.rs | 1 - src/librustc/middle/intrinsicck.rs | 170 ------------------------------------- src/librustc_interface/passes.rs | 1 - src/librustc_passes/Cargo.toml | 2 + src/librustc_passes/error_codes.rs | 105 +++++++++++++++++++++++ src/librustc_passes/intrinsicck.rs | 170 +++++++++++++++++++++++++++++++++++++ src/librustc_passes/lib.rs | 2 + 9 files changed, 281 insertions(+), 277 deletions(-) delete mode 100644 src/librustc/middle/intrinsicck.rs create mode 100644 src/librustc_passes/intrinsicck.rs diff --git a/Cargo.lock b/Cargo.lock index 80364515a7c..512dc5fd887 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -3613,6 +3613,8 @@ dependencies = [ "rustc", "rustc_data_structures", "rustc_errors", + "rustc_index", + "rustc_target", "syntax", "syntax_pos", ] diff --git a/src/librustc/error_codes.rs b/src/librustc/error_codes.rs index 9b04c2db9ff..66c51000066 100644 --- a/src/librustc/error_codes.rs +++ b/src/librustc/error_codes.rs @@ -1566,33 +1566,6 @@ It is not possible to use stability attributes outside of the standard library. Also, for now, it is not possible to write deprecation messages either. "##, -E0512: r##" -Transmute with two differently sized types was attempted. Erroneous code -example: - -```compile_fail,E0512 -fn takes_u8(_: u8) {} - -fn main() { - unsafe { takes_u8(::std::mem::transmute(0u16)); } - // error: cannot transmute between types of different sizes, - // or dependently-sized types -} -``` - -Please use types with same size or use the expected type directly. Example: - -``` -fn takes_u8(_: u8) {} - -fn main() { - unsafe { takes_u8(::std::mem::transmute(0i8)); } // ok! - // or: - unsafe { takes_u8(0u8); } // ok! -} -``` -"##, - E0517: r##" This error indicates that a `#[repr(..)]` attribute was placed on an unsupported item. @@ -1787,84 +1760,6 @@ See [RFC 1522] for more details. [RFC 1522]: https://github.com/rust-lang/rfcs/blob/master/text/1522-conservative-impl-trait.md "##, -E0591: r##" -Per [RFC 401][rfc401], if you have a function declaration `foo`: - -``` -// For the purposes of this explanation, all of these -// different kinds of `fn` declarations are equivalent: -struct S; -fn foo(x: S) { /* ... */ } -# #[cfg(for_demonstration_only)] -extern "C" { fn foo(x: S); } -# #[cfg(for_demonstration_only)] -impl S { fn foo(self) { /* ... */ } } -``` - -the type of `foo` is **not** `fn(S)`, as one might expect. -Rather, it is a unique, zero-sized marker type written here as `typeof(foo)`. -However, `typeof(foo)` can be _coerced_ to a function pointer `fn(S)`, -so you rarely notice this: - -``` -# struct S; -# fn foo(_: S) {} -let x: fn(S) = foo; // OK, coerces -``` - -The reason that this matter is that the type `fn(S)` is not specific to -any particular function: it's a function _pointer_. So calling `x()` results -in a virtual call, whereas `foo()` is statically dispatched, because the type -of `foo` tells us precisely what function is being called. - -As noted above, coercions mean that most code doesn't have to be -concerned with this distinction. However, you can tell the difference -when using **transmute** to convert a fn item into a fn pointer. - -This is sometimes done as part of an FFI: - -```compile_fail,E0591 -extern "C" fn foo(userdata: Box) { - /* ... */ -} - -# fn callback(_: extern "C" fn(*mut i32)) {} -# use std::mem::transmute; -# unsafe { -let f: extern "C" fn(*mut i32) = transmute(foo); -callback(f); -# } -``` - -Here, transmute is being used to convert the types of the fn arguments. -This pattern is incorrect because, because the type of `foo` is a function -**item** (`typeof(foo)`), which is zero-sized, and the target type (`fn()`) -is a function pointer, which is not zero-sized. -This pattern should be rewritten. There are a few possible ways to do this: - -- change the original fn declaration to match the expected signature, - and do the cast in the fn body (the preferred option) -- cast the fn item fo a fn pointer before calling transmute, as shown here: - - ``` - # extern "C" fn foo(_: Box) {} - # use std::mem::transmute; - # unsafe { - let f: extern "C" fn(*mut i32) = transmute(foo as extern "C" fn(_)); - let f: extern "C" fn(*mut i32) = transmute(foo as usize); // works too - # } - ``` - -The same applies to transmutes to `*mut fn()`, which were observed in practice. -Note though that use of this type is generally incorrect. -The intention is typically to describe a function pointer, but just `fn()` -alone suffices for that. `*mut fn()` is a pointer to a fn pointer. -(Since these values are typically just passed to C code, however, this rarely -makes a difference in practice.) - -[rfc401]: https://github.com/rust-lang/rfcs/blob/master/text/0401-coercions.md -"##, - E0593: r##" You tried to supply an `Fn`-based type with an incorrect number of arguments than what was expected. diff --git a/src/librustc/lib.rs b/src/librustc/lib.rs index 197792eebb3..0eea149f30a 100644 --- a/src/librustc/lib.rs +++ b/src/librustc/lib.rs @@ -106,7 +106,6 @@ pub mod middle { pub mod diagnostic_items; pub mod exported_symbols; pub mod free_region; - pub mod intrinsicck; pub mod lib_features; pub mod lang_items; pub mod mem_categorization; diff --git a/src/librustc/middle/intrinsicck.rs b/src/librustc/middle/intrinsicck.rs deleted file mode 100644 index 7b5aea8ac98..00000000000 --- a/src/librustc/middle/intrinsicck.rs +++ /dev/null @@ -1,170 +0,0 @@ -use crate::hir::def::{Res, DefKind}; -use crate::hir::def_id::DefId; -use crate::ty::{self, Ty, TyCtxt}; -use crate::ty::layout::{LayoutError, Pointer, SizeSkeleton, VariantIdx}; -use crate::ty::query::Providers; - -use rustc_target::spec::abi::Abi::RustIntrinsic; -use rustc_index::vec::Idx; -use syntax_pos::{Span, sym}; -use crate::hir::intravisit::{self, Visitor, NestedVisitorMap}; -use crate::hir; - -fn check_mod_intrinsics(tcx: TyCtxt<'_>, module_def_id: DefId) { - tcx.hir().visit_item_likes_in_module( - module_def_id, - &mut ItemVisitor { tcx }.as_deep_visitor() - ); -} - -pub fn provide(providers: &mut Providers<'_>) { - *providers = Providers { - check_mod_intrinsics, - ..*providers - }; -} - -struct ItemVisitor<'tcx> { - tcx: TyCtxt<'tcx>, -} - -struct ExprVisitor<'tcx> { - tcx: TyCtxt<'tcx>, - tables: &'tcx ty::TypeckTables<'tcx>, - param_env: ty::ParamEnv<'tcx>, -} - -/// If the type is `Option`, it will return `T`, otherwise -/// the type itself. Works on most `Option`-like types. -fn unpack_option_like<'tcx>(tcx: TyCtxt<'tcx>, ty: Ty<'tcx>) -> Ty<'tcx> { - let (def, substs) = match ty.kind { - ty::Adt(def, substs) => (def, substs), - _ => return ty - }; - - if def.variants.len() == 2 && !def.repr.c() && def.repr.int.is_none() { - let data_idx; - - let one = VariantIdx::new(1); - let zero = VariantIdx::new(0); - - if def.variants[zero].fields.is_empty() { - data_idx = one; - } else if def.variants[one].fields.is_empty() { - data_idx = zero; - } else { - return ty; - } - - if def.variants[data_idx].fields.len() == 1 { - return def.variants[data_idx].fields[0].ty(tcx, substs); - } - } - - ty -} - -impl ExprVisitor<'tcx> { - fn def_id_is_transmute(&self, def_id: DefId) -> bool { - self.tcx.fn_sig(def_id).abi() == RustIntrinsic && - self.tcx.item_name(def_id) == sym::transmute - } - - fn check_transmute(&self, span: Span, from: Ty<'tcx>, to: Ty<'tcx>) { - let sk_from = SizeSkeleton::compute(from, self.tcx, self.param_env); - let sk_to = SizeSkeleton::compute(to, self.tcx, self.param_env); - - // Check for same size using the skeletons. - if let (Ok(sk_from), Ok(sk_to)) = (sk_from, sk_to) { - if sk_from.same_size(sk_to) { - return; - } - - // Special-case transmutting from `typeof(function)` and - // `Option` to present a clearer error. - let from = unpack_option_like(self.tcx, from); - if let (&ty::FnDef(..), SizeSkeleton::Known(size_to)) = (&from.kind, sk_to) { - if size_to == Pointer.size(&self.tcx) { - struct_span_err!(self.tcx.sess, span, E0591, - "can't transmute zero-sized type") - .note(&format!("source type: {}", from)) - .note(&format!("target type: {}", to)) - .help("cast with `as` to a pointer instead") - .emit(); - return; - } - } - } - - // Try to display a sensible error with as much information as possible. - let skeleton_string = |ty: Ty<'tcx>, sk| { - match sk { - Ok(SizeSkeleton::Known(size)) => { - format!("{} bits", size.bits()) - } - Ok(SizeSkeleton::Pointer { tail, .. }) => { - format!("pointer to `{}`", tail) - } - Err(LayoutError::Unknown(bad)) => { - if bad == ty { - "this type does not have a fixed size".to_owned() - } else { - format!("size can vary because of {}", bad) - } - } - Err(err) => err.to_string() - } - }; - - let mut err = struct_span_err!(self.tcx.sess, span, E0512, - "cannot transmute between types of different sizes, \ - or dependently-sized types"); - if from == to { - err.note(&format!("`{}` does not have a fixed size", from)); - } else { - err.note(&format!("source type: `{}` ({})", from, skeleton_string(from, sk_from))) - .note(&format!("target type: `{}` ({})", to, skeleton_string(to, sk_to))); - } - err.emit() - } -} - -impl Visitor<'tcx> for ItemVisitor<'tcx> { - fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> { - NestedVisitorMap::None - } - - fn visit_nested_body(&mut self, body_id: hir::BodyId) { - let owner_def_id = self.tcx.hir().body_owner_def_id(body_id); - let body = self.tcx.hir().body(body_id); - let param_env = self.tcx.param_env(owner_def_id); - let tables = self.tcx.typeck_tables_of(owner_def_id); - ExprVisitor { tcx: self.tcx, param_env, tables }.visit_body(body); - self.visit_body(body); - } -} - -impl Visitor<'tcx> for ExprVisitor<'tcx> { - fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> { - NestedVisitorMap::None - } - - fn visit_expr(&mut self, expr: &'tcx hir::Expr) { - let res = if let hir::ExprKind::Path(ref qpath) = expr.kind { - self.tables.qpath_res(qpath, expr.hir_id) - } else { - Res::Err - }; - if let Res::Def(DefKind::Fn, did) = res { - if self.def_id_is_transmute(did) { - let typ = self.tables.node_type(expr.hir_id); - let sig = typ.fn_sig(self.tcx); - let from = sig.inputs().skip_binder()[0]; - let to = *sig.output().skip_binder(); - self.check_transmute(expr.span, from, to); - } - } - - intravisit::walk_expr(self, expr); - } -} diff --git a/src/librustc_interface/passes.rs b/src/librustc_interface/passes.rs index 6d90d1c839f..870f804ed44 100644 --- a/src/librustc_interface/passes.rs +++ b/src/librustc_interface/passes.rs @@ -780,7 +780,6 @@ pub fn default_provide(providers: &mut ty::query::Providers<'_>) { ty::provide(providers); traits::provide(providers); stability::provide(providers); - middle::intrinsicck::provide(providers); reachable::provide(providers); rustc_passes::provide(providers); rustc_traits::provide(providers); diff --git a/src/librustc_passes/Cargo.toml b/src/librustc_passes/Cargo.toml index 596ec6c19bc..9d29a230314 100644 --- a/src/librustc_passes/Cargo.toml +++ b/src/librustc_passes/Cargo.toml @@ -15,3 +15,5 @@ rustc_data_structures = { path = "../librustc_data_structures" } syntax = { path = "../libsyntax" } syntax_pos = { path = "../libsyntax_pos" } errors = { path = "../librustc_errors", package = "rustc_errors" } +rustc_target = { path = "../librustc_target" } +rustc_index = { path = "../librustc_index" } diff --git a/src/librustc_passes/error_codes.rs b/src/librustc_passes/error_codes.rs index 78260bd8245..1c61eb35497 100644 --- a/src/librustc_passes/error_codes.rs +++ b/src/librustc_passes/error_codes.rs @@ -396,6 +396,111 @@ If you don't know the basics of Rust, you can go look to the Rust Book to get started: https://doc.rust-lang.org/book/ "##, +E0591: r##" +Per [RFC 401][rfc401], if you have a function declaration `foo`: + +``` +// For the purposes of this explanation, all of these +// different kinds of `fn` declarations are equivalent: +struct S; +fn foo(x: S) { /* ... */ } +# #[cfg(for_demonstration_only)] +extern "C" { fn foo(x: S); } +# #[cfg(for_demonstration_only)] +impl S { fn foo(self) { /* ... */ } } +``` + +the type of `foo` is **not** `fn(S)`, as one might expect. +Rather, it is a unique, zero-sized marker type written here as `typeof(foo)`. +However, `typeof(foo)` can be _coerced_ to a function pointer `fn(S)`, +so you rarely notice this: + +``` +# struct S; +# fn foo(_: S) {} +let x: fn(S) = foo; // OK, coerces +``` + +The reason that this matter is that the type `fn(S)` is not specific to +any particular function: it's a function _pointer_. So calling `x()` results +in a virtual call, whereas `foo()` is statically dispatched, because the type +of `foo` tells us precisely what function is being called. + +As noted above, coercions mean that most code doesn't have to be +concerned with this distinction. However, you can tell the difference +when using **transmute** to convert a fn item into a fn pointer. + +This is sometimes done as part of an FFI: + +```compile_fail,E0591 +extern "C" fn foo(userdata: Box) { + /* ... */ +} + +# fn callback(_: extern "C" fn(*mut i32)) {} +# use std::mem::transmute; +# unsafe { +let f: extern "C" fn(*mut i32) = transmute(foo); +callback(f); +# } +``` + +Here, transmute is being used to convert the types of the fn arguments. +This pattern is incorrect because, because the type of `foo` is a function +**item** (`typeof(foo)`), which is zero-sized, and the target type (`fn()`) +is a function pointer, which is not zero-sized. +This pattern should be rewritten. There are a few possible ways to do this: + +- change the original fn declaration to match the expected signature, + and do the cast in the fn body (the preferred option) +- cast the fn item fo a fn pointer before calling transmute, as shown here: + + ``` + # extern "C" fn foo(_: Box) {} + # use std::mem::transmute; + # unsafe { + let f: extern "C" fn(*mut i32) = transmute(foo as extern "C" fn(_)); + let f: extern "C" fn(*mut i32) = transmute(foo as usize); // works too + # } + ``` + +The same applies to transmutes to `*mut fn()`, which were observed in practice. +Note though that use of this type is generally incorrect. +The intention is typically to describe a function pointer, but just `fn()` +alone suffices for that. `*mut fn()` is a pointer to a fn pointer. +(Since these values are typically just passed to C code, however, this rarely +makes a difference in practice.) + +[rfc401]: https://github.com/rust-lang/rfcs/blob/master/text/0401-coercions.md +"##, + +E0512: r##" +Transmute with two differently sized types was attempted. Erroneous code +example: + +```compile_fail,E0512 +fn takes_u8(_: u8) {} + +fn main() { + unsafe { takes_u8(::std::mem::transmute(0u16)); } + // error: cannot transmute between types of different sizes, + // or dependently-sized types +} +``` + +Please use types with same size or use the expected type directly. Example: + +``` +fn takes_u8(_: u8) {} + +fn main() { + unsafe { takes_u8(::std::mem::transmute(0i8)); } // ok! + // or: + unsafe { takes_u8(0u8); } // ok! +} +``` +"##, + ; E0226, // only a single explicit lifetime bound is permitted E0472, // asm! is unsupported on this target diff --git a/src/librustc_passes/intrinsicck.rs b/src/librustc_passes/intrinsicck.rs new file mode 100644 index 00000000000..91a7e9f5d7f --- /dev/null +++ b/src/librustc_passes/intrinsicck.rs @@ -0,0 +1,170 @@ +use rustc::hir::def::{Res, DefKind}; +use rustc::hir::def_id::DefId; +use rustc::ty::{self, Ty, TyCtxt}; +use rustc::ty::layout::{LayoutError, Pointer, SizeSkeleton, VariantIdx}; +use rustc::ty::query::Providers; + +use rustc_target::spec::abi::Abi::RustIntrinsic; +use rustc_index::vec::Idx; +use syntax_pos::{Span, sym}; +use rustc::hir::intravisit::{self, Visitor, NestedVisitorMap}; +use rustc::hir; + +fn check_mod_intrinsics(tcx: TyCtxt<'_>, module_def_id: DefId) { + tcx.hir().visit_item_likes_in_module( + module_def_id, + &mut ItemVisitor { tcx }.as_deep_visitor() + ); +} + +pub fn provide(providers: &mut Providers<'_>) { + *providers = Providers { + check_mod_intrinsics, + ..*providers + }; +} + +struct ItemVisitor<'tcx> { + tcx: TyCtxt<'tcx>, +} + +struct ExprVisitor<'tcx> { + tcx: TyCtxt<'tcx>, + tables: &'tcx ty::TypeckTables<'tcx>, + param_env: ty::ParamEnv<'tcx>, +} + +/// If the type is `Option`, it will return `T`, otherwise +/// the type itself. Works on most `Option`-like types. +fn unpack_option_like<'tcx>(tcx: TyCtxt<'tcx>, ty: Ty<'tcx>) -> Ty<'tcx> { + let (def, substs) = match ty.kind { + ty::Adt(def, substs) => (def, substs), + _ => return ty + }; + + if def.variants.len() == 2 && !def.repr.c() && def.repr.int.is_none() { + let data_idx; + + let one = VariantIdx::new(1); + let zero = VariantIdx::new(0); + + if def.variants[zero].fields.is_empty() { + data_idx = one; + } else if def.variants[one].fields.is_empty() { + data_idx = zero; + } else { + return ty; + } + + if def.variants[data_idx].fields.len() == 1 { + return def.variants[data_idx].fields[0].ty(tcx, substs); + } + } + + ty +} + +impl ExprVisitor<'tcx> { + fn def_id_is_transmute(&self, def_id: DefId) -> bool { + self.tcx.fn_sig(def_id).abi() == RustIntrinsic && + self.tcx.item_name(def_id) == sym::transmute + } + + fn check_transmute(&self, span: Span, from: Ty<'tcx>, to: Ty<'tcx>) { + let sk_from = SizeSkeleton::compute(from, self.tcx, self.param_env); + let sk_to = SizeSkeleton::compute(to, self.tcx, self.param_env); + + // Check for same size using the skeletons. + if let (Ok(sk_from), Ok(sk_to)) = (sk_from, sk_to) { + if sk_from.same_size(sk_to) { + return; + } + + // Special-case transmutting from `typeof(function)` and + // `Option` to present a clearer error. + let from = unpack_option_like(self.tcx, from); + if let (&ty::FnDef(..), SizeSkeleton::Known(size_to)) = (&from.kind, sk_to) { + if size_to == Pointer.size(&self.tcx) { + struct_span_err!(self.tcx.sess, span, E0591, + "can't transmute zero-sized type") + .note(&format!("source type: {}", from)) + .note(&format!("target type: {}", to)) + .help("cast with `as` to a pointer instead") + .emit(); + return; + } + } + } + + // Try to display a sensible error with as much information as possible. + let skeleton_string = |ty: Ty<'tcx>, sk| { + match sk { + Ok(SizeSkeleton::Known(size)) => { + format!("{} bits", size.bits()) + } + Ok(SizeSkeleton::Pointer { tail, .. }) => { + format!("pointer to `{}`", tail) + } + Err(LayoutError::Unknown(bad)) => { + if bad == ty { + "this type does not have a fixed size".to_owned() + } else { + format!("size can vary because of {}", bad) + } + } + Err(err) => err.to_string() + } + }; + + let mut err = struct_span_err!(self.tcx.sess, span, E0512, + "cannot transmute between types of different sizes, \ + or dependently-sized types"); + if from == to { + err.note(&format!("`{}` does not have a fixed size", from)); + } else { + err.note(&format!("source type: `{}` ({})", from, skeleton_string(from, sk_from))) + .note(&format!("target type: `{}` ({})", to, skeleton_string(to, sk_to))); + } + err.emit() + } +} + +impl Visitor<'tcx> for ItemVisitor<'tcx> { + fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> { + NestedVisitorMap::None + } + + fn visit_nested_body(&mut self, body_id: hir::BodyId) { + let owner_def_id = self.tcx.hir().body_owner_def_id(body_id); + let body = self.tcx.hir().body(body_id); + let param_env = self.tcx.param_env(owner_def_id); + let tables = self.tcx.typeck_tables_of(owner_def_id); + ExprVisitor { tcx: self.tcx, param_env, tables }.visit_body(body); + self.visit_body(body); + } +} + +impl Visitor<'tcx> for ExprVisitor<'tcx> { + fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> { + NestedVisitorMap::None + } + + fn visit_expr(&mut self, expr: &'tcx hir::Expr) { + let res = if let hir::ExprKind::Path(ref qpath) = expr.kind { + self.tables.qpath_res(qpath, expr.hir_id) + } else { + Res::Err + }; + if let Res::Def(DefKind::Fn, did) = res { + if self.def_id_is_transmute(did) { + let typ = self.tables.node_type(expr.hir_id); + let sig = typ.fn_sig(self.tcx); + let from = sig.inputs().skip_binder()[0]; + let to = *sig.output().skip_binder(); + self.check_transmute(expr.span, from, to); + } + } + + intravisit::walk_expr(self, expr); + } +} diff --git a/src/librustc_passes/lib.rs b/src/librustc_passes/lib.rs index 1000770fb41..db59d8e101f 100644 --- a/src/librustc_passes/lib.rs +++ b/src/librustc_passes/lib.rs @@ -29,9 +29,11 @@ pub mod loops; pub mod dead; pub mod entry; mod liveness; +mod intrinsicck; pub fn provide(providers: &mut Providers<'_>) { entry::provide(providers); loops::provide(providers); liveness::provide(providers); + intrinsicck::provide(providers); } -- cgit 1.4.1-3-g733a5