Problem with borrow checker and AddAssign

[sebpuetz]

Hi,

there seems to be a problem with the borrow checker that allows references to exist after the borrowed data has been dropped.

I wrote a wrapper struct for a HashMap that would allow me to add frequencies in a manner similar to the Counter known from Python.

When using the += operator to add two of these structs the borrow checker seems to be unable to detect when borrowed values are dropped. The code compiles allowing invalid pointers.
The compiler rejects the code when .add_assign() is called explicitly.

I tried this code (Playground):

use std::collections::HashMap;
use std::hash::Hash;
use std::ops::AddAssign;

pub fn main() {
    works();
    panics();
}

pub struct Counter<K> {
    map: HashMap<K, usize>,
}

impl<K> AddAssign for Counter<K>
where
    K: Hash + Eq,
{
    fn add_assign(&mut self, rhs: Counter<K>) {
        rhs.map.into_iter().for_each(|(key, val)| {
            let count = self.map.entry(key).or_insert(0);
            *count += val;
        });
    }
}

/// reliably prints correct
pub fn works() {
    let mut acc = Counter{map: HashMap::new()};
    for line in vec!["12345678".to_string(), "12345678".to_string()] {
        let v: Vec<&str> = line.split_whitespace().collect();
        println!("accumulator before add_assign {:?}", acc.map);
        let mut map = HashMap::new();
        for str_ref in v {
            {
                let count = map.entry(str_ref).or_insert(0);
                *count += 1;
            }
        }
        let cnt2 = Counter{map};
        acc += cnt2;
        println!("accumulator after add_assign {:?}", acc.map);
    }
}

/// often times crashes, if not prints invalid strings
pub fn panics() {
    let mut acc = Counter{map: HashMap::new()};
    for line in vec!["123456789".to_string(), "12345678".to_string()] {
        let v: Vec<&str> = line.split_whitespace().collect();
        println!("accumulator before add_assign {:?}", acc.map);
        let mut map = HashMap::new();
        for str_ref in v {
            {
                let count = map.entry(str_ref).or_insert(0);
                *count += 1;
            }
        }
        let cnt2 = Counter{map};
        acc += cnt2;
        println!("accumulator after add_assign {:?}", acc.map);
        // line gets dropped here but references are kept in acc.map
    }
}

I expected to see this happen:
The compiler should reject this code

Instead, this happened:
The program compiles and results in unpredictable behaviour. Sometimes the program panics at runtime, sometimes invalid strings are printed.

Meta

rustc --version --verbose:
rustc 1.26.0 (a775680 2018-05-07)
binary: rustc
commit-hash: a775680
commit-date: 2018-05-07
host: x86_64-unknown-linux-gnu
release: 1.26.0
LLVM version: 6.0

Backtrace:

