In-band lifetimes: Lint against single-use lifetime names

[nikomatsakis]

Once support for '_ lands in #44691, the next step for #44524 is to implement a lint that warns against "single use" lifetime names.

Current status

The lint is partially implemented but needs to be completed. Here is a checklist:

• Issue warnings at the right times; this gist provides a comprehensive test case.
• For each warning, issue a suggested fix:
  • For a single-use lifetime 'a appearing in &'a T, suggest &T
  • For a single-use lifetime 'a appearing in any other place, suggest '_
  • One challenge: the binder must be removed too
    • cc @estebank -- is it possible to give suggested fixes that make changes to multiple spots at once? I guess that might just be multiple suggestions?
• We'll know this is really done when we can enable by default in rustc crates and apply rustfix with suggestions

Older Background

The idea is that an explicit name like 'a should only be used (at least in a function or impl) to link together two things. Otherwise, you should just use '_ to indicate that the lifetime is not linked to anything.

Until #15872 is closed, we should only lint for single-use lifetime names that are bound in functions. Once #15872 is closed, we can also lint against those found in impl headers.

We can detect cases where a lint is valid by modifying the resolve_lifetimes code:

• This code basically walks over the HIR and resolves all lifetime names.
• It maintains a stack of scopes indicating what names are valid.
• The function with() is used to push new scopes on the stack. It is also given a closure which will execute with the new name bindings in scope.
  • with() gets called for impls and other kinds of items from here; for methods and functions in particular it is called from visit_early_late).
• Once a name is in scope, resolve_lifetime_ref() is called to resolve an actual reference to a named lifetime.
  • This could be used, for example, to update some information in the Scope, e.g. counting how many times a particular lifetime was referenced.
• Then, before with() returns, we could scan the lifetimes and check for those that were only referenced 1 time (or 0 times...) and issue a lint warning.

(There are some directions for how to add a lint under the header "Issuing future compatibility warnings" in the rustc-bug-fix-procedure page on forge -- we can skip the "future compatibility" parts here.)

[cramertj]

we should only lint for single-use lifetime names that are bound in functions

Also, I believe, only for lifetime names that appear in argument position. Currently we require explicitly binding output-only lifetimes with a name:

fn bar<'a>() -> &'a u8 { &5 } // OK
fn bar() -> &'_ u8 { &5 } // ERROR: missing lifetime specifier

[nikomatsakis]

@cramertj Hmm. I would consider the proper way to declare bar() to probably be fn bar() -> &'static u8, really, though there are subtleties involved in rare cases (e.g., around invariance).

[cramertj]

@nikomatsakis Yes, 'static is the right thing to use. I wanted to point out that we shouldn't recommend '_ here, as it won't work.

[gaurikholkar]

Is this up for grabs?

[cramertj]

@gaurikholkar Go for it!

[gaurikholkar]

Will start working on it

[nikomatsakis]

@gaurikholkar hey, just checking in! How's it going? Any blockers?

[nikomatsakis]

Some examples:

fn foo<'x>(_: &'x u32) { }

This should lint against 'x and suggest &u32 instead.

struct Foo<'a> { x: &'a u32 }
fn foo<'x>(_: Foo<'x>) { }

This should lint against 'x and suggest Foo<'_> instead.

struct Foo<'a, 'b> { f: &'a &'b u32 }
fn foo<'x, 'y>(foo: Foo<'x, 'y>) -> &'x u32 { foo.f }

This should lint against 'y and suggest Foo<'x, '_> instead.

struct Foo<'a, 'b> { f: &'a &'b u32 }
fn foo<'x, 'y>(foo: Foo<'x, 'y>) -> &'y u32 { foo.f }

This should lint against 'x and suggest Foo<'_, 'y> instead.

fn foo<'x>() -> &'x u32 { &22 }

This should not lint, because 'x appears only in the return type.

trait Trait<'a> { }
impl<'a, T> Trait<'a> for T { }

fn foo<'x, T>(t: T)
where T: Trait<'x>
{ 
}

fn main() { 
  foo(22);
}

This should not lint, because at present '_ does not work in that position (which we should fix).

[nikomatsakis]

OK, let's start with this specific test:

fn deref<'x>(v: &'x u32) -> u32 {
    *v
}

