The problem you're describing still exists, though I'd say the advice isn't quite right.

Generally the better advice is to use a graph library, or something like slotmap [1] if you're rolling your own, than to use a Vec or HashMap. That's superior to a vec/hashmap for a few reasons. It handles keeping indicies stable/writing your own index allocator. It also makes it possible with a feature flag to detect all use after frees at low-ish cost (instead of only detecting them if no-one is re-using the slot). It makes it convenient to use typed keys instead of integers. The underlying datastructure is basically the same though.

You can also use Rc/Weak for cyclic data, for ref counting "GC", it's an approach I have less experience with so I can't speak towards it as well.

In the end not that much data is cyclic (especially in idiomatic rust), and this is trading off a small amount of debugging convenience on cyclic data, for guarantees of memory handling correctness in the rest of your code, and for guarantees about the amount of damage that mistakes can do in the code that does need to handle cyclic data (which in turn is a debugging win on cyclic data, so...).

I agree it's a bit of a rough edge, but it's a case where rust solved the easy 95% of the problem with only slightly questionable tradeoffs on the remaining 5%, and that's a win in my book.

[1] https://crates.io/crates/slotmap

It's been a long time since I've been able to write anything in Rust despite loving the language. My last hopes for Rust are now in gcc-rs splitting the Rust ecosystem into two; the current npm-style crates.io ecosystem and a more destro-centric properly vetted package ecosystem. If this doesn't happen, I'll just continue to use other languages or limit my dependencies to those with sane package management (usually this means libraries written in C) until something better pops up.

Rust being a low-level library, adding something means inherently choosing a preferred approach to a problem rather than another, which may be disagreeble.

The consequence is that there would be still the sub-sub-dependencies problem, because the author of a crate may decide that the stdlib implementation is not appropriate for the use-case (Rust is low-level; low-level development is typically "pickier" than web development).

I personally think that it's good not to have higher level APIs in the stdlib. My only exception to this is the exclusion of fast hashing, because this choice had side-effects beyond simple need for an API.

Having two distinct "products" could help here. There could be a "bare rust" that is minimal and unopinionated, and used by those that need a small footprint, for example. A "battery included rust" could have common solutions to common problems that are hard to solve with "bare rust", at the expense of making choices that are best avoided for "bare rust".

My current outsider's perspective is that there's some kind of ever-shifting, never quite established consensus on which batteries to include, which tends to make it harder than necessary to switch project, interoperate between libraries etc.

There is already, it's the nostd.

Has there been discussion about this here on HN or an article about it you can point me to? I'm very much interested in exactly the same thing.

While I think there are valid arguments in both directions for putting more things like this in std, I don't think "non-bug issues have been open for over a year" is one of them. The exact same is true of std.

