1 //! For each definition, we track the following data. A definition 2 //! here is defined somewhat circularly as "something with a `DefId`", 3 //! but it generally corresponds to things like structs, enums, etc. 4 //! There are also some rather random cases (like const initializer 5 //! expressions) that are mostly just leftovers. 6 7 pub use crate::def_id::DefPathHash; 8 use crate::def_id::{CrateNum, DefIndex, LocalDefId, StableCrateId, CRATE_DEF_INDEX, LOCAL_CRATE}; 9 use crate::def_path_hash_map::DefPathHashMap; 10 use crate::hir; 11 12 use rustc_data_structures::fx::FxHashMap; 13 use rustc_data_structures::stable_hasher::StableHasher; 14 use rustc_index::vec::IndexVec; 15 use rustc_span::hygiene::ExpnId; 16 use rustc_span::symbol::{kw, sym, Symbol}; 17 use rustc_span::Span; 18 19 use std::fmt::{self, Write}; 20 use std::hash::Hash; 21 use tracing::debug; 22 23 /// The `DefPathTable` maps `DefIndex`es to `DefKey`s and vice versa. 24 /// Internally the `DefPathTable` holds a tree of `DefKey`s, where each `DefKey` 25 /// stores the `DefIndex` of its parent. 26 /// There is one `DefPathTable` for each crate. 27 #[derive(Clone, Default, Debug)] 28 pub struct DefPathTable { 29 index_to_key: IndexVec<DefIndex, DefKey>, 30 def_path_hashes: IndexVec<DefIndex, DefPathHash>, 31 def_path_hash_to_index: DefPathHashMap, 32 } 33 34 impl DefPathTable { allocate(&mut self, key: DefKey, def_path_hash: DefPathHash) -> DefIndex35 fn allocate(&mut self, key: DefKey, def_path_hash: DefPathHash) -> DefIndex { 36 let index = { 37 let index = DefIndex::from(self.index_to_key.len()); 38 debug!("DefPathTable::insert() - {:?} <-> {:?}", key, index); 39 self.index_to_key.push(key); 40 index 41 }; 42 self.def_path_hashes.push(def_path_hash); 43 debug_assert!(self.def_path_hashes.len() == self.index_to_key.len()); 44 45 // Check for hash collisions of DefPathHashes. These should be 46 // exceedingly rare. 47 if let Some(existing) = self.def_path_hash_to_index.insert(&def_path_hash, &index) { 48 let def_path1 = DefPath::make(LOCAL_CRATE, existing, |idx| self.def_key(idx)); 49 let def_path2 = DefPath::make(LOCAL_CRATE, index, |idx| self.def_key(idx)); 50 51 // Continuing with colliding DefPathHashes can lead to correctness 52 // issues. We must abort compilation. 53 // 54 // The likelyhood of such a collision is very small, so actually 55 // running into one could be indicative of a poor hash function 56 // being used. 57 // 58 // See the documentation for DefPathHash for more information. 59 panic!( 60 "found DefPathHash collsion between {:?} and {:?}. \ 61 Compilation cannot continue.", 62 def_path1, def_path2 63 ); 64 } 65 66 // Assert that all DefPathHashes correctly contain the local crate's 67 // StableCrateId 68 #[cfg(debug_assertions)] 69 if let Some(root) = self.def_path_hashes.get(CRATE_DEF_INDEX) { 70 assert!(def_path_hash.stable_crate_id() == root.stable_crate_id()); 71 } 72 73 index 74 } 75 76 #[inline(always)] def_key(&self, index: DefIndex) -> DefKey77 pub fn def_key(&self, index: DefIndex) -> DefKey { 78 self.index_to_key[index] 79 } 80 81 #[inline(always)] def_path_hash(&self, index: DefIndex) -> DefPathHash82 pub fn def_path_hash(&self, index: DefIndex) -> DefPathHash { 83 let hash = self.def_path_hashes[index]; 84 debug!("def_path_hash({:?}) = {:?}", index, hash); 85 hash 86 } 87 enumerated_keys_and_path_hashes( &self, ) -> impl Iterator<Item = (DefIndex, &DefKey, &DefPathHash)> + ExactSizeIterator + '_88 pub fn enumerated_keys_and_path_hashes( 89 &self, 90 ) -> impl Iterator<Item = (DefIndex, &DefKey, &DefPathHash)> + ExactSizeIterator + '_ { 91 self.index_to_key 92 .iter_enumerated() 93 .map(move |(index, key)| (index, key, &self.def_path_hashes[index])) 94 } 95 } 96 97 /// The definition table containing node definitions. 98 /// It holds the `DefPathTable` for `LocalDefId`s/`DefPath`s. 99 /// It also stores mappings to convert `LocalDefId`s to/from `HirId`s. 100 #[derive(Clone, Debug)] 101 pub struct Definitions { 102 table: DefPathTable, 103 104 // FIXME(eddyb) ideally all `LocalDefId`s would be HIR owners. 105 pub(super) def_id_to_hir_id: IndexVec<LocalDefId, Option<hir::HirId>>, 106 /// The reverse mapping of `def_id_to_hir_id`. 107 pub(super) hir_id_to_def_id: FxHashMap<hir::HirId, LocalDefId>, 108 109 /// Item with a given `LocalDefId` was defined during macro expansion with ID `ExpnId`. 110 expansions_that_defined: FxHashMap<LocalDefId, ExpnId>, 111 112 def_id_to_span: IndexVec<LocalDefId, Span>, 113 114 /// The [StableCrateId] of the local crate. 115 stable_crate_id: StableCrateId, 116 } 117 118 /// A unique identifier that we can use to lookup a definition 119 /// precisely. It combines the index of the definition's parent (if 120 /// any) with a `DisambiguatedDefPathData`. 121 #[derive(Copy, Clone, PartialEq, Debug, Encodable, Decodable)] 122 pub struct DefKey { 123 /// The parent path. 124 pub parent: Option<DefIndex>, 125 126 /// The identifier of this node. 127 pub disambiguated_data: DisambiguatedDefPathData, 128 } 129 130 impl DefKey { compute_stable_hash(&self, parent: DefPathHash) -> DefPathHash131 pub(crate) fn compute_stable_hash(&self, parent: DefPathHash) -> DefPathHash { 132 let mut hasher = StableHasher::new(); 133 134 parent.hash(&mut hasher); 135 136 let DisambiguatedDefPathData { ref data, disambiguator } = self.disambiguated_data; 137 138 std::mem::discriminant(data).hash(&mut hasher); 139 if let Some(name) = data.get_opt_name() { 140 // Get a stable hash by considering the symbol chars rather than 141 // the symbol index. 142 name.as_str().hash(&mut hasher); 143 } 144 145 disambiguator.hash(&mut hasher); 146 147 let local_hash: u64 = hasher.finish(); 148 149 // Construct the new DefPathHash, making sure that the `crate_id` 150 // portion of the hash is properly copied from the parent. This way the 151 // `crate_id` part will be recursively propagated from the root to all 152 // DefPathHashes in this DefPathTable. 153 DefPathHash::new(parent.stable_crate_id(), local_hash) 154 } 155 } 156 157 /// A pair of `DefPathData` and an integer disambiguator. The integer is 158 /// normally `0`, but in the event that there are multiple defs with the 159 /// same `parent` and `data`, we use this field to disambiguate 160 /// between them. This introduces some artificial ordering dependency 161 /// but means that if you have, e.g., two impls for the same type in 162 /// the same module, they do get distinct `DefId`s. 163 #[derive(Copy, Clone, PartialEq, Debug, Encodable, Decodable)] 164 pub struct DisambiguatedDefPathData { 165 pub data: DefPathData, 166 pub disambiguator: u32, 167 } 168 169 impl DisambiguatedDefPathData { fmt_maybe_verbose(&self, writer: &mut impl Write, verbose: bool) -> fmt::Result170 pub fn fmt_maybe_verbose(&self, writer: &mut impl Write, verbose: bool) -> fmt::Result { 171 match self.data.name() { 172 DefPathDataName::Named(name) => { 173 if verbose && self.disambiguator != 0 { 174 write!(writer, "{}#{}", name, self.disambiguator) 175 } else { 176 writer.write_str(&name.as_str()) 177 } 178 } 179 DefPathDataName::Anon { namespace } => { 180 write!(writer, "{{{}#{}}}", namespace, self.disambiguator) 181 } 182 } 183 } 184 } 185 186 impl fmt::Display for DisambiguatedDefPathData { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result187 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 188 self.fmt_maybe_verbose(f, true) 189 } 190 } 191 192 #[derive(Clone, Debug, Encodable, Decodable)] 193 pub struct DefPath { 194 /// The path leading from the crate root to the item. 195 pub data: Vec<DisambiguatedDefPathData>, 196 197 /// The crate root this path is relative to. 198 pub krate: CrateNum, 199 } 200 201 impl DefPath { make<FN>(krate: CrateNum, start_index: DefIndex, mut get_key: FN) -> DefPath where FN: FnMut(DefIndex) -> DefKey,202 pub fn make<FN>(krate: CrateNum, start_index: DefIndex, mut get_key: FN) -> DefPath 203 where 204 FN: FnMut(DefIndex) -> DefKey, 205 { 206 let mut data = vec![]; 207 let mut index = Some(start_index); 208 loop { 209 debug!("DefPath::make: krate={:?} index={:?}", krate, index); 210 let p = index.unwrap(); 211 let key = get_key(p); 212 debug!("DefPath::make: key={:?}", key); 213 match key.disambiguated_data.data { 214 DefPathData::CrateRoot => { 215 assert!(key.parent.is_none()); 216 break; 217 } 218 _ => { 219 data.push(key.disambiguated_data); 220 index = key.parent; 221 } 222 } 223 } 224 data.reverse(); 225 DefPath { data, krate } 226 } 227 228 /// Returns a string representation of the `DefPath` without 229 /// the crate-prefix. This method is useful if you don't have 230 /// a `TyCtxt` available. to_string_no_crate_verbose(&self) -> String231 pub fn to_string_no_crate_verbose(&self) -> String { 232 let mut s = String::with_capacity(self.data.len() * 16); 233 234 for component in &self.data { 235 write!(s, "::{}", component).unwrap(); 236 } 237 238 s 239 } 240 241 /// Returns a filename-friendly string of the `DefPath`, without 242 /// the crate-prefix. This method is useful if you don't have 243 /// a `TyCtxt` available. to_filename_friendly_no_crate(&self) -> String244 pub fn to_filename_friendly_no_crate(&self) -> String { 245 let mut s = String::with_capacity(self.data.len() * 16); 246 247 let mut opt_delimiter = None; 248 for component in &self.data { 249 s.extend(opt_delimiter); 250 opt_delimiter = Some('-'); 251 write!(s, "{}", component).unwrap(); 252 } 253 254 s 255 } 256 } 257 258 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, Encodable, Decodable)] 259 pub enum DefPathData { 260 // Root: these should only be used for the root nodes, because 261 // they are treated specially by the `def_path` function. 262 /// The crate root (marker). 263 CrateRoot, 264 // Catch-all for random `DefId` things like `DUMMY_NODE_ID`. 265 Misc, 266 267 // Different kinds of items and item-like things: 268 /// An impl. 269 Impl, 270 /// Something in the type namespace. 271 TypeNs(Symbol), 272 /// Something in the value namespace. 273 ValueNs(Symbol), 274 /// Something in the macro namespace. 275 MacroNs(Symbol), 276 /// Something in the lifetime namespace. 277 LifetimeNs(Symbol), 278 /// A closure expression. 279 ClosureExpr, 280 281 // Subportions of items: 282 /// Implicit constructor for a unit or tuple-like struct or enum variant. 283 Ctor, 284 /// A constant expression (see `{ast,hir}::AnonConst`). 285 AnonConst, 286 /// An `impl Trait` type node. 287 ImplTrait, 288 } 289 290 impl Definitions { def_path_table(&self) -> &DefPathTable291 pub fn def_path_table(&self) -> &DefPathTable { 292 &self.table 293 } 294 295 /// Gets the number of definitions. def_index_count(&self) -> usize296 pub fn def_index_count(&self) -> usize { 297 self.table.index_to_key.len() 298 } 299 300 #[inline] def_key(&self, id: LocalDefId) -> DefKey301 pub fn def_key(&self, id: LocalDefId) -> DefKey { 302 self.table.def_key(id.local_def_index) 303 } 304 305 #[inline(always)] def_path_hash(&self, id: LocalDefId) -> DefPathHash306 pub fn def_path_hash(&self, id: LocalDefId) -> DefPathHash { 307 self.table.def_path_hash(id.local_def_index) 308 } 309 310 /// Returns the path from the crate root to `index`. The root 311 /// nodes are not included in the path (i.e., this will be an 312 /// empty vector for the crate root). For an inlined item, this 313 /// will be the path of the item in the external crate (but the 314 /// path will begin with the path to the external crate). def_path(&self, id: LocalDefId) -> DefPath315 pub fn def_path(&self, id: LocalDefId) -> DefPath { 316 DefPath::make(LOCAL_CRATE, id.local_def_index, |index| { 317 self.def_key(LocalDefId { local_def_index: index }) 318 }) 319 } 320 321 #[inline] 322 #[track_caller] local_def_id_to_hir_id(&self, id: LocalDefId) -> hir::HirId323 pub fn local_def_id_to_hir_id(&self, id: LocalDefId) -> hir::HirId { 324 self.def_id_to_hir_id[id].unwrap() 325 } 326 327 #[inline] opt_hir_id_to_local_def_id(&self, hir_id: hir::HirId) -> Option<LocalDefId>328 pub fn opt_hir_id_to_local_def_id(&self, hir_id: hir::HirId) -> Option<LocalDefId> { 329 self.hir_id_to_def_id.get(&hir_id).copied() 330 } 331 332 /// Adds a root definition (no parent) and a few other reserved definitions. new(stable_crate_id: StableCrateId, crate_span: Span) -> Definitions333 pub fn new(stable_crate_id: StableCrateId, crate_span: Span) -> Definitions { 334 let key = DefKey { 335 parent: None, 336 disambiguated_data: DisambiguatedDefPathData { 337 data: DefPathData::CrateRoot, 338 disambiguator: 0, 339 }, 340 }; 341 342 let parent_hash = DefPathHash::new(stable_crate_id, 0); 343 let def_path_hash = key.compute_stable_hash(parent_hash); 344 345 // Create the root definition. 346 let mut table = DefPathTable::default(); 347 let root = LocalDefId { local_def_index: table.allocate(key, def_path_hash) }; 348 assert_eq!(root.local_def_index, CRATE_DEF_INDEX); 349 350 let mut def_id_to_span = IndexVec::new(); 351 // A relative span's parent must be an absolute span. 352 debug_assert_eq!(crate_span.data_untracked().parent, None); 353 let _root = def_id_to_span.push(crate_span); 354 debug_assert_eq!(_root, root); 355 356 Definitions { 357 table, 358 def_id_to_hir_id: Default::default(), 359 hir_id_to_def_id: Default::default(), 360 expansions_that_defined: Default::default(), 361 def_id_to_span, 362 stable_crate_id, 363 } 364 } 365 366 /// Retrieves the root definition. get_root_def(&self) -> LocalDefId367 pub fn get_root_def(&self) -> LocalDefId { 368 LocalDefId { local_def_index: CRATE_DEF_INDEX } 369 } 370 371 /// Adds a definition with a parent definition. create_def( &mut self, parent: LocalDefId, data: DefPathData, expn_id: ExpnId, mut next_disambiguator: impl FnMut(LocalDefId, DefPathData) -> u32, span: Span, ) -> LocalDefId372 pub fn create_def( 373 &mut self, 374 parent: LocalDefId, 375 data: DefPathData, 376 expn_id: ExpnId, 377 mut next_disambiguator: impl FnMut(LocalDefId, DefPathData) -> u32, 378 span: Span, 379 ) -> LocalDefId { 380 debug!("create_def(parent={:?}, data={:?}, expn_id={:?})", parent, data, expn_id); 381 382 // The root node must be created with `create_root_def()`. 383 assert!(data != DefPathData::CrateRoot); 384 385 let disambiguator = next_disambiguator(parent, data); 386 let key = DefKey { 387 parent: Some(parent.local_def_index), 388 disambiguated_data: DisambiguatedDefPathData { data, disambiguator }, 389 }; 390 391 let parent_hash = self.table.def_path_hash(parent.local_def_index); 392 let def_path_hash = key.compute_stable_hash(parent_hash); 393 394 debug!("create_def: after disambiguation, key = {:?}", key); 395 396 // Create the definition. 397 let def_id = LocalDefId { local_def_index: self.table.allocate(key, def_path_hash) }; 398 399 if expn_id != ExpnId::root() { 400 self.expansions_that_defined.insert(def_id, expn_id); 401 } 402 403 // A relative span's parent must be an absolute span. 404 debug_assert_eq!(span.data_untracked().parent, None); 405 let _id = self.def_id_to_span.push(span); 406 debug_assert_eq!(_id, def_id); 407 408 def_id 409 } 410 411 /// Initializes the `LocalDefId` to `HirId` mapping once it has been generated during 412 /// AST to HIR lowering. init_def_id_to_hir_id_mapping( &mut self, mapping: IndexVec<LocalDefId, Option<hir::HirId>>, )413 pub fn init_def_id_to_hir_id_mapping( 414 &mut self, 415 mapping: IndexVec<LocalDefId, Option<hir::HirId>>, 416 ) { 417 assert!( 418 self.def_id_to_hir_id.is_empty(), 419 "trying to initialize `LocalDefId` <-> `HirId` mappings twice" 420 ); 421 422 // Build the reverse mapping of `def_id_to_hir_id`. 423 self.hir_id_to_def_id = mapping 424 .iter_enumerated() 425 .filter_map(|(def_id, hir_id)| hir_id.map(|hir_id| (hir_id, def_id))) 426 .collect(); 427 428 self.def_id_to_hir_id = mapping; 429 } 430 expansion_that_defined(&self, id: LocalDefId) -> ExpnId431 pub fn expansion_that_defined(&self, id: LocalDefId) -> ExpnId { 432 self.expansions_that_defined.get(&id).copied().unwrap_or_else(ExpnId::root) 433 } 434 435 /// Retrieves the span of the given `DefId` if `DefId` is in the local crate. 436 #[inline] def_span(&self, def_id: LocalDefId) -> Span437 pub fn def_span(&self, def_id: LocalDefId) -> Span { 438 self.def_id_to_span[def_id] 439 } 440 iter_local_def_id(&self) -> impl Iterator<Item = LocalDefId> + '_441 pub fn iter_local_def_id(&self) -> impl Iterator<Item = LocalDefId> + '_ { 442 self.def_id_to_hir_id.iter_enumerated().map(|(k, _)| k) 443 } 444 445 #[inline(always)] local_def_path_hash_to_def_id(&self, hash: DefPathHash) -> LocalDefId446 pub fn local_def_path_hash_to_def_id(&self, hash: DefPathHash) -> LocalDefId { 447 debug_assert!(hash.stable_crate_id() == self.stable_crate_id); 448 self.table 449 .def_path_hash_to_index 450 .get(&hash) 451 .map(|local_def_index| LocalDefId { local_def_index }) 452 .unwrap() 453 } 454 def_path_hash_to_def_index_map(&self) -> &DefPathHashMap455 pub fn def_path_hash_to_def_index_map(&self) -> &DefPathHashMap { 456 &self.table.def_path_hash_to_index 457 } 458 } 459 460 #[derive(Copy, Clone, PartialEq, Debug)] 461 pub enum DefPathDataName { 462 Named(Symbol), 463 Anon { namespace: Symbol }, 464 } 465 466 impl DefPathData { get_opt_name(&self) -> Option<Symbol>467 pub fn get_opt_name(&self) -> Option<Symbol> { 468 use self::DefPathData::*; 469 match *self { 470 TypeNs(name) | ValueNs(name) | MacroNs(name) | LifetimeNs(name) => Some(name), 471 472 Impl | CrateRoot | Misc | ClosureExpr | Ctor | AnonConst | ImplTrait => None, 473 } 474 } 475 name(&self) -> DefPathDataName476 pub fn name(&self) -> DefPathDataName { 477 use self::DefPathData::*; 478 match *self { 479 TypeNs(name) | ValueNs(name) | MacroNs(name) | LifetimeNs(name) => { 480 DefPathDataName::Named(name) 481 } 482 // Note that this does not show up in user print-outs. 483 CrateRoot => DefPathDataName::Anon { namespace: kw::Crate }, 484 Impl => DefPathDataName::Anon { namespace: kw::Impl }, 485 Misc => DefPathDataName::Anon { namespace: sym::misc }, 486 ClosureExpr => DefPathDataName::Anon { namespace: sym::closure }, 487 Ctor => DefPathDataName::Anon { namespace: sym::constructor }, 488 AnonConst => DefPathDataName::Anon { namespace: sym::constant }, 489 ImplTrait => DefPathDataName::Anon { namespace: sym::opaque }, 490 } 491 } 492 } 493 494 impl fmt::Display for DefPathData { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result495 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 496 match self.name() { 497 DefPathDataName::Named(name) => f.write_str(&name.as_str()), 498 // FIXME(#70334): this will generate legacy {{closure}}, {{impl}}, etc 499 DefPathDataName::Anon { namespace } => write!(f, "{{{{{}}}}}", namespace), 500 } 501 } 502 } 503