6 ms·

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 pointe

• 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
          But even languages with Tricolour Mark&Sweep GC, which handles cyclic references just fine, it's still possible to make memory leak via a dangling reference to a node in a complex cross-linked graph, because language and GC allows that. Rust by default forbids cyclic references, by forcing to use trees, which completely avoids the problem.
          • LudwigNagasena 2y ago
            You can leak memory in any complex project, even if you only use safe Rust. Linux kernel uses doubly linked lists, Redis uses doubly linked lists, V8 JS engine uses doubly linked lists. Have their authors chosen something obviously wrong?
            • oneshtein 2y ago
              Rust uses double linked lists, they are not harder to implement in Rust than in any other language. Moreover, built-in borrow checker will help to implement them properly, without memory leaks or use-after-free. What is your point?
  • __s 2y ago
    garbage collectors detect cycles. you may be thinking of reference counting. CPython includes a gc for cycle detection
    • oneshtein 2y ago
      Some GC detects cycles, some not (reference counting is example of GC which does not), but even those which detects cycles, may not able to detect all of them or it can be expensive as, for example, in typical Mark&Sweep GC, because it may require to stop the world to perform GC, which is unacceptable for system programming languages, like C, C++, Rust.
      • pebal 2y ago
        You can have completely pauseless GC tracking, also in Rust.