4 ms·

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 nod

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?
      - oneshtein 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. Yes, it's true. Most of the time I had logic errors only in safe code and segfaults caused by unsafe code. But it's not a problem after C, where segfaults and memory leaks are norm. > Did you mean that the safe interface should be built around the whole tree rather than just the parent reference? Safe and sound (bulletproof) façade for the pointer and the tree. Safety is overloaded term in Rust. For example, when indices are used instead of references, it easy to make memory management mistakes invisible to rust compiler. Such code is "safe" in Rust terms, but unsound.
        SkiFire13 2y ago
        > Safe and sound (bulletproof) façade for the pointer and the tree That doesn't really answer my question, the façade should be either: - at the level of the pointer, meaning it offers the user all the functionality they need to code the tree data structure; - at the level of the tree, meaning the tree externally offers the user all the functionality they wanted from the tree, but the tree internally uses `unsafe` and maintains invariants that make its use sound. > Such code is "safe" in Rust terms, but unsound. You might not want to use unsound here, since that's overloaded too. The way I usually see and use those terms in a Rust context is: - safe: code that does not use `unsafe` - sound: a safe interface (i.e. callable from safe code) that internally uses `unsafe`, but there is no way for the safe side to produce UB when calling it. I would refer to the index code as "incorrect", "erroneous" or "buggy" instead to avoid the overload in this context.
        oneshtein 2y ago
        UB and unsoundness are different things. "If it compiles, then it works (properly)" is true for sound code only. Direct indexing of arrays with `for` loop is unsound, because of typical errors with indexes, such as off by one. Iterators are sound. I want to debug my code less, so I use sound interface to arrays: iterators. Other than that, both interfaces are equal. If there is no ready to use method for my usage pattern, I can write unsound code directly, or I can write sound interface and then write sound code using it, so compiler will not allow me to write stupid mistakes. Unsound version will be faster to write, but may require more time to debug and support.

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?
    - oneshtein 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. Yes, it's true. Most of the time I had logic errors only in safe code and segfaults caused by unsafe code. But it's not a problem after C, where segfaults and memory leaks are norm. > Did you mean that the safe interface should be built around the whole tree rather than just the parent reference? Safe and sound (bulletproof) façade for the pointer and the tree. Safety is overloaded term in Rust. For example, when indices are used instead of references, it easy to make memory management mistakes invisible to rust compiler. Such code is "safe" in Rust terms, but unsound.
      - SkiFire13 2y ago
        > Safe and sound (bulletproof) façade for the pointer and the tree That doesn't really answer my question, the façade should be either: - at the level of the pointer, meaning it offers the user all the functionality they need to code the tree data structure; - at the level of the tree, meaning the tree externally offers the user all the functionality they wanted from the tree, but the tree internally uses `unsafe` and maintains invariants that make its use sound. > Such code is "safe" in Rust terms, but unsound. You might not want to use unsound here, since that's overloaded too. The way I usually see and use those terms in a Rust context is: - safe: code that does not use `unsafe` - sound: a safe interface (i.e. callable from safe code) that internally uses `unsafe`, but there is no way for the safe side to produce UB when calling it. I would refer to the index code as "incorrect", "erroneous" or "buggy" instead to avoid the overload in this context.
        oneshtein 2y ago
        UB and unsoundness are different things. "If it compiles, then it works (properly)" is true for sound code only. Direct indexing of arrays with `for` loop is unsound, because of typical errors with indexes, such as off by one. Iterators are sound. I want to debug my code less, so I use sound interface to arrays: iterators. Other than that, both interfaces are equal. If there is no ready to use method for my usage pattern, I can write unsound code directly, or I can write sound interface and then write sound code using it, so compiler will not allow me to write stupid mistakes. Unsound version will be faster to write, but may require more time to debug and support.