12 ms·
I've been having a little trouble using rust for a little project: I need a tree with uplinks (meaning there are cycles). I asked on IRC a couple times and I th
by jeffdavis 9y ago
I've been having a little trouble using rust for a little project: I need a tree with uplinks (meaning there are cycles). I asked on IRC a couple times and I think what I need is a weak reference inside a refcell, but it's not very easy to make it work cleanly. For one thing, it doesn't look like refcell works well with traits (the nodes in the tree are traits, not plain structs).
I'm a bit frustrated because this is so easy in C. Is there any way this can be easier?
I am imagining a special way to construct cyclical structures where everything inside would have the same lifetime and be destructed at once. We may need to hide the references from destructors though, otherwise a destructor could see a dangling reference.
- kibwen 9y agoHave you considered leveraging crates.io? I'm not sure of your exact constraints, but I've heard some good things about petgraph: https://crates.io/crates/petgraph https://crates.io/crates/petgraph . It sounds like you might also want to check out some implementations of arenas.
- steveklabnik 9y ago> a weak reference inside a refcell, It'd likely be the other way, that is, you'd put a RefCell inside of an Rc/Weak. > it doesn't look like refcell works well with traits It should; I bet you had problems since you did it the other way around. > I'm a bit frustrated because this is so easy in C. You could do it the same way as you do it in C, if you're willing to resort to `unsafe`. FWIW, Rust sort of changes the equation for what's easy here; thread-safe concurrency? Simple! Data structures? Hard! C is the other way around. So feeling a bit frustrated is normal; your C skills won't carry over, but it feels like they should. > I am imagining a special way to construct cyclical structures where everything inside would have the same lifetime and be destructed at once This sounds like an arena to me, which is another option, for sure. If you post to https://users.rust-lang.org/ https://users.rust-lang.org/, someone might be willing to whip up an example, or if you post your in-progress stuff, someone might be able to fix it for you. https://crates.io/crates/petgraph https://crates.io/crates/petgraph might also just already have what you need, maybe.
- jeffdavis 9y agoThank you. I will look into these and give it another try. It's a good point that maybe I should just have the right expectations here, and expect data structures to be hard in rust. I looked around a bit and it looks like these thing are quite challenging in haskell as well.
- lederhosen 9y agoIn Haskell it is easy, you can not create cyclic data structures ;-)
- tome 9y agoHuh? Sure you can.
- wtetzner 9y agoCyclic data structures can be created in Haskell, in large part due to laziness.
- lederhosen 9y agoIf you see data structures as cyclic, it is not "in large part due to laziness", but _only_ due to laziness. If you look at the memory representation I think (but I am not sure) there will be no cycles between allocated objects. Only a thunk. Using strict data types, I think you agree that cycles can not be created. Non strict data structures I agree can be seen as cyclic, but I prefer seeing them as infinite.
- lomnakkus 9y agoCounterexample: $ ghci GHCi, version 8.0.2: http://www.haskell.org/ghc/ :? for help Prelude> let ones = 1 : ones Prelude> take 50 ones [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] You can take as many as you like. (The 'ones' list contains a tail which links back to its head, producing an infinite list.) Obviously, this is a trivial example, you can do much more interesting things with mutually recursive bindings.
- chancancode 9y agoHave you read "Learning Rust With Entirely Too Many Linked Lists"[1]? I think it will be quite helpful for these kind of situations. It walks you through all the possible tools in the language that is available to you, and at the end, if you just want to write it how you would in C, you could always do it "unsafely" with raw pointers (which is no worse than C). --- [1] http://cglab.ca/~abeinges/blah/too-many-lists/book/ http://cglab.ca/~abeinges/blah/too-many-lists/book/
- reificator 9y agoBeat me to this by six hours. Can vouch that the above link is quite helpful when learning Rust.
- alphaalpha101 9y agoIt's also really no better than C. Or at least no better than C++. This is my main issue with Rust. It doesn't seem to really solve the right problem. I feel like it solves the easy problems that I already know how to solve easily, but as soon as I get to something that really, truly feels like I want it, the best solution is unsafe. A complicated circular linked data structure is exactly where I want the language to be screaming at me if I make a silly error. But Rust doesn't even consider memory leaks to be errors...
- jacobush 9y agoHere have an upvote. Can someone else comment/refute this?
- kevincox 9y agoI don't really have a refutal, but more of a dismissal. Almost all of the code I write just uses prebuilt data structures (other then structs to group things) and when writing this code I find the safety measures that rust provides very convenient because I don't have to worry about these things such as lifetimes. It is nice knowing that the compiler will let me know if I make an error. However yes, it doesn't solve the hard probem of complex circular structures. I don't see this as a major issue because when I am writing these I am carefully thinking about the strucutre anyways. So yes, while it would be nice to have these verified as well I wouldn't want take the tradeoff if it made the language much more complex.
- msbarnett 9y ago> I am imagining a special way to construct cyclical structures where everything inside would have the same lifetime and be destructed at once. The simple way to do that would be to allocate an array, and use indices into the array rather than pointers/references. Doing it with pointers isn't so much harder in Rust than C as it is that Rust is making you deal with how hard it is to get this right, whereas in C the compiler is happy to let you think it's easy while you accidentally shoot yourself in the foot. If you want the Rust compiler to accept your mistakes, you can always wrap it in an unsafe block ;)
- fish_fan 9y agoWhile it may be simpler, it also removes any safety that rust adds. I'd imagine you'd get more mileage out of just using pointers and unsafe blocks liberally to get lifetime checking where you can.
- skariel1 9y agoIt is still safer than c, as it will not allow any segfaults. The only thing that can happen is a runtime error but no memory corruption so it is more akin to say Java or Go
- steveklabnik 9y agoThe context of this thread is unsafe, which can segfault.
- ComputerGuru 9y agoYou are describing the behavior of standard, safe rust code. Using unsafe blocks throws all that away.
- jeffdavis 9y agoBut in my example this is not hard to get right in C. The tree is constructed (on the stack would be fine), then used for a while without mutating it, then freed all at once. The thing that makes this hard in rust is destructors. If there's a cycle between A and B, and you destruct A first, then B, then B's destructor would see a dangling reference to A. And vice versa if you destruct B first. But I don't need destructors, or at least ones that can see these references, so it's frustrating.
- comex 9y agoRegarding traits: you can have Rc<Trait> (by casting from Rc<your concrete type>), but not RefCell<Trait>. The reason is that Rc is a pointer, so the size of Rc<Trait> can be constant regardless of the size of the type implementing the trait. But if you actually want a weak reference inside a refcell (as opposed to the other way around), RefCell<Weak<Trait>> should work fine. Also consider the Cell type, which has a more limited API than RefCell but zero overhead. Regarding everything being destructed at once: that’s called an arena, and there are crates for it: https://crates.io/crates/typed-arena https://crates.io/crates/typed-arena
- circlingthesun 9y ago> Regarding everything being destructed at once: that’s called an arena Thats such a great name :)
- pjmlp 9y agoIt is quite common name for memory pools.
- jeffdavis 9y agoArenas have more to do with the allocation pattern, they don't solve the cycle problem, right?
- trishume 9y agoYou're correct, that crate doesn't solve the cycle problem. There is a different way of doing arenas in Rust that does though. What you do is you put all of your tree nodes in a big Vec<Node> and instead of referring to children and parents via pointers, you do so via indices. It's less convenient because you have to pass around a reference to your "arena" everywhere (the Vec or a slice of it), and it incurs bounds checks (pretty cheap though). But, it solves the problem in a way that is guaranteed safe.
- GolDDranks 9y agoIn a sense, they solve the cycle problem in Rust. The trick is that once something is allocated to an arena, it has the same lifetime as the whole arena, and that allows cyclical links because none of the nodes "outlive each other". However, you must have interior mutability (achieved using Cell types), because otherwise you can't mutate the parent nodes to add links to child nodes. Check the typed arena crate in crates.io and the Cell type in the standard library.
- whyever 9y agoI think I would just put all the nodes into a Vec and use indices instead of references. This results in every node having the same lifetime, like you wanted. It is what the specialized graph libraries like petgraph are doing, and it is memory safe due to bound checks.
- stjepang 9y agoIt's fairly easy to do this kind of thing using an arena and indices instead of pointers. Here's a simple splay tree with uplinks implemented this way: https://github.com/stjepang/vec-arena/blob/master/examples/splay_tree.rs https://github.com/stjepang/vec-arena/blob/master/examples/s...
- kannanvijayan 9y agoFrankly, I'd just use unsafe pointers for the backrefs, and wrap the tree API up in a typesafe layer, and build on top of that. RefCells seem to add unnecessary redundancy here. You'll take a hit for runtime borrow for every pointer chase up the tree. If walking from a leaf to the root is important, you don't want to add an extra compare/branch/set to every pointer chase. Turns a single memory read into a branch, a write, and two reads. Probably about 5x slower at least.
- hashmal 9y agoI'd take a similar approach. After all `unsafe` use cases include the implementation of data structures.
- Animats 9y agoI've argued this issue before. The answer isn't generics, Coq, or some fancy type system nobody will understand or use properly. There are only a few inherent trouble spots in pure Rust code safety. The big two are: - Partially initialized arrays. "Vec" has to be unsafe because growing an array involves uninitialized slots. You just need a way to say "this array is initialized from 0..N only", where N is in a data structure associated with the array. Then you need an operation that says "initialize entry N+1 and update the count". That's all it takes. "Map" could be implemented on top of "Vec", instead of using unsafe code. It would be worth trying this and seeing what the performance penalty is. That may be a premature optimization. - Backpointers. Backpointers have an easily checked invariant relationship with the forward pointer that owns their containing object, but there's no way to tell the language that something is a backpointer.
- hashmal 9y agoQuite often in Rust, the way to make it easier is to go one step back: instead of thinking about how to make a tree right, you might want to think about why you want a tree in the first place. Sometimes it's the right thing to do, sometimes there is another approach that fits Rust's paradigm better. Speaking of paradigms, although Rust definitely looks "imperative", the ownership system makes it bloody different. Try to implement a tree "as in C" using Haskell or Prolog and you will lose time and energy for a result that does not use the language to its fullest.
- ComputerGuru 9y ago> instead of thinking about how to make a tree right, you might want to think about why you want a tree in the first place. Sure. But that's true for every programming languages, at least in my experience. Anyway, someone, somewhere will actually want/need that tree. And they'll run into the aforementioned problems.