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};
   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 CrateId {
  14         ENCODABLE = custom
  15     }
  16 }
  17
  18 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
  19 pub enum CrateNum {
  20     /// A special `CrateNum` that we use for the `tcx.rcache` when decoding from
  21     /// the incr. comp. cache.
  22     ReservedForIncrCompCache,
  23     Index(CrateId),
  24 }
  25
  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));
  29
  30 impl Idx for CrateNum {
  31     #[inline]
  32     fn new(value: usize) -> Self {
  33         CrateNum::Index(Idx::new(value))
  34     }
  35
  36     #[inline]
  37     fn index(self) -> usize {
  38         match self {
  39             CrateNum::Index(idx) => Idx::index(idx),
  40             _ => panic!("Tried to get crate index of {:?}", self),
  41         }
  42     }
  43 }
  44
  45 impl CrateNum {
  46     pub fn new(x: usize) -> CrateNum {
  47         CrateNum::from_usize(x)
  48     }
  49
  50     pub fn from_usize(x: usize) -> CrateNum {
  51         CrateNum::Index(CrateId::from_usize(x))
  52     }
  53
  54     pub fn from_u32(x: u32) -> CrateNum {
  55         CrateNum::Index(CrateId::from_u32(x))
  56     }
  57
  58     pub fn as_usize(self) -> usize {
  59         match self {
  60             CrateNum::Index(id) => id.as_usize(),
  61             _ => panic!("tried to get index of non-standard crate {:?}", self),
  62         }
  63     }
  64
  65     pub fn as_u32(self) -> u32 {
  66         match self {
  67             CrateNum::Index(id) => id.as_u32(),
  68             _ => panic!("tried to get index of non-standard crate {:?}", self),
  69         }
  70     }
  71
  72     pub fn as_def_id(&self) -> DefId {
  73         DefId { krate: *self, index: CRATE_DEF_INDEX }
  74     }
  75 }
  76
  77 impl fmt::Display for CrateNum {
  78     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  79         match self {
  80             CrateNum::Index(id) => fmt::Display::fmt(&id.private, f),
  81             CrateNum::ReservedForIncrCompCache => write!(f, "crate for decoding incr comp cache"),
  82         }
  83     }
  84 }
  85
  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())
  91     }
  92 }
  93
  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()?))
  97     }
  98 }
  99
 100 impl ::std::fmt::Debug for CrateNum {
 101     fn fmt(&self, fmt: &mut ::std::fmt::Formatter<'_>) -> ::std::fmt::Result {
 102         match self {
 103             CrateNum::Index(id) => write!(fmt, "crate{}", id.private),
 104             CrateNum::ReservedForIncrCompCache => write!(fmt, "crate for decoding incr comp cache"),
 105         }
 106     }
 107 }
 108
 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.
 115 ///
 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
 121 /// it finds one.
 122 ///
 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).
 129 ///
 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
 135 /// way).
 136 ///
 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.
 143 ///
 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);
 153
 154 impl DefPathHash {
 155     /// Returns the [StableCrateId] identifying the crate this [DefPathHash]
 156     /// originates from.
 157     #[inline]
 158     pub fn stable_crate_id(&self) -> StableCrateId {
 159         StableCrateId(self.0.as_value().0)
 160     }
 161
 162     /// Returns the crate-local part of the [DefPathHash].
 163     ///
 164     /// Used for tests.
 165     #[inline]
 166     pub fn local_hash(&self) -> u64 {
 167         self.0.as_value().1
 168     }
 169
 170     /// Builds a new [DefPathHash] with the given [StableCrateId] and
 171     /// `local_hash`, where `local_hash` must be unique within its crate.
 172     pub fn new(stable_crate_id: StableCrateId, local_hash: u64) -> DefPathHash {
 173         DefPathHash(Fingerprint::new(stable_crate_id.0, local_hash))
 174     }
 175 }
 176
 177 impl Borrow<Fingerprint> for DefPathHash {
 178     #[inline]
 179     fn borrow(&self) -> &Fingerprint {
 180         &self.0
 181     }
 182 }
 183
 184 /// A [StableCrateId] is a 64 bit hash of `(crate-name, crate-disambiguator)`. It
 185 /// is to [CrateNum] what [DefPathHash] is to [DefId]. It is stable across
 186 /// compilation sessions.
 187 ///
 188 /// Since the ID is a hash value there is a (very small) chance that two crates
 189 /// end up with the same [StableCrateId]. The compiler will check for such
 190 /// collisions when loading crates and abort compilation in order to avoid
 191 /// further trouble.
 192 #[derive(Copy, Clone, Hash, PartialEq, Eq, PartialOrd, Ord, Debug, Encodable, Decodable)]
 193 pub struct StableCrateId(u64);
 194
 195 impl StableCrateId {
 196     /// Computes the stable ID for a crate with the given name and
 197     /// disambiguator.
 198     pub fn new(crate_name: &str, crate_disambiguator: CrateDisambiguator) -> StableCrateId {
 199         use std::hash::Hash;
 200
 201         let mut hasher = StableHasher::new();
 202         crate_name.hash(&mut hasher);
 203         crate_disambiguator.hash(&mut hasher);
 204         StableCrateId(hasher.finish())
 205     }
 206 }
 207
 208 rustc_index::newtype_index! {
 209     /// A DefIndex is an index into the hir-map for a crate, identifying a
 210     /// particular definition. It should really be considered an interned
 211     /// shorthand for a particular DefPath.
 212     pub struct DefIndex {
 213         ENCODABLE = custom // (only encodable in metadata)
 214
 215         DEBUG_FORMAT = "DefIndex({})",
 216         /// The crate root is always assigned index 0 by the AST Map code,
 217         /// thanks to `NodeCollector::new`.
 218         const CRATE_DEF_INDEX = 0,
 219     }
 220 }
 221
 222 impl<E: Encoder> Encodable<E> for DefIndex {
 223     default fn encode(&self, _: &mut E) -> Result<(), E::Error> {
 224         panic!("cannot encode `DefIndex` with `{}`", std::any::type_name::<E>());
 225     }
 226 }
 227
 228 impl<D: Decoder> Decodable<D> for DefIndex {
 229     default fn decode(_: &mut D) -> Result<DefIndex, D::Error> {
 230         panic!("cannot decode `DefIndex` with `{}`", std::any::type_name::<D>());
 231     }
 232 }
 233
 234 /// A `DefId` identifies a particular *definition*, by combining a crate
 235 /// index and a def index.
 236 ///
 237 /// You can create a `DefId` from a `LocalDefId` using `local_def_id.to_def_id()`.
 238 #[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Copy)]
 239 pub struct DefId {
 240     pub krate: CrateNum,
 241     pub index: DefIndex,
 242 }
 243
 244 impl DefId {
 245     /// Makes a local `DefId` from the given `DefIndex`.
 246     #[inline]
 247     pub fn local(index: DefIndex) -> DefId {
 248         DefId { krate: LOCAL_CRATE, index }
 249     }
 250
 251     /// Returns whether the item is defined in the crate currently being compiled.
 252     #[inline]
 253     pub fn is_local(self) -> bool {
 254         self.krate == LOCAL_CRATE
 255     }
 256
 257     #[inline]
 258     pub fn as_local(self) -> Option<LocalDefId> {
 259         if self.is_local() { Some(LocalDefId { local_def_index: self.index }) } else { None }
 260     }
 261
 262     #[inline]
 263     pub fn expect_local(self) -> LocalDefId {
 264         self.as_local().unwrap_or_else(|| panic!("DefId::expect_local: `{:?}` isn't local", self))
 265     }
 266
 267     pub fn is_top_level_module(self) -> bool {
 268         self.is_local() && self.index == CRATE_DEF_INDEX
 269     }
 270 }
 271
 272 impl<E: Encoder> Encodable<E> for DefId {
 273     default fn encode(&self, s: &mut E) -> Result<(), E::Error> {
 274         s.emit_struct("DefId", 2, |s| {
 275             s.emit_struct_field("krate", 0, |s| self.krate.encode(s))?;
 276
 277             s.emit_struct_field("index", 1, |s| self.index.encode(s))
 278         })
 279     }
 280 }
 281
 282 impl<D: Decoder> Decodable<D> for DefId {
 283     default fn decode(d: &mut D) -> Result<DefId, D::Error> {
 284         d.read_struct("DefId", 2, |d| {
 285             Ok(DefId {
 286                 krate: d.read_struct_field("krate", 0, Decodable::decode)?,
 287                 index: d.read_struct_field("index", 1, Decodable::decode)?,
 288             })
 289         })
 290     }
 291 }
 292
 293 pub fn default_def_id_debug(def_id: DefId, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 294     f.debug_struct("DefId").field("krate", &def_id.krate).field("index", &def_id.index).finish()
 295 }
 296
 297 pub static DEF_ID_DEBUG: AtomicRef<fn(DefId, &mut fmt::Formatter<'_>) -> fmt::Result> =
 298     AtomicRef::new(&(default_def_id_debug as fn(_, &mut fmt::Formatter<'_>) -> _));
 299
 300 impl fmt::Debug for DefId {
 301     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 302         (*DEF_ID_DEBUG)(*self, f)
 303     }
 304 }
 305
 306 rustc_data_structures::define_id_collections!(DefIdMap, DefIdSet, DefId);
 307
 308 /// A LocalDefId is equivalent to a DefId with `krate == LOCAL_CRATE`. Since
 309 /// we encode this information in the type, we can ensure at compile time that
 310 /// no DefIds from upstream crates get thrown into the mix. There are quite a
 311 /// few cases where we know that only DefIds from the local crate are expected
 312 /// and a DefId from a different crate would signify a bug somewhere. This
 313 /// is when LocalDefId comes in handy.
 314 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
 315 pub struct LocalDefId {
 316     pub local_def_index: DefIndex,
 317 }
 318
 319 pub const CRATE_DEF_ID: LocalDefId = LocalDefId { local_def_index: CRATE_DEF_INDEX };
 320
 321 impl Idx for LocalDefId {
 322     #[inline]
 323     fn new(idx: usize) -> Self {
 324         LocalDefId { local_def_index: Idx::new(idx) }
 325     }
 326     #[inline]
 327     fn index(self) -> usize {
 328         self.local_def_index.index()
 329     }
 330 }
 331
 332 impl LocalDefId {
 333     #[inline]
 334     pub fn to_def_id(self) -> DefId {
 335         DefId { krate: LOCAL_CRATE, index: self.local_def_index }
 336     }
 337
 338     #[inline]
 339     pub fn is_top_level_module(self) -> bool {
 340         self.local_def_index == CRATE_DEF_INDEX
 341     }
 342 }
 343
 344 impl fmt::Debug for LocalDefId {
 345     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 346         self.to_def_id().fmt(f)
 347     }
 348 }
 349
 350 impl<E: Encoder> Encodable<E> for LocalDefId {
 351     fn encode(&self, s: &mut E) -> Result<(), E::Error> {
 352         self.to_def_id().encode(s)
 353     }
 354 }
 355
 356 impl<D: Decoder> Decodable<D> for LocalDefId {
 357     fn decode(d: &mut D) -> Result<LocalDefId, D::Error> {
 358         DefId::decode(d).map(|d| d.expect_local())
 359     }
 360 }
 361
 362 rustc_data_structures::define_id_collections!(LocalDefIdMap, LocalDefIdSet, LocalDefId);
 363
 364 impl<CTX: HashStableContext> HashStable<CTX> for DefId {
 365     fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
 366         hcx.hash_def_id(*self, hasher)
 367     }
 368 }
 369
 370 impl<CTX: HashStableContext> HashStable<CTX> for CrateNum {
 371     fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
 372         hcx.hash_crate_num(*self, hasher)
 373     }
 374 }