Handling Arbitrary on structs containing the Never type (!)

[nipunn1313]

Hello! Here's a motivating example

fn main() {
    let x = any::<Wrapper<!>>();
}

#[derive(proptest_derive::Arbitrary, Debug)]
enum Wrapper<T> {
    A(T),
    B,
    C,
}

I'd like to be able to create such a Wrapper struct such that for Wrapper<!>, the proptest arbitrary picks between the other two options. This of course fails with

the trait `Arbitrary` is not implemented for `!`

Which makes sense! Impling arbitrary on ! doesn't particularly make sense since it can't be instantiated. Perhaps I can implement Arbitrary manually with separate impls for <T: Arbitrary> and T = !.

type WrapperStrategy<T: Arbitrary> = impl Strategy<Value = Wrapper<T>>;
impl<T: Arbitrary> Arbitrary for Wrapper<T> {
    type Parameters = T::Parameters;
    type Strategy = WrapperStrategy<T>;

    fn arbitrary_with(args: Self::Parameters) -> Self::Strategy {
        unimplemented!()
    }
}

impl Arbitrary for Wrapper<!> {
    type Parameters = ();
    type Strategy = WrapperStrategy<!>;

    fn arbitrary_with(args: Self::Parameters) -> Self::Strategy {
        unimplemented!()
    }
}

Unfortunately, this also doesn't work because

19 | impl<T: Arbitrary> Arbitrary for Wrapper<T> {
   | ------------------------------------------- first implementation here
...
28 | impl Arbitrary for Wrapper<!> {
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ conflicting implementation for `Wrapper<!>`
   |
   = note: upstream crates may add a new impl of trait `_IMPL_ARBITRARY_FOR_Wrapper::_proptest::arbitrary::Arbitrary` for type `!` in future versions

I briefly tried using https://doc.rust-lang.org/beta/unstable-book/language-features/negative-impls.html to impl !Arbitrary for ! {} - but this does not work for avoiding this coherence detection.

Any ideas on how this could work?
Perhaps proptest_derive could be augmented to detect this scenario and loosen the requirement that T: Arbitrary. Another idea could be something in the same vein as #[proptest(skip)] on Wrapper::A(T) that only skips it for the uninhabited case.

[matthew-russo]

I think you're looking to restrict generation to just the two variants that don't contain a T which can be done via

#![feature(never_type)]

#[derive(proptest_derive::Arbitrary, Debug)]
enum Wrapper<T> {
    A(T),
    B,
    C,
}

fn main() {
    let x = proptest::prop_oneof![
        Just(Wrapper::<!>::B),
        Just(Wrapper::<!>::C),
    ];
}

does this address your use case or is there some dependency between Arbitrary and the use of ! for your use case?

[nipunn1313]

Ideally, we're able to instantiate both Wrapper<!> and an inhabited variant (eg Wrapper<String>).

For the Wrapper<String> - I'd want arbitrary to pick from all of the choices, and for the Wrapper<!> - I'd want it to pick from the two inhabited choices.

It is possible (as you mentioned) to make two different strategies, but it doesn't seem possible to impl Arbitrary for Wrapper<!>. My codebase uses both Wrapper<String> and Wrapper<!> in many places. It would be possible (but annoying) to override the arbitrary strategy - but it would be nicer to be able to impl Arbitrary.

One workaround is to make our own never type - then it allows impling arbitrary.

#[derive(Clone, Debug)]
enum Never {}
impl Arbitrary for Wrapper<Never> {
    type Parameters = ();
    type Strategy = impl Strategy<Value = Self>;

    fn arbitrary_with(args: Self::Parameters) -> Self::Strategy {
        proptest::sample::select(vec![
            Wrapper::<Never>::B,
            Wrapper::<Never>::C,
        ])
    }
}

I think it would be nice if we could get proptest-rs to work nicely with coherence rules to allow for impl Arbitrary for Wrapper<!>. I think this could be possible with both

• Negative impls integrated into coherence rust-lang/negative-impls-initiative#1
• Adding a negative trait impl - impl !Arbitrary for ! to the proptest-rs crate, thus promising that proptest-rs will never impl Arbitrary for !.

I also additionally think it would be nice if #[derive(Arbitrary)] supported cases where ! was a type param, though I suspect that would be difficult to implement.

[matthew-russo]

I see. I think a negative impl for ! is reasonable given its impossible to generate a value.

I also additionally think it would be nice if #[derive(Arbitrary)] supported cases where ! was a type param, though I suspect that would be difficult to implement.

I'm not as convinced on adding this to the derive impl at the moment but I'll think it over a bit more

[matthew-russo]

Let me know if this works for you. you'll need to use proptest with features unstable and never-arbitrary