aboutsummaryrefslogtreecommitdiff
path: root/src/eval.rs
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 /src/eval.rs
parent171c32577ef504ec3b8ea09bb8df00fd6be7a13d (diff)
downloadele-ed979a49940b3054468b48ad1a9f97fab5a2fd81.tar.gz
ele-ed979a49940b3054468b48ad1a9f97fab5a2fd81.zip
Use linear-time matching for overlapping phrases
Diffstat (limited to 'src/eval.rs')
-rw-r--r--src/eval.rs56
1 files changed, 45 insertions, 11 deletions
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)