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