Whether/how to support TryFromBytes on unions?

[joshlf]

The bit validity of union types is currently up in the air. Since we currently support unions in our derive of FromZeros, and since we want to eventually make TryFromBytes a super-trait of FromZeros, we need some way of supporting unions in TryFromBytes. How do we do it?

[jswrenn]

Although the exact validity invariant of unions is under debate, I believe we can make useful progress on this.

Trait Bounds

First, let's consider the requirements of FromZeros. To be a supertrait of FromZeros, our derive of TryFromBytes will need to be derivable on all types that FromZeros is derivable for. A union is FromZeros if all of its variants are FromZeros. Consequently, a union is TryFromBytes if all of its variants are TryFromBytes.

Given this, how do we make our generated implementations of TryFromBytes::is_bit_valid sound?

Implementing TryFromBytes::is_bit_valid

It's trivial to soundly (but incompletely) implement of TryFromBytes::is_bit_valid: always return false. Such an implementation would not be particularly useful, and it would have some odd properties. For instance, one could do FromZeroes::new_zeroed() but not TryFromBytes::try_from_ref(&[0, 0, 0, 0...]).

Under any sound-but-incomplete implementation of is_bit_valid, such odd cases must exist. This is not unsound. (That said, we will need to be mindful not to implement sub-trait routines in terms of TryFromBytes::try_from_ref, or else we will introduce runtime regressions.)

Improving Completeness: Conjunctive Validity

From safe code, we can conclude that a union's validity includes bits valid for all of its fields; e.g.:

#[repr(C)]
union Simple {
    f1: u8,
    f2: i8,
}

let mut u = Simple { f1: 42 };
u.f2 = -42;

Any byte that is a valid u8 and i8 will also be a valid Simple.

Using this, we can soundly implement a more expressive is_bit_valid: the bytes are a valid instance of Self, if they are a valid instance of all variants.

Improving Completeness: Disjunctive Validity

From safe code, we can conclude that a union's validity includes bits valid for any of its fields; e.g.:

#[repr(C)]
union Different {
    f1: u8,
    f2: bool,
}

let mut u = Simple { f1: 1 };
u.f2 = 0 as bool;

Any byte that is a valid u8 and bool (i.e., the values 0 or 1) will also be a valid Different.

Using this, we can soundly implement a more expressive is_bit_valid: the bytes are a valid instance of Self, if they are a valid instance of any variant.

Improving Completeness: Torn Validity

From safe code, we can even observe that it's possible to construct a valid union whose value isn't valid for any whole field, but rather a mix:

union Mix {
  f1: (bool, u8),
  f2: (u8, bool),
}

let mut u = Mix { f1: (true, 99) };
u.f2.0 = 99;

I don't think our expansion of is_bit_valid can support such cases without also inspecting the internal structure of each field.

Conclusion

Our derive for TryFromBytes should require a TryFromBytes bound on each unit variant type. The expansion of is_bit_valid should check that there exists a field for which the candidate bytes are valid (i.e., "Disjunctive Validity").

This will lead to some weird edge cases. For instance, it could be possible to take a Mix, convert it to bytes via AsBytes, and then fail to TryFromBytes::try_from_ref those bytes. Again, we will need to be careful in FromBytes's and FromZeros's methods that we do not rely on TryFromBytes::try_from_ref being complete.

[jswrenn]

Actually implementing the above strategy, we run into some issues with our definition of TryFromBytes:

pub type Maybe<'a, T, Alignment = invariant::AnyAlignment> =
    Ptr<'a, T, (invariant::Shared, Alignment, invariant::AsInitialized)>;

trait TryFromBytes {
    fn is_bit_valid(candidate: Maybe<Self>) -> bool;

    // casts `candidate` to `Maybe<Self>` and delegates to `is_bit_valid`
    fn try_from_ref(candidate: &[u8]) -> Option<&Self>;
}

This definition is fine for structs, but problematic for unions. Imagine we have a union U, defined like so:

union U {
    a: (u16, bool), // [IIIU]
    b: (bool, u16), // [IUII]
}

Since Maybe<U> has validity AsInitialized, its referent may — as far as is_bit_valid is concerned — have any of the following patterns of (un)initialized bytes:

• [IIII]
• [IIIU]
• [IUII]

However, if we project U::a, an AsInitialized bound on the resulting projection demands that the referent have an (un)initialization of either:

• [IIII]
• [IIIU]

But this is untrue: the referent could have the (un)initialization pattern of U::b; i.e., [IUII]! If we were to call is_bit_valid on such a projection, we might read uninitialized memory as if it were initialized.

Solutions

Only provide try_from_ref, or change argument type of is_bit_valid to &[u8]

This problem does not exist in the composition of try_from_ref and is_bit_valid. Since try_from_ref takes only a slice of initialized bytes, there is no danger of its invocation of is_bit_valid reading uninitialized memory as if it were initialized. Do we even need Ptr in this case?

Make is_bit_valid unsafe

We could make is_bit_valid unsafe, and add the safety precondition that its argument is completely initialized. Doing so would negate some of the benefits of the invariant-paramterized Ptr introduced in #715.

Add an Initialized validity invariant to Ptr

We could add an Initialized validity invariant to Ptr. Again, this option retains Ptr as our safety boundary but underutilizes the flexibility we thought we needed from Ptr. What's the role of AsInitialized?

Initialize uninitialized bytes

We could, perhaps, sanitize the referent of Maybe<U> by initializing its uninitialized bytes. That is not a solution in this particular scenario, because Maybe<Self> is shared-aliased and cannot be freely mutated.

[jswrenn]

If unions are implicitly maybe-uninitialized, our job here gets distinctly easier: is_bit_valid can simply always return true.