A few soundness issues / suggestions

[steffahn]

Hi there, interesting little API you have here. It seems this crate works as intended w.r.t. the operational behavior (I suppose you probably have probably already tested it with miri yourself, too.) but there are 2 API soundness issues that you should fix:

I’m looking only at MutCursor now, but wouldn’t be surprised that similar issues might be present in the other versions, too.

1. lifetimes

the only time you can hand out a 'root-lifetime reference to any user code soundly is when the MutCursor is for sure going to be consumed. Otherwise, that lifetime is wrong. So into_mut is correct, top_mut correctly only gives a shorter-lived one; try_map_into_mut correctly requires a higher-order closure (for<'r> …), but advance is incorrect.

let mut x = 1;
let mut c = MutCursor::<_, 1>::new(&mut x);
let mut r1 = None;
c.advance(|r| {
    r1 = Some(r);
    None
});
let mut r2 = None;
c.advance(|r| {
    r2 = Some(r);
    None
});
let [r1, r2]: [&mut i32; 2] = [r1.unwrap(), r2.unwrap()];
// now we have aliasing mutable references!

you should change advance so it works with for<'r> FnOnce(&'r mut T) -> Option<&'r mut T> as well.

(which you can equivalently write as FnOnce(&mut T) -> Option<&mut T>)

2. variance

Your cursor type semantically contains a mutable borrow, and as such T must be invariant. With neither NonNull<T> nor the PhantomData<&'a T>, you will actually achieve this. Instead, you should use PhantomData<&'a mut T>.

let mut dummy = String::new();
let mut dummy_ref = &mut dummy;
let mut c = MutCursor::<_, 1>::new(&mut dummy_ref);
{
    let mut hello = String::from("hello!");
    // covariance allows turning `MutCursor<'a, &'long mut String, 1>` into
    // `MutCursor<'a, &'short mut String, 1>`, where the `'short` lifetime now
    // can be shorter than the original lifetime of `dummy_ref`
    // 
    // (I believe the coercion actually already happens when `c` gets assigned above,
    // but even without that, you could imagine inserting a `let c = c as _;` step
    // that makes this more explicit)
    *c.top_mut() = &mut hello; // this sets `dummy_ref` to point to `hello`
    println!("{}", dummy_ref); // hello!
}
println!("{}", dummy_ref); // <garbage> (use-after-free)

3. thread safety (no issue here, improvement suggestion instead)

you currently (conservatively) require &mut T: Send + Sync for all your Send or Sync implementations of MutCursor. But since MutCursor is giving the same kind of exclusive access that &mut T gives, you can relax the restrictions here. You only need T: Send (equivalent to &mut T: Send) for MutCursor<'_, T, N>: Send; and you only need T: Sync (equivalent to &mut T: Sync) for MutCursor<'_, T, N>: Sync

[steffahn]

Actually looking at MutCursorVec anyways. Seems like it has the same lifetime issue [same idea to fix it]; same improvements for Send/Sync are possible; there is not a variance issue though;

but it does do some questionable handling of the references, as far as miri is concerned (try running the following through miri):

let x = &mut 0;
let mut c = MutCursorVec::new(x);
c.advance(Some);
c.backtrack();
println!("{}", c.top());

error: Undefined Behavior: not granting access to tag <1488> because that would remove [Unique for <1522>] which is strongly protected
   --> /home/frank/.cargo/registry/src/index.crates.io-6f17d22bba15001f/mutcursor-0.2.2/src/mut_cursor_vec.rs:123:39
    |
123 |         self.stack.push(NonNull::from(t_ref));
    |                                       ^^^^^ not granting access to tag <1488> because that would remove [Unique for <1522>] which is strongly protected
    |
    = 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: <1488> was created by a Unique retag at offsets [0x0..0x4]
   --> src/main.rs:5:13
    |
5   | let mut c = MutCursorVec::new(x);
    |             ^^^^^^^^^^^^^^^^^^^^
help: <1522> is this argument
   --> src/main.rs:6:1
    |
6   | c.advance(Some);
    | ^^^^^^^^^^^^^^^
    = note: BACKTRACE (of the first span):
    = note: inside `mutcursor::MutCursorVec::<'_, i32>::push` at /home/frank/.cargo/registry/src/index.crates.io-6f17d22bba15001f/mutcursor-0.2.2/src/mut_cursor_vec.rs:123:39: 123:44
    = note: inside `mutcursor::MutCursorVec::<'_, i32>::advance::<fn(&mut i32) -> std::option::Option<&mut i32> {std::option::Option::<&mut i32>::Some}>` at /home/frank/.cargo/registry/src/index.crates.io-6f17d22bba15001f/mutcursor-0.2.2/src/mut_cursor_vec.rs:85:25: 85:44
note: inside `main`
   --> src/main.rs:6:1
    |
6   | c.advance(Some);
    | ^^^^^^^^^^^^^^^

