Well, petgraph uses vectors and indices to avoid unsafe code, and it's the most popular graph library on crates.io.
Really, the answer here is "use a graph crate on crates.io". If you don't know which one to use, the best answer is probably petgraph.
> The Servo team really wants GCed, safe pointer support in Rust, and design work is well underway. But it's going to take a while to stabilize.
We aren't going to use GC'd pointers for any of the trees except the DOM. GC is way overkill for this use case. The reason why we want GC support is not to make tree data structures: it's for integration with JavaScript.
Nice! I hadn't seen that yet, but it looks really interesting:
http://bluss.github.io/petgraph/doc/petgraph/graph/struct.Gr...
Edit: Doesn't occur on IE 11, so it seems Chrome specific.
Like someone else said recently, it's a problem if you can't reasonably teach a basic computer science course in Rust.
But if you want to teach an operating systems course or build cyclic, pointer-based data structures, you'll usually need a modest amount of "unsafe" Rust. Using "unsafe" gives you access to real pointers, which work just like they do in any systems language.
It's just that Rust chooses to lock those features away when you don't explicitly ask for them. If you actually need "unsafe", it's no more dangerous or more difficult than writing C code.
It's not a kludge. It's how you prove to the compiler that you're using those structures safely.
If you aren't used to programming with compiler-enforced safety, you might be tempted to call working with the safety mechanisms a "kludge". But in reality all you're doing is doing things a little differently so that the compiler can ensure safety.
For the article author, I'd recommend going down a virtual DOM like approach rather than traditional OO toolkit. Rust meshes a bit more closely with functional ideas than OO.
(It's not a basic course, but you absolutely could.)
I am currently "attending" the above mentioned course by following along online. I am enjoying it very much so far. There have been three assignments so far, the first of which was to get rust installed and such. I think it would take most of the HN crowd less than a week to catch up with the course so that they can follow it for the remainder of the semester, even if they have a day job. The most experienced programmers might be able to catch up within just a few hours.
The schedule at https://cis198-2016f.github.io/schedule/ has links to the slides, lecture notes and assignments.
I doubt they have to be. There are other ways to do GUI, see for instance how Light Table uses a database-like Entity Component System. https://www.youtube.com/watch?v=V1Eu9vZaDYw
However, that does not solve the problem that all the mature existing UI widget toolkits are based on inheritance, and that causes a serious "impedance mismatch" with languages that don't have inheritance.
As I expect more languages to start privileging composition over inheritance, I also therefore expect this problem to continue to become more acute until "someone" finally solves it. However, GUI toolkits are huge and "someone" is likely to be a substantially-sized organization. The problem is going to have to become very painful before it is solved well.
I'm pretty sure properly written GUI toolkits can be much smaller. As in, satisfying 90% of our needs in a couple thousand lines of code. (The remaining 10% might require heaps and heaps of code, but I'm sure it doesn't have to affect the core.)
It's only an intuition at this point (I have yet to implement my own GUI toolkit). But I have reasons to believe this intuition is right: http://www.vpri.org/pdf/tr2012001_steps.pdf
The "long tail" is like the long tail of Excel or Word; yeah, everybody only uses 5% of it but everybody uses a different 5%.
I'm pretty sure properly written GUI toolkits can be much smaller...
Like, I'm sure you can write a procedural generator in a handful of lines of code that spits out the full works of Shakespeare. It's probably possible, if you have the right seed and the right algorithm.
...but practically speaking, how do you actually build one?
The same goes for UI libraries; certainly it should be possible (in theory) to have a minimal beautiful GUI libraries with an excellent API; but every attempt to build one seems to have failed.
Perhaps the problem domain is actually more difficult than you're giving it credit for...
I'm pretty sure we haven't explored the sheer depth of simplifications that can still be done.
I can't find anything on their website that seems to be that sort of thing?
Their writing is here: http://vpri.org/html/writings.php
Their various reports are there (most recent first):
http://www.vpri.org/pdf/tr2012001_steps.pdf
http://www.vpri.org/pdf/tr2011004_steps11.pdf
http://www.vpri.org/pdf/tr2010004_steps10.pdf
http://www.vpri.org/pdf/tr2009016_steps09.pdf
- http://www.fltk.org/index.php - https://github.com/froggey/Mezzano
Then again most gui libraries end up including networking, file handling, etc...
> Unfortunately, the correct idiomatic way is that you try very hard to avoid doing so. Rust is all about clear ownership, and it doesn't like circular references.
> The usual solution is to put the cyclic graph code into a library, and to use pointers and about 20 lines of unsafe code.
The point about C++ is important. Cyclic graphs are hard in any non-GC'ed language because it breaks the ownership story.
That indicates a fundamental design flaw in the language.
Safe Rust allows one to do an incredible amount of things whole providing strong guarantees against the sorts of problems that plague lower level languages. Since this isn't suitable for absolutely everything, we have unsafe Rust to fill in the gaps in the small areas it's needed. Unsafe Rust isn't "bad", it just doesn't provide the same guarantees as safe Rust. And if something goes wrong, you can at least narrow down your search to unsafe areas of the code.
This isn't the sign of fundamental language design flaws. It's the sign of a phenomenally well-designed language, where the downsides of seldom-needed yet powerful features are limited to only those areas where they're used.
So I'd think a better way than saying "don't do that - or if you have to, you're on your own" would be to analyze use cases and see which scenarios the language can satisfy. (As another poster suggested in making "parent pointers" an explicit language feature(
- Back pointers. (They're not owning pointers, and they have a well defined relationship with some other pointer. The language may need some way to explicitly say that.)
- Collections where not all slots are initialized. (This requires simple proofs by induction as you grow a collection into previously allocated unused space.)
For real, honest-to-god, cyclic data structures — just use unsafe Rust. Again, unsafe Rust isn't "bad". It's just unsafe. More care will be expected of the code to ensure that it exports a safe interface, but nothing in the language stops you from doing it. There's quite literally no loss of expressive power.
No. That's only true if the unsafe code presents a completely safe interface to its callers. If the safe code opens a hole in Rust's protection system, which is very easy to do, you can now have C-type no-idea-where-it-is bugs.
It is not mandated that you 'must' write safe code but that you 'can' write safe code. So there really is no fundamental assurance that rust and its libraries are in fact 'safe' by Rusts own definition in any meaningful sense.
You could make the same style argument that C is a 'safe' memory language also as long as you use automatic memory management and no malloc. Of course that would be a rather disingenuous claim to make.
That said, people also need to understand that many such instances are not design flaw, but are instead design tradeoffs. The OP indicated that having to switch to unsafe Rust to represent a cyclic datastructure is a design flaw. My response is that it's a tradeoff that pays dividends in every other piece of code.
Can Rust improve upon the number of problems that can be solved with safe vs. unsafe Rust? Absolutely! Is it worth cordoning off a few cases that don't technically need unsafe behavior, to ensure all other Rust code performs safely? Emphatically yes.
As somebody who has used Rust since late 2012, I completely agree. It seems that most of the more sweeping claims come from those new and excited users - hopefully over time this will soften and become more reasonable. Hype is definitely something that needs to be kept in check though, as it more than often results in a back-fire.
It indicates that idiomatic Rust doesn't like cyclic references and thus you must step outside safe, idiomatic Rust to do that, it really just means that every language has an idiomatic way to do things to stay on that idiomatic road and not every way of doing things fits the idioms - they're still possible but not idiomatic. Given how the ownership system works, it makes sense
You may say that that indicates a flaw in the ownership system, but it doesn't. The ownership system can do certain things, but not all of them - it's designed to prevent the majority of common memory safety violations, but if it can't prove everything. That doesn't indicate a design flaw, it indicates a system limitation, same way a GC pause it's not a design flaw, but rather a limitation of a well deigned system.
UIs work routinely by the organizational principle the author is attempting. Nested groupings of related functions that often interact in small groups.
And the thing is, a pointer to your parent doesn't semantically mean an ownership relationship anyway. It s in fact an extremely clear declaration of the ownership contract because while the owner can own many things, an object in this graph can have but one owner.
Now, I'm not sure how you would encode this into a compiler, so the discussion may have to end there as being impractical to implement.
I believe that the JS engine has ownership over the DOM, and pointers into the DOM are GC'd by the JS engine. This is part of the motivation for adding hooks for GC's in Rust. These posts [1][2] discusses this, although I think there is a more recent one. Edit: more recent one here [4].
> Now, I'm not sure how you would encode this into a compiler, so the discussion may have to end there as being impractical to implement.
This seems like a good use case for a Weak<> pointer [3].
[1]: http://blog.pnkfx.org/blog/2015/11/10/gc-and-rust-part-1-spe... [2]: http://blog.pnkfx.org/blog/2016/01/01/gc-and-rust-part-2-roo... [3]: https://doc.rust-lang.org/std/rc/struct.Weak.html [4]: http://manishearth.github.io/blog/2016/08/18/gc-support-in-r...
The road to hell is paved with good intentions, and I know myself and my cohort well enough that I appreciate the Rust sentiment on this subject. It was the main feature that drew my attention.
I'm wondering if this is a concrete concept that could be build into the ownership system. Logically speaking, this back pointer only exists to allow objects that are part of a Composition to reason about their environment, or be reasoned upon by an outside observer.
Maybe some of this information already exists in the language internals and you just need a function that can expose the owner of record of the object... There can only be one, right?
Any details on this? GCs and finalizers don't really work well together, which is why I gave up on my cycle detector implementation.
The reason Servo in particular would like GC hooks is because JavaScript is GCd and we want to be able to pass around Spidermonkey-managed pointers safely. We have a framework in place that does this, but proper compiler support would be nice.
Servo doesn't need to worry about finalizers because our DOM structs never have nontrivial destructors (explicit Drop impls).
The blog post throws around some ideas for dealing with the finalized problem though.
> traditional object-oriented GUI designs may be awkward
For example, Qt has moved that tricky part into a specialized language. I think that it's the way to go.
So it's okay if a low-level language is not designed to do that ancient stuff with pointers to widgets.
> So a trait can define abstract functions, but can't access any underlying fields.
In Rust, a trait is a purely abstract interface to a type. It explains how you can use that type, but it knows nothing about the implementation.
I'm not quite sure what the design goal was with the Widget type, but the closest solution is to replace the member variable in the abstract type with some kind of accessor (and to replace the magic negative font sizes with an Option):
I'm not sure this is how I'd personally design this, but it should compile.> What IS the idiomatic Rust way to do a cyclical directed graph?
Unfortunately, the correct idiomatic way is that you try very hard to avoid doing so. Rust is all about clear ownership, and it doesn't like circular references.
The usual solution is to put the cyclic graph code into a library, and to use pointers and about 20 lines of unsafe code. (EDIT: See below for a better solution.) It's not much different from the C++ solution.
The Servo team really wants GCed, safe pointer support in Rust, and design work is well underway. But it's going to take a while to stabilize.
GUI libraries are an interesting special case: They involve huge class hierarchies, lots of implementation inheritance, circular references, and tricky ownership. Most older OO languages were optimized for this case. Newer languages tend to favor flatter type hierarchies and far less implementation inheritance. Which means that traditional object-oriented GUI designs may be awkward.