4 ms·

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

by sdf45 11y ago

lifthrasiir 11y ago
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.
- sdf45 11y 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.
  - lifthrasiir 11y 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.
jganetsk 11y ago
Several answers to this challenge 1) It's doable http://smallcultfollowing.com/babysteps/blog/2015/04/06/modeling-graphs-in-rust-using-vector-indices/ 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.
zamalek 11y ago
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...
- steveklabnik 11y 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.
  - dbaupp 11y 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).
cousin_it 11y 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?

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

by sdf45 11y ago

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

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.

sdf45 11y 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.
- lifthrasiir 11y 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.

jganetsk 11y ago

Several answers to this challenge 1) It's doable http://smallcultfollowing.com/babysteps/blog/2015/04/06/modeling-graphs-in-rust-using-vector-indices/ 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.

zamalek 11y ago

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

steveklabnik 11y 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.
- dbaupp 11y 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).

cousin_it 11y 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?