Dyn upcasting coercion initiative

What is this?

This page tracks the work of the dyn upcasting coercion initiative! To learn more about what we are trying to do, and to find out the people who are doing it, take a look at the charter.

Current status

The following table lists of the stages of an initiative, along with links to the artifacts that will be produced during that stage.

Key:

• ✅ -- phase complete
• 🦀 -- phase in progress
• 💤 -- phase not started yet

How Can I Get Involved?

• Check for 'help wanted' issues on this repository!
• If you would like to help with development, please contact the owner to find out if there are things that need doing.
• If you would like to help with the design, check the list of active design discussions first.
• If you have questions about the design, you can file an issue, but be sure to check the FAQ or the design-discussions first to see if there is already something that covers your topic.
• If you are using the feature and would like to provide feedback about your experiences, please [open a "experience report" issue].
• If you are using the feature and would like to report a bug, please open a regular issue.

We also participate on Zulip, feel free to introduce yourself over there and ask us any questions you have.

Building Documentation

This repository is also an mdbook project. You can view and build it using the following command.

mdbook serve

✏️ Updates

Lang-team initiatives give monthly updates. This section collects the updates from this initiative for posterity.

2021-Oct: Lang team update

Summary

• Impl is largely ready
• Blocked on deciding the question of upcast safety

Goals for this month

• Hold design meeting about upcast safety and reach a conclusion

Deref coercion

It was discovered in #89190 that extending "unsizing coercions" to include upcasts can cause deref coercions not to trigger, if those deref coercions "deref" to a dyn type. Current plan is to issue future compatibility warnings in #89461, since the only known use of this is emulating the upcasting coercion (and hence the code will continue to work afterwards, but the Deref impl is not invoked).

Dyn upcast Charter

Goals

Summary and problem statement

• Add the trait_upcasting feature to the language.

Motivation, use-cases, and solution sketches

• The trait_upcasting feature adds support for trait upcasting coercion. This allows a trait object of type dyn Bar to be cast to a trait object of type dyn Foo so long as Bar: Foo.

#![allow(unused)]
#![feature(trait_upcasting)]

fn main() {
trait Foo {}

trait Bar: Foo {}

impl Foo for i32 {}

impl<T: Foo + ?Sized> Bar for T {}

let bar: &dyn Bar = &123;
let foo: &dyn Foo = bar;
}

Non-goals

• To support dyn Trait1 + Trait2 for general traits (this syntax naturally works, and should continue to work, with auto traits).

Membership

📚 Explainer

The "explainer" is "end-user readable" documentation that explains how to use the feature being deveoped by this initiative. If you want to experiment with the feature, you've come to the right place. Until the feature enters "feature complete" form, the explainer should be considered a work-in-progress.

Design questions

Catalogs various interesting design questions that have arisen.

What qualitifies as a dyn upcasting coercion

The condition comes from the existing infrastructure within the compiler.

Currently the unsizing coercion on a trait object type allows it to:

1. Removing one or more auto traits. (i.e. dyn Foo + Send: Unsize<dyn Foo>)

2. Changing lifetime bounds according to subtyping rules. (dyn Bar<'static>: Unsize<dyn Bar<'a>>)

3. Changing the principal trait to one of its supertraits. (dyn Goo: Unsize<dyn Foo> where Goo is trait Goo: Foo {})

When the third rule is involved, this unsizing coercion is a dyn upcasting coercion.

Dyn upcast safety

This document proposes a resolution to the last outstanding question blocking dyn upcast.

Tracking issue: https://github.com/rust-lang/rust/issues/101336

Background

We are trying to enable "upcasts" from a dyn Trait to its supertraits:

#![allow(unused)]
fn main() {
trait Foo {
    fn foo_method(&self);
}
trait Bar: Foo {
    fn bar_method(&self);
}

let x: &dyn Bar = /* ... */;
let y: &dyn Foo = x; // compiles
}

The key factor for these upcasts is that they require adjusting the vtable. The current implementation strategy is that the vtables for the Bar trait embed pointers to a Foo vtable within them:

+----------------------------+
| Bar vtable for some type T |
|----------------------------|
| Foo vtable                 | ----------> +------------------+
| foo_method                 | -----+      | Foo vtable for T |
| bar_method                 | --+  |      |------------------|
+----------------------------+   |  |      | foo_method       | ---+
                                 |  |      +------------------+    |
                                 |  |                              |
                                 |  +---> <T as Foo>::foo_method <-+
                                 v
                     <T as Bar>::bar_method
                 
(this diagram is only meant to convey the general idea of the vtable
 layout, and doesn't represent the exact offsets we would use etc;
 in fact, with the current implementation,
 the first supertrait is stored 'inline' and hence no load is required)

This way, given a &dyn Bar object, we convert its Bar vtable to the appropriate Foo vtable by loading the appropriate field.

