meta_language/grammar/emit/
javascript.rs

1use std::collections::{BTreeMap, BTreeSet};
2use std::fmt::Write as _;
3
4use crate::grammar::{CharClassItem, Grammar, GrammarExpr, GrammarFormat, RuleKind};
5
6use super::{
7    finish_lines, ordered_rules, peg_choice_alternatives, unsupported_error, EmitReport,
8    GrammarEmitError,
9};
10
11/// Bundled JavaScript parser codegen output.
12#[derive(Clone, Debug, PartialEq, Eq)]
13pub struct JsParserArtifacts {
14    /// Peggy grammar source.
15    pub peggy_grammar: String,
16    /// ESM wrapper module that compiles and exports a Peggy parser.
17    pub module: String,
18}
19
20/// Emits Peggy PEG grammar text from the grammar IR.
21///
22/// Peggy maps directly to the IR's PEG-oriented expression algebra: ordered
23/// choice uses `/`, sequences are whitespace-separated, predicates use `&` and
24/// `!`, labels use `label:expr`, and counted repetitions use Peggy's
25/// `expr|min..max|` form.
26///
27/// # Errors
28///
29/// Returns [`GrammarEmitError`] when the IR contains an internal invariant that
30/// cannot form valid Peggy text, such as an empty choice, an empty character
31/// class, a descending character range, or counted repetition with `max < min`.
32pub fn emit_peggy(grammar: &Grammar) -> Result<(String, EmitReport), GrammarEmitError> {
33    let mut report = EmitReport::default();
34    let names = NamePlan::new(grammar, &mut report);
35    let mut emitter = PeggyEmitter { report, names };
36    let mut lines = Vec::new();
37
38    for rule in ordered_rules(grammar) {
39        if let Some(doc) = rule.doc() {
40            push_doc_lines(&mut lines, doc);
41        }
42        if let Some(comment) = emitter.names.rule_rename_comment(rule.name()) {
43            lines.push(comment);
44        }
45        if contains_unordered_choice(rule.expr()) {
46            lines.push(
47                "// NOTE: unordered choice in source is emitted as ordered Peggy choice."
48                    .to_string(),
49            );
50        }
51        if let Some(comment) = rule_kind_comment(rule.kind()) {
52            lines.push(comment.to_string());
53        }
54
55        let body = emitter.emit_expr(rule.expr(), Precedence::Choice)?;
56        let body = apply_rule_kind(rule.kind(), body, &mut emitter.report);
57        let name = emitter.names.name_for(rule.name());
58        lines.push(format!("{name} = {body}"));
59    }
60
61    Ok((finish_lines(&lines), emitter.report))
62}
63
64/// Emits a runnable JavaScript parser bundle from the grammar IR.
65///
66/// The generated ESM module imports `peggy`, embeds the emitted grammar as a
67/// JavaScript string literal, and exports `parser = peggy.generate(GRAMMAR)`.
68///
69/// # Errors
70///
71/// Returns [`GrammarEmitError`] when the underlying Peggy grammar emitter cannot
72/// represent an invalid IR construct.
73pub fn emit_javascript_parser(
74    grammar: &Grammar,
75) -> Result<(JsParserArtifacts, EmitReport), GrammarEmitError> {
76    let (peggy_grammar, report) = emit_peggy(grammar)?;
77    let module = render_javascript_module(&peggy_grammar);
78
79    Ok((
80        JsParserArtifacts {
81            peggy_grammar,
82            module,
83        },
84        report,
85    ))
86}
87
88#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
89enum Precedence {
90    Choice = 0,
91    Sequence = 1,
92    Prefix = 2,
93    Postfix = 3,
94    Atom = 4,
95}
96
97#[derive(Clone, Debug)]
98struct PeggyEmitter {
99    report: EmitReport,
100    names: NamePlan,
101}
102
103impl PeggyEmitter {
104    fn emit_expr(
105        &mut self,
106        expr: &GrammarExpr,
107        parent: Precedence,
108    ) -> Result<String, GrammarEmitError> {
109        let (text, precedence) = match expr {
110            GrammarExpr::Empty => (quote_js_string(""), Precedence::Atom),
111            GrammarExpr::Terminal(value) => (quote_js_string(value), Precedence::Atom),
112            GrammarExpr::TerminalInsensitive(value) => {
113                (format!("{}i", quote_js_string(value)), Precedence::Atom)
114            }
115            GrammarExpr::CharRange(start, end) => {
116                (emit_char_range(*start, *end)?, Precedence::Atom)
117            }
118            GrammarExpr::CharClass { negated, items } => {
119                (emit_char_class(*negated, items)?, Precedence::Atom)
120            }
121            GrammarExpr::AnyChar => (".".to_string(), Precedence::Atom),
122            GrammarExpr::NonTerminal(name) => (self.names.name_for(name), Precedence::Atom),
123            GrammarExpr::Choice {
124                ordered,
125                alternatives,
126            } => (
127                self.emit_choice(*ordered, alternatives)?,
128                Precedence::Choice,
129            ),
130            GrammarExpr::Sequence(items) => (self.emit_sequence(items)?, Precedence::Sequence),
131            GrammarExpr::Optional(inner) => {
132                let inner = self.emit_expr(inner, Precedence::Postfix)?;
133                (format!("{inner}?"), Precedence::Postfix)
134            }
135            GrammarExpr::ZeroOrMore(inner) => {
136                let inner = self.emit_expr(inner, Precedence::Postfix)?;
137                (format!("{inner}*"), Precedence::Postfix)
138            }
139            GrammarExpr::OneOrMore(inner) => {
140                let inner = self.emit_expr(inner, Precedence::Postfix)?;
141                (format!("{inner}+"), Precedence::Postfix)
142            }
143            GrammarExpr::Repeat { expr, min, max } => {
144                (self.emit_repeat(expr, *min, *max)?, Precedence::Postfix)
145            }
146            GrammarExpr::And(inner) => {
147                let inner = self.emit_expr(inner, Precedence::Prefix)?;
148                (format!("&{inner}"), Precedence::Prefix)
149            }
150            GrammarExpr::Not(inner) => {
151                let inner = self.emit_expr(inner, Precedence::Prefix)?;
152                (format!("!{inner}"), Precedence::Prefix)
153            }
154            GrammarExpr::Capture { label, expr } => {
155                let Some(label) = label else {
156                    return self.emit_expr(expr, parent);
157                };
158                let label = self.emit_label(label);
159                let inner = self.emit_expr(expr, Precedence::Atom)?;
160                (format!("{label}:{inner}"), Precedence::Prefix)
161            }
162        };
163
164        if precedence < parent {
165            Ok(format!("({text})"))
166        } else {
167            Ok(text)
168        }
169    }
170
171    fn emit_choice(
172        &mut self,
173        ordered: bool,
174        alternatives: &[GrammarExpr],
175    ) -> Result<String, GrammarEmitError> {
176        if alternatives.is_empty() {
177            return Err(unsupported_error(GrammarFormat::Peg, "empty Choice"));
178        }
179        if !ordered {
180            self.report
181                .add_lossy("Peggy treats unordered choice as ordered choice");
182        }
183
184        peg_choice_alternatives(ordered, alternatives)
185            .into_iter()
186            .map(|alternative| self.emit_expr(alternative, Precedence::Choice))
187            .collect::<Result<Vec<_>, _>>()
188            .map(|items| items.join(" / "))
189    }
190
191    fn emit_sequence(&mut self, items: &[GrammarExpr]) -> Result<String, GrammarEmitError> {
192        let mut emitted = Vec::new();
193        for item in items {
194            if matches!(item, GrammarExpr::Empty) {
195                continue;
196            }
197            let text = self.emit_expr(item, Precedence::Sequence)?;
198            if !text.is_empty() {
199                emitted.push(text);
200            }
201        }
202
203        if emitted.is_empty() {
204            Ok(quote_js_string(""))
205        } else {
206            Ok(emitted.join(" "))
207        }
208    }
209
210    fn emit_repeat(
211        &mut self,
212        expr: &GrammarExpr,
213        min: usize,
214        max: Option<usize>,
215    ) -> Result<String, GrammarEmitError> {
216        if max.is_some_and(|max| max < min) {
217            return Err(unsupported_error(
218                GrammarFormat::Peg,
219                format!("Repeat with min {min} greater than max {max:?}"),
220            ));
221        }
222
223        let inner = self.emit_expr(expr, Precedence::Postfix)?;
224        let suffix = match max {
225            Some(max) if min == max => format!("|{min}|"),
226            Some(max) => format!("|{min}..{max}|"),
227            None => format!("|{min}..|"),
228        };
229        Ok(format!("{inner}{suffix}"))
230    }
231
232    fn emit_label(&mut self, label: &str) -> String {
233        let emitted = sanitize_identifier(label);
234        if emitted != label {
235            self.report.add_lossy(format!(
236                "Peggy renamed capture label {label:?} to {emitted:?}"
237            ));
238        }
239        emitted
240    }
241}
242
243#[derive(Clone, Debug)]
244struct NamePlan {
245    names: BTreeMap<String, String>,
246}
247
248impl NamePlan {
249    fn new(grammar: &Grammar, report: &mut EmitReport) -> Self {
250        let defined_names = grammar
251            .rules()
252            .iter()
253            .map(|rule| rule.name().to_string())
254            .collect::<BTreeSet<_>>();
255        let mut symbols = Vec::new();
256        let mut seen = BTreeSet::new();
257
258        for rule in grammar.rules() {
259            push_unique_symbol(&mut symbols, &mut seen, rule.name());
260        }
261        for reference in grammar.referenced_nonterminals() {
262            push_unique_symbol(&mut symbols, &mut seen, &reference);
263        }
264
265        let mut used = BTreeSet::new();
266        let mut names = BTreeMap::new();
267        for symbol in symbols {
268            let base = sanitize_identifier(&symbol);
269            let emitted = unique_identifier(&base, &mut used);
270            if emitted != symbol {
271                report_name_change(report, &defined_names, &symbol, &emitted);
272            }
273            names.insert(symbol, emitted);
274        }
275
276        Self { names }
277    }
278
279    fn name_for(&self, source: &str) -> String {
280        self.names
281            .get(source)
282            .map_or_else(|| source.to_string(), Clone::clone)
283    }
284
285    fn rule_rename_comment(&self, source: &str) -> Option<String> {
286        let emitted = self.names.get(source)?;
287        (emitted != source).then(|| {
288            format!(
289                "// NOTE: rule {source:?} is emitted as {emitted:?} for Peggy identifier syntax."
290            )
291        })
292    }
293}
294
295fn push_unique_symbol(symbols: &mut Vec<String>, seen: &mut BTreeSet<String>, symbol: &str) {
296    if seen.insert(symbol.to_string()) {
297        symbols.push(symbol.to_string());
298    }
299}
300
301fn report_name_change(
302    report: &mut EmitReport,
303    defined_names: &BTreeSet<String>,
304    source: &str,
305    emitted: &str,
306) {
307    let kind = if defined_names.contains(source) {
308        "rule"
309    } else {
310        "non-terminal reference"
311    };
312    report.add_lossy(format!("Peggy renamed {kind} {source:?} to {emitted:?}"));
313}
314
315fn unique_identifier(base: &str, used: &mut BTreeSet<String>) -> String {
316    if used.insert(base.to_string()) {
317        return base.to_string();
318    }
319
320    let mut suffix = 1_usize;
321    loop {
322        let candidate = format!("{base}_{suffix}");
323        if used.insert(candidate.clone()) {
324            return candidate;
325        }
326        suffix = suffix.saturating_add(1);
327    }
328}
329
330fn sanitize_identifier(source: &str) -> String {
331    let mut output = String::new();
332    for character in source.chars() {
333        if output.is_empty() {
334            if is_identifier_start(character) {
335                output.push(character);
336            } else if is_identifier_continue(character) {
337                output.push('_');
338                output.push(character);
339            } else {
340                output.push('_');
341            }
342        } else if is_identifier_continue(character) {
343            output.push(character);
344        } else {
345            output.push('_');
346        }
347    }
348
349    if output.is_empty() {
350        output.push_str("ml");
351    }
352    if is_reserved_identifier(&output) {
353        output.insert_str(0, "ml_");
354    }
355    output
356}
357
358const fn is_identifier_start(character: char) -> bool {
359    character.is_ascii_alphabetic() || character == '_'
360}
361
362const fn is_identifier_continue(character: char) -> bool {
363    character.is_ascii_alphanumeric() || character == '_' || character == '$'
364}
365
366fn is_reserved_identifier(value: &str) -> bool {
367    matches!(
368        value,
369        "arguments"
370            | "await"
371            | "break"
372            | "case"
373            | "catch"
374            | "class"
375            | "const"
376            | "continue"
377            | "debugger"
378            | "default"
379            | "delete"
380            | "do"
381            | "else"
382            | "enum"
383            | "eval"
384            | "export"
385            | "extends"
386            | "false"
387            | "finally"
388            | "for"
389            | "function"
390            | "if"
391            | "implements"
392            | "import"
393            | "in"
394            | "instanceof"
395            | "interface"
396            | "let"
397            | "new"
398            | "null"
399            | "package"
400            | "private"
401            | "protected"
402            | "public"
403            | "return"
404            | "static"
405            | "super"
406            | "switch"
407            | "this"
408            | "throw"
409            | "true"
410            | "try"
411            | "typeof"
412            | "var"
413            | "void"
414            | "while"
415            | "with"
416            | "yield"
417    )
418}
419
420fn emit_char_range(start: char, end: char) -> Result<String, GrammarEmitError> {
421    validate_range("CharRange", start, end)?;
422    Ok(format!(
423        "[{}-{}]",
424        escaped_class_char(start),
425        escaped_class_char(end)
426    ))
427}
428
429fn emit_char_class(negated: bool, items: &[CharClassItem]) -> Result<String, GrammarEmitError> {
430    if items.is_empty() {
431        return Err(unsupported_error(GrammarFormat::Peg, "empty CharClass"));
432    }
433
434    let mut output = String::new();
435    output.push('[');
436    if negated {
437        output.push('^');
438    }
439    for item in items {
440        output.push_str(&emit_char_class_item(item)?);
441    }
442    output.push(']');
443    Ok(output)
444}
445
446fn emit_char_class_item(item: &CharClassItem) -> Result<String, GrammarEmitError> {
447    match item {
448        CharClassItem::Char(value) => Ok(escaped_class_char(*value)),
449        CharClassItem::Range(start, end) => {
450            validate_range("CharClass range", *start, *end)?;
451            Ok(format!(
452                "{}-{}",
453                escaped_class_char(*start),
454                escaped_class_char(*end)
455            ))
456        }
457    }
458}
459
460fn validate_range(construct: &str, start: char, end: char) -> Result<(), GrammarEmitError> {
461    if start > end {
462        return Err(unsupported_error(
463            GrammarFormat::Peg,
464            format!(
465                "{construct} has descending bounds U+{:04X}..=U+{:04X}",
466                start as u32, end as u32
467            ),
468        ));
469    }
470    Ok(())
471}
472
473fn apply_rule_kind(kind: RuleKind, body: String, report: &mut EmitReport) -> String {
474    match kind {
475        RuleKind::Normal => body,
476        RuleKind::Atomic => {
477            report.add_lossy("Peggy has no RuleKind::Atomic modifier; emitted a text() action");
478            format!("({body}) {{ return text(); }}")
479        }
480        RuleKind::Silent => {
481            report.add_lossy("Peggy has no RuleKind::Silent modifier; emitted a normal rule");
482            body
483        }
484        RuleKind::Token => {
485            report.add_lossy("Peggy has no RuleKind::Token modifier; emitted a text() action");
486            format!("({body}) {{ return text(); }}")
487        }
488    }
489}
490
491const fn rule_kind_comment(kind: RuleKind) -> Option<&'static str> {
492    match kind {
493        RuleKind::Normal => None,
494        RuleKind::Atomic => {
495            Some("// NOTE: Peggy has no atomic rule modifier; this rule returns its matched text.")
496        }
497        RuleKind::Silent => Some(
498            "// NOTE: Peggy has no silent rule modifier; this rule is emitted as a normal rule.",
499        ),
500        RuleKind::Token => {
501            Some("// NOTE: Peggy has no token rule modifier; this rule returns its matched text.")
502        }
503    }
504}
505
506fn push_doc_lines(lines: &mut Vec<String>, doc: &str) {
507    if doc.is_empty() {
508        lines.push("//".to_string());
509        return;
510    }
511    for line in doc.lines() {
512        if line.is_empty() {
513            lines.push("//".to_string());
514        } else {
515            lines.push(format!("// {line}"));
516        }
517    }
518}
519
520fn contains_unordered_choice(expr: &GrammarExpr) -> bool {
521    match expr {
522        GrammarExpr::Choice { ordered: false, .. } => true,
523        GrammarExpr::Choice { alternatives, .. } | GrammarExpr::Sequence(alternatives) => {
524            alternatives.iter().any(contains_unordered_choice)
525        }
526        GrammarExpr::Optional(expr)
527        | GrammarExpr::ZeroOrMore(expr)
528        | GrammarExpr::OneOrMore(expr)
529        | GrammarExpr::And(expr)
530        | GrammarExpr::Not(expr)
531        | GrammarExpr::Capture { expr, .. }
532        | GrammarExpr::Repeat { expr, .. } => contains_unordered_choice(expr),
533        GrammarExpr::Empty
534        | GrammarExpr::Terminal(_)
535        | GrammarExpr::TerminalInsensitive(_)
536        | GrammarExpr::CharRange(_, _)
537        | GrammarExpr::CharClass { .. }
538        | GrammarExpr::AnyChar
539        | GrammarExpr::NonTerminal(_) => false,
540    }
541}
542
543fn render_javascript_module(peggy_grammar: &str) -> String {
544    format!(
545        "import peggy from \"peggy\";\n\nconst GRAMMAR = {};\nexport const parser = peggy.generate(GRAMMAR);\n",
546        quote_js_string(peggy_grammar)
547    )
548}
549
550fn quote_js_string(value: &str) -> String {
551    let mut output = String::with_capacity(value.len() + 2);
552    output.push('"');
553    for character in value.chars() {
554        push_escaped_string_char(&mut output, character);
555    }
556    output.push('"');
557    output
558}
559
560fn escaped_class_char(character: char) -> String {
561    let mut output = String::new();
562    push_escaped_class_char(&mut output, character);
563    output
564}
565
566fn push_escaped_string_char(output: &mut String, character: char) {
567    match character {
568        '"' => output.push_str("\\\""),
569        '\\' => output.push_str("\\\\"),
570        '\n' => output.push_str("\\n"),
571        '\r' => output.push_str("\\r"),
572        '\t' => output.push_str("\\t"),
573        '\u{08}' => output.push_str("\\b"),
574        '\u{0c}' => output.push_str("\\f"),
575        '\u{2028}' => output.push_str("\\u2028"),
576        '\u{2029}' => output.push_str("\\u2029"),
577        character if character.is_ascii_control() => push_hex_escape(output, character),
578        character if !character.is_ascii() => push_unicode_escape(output, character),
579        character => output.push(character),
580    }
581}
582
583fn push_escaped_class_char(output: &mut String, character: char) {
584    match character {
585        '\\' => output.push_str("\\\\"),
586        '[' => output.push_str("\\["),
587        ']' => output.push_str("\\]"),
588        '-' => output.push_str("\\-"),
589        '^' => output.push_str("\\^"),
590        '\n' => output.push_str("\\n"),
591        '\r' => output.push_str("\\r"),
592        '\t' => output.push_str("\\t"),
593        '\u{08}' => output.push_str("\\b"),
594        '\u{0c}' => output.push_str("\\f"),
595        character if character.is_ascii_control() => push_hex_escape(output, character),
596        character if !character.is_ascii() => push_unicode_escape(output, character),
597        character => output.push(character),
598    }
599}
600
601fn push_hex_escape(output: &mut String, character: char) {
602    let code = character as u32;
603    let _ = write!(output, "\\x{code:02X}");
604}
605
606fn push_unicode_escape(output: &mut String, character: char) {
607    let code = character as u32;
608    if code <= 0xffff {
609        let _ = write!(output, "\\u{code:04X}");
610    } else {
611        let _ = write!(output, "\\u{{{code:X}}}");
612    }
613}
meta_language/grammar/emit/javascript.rs

meta_language/grammar/emit/
javascript.rs
