Internal compiler error when documenting `capnp`

[juchiast]

Cargo.toml:

[dependencies]
capnp = "0.8.17"

Result when run cargo doc:

thread '<unnamed>' panicked at 'Unable to fulfill trait DefId(2/0:864 ~ core[b3f3]::marker[0]::Send[0]) for 'list_list::Owned<T>': [FulfillmentError(Obligation(predicate=Binder(ProjectionPredicate(ProjectionTy { substs: [T, ReStatic], item_def_id: DefId(0/0:1150 ~ lib[8787]::traits[0]::Owned[0]::Reader[0]) }, _)),depth=2),Ambiguity), FulfillmentError(Obligation(predicate=Binder(TraitPredicate(<_ as std::marker::Send>)),depth=2),Ambiguity)]', librustc/traits/auto_trait.rs:218:17
note: Run with `RUST_BACKTRACE=1` for a backtrace.

error: internal compiler error: unexpected panic

note: the compiler unexpectedly panicked. this is a bug.

note: we would appreciate a bug report: https://github.com/rust-lang/rust/blob/master/CONTRIBUTING.md#bug-reports

note: rustc 1.28.0-nightly (5d0631a64 2018-05-30) running on x86_64-unknown-linux-gnu

error: Could not document `capnp`.

Caused by:
  process didn't exit successfully: `rustdoc --crate-name capnp /home/qwe/.cargo/registry/src/github.spider-man.dpdns.org-1ecc6299db9ec823/capnp-0.8.17/src/lib.rs -o /home/qwe/Desktop/upw/test_rustdoc/target/doc -L dependency=/home/qwe/Desktop/upw/test_rustdoc/target/debug/deps --extern byteorder=/home/qwe/Desktop/upw/test_rustdoc/target/debug/deps/libbyteorder-3355ea0a902fb6f6.rmeta` (exit code: 101)

rustc version: nightly-x86_64-unknown-linux-gnu (5d0631a 2018-05-30)
Also happen in nightly-2018-05-29 and nightly-2018-05-23.

[juchiast]

UPDATE

Also happen on rustc 1.26.1

thread 'rustc' panicked at 'Unable to fulfill trait DefId(2/0:885 ~ core[3db6]::marker[0]::Send[0]) for 'list_list::Owned<T>': [FulfillmentError(Obligation(predicate=Binder(ProjectionPredicate(ProjectionTy { substs: Slice([T, ReStatic]), item_def_id: DefId(0/0:1150 ~ lib[8787]::traits[0]::Owned[0]::Reader[0]) }, _)),depth=2),Ambiguity), FulfillmentError(Obligation(predicate=Binder(TraitPredicate(<_ as std::marker::Send>)),depth=2),Ambiguity)]', librustdoc/clean/auto_trait.rs:401:17
note: Run with `RUST_BACKTRACE=1` for a backtrace.

error: internal compiler error: unexpected panic

note: the compiler unexpectedly panicked. this is a bug.

note: we would appreciate a bug report: https://github.com/rust-lang/rust/blob/master/CONTRIBUTING.md#bug-reports

note: rustc 1.26.1 (827013a31 2018-05-25) running on x86_64-unknown-linux-gnu

error: Could not document `capnp`.

Caused by:
  process didn't exit successfully: `rustdoc --crate-name capnp /home/qwe/.cargo/registry/src/github.spider-man.dpdns.org-1ecc6299db9ec823/capnp-0.8.17/src/lib.rs -o /home/qwe/Desktop/upw/test_rustdoc/target/doc -L dependency=/home/qwe/Desktop/upw/test_rustdoc/target/debug/deps --extern byteorder=/home/qwe/Desktop/upw/test_rustdoc/target/debug/deps/libbyteorder-52361c0693377ac0.rmeta` (exit code: 101)

[QuietMisdreavus]

Minimal reproduction:

use std::marker::PhantomData;

pub mod traits {
    pub trait Owned<'a> {
        type Reader;
    }
}

pub struct Owned<T> where T: for<'a> ::traits::Owned<'a> {
    marker: PhantomData<<T as ::traits::Owned<'static>>::Reader>,
}

Maybe some kind of mismatch between the HRTB on the struct definition and the 'static used in the marker?

EDIT: This is happening when figuring out the auto-trait impls on the Owned struct. It looks like @varkor and @ibabushkin were the last ones to touch that? We'll probably need to bring in a compiler person, depending on what the code is asking the compiler for.

[coder543]

