Closed
Description
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
}
}Meta
rustc --version --verbose:
rustc 1.60.0-nightly (71226d717 2022-02-04)
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`