Long term plan: Investigate strategies for non-owned types

[Centril]

Currently, it is impossible to have a S: Strategy where ValueOf<S> is non-owned.

Examples:

1. We have a base strategy T where ValueOf<T> is owned, and then we use that to make a strategy where ValueOf<S> = &'a ValueOf<T> - This will not type check.
2. Derived types, for example: Cow<'a, X>.

Generally, I think that, any type that has a lifetime can't be generated.

Being able to generate types with lifetimes in them is however useful when you have lifetimes somewhere deep in the hierarchy of a type. To be able to do this soundly, the ValueTree must perhaps have a notion of Owned (which defaults to Value) in addition to Value (which may be borrowed). Then TestRunner will return the Owned type instead of Value, but the function under test receives Value.
I tried to implement this and got TestRunner to compile, but no strategies would compile.
Solving this may require generic associated types (GAT). I'll experiment with it once we have GAT in nightly.

There's also *const T and *mut T. While it is possible to give a sound strategy for these by Box::leak, this may cause problems since tests for large data types may leak huge amounts of memory. This could perhaps be mitigated by letting the ValueTree store the previous value of .current(), and whenever .current() happens, the old value is deallocated. The last value needs to be persisted in the TestRunner somehow if the entire ValueTree did not fail so that it can be cleared.

I'd like your thought's on the desirability of these features.

[AltSysrq]

I do think it'd be useful, but I also agree that this definitely requires GATs. (If trait aliases become a thing, there might also be a viable option of just adding a lifetime parameter to all the traits that most people wouldn't have to deal with.)

I think the problem bears a lot of similarity to "streaming iterators", so it might be best to wait and see how that gets solved and then follow suit.

[Centril]

Agreed, it is similar to streaming iterators. Once GATs lands I will do some prototyping on nightly to see how much the interface has to change to accommodate generation of borrowed types and how much we have to modify the strategies already provided.

If we find a good solution we can perhaps develop it as a separate branch and then merge it in once GATs for lifetimes are stabilized (which might be before GATs for types).

[Ten0]

Hmm while GATs may be the correct way to represent this, they look unlikely to be stabilized anytime soon, and I'm curious as to why this wouldn't work if Strategy and ValueTree were simply generic on 'a.
It feels to me it would work, with ValueTree holding the owned data and generating the non-owned structures on call to current. current on ValueTree would take &'a self.
We would always implement ValueTree and Strategy for every 'a and use for<'a> T: Strategy<'a> wherever required.

[adaszko]

It’d be lovely to revisit this issue now that GATs have been stabilized. Has anybody experimented with it? :)

EDIT: A bit about my use case: Due to proptest not supporting non-owned types, I’m unable to randomly generate a tree value whose nodes are allocated in an arena (bumpalo) because I can’t store &Child references in the node type. I’m forced to allocate with Box::new() and Vec<> to create the nodes.