`Graph::index_twice_mut` is unsound

[cod10129]

Test Case

fn main() {
    use petgraph::Graph;
    let mut g: Graph<u8, ()> = Graph::new();
    let i = g.add_node(1);
    let j = g.add_node(2);
    let (one, two) = g.index_twice_mut(i, j);
    dbg!(one);
    dbg!(two);
}

(Playground)

Miri detects UB in this Playground. The petgraph code is the only unsafe in the program, so it must be at fault.

Steps To Reproduce

Insert instructions for reproducing the bug with the above test case:

• First, put the test case into a project with petgraph available. (cargo new & cargo add petgraph or in the playground).
• Then, run cargo miri over that code and it will detect UB.

Actual Results

UB exists in this program with only safe code. This means petgraph is unsound.

Expected Results

It should have the same result, but without undefined behavior being invoked in the program.

Explanation

For reference, this is Graph::index_twice_mut:

impl Graph {
    pub fn index_twice_mut<T, U>(
        &mut self,
        i: T,
        j: U,
    ) -> (
        &mut <Self as Index<T>>::Output,
        &mut <Self as Index<U>>::Output,
    )
    where
        Self: IndexMut<T> + IndexMut<U>,
        T: GraphIndex,
        U: GraphIndex,
    {
        assert!(T::is_node_index() != U::is_node_index() || i.index() != j.index());

        // Allow two mutable indexes here -- they are nonoverlapping
        unsafe {
            let self_mut = self as *mut _;
            (
                <Self as IndexMut<T>>::index_mut(&mut *self_mut, i),
                <Self as IndexMut<U>>::index_mut(&mut *self_mut, j),
            )
        }
    }
}

The safety comment is a lie, because of a sneaky problem.

Creating the &mut to pass to the second index_mut call asserts unique access to the entire graph to the compiler. This includes the first mutable reference, and there are now aliasing &muts, thus UB. The second mutable reference to the graph invalidates any other references to the graph, which borrowck doesn't see because the code uses unsafe to bypass it.

Solutions

To implement this function without UB, you would likely want to use slice::split_at_mut or a similar function for getting mutiple mutable references from a vector. This could be problematic because the signature of the function allows any type where Graph: IndexMut<T>, and it is possible for downstream crates to impl IndexMut<LocalType> for Graph. This might have to be a breaking change to fix this soundness bug.

I have found this bug dating back to the first version of petgraph that docs.rs could build, 0.1.11. This function has had the exact same signature, source, and safety comment dating back to 2015.

I hope this is helpful. I thought this was my mistake at first while reading the code, but then I thought to miri it, and this has been silently sitting as a dependency of 5000 Rust crates for years.

[cod10129]

Changing this function to only accept an internal trait for NodeIndex and EdgeIndex would not be breaking any sensible users of petgraph. A user's type can impl IndexMut<Foo> for Graph, but to pass that type to index_twice_mut, they would need to implement the GraphIndex trait. This trait is not sealed, but there are required #[doc(hidden)] functions. If you look into source code to implement hidden functions, you're practically asking for breakage.

[Imberflur]

This looks like a duplicate of https://github.com/petgraph/petgraph/issues/582

[cod10129]

Yes it is. Sorry I didn't see that earlier. I'll close this issue and move any of my further thoughts over there.