Implicit auto traits and trait definitions

Waddup everyone!

trait Deref {
    type Target: ?Sized;
}

has to get lowered to

trait Deref: Move {
    type Target: ?Sized + Move;
}

to avoid breaking the following snippets:

fn nested_explicit_arg<T: Deref<Target = U>, U: ?Sized>(x: T) {}
fn foo<T: Deref>(x: T) {
    nested_explicit_arg(x)
}

fn nested_takes_target<T: ?Sized>(x: Option<&T>) {}
fn bar<T: Deref>(x: Option<T>) {
    nested_takes_target(x.as_deref())
}

trait Trait<T> {}
fn impls_trait_with_arg<T: Deref, U: Trait<T::Target>>() {}

This sucks. It would mean we could not implement Deref for Box<ExternType>. In general, adding new implicit trait bounds requires putting them on associated types to not break backwards compatibility.

Even more generally, removing implicit trait bounds in trait definitions is a breaking change. While free functions can freely remove implicit trait bounds, we must not do so in trait definitions.

We have to really look for a way to weaken requirements of traits in a backwards compatible way if we want to introduce new implicit auto traits. Doing so is especially challenging for associated types.

Elaborating on use

Instead of adding the implicit default to the trait definition, we could try to add these defaults to uses of the trait. We can then change the lowering in a future edition to no longer implicitly add the default auto trait. I don’t whether we can get this to work. It would result in the following lowering for the code above

trait Deref {
    type Target: ?Sized;
}

fn nested_explicit_arg<
    T: Deref<Target = U> + Move,
    U: ?Sized + Move
>(x: T) {}
fn foo<T: Deref<Target: Move> + Move>(x: T) {
    nested_explicit_arg(x)
}

fn nested_takes_target<T: ?Sized + Move>(x: Option<&T>) {}
fn bar<T: Deref<Target: Move> + Move>(x: Option<T>) {
    nested_takes_target(x.as_deref())
}

trait Trait<T> {}
fn impls_trait_with_arg<
    T: Deref<Target: Move> + Move,
    U: Trait<T::Target> + Move,
>() {}

It’s unclear how this could handle

trait Recur {
    type Assoc: Recur;	
}

fn foo<T: Recur>() {}

Trying to lower this would result in an infinite expansion:

fn foo<T: Recur>()
where
    T: Move,
    T::Assoc: Move,
    <T::Assoc as Recur>::Assoc: Move,
    <<T::Assoc as Recur>::Assoc as Recur>::Assoc: Move,
    ...
{}

Alternatively, we could only elaborate the where-bound for one layer until T: Recur<Assoc: Recur>, without any bound for <T::Assoc as Recur>::Assoc: Move. This would cause the following code to error however:

fn foo<T: Recur>() {}
fn bar<T: Recur>() {
    // `bar` has an elaborated where-bound that `T::Assoc: Move` holds,
    // would fail to prove the elaborated where-bound of `foo` requiring
    // `<T::Assoc as Recur>::Assoc: Move` however. 
    foo::<T::Assoc>();
}

That sort of breakage seems like a no-go to me.

While elaborating on use seems challenging in general, @davidtwco and @nikomatsakis have considered only doing it for selected traits, e.g. Deref, avoiding the infinite expansion issue. This then allows nice use of Deref for pointers to extern types in future editions.

Rules? More like guidelines

Rust’s type system is cool and all, however, we could just give up and not bother.

What if instead of elaborating traits to make sure default auto-traits don’t break anything, we support deferring that check to monomorphization time for rigid aliases - and maybe generic parameters - while emitting a future compat lint.

fn nested_takes_target<T: ?Sized>(x: Option<&T>) {}
fn bar<T: Deref>(x: Option<T>) {
    nested_takes_target(x.as_deref())
    //~^ WARN `T::Target: Move` does not hold but should
    //~| NOTE required by `nested_takes_target`
    //~| NOTE this is guaranteed to result in an error when monomorphizing this item with a type which is not `Move`
    //~| NOTE this is currently accepted but is getting phased out
}

Is this actually possible?

Adding support for this kind of hack is non-trivial, but should be possible. This is sketch of how this could work and I have not actually tried to get a working implementation here.

When encountering a rigid alias for which an implicit-default trait does not hold, we add a candidate which holds with this goal as a deferred requirement in its external constraints.

This way the trait system is now able to handle Option<T::Assoc>: Move. This goal will now hold while returning the deferred requirement that T::Assoc: Move holds. We then require the InferCtxt which got these deferred requirements to do something with them.

What to do with these requirements depends on the query we’re in. In general, we’d erase any lifetimes and then put them in the corresponding MIR body/check that they are already required by this MIR body. When monomorphizing a MIR body during codegen/CTFE and so on we check these requirements.

Lifetime-dependence

This cannot handle lifetimes. I don’t believe this to be a major issue.Move implementations should generally not be lifetime dependent. We could either require them to not be by adding a check to user-written impls. This feels like the best option to me.

Alternatively, we could prove that these deferred goals hold for all lifetimes. This is challenging as it would require us to “uniquify” lifetimes which causes hangs for deeply recursive, but otherwise self-similar types.

Another somewhat hacky alternative is to track whether we’ve relied on a potentially lifetime dependent impl while proving the deferred goal, and if so, emit a hard error. As long as this check never incorrectly triggers for builtin impls it’d only cause breakage in cases where somebody already replaced the builtin auto-trait impl with a different user-written impl. This feels like an acceptable risk to me.

We could just accept some theoretical unsoundness here and mention that concern in the future compat lint. This should only be done if the future compat lint triggers fairly rarely. I cannot judge this right now.

It’s possible, cool! How can users fix the FCW

Free functions and methods

For free functions they propagate the requirement to the where-clauses of their function. This should never be a breaking change.

It may move an error from monomorphization time to analysis if the function already had a caller which does not implement the default auto trait, however that should not be considered a breaking change.

Trait implementations and definitions

Adding implicit super trait bounds limits implementations of that trait. Users can always instead add a bound on the impl. We can implicitly support this by implicitly adding these auto traits during where-clause lowering instead, which allows us to remove the implicit bound over an edition. We do require these bounds on traits to support using them in trait methods which rely on the auto-trait.

If all methods of a trait implementation require the new builtin auto-trait, and the requirement can be added as a where-clause to the impl itself, fixing this is not a breaking change, same as for free functions.

If only some of the trait methods rely on the auto-trait or if the requirement is for a generic parameter of a trait function, it’s harder to fix. Moving these requirements to the trait definition is limiting and a breaking change unfortunately. It breaks code which currently uses the trait for types which don’t have that auto-trait requirement.

Anyways

Changing auto trait errors to be FCWs instead of hard errors and only hard erroring if they don’t hold during monomophization is possible. It could empower us to better add new implicit trait bounds.

It will still not be easy and I don’t have the time to think this through. I luckily don’t have to. Have fun @yoshuawuyts. Please send any language design ideas or questions to them.

back

impressum rss