Auto merge of #7346 - lengyijun:redundant_clone_5707, r=oli-obk

fix 5707

changelog: ``[`redundant_clone`]``, fix #5707

# Root problem of #5707 :
```
&2:&mut HashMap = &mut _4;
&3:&str = & _5;
_1 = HashMap::insert(move _2,move _3, _);
```

generate PossibleBorrower(_2,_1) and PossibleBorrower(_3,_1).

However, it misses PossibleBorrower(_3,_2).

# My solution to #5707 :

When meet a function call, we should:
1. build PossibleBorrower between borrow parameters and return value (currently)
2. build PossibleBorrower between immutable borrow parameters and mutable borrow parameters (*add*)
3. build PossibleBorrower inside mutable borrow parameters (*add*)

For example:
```
_2: &mut _22;
_3: &mut _;
_4: & _;
_5: & _;
_1 = call(move _2, move _3, move _4, move _5);
```
we need to build
1. return value with parameter(current implementataion)
 PossibleBorrower(_2,_1)
 PossibleBorrower(_3,_1)
 PossibleBorrower(_4,_1)
 PossibleBorrower(_5,_1)

2. between mutable borrow and immutable borrow
PossibleBorrower(_4,_2)
PossibleBorrower(_5,_2)
PossibleBorrower(_4,_3)
PossibleBorrower(_5,_3)

3. between mutable borrow and mutable borrow
PossibleBorrower(_3,_2)
PossibleBorrower(_2,_3)

  But that's not enough.
 Modification to _2 actually apply to _22.
  So I write a `PossibleBorrowed` visitor, which tracks (borrower => possible borrowed) relation.
  For example (_2 => _22).
  However, a lot of problems exist here.

## Known Problems:
  1. not sure all `&mut`'s origin are collected.
  I'm not sure how to deal with `&mut` when meet a function call, so I didn't do it currently.
  Also, my implement is not flow sensitive, so it's not accurate.

```
foo(_2:&mut _, _3: &_)
```
This pr doesn't count _3 as origin of _2.

 2. introduce false negative
`foo(_2, _3)` will  emit PossibleBorrower(_3,_2) in this pr, but _3 and _2 may not have relation.
Clippy may feel that _3 is still in use because of _2, but actually, _3 is on longer needed and can be moved.

## Insight
  The key problem is determine where every `&mut` come from accurately.
  I think Polonius is an elegant solution to it. Polonius is flow sensitive and accurate.
  But I'm uncertain about whether we can import Polonius in rust-clippy currently.
  This pr actually is part of Polonius' functionality, I think.

# TODO
1. `cargo test` can't pass yet due to similar variable name

4 files changed, 168 insertions, 16 deletions

diff --git a/clippy_lints/src/redundant_clone.rs b/clippy_lints/src/redundant_clone.rs
index 380557c81a1..56ef95a88c8 100644
--- a/clippy_lints/src/redundant_clone.rs
+++ b/clippy_lints/src/redundant_clone.rs
@@ -12,6 +12,7 @@ use rustc_lint::{LateContext, LateLintPass};
 use rustc_middle::mir::{
     self, traversal,
     visit::{MutatingUseContext, NonMutatingUseContext, PlaceContext, Visitor as _},
+    Mutability,
 };
 use rustc_middle::ty::{self, fold::TypeVisitor, Ty};
 use rustc_mir::dataflow::{Analysis, AnalysisDomain, GenKill, GenKillAnalysis, ResultsCursor};
