use std::fmt::{self, Write};
use std::hash::Hash;
use rustc_data_structures::stable_hasher::{Hash64, StableHasher};
use rustc_data_structures::unord::UnordMap;
use rustc_index::IndexVec;
use rustc_macros::{Decodable, Encodable};
use rustc_span::symbol::{Symbol, kw, sym};
use tracing::{debug, instrument};
pub use crate::def_id::DefPathHash;
use crate::def_id::{CRATE_DEF_INDEX, CrateNum, DefIndex, LOCAL_CRATE, LocalDefId, StableCrateId};
use crate::def_path_hash_map::DefPathHashMap;
#[derive(Debug)]
pub struct DefPathTable {
stable_crate_id: StableCrateId,
index_to_key: IndexVec<DefIndex, DefKey>,
def_path_hashes: IndexVec<DefIndex, Hash64>,
def_path_hash_to_index: DefPathHashMap,
}
impl DefPathTable {
fn new(stable_crate_id: StableCrateId) -> DefPathTable {
DefPathTable {
stable_crate_id,
index_to_key: Default::default(),
def_path_hashes: Default::default(),
def_path_hash_to_index: Default::default(),
}
}
fn allocate(&mut self, key: DefKey, def_path_hash: DefPathHash) -> DefIndex {
debug_assert_eq!(self.stable_crate_id, def_path_hash.stable_crate_id());
let local_hash = def_path_hash.local_hash();
let index = {
let index = DefIndex::from(self.index_to_key.len());
debug!("DefPathTable::insert() - {:?} <-> {:?}", key, index);
self.index_to_key.push(key);
index
};
self.def_path_hashes.push(local_hash);
debug_assert!(self.def_path_hashes.len() == self.index_to_key.len());
if let Some(existing) = self.def_path_hash_to_index.insert(&local_hash, &index) {
let def_path1 = DefPath::make(LOCAL_CRATE, existing, |idx| self.def_key(idx));
let def_path2 = DefPath::make(LOCAL_CRATE, index, |idx| self.def_key(idx));
panic!(
"found DefPathHash collision between {def_path1:?} and {def_path2:?}. \
Compilation cannot continue."
);
}
index
}
#[inline(always)]
pub fn def_key(&self, index: DefIndex) -> DefKey {
self.index_to_key[index]
}
#[instrument(level = "trace", skip(self), ret)]
#[inline(always)]
pub fn def_path_hash(&self, index: DefIndex) -> DefPathHash {
let hash = self.def_path_hashes[index];
DefPathHash::new(self.stable_crate_id, hash)
}
pub fn enumerated_keys_and_path_hashes(
&self,
) -> impl Iterator<Item = (DefIndex, &DefKey, DefPathHash)> + ExactSizeIterator + '_ {
self.index_to_key
.iter_enumerated()
.map(move |(index, key)| (index, key, self.def_path_hash(index)))
}
}
#[derive(Debug)]
pub struct Definitions {
table: DefPathTable,
next_disambiguator: UnordMap<(LocalDefId, DefPathData), u32>,
}
#[derive(Copy, Clone, PartialEq, Debug, Encodable, Decodable)]
pub struct DefKey {
pub parent: Option<DefIndex>,
pub disambiguated_data: DisambiguatedDefPathData,
}
impl DefKey {
pub(crate) fn compute_stable_hash(&self, parent: DefPathHash) -> DefPathHash {
let mut hasher = StableHasher::new();
parent.hash(&mut hasher);
let DisambiguatedDefPathData { ref data, disambiguator } = self.disambiguated_data;
std::mem::discriminant(data).hash(&mut hasher);
if let Some(name) = data.get_opt_name() {
name.as_str().hash(&mut hasher);
}
disambiguator.hash(&mut hasher);
let local_hash = hasher.finish();
DefPathHash::new(parent.stable_crate_id(), local_hash)
}
#[inline]
pub fn get_opt_name(&self) -> Option<Symbol> {
self.disambiguated_data.data.get_opt_name()
}
}
#[derive(Copy, Clone, PartialEq, Debug, Encodable, Decodable)]
pub struct DisambiguatedDefPathData {
pub data: DefPathData,
pub disambiguator: u32,
}
impl DisambiguatedDefPathData {
pub fn fmt_maybe_verbose(&self, writer: &mut impl Write, verbose: bool) -> fmt::Result {
match self.data.name() {
DefPathDataName::Named(name) => {
if verbose && self.disambiguator != 0 {
write!(writer, "{}#{}", name, self.disambiguator)
} else {
writer.write_str(name.as_str())
}
}
DefPathDataName::Anon { namespace } => {
write!(writer, "{{{}#{}}}", namespace, self.disambiguator)
}
}
}
}
impl fmt::Display for DisambiguatedDefPathData {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
self.fmt_maybe_verbose(f, true)
}
}
#[derive(Clone, Debug, Encodable, Decodable)]
pub struct DefPath {
pub data: Vec<DisambiguatedDefPathData>,
pub krate: CrateNum,
}
impl DefPath {
pub fn make<FN>(krate: CrateNum, start_index: DefIndex, mut get_key: FN) -> DefPath
where
FN: FnMut(DefIndex) -> DefKey,
{
let mut data = vec![];
let mut index = Some(start_index);
loop {
debug!("DefPath::make: krate={:?} index={:?}", krate, index);
let p = index.unwrap();
let key = get_key(p);
debug!("DefPath::make: key={:?}", key);
match key.disambiguated_data.data {
DefPathData::CrateRoot => {
assert!(key.parent.is_none());
break;
}
_ => {
data.push(key.disambiguated_data);
index = key.parent;
}
}
}
data.reverse();
DefPath { data, krate }
}
pub fn to_string_no_crate_verbose(&self) -> String {
let mut s = String::with_capacity(self.data.len() * 16);
for component in &self.data {
write!(s, "::{component}").unwrap();
}
s
}
pub fn to_filename_friendly_no_crate(&self) -> String {
let mut s = String::with_capacity(self.data.len() * 16);
let mut opt_delimiter = None;
for component in &self.data {
s.extend(opt_delimiter);
opt_delimiter = Some('-');
write!(s, "{component}").unwrap();
}
s
}
}
#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, Encodable, Decodable)]
pub enum DefPathData {
CrateRoot,
Impl,
ForeignMod,
Use,
GlobalAsm,
TypeNs(Symbol),
ValueNs(Symbol),
MacroNs(Symbol),
LifetimeNs(Symbol),
Closure,
Ctor,
AnonConst,
OpaqueTy,
AnonAdt,
}
impl Definitions {
pub fn def_path_table(&self) -> &DefPathTable {
&self.table
}
pub fn def_index_count(&self) -> usize {
self.table.index_to_key.len()
}
#[inline]
pub fn def_key(&self, id: LocalDefId) -> DefKey {
self.table.def_key(id.local_def_index)
}
#[inline(always)]
pub fn def_path_hash(&self, id: LocalDefId) -> DefPathHash {
self.table.def_path_hash(id.local_def_index)
}
pub fn def_path(&self, id: LocalDefId) -> DefPath {
DefPath::make(LOCAL_CRATE, id.local_def_index, |index| {
self.def_key(LocalDefId { local_def_index: index })
})
}
pub fn new(stable_crate_id: StableCrateId) -> Definitions {
let key = DefKey {
parent: None,
disambiguated_data: DisambiguatedDefPathData {
data: DefPathData::CrateRoot,
disambiguator: 0,
},
};
let parent_hash = DefPathHash::new(stable_crate_id, Hash64::ZERO);
let def_path_hash = key.compute_stable_hash(parent_hash);
let mut table = DefPathTable::new(stable_crate_id);
let root = LocalDefId { local_def_index: table.allocate(key, def_path_hash) };
assert_eq!(root.local_def_index, CRATE_DEF_INDEX);
Definitions { table, next_disambiguator: Default::default() }
}
pub fn create_def(&mut self, parent: LocalDefId, data: DefPathData) -> LocalDefId {
debug!(
"create_def(parent={}, data={data:?})",
self.def_path(parent).to_string_no_crate_verbose(),
);
assert!(data != DefPathData::CrateRoot);
let disambiguator = {
let next_disamb = self.next_disambiguator.entry((parent, data)).or_insert(0);
let disambiguator = *next_disamb;
*next_disamb = next_disamb.checked_add(1).expect("disambiguator overflow");
disambiguator
};
let key = DefKey {
parent: Some(parent.local_def_index),
disambiguated_data: DisambiguatedDefPathData { data, disambiguator },
};
let parent_hash = self.table.def_path_hash(parent.local_def_index);
let def_path_hash = key.compute_stable_hash(parent_hash);
debug!("create_def: after disambiguation, key = {:?}", key);
LocalDefId { local_def_index: self.table.allocate(key, def_path_hash) }
}
#[inline(always)]
pub fn local_def_path_hash_to_def_id(&self, hash: DefPathHash) -> Option<LocalDefId> {
debug_assert!(hash.stable_crate_id() == self.table.stable_crate_id);
self.table
.def_path_hash_to_index
.get(&hash.local_hash())
.map(|local_def_index| LocalDefId { local_def_index })
}
pub fn def_path_hash_to_def_index_map(&self) -> &DefPathHashMap {
&self.table.def_path_hash_to_index
}
pub fn num_definitions(&self) -> usize {
self.table.def_path_hashes.len()
}
}
#[derive(Copy, Clone, PartialEq, Debug)]
pub enum DefPathDataName {
Named(Symbol),
Anon { namespace: Symbol },
}
impl DefPathData {
pub fn get_opt_name(&self) -> Option<Symbol> {
use self::DefPathData::*;
match *self {
TypeNs(name) if name == kw::Empty => None,
TypeNs(name) | ValueNs(name) | MacroNs(name) | LifetimeNs(name) => Some(name),
Impl | ForeignMod | CrateRoot | Use | GlobalAsm | Closure | Ctor | AnonConst
| OpaqueTy | AnonAdt => None,
}
}
pub fn name(&self) -> DefPathDataName {
use self::DefPathData::*;
match *self {
TypeNs(name) if name == kw::Empty => {
DefPathDataName::Anon { namespace: sym::synthetic }
}
TypeNs(name) | ValueNs(name) | MacroNs(name) | LifetimeNs(name) => {
DefPathDataName::Named(name)
}
CrateRoot => DefPathDataName::Anon { namespace: kw::Crate },
Impl => DefPathDataName::Anon { namespace: kw::Impl },
ForeignMod => DefPathDataName::Anon { namespace: kw::Extern },
Use => DefPathDataName::Anon { namespace: kw::Use },
GlobalAsm => DefPathDataName::Anon { namespace: sym::global_asm },
Closure => DefPathDataName::Anon { namespace: sym::closure },
Ctor => DefPathDataName::Anon { namespace: sym::constructor },
AnonConst => DefPathDataName::Anon { namespace: sym::constant },
OpaqueTy => DefPathDataName::Anon { namespace: sym::opaque },
AnonAdt => DefPathDataName::Anon { namespace: sym::anon_adt },
}
}
}
impl fmt::Display for DefPathData {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self.name() {
DefPathDataName::Named(name) => f.write_str(name.as_str()),
DefPathDataName::Anon { namespace } => write!(f, "{{{{{namespace}}}}}"),
}
}
}