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    /// Families with named or entity-specific invalidation retain their complete key. All other relevant families aggregate by their validated owner header; family IDs separate these scopes from complete keys of other families.
50    pub(crate) fn revision_scope(key: &[u8]) -> Option<&[u8]> {
51        use NativeRecordFamily as Family;
52
53        let Ok(identity) = Self::decode(key) else {
54            // Preserve malformed raw records for the existing read/publication validator.
55            return Some(key);
56        };
57        match identity.family {
58            family if family.is_standalone_graph() => return None,
59            Family::TableOwners
60            | Family::OccurrenceGuards
61            | Family::VectorGuards
62            | Family::GraphLookups
63            | Family::GraphPathPairs
64            | Family::GraphPathIndexState => return None,
65            Family::Metadata
66            | Family::NamedGraphs
67            | Family::GraphMembership
68            | Family::GraphVertices
69            | Family::GraphEdges => return Some(key),
70            _ => {}
71        }
72        let owner_bytes = match identity.owner {
73            NativeRecordOwner::Database(_) => 16,
74            NativeRecordOwner::Object { .. } => 32,
75        };
76        Some(&key[..PREFIX.len() + 2 + 1 + owner_bytes])
77    }
78
79    /// Address every retained generation of one object without scanning other object payloads.
80    pub(crate) fn object_prefix(
81        family: NativeRecordFamily,
82        identity: [u8; 16],
83        control: &StorageReadControl,
84    ) -> VersionResult<BudgetedVec<u8>> {
85        if !family.layout().object_owned || identity == [0; 16] {
86            return Err(invalid(
87                "native object prefix requires an assigned object identity",
88            ));
89        }
90        let mut key = Self::family_prefix(family, control)?;
91        key.push(1)?;
92        key.extend_from_slice(&identity)?;
93        Ok(key)
94    }
95
96    pub(crate) fn family_prefix(
97        family: NativeRecordFamily,
98        control: &StorageReadControl,
99    ) -> VersionResult<BudgetedVec<u8>> {
100        control.cancellation().check()?;
101        let mut key = BudgetedVec::new(control.memory());
102        key.extend_from_slice(PREFIX)?;
103        key.extend_from_slice(&family.id().to_be_bytes())?;
104        Ok(key)
105    }
106
107    pub fn new(family: NativeRecordFamily, owner: NativeRecordOwner) -> VersionResult<Self> {
108        if family.layout().object_owned != matches!(owner, NativeRecordOwner::Object { .. }) {
109            return Err(invalid("native family does not match its owner kind"));
110        }
111        if let NativeRecordOwner::Object {
112            identity,
113            generation,
114        } = owner
115        {
116            if identity == [0; 16] || generation == [0; 16] {
117                return Err(invalid(
118                    "native object identity and generation must be assigned",
119                ));
120            }
121        }
122        Ok(Self { family, owner })
123    }
124
125    pub fn family(self) -> NativeRecordFamily {
126        self.family
127    }
128
129    pub fn owner(self) -> NativeRecordOwner {
130        self.owner
131    }
132
133    /// Compare the canonical encoding directly, without allocating a second copy of a retained record key.
134    pub(super) fn matches_row_key(
135        self,
136        key: &[u8],
137        values: &[ValueRef<'_>],
138        control: &StorageReadControl,
139    ) -> VersionResult<bool> {
140        let owner_bytes = match self.owner {
141            NativeRecordOwner::Database(_) => 16,
142            NativeRecordOwner::Object { .. } => 32,
143        };
144        // decode_record already validated this exact family/owner header.
145        let mut input = &key[PREFIX.len() + 2 + 1 + owner_bytes..];
146        for &column in self.family.layout().identity_columns {
147            control.cancellation().check()?;
148            let matches = match values[column] {
149                ValueRef::Integer(value) => {
150                    let ordered = u64::from_be_bytes(value.to_be_bytes()) ^ (1 << 63);
151                    consume(&mut input, &[1]) && consume(&mut input, &ordered.to_be_bytes())
152                }
153                ValueRef::Text(bytes) => {
154                    consume(&mut input, &[2]) && matches_escaped(&mut input, bytes, control)?
155                }
156                ValueRef::Blob(bytes) => {
157                    consume(&mut input, &[3]) && matches_escaped(&mut input, bytes, control)?
158                }
159                ValueRef::Null | ValueRef::Real(_) => {
160                    return Err(invalid("native primary key must be INTEGER, TEXT or BLOB"));
161                }
162            };
163            if !matches {
164                return Ok(false);
165            }
166        }
167        control.cancellation().check()?;
168        Ok(input.is_empty())
169    }
170
171    pub(super) fn validate_row(self, values: &[ValueRef<'_>]) -> VersionResult<()> {
172        let layout = self.family.layout();
173        layout.validate_values(values)?;
174        if self.family.is_standalone_graph() {
175            super::standalone_graph::validate_values(self.family, values)?;
176        }
177        let generation_column = match self.family {
178            NativeRecordFamily::Tables => "storage_generation",
179            NativeRecordFamily::Sequences | NativeRecordFamily::SequenceValues => {
180                "definition_generation"
181            }
182            _ => return Ok(()),
183        };
184        let NativeRecordOwner::Object {
185            identity,
186            generation,
187        } = self.owner
188        else {
189            return Err(invalid("native definition requires an object owner"));
190        };
191        for (name, expected) in [("object_id", identity), (generation_column, generation)] {
192            let column = layout
193                .columns
194                .iter()
195                .position(|column| *column == name)
196                .ok_or_else(|| invalid("native definition layout lacks its identity column"))?;
197            if values[column] != ValueRef::Blob(&expected) {
198                return Err(invalid(
199                    "native definition does not match its owner generation",
200                ));
201            }
202        }
203        Ok(())
204    }
205
206    pub(crate) fn decode(key: &[u8]) -> VersionResult<Self> {
207        let bytes = key
208            .strip_prefix(PREFIX)
209            .ok_or_else(|| invalid("unknown native record key codec"))?;
210        let family_bytes = bytes
211            .get(..2)
212            .ok_or_else(|| invalid("truncated native record family"))?;
213        let family =
214            NativeRecordFamily::from_id(u16::from_be_bytes([family_bytes[0], family_bytes[1]]))
215                .ok_or_else(|| invalid("unknown native record family"))?;
216        let array = |start: usize| -> VersionResult<[u8; 16]> {
217            bytes
218                .get(start..start + 16)
219                .and_then(|slice| slice.try_into().ok())
220                .ok_or_else(|| invalid("truncated native record owner"))
221        };
222        let owner = match bytes.get(2) {
223            Some(0) => NativeRecordOwner::Database(DatabaseId::from_bytes(array(3)?)),
224            Some(1) => NativeRecordOwner::Object {
225                identity: array(3)?,
226                generation: array(19)?,
227            },
228            _ => return Err(invalid("unknown native record owner kind")),
229        };
230        Self::new(family, owner)
231    }
232
233    /// 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.
234    pub fn encode_key(
235        self,
236        components: &[ValueRef<'_>],
237        control: &StorageReadControl,
238    ) -> VersionResult<BudgetedVec<u8>> {
239        if components.len() != self.family.layout().identity_columns.len() {
240            return Err(invalid("native primary key does not match its layout"));
241        }
242        self.encode_prefix(components, control)
243    }
244
245    /// Encode an owner/component prefix for a bounded scan over this family and generation.
246    pub fn encode_prefix(
247        self,
248        components: &[ValueRef<'_>],
249        control: &StorageReadControl,
250    ) -> VersionResult<BudgetedVec<u8>> {
251        control.cancellation().check()?;
252        if components.len() > self.family.layout().identity_columns.len() {
253            return Err(invalid("native primary key prefix exceeds its layout"));
254        }
255        let mut key = Self::family_prefix(self.family, control)?;
256        match self.owner {
257            NativeRecordOwner::Database(database) => {
258                key.push(0)?;
259                key.extend_from_slice(&database.as_bytes())?;
260            }
261            NativeRecordOwner::Object {
262                identity,
263                generation,
264            } => {
265                key.push(1)?;
266                key.extend_from_slice(&identity)?;
267                key.extend_from_slice(&generation)?;
268            }
269        }
270        for (component, &column) in components.iter().zip(self.family.layout().identity_columns) {
271            control.cancellation().check()?;
272            let expected = self.family.layout().column_types[column];
273            if !expected.accepts(*component) {
274                return Err(invalid(
275                    "native primary key storage class does not match its layout",
276                ));
277            }
278            match component {
279                ValueRef::Integer(value) => {
280                    key.push(1)?;
281                    let ordered = u64::from_be_bytes(value.to_be_bytes()) ^ (1 << 63);
282                    key.extend_from_slice(&ordered.to_be_bytes())?;
283                }
284                ValueRef::Text(bytes) => {
285                    std::str::from_utf8(bytes)
286                        .map_err(|_| invalid("native text key is not UTF-8"))?;
287                    key.push(2)?;
288                    escaped_bytes(&mut key, bytes, control)?;
289                }
290                ValueRef::Blob(bytes) => {
291                    key.push(3)?;
292                    escaped_bytes(&mut key, bytes, control)?;
293                }
294                ValueRef::Null | ValueRef::Real(_) => {
295                    return Err(invalid("native primary key must be INTEGER, TEXT or BLOB"));
296                }
297            }
298        }
299        Ok(key)
300    }
301
302    /// Encode a byte prefix within a single BLOB key, without its component terminator. Complete keys retain the existing escaped byte order.
303    pub(crate) fn encode_blob_prefix(
304        self,
305        bytes: &[u8],
306        control: &StorageReadControl,
307    ) -> VersionResult<BudgetedVec<u8>> {
308        self.encode_variable_prefix(bytes, super::NativeColumnType::Blob, 3, control)
309    }
310
311    /// Encode a UTF-8 prefix within one TEXT identity, without a component terminator.
312    pub(crate) fn encode_text_prefix(
313        self,
314        bytes: &[u8],
315        control: &StorageReadControl,
316    ) -> VersionResult<BudgetedVec<u8>> {
317        std::str::from_utf8(bytes).map_err(|_| invalid("native text prefix is not UTF-8"))?;
318        self.encode_variable_prefix(bytes, super::NativeColumnType::Text, 2, control)
319    }
320
321    fn encode_variable_prefix(
322        self,
323        bytes: &[u8],
324        kind: super::NativeColumnType,
325        tag: u8,
326        control: &StorageReadControl,
327    ) -> VersionResult<BudgetedVec<u8>> {
328        let layout = self.family.layout();
329        if layout.identity_columns.len() != 1
330            || layout.column_types[layout.identity_columns[0]] != kind
331        {
332            return Err(invalid(
333                "native variable prefix requires one matching identity column",
334            ));
335        }
336        let mut key = self.encode_prefix(&[], control)?;
337        key.push(tag)?;
338        escaped_prefix(&mut key, bytes, control)?;
339        Ok(key)
340    }
341
342    /// Validate every ordered component, including keys for an absent tombstone.
343    pub(super) fn decode_full(key: &[u8], control: &StorageReadControl) -> VersionResult<Self> {
344        Self::visit_key_components(key, control, |_, _| Ok(()))
345    }
346
347    /// Decode ordered keys without loading row payloads. Borrowed component buffers are valid only during the callback.
348    pub(crate) fn visit_key_components(
349        key: &[u8],
350        control: &StorageReadControl,
351        visit: impl FnMut(usize, ValueRef<'_>) -> VersionResult<()>,
352    ) -> VersionResult<Self> {
353        let count = Self::decode(key)?.family.layout().identity_columns.len();
354        Self::visit_prefix_components(key, count, control, visit)
355    }
356
357    /// Validate an exact number of complete primary-key components in an encoded prefix.
358    pub(crate) fn visit_prefix_components(
359        key: &[u8],
360        count: usize,
361        control: &StorageReadControl,
362        mut visit: impl FnMut(usize, ValueRef<'_>) -> VersionResult<()>,
363    ) -> VersionResult<Self> {
364        let identity = Self::decode(key)?;
365        if count > identity.family.layout().identity_columns.len() {
366            return Err(invalid("native prefix has too many components"));
367        }
368        let header = identity.encode_prefix(&[], control)?;
369        let mut input = &key[header.len()..];
370        for (component, &column) in identity
371            .family
372            .layout()
373            .identity_columns
374            .iter()
375            .take(count)
376            .enumerate()
377        {
378            control.cancellation().check()?;
379            let (&tag, rest) = input
380                .split_first()
381                .ok_or_else(|| invalid("truncated native key component"))?;
382            input = rest;
383            let mut bytes = BudgetedVec::new(control.memory());
384            let value = match tag {
385                1 => {
386                    let (integer, rest) = input
387                        .split_at_checked(8)
388                        .ok_or_else(|| invalid("truncated native integer key"))?;
389                    input = rest;
390                    let ordered = u64::from_be_bytes(integer.try_into().expect("eight bytes"));
391                    ValueRef::Integer(i64::from_be_bytes((ordered ^ (1 << 63)).to_be_bytes()))
392                }
393                2 | 3 => {
394                    loop {
395                        control.cancellation().check()?;
396                        let (&byte, rest) = input
397                            .split_first()
398                            .ok_or_else(|| invalid("unterminated native binary key"))?;
399                        input = rest;
400                        if byte == 0 {
401                            let (&escape, rest) = input
402                                .split_first()
403                                .ok_or_else(|| invalid("truncated native key escape"))?;
404                            input = rest;
405                            match escape {
406                                0 => break,
407                                255 => {}
408                                _ => return Err(invalid("invalid native key escape")),
409                            }
410                        }
411                        bytes.push(byte)?;
412                    }
413                    if tag == 2 {
414                        std::str::from_utf8(&bytes)
415                            .map_err(|_| invalid("native text key is not UTF-8"))?;
416                        ValueRef::Text(&bytes)
417                    } else {
418                        ValueRef::Blob(&bytes)
419                    }
420                }
421                _ => return Err(invalid("unknown native key component")),
422            };
423            if !identity.family.layout().column_types[column].accepts(value) {
424                return Err(invalid("native key component does not match its layout"));
425            }
426            visit(component, value)?;
427        }
428        if !input.is_empty() {
429            return Err(invalid("native key has trailing components"));
430        }
431        Ok(identity)
432    }
433}
434
435fn consume(input: &mut &[u8], expected: &[u8]) -> bool {
436    if let Some(rest) = input.strip_prefix(expected) {
437        *input = rest;
438        true
439    } else {
440        false
441    }
442}
443
444fn matches_escaped(
445    input: &mut &[u8],
446    bytes: &[u8],
447    control: &StorageReadControl,
448) -> VersionResult<bool> {
449    for (index, &byte) in bytes.iter().enumerate() {
450        if index % 1024 == 0 {
451            control.cancellation().check()?;
452        }
453        if !consume(input, &[byte]) || (byte == 0 && !consume(input, &[255])) {
454            return Ok(false);
455        }
456    }
457    Ok(consume(input, &[0, 0]))
458}
459
460fn escaped_bytes(
461    output: &mut BudgetedVec<u8>,
462    bytes: &[u8],
463    control: &StorageReadControl,
464) -> VersionResult<()> {
465    escaped_prefix(output, bytes, control)?;
466    output.extend_from_slice(&[0, 0])?;
467    Ok(())
468}
469
470fn escaped_prefix(
471    output: &mut BudgetedVec<u8>,
472    bytes: &[u8],
473    control: &StorageReadControl,
474) -> VersionResult<()> {
475    output.reserve(
476        bytes
477            .len()
478            .checked_add(2)
479            .ok_or(MemoryError::SizeOverflow)?,
480    )?;
481    for chunk in bytes.chunks(1024) {
482        control.cancellation().check()?;
483        for &byte in chunk {
484            output.push(byte)?;
485            if byte == 0 {
486                output.push(255)?;
487            }
488        }
489    }
490    Ok(())
491}