Miri error - Stacked Borrows when implementing doubly linked list

Hi :slight_smile:
When running cargo +nightly miri test I get an error related to Stacked borrows

A link to the offending test:

The output.

10:06:05 bb@f1 tangled-doubly-list ±|master|→ MIRI_BACKTRACE=full cargo +nightly miri test -- --nocapture
Compiling tangled-doubly-list v0.1.0 (/home/bb/projects/foss/tangled-doubly-list)
    Finished test [unoptimized + debuginfo] target(s) in 0.09s
    Running target/x86_64-unknown-linux-gnu/debug/deps/tangled_doubly_list-86bc5cae100c17c4

running 3 tests
test tests::populate_and_delete ... 

An error occurred in miri:
0: <rustc_middle::mir::interpret::error::InterpErrorInfo as core::convert::From<rustc_middle::mir::interpret::error::InterpError>>::from
1: miri::stacked_borrows::Stack::grant
2: miri::stacked_borrows::Stacks::for_each
3: miri::stacked_borrows::EvalContextPrivExt::retag_reference
4: rustc_mir::interpret::step::<impl rustc_mir::interpret::eval_context::InterpCx<M>>::statement
5: miri::eval::eval_main
6: rustc_interface::passes::QueryContext::enter
7: <miri::MiriCompilerCalls as rustc_driver::Callbacks>::after_analysis
8: rustc_interface::queries::<impl rustc_interface::interface::Compiler>::enter
9: rustc_span::with_source_map
10: scoped_tls::ScopedKey<T>::set
11: std::sys_common::backtrace::__rust_begin_short_backtrace
12: core::ops::function::FnOnce::call_once{{vtable.shim}}
13: <alloc::boxed::Box<F> as core::ops::function::FnOnce<A>>::call_once
            at /rustc/25c8c53dd994acb3f4f7c02fe6bb46076393f8b0/library/alloc/src/boxed.rs:1042
    <alloc::boxed::Box<F> as core::ops::function::FnOnce<A>>::call_once
            at /rustc/25c8c53dd994acb3f4f7c02fe6bb46076393f8b0/library/alloc/src/boxed.rs:1042
    std::sys::unix::thread::Thread::new::thread_start
            at /rustc/25c8c53dd994acb3f4f7c02fe6bb46076393f8b0/library/std/src/sys/unix/thread.rs:87
14: start_thread
15: clone

error: Undefined Behavior: trying to reborrow for SharedReadWrite, but parent tag <221362> does not have an appropriate item in the borrow stack
--> src/lib.rs:66:43
    |
66  |         let node = unsafe { Box::from_raw(node) };
    |                                           ^^^^ trying to reborrow for SharedReadWrite, but parent tag <221362> does not have an appropriate item in the borrow stack
    |
    = help: this indicates a potential bug in the program: it performed an invalid operation, but the 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
            
    = note: inside `DoublyLinkedList::<i32>::delete` at src/lib.rs:66:43
note: inside `tests::populate_and_delete` at src/lib.rs:214:9
--> src/lib.rs:214:9
    |
214 |         dll.delete(elements[0]);
    |         ^^^^^^^^^^^^^^^^^^^^^^^
note: inside closure at src/lib.rs:203:5
--> src/lib.rs:203:5
    |
