CODEWITHSUNDEEP
arrayscompiler-errorsruntime-errorrustlanguage-design
1ijk
1ijk

Reputation: 1507

Why does Rust check array bounds at runtime, when (most) other checks occur at compile time?

Reading the basic introduction:

If you try to use a subscript that is not in the array, you will get an error: array access is bounds-checked at run-time.

Why does Rust check array bounds at runtime, when it seems most other checks occur at compile time?

Upvotes: 13

Views: 7207

Answers (2)

mherzl
mherzl

Reputation: 6220

The reason is because: Although the array's length may be known ahead of time, the index being referenced may not be known ahead of time.

Simple example:

fn main() {
    let a = [1,2,3,4,5];
    let index = 10;

    let element = a[index];
}

In rust arrays are stack-variables, so their length does not change. The length of the array will therefore be known at compile-time.

After seeing an example like the above, it may seem that rust should be able to check for 'index out-of-bounds' errors at compile time.

However, although the array size is known at compile time, often the index at which the array is being referenced is not known at compile time.

Consider this more complex example:

fn main() {
    let a = [1,2,3,4,5];

    let mut guess = String::new();
    io::stdin().read_line(&mut guess).expect("Failed to read line");
    let guess: u32 = guess.trim().parse().expect("Please type a number!");

    let element = a[guess];
}

The index at which the array will be accessed is coming from user input. There is no way for the compiler to know the index at which the array will be accessed. The only way to know the index here, is to run the program. That's why rust deals with array-index-out-of-bounds errors then, at runtime, instead of at compile-time.

Upvotes: 2

user395760
user395760

Reputation:

Because checking indices at compile time is not feasible in the general case. Reasoning about the possible values of arbitrary variables is somewhere between hard and impossible even for small programs. Nobody wants to have to:

  1. formally prove that the index can't be out of bounds, and
  2. encode that proof into the type system

... for every single slice/Vec/etc. access, because that's what you'd have to do to perform bounds checks at compile time. You essentially need dependent typing.

Aside from possibly making type checking undecidable (and getting a program to type check vastly harder), type inference becomes impossible in general (and far more restricted in the best case), types get much more complicated and wordy, and the complexity of the language increases significantly. That indices are in bounds can only be proven without significant additional programmer effort in very simple circumstances.

Furthermore, there is little incentive to get rid of bounds checks. Lifetimes pull their weight by almost entirely eliminating the need for garbage collection --- which is a huge, invasive feature with unpredictable throughput, space and latency implications. Run-time bounds checking in the other hand is very non-invasive, has a small and well-known overhead, and can be selectively turned off in performance-critical sections even if the entire rest of the program uses it liberally.

Note that the compiler can do some simple checks for out-of-bounds access of arrays:

let a = [1, 2];
let element = a[100];

error: index out of bounds: the len is 2 but the index is 100
 --> src/main.rs:3:19
  |
3 |     let element = a[100];
  |                   ^^^^^^
  |
  = note: #[deny(const_err)] on by default

However, this is limited and is easily avoided by making the index value not an "obvious" constant: 

let a = [1, 2];
let idx = 100;
let element = a[idx];

Upvotes: 20

Related Questions