Const slicing

1

I'd sometimes like to defined a sliced constant like this:

const FIBS: [u32; 11] = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
const NONZERO: [u32; 10] = FIBS[1 ..];
fn main() {}

Do you think this is going to work eventually?

2

cc @oli-obk and @ecstatic-morse

3

I think you'd run into a couple problems...

  1. The std::ops::Index trait expects you to return a reference and not a value, so you'd need to either rely on [T; FIBS.len() - 1] being Copy or use something else
  2. You need to move the runtime value, 1.. (a Range<usize>) to something compile time
  3. We need to use unsafe and pointer arithmetic in a const fn
  4. Const generics need to be able to express conditions like N < M in a where clause

Here's my take:

struct Array<T, const N: usize>([T; N]);

struct Range<const Start: usize>;

impl<T, const N: usize> Array<T, N> {
    pub const fn slice<const Start: usize>(self, range: Range<Start>) -> [T; N - Start]
    where
        Start <= N,
    {
        unimplemented!("Magic...")
    }
}
2 Likes
4

Here's a version that typechecks:

const FIBS: [u32; 11] = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
const NONZERO: [u32; 10] = FIBS[1 ..].try_into().unwrap();
fn main() {}

To work, it needs -Zunleash-the-miri-inside-of-you or

  • const implementations of nonconst traits
  • impl const Index<RangeFrom<usize>> for [_]
  • impl const TryFrom<&[_]> for [_; N]
  • const fn Option::unwrap
4 Likes
5

I would go with the approach outlined by @CAD97 as well. It only requires https://github.com/rust-lang/rfcs/pull/2632 and https://github.com/rust-lang/rust/issues/66753. We already allow integer indexing inside a const context; range indexing doesn't present any additional theoretical problems, although it would probably need something like const slice_from_raw_parts.

3 Likes
7

This is a real flag? :smile:

5 Likes
8

