compiler/rustc_span/src/def_id.rs

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