Rust: 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 https://github.com/rust-lang/rust/issues/58291#issuecomment-483574502 )

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

• 686d0ae137b1d66711694903607750ad54f60f69 Auto merge of #50290 - kennytm:rollup, r=kennytm
  
  
  
  • #49858 (std: Mark ptr::Unique with #[doc(hidden)])
  
  
  • #49968 (Stabilize dyn trait)
  
  
  • #50192 (Add some utilities to libsyntax)
  
  
  • #50251 (rustc: Disable threads in LLD for wasm)
  
  
  • #50263 (rustc: Emit uwtable for allocator shims)
  
  
  • #50269 (Update parking_lot dependencies)
  
  
  • #50273 (Allow #[inline] on closures)
  
  
  • #50284 (fix search load page failure)
  
  
  • #50257 (Don't ICE on tuple struct ctor with incorrect arg count)
  
  
• a9975254ee6510cd1360417d3d145b56fb70b2e7 Auto merge of #50137 - nox:rm-bool-cmp-hack, r=eddyb
• 3c43aa5677e17dfb9f5004522745a02e21a604a4 Auto merge of #50102 - Zoxc:query-nomacro, r=michaelwoerister
• 71d3dac4a86d192c2c80948621859da3b363fa50 Auto merge of #50097 - glandium:box_free, r=nikomatsakis
• ada45fd49a2dfcf2a163e1f4641ac34f2803eb9b Auto merge of #50275 - kennytm:rollup, r=kennytm
  
  
  
  • #49707 (Add "the Rustc book")
  
  
  • #50222 (Bump bootstrap compiler to 2018-04-24)
  
  
  • #50227 (Fix ICE with erroneous impl Trait in a trait impl)
  
  
  • #50229 (Add setting to go to item if there is only one result)
  
  
  • #50231 (Add more doc aliases)
  
  
  • #50246 (Make dump_{alloc,allocs,local}() no-ops when tracing is disabled.)
  
  
  • #49894 (Rename InternedString to LocalInternedString and introduce a new thread-safe InternedString)
  
  
• 9822b5709ca78d6398e9ae609de0181116e8b0db Auto merge of #49891 - cuviper:compiletest-crash, r=alexcrichton
• 8a09bc6a77a908b11120cb09e6d2bf0b7a13494e Auto merge of #48995 - aravind-pg:canonical-query, r=nikomatsakis
• e05b78daa628ad88952d856c68cb5708434fa934 Auto merge of #49420 - nox:enum-scalarpair, r=eddyb
• 7d8f0e22f574c7ffb4b6544cc96c066b7de3b6be Auto merge of #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.

[pnkfelix]

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.