Although we don't want to commit to a particular implementation strategy, we do want to leave room for this strategy. One implication is that performing an upcast may require loading from the vtable, which implies that the vtable must be a valid pointer to an actual Rust vtable. Although &dyn Bar references would always contain a valid vtable, the same is not necessarily true for a raw pointer like *const dyn Bar or *mut dyn Bar.

In the language today, we only support "noop upcasts" that don't affect the vtable, and these are safe (e.g., converting from *const dyn Foo + Send to *const dyn Foo). If we extend the set of upcasts to permit vtable-adjusting upcasts, like *const dyn Bar to *const dyn Foo, this implies that, for safe code at least, all *const dyn Trait values must have a valid vtable, so that we know we can safely load the required field and perform the upcast.

On the other hand, we do not generally require raw *mut T pointers to point to valid data. In fact, we explicitly permit them to have any value, including null, and only require that they point to valid data when they are dereferenced. Because dereferencing a raw pointer is an unsafe operation, it has always been considered safe to expose an arbitrary raw pointer to unsafe code -- the unsafety arises when you take a raw pointer from an unknown source and dereference it, since unless you can trace the origin of that pointer you can't possible guarantee that it is valid to dereference.

This brings us to the conflict:

• It has historically been safe to "release" a raw pointer to safe code, but not safe to receive one (since you cannot know if it is valid).
• It has historically been safe to upcast *const dyn values (e.g., *const dyn Foo + Send to *const dyn Foo).
  • Unlike the upcasts we are considering now, this upcast does not require changing the vtable at runtime, but the distinction is subtle for end-users.
  • Moreover, there are future extensions (e.g., upcasting *const dyn Foo + Bar to *const dyn Foo) that would require adjusting the vtable much like the upcasts currently being stabilized.

Related future consideration: virtual method calls on raw pointers

There have been requests to extend traits with the option to include raw pointer methods:

#![allow(unused)]
fn main() {
trait PtrLike {
    fn is_null(v: *const Self) -> bool;
}
}

These methods would be useful when writing unsafe code because having an &self method requires satisfying the validity conditions of an &-reference, which may not be possible. If we did have such methods, however, it raises the question of whether it would be safe to invoke is_null on a *const dyn PtrLike reference. Just as with upcasting, invoking a method from the vtable requires loading from the vtable, and hence requires a valid vtable generated by the compiler.

The solution we propose in this document also resolves this future dilemma.

Definitions: validity vs safety invariant

We adopt the terms validity and safety invariant from the unsafe code guidelines:

The validity invariant is an invariant that all data must uphold any time it is accessed or copied in a typed manner. This invariant is known to the compiler and exploited by optimizations such as improved enum layout or eliding in-bounds checks.

The safety invariant is an invariant that safe code may assume all data to uphold. This invariant is used to justify which operations safe code can perform. The safety invariant can be temporarily violated by unsafe code, but must always be upheld when interfacing with unknown safe code. It is not relevant when arguing whether some program has UB, but it is relevant when arguing whether some code safely encapsulates its unsafety -- in other words, it is relevant when arguing whether some library is sound.

In short, the validity invariant defines a condition that must always be true, even in unsafe code, and the safety invariant defines an invariant that unsafe code must guarantee before a value can be released to be used by arbitrary code.

Contours of the solution space

We can fix this conflict in one of two basic ways:

First, we could make vtable-adjusting upcasts casts (and *Self method calls) unsafe. This is difficult to implement and would require changes to the Coerce trait, which is already excessively complicated. In exchange, it offers at best marginal benefit: raw *dyn pointers can be released to safe code, but safe code can't do anything interesting with them. For this reason, we do not recommend this option.

If vtable-adjusting casts (and *Self method calls) are safe, then the safety invariant for *dyn types must be that their metadata points to a fully valid vtable (i.e., a vtable created by the compiler). This ensures safe code can perform upcasts or dynamic dispatch. This also implies that std::ptr::null (which is safe) cannot be extended to T where T: ?Sized unless further changes are made, since we would need to provide a valid vtable (it would be possible to permit a sentinel value, like null, to be used, but that would imply that upcasting must have a branch, making it less efficient).

There are, however, various options for the validity invariant, ranging from no invariant to requiring a fully valid vtable at all times. The strict invariants offer some benefits, such as the ability to have a niche for *dyn pointers. We survey the options here:

Explanations for the column titles:

• Validity invariant for *dyn metadata -- describes the invariant that applies to the metadata for a *dyn value.
• Supports niche -- true if there is a niche value so that sizeof(Option<*const dyn Foo>) == sizeof(*const dyn Foo).
• Can be initialized with std::mem::zeroed -- true if std::mem::zeroed can be used to create a valid value (very convenient). This makes it trivial to innitialize a *const dyn with a dummy value, though the value cannot be released to safe code.
• Constant initializer -- true if there is some constant value for *const dyn Foo that satisfies the validity invariant, no matter the trait Foo. This makes it easy to initialize a *const dyn with a dummy value, though the value cannot be released to safe code.

Other points:

