diff options
Diffstat (limited to 'clippy_lints/src')
| -rw-r--r-- | clippy_lints/src/booleans.rs | 2 | ||||
| -rw-r--r-- | clippy_lints/src/lib.rs | 5 | ||||
| -rw-r--r-- | clippy_lints/src/redundant_clone.rs | 423 |
3 files changed, 346 insertions, 84 deletions
diff --git a/clippy_lints/src/booleans.rs b/clippy_lints/src/booleans.rs index 4309eaa7879..c5da0af6f4d 100644 --- a/clippy_lints/src/booleans.rs +++ b/clippy_lints/src/booleans.rs @@ -343,7 +343,7 @@ impl<'a, 'tcx> NonminimalBoolVisitor<'a, 'tcx> { let stats = terminal_stats(&expr); let mut simplified = expr.simplify(); - for simple in Bool::Not(Box::new(expr.clone())).simplify() { + for simple in Bool::Not(Box::new(expr)).simplify() { match simple { Bool::Not(_) | Bool::True | Bool::False => {}, _ => simplified.push(Bool::Not(Box::new(simple.clone()))), diff --git a/clippy_lints/src/lib.rs b/clippy_lints/src/lib.rs index 10a14f3b906..490f47424b1 100644 --- a/clippy_lints/src/lib.rs +++ b/clippy_lints/src/lib.rs @@ -27,6 +27,8 @@ extern crate rustc_driver; #[allow(unused_extern_crates)] extern crate rustc_errors; #[allow(unused_extern_crates)] +extern crate rustc_index; +#[allow(unused_extern_crates)] extern crate rustc_mir; #[allow(unused_extern_crates)] extern crate rustc_target; @@ -864,6 +866,7 @@ pub fn register_plugins(reg: &mut rustc_driver::plugin::Registry<'_>, conf: &Con ranges::RANGE_MINUS_ONE, ranges::RANGE_PLUS_ONE, ranges::RANGE_ZIP_WITH_LEN, + redundant_clone::REDUNDANT_CLONE, redundant_field_names::REDUNDANT_FIELD_NAMES, redundant_pattern_matching::REDUNDANT_PATTERN_MATCHING, redundant_static_lifetimes::REDUNDANT_STATIC_LIFETIMES, @@ -1169,6 +1172,7 @@ pub fn register_plugins(reg: &mut rustc_driver::plugin::Registry<'_>, conf: &Con methods::SINGLE_CHAR_PATTERN, misc::CMP_OWNED, mutex_atomic::MUTEX_ATOMIC, + redundant_clone::REDUNDANT_CLONE, slow_vector_initialization::SLOW_VECTOR_INITIALIZATION, trivially_copy_pass_by_ref::TRIVIALLY_COPY_PASS_BY_REF, types::BOX_VEC, @@ -1188,7 +1192,6 @@ pub fn register_plugins(reg: &mut rustc_driver::plugin::Registry<'_>, conf: &Con mutex_atomic::MUTEX_INTEGER, needless_borrow::NEEDLESS_BORROW, path_buf_push_overwrite::PATH_BUF_PUSH_OVERWRITE, - redundant_clone::REDUNDANT_CLONE, ]); } diff --git a/clippy_lints/src/redundant_clone.rs b/clippy_lints/src/redundant_clone.rs index 09a55d26424..478ca2e04ff 100644 --- a/clippy_lints/src/redundant_clone.rs +++ b/clippy_lints/src/redundant_clone.rs @@ -9,12 +9,16 @@ use rustc::hir::{def_id, Body, FnDecl, HirId}; use rustc::lint::{LateContext, LateLintPass, LintArray, LintPass}; use rustc::mir::{ self, traversal, - visit::{MutatingUseContext, PlaceContext, Visitor}, - TerminatorKind, + visit::{MutatingUseContext, PlaceContext, Visitor as _}, }; -use rustc::ty::{self, Ty}; +use rustc::ty::{self, fold::TypeVisitor, Ty}; use rustc::{declare_lint_pass, declare_tool_lint}; +use rustc_data_structures::{fx::FxHashMap, transitive_relation::TransitiveRelation}; use rustc_errors::Applicability; +use rustc_index::bit_set::{BitSet, HybridBitSet}; +use rustc_mir::dataflow::{ + do_dataflow, BitDenotation, BottomValue, DataflowResults, DataflowResultsCursor, DebugFormatted, GenKillSet, +}; use std::convert::TryFrom; use syntax::source_map::{BytePos, Span}; @@ -36,17 +40,7 @@ declare_clippy_lint! { /// /// **Known problems:** /// - /// * Suggestions made by this lint could require NLL to be enabled. - /// * False-positive if there is a borrow preventing the value from moving out. - /// - /// ```rust - /// # fn foo(x: String) {} - /// let x = String::new(); - /// - /// let y = &x; - /// - /// foo(x.clone()); // This lint suggests to remove this `clone()` - /// ``` + /// False-negatives: analysis performed by this lint is conservative and limited. /// /// **Example:** /// ```rust @@ -68,7 +62,7 @@ declare_clippy_lint! { /// Path::new("/a/b").join("c").to_path_buf(); /// ``` pub REDUNDANT_CLONE, - nursery, + perf, "`clone()` of an owned value that is going to be dropped immediately" } @@ -88,6 +82,22 @@ impl<'a, 'tcx> LateLintPass<'a, 'tcx> for RedundantClone { let def_id = cx.tcx.hir().body_owner_def_id(body.id()); let mir = cx.tcx.optimized_mir(def_id); + let dead_unwinds = BitSet::new_empty(mir.basic_blocks().len()); + let maybe_storage_live_result = do_dataflow( + cx.tcx, + mir, + def_id, + &[], + &dead_unwinds, + MaybeStorageLive::new(mir), + |bd, p| DebugFormatted::new(&bd.body.local_decls[p]), + ); + let mut possible_borrower = { + let mut vis = PossibleBorrowerVisitor::new(cx, mir); + vis.visit_body(mir); + vis.into_map(cx, maybe_storage_live_result) + }; + for (bb, bbdata) in mir.basic_blocks().iter_enumerated() { let terminator = bbdata.terminator(); @@ -114,29 +124,35 @@ impl<'a, 'tcx> LateLintPass<'a, 'tcx> for RedundantClone { continue; } - // _1 in MIR `{ _2 = &_1; clone(move _2); }` or `{ _2 = _1; to_path_buf(_2); } (from_deref) - // In case of `from_deref`, `arg` is already a reference since it is `deref`ed in the previous - // block. - let (cloned, cannot_move_out) = unwrap_or_continue!(find_stmt_assigns_to( - cx, - mir, - arg, - from_borrow, - bbdata.statements.iter() - )); - - if from_borrow && cannot_move_out { - continue; - } + // `{ cloned = &arg; clone(move cloned); }` or `{ cloned = &arg; to_path_buf(cloned); }` + let (cloned, cannot_move_out) = unwrap_or_continue!(find_stmt_assigns_to(cx, mir, arg, from_borrow, bb)); + + let loc = mir::Location { + block: bb, + statement_index: bbdata.statements.len(), + }; + + // Cloned local + let local = if from_borrow { + // `res = clone(arg)` can be turned into `res = move arg;` + // if `arg` is the only borrow of `cloned` at this point. + + if cannot_move_out || !possible_borrower.only_borrowers(&[arg], cloned, loc) { + continue; + } + + cloned + } else { + // `arg` is a reference as it is `.deref()`ed in the previous block. + // Look into the predecessor block and find out the source of deref. - // _1 in MIR `{ _2 = &_1; _3 = deref(move _2); } -> { _4 = _3; to_path_buf(move _4); }` - let referent = if from_deref { let ps = mir.predecessors_for(bb); if ps.len() != 1 { continue; } let pred_terminator = mir[ps[0]].terminator(); + // receiver of the `deref()` call let pred_arg = if_chain! { if let Some((pred_fn_def_id, pred_arg, pred_arg_ty, Some(res))) = is_call_with_ref_arg(cx, mir, &pred_terminator.kind); @@ -151,21 +167,31 @@ impl<'a, 'tcx> LateLintPass<'a, 'tcx> for RedundantClone { } }; - let (local, cannot_move_out) = unwrap_or_continue!(find_stmt_assigns_to( - cx, - mir, - pred_arg, - true, - mir[ps[0]].statements.iter() - )); - if cannot_move_out { + let (local, cannot_move_out) = + unwrap_or_continue!(find_stmt_assigns_to(cx, mir, pred_arg, true, ps[0])); + let loc = mir::Location { + block: bb, + statement_index: mir.basic_blocks()[bb].statements.len(), + }; + + // This can be turned into `res = move local` if `arg` and `cloned` are not borrowed + // at the last statement: + // + // ``` + // pred_arg = &local; + // cloned = deref(pred_arg); + // arg = &cloned; + // StorageDead(pred_arg); + // res = to_path_buf(cloned); + // ``` + if cannot_move_out || !possible_borrower.only_borrowers(&[arg, cloned], local, loc) { continue; } + local - } else { - cloned }; + // `local` cannot be moved out if it is used later let used_later = traversal::ReversePostorder::new(&mir, bb).skip(1).any(|(tbb, tdata)| { // Give up on loops if tdata.terminator().successors().any(|s| *s == bb) { @@ -173,7 +199,7 @@ impl<'a, 'tcx> LateLintPass<'a, 'tcx> for RedundantClone { } let mut vis = LocalUseVisitor { - local: referent, + local, used_other_than_drop: false, }; vis.visit_basic_block_data(tbb, tdata); @@ -195,13 +221,23 @@ impl<'a, 'tcx> LateLintPass<'a, 'tcx> for RedundantClone { let sugg_span = span.with_lo( span.lo() + BytePos(u32::try_from(dot).unwrap()) ); + let mut app = Applicability::MaybeIncorrect; + + let mut call_snip = &snip[dot + 1..]; + // Machine applicable when `call_snip` looks like `foobar()` + if call_snip.ends_with("()") { + call_snip = call_snip[..call_snip.len()-2].trim(); + if call_snip.as_bytes().iter().all(|b| b.is_ascii_alphabetic() || *b == b'_') { + app = Applicability::MachineApplicable; + } + } span_lint_hir_and_then(cx, REDUNDANT_CLONE, node, sugg_span, "redundant clone", |db| { db.span_suggestion( sugg_span, "remove this", String::new(), - Applicability::MaybeIncorrect, + app, ); db.span_note( span.with_hi(span.lo() + BytePos(u32::try_from(dot).unwrap())), @@ -224,7 +260,7 @@ fn is_call_with_ref_arg<'tcx>( kind: &'tcx mir::TerminatorKind<'tcx>, ) -> Option<(def_id::DefId, mir::Local, Ty<'tcx>, Option<&'tcx mir::Place<'tcx>>)> { if_chain! { - if let TerminatorKind::Call { func, args, destination, .. } = kind; + if let mir::TerminatorKind::Call { func, args, destination, .. } = kind; if args.len() == 1; if let mir::Operand::Move(mir::Place { base: mir::PlaceBase::Local(local), .. }) = &args[0]; if let ty::FnDef(def_id, _) = func.ty(&*mir, cx.tcx).kind; @@ -241,42 +277,35 @@ fn is_call_with_ref_arg<'tcx>( type CannotMoveOut = bool; /// Finds the first `to = (&)from`, and returns -/// ``Some((from, [`true` if `from` cannot be moved out]))``. -fn find_stmt_assigns_to<'a, 'tcx: 'a>( +/// ``Some((from, whether `from` cannot be moved out))``. +fn find_stmt_assigns_to<'tcx>( cx: &LateContext<'_, 'tcx>, mir: &mir::Body<'tcx>, - to: mir::Local, + to_local: mir::Local, by_ref: bool, - stmts: impl DoubleEndedIterator<Item = &'a mir::Statement<'tcx>>, + bb: mir::BasicBlock, ) -> Option<(mir::Local, CannotMoveOut)> { - stmts - .rev() - .find_map(|stmt| { - if let mir::StatementKind::Assign(box ( - mir::Place { - base: mir::PlaceBase::Local(local), - .. - }, - v, - )) = &stmt.kind - { - if *local == to { - return Some(v); - } - } + let rvalue = mir.basic_blocks()[bb].statements.iter().rev().find_map(|stmt| { + if let mir::StatementKind::Assign(box ( + mir::Place { + base: mir::PlaceBase::Local(local), + .. + }, + v, + )) = &stmt.kind + { + return if *local == to_local { Some(v) } else { None }; + } - None - }) - .and_then(|v| { - if by_ref { - if let mir::Rvalue::Ref(_, _, ref place) = v { - return base_local_and_movability(cx, mir, place); - } - } else if let mir::Rvalue::Use(mir::Operand::Copy(ref place)) = v { - return base_local_and_movability(cx, mir, place); - } - None - }) + None + })?; + + match (by_ref, &*rvalue) { + (true, mir::Rvalue::Ref(_, _, place)) | (false, mir::Rvalue::Use(mir::Operand::Copy(place))) => { + base_local_and_movability(cx, mir, place) + }, + _ => None, + } } /// Extracts and returns the undermost base `Local` of given `place`. Returns `place` itself @@ -288,8 +317,6 @@ fn base_local_and_movability<'tcx>( mir: &mir::Body<'tcx>, place: &mir::Place<'tcx>, ) -> Option<(mir::Local, CannotMoveOut)> { - use rustc::mir::Place; - use rustc::mir::PlaceBase; use rustc::mir::PlaceRef; // Dereference. You cannot move things out from a borrowed value. @@ -301,13 +328,15 @@ fn base_local_and_movability<'tcx>( base: place_base, mut projection, } = place.as_ref(); - if let PlaceBase::Local(local) = place_base { + if let mir::PlaceBase::Local(local) = place_base { while let [base @ .., elem] = projection { projection = base; - deref = matches!(elem, mir::ProjectionElem::Deref); - field = !field - && matches!(elem, mir::ProjectionElem::Field(..)) - && has_drop(cx, Place::ty_from(place_base, projection, &mir.local_decls, cx.tcx).ty); + deref |= matches!(elem, mir::ProjectionElem::Deref); + field |= matches!(elem, mir::ProjectionElem::Field(..)) + && has_drop( + cx, + mir::Place::ty_from(place_base, projection, &mir.local_decls, cx.tcx).ty, + ); } Some((*local, deref || field)) @@ -353,3 +382,233 @@ impl<'tcx> mir::visit::Visitor<'tcx> for LocalUseVisitor { } } } + +/// Determines liveness of each local purely based on `StorageLive`/`Dead`. +#[derive(Copy, Clone)] +struct MaybeStorageLive<'a, 'tcx> { + body: &'a mir::Body<'tcx>, +} + +impl<'a, 'tcx> MaybeStorageLive<'a, 'tcx> { + fn new(body: &'a mir::Body<'tcx>) -> Self { + MaybeStorageLive { body } + } +} + +impl<'a, 'tcx> BitDenotation<'tcx> for MaybeStorageLive<'a, 'tcx> { + type Idx = mir::Local; + fn name() -> &'static str { + "maybe_storage_live" + } + fn bits_per_block(&self) -> usize { + self.body.local_decls.len() + } + + fn start_block_effect(&self, on_entry: &mut BitSet<mir::Local>) { + for arg in self.body.args_iter() { + on_entry.insert(arg); + } + } + + fn statement_effect(&self, trans: &mut GenKillSet<mir::Local>, loc: mir::Location) { + let stmt = &self.body[loc.block].statements[loc.statement_index]; + + match stmt.kind { + mir::StatementKind::StorageLive(l) => trans.gen(l), + mir::StatementKind::StorageDead(l) => trans.kill(l), + _ => (), + } + } + + fn terminator_effect(&self, _trans: &mut GenKillSet<mir::Local>, _loc: mir::Location) {} + + fn propagate_call_return( + &self, + _in_out: &mut BitSet<mir::Local>, + _call_bb: mir::BasicBlock, + _dest_bb: mir::BasicBlock, + _dest_place: &mir::Place<'tcx>, + ) { + // Nothing to do when a call returns successfully + } +} + +impl<'a, 'tcx> BottomValue for MaybeStorageLive<'a, 'tcx> { + /// bottom = dead + const BOTTOM_VALUE: bool = false; +} + +/// Collects the possible borrowers of each local. +/// For example, `b = &a; c = &a;` will make `b` and (transitively) `c` +/// possible borrowers of `a`. +struct PossibleBorrowerVisitor<'a, 'tcx> { + possible_borrower: TransitiveRelation<mir::Local>, + body: &'a mir::Body<'tcx>, + cx: &'a LateContext<'a, 'tcx>, +} + +impl<'a, 'tcx> PossibleBorrowerVisitor<'a, 'tcx> { + fn new(cx: &'a LateContext<'a, 'tcx>, body: &'a mir::Body<'tcx>) -> Self { + Self { + possible_borrower: TransitiveRelation::default(), + cx, + body, + } + } + + fn into_map( + self, + cx: &LateContext<'a, 'tcx>, + maybe_live: DataflowResults<'tcx, MaybeStorageLive<'a, 'tcx>>, + ) -> PossibleBorrower<'a, 'tcx> { + let mut map = FxHashMap::default(); + for row in (1..self.body.local_decls.len()).map(mir::Local::from_usize) { + if is_copy(cx, self.body.local_decls[row].ty) { + continue; + } + + let borrowers = self.possible_borrower.reachable_from(&row); + if !borrowers.is_empty() { + let mut bs = HybridBitSet::new_empty(self.body.local_decls.len()); + for &c in borrowers { + if c != mir::Local::from_usize(0) { + bs.insert(c); + } + } + + if !bs.is_empty() { + map.insert(row, bs); + } + } + } + + let bs = BitSet::new_empty(self.body.local_decls.len()); + PossibleBorrower { + map, + maybe_live: DataflowResultsCursor::new(maybe_live, self.body), + bitset: (bs.clone(), bs), + } + } +} + +impl<'a, 'tcx> mir::visit::Visitor<'tcx> for PossibleBorrowerVisitor<'a, 'tcx> { + fn visit_assign(&mut self, place: &mir::Place<'tcx>, rvalue: &mir::Rvalue<'_>, _location: mir::Location) { + if let mir::PlaceBase::Local(lhs) = place.base { + match rvalue { + mir::Rvalue::Ref(_, _, borrowed) => { + if let mir::PlaceBase::Local(borrowed_local) = borrowed.base { + self.possible_borrower.add(borrowed_local, lhs); + } + }, + other => { + if !ContainsRegion.visit_ty(place.ty(&self.body.local_decls, self.cx.tcx).ty) { + return; + } + rvalue_locals(other, |rhs| { + if lhs != rhs { + self.possible_borrower.add(rhs, lhs); + } + }); + }, + } + } + } + + fn visit_terminator(&mut self, terminator: &mir::Terminator<'_>, _loc: mir::Location) { + if let mir::TerminatorKind::Call { + args, + destination: + Some(( + mir::Place { + base: mir::PlaceBase::Local(dest), + .. + }, + _, + )), + .. + } = &terminator.kind + { + // If the call returns something with lifetimes, + // let's conservatively assume the returned value contains lifetime of all the arguments. + // For example, given `let y: Foo<'a> = foo(x)`, `y` is considered to be a possible borrower of `x`. + if !ContainsRegion.visit_ty(&self.body.local_decls[*dest].ty) { + return; + } + + for op in args { + match op { + mir::Operand::Copy(p) | mir::Operand::Move(p) => { + if let mir::PlaceBase::Local(arg) = p.base { + self.possible_borrower.add(arg, *dest); + } + }, + _ => (), + } + } + } + } +} + +struct ContainsRegion; + +impl TypeVisitor<'_> for ContainsRegion { + fn visit_region(&mut self, _: ty::Region<'_>) -> bool { + true + } +} + +fn rvalue_locals(rvalue: &mir::Rvalue<'_>, mut visit: impl FnMut(mir::Local)) { + use rustc::mir::Rvalue::*; + + let mut visit_op = |op: &mir::Operand<'_>| match op { + mir::Operand::Copy(p) | mir::Operand::Move(p) => { + if let mir::PlaceBase::Local(l) = p.base { + visit(l) + } + }, + _ => (), + }; + + match rvalue { + Use(op) | Repeat(op, _) | Cast(_, op, _) | UnaryOp(_, op) => visit_op(op), + Aggregate(_, ops) => ops.iter().for_each(visit_op), + BinaryOp(_, lhs, rhs) | CheckedBinaryOp(_, lhs, rhs) => { + visit_op(lhs); + visit_op(rhs); + }, + _ => (), + } +} + +/// Result of `PossibleBorrowerVisitor`. +struct PossibleBorrower<'a, 'tcx> { + /// Mapping `Local -> its possible borrowers` + map: FxHashMap<mir::Local, HybridBitSet<mir::Local>>, + maybe_live: DataflowResultsCursor<'a, 'tcx, MaybeStorageLive<'a, 'tcx>>, + // Caches to avoid allocation of `BitSet` on every query + bitset: (BitSet<mir::Local>, BitSet<mir::Local>), +} + +impl PossibleBorrower<'_, '_> { + /// Returns true if the set of borrowers of `borrowed` living at `at` matches with `borrowers`. + fn only_borrowers(&mut self, borrowers: &[mir::Local], borrowed: mir::Local, at: mir::Location) -> bool { + self.maybe_live.seek(at); + + self.bitset.0.clear(); + let maybe_live = &mut self.maybe_live; + if let Some(bitset) = self.map.get(&borrowed) { + for b in bitset.iter().filter(move |b| maybe_live.contains(*b)) { + self.bitset.0.insert(b); + } + } else { + return false; + } + + self.bitset.1.clear(); + for b in borrowers { + self.bitset.1.insert(*b); + } + + self.bitset.0 == self.bitset.1 + } +} |