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