Unsafe, optimization-oriented traits for precise sizes, orderings, and so forth

[nikomatsakis]

We could sometimes write faster routines (e.g. sort, etc) if they can rely on orderings being sane, iterators having correct lengths. But this makes implementing that ordering/iterator code unsafe. Currently the traits do not require unsafe code.

This issue is a request to extend the set of traits with unsafe variants that let users opt in to these faster implementations. These traits might be generated by derive etc.

RFCs and issues along these lines:

• ExactSizeIterator should be an unsafe trait #958
• Unsafe comparison traits (PartialEq, Eq, PartialOrd, Ord) #956

[theemathas]

FYI, my preferred solution is having an unsafe default associated const such as assume_correct_eq, assume_correct_ord, assume_correct_length that defaults to false (but is true for derive comparisons). Changing them to true should require unsafe code.

Current problems:

• Requires associated constants
• Requires unsafe const
• Requires where Self: Sized on constants
• Requires default associated constants

[Gankra]

@theemathas an unsafe method seems strictly better. If it's implemented as just true or false then it will trivially be inlined to a constant, and it allows implementors to make the trusted-ness runtime conditional if need be (for instance if I provide an iterator with a fixed length that is potentially too large to be represented).

Also works with trait objects.

Also would completely work today without all of that extra tooling.

[theemathas]

@gankro Are you intending to use a static method or a &self method? If it's a static method, I cannot think of any useful runtime checks, but if it's a &self method, it won't work well with Ord and sort

[Gankra]

@theemathas I was mostly thinking about trusted_len; for trusted_cmp static probably makes more sense.

[pythonesque]

Unsafe methods won't work as intended currently (unless something has changed) because you don't need to write unsafe to implement an unsafe fn in a trait. Of course, this wouldn't be too hard to fix.

[Rufflewind]

I don't think a new language feature is necessary at all. The proof of a trait impl's law-abiding nature can be encoded as an abstract type that can only be conjured through an unsafe method. Here's a demonstration:

mod my_trait {
    use std::marker::PhantomData;

    pub trait MyTrait {
        /// Is there a witness to the trustworthiness of this trait?
        fn trust() -> Option<TrustMyTrait<Self>> {
            None
        }
    }

    /// Proof that the trait impl of `T` is trustworthy.
    pub struct TrustMyTrait<T: MyTrait + ?Sized>(PhantomData<T>);

    /// Conjure a proof out of thin air (hence the unsafety).
    pub unsafe fn trust_my_trait<T: MyTrait + ?Sized>() -> TrustMyTrait<T> {
        TrustMyTrait(PhantomData)
    }
}

use my_trait::{MyTrait, TrustMyTrait, trust_my_trait};

struct MyType;

impl MyTrait for MyType {
    fn trust() -> Option<TrustMyTrait<Self>> {
         // assert the impl of MyTrait for MyType is correct
         unsafe { Some(trust_my_trait()) }
    }
}

fn main() {
    match <MyType as MyTrait>::trust() {
        None => println!("MyTrait of MyType is not trustworthy :("),
        Some(_) => println!("MyTrait of MyType is trustworthy :D"),
    }
}

[comex]

This is an old thread, and by now Rust already has unsafe trait, which requires an unsafe impl.

(Just for the sake of completeness: your workaround would work for 'simulated' specialization using constant-returning functions plus the optimizer, but it wouldn't work particularly well for the upcoming true (type-system based) trait specialization. This is because the existence of an impl is not enough; since fn trust() could be implemented as a panic or infinite loop, code that relies on the unsafe property must actually call the function before doing anything dangerous. Trait specialization is of course based on the existence of an impl; you could still make sure to call the trust function in all affected code, but this would be easy to mess up, and impossible in some cases, e.g. with associated types or consts.)

[Rufflewind]

… you don't need to write unsafe to implement an unsafe fn in a trait. Of course, this wouldn't be too hard to fix.

@pythonesque I just tried it on 0.15.0 and it seems to be mandatory. I can't find any documentation to confirm whether this is intended behavior or not, though. If it is, then this proposal can be implemented without any new language features.

[Centril]

Closing as implemented.

[GoldsteinE]

Is there an issue/RFC for unsafe versions of Ord, Eq and Hash? There’s TrustedLen for ExactSizeIterator, but I failed to find traits for #956 in the standard library.