Rust-analyzer: Add support for multiple universes in `impls_for_trait`

[yaahc]

I don't really have many details on exactly whats wrong, I know that code actions seem completely busted right now so they might be related to the issue, but I'm seeing a ton of assertion failures, seems to be related to chalk maybe.

[ERROR rust_analyzer::main_loop] overly long loop turn: 2.525155556s
thread '<unnamed>' panicked at 'assertion failed: `(left == right)`
  left: `U1`,
 right: `U0`', crates/ra_hir_ty/src/traits/chalk/mapping.rs:99:17
stack backtrace:
   0: <unknown>
   1: core::fmt::write
   2: <unknown>
   3: <unknown>
   4: <unknown>
   5: std::panicking::rust_panic_with_hook
   6: rust_begin_unwind
   7: std::panicking::begin_panic_fmt
   8: ra_hir_ty::traits::chalk::mapping::<impl ra_hir_ty::traits::chalk::ToChalk for ra_hir_ty::Ty>::from_chalk
   9: <unknown>
  10: ra_hir_ty::traits::chalk::mapping::<impl ra_hir_ty::traits::chalk::ToChalk for ra_hir_ty::Substs>::from_chalk
  11: ra_hir_ty::traits::chalk::mapping::<impl ra_hir_ty::traits::chalk::ToChalk for ra_hir_ty::Ty>::from_chalk
  12: <unknown>
  13: <unknown>
  14: <unknown>
  15: <unknown>
  16: <unknown>
  17: <unknown>
  18: <unknown>
  19: <unknown>
  20: <unknown>
  21: <unknown>
  22: <unknown>
  23: <unknown>
  24: <unknown>
  25: <unknown>
  26: <unknown>
  27: <unknown>
  28: <unknown>
  29: <unknown>
  30: <unknown>
  31: <unknown>
  32: ra_hir_ty::traits::trait_solve_query
  33: <unknown>
  34: <unknown>
  35: <unknown>
  36: <unknown>
  37: <unknown>
  38: <unknown>
  39: <unknown>
  40: <unknown>
  41: <unknown>
  42: <unknown>
  43: <unknown>
  44: <unknown>
  45: <unknown>
  46: <unknown>
  47: <unknown>
  48: <unknown>
  49: <unknown>
  50: <unknown>
  51: ra_hir_ty::infer::infer_query
  52: <unknown>
  53: <unknown>
  54: <unknown>
  55: <unknown>
  56: <unknown>
  57: ra_hir::code_model::Function::diagnostics
  58: ra_hir::code_model::Module::diagnostics
  59: <unknown>
  60: ra_ide::Analysis::diagnostics
  61: <unknown>
  62: <unknown>
  63: <unknown>
  64: <unknown>
  65: <unknown>
  66: start_thread
             at /build/glibc-YYA7BZ/glibc-2.31/nptl/pthread_create.c:477
  67: __clone
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.

I tried exporting RUST_BACKTRACE=full before launching vscode but it doesn't seem to inherit env variables from the shell that launches it so this is all I've got, though I'll be happy to gather more details. Sorry for the as of yet lousy bug report :grimacing:

[flodiebold]

Can you try running rust-analyzer analysis-stats . in the project, to see if that reproduces the crash? You should also see the last function it was working on when it crashes, so then you could run rust-analyzer analysis-stats -o that_function . to only check that function, and then run it with CHALK_DEBUG=1 or maybe 2 and RA_LOG=ra_hir_ty::traits=debug. If the function is too big, it might help to reduce it a bit first though.

[lnicola]

See https://rust-analyzer.github.io/manual.html#vs-code.

[yaahc]

See https://rust-analyzer.github.io/manual.html#vs-code.

I see i didn't delete my comment fast enough, I noticed the binary path as soon as I went to lookup the install method :+1:

[yaahc]

❯ rust-analyzer analysis-stats . -o peer_set::set::call
Database loaded, 235 roots, 288.683791ms
Crates in this dir: 11
Total modules found: 121
Total declarations: 826
Total functions: 454
Item Collection: 12.084226579s, 0b allocated 0b resident
0/454 0% processing: peer_set::set::callthread 'main' panicked at 'assertion failed: `(left == right)`
  left: `U1`,
 right: `U0`', crates/ra_hir_ty/src/traits/chalk/mapping.rs:99:17
