[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)

[nikomatsakis]

Not an RC blocker: the migration strategy means this will be a warning anyway.

[nikomatsakis]

OK, so, for the record: the reason that this errors out only with --compile-type=lib is that the errors occur in the generated code for "variant constructors", and -- since the variants are unused, I suppose -- we only wind up generating that code when creating a library. You can get an error without --compile-type lib by using this gist, which coerces the variant into a function, thus forcing the code in question to be generated.

I note though that we skip comparable struct constructors:

rust/src/librustc_mir/borrow_check/mod.rs

Lines 89 to 112 in 7ee7207

	if tcx.is_struct_constructor(def_id) {
	// We are not borrow checking the automatically generated struct constructors
	// because we want to accept structs such as this (taken from the `linked-hash-map`
	// crate):
	// ```rust
	// struct Qey<Q: ?Sized>(Q);
	// ```
	// MIR of this struct constructor looks something like this:
	// ```rust
	// fn Qey(_1: Q) -> Qey<Q>{
	// let mut _0: Qey<Q>; // return place
	//
	// bb0: {
	// (_0.0: Q) = move _1; // bb0[0]: scope 0 at src/main.rs:1:1: 1:26
	// return; // bb0[1]: scope 0 at src/main.rs:1:1: 1:26
	// }
	// }
	// ```
	// The problem here is that `(_0.0: Q) = move _1;` is valid only if `Q` is
	// of statically known size, which is not known to be true because of the
	// `Q: ?Sized` constraint. However, it is true because the constructor can be
	// called only when `Q` is of statically known size.
	return_early = true;
	}

but anyway we should fix this bug. I believe that this example, from #53789, is the same underlying problem:

#![feature(nll)]
#![allow(unused_variables)]

use std::collections::BTreeMap;

trait ValueTree {
    type Value;
}

trait Strategy {
    type Value: ValueTree;
}

type StrategyFor<A> = StrategyType<'static, A>;
type StrategyType<'a, A> = <A as Arbitrary<'a>>::Strategy;

impl<K: ValueTree, V: ValueTree> Strategy for (K, V)
{
    type Value = TupleValueTree<(K, V)>;
}

impl<K: ValueTree, V: ValueTree> ValueTree for TupleValueTree<(K, V)>
{
    type Value = BTreeMapValueTree<K, V>;
}

struct TupleValueTree<T> {
    tree: T,
}

struct BTreeMapStrategy<K, V>(std::marker::PhantomData<(K, V)>)
where
    K: Strategy,
    V: Strategy;

struct BTreeMapValueTree<K, V>(
    std::marker::PhantomData<(K, V)>
)
where
    K: ValueTree,
    V: ValueTree;

impl<K, V> Strategy for BTreeMapStrategy<K, V>
where
    K: Strategy,
    V: Strategy,
{
    type Value = BTreeMapValueTree<K::Value, V::Value>;
}

impl<K, V> ValueTree for BTreeMapValueTree<K, V>
where
    K: ValueTree,
    V: ValueTree,
{
    type Value = BTreeMap<K::Value, V::Value>;
}

trait Arbitrary<'a>: Sized {
    fn arbitrary_with(args: Self::Parameters) -> Self::Strategy;
    type Parameters;
    type Strategy: Strategy<Value = Self::ValueTree>;
    type ValueTree: ValueTree<Value = Self>;
}

impl<'a, A, B> Arbitrary<'a> for BTreeMap<A, B>
where
    A: Arbitrary<'static>,
    B: Arbitrary<'static>,
    StrategyFor<A>: 'static,
    StrategyFor<B>: 'static,
{
    type ValueTree = <Self::Strategy as Strategy>::Value;
    type Parameters = (A::Parameters, B::Parameters);
    type Strategy = BTreeMapStrategy<A::Strategy, B::Strategy>;
    fn arbitrary_with(args: Self::Parameters) -> BTreeMapStrategy<A::Strategy, B::Strategy> {
        let (a, b) = args;
        btree_map(any_with::<A>(a), any_with::<B>(b))
    }
}

fn btree_map<K: Strategy + 'static, V: Strategy>(
    key: K,
    value: V
) -> BTreeMapStrategy<K, V>
{
    unimplemented!()
}

fn any_with<'a, A: Arbitrary<'a>>(args: A::Parameters) -> StrategyType<'a, A> {
    unimplemented!()
}

[nikomatsakis]

Minimized test showing the core problem:

trait MyTrait<'a> {
    type Output;
}

fn foo<'a, T>() -> &'a ()
where
    T: MyTrait<'a>, <T as MyTrait<'a>>::Output: 'a,
{
    bar::<T::Output>()
}

fn bar<'a, T>() -> &'a ()
where
    T: 'a,
{
    &()
}

fn main() {}

[nikomatsakis]

Fix in #54453