8 ms·

Why do rust arrays have to have a size known at compile time? This restriction is not found in other programming languages. I'm sure this helps the borrow check

Why do rust arrays have to have a size known at compile time? This restriction is not found in other programming languages. I'm sure this helps the borrow checker or bounds check but why precisely?

ynik 6y ago
Arrays in Rust are value types (same as std::array in C++, which also has a compile-time size). That means the array doesn't have a separate heap allocation, but is stored inline in the struct/stack frame containing the array. The compiler needs to know the size so that it can place other struct members/local variables after the array. For dynamically-sized arrays you'd typically use a `Vec<T>` in Rust (or a `Box<[T]>`). These imply the array is stored as a separate heap allocation.
NobodyNada 6y ago
> This restriction is not found in other programming languages It is. C used to have variable-length arrays as a required part of the standard, but that was made an optional feature in C99. C++ (like Rust) does not have variable-length arrays at all. If you need a dynamically-sized array in any language, usually you allocate the array on the heap — for instance, with malloc/free, or with a vector type like C++’s std::vector or Rust’s Vec. As for why, I’m not entirely sure — hopefully someone with more expertise than me can chime in. I’m not sure if it adds too much complexity in the compiler, or if they were simply deemed too unsafe even for C/C++ (since it’s way too easy to accidentally overflow the stack with VLAs).
- kzrdude 6y ago
  Vararrays were new (and required) in C99 and optional in C11
- jessa0 6y ago
  Slices in Rust are actually kinda similar to VLAs in C99, but usable in places other than aggregates, and use an additional word in pointers to them for the length, as a safety mechanism. You can even use slices as the last member of a struct, like VLAs, though they're not very ergonomic currently (you can only obtain references to them, as well as Boxes containing them, using "unsizing" coercion): https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=cf12a502a25d674f0f376af383af62a3 https://play.rust-lang.org/?version=stable&mode=debug&editio...
  - jessa0 6y ago
    Ok, turns out I was mixing up "flexible array member" with "variable-length array". Slices can be used on the stack like a VLA as well, though, with the unstable "unsized_locals" feature. This feature is controversial, however, because of the risk of unintentional stack blowup..
