NLL should identify and respect the lifetime annotations that the user wrote

[shepmaster]

We have made some progress on this issue.

Here's a list of everywhere within function bodies where we annotate types, with check boxes on the ones that are currently getting checked by the MIR-borrowck / NLL.

• Let bindings
  • Simple local variable declarations, eg. let x: u32 = 3;
  • More complicated let bindings. eg. let (x, y): (u32, u32) = (33, 54);
    • support ascription for patterns in NLL #53873 made these mostly work, but there are some edge cases where we still have problems. See the FIXME in the patterns.rs UI test.
    • remainder is broken out into handle user type annotations in NLL for complex patterns #54570
  • "Ignored" bindings, eg. let _: Foo<'long> = c_is_short_oops; (support ascription for patterns in NLL #53873)
  • Simple bindings with no initializer, e.g., let x: T; (support ascription for patterns in NLL #53873)
  • Complex bindings with no initializer, e.g., let (x, y): (u32, u32);
    • broken out into handle user type annotations in NLL for complex patterns #54570
  • ref bindings: e.g. let ref x: u32 = 3;, broken out into handle user type annotations in NLL for ref bindings #55401
• Turbofish
  • Function calls. eg. "2048".parse::<u32>() -- MIR: support user-given type annotations on fns, structs, and enums #53225
  • Fully qualified paths. eg. <T as Trait<_>>::method -- MIR: support user-given type annotations on fns, structs, and enums #53225
  • Fully qualified paths. eg. <_ as Trait<T>>::method -- MIR: support user-given type annotations on fns, structs, and enums #53225
  • Fully qualified paths. eg. <_ as Trait<_>>::method<T> -- MIR: support user-given type annotations on fns, structs, and enums #53225
  • Multi-segment paths. e.g. Foo::<X>::method -- broken out into nll should respect lifetime annotations from multi-segment paths #54574
  • Value references. eg. let x = foo::<...>; -- MIR: support user-given type annotations on fns, structs, and enums #53225
  • Struct names. eg. let x = SomeStruct::<'static> { field: u32 }; -- MIR: support user-given type annotations on fns, structs, and enums #53225
  • Associated constants in expressions: <T as Foo>::BAR ? (broken out to nll: respect user type annotations with constants in expressions #54571)
  • Associated constants in patterns: <T as Foo>::BAR ? (nll: respect user type annotations with constants in patterns #55511)
  • Lifetimes in patterns: let A::<'static>(r) = ... ? -- broken out into nll should respect lifetime annotations from patterns #54573
  • Calls to enum variants / struct ctors: Enum::Variant::<...>(...) -- MIR: support user-given type annotations on fns, structs, and enums #53225
  • Reference to nullary structs / variants: None::<&'static u32> -- MIR: support user-given type annotations on fns, structs, and enums #53225
• Casts: x as T (broken out into NLL should respect lifetimes in as expressions #54332)
• Type ascription: x: &'static u32 (broken out into nll should preserve user types in type ascription #54331)
• Method call disambiguation. eg. <Type as Trait>::method(args); -- MIR: support user-given type annotations on fns, structs, and enums #53225
• Lifetimes defined but not used, this currently only occurs in the yield-subtype.rs test but that will also need resolved.
• Normalization code is probably wrong (the user types need, I suspect, to be normalized? Not sure, have to look.)

(We should update this list as we think of more.)

Original bug report follows:

---

This code compiles with 1.24.0-nightly (2018-01-03 0a3761e):

#![feature(nll)]

fn main() {
    let vec: Vec<&'static String> = vec![&String::new()];

    // fn only_static(_: Vec<&'static String>) {}
    // only_static(vec);
}

This is confusing as the Vec almost certainly cannot contain a reference of a 'static lifetime. If you uncomment the call to only_static, you get the expected error that the String does not live long enough.

@nikomatsakis said:

NLL currently ignores hand-written type annotations, in particular, those that appear in local variables.

[nikomatsakis]

I'm tagging this with E-hard because @pnkfelix and I established that as the "have to figure out how to do this" convention. That said, I don't know that it's that hard. My rough plan was something like this:

• Extend HAIR/MIR with some sort of extra operations, that assert equality between types.
  • The region renumbering code would know that the types in such operations come from the user, and should not be renumbered.
  • Example: ASSERT_HAS_TY<T>(_1) would assert that the variable _1 has the given type T
  • We also have to handle foo::<T>() style annotations though
• The HIR -> HAIR lowering would insert these operations when there are explicit Ty nodes
• The HAIR -> MIR would produce ASSERT.
• Similar strategy could be used for casts and things.

However, it might also be best to have some other way to indicate which types are from user -- for example, maybe instead of a Ty, MIR could embed a newtype that also carries a boolean whether it was inferred or explicit.

But I sort of prefer to have the "explicit annotations" come from somewhere else, seems easier overall to me.

[nikomatsakis]

cc @Aaron1011 -- btw, since you're on a roll lately, this would be a good one to get done at some point. It'll require a bit of experimentation though. =) Happy to discuss it sometime.

[davidtwco]

I'll tackle this one.

[nikomatsakis]

@davidtwco ok, so I think my prior directions were the right path still. It probably makes sense to tackle different kinds of annotations independently. Let's start with the most basic sort of annotation, that placed on local variables:

let x: T = ...

To handle this, I think we want to add a new form of MIR statement, a type assertion. That would be done by editing the StorageKind enum:

rust/src/librustc/mir/mod.rs

Line 1163 in 27a046e

pub enum StatementKind<'tcx> {

I would call it something like UserAssertTy. It might look like:

/// Encodes a user's type assertion. These need to be preserved
/// intact so that NLL can respect them. For example:
///
///     let (a, b): (T, U) = y;
///
/// Here, we would insert a `UserAssertTy<(T, U)>(y)` instruction to check
/// that the type of `y` is the right thing.
UserAssertTy(Ty<'tcx>, Local),

We would then want to special-case these statements in the renumberer, so that it skips the embedded type within:

rust/src/librustc_mir/borrow_check/nll/renumber.rs

Lines 121 to 131 in 27a046e

	fn visit_statement(
	&mut self,
	block: BasicBlock,
	statement: &mut Statement<'tcx>,
	location: Location,
	) {
	if let StatementKind::EndRegion(_) = statement.kind {
	statement.kind = StatementKind::Nop;
	}
	self.super_statement(block, statement, location);
	}

But actually I realize there is a bit more complexity here than I initially considered. For example:

let x: &u32 = ...;

needs to be distinguished from

let x: &'static u32 = ...;

The current code doesn't have give you a good way to do that. But let's ignore that complication for a moment -- I have some ideas there for later =). For now, let's just test it with &'static u32 =)

Anyway, once we have this MIR, we also need to generate it. This could presumably mean instrumenting the HAIR, which is the intermediate IR that we use to transition from HIR to MIR.

I think we would want to extend the Let variant in HAIR to include the type annotation (if any):

rust/src/librustc_mir/hair/mod.rs

Lines 87 to 104 in 27a046e

	Let {
	/// scope for variables bound in this let; covers this and
	/// remaining statements in block
	remainder_scope: region::Scope,
	/// scope for the initialization itself; might be used as
	/// lifetime of temporaries
	init_scope: region::Scope,
	/// let <PAT> = ...
	pattern: Pattern<'tcx>,
	/// let pat = <INIT> ...
	initializer: Option<ExprRef<'tcx>>,
	/// the lint level for this let-statement
	lint_level: LintLevel,
	},

These are converted to MIR here:

rust/src/librustc_mir/build/block.rs

Lines 101 to 107 in 27a046e

	StmtKind::Let {
	remainder_scope,
	init_scope,
	pattern,
	initializer,
	lint_level
	} => {

Hmm. As you can see from the comment, I initially thought we would apply the type to the initializer -- this would probably mean threading the user's type to expr_into_pattern here:

rust/src/librustc_mir/build/block.rs

Line 124 in 27a046e

this.expr_into_pattern(block, pattern, init)

So it can add the appropriate assertions. But I guess that wouldn't cover a case like

let (a, b): (T, U);

Maybe we want to do things slightly differently. Mostly I wanted to avoid having the need to "match up" the patterns on the LHS (e.g., the (_, _) pattern) with the type on the RHS, which sounds annoying.

[nikomatsakis]

Oh, I neglected to add that we will want to kill those new statements, presumably through a pass roughly like clean_end_regions. In fact, I think I would want to generalize that existing pass to something like cleanup_post_borrowck.

[davidtwco]

@nikomatsakis I've submitted a PR with what I've got so far: #48482.

[davidtwco]

After chatting with @nikomatsakis on Gitter, here's a list of everywhere within function bodies where we annotate types:

(Update: @pnkfelix moved the list to the issue description to increase its visibility and make it easier to update it consistently.)

[nikomatsakis]

@davidtwco so the problem in #48482 is (I think) precisely that sometimes user-given types may still include inference variables. The example I gave on gitter is a case of that:

fn foo() {
  let x = 22;
  let y: &u32 = &x;
  ...
}

Specifically, the lifetime in the type of y will be an inference variable. That will ultimately get inferred by the lexical region resolver to some specific lifetime, and that is what is recorded in the HIR -- and hence what gets propagated as part of the UserAssertTy. The problem is that this region is (a) going to be some scope, which makes no sense in NLL and (b) not coming from the user, but from inference! We only want to get the things the user gave us. The problem is that these types the user is giving are not complete types, we we can't just use a Ty<'tcx> to represent them.

However, what we can use is a Canonical<'_, Ty<'tcx>>. The canonicalization code was added recently in #48411. The high-level idea is covered in the rustc-guide, but in short canonicalization lets us take a type that includes inference variables and "extract them".

So, I think that the thing we want to be keeping in all of these cases (but let's just keep concentrating on the types in let x: T) is a Canonical<'_, Ty<'tcx>>. We can produce one of those readily enough by invoking canonicalize_query:

rust/src/librustc/infer/canonical.rs

Lines 470 to 472 in 8c4ff22

	pub fn canonicalize_query<V>(&self, value: &V) -> (V::Canonicalized, CanonicalVarValues<'tcx>)
	where
	V: Canonicalize<'gcx, 'tcx>,

Though we may need to add a Canonicalize impl, like so:

pub type CanonicalTy<'gcx> = Canonical<'gcx, Ty<'tcx>>;

impl<'gcx: 'tcx, 'tcx> Canonicalize<'gcx, 'tcx> for Ty<'tcx> {
    type Canonicalized = CanonicalTy<'gcx>;

    fn intern(
        _gcx: TyCtxt<'_, 'gcx, 'gcx>,
        value: Canonical<'gcx, Self::Lifted>,
    ) -> Self::Canonicalized {
        value
    }
}

Anyway, the next challenge is that the "typeck tables" don't have a suitable table:

rust/src/librustc/ty/context.rs

Lines 338 to 339 in 8c4ff22

	#[derive(RustcEncodable, RustcDecodable, Debug)]
	pub struct TypeckTables<'tcx> {

We'll have to add a field like this one:

rust/src/librustc/ty/context.rs

Lines 347 to 350 in 8c4ff22

	/// Stores the types for various nodes in the AST. Note that this table
	/// is not guaranteed to be populated until after typeck. See
	/// typeck::check::fn_ctxt for details.
	node_types: ItemLocalMap<Ty<'tcx>>,

but it should be called user_provided_tys and have the type ItemLocalMap<CanonicalTy<'tcx>>.

Finally, we have to populate that field. We first convert the user-provided types here:

rust/src/librustc_typeck/check/mod.rs

Lines 946 to 949 in 8c4ff22

	let o_ty = match local.ty {
	Some(ref ty) => Some(self.fcx.to_ty(&ty)),
	None => None
	};

If we canonicalize the type right there, before we go and do anything else it, that should give us the value we want for the table. We can do the store into the table with local.id, sort of like here:

rust/src/librustc_typeck/check/mod.rs

Line 950 in 8c4ff22

self.assign(local.span, local.id, o_ty);

[davidtwco]

With #48482 merged, there are some things that were not covered in that PR.

rust/src/librustc_mir/build/block.rs

Lines 128 to 135 in 4161ae7

	// FIXME(#47184): We currently only insert `UserAssertTy` statements for
	// patterns that are bindings, this is as we do not want to deconstruct
	// the type being assertion to match the pattern.
	if let PatternKind::Binding { var, .. } = *pattern.kind {
	if let Some(ty) = ty {
	this.user_assert_ty(block, ty, var, span);
	}
	}

• The current implementation does not handle patterns that are not bindings, such as let (a, b): (u32, u32) = (84, 29);.

rust/src/test/run-pass/generator/yield-subtype.rs

Line 12 in 4161ae7

//[nll]compile-flags: -Z disable-nll-user-type-assert

• There is a temporary flag to disable this functionality for the case where a lifetime was defined but not used, this currently only occurs in the yield-subtype.rs test but that will also need resolved.

Further, this PR also only implements the check for type annotations in the let x: T = ...; case, see this comment for the remaining cases.

[nikomatsakis]

Spun out to sub-issues.

[nikomatsakis]

Demoting to Rust 2018 release. However, we should go ahead and convert all remaining items to sub-issues, I think, and close this

[nikomatsakis]

I'm going to close this bug now -- we're down to just a handful of "subbullets", each of which has their own tracking issues.