april 2018 trait resolution regression

[pnkfelix]

(spawned off of #58291)

Reduced example (play):

use std::panic::RefUnwindSafe;

trait Database { type Storage; }
trait HasQueryGroup { }
trait Query<DB> { type Data; }
trait SourceDatabase { fn parse(&self) { loop { } } }

struct ParseQuery;
struct RootDatabase { _runtime: Runtime<RootDatabase>, }
struct Runtime<DB: Database> { _storage: Box<DB::Storage> }
struct SalsaStorage { _parse: <ParseQuery as Query<RootDatabase>>::Data, }

impl Database for RootDatabase  { type Storage = SalsaStorage; }
impl HasQueryGroup for RootDatabase {}
impl<DB> Query<DB> for ParseQuery where DB: SourceDatabase, DB: Database { type Data = RootDatabase; }
impl<T> SourceDatabase for T where T: RefUnwindSafe, T: HasQueryGroup {}

pub(crate) fn goto_implementation(db: &RootDatabase) -> u32 { db.parse(); loop { } }

fn main() { }

original code:

https://gist.github.com/dc3f0f8568ca093d9750653578bb8026

% rustc +nightly-2018-04-27 --allow dead_code  src/main.rs
% rustc +nightly-2018-04-28 --allow dead_code  src/main.rs
error[E0599]: no method named `parse` found for type `&RootDatabase` in the current scope
   --> src/main.rs:231:6
    |
231 | { db.parse(); loop { } }
    |      ^^^^^
    |
    = note: the method `parse` exists but the following trait bounds were not satisfied:
            `RootDatabase : SourceDatabase`
            `&RootDatabase : SourceDatabase`
            `RootDatabase : SourceDatabase`
    = help: items from traits can only be used if the trait is implemented and in scope
    = note: the following trait defines an item `parse`, perhaps you need to implement it:
            candidate #1: `SourceDatabase`

error: aborting due to previous error

For more information about this error, try `rustc --explain E0599`.
%

[pnkfelix]

This change in behavior might be a bugfix. I'm still trying to understand the further narrowed-down test case, where it seems like one of the crucial details is the handling of std::panic::RefUnwindSafe:

use std::panic::RefUnwindSafe;

trait Database { type Storage; }
trait HasQueryGroup { }
trait Query<DB> { type Data; }
trait SourceDatabase { fn parse(&self) { loop { } } }

struct ParseQuery;
struct RootDatabase { _runtime: Runtime<RootDatabase>, }
struct Runtime<DB: Database> { _storage: Box<DB::Storage> }
struct SalsaStorage { _parse: <ParseQuery as Query<RootDatabase>>::Data, }

impl Database for RootDatabase  { type Storage = SalsaStorage; }
impl HasQueryGroup for RootDatabase {}
impl<DB> Query<DB> for ParseQuery where DB: SourceDatabase, DB: Database { type Data = RootDatabase; }
impl<T> SourceDatabase for T where T: RefUnwindSafe, T: HasQueryGroup {}

pub(crate) fn goto_implementation(db: &RootDatabase) -> u32 { db.parse(); loop { } }

fn main() { }

[pnkfelix]

(note in particular that in this example, we have a blanket implementation of SourceDatabase for any T that implements HasQueryGroup and RefUnwindSafe. There's an implementation of the former for RootDatabase, but not for the latter.

(But I'm not yet sure whether RefUnwindSafe is an OIBIT. Looking now.)

Update: okay, pub auto trait RefUnwindSafe, so I think RootDatabase implements it by default; I don't see any negative impls for Box. But I also am not 100% sure how that auto traits interact with fields defined via associated types of generic type parameters...

[pnkfelix]

For reference, here is the log of changes between the two relevant nightlies. (I just transcribed this directly from #58291 (comment) )

% git log 7f3444e1b..686d0ae13 --author=bors --format=oneline

• 686d0ae Auto merge of Rollup of 9 pull requests #50290 - kennytm:rollup, r=kennytm
  • std: Mark ptr::Unique with #[doc(hidden)] #49858 (std: Mark ptr::Unique with #[doc(hidden)])
  • Stabilize dyn trait #49968 (Stabilize dyn trait)
  • Add some utilities to libsyntax #50192 (Add some utilities to libsyntax)
  • rustc: Disable threads in LLD for wasm #50251 (rustc: Disable threads in LLD for wasm)
  • rustc: Emit uwtable for allocator shims #50263 (rustc: Emit uwtable for allocator shims)
  • Update parking_lot dependencies #50269 (Update parking_lot dependencies)
  • Allow #[inline] on closures #50273 (Allow #[inline] on closures)
  • fix search load page failure #50284 (fix search load page failure)
  • Don't ICE on tuple struct ctor with incorrect arg count #50257 (Don't ICE on tuple struct ctor with incorrect arg count)
• a997525 Auto merge of Remove hack around comparisons of i1 values (fixes #40980) #50137 - nox:rm-bool-cmp-hack, r=eddyb
• 3c43aa5 Auto merge of Move query code outside macros and store query jobs separately from query results #50102 - Zoxc:query-nomacro, r=michaelwoerister
• 71d3dac Auto merge of Partial future-proofing for Box<T, A> #50097 - glandium:box_free, r=nikomatsakis
• ada45fd Auto merge of Rollup of 7 pull requests #50275 - kennytm:rollup, r=kennytm
  • Add "the Rustc book" #49707 (Add "the Rustc book")
  • Bump bootstrap compiler to 2018-04-24 #50222 (Bump bootstrap compiler to 2018-04-24)
  • Fix ICE with erroneous impl Trait in a trait impl #50227 (Fix ICE with erroneous impl Trait in a trait impl)
  • Add setting to go to item if there is only one result #50229 (Add setting to go to item if there is only one result)
  • Add more doc aliases #50231 (Add more doc aliases)
  • Make dump_{alloc,allocs,local}() no-ops when tracing is disabled. #50246 (Make dump_{alloc,allocs,local}() no-ops when tracing is disabled.)
  • Rename InternedString to LocalInternedString and introduce a new thread-safe InternedString #49894 (Rename InternedString to LocalInternedString and introduce a new thread-safe InternedString)
• 9822b57 Auto merge of compiletest: detect non-ICE compiler panics #49891 - cuviper:compiletest-crash, r=alexcrichton
• 8a09bc6 Auto merge of Create a canonical trait query for evaluate_obligation #48995 - aravind-pg:canonical-query, r=nikomatsakis
• e05b78d Auto merge of Use ScalarPair for tagged enums #49420 - nox:enum-scalarpair, r=eddyb
• 7d8f0e2 Auto merge of drop elaboration should reveal all #50253 - nikomatsakis:regressions-2018-04-26, r=eddyb

[pnkfelix]

The two PR's that I think seem most likely to be at fault here are either #48995 or #50102

[pnkfelix]

Okay I have now confirmed that this was injected by #48995

[pnkfelix]

my current theory is that this is arising due to some interaction between inductive and co-inductive reasoning.

In particular, if you focus in on the impl<T> SourceDatabase for T where T: RefUnwindSafe, T: HasQueryGroup {}:

impl<T> SourceDatabase for T 
    where
        T: RefUnwindSafe, // [1]
        T: HasQueryGroup, // [2]
{}

commenting out either line [1] or line [2] above from the original code will cause the whole source input to be acccepted.

It is only when both are presented as preconditions on the blanket impl of SourceDatabase that we see a failure.

---

I extended the debug! output a bit to print out the whole trait obligation stack (with syntax elem1 :: elem2 :: elem3 :: []) and am seeing this in one of the compiler's attempts to prove that RootDatabase may implement SourceDatabase when its trying to resolve that parse method invocation:

DEBUG 2019-04-17T09:14:41Z: rustc::traits::select: evaluate_stack entry
stack: TraitObligationStack { obligation: Obligation(predicate=Binder(TraitPredicate(<RootDatabase as SourceDatabase>)),depth=9), fresh_trait_ref: Binder(<RootDatabase as SourceDatabase>) }
    :: TraitObligationStack { obligation: Obligation(predicate=Binder(TraitPredicate(<SalsaStorage as std::panic::RefUnwindSafe>)),depth=7), fresh_trait_ref: Binder(<SalsaStorage as std::panic::RefUnwindSafe>) }
    :: TraitObligationStack { obligation: Obligation(predicate=Binder(TraitPredicate(<*const SalsaStorage as std::panic::RefUnwindSafe>)),depth=6), fresh_trait_ref: Binder(<*const SalsaStorage as std::panic::RefUnwindSafe>) }
    :: TraitObligationStack { obligation: Obligation(predicate=Binder(TraitPredicate(<core::nonzero::NonZero<*const SalsaStorage> as std::panic::RefUnwindSafe>)),depth=5), fresh_trait_ref: Binder(<core::nonzero::NonZero<*const SalsaStorage> as std::panic::RefUnwindSafe>) }
    :: TraitObligationStack { obligation: Obligation(predicate=Binder(TraitPredicate(<std::ptr::Unique<SalsaStorage> as std::panic::RefUnwindSafe>)),depth=4), fresh_trait_ref: Binder(<std::ptr::Unique<SalsaStorage> as std::panic::RefUnwindSafe>) }
    :: TraitObligationStack { obligation: Obligation(predicate=Binder(TraitPredicate(<std::boxed::Box<SalsaStorage> as std::panic::RefUnwindSafe>)),depth=3), fresh_trait_ref: Binder(<std::boxed::Box<SalsaStorage> as std::panic::RefUnwindSafe>) }
    :: TraitObligationStack { obligation: Obligation(predicate=Binder(TraitPredicate(<Runtime<RootDatabase> as std::panic::RefUnwindSafe>)),depth=2), fresh_trait_ref: Binder(<Runtime<RootDatabase> as std::panic::RefUnwindSafe>) }
    :: TraitObligationStack { obligation: Obligation(predicate=Binder(TraitPredicate(<RootDatabase as std::panic::RefUnwindSafe>)),depth=1), fresh_trait_ref: Binder(<RootDatabase as std::panic::RefUnwindSafe>) }
    :: TraitObligationStack { obligation: Obligation(predicate=Binder(TraitPredicate(<RootDatabase as SourceDatabase>)),depth=0), fresh_trait_ref: Binder(<RootDatabase as SourceDatabase>) }
    :: []
DEBUG 2019-04-17T09:14:41Z: rustc::traits::select: evaluate_stack(Binder(<RootDatabase as SourceDatabase>)) --> recursive

that is, it thinks the attempt to prove RootDatabase implements SourceDatabase requires recursive reasoning: because proving that requires proving that RootDatabase: RefUnwindSafe, which bubbles down to Runtime<RootDatabase>: RefUnwindSafe and from there to SalsaStorage: RefUnwindSafe.

And that last bit, SalsaStorage: RefUnwindSafe, might be where we are hitting a problem, due to these definitions:

struct SalsaStorage { _parse: <ParseQuery as Query<RootDatabase>>::Data, }
// ...
impl<DB> Query<DB> for ParseQuery where DB: SourceDatabase { type Data = RootDatabase; }

so we now see why the compiler might reason that it has to prove RootDatabase: SourceDatabase when analyzing the structure of SalsaStorage: it needs to find the implementation of that trait so that it can find its associated ::Data type.

---

But for some reason we don't hit the above problem if we remove the T: HasQueryGroup where clause on the blanket impl of SourceDatabase.

[nikomatsakis]

@pnkfelix I haven't had time to deeply look yet, but a few notes about induction/co-induction in general:

In short, a cycle in trait resolution is only considered "true" if all the traits involved are co-inductive (i.e., auto-traits). So if you have Foo: Send requires (indirectly, say) Foo: Send, that's ok.

But if you have Foo: Send requires Foo: Debug which requires Foo: Send, that's not ok.

In this case, then, I expect that cycle to be "non-true", because SourceDatabase is an inductive trait and hence proving that RootDatabase: SourceDatabase cannot require RootDatabase: SourceDatabase.

What I'm not sure about 100% is why the behavior changed here and whether the cycle ought to arise.

[nikomatsakis]

Also curious:

If you do SourceDatabase::parse(db) instead of db.parse(), it compiles.

There are two distinct systems for trait evaluation (the "evaluate" code and the "confirm" code) which, I suppose, are disagreeing here. Digging a bit more.