thread 'main' panicked at 'byte index 3 is not a char boundary; it is inside 'B' (bytes 2..3) of `� B��� `', libcore/str/mod.rs:2252:5
stack backtrace:
  0: std::sys::unix::backtrace::tracing::imp::unwind_backtrace
            at libstd/sys/unix/backtrace/tracing/gcc_s.rs:49
  1: std::sys_common::backtrace::print
            at libstd/sys_common/backtrace.rs:71
            at libstd/sys_common/backtrace.rs:59
  2: std::panicking::default_hook::{{closure}}
            at libstd/panicking.rs:207
  3: std::panicking::default_hook
            at libstd/panicking.rs:223
  4: std::panicking::rust_panic_with_hook
            at libstd/panicking.rs:402
  5: std::panicking::begin_panic_fmt
            at libstd/panicking.rs:349
  6: rust_begin_unwind
            at libstd/panicking.rs:325
  7: core::panicking::panic_fmt
            at libcore/panicking.rs:72
  8: core::str::slice_error_fail
            at libcore/str/mod.rs:0
  9: core::str::traits::<impl core::slice::SliceIndex<str> for core::ops::range::Range<usize>>::index::{{closure}}
            at libcore/str/mod.rs:1915
 10: <str as core::fmt::Debug>::fmt
            at libcore/option.rs:376
            at libcore/str/mod.rs:1915
            at libcore/str/mod.rs:1697
            at libcore/fmt/mod.rs:1818
 11: <&'a T as core::fmt::Debug>::fmt
            at /checkout/src/libcore/fmt/mod.rs:1768
 12: <&'a T as core::fmt::Debug>::fmt
            at /checkout/src/libcore/fmt/mod.rs:1768
 13: core::fmt::builders::DebugMap::entry
            at libcore/fmt/builders.rs:502
            at libcore/result.rs:621
            at libcore/fmt/builders.rs:486
 14: core::fmt::builders::DebugMap::entries
            at /checkout/src/libcore/fmt/builders.rs:520
 15: <std::collections::hash::map::HashMap<K, V, S> as core::fmt::Debug>::fmt
            at /checkout/src/libstd/collections/hash/map.rs:1487
 16: core::fmt::write
            at libcore/fmt/mod.rs:1100
            at libcore/fmt/mod.rs:1047
 17: <std::io::stdio::Stdout as std::io::Write>::write_fmt
            at libstd/io/mod.rs:1169
            at libstd/io/stdio.rs:459
 18: <std::thread::local::LocalKey<T>>::try_with
            at libstd/io/stdio.rs:686
            at libstd/thread/local.rs:290
 19: std::io::stdio::_print
            at libstd/io/stdio.rs:680
            at libstd/io/stdio.rs:701
 20: counter::panics
            at src/main.rs:51
 21: counter::main
            at src/main.rs:7
 22: std::rt::lang_start::{{closure}}
            at /checkout/src/libstd/rt.rs:74
 23: std::panicking::try::do_call
            at libstd/rt.rs:59
            at libstd/panicking.rs:306
 24: __rust_maybe_catch_panic
            at libpanic_unwind/lib.rs:102
 25: std::rt::lang_start_internal
            at libstd/panicking.rs:285
            at libstd/panic.rs:361
            at libstd/rt.rs:58
 26: std::rt::lang_start
            at /checkout/src/libstd/rt.rs:74
 27: main
 28: __libc_start_main
 29: _start

[ishitatsuyuki]

NLL correctly rejects this. https://play.rust-lang.org/?gist=39fef98d3c1259109f71749ec47cf27b&version=nightly&mode=debug&edition=2015

[kennytm]

This is a regression introduced in Rust 1.23.0. On 1.22.0 the example was rejected as:

error[E0597]: `line` does not live long enough
  --> <source>:42:5
   |
30 |         let v: Vec<&str> = line.split_whitespace().collect();
   |                            ---- borrow occurs here
...
42 |     }
   |     ^ `line` dropped here while still borrowed
43 | }
   | - borrowed value needs to live until here
error[E0597]: `line` does not live long enough
  --> <source>:62:5
   |
49 |         let v: Vec<&str> = line.split_whitespace().collect();
   |                            ---- borrow occurs here
...
62 |     }
   |     ^ `line` dropped here while still borrowed
63 | }
   | - borrowed value needs to live until here
error: aborting due to 2 previous errors
Compiler returned: 101

[pnkfelix]

visiting for triage. Assigning to self and marking P-high.

[pnkfelix]

Bisected over the nightlies and narrowed it to the range 8b22e70...2be4cc0

Transcript showing end of bisection:

% rustup default nightly-2017-11-01-x86_64-unknown-linux-gnu
info: using existing install for 'nightly-2017-11-01-x86_64-unknown-linux-gnu'
info: default toolchain set to 'nightly-2017-11-01-x86_64-unknown-linux-gnu'

  nightly-2017-11-01-x86_64-unknown-linux-gnu unchanged - rustc 1.23.0-nightly (8b22e70b2 2017-10-31)

% rustc --version
rustc 1.23.0-nightly (8b22e70b2 2017-10-31)
% rustc issue-52126.rs
error[E0597]: `line` does not live long enough
  --> issue-52126.rs:43:5
   |
30 |         let v: Vec<&str> = line.split_whitespace().collect();
   |                            ---- borrow occurs here
...
43 |     }
   |     ^ `line` dropped here while still borrowed
44 | }
   | - borrowed value needs to live until here

error[E0597]: `line` does not live long enough
  --> issue-52126.rs:63:5
   |
