Hacker News Reader

Comment by hgs3 | Hacker News Reader

I tried Rust about five years ago and I had trouble expressing cyclic data structures because there is no clear "owner" in a cyclic data structure. The "safe" solution recommended by the rustaceans was to use integers as references to the data in a vec or hashmap. I was rather put off by this: Instead of juggling pointers I was juggling integers. It made the code harder to debug and find logic errors. At least when I was troubleshooting C I could rely on the debugger to break on a bad pointer, but finding where an integer became "bad" was more time consuming.

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. Has the borrow checker become smarter since then? At the time I was very put off.

View on HN

The borrow checker has become smarter, but not at handling cyclic data structures.

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

Stuff like Slotmap should be part of the standard library instead of some github project with open issues that isn't updated for over a year.

I just glanced through the small number of open issues, and none seem like actual issues so much as potential improvements. The maintainer seems to still be around, and I've never found that a standard library is faster at merging improvements than third party libraries, rather the exact opposite (for good reason, the standard library needs to avoid breaking changes at nearly all costs).

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.

> the standard library needs to avoid breaking changes at nearly all costs

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.

Yes but everything is versioned so it's not like this will break any existing applications unless the user/owner explicitly upgrades (but then they should be ready for breakages).

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

On the other hand it means you don't automatically get security fixes and have to manually set up CVE monitoring and rebuild your application every time a CVE appears.

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.

Are we still talking about Rust or have we moved on to general grumbling about life?

Any language with an insufficient standard library and a need to import small modules in large numbers.

rust is one of them.

Yeah, I'd emphasize that moving something to the standard library doesn't magically solve maintenance issues. In fact if the community can't even maintain something then that's a strong argument for it not to be moved somewhere that's much harder to contribute to, whose maintainers have a lot else on their plate and where any API mistakes are for forever.

This is my main gripe with Rust. Things that should be part of the standard library are relegated to third parties, thus requiring developers to audit yet another dependency (and it's dependencies, and sub-dependencies, and sub-sub-dependencies, ...). Realistically, this just means I can't use most third-party crates, greatly limiting what I can do with Rust.

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.

There was a time when it felt as if every piece of interesting java code out there also came in variation badge-engineered into its matching "spring-whatever". Perhaps there is some merit to that kind of business model?

> gcc-rs splitting the Rust ecosystem into two; the current npm-style crates.io ecosystem and a more destro-centric properly vetted package ecosystem

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.

This is a tricky subject.

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.

Clearly different people have different needs.

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.

> 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

There is already, it's the nostd.

Is there any process or policy for promoting third-party libs to standard library?

A github with open issues that hasn't been updated for over a year doesn't say anything about the code or quality.

Yeah. FFS, they don't even have a JSON parser in the standard library...

As a Rust user, I have to say I think this is the right choice. Keep things out until they are practically dead/done. Rust covers a very large number of language use cases from C++ to Python. C++ doesn't have a std lib JSON parser either. And serde is fantastic!

Generally rust prefers to keep things out of the standard library because it's hard to change/improve a standard library. They try to give enough useful stuff and then leave all the other stuff to easily downloadable packages.

More importantly, it means that version upgrades are decoupled.

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.)

Hey, slotmap author here.

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).

Thank you for creating slotmap. It helps for folks who don't want to dig into nitty-gritty laborious unsafe code themselves. I only expressed the wish that something fundamental like this was was designed and incorporated as part of Rust stdlib.

What is the advantage of a slotmap style approach vs references? It seems a bit manual and error prone, and the errors risk being silent references to wrong objects that may result in security vulnerabilities or data corruption.

The advantage w.r.t references is that with Slotmap, you can express cyclical data structures, whereas with references you can't.

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!

> Slotmap keeps track of the "identity" of the stored object

(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.

I meant counted references that were mentioned as an alternative in the GP comment.

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?

> I meant counted references that were mentioned as an alternative in the GP comment.

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...

Hey, slotmap author here.

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

Hey, thanks for the great library :)

> 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.

what do most people use for a generic graph / tree library in rust?

For "proper" graphs, petgraph: https://crates.io/crates/petgraph

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>>
    }

For trees with parent pointers, I'm not sure what's most common. Potentially Rc with Weak, potentially petgraph, maybe something else.

Seriously, just use unsafe.

“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.

Sorry to stretch the analogy beyond recognition but a lot of people who would prefer C over Rust want to build a bathtub for the baby without dragging the rest of the greater metro area into the picture.

Yeah, and a ton of people still complain about having to put their seat belt on in the car too.

No, the point is that Rust does not replace C. At best, it’s “safe C++” (and even that’s debatable, given the cyclic references issue discussed here). But for the use cases where even C++ is too much, there is no replacement for C.

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.

