iter::Fuse is unsound with how specialization currently behaves around HRTB fn pointers

[steffahn]

New high-level explanation of this issue, also covering #85873

Fuse<T> and Zip<T, U> have optimizations relying on specialization if their type parameters implement a trait (FusedIterator or TrustedRandomAccess, respectively).

These optimizations fundamentally change the way the iterator operates.

All type arguments are covariant. Coercing e.g. Fuse<T> to Fuse<U> if U is a subtype of T can “switch between” these fundamentally different ways of operation if T: !FusedIterator and U: FusedIterator which can bring the iterator into an invalid state that can cause UB; the same kind of problem exists for Zip.

For Zip, this problem can be avoided if TrustedRandomAccess never differs between types and subtypes. Copy-dependent impls for e.g. vec::IntoIter have to be removed (PR #85874).

Regarding Fuse: FusedIterator is a safe public trait, this is problematic. Some possible fixes: Either change Fuse to not get into a UB-causing invalid state by such a coercion (which kills some (or perhaps most) of the optimization offered by Fuse), or make Fuse invariant (but that’s a breaking change!). Here’s another possible approach, but this one requires new language features and could be done in the future if an immediate fix that just makes Fuse less performant is taken now.

Specialization not differentiating between e.g. Foo<'a> and Foo<'b> made this issue harder to spot.
But fn(&()) (that is, for<'a> fn(&'a ())) is a supertype [edited:] subtype of fn(&'static ()) and those are entirely different types.

---

Previous start of issue description

use std::{
    iter::{Fuse, FusedIterator},
    marker::PhantomData,
};

struct MyEmptyIterator<T>(PhantomData<T>, &'static str);
impl<T> Iterator for MyEmptyIterator<T> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        println!("called next, {}", self.1);
        None
    }
}

impl FusedIterator for MyEmptyIterator<fn(&'static ())> {}

fn main() {
    let mut f = MyEmptyIterator::<fn(&())>(PhantomData, "Hello, World").fuse();
    f.next();
    let mut f = f as Fuse<MyEmptyIterator<fn(&'static ())>>;
    f.next();
}

   Compiling playground v0.0.1 (/playground)
    Finished dev [unoptimized + debuginfo] target(s) in 1.74s
     Running `target/debug/playground`
timeout: the monitored command dumped core
/playground/tools/entrypoint.sh: line 11:     8 Segmentation fault      timeout --signal=KILL ${timeout} "$@"
Standard Output
called next, Hello, World

(playground)

@rustbot label T-libs, T-libs-impl, T-compiler, A-specialization, A-iterators, A-typesystem, A-lifetimes, A-traits, C-bug
someone please add the unsound label thanks

Explanation

The types for<'a> fn(&'a ()) (i.e. fn(&())) and fn(&'static ()) do seem to be distinguished by rust’s specialization. (I.e. the difference between the two types is not erased before the trait impl for specializing on FusedIterator is chosen.) But it’s also possible to convert Fuse<MyEmptyIterator<fn(&i32)>> into Fuse<MyEmptyIterator<fn(&'static i32)>>. This way, the first call to .next() will use unspecialized code and write a None value into the field of Fuse, whereas the second call will use the specialized version that uses intrinsics::unreachable() to unwrap the contained Option.

I haven’t tested it, but I’d guess that the same thing might be possible using HRTB trait objects instead of function pointers. (See comment below.)

Possible fixes

This soundness issue would probably go away if, somehow, specialization would also consider types such as fn(&()) and fn(&'static ()) to be “the same type”. Edit2: I don’t think that this approach is reasonable, and it’s probably even impossible.

The easiest / fastest fix for now would probably be to remove all the intrinsics::unreachable() assertions in the implementation of Fuse and replace them either with panics (which results in unexpected panicking but at least no unsoundness), or replace them with code that “properly” handles the None case as the iterator being empty. In either case, performance benefits from FusedIterator implementations could probably somewhat be retained by somehow marking the Some case as the hot path and the None case as a cold path. (In the approach with the None case panicking, this would probably be automatically considered the cold path due to the panic.)

Edit: Yet another alternative fix is to make Fuse<T> invariant over T.

[the8472]

I think this is a known hole see #68970 on rustc_unsafe_specialization_marker. Copy is similar in that regard.

[steffahn]

@the8472 That section also says

we allow it in the short term because it can't cause use after frees with purely safe code in the same way as specializing on traits methods can

This issue is a way to “cause use after frees with purely safe code” (not 100% a “use after free” with the current example code, but it can certainly be turned into “use-after-free” UB, too). So it is not a known hole AFAICT. I mean, sure, the fact that FusedIterator is a bit questionable in general and that implementing it for something like MyIterator<'static> will have the same fact as implementing it for all MyIterator<'a> is weird/questionable/perhaps-technically-UB. This issue is about the fact that the way that specialization handles HRTB-fn-pointers combined with the covariance of iter::Fuse makes for some practical unsoundness.

On a similar note, there are no other open I-unsound 💥+A-specialization issues that aren’t requires-nightly, further demonstrating the relevance of this issue.

[steffahn]

@the8472

Copy is similar in that regard.

Funny that you mentioned Copy, now I’ve also found an issue involving specialization on Copy: #85873

Maybe your remark even helped me a little bit in finding it. (I’m always unable to accurately recall afterwards how exactly I found such a soundness issue, so I’m not sure.)