Implement proptest's Arbitrary trait for Array #596

Activity

1. jturner314

   added

   help wanted

   on Mar 13, 2019
2. phungleson commented on Mar 16, 2019

   

   phungleson

   on Mar 16, 2019

   More actions

   @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?
3. jturner314 commented on Mar 18, 2019

   

   jturner314

   on Mar 18, 2019

   MemberAuthor

   More actions

   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.
4. xd009642 commented on Oct 20, 2019

   

   xd009642

   on Oct 20, 2019

   Contributor

   More actions

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

   👍React with 👍1Reacted by Luca Palmieri
5. jturner314 commented on Oct 20, 2019

   

   jturner314

   on Oct 20, 2019

   MemberAuthor

   More actions

   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.

   ❤️React with ❤️3Reacted by Luca Palmieri, Andrew Wagner and Daira-Emma Hopwood