Compiler #94735

hummingly · 2022-03-08T14:25:46Z

Rust-analyzer as well as the compiler fail to emit an error for map_page_indices. It seems like the impl before makes the compiler ignore it. If I remove the first impl of SparseTreeSet, a compile error is output as usual. Also cargo clean does not solve the issue. However, I cannot test on a more recent nightly as the hospital wifi is too slow.

Edit 1: Minimized the code more.
Edit 2: Problems seems to be that the compiler does not see that I forgot to add parentheses around a pair values and it just assumes they are tuples.

Code

use std::{
    collections::hash_map::DefaultHasher,
    hash::{Hash, Hasher},
    marker::PhantomData,
};

pub struct SparseTreeSet<K, V> {
    sparse: Vec<Bucket>,
    dense: Vec<u64>,
    relations: Vec<Relation>,
    values: Vec<V>,
    _key_marker: PhantomData<K>,
}

pub struct Relation {
    parent: u32,
    prev_sibling: u32,
    next_sibling: u32,
    children_count: u32,
}

type Bucket = Option<Box<Chunk>>;

#[derive(Clone)]
struct Chunk([u32; PAGE_SIZE as usize]);

const PAGE_BITS: u32 = 5;
const PAGE_SIZE: u32 = 2u32.pow(PAGE_BITS);

const NULL: u32 = u32::MAX;

impl<K: Hash, V> SparseTreeSet<K, V> {
    pub fn subtree(&self, key: &K) -> Option<(&[Relation], &[V])> {
        let start = self.get_index(key)?;
        let end = self.get_subtree_end(start).cast();
        Some(
            &self.relations[start.cast()..end],
            &self.values[start.cast()..end],
        )
    }
}

impl<K, V> SparseTreeSet<K, V> {
    fn get_subtree_end(&self, index: u32) -> u32 {
        let start = index.cast();
        let next_sibling = self.relations[start].next_sibling;
        let len = self.relations.len();
        if next_sibling > index && next_sibling < len.truncate() {
            self.relations[start].next_sibling
        } else {
            let mut offset = self.relations[start].children_count.cast() + 1;
            while offset < len && !(self.relations[offset].prev_sibling <= index) {
                offset += self.relations[offset].children_count.cast() + 1;
            }
            offset.truncate()
        }
    }

    fn get_index(&self, key: &impl Hash) -> Option<u32> {
        let key_index = hash_key(key);
        let (page, page_index) = map_page_indices(key_index);
        self.sparse.get(page).and_then(|bucket| {
            bucket
                .as_ref()
                .and_then(|b| (b[page_index] != NULL).then(|| b[page_index]))
        })
    }
}

fn hash_key(key: &impl Hash) -> u64 {
    let mut hasher = DefaultHasher::new();
    key.hash(&mut hasher);
    hasher.finish()
}

fn map_page_indices(key_index: u64) -> (usize, usize) {
    let page = (key_index >> PAGE_BITS).cast();
    let page_index = (key_index & (PAGE_SIZE - 1)).cast();
    (page, page_index)
}

trait SafeCast<T> {
    fn cast(self) -> T;
}

impl SafeCast<usize> for u32 {
    fn cast(self) -> usize {
        self as usize
    }
}

Error output

