btree_map runs forever

[mimoo]

The proptest::collection::btree_map strategy runs in a loop. Simple example:

use std::collections::BTreeMap;
use proptest::{prelude::*, collection::btree_map};

#[derive(Debug)]
struct Thing {
    map: BTreeMap<u8, u8>,
}

prop_compose! {
    fn thing()(
        map in btree_map(any::<u8>(), any::<u8>(), 100),
    ) -> Thing {
        Thing {
            map,
        }
    }
}

proptest! {
    #[test]
    fn test_thing(stuff in thing()) {
        println!("{:?}", stuff);
    }
}

[mimoo]

OK I think it just takes a lot of time, but I'm wondering why would this simple example take so much time?

[Centril]

Can you elaborate on "a lot of time" (how much)?

From the, indeed simple, code you've posted, there's no reason why it should take a lot of time, but it's possible there's a bug of course (so I've marked as such preemptively).

[Eh2406]

How much does it change the time to switch from println to black_box(format? I wonder if it has to do with the 25000 lines of output

running 1 test
thread 'test_thing' panicked at 'Test aborted: Too many local rejects
        successes: 0
        local rejects: 65536
                65536 times at BTreeMap minimum size
        global rejects: 0
', src\main.rs:24:1
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
test test_thing ... FAILED

It takes some work to randomly sample 100 distinct u8s given there are only 256 of them. btree_map may need to be redesigned to not use rejection sampling.

[Centril]

The (only) rejection sampling that btree_map uses is for the minimum size, in case there were duplicate keys sampled:

pub fn btree_map<K: Strategy, V: Strategy>(
    key: K,
    value: V,
    size: impl Into<SizeRange>,
) -> BTreeMapStrategy<K, V>
where
    K::Value: Ord,
{
    let size = size.into();
    BTreeMapStrategy(statics::Filter::new(
        statics::Map::new(vec((key, value), size.clone()), VecToBTreeMap),
        "BTreeMap minimum size".into(),
        MinSize(size.start()),
    ))
}

One way to get rid of the rejection sampling is to continually sample additional elements until the minimum length has been reached (although there are infinite-loop hazards -- if the set of distinct values have cardinality 1 and 2 is the minimum, then that will never happen).