lang_forge/language.rs
1//! [`Language`]: a language forged from a schematic.
2
3use alloc::{boxed::Box, format, vec::Vec};
4use core::str::FromStr;
5
6use diag_lang::{Diagnostic, Label, Severity};
7use pass_lang::{Outcome, Pass, PassError, PassManager};
8use syntax_lang::{Span, Token};
9
10use crate::{
11 Error, Parse,
12 error::Report,
13 grammar::{self, Grammar},
14 kind::Kind,
15 noml, parser, schematic,
16};
17
18/// A capability pass, boxed for [`Language::pipeline`].
19///
20/// A capability is a [`pass_lang::Pass`] over a [`Parse`], named by its
21/// [`Pass::name`]. Implement the pass for every lifetime —
22/// `impl<'a> Pass<Parse<'a>> for MyPass` — and box it as a `Capability`; the
23/// language then runs it whenever its schematic includes that name.
24///
25/// # Examples
26///
27/// ```
28/// use lang_forge::pass_lang::{Outcome, Pass, PassError};
29/// use lang_forge::{Capability, Parse};
30///
31/// struct CountNodes(usize);
32///
33/// impl<'a> Pass<Parse<'a>> for CountNodes {
34/// fn name(&self) -> &'static str {
35/// "count-nodes"
36/// }
37///
38/// fn run(&mut self, parse: &mut Parse<'a>) -> Result<Outcome, PassError> {
39/// self.0 = parse.tree().descendants().count();
40/// Ok(Outcome::Unchanged)
41/// }
42/// }
43///
44/// let capability: Capability = Box::new(CountNodes(0));
45/// assert_eq!(capability.name(), "count-nodes");
46/// ```
47pub type Capability = Box<dyn for<'a> Pass<Parse<'a>>>;
48
49/// A language forged from a `.lsf` schematic: a lexer, a parser, and the kinds
50/// of its syntax tree.
51///
52/// Forge one with [`Language::from_lsf`] (or `str::parse`), then call
53/// [`parse`](Self::parse) as often as needed. Forging does all the analysis
54/// up front — every rule resolved, every set computed, every conflict
55/// refused — so parsing is a walk over precomputed tables that never fails and
56/// never panics: malformed input yields a complete tree plus diagnostics.
57///
58/// A `Language` is immutable once forged. It is `Send` and `Sync`, so one
59/// language can parse on many threads at once, and `Clone` when a copy is
60/// needed.
61///
62/// # The schematic
63///
64/// A schematic is a NOML document with up to four tables: `[language]` (the
65/// name, and optionally the version, file extensions, and start rule),
66/// `[lexer]` (identifier style, significant newlines, comments, strings),
67/// `[rules]` (the grammar), and `[capabilities]` (passes the language
68/// includes). The full reference is in `docs/API.md`.
69///
70/// # Examples
71///
72/// ```
73/// use lang_forge::Language;
74///
75/// let calc = Language::from_lsf(
76/// r##"
77/// [language]
78/// name = "calc"
79/// version = "1.0.0"
80/// extensions = ["calc"]
81///
82/// [lexer]
83/// line_comments = ["#"]
84///
85/// [rules]
86/// program = "stmt*"
87/// stmt = "'let' IDENT '=' expr ';' | expr ';'"
88///
89/// [rules.expr]
90/// operand = "NUMBER | IDENT | '(' expr ')'"
91/// levels = [
92/// { left = ["+", "-"] },
93/// { left = ["*", "/"] },
94/// { prefix = ["-"] },
95/// ]
96/// "##,
97/// )?;
98///
99/// let parse = calc.parse("let x = 2 * (3 + 4); # seven, doubled\n-x;");
100/// assert!(!parse.has_errors());
101///
102/// let stmt = calc.kind("stmt").expect("a rule");
103/// assert_eq!(parse.tree().child_nodes().filter(|n| *n.kind() == stmt).count(), 2);
104/// # Ok::<(), lang_forge::Error>(())
105/// ```
106#[derive(Clone, Debug)]
107pub struct Language {
108 grammar: Grammar,
109}
110
111impl Language {
112 /// Forges a language from the text of a `.lsf` schematic.
113 ///
114 /// The schematic is read, checked against the schematic layout, and its
115 /// grammar compiled and analysed. Everything wrong with it is reported at
116 /// once.
117 ///
118 /// # Errors
119 ///
120 /// Returns an [`Error`] carrying one diagnostic per problem, with spans
121 /// into `schematic`: NOML syntax errors; unknown, missing, or mistyped
122 /// settings; malformed rules; undefined rules (with a suggestion);
123 /// literals the lexer cannot produce; delimiters used twice; left
124 /// recursion; repetitions of something that can match nothing;
125 /// alternatives that can never match; and the use of NOML's dynamic
126 /// features, which would make the language depend on where it was forged.
127 ///
128 /// # Examples
129 ///
130 /// ```
131 /// use lang_forge::Language;
132 ///
133 /// let json = Language::from_lsf(
134 /// r#"
135 /// [language]
136 /// name = "json"
137 ///
138 /// [lexer]
139 /// strings = ['"']
140 ///
141 /// [rules]
142 /// document = "value"
143 /// value = "object | array | STRING | NUMBER | 'true' | 'false' | 'null'"
144 /// object = "'{' (member (',' member)*)? '}'"
145 /// member = "STRING ':' value"
146 /// array = "'[' (value (',' value)*)? ']'"
147 /// "#,
148 /// )?;
149 /// assert!(!json.parse(r#"{"a": [1, true, {"b": null}]}"#).has_errors());
150 /// assert!(json.parse(r#"{"a": }"#).has_errors());
151 /// # Ok::<(), lang_forge::Error>(())
152 /// ```
153 ///
154 /// A left-recursive rule is refused, with the fix:
155 ///
156 /// ```
157 /// use lang_forge::Language;
158 ///
159 /// let err = Language::from_lsf(
160 /// "[language]\nname = \"bad\"\n[rules]\nsum = \"sum '+' NUMBER | NUMBER\"\n",
161 /// )
162 /// .unwrap_err();
163 /// assert_eq!(err.to_string(), "4:1: rule `sum` is left-recursive: sum → sum");
164 /// ```
165 pub fn from_lsf(schematic: &str) -> Result<Self, Error> {
166 let mut report = Report::default();
167 let root = match noml::read(schematic) {
168 Ok(root) => root,
169 Err(diagnostic) => {
170 report.diagnostic(diagnostic);
171 return Err(report.into_error(schematic));
172 }
173 };
174 let spec = schematic::interpret(root, &mut report);
175 let grammar = spec.and_then(|spec| grammar::compile(&spec, schematic, &mut report));
176 match grammar {
177 Some(grammar) if report.is_clean() => Ok(Self { grammar }),
178 _ => {
179 if report.is_clean() {
180 report.error(Span::empty(0), "the schematic could not be forged");
181 }
182 Err(report.into_error(schematic))
183 }
184 }
185 }
186
187 /// The compiled tables, for the crate's own tests.
188 #[cfg(test)]
189 pub(crate) fn grammar(&self) -> &Grammar {
190 &self.grammar
191 }
192
193 /// The language's name, from `[language] name`.
194 #[inline]
195 #[must_use]
196 pub fn name(&self) -> &str {
197 &self.grammar.name
198 }
199
200 /// The language's version, from `[language] version`, if given.
201 ///
202 /// The text is kept as written; lang-forge does not interpret it.
203 #[inline]
204 #[must_use]
205 pub fn version(&self) -> Option<&str> {
206 self.grammar.version.as_deref()
207 }
208
209 /// The file extensions of the language's source files, without the dot,
210 /// from `[language] extensions`.
211 ///
212 /// # Examples
213 ///
214 /// ```
215 /// use lang_forge::Language;
216 ///
217 /// let lang = Language::from_lsf(
218 /// "[language]\nname = \"mox\"\nextensions = [\"mox\", \"mx\"]\n[rules]\nfile = \"IDENT*\"\n",
219 /// )?;
220 /// assert_eq!(lang.extensions().collect::<Vec<_>>(), ["mox", "mx"]);
221 /// assert!(lang.extensions().any(|e| e == "mx"));
222 /// # Ok::<(), lang_forge::Error>(())
223 /// ```
224 pub fn extensions(&self) -> impl ExactSizeIterator<Item = &str> {
225 self.grammar.extensions.iter().map(|e| &**e)
226 }
227
228 /// The capabilities the schematic includes, in the order their passes
229 /// run, from `[capabilities] include`.
230 ///
231 /// # Examples
232 ///
233 /// ```
234 /// use lang_forge::Language;
235 ///
236 /// let lang = Language::from_lsf(
237 /// "[language]\nname = \"iron\"\n[rules]\nfile = \"IDENT*\"\n\
238 /// [capabilities]\ninclude = [\"borrow-check\", \"thermal\"]\n",
239 /// )?;
240 /// assert_eq!(lang.capabilities().collect::<Vec<_>>(), ["borrow-check", "thermal"]);
241 /// # Ok::<(), lang_forge::Error>(())
242 /// ```
243 pub fn capabilities(&self) -> impl ExactSizeIterator<Item = &str> {
244 self.grammar.capabilities.iter().map(|c| &*c.name)
245 }
246
247 /// The kind called `name`, or `None` if the language has no such kind.
248 ///
249 /// Rule names name the nodes rules build (hidden `_` rules build none);
250 /// a keyword or symbol is named by its text; Pratt levels add their node
251 /// names (`binary`, `prefix`, `postfix` unless renamed); and every
252 /// language has `IDENT`, `NUMBER`, `STRING`, `NEWLINE`, `WHITESPACE`,
253 /// `COMMENT`, `UNKNOWN`, and `ERROR`. See [`Kind`] for the full table.
254 ///
255 /// The lookup is a binary search; look kinds up once and keep them.
256 ///
257 /// # Examples
258 ///
259 /// ```
260 /// use lang_forge::Language;
261 ///
262 /// let lang = Language::from_lsf("[language]\nname = \"x\"\n[rules]\nitem = \"'go' NUMBER\"\n")?;
263 /// assert!(lang.kind("item").is_some());
264 /// assert!(lang.kind("go").is_some());
265 /// assert!(lang.kind("ERROR").is_some());
266 /// assert!(lang.kind("missing").is_none());
267 /// # Ok::<(), lang_forge::Error>(())
268 /// ```
269 #[must_use]
270 pub fn kind(&self, name: &str) -> Option<Kind> {
271 self.grammar.kinds.get(name)
272 }
273
274 /// The name of `kind`: the inverse of [`kind`](Self::kind).
275 ///
276 /// Returns `"<unknown>"` for a kind this language does not have, which
277 /// can only come from another language.
278 ///
279 /// # Examples
280 ///
281 /// ```
282 /// use lang_forge::Language;
283 ///
284 /// let lang = Language::from_lsf("[language]\nname = \"x\"\n[rules]\nitem = \"'go' NUMBER\"\n")?;
285 /// let parse = lang.parse("go 7");
286 /// let names: Vec<&str> = parse.tree().tokens().map(|t| lang.kind_name(*t.kind())).collect();
287 /// assert_eq!(names, ["go", "WHITESPACE", "NUMBER"]);
288 /// # Ok::<(), lang_forge::Error>(())
289 /// ```
290 #[must_use]
291 pub fn kind_name(&self, kind: Kind) -> &str {
292 self.grammar.kinds.name(kind)
293 }
294
295 /// Splits `source` into tokens, trivia included.
296 ///
297 /// The tokens are contiguous and cover the whole source, so this is the
298 /// stream a syntax highlighter wants. Characters that begin no token come
299 /// back as `UNKNOWN` tokens; [`parse`](Self::parse) reports them, `lex`
300 /// does not. A source of 4 GiB or more, which spans cannot address,
301 /// yields no tokens.
302 ///
303 /// # Examples
304 ///
305 /// ```
306 /// use lang_forge::Language;
307 /// use lang_forge::syntax_lang::TokenKind;
308 ///
309 /// let lang = Language::from_lsf(
310 /// "[language]\nname = \"x\"\n[lexer]\nline_comments = [\"--\"]\n[rules]\nfile = \"IDENT*\"\n",
311 /// )?;
312 /// let tokens = lang.lex("alpha -- note\nbeta");
313 /// let significant: Vec<&str> = tokens
314 /// .iter()
315 /// .filter(|t| !t.is_trivia())
316 /// .map(|t| lang.kind_name(*t.kind()))
317 /// .collect();
318 /// assert_eq!(significant, ["IDENT", "IDENT"]);
319 /// assert_eq!(tokens.len(), 5); // IDENT, WHITESPACE, COMMENT, WHITESPACE, IDENT
320 /// # Ok::<(), lang_forge::Error>(())
321 /// ```
322 #[must_use]
323 pub fn lex(&self, source: &str) -> Vec<Token<Kind>> {
324 let mut tokens = Vec::new();
325 if u32::try_from(source.len()).is_ok() {
326 let mut diagnostics = Vec::new();
327 self.grammar
328 .lexer
329 .run(source, &mut tokens, &mut diagnostics);
330 }
331 tokens
332 }
333
334 /// Parses `source` into a lossless syntax tree.
335 ///
336 /// Never fails: problems become diagnostics on the returned [`Parse`] and
337 /// the tree is complete regardless, with unexpected tokens wrapped in
338 /// `ERROR` nodes. Input nested too deeply to parse is reported rather
339 /// than followed: the parser recurses at most 768 grammar levels, which
340 /// needs at most about 256 KiB of stack in a release build (768 KiB in a
341 /// debug build) and allows well over a hundred levels of nesting in
342 /// typical grammars.
343 ///
344 /// # Examples
345 ///
346 /// ```
347 /// use lang_forge::Language;
348 ///
349 /// let lang = Language::from_lsf(
350 /// "[language]\nname = \"block\"\n[rules]\nblock = \"'{' stmt* '}'\"\nstmt = \"IDENT ';'\"\n",
351 /// )?;
352 ///
353 /// let good = lang.parse("{ a; b; }");
354 /// assert!(!good.has_errors());
355 ///
356 /// // A stray `;` is skipped, the rest still parses.
357 /// let bad = lang.parse("{ a; ; b; }");
358 /// assert_eq!(bad.diagnostics().len(), 1);
359 /// assert_eq!(bad.diagnostics()[0].message(), "expected stmt, found `;`");
360 /// let error = lang.kind("ERROR").expect("built in");
361 /// assert_eq!(bad.tree().descendants().filter(|n| *n.kind() == error).count(), 1);
362 /// # Ok::<(), lang_forge::Error>(())
363 /// ```
364 #[must_use]
365 pub fn parse<'a>(&'a self, source: &'a str) -> Parse<'a> {
366 let (tree, diagnostics) = parser::parse(&self.grammar, source);
367 Parse::new(self, source, tree, diagnostics)
368 }
369
370 /// Assembles the language's capability pipeline from a registry of passes.
371 ///
372 /// `passes` may hold passes for many languages; the pipeline takes the
373 /// ones whose [`Pass::name`] the schematic's `[capabilities] include`
374 /// lists, in that order, and ignores the rest. Run it over each
375 /// [`Parse`] with [`PassManager::run`].
376 ///
377 /// # Errors
378 ///
379 /// Returns an [`Error`] with a diagnostic, pointing into the schematic,
380 /// for every included capability that has no pass in `passes` or more
381 /// than one.
382 ///
383 /// # Examples
384 ///
385 /// ```
386 /// use lang_forge::diag_lang::{Diagnostic, Label, Severity};
387 /// use lang_forge::pass_lang::{Outcome, Pass, PassError};
388 /// use lang_forge::{Capability, Language, Parse};
389 ///
390 /// /// Warns about every identifier written in capitals.
391 /// struct Shouting;
392 ///
393 /// impl<'a> Pass<Parse<'a>> for Shouting {
394 /// fn name(&self) -> &'static str {
395 /// "no-shouting"
396 /// }
397 ///
398 /// fn run(&mut self, parse: &mut Parse<'a>) -> Result<Outcome, PassError> {
399 /// let ident = parse.language().kind("IDENT").ok_or_else(|| PassError::new("no IDENT"))?;
400 /// let loud: Vec<_> = parse
401 /// .tree()
402 /// .tokens()
403 /// .filter(|t| *t.kind() == ident)
404 /// .filter(|t| {
405 /// let text = &parse.source()[t.span().start().to_usize()..t.span().end().to_usize()];
406 /// text.len() > 1 && text.chars().all(|c| c.is_ascii_uppercase())
407 /// })
408 /// .map(|t| t.span())
409 /// .collect();
410 /// for span in loud {
411 /// parse.report(Diagnostic::new(Severity::Warning, "no need to shout", Label::unlabelled(span)));
412 /// }
413 /// Ok(Outcome::Unchanged)
414 /// }
415 /// }
416 ///
417 /// let lang = Language::from_lsf(
418 /// "[language]\nname = \"words\"\n[rules]\nfile = \"IDENT*\"\n\
419 /// [capabilities]\ninclude = [\"no-shouting\"]\n",
420 /// )?;
421 /// let registry: Vec<Capability> = vec![Box::new(Shouting)];
422 /// let mut pipeline = lang.pipeline(registry)?;
423 ///
424 /// let mut parse = lang.parse("quiet LOUD calm");
425 /// pipeline.run(&mut parse).expect("the pass succeeds");
426 /// assert_eq!(parse.diagnostics().len(), 1);
427 /// assert_eq!(parse.diagnostics()[0].message(), "no need to shout");
428 /// # Ok::<(), lang_forge::Error>(())
429 /// ```
430 pub fn pipeline<'a>(
431 &self,
432 passes: impl IntoIterator<Item = Capability>,
433 ) -> Result<PassManager<Parse<'a>>, Error> {
434 let mut available: Vec<Option<Capability>> = passes.into_iter().map(Some).collect();
435 let mut manager = PassManager::new();
436 let mut problems = Vec::new();
437 let mut location = None;
438 for capability in self.grammar.capabilities.iter() {
439 let mut matching = available
440 .iter()
441 .enumerate()
442 .filter(|(_, p)| p.as_ref().is_some_and(|p| p.name() == &*capability.name))
443 .map(|(i, _)| i);
444 let (first, second) = (matching.next(), matching.next());
445 let problem = match (first, second) {
446 (Some(i), None) => {
447 if let Some(pass) = available[i].take() {
448 let _ = manager.add(Plugged(pass));
449 }
450 continue;
451 }
452 (None, _) => Diagnostic::new(
453 Severity::Error,
454 format!("capability `{}` has no pass", capability.name),
455 Label::unlabelled(capability.span),
456 )
457 .with_help(format!(
458 "pass a capability whose `name()` is \"{}\"",
459 capability.name
460 )),
461 (Some(_), Some(_)) => Diagnostic::new(
462 Severity::Error,
463 format!("capability `{}` has more than one pass", capability.name),
464 Label::unlabelled(capability.span),
465 ),
466 };
467 if location.is_none() {
468 location = Some((capability.line, capability.column));
469 }
470 problems.push(problem);
471 }
472 match location {
473 None => Ok(manager),
474 Some((line, column)) => Err(Error::located(problems, line, column)),
475 }
476 }
477}
478
479impl FromStr for Language {
480 type Err = Error;
481
482 /// Forges a language; the same as [`Language::from_lsf`].
483 ///
484 /// ```
485 /// use lang_forge::Language;
486 ///
487 /// let lang: Language = "[language]\nname = \"n\"\n[rules]\nn = \"NUMBER\"\n".parse()?;
488 /// assert_eq!(lang.name(), "n");
489 /// # Ok::<(), lang_forge::Error>(())
490 /// ```
491 fn from_str(schematic: &str) -> Result<Self, Error> {
492 Self::from_lsf(schematic)
493 }
494}
495
496/// A boxed capability, as the pass manager stores passes.
497struct Plugged(Capability);
498
499impl<'a> Pass<Parse<'a>> for Plugged {
500 fn name(&self) -> &'static str {
501 self.0.name()
502 }
503
504 fn run(&mut self, unit: &mut Parse<'a>) -> Result<Outcome, PassError> {
505 self.0.run(unit)
506 }
507}