Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

ICE when trying to match on non-PartialEq slice. #61188

Closed
matthewjasper opened this issue May 25, 2019 · 16 comments · Fixed by #62339
Closed

ICE when trying to match on non-PartialEq slice. #61188

matthewjasper opened this issue May 25, 2019 · 16 comments · Fixed by #62339
Assignees
Labels
A-MIR Area: Mid-level IR (MIR) - https://blog.rust-lang.org/2016/04/19/MIR.html C-bug Category: This is a bug. glacier ICE tracked in rust-lang/glacier. I-ICE Issue: The compiler panicked, giving an Internal Compilation Error (ICE) ❄️ P-high High priority T-compiler Relevant to the compiler team, which will review and decide on the PR/issue.

Comments

@matthewjasper
Copy link
Contributor

matthewjasper commented May 25, 2019

The following code will result in an ICE in codegen MIR construction:

struct B(i32);

const A: &[B] = &[];

fn main() {
    match &[][..] {
        A => (),
        _ => (),
    }
}

playground

Error and Backtrace
error: internal compiler error: src/librustc/traits/codegen/mod.rs:156: Encountered errors `[FulfillmentError(Obligation(predicate=Binder(TraitPredicate(<B as std::cmp::PartialEq>)),depth=2),Unimplemented)]` resolving bounds after type-checking

thread 'rustc' panicked at 'Box<Any>', src/librustc_errors/lib.rs:570:9
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.
stack backtrace:

 0: std::sys::unix::backtrace::tracing::imp::unwind_backtrace
             at src/libstd/sys/unix/backtrace/tracing/gcc_s.rs:39
   1: std::sys_common::backtrace::_print
             at src/libstd/sys_common/backtrace.rs:71
   2: std::panicking::default_hook::{{closure}}
             at src/libstd/sys_common/backtrace.rs:59
             at src/libstd/panicking.rs:197
   3: std::panicking::default_hook
             at src/libstd/panicking.rs:211
   4: rustc::util::common::panic_hook
   5: std::panicking::rust_panic_with_hook
             at src/libstd/panicking.rs:478
   6: std::panicking::begin_panic
   7: rustc_errors::Handler::span_bug
   8: rustc::util::bug::opt_span_bug_fmt::{{closure}}
   9: rustc::ty::context::tls::with_opt::{{closure}}
  10: rustc::ty::context::tls::with_context_opt
  11: rustc::ty::context::tls::with_opt
  12: rustc::util::bug::opt_span_bug_fmt
  13: rustc::util::bug::span_bug_fmt
  14: rustc::traits::codegen::<impl rustc::infer::InferCtxt>::drain_fulfillment_cx_or_panic
  15: rustc::ty::context::GlobalCtxt::enter_local
  16: rustc::traits::codegen::codegen_fulfill_obligation
  17: rustc::ty::query::__query_compute::codegen_fulfill_obligation
  18: rustc::ty::query::<impl rustc::ty::query::config::QueryAccessors for rustc::ty::query::queries::codegen_fulfill_obligation>::compute
  19: rustc::dep_graph::graph::DepGraph::with_task_impl
  20: rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt>::get_query
  21: rustc::ty::instance::Instance::resolve
  22: rustc_mir::lints::check
  23: rustc::ty::context::GlobalCtxt::enter_local
  24: rustc_mir::build::mir_build
  25: rustc_mir::transform::mir_built
  26: rustc::ty::query::__query_compute::mir_built
  27: rustc::ty::query::<impl rustc::ty::query::config::QueryAccessors for rustc::ty::query::queries::mir_built>::compute
  28: rustc::dep_graph::graph::DepGraph::with_task_impl
  29: rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt>::get_query
  30: rustc_mir::transform::check_unsafety::unsafety_check_result
  31: rustc::ty::query::__query_compute::unsafety_check_result
  32: rustc::ty::query::<impl rustc::ty::query::config::QueryAccessors for rustc::ty::query::queries::unsafety_check_result>::compute
  33: rustc::dep_graph::graph::DepGraph::with_task_impl
  34: rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt>::get_query
  35: rustc_mir::transform::mir_const
  36: rustc::ty::query::__query_compute::mir_const
  37: rustc::ty::query::<impl rustc::ty::query::config::QueryAccessors for rustc::ty::query::queries::mir_const>::compute
  38: rustc::dep_graph::graph::DepGraph::with_task_impl
  39: rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt>::get_query
  40: rustc_mir::transform::mir_validated
  41: rustc::ty::query::__query_compute::mir_validated
  42: rustc::ty::query::<impl rustc::ty::query::config::QueryAccessors for rustc::ty::query::queries::mir_validated>::compute
  43: rustc::dep_graph::graph::DepGraph::with_task_impl
  44: rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt>::get_query
  45: rustc_mir::borrow_check::mir_borrowck
  46: rustc::ty::query::__query_compute::mir_borrowck
  47: rustc::ty::query::<impl rustc::ty::query::config::QueryAccessors for rustc::ty::query::queries::mir_borrowck>::compute
  48: rustc::dep_graph::graph::DepGraph::with_task_impl
  49: rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt>::get_query
  50: rustc::ty::<impl rustc::ty::context::TyCtxt>::par_body_owners
  51: rustc::util::common::time
  52: rustc_interface::passes::analysis
  53: rustc::ty::query::__query_compute::analysis
  54: rustc::ty::query::<impl rustc::ty::query::config::QueryAccessors for rustc::ty::query::queries::analysis>::compute
  55: rustc::dep_graph::graph::DepGraph::with_task_impl
  56: rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt>::get_query
  57: rustc_interface::passes::BoxedGlobalCtxt::access::{{closure}}
  58: rustc_interface::passes::create_global_ctxt::{{closure}}
  59: rustc_interface::interface::run_compiler_in_existing_thread_pool
  60: std::thread::local::LocalKey<T>::with
  61: scoped_tls::ScopedKey<T>::set
  62: syntax::with_globals
