Implement proptest's Arbitrary trait for Array

[jturner314]

Property-based testing is a very powerful way to create robust tests, but it's currently somewhat difficult to use property-based testing with Array inputs because Array doesn't implement the Arbitrary trait.

It would be nice to implement the Arbitrary trait similar to the impl for Vec such that the shape and elements could be parameterized. We could also take the memory layout as a parameter (with choices row-major/column-major/contiguous/arbitrary) or just randomize it.

[phungleson]

@jturner314 Hey, this looks both interesting and challenging for me at the same time, do you mind showing me some initial ideas?

I currently reading proptest but not sure what should be Parameters and Strategy?

[jturner314]

I'm not really familiar with the internals of proptest; I'll need to do some reading to provide detailed suggestions. There's a proptest book that looks pretty good. I'd suggest looking at how Arbitrary is implemented for Vec and writing the implementation based on that. You could also see if the proptest-derive crate might be helpful.

When I think about testing with ArrayBase inputs, these are some possible constraints that could be useful:

1. Shape constraints
   1. Bounds for each axis length (e.g. something like (0..10, 0..20) for a 2-D array with no more than 10 rows and no more than 20 columns.
   2. Bounds for the total number of elements in the array.
   3. Restrict to square arrays (all axes the same length).
2. Stride constraints
   1. Restrict to row-major arrays.
   2. Restrict to column-major arrays.
   3. Restrict to contiguous arrays.
   4. Allow arbitrary layout (including non-contiguous arrays) but restrict the size in memory of the array.
3. Element constraints
   1. Use whatever the parameters are for that element type, like the implementation for Vec does.

If I was to prioritize these, I'd focus on item (ii) of (1), item (iii) or (iv) of (2), and item (i) of (3). So, the parameter type could be

(SizeRange, A::Parameters)

if we only consider contiguous arrays with a limited number of elements. This would be great for an initial implementation.

Or, we could do something more sophisticated like

struct Parameters<A, D> {
    /// Limits on the number of elements in the array.
    len: SizeRange,
    /// Limits on the axis lengths.
    axis_lens: (D, D),
    /// Restrict to only square arrays (default: `false`).
    only_square: bool,
    /// Restrictions on the memory layout of the array.
    layout: Layout,
    /// Parameters for the elements within the array.
    elems: A::Parameters,
}

enum Layout {
    /// Generate only contiguous, row-major arrays.
    RowMajor,
    /// Generate only contiguous, column-major arrays.
    ColMajor,
    /// Generate only contiguous arrays. (This is the default.)
    Contiguous,
    /// Generate arrays with arbitrary layout, but with bounded size in memory.
    Arbitrary(SizeRange),
}

I'd just focus on getting something simple working first (e.g. the (SizeRange, A::Parameters) option, which is the same parameter type as Vec's Arbitrary implementation) before working on supporting more complex parameters.

[xd009642]

This issue appears to be a bit dormant. I'll try and have a stab at it if no ones currently working on it?

[jturner314]

I've been working on this, and I've made a lot of progress. The hardest part to getting something working is the random generation of arbitrary shapes/layouts that are representative of all possible arrays within the constraints, while obtaining a reasonable distribution without expensive rejection sampling. I've mostly figured that part out. The other potentially difficult piece is a sophisticated simplification strategy, but I'm delaying that for later because it isn't critical for a MVP.

I've been temporarily working on this in a branch of nditer with the intention of splitting it off into a separate crate or merging it into ndarray. Most of the key Strategy and ValueTree work is done; the primary remaining pieces are cleaning up the implementation and refining the API. I'm not sure where would be a good place to contribute at the moment, but please feel free to take a look.