PartialEq implementation for RangeInclusive is unsound

[sugar700]

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]

cc #45982

rust/src/libcore/ops/range.rs

Lines 347 to 363 in 883b6aa

	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]

Seems to be an nll issue:

rustup override set 1.34.0
cargo run # <- errors
vim Cargo.toml # comment out the edition line
cargo run # <- works

This doesn't work with the newest version, because NLL was enabled in 2015 mode as well (CMIIW)

So I don't think it's a A-specialization thing @jonas-schievink

[jonas-schievink]

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]

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

[sugar700]

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]

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.

[nikomatsakis]

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]

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

[matthewjasper]

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,