Comment by jcranmer | Hacker News Reader

Comment by jcranmer | Hacker News Reader

Parent Full thread

The basic model of Rust is to move use-after-free from a dynamic, runtime check to a static, compile-time check. But to keep the static checks from being Turing-complete, you need to prohibit arbitrary cycles while something like a tree (or other boundable recursion) is doable. So Rust not being able to check cyclic data structures isn't a "Rust currently can't do better" situation, it's a "Rust just can't do better" situation.

What Rust's intended solution for that is that you add in data structures that do the dynamic checking for you in those cases. But the Rust library doesn't provide anything here that's useful (RefCell is the closest alternative, and that's pretty close to a this-is-never-what-you-want datatype), which means your options are either to use integers, roll your own with unsafe, or try hard to rewrite your code to not use cycles (which is usually a euphemism for use integers anyways). The problem here, I think, is that there is a missing data structure helper that can sit in between integers and references, namely something akin to handles (with a corresponding allocator that allows concurrent creation/deletion of elements).

missing data structure helper -- didn't you already just name-check that though, since that's basically RefCell .. or if you're willing to roll the dice... UnsafeCell (aka "trust me I know what I'm doing")?

What you essentially want for the user to not write any unsafe code is this kind of interface:

   trait Allocator {
     fn allocate<'a, T>(&'a self, init: T) -> Handle<'a, T>;
     fn deallocate<'a, T>(&'a self, handle: Handle<'a, T>);
     fn read<T>(&self, handle: Handle<'_, T>) -> impl Deref<T>;
     fn write<T>(&self, handle: Handle<'_, T>) -> impl DerefMut<T>;
   }

&'a RefCell<T> is pretty close to a definition of Handle<'a, T>, except that Rust provides no implementations of allocate and deallocate that take a const instead of a mut reference for self. Trying to make an allocator that lets you safely deallocate something requires a completely different implementation of Handle<'a, T> than what RefCell can provide, and even if you're fine without deallocation, allocation with a const ref still requires unsafe to get the lifetime parameter right.

Can you clone a Handle? If so, how do you handle using a clone after freeing it? If clones are refcounted, how do you handle cycles?

There are several different ways you can implement a Handle, depending on what features you want; the most important part of its implementation is that `fn is_valid(handle: Handle) -> bool` is possible. The simplest implementation is a (pointer, generation) pair, which can be packed into a u64 pretty easily even for 64-bit systems; every allocation and deallocation increments the generation counter in the allocator, and is_valid is thus implemented by checking if the allocator's generation matches the claimed generation for a Handle. This kind of Handle is effectively a Copy implementation (not merely Clone!).

Effectively, handles are like weak pointers in that you can detect when the underlying object has been freed, but unlike weak pointers, there's no need for a reference counter to know when to deallocate the object--the object is freed when the allocator itself dies, or it can manually be freed earlier. It is possible to write code that will attempt to use the freed object, and the compiler will be happy, but the runtime will detect that it has been freed and panic instead. (RefCell does something similar, except it only detects violations of multiple readers xor one writer requirement, not overall lifteime). You can also add other wrappers around Handles to automatically free those Handles on scope exit, but the point is you can now have multiple references to an object that can be upgraded to a mutable reference if you desire.

Did you get a look at https://github.com/rust-lang/rfcs/pull/3446 at all?

I'm not in the habit of regularly following new Rust RFCs, so I'd have no way of knowing about something made just last week. :-) But I'm taking a look now.

I don't tend to follow them either, but I've been frustrated by the lack of progress on allocator_api, and I came across this yesterday after looking into that. I only mention it because the Handle stuff in there looked tangentially related, though it's talking about something quite a bit different than you were.

Reply on news.ycombinator.com