1use std::fmt::{self, Write};
8use std::hash::Hash;
9
10use rustc_data_structures::stable_hasher::StableHasher;
11use rustc_data_structures::unord::UnordMap;
12use rustc_hashes::Hash64;
13use rustc_index::IndexVec;
14use rustc_macros::{Decodable, Encodable};
15use rustc_span::{Symbol, kw, sym};
16use tracing::{debug, instrument};
17
18pub use crate::def_id::DefPathHash;
19use crate::def_id::{CRATE_DEF_INDEX, CrateNum, DefIndex, LOCAL_CRATE, LocalDefId, StableCrateId};
20use crate::def_path_hash_map::DefPathHashMap;
21
22#[derive(Debug)]
27pub struct DefPathTable {
28 stable_crate_id: StableCrateId,
29 index_to_key: IndexVec<DefIndex, DefKey>,
30 def_path_hashes: IndexVec<DefIndex, Hash64>,
32 def_path_hash_to_index: DefPathHashMap,
33}
34
35impl DefPathTable {
36 fn new(stable_crate_id: StableCrateId) -> DefPathTable {
37 DefPathTable {
38 stable_crate_id,
39 index_to_key: Default::default(),
40 def_path_hashes: Default::default(),
41 def_path_hash_to_index: Default::default(),
42 }
43 }
44
45 fn allocate(&mut self, key: DefKey, def_path_hash: DefPathHash) -> DefIndex {
46 debug_assert_eq!(self.stable_crate_id, def_path_hash.stable_crate_id());
48 let local_hash = def_path_hash.local_hash();
49
50 let index = self.index_to_key.push(key);
51 debug!("DefPathTable::insert() - {key:?} <-> {index:?}");
52
53 self.def_path_hashes.push(local_hash);
54 debug_assert!(self.def_path_hashes.len() == self.index_to_key.len());
55
56 if let Some(existing) = self.def_path_hash_to_index.insert(&local_hash, &index) {
59 let def_path1 = DefPath::make(LOCAL_CRATE, existing, |idx| self.def_key(idx));
60 let def_path2 = DefPath::make(LOCAL_CRATE, index, |idx| self.def_key(idx));
61
62 panic!(
71 "found DefPathHash collision between {def_path1:#?} and {def_path2:#?}. \
72 Compilation cannot continue."
73 );
74 }
75
76 index
77 }
78
79 #[inline(always)]
80 pub fn def_key(&self, index: DefIndex) -> DefKey {
81 self.index_to_key[index]
82 }
83
84 #[instrument(level = "trace", skip(self), ret)]
85 #[inline(always)]
86 pub fn def_path_hash(&self, index: DefIndex) -> DefPathHash {
87 let hash = self.def_path_hashes[index];
88 DefPathHash::new(self.stable_crate_id, hash)
89 }
90
91 pub fn enumerated_keys_and_path_hashes(
92 &self,
93 ) -> impl Iterator<Item = (DefIndex, &DefKey, DefPathHash)> + ExactSizeIterator {
94 self.index_to_key
95 .iter_enumerated()
96 .map(move |(index, key)| (index, key, self.def_path_hash(index)))
97 }
98}
99
100#[derive(Debug)]
101pub struct DisambiguatorState {
102 next: UnordMap<(LocalDefId, DefPathData), u32>,
103}
104
105impl DisambiguatorState {
106 pub fn new() -> Self {
107 Self { next: Default::default() }
108 }
109
110 pub fn with(def_id: LocalDefId, data: DefPathData, index: u32) -> Self {
113 let mut this = Self::new();
114 this.next.insert((def_id, data), index);
115 this
116 }
117}
118
119#[derive(Debug)]
123pub struct Definitions {
124 table: DefPathTable,
125}
126
127#[derive(Copy, Clone, PartialEq, Debug, Encodable, Decodable)]
131pub struct DefKey {
132 pub parent: Option<DefIndex>,
134
135 pub disambiguated_data: DisambiguatedDefPathData,
137}
138
139impl DefKey {
140 pub(crate) fn compute_stable_hash(&self, parent: DefPathHash) -> DefPathHash {
141 let mut hasher = StableHasher::new();
142
143 parent.hash(&mut hasher);
144
145 let DisambiguatedDefPathData { ref data, disambiguator } = self.disambiguated_data;
146
147 std::mem::discriminant(data).hash(&mut hasher);
148 if let Some(name) = data.hashed_symbol() {
149 name.as_str().hash(&mut hasher);
152 }
153
154 disambiguator.hash(&mut hasher);
155
156 let local_hash = hasher.finish();
157
158 DefPathHash::new(parent.stable_crate_id(), local_hash)
163 }
164
165 #[inline]
166 pub fn get_opt_name(&self) -> Option<Symbol> {
167 self.disambiguated_data.data.get_opt_name()
168 }
169}
170
171#[derive(Copy, Clone, PartialEq, Debug, Encodable, Decodable)]
178pub struct DisambiguatedDefPathData {
179 pub data: DefPathData,
180 pub disambiguator: u32,
181}
182
183impl DisambiguatedDefPathData {
184 pub fn fmt_maybe_verbose(&self, writer: &mut impl Write, verbose: bool) -> fmt::Result {
185 match self.data.name() {
186 DefPathDataName::Named(name) => {
187 if verbose && self.disambiguator != 0 {
188 write!(writer, "{}#{}", name, self.disambiguator)
189 } else {
190 writer.write_str(name.as_str())
191 }
192 }
193 DefPathDataName::Anon { namespace } => {
194 if let DefPathData::AnonAssocTy(method) = self.data {
195 write!(writer, "{}::{{{}#{}}}", method, namespace, self.disambiguator)
196 } else {
197 write!(writer, "{{{}#{}}}", namespace, self.disambiguator)
198 }
199 }
200 }
201 }
202}
203
204impl fmt::Display for DisambiguatedDefPathData {
205 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
206 self.fmt_maybe_verbose(f, true)
207 }
208}
209
210#[derive(Clone, Debug, Encodable, Decodable)]
211pub struct DefPath {
212 pub data: Vec<DisambiguatedDefPathData>,
214
215 pub krate: CrateNum,
217}
218
219impl DefPath {
220 pub fn make<FN>(krate: CrateNum, start_index: DefIndex, mut get_key: FN) -> DefPath
221 where
222 FN: FnMut(DefIndex) -> DefKey,
223 {
224 let mut data = vec![];
225 let mut index = Some(start_index);
226 loop {
227 debug!("DefPath::make: krate={:?} index={:?}", krate, index);
228 let p = index.unwrap();
229 let key = get_key(p);
230 debug!("DefPath::make: key={:?}", key);
231 match key.disambiguated_data.data {
232 DefPathData::CrateRoot => {
233 assert!(key.parent.is_none());
234 break;
235 }
236 _ => {
237 data.push(key.disambiguated_data);
238 index = key.parent;
239 }
240 }
241 }
242 data.reverse();
243 DefPath { data, krate }
244 }
245
246 pub fn to_string_no_crate_verbose(&self) -> String {
250 let mut s = String::with_capacity(self.data.len() * 16);
251
252 for component in &self.data {
253 write!(s, "::{component}").unwrap();
254 }
255
256 s
257 }
258
259 pub fn to_filename_friendly_no_crate(&self) -> String {
263 let mut s = String::with_capacity(self.data.len() * 16);
264
265 let mut opt_delimiter = None;
266 for component in &self.data {
267 s.extend(opt_delimiter);
268 opt_delimiter = Some('-');
269 write!(s, "{component}").unwrap();
270 }
271
272 s
273 }
274}
275
276#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, Encodable, Decodable)]
278pub enum DefPathData {
279 CrateRoot,
283
284 Impl,
287 ForeignMod,
289 Use,
291 GlobalAsm,
293 TypeNs(Symbol),
295 ValueNs(Symbol),
297 MacroNs(Symbol),
299 LifetimeNs(Symbol),
301 Closure,
303
304 Ctor,
307 AnonConst,
309 OpaqueTy,
312 OpaqueLifetime(Symbol),
314 AnonAssocTy(Symbol),
317 SyntheticCoroutineBody,
319 NestedStatic,
321}
322
323impl Definitions {
324 pub fn def_path_table(&self) -> &DefPathTable {
325 &self.table
326 }
327
328 pub fn def_index_count(&self) -> usize {
330 self.table.index_to_key.len()
331 }
332
333 #[inline]
334 pub fn def_key(&self, id: LocalDefId) -> DefKey {
335 self.table.def_key(id.local_def_index)
336 }
337
338 #[inline(always)]
339 pub fn def_path_hash(&self, id: LocalDefId) -> DefPathHash {
340 self.table.def_path_hash(id.local_def_index)
341 }
342
343 pub fn def_path(&self, id: LocalDefId) -> DefPath {
349 DefPath::make(LOCAL_CRATE, id.local_def_index, |index| {
350 self.def_key(LocalDefId { local_def_index: index })
351 })
352 }
353
354 pub fn new(stable_crate_id: StableCrateId) -> Definitions {
356 let key = DefKey {
357 parent: None,
358 disambiguated_data: DisambiguatedDefPathData {
359 data: DefPathData::CrateRoot,
360 disambiguator: 0,
361 },
362 };
363
364 let parent_hash = DefPathHash::new(stable_crate_id, Hash64::ZERO);
365 let def_path_hash = key.compute_stable_hash(parent_hash);
366
367 let mut table = DefPathTable::new(stable_crate_id);
369 let root = LocalDefId { local_def_index: table.allocate(key, def_path_hash) };
370 assert_eq!(root.local_def_index, CRATE_DEF_INDEX);
371
372 Definitions { table }
373 }
374
375 pub fn create_def(
381 &mut self,
382 parent: LocalDefId,
383 data: DefPathData,
384 disambiguator: &mut DisambiguatorState,
385 ) -> LocalDefId {
386 debug!(
389 "create_def(parent={}, data={data:?})",
390 self.def_path(parent).to_string_no_crate_verbose(),
391 );
392
393 assert!(data != DefPathData::CrateRoot);
395
396 let disambiguator = {
398 let next_disamb = disambiguator.next.entry((parent, data)).or_insert(0);
399 let disambiguator = *next_disamb;
400 *next_disamb = next_disamb.checked_add(1).expect("disambiguator overflow");
401 disambiguator
402 };
403 let key = DefKey {
404 parent: Some(parent.local_def_index),
405 disambiguated_data: DisambiguatedDefPathData { data, disambiguator },
406 };
407
408 let parent_hash = self.table.def_path_hash(parent.local_def_index);
409 let def_path_hash = key.compute_stable_hash(parent_hash);
410
411 debug!("create_def: after disambiguation, key = {:?}", key);
412
413 LocalDefId { local_def_index: self.table.allocate(key, def_path_hash) }
415 }
416
417 #[inline(always)]
418 pub fn local_def_path_hash_to_def_id(&self, hash: DefPathHash) -> Option<LocalDefId> {
424 debug_assert!(hash.stable_crate_id() == self.table.stable_crate_id);
425 self.table
426 .def_path_hash_to_index
427 .get(&hash.local_hash())
428 .map(|local_def_index| LocalDefId { local_def_index })
429 }
430
431 pub fn def_path_hash_to_def_index_map(&self) -> &DefPathHashMap {
432 &self.table.def_path_hash_to_index
433 }
434
435 pub fn num_definitions(&self) -> usize {
436 self.table.def_path_hashes.len()
437 }
438}
439
440#[derive(Copy, Clone, PartialEq, Debug)]
441pub enum DefPathDataName {
442 Named(Symbol),
443 Anon { namespace: Symbol },
444}
445
446impl DefPathData {
447 pub fn get_opt_name(&self) -> Option<Symbol> {
448 use self::DefPathData::*;
449 match *self {
450 TypeNs(name) | ValueNs(name) | MacroNs(name) | LifetimeNs(name)
451 | OpaqueLifetime(name) => Some(name),
452
453 Impl
454 | ForeignMod
455 | CrateRoot
456 | Use
457 | GlobalAsm
458 | Closure
459 | Ctor
460 | AnonConst
461 | OpaqueTy
462 | AnonAssocTy(..)
463 | SyntheticCoroutineBody
464 | NestedStatic => None,
465 }
466 }
467
468 fn hashed_symbol(&self) -> Option<Symbol> {
469 use self::DefPathData::*;
470 match *self {
471 TypeNs(name) | ValueNs(name) | MacroNs(name) | LifetimeNs(name) | AnonAssocTy(name)
472 | OpaqueLifetime(name) => Some(name),
473
474 Impl
475 | ForeignMod
476 | CrateRoot
477 | Use
478 | GlobalAsm
479 | Closure
480 | Ctor
481 | AnonConst
482 | OpaqueTy
483 | SyntheticCoroutineBody
484 | NestedStatic => None,
485 }
486 }
487
488 pub fn name(&self) -> DefPathDataName {
489 use self::DefPathData::*;
490 match *self {
491 TypeNs(name) | ValueNs(name) | MacroNs(name) | LifetimeNs(name)
492 | OpaqueLifetime(name) => DefPathDataName::Named(name),
493 CrateRoot => DefPathDataName::Anon { namespace: kw::Crate },
495 Impl => DefPathDataName::Anon { namespace: kw::Impl },
496 ForeignMod => DefPathDataName::Anon { namespace: kw::Extern },
497 Use => DefPathDataName::Anon { namespace: kw::Use },
498 GlobalAsm => DefPathDataName::Anon { namespace: sym::global_asm },
499 Closure => DefPathDataName::Anon { namespace: sym::closure },
500 Ctor => DefPathDataName::Anon { namespace: sym::constructor },
501 AnonConst => DefPathDataName::Anon { namespace: sym::constant },
502 OpaqueTy => DefPathDataName::Anon { namespace: sym::opaque },
503 AnonAssocTy(..) => DefPathDataName::Anon { namespace: sym::anon_assoc },
504 SyntheticCoroutineBody => DefPathDataName::Anon { namespace: sym::synthetic },
505 NestedStatic => DefPathDataName::Anon { namespace: sym::nested },
506 }
507 }
508}
509
510impl fmt::Display for DefPathData {
511 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
512 match self.name() {
513 DefPathDataName::Named(name) => f.write_str(name.as_str()),
514 DefPathDataName::Anon { namespace } => write!(f, "{{{{{namespace}}}}}"),
516 }
517 }
518}