• *dyn values currently have a niche.
• Other pointer-like values (such as fn and &-references) are expected to have a validity invariant of word-aligned, non-null.
• Whichever option we use, we can backwards-compatibly move "up the table" and adopt a less-strict validity invariant without introducing UB into any extant programs.

Proposal

The proposal is as follows:

• Vtable-adjusting upcasts are safe operations. The upcast is UB if performed on a value without a valid vtable
• As such, the "safety invariant" requires a fully valid vtable.
• The "validity invariant" requires *dyn metadata to be word-aligned and non-null.

Vtable-adjusting upcasts are defined as:

• Trait upcasts that alter the set of methods that can be invoked on the resulting value at runtime (e.g., dyn Bar to dyn Foo from the introduction). In particular, upcasts that simply add or remove auto-traits are not vtable-adjusting (e.g., dyn Debug + Send to dyn Debug).

This approach...

• permits safe upcasting (and method calls, in the future);
• preserves the existing niche for *const dyn;
• is consistent with other validity requirements for "pointer-like" things such as fn;

The rules also imply that...

• valid (i.e., compiler-generated) vtables are only required for a *dyn pointer when
  • the *dyn pointer is upcast (or invoke methods);
  • or, when the *dyn pointer is released to arbitrary code, because that code may upcast (or invoke methods).
    • By implication, extending std::ptr::null to permit T: ?Sized would not be safe.

Possible future changes...

• without introducing UB, we could loosen the validity invariant if desired, for example to permit NULL as a valid value in unsafe code.
• without introducing UB, we could also loosen the safety invariant to permit a sentinel value (such as NULL), but that would require a branch or other check in the upcast code, which would be less efficient.

Prior links

• Dyn safety write-up, which includes links to prior write-ups
• Exhaustive set of validity invariants considered

Upcast safety options considered

This document details a number of options that were considered while preparing the upcast-safety-3 proposal.

Summary table

True no matter what

• MaybeUnit<*const dyn Foo> can be used to create an uninitialized *const dyn Foo easily, like with any other type.
• If we add *const self methods (which we should), and permit those to be invoked from safe code (which would be consistent, given that one can invoke a self method defined on a *const T type in safe code), then it will be unsound (i.e., potentially allow safe code to create UB) to release a *const dyn Foo to safe code unless the vtable is fully valid (created by the compiler).
• vtable layout is not defined.
• No matter what proposal we adopt, if you create a *const dyn Foo with anything less than a fully valid vtable (including e.g. a null placeholder), you must not allow that to escape to arbitrary code
  • This is actually a consequence of wanting to support *const self methods and method dispatch -- it could conceivably be true only for a trait Foo is it includes a *const self method, since those are not yet legal.

Proposals

fully-valid-vtable

It is UB to create a *const dyn Foo unless the vtable is fully valid (given that vtable layouts are undefined, this means produced by the compiler for the time being).

If you need to create a *const dyn Foo and don't have a valid vtable available, you can use MaybeUninit<*const dyn Foo>, or a union, or Option, which is probably good practice.

Forwards compatibility:

• Given that vtable layouts are not defined, there isn't much you can do at present in unsafe code with a vtable besides invoking methods, upcasting, computing the size, or other such operations.
• If we were to adopt other proposals that weaken the validity requirement, compatibility is a bit complex. At the time we make the change, all *const dyn values in extant code would have valid vtables. But people would be able to write code that created values with less-than-valid vtables (e.g., maybe null, etc, depending on what change we made). They would not however be able to give that code to other functions, even unsafe functions, unless those functions stated explicitly that they don't require the *const dyn value to have a fully valid vtable (i.e., they promised not to upcast it, etc).
  • This is effectively the same as the operations-are-ub proposal, even if we adopt it today. You can create invalid vtables, but you cannot allow them to escape.

null-placeholder

It is UB to create a *const dyn Foo unless the vtable is "sufficiently valid", except that NULL is permitted as a placeholder value.

This has the consequence that when we upcast, we have to check for NULL, which is less efficient.

Upshot:

• You may create a *const dyn Foo from std::mem::zeroed.
• The only thing you can do on a *const dyn Foo that is zeroed is copy it and upcast it.
  • Currently, this means you can release a *const dyn Foo to safe code, but if we were to add *const self methods, that might no longer be true, unless those methods are also prepared to deal with the null pointer in some way (e.g., abort?), or unless it's unsafe to invoke such a method (seems odd). But that's really an issue for *const self methods to deal with, since it's already true today.
• If receiving one from an unknown source, you can assume the vtable is either value for some type or NULL (of course, you can't assume anything about the data pointer, and vtable layouts are unknown, so it's not clear how useful that is).

Forwards compatibility:

• We can adopt any other proposal later, but we might lose the niche.

Notes:

• We can in theory support a niche with a value like 0x1 for the vtable?

operations-are-ub

There is no validity invariant for *const dyn Foo -- the vtable can be arbitrary. However, the only "non-UB" operation that you can do on a *const dyn Foo is to copy it, unless the vtable is known to be valid (produced by the compiler). Without a known valid vtable, all other options, including but not limited to the following, are UB:

