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 /src | |
| parent | 171c32577ef504ec3b8ea09bb8df00fd6be7a13d (diff) | |
| download | ele-ed979a49940b3054468b48ad1a9f97fab5a2fd81.tar.gz ele-ed979a49940b3054468b48ad1a9f97fab5a2fd81.zip | |
Use linear-time matching for overlapping phrases
Diffstat (limited to 'src')
| -rw-r--r-- | src/compiled.rs | 2 | ||||
| -rw-r--r-- | src/eval.rs | 56 |
2 files changed, 46 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) |