203 | /     fn populate_and_delete() {
204 | |         let mut dll = DoublyLinkedList::<i32>::new();
205 | |         let range = std::ops::Range { start: 0, end: 3 };
206 | |
...   |
216 | |         assert!(dll.is_empty());
217 | |     }
    | |_____^
    = note: inside `<[closure@src/lib.rs:203:5: 217:6] as std::ops::FnOnce<()>>::call_once - shim` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:227:5
    = note: inside `<fn() as std::ops::FnOnce<()>>::call_once - shim(fn())` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:227:5
    = note: inside `tests::test::__rust_begin_short_backtrace::<fn()>` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:516:5
    = note: inside closure at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:507:30
    = note: inside `<[closure@tests::test::run_test::{closure#2}] as std::ops::FnOnce<()>>::call_once - shim(vtable)` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:227:5
    = note: inside `<std::boxed::Box<dyn std::ops::FnOnce() + std::marker::Send> as std::ops::FnOnce<()>>::call_once` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/boxed.rs:1042:9
    = note: inside `<std::panic::AssertUnwindSafe<std::boxed::Box<dyn std::ops::FnOnce() + std::marker::Send>> as std::ops::FnOnce<()>>::call_once` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panic.rs:308:9
    = note: inside `std::panicking::r#try::do_call::<std::panic::AssertUnwindSafe<std::boxed::Box<dyn std::ops::FnOnce() + std::marker::Send>>, ()>` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:381:40
    = note: inside `std::panicking::r#try::<(), std::panic::AssertUnwindSafe<std::boxed::Box<dyn std::ops::FnOnce() + std::marker::Send>>>` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:345:19
    = note: inside `std::panic::catch_unwind::<std::panic::AssertUnwindSafe<std::boxed::Box<dyn std::ops::FnOnce() + std::marker::Send>>, ()>` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panic.rs:382:14
    = note: inside `tests::test::run_test_in_process` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:543:18
    = note: inside closure at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:449:39
    = note: inside `tests::test::run_test::run_test_inner` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:474:13
    = note: inside `tests::test::run_test` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:504:28
    = note: inside `tests::test::run_tests::<[closure@tests::test::run_tests_console::{closure#2}]>` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:283:13
    = note: inside `tests::test::run_tests_console` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/console.rs:280:5
    = note: inside `tests::test::test_main` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:121:15
    = note: inside `tests::test::test_main_static` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:140:5
    = note: inside `main`
    = note: inside `<fn() as std::ops::FnOnce<()>>::call_once - shim(fn())` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:227:5
    = note: inside `std::sys_common::backtrace::__rust_begin_short_backtrace::<fn(), ()>` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/sys_common/backtrace.rs:137:18
    = note: inside closure at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:66: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 /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:259:13
    = note: inside `std::panicking::r#try::do_call::<&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe, i32>` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:381:40
    = note: inside `std::panicking::r#try::<i32, &dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe>` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:345:19
    = note: inside `std::panic::catch_unwind::<&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe, i32>` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panic.rs:382:14
    = note: inside `std::rt::lang_start_internal` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:51:25
    = note: inside `std::rt::lang_start::<()>` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:65:5
    = note: this error originates in an attribute macro (in Nightly builds, run with -Z macro-backtrace for more info)

error: aborting due to previous error

error: test failed, to rerun pass '--lib'

I'd appreciate it if I could get someone to help me understand what's going on.
Thanks for your help!

Hello @blasrodri, and welcome :slightly_smiling_face:

I can't quickly pin-point the root issue with your code, but &mut references, that is, non-aliased references, don't play well with a doubly-linked list, that is, a structure whereby all non-terminal nodes are aliased.

I recommend you use only shared accesses to the nodes (&_), thus relying on Cell to mutate the fields:

  #[derive(Debug)]
  pub struct Node<T> {
      pub elem: T,
-     pub next: Option<NonNull<Node<T>>>,
+     pub next: Cell< Option<NonNull<Node<T>>> >,
-     pub prev: Option<NonNull<Node<T>>>,
+     pub prev: Cell< Option<NonNull<Node<T>>> >,
  }
1 Like

Presumably you've already read Learn Rust With Entirely Too Many Linked Lists. If not, read it without delay, as it builds up to the last part, which is about why it's so hard to implement doubly-linked lists in Rust.

2 Likes

Hi @Yandros! Thanks for the warm welcome.

My concern is that I'd be paying a runtime cost for using Cell, and I wanted to attempt using something that did not. Is that correct?
std has a similar signature than mine. And it doesn't use Cell either. I guess it's sound and does not have UB like mine, though.

1 Like

There is no runtime cost of Cell, only RefCell.

2 Likes

Cell only has a cost if you have to restructure your algorithm around its API limitations: In order to maintain safety, it requires you to move / copy the value out of the cell before doing anything with it.

For a 1-word Copy type like NonNull, this is essentially zero-cost— you’d be doing the same operations on a standard variable anyway.

2 Likes

@Yandros
I've tried following your suggestion here
However, I get the exact same issue with miri.

09:41:45 bb@f1 tangled-doubly-list ±|node-using-cell|→ MIRI_BACKTRACE=full cargo +nightly miri test -- --nocapture
    Finished test [unoptimized + debuginfo] target(s) in 0.00s
     Running target/x86_64-unknown-linux-gnu/debug/deps/tangled_doubly_list-86bc5cae100c17c4

running 3 tests
test tests::populate_and_delete ... 

An error occurred in miri:
   0: <rustc_middle::mir::interpret::error::InterpErrorInfo as core::convert::From<rustc_middle::mir::interpret::error::InterpError>>::from
   1: miri::stacked_borrows::Stack::grant
   2: miri::stacked_borrows::Stacks::for_each
   3: miri::stacked_borrows::EvalContextPrivExt::retag_reference
   4: rustc_mir::interpret::step::<impl rustc_mir::interpret::eval_context::InterpCx<M>>::statement
   5: miri::eval::eval_main
   6: rustc_interface::passes::QueryContext::enter
   7: <miri::MiriCompilerCalls as rustc_driver::Callbacks>::after_analysis
   8: rustc_interface::queries::<impl rustc_interface::interface::Compiler>::enter
   9: rustc_span::with_source_map
  10: scoped_tls::ScopedKey<T>::set
  11: std::sys_common::backtrace::__rust_begin_short_backtrace
  12: core::ops::function::FnOnce::call_once{{vtable.shim}}
  13: <alloc::boxed::Box<F> as core::ops::function::FnOnce<A>>::call_once
             at /rustc/25c8c53dd994acb3f4f7c02fe6bb46076393f8b0/library/alloc/src/boxed.rs:1042
      <alloc::boxed::Box<F> as core::ops::function::FnOnce<A>>::call_once
             at /rustc/25c8c53dd994acb3f4f7c02fe6bb46076393f8b0/library/alloc/src/boxed.rs:1042
      std::sys::unix::thread::Thread::new::thread_start
             at /rustc/25c8c53dd994acb3f4f7c02fe6bb46076393f8b0/library/std/src/sys/unix/thread.rs:87
  14: start_thread
  15: clone