stack backtrace:
   0: <unknown>
   1: core::fmt::write
   2: <unknown>
   3: <unknown>
   4: <unknown>
   5: std::panicking::rust_panic_with_hook
   6: rust_begin_unwind
   7: std::panicking::begin_panic_fmt
   8: ra_hir_ty::traits::chalk::mapping::<impl ra_hir_ty::traits::chalk::ToChalk for ra_hir_ty::Ty>::from_chalk
   9: <unknown>
  10: ra_hir_ty::traits::chalk::mapping::<impl ra_hir_ty::traits::chalk::ToChalk for ra_hir_ty::Substs>::from_chalk
  11: ra_hir_ty::traits::chalk::mapping::<impl ra_hir_ty::traits::chalk::ToChalk for ra_hir_ty::Ty>::from_chalk
  12: <unknown>
  13: <unknown>
  14: <unknown>
  15: <unknown>
  16: <unknown>
  17: <unknown>
  18: <unknown>
  19: <unknown>
  20: <unknown>
  21: <unknown>
  22: <unknown>
  23: <unknown>
  24: <unknown>
  25: <unknown>
  26: <unknown>
  27: <unknown>
  28: <unknown>
  29: <unknown>
  30: <unknown>
  31: <unknown>
  32: ra_hir_ty::traits::trait_solve_query
  33: <unknown>
  34: <unknown>
  35: <unknown>
  36: <unknown>
  37: <unknown>
  38: <unknown>
  39: <unknown>
  40: <unknown>
  41: <unknown>
  42: <unknown>
  43: <unknown>
  44: <unknown>
  45: <unknown>
  46: <unknown>
  47: <unknown>
  48: <unknown>
  49: <unknown>
  50: <unknown>
  51: ra_hir_ty::infer::infer_query
  52: <unknown>
  53: <unknown>
  54: <unknown>
  55: <unknown>
  56: <unknown>
  57: rust_analyzer::cli::analysis_stats::analysis_stats
  58: <unknown>
  59: <unknown>
  60: std::rt::lang_start_internal
  61: <unknown>
  62: __libc_start_main
  63: <unknown>
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.

turning on those debug settings produce _massive_ amounts of logs, I think it might be easier to just help yall run this against our project to get the repro,

Here is the repo: https://github.com/ZcashFoundation/zebra

alternatively

git clone https://github.com/ZcashFoundation/zebra.git

And the specific command that repros the issue is

rust-analyzer analysis-stats -o peer_set::set::call .

If you prefer I can still upload the logs but its seriously thousands of lines of output so I'd be surprised if its helpful...

[yaahc]

I'm interested in helping fix this issue today btw

[flodiebold]

I haven't had time to look into it yet; log-wise, it'd be interesting to see the last thing Chalk worked on (based on the nesting of its debug logs); another approach would be trying to remove code from the function to get a more minimal example.

[yaahc]

No worries, I wanted to get involved anyways so this is as good an excuse as any, and ty for the recommendation of where to dig first :+1:

[yaahc]

So this is what it was doing when it failed,