• Upcasting it do *const dyn Bar (where trait Foo: Bar)
• Invoking methods from Foo (not currently possible without arbitrary-self-types)
• Creating a safe pointer type (e.g., &*foo)

Upshot:

• You can create a *const dyn Bar with mem::zeroed, but it must not escape to safe code (that would permit the safe code to create UB, and hence be unsound).
• If you are going to do anything besides copy that value around, it must be known to have a valid vtable at that time, or UB will result.

Forwards compatibility:

• If we adopt this proposal, we can't move to the others without introducing UB into otherwise valid code (consequence of the can-create-from-arbitrary-bits)

operations-are-ub-nza

The validity invariant for *const dyn Foo is that the vtable must be non-zero and aligned, ensuring a niche. However, -- the vtable can be arbitrary. However, the only "non-UB" operation that you can do on a *const dyn Foo is to copy it, unless the vtable is known to be valid (produced by the compiler). Without a known valid vtable, all other options, including but not limited to the following, are UB:

Properties

unconditional-upcast

If this property holds, then...

#![allow(unused)]
fn main() {
trait Foo: Bar { }

let x: *const dyn Foo = ...;
let y: *const dyn Bar = x;
}

can be done without any conditional operations.

can-create-from-zeroed

If this property holds, then...

#![allow(unused)]
fn main() {
let x: *const dyn Foo = std::mem::zeroed();
}

...is not insta-UB.

can-create-from-arbitrary-bits

If this property holds, then...

#![allow(unused)]
fn main() {
let x: *const dyn Foo = /* arbitrary bits */;
}

...is not insta-UB.

niche-for-dyn

Raw pointers for sized types do not presently have niches -- but under some of these proposals, vtables could potentially act as a niche, such that Option<*const dyn Foo> has the same size as *const dyn Foo. This seems like a pretty niche (no pun intended) advantage, and is not clearly desirable, but it helps to illustrate certain things.

Note that in some cases this property would be lost if we made future 'forwards compatible' changes (e.g., by moving from a more restricted variant to operations-are-ub).

Removed proposals

There were some ideas that turned out to not add value and were removed from the vtable.

sufficiently-valid-vtable

An earlier doc proposed a "sufficiently valid" vtable as the condition, where it was only legal to create a *const dyn Foo with a valid vtable, but you could not generally assume the vtable was valid. However, it was pointed out that because vtable layout is unstable, it's not clear what this "sufficiently valid" language adds.

The original intent was to prevent unsafe code authors who receive a *const dyn Foo from assuming that the vtable was valid. The fear was that if we made changes that permitted a "less than fully valid" vtable, that unsafe code would now be getting fewer guaranteese than it had before. But given that vtable layouts are unstable, the code can't do much in practice, and in any case, if we did change the requirements, we could safe that "unsafe code which doesn't say otherwise requires a fully valid vtable".

Spelling out the scenarios:

