SpecExtend for TrustedLen is unsound

[lcnr]

#![feature(trusted_len)]
use std::iter::TrustedLen;
use std::marker::PhantomData;

pub struct MaybeTrusted<'a, I>(I, PhantomData<fn(&'a ()) -> &'a ()>);

impl<'a, I: Iterator> Iterator for MaybeTrusted<'a, I> {
    type Item = I::Item;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.next()
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.0.size_hint()
    }
}

/// This is safe, as a `'static` version of this struct can only be created
/// using a trusted iterator.
unsafe impl<I: Iterator> TrustedLen for MaybeTrusted<'static, I> {}
impl<I: TrustedLen> MaybeTrusted<'static, I> {
    pub fn new(value: I) -> Self {
        MaybeTrusted(value, PhantomData)
    }
}

/// `I` might not implement `TrustedLen`, but that's ok,
/// because you can't get a `MaybeTrusted<'static, I>` from this.
pub fn not_trusted<I: Iterator, T>(i: I, f: impl for<'a> FnOnce(MaybeTrusted<'a, I>) -> T) -> T {
    f(MaybeTrusted(i, PhantomData))
}

// In a separate crate:

struct Liar(usize);
impl Iterator for Liar {
    type Item = usize;
    fn next(&mut self) -> Option<Self::Item> {
        if self.0 < 10000 {
            self.0 += 1;
            Some(self.0)
        } else {
            None
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        // happy little accident, but ok, doesn't implemented `TrustedLen`.
        let len = self.0.saturating_sub(10000);
        (len, Some(len))
    }
}

fn main() {
    not_trusted(Liar(0), |iter| iter.collect::<Vec<_>>());
}

results in:

Segmentation fault (core dumped)

[the8472]

Is this actionable though? TrustedLen currently is not on a path to stabilization (#37572 (comment)) until specialization is ready. And that rustc_unsafe_specialization_marker (min_specialization.rs) is iffy... is in its description.

The question is whether it can be exploited by user code without using the feature gate itself. E.g. if there were an impl of TrustedLen somewhere conditional on a stable trait that user code could implement that would be a problem.

[mbartlett21]

Isn't this the same story with specialization being unsound with lifetimes?

The current implementation for specialization seems to be ignoring the 'static in the impl, which is unsound:

(from the RFC)

Interaction with lifetimes

A hard constraint in the design of the trait system is that dispatch cannot
depend on lifetime information. In particular, we both cannot, and should not
allow specialization based on lifetimes:

• We can't, because when the compiler goes to actually generate code ("trans"),
  lifetime information has been erased -- so we'd have no idea what
  specializations would soundly apply.

• We shouldn't, because lifetime inference is subtle and would often lead to
  counterintuitive results. For example, you could easily fail to get 'static
  even if it applies, because inference is choosing the smallest lifetime that
  matches the other constraints.

[lcnr]

Isn't this the same story with specialization being unsound with lifetimes?

yes, that's the root issue here. min_specialization (the subset std is using) avoids these issues by not allowing specializing impls to require specific lifetimes. As that didn't allow all uses of specialization in std we've added #[rustc_unsafe_specialization_marker] which is pretty much always unsound for traits which can depend on impls by users.

[mbartlett21]

It turns out that this is exactly analogous to the case documented in @aturon's blog: https://aturon.github.io/blog/2017/07/08/lifetime-dispatch/#cant-we-just-rule-out-bad-specializations

[the8472]

Yeah, afaict it only shows that if you use #![feature(trusted_len)] you can do unsafe impl TrustedLen for Foo<'static> {}. Which is a specific instance of using #![feature(min_specialization)], #[rustc_unsafe_specialization_marker] and a lifetime-dependent impl. Which in turn is a violation of the safety contract of that marker.

As long as this isn't exploitable by stable code through some incorrect impl of TrustedLen in the standard library there doesn't seem to be a novel issue here.

Perhaps we could put a warning on the TrustedLen docs if someone wants to implement it on a nightly crate, mention it in the tracking issue or make it doc(hidden) like some of the other internal specialization traits.

[the8472]

Also note that Copy has a similar hole that is exploitable by stable code and yet that has been tolerated (until specialization gets improved).

[alercah]

I'm not sure this is a bug, as the comment on not_trusted is wrong. The new function having an I: TrustedLen bound is irrelevant because that's not what not_trusted is using to construct the MaybeTrusted. We can see that a MaybeTrusted<'static, I> is indeed possible:

https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=9e9dcecaf73eaf6e7a5e9d4ac8c25079

Calling new gives an error as expected: https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=c6844306a602ac5e6bae523d254f3fb4

In the original example, the lifetime selected for the MaybeTrusted is entirely unconstrained by anything anywhere in the program. So the comment on not_trusted is operating under the assumption that Rust will not default to 'static when facing an unconstrained lifetime being passed into a closure with a HRTB, and I don't think that's an assumption that's at all justified.