use alloc::boxed::Box;
use alloc::string::String;
use alloc::vec::Vec;
use core::fmt::Write;
#[derive(Debug, Clone)]
#[cfg_attr(feature = "fuzz-gen", derive(arbitrary::Arbitrary))]
pub enum RegexNode {
Literal(LitChar),
Dot,
Anchor(Anchor),
Escape(EscClass),
LineBreak, Class(CharClass),
Concat(Vec<RegexNode>),
Alt(Vec<RegexNode>),
Group { kind: GroupKind, body: Box<RegexNode> },
Quantified { body: Box<RegexNode>, quant: Quantifier },
Lookaround { ahead: bool, neg: bool, body: Box<RegexNode> },
Backref(BackrefIdx),
Quote(Vec<LitChar>), InlineFlags(FlagSet), FlagGroup { flags: FlagSet, body: Box<RegexNode> }, }
#[derive(Debug, Clone, Copy)]
#[cfg_attr(feature = "fuzz-gen", derive(arbitrary::Arbitrary))]
pub enum LitChar {
Ascii(AsciiPrintable),
Newline,
Tab,
Cr,
Unicode(UnicodeChar),
}
#[derive(Debug, Clone, Copy)]
#[cfg_attr(feature = "fuzz-gen", derive(arbitrary::Arbitrary))]
pub enum AsciiPrintable {
A, B, C, D, E, F, G, H,
Zero, One, Two, Three,
Space, Comma, Colon, Underscore, Slash, Hyphen, At,
OpenAngle, CloseAngle, Equals, Plus, Tilde,
}
#[derive(Debug, Clone, Copy)]
#[cfg_attr(feature = "fuzz-gen", derive(arbitrary::Arbitrary))]
pub enum UnicodeChar {
LatinEAcute, LatinSsharp, GreekAlpha, GreekCapAlpha, CyrillicYa, Cjk, Snowman, EmojiGrin, }
#[derive(Debug, Clone, Copy)]
#[cfg_attr(feature = "fuzz-gen", derive(arbitrary::Arbitrary))]
pub enum Anchor {
StartLine, EndLine, StartInput, EndInputZ, EndInputBigZ, WordBoundary, NonWordBoundary, PrevMatchEnd, }
#[derive(Debug, Clone, Copy)]
#[cfg_attr(feature = "fuzz-gen", derive(arbitrary::Arbitrary))]
pub enum EscClass {
Digit, NonDigit,
Word, NonWord,
Space, NonSpace,
HSpace, NonHSpace,
VSpace, NonVSpace,
UnicodeLetter, UnicodeNotLetter, UnicodeDigit, UnicodePunct, JavaUpperCase, JavaWhitespace, InGreek, IsLatin, }
#[derive(Debug, Clone)]
#[cfg_attr(feature = "fuzz-gen", derive(arbitrary::Arbitrary))]
pub struct CharClass {
pub negated: bool,
pub items: Vec<ClassItem>,
}
#[derive(Debug, Clone)]
#[cfg_attr(feature = "fuzz-gen", derive(arbitrary::Arbitrary))]
pub enum ClassItem {
Single(LitChar),
Range(AsciiPrintable, AsciiPrintable), Esc(EscClass),
Nested(Box<CharClass>),
Intersect(Box<CharClass>, Box<CharClass>),
}
#[derive(Debug, Clone)]
#[cfg_attr(feature = "fuzz-gen", derive(arbitrary::Arbitrary))]
pub enum GroupKind {
Capturing,
NonCapturing,
Atomic,
Named(GroupName),
}
#[derive(Debug, Clone, Copy)]
#[cfg_attr(feature = "fuzz-gen", derive(arbitrary::Arbitrary))]
pub enum GroupName { Foo, Bar, Baz, X1, Y2 }
#[derive(Debug, Clone)]
#[cfg_attr(feature = "fuzz-gen", derive(arbitrary::Arbitrary))]
pub struct Quantifier {
pub kind: QuantKind,
pub mode: QuantMode,
}
#[derive(Debug, Clone, Copy)]
#[cfg_attr(feature = "fuzz-gen", derive(arbitrary::Arbitrary))]
pub enum QuantKind {
Star,
Plus,
Opt,
Exact(SmallCount),
AtLeast(SmallCount),
Range(SmallCount, SmallCount),
}
#[derive(Debug, Clone, Copy)]
#[cfg_attr(feature = "fuzz-gen", derive(arbitrary::Arbitrary))]
pub enum SmallCount { Zero, One, Two, Three, Four, Five }
impl SmallCount {
fn val(self) -> u32 {
match self {
SmallCount::Zero => 0, SmallCount::One => 1, SmallCount::Two => 2,
SmallCount::Three => 3, SmallCount::Four => 4, SmallCount::Five => 5,
}
}
}
#[derive(Debug, Clone, Copy)]
#[cfg_attr(feature = "fuzz-gen", derive(arbitrary::Arbitrary))]
pub enum QuantMode { Greedy, Reluctant, Possessive }
#[derive(Debug, Clone, Copy)]
#[cfg_attr(feature = "fuzz-gen", derive(arbitrary::Arbitrary))]
pub enum BackrefIdx { B1, B2, B3 }
#[derive(Debug, Clone, Copy, Default)]
#[cfg_attr(feature = "fuzz-gen", derive(arbitrary::Arbitrary))]
pub struct FlagSet {
pub i: bool,
pub m: bool,
pub s: bool,
pub u: bool,
}
impl LitChar {
pub fn to_char(self) -> char {
match self {
LitChar::Ascii(a) => a.to_char(),
LitChar::Newline => '\n',
LitChar::Tab => '\t',
LitChar::Cr => '\r',
LitChar::Unicode(u) => u.to_char(),
}
}
}
impl AsciiPrintable {
pub fn to_char(self) -> char {
match self {
AsciiPrintable::A => 'a', AsciiPrintable::B => 'b', AsciiPrintable::C => 'c',
AsciiPrintable::D => 'd', AsciiPrintable::E => 'e', AsciiPrintable::F => 'f',
AsciiPrintable::G => 'g', AsciiPrintable::H => 'h',
AsciiPrintable::Zero => '0', AsciiPrintable::One => '1',
AsciiPrintable::Two => '2', AsciiPrintable::Three => '3',
AsciiPrintable::Space => ' ', AsciiPrintable::Comma => ',',
AsciiPrintable::Colon => ':', AsciiPrintable::Underscore => '_',
AsciiPrintable::Slash => '/', AsciiPrintable::Hyphen => '-',
AsciiPrintable::At => '@',
AsciiPrintable::OpenAngle => '<', AsciiPrintable::CloseAngle => '>',
AsciiPrintable::Equals => '=', AsciiPrintable::Plus => '+',
AsciiPrintable::Tilde => '~',
}
}
}
impl UnicodeChar {
pub fn to_char(self) -> char {
match self {
UnicodeChar::LatinEAcute => 'é',
UnicodeChar::LatinSsharp => 'ß',
UnicodeChar::GreekAlpha => 'α',
UnicodeChar::GreekCapAlpha => 'Α',
UnicodeChar::CyrillicYa => 'я',
UnicodeChar::Cjk => '中',
UnicodeChar::Snowman => '☃',
UnicodeChar::EmojiGrin => '\u{1F600}',
}
}
}
impl GroupName {
pub fn name(self) -> &'static str {
match self {
GroupName::Foo => "foo", GroupName::Bar => "bar", GroupName::Baz => "baz",
GroupName::X1 => "x1", GroupName::Y2 => "y2",
}
}
}
impl FlagSet {
fn to_chars(self) -> String {
let mut s = String::new();
if self.i { s.push('i'); }
if self.m { s.push('m'); }
if self.s { s.push('s'); }
if self.u { s.push('u'); }
s
}
pub fn to_flags_str(self) -> String { self.to_chars() }
}
pub fn render(node: &RegexNode) -> String {
let mut out = String::new();
render_into(node, &mut out);
out
}
fn render_into(node: &RegexNode, out: &mut String) {
match node {
RegexNode::Literal(c) => write_literal(c.to_char(), out),
RegexNode::Dot => out.push('.'),
RegexNode::Anchor(a) => out.push_str(anchor_str(*a)),
RegexNode::Escape(e) => out.push_str(esc_str(*e)),
RegexNode::LineBreak => out.push_str("\\R"),
RegexNode::Class(c) => render_class(c, out),
RegexNode::Concat(items) => {
for n in items { render_atom(n, out); }
}
RegexNode::Alt(branches) => {
if branches.is_empty() {
out.push_str("(?:)");
return;
}
for (i, b) in branches.iter().enumerate() {
if i > 0 { out.push('|'); }
render_branch(b, out);
}
}
RegexNode::Group { kind, body } => {
out.push('(');
match kind {
GroupKind::Capturing => {}
GroupKind::NonCapturing => out.push_str("?:"),
GroupKind::Atomic => out.push_str("?>"),
GroupKind::Named(n) => {
out.push_str("?<");
out.push_str(n.name());
out.push('>');
}
}
render_branch(body, out);
out.push(')');
}
RegexNode::Quantified { body, quant } => {
render_atom(body, out);
quant_str(quant, out);
}
RegexNode::Lookaround { ahead, neg, body } => {
out.push('(');
match (ahead, neg) {
(true, false) => out.push_str("?="),
(true, true) => out.push_str("?!"),
(false, false) => out.push_str("?<="),
(false, true) => out.push_str("?<!"),
}
render_branch(body, out);
out.push(')');
}
RegexNode::Backref(b) => {
let n = match b { BackrefIdx::B1 => 1, BackrefIdx::B2 => 2, BackrefIdx::B3 => 3 };
write!(out, "\\{}", n).unwrap();
}
RegexNode::Quote(chars) => {
out.push_str("\\Q");
for c in chars {
let ch = c.to_char();
if ch == '\\' {
out.push('\\');
} else {
out.push(ch);
}
}
out.push_str("\\E");
}
RegexNode::InlineFlags(f) => {
let s = f.to_chars();
if !s.is_empty() {
out.push_str("(?");
out.push_str(&s);
out.push(')');
}
}
RegexNode::FlagGroup { flags, body } => {
let s = flags.to_chars();
if s.is_empty() {
out.push_str("(?:");
} else {
out.push_str("(?");
out.push_str(&s);
out.push(':');
}
render_branch(body, out);
out.push(')');
}
}
}
fn render_branch(node: &RegexNode, out: &mut String) {
render_into(node, out);
}
fn render_atom(node: &RegexNode, out: &mut String) {
match node {
RegexNode::Alt(_) | RegexNode::Concat(_) => {
out.push_str("(?:");
render_into(node, out);
out.push(')');
}
RegexNode::Quantified { .. } => {
out.push_str("(?:");
render_into(node, out);
out.push(')');
}
_ => render_into(node, out),
}
}
fn anchor_str(a: Anchor) -> &'static str {
match a {
Anchor::StartLine => "^", Anchor::EndLine => "$",
Anchor::StartInput => "\\A", Anchor::EndInputZ => "\\z",
Anchor::EndInputBigZ => "\\Z",
Anchor::WordBoundary => "\\b", Anchor::NonWordBoundary => "\\B",
Anchor::PrevMatchEnd => "\\G",
}
}
fn esc_str(e: EscClass) -> &'static str {
match e {
EscClass::Digit => "\\d", EscClass::NonDigit => "\\D",
EscClass::Word => "\\w", EscClass::NonWord => "\\W",
EscClass::Space => "\\s", EscClass::NonSpace => "\\S",
EscClass::HSpace => "\\h", EscClass::NonHSpace => "\\H",
EscClass::VSpace => "\\v", EscClass::NonVSpace => "\\V",
EscClass::UnicodeLetter => "\\p{L}",
EscClass::UnicodeNotLetter => "\\P{L}",
EscClass::UnicodeDigit => "\\p{Nd}",
EscClass::UnicodePunct => "\\p{P}",
EscClass::JavaUpperCase => "\\p{javaUpperCase}",
EscClass::JavaWhitespace => "\\p{javaWhitespace}",
EscClass::InGreek => "\\p{InGreek}",
EscClass::IsLatin => "\\p{IsLatin}",
}
}
fn quant_str(q: &Quantifier, out: &mut String) {
match q.kind {
QuantKind::Star => out.push('*'),
QuantKind::Plus => out.push('+'),
QuantKind::Opt => out.push('?'),
QuantKind::Exact(n) => write!(out, "{{{}}}", n.val()).unwrap(),
QuantKind::AtLeast(n) => write!(out, "{{{},}}", n.val()).unwrap(),
QuantKind::Range(lo, hi) => {
let (a, b) = if lo.val() <= hi.val() { (lo.val(), hi.val()) } else { (hi.val(), lo.val()) };
write!(out, "{{{},{}}}", a, b).unwrap();
}
}
match q.mode {
QuantMode::Greedy => {}
QuantMode::Reluctant => out.push('?'),
QuantMode::Possessive => out.push('+'),
}
}
fn write_literal(c: char, out: &mut String) {
match c {
'.' | '*' | '+' | '?' | '(' | ')' | '[' | ']' | '{' | '}' |
'\\' | '|' | '^' | '$' => {
out.push('\\'); out.push(c);
}
'\n' => out.push_str("\\n"),
'\r' => out.push_str("\\r"),
'\t' => out.push_str("\\t"),
_ => out.push(c),
}
}
fn write_class_char(c: char, out: &mut String) {
match c {
'\\' | ']' | '[' | '^' | '-' | '&' => {
out.push('\\'); out.push(c);
}
'\n' => out.push_str("\\n"),
'\r' => out.push_str("\\r"),
'\t' => out.push_str("\\t"),
_ => out.push(c),
}
}
fn render_class(c: &CharClass, out: &mut String) {
out.push('[');
if c.negated { out.push('^'); }
if c.items.is_empty() {
out.push_str("\\w");
} else {
for it in &c.items {
render_class_item(it, out);
}
}
out.push(']');
}
fn render_class_item(it: &ClassItem, out: &mut String) {
match it {
ClassItem::Single(c) => write_class_char(c.to_char(), out),
ClassItem::Range(lo, hi) => {
let (a, b) = (lo.to_char(), hi.to_char());
let (lo_c, hi_c) = if (a as u32) <= (b as u32) { (a, b) } else { (b, a) };
write_class_char(lo_c, out);
out.push('-');
write_class_char(hi_c, out);
}
ClassItem::Esc(e) => out.push_str(esc_str(*e)),
ClassItem::Nested(c) => render_class(c, out),
ClassItem::Intersect(a, b) => {
render_class(a, out);
out.push_str("&&");
render_class(b, out);
}
}
}
#[cfg(all(test, feature = "fuzz-gen"))]
mod tests {
use super::*;
use arbitrary::{Arbitrary, Unstructured};
use alloc::vec;
fn fill(state: &mut u64, buf: &mut [u8]) {
for chunk in buf.chunks_mut(8) {
*state = state.wrapping_add(0x9E3779B97F4A7C15);
let mut z = *state;
z = (z ^ (z >> 30)).wrapping_mul(0xBF58476D1CE4E5B9);
z = (z ^ (z >> 27)).wrapping_mul(0x94D049BB133111EB);
let bytes = (z ^ (z >> 31)).to_le_bytes();
for (i, b) in chunk.iter_mut().enumerate() { *b = bytes[i]; }
}
}
#[test]
fn fuzz_render_covers_all_variants() {
let mut state: u64 = 0xDEADBEEFCAFEBABE;
let mut buf = vec![0u8; 1024];
let mut produced = 0usize;
for _ in 0..50_000 {
fill(&mut state, &mut buf);
let mut u = Unstructured::new(&buf);
if let Ok(node) = RegexNode::arbitrary(&mut u) {
let s = render(&node);
let _ = s;
produced += 1;
}
}
assert!(produced > 1000, "expected >1k successful renders, got {produced}");
}
#[test]
fn flag_set_to_flags_str_alias() {
let f = FlagSet { i: true, m: false, s: true, u: false };
assert_eq!(f.to_flags_str(), "is");
}
#[test]
fn render_each_top_level_variant() {
let cases: alloc::vec::Vec<RegexNode> = vec![
RegexNode::Literal(LitChar::Cr),
RegexNode::Dot,
RegexNode::Anchor(Anchor::WordBoundary),
RegexNode::Escape(EscClass::Digit),
RegexNode::LineBreak,
RegexNode::Concat(vec![RegexNode::Dot, RegexNode::Dot]),
RegexNode::Alt(vec![RegexNode::Dot, RegexNode::Literal(LitChar::Cr)]),
RegexNode::Alt(vec![]),
RegexNode::Group {
kind: GroupKind::Capturing,
body: Box::new(RegexNode::Dot),
},
RegexNode::Group {
kind: GroupKind::NonCapturing,
body: Box::new(RegexNode::Dot),
},
RegexNode::Group {
kind: GroupKind::Atomic,
body: Box::new(RegexNode::Dot),
},
RegexNode::Group {
kind: GroupKind::Named(GroupName::Foo),
body: Box::new(RegexNode::Dot),
},
RegexNode::Quantified {
body: Box::new(RegexNode::Dot),
quant: Quantifier { kind: QuantKind::Star, mode: QuantMode::Greedy },
},
RegexNode::Lookaround {
ahead: true, neg: false,
body: Box::new(RegexNode::Dot),
},
RegexNode::Lookaround {
ahead: false, neg: true,
body: Box::new(RegexNode::Dot),
},
RegexNode::Backref(BackrefIdx::B1),
RegexNode::Quote(vec![LitChar::Cr]),
RegexNode::InlineFlags(FlagSet { i: true, m: false, s: true, u: false }),
RegexNode::InlineFlags(FlagSet { i: false, m: false, s: false, u: false }),
RegexNode::FlagGroup {
flags: FlagSet { i: true, m: false, s: false, u: false },
body: Box::new(RegexNode::Dot),
},
RegexNode::FlagGroup {
flags: FlagSet { i: false, m: false, s: false, u: false },
body: Box::new(RegexNode::Dot),
},
];
for n in &cases {
let _ = render(n);
}
}
}