> No, the point is that Rust does not replace C. At best, it’s “safe C++”.

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>,
    }

Wow, so difficult! If the comparison is C, I don't even have to bother writing a safe abstraction around this.

Not a rust dev, but shouldn't this be solvable using generics? At least I'm pretty sure I could construct a double linked list with a sane API using only references in C++ with templates.

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.

Not really. The fundamental issue is ownership, what is responsible for freeing resources when they are no-longer needed? In that example, owning references are used on the "next" pointers and weak references are used on the "previous" pointers. Then there are no ownership loops, and everything is fine.

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.

Why would you design a list this way? So many things are wrong here; to name just a few:

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.

I was just wondering how to do that without using 'unsafe' 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.

I feel sorry for your coworkers

Yes, I felt the same when I read the grandparent post! I am not a Rust nut (nor expert!), but the improvements offered seem very impressive. After reading your post, I immediately went to Google this phrase: "doubly-linked list in safe Rust". Plenty of good and interesting results!

There are convenient libraries for working with such data structures. Unsafe should be relegated for highly specific us cases.

If the last time you tried it was 5 years ago, then you probably didn't experience Rust with non-lexical lifetimes. That was added in around 2018 (IIRC), and radically increased the number of programs that the borrow checker accepted.

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...

Ghost-cell [0] also lets you create a doubly-linked lists (without you having to use unsafe code, and with no overhead)

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

Yea but it’s not really useable in practice as it heavily relies on nesting allocations in closures to simulate “generative lifetimes”. It’s a research artifact, not meant for serious usage. Instead, I would recommend using something like https://crates.io/crates/qcell, which works on similar principles.

It's intentionally limiting. If you need an owner, create one (call it a graph struct that holds all you nodes for example). Make lifetime management an explicit and separate concern and unit test it independently. If this is too slow for your performance needs use a library that probably uses unsafe Rust to optimize the parts that matter and that offers safe abstractions for you to interact with. If there's none, roll your own. Be happy that not everybody is slinging dangling pointers all over the place in code where it's really unnecessary.

Was about to write this exactly. Keep the lifecycle management in a dedicated component. Unsafe seems vastly overkill for dealing with this use case.

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_).

> I had trouble expressing cyclic data structures

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.

The data held by an Rc doesn't have one owner. It would probably be pretty painstaking to do cyclic data structures with them correctly, differentiating between strong and weak Rc as appropriate, but probably doable. If you don't care about leaking memory, or if the graph is static, you don't even need to worry about that.

> The "safe" solution recommended by the rustaceans was to use integers as references to the data in a vec or hashmap

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 :)

Using integers instead of pointers is a cool optimization outside of Rust as well. It lets you serialize data easier (indices are the same when you load data on a different machine, pointers will change) and can use less memory (common choices: 8, 16 or 32 bits per int; 32 or 64 bits per pointer).

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)

While that is true, using integers as pointers in Rust just makes them invisible to the borrow checker. It's a useful trick but one should be aware this is basically unmarked unsafe code.

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.

There's nothing unsafe about integer indices because access to the array they index will incur bounds checks.

This means that you have array accesses that cause index out of bounds fatal errors instead of invalid pointer dereferencing that causes fatal segmentation failure errors. Detecting this kind of bugs reliably is a very good thing, but preventing such errors (and optimizing away bounds checking if possible) would be better.

