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

alias bound candidates for opaques allow cyclic reasoning #109387

Open
lcnr opened this issue Mar 20, 2023 · 3 comments
Open

alias bound candidates for opaques allow cyclic reasoning #109387

lcnr opened this issue Mar 20, 2023 · 3 comments
Labels
A-impl-trait Area: `impl Trait`. Universally / existentially quantified anonymous types with static dispatch. A-typesystem Area: The type system C-bug Category: This is a bug. F-type_alias_impl_trait `#[feature(type_alias_impl_trait)]` I-unsound Issue: A soundness hole (worst kind of bug), see: https://en.wikipedia.org/wiki/Soundness requires-nightly This issue requires a nightly compiler in some way. T-compiler Relevant to the compiler team, which will review and decide on the PR/issue. T-types Relevant to the types team, which will review and decide on the PR/issue.

Comments

@lcnr
Copy link
Contributor

lcnr commented Mar 20, 2023

#![feature(type_alias_impl_trait)]

trait Trait<T> {
    type Assoc: Default;
}

type Ty<T> = impl Trait<T>;
    
impl<T> Trait<T> for T {
    type Assoc = <Ty<T> as Trait<T>>::Assoc;
}

#[allow(unused)]
fn define<T>(x: T) -> Ty<T> { x }

fn main() {
    let _ = <() as Trait<()>>::Assoc::default();
}
passes cargo check and results in an ICE
error: internal compiler error: compiler/rustc_middle/src/ty/normalize_erasing_regions.rs:195:90: Failed to normalize fn() -> <Ty<()> as Trait<()>>::Assoc {<<Ty<()> as Trait<()>>::Assoc as std::default::Default>::default}, maybe try to call `try_normalize_erasing_regions` instead

