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
28/// A provider-assigned physical family and stable owner. The durable family number must come from a fixed format registry, never schema enumeration order.
29#[derive(Clone, Copy, Debug, PartialEq, Eq)]
30pub struct NativeRecordIdentity {
31    family: NativeRecordFamily,
32    owner: NativeRecordOwner,
33}
34
35impl NativeRecordIdentity {
36    /// Address every retained generation of one object without scanning other object payloads.
37    pub(crate) fn object_prefix(
38        family: NativeRecordFamily,
39        identity: [u8; 16],
40        control: &StorageReadControl,
41    ) -> VersionResult<BudgetedVec<u8>> {
42        if !family.layout().object_owned || identity == [0; 16] {
43            return Err(invalid(
44                "native object prefix requires an assigned object identity",
45            ));
46        }
47        let mut key = Self::family_prefix(family, control)?;
48        key.push(1)?;
49        key.extend_from_slice(&identity)?;
50        Ok(key)
51    }
52
53    pub(crate) fn family_prefix(
54        family: NativeRecordFamily,
55        control: &StorageReadControl,
56    ) -> VersionResult<BudgetedVec<u8>> {
57        control.cancellation().check()?;
58        let mut key = BudgetedVec::new(control.memory());
59        key.extend_from_slice(PREFIX)?;
60        key.extend_from_slice(&family.id().to_be_bytes())?;
61        Ok(key)
62    }
63
64    pub fn new(family: NativeRecordFamily, owner: NativeRecordOwner) -> VersionResult<Self> {
65        if family.layout().object_owned != matches!(owner, NativeRecordOwner::Object { .. }) {
66            return Err(invalid("native family does not match its owner kind"));
67        }
68        if let NativeRecordOwner::Object {
69            identity,
70            generation,
71        } = owner
72        {
73            if identity == [0; 16] || generation == [0; 16] {
74                return Err(invalid(
75                    "native object identity and generation must be assigned",
76                ));
77            }
78        }
79        Ok(Self { family, owner })
80    }
81
82    pub fn family(self) -> NativeRecordFamily {
83        self.family
84    }
85
86    pub fn owner(self) -> NativeRecordOwner {
87        self.owner
88    }
89
90    pub(super) fn validate_row(self, values: &[ValueRef<'_>]) -> VersionResult<()> {
91        let layout = self.family.layout();
92        layout.validate_values(values)?;
93        if self.family.is_standalone_graph() {
94            super::standalone_graph::validate_values(self.family, values)?;
95        }
96        let generation_column = match self.family {
97            NativeRecordFamily::Tables => "storage_generation",
98            NativeRecordFamily::Sequences => "definition_generation",
99            _ => return Ok(()),
100        };
101        let NativeRecordOwner::Object {
102            identity,
103            generation,
104        } = self.owner
105        else {
106            return Err(invalid("native definition requires an object owner"));
107        };
108        for (name, expected) in [("object_id", identity), (generation_column, generation)] {
109            let column = layout
110                .columns
111                .iter()
112                .position(|column| *column == name)
113                .ok_or_else(|| invalid("native definition layout lacks its identity column"))?;
114            if values[column] != ValueRef::Blob(&expected) {
115                return Err(invalid(
116                    "native definition does not match its owner generation",
117                ));
118            }
119        }
120        Ok(())
121    }
122
123    pub(crate) fn decode(key: &[u8]) -> VersionResult<Self> {
124        let bytes = key
125            .strip_prefix(PREFIX)
126            .ok_or_else(|| invalid("unknown native record key codec"))?;
127        let family_bytes = bytes
128            .get(..2)
129            .ok_or_else(|| invalid("truncated native record family"))?;
130        let family =
131            NativeRecordFamily::from_id(u16::from_be_bytes([family_bytes[0], family_bytes[1]]))
132                .ok_or_else(|| invalid("unknown native record family"))?;
133        let array = |start: usize| -> VersionResult<[u8; 16]> {
134            bytes
135                .get(start..start + 16)
136                .and_then(|slice| slice.try_into().ok())
137                .ok_or_else(|| invalid("truncated native record owner"))
138        };
139        let owner = match bytes.get(2) {
140            Some(0) => NativeRecordOwner::Database(DatabaseId::from_bytes(array(3)?)),
141            Some(1) => NativeRecordOwner::Object {
142                identity: array(3)?,
143                generation: array(19)?,
144            },
145            _ => return Err(invalid("unknown native record owner kind")),
146        };
147        Self::new(family, owner)
148    }
149
150    /// 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.
151    pub fn encode_key(
152        self,
153        components: &[ValueRef<'_>],
154        control: &StorageReadControl,
155    ) -> VersionResult<BudgetedVec<u8>> {
156        if components.len() != self.family.layout().identity_columns.len() {
157            return Err(invalid("native primary key does not match its layout"));
158        }
159        self.encode_prefix(components, control)
160    }
161
162    /// Encode an owner/component prefix for a bounded scan over this family and generation.
163    pub fn encode_prefix(
164        self,
165        components: &[ValueRef<'_>],
166        control: &StorageReadControl,
167    ) -> VersionResult<BudgetedVec<u8>> {
168        control.cancellation().check()?;
169        if components.len() > self.family.layout().identity_columns.len() {
170            return Err(invalid("native primary key prefix exceeds its layout"));
171        }
172        let mut key = Self::family_prefix(self.family, control)?;
173        match self.owner {
174            NativeRecordOwner::Database(database) => {
175                key.push(0)?;
176                key.extend_from_slice(&database.as_bytes())?;
177            }
178            NativeRecordOwner::Object {
179                identity,
180                generation,
181            } => {
182                key.push(1)?;
183                key.extend_from_slice(&identity)?;
184                key.extend_from_slice(&generation)?;
185            }
186        }
187        for (component, &column) in components.iter().zip(self.family.layout().identity_columns) {
188            control.cancellation().check()?;
189            let expected = self.family.layout().column_types[column];
190            if !expected.accepts(*component) {
191                return Err(invalid(
192                    "native primary key storage class does not match its layout",
193                ));
194            }
195            match component {
196                ValueRef::Integer(value) => {
197                    key.push(1)?;
198                    let ordered = u64::from_be_bytes(value.to_be_bytes()) ^ (1 << 63);
199                    key.extend_from_slice(&ordered.to_be_bytes())?;
200                }
201                ValueRef::Text(bytes) => {
202                    std::str::from_utf8(bytes)
203                        .map_err(|_| invalid("native text key is not UTF-8"))?;
204                    key.push(2)?;
205                    escaped_bytes(&mut key, bytes, control)?;
206                }
207                ValueRef::Blob(bytes) => {
208                    key.push(3)?;
209                    escaped_bytes(&mut key, bytes, control)?;
210                }
211                ValueRef::Null | ValueRef::Real(_) => {
212                    return Err(invalid("native primary key must be INTEGER, TEXT or BLOB"));
213                }
214            }
215        }
216        Ok(key)
217    }
218
219    /// Encode a byte prefix within a single BLOB key, without its component terminator. Complete keys retain the existing escaped byte order.
220    pub(crate) fn encode_blob_prefix(
221        self,
222        bytes: &[u8],
223        control: &StorageReadControl,
224    ) -> VersionResult<BudgetedVec<u8>> {
225        self.encode_variable_prefix(bytes, super::NativeColumnType::Blob, 3, control)
226    }
227
228    /// Encode a UTF-8 prefix within one TEXT identity, without a component terminator.
229    pub(crate) fn encode_text_prefix(
230        self,
231        bytes: &[u8],
232        control: &StorageReadControl,
233    ) -> VersionResult<BudgetedVec<u8>> {
234        std::str::from_utf8(bytes).map_err(|_| invalid("native text prefix is not UTF-8"))?;
235        self.encode_variable_prefix(bytes, super::NativeColumnType::Text, 2, control)
236    }
237
238    fn encode_variable_prefix(
239        self,
240        bytes: &[u8],
241        kind: super::NativeColumnType,
242        tag: u8,
243        control: &StorageReadControl,
244    ) -> VersionResult<BudgetedVec<u8>> {
245        let layout = self.family.layout();
246        if layout.identity_columns.len() != 1
247            || layout.column_types[layout.identity_columns[0]] != kind
248        {
249            return Err(invalid(
250                "native variable prefix requires one matching identity column",
251            ));
252        }
253        let mut key = self.encode_prefix(&[], control)?;
254        key.push(tag)?;
255        escaped_prefix(&mut key, bytes, control)?;
256        Ok(key)
257    }
258
259    /// Validate every ordered component, including keys for an absent tombstone.
260    pub(super) fn decode_full(key: &[u8], control: &StorageReadControl) -> VersionResult<Self> {
261        Self::visit_key_components(key, control, |_, _| Ok(()))
262    }
263
264    /// Decode ordered keys without loading row payloads. Borrowed component buffers are valid only during the callback.
265    pub(crate) fn visit_key_components(
266        key: &[u8],
267        control: &StorageReadControl,
268        visit: impl FnMut(usize, ValueRef<'_>) -> VersionResult<()>,
269    ) -> VersionResult<Self> {
270        let count = Self::decode(key)?.family.layout().identity_columns.len();
271        Self::visit_prefix_components(key, count, control, visit)
272    }
273
274    /// Validate an exact number of complete primary-key components in an encoded prefix.
275    pub(crate) fn visit_prefix_components(
276        key: &[u8],
277        count: usize,
278        control: &StorageReadControl,
279        mut visit: impl FnMut(usize, ValueRef<'_>) -> VersionResult<()>,
280    ) -> VersionResult<Self> {
281        let identity = Self::decode(key)?;
282        if count > identity.family.layout().identity_columns.len() {
283            return Err(invalid("native prefix has too many components"));
284        }
285        let header = identity.encode_prefix(&[], control)?;
286        let mut input = &key[header.len()..];
287        for (component, &column) in identity
288            .family
289            .layout()
290            .identity_columns
291            .iter()
292            .take(count)
293            .enumerate()
294        {
295            control.cancellation().check()?;
296            let (&tag, rest) = input
297                .split_first()
298                .ok_or_else(|| invalid("truncated native key component"))?;
299            input = rest;
300            let mut bytes = BudgetedVec::new(control.memory());
301            let value = match tag {
302                1 => {
303                    let (integer, rest) = input
304                        .split_at_checked(8)
305                        .ok_or_else(|| invalid("truncated native integer key"))?;
306                    input = rest;
307                    let ordered = u64::from_be_bytes(integer.try_into().expect("eight bytes"));
308                    ValueRef::Integer(i64::from_be_bytes((ordered ^ (1 << 63)).to_be_bytes()))
309                }
310                2 | 3 => {
311                    loop {
312                        control.cancellation().check()?;
313                        let (&byte, rest) = input
314                            .split_first()
315                            .ok_or_else(|| invalid("unterminated native binary key"))?;
316                        input = rest;
317                        if byte == 0 {
318                            let (&escape, rest) = input
319                                .split_first()
320                                .ok_or_else(|| invalid("truncated native key escape"))?;
321                            input = rest;
322                            match escape {
323                                0 => break,
324                                255 => {}
325                                _ => return Err(invalid("invalid native key escape")),
326                            }
327                        }
328                        bytes.push(byte)?;
329                    }
330                    if tag == 2 {
331                        std::str::from_utf8(&bytes)
332                            .map_err(|_| invalid("native text key is not UTF-8"))?;
333                        ValueRef::Text(&bytes)
334                    } else {
335                        ValueRef::Blob(&bytes)
336                    }
337                }
338                _ => return Err(invalid("unknown native key component")),
339            };
340            if !identity.family.layout().column_types[column].accepts(value) {
341                return Err(invalid("native key component does not match its layout"));
342            }
343            visit(component, value)?;
344        }
345        if !input.is_empty() {
346            return Err(invalid("native key has trailing components"));
347        }
348        Ok(identity)
349    }
350}
351
352fn escaped_bytes(
353    output: &mut BudgetedVec<u8>,
354    bytes: &[u8],
355    control: &StorageReadControl,
356) -> VersionResult<()> {
357    escaped_prefix(output, bytes, control)?;
358    output.extend_from_slice(&[0, 0])?;
359    Ok(())
360}
361
362fn escaped_prefix(
363    output: &mut BudgetedVec<u8>,
364    bytes: &[u8],
365    control: &StorageReadControl,
366) -> VersionResult<()> {
367    output.reserve(
368        bytes
369            .len()
370            .checked_add(2)
371            .ok_or(MemoryError::SizeOverflow)?,
372    )?;
373    for chunk in bytes.chunks(1024) {
374        control.cancellation().check()?;
375        for &byte in chunk {
376            output.push(byte)?;
377            if byte == 0 {
378                output.push(255)?;
379            }
380        }
381    }
382    Ok(())
383}