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    /// Validate every ordered component, including keys for an absent tombstone.
220    pub(super) fn decode_full(key: &[u8], control: &StorageReadControl) -> VersionResult<Self> {
221        Self::visit_key_components(key, control, |_, _| Ok(()))
222    }
223
224    /// Decode ordered keys without loading row payloads. Borrowed component buffers are valid only during the callback.
225    pub(crate) fn visit_key_components(
226        key: &[u8],
227        control: &StorageReadControl,
228        mut visit: impl FnMut(usize, ValueRef<'_>) -> VersionResult<()>,
229    ) -> VersionResult<Self> {
230        let identity = Self::decode(key)?;
231        let header = identity.encode_prefix(&[], control)?;
232        let mut input = &key[header.len()..];
233        for (component, &column) in identity.family.layout().identity_columns.iter().enumerate() {
234            control.cancellation().check()?;
235            let (&tag, rest) = input
236                .split_first()
237                .ok_or_else(|| invalid("truncated native key component"))?;
238            input = rest;
239            let mut bytes = BudgetedVec::new(control.memory());
240            let value = match tag {
241                1 => {
242                    let (integer, rest) = input
243                        .split_at_checked(8)
244                        .ok_or_else(|| invalid("truncated native integer key"))?;
245                    input = rest;
246                    let ordered = u64::from_be_bytes(integer.try_into().expect("eight bytes"));
247                    ValueRef::Integer(i64::from_be_bytes((ordered ^ (1 << 63)).to_be_bytes()))
248                }
249                2 | 3 => {
250                    loop {
251                        control.cancellation().check()?;
252                        let (&byte, rest) = input
253                            .split_first()
254                            .ok_or_else(|| invalid("unterminated native binary key"))?;
255                        input = rest;
256                        if byte == 0 {
257                            let (&escape, rest) = input
258                                .split_first()
259                                .ok_or_else(|| invalid("truncated native key escape"))?;
260                            input = rest;
261                            match escape {
262                                0 => break,
263                                255 => {}
264                                _ => return Err(invalid("invalid native key escape")),
265                            }
266                        }
267                        bytes.push(byte)?;
268                    }
269                    if tag == 2 {
270                        std::str::from_utf8(&bytes)
271                            .map_err(|_| invalid("native text key is not UTF-8"))?;
272                        ValueRef::Text(&bytes)
273                    } else {
274                        ValueRef::Blob(&bytes)
275                    }
276                }
277                _ => return Err(invalid("unknown native key component")),
278            };
279            if !identity.family.layout().column_types[column].accepts(value) {
280                return Err(invalid("native key component does not match its layout"));
281            }
282            visit(component, value)?;
283        }
284        if !input.is_empty() {
285            return Err(invalid("native key has trailing components"));
286        }
287        Ok(identity)
288    }
289}
290
291fn escaped_bytes(
292    output: &mut BudgetedVec<u8>,
293    bytes: &[u8],
294    control: &StorageReadControl,
295) -> VersionResult<()> {
296    output.reserve(
297        bytes
298            .len()
299            .checked_add(2)
300            .ok_or(MemoryError::SizeOverflow)?,
301    )?;
302    for chunk in bytes.chunks(1024) {
303        control.cancellation().check()?;
304        for &byte in chunk {
305            output.push(byte)?;
306            if byte == 0 {
307                output.push(255)?;
308            }
309        }
310    }
311    output.extend_from_slice(&[0, 0])?;
312    Ok(())
313}