Hi, Rust experts! I've been pondering a question for a long time: is the borrow checker the only solution for achieving "aliasing XOR mutation" ? After years of exploration, I personally feel there might be other solutions to this problem. All the thinkings result in an experimental language zinc-lang · GitHub . Let me explain my design, and I would appreciate it if the experts here could point out any aspects I might have overlooked or failed to consider correctly.
-
use RC to manage all heap memories
RC is very good at tracking aliasing, since it inherently keeps a record of aliasing count.
Zinc uses "Automatic Reference Counting", which means the compiler automatically choose atomic or non-atomic RC pointer according to pointee type. Thanks to thread-safety feature, the compiler knows whether a pointer can be transferred across thread boundaries, so it knows whether atomic ref-counting is needed. ARC is the most commonly used pointer type in Zinc language. So the simplest syntax is chosen for this type:
*T. -
borrow to heap objects should change the ref-count of the heap object
fn main() { let mut p1: *UInt = box 1_u; let b1 = &*p1; // b1 is pointing to a heap object, the ref-count of the object increases to 2. println(*b1); // prints 1 p1 = box 2_u; // p1 is pointing to a new object, the ref-count of the old object decreases to 1. println(*b1); // prints 1, because the old object is not freed. The borrow continues to be valid. println(*p1); // prints 2, because p1 is pointing to the new object. }This means borrow pointer will never become a dangling pointer. A heap object will not be freed when there is an aliasing pointing to it.
-
return fat borrow type when a borrow to heap object escapes outside a fn
Let's consider how to implement
fn indexofVec<T>type. Its return type is expected to be a&Ttype, which points to an item on the heap.// test case: fn main() { let mut vec = (type Vec<Int>)::from(&[1i,2i,3i,4i] as Slice<Int>); let p: &Int = vec.index(1); // we get a borrow pointing to heap object vec.push(5); // push might triger re-allocation println(*p); // how to ensure p is valid ? }Solution: the
fn indexshould return an user-defined-type instead of a borrow pointer. The user defined type contains a borrow pointer and a RC pointer both, which can be viewed as a "fat borrow pointer". And it can be implicitly deref to a borrow pointer.// explain: fn main() { let mut vec = (type Vec<Int>)::from(&[1i,2i,3i,4i] as Slice<Int>); let _temp: ItemRef<Int> = vec.index(1); // the index method actually returns a struct ItemRef, it is an invisible local variable let p: &Int = _temp.deref(); // the struct ItemRef can be implicitly deref to a borrow pointer by compiler vec.push(5); // Since ItemRef contains a RC to heap objects. So re-allocation will not cause old objects be freed println(*p); // p is always valid // when _temp is dropped, the old heap objects will be freed } -
use copy-on-write to implement value type collections
Copy-on-write is the key technique to achieve "aliasing xor mutation".
Take
Stringtype as an example. It is possible to implement a memory-safe and thread-safeStringtype without ownership and borrow-checker. It is implemented like this:- internal byte buffer is managed by ARC pointer
- methods with
&mut selfreceiver always check the ref-count before modification
We can ensure when mutation happens, there is always only one aliasing pointing to the byte buffer. It conforms "aliasing xor mutation" rule perfectly.
-
avoid invalid iteration
Without borrow checker, we can still avoid iterator invalidation issues during iteration.
fn main() { let mut vec = (type Vec<Int>)::from(&[1_i, 2_i, 3_i] as Slice<Int>); // The iterator increased the ref-count of underlying array buffer for i in vec { // when calling mutable methods of vec, it will copy its underlying array buffer to a new allocation, and then modify. // this behavior is called copy-on-write. // the old array buffer is still alive until the iterator is dropped. vec.push(4); println(i); } // After above for loop, the vec's value is updated to [1,2,3,4,4,4]. } -
what if a mut borrow is created, and then add immut aliasing later?
// test case: fn main() { let mut vec = (type Vec<Int>)::from(&[1i,2i,3i,4i] as Slice<Int>); let p: &mut Int = vec.index_mut(1); // we get a mut borrow pointing to heap object let vec2 = vec; // shallow copy of vec *p += 1; // Will this modification affect vec2? Is there a data race if vec2 is send to another thread? }The answer is that this case will panic when copying the vec. The
index_mutmethod will do a copy-on-write first and then set the ref-count to MAX. So increasing ref-count will cause integer overflow panic if the mut borrow is alive. This is basically the same logic as that ofRefCell. -
borrow to enum payload
fn test(o: &Option<Int>) { if o is Some(ref p) { f(); println(*p); // how can we ensure p is valid? } }For this case, I don't have a good idea to solve it. For now, I just simply disallow borrow pointers pointing to enum payload. It should be improved later.
-
thread safety
Similar with Rust, thread-safety is maintained by
Send&Synctraits in Zinc.struct S {} impl !Send for S {} static G: S = {...}:S; // error. `S` is not Send type // ok. `&AtomicUInt` is Send type static M: &'static AtomicUInt = &AtomicUInt::new(0);Note: there is a difference between Rust and Zinc that, Rust requires
Syncconstraints for globals, whereas Zinc requiresSendconstraints for globals.Below types conform
Sendtrait, and can be safely transferred across threads:- "value semantic" types
- "reference semantic" types which points to synchronized types
fn send<T>(x: T) where T: Send {} fn main() { let mut vec1: Vec<Int> = Vec::new(); let mut vec2: Vec<*Int> = Vec::new(); send(move vec1); // ok. `Vec<Int>` is Send type. send(move vec2); // error. `Vec<*Int>` is not Send type }
Back to the original question at the begining, is my design a correct solution to "aliasing xor mutation"? I'm not sure. And I'm eager to hear your opinions. Thank you very much!
