1use std::collections::{BTreeMap, BTreeSet};
2use std::fmt::Write as _;
3
4use crate::grammar::{CharClassItem, Grammar, GrammarExpr, GrammarFormat, RuleKind};
5
6use super::{EmitReport, GrammarEmitError, ordered_rules, unsupported_error};
7
8const FORMAT: GrammarFormat = GrammarFormat::TreeSitter;
9
10pub fn emit_tree_sitter_grammar_js(grammar: &Grammar) -> Result<String, GrammarEmitError> {
16 emit_tree_sitter_grammar_js_with_report(grammar).map(|(source, _report)| source)
17}
18
19pub fn emit_tree_sitter_grammar_js_with_report(
27 grammar: &Grammar,
28) -> Result<(String, EmitReport), GrammarEmitError> {
29 let mut report = EmitReport::default();
30 let names = NamePlan::new(grammar, &mut report);
31 let mut emitter = TreeSitterEmitter { report, names };
32
33 let mut output = String::new();
34 output.push_str("module.exports = grammar({\n");
35 let _ = writeln!(
36 output,
37 " name: {},",
38 quote_js_string(&emitter.names.grammar_name)
39 );
40
41 let inline_rules = inline_rules(grammar, &emitter.names, &mut emitter.report);
42 if !inline_rules.is_empty() {
43 output.push_str(" inline: $ => [\n");
44 for name in inline_rules {
45 let _ = writeln!(output, " $.{name},");
46 }
47 output.push_str(" ],\n");
48 }
49
50 output.push_str(" rules: {\n");
51 for rule in ordered_rules(grammar) {
52 if let Some(doc) = rule.doc() {
53 push_doc_lines(&mut output, doc);
54 }
55 let body = emitter.emit_expr(rule.expr())?;
56 let body = apply_rule_kind(rule.kind(), body);
57 let name = emitter.names.name_for(rule.name());
58 let _ = writeln!(output, " {name}: $ => {body},");
59 }
60 output.push_str(" },\n");
61 output.push_str("});\n");
62
63 Ok((output, emitter.report))
64}
65
66#[derive(Clone, Debug)]
67struct TreeSitterEmitter {
68 report: EmitReport,
69 names: NamePlan,
70}
71
72impl TreeSitterEmitter {
73 fn emit_expr(&mut self, expr: &GrammarExpr) -> Result<String, GrammarEmitError> {
74 match expr {
75 GrammarExpr::Empty => Ok("blank()".to_string()),
76 GrammarExpr::Terminal(value) => Ok(quote_js_string(value)),
77 GrammarExpr::TerminalInsensitive(value) => {
78 self.report.add_lossy(format!(
79 "tree-sitter expands case-insensitive terminal {value:?} to a regex"
80 ));
81 Ok(emit_case_insensitive_terminal(value))
82 }
83 GrammarExpr::CharRange(start, end) => emit_char_range(*start, *end),
84 GrammarExpr::CharClass { negated, items } => emit_char_class(*negated, items),
85 GrammarExpr::AnyChar => Ok("/./".to_string()),
86 GrammarExpr::NonTerminal(name) => Ok(format!("$.{}", self.names.name_for(name))),
87 GrammarExpr::Choice {
88 ordered,
89 alternatives,
90 } => self.emit_choice(*ordered, alternatives),
91 GrammarExpr::Sequence(items) => self.emit_sequence(items),
92 GrammarExpr::Optional(inner) => {
93 let inner = self.emit_expr(inner)?;
94 Ok(format!("optional({inner})"))
95 }
96 GrammarExpr::ZeroOrMore(inner) => {
97 let inner = self.emit_expr(inner)?;
98 Ok(format!("repeat({inner})"))
99 }
100 GrammarExpr::OneOrMore(inner) => {
101 let inner = self.emit_expr(inner)?;
102 Ok(format!("repeat1({inner})"))
103 }
104 GrammarExpr::Repeat { expr, min, max } => self.emit_repeat(expr, *min, *max),
105 GrammarExpr::And(_) | GrammarExpr::Not(_) => {
106 Err(unsupported_error(FORMAT, "predicate"))
107 }
108 GrammarExpr::Capture { label, expr } => self.emit_capture(label.as_deref(), expr),
109 GrammarExpr::Feature(feature) => Err(unsupported_error(FORMAT, feature.head())),
110 }
111 }
112
113 fn emit_choice(
114 &mut self,
115 ordered: bool,
116 alternatives: &[GrammarExpr],
117 ) -> Result<String, GrammarEmitError> {
118 if alternatives.is_empty() {
119 return Err(unsupported_error(FORMAT, "empty Choice"));
120 }
121 if ordered {
122 self.report
123 .add_lossy("tree-sitter treats ordered choice as unordered choice");
124 }
125
126 alternatives
127 .iter()
128 .map(|alternative| self.emit_expr(alternative))
129 .collect::<Result<Vec<_>, _>>()
130 .map(|items| format!("choice({})", items.join(", ")))
131 }
132
133 fn emit_sequence(&mut self, items: &[GrammarExpr]) -> Result<String, GrammarEmitError> {
134 let mut emitted = Vec::new();
135 for item in items {
136 if matches!(item, GrammarExpr::Empty) {
137 continue;
138 }
139 emitted.push(self.emit_expr(item)?);
140 }
141
142 Ok(match emitted.len() {
143 0 => "blank()".to_string(),
144 _ => format!("seq({})", emitted.join(", ")),
145 })
146 }
147
148 fn emit_repeat(
149 &mut self,
150 expr: &GrammarExpr,
151 min: usize,
152 max: Option<usize>,
153 ) -> Result<String, GrammarEmitError> {
154 if max.is_some_and(|max| max < min) {
155 return Err(unsupported_error(
156 FORMAT,
157 format!("Repeat with min {min} greater than max {max:?}"),
158 ));
159 }
160
161 let inner = self.emit_expr(expr)?;
162 match (min, max) {
163 (0, None) => Ok(format!("repeat({inner})")),
164 (1, None) => Ok(format!("repeat1({inner})")),
165 _ => {
166 self.report.add_lossy(format!(
167 "tree-sitter desugared Repeat with min {min} and max {max:?}"
168 ));
169 Ok(desugar_repeat(&inner, min, max))
170 }
171 }
172 }
173
174 fn emit_capture(
175 &mut self,
176 label: Option<&str>,
177 expr: &GrammarExpr,
178 ) -> Result<String, GrammarEmitError> {
179 let Some(label) = label else {
180 self.report
181 .add_lossy("tree-sitter dropped anonymous capture");
182 return self.emit_expr(expr);
183 };
184
185 let inner = self.emit_expr(expr)?;
186 if let Some(value) = label.strip_prefix("prec=") {
187 return Ok(format!("prec({}, {inner})", emit_precedence_value(value)));
188 }
189 if let Some(value) = label.strip_prefix("prec_left=") {
190 return Ok(format!(
191 "prec.left({}, {inner})",
192 emit_precedence_value(value)
193 ));
194 }
195 if let Some(value) = label.strip_prefix("prec_right=") {
196 return Ok(format!(
197 "prec.right({}, {inner})",
198 emit_precedence_value(value)
199 ));
200 }
201 if let Some(value) = label.strip_prefix("prec_dynamic=") {
202 return Ok(format!(
203 "prec.dynamic({}, {inner})",
204 emit_precedence_value(value)
205 ));
206 }
207 if let Some(value) = label.strip_prefix("alias:") {
208 return Ok(format!("alias({inner}, {})", emit_alias_target(value)));
209 }
210
211 match label {
212 "token" => Ok(format!("token({inner})")),
213 "immediate_token" => Ok(format!("token.immediate({inner})")),
214 _ => Ok(format!("field({}, {inner})", quote_js_string(label))),
215 }
216 }
217}
218
219fn desugar_repeat(inner: &str, min: usize, max: Option<usize>) -> String {
220 let mut parts = vec![inner.to_string(); min];
221 match max {
222 Some(max) => {
223 parts.extend((min..max).map(|_| format!("optional({inner})")));
224 }
225 None => parts.push(format!("repeat({inner})")),
226 }
227
228 match parts.len() {
229 0 => "blank()".to_string(),
230 1 => parts.remove(0),
231 _ => format!("seq({})", parts.join(", ")),
232 }
233}
234
235fn apply_rule_kind(kind: RuleKind, body: String) -> String {
236 match kind {
237 RuleKind::Normal | RuleKind::Silent => body,
238 RuleKind::Atomic | RuleKind::Token => format!("token({body})"),
239 }
240}
241
242fn inline_rules(grammar: &Grammar, names: &NamePlan, report: &mut EmitReport) -> Vec<String> {
243 let rules = ordered_rules(grammar)
244 .into_iter()
245 .filter(|rule| rule.kind() == RuleKind::Silent)
246 .map(|rule| names.name_for(rule.name()))
247 .collect::<Vec<_>>();
248
249 for name in &rules {
250 report.add_lossy(format!(
251 "tree-sitter emits RuleKind::Silent rule {name:?} in the inline list"
252 ));
253 }
254
255 rules
256}
257
258#[derive(Clone, Debug)]
259struct NamePlan {
260 names: BTreeMap<String, String>,
261 grammar_name: String,
262}
263
264impl NamePlan {
265 fn new(grammar: &Grammar, report: &mut EmitReport) -> Self {
266 let defined_names = grammar
267 .rules()
268 .iter()
269 .map(|rule| rule.name().to_string())
270 .collect::<BTreeSet<_>>();
271 let mut symbols = Vec::new();
272 let mut seen = BTreeSet::new();
273
274 for rule in grammar.rules() {
275 push_unique_symbol(&mut symbols, &mut seen, rule.name());
276 }
277 for reference in grammar.referenced_nonterminals() {
278 push_unique_symbol(&mut symbols, &mut seen, &reference);
279 }
280
281 let mut used = BTreeSet::new();
282 let mut names = BTreeMap::new();
283 for symbol in symbols {
284 let base = sanitize_identifier(&symbol);
285 let emitted = unique_identifier(&base, &mut used);
286 if emitted != symbol {
287 report_name_change(report, &defined_names, &symbol, &emitted);
288 }
289 names.insert(symbol, emitted);
290 }
291
292 let grammar_name = grammar
293 .start_rule()
294 .or_else(|| grammar.rules().first())
295 .map_or_else(|| "grammar".to_string(), |rule| rule.name().to_string());
296 let grammar_name = names
297 .get(&grammar_name)
298 .cloned()
299 .unwrap_or_else(|| sanitize_identifier(&grammar_name));
300
301 Self {
302 names,
303 grammar_name,
304 }
305 }
306
307 fn name_for(&self, source: &str) -> String {
308 self.names
309 .get(source)
310 .map_or_else(|| sanitize_identifier(source), Clone::clone)
311 }
312}
313
314fn push_unique_symbol(symbols: &mut Vec<String>, seen: &mut BTreeSet<String>, symbol: &str) {
315 if seen.insert(symbol.to_string()) {
316 symbols.push(symbol.to_string());
317 }
318}
319
320fn report_name_change(
321 report: &mut EmitReport,
322 defined_names: &BTreeSet<String>,
323 source: &str,
324 emitted: &str,
325) {
326 let kind = if defined_names.contains(source) {
327 "rule"
328 } else {
329 "non-terminal reference"
330 };
331 report.add_lossy(format!(
332 "tree-sitter renamed {kind} {source:?} to {emitted:?}"
333 ));
334}
335
336fn unique_identifier(base: &str, used: &mut BTreeSet<String>) -> String {
337 if used.insert(base.to_string()) {
338 return base.to_string();
339 }
340
341 for suffix in 1_usize.. {
342 let candidate = format!("{base}_{suffix}");
343 if used.insert(candidate.clone()) {
344 return candidate;
345 }
346 }
347 unreachable!("unbounded suffix search must eventually find a free identifier")
348}
349
350fn sanitize_identifier(source: &str) -> String {
351 let mut output = String::new();
352 for character in source.chars() {
353 if output.is_empty() {
354 if is_identifier_start(character) {
355 output.push(character);
356 } else if is_identifier_continue(character) {
357 output.push('_');
358 output.push(character);
359 } else {
360 output.push('_');
361 }
362 } else if is_identifier_continue(character) {
363 output.push(character);
364 } else {
365 output.push('_');
366 }
367 }
368
369 if output.is_empty() {
370 output.push_str("grammar");
371 }
372 if is_reserved_identifier(&output) {
373 output.insert_str(0, "ml_");
374 }
375 output
376}
377
378const fn is_identifier_start(character: char) -> bool {
379 character.is_ascii_alphabetic() || character == '_'
380}
381
382const fn is_identifier_continue(character: char) -> bool {
383 character.is_ascii_alphanumeric() || character == '_'
384}
385
386fn is_reserved_identifier(value: &str) -> bool {
387 matches!(
388 value,
389 "arguments"
390 | "await"
391 | "break"
392 | "case"
393 | "catch"
394 | "class"
395 | "const"
396 | "continue"
397 | "debugger"
398 | "default"
399 | "delete"
400 | "do"
401 | "else"
402 | "enum"
403 | "eval"
404 | "export"
405 | "extends"
406 | "false"
407 | "finally"
408 | "for"
409 | "function"
410 | "if"
411 | "implements"
412 | "import"
413 | "in"
414 | "instanceof"
415 | "interface"
416 | "let"
417 | "new"
418 | "null"
419 | "package"
420 | "private"
421 | "protected"
422 | "public"
423 | "return"
424 | "static"
425 | "super"
426 | "switch"
427 | "this"
428 | "throw"
429 | "true"
430 | "try"
431 | "typeof"
432 | "var"
433 | "void"
434 | "while"
435 | "with"
436 | "yield"
437 )
438}
439
440fn emit_case_insensitive_terminal(value: &str) -> String {
441 if value.is_empty() {
442 return quote_js_string("");
443 }
444
445 let mut pattern = String::new();
446 for character in value.chars() {
447 if character.is_ascii_alphabetic() {
448 pattern.push('[');
449 push_escaped_class_char(&mut pattern, character.to_ascii_uppercase());
450 push_escaped_class_char(&mut pattern, character.to_ascii_lowercase());
451 pattern.push(']');
452 } else {
453 push_escaped_regex_char(&mut pattern, character);
454 }
455 }
456 regex_literal(&pattern)
457}
458
459fn emit_char_range(start: char, end: char) -> Result<String, GrammarEmitError> {
460 validate_range("CharRange", start, end)?;
461 let mut pattern = String::new();
462 pattern.push('[');
463 push_escaped_class_char(&mut pattern, start);
464 pattern.push('-');
465 push_escaped_class_char(&mut pattern, end);
466 pattern.push(']');
467 Ok(regex_literal(&pattern))
468}
469
470fn emit_char_class(negated: bool, items: &[CharClassItem]) -> Result<String, GrammarEmitError> {
471 if items.is_empty() {
472 return Err(unsupported_error(FORMAT, "empty CharClass"));
473 }
474
475 let mut pattern = String::new();
476 pattern.push('[');
477 if negated {
478 pattern.push('^');
479 }
480 for item in items {
481 push_char_class_item(&mut pattern, item)?;
482 }
483 pattern.push(']');
484 Ok(regex_literal(&pattern))
485}
486
487fn push_char_class_item(output: &mut String, item: &CharClassItem) -> Result<(), GrammarEmitError> {
488 match item {
489 CharClassItem::Char(value) => push_escaped_class_char(output, *value),
490 CharClassItem::Range(start, end) => {
491 validate_range("CharClass range", *start, *end)?;
492 push_escaped_class_char(output, *start);
493 output.push('-');
494 push_escaped_class_char(output, *end);
495 }
496 }
497 Ok(())
498}
499
500fn validate_range(construct: &str, start: char, end: char) -> Result<(), GrammarEmitError> {
501 if start > end {
502 return Err(unsupported_error(
503 FORMAT,
504 format!(
505 "{construct} has descending bounds U+{:04X}..=U+{:04X}",
506 start as u32, end as u32
507 ),
508 ));
509 }
510 Ok(())
511}
512
513fn emit_precedence_value(value: &str) -> String {
514 if value.parse::<i64>().is_ok() {
515 value.to_string()
516 } else {
517 quote_js_string(value)
518 }
519}
520
521fn emit_alias_target(value: &str) -> String {
522 let identifier = sanitize_identifier(value);
523 if identifier == value {
524 format!("$.{identifier}")
525 } else {
526 quote_js_string(value)
527 }
528}
529
530fn regex_literal(pattern: &str) -> String {
531 format!("/{pattern}/")
532}
533
534fn quote_js_string(value: &str) -> String {
535 let mut output = String::with_capacity(value.len() + 2);
536 output.push('"');
537 for character in value.chars() {
538 push_escaped_string_char(&mut output, character);
539 }
540 output.push('"');
541 output
542}
543
544fn push_escaped_string_char(output: &mut String, character: char) {
545 match character {
546 '"' => output.push_str("\\\""),
547 '\\' => output.push_str("\\\\"),
548 '\n' => output.push_str("\\n"),
549 '\r' => output.push_str("\\r"),
550 '\t' => output.push_str("\\t"),
551 '\u{08}' => output.push_str("\\b"),
552 '\u{0c}' => output.push_str("\\f"),
553 '\u{2028}' => output.push_str("\\u2028"),
554 '\u{2029}' => output.push_str("\\u2029"),
555 character if character.is_ascii_control() => push_hex_escape(output, character),
556 character if !character.is_ascii() => push_unicode_escape(output, character),
557 character => output.push(character),
558 }
559}
560
561fn push_escaped_regex_char(output: &mut String, character: char) {
562 match character {
563 '/' => output.push_str("\\/"),
564 '\\' => output.push_str("\\\\"),
565 '^' | '$' | '.' | '*' | '+' | '?' | '(' | ')' | '[' | ']' | '{' | '}' | '|' => {
566 output.push('\\');
567 output.push(character);
568 }
569 '\n' => output.push_str("\\n"),
570 '\r' => output.push_str("\\r"),
571 '\t' => output.push_str("\\t"),
572 '\u{08}' => output.push_str("\\b"),
573 '\u{0c}' => output.push_str("\\f"),
574 '\u{2028}' => output.push_str("\\u2028"),
575 '\u{2029}' => output.push_str("\\u2029"),
576 character if character.is_ascii_control() => push_hex_escape(output, character),
577 character if !character.is_ascii() => push_unicode_escape(output, character),
578 character => output.push(character),
579 }
580}
581
582fn push_escaped_class_char(output: &mut String, character: char) {
583 match character {
584 '/' => output.push_str("\\/"),
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 '\u{2028}' => output.push_str("\\u2028"),
596 '\u{2029}' => output.push_str("\\u2029"),
597 character if character.is_ascii_control() => push_hex_escape(output, character),
598 character if !character.is_ascii() => push_unicode_escape(output, character),
599 character => output.push(character),
600 }
601}
602
603fn push_hex_escape(output: &mut String, character: char) {
604 let code = character as u32;
605 let _ = write!(output, "\\x{code:02X}");
606}
607
608fn push_unicode_escape(output: &mut String, character: char) {
609 let code = character as u32;
610 if code <= 0xffff {
611 let _ = write!(output, "\\u{code:04X}");
612 } else {
613 for unit in character.encode_utf16(&mut [0; 2]) {
614 let _ = write!(output, "\\u{unit:04X}");
615 }
616 }
617}
618
619fn push_doc_lines(output: &mut String, doc: &str) {
620 if doc.is_empty() {
621 output.push_str(" //\n");
622 return;
623 }
624 for line in doc.lines() {
625 if line.is_empty() {
626 output.push_str(" //\n");
627 } else {
628 let _ = writeln!(output, " // {line}");
629 }
630 }
631}