Please show me how to implement a graph library without using unsafe in Rust.

Several answers to this challenge

1) It's doable http://smallcultfollowing.com/babysteps/blog/2015/04/06/mode...

2) Which attack surface would you rather deal with... the small fraction of your graph library that deals with mutability... or all of Adobe Flash?

3) The fact is that "unsafe" doesn't mean unsafe, it means "trust the programmer that this is safe". It's reasonable to assume that safety can be maintained in Rust libraries that use the unsafe keyword.

It seems to me that an undirected graph can be represented as a map from keys to sets of keys (which can be integers, strings, or anything else), with the invariant that map[x] contains y iff map[y] contains x. For a directed graph, use two maps for incoming and outgoing, with the invariant that incoming[x] contains y iff outgoing[y] contains x.

This approach doesn't require unsafe anywhere and all graph operations are easy to implement, including deleting nodes. Am I missing something?

This argument is very flawed, since you are forced to use `unsafe` when you need anything communicating to the outside world (which includes, obviously, `println!`). The very point of Rust is to limit the unsafe surface, not to completely eliminate that.

First of all a graph library does not communicate with the outside world.

My point was that even for the ubiquitous task of implementing a graph structure, unsafe is necessary.

So while Rust may provide a clean separation between unsafe and safe code (enforced by the type system), the original problem remains: How do we ensure correctness of the unsafe parts of the code.

For what it's worth (and I intentionally didn't point this out in the parent), you can make a safe graph library in Rust with a typed arena (slightly less ergonomic and faster) or a refcounted smart pointer (slightly more ergonomic and slower). But this still does not validate your point, since the memory allocator is in many cases unsafe.

On how to ensure correctness of the `unsafe` code: that was what we were doing with the entire C/C++ code for decades, so what's the problem? We could however concentrate on the much less amount of code if we were using safer languages.

I've never actually used Rust myself - I'm just familiar with their goals: so I'm not entirely sure what you are referring to.

Just keep in mind that the amount of work done on the various C++ compilers is most likely measured in man-decades, where Rust is probably still man-hours.

Do you mean a directed graph or a graphical graph? I've implemented directed graphs in at least two different managed languages (which are more constrained than Rust) and had to use no unsafe breakouts. There might be some complexity for some reason with Rust, but if it's possible in a managed language then surely...

  >  Rust is probably still man-hours.

It's nowhere near the amount of time put into various C++ compilers, but

  1. We use LLVM, so all that time is working for us as well.
  2. Mozilla has been paying at least 4 people for at least a
     few years to write Rust full-time, I would bet we're coming
     up on a person-decade of time for Rust. The project has existed
     for eight years in total, though four of that was just as a side
     project.

I would guess that it's well past one decade for Rust (there's been 8 paid people on the team for at least a year).

  > (according to some source I read a month or two back that
  > I can no longer find).

Stuff changes fast in Rust-land, so even if it were a month or two, it might be wrong. We should always be pretty close, and we're sometimes faster, depending on the code.