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!

[nikomatsakis]

@toidiu hey, just checking in! I just r+'d that first PR, wondering if you'd had any time to mess around with the next few steps?

[toidiu]

@nikomatsakis hey sry for the slow progress. I have have mainly been trying to wrap my head around all the different concepts and the repo structure. Have read the mentoring guide and rfc a few times now I am hoping to make some initial pr's early this week.

[nikomatsakis]

Pseudocode of how the inference wants to work, I think:

// Compute a map from each struct/enum/union S to the **explicit**
// outlives predicates (`T: 'a`, `'a: 'b`) that the user wrote.
// Typically there won't be many of these, except in older code where
// they were mandatory. Nonetheless, we have to ensure that every such
// predicate is satisfied, so they form a kind of base set of requirements
// for the type.
let mut explicit_outlives_predicates = map();
for def_id in all_types() {
    let explicit_predicates = tcx.explicit_predicates(def_id);
    let filtered_predicates = explicit_predicates.iter().filter_map(is_outlives_predicate).collect();
    explicit_outlives_predicates.insert(
        def_id,
        filtered_predicates);
}

// Create the sets of inferred predicates for each type. These sets
// are initially empty but will grow during the inference step.
let mut inferred_outlives_predicates = map();
for def_id in all_types() {
    inferred_outlives_predicates.insert(def_id, empty_set());
}

// Now comes the inference part. We iterate over each type and figure out,
// for each of its fields, what outlives predicates are needed to make that field's
// type well-formed. Those get added to the `inferred_outlives_predicates` set
// for that type.
let mut changed = true;
while changed {
    changed = false;
    for def_id in all_types() {
        for field_ty in the HIR type definition {
            let required_predicates = required_predicates_for_type_to_be_wf(field_ty);
            inferred_outlives_predicates.extend(required_predicates);
            if new predicates were added { changed = true; }
        }
    }
}

// When we are done, `inferred_outlives_predicates` is the resulting map.

[Yoric]

@toidiu Are you still working on this? If not, I'd be interested in taking a jab at this issue.

[toidiu]

@Yoric yea still making progress and iterating on one PR so as not to queue up bors

[rfcbot]

The final comment period, with a disposition to merge, as per the review above, is now complete.

[nikomatsakis]

Let's get this stabilized, then!

There are instructions for how to do so here:

https://forge.rust-lang.org/stabilization-guide.html

@toidiu — you would be up for that? You've seen this thing through from start to finish thus far!

[nikomatsakis]

I think we should also split off a new issue for the 'static feature gate...

[toidiu]

@nikomatsakis yep would be glad to :)

[pnkfelix]

visiting for triage. PR #53793 is meant to resolve this.

[pnkfelix]

visiting for triage. #53793 landed. closing as fixed.

[nikomatsakis]

Created #54185 to track the 'static question

[nikomatsakis]

#52042 already exists to track an idiom lint

[pnkfelix]

#54185 (comment) ended the question about whether to special-case 'static ; PR #97875 removed #![feature(infer_static_outlives_requirements)].