submilli_engine/
span.rs

1use crate::source::SourceError;
2use serde::{Deserialize, Serialize};
3
4/// Index into a [`Sources`](crate::Sources) registry, identifying the file a
5/// [`Span`] points at.
6///
7/// User/script modules occupy the low ids (the registry stores their text).
8/// The prelude and each stdlib package own a fixed *reserved* id near
9/// `u32::MAX`; these have no source text and are not stored in the registry —
10/// the diagnostic renderer maps them to a virtual path via [`reserved_path`].
11///
12/// [`reserved_path`]: FileId::reserved_path
13#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
14pub struct FileId(pub u32);
15
16impl FileId {
17    pub const FIRST_RESERVED: u32 = u32::MAX - 25;
18    pub const COMPILER: FileId = FileId(Self::FIRST_RESERVED);
19
20    pub const PRELUDE: FileId = FileId(u32::MAX);
21    pub const FS: FileId = FileId(u32::MAX - 1);
22    pub const HTTP: FileId = FileId(u32::MAX - 2);
23    pub const URL: FileId = FileId(u32::MAX - 3);
24    pub const UUID: FileId = FileId(u32::MAX - 4);
25    pub const CRYPTO: FileId = FileId(u32::MAX - 5);
26    pub const SECURITY: FileId = FileId(u32::MAX - 6);
27    pub const MATH: FileId = FileId(u32::MAX - 7);
28    pub const JSON: FileId = FileId(u32::MAX - 8);
29    pub const TEMPORAL: FileId = FileId(u32::MAX - 9);
30    pub const MCP: FileId = FileId(u32::MAX - 10);
31    pub const NUMBER: FileId = FileId(u32::MAX - 11);
32    pub const STRING: FileId = FileId(u32::MAX - 12);
33    pub const REGEX: FileId = FileId(u32::MAX - 13);
34    pub const URI: FileId = FileId(u32::MAX - 14);
35    pub const SECRETS: FileId = FileId(u32::MAX - 15);
36    pub const TEST: FileId = FileId(u32::MAX - 16);
37    pub const SESSION: FileId = FileId(u32::MAX - 17);
38    pub const LLM: FileId = FileId(u32::MAX - 18);
39    pub const EMBEDDING: FileId = FileId(u32::MAX - 21);
40    pub const CODE: FileId = FileId(u32::MAX - 20);
41    pub const GIT: FileId = FileId(u32::MAX - 19);
42    pub const AGENTS: FileId = FileId(u32::MAX - 22);
43    pub const VARIABLES: FileId = FileId(u32::MAX - 24);
44    pub const SKILLS: FileId = FileId(u32::MAX - 23);
45
46    /// Virtual display path for a reserved (prelude/stdlib) id, e.g.
47    /// `submilli:fs`. Returns `None` for ordinary user/script files, which
48    /// instead resolve to a [`SourceFile`](crate::SourceFile) in the registry.
49    pub fn reserved_path(self) -> Option<&'static str> {
50        Some(match self {
51            FileId::COMPILER => "<compiler>",
52            FileId::PRELUDE => "<prelude>",
53            FileId::CODE => "submilli:code",
54            FileId::EMBEDDING => "submilli:embedding",
55            FileId::GIT => "submilli:git",
56            FileId::FS => "submilli:fs",
57            FileId::HTTP => "submilli:http",
58            FileId::URL => "submilli:url",
59            FileId::URI => "submilli:uri",
60            FileId::UUID => "submilli:uuid",
61            FileId::CRYPTO => "submilli:crypto",
62            FileId::SECURITY => "submilli:security",
63            FileId::MATH => "submilli:math",
64            FileId::JSON => "submilli:json",
65            FileId::TEMPORAL => "submilli:temporal",
66            FileId::MCP => "submilli:mcp",
67            FileId::NUMBER => "submilli:number",
68            FileId::STRING => "submilli:string",
69            FileId::REGEX => "submilli:regex",
70            FileId::VARIABLES => "submilli:variables",
71            FileId::SECRETS => "submilli:secrets",
72            FileId::SESSION => "submilli:session",
73            FileId::LLM => "submilli:llm",
74            FileId::AGENTS => "submilli:agents",
75            FileId::SKILLS => "submilli:skills",
76            FileId::TEST => "submilli:test",
77            _ => return None,
78        })
79    }
80}
81
82#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
83pub struct Span {
84    pub file: FileId,
85    pub start: u32,
86    pub end: u32,
87}
88
89impl Span {
90    pub const fn new(file: FileId, start: u32, end: u32) -> Result<Self, SourceError> {
91        let span = Self { file, start, end };
92        if start > end {
93            return Err(SourceError::InvalidSpan {
94                span,
95                reason: "start exceeds end",
96            });
97        }
98        Ok(span)
99    }
100
101    pub fn text(self, source: &str, file: FileId) -> Result<&str, SourceError> {
102        if self.file != file {
103            return Err(SourceError::InvalidSpan {
104                span: self,
105                reason: "span belongs to another file",
106            });
107        }
108        source
109            .get(self.start as usize..self.end as usize)
110            .ok_or(SourceError::InvalidSpan {
111                span: self,
112                reason: "range is outside source or splits a UTF-8 character",
113            })
114    }
115
116    /// A zero-length placeholder anchored to `file` — for definitions and
117    /// generated nodes that have a logical home file but no source range
118    /// (prelude/stdlib declarations, desugared temporaries). The home is always
119    /// named explicitly: a reserved id for prelude/stdlib, the script's id for
120    /// compiler-generated user-code nodes.
121    pub const fn at(file: FileId) -> Self {
122        Self {
123            file,
124            start: 0,
125            end: 0,
126        }
127    }
128
129    /// This span cut to its first line of `text`, its file's source; unchanged
130    /// when it is not a range of `text`. A line ends at `\n` or `\r`, as in
131    /// [`LineIndex`].
132    pub fn first_line_of(self, text: &str) -> Self {
133        let first_line_len = text
134            .get(self.start as usize..self.end as usize)
135            .and_then(|range| range.find(['\n', '\r']))
136            .and_then(|len| u32::try_from(len).ok());
137        match first_line_len.and_then(|len| self.start.checked_add(len)) {
138            Some(end) => Self { end, ..self },
139            None => self,
140        }
141    }
142
143    /// Whether this is a [`Self::at`] placeholder, which locates nothing.
144    pub const fn is_placeholder(self) -> bool {
145        self.start == 0 && self.end == 0
146    }
147
148    pub fn merge(self, other: Self) -> Result<Self, SourceError> {
149        Self::new(self.file, self.start, self.end)?;
150        Self::new(other.file, other.start, other.end)?;
151        if self.file != other.file {
152            return Err(SourceError::InvalidSpan {
153                span: other,
154                reason: "cannot merge spans from different files",
155            });
156        }
157        Self::new(
158            self.file,
159            self.start.min(other.start),
160            self.end.max(other.end),
161        )
162    }
163
164    pub fn contains(self, offset: u32) -> bool {
165        self.start <= offset && offset < self.end
166    }
167
168    /// Whether `inner` lies wholly within this span, in the same file.
169    pub fn encloses(self, inner: Span) -> bool {
170        self.file == inner.file && self.start <= inner.start && inner.end <= self.end
171    }
172}
173
174/// Owns the text as well as its index, so line access cannot use unrelated text.
175#[derive(Clone, Debug)]
176pub struct LineIndex {
177    source: String,
178    line_starts: Vec<u32>,
179}
180
181impl LineIndex {
182    pub fn new(source: &str) -> Result<Self, SourceError> {
183        SourceError::check_source_len(source.len())?;
184        let mut text = String::new();
185        text.try_reserve(source.len())
186            .map_err(SourceError::Allocation)?;
187        text.push_str(source);
188        Self::from_owned(text)
189    }
190
191    pub(crate) fn from_owned(source: String) -> Result<Self, SourceError> {
192        SourceError::check_source_len(source.len())?;
193        let mut line_starts = Vec::new();
194        line_starts
195            .try_reserve(1)
196            .map_err(SourceError::Allocation)?;
197        line_starts.push(0);
198        let mut bytes = source.bytes().enumerate().peekable();
199        while let Some((offset, byte)) = bytes.next() {
200            let end = match byte {
201                b'\n' => offset + 1,
202                b'\r' => match bytes.peek() {
203                    Some((_, b'\n')) => {
204                        bytes.next();
205                        offset + 2
206                    }
207                    _ => offset + 1,
208                },
209                _ => continue,
210            };
211            let end =
212                u32::try_from(end).map_err(|_| SourceError::SourceLimit { len: source.len() })?;
213            line_starts
214                .try_reserve(1)
215                .map_err(SourceError::Allocation)?;
216            line_starts.push(end);
217        }
218        Ok(Self {
219            source,
220            line_starts,
221        })
222    }
223
224    pub fn source(&self) -> &str {
225        &self.source
226    }
227
228    pub fn line_col(&self, offset: u32) -> Result<(u32, u32), SourceError> {
229        if !self.source.is_char_boundary(offset as usize) {
230            return Err(SourceError::InvalidOffset { offset });
231        }
232        let count = self.line_starts.partition_point(|&start| start <= offset);
233        let start = count
234            .checked_sub(1)
235            .and_then(|i| self.line_starts.get(i))
236            .ok_or(SourceError::InvalidOffset { offset })?;
237        let line = u32::try_from(count).map_err(|_| SourceError::SourceLimit {
238            len: self.source.len(),
239        })?;
240        let column = offset
241            .checked_sub(*start)
242            .and_then(|n| n.checked_add(1))
243            .ok_or(SourceError::InvalidOffset { offset })?;
244        Ok((line, column))
245    }
246
247    pub fn line_count(&self) -> u32 {
248        // Source length is bounded below u32::MAX; each line consumes a byte.
249        self.line_starts.len() as u32
250    }
251
252    pub fn byte_offset(&self, line: u32, col: u32) -> Result<u32, SourceError> {
253        let error = || SourceError::InvalidPosition { line, col };
254        let start = line
255            .checked_sub(1)
256            .and_then(|i| self.line_starts.get(i as usize))
257            .ok_or_else(error)?;
258        let offset = col
259            .checked_sub(1)
260            .and_then(|n| start.checked_add(n))
261            .ok_or_else(error)?;
262        let (actual_line, _) = self.line_col(offset).map_err(|_| error())?;
263        if actual_line != line {
264            return Err(error());
265        }
266        Ok(offset)
267    }
268
269    pub fn line_text(&self, line: u32) -> Result<&str, SourceError> {
270        let start = line
271            .checked_sub(1)
272            .and_then(|i| self.line_starts.get(i as usize))
273            .ok_or(SourceError::InvalidPosition { line, col: 1 })?;
274        let end = self
275            .line_starts
276            .get(line as usize)
277            .map_or(self.source.len(), |n| *n as usize);
278        self.source
279            .get(*start as usize..end)
280            .map(|text| text.trim_end_matches(['\n', '\r']))
281            .ok_or(SourceError::InvalidPosition { line, col: 1 })
282    }
283}
284
285#[cfg(test)]
286mod tests {
287    use super::{FileId, LineIndex, Span};
288
289    #[test]
290    fn first_line_of_ends_at_either_line_break() {
291        let text = "héllo\r\nworld\rmore\nend";
292        let span = |start, end| Span::new(FileId(0), start, end).unwrap();
293        assert_eq!(span(0, 20).first_line_of(text), span(0, 6));
294        assert_eq!(span(8, 20).first_line_of(text), span(8, 13));
295        assert_eq!(span(14, 20).first_line_of(text), span(14, 18));
296        assert_eq!(span(19, 22).first_line_of(text), span(19, 22));
297        // Not a range of `text`: left as is.
298        assert_eq!(span(2, 20).first_line_of(text), span(2, 20));
299        assert_eq!(span(0, 99).first_line_of(text), span(0, 99));
300    }
301
302    const F: FileId = FileId(0);
303
304    #[test]
305    fn new_stores_fields() {
306        let s = Span::new(F, 3, 7).unwrap();
307        assert_eq!(s.start, 3);
308        assert_eq!(s.end, 7);
309    }
310
311    #[test]
312    fn new_allows_empty_span() {
313        let s = Span::new(F, 5, 5).unwrap();
314        assert_eq!(s.start, 5);
315        assert_eq!(s.end, 5);
316    }
317
318    #[test]
319    fn merge_overlapping() {
320        assert_eq!(
321            Span::new(F, 0, 5)
322                .unwrap()
323                .merge(Span::new(F, 3, 8).unwrap())
324                .unwrap(),
325            Span::new(F, 0, 8).unwrap()
326        );
327    }
328
329    #[test]
330    fn merge_disjoint_covers_gap() {
331        assert_eq!(
332            Span::new(F, 0, 2)
333                .unwrap()
334                .merge(Span::new(F, 5, 7).unwrap())
335                .unwrap(),
336            Span::new(F, 0, 7).unwrap()
337        );
338    }
339
340    #[test]
341    fn merge_identical() {
342        let s = Span::new(F, 4, 9).unwrap();
343        assert_eq!(s.merge(s).unwrap(), s);
344    }
345
346    #[test]
347    fn merge_nested_returns_outer() {
348        let outer = Span::new(F, 0, 10).unwrap();
349        let inner = Span::new(F, 3, 5).unwrap();
350        assert_eq!(outer.merge(inner).unwrap(), outer);
351        assert_eq!(inner.merge(outer).unwrap(), outer);
352    }
353
354    #[test]
355    fn merge_is_commutative() {
356        let a = Span::new(F, 2, 6).unwrap();
357        let b = Span::new(F, 4, 10).unwrap();
358        assert_eq!(a.merge(b).unwrap(), b.merge(a).unwrap());
359    }
360
361    #[test]
362    fn encloses_a_span_inside_and_itself() {
363        let outer = Span::new(F, 3, 7).unwrap();
364        assert!(outer.encloses(Span::new(F, 4, 7).unwrap()));
365        assert!(outer.encloses(outer));
366        assert!(!outer.encloses(Span::new(F, 2, 5).unwrap()));
367    }
368
369    #[test]
370    fn contains_start_is_inclusive() {
371        assert!(Span::new(F, 3, 7).unwrap().contains(3));
372    }
373
374    #[test]
375    fn contains_end_is_exclusive() {
376        assert!(!Span::new(F, 3, 7).unwrap().contains(7));
377    }
378
379    #[test]
380    fn contains_strictly_inside() {
381        assert!(Span::new(F, 3, 7).unwrap().contains(5));
382    }
383
384    #[test]
385    fn contains_before_start() {
386        assert!(!Span::new(F, 3, 7).unwrap().contains(2));
387    }
388
389    #[test]
390    fn contains_after_end() {
391        assert!(!Span::new(F, 3, 7).unwrap().contains(8));
392    }
393
394    #[test]
395    fn empty_span_contains_nothing() {
396        let s = Span::new(F, 4, 4).unwrap();
397        assert!(!s.contains(3));
398        assert!(!s.contains(4));
399        assert!(!s.contains(5));
400    }
401
402    #[test]
403    fn line_index_empty_file() {
404        let idx = LineIndex::new("").unwrap();
405        assert_eq!(idx.line_col(0).unwrap(), (1, 1));
406        assert_eq!(idx.line_count(), 1);
407    }
408
409    #[test]
410    fn line_index_single_line_no_terminator() {
411        let idx = LineIndex::new("hello").unwrap();
412        assert_eq!(idx.line_col(0).unwrap(), (1, 1));
413        assert_eq!(idx.line_col(1).unwrap(), (1, 2));
414        assert_eq!(idx.line_col(5).unwrap(), (1, 6));
415        assert_eq!(idx.line_count(), 1);
416    }
417
418    #[test]
419    fn line_index_multi_line_lf() {
420        let src = "abc\ndef\nghi";
421        let idx = LineIndex::new(src).unwrap();
422        assert_eq!(idx.line_col(0).unwrap(), (1, 1));
423        assert_eq!(idx.line_col(2).unwrap(), (1, 3));
424        assert_eq!(idx.line_col(3).unwrap(), (1, 4)); // \n counts as last col of line 1
425        assert_eq!(idx.line_col(4).unwrap(), (2, 1));
426        assert_eq!(idx.line_col(7).unwrap(), (2, 4));
427        assert_eq!(idx.line_col(8).unwrap(), (3, 1));
428        assert_eq!(idx.line_col(10).unwrap(), (3, 3));
429        assert_eq!(idx.line_count(), 3);
430    }
431
432    #[test]
433    fn line_index_crlf() {
434        let src = "abc\r\ndef";
435        let idx = LineIndex::new(src).unwrap();
436        assert_eq!(idx.line_col(0).unwrap(), (1, 1));
437        assert_eq!(idx.line_col(4).unwrap(), (1, 5));
438        assert_eq!(idx.line_col(5).unwrap(), (2, 1));
439        assert_eq!(idx.line_count(), 2);
440    }
441
442    #[test]
443    fn line_index_bare_cr() {
444        let src = "abc\rdef";
445        let idx = LineIndex::new(src).unwrap();
446        assert_eq!(idx.line_col(0).unwrap(), (1, 1));
447        assert_eq!(idx.line_col(4).unwrap(), (2, 1));
448        assert_eq!(idx.line_count(), 2);
449    }
450
451    #[test]
452    fn line_index_trailing_newline() {
453        let src = "abc\n";
454        let idx = LineIndex::new(src).unwrap();
455        assert_eq!(idx.line_col(0).unwrap(), (1, 1));
456        assert_eq!(idx.line_col(3).unwrap(), (1, 4));
457        assert_eq!(idx.line_col(4).unwrap(), (2, 1)); // EOF = start of empty line 2
458        assert_eq!(idx.line_count(), 2);
459    }
460
461    #[test]
462    fn line_index_unicode() {
463        // α, β, γ are each 2 UTF-8 bytes.
464        let src = "αβ\nγ";
465        assert_eq!(src.len(), 7);
466        let idx = LineIndex::new(src).unwrap();
467        assert_eq!(idx.line_col(0).unwrap(), (1, 1));
468        assert_eq!(idx.line_col(2).unwrap(), (1, 3));
469        assert!(idx.line_col(3).is_err()); // middle of a UTF-8 character
470        assert_eq!(idx.line_col(4).unwrap(), (1, 5));
471        assert_eq!(idx.line_col(5).unwrap(), (2, 1));
472        assert!(idx.line_col(6).is_err());
473    }
474
475    #[test]
476    fn line_index_rejects_past_eof() {
477        let idx = LineIndex::new("abc").unwrap();
478        assert!(idx.line_col(100).is_err());
479    }
480
481    #[test]
482    fn line_index_rejects_past_eof_with_trailing_newline() {
483        let idx = LineIndex::new("abc\n").unwrap();
484        assert!(idx.line_col(999).is_err());
485    }
486
487    #[test]
488    fn line_text_strips_terminators_and_clamps() {
489        let src = "first\nsecond\r\nthird";
490        let idx = LineIndex::new(src).unwrap();
491        assert_eq!(idx.line_text(1).unwrap(), "first");
492        assert_eq!(idx.line_text(2).unwrap(), "second");
493        assert_eq!(idx.line_text(3).unwrap(), "third");
494        assert!(idx.line_text(0).is_err());
495        assert!(idx.line_text(99).is_err());
496        // Trailing-newline: a final empty line exists at index line_count.
497        let src2 = "a\n";
498        let idx2 = LineIndex::new(src2).unwrap();
499        assert_eq!(idx2.line_text(1).unwrap(), "a");
500        assert_eq!(idx2.line_text(2).unwrap(), "");
501    }
502}
submilli_engine/span.rs

submilli_engine/
span.rs