error: Undefined Behavior: trying to reborrow for SharedReadWrite, but parent tag <221462> does not have an appropriate item in the borrow stack
   --> src/lib.rs:65:43
    |
65  |         let node = unsafe { Box::from_raw(node) };
    |                                           ^^^^ trying to reborrow for SharedReadWrite, but parent tag <221462> does not have an appropriate item in the borrow stack
    |
    = help: this indicates a potential bug in the program: it performed an invalid operation, but the 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
            
    = note: inside `DoublyLinkedList::<i32>::delete` at src/lib.rs:65:43
note: inside `tests::populate_and_delete` at src/lib.rs:213:9
   --> src/lib.rs:213:9
    |
213 |         dll.delete(elements[0]);
    |         ^^^^^^^^^^^^^^^^^^^^^^^
note: inside closure at src/lib.rs:202:5
   --> src/lib.rs:202:5
    |
202 | /     fn populate_and_delete() {
203 | |         let mut dll = DoublyLinkedList::<i32>::new();
204 | |         let range = std::ops::Range { start: 0, end: 3 };
205 | |
...   |
215 | |         assert!(dll.is_empty());
216 | |     }
    | |_____^
    = note: inside `<[closure@src/lib.rs:202:5: 216:6] as std::ops::FnOnce<()>>::call_once - shim` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:227:5
    = note: inside `<fn() as std::ops::FnOnce<()>>::call_once - shim(fn())` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:227:5
    = note: inside `tests::test::__rust_begin_short_backtrace::<fn()>` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:516:5
    = note: inside closure at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:507:30
    = note: inside `<[closure@tests::test::run_test::{closure#2}] as std::ops::FnOnce<()>>::call_once - shim(vtable)` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:227:5
    = note: inside `<std::boxed::Box<dyn std::ops::FnOnce() + std::marker::Send> as std::ops::FnOnce<()>>::call_once` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/boxed.rs:1042:9
    = note: inside `<std::panic::AssertUnwindSafe<std::boxed::Box<dyn std::ops::FnOnce() + std::marker::Send>> as std::ops::FnOnce<()>>::call_once` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panic.rs:308:9
    = note: inside `std::panicking::r#try::do_call::<std::panic::AssertUnwindSafe<std::boxed::Box<dyn std::ops::FnOnce() + std::marker::Send>>, ()>` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:381:40
    = note: inside `std::panicking::r#try::<(), std::panic::AssertUnwindSafe<std::boxed::Box<dyn std::ops::FnOnce() + std::marker::Send>>>` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:345:19
    = note: inside `std::panic::catch_unwind::<std::panic::AssertUnwindSafe<std::boxed::Box<dyn std::ops::FnOnce() + std::marker::Send>>, ()>` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panic.rs:382:14
    = note: inside `tests::test::run_test_in_process` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:543:18
    = note: inside closure at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:449:39
    = note: inside `tests::test::run_test::run_test_inner` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:474:13
    = note: inside `tests::test::run_test` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:504:28
    = note: inside `tests::test::run_tests::<[closure@tests::test::run_tests_console::{closure#2}]>` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:283:13
    = note: inside `tests::test::run_tests_console` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/console.rs:280:5
    = note: inside `tests::test::test_main` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:121:15
    = note: inside `tests::test::test_main_static` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:140:5
    = note: inside `main`
    = note: inside `<fn() as std::ops::FnOnce<()>>::call_once - shim(fn())` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:227:5
    = note: inside `std::sys_common::backtrace::__rust_begin_short_backtrace::<fn(), ()>` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/sys_common/backtrace.rs:137:18
    = note: inside closure at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:66: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 /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:259:13
    = note: inside `std::panicking::r#try::do_call::<&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe, i32>` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:381:40
    = note: inside `std::panicking::r#try::<i32, &dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe>` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:345:19
    = note: inside `std::panic::catch_unwind::<&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe, i32>` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panic.rs:382:14
    = note: inside `std::rt::lang_start_internal` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:51:25
    = note: inside `std::rt::lang_start::<()>` at /home/bb/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:65:5
    = note: this error originates in an attribute macro (in Nightly builds, run with -Z macro-backtrace for more info)

