1use std::{fmt::Write, sync::Arc};
2
3use regast_syntax::{AnchorKind, AstKind, GroupKind, NodeId, Pattern, RepKind, Span};
4use serde::{Deserialize, Serialize};
5use serde_json::{Value as JsonValue, json};
6
7use crate::{Disambiguation, IrId, IrKind, IrPool, Lowering, Value};
8
9#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
10#[serde(tag = "kind", rename_all = "snake_case")]
11pub enum PtKind {
12 Empty,
13 Anchor {
14 anchor: AnchorKind,
15 },
16 Char {
17 c: char,
18 },
19 ClassChar {
20 c: char,
21 },
22 Concat,
23 AltTaken {
24 arm: u32,
25 },
26 Repeat {
27 count: u32,
28 },
29 Group {
30 index: Option<u32>,
31 name: Option<Box<str>>,
32 },
33 OptTaken {
34 taken: bool,
35 },
36}
37
38#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
39pub struct PtNode {
40 pub kind: PtKind,
41 pub ast: NodeId,
42 pub span: Span,
43 pub children: Vec<Self>,
44}
45
46#[derive(Clone, Debug)]
47pub struct ParseTree {
48 input: Arc<str>,
49 match_span: Span,
50 pattern: Arc<Pattern>,
51 root: PtNode,
52}
53
54impl ParseTree {
55 pub(crate) fn build(
56 pattern: Arc<Pattern>,
57 lowering: &Lowering,
58 pool: &IrPool,
59 value: Value,
60 input: &str,
61 disambiguation: Disambiguation,
62 ) -> Self {
63 Self::build_at(
64 pattern,
65 lowering,
66 pool,
67 value,
68 input,
69 input,
70 0,
71 disambiguation,
72 )
73 }
74
75 #[allow(clippy::too_many_arguments)]
76 pub(crate) fn build_at(
77 pattern: Arc<Pattern>,
78 lowering: &Lowering,
79 pool: &IrPool,
80 value: Value,
81 matched: &str,
82 full_input: &str,
83 base: usize,
84 disambiguation: Disambiguation,
85 ) -> Self {
86 let mut builder = TreeBuilder {
87 pattern: &pattern,
88 lowering,
89 pool,
90 input: full_input,
91 disambiguation,
92 offset: base,
93 };
94 let root = builder.build(pattern.root_id(), lowering.root, value);
95 debug_assert_eq!(builder.offset, base + matched.len());
96 Self {
97 input: Arc::from(full_input),
98 match_span: Span::new(base, base + matched.len()),
99 pattern,
100 root,
101 }
102 }
103
104 #[must_use]
105 pub fn flatten(&self) -> &str {
106 &self.input[self.match_span.start as usize..self.match_span.end as usize]
107 }
108
109 #[must_use]
110 pub const fn match_span(&self) -> Span {
111 self.match_span
112 }
113
114 #[must_use]
115 pub const fn root(&self) -> &PtNode {
116 &self.root
117 }
118
119 #[must_use]
120 pub fn pattern(&self) -> &Pattern {
121 &self.pattern
122 }
123
124 #[must_use]
125 pub fn walk(&self) -> ParseTreeWalk<'_> {
126 ParseTreeWalk {
127 stack: vec![&self.root],
128 }
129 }
130
131 #[must_use]
132 pub fn group_all(&self, index: u32) -> Vec<&PtNode> {
133 self.walk()
134 .filter(|node| matches!(node.kind, PtKind::Group { index: Some(i), .. } if i == index))
135 .collect()
136 }
137
138 #[must_use]
139 pub fn group_by_name_all(&self, name: &str) -> Vec<&PtNode> {
140 self.walk()
141 .filter(|node| {
142 matches!(&node.kind, PtKind::Group { name: Some(node_name), .. } if node_name.as_ref() == name)
143 })
144 .collect()
145 }
146
147 #[must_use]
148 pub fn captures_compat(&self) -> Vec<Option<Span>> {
149 let max = self.pattern.groups().len();
150 let mut captures = vec![None; max + 1];
151 captures[0] = Some(self.root.span);
152 for node in self.walk() {
153 if let PtKind::Group {
154 index: Some(index), ..
155 } = node.kind
156 {
157 captures[index as usize] = Some(node.span);
158 }
159 }
160 captures
161 }
162
163 #[must_use]
164 pub fn to_json(&self) -> JsonValue {
170 let mut root = node_json(&self.root);
171 let object = root.as_object_mut().expect("node JSON is an object");
172 object.insert("schema_version".into(), json!(1));
173 object.insert("input".into(), json!(self.input));
174 object.insert(
175 "match_span".into(),
176 json!([self.match_span.start, self.match_span.end]),
177 );
178 root
179 }
180
181 #[must_use]
182 pub fn to_sexpr(&self) -> String {
183 node_sexpr(&self.root)
184 }
185
186 #[must_use]
187 pub fn to_dot(&self) -> String {
188 let mut output = String::from("digraph parse_tree {\n node [shape=box];\n");
189 for cursor in self.pattern.root().walk() {
190 writeln!(
191 output,
192 " a{} [label=\"AST {}\\n{}\",shape=ellipse];",
193 cursor.id().0,
194 cursor.id().0,
195 escape_dot(cursor.text())
196 )
197 .expect("writing to String cannot fail");
198 for child in cursor.children() {
199 writeln!(output, " a{} -> a{};", cursor.id().0, child.id().0)
200 .expect("writing to String cannot fail");
201 }
202 }
203 let mut stack = vec![(&self.root, None)];
204 let mut next_id = 0_u32;
205 while let Some((node, parent)) = stack.pop() {
206 let id = next_id;
207 next_id += 1;
208 writeln!(
209 output,
210 " p{id} [label=\"{}\\n{}..{}\"] ;",
211 kind_name(&node.kind),
212 node.span.start,
213 node.span.end
214 )
215 .expect("writing to String cannot fail");
216 writeln!(output, " p{id} -> a{} [style=dotted];", node.ast.0)
217 .expect("writing to String cannot fail");
218 if let Some(parent) = parent {
219 writeln!(output, " p{parent} -> p{id};").expect("writing to String cannot fail");
220 }
221 stack.extend(node.children.iter().rev().map(|child| (child, Some(id))));
222 }
223 output.push_str("}\n");
224 output
225 }
226}
227
228pub struct ParseTreeWalk<'a> {
229 stack: Vec<&'a PtNode>,
230}
231
232impl<'a> Iterator for ParseTreeWalk<'a> {
233 type Item = &'a PtNode;
234
235 fn next(&mut self) -> Option<Self::Item> {
236 let node = self.stack.pop()?;
237 self.stack.extend(node.children.iter().rev());
238 Some(node)
239 }
240}
241
242struct TreeBuilder<'a> {
243 pattern: &'a Pattern,
244 lowering: &'a Lowering,
245 pool: &'a IrPool,
246 input: &'a str,
247 disambiguation: Disambiguation,
248 offset: usize,
249}
250
251impl TreeBuilder<'_> {
252 fn build(&mut self, ast: NodeId, ir: IrId, value: Value) -> PtNode {
253 let start = self.offset;
254 let (kind, children) = match &self.pattern.node(ast).kind {
255 AstKind::Empty => (PtKind::Empty, Vec::new()),
256 AstKind::Anchor { kind } => {
257 debug_assert!(matches!(value, Value::Empty));
258 (PtKind::Anchor { anchor: *kind }, Vec::new())
259 }
260 AstKind::Literal { .. } => self.character(&value, false),
261 AstKind::Dot | AstKind::Class { .. } => self.character(&value, true),
262 AstKind::Group { kind, inner } => self.group(kind, *inner, value),
263 AstKind::Concat { parts } => self.concat(parts, value),
264 AstKind::Alt { arms } => self.alternation(ir, arms, value),
265 AstKind::Repeat {
266 inner,
267 kind,
268 greedy,
269 } => self.repeat(*inner, *kind, *greedy, value),
270 };
271 debug_assert_eq!(
272 &self.input[start..self.offset],
273 flatten_children(&kind, &children)
274 );
275 PtNode {
276 kind,
277 ast,
278 span: Span::new(start, self.offset),
279 children,
280 }
281 }
282
283 fn character(&mut self, value: &Value, class: bool) -> (PtKind, Vec<PtNode>) {
284 let Value::Char(c) = value else {
285 unreachable!("literal or class must produce a character")
286 };
287 self.offset += c.len_utf8();
288 let kind = if class {
289 PtKind::ClassChar { c: *c }
290 } else {
291 PtKind::Char { c: *c }
292 };
293 (kind, Vec::new())
294 }
295
296 fn group(&mut self, kind: &GroupKind, inner: NodeId, value: Value) -> (PtKind, Vec<PtNode>) {
297 let child = self.build(inner, self.ir_for(inner), value);
298 let (index, name) = match kind {
299 GroupKind::Capture { index, name } => (Some(*index), name.clone()),
300 GroupKind::NonCapture => (None, None),
301 };
302 (PtKind::Group { index, name }, vec![child])
303 }
304
305 fn concat(&mut self, parts: &[NodeId], value: Value) -> (PtKind, Vec<PtNode>) {
306 let children = parts
307 .iter()
308 .zip(split_sequence(value, parts.len()))
309 .map(|(part, value)| self.build(*part, self.ir_for(*part), value))
310 .collect();
311 (PtKind::Concat, children)
312 }
313
314 fn alternation(&mut self, ir: IrId, arms: &[NodeId], value: Value) -> (PtKind, Vec<PtNode>) {
315 let (arm, value) = select_alt(self.pool, ir, value, arms.len());
316 let child_ast = arms[arm];
317 let child = self.build(child_ast, self.ir_for(child_ast), value);
318 (
319 PtKind::AltTaken {
320 arm: u32::try_from(arm).expect("arm index exceeds u32"),
321 },
322 vec![child],
323 )
324 }
325
326 fn repeat(
327 &mut self,
328 inner: NodeId,
329 kind: RepKind,
330 greedy: bool,
331 value: Value,
332 ) -> (PtKind, Vec<PtNode>) {
333 let effective_greedy = self.disambiguation == Disambiguation::Posix || greedy;
334 let (taken, values) = repeat_values(value, kind, effective_greedy);
335 let children: Vec<_> = values
336 .into_iter()
337 .map(|value| self.build(inner, self.ir_for(inner), value))
338 .collect();
339 if matches!(kind, RepKind::ZeroOrOne) {
340 return (PtKind::OptTaken { taken }, children);
341 }
342 (
343 PtKind::Repeat {
344 count: u32::try_from(children.len()).expect("repeat count exceeds u32"),
345 },
346 children,
347 )
348 }
349
350 fn ir_for(&self, ast: NodeId) -> IrId {
351 self.lowering.ir_for(ast).expect("AST node was lowered")
352 }
353}
354
355fn split_sequence(mut value: Value, count: usize) -> Vec<Value> {
356 let mut values = Vec::with_capacity(count);
357 for index in 0..count {
358 if index + 1 == count {
359 values.push(value);
360 break;
361 }
362 let Value::Seq(left, right) = value else {
363 unreachable!("right-associated concatenation must produce Seq")
364 };
365 values.push(*left);
366 value = *right;
367 }
368 values
369}
370
371fn select_alt(pool: &IrPool, mut ir: IrId, mut value: Value, arm_count: usize) -> (usize, Value) {
372 for arm in 0..arm_count - 1 {
373 match value {
374 Value::Left(inner) => return (arm, *inner),
375 Value::Right(inner) => {
376 let IrKind::Alt(_, right, _, _) = pool.kind(ir) else {
377 unreachable!("right-associated alternation expected")
378 };
379 ir = *right;
380 value = *inner;
381 }
382 _ => unreachable!("alternation must produce a branch value"),
383 }
384 }
385 (arm_count - 1, value)
386}
387
388fn repeat_values(value: Value, kind: RepKind, greedy: bool) -> (bool, Vec<Value>) {
389 match kind {
390 RepKind::ZeroOrOne => {
391 optional_value(value, greedy).map_or((false, Vec::new()), |value| (true, vec![value]))
392 }
393 RepKind::ZeroOrMore => {
394 let Value::Stars(values) = value else {
395 unreachable!("star must produce Stars")
396 };
397 (!values.is_empty(), values)
398 }
399 RepKind::OneOrMore => {
400 let Value::Seq(first, rest) = value else {
401 unreachable!("plus must produce Seq")
402 };
403 let Value::Stars(mut values) = *rest else {
404 unreachable!("plus tail must produce Stars")
405 };
406 values.insert(0, *first);
407 (true, values)
408 }
409 RepKind::Range { min, max } => {
410 let values = range_values(value, min, max, greedy);
411 (!values.is_empty(), values)
412 }
413 }
414}
415
416fn range_values(mut value: Value, min: u32, max: Option<u32>, greedy: bool) -> Vec<Value> {
417 let optional_count = max.map(|max| max - min);
418 let suffix_exists = optional_count.is_none_or(|count| count > 0);
419 let mut values = Vec::new();
420 for required in 0..min {
421 if required + 1 == min && !suffix_exists {
422 values.push(value);
423 return values;
424 }
425 let Value::Seq(first, rest) = value else {
426 unreachable!("required range prefix must produce Seq")
427 };
428 values.push(*first);
429 value = *rest;
430 }
431 match optional_count {
432 None => {
433 let Value::Stars(rest) = value else {
434 unreachable!("unbounded range must end in Stars")
435 };
436 values.extend(rest);
437 }
438 Some(0) => debug_assert!(matches!(value, Value::Empty)),
439 Some(count) => {
440 for remaining in (1..=count).rev() {
441 let Some(taken) = optional_value(value, greedy) else {
442 break;
443 };
444 if remaining == 1 {
445 values.push(taken);
446 break;
447 }
448 let Value::Seq(first, rest) = taken else {
449 unreachable!("nested optional range must produce Seq")
450 };
451 values.push(*first);
452 value = *rest;
453 }
454 }
455 }
456 values
457}
458
459fn optional_value(value: Value, greedy: bool) -> Option<Value> {
460 match (greedy, value) {
461 (true, Value::Left(value)) | (false, Value::Right(value)) => Some(*value),
462 (true, Value::Right(value)) | (false, Value::Left(value))
463 if matches!(*value, Value::Empty) =>
464 {
465 None
466 }
467 _ => unreachable!("optional value has an invalid branch"),
468 }
469}
470
471fn flatten_children(kind: &PtKind, children: &[PtNode]) -> String {
472 match kind {
473 PtKind::Char { c } | PtKind::ClassChar { c } => c.to_string(),
474 PtKind::Empty | PtKind::Anchor { .. } => String::new(),
475 PtKind::Concat
476 | PtKind::AltTaken { .. }
477 | PtKind::Repeat { .. }
478 | PtKind::Group { .. }
479 | PtKind::OptTaken { .. } => children
480 .iter()
481 .map(|child| flatten_children(&child.kind, &child.children))
482 .collect(),
483 }
484}
485
486fn node_json(node: &PtNode) -> JsonValue {
487 let mut value = serde_json::to_value(&node.kind).expect("PtKind serialization cannot fail");
488 let object = value.as_object_mut().expect("tagged enum is an object");
489 object.insert("ast".into(), json!(node.ast.0));
490 object.insert("span".into(), json!([node.span.start, node.span.end]));
491 if !node.children.is_empty() {
492 object.insert(
493 "children".into(),
494 JsonValue::Array(node.children.iter().map(node_json).collect()),
495 );
496 }
497 value
498}
499
500fn node_sexpr(node: &PtNode) -> String {
501 let children = node
502 .children
503 .iter()
504 .map(node_sexpr)
505 .collect::<Vec<_>>()
506 .join(" ");
507 if children.is_empty() {
508 format!("({})", kind_name(&node.kind))
509 } else {
510 format!("({} {children})", kind_name(&node.kind))
511 }
512}
513
514fn kind_name(kind: &PtKind) -> &'static str {
515 match kind {
516 PtKind::Empty => "empty",
517 PtKind::Anchor { .. } => "anchor",
518 PtKind::Char { .. } => "char",
519 PtKind::ClassChar { .. } => "class_char",
520 PtKind::Concat => "concat",
521 PtKind::AltTaken { .. } => "alt_taken",
522 PtKind::Repeat { .. } => "repeat",
523 PtKind::Group { .. } => "group",
524 PtKind::OptTaken { .. } => "opt_taken",
525 }
526}
527
528fn escape_dot(text: &str) -> String {
529 text.replace('\\', "\\\\")
530 .replace('"', "\\\"")
531 .replace('\n', "\\n")
532}
533
534#[cfg(test)]
535mod tests {
536 use regast_syntax::Pattern;
537
538 use super::*;
539 use crate::Matcher;
540
541 #[test]
542 fn exposes_every_repeated_group_and_alt_choice() {
543 let mut matcher = Matcher::new(
544 Pattern::parse("(a|b)*c").unwrap(),
545 Disambiguation::Posix,
546 100_000,
547 );
548 let tree = matcher.parse("abac").unwrap();
549 assert_eq!(tree.flatten(), "abac");
550 assert_eq!(tree.group_all(1).len(), 3);
551 let arms: Vec<_> = tree
552 .walk()
553 .filter_map(|node| match node.kind {
554 PtKind::AltTaken { arm } => Some(arm),
555 _ => None,
556 })
557 .collect();
558 assert_eq!(arms, [0, 1, 0]);
559 }
560
561 #[test]
562 fn range_repetitions_preserve_iteration_boundaries() {
563 for pattern in ["a{0}", "a{2}", "a{1,3}", "a{2,}"] {
564 let input = match pattern {
565 "a{0}" => "",
566 "a{2}" => "aa",
567 "a{1,3}" => "aaa",
568 _ => "aaaa",
569 };
570 let mut matcher = Matcher::new(
571 Pattern::parse(pattern).unwrap(),
572 Disambiguation::Posix,
573 100_000,
574 );
575 let tree = matcher.parse(input).unwrap();
576 assert_eq!(tree.flatten(), input);
577 assert_eq!(tree.root.children.len(), input.len(), "pattern {pattern}");
578 }
579 }
580
581 #[test]
582 fn exact_range_preserves_required_empty_iterations() {
583 for pattern in ["(?:){2}", "(?:){2}(?:)"] {
584 let mut matcher = Matcher::new(
585 Pattern::parse(pattern).unwrap(),
586 Disambiguation::Posix,
587 100_000,
588 );
589 let tree = matcher.parse("").unwrap();
590 let repeat = tree
591 .walk()
592 .find(|node| matches!(node.kind, PtKind::Repeat { .. }))
593 .unwrap();
594 assert!(matches!(repeat.kind, PtKind::Repeat { count: 2 }));
595 assert_eq!(repeat.children.len(), 2);
596 assert!(repeat.children.iter().all(|child| child.span.is_empty()));
597 }
598 }
599
600 #[test]
601 fn lazy_star_changes_greedy_mode_derivation() {
602 let pattern = Pattern::parse("a*?a*").unwrap();
603 let mut greedy = Matcher::new(pattern.clone(), Disambiguation::Greedy, 100_000);
604 let greedy_tree = greedy.parse("aa").unwrap();
605 assert!(matches!(
606 greedy_tree.root.children[0].kind,
607 PtKind::Repeat { count: 0 }
608 ));
609 assert!(matches!(
610 greedy_tree.root.children[1].kind,
611 PtKind::Repeat { count: 2 }
612 ));
613
614 let mut posix = Matcher::new(pattern, Disambiguation::Posix, 100_000);
615 let posix_tree = posix.parse("aa").unwrap();
616 assert!(matches!(
617 posix_tree.root.children[0].kind,
618 PtKind::Repeat { count: 2 }
619 ));
620 }
621}