diff options
| author | Onur Gündüz <ogunduz@gmail.com> | 2026-09-29 14:11:15 +0200 |
|---|---|---|
| committer | Onur Gündüz <ogunduz@gmail.com> | 2026-09-29 14:11:15 +0200 |
| commit | ed979a49940b3054468b48ad1a9f97fab5a2fd81 (patch) | |
| tree | 0c5bd82595b6b83f77ddc327690558a43c273309 | |
| parent | 171c32577ef504ec3b8ea09bb8df00fd6be7a13d (diff) | |
| download | ele-ed979a49940b3054468b48ad1a9f97fab5a2fd81.tar.gz ele-ed979a49940b3054468b48ad1a9f97fab5a2fd81.zip | |
Use linear-time matching for overlapping phrases
| -rw-r--r-- | src/compiled.rs | 2 | ||||
| -rw-r--r-- | src/eval.rs | 56 | ||||
| -rw-r--r-- | tests/compiled_tests.rs | 64 |
3 files changed, 110 insertions, 12 deletions
diff --git a/src/compiled.rs b/src/compiled.rs index 45c7dc3..c9f5ab8 100644 --- a/src/compiled.rs +++ b/src/compiled.rs @@ -211,7 +211,7 @@ impl<'a> Predicate<'a> { negated: op == CompareOp::NotMatchesRegexp, } } - _ => Self::Literal(op, Literal::new(literal_text(expr)?)), + _ => Self::Literal(op, Literal::new(literal_text(expr)?, op)), }) } diff --git a/src/eval.rs b/src/eval.rs index e338900..512d7e5 100644 --- a/src/eval.rs +++ b/src/eval.rs @@ -233,10 +233,11 @@ pub(crate) struct Literal<'a> { folded: Option<String>, number: Option<Value<'static>>, boolean: Option<bool>, + word_prefix: Vec<usize>, } impl<'a> Literal<'a> { - pub(crate) fn new(text: Cow<'a, str>) -> Self { + pub(crate) fn new(text: Cow<'a, str>, op: CompareOp) -> Self { let number = if let Ok(value) = text.parse::<i64>() { Some(Value::Int(value)) } else if let Ok(value) = text.parse::<u64>() { @@ -255,7 +256,14 @@ impl<'a> Literal<'a> { Cow::Borrowed(_) => None, Cow::Owned(text) => Some(text), }; - Self { text, folded, number, boolean } + let word_prefix = if op == CompareOp::Has + && !text.starts_with('*') && !text.ends_with('*') + { + prefix_lengths(folded.as_deref().unwrap_or(&text).as_bytes()) + } else { + Vec::new() + }; + Self { text, folded, number, boolean, word_prefix } } fn folded(&self) -> &str { @@ -343,16 +351,26 @@ fn string_match(haystack: &str, literal: &Literal<'_>, op: CompareOp) -> bool { let boundary = |c: char| { c.is_whitespace() || (c.is_ascii() && !c.is_ascii_alphanumeric()) }; - let mut offset = 0; - while let Some(index) = haystack[offset..].find(needle) { - let start = offset + index; - let end = start + needle.len(); - if haystack[..start].chars().next_back().is_none_or(boundary) - && haystack[end..].chars().next().is_none_or(boundary) - { - return true; + let bytes = needle.as_bytes(); + let mut matched = 0; + for (index, byte) in haystack.bytes().enumerate() { + while matched > 0 && byte != bytes[matched] { + matched = literal.word_prefix[matched - 1]; + } + if byte == bytes[matched] { + matched += 1; + } + if matched == bytes.len() { + // A complete UTF-8 needle matches only at character boundaries. + let end = index + 1; + let start = end - bytes.len(); + if haystack[..start].chars().next_back().is_none_or(boundary) + && haystack[end..].chars().next().is_none_or(boundary) + { + return true; + } + matched = literal.word_prefix[matched - 1]; } - offset = start + haystack[start..].chars().next().unwrap().len_utf8(); } false } @@ -360,6 +378,22 @@ fn string_match(haystack: &str, literal: &Literal<'_>, op: CompareOp) -> bool { } } +// Prefix lengths let the KMP search reuse overlapping matches in linear time. +fn prefix_lengths(needle: &[u8]) -> Vec<usize> { + let mut prefix = vec![0; needle.len()]; + for index in 1..needle.len() { + let mut matched = prefix[index - 1]; + while matched > 0 && needle[index] != needle[matched] { + matched = prefix[matched - 1]; + } + if needle[index] == needle[matched] { + matched += 1; + } + prefix[index] = matched; + } + prefix +} + fn lowercase(s: &str) -> Cow<'_, str> { if s.is_ascii() && !s.bytes().any(|b| b.is_ascii_uppercase()) { Cow::Borrowed(s) diff --git a/tests/compiled_tests.rs b/tests/compiled_tests.rs index c591fbc..b90c810 100644 --- a/tests/compiled_tests.rs +++ b/tests/compiled_tests.rs @@ -140,6 +140,70 @@ fn regex_resources_and_manual_trees_are_bounded() { } #[test] +fn phrase_matching_agrees_with_a_simple_reference() { + struct Text<'a>(&'a str); + impl Filterable for Text<'_> { + fn field(&self, name: &str) -> Option<Value<'_>> { + (name == "value").then_some(Value::String(self.0)) + } + } + fn strings(depth: usize) -> Vec<String> { + let mut result = vec![String::new()]; + let mut level = vec![String::new()]; + for _ in 0..depth { + level = level + .iter() + .flat_map(|prefix| { + ["a", "é", "İ", " ", "!"].map(|suffix| format!("{prefix}{suffix}")) + }) + .collect(); + result.extend(level.iter().cloned()); + } + result + } + let haystacks = strings(4); + for needle in strings(3) { + let expr = parse(&format!( + "value:{}", + serde_json::to_string(&needle).unwrap() + )) + .unwrap() + .unwrap(); + let filter = expr.compile().unwrap(); + let folded_needle = needle.to_lowercase(); + for haystack in &haystacks { + let folded = haystack.to_lowercase(); + let boundary = + |c: char| c.is_whitespace() || (c.is_ascii() && !c.is_ascii_alphanumeric()); + let expected = folded_needle.is_empty() + || folded.char_indices().any(|(start, _)| { + folded[start..].starts_with(&folded_needle) + && folded[..start].chars().next_back().is_none_or(boundary) + && folded[start + folded_needle.len()..] + .chars() + .next() + .is_none_or(boundary) + }); + assert_eq!( + filter.evaluate(&Text(haystack)), + expected, + "{haystack:?} : {needle:?}" + ); + } + } +} + +#[test] +fn long_overlapping_phrases_are_supported() { + let needle = "aa ".repeat(1000) + "a"; + let expr = parse(&format!("value:\"{needle}\"")).unwrap().unwrap(); + let filter = expr.compile().unwrap(); + let haystack = "aa ".repeat(100_000); + assert!(!filter.evaluate(&json!({"value": haystack}))); + assert!(filter.evaluate(&json!({"value": haystack + "a"}))); +} + +#[test] fn invalid_comparison_operands_report_errors() { let expr = parse("value:(other=1)").unwrap().unwrap(); assert!(expr.compile().is_err()); |
