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.)

[cuviper]

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

Wouldn't that be a breaking API change?

[steffahn]

Sure, it's a breaking change. I suppose this depends on the long term vision for Fuse. I haven't thought about it for too long myself either at the time of writing the idea of making it invariant, and my feeling when suggesting it was “maybe a Fuse type that holds its promise of being a no-op when the iterator implements FusedIterator can never be sound if it's covariant”, in which case considering and evaluating the possibility for the breaking change of making it invariant would perhaps be useful.

Anyways, since then, I'm thinking more along the lines of a long term solution of “somehow detect if the Fused Iterator implementation is having stronger bounds than the corresponding Iterator impl in a way that leaves an iterator type and one of its (also iterator) subtypes that differ on whether they implement FusedIterator. And only then drop the “no-op” guarantee and behave as if FusedIterator was implemented for neither.”

With such a long term vision for making Fuse sound (or something similar), the breaking change of introducing in variance would probably not be worth it and some (hopefully minor) performance overhead for a short term / intermediate solution could be a lot better.

[the8472]

@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.

CC @matthewjasper for clarification on what kind of unsoundness is expected from user-implementable #[rustc_unsafe_specialization_marker] traits.

[matthewjasper]

"purely safe code" includes library code in this context, which FusedIterator is not. I would prefer (soft) deprecating Fused and removing the specialization, but I can understand the library team not considering that feasible.

[the8472]

That sounds to me like some safety loopholes around specializations on FusedIterator and Copy were not unexpected since they tend to include unsafe code.

[steffahn]

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

For the record, the same thing is indeed also possible using trait objects.

[apiraino]

Assigning priority as discussed in the Zulip thread of the Prioritization Working Group.

@rustbot label -I-prioritize +P-critical

[steffahn]

Added a new high-level explanation for both this issue and #85873 at the beginning of this issue.

[steffahn]

Another possible fix for Fuse I just thought of, but that one would require new language features, would be to make Fuse<T> only use its optimized implementation if T and all its subtypes implement FusedIterator. Some way of writing a bound for<U: T> U: FusedIterator would be needed.

