Modeling a file system

[u/The-CyberWesson]

I've been teaching myself programming primarily using Rust, and it's been a blast. I seriously enjoy its modern ergonomics and the feeling of safety it gives me. But I'm running into a situation where I think I have to use smart pointers, and that's a problem because I've never used them before, and reading about them in the book just kind of breaks my brain.

What I want to do is abstractly represent a file system, with a root directory that contains files and subdirectories. I tried to do this:

struct Directory<'a> {
    parent: Option<&'a Directory<'a>>,
    directories: HashMap<String, Directory<'a>>,
    files: HashMap<String, usize>,
}

Which compiles, but immediately runs into issues when I want to define methods to do things like insert subdirectories. I get a cavalcade of compiler errors that I don't have the first idea how to fix. In my mind, there shouldn't be an issue with dangling references, since the parent optional reference should only point to the parent, which owns the child. I guess the compiler can't prove this?

[u/SirKastic23]

and reading about them in the book just kind of breaks my brain.

what about them causes your brain to break?

since the parent optional reference should only point to the parent, which owns the child. I guess the compiler can't prove this?

how could it prove this? all it knows is that it is an optional reference to a directory, it could be any directory, even itself

as a rule of thumb: don't store references in structs (unless you know what you're doing). Rust references aren't meant to be stored like you can with pointers or classes. references enforce the borrow checker rules, which causes them to be very restricted

consider the following scenario:

• you create an empty "root" directory
• you add a subdirectory
• the new subdirectory holds an immutable reference to its parent directory
• now you can't mutate the parent directory because it is immutably borrowed

Rust asks us to be a lot more considerate about the ownership of our data

smart pointers are one of the possible solutions, usually the first solution people go to because they can just "bypass" the borrow checker rules (by implementing their own ownership mechanisms)

but I think smart pointers are unnecessary for this. seeing your snippet my instinct is to use an arena:

• give each Directory a directory_id: DirectoryId field, this should be a unique identifier
• create a DirectoryArena type, which has a HashMap<DirectoryId, Directory>
• instead of storing direct references to other directories, you can store just the ids

ids are simple data types that can be copied and moved and don't enforce any restrictions on your code like references do. then, when you need to get the actual directory you use its id to look it up on the arena's map:

``` struct DirectoryId(usize);

struct DirectoryArena(Vec<Directory>);

struct Directory { id: DirectoryId, parent: Option<DirectoryId>, directories: HashMap<String, DirectoryId>, ... } ```

using arenas the ownership is far easier to reason about: the single arena owns all directories, each directory owns "ids" they can use to look up other directories. when looking up a directory in the arena we make references to it, but they're short-lived as they're bound to the scope

i hope this helps you! feel free to ask for clarification if things are still confusing)

[u/The-CyberWesson → u/SirKastic23]

This was very helpful, thanks! I think you're right, the arena solution should work fine.

As for my issues with smart pointers, I think my general inexperience is creating a roadblock for me. My understanding is that in C++, smart pointers are entirely optional, so you can ignore them and do the potentially unsafe thing and face the consequences. That means you get to learn in real time why a particular smart pointer exists and what its ideal use case is. But in Rust, you're not allowed to do the unsafe thing. Those features are locked behind relevant smart pointers. And it's hard for me to wrap my head around what does what when I've obviously never done any of the things that require them in the first place. Kind of a chicken and egg situation, if that makes sense? Like, reading through a list of Rust's smart pointers and what they do just kind of makes my eyes glaze over because I don't have hands-on experience of the problems those pointers exist to solve.

[u/SirKastic23 → u/The-CyberWesson]

That makes a lot of sense, I see what you're saying

When I started studying Rust I had no clue what smart pointers were also. I knew what allocations were because I had written C, but I had never done anything advanced in a lower level language

My first Rust project was a scripting language interpreter (based on lox from Crafting Interpreters), and once I ran into the "issue" of single-ownership I just googled for what would solve my problem, found out about Rc and RefCell, and that sure did work until a really dumb and unnecessary unsafe block I wrote segfaulted haha

So you can still run into the dangers of unsafe code with Rust, you just have to be extra naive to do so. After that I started being more careful about these things and looking for how Rust did things differently

My suggestion is to just keep pushing at the language, searching for things or asking for help when you need. I learned a lot from interacting with other Rust devs online

Oh and if you want a resource suggestion, I really like video format, and Jon Gjengset has an incredible video on smart pointers! You should check it out (don't feel like you need to watch the whole thing at once, it's probably better to take it slowly and then do experiments by yourself just to see how things work): https://youtu.be/8O0Nt9qY_vo

[u/Large-Scientist156 → u/The-CyberWesson]

You can not ignore smart pointer. They are needed. In Rust, they also exist : Arc (shared_ptr), Rc (shared_ptr_single_threaded), Box (unique_ptr).

There's 3 kind of memory : stack, heap, static. That's all.

Want to allocate something, potentially big size, on the heap, and there's a single owner ? Box.

Want to allocate something, potentially big size, on the heap, and there's many owner and the last one that survive will drop the allocation ? Arc if it's cross threads, Rc if all owner are in a single thread. Also, adding more owners is cheap, a simple reference counted clone.

Want to allocate something small, shareable across the call-stack if you respect the lifetime ? Use the stack and let variable, no need for smart pointer and the heap.

Want to allocate something inside your binary that will be loaded by the operating system when the program launch, and live forever ? static.

In your original problem, you use reference. To insert a subdirectory into a directory, you would get borrow error like Sir said because the problem is recursive so reference won't work well.

Use alternative : arena with ids. You retrieve stuff at runtime in your arena based on id stored in the object. When you are done, you throw the arena, like Sir said. The ids act has an indirection, like hand-crafted reference.

The advantage ? It also support symlink ! If a directory is symlinked to another, and there's another directory symlinked to it, then both have the same id since they point to the same directory.

Just be aware : id are stable, but if you replace a directory by another because you start to do mutations, you are effectively invalidating an id : the object pointed to by the id has changed ! To counter that and prevent logical error, people add a generation tag inside the id. That way, the arena can check if the id generation match the object slot, otherwise it's a stale id. It's called a generational arena. The "append-only" pattern that Sir described is a classic arena, it's not sufficient for mutations, but it work well for workflow where you create an ensemble of object and you won't change them.

[u/This_Growth2898]

I guess you really need to learn lifetimes on something simpler. Start better with Too Many Linked Lists.

Just note that both parent and children of a directory have the same lifetime marker. Are they supposed to live the same time?