use crate::trigram::{Trigram, extract_trigrams};
pub fn extract_trigrams_from_regex(pattern: &str) -> Vec<Trigram> {
let literals = extract_literal_sequences(pattern);
if literals.is_empty() {
log::debug!(
"No literals found in regex pattern '{}', will fall back to full scan",
pattern
);
return vec![];
}
log::debug!(
"Extracted {} literal sequences from regex: {:?}",
literals.len(),
literals
);
let mut all_trigrams = Vec::new();
for literal in literals {
let trigrams = extract_trigrams(&literal);
all_trigrams.extend(trigrams);
}
all_trigrams.sort_unstable();
all_trigrams.dedup();
log::debug!(
"Extracted {} unique trigrams from regex pattern",
all_trigrams.len()
);
all_trigrams
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct RegexLiteral {
pub text: String,
pub case_insensitive: bool,
}
struct Frame {
ci: bool,
start: usize,
branch_start: usize,
branch_without_literal: bool,
}
impl Frame {
fn new(ci: bool, at: usize) -> Self {
Self {
ci,
start: at,
branch_start: at,
branch_without_literal: false,
}
}
}
pub fn extract_literals(pattern: &str) -> Vec<RegexLiteral> {
let mut out: Vec<RegexLiteral> = Vec::new();
let mut current = String::new();
let mut chars = pattern.chars().peekable();
let mut stack: Vec<Frame> = vec![Frame::new(false, 0)];
let mut verbose = false;
let mut last_group_start: Option<usize> = None;
let mut prev_was_quantifier = false;
fn flush(current: &mut String, out: &mut Vec<RegexLiteral>, ci: bool) {
if current.len() >= 3 {
out.push(RegexLiteral {
text: std::mem::take(current),
case_insensitive: ci,
});
} else {
current.clear();
}
}
while let Some(ch) = chars.next() {
let ci = stack.last().map(|f| f.ci).unwrap_or(false);
let mut group_just_closed = None;
let mut is_quantifier = false;
match ch {
'?' if prev_was_quantifier => {
is_quantifier = true;
}
'*' | '?' => {
is_quantifier = true;
match last_group_start {
Some(start) => out.truncate(start),
None => {
current.pop();
}
}
flush(&mut current, &mut out, ci);
}
'+' => {
is_quantifier = true;
flush(&mut current, &mut out, ci);
}
'.' | '^' | '$' => {
flush(&mut current, &mut out, ci);
}
'[' => {
flush(&mut current, &mut out, ci);
let mut depth = 1usize;
let mut first = true;
while let Some(c) = chars.next() {
match c {
'\\' => {
chars.next();
}
'^' if first => continue,
']' if first => {}
'[' => depth += 1,
']' => {
depth -= 1;
if depth == 0 {
break;
}
}
_ => {}
}
first = false;
}
}
']' => {
flush(&mut current, &mut out, ci);
}
'|' => {
flush(&mut current, &mut out, ci);
let frame = stack.last_mut().expect("root frame");
if out.len() == frame.branch_start {
frame.branch_without_literal = true;
}
frame.branch_start = out.len();
}
'(' => {
flush(&mut current, &mut out, ci);
if chars.peek() == Some(&'?') {
chars.next(); match chars.peek().copied() {
Some(':') => {
chars.next();
stack.push(Frame::new(ci, out.len()));
}
Some('P') | Some('<') => {
for c in chars.by_ref() {
if c == '>' {
break;
}
}
stack.push(Frame::new(ci, out.len()));
}
Some(c) if c.is_ascii_alphabetic() || c == '-' => {
let mut negate = false;
let mut new_ci = ci;
let mut scoped = false;
for c in chars.by_ref() {
match c {
'-' => negate = true,
'i' => new_ci = !negate,
'x' => {
if !negate {
verbose = true;
}
}
':' => {
scoped = true;
break;
}
')' => break,
_ => {}
}
}
if scoped {
stack.push(Frame::new(new_ci, out.len()));
} else if let Some(frame) = stack.last_mut() {
frame.ci = new_ci;
}
}
_ => {
for c in chars.by_ref() {
if c == ')' {
break;
}
}
}
}
} else {
stack.push(Frame::new(ci, out.len()));
}
}
')' => {
flush(&mut current, &mut out, ci);
if stack.len() > 1 {
let frame = stack.pop().expect("non-root frame");
let last_branch_has_literal = out.len() > frame.branch_start;
if frame.branch_without_literal || !last_branch_has_literal {
out.truncate(frame.start);
}
group_just_closed = Some(frame.start);
}
}
'{' => {
is_quantifier = true;
let mut body = String::new();
while let Some(&next_ch) = chars.peek() {
chars.next();
if next_ch == '}' {
break;
}
body.push(next_ch);
}
let min_repeats = body
.split(',')
.next()
.and_then(|n| n.trim().parse::<u32>().ok());
if min_repeats == Some(0) {
match last_group_start {
Some(start) => out.truncate(start),
None => {
current.pop();
}
}
}
flush(&mut current, &mut out, ci);
}
'}' => {
flush(&mut current, &mut out, ci);
}
'\\' => {
match chars.next() {
Some(c) if c.is_ascii_alphanumeric() => {
flush(&mut current, &mut out, ci);
match c {
'x' | 'u' | 'U' | 'p' | 'P' => {
if chars.peek() == Some(&'{') {
for c in chars.by_ref() {
if c == '}' {
break;
}
}
} else {
let n = match c {
'x' => 2,
'u' => 4,
'U' => 8,
_ => 1,
};
for _ in 0..n {
chars.next();
}
}
}
_ => {}
}
}
Some(c) => current.push(c),
None => flush(&mut current, &mut out, ci),
}
}
_ => {
current.push(ch);
}
}
last_group_start = group_just_closed;
prev_was_quantifier = is_quantifier;
}
let ci = stack.last().map(|f| f.ci).unwrap_or(false);
flush(&mut current, &mut out, ci);
let root = &stack[0];
if root.branch_without_literal || out.len() == root.branch_start {
out.clear();
}
if verbose {
log::debug!("Verbose (x) flag in pattern, cannot use trigram optimization");
return vec![];
}
out
}
pub fn extract_literal_sequences(pattern: &str) -> Vec<String> {
extract_literals(pattern)
.into_iter()
.map(|l| l.text)
.collect()
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_extract_literal_sequences_simple() {
let sequences = extract_literal_sequences("hello");
assert_eq!(sequences, vec!["hello"]);
}
#[test]
fn test_extract_literal_sequences_with_wildcard() {
let sequences = extract_literal_sequences("fn.*test");
assert_eq!(sequences, vec!["test"]);
}
#[test]
fn test_extract_literal_sequences_multiple() {
let sequences = extract_literal_sequences("class.*Controller");
assert_eq!(sequences, vec!["class", "Controller"]);
}
#[test]
fn test_extract_literal_sequences_no_literals() {
let sequences = extract_literal_sequences(".*");
assert!(sequences.is_empty());
}
#[test]
fn test_extract_literal_sequences_short_literals() {
let sequences = extract_literal_sequences("fn.*test");
assert_eq!(sequences, vec!["test"]);
}
#[test]
fn test_extract_literal_sequences_escaped() {
let sequences = extract_literal_sequences("test\\.txt");
assert_eq!(sequences, vec!["test.txt"]);
}
#[test]
fn test_extract_literal_sequences_whitespace_escape() {
let sequences = extract_literal_sequences("fn\\s+extract");
assert_eq!(sequences, vec!["extract"]);
}
#[test]
fn test_extract_literal_sequences_word_boundary() {
let sequences = extract_literal_sequences("\\bListUsersController\\b");
assert_eq!(sequences, vec!["ListUsersController"]);
}
#[test]
fn test_extract_trigrams_simple_literal() {
let trigrams = extract_trigrams_from_regex("extract");
assert_eq!(trigrams.len(), 5);
}
#[test]
fn test_extract_trigrams_with_wildcard() {
let trigrams = extract_trigrams_from_regex("fn.*test");
assert_eq!(trigrams.len(), 2);
}
#[test]
fn test_extract_trigrams_multiple_literals() {
let trigrams = extract_trigrams_from_regex("class.*Controller");
assert!(trigrams.len() >= 10); }
#[test]
fn test_extract_trigrams_no_literals() {
let trigrams = extract_trigrams_from_regex(".*");
assert!(trigrams.is_empty());
}
#[test]
fn test_extract_trigrams_complex_pattern() {
let trigrams = extract_trigrams_from_regex("(function|const)");
assert!(trigrams.len() >= 6);
}
#[test]
fn test_extract_literal_sequences_alternation() {
let sequences = extract_literal_sequences("(SymbolWriter|ContentWriter)");
assert_eq!(sequences, vec!["SymbolWriter", "ContentWriter"]);
}
#[test]
fn test_extract_literal_sequences_three_way_alternation() {
let sequences = extract_literal_sequences("(Indexer|QueryEngine|CacheManager)");
assert_eq!(sequences, vec!["Indexer", "QueryEngine", "CacheManager"]);
}
#[test]
fn test_extract_literal_sequences_case_insensitive_flag() {
assert_eq!(extract_literals("(?i)queryengine"), vec![ci("queryengine")]);
assert_eq!(
extract_literal_sequences("(?i)queryengine"),
vec!["queryengine"]
);
}
fn ci(text: &str) -> RegexLiteral {
RegexLiteral {
text: text.into(),
case_insensitive: true,
}
}
fn cs(text: &str) -> RegexLiteral {
RegexLiteral {
text: text.into(),
case_insensitive: false,
}
}
#[test]
fn test_extract_literals_scoped_case_flag() {
assert_eq!(extract_literals("(?i:foo)bar"), vec![ci("foo"), cs("bar")]);
assert_eq!(
extract_literals("(?i)foo(?-i)bar"),
vec![ci("foo"), cs("bar")]
);
assert_eq!(extract_literals("((?i)foo)bar"), vec![ci("foo"), cs("bar")]);
assert_eq!(extract_literals("(?i-s:foo)"), vec![ci("foo")]);
assert_eq!(extract_literals("(?s-i:foo)"), vec![cs("foo")]);
assert_eq!(extract_literals("(?i)straße"), vec![ci("straße")]);
}
#[test]
fn test_extract_literals_alternation_branch_without_literal() {
assert_eq!(extract_literal_sequences("(abc|de)f"), Vec::<String>::new());
assert_eq!(extract_literal_sequences("(abc|de)fgh"), vec!["fgh"]);
assert_eq!(extract_literal_sequences("abc|de"), Vec::<String>::new());
assert_eq!(extract_literal_sequences("abc|"), Vec::<String>::new());
assert_eq!(extract_literal_sequences("(abc|def)"), vec!["abc", "def"]);
assert_eq!(
extract_literal_sequences("(?i:abc)|de"),
Vec::<String>::new()
);
assert_eq!(extract_literal_sequences("((abc|def)|x)yyy"), vec!["yyy"]);
}
#[test]
fn test_extract_literals_character_class_is_not_literal() {
assert_eq!(extract_literal_sequences("[abc]def"), vec!["def"]);
assert_eq!(extract_literal_sequences("[^abc]def"), vec!["def"]);
assert_eq!(extract_literal_sequences("[]abc]def"), vec!["def"]);
assert_eq!(extract_literal_sequences("[[:alpha:]]def"), vec!["def"]);
assert_eq!(extract_literal_sequences(r"[\]abc]def"), vec!["def"]);
assert_eq!(
extract_literal_sequences("abc[xyz]?def"),
vec!["abc", "def"]
);
}
#[test]
fn test_extract_literals_unknown_escapes_break_sequence() {
assert_eq!(extract_literal_sequences(r"abc\p{Lu}"), vec!["abc"]);
assert_eq!(extract_literal_sequences(r"abc\pLdef"), vec!["abc", "def"]);
assert_eq!(extract_literal_sequences(r"abc\x41def"), vec!["abc", "def"]);
assert_eq!(
extract_literal_sequences(r"abc\x{41}def"),
vec!["abc", "def"]
);
assert_eq!(
extract_literal_sequences(r"abc\u{1F600}def"),
vec!["abc", "def"]
);
assert_eq!(extract_literal_sequences(r"\Aabc\z"), vec!["abc"]);
assert_eq!(extract_literal_sequences(r"abc\-def"), vec!["abc-def"]);
assert_eq!(extract_literal_sequences(r"abc\/def"), vec!["abc/def"]);
}
#[test]
fn test_extract_literals_verbose_flag_forces_scan() {
assert_eq!(
extract_literal_sequences("(?x) abc # comment"),
Vec::<String>::new()
);
assert_eq!(extract_literal_sequences("(?ix:abc)"), Vec::<String>::new());
}
#[test]
fn test_extract_literals_named_group() {
assert_eq!(
extract_literal_sequences("(?P<name>abc)def"),
vec!["abc", "def"]
);
assert_eq!(extract_literal_sequences("(?<name>abc)?def"), vec!["def"]);
}
#[test]
fn test_extract_literal_sequences_multiline_flag() {
let sequences = extract_literal_sequences("(?m)^test");
assert_eq!(sequences, vec!["test"]);
}
#[test]
fn test_extract_literal_sequences_non_capturing_group() {
let sequences = extract_literal_sequences("(?:test|func)");
assert_eq!(sequences, vec!["test", "func"]);
}
#[test]
fn test_extract_literal_sequences_optional_last_atom() {
assert_eq!(extract_literal_sequences("foobar?"), vec!["fooba"]);
assert_eq!(extract_literal_sequences("abcd*"), vec!["abc"]);
assert_eq!(extract_literal_sequences("abcd+"), vec!["abcd"]);
assert_eq!(extract_literal_sequences("ab{0,2}c"), Vec::<String>::new());
assert_eq!(
extract_literal_sequences("test{0}word"),
vec!["tes", "word"]
);
assert_eq!(
extract_literal_sequences("test{1,5}word"),
vec!["test", "word"]
);
assert_eq!(extract_literal_sequences("foobar(baz)?"), vec!["foobar"]);
assert_eq!(extract_literal_sequences("foobar(baz)*"), vec!["foobar"]);
assert_eq!(
extract_literal_sequences("foobar(baz){0,3}"),
vec!["foobar"]
);
assert_eq!(
extract_literal_sequences("foobar(baz)+"),
vec!["foobar", "baz"]
);
assert_eq!(extract_literal_sequences("abcd+?"), vec!["abcd"]);
assert_eq!(extract_literal_sequences("abcd*?x"), vec!["abc"]);
}
#[test]
fn test_extract_literal_sequences_quantifier_no_false_literal() {
let sequences = extract_literal_sequences("a{2,3}test");
assert_eq!(sequences, vec!["test"]);
assert!(!sequences.contains(&"2,3".to_string()));
}
#[test]
fn test_extract_literal_sequences_quantifier_range() {
let sequences = extract_literal_sequences("test{1,5}word");
assert_eq!(sequences, vec!["test", "word"]);
assert!(!sequences.contains(&"1,5".to_string()));
}
#[test]
fn test_extract_literal_sequences_quantifier_exact() {
let sequences = extract_literal_sequences("test{3}word");
assert_eq!(sequences, vec!["test", "word"]);
assert!(!sequences.contains(&"3".to_string()));
}
#[test]
fn test_extract_literal_sequences_combined_flags() {
assert_eq!(extract_literals("(?im)test"), vec![ci("test")]);
assert_eq!(extract_literals("(?mi)^test"), vec![ci("test")]);
}
#[test]
fn test_extract_literal_sequences_flag_before_literal() {
assert_eq!(
extract_literals("(?i)test.*function"),
vec![ci("test"), ci("function")]
);
}
}