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