Might be worth pointing out: leptos, a Rust WASM UI library, uses the "store an index (or ID) into some central data structure" idea extensively.
Sycamore, another Rust WASM UI library, has been using arena allocation, but will also be transitioning into the leptos approach in coming versions.
(I believe) this is partly because the borrow checker's enforcement of a tree-like data structures / ownership doesn't always work well with the JS event loop.
The index is bounds-checked, sure, but lifetime issues like “double free” or “use after free” are every bit as present with indexes. For instance, if you have an index in one place, but it’s deleted and/or reinitialized to some other place, you are now holding on to an object in an undefined state. Using it will cause the same issues “use-after-free” does in C. Best case scenario in that cases is that it crashes, but it’s just as likely your program will just silently be wrong.
I’m not saying not to do it, I’m just saying this is something Rust developers needs to be aware of: storing indexes like that removes a whole bunch of safety guarantees the borrow checker checks for you, without any code marked “unsafe”.
Notice how the array technique has parallels to memory: You can have multiple arrays of different types a.k.a segmented memory. You can mark unused array objects, a.k.a. overwrite free'd memory with 0xDEADBEEF.
Instead, attain Nirvana, open emacs and embrace Fearless Development.
Pointers in C point to objects and not memory locations afaik, which has subtle semantic implications. See the whole discussion around pointer provenance.
Segregated, typed, heaps (never reuse the memory for a different type after a free) could allow similar safety.
But more generally: imagine you're making a game where you shoot a bunch of dudes, so you have a `std::Vec<Dude>` to store them, and elsewhere in the code, you reference this vec using indexes. When you shoot a dude, you want to remove it from this array, but being a programmer concerned about performance, you don't want to literally delete the entry, as that is an O(n) operation. Instead, you mark the dude as "despawned" or whatever, and then when you want to spawn a new dude, you keep a list of despawned dudes and just recreate the new dude in the same place in the array. If other places in the code are holding on to indexes to this array, the index is now invalid, but it will not be detectable: it'll just point to the wrong data, which can wreak all sorts of havoc.
This is almost exactly equivalent to "use-after-free" issues in C. In most cases, `free()` will not literally free the memory, it will mark the memory as unused and stored in a free-list, to be available for the next `malloc()` call. If you're holding on to a pointer that has been free()d, it's not that the program will segfault, it's much more insidious than that: it will point to memory that is apparently valid, but actually garbage.
This is precisely the kind of lifetime issue the Rust borrow checker was designed to solve, but by using indexes like this, you've basically just turned the borrow checker off without realizing it. If the borrow checker is intrusive enough that this becomes a very common pattern in Rust, I personally think it does serve as a pretty good counter-argument to a lot of things people say about Rust. Rust people are very quick to sing the borrow checker's praises and say that "as long as you learn to work with it, it stops becoming a problem!". If it stops becoming a problem only because you sneakily turn it off using tricks like this, maybe it's a bigger problem than people are willing to admit.
One leads to undefined behavior and is potentially exploitable in a way that allows for full control over your program's execution. That's the difference.
No one is arguing that the bug you've described isn't expressible in Rust - it obviously is. It's just not what the borrow checker is for because the borrow checker is for memory safety issues, and you're describing a logical bug.
I think this description is a very narrow way to look at memory safety (and again: totally ignoring the broader issue of lifetime safety), if I'm going to be honest. In my Rust program, I have two functions `spawnDude()` returning an index and a `despawnDude()` taking an index. In C, i have `malloc()` returning a pointer and `free()` taking a pointer. The lifetime issues are the same: just like I shouldn't `free()` a pointer twice, i shouldn't `despawnDude()` twice, and I shouldn't use a dude after I've despawned him. The implementation could even be very similar: using arenas (which is essentially what the Rust array is) and free-lists.
Again: these were the issues Rust was designed to solve, and the borrow checker is the tool it uses to solve them. And it absolutely does do that, if you use the native Rust constructs: this is the true super-power of Rust. The reason why it's so much easier to work with indexes is because you've deliberately chosen not to have the borrow checker analyze this situation. If that is something you have to do a lot of (and I've seen it a number of times, not just in the project the parent mentioned), it does say something important about how the borrow checker limits the expressive power of the language, if you have to turn it off in this way.
No. That's the end of it. The answer is no, you are wrong, that is not the case. The rest of your post is fine but irrelevant.
If this is true or at least fundamentally very close to each other, and given that exceptions can be abused for arbitrary code execution [1] [2], then it follows that Rust is no different/safer with respect to that, no?
[1] https://billdemirkapi.me/exception-oriented-programming-abus... [2] https://billdemirkapi.me/abusing-exceptions-for-code-executi...
There is huge difference between the controlled and guaranteed teardown from panic in Rust and maybe segfault maybe nasal demons in C.
Nope. If you're lucky, you get a segfault.
> imagine you're making a game
Actually, I would love to be making games. The benefits Rust provides aren't huge benefits in Game Dev, we get it. In fact, isn't this whole thing just a rehash of Jonathan Blow's ECS critique? But most of us aren't making games.
Imagine instead you're a not making a game, and you see CVE after CVE because of memory safety. Customer data gets stolen, things like SSNs. People's lives are impacted. I suppose a game crash is annoying, but way less annoying than someone's/my personal info being leaked.
Sure, we could go on as usual, blame "human error" and say everybody needs to do better. Or, we could accept better over perfect, and try to mitigate common errors that seem to happen often. You can still use `unsafe`. I guess by this argument, seat belts are useless, too, because they don't stop traffic fatalities completely. And so are all aviation safety improvements.
We're still here having the "Rust offers no/marginal benefits (to game dev and other niches)". Ok.
It seems to me to be a pretty unarguable point. It's frankly a bit shocking to me to see this vehement of a disagreement.
Rust makes this really, really difficult. If you can live with immutable pointers, you can have as many as you like, but the lifetime syntax you have to juggle can become a horror show, and can force lifetime annotations on a whole chain of structures. If you can't live with immutable references, then you are forced to use the unnecessarily ugly Rc<> syntax.
I often find myself using the array indexes trick, which leads to buggy code.
In Java, I never had to do this. Multiple "pointers" are fine. The garbage collector takes care of memory safety. In this one sense, Rust is a less-safe language than Java.
I have been writing Rust for two years now. I would not use it again if I could avoid it. It is a giant waste of time.
You've been poisoned by C, where this is literally how arrays work, they're just pointer arithmetic plus syntax sugar (which is why arr[x] == x[arr])
Rust's array type is an actual array, and so a lot of the problems you're worried about (which would be big pitfalls out of the box in C) only happen in Rust if you went to some effort to dig a hole for yourself so you could fall into it.
> For instance, if you have an index in one place, but it’s deleted and/or reinitialized to some other place, you are now holding on to an object in an undefined state
This idea of "objects in an undefined state" is a normal part of C, but Rust doesn't have it. So you'll have to go invent it for your types, so as to inflict this injury on yourself, and I have no doubt you'd eagerly do so maybe even persuading yourself that this way is "faster" or some such nonsense.
You might sensibly store the indices as owned pseudo-reference types, akin to Unix file descriptors and various Windows handle types, both of which Rust manages as opaque owned objects (ie they don't implement Copy) and borrowed objects (which do Copy)
Contrast:
https://doc.rust-lang.org/std/os/fd/struct.OwnedFd.html https://doc.rust-lang.org/std/os/windows/io/struct.BorrowedH...
When you treat them as opaque handles, it becomes more apparent whose job it is to ensure the handles work as intended. Nobody would say "Oh that's your problem, you used it wrong" if your open file handle to the settings file suddenly morphed into stdin because of unrelated code.
> Rust's array type is an actual array, and so a lot of the problems you're worried about (which would be big pitfalls out of the box in C) only happen in Rust if you went to some effort to dig a hole for yourself so you could fall into it.
It is an extremely easy hole to fall into. If you hold on to an index X into an array, and some different part of the program deleted an entry in the array with an index smaller than X, your X is now no longer valid, it's pointing to the wrong object. This is exactly equivalent to an "invalidated pointer", which is an issue the borrow checker was designed to solve. But there is no way for it to know this, because by using indexes instead of pointers, you've disabled its ability to analyze this situation.
I agree that pointers in C and indexes in Rust are not the same thing, and there are other issues with C pointers that Rust's borrow checker solves. But imagining that you're magically safe from any lifetime issues "because Rust" is foolish.
It completely sidesteps the issue you are describing because "deleting from array" does not mean "adjust every greater index by one".
However, I'll grant you that using this crate means you have to extend _some_ trust (even if very small) to the crate maintainer to maintain safety invariants, in addition to Rust's compiler maintainers.
But the fact that I could dive into its code (that I've never seen before) in 2 minutes and verify that it is not susceptible to the issue you describe gives me more confidence that auditing+trusting this crate will not be an undue burden.
[1] https://docs.rs/slotmap/latest/src/slotmap/basic.rs.html#395
That's not a thing. This is the linchpin of your argument, and it just doesn't exist.
Try it, make an array of, I dunno, Strings, and then "delete" one. You can't, there is no "delete" operator, that would be meaningless.
People with some brief exposure to Rust might think, "OK smart arse, it's called drop, I can just drop the String". Nope. That's an array of Strings, you can't just drop one of them, it's part of the type [String; N] it's not OK if one of them isn't a String, so you're going to need to consciously swap it for a different String, you could core::mem::take that element of the array, leaving its default (an empty String) behind and then drop the one you took. But what we've got here isn't an "invalidated pointer" we've just got an ordinary logic error in our program where we mistakenly empty strings we still wanted.
You have to go build your own pit, and fill it with spikes, and jump into it, all so that you can moan, "Oh, Rust basically has the same terrible pit traps as C or C++" except, you built the trap, so don't do that.
Your argument is that there's no such function as `std::Vec::remove`? I can assure you, it exists: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.rem...
If you use that function, and you've held on to a an index that is no longer valid, it is pointing to the wrong string. Or worse: it's pointing outside of the array, and your program will panic. The index is no longer valid, just like a pointer in C is no longer valid after calling free().
> You have to go build your own pit, and fill it with spikes, and jump into it, all so that you can moan, "Oh, Rust basically has the same terrible pit traps as C or C++" except, you built the trap, so don't do that.
I am not saying "Rust basically has the same terrible pit traps as C or C++". I have never said that, and I never would. What I'm saying is that if you're using indexes like this, you no longer have the benefit of lifetime safety guaranteed by the borrow checker. You have, in essence, turned the borrow checker off for this part.
BTW, making the argument "as long as you're not a bad programmer, this isn't a problem" is exactly the argument that some Rust haters make: "well, just don't call free() twice, and it's not a problem!". Either way, it's bull: the whole point of the borrow checker is that it statically guarantees that these kinds of lifetime issues can't happen. But if you turn it off using indexes, it guarantee is out the window. The whole discussion started with the parent commentator pointing out a project that does exactly this, and me pointing out that this is a problem from a static safety perspective.
In C, if you have a UAF, the attacker likely owns your entire process. They can call any function with any arguments. They can modify entirely unrelated objects. Your backups get encrypted and your secrets show up on dubious websites. You lose, badly.
If you roll your own arena in Rust and you “UAF” a struct, you either panic or you continue executing, with a correct control flow graph, with no language-defined UB. The attacker can do only what your code can be convinced to do. Sure, if you implemented an entire VM based on your arena, maybe the attacker can convince your VM to encrypt your backups and leak your private data. But this only happens if your VM can do that in the first place. If your code just draws creatures in 3D, then all the attacker can do is mess with the creatures.
>Having a raw pointer and having an index into an array are essentially equivalent, and doing this in Rust is a way to turn off the borrow checker for this particular object. [...] The index is bounds-checked, sure, but lifetime issues like “double free” or “use after free” are every bit as present with indexes. For instance, if you have an index in one place, but it’s deleted and/or reinitialized to some other place, you are now holding on to an object in an undefined state. Using it will cause the same issues “use-after-free” does in C.
... which is false. Later they shifted the goalposts to:
>If you use that function, and you've held on to a an index that is no longer valid, it is pointing to the wrong string. Or worse: it's pointing outside of the array, and your program will panic.
... which nobody would've disputed if they'd said that initially.
If you've decided to treat indexes into a Vec as handles, then yeah, you mustn't use Vec::remove because it's nonsense in your context. You also mustn't Vec::retain and numerous other "I don't care about ordering" operations, because you do care about ordering.
I'd argue it's probably sensible to make your own custom container which cares about ordering for this work since that preserves the invariant you've decided upon, rather than trust yourself not to make mistakes. You can build one out of a Vec pretty easily.
And sure enough that's exactly what the project you're referencing seems to actually do, they've got themselves a custom container which preserves their intended semantics.
No one is using a Vec<T> with indexes for long term storage if you know you will remove and replace items there, it's obvious regardless of programming language that it's a bad idea.
You use a dedicated data structure for this where the keys have a generation and that solves the ABA problem.
Rust has multiple crates that provide such data structures.
If most Rust libs migrate to use index based memory references, then what is the point of the borrow checker ? It would be demoted to a rarely used 1% feature leveraged only by Language Complexity Fanatics - might as well remove it from the language and speed up the slow Rust compile times by orders of magnitude.
The growing adoption of handle/index based resource management is also demonstrating that borrow checking is effectively a failure. Most library authors are beginning to move away from borrow checking as it imposes severe limitations on software design and usability and severe increases to cognitive complexity.
I mentioned two crates that are DOM frontend frameworks, that also are based on fine grained reactivity (and not a virtual DOM). That’s an incredibly specific niche of rust libs.
You can split the handle (index) into an upper "magic" and lower "index" part, with the handle being an opaque type, only being able to be accessed and modified by the container giving out handles. In C++, you'd likely see operator* and operator-> overloaded for usage. This technique is described in the original "Game Programming Gems" book.
Not 100%, but on usage, the handle checks the magic against what's currently in the data-structure to let you know if the handle has been freed and/or reused. Since handles are opaque, you can muck with the underlying objects as you want, e.g relocate them in memory, having multiple internal arrays, etc.
Sure, you no longer have to satisfy the borrow checker - but it was a tool to help you catch bugs, and you've cleverly avoided getting that help.
Rust tries very very hard to avoid bounds-checking bugs, because it's central to the safety promise, maybe I'm misunderstanding you?
> either "list was re-ordered, you now have the wrong item" ... "can't compact the list, it just keeps growing even when old items are no longer used" bugs.
I have no direct experience implementing this pattern, but it's good to know that leptos (and others) tend to use one well-tested library that addresses these concerns[1].
> Sure, you no longer have to satisfy the borrow checker - but it was a tool to help you catch bugs, and you've cleverly avoided getting that help.
My impression is that one can perhaps claim "one traded compile-time checks of safety for runtime _panics_ when unsafe things are about to happen", and not that using this pattern exposes one to the same issues that the borrow checker avoids.
[1] https://docs.rs/slotmap/latest/slotmap/index.html#why-not-in...
Slotmap avoids this via unsafe + implements its own handle system, which is probably the right approach.
The borrow checker avoids many other issues in addition to memory safety.
Sounds like OpenGL object management. Shudder. This is not a step forward.