compiler/rustc_hir/src/definitions.rs

   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
  11 use rustc_data_structures::fx::FxHashMap;
  12 use rustc_data_structures::stable_hasher::StableHasher;
  13 use rustc_index::vec::IndexVec;
  14 use rustc_span::symbol::{kw, sym, Symbol};
  15
  16 use std::fmt::{self, Write};
  17 use std::hash::Hash;
  18 use tracing::debug;
  19
  20 /// The `DefPathTable` maps `DefIndex`es to `DefKey`s and vice versa.
  21 /// Internally the `DefPathTable` holds a tree of `DefKey`s, where each `DefKey`
  22 /// stores the `DefIndex` of its parent.
  23 /// There is one `DefPathTable` for each crate.
  24 #[derive(Clone, Default, Debug)]
  25 pub struct DefPathTable {
  26     index_to_key: IndexVec<DefIndex, DefKey>,
  27     def_path_hashes: IndexVec<DefIndex, DefPathHash>,
  28     def_path_hash_to_index: DefPathHashMap,
  29 }
  30
  31 impl DefPathTable {
  32     fn allocate(&mut self, key: DefKey, def_path_hash: DefPathHash) -> DefIndex {
  33         let index = {
  34             let index = DefIndex::from(self.index_to_key.len());
  35             debug!("DefPathTable::insert() - {:?} <-> {:?}", key, index);
  36             self.index_to_key.push(key);
  37             index
  38         };
  39         self.def_path_hashes.push(def_path_hash);
  40         debug_assert!(self.def_path_hashes.len() == self.index_to_key.len());
  41
  42         // Check for hash collisions of DefPathHashes. These should be
  43         // exceedingly rare.
  44         if let Some(existing) = self.def_path_hash_to_index.insert(&def_path_hash, &index) {
  45             let def_path1 = DefPath::make(LOCAL_CRATE, existing, |idx| self.def_key(idx));
  46             let def_path2 = DefPath::make(LOCAL_CRATE, index, |idx| self.def_key(idx));
  47
  48             // Continuing with colliding DefPathHashes can lead to correctness
  49             // issues. We must abort compilation.
  50             //
  51             // The likelihood of such a collision is very small, so actually
  52             // running into one could be indicative of a poor hash function
  53             // being used.
  54             //
  55             // See the documentation for DefPathHash for more information.
  56             panic!(
  57                 "found DefPathHash collision between {:?} and {:?}. \
  58                     Compilation cannot continue.",
  59                 def_path1, def_path2
  60             );
  61         }
  62
  63         // Assert that all DefPathHashes correctly contain the local crate's
  64         // StableCrateId
  65         #[cfg(debug_assertions)]
  66         if let Some(root) = self.def_path_hashes.get(CRATE_DEF_INDEX) {
  67             assert!(def_path_hash.stable_crate_id() == root.stable_crate_id());
  68         }
  69
  70         index
  71     }
  72
  73     #[inline(always)]
  74     pub fn def_key(&self, index: DefIndex) -> DefKey {
  75         self.index_to_key[index]
  76     }
  77
  78     #[inline(always)]
  79     pub fn def_path_hash(&self, index: DefIndex) -> DefPathHash {
  80         let hash = self.def_path_hashes[index];
  81         debug!("def_path_hash({:?}) = {:?}", index, hash);
  82         hash
  83     }
  84
  85     pub fn enumerated_keys_and_path_hashes(
  86         &self,
  87     ) -> impl Iterator<Item = (DefIndex, &DefKey, &DefPathHash)> + ExactSizeIterator + '_ {
  88         self.index_to_key
  89             .iter_enumerated()
  90             .map(move |(index, key)| (index, key, &self.def_path_hashes[index]))
  91     }
  92 }
  93
  94 /// The definition table containing node definitions.
  95 /// It holds the `DefPathTable` for `LocalDefId`s/`DefPath`s.
  96 /// It also stores mappings to convert `LocalDefId`s to/from `HirId`s.
  97 #[derive(Clone, Debug)]
  98 pub struct Definitions {
  99     table: DefPathTable,
 100     next_disambiguator: FxHashMap<(LocalDefId, DefPathData), u32>,
 101
 102     /// The [StableCrateId] of the local crate.
 103     stable_crate_id: StableCrateId,
 104 }
 105
 106 /// A unique identifier that we can use to lookup a definition
 107 /// precisely. It combines the index of the definition's parent (if
 108 /// any) with a `DisambiguatedDefPathData`.
 109 #[derive(Copy, Clone, PartialEq, Debug, Encodable, Decodable)]
 110 pub struct DefKey {
 111     /// The parent path.
 112     pub parent: Option<DefIndex>,
 113
 114     /// The identifier of this node.
 115     pub disambiguated_data: DisambiguatedDefPathData,
 116 }
 117
 118 impl DefKey {
 119     pub(crate) fn compute_stable_hash(&self, parent: DefPathHash) -> DefPathHash {
 120         let mut hasher = StableHasher::new();
 121
 122         parent.hash(&mut hasher);
 123
 124         let DisambiguatedDefPathData { ref data, disambiguator } = self.disambiguated_data;
 125
 126         std::mem::discriminant(data).hash(&mut hasher);
 127         if let Some(name) = data.get_opt_name() {
 128             // Get a stable hash by considering the symbol chars rather than
 129             // the symbol index.
 130             name.as_str().hash(&mut hasher);
 131         }
 132
 133         disambiguator.hash(&mut hasher);
 134
 135         let local_hash: u64 = hasher.finish();
 136
 137         // Construct the new DefPathHash, making sure that the `crate_id`
 138         // portion of the hash is properly copied from the parent. This way the
 139         // `crate_id` part will be recursively propagated from the root to all
 140         // DefPathHashes in this DefPathTable.
 141         DefPathHash::new(parent.stable_crate_id(), local_hash)
 142     }
 143
 144     #[inline]
 145     pub fn get_opt_name(&self) -> Option<Symbol> {
 146         self.disambiguated_data.data.get_opt_name()
 147     }
 148 }
 149
 150 /// A pair of `DefPathData` and an integer disambiguator. The integer is
 151 /// normally `0`, but in the event that there are multiple defs with the
 152 /// same `parent` and `data`, we use this field to disambiguate
 153 /// between them. This introduces some artificial ordering dependency
 154 /// but means that if you have, e.g., two impls for the same type in
 155 /// the same module, they do get distinct `DefId`s.
 156 #[derive(Copy, Clone, PartialEq, Debug, Encodable, Decodable)]
 157 pub struct DisambiguatedDefPathData {
 158     pub data: DefPathData,
 159     pub disambiguator: u32,
 160 }
 161
 162 impl DisambiguatedDefPathData {
 163     pub fn fmt_maybe_verbose(&self, writer: &mut impl Write, verbose: bool) -> fmt::Result {
 164         match self.data.name() {
 165             DefPathDataName::Named(name) => {
 166                 if verbose && self.disambiguator != 0 {
 167                     write!(writer, "{}#{}", name, self.disambiguator)
 168                 } else {
 169                     writer.write_str(name.as_str())
 170                 }
 171             }
 172             DefPathDataName::Anon { namespace } => {
 173                 write!(writer, "{{{}#{}}}", namespace, self.disambiguator)
 174             }
 175         }
 176     }
 177 }
 178
 179 impl fmt::Display for DisambiguatedDefPathData {
 180     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 181         self.fmt_maybe_verbose(f, true)
 182     }
 183 }
 184
 185 #[derive(Clone, Debug, Encodable, Decodable)]
 186 pub struct DefPath {
 187     /// The path leading from the crate root to the item.
 188     pub data: Vec<DisambiguatedDefPathData>,
 189
 190     /// The crate root this path is relative to.
 191     pub krate: CrateNum,
 192 }
 193
 194 impl DefPath {
 195     pub fn make<FN>(krate: CrateNum, start_index: DefIndex, mut get_key: FN) -> DefPath
 196     where
 197         FN: FnMut(DefIndex) -> DefKey,
 198     {
 199         let mut data = vec![];
 200         let mut index = Some(start_index);
 201         loop {
 202             debug!("DefPath::make: krate={:?} index={:?}", krate, index);
 203             let p = index.unwrap();
 204             let key = get_key(p);
 205             debug!("DefPath::make: key={:?}", key);
 206             match key.disambiguated_data.data {
 207                 DefPathData::CrateRoot => {
 208                     assert!(key.parent.is_none());
 209                     break;
 210                 }
 211                 _ => {
 212                     data.push(key.disambiguated_data);
 213                     index = key.parent;
 214                 }
 215             }
 216         }
 217         data.reverse();
 218         DefPath { data, krate }
 219     }
 220
 221     /// Returns a string representation of the `DefPath` without
 222     /// the crate-prefix. This method is useful if you don't have
 223     /// a `TyCtxt` available.
 224     pub fn to_string_no_crate_verbose(&self) -> String {
 225         let mut s = String::with_capacity(self.data.len() * 16);
 226
 227         for component in &self.data {
 228             write!(s, "::{}", component).unwrap();
 229         }
 230
 231         s
 232     }
 233
 234     /// Returns a filename-friendly string of the `DefPath`, without
 235     /// the crate-prefix. This method is useful if you don't have
 236     /// a `TyCtxt` available.
 237     pub fn to_filename_friendly_no_crate(&self) -> String {
 238         let mut s = String::with_capacity(self.data.len() * 16);
 239
 240         let mut opt_delimiter = None;
 241         for component in &self.data {
 242             s.extend(opt_delimiter);
 243             opt_delimiter = Some('-');
 244             write!(s, "{}", component).unwrap();
 245         }
 246
 247         s
 248     }
 249 }
 250
 251 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, Encodable, Decodable)]
 252 pub enum DefPathData {
 253     // Root: these should only be used for the root nodes, because
 254     // they are treated specially by the `def_path` function.
 255     /// The crate root (marker).
 256     CrateRoot,
 257
 258     // Different kinds of items and item-like things:
 259     /// An impl.
 260     Impl,
 261     /// An `extern` block.
 262     ForeignMod,
 263     /// A `use` item.
 264     Use,
 265     /// A global asm item.
 266     GlobalAsm,
 267     /// Something in the type namespace.
 268     TypeNs(Symbol),
 269     /// Something in the value namespace.
 270     ValueNs(Symbol),
 271     /// Something in the macro namespace.
 272     MacroNs(Symbol),
 273     /// Something in the lifetime namespace.
 274     LifetimeNs(Symbol),
 275     /// A closure expression.
 276     ClosureExpr,
 277
 278     // Subportions of items:
 279     /// Implicit constructor for a unit or tuple-like struct or enum variant.
 280     Ctor,
 281     /// A constant expression (see `{ast,hir}::AnonConst`).
 282     AnonConst,
 283     /// An `impl Trait` type node.
 284     ImplTrait,
 285 }
 286
 287 impl Definitions {
 288     pub fn def_path_table(&self) -> &DefPathTable {
 289         &self.table
 290     }
 291
 292     /// Gets the number of definitions.
 293     pub fn def_index_count(&self) -> usize {
 294         self.table.index_to_key.len()
 295     }
 296
 297     #[inline]
 298     pub fn def_key(&self, id: LocalDefId) -> DefKey {
 299         self.table.def_key(id.local_def_index)
 300     }
 301
 302     #[inline(always)]
 303     pub fn def_path_hash(&self, id: LocalDefId) -> DefPathHash {
 304         self.table.def_path_hash(id.local_def_index)
 305     }
 306
 307     /// Returns the path from the crate root to `index`. The root
 308     /// nodes are not included in the path (i.e., this will be an
 309     /// empty vector for the crate root). For an inlined item, this
 310     /// will be the path of the item in the external crate (but the
 311     /// path will begin with the path to the external crate).
 312     pub fn def_path(&self, id: LocalDefId) -> DefPath {
 313         DefPath::make(LOCAL_CRATE, id.local_def_index, |index| {
 314             self.def_key(LocalDefId { local_def_index: index })
 315         })
 316     }
 317
 318     /// Adds a root definition (no parent) and a few other reserved definitions.
 319     pub fn new(stable_crate_id: StableCrateId) -> Definitions {
 320         let key = DefKey {
 321             parent: None,
 322             disambiguated_data: DisambiguatedDefPathData {
 323                 data: DefPathData::CrateRoot,
 324                 disambiguator: 0,
 325             },
 326         };
 327
 328         let parent_hash = DefPathHash::new(stable_crate_id, 0);
 329         let def_path_hash = key.compute_stable_hash(parent_hash);
 330
 331         // Create the root definition.
 332         let mut table = DefPathTable::default();
 333         let root = LocalDefId { local_def_index: table.allocate(key, def_path_hash) };
 334         assert_eq!(root.local_def_index, CRATE_DEF_INDEX);
 335
 336         Definitions { table, next_disambiguator: Default::default(), stable_crate_id }
 337     }
 338
 339     /// Adds a definition with a parent definition.
 340     pub fn create_def(&mut self, parent: LocalDefId, data: DefPathData) -> LocalDefId {
 341         debug!("create_def(parent={:?}, data={:?})", parent, data);
 342
 343         // The root node must be created with `create_root_def()`.
 344         assert!(data != DefPathData::CrateRoot);
 345
 346         // Find the next free disambiguator for this key.
 347         let disambiguator = {
 348             let next_disamb = self.next_disambiguator.entry((parent, data)).or_insert(0);
 349             let disambiguator = *next_disamb;
 350             *next_disamb = next_disamb.checked_add(1).expect("disambiguator overflow");
 351             disambiguator
 352         };
 353         let key = DefKey {
 354             parent: Some(parent.local_def_index),
 355             disambiguated_data: DisambiguatedDefPathData { data, disambiguator },
 356         };
 357
 358         let parent_hash = self.table.def_path_hash(parent.local_def_index);
 359         let def_path_hash = key.compute_stable_hash(parent_hash);
 360
 361         debug!("create_def: after disambiguation, key = {:?}", key);
 362
 363         // Create the definition.
 364         LocalDefId { local_def_index: self.table.allocate(key, def_path_hash) }
 365     }
 366
 367     pub fn iter_local_def_id(&self) -> impl Iterator<Item = LocalDefId> + '_ {
 368         self.table.def_path_hashes.indices().map(|local_def_index| LocalDefId { local_def_index })
 369     }
 370
 371     #[inline(always)]
 372     pub fn local_def_path_hash_to_def_id(
 373         &self,
 374         hash: DefPathHash,
 375         err: &mut dyn FnMut() -> !,
 376     ) -> LocalDefId {
 377         debug_assert!(hash.stable_crate_id() == self.stable_crate_id);
 378         self.table
 379             .def_path_hash_to_index
 380             .get(&hash)
 381             .map(|local_def_index| LocalDefId { local_def_index })
 382             .unwrap_or_else(|| err())
 383     }
 384
 385     pub fn def_path_hash_to_def_index_map(&self) -> &DefPathHashMap {
 386         &self.table.def_path_hash_to_index
 387     }
 388 }
 389
 390 #[derive(Copy, Clone, PartialEq, Debug)]
 391 pub enum DefPathDataName {
 392     Named(Symbol),
 393     Anon { namespace: Symbol },
 394 }
 395
 396 impl DefPathData {
 397     pub fn get_opt_name(&self) -> Option<Symbol> {
 398         use self::DefPathData::*;
 399         match *self {
 400             TypeNs(name) | ValueNs(name) | MacroNs(name) | LifetimeNs(name) => Some(name),
 401
 402             Impl | ForeignMod | CrateRoot | Use | GlobalAsm | ClosureExpr | Ctor | AnonConst
 403             | ImplTrait => None,
 404         }
 405     }
 406
 407     pub fn name(&self) -> DefPathDataName {
 408         use self::DefPathData::*;
 409         match *self {
 410             TypeNs(name) | ValueNs(name) | MacroNs(name) | LifetimeNs(name) => {
 411                 DefPathDataName::Named(name)
 412             }
 413             // Note that this does not show up in user print-outs.
 414             CrateRoot => DefPathDataName::Anon { namespace: kw::Crate },
 415             Impl => DefPathDataName::Anon { namespace: kw::Impl },
 416             ForeignMod => DefPathDataName::Anon { namespace: kw::Extern },
 417             Use => DefPathDataName::Anon { namespace: kw::Use },
 418             GlobalAsm => DefPathDataName::Anon { namespace: sym::global_asm },
 419             ClosureExpr => DefPathDataName::Anon { namespace: sym::closure },
 420             Ctor => DefPathDataName::Anon { namespace: sym::constructor },
 421             AnonConst => DefPathDataName::Anon { namespace: sym::constant },
 422             ImplTrait => DefPathDataName::Anon { namespace: sym::opaque },
 423         }
 424     }
 425 }
 426
 427 impl fmt::Display for DefPathData {
 428     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 429         match self.name() {
 430             DefPathDataName::Named(name) => f.write_str(name.as_str()),
 431             // FIXME(#70334): this will generate legacy {{closure}}, {{impl}}, etc
 432             DefPathDataName::Anon { namespace } => write!(f, "{{{{{}}}}}", namespace),
 433         }
 434     }
 435 }