error: aborting due to previous error

error: test failed, to rerun pass '--lib'

I don’t know for sure but at a first glance, this part seems buggy

        if self.head.is_none() {
            self.head = node;
            self.tail = node;
        }
        let raw_old_head = self.head;

        self.head = node;
        match raw_old_head {
            None => (),
            Some(mut non_null_node) => unsafe {
                non_null_node.as_mut().prev = node;
            },
        };

        match node {
            None => (),
            Some(mut n) => unsafe {
                n.as_mut().next = raw_old_head;
            },
        };

When head is initially None, then you put node into head and then link node to itself which, I suppose, wreaks havoc when you start deleting the nodes again.


Also, unlike @Yandros, I don’t really understand what is gained by adding Cells here.

BTW, instead of .as_ptr().as_mut().unwrap() you could use simply as_mut(). NonNull has a convenience method for this.

image

Whenever you deal with a non-terminal node, you can no longer have an exclusive access on the node.

That being said, in this case the pointers used are "inert" / raw ones (NonNull), so by virtue of being inert they can be seen as behaving as a &UnsafeCell<Node>, so for this very instance there may not be issues. Still, I find that knowing which pointers are active and which aren't, all while tracking the exclusive-or-not provenance of pointers make playing with &muts be very very dangerous and UB-prone.

Using Cell completely side-steps that problem.

One thing to understand, is that despite their similar names, Cell and RefCell are quite different constructs. The former is what all the other programming languages in the world use (that is, no other programming language has &mut references, only Rust, AFAIK), whereas the latter is indeed a runtime-checked construct for cases where Cell's non-unsafe API is lackluster.

  • An example I like to take is, to try and write the following C++ code in Rust:

    int32_t x = 42;
    auto inc_x = [&] () { x += 1; };
    auto display_x = [&] () { std::cout << x << std::endl; };
    
    display_x();
    inc_x();
    display_x();
    inc_x();
    display_x();
    

    If you try to write it in Rust with the misguided idea that C++'s int32_t & mutable reference is a &mut i32 in Rust, you will see you can't get that code to compile. Indeed, both closures / lambdas are referring to x, thus x is aliased. Thus, by definition, the only accesses possible to x are shared accesses: & _.

    It also happens that inc_x does mutate x, so inc_x needs to capture a shared mutable reference to x. In C++, there is no concept, at the language level, of shared vs. exclusive access, so this difference is invisible there. We just know that inc_x and display_x are not, for instance, thread-safe, so C++ programmers are expected not to run those two closures in parallel.

    In Rust, however, there is a such a difference. To get aliased / shared mutability, one needs to use a shared mutability (also called interior mutability) wrapper type. And Rust being as rigorous as it is, there are different wrappers to express the different guarantees that we want: each wrapper restricts what can be done with such shared mutable references, thus ensuring safety.

    For instance, the unchecked unsynchronized mutation that C-like languages love so much, is safe to use when there is:

    • no "reference re-entrancy" (e.g., iterator invalidation),

    • no parallelism (lack of thread safety)

    To express such semantics for our int32_t & mutable reference from C++ here, Rust offers &Cell<i32>.

    Indeed, the Cell wrapper:

    • is not Sync, thus expressing at the type-level its lack of thread-safety,

    • it only allows a by-value API (.set(), .get(), .replace()), which prevents the "reference re-entrancy" issue.

    By having, at the type-level / compile-time, ruled out the cases where such aliased mutable reference could be misused, Rust is able to allow a non-unsafe and unchecked wrapper for shared mutable references: no need to pay any runtime cost whatsoever!

    use ::core::cell::Cell as Mut; // renamed to better convey the meaning
    
    let x: Mut<i32> = 42.into();
    let inc_x = /* captures `&Mut<i32>` */ || x.set(x.get() + 1);
    let display_x = /* ditto */ || println!("{}",  x.get());
    
    display_x();
    inc_x();
    display_x();
    inc_x();
    display_x();
    

I guess that relates to what I was talking about of "inert pointers" (vs. Rust references which are always "active" (dereferenceable)). But as I mentioned, although it can be done, it is a very dangerous and error-prone thing to do. On top of that, there are places in the standard library where they perform "deliberate UB", since by virtue of it being maintained by a team with very strong ties to the language team, they both get to discuss about what UB is exploited and what isn't yet.

  • That is, if Rust-the-language started exploiting Stacked Borrows UB, then the standard library would have time to adapt, since they are in sync. But a user-provide dlibrary has no such luxury, unless you want to showcase a library that says: "hey, don't compile this with a Rust compiler that is too recent, otherwise the compiler will exploit the UB present in my crate" :smile:
7 Likes

You were right about this. Thanks. It made the miri warning dissapear.