icydb_core/db/index/key/
codec.rs

1use crate::{
2    MAX_INDEX_FIELDS,
3    db::{identity::IndexName, index::key::IndexId},
4    traits::Storable,
5};
6use canic_cdk::structures::storable::Bound;
7use std::borrow::Cow;
8
9///
10/// IndexKey
11///
12/// Fully-qualified index lookup key.
13/// Fixed-size, manually encoded structure designed for stable-memory ordering.
14/// Ordering of this type must exactly match byte-level ordering.
15///
16
17#[derive(Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
18pub struct IndexKey {
19    pub(super) index_id: IndexId,
20    pub(super) len: u8,
21    pub(super) values: [[u8; 16]; MAX_INDEX_FIELDS],
22}
23
24#[expect(clippy::cast_possible_truncation)]
25impl IndexKey {
26    /// Fixed on-disk size in bytes (stable, protocol-level)
27    pub const STORED_SIZE_BYTES: u64 =
28        IndexName::STORED_SIZE_BYTES + 1 + (MAX_INDEX_FIELDS as u64 * 16);
29
30    /// Fixed in-memory size (for buffers and arrays)
31    pub const STORED_SIZE_USIZE: usize = Self::STORED_SIZE_BYTES as usize;
32
33    #[must_use]
34    pub fn to_raw(&self) -> RawIndexKey {
35        let mut bytes = [0u8; Self::STORED_SIZE_USIZE];
36
37        let name_bytes = self.index_id.0.to_bytes();
38        bytes[..name_bytes.len()].copy_from_slice(&name_bytes);
39
40        let mut offset = IndexName::STORED_SIZE_USIZE;
41        bytes[offset] = self.len;
42        offset += 1;
43
44        for value in &self.values {
45            bytes[offset..offset + 16].copy_from_slice(value);
46            offset += 16;
47        }
48
49        RawIndexKey(bytes)
50    }
51
52    pub fn try_from_raw(raw: &RawIndexKey) -> Result<Self, &'static str> {
53        let bytes = &raw.0;
54        if bytes.len() != Self::STORED_SIZE_USIZE {
55            return Err("corrupted IndexKey: invalid size");
56        }
57
58        let mut offset = 0;
59
60        let index_name =
61            IndexName::from_bytes(&bytes[offset..offset + IndexName::STORED_SIZE_USIZE])
62                .map_err(|_| "corrupted IndexKey: invalid IndexName bytes")?;
63        offset += IndexName::STORED_SIZE_USIZE;
64
65        let len = bytes[offset];
66        offset += 1;
67
68        if len as usize > MAX_INDEX_FIELDS {
69            return Err("corrupted IndexKey: invalid index length");
70        }
71
72        let mut values = [[0u8; 16]; MAX_INDEX_FIELDS];
73        for value in &mut values {
74            value.copy_from_slice(&bytes[offset..offset + 16]);
75            offset += 16;
76        }
77
78        let len_usize = len as usize;
79        for value in values.iter().skip(len_usize) {
80            if value.iter().any(|&byte| byte != 0) {
81                return Err("corrupted IndexKey: non-zero fingerprint padding");
82            }
83        }
84
85        Ok(Self {
86            index_id: IndexId(index_name),
87            len,
88            values,
89        })
90    }
91
92    // System index keys reserve the `~` namespace in any non-entity segment.
93    #[must_use]
94    pub(crate) fn uses_system_namespace(&self) -> bool {
95        self.index_id
96            .0
97            .as_str()
98            .split('|')
99            .skip(1)
100            .any(|segment| segment.starts_with('~'))
101    }
102}
103
104///
105/// RawIndexKey
106///
107/// Fixed-size, stable-memory representation of IndexKey.
108/// This is the form stored in BTreeMap keys.
109///
110
111#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
112pub struct RawIndexKey([u8; IndexKey::STORED_SIZE_USIZE]);
113
114impl RawIndexKey {
115    /// Borrow the raw byte representation.
116    #[must_use]
117    pub const fn as_bytes(&self) -> &[u8; IndexKey::STORED_SIZE_USIZE] {
118        &self.0
119    }
120}
121
122impl Storable for RawIndexKey {
123    fn to_bytes(&self) -> Cow<'_, [u8]> {
124        Cow::Borrowed(&self.0)
125    }
126
127    fn from_bytes(bytes: Cow<'_, [u8]>) -> Self {
128        let mut out = [0u8; IndexKey::STORED_SIZE_USIZE];
129        if bytes.len() == out.len() {
130            out.copy_from_slice(bytes.as_ref());
131        }
132        Self(out)
133    }
134
135    fn into_bytes(self) -> Vec<u8> {
136        self.0.to_vec()
137    }
138
139    #[expect(clippy::cast_possible_truncation)]
140    const BOUND: Bound = Bound::Bounded {
141        max_size: IndexKey::STORED_SIZE_BYTES as u32,
142        is_fixed_size: true,
143    };
144}
145
146///
147/// TESTS
148///
149
150#[cfg(test)]
151mod tests {
152    use crate::{
153        MAX_INDEX_FIELDS,
154        db::{
155            identity::{EntityName, IndexName},
156            index::{IndexId, IndexKey, RawIndexKey},
157        },
158        traits::Storable,
159    };
160    use std::borrow::Cow;
161
162    #[test]
163    fn index_key_rejects_undersized_bytes() {
164        let bytes = vec![0u8; IndexKey::STORED_SIZE_USIZE - 1];
165        let raw = RawIndexKey::from_bytes(Cow::Borrowed(&bytes));
166        let err = IndexKey::try_from_raw(&raw).expect_err("undersized key should fail");
167        assert!(err.contains("corrupted"));
168    }
169
170    #[test]
171    fn index_key_rejects_oversized_bytes() {
172        let bytes = vec![0u8; IndexKey::STORED_SIZE_USIZE + 1];
173        let raw = RawIndexKey::from_bytes(Cow::Borrowed(&bytes));
174        let err = IndexKey::try_from_raw(&raw).expect_err("oversized key should fail");
175        assert!(err.contains("corrupted"));
176    }
177
178    #[test]
179    #[allow(clippy::cast_possible_truncation)]
180    fn index_key_rejects_len_over_max() {
181        let key = IndexKey::empty(IndexId::max_storable());
182        let raw = key.to_raw();
183        let len_offset = IndexName::STORED_SIZE_BYTES as usize;
184        let mut bytes = raw.as_bytes().to_vec();
185        bytes[len_offset] = (MAX_INDEX_FIELDS as u8) + 1;
186        let raw = RawIndexKey::from_bytes(Cow::Owned(bytes));
187        let err = IndexKey::try_from_raw(&raw).expect_err("oversized length should fail");
188        assert!(err.contains("corrupted"));
189    }
190
191    #[test]
192    fn index_key_rejects_invalid_index_name() {
193        let key = IndexKey::empty(IndexId::max_storable());
194        let raw = key.to_raw();
195        let mut bytes = raw.as_bytes().to_vec();
196        bytes[0] = 0;
197        bytes[1] = 0;
198        let raw = RawIndexKey::from_bytes(Cow::Owned(bytes));
199        let err = IndexKey::try_from_raw(&raw).expect_err("invalid index name should fail");
200        assert!(err.contains("corrupted"));
201    }
202
203    #[test]
204    fn index_key_rejects_fingerprint_padding() {
205        let key = IndexKey::empty(IndexId::max_storable());
206        let raw = key.to_raw();
207        let values_offset = IndexName::STORED_SIZE_USIZE + 1;
208        let mut bytes = raw.as_bytes().to_vec();
209        bytes[values_offset] = 1;
210        let raw = RawIndexKey::from_bytes(Cow::Owned(bytes));
211        let err = IndexKey::try_from_raw(&raw).expect_err("padding should fail");
212        assert!(err.contains("corrupted"));
213    }
214
215    #[test]
216    #[expect(clippy::large_types_passed_by_value)]
217    fn index_key_ordering_matches_bytes() {
218        fn make_key(index_id: IndexId, value_count: u8, first: u8, second: u8) -> IndexKey {
219            let mut bytes = [0u8; IndexKey::STORED_SIZE_USIZE];
220
221            let name_bytes = index_id.0.to_bytes();
222            bytes[..name_bytes.len()].copy_from_slice(&name_bytes);
223
224            let mut offset = IndexName::STORED_SIZE_USIZE;
225            bytes[offset] = value_count;
226            offset += 1;
227
228            let mut values = [[0u8; 16]; MAX_INDEX_FIELDS];
229            values[0] = [first; 16];
230            values[1] = [second; 16];
231
232            for value in values {
233                bytes[offset..offset + 16].copy_from_slice(&value);
234                offset += 16;
235            }
236
237            let raw = RawIndexKey::from_bytes(Cow::Borrowed(&bytes));
238            IndexKey::try_from_raw(&raw).expect("valid key bytes should decode")
239        }
240
241        let entity = EntityName::try_from_str("entity").expect("entity name should parse");
242        let idx_a = IndexId(IndexName::try_from_parts(&entity, &["a"]).expect("index name"));
243        let idx_b = IndexId(IndexName::try_from_parts(&entity, &["b"]).expect("index name"));
244
245        let keys = vec![
246            make_key(idx_a, 1, 1, 0),
247            make_key(idx_a, 2, 1, 2),
248            make_key(idx_a, 1, 2, 0),
249            make_key(idx_b, 1, 0, 0),
250        ];
251
252        let mut sorted_by_ord = keys.clone();
253        sorted_by_ord.sort();
254
255        let mut sorted_by_bytes = keys;
256        sorted_by_bytes.sort_by(|a, b| a.to_raw().as_bytes().cmp(b.to_raw().as_bytes()));
257
258        assert_eq!(sorted_by_ord, sorted_by_bytes);
259    }
260
261    #[test]
262    #[expect(clippy::cast_possible_truncation)]
263    fn index_key_decode_fuzz_roundtrip_is_canonical() {
264        const RUNS: u64 = 1_000;
265
266        let mut seed = 0xBADC_0FFE_u64;
267        for _ in 0..RUNS {
268            let mut bytes = [0u8; IndexKey::STORED_SIZE_BYTES as usize];
269            for byte in &mut bytes {
270                seed = seed.wrapping_mul(6_364_136_223_846_793_005).wrapping_add(1);
271                *byte = (seed >> 24) as u8;
272            }
273
274            let raw = RawIndexKey::from_bytes(Cow::Borrowed(&bytes));
275            if let Ok(decoded) = IndexKey::try_from_raw(&raw) {
276                let reencoded = decoded.to_raw();
277                assert_eq!(raw.as_bytes(), reencoded.as_bytes());
278            }
279        }
280    }
281
282    #[test]
283    fn index_key_detects_system_namespace() {
284        let entity = EntityName::try_from_str("entity").expect("entity name should parse");
285
286        let user_id = IndexId(IndexName::try_from_parts(&entity, &["email"]).expect("index name"));
287        let user_key = IndexKey::empty(user_id);
288        assert!(!user_key.uses_system_namespace());
289
290        let system_id = IndexId(IndexName::try_from_parts(&entity, &["~ri"]).expect("index name"));
291        let system_key = IndexKey::empty(system_id);
292        assert!(system_key.uses_system_namespace());
293
294        let nested_system_id = IndexId(
295            IndexName::try_from_parts(&entity, &["email", "~ri_shadow"]).expect("index name"),
296        );
297        let nested_system_key = IndexKey::empty(nested_system_id);
298        assert!(nested_system_key.uses_system_namespace());
299    }
300}
icydb_core/db/index/key/codec.rs

icydb_core/db/index/key/
codec.rs
