Tracking issue for lifetime elision for impl headers (feature impl_header_lifetime_elision)

[aturon]

The lifetime elision RFC included rules for eliding lifetimes in impl headers, but these rules were not included in the implementation.

Mentoring instructions can be found here.

[pnkfelix]

triage: P-low

[nikomatsakis]

See here for a summary of the current status.

[sophiajt]

Should this be P-low since @brson notes it as a critical part of the implementation?

[aturon]

@jonathandturner I think there's some confusion -- @brson was referring to error messages, which I believe at this point are largely as specified (but would be worth checking). This issue, OTOH, is about adding an additional point of elision.

I'm nominating this for lang team discussion -- the RFC for this feature is quite old, and at this point I think we should revisit whether we even want to do it.

[nikomatsakis]

We discussed in the @rust-lang/lang meeting today and decided that there is no reason to expire an RFC just because it's been a while. Basically, the motivation of the RFC still seems fairly relevant. That said, we would expect that if these changes were implemented, they would go through a stabilization period, and so if people felt like they were now bad, we could address that then.

It's worth noting here for the record a few random thoughts of my own. First, I feel like elision has been wonderful except for one case: fn foo(&self) -> Bar where Bar has lifetime parameters (struct Bar<'x>). In this case, I feel like the fact that Bar "extends" the borrow of self is subtle. This becomes worse when there are other named lifetime parameters that appear in the return type, for example fn foo(&self) -> &'a Bar, which would expand to fn foo<'b>(&'b self) -> &'a Foo<'b>. I'd love if we could find some way to lint against harmful patterns and provide a lightweight way to indicate that there are lifetimes in Bar without having to name them.

[djc]

I might be interested in working on this. Can someone outline some steps to get going? What's the perceived complexity factor here? (I have contributed small things before, but no actual compiler work.)

[eddyb]

@djc You might want to start by taking a look at #39265, which stabilized 'static elision in const & static (by removing the special casing it needed for feature-gating), and which touched the new version of the elision system in resolve_lifetime, hopefully the site of most of your changes.

I worry that impl headers would want early-bound lifetime parameters so you'd need to synthetize those in a way that librustc_typeck/collect.rs understands and keeps track of in the impl's ty::Generics.

It still wouldn't be that hard, as impl lifetime/type parameters are never exposed to the user (instead, they're inferred from Self and trait parameters, where applicable), but it's unlike other forms of elision.

[nikomatsakis]

I'm definitely keen on seeing this done. @djc if you want I can try to draw up somewhat more detailed instructions that what @eddyb provided, but let me know.

[djc]

@nikomatsakis that would be quite welcome. I did look at lifetime_resolvers and typeck::collect a little, but a strategy to get started did not jump out at me. One thing I was wondering is if I could somehow print HIR before and after the pass that should the elision, to give me some way to debug.

[eddyb]

@djc the HIR is not mutated, extra information (associated by NodeIds from the HIR) is collected instead.

[djc]

@nikomatsakis ping, would you still have a chance to draw up more detailed instructions?

[nikomatsakis]

@djc I haven't. :( I'll do some poking about now and see how easy I think it would be.

[nikomatsakis]

@aturon @wycats

I have been looking into how to implicit impl elision, and I wanted to clarify one part of the RFC. The text says this (emphasis mine):

For impl headers, input refers to the lifetimes appears in the type receiving the impl, while output refers to the trait, if any. So impl<'a> Foo<'a> has 'a in input position, while impl<'a, 'b, 'c> SomeTrait<'b, 'c> for Foo<'a, 'c> has 'a in input position, 'b in output position, and 'c in both input and output positions.

In general, though, there can be more than one type in an impl header, and the text doesn't seem to clearly address this case. (Neither do the examples.) This is how I would interpret the rules:

• Input types are considered inputs (this includes Self, which is explicit in the text, but also other input types).
• Lifetime parameters on the trait are considered outputs (this makes sense even though they are input parameters to the trait resolution process, as they cannot affect which impl is chosen, and in practice they are basically always functional dependencies of the input types anyhow).