IIRC in Rust this is a little bit looser than elsewhere (let's say in C++) as the ABI is not stable. This allows improvements that change the internal structure of structs but not the API. As a counter example, in C++11 there was a breaking change that introduced a size field to std::list, making size() O(1) instead of O(n), breaking linkage between older and newer versions of C++ binaries. In Rust there is no such guarantee so changes like that could be introduced anytime.

The absence of versioning hell with Rust is one of the many things I love about Rust.

Of course if it appears in an old version the author won't bother to backport the fix so you will have to bump the dependency to the latest, doing all the API changes that you didn't want to do.

rust is one of them.

Last year has been a bit rough and I didn't have a whole lot of free time and energy to work on projects at the same time.

That said, I don't believe any of the open issues on slotmap are of immediate need of attention, they are mostly minor feature requests/incremental improvements.

I do have a slotmap 2.0 in the planning that will include most of these improvements and allow further customization and control of the number of bits used for index/generation as well as what to do when the generation would wrap around (either leak that specific slot or allow a spurious reference with a (very) old key).

They don't have to download and install version 1 of an API for backwards compatibility if you're on version 2, and you don't have to download a new compiler version to upgrade a package as long as the package's maintainer is still willing to support the version you're on.

(That latter one being the same as with support for new revisions of C or C++ in in GCC.)

The advantage w.r.t plain Vec and juggling integer indices is that unlike integers, Slotmap keeps track of the "identity" of the stored object; the keys are unique to that object, and you can't accidentally refer to a wrong object with them.

> errors risk being silent references to wrong objects

Slotmap is specifically designed to prevents this. I recommend you to read its documentation; the generational indices system is quite nice!

(I am not sure if slotmap uses this strategy)

To give more details some of these data structures use generational indexes, a pair (generation, index) where index is a plain index of the underlying vector and generation is a bookkeeping counter of how many times you have allocated a value to that index. These two values can be combined in a single 32bit-64bit value but additional memory would be required to keep track of the counter.

E.g. with a vector of length 2

{meta: [0,0], data:[...]}

malloc -> (1,0)

{meta: [1,0], data:[...]}

malloc -> (1,1)

{meta: [1,1], data:[...]}

free(0)

{meta: [2,1], data:[...]}

malloc -> (3,0)

{meta: [3,1], data:[...]}

free(0)

{meta: [4,1], data:[...]}

malloc -> (5,0)

{meta: [5,1], data:[...]}

free(0)

free(1)

{meta: [6,2], data:[...]}

malloc -> (7,0)

malloc -> (3,1)

{meta: [7,3], data:[...]}

This way if you tried to access the pointer (5,0) the library can check that at index zero of the meta array the generation is 7 and conclude that you are doing a use after free (in this example even generations denote unallocated memory).

This is a description of a very simplified algorithm.

A generation count indeed could mitigate "use after free" style bugs, but may have a high false negative ratio if many/most objects have same generation. But a glance at slotmap docs didn't yield any hits for a generation I'd being used, do you have a specific link?

The main problem with reference counted pointers is detecting cycles. Rust doesn't have a cycle detector, but only a concept of "weak" pointers that don't prevent the object they're pointing at from being destroyed, just detect if it has been. This works fine if you have a tree with parent pointers, you make the parent pointers weak and everything works. It doesn't work so well if you don't have a clear tree structure though, because then you can't really tell which pointers should be strong and which should be weak.

> but may have a high false negative ratio if many/most objects have same generation. But a glance at slotmap docs didn't yield any hits for a generation I'd being used, do you have a specific link?

Apart from wrapping around after 2^32 frees of a specific slot, I don't believe any false positives are possible. The trade off is that there's more overhead than I think you're imagining.

https://docs.rs/slotmap/1.0.6/slotmap/#performance-character...

Once I get around to slotmap 2.0 (as noted by my inactivity, I haven't had much of the good free time + energy combination last year), the default behavior will be to leak the memory of a slot after 2^31 alloc/free pairs in that slot rather than wrapping around. You can still get the old wrapping behavior, but the default will be to never, ever allow spurious references, at the cost of leaking a couple bytes of memory once in a blue moon if you have heavy, heavy churn. That means, amortized, each insertion will leak 3.726 nanobytes if you're storing u32s, which is a fun unit. Note that if you destruct the slotmap the memory is reclaimed of course, I just mean that slotmap itself will not use that piece of memory again.

> The trade off is that there's more overhead than I think you're imagining.

I don't think the overhead is as large as this implies. For SlotMap the memory overhead is ~4bytes plus alignment per element, and insertion/deletion is only a handful instructions and one branch extra compared to a vector push:

https://docs.rs/slotmap/1.0.6/src/slotmap/basic.rs.html#349

An index adds one extra branch compared to a normal index:

https://docs.rs/slotmap/1.0.6/src/slotmap/basic.rs.html#538

> I don't think the overhead is as large as this implies. For SlotMap the memory overhead is ~4bytes plus alignment per element, and insertion/deletion is only a handful instructions and one branch extra compared to a vector push:

I think they were imagining one generation counter for the entire map instead of one per slot. I agree it's not particularly high.

For trees without parent pointers: Just roll your own along the lines of the following. This fits nicely into rust's ownership semantics

    struct Node<T> {
        children: Vec<Node<T>>
    }

“Welp, can’t write a doubly-linked list in safe Rust so I might as well use C” is throwing the baby, the bathtub, and the rest of the greater metro area out with the bathwater.

Zig aspires to be that minimal language. It seems to have a lot of really good ideas. It’s too bad the compiler is so opinionated that a lot of developers will be alienated by it.

This is a meaningless distinction. No language in the history of languages has ever strictly "replaced" another. Over time Rust will eat into the market share of every language to differing amounts. C and C++ top the list of languages that Rust will likely eat into the most, but of course they will still continue to exist and people will find reasons to continue using them.

> But for the use cases where even C++ is too much, there is no replacement for C.

Rust is a significantly less complicated language than C++. But what does this even mean, anyway? Whose use-case is "A systems programming language, but the spec can only be so many pages long?"

> (and even that’s debatable, given the cyclic references issue discussed here)

    struct Node<T> {
        data: T,

        left:   *mut Node<T>,
        right:  *mut Node<T>,
        parent: *mut Node<T>,
    }

I would have used inheritance to create a "ListBaseType" with a "ListElementType" specialization (with all the data required to wrap some element) and an empty "ListNullType" to use as begin/end elements. A quick Google search results in a implementation using "None" instead: https://gist.github.com/matey-jack/3e19b6370c6f7036a9119b79a... (I don't vouch for it!)

In the end the correctness boils down to correctly handling the beginning/end. It does matter little if that's a NULL, None, nullptr or ListNullType.

The real difficulty would be adding thread safety with minimal performance loss.

1. Pointers work fine, you're not solving any problems here. 2. You can't rebind references in C++, so you wouldn't be able to delete nodes 3. Even with this insane approach, why would you use inheritance over a sum type? 4. Extra allocations or statics are needed to hold sentinels.

As for why this wouldn't work in Rust, in addition to its many general problems, the fundamental issue is aliasing. Rust mandates that if a mutable reference to an object is alive, then nothing else references it. Thus, it would only work if your entire list was immutable; this may fit within your definition of a sane API, but it's not what most people would want if they were choosing to use Rust.

1. Dereferencing raw pointer is unsafe; but maybe not necessary? 2. `int main (void) { int a = 1; int b = 0; int &ref = a; ref = b; return b; }` 3. union access is unsafe 4. the cost of not having nullptr or similar

Obviously a linked list is trival to implement with pointers; but at least in C++ a naive linked list implementation can easily produce lots of suffering (read: UAF or DF) with a `delete list.getPointerToElement(i)` (in practice it will be a more convoluted variant of that, maybe introduced by dozens of people working on a badly documented code base over a decade or two). I'd expect if programmers already do that in C++ there isn't much that prevent them doing that in unsafe rust?

> insane approach

I can assure you my mental health is pretty good, thanks. Though I made a comment regarding a thought experiment in a rust thread, I can see why you would think that.

In a GC language, the runtime has ownership over memory allocations. The "owner" is actually outside the application code, so the application code can have as many reference loops as it likes, as none of them are owning references.

That being said, you still can't do "naive" cyclical data structures without some additional assistance. But the ecosystem has matured around that: crates like ouroboros[1] provide safe interfaces for creating self-referential structures and datatypes.

Edit: NLL was indeed added in the 2018 Edition[2].

[1]: https://docs.rs/ouroboros/latest/ouroboros/

[2]: https://blog.rust-lang.org/2018/12/06/Rust-1.31-and-rust-201...

[0]: https://crates.io/crates/ghost-cell

I'm even having a hard time seeing how this could be slower than any other alternative. Yes, in the places where creating / deleting is necessary, the "root" structure will have to be passed around, but in the worst case that has the cost of adding one argument to a function (which has the nice side effect of making the lifecycle _visible_).

You cannot do cyclic data structures in Rust because every thing must have one owner, so no cycles.

You can do cyclic data structures in Rust with unsafe code or doing your own memory management (e.g. an arena data structure).

> The borrow checker worked fine when all I needed to do was pass data up and down the callstack, but anything beyond that was difficult or impossible to express

That is not true. It is true at the start of the learning curve, but you get used to it. Cyclic data structures are very far from simple.

This is not correct advice; not sure why you've been given this answer.

There are a couple of solutions.

1. you use a data structure (library) that returns you a handler, which can be an int, but it's not an int as in "position inside a vec" (index), but a symbolic reference, whose management is deferred to the library.

You can't use an index directly because if a position is freed, then taken, you will hold an invalid reference (int).

This is a handy solution, convenient to work with; if you do something wrong, you'll get an error from the library.

2. the manual solution is to use strong/weak references, which are quite ugly to use :)

This is, however, an optimization. I rarely write my code like that on the first pass. It's something I always have in mind that at some point it's worth replacing the pointers.

(This is not specific to rust, or any other language)

Though in Rust it has another advantage over pointers: it doesn't force you to suddenly annotate every single type that touches your data structure in any way.

Or worse, actual data belonging to someone else. If the integer is a user id, and you delete an user, reuse it for another user, the former user might see data for another use. That is a big security issue

Out-of-bounds array accesses causing segfaults is the happy case! The sad case is security vulnerabilities.

I would agree that using naive integer indices, and running the risk of accessing the wrong data, is also completely unacceptable, though.

(You're right that it actually doesn't always work because sometimes your stale index will still be inside the array but refer to a different thing, but at least it can't be abused to write into other arrays).

Unsafe is there if you need it. It gives you C pointers for everyone and their debugger to blow up on. The difference is Rust makes you painfully aware that CS 101 is actually hardcore engineering.

That's... not really that fatal. There's a lot of very useful code that can be written using only runtime-provided[1] containers and straightforward ownership trees.

But obviously the big problem is that for applications that do need to do non-trivial reference semantics, Rust doesn't really offer much. Applications with nonstandard allocator paradigms or weak-referenced caches or that need to do complicated graph management are mostly on their own in the world of unsafe.

And the somewhat more cynical point is: for applications that can easily fit within standard containers and standard allocation paradigms, C++ actually works really well already. Use your smart pointers. Use your containers. Follow the rules everyone tells you about not using bare new/malloc. And... it's basically just as safe, because anything beyond that would be unsafe in Rust too.

I don't dislike Rust, really. But the space between "Need to stay away from C++" and "Should probably just have written it in Go" seems to be getting smaller and not larger.

[1] Which in Rust, means "written using a ton of unsafe blocks".

For those applications you can almost always encapsulate the unsafe code in a data structure library with a safe interface, such that the library is a tiny fraction of the application code. And in many cases someone else already wrote that library. For graphs, for example, there is petgraph.

> for applications that can easily fit within standard containers and standard allocation paradigms, C++ actually works really well already

Not at all. For example it is still easy to corrupt memory using C++ references. Just the other day I discovered a nasty little bug involving absl::hash_map: someone had written "map[i] = map[j]" which is unsafe if the element at i does not already exist --- it can trigger a rehash, invalidating the reference obtained by map[j].

This is something I never understood. Given that a Rust application is running on top of an OS making OS calls... or uses a huge library like FFMPEG... The only safe portion is like the 1% of code being executed.

"such that the library is a tiny fraction of the application code"

I mean, your Rust app uses sockets to pull a video and save it with FFMPEG. The quantity of code executed to do that is like 99% unsafe and 1% safe. Right?

What are we talking about here? I can still find a bug in FFMPEG and ROP-exploit some code in the safe 1%, right?

The same languages and code Rust evangelists (and Mark Russinovich if not one) are blaming is the only code that makes Rust do something meaninful. Don't you agree?

Also, "if it can't be 100% safe right now all at once, then why even bother?" isn't very pragmatic.

It might not be using FFMPEG, but gdi32.dll, winsock2.dll, libc, etc. Correct?

Unless you run on 100% bare-metal, the "safe" code is still a tiny fraction.

What if my linked C library returns an invalid pointer? Rust will still make the assumption it might be valid and play along.

(that might be the reason why Rust likes to compile libraries/dependencies from source)

> Also, "if it can't be 100% safe right now all at once, then why even bother?" isn't very pragmatic.

Never said that. I only say that people thinks "unsafe" is just for a "tiny wrapper around a library" or as parent said "that the library is a tiny fraction of the application code."

At the end, it's not. If you consider the rest of the code that makes a Rust program run, then "library is a tiny fraction" is, in fact, the other 99% of your executing code, and that this code is unsafe (unless you run on 100% bare-metal).

The 1% of code that is your own will, upon creation, have been run precisely zero times, so there is no probabilistic argument to be made for its correctness. Safe languages let you exclude entire categories of mistakes even when your code hasn't been run yet, which seems obviously valuable.

This was referring to using unsafe data structures in Rust by pulling in a Rust library so that your application code doesn't need any unsafe blocks itself. This is a huge win for your application code, even if there's other code that is still "unsafe".

Nevertheless, the more code we write in Rust, the safer we will be. Especially because popular kernels and system libraries are often very well tested these days, whereas application code newly written by developers of varying skill levels likely won't be.

If you're perfectly attentive and constantly vigilant, maybe. In practice everyone thinks they're following the rules and everyone messes it up.

That used to be the case 10 or 15 years ago. Today it is much easier to "follow the rules", because:

1. You used to need to tread carefully to both follow them and do what you needed to; now you can do more complex things more easily. Example: In the past, you couldn't avoid new and free being strewn around your code. These days, you can avoid them entirely when not implementing a complex data structure of your own.

2. A decent version of "the rules" is basically explicit: https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines

3. The standard library and other FOSS libraries do a lot of the rule-following for you

(4. Compilers are more attentive and do more static checking.)

This is "don't write bugs, lol, and you're safe" argument. It has been demonstrated many, many times on HN, that you can cause UB in C++ using just high-level standard containers and smart pointers, without doing anything suspicious with raw pointers. Bugs of that kind are virtually impossible to detect during a typical code-review. So it is not "just as safe". It is tad safer than C, but nowhere near Rust.

> But the space between "Need to stay away from C++" and "Should probably just have written it in Go" seems to be getting smaller and not larger.

That might sound as a rant, but IMHO the designers of Go sadly made some odd choices in areas unrelated to memory management, which put me off from Go. Go is not just Rust with borrow checker replaced by tracing GC. It is a completely different language, with a much different "feel":

* some syntax choices that seem to have no justification other than "we wanted to make it look different than other languages" (ok, one can get used to it)

* no sum types / unions / enums

* code generation / copy pasting instead of proper macros

* error handling not really better than in C (caused by no sum types)

* visibility controlled by character case (so when you want to unprivate sth, you have to find-replace all occurrences; I guess this stupid idea originates from Python)

* unused stuff is hard error (terrible for prototyping)

* you don't need generics, but we've just added them anyways ;d

* no tools for controlling mutability/immutability/sharing (which is still useful in GCed languages)

* data races possible, accidental mutable sharing possible

* no RAII for deterministic destruction of non-memory resources (`defer` doesn't even come close)

* package/dependency management IMHO subpar compared to cargo

When trying to learn Go, I had exactly same feeling as when I first learned Java (after C++) - that the authors of the language designed it for people less capable than the creators themselves. So I didn't like it.

The language causes you to rethink datastructures that were largely created in a single-core context. You can think up equivalent functionality that satisfies the Rust borrow checker but then also lets you trivially parallelize via something like Rayon.

Rc or Arc work for a double LL if you insist on pointers, or a wrapped owned vector with integer based references if you don’t want the overhead of reference counting. But to say “Rust doesn’t offer X” is just not true; you can build anything but it just takes more work and thought, and it is always worth it given the performance and bug classes automatically eliminated by that extra effort. And with unsafe code, you get bare metal access without the rules.

https://github.com/rust-lang/rust/blob/master/library/alloc/...

It's part of standard lib. And you don't get more idiomatic than that.

Depends what you mean by that. It has 2 pointer to other nodes and element on the heap (EDIT: Not stack). It's bog standard double linked list.

If you're looking for intrusive lists those a very niche data structure.

https://docs.rs/intrusive-collections/latest/intrusive_colle...

https://github.com/rust-lang/rust/blob/master/library/alloc/...

You can still happily have UAF through references. The adoption of string_view has made this super clear. Arithmetic is still very error prone, with confusing promotion rules and little protection for overflows. Pointer arithmetic is still common - yes even if are using typical containers. What do you think is happening underneath the hood when you increment an iterator? Oh, and iterator invalidation remains a fun way of ending up with unsafe code even if everything looks totally fine.

This reminds me of those static provers which prove everything correct up until user input, you know, the place where an attacker will inject their payload.

No because in practice you only need unsafe a tiny minority of the time, whereas C++ is always unsafe.

Most programmers do not spend most of their time writing low-level cyclic data structure libraries. If they did, then indeed some of Rust’s advantages would be mitigated.

We also have D which can use C/C++ libraries seamlessly.

Using integer handles as pointer replacements does have some universal benefits though outside of Rust. You can make them more compact, they serialize more easily, etc.

What ? Box, Arc (and weak) are exactly made for this.

No, this is genuinely a big hole in the expressive space of the language. Not a lot of apps really need to do a ton of manual pointer work implementing non-trivial data structures, but some do, and it kinda sucks in Rust.

I've implemented several of such data structures, there is not that many tradeoffs available : safe and easy, or unsafe and fast.

The unsafe parts are still much better than raw C. I don't agree that the language and ecosystem is missing a "big piece". Everything is already there.

Doing this in Rust is still going to be orders of magnitude faster than many other languages. Maybe not C/C++, but then again if you’re chasing pointers in a list maybe squeezing every ounce of performance you can isn’t the #1 priority for the given application. The industry consensus is shifting to the idea that being #1 in security at the expense of being #2 or #3 in performance is a fine trade off.

Is it? That's where Java was 20 years ago.