Re:The Rustonomicon: The Dark Arts of Advanced and Unsafe Rust
by Animats on Friday September 18, 2015 @02:41AM
(#10237791)
Interesting. Other than interfaces to non-Rust code, the big safety issues revolve around partial allocation of arrays. That's the machinery underneath the ability to grow a vector, and comes up with some other data structures.
It's not that hard to formalize safety in that area. You need some way to talk about an array being partially initialized. This requires some simple design-by-contract machinery - object invariants, basically. With some proof machinery, it should be possible to determine at compile time that a data manipulation is safe.
Rust already has the concept of raw memory space, which is treated as write-only. That takes care of initialization for non-array types. Partially initialized arrays require some additional annotation.
Suppose we have a primitive for talking about initialization:
isvalid(T, arr, lo, hi)
This means that array arr consists of valid values of type T is initialized and valid for subscripts in the range lo to hi inclusive.
Now there's a way to talk about partially initialized arrays:
This says that the array is only initialized up to len-1. The current requirement for "unsafe" comes from the lack of any way to talk about partial initialization. It's an expressive problem. Much of Rust's success comes from finding ways to talk about safety issues such as ownership within the language. This is an extension to that.
Then, a minimal theorem prover is needed, one which at least knows these theorems:
j < i ==> isvalid(T, a, i, j) // the null case
isvalid(T, a, i, j) and k >= i and k <= j ==> isvalid(T, a[k]) // element valid in range
isvalid(T, a, i, j) and isvalid(T, a[j+1]) ==> isvalid(T, a, i, j+1) // extend by adding new valid element
With that info, it's possible to check operations such as push, pop, and array growth, where an array is partially initialized in a controlled way. Array references can also be checked; this implies that access to an element index >= len is an error, and the compiler now knows this.
When the compiler knows something like that, it can optimize. If you're iterating a vec, from 0 to len-1, the subscript check required is
i < len
Within a FOR statement, the compiler already knows the range of i is within 0..len-1,
so the subscript check becomes
len-1 < len
which simplifies to True, eliminating the subscript check. That gets rid of the need for most unchecked subscripting.
This sort of proof machinery used to be exotic technology. (I was doing this kind of thing 35 years ago.[1]) Now it's well understood. It's quite possible to do this in a compiler today.
It's not that hard to formalize safety in that area. You need some way to talk about an array being partially initialized. This requires some simple design-by-contract machinery - object invariants, basically. With some proof machinery, it should be possible to determine at compile time that a data manipulation is safe.
Rust already has the concept of raw memory space, which is treated as write-only. That takes care of initialization for non-array types. Partially initialized arrays require some additional annotation.
Suppose we have a primitive for talking about initialization:
This means that array arr consists of valid values of type T is initialized and valid for subscripts in the range lo to hi inclusive.Now there's a way to talk about partially initialized arrays:
This says that the array is only initialized up to len-1. The current requirement for "unsafe" comes from the lack of any way to talk about partial initialization. It's an expressive problem. Much of Rust's success comes from finding ways to talk about safety issues such as ownership within the language. This is an extension to that.Then, a minimal theorem prover is needed, one which at least knows these theorems:
With that info, it's possible to check operations such as push, pop, and array growth, where an array is partially initialized in a controlled way. Array references can also be checked; this implies that access to an element index >= len is an error, and the compiler now knows this.When the compiler knows something like that, it can optimize. If you're iterating a vec, from 0 to len-1, the subscript check required is
Within a FOR statement, the compiler already knows the range of i is within 0..len-1, so the subscript check becomes which simplifies to True, eliminating the subscript check. That gets rid of the need for most unchecked subscripting.This sort of proof machinery used to be exotic technology. (I was doing this kind of thing 35 years ago.[1]) Now it's well understood. It's quite possible to do this in a compiler today.
[1] http://www.animats.com/papers/verifier/verifiermanual.pdf