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