One question is whether to extend the "self is privileged" rule to impls. I'd be inclined to say no, even though I think it might make sense, in the absence of data, simply because it's the conservative choice. However, there is an even more conservative choice, which is to require explicit lifetimes everywhere but Self. I don't see much of a point to that.

Therefore:

impl Eq<&str> for &str // becomes:
impl<'a, 'b> Eq<&'a str> for &'b str

trait Foo<'x, T> { ... }

impl Foo<&str> for &str // error: output position `'x` has multiple possibilities

impl Foo<u8> for &str // becomes:
impl<'a> Foo<'a, u8> for &'a str

impl Foo<&str> for u8 // becomes:
impl<'a> Foo<'a, &'a str> for u8

[nikomatsakis]

Another question: in the "Elision 2.0 RFC" draft that @solson and I have been (slowly) working on, we are planning to deprecate "implicit" lifetimes (e.g., Ref<T> being expanded to Ref<'a ,T>), at least in some scenarios (I rather liked @aturon's proposal of deprecating an implicit lifetime only if it is used in an output position as well, and thus encouraging one to signal it by writing Ref<', T> in that case, though I also might not object to just deprecating them altogether). Should we omit such cases from impl headers and just focus on &T? Or implement the rules more evenly and then deprecate evenly?

[nikomatsakis]

OK @djc, so I did some research into how to implement this. As you can see from my previous comment, there are some vaguaries in the RFC text that I think we should clear up, but it doesn't really affect the implementation very much. The good news is that the heroic @eddyb has done some nice refactoring here that I think makes this job much nicer than it once was.

A quick outline of how the various bits in the compiler work that are relevant here. First off, let's take two example impls to show what I'm talking about:

impl Foo for &str { .. }
impl Foo for Ref<u8> { .. } // Ref is defined as `struct Ref<'a, T>`

OK, so, the general flow of the compiler is like this:

• After we parse, we have an AST (syntax::ast), but we only use that for macro expansion and (some parts of) name resolution.
• The AST is lowered to HIR (rustc::hir) by the code in rustc::hir::lowering. The HIR is the compiler's main abstract-syntax-tree-like representation (HIR stands for "high-level IR").
• As we commence this lowering process, we already have most paths fully resolved -- the only exception is associated types like T::Item or <T as Iterator>::Item> (but in the latter case, we would have resolved the path Iterator). In our second example, that means that we would have a "link" from the path Ref to the definition of the Ref -- this will be important. However, we have not resolved lifetimes. Those are still just strings, basically.
• Then the pass rustc::middle::resolve_lifetime walks the HIR and, for each named lifetime like 'a, as well as the elided lifetimes, figures out which lifetime definition they refer to.
• The results of this lifetime resolution are used by the type-checker's collect pass, which has the job of converting the HIR representation of a type into the compiler's internal representation of a type, rustc::ty::Ty -- among other things. (Note: A lot of the code executed during collect -- and specifically the code around types -- actually lives in astconv.)
• Another part of collect's job is to compute a Generics structure for each type, impl, etc. The Generics
  struct stores the set of parameters (type, lifetime) introduced by the given item.

So, to make impl elision work, we are going to have to modify a little bit of each of these places. In particular, we are going to be inserted new "automatic" lifetime parameters, so those will have to appear in the Generics structure. The types which reference those automatic parameters will need to be correct, though probably we'll achieve that mostly by making sure that the resolve_lifetimes pass links up the lifetimes correctly (we may not need to modify the code for types in astconv at all).

OK, let's dive into a bit more detail. Let's walk through how elided lifetimes work today. In the AST, elided lifetimes are simply not present. So if you check out the enum variant for &ptr, called Rptr, you see that it has an Option for a lifetime. In the case of Ref, they are "even more" elided, in that there will simply be a path with zero lifetime parameters. However, in the HIR, all lifetime parameters are always present. So, the corresponding enum variant in the HIR does not contain an option:

 TyRptr(Lifetime, MutTy),

Similarly, although you can't see this in their definition, paths like Ref<T> where no lifetime was provided will have the elided lifetimes present in the HIR. The way this works is that, during lowering, we insert a sentinel lifetime indicating that the lifetime was elided by the user. For example, here is the code that converts &T types from the AST to the HIR: you can see that if the AST has None for the lifetime, the HIR gets the sentinel value.

This is handy because every hir::Lifetime struct has a unique id. This id will be used by resolve_lifetimes to record, for each hir::Lifetime, what that lifetime actually refers to (this is not done on the AST, like paths, but rather on the HIR). These are stored in a map called the NamedRegionMap, in the defs field. This is a NodeMap, which is a hashmap keyed by NodeId (the type of the id field from Lifetime). The value is a resolve_lifetime::Region struct -- somewhat confusingly, the resolve_lifetime code has its own Region struct (there is another in ty).

OK, let's take a break and walk through one of our examples now. We'll look at the first impl, the one for &str. Actually, we'll look at a variant, with a named lifetime parameter (this is kind of what we want to desugar to):

impl<'a> Foo for &'a str { .. }

What happens to this impl as we proceed through the passes? In the AST, the type of &str would be a Rptr with Some('a) for the lifetime. During lowering, this 'a gets converted into a hir::Lifetime struct with basically the same information. In the resolve-lifetimes code, we will walk down the HIR. As we get to the impl, we will bring the lifetimes declared on it into scope. In this case, that is the lifetime 'a. We map 'a to the resolve_lifetime::Region::Early variant (see the note below about the name "early"). Then later, when resolve_lifetime reaches the type &'a str, it will search these scopes and store the result into the map. This basically just stores the index of this lifetime parameter in the list of generics (in this case, I think it will be 0, as its the only parameter on the impl).

Later on, during collect, we have to create the generics for the impl. This will read the fields from the HIR, iterate over each lifetime in there, and create a RegionParameterDef for each one. This eventually gets stored in the Generics structure.

When we convert the &'a str type into the compiler's internal representation, meanwhile, it will lookup the result from the NamedRegionMap that resolve_lifetime created. It will find the Early variant and create a ty::Region with the given index.

OK, that's all I have time for for now. I haven't actually gotten into how to DO the change, but hopefully this will help you get acquanted with how the relevant code works now and maybe gives you an inkling how we will update it.

[eddyb]

If you treat it like argument elision in rustc::middle::resolve_lifetime, but just slightly different so you can tell between the lifetimes added in an impl header (always "early") and a fn signature (always "late"), then you can use a map (or just traverse the HIR) to add those lifetimes in typeck::collect to ty::Generics.

Most of the code out there shouldn't mind, i.e. it should assume it can't know what ty::Generics looks like for a given HIR without asking for ty::Generics specifically.

[djc]

@nikomatsakis thanks a lot for the detailed explanation. I'll be diving in soon to see if I can make sense of it all.

[nikomatsakis]

@djc I'll try to write up the next few steps soon -- but I figured I'd given you enough to chew on to start. =)

[nikomatsakis]

One more point that I forgot to add. I thought that the elision rules as originally written would require you to sometimes use disjoint names just to force disjointness, which is weird. e.g. you might need to write this:

impl<'a, 'b> PartialEq<&'a Foo> for &'b Foo { }

to permit two references with distinct lifetimes to be used.

[scottmcm]

To add to niko's comment: ...and we want to lint on single-use lifetimes like that.

[rfcbot]

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

[steveklabnik]

What's the current status here? @rfcbot says we're good to go. It seems this is already stable as part of edition 2018. What's left to do?

[Centril]

@steveklabnik this needs to be stabilized by someone and then I think the reference and docs need to be updated.

[steveklabnik]

What does that stabilization effect, given that it’s already stable in 2018? For 2015?

…

On Sep 20, 2018, at 2:09 PM, Mazdak Farrokhzad ***@***.***> wrote: @steveklabnik this needs to be stabilized by someone and then I think the reference and docs need to be updated. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or mute the thread.

[Centril]

@steveklabnik yes, there's no reason AFAIK that this should not be stable in 2015 because there is no breakage.

[steveklabnik]

Great, just trying to understand exactly what's up.

[Centril]

@steveklabnik you and me both ;)

[scottmcm]

I have a PR up for the issue I found with this (#54458); should be good for a stabilization PR.

Edit: Started one at #54778

[scottmcm]

🎉 #54778 stabilized this for 1.31 🎉