fn main() { }

When we are done, we want to issue a warning, probably like this:

fn deref<'x>(v: &'x u32) -> u32 {
//       ^^ lifetime name `'x` only used once
    *v
}

fn main() { }

In this case, the one use of 'x is as the operand to a &-type, so I think we don't have to say much more than that. If the one use of 'x were in a struct, we might want to have a hint indicating that it can be replaced with '_, but let's leave that stuff to future work.

The first thing we want to do then is to figure out how many times each name is used and where. Now, accounting around lifetimes (e.g., early-bound, late-bound, etc) can get kind of complicated, but luckily we can ignore most of that crap for our purposes. I imagine we would want to add to the LifetimeContext struct a new field:

lifetime_uses: DefIdMap<LifetimeUseSet<'tcx>

where a LifetimeUseSet<'tcx> is defined like:

enum LifetimeUseSet<'tcx> {
    One(&'tcx hir::Lifetime),
    Many,
}

We don't really need to track more detail than that -- once there are many uses of a lifetime, we don't want to warn about it anymore, so we don't need to track them. Now, when we are resolving a lifetime in resolve_lifetime_ref, we want to update these lifetime use sets. Actually, I think the place to add code is the insert_lifetime method, which records a successful lifetime resolution:

rust/src/librustc/middle/resolve_lifetime.rs

Lines 1516 to 1518 in 3cf28f3

	fn insert_lifetime(&mut self,
	lifetime_ref: &hir::Lifetime,
	def: Region) {

Here, we want to match on the def, which is of the type Region. We want to do something like:

match def {
    LateBoundAnon(..) | Static => {
        // These are anonymous lifetimes or lifetimes that are not declared.
    }

    Free(_, def_id) | LateBound(_, def_id) | EarlyBound(_, def_id) => {
        // A lifetime declared by the user.
        if !self.lifetime_uses.contains_key(&def_id) {
            self.lifetime_uses.insert(def_id, LifetimeUseSet::One(lifetime_ref));
        } else {
            self.lifetime_uses.insert(def_id, LifetimeUseSet::Many);
        }
    }
}

Now we have a record of where each lifetime def was used. The next step will be going over the set of lifetime names defined and warning if they are LifetimeUseSet::One. I'm going to stop here, but we can talk about the best way to do that later.

[gaurikholkar]

I've been in touch with @nikomatsakis over this. The current status is: I've followed the instructions he has given above and written code for the same locally.

[nikomatsakis]

So, if we follow the steps above, we wind up with a map from the def-id of each LifetimeDef to either zero (no key), one, or many uses of it. I think maybe the easiest thing way to handle things is to do a second walk of the krate, just looking for lifetime defs, and issuing the warnings. Originally I had thought we could do them as we walk the first time, but now that seems like it would just clutter the code unnecessary.

This is the main function for resolve_lifetime:

https://github.com/rust-lang/rust/blob/master/src/librustc/middle/resolve_lifetime.rs#L259-L285

I am imagining that we can basically write a second visitor, struct LifetimeSingleUseWarnVisitor or something. Like LintContext, it will implement the visitor trait and return All for its nested_visitor_map:

https://github.com/rust-lang/rust/blob/master/src/librustc/middle/resolve_lifetime.rs#L287-L290

It would only implement one method, though, visit_lifetime_def:

fn visit_lifetime_def(&mut self, lifetime_def: &hir::LifetimeDef) {
    let def_id = self.tcx.hir.as_local_def_id(lifetime_def.id);
    ...
}

In there, it will check if the map contains def_id. If not, it can issue a warning "lifetime never used". If so, and it contains One, it will issue a warning "lifetime used only once". Otherwise, no warning. (Issuing a warning is done by calling add_lint, you can grep around for example.)

OK, this is a not quite right -- we're going to eventually want to be a bit more selective, since it will depend whether that use is one that could be elided or replaced with '_. But let's start there and then narrow it down.

[nikomatsakis]

Actually I take that back. Don't use a visitor. Just iterate over the map we built and look things up in the HIR map. For example, given the DefId of some lifetime def, we can look up its span in the HIR map by doing

let node_id = hir.as_local_node_id(def_id).unwrap(); // guarnateed to be local
let hir_lifetime: &hir::Lifetime = match hir.get(node_id) {
    hir_map::NodeLifetime(l) => l,
    _ => bug!()
};
let span = hir_lifetime.span;

[nikomatsakis]

Well, that won't allow you to catch lifetimes used zero times. To do that, we either need a separate visitor, or visit the map during with and store a "zero times" entry (extending the enum), or to visit the entries at the end of with and issue warnings.

[gaurikholkar]

Track the progress here

[gaurikholkar]

  |
3 | fn deref<'x>(v: &'x u32) -> u32 {
  |          ^^
  |
note: lint level defined here
 --> /home/user/mp/foo.rs:1:9
  |
1 | #![warn(single_use_lifetime)]
  |         ^^^^^^^^^^^^^^^^^^^

Is what gets generated for now

[gaurikholkar]

@nikomatsakis it's compile-fail tests that are failing now

[nikomatsakis]

I started trying to record all places where this lint might be needed and document their expected behavior. This is not done, but I have to go, so I'm saving my status here for now. My goal is to make a checklist and try to mentor the remaining improvements.

File can be found in this gist.

[nikomatsakis]

Here is an updated check-list of the overall goals:

moved to issue header

[gaurikholkar]

Well, that won't allow you to catch lifetimes used zero times

This isn't implemented either

[nikomatsakis]

Ah, good point. I was wondering if we might want to actually handle the "multiple edits" this way -- that is, we could first suggest removing the 'a from &'a u32, then suggest removing an unused lifetime.

[nikomatsakis]

Kind of annoying to have to run rustfix to a fixed point though =)

