I know this works, but whenever I hear this advice, I can't help thinking: Aren't indexes and vectors basically just a way of smuggling pointers past the borrow checker?
This isn't to say that futzing with integers is the best imaginable solution for these tasks. Language-level support (or at least stdlib support) for generational indices would be an interesting subject to pursue.
Granted, you could `Option`-up all your operations, but the dynamic GC languages (or even C++) will let you operate on stuff "correctly", so long as your implementation is right.
You can go `unsafe` and implement correct stuff and still be better than C++. I really feel like reference IDs aren't a great way to solve something like a doubly-linked list. Reference IDs make you lose almost all guarantees of correctness, unsafe + a good API will at least give you a fighting chance.
There are problems (like entity system stuff) where reference IDs are just the way to go, though
But I don't think anyone should be juggling integers themselves; they should be using a library (just like a library-defined smart pointer) that handles that (the presentation at https://www.youtube.com/watch?v=P9u8x13W7UE may be of interest).
> There are problems (like entity system stuff) where reference IDs are just the way to go, though
Sure, and there isn't anything stopping anyone from both using them where they're practical and not using them where they're not. Some of the comments in this thread seem to be suggesting that you must choose one or the other, but that's simply not the case; using references in one part of one's program and indices in another is totally fine, as is using references and indices together in the same part of the program. They're not exclusive.
In particular, nobody is saying that one should be reaching for indices regularly; I've written Rust for years and have never, ever needed them. References work just fine for plenty of applications. But we have other smart pointers for good reasons, and sometimes an application will call for the use one of those smart pointers, and that's totally cool; again, references may be thoroughly useful, but they are not the end-all be-all of pointer-like abstractions.
https://www.gamedev.net/blogs/entry/2265481-oop-is-dead-long...
In this particular case, currently Rust's borrow checker isn't of much help either, hence the workaround with generations.
I find this argument deeply frustrating. C++ doesn't even try to make graph memory management safe. Rust has several different strategies for graphs, all of which have some drawbacks, but which are all nonetheless safe. But because they aren't quite as ergonomic as C++, C++ somehow wins. No. C++ graph management is unsafe, regardless of whether you're using the lifetime profile.
One reason why Pascal, Ada and Modula-2 lost against C, was because they weren't ergonomic enough to the eyes of many developers.
The typical magazine articles why using them felt like ceremony and straitjackets by those whose security wasn't on their top concerns.
So I get to have a bit of experience being on the losing side, arguing how using array indexes with bounds checking (which could be disabled if really needed) was a better option than just incrementing away bare bones pointers. Or why explicit type casts were a better option.
Ideally, I would be using C# or Java for everything I do, so it isn't about C++ vs Rust as such, rather making the point that it is not only about grammar and semantics when comparing programming languages.
Given Biscuit's paper, I would say Go is on the good path if their Go 2.0 plans actually play as promise. Which remains to be seen, nonetheless.
In the end it is a matter of ergonomics and perceptions.
I'd phrase it the other way - pointers are just a tool to express certain reference patters. The solution you proposed - integers - are another. Conceptually, the way both are used, both are references - a way to indirectly access another object.
But if you do it with indices into another data structure, then you do, in fact, just work around the borrow checker, and escape to the land of freedom where you do whatever you want - and pay the price. Now you can pass them with impunity, sure... but now you also have to deal with indices that reference non-existent elements, or (depending on your usage patterns) indices that were not properly updated when an element was deleted from the middle etc.
I explicitly said that I don't think integers are the solution; it's simply that for tasks like e.g. managing the thoroughly interconnected world state of a video game, where you have a web of dynamic entities, references aren't the right solution, and so people start to concoct other solutions using the primitives they have available. I mention that I think generational indices are the solution (or at least a solution).
> But if you do it with indices into another data structure, then you do, in fact, just work around the borrow checker
Why is it "working around the borrow checker" when it happens in Rust, but "employing an ECS architecture" when it happens in C++? The fundamental insight is that pointers and references as we know them kinda sorta suck at managing arbitrarily-interconnected webs of entities with dynamic lifetime; a garbage collector neatly solves this use case (dynamic lifetimes are their entire jam), but if you're using Rust or C++ then we're assuming that you have stricter performance requirements than a typical garbage collector provides (and if you don't, then you should consider using a GC'd language). An ECS-like approach using indices (which, if you squint and turn your head, resembles a very specialized form of garbage collection) is a way to keep entity management tractable without going all-in on GC.
> now you also have to deal with indices that reference non-existent elements, or (depending on your usage patterns) indices that were not properly updated when an element was deleted from the middle etc.
Generational indices address these problems. Again, I don't think anyone should use integers directly, you should seek to leverage abstractions that other people have already sat down and thought about.
Anyway, the point still stands: this is bypassing the borrow checker, because something cannot be adequately handled by it. And by doing that, you're back to square one with all the problems that the borrow checker was supposed to solve.
So if you can't prove your ownership graph is safe at compile time, you have to do it at runtime. For some ownership graphs, reference counting with Rc<T> is the right choice, but in the general case indexes and vectors are the least-verbose way to represent a runtime ownership graph.
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.
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.
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.
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.
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.
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.
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.
If my index 2 now contains the contents of lets say index 5, due to array rearrangement after deletion of the element at 2, whatever happens with data[idx].is_data_valid() is not what the developer would be expecting.
To me it feels a bit like a workaround for something that cannot be validated by the borrow checker, because it is something that developers have to go the extra mile to implement, or get a third party library, which someone has to validate that actually works as expected.
In a way, it isn't much different than expecting C and C++ developers to use static analysis for lifetime validations.
Meaning, using a tool outside of the core language for added safety.
Is it so hard to believe that references are not the correct abstraction for 100% of use cases? Reaching for something other than references when references are the wrong tool for the job is not working around the borrow checker; it's choosing the right abstraction for the right task. Being hung up on the borrow checker is missing the forest for the trees.
> get a third party library, which someone has to validate that actually works as expected.
How is this different from using any third-party library, ever?
> Meaning, using a tool outside of the core language for added safety.
Rust explicitly supports users defining their own smart pointer types to provide pointer-like abstractions with custom semantics; using tools outside of the core language for added safety (for whatever definition of "safety" one wants) is completely expected and encouraged.
Meaning Java/C++, .NET + (C++/CLI | C++/WinRT), Node.js + C++, Swift / Objective-C++.
So with C++ improving its safety history, usually with ideas taken from Rust, Rust ergonomics and tooling need to have a better story than C++'s to replace it on the above stacks.
As for C++ adding more static analysis, its lifetime analysis is a nice-to-have, but doesn't compare to Rust's borrow checker. You simply can't tack on a sound borrow checker to C++, because the language wasn't designed to accommodate one, and trying to impose the concomitant rules regarding mutability, aliasing, and single-ownership would break every C++ program ever written. For anyone who prioritizes sound static analysis WRT lifetime verification, C++ isn't a competitor to Rust. And there are plenty of people for whom that isn't the case, and they will continue to use C++, and that's not a problem. Rust exists to provide an alternative systems language for people who favor memory safety, and it's pretty good at that. :)
As for being an alternative systems language for people who favor memory safety, I fully agree, my point is that it still needs to improve its productivity and eco-system.
At CppCon 2018 Embedded Development panel, one theme was that only now companies are slowly willing to migrate from C to C++11(!), with a language that allows for a progressive rewrite from C while keeping the existing toolchains.
Another productivity example, with .NET I can get the safety I advocate, while C++/CLI/CX/WinRT allow for a seamless interoperability story with native code.
So even if the lifetime analysis is a subset of what Rust is capable of, mixed debugging and seamless CLR/COM/UWP integration are more attractive than rewriting that code in Rust, without having VS integration and WIP integration with Windows APIs.
I think Rust on its current state, is more indicated for GC free scenarios with either CLI or headless execution.
That's funny, because the largest deployment of Rust is in Firefox, which has a UI.
As far as I am aware, Rust is only being used for low level rendering, not widgets.
That's pretty different to static analysis tools which most likely won't always work.
Maybe we could uplift them to the nursery, but again, generational indices are nowhere near the top 10 crates on crates.io.
Many logic bugs become security issues. This specific one -- by way of TOCTOU races -- is one of the richest sources of security issues in Unix. The proposed "dormant index" solution is likely to generate a lot of these as well.
What is a dormant index? I've not seen anything like this proposed, or heard the terminology before.
I like the “dormant” name because unlike a weak pointer (say, in Java or Python), you can’t use it directly - you have to borrow the actual object to use it; so it lies “dormant” until you wake it up. It’s not (necessarily) weak because there is no automatic destruction once all other references are gone.
In other words, static safety in the face of circular references is what would provide me a major clear advantage for better-than-C++, and unfortunately that doesn't seem to be something that is even seen as an opportunity for Rust given all of the rhetoric about that being an abnormal pattern and index-into-array being safe enough under that world.
Having a compiler able to solve the halting problem would also be “a major clear advantage for better-than-C++”, but too bad it's impossible … Arbitrary circular graphs can't be statically managed, that's it. Your need a runtime support, and it will either be a garbage collector, or some kind of constructions with array an indices.
Checking for graph cycle is elementary CS - planning the entry/exit nodes is not. It is similar to link time optimization to implement.
Yeah, but that's for built graphs, not graphs that will be built at runtime? Seems really, really different.
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.
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.
And accessing data through an index still requires you to first acquire e.g. a borrow, and the useful invariants of that borrow still hold: for the duration of that borrow, you have freedom from data races - there will be no other borrows to that instance when you're holding a &mut T, or there will be no other mutable borrows to that instance when you're holding a &T.
An index may allow you to reduce the scope and lifetimes of your borrows, but it does not allow you to eliminate your borrows.
I think it's possible to write a DormantPtr library that encapsulates this pattern with better ergonomics than vec<> + generational index.
Further, even if Rust guarantees memory safety, the approach is still less safe in the broader sense of guaranteeing program correctness. For one thing, if you just use raw integers for your indices, you basically have the equivalent of a C void pointer, a pointer to some unknown type. The compiler doesn’t know what the index is for and can’t catch you if you accidentally index into the wrong array. You can partially solve this by making a newtype wrapper for indices into each type of array, but even that can’t differentiate between multiple arrays of the same type.
Also, if you have a system for ‘freeing’ array indices and reusing those array slots for new data, you run the risk of keeping an index around too long and causing a semantic use-after-free: not as bad as a traditional memory use-after-free, usually, but certainly a source of incorrect and unpredictable behavior. And whereas tools like ASan let you ‘flip a switch’ to catch traditional use-after-frees if they happen in development builds, with arrays you have to add the extra checking manually. (On the other hand, if you do design extra checks, they might be cheap enough to run in production, where ASan is probably not. And yes, I know, when it comes to security, “if they happen in development builds” is quite meager comfort.)
But I’m not saying all this just to be negative. Personally, it’s my hope that someday in the future, Niko and co. will find ways to make the borrow checker more expressive when it comes to parent-child relationships, and in other situations where it currently struggles. If so, it won’t just help with pointers, but with array-based designs as well: it’ll become a more viable approach to have the borrow checker check array indices, by adding lifetimes to those array index newtypes. That would remove all of the aforementioned safety issues, while keeping the performance benefit of arrays – indeed, increasing it, since with the right design you would be able to safely disable the bounds check when indexing.
One of the many great things described by Catherine's keynote about ECS's in Rust: generational indices. Generational indices are a dynamic fix for this problem.
> Personally, it’s my hope that someday in the future, Niko and co. will find ways to make the borrow checker more expressive when it comes to parent-child relationships, and in other situations where it currently struggles.
I agree it'd be nice, and I've given it a lot of thought, as has Niko. In the limit, though, I think you're always going to have the situation in which there just aren't any static guarantees and the graph structure is truly unrestricted. In those cases, I'm not sure you can really do much better than dynamic checks of some kind, and it's hard to get much more efficient than a single bounds check.
Hmm… I'd heard of stuffing a generation ID into unused bits (which can help but is limited), but I see this proposes having the index type be a full (index: usize, generation: u64). Well, that works, but now instead of indices potentially being half the size of pointers (if you don't need more than 2^32 objects), they're double the size. Also, each object must store a generation, and you have to check that each time you use the index. (So it's not just a single bounds check, though I suppose you could turn the generation check off in release builds or something.)
If you're willing to accept that overhead, it seems to me that you may as well just store a pointer instead of an index; design the arena to ensure that the pointers remain valid as long as the arena itself lives, and use lifetimes to track that (much easier than managing lifetimes of each object). That way you don't need to keep track of the array and the index separately, and you also save on the bounds check. Well… I guess that with an array you can have unique mutable access, whereas with pointers you'd have to rely on interior mutability. But it sounds like a pain to ensure uniqueness when threading around &mut references to the arrays (especially if there's one big object with all the arrays); you could never keep references across calls even when that would be completely safe. I would rather rely on interior mutability. (Have I mentioned that I think Cell should be built into the language?)
I should note that one nice thing about the ECS style is that it's built around threading around Systems, which consist of references to the various Components. So it's a natural fit for the borrow checker.
pub struct SmartRef<'a> {
container: &'a Container,
widget: usize,
}
impl <'a> std::ops::Deref for SmartRef<'a> {
type Target = Widget; // Widget provides non-traversing functionality
fn deref(&self) -> &Widget {
&self.container.widgets[self.widget]
}
}
impl <'a> SmartRef<'a> {
fn children(&'a self) -> impl Iterator<Item = SmartRef<'a>> {
self.container
.widgets[self.widget]
.children.iter().map(move |w| SmartRef { container: self.container, widget: *w })
}
}
fn boo(container: &Container) {
let root = SmartRef { container, widget: 0 };
println!("name: {}", root.name);
for child in root.children() {
println!("child name: {}", child.name);
}
}
Mutability is also possible to some extent with these "smart" pointers. It gets a bit trickier and less ergonomic, though. See https://play.rust-lang.org/?gist=fbf1c24397e7020c95774bf0906...
Another option would be to store something like "Rc<RefCell<Container>>" instead of "&'a mut Container", in which case you will be able to achieve something that behaves like multiple mutable references (with all the concurrency issues of them).
References (i.e. pointers the compiler knows about), on the other hand, are strictly better than either. Indices can only be bounds-checked at runtime, while references can be both alias-checked and bounds-checked (if they're references into a slice of memory that is known to the compiler) at compile-time.
But, of course, you can't do math to references. Construct a pointer by through an integer cast + math, and now the compiler has no idea what that thing is, what it's inside of, or how many other pointers point to the same place it does.
I prefer my runtime validity checking to not come with CVE numbers, the corruption of instances of completely unrelated types, and other such heisenbugs.
> I feel like raw pointers and indices are about the same
On a large codebases with lots of contributors, there's several orders of magnitude of difference - between the number of bounds checked indices that could be "corrupting" your instances of type T (only those used to index arrays of T or things containing them), vs the number of pointers that could be corrupting your instances of type T (basically any pointer in the program whatsoever.)
Frequently with a similar "several orders of magnitude" difference in debug times.
Conceptually similar, practically not.
> I prefer my runtime validity checking to not come with CVE numbers, the corruption of instances of completely unrelated types, and other such heisenbugs.
I agree with your point, but DoS attacks do get you CVEs as well.
Personally, whenever I've got into writing Rust I was quite worried about the relaxed way you were told to use runtime-checked structures after many pages describing how Rust has such strong statically-checked safety guarantees.
I get that you need both because compilers and compiler research aren't close to proving many cases that programmers need to make use of, but selling both the ease of runtime-checked structures and how strong the static checking is feels a bit too much like trying to have it both ways. Sure, both are true, but then strong static checking doesn't really mean the same thing (that you're sure your program won't do certain things, which means you have to now do similar reasoning and debugging when dealing with other runtime-checked languages).
I don't quite understand this sentiment. If you try hard enough, you can verify anything at compile-time (modulo the halting problem, etc.). If you want, you can also use a language that verifies nothing at compile-time and does all verification at runtime. Where we choose to draw the line between static and dynamic verification depends on our requirements. The existence of dynamically-verified entities does not obviate the usefulness of statically-verified ones; Rust statically guarantees memory safety and data-race safety, and using e.g. Rc or indices into an array doesn't change any of that. If you're simply looking for a systems language with even stronger static guarantees than Rust, then look at ATS.
Not for off-by-constant-offset errors it won't. Even with address sanitization there's still a significant chance your overflowed offset will correspond with a valid part of some other a array--not really detectable at runtime in C.
I think the tldr; is, opinions vary.
Using indexes manually doesn't by-pass the borrow checker, its just a different, manual, memory allocation and management strategy.
It preserves memory-safety, but, it's questionable if you're better or worse off in terms of correctness of application logic when you use it.
...you're probably better off using the borrow checker (that's why it exists) or an abstraction in a crate to deal with this sort of problem, regardless of whatever implementation strategy it uses internally (unsafe, this, etc).
These savings matter a lot in some domains of computing.