Strategy::prop_and_then for composing strategies

danburkert commented 6 years ago

It would be nice to have the equivalent of {Option, Future}::and_then for composing Strategies. Composition can already be done via prop_compose! (which is probably more flexible), but for simply gluing together two strategies in a straight line and_then can be more straightforward and readable. Here's a sketch of what the API might look like:

    /// Returns a strategy which chains another strategy produced by `f` to this one.
    ///
    /// TODO: describe shrinking behavior
    fn prop_and_then<T, U, F>(self, f: F) -> AndThen<Self, U>
    where
        U: Strategy<Value=T>,
        F: FnOnce(Self::Value) -> U
    {
        ...
    }

AltSysrq commented 6 years ago

I believe prop_flat_map is what you are looking for.

danburkert commented 6 years ago

@AltSysrq

Thanks, that's what I was looking for. Question about the shrinking behavior of prop_flat_map -- it appears that it prefers to shrink the inner (second) strategy fully before attempting to shrink the outer (first) strategy.

Is there a way to flip this behavior and shrink the outer strategy fully before attempting to shrink the inner strategy? I realize doing this wouldn't work for every application, but when it's possible it should reduce the search space considerably. I've seen prop_ind_flat_map, but it doesn't appear to be doing what I want.

As an example, let's try to generate two sequences of 'words', with the first sequence containing between 1 and 10 words, and with the additional constraint that the total number of words across both sequences not exceed 20. This is my best shot at implementing this:

            #[test]
            fn word_sequences(vectors in (
                    (1usize..=10)
                        .prop_ind_flat_map2(|left_size| 0usize..(20 - left_size))
                        .prop_flat_map(|(left_size, right_size)| (proptest::collection::vec("[a-z]{1, 4}", left_size),
                                                                  proptest::collection::vec("[a-z]{1, 4}", right_size)))
                    )) {
                let _ = env_logger::try_init();
                info!("({}/{}): {:?}", vectors.0.len(), vectors.1.len(), vectors);
                panic!()
            }

