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
28#[derive(Clone, Copy, Debug, PartialEq, Eq)]
30pub struct NativeRecordIdentity {
31 family: NativeRecordFamily,
32 owner: NativeRecordOwner,
33}
34
35impl NativeRecordIdentity {
36 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 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 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 pub(crate) fn encode_blob_prefix(
221 self,
222 bytes: &[u8],
223 control: &StorageReadControl,
224 ) -> VersionResult<BudgetedVec<u8>> {
225 self.encode_variable_prefix(bytes, super::NativeColumnType::Blob, 3, control)
226 }
227
228 pub(crate) fn encode_text_prefix(
230 self,
231 bytes: &[u8],
232 control: &StorageReadControl,
233 ) -> VersionResult<BudgetedVec<u8>> {
234 std::str::from_utf8(bytes).map_err(|_| invalid("native text prefix is not UTF-8"))?;
235 self.encode_variable_prefix(bytes, super::NativeColumnType::Text, 2, control)
236 }
237
238 fn encode_variable_prefix(
239 self,
240 bytes: &[u8],
241 kind: super::NativeColumnType,
242 tag: u8,
243 control: &StorageReadControl,
244 ) -> VersionResult<BudgetedVec<u8>> {
245 let layout = self.family.layout();
246 if layout.identity_columns.len() != 1
247 || layout.column_types[layout.identity_columns[0]] != kind
248 {
249 return Err(invalid(
250 "native variable prefix requires one matching identity column",
251 ));
252 }
253 let mut key = self.encode_prefix(&[], control)?;
254 key.push(tag)?;
255 escaped_prefix(&mut key, bytes, control)?;
256 Ok(key)
257 }
258
259 pub(super) fn decode_full(key: &[u8], control: &StorageReadControl) -> VersionResult<Self> {
261 Self::visit_key_components(key, control, |_, _| Ok(()))
262 }
263
264 pub(crate) fn visit_key_components(
266 key: &[u8],
267 control: &StorageReadControl,
268 visit: impl FnMut(usize, ValueRef<'_>) -> VersionResult<()>,
269 ) -> VersionResult<Self> {
270 let count = Self::decode(key)?.family.layout().identity_columns.len();
271 Self::visit_prefix_components(key, count, control, visit)
272 }
273
274 pub(crate) fn visit_prefix_components(
276 key: &[u8],
277 count: usize,
278 control: &StorageReadControl,
279 mut visit: impl FnMut(usize, ValueRef<'_>) -> VersionResult<()>,
280 ) -> VersionResult<Self> {
281 let identity = Self::decode(key)?;
282 if count > identity.family.layout().identity_columns.len() {
283 return Err(invalid("native prefix has too many components"));
284 }
285 let header = identity.encode_prefix(&[], control)?;
286 let mut input = &key[header.len()..];
287 for (component, &column) in identity
288 .family
289 .layout()
290 .identity_columns
291 .iter()
292 .take(count)
293 .enumerate()
294 {
295 control.cancellation().check()?;
296 let (&tag, rest) = input
297 .split_first()
298 .ok_or_else(|| invalid("truncated native key component"))?;
299 input = rest;
300 let mut bytes = BudgetedVec::new(control.memory());
301 let value = match tag {
302 1 => {
303 let (integer, rest) = input
304 .split_at_checked(8)
305 .ok_or_else(|| invalid("truncated native integer key"))?;
306 input = rest;
307 let ordered = u64::from_be_bytes(integer.try_into().expect("eight bytes"));
308 ValueRef::Integer(i64::from_be_bytes((ordered ^ (1 << 63)).to_be_bytes()))
309 }
310 2 | 3 => {
311 loop {
312 control.cancellation().check()?;
313 let (&byte, rest) = input
314 .split_first()
315 .ok_or_else(|| invalid("unterminated native binary key"))?;
316 input = rest;
317 if byte == 0 {
318 let (&escape, rest) = input
319 .split_first()
320 .ok_or_else(|| invalid("truncated native key escape"))?;
321 input = rest;
322 match escape {
323 0 => break,
324 255 => {}
325 _ => return Err(invalid("invalid native key escape")),
326 }
327 }
328 bytes.push(byte)?;
329 }
330 if tag == 2 {
331 std::str::from_utf8(&bytes)
332 .map_err(|_| invalid("native text key is not UTF-8"))?;
333 ValueRef::Text(&bytes)
334 } else {
335 ValueRef::Blob(&bytes)
336 }
337 }
338 _ => return Err(invalid("unknown native key component")),
339 };
340 if !identity.family.layout().column_types[column].accepts(value) {
341 return Err(invalid("native key component does not match its layout"));
342 }
343 visit(component, value)?;
344 }
345 if !input.is_empty() {
346 return Err(invalid("native key has trailing components"));
347 }
348 Ok(identity)
349 }
350}
351
352fn escaped_bytes(
353 output: &mut BudgetedVec<u8>,
354 bytes: &[u8],
355 control: &StorageReadControl,
356) -> VersionResult<()> {
357 escaped_prefix(output, bytes, control)?;
358 output.extend_from_slice(&[0, 0])?;
359 Ok(())
360}
361
362fn escaped_prefix(
363 output: &mut BudgetedVec<u8>,
364 bytes: &[u8],
365 control: &StorageReadControl,
366) -> VersionResult<()> {
367 output.reserve(
368 bytes
369 .len()
370 .checked_add(2)
371 .ok_or(MemoryError::SizeOverflow)?,
372 )?;
373 for chunk in bytes.chunks(1024) {
374 control.cancellation().check()?;
375 for &byte in chunk {
376 output.push(byte)?;
377 if byte == 0 {
378 output.push(255)?;
379 }
380 }
381 }
382 Ok(())
383}