: : : : : : : | solve_via_implication(
: : : : : : : :     canonical_goal=UCanonical { canonical: Canonical { value: InEnvironment { environment: Env([for<> FromEnv(!0_0: Discover), for<> FromEnv(!0_0: Unpin), for<> FromEnv(<!0_0 as Discover>::Key: Clone), for<> FromEnv(<!0_0 as Discover>::Key: Debug), for<> FromEnv(<!0_0 as Discover>::Key: ToString), for<> FromEnv(<!0_0 as Discover>::Service: Service<Request>), for<> AliasEq(<<!0_0 as Discover>::Service as Service<Request>>::Response = Response), for<> FromEnv(<!0_0 as Discover>::Service: Load), for<> FromEnv(<!0_0 as Discover>::Error: Into<Box<dyn for<type> [for<> Implemented(^1.0: Error), for<> Implemented(^1.0: Send), for<> Implemented(^1.0: Sync)]>>), for<> FromEnv(<<!0_0 as Discover>::Service as Service<Request>>::Error: Into<Box<dyn for<type> [for<> Implemented(^1.0: Error), for<> Implemented(^1.0: Send), for<> Implemented(^1.0: Sync)]>>), for<> FromEnv(<<!0_0 as Discover>::Service as Service<Request>>::Future: Send), for<> FromEnv(<<!0_0 as Discover>::Service as Load>::Metric: Debug)]), goal: AliasEq(<PeerSet<!1_0> as Service<Request>>::Error = Service::Error<PeerSet<!1_0>, Request>) }, binders: [] }, universes: 2 },
: : : : : : : :     clause=for<type, type, type> AliasEq(<^0.0 as Service<^0.1>>::Error = ^0.2) :- Normalize(<^0.0 as Service<^0.1>>::Error -> ^0.2)) {
: : : : : : : : | solve_goal(UCanonical { canonical: Canonical { value: InEnvironment { environment: Env([for<> FromEnv(!0_0: Discover), for<> FromEnv(!0_0: Unpin), for<> FromEnv(<!0_0 as Discover>::Key: Clone), for<> FromEnv(<!0_0 as Discover>::Key: Debug), for<> FromEnv(<!0_0 as Discover>::Key: ToString), for<> FromEnv(<!0_0 as Discover>::Service: Service<Request>), for<> AliasEq(<<!0_0 as Discover>::Service as Service<Request>>::Response = Response), for<> FromEnv(<!0_0 as Discover>::Service: Load), for<> FromEnv(<!0_0 as Discover>::Error: Into<Box<dyn for<type> [for<> Implemented(^1.0: Error), for<> Implemented(^1.0: Send), for<> Implemented(^1.0: Sync)]>>), for<> FromEnv(<<!0_0 as Discover>::Service as Service<Request>>::Error: Into<Box<dyn for<type> [for<> Implemented(^1.0: Error), for<> Implemented(^1.0: Send), for<> Implemented(^1.0: Sync)]>>), for<> FromEnv(<<!0_0 as Discover>::Service as Service<Request>>::Future: Send), for<> FromEnv(<<!0_0 as Discover>::Service as Load>::Metric: Debug)]), goal: Normalize(<PeerSet<!1_0> as Service<Request>>::Error -> Service::Error<PeerSet<!1_0>, Request>) }, binders: [] }, universes: 2 }) {
[DEBUG ra_hir_ty::traits::chalk] impls_for_trait Service
thread 'main' panicked at 'assertion failed: `(left == right)`

Here's the full output:

• analysis-stats.txt.gz

I'm currently fiddling with the src on rust-analyzer to try to get debug info I understand better out of it to get an idea of what type the universe ID that isnt UniverseIndex::ROOT is coming from and just generally exploring to understand the codebase better

[yaahc]

    // We currently don't deal with universes (I think / hope they're not yet
    // relevant for our use cases?)
    let u_canonical = chalk_ir::UCanonical { canonical, universes: 1 };

laughing about this comment

[flodiebold]

Aah of course, the assumption that we only get back root universe placeholders probably doesn't hold in callbacks like impls_for_trait...

[yaahc]

@flodiebold assuming this isn't going to be extremely involved to fix, could you write up mentor instructions on how to go about fixing this? I started with trying to make a minimal test case that reproduces the issue but I still don't really understand where the second universe is coming into it so I'm pretty much stuck rn.

[flodiebold]

After staring at the part of the log where the second universe shows up for a while, I think it comes from trying to unify two projections within dyn types. In particular, we have the goal

Normalize(<PeerSet<!0_0> as Service<Request>>::Future -> Pin<Box<dyn for<type> [for<> Implemented(^1.0: Future), for<> AliasEq(<^1.0 as Future>::Output = Result<<PeerSet<^1.0> as Service<Request>>::Response, <PeerSet<^1.0> as Service<Request>>::Error>), for<> Implemented(^1.0: Send)]>>)

and the clause

Normalize(<PeerSet<^0.0> as Service<Request>>::Future -> Pin<Box<dyn for<type> [for<> Implemented(^1.0: Future), for<> AliasEq(<^1.0 as Future>::Output = Result<<PeerSet<^1.0> as Service<Request>>::Response, <PeerSet<^1.0> as Service<Request>>::Error>), for<> Implemented(^1.0: Send)]>>)

, so while trying to unify the goal and the clause we have to unify

dyn for<type> [for<> Implemented(^1.0: Future), for<> AliasEq(<^1.0 as Future>::Output = Result<<PeerSet<^1.0> as Service<Request>>::Response, <PeerSet<^1.0> as Service<Request>>::Error>), for<> Implemented(^1.0: Send)]

with itself, which I think involves instantiating the self type of the dyn universally (i.e. as a placeholder in a new universe); and then unifying the <PeerSet<^1.0> as Service<Request>>::Error with itself creates an AliasEq goal that contains the new placeholder.

Soo, I would guess it should be possible to construct a test for this by having a dyn type similar to that one (dyn Future<Output = Result<Self::Response, Self::Error>>) and trying to prove some goal for it.

Buut after writing all this, I realize that the type there is wrong anyway. The PeerSet<^1.0> should be PeerSet<!0_0> -- it looks like we're forgetting a level of binders somewhere, either during lowering or during conversion to Chalk, so that bound variable doesn't get replaced by the type param placeholder when it should. I looked a bit, but didn't see an obvious place for this, so that test would still be useful.

[yaahc]

Okay, I'll start with trying to build out that minimal test case then

[flodiebold]

Although I don't see any reason why this couldn't happen without that mistake, so we might still have to handle non-root placeholders somehow :thinking:

[yaahc]

okay, @flodiebold, this is the simplest repro I could come up with.

https://github.com/ZcashFoundation/zebra-net-ra-crash-repro

Theres something REALLY weird with this bug, I had to just manually creduce my program to even have a chance of still reproing it, no attempts by hand could recreate the issue. Also the bug will go away from REALLY odd changes to the source that make it seem like its not a local issue, which makes sense with your "forgetting a level of binders somewhere" comment

Non exhaustive list of small changes that will make the bug go away:

• Removing the proptest dependency
• Moving the content of set.rs into lib.rs as an inline module instead of an external one
• defining a PinnedFut<T> type alias for the Future type on the service in set.rs.

I think the PinnedFut change in particular has a good chance at giving us a work around, I'm gonna play with some of the small tweaks to see if I can get it working for us temporarily, hopefully this repo will help with fixing the bug.

[yaahc]

Applying the PinnedFut type alias to our actual codebase fixes the panic, but it doesn't get us out of the woods, now we have a new panic in an entirely different part of the code, and turning on CHALK_DEBUG or RA_LOG produces no output...

zebra/zebra-network on  main [!] is 📦 v0.1.0 via 🦀 v1.44.0 
❯ RA_LOG=ra_hir_ty::traits=debug rust-analyzer analysis-stats -o peer::error::from .
Database loaded, 252 roots, 314.810466ms
Crates in this dir: 13
Total modules found: 135
Total declarations: 1019
Total functions: 580
Item Collection: 13.814810908s, 0b allocated 0b resident
0/580 0% processing: peer::error::fromthread 'main' panicked at 'assertion failed: `(left == right)`
  left: `1`,
 right: `0`', crates/ra_hir_ty/src/lib.rs:552:9
stack backtrace:
   0: backtrace::backtrace::libunwind::trace
             at /cargo/registry/src/github.com-1ecc6299db9ec823/backtrace-0.3.46/src/backtrace/libunwind.rs:86
   1: backtrace::backtrace::trace_unsynchronized
             at /cargo/registry/src/github.com-1ecc6299db9ec823/backtrace-0.3.46/src/backtrace/mod.rs:66
   2: std::sys_common::backtrace::_print_fmt
             at src/libstd/sys_common/backtrace.rs:78
   3: <std::sys_common::backtrace::_print::DisplayBacktrace as core::fmt::Display>::fmt
             at src/libstd/sys_common/backtrace.rs:59
   4: core::fmt::write
             at src/libcore/fmt/mod.rs:1069
   5: std::io::Write::write_fmt
             at src/libstd/io/mod.rs:1504
   6: std::sys_common::backtrace::_print
             at src/libstd/sys_common/backtrace.rs:62
   7: std::sys_common::backtrace::print
             at src/libstd/sys_common/backtrace.rs:49
   8: std::panicking::default_hook::{{closure}}
             at src/libstd/panicking.rs:198
   9: std::panicking::default_hook
             at src/libstd/panicking.rs:218
  10: std::panicking::rust_panic_with_hook
             at src/libstd/panicking.rs:511
  11: rust_begin_unwind
             at src/libstd/panicking.rs:419
  12: std::panicking::begin_panic_fmt
             at src/libstd/panicking.rs:373
  13: ra_hir_ty::infer::path::<impl ra_hir_ty::infer::InferenceContext>::infer_path
  14: ra_hir_ty::infer::expr::<impl ra_hir_ty::infer::InferenceContext>::infer_expr_inner
  15: ra_hir_ty::infer::expr::<impl ra_hir_ty::infer::InferenceContext>::infer_expr
  16: ra_hir_ty::infer::expr::<impl ra_hir_ty::infer::InferenceContext>::infer_expr_inner
  17: ra_hir_ty::infer::expr::<impl ra_hir_ty::infer::InferenceContext>::infer_expr_coerce
  18: ra_hir_ty::infer::expr::<impl ra_hir_ty::infer::InferenceContext>::infer_expr_inner
  19: ra_hir_ty::infer::expr::<impl ra_hir_ty::infer::InferenceContext>::infer_expr_coerce
  20: ra_hir_ty::infer::infer_query
  21: salsa::runtime::Runtime<DB>::execute_query_implementation
  22: salsa::derived::slot::Slot<DB,Q,MP>::read_upgrade
  23: salsa::derived::slot::Slot<DB,Q,MP>::read
  24: <salsa::derived::DerivedStorage<DB,Q,MP> as salsa::plumbing::QueryStorageOps<DB,Q>>::try_fetch
  25: ra_hir_ty::db::infer_wait
  26: rust_analyzer::cli::analysis_stats::analysis_stats
  27: rust_analyzer::main
  28: std::rt::lang_start::{{closure}}
  29: std::rt::lang_start_internal::{{closure}}
             at src/libstd/rt.rs:52
  30: std::panicking::try::do_call
             at src/libstd/panicking.rs:331
  31: std::panicking::try
             at src/libstd/panicking.rs:274
  32: std::panic::catch_unwind
             at src/libstd/panic.rs:394
  33: std::rt::lang_start_internal
             at src/libstd/rt.rs:51
  34: main
  35: __libc_start_main
  36: _start

[yaahc]

Here's a log that may help with debugging the above error

RA_LOG=debug,salsa=warn rust-analyzer analysis-stats -o peer::error::from .

I also have one that just sets everything to debug but its 42 MB when compressed so I need to find a way to upload it...

[yaahc]

I took a shot in the dark and managed to get past this one with

-    fn from(source: E) -> Self {
-        Self(Arc::new(PeerError::from(source)))
+    fn from(source: E) -> SharedPeerError {
+        SharedPeerError(Arc::new(PeerError::from(source)))

[yaahc]

It seems like no matter how many ways I try to work around the issue it just keeps popping up like an evil game of whack a mole.

[flodiebold]

Thanks for the reproduction! That it requires the proptest dependency is really weird. I'll try whether I can reduce it a bit further.

Moving the content of set.rs into lib.rs as an inline module instead of an external one

Hmm I just did that and it's still crashing for me. Maybe you made it accidentally not resolve something while doing that?

[flodiebold]

I've got it down to this:

use std::fmt::Debug;

pub trait Future {
    type Output;
}

pub struct PeerSet<D>;

impl<D> Service<Request> for PeerSet<D>
where
    D: Discover,
    D::Key: Debug,
{
    type Error = ();
    type Future = dyn Future<Output = Self::Error>;

    fn call(&mut self) -> Self::Future {
        loop {}
    }
}

pub trait Discover {
    type Key;
}

pub trait Service<Request> {
    type Error;
    type Future: Future<Output = Self::Error>;
    fn call(&mut self) -> Self::Future;
}

but without Debug resolving, it doesn't crash, so I guess it's related to some Debug impl in proptest.

[flodiebold]

Ok, I've got a reproduction that doesn't need proptest:

trait Debug {}

struct Foo<T>;

type E1<T> = (T, T, T);
type E2<T> = E1<E1<E1<(T, T, T)>>>;

impl Debug for Foo<E2<()>> {}

struct Request;

pub trait Future {
    type Output;
}

pub struct PeerSet<D>;

impl<D> Service<Request> for PeerSet<D>
where
    D: Discover,
    D::Key: Debug,
{
    type Error = ();
    type Future = dyn Future<Output = Self::Error>;

    fn call(&mut self) -> Self::Future {
        loop {}
    }
}

pub trait Discover {
    type Key;
}

pub trait Service<Request> {
    type Error;
    type Future: Future<Output = Self::Error>;
    fn call(&mut self) -> Self::Future;
}

I got this by reading the Chalk logs and comparing them to the case where we declare our own Debug trait. There's a very big type somewhere in proptest that has a Debug impl, which I simulated using this Foo type. Then it goes like this:

• we want to normalize Self::Future
• this requires us to prove D::Key: Debug
• we do manage to prove this from the environment; but we also look further for impls. Because D::Key could be anything, we look at all impls for Debug everywhere. This shouldn't happen! Hopefully, with the "semantic/syntactic equality" change in Chalk, it won't anymore.
• we come across the Debug impl for Foo. We try to apply it, but because the type is so big, the type size limit stops us and we return Ambiguous.
• so the whole D::Key: Debug goal is ambiguous. We still manage to normalize Self::Future, but it's also ambiguous, and for some reason that I'm not sure about (and that probably doesn't matter), that causes us to continue solving and run into the crash.

So at least we've got a reproduction that should work in a unit test now; I haven't tried it yet though, it's getting late...

[flodiebold]

As to the actual problem, the Chalk logs say:

: : : : : : : : : : : : : | atv_id = AssociatedTyValueId(1) atv = AssociatedTyValue {
: : : : : : : : : : : : : :     impl_id: ImplId(0),
: : : : : : : : : : : : : :     associated_ty_id: Service::Future,
: : : : : : : : : : : : : :     value: for<type> AssociatedTyValueBound {
: : : : : : : : : : : : : :         ty: dyn for<type> [for<> Implemented(^1.0: Future), for<> AliasEq(<^1.0 as Future>::Output = <PeerSet<^1.0> as Service<Request>>::Error)],
: : : : : : : : : : : : : :     },
: : : : : : : : : : : : : : }

which is already wrong, that ^1.0 in PeerSet<^1.0> should be a ^2.0 since it's supposed to refer to the type parameter of the impl, not the self type of the dyn. So we're returning the wrong type here:
https://github.com/rust-analyzer/rust-analyzer/blob/1ce8c2b5a08949e78de7ff9dfbae594f6c17b951/crates/ra_hir_ty/src/traits/chalk.rs#L417-L418
The next step would be seeing whether ty there is already wrong, or whether the problem is in the to_chalk call (though I'd guess it's ty being wrong). And then going through the lowering code (starting here) to see when it's going wrong.

[yaahc]

Awesome! I'm glad to see you got it to a unit test, that will be a lot easier to work with. As for the next steps, did you want me to take over and look at ty and the lowering code? I ask because I'm not sure if you're pointing out the next steps for your own benefit or so I can pick back up where you left off and I just want to make sure this doesn't get dropped on the ground accidentally.

[flodiebold]

Feel free to take over if you want to, I'll probably only be able to get back to it in a few days.

[flodiebold]

Well, I got to it earlier than I expected :sweat_smile: Turns out it's the same problem as #4885 (which has a much simpler reproduction :weary: ) Knowing that it was specifically related to associated type shorthand, it was pretty easy to find the place where we're not shifting the variables.

[yaahc]

Awesome! I just tried out the branch that fixed this and it got me past the panic i was seeing before but I ran into a new one, looks like a different bug so I'll open a new issue for it.