Complex hierarchy with parent/sibling pointers

How do you plan to prove that your structure wouldn't end up in the inconsistent state?

In other languages, this would be the onus of the programmer. I'd ensure invariants are held through asserts, but I wouldn't be able to guarantee memory safety, no dangling pointers etc. In Rust, this is handled for us by the compiler. Great! But, how do we do this given the current requirements? I'm a Rust novice.

Which it already is judging from your definition.

In other languages, we would encapsulate together data and code to provide better readability. In the Rust version it's one big Tree class with logic all over the place. The interface isn't clear and neither is the change propagation.

That's true only if people “outside” couldn't keep references to members of your structure. And then the decision becomes obvious, isn't it?

Correct, no other threads have pointers into the Tree structure. Its entirety is owned by a single thread. What do you suggest?

The Rust compiler knows how to prove that certain specific usage patterns are memory safe. It cannot reason that an arbitrary data structure is sound — that's known impossible via the undecidability of the halting problem — but not only that, it has very limited understanding overall. In fact, the thing the compiler checks the most about — references — are mainly only usable in specific temporary situations (passing a reference to a function). The rest is all based on Rust's single-ownership/"move" system, carefully-written code in std (e.g. the code of Box, Vec, and Rc), and module privacy preventing the outside violation of invariants maintained by that code.

(Arguably, it is a good thing that the compiler is not very smart about this; if it were to try to analyze your code in clever ways to prove more possible programs sound, then when it fails to do so the error messages would become less clear, and the boundaries of what is permitted — the definition of “what is a valid Rust program?” — would become harder to understand.)

The reason “don't have parent and sibling pointers” is such common advice is that it lets you stick to the things the compiler knows how to reason about, so it is the least complication in many situations. If you want to actually have parent pointers, then you will have to either write unsafe code with raw pointers (promising the compiler that you know exactly what you're doing) or use Rc<RefCell<Node>> for child links and Weak<RefCell<Node>> for parent/sibling links.


Another option is worth mentioning. If the data structure you are attempting to build is more like a graph than a tree, perhaps you could use an existing graph structure crate like petgraph.

I don't have strong opinions over which crate you use, but it is certainly beneficial to look for a well-supported crate so you don't have to write unsafe code as a newcomer to the language. Largely because you cannot be expected to understand all of the rules and invariants to uphold to write unsafe code that is also sound.

The idea was that by providing readability you may achieve safety, too.

it doesn't work. Java programs may be free from memory corruption, but they corrupt data structures they use just fine and access to stale data, data races, violations of invariants and so on are still common.

Rust can not eliminate that, but it tries to reduce scope. In particular it views on arbitrary graphs is highly sceptical. It just doesn't do them.

Well… that how you defined the interface.

The whole thing reminds me of incident in college. Where one of my friends was presented with flow-chart written by some “old school” customer.

On A1 (or was that A0?) paper in a tube with literally hundreds (if not thousands) of rectangles. Connected in seemingly arbitrary way.

Client was extremely smug and explained how he would force my friend to abandon this structured programming nonsense and make him write good old GOTO-based FORTRAN pogram.

Of course college abandoned FORTRAN long ago, it wanted Pascal and GOTO was forbidden.

In the end program was, formally, structured, it contained variable "state", dozens of procedures and plug switch (to avoid GOTO).

it was as incomprehensible as that original flow-chart but it was, formally, structured programming-compliant.

That's what you are, essentially, trying to achieve here.


Yet you actively try to avoid learning Rust. That's Mistake #3, Mistake #6c, Mistake #12 from the well-known list.

It's not impossible to write Rust program that way, mind you, but in the end you would have something that's harder to modify and write than if you would have implemented it in a different form in a different languge and you would be left confused about why people say Rust makes your programs easier to design and modify. Other than that… no difference.

Like my friend was confused after I helped him create “FORTRAN spaghetti in PASCAL guise”.

I have no idea why you want to learn rust in such a masochist way, but you have your reasons, I guess.

In particular this is very telling:

You still, somehow, tell us that again and again. In Rust each and every program have to be ready for multithreading. By design.

Whether your data structure is confined to a single thread or if it's executed in bazillion threads is a tiny implementation detail, as far as Rust is concerned you still have to do everything properly.

If you are using multi-threading you use std's Mutex, if you use async your choice would be tokio's Mutex, if program is single-threaded then you may use std's RefCell (but it's not compatible with async which means your Tokio is an implementation detail is also wrong: it maybe an implementation detail but it would leak out into your design).

This was already mentioned. As well as recommendation to first learn Rust and then try to solve some task which is ill-suited for Rust.

Before you may do that you have to pass “step zero”. Switch from “I'm an expert C++ (C#, Java, JavaScrtipt, PHP, Python, etc) programmer, I don't need to learn Rust, I would just quickly find out “how to write C++ C#, Java, JavaScrtipt, PHP, Python, etc) in Rust” and I'm good to go” to “I know that Rust is raising the abstraction and that “writing 𝓼𝓸𝓶𝓮-𝓸𝓽𝓱𝓮𝓻-𝓵𝓪𝓷𝓰𝓾𝓪𝓰𝓮 in Rust” wouldn't work”.

Then you can learn Rust and learn how you deal with things which Rust can do cleanly and then go back to complicated constructs from other languages and see what you can do to them and when.

It's structured programming all over again: Us converts waved this interesting bit of news under the noses of the unreconstructed assembly-language programmers who kept trotting forth twisty bits of logic and saying, 'I betcha can't structure this.' Neither the proof by Böhm and Jacopini nor our repeated successes at writing structured code brought them around one day sooner than they were ready to convince themselves.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.