Skip to main content

uqa_storage_sqlite/mvcc/native/
key.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Ordered native record identities separate physical families, object incarnations and primary-key components.
8
9use rusqlite::types::ValueRef;
10use uqa_core::memory::{BudgetedVec, MemoryError};
11use uqa_storage::mvcc::{DatabaseId, VersionResult};
12use uqa_storage::read_control::StorageReadControl;
13
14use super::{invalid, NativeRecordFamily};
15
16const PREFIX: &[u8] = b"\0uqa-native-record\x01";
17
18/// The database incarnation owns global catalog/name records. Tuple and index records require the object's identity and storage generation, independently of its current SQL name.
19#[derive(Clone, Copy, Debug, PartialEq, Eq)]
20pub enum NativeRecordOwner {
21    Database(DatabaseId),
22    Object {
23        identity: [u8; 16],
24        generation: [u8; 16],
25    },
26}
27
28impl NativeRecordOwner {
29    /// Whether this owner's rows are the documents of `namespace`. An object's identity and storage generation key its rows and name the namespace of its document identities alike, so what the namespace's watermark shows about an identity holds for the rows of this owner and of no other.
30    pub(crate) fn stores(
31        self,
32        namespace: uqa_storage::document_store::identifiers::DocumentIdNamespace,
33    ) -> bool {
34        self == Self::Object {
35            identity: namespace.object,
36            generation: namespace.generation,
37        }
38    }
39}
40
41/// A provider-assigned physical family and stable owner. The durable family number must come from a fixed format registry, never schema enumeration order.
42#[derive(Clone, Copy, Debug, PartialEq, Eq)]
43pub struct NativeRecordIdentity {
44    family: NativeRecordFamily,
45    owner: NativeRecordOwner,
46}
47
48impl NativeRecordIdentity {
49    /// Address every retained generation of one object without scanning other object payloads.
50    pub(crate) fn object_prefix(
51        family: NativeRecordFamily,
52        identity: [u8; 16],
53        control: &StorageReadControl,
54    ) -> VersionResult<BudgetedVec<u8>> {
55        if !family.layout().object_owned || identity == [0; 16] {
56            return Err(invalid(
57                "native object prefix requires an assigned object identity",
58            ));
59        }
60        let mut key = Self::family_prefix(family, control)?;
61        key.push(1)?;
62        key.extend_from_slice(&identity)?;
63        Ok(key)
64    }
65
66    pub(crate) fn family_prefix(
67        family: NativeRecordFamily,
68        control: &StorageReadControl,
69    ) -> VersionResult<BudgetedVec<u8>> {
70        control.cancellation().check()?;
71        let mut key = BudgetedVec::new(control.memory());
72        key.extend_from_slice(PREFIX)?;
73        key.extend_from_slice(&family.id().to_be_bytes())?;
74        Ok(key)
75    }
76
77    pub fn new(family: NativeRecordFamily, owner: NativeRecordOwner) -> VersionResult<Self> {
78        if family.layout().object_owned != matches!(owner, NativeRecordOwner::Object { .. }) {
79            return Err(invalid("native family does not match its owner kind"));
80        }
81        if let NativeRecordOwner::Object {
82            identity,
83            generation,
84        } = owner
85        {
86            if identity == [0; 16] || generation == [0; 16] {
87                return Err(invalid(
88                    "native object identity and generation must be assigned",
89                ));
90            }
91        }
92        Ok(Self { family, owner })
93    }
94
95    pub fn family(self) -> NativeRecordFamily {
96        self.family
97    }
98
99    pub fn owner(self) -> NativeRecordOwner {
100        self.owner
101    }
102
103    /// Compare the canonical encoding directly, without allocating a second copy of a retained record key.
104    pub(super) fn matches_row_key(
105        self,
106        key: &[u8],
107        values: &[ValueRef<'_>],
108        control: &StorageReadControl,
109    ) -> VersionResult<bool> {
110        let owner_bytes = match self.owner {
111            NativeRecordOwner::Database(_) => 16,
112            NativeRecordOwner::Object { .. } => 32,
113        };
114        // decode_record already validated this exact family/owner header.
115        let mut input = &key[PREFIX.len() + 2 + 1 + owner_bytes..];
116        for &column in self.family.layout().identity_columns {
117            control.cancellation().check()?;
118            let matches = match values[column] {
119                ValueRef::Integer(value) => {
120                    let ordered = u64::from_be_bytes(value.to_be_bytes()) ^ (1 << 63);
121                    consume(&mut input, &[1]) && consume(&mut input, &ordered.to_be_bytes())
122                }
123                ValueRef::Text(bytes) => {
124                    consume(&mut input, &[2]) && matches_escaped(&mut input, bytes, control)?
125                }
126                ValueRef::Blob(bytes) => {
127                    consume(&mut input, &[3]) && matches_escaped(&mut input, bytes, control)?
128                }
129                ValueRef::Null | ValueRef::Real(_) => {
130                    return Err(invalid("native primary key must be INTEGER, TEXT or BLOB"));
131                }
132            };
133            if !matches {
134                return Ok(false);
135            }
136        }
137        control.cancellation().check()?;
138        Ok(input.is_empty())
139    }
140
141    pub(super) fn validate_row(self, values: &[ValueRef<'_>]) -> VersionResult<()> {
142        let layout = self.family.layout();
143        layout.validate_values(values)?;
144        if self.family.is_standalone_graph() {
145            super::standalone_graph::validate_values(self.family, values)?;
146        }
147        let generation_column = match self.family {
148            NativeRecordFamily::Tables => "storage_generation",
149            NativeRecordFamily::Sequences | NativeRecordFamily::SequenceValues => {
150                "definition_generation"
151            }
152            _ => return Ok(()),
153        };
154        let NativeRecordOwner::Object {
155            identity,
156            generation,
157        } = self.owner
158        else {
159            return Err(invalid("native definition requires an object owner"));
160        };
161        for (name, expected) in [("object_id", identity), (generation_column, generation)] {
162            let column = layout
163                .columns
164                .iter()
165                .position(|column| *column == name)
166                .ok_or_else(|| invalid("native definition layout lacks its identity column"))?;
167            if values[column] != ValueRef::Blob(&expected) {
168                return Err(invalid(
169                    "native definition does not match its owner generation",
170                ));
171            }
172        }
173        Ok(())
174    }
175
176    pub(crate) fn decode(key: &[u8]) -> VersionResult<Self> {
177        let bytes = key
178            .strip_prefix(PREFIX)
179            .ok_or_else(|| invalid("unknown native record key codec"))?;
180        let family_bytes = bytes
181            .get(..2)
182            .ok_or_else(|| invalid("truncated native record family"))?;
183        let family =
184            NativeRecordFamily::from_id(u16::from_be_bytes([family_bytes[0], family_bytes[1]]))
185                .ok_or_else(|| invalid("unknown native record family"))?;
186        let array = |start: usize| -> VersionResult<[u8; 16]> {
187            bytes
188                .get(start..start + 16)
189                .and_then(|slice| slice.try_into().ok())
190                .ok_or_else(|| invalid("truncated native record owner"))
191        };
192        let owner = match bytes.get(2) {
193            Some(0) => NativeRecordOwner::Database(DatabaseId::from_bytes(array(3)?)),
194            Some(1) => NativeRecordOwner::Object {
195                identity: array(3)?,
196                generation: array(19)?,
197            },
198            _ => return Err(invalid("unknown native record owner kind")),
199        };
200        Self::new(family, owner)
201    }
202
203    /// Encode a complete primary key. Integer order is signed `SQLite` order; TEXT and BLOB order is binary byte order. NULL/REAL primary keys require a different equality contract and are rejected.
204    pub fn encode_key(
205        self,
206        components: &[ValueRef<'_>],
207        control: &StorageReadControl,
208    ) -> VersionResult<BudgetedVec<u8>> {
209        if components.len() != self.family.layout().identity_columns.len() {
210            return Err(invalid("native primary key does not match its layout"));
211        }
212        self.encode_prefix(components, control)
213    }
214
215    /// Encode an owner/component prefix for a bounded scan over this family and generation.
216    pub fn encode_prefix(
217        self,
218        components: &[ValueRef<'_>],
219        control: &StorageReadControl,
220    ) -> VersionResult<BudgetedVec<u8>> {
221        control.cancellation().check()?;
222        if components.len() > self.family.layout().identity_columns.len() {
223            return Err(invalid("native primary key prefix exceeds its layout"));
224        }
225        let mut key = Self::family_prefix(self.family, control)?;
226        match self.owner {
227            NativeRecordOwner::Database(database) => {
228                key.push(0)?;
229                key.extend_from_slice(&database.as_bytes())?;
230            }
231            NativeRecordOwner::Object {
232                identity,
233                generation,
234            } => {
235                key.push(1)?;
236                key.extend_from_slice(&identity)?;
237                key.extend_from_slice(&generation)?;
238            }
239        }
240        for (component, &column) in components.iter().zip(self.family.layout().identity_columns) {
241            control.cancellation().check()?;
242            let expected = self.family.layout().column_types[column];
243            if !expected.accepts(*component) {
244                return Err(invalid(
245                    "native primary key storage class does not match its layout",
246                ));
247            }
248            match component {
249                ValueRef::Integer(value) => {
250                    key.push(1)?;
251                    let ordered = u64::from_be_bytes(value.to_be_bytes()) ^ (1 << 63);
252                    key.extend_from_slice(&ordered.to_be_bytes())?;
253                }
254                ValueRef::Text(bytes) => {
255                    std::str::from_utf8(bytes)
256                        .map_err(|_| invalid("native text key is not UTF-8"))?;
257                    key.push(2)?;
258                    escaped_bytes(&mut key, bytes, control)?;
259                }
260                ValueRef::Blob(bytes) => {
261                    key.push(3)?;
262                    escaped_bytes(&mut key, bytes, control)?;
263                }
264                ValueRef::Null | ValueRef::Real(_) => {
265                    return Err(invalid("native primary key must be INTEGER, TEXT or BLOB"));
266                }
267            }
268        }
269        Ok(key)
270    }
271
272    /// Encode a byte prefix within a single BLOB key, without its component terminator. Complete keys retain the existing escaped byte order.
273    pub(crate) fn encode_blob_prefix(
274        self,
275        bytes: &[u8],
276        control: &StorageReadControl,
277    ) -> VersionResult<BudgetedVec<u8>> {
278        self.encode_variable_prefix(bytes, super::NativeColumnType::Blob, 3, control)
279    }
280
281    /// Encode a UTF-8 prefix within one TEXT identity, without a component terminator.
282    pub(crate) fn encode_text_prefix(
283        self,
284        bytes: &[u8],
285        control: &StorageReadControl,
286    ) -> VersionResult<BudgetedVec<u8>> {
287        std::str::from_utf8(bytes).map_err(|_| invalid("native text prefix is not UTF-8"))?;
288        self.encode_variable_prefix(bytes, super::NativeColumnType::Text, 2, control)
289    }
290
291    fn encode_variable_prefix(
292        self,
293        bytes: &[u8],
294        kind: super::NativeColumnType,
295        tag: u8,
296        control: &StorageReadControl,
297    ) -> VersionResult<BudgetedVec<u8>> {
298        let layout = self.family.layout();
299        if layout.identity_columns.len() != 1
300            || layout.column_types[layout.identity_columns[0]] != kind
301        {
302            return Err(invalid(
303                "native variable prefix requires one matching identity column",
304            ));
305        }
306        let mut key = self.encode_prefix(&[], control)?;
307        key.push(tag)?;
308        escaped_prefix(&mut key, bytes, control)?;
309        Ok(key)
310    }
311
312    /// Validate every ordered component, including keys for an absent tombstone.
313    pub(super) fn decode_full(key: &[u8], control: &StorageReadControl) -> VersionResult<Self> {
314        Self::visit_key_components(key, control, |_, _| Ok(()))
315    }
316
317    /// Decode ordered keys without loading row payloads. Borrowed component buffers are valid only during the callback.
318    pub(crate) fn visit_key_components(
319        key: &[u8],
320        control: &StorageReadControl,
321        visit: impl FnMut(usize, ValueRef<'_>) -> VersionResult<()>,
322    ) -> VersionResult<Self> {
323        let count = Self::decode(key)?.family.layout().identity_columns.len();
324        Self::visit_prefix_components(key, count, control, visit)
325    }
326
327    /// Validate an exact number of complete primary-key components in an encoded prefix.
328    pub(crate) fn visit_prefix_components(
329        key: &[u8],
330        count: usize,
331        control: &StorageReadControl,
332        mut visit: impl FnMut(usize, ValueRef<'_>) -> VersionResult<()>,
333    ) -> VersionResult<Self> {
334        let identity = Self::decode(key)?;
335        if count > identity.family.layout().identity_columns.len() {
336            return Err(invalid("native prefix has too many components"));
337        }
338        let header = identity.encode_prefix(&[], control)?;
339        let mut input = &key[header.len()..];
340        for (component, &column) in identity
341            .family
342            .layout()
343            .identity_columns
344            .iter()
345            .take(count)
346            .enumerate()
347        {
348            control.cancellation().check()?;
349            let (&tag, rest) = input
350                .split_first()
351                .ok_or_else(|| invalid("truncated native key component"))?;
352            input = rest;
353            let mut bytes = BudgetedVec::new(control.memory());
354            let value = match tag {
355                1 => {
356                    let (integer, rest) = input
357                        .split_at_checked(8)
358                        .ok_or_else(|| invalid("truncated native integer key"))?;
359                    input = rest;
360                    let ordered = u64::from_be_bytes(integer.try_into().expect("eight bytes"));
361                    ValueRef::Integer(i64::from_be_bytes((ordered ^ (1 << 63)).to_be_bytes()))
362                }
363                2 | 3 => {
364                    loop {
365                        control.cancellation().check()?;
366                        let (&byte, rest) = input
367                            .split_first()
368                            .ok_or_else(|| invalid("unterminated native binary key"))?;
369                        input = rest;
370                        if byte == 0 {
371                            let (&escape, rest) = input
372                                .split_first()
373                                .ok_or_else(|| invalid("truncated native key escape"))?;
374                            input = rest;
375                            match escape {
376                                0 => break,
377                                255 => {}
378                                _ => return Err(invalid("invalid native key escape")),
379                            }
380                        }
381                        bytes.push(byte)?;
382                    }
383                    if tag == 2 {
384                        std::str::from_utf8(&bytes)
385                            .map_err(|_| invalid("native text key is not UTF-8"))?;
386                        ValueRef::Text(&bytes)
387                    } else {
388                        ValueRef::Blob(&bytes)
389                    }
390                }
391                _ => return Err(invalid("unknown native key component")),
392            };
393            if !identity.family.layout().column_types[column].accepts(value) {
394                return Err(invalid("native key component does not match its layout"));
395            }
396            visit(component, value)?;
397        }
398        if !input.is_empty() {
399            return Err(invalid("native key has trailing components"));
400        }
401        Ok(identity)
402    }
403}
404
405fn consume(input: &mut &[u8], expected: &[u8]) -> bool {
406    if let Some(rest) = input.strip_prefix(expected) {
407        *input = rest;
408        true
409    } else {
410        false
411    }
412}
413
414fn matches_escaped(
415    input: &mut &[u8],
416    bytes: &[u8],
417    control: &StorageReadControl,
418) -> VersionResult<bool> {
419    for (index, &byte) in bytes.iter().enumerate() {
420        if index % 1024 == 0 {
421            control.cancellation().check()?;
422        }
423        if !consume(input, &[byte]) || (byte == 0 && !consume(input, &[255])) {
424            return Ok(false);
425        }
426    }
427    Ok(consume(input, &[0, 0]))
428}
429
430fn escaped_bytes(
431    output: &mut BudgetedVec<u8>,
432    bytes: &[u8],
433    control: &StorageReadControl,
434) -> VersionResult<()> {
435    escaped_prefix(output, bytes, control)?;
436    output.extend_from_slice(&[0, 0])?;
437    Ok(())
438}
439
440fn escaped_prefix(
441    output: &mut BudgetedVec<u8>,
442    bytes: &[u8],
443    control: &StorageReadControl,
444) -> VersionResult<()> {
445    output.reserve(
446        bytes
447            .len()
448            .checked_add(2)
449            .ok_or(MemoryError::SizeOverflow)?,
450    )?;
451    for chunk in bytes.chunks(1024) {
452        control.cancellation().check()?;
453        for &byte in chunk {
454            output.push(byte)?;
455            if byte == 0 {
456                output.push(255)?;
457            }
458        }
459    }
460    Ok(())
461}