It's very real. IIUC it basically means run MIRI / the compile-time evaluation engine on ALL OF THE THINGS, which is great for testing error cases in that engine and features that don't even have a flag yet, but also wildly unsound and perma-unstable since (to ensure the tests aren't brittle) it disables a bunch of the static checks that happen before full evaluation. Nobody else should be using it, hence the silly name.

9 Likes
9

I've implemented a variant of this, RangeTo, in the index-ext crate so I do have some practical notes. The RangeTo<const To: usize> suffers from one unnamed problems, the length might be chosen such that [T; N] is not a well-formed type, which I had to ignore currently. One really cool feature is that the single type paramer can be deduced by the context which, barring dependent types, is not possible with regular function parameters. The example does not quite work since trait impls can not be used on const context, even with -Zunleash-the-miri-inside-of-you but otherwise it is easy to apply and compiles fine:

use index_ext::array::RangeTo;
fn main() {
    const FIBS: [u32; 11] = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
    let NONZERO: [u32; 10] = FIBS[1..][RangeTo];
}
fn main() {}

To expand a bit on the potential post-monomorphization error, note that all types need to have a valid Layout. The size of an array is the (align-padded) size of the contained type multiplied by its length the layout. This implies that the size of [u32; usize::MAX] can not be computed and programs which contain that type must be rejected. With const generics this type can now occur after monomorphization. The next code block shows that the error occurs when explicitely used but it should be clear that if T were instead part of a library internal controlled by an interface type parameter then that interface would be unexpectedly brittle. It would not accurately capture the requirements placed upon the parameters.

fn must_fail() {
    // Instantiate the type without constructing an instance of it.
    fn types<U>() -> <[U] as core::ops::Index<RangeTo<{usize::MAX}>>>::Output {
        panic!()
    }

    types();
  // ^^^^^ This use leads to:
  // error: the type `[u32; 18446744073709551615]` is too big for the current architecture
}

An concept for an alternative to post-monomorphization errors are surprising types and runtime panics. We could use [T; 0] as a placeholder output type during const-eval where constraints are not satisfied, and then panic at the site of use instead. This is arguably similar to regular indexing which also panics when an invalid index is chosen but the type itself can confuse the programmer and other uses.

struct Range<const Start: usize, const End: usize>;

impl<T, const Start: usize, const End: usize> ops::Index<Range<Start, End>> for [T] {
    // Not currently permitted due to potential error. The compiler doesn't trust that these do 
    // not panic and we have the same problem as `RangeTo`, the type may not even be valid.
    type Output = [T; [0, End - Start][Range::]];
    fn index(&self, idx: Range<Start, End>) -> &Self::Output {
        if Start <= End {
            self[Start..End].try_into().unwrap()
        } else {
            panic!("Invalid range")
        }
    }
}
10

I think that's a really bad idea, and I don't agree that

because in this case, we would panic on a purely type-level error which is otherwise possible to catch at compile time. This is very different from indexing which in the general case needs to be checked dynamically. And using a different type (namely, [T; 0]) in the place of a different type just feels like a hack.

I would actually prefer a post-monomorphization error to both alternatives, as it's not nearly as surprising as other kinds of post-monomorphization errors. Namely, it doesn't fall into the C++ style "I forgot to test my template with this particular, supposedly valid instantiation" category, as the resulting big array type is not just unexpected but valid, it is instead completely invalid.

However, couldn't there still be a way for detecting it before monomorphization? I mean, the requirement size_of::<T> * N <= usize::MAX is clear from the very beginning, so couldn't the use of [T; N] be constrained by a bound involving the const values, something along the lines of the following?

impl<const Start: usize, const End: usize> Index<Range<Start, End>> for [T]
    where End >= Start && (End - Start) * mem::size_of::<T>() <= usize::MAX
{
    type Output = [T; End - Start]; // compiling this would require the above where clause
    …
}

Of course the size constraint might not be / is probably not the only thing to worry about, it'd be neater to be able to validate the existence of the whole Layout<[T; N]> type, but you get the idea.

11

If you replace it with

type Output = [T; [0, End.wrapping_sub(Start)][(End > Start) as usize]];

Then you get

error: constant expression depends on a generic parameter
 --> src/lib.rs:8:5
  |
8 |     type Output = [T; [0, End.wrapping_sub(Start)][(End > Start) as usize]];
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  |
  = note: this may fail depending on what value the parameter takes

Note that this works without -Z unleash-the-miri-inside-of-you:

#![feature(const_fn, const_if_match, const_panic)]
#![feature(const_generics)]
#![allow(const_err)]

struct Range<const Start: usize, const End: usize>;
struct CheckedRange<const Start: usize, const End: usize, const Diff: usize>;

impl<const Start: usize, const End: usize> Range<Start, End> {
    pub const fn new() -> CheckedRange<Start, End, { End - Start }> {
        assert!([0, End.wrapping_sub(Start)][(End > Start) as usize] == End.wrapping_sub(Start));
        CheckedRange
    }
}

const FIBS: [u32; 11] = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];

pub fn main() {
    // pattern match on array of length 2
    let [a, b] = FIBS[Range::<3, 5>::new()];
}

impl<T, const Start: usize, const End: usize, const Diff: usize>
    core::ops::Index<CheckedRange<Start, End, Diff>> for [T]
{
    type Output = [T; Diff];

    fn index(&self, idx: CheckedRange<Start, End, Diff>) -> &Self::Output {
        unsafe {
            assert_eq!(End.wrapping_sub(Start), Diff);
            let slice = &self[Start..End]; // this will check bounds
            &*(slice as *const [T] as *const [T; Diff])
        }
    }
}

But we can't lift the indexing into a const because you can't call trait fn in a const But we don't need to go through Index::index (this requires -Z unleash-the-miri-inside-of-you)

impl<const Start: usize, const End: usize, const Diff: usize> CheckedRange<Start, End, Diff> {
    pub const fn index<T>(self, slice: &[T]) -> &[T; Diff] {
        unsafe {
            assert_eq!(End.wrapping_sub(Start), Diff);
            let slice = &slice[Start..End]; // this will check bounds
            &*(slice as *const [T] as *const [T; Diff])
        }
    }
}


const FIBS: [u32; 11] = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
const BARS: [u32; 2] = *Range::<3, 5>::new().index(&FIBS);

If you don't want to use -Z unleash... you will need at least <*const T>::add to be a const fn before we can do this on nightly

2 Likes
12

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.