Rfcs: Compile Time Bounds Checks

[realSmushyTaco]

I've noticed very simple out of bounds cases with arrays have compile time errors and everything else has runtime errors. If things could get to a point where all bounds checking in Rust was compile time developing anything that has to do with iteration and arrays would be a lot easier.

Think of it like this:

Would you rather constantly recompile for every tiny change to figure out why your code is throwing out of bounds errors or would you rather have a compile time error (Or warning for backwards compatibility) that tells you the cases that need to be covered?

[Lokathor]

Arrays have a compile time length but the value used to index doesn't always have a compile time computable value, is the problem.

[realSmushyTaco]

There are still plenty of cases that could be checked at compile time so don't you think doing so and spitting out a warning instead of doing nothing and keeping most cases at runtime would be better? Also can you provide a case that doesn't have a complie time computable value for reference?

So far the way I see it there are two options for better compile time checks:

1. If the value can't be computed at compile time require the use of unsafe for what's being done and throw hard errors for the things that can be checked at compile time that aren't (Unsafe would turn these hard errors into warnings).
2. If it's possible to check at compile time have a warning whenever there's a case the complier checks that hasn't been covered.

Personally, I think option 1 is the optimal solution.

[ejaszewski]

can you provide a case that doesn't have a complie time computable value for reference?

Anything that depends on user input, a system dependent value, random number generator, etc. Theoretically, one could consider these "unsafe," but they clearly don't fit within the current concept of unsafe in Rust, and would cause tons of errors to crop up.

Another example is something that requires computation involving loops or recursion -- while it may terminate in reality, it is not possible to always prove such a computation will terminate, and thus, to get its value. Throwing a warning or requiring unsafe here doesn't make sense at all to me either.

[realSmushyTaco]

Regarding the requiring unsafe for things the compiler can't determine it doesn't have to break compatibility. There could be two attributes named #![forbid(runtime_bounds_checks)] and #![allow(runtime_bounds_checks)] with allow on by default. That way by default nothing breaks when moving to a new Rust version unless the forbid attribute is used.

If #![forbid(runtime_bounds_checks)] is used then:
If the value can't be computed at compile time require the use of unsafe for what's being done and throw hard errors for the things that can be checked at compile time that aren't (Unsafe would turn these hard errors into warnings).

If #![allow(runtime_bounds_checks)] is used (Which would be used by default) then:
If the value can't be computed at compile time throw a warning and also throw warnings for the things that can be checked at compile time that aren't.

[jhpratt]

What is so wrong about runtime bounds checks that you want to use unsafe for everything? And what's preventing you from doing this already?

The compiler doesn't provide any guarantees about what's knowable at compile-time, aside from the obvious const fn, const, and static. I've seen a proposal for const blocks, which would allow the compiler to optimize it away (guaranteed). But I don't think there's demand _at all_ for a lint along the lines of what you're asking. Bounds checks _are a good thing_.

[realSmushyTaco]

Yes and they'd be a _better_ thing if they were done at compile time. Right now only super simple cases error out at compile time and having more things be caught by the compiler would be beneficial.

[golddranks]

@realSmushyTaco In Rust, it's generally frowned upon to introduce "ad hoc" systems for specific features like that. There is already a related feature brewing: "arbitrary-but-deterministic" constant computation and constants-in-generics. With constant generics, this problem will be solvable in a way that doesn't need any special casing.

[realSmushyTaco]

So in the future when this "arbitrary-but-deterministic" feature is developed and all stable there'll be more compile time checks for what I'm asking for? If so could you link me where this feature is being discussed? I'd love to follow progress on it.

[golddranks]

Not in the sense that the current types would magically introduce them. (That is also a backwards compatibility hazard: we can't make code that used to compile suddenly not compile. Issuing warnings is a fair game though.) The way I'm imagining it is that there is a "ranged integer" type and an array (arrays have known size in Rust) or a reference to an array. Once introduced, there would be methods to convert between "normal integers" and "ranged integers", with non-compile-time check. (And proper error handling.) Similarly, there would be a checked conversion function from a slice reference into an array reference. Once you have these types with extra-compile-time guarantees, indexing between them can be implemented internally with zero-cost unsafe, but with safe API.

Also note that it's "mostly solvable" already: skipping bounds checks is important for indexing in a tight loop. If you assert the size of the index (or inputs where the index is calculated from) and the size of the slice in the same function but before entering the loop, LLVM is likely able to optimize the checks out. Of course, like all optimizations this is not an ironclad guarantee, like type-based approach would be.

[golddranks]

Check everything in the index starting with const here: https://doc.rust-lang.org/unstable-book/language-features/const-fn.html There are links to "tracking issues" which have also links in RFCs.

[realSmushyTaco]

Alright thanks for the info! I'll go ahead and close the issue now.

[le-jzr]

I should point out that compile-time bounds checking is not as simple as it sounds. It's an area of active research. The issue is that very often you simply aren't able to determine whether a given access is safe, because the algorithm is not strong enough yet. You get tons of false positives. If you add errors, or even warnings about things you can't prove correct, you are effectively incorporating the complete implementation of the specific checking algorithm into your programming language specification. This is already an issue with borrow checker, but borrow checking as done in Rust is much, much simpler than bounds checking.