search

rust-lang / rust

Empowering everyone to build reliable and efficient software.
https://www.rust-lang.org
Other
98.14k stars 12.69k forks source link

april 2018 trait resolution regression #60010

Closed pnkfelix closed 5 years ago

pnkfelix commented 5 years ago

(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 commented 5 years ago

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 commented 5 years ago

(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 commented 5 years ago

For reference, here is the log of changes between the two relevant nightlies. (I just transcribed this directly from https://github.com/rust-lang/rust/issues/58291#issuecomment-483574502 )

% git log 7f3444e1b..686d0ae13 --author=bors --format=oneline
pnkfelix commented 5 years ago

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

pnkfelix commented 5 years ago

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

pnkfelix commented 5 years ago

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 commented 5 years ago

@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 commented 5 years ago

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.

pnkfelix commented 5 years ago

I believe this is resolved by PR #60444, in the sense that we now issue: 

error[E0275]: overflow evaluating the requirement `RootDatabase: SourceDatabase`
  --> src/main.rs:11:23
   |
11 | struct SalsaStorage { _parse: <ParseQuery as Query<RootDatabase>>::Data, }
   |                       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
   = note: required because of the requirements on the impl of `Query<RootDatabase>` for `ParseQuery`

error[E0275]: overflow evaluating the requirement `RootDatabase: SourceDatabase`
  --> src/main.rs:13:6
   |
13 | impl Database for RootDatabase  { type Storage = SalsaStorage; }
   |      ^^^^^^^^
   |
   = note: required because of the requirements on the impl of `Query<RootDatabase>` for `ParseQuery`
   = note: required because it appears within the type `SalsaStorage`

and furthermore, we do so independently of whatever the function body of fn goto_implementation contains (thus eliminating the oddity that niko noted in their previous comment).

Closing as fixed.