# Types as Contracts: Implementation and Evaluation

**URL:** <https://internals.rust-lang.org/t/types-as-contracts-implementation-and-evaluation/5753>\
**Category:** Unsafe Code Guidelines\
**Created:** [August 11, 2017, 11:03pm UTC](https://internals.rust-lang.org/t/types-as-contracts-implementation-and-evaluation/5753 "2017-08-11T23:03:49Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![RalfJung](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/ralfjung/32/2415_2.png) [@RalfJung](https://internals.rust-lang.org/u/RalfJung)\
**Post date:** [August 11, 2017, 11:03pm UTC](https://internals.rust-lang.org/t/types-as-contracts-implementation-and-evaluation/5753/1 "2017-08-11T23:03:50Z")

</div>

Some weeks ago, I described [Types as Contracts](https://internals.rust-lang.org/t/types-as-contracts/5562) as an approach for how to go about defining Rust’s aliasing-related [undefined behavior](https://www.ralfj.de/blog/2017/07/14/undefined-behavior.html). One key property of this approach is that it is executable, which means we can actually have a program (in this case, [miri](https://github.com/solson/miri/)) tell us whether some particular Rust test case exhibits undefined behavior or not. I have since then spent most of my time completing and refining this implementation, and running it on miri’s test suite to exercise various bits of the standard library and see whether they are actually following the rules I have been suggesting.

This post is my report on what I found, and how the approach itself changed in response to these findings. It also explains how you can run miri yourself and have it check your code for undefined behavior according to this model. Finally, I discuss some of the things that I would like to look at going forward.

[https://www.ralfj.de/blog/2017/08/11/types-as-contracts-evaluation.html](https://www.ralfj.de/blog/2017/08/11/types-as-contracts-evaluation.html)

---

<div class="post-metadata">

**Author:** ![Ixrec](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/ixrec/32/6754_2.png) [@Ixrec](https://internals.rust-lang.org/u/Ixrec)\
**Post date:** [August 12, 2017, 12:05am UTC](https://internals.rust-lang.org/t/types-as-contracts-implementation-and-evaluation/5753/2 "2017-08-12T00:05:27Z")

</div>

Regarding the Arc::drop case, would it be legal in your model if the `self.inner().weak` was replaced by some unsafe pointer arithmetic that fetched the `weak` field without any intermediate partially invalid `ArcInner` value? (i.e., would removing the type also “remove the contract” that’s being violated?)

---

<div class="post-metadata">

**Author:** ![RalfJung](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/ralfjung/32/2415_2.png) [@RalfJung](https://internals.rust-lang.org/u/RalfJung)\
**Post date:** [August 12, 2017, 1:34am UTC](https://internals.rust-lang.org/t/types-as-contracts-implementation-and-evaluation/5753/3 "2017-08-12T01:34:06Z")

</div>

> [@Ixrec](#):
>
> Regarding the Arc::drop case, would it be legal in your model if the self.inner().weak was replaced by some unsafe pointer arithmetic that fetched the weak field without any intermediate partially invalid ArcInner value? (i.e., would removing the type also “remove the contract” that’s being violated?)

Yes. Notice however that the call to `Layout::for_value` would still be UB and also needs to be fixed. Also, there is no need for literally using pointer arithmetic. I think the following should work (and I should really test that...):

```rust
    unsafe fn drop_slow(&mut self) {
        let old_weak = self.inner().weak.fetch_sub(1, Release);

        let ptr = self.ptr.as_ptr();
        let layout = Layout::for_value(&*ptr);

        // Destroy the data at this time, even though we may not free the box
        // allocation itself (there may still be weak pointers lying around).
        ptr::drop_in_place(&mut self.ptr.as_mut().data);

        if old_weak == 1 {
            atomic::fence(Acquire);
            Heap.dealloc(ptr as *mut u8, layout)
        }
    }

```

Note that this computes the layout even when that is not needed. But we are talking about a one-time cost per `Arc`, this is probably not significant (and would be fixed at the expense of some code duplication).

I _think_ reordering the `fetch_sub` up to the beginning of the function is okay, but if it is not, this should also work:

```rust
    unsafe fn drop_slow(&mut self) {
        let ptr = self.ptr.as_ptr();

        let layout = Layout::for_value(&*ptr);

        // Destroy the data at this time, even though we may not free the box
        // allocation itself (there may still be weak pointers lying around).
        ptr::drop_in_place(&mut (*ptr).data);
        // We must not use the type &(mut) ArcInner from now on, because that
        // type is actually no longer valid.

        if (*ptr).weak.fetch_sub(1, Release) == 1 {
            atomic::fence(Acquire);
            Heap.dealloc(ptr as *mut u8, layout)
        }
    }

```

I actually think not obtaining a pointer to the inner part three times makes the code overall more readable.

---

<div class="post-metadata">

**Author:** ![RalfJung](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/ralfjung/32/2415_2.png) [@RalfJung](https://internals.rust-lang.org/u/RalfJung)\
**Post date:** [August 12, 2017, 2:22am UTC](https://internals.rust-lang.org/t/types-as-contracts-implementation-and-evaluation/5753/4 "2017-08-12T02:22:44Z")

</div>

I confirmed that the second version I presented above (now also shown in the post itself) indeed makes validation go through just fine – of course, this makes use of the “validation is relaxed around unsafe blocks” mode.

---

<div class="post-metadata">

**Author:** ![RalfJung](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/ralfjung/32/2415_2.png) [@RalfJung](https://internals.rust-lang.org/u/RalfJung)\
**Post date:** [September 15, 2017, 10:55am UTC](https://internals.rust-lang.org/t/types-as-contracts-implementation-and-evaluation/5753/5 "2017-09-15T10:55:07Z")

</div>

Status update: I finally got around to [implement a fix](https://github.com/solson/miri/pull/336) for the problem with suspended write locks hat I have been alluding to earlier. This made a bunch of additional test cases work in miri. Also, there’s an [RFC on the way](https://github.com/rust-lang/rfcs/pull/1892) that will fix the problems I have been having around `mem::uninitialized`.

The only unexpected failure currently is that tests that panic trigger a validation error; I still have to investigate that problem.

---

<div class="post-metadata">

**Author:** ![RalfJung](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/ralfjung/32/2415_2.png) [@RalfJung](https://internals.rust-lang.org/u/RalfJung)\
**Post date:** [September 16, 2017, 10:05am UTC](https://internals.rust-lang.org/t/types-as-contracts-implementation-and-evaluation/5753/6 "2017-09-16T10:05:18Z")

</div>

In implementing more validation for miri (namely, ruling out uninitialized data to be passed around at types like `u8`), I found at least one other contract violation in the standard library. `Vec::extend` can end up running the following code:

```rust
    fn spec_extend(&mut self, iterator: slice::Iter<'a, T>) {
        let slice = iterator.as_slice();
        self.reserve(slice.len());
        unsafe {
            let len = self.len();
            self.set_len(len + slice.len());
            self.get_unchecked_mut(len..).copy_from_slice(slice); // <-
        }
    }

```

The interesting line here is the `get_unchecked_mut`, which creates a slice covering uninitialized data. So this ends up calling `copy_from_slice` (a safe, public function) with a `self` argument that is _not_ a valid reference to initialized data. `T` here can be arbitrary. Imagine `T` being an `enum`, then this would pass around (references to) data with an uninitialized discriminant.

None of the exceptions (concerning unsafe code, or private fields) that have been suggested so far would make this legal, nor does there seem to be a good way to fix this locally.

---

<div class="post-metadata">

**Author:** ![ahmedcharles](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/ahmedcharles/32/4041_2.png) [@ahmedcharles](https://internals.rust-lang.org/u/ahmedcharles)\
**Post date:** [September 19, 2017, 4:21am UTC](https://internals.rust-lang.org/t/types-as-contracts-implementation-and-evaluation/5753/7 "2017-09-19T04:21:49Z")

</div>

It seems that you would want to have a function in `std::slice`, such as `uninitialized_copy_from_slice`:

```rust
pub unsafe fn uninitialized_copy_from_slice<'a, T>(p: *const T, len: usize, src: &[T]) -> &'a [T] {
    assert!(len == src.len(),
                "destination and source slices have different lengths");
    ptr::copy_nonoverlapping(src.as_ptr(), p, len);
    from_raw_parts(p, len)
}

```

This would then allow:

```rust
    fn spec_extend(&mut self, iterator: slice::Iter<'a, T>) {
        let slice = iterator.as_slice();
        self.reserve(slice.len());
        let len = self.len();
        unsafe {
            uninitialized_copy_from_slice(self.as_mut_ptr().offset(len as isize), slice.len(), slice);
            self.set_len(len + slice.len());
        }
    }

```

This actually does the same operations as it does currently but without ever forming a slice with uninitialized data. Note, setting the length after the data is initialized prevents the Vec from perceiving itself as having uninitialized data as well.

---

<div class="post-metadata">

**Author:** ![RalfJung](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/ralfjung/32/2415_2.png) [@RalfJung](https://internals.rust-lang.org/u/RalfJung)\
**Post date:** [September 19, 2017, 9:06am UTC](https://internals.rust-lang.org/t/types-as-contracts-implementation-and-evaluation/5753/8 "2017-09-19T09:06:59Z")

</div>

@ahmedcharles There is no need for `uninitialized_copy_from_slice` to return anything then, and indeed `spec_extend` could just as well call `copy_nonoverlapping` directly. So it seems I was wrong, there _is_ a good way to fix this locally. That’s great.

However, the really interesting question is: We now have at least two cases where programmers considered it fine to pass around uninitialized data behind a reference type, given that they knew that the code that is called here is actually able to cope with uninitialized data. IOW, the functions that were called `Layout::for_value` and `copy_from_slice` are “super-safe” in that they are safe to call with certain “bad” values. Given that, is it reasonable to eventually rule out this pattern in the future and always require uninitialized data to live behind a [`MaybeUninitialized`](https://github.com/rust-lang/rfcs/pull/1892) (or a raw pointer) when crossing function boundaries? Or will that break too much existing code?

---

<div class="post-metadata">

**Author:** ![arielb1](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/arielb1/32/3044_2.png) [@arielb1](https://internals.rust-lang.org/u/arielb1)\
**Post date:** [September 19, 2017, 9:11am UTC](https://internals.rust-lang.org/t/types-as-contracts-implementation-and-evaluation/5753/9 "2017-09-19T09:11:07Z")

</div>

> [@RalfJung](#):
>
> Given that, is it reasonable to eventually rule out this pattern in the future and always require uninitialized data to live behind a MaybeUninitialized (or a raw pointer) when crossing function boundaries? Or will that break too much existing code?

From my POV from unsafe code guidelines project: I made references to uninitialized data defined behavior because that seemed like a fairly popular pattern, and it didn't break the compiler as badly as directly uninitialized data. The compiler "crawling" through references deeply to cause UB seemed to be a very surprising behavior.

---

<div class="post-metadata">

**Author:** ![RalfJung](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/ralfjung/32/2415_2.png) [@RalfJung](https://internals.rust-lang.org/u/RalfJung)\
**Post date:** [September 19, 2017, 9:17am UTC](https://internals.rust-lang.org/t/types-as-contracts-implementation-and-evaluation/5753/10 "2017-09-19T09:17:15Z")

</div>

> I made references to uninitialized data defined behavior because that seemed like a fairly popular pattern, and it didn’t break the compiler as badly as directly uninitialized data. The compiler “crawling” through references deeply to cause UB seemed to be a very surprising behavior.

I can see that. For consistency, then, this shouldn't be restricted to uninitialized data -- passing a `&bool` to an out-of-range value, or an `&&i32` where the inner reference is 0, should also not be "insta-UB" when crossing function boundaries, but only become UB at some later stage after the reference has been dereferenced.

What exactly that later stage is I suppose remains open; this then becomes one of [these](https://github.com/nikomatsakis/rust-memory-model/issues/12) old [discussions](https://github.com/nikomatsakis/rust-memory-model/issues/2).

---

<div class="post-metadata">

**Author:** ![ahmedcharles](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/ahmedcharles/32/4041_2.png) [@ahmedcharles](https://internals.rust-lang.org/u/ahmedcharles)\
**Post date:** [September 19, 2017, 9:23am UTC](https://internals.rust-lang.org/t/types-as-contracts-implementation-and-evaluation/5753/11 "2017-09-19T09:23:26Z")

</div>

The point of suggesting `uninitialized_copy_from_slice` is to create helper functions for dealing with uninitialized data, much like similar functions in the C++ STL. The reason it returns a slice is because algorithms should return information rather than throw it away and this function knows that the slice is initialized, so it’s in the best position to call `from_raw_parts` correctly.

And my preference would be to explicitly treat uninitialized data and have functions which help with common ways of initializing that data. One of the things I like about Rust is that safe references are always valid. I wouldn’t want to lose that.

---

<div class="post-metadata">

**Author:** ![arielb1](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/arielb1/32/3044_2.png) [@arielb1](https://internals.rust-lang.org/u/arielb1)\
**Post date:** [September 19, 2017, 1:30pm UTC](https://internals.rust-lang.org/t/types-as-contracts-implementation-and-evaluation/5753/12 "2017-09-19T13:30:16Z")

</div>

> [@RalfJung](#):
>
> I can see that. For consistency, then, this shouldn’t be restricted to uninitialized data – passing a `&bool` to an out-of-range value, or an `&&i32` where the inner reference is 0, should also not be “insta-UB” when crossing function boundaries, but only become UB at some later stage after the reference has been dereferenced.

Right. Uninitialized data is just one kind of invalid data.

---

<div class="post-metadata">

**Author:** ![RalfJung](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/ralfjung/32/2415_2.png) [@RalfJung](https://internals.rust-lang.org/u/RalfJung)\
**Post date:** [September 19, 2017, 4:13pm UTC](https://internals.rust-lang.org/t/types-as-contracts-implementation-and-evaluation/5753/13 "2017-09-19T16:13:40Z")

</div>

> [@ahmedcharles](#):
>
> And my preference would be to explicitly treat uninitialized data and have functions which help with common ways of initializing that data. One of the things I like about Rust is that safe references are always valid. I wouldn’t want to lose that.

Well, I think we all want to uphold the rule that they are properly aligned and point to allocated storage. But there's a problem with enforcing things "behind the reference" to be initialized. After fixing `extend_with`, I now hit [`fmt::Display`](https://github.com/rust-lang/rust/blob/5d5dcae7f15850e7668a38e5da87cf6010e87eba/src/libcore/fmt/num.rs#L210):

```rust
            let mut buf: [u8; 39] = unsafe { mem::uninitialized() };
            let mut curr = buf.len() as isize;
            let buf_ptr = buf.as_mut_ptr();

```

The call to `len()` is fixed easy enough by using a `const LEN : usize = 39;`, but `buf_ptr` is... more interesting.

* * *

@arielb1: One problem with not going "below" references is the interaction with other guarantees, e.g. shared references being read-only. Consider a function like

```rust
fn foo(x: &Result<Cell<i32>, i32>) {
  // ...
}

```

(I am using `Result` here just as a general sum type.) Assuming a 4-byte discriminant, the question now is: Does `foo` have a "lock" on the memory range `[x+4, x+8[` or not? My model will just read the enum discriminant to determine whether the second half of `*x` is covered by an `UnsafeCell` or not. However, if we do not descend through references, then we cannot tell whether there is an `UnsafeCell` or not. What are your thoughts on this?

---

<div class="post-metadata">

**Author:** ![ahmedcharles](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/ahmedcharles/32/4041_2.png) [@ahmedcharles](https://internals.rust-lang.org/u/ahmedcharles)\
**Post date:** [September 19, 2017, 4:23pm UTC](https://internals.rust-lang.org/t/types-as-contracts-implementation-and-evaluation/5753/14 "2017-09-19T16:23:09Z")

</div>

Given that arrays are built in, it seems like the semantics of an uninitialized array should be that the content of the array is uninitialized but the address and length are valid (they can’t change anyways). So, why would the code, as written, be problematic? The uninitialized data doesn’t apply to the address or size of the array, only the data.

And what’s the problem with enforcing things behind a reference being valid? You can certainly check for it, even if it’s expensive. (On second thought, I see the point. In many cases you have to form a reference to something that’s uninitialized in order to initialize it. Though, that would only require `&mut`, since `&` alone can’t be used to initialize it. And obviously, arrays have to be special cased.)

---

<div class="post-metadata">

**Author:** ![ahmedcharles](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/ahmedcharles/32/4041_2.png) [@ahmedcharles](https://internals.rust-lang.org/u/ahmedcharles)\
**Post date:** [September 19, 2017, 4:59pm UTC](https://internals.rust-lang.org/t/types-as-contracts-implementation-and-evaluation/5753/15 "2017-09-19T16:59:45Z")

</div>

I’m beginning to realize that having write only references would be really nice. You could have functions like `fn reset(&write self)` which only write to the value. Obviously, some functions that do a ‘reset’ operation need to read and write, but then you could distinguish which ones require reading first. Note, you could have `&write` mean that any member needs to be written before being read, rather than requiring that it can only be written.

---

<div class="post-metadata">

**Author:** ![arielb1](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/arielb1/32/3044_2.png) [@arielb1](https://internals.rust-lang.org/u/arielb1)\
**Post date:** [September 19, 2017, 5:18pm UTC](https://internals.rust-lang.org/t/types-as-contracts-implementation-and-evaluation/5753/16 "2017-09-19T17:18:48Z")

</div>

> [@RalfJung](#):
>
> (I am using Result here just as a general sum type.) Assuming a 4-byte discriminant, the question now is: Does foo have a “lock” on the memory range [x+4, x+8[ or not? My model will just read the enum discriminant to determine whether the second half of \*x is covered by an UnsafeCell or not. However, if we do not descend through references, then we cannot tell whether there is an UnsafeCell or not. What are your thoughts on this?

The RMM model was "aliasing-based" - it only ever "locked" on an access, so it did not encounter that particular problem (as `UnsafeCell` is not `Copy`, not even when copying a complex structure).

However, I see why a validation-based model would encounter this problem. But it's the "reference to garbage" problem from before. Maybe it's interesting enough to lock down.

---

<div class="post-metadata">

**Author:** ![bluss](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/bluss/32/2264_2.png) [@bluss](https://internals.rust-lang.org/u/bluss)\
**Post date:** [September 19, 2017, 8:16pm UTC](https://internals.rust-lang.org/t/types-as-contracts-implementation-and-evaluation/5753/17 "2017-09-19T20:16:09Z")

</div>

Is the slice case different than the reference case? I thought there were quite a few “out of bounds” `.get_unchecked_mut(i)` for single indices `i` in the `Vec` code. There is for example one here, in a different extend function:

```rust
    fn extend_desugared<I: Iterator<Item = T>>(&mut self, mut iterator: I) {
        // This is the case for a general iterator.
        //
        // This function should be the moral equivalent of:
        //
        // for item in iterator {
        // self.push(item);
        // }
        while let Some(element) = iterator.next() {
            let len = self.len();
            if len == self.capacity() {
                let (lower, _) = iterator.size_hint();
                self.reserve(lower.saturating_add(1));
            }
            unsafe {
                ptr::write(self.get_unchecked_mut(len), element);
                // NB can't overflow since we would have had to alloc the address space
                self.set_len(len + 1);
            }
        }
    }

```

---

<div class="post-metadata">

**Author:** ![RalfJung](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/ralfjung/32/2415_2.png) [@RalfJung](https://internals.rust-lang.org/u/RalfJung)\
**Post date:** [September 25, 2017, 8:29am UTC](https://internals.rust-lang.org/t/types-as-contracts-implementation-and-evaluation/5753/18 "2017-09-25T08:29:46Z")

</div>

> [@ahmedcharles](#):
>
> why would the code, as written, be problematic?

For exactly the same reason that `extend_with` was problematic -- it passes `&T` to another function where `T` is not initialized. `len` and `as_mut_ptr` as both just methods that take `&self` and `&mut self` respectively.

> [@ahmedcharles](#):
>
> In many cases you have to form a reference to something that’s uninitialized in order to initialize it. Though, that would only require &mut, since & alone can’t be used to initialize it.

Ah, that's a good point. We could in principle require data behind `&` to be initialized and recursively follow shared references (which would also solve then`UnsafeCell` problem above), but permit uninitialized data behind `&mut` and only do shallow validation of mutable references.

However, that would probably we a fairly surprising asymmetry.

* * *

> [@arielb1](#):
>
> The RMM model was “aliasing-based” - it only ever “locked” on an access, so it did not encounter that particular problem

Right. However, I think it would be preferrable to hold locks even for un-accessed data, at least under some circumstances.

> [@arielb1](#):
>
> as UnsafeCell is not Copy, not even when copying a complex structure

However, it could well be `Copy`, and I think we should have a model compatible with that. There is no reason besides ergonomics for `Cell` not to be `Copy`.

* * *

> [@bluss](#):
>
> Is the slice case different than the reference case?

No, not fundamentally. It is just another example. Thanks for adding yet another one!

---

<div class="post-metadata">

**Author:** ![ahmedcharles](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/ahmedcharles/32/4041_2.png) [@ahmedcharles](https://internals.rust-lang.org/u/ahmedcharles)\
**Post date:** [September 28, 2017, 1:24am UTC](https://internals.rust-lang.org/t/types-as-contracts-implementation-and-evaluation/5753/19 "2017-09-28T01:24:24Z")

</div>

> [@RalfJung](#):
>
> For exactly the same reason that extend\_with was problematic – it passes &T to another function where T is not initialized. len and as\_mut\_ptr as both just methods that take &self and &mut self respectively.

That's my point, have the compiler treat `len` and `as_mut_ptr` on arrays as being special. No other type in the language has the same properties as arrays in this regard, by definition, so why wouldn't treating them specially be ok?

> [@RalfJung](#):
>
> However, that would probably we a fairly surprising asymmetry.

Reading from a `&mut` would still require a deep check. It's just that the check wouldn't happen at function boundaries, but instead, happen at the location of the read operation. Normal `&`'s can be checked at the function boundary. So, there isn't an asymmetry, they just get treated differently because they are different.

---

<div class="post-metadata">

**Author:** ![RalfJung](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/ralfjung/32/2415_2.png) [@RalfJung](https://internals.rust-lang.org/u/RalfJung)\
**Post date:** [September 29, 2017, 12:14pm UTC](https://internals.rust-lang.org/t/types-as-contracts-implementation-and-evaluation/5753/20 "2017-09-29T12:14:27Z")

</div>

> [@ahmedcharles](#):
>
> have the compiler treat len and as\_mut\_ptr on arrays as being special.

I don't think that's a good idea -- this looks fairly arbitrary to me. Many functions are fine to be called with some of their references being uninitialized, so I don't see these two as being special in any way.

[Next page](https://internals.rust-lang.org/t/types-as-contracts-implementation-and-evaluation/5753.md?page=2)
