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
93///
94/// RawIndexKey
95///
96/// Fixed-size, stable-memory representation of IndexKey.
97/// This is the form stored in BTreeMap keys.
98///
99
100#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
101pub struct RawIndexKey([u8; IndexKey::STORED_SIZE_USIZE]);
102
103impl RawIndexKey {
104    /// Borrow the raw byte representation.
105    #[must_use]
106    pub const fn as_bytes(&self) -> &[u8; IndexKey::STORED_SIZE_USIZE] {
107        &self.0
108    }
109}
110
111impl Storable for RawIndexKey {
112    fn to_bytes(&self) -> Cow<'_, [u8]> {
113        Cow::Borrowed(&self.0)
114    }
115
116    fn from_bytes(bytes: Cow<'_, [u8]>) -> Self {
117        let mut out = [0u8; IndexKey::STORED_SIZE_USIZE];
118        if bytes.len() == out.len() {
119            out.copy_from_slice(bytes.as_ref());
120        }
121        Self(out)
122    }
123
124    fn into_bytes(self) -> Vec<u8> {
125        self.0.to_vec()
126    }
127
128    #[expect(clippy::cast_possible_truncation)]
129    const BOUND: Bound = Bound::Bounded {
130        max_size: IndexKey::STORED_SIZE_BYTES as u32,
131        is_fixed_size: true,
132    };
133}
134
135///
136/// TESTS
137///
138
139#[cfg(test)]
140mod tests {
141    use crate::{
142        MAX_INDEX_FIELDS,
143        db::{
144            identity::{EntityName, IndexName},
145            index::{IndexId, IndexKey, RawIndexKey},
146        },
147        traits::Storable,
148    };
149    use std::borrow::Cow;
150
151    #[test]
152    fn index_key_rejects_undersized_bytes() {
153        let bytes = vec![0u8; IndexKey::STORED_SIZE_USIZE - 1];
154        let raw = RawIndexKey::from_bytes(Cow::Borrowed(&bytes));
155        let err = IndexKey::try_from_raw(&raw).expect_err("undersized key should fail");
156        assert!(err.contains("corrupted"));
157    }
158
159    #[test]
160    fn index_key_rejects_oversized_bytes() {
161        let bytes = vec![0u8; IndexKey::STORED_SIZE_USIZE + 1];
162        let raw = RawIndexKey::from_bytes(Cow::Borrowed(&bytes));
163        let err = IndexKey::try_from_raw(&raw).expect_err("oversized key should fail");
164        assert!(err.contains("corrupted"));
165    }
166
167    #[test]
168    #[allow(clippy::cast_possible_truncation)]
169    fn index_key_rejects_len_over_max() {
170        let key = IndexKey::empty(IndexId::max_storable());
171        let raw = key.to_raw();
172        let len_offset = IndexName::STORED_SIZE_BYTES as usize;
173        let mut bytes = raw.as_bytes().to_vec();
174        bytes[len_offset] = (MAX_INDEX_FIELDS as u8) + 1;
175        let raw = RawIndexKey::from_bytes(Cow::Owned(bytes));
176        let err = IndexKey::try_from_raw(&raw).expect_err("oversized length should fail");
177        assert!(err.contains("corrupted"));
178    }
179
180    #[test]
181    fn index_key_rejects_invalid_index_name() {
182        let key = IndexKey::empty(IndexId::max_storable());
183        let raw = key.to_raw();
184        let mut bytes = raw.as_bytes().to_vec();
185        bytes[0] = 0;
186        bytes[1] = 0;
187        let raw = RawIndexKey::from_bytes(Cow::Owned(bytes));
188        let err = IndexKey::try_from_raw(&raw).expect_err("invalid index name should fail");
189        assert!(err.contains("corrupted"));
190    }
191
192    #[test]
193    fn index_key_rejects_fingerprint_padding() {
194        let key = IndexKey::empty(IndexId::max_storable());
195        let raw = key.to_raw();
196        let values_offset = IndexName::STORED_SIZE_USIZE + 1;
197        let mut bytes = raw.as_bytes().to_vec();
198        bytes[values_offset] = 1;
199        let raw = RawIndexKey::from_bytes(Cow::Owned(bytes));
200        let err = IndexKey::try_from_raw(&raw).expect_err("padding should fail");
201        assert!(err.contains("corrupted"));
202    }
203
204    #[test]
205    #[expect(clippy::large_types_passed_by_value)]
206    fn index_key_ordering_matches_bytes() {
207        fn make_key(index_id: IndexId, value_count: u8, first: u8, second: u8) -> IndexKey {
208            let mut bytes = [0u8; IndexKey::STORED_SIZE_USIZE];
209
210            let name_bytes = index_id.0.to_bytes();
211            bytes[..name_bytes.len()].copy_from_slice(&name_bytes);
212
213            let mut offset = IndexName::STORED_SIZE_USIZE;
214            bytes[offset] = value_count;
215            offset += 1;
216
217            let mut values = [[0u8; 16]; MAX_INDEX_FIELDS];
218            values[0] = [first; 16];
219            values[1] = [second; 16];
220
221            for value in values {
222                bytes[offset..offset + 16].copy_from_slice(&value);
223                offset += 16;
224            }
225
226            let raw = RawIndexKey::from_bytes(Cow::Borrowed(&bytes));
227            IndexKey::try_from_raw(&raw).expect("valid key bytes should decode")
228        }
229
230        let entity = EntityName::try_from_str("entity").expect("entity name should parse");
231        let idx_a = IndexId(IndexName::try_from_parts(&entity, &["a"]).expect("index name"));
232        let idx_b = IndexId(IndexName::try_from_parts(&entity, &["b"]).expect("index name"));
233
234        let keys = vec![
235            make_key(idx_a, 1, 1, 0),
236            make_key(idx_a, 2, 1, 2),
237            make_key(idx_a, 1, 2, 0),
238            make_key(idx_b, 1, 0, 0),
239        ];
240
241        let mut sorted_by_ord = keys.clone();
242        sorted_by_ord.sort();
243
244        let mut sorted_by_bytes = keys;
245        sorted_by_bytes.sort_by(|a, b| a.to_raw().as_bytes().cmp(b.to_raw().as_bytes()));
246
247        assert_eq!(sorted_by_ord, sorted_by_bytes);
248    }
249
250    #[test]
251    #[expect(clippy::cast_possible_truncation)]
252    fn index_key_decode_fuzz_roundtrip_is_canonical() {
253        const RUNS: u64 = 1_000;
254
255        let mut seed = 0xBADC_0FFE_u64;
256        for _ in 0..RUNS {
257            let mut bytes = [0u8; IndexKey::STORED_SIZE_BYTES as usize];
258            for byte in &mut bytes {
259                seed = seed.wrapping_mul(6_364_136_223_846_793_005).wrapping_add(1);
260                *byte = (seed >> 24) as u8;
261            }
262
263            let raw = RawIndexKey::from_bytes(Cow::Borrowed(&bytes));
264            if let Ok(decoded) = IndexKey::try_from_raw(&raw) {
265                let reencoded = decoded.to_raw();
266                assert_eq!(raw.as_bytes(), reencoded.as_bytes());
267            }
268        }
269    }
270}
icydb_core/db/index/key/codec.rs

icydb_core/db/index/key/
codec.rs
