use std::{fmt::Write, sync::Arc};
use regast_syntax::{AnchorKind, AstKind, GroupKind, NodeId, Pattern, RepKind, Span};
use serde::{Deserialize, Serialize};
use serde_json::{Value as JsonValue, json};
use crate::{Disambiguation, IrId, IrKind, IrPool, Lowering, Value};
#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
#[serde(tag = "kind", rename_all = "snake_case")]
pub enum PtKind {
Empty,
Anchor {
anchor: AnchorKind,
},
Char {
c: char,
},
ClassChar {
c: char,
},
Concat,
AltTaken {
arm: u32,
},
Repeat {
count: u32,
},
Group {
index: Option<u32>,
name: Option<Box<str>>,
},
OptTaken {
taken: bool,
},
}
#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub struct PtNode {
pub kind: PtKind,
pub ast: NodeId,
pub span: Span,
pub children: Vec<Self>,
}
#[derive(Clone, Debug)]
pub struct ParseTree {
input: Arc<str>,
match_span: Span,
pattern: Arc<Pattern>,
root: PtNode,
}
impl ParseTree {
pub(crate) fn build(
pattern: Arc<Pattern>,
lowering: &Lowering,
pool: &IrPool,
value: Value,
input: &str,
disambiguation: Disambiguation,
) -> Self {
Self::build_at(
pattern,
lowering,
pool,
value,
input,
input,
0,
disambiguation,
)
}
#[allow(clippy::too_many_arguments)]
pub(crate) fn build_at(
pattern: Arc<Pattern>,
lowering: &Lowering,
pool: &IrPool,
value: Value,
matched: &str,
full_input: &str,
base: usize,
disambiguation: Disambiguation,
) -> Self {
let mut builder = TreeBuilder {
pattern: &pattern,
lowering,
pool,
input: full_input,
disambiguation,
offset: base,
};
let root = builder.build(pattern.root_id(), lowering.root, value);
debug_assert_eq!(builder.offset, base + matched.len());
Self {
input: Arc::from(full_input),
match_span: Span::new(base, base + matched.len()),
pattern,
root,
}
}
#[must_use]
pub fn flatten(&self) -> &str {
&self.input[self.match_span.start as usize..self.match_span.end as usize]
}
#[must_use]
pub const fn match_span(&self) -> Span {
self.match_span
}
#[must_use]
pub const fn root(&self) -> &PtNode {
&self.root
}
#[must_use]
pub fn pattern(&self) -> &Pattern {
&self.pattern
}
#[must_use]
pub fn walk(&self) -> ParseTreeWalk<'_> {
ParseTreeWalk {
stack: vec![&self.root],
}
}
#[must_use]
pub fn group_all(&self, index: u32) -> Vec<&PtNode> {
self.walk()
.filter(|node| matches!(node.kind, PtKind::Group { index: Some(i), .. } if i == index))
.collect()
}
#[must_use]
pub fn group_by_name_all(&self, name: &str) -> Vec<&PtNode> {
self.walk()
.filter(|node| {
matches!(&node.kind, PtKind::Group { name: Some(node_name), .. } if node_name.as_ref() == name)
})
.collect()
}
#[must_use]
pub fn captures_compat(&self) -> Vec<Option<Span>> {
let max = self.pattern.groups().len();
let mut captures = vec![None; max + 1];
captures[0] = Some(self.root.span);
for node in self.walk() {
if let PtKind::Group {
index: Some(index), ..
} = node.kind
{
captures[index as usize] = Some(node.span);
}
}
captures
}
#[must_use]
pub fn to_json(&self) -> JsonValue {
let mut root = node_json(&self.root);
let object = root.as_object_mut().expect("node JSON is an object");
object.insert("schema_version".into(), json!(1));
object.insert("input".into(), json!(self.input));
object.insert(
"match_span".into(),
json!([self.match_span.start, self.match_span.end]),
);
root
}
#[must_use]
pub fn to_sexpr(&self) -> String {
node_sexpr(&self.root)
}
#[must_use]
pub fn to_dot(&self) -> String {
let mut output = String::from("digraph parse_tree {\n node [shape=box];\n");
for cursor in self.pattern.root().walk() {
writeln!(
output,
" a{} [label=\"AST {}\\n{}\",shape=ellipse];",
cursor.id().0,
cursor.id().0,
escape_dot(cursor.text())
)
.expect("writing to String cannot fail");
for child in cursor.children() {
writeln!(output, " a{} -> a{};", cursor.id().0, child.id().0)
.expect("writing to String cannot fail");
}
}
let mut stack = vec![(&self.root, None)];
let mut next_id = 0_u32;
while let Some((node, parent)) = stack.pop() {
let id = next_id;
next_id += 1;
writeln!(
output,
" p{id} [label=\"{}\\n{}..{}\"] ;",
kind_name(&node.kind),
node.span.start,
node.span.end
)
.expect("writing to String cannot fail");
writeln!(output, " p{id} -> a{} [style=dotted];", node.ast.0)
.expect("writing to String cannot fail");
if let Some(parent) = parent {
writeln!(output, " p{parent} -> p{id};").expect("writing to String cannot fail");
}
stack.extend(node.children.iter().rev().map(|child| (child, Some(id))));
}
output.push_str("}\n");
output
}
}
pub struct ParseTreeWalk<'a> {
stack: Vec<&'a PtNode>,
}
impl<'a> Iterator for ParseTreeWalk<'a> {
type Item = &'a PtNode;
fn next(&mut self) -> Option<Self::Item> {
let node = self.stack.pop()?;
self.stack.extend(node.children.iter().rev());
Some(node)
}
}
struct TreeBuilder<'a> {
pattern: &'a Pattern,
lowering: &'a Lowering,
pool: &'a IrPool,
input: &'a str,
disambiguation: Disambiguation,
offset: usize,
}
impl TreeBuilder<'_> {
fn build(&mut self, ast: NodeId, ir: IrId, value: Value) -> PtNode {
let start = self.offset;
let (kind, children) = match &self.pattern.node(ast).kind {
AstKind::Empty => (PtKind::Empty, Vec::new()),
AstKind::Anchor { kind } => {
debug_assert!(matches!(value, Value::Empty));
(PtKind::Anchor { anchor: *kind }, Vec::new())
}
AstKind::Literal { .. } => self.character(&value, false),
AstKind::Dot | AstKind::Class { .. } => self.character(&value, true),
AstKind::Group { kind, inner } => self.group(kind, *inner, value),
AstKind::Concat { parts } => self.concat(parts, value),
AstKind::Alt { arms } => self.alternation(ir, arms, value),
AstKind::Repeat {
inner,
kind,
greedy,
} => self.repeat(*inner, *kind, *greedy, value),
};
debug_assert_eq!(
&self.input[start..self.offset],
flatten_children(&kind, &children)
);
PtNode {
kind,
ast,
span: Span::new(start, self.offset),
children,
}
}
fn character(&mut self, value: &Value, class: bool) -> (PtKind, Vec<PtNode>) {
let Value::Char(c) = value else {
unreachable!("literal or class must produce a character")
};
self.offset += c.len_utf8();
let kind = if class {
PtKind::ClassChar { c: *c }
} else {
PtKind::Char { c: *c }
};
(kind, Vec::new())
}
fn group(&mut self, kind: &GroupKind, inner: NodeId, value: Value) -> (PtKind, Vec<PtNode>) {
let child = self.build(inner, self.ir_for(inner), value);
let (index, name) = match kind {
GroupKind::Capture { index, name } => (Some(*index), name.clone()),
GroupKind::NonCapture => (None, None),
};
(PtKind::Group { index, name }, vec![child])
}
fn concat(&mut self, parts: &[NodeId], value: Value) -> (PtKind, Vec<PtNode>) {
let children = parts
.iter()
.zip(split_sequence(value, parts.len()))
.map(|(part, value)| self.build(*part, self.ir_for(*part), value))
.collect();
(PtKind::Concat, children)
}
fn alternation(&mut self, ir: IrId, arms: &[NodeId], value: Value) -> (PtKind, Vec<PtNode>) {
let (arm, value) = select_alt(self.pool, ir, value, arms.len());
let child_ast = arms[arm];
let child = self.build(child_ast, self.ir_for(child_ast), value);
(
PtKind::AltTaken {
arm: u32::try_from(arm).expect("arm index exceeds u32"),
},
vec![child],
)
}
fn repeat(
&mut self,
inner: NodeId,
kind: RepKind,
greedy: bool,
value: Value,
) -> (PtKind, Vec<PtNode>) {
let effective_greedy = self.disambiguation == Disambiguation::Posix || greedy;
let (taken, values) = repeat_values(value, kind, effective_greedy);
let children: Vec<_> = values
.into_iter()
.map(|value| self.build(inner, self.ir_for(inner), value))
.collect();
if matches!(kind, RepKind::ZeroOrOne) {
return (PtKind::OptTaken { taken }, children);
}
(
PtKind::Repeat {
count: u32::try_from(children.len()).expect("repeat count exceeds u32"),
},
children,
)
}
fn ir_for(&self, ast: NodeId) -> IrId {
self.lowering.ir_for(ast).expect("AST node was lowered")
}
}
fn split_sequence(mut value: Value, count: usize) -> Vec<Value> {
let mut values = Vec::with_capacity(count);
for index in 0..count {
if index + 1 == count {
values.push(value);
break;
}
let Value::Seq(left, right) = value else {
unreachable!("right-associated concatenation must produce Seq")
};
values.push(*left);
value = *right;
}
values
}
fn select_alt(pool: &IrPool, mut ir: IrId, mut value: Value, arm_count: usize) -> (usize, Value) {
for arm in 0..arm_count - 1 {
match value {
Value::Left(inner) => return (arm, *inner),
Value::Right(inner) => {
let IrKind::Alt(_, right, _, _) = pool.kind(ir) else {
unreachable!("right-associated alternation expected")
};
ir = *right;
value = *inner;
}
_ => unreachable!("alternation must produce a branch value"),
}
}
(arm_count - 1, value)
}
fn repeat_values(value: Value, kind: RepKind, greedy: bool) -> (bool, Vec<Value>) {
match kind {
RepKind::ZeroOrOne => {
optional_value(value, greedy).map_or((false, Vec::new()), |value| (true, vec![value]))
}
RepKind::ZeroOrMore => {
let Value::Stars(values) = value else {
unreachable!("star must produce Stars")
};
(!values.is_empty(), values)
}
RepKind::OneOrMore => {
let Value::Seq(first, rest) = value else {
unreachable!("plus must produce Seq")
};
let Value::Stars(mut values) = *rest else {
unreachable!("plus tail must produce Stars")
};
values.insert(0, *first);
(true, values)
}
RepKind::Range { min, max } => {
let values = range_values(value, min, max, greedy);
(!values.is_empty(), values)
}
}
}
fn range_values(mut value: Value, min: u32, max: Option<u32>, greedy: bool) -> Vec<Value> {
let optional_count = max.map(|max| max - min);
let suffix_exists = optional_count.is_none_or(|count| count > 0);
let mut values = Vec::new();
for required in 0..min {
if required + 1 == min && !suffix_exists {
values.push(value);
return values;
}
let Value::Seq(first, rest) = value else {
unreachable!("required range prefix must produce Seq")
};
values.push(*first);
value = *rest;
}
match optional_count {
None => {
let Value::Stars(rest) = value else {
unreachable!("unbounded range must end in Stars")
};
values.extend(rest);
}
Some(0) => debug_assert!(matches!(value, Value::Empty)),
Some(count) => {
for remaining in (1..=count).rev() {
let Some(taken) = optional_value(value, greedy) else {
break;
};
if remaining == 1 {
values.push(taken);
break;
}
let Value::Seq(first, rest) = taken else {
unreachable!("nested optional range must produce Seq")
};
values.push(*first);
value = *rest;
}
}
}
values
}
fn optional_value(value: Value, greedy: bool) -> Option<Value> {
match (greedy, value) {
(true, Value::Left(value)) | (false, Value::Right(value)) => Some(*value),
(true, Value::Right(value)) | (false, Value::Left(value))
if matches!(*value, Value::Empty) =>
{
None
}
_ => unreachable!("optional value has an invalid branch"),
}
}
fn flatten_children(kind: &PtKind, children: &[PtNode]) -> String {
match kind {
PtKind::Char { c } | PtKind::ClassChar { c } => c.to_string(),
PtKind::Empty | PtKind::Anchor { .. } => String::new(),
PtKind::Concat
| PtKind::AltTaken { .. }
| PtKind::Repeat { .. }
| PtKind::Group { .. }
| PtKind::OptTaken { .. } => children
.iter()
.map(|child| flatten_children(&child.kind, &child.children))
.collect(),
}
}
fn node_json(node: &PtNode) -> JsonValue {
let mut value = serde_json::to_value(&node.kind).expect("PtKind serialization cannot fail");
let object = value.as_object_mut().expect("tagged enum is an object");
object.insert("ast".into(), json!(node.ast.0));
object.insert("span".into(), json!([node.span.start, node.span.end]));
if !node.children.is_empty() {
object.insert(
"children".into(),
JsonValue::Array(node.children.iter().map(node_json).collect()),
);
}
value
}
fn node_sexpr(node: &PtNode) -> String {
let children = node
.children
.iter()
.map(node_sexpr)
.collect::<Vec<_>>()
.join(" ");
if children.is_empty() {
format!("({})", kind_name(&node.kind))
} else {
format!("({} {children})", kind_name(&node.kind))
}
}
fn kind_name(kind: &PtKind) -> &'static str {
match kind {
PtKind::Empty => "empty",
PtKind::Anchor { .. } => "anchor",
PtKind::Char { .. } => "char",
PtKind::ClassChar { .. } => "class_char",
PtKind::Concat => "concat",
PtKind::AltTaken { .. } => "alt_taken",
PtKind::Repeat { .. } => "repeat",
PtKind::Group { .. } => "group",
PtKind::OptTaken { .. } => "opt_taken",
}
}
fn escape_dot(text: &str) -> String {
text.replace('\\', "\\\\")
.replace('"', "\\\"")
.replace('\n', "\\n")
}
#[cfg(test)]
mod tests {
use regast_syntax::Pattern;
use super::*;
use crate::Matcher;
#[test]
fn exposes_every_repeated_group_and_alt_choice() {
let mut matcher = Matcher::new(
Pattern::parse("(a|b)*c").unwrap(),
Disambiguation::Posix,
100_000,
);
let tree = matcher.parse("abac").unwrap();
assert_eq!(tree.flatten(), "abac");
assert_eq!(tree.group_all(1).len(), 3);
let arms: Vec<_> = tree
.walk()
.filter_map(|node| match node.kind {
PtKind::AltTaken { arm } => Some(arm),
_ => None,
})
.collect();
assert_eq!(arms, [0, 1, 0]);
}
#[test]
fn range_repetitions_preserve_iteration_boundaries() {
for pattern in ["a{0}", "a{2}", "a{1,3}", "a{2,}"] {
let input = match pattern {
"a{0}" => "",
"a{2}" => "aa",
"a{1,3}" => "aaa",
_ => "aaaa",
};
let mut matcher = Matcher::new(
Pattern::parse(pattern).unwrap(),
Disambiguation::Posix,
100_000,
);
let tree = matcher.parse(input).unwrap();
assert_eq!(tree.flatten(), input);
assert_eq!(tree.root.children.len(), input.len(), "pattern {pattern}");
}
}
#[test]
fn exact_range_preserves_required_empty_iterations() {
for pattern in ["(?:){2}", "(?:){2}(?:)"] {
let mut matcher = Matcher::new(
Pattern::parse(pattern).unwrap(),
Disambiguation::Posix,
100_000,
);
let tree = matcher.parse("").unwrap();
let repeat = tree
.walk()
.find(|node| matches!(node.kind, PtKind::Repeat { .. }))
.unwrap();
assert!(matches!(repeat.kind, PtKind::Repeat { count: 2 }));
assert_eq!(repeat.children.len(), 2);
assert!(repeat.children.iter().all(|child| child.span.is_empty()));
}
}
#[test]
fn lazy_star_changes_greedy_mode_derivation() {
let pattern = Pattern::parse("a*?a*").unwrap();
let mut greedy = Matcher::new(pattern.clone(), Disambiguation::Greedy, 100_000);
let greedy_tree = greedy.parse("aa").unwrap();
assert!(matches!(
greedy_tree.root.children[0].kind,
PtKind::Repeat { count: 0 }
));
assert!(matches!(
greedy_tree.root.children[1].kind,
PtKind::Repeat { count: 2 }
));
let mut posix = Matcher::new(pattern, Disambiguation::Posix, 100_000);
let posix_tree = posix.parse("aa").unwrap();
assert!(matches!(
posix_tree.root.children[0].kind,
PtKind::Repeat { count: 2 }
));
}
}