[nikomatsakis]

@gaurikholkar I updated the list of warnings

[estebank]

is it possible to give suggested fixes that make changes to multiple spots at once? I guess that might just be multiple suggestions?

The suggestions machinery is capable of having multiple suggestions at one time, and each suggestions being different Spans, but there's no method access these features, which means it hasn't been thoroughly tested.

---

EDIT

The support to suggest multiple substitutions at once was added in #50943, and a slight tweak to the presentation will be added in #50987.

[nikomatsakis]

Issuing warnings at the right times

This is the first step for the mentoring instructions. The lint as is is partially implemented, but it often fires at the wrong times.

Step one: Add the tests. I've created a fairly comprehensive set of test cases in this gist. The first step then would be to add these tests into your branch, by doing something like the following. This will put all of the tests into src/test/ui/in-band-lifetimes/single-use-lint.

> cd src/test/ui/in-band-lifetimes
> mkdir single-use-lint
> git clone git@gist.github.com:f13da812c97b8094a9566ca9b3d9677d.git tmp
> mv tmp/*rs single-use-lint
> rm -rf tmp

(Unfortunately, I forgot when making those tests that we already had a fair number of tests with names like src/test/ui/in-band-lifetimes/single_use_lifetimes-*rs. You might just want to remove those tests, or else compare them to the new ones.)

We can then run all the tests by running this command from the main directory:

> ./x.py test --stage 1 -i src/test/ui --test-args single-use-lint

That should run just the new tests and nothing else. You should see various failures. (You can learn more about rustc's test suite here, in the rustc-guide; these test are ui tests.)

Step two: Examine existing code. The way that the current lint works is in the resolve_lifetime pass. Basically, for each lifetime that is declared, we track a LifetimeUseSet indicating how many times it is used:

rust/src/librustc/middle/resolve_lifetime.rs

Lines 61 to 66 in c19264f

	// This counts the no of times a lifetime is used
	#[derive(Clone, Copy, Debug)]
	pub enum LifetimeUseSet<'tcx> {
	One(&'tcx hir::Lifetime),
	Many,
	}

These are kept in a map, indexed by the DefId from the lifetime definition:

rust/src/librustc/middle/resolve_lifetime.rs

Line 258 in c19264f

lifetime_uses: DefIdMap<LifetimeUseSet<'tcx>>,

This map is populated in the insert_lifetime routine, which is what we invoke when we have resolved some reference to a lifetime. So e.g. if you have a type &'a u32, this method has the job of recording which lifetime that 'a refers to:

rust/src/librustc/middle/resolve_lifetime.rs

Line 2201 in c19264f

fn insert_lifetime(&mut self, lifetime_ref: &'tcx hir::Lifetime, def: Region) {

Towards the bottom you will see this code, which upgrades the number of times that the reference is used:

rust/src/librustc/middle/resolve_lifetime.rs

Lines 2228 to 2233 in c19264f

	if !self.lifetime_uses.contains_key(&def_id) {
	self.lifetime_uses
	.insert(def_id, LifetimeUseSet::One(lifetime_ref));
	} else {
	self.lifetime_uses.insert(def_id, LifetimeUseSet::Many);
	}

Examine the test failures. Looking at the test failures, we can group them into two categories:

• Lifetimes that appear in some places should not be warned about, even if they are only used once. For example, using a lifetime name in a struct, or in a return type.
• Lifetimes that are never used are not warned.

Making lifetimes used in particular places issue a warning. I think what we want to do here is to extend the LifetimeContext struct with a new field:

rust/src/librustc/middle/resolve_lifetime.rs

Line 228 in c19264f

struct LifetimeContext<'a, 'tcx: 'a> {

Let's call the flag track_individual_lifetime_uses: bool. The idea is that, when this flag is false, insert_lifetime is not going to track whether a lifetime is used once or many times: if it finds any use, it will treat it as though it is used many times. So we might modify the insert_lifetime code as follows:

if self.track_individual_lifetime_uses && !self.lifetime_uses.contains_key(&def_id) {
    self.lifetime_uses.insert(def_id, LifetimeUseSet::One(lifetime_ref));
} else {
    self.lifetime_uses.insert(def_id, LifetimeUseSet::Many);
}

The basic idea is that this field should be true whenever a single-use lifetime could be replaced with '_. This is actually not true most of the time, so we can initialize the field to false. We can then modify the with function, which is the function that adds a new lifetime scope, to update the field:

rust/src/librustc/middle/resolve_lifetime.rs

Lines 1247 to 1249 in c19264f

	fn with<F>(&mut self, wrap_scope: Scope, f: F)
	where
	F: for<'b> FnOnce(ScopeRef, &mut LifetimeContext<'b, 'tcx>),

with should take a new argument (track_lifetime_uses: bool); it should save the old value of the flag, modify it, and then restore it before returning.

Usually, we will want to pass false as the value of this flag, but there are some exceptions. For example, when checking fn arguments:

rust/src/librustc/middle/resolve_lifetime.rs

Lines 1627 to 1637 in c19264f

	self.with(arg_scope, |_, this| {
	for input in inputs {
	this.visit_ty(input);
	}
	match *this.scope {
	Scope::Elision { ref elide, .. } => {
	arg_elide = elide.clone();
	}
	_ => bug!(),
	}
	});

and function bodies:

rust/src/librustc/middle/resolve_lifetime.rs

Lines 451 to 466 in c19264f

	fn visit_nested_body(&mut self, body: hir::BodyId) {
	// Each body has their own set of labels, save labels.
	let saved = replace(&mut self.labels_in_fn, vec![]);
	let body = self.tcx.hir.body(body);
	extract_labels(self, body);
	self.with(
	Scope::Body {
	id: body.id(),
	s: self.scope,
	},
	|_, this| {
	this.visit_body(body);
	},
	);
	replace(&mut self.labels_in_fn, saved);
	}

Anyway, that should be the rough idea. We'll have to see if it starts to issue warnings at strange times!

Making lifetimes that are never used issue a warning. Warnings are actually issued in this loop:

rust/src/librustc/middle/resolve_lifetime.rs

Lines 1273 to 1299 in c19264f

	for (def_id, lifetimeuseset) in &this.lifetime_uses {
	match lifetimeuseset {
	&LifetimeUseSet::One(_) => {
	let node_id = this.tcx.hir.as_local_node_id(*def_id).unwrap();
	debug!("node id first={:?}", node_id);
	if let hir::map::NodeLifetime(hir_lifetime) = this.tcx.hir.get(node_id) {
	let span = hir_lifetime.span;
	let id = hir_lifetime.id;
	debug!("id ={:?} span = {:?} hir_lifetime = {:?}",
	node_id,
	span,
	hir_lifetime);
	this.tcx
	.struct_span_lint_node(lint::builtin::SINGLE_USE_LIFETIME,
	id,
	span,
	&format!("lifetime name `{}` only used once",
	hir_lifetime.name.name()))
	.emit();
	}
	}
	_ => {
	debug!("Not one use lifetime");
	}
	}
	}

The problem here is that, if a lifetime is never used, it will never be added to the map, so we never see it to issue a warning! To fix that, we have to keep a separate set of all lifetimes and iterate over that set. Otherwise, we could walk the IR one more time with a separate visitor to find each lifetime definition.

[tamird]

@nikomatsakis thanks for the detailed instructions!

The approach you outline doesn't totally work out, I think. Consider two-uses-in-fn-argument-and-return - we want to permit the lifetime here because it has two uses, but we want to pass false when calling self.with on the output (because lifetimes on the output alone are permitted).

I think we need to always populate self. lifetime_uses but only check it when track_lifetime_uses is true. What do you think?

Other than that, to do the last part (finding lifetimes with zero uses): where would you populate the set of lifetimes?

[tamird]

Also, a few of the tests are incoherent:

• one-use-in-inherent-method-argument: the comment says "DO NOT warn" and the test is missing the "run-pass" annotation, but various expected errors are included.
• one-use-in-inherent-method-return: same.
• one-use-in-trait-method-argument: same (does have run-pass, though).
• two-uses-in-inherent-method-argument-and-return: same (does have run-pass, though).

[nikomatsakis]

@tamird

Sorry I missed those comments!

Regarding the incoherent tests:

• one-use-in-inherent-method-argument: I believe the comment is wrong. We should warn now, as you could write impl Foo<'_>.
• one-use-in-inherent-method-return: I think the impl should be changed to impl Foo<'_>, but no error is expected.
• one-use-in-trait-method-argument: here a warning IS expected, but for 'g, not 'f
• two-uses-in-inherent-method-argument-and-return: should be changed I think to impl Foo<'_>, and then no warnings would be expected

[nikomatsakis]

@tamird

The approach you outline doesn't totally work out, I think

Regarding this... I think actually that the two-uses-in-fn-argument-and-return test:

fn c<'a>(x: &'a u32) -> &'a u32 { // OK: used twice
    &22
}

is ok for two independent reasons: first, because the lifetime is used twice, but also because it is used in the return type. So it would be ok to invoke with with false (while visiting the return type). Hence tests like one-use-in-inherent-method-return still do not warn.

Put another way, I do not yet see the problem. =)

Other than that, to do the last part (finding lifetimes with zero uses): where would you populate the set of lifetimes?

Hmm. I was thinking about this later. Keeping a set of "all lifetimes" doesn't feel right to me. In fact, the point where we iterate over the lifetimes in order to issue warnings is precisely the point where a set of declared lifetimes are going out of scope:

rust/src/librustc/middle/resolve_lifetime.rs

Lines 1273 to 1299 in c19264f

	for (def_id, lifetimeuseset) in &this.lifetime_uses {
	match lifetimeuseset {
	&LifetimeUseSet::One(_) => {
	let node_id = this.tcx.hir.as_local_node_id(*def_id).unwrap();
	debug!("node id first={:?}", node_id);
	if let hir::map::NodeLifetime(hir_lifetime) = this.tcx.hir.get(node_id) {
	let span = hir_lifetime.span;
	let id = hir_lifetime.id;
	debug!("id ={:?} span = {:?} hir_lifetime = {:?}",
	node_id,
	span,
	hir_lifetime);
	this.tcx
	.struct_span_lint_node(lint::builtin::SINGLE_USE_LIFETIME,
	id,
	span,
	&format!("lifetime name `{}` only used once",
	hir_lifetime.name.name()))
	.emit();
	}
	}
	_ => {
	debug!("Not one use lifetime");
	}
	}
	}

That is, the purpose of the with function is to bring new lifetimes into scope. The lifetimes are found on the scope parameter, which is of type Scope<'a>:

rust/src/librustc/middle/resolve_lifetime.rs

Lines 261 to 315 in c19264f

	#[derive(Debug)]
	enum Scope<'a> {
	/// Declares lifetimes, and each can be early-bound or late-bound.
	/// The `DebruijnIndex` of late-bound lifetimes starts at `1` and
	/// it should be shifted by the number of `Binder`s in between the
	/// declaration `Binder` and the location it's referenced from.
	Binder {
	lifetimes: FxHashMap<hir::LifetimeName, Region>,
	/// if we extend this scope with another scope, what is the next index
	/// we should use for an early-bound region?
	next_early_index: u32,
	/// Whether or not this binder would serve as the parent
	/// binder for abstract types introduced within. For example:
	///
	/// fn foo<'a>() -> impl for<'b> Trait<Item = impl Trait2<'a>>
	///
	/// Here, the abstract types we create for the `impl Trait`
	/// and `impl Trait2` references will both have the `foo` item
	/// as their parent. When we get to `impl Trait2`, we find
	/// that it is nested within the `for<>` binder -- this flag
	/// allows us to skip that when looking for the parent binder
	/// of the resulting abstract type.
	abstract_type_parent: bool,
	s: ScopeRef<'a>,
	},
	/// Lifetimes introduced by a fn are scoped to the call-site for that fn,
	/// if this is a fn body, otherwise the original definitions are used.
	/// Unspecified lifetimes are inferred, unless an elision scope is nested,
	/// e.g. `(&T, fn(&T) -> &T);` becomes `(&'_ T, for<'a> fn(&'a T) -> &'a T)`.
	Body {
	id: hir::BodyId,
	s: ScopeRef<'a>,
	},
	/// A scope which either determines unspecified lifetimes or errors
	/// on them (e.g. due to ambiguity). For more details, see `Elide`.
	Elision {
	elide: Elide,
	s: ScopeRef<'a>,
	},
	/// Use a specific lifetime (if `Some`) or leave it unset (to be
	/// inferred in a function body or potentially error outside one),
	/// for the default choice of lifetime in a trait object type.
	ObjectLifetimeDefault {
	lifetime: Option<Region>,
	s: ScopeRef<'a>,
	},
	Root,
	}

we could iterate over all the lifetimes that were declared in Scope. We basically only care about the case where Scope is a Binder, in which case we can iterate over the lifetimes map:

rust/src/librustc/middle/resolve_lifetime.rs

Line 268 in c19264f

lifetimes: FxHashMap<hir::LifetimeName, Region>,

For each Region value found within, we can extract a DefId (look for the /* lifetime_decl */ comments):

