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