PartialEq, Eq, PartialOrd and Ord should be unsafe traits

[theemathas]

The traits PartialEq, Eq, PartialOrd and Ord have contracts for sanity described in the documentation. However, some data structures and algorithms (such as https://crates.io/crates/skiplist) can end up relying on these being well-behaved, and not relying on this requires inefficient code. Additionally, it is unergonomic to put unsafe on the constructor methods, and it is impossible for these to correctly implement FromIterator, for example.

Therefore, I propose that these 4 traits be unsafe traits. This should only affect custom implementations, and not derives.

[pnkfelix]

see also relevant follow-on discussion here: https://botbot.me/mozilla/rust/2015-03-03/?msg=33235253&page=18 (and page 19, etc)

[Diggsey]

What about instead adding PartialEqStrict/EqStrict/etc. variants which extend PartialEq/Eq/etc. but are unsafe. Data structures and algorithms which would be unsafe if the relevent trait were implemented incorrectly should require the Strict variant of the trait.

This way, safe code can continue to use these traits effectively, where they would not cause unsafety, while unsafe code can always "upgrade" the safe versions into the strict versions without code duplication.

[theemathas]

FYI the conversation started here: https://botbot.me/mozilla/rust/2015-03-03/?msg=33233918&page=18

[Gankra]

I don't really see a reason why you would impl Eq but not EqStrict.

[theemathas]

@Diggsey That is pretty reasonable. However, how are ill-behaved Ord and friends useful at all?

Also note that, by "unsafe trait" I mean the one that is described here: https://github.com/rust-lang/rfcs/blob/master/text/0019-opt-in-builtin-traits.md

An unsafe trait is a trait that is unsafe to implement, because it represents some kind of trusted assertion. Note that unsafe traits are perfectly safe to use

[Diggsey]

One of the goals of rust is to maximize the safe subset of the language - otherwise you might as well just use C++ or do away with lifetimes. If you can't implement Eq/PartialEq/Ord/PartialOrd without resorting to unsafe code, then I see that as a serious failing, as they're necessary for most algorithms. It's not that ill-behaved versions are useful, it's that potentially ill-behaved versions will not result in memory unsafety.

[theemathas]

@Diggsey most code would use #[derive(...)] any way.

[seanmonstar]

I don't see how sticking an unsafe into there will make all implementations somehow stricter. If someone writes a bad implementation, there's nothing we can do. People would just shove in the unsafe and carry on, and you still can't "trust" the implementation.

Then again, it's their software that is using a crazy Eq implementation, so let them eat their cake too.

[Diggsey]

@theemathas I disagree - when writing algorithms I often need custom behaviour, such as to not include some fields, or to include some fields in reverse, or even more commonly, to calculate some other metric based on the fields. Particularly for these traits, the "derive" case is the exception rather than the rule.

@seanmonstar
You're missing the point of "unsafe" - it's not necessarily about guaranteeing that the code is correct, it's about marking code where incorrectness would result in memory unsafety, and rust is supposed to ensure that code not marked in that way cannot possibly cause memory unsafety. This means that if the code does crash with eg. an access violation/segfault, then you know the culprit is a piece of code marked as "unsafe", which should reduce the search space considerably.

[bluss]

I don't think we have the language features needed for this type of specialization. It's the same as the trusted iterator length problem -- we want to impl a feature based on the T: Iterator bound, but modify our behavior based upon an optional unsafe trait bound, something like if T: TrustedIterator..

Also, this doesn't stop at Eq and Ord. What other traits may unsafe blocks want to rely on that their behavior is predictable?

[Diggsey]

You don't need specialization - each data structure just picks either Trait or TraitStrict as its bound, depending on its requirements. For example, most existing data structures would continue to use Trait, whereas eg. skiplist, which depends on correct behaviour for memory safety, would use TraitStrict as its bound.

You're right that this doesn't stop at Eq and Ord - it stems from the fact that traits have more of a contract than just the methods they implement. Maybe instead of traits being either "unsafe" or "safe" to implement, implementations could choose to implement any trait in either a safe or unsafe way, and then trait bounds would specify whether they require a safe or unsafe implementation, eg:

// Implict contract, in the form of behaviour implementations should have
trait Ord {
    // Explicit contract, in the form of methods which must be implemented
}

// Guarantee that this impl fulfills both the implicit contract of Ord, and the explicit one
// This is unsafe because rust can't check the implicit contract for correctness
unsafe impl Ord for X { ... }
// Guarantee that this impl fullfills the explicit contract of Ord, which is checked by the compiler
impl Ord for Y { ... }

// Skiplist would be unsafe if Ord were implemented poorly
struct SkipList<T: unsafe Ord> { ... }
// BinaryHeap would just give incorrect results if Ord were implemented poorly
struct BinaryHeap<T: Ord> { ... }

SkipList<X> // OK
SkipList<Y> // Error, <Y as Ord> does not guarantee the implicit contract
BinaryHeap<X> // OK
BinaryHeap<Y> // OK

[theemathas]

@Diggsey It is possible to optimize certain algorithms based on the assumption that comparing is well-behaved.

[theemathas]

@bluss My proposal was based on the assumption that this will stop at these 4 traits and Iterator (which is probably addressed somewhere else). However, that assumption is wrong.

The reason that Cell only admits Copy, and not Clone, is that an ill-behaved clone() can caused problems there. See this chat log

I'm starting to be unsure whether this proposal is a good idea.

[glaebhoerl]

Yeah, this crops up for all kinds of traits. I've seen cases in Haskell where people wanted to rely on the associativity of Semigroup/Monoid in a similarly unsafe fashion. I don't know of any truly satisfactory solution to this issue...

[theemathas]

I made a PR for this. Please continue the discussion there.