error: internal compiler error: compiler\rustc_typeck\src\check\fn_ctxt\_impl.rs:318:26: while adjusting Expr { hir_id: HirId { owner: DefId(0:338 ~ allusion_proto[9561]::tree::{impl#0}::subtree), local_id: 44 }, kind: Path(Resolved(None, Path { span: src\tree.rs:37:14: 37:18 (#0), res: Local(HirId { 
owner: DefId(0:338 ~ allusion_proto[9561]::tree::{impl#0}::subtree), local_id: 2 }), segments: [PathSegment { ident: self#0, hir_id: Some(HirId { owner: DefId(0:338 ~ allusion_proto[9561]::tree::{impl#0}::subtree), local_id: 43 }), res: Some(Local(HirId { owner: DefId(0:338 ~ allusion_proto[9561]::tree::{impl#0}::subtree), local_id: 2 })), args: None, infer_args: true }] })), span: src\tree.rs:37:14: 37:18 (#0) }, can't compose [Deref(None) -> SparseTreeSet<K, V>] and [Deref(None) -> SparseTreeSet<K, V>]

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

note: the compiler unexpectedly panicked. this is a bug.

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.60.0-nightly (71226d717 2022-02-04) running on x86_64-pc-windows-msvc

note: compiler flags: --crate-type lib -C embed-bitcode=no -C debuginfo=2 -C incremental

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

query stack during panic:
#0 [typeck] type-checking `tree::<impl at src\tree.rs:32:1: 41:2>::subtree`
#1 [typeck_item_bodies] type-checking all item bodies
#2 [analysis] running analysis passes on this crate
end of query stack
error: could not compile `allusion-proto`

Backtrace

error: internal compiler error: compiler\rustc_typeck\src\check\fn_ctxt\_impl.rs:318:26: while adjusting Expr { hir_id: HirId { owner: DefId(0:338 ~ allusion_proto[9561]::tree::{impl#0}::subtree), local_id: 44 }, kind: Path(Resolved(None, Path { span: src\tree.rs:37:14: 37:18 (#0), res: Local(HirId { 
owner: DefId(0:338 ~ allusion_proto[9561]::tree::{impl#0}::subtree), local_id: 2 }), segments: [PathSegment { ident: self#0, hir_id: Some(HirId { owner: DefId(0:338 ~ allusion_proto[9561]::tree::{impl#0}::subtree), local_id: 43 }), res: Some(Local(HirId { owner: DefId(0:338 ~ allusion_proto[9561]::tree::{impl#0}::subtree), local_id: 2 })), args: None, infer_args: true }] })), span: src\tree.rs:37:14: 37:18 (#0) }, can't compose [Deref(None) -> SparseTreeSet<K, V>] and [Deref(None) -> SparseTreeSet<K, V>]

thread 'rustc' panicked at 'Box<dyn Any>', compiler\rustc_errors\src\lib.rs:1160:9
stack backtrace:
   0:     0x7ff943e06ff0 - <std::sys_common::backtrace::_print::DisplayBacktrace as core::fmt::Display>::fmt::hb244e4499743fa60
   1:     0x7ff943e3664a - core::fmt::write::he386a1321de23221
   2:     0x7ff943df7ee8 - <std::io::IoSlice as core::fmt::Debug>::fmt::h9109705453d96e26
   3:     0x7ff943e0a907 - std::panicking::default_hook::h1c664fc771e7229c
   4:     0x7ff943e0a4c3 - std::panicking::default_hook::h1c664fc771e7229c
   5:     0x7ff93012b1d6 - <rustc_middle[9de57e7aee5035b7]::ty::SymbolName as core[1bfa7175043acf8b]::fmt::Debug>::fmt
   6:     0x7ff943e0b1ec - std::panicking::rust_panic_with_hook::h99f63b579d29370e
   7:     0x7ff9347a2d65 - <rustc_feature[54a509b25cc73755]::builtin_attrs::AttributeType as core[1bfa7175043acf8b]::fmt::Debug>::fmt
   8:     0x7ff9347a2d19 - <rustc_feature[54a509b25cc73755]::builtin_attrs::AttributeType as core[1bfa7175043acf8b]::fmt::Debug>::fmt
   9:     0x7ff934aa7f01 - rustc_query_system[4edc07398fadc0dc]::query::job::report_cycle
  10:     0x7ff9347db830 - <rustc_errors[c875eb3d3ed35e22]::ErrorReported as core[1bfa7175043acf8b]::fmt::Debug>::fmt
  11:     0x7ff9347d8267 - <rustc_errors[c875eb3d3ed35e22]::HandlerInner>::emit_diagnostic
  12:     0x7ff9347d580e - <rustc_errors[c875eb3d3ed35e22]::Handler>::bug
  13:     0x7ff9344b353f - <rustc_middle[9de57e7aee5035b7]::ty::vtable::VtblEntry as core[1bfa7175043acf8b]::fmt::Debug>::fmt
  14:     0x7ff9344b3db9 - <rustc_middle[9de57e7aee5035b7]::ty::vtable::VtblEntry as core[1bfa7175043acf8b]::fmt::Debug>::fmt
  15:     0x7ff934a9dca0 - rustc_middle[9de57e7aee5035b7]::util::bug::bug_fmt
  16:     0x7ff932a0fcc5 - <rustc_typeck[9523f0690178aed4]::check::fn_ctxt::FnCtxt>::apply_adjustments
  17:     0x7ff9329bcfba - <rustc_typeck[9523f0690178aed4]::check::fn_ctxt::FnCtxt>::check_for_cast
  18:     0x7ff932a09405 - <rustc_typeck[9523f0690178aed4]::check::fn_ctxt::FnCtxt>::check_expr_with_expectation
  19:     0x7ff9329b4518 - <rustc_typeck[9523f0690178aed4]::check::fn_ctxt::FnCtxt>::check_for_cast
  20:     0x7ff932a094a6 - <rustc_typeck[9523f0690178aed4]::check::fn_ctxt::FnCtxt>::check_expr_with_expectation
  21:     0x7ff9329b4518 - <rustc_typeck[9523f0690178aed4]::check::fn_ctxt::FnCtxt>::check_for_cast
  22:     0x7ff932a0bcd5 - <rustc_typeck[9523f0690178aed4]::check::fn_ctxt::FnCtxt>::check_expr_with_expectation
  23:     0x7ff9329b4518 - <rustc_typeck[9523f0690178aed4]::check::fn_ctxt::FnCtxt>::check_for_cast
  24:     0x7ff9329c92d1 - <rustc_typeck[9523f0690178aed4]::check::fn_ctxt::FnCtxt>::structurally_resolved_type
  25:     0x7ff93299bbe0 - <rustc_typeck[9523f0690178aed4]::check::fn_ctxt::FnCtxt>::check_call
  26:     0x7ff9329985f7 - <rustc_typeck[9523f0690178aed4]::check::fn_ctxt::FnCtxt>::check_call
  27:     0x7ff932a0902d - <rustc_typeck[9523f0690178aed4]::check::fn_ctxt::FnCtxt>::check_expr_with_expectation
  28:     0x7ff9329b4518 - <rustc_typeck[9523f0690178aed4]::check::fn_ctxt::FnCtxt>::check_for_cast
  29:     0x7ff9329ceb57 - <rustc_typeck[9523f0690178aed4]::check::fn_ctxt::FnCtxt>::check_block_no_value
  30:     0x7ff9329b4518 - <rustc_typeck[9523f0690178aed4]::check::fn_ctxt::FnCtxt>::check_for_cast
  31:     0x7ff9329b5404 - <rustc_typeck[9523f0690178aed4]::check::fn_ctxt::FnCtxt>::check_for_cast
  32:     0x7ff932c2aaa9 - <rustc_typeck[9523f0690178aed4]::variance::constraints::ConstraintContext as rustc_hir[33c483301c74e140]::itemlikevisit::ItemLikeVisitor>::visit_foreign_item
  33:     0x7ff932af7964 - <rustc_typeck[9523f0690178aed4]::check::op::Op as core[1bfa7175043acf8b]::fmt::Debug>::fmt
  34:     0x7ff932ab4818 - rustc_typeck[9523f0690178aed4]::check::provide
  35:     0x7ff9338f6a0f - <rustc_query_impl[45d3f46ffcc7d851]::on_disk_cache::EncodedSourceFileId as core[1bfa7175043acf8b]::fmt::Debug>::fmt
  36:     0x7ff93385dae0 - <rustc_query_impl[45d3f46ffcc7d851]::on_disk_cache::EncodedSourceFileId as core[1bfa7175043acf8b]::fmt::Debug>::fmt
  37:     0x7ff93374eab0 - <rustc_query_impl[45d3f46ffcc7d851]::Queries>::as_dyn
  38:     0x7ff9335b13d2 - <rustc_mir_dataflow[7dd8cfc28066c66d]::framework::engine::RustcMirAttrs>::output_path
  39:     0x7ff9336f70d5 - <rustc_mir_dataflow[7dd8cfc28066c66d]::framework::engine::RustcMirAttrs>::output_path
  40:     0x7ff932b49b8e - <<dyn rustc_typeck[9523f0690178aed4]::astconv::AstConv>::create_substs_for_ast_path::SubstsForAstPathCtxt as rustc_typeck[9523f0690178aed4]::astconv::CreateSubstsForGenericArgsCtxt>::inferred_kind
  41:     0x7ff932aba7d3 - <rustc_typeck[9523f0690178aed4]::check::CheckItemTypesVisitor as rustc_hir[33c483301c74e140]::itemlikevisit::ItemLikeVisitor>::visit_item
  42:     0x7ff9338f9644 - <rustc_query_impl[45d3f46ffcc7d851]::on_disk_cache::EncodedSourceFileId as core[1bfa7175043acf8b]::fmt::Debug>::fmt
  43:     0x7ff93388900d - <rustc_query_impl[45d3f46ffcc7d851]::on_disk_cache::EncodedSourceFileId as core[1bfa7175043acf8b]::fmt::Debug>::fmt
  44:     0x7ff933753d7a - <rustc_query_impl[45d3f46ffcc7d851]::Queries>::as_dyn
  45:     0x7ff93364b8de - <rustc_mir_dataflow[7dd8cfc28066c66d]::framework::engine::RustcMirAttrs>::output_path
  46:     0x7ff9336c8955 - <rustc_mir_dataflow[7dd8cfc28066c66d]::framework::engine::RustcMirAttrs>::output_path
  47:     0x7ff932ac5aec - <rustc_typeck[9523f0690178aed4]::check::PlaceOp as core[1bfa7175043acf8b]::fmt::Debug>::fmt
  48:     0x7ff932a7ae75 - rustc_typeck[9523f0690178aed4]::check_crate
  49:     0x7ff93023cbbf - rustc_interface[feeab83c02a6685a]::passes::analysis
  50:     0x7ff9338f9194 - <rustc_query_impl[45d3f46ffcc7d851]::on_disk_cache::EncodedSourceFileId as core[1bfa7175043acf8b]::fmt::Debug>::fmt
  51:     0x7ff933880b7d - <rustc_query_impl[45d3f46ffcc7d851]::on_disk_cache::EncodedSourceFileId as core[1bfa7175043acf8b]::fmt::Debug>::fmt
  52:     0x7ff933744ce1 - <rustc_query_impl[45d3f46ffcc7d851]::Queries>::as_dyn
  53:     0x7ff93363a0ee - <rustc_mir_dataflow[7dd8cfc28066c66d]::framework::engine::RustcMirAttrs>::output_path
  54:     0x7ff9336f7522 - <rustc_mir_dataflow[7dd8cfc28066c66d]::framework::engine::RustcMirAttrs>::output_path
  55:     0x7ff9300e157e - <rustc_driver[95bf5c8e465c1fbc]::args::Error as core[1bfa7175043acf8b]::fmt::Debug>::fmt
  56:     0x7ff9300dba3f - <md5[f98078c158afda2e]::Md5 as std[9b5ceeebf257efe9]::io::Write>::flush
  57:     0x7ff9300e1ec5 - <rustc_driver[95bf5c8e465c1fbc]::args::Error as core[1bfa7175043acf8b]::fmt::Debug>::fmt
  58:     0x7ff9300da371 - <md5[f98078c158afda2e]::Md5 as std[9b5ceeebf257efe9]::io::Write>::flush
  59:     0x7ff9300c1b83 - <md5[f98078c158afda2e]::Md5 as std[9b5ceeebf257efe9]::io::Write>::flush
  60:     0x7ff9300bbce8 - <md5[f98078c158afda2e]::Md5 as std[9b5ceeebf257efe9]::io::Write>::flush
  61:     0x7ff943e1b06c - std::sys::windows::thread::Thread::new::h44896cc45d24b16e
  62:     0x7ff987097034 - BaseThreadInitThunk
  63:     0x7ff988982651 - RtlUserThreadStart

note: the compiler unexpectedly panicked. this is a bug.

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.60.0-nightly (71226d717 2022-02-04) running on x86_64-pc-windows-msvc

note: compiler flags: --crate-type lib -C embed-bitcode=no -C debuginfo=2 -C incremental

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

query stack during panic:
#0 [typeck] type-checking `tree::<impl at src\tree.rs:32:1: 41:2>::subtree`
#1 [typeck_item_bodies] type-checking all item bodies
#2 [analysis] running analysis passes on this crate
end of query stack
error: could not compile `allusion-proto`

The text was updated successfully, but these errors were encountered:

compiler-errors · 2022-03-09T01:59:08Z

This was fixed in #94596. Can you test this after running rustup update to update your compiler to the newest nightly?

hummingly · 2022-03-09T23:26:57Z

Everything fine on the latest nightly!

hummingly added C-bug Category: This is a bug. I-ICE Issue: The compiler panicked, giving an Internal Compilation Error (ICE) ❄️ T-compiler Relevant to the compiler team, which will review and decide on the PR/issue. labels Mar 8, 2022

hummingly closed this as completed Mar 9, 2022

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Compiler #94735

Compiler #94735

hummingly commented Mar 8, 2022 •

edited

Loading

compiler-errors commented Mar 9, 2022

hummingly commented Mar 9, 2022

Compiler #94735

Compiler #94735

Comments

hummingly commented Mar 8, 2022 • edited Loading

Code

Meta

Error output

compiler-errors commented Mar 9, 2022

hummingly commented Mar 9, 2022

hummingly commented Mar 8, 2022 •

edited

Loading