compiler/rustc_span/src/lib.rs

   1 //! Source positions and related helper functions.
   2 //!
   3 //! Important concepts in this module include:
   4 //!
   5 //! - the *span*, represented by [`SpanData`] and related types;
   6 //! - source code as represented by a [`SourceMap`]; and
   7 //! - interned strings, represented by [`Symbol`]s, with some common symbols available statically in the [`sym`] module.
   8 //!
   9 //! Unlike most compilers, the span contains not only the position in the source code, but also various other metadata,
  10 //! such as the edition and macro hygiene. This metadata is stored in [`SyntaxContext`] and [`ExpnData`].
  11 //!
  12 //! ## Note
  13 //!
  14 //! This API is completely unstable and subject to change.
  15
  16 #![doc(html_root_url = "https://doc.rust-lang.org/nightly/nightly-rustc/")]
  17 #![feature(array_windows)]
  18 #![feature(if_let_guard)]
  19 #![feature(negative_impls)]
  20 #![feature(min_specialization)]
  21 #![feature(rustc_attrs)]
  22 #![deny(rustc::untranslatable_diagnostic)]
  23 #![deny(rustc::diagnostic_outside_of_impl)]
  24
  25 #[macro_use]
  26 extern crate rustc_macros;
  27
  28 #[macro_use]
  29 extern crate tracing;
  30
  31 use rustc_data_structures::AtomicRef;
  32 use rustc_macros::HashStable_Generic;
  33 use rustc_serialize::{Decodable, Decoder, Encodable, Encoder};
  34
  35 mod caching_source_map_view;
  36 pub mod source_map;
  37 pub use self::caching_source_map_view::CachingSourceMapView;
  38 use source_map::SourceMap;
  39
  40 pub mod edition;
  41 use edition::Edition;
  42 pub mod hygiene;
  43 use hygiene::Transparency;
  44 pub use hygiene::{DesugaringKind, ExpnKind, MacroKind};
  45 pub use hygiene::{ExpnData, ExpnHash, ExpnId, LocalExpnId, SyntaxContext};
  46 use rustc_data_structures::stable_hasher::HashingControls;
  47 pub mod def_id;
  48 use def_id::{CrateNum, DefId, DefPathHash, LocalDefId, LOCAL_CRATE};
  49 pub mod lev_distance;
  50 mod span_encoding;
  51 pub use span_encoding::{Span, DUMMY_SP};
  52
  53 pub mod symbol;
  54 pub use symbol::{sym, Symbol};
  55
  56 mod analyze_source_file;
  57 pub mod fatal_error;
  58
  59 pub mod profiling;
  60
  61 use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
  62 use rustc_data_structures::sync::{Lock, Lrc};
  63
  64 use std::borrow::Cow;
  65 use std::cmp::{self, Ordering};
  66 use std::fmt;
  67 use std::hash::Hash;
  68 use std::ops::{Add, Range, Sub};
  69 use std::path::{Path, PathBuf};
  70 use std::str::FromStr;
  71 use std::sync::Arc;
  72
  73 use md5::Digest;
  74 use md5::Md5;
  75 use sha1::Sha1;
  76 use sha2::Sha256;
  77
  78 #[cfg(test)]
  79 mod tests;
  80
  81 /// Per-session global variables: this struct is stored in thread-local storage
  82 /// in such a way that it is accessible without any kind of handle to all
  83 /// threads within the compilation session, but is not accessible outside the
  84 /// session.
  85 pub struct SessionGlobals {
  86     symbol_interner: symbol::Interner,
  87     span_interner: Lock<span_encoding::SpanInterner>,
  88     hygiene_data: Lock<hygiene::HygieneData>,
  89     source_map: Lock<Option<Lrc<SourceMap>>>,
  90 }
  91
  92 impl SessionGlobals {
  93     pub fn new(edition: Edition) -> SessionGlobals {
  94         SessionGlobals {
  95             symbol_interner: symbol::Interner::fresh(),
  96             span_interner: Lock::new(span_encoding::SpanInterner::default()),
  97             hygiene_data: Lock::new(hygiene::HygieneData::new(edition)),
  98             source_map: Lock::new(None),
  99         }
 100     }
 101 }
 102
 103 #[inline]
 104 pub fn create_session_globals_then<R>(edition: Edition, f: impl FnOnce() -> R) -> R {
 105     assert!(
 106         !SESSION_GLOBALS.is_set(),
 107         "SESSION_GLOBALS should never be overwritten! \
 108          Use another thread if you need another SessionGlobals"
 109     );
 110     let session_globals = SessionGlobals::new(edition);
 111     SESSION_GLOBALS.set(&session_globals, f)
 112 }
 113
 114 #[inline]
 115 pub fn set_session_globals_then<R>(session_globals: &SessionGlobals, f: impl FnOnce() -> R) -> R {
 116     assert!(
 117         !SESSION_GLOBALS.is_set(),
 118         "SESSION_GLOBALS should never be overwritten! \
 119          Use another thread if you need another SessionGlobals"
 120     );
 121     SESSION_GLOBALS.set(session_globals, f)
 122 }
 123
 124 #[inline]
 125 pub fn create_default_session_if_not_set_then<R, F>(f: F) -> R
 126 where
 127     F: FnOnce(&SessionGlobals) -> R,
 128 {
 129     create_session_if_not_set_then(edition::DEFAULT_EDITION, f)
 130 }
 131
 132 #[inline]
 133 pub fn create_session_if_not_set_then<R, F>(edition: Edition, f: F) -> R
 134 where
 135     F: FnOnce(&SessionGlobals) -> R,
 136 {
 137     if !SESSION_GLOBALS.is_set() {
 138         let session_globals = SessionGlobals::new(edition);
 139         SESSION_GLOBALS.set(&session_globals, || SESSION_GLOBALS.with(f))
 140     } else {
 141         SESSION_GLOBALS.with(f)
 142     }
 143 }
 144
 145 #[inline]
 146 pub fn with_session_globals<R, F>(f: F) -> R
 147 where
 148     F: FnOnce(&SessionGlobals) -> R,
 149 {
 150     SESSION_GLOBALS.with(f)
 151 }
 152
 153 #[inline]
 154 pub fn create_default_session_globals_then<R>(f: impl FnOnce() -> R) -> R {
 155     create_session_globals_then(edition::DEFAULT_EDITION, f)
 156 }
 157
 158 // If this ever becomes non thread-local, `decode_syntax_context`
 159 // and `decode_expn_id` will need to be updated to handle concurrent
 160 // deserialization.
 161 scoped_tls::scoped_thread_local!(static SESSION_GLOBALS: SessionGlobals);
 162
 163 // FIXME: We should use this enum or something like it to get rid of the
 164 // use of magic `/rust/1.x/...` paths across the board.
 165 #[derive(Debug, Eq, PartialEq, Clone, Ord, PartialOrd)]
 166 #[derive(Decodable)]
 167 pub enum RealFileName {
 168     LocalPath(PathBuf),
 169     /// For remapped paths (namely paths into libstd that have been mapped
 170     /// to the appropriate spot on the local host's file system, and local file
 171     /// system paths that have been remapped with `FilePathMapping`),
 172     Remapped {
 173         /// `local_path` is the (host-dependent) local path to the file. This is
 174         /// None if the file was imported from another crate
 175         local_path: Option<PathBuf>,
 176         /// `virtual_name` is the stable path rustc will store internally within
 177         /// build artifacts.
 178         virtual_name: PathBuf,
 179     },
 180 }
 181
 182 impl Hash for RealFileName {
 183     fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
 184         // To prevent #70924 from happening again we should only hash the
 185         // remapped (virtualized) path if that exists. This is because
 186         // virtualized paths to sysroot crates (/rust/$hash or /rust/$version)
 187         // remain stable even if the corresponding local_path changes
 188         self.remapped_path_if_available().hash(state)
 189     }
 190 }
 191
 192 // This is functionally identical to #[derive(Encodable)], with the exception of
 193 // an added assert statement
 194 impl<S: Encoder> Encodable<S> for RealFileName {
 195     fn encode(&self, encoder: &mut S) {
 196         match *self {
 197             RealFileName::LocalPath(ref local_path) => encoder.emit_enum_variant(0, |encoder| {
 198                 local_path.encode(encoder);
 199             }),
 200
 201             RealFileName::Remapped { ref local_path, ref virtual_name } => encoder
 202                 .emit_enum_variant(1, |encoder| {
 203                     // For privacy and build reproducibility, we must not embed host-dependant path in artifacts
 204                     // if they have been remapped by --remap-path-prefix
 205                     assert!(local_path.is_none());
 206                     local_path.encode(encoder);
 207                     virtual_name.encode(encoder);
 208                 }),
 209         }
 210     }
 211 }
 212
 213 impl RealFileName {
 214     /// Returns the path suitable for reading from the file system on the local host,
 215     /// if this information exists.
 216     /// Avoid embedding this in build artifacts; see `remapped_path_if_available()` for that.
 217     pub fn local_path(&self) -> Option<&Path> {
 218         match self {
 219             RealFileName::LocalPath(p) => Some(p),
 220             RealFileName::Remapped { local_path, virtual_name: _ } => local_path.as_deref(),
 221         }
 222     }
 223
 224     /// Returns the path suitable for reading from the file system on the local host,
 225     /// if this information exists.
 226     /// Avoid embedding this in build artifacts; see `remapped_path_if_available()` for that.
 227     pub fn into_local_path(self) -> Option<PathBuf> {
 228         match self {
 229             RealFileName::LocalPath(p) => Some(p),
 230             RealFileName::Remapped { local_path: p, virtual_name: _ } => p,
 231         }
 232     }
 233
 234     /// Returns the path suitable for embedding into build artifacts. This would still
 235     /// be a local path if it has not been remapped. A remapped path will not correspond
 236     /// to a valid file system path: see `local_path_if_available()` for something that
 237     /// is more likely to return paths into the local host file system.
 238     pub fn remapped_path_if_available(&self) -> &Path {
 239         match self {
 240             RealFileName::LocalPath(p)
 241             | RealFileName::Remapped { local_path: _, virtual_name: p } => p,
 242         }
 243     }
 244
 245     /// Returns the path suitable for reading from the file system on the local host,
 246     /// if this information exists. Otherwise returns the remapped name.
 247     /// Avoid embedding this in build artifacts; see `remapped_path_if_available()` for that.
 248     pub fn local_path_if_available(&self) -> &Path {
 249         match self {
 250             RealFileName::LocalPath(path)
 251             | RealFileName::Remapped { local_path: None, virtual_name: path }
 252             | RealFileName::Remapped { local_path: Some(path), virtual_name: _ } => path,
 253         }
 254     }
 255
 256     pub fn to_string_lossy(&self, display_pref: FileNameDisplayPreference) -> Cow<'_, str> {
 257         match display_pref {
 258             FileNameDisplayPreference::Local => self.local_path_if_available().to_string_lossy(),
 259             FileNameDisplayPreference::Remapped => {
 260                 self.remapped_path_if_available().to_string_lossy()
 261             }
 262             FileNameDisplayPreference::Short => self
 263                 .local_path_if_available()
 264                 .file_name()
 265                 .map_or_else(|| "".into(), |f| f.to_string_lossy()),
 266         }
 267     }
 268 }
 269
 270 /// Differentiates between real files and common virtual files.
 271 #[derive(Debug, Eq, PartialEq, Clone, Ord, PartialOrd, Hash)]
 272 #[derive(Decodable, Encodable)]
 273 pub enum FileName {
 274     Real(RealFileName),
 275     /// Call to `quote!`.
 276     QuoteExpansion(u64),
 277     /// Command line.
 278     Anon(u64),
 279     /// Hack in `src/librustc_ast/parse.rs`.
 280     // FIXME(jseyfried)
 281     MacroExpansion(u64),
 282     ProcMacroSourceCode(u64),
 283     /// Strings provided as `--cfg [cfgspec]` stored in a `crate_cfg`.
 284     CfgSpec(u64),
 285     /// Strings provided as crate attributes in the CLI.
 286     CliCrateAttr(u64),
 287     /// Custom sources for explicit parser calls from plugins and drivers.
 288     Custom(String),
 289     DocTest(PathBuf, isize),
 290     /// Post-substitution inline assembly from LLVM.
 291     InlineAsm(u64),
 292 }
 293
 294 impl From<PathBuf> for FileName {
 295     fn from(p: PathBuf) -> Self {
 296         assert!(!p.to_string_lossy().ends_with('>'));
 297         FileName::Real(RealFileName::LocalPath(p))
 298     }
 299 }
 300
 301 #[derive(Clone, Copy, Eq, PartialEq, Hash, Debug)]
 302 pub enum FileNameDisplayPreference {
 303     /// Display the path after the application of rewrite rules provided via `--remap-path-prefix`.
 304     /// This is appropriate for paths that get embedded into files produced by the compiler.
 305     Remapped,
 306     /// Display the path before the application of rewrite rules provided via `--remap-path-prefix`.
 307     /// This is appropriate for use in user-facing output (such as diagnostics).
 308     Local,
 309     /// Display only the filename, as a way to reduce the verbosity of the output.
 310     /// This is appropriate for use in user-facing output (such as diagnostics).
 311     Short,
 312 }
 313
 314 pub struct FileNameDisplay<'a> {
 315     inner: &'a FileName,
 316     display_pref: FileNameDisplayPreference,
 317 }
 318
 319 impl fmt::Display for FileNameDisplay<'_> {
 320     fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
 321         use FileName::*;
 322         match *self.inner {
 323             Real(ref name) => {
 324                 write!(fmt, "{}", name.to_string_lossy(self.display_pref))
 325             }
 326             QuoteExpansion(_) => write!(fmt, "<quote expansion>"),
 327             MacroExpansion(_) => write!(fmt, "<macro expansion>"),
 328             Anon(_) => write!(fmt, "<anon>"),
 329             ProcMacroSourceCode(_) => write!(fmt, "<proc-macro source code>"),
 330             CfgSpec(_) => write!(fmt, "<cfgspec>"),
 331             CliCrateAttr(_) => write!(fmt, "<crate attribute>"),
 332             Custom(ref s) => write!(fmt, "<{}>", s),
 333             DocTest(ref path, _) => write!(fmt, "{}", path.display()),
 334             InlineAsm(_) => write!(fmt, "<inline asm>"),
 335         }
 336     }
 337 }
 338
 339 impl<'a> FileNameDisplay<'a> {
 340     pub fn to_string_lossy(&self) -> Cow<'a, str> {
 341         match self.inner {
 342             FileName::Real(ref inner) => inner.to_string_lossy(self.display_pref),
 343             _ => Cow::from(self.to_string()),
 344         }
 345     }
 346 }
 347
 348 impl FileName {
 349     pub fn is_real(&self) -> bool {
 350         use FileName::*;
 351         match *self {
 352             Real(_) => true,
 353             Anon(_)
 354             | MacroExpansion(_)
 355             | ProcMacroSourceCode(_)
 356             | CfgSpec(_)
 357             | CliCrateAttr(_)
 358             | Custom(_)
 359             | QuoteExpansion(_)
 360             | DocTest(_, _)
 361             | InlineAsm(_) => false,
 362         }
 363     }
 364
 365     pub fn prefer_remapped(&self) -> FileNameDisplay<'_> {
 366         FileNameDisplay { inner: self, display_pref: FileNameDisplayPreference::Remapped }
 367     }
 368
 369     /// This may include transient local filesystem information.
 370     /// Must not be embedded in build outputs.
 371     pub fn prefer_local(&self) -> FileNameDisplay<'_> {
 372         FileNameDisplay { inner: self, display_pref: FileNameDisplayPreference::Local }
 373     }
 374
 375     pub fn display(&self, display_pref: FileNameDisplayPreference) -> FileNameDisplay<'_> {
 376         FileNameDisplay { inner: self, display_pref }
 377     }
 378
 379     pub fn macro_expansion_source_code(src: &str) -> FileName {
 380         let mut hasher = StableHasher::new();
 381         src.hash(&mut hasher);
 382         FileName::MacroExpansion(hasher.finish())
 383     }
 384
 385     pub fn anon_source_code(src: &str) -> FileName {
 386         let mut hasher = StableHasher::new();
 387         src.hash(&mut hasher);
 388         FileName::Anon(hasher.finish())
 389     }
 390
 391     pub fn proc_macro_source_code(src: &str) -> FileName {
 392         let mut hasher = StableHasher::new();
 393         src.hash(&mut hasher);
 394         FileName::ProcMacroSourceCode(hasher.finish())
 395     }
 396
 397     pub fn cfg_spec_source_code(src: &str) -> FileName {
 398         let mut hasher = StableHasher::new();
 399         src.hash(&mut hasher);
 400         FileName::QuoteExpansion(hasher.finish())
 401     }
 402
 403     pub fn cli_crate_attr_source_code(src: &str) -> FileName {
 404         let mut hasher = StableHasher::new();
 405         src.hash(&mut hasher);
 406         FileName::CliCrateAttr(hasher.finish())
 407     }
 408
 409     pub fn doc_test_source_code(path: PathBuf, line: isize) -> FileName {
 410         FileName::DocTest(path, line)
 411     }
 412
 413     pub fn inline_asm_source_code(src: &str) -> FileName {
 414         let mut hasher = StableHasher::new();
 415         src.hash(&mut hasher);
 416         FileName::InlineAsm(hasher.finish())
 417     }
 418 }
 419
 420 /// Represents a span.
 421 ///
 422 /// Spans represent a region of code, used for error reporting. Positions in spans
 423 /// are *absolute* positions from the beginning of the [`SourceMap`], not positions
 424 /// relative to [`SourceFile`]s. Methods on the `SourceMap` can be used to relate spans back
 425 /// to the original source.
 426 ///
 427 /// You must be careful if the span crosses more than one file, since you will not be
 428 /// able to use many of the functions on spans in source_map and you cannot assume
 429 /// that the length of the span is equal to `span.hi - span.lo`; there may be space in the
 430 /// [`BytePos`] range between files.
 431 ///
 432 /// `SpanData` is public because `Span` uses a thread-local interner and can't be
 433 /// sent to other threads, but some pieces of performance infra run in a separate thread.
 434 /// Using `Span` is generally preferred.
 435 #[derive(Clone, Copy, Hash, PartialEq, Eq)]
 436 pub struct SpanData {
 437     pub lo: BytePos,
 438     pub hi: BytePos,
 439     /// Information about where the macro came from, if this piece of
 440     /// code was created by a macro expansion.
 441     pub ctxt: SyntaxContext,
 442     pub parent: Option<LocalDefId>,
 443 }
 444
 445 // Order spans by position in the file.
 446 impl Ord for SpanData {
 447     fn cmp(&self, other: &Self) -> Ordering {
 448         let SpanData {
 449             lo: s_lo,
 450             hi: s_hi,
 451             ctxt: s_ctxt,
 452             // `LocalDefId` does not implement `Ord`.
 453             // The other fields are enough to determine in-file order.
 454             parent: _,
 455         } = self;
 456         let SpanData {
 457             lo: o_lo,
 458             hi: o_hi,
 459             ctxt: o_ctxt,
 460             // `LocalDefId` does not implement `Ord`.
 461             // The other fields are enough to determine in-file order.
 462             parent: _,
 463         } = other;
 464
 465         (s_lo, s_hi, s_ctxt).cmp(&(o_lo, o_hi, o_ctxt))
 466     }
 467 }
 468
 469 impl PartialOrd for SpanData {
 470     fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
 471         Some(self.cmp(other))
 472     }
 473 }
 474
 475 impl SpanData {
 476     #[inline]
 477     pub fn span(&self) -> Span {
 478         Span::new(self.lo, self.hi, self.ctxt, self.parent)
 479     }
 480     #[inline]
 481     pub fn with_lo(&self, lo: BytePos) -> Span {
 482         Span::new(lo, self.hi, self.ctxt, self.parent)
 483     }
 484     #[inline]
 485     pub fn with_hi(&self, hi: BytePos) -> Span {
 486         Span::new(self.lo, hi, self.ctxt, self.parent)
 487     }
 488     #[inline]
 489     pub fn with_ctxt(&self, ctxt: SyntaxContext) -> Span {
 490         Span::new(self.lo, self.hi, ctxt, self.parent)
 491     }
 492     #[inline]
 493     pub fn with_parent(&self, parent: Option<LocalDefId>) -> Span {
 494         Span::new(self.lo, self.hi, self.ctxt, parent)
 495     }
 496     /// Returns `true` if this is a dummy span with any hygienic context.
 497     #[inline]
 498     pub fn is_dummy(self) -> bool {
 499         self.lo.0 == 0 && self.hi.0 == 0
 500     }
 501     #[inline]
 502     pub fn is_visible(self, sm: &SourceMap) -> bool {
 503         !self.is_dummy() && sm.is_span_accessible(self.span())
 504     }
 505     /// Returns `true` if `self` fully encloses `other`.
 506     pub fn contains(self, other: Self) -> bool {
 507         self.lo <= other.lo && other.hi <= self.hi
 508     }
 509 }
 510
 511 // The interner is pointed to by a thread local value which is only set on the main thread
 512 // with parallelization is disabled. So we don't allow `Span` to transfer between threads
 513 // to avoid panics and other errors, even though it would be memory safe to do so.
 514 #[cfg(not(parallel_compiler))]
 515 impl !Send for Span {}
 516 #[cfg(not(parallel_compiler))]
 517 impl !Sync for Span {}
 518
 519 impl PartialOrd for Span {
 520     fn partial_cmp(&self, rhs: &Self) -> Option<Ordering> {
 521         PartialOrd::partial_cmp(&self.data(), &rhs.data())
 522     }
 523 }
 524 impl Ord for Span {
 525     fn cmp(&self, rhs: &Self) -> Ordering {
 526         Ord::cmp(&self.data(), &rhs.data())
 527     }
 528 }
 529
 530 impl Span {
 531     #[inline]
 532     pub fn lo(self) -> BytePos {
 533         self.data().lo
 534     }
 535     #[inline]
 536     pub fn with_lo(self, lo: BytePos) -> Span {
 537         self.data().with_lo(lo)
 538     }
 539     #[inline]
 540     pub fn hi(self) -> BytePos {
 541         self.data().hi
 542     }
 543     #[inline]
 544     pub fn with_hi(self, hi: BytePos) -> Span {
 545         self.data().with_hi(hi)
 546     }
 547     #[inline]
 548     pub fn eq_ctxt(self, other: Span) -> bool {
 549         self.data_untracked().ctxt == other.data_untracked().ctxt
 550     }
 551     #[inline]
 552     pub fn with_ctxt(self, ctxt: SyntaxContext) -> Span {
 553         self.data_untracked().with_ctxt(ctxt)
 554     }
 555     #[inline]
 556     pub fn parent(self) -> Option<LocalDefId> {
 557         self.data().parent
 558     }
 559     #[inline]
 560     pub fn with_parent(self, ctxt: Option<LocalDefId>) -> Span {
 561         self.data().with_parent(ctxt)
 562     }
 563
 564     /// Returns `true` if this is a dummy span with any hygienic context.
 565     #[inline]
 566     pub fn is_dummy(self) -> bool {
 567         self.data_untracked().is_dummy()
 568     }
 569
 570     #[inline]
 571     pub fn is_visible(self, sm: &SourceMap) -> bool {
 572         self.data_untracked().is_visible(sm)
 573     }
 574
 575     /// Returns `true` if this span comes from any kind of macro, desugaring or inlining.
 576     #[inline]
 577     pub fn from_expansion(self) -> bool {
 578         self.ctxt() != SyntaxContext::root()
 579     }
 580
 581     /// Returns `true` if `span` originates in a macro's expansion where debuginfo should be
 582     /// collapsed.
 583     pub fn in_macro_expansion_with_collapse_debuginfo(self) -> bool {
 584         let outer_expn = self.ctxt().outer_expn_data();
 585         matches!(outer_expn.kind, ExpnKind::Macro(..)) && outer_expn.collapse_debuginfo
 586     }
 587
 588     /// Returns `true` if this span comes from MIR inlining.
 589     pub fn is_inlined(self) -> bool {
 590         let outer_expn = self.ctxt().outer_expn_data();
 591         matches!(outer_expn.kind, ExpnKind::Inlined)
 592     }
 593
 594     /// Returns `true` if `span` originates in a derive-macro's expansion.
 595     pub fn in_derive_expansion(self) -> bool {
 596         matches!(self.ctxt().outer_expn_data().kind, ExpnKind::Macro(MacroKind::Derive, _))
 597     }
 598
 599     /// Gate suggestions that would not be appropriate in a context the user didn't write.
 600     pub fn can_be_used_for_suggestions(self) -> bool {
 601         !self.from_expansion()
 602         // FIXME: If this span comes from a `derive` macro but it points at code the user wrote,
 603         // the callsite span and the span will be pointing at different places. It also means that
 604         // we can safely provide suggestions on this span.
 605             || (matches!(self.ctxt().outer_expn_data().kind, ExpnKind::Macro(MacroKind::Derive, _))
 606                 && self.parent_callsite().map(|p| (p.lo(), p.hi())) != Some((self.lo(), self.hi())))
 607     }
 608
 609     #[inline]
 610     pub fn with_root_ctxt(lo: BytePos, hi: BytePos) -> Span {
 611         Span::new(lo, hi, SyntaxContext::root(), None)
 612     }
 613
 614     /// Returns a new span representing an empty span at the beginning of this span.
 615     #[inline]
 616     pub fn shrink_to_lo(self) -> Span {
 617         let span = self.data_untracked();
 618         span.with_hi(span.lo)
 619     }
 620     /// Returns a new span representing an empty span at the end of this span.
 621     #[inline]
 622     pub fn shrink_to_hi(self) -> Span {
 623         let span = self.data_untracked();
 624         span.with_lo(span.hi)
 625     }
 626
 627     #[inline]
 628     /// Returns `true` if `hi == lo`.
 629     pub fn is_empty(self) -> bool {
 630         let span = self.data_untracked();
 631         span.hi == span.lo
 632     }
 633
 634     /// Returns `self` if `self` is not the dummy span, and `other` otherwise.
 635     pub fn substitute_dummy(self, other: Span) -> Span {
 636         if self.is_dummy() { other } else { self }
 637     }
 638
 639     /// Returns `true` if `self` fully encloses `other`.
 640     pub fn contains(self, other: Span) -> bool {
 641         let span = self.data();
 642         let other = other.data();
 643         span.contains(other)
 644     }
 645
 646     /// Returns `true` if `self` touches `other`.
 647     pub fn overlaps(self, other: Span) -> bool {
 648         let span = self.data();
 649         let other = other.data();
 650         span.lo < other.hi && other.lo < span.hi
 651     }
 652
 653     /// Returns `true` if the spans are equal with regards to the source text.
 654     ///
 655     /// Use this instead of `==` when either span could be generated code,
 656     /// and you only care that they point to the same bytes of source text.
 657     pub fn source_equal(self, other: Span) -> bool {
 658         let span = self.data();
 659         let other = other.data();
 660         span.lo == other.lo && span.hi == other.hi
 661     }
 662
 663     /// Returns `Some(span)`, where the start is trimmed by the end of `other`.
 664     pub fn trim_start(self, other: Span) -> Option<Span> {
 665         let span = self.data();
 666         let other = other.data();
 667         if span.hi > other.hi { Some(span.with_lo(cmp::max(span.lo, other.hi))) } else { None }
 668     }
 669
 670     /// Returns the source span -- this is either the supplied span, or the span for
 671     /// the macro callsite that expanded to it.
 672     pub fn source_callsite(self) -> Span {
 673         let expn_data = self.ctxt().outer_expn_data();
 674         if !expn_data.is_root() { expn_data.call_site.source_callsite() } else { self }
 675     }
 676
 677     /// The `Span` for the tokens in the previous macro expansion from which `self` was generated,
 678     /// if any.
 679     pub fn parent_callsite(self) -> Option<Span> {
 680         let expn_data = self.ctxt().outer_expn_data();
 681         if !expn_data.is_root() { Some(expn_data.call_site) } else { None }
 682     }
 683
 684     /// Walk down the expansion ancestors to find a span that's contained within `outer`.
 685     pub fn find_ancestor_inside(mut self, outer: Span) -> Option<Span> {
 686         while !outer.contains(self) {
 687             self = self.parent_callsite()?;
 688         }
 689         Some(self)
 690     }
 691
 692     /// Like `find_ancestor_inside`, but specifically for when spans might not
 693     /// overlaps. Take care when using this, and prefer `find_ancestor_inside`
 694     /// when you know that the spans are nested (modulo macro expansion).
 695     pub fn find_ancestor_in_same_ctxt(mut self, other: Span) -> Option<Span> {
 696         while !Span::eq_ctxt(self, other) {
 697             self = self.parent_callsite()?;
 698         }
 699         Some(self)
 700     }
 701
 702     /// Edition of the crate from which this span came.
 703     pub fn edition(self) -> edition::Edition {
 704         self.ctxt().edition()
 705     }
 706
 707     #[inline]
 708     pub fn rust_2015(self) -> bool {
 709         self.edition() == edition::Edition::Edition2015
 710     }
 711
 712     #[inline]
 713     pub fn rust_2018(self) -> bool {
 714         self.edition() >= edition::Edition::Edition2018
 715     }
 716
 717     #[inline]
 718     pub fn rust_2021(self) -> bool {
 719         self.edition() >= edition::Edition::Edition2021
 720     }
 721
 722     #[inline]
 723     pub fn rust_2024(self) -> bool {
 724         self.edition() >= edition::Edition::Edition2024
 725     }
 726
 727     /// Returns the source callee.
 728     ///
 729     /// Returns `None` if the supplied span has no expansion trace,
 730     /// else returns the `ExpnData` for the macro definition
 731     /// corresponding to the source callsite.
 732     pub fn source_callee(self) -> Option<ExpnData> {
 733         fn source_callee(expn_data: ExpnData) -> ExpnData {
 734             let next_expn_data = expn_data.call_site.ctxt().outer_expn_data();
 735             if !next_expn_data.is_root() { source_callee(next_expn_data) } else { expn_data }
 736         }
 737         let expn_data = self.ctxt().outer_expn_data();
 738         if !expn_data.is_root() { Some(source_callee(expn_data)) } else { None }
 739     }
 740
 741     /// Checks if a span is "internal" to a macro in which `#[unstable]`
 742     /// items can be used (that is, a macro marked with
 743     /// `#[allow_internal_unstable]`).
 744     pub fn allows_unstable(self, feature: Symbol) -> bool {
 745         self.ctxt()
 746             .outer_expn_data()
 747             .allow_internal_unstable
 748             .map_or(false, |features| features.iter().any(|&f| f == feature))
 749     }
 750
 751     /// Checks if this span arises from a compiler desugaring of kind `kind`.
 752     pub fn is_desugaring(self, kind: DesugaringKind) -> bool {
 753         match self.ctxt().outer_expn_data().kind {
 754             ExpnKind::Desugaring(k) => k == kind,
 755             _ => false,
 756         }
 757     }
 758
 759     /// Returns the compiler desugaring that created this span, or `None`
 760     /// if this span is not from a desugaring.
 761     pub fn desugaring_kind(self) -> Option<DesugaringKind> {
 762         match self.ctxt().outer_expn_data().kind {
 763             ExpnKind::Desugaring(k) => Some(k),
 764             _ => None,
 765         }
 766     }
 767
 768     /// Checks if a span is "internal" to a macro in which `unsafe`
 769     /// can be used without triggering the `unsafe_code` lint.
 770     /// (that is, a macro marked with `#[allow_internal_unsafe]`).
 771     pub fn allows_unsafe(self) -> bool {
 772         self.ctxt().outer_expn_data().allow_internal_unsafe
 773     }
 774
 775     pub fn macro_backtrace(mut self) -> impl Iterator<Item = ExpnData> {
 776         let mut prev_span = DUMMY_SP;
 777         std::iter::from_fn(move || {
 778             loop {
 779                 let expn_data = self.ctxt().outer_expn_data();
 780                 if expn_data.is_root() {
 781                     return None;
 782                 }
 783
 784                 let is_recursive = expn_data.call_site.source_equal(prev_span);
 785
 786                 prev_span = self;
 787                 self = expn_data.call_site;
 788
 789                 // Don't print recursive invocations.
 790                 if !is_recursive {
 791                     return Some(expn_data);
 792                 }
 793             }
 794         })
 795     }
 796
 797     /// Returns a `Span` that would enclose both `self` and `end`.
 798     ///
 799     /// ```text
 800     ///     ____             ___
 801     ///     self lorem ipsum end
 802     ///     ^^^^^^^^^^^^^^^^^^^^
 803     /// ```
 804     pub fn to(self, end: Span) -> Span {
 805         let span_data = self.data();
 806         let end_data = end.data();
 807         // FIXME(jseyfried): `self.ctxt` should always equal `end.ctxt` here (cf. issue #23480).
 808         // Return the macro span on its own to avoid weird diagnostic output. It is preferable to
 809         // have an incomplete span than a completely nonsensical one.
 810         if span_data.ctxt != end_data.ctxt {
 811             if span_data.ctxt == SyntaxContext::root() {
 812                 return end;
 813             } else if end_data.ctxt == SyntaxContext::root() {
 814                 return self;
 815             }
 816             // Both spans fall within a macro.
 817             // FIXME(estebank): check if it is the *same* macro.
 818         }
 819         Span::new(
 820             cmp::min(span_data.lo, end_data.lo),
 821             cmp::max(span_data.hi, end_data.hi),
 822             if span_data.ctxt == SyntaxContext::root() { end_data.ctxt } else { span_data.ctxt },
 823             if span_data.parent == end_data.parent { span_data.parent } else { None },
 824         )
 825     }
 826
 827     /// Returns a `Span` between the end of `self` to the beginning of `end`.
 828     ///
 829     /// ```text
 830     ///     ____             ___
 831     ///     self lorem ipsum end
 832     ///         ^^^^^^^^^^^^^
 833     /// ```
 834     pub fn between(self, end: Span) -> Span {
 835         let span = self.data();
 836         let end = end.data();
 837         Span::new(
 838             span.hi,
 839             end.lo,
 840             if end.ctxt == SyntaxContext::root() { end.ctxt } else { span.ctxt },
 841             if span.parent == end.parent { span.parent } else { None },
 842         )
 843     }
 844
 845     /// Returns a `Span` from the beginning of `self` until the beginning of `end`.
 846     ///
 847     /// ```text
 848     ///     ____             ___
 849     ///     self lorem ipsum end
 850     ///     ^^^^^^^^^^^^^^^^^
 851     /// ```
 852     pub fn until(self, end: Span) -> Span {
 853         // Most of this function's body is copied from `to`.
 854         // We can't just do `self.to(end.shrink_to_lo())`,
 855         // because to also does some magic where it uses min/max so
 856         // it can handle overlapping spans. Some advanced mis-use of
 857         // `until` with different ctxts makes this visible.
 858         let span_data = self.data();
 859         let end_data = end.data();
 860         // FIXME(jseyfried): `self.ctxt` should always equal `end.ctxt` here (cf. issue #23480).
 861         // Return the macro span on its own to avoid weird diagnostic output. It is preferable to
 862         // have an incomplete span than a completely nonsensical one.
 863         if span_data.ctxt != end_data.ctxt {
 864             if span_data.ctxt == SyntaxContext::root() {
 865                 return end;
 866             } else if end_data.ctxt == SyntaxContext::root() {
 867                 return self;
 868             }
 869             // Both spans fall within a macro.
 870             // FIXME(estebank): check if it is the *same* macro.
 871         }
 872         Span::new(
 873             span_data.lo,
 874             end_data.lo,
 875             if end_data.ctxt == SyntaxContext::root() { end_data.ctxt } else { span_data.ctxt },
 876             if span_data.parent == end_data.parent { span_data.parent } else { None },
 877         )
 878     }
 879
 880     pub fn from_inner(self, inner: InnerSpan) -> Span {
 881         let span = self.data();
 882         Span::new(
 883             span.lo + BytePos::from_usize(inner.start),
 884             span.lo + BytePos::from_usize(inner.end),
 885             span.ctxt,
 886             span.parent,
 887         )
 888     }
 889
 890     /// Equivalent of `Span::def_site` from the proc macro API,
 891     /// except that the location is taken from the `self` span.
 892     pub fn with_def_site_ctxt(self, expn_id: ExpnId) -> Span {
 893         self.with_ctxt_from_mark(expn_id, Transparency::Opaque)
 894     }
 895
 896     /// Equivalent of `Span::call_site` from the proc macro API,
 897     /// except that the location is taken from the `self` span.
 898     pub fn with_call_site_ctxt(self, expn_id: ExpnId) -> Span {
 899         self.with_ctxt_from_mark(expn_id, Transparency::Transparent)
 900     }
 901
 902     /// Equivalent of `Span::mixed_site` from the proc macro API,
 903     /// except that the location is taken from the `self` span.
 904     pub fn with_mixed_site_ctxt(self, expn_id: ExpnId) -> Span {
 905         self.with_ctxt_from_mark(expn_id, Transparency::SemiTransparent)
 906     }
 907
 908     /// Produces a span with the same location as `self` and context produced by a macro with the
 909     /// given ID and transparency, assuming that macro was defined directly and not produced by
 910     /// some other macro (which is the case for built-in and procedural macros).
 911     pub fn with_ctxt_from_mark(self, expn_id: ExpnId, transparency: Transparency) -> Span {
 912         self.with_ctxt(SyntaxContext::root().apply_mark(expn_id, transparency))
 913     }
 914
 915     #[inline]
 916     pub fn apply_mark(self, expn_id: ExpnId, transparency: Transparency) -> Span {
 917         let span = self.data();
 918         span.with_ctxt(span.ctxt.apply_mark(expn_id, transparency))
 919     }
 920
 921     #[inline]
 922     pub fn remove_mark(&mut self) -> ExpnId {
 923         let mut span = self.data();
 924         let mark = span.ctxt.remove_mark();
 925         *self = Span::new(span.lo, span.hi, span.ctxt, span.parent);
 926         mark
 927     }
 928
 929     #[inline]
 930     pub fn adjust(&mut self, expn_id: ExpnId) -> Option<ExpnId> {
 931         let mut span = self.data();
 932         let mark = span.ctxt.adjust(expn_id);
 933         *self = Span::new(span.lo, span.hi, span.ctxt, span.parent);
 934         mark
 935     }
 936
 937     #[inline]
 938     pub fn normalize_to_macros_2_0_and_adjust(&mut self, expn_id: ExpnId) -> Option<ExpnId> {
 939         let mut span = self.data();
 940         let mark = span.ctxt.normalize_to_macros_2_0_and_adjust(expn_id);
 941         *self = Span::new(span.lo, span.hi, span.ctxt, span.parent);
 942         mark
 943     }
 944
 945     #[inline]
 946     pub fn glob_adjust(&mut self, expn_id: ExpnId, glob_span: Span) -> Option<Option<ExpnId>> {
 947         let mut span = self.data();
 948         let mark = span.ctxt.glob_adjust(expn_id, glob_span);
 949         *self = Span::new(span.lo, span.hi, span.ctxt, span.parent);
 950         mark
 951     }
 952
 953     #[inline]
 954     pub fn reverse_glob_adjust(
 955         &mut self,
 956         expn_id: ExpnId,
 957         glob_span: Span,
 958     ) -> Option<Option<ExpnId>> {
 959         let mut span = self.data();
 960         let mark = span.ctxt.reverse_glob_adjust(expn_id, glob_span);
 961         *self = Span::new(span.lo, span.hi, span.ctxt, span.parent);
 962         mark
 963     }
 964
 965     #[inline]
 966     pub fn normalize_to_macros_2_0(self) -> Span {
 967         let span = self.data();
 968         span.with_ctxt(span.ctxt.normalize_to_macros_2_0())
 969     }
 970
 971     #[inline]
 972     pub fn normalize_to_macro_rules(self) -> Span {
 973         let span = self.data();
 974         span.with_ctxt(span.ctxt.normalize_to_macro_rules())
 975     }
 976 }
 977
 978 impl Default for Span {
 979     fn default() -> Self {
 980         DUMMY_SP
 981     }
 982 }
 983
 984 impl<E: Encoder> Encodable<E> for Span {
 985     default fn encode(&self, s: &mut E) {
 986         let span = self.data();
 987         span.lo.encode(s);
 988         span.hi.encode(s);
 989     }
 990 }
 991 impl<D: Decoder> Decodable<D> for Span {
 992     default fn decode(s: &mut D) -> Span {
 993         let lo = Decodable::decode(s);
 994         let hi = Decodable::decode(s);
 995
 996         Span::new(lo, hi, SyntaxContext::root(), None)
 997     }
 998 }
 999
