Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

PartialEq implementation for RangeInclusive is unsound #67194

Closed
xfix opened this issue Dec 10, 2019 · 35 comments · Fixed by #68835
Closed

PartialEq implementation for RangeInclusive is unsound #67194

xfix opened this issue Dec 10, 2019 · 35 comments · Fixed by #68835
Labels
A-specialization C-bug E-help-wanted E-medium I-unsound P-high T-compiler T-libs-api

Comments

@xfix
Copy link
Contributor

xfix commented Dec 10, 2019

The following code causes UB in stable without unsafe (as can be seen on playground).

use std::cell::RefCell;
use std::cmp::Ordering;

struct Evil<'a, 'b> {
    values: RefCell<Vec<&'a str>>,
    to_insert: &'b String,
}

impl<'a, 'b> PartialEq for Evil<'a, 'b> {
    fn eq(&self, _other: &Self) -> bool {
        true
    }
}

impl<'a> PartialOrd for Evil<'a, 'a> {
    fn partial_cmp(&self, _other: &Self) -> Option<Ordering> {
        self.values.borrow_mut().push(self.to_insert);
        None
    }
}

fn main() {
    let e;
    let values;
    {
        let to_insert = String::from("Hello, world!");
        e = Evil {
            values: RefCell::new(Vec::new()),
            to_insert: &to_insert,
        };
        let range = &e..=&e;
        let _ = range == range;
        values = e.values;
    }
    println!("{:?}", values.borrow());
}

Effects of executing this code are random, for instance, I once got this.

["`�d�\u{11}V\u{0}\u{0}\u{0}\u{0}\u{0}\u{0}\u{0}", "`�d�\u{11}V\u{0}\u{0}\u{0}\u{0}\u{0}\u{0}\u{0}"]
@jonas-schievink jonas-schievink added I-nominated I-unsound T-libs-api C-bug A-specialization labels Dec 10, 2019
@jonas-schievink
Copy link
Member

jonas-schievink commented Dec 10, 2019

cc #45982

trait RangeInclusiveEquality: Sized {
fn canonicalized_is_empty(range: &RangeInclusive<Self>) -> bool;
}
impl<T> RangeInclusiveEquality for T {
#[inline]
default fn canonicalized_is_empty(range: &RangeInclusive<Self>) -> bool {
range.is_empty.unwrap_or_default()
}
}
impl<T: PartialOrd> RangeInclusiveEquality for T {
#[inline]
fn canonicalized_is_empty(range: &RangeInclusive<Self>) -> bool {
range.is_empty()
}
}

@hellow554

This comment has been minimized.

@jonas-schievink
Copy link
Member

jonas-schievink commented Dec 10, 2019

Interesting! Non-NLL version of the PoC:

use std::cell::RefCell;
use std::cmp::Ordering;

struct Evil<'a, 'b> {
    values: RefCell<Vec<&'a str>>,
    to_insert: &'b String,
}

impl<'a, 'b> PartialEq for Evil<'a, 'b> {
    fn eq(&self, _other: &Self) -> bool {
        true
    }
}

impl<'a> PartialOrd for Evil<'a, 'a> {
    fn partial_cmp(&self, _other: &Self) -> Option<Ordering> {
        self.values.borrow_mut().push(self.to_insert);
        None
    }
}

fn main() {
    let values;
    {
        let to_insert = String::from("Hello, world!");
        let e;
        {
            e = Evil {
                values: RefCell::new(Vec::new()),
                to_insert: &to_insert,
            };
            let range = &e..=&e;
            let _ = range == range;
        }
        values = e.values;
    }
    println!("{:?}", values.borrow());
}

@hellow554
Copy link
Contributor

hellow554 commented Dec 10, 2019

Thanks jonas! Okay, it could be the code you linked, because it starts crashing at 1.29.0 and that matches the date of your code snippet. Thanks :)

@xfix
Copy link
Contributor Author

xfix commented Dec 10, 2019

I'm almost sure this is due to specialization, because I actually did look in Rust source code for places with exploitable specialization by searching for default fn (specialization is known to be unsound, nothing new here), and found this one.

@slightlyoutofphase
Copy link
Contributor

slightlyoutofphase commented Dec 10, 2019

If it helps at all, here's a completely self-contained version, with RangeInclusive extracted and renamed MyRangeInclusive, modified such that it actually gives the compile-time borrowing error I believe it's probably supposed to:

#![feature(specialization)]

