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 => "definition_generation",
150            _ => return Ok(()),
151        };
152        let NativeRecordOwner::Object {
153            identity,
154            generation,
155        } = self.owner
156        else {
157            return Err(invalid("native definition requires an object owner"));
158        };
159        for (name, expected) in [("object_id", identity), (generation_column, generation)] {
160            let column = layout
161                .columns
162                .iter()
163                .position(|column| *column == name)
164                .ok_or_else(|| invalid("native definition layout lacks its identity column"))?;
165            if values[column] != ValueRef::Blob(&expected) {
166                return Err(invalid(
167                    "native definition does not match its owner generation",
168                ));
169            }
170        }
171        Ok(())
172    }
173
174    pub(crate) fn decode(key: &[u8]) -> VersionResult<Self> {
175        let bytes = key
176            .strip_prefix(PREFIX)
177            .ok_or_else(|| invalid("unknown native record key codec"))?;
178        let family_bytes = bytes
179            .get(..2)
180            .ok_or_else(|| invalid("truncated native record family"))?;
181        let family =
182            NativeRecordFamily::from_id(u16::from_be_bytes([family_bytes[0], family_bytes[1]]))
183                .ok_or_else(|| invalid("unknown native record family"))?;
184        let array = |start: usize| -> VersionResult<[u8; 16]> {
185            bytes
186                .get(start..start + 16)
187                .and_then(|slice| slice.try_into().ok())
188                .ok_or_else(|| invalid("truncated native record owner"))
189        };
190        let owner = match bytes.get(2) {
191            Some(0) => NativeRecordOwner::Database(DatabaseId::from_bytes(array(3)?)),
192            Some(1) => NativeRecordOwner::Object {
193                identity: array(3)?,
194                generation: array(19)?,
195            },
196            _ => return Err(invalid("unknown native record owner kind")),
197        };
198        Self::new(family, owner)
199    }
200
201    /// 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.
202    pub fn encode_key(
203        self,
204        components: &[ValueRef<'_>],
205        control: &StorageReadControl,
206    ) -> VersionResult<BudgetedVec<u8>> {
207        if components.len() != self.family.layout().identity_columns.len() {
208            return Err(invalid("native primary key does not match its layout"));
209        }
210        self.encode_prefix(components, control)
211    }
212
213    /// Encode an owner/component prefix for a bounded scan over this family and generation.
214    pub fn encode_prefix(
215        self,
216        components: &[ValueRef<'_>],
217        control: &StorageReadControl,
218    ) -> VersionResult<BudgetedVec<u8>> {
219        control.cancellation().check()?;
220        if components.len() > self.family.layout().identity_columns.len() {
221            return Err(invalid("native primary key prefix exceeds its layout"));
222        }
223        let mut key = Self::family_prefix(self.family, control)?;
224        match self.owner {
225            NativeRecordOwner::Database(database) => {
226                key.push(0)?;
227                key.extend_from_slice(&database.as_bytes())?;
228            }
229            NativeRecordOwner::Object {
230                identity,
231                generation,
232            } => {
233                key.push(1)?;
234                key.extend_from_slice(&identity)?;
235                key.extend_from_slice(&generation)?;
236            }
237        }
238        for (component, &column) in components.iter().zip(self.family.layout().identity_columns) {
239            control.cancellation().check()?;
240            let expected = self.family.layout().column_types[column];
241            if !expected.accepts(*component) {
242                return Err(invalid(
243                    "native primary key storage class does not match its layout",
244                ));
245            }
246            match component {
247                ValueRef::Integer(value) => {
248                    key.push(1)?;
249                    let ordered = u64::from_be_bytes(value.to_be_bytes()) ^ (1 << 63);
250                    key.extend_from_slice(&ordered.to_be_bytes())?;
251                }
252                ValueRef::Text(bytes) => {
253                    std::str::from_utf8(bytes)
254                        .map_err(|_| invalid("native text key is not UTF-8"))?;
255                    key.push(2)?;
256                    escaped_bytes(&mut key, bytes, control)?;
257                }
258                ValueRef::Blob(bytes) => {
259                    key.push(3)?;
260                    escaped_bytes(&mut key, bytes, control)?;
261                }
262                ValueRef::Null | ValueRef::Real(_) => {
263                    return Err(invalid("native primary key must be INTEGER, TEXT or BLOB"));
264                }
265            }
266        }
267        Ok(key)
268    }
269
270    /// Encode a byte prefix within a single BLOB key, without its component terminator. Complete keys retain the existing escaped byte order.
271    pub(crate) fn encode_blob_prefix(
272        self,
273        bytes: &[u8],
274        control: &StorageReadControl,
275    ) -> VersionResult<BudgetedVec<u8>> {
276        self.encode_variable_prefix(bytes, super::NativeColumnType::Blob, 3, control)
277    }
278
279    /// Encode a UTF-8 prefix within one TEXT identity, without a component terminator.
280    pub(crate) fn encode_text_prefix(
281        self,
282        bytes: &[u8],
283        control: &StorageReadControl,
284    ) -> VersionResult<BudgetedVec<u8>> {
285        std::str::from_utf8(bytes).map_err(|_| invalid("native text prefix is not UTF-8"))?;
286        self.encode_variable_prefix(bytes, super::NativeColumnType::Text, 2, control)
287    }
288
289    fn encode_variable_prefix(
290        self,
291        bytes: &[u8],
292        kind: super::NativeColumnType,
293        tag: u8,
294        control: &StorageReadControl,
295    ) -> VersionResult<BudgetedVec<u8>> {
296        let layout = self.family.layout();
297        if layout.identity_columns.len() != 1
298            || layout.column_types[layout.identity_columns[0]] != kind
299        {
300            return Err(invalid(
301                "native variable prefix requires one matching identity column",
302            ));
303        }
304        let mut key = self.encode_prefix(&[], control)?;
305        key.push(tag)?;
306        escaped_prefix(&mut key, bytes, control)?;
307        Ok(key)
308    }
309
310    /// Validate every ordered component, including keys for an absent tombstone.
311    pub(super) fn decode_full(key: &[u8], control: &StorageReadControl) -> VersionResult<Self> {
312        Self::visit_key_components(key, control, |_, _| Ok(()))
313    }
314
315    /// Decode ordered keys without loading row payloads. Borrowed component buffers are valid only during the callback.
316    pub(crate) fn visit_key_components(
317        key: &[u8],
318        control: &StorageReadControl,
319        visit: impl FnMut(usize, ValueRef<'_>) -> VersionResult<()>,
320    ) -> VersionResult<Self> {
321        let count = Self::decode(key)?.family.layout().identity_columns.len();
322        Self::visit_prefix_components(key, count, control, visit)
323    }
324
325    /// Validate an exact number of complete primary-key components in an encoded prefix.
326    pub(crate) fn visit_prefix_components(
327        key: &[u8],
328        count: usize,
329        control: &StorageReadControl,
330        mut visit: impl FnMut(usize, ValueRef<'_>) -> VersionResult<()>,
331    ) -> VersionResult<Self> {
332        let identity = Self::decode(key)?;
333        if count > identity.family.layout().identity_columns.len() {
334            return Err(invalid("native prefix has too many components"));
335        }
336        let header = identity.encode_prefix(&[], control)?;
337        let mut input = &key[header.len()..];
338        for (component, &column) in identity
339            .family
340            .layout()
341            .identity_columns
342            .iter()
343            .take(count)
344            .enumerate()
345        {
346            control.cancellation().check()?;
347            let (&tag, rest) = input
348                .split_first()
349                .ok_or_else(|| invalid("truncated native key component"))?;
350            input = rest;
351            let mut bytes = BudgetedVec::new(control.memory());
352            let value = match tag {
353                1 => {
354                    let (integer, rest) = input
355                        .split_at_checked(8)
356                        .ok_or_else(|| invalid("truncated native integer key"))?;
357                    input = rest;
358                    let ordered = u64::from_be_bytes(integer.try_into().expect("eight bytes"));
359                    ValueRef::Integer(i64::from_be_bytes((ordered ^ (1 << 63)).to_be_bytes()))
360                }
361                2 | 3 => {
362                    loop {
363                        control.cancellation().check()?;
364                        let (&byte, rest) = input
365                            .split_first()
366                            .ok_or_else(|| invalid("unterminated native binary key"))?;
367                        input = rest;
368                        if byte == 0 {
369                            let (&escape, rest) = input
370                                .split_first()
371                                .ok_or_else(|| invalid("truncated native key escape"))?;
372                            input = rest;
373                            match escape {
374                                0 => break,
375                                255 => {}
376                                _ => return Err(invalid("invalid native key escape")),
377                            }
378                        }
379                        bytes.push(byte)?;
380                    }
381                    if tag == 2 {
382                        std::str::from_utf8(&bytes)
383                            .map_err(|_| invalid("native text key is not UTF-8"))?;
384                        ValueRef::Text(&bytes)
385                    } else {
386                        ValueRef::Blob(&bytes)
387                    }
388                }
389                _ => return Err(invalid("unknown native key component")),
390            };
391            if !identity.family.layout().column_types[column].accepts(value) {
392                return Err(invalid("native key component does not match its layout"));
393            }
394            visit(component, value)?;
395        }
396        if !input.is_empty() {
397            return Err(invalid("native key has trailing components"));
398        }
399        Ok(identity)
400    }
401}
402
403fn consume(input: &mut &[u8], expected: &[u8]) -> bool {
404    if let Some(rest) = input.strip_prefix(expected) {
405        *input = rest;
406        true
407    } else {
408        false
409    }
410}
411
412fn matches_escaped(
413    input: &mut &[u8],
414    bytes: &[u8],
415    control: &StorageReadControl,
416) -> VersionResult<bool> {
417    for (index, &byte) in bytes.iter().enumerate() {
418        if index % 1024 == 0 {
419            control.cancellation().check()?;
420        }
421        if !consume(input, &[byte]) || (byte == 0 && !consume(input, &[255])) {
422            return Ok(false);
423        }
424    }
425    Ok(consume(input, &[0, 0]))
426}
427
428fn escaped_bytes(
429    output: &mut BudgetedVec<u8>,
430    bytes: &[u8],
431    control: &StorageReadControl,
432) -> VersionResult<()> {
433    escaped_prefix(output, bytes, control)?;
434    output.extend_from_slice(&[0, 0])?;
435    Ok(())
436}
437
438fn escaped_prefix(
439    output: &mut BudgetedVec<u8>,
440    bytes: &[u8],
441    control: &StorageReadControl,
442) -> VersionResult<()> {
443    output.reserve(
444        bytes
445            .len()
446            .checked_add(2)
447            .ok_or(MemoryError::SizeOverflow)?,
448    )?;
449    for chunk in bytes.chunks(1024) {
450        control.cancellation().check()?;
451        for &byte in chunk {
452            output.push(byte)?;
453            if byte == 0 {
454                output.push(255)?;
455            }
456        }
457    }
458    Ok(())
459}