• Feature Name: N/A
• Start Date: (fill me in with today's date, YYYY-MM-DD)
• RFC PR: rust-lang/rfcs#1214
• Rust Issue: rust-lang/rust#27579

Summary

Type system changes to address the outlives relation with respect to projections, and to better enforce that all types are well-formed (meaning that they respect their declared

• Simplify the outlives relation to be syntactically based.
  基となる、基底(の)
• Specify
  特定する、指定する、規定する
  improved rules for the outlives relation and projections.
• Specify
  特定する、指定する、規定する
  more specifically
  特に
  where WF bounds
  制限する、結び付けられて
  are enforced, covering several cases missing from the implementation.
  実装

The proposed changes here have been tested and found to cause only a modest number of regressions (about two dozen root regressions were previously found on crates.io; however, that run did not yet include all the provisions from this RFC; updated numbers coming soon). In order

1. Initially, warnings will be issued for cases that violate
   違反する
   the rules specified
   特定する、指定する、規定する
   in this RFC. These warnings are not lints and cannot be silenced except by correcting the code such that it type-checks under the new rules.
2. After one release cycle, those warnings will become errors.

Note that although the changes do cause regressions, they also cause some code (like that in #23442) which currently gets errors to compile successfully.

Motivation

TL;DR

This is a long detailed RFC that is attempting to specify

Warnings first, errors later. Although the changes described

Associated type projections and lifetimes work more smoothly. The current rules for relating associated type projections (like T::Foo) and lifetimes are somewhat cumbersome. The newer rules are more flexible, so that e.g. we can deduce that T::Foo: 'a if T: 'a, and similarly

Simpler outlives relation. The older definition

#![allow(unused)]
fn main() {
// OK now, but after this RFC requires `X: 'a`:
struct Foo<'a, X> {
    f: fn(&'a X) // (because of this field)
}
}

More types are sanity checked. Generally Rust requires that if you have a type like SomeStruct<T>, then whatever where clauses

#![allow(unused)]
fn main() {
struct SomeStruct<T:Eq> { .. }
}

then this implies

#![allow(unused)]
fn main() {
impl Iterator for SomethingElse {
    type Item = SomeStruct<f32>; // accepted now, not after this RFC
}
}

Similarly,

There are a few other places where similar

#![allow(unused)]
fn main() {
trait Foo {
    // currently accepted, but should require that Self: Sized
    fn method(&self, value: Option<Self>);
}
}

To be well-formed, an Option<T> type requires that T: Sized. In this case, though T=Self, and Self is not Sized by default. Therefore, this trait should be declared

Impact on crates.io

This RFC has been largely implemented

Of the affected crates, 40 are receiving future compatibility

What follows

As you can see, by far the largest source

An example of each case follows:

Cases 1 and 2. In the compiler today, types appearing

#![allow(unused)]
fn main() {
trait Test {
    fn test(&self) -> Option<Self>;
    //                ~~~~~~~~~~~~
    //            Incorrectly permitted before.
}
}

Because Option<T> requires that T: Sized, this trait should be declared

#![allow(unused)]
fn main() {
trait Test: Sized {
    fn test(&self) -> Option<Self>;
}
}

Case 2. Case 2 is the same as case 1, except that the missing bound

Case 3. The compiler currently permits

Projections and the outlives relation

RFC 192 introduced the outlives relation T: 'a and described

#![allow(unused)]
fn main() {
fn foo<'a,I>(x: &'a I)
    where I: Iterator
{ ... }
}

the compiler is able to use implied

• all borrowed content in the type I outlives the function body;
• all borrowed content in the type I outlives the lifetime 'a.

When associated types were introduced in RFC 195, some new rules were required to decide when an "outlives relation" involving a projection (e.g., I::Item: 'a) should hold.

Simultaneously, we realized in #24622 that the compiler had a bug that caused it to erroneously

This RFC describes

Well-formed types

A type is considered

For example, consider

#![allow(unused)]
fn main() {
struct DeltaMap<'a, K, V> where K: Hash + 'a, V: 'a {
    base_map: &'a mut HashMap<K,V>,
    additional_values: Vec<(K,V)>
}
}

Here, the WF criteria for DeltaMap<K,V> are as follows:

• K: Hash, because of the where-clause,
• K: 'a, because of the where-clause,
• V: 'a, because of the where-clause
• K: Sized, because of the implicit
  暗黙の
  Sized bound
  制限する、結び付けられて
• V: Sized, because of the implicit
  暗黙の
  Sized bound
  制限する、結び付けられて

Let's look at those K:'a bounds

An aside: explicit

明示的な

WF requirements on types

You might wonder why you have to write K:Hash and K:'a explicitly.

This has real consequences

#![allow(unused)]
fn main() {
struct Wrap1<'a,K>(Wrap2<'a,K>);
struct Wrap2<'a,K>(Wrap3<'a,K>);
struct Wrap3<'a,K>(DeltaMap<'a,K,K>);
}