use core::cmp::Ordering;
use core::fmt;
use core::hash::{Hash, Hasher};
use core::ops::{Bound, Bound::Included, RangeBounds};

#[derive(Clone)]
pub struct MyRangeInclusive<Idx> {
    pub(crate) start: Idx,
    pub(crate) end: Idx,
    pub(crate) is_empty: Option<bool>,
}

impl<T> RangeBounds<T> for MyRangeInclusive<T> {
    fn start_bound(&self) -> Bound<&T> {
        Included(&self.start)
    }
    fn end_bound(&self) -> Bound<&T> {
        Included(&self.end)
    }
}

trait MyRangeInclusiveEquality: Sized {
    fn canonicalized_is_empty(range: &MyRangeInclusive<Self>) -> bool;
}

impl<T> MyRangeInclusiveEquality for T {
    #[inline]
    default fn canonicalized_is_empty(range: &MyRangeInclusive<Self>) -> bool {
        range.is_empty.unwrap_or_default()
    }
}

impl<T: PartialOrd> MyRangeInclusiveEquality for T {
    #[inline]
    fn canonicalized_is_empty(range: &MyRangeInclusive<Self>) -> bool {
        range.is_empty()
    }
}

// Make this one a `default fn`...
impl<Idx: PartialEq> PartialEq for MyRangeInclusive<Idx> {
    #[inline]
    default fn eq(&self, other: &Self) -> bool {
        self.start == other.start
            && self.end == other.end
            && MyRangeInclusiveEquality::canonicalized_is_empty(self)
                == MyRangeInclusiveEquality::canonicalized_is_empty(other)
    }
}

// And add a second version (with an identical implementation) for PartialOrd.
// The presence of this second impl specifically is what makes it fail the borrow
// checker as opposed to compiling and printing invalid text (though I don't know why.)
impl<Idx: PartialOrd> PartialEq for MyRangeInclusive<Idx> {
    #[inline]
    fn eq(&self, other: &Self) -> bool {
        self.start == other.start
            && self.end == other.end
            && MyRangeInclusiveEquality::canonicalized_is_empty(self)
                == MyRangeInclusiveEquality::canonicalized_is_empty(other)
    }
}

impl<Idx: Eq> Eq for MyRangeInclusive<Idx> {}

impl<Idx: Hash> Hash for MyRangeInclusive<Idx> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.start.hash(state);
        self.end.hash(state);
        MyRangeInclusiveEquality::canonicalized_is_empty(self).hash(state);
    }
}

impl<Idx> MyRangeInclusive<Idx> {
    #[inline]
    pub const fn new(start: Idx, end: Idx) -> Self {
        Self {
            start,
            end,
            is_empty: None,
        }
    }

    #[inline]
    pub const fn start(&self) -> &Idx {
        &self.start
    }

    #[inline]
    pub const fn end(&self) -> &Idx {
        &self.end
    }

    #[inline]
    pub fn into_inner(self) -> (Idx, Idx) {
        (self.start, self.end)
    }
}

impl<Idx: fmt::Debug> fmt::Debug for MyRangeInclusive<Idx> {
    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
        self.start.fmt(fmt)?;
        write!(fmt, "..=")?;
        self.end.fmt(fmt)?;
        Ok(())
    }
}

impl<Idx: PartialOrd<Idx>> MyRangeInclusive<Idx> {
    pub fn contains<U>(&self, item: &U) -> bool
    where
        Idx: PartialOrd<U>,
        U: ?Sized + PartialOrd<Idx>,
    {
        <Self as RangeBounds<Idx>>::contains(self, item)
    }

    #[inline]
    pub fn is_empty(&self) -> bool {
        self.is_empty.unwrap_or_else(|| !(self.start <= self.end))
    }

    #[inline]
    pub(crate) fn compute_is_empty(&mut self) {
        if self.is_empty.is_none() {
            self.is_empty = Some(!(self.start <= self.end));
        }
    }
}

use core::cell::RefCell;

#[derive(Debug)]
struct Evil<'a, 'b> {
    values: RefCell<Vec<&'a str>>,
    to_insert: &'b String,
}

impl<'a, 'b> PartialEq for Evil<'a, 'b> {
    fn eq(&self, _other: &Self) -> bool {
        true
    }
}

impl<'a> PartialOrd for Evil<'a, 'a> {
    fn partial_cmp(&self, _other: &Self) -> Option<Ordering> {
        self.values.borrow_mut().push(self.to_insert);
        None
    }
}

