elly_core/
source.rs

1//! Source locations (see `docs/done/2026-10-11_elly-ctx-chunks.md`, *Source locations*).
2//!
3//! A **document** is one input to `muon::parse`: a file, a REPL input or an
4//! `eval` source. A chunk records its documents and gives each a range of its
5//! own positions, a [`ChunkLoc`]; its code has spans in those positions, in
6//! side tables parallel to its nodes, patterns, lambdas and members. A realm
7//! gives each chunk a base in its own offset space when the chunk is added, so
8//! a [`Loc`] names a position in any of the realm's chunks, and
9//! [`Ctx::locate`] resolves it to a [`Location`] in a document.
10//!
11//! The realm keeps no source text. A line is found from the line starts a
12//! chunk records; a column is computed from the text on demand
13//! ([`Location::column`]).
14
15use alloc::boxed::Box;
16use alloc::format;
17use alloc::string::{String, ToString};
18use alloc::vec::Vec;
19
20use crate::code::{ChunkId, Id, LambdaId, ModId, NodeId, PatId, StaticChunk, Text};
21use crate::Ctx;
22
23/// A position in a realm's offset space or in a chunk's.
24pub type Pos = u32;
25/// A length in bytes.
26pub type Len = u32;
27/// A line number, 1-based.
28pub type Line = u32;
29
30/// A position in a realm's offset space, which concatenates the documents of
31/// its chunks in the order the chunks were added.
32#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
33pub struct Loc(Pos);
34
35/// A position relative to a chunk: an offset into the concatenation of its
36/// documents. A chunk is built with no realm's offsets; adding the base its
37/// realm gives it (see [`Ctx::chunk_bases`]) is the one way to a [`Loc`].
38#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
39pub struct ChunkLoc(Pos);
40
41macro_rules! loc {
42    ($name:ident) => {
43        impl $name {
44            /// No location: code the implementation made rather than parsed.
45            pub const NONE: Self = Self(Pos::MAX);
46
47            /// The location, or `None` for [`NONE`](Self::NONE).
48            pub fn get(self) -> Option<Self> {
49                (self != Self::NONE).then_some(self)
50            }
51        }
52    };
53}
54
55loc!(Loc);
56loc!(ChunkLoc);
57
58/// `len` bytes from a [`Loc`].
59#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
60pub struct CtxSpan(pub Loc, pub Len);
61
62/// `len` bytes from a [`ChunkLoc`].
63#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
64pub struct ChunkSpan(pub ChunkLoc, pub Len);
65
66impl ChunkSpan {
67    /// No span: code the implementation made rather than parsed.
68    pub const NONE: Self = ChunkSpan(ChunkLoc::NONE, 0);
69
70    pub(crate) fn new(at: Pos, len: Len) -> Self {
71        ChunkSpan(ChunkLoc(at), len)
72    }
73
74    /// The span, or `None` for [`NONE`](Self::NONE).
75    pub fn get(self) -> Option<Self> {
76        self.0.get().map(|_| self)
77    }
78
79    /// The span relative to a document that starts at `start`, or `None` for
80    /// [`NONE`](Self::NONE).
81    pub(crate) fn in_doc(self, start: Pos) -> Option<muon::Span> {
82        let ChunkSpan(at, length) = self.get()?;
83        Some(muon::Span {
84            offset: at.0 - start,
85            length,
86        })
87    }
88
89    /// The position just past the span.
90    /// Whether `other` lies within this span.
91    pub(crate) fn contains(self, other: ChunkSpan) -> bool {
92        self.0 .0 <= other.0 .0 && other.end() <= self.end()
93    }
94
95    fn end(self) -> Pos {
96        self.0 .0 + self.1
97    }
98
99    /// The smallest span covering both; a missing span covers nothing.
100    pub(crate) fn join(self, other: ChunkSpan) -> ChunkSpan {
101        if self.get().is_none() {
102            return other;
103        }
104        if other.get().is_none() {
105            return self;
106        }
107        let at = self.0 .0.min(other.0 .0);
108        ChunkSpan(ChunkLoc(at), self.end().max(other.end()) - at)
109    }
110}
111
112/// Where a document came from. The realm keeps no source text, so this is
113/// what finds the text again.
114#[derive(Debug, Clone, PartialEq, Eq)]
115pub enum DocSource {
116    /// A file, read again on demand.
117    Path(Text),
118    /// An opaque back-reference from the embedder, which stores the text: a
119    /// REPL input, a notebook cell.
120    Embedder(u64),
121    /// A source given with nothing to point back to. Numbered from the realm's
122    /// made names, so the document of chunk `__eval_3` is `Anonymous(3)`.
123    Anonymous(u32),
124}
125
126/// A document of a chunk: its source, and where its text and lines lie
127/// among the chunk's.
128#[derive(Debug, Clone, PartialEq, Eq)]
129pub struct Doc {
130    source: DocSource,
131    start: Pos,
132    len: Len,
133    /// Its range in the chunk's line starts.
134    first_line: u32,
135    lines: u32,
136}
137
138impl Doc {
139    pub fn source(&self) -> &DocSource {
140        &self.source
141    }
142
143    /// The length of the document's text in bytes.
144    pub fn len(&self) -> Len {
145        self.len
146    }
147
148    pub fn is_empty(&self) -> bool {
149        self.len == 0
150    }
151
152    fn end(&self) -> Pos {
153        self.start + self.len
154    }
155}
156
157/// A [`Loc`] resolved: the document it falls in, and its line there.
158#[derive(Debug, Clone, Copy, PartialEq, Eq)]
159pub struct Location {
160    pub chunk: ChunkId,
161    /// The document's index among the chunk's [`documents`](StaticChunk::documents).
162    pub doc: u32,
163    /// The byte offset in the document.
164    pub pos: Pos,
165    pub line_num: Line,
166    /// The byte offset in the document where the line starts.
167    pub line_start: Pos,
168}
169
170impl Location {
171    /// The 1-based column in `text`, the document's text, counted in code
172    /// points; a tab is one column. `None` if `text` is not long enough or
173    /// the location is not on a character boundary, as when the document
174    /// changed since it was parsed.
175    pub fn column(&self, text: &str) -> Option<u32> {
176        let line = text.get(self.line_start as usize..self.pos as usize)?;
177        Some(line.chars().count() as u32 + 1)
178    }
179}
180
181/// Reports `message` at `span` of the document `name`, whose text is `text`:
182/// a `name:line:column: message` line, then the span's first line with the
183/// span underlined to that line's end. Columns count code points, a tab as
184/// one, as [`Location::column`] does. A span past the text's end is put at
185/// its end.
186pub fn report(name: &str, text: &str, span: muon::Span, message: &str) -> String {
187    let mut at = (span.offset as usize).min(text.len());
188    while !text.is_char_boundary(at) {
189        at -= 1;
190    }
191    let start = text[..at].rfind('\n').map_or(0, |i| i + 1);
192    let end = text[at..].find('\n').map_or(text.len(), |i| at + i);
193    let line = text[start..end].trim_end_matches('\r');
194    let line_num = text[..start].matches('\n').count() + 1;
195    let before = &text[start..at];
196    let column = before.chars().count() + 1;
197    // Keep the line's tabs in the indent, so the marks line up however the
198    // tabs are shown.
199    let indent: String = before
200        .chars()
201        .map(|c| if c == '\t' { '\t' } else { ' ' })
202        .collect();
203    let under = (at + span.length as usize).min(start + line.len()).max(at);
204    let marks = "^".repeat(text[at..under].chars().count().max(1));
205    let gutter = " ".repeat(line_num.to_string().len());
206    format!(
207        "{name}:{line_num}:{column}: {message}\n {line_num} | {line}\n {gutter} | {indent}{marks}"
208    )
209}
210
211// ---------------------------------------------------------------------------
212// A chunk's documents
213// ---------------------------------------------------------------------------
214
215/// A chunk's source locations: the spans of its nodes, patterns, lambdas and
216/// members, each parallel to its table, and the documents they point into.
217/// A chunk keeps them out of line, as only errors and tools read them, so
218/// that they do not widen the chunk entry every code read goes through.
219#[derive(Debug)]
220pub(crate) struct ChunkLocs {
221    pub(crate) node_spans: Box<[ChunkSpan]>,
222    pub(crate) pat_spans: Box<[ChunkSpan]>,
223    pub(crate) lambda_spans: Box<[ChunkSpan]>,
224    pub(crate) member_spans: Box<[ChunkSpan]>,
225    pub(crate) docs: Box<[Doc]>,
226    /// The position of every line's start, each document's first included.
227    pub(crate) line_starts: Box<[Pos]>,
228    /// The chunk's base in its realm's offset space, given when the realm
229    /// adds it; the code built carries none.
230    pub(crate) base: Loc,
231}
232
233/// The documents of a chunk being built, and the starts of their lines.
234#[derive(Debug, Default)]
235pub(crate) struct DocsBuilder {
236    /// The documents; a `None` source is anonymous, numbered when the chunk
237    /// is named.
238    docs: Vec<(Option<DocSource>, Pos, Len, u32, u32)>,
239    line_starts: Vec<Pos>,
240}
241
242impl DocsBuilder {
243    /// Records the document `text` from `source`, `None` for an anonymous
244    /// one, and returns its first position in the chunk. Each document starts
245    /// one past the end of the last, so that a position at a document's end
246    /// is in no other document.
247    pub(crate) fn add(&mut self, source: Option<DocSource>, text: &str) -> Pos {
248        let start = match self.docs.last() {
249            Some(&(_, start, len, _, _)) => start + len + 1,
250            None => 0,
251        };
252        let len = Len::try_from(text.len()).expect("a document outgrew u32");
253        start
254            .checked_add(len)
255            .expect("a chunk's documents outgrew u32");
256        let first_line = crate::code::len32(self.line_starts.len());
257        self.line_starts.push(start);
258        for (i, b) in text.bytes().enumerate() {
259            if b == b'\n' {
260                self.line_starts.push(start + i as Pos + 1);
261            }
262        }
263        let lines = crate::code::len32(self.line_starts.len()) - first_line;
264        self.docs.push((source, start, len, first_line, lines));
265        start
266    }
267
268    /// Whether a document is anonymous, and so needs a made number.
269    pub(crate) fn has_anonymous(&self) -> bool {
270        self.docs.iter().any(|d| d.0.is_none())
271    }
272
273    /// The documents, an anonymous one numbered `made`, and the line starts.
274    pub(crate) fn finish(self, made: Option<u32>) -> (Box<[Doc]>, Box<[Pos]>) {
275        let docs = self
276            .docs
277            .into_iter()
278            .map(|(source, start, len, first_line, lines)| Doc {
279                source: source.unwrap_or_else(|| {
280                    DocSource::Anonymous(made.expect("an anonymous document has a number"))
281                }),
282                start,
283                len,
284                first_line,
285                lines,
286            })
287            .collect();
288        (docs, self.line_starts.into_boxed_slice())
289    }
290}
291
292impl StaticChunk {
293    /// The documents this chunk was parsed from, in order. The prelude chunk
294    /// has none.
295    pub fn documents(&self) -> &[Doc] {
296        &self.locs.docs
297    }
298
299    /// How many positions the chunk takes in its realm's offset space: its
300    /// documents and one past them, or none without documents.
301    pub(crate) fn extent(&self) -> Pos {
302        self.locs.docs.last().map_or(0, |doc| doc.end() + 1)
303    }
304
305    /// Chunk position `at` resolved to its document's index, its position in
306    /// the document, its line number and where the line starts.
307    pub(crate) fn locate(&self, at: ChunkLoc) -> Option<(u32, Pos, Line, Pos)> {
308        let at = at.get()?.0;
309        let i = self.locs.docs.partition_point(|doc| doc.end() < at);
310        let doc = self.locs.docs.get(i)?;
311        if at < doc.start {
312            return None;
313        }
314        let first = doc.first_line as usize;
315        let starts = &self.locs.line_starts[first..first + doc.lines as usize];
316        // A document's start is its first line's, so at least one start is
317        // not past `at`.
318        let line = starts.partition_point(|&s| s <= at) - 1;
319        Some((
320            i as u32,
321            at - doc.start,
322            line as Line + 1,
323            starts[line] - doc.start,
324        ))
325    }
326
327    /// The ids of the chunk's nodes, in table order, debug barriers included.
328    pub fn node_ids(&self) -> impl Iterator<Item = NodeId> {
329        (0..self.locs.node_spans.len()).map(NodeId::at)
330    }
331
332    /// The ids of the chunk's patterns, as [`node_ids`](Self::node_ids).
333    pub fn pat_ids(&self) -> impl Iterator<Item = PatId> {
334        (0..self.locs.pat_spans.len()).map(PatId::at)
335    }
336
337    /// The ids of the chunk's lambdas, in table order.
338    pub fn lambda_ids(&self) -> impl Iterator<Item = LambdaId> {
339        (0..self.locs.lambda_spans.len()).map(LambdaId::at)
340    }
341
342    /// The span of node `id`, if it was parsed.
343    pub fn node_span(&self, id: NodeId) -> Option<ChunkSpan> {
344        self.locs.node_spans[id.index()].get()
345    }
346
347    /// The span of pattern `id`, if it was parsed.
348    pub fn pat_span(&self, id: PatId) -> Option<ChunkSpan> {
349        self.locs.pat_spans[id.index()].get()
350    }
351
352    /// The span of lambda `id`: its whole `&`, with the parameters.
353    pub fn lambda_span(&self, id: LambdaId) -> Option<ChunkSpan> {
354        self.locs.lambda_spans[id.index()].get()
355    }
356
357    /// The span of member `index` of module `m`, counted over its items,
358    /// locals and iotas: a declaration's `name = body`, or an iota's name.
359    pub fn member_span(&self, m: ModId, index: u32) -> Option<ChunkSpan> {
360        let members = self.module(m).members;
361        if index >= members.len {
362            return None;
363        }
364        self.locs.member_spans[members.first.index() + index as usize].get()
365    }
366}
367
368// ---------------------------------------------------------------------------
369// The realm's offset space
370// ---------------------------------------------------------------------------
371
372impl Ctx {
373    /// Each chunk's base in the realm's offset space, in chunk order. Bases
374    /// do not decrease; a chunk with no documents shares its base with the
375    /// next.
376    pub fn chunk_bases(&self) -> Vec<Loc> {
377        self.chunks.borrow().iter().map(|c| c.locs.base).collect()
378    }
379
380    /// The base of the next chunk to be added.
381    pub(crate) fn next_base(&self) -> Loc {
382        match self.chunks.borrow().last() {
383            Some(last) => Loc(last.locs.base.0 + last.extent()),
384            None => Loc(0),
385        }
386    }
387
388    /// Chunk `chunk`'s span `span` in the realm's offset space.
389    pub fn ctx_span(&self, chunk: ChunkId, span: ChunkSpan) -> Option<CtxSpan> {
390        let span = span.get()?;
391        let base = self.chunk(chunk).locs.base;
392        Some(CtxSpan(Loc(base.0 + span.0 .0), span.1))
393    }
394
395    /// The span of node `id` of chunk `chunk`, if it was parsed.
396    pub fn node_span(&self, chunk: ChunkId, id: NodeId) -> Option<CtxSpan> {
397        let span = self.chunk(chunk).node_span(id)?;
398        self.ctx_span(chunk, span)
399    }
400
401    /// The span of pattern `id` of chunk `chunk`, if it was parsed.
402    pub fn pat_span(&self, chunk: ChunkId, id: PatId) -> Option<CtxSpan> {
403        let span = self.chunk(chunk).pat_span(id)?;
404        self.ctx_span(chunk, span)
405    }
406
407    /// The span of lambda `id` of chunk `chunk`, if it was parsed.
408    pub fn lambda_span(&self, chunk: ChunkId, id: LambdaId) -> Option<CtxSpan> {
409        let span = self.chunk(chunk).lambda_span(id)?;
410        self.ctx_span(chunk, span)
411    }
412
413    /// The span of member `index` of module `m` of chunk `chunk`, if it was
414    /// parsed (see [`StaticChunk::member_span`]).
415    pub fn member_span(&self, chunk: ChunkId, m: ModId, index: u32) -> Option<CtxSpan> {
416        let span = self.chunk(chunk).member_span(m, index)?;
417        self.ctx_span(chunk, span)
418    }
419
420    /// `at` resolved to a document and a line: the chunk is found by its
421    /// base, the document and the line by the chunk's tables. `None` for
422    /// [`Loc::NONE`] or a position in no document.
423    pub fn locate(&self, at: Loc) -> Option<Location> {
424        let at = at.get()?;
425        let chunks = self.chunks.borrow();
426        let mut i = chunks.partition_point(|chunk| chunk.locs.base <= at);
427        // Skip the chunks without documents that share the base of `at`'s.
428        while i > 0 {
429            i -= 1;
430            let chunk = &chunks[i];
431            if chunk.locs.docs.is_empty() {
432                continue;
433            }
434            let (doc, pos, line_num, line_start) =
435                chunk.locate(ChunkLoc(at.0 - chunk.locs.base.0))?;
436            return Some(Location {
437                chunk: ChunkId::at(i),
438                doc,
439                pos,
440                line_num,
441                line_start,
442            });
443        }
444        None
445    }
446}
elly_core/source.rs

elly_core/
source.rs
