Skip to main content

qualia_core_db/bundle/stream/index/
admit.rs

1//! Nonallocating scans and caller-scratch global directory checks.
2use super::cbor::{checked, decode_row};
3use super::{CheckedHeader, EntryIter, EntryView, IndexError, IndexReadLimits};
4use crate::bundle::BundleEntry;
5use minicbor::Decoder;
6
7#[derive(Clone, Copy, Debug)]
8pub struct EntryScratch<'a> {
9    key: &'a str,
10    offset: u64,
11    end: u64,
12    length: u64,
13}
14impl EntryScratch<'_> {
15    pub const EMPTY: Self = Self {
16        key: "",
17        offset: 0,
18        end: 0,
19        length: 0,
20    };
21}
22
23#[derive(Clone, Copy, Debug, PartialEq, Eq)]
24pub struct IndexSizing {
25    entry_count: usize,
26    retained_bytes: usize,
27    scratch_bytes: usize,
28    aggregate_bytes: usize,
29}
30impl IndexSizing {
31    pub const fn entry_count(self) -> usize {
32        self.entry_count
33    }
34    pub const fn retained_bytes(self) -> usize {
35        self.retained_bytes
36    }
37    pub const fn scratch_bytes(self) -> usize {
38        self.scratch_bytes
39    }
40    pub const fn aggregate_bytes(self) -> usize {
41        self.aggregate_bytes
42    }
43}
44
45/// Structurally admitted original bytes; no payload/proof/authority assertion.
46#[derive(Debug)]
47pub struct AdmittedIndex<'a> {
48    header: CheckedHeader,
49    bytes: &'a [u8],
50    sizing: IndexSizing,
51    limits: IndexReadLimits,
52}
53impl<'a> AdmittedIndex<'a> {
54    pub const fn header(&self) -> CheckedHeader {
55        self.header
56    }
57    pub const fn encoded_bytes(&self) -> &'a [u8] {
58        self.bytes
59    }
60    pub const fn sizing(&self) -> IndexSizing {
61        self.sizing
62    }
63    pub fn entries(&self) -> EntryIter<'a> {
64        EntryIter::new(self.bytes, self.sizing.entry_count, self.limits)
65    }
66}
67
68fn scan<'a>(
69    h: &CheckedHeader,
70    bytes: &'a [u8],
71    l: IndexReadLimits,
72    mut visit: impl FnMut(usize, EntryView<'a>, u64) -> Result<(), IndexError>,
73) -> Result<IndexSizing, IndexError> {
74    h.check_limits(l)?;
75    if u64::try_from(bytes.len()).map_err(|_| IndexError::Overflow)? != h.index_length() {
76        return Err(IndexError::Footer);
77    }
78    let mut d = Decoder::new(bytes);
79    let count = checked(d.array())?.ok_or(IndexError::Malformed)?;
80    if count != u64::from(h.entry_count()) {
81        return Err(IndexError::Count);
82    }
83    let count = usize::try_from(count).map_err(|_| IndexError::Overflow)?;
84    let scratch_bytes = count
85        .checked_mul(core::mem::size_of::<EntryScratch<'_>>())
86        .ok_or(IndexError::Overflow)?;
87    let mut retained_bytes = count
88        .checked_mul(core::mem::size_of::<BundleEntry>())
89        .ok_or(IndexError::Overflow)?;
90    let aggregate = |n: usize| {
91        n.checked_mul(4)
92            .and_then(|n| n.checked_add(scratch_bytes))
93            .ok_or(IndexError::Overflow)
94    };
95    if aggregate(retained_bytes)? > l.decoded_index_bytes {
96        return Err(IndexError::ResidentLimit);
97    }
98    for i in 0..count {
99        let row = decode_row(&mut d, l)?;
100        let end = row
101            .offset
102            .checked_add(row.length)
103            .ok_or(IndexError::Overflow)?;
104        if row.offset < 64 || end > h.index_offset() {
105            return Err(IndexError::EntryBounds);
106        }
107        if row.offset % h.alignment() != 0 {
108            return Err(IndexError::Alignment);
109        }
110        retained_bytes = retained_bytes
111            .checked_add(row.retained_bytes()?)
112            .ok_or(IndexError::Overflow)?;
113        if aggregate(retained_bytes)? > l.decoded_index_bytes {
114            return Err(IndexError::ResidentLimit);
115        }
116        visit(i, row, end)?;
117    }
118    if d.position() != bytes.len() {
119        return Err(IndexError::Malformed);
120    }
121    Ok(IndexSizing {
122        entry_count: count,
123        retained_bytes,
124        scratch_bytes,
125        aggregate_bytes: aggregate(retained_bytes)?,
126    })
127}
128
129pub fn measure_index(
130    h: &CheckedHeader,
131    bytes: &[u8],
132    l: IndexReadLimits,
133) -> Result<IndexSizing, IndexError> {
134    scan(h, bytes, l, |_, _, _| Ok(()))
135}
136
137pub fn admit_index<'a>(
138    h: &CheckedHeader,
139    bytes: &'a [u8],
140    l: IndexReadLimits,
141    scratch: &mut [EntryScratch<'a>],
142) -> Result<AdmittedIndex<'a>, IndexError> {
143    let count = usize::try_from(h.entry_count()).map_err(|_| IndexError::Overflow)?;
144    if scratch.len() < count {
145        return Err(IndexError::Scratch);
146    }
147    let sizing = scan(h, bytes, l, |i, row, end| {
148        scratch[i] = EntryScratch {
149            key: row.key,
150            offset: row.offset,
151            end,
152            length: row.length,
153        };
154        Ok(())
155    })?;
156    let rows = &mut scratch[..count];
157    rows.sort_unstable_by(|a, b| a.key.cmp(b.key));
158    if rows.windows(2).any(|p| p[0].key == p[1].key) {
159        return Err(IndexError::DuplicateKey);
160    }
161    rows.sort_unstable_by_key(|r| (r.offset, r.end));
162    let mut occupied_end = 64;
163    for row in rows {
164        // Empty half-open ranges occupy no bytes and never reset the frontier.
165        if row.length == 0 {
166            continue;
167        }
168        if row.offset < occupied_end {
169            return Err(IndexError::Overlap);
170        }
171        occupied_end = row.end;
172    }
173    Ok(AdmittedIndex {
174        header: *h,
175        bytes,
176        sizing,
177        limits: l,
178    })
179}