Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Miri doesn't accept same algorithm with ArrayVec::retain while accepting Vec::retain #221

Open
AngelicosPhosphoros opened this issue Jul 16, 2022 · 3 comments

Comments

@AngelicosPhosphoros
Copy link

AngelicosPhosphoros commented Jul 16, 2022

Configuration

arrayvec 0.7.2 default features

>cargo +nightly miri --version --verbose
miri 0.1.0 (cde87d1 2022-07-08)

>rustc +nightly --version --verbose
rustc 1.64.0-nightly (87588a2af 2022-07-13)
binary: rustc
commit-hash: 87588a2afd9ca903366f0deaf84d805f34469384
commit-date: 2022-07-13
host: x86_64-pc-windows-msvc
release: 1.64.0-nightly
LLVM version: 14.0.6

Code:

use arrayvec; // 0.7.2

use arrayvec::ArrayVec;
use std::mem::MaybeUninit;

fn retain_remove_vec(a: &mut Vec<MaybeUninit<String>>){
    let mut i = 0;
    a.retain(|x|{
        let res = if i % 2 == 0 {
            true
        }
        else{
            drop(unsafe{
                x.assume_init_read()
            });
            false
        };
        i += 1;
        res
    })
}

fn retain_remove_arrvec(a: &mut ArrayVec<MaybeUninit<String>, 5>){
    let mut i = 0;
    a.retain(|x|{
        let res = if i % 2 == 0 {
            true
        }
        else{
            drop(unsafe{
                x.assume_init_read()
            });
            false
        };
        i += 1;
        res
    })
}

fn main(){
    let mut v: Vec<_> = "ABCDE".chars()
        .map(|c|c.to_string())
        .map(MaybeUninit::new)
        .collect();
    retain_remove_vec(&mut v);
    v.into_iter().map(|x|unsafe{x.assume_init()}).for_each(drop);
    
    let mut v: ArrayVec<_, 5> = "ABCDE".chars()
        .map(|c|c.to_string())
        .map(MaybeUninit::new)
        .collect();
    retain_remove_arrvec(&mut v);
    v.into_iter().map(|x|unsafe{x.assume_init()}).for_each(drop);
}

Error

Miri output
error: Undefined Behavior: attempting a read access using <12341> at alloc4524[0x30], but that tag does not exist in the borrow stack for this location
    --> <skipped>\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\core\src\intrinsics.rs:2453:9
     |
2453 |         copy_nonoverlapping(src, dst, count)
     |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
     |         |
     |         attempting a read access using <12341> at alloc4524[0x30], but that tag does not exist in the borrow stack for this location
     |         this error occurs as part of an access at alloc4524[0x30..0x48]
     |
     = help: this indicates a potential bug in the program: it performed an invalid operation, but the Stacked Borrows rules it violated are still experimental
     = help: see https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md for further information
help: <12341> was created by a retag at offsets [0x0..0x78]
    --> src\main.rs:25:5
     |
25   | /     a.retain(|x|{
26   | |         let res = if i % 2 == 0 {
27   | |             true
28   | |         }
...    |
36   | |         res
37   | |     })
     | |______^
help: <12341> was later invalidated at offsets [0x0..0x80]
    --> src\main.rs:25:5
     |
25   | /     a.retain(|x|{
26   | |         let res = if i % 2 == 0 {
27   | |             true
28   | |         }
...    |
36   | |         res
37   | |     })
     | |______^
     = note: backtrace:
     = note: inside `std::intrinsics::copy_nonoverlapping::<std::mem::MaybeUninit<std::string::String>>` at <skipped>\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\core\src\intrinsics.rs:2453:9
     = note: inside `arrayvec::ArrayVec::<T, CAP>::retain::process_one::<[closure@src\main.rs:25:14: 25:17], std::mem::MaybeUninit<std::string::String>, 5_usize, true>` at <skipped>\.cargo\registry\src\github.com-1ecc6299db9ec823\arrayvec-0.7.2\src\arrayvec.rs:511:21
     = note: inside `arrayvec::ArrayVec::<std::mem::MaybeUninit<std::string::String>, 5_usize>::retain::<[closure@src\main.rs:25:14: 25:17]>` at <skipped>\.cargo\registry\src\github.com-1ecc6299db9ec823\arrayvec-0.7.2\src\arrayvec.rs:527:13
note: inside `retain_remove_arrvec` at src\main.rs:25:5
    --> src\main.rs:25:5
     |
25   | /     a.retain(|x|{
26   | |         let res = if i % 2 == 0 {
27   | |             true
28   | |         }
...    |
36   | |         res
37   | |     })
     | |______^
note: inside `main` at src\main.rs:52:5
    --> src\main.rs:52:5
     |
52   |     retain_remove_arrvec(&mut v);
     |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
     = note: inside `<fn() as std::ops::FnOnce<()>>::call_once - shim(fn())` at <skipped>\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\core\src\ops\function.rs:248:5
     = note: inside `std::sys_common::backtrace::__rust_begin_short_backtrace::<fn(), ()>` at <skipped>\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\std\src\sys_common\backtrace.rs:122:18
     = note: inside closure at <skipped>\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\std\src\rt.rs:145:18
     = note: inside `std::ops::function::impls::<impl std::ops::FnOnce<()> for &dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe>::call_once` at <skipped>\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\core\src\ops\function.rs:280:13
     = note: inside `std::panicking::r#try::do_call::<&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe, i32>` at <skipped>\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\std\src\panicking.rs:492:40
     = note: inside `std::panicking::r#try::<i32, &dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe>` at <skipped>\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\std\src\panicking.rs:456:19
     = note: inside `std::panic::catch_unwind::<&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe, i32>` at <skipped>\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\std\src\panic.rs:137:14
     = note: inside closure at <skipped>\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\std\src\rt.rs:128:48
     = note: inside `std::panicking::r#try::do_call::<[closure@std::rt::lang_start_internal::{closure#2}], isize>` at <skipped>\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\std\src\panicking.rs:492:40
     = note: inside `std::panicking::r#try::<isize, [closure@std::rt::lang_start_internal::{closure#2}]>` at <skipped>\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\std\src\panicking.rs:456:19
     = note: inside `std::panic::catch_unwind::<[closure@std::rt::lang_start_internal::{closure#2}], isize>` at <skipped>\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\std\src\panic.rs:137:14
     = note: inside `std::rt::lang_start_internal` at <skipped>\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\std\src\rt.rs:128:20
     = note: inside `std::rt::lang_start::<()>` at <skipped>\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\std\src\rt.rs:144:17

error: aborting due to previous error

error: process didn't exit successfully: `<skipped>\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\bin\cargo-miri.exe target\miri\x86_64-pc-windows-msvc\debug\test_miri_isolated.exe` (exit code: 1)

Extra Context

I need such strange iteration when I tried to implement retain_take(&mut self, condition: Predicate, consumer_of_removed: impl FnMut(T)).

@AngelicosPhosphoros
Copy link
Author

The program above should be correct because:

  1. It is guaranteed that retain predicate would invoked exactly once per element and in order from v[0] to v.last().
  2. Elements in vectors are initialized before call to retain.

@AngelicosPhosphoros
Copy link
Author

Btw, I cloned your repo and this test fails as well:
cargo +nightly miri test test_retain

@lincot
Copy link

lincot commented Aug 12, 2024

Seems to run fine on nightly-2024-08-12. If not, try MIRIFLAGS=-Zmiri-tree-borrows.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants