5 ms·

Kind of but not really. You still can't access an undeclared element, and you still can't take a mutable and an immutable reference to an element by index. The

Kind of but not really. You still can't access an undeclared element, and you still can't take a mutable and an immutable reference to an element by index. The borrow checker only cares about memory safety, and index accessors are implemented in a memory safe manner (whether that's panic!ing or returning an Option<>). If you want… umm… "data safety" (I'll call it for now), so you can't use an index to access an element that you didn't intend to access because stuff got shifted around for instance, then generational indexes will solve that issue for you. And to clarify something that's probably obvious. A direct pointer to a vector element could easily end up becoming invalid when the vector has to be copied somewhere else for it to grow or if the element gets deleted in another thread, so you can't just easily use pointers to vector (or array) elements in Rust.

esrauch 8y ago
I think the point is that Rust's checking allows you to statically know you don't have a dangling pointer. Indices explicitly can be dangling or accidentally incorrectly point at a new value that replaced the same slot or whatever. You suddently need to manually decide when to free values. It does avoids the worst security issues (bad reads are at least contained to the same data structure, which can easily be a serious security issue but at least not arbitrary memory reads) but for a lot of purposes it has the same properties that you have with C style pointers. It seems like a giant problem that Rust advocates are strangle quick to gloss over as a good pattern.
- skybrian 8y ago
  Indexes in an ECS system are basically a way to implement weak references. If you use generational indexes, it's a checked weak reference. Otherwise it's unchecked. Perhaps some future Rust-like language will have weak references built in? Even with unchecked weak references, you can't get arbitrary undefined behavior. It's more like Java where you can defeat the type system due to the way generics work, but it's still memory-safe. Also, relational databases work the same way. Sometimes people use constraints to avoid dangling references, but not always.
- malkia 8y ago
  Well it kind of reminds me of this - back when BASIC had just plain arrays (DIM), one had to do tree structures using indices. Later (with Pascal/C/C++) you would tend to use pointers, but then back in SQL land you would go back to indices (foreign keys?). So if SQL can deal with it, BASIC too, what would be the issue in Rust? Even in Pascal/C/C++, especially in 64-bit platforms, encoding index maybe the better thing to do, and then in GC collected languages - the less pointers to explore the less work the GC has to do.
  - int_19h 8y ago
    In SQL, foreign keys are semantically closer to references in many ways, not least because deleting a row doesn't change the keys of other rows. So it's not really an index - it's just a row ID. And then with ON DELETE you can make it safe in a sense of not having dangling references (because it'd either block deletion if such were to appear, or cascade to remove all rows that have them). Still a bit closer to raw pointers in that you can treat it as a raw number and point at some random rows this way. But still. In BASIC, yeah, you pretty much had to use indices. And it was very much not fun! BASIC was actually the first thing I remembered in the context of this discussion, because I wrote a lot of that kind of code. The other thing that it reminded me of is J2ME. People used indices into arrays of primitives there to avoid GC, because it was not really practical given the memory constraints of your average phone back then.
- pcwalton 8y ago
  Usually programmers expect to destroy objects in some specific location. For example, if a widget is removed from a window and then goes out of scope, then most programmers would expect it to be destroyed shortly thereafter. If there are actually references to the object remaining, contrary to programmers' intent, then one of four things can happen: 1. Use-after-free (C, C++). This is a logic bug and a security problem. 2. "Logically" dangling pointers (safe languages with non-generational indices). This is a logic bug, but not a security problem. 3. A memory leak (safe languages with garbage collectors). This is a bug that can be difficult to track down. 4. Panic/exception (safe languages with generational indices or weak pointers). This is a runtime failure. I'd argue that, of these four options, (4) is generally the best. The ideal would of course be a static guarantee instead of any of these. However, static guarantees always come with restrictions of some kind. For the truly unrestricted case, in which your data references are completely irregular, I'm not sure you can really do better.
  - josephg 8y ago
    The point still stands. If you hold an index into an array of widgets, and the widget you reference is removed or replaced in the array, you could get behaviours 1, 2 or 4 depending on your implementation. Rust's index-into-array pattern removes the possibility of memory leaks, but it also removes most of the benefit of having a borrow checker in the first place. Its basically a less performant, less ergonomic version of using raw C pointers. Less ergonomic because you need to write your own allocator for your array. And its less performant because fetching the associated struct from memory requires 2 fetches rather than 1. If you're convinced dynamic memory management is the only solution to your data structure, rust's unsafe{} seems a better choice. Its in the language for a reason.
    - pcwalton 8y ago
      You can't get security vulnerabilities due to use-after-free if you use indices. Don't use unsafe for this.
      - pjmlp 8y ago
psykotic 8y ago
> The borrow checker only cares about memory safety, and index accessors are implemented in a memory safe manner (whether that's panic!ing or returning an Option<>). Reductio ad absurdum: Implement the entire heap as a single array with typed views and you have the asm.js model. Memory safety is ultimately just another class of bug and it's worth keeping the end goal in mind. (And the asm.js approach is resistant against smashing the return address even if the hosted application has buffer overflows out of every orifice, and of course it provides isolation from the rest of the host process, so segregating the heap into a separate memory space has real security value.) I use indices and tagged handles instead of pointers in low-level C code all the time for sound engineering reasons as it's often the superior solution (and the move to 64-bit pointers created further incentives), but I think skepticism is warranted towards the growing Rust prescription of indexed arrays whenever you're dealing with non-tree-structured data. Probably the greatest thing about pointers is that they enable generic code without any abstraction cost. It's painful enough to work in a language like Java with object references but without interior pointers to array elements or structure fields. You may feel tempted to introduce a case-specific 'fat pointer' pairing of an array reference with an index, which is not only awkward to work with but puts you in the absurd situation of having an index type which will often round up to 16 effective bytes on a 64-bit platform due to packing alignment for the next value in memory, when often one of the goals of replacing pointers with indices on a 64-bit platform should be to reduce the size from 8 bytes to 4 or 2 bytes.
- kibwen 8y ago
  > the growing Rust prescription of indexed arrays I think there might be a disconnect here between people who talk about Rust and people who use Rust, because the use cases that are amenable to indexing into arrays are few and far between. I have never encountered such an approach in any Rust project that I have contributed to; tracking indexes is far, far less common than e.g. something like the Rc smart pointer. It does get talked about a lot though, for some reason.

esrauch 8y ago

I think the point is that Rust's checking allows you to statically know you don't have a dangling pointer. Indices explicitly can be dangling or accidentally incorrectly point at a new value that replaced the same slot or whatever. You suddently need to manually decide when to free values. It does avoids the worst security issues (bad reads are at least contained to the same data structure, which can easily be a serious security issue but at least not arbitrary memory reads) but for a lot of purposes it has the same properties that you have with C style pointers. It seems like a giant problem that Rust advocates are strangle quick to gloss over as a good pattern.

skybrian 8y ago
Indexes in an ECS system are basically a way to implement weak references. If you use generational indexes, it's a checked weak reference. Otherwise it's unchecked. Perhaps some future Rust-like language will have weak references built in? Even with unchecked weak references, you can't get arbitrary undefined behavior. It's more like Java where you can defeat the type system due to the way generics work, but it's still memory-safe. Also, relational databases work the same way. Sometimes people use constraints to avoid dangling references, but not always.
malkia 8y ago
Well it kind of reminds me of this - back when BASIC had just plain arrays (DIM), one had to do tree structures using indices. Later (with Pascal/C/C++) you would tend to use pointers, but then back in SQL land you would go back to indices (foreign keys?). So if SQL can deal with it, BASIC too, what would be the issue in Rust? Even in Pascal/C/C++, especially in 64-bit platforms, encoding index maybe the better thing to do, and then in GC collected languages - the less pointers to explore the less work the GC has to do.
- int_19h 8y ago
  In SQL, foreign keys are semantically closer to references in many ways, not least because deleting a row doesn't change the keys of other rows. So it's not really an index - it's just a row ID. And then with ON DELETE you can make it safe in a sense of not having dangling references (because it'd either block deletion if such were to appear, or cascade to remove all rows that have them). Still a bit closer to raw pointers in that you can treat it as a raw number and point at some random rows this way. But still. In BASIC, yeah, you pretty much had to use indices. And it was very much not fun! BASIC was actually the first thing I remembered in the context of this discussion, because I wrote a lot of that kind of code. The other thing that it reminded me of is J2ME. People used indices into arrays of primitives there to avoid GC, because it was not really practical given the memory constraints of your average phone back then.
pcwalton 8y ago
Usually programmers expect to destroy objects in some specific location. For example, if a widget is removed from a window and then goes out of scope, then most programmers would expect it to be destroyed shortly thereafter. If there are actually references to the object remaining, contrary to programmers' intent, then one of four things can happen: 1. Use-after-free (C, C++). This is a logic bug and a security problem. 2. "Logically" dangling pointers (safe languages with non-generational indices). This is a logic bug, but not a security problem. 3. A memory leak (safe languages with garbage collectors). This is a bug that can be difficult to track down. 4. Panic/exception (safe languages with generational indices or weak pointers). This is a runtime failure. I'd argue that, of these four options, (4) is generally the best. The ideal would of course be a static guarantee instead of any of these. However, static guarantees always come with restrictions of some kind. For the truly unrestricted case, in which your data references are completely irregular, I'm not sure you can really do better.
- josephg 8y ago
  The point still stands. If you hold an index into an array of widgets, and the widget you reference is removed or replaced in the array, you could get behaviours 1, 2 or 4 depending on your implementation. Rust's index-into-array pattern removes the possibility of memory leaks, but it also removes most of the benefit of having a borrow checker in the first place. Its basically a less performant, less ergonomic version of using raw C pointers. Less ergonomic because you need to write your own allocator for your array. And its less performant because fetching the associated struct from memory requires 2 fetches rather than 1. If you're convinced dynamic memory management is the only solution to your data structure, rust's unsafe{} seems a better choice. Its in the language for a reason.
  - pcwalton 8y ago
    You can't get security vulnerabilities due to use-after-free if you use indices. Don't use unsafe for this.
    - pjmlp 8y ago

psykotic 8y ago

> The borrow checker only cares about memory safety, and index accessors are implemented in a memory safe manner (whether that's panic!ing or returning an Option<>). Reductio ad absurdum: Implement the entire heap as a single array with typed views and you have the asm.js model. Memory safety is ultimately just another class of bug and it's worth keeping the end goal in mind. (And the asm.js approach is resistant against smashing the return address even if the hosted application has buffer overflows out of every orifice, and of course it provides isolation from the rest of the host process, so segregating the heap into a separate memory space has real security value.) I use indices and tagged handles instead of pointers in low-level C code all the time for sound engineering reasons as it's often the superior solution (and the move to 64-bit pointers created further incentives), but I think skepticism is warranted towards the growing Rust prescription of indexed arrays whenever you're dealing with non-tree-structured data. Probably the greatest thing about pointers is that they enable generic code without any abstraction cost. It's painful enough to work in a language like Java with object references but without interior pointers to array elements or structure fields. You may feel tempted to introduce a case-specific 'fat pointer' pairing of an array reference with an index, which is not only awkward to work with but puts you in the absurd situation of having an index type which will often round up to 16 effective bytes on a 64-bit platform due to packing alignment for the next value in memory, when often one of the goals of replacing pointers with indices on a 64-bit platform should be to reduce the size from 8 bytes to 4 or 2 bytes.

kibwen 8y ago
> the growing Rust prescription of indexed arrays I think there might be a disconnect here between people who talk about Rust and people who use Rust, because the use cases that are amenable to indexing into arrays are few and far between. I have never encountered such an approach in any Rust project that I have contributed to; tracking indexes is far, far less common than e.g. something like the Rc smart pointer. It does get talked about a lot though, for some reason.