which results in the following shrink sequences:

 (3/11): (["vtdh", "amch", "aw"], ["d", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["tdh", "amch", "aw"], ["d", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["dh", "amch", "aw"], ["d", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["h", "amch", "aw"], ["d", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["d", "amch", "aw"], ["d", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["b", "amch", "aw"], ["d", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "amch", "aw"], ["d", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "mch", "aw"], ["d", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "ch", "aw"], ["d", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "h", "aw"], ["d", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "d", "aw"], ["d", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "b", "aw"], ["d", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "a", "aw"], ["d", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "a", "w"], ["d", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "a", "l"], ["d", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "a", "f"], ["d", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "a", "c"], ["d", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "a", "b"], ["d", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "a", "a"], ["d", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "a", "a"], ["b", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "a", "a"], ["a", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "a", "a"], ["a", "da", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "a", "a"], ["a", "a", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "a", "a"], ["a", "a", "fn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "a", "a"], ["a", "a", "n", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "a", "a"], ["a", "a", "g", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "a", "a"], ["a", "a", "d", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "a", "a"], ["a", "a", "b", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "a", "a"], ["a", "a", "a", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "a", "a"], ["a", "a", "a", "ss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "a", "a"], ["a", "a", "a", "s", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "a", "a"], ["a", "a", "a", "j", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "a", "a"], ["a", "a", "a", "e", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "a", "a"], ["a", "a", "a", "c", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "a", "a"], ["a", "a", "a", "b", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "a", "a"], ["a", "a", "a", "a", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "a", "a"], ["a", "a", "a", "a", "cys", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "a", "a"], ["a", "a", "a", "a", "ys", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "a", "a"], ["a", "a", "a", "a", "s", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "a", "a"], ["a", "a", "a", "a", "j", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "a", "a"], ["a", "a", "a", "a", "e", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "a", "a"], ["a", "a", "a", "a", "c", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "a", "a"], ["a", "a", "a", "a", "b", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "yrd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "rd", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "d", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "b", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "a", "zd", "cvb", "e", "l", "w"])
 (3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "a", "d", "cvb", "e", "l", "w"])
 (3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "a", "b", "cvb", "e", "l", "w"])
 (3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "a", "a", "cvb", "e", "l", "w"])
 (3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "a", "a", "vb", "e", "l", "w"])
 (3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "a", "a", "b", "e", "l", "w"])
 (3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "e", "l", "w"])
 (3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "c", "l", "w"])
 (3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "b", "l", "w"])
 (3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "l", "w"])
 (3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "f", "w"])
 (3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "c", "w"])
 (3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "b", "w"])
 (3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "w"])
 (3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "l"])
 (3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "f"])
 (3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "c"])
 (3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "b"])
 (3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a"])
 (2/11): (["wfgz", "hhhp"], ["dito", "xxsw", "guel", "uqh", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["fgz", "hhhp"], ["dito", "xxsw", "guel", "uqh", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["gz", "hhhp"], ["dito", "xxsw", "guel", "uqh", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["z", "hhhp"], ["dito", "xxsw", "guel", "uqh", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["m", "hhhp"], ["dito", "xxsw", "guel", "uqh", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["g", "hhhp"], ["dito", "xxsw", "guel", "uqh", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["d", "hhhp"], ["dito", "xxsw", "guel", "uqh", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["b", "hhhp"], ["dito", "xxsw", "guel", "uqh", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "hhhp"], ["dito", "xxsw", "guel", "uqh", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "hhp"], ["dito", "xxsw", "guel", "uqh", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "hp"], ["dito", "xxsw", "guel", "uqh", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "p"], ["dito", "xxsw", "guel", "uqh", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "h"], ["dito", "xxsw", "guel", "uqh", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "d"], ["dito", "xxsw", "guel", "uqh", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "b"], ["dito", "xxsw", "guel", "uqh", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["dito", "xxsw", "guel", "uqh", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["ito", "xxsw", "guel", "uqh", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["to", "xxsw", "guel", "uqh", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["o", "xxsw", "guel", "uqh", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["h", "xxsw", "guel", "uqh", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["d", "xxsw", "guel", "uqh", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["b", "xxsw", "guel", "uqh", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "xxsw", "guel", "uqh", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "xsw", "guel", "uqh", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "sw", "guel", "uqh", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "w", "guel", "uqh", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "l", "guel", "uqh", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "f", "guel", "uqh", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "c", "guel", "uqh", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "b", "guel", "uqh", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "guel", "uqh", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "uel", "uqh", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "el", "uqh", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "l", "uqh", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "f", "uqh", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "c", "uqh", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "b", "uqh", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "uqh", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "qh", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "h", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "d", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "b", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "nutt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "utt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "tt", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "t", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "j", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "e", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "c", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "b", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "a", "try", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "a", "ry", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "a", "y", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "a", "m", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "a", "g", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "a", "d", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "a", "b", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "a", "a", "oeh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "a", "a", "eh", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "a", "a", "h", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "a", "a", "d", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "a", "a", "b", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "a", "a", "a", "yr", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "a", "a", "a", "r", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "a", "a", "a", "i", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "a", "a", "a", "e", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "a", "a", "a", "c", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "a", "a", "a", "b", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "xtn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "tn", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "n", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "g", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "d", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "b", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "n", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "g", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "d", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "b", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "bwk"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "wk"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "k"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "f"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "c"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "b"])
 (2/11): (["a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a"])
 (1/11): (["k"], ["azf", "ws", "iwl", "rmq", "ad", "a", "qilt", "btwn", "iaad", "z", "xxbh"])
 (1/11): (["f"], ["azf", "ws", "iwl", "rmq", "ad", "a", "qilt", "btwn", "iaad", "z", "xxbh"])
 (1/11): (["c"], ["azf", "ws", "iwl", "rmq", "ad", "a", "qilt", "btwn", "iaad", "z", "xxbh"])
 (1/11): (["b"], ["azf", "ws", "iwl", "rmq", "ad", "a", "qilt", "btwn", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["azf", "ws", "iwl", "rmq", "ad", "a", "qilt", "btwn", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["zf", "ws", "iwl", "rmq", "ad", "a", "qilt", "btwn", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["f", "ws", "iwl", "rmq", "ad", "a", "qilt", "btwn", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["c", "ws", "iwl", "rmq", "ad", "a", "qilt", "btwn", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["b", "ws", "iwl", "rmq", "ad", "a", "qilt", "btwn", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["a", "ws", "iwl", "rmq", "ad", "a", "qilt", "btwn", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["a", "s", "iwl", "rmq", "ad", "a", "qilt", "btwn", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["a", "j", "iwl", "rmq", "ad", "a", "qilt", "btwn", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["a", "e", "iwl", "rmq", "ad", "a", "qilt", "btwn", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["a", "c", "iwl", "rmq", "ad", "a", "qilt", "btwn", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["a", "b", "iwl", "rmq", "ad", "a", "qilt", "btwn", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["a", "a", "iwl", "rmq", "ad", "a", "qilt", "btwn", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["a", "a", "wl", "rmq", "ad", "a", "qilt", "btwn", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["a", "a", "l", "rmq", "ad", "a", "qilt", "btwn", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["a", "a", "f", "rmq", "ad", "a", "qilt", "btwn", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["a", "a", "c", "rmq", "ad", "a", "qilt", "btwn", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["a", "a", "b", "rmq", "ad", "a", "qilt", "btwn", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["a", "a", "a", "rmq", "ad", "a", "qilt", "btwn", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["a", "a", "a", "mq", "ad", "a", "qilt", "btwn", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["a", "a", "a", "q", "ad", "a", "qilt", "btwn", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["a", "a", "a", "i", "ad", "a", "qilt", "btwn", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["a", "a", "a", "e", "ad", "a", "qilt", "btwn", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["a", "a", "a", "c", "ad", "a", "qilt", "btwn", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["a", "a", "a", "b", "ad", "a", "qilt", "btwn", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["a", "a", "a", "a", "ad", "a", "qilt", "btwn", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["a", "a", "a", "a", "d", "a", "qilt", "btwn", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["a", "a", "a", "a", "b", "a", "qilt", "btwn", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["a", "a", "a", "a", "a", "a", "qilt", "btwn", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["a", "a", "a", "a", "a", "a", "ilt", "btwn", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["a", "a", "a", "a", "a", "a", "lt", "btwn", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["a", "a", "a", "a", "a", "a", "t", "btwn", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["a", "a", "a", "a", "a", "a", "j", "btwn", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["a", "a", "a", "a", "a", "a", "e", "btwn", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["a", "a", "a", "a", "a", "a", "c", "btwn", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["a", "a", "a", "a", "a", "a", "b", "btwn", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["a", "a", "a", "a", "a", "a", "a", "btwn", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["a", "a", "a", "a", "a", "a", "a", "twn", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["a", "a", "a", "a", "a", "a", "a", "wn", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["a", "a", "a", "a", "a", "a", "a", "n", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["a", "a", "a", "a", "a", "a", "a", "g", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["a", "a", "a", "a", "a", "a", "a", "d", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["a", "a", "a", "a", "a", "a", "a", "b", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["a", "a", "a", "a", "a", "a", "a", "a", "iaad", "z", "xxbh"])
 (1/11): (["a"], ["a", "a", "a", "a", "a", "a", "a", "a", "aad", "z", "xxbh"])
 (1/11): (["a"], ["a", "a", "a", "a", "a", "a", "a", "a", "ad", "z", "xxbh"])
 (1/11): (["a"], ["a", "a", "a", "a", "a", "a", "a", "a", "d", "z", "xxbh"])
 (1/11): (["a"], ["a", "a", "a", "a", "a", "a", "a", "a", "b", "z", "xxbh"])
 (1/11): (["a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "z", "xxbh"])
 (1/11): (["a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "m", "xxbh"])
 (1/11): (["a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "g", "xxbh"])
 (1/11): (["a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "d", "xxbh"])
 (1/11): (["a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "b", "xxbh"])
 (1/11): (["a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "xxbh"])
 (1/11): (["a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "xbh"])
 (1/11): (["a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "bh"])
 (1/11): (["a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "h"])
 (1/11): (["a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "d"])
 (1/11): (["a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "b"])
 (1/11): (["a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a"])
 (1/5): (["gz"], ["ljs", "s", "zt", "rpqx", "ov"])
 (1/5): (["z"], ["ljs", "s", "zt", "rpqx", "ov"])
 (1/5): (["m"], ["ljs", "s", "zt", "rpqx", "ov"])
 (1/5): (["g"], ["ljs", "s", "zt", "rpqx", "ov"])
 (1/5): (["d"], ["ljs", "s", "zt", "rpqx", "ov"])
 (1/5): (["b"], ["ljs", "s", "zt", "rpqx", "ov"])
 (1/5): (["a"], ["ljs", "s", "zt", "rpqx", "ov"])
 (1/5): (["a"], ["js", "s", "zt", "rpqx", "ov"])
 (1/5): (["a"], ["s", "s", "zt", "rpqx", "ov"])
 (1/5): (["a"], ["j", "s", "zt", "rpqx", "ov"])
 (1/5): (["a"], ["e", "s", "zt", "rpqx", "ov"])
 (1/5): (["a"], ["c", "s", "zt", "rpqx", "ov"])
 (1/5): (["a"], ["b", "s", "zt", "rpqx", "ov"])
 (1/5): (["a"], ["a", "s", "zt", "rpqx", "ov"])
 (1/5): (["a"], ["a", "j", "zt", "rpqx", "ov"])
 (1/5): (["a"], ["a", "e", "zt", "rpqx", "ov"])
 (1/5): (["a"], ["a", "c", "zt", "rpqx", "ov"])
 (1/5): (["a"], ["a", "b", "zt", "rpqx", "ov"])
 (1/5): (["a"], ["a", "a", "zt", "rpqx", "ov"])
 (1/5): (["a"], ["a", "a", "t", "rpqx", "ov"])
 (1/5): (["a"], ["a", "a", "j", "rpqx", "ov"])
 (1/5): (["a"], ["a", "a", "e", "rpqx", "ov"])
 (1/5): (["a"], ["a", "a", "c", "rpqx", "ov"])
 (1/5): (["a"], ["a", "a", "b", "rpqx", "ov"])
 (1/5): (["a"], ["a", "a", "a", "rpqx", "ov"])
 (1/5): (["a"], ["a", "a", "a", "pqx", "ov"])
 (1/5): (["a"], ["a", "a", "a", "qx", "ov"])
 (1/5): (["a"], ["a", "a", "a", "x", "ov"])
 (1/5): (["a"], ["a", "a", "a", "l", "ov"])
 (1/5): (["a"], ["a", "a", "a", "f", "ov"])
 (1/5): (["a"], ["a", "a", "a", "c", "ov"])
 (1/5): (["a"], ["a", "a", "a", "b", "ov"])
 (1/5): (["a"], ["a", "a", "a", "a", "ov"])
 (1/5): (["a"], ["a", "a", "a", "a", "v"])
 (1/5): (["a"], ["a", "a", "a", "a", "k"])
 (1/5): (["a"], ["a", "a", "a", "a", "f"])
 (1/5): (["a"], ["a", "a", "a", "a", "c"])
 (1/5): (["a"], ["a", "a", "a", "a", "b"])
 (1/5): (["a"], ["a", "a", "a", "a", "a"])
 (1/2): (["yw"], ["pfop", "wfnf"])
 (1/2): (["w"], ["pfop", "wfnf"])
 (1/2): (["l"], ["pfop", "wfnf"])
 (1/2): (["f"], ["pfop", "wfnf"])
 (1/2): (["c"], ["pfop", "wfnf"])
 (1/2): (["b"], ["pfop", "wfnf"])
 (1/2): (["a"], ["pfop", "wfnf"])
 (1/2): (["a"], ["fop", "wfnf"])
 (1/2): (["a"], ["op", "wfnf"])
 (1/2): (["a"], ["p", "wfnf"])
 (1/2): (["a"], ["h", "wfnf"])
 (1/2): (["a"], ["d", "wfnf"])
 (1/2): (["a"], ["b", "wfnf"])
 (1/2): (["a"], ["a", "wfnf"])
 (1/2): (["a"], ["a", "fnf"])
 (1/2): (["a"], ["a", "nf"])
 (1/2): (["a"], ["a", "f"])
 (1/2): (["a"], ["a", "c"])
 (1/2): (["a"], ["a", "b"])
 (1/2): (["a"], ["a", "a"])
 (1/1): (["zoyw"], ["zpr"])
 (1/1): (["oyw"], ["zpr"])
 (1/1): (["yw"], ["zpr"])
 (1/1): (["w"], ["zpr"])
 (1/1): (["l"], ["zpr"])
 (1/1): (["f"], ["zpr"])
 (1/1): (["c"], ["zpr"])
 (1/1): (["b"], ["zpr"])
 (1/1): (["a"], ["zpr"])
 (1/1): (["a"], ["pr"])
 (1/1): (["a"], ["r"])
 (1/1): (["a"], ["i"])
 (1/1): (["a"], ["e"])
 (1/1): (["a"], ["c"])
 (1/1): (["a"], ["b"])
 (1/1): (["a"], ["a"])
 (1/0): (["q"], [])
 (1/0): (["i"], [])
 (1/0): (["e"], [])
 (1/0): (["c"], [])
 (1/0): (["b"], [])
 (1/0): (["a"], [])

As you can see, the inner word strategies are still getting shrunk first. If you substitute prop_ind_flat_map for prop_flat_map, the sequence lengths are never shrunk:

(3/11): (["vtdh", "amch", "aw"], ["d", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["tdh", "amch", "aw"], ["d", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["dh", "amch", "aw"], ["d", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["h", "amch", "aw"], ["d", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["d", "amch", "aw"], ["d", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["b", "amch", "aw"], ["d", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "amch", "aw"], ["d", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "mch", "aw"], ["d", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "ch", "aw"], ["d", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "h", "aw"], ["d", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "d", "aw"], ["d", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "b", "aw"], ["d", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "a", "aw"], ["d", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "a", "w"], ["d", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "a", "l"], ["d", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "a", "f"], ["d", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "a", "c"], ["d", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "a", "b"], ["d", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "a", "a"], ["d", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "a", "a"], ["b", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "a", "a"], ["a", "jda", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "a", "a"], ["a", "da", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "a", "a"], ["a", "a", "yfn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "a", "a"], ["a", "a", "fn", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "a", "a"], ["a", "a", "n", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "a", "a"], ["a", "a", "g", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "a", "a"], ["a", "a", "d", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "a", "a"], ["a", "a", "b", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "a", "a"], ["a", "a", "a", "sss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "a", "a"], ["a", "a", "a", "ss", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "a", "a"], ["a", "a", "a", "s", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "a", "a"], ["a", "a", "a", "j", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "a", "a"], ["a", "a", "a", "e", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "a", "a"], ["a", "a", "a", "c", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "a", "a"], ["a", "a", "a", "b", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "a", "a"], ["a", "a", "a", "a", "hcys", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "a", "a"], ["a", "a", "a", "a", "cys", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "a", "a"], ["a", "a", "a", "a", "ys", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "a", "a"], ["a", "a", "a", "a", "s", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "a", "a"], ["a", "a", "a", "a", "j", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "a", "a"], ["a", "a", "a", "a", "e", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "a", "a"], ["a", "a", "a", "a", "c", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "a", "a"], ["a", "a", "a", "a", "b", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "yrd", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "rd", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "d", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "b", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "a", "zd", "cvb", "e", "l", "w"])
(3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "a", "d", "cvb", "e", "l", "w"])
(3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "a", "b", "cvb", "e", "l", "w"])
(3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "a", "a", "cvb", "e", "l", "w"])
(3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "a", "a", "vb", "e", "l", "w"])
(3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "a", "a", "b", "e", "l", "w"])
(3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "e", "l", "w"])
(3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "c", "l", "w"])
(3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "b", "l", "w"])
(3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "l", "w"])
(3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "f", "w"])
(3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "c", "w"])
(3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "b", "w"])
(3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "w"])
(3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "l"])
(3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "f"])
(3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "c"])
(3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "b"])
(3/11): (["a", "a", "a"], ["a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a"])

AltSysrq commented 6 years ago

Is there a way to flip this behavior and shrink the outer strategy fully before attempting to shrink the inner strategy?

Not currently. It's probably possible to add, but I'll need a bit more time to think about it.

If you substitute prop_ind_flat_map for prop_flat_map, the sequence lengths are never shrunk:

That's because prop_ind_flat_map() does not allow the LHS strategy to shrink. It would do something closer to what you want if you used 0..=left_size and 0..=right_size for your vec strategies.

In a lot of cases, it's possible to move things around and reduce dependencies on prop_flat_map. I can't speculate as to whether that is true for your actual code, but your example strategy could be expressed as

vectors in
  prop::collection::vec("[a-z]{1, 4}", 0..=10)
  .prop_flat_map(|left| {
    let left_len = left.len();
    (Just(left), prop::collection::vec("[a-z]{1,4}", 0..20-left_len))
  })

danburkert commented 6 years ago

but your example strategy could be expressed as

That shrinks to the correct simplified answer, but it's still shrinking from the inside out, so it goes through a lot more iterations than necessary:

(6/8): (["j", "t", "pfv", "g", "grp", "hvbq"], ["ass", "ig", "xp", "gq", "jwck", "ri", "dv", "o"])                               
(6/7): (["j", "t", "pfv", "g", "grp", "hvbq"], ["ig", "xp", "gq", "jwck", "ri", "dv", "o"])                                      
(6/6): (["j", "t", "pfv", "g", "grp", "hvbq"], ["xp", "gq", "jwck", "ri", "dv", "o"])                                            
(6/5): (["j", "t", "pfv", "g", "grp", "hvbq"], ["gq", "jwck", "ri", "dv", "o"])                                                  
(6/4): (["j", "t", "pfv", "g", "grp", "hvbq"], ["jwck", "ri", "dv", "o"])                                                        
(6/3): (["j", "t", "pfv", "g", "grp", "hvbq"], ["ri", "dv", "o"])                                                                
(6/2): (["j", "t", "pfv", "g", "grp", "hvbq"], ["dv", "o"])                                                                      
(6/1): (["j", "t", "pfv", "g", "grp", "hvbq"], ["o"])                                                                            
(6/0): (["j", "t", "pfv", "g", "grp", "hvbq"], [])                                                                               
(5/1): (["t", "pfv", "g", "grp", "hvbq"], ["bpa"])                                                                               
(5/0): (["t", "pfv", "g", "grp", "hvbq"], [])                                                                                    
(4/2): (["pfv", "g", "grp", "hvbq"], ["scp", "g"])                                                                               
(4/1): (["pfv", "g", "grp", "hvbq"], ["g"])                                                                                      
(4/0): (["pfv", "g", "grp", "hvbq"], [])                                                                                         
(3/4): (["g", "grp", "hvbq"], ["fy", "zxf", "o", "cd"])                                                                          
(3/3): (["g", "grp", "hvbq"], ["zxf", "o", "cd"])                                                                                
(3/2): (["g", "grp", "hvbq"], ["o", "cd"])                                                                                       
(3/1): (["g", "grp", "hvbq"], ["cd"])                                                                                            
(3/0): (["g", "grp", "hvbq"], [])                                                                                                
(2/10): (["grp", "hvbq"], ["m", "u", "zhct", "afs", "hr", "xy", "moe", "ulla", "u", "pvn"])                                      
(2/9): (["grp", "hvbq"], ["u", "zhct", "afs", "hr", "xy", "moe", "ulla", "u", "pvn"])                                            
(2/8): (["grp", "hvbq"], ["zhct", "afs", "hr", "xy", "moe", "ulla", "u", "pvn"])                                                 
(2/7): (["grp", "hvbq"], ["afs", "hr", "xy", "moe", "ulla", "u", "pvn"])                                                         
(2/6): (["grp", "hvbq"], ["hr", "xy", "moe", "ulla", "u", "pvn"])                                                                
(2/5): (["grp", "hvbq"], ["xy", "moe", "ulla", "u", "pvn"])                                                                      
(2/4): (["grp", "hvbq"], ["moe", "ulla", "u", "pvn"])                                                                            
(2/3): (["grp", "hvbq"], ["ulla", "u", "pvn"])                                                                                   
(2/2): (["grp", "hvbq"], ["u", "pvn"])                                                                                           
(2/1): (["grp", "hvbq"], ["pvn"])                                                                                                
(2/0): (["grp", "hvbq"], [])                                                                                                     
(1/17): (["hvbq"], ["rn", "dhph", "as", "yi", "ip", "dyt", "sp", "mc", "w", "recz", "c", "j", "hpi", "kdk", "eh", "vb", "kwrn"]) 
(1/16): (["hvbq"], ["dhph", "as", "yi", "ip", "dyt", "sp", "mc", "w", "recz", "c", "j", "hpi", "kdk", "eh", "vb", "kwrn"])       
(1/15): (["hvbq"], ["as", "yi", "ip", "dyt", "sp", "mc", "w", "recz", "c", "j", "hpi", "kdk", "eh", "vb", "kwrn"])               
(1/14): (["hvbq"], ["yi", "ip", "dyt", "sp", "mc", "w", "recz", "c", "j", "hpi", "kdk", "eh", "vb", "kwrn"])                     
(1/13): (["hvbq"], ["ip", "dyt", "sp", "mc", "w", "recz", "c", "j", "hpi", "kdk", "eh", "vb", "kwrn"])                           
(1/12): (["hvbq"], ["dyt", "sp", "mc", "w", "recz", "c", "j", "hpi", "kdk", "eh", "vb", "kwrn"])                                 
(1/11): (["hvbq"], ["sp", "mc", "w", "recz", "c", "j", "hpi", "kdk", "eh", "vb", "kwrn"])                                        
(1/10): (["hvbq"], ["mc", "w", "recz", "c", "j", "hpi", "kdk", "eh", "vb", "kwrn"])                                              
(1/9): (["hvbq"], ["w", "recz", "c", "j", "hpi", "kdk", "eh", "vb", "kwrn"])                                                     
(1/8): (["hvbq"], ["recz", "c", "j", "hpi", "kdk", "eh", "vb", "kwrn"])                                                          
(1/7): (["hvbq"], ["c", "j", "hpi", "kdk", "eh", "vb", "kwrn"])                                                                  
(1/6): (["hvbq"], ["j", "hpi", "kdk", "eh", "vb", "kwrn"])                                                                       
(1/5): (["hvbq"], ["hpi", "kdk", "eh", "vb", "kwrn"])                                                                            
(1/4): (["hvbq"], ["kdk", "eh", "vb", "kwrn"])                                                                                   
(1/3): (["hvbq"], ["eh", "vb", "kwrn"])                                                                                          
(1/2): (["hvbq"], ["vb", "kwrn"])                                                                                                
(1/1): (["hvbq"], ["kwrn"])                                                                                                      
(1/0): (["hvbq"], [])                                                                                                            
(1/8): (["vbq"], ["ubrd", "wahb", "eaxk", "k", "dzn", "gv", "x", "z"])                                                           
(1/7): (["vbq"], ["wahb", "eaxk", "k", "dzn", "gv", "x", "z"])                                                                   
(1/6): (["vbq"], ["eaxk", "k", "dzn", "gv", "x", "z"])                                                                           
(1/5): (["vbq"], ["k", "dzn", "gv", "x", "z"])                                                                                   
(1/4): (["vbq"], ["dzn", "gv", "x", "z"])                                                                                        
(1/3): (["vbq"], ["gv", "x", "z"])                                                                                               
(1/2): (["vbq"], ["x", "z"])                                                                                                     
(1/1): (["vbq"], ["z"])                                                                                                          
(1/0): (["vbq"], [])                                                                                                             
(1/7): (["bq"], ["nrjn", "wdr", "uhxj", "wd", "v", "n", "qwvf"])                                                                 
(1/6): (["bq"], ["wdr", "uhxj", "wd", "v", "n", "qwvf"])                                                                         
(1/5): (["bq"], ["uhxj", "wd", "v", "n", "qwvf"])                                                                                
(1/4): (["bq"], ["wd", "v", "n", "qwvf"])                                                                                        
(1/3): (["bq"], ["v", "n", "qwvf"])                                                                                              
(1/2): (["bq"], ["n", "qwvf"])                                                                                                   
(1/1): (["bq"], ["qwvf"])                                                                                                        
(1/0): (["bq"], [])                                                                                                              
(1/13): (["q"], ["gxsq", "ynid", "dd", "b", "opo", "rl", "as", "a", "zlf", "h", "kee", "ak", "qgyp"])                            
(1/12): (["q"], ["ynid", "dd", "b", "opo", "rl", "as", "a", "zlf", "h", "kee", "ak", "qgyp"])                                    
(1/11): (["q"], ["dd", "b", "opo", "rl", "as", "a", "zlf", "h", "kee", "ak", "qgyp"])                                            
(1/10): (["q"], ["b", "opo", "rl", "as", "a", "zlf", "h", "kee", "ak", "qgyp"])                                                  
(1/9): (["q"], ["opo", "rl", "as", "a", "zlf", "h", "kee", "ak", "qgyp"])                                                        
(1/8): (["q"], ["rl", "as", "a", "zlf", "h", "kee", "ak", "qgyp"])                                                               
(1/7): (["q"], ["as", "a", "zlf", "h", "kee", "ak", "qgyp"])                                                                     
(1/6): (["q"], ["a", "zlf", "h", "kee", "ak", "qgyp"])                                                                           
(1/5): (["q"], ["zlf", "h", "kee", "ak", "qgyp"])                                                                                
(1/4): (["q"], ["h", "kee", "ak", "qgyp"])                                                                                       
(1/3): (["q"], ["kee", "ak", "qgyp"])                                                                                            
(1/2): (["q"], ["ak", "qgyp"])                                                                                                   
(1/1): (["q"], ["qgyp"])                                                                                                         
(1/0): (["q"], [])                                                                                                               
(1/5): (["i"], ["rnp", "aii", "qz", "ecc", "doyx"])                                                                              
(1/4): (["i"], ["aii", "qz", "ecc", "doyx"])                                                                                     
(1/3): (["i"], ["qz", "ecc", "doyx"])                                                                                            
(1/2): (["i"], ["ecc", "doyx"])                                                                                                  
(1/1): (["i"], ["doyx"])                                                                                                         
(1/0): (["i"], [])                                                                                                               
(1/5): (["e"], ["lav", "wk", "nzd", "amu", "yrqc"])                                                                              
(1/4): (["e"], ["wk", "nzd", "amu", "yrqc"])                                                                                     
(1/3): (["e"], ["nzd", "amu", "yrqc"])                                                                                           
(1/2): (["e"], ["amu", "yrqc"])                                                                                                  
(1/1): (["e"], ["yrqc"])                                                                                                         
(1/0): (["e"], [])                                                                                                               
(1/6): (["c"], ["gye", "f", "kf", "cmx", "s", "etoj"])                                                                           
(1/5): (["c"], ["f", "kf", "cmx", "s", "etoj"])                                                                                  
(1/4): (["c"], ["kf", "cmx", "s", "etoj"])                                                                                       
(1/3): (["c"], ["cmx", "s", "etoj"])                                                                                             
(1/2): (["c"], ["s", "etoj"])                                                                                                    
(1/1): (["c"], ["etoj"])                                                                                                         
(1/0): (["c"], [])                                                                                                               
(1/1): (["b"], ["algh"])                                                                                                         
(1/0): (["b"], [])                                                                                                               
(1/6): (["a"], ["ftxq", "uw", "mceb", "p", "ucl", "pwp"])                                                                        
(1/5): (["a"], ["uw", "mceb", "p", "ucl", "pwp"])                                                                                
(1/4): (["a"], ["mceb", "p", "ucl", "pwp"])                                                                                      
(1/3): (["a"], ["p", "ucl", "pwp"])                                                                                              
(1/2): (["a"], ["ucl", "pwp"])                                                                                                   
(1/1): (["a"], ["pwp"])                                                                                                          
(1/0): (["a"], [])

My actual usecase is similar to this, but instead of the two shrinking dimensions these generated ascii word have, the types I'm generating have about 5 dimensions, so this inside out behavior is hugely impactful.

AltSysrq commented 6 years ago

Turns out there is a reason to do it in the order it is right now. When the LHS strategy of prop_flat_map is simplified, the RHS value needs to be generated from scratch, which necessitates a new random search of the value space to find a new failing test case. Since such a search isn't guaranteed to terminate, there's a counter before it gives up and reverts to the old LHS value; and to prevent exponential explosion due to chained prop_flat_map usages, that counter is shared over the whole test run, so shrinking the LHS first would just exhaust that almost immediately.

AltSysrq commented 6 years ago

but it's still shrinking from the inside out

I'm not sure I understand what you need here. Could you post a simplified example of what you'd like the shrinking sequence to be?

danburkert commented 6 years ago

Sure, going off your example I've gotten pretty close with this:

            #[test]
            fn word_sequences(vectors in proptest::collection::vec("[a-z]{1, 4}", 1..=10)
                              .prop_ind_flat_map2(|left| proptest::collection::vec("[a-z]{1, 4}", 0..(20 - left.len())))) {
                let _ = env_logger::try_init();
                info!("({}/{}): {:?}", vectors.0.len(), vectors.1.len(), vectors);
                panic!()
            }

which results in these cases:

(["hq", "cvtb", "vjk", "oi", "o", "eiy", "ne", "hllh", "e"], ["s", "zab", "ffm", "dwez", "al", "dph", "dv", "mwmr"])
(["cvtb", "vjk", "oi", "o", "eiy", "ne", "hllh", "e"], ["s", "zab", "ffm", "dwez", "al", "dph", "dv", "mwmr"])
(["vjk", "oi", "o", "eiy", "ne", "hllh", "e"], ["s", "zab", "ffm", "dwez", "al", "dph", "dv", "mwmr"])
(["oi", "o", "eiy", "ne", "hllh", "e"], ["s", "zab", "ffm", "dwez", "al", "dph", "dv", "mwmr"])
(["o", "eiy", "ne", "hllh", "e"], ["s", "zab", "ffm", "dwez", "al", "dph", "dv", "mwmr"])
(["eiy", "ne", "hllh", "e"], ["s", "zab", "ffm", "dwez", "al", "dph", "dv", "mwmr"])
(["ne", "hllh", "e"], ["s", "zab", "ffm", "dwez", "al", "dph", "dv", "mwmr"])
(["hllh", "e"], ["s", "zab", "ffm", "dwez", "al", "dph", "dv", "mwmr"])
(["e"], ["s", "zab", "ffm", "dwez", "al", "dph", "dv", "mwmr"])
(["c"], ["s", "zab", "ffm", "dwez", "al", "dph", "dv", "mwmr"])
(["b"], ["s", "zab", "ffm", "dwez", "al", "dph", "dv", "mwmr"])
(["a"], ["s", "zab", "ffm", "dwez", "al", "dph", "dv", "mwmr"])
(["a"], ["zab", "ffm", "dwez", "al", "dph", "dv", "mwmr"])
(["a"], ["ffm", "dwez", "al", "dph", "dv", "mwmr"])
(["a"], ["dwez", "al", "dph", "dv", "mwmr"])
(["a"], ["al", "dph", "dv", "mwmr"])
(["a"], ["dph", "dv", "mwmr"])
(["a"], ["dv", "mwmr"])
(["a"], ["mwmr"])
(["a"], [])

As you can see it converges much faster.

danburkert commented 6 years ago

The only thing left would be having it not re-generate each element when shrinking the vector. Perhaps I can just write my own shrinker since this seems to be pretty niche.

danburkert commented 6 years ago

The only thing left would be having it not re-generate each element when shrinking the vector.

Err wait, that's not happening. The vector appears to be shrinking by truncating the first element. That's great. I think this solution should work!

AltSysrq commented 6 years ago

Oh! Yeah, prop_ind_flat_map2 is probably what you want since your only constraint is held by the natural shrinking of the vectors. The reason it takes so long to converge with prop_flat_map() is that the system doesn't know that the strategy you return for ["b"] is in any way related to what you return for ["a"] (after all, you could do literally anything in your closure) so it has to start from scratch every time it shrinks the LHS.

The vector appears to be shrinking by truncating the first element.

Right. And if deleting the element causes the test to pass, it'll put it back in and move on to the next one.

There's also a .no_shrink() combinator should you find it helpful to prevent the elements of a vector from being shrunken before the vector itself starts shrinking.

danburkert commented 6 years ago

Great, thanks for the help!

proptest-rs / proptest

Strategy::prop_and_then for composing strategies #67