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