Inconsistent bound requirements on arrays with generic sizes

[calebzulawski]

I'm working on integrating const generics into stdsimd. We want to support two types of bit masks. The first has an entire mask per lane, e.g.:

struct Mask32<const LANES: usize>([u32; LANES]);

The other type of mask only uses a single bit per lane, e.g.:

struct BitMask<const LANES: usize>([u8; (LANES + 7) / 8]);

This doesn't work, however, and errors with error: unconstrained generic constant. After finding #68436, I was able to get it working with:

struct BitMask<const LANES: usize>([u8; (LANES + 7) / 8]) where [u8; (LANES + 7) / 8]: Sized;

This seems inconsistent since the two types are negligibly different. Also, since this type will be public, the bound bleeds into the interface which is undesirable.

[newpavlov]

Currently it's an intended behavior (with which I also disagree). See this comment by @oli-obk.

[jonas-schievink]

Yes, this is working as intended

[calebzulawski]

Is this something likely to ever change, or is the behavior expected to stabilize like this? I'll have to discuss with the rest of the portable SIMD project group but this may preclude a const generic implementation.

[oli-obk]

I'm still very much in the court of requiring bounds just like we require trait bounds on types before being able to use them beyond moving or otherwise directly forwarding them. This is definitely open for discussion, just like anything, but I'd really prefer it if we stabilized the current version first and thought about convenience extensions second. Ideally any convenience features would also apply to types.

Note that you can create a const fn that does your math, thus requiring you to only bubble up some_fn(LANES) instead of the actual math. This is very similar to bubbling up T: Trait bounds.

[oli-obk]

Oh, also note that callers who supply concrete integers will not have to do anything, the bound will be evaluated once at the call site and either error or just work if the expression evaluates successfully.

[calebzulawski]

That's a good point about the const fn, though that would still end up with an extra implementation detail in std. That still exposes [u8; bytes(LANES)]: Sized or similar which is still very much an implementation detail. I suppose my question then, why is the bound not required for the first example? Something like:

struct Foo<N>([u8; N]) where [u8; N]: Sized;

I do understand that it's a bound, but it's unfortunate because I do think this is a common pattern (I'm basically just trying to replicate C++'s std::bitset). I think as it stands right now it would be impossible to implement a type like this:

pub(crate) struct Wrapper(u8);
pub struct Array<const N: usize>([Wrapper; N / 8]) where [Wrapper; N / 8]: Sized;

[oli-obk]

you do not actually need the Wrapper in the array here. We currently just have no good way of specifying bounds for constants, this will likely be remedied before stabilization. So right now you can do where [(); N / 8]:;, not even a Sized bound necessary iirc.

That still exposes [u8; bytes(LANES)]: Sized or similar which is still very much an implementation detail.

I think you would probably name your const fn something like valid_lanes, which usize::max_value() would not satisfy, because it would overflow.

[calebzulawski]

Okay, I think I misunderstood what that bound was representing. Perhaps it could be be possible to indicate that a bound is always valid? In my example above, N / 8 is always valid.

[oli-obk]

I guess some kind of opt out of the system could be reasonable. I'm trying to come up with an example in the type system and trait bounds that have a similar situation. I guess it's when you do impl<T> SomeTrait for T, you always have access to SomeTrait, even if you did not specify that bound. We should figure out all things like this in the trait system, look at how this could be used in typenum to get the effects we want, and then come up with a scheme to get it for const generics. As long as we have a trait system mirror of something, I think it is fairly uncontroversial and would probably be an easy RFC to get through

[newpavlov]

@oli-obk
I think the trait analogy should be applied a bit differently. Let's take a look at the following example:

fn foo<const N: usize>(val: Val) -> [u8; bar(N)] where [u8; bar(N)]: Sized { .. }

A trait analog of this function is:

fn foo<N: Unsigned>(val: Val) -> Bar<N> { .. }

We don't need the sized bound here because, contrary to the bar constant function, we are sure that Bar<N> will always evaluate to a valid type (and we do not care about preventing "too big" errors using bounds). A general const fn not only may not terminate, but also can panic, which includes potential overflow and underflow errors. For example , N.wrapping_add(N) is a valid body for the bar function. Such body will return result for any input N, so the bound is redundant.

But if I am not mistaken, strictly speaking it's not guaranteed that Bar<N> will terminate either. Rust type system is Turing-complete, so we can not guarantee termination (IIRC there exists some kind of type recursion limit error to terminate compilation in pathological cases), but in practice we extremely rarely encounter such errors to bother adding bounds to prevent them.

So the only difference between traits and const expressions used in type construction is potential panics. In other words, I think that the mandatory sized bound effectively ensure that const computations used in type construction will not panic for every possible input. And as I've argued in the other discussion, I don't think it's worth to introduce mandatory manual bounds just for that.