the issue is that in advance, you first project the top reference into a new one; and then push the old one into the Vec. However, by doing the latter, and "moving around" the old (currently re-borrowed) reference as a true &mut T type value, not a raw pointer, you are already killing its re-borrow, so the pointer in the Vec is already invalid. After backtrack, we can access the invalid pointer.

As an alternative, try the following approach for advance:

first option:

First turn top into some local variable ptr: NonNull<T> (or *mut T, or whatever); then call step_f on a dereference of ptr; on success then, push this ptr to the Vec, and simply overwrite self.top.

second option:

Follow the example of MutCursor and make the top field NonNull<T> to begin with, instead of &'root mut T. That way, you can keep the rest of the code structure unchanged; moving the NonNull<T> to the Vec will not assert any validity.

If you do this, don’t forget PhantomData<&'root mut T> for invariant T.

(third option)

change nothing and help that when Rust semantics settle in the future, your current code will be allowed

[steffahn]

MutCursorRootedVec is a lot more complex API. Probably a lot more possible pitfalls here, because this is offering a full sort of "self-referencing struct" API surface. Kind of a generalization of owning-ref ish. Those are insanely hard to get right, soundly.

To mention just one immediately very apparent thing: yours is failing the most basic detail that the owned root must be behind indirection, otherwise moving the MutCursorRootedVec makes all borrows in the stack point to the wrong memory addresses after a move.

[luketpeterson]

Thank you for looking at this! I really appreciate your suggestions and I'm very happy to hear the idea isn't horribly flawed in a fundamental way.

Regarding the Send + Sync point you raised, I am struggling to understand why Arc (for example) requires both traits. I guess Arc can be cloned and MutCursor can't be.
https://github.com/rust-lang/rust/blob/7e6bf003f396aeea510577b4e925d1d95c12ff53/library/alloc/src/sync.rs#L248

I just published v0.3.0 with your suggestions.

Still not clear how to handle MutCursorRootedVec because having no lifetime parameter is part of its usefulness. In another project I use it to wrap an Arc as RootT, which doesn't run afoul of the "owning-ref" issue, but I don't know how to formalize that requirement in the contract / bounds... One idea is to re-implement Arc within MutCursorRootedVec but that has a lot more error-surface. For now I just made the create method unsafe.

Thanks again!

[luketpeterson]

Can I ask how you found this crate? Were you thinking about writing something similar? I didn't think anybody ever saw the stuff I published.

Thank you!

[steffahn]

Regarding the Send + Sync point you raised, I am struggling to understand why Arc (for example) requires both traits. I guess Arc can be cloned and MutCursor can't be.

Yes that’s exactly it. With Arc<T>: Send alone, it’s possible to produce &T-access in two threads simultaneously. (By cloning the Arc<T>, then sending one of them to the other thread. Or by downgrading to Weak, and upgrading that Weak, then sending the resulting Arc. You can also see how this is a larger concept about a whole API surface; e.g. Weak<T>: Send also needs T: Sync for that reason.)

So yeah, T: Sync is mostly about simultaneous &T-access on multiple threads at the same time.

And conversely with Arc<T>: Sync alone, which makes &Arc<T>-access on multiple threads possible, each of the threads could then clone the Arc<T> to get their own long-lived clone. Not a problem yet… but… if it so happens that these threads live long enough so there are no other strong clones of that Arc left, than either of the threads could be the one that drops the value, and only with T: Send are you allowed to drop a value of type T in another thread. Other aspects of T: Send: being able to transfer ownership between threads; being able to give a &mut T borrow to another thread. [Notably, &mut T borrows allow ownership-transfer, e.g. via std::mem::replace, or via wrapping in &mut Option<T>; and Drop impls offer &mut T access in the destructor; so it’s all related to ownership-transfer after all.]

Arc<T> also has additional API like try_unwrap giving an easier way to see why sending an Arc<T> can send a T.

It’s a complex topic anyways…

---

Can I ask how you found this crate? Were you thinking about writing something similar? I didn't think anybody ever saw the stuff I published.

Well, I tend to review crates encapsulating self-referencing-ish stuff when I come across them because it’s fun. In this case, that was quite random. I was rather looking for whether anyone had made any trait abstractions for APIs like the (unstable) cursor access to the standard library’s LinkedList (in this context) and so your crate has the cursor keyword so… it was something I looked at…

[steffahn]

In another project I use it to wrap an Arc as RootT

could you elaborate how this use-case works, given MutCursorRootedVec works with mutable borrows? Or are you simply using it with the get_mut/make_mut API?

[luketpeterson]

In another project I use it to wrap an Arc as RootT

could you elaborate how this use-case works, given MutCursorRootedVec works with mutable borrows? Or are you simply using it with the get_mut/make_mut API?

Yes exactly. It only calls get_mut&make_mut methods to get to the &mut NodeT

[steffahn]

@luketpeterson

I see. I have already thought about this, and I think it can fit the existing API. For supporting this use-case, we could simply provide a Unique-wrapper around Arc, and then give that wrapper the stable DerefMut impl. I think I can write down the exact API for this in a PR soon.

[luketpeterson]

Thanks! Closing this issue as complete.