1000 /// Calls the provided closure, using the provided `SourceMap` to format
1001 /// any spans that are debug-printed during the closure's execution.
1002 ///
1003 /// Normally, the global `TyCtxt` is used to retrieve the `SourceMap`
1004 /// (see `rustc_interface::callbacks::span_debug1`). However, some parts
1005 /// of the compiler (e.g. `rustc_parse`) may debug-print `Span`s before
1006 /// a `TyCtxt` is available. In this case, we fall back to
1007 /// the `SourceMap` provided to this function. If that is not available,
1008 /// we fall back to printing the raw `Span` field values.
1009 pub fn with_source_map<T, F: FnOnce() -> T>(source_map: Lrc<SourceMap>, f: F) -> T {
1010     with_session_globals(|session_globals| {
1011         *session_globals.source_map.borrow_mut() = Some(source_map);
1012     });
1013     struct ClearSourceMap;
1014     impl Drop for ClearSourceMap {
1015         fn drop(&mut self) {
1016             with_session_globals(|session_globals| {
1017                 session_globals.source_map.borrow_mut().take();
1018             });
1019         }
1020     }
1021
1022     let _guard = ClearSourceMap;
1023     f()
1024 }
1025
1026 impl fmt::Debug for Span {
1027     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1028         with_session_globals(|session_globals| {
1029             if let Some(source_map) = &*session_globals.source_map.borrow() {
1030                 write!(f, "{} ({:?})", source_map.span_to_diagnostic_string(*self), self.ctxt())
1031             } else {
1032                 f.debug_struct("Span")
1033                     .field("lo", &self.lo())
1034                     .field("hi", &self.hi())
1035                     .field("ctxt", &self.ctxt())
1036                     .finish()
1037             }
1038         })
1039     }
1040 }
1041
1042 impl fmt::Debug for SpanData {
1043     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1044         fmt::Debug::fmt(&Span::new(self.lo, self.hi, self.ctxt, self.parent), f)
1045     }
1046 }
1047
1048 /// Identifies an offset of a multi-byte character in a `SourceFile`.
1049 #[derive(Copy, Clone, Encodable, Decodable, Eq, PartialEq, Debug)]
1050 pub struct MultiByteChar {
1051     /// The absolute offset of the character in the `SourceMap`.
1052     pub pos: BytePos,
1053     /// The number of bytes, `>= 2`.
1054     pub bytes: u8,
1055 }
1056
1057 /// Identifies an offset of a non-narrow character in a `SourceFile`.
1058 #[derive(Copy, Clone, Encodable, Decodable, Eq, PartialEq, Debug)]
1059 pub enum NonNarrowChar {
1060     /// Represents a zero-width character.
1061     ZeroWidth(BytePos),
1062     /// Represents a wide (full-width) character.
1063     Wide(BytePos),
1064     /// Represents a tab character, represented visually with a width of 4 characters.
1065     Tab(BytePos),
1066 }
1067
1068 impl NonNarrowChar {
1069     fn new(pos: BytePos, width: usize) -> Self {
1070         match width {
1071             0 => NonNarrowChar::ZeroWidth(pos),
1072             2 => NonNarrowChar::Wide(pos),
1073             4 => NonNarrowChar::Tab(pos),
1074             _ => panic!("width {} given for non-narrow character", width),
1075         }
1076     }
1077
1078     /// Returns the absolute offset of the character in the `SourceMap`.
1079     pub fn pos(&self) -> BytePos {
1080         match *self {
1081             NonNarrowChar::ZeroWidth(p) | NonNarrowChar::Wide(p) | NonNarrowChar::Tab(p) => p,
1082         }
1083     }
1084
1085     /// Returns the width of the character, 0 (zero-width) or 2 (wide).
1086     pub fn width(&self) -> usize {
1087         match *self {
1088             NonNarrowChar::ZeroWidth(_) => 0,
1089             NonNarrowChar::Wide(_) => 2,
1090             NonNarrowChar::Tab(_) => 4,
1091         }
1092     }
1093 }
1094
1095 impl Add<BytePos> for NonNarrowChar {
1096     type Output = Self;
1097
1098     fn add(self, rhs: BytePos) -> Self {
1099         match self {
1100             NonNarrowChar::ZeroWidth(pos) => NonNarrowChar::ZeroWidth(pos + rhs),
1101             NonNarrowChar::Wide(pos) => NonNarrowChar::Wide(pos + rhs),
1102             NonNarrowChar::Tab(pos) => NonNarrowChar::Tab(pos + rhs),
1103         }
1104     }
1105 }
1106
1107 impl Sub<BytePos> for NonNarrowChar {
1108     type Output = Self;
1109
1110     fn sub(self, rhs: BytePos) -> Self {
1111         match self {
1112             NonNarrowChar::ZeroWidth(pos) => NonNarrowChar::ZeroWidth(pos - rhs),
1113             NonNarrowChar::Wide(pos) => NonNarrowChar::Wide(pos - rhs),
1114             NonNarrowChar::Tab(pos) => NonNarrowChar::Tab(pos - rhs),
1115         }
1116     }
1117 }
1118
1119 /// Identifies an offset of a character that was normalized away from `SourceFile`.
1120 #[derive(Copy, Clone, Encodable, Decodable, Eq, PartialEq, Debug)]
1121 pub struct NormalizedPos {
1122     /// The absolute offset of the character in the `SourceMap`.
1123     pub pos: BytePos,
1124     /// The difference between original and normalized string at position.
1125     pub diff: u32,
1126 }
1127
1128 #[derive(PartialEq, Eq, Clone, Debug)]
1129 pub enum ExternalSource {
1130     /// No external source has to be loaded, since the `SourceFile` represents a local crate.
1131     Unneeded,
1132     Foreign {
1133         kind: ExternalSourceKind,
1134         /// Index of the file inside metadata.
1135         metadata_index: u32,
1136     },
1137 }
1138
1139 /// The state of the lazy external source loading mechanism of a `SourceFile`.
1140 #[derive(PartialEq, Eq, Clone, Debug)]
1141 pub enum ExternalSourceKind {
1142     /// The external source has been loaded already.
1143     Present(Lrc<String>),
1144     /// No attempt has been made to load the external source.
1145     AbsentOk,
1146     /// A failed attempt has been made to load the external source.
1147     AbsentErr,
1148     Unneeded,
1149 }
1150
1151 impl ExternalSource {
1152     pub fn get_source(&self) -> Option<&Lrc<String>> {
1153         match self {
1154             ExternalSource::Foreign { kind: ExternalSourceKind::Present(ref src), .. } => Some(src),
1155             _ => None,
1156         }
1157     }
1158 }
1159
1160 #[derive(Debug)]
1161 pub struct OffsetOverflowError;
1162
1163 #[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash, Encodable, Decodable)]
1164 #[derive(HashStable_Generic)]
1165 pub enum SourceFileHashAlgorithm {
1166     Md5,
1167     Sha1,
1168     Sha256,
1169 }
1170
1171 impl FromStr for SourceFileHashAlgorithm {
1172     type Err = ();
1173
1174     fn from_str(s: &str) -> Result<SourceFileHashAlgorithm, ()> {
1175         match s {
1176             "md5" => Ok(SourceFileHashAlgorithm::Md5),
1177             "sha1" => Ok(SourceFileHashAlgorithm::Sha1),
1178             "sha256" => Ok(SourceFileHashAlgorithm::Sha256),
1179             _ => Err(()),
1180         }
1181     }
1182 }
1183
1184 /// The hash of the on-disk source file used for debug info.
1185 #[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
1186 #[derive(HashStable_Generic, Encodable, Decodable)]
1187 pub struct SourceFileHash {
1188     pub kind: SourceFileHashAlgorithm,
1189     value: [u8; 32],
1190 }
1191
1192 impl SourceFileHash {
1193     pub fn new(kind: SourceFileHashAlgorithm, src: &str) -> SourceFileHash {
1194         let mut hash = SourceFileHash { kind, value: Default::default() };
1195         let len = hash.hash_len();
1196         let value = &mut hash.value[..len];
1197         let data = src.as_bytes();
1198         match kind {
1199             SourceFileHashAlgorithm::Md5 => {
1200                 value.copy_from_slice(&Md5::digest(data));
1201             }
1202             SourceFileHashAlgorithm::Sha1 => {
1203                 value.copy_from_slice(&Sha1::digest(data));
1204             }
1205             SourceFileHashAlgorithm::Sha256 => {
1206                 value.copy_from_slice(&Sha256::digest(data));
1207             }
1208         }
1209         hash
1210     }
1211
1212     /// Check if the stored hash matches the hash of the string.
1213     pub fn matches(&self, src: &str) -> bool {
1214         Self::new(self.kind, src) == *self
1215     }
1216
1217     /// The bytes of the hash.
1218     pub fn hash_bytes(&self) -> &[u8] {
1219         let len = self.hash_len();
1220         &self.value[..len]
1221     }
1222
1223     fn hash_len(&self) -> usize {
1224         match self.kind {
1225             SourceFileHashAlgorithm::Md5 => 16,
1226             SourceFileHashAlgorithm::Sha1 => 20,
1227             SourceFileHashAlgorithm::Sha256 => 32,
1228         }
1229     }
1230 }
1231
1232 #[derive(HashStable_Generic)]
1233 #[derive(Copy, PartialEq, PartialOrd, Clone, Ord, Eq, Hash, Debug, Encodable, Decodable)]
1234 pub enum DebuggerVisualizerType {
1235     Natvis,
1236     GdbPrettyPrinter,
1237 }
1238
1239 /// A single debugger visualizer file.
1240 #[derive(HashStable_Generic)]
1241 #[derive(Clone, Debug, Hash, PartialEq, Eq, PartialOrd, Ord, Encodable, Decodable)]
1242 pub struct DebuggerVisualizerFile {
1243     /// The complete debugger visualizer source.
1244     pub src: Arc<[u8]>,
1245     /// Indicates which visualizer type this targets.
1246     pub visualizer_type: DebuggerVisualizerType,
1247 }
1248
1249 impl DebuggerVisualizerFile {
1250     pub fn new(src: Arc<[u8]>, visualizer_type: DebuggerVisualizerType) -> Self {
1251         DebuggerVisualizerFile { src, visualizer_type }
1252     }
1253 }
1254
1255 #[derive(Clone)]
1256 pub enum SourceFileLines {
1257     /// The source file lines, in decoded (random-access) form.
1258     Lines(Vec<BytePos>),
1259
1260     /// The source file lines, in undecoded difference list form.
1261     Diffs(SourceFileDiffs),
1262 }
1263
1264 impl SourceFileLines {
1265     pub fn is_lines(&self) -> bool {
1266         matches!(self, SourceFileLines::Lines(_))
1267     }
1268 }
1269
1270 /// The source file lines in difference list form. This matches the form
1271 /// used within metadata, which saves space by exploiting the fact that the
1272 /// lines list is sorted and individual lines are usually not that long.
1273 ///
1274 /// We read it directly from metadata and only decode it into `Lines` form
1275 /// when necessary. This is a significant performance win, especially for
1276 /// small crates where very little of `std`'s metadata is used.
1277 #[derive(Clone)]
1278 pub struct SourceFileDiffs {
1279     /// Position of the first line. Note that this is always encoded as a
1280     /// `BytePos` because it is often much larger than any of the
1281     /// differences.
1282     line_start: BytePos,
1283
1284     /// Always 1, 2, or 4. Always as small as possible, while being big
1285     /// enough to hold the length of the longest line in the source file.
1286     /// The 1 case is by far the most common.
1287     bytes_per_diff: usize,
1288
1289     /// The number of diffs encoded in `raw_diffs`. Always one less than
1290     /// the number of lines in the source file.
1291     num_diffs: usize,
1292
1293     /// The diffs in "raw" form. Each segment of `bytes_per_diff` length
1294     /// encodes one little-endian diff. Note that they aren't LEB128
1295     /// encoded. This makes for much faster decoding. Besides, the
1296     /// bytes_per_diff==1 case is by far the most common, and LEB128
1297     /// encoding has no effect on that case.
1298     raw_diffs: Vec<u8>,
1299 }
1300
1301 /// A single source in the [`SourceMap`].
1302 #[derive(Clone)]
1303 pub struct SourceFile {
1304     /// The name of the file that the source came from. Source that doesn't
1305     /// originate from files has names between angle brackets by convention
1306     /// (e.g., `<anon>`).
1307     pub name: FileName,
1308     /// The complete source code.
1309     pub src: Option<Lrc<String>>,
1310     /// The source code's hash.
1311     pub src_hash: SourceFileHash,
1312     /// The external source code (used for external crates, which will have a `None`
1313     /// value as `self.src`.
1314     pub external_src: Lock<ExternalSource>,
1315     /// The start position of this source in the `SourceMap`.
1316     pub start_pos: BytePos,
1317     /// The end position of this source in the `SourceMap`.
1318     pub end_pos: BytePos,
1319     /// Locations of lines beginnings in the source code.
1320     pub lines: Lock<SourceFileLines>,
1321     /// Locations of multi-byte characters in the source code.
1322     pub multibyte_chars: Vec<MultiByteChar>,
1323     /// Width of characters that are not narrow in the source code.
1324     pub non_narrow_chars: Vec<NonNarrowChar>,
1325     /// Locations of characters removed during normalization.
1326     pub normalized_pos: Vec<NormalizedPos>,
1327     /// A hash of the filename, used for speeding up hashing in incremental compilation.
1328     pub name_hash: u128,
1329     /// Indicates which crate this `SourceFile` was imported from.
1330     pub cnum: CrateNum,
1331 }
1332
1333 impl<S: Encoder> Encodable<S> for SourceFile {
1334     fn encode(&self, s: &mut S) {
1335         self.name.encode(s);
1336         self.src_hash.encode(s);
1337         self.start_pos.encode(s);
1338         self.end_pos.encode(s);
1339
1340         // We are always in `Lines` form by the time we reach here.
1341         assert!(self.lines.borrow().is_lines());
1342         self.lines(|lines| {
1343             // Store the length.
1344             s.emit_u32(lines.len() as u32);
1345
1346             // Compute and store the difference list.
1347             if lines.len() != 0 {
1348                 let max_line_length = if lines.len() == 1 {
1349                     0
1350                 } else {
1351                     lines
1352                         .array_windows()
1353                         .map(|&[fst, snd]| snd - fst)
1354                         .map(|bp| bp.to_usize())
1355                         .max()
1356                         .unwrap()
1357                 };
1358
1359                 let bytes_per_diff: usize = match max_line_length {
1360                     0..=0xFF => 1,
1361                     0x100..=0xFFFF => 2,
1362                     _ => 4,
1363                 };
1364
1365                 // Encode the number of bytes used per diff.
1366                 s.emit_u8(bytes_per_diff as u8);
1367
1368                 // Encode the first element.
1369                 lines[0].encode(s);
1370
1371                 // Encode the difference list.
1372                 let diff_iter = lines.array_windows().map(|&[fst, snd]| snd - fst);
1373                 let num_diffs = lines.len() - 1;
1374                 let mut raw_diffs;
1375                 match bytes_per_diff {
1376                     1 => {
1377                         raw_diffs = Vec::with_capacity(num_diffs);
1378                         for diff in diff_iter {
1379                             raw_diffs.push(diff.0 as u8);
1380                         }
1381                     }
1382                     2 => {
1383                         raw_diffs = Vec::with_capacity(bytes_per_diff * num_diffs);
1384                         for diff in diff_iter {
1385                             raw_diffs.extend_from_slice(&(diff.0 as u16).to_le_bytes());
1386                         }
1387                     }
1388                     4 => {
1389                         raw_diffs = Vec::with_capacity(bytes_per_diff * num_diffs);
1390                         for diff in diff_iter {
1391                             raw_diffs.extend_from_slice(&(diff.0).to_le_bytes());
1392                         }
1393                     }
1394                     _ => unreachable!(),
1395                 }
1396                 s.emit_raw_bytes(&raw_diffs);
1397             }
1398         });
1399
1400         self.multibyte_chars.encode(s);
1401         self.non_narrow_chars.encode(s);
1402         self.name_hash.encode(s);
1403         self.normalized_pos.encode(s);
1404         self.cnum.encode(s);
1405     }
1406 }
1407
1408 impl<D: Decoder> Decodable<D> for SourceFile {
1409     fn decode(d: &mut D) -> SourceFile {
1410         let name: FileName = Decodable::decode(d);
1411         let src_hash: SourceFileHash = Decodable::decode(d);
1412         let start_pos: BytePos = Decodable::decode(d);
1413         let end_pos: BytePos = Decodable::decode(d);
1414         let lines = {
1415             let num_lines: u32 = Decodable::decode(d);
1416             if num_lines > 0 {
1417                 // Read the number of bytes used per diff.
1418                 let bytes_per_diff = d.read_u8() as usize;
1419
1420                 // Read the first element.
1421                 let line_start: BytePos = Decodable::decode(d);
1422
1423                 // Read the difference list.
1424                 let num_diffs = num_lines as usize - 1;
1425                 let raw_diffs = d.read_raw_bytes(bytes_per_diff * num_diffs).to_vec();
1426                 SourceFileLines::Diffs(SourceFileDiffs {
1427                     line_start,
1428                     bytes_per_diff,
1429                     num_diffs,
1430                     raw_diffs,
1431                 })
1432             } else {
1433                 SourceFileLines::Lines(vec![])
1434             }
1435         };
1436         let multibyte_chars: Vec<MultiByteChar> = Decodable::decode(d);
1437         let non_narrow_chars: Vec<NonNarrowChar> = Decodable::decode(d);
1438         let name_hash: u128 = Decodable::decode(d);
1439         let normalized_pos: Vec<NormalizedPos> = Decodable::decode(d);
1440         let cnum: CrateNum = Decodable::decode(d);
1441         SourceFile {
1442             name,
1443             start_pos,
1444             end_pos,
1445             src: None,
1446             src_hash,
1447             // Unused - the metadata decoder will construct
1448             // a new SourceFile, filling in `external_src` properly
1449             external_src: Lock::new(ExternalSource::Unneeded),
1450             lines: Lock::new(lines),
1451             multibyte_chars,
1452             non_narrow_chars,
1453             normalized_pos,
1454             name_hash,
1455             cnum,
1456         }
1457     }
1458 }
1459
1460 impl fmt::Debug for SourceFile {
1461     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
1462         write!(fmt, "SourceFile({:?})", self.name)
1463     }
1464 }
1465
1466 impl SourceFile {
1467     pub fn new(
1468         name: FileName,
1469         mut src: String,
1470         start_pos: BytePos,
1471         hash_kind: SourceFileHashAlgorithm,
1472     ) -> Self {
1473         // Compute the file hash before any normalization.
1474         let src_hash = SourceFileHash::new(hash_kind, &src);
1475         let normalized_pos = normalize_src(&mut src, start_pos);
1476
1477         let name_hash = {
1478             let mut hasher: StableHasher = StableHasher::new();
1479             name.hash(&mut hasher);
1480             hasher.finish::<u128>()
1481         };
1482         let end_pos = start_pos.to_usize() + src.len();
1483         assert!(end_pos <= u32::MAX as usize);
1484
1485         let (lines, multibyte_chars, non_narrow_chars) =
1486             analyze_source_file::analyze_source_file(&src, start_pos);
1487
1488         SourceFile {
1489             name,
1490             src: Some(Lrc::new(src)),
1491             src_hash,
1492             external_src: Lock::new(ExternalSource::Unneeded),
1493             start_pos,
1494             end_pos: Pos::from_usize(end_pos),
1495             lines: Lock::new(SourceFileLines::Lines(lines)),
1496             multibyte_chars,
1497             non_narrow_chars,
1498             normalized_pos,
1499             name_hash,
1500             cnum: LOCAL_CRATE,
1501         }
1502     }
1503
1504     pub fn lines<F, R>(&self, f: F) -> R
1505     where
1506         F: FnOnce(&[BytePos]) -> R,
1507     {
1508         let mut guard = self.lines.borrow_mut();
1509         match &*guard {
1510             SourceFileLines::Lines(lines) => f(lines),
1511             SourceFileLines::Diffs(SourceFileDiffs {
1512                 mut line_start,
1513                 bytes_per_diff,
1514                 num_diffs,
1515                 raw_diffs,
1516             }) => {
1517                 // Convert from "diffs" form to "lines" form.
1518                 let num_lines = num_diffs + 1;
1519                 let mut lines = Vec::with_capacity(num_lines);
1520                 lines.push(line_start);
1521
1522                 assert_eq!(*num_diffs, raw_diffs.len() / bytes_per_diff);
1523                 match bytes_per_diff {
1524                     1 => {
1525                         lines.extend(raw_diffs.into_iter().map(|&diff| {
1526                             line_start = line_start + BytePos(diff as u32);
1527                             line_start
1528                         }));
1529                     }
1530                     2 => {
1531                         lines.extend((0..*num_diffs).map(|i| {
1532                             let pos = bytes_per_diff * i;
1533                             let bytes = [raw_diffs[pos], raw_diffs[pos + 1]];
1534                             let diff = u16::from_le_bytes(bytes);
1535                             line_start = line_start + BytePos(diff as u32);
1536                             line_start
1537                         }));
1538                     }
1539                     4 => {
1540                         lines.extend((0..*num_diffs).map(|i| {
1541                             let pos = bytes_per_diff * i;
1542                             let bytes = [
1543                                 raw_diffs[pos],
1544                                 raw_diffs[pos + 1],
1545                                 raw_diffs[pos + 2],
1546                                 raw_diffs[pos + 3],
1547                             ];
1548                             let diff = u32::from_le_bytes(bytes);
1549                             line_start = line_start + BytePos(diff);
1550                             line_start
1551                         }));
1552                     }
1553                     _ => unreachable!(),
1554                 }
1555                 let res = f(&lines);
1556                 *guard = SourceFileLines::Lines(lines);
1557                 res
1558             }
1559         }
1560     }
1561
1562     /// Returns the `BytePos` of the beginning of the current line.
1563     pub fn line_begin_pos(&self, pos: BytePos) -> BytePos {
1564         let line_index = self.lookup_line(pos).unwrap();
1565         self.lines(|lines| lines[line_index])
1566     }
1567
1568     /// Add externally loaded source.
1569     /// If the hash of the input doesn't match or no input is supplied via None,
1570     /// it is interpreted as an error and the corresponding enum variant is set.
1571     /// The return value signifies whether some kind of source is present.
1572     pub fn add_external_src<F>(&self, get_src: F) -> bool
1573     where
1574         F: FnOnce() -> Option<String>,
1575     {
1576         if matches!(
1577             *self.external_src.borrow(),
1578             ExternalSource::Foreign { kind: ExternalSourceKind::AbsentOk, .. }
1579         ) {
1580             let src = get_src();
1581             let mut external_src = self.external_src.borrow_mut();
1582             // Check that no-one else have provided the source while we were getting it
1583             if let ExternalSource::Foreign {
1584                 kind: src_kind @ ExternalSourceKind::AbsentOk, ..
1585             } = &mut *external_src
1586             {
1587                 if let Some(mut src) = src {
1588                     // The src_hash needs to be computed on the pre-normalized src.
1589                     if self.src_hash.matches(&src) {
1590                         normalize_src(&mut src, BytePos::from_usize(0));
1591                         *src_kind = ExternalSourceKind::Present(Lrc::new(src));
1592                         return true;
1593                     }
1594                 } else {
1595                     *src_kind = ExternalSourceKind::AbsentErr;
1596                 }
1597
1598                 false
1599             } else {
1600                 self.src.is_some() || external_src.get_source().is_some()
1601             }
1602         } else {
1603             self.src.is_some() || self.external_src.borrow().get_source().is_some()
1604         }
1605     }
1606
1607     /// Gets a line from the list of pre-computed line-beginnings.
1608     /// The line number here is 0-based.
1609     pub fn get_line(&self, line_number: usize) -> Option<Cow<'_, str>> {
1610         fn get_until_newline(src: &str, begin: usize) -> &str {
1611             // We can't use `lines.get(line_number+1)` because we might
1612             // be parsing when we call this function and thus the current
1613             // line is the last one we have line info for.
1614             let slice = &src[begin..];
1615             match slice.find('\n') {
1616                 Some(e) => &slice[..e],
1617                 None => slice,
1618             }
1619         }
1620
1621         let begin = {
1622             let line = self.lines(|lines| lines.get(line_number).copied())?;
1623             let begin: BytePos = line - self.start_pos;
1624             begin.to_usize()
1625         };
1626
1627         if let Some(ref src) = self.src {
1628             Some(Cow::from(get_until_newline(src, begin)))
1629         } else if let Some(src) = self.external_src.borrow().get_source() {
1630             Some(Cow::Owned(String::from(get_until_newline(src, begin))))
1631         } else {
1632             None
1633         }
1634     }
1635
1636     pub fn is_real_file(&self) -> bool {
1637         self.name.is_real()
1638     }
1639
1640     #[inline]
1641     pub fn is_imported(&self) -> bool {
1642         self.src.is_none()
1643     }
1644
1645     pub fn count_lines(&self) -> usize {
1646         self.lines(|lines| lines.len())
1647     }
1648
1649     /// Finds the line containing the given position. The return value is the
1650     /// index into the `lines` array of this `SourceFile`, not the 1-based line
1651     /// number. If the source_file is empty or the position is located before the
1652     /// first line, `None` is returned.
1653     pub fn lookup_line(&self, pos: BytePos) -> Option<usize> {
1654         self.lines(|lines| lines.partition_point(|x| x <= &pos).checked_sub(1))
1655     }
1656
1657     pub fn line_bounds(&self, line_index: usize) -> Range<BytePos> {
1658         if self.is_empty() {
1659             return self.start_pos..self.end_pos;
1660         }
1661
1662         self.lines(|lines| {
1663             assert!(line_index < lines.len());
1664             if line_index == (lines.len() - 1) {
1665                 lines[line_index]..self.end_pos
1666             } else {
1667                 lines[line_index]..lines[line_index + 1]
1668             }
1669         })
1670     }
1671
1672     /// Returns whether or not the file contains the given `SourceMap` byte
1673     /// position. The position one past the end of the file is considered to be
1674     /// contained by the file. This implies that files for which `is_empty`
1675     /// returns true still contain one byte position according to this function.
1676     #[inline]
1677     pub fn contains(&self, byte_pos: BytePos) -> bool {
1678         byte_pos >= self.start_pos && byte_pos <= self.end_pos
1679     }
1680
1681     #[inline]
1682     pub fn is_empty(&self) -> bool {
1683         self.start_pos == self.end_pos
1684     }
1685
1686     /// Calculates the original byte position relative to the start of the file
1687     /// based on the given byte position.
1688     pub fn original_relative_byte_pos(&self, pos: BytePos) -> BytePos {
1689         // Diff before any records is 0. Otherwise use the previously recorded
1690         // diff as that applies to the following characters until a new diff
1691         // is recorded.
1692         let diff = match self.normalized_pos.binary_search_by(|np| np.pos.cmp(&pos)) {
1693             Ok(i) => self.normalized_pos[i].diff,
1694             Err(i) if i == 0 => 0,
1695             Err(i) => self.normalized_pos[i - 1].diff,
1696         };
1697
1698         BytePos::from_u32(pos.0 - self.start_pos.0 + diff)
1699     }
1700
1701     /// Converts an absolute `BytePos` to a `CharPos` relative to the `SourceFile`.
1702     pub fn bytepos_to_file_charpos(&self, bpos: BytePos) -> CharPos {
1703         // The number of extra bytes due to multibyte chars in the `SourceFile`.
1704         let mut total_extra_bytes = 0;
1705
1706         for mbc in self.multibyte_chars.iter() {
1707             debug!("{}-byte char at {:?}", mbc.bytes, mbc.pos);
1708             if mbc.pos < bpos {
1709                 // Every character is at least one byte, so we only
1710                 // count the actual extra bytes.
1711                 total_extra_bytes += mbc.bytes as u32 - 1;
1712                 // We should never see a byte position in the middle of a
1713                 // character.
1714                 assert!(bpos.to_u32() >= mbc.pos.to_u32() + mbc.bytes as u32);
1715             } else {
1716                 break;
1717             }
1718         }
1719
1720         assert!(self.start_pos.to_u32() + total_extra_bytes <= bpos.to_u32());
1721         CharPos(bpos.to_usize() - self.start_pos.to_usize() - total_extra_bytes as usize)
1722     }
1723
1724     /// Looks up the file's (1-based) line number and (0-based `CharPos`) column offset, for a
1725     /// given `BytePos`.
1726     pub fn lookup_file_pos(&self, pos: BytePos) -> (usize, CharPos) {
1727         let chpos = self.bytepos_to_file_charpos(pos);
1728         match self.lookup_line(pos) {
1729             Some(a) => {
1730                 let line = a + 1; // Line numbers start at 1
1731                 let linebpos = self.lines(|lines| lines[a]);
1732                 let linechpos = self.bytepos_to_file_charpos(linebpos);
1733                 let col = chpos - linechpos;
1734                 debug!("byte pos {:?} is on the line at byte pos {:?}", pos, linebpos);
1735                 debug!("char pos {:?} is on the line at char pos {:?}", chpos, linechpos);
1736                 debug!("byte is on line: {}", line);
1737                 assert!(chpos >= linechpos);
1738                 (line, col)
1739             }
1740             None => (0, chpos),
1741         }
1742     }
1743
1744     /// Looks up the file's (1-based) line number, (0-based `CharPos`) column offset, and (0-based)
1745     /// column offset when displayed, for a given `BytePos`.
1746     pub fn lookup_file_pos_with_col_display(&self, pos: BytePos) -> (usize, CharPos, usize) {
1747         let (line, col_or_chpos) = self.lookup_file_pos(pos);
1748         if line > 0 {
1749             let col = col_or_chpos;
1750             let linebpos = self.lines(|lines| lines[line - 1]);
1751             let col_display = {
1752                 let start_width_idx = self
1753                     .non_narrow_chars
1754                     .binary_search_by_key(&linebpos, |x| x.pos())
1755                     .unwrap_or_else(|x| x);
1756                 let end_width_idx = self
1757                     .non_narrow_chars
1758                     .binary_search_by_key(&pos, |x| x.pos())
1759                     .unwrap_or_else(|x| x);
1760                 let special_chars = end_width_idx - start_width_idx;
1761                 let non_narrow: usize = self.non_narrow_chars[start_width_idx..end_width_idx]
1762                     .iter()
1763                     .map(|x| x.width())
1764                     .sum();
1765                 col.0 - special_chars + non_narrow
1766             };
1767             (line, col, col_display)
1768         } else {
1769             let chpos = col_or_chpos;
1770             let col_display = {
1771                 let end_width_idx = self
1772                     .non_narrow_chars
1773                     .binary_search_by_key(&pos, |x| x.pos())
1774                     .unwrap_or_else(|x| x);
1775                 let non_narrow: usize =
1776                     self.non_narrow_chars[0..end_width_idx].iter().map(|x| x.width()).sum();
1777                 chpos.0 - end_width_idx + non_narrow
1778             };
1779             (0, chpos, col_display)
1780         }
1781     }
1782 }
1783
1784 /// Normalizes the source code and records the normalizations.
1785 fn normalize_src(src: &mut String, start_pos: BytePos) -> Vec<NormalizedPos> {
1786     let mut normalized_pos = vec![];
1787     remove_bom(src, &mut normalized_pos);
1788     normalize_newlines(src, &mut normalized_pos);
1789
1790     // Offset all the positions by start_pos to match the final file positions.
1791     for np in &mut normalized_pos {
1792         np.pos.0 += start_pos.0;
1793     }
1794
1795     normalized_pos
1796 }
1797
1798 /// Removes UTF-8 BOM, if any.
1799 fn remove_bom(src: &mut String, normalized_pos: &mut Vec<NormalizedPos>) {
1800     if src.starts_with('\u{feff}') {
1801         src.drain(..3);
1802         normalized_pos.push(NormalizedPos { pos: BytePos(0), diff: 3 });
1803     }
1804 }
1805
1806 /// Replaces `\r\n` with `\n` in-place in `src`.
1807 ///
1808 /// Returns error if there's a lone `\r` in the string.
1809 fn normalize_newlines(src: &mut String, normalized_pos: &mut Vec<NormalizedPos>) {
1810     if !src.as_bytes().contains(&b'\r') {
1811         return;
1812     }
1813
1814     // We replace `\r\n` with `\n` in-place, which doesn't break utf-8 encoding.
1815     // While we *can* call `as_mut_vec` and do surgery on the live string
1816     // directly, let's rather steal the contents of `src`. This makes the code
1817     // safe even if a panic occurs.
1818
1819     let mut buf = std::mem::replace(src, String::new()).into_bytes();
1820     let mut gap_len = 0;
1821     let mut tail = buf.as_mut_slice();
1822     let mut cursor = 0;
1823     let original_gap = normalized_pos.last().map_or(0, |l| l.diff);
1824     loop {
1825         let idx = match find_crlf(&tail[gap_len..]) {
1826             None => tail.len(),
1827             Some(idx) => idx + gap_len,
1828         };
1829         tail.copy_within(gap_len..idx, 0);
1830         tail = &mut tail[idx - gap_len..];
1831         if tail.len() == gap_len {
1832             break;
1833         }
1834         cursor += idx - gap_len;
1835         gap_len += 1;
1836         normalized_pos.push(NormalizedPos {
1837             pos: BytePos::from_usize(cursor + 1),
1838             diff: original_gap + gap_len as u32,
1839         });
1840     }
1841
1842     // Account for removed `\r`.
1843     // After `set_len`, `buf` is guaranteed to contain utf-8 again.
1844     let new_len = buf.len() - gap_len;
1845     unsafe {
1846         buf.set_len(new_len);
1847         *src = String::from_utf8_unchecked(buf);
1848     }
1849
1850     fn find_crlf(src: &[u8]) -> Option<usize> {
1851         let mut search_idx = 0;
1852         while let Some(idx) = find_cr(&src[search_idx..]) {
1853             if src[search_idx..].get(idx + 1) != Some(&b'\n') {
1854                 search_idx += idx + 1;
1855                 continue;
1856             }
1857             return Some(search_idx + idx);
1858         }
1859         None
1860     }
1861
1862     fn find_cr(src: &[u8]) -> Option<usize> {
1863         src.iter().position(|&b| b == b'\r')
1864     }
1865 }
1866
1867 // _____________________________________________________________________________
1868 // Pos, BytePos, CharPos
1869 //
1870
1871 pub trait Pos {
1872     fn from_usize(n: usize) -> Self;
1873     fn to_usize(&self) -> usize;
1874     fn from_u32(n: u32) -> Self;
1875     fn to_u32(&self) -> u32;
1876 }
1877
1878 macro_rules! impl_pos {
1879     (
1880         $(
1881             $(#[$attr:meta])*
1882             $vis:vis struct $ident:ident($inner_vis:vis $inner_ty:ty);
1883         )*
1884     ) => {
1885         $(
1886             $(#[$attr])*
1887             $vis struct $ident($inner_vis $inner_ty);
1888
1889             impl Pos for $ident {
1890                 #[inline(always)]
1891                 fn from_usize(n: usize) -> $ident {
1892                     $ident(n as $inner_ty)
1893                 }
1894
1895                 #[inline(always)]
1896                 fn to_usize(&self) -> usize {
1897                     self.0 as usize
1898                 }
1899
1900                 #[inline(always)]
1901                 fn from_u32(n: u32) -> $ident {
1902                     $ident(n as $inner_ty)
1903                 }
1904
1905                 #[inline(always)]
1906                 fn to_u32(&self) -> u32 {
1907                     self.0 as u32
1908                 }
1909             }
1910
1911             impl Add for $ident {
1912                 type Output = $ident;
1913
1914                 #[inline(always)]
1915                 fn add(self, rhs: $ident) -> $ident {
1916                     $ident(self.0 + rhs.0)
1917                 }
1918             }
1919
1920             impl Sub for $ident {
1921                 type Output = $ident;
1922
1923                 #[inline(always)]
1924                 fn sub(self, rhs: $ident) -> $ident {
1925                     $ident(self.0 - rhs.0)
1926                 }
1927             }
1928         )*
1929     };
1930 }
1931
1932 impl_pos! {
1933     /// A byte offset.
1934     ///
1935     /// Keep this small (currently 32-bits), as AST contains a lot of them.
1936     #[derive(Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord, Debug)]
1937     pub struct BytePos(pub u32);
1938
1939     /// A character offset.
1940     ///
1941     /// Because of multibyte UTF-8 characters, a byte offset
1942     /// is not equivalent to a character offset. The [`SourceMap`] will convert [`BytePos`]
1943     /// values to `CharPos` values as necessary.
1944     #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Debug)]
1945     pub struct CharPos(pub usize);
1946 }
1947
1948 impl<S: Encoder> Encodable<S> for BytePos {
1949     fn encode(&self, s: &mut S) {
1950         s.emit_u32(self.0);
1951     }
1952 }
1953
1954 impl<D: Decoder> Decodable<D> for BytePos {
1955     fn decode(d: &mut D) -> BytePos {
1956         BytePos(d.read_u32())
1957     }
1958 }
1959
1960 // _____________________________________________________________________________
1961 // Loc, SourceFileAndLine, SourceFileAndBytePos
1962 //
1963
1964 /// A source code location used for error reporting.
1965 #[derive(Debug, Clone)]
1966 pub struct Loc {
1967     /// Information about the original source.
1968     pub file: Lrc<SourceFile>,
1969     /// The (1-based) line number.
1970     pub line: usize,
1971     /// The (0-based) column offset.
1972     pub col: CharPos,
1973     /// The (0-based) column offset when displayed.
1974     pub col_display: usize,
1975 }
1976
1977 // Used to be structural records.
1978 #[derive(Debug)]
1979 pub struct SourceFileAndLine {
1980     pub sf: Lrc<SourceFile>,
1981     /// Index of line, starting from 0.
1982     pub line: usize,
1983 }
1984 #[derive(Debug)]
1985 pub struct SourceFileAndBytePos {
1986     pub sf: Lrc<SourceFile>,
1987     pub pos: BytePos,
1988 }
1989
1990 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
1991 pub struct LineInfo {
1992     /// Index of line, starting from 0.
1993     pub line_index: usize,
1994
1995     /// Column in line where span begins, starting from 0.
1996     pub start_col: CharPos,
1997
1998     /// Column in line where span ends, starting from 0, exclusive.
1999     pub end_col: CharPos,
2000 }
2001
2002 pub struct FileLines {
2003     pub file: Lrc<SourceFile>,
2004     pub lines: Vec<LineInfo>,
2005 }
2006
2007 pub static SPAN_TRACK: AtomicRef<fn(LocalDefId)> = AtomicRef::new(&((|_| {}) as fn(_)));
2008
2009 // _____________________________________________________________________________
2010 // SpanLinesError, SpanSnippetError, DistinctSources, MalformedSourceMapPositions
2011 //
2012
2013 pub type FileLinesResult = Result<FileLines, SpanLinesError>;
2014
2015 #[derive(Clone, PartialEq, Eq, Debug)]
2016 pub enum SpanLinesError {
2017     DistinctSources(DistinctSources),
2018 }
2019
2020 #[derive(Clone, PartialEq, Eq, Debug)]
2021 pub enum SpanSnippetError {
2022     IllFormedSpan(Span),
2023     DistinctSources(DistinctSources),
2024     MalformedForSourcemap(MalformedSourceMapPositions),
2025     SourceNotAvailable { filename: FileName },
2026 }
2027
2028 #[derive(Clone, PartialEq, Eq, Debug)]
2029 pub struct DistinctSources {
2030     pub begin: (FileName, BytePos),
2031     pub end: (FileName, BytePos),
2032 }
2033
2034 #[derive(Clone, PartialEq, Eq, Debug)]
2035 pub struct MalformedSourceMapPositions {
2036     pub name: FileName,
2037     pub source_len: usize,
2038     pub begin_pos: BytePos,
2039     pub end_pos: BytePos,
2040 }
2041
2042 /// Range inside of a `Span` used for diagnostics when we only have access to relative positions.
2043 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
2044 pub struct InnerSpan {
2045     pub start: usize,
2046     pub end: usize,
2047 }
2048
2049 impl InnerSpan {
2050     pub fn new(start: usize, end: usize) -> InnerSpan {
2051         InnerSpan { start, end }
2052     }
2053 }
2054
2055 /// Requirements for a `StableHashingContext` to be used in this crate.
2056 ///
2057 /// This is a hack to allow using the [`HashStable_Generic`] derive macro
2058 /// instead of implementing everything in rustc_middle.
2059 pub trait HashStableContext {
2060     fn def_path_hash(&self, def_id: DefId) -> DefPathHash;
2061     fn hash_spans(&self) -> bool;
2062     /// Accesses `sess.opts.unstable_opts.incremental_ignore_spans` since
2063     /// we don't have easy access to a `Session`
2064     fn unstable_opts_incremental_ignore_spans(&self) -> bool;
2065     fn def_span(&self, def_id: LocalDefId) -> Span;
2066     fn span_data_to_lines_and_cols(
2067         &mut self,
2068         span: &SpanData,
2069     ) -> Option<(Lrc<SourceFile>, usize, BytePos, usize, BytePos)>;
2070     fn hashing_controls(&self) -> HashingControls;
2071 }
2072
2073 impl<CTX> HashStable<CTX> for Span
2074 where
2075     CTX: HashStableContext,
2076 {
2077     /// Hashes a span in a stable way. We can't directly hash the span's `BytePos`
2078     /// fields (that would be similar to hashing pointers, since those are just
2079     /// offsets into the `SourceMap`). Instead, we hash the (file name, line, column)
2080     /// triple, which stays the same even if the containing `SourceFile` has moved
2081     /// within the `SourceMap`.
2082     ///
2083     /// Also note that we are hashing byte offsets for the column, not unicode
2084     /// codepoint offsets. For the purpose of the hash that's sufficient.
2085     /// Also, hashing filenames is expensive so we avoid doing it twice when the
2086     /// span starts and ends in the same file, which is almost always the case.
2087     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
2088         const TAG_VALID_SPAN: u8 = 0;
2089         const TAG_INVALID_SPAN: u8 = 1;
2090         const TAG_RELATIVE_SPAN: u8 = 2;
2091
2092         if !ctx.hash_spans() {
2093             return;
2094         }
2095
2096         let span = self.data_untracked();
2097         span.ctxt.hash_stable(ctx, hasher);
2098         span.parent.hash_stable(ctx, hasher);
2099
2100         if span.is_dummy() {
2101             Hash::hash(&TAG_INVALID_SPAN, hasher);
2102             return;
2103         }
2104
2105         if let Some(parent) = span.parent {
2106             let def_span = ctx.def_span(parent).data_untracked();
2107             if def_span.contains(span) {
2108                 // This span is enclosed in a definition: only hash the relative position.
2109                 Hash::hash(&TAG_RELATIVE_SPAN, hasher);
2110                 (span.lo - def_span.lo).to_u32().hash_stable(ctx, hasher);
2111                 (span.hi - def_span.lo).to_u32().hash_stable(ctx, hasher);
2112                 return;
2113             }
2114         }
2115
2116         // If this is not an empty or invalid span, we want to hash the last
2117         // position that belongs to it, as opposed to hashing the first
2118         // position past it.
2119         let Some((file, line_lo, col_lo, line_hi, col_hi)) = ctx.span_data_to_lines_and_cols(&span) else {
2120             Hash::hash(&TAG_INVALID_SPAN, hasher);
2121             return;
2122         };
2123
2124         Hash::hash(&TAG_VALID_SPAN, hasher);
2125         // We truncate the stable ID hash and line and column numbers. The chances
2126         // of causing a collision this way should be minimal.
2127         Hash::hash(&(file.name_hash as u64), hasher);
2128
2129         // Hash both the length and the end location (line/column) of a span. If we
2130         // hash only the length, for example, then two otherwise equal spans with
2131         // different end locations will have the same hash. This can cause a problem
2132         // during incremental compilation wherein a previous result for a query that
2133         // depends on the end location of a span will be incorrectly reused when the
2134         // end location of the span it depends on has changed (see issue #74890). A
2135         // similar analysis applies if some query depends specifically on the length
2136         // of the span, but we only hash the end location. So hash both.
2137
2138         let col_lo_trunc = (col_lo.0 as u64) & 0xFF;
2139         let line_lo_trunc = ((line_lo as u64) & 0xFF_FF_FF) << 8;
2140         let col_hi_trunc = (col_hi.0 as u64) & 0xFF << 32;
2141         let line_hi_trunc = ((line_hi as u64) & 0xFF_FF_FF) << 40;
2142         let col_line = col_lo_trunc | line_lo_trunc | col_hi_trunc | line_hi_trunc;
2143         let len = (span.hi - span.lo).0;
2144         Hash::hash(&col_line, hasher);
2145         Hash::hash(&len, hasher);
2146     }
2147 }