50 |         let v: Vec<&str> = line.split_whitespace().collect();
   |                            ---- borrow occurs here
...
63 |     }
   |     ^ `line` dropped here while still borrowed
64 | }
   | - borrowed value needs to live until here

error: aborting due to 2 previous errors

% rustup default nightly-2017-11-02-x86_64-unknown-linux-gnu
info: using existing install for 'nightly-2017-11-02-x86_64-unknown-linux-gnu'
info: default toolchain set to 'nightly-2017-11-02-x86_64-unknown-linux-gnu'

  nightly-2017-11-02-x86_64-unknown-linux-gnu unchanged - rustc 1.23.0-nightly (2be4cc040 2017-11-01)

% rustc --version
rustc 1.23.0-nightly (2be4cc040 2017-11-01)
% rustc issue-52126.rs
%

---

And here's the log of bors commits during that range of time:

�[33mcommit 2be4cc040211a85b17f21e813ff62351ae4de642�[m
Merge: a3f990dc08 aae3e74e70
Author: bors <bors@rust-lang.org>
Date:   Wed Nov 1 18:14:13 2017 +0000

    Auto merge of #45538 - nikomatsakis:nll-liveness, r=pnkfelix
    
    enable non-lexical lifetimes in the MIR borrow checker
    
    This PR, joint work with @spastorino, fills out the NLL infrastructure and integrates it with the borrow checker. **Don't get too excited:** it includes still a number of hacks (the subtyping code is particularly hacky). However, it *does* kinda' work. =)
    
    The final commit demonstrates this by including a test that -- with both the AST borrowck and MIR borrowck -- reports an error by default. But if you pass `-Znll`, you only get an error from the AST borrowck, demonstrating that the integration succeeds:
    
    ```
    struct MyStruct {
        field: String
    }
    
    fn main() {
        let mut my_struct = MyStruct { field: format!("Hello") };
    
        let value = &my_struct.field;
        if value.is_empty() {
            my_struct.field.push_str("Hello, world!");
            //~^ ERROR cannot borrow (Ast)
        }
    }
    ```

�[33mcommit a3f990dc08437ecf63f5e15e8ec6acb9cbedbc14�[m
Merge: 2f581cf9d6 6faba5bf8d
Author: bors <bors@rust-lang.org>
Date:   Wed Nov 1 14:28:11 2017 +0000

    Auto merge of #45472 - michaelwoerister:incr-comp-caching-base, r=nikomatsakis
    
    incr.comp.: Implement compiler diagnostic persistence.
    
    This PR implements storing and loading diagnostics that the compiler generates and thus allows for emitting warnings during incremental compilation without actually re-evaluating the thing the warning originally came from. It also lays some groundwork for storing and loading type information and MIR in the incr. comp. cache.
    
    ~~It is still work in progress:~~
    - ~~There's still some documentation to be added.~~
    - ~~The way anonymous queries are handled might lead to duplicated emissions of warnings. Not sure if there is a better way or how frequent such duplication would be in practice.~~
    
    Diagnostic message duplication is addressed separately in #45519.
    
    r? @nikomatsakis

�[33mcommit 2f581cf9d692781847bede5d966b098a5d09b5e4�[m
Merge: 740286657a 1a7fb7dc78
Author: bors <bors@rust-lang.org>
Date:   Wed Nov 1 09:40:15 2017 +0000

    Auto merge of #45435 - eddyb:binop-subtype-lhs, r=nikomatsakis
    
    rustc_typeck: use subtyping on the LHS of binops.
    
    Fixes #45425.
    
    r? @nikomatsakis

�[33mcommit 740286657a97770eca193062fd5e127c08c0808c�[m
Merge: 31bbe57c79 028455082e
Author: bors <bors@rust-lang.org>
Date:   Wed Nov 1 07:04:17 2017 +0000

    Auto merge of #45674 - kennytm:rollup, r=kennytm
    
    Rollup of 14 pull requests
    
    - Successful merges: #45450, #45579, #45602, #45619, #45624, #45644, #45646, #45648, #45649, #45650, #45652, #45660, #45664, #45671
    - Failed merges:

�[33mcommit 31bbe57c79112e91d2d8783032231c7e1d22855b�[m
Merge: fc3e12a03c fbf6885fd3
Author: bors <bors@rust-lang.org>
Date:   Wed Nov 1 04:32:15 2017 +0000

    Auto merge of #45267 - oconnor663:rwlock_send, r=alexcrichton
    
    remove the `T: Sync` requirement for `RwLock<T>: Send`
    
    That requirement makes sense for containers like `Arc` that don't
    uniquely own their contents, but `RwLock` is not one of those.
    
    This restriction was added in https://github.com/rust-lang/rust/commit/380d23b5d4b9fb8f5f0ebf178590f61528b2483e, but it's not clear why. @hniksic
    and I [were discussing this on reddit](https://www.reddit.com/r/rust/comments/763o7r/blog_posts_introducing_lockfree_rust_comparing/dobcvbm/). I might be totally wrong about this change being sound, but I'm super curious to find out :)

�[33mcommit fc3e12a03c8d5298ddfac6fb8c14c1b918eb55a8�[m
Merge: f3b900cc3b 6fa521c491
Author: bors <bors@rust-lang.org>
Date:   Wed Nov 1 01:45:58 2017 +0000

    Auto merge of #45187 - GuillaumeGomez:doc-ui-improvement, r=QuietMisdreavus
    
    Improve sidebar rendering and add methods list
    
    I suppose it can be reviewed as is, but this is just the first step of a more global plan.
    
    cc @rust-lang/docs @nical
    
    And a screenshot of course:
    
    <img width="1440" alt="screen shot 2017-10-10 at 23 38 45" src="https://user-images.githubusercontent.com/3050060/31412170-657beaf6-ae14-11e7-9f01-1e562a034595.png">

�[33mcommit f3b900cc3b122c7e9eb78ca28bec18df68791b08�[m
Merge: 8b22e70b2d 4c853adce9
Author: bors <bors@rust-lang.org>
Date:   Tue Oct 31 23:06:37 2017 +0000

    Auto merge of #44764 - nvzqz:master, r=alexcrichton
    
    Implement TryFrom<&[T]> for &[T; N]
    
    There are many cases where a buffer with a static compile-time size is preferred over a slice with a dynamic size. This allows for performing a checked conversion from `&[T]` to `&[T; N]`. This may also lead to compile-time optimizations involving `[T; N]` such as loop unrolling.
    
    This is my first PR to Rust, so I'm not sure if discussion of this change should happen here or does it need its own RFC? I figured these changes would be a subset of #33417.

�[33mcommit 8b22e70b2de5152db3b0c53cfa16eb96b0b9e40e�[m
Merge: 6713736275 b1fd5a7618
Author: bors <bors@rust-lang.org>
Date:   Tue Oct 31 14:56:06 2017 +0000

    Auto merge of #45655 - alexcrichton:mips-less-cgus, r=michaelwoerister
    
    rustbuild: Don't build with ThinLTO on MIPS
    
    Discovered in #45529 it looks like cross-module TLS imports aren't quite working
    today, especially with `hidden` visibility which mostly comes up with multiple
    codegen units. As a result this completely disables compiling with ThinLTO and
    multiple codegen units on MIPS when bootstrapping.
    
    cc #45654, the tracking issue for this

[pnkfelix]

Skimming over the log, here are my initial suspicious looking PRs. (Note that I'm trying to cast my net as broadly as possible.)

• enable non-lexical lifetimes in the MIR borrow checker #45538 just because it touched the borrow checker(s)
• rustc_typeck: use subtyping on the LHS of binops. #45435 because it did something with subtyping on LHS of binops
• Rollup of 14 pull requests #45674 because its a rollup and I need to review its individual commits to determine if one of them is suspect.

(I'm now going to bisect over the aforementioned commit range, using the above list of suspects as a rough set of hints as to which points in the history to inspect first.)

[pnkfelix]

okay, I have now confirmed that this does not reproduce on commit 7402866 but does reproduce on commit 2f581cf

Thus I conclude that this was injected by #45435

[pnkfelix]

cc @eddyb and @nikomatsakis

[pnkfelix]

I might have a (nice small) fix for this.

[pnkfelix]

(this was fixed independently of NLL.)