1use crate::{IndexEntry, ObjectLogError, PartitionKey, Sequencer};
3
4pub trait BoundedSequencer: Sequencer {
6 fn lookup_page(
10 &self,
11 partition: &PartitionKey,
12 offset: i64,
13 max_entries: usize,
14 max_metadata_bytes: usize,
15 ) -> Result<Vec<IndexEntry>, ObjectLogError>;
16}
17fn invalid(message: &str) -> ObjectLogError {
18 ObjectLogError::Sequencer(message.into())
19}
20pub(crate) fn entry_end(entry: &IndexEntry) -> Result<i64, ObjectLogError> {
21 if entry.base_offset < 0 || entry.record_count <= 0 {
22 return Err(invalid("invalid index offset/count"));
23 }
24 entry
25 .base_offset
26 .checked_add(i64::from(entry.record_count))
27 .ok_or_else(|| invalid("index offset overflow"))
28}
29pub(crate) fn validate_index(
30 entries: &[IndexEntry],
31 log_start: i64,
32 next: i64,
33) -> Result<(), ObjectLogError> {
34 if log_start < 0 || next < log_start {
35 return Err(invalid("invalid retained index bounds"));
36 }
37 let mut previous = None;
38 for entry in entries {
39 let end = entry_end(entry)?;
40 if entry.location.object_id.is_empty() {
41 return Err(invalid("index has empty object identifier"));
42 }
43 if let Some(previous) = previous {
44 if entry.base_offset != previous {
45 return Err(invalid("index ranges are not ordered and contiguous"));
46 }
47 } else if entry.base_offset > log_start || end <= log_start {
48 return Err(invalid("index does not cover retained boundary"));
49 }
50 previous = Some(end);
51 }
52 if previous.unwrap_or(log_start) != next {
53 return Err(invalid("index does not cover committed tail"));
54 }
55 Ok(())
56}
57pub(crate) fn page(
59 entries: &[IndexEntry],
60 offset: i64,
61 max_entries: usize,
62 max_bytes: usize,
63) -> Result<Vec<IndexEntry>, ObjectLogError> {
64 if offset < 0 || max_entries == 0 || max_bytes == 0 {
65 return Err(ObjectLogError::InvalidConfig(
66 "positive page limits and nonnegative offset required".into(),
67 ));
68 }
69 let start = entries
70 .partition_point(|entry| entry.base_offset + i64::from(entry.record_count) <= offset);
71 let available = &entries[start..];
72 let mut count = 0;
73 let mut bytes = 0usize;
74 for entry in available.iter().take(max_entries) {
75 let cost = std::mem::size_of::<IndexEntry>()
76 .checked_add(entry.location.object_id.len())
77 .and_then(|n| n.checked_add(64))
78 .ok_or_else(|| invalid("index metadata size overflow"))?;
79 let Some(next) = bytes.checked_add(cost).filter(|next| *next <= max_bytes) else {
80 if count == 0 {
81 return Err(ObjectLogError::BudgetExceeded(
82 "first index entry exceeds metadata page budget".into(),
83 ));
84 }
85 break;
86 };
87 bytes = next;
88 count += 1;
89 }
90 let mut out = Vec::with_capacity(count);
91 out.extend(available[..count].iter().cloned());
92 Ok(out)
93}
94
95#[cfg(test)]
96mod tests {
97 use super::*;
98 use crate::BatchLocation;
99 fn entry(base: i64, count: i32, name: &str) -> IndexEntry {
100 IndexEntry {
101 base_offset: base,
102 record_count: count,
103 location: BatchLocation {
104 object_id: name.into(),
105 byte_start: 0,
106 byte_len: 1,
107 },
108 }
109 }
110 #[test]
111 fn installed_ranges_are_checked_without_sorting_or_overflow() {
112 let good = [entry(0, 3, "a"), entry(3, 2, "b")];
113 validate_index(&good, 0, 5).unwrap();
114 validate_index(&good, 2, 5).unwrap();
115 for entries in [
116 vec![entry(-1, 1, "a")],
117 vec![entry(0, 0, "a")],
118 vec![entry(i64::MAX, 1, "a")],
119 vec![entry(0, 2, "a"), entry(1, 1, "b")],
120 vec![entry(1, 1, "a")],
121 vec![entry(0, 1, "")],
122 ] {
123 assert!(validate_index(&entries, 0, 2).is_err());
124 }
125 assert!(validate_index(&good, 0, 6).is_err());
126 assert!(validate_index(&[], 0, 1).is_err());
127 validate_index(&[], 5, 5).unwrap();
128 }
129 #[test]
130 fn page_bound_includes_full_object_names_and_mid_batch_offsets() {
131 let entries = [
132 entry(0, 3, &"a".repeat(5000)),
133 entry(3, 2, "b"),
134 entry(5, 1, "c"),
135 ];
136 let cost = std::mem::size_of::<IndexEntry>() + 5000 + 64;
137 assert!(matches!(
138 page(&entries, 2, 3, cost - 1),
139 Err(ObjectLogError::BudgetExceeded(_))
140 ));
141 let first = page(&entries, 2, 3, cost).unwrap();
142 assert_eq!(first, entries[..1]);
143 assert_eq!(page(&entries, 3, 1, 4096).unwrap(), entries[1..2]);
144 assert!(page(&entries, 6, 1, 4096).unwrap().is_empty());
145 assert!(page(&entries, -1, 1, 4096).is_err());
146 assert!(page(&entries, 0, 0, 4096).is_err());
147 }
148}