- oconnor663 6y ago
  The Linux kernel devs have banned VLAs from their codebase, so you can get a lot of context from that discussion. (https://www.phoronix.com/scan.php?page=news_item&px=Linux-Kills-The-VLA https://www.phoronix.com/scan.php?page=news_item&px=Linux-Ki...). One of the drawbacks of VLAs is that, maybe just because of an unfortunate choice of syntax, it's surprisingly easy to create one accidentally: https://lwn.net/Articles/749064/ https://lwn.net/Articles/749064/
jimktrains2 6y ago
The size of all stack-allocated items needs to be known at compile-time. It's the same reason you can't directly have a field in a struct that is the same type as the struct: the size can't be known at compile-time. If you need an array of unknown size, then you can heap allocate it or use std::vec::Vec (usually via the vec! macro) to provide a nice interface for doing so. If you need nested structs, e.g. for a tree, then you need to make the field, e.g. the children nodes, pointers or a Box type. Rust tries to make what it's doing with memory obvious. Other languages with unknown array sizes do a lot of potentially unpredictable memory allocations and copies.
nsajko 6y ago
> Why do rust arrays have to have a size known at compile time? Having a known-length array type in a programming language: * allows the compiler to make certain optimizations using the information it has on the length, especially if the length is small * allows the programmer to enforce constraints on the length of arrays at compilation time, which can make program correctness more evident and easier to accomplish > This restriction is not found in other programming languages. Ever heard about C or C++ or Go? Even dynamic languages like Julia allow defining such types.
kjwhefkjhwe 6y ago
If you're asking this then you have a pretty big misunderstanding about how computers work, and how compilers translate types in a language into machine instructions. The real answer is that, for types to be able to be passed around a program like we're used to, they have to have a size known at compile time. (The mostly irrelevant but invariably talked-about exception is a VLA, which I'm ignoring for now.) If you're writing in a language where the array's size is not known at compile time, the language is lying to you---it's not really an array, it's most likely a pointer and a length. Rust doesn't lie to the programmer, so you can't have an array's size not known at compile time. You should learn C.
andoriyu 6y ago
That's a requirment for any language that isn't allocating everything on heap. Nothing to do with borrow checker. OutOfBounds errors aren't checked at compile time unless it's a `const` type IIRC.
- kibwen 6y ago
  > OutOfBounds errors aren't checked at compile time unless it's a `const` type IIRC. There are circumstances where Rust can calculate the array index at compile time and, if it can, it will result in a compilation error if the index is out of bounds. Of course, this is a best-effort analysis and doesn't work for all possible cases. Here's some Rust code, the first three indexing operations fail at compile-time, but the last doesn't: let x = [1,2,3]; x[4]; // compile error const FOUR: usize = 4; x[FOUR]; // compile error let y = 4; x[y]; // compile error fn foo() -> usize { 4 } x[foo()]; // runtime error This analysis works on fixed-size arrays, but not on Vec.
jlrubin 6y ago
https://doc.rust-lang.org/nightly/unstable-book/language-features/unsized-locals.html https://doc.rust-lang.org/nightly/unstable-book/language-fea... This should provide interesting reading -- it's a discussion on unsized local variables, e.g. VLA's on the stack.
moldavi 6y ago
Yes, Rust lacks a runtime-sized array. I think the rest of these replies are presenting a false dichotomy; having a compile-time sized array doesn't change that. Rust could easily have all three (compile-time-sized, runtime-sized, and Vec) but they chose not to. Probably because Vec is mostly good enough (albeit wasting a bit of memory).
- brundolf 6y ago
  A Vec is a length, capacity, and pointer. I don't see how you could implement Rust's safety guarantees with runtime-sized arrays that don't know their capacity (for bounds-checks). I guess you could theoretically do without the length/capacity distinction, so you could eliminate one value (but not two) by having "plain" runtime arrays. Overall I just can't imagine there are very many cases where eliminating a single number's worth of memory usage for an entire collection is worth having separate concepts with separate implementations, syntaxes, etc, not to mention all the downsides of not having reallocations/usage-length managed for you.
  - unanswered 6y ago
    Length=capacity is already available, and always has been, as Box<[T]>
    - brundolf 6y ago
      Can [T] be any length, decided at runtime?
      - unanswered 6y ago
        Yes.
        brundolf 6y ago
        That's news to me, and good to know. Seems moldavi's original comment was incorrect
dathinab 6y ago
They also have arrays which size is not known at compiler time (`[T]` instead of `[T; SIZE]`). It's just that you (for now(1)) can't put dynamic sized types (DST) on the stack, but you can coerce a `&[T; SIZE]` to a `&[T]`. The later has the size encoded in the pointer. Which combined with rusts system to compiler time enforce proper aliasing and RAII allows nice sub-slicing like e.g the `split` at method which allows splitting a `&[T]` into two non-overlapping `&[T]`'s. (1): There is ongoing work to allow DST on the stack in some limited circumstances which would help with some things, but I'm not the biggest fan of it. For example because this is in many but not all cases incompatible with `async/await` and the not yet existing generators.

Why do rust arrays have to have a size known at compile time? This restriction is not found in other programming languages. I'm sure this helps the borrow checker or bounds check but why precisely?

ynik 6y ago

Arrays in Rust are value types (same as std::array in C++, which also has a compile-time size). That means the array doesn't have a separate heap allocation, but is stored inline in the struct/stack frame containing the array. The compiler needs to know the size so that it can place other struct members/local variables after the array. For dynamically-sized arrays you'd typically use a `Vec<T>` in Rust (or a `Box<[T]>`). These imply the array is stored as a separate heap allocation.

NobodyNada 6y ago

> This restriction is not found in other programming languages It is. C used to have variable-length arrays as a required part of the standard, but that was made an optional feature in C99. C++ (like Rust) does not have variable-length arrays at all. If you need a dynamically-sized array in any language, usually you allocate the array on the heap — for instance, with malloc/free, or with a vector type like C++’s std::vector or Rust’s Vec. As for why, I’m not entirely sure — hopefully someone with more expertise than me can chime in. I’m not sure if it adds too much complexity in the compiler, or if they were simply deemed too unsafe even for C/C++ (since it’s way too easy to accidentally overflow the stack with VLAs).

kzrdude 6y ago
Vararrays were new (and required) in C99 and optional in C11
jessa0 6y ago
Slices in Rust are actually kinda similar to VLAs in C99, but usable in places other than aggregates, and use an additional word in pointers to them for the length, as a safety mechanism. You can even use slices as the last member of a struct, like VLAs, though they're not very ergonomic currently (you can only obtain references to them, as well as Boxes containing them, using "unsizing" coercion): https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=cf12a502a25d674f0f376af383af62a3 https://play.rust-lang.org/?version=stable&mode=debug&editio...
- jessa0 6y ago
  Ok, turns out I was mixing up "flexible array member" with "variable-length array". Slices can be used on the stack like a VLA as well, though, with the unstable "unsized_locals" feature. This feature is controversial, however, because of the risk of unintentional stack blowup..
oconnor663 6y ago
The Linux kernel devs have banned VLAs from their codebase, so you can get a lot of context from that discussion. (https://www.phoronix.com/scan.php?page=news_item&px=Linux-Kills-The-VLA https://www.phoronix.com/scan.php?page=news_item&px=Linux-Ki...). One of the drawbacks of VLAs is that, maybe just because of an unfortunate choice of syntax, it's surprisingly easy to create one accidentally: https://lwn.net/Articles/749064/ https://lwn.net/Articles/749064/

jimktrains2 6y ago

The size of all stack-allocated items needs to be known at compile-time. It's the same reason you can't directly have a field in a struct that is the same type as the struct: the size can't be known at compile-time. If you need an array of unknown size, then you can heap allocate it or use std::vec::Vec (usually via the vec! macro) to provide a nice interface for doing so. If you need nested structs, e.g. for a tree, then you need to make the field, e.g. the children nodes, pointers or a Box type. Rust tries to make what it's doing with memory obvious. Other languages with unknown array sizes do a lot of potentially unpredictable memory allocations and copies.

nsajko 6y ago

> Why do rust arrays have to have a size known at compile time? Having a known-length array type in a programming language: * allows the compiler to make certain optimizations using the information it has on the length, especially if the length is small * allows the programmer to enforce constraints on the length of arrays at compilation time, which can make program correctness more evident and easier to accomplish > This restriction is not found in other programming languages. Ever heard about C or C++ or Go? Even dynamic languages like Julia allow defining such types.

kjwhefkjhwe 6y ago

If you're asking this then you have a pretty big misunderstanding about how computers work, and how compilers translate types in a language into machine instructions. The real answer is that, for types to be able to be passed around a program like we're used to, they have to have a size known at compile time. (The mostly irrelevant but invariably talked-about exception is a VLA, which I'm ignoring for now.) If you're writing in a language where the array's size is not known at compile time, the language is lying to you---it's not really an array, it's most likely a pointer and a length. Rust doesn't lie to the programmer, so you can't have an array's size not known at compile time. You should learn C.

andoriyu 6y ago

That's a requirment for any language that isn't allocating everything on heap. Nothing to do with borrow checker. OutOfBounds errors aren't checked at compile time unless it's a `const` type IIRC.

kibwen 6y ago
> OutOfBounds errors aren't checked at compile time unless it's a `const` type IIRC. There are circumstances where Rust can calculate the array index at compile time and, if it can, it will result in a compilation error if the index is out of bounds. Of course, this is a best-effort analysis and doesn't work for all possible cases. Here's some Rust code, the first three indexing operations fail at compile-time, but the last doesn't: let x = [1,2,3]; x[4]; // compile error const FOUR: usize = 4; x[FOUR]; // compile error let y = 4; x[y]; // compile error fn foo() -> usize { 4 } x[foo()]; // runtime error This analysis works on fixed-size arrays, but not on Vec.

jlrubin 6y ago

https://doc.rust-lang.org/nightly/unstable-book/language-features/unsized-locals.html https://doc.rust-lang.org/nightly/unstable-book/language-fea... This should provide interesting reading -- it's a discussion on unsized local variables, e.g. VLA's on the stack.

moldavi 6y ago

Yes, Rust lacks a runtime-sized array. I think the rest of these replies are presenting a false dichotomy; having a compile-time sized array doesn't change that. Rust could easily have all three (compile-time-sized, runtime-sized, and Vec) but they chose not to. Probably because Vec is mostly good enough (albeit wasting a bit of memory).

brundolf 6y ago
A Vec is a length, capacity, and pointer. I don't see how you could implement Rust's safety guarantees with runtime-sized arrays that don't know their capacity (for bounds-checks). I guess you could theoretically do without the length/capacity distinction, so you could eliminate one value (but not two) by having "plain" runtime arrays. Overall I just can't imagine there are very many cases where eliminating a single number's worth of memory usage for an entire collection is worth having separate concepts with separate implementations, syntaxes, etc, not to mention all the downsides of not having reallocations/usage-length managed for you.
- unanswered 6y ago
  Length=capacity is already available, and always has been, as Box<[T]>
  - brundolf 6y ago
    Can [T] be any length, decided at runtime?
    - unanswered 6y ago
      Yes.
      - brundolf 6y ago
        That's news to me, and good to know. Seems moldavi's original comment was incorrect

dathinab 6y ago

They also have arrays which size is not known at compiler time (`[T]` instead of `[T; SIZE]`). It's just that you (for now(1)) can't put dynamic sized types (DST) on the stack, but you can coerce a `&[T; SIZE]` to a `&[T]`. The later has the size encoded in the pointer. Which combined with rusts system to compiler time enforce proper aliasing and RAII allows nice sub-slicing like e.g the `split` at method which allows splitting a `&[T]` into two non-overlapping `&[T]`'s. (1): There is ongoing work to allow DST on the stack in some limited circumstances which would help with some things, but I'm not the biggest fan of it. For example because this is in many but not all cases incompatible with `async/await` and the not yet existing generators.