Revise Safety Analysis

[jswrenn]

This issue tracks the design work to revise and simplify BikeshedIntrinsicFrom's safety analysis.

Background

Safe transmutation requires reasoning about whether transmuted fields carry safety invariants. A safe transmutation between two value types is only safe if the destination type does not maintain safety invariants on its fields. A safe transmutation between two mutable reference types requires that both that the source and destination are free of invariants.

Status Quo

At present, BikeshedIntrinsicFrom uses a visibility-based analysis to determine safety: the trait takes a Context type parameter which represents the location at which the transmutation is occurring. This design is described in-depth by MCP411 and summarized below.

When analyzing the safety of a transmutation, the compiler pretends it is sitting at the definition location of the type provided for Context, and checks that the Dst (and, if necessary, Src) type is fully implicitly constructible (i.e., you can recursively call the implicit constructors of its fields and those field's fields, and so on, to construct the Dst). If this check passes, then the transmute isn't constructing Dst in a way that couldn't be achieved without safe code.

Motivation

The visibility-based analyses has several drawbacks.

Drawback 1: Limited Utility

In general, it is not true that the ability to safely modify or construct a field means that it is free of safety invariants. Since Rust does not presently have a notion of unsafe fields, all fields are safely constructible and mutable in their defining context. See The Scope of Unsafe for additional information about this problem.

Drawback 2: Difficulty of Sound Implementation

A visibility-based analysis is difficult to implement completely. The implicit constructibility of a field does not depend only on its type's visibility and implicit constructibility of its fields, but also the visibility of the modules that the type is defined in. The "pub-in-priv trick" complicates this analysis from "inspecting type definitions" to "thoroughly exploring the reachability of fields in the module graph".

Proposal

We will remove the visibility based analysis. The Context parameter will be removed from BikeshedIntrinsicFrom, simplifying its definition to:

pub unsafe trait BikeshedIntrinsicFrom<Src, const ASSUME: Assume>
where
    Src: ?Sized
{}

#[derive(PartialEq, Eq, Clone, Copy)]
#[non_exhaustive]
pub struct Assume {
    /// The transmutability analysis unsafely assumes that *you* have
    /// ensured that the destination's alignment requirements are
    /// satisfied.
    pub alignment: bool,
    /// The transmutability analysis unsafely assumes that *you* have
    /// ensured that all lifetime constraints are respected.
    pub lifetimes: bool,
    /// The transmutability analysis unsafely assumes that *you* have
    /// ensured that no validity invariants are violated.
    pub validity: bool,
    /// The transmutability analysis unsafely assumes that *you* have
    /// ensured that no safety invariants are violated.
    pub safety: bool,
}

Implementations of BikeshedIntriniscFrom without the assumption of safety will only be emitted if fields constructed or rendered mutable by the transmutation are free from safety invariants. The set of such types $T$ that are free of safety invariants shall be defined as:

$$\begin{align} T = & \, \texttt{bool}\\\ | & \, \texttt{char}\\\ | & \, \texttt{f32}\\\ | & \, \texttt{f64}\\\ | & \, \texttt{i8}\\\ | & \, \texttt{i16}\\\ | & \, \texttt{i32}\\\ | & \, \texttt{i64}\\\ | & \, \texttt{i128}\\\ | & \, \texttt{isize}\\\ | & \, \texttt{u8}\\\ | & \, \texttt{u16}\\\ | & \, \texttt{u32}\\\ | & \, \texttt{u64}\\\ | & \, \texttt{u128}\\\ | & \, \texttt{usize}\\\ | & \, \texttt{()}\\\ | & \, \texttt{[}T\texttt{; N]}\\\ | & \, \texttt{(}T\texttt{,}...\texttt{)}\\\ | & \, \texttt{\&}T\\\ | & \, \texttt{\&mut }T\\\ \end{align}$$

Practically speaking, this means that Src: BikeshedIntriniscFrom<Dst, Assume::NOTHING> for all primitive Src and Dst (provided that validity requirements are fulfilled); e.g., u8: BikeshedIntriniscFrom<i8, Assume::NOTHING>.

Since Rust does not currently have any way for users to denote that their fields carry safety invariants, Assume::SAFETY will be required for most analyses of user-defined types. If Rust gains (un)safe fields in the future, our safety analysis can be updated to incorporate that information.

This design has several advantages:

1. It mostly eliminates the safety foot-gun caused by the lack of unsafe fields.
2. It is forwards-compatible with the addition of unsafe fields.
3. It is much simpler to use correctly.
4. It is much simpler to implement correctly.

Implementation

This section is a note to myself. Feel free to stop reading here!

Status Quo

The transmutability analysis represents types, first, as a Tree of definition elements:

/// A tree-based representation of a type layout.
///
/// Invariants:
/// 1. All paths through the layout have the same length (in bytes).
///
/// Nice-to-haves:
/// 1. An `Alt` is never directly nested beneath another `Alt`.
/// 2. A `Seq` is never directly nested beneath another `Seq`.
/// 3. `Seq`s and `Alt`s with a single member do not exist.
#[derive(Clone, Debug, Hash, PartialEq, Eq)]
pub(crate) enum Tree<D, R>
where
    D: Def,
    R: Ref,
{
    /// A sequence of successive layouts.
    Seq(Vec<Self>),
    /// A choice between alternative layouts.
    Alt(Vec<Self>),
    /// A definition node.
    Def(D),
    /// A reference node.
    Ref(R),
    /// A byte node.
    Byte(Byte),
}

The visibility analysis centers on Def nodes, which represent the definitions of types and fields. The accessibility of these definitions from the Scope parameter type can be queried from the QueryContext:

/// Context necessary to answer the question "Are these types transmutable?".
pub(crate) trait QueryContext {
    type Def: layout::Def;
    type Ref: layout::Ref;
    type Scope: Copy;

    /// Is `def` accessible from the defining module of `scope`?
    fn is_accessible_from(&self, def: Self::Def, scope: Self::Scope) -> bool;

    /* other methods */
}

The visibility analysis over these Trees is the first stage of analyzing transmutability:

impl<C> MaybeTransmutableQuery<Tree<<C as QueryContext>::Def, <C as QueryContext>::Ref>, C>
where
    C: QueryContext,
{
    /// Answers whether a `Tree` is transmutable into another `Tree`.
    ///
    /// This method begins by de-def'ing `src` and `dst`, and prunes private paths from `dst`,
    /// then converts `src` and `dst` to `Nfa`s, and computes an answer using those NFAs.
    #[inline(always)]
    #[instrument(level = "debug", skip(self), fields(src = ?self.src, dst = ?self.dst))]
    pub(crate) fn answer(self) -> Answer<<C as QueryContext>::Ref> {
        let assume_visibility = self.assume.safety;

        let Self { src, dst, scope, assume, context } = self;

        // Remove all `Def` nodes from `src`, without checking their visibility.
        let src = src.prune(&|def| true);

        trace!(?src, "pruned src");

        // Remove all `Def` nodes from `dst`, additionally...
        let dst = if assume_visibility {
            // ...if visibility is assumed, don't check their visibility.
            dst.prune(&|def| true)
        } else {
            // ...otherwise, prune away all unreachable paths through the `Dst` layout.
            dst.prune(&|def| context.is_accessible_from(def, scope))
        };

        trace!(?dst, "pruned dst");

        // Convert `src` from a tree-based representation to an NFA-based representation.
        // If the conversion fails because `src` is uninhabited, conclude that the transmutation
        // is acceptable, because instances of the `src` type do not exist.
        let src = match Nfa::from_tree(src) {
            Ok(src) => src,
            Err(Uninhabited) => return Answer::Yes,
        };

        // Convert `dst` from a tree-based representation to an NFA-based representation.
        // If the conversion fails because `src` is uninhabited, conclude that the transmutation
        // is unacceptable, because instances of the `dst` type do not exist.
        let dst = match Nfa::from_tree(dst) {
            Ok(dst) => dst,
            Err(Uninhabited) => return Answer::No(Reason::DstIsPrivate),
        };

        MaybeTransmutableQuery { src, dst, scope, assume, context }.answer()
    }
}

In the above routine, inaccessible branches of the layout tree are pruned from the destination type. If the remaining tree is uninhabited (either because it started as uninhabited or because it has no visible branches), we reject the transmutation.

Revised Implementation

Roughly speaking, the revised implementation is almost entirely the same, but with a few tweaks:

• The Scope/Context parameter is eliminated from the public API and the analysis
• On compound types, Def nodes are only emitted for fields
• Def is modified to carry a has_safety_invariants flag
  • For the fields of compound types, this flag is true
  • For primitive types, this flag is false