query stack during panic:
#0 [codegen_fulfill_obligation] checking if `std::cmp::PartialEq` fulfills its obligations
#1 [mir_built] processing `main`
#2 [unsafety_check_result] processing `main`
#3 [mir_const] processing `main`
#4 [mir_validated] processing `main`
#5 [mir_borrowck] processing `main`
#6 [analysis] running analysis passes on this crate
end of query stack
@matthewjasper matthewjasper added the I-ICE Issue: The compiler panicked, giving an Internal Compilation Error (ICE) ❄️ label May 25, 2019
@jonas-schievink jonas-schievink added C-bug Category: This is a bug. I-nominated T-compiler Relevant to the compiler team, which will review and decide on the PR/issue. labels May 25, 2019
@estebank
Copy link
Contributor

CC #53708

@pnkfelix pnkfelix added the A-MIR Area: Mid-level IR (MIR) - https://blog.rust-lang.org/2016/04/19/MIR.html label Jun 6, 2019
@pnkfelix
Copy link
Member

pnkfelix commented Jun 6, 2019

As implied by @estebank above, this seems very likely to be a duplicate (or at least strongly related to) #53708 ...

Update: Not duplicate. Further investigation of #53708 shows that it is no longer an ICE, but "merely" an exhaustiveness checker bug. This bug, #61188, remains an ICE today.

@pnkfelix
Copy link
Member

pnkfelix commented Jun 6, 2019

Ah ha!

If you add #[derive(PartialEq, Eq)] to the struct B(i32) in the example above, then the code compiles successfully.

Which may be something a user might infer from the message ...

Encountered errors [FulfillmentError(Obligation(predicate=Binder(TraitPredicate(<B as std::cmp::PartialEq>)),depth=2),Unimplemented)]

... but probably not 🤣

@pnkfelix
Copy link
Member

pnkfelix commented Jun 6, 2019

triage: P-high; removing nomination. I want to know why we are not catching the failure to fulfill B: PartialEq earlier in the compilation. Is this perhaps a const-eval issue, based on the stack trace? (or a mir-borrowck one? I suppose the query-system is just making that appear on the stack, though it is not necessarily the root cause?)

@pnkfelix pnkfelix added P-high High priority and removed I-nominated labels Jun 6, 2019
@eddyb
Copy link
Member

eddyb commented Jun 6, 2019

I suspect rustc_typeck is not enforcing it, and MIR borrowck, as I found recently, doesn't produce user errors from trait matching, but rather expects it to succeed, and only uses it to get lifetime obligations.

EDIT: I should've read more carefully, looks like Instance::resolve is being used by rustc_mir::build without rustc_typeck having checked that Eq is implemented for that type.

@pnkfelix
Copy link
Member

pnkfelix commented Jun 6, 2019

assigning to self with intent to try to mentor.

@pnkfelix pnkfelix self-assigned this Jun 6, 2019
@jonas-schievink jonas-schievink added the E-mentor Call for participation: This issue has a mentor. Use #t-compiler/help on Zulip for discussion. label Jun 6, 2019
@pnkfelix
Copy link
Member

pnkfelix commented Jul 2, 2019

