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 /// A kind is only meaningful to the language that made it. Given a kind
277 /// from another language, `kind_name` cannot tell: it returns whatever
278 /// name this language has at that kind's position in its kind table —
279 /// usually a wrong one — or `"<unknown>"` when this language has fewer
280 /// kinds than that.
281 ///
282 /// # Examples
283 ///
284 /// ```
285 /// use lang_forge::Language;
286 ///
287 /// let lang = Language::from_lsf("[language]\nname = \"x\"\n[rules]\nitem = \"'go' NUMBER\"\n")?;
288 /// let parse = lang.parse("go 7");
289 /// let names: Vec<&str> = parse.tree().tokens().map(|t| lang.kind_name(*t.kind())).collect();
290 /// assert_eq!(names, ["go", "WHITESPACE", "NUMBER"]);
291 ///
292 /// // Another language's kinds get a wrong name, or none.
293 /// let other = Language::from_lsf(
294 /// "[language]\nname = \"y\"\n[rules]\nlist = \"'[' (pair (',' pair)*)? ']'\"\npair = \"IDENT ':' NUMBER\"\n",
295 /// )?;
296 /// assert_eq!(lang.kind_name(other.kind("[").expect("a symbol")), "go");
297 /// assert_eq!(lang.kind_name(other.kind("pair").expect("a rule")), "<unknown>");
298 /// # Ok::<(), lang_forge::Error>(())
299 /// ```
300 #[must_use]
301 pub fn kind_name(&self, kind: Kind) -> &str {
302 self.grammar.kinds.name(kind)
303 }
304
305 /// Splits `source` into tokens, trivia included.
306 ///
307 /// The tokens are contiguous and cover the whole source, so this is the
308 /// stream a syntax highlighter wants. Characters that begin no token come
309 /// back as `UNKNOWN` tokens; [`parse`](Self::parse) reports them, `lex`
310 /// does not. A source of 4 GiB or more, which spans cannot address,
311 /// yields no tokens.
312 ///
313 /// # Examples
314 ///
315 /// ```
316 /// use lang_forge::Language;
317 /// use lang_forge::syntax_lang::TokenKind;
318 ///
319 /// let lang = Language::from_lsf(
320 /// "[language]\nname = \"x\"\n[lexer]\nline_comments = [\"--\"]\n[rules]\nfile = \"IDENT*\"\n",
321 /// )?;
322 /// let tokens = lang.lex("alpha -- note\nbeta");
323 /// let significant: Vec<&str> = tokens
324 /// .iter()
325 /// .filter(|t| !t.is_trivia())
326 /// .map(|t| lang.kind_name(*t.kind()))
327 /// .collect();
328 /// assert_eq!(significant, ["IDENT", "IDENT"]);
329 /// assert_eq!(tokens.len(), 5); // IDENT, WHITESPACE, COMMENT, WHITESPACE, IDENT
330 /// # Ok::<(), lang_forge::Error>(())
331 /// ```
332 #[must_use]
333 pub fn lex(&self, source: &str) -> Vec<Token<Kind>> {
334 let mut tokens = Vec::new();
335 if u32::try_from(source.len()).is_ok() {
336 let mut diagnostics = Vec::new();
337 self.grammar
338 .lexer
339 .run(source, &mut tokens, &mut diagnostics);
340 }
341 tokens
342 }
343
344 /// Parses `source` into a lossless syntax tree.
345 ///
346 /// Never fails: problems become diagnostics on the returned [`Parse`] and
347 /// the tree is complete regardless, with unexpected tokens wrapped in
348 /// `ERROR` nodes. Input nested too deeply to parse is reported rather
349 /// than followed: the parser recurses at most 768 grammar levels, which
350 /// needs at most about 256 KiB of stack in a release build (768 KiB in a
351 /// debug build) and allows well over a hundred levels of nesting in
352 /// typical grammars.
353 ///
354 /// # Examples
355 ///
356 /// ```
357 /// use lang_forge::Language;
358 ///
359 /// let lang = Language::from_lsf(
360 /// "[language]\nname = \"block\"\n[rules]\nblock = \"'{' stmt* '}'\"\nstmt = \"IDENT ';'\"\n",
361 /// )?;
362 ///
363 /// let good = lang.parse("{ a; b; }");
364 /// assert!(!good.has_errors());
365 ///
366 /// // A stray `;` is skipped, the rest still parses.
367 /// let bad = lang.parse("{ a; ; b; }");
368 /// assert_eq!(bad.diagnostics().len(), 1);
369 /// assert_eq!(bad.diagnostics()[0].message(), "expected stmt, found `;`");
370 /// let error = lang.kind("ERROR").expect("built in");
371 /// assert_eq!(bad.tree().descendants().filter(|n| *n.kind() == error).count(), 1);
372 /// # Ok::<(), lang_forge::Error>(())
373 /// ```
374 #[must_use]
375 pub fn parse<'a>(&'a self, source: &'a str) -> Parse<'a> {
376 let (tree, diagnostics) = parser::parse(&self.grammar, source);
377 Parse::new(self, source, tree, diagnostics)
378 }
379
380 /// Assembles the language's capability pipeline from a registry of passes.
381 ///
382 /// `passes` may hold passes for many languages; the pipeline takes the
383 /// ones whose [`Pass::name`] the schematic's `[capabilities] include`
384 /// lists, in that order, and ignores the rest. Run it over each
385 /// [`Parse`] with [`PassManager::run`].
386 ///
387 /// # Errors
388 ///
389 /// Returns an [`Error`] with a diagnostic, pointing into the schematic,
390 /// for every included capability that has no pass in `passes` or more
391 /// than one.
392 ///
393 /// # Examples
394 ///
395 /// ```
396 /// use lang_forge::diag_lang::{Diagnostic, Label, Severity};
397 /// use lang_forge::pass_lang::{Outcome, Pass, PassError};
398 /// use lang_forge::{Capability, Language, Parse};
399 ///
400 /// /// Warns about every identifier written in capitals.
401 /// struct Shouting;
402 ///
403 /// impl<'a> Pass<Parse<'a>> for Shouting {
404 /// fn name(&self) -> &'static str {
405 /// "no-shouting"
406 /// }
407 ///
408 /// fn run(&mut self, parse: &mut Parse<'a>) -> Result<Outcome, PassError> {
409 /// let ident = parse.language().kind("IDENT").ok_or_else(|| PassError::new("no IDENT"))?;
410 /// let loud: Vec<_> = parse
411 /// .tree()
412 /// .tokens()
413 /// .filter(|t| *t.kind() == ident)
414 /// .filter(|t| {
415 /// let text = &parse.source()[t.span().start().to_usize()..t.span().end().to_usize()];
416 /// text.len() > 1 && text.chars().all(|c| c.is_ascii_uppercase())
417 /// })
418 /// .map(|t| t.span())
419 /// .collect();
420 /// for span in loud {
421 /// parse.report(Diagnostic::new(Severity::Warning, "no need to shout", Label::unlabelled(span)));
422 /// }
423 /// Ok(Outcome::Unchanged)
424 /// }
425 /// }
426 ///
427 /// let lang = Language::from_lsf(
428 /// "[language]\nname = \"words\"\n[rules]\nfile = \"IDENT*\"\n\
429 /// [capabilities]\ninclude = [\"no-shouting\"]\n",
430 /// )?;
431 /// let registry: Vec<Capability> = vec![Box::new(Shouting)];
432 /// let mut pipeline = lang.pipeline(registry)?;
433 ///
434 /// let mut parse = lang.parse("quiet LOUD calm");
435 /// pipeline.run(&mut parse).expect("the pass succeeds");
436 /// assert_eq!(parse.diagnostics().len(), 1);
437 /// assert_eq!(parse.diagnostics()[0].message(), "no need to shout");
438 /// # Ok::<(), lang_forge::Error>(())
439 /// ```
440 pub fn pipeline<'a>(
441 &self,
442 passes: impl IntoIterator<Item = Capability>,
443 ) -> Result<PassManager<Parse<'a>>, Error> {
444 let mut available: Vec<Option<Capability>> = passes.into_iter().map(Some).collect();
445 let mut manager = PassManager::new();
446 let mut problems = Vec::new();
447 let mut location = None;
448 for capability in self.grammar.capabilities.iter() {
449 let mut matching = available
450 .iter()
451 .enumerate()
452 .filter(|(_, p)| p.as_ref().is_some_and(|p| p.name() == &*capability.name))
453 .map(|(i, _)| i);
454 let (first, second) = (matching.next(), matching.next());
455 let problem = match (first, second) {
456 (Some(i), None) => {
457 if let Some(pass) = available[i].take() {
458 let _ = manager.add(Plugged(pass));
459 }
460 continue;
461 }
462 (None, _) => Diagnostic::new(
463 Severity::Error,
464 format!("capability `{}` has no pass", capability.name),
465 Label::unlabelled(capability.span),
466 )
467 .with_help(format!(
468 "pass a capability whose `name()` is \"{}\"",
469 capability.name
470 )),
471 (Some(_), Some(_)) => Diagnostic::new(
472 Severity::Error,
473 format!("capability `{}` has more than one pass", capability.name),
474 Label::unlabelled(capability.span),
475 ),
476 };
477 if location.is_none() {
478 location = Some((capability.line, capability.column));
479 }
480 problems.push(problem);
481 }
482 match location {
483 None => Ok(manager),
484 Some((line, column)) => Err(Error::located(problems, line, column)),
485 }
486 }
487}
488
489impl FromStr for Language {
490 type Err = Error;
491
492 /// Forges a language; the same as [`Language::from_lsf`].
493 ///
494 /// ```
495 /// use lang_forge::Language;
496 ///
497 /// let lang: Language = "[language]\nname = \"n\"\n[rules]\nn = \"NUMBER\"\n".parse()?;
498 /// assert_eq!(lang.name(), "n");
499 /// # Ok::<(), lang_forge::Error>(())
500 /// ```
501 fn from_str(schematic: &str) -> Result<Self, Error> {
502 Self::from_lsf(schematic)
503 }
504}
505
506/// A boxed capability, as the pass manager stores passes.
507struct Plugged(Capability);
508
509impl<'a> Pass<Parse<'a>> for Plugged {
510 fn name(&self) -> &'static str {
511 self.0.name()
512 }
513
514 fn run(&mut self, unit: &mut Parse<'a>) -> Result<Outcome, PassError> {
515 self.0.run(unit)
516 }
517}