Amanieu / intrusive-rs

Intrusive collections for Rust
Apache License 2.0
400 stars 47 forks source link

Is this pattern for removing an item from a list safe? #52

Closed TooManyBees closed 3 years ago

TooManyBees commented 3 years ago

I have a use case where I want to iterate through a linked list and remove the "best" item (by whatever metric). So it involves testing each item, maintaining a reference to the best one found so far, then afterward removing the best item from the list.

This is roughly the code I want to use. It works, but results in the warning https://github.com/rust-lang/rust/issues/59159, which will soon turn into a hard error, that list is being mutably borrowed while reference is already immutably borrowing list.

fn pluck_best_item(list: &mut LinkedList<LinkAdapter>, prefix: &str) -> Option<Rc<Thing>> {
    let mut best_so_far = None;

    for thing in list.iter() {
        if is_better_candidate_for_removal(thing, &best_so_far) {
            best_so_far = Some(thing);
        }
    }

    if let Some(reference) = best_so_far {
        let mut cursor = unsafe { list.cursor_mut_from_ptr(reference) };
        return cursor.remove();
    }

    None
}

I found that casting the reference to a *const drops the immutable borrow and makes the borrow checker happy, like so:

if let Some(reference) = best_so_far {
    let ptr = reference as *const Thing;
    let mut cursor = unsafe { list.cursor_mut_from_ptr(ptr) };
    return cursor.remove();
}

Is this pattern safe at all? Not just casting the reference to a pointer, but the whole thing: maintaining a reference that was borrowed immutably to create a mutable cursor in order to remove the item. If it's unsafe, is there a better way to do what I'm trying to?

Amanieu commented 3 years ago

You may have to perform the cast when assigning best_so_far: best_so_far = Some(thing as *const _).

It is safe since even mutable cursors only expose an immutable reference to elements in the collection.

TooManyBees commented 3 years ago

That's great to hear, thanks.