1. when I release to safe code, full validity is required, because there are safe operations that require it
2. so if I write a safe function, I can always assume full validity on input
3. if I write an unsafe fn, in Rust now I can assume that I get full validity (because we defined that as the invariant), but the only thing I can do with that are defined operations at present (e.g., invoke methods, etc). If in the future we define the layout, I could read data from that vtable, but since it is required to be fully valid, that seems ok. In the future, we could loosen the validity requirement, but we would say that unsafe functions must explicitly state that they accept a *const dyn with a less than fully valid vtable (in other words, we'd have "edition-like" treatment of validity invariants.

Regardless, it's not clear what kind of "less than fully valid" vtables we would accept. Some possibilities:

• Null placeholder.
• A "skeleton" vtable that permits upcast but has invalid methods. Feels awfully niche, not worth it.

Dyn upcast safety

NB: This document is outdated. Click here to see the latest version.

Summary

This doc concerns possible resolutions for the following potential problem:

• Given:
  • unsize coercions of raw pointers are legal and stable in safe code
  • upcasting may require loading data from vtable
• If:
  • dyn upcast coercions are a kind of unsize coercion
  • the safety invariant for *const dyn Foo permits an invalid vtable
• Then:
  • safe code could cause UB by upcasting a *const dyn SubTrait to a *const dyn SuperTrait

The doc recommends:

• Defining the safety invariant for a *const dyn Foo to be a "sufficiently valid" vtable for Foo
  • the definition of "sufficiently valid" is intentionally left undefined except to say:
    • a fully valid vtable is also "sufficiently valid"
    • it permits upcasting from *const dyn SubTrait to *const dyn SuperTrait without UB
  • this implies that the only way for users to produce a "sufficiently valid" vtable is with a fully valid one, but conversely safe code cannot rely on a *const dyn Foo having a fully valid vtable

Background

Unsize coercions are possible in safe code

A brief review of the DST coercion design:

• The PT: CoerceUnsized<PU> trait indicates that a smart pointer PT can be coerced to a smart pointer PU
  • This trait is manually implemented for each smart pointer type, e.g. impl<T> CoerceUnsized<Rc<U>> for Rc<T> where T: Unsize<U>.
  • The compiler requires that Rc<T> -> Rc<U> be a legal DST coercion per various built-in rules (e.g., T must be stored in the final field of the struct and cannot be behind another pointer indirection).
  • Example: Rc<String>: CoerceUnsized<Rc<dyn Debug>>
• The T: Unsize<U> trait indicates that the T: ?Sized referent can be "unsized" to the reference U
  • This trait is automatically implemented by the compiler.
  • Example: String: Unsize<dyn Debug>
  • Example: [String; 32]: Unsize<[String]>

This design permits one to write generic code that performances unsized coercions, but the trait is unstable so this only works on nightly:

#![allow(unused)]
fn main() {
// Unstable:
fn foo<PT, PU>(pt: PT) -> PU 
where 
    PT: CoerceUnsized<PU>,
{
    pt
}
}

Example

You can however coerce from a *const T to a *const dyn Trait in safe code on stable (playground):

fn main() {
    let x: *const u32 = &32;
    let y: *const dyn std::fmt::Debug = x;
}

Upcasting dyn SubTrait to dyn SuperTrait is considered an unsize coercion

We implemented upcasting from one dyn trait to a supertrait as an upsizing coercion. This means that dyn SubTrait: Unsize<dyn SuperTrait>. This is a coercion because it requires adjusting the vtable.

How upcasting coercions adjust the vtable

The vtable for a dyn SubTrait now embeds pointers to the vtables for super traits. Upcasting therefore requires loading the new vtable for the supertrait from the specific slot within the subtrait's table.

There are alternatives we could use such that upcasting would be a pure integer adjustment with no load, but that would be less efficient in terms of space usage.

Although not directly relevant here, there is another operation that requires accessing the vtable, which is finding the offset of fields -- see the discussion in the appendices for details. This operation is however only permitted in unsafe code because it requires a dereference of the raw pointer.

Ergo, upcasting raw pointers is possible in safe code

Without any further changes, the following upcasting is legal in safe Rust (playground):

#![allow(unused)]
#![feature(trait_upcasting])]

fn main() {
trait Sub: Sup { }
trait Sup { }

fn convert(x: *const dyn Sub) -> *const dyn Sup {
    x
}
}

Raw pointers are traditionally permitted to be "garbage"

A sized raw pointer like *const u32 has no validity/safety invariants to speak of. It is not required to be aligned, it may be null, and it may point at arbitrary memory. This is why Option<*const u32> requires an extra word fo the discriminant and it is why dereferencing a raw pointer is unsafe.

However, as noted in the previous section:

• if upcasting raw pointers is possible in safe code and
• if upcasting requires loading data from the vtable

then the safety condition of *const dyn Foo must include a "sufficiently valid" vtable. Sufficiently valid means that it is "structurally complete" in that it contains valid pointers that can be loaded to do upcasting.

What do we do for null or garbage data?

The challenge with *const dyn Trait is "what do we do to make a null pointer"? For better or worse, *const T pointers can traditionally be null: but when one creates a vtable, one is supposed to have some underlying data type to make the vtable for, and with a null pointer that is not possible.

Creating a *const dyn

If we wish to ensure a safety invariant for *const dyn values, we have to ask ourselves how one could go about producing such a value. There are currently two ways to create a *const dyn Trait, one safe and one unsafe:

• std::ptr::from_raw_parts -- safe, unstable
• std::mem::transmute -- unsafe, unwise

There is also a third way to make a *const T that doesn't work for dyn now but which could be made to work:

• std::ptr::null -- safe, stable, but currently limited only to *const T where T: Sized

Of these three:

• from_raw_parts requires a valid vtable for T as argument, so it would meet the safety requirement
• transmute is unsafe, but it would indeed be a requirement that users of transmute must uphold
• null, if extended to unsized types, would be tricky -- we would need to have some way to get a "dummy" vtable that is structurally sound enough to permit upcasting, but which has (for example) null pointers for the actual methods. This is, however, eminently doable.

Interaction: Raw pointer method calls

It would be useful if unsafe code could declare *const self and *mut self methods in traits

#![allow(unused)]
fn main() {
pub trait FreeMe {
    pub unsafe fn free_me(*const self);
}
}

Given that using &self implies (for ex

Core decision to be made

The core decision to be made is to choose between two paths:

• Splitting out "unsafe" unsizing operations from safe ones;
  • Unsizing operations on safe pointers like &dyn SubTrait would continue to work as they do today.
  • Implicit unsizing operations on raw pointers like *const dyn SubTrait would work sometimes, but those unsizing operations that require the metadata meet some sort of condition would require an explicit function call (e.g. the proposal below adds an unsafe function unsize_raw_pointer).
• Raw pointers have a validity or safety invariant that puts conditions on metadata
  • There are options in terms of when this invariant must hold and how strict the invariant must be, but the upshot is that whenever you synthesize the metadata for a raw, wide pointer (e.g., from a transmute), you need to ensure that this metadata comes from some valid source, and is not just garbage. This is contrast to the data pointer, which can generally be arbitrary bytes (though not unininitialized).

Why prefer unsafe raw pointer upcasting?

Raw pointers have traditionally been viewed as "untrusted data until they are used". This is why dereferencing a raw pointer is unsafe: that's the point where it must be valid. It makes sense to extend this model to the metadata as well. When working with raw pointers and unsafe code, implicit operations like upcasting are a bug, not a feature, so it's useful to segregate them out and make them explicit via some kind of function call. It does require adding a new trait (see below) to the unsizing mechanism, but it only requires an internal "implementation" trait, and doesn't affect the "main trait" (CoerceUnsized).

Besides, so long as the validity/safety invariants remain in flux (which they will be for a while yet), this choice is forwards compatible with the others. We have the option to remove the "unsafe upcast" and merge it with safe upcast and strengthen the relevant invariant(s).

Why prefer unsafe some form of invariant?

It's not clear why one would ever have invalid metadata in a wide pointer to start with; it's not an easy thing to do, you have to basically transmute from random bytes (e.g., zeroed memory). If you want to have a garbage pointer that is not yet initialized, use MaybeUninit. If you want a null pointer, use ptr::null or Option<Unique<_>>. In exchange for following these best practices, you get two things:

• Safe unsafe code overall, since you are being clearer about your intentions.
• A simpler coercion model, with fewer traits and moving parts, and things that work the same for all kinds of pointers
• A language that is

Options

The following options have been identified. The preferred solution is not yet clear.

RawUnsafe: Make raw pointer upcasting unsafe (not possible once dyn SubTrait: Unsize<dyn SuperTrait> is stable)

We could permit "safe pointer" upcasting but make raw pointer upcasting unsafe. This would require changing the design of the coercion traits somewhat. We would introduce a new "magic trait" RawUnsize, analogous to Unsize except that it doesn't permit upcasting or any other operations that could require valid metadata. We would then modify the impl of CoerceUnsized for raw pointers to be:

#![allow(unused)]
fn main() {
impl<T, U> CoerceUnsized<*const U> for *const T where
    T: Unsize<U> + ?Sized,
    U: ?Sized, 
}

and it would become

#![allow(unused)]
fn main() {
impl<T, U> CoerceUnsized<*const U> for *const T where
    T: RawUnsize<U> + ?Sized,
    U: ?Sized, 
}

To support upcasting on raw pointers, we can then introduce some other intrinsic for doing raw pointer upcast, such as something like this (modulo stacked borrows, which this particular definition may invalidate):

#![allow(unused)]
fn main() {
/// Unsafefy condition: If the metadata for `T` must be valid.
pub unsafe fn unsize_raw_pointer<T, U>(t: *const T) -> *const U
where
    T: Unsize<U>,
{
    let (_, t_metadata) = t.into_raw_parts();
    unsafe { &*t }
}
}

So long as Unsize remains a strict superset of RawUnsize, we could change things in the future to make RawUnsize an alias for Unsize (or, if it is unstable, remove it altogether) and thus deprecate the unsize_raw_pointer function. This is therefore forwards compatible with the preferred proposal here as well as other things that say "still possible in the future".

VISufficientlyValid: Extend the validity invariant of dyn Trait to require a "sufficiently valid" vtable

One solution is to extend the validity invariant for raw pointers to require a "sufficiently valid" vtable. We don't specify the precise condition that makes a vtable "sufficiently valid" except to say that a fully valid vtable is "sufficiently valid", and that a "sufficiently valid" vtable permits dyn upcasting without UB.

Implications:

• Whenever one creates a wide pointer, one must ensure that the metadata is "sufficiently valid":
  • For *const dyn Trait, this would mean that one must use a valid vtable for Trait.
    • In particular, we don't define what is "sufficiently valid" so you have to use something that is fully valid; at the same time, you cannot rely on the vtable for *const dyn Trait being fully valid yourself, only "sufficiently valid" (which is "valid enough for upcast" and that's it).
• If the pointer is not initialized, and hence you don't know which vtable to use, you have the following options:
  • Use a dummy vtable for any type, it doesn't matter which.
  • Use MaybeUninit<*const dyn Foo>, in which case no safety invariant is assumed.
  • Use Option<*const dyn Foo> and None instead of null: safer, wastes space.
  • Use Option<NonNull<dyn Foo>> and None instead of null: safer, generally better, perhaps less ergonomic.

One downside of this proposal is that the validity invariant is stricter than is needed: that is, the purpose of the validity invariant is primarily to enable the compiler's ability to perform layout optimizations. This rule would enable the compiler to silently insert upcasting operations if it needed to do so, but it's not clear why it would need to do that spontaneously: those operations are always tied to something else (e.g., a coercion or a method call). Therefore, the safety invariant might seem like a better fit.

SISufficientlyValid: Extend the safety invariant of dyn Trait to require a "sufficiently valid" vtable

As an alternative to modifying the validity invariant, we could modify the safety invariant for wide pointers to include "sufficiently valid" metadata (see VISufficientlyValid for details).

Implications:

• Whenever one performs an upcast or other operation with a wide pointer, one must ensure that the metadata is "sufficiently valid":
• If the pointer is not initialized, and hence you don't know which vtable to use, you have the same options as described under VISufficientlyValid.

The primary downsice of this proposal versus VISufficientlyValid is that the causes of UB are rather more subtle. Instead of UB occurring when the pointer is created, it occurs when an upcast occurs, and the locations for upcasts can be implicit (eg., any assignment or function call). Consider the following example:

#![allow(unused)]
fn main() {
fn noop(x: *mut dyn SuperTrait) { 
    /* look ma, empty body */
}

fn creator() {
    // No UB yet: the metadata for `x` is not sufficiently valid,
    // but we haven't done anything with it yet.
    let x: *mut dyn SubTrait = unsafe { std::mem::zeroed() };

    // `y = x` does not trigger UB, just a copy.
    let y = x;

    // UB! Here there is a coercion.
    noop(y);
}
}

For this reason, it would probably be "best practice" to treat this condition "as if" it were part of the validity invariant.

SIFullyValid: Extend safety condition to require a "fully valid" vtable (still possible in the future)

This would permit safe code to read values from the vtable of a *const dyn Trait without any unsafety (just as it does for upcasting). It's not clear why we would want to permit this, and it may foreclose useful options in the future.

Adopting this option remains a possibility in the future, as it would be a backwards compatible extension to the above rule.

SIStructValid: Extend safety condition to require a "structurally valid" vtable (still possible in the future)

Instead of requiring a valid vtable, we could require a "structurally valid" vtable. This vtable would have null pointers for all methods as well as a dummy type-id but would have the same "structure" as an ordinary vtable. There would be an intrinsic that gives access to the vtable:

#![allow(unused)]
fn main() {
fn dummy_vtable::<T: ?Sized>() -> T::Metadata
}

This would permit one to represent an uninitialized dyn pointer as *const dyn Foo and use the dummy-vtable for its metadata. This could be convenient, but is less typesafe than MaybeUnit or Option<NonNull> and not obviously better.

Adopting this option remains a possibility in the future, as it would be a backwards compatible extension to the above rule.

NullVtable: Special case the vtable for null (still possible in the future)

Instead of saying that a "null dyn pointer" must have a structurally sound vtable, we could permit null as the value for the vtable. This would require an "if branch" or some kind of more complex logic in the upcasting path, since we couldn't unconditionally do a load. That might be acceptable, but it seems silly to slow down the upcasting path for a relatively unusual case of having a null

FlatVtable: Adjust vtable layout to not require a load (still possible in the future)

We could adjust the vtable layout for a subtrait to include embedded copies of all supertraits. This way the upcast is a pure offset operation and does not require a load. This would be less efficient in terms of space usage. We generally prefer not to limit the possible vtable designs that an implementation can use unless we have to, so as to leave room for future developments.

Appendices

Validity versus safety invariants

Let us take a digression to cover Ralf's distinction of validity vs safety invariants:

• The validity invariant for a type T defines the invariant that all values of type T must meet, all of the time. These invariants are respected in both safe and unsafe code and are primarily used to do layout optimizations.
  • For example, the validity invariant of bool requires that the value is 0 or 1 but not 2. Thanks to this validity invariant, Option<bool> can be represented by the compiler in the same amount of space as bool.
• The safety invariant for a type T defines the invariant that all values of type T must meet when given to safe code. These invariants are used to justify unsafe code, but aren't understood by the compiler.
  • For example, a vector has a field for its length and capacity, and the safety invariant requires that they accurately describe the allocate space available in the vector's buffer (and aren't just random values). Thanks to this safety invariant, we can create push as a safe function: it can read those fields and rely on them being accurate to decide whether the memory still has any free capacity.