Applying the same idea to Zip (i.e. #85873) could work, but I think this would need a TrustedRandomAccess bound for all subtypes and all supertypes. As long as TrustedRandomAccess is not a public trait, this can also be done in the future after a short-term fix like #85874 has been implemented.

[nikomatsakis]

@rustbot label +T-lang

I think this is at least worth putting on the lang-team radar.

[joshtriplett]

Based on discussion in the @rust-lang/lang meeting today, this is worth discussing further in a language context to talk about how to make specialization safer, but this is not P-critical for lang, just for the specific impls in the standard library that use rustc_unsafe_specialization_marker.

[cuviper]

Another possible fix for Fuse I just thought of, but that one would require new language features, would be to make Fuse<T> only use its optimized implementation if T and all its subtypes implement FusedIterator. Some way of writing a bound for<U: T> U: FusedIterator would be needed.

I'm trying to understand how this would work. Your example has a subtype that does implement FusedIterator, but the supertype does not. So for Fuse to specialize that subtype, wouldn't it need a constraint that makes an assertion about all supertypes?

[cuviper]

I also realized that all of this was not a problem with the old done-flag version of Fuse before #70366. The difference used to be just that the specialized version didn't check or maintain the done flag, but the iterator always stuck around. So if variance moved us in and out of FusedIterator sub/supertypes, it would only have a logic bug whether things are fused, not unsoundness.

[steffahn]

Interesting observation. I wasn’t aware of this change / earlier design. AFAICT it’s indeed true that the worst that could happen with a done-flag design is that a non-FusedIterator typed iterator gets extra next() calls after None was first returned. However, following the approach in this issue, this is only possible if the iterator type is a subtype/supertype (I’m not sure which one, off the top of my head) of an iterator type that does implement FusedIterator. It’s a logic error that’s not worse than the general problem that specialization on FusedIterator ignores lifetime-constraints of FusedIterator-impls anyways.

@cuviper Your PR states “The former done flag was roughly similar to an Option tag, but left
the possibity of misuse.” What does “misuse” mean / refer to? I’d also be curious about performance implication of a done-flag version vs Option-version of Fuse. I guess reverting the design change of #70366 might be a very reasonable way to fix this issue.

[steffahn]

@cuviper

Your example has a subtype that does implement FusedIterator, but the supertype does not.

I think it’s the other way.

My example uses

MyEmptyIterator<fn(&'static ())>

and

MyEmptyIterator::<fn(&())>

The former implements FusedIterator. But MyEmptyIterator<fn(&'static ())> is a supertype of MyEmptyIterator<fn(&())>. The way to not mess this up is to think about the fact that you can always coerce a subtype into a supertype. A supertype is more general in the sense that a “every Foo is a Bar” relationship makes “Bar” as supertype of “Foo”. MyEmptyIterator<fn(&())> can be coerced into MyEmptyIterator<fn(&'static ())>, but not the other way around.

This terminology also has the effect that “larger” lifetimes create subtypes and “shorter” lifetimes create supertypes, even though “super” sounds more like “larger”. &'static T is a subtype of &'a T; the outlives-relation in Rust 'a: 'b “'a outlives 'b” corresponds to a subtype relationship (if lifetimes are used covariantly).

[cuviper]

But MyEmptyIterator<fn(&'static ())> is a supertype of MyEmptyIterator<fn(&())>.

Ah, right, function are contravariant in their parameters. In my defense, you also wrote in the OP:

But fn(&()) (that is, for<'a> fn(&'a ())) is a supertype of fn(&'static ()) and those are entirely different types.

[cuviper]

Your PR states “The former done flag was roughly similar to an Option tag, but left
the possibity of misuse.” What does “misuse” mean / refer to?

It's been a while, but I don't think there was any concrete misuse of Fuse at hand. The idea was basically just to guard against bugs in the implementation, where we might forget to check done in some instance. I first implemented that change along with Chain in #70332, and I think that one did have such state bugs over the years.

[steffahn]

But MyEmptyIterator<fn(&'static ())> is a supertype of MyEmptyIterator<fn(&())>.

Ah, right, function are contravariant in their parameters. In my defense, you also wrote in the OP:

But fn(&()) (that is, for<'a> fn(&'a ())) is a supertype of fn(&'static ()) and those are entirely different types.

Fair point, I’ll fix that. As you can tell by my lengthy reply above I’ve needed to double-check everything thoroughly myself, too, to make sure I’m not correcting you on something that you didn’t get wrong. These things are highly non-intuitive.

By the way, it doesn’t have anything to do with contravariance of fn arguments. for<'a> fn() -> &'a T vs fn() -> &'static T would work the same, the relevant “place” to look at is where the quantifier is, not where the lifetime is used. (So I guess the situation reverses if you have fn(for<'a> fn(&'a ())) vs fn(fn(&'static ()))).

[workingjubilee]

I am having trouble following this conversation, so I won't claim to have a deep opinion, but since there is a lot of confusion about which way the variance goes &etc., more cleanly expressing the subtype/supertype relationships seems desirable if we're going to expand the syntax for universal quantification. This is largely aside from the point, though.

[cuviper]

I opened #86765 and #86766 with reduced and eliminated specialization, so we can compare performance.

I also considered just changing those intrinsics::unreachable() to unreachable!() panics, but I think that's a bad move. It would avoid the unsound case, but it still implies that the user did something wrong, which isn't really true.

[danielhenrymantilla]

following this conversation

A diagram with some subtyping relationships

To recap, here is a hopefully illustrative diagram summarizing the basic subtyping relationships:

• source

• Playground

I have greyed out the types there that are necessarily / known to be 'static.

My personal view of the situation

I believe the "surprising thing" here is that some of us may have intuitively thought (I personally did!) that subtyping necessarily involved variance, and thus, involved there being different lifetimes. Or, in other words, some of us may have intuitively thought that a : 'static bound disabled strict subtyping (by strict I mean there being T : U with T ≠ U). That is, that there would not be distinct and yet greyed out nodes in that graph that happened to be connected by an arrow.

But there are: it turns out that a higher order fn pointer –which is currently distinct, type-level-wise, from any non-higher order fn pointer (this may change, IIRC, so that impl<A> … for fn(A) would cover fn(&()), for instance)– does feature a subtyping relationship with any "concrete / fixed choice of its higher-order lifetime parameter(s)", so that fn(&()) : fn(&'static ()) holds, and both of these types are : 'static.

Thus, not specializing over lifetimes does not prevent specializing over {sub,super}types.

This, however, in and of itself, is not a problem (≠ specializing over lifetimes, which is definitely a problem even without unsafe code).

Indeed, specialization itself is not to blame, here. There could have been two non-generic impls, one for Fuse<…fn(&())>, and one for Fuse<…fn(&'static ())>, and the problem would have still been there. Specialization has just made leading to this situation easier.

The problem stems from unsafe code inside one of these two impls (it happens to be the specialized one), which relied on a very specific state machine to uphold the invariants: it assumed full control of the "entrypoint" to this state machine. But it turns out subtyping makes it possible to start transitioning within the state machine for the fn(&()) impl, and then suddenly hop onto the middle of the state machine for the fn(&'static ()) impl, with the expected invariants thus not upheld. Hence the issue.

This is no different to some oversight regarding some .into() or .to_owned() conversion allowing something along the same lines (in that regard, coercions, a very close friend to subtyping, are also something to be mindful of: depending on the internals of Fuse, we could imagine it allowing an unsize coercion, and we'd have the same issue).

In practice

The short answer is to say that that impl for Fuse<impl FusedIterator> is unsound, because of this conversion. A middle ground could be to replace the unreachable_unchecked with an unreachable!(), and this would make a lot of sense if somebody had had to call .clone() / .into() in some weird fashion just to trigger that code path.

But the issue here is that the type conversion is very sneaky, since it's a subtyping conversion, which can happen at any point under our feet. So I agree with @cuviper that panic!-king may not be ideal.

For the case of Fuse specifically:

• since we can't specialize over lifetimes,

• since unsized coercions are not possible either (I think? Somebody double check this)

• this only leaves the fn(…)-shenanigans to perform this subtyping issue.

Thus, rather than a whole for<U : T> quantification (which seems like a big deal to implement; but I'm not against it either), there is a way to weasel out of this issue, to keep the optimized impl and avoid the soundness issue, at the cost of a tiny bit of lang magic: to have some unsafe auto trait which is unimplemented for all function pointer types (that's the only thing that requires lang magic). Let's call this auto trait BikeshedContainsNoFnPointers

Then, if we have T : BikeshedContainsNoFnPointers, and thanks to there not being specialization over lifetimes, Fuse<impl FusedIterator + BikeshedContainsNoFnPointers> could still feature the optimized impl.

• Obviously this breaks if there is another way, within Fuse specialized impls, to feature two distinct and yet convertible types (other form of subtypes? unsized coercion? some other way to construct a Fuse mid-way?).

[steffahn]

@danielhenrymantilla I believe that writing “outlives” as “⊇” also has potential for confusion. It might be useful if you’re thinking of lifetimes as a set of lines/places in your source code, but I wouldn’t necessarily want to introduce it as actual notation, because a correspondence between supersets (“⊇”) and subtypes – both using : and both being strongly related due to reference types – seems suboptimal. You’re writing “subtypes” explicitly in your diagram, so writing “outlives” explicitly, too, seems like the best option to me.

[cuviper]

That diagram would be a great addition to the reference!
https://doc.rust-lang.org/reference/subtyping.html

[steffahn]

@the8472 The original example works just as well with a generic

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

instead of just

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

The former kind of impl is not prohibited even for “#[rustc_specialization_trait]”. This means: even though “#[rustc_specialization_trait]” has more restriction, does in fact still fully support

these kinds of shenanigans.

[the8472]

Objection retracted.

[steffahn]

A day later, I still think that moving back to a done-flag design is the best way of fixing this issue. Especially, if it really doesn't come with any significant performance impact.

[cuviper]

The other downside of the done flag is that it adds align_of::<I>() bytes, whereas Option<I> may use a niche.

The performance of #86765 looks stable enough that this would be my preference, although it does lose in-place iteration.

[QuineDot]

But there are: it turns out that a higher order fn pointer –which is currently distinct, type-level-wise, from any non-higher order fn pointer (this may change, IIRC, so that impl<A> … for fn(A) would cover fn(&()), for instance)– does feature a subtyping relationship with any "concrete / fixed choice of its higher-order lifetime parameter(s)", so that fn(&()) : fn(&'static ()) holds, and both of these types are : 'static.

The current direction is for them to remain distinct types. See

• This writeup for MCP 295
• And some briefer conversation in the implementation PR

* this only leaves the `fn(…)`-shenanigans to perform this subtyping issue.

[...]
* Obviously this breaks if there is another way, within Fuse specialized impls, to feature two distinct and yet convertible types (other form of subtypes? unsized coercion? some other way to construct a Fuse mid-way?).

I'm not sure within Fuse specifically, but dyn for<'a> Trait<'a> and dyn Trait<'bound> exhibit the same behavior.