@@ -87,13 +88,18 @@ impl<'tcx> LateLintPass<'tcx> for RedundantClone {
 
         let mir = cx.tcx.optimized_mir(def_id.to_def_id());
 
+        let possible_origin = {
+            let mut vis = PossibleOriginVisitor::new(mir);
+            vis.visit_body(mir);
+            vis.into_map(cx)
+        };
         let maybe_storage_live_result = MaybeStorageLive
             .into_engine(cx.tcx, mir)
             .pass_name("redundant_clone")
             .iterate_to_fixpoint()
             .into_results_cursor(mir);
         let mut possible_borrower = {
-            let mut vis = PossibleBorrowerVisitor::new(cx, mir);
+            let mut vis = PossibleBorrowerVisitor::new(cx, mir, possible_origin);
             vis.visit_body(mir);
             vis.into_map(cx, maybe_storage_live_result)
         };
@@ -509,14 +515,20 @@ struct PossibleBorrowerVisitor<'a, 'tcx> {
     possible_borrower: TransitiveRelation<mir::Local>,
     body: &'a mir::Body<'tcx>,
     cx: &'a LateContext<'tcx>,
+    possible_origin: FxHashMap<mir::Local, HybridBitSet<mir::Local>>,
 }
 
 impl<'a, 'tcx> PossibleBorrowerVisitor<'a, 'tcx> {
-    fn new(cx: &'a LateContext<'tcx>, body: &'a mir::Body<'tcx>) -> Self {
+    fn new(
+        cx: &'a LateContext<'tcx>,
+        body: &'a mir::Body<'tcx>,
+        possible_origin: FxHashMap<mir::Local, HybridBitSet<mir::Local>>,
+    ) -> Self {
         Self {
             possible_borrower: TransitiveRelation::default(),
             cx,
             body,
+            possible_origin,
         }
     }
 
@@ -585,21 +597,105 @@ impl<'a, 'tcx> mir::visit::Visitor<'tcx> for PossibleBorrowerVisitor<'a, 'tcx> {
             ..
         } = &terminator.kind
         {
+            // TODO add doc
             // 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).is_continue() {
-                return;
-            }
+
+            let mut immutable_borrowers = vec![];
+            let mut mutable_borrowers = vec![];
 
             for op in args {
                 match op {
                     mir::Operand::Copy(p) | mir::Operand::Move(p) => {
-                        self.possible_borrower.add(p.local, *dest);
+                        if let ty::Ref(_, _, Mutability::Mut) = self.body.local_decls[p.local].ty.kind() {
+                            mutable_borrowers.push(p.local);
+                        } else {
+                            immutable_borrowers.push(p.local);
+                        }
                     },
                     mir::Operand::Constant(..) => (),
                 }
             }
+
+            let mut mutable_variables: Vec<mir::Local> = mutable_borrowers
+                .iter()
+                .filter_map(|r| self.possible_origin.get(r))
+                .flat_map(HybridBitSet::iter)
+                .collect();
+
+            if ContainsRegion.visit_ty(self.body.local_decls[*dest].ty).is_break() {
+                mutable_variables.push(*dest);
+            }
+
+            for y in mutable_variables {
+                for x in &immutable_borrowers {
+                    self.possible_borrower.add(*x, y);
+                }
+                for x in &mutable_borrowers {
+                    self.possible_borrower.add(*x, y);
+                }
+            }
+        }
+    }
+}
+
+/// Collect possible borrowed for every `&mut` local.
+/// For exampel, `_1 = &mut _2` generate _1: {_2,...}
+/// Known Problems: not sure all borrowed are tracked
+struct PossibleOriginVisitor<'a, 'tcx> {
+    possible_origin: TransitiveRelation<mir::Local>,
+    body: &'a mir::Body<'tcx>,
+}
+
+impl<'a, 'tcx> PossibleOriginVisitor<'a, 'tcx> {
+    fn new(body: &'a mir::Body<'tcx>) -> Self {
+        Self {
+            possible_origin: TransitiveRelation::default(),
+            body,
+        }
+    }
+
+    fn into_map(self, cx: &LateContext<'tcx>) -> FxHashMap<mir::Local, HybridBitSet<mir::Local>> {
+        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_origin.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);
+                }
+            }
+        }
+        map
+    }
+}
+
+impl<'a, 'tcx> mir::visit::Visitor<'tcx> for PossibleOriginVisitor<'a, 'tcx> {
+    fn visit_assign(&mut self, place: &mir::Place<'tcx>, rvalue: &mir::Rvalue<'_>, _location: mir::Location) {
+        let lhs = place.local;
+        match rvalue {
+            // Only consider `&mut`, which can modify origin place
+            mir::Rvalue::Ref(_, rustc_middle::mir::BorrowKind::Mut { .. }, borrowed) |
+            // _2: &mut _;
+            // _3 = move _2
+            mir::Rvalue::Use(mir::Operand::Move(borrowed))  |
+            // _3 = move _2 as &mut _;
+            mir::Rvalue::Cast(_, mir::Operand::Move(borrowed), _)
+                => {
+                self.possible_origin.add(lhs, borrowed.local);
+            },
+            _ => {},
         }
     }
 }
diff --git a/tests/ui/redundant_clone.fixed b/tests/ui/redundant_clone.fixed
index f5da703cd1d..2d711082746 100644
--- a/tests/ui/redundant_clone.fixed
+++ b/tests/ui/redundant_clone.fixed
@@ -55,6 +55,8 @@ fn main() {
     issue_5405();
     manually_drop();
     clone_then_move_cloned();
+    hashmap_neg();
+    false_negative_5707();
 }
 
 #[derive(Clone)]
@@ -206,3 +208,29 @@ fn clone_then_move_cloned() {
     let mut x = S(String::new());
     x.0.clone().chars().for_each(|_| x.m());
 }
