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