fn main() {
    let e;
    let values;
    {
        let to_insert = String::from("Hello, world!");
        e = Evil {
            values: RefCell::new(Vec::new()),
            to_insert: &to_insert,
        };
        let range = MyRangeInclusive::new(&e, &e);
        let _ = range == range;
        values = e.values;
    }
    println!("{:?}", values.borrow());
}

Playground link.

Edit: added a better comment indicating what the specific code change is that makes it fail the borrow checker as opposed to UB-ing.

@Centril Centril added the T-lang label Dec 11, 2019
@nikomatsakis
Copy link
Contributor

nikomatsakis commented Dec 13, 2019

The problem here clearly has to do with the known unsoundness related to specialization. I believe the core specialization is here:

impl<Idx: PartialEq> PartialEq for MyRangeInclusive<Idx>
impl<Idx: PartialOrd> PartialEq for MyRangeInclusive<Idx>

Unfortunately, this specialization violates the always applicable test. In particular, the specializing impl (the second one) is not, well, always applicable. =) In particular the Idx: PartialOrd bound is not implied by the WF conditions of the type nor by the conditions on the base impl.

(Note that the extended version of specialization that @aturon described here would permit this specialization, but it would exclude the troublesome PartialOrd impl from being used, and thus also be sound.)

@nikomatsakis
Copy link
Contributor

nikomatsakis commented Dec 13, 2019

So... the specialization is unsound as implemented today, but could be made sound. This is probably true of a lot of specializations.

@matthewjasper
Copy link
Contributor

matthewjasper commented Jan 9, 2020

There's also this impl:

rust/src/libcore/slice/mod.rs

Lines 5614 to 5616 in 2c796ee

impl<A> SlicePartialOrd<A> for [A]
where
A: Ord,

@nikomatsakis
Copy link
Contributor

nikomatsakis commented Jan 9, 2020

We discussed this in today's @rust-lang/lang meeting on 2020-01-09. A few things:

We should probably prepare a PR that comments out the unsound specialization. It'd be good to get an idea of the performance impact -- perhaps someone can figure out who added it and ping them? (Short on time right now or I'd do it myself)

We might want to do a more general audit. In general, we'd be looking for specializations that are based on "do one thing for types that implement trait X, another for types that also implement trait Y". The current implementation cannot handle this soundly, we would need the concepts @aturon described in this blog post.

Specializations that should generally be fine are those that pick out specific types:

impl<T> Foo for T { }
impl Foo for u32 { }

This suggests we may be able to recover performance here if we can replace these specialized impls with various special cases:

impl<Idx: PartialEq> PartialEq for MyRangeInclusive<Idx>
impl PartialEq for MyRangeInclusive<usize>
impl PartialEq for MyRangeInclusive<isize>
// etc

@Centril Centril added E-help-wanted E-medium T-compiler I-nominated and removed I-nominated T-lang T-libs-api labels Jan 9, 2020
@pnkfelix
Copy link
Member

pnkfelix commented Jan 16, 2020

T-compiler triage: I don't think this is currently a T-compiler issue.

(Obviously if we were to adopt changes to specialization semantics to accommodate this, then that would be T-compiler; but my reading of the comment thread here is that in the immediate term, the right answer is to remove the offending specialization, which I think is a T-libs matter, right?)

@pnkfelix
Copy link
Member

pnkfelix commented Jan 16, 2020

T-compiler triage: P-high, removing nomination. readding T-libs tag.

@pnkfelix pnkfelix added P-high T-libs-api and removed I-nominated labels Jan 16, 2020
bors added a commit that referenced this issue Jan 16, 2020
…-specialization, r=<try>

[WIP] Commenting out unsound specialiation.

If perf results indicate that we need this, then we should try to emulate it via a series of implementations on concrete types.

cc #67194
bors added a commit that referenced this issue Jan 19, 2020
Remove some unsound or hard to verify specializations

I've been working on restricting specialization in the standard library to prevent issues like #67194. This is the fallout of those changes.

* The `PartialEq` and `Hash` implementations for  `RangeInclusive` are changed to avoid specialization.
* The `PartialOrd` specialization for slices now specializes on a limited set of concrete types.
* Some impls of `TrustedRandomAccess` (a trait used to improve `iter::Zip` performance) have been removed.
* Added some tests for the soundness problems.
@eddyb
Copy link
Member

eddyb commented Jan 19, 2020

@xfix Okay I missed that, although to be fair that impl is really:

