Improve `possible_borrower` by smoelius · Pull Request #9701 · rust-lang/rust-cl...

This PR makes several improvements to clippy_uitls::mir::possible_borrower. These changes benefit both needless_borrow and redundant clone.

1. Use the compiler's MaybeStorageLive analysis

I could spot not functional differences between the one in the compiler and the one in Clippy's repository. So, I removed the latter in favor of the the former.

1. Make PossibleBorrower a dataflow analysis instead of a visitor

The main benefit of this change is that allows possible_borrower to take advantage of statements' relative locations, which is easier to do in an analysis than in a visitor.

This is easier to illustrate with an example, so consider this one:

    fn foo(cx: &LateContext<'_>, lint: &'static Lint) {
        cx.struct_span_lint(lint, rustc_span::Span::default(), "", |diag| diag.note(&String::new()));
        //                                                                          ^
    }

We would like to flag the & pointed to by the ^ for removal. foo's MIR begins like this:

fn span_lint::foo::{closure#0}(_1: [closure@$DIR/needless_borrow.rs:396:68: 396:74], _2: &mut rustc_errors::diagnostic_builder::DiagnosticBuilder<'_, ()>) -> &mut rustc_errors::diagnostic_builder::DiagnosticBuilder<'_, ()> {
    debug diag => _2;                    // in scope 0 at $DIR/needless_borrow.rs:396:69: 396:73
    let mut _0: &mut rustc_errors::diagnostic_builder::DiagnosticBuilder<'_, ()>; // return place in scope 0 at $DIR/needless_borrow.rs:396:75: 396:75
    let mut _3: &mut rustc_errors::diagnostic_builder::DiagnosticBuilder<'_, ()>; // in scope 0 at $DIR/needless_borrow.rs:396:75: 396:100
    let mut _4: &mut rustc_errors::diagnostic_builder::DiagnosticBuilder<'_, ()>; // in scope 0 at $DIR/needless_borrow.rs:396:75: 396:100
    let mut _5: &std::string::String;    // in scope 0 at $DIR/needless_borrow.rs:396:85: 396:99
    let _6: std::string::String;         // in scope 0 at $DIR/needless_borrow.rs:396:86: 396:99

    bb0: {
        StorageLive(_3);                 // scope 0 at $DIR/needless_borrow.rs:396:75: 396:100
        StorageLive(_4);                 // scope 0 at $DIR/needless_borrow.rs:396:75: 396:100
        _4 = &mut (*_2);                 // scope 0 at $DIR/needless_borrow.rs:396:75: 396:100
        StorageLive(_5);                 // scope 0 at $DIR/needless_borrow.rs:396:85: 396:99
        StorageLive(_6);                 // scope 0 at $DIR/needless_borrow.rs:396:86: 396:99
        _6 = std::string::String::new() -> bb1; // scope 0 at $DIR/needless_borrow.rs:396:86: 396:99
                                         // mir::Constant
                                         // + span: $DIR/needless_borrow.rs:396:86: 396:97
                                         // + literal: Const { ty: fn() -> std::string::String {std::string::String::new}, val: Value(<ZST>) }
    }

    bb1: {
        _5 = &_6;                        // scope 0 at $DIR/needless_borrow.rs:396:85: 396:99
        _3 = rustc_errors::diagnostic_builder::DiagnosticBuilder::<'_, ()>::note::<&std::string::String>(move _4, move _5) -> [return: bb2, unwind: bb4]; // scope 0 at $DIR/needless_borrow.rs:396:75: 396:100
                                         // mir::Constant
                                         // + span: $DIR/needless_borrow.rs:396:80: 396:84
                                         // + literal: Const { ty: for<'a> fn(&'a mut rustc_errors::diagnostic_builder::DiagnosticBuilder<'_, ()>, &std::string::String) -> &'a mut rustc_errors::diagnostic_builder::DiagnosticBuilder<'_, ()> {rustc_errors::diagnostic_builder::DiagnosticBuilder::<'_, ()>::note::<&std::string::String>}, val: Value(<ZST>) }
    }

The call to diag.note appears in bb1 on the line beginning with _3 =. The String is owned by _6. So, in the call to diag.note, we would like to know whether there are any references to _6 besides _5.

The old, visitor approach did not consider the relative locations of statements. So all borrows were treated the same, even if they occurred after the location of interest.

For example, before the _3 = ... call, the possible borrowers of _6 would be just _5. But after the call, the possible borrowers would include _2, _3, and _4.

So, in a sense, the call from which we are try to remove the needless borrow is trying to prevent us from removing the needless borrow(!).

With an analysis, things do not get so muddled. We can determine the set of possible borrowers at any specific location, e.g., using a ResultsCursor.

1. Change only_borrowers to at_most_borrowers

possible_borrowers exposed a function only_borrowers that determined whether the borrowers of some local were exactly some set S. But, from what I can tell, this was overkill. For the lints that currently use possible_borrower (needless_borrow and redundant_clone), all we really want to know is whether there are borrowers other than those in S. (Put another way, we only care about the subset relation in one direction.) The new function at_most_borrowers takes this more tailored approach.

1. Compute relations "on the fly" rather than using transitive_relation

The visitor would compute and store the transitive closure of the possible borrower relation for an entire MIR body.

But with an analysis, there is effectively a different possible borrower relation at each location in the body. Computing and storing a transitive closure at each location would not be practical.

So the new approach is to compute the transitive closure on the fly, as needed. But the new approach might actually be more efficient, as I now explain.

In all current uses of at_most_borrowers (previously only_borrowers), the size of the set of borrowers S is at most 2. So you need only check at most three borrowers to determine whether the subset relation holds. That is, once you have found a third borrower, you can stop, since you know the relation cannot hold.

Note that transitive_relation is still used by clippy_uitls::mir::possible_origin (a kind of "subroutine" of possible_borrower).

cc: @Jarcho

changelog: [needless_borrow], [redundant_clone]: Now track references better and detect more cases
#9701