thread 'rustc' panicked at 'Box<dyn Any>', /rustc/da7c50c089d5db2d3ebaf227fe075bb1346bfaec/compiler/rustc_errors/src/lib.rs:1644:9
stack backtrace:
   0:     0x7fccbf4e4c2a - std::backtrace_rs::backtrace::libunwind::trace::h2515acc71f4b7930
                               at /rustc/da7c50c089d5db2d3ebaf227fe075bb1346bfaec/library/std/src/../../backtrace/src/backtrace/libunwind.rs:93:5
   1:     0x7fccbf4e4c2a - std::backtrace_rs::backtrace::trace_unsynchronized::he6766fb71a792b8f
                               at /rustc/da7c50c089d5db2d3ebaf227fe075bb1346bfaec/library/std/src/../../backtrace/src/backtrace/mod.rs:66:5
   2:     0x7fccbf4e4c2a - std::sys_common::backtrace::_print_fmt::h66095118e41b05ee
                               at /rustc/da7c50c089d5db2d3ebaf227fe075bb1346bfaec/library/std/src/sys_common/backtrace.rs:65:5
   3:     0x7fccbf4e4c2a - <std::sys_common::backtrace::_print::DisplayBacktrace as core::fmt::Display>::fmt::h7b02ddcbc50194ff
                               at /rustc/da7c50c089d5db2d3ebaf227fe075bb1346bfaec/library/std/src/sys_common/backtrace.rs:44:22
   4:     0x7fccbf54824e - core::fmt::write::h0189aceee7302cd0
                               at /rustc/da7c50c089d5db2d3ebaf227fe075bb1346bfaec/library/core/src/fmt/mod.rs:1254:17
   5:     0x7fccbf4d79b5 - std::io::Write::write_fmt::h918fabbbac2260c4
                               at /rustc/da7c50c089d5db2d3ebaf227fe075bb1346bfaec/library/std/src/io/mod.rs:1698:15
   6:     0x7fccbf4e49f5 - std::sys_common::backtrace::_print::h41f5e13e972dc45f
                               at /rustc/da7c50c089d5db2d3ebaf227fe075bb1346bfaec/library/std/src/sys_common/backtrace.rs:47:5
   7:     0x7fccbf4e49f5 - std::sys_common::backtrace::print::h1c3c6b0fe82cc982
                               at /rustc/da7c50c089d5db2d3ebaf227fe075bb1346bfaec/library/std/src/sys_common/backtrace.rs:34:9
   8:     0x7fccbf4e776f - std::panicking::default_hook::{{closure}}::hce27f1b648cb1527
                               at /rustc/da7c50c089d5db2d3ebaf227fe075bb1346bfaec/library/std/src/panicking.rs:271:22
   9:     0x7fccbf4e74ab - std::panicking::default_hook::hadee4be0a52a9df6
                               at /rustc/da7c50c089d5db2d3ebaf227fe075bb1346bfaec/library/std/src/panicking.rs:290:9
  10:     0x7fccc273d565 - <rustc_driver_impl[f5bb7a311e11caf0]::DEFAULT_HOOK::{closure#0}::{closure#0} as core[ef02eb5763a621f4]::ops::function::FnOnce<(&core[ef02eb5763a621f4]::panic::panic_info::PanicInfo,)>>::call_once::{shim:vtable#0}
  11:     0x7fccbf4e7fad - <alloc::boxed::Box<F,A> as core::ops::function::Fn<Args>>::call::h0c02084a5fe3170c
                               at /rustc/da7c50c089d5db2d3ebaf227fe075bb1346bfaec/library/alloc/src/boxed.rs:2002:9
  12:     0x7fccbf4e7fad - std::panicking::rust_panic_with_hook::h0498acdcd60e6d9e
                               at /rustc/da7c50c089d5db2d3ebaf227fe075bb1346bfaec/library/std/src/panicking.rs:696:13
  13:     0x7fccc2c775b1 - std[d2fc22aa23273b84]::panicking::begin_panic::<rustc_errors[155c2eed68b88154]::ExplicitBug>::{closure#0}
  14:     0x7fccc2c75096 - std[d2fc22aa23273b84]::sys_common::backtrace::__rust_end_short_backtrace::<std[d2fc22aa23273b84]::panicking::begin_panic<rustc_errors[155c2eed68b88154]::ExplicitBug>::{closure#0}, !>
  15:     0x7fccc2c8a476 - std[d2fc22aa23273b84]::panicking::begin_panic::<rustc_errors[155c2eed68b88154]::ExplicitBug>
  16:     0x7fccc2cec4d6 - std[d2fc22aa23273b84]::panic::panic_any::<rustc_errors[155c2eed68b88154]::ExplicitBug>
  17:     0x7fccc2ceaf76 - <rustc_errors[155c2eed68b88154]::HandlerInner>::bug::<&alloc[146302d0966b713d]::string::String>
  18:     0x7fccc2ceac40 - <rustc_errors[155c2eed68b88154]::Handler>::bug::<&alloc[146302d0966b713d]::string::String>
  19:     0x7fccc2ce2fab - rustc_middle[44f4fa3c07a5b96d]::util::bug::opt_span_bug_fmt::<rustc_span[fc3e3761b6371eb]::span_encoding::Span>::{closure#0}
  20:     0x7fccc2ce19fa - rustc_middle[44f4fa3c07a5b96d]::ty::context::tls::with_opt::<rustc_middle[44f4fa3c07a5b96d]::util::bug::opt_span_bug_fmt<rustc_span[fc3e3761b6371eb]::span_encoding::Span>::{closure#0}, !>::{closure#0}
  21:     0x7fccc2ce19c6 - rustc_middle[44f4fa3c07a5b96d]::ty::context::tls::with_context_opt::<rustc_middle[44f4fa3c07a5b96d]::ty::context::tls::with_opt<rustc_middle[44f4fa3c07a5b96d]::util::bug::opt_span_bug_fmt<rustc_span[fc3e3761b6371eb]::span_encoding::Span>::{closure#0}, !>::{closure#0}, !>
  22:     0x7fccc2ce2ef6 - rustc_middle[44f4fa3c07a5b96d]::util::bug::opt_span_bug_fmt::<rustc_span[fc3e3761b6371eb]::span_encoding::Span>
  23:     0x7fccc0dc86d3 - rustc_middle[44f4fa3c07a5b96d]::util::bug::bug_fmt
  24:     0x7fccc08b296a - <rustc_middle[44f4fa3c07a5b96d]::ty::normalize_erasing_regions::NormalizeAfterErasingRegionsFolder as rustc_type_ir[4e16d9d0ea93f861]::fold::TypeFolder<rustc_middle[44f4fa3c07a5b96d]::ty::context::TyCtxt>>::fold_ty
  25:     0x7fccc122e51a - <rustc_const_eval[7020ac6afbf43f29]::interpret::eval_context::InterpCx<rustc_mir_transform[40d85b965ee1f86e]::const_prop::ConstPropMachine>>::eval_mir_constant
  26:     0x7fccc12250f1 - <rustc_mir_transform[40d85b965ee1f86e]::const_prop_lint::ConstPropagator as rustc_middle[44f4fa3c07a5b96d]::mir::visit::Visitor>::visit_basic_block_data
  27:     0x7fccc1220c89 - <rustc_mir_transform[40d85b965ee1f86e]::const_prop_lint::ConstProp as rustc_mir_transform[40d85b965ee1f86e]::pass_manager::MirLint>::run_lint
  28:     0x7fccc11f78b9 - rustc_mir_transform[40d85b965ee1f86e]::run_analysis_to_runtime_passes
  29:     0x7fccc11f67d1 - rustc_mir_transform[40d85b965ee1f86e]::mir_drops_elaborated_and_const_checked
  30:     0x7fccc11f4c50 - rustc_query_system[fba465ff5df52802]::query::plumbing::try_execute_query::<rustc_query_impl[2a1bc161575ee7a7]::queries::mir_drops_elaborated_and_const_checked, rustc_query_impl[2a1bc161575ee7a7]::plumbing::QueryCtxt>
  31:     0x7fccc1aa2ac2 - rustc_mir_transform[40d85b965ee1f86e]::optimized_mir
  32:     0x7fccc1aa0ccf - rustc_query_system[fba465ff5df52802]::query::plumbing::try_execute_query::<rustc_query_impl[2a1bc161575ee7a7]::queries::optimized_mir, rustc_query_impl[2a1bc161575ee7a7]::plumbing::QueryCtxt>
  33:     0x7fccc15e4eba - rustc_monomorphize[882ebeeb6d5d3a1d]::collector::collect_neighbours
  34:     0x7fccc15e13aa - rustc_monomorphize[882ebeeb6d5d3a1d]::collector::collect_items_rec
  35:     0x7fccc1bdca5a - rustc_data_structures[a666149ac6da9659]::sync::par_for_each_in::<alloc[146302d0966b713d]::vec::Vec<rustc_middle[44f4fa3c07a5b96d]::mir::mono::MonoItem>, rustc_monomorphize[882ebeeb6d5d3a1d]::collector::collect_crate_mono_items::{closure#1}::{closure#0}>
  36:     0x7fccc1bdc6f1 - <rustc_session[1ea5019974f9ef49]::session::Session>::time::<(), rustc_monomorphize[882ebeeb6d5d3a1d]::collector::collect_crate_mono_items::{closure#1}>
  37:     0x7fccc1bdc464 - rustc_monomorphize[882ebeeb6d5d3a1d]::collector::collect_crate_mono_items
  38:     0x7fccc1bda7b0 - rustc_monomorphize[882ebeeb6d5d3a1d]::partitioning::collect_and_partition_mono_items
  39:     0x7fccc1932c82 - rustc_query_system[fba465ff5df52802]::query::plumbing::try_execute_query::<rustc_query_impl[2a1bc161575ee7a7]::queries::collect_and_partition_mono_items, rustc_query_impl[2a1bc161575ee7a7]::plumbing::QueryCtxt>
  40:     0x7fccc193293d - <rustc_query_impl[2a1bc161575ee7a7]::Queries as rustc_middle[44f4fa3c07a5b96d]::ty::query::QueryEngine>::collect_and_partition_mono_items
  41:     0x7fccc1c6c013 - rustc_codegen_ssa[9a4b9ef85533b414]::base::codegen_crate::<rustc_codegen_llvm[5a6ec57f0ad6e07b]::LlvmCodegenBackend>
  42:     0x7fccc1c6bdde - <rustc_codegen_llvm[5a6ec57f0ad6e07b]::LlvmCodegenBackend as rustc_codegen_ssa[9a4b9ef85533b414]::traits::backend::CodegenBackend>::codegen_crate
  43:     0x7fccc19567b1 - <rustc_session[1ea5019974f9ef49]::session::Session>::time::<alloc[146302d0966b713d]::boxed::Box<dyn core[ef02eb5763a621f4]::any::Any>, rustc_interface[9d302fd946af7c88]::passes::start_codegen::{closure#0}>
  44:     0x7fccc19562d9 - rustc_interface[9d302fd946af7c88]::passes::start_codegen
  45:     0x7fccc1953018 - <rustc_middle[44f4fa3c07a5b96d]::ty::context::GlobalCtxt>::enter::<<rustc_interface[9d302fd946af7c88]::queries::Queries>::ongoing_codegen::{closure#0}::{closure#0}, core[ef02eb5763a621f4]::result::Result<alloc[146302d0966b713d]::boxed::Box<dyn core[ef02eb5763a621f4]::any::Any>, rustc_span[fc3e3761b6371eb]::ErrorGuaranteed>>
  46:     0x7fccc1951574 - <rustc_interface[9d302fd946af7c88]::queries::Queries>::ongoing_codegen
  47:     0x7fccc1950b41 - <rustc_interface[9d302fd946af7c88]::interface::Compiler>::enter::<rustc_driver_impl[f5bb7a311e11caf0]::run_compiler::{closure#1}::{closure#2}, core[ef02eb5763a621f4]::result::Result<core[ef02eb5763a621f4]::option::Option<rustc_interface[9d302fd946af7c88]::queries::Linker>, rustc_span[fc3e3761b6371eb]::ErrorGuaranteed>>
  48:     0x7fccc194ec10 - rustc_span[fc3e3761b6371eb]::with_source_map::<core[ef02eb5763a621f4]::result::Result<(), rustc_span[fc3e3761b6371eb]::ErrorGuaranteed>, rustc_interface[9d302fd946af7c88]::interface::run_compiler<core[ef02eb5763a621f4]::result::Result<(), rustc_span[fc3e3761b6371eb]::ErrorGuaranteed>, rustc_driver_impl[f5bb7a311e11caf0]::run_compiler::{closure#1}>::{closure#0}::{closure#0}>
  49:     0x7fccc194e1b9 - std[d2fc22aa23273b84]::sys_common::backtrace::__rust_begin_short_backtrace::<rustc_interface[9d302fd946af7c88]::util::run_in_thread_pool_with_globals<rustc_interface[9d302fd946af7c88]::interface::run_compiler<core[ef02eb5763a621f4]::result::Result<(), rustc_span[fc3e3761b6371eb]::ErrorGuaranteed>, rustc_driver_impl[f5bb7a311e11caf0]::run_compiler::{closure#1}>::{closure#0}, core[ef02eb5763a621f4]::result::Result<(), rustc_span[fc3e3761b6371eb]::ErrorGuaranteed>>::{closure#0}::{closure#0}, core[ef02eb5763a621f4]::result::Result<(), rustc_span[fc3e3761b6371eb]::ErrorGuaranteed>>
  50:     0x7fccc20267ba - <<std[d2fc22aa23273b84]::thread::Builder>::spawn_unchecked_<rustc_interface[9d302fd946af7c88]::util::run_in_thread_pool_with_globals<rustc_interface[9d302fd946af7c88]::interface::run_compiler<core[ef02eb5763a621f4]::result::Result<(), rustc_span[fc3e3761b6371eb]::ErrorGuaranteed>, rustc_driver_impl[f5bb7a311e11caf0]::run_compiler::{closure#1}>::{closure#0}, core[ef02eb5763a621f4]::result::Result<(), rustc_span[fc3e3761b6371eb]::ErrorGuaranteed>>::{closure#0}::{closure#0}, core[ef02eb5763a621f4]::result::Result<(), rustc_span[fc3e3761b6371eb]::ErrorGuaranteed>>::{closure#1} as core[ef02eb5763a621f4]::ops::function::FnOnce<()>>::call_once::{shim:vtable#0}
  51:     0x7fccbf4f1e83 - <alloc::boxed::Box<F,A> as core::ops::function::FnOnce<Args>>::call_once::hc115614f1f0f79d3
                               at /rustc/da7c50c089d5db2d3ebaf227fe075bb1346bfaec/library/alloc/src/boxed.rs:1988:9
  52:     0x7fccbf4f1e83 - <alloc::boxed::Box<F,A> as core::ops::function::FnOnce<Args>>::call_once::h123e851e4d4b5225
                               at /rustc/da7c50c089d5db2d3ebaf227fe075bb1346bfaec/library/alloc/src/boxed.rs:1988:9
  53:     0x7fccbf4f1e83 - std::sys::unix::thread::Thread::new::thread_start::h823b35624605ef69
                               at /rustc/da7c50c089d5db2d3ebaf227fe075bb1346bfaec/library/std/src/sys/unix/thread.rs:108:17
  54:     0x7fccbf3b9609 - start_thread
  55:     0x7fccbf2dc133 - clone
  56:                0x0 - <unknown>

note: we would appreciate a bug report: https://github.com/rust-lang/rust/issues/new?labels=C-bug%2C+I-ICE%2C+T-compiler&template=ice.md

note: rustc 1.70.0-nightly (da7c50c08 2023-03-19) running on x86_64-unknown-linux-gnu

note: compiler flags: --crate-type bin -C embed-bitcode=no -C codegen-units=1 -C debuginfo=2

note: some of the compiler flags provided by cargo are hidden

query stack during panic:
#0 [mir_drops_elaborated_and_const_checked] elaborating drops for `main`
#1 [optimized_mir] optimizing MIR for `main`
#2 [collect_and_partition_mono_items] collect_and_partition_mono_items
end of query stack
error: could not compile `playground` (bin "playground")

This has the same underlying reason as the unsoundness for super traits with coinduction and alias bound for projections. To my knowledge none of these issues are exploitable on stable right now though.

This relies on the following unsound circular reasoning:

  • the impl of Trait<T> for T relies on the item bound Ty<T>: Trait<T>
  • proving the item bounds for the underlying type of Ty<T> (T) uses the impl
@lcnr lcnr added A-typesystem Area: The type system I-unsound Issue: A soundness hole (worst kind of bug), see: https://en.wikipedia.org/wiki/Soundness C-bug Category: This is a bug. F-type_alias_impl_trait `#[feature(type_alias_impl_trait)]` requires-nightly This issue requires a nightly compiler in some way. T-types Relevant to the types team, which will review and decide on the PR/issue. labels Mar 20, 2023
@lcnr
Copy link
Contributor Author

lcnr commented Mar 20, 2023

it's probably possible to get a segfault at runtime from this instead, but thinking about circular reasoning like this is hard so I am satisfied with an ICE for now.

@Noratrieb Noratrieb added the T-compiler Relevant to the compiler team, which will review and decide on the PR/issue. label Apr 5, 2023
@lcnr
Copy link
Contributor Author

lcnr commented Jun 8, 2023

A proposed solution was to recheck the opaque for well-formedness with Reveal::All. This check probably still needs to handle region obligations as we can otherwise end up with unproven outlives bounds.

@lcnr
Copy link
Contributor Author

lcnr commented Jul 2, 2023

it's probably possible to get a segfault at runtime from this instead, but thinking about circular reasoning like this is hard so I am satisfied with an ICE for now.

This is surprisingly hard: taking the known issue for projections in the new solver lcnr/solver-woes#9 (comment), we instead overflow because instantiating Tait with String requires a nested String: Copy bound which we again prove using the alias bound on Tait, resulting in a cycle https://rust.godbolt.org/z/41cM1snx5

// compile-flags: -Ztrait-solver=next
#![feature(type_alias_impl_trait)]

mod define {
    pub type Tait where Tait: Copy = impl Copy;
    fn define() -> Tait
    where
        Tait: Copy
    {
        String::new()
    }
}
fn copy(x: &define::Tait) -> define::Tait {
    *x
}

using a coinductive trait currently also doesn't compile though I am unsure why https://rust.godbolt.org/z/xncdcecWY

// compile-flags: -Ztrait-solver=next
#![feature(rustc_attrs, type_alias_impl_trait)]

#[rustc_coinductive]
trait Trait {
    fn mk() -> Self;
}

mod define {
    use super::*;
    pub type Tait where Tait: Trait = impl Trait;
    fn define() -> Tait
    where
        Tait: Trait
    {}
}
fn make() -> define::Tait {
    Trait::mk()
}

@lcnr lcnr added the A-impl-trait Area: `impl Trait`. Universally / existentially quantified anonymous types with static dispatch. label Oct 11, 2023
@lcnr lcnr changed the title alias bound candidates for opaques are unsound alias bound candidates for opaques allow cyclic reasoning Nov 15, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
A-impl-trait Area: `impl Trait`. Universally / existentially quantified anonymous types with static dispatch. A-typesystem Area: The type system C-bug Category: This is a bug. F-type_alias_impl_trait `#[feature(type_alias_impl_trait)]` I-unsound Issue: A soundness hole (worst kind of bug), see: https://en.wikipedia.org/wiki/Soundness requires-nightly This issue requires a nightly compiler in some way. T-compiler Relevant to the compiler team, which will review and decide on the PR/issue. T-types Relevant to the types team, which will review and decide on the PR/issue.
Projects
None yet
Development

No branches or pull requests

2 participants