CODEWITHSUNDEEP
rust
Aehmlo
Aehmlo

Reputation: 930

How do I return an array of objects using `impl Trait` from a function without boxing?

I'm implementing a Sudoku crate, and I'd like to allow the possibility of higher-dimension Sudokus. In 2 dimensions, there are 3 groups that need to be checked for correctness (the prime rule contains only 3 subrules) and position (by definition) requires only 2 coordinates to fully specify, but in higher dimensions this obviously increases.

I wrote the following method signature, but it doesn't work, and I'd like to avoid boxing at all costs due to the environments for which I'm developing.

pub fn groups(position: [u8; DIMENSIONS]) -> [impl Group; DIMENSIONS + 1]

The actual type of each group will be known at compile time (the actual type will be something like [Box, Stack, Band]), but it appears that the compiler doesn't like this even though it'll know the size of each element.

I'd love to be able to use a tuple with size determined at compile time, but that doesn't seem to be easily supported, unless I'm missing something.

The idea is that there are three types of Group: a Stack (column), a Band (row), and a Box. The definition for Group is given below.

pub trait Group {
    /// A group is considered valid if it has contains only unique elements.
    fn is_valid(&self) -> bool { /* Default implementation elided. */ }
    /// Returns an owned copy of the group's constituent elements.
    fn elements(&self) -> Vec<Option<Element>>;
}

Let's start with the two-dimensional case. For a given element, we can write the element's index as a double (i.e. 2-tuple) (x, y). The groups associated with this element are then one Box (as always; this is where DIMENSION + 1 comes from), one Stack, and one Band.

In three dimensions, a given element is indexed (by definition) by a triple (i.e. 3-tuple) (x, y, z). The groups associated with this element are then one Box, one Stack, and two Bands.

This trend continues into higher dimensions, and I want to enable the user to use a different dimensionality — thus the compile-time determination of sizes.

To check the puzzle for correctness, the caller simply calls Group::is_valid() on each of puzzle.groups(); they can also iterate over each to render the puzzle as appropriate.

Upvotes: 1

Views: 1569

Answers (1)

Jorge Israel Pe&#241;a
Jorge Israel Pe&#241;a

Reputation: 38606

You can't because all impl Trait guarantees is that it's some type that implements Trait. Arrays in Rust are homogeneous, each element must be the same type, but something like [impl Group; DIMENSIONS + 1] would mean that each element could be any type as long as it implemented Group.

It's difficult to say without more code but this could probably be accomplished by parameterizing on the type of Group:

pub fn groups<T: Group>(position: [u8; DIMENSIONS]) -> [T; DIMENSIONS + 1]

Now there will be one instance of the groups() function monomorphized for each kind of T it's called with which implements Group. This has the consequence that the returned array is fixed to that type only, allowing it to be homogeneous. Since the function has no parameter of type T, the type of T probably can't be inferred unless it can be inferred from the call-site (e.g. let x: [SomeGroup; 3] = groups([...])), so you would need to explicitly specify the type with groups::<SomeGroup>([...]).

I don't know if this is exactly what you want, but it communicates the general idea that you need to set the array to some fixed type. That is, [T; N] is fixed to T whereas [impl Trait; N] would imply that each element can be any type that implements Trait, which itself would imply that it's a heterogeneous array, but arrays in Rust are homogeneous.

I can't tell if you also want to parameterize on the constant DIMENSIONS, which requires RFC 2000: const generics which AFAIK isn't implemented yet, even in nightly. You probably don't need that if you're able to infer it from the parameter, as you seem to be doing.

pub fn groups<T: Group, const DIMENSIONS: usize>(position: [u8; DIMENSIONS])
  -> [T; DIMENSIONS + 1]

Upvotes: 3

Related Questions