Skip to content

Undefined behavior and wrong output with iterators #11

@Macdu

Description

@Macdu

Hello,
First, I would like to thank you for this very nice crate.

While using it, I ended up with some outputs that didn't make any sense (a node value and interval being swapped...). I tracked it down to the into_iter implementation. Here is a simple piece of code to show the issue:

fn bad() {
    use core::num::NonZeroU32;

    let tree : IntervalMap<u32, NonZeroU32> = interval_map! { 1..2 => NonZeroU32::try_from(3).unwrap() };

    println!("{:?}",  tree.into_iter(..).next().unwrap()); // Output (3..1, 2)
}

The reason being that this function uses cast_nodes which transmutes Node<T, V, Ix> to Node<T, MaybeUninit<V>, Ix>. However, even though V and MaybeUninit<V> are guaranteed to have the same layout, this is not the case for Node<T, V, Ix> and Node<T, MaybeUninit<V>, Ix>. This happens in practice for types with niches (NonZero, NonNull, Box) for which the compiler prefers to put them in front of the Node structure.
The correct way to fix it would be to transmute to MaybeUninit<Node<T, V, Ix>> instead.

Also while looking at it, I realized that remaining nodes value are not dropped if the iterator gets dropped.

One last thing is that the regular iterators returning mutable references are all causing undefined behavior (they cause two live mutable references for the same location to co-exist at the same time which is undefined behavior), although it would be much harder to observe in practice. The correct way to implement it would be doing something similar to std slice iterator.

I can do a pull request to fix all of this, but I would first like to know if this crate is still maintained, as it seems there has not been any update within the last year.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions