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