Tracking issue for RFC 2093: Infer `T: 'x` outlives requirements on structs

[aturon]

This is a tracking issue for the RFC "Infer T: 'x outlives requirements on structs " (rust-lang/rfcs#2093).

Current status:

Implemented and we have decided to stabilize. We still need someone to make the stabilization PR! Mentoring instructions here:

https://github.com/rust-lang/rust/issue_comments#issuecomment-411781121

Until then, you can use this by adding #![feature(infer_outlives_requirements)] to your crate.

Steps:

• Implement the RFC (mentoring instructions here)
• Adjust documentation (see instructions on forge)
• Stabilization PR (see instructions on forge)

Unresolved questions:

The interaction with 'static remains a bit unclear. For example, do we want to infer a T: 'static requirement on the type parameter T here? The code currently will do so, arguably leading to confusing errors.

#![feature(infer_outlives_requirements)]

struct Foo<T> { t: &'static T }

fn main() {
    let x = 3;
    let _ = Foo { t: &x };
}

[nikomatsakis]

Mentoring instructions

In the compiler, when we want to know what predicates are defined on something (e.g., a struct), we do that via the predicates_of query. Right now, this is implemented by this code in librusc_typeck. This code basically reads the HIR and produces exactly the results found there.

In terms of how to fit this inference into the compiler pipeline, then, I think we want to ensure that predicates_of includes these inferred predicates. To do that, we can redefine predicates_of in terms of two new queries, explicit_predicates_of and inferred_outlives_of -- basically, predicates_of would be the union of the two:

predicates_of(D) = explicit_predicates_of(D) + inferred_outlives_of(D)

explicit_predicates_of would be exactly the same as predicates_of is today (and only defined for local crates). It just returns the predicates the user typed. inferred_outlives_of, in contrast, will include the predicates that we are going to infer.

The very first PR, then, could be to introduce the explicit_predicates_of query and to make predicates_of just redirect to it (later, we will add inferred_outlives_of). This makes sense because we're going to need explicit_predicates_of when defining inferred_outlives_of.

Now we have to figure out how to implemented inferred_outlives_of. I think the basic structure here is going to be similar to how variance inference is setup. In terms of queries, variance inference is defined by two queries:

• crate_variances -- returns a map containing the variance for every item in the crate
• variances_of -- just selects an item of this map.

The crate_variances query is intended as an implementation detail of variance -- end-users should use variances_of for a particular item.

The reason for this particular setup is that we can't infer the variances for a single item in isolation; the variance for an item X depends on the contents of the struct, and there may be cycles. Since cycles are generally forbidden between queries, we instead compute the variances for ALL structs in the crate, and then use individual queries to extract the result.

So, for inferred_outlives_of, we will basically create a new query, probably living alongside variance in librustc_typeck, let's call it inferred_outlives_of. This query will defer to a crate-wide query inferred_outlives_crate (we should probably have named crate_variances as variances_crate...). Since we only infer predicates for struts, inferred_outlives_of can just return the empty set for any def-id that is not a struct.

This crate-wide computation will work much as it is described in the RFC -- there will be a set of constraints being inferred for each struct S, what the RFC calls A[S]. These sets will be sets of Predicate<'tcx> values. We will initialize them by filtering the explicit_predicates_of each struct to only include those of type TypeOutlives or RegionOutlives.

Next, we can walk the types of the fields declared in each struct. These can be obtained by invoking type_of(def_id) where def_id is the DefId of the struct. This should give back a type of the TyAdt variant; from this, you can extract the types of the fields. Something like this code from variance should give you the idea. For each field that references another struct S2, we need to create a link between those types and ensure that their implied predicates are a superset.

Once this is done, we should have some kind of inferred set of obligations for each struct. I think it'd be good to setup a unit-testing mechanism for this similar to the one we use for variance. Basically, some custom code that looks for a #[rustc_inferred_outlives] annotation and, when found, dumps out a "compilation error" that includes the results. This lets us write unit tests like this one, where we just check the result of this query.

So, in terms of first steps, these are good PRs to open:

• Check predicates_of to be implemented in terms of a subsidiary predicate explicit_predicates_of.
• Introduce inferred_outlives predicate and unit-testing mechanism. Initially, the predicate can always return an empty set of predicates, but we can add some tests nonetheless; they'll just initially show an empty result for the predicate.
• Implement the predicate inference, fix the test, add more tests.

[toidiu]

I would like to work on this!