Tuple unions created by proptest_derive should branch out more (stack overflow while generating values)

[sunshowers]

Hi again! ☺️

So it turns out that we have an enum with 70+ different variants, and it's large enough that generating values for it appears to cause a stack overflow with the default Rust stack size 😕

At the moment, when there are a large number of variants, proptest_derive will create essentially a linear structure. For variants v<n>, the structure looks like:

[v0, v1, v2, v3, ... v8, ___ ]
                          |
                          v
                         [v9, v10, v11, ...]

and so on. Instead, what we could do is a bit more branchy:

[ ______________ , _______________ , ...]
       |                  |
       v                  v
[v0, v1, v2, ...] [v10, v11, v12, ...]

There are several possible distributions we could use, e.g. an exponential distribution (1 variant in the first slot, 2 in the second slot and so on). I'd love to hear your opinions on it! Thank you 😀

This isn't a problem with prop_oneof! since it just uses the Union strategy past 10 variants.

[sunshowers]

I might give implementing this a shot if I have free time soon.

[Centril]

(Might also be relevant to #151, cc @alessandrod)

Well... this was unexpected (for me) =P
I'm curious to hear more about why (and where) the stack overflow happens.

Instead, what we could do is a bit more branchy:

Did you try the more branchy expansion in a manual implementation to see that the issue is resolved with that?

There are several possible distributions we could use, e.g. an exponential distribution (1 variant in the first slot, 2 in the second slot and so on). I'd love to hear your opinions on it! Thank you 😀

Here's two alternatives that come to mind (the invariant here is that we have max 3 slots):

[ ____________, v4]
       |
       v
  [v0, v1, v2]

[ ____________, ____________]
       |             |
       v             v
  [v0, v1, v2]   [v4, v5]

(this seems most even tho possibly less efficient due to never having shortcuts)

vs.

[ ________, ________]
     |         |
     v         v
  [v0, v1]  [v3, v4]

[ ____________, v4, v5]
       |
       v
  [v0, v1, v2]

(this seems simplest; tho you might want to mirror the to put "extras" to the right instead...)

[matthew-russo]

an interesting note. I had a pretty old toolchain (1.72 nightly) and could repro this. updating to 1.77 nightly turned the stack overflow in to a segfault. then if i removed a few variants from my test then it turned back in to a stack overflow.

segfault might be from overjumping the guard page?