1 use crate::crate_disambiguator::CrateDisambiguator;
2 use crate::HashStableContext;
3 use rustc_data_structures::fingerprint::Fingerprint;
4 use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
5 use rustc_data_structures::AtomicRef;
6 use rustc_index::vec::Idx;
7 use rustc_macros::HashStable_Generic;
8 use rustc_serialize::{Decodable, Decoder, Encodable, Encoder};
9 use std::borrow::Borrow;
12 rustc_index::newtype_index! {
18 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
20 /// A special `CrateNum` that we use for the `tcx.rcache` when decoding from
21 /// the incr. comp. cache.
22 ReservedForIncrCompCache,
26 /// Item definitions in the currently-compiled crate would have the `CrateNum`
27 /// `LOCAL_CRATE` in their `DefId`.
28 pub const LOCAL_CRATE: CrateNum = CrateNum::Index(CrateId::from_u32(0));
30 impl Idx for CrateNum {
32 fn new(value: usize) -> Self {
33 CrateNum::Index(Idx::new(value))
37 fn index(self) -> usize {
39 CrateNum::Index(idx) => Idx::index(idx),
40 _ => panic!("Tried to get crate index of {:?}", self),
46 pub fn new(x: usize) -> CrateNum {
47 CrateNum::from_usize(x)
50 pub fn from_usize(x: usize) -> CrateNum {
51 CrateNum::Index(CrateId::from_usize(x))
54 pub fn from_u32(x: u32) -> CrateNum {
55 CrateNum::Index(CrateId::from_u32(x))
58 pub fn as_usize(self) -> usize {
60 CrateNum::Index(id) => id.as_usize(),
61 _ => panic!("tried to get index of non-standard crate {:?}", self),
65 pub fn as_u32(self) -> u32 {
67 CrateNum::Index(id) => id.as_u32(),
68 _ => panic!("tried to get index of non-standard crate {:?}", self),
72 pub fn as_def_id(&self) -> DefId {
73 DefId { krate: *self, index: CRATE_DEF_INDEX }
77 impl fmt::Display for CrateNum {
78 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
80 CrateNum::Index(id) => fmt::Display::fmt(&id.private, f),
81 CrateNum::ReservedForIncrCompCache => write!(f, "crate for decoding incr comp cache"),
86 /// As a local identifier, a `CrateNum` is only meaningful within its context, e.g. within a tcx.
87 /// Therefore, make sure to include the context when encode a `CrateNum`.
88 impl<E: Encoder> Encodable<E> for CrateNum {
89 default fn encode(&self, s: &mut E) -> Result<(), E::Error> {
90 s.emit_u32(self.as_u32())
94 impl<D: Decoder> Decodable<D> for CrateNum {
95 default fn decode(d: &mut D) -> Result<CrateNum, D::Error> {
96 Ok(CrateNum::from_u32(d.read_u32()?))
100 impl ::std::fmt::Debug for CrateNum {
101 fn fmt(&self, fmt: &mut ::std::fmt::Formatter<'_>) -> ::std::fmt::Result {
103 CrateNum::Index(id) => write!(fmt, "crate{}", id.private),
104 CrateNum::ReservedForIncrCompCache => write!(fmt, "crate for decoding incr comp cache"),
109 /// A `DefPathHash` is a fixed-size representation of a `DefPath` that is
110 /// stable across crate and compilation session boundaries. It consists of two
111 /// separate 64-bit hashes. The first uniquely identifies the crate this
112 /// `DefPathHash` originates from (see [StableCrateId]), and the second
113 /// uniquely identifies the corresponding `DefPath` within that crate. Together
114 /// they form a unique identifier within an entire crate graph.
116 /// There is a very small chance of hash collisions, which would mean that two
117 /// different `DefPath`s map to the same `DefPathHash`. Proceeding compilation
118 /// with such a hash collision would very probably lead to an ICE, and in the
119 /// worst case lead to a silent mis-compilation. The compiler therefore actively
120 /// and exhaustively checks for such hash collisions and aborts compilation if
123 /// `DefPathHash` uses 64-bit hashes for both the crate-id part and the
124 /// crate-internal part, even though it is likely that there are many more
125 /// `LocalDefId`s in a single crate than there are individual crates in a crate
126 /// graph. Since we use the same number of bits in both cases, the collision
127 /// probability for the crate-local part will be quite a bit higher (though
128 /// still very small).
130 /// This imbalance is not by accident: A hash collision in the
131 /// crate-local part of a `DefPathHash` will be detected and reported while
132 /// compiling the crate in question. Such a collision does not depend on
133 /// outside factors and can be easily fixed by the crate maintainer (e.g. by
134 /// renaming the item in question or by bumping the crate version in a harmless
137 /// A collision between crate-id hashes on the other hand is harder to fix
138 /// because it depends on the set of crates in the entire crate graph of a
139 /// compilation session. Again, using the same crate with a different version
140 /// number would fix the issue with a high probability -- but that might be
141 /// easier said then done if the crates in questions are dependencies of
142 /// third-party crates.
144 /// That being said, given a high quality hash function, the collision
145 /// probabilities in question are very small. For example, for a big crate like
146 /// `rustc_middle` (with ~50000 `LocalDefId`s as of the time of writing) there
147 /// is a probability of roughly 1 in 14,750,000,000 of a crate-internal
148 /// collision occurring. For a big crate graph with 1000 crates in it, there is
149 /// a probability of 1 in 36,890,000,000,000 of a `StableCrateId` collision.
150 #[derive(Copy, Clone, Hash, PartialEq, Eq, PartialOrd, Ord, Debug)]
151 #[derive(HashStable_Generic, Encodable, Decodable)]
152 pub struct DefPathHash(pub Fingerprint);
155 /// Returns the [StableCrateId] identifying the crate this [DefPathHash]
158 pub fn stable_crate_id(&self) -> StableCrateId {
159 StableCrateId(self.0.as_value().0)
162 /// Builds a new [DefPathHash] with the given [StableCrateId] and
163 /// `local_hash`, where `local_hash` must be unique within its crate.
164 pub fn new(stable_crate_id: StableCrateId, local_hash: u64) -> DefPathHash {
165 DefPathHash(Fingerprint::new(stable_crate_id.0, local_hash))
169 impl Borrow<Fingerprint> for DefPathHash {
171 fn borrow(&self) -> &Fingerprint {
176 /// A [StableCrateId] is a 64 bit hash of `(crate-name, crate-disambiguator)`. It
177 /// is to [CrateNum] what [DefPathHash] is to [DefId]. It is stable across
178 /// compilation sessions.
180 /// Since the ID is a hash value there is a (very small) chance that two crates
181 /// end up with the same [StableCrateId]. The compiler will check for such
182 /// collisions when loading crates and abort compilation in order to avoid
184 #[derive(Copy, Clone, Hash, PartialEq, Eq, PartialOrd, Ord, Debug, Encodable, Decodable)]
185 pub struct StableCrateId(u64);
188 /// Computes the stable ID for a crate with the given name and
190 pub fn new(crate_name: &str, crate_disambiguator: CrateDisambiguator) -> StableCrateId {
193 let mut hasher = StableHasher::new();
194 crate_name.hash(&mut hasher);
195 crate_disambiguator.hash(&mut hasher);
196 StableCrateId(hasher.finish())
200 rustc_index::newtype_index! {
201 /// A DefIndex is an index into the hir-map for a crate, identifying a
202 /// particular definition. It should really be considered an interned
203 /// shorthand for a particular DefPath.
204 pub struct DefIndex {
205 ENCODABLE = custom // (only encodable in metadata)
207 DEBUG_FORMAT = "DefIndex({})",
208 /// The crate root is always assigned index 0 by the AST Map code,
209 /// thanks to `NodeCollector::new`.
210 const CRATE_DEF_INDEX = 0,
214 impl<E: Encoder> Encodable<E> for DefIndex {
215 default fn encode(&self, _: &mut E) -> Result<(), E::Error> {
216 panic!("cannot encode `DefIndex` with `{}`", std::any::type_name::<E>());
220 impl<D: Decoder> Decodable<D> for DefIndex {
221 default fn decode(_: &mut D) -> Result<DefIndex, D::Error> {
222 panic!("cannot decode `DefIndex` with `{}`", std::any::type_name::<D>());
226 /// A `DefId` identifies a particular *definition*, by combining a crate
227 /// index and a def index.
229 /// You can create a `DefId` from a `LocalDefId` using `local_def_id.to_def_id()`.
230 #[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Copy)]
237 /// Makes a local `DefId` from the given `DefIndex`.
239 pub fn local(index: DefIndex) -> DefId {
240 DefId { krate: LOCAL_CRATE, index }
243 /// Returns whether the item is defined in the crate currently being compiled.
245 pub fn is_local(self) -> bool {
246 self.krate == LOCAL_CRATE
250 pub fn as_local(self) -> Option<LocalDefId> {
251 if self.is_local() { Some(LocalDefId { local_def_index: self.index }) } else { None }
255 pub fn expect_local(self) -> LocalDefId {
256 self.as_local().unwrap_or_else(|| panic!("DefId::expect_local: `{:?}` isn't local", self))
259 pub fn is_top_level_module(self) -> bool {
260 self.is_local() && self.index == CRATE_DEF_INDEX
264 impl<E: Encoder> Encodable<E> for DefId {
265 default fn encode(&self, s: &mut E) -> Result<(), E::Error> {
266 s.emit_struct("DefId", 2, |s| {
267 s.emit_struct_field("krate", 0, |s| self.krate.encode(s))?;
269 s.emit_struct_field("index", 1, |s| self.index.encode(s))
274 impl<D: Decoder> Decodable<D> for DefId {
275 default fn decode(d: &mut D) -> Result<DefId, D::Error> {
276 d.read_struct("DefId", 2, |d| {
278 krate: d.read_struct_field("krate", 0, Decodable::decode)?,
279 index: d.read_struct_field("index", 1, Decodable::decode)?,
285 pub fn default_def_id_debug(def_id: DefId, f: &mut fmt::Formatter<'_>) -> fmt::Result {
286 f.debug_struct("DefId").field("krate", &def_id.krate).field("index", &def_id.index).finish()
289 pub static DEF_ID_DEBUG: AtomicRef<fn(DefId, &mut fmt::Formatter<'_>) -> fmt::Result> =
290 AtomicRef::new(&(default_def_id_debug as fn(_, &mut fmt::Formatter<'_>) -> _));
292 impl fmt::Debug for DefId {
293 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
294 (*DEF_ID_DEBUG)(*self, f)
298 rustc_data_structures::define_id_collections!(DefIdMap, DefIdSet, DefId);
300 /// A LocalDefId is equivalent to a DefId with `krate == LOCAL_CRATE`. Since
301 /// we encode this information in the type, we can ensure at compile time that
302 /// no DefIds from upstream crates get thrown into the mix. There are quite a
303 /// few cases where we know that only DefIds from the local crate are expected
304 /// and a DefId from a different crate would signify a bug somewhere. This
305 /// is when LocalDefId comes in handy.
306 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
307 pub struct LocalDefId {
308 pub local_def_index: DefIndex,
311 impl Idx for LocalDefId {
313 fn new(idx: usize) -> Self {
314 LocalDefId { local_def_index: Idx::new(idx) }
317 fn index(self) -> usize {
318 self.local_def_index.index()
324 pub fn to_def_id(self) -> DefId {
325 DefId { krate: LOCAL_CRATE, index: self.local_def_index }
329 pub fn is_top_level_module(self) -> bool {
330 self.local_def_index == CRATE_DEF_INDEX
334 impl fmt::Debug for LocalDefId {
335 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
336 self.to_def_id().fmt(f)
340 impl<E: Encoder> Encodable<E> for LocalDefId {
341 fn encode(&self, s: &mut E) -> Result<(), E::Error> {
342 self.to_def_id().encode(s)
346 impl<D: Decoder> Decodable<D> for LocalDefId {
347 fn decode(d: &mut D) -> Result<LocalDefId, D::Error> {
348 DefId::decode(d).map(|d| d.expect_local())
352 impl<CTX: HashStableContext> HashStable<CTX> for DefId {
353 fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
354 hcx.hash_def_id(*self, hasher)
358 impl<CTX: HashStableContext> HashStable<CTX> for CrateNum {
359 fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
360 hcx.hash_crate_num(*self, hasher)