Metadata and field offsets

Consider these struct definitions:

#![allow(unused)]
fn main() {
struct RefCounted<T> {
    counter: usize,
    data: T,
}

struct Foo<U> {
    field: u32,
    data: U
}
}

and now assume that I have a *const RefCounted<Foo<u32>> which is coerced:

#![allow(unused)]
fn main() {
let pointer1: *const RefCounted<Foo<u32>> = ...;
let pointer2: *const RefCounted<Foo<dyn Debug>> = pointer1;
}

If I now try to get the address of the field field...

#![allow(unused)]
fn main() {
let pointer3: *const u32 = unsafe { raw_addr!((*pointer2).data.field) };
}

...this operation requires valid metadata. This is because the offset of field is a function of the alignment of Foo<U>, which is a function of the alignment of U. In these cases, the compiler will load the alignment from the vtable and do the required address computations itself.

Upcast safety

NB: This document is outdated. Click here to see the latest version.

Scenario

• Casting *dyn Foo to *dyn Bar requires adjusting the vtable from a vtable for Foo to one for Bar
• For raw pointers, the metadata can be supplied by the user with from_raw_parts
  • If that metadata is incorrect, this could cause UB:
    • our current vtable format requires loads, and the pointers may not be valid
    • a flat vtable layout could give rise to out-of-bounds loads
