1.98 beta regression: Behavior change involving comparisons

[theemathas]

Regression found in the 1.98 beta crater run.

[INFO] [stdout] thread 'example_part1' (1539) panicked at 2022/day13/src/main.rs:159:5:
[INFO] [stdout] assertion failed: PacketPair::new("[[1],[2,3,4]]", "[[1],4]").is_sorted()

• https://crater-reports.s3.amazonaws.com/beta-1.98-4/1.98.0-beta.1/gh/benallard.advent/log.txt

Edit: Also probably affects the spdx crate, which is quite popular. See #159519 (comment)

[theemathas]

Smaller reproducer (assertion fails in beta but not stable):

#[derive(PartialEq, Debug, Eq, Ord)]
enum PacketValue {
    Value(u32), // terminal
    Deeper(Packet),
}

impl PartialOrd for PacketValue {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        match (self, other) {
            (PacketValue::Value(a), PacketValue::Value(b)) => a.partial_cmp(b),
            (PacketValue::Deeper(a), PacketValue::Deeper(b)) => a.partial_cmp(b),
            (PacketValue::Value(a), PacketValue::Deeper(_b)) => PacketValue::Deeper(Packet {
                value: vec![PacketValue::Value(*a)],
            })
            .partial_cmp(other),
            (PacketValue::Deeper(_a), PacketValue::Value(b)) => {
                self.partial_cmp(&PacketValue::Deeper(Packet {
                    value: vec![PacketValue::Value(*b)],
                }))
            }
        }
    }
}

#[derive(PartialOrd, PartialEq, Debug, Ord, Eq)]
struct Packet {
    value: Vec<PacketValue>,
}

fn main() {
    use PacketValue::{Deeper, Value};
    assert!(
        Packet {
            value: vec![Deeper(Packet {
                value: vec![Value(2), Value(3), Value(4)]
            })]
        } < Packet {
            value: vec![Value(4)]
        }
    );
}

[theemathas]

Bisection results:

searched toolchains e96c36b6f76833388c519561d145492d2c08db4e through 7148b31956911d5d5496900bf564ca5212bf199b


********************************************************************************
Regression in dd8b2d6162c5616d7030238c29f892a431093cdd
********************************************************************************

Attempting to search unrolled perf builds
ERROR: couldn't find perf build comment

Regressed in #155598. cc @makai410 @nnethercote

[theemathas]

This might also affect the spdx crate (which is quite a popular crate), although I have not yet investigated in detail.

Relevant source code. Error log

[lukaslueg]

If I read #155598 correctly, it only checks the outer container (Packet in this case) for if their PartialOrd+Ord are derived. But PacketValue's PartialOrd impl is incompatible to a derived Ord to begin with, because the last two match arms lift Deeper above what a derived Ord does, which goes by order of declaration. That way, the combined manual PartialOrd + incompatible derived Ord from PacketValue creep into the derived Packet impls, where #155598 applies an optimization that it thinks is safe but actually isn't.

[asquared31415]

Minimized further:

#[derive(PartialEq, Debug, Eq, Ord)]
enum PacketValue {
    Value(u32),
    Deeper(u32),
}

impl PartialOrd for PacketValue {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        match (self, other) {
            (PacketValue::Deeper(a), PacketValue::Value(b)) => a.partial_cmp(b),
            _ => unreachable!(),
        }
    }
}

#[derive(PartialOrd, PartialEq, Debug, Ord, Eq)]
struct Packet {
    value: Vec<PacketValue>,
}

fn main() {
    use PacketValue::{Deeper, Value};
    // PASS
    assert!(Deeper(2) < Value(4));
    // PASS
    assert!(vec![Deeper(2)] < vec![Value(4)]);
    // FAILS on beta/nightly, when it should pass
    assert!(
        Packet {
            value: vec![Deeper(2)]
        } < Packet {
            value: vec![Value(4)]
        }
    );
}

EDIT: i'm not sure that the following is true, see my next comment

I'm going to take a guess that this Ord specialization for slices (used by Vec), is unsound:

rust/library/core/src/slice/cmp.rs

Lines 277 to 282 in b26c8ef

	#[doc(hidden)]
	#[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
	// intermediate trait for specialization of slice's Ord
	const trait SliceOrd: Sized {
	fn compare(left: &[Self], right: &[Self]) -> Ordering;
	}

and was only made visible (or only easily visible) with the changes to derive(Ord). There's a comment in that file about how the PartialOrd version is unsound.

[asquared31415]

Oh wait actually, is this just a violation of the PartialEq/PartialOrd relationship? Your minimized example derives PartialEq which means that values of PacketValue are only considered equal if and only if their discriminants are equal and their values are equal. Your minimization's PartialOrd however, can return Some(Equal) for values where that's not the case.

The PartialOrd docs say:

a == b if and only if partial_cmp(a, b) == Some(Equal).

And they even say:

It’s easy to accidentally make them disagree by deriving some of the traits and manually implementing others.

Maybe the specialization isn't unsound, but makes it easier to observe problematic behavior when the PartialOrd and PartialEq contract is violated.