4 ms·

> The first thing is that Rust is just not particularly amazing at tree structures. As someone who doesn't write any Rust I'd like to understand this more. Is

• __s 2y ago
  it's a pain if you want children to reference their parents while their parents reference them Similarly getting a mutable reference to a leaf while parents have references to children is awkward
  • giancarlostoro 2y ago
    I know just Rust basics, what specifically makes it awkward? I'm not a heavy Rust user, so I'm having a hard time following, do you have any simple pseudo-Rust code you could share? I'm also a basic CRUD app dev by day, hobbyist by night.
    • BonusPlay 2y ago
      I'm not a rust expert by any means, but I believe there's a problem with lifetimes. There are many ways to implement double-linked lists (think C++ smart pointers), but when you try to squeeze performance and use references, then it's a fight against borrow checker, which ends with the need to use unsafe rust. smarter sources: https://rust-unofficial.github.io/too-many-lists/ https://rust-unofficial.github.io/too-many-lists/ https://softsilverwind.github.io/rust/2019/01/11/Rust-Linked-Lists.html https://softsilverwind.github.io/rust/2019/01/11/Rust-Linked...
      • oneshtein 2y ago
        Borrow checker is just a checker, which ensures that programmer doesn't write obviously wrong programs. It's obviously wrong to create cyclic references, even in a language with garbage collector, such as JavaScript. Why you need to fight with checker?
        • kbolino 2y ago
          Regarding the borrow checker, what you say is not correct. The borrow checker's rules are stricter than absolutely necessary. It is designed to reject all invalid programs, but it also rejects some valid programs.
          • oneshtein 2y ago
            Yes, rust compiler team improves borrow checker from time, to allow more valid programs to pass the checker. However, in practice, it's always possible to use unsafe code to do the job, and then build a safe façade for it. In this particular case, borrow checker does it job as designed. So, why to fight it?
        • LudwigNagasena 2y ago
          Why would it be obviously wrong?
          • oneshtein 2y ago
            When tree will go out of scope, their nodes memory will be reclaimed automatically ("dropping" in Rust terms) by automatic garbage collector built-in into compiler: `drop(root)->drop(leaf_a),drop(leaf_b)`. However, if leaf will have reference to its parent, then an infinite loop occurs: `drop(root)->drop(leaf_a)->drop(root)->drop(leaf_a)...` The solution is to use an alternative automatic garbage collector instead of compiler built-in: arenas, RC with weak references, or Mark&Sweep GC. Arenas have better performance, because they drop all nodes at once. The easiest way to quickly implement an arena in safe Rust is to use vector (array) of nodes and used indices instead of direct references.
            • LudwigNagasena 2y ago
              You've said it would be obviously wrong "even in a language with garbage collector, such as JavaScript." But, obviously, most modern GC can handle cyclic references just fine.
    • oneshtein 2y ago
      Some people are trying to use references everywhere everytime, instead of (safely wrapped) pointers. It's a mental lock.
• SkiFire13 2y ago
  Actually, Rust's rules really wants your data to look like trees. Requiring each value to have exactly one owner is not really different than requiring each node of tree to have exactly one parent. The problem however comes when you want to reference the parent from a child. In the ownership/reference graph that would also count as an edge, and hence creates a cycle with the parent-to-child edge. There are workarounds like using weak reference counted pointers or indexes into arrays, but ultimately they don't offer the same ergonomics as other languages and it's better to design with only parent-to-child links.
  • oneshtein 2y ago
    Why you want to create cyclic reference from child to parent instead of a bare pointer?
    • Cyph0n 2y ago
      Because dereferencing a raw pointer in Rust requires unsafe.
      • oneshtein 2y ago
        Everything in Rust requires unsafe code at some point. Encapsulate unsafe code under safe and sound façade, and hide it in a library. Or use an existing library for memory management: arenas, RC, or a Mark&Sweep GC (rust-gc, pgc), etc.
        • SkiFire13 2y ago
          Encapsulating unsafe code behind a safe interface is not so easy (especially when cycles like these are involved) and there's always the danger of getting it wrong, so you generally want to avoid doing that. In this case using `Rc` for the children and `Weak` for references to the parent does exactly this and is included in the stdlib, so I guess I'm missing your previous point of using "bare pointer". Did you mean that the safe interface should be built around the whole tree rather than just the parent reference?