Now, for Wrap1<'foo,T> to be well-formed, T:'foo and T:Hash must hold,

Implied

暗黙の

lifetime bounds

制限する、結び付けられて

To help avoid

To see this in action, consider

#![allow(unused)]
fn main() {
fn foo<'a,K:Hash,V>(d: DeltaMap<'a,K,V>) { ... }
}

You'll notice that there are no K:'a or V:'a annotations required here. This is due to implied

As the name "implied

Currently, implied

NB. There is an additional

Missing WF checks

Unfortunately, the compiler currently fails to enforce WF in several important cases. For example, the following

#![allow(unused)]
fn main() {
struct MyType<T:Copy> { t: T }

trait ExampleTrait {
    type Output;
}

struct ExampleType;

impl ExampleTrait for ExampleType {
    type Output = MyType<Box<i32>>;
    //            ~~~~~~~~~~~~~~~~
    //                   |
    //   Note that `Box<i32>` is not `Copy`!
}
}

However, if we simply naively add the requirement that associated types must be well-formed, this results

#![allow(unused)]
fn main() {
impl<'a, T> IntoIterator for &'a LinkedList<T> {
   type Item = &'a T;
   ...
}
}

The problem here is that for &'a T to be well-formed, T: 'a must hold,

Detailed design

設計（する）

This section

A little type grammar

文法

We extend

T = scalar (i32, u32, ...)        // Boring stuff
  | X                             // Type variable
  | Id<P0..Pn>                    // Nominal type (struct, enum)
  | &r T                          // Reference (mut doesn't matter here)
  | O0..On+r                      // Object type
  | [T]                           // Slice type
  | for<r..> fn(T1..Tn) -> T0     // Function pointer
  | <P0 as Trait<P1..Pn>>::Id     // Projection
P = r                             // Region name
  | T                             // Type
O = for<r..> TraitId<P1..Pn>      // Object type fragment
r = 'x                            // Region name

We'll use this to describe the rules in detail.

A quick note on terminology: an "object type fragment" is part of an object type: so if you have Box<FnMut()+Send>, FnMut() and Send are object type fragments. Object type fragments are identical

Syntactic definition

定義

of the outlives relation

The outlives relation is defined

Simple outlives rules

Here are the rules covering the simple cases, where no type parameters

OutlivesScalar:
  --------------------------------------------------
  R ⊢ scalar: 'a

OutlivesNominalType:
  ∀i. R ⊢ Pi: 'a
  --------------------------------------------------
  R ⊢ Id<P0..Pn>: 'a

OutlivesReference:
  R ⊢ 'x: 'a
  R ⊢ T: 'a
  --------------------------------------------------
  R ⊢ &'x T: 'a

OutlivesObject:
  ∀i. R ⊢ Oi: 'a
  R ⊢ 'x: 'a
  --------------------------------------------------
  R ⊢ O0..On+'x: 'a

OutlivesFunction:
  ∀i. R,r.. ⊢ Ti: 'a
  --------------------------------------------------
  R ⊢ for<r..> fn(T1..Tn) -> T0: 'a

OutlivesFragment:
  ∀i. R,r.. ⊢ Pi: 'a
  --------------------------------------------------
  R ⊢ for<r..> TraitId<P0..Pn>: 'a

Outlives for lifetimes

The outlives relation for lifetimes depends on whether the lifetime in question was bound

OutlivesRegionEnv:
  'x ∉ R               // not a bound region
  ('x: 'a) in Env      // derivable from where-clauses etc
  --------------------------------------------------
  R ⊢ 'x: 'a

OutlivesRegionReflexive:
  --------------------------------------------------
  R ⊢ 'a: 'a

OutlivesRegionTransitive:
  R ⊢ 'a: 'c
  R ⊢ 'c: 'b
  --------------------------------------------------
  R ⊢ 'a: 'b

For higher-ranked lifetimes, we simply ignore

OutlivesRegionBound:
  'x ∈ R               // bound region
  --------------------------------------------------
  R ⊢ 'x: 'a

Outlives for type parameters

仮引数

For type parameters,

OutlivesTypeParameterEnv:
  X: 'a in Env
  --------------------------------------------------
  R ⊢ X: 'a

Outlives for projections

Projections have the most possibilities. First, we may find information in the in-scope where clauses,

OutlivesProjectionEnv:
  <P0 as Trait<P1..Pn>>::Id: 'b in Env
  <> ⊢ 'b: 'a
  --------------------------------------------------
  <> ⊢ <P0 as Trait<P1..Pn>>::Id: 'a

