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

submilli_engine/
span.rs
