3 ms·

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

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).

cmrdporcupine 3y ago
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")?
- jcranmer 3y ago
  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.
  - nyanpasu64 3y ago
    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?
    - jcranmer 3y ago
      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.
  - cmrdporcupine 3y ago
    Did you get a look at https://github.com/rust-lang/rfcs/pull/3446 https://github.com/rust-lang/rfcs/pull/3446 at all?
    - jcranmer 3y ago
      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.

cmrdporcupine 3y ago

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")?

jcranmer 3y ago
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.
- nyanpasu64 3y ago
  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?
  - jcranmer 3y ago
    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.
- cmrdporcupine 3y ago
  Did you get a look at https://github.com/rust-lang/rfcs/pull/3446 https://github.com/rust-lang/rfcs/pull/3446 at all?
  - jcranmer 3y ago
    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.