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    EmitReport, GrammarEmitError, finish_lines, ordered_rules, peg_choice_alternatives,
8    unsupported_error,
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::Feature(feature) => {
155                return Err(unsupported_error(GrammarFormat::Peg, feature.head()));
156            }
157            GrammarExpr::Capture { label, expr } => {
158                let Some(label) = label else {
159                    return self.emit_expr(expr, parent);
160                };
161                let label = self.emit_label(label);
162                let inner = self.emit_expr(expr, Precedence::Atom)?;
163                (format!("{label}:{inner}"), Precedence::Prefix)
164            }
165        };
166
167        if precedence < parent {
168            Ok(format!("({text})"))
169        } else {
170            Ok(text)
171        }
172    }
173
174    fn emit_choice(
175        &mut self,
176        ordered: bool,
177        alternatives: &[GrammarExpr],
178    ) -> Result<String, GrammarEmitError> {
179        if alternatives.is_empty() {
180            return Err(unsupported_error(GrammarFormat::Peg, "empty Choice"));
181        }
182        if !ordered {
183            self.report
184                .add_lossy("Peggy treats unordered choice as ordered choice");
185        }
186
187        peg_choice_alternatives(ordered, alternatives)
188            .into_iter()
189            .map(|alternative| self.emit_expr(alternative, Precedence::Choice))
190            .collect::<Result<Vec<_>, _>>()
191            .map(|items| items.join(" / "))
192    }
193
194    fn emit_sequence(&mut self, items: &[GrammarExpr]) -> Result<String, GrammarEmitError> {
195        let mut emitted = Vec::new();
196        for item in items {
197            if matches!(item, GrammarExpr::Empty) {
198                continue;
199            }
200            let text = self.emit_expr(item, Precedence::Sequence)?;
201            if !text.is_empty() {
202                emitted.push(text);
203            }
204        }
205
206        if emitted.is_empty() {
207            Ok(quote_js_string(""))
208        } else {
209            Ok(emitted.join(" "))
210        }
211    }
212
213    fn emit_repeat(
214        &mut self,
215        expr: &GrammarExpr,
216        min: usize,
217        max: Option<usize>,
218    ) -> Result<String, GrammarEmitError> {
219        if max.is_some_and(|max| max < min) {
220            return Err(unsupported_error(
221                GrammarFormat::Peg,
222                format!("Repeat with min {min} greater than max {max:?}"),
223            ));
224        }
225
226        let inner = self.emit_expr(expr, Precedence::Postfix)?;
227        let suffix = match max {
228            Some(max) if min == max => format!("|{min}|"),
229            Some(max) => format!("|{min}..{max}|"),
230            None => format!("|{min}..|"),
231        };
232        Ok(format!("{inner}{suffix}"))
233    }
234
235    fn emit_label(&mut self, label: &str) -> String {
236        let emitted = sanitize_identifier(label);
237        if emitted != label {
238            self.report.add_lossy(format!(
239                "Peggy renamed capture label {label:?} to {emitted:?}"
240            ));
241        }
242        emitted
243    }
244}
245
246#[derive(Clone, Debug)]
247struct NamePlan {
248    names: BTreeMap<String, String>,
249}
250
251impl NamePlan {
252    fn new(grammar: &Grammar, report: &mut EmitReport) -> Self {
253        let defined_names = grammar
254            .rules()
255            .iter()
256            .map(|rule| rule.name().to_string())
257            .collect::<BTreeSet<_>>();
258        let mut symbols = Vec::new();
259        let mut seen = BTreeSet::new();
260
261        for rule in grammar.rules() {
262            push_unique_symbol(&mut symbols, &mut seen, rule.name());
263        }
264        for reference in grammar.referenced_nonterminals() {
265            push_unique_symbol(&mut symbols, &mut seen, &reference);
266        }
267
268        let mut used = BTreeSet::new();
269        let mut names = BTreeMap::new();
270        for symbol in symbols {
271            let base = sanitize_identifier(&symbol);
272            let emitted = unique_identifier(&base, &mut used);
273            if emitted != symbol {
274                report_name_change(report, &defined_names, &symbol, &emitted);
275            }
276            names.insert(symbol, emitted);
277        }
278
279        Self { names }
280    }
281
282    fn name_for(&self, source: &str) -> String {
283        self.names
284            .get(source)
285            .map_or_else(|| source.to_string(), Clone::clone)
286    }
287
288    fn rule_rename_comment(&self, source: &str) -> Option<String> {
289        let emitted = self.names.get(source)?;
290        (emitted != source).then(|| {
291            format!(
292                "// NOTE: rule {source:?} is emitted as {emitted:?} for Peggy identifier syntax."
293            )
294        })
295    }
296}
297
298fn push_unique_symbol(symbols: &mut Vec<String>, seen: &mut BTreeSet<String>, symbol: &str) {
299    if seen.insert(symbol.to_string()) {
300        symbols.push(symbol.to_string());
301    }
302}
303
304fn report_name_change(
305    report: &mut EmitReport,
306    defined_names: &BTreeSet<String>,
307    source: &str,
308    emitted: &str,
309) {
310    let kind = if defined_names.contains(source) {
311        "rule"
312    } else {
313        "non-terminal reference"
314    };
315    report.add_lossy(format!("Peggy renamed {kind} {source:?} to {emitted:?}"));
316}
317
318fn unique_identifier(base: &str, used: &mut BTreeSet<String>) -> String {
319    if used.insert(base.to_string()) {
320        return base.to_string();
321    }
322
323    let mut suffix = 1_usize;
324    loop {
325        let candidate = format!("{base}_{suffix}");
326        if used.insert(candidate.clone()) {
327            return candidate;
328        }
329        suffix = suffix.saturating_add(1);
330    }
331}
332
333fn sanitize_identifier(source: &str) -> String {
334    let mut output = String::new();
335    for character in source.chars() {
336        if output.is_empty() {
337            if is_identifier_start(character) {
338                output.push(character);
339            } else if is_identifier_continue(character) {
340                output.push('_');
341                output.push(character);
342            } else {
343                output.push('_');
344            }
345        } else if is_identifier_continue(character) {
346            output.push(character);
347        } else {
348            output.push('_');
349        }
350    }
351
352    if output.is_empty() {
353        output.push_str("ml");
354    }
355    if is_reserved_identifier(&output) {
356        output.insert_str(0, "ml_");
357    }
358    output
359}
360
361const fn is_identifier_start(character: char) -> bool {
362    character.is_ascii_alphabetic() || character == '_'
363}
364
365const fn is_identifier_continue(character: char) -> bool {
366    character.is_ascii_alphanumeric() || character == '_' || character == '$'
367}
368
369fn is_reserved_identifier(value: &str) -> bool {
370    matches!(
371        value,
372        "arguments"
373            | "await"
374            | "break"
375            | "case"
376            | "catch"
377            | "class"
378            | "const"
379            | "continue"
380            | "debugger"
381            | "default"
382            | "delete"
383            | "do"
384            | "else"
385            | "enum"
386            | "eval"
387            | "export"
388            | "extends"
389            | "false"
390            | "finally"
391            | "for"
392            | "function"
393            | "if"
394            | "implements"
395            | "import"
396            | "in"
397            | "instanceof"
398            | "interface"
399            | "let"
400            | "new"
401            | "null"
402            | "package"
403            | "private"
404            | "protected"
405            | "public"
406            | "return"
407            | "static"
408            | "super"
409            | "switch"
410            | "this"
411            | "throw"
412            | "true"
413            | "try"
414            | "typeof"
415            | "var"
416            | "void"
417            | "while"
418            | "with"
419            | "yield"
420    )
421}
422
423fn emit_char_range(start: char, end: char) -> Result<String, GrammarEmitError> {
424    validate_range("CharRange", start, end)?;
425    Ok(format!(
426        "[{}-{}]",
427        escaped_class_char(start),
428        escaped_class_char(end)
429    ))
430}
431
432fn emit_char_class(negated: bool, items: &[CharClassItem]) -> Result<String, GrammarEmitError> {
433    if items.is_empty() {
434        return Err(unsupported_error(GrammarFormat::Peg, "empty CharClass"));
435    }
436
437    let mut output = String::new();
438    output.push('[');
439    if negated {
440        output.push('^');
441    }
442    for item in items {
443        output.push_str(&emit_char_class_item(item)?);
444    }
445    output.push(']');
446    Ok(output)
447}
448
449fn emit_char_class_item(item: &CharClassItem) -> Result<String, GrammarEmitError> {
450    match item {
451        CharClassItem::Char(value) => Ok(escaped_class_char(*value)),
452        CharClassItem::Range(start, end) => {
453            validate_range("CharClass range", *start, *end)?;
454            Ok(format!(
455                "{}-{}",
456                escaped_class_char(*start),
457                escaped_class_char(*end)
458            ))
459        }
460    }
461}
462
463fn validate_range(construct: &str, start: char, end: char) -> Result<(), GrammarEmitError> {
464    if start > end {
465        return Err(unsupported_error(
466            GrammarFormat::Peg,
467            format!(
468                "{construct} has descending bounds U+{:04X}..=U+{:04X}",
469                start as u32, end as u32
470            ),
471        ));
472    }
473    Ok(())
474}
475
476fn apply_rule_kind(kind: RuleKind, body: String, report: &mut EmitReport) -> String {
477    match kind {
478        RuleKind::Normal => body,
479        RuleKind::Atomic => {
480            report.add_lossy("Peggy has no RuleKind::Atomic modifier; emitted a text() action");
481            format!("({body}) {{ return text(); }}")
482        }
483        RuleKind::Silent => {
484            report.add_lossy("Peggy has no RuleKind::Silent modifier; emitted a normal rule");
485            body
486        }
487        RuleKind::Token => {
488            report.add_lossy("Peggy has no RuleKind::Token modifier; emitted a text() action");
489            format!("({body}) {{ return text(); }}")
490        }
491    }
492}
493
494const fn rule_kind_comment(kind: RuleKind) -> Option<&'static str> {
495    match kind {
496        RuleKind::Normal => None,
497        RuleKind::Atomic => {
498            Some("// NOTE: Peggy has no atomic rule modifier; this rule returns its matched text.")
499        }
500        RuleKind::Silent => Some(
501            "// NOTE: Peggy has no silent rule modifier; this rule is emitted as a normal rule.",
502        ),
503        RuleKind::Token => {
504            Some("// NOTE: Peggy has no token rule modifier; this rule returns its matched text.")
505        }
506    }
507}
508
509fn push_doc_lines(lines: &mut Vec<String>, doc: &str) {
510    if doc.is_empty() {
511        lines.push("//".to_string());
512        return;
513    }
514    for line in doc.lines() {
515        if line.is_empty() {
516            lines.push("//".to_string());
517        } else {
518            lines.push(format!("// {line}"));
519        }
520    }
521}
522
523fn contains_unordered_choice(expr: &GrammarExpr) -> bool {
524    match expr {
525        GrammarExpr::Choice { ordered: false, .. } => true,
526        GrammarExpr::Choice { alternatives, .. } | GrammarExpr::Sequence(alternatives) => {
527            alternatives.iter().any(contains_unordered_choice)
528        }
529        GrammarExpr::Optional(expr)
530        | GrammarExpr::ZeroOrMore(expr)
531        | GrammarExpr::OneOrMore(expr)
532        | GrammarExpr::And(expr)
533        | GrammarExpr::Not(expr)
534        | GrammarExpr::Capture { expr, .. }
535        | GrammarExpr::Repeat { expr, .. } => contains_unordered_choice(expr),
536        GrammarExpr::Empty
537        | GrammarExpr::Terminal(_)
538        | GrammarExpr::TerminalInsensitive(_)
539        | GrammarExpr::CharRange(_, _)
540        | GrammarExpr::CharClass { .. }
541        | GrammarExpr::Feature(_)
542        | GrammarExpr::AnyChar
543        | GrammarExpr::NonTerminal(_) => false,
544    }
545}
546
547fn render_javascript_module(peggy_grammar: &str) -> String {
548    format!(
549        "import peggy from \"peggy\";\n\nconst GRAMMAR = {};\nexport const parser = peggy.generate(GRAMMAR);\n",
550        quote_js_string(peggy_grammar)
551    )
552}
553
554fn quote_js_string(value: &str) -> String {
555    let mut output = String::with_capacity(value.len() + 2);
556    output.push('"');
557    for character in value.chars() {
558        push_escaped_string_char(&mut output, character);
559    }
560    output.push('"');
561    output
562}
563
564fn escaped_class_char(character: char) -> String {
565    let mut output = String::new();
566    push_escaped_class_char(&mut output, character);
567    output
568}
569
570fn push_escaped_string_char(output: &mut String, character: char) {
571    match character {
572        '"' => output.push_str("\\\""),
573        '\\' => output.push_str("\\\\"),
574        '\n' => output.push_str("\\n"),
575        '\r' => output.push_str("\\r"),
576        '\t' => output.push_str("\\t"),
577        '\u{08}' => output.push_str("\\b"),
578        '\u{0c}' => output.push_str("\\f"),
579        '\u{2028}' => output.push_str("\\u2028"),
580        '\u{2029}' => output.push_str("\\u2029"),
581        character if character.is_ascii_control() => push_hex_escape(output, character),
582        character if !character.is_ascii() => push_unicode_escape(output, character),
583        character => output.push(character),
584    }
585}
586
587fn push_escaped_class_char(output: &mut String, character: char) {
588    match character {
589        '\\' => output.push_str("\\\\"),
590        '[' => output.push_str("\\["),
591        ']' => output.push_str("\\]"),
592        '-' => output.push_str("\\-"),
593        '^' => output.push_str("\\^"),
594        '\n' => output.push_str("\\n"),
595        '\r' => output.push_str("\\r"),
596        '\t' => output.push_str("\\t"),
597        '\u{08}' => output.push_str("\\b"),
598        '\u{0c}' => output.push_str("\\f"),
599        character if character.is_ascii_control() => push_hex_escape(output, character),
600        character if !character.is_ascii() => push_unicode_escape(output, character),
601        character => output.push(character),
602    }
603}
604
605fn push_hex_escape(output: &mut String, character: char) {
606    let code = character as u32;
607    let _ = write!(output, "\\x{code:02X}");
608}
609
610fn push_unicode_escape(output: &mut String, character: char) {
611    let code = character as u32;
612    if code <= 0xffff {
613        let _ = write!(output, "\\u{code:04X}");
614    } else {
615        let _ = write!(output, "\\u{{{code:X}}}");
616    }
617}
meta_language/grammar/emit/javascript.rs

meta_language/grammar/emit/
javascript.rs
