Ordering for Set and Map is not what's expected

[udoprog]

See comment.

This primarily stems from how the ordering implementation for Option is derived:

#[derive(PartialEq, PartialOrd)]
enum Foo {
    First,
    Second,
}

fn main() {
    assert!(Foo::First < Foo::Second);
    assert!([Some(Foo::First), None] > [None, Some(Foo::Second)]);
}

Without such a definition, some form of wrapper would be needed to change how ordering is done. But any such abstractions also cause issues with potential optimization opportunities.

However it's done, it will become part of the public API of this crate.

[pitaj]

Should we even implement Ord and PartialOrd? HashSet and HashMap don't. Given we don't necessarily store the set and map in Ord order, we essentially have to reorder before we do the compare.

Consider that BTreeMap and BTreeSet just do self.iter().cmp(other.iter()). I find it a little weird because that means BTreeSet[1, 2, 3, 4] < BTreeSet[1, 4]

[pitaj]

I think we'd have to generically implement Ord something like this to match the behavior of BTreeSet. Of course it would be much more complicated for non-unit enums.

static KEYS_ORDERED: Lazy<[KeyOOO; 5]> = Lazy::new(|| {
    let mut keys = [
        KeyOOO::Four,
        KeyOOO::One,
        KeyOOO::Three,
        KeyOOO::Five,
        KeyOOO::Two,
    ];
    keys.sort_unstable();
    keys
});

impl Ord for Set {
    fn cmp(&self, other: &Self) -> Ordering {
        static KEYS_ORDERED: Lazy<[KeyOOO; 5]> = Lazy::new(|| {
            let mut keys = [
                KeyOOO::Four,
                KeyOOO::One,
                KeyOOO::Three,
                KeyOOO::Five,
                KeyOOO::Two,
            ];
            keys.sort_unstable();
            keys
        });

        let self_iter = KEYS_ORDERED.iter().filter(|&&key| self.contains(key));
        let other_iter = KEYS_ORDERED.iter().filter(|&&key| other.contains(key));

        self_iter.cmp(other_iter)
    }
}

[udoprog]

Keys and their associated storage are very much expected to be strictly ordered in their definition order. The corollary I keep in mind here is a comparison with [Option<Value>; N] and Key is strictly being used to index into it (any enum and their variants makes this a bit more complicated, but the idea should still hold).

We should probably not attempt to abide by any particular PartialOrd or Ord implementations, since there is no reliable or good way to make use of that when building specialized storage through the macro.

[pitaj]

Maybe we should require that PartialOrd and Ord are derived in order to implement Ord and PartialOrd for Storage. I'm pretty sure it's possible to detect the presence of a given derive, because the compiler does it for derive(Copy, Clone), but maybe not.

[pitaj]

Okay so it looks like, assuming data is in the correct order, we could just implement Ord like this for unit enums:

impl<V: Ord> Ord for Storage<V> {
    fn cmp(&self, other: &Self) -> Ordering {
        self.data
            .iter()
            .enumerate()
            .filter(|(_, x)| x.is_some())
            .cmp(
                other.data
                    .iter()
                    .enumerate()
                    .filter(|(_, x)| x.is_some())
            )
    }
}

[pitaj]

Another thing: I don't know if there's a way to use a custom option enum to make this work. In your playground posted to the PR, the following passes:

assert!([Option::Some(Foo::First), Option::None] < [Option::None, Option::None]);

Which is obviously not what we want.

[udoprog]

I'm trying out a solution in #39. I went down the route of trying to make a custom Option enum for storage, but that is not a tenable solution. For that a lot of stuff would have to be implemented in ways which inevitably would lead to harder to optimize code (mainly iterators).

[udoprog]

assert!([Option::Some(Foo::First), Option::None], [Option::None, Option::None]);

Accidentally an operator?

[pitaj]

Ah sorry yeah, I was typing on my phone. Fixed now.