1use std::cmp::Ordering;
2
3use crate::{
4 CaseSensitivity, LogPredicate, LogQuery, MetadataField, NumericComparison, QueryCursor,
5 QueryOrder, QuerySort, StructuralRecordView, TextMatchKind, TextMatcher, analyze_message,
6};
7
8pub(crate) struct RequiredIndexConstraints<'a> {
9 pub(crate) terms: Vec<&'a str>,
10 pub(crate) fields: Vec<(&'a str, &'a str)>,
11 pub(crate) message_literals: Vec<&'a str>,
12 pub(crate) impossible: bool,
13}
14
15impl LogQuery {
16 #[must_use]
19 pub fn matches<R: StructuralRecordView>(&self, record: &R) -> bool {
20 self.offset_matches(record.structural_offset())
21 && self.timestamp_matches(record.structural_timestamp_unix_nanos())
22 && self.cursor_matches(record)
23 && self.legacy_terms_match(record)
24 && self.legacy_fields_match(record)
25 && predicate_matches(&self.predicate, record)
26 }
27
28 #[must_use]
30 pub fn compare<R: StructuralRecordView>(&self, left: &R, right: &R) -> Ordering {
31 let ordering = match self.sort {
32 QuerySort::Offset => left.structural_offset().cmp(&right.structural_offset()),
33 QuerySort::Timestamp => (
34 left.structural_timestamp_unix_nanos(),
35 left.structural_offset(),
36 )
37 .cmp(&(
38 right.structural_timestamp_unix_nanos(),
39 right.structural_offset(),
40 )),
41 };
42 if self.order == QueryOrder::NewestFirst {
43 ordering.reverse()
44 } else {
45 ordering
46 }
47 }
48
49 #[must_use]
51 pub fn cursor_for<R: StructuralRecordView>(&self, record: &R) -> QueryCursor {
52 QueryCursor::new(
53 record.structural_timestamp_unix_nanos(),
54 record.structural_offset(),
55 )
56 }
57
58 #[must_use]
61 pub fn select<R: StructuralRecordView>(&self, records: impl IntoIterator<Item = R>) -> Vec<R> {
62 let mut selected = records
63 .into_iter()
64 .filter(|record| self.matches(record))
65 .collect::<Vec<_>>();
66 selected.sort_unstable_by(|left, right| self.compare(left, right));
67 if let Some(limit) = self.limit {
68 selected.truncate(limit);
69 }
70 selected
71 }
72
73 #[must_use]
79 pub fn requires_post_decode(&self) -> bool {
80 self.start_offset.is_some()
81 || self.end_offset.is_some()
82 || self.start_timestamp_unix_nanos.is_some()
83 || self.end_timestamp_unix_nanos.is_some()
84 || self.after.is_some()
85 || self.sort == QuerySort::Timestamp
86 || !predicate_is_index_only_conjunction(&self.predicate)
87 }
88
89 pub(crate) fn required_index_constraints(&self) -> RequiredIndexConstraints<'_> {
90 let mut constraints = RequiredIndexConstraints {
91 terms: self.terms.iter().map(AsRef::as_ref).collect(),
92 fields: self
93 .exact_fields
94 .iter()
95 .map(|field| (field.key.as_ref(), field.value.as_ref()))
96 .collect(),
97 message_literals: Vec::new(),
98 impossible: false,
99 };
100 collect_required_constraints(&self.predicate, &mut constraints);
101 constraints
102 }
103
104 pub(crate) fn can_apply_index_limit(&self) -> bool {
105 self.start_offset.is_none()
106 && self.end_offset.is_none()
107 && self.start_timestamp_unix_nanos.is_none()
108 && self.end_timestamp_unix_nanos.is_none()
109 && self.after.is_none()
110 && self.sort == QuerySort::Offset
111 && predicate_is_index_only_conjunction(&self.predicate)
112 }
113
114 pub(crate) fn needs_record_filter(&self) -> bool {
115 self.start_timestamp_unix_nanos.is_some()
116 || self.end_timestamp_unix_nanos.is_some()
117 || self.after.is_some()
118 || self.sort == QuerySort::Timestamp
119 || !predicate_is_index_only_conjunction(&self.predicate)
120 }
121
122 pub(crate) fn has_residual_predicate(&self) -> bool {
123 !predicate_is_index_only_conjunction(&self.predicate)
124 }
125
126 pub(crate) fn message_candidate_matches(&self, message: &str) -> Option<bool> {
127 if !self
128 .terms
129 .iter()
130 .all(|expected| message_has_term(message, expected))
131 {
132 return Some(false);
133 }
134 message_only_predicate_matches(&self.predicate, message)
135 }
136
137 pub(crate) fn matches_index_candidate<R: StructuralRecordView>(&self, record: &R) -> bool {
138 self.offset_matches(record.structural_offset())
139 && self.timestamp_matches(record.structural_timestamp_unix_nanos())
140 && self.cursor_matches(record)
141 && predicate_matches(&self.predicate, record)
142 }
143
144 pub(crate) fn has_invalid_range(&self) -> bool {
145 self.start_offset
146 .zip(self.end_offset)
147 .is_some_and(|(start, end)| start >= end)
148 || self
149 .start_timestamp_unix_nanos
150 .zip(self.end_timestamp_unix_nanos)
151 .is_some_and(|(start, end)| start >= end)
152 }
153
154 fn offset_matches(&self, offset: shard_stream_core::LogicalOffset) -> bool {
155 self.start_offset.is_none_or(|start| offset >= start)
156 && self.end_offset.is_none_or(|end| offset < end)
157 }
158
159 fn timestamp_matches(&self, timestamp_unix_nanos: u64) -> bool {
160 self.start_timestamp_unix_nanos
161 .is_none_or(|start| timestamp_unix_nanos >= start)
162 && self
163 .end_timestamp_unix_nanos
164 .is_none_or(|end| timestamp_unix_nanos < end)
165 }
166
167 fn cursor_matches<R: StructuralRecordView>(&self, record: &R) -> bool {
168 let Some(cursor) = self.after else {
169 return true;
170 };
171 let ordering = match self.sort {
172 QuerySort::Offset => record.structural_offset().cmp(&cursor.offset),
173 QuerySort::Timestamp => (
174 record.structural_timestamp_unix_nanos(),
175 record.structural_offset(),
176 )
177 .cmp(&(cursor.timestamp_unix_nanos, cursor.offset)),
178 };
179 if self.order == QueryOrder::NewestFirst {
180 ordering == Ordering::Less
181 } else {
182 ordering == Ordering::Greater
183 }
184 }
185
186 fn legacy_terms_match<R: StructuralRecordView>(&self, record: &R) -> bool {
187 self.terms
188 .iter()
189 .all(|expected| message_has_term(record.structural_message(), expected))
190 }
191
192 fn legacy_fields_match<R: StructuralRecordView>(&self, record: &R) -> bool {
193 self.exact_fields
194 .iter()
195 .all(|expected| field_equals(record, expected))
196 }
197}
198
199fn collect_required_constraints<'a>(
200 predicate: &'a LogPredicate,
201 constraints: &mut RequiredIndexConstraints<'a>,
202) {
203 match predicate {
204 LogPredicate::MatchAll => {}
205 LogPredicate::MatchNone => constraints.impossible = true,
206 LogPredicate::Term(term) => constraints.terms.push(term),
207 LogPredicate::MessageToken { value, .. } if clickhouse_token_is_index_safe(value) => {
208 constraints.terms.push(value);
209 }
210 LogPredicate::Field { key, matcher }
211 if matcher.kind == TextMatchKind::Exact
212 && matcher.case_sensitivity == CaseSensitivity::Sensitive =>
213 {
214 constraints.fields.push((key, &matcher.value));
215 }
216 LogPredicate::And(predicates) => {
217 for predicate in predicates {
218 collect_required_constraints(predicate, constraints);
219 }
220 }
221 LogPredicate::Message(matcher) => {
222 constraints.message_literals.push(matcher.value.as_ref());
223 }
224 LogPredicate::MessageToken { .. }
225 | LogPredicate::MessageRegex(_)
226 | LogPredicate::FieldExists(_)
227 | LogPredicate::Field { .. }
228 | LogPredicate::FieldIn { .. }
229 | LogPredicate::FieldRegex { .. }
230 | LogPredicate::FieldNumeric { .. }
231 | LogPredicate::Or(_)
232 | LogPredicate::Not(_) => {}
233 }
234}
235
236fn predicate_is_index_only_conjunction(predicate: &LogPredicate) -> bool {
237 match predicate {
238 LogPredicate::MatchAll
239 | LogPredicate::MatchNone
240 | LogPredicate::Term(_)
241 | LogPredicate::Field {
242 matcher:
243 TextMatcher {
244 kind: TextMatchKind::Exact,
245 case_sensitivity: CaseSensitivity::Sensitive,
246 ..
247 },
248 ..
249 } => true,
250 LogPredicate::And(predicates) => predicates.iter().all(predicate_is_index_only_conjunction),
251 LogPredicate::MessageToken { .. }
252 | LogPredicate::Message(_)
253 | LogPredicate::MessageRegex(_)
254 | LogPredicate::FieldExists(_)
255 | LogPredicate::Field { .. }
256 | LogPredicate::FieldIn { .. }
257 | LogPredicate::FieldRegex { .. }
258 | LogPredicate::FieldNumeric { .. }
259 | LogPredicate::Or(_)
260 | LogPredicate::Not(_) => false,
261 }
262}
263
264fn predicate_matches<R: StructuralRecordView>(predicate: &LogPredicate, record: &R) -> bool {
265 match predicate {
266 LogPredicate::MatchAll => true,
267 LogPredicate::MatchNone => false,
268 LogPredicate::Term(term) => message_has_term(record.structural_message(), term),
269 LogPredicate::MessageToken {
270 value,
271 case_sensitivity,
272 } => message_has_clickhouse_token(record.structural_message(), value, *case_sensitivity),
273 LogPredicate::Message(matcher) => text_matches(record.structural_message(), matcher),
274 LogPredicate::MessageRegex(regex) => regex.is_match(record.structural_message()),
275 LogPredicate::FieldExists(key) => {
276 fields(record).any(|(observed, _)| observed == key.as_ref())
277 }
278 LogPredicate::Field { key, matcher } => fields(record).any(|(observed_key, value)| {
279 observed_key == key.as_ref() && text_matches(value, matcher)
280 }),
281 LogPredicate::FieldIn { key, values } => fields(record).any(|(observed_key, value)| {
282 observed_key == key.as_ref() && values.iter().any(|expected| value == expected.as_ref())
283 }),
284 LogPredicate::FieldRegex { key, regex } => fields(record)
285 .any(|(observed_key, value)| observed_key == key.as_ref() && regex.is_match(value)),
286 LogPredicate::FieldNumeric {
287 key,
288 comparison,
289 value,
290 } => fields(record).any(|(observed_key, observed)| {
291 observed_key == key.as_ref()
292 && observed
293 .parse::<i128>()
294 .is_ok_and(|observed| compare_numeric(observed, *comparison, *value))
295 }),
296 LogPredicate::And(predicates) => predicates
297 .iter()
298 .all(|predicate| predicate_matches(predicate, record)),
299 LogPredicate::Or(predicates) => predicates
300 .iter()
301 .any(|predicate| predicate_matches(predicate, record)),
302 LogPredicate::Not(predicate) => !predicate_matches(predicate, record),
303 }
304}
305
306fn message_only_predicate_matches(predicate: &LogPredicate, message: &str) -> Option<bool> {
307 match predicate {
308 LogPredicate::MatchAll => Some(true),
309 LogPredicate::MatchNone => Some(false),
310 LogPredicate::Term(term) => Some(message_has_term(message, term)),
311 LogPredicate::MessageToken {
312 value,
313 case_sensitivity,
314 } => Some(message_has_clickhouse_token(
315 message,
316 value,
317 *case_sensitivity,
318 )),
319 LogPredicate::Message(matcher) => Some(text_matches(message, matcher)),
320 LogPredicate::MessageRegex(regex) => Some(regex.is_match(message)),
321 LogPredicate::And(predicates) => {
322 let mut matched = true;
323 for predicate in predicates {
324 matched &= message_only_predicate_matches(predicate, message)?;
325 }
326 Some(matched)
327 }
328 LogPredicate::Or(predicates) => {
329 let mut matched = false;
330 for predicate in predicates {
331 matched |= message_only_predicate_matches(predicate, message)?;
332 }
333 Some(matched)
334 }
335 LogPredicate::Not(predicate) => {
336 message_only_predicate_matches(predicate, message).map(|value| !value)
337 }
338 LogPredicate::FieldExists(_)
339 | LogPredicate::Field { .. }
340 | LogPredicate::FieldIn { .. }
341 | LogPredicate::FieldRegex { .. }
342 | LogPredicate::FieldNumeric { .. } => None,
343 }
344}
345
346fn fields<R: StructuralRecordView>(record: &R) -> impl Iterator<Item = (&str, &str)> {
347 (0..record.structural_field_count()).filter_map(|index| record.structural_field(index))
348}
349
350fn field_equals<R: StructuralRecordView>(record: &R, expected: &MetadataField) -> bool {
351 fields(record)
352 .any(|(key, value)| key == expected.key.as_ref() && value == expected.value.as_ref())
353}
354
355pub(crate) fn message_has_term(message: &str, expected: &str) -> bool {
356 let mut matched = false;
357 let _ = analyze_message(message, &[], |term| {
358 matched |= text_equal(term, expected, CaseSensitivity::Insensitive);
359 });
360 matched
361}
362
363pub(crate) fn message_has_clickhouse_token(
364 message: &str,
365 expected: &str,
366 case_sensitivity: CaseSensitivity,
367) -> bool {
368 let expected = expected.as_bytes();
369 if expected.is_empty() || expected.iter().copied().any(clickhouse_token_separator) {
370 return false;
371 }
372 let message = message.as_bytes();
373 if expected.len() > message.len() {
374 return false;
375 }
376 message
377 .windows(expected.len())
378 .enumerate()
379 .any(|(start, candidate)| {
380 let bytes_match = match case_sensitivity {
381 CaseSensitivity::Sensitive => candidate == expected,
382 CaseSensitivity::Insensitive => candidate.eq_ignore_ascii_case(expected),
383 };
384 bytes_match
385 && (start == 0 || clickhouse_token_separator(message[start - 1]))
386 && (start + expected.len() == message.len()
387 || clickhouse_token_separator(message[start + expected.len()]))
388 })
389}
390
391fn clickhouse_token_is_index_safe(value: &str) -> bool {
392 !value.is_empty() && value.bytes().all(|byte| byte.is_ascii_alphanumeric())
393}
394
395const fn clickhouse_token_separator(byte: u8) -> bool {
396 byte.is_ascii() && !(byte.is_ascii_alphanumeric() || byte == b'_')
397}
398
399fn text_matches(observed: &str, matcher: &TextMatcher) -> bool {
400 match matcher.kind {
401 TextMatchKind::Exact => text_equal(observed, &matcher.value, matcher.case_sensitivity),
402 TextMatchKind::Contains => {
403 text_contains(observed, &matcher.value, matcher.case_sensitivity)
404 }
405 TextMatchKind::Prefix => text_prefix(observed, &matcher.value, matcher.case_sensitivity),
406 TextMatchKind::Suffix => text_suffix(observed, &matcher.value, matcher.case_sensitivity),
407 }
408}
409
410fn text_equal(left: &str, right: &str, case_sensitivity: CaseSensitivity) -> bool {
411 match case_sensitivity {
412 CaseSensitivity::Sensitive => left == right,
413 CaseSensitivity::Insensitive if left.is_ascii() && right.is_ascii() => {
414 left.eq_ignore_ascii_case(right)
415 }
416 CaseSensitivity::Insensitive => left.to_lowercase() == right.to_lowercase(),
417 }
418}
419
420fn text_contains(haystack: &str, needle: &str, case_sensitivity: CaseSensitivity) -> bool {
421 if needle.is_empty() {
422 return true;
423 }
424 match case_sensitivity {
425 CaseSensitivity::Sensitive => haystack.contains(needle),
426 CaseSensitivity::Insensitive if haystack.is_ascii() && needle.is_ascii() => haystack
427 .as_bytes()
428 .windows(needle.len())
429 .any(|window| window.eq_ignore_ascii_case(needle.as_bytes())),
430 CaseSensitivity::Insensitive => haystack.to_lowercase().contains(&needle.to_lowercase()),
431 }
432}
433
434fn text_prefix(observed: &str, prefix: &str, case_sensitivity: CaseSensitivity) -> bool {
435 match case_sensitivity {
436 CaseSensitivity::Sensitive => observed.starts_with(prefix),
437 CaseSensitivity::Insensitive if observed.is_ascii() && prefix.is_ascii() => observed
438 .get(..prefix.len())
439 .is_some_and(|candidate| candidate.eq_ignore_ascii_case(prefix)),
440 CaseSensitivity::Insensitive => observed.to_lowercase().starts_with(&prefix.to_lowercase()),
441 }
442}
443
444fn text_suffix(observed: &str, suffix: &str, case_sensitivity: CaseSensitivity) -> bool {
445 match case_sensitivity {
446 CaseSensitivity::Sensitive => observed.ends_with(suffix),
447 CaseSensitivity::Insensitive if observed.is_ascii() && suffix.is_ascii() => observed
448 .len()
449 .checked_sub(suffix.len())
450 .and_then(|start| observed.get(start..))
451 .is_some_and(|candidate| candidate.eq_ignore_ascii_case(suffix)),
452 CaseSensitivity::Insensitive => observed.to_lowercase().ends_with(&suffix.to_lowercase()),
453 }
454}
455
456const fn compare_numeric(observed: i128, comparison: NumericComparison, expected: i128) -> bool {
457 match comparison {
458 NumericComparison::Equal => observed == expected,
459 NumericComparison::NotEqual => observed != expected,
460 NumericComparison::LessThan => observed < expected,
461 NumericComparison::LessThanOrEqual => observed <= expected,
462 NumericComparison::GreaterThan => observed > expected,
463 NumericComparison::GreaterThanOrEqual => observed >= expected,
464 }
465}
466
467#[cfg(test)]
468mod tests {
469 use shard_stream_core::{LogicalOffset, LogicalPartitionId, ShardId, TopicId, TopicPartition};
470
471 use super::*;
472 use crate::{CompressionCohortId, DurableLog, LogRegex};
473
474 fn record(message: &str) -> DurableLog {
475 DurableLog::new(
476 ShardId::new(1),
477 TopicPartition::new(TopicId::new(1), LogicalPartitionId::new(2)),
478 LogicalOffset::new(7),
479 99,
480 message,
481 CompressionCohortId::new(1),
482 )
483 .with_field("service", "Paiements")
484 .with_field("status", "503")
485 }
486
487 #[test]
488 fn literal_regex_numeric_and_boolean_predicates_are_exact() {
489 let record = record("ÉCHEC checkout timed out");
490 let predicate = LogPredicate::and(vec![
491 LogPredicate::message_contains("échec checkout"),
492 LogPredicate::message_regex("timed\\s+out$", CaseSensitivity::Insensitive)
493 .expect("regex compiles"),
494 LogPredicate::field(
495 "service",
496 TextMatcher::new("paie", TextMatchKind::Prefix, CaseSensitivity::Insensitive),
497 ),
498 LogPredicate::field_numeric("status", NumericComparison::GreaterThanOrEqual, 500),
499 LogPredicate::negate(LogPredicate::field_equals("service", "worker")),
500 ]);
501 assert!(predicate_matches(&predicate, &record));
502 assert!(!predicate_matches(
503 &LogPredicate::message_contains("success"),
504 &record
505 ));
506 assert!(predicate_matches(
507 &LogPredicate::field_numeric("status", NumericComparison::Equal, 503),
508 &record
509 ));
510 assert!(predicate_matches(
511 &LogPredicate::field_numeric("status", NumericComparison::NotEqual, 200),
512 &record
513 ));
514 }
515
516 #[test]
517 fn invalid_regular_expressions_are_rejected_at_query_construction() {
518 let error =
519 LogRegex::new("(", CaseSensitivity::Sensitive).expect_err("invalid regex is rejected");
520 assert!(matches!(error, crate::TelemetryError::InvalidQuery(_)));
521 }
522
523 #[test]
524 fn empty_literal_contains_matches_without_panicking() {
525 assert!(text_contains("anything", "", CaseSensitivity::Insensitive));
526 }
527
528 #[test]
529 fn clickhouse_tokens_preserve_case_and_ascii_boundaries() {
530 assert!(message_has_clickhouse_token(
531 "prefix Cannot suffix",
532 "Cannot",
533 CaseSensitivity::Sensitive
534 ));
535 assert!(!message_has_clickhouse_token(
536 "prefix Cannot suffix",
537 "cannot",
538 CaseSensitivity::Sensitive
539 ));
540 assert!(message_has_clickhouse_token(
541 "prefix Cannot suffix",
542 "cannot",
543 CaseSensitivity::Insensitive
544 ));
545 assert!(!message_has_clickhouse_token(
546 "prefix_cannot suffix",
547 "cannot",
548 CaseSensitivity::Sensitive
549 ));
550 assert!(!message_has_clickhouse_token(
551 "prefix écannot suffix",
552 "cannot",
553 CaseSensitivity::Sensitive
554 ));
555 }
556
557 #[test]
558 fn clickhouse_token_uses_the_case_folded_index_only_as_a_candidate_filter() {
559 let query = LogQuery::new(record("unused").record_ref.topic_partition).where_predicate(
560 LogPredicate::message_token("Cannot", CaseSensitivity::Sensitive),
561 );
562 let constraints = query.required_index_constraints();
563 assert_eq!(constraints.terms, ["Cannot"]);
564 assert!(query.requires_post_decode());
565 }
566}