Happens on current stable* and current nightly**, so this is interesting. I guess I can't build local documentation for my dependencies until this is fixed.

*  rustc 1.26.2 (594fb253c 2018-06-01)
** rustc 1.28.0-nightly (f28c7aef7 2018-06-19)

[eddyb]

cc @nikomatsakis @Aaron1011 So this is what's failing

rust/src/librustc/traits/auto_trait.rs

Lines 217 to 222 in 4dc2d74

	fulfill.select_all_or_error(&infcx).unwrap_or_else(|e| {
	panic!(
	"Unable to fulfill trait {:?} for '{:?}': {:?}",
	trait_did, ty, e
	)
	});

The huge comment before all of this suggests to me that it's a bit fragile and this is an edge case:

rust/src/librustc/traits/auto_trait.rs

Lines 136 to 167 in 4dc2d74

	// Due to the way projections are handled by SelectionContext, we need to run
	// evaluate_predicates twice: once on the original param env, and once on the result of
	// the first evaluate_predicates call.
	//
	// The problem is this: most of rustc, including SelectionContext and traits::project,
	// are designed to work with a concrete usage of a type (e.g. Vec<u8>
	// fn<T>() { Vec<T> }. This information will generally never change - given
	// the 'T' in fn<T>() { ... }, we'll never know anything else about 'T'.
	// If we're unable to prove that 'T' implements a particular trait, we're done -
	// there's nothing left to do but error out.
	//
	// However, synthesizing an auto trait impl works differently. Here, we start out with
	// a set of initial conditions - the ParamEnv of the struct/enum/union we're dealing
	// with - and progressively discover the conditions we need to fulfill for it to
	// implement a certain auto trait. This ends up breaking two assumptions made by trait
	// selection and projection:
	//
	// * We can always cache the result of a particular trait selection for the lifetime of
	// an InfCtxt
	// * Given a projection bound such as '<T as SomeTrait>::SomeItem = K', if 'T:
	// SomeTrait' doesn't hold, then we don't need to care about the 'SomeItem = K'
	//
	// We fix the first assumption by manually clearing out all of the InferCtxt's caches
	// in between calls to SelectionContext.select. This allows us to keep all of the
	// intermediate types we create bound to the 'tcx lifetime, rather than needing to lift
	// them between calls.
	//
	// We fix the second assumption by reprocessing the result of our first call to
	// evaluate_predicates. Using the example of '<T as SomeTrait>::SomeItem = K', our first
	// pass will pick up 'T: SomeTrait', but not 'SomeItem = K'. On our second pass,
	// traits::project will see that 'T: SomeTrait' is in our ParamEnv, allowing
	// SelectionContext to return it back to us.

[QuietMisdreavus]

Debug output when run on my sample:

