[nll] spurious outlives requirement in shred-0.7.0

[nikomatsakis]

The following snippet, extracted from the crate shred v0.7.0, fails to compile with NLL, but only when compiled with --crate-type lib:

// NB You must compile with `--crate-type lib` to see the failure!

#![feature(nll)]

pub trait Accessor: Sized {
}

pub enum AccessorCow<'a, 'b, T>
where
    AccessorTy<'a, T>: 'b,
    T: System<'a> + ?Sized,
'a: 'b,
{
    /// A reference to an accessor.
    Ref(&'b AccessorTy<'a, T>),
    /// An owned accessor.
    Owned(AccessorTy<'a, T>),
}

type AccessorTy<'a, T> = <<T as System<'a>>::SystemData as DynamicSystemData<'a>>::Accessor;

pub trait System<'a> {
    type SystemData: DynamicSystemData<'a>;
}

pub trait SystemData<'a> {
}

pub trait DynamicSystemData<'a> {
    /// The accessor of the `SystemData`, which specifies the read and write dependencies and does
    /// the fetching.
    type Accessor: Accessor;
}

fn main() { }

yields

> rustc +nightly ~/tmp/reduce.rs -Zborrowck=mir -Ztwo-phase-borrows --crate-type lib

error[E0309]: the parameter type `T` may not live long enough
  --> /home/nmatsakis/tmp/reduce.rs:13:5
   |
13 |     Ref(&'b AccessorTy<'a, T>),
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
   = help: consider adding an explicit lifetime bound `T: 'b`...

error[E0309]: the parameter type `T` may not live long enough
  --> /home/nmatsakis/tmp/reduce.rs:15:5
   |
15 |     Owned(AccessorTy<'a, T>),
   |     ^^^^^^^^^^^^^^^^^^^^^^^^
   |
   = help: consider adding an explicit lifetime bound `T: 'b`...

I'm not entirely sure what is going on here, but it seems very fishy, particularly since it is specific to --crate-type lib.

[nikomatsakis]

OK so I've dug into this a bit more. The NLL behavior here is buggy, I think, but I'm having trouble isolating it to a nicer test case because in general our behavior here is not that strong. I think that this struct ought to be well-formed as is -- requiring that T: 'b is sufficient but not necessary, the existing where AccessorTy<'a, T>: 'b ought to suffice.

I think that the problem is that the NLL code is hitting this "fallback" in the code that handles obligations like AccessorTy<'0, T>: '1:

rust/src/librustc/infer/outlives/obligations.rs

Lines 383 to 410 in cf84056

	// If declared bounds list is empty, the only applicable rule is
	// OutlivesProjectionComponent. If there are inference variables,
	// then, we can break down the outlives into more primitive
	// components without adding unnecessary edges.
	//
	// If there are *no* inference variables, however, we COULD do
	// this, but we choose not to, because the error messages are less
	// good. For example, a requirement like `T::Item: 'r` would be
	// translated to a requirement that `T: 'r`; when this is reported
	// to the user, it will thus say "T: 'r must hold so that T::Item:
	// 'r holds". But that makes it sound like the only way to fix
	// the problem is to add `T: 'r`, which isn't true. So, if there are no
	// inference variables, we use a verify constraint instead of adding
	// edges, which winds up enforcing the same condition.
	let needs_infer = projection_ty.needs_infer();
	if env_bounds.is_empty() && needs_infer {
	debug!("projection_must_outlive: no declared bounds");
	for component_ty in projection_ty.substs.types() {
	self.type_must_outlive(origin.clone(), component_ty, region);
	}
	for r in projection_ty.substs.regions() {
	self.delegate.push_sub_region_constraint(origin.clone(), region, r);
	}
	return;
	}

In particular, if we encounter an obligation to prove AccessorTy<'0, T>: '1, we fallback to requiring that '0: '1 and T: '1. As the comment describes, this case is quite tricky because if we don't add constraints to inference, then '0 might be too small -- but if we do, we don't know which to add really.

Anyway, since NLL uses region inference variables everywhere, it basically always hits this case, which makes us overly conservative in this example.

I'm not sure yet the right fix. I suppose that in NLL we could avoid going down this path, but I think this will likely cause other failures.

[nikomatsakis]

I was thinking about this. I think maybe the best fix is that we should not be so eager to convert "outlives bounds" into type tests and constraints. We could hold off on that, do inference, and then do the type test conversion. This second round may of course add new constraints, and we can deal with that.

This will be a bit of a pain, though, since we currently compute the SCCs etc based on the previous set of obligations, and this would introduce new edges into the graph. Not sure how to deal with that.

Gah, still not entirely sure what to do here.

[pnkfelix]

visited at meeting. assigning to niko to try to write up a plan of attack. (Also, we need to decide whether it is really an RC blocker or not)