+
+fn hashmap_neg() {
+    // issue 5707
+    use std::collections::HashMap;
+    use std::path::PathBuf;
+
+    let p = PathBuf::from("/");
+
+    let mut h: HashMap<&str, &str> = HashMap::new();
+    h.insert("orig-p", p.to_str().unwrap());
+
+    let mut q = p.clone();
+    q.push("foo");
+
+    println!("{:?} {}", h, q.display());
+}
+
+fn false_negative_5707() {
+    fn foo(_x: &Alpha, _y: &mut Alpha) {}
+
+    let x = Alpha;
+    let mut y = Alpha;
+    foo(&x, &mut y);
+    let _z = x.clone(); // pr 7346 can't lint on `x`
+    drop(y);
+}
diff --git a/tests/ui/redundant_clone.rs b/tests/ui/redundant_clone.rs
index fd7f31a1cc5..bd3d7365229 100644
--- a/tests/ui/redundant_clone.rs
+++ b/tests/ui/redundant_clone.rs
@@ -55,6 +55,8 @@ fn main() {
     issue_5405();
     manually_drop();
     clone_then_move_cloned();
+    hashmap_neg();
+    false_negative_5707();
 }
 
 #[derive(Clone)]
@@ -206,3 +208,29 @@ fn clone_then_move_cloned() {
     let mut x = S(String::new());
     x.0.clone().chars().for_each(|_| x.m());
 }
+
+fn hashmap_neg() {
+    // issue 5707
+    use std::collections::HashMap;
+    use std::path::PathBuf;
+
+    let p = PathBuf::from("/");
+
+    let mut h: HashMap<&str, &str> = HashMap::new();
+    h.insert("orig-p", p.to_str().unwrap());
+
+    let mut q = p.clone();
+    q.push("foo");
+
+    println!("{:?} {}", h, q.display());
+}
+
+fn false_negative_5707() {
+    fn foo(_x: &Alpha, _y: &mut Alpha) {}
+
+    let x = Alpha;
+    let mut y = Alpha;
+    foo(&x, &mut y);
+    let _z = x.clone(); // pr 7346 can't lint on `x`
+    drop(y);
+}
diff --git a/tests/ui/redundant_clone.stderr b/tests/ui/redundant_clone.stderr
index 529a6de91e2..fbc90493ae9 100644
--- a/tests/ui/redundant_clone.stderr
+++ b/tests/ui/redundant_clone.stderr
@@ -108,61 +108,61 @@ LL |     let _t = tup.0.clone();
    |              ^^^^^
 
 error: redundant clone
-  --> $DIR/redundant_clone.rs:63:25
+  --> $DIR/redundant_clone.rs:65:25
    |
 LL |     if b { (a.clone(), a.clone()) } else { (Alpha, a) }
    |                         ^^^^^^^^ help: remove this
    |
 note: this value is dropped without further use
-  --> $DIR/redundant_clone.rs:63:24
+  --> $DIR/redundant_clone.rs:65:24
    |
 LL |     if b { (a.clone(), a.clone()) } else { (Alpha, a) }
    |                        ^
 
 error: redundant clone
-  --> $DIR/redundant_clone.rs:120:15
+  --> $DIR/redundant_clone.rs:122:15
    |
 LL |     let _s = s.clone();
    |               ^^^^^^^^ help: remove this
    |
 note: this value is dropped without further use
-  --> $DIR/redundant_clone.rs:120:14
+  --> $DIR/redundant_clone.rs:122:14
    |
 LL |     let _s = s.clone();
    |              ^
 
 error: redundant clone
-  --> $DIR/redundant_clone.rs:121:15
+  --> $DIR/redundant_clone.rs:123:15
    |
 LL |     let _t = t.clone();
    |               ^^^^^^^^ help: remove this
    |
 note: this value is dropped without further use
-  --> $DIR/redundant_clone.rs:121:14
+  --> $DIR/redundant_clone.rs:123:14
    |
 LL |     let _t = t.clone();
    |              ^
 
 error: redundant clone
-  --> $DIR/redundant_clone.rs:131:19
+  --> $DIR/redundant_clone.rs:133:19
    |
 LL |         let _f = f.clone();
    |                   ^^^^^^^^ help: remove this
    |
 note: this value is dropped without further use
-  --> $DIR/redundant_clone.rs:131:18
+  --> $DIR/redundant_clone.rs:133:18
    |
 LL |         let _f = f.clone();
    |                  ^
 
 error: redundant clone
-  --> $DIR/redundant_clone.rs:143:14
+  --> $DIR/redundant_clone.rs:145:14
    |
 LL |     let y = x.clone().join("matthias");
    |              ^^^^^^^^ help: remove this
    |
 note: cloned value is neither consumed nor mutated
-  --> $DIR/redundant_clone.rs:143:13
+  --> $DIR/redundant_clone.rs:145:13
    |
 LL |     let y = x.clone().join("matthias");
    |             ^^^^^^^^^