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