rust/src/librustc/middle/resolve_lifetime.rs

Lines 68 to 83 in c19264f

	#[derive(Clone, Copy, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable, Debug)]
	pub enum Region {
	Static,
	EarlyBound(
	/* index */ u32,
	/* lifetime decl */ DefId,
	LifetimeDefOrigin,
	),
	LateBound(
	ty::DebruijnIndex,
	/* lifetime decl */ DefId,
	LifetimeDefOrigin,
	),
	LateBoundAnon(ty::DebruijnIndex, /* anon index */ u32),
	Free(DefId, /* lifetime decl */ DefId),
	}

then we can lookup that DefId the lifetime_uses map. If it is not present, that should be zero uses.

[nikomatsakis]

@tamird -- do you think you are going to try and tackle this issue? That would be great! (If not, though, let me know so I can find someone else; I'd like to see this get done.)

[tamird]

@nikomatsakis yep, I'm looking at this. Is there any reason to keep lifetime_uses? it seems cleaner to combine the usage information into the binder's lifetimes map.

[nikomatsakis]

@tamird

Is there any reason to keep lifetime_uses?

If you think you see a cleaner way, go for it!

[nikomatsakis]

@tamird btw, just checking -- how goes? I was away last week for PTO

[nikomatsakis]

ping @tamird -- not trying to bug ya', just want to know if you're still working on this. I'm doing my weekly sweep and trying to figure out what I should do to ensure that this moves forward. It's .. mildly high priority, mostly because we'd like to encourage people to try out the in-band lifetimes feature, and for them to do that effectively, this lint ought to be a big help...

[nikomatsakis]

First PR: #50440

(I checked with @tamird and they would not be able to get to this for some time yet)

[joshtriplett]

Given that the 2018 edition preview included in-band lifetimes, it seems like we need to have this lint available for either the next preview or the 2018 edition stable release.

[scottmcm]

Even without in-band lifetimes, I think this is an important idiom lint, so I've added it to an edition milestone to get eyes on it. Edition folks: please move or remove if you think otherwise.