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