undefined | Better HN

0 pointssdf4510y ago0 comments

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

0 comments

8 comments · 4 top-level

lifthrasiir10y ago· 2 in thread

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.

sdf45OP10y ago

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.

lifthrasiir10y ago

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.

zamalek10y ago· 2 in thread

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

steveklabnik10y ago

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

dbaupp10y ago

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

jganetsk10y ago

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.

cousin_it10y ago

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?

j / k navigate · click thread line to collapse