OutlivesProjectionTraitDef:
  WC = [Xi => Pi] WhereClauses(Trait)
  <P0 as Trait<P1..Pn>>::Id: 'b in WC
  <> ⊢ 'b: 'a
  --------------------------------------------------
  <> ⊢ <P0 as Trait<P1..Pn>>::Id: 'a

All the rules covered so far already exist today. This last rule, however, is not only new, it is the crucial insight of this RFC. It states that if all the components

OutlivesProjectionComponents:
  ∀i. R ⊢ Pi: 'a
  --------------------------------------------------
  R ⊢ <P0 as Trait<P1..Pn>>::Id: 'a

Given

Let's begin with a concrete

<Iter<'a,T> as Iterator>::Item

or, in the more succint (but potentially ambiguous) form:

Iter<'a,T>::Item

Since I'm going to be talking a lot about this type, let's just call

Now, the easy way to solve <PROJ>: 'x would be to normalize <PROJ> by looking at the relevant impl:

#![allow(unused)]
fn main() {
impl<'b,U> Iterator for Iter<'b,U> {
    type Item = &'b U;
    ...
}
}

From this impl, we can conclude that <PROJ> == &'a T, and thus

But often we are in a situation where we can't normalize the projection (for example, a projection like I::Item where we only know that I: Iterator). What can we do then? The rule OutlivesProjectionComponents says that if we can conclude that every lifetime/type parameter

OK, so we've seen that applying

The basis of the rule comes from reasoning about the impl that we used to do normalization. Let's consider

#![allow(unused)]
fn main() {
impl<'b,U> Iterator for Iter<'b,U> {
    type Item = /* <TYPE> */;
    ...
}
}

So when we normalize <PROJ>, we obtain

The key idea for the OutlivesProjectionComponents is that the only way that <TYPE> can fail to outlive 'x is if either:

• it names some lifetime parameter
  仮引数
  'p where 'p: 'x does not hold;
  保有する、有効である
  or,
• it names some type parameter
  仮引数
  X where X: 'x does not hold.
  保有する、有効である

Now, the only way that <TYPE> can refer

Put yet another way: imagine that you have an impl with no parameters

#![allow(unused)]
fn main() {
impl Iterator for Foo {
    type Item = /* <TYPE> */;
}
}

Clearly, whatever <TYPE> is, it can only refer

Implementation

実装

complications

The current region inference code only permits

C = r0: r1
  | C AND C

This is convenient because a simple fixed-point iteration

Unfortunately, this constraint

C = 'X:'a AND 'a:'X AND 'b:'Y

Otherwise,

C = C1 AND 'X:'Y

where C1 is the constraint

As you can see, these two rules yielded

This complication is unfortunate, but to a large extent already exists with where-clauses and trait matching (see e.g. #21974). (Moreover, it seems to be inherent to the concept of assocated types, since they take

For the time being, the current implementation

The WF relation

This section

The WF relation is really pretty simple: it just says that a type is "self-consistent". Typically,

WfScalar:
  --------------------------------------------------
  R ⊢ scalar WF

WfParameter:
  --------------------------------------------------
  R ⊢ X WF                  // where X is a type parameter

WfTuple:
  ∀i. R ⊢ Ti WF
  ∀i<n. R ⊢ Ti: Sized       // the *last* field may be unsized
  --------------------------------------------------
  R ⊢ (T0..Tn) WF

WfNominalType:
  ∀i. R ⊢ Pi Wf             // parameters must be WF,
  C = WhereClauses(Id)      // and the conditions declared on Id must hold...
  R ⊢ [P0..Pn] C            // ...after substituting parameters, of course
  --------------------------------------------------
  R ⊢ Id<P0..Pn> WF

WfReference:
  R ⊢ T WF                  // T must be WF
  R ⊢ T: 'x                 // T must outlive 'x
  --------------------------------------------------
  R ⊢ &'x T WF

WfSlice:
  R ⊢ T WF
  R ⊢ T: Sized
  --------------------------------------------------
  [T] WF

WfProjection:
  ∀i. R ⊢ Pi WF             // all components well-formed
  R ⊢ <P0: Trait<P1..Pn>>   // the projection itself is valid
  --------------------------------------------------
  R ⊢ <P0 as Trait<P1..Pn>>::Id WF

WF checking and higher-ranked types

There are two places in Rust where types can introduce

WfFn:
  ∀i. R, r.. ⊢ Ti WF
  --------------------------------------------------
  R ⊢ for<r..> fn(T1..Tn) -> T0 WF

Basically, this rule adds the bound

Note that fn types do not require that T0..Tn be Sized. This is intentional. The limitation that only sized values can be passed as argument

The object type rule is similar,

WfObject:
  rᵢ = union of implied region bounds from Oi
  ∀i. rᵢ: r
  ∀i. R ⊢ Oi WF
  --------------------------------------------------
  R ⊢ O0..On+r WF

The first two clauses

#![allow(unused)]
fn main() {
trait Foo: 'static { ... }
}

and a trait object like Foo+'x, when we require that 'static:

The next clause

WfObjectFragment:
  ∀i. R, r.. ⊢ Pi
  TraitId is object safe
  --------------------------------------------------
  R ⊢ for<r..> TraitId<P1..Pn>

Note that we don't check the where clauses

WF checking a trait reference

参照

In some contexts, we want to check a trait reference,

WfTraitReference:
  ∀i. R, r.. ⊢ Pi
  C = WhereClauses(Id)      // and the conditions declared on Id must hold...
  R, r0...rn ⊢ [P0..Pn] C   // ...after substituting parameters, of course
  --------------------------------------------------
  R ⊢ for<r..> P0: TraitId<P1..Pn>

The rules are fairly straightforward. The components

Checking conditions

条件

In various

In practical terms,

#![allow(unused)]
fn main() {
struct Iterator<'a, T:'a> { ... }
}

and a function type like for<'a> fn(i: Iterator<'a, T>) then this type is considered

