icydb_core/db/index/
entry.rs

1use crate::{
2    db::{
3        index::RawIndexKey,
4        store::{StorageKey, StorageKeyEncodeError},
5    },
6    traits::{EntityKind, FieldValue, Storable},
7    value::Value,
8};
9use canic_cdk::structures::storable::Bound;
10use std::{borrow::Cow, collections::BTreeSet};
11use thiserror::Error as ThisError;
12
13///
14/// Constants
15///
16
17const INDEX_ENTRY_LEN_BYTES: usize = 4;
18pub const MAX_INDEX_ENTRY_KEYS: usize = 65_535;
19
20#[allow(clippy::cast_possible_truncation)]
21pub const MAX_INDEX_ENTRY_BYTES: u32 =
22    (INDEX_ENTRY_LEN_BYTES + (MAX_INDEX_ENTRY_KEYS * StorageKey::STORED_SIZE_USIZE)) as u32;
23
24///
25/// IndexEntryCorruption
26///
27
28#[derive(Debug, ThisError)]
29pub enum IndexEntryCorruption {
30    #[error("index entry exceeds max size")]
31    TooLarge { len: usize },
32
33    #[error("index entry missing key count")]
34    MissingLength,
35
36    #[error("index entry key count exceeds limit")]
37    TooManyKeys { count: usize },
38
39    #[error("index entry length does not match key count")]
40    LengthMismatch,
41
42    #[error("index entry contains invalid key bytes")]
43    InvalidKey,
44
45    #[error("index entry contains duplicate key")]
46    DuplicateKey,
47
48    #[error("index entry contains zero keys")]
49    EmptyEntry,
50
51    #[error("unique index entry contains {keys} keys")]
52    NonUniqueEntry { keys: usize },
53
54    #[error("index entry missing expected entity key: {entity_key:?} (index {index_key:?})")]
55    MissingKey {
56        index_key: Box<RawIndexKey>,
57        entity_key: Value,
58    },
59
60    #[error("index entry points at key {indexed_key:?} but stored row key is {row_key:?}")]
61    RowKeyMismatch {
62        indexed_key: Box<Value>,
63        row_key: Box<Value>,
64    },
65}
66
67impl IndexEntryCorruption {
68    #[must_use]
69    pub fn missing_key(index_key: RawIndexKey, entity_key: impl FieldValue) -> Self {
70        Self::MissingKey {
71            index_key: Box::new(index_key),
72            entity_key: entity_key.to_value(),
73        }
74    }
75}
76
77///
78/// IndexEntryEncodeError
79///
80
81#[derive(Debug, ThisError)]
82pub enum IndexEntryEncodeError {
83    #[error("index entry exceeds max keys: {keys} (limit {MAX_INDEX_ENTRY_KEYS})")]
84    TooManyKeys { keys: usize },
85
86    #[error("index entry key encoding failed: {0}")]
87    KeyEncoding(#[from] StorageKeyEncodeError),
88}
89
90impl IndexEntryEncodeError {
91    #[must_use]
92    pub const fn keys(&self) -> usize {
93        match self {
94            Self::TooManyKeys { keys } => *keys,
95            Self::KeyEncoding(_) => 0,
96        }
97    }
98}
99
100///
101/// IndexEntry
102///
103
104#[derive(Clone, Debug)]
105pub struct IndexEntry<E: EntityKind> {
106    ids: BTreeSet<E::Id>,
107}
108
109impl<E: EntityKind> IndexEntry<E> {
110    #[must_use]
111    pub fn new(id: E::Id) -> Self {
112        let mut ids = BTreeSet::new();
113        ids.insert(id);
114        Self { ids }
115    }
116
117    pub fn insert(&mut self, id: E::Id) {
118        self.ids.insert(id);
119    }
120
121    pub fn remove(&mut self, id: E::Id) {
122        self.ids.remove(&id);
123    }
124
125    #[must_use]
126    pub fn contains(&self, id: E::Id) -> bool {
127        self.ids.contains(&id)
128    }
129
130    #[must_use]
131    pub fn is_empty(&self) -> bool {
132        self.ids.is_empty()
133    }
134
135    #[must_use]
136    pub fn len(&self) -> usize {
137        self.ids.len()
138    }
139
140    pub fn iter_ids(&self) -> impl Iterator<Item = E::Id> + '_ {
141        self.ids.iter().copied()
142    }
143
144    #[must_use]
145    pub fn single_id(&self) -> Option<E::Id> {
146        if self.ids.len() == 1 {
147            self.ids.iter().copied().next()
148        } else {
149            None
150        }
151    }
152
153    pub fn try_to_raw(&self) -> Result<RawIndexEntry, IndexEntryEncodeError> {
154        RawIndexEntry::try_from_entry(self)
155    }
156}
157
158///
159/// RawIndexEntry
160///
161
162#[derive(Clone, Debug, Eq, PartialEq)]
163pub struct RawIndexEntry(Vec<u8>);
164
165impl RawIndexEntry {
166    pub fn try_from_entry<E: EntityKind>(
167        entry: &IndexEntry<E>,
168    ) -> Result<Self, IndexEntryEncodeError> {
169        let mut keys = Vec::with_capacity(entry.ids.len());
170        for id in &entry.ids {
171            let value = id.to_value();
172            let key = StorageKey::try_from_value(&value)?;
173            keys.push(key);
174        }
175
176        Self::try_from_storage_keys(keys)
177    }
178
179    pub fn try_decode<E: EntityKind>(&self) -> Result<IndexEntry<E>, IndexEntryCorruption> {
180        let storage_keys = self.decode_keys()?;
181        let mut ids = BTreeSet::new();
182
183        for key in storage_keys {
184            let value = key.as_value();
185            let Some(id) = <E::Id as FieldValue>::from_value(&value) else {
186                return Err(IndexEntryCorruption::InvalidKey);
187            };
188            ids.insert(id);
189        }
190
191        if ids.is_empty() {
192            return Err(IndexEntryCorruption::EmptyEntry);
193        }
194
195        Ok(IndexEntry { ids })
196    }
197
198    pub fn try_from_storage_keys<I>(keys: I) -> Result<Self, IndexEntryEncodeError>
199    where
200        I: IntoIterator<Item = StorageKey>,
201    {
202        let keys: Vec<StorageKey> = keys.into_iter().collect();
203        let count = keys.len();
204
205        if count > MAX_INDEX_ENTRY_KEYS {
206            return Err(IndexEntryEncodeError::TooManyKeys { keys: count });
207        }
208
209        let mut out =
210            Vec::with_capacity(INDEX_ENTRY_LEN_BYTES + count * StorageKey::STORED_SIZE_USIZE);
211
212        let count_u32 =
213            u32::try_from(count).map_err(|_| IndexEntryEncodeError::TooManyKeys { keys: count })?;
214        out.extend_from_slice(&count_u32.to_be_bytes());
215
216        for sk in keys {
217            out.extend_from_slice(&sk.to_bytes()?);
218        }
219
220        Ok(Self(out))
221    }
222
223    pub fn decode_keys(&self) -> Result<Vec<StorageKey>, IndexEntryCorruption> {
224        self.validate()?;
225
226        let bytes = self.0.as_slice();
227
228        let mut len_buf = [0u8; INDEX_ENTRY_LEN_BYTES];
229        len_buf.copy_from_slice(&bytes[..INDEX_ENTRY_LEN_BYTES]);
230        let count = u32::from_be_bytes(len_buf) as usize;
231
232        let mut keys = Vec::with_capacity(count);
233        let mut offset = INDEX_ENTRY_LEN_BYTES;
234
235        for _ in 0..count {
236            let end = offset + StorageKey::STORED_SIZE_USIZE;
237            let sk = StorageKey::try_from(&bytes[offset..end])
238                .map_err(|_| IndexEntryCorruption::InvalidKey)?;
239
240            keys.push(sk);
241            offset = end;
242        }
243
244        Ok(keys)
245    }
246
247    /// Validate the raw index entry structure without binding to an entity.
248    pub fn validate(&self) -> Result<(), IndexEntryCorruption> {
249        let bytes = self.0.as_slice();
250
251        if bytes.len() > MAX_INDEX_ENTRY_BYTES as usize {
252            return Err(IndexEntryCorruption::TooLarge { len: bytes.len() });
253        }
254        if bytes.len() < INDEX_ENTRY_LEN_BYTES {
255            return Err(IndexEntryCorruption::MissingLength);
256        }
257
258        let mut len_buf = [0u8; INDEX_ENTRY_LEN_BYTES];
259        len_buf.copy_from_slice(&bytes[..INDEX_ENTRY_LEN_BYTES]);
260        let count = u32::from_be_bytes(len_buf) as usize;
261
262        if count == 0 {
263            return Err(IndexEntryCorruption::EmptyEntry);
264        }
265        if count > MAX_INDEX_ENTRY_KEYS {
266            return Err(IndexEntryCorruption::TooManyKeys { count });
267        }
268
269        let expected = INDEX_ENTRY_LEN_BYTES
270            + count
271                .checked_mul(StorageKey::STORED_SIZE_USIZE)
272                .ok_or(IndexEntryCorruption::LengthMismatch)?;
273
274        if bytes.len() != expected {
275            return Err(IndexEntryCorruption::LengthMismatch);
276        }
277
278        // Validate each StorageKey structurally and detect duplicates
279        let mut keys = BTreeSet::new();
280        let mut offset = INDEX_ENTRY_LEN_BYTES;
281
282        for _ in 0..count {
283            let end = offset + StorageKey::STORED_SIZE_USIZE;
284
285            let sk = StorageKey::try_from(&bytes[offset..end])
286                .map_err(|_| IndexEntryCorruption::InvalidKey)?;
287
288            if !keys.insert(sk) {
289                return Err(IndexEntryCorruption::DuplicateKey);
290            }
291
292            offset = end;
293        }
294
295        Ok(())
296    }
297
298    #[must_use]
299    pub fn as_bytes(&self) -> &[u8] {
300        &self.0
301    }
302
303    #[must_use]
304    pub const fn len(&self) -> usize {
305        self.0.len()
306    }
307
308    #[must_use]
309    pub const fn is_empty(&self) -> bool {
310        self.0.is_empty()
311    }
312}
313
314impl<E: EntityKind> TryFrom<&IndexEntry<E>> for RawIndexEntry {
315    type Error = IndexEntryEncodeError;
316
317    fn try_from(entry: &IndexEntry<E>) -> Result<Self, Self::Error> {
318        Self::try_from_entry(entry)
319    }
320}
321
322impl Storable for RawIndexEntry {
323    fn to_bytes(&self) -> Cow<'_, [u8]> {
324        Cow::Borrowed(&self.0)
325    }
326
327    fn from_bytes(bytes: Cow<'_, [u8]>) -> Self {
328        Self(bytes.into_owned())
329    }
330
331    fn into_bytes(self) -> Vec<u8> {
332        self.0
333    }
334
335    const BOUND: Bound = Bound::Bounded {
336        max_size: MAX_INDEX_ENTRY_BYTES,
337        is_fixed_size: false,
338    };
339}
icydb_core/db/index/entry.rs

icydb_core/db/index/
entry.rs