impl PartialEq<Evil<'c, 'd>> for Evil<'a, 'b>
    where 'a = 'c, 'b = 'd

You could've written even PartialEq<Evil<'static, 'static>> and specialization would still apply.

@nikomatsakis Oh, right, no bound relying a public trait can work in such a situation (user operations involving multiple values of the same type, which can differ in lifetimes after erasure), because we don't have a way to constrain the user impls.
(we could still add a core-private SpecizationSafePartialOrd which we'd only implement on types with no lifetimes in them - probably just integers and floats)

@the8472
Copy link
Contributor

the8472 commented Jan 21, 2020

I wasn't aware of this kind of problem with specialization. I'm trying to add some more specializations to Vec, which might run afoul of these: #66383
Can someone take a look whether what I am doing is ok?

@nikomatsakis
Copy link
Contributor

nikomatsakis commented Jan 24, 2020

@eddyb right...we do have a plan to fix such cases, but it's not implemented or really universally agreed upon

@withoutboats
Copy link
Contributor

withoutboats commented Jan 28, 2020

This suggests we may be able to recover performance here if we can replace these specialized impls with various special cases:

Another option is to use a private, blanket implemented marker subtrait (SpecializablePartialOrd) which is not exposed to users but gives the specialization to all std types with one impl. This assumes that all std impls are always applicable impls of course, but I think that's true.

You could also not blanket impl it, but it would then still be less impls in theory than concrete impls: O(PartialOrd types + Specialization impls) instead of O(PartialOrd types * Specialization impls)

@pnkfelix
Copy link
Member

pnkfelix commented Jan 30, 2020

Just to keep people up to date: We (or I) tried removing the specialization in PR #68280.

The CI run for that revealed a regression test failure: This particular specialization has semantic meaning. It is not just a performance optimization, as I understand it.

I talked to @alexcrichton about this today, and they told me that the T-libs team would take charge on resolving this.

@alexcrichton
Copy link
Member

alexcrichton commented Jan 31, 2020

@rust-lang/libs this is something we'll likely want to take a look at. There's a lot to digest here but the tl;dr is that there's unsound code via specialization in the standard library. A PR to remove the specialization is failing a regression test. This specialized impl accidentally isn't following our attempted rule of "no specialization if it changes behavior".

My personal read on this is that we should simply ignore the failing test (comment it out) and land the soundness fix. However surprising the PartialEq impl may be afterwards it's not as surprising as accidental undefined behavior. I do not personally remember why this impl is the way it is, nor why specialization is used here with RangeInclusive.

Do others object to landing #68280 after commenting out the test and perhaps getting a crater run to double-check it doesn't have a massive community impact?

@Mark-Simulacrum
Copy link
Member

Mark-Simulacrum commented Jan 31, 2020

So that it's easier for people landing here -- the regression test in question is this one:

rust/src/libcore/tests/iter.rs

Lines 1986 to 1991 in f2e1357

let mut r = 100..=10;
assert_eq!(r.next(), None);
assert!(r.is_empty());
assert_eq!(r.next(), None);
assert_eq!(r.next(), None);
assert_eq!(r, 100..=10);

AFAICT, it's testing that the RangeInclusive remains equivalent according to PartialEq when next() is called on an "empty" range.

The problem seems to stem from the fact that RangeInclusive stores emptiness as an Option<bool> -- this is only initialized when iterating (see compute_is_empty).

The reason we need specialization, at least by default, is that you can construct a RangeInclusive from something that doesn't implement PartialOrd (or Step, which is : PartialOrd). Plus, we cannot eagerly compute the emptiness, as that requires a trait method call (PartialOrd::partial_cmp) which is not const, and the constructor is stably const.

The specialization was added in #51622, primarily I think to resolve this discussion.

@xfix
Copy link
Contributor Author

xfix commented Jan 31, 2020

I wonder if specialization could be specifically for Step instead of PartialOrd, avoiding this issue on stable. I think #62886 intends to make this trait unsafe, if that helps.

This likely would block stabilization of Step, but that's fine.

@pnkfelix
Copy link
Member

pnkfelix commented Feb 3, 2020

To be honest, I'm trying to understand the actual goal here, in terms of how the T-libs team expects ranges to behave.

If it suffices to implement the specialized version on a set of built-in integer types, and not all PartialOrd types, then we can just do that right now. Certainly that is a simple approach. But is it actually sufficient, @xfix? Your comment seems to imply it would be...

@Mark-Simulacrum
Copy link
Member

Mark-Simulacrum commented Feb 3, 2020

All tests in libcore do pass with the following diff. Unfortunately, it means that the Hash and PartialEq/Eq impls no longer satisfy the requirement given in https://doc.rust-lang.org/nightly/std/hash/trait.Hash.html#hash-and-eq. It is my opinion that it was almost certainly a mistake to not have a Idx: PartialEq bound on the Hash impl for RangeInclusive. I believe it may be true that we can use specialization to resolve this, though I have not tried.

diff --git a/src/libcore/ops/range.rs b/src/libcore/ops/range.rs
index d38b3516569..54672cd8bf6 100644
--- a/src/libcore/ops/range.rs
+++ b/src/libcore/ops/range.rs
@@ -349,32 +349,13 @@ pub struct RangeInclusive<Idx> {
     // accept non-PartialOrd types, also we want the constructor to be const.
 }
 
-trait RangeInclusiveEquality: Sized {
-    fn canonicalized_is_empty(range: &RangeInclusive<Self>) -> bool;
-}
-
-impl<T> RangeInclusiveEquality for T {
-    #[inline]
-    default fn canonicalized_is_empty(range: &RangeInclusive<Self>) -> bool {
-        range.is_empty.unwrap_or_default()
-    }
-}
-
-impl<T: PartialOrd> RangeInclusiveEquality for T {
-    #[inline]
-    fn canonicalized_is_empty(range: &RangeInclusive<Self>) -> bool {
-        range.is_empty()
-    }
-}
-
 #[stable(feature = "inclusive_range", since = "1.26.0")]
 impl<Idx: PartialEq> PartialEq for RangeInclusive<Idx> {
     #[inline]
     fn eq(&self, other: &Self) -> bool {
         self.start == other.start
             && self.end == other.end
-            && RangeInclusiveEquality::canonicalized_is_empty(self)
-                == RangeInclusiveEquality::canonicalized_is_empty(other)
+            && ((self.start == self.end) == (other.start == other.end))
     }
 }
 
@@ -386,7 +367,6 @@ impl<Idx: Hash> Hash for RangeInclusive<Idx> {
     fn hash<H: Hasher>(&self, state: &mut H) {
         self.start.hash(state);
         self.end.hash(state);
-        RangeInclusiveEquality::canonicalized_is_empty(self).hash(state);
     }
 }
 

@Mark-Simulacrum
Copy link
Member

Mark-Simulacrum commented Feb 3, 2020

Thinking about my impl more, it won't work -- we can't verify emptiness without PartialOrd/Step, as the three-field nature of RangeInclusive requires that all three fields are used to determine if we're empty (presuming we have not yet called next()).

I believe the property we want is that if PartialEq(&self, &other) == true, then self.next() == other.next(). It is true that this is satisfied by removing the specialization and always doing is_empty.unwrap_or_default(); the "wrong" behavior there arises from calling next() having an effect on initially empty ranges, as we should be in is_empty = true but are not (yet) there. It might be possible to detect that the current state is always empty (i.e., start > end) and then not fill in the empty slot. I think this might solve the problem without regressing tests; however, this could have performance implications.

That approach essentially states that we only use the is_empty slot for cases where start <= end. That means that Idx: !Step and start > end would both behave the same, and correctly -- we do not need the boolean if we're not ever going to emit any values from the iterator.

@CAD97
Copy link
Contributor

CAD97 commented Feb 4, 2020

I think the following diff achieves that:

diff --git a/src/libcore/iter/range.rs b/src/libcore/iter/range.rs
index eac3c107d22..640ea417207 100644
--- a/src/libcore/iter/range.rs
+++ b/src/libcore/iter/range.rs
@@ -341,10 +341,10 @@ impl<A: Step> Iterator for ops::RangeInclusive<A> {
 
     #[inline]
     fn next(&mut self) -> Option<A> {
-        self.compute_is_empty();
-        if self.is_empty.unwrap_or_default() {
+        if self.is_empty() {
             return None;
         }
+        self.compute_is_empty();
         let is_iterating = self.start < self.end;
         self.is_empty = Some(!is_iterating);
         Some(if is_iterating {
@@ -369,10 +369,10 @@ impl<A: Step> Iterator for ops::RangeInclusive<A> {
 
     #[inline]
     fn nth(&mut self, n: usize) -> Option<A> {
-        self.compute_is_empty();
-        if self.is_empty.unwrap_or_default() {
+        if self.is_empty() {
             return None;
         }
+        self.compute_is_empty();
 
         if let Some(plus_n) = self.start.add_usize(n) {
             use crate::cmp::Ordering::*;
@@ -402,11 +402,10 @@ impl<A: Step> Iterator for ops::RangeInclusive<A> {
         F: FnMut(B, Self::Item) -> R,
         R: Try<Ok = B>,
     {
-        self.compute_is_empty();
-
         if self.is_empty() {
             return Try::from_ok(init);
         }
+        self.compute_is_empty();
 
         let mut accum = init;
 
@@ -445,10 +444,10 @@ impl<A: Step> Iterator for ops::RangeInclusive<A> {
 impl<A: Step> DoubleEndedIterator for ops::RangeInclusive<A> {
     #[inline]
     fn next_back(&mut self) -> Option<A> {
-        self.compute_is_empty();
-        if self.is_empty.unwrap_or_default() {
+        if self.is_empty() {
             return None;
         }
+        self.compute_is_empty();
         let is_iterating = self.start < self.end;
         self.is_empty = Some(!is_iterating);
         Some(if is_iterating {
@@ -461,10 +460,10 @@ impl<A: Step> DoubleEndedIterator for ops::RangeInclusive<A> {
 
     #[inline]
     fn nth_back(&mut self, n: usize) -> Option<A> {
-        self.compute_is_empty();
-        if self.is_empty.unwrap_or_default() {
+        if self.is_empty() {
             return None;
         }
+        self.compute_is_empty();
 
         if let Some(minus_n) = self.end.sub_usize(n) {
             use crate::cmp::Ordering::*;
@@ -494,11 +493,10 @@ impl<A: Step> DoubleEndedIterator for ops::RangeInclusive<A> {
         F: FnMut(B, Self::Item) -> R,
         R: Try<Ok = B>,
     {
-        self.compute_is_empty();
-
         if self.is_empty() {
             return Try::from_ok(init);
         }
+        self.compute_is_empty();
 
         let mut accum = init;
 
diff --git a/src/libcore/ops/range.rs b/src/libcore/ops/range.rs
index d38b3516569..72d66698520 100644
--- a/src/libcore/ops/range.rs
+++ b/src/libcore/ops/range.rs
@@ -349,32 +349,11 @@ pub struct RangeInclusive<Idx> {
     // accept non-PartialOrd types, also we want the constructor to be const.
 }
 
-trait RangeInclusiveEquality: Sized {
-    fn canonicalized_is_empty(range: &RangeInclusive<Self>) -> bool;
-}
-
-impl<T> RangeInclusiveEquality for T {
-    #[inline]
-    default fn canonicalized_is_empty(range: &RangeInclusive<Self>) -> bool {
-        range.is_empty.unwrap_or_default()
-    }
-}
-
-impl<T: PartialOrd> RangeInclusiveEquality for T {
-    #[inline]
-    fn canonicalized_is_empty(range: &RangeInclusive<Self>) -> bool {
-        range.is_empty()
-    }
-}
-
 #[stable(feature = "inclusive_range", since = "1.26.0")]
 impl<Idx: PartialEq> PartialEq for RangeInclusive<Idx> {
     #[inline]
     fn eq(&self, other: &Self) -> bool {
-        self.start == other.start
-            && self.end == other.end
-            && RangeInclusiveEquality::canonicalized_is_empty(self)
-                == RangeInclusiveEquality::canonicalized_is_empty(other)
+        self.start == other.start && self.end == other.end && self.is_empty.unwrap_or_default()
     }
 }
 
@@ -386,7 +365,7 @@ impl<Idx: Hash> Hash for RangeInclusive<Idx> {
     fn hash<H: Hasher>(&self, state: &mut H) {
         self.start.hash(state);
         self.end.hash(state);
-        RangeInclusiveEquality::canonicalized_is_empty(self).hash(state);
+        self.is_empty.unwrap_or_default().hash(state);
     }
 }
 

Every use of compute_if_empty is already next to a use of is_empty, and a short circuit if it is empty. So I just made sure each one of them calls .if_empty() and short circuits the empty case before compute_if_empty is called.

This feels like creating a footgun for the future, but should resolve the immediate issue. (It is, however, untested, because I got a weird ICE when building stage1 while trying to test it.)

Ultimately, perhaps that means changing the variable to exhausted: bool, and only setting it when exhausting via next?

@kennytm
Copy link
Member

kennytm commented Feb 4, 2020

What if we change it back to a two-field struct (rust-lang/rfcs#1980) 🤷‍?

@xfix
Copy link
Contributor Author

xfix commented Feb 4, 2020

Let me explain what I mean that the specialization is only needed for integer types. RangeInclusive has three fields.

pub struct RangeInclusive<Idx> {
    pub(crate) start: Idx,
    pub(crate) end: Idx,
    pub(crate) is_empty: Option<bool>,
    // This field is:
    //  - `None` when next() or next_back() was never called
    //  - `Some(false)` when `start <= end` assuming no overflow
    //  - `Some(true)` otherwise
    // The field cannot be a simple `bool` because the `..=` constructor can
    // accept non-PartialOrd types, also we want the constructor to be const.
}

The field is_empty is always going to be None when next or next_back was never called. Those methods can only be called when the RangeInclusive is an iterator.

impl<A: Step> Iterator for ops::RangeInclusive<A>

Step is only implemented for integer types and is an unstable trait: https://doc.rust-lang.org/std/iter/trait.Step.html. This means nobody can implement it for other types on stable.

This would pretty much prevent the stabilization of Step, but that seems acceptable to me. It's not ready for stabilization anyway in its current state.

Alternatively, it's possible to modify PartialEq to not call is_empty method when is_empty field for both ranges is None. is_empty is useful only in scenario when one range has Some, but the other one is None.

Another way out is to revert to two-field struct. Then we would avoid the need to do a lazy computation of whether the iterator is empty or not.

So, the fix essentially would be to do this (and of course, you need to import Step trait).

-impl<T: PartialOrd> RangeInclusiveEquality for T {
+impl<T: Step> RangeInclusiveEquality for T {
     #[inline]
     fn canonicalized_is_empty(range: &RangeInclusive<Self>) -> bool {
         range.is_empty()
     }
 }

It doesn't fix the issue fully (you can still have incorrect Step implementations on nightly), but it sure does solve it on stable.

Also, we can simplify RangeInclusiveEquality's default implementation.

impl<T> RangeInclusiveEquality for T {
    #[inline]
    default fn canonicalized_is_empty(range: &RangeInclusive<Self>) -> bool {
        false // the exact value doesn't matter when range is not an iterator
    }
}

Easy performance improvement in my opinion. You can even do some more advanced stuff to not even have a pointless constant value to skip stuff like hashing the value returned from this function. Maybe canonicalized_is_empty should return a three state boolean (where the None state would mean it doesn't matter and it doesn't need to be hashed). For Step types, the value would be Some, for non-Step types the value would be always None.

It kinda could be cool to not have to have is_empty field in a struct for non-Step types, but I don't think it's possible, Rust doesn't have associated type specialization. Oh well.

@Mark-Simulacrum
Copy link
Member

Mark-Simulacrum commented Feb 4, 2020

I think based on the discussion so far replacing the specialization to be bounded by a new trait that is only implemented for the integer primitives makes sense to me. I think that gets us soundness and is (per what you've said) not breaking for essentially anyone today. It's only breaking if there are (unstable) impls of Step in the wild where the code also wants a PartialEq impl on RangeInclusive. My guess is that code is very rare.

@scottmcm
Copy link
Member

scottmcm commented Feb 4, 2020

And there's an open PR to redesign the Step trait, which will break all that code anyway.

@SimonSapin
Copy link
Contributor

SimonSapin commented Feb 10, 2020

PR #68358 has been merged. Is this issue fixed?

@nikomatsakis
Copy link
Contributor

nikomatsakis commented Feb 10, 2020

cc @matthewjasper on that topic

@Mark-Simulacrum
Copy link
Member

Mark-Simulacrum commented Feb 10, 2020

Also note that we're landing #68835 shortly which fixes the Range inclusive Hash and Eq impls to be the same.

@bors bors closed this as completed in e6ec0d1 Feb 10, 2020
bors added a commit that referenced this issue Mar 16, 2020
Implement a feature for a sound specialization subset

This implements a new feature (`min_specialization`) that restricts specialization to a subset that is reasonable for the standard library to use.

The plan is to then:

* Update `libcore` and `liballoc` to compile with `min_specialization`.
* Add a lint to forbid use of `feature(specialization)` (and other unsound, type system extending features) in the standard library.
* Fix the soundness issues around `specialization`.
* Remove `min_specialization`

The rest of this is an overview from a comment in this PR

## Basic approach

To enforce this requirement on specializations we take the following approach:
1. Match up the substs for `impl2` so that the implemented trait and self-type match those for `impl1`.
2. Check for any direct use of `'static` in the substs of `impl2`.
3. Check that all of the generic parameters of `impl1` occur at most once in the *unconstrained* substs for `impl2`. A parameter is constrained if its value is completely determined by an associated type projection predicate.
4. Check that all predicates on `impl1` also exist on `impl2` (after matching substs).

## Example

Suppose we have the following always applicable impl:

```rust
impl<T> SpecExtend<T> for std::vec::IntoIter<T> { /* specialized impl */ }
impl<T, I: Iterator<Item=T>> SpecExtend<T> for I { /* default impl */ }
```

We get that the subst for `impl2` are `[T, std::vec::IntoIter<T>]`. `T` is constrained to be `<I as Iterator>::Item`, so we check only `std::vec::IntoIter<T>` for repeated parameters, which it doesn't have. The predicates of `impl1` are only `T: Sized`, which is also a predicate of impl2`. So this specialization is sound.

## Extensions

Unfortunately not all specializations in the standard library are allowed by this. So there are two extensions to these rules that allow specializing on some traits.

### rustc_specialization_trait

If a trait is always applicable, then it's sound to specialize on it. We check trait is always applicable in the same way as impls, except that step 4 is now "all predicates on `impl1` are always applicable". We require that `specialization` or `min_specialization` is enabled to implement these traits.

### rustc_specialization_marker

There are also some specialization on traits with no methods, including the `FusedIterator` trait which is advertised as allowing optimizations. We allow marking marker traits with an unstable attribute that means we ignore them in point 3 of the checks above. This is unsound but 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.

r? @nikomatsakis
cc #31844 #67194
bors added a commit that referenced this issue Mar 16, 2020
Implement a feature for a sound specialization subset

This implements a new feature (`min_specialization`) that restricts specialization to a subset that is reasonable for the standard library to use.

The plan is to then:

* Update `libcore` and `liballoc` to compile with `min_specialization`.
* Add a lint to forbid use of `feature(specialization)` (and other unsound, type system extending features) in the standard library.
* Fix the soundness issues around `specialization`.
* Remove `min_specialization`

The rest of this is an overview from a comment in this PR

## Basic approach

To enforce this requirement on specializations we take the following approach:
1. Match up the substs for `impl2` so that the implemented trait and self-type match those for `impl1`.
2. Check for any direct use of `'static` in the substs of `impl2`.
3. Check that all of the generic parameters of `impl1` occur at most once in the *unconstrained* substs for `impl2`. A parameter is constrained if its value is completely determined by an associated type projection predicate.
4. Check that all predicates on `impl1` also exist on `impl2` (after matching substs).

## Example

Suppose we have the following always applicable impl:

```rust
impl<T> SpecExtend<T> for std::vec::IntoIter<T> { /* specialized impl */ }
impl<T, I: Iterator<Item=T>> SpecExtend<T> for I { /* default impl */ }
```

We get that the subst for `impl2` are `[T, std::vec::IntoIter<T>]`. `T` is constrained to be `<I as Iterator>::Item`, so we check only `std::vec::IntoIter<T>` for repeated parameters, which it doesn't have. The predicates of `impl1` are only `T: Sized`, which is also a predicate of impl2`. So this specialization is sound.

## Extensions

Unfortunately not all specializations in the standard library are allowed by this. So there are two extensions to these rules that allow specializing on some traits.

### rustc_specialization_trait

If a trait is always applicable, then it's sound to specialize on it. We check trait is always applicable in the same way as impls, except that step 4 is now "all predicates on `impl1` are always applicable". We require that `specialization` or `min_specialization` is enabled to implement these traits.

### rustc_specialization_marker

There are also some specialization on traits with no methods, including the `FusedIterator` trait which is advertised as allowing optimizations. We allow marking marker traits with an unstable attribute that means we ignore them in point 3 of the checks above. This is unsound but 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.

r? @nikomatsakis
cc #31844 #67194
Amanieu added a commit to Amanieu/hashbrown that referenced this issue Apr 25, 2020
Amanieu added a commit to Amanieu/hashbrown that referenced this issue Apr 25, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
A-specialization C-bug E-help-wanted E-medium I-unsound P-high T-compiler T-libs-api
Projects
None yet
Development

Successfully merging a pull request may close this issue.