However, if I have a type like

#![allow(unused)]
fn main() {
struct Foo<'a, T:Eq> { .. }
}

and a function type like for<'a> fn(f: Foo<'a, T>), I still must show that T: Eq holds

Implied

暗黙の

bounds

制限する、結び付けられて

Implied

• 'a:'r, where two regions must be related;
• X:'r, where a type parameter
  仮引数
  X outlives a region; or,
• <T as Trait<..>>::Id: 'r, where a projection outlives a region.

Some caution is required around projections when deriving implied

When should we check the WF relation and under what conditions?

Currently the compiler performs WF checking in a somewhat haphazard way: in some cases (such as impls), it omits

Constants/statics. The type of a constant

Struct/enum declarations.

Function items. For function items, the environment

• argument
  引数
  types;
• return type;
• where clauses;
  句、節
• types of local variables.

These WF requirements are imposed at each fn or associated fn definition

Trait impls. In a trait impl, we assume

• Where-clauses declared
  宣言
  on the trait must be WF.
• Associated types must be WF in the trait environment.
  環境
• The types of associated constants
  定数
  must be WF in the trait environment.
  環境
• Associated fns are checked just like regular
  普通の、正規の
  function items, but with the additional
  追加の
  implied
  暗黙の
  bounds
  制限する、結び付けられて
  from the impl signature.
  シグネチャ

Inherent impls. In an inherent impl, we can assume

Trait declarations.

Type aliases.

Several points in the list

Fns being called.

Method calls,

Normalizing associated type references.

Drawbacks

N/A

Alternatives

代わりのもの、選択肢

I'm not aware of any appealing alternatives.

Unresolved questions

Best policy for type aliases.

For trait object type fragments, should we check WF conditions

#![allow(unused)]
fn main() {
trait HashSet<K:Hash>
}

should an object like Box<HashSet<NotHash>> be illegal? It seems like that would be inline with our "best effort" approach to bound

Appendix

The informal explanation glossed over some details. This appendix tries to be a bit more thorough with how it is that we can conclude that a projection outlives 'a if its inputs outlive 'a. To start, let's specify

<P0 as Trait<P1...Pn>>::Id

where P can be a lifetime or type parameter

Then we know that there exists some impl of the form:

#![allow(unused)]
fn main() {
impl<X0..Xn> Trait<Q1..Qn> for Q0 {
    type Id = T;
}
}

Here again, X can be a lifetime or type parameter

Let Θ be a suitable substitution

RFC 447 and #24461 require that a parameter

Recall the rule OutlivesProjectionComponents:

OutlivesProjectionComponents:
  ∀i. R ⊢ Pi: 'a
  --------------------------------------------------
  R ⊢ <P0 as Trait<P1..Pn>>::Id: 'a

We aim to show that ∀i. R ⊢ Pi: 'a implies

1. First, we show that if R ⊢ Pi: 'a, then every "subcomponent" P' of Pi outlives 'a. The idea here is that each variable
   変数、ストレージ
   Xi from the impl will match
   一致する、マッチさせる
   against and extract
   抽出する
   some subcomponent P' of Pi, and we wish to show that the subcomponent P' extracted
   抽出する
   by Xi outlives 'a.
2. Then we will show that the type θ T outlives 'a if, for each of the in-scope parameters
   仮引数
   Xi, Θ Xi: 'a.