• Unsafety is needed, but where?

Options

Unsafe to create a *dyn Foo

Announce that every fat pointer needs to have valid metadata part. Needs to switch the std::ptr::from_raw_parts{,_mut} APIs to be unsafe. And updates other documentations.

Implication: Not able to create a "null pointer" version of *dyn Foo unless:

• You use Option<*dyn Foo>, of course
• We create some kind of "dummy" vtable that is structurally correct but has no actual functions within it; we would need a function for creating "valid-but-default" metadata as part of custom DST

Update:

• It was pointed out by steffahn that std::ptr::from_raw_parts won't create fat pointer with invalid metadata.
• One of the remaining ways to create a pointer with invalid metadata is by using transmute.

Question:

• Does the language UB happen at transmute site or coercion site?

Alter vtable layout to be flat

Make vtables "flat", by removing all pointer indirections in vtables and appending all the data to the tail. This makes upcasting coercion codegen become adding an offset to the metadata scalar, so won't cause real UB. Will waste some more static bytes in multiple inheritance cases than before, might make embedded-dev people unhappy.

Question from Niko:

• Is this sufficient? Does it imply we can't use InBoundsGep? Is that already true?

Make raw pointer unsizing unsafe

Announce that raw pointer unsizing coercion must happen in unsafe blocks, while other unsizing coercions can happen outside an unsafe block. This is actually a small breaking change. So need a future compat lint to migrate existing users dealing with raw pointers and some more changes to std(POC PR at #88239 explains the details but it's a bit long). A few other MIR-level details become observable by user: whether the compiler thinks it's a unsizing coercion or not.

nikomatsakis: (cc @RalfJ, if you happen to be around)

Conversation log

• 2021-08-25

Vtable format to support dyn upcasting coercion

This current design was proposed by Mario Carneiro based on previous proposals on Zulip discussion. It's a hybrid approach taking the benefits of both a "flat" design, and a "pointer"-based design.

This is implemented in #86461.

The vtable is generated by this algorithm in principle for a type T and a trait Tr:

1. First emit the header part, including MetadataDropInPlace, MetadataSize, MetadataAlign items.
2. Create a tree of all the supertraits of this TraitRef, by filtering out all of duplicates.
3. Collect a set of TraitRefs consisting the trait and its first supertrait and its first supertrait's super trait,... and so on. Call this set PrefixSet
4. Traverse the tree in post-order, for each TraitRef emit all its associated functions as either Method or Vacant entries. If this TraitRef is not in PrefixSet, emit a TraitVPtr containing a constant pointer to the vtable generated for the type T and this TraitRef.

Example

#![allow(unused)]
fn main() {
trait A {
    fn foo_a(&self) {}
}

trait B: A {
    fn foo_b(&self) {}
}

trait C: A {
    fn foo_c(&self) {}
}

trait D: B + C {
    fn foo_d(&self) {}
}
}

Vtable entries for `<S as D>`: [
    MetadataDropInPlace,
    MetadataSize,
    MetadataAlign,
    Method(<S as A>::foo_a),
    Method(<S as B>::foo_b),
    Method(<S as C>::foo_c),
    TraitVPtr(<S as C>),
    Method(<S as D>::foo_d),
]

Vtable entries for `<S as C>`: [
    MetadataDropInPlace,
    MetadataSize,
    MetadataAlign,
    Method(<S as A>::foo_a),
    Method(<S as C>::foo_c),
]

Runtime behavior for dyn upcasting coercion

At the codegen time, the same algorithm above is performed for the source principal trait and the source trait object type. If the target principal trait is in the PrefixSet set, this coercion is a no-op.

If the target principal trait is not in the PrefixSet, generate code that read the data pointer from the corresponding TraitVPtr slot.

Alternatives

Flat design

The vtable is generated by this algorithm in principle for a type T and a trait Tr:

1. Create a tree of all the supertraits of this TraitRef, duplicate for the cyclic cases.
2. Traverse the tree in post-order, for each TraitRef,
   1. if it has no supertrait, emit a header part, including MetadataDropInPlace, MetadataSize, MetadataAlign items.
   2. emit all its associated functions as either Method or Vacant entries.

Cons

If there is a lot of diamond inheritance that could result in exponential blowup of the vtable for example, trait A(n+1): Bn + Cn {}, trait Bn: An { fn bn(&self); }, trait Cn: An { fn cn(&self); }

the vtable for An will contain 2^n DSAs

Pointer-based design

All traits have their own vtables, and embedded all links to supertraits in the vtables

Cons

Codegen regression for single-inheritance cases, which is very widely used.

😕 FAQ