I started looking at this, with the intent of writing mentorship notes. I'm going to try to jot down notes on my process as I go, with the intent of showing a mentee what kinds of experiments one might do to figure out how to narrow down the code to the point of interest for finding a fix.

To be clear, I don't consider myself an expert in the MIR generation code; I've done some work in it, but I am at a point where I need to reacquaint myself with it before I'd feel comfortable hacking on it.

So, here's the steps I've done so far:

  1. Copy the test case into its own file (I named mine issue-61188-match-nonpartialeq-graceful.rs). I ran rustc on that, using RUST_BACKTRACE=1 again just to confirm that it still fails, and to skim over the lines of code that panicked in context.
  2. Based on @eddyb's comment above, I decided I need to see some RUSTC_LOG output from the modules in question. So I ran rustc again, first using RUST_LOG=rustc::ty::instance,rustc_mir::build, and then after seing no debug output, using RUSTC_LOG=rustc::ty::instance,rustc_mir::build instead. (I keep forgetting that we renamed the environment variable back in PR Rename RUST_LOG to RUSTC_LOG #60401.)
  3. After skimming over the log and deciding I wanted to focus on instances of constants mentioned in the output of match processing, I loaded the log output into emacs, used M-x highlight-regexp to highlight all instances of kind: Constant { value: Const, and then starting searching for the instances of that string.
  4. I happened to notice one of the relevant lines said it was a test with kind: Eq. For some reason I had forgotten (or never knew about) this variant of TestKind, shown here:
    /// Test for equality with value, possibly after an unsizing coercion to
    /// `ty`,
    Eq {
    value: &'tcx ty::Const<'tcx>,
    // Integer types are handled by `SwitchInt`, and constants with ADT
    // types are converted back into patterns, so this can only be `&str`,
    // `&[T]`, `f32` or `f64`.
    ty: Ty<'tcx>,
    },

Look at that comment (added back in df3de7b, many thanks @matthewjasper!); the fact that you see three types that really can be hard-coded into the compiler, and then one special case of &[T] is super-subtle, and perhaps a little suspicious.

That's where I decided I wanted to start taking some notes, since arguably I was supposed to be making mentorship instructions for this, but if I get further into the weeds without documenting the context, I won't be able to make sensible instructions.

@pnkfelix
Copy link
Member

pnkfelix commented Jul 2, 2019

To be clear, the reason that I saw the TestKind::Eq variant as a good place to take a note is because I see that as opening up a useful thing to search for in the code base (to find spots where that variant is created), and then do one of two thingss:

Either:

  1. Add a check, right before creating TestKind::Eq, that the given type implements PartialEq, or
  2. If it is still to late at this point to add said check, then use the context of where TestKind::Eq is created to figure out the shape of the data structure that we have in our hands, so that we can add the necessary check earlier in the compiler control flow, or
  3. (a new option i hadn't considered until now): change the code generation so that T is converted back into a pattern just as ADT types are if T is not generated by the grammar U ::= &str | f32 | f64 | &[U].

@pnkfelix
Copy link
Member

pnkfelix commented Jul 2, 2019

And reading over rust-lang/rfcs#1445 led me to find that the current code (linked below) for linting use of #[structural_match] is, well, insufficient: it special cases matching Adt consts and matching &Adt consts, but fails to handle & &Adt consts and &[Adt] consts, etc.

ty::Adt(adt_def, _) if !self.tcx.has_attr(adt_def.did, sym::structural_match) => {
let path = self.tcx.def_path_str(adt_def.did);
let msg = format!(
"to use a constant of type `{}` in a pattern, \
`{}` must be annotated with `#[derive(PartialEq, Eq)]`",
path,
path,
);
self.tcx.sess.span_err(span, &msg);
PatternKind::Wild
}
ty::Ref(_, ty::TyS { sty: ty::Adt(adt_def, _), .. }, _)
if !self.tcx.has_attr(adt_def.did, sym::structural_match) => {
// HACK(estebank): Side-step ICE #53708, but anything other than erroring here
// would be wrong. Returnging `PatternKind::Wild` is not technically correct.
let path = self.tcx.def_path_str(adt_def.did);
let msg = format!(
"to use a constant of type `{}` in a pattern, \
`{}` must be annotated with `#[derive(PartialEq, Eq)]`",
path,
path,
);
self.tcx.sess.span_err(span, &msg);
PatternKind::Wild
}

@pnkfelix
Copy link
Member

pnkfelix commented Jul 2, 2019

Filed #62307 to track the insufficient check for #[structural_match].

@pnkfelix
Copy link
Member

pnkfelix commented Jul 3, 2019

(the change suggested in PR #62339 fixes this and has a regression test for it.)

bors added a commit that referenced this issue Jul 10, 2019
…l-match-check, r=nikomatsakis

use visitor for #[structural_match] check

This changes the code so that we recur down the structure of a type of a const (rather than just inspecting at a shallow one or two levels) when we are looking to see if it has an ADT that did not derive `PartialEq` and `Eq`.

Fix #61188

Fix #62307

Cc #62336
@matthewjasper
Copy link
Contributor Author

Reopening because there are still cases where we ICE:

#![deny(indirect_structural_match)]

#[derive(PartialEq, Eq)]
enum O<T> {
    Some(*const T), // Can also use PhantomData<T>
    None,
}

struct B;

const C: &[O<B>] = &[O::None];

pub fn foo() {
    let x = O::None;
    match &[x][..] {
        C => (),
        _ => (),
    }
}

We might want to move to a trait based approach as in #63248 (comment)

@pnkfelix
Copy link
Member

visiting for triage. I agree with @matthewjasper about potentially moving to a trait-based approach.

part of me is tempted to jump into implementing that. But it probably makes more sense for me to write up mentorship instructions, maybe.

@pnkfelix pnkfelix added E-needs-mentor and removed E-mentor Call for participation: This issue has a mentor. Use #t-compiler/help on Zulip for discussion. labels Oct 3, 2019
@pnkfelix pnkfelix added E-mentor Call for participation: This issue has a mentor. Use #t-compiler/help on Zulip for discussion. E-needs-mentor and removed E-needs-mentor E-mentor Call for participation: This issue has a mentor. Use #t-compiler/help on Zulip for discussion. labels Oct 3, 2019
@pnkfelix
Copy link
Member

pnkfelix commented Oct 3, 2019

triage: this is probably easy to resolve but I have not had time myself to write up mentorship instructions. Marking bug accordingly (i.e. "need-mentor" is to be interpreted as "if you are willing to help make some instructions, I'd love it...")

@pnkfelix
Copy link
Member

pnkfelix commented Oct 8, 2019

Note: moving to a trait-based approach alone won't resolve every ICE. Not without regressing other stable code, least.

In particular:

I discovered this while exploring cases related to #63438 and #63479

Here is a concrete example (play):

fn assert_partialeq<T: PartialEq>(_: &T) {}

fn rquux(_: &()) { }
const RQ: fn(&()) = rquux;
const LRQ: &[fn(&())] = &[];

fn main() {
    // assert_partialeq(&RQ); (RQ isn't PartialEq, and this will say so.)

    match RQ {
        RQ => println!("RQ"),
        _ => {}
    };

    let input: &[fn(&())] = &[][..];
    match input {
        LRQ => println!("LRQ"), // compiles if you comment this out
        &[] => println!("matched inlined pattern"),
        _ => {}
    };
}

(The "obvious solution" of just requiring const patterns to always implement PartialEq will break the matching of RQ, which is why we can't just adopt that solution.)

pnkfelix added a commit to pnkfelix/rust that referenced this issue Oct 14, 2019
…ructural` trait.

As far as I can tell this preserves previous observable stable behavior,
*including* the ICE from rust-lang#61188.

(In other words, further work is necessary to reap benefits of switching to a
trait.)
pnkfelix added a commit to pnkfelix/rust that referenced this issue Oct 14, 2019
…ewjasper's example.

specific example is from [comment][]:

[comment]: rust-lang#61188 (comment)

```rust
#![deny(indirect_structural_match)]

#[derive(PartialEq, Eq)]
enum O<T> {
    Some(*const T), // Can also use PhantomData<T>
    None,
}

struct B;

const C: &[O<B>] = &[O::None];

pub fn foo() {
    let x = O::None;
    match &[x][..] {
        C => (),
        _ => (),
    }
}
```
@rust-lang-glacier-bot rust-lang-glacier-bot added the glacier ICE tracked in rust-lang/glacier. label Oct 15, 2019
@pnkfelix
Copy link
Member

(closing this bug so we can let issue #65466 be dedicated to tracking the more subtle problem laid out in @matthewjasper 's comment above.)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
A-MIR Area: Mid-level IR (MIR) - https://blog.rust-lang.org/2016/04/19/MIR.html C-bug Category: This is a bug. glacier ICE tracked in rust-lang/glacier. I-ICE Issue: The compiler panicked, giving an Internal Compilation Error (ICE) ❄️ P-high High priority T-compiler Relevant to the compiler team, which will review and decide on the PR/issue.
Projects
None yet
Development

Successfully merging a pull request may close this issue.

6 participants