$ RUST_LOG=rustc::traits::auto_trait rustdoc +local -o asdf l.rs
DEBUG 2018-06-22T19:03:59Z: rustc::traits::auto_trait: evaluate_nested_obligations(ty_did=DefId(0/0:7 ~ l[8787]::Owned[0]), trait_did=DefId(2/0:865 ~ core[1c6a]::marker[0]::Send[0])): succeeded with 'ParamEnv { caller_bounds: [Binder(TraitPredicate(<T as traits::Owned<'a>>)), Binder(TraitPredicate(<T
as std::marker::Sized>)), Binder(TraitPredicate(<<T as traits::Owned<'static>>::Reader as std::marker::Send>)), Binder(TraitPredicate(<T as traits::Owned<'static>>))], reveal: UserFacing }' 'ParamEnv { caller_bounds: [Binder(TraitPredicate(<T as traits::Owned<'static>>)), Binder(TraitPredicate(<<T as
traits::Owned<'static>>::Reader as std::marker::Send>)), Binder(TraitPredicate(<T as std::marker::Sized>)), Binder(TraitPredicate(<T as traits::Owned<'a>>))], reveal: UserFacing }'
DEBUG 2018-06-22T19:03:59Z: rustc::traits::auto_trait: evaluate_nested_obligations(ty_did=DefId(0/0:7 ~ l[8787]::Owned[0]), trait_did=DefId(2/0:865 ~ core[1c6a]::marker[0]::Send[0])): succeeded with 'ParamEnv { caller_bounds: [Binder(TraitPredicate(<T as traits::Owned<'a>>)), Binder(TraitPredicate(<T
as std::marker::Sized>)), Binder(TraitPredicate(<<T as traits::Owned<'static>>::Reader as std::marker::Send>)), Binder(TraitPredicate(<T as traits::Owned<'static>>))], reveal: UserFacing }' 'ParamEnv { caller_bounds: [Binder(TraitPredicate(<T as traits::Owned<'static>>)), Binder(TraitPredicate(<<T as
traits::Owned<'static>>::Reader as std::marker::Send>)), Binder(TraitPredicate(<T as std::marker::Sized>)), Binder(TraitPredicate(<T as traits::Owned<'a>>))], reveal: UserFacing }'
DEBUG 2018-06-22T19:03:59Z: rustc::traits::auto_trait: find_auto_trait_generics(did=DefId(0/0:7 ~ l[8787]::Owned[0]), trait_did=DefId(2/0:865 ~ core[1c6a]::marker[0]::Send[0]), generics=Generics { parent: None, parent_count: 0, params: [Type(T, DefId(0/1:10 ~ l[8787]::Owned[0]::T[0]), 0)], param_def_id_to_index: {DefId(0/1:10 ~ l[8787]::Owned[0]::T[0]): 0}, has_self: false, has_late_bound_regions: None }): fulfilling with ParamEnv { caller_bounds: [Binder(TraitPredicate(<T as traits::Owned<'a>>)), Binder(TraitPredicate(<T as std::marker::Sized>)), Binder(TraitPredicate(<<T as traits::Owned<'static>>::Reader as std::marker::Send>)), Binder(TraitPredicate(<T as traits::Owned<'static>>))], reveal: UserFacing }
thread '<unnamed>' panicked at 'Unable to fulfill trait DefId(2/0:865 ~ core[1c6a]::marker[0]::Send[0]) for 'Owned<T>': [FulfillmentError(Obligation(predicate=Binder(ProjectionPredicate(ProjectionTy { substs: [T, ReStatic], item_def_id: DefId(0/0:6 ~ l[8787]::traits[0]::Owned[0]::Reader[0]) }, _)),depth=2),Ambiguity), FulfillmentError(Obligation(predicate=Binder(TraitPredicate(<_ as std::marker::Send>)),depth=2),Ambiguity)]', librustc/traits/auto_trait.rs:218:17
note: Run with `RUST_BACKTRACE=1` for a backtrace.

error: internal compiler error: unexpected panic

note: the compiler unexpectedly panicked. this is a bug.

note: we would appreciate a bug report: https://github.com/rust-lang/rust/blob/master/CONTRIBUTING.md#bug-reports

note: rustc 1.28.0-dev running on x86_64-unknown-linux-gnu

[Aaron1011]

Here's a slightly more simplified reproduction:

use std::marker::PhantomData;

pub trait OwnedTrait<'a> {
    type Reader;
}

pub struct Owned<T> where T: for<'a> OwnedTrait<'a> {
    marker: PhantomData<<T as OwnedTrait<'static>>::Reader>,
}

[Aaron1011]

I'd like to work on this.

[QuietMisdreavus]

I wonder if #50159 is related? It's not the same failure, but it's another failure when synthesizing impls for rustdoc, and it also deals with associated types as type parameters in struct fields.

[Aaron1011]

Initial thoughts:

The issue seems to be related to the fact that the auto trait finder picks up the following two bounds;

<T as OwnedTrait<'a>>
<T as OwnedTrait<'static>>

The first bounds is part of the initial param env (where T: for<'a> OwnedTrait<'a>), while the second gets picked up as a result of attempting to normalize <T as OwnedTrait<'static>>::Reader.

Once both of these predicates have been added to the ParamEnv, we run into issues the next time that SelectionContext.select is called, since both will end up as matching candidates.

I'm not entirely certain what the best way to resolve this is. One solution might be to inspect the generated ParamEnv after each call to select, and check for predicates that differ only in their Substs. However, it's not clear to me how to do this in a way that ensures that we still generate the correct bounds - i.e we need to ensure that the bounds we display to the user are actually sufficient to make it implement the auto trait.

[Aaron1011]

Some further thoughts:

I think I can make the de-duplication approach work. Given two trait predicates that differ only in their lifetime substations, we should always choose the 'more strict' one. This means always choosing a predicate involving a HRTB over one involving 'static. Requiring that we be able to choose any lifetime in the type means that it's fine to pick 'static.

If I'm correct in my understanding of trait selection and fulfillment, this shouldn't lead to any 'unsound' (not actually sufficient) bounds being displayed to user. This de-duplication will take place before we run FulfillmentContext run, which means that we'll get an error if our computed bounds are insufficient.