Invalid pointer dereferencing isn't guaranteed to cause segfaults, you might just get garbage memory or nasal demons from LLVM handling undefined behavior. That's the key advantage of using integers (or a GC'd language) - it's memory safe.

But if you use integers, and delete an array element and reuse it for something else, but somewhere there is a use-after-free integer, you also get garbage memory

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

That's good! That's what you want.

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

If dereferencing an invalid pointer reliably caused a segfault, this would be true. But it's undefined behaviour, so it can segfault, corrupt data, leak data, etc. Given that the possible behaviour is a superset of what can go wrong using an integer index, i would say it's worse.

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

I'm agreeing with you. I'm saying that a bounds checker is better than a segfault because it always works.

(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).

The alternative in Rust would be using `.get()` in those situations, which returns an optional result. That still doesn't account for valid but outdated array indices, though.

Using integers as allocation strategy (as in the referenced use case) will fail when slots are reused.

To be fair pointers can (and are) also reused by the OS allocators which can lead to "fun" bugs if you aren't careful

Unsafe is literally made for that. For cases when your wants can only be checked by your brain saying "I did the logic and it's all good". Ten lines of unsafe does not mean your program will blow up. If anything, it's here to encourage you to just be much more careful here.

Right, you don't have to be a purist to get safety benefits from Rust. If a Rust program is 1% "unsafe" code, it still has a far lower vulnerable surface area than an equivalent C program.

In fairness, using integer handles instead of pointers is pretty idiomatic in high-performance C++ too. I've never found it to be onerous or complicated.

Yes, using integers is not a handicap in many cases but default way of addressing.

Hey, I'm a college student majoring in Physics and wanted to ask for your email. A lot of my interests mirror yours and I want some guidance from someone who has experience with them.

I know this is out of the blue, but I really want to get in contact with you. Thanks.

Sure. But the selling point of Rust is that the compiler will check ownership and lifetimes for you. That goes away if you use integer handles, in which case I might as well use another language.

I'm not sure if that's true. The data still has an owner and when the owner goes out of scope the memory should be freed. Without the concept of ownership you might end up leaking that memory. I could be wrong, but I think that's how it goes.

Cyclical data structures are difficult to reason about, full stop - not only for the borrow checker.

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 my take too. Idiomatic Rust is "safe" in the sense that... it disallows most nontrivial data structures. Even a doubly-linked list is impossible to get through the borrow checker.

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".

Agreed, having touched browser development circa Rust’s invention, I think there are some good ideas, but the execution fell flat over the years, orthogonality broke, and thus the utility is kind of limited. I’m more excited about some newer languages to be honest.

Random question, doesn't this then defeat the whole purpose of using rust? Memory errors, that is, pointer issues are the primary source of errors that ownership in rust claims to fix. If the only way you can make nontrivial data structures is use "a ton of unsafe blocks," then you'll still likely get the memory errors, only now it's in an unsafe block...so, now everyone can just blame the unsafe block?

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.

Not really, rust has an excellent build system (better than any c++ build system I've used), great community accepted libraries for just about everything integrated well into the build system, catches a lot more "move semantic" and ownership type errors that are easy to mess up in c++. There are other things, but for me it's the excellently maintained and integrated libraries and build system that are kind of a joy to use coming from c/c++ land.

It's much easier to audit a ton of unsafe blocks beneath a safe abstraction layer than an entire codebase. And Rust provides very powerful tools like Miri which can catch pretty much any soundness issue if you have good enough test coverage.

> doesn't this then defeat the whole purpose of using rust?

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.

> 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.

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

> If you're perfectly attentive and constantly vigilant, maybe

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.)

> Even a doubly-linked list is impossible to get through the borrow checker.

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.

That looks like an allocating container. Probably the most useful property of linked lists and other node based data structures is the ability to make them intrusive and to avoid dynamic allocation. In some domains you just don't have a runtime allocator available to you, so this library would be useless.

> That looks like an allocating container

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...

Yes, and the pointer management is all done using unsafe blocks:

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

> 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.

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

> the big problem is that for applications that do need to do non-trivial reference semantics, Rust doesn't really offer much.

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].

> 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.

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?

Not all Rust programs are thin layers around libraries like FFMPEG. Why would you assume that?

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

> Why would you assume that?

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 code in those libraries has been run billions upon billions of times, by billions of people. Sure, the libraries are written in unsafe languages, but they are incredibly battle-tested. Depending on your perspective, this may or may not be as good as a formal guarantee of correctness; at the very least there is a strong probabilistic argument for their correctness and safety.

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.

> "encapsulate the unsafe code in a data structure library with a safe interface"

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".

It's true that writing code in safe Rust does not make other non-Rust code safe.

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.

Both doubly linked lists and cyclic graphs can be written in a way that satisfies the borrow checker. If not already existing in the STL, there is a crate for it 99% of the time.

> 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

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 thing is, once you get it right in Rust it just works very, very well — and it generally works multithreaded with little additional effort.

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.

Modern C++ happily introduces nightmare bugs. Banning "new" from your codebase does not prevent problems.

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.

Juggling (raw) pointers is still an option in Rust, just not the most idiomatic one. But you're right that expressing cyclic data structures is very challenging to do idiomatically in Rust.

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.

I ran into the exact same problem and wrote up some potential solutions at https://eli.thegreenplace.net/2021/rust-data-structures-with...

That's a very good point. A pointer dereferences its object, an index does not. So arguably having to switch from pointers to integers is going be a net drag on debugging since it will be no trivial to see what objects are being referenced.

Use generational arenas.

> The "safe" solution recommended by the rustaceans was to use integers as references to the data in a vec or hashmap.

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

Box doesn't solve the problem of cyclic references. And telling people they need to eat the overhead of a per-object reference count and/or weak pointer double-dereference just to write a list that can delete items in place is a pretty tall order for a language that claims to be high performance.

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.

As other pointed out, if Arc is not an option, then a well encapsulated raw pointer might just be what's needed.

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.

> a pretty tall order for a language that claims to be high performance.

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.

> 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.

unsafe is the feature you need.

The answer today is to use a GhostCell

Reply on news.ycombinator.com