1use alloc::{collections::VecDeque, string::String, vec::Vec};
6use core::{num::NonZeroUsize, ops::ControlFlow};
7
8const TRUNCATION_SUFFIX: &str = "...[truncated]";
9
10#[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)]
12pub enum Level {
13 Debug,
15 Info,
17 Ok,
19 Warn,
21 Error,
23}
24
25#[derive(Clone, Copy, Debug, Eq, PartialEq)]
27pub struct Limits {
28 pub max_entries: NonZeroUsize,
30 pub max_message_bytes: usize,
32 pub max_label_bytes: usize,
34 pub max_text_bytes: usize,
37}
38
39#[derive(Clone, Copy, Debug)]
41pub struct EntryInput<'a> {
42 pub created_at_secs: u64,
44 pub level: Level,
46 pub source: &'a str,
48 pub topic: Option<&'a str>,
50 pub message: &'a str,
52}
53
54#[derive(Clone, Debug, Eq, PartialEq)]
56pub struct Entry {
57 pub sequence: u64,
59 pub created_at_secs: u64,
61 pub level: Level,
63 pub source: String,
65 pub topic: Option<String>,
67 pub message: String,
69 pub truncated: bool,
71}
72
73#[derive(Clone, Copy, Debug, Eq, PartialEq)]
75pub enum Label {
76 Source,
78 Topic,
80}
81
82#[derive(Clone, Copy, Debug, Eq, PartialEq)]
84pub enum AppendError {
85 LabelTooLong {
87 label: Label,
89 actual_bytes: usize,
91 max_bytes: usize,
93 },
94 TimestampRegressed {
96 previous: u64,
98 current: u64,
100 },
101 SequenceExhausted,
103 TextBudgetExceeded {
105 required_bytes: u128,
107 max_bytes: usize,
109 },
110}
111
112impl core::fmt::Display for AppendError {
113 fn fmt(&self, formatter: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
114 match self {
115 Self::LabelTooLong {
116 label,
117 actual_bytes,
118 max_bytes,
119 } => {
120 let label = match label {
121 Label::Source => "source",
122 Label::Topic => "topic",
123 };
124 write!(
125 formatter,
126 "log {label} label exceeds {max_bytes} bytes ({actual_bytes} supplied)"
127 )
128 }
129 Self::TimestampRegressed { previous, current } => write!(
130 formatter,
131 "log timestamp regressed from {previous} to {current} seconds"
132 ),
133 Self::SequenceExhausted => formatter.write_str("log sequence identities are exhausted"),
134 Self::TextBudgetExceeded {
135 required_bytes,
136 max_bytes,
137 } => write!(
138 formatter,
139 "log row requires {required_bytes} text bytes (limit {max_bytes})"
140 ),
141 }
142 }
143}
144
145impl core::error::Error for AppendError {}
146
147#[derive(Clone, Copy, Debug, Eq, PartialEq)]
149pub struct AppendReceipt {
150 pub sequence: u64,
152 pub truncated: bool,
154 pub evicted: usize,
156}
157
158#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
160pub enum TopicMatch<'a> {
161 #[default]
163 Any,
164 Absent,
166 Exact(&'a str),
168}
169
170#[derive(Clone, Copy, Debug, Default)]
172pub struct Filter<'a> {
173 pub source: Option<&'a str>,
175 pub topic: TopicMatch<'a>,
177 pub min_level: Option<Level>,
179}
180
181impl Filter<'_> {
182 fn matches(self, entry: &Entry) -> bool {
183 let source_matches = self.source.is_none_or(|source| source == entry.source);
184 let topic_matches = match self.topic {
185 TopicMatch::Any => true,
186 TopicMatch::Absent => entry.topic.is_none(),
187 TopicMatch::Exact(topic) => entry.topic.as_deref() == Some(topic),
188 };
189 let level_matches = self.min_level.is_none_or(|level| entry.level >= level);
190 source_matches && topic_matches && level_matches
191 }
192}
193
194#[derive(Clone, Copy, Debug)]
196pub struct PageRequest {
197 pub before: Option<u64>,
199 pub max_results: NonZeroUsize,
201 pub max_scanned: NonZeroUsize,
203}
204
205#[derive(Debug)]
207pub struct Page<'a> {
208 pub entries: Vec<&'a Entry>,
210 pub scanned: usize,
212 pub next_before: Option<u64>,
214}
215
216#[derive(Clone, Copy, Debug, Eq, PartialEq)]
218pub struct PageScan {
219 pub matched: usize,
221 pub scanned: usize,
223 pub next_before: Option<u64>,
225}
226
227#[derive(Clone, Copy, Debug)]
230pub struct LogCheckpoint<'a> {
231 limits: Limits,
232 entries: &'a VecDeque<Entry>,
233 next_sequence: Option<u64>,
234 last_created_at_secs: Option<u64>,
235}
236
237impl<'a> LogCheckpoint<'a> {
238 #[must_use]
240 pub const fn limits(&self) -> Limits {
241 self.limits
242 }
243
244 pub fn entries(&self) -> impl ExactSizeIterator<Item = &'a Entry> + DoubleEndedIterator + 'a {
246 self.entries.iter()
247 }
248
249 #[must_use]
251 pub const fn next_sequence(&self) -> Option<u64> {
252 self.next_sequence
253 }
254
255 #[must_use]
257 pub const fn last_created_at_secs(&self) -> Option<u64> {
258 self.last_created_at_secs
259 }
260}
261
262#[derive(Clone, Copy, Debug, Eq, PartialEq)]
264pub struct RetentionBatch {
265 pub removed: usize,
267 pub more_due: bool,
269}
270
271#[derive(Clone, Debug, Eq, PartialEq)]
276pub struct LogSnapshot {
277 pub limits: Limits,
279 pub entries: Vec<Entry>,
281 pub next_sequence: Option<u64>,
283 pub last_created_at_secs: Option<u64>,
285}
286
287#[derive(Clone, Copy, Debug, Eq, PartialEq)]
289pub enum RestoreError {
290 TooManyEntries,
292 InvalidSequence,
294 InvalidTimestamp,
296 InvalidEntry,
298 TextBudgetExceeded,
300}
301
302impl core::fmt::Display for RestoreError {
303 fn fmt(&self, formatter: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
304 formatter.write_str(match self {
305 Self::TooManyEntries => "log checkpoint exceeds its entry limit",
306 Self::InvalidSequence => "invalid log checkpoint sequence",
307 Self::InvalidTimestamp => "invalid log checkpoint timestamp",
308 Self::InvalidEntry => "invalid bounded log checkpoint entry",
309 Self::TextBudgetExceeded => "log checkpoint exceeds its text budget",
310 })
311 }
312}
313
314impl core::error::Error for RestoreError {}
315
316#[derive(Debug)]
318pub struct Log {
319 limits: Limits,
320 entries: VecDeque<Entry>,
321 retained_text_bytes: usize,
322 next_sequence: Option<u64>,
323 last_created_at_secs: Option<u64>,
324}
325
326impl Log {
327 #[must_use]
329 pub const fn new(limits: Limits) -> Self {
330 Self {
331 limits,
332 entries: VecDeque::new(),
333 retained_text_bytes: 0,
334 next_sequence: Some(0),
335 last_created_at_secs: None,
336 }
337 }
338
339 #[must_use]
341 pub const fn limits(&self) -> Limits {
342 self.limits
343 }
344
345 #[must_use]
347 pub const fn retained_text_bytes(&self) -> usize {
348 self.retained_text_bytes
349 }
350
351 #[must_use]
353 pub const fn checkpoint(&self) -> LogCheckpoint<'_> {
354 LogCheckpoint {
355 limits: self.limits,
356 entries: &self.entries,
357 next_sequence: self.next_sequence,
358 last_created_at_secs: self.last_created_at_secs,
359 }
360 }
361
362 #[must_use]
365 pub fn snapshot(&self) -> LogSnapshot {
366 LogSnapshot {
367 limits: self.limits,
368 entries: self.entries.iter().cloned().collect(),
369 next_sequence: self.next_sequence,
370 last_created_at_secs: self.last_created_at_secs,
371 }
372 }
373
374 #[must_use]
378 pub fn into_snapshot(self) -> LogSnapshot {
379 LogSnapshot {
380 limits: self.limits,
381 entries: self.entries.into(),
382 next_sequence: self.next_sequence,
383 last_created_at_secs: self.last_created_at_secs,
384 }
385 }
386
387 pub fn restore(snapshot: LogSnapshot) -> Result<Self, RestoreError> {
397 let retained_text_bytes = validate_snapshot(&snapshot)?;
398 let LogSnapshot {
399 limits,
400 entries,
401 next_sequence,
402 last_created_at_secs,
403 } = snapshot;
404 Ok(Self {
405 limits,
406 entries: entries.into(),
407 retained_text_bytes,
408 next_sequence,
409 last_created_at_secs,
410 })
411 }
412
413 #[must_use]
415 pub fn len(&self) -> usize {
416 self.entries.len()
417 }
418
419 #[must_use]
421 pub fn is_empty(&self) -> bool {
422 self.entries.is_empty()
423 }
424
425 pub fn append(&mut self, input: EntryInput<'_>) -> Result<AppendReceipt, AppendError> {
433 self.validate_label(Label::Source, input.source)?;
434 if let Some(topic) = input.topic {
435 self.validate_label(Label::Topic, topic)?;
436 }
437 if let Some(previous) = self.last_created_at_secs
438 && input.created_at_secs < previous
439 {
440 return Err(AppendError::TimestampRegressed {
441 previous,
442 current: input.created_at_secs,
443 });
444 }
445 let sequence = self.next_sequence.ok_or(AppendError::SequenceExhausted)?;
446 let (prefix, suffix) = message_parts(input.message, self.limits.max_message_bytes);
447 let required_bytes = text_lengths(input.source, input.topic, prefix.len() + suffix.len())
449 .into_iter()
450 .map(|bytes| bytes as u128)
451 .sum();
452 let text_bytes = usize::try_from(required_bytes)
453 .ok()
454 .filter(|bytes| *bytes <= self.limits.max_text_bytes)
455 .ok_or(AppendError::TextBudgetExceeded {
456 required_bytes,
457 max_bytes: self.limits.max_text_bytes,
458 })?;
459 let truncated = input.message.len() > self.limits.max_message_bytes;
460 let entry = Entry {
461 sequence,
462 created_at_secs: input.created_at_secs,
463 level: input.level,
464 source: String::from(input.source),
465 topic: input.topic.map(String::from),
466 message: bounded_message(prefix, suffix),
467 truncated,
468 };
469 let mut evicted = 0;
470 while (self.entries.len() >= self.limits.max_entries.get()
471 || self.retained_text_bytes > self.limits.max_text_bytes - text_bytes)
472 && self.remove_oldest()
473 {
474 evicted += 1;
475 }
476 self.entries.push_back(entry);
477 self.retained_text_bytes += text_bytes;
478 self.next_sequence = sequence.checked_add(1);
479 self.last_created_at_secs = Some(input.created_at_secs);
480 Ok(AppendReceipt {
481 sequence,
482 truncated,
483 evicted,
484 })
485 }
486
487 pub fn prune_expired(
490 &mut self,
491 now_secs: u64,
492 max_age_secs: u64,
493 max_remove: usize,
494 ) -> RetentionBatch {
495 let cutoff = now_secs.saturating_sub(max_age_secs);
496 let mut removed = 0;
497 while removed < max_remove && self.expired_before(cutoff) {
498 self.remove_oldest();
499 removed += 1;
500 }
501 RetentionBatch {
502 removed,
503 more_due: self.expired_before(cutoff),
504 }
505 }
506
507 #[must_use]
509 pub fn next_expiry_secs(&self, max_age_secs: u64) -> Option<u64> {
510 self.entries
511 .front()?
512 .created_at_secs
513 .checked_add(max_age_secs)?
514 .checked_add(1)
515 }
516
517 #[must_use]
520 pub fn page(&self, filter: Filter<'_>, request: PageRequest) -> Page<'_> {
521 let mut entries = Vec::new();
522 let scan = self.visit_page(filter, request, |entry| {
523 entries.push(entry);
524 ControlFlow::Continue(())
525 });
526 Page {
527 entries,
528 scanned: scan.scanned,
529 next_before: scan.next_before,
530 }
531 }
532
533 pub fn visit_page<'a>(
538 &'a self,
539 filter: Filter<'_>,
540 request: PageRequest,
541 mut visit: impl FnMut(&'a Entry) -> ControlFlow<()>,
542 ) -> PageScan {
543 let mut cursor = request.before.map_or(self.entries.len(), |sequence| {
544 self.entries
545 .binary_search_by_key(&sequence, |entry| entry.sequence)
546 .unwrap_or_else(|index| index)
547 });
548 let mut matched = 0;
549 let mut scanned = 0;
550 while cursor > 0
551 && scanned < request.max_scanned.get()
552 && matched < request.max_results.get()
553 {
554 cursor -= 1;
555 let entry = &self.entries[cursor];
556 scanned += 1;
557 if filter.matches(entry) {
558 matched += 1;
559 if visit(entry).is_break() {
560 break;
561 }
562 }
563 }
564 PageScan {
565 matched,
566 scanned,
567 next_before: if cursor > 0 {
570 self.entries.get(cursor).map(|entry| entry.sequence)
571 } else {
572 None
573 },
574 }
575 }
576
577 const fn validate_label(&self, label: Label, text: &str) -> Result<(), AppendError> {
578 if text.len() > self.limits.max_label_bytes {
579 return Err(AppendError::LabelTooLong {
580 label,
581 actual_bytes: text.len(),
582 max_bytes: self.limits.max_label_bytes,
583 });
584 }
585 Ok(())
586 }
587
588 fn expired_before(&self, cutoff: u64) -> bool {
589 self.entries
590 .front()
591 .is_some_and(|entry| entry.created_at_secs < cutoff)
592 }
593
594 fn remove_oldest(&mut self) -> bool {
595 let Some(entry) = self.entries.pop_front() else {
596 return false;
597 };
598 for bytes in text_lengths(&entry.source, entry.topic.as_deref(), entry.message.len()) {
600 self.retained_text_bytes -= bytes;
601 }
602 true
603 }
604}
605
606fn text_lengths(source: &str, topic: Option<&str>, message_bytes: usize) -> [usize; 3] {
608 [source.len(), topic.map_or(0, str::len), message_bytes]
609}
610
611fn validate_snapshot(snapshot: &LogSnapshot) -> Result<usize, RestoreError> {
612 let LogSnapshot {
613 limits,
614 entries,
615 next_sequence,
616 last_created_at_secs,
617 } = snapshot;
618 let (next_sequence, last_created_at_secs) = (*next_sequence, *last_created_at_secs);
619 if entries.len() > limits.max_entries.get() {
620 return Err(RestoreError::TooManyEntries);
621 }
622 if (next_sequence == Some(0)) != last_created_at_secs.is_none() {
623 return Err(RestoreError::InvalidTimestamp);
624 }
625 if entries.is_empty() && last_created_at_secs == Some(u64::MAX) {
628 return Err(RestoreError::InvalidTimestamp);
629 }
630 let mut previous: Option<&Entry> = None;
631 let mut retained_text_bytes = 0_usize;
632 for entry in entries {
633 if entry.source.len() > limits.max_label_bytes
634 || entry
635 .topic
636 .as_ref()
637 .is_some_and(|topic| topic.len() > limits.max_label_bytes)
638 || !valid_retained_message(entry, limits.max_message_bytes)
639 {
640 return Err(RestoreError::InvalidEntry);
641 }
642 for bytes in text_lengths(&entry.source, entry.topic.as_deref(), entry.message.len()) {
643 retained_text_bytes = retained_text_bytes
644 .checked_add(bytes)
645 .filter(|total| *total <= limits.max_text_bytes)
646 .ok_or(RestoreError::TextBudgetExceeded)?;
647 }
648 if let Some(previous) = previous {
649 if previous.sequence.checked_add(1) != Some(entry.sequence) {
650 return Err(RestoreError::InvalidSequence);
651 }
652 if entry.created_at_secs < previous.created_at_secs {
653 return Err(RestoreError::InvalidTimestamp);
654 }
655 }
656 previous = Some(entry);
657 }
658 if let Some(last) = previous {
659 if last.sequence.checked_add(1) != next_sequence {
660 return Err(RestoreError::InvalidSequence);
661 }
662 if Some(last.created_at_secs) != last_created_at_secs {
663 return Err(RestoreError::InvalidTimestamp);
664 }
665 }
666 Ok(retained_text_bytes)
667}
668
669const fn truncation_suffix(max_bytes: usize) -> &'static str {
670 if max_bytes > TRUNCATION_SUFFIX.len() {
671 TRUNCATION_SUFFIX
672 } else {
673 ""
674 }
675}
676
677fn valid_retained_message(entry: &Entry, max_bytes: usize) -> bool {
678 if entry.message.len() > max_bytes {
679 return false;
680 }
681 if !entry.truncated {
682 return true;
683 }
684 let suffix = truncation_suffix(max_bytes);
685 let Some(prefix) = entry.message.strip_suffix(suffix) else {
686 return false;
687 };
688 let budget = max_bytes - suffix.len();
689 budget.saturating_sub(prefix.len()) < 4
690}
691
692fn bounded_message(prefix: &str, suffix: &str) -> String {
693 let mut retained = String::with_capacity(prefix.len() + suffix.len());
694 retained.push_str(prefix);
695 retained.push_str(suffix);
696 retained
697}
698
699fn message_parts(message: &str, max_bytes: usize) -> (&str, &'static str) {
700 if message.len() <= max_bytes {
701 return (message, "");
702 }
703 let suffix = truncation_suffix(max_bytes);
704 let mut end = max_bytes - suffix.len();
705 while !message.is_char_boundary(end) {
706 end -= 1;
707 }
708 (&message[..end], suffix)
709}
710
711#[cfg(test)]
712mod tests;