Skip to main content

sleigh/
source.rs

1//! Source ownership and stable source locations for SLEIGH tooling.
2//!
3//! [`SourceDb`] is the public owner for SLEIGH source text.  Library entry
4//! points take [`FileId`] handles instead of borrowed source strings so callers
5//! do not need to leak or otherwise pin source text to compile a specification.
6
7mod preprocess;
8
9use std::{
10    collections::{BTreeMap, HashMap},
11    error::Error,
12    fmt, fs, io,
13    ops::Range,
14    path::{Path, PathBuf},
15    sync::Arc,
16};
17
18use crate::diagnostic::Diagnostic;
19use jstd::{Identifier, registry::Registry};
20
21/// Stable identifier for a file stored in a [`SourceDb`].
22#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
23pub struct FileId(usize);
24
25impl FileId {
26    pub(crate) fn index(self) -> usize {
27        self.0
28    }
29
30    pub(crate) fn from_index(index: usize) -> Self {
31        Self(index)
32    }
33}
34
35/// Zero-based byte offset within a source file.
36#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
37pub struct BytePos(pub usize);
38
39/// A concrete physical source-file location.
40///
41/// `Span` is the public source-location type. It always names a physical
42/// [`FileId`], carries zero-based byte bounds for slicing, and carries
43/// one-based line/column endpoints for diagnostics and editor integrations.
44/// Internal preprocessing coordinates are mapped into `Span` before crossing
45/// public source APIs.
46#[derive(Debug, Clone, Copy, PartialEq, Eq)]
47pub struct Span {
48    /// File that contains this span.
49    pub file: FileId,
50    /// Zero-based start byte.
51    pub start: BytePos,
52    /// Zero-based exclusive end byte.
53    pub end: BytePos,
54    /// One-based start line.
55    pub start_line: usize,
56    /// One-based start column.
57    pub start_col: usize,
58    /// One-based end line.
59    pub end_line: usize,
60    /// One-based end column.
61    pub end_col: usize,
62}
63
64impl Span {
65    /// Creates a span from line/column endpoints when byte offsets are not
66    /// available in the same coordinate space.
67    ///
68    /// This is used only as a temporary carrier for diagnostics produced
69    /// against prepared text before they are mapped back to physical source.
70    pub(crate) fn from_line_cols(file: FileId, start: (usize, usize), end: (usize, usize)) -> Self {
71        Self {
72            file,
73            start: BytePos(0),
74            end: BytePos(0),
75            start_line: start.0,
76            start_col: start.1,
77            end_line: end.0,
78            end_col: end.1,
79        }
80    }
81
82    /// Creates a placeholder span with no meaningful source location.
83    ///
84    /// Used inside builder methods that produce diagnostics before the caller
85    /// has a chance to attach a real span. Callers in the resolver always
86    /// overwrite `diagnostic.primary` with a real span immediately after.
87    pub(crate) fn sentinel() -> Self {
88        Self {
89            file: FileId(0),
90            start: BytePos(0),
91            end: BytePos(0),
92            start_line: 0,
93            start_col: 0,
94            end_line: 0,
95            end_col: 0,
96        }
97    }
98
99    /// Creates a file-level span pointing at byte 0 of `file`.
100    ///
101    /// Used as a last-resort span when no finer location is available (e.g.
102    /// catastrophic parse failure before any tokens are produced).
103    pub fn file_level(file: FileId) -> Self {
104        Self {
105            file,
106            start: BytePos(0),
107            end: BytePos(0),
108            start_line: 1,
109            start_col: 1,
110            end_line: 1,
111            end_col: 1,
112        }
113    }
114
115    /// Creates a physical source span from byte coordinates and line/column
116    /// endpoints.
117    pub fn from_parts(
118        file: FileId,
119        start: BytePos,
120        end: BytePos,
121        start_line_col: (usize, usize),
122        end_line_col: (usize, usize),
123    ) -> Self {
124        Self {
125            file,
126            start,
127            end,
128            start_line: start_line_col.0,
129            start_col: start_line_col.1,
130            end_line: end_line_col.0,
131            end_col: end_line_col.1,
132        }
133    }
134}
135
136#[derive(Debug, Clone)]
137struct SourceFile {
138    path: PathBuf,
139    text: Box<str>,
140    line_starts: Vec<usize>,
141}
142
143impl SourceFile {
144    fn new(path: PathBuf, text: String) -> Self {
145        let line_starts = line_starts(&text);
146        Self {
147            path,
148            text: text.into_boxed_str(),
149            line_starts,
150        }
151    }
152}
153
154/// Stable identifier for a preprocessed source owned by [`SourceDb`].
155#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
156pub struct PreparedSourceId(usize);
157
158impl PreparedSourceId {
159    fn index(self) -> usize {
160        self.0
161    }
162}
163
164/// An include edge resolved by the source database.
165#[derive(Debug, Clone, PartialEq, Eq)]
166pub struct IncludeEdge {
167    /// File containing the include directive.
168    pub from: FileId,
169    /// File included by the directive.
170    pub to: FileId,
171    /// Span of the include path in the including file.
172    pub span: Span,
173}
174
175/// Mapping from one line of preprocessed output to the original source line.
176#[derive(Debug, Clone, Copy, PartialEq, Eq)]
177pub(crate) struct LineMapping {
178    /// One-based line in the preprocessed output.
179    pub generated_line: usize,
180    /// Original file.
181    pub source_file: FileId,
182    /// One-based line in the original file.
183    pub source_line: usize,
184}
185
186/// Stable identifier for a macro substitution emitted during preprocessing.
187#[derive(Identifier)]
188pub struct MacroExpansionId(pub(crate) usize);
189
190/// Stable identifier for a macro definition seen during preprocessing.
191#[derive(Identifier)]
192pub struct MacroDefinitionId(pub(crate) usize);
193
194/// Provenance class for generated preprocessed bytes.
195#[derive(Debug, Clone, Copy, PartialEq, Eq)]
196pub enum SourceOrigin {
197    /// Bytes copied directly from active source text.
198    Source,
199    /// Bytes were produced by a `$(NAME)` substitution.
200    MacroExpansion(MacroExpansionId),
201}
202
203/// Provenance for an active `@define` directive seen during preprocessing.
204#[derive(Debug, Clone, PartialEq, Eq)]
205pub struct MacroDefinition {
206    /// Macro name without directive syntax.
207    pub name: String,
208    /// Replacement text after preprocessing directive parsing.
209    pub value: String,
210    /// Span of the physical `@define` line.
211    pub span: Span,
212}
213
214/// Mapping from generated preprocessed bytes back to original source.
215#[derive(Debug, Clone, PartialEq, Eq)]
216pub(crate) struct SourceMapSegment {
217    /// Byte range in the generated preprocessed buffer.
218    pub generated: Range<usize>,
219    /// Original source span that caused these generated bytes.
220    pub source: Span,
221    /// Provenance class for this segment.
222    pub origin: SourceOrigin,
223}
224
225/// Provenance for a `$(NAME)` substitution inside an active source line.
226#[derive(Debug, Clone, PartialEq, Eq)]
227pub struct MacroExpansion {
228    /// Macro name without `$(` and `)`.
229    pub name: String,
230    /// Span of the macro use in the original physical file.
231    pub use_span: Span,
232    /// Replacement text inserted into the generated line.
233    pub replacement: String,
234    /// Byte range in the complete generated preprocessed buffer.
235    pub(crate) generated_range: Range<usize>,
236    /// Span of the active `@define`, if known.
237    pub definition: Option<Span>,
238    /// Id of the active `@define`, if it came from source text.
239    pub definition_id: Option<MacroDefinitionId>,
240}
241
242/// Error returned when a physical source file cannot be formatted from
243/// preprocessing metadata.
244#[derive(Debug, Clone, PartialEq, Eq)]
245pub enum FormatError {
246    /// No prepared source contains reconstruction records for this file.
247    MissingMetadata {
248        /// The file that could not be reconstructed.
249        file: FileId,
250    },
251    /// Reconstruction records exist but cannot form one coherent file.
252    IncompleteMetadata {
253        /// The file that could not be reconstructed.
254        file: FileId,
255    },
256}
257
258impl fmt::Display for FormatError {
259    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
260        match self {
261            Self::MissingMetadata { file } => {
262                write!(f, "missing preprocessing metadata for {file}")
263            }
264            Self::IncompleteMetadata { file } => {
265                write!(f, "incomplete preprocessing metadata for {file}")
266            }
267        }
268    }
269}
270
271impl Error for FormatError {}
272
273/// Role of one physical source line during preprocessing.
274#[derive(Debug, Clone, Copy, PartialEq, Eq)]
275pub enum FormatLineKind {
276    /// A non-directive line emitted into the prepared source.
277    ActiveSource,
278    /// A preprocessing directive line.
279    Directive,
280    /// A non-directive line skipped by an inactive conditional branch.
281    InactiveBranch,
282}
283
284/// Role of one line chunk in the prepared output.
285#[derive(Debug, Clone, Copy, PartialEq, Eq)]
286pub enum FormatChunkKind {
287    /// Text copied directly from a physical source line.
288    Direct,
289    /// Text produced by a macro substitution at the original source span.
290    MacroUse(MacroExpansionId),
291}
292
293/// Lossless formatting chunk for one physical line.
294#[derive(Debug, Clone, PartialEq, Eq)]
295pub struct FormatChunk {
296    /// Original source span for this chunk.
297    pub source: Span,
298    /// Exact original text for this chunk.
299    pub text: String,
300    /// Generated byte range when the chunk contributes to prepared text.
301    pub(crate) generated: Option<Range<usize>>,
302    /// Chunk role.
303    pub kind: FormatChunkKind,
304}
305
306/// Lossless formatting record for one physical source line.
307#[derive(Debug, Clone, PartialEq, Eq)]
308pub struct FormatLine {
309    /// Physical file containing this line.
310    pub file: FileId,
311    /// One-based physical line number.
312    pub line: usize,
313    /// Exact original line span, including the trailing newline if present.
314    pub span: Span,
315    /// Exact original line text, including the trailing newline if present.
316    pub text: String,
317    /// How preprocessing handled this line.
318    pub kind: FormatLineKind,
319    /// Generated byte range when this line contributes to prepared text.
320    pub(crate) generated: Option<Range<usize>>,
321    /// Chunk-level source/generation metadata for active source text.
322    pub chunks: Vec<FormatChunk>,
323}
324
325/// Preprocessor options.
326#[derive(Debug, Clone, Default, PartialEq, Eq)]
327pub struct PreprocessOptions {
328    /// Macro definitions available before the root file is processed.
329    pub defines: HashMap<String, String>,
330}
331
332#[derive(Debug, Clone)]
333struct PreparedSource {
334    root: FileId,
335    text: Arc<str>,
336    line_map: Vec<LineMapping>,
337    line_start_bytes: Vec<usize>,
338    source_map: Vec<SourceMapSegment>,
339    format_lines: Vec<FormatLine>,
340    include_edges: Vec<IncludeEdge>,
341    inactive_ranges: Vec<Span>,
342    macro_definitions: Registry<MacroDefinitionId, MacroDefinition>,
343    macro_expansions: Registry<MacroExpansionId, MacroExpansion>,
344}
345
346/// Owned collection of SLEIGH source files.
347///
348/// The database assigns stable [`FileId`] handles for the lifetime of the
349/// database.  Compile and analysis entry points use those handles to keep
350/// public APIs owned and source-aware.
351#[derive(Debug, Default, Clone)]
352pub struct SourceDb {
353    files: Vec<SourceFile>,
354    prepared: Vec<PreparedSource>,
355}
356
357impl SourceDb {
358    /// Creates an empty source database.
359    pub fn new() -> Self {
360        Self::default()
361    }
362
363    /// Adds a source file and returns its stable id.
364    pub fn add_file(&mut self, path: impl Into<PathBuf>, text: impl Into<String>) -> FileId {
365        let id = FileId(self.files.len());
366        self.files.push(SourceFile::new(path.into(), text.into()));
367        id
368    }
369
370    /// Reads one file from disk into the database.
371    pub fn add_file_from_path(&mut self, path: impl Into<PathBuf>) -> io::Result<FileId> {
372        let path = path.into();
373        if let Some(id) = self.file_by_path(&path) {
374            return Ok(id);
375        }
376
377        let text = fs::read_to_string(&path)?;
378        Ok(self.add_file(path, text))
379    }
380
381    /// Returns the path recorded for `file`.
382    pub fn path(&self, file: FileId) -> Option<&Path> {
383        self.files.get(file.index()).map(|file| file.path.as_path())
384    }
385
386    /// Returns the source text recorded for `file`.
387    pub fn text(&self, file: FileId) -> Option<&str> {
388        self.files.get(file.index()).map(|file| file.text.as_ref())
389    }
390
391    /// Returns both path and source text for `file`.
392    pub(crate) fn file(&self, file: FileId) -> Option<(&Path, &str)> {
393        self.files
394            .get(file.index())
395            .map(|file| (file.path.as_path(), file.text.as_ref()))
396    }
397
398    /// Returns a byte-based span for `file`.
399    pub fn span(&self, file: FileId, start: BytePos, end: BytePos) -> Option<Span> {
400        let source = self.files.get(file.index())?;
401        Some(Span::from_parts(
402            file,
403            start,
404            end,
405            line_col(source, start.0),
406            line_col(source, end.0),
407        ))
408    }
409
410    /// Returns the span covering one complete one-based line.
411    pub fn line_span(&self, file: FileId, line: usize) -> Option<Span> {
412        let source = self.files.get(file.index())?;
413        if line == 0 || line > source.line_starts.len() {
414            return None;
415        }
416
417        let start = source.line_starts[line - 1];
418        let end = if line < source.line_starts.len() {
419            source.line_starts[line] - 1
420        } else {
421            source.text.len()
422        };
423        self.span(file, BytePos(start), BytePos(end))
424    }
425
426    /// Converts one-based line/column endpoints to a physical source span.
427    pub fn span_from_line_cols(
428        &self,
429        file: FileId,
430        start_line_col: (usize, usize),
431        end_line_col: (usize, usize),
432    ) -> Option<Span> {
433        let start = byte_for_line_col(
434            self.files.get(file.index())?,
435            start_line_col.0,
436            start_line_col.1,
437        )?;
438        let end = byte_for_line_col(
439            self.files.get(file.index())?,
440            end_line_col.0,
441            end_line_col.1,
442        )?;
443        Some(Span::from_parts(
444            file,
445            BytePos(start),
446            BytePos(end),
447            start_line_col,
448            end_line_col,
449        ))
450    }
451
452    /// Finds a file by display path.
453    pub fn file_by_path(&self, path: &Path) -> Option<FileId> {
454        self.files
455            .iter()
456            .position(|file| file.path == path)
457            .map(FileId)
458    }
459
460    /// Preprocesses `root` through source-database include resolution.
461    pub fn preprocess(
462        &mut self,
463        root: FileId,
464        options: &PreprocessOptions,
465    ) -> Result<PreparedSourceId, Vec<Diagnostic>> {
466        let mut preprocessor = preprocess::Preprocessor::new(self, options);
467        preprocessor.preprocess_file(root);
468        let preprocess::Preprocessor {
469            output,
470            line_map,
471            source_map,
472            format_lines,
473            include_edges,
474            inactive_ranges,
475            macro_definitions,
476            macro_expansions,
477            diagnostics,
478            ..
479        } = preprocessor;
480
481        if !diagnostics.is_empty() {
482            return Err(diagnostics);
483        }
484
485        let line_start_bytes = line_starts(&output);
486        let id = PreparedSourceId(self.prepared.len());
487        self.prepared.push(PreparedSource {
488            root,
489            text: Arc::from(output.as_str()),
490            line_map,
491            line_start_bytes,
492            source_map,
493            format_lines,
494            include_edges,
495            inactive_ranges,
496            macro_definitions,
497            macro_expansions,
498        });
499        Ok(id)
500    }
501
502    /// Returns preprocessed text by id.
503    pub(crate) fn prepared_text(&self, id: PreparedSourceId) -> Option<&str> {
504        self.prepared
505            .get(id.index())
506            .map(|source| source.text.as_ref())
507    }
508
509    /// Returns the root file for a preprocessed source.
510    pub fn prepared_root(&self, id: PreparedSourceId) -> Option<FileId> {
511        self.prepared.get(id.index()).map(|source| source.root)
512    }
513
514    /// Returns include edges for a preprocessed source.
515    pub fn include_edges(&self, id: PreparedSourceId) -> Option<&[IncludeEdge]> {
516        self.prepared
517            .get(id.index())
518            .map(|source| source.include_edges.as_slice())
519    }
520
521    /// Returns inactive conditional ranges for a preprocessed source.
522    pub fn inactive_ranges(&self, id: PreparedSourceId) -> Option<&[Span]> {
523        self.prepared
524            .get(id.index())
525            .map(|source| source.inactive_ranges.as_slice())
526    }
527
528    /// Returns line mappings for a preprocessed source.
529    #[cfg(test)]
530    pub(crate) fn line_map(&self, id: PreparedSourceId) -> Option<&[LineMapping]> {
531        self.prepared
532            .get(id.index())
533            .map(|source| source.line_map.as_slice())
534    }
535
536    #[cfg(test)]
537    pub(crate) fn source_map(&self, id: PreparedSourceId) -> Option<&[SourceMapSegment]> {
538        self.prepared
539            .get(id.index())
540            .map(|source| source.source_map.as_slice())
541    }
542
543    /// Returns macro substitutions emitted into a preprocessed source.
544    pub fn macro_expansions(
545        &self,
546        id: PreparedSourceId,
547    ) -> Option<&Registry<MacroExpansionId, MacroExpansion>> {
548        self.prepared
549            .get(id.index())
550            .map(|source| &source.macro_expansions)
551    }
552
553    /// Returns macro definitions seen during preprocessing.
554    pub fn macro_definitions(
555        &self,
556        id: PreparedSourceId,
557    ) -> Option<&Registry<MacroDefinitionId, MacroDefinition>> {
558        self.prepared
559            .get(id.index())
560            .map(|source| &source.macro_definitions)
561    }
562
563    /// Returns physical-line reconstruction metadata for a preprocessed source.
564    pub fn format_lines(&self, id: PreparedSourceId) -> Option<&[FormatLine]> {
565        self.prepared
566            .get(id.index())
567            .map(|source| source.format_lines.as_slice())
568    }
569
570    /// Formats one physical source file from preprocessing metadata.
571    ///
572    /// This initial formatter is intentionally identity-only: it reconstructs
573    /// the original physical file from recorded line/chunk metadata. It never
574    /// falls back to returning the owned source text directly.
575    ///
576    /// # Errors
577    ///
578    /// Returns a [`FormatError`] if `file` has no recorded formatting metadata
579    /// — it was never preprocessed, or was skipped by an inactive `@if`.
580    pub fn format(&self, file: FileId) -> Result<String, FormatError> {
581        let Some(records) = self.prepared.iter().rev().find_map(|prepared| {
582            let records = prepared
583                .format_lines
584                .iter()
585                .filter(|line| line.file == file)
586                .collect::<Vec<_>>();
587            (!records.is_empty()).then_some(records)
588        }) else {
589            return Err(FormatError::MissingMetadata { file });
590        };
591
592        let mut by_line: BTreeMap<usize, &FormatLine> = BTreeMap::new();
593        for record in records {
594            if let Some(existing) = by_line.insert(record.line, record)
595                && existing.text != record.text
596            {
597                return Err(FormatError::IncompleteMetadata { file });
598            }
599        }
600
601        let mut formatted = String::new();
602        for (expected_line, (line, record)) in (1..).zip(by_line) {
603            if line != expected_line {
604                return Err(FormatError::IncompleteMetadata { file });
605            }
606            formatted.push_str(&record.text);
607        }
608
609        Ok(formatted)
610    }
611
612    /// Maps a preprocessed byte range back to the original source.
613    ///
614    /// # Panics
615    ///
616    /// Panics if the byte range cannot be mapped. This indicates a bug in the
617    /// preprocessor — for example a token straddling a macro expansion
618    /// boundary — rather than bad input. Use
619    /// [`Self::try_map_preprocessed_bytes`] when `None` is a legitimate
620    /// outcome.
621    pub fn map_preprocessed_bytes(
622        &self,
623        id: PreparedSourceId,
624        start_byte: usize,
625        end_byte: usize,
626    ) -> Span {
627        self.try_map_preprocessed_bytes(id, start_byte, end_byte)
628            .unwrap_or_else(|| {
629                panic!(
630                    "failed to map prepared-source bytes {start_byte}..{end_byte} back to \
631                     physical source — preprocessor produced an unmappable token boundary"
632                )
633            })
634    }
635
636    /// Maps a preprocessed byte range back to the original source, returning
637    /// `None` when the range cannot be mapped (e.g. macro expansion boundary).
638    pub fn try_map_preprocessed_bytes(
639        &self,
640        id: PreparedSourceId,
641        start_byte: usize,
642        end_byte: usize,
643    ) -> Option<Span> {
644        let prepared = self.prepared.get(id.index())?;
645        if let Some(span) = self.map_preprocessed_bytes_via_segments(prepared, start_byte, end_byte)
646        {
647            return Some(span);
648        }
649        let lsb = &prepared.line_start_bytes;
650
651        let start_li = lsb.partition_point(|&s| s <= start_byte).saturating_sub(1);
652        let end_search = if end_byte > start_byte {
653            end_byte - 1
654        } else {
655            start_byte
656        };
657        let end_li = lsb.partition_point(|&s| s <= end_search).saturating_sub(1);
658
659        let start_col = start_byte - lsb[start_li] + 1;
660        let mut end_col = end_byte - lsb[end_li] + 1;
661        if start_li == end_li && end_col == start_col {
662            end_col += 1;
663        }
664
665        let start_m = prepared.line_map.get(start_li)?;
666        let end_m = prepared.line_map.get(end_li).unwrap_or(start_m);
667
668        self.span_from_line_cols(
669            start_m.source_file,
670            (start_m.source_line, start_col),
671            (end_m.source_line, end_col),
672        )
673    }
674
675    fn map_preprocessed_bytes_via_segments(
676        &self,
677        prepared: &PreparedSource,
678        start_byte: usize,
679        end_byte: usize,
680    ) -> Option<Span> {
681        let end_search = if end_byte > start_byte {
682            end_byte - 1
683        } else {
684            start_byte
685        };
686
687        let start_segment = segment_containing(&prepared.source_map, start_byte)?;
688        let end_segment = segment_containing(&prepared.source_map, end_search)?;
689
690        if start_segment.source.file != end_segment.source.file {
691            return Some(start_segment.source);
692        }
693
694        if start_segment.generated == end_segment.generated
695            && matches!(start_segment.origin, SourceOrigin::MacroExpansion(_))
696        {
697            return Some(start_segment.source);
698        }
699
700        let source_start = mapped_source_byte(start_segment, start_byte);
701        let source_end = if end_byte > start_byte {
702            mapped_source_byte(end_segment, end_byte).max(source_start + 1)
703        } else {
704            source_start + 1
705        };
706
707        self.span(
708            start_segment.source.file,
709            BytePos(source_start),
710            BytePos(source_end),
711        )
712        .or(Some(start_segment.source))
713    }
714
715    /// Iterates over files in insertion order.
716    pub fn files(&self) -> impl Iterator<Item = (FileId, &Path, &str)> {
717        self.files
718            .iter()
719            .enumerate()
720            .map(|(idx, file)| (FileId(idx), file.path.as_path(), file.text.as_ref()))
721    }
722}
723
724/// Builds a temporary prepared-text span from Pest line/column endpoints.
725///
726/// The returned span carries zero byte offsets and must be remapped to a
727/// physical source span via [`SourceDb::map_preprocessed_span`] before
728/// crossing any public API boundary.
729pub(crate) fn prepared_span_from_line_cols(
730    file: FileId,
731    start: (usize, usize),
732    end: (usize, usize),
733) -> Span {
734    let (start_line, start_col) = start;
735    let (mut end_line, mut end_col) = end;
736
737    if (start_line, start_col) == (end_line, end_col) {
738        end_col += 1;
739    }
740
741    if end_line == 0 {
742        end_line = start_line;
743    }
744
745    Span::from_line_cols(file, (start_line, start_col), (end_line, end_col))
746}
747
748impl fmt::Display for FileId {
749    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
750        write!(f, "file#{}", self.0)
751    }
752}
753
754fn line_starts(text: &str) -> Vec<usize> {
755    let mut starts = vec![0];
756    for (idx, byte) in text.bytes().enumerate() {
757        if byte == b'\n' && idx + 1 < text.len() {
758            starts.push(idx + 1);
759        }
760    }
761    starts
762}
763
764fn line_col(source: &SourceFile, byte: usize) -> (usize, usize) {
765    let line_idx = match source.line_starts.binary_search(&byte) {
766        Ok(idx) => idx,
767        Err(idx) => idx.saturating_sub(1),
768    };
769    let line_start = source.line_starts[line_idx];
770    (line_idx + 1, byte.saturating_sub(line_start) + 1)
771}
772
773fn byte_for_line_col(source: &SourceFile, line: usize, col: usize) -> Option<usize> {
774    let line_start = *source.line_starts.get(line.checked_sub(1)?)?;
775    Some((line_start + col.saturating_sub(1)).min(source.text.len()))
776}
777
778fn mapped_source_byte(segment: &SourceMapSegment, generated_byte: usize) -> usize {
779    match segment.origin {
780        SourceOrigin::MacroExpansion(_) => segment.source.start.0,
781        SourceOrigin::Source => {
782            let generated_offset = generated_byte.saturating_sub(segment.generated.start);
783            (segment.source.start.0 + generated_offset).min(segment.source.end.0)
784        }
785    }
786}
787
788fn segment_containing(
789    segments: &[SourceMapSegment],
790    generated_byte: usize,
791) -> Option<&SourceMapSegment> {
792    let idx = segments.partition_point(|segment| segment.generated.end <= generated_byte);
793    let segment = segments.get(idx)?;
794    (segment.generated.start <= generated_byte && generated_byte < segment.generated.end)
795        .then_some(segment)
796}
797
798/// Resolves the span of the include path string within a source line.
799/// Used by the preprocessor to build include edges with accurate spans.
800fn include_path_span(
801    db: &SourceDb,
802    file: FileId,
803    line_no: usize,
804    raw: &str,
805    include: &str,
806) -> Option<Span> {
807    let line_start = db.files.get(file.index())?.line_starts[line_no - 1];
808    let start_in_line = raw.find(include)?;
809    db.span(
810        file,
811        BytePos(line_start + start_in_line),
812        BytePos(line_start + start_in_line + include.len()),
813    )
814}