aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorOnur Gündüz <ogunduz@gmail.com>2026-09-29 14:11:15 +0200
committerOnur Gündüz <ogunduz@gmail.com>2026-09-29 14:11:15 +0200
commited979a49940b3054468b48ad1a9f97fab5a2fd81 (patch)
tree0c5bd82595b6b83f77ddc327690558a43c273309
parent171c32577ef504ec3b8ea09bb8df00fd6be7a13d (diff)
downloadele-ed979a49940b3054468b48ad1a9f97fab5a2fd81.tar.gz
ele-ed979a49940b3054468b48ad1a9f97fab5a2fd81.zip
Use linear-time matching for overlapping phrases
-rw-r--r--src/compiled.rs2
-rw-r--r--src/eval.rs56
-rw-r--r--tests/compiled_tests.rs64
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());