compiler/rustc_span/src/def_id.rs

   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, ToStableHashKey};
   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;
  10 use std::fmt;
  11
  12 rustc_index::newtype_index! {
  13     pub struct CrateNum {
  14         ENCODABLE = custom
  15         DEBUG_FORMAT = "crate{}"
  16     }
  17 }
  18
  19 /// Item definitions in the currently-compiled crate would have the `CrateNum`
  20 /// `LOCAL_CRATE` in their `DefId`.
  21 pub const LOCAL_CRATE: CrateNum = CrateNum::from_u32(0);
  22
  23 impl CrateNum {
  24     #[inline]
  25     pub fn new(x: usize) -> CrateNum {
  26         CrateNum::from_usize(x)
  27     }
  28
  29     #[inline]
  30     pub fn as_def_id(&self) -> DefId {
  31         DefId { krate: *self, index: CRATE_DEF_INDEX }
  32     }
  33 }
  34
  35 impl fmt::Display for CrateNum {
  36     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  37         fmt::Display::fmt(&self.private, f)
  38     }
  39 }
  40
  41 /// As a local identifier, a `CrateNum` is only meaningful within its context, e.g. within a tcx.
  42 /// Therefore, make sure to include the context when encode a `CrateNum`.
  43 impl<E: Encoder> Encodable<E> for CrateNum {
  44     default fn encode(&self, s: &mut E) -> Result<(), E::Error> {
  45         s.emit_u32(self.as_u32())
  46     }
  47 }
  48
  49 impl<D: Decoder> Decodable<D> for CrateNum {
  50     default fn decode(d: &mut D) -> Result<CrateNum, D::Error> {
  51         Ok(CrateNum::from_u32(d.read_u32()?))
  52     }
  53 }
  54
  55 /// A `DefPathHash` is a fixed-size representation of a `DefPath` that is
  56 /// stable across crate and compilation session boundaries. It consists of two
  57 /// separate 64-bit hashes. The first uniquely identifies the crate this
  58 /// `DefPathHash` originates from (see [StableCrateId]), and the second
  59 /// uniquely identifies the corresponding `DefPath` within that crate. Together
  60 /// they form a unique identifier within an entire crate graph.
  61 ///
  62 /// There is a very small chance of hash collisions, which would mean that two
  63 /// different `DefPath`s map to the same `DefPathHash`. Proceeding compilation
  64 /// with such a hash collision would very probably lead to an ICE, and in the
  65 /// worst case lead to a silent mis-compilation. The compiler therefore actively
  66 /// and exhaustively checks for such hash collisions and aborts compilation if
  67 /// it finds one.
  68 ///
  69 /// `DefPathHash` uses 64-bit hashes for both the crate-id part and the
  70 /// crate-internal part, even though it is likely that there are many more
  71 /// `LocalDefId`s in a single crate than there are individual crates in a crate
  72 /// graph. Since we use the same number of bits in both cases, the collision
  73 /// probability for the crate-local part will be quite a bit higher (though
  74 /// still very small).
  75 ///
  76 /// This imbalance is not by accident: A hash collision in the
  77 /// crate-local part of a `DefPathHash` will be detected and reported while
  78 /// compiling the crate in question. Such a collision does not depend on
  79 /// outside factors and can be easily fixed by the crate maintainer (e.g. by
  80 /// renaming the item in question or by bumping the crate version in a harmless
  81 /// way).
  82 ///
  83 /// A collision between crate-id hashes on the other hand is harder to fix
  84 /// because it depends on the set of crates in the entire crate graph of a
  85 /// compilation session. Again, using the same crate with a different version
  86 /// number would fix the issue with a high probability -- but that might be
  87 /// easier said then done if the crates in questions are dependencies of
  88 /// third-party crates.
  89 ///
  90 /// That being said, given a high quality hash function, the collision
  91 /// probabilities in question are very small. For example, for a big crate like
  92 /// `rustc_middle` (with ~50000 `LocalDefId`s as of the time of writing) there
  93 /// is a probability of roughly 1 in 14,750,000,000 of a crate-internal
  94 /// collision occurring. For a big crate graph with 1000 crates in it, there is
  95 /// a probability of 1 in 36,890,000,000,000 of a `StableCrateId` collision.
  96 #[derive(Copy, Clone, Hash, PartialEq, Eq, PartialOrd, Ord, Debug)]
  97 #[derive(HashStable_Generic, Encodable, Decodable)]
  98 pub struct DefPathHash(pub Fingerprint);
  99
 100 impl DefPathHash {
 101     /// Returns the [StableCrateId] identifying the crate this [DefPathHash]
 102     /// originates from.
 103     #[inline]
 104     pub fn stable_crate_id(&self) -> StableCrateId {
 105         StableCrateId(self.0.as_value().0)
 106     }
 107
 108     /// Returns the crate-local part of the [DefPathHash].
 109     ///
 110     /// Used for tests.
 111     #[inline]
 112     pub fn local_hash(&self) -> u64 {
 113         self.0.as_value().1
 114     }
 115
 116     /// Builds a new [DefPathHash] with the given [StableCrateId] and
 117     /// `local_hash`, where `local_hash` must be unique within its crate.
 118     pub fn new(stable_crate_id: StableCrateId, local_hash: u64) -> DefPathHash {
 119         DefPathHash(Fingerprint::new(stable_crate_id.0, local_hash))
 120     }
 121 }
 122
 123 impl Borrow<Fingerprint> for DefPathHash {
 124     #[inline]
 125     fn borrow(&self) -> &Fingerprint {
 126         &self.0
 127     }
 128 }
 129
 130 /// A [StableCrateId] is a 64 bit hash of `(crate-name, crate-disambiguator)`. It
 131 /// is to [CrateNum] what [DefPathHash] is to [DefId]. It is stable across
 132 /// compilation sessions.
 133 ///
 134 /// Since the ID is a hash value there is a (very small) chance that two crates
 135 /// end up with the same [StableCrateId]. The compiler will check for such
 136 /// collisions when loading crates and abort compilation in order to avoid
 137 /// further trouble.
 138 #[derive(Copy, Clone, Hash, PartialEq, Eq, PartialOrd, Ord, Debug, Encodable, Decodable)]
 139 pub struct StableCrateId(u64);
 140
 141 impl StableCrateId {
 142     /// Computes the stable ID for a crate with the given name and
 143     /// disambiguator.
 144     pub fn new(crate_name: &str, crate_disambiguator: CrateDisambiguator) -> StableCrateId {
 145         use std::hash::Hash;
 146
 147         let mut hasher = StableHasher::new();
 148         crate_name.hash(&mut hasher);
 149         crate_disambiguator.hash(&mut hasher);
 150         StableCrateId(hasher.finish())
 151     }
 152 }
 153
 154 rustc_index::newtype_index! {
 155     /// A DefIndex is an index into the hir-map for a crate, identifying a
 156     /// particular definition. It should really be considered an interned
 157     /// shorthand for a particular DefPath.
 158     pub struct DefIndex {
 159         ENCODABLE = custom // (only encodable in metadata)
 160
 161         DEBUG_FORMAT = "DefIndex({})",
 162         /// The crate root is always assigned index 0 by the AST Map code,
 163         /// thanks to `NodeCollector::new`.
 164         const CRATE_DEF_INDEX = 0,
 165     }
 166 }
 167
 168 impl<E: Encoder> Encodable<E> for DefIndex {
 169     default fn encode(&self, _: &mut E) -> Result<(), E::Error> {
 170         panic!("cannot encode `DefIndex` with `{}`", std::any::type_name::<E>());
 171     }
 172 }
 173
 174 impl<D: Decoder> Decodable<D> for DefIndex {
 175     default fn decode(_: &mut D) -> Result<DefIndex, D::Error> {
 176         panic!("cannot decode `DefIndex` with `{}`", std::any::type_name::<D>());
 177     }
 178 }
 179
 180 /// A `DefId` identifies a particular *definition*, by combining a crate
 181 /// index and a def index.
 182 ///
 183 /// You can create a `DefId` from a `LocalDefId` using `local_def_id.to_def_id()`.
 184 #[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Copy)]
 185 pub struct DefId {
 186     pub krate: CrateNum,
 187     pub index: DefIndex,
 188 }
 189
 190 impl DefId {
 191     /// Makes a local `DefId` from the given `DefIndex`.
 192     #[inline]
 193     pub fn local(index: DefIndex) -> DefId {
 194         DefId { krate: LOCAL_CRATE, index }
 195     }
 196
 197     /// Returns whether the item is defined in the crate currently being compiled.
 198     #[inline]
 199     pub fn is_local(self) -> bool {
 200         self.krate == LOCAL_CRATE
 201     }
 202
 203     #[inline]
 204     pub fn as_local(self) -> Option<LocalDefId> {
 205         if self.is_local() { Some(LocalDefId { local_def_index: self.index }) } else { None }
 206     }
 207
 208     #[inline]
 209     pub fn expect_local(self) -> LocalDefId {
 210         self.as_local().unwrap_or_else(|| panic!("DefId::expect_local: `{:?}` isn't local", self))
 211     }
 212
 213     pub fn is_top_level_module(self) -> bool {
 214         self.is_local() && self.index == CRATE_DEF_INDEX
 215     }
 216 }
 217
 218 impl<E: Encoder> Encodable<E> for DefId {
 219     default fn encode(&self, s: &mut E) -> Result<(), E::Error> {
 220         s.emit_struct(false, |s| {
 221             s.emit_struct_field("krate", true, |s| self.krate.encode(s))?;
 222
 223             s.emit_struct_field("index", false, |s| self.index.encode(s))
 224         })
 225     }
 226 }
 227
 228 impl<D: Decoder> Decodable<D> for DefId {
 229     default fn decode(d: &mut D) -> Result<DefId, D::Error> {
 230         d.read_struct(|d| {
 231             Ok(DefId {
 232                 krate: d.read_struct_field("krate", Decodable::decode)?,
 233                 index: d.read_struct_field("index", Decodable::decode)?,
 234             })
 235         })
 236     }
 237 }
 238
 239 pub fn default_def_id_debug(def_id: DefId, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 240     f.debug_struct("DefId").field("krate", &def_id.krate).field("index", &def_id.index).finish()
 241 }
 242
 243 pub static DEF_ID_DEBUG: AtomicRef<fn(DefId, &mut fmt::Formatter<'_>) -> fmt::Result> =
 244     AtomicRef::new(&(default_def_id_debug as fn(_, &mut fmt::Formatter<'_>) -> _));
 245
 246 impl fmt::Debug for DefId {
 247     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 248         (*DEF_ID_DEBUG)(*self, f)
 249     }
 250 }
 251
 252 rustc_data_structures::define_id_collections!(DefIdMap, DefIdSet, DefId);
 253
 254 /// A LocalDefId is equivalent to a DefId with `krate == LOCAL_CRATE`. Since
 255 /// we encode this information in the type, we can ensure at compile time that
 256 /// no DefIds from upstream crates get thrown into the mix. There are quite a
 257 /// few cases where we know that only DefIds from the local crate are expected
 258 /// and a DefId from a different crate would signify a bug somewhere. This
 259 /// is when LocalDefId comes in handy.
 260 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
 261 pub struct LocalDefId {
 262     pub local_def_index: DefIndex,
 263 }
 264
 265 pub const CRATE_DEF_ID: LocalDefId = LocalDefId { local_def_index: CRATE_DEF_INDEX };
 266
 267 impl Idx for LocalDefId {
 268     #[inline]
 269     fn new(idx: usize) -> Self {
 270         LocalDefId { local_def_index: Idx::new(idx) }
 271     }
 272     #[inline]
 273     fn index(self) -> usize {
 274         self.local_def_index.index()
 275     }
 276 }
 277
 278 impl LocalDefId {
 279     #[inline]
 280     pub fn to_def_id(self) -> DefId {
 281         DefId { krate: LOCAL_CRATE, index: self.local_def_index }
 282     }
 283
 284     #[inline]
 285     pub fn is_top_level_module(self) -> bool {
 286         self.local_def_index == CRATE_DEF_INDEX
 287     }
 288 }
 289
 290 impl fmt::Debug for LocalDefId {
 291     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 292         self.to_def_id().fmt(f)
 293     }
 294 }
 295
 296 impl<E: Encoder> Encodable<E> for LocalDefId {
 297     fn encode(&self, s: &mut E) -> Result<(), E::Error> {
 298         self.to_def_id().encode(s)
 299     }
 300 }
 301
 302 impl<D: Decoder> Decodable<D> for LocalDefId {
 303     fn decode(d: &mut D) -> Result<LocalDefId, D::Error> {
 304         DefId::decode(d).map(|d| d.expect_local())
 305     }
 306 }
 307
 308 rustc_data_structures::define_id_collections!(LocalDefIdMap, LocalDefIdSet, LocalDefId);
 309
 310 impl<CTX: HashStableContext> HashStable<CTX> for DefId {
 311     #[inline]
 312     fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
 313         self.to_stable_hash_key(hcx).hash_stable(hcx, hasher);
 314     }
 315 }
 316
 317 impl<CTX: HashStableContext> HashStable<CTX> for LocalDefId {
 318     #[inline]
 319     fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
 320         self.to_stable_hash_key(hcx).hash_stable(hcx, hasher);
 321     }
 322 }
 323
 324 impl<CTX: HashStableContext> HashStable<CTX> for CrateNum {
 325     #[inline]
 326     fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
 327         self.to_stable_hash_key(hcx).hash_stable(hcx, hasher);
 328     }
 329 }
 330
 331 impl<CTX: HashStableContext> ToStableHashKey<CTX> for DefId {
 332     type KeyType = DefPathHash;
 333
 334     #[inline]
 335     fn to_stable_hash_key(&self, hcx: &CTX) -> DefPathHash {
 336         hcx.def_path_hash(*self)
 337     }
 338 }
 339
 340 impl<CTX: HashStableContext> ToStableHashKey<CTX> for LocalDefId {
 341     type KeyType = DefPathHash;
 342
 343     #[inline]
 344     fn to_stable_hash_key(&self, hcx: &CTX) -> DefPathHash {
 345         hcx.def_path_hash(self.to_def_id())
 346     }
 347 }
 348
 349 impl<CTX: HashStableContext> ToStableHashKey<CTX> for CrateNum {
 350     type KeyType = DefPathHash;
 351
 352     #[inline]
 353     fn to_stable_hash_key(&self, hcx: &CTX) -> DefPathHash {
 354         self.as_def_id().to_stable_hash_key(hcx)
 355     }
 356 }