1use crate::{
5 __private::RowInfo, Entity, EntitySchema, Error, FieldType, IndexValue, PrimaryKey, Schema,
6 key, primary::RowKey, store_key::StoreKey,
7};
8use ic_storage::{
9 Memory, RuntimeMemory,
10 adapter::{MapIter, StableBTreeMap},
11};
12use std::collections::{BTreeMap, BTreeSet};
13
14mod maintenance;
15mod query;
16pub use maintenance::{CopyStep, Maintenance, RetiredSource, SchemaCopy, SchemaTransition};
17pub use query::{
18 Aggregate, AggregateJobs, Comparison, GroupCount, GroupCursor, GroupOrder, GroupPage,
19 GroupValue, JobHandle, JobOutcome, JobStep, Query, QueryCursor, QueryOperand, QueryPage,
20 SortDirection,
21};
22
23const MANIFEST: &[u8] = b"ICDBMF02";
24const MAX_BATCH: usize = 32;
25const MAX_BATCH_BYTES: usize = 128 * 1024;
26type Map<M> = StableBTreeMap<StoreKey, Vec<u8>, M>;
27
28#[inline(never)]
31fn next_primary<M: Memory>(
32 entries: &mut MapIter<'_, StoreKey, Vec<u8>, M>,
33 prefix: &[u8],
34 key_type: FieldType,
35) -> Result<Option<(RowKey, Vec<u8>)>, Error> {
36 let Some(entry) = entries.next() else {
37 return Ok(None);
38 };
39 if !entry.key().starts_with(prefix) {
40 return Ok(None);
41 }
42 let id = RowKey::decode(&entry.key()[5..], key_type)?;
43 Ok(Some((id, entry.value())))
44}
45
46#[inline(never)]
48fn next_index<M: Memory>(
49 map: &Map<M>,
50 entries: &mut MapIter<'_, StoreKey, Vec<u8>, M>,
51 prefix: &[u8],
52 entity: u32,
53 key_type: FieldType,
54) -> Result<Option<(StoreKey, RowKey, Vec<u8>)>, Error> {
55 let Some(entry) = entries.next() else {
56 return Ok(None);
57 };
58 if !entry.key().starts_with(prefix) {
59 return Ok(None);
60 }
61 let id = RowKey::decode(&entry.value(), key_type)?;
62 let bytes = map.get(&row_key(entity, id)).ok_or(Error::Corrupt)?;
63 Ok(Some((entry.key().clone(), id, bytes)))
64}
65
66#[inline(never)]
67fn index_prefix_key(
68 entity: &EntitySchema,
69 index: &str,
70 values: &[IndexValue<'_>],
71 limit: usize,
72) -> Result<StoreKey, Error> {
73 let index = entity
74 .indexes
75 .iter()
76 .find(|value| value.name == index)
77 .ok_or(Error::InvalidSchema)?;
78 if values.is_empty() || values.len() > index.fields.len() || !(1..=32).contains(&limit) {
79 return Err(Error::Limit);
80 }
81 StoreKey::new(admit_index_prefix(entity, index, values)?)
82}
83
84fn collect_references(
87 entity: &EntitySchema,
88 info: &RowInfo,
89 required: &mut BTreeSet<(u32, RowKey)>,
90) -> Result<(), Error> {
91 for field in entity.fields {
92 if let Some(reference) = field.reference {
93 let position = entity
94 .indexes
95 .iter()
96 .position(|index| index.id == reference.index)
97 .ok_or(Error::Corrupt)?;
98 let mut bytes = info
99 .indexes
100 .get(position)
101 .and_then(Option::as_ref)
102 .map(Vec::as_slice)
103 .ok_or(Error::Corrupt)?;
104 if field.optional {
105 match bytes.split_first() {
107 Some((0, _)) => continue,
108 Some((1, rest)) => bytes = rest,
109 _ => return Err(Error::Corrupt),
110 }
111 }
112 let mut remaining = bytes;
113 key::consume(&mut remaining, field.value)?;
114 let target = RowKey::decode(&bytes[..bytes.len() - remaining.len()], field.value)?;
115 required.insert((reference.entity, target));
116 }
117 }
118 Ok(())
119}
120
121fn validate_reference_target<M: Memory>(
122 map: &Map<M>,
123 schema: &Schema,
124 entity: u32,
125 id: RowKey,
126) -> Result<(), Error> {
127 let bytes = map
128 .get(&row_key(entity, id))
129 .ok_or(Error::ReferenceViolation)?;
130 let entity = schema
131 .entities()
132 .iter()
133 .find(|value| value.id == entity)
134 .ok_or(Error::Corrupt)?;
135 if entity.inspect_row(&bytes)?.key != id {
136 return Err(Error::Corrupt);
137 }
138 Ok(())
139}
140
141fn manifest_key() -> StoreKey {
142 StoreKey::new(vec![0]).expect("manifest key fits")
143}
144
145fn live_manifest(schema: [u8; 32], incarnation: [u8; 16]) -> Vec<u8> {
146 let mut bytes = MANIFEST.to_vec();
147 bytes.extend(schema);
148 bytes.extend(incarnation);
149 bytes
150}
151
152#[derive(Default)]
154pub struct Batch {
155 operation_time: Option<crate::Timestamp>,
156 mutations: Vec<Mutation>,
157 bytes: usize,
158}
159struct Mutation {
160 entity: &'static EntitySchema,
161 key: RowKey,
162 kind: Kind,
163}
164enum Kind {
165 Insert(Vec<u8>, RowInfo),
166 CopyInsert(Vec<u8>, RowInfo, [Option<crate::Timestamp>; 2]),
168 Replace(Vec<u8>, RowInfo),
169 Delete,
170}
171
172impl Batch {
173 #[must_use]
175 pub fn new() -> Self {
176 Self::default()
177 }
178
179 #[must_use]
182 pub fn at(time: crate::Timestamp) -> Self {
183 Self {
184 operation_time: Some(time),
185 ..Self::default()
186 }
187 }
188
189 pub fn insert<E: Entity>(&mut self, row: &E) -> Result<(), Error> {
193 if E::SCHEMA.has_managed() {
194 return Err(Error::ManagedField);
195 }
196 self.put(row, Kind::Insert)
197 }
198
199 pub fn insert_input<I: crate::InsertInput>(&mut self, input: I) -> Result<I::Entity, Error> {
207 let row = input.__into_entity(self.operation_time)?;
208 self.put(&row, Kind::Insert)?;
209 Ok(row)
210 }
211
212 pub fn replace<E: Entity>(&mut self, row: &E) -> Result<(), Error> {
218 self.put(row, Kind::Replace)
219 }
220
221 pub fn delete<E: Entity>(&mut self, key: E::Key) -> Result<(), Error> {
225 self.push(
226 Mutation {
227 entity: E::SCHEMA,
228 key: key.into_row_key(),
229 kind: Kind::Delete,
230 },
231 0,
232 )
233 }
234
235 fn put<E: Entity>(
236 &mut self,
237 row: &E,
238 kind: impl FnOnce(Vec<u8>, RowInfo) -> Kind,
239 ) -> Result<(), Error> {
240 let bytes = row.encode()?;
241 if bytes.len() > crate::__private::MAX_ROW_BYTES {
242 return Err(Error::Limit);
243 }
244 let info = row.__row_info();
247 let key = info.key;
248 let len = bytes.len();
249 let kind = kind(bytes, info);
250 if E::SCHEMA.has_managed()
251 && self.operation_time.is_none()
252 && !matches!(kind, Kind::CopyInsert(..))
253 {
254 return Err(Error::MissingOperationTime);
255 }
256 self.push(
257 Mutation {
258 entity: E::SCHEMA,
259 key,
260 kind,
261 },
262 len,
263 )
264 }
265
266 fn push(&mut self, mutation: Mutation, bytes: usize) -> Result<(), Error> {
267 if self.mutations.len() == MAX_BATCH || bytes > MAX_BATCH_BYTES - self.bytes {
268 return Err(Error::Limit);
269 }
270 self.bytes += bytes;
271 self.mutations.push(mutation);
272 Ok(())
273 }
274}
275
276pub struct Page<E: Entity> {
278 pub rows: Vec<E>,
280 pub next_after: Option<E::Key>,
282}
283
284pub struct Database<M: Memory> {
286 map: Map<M>,
287 schema: Schema,
288 incarnation: [u8; 16],
289}
290
291impl<M: Memory> Database<M> {
292 pub fn create(
298 memory: RuntimeMemory<M>,
299 schema: Schema,
300 incarnation: [u8; 16],
301 ) -> Result<Self, Error> {
302 if incarnation == [0; 16] {
303 return Err(Error::InvalidSchema);
304 }
305 if memory.size() != 0 {
306 return Err(Error::Exists);
307 }
308 let mut map = Map::create(memory);
309 map.insert(
310 manifest_key(),
311 live_manifest(schema.fingerprint, incarnation),
312 );
313 for entity in &schema.entities {
314 map.insert(entity_state_key(entity.id), EntityState::default().encode());
315 }
316 Ok(Self {
317 map,
318 schema,
319 incarnation,
320 })
321 }
322
323 pub fn open(memory: RuntimeMemory<M>, schema: Schema) -> Result<Self, Error> {
331 if memory.size() == 0 {
332 return Err(Error::Corrupt);
333 }
334 let map = Map::load(memory);
335 let manifest = map.get(&manifest_key()).ok_or(Error::Corrupt)?;
336 if maintenance::admits_gate(&manifest)? {
337 return Err(Error::Maintenance);
338 }
339 if manifest.len() != 56 {
340 return Err(Error::Corrupt);
341 }
342 if &manifest[..8] != MANIFEST || manifest[8..40] != schema.fingerprint {
343 return Err(Error::IncompatibleSchema);
344 }
345 let incarnation = manifest[40..].try_into().map_err(|_| Error::Corrupt)?;
346 if incarnation == [0; 16] {
347 return Err(Error::Corrupt);
348 }
349 Ok(Self {
350 map,
351 schema,
352 incarnation,
353 })
354 }
355
356 #[must_use]
358 pub const fn schema(&self) -> &Schema {
359 &self.schema
360 }
361
362 #[must_use]
364 pub const fn incarnation(&self) -> [u8; 16] {
365 self.incarnation
366 }
367
368 pub fn revision<E: Entity>(&self) -> Result<u64, Error> {
372 let entity = self.schema.admits(E::SCHEMA)?;
373 read_revision(&self.map, entity.id)
374 }
375
376 pub fn cardinality<E: Entity>(&self) -> Result<u64, Error> {
384 let entity = self.schema.admits(E::SCHEMA)?;
385 Ok(read_entity_state(&self.map, entity.id)?.count)
386 }
387
388 pub fn cardinality_by_name(&self, name: &str) -> Result<u64, Error> {
395 let entity = self
396 .schema
397 .entities
398 .iter()
399 .find(|entity| entity.name == name)
400 .ok_or(Error::UnknownEntity)?;
401 Ok(read_entity_state(&self.map, entity.id)?.count)
402 }
403
404 fn revision_by_id(&self, entity: u32) -> Result<u64, Error> {
405 if !self.schema.entities.iter().any(|value| value.id == entity) {
406 return Err(Error::UnknownEntity);
407 }
408 read_revision(&self.map, entity)
409 }
410
411 #[inline]
415 pub fn get<E: Entity>(&self, key: E::Key) -> Result<Option<E>, Error> {
416 let entity = self.schema.admits(E::SCHEMA)?;
417 self.get_typed::<E>(entity, key)
418 }
419
420 pub fn get_many<E: Entity>(&self, keys: &[E::Key]) -> Result<Vec<Option<E>>, Error> {
425 if keys.len() > 32 {
426 return Err(Error::Limit);
427 }
428 let entity = self.schema.admits(E::SCHEMA)?;
429 keys.iter()
430 .map(|&key| self.get_typed::<E>(entity, key))
431 .collect()
432 }
433
434 #[inline(never)]
437 fn get_typed<E: Entity>(&self, entity: &EntitySchema, key: E::Key) -> Result<Option<E>, Error> {
438 self.map
439 .get(&row_key(entity.id, key.into_row_key()))
440 .map(|bytes| {
441 let row = E::decode(&bytes)?;
442 if row.key() != key {
443 return Err(Error::Corrupt);
444 }
445 Ok(row)
446 })
447 .transpose()
448 }
449
450 #[inline]
456 pub fn page<E: Entity>(&self, after: Option<E::Key>, limit: usize) -> Result<Page<E>, Error> {
457 let entity = self.schema.admits(E::SCHEMA)?;
458 self.page_typed::<E>(entity, after, limit)
459 }
460
461 #[inline(never)]
462 fn page_typed<E: Entity>(
463 &self,
464 entity: &EntitySchema,
465 after: Option<E::Key>,
466 limit: usize,
467 ) -> Result<Page<E>, Error> {
468 if !(1..=32).contains(&limit) {
469 return Err(Error::Limit);
470 }
471 let prefix = prefix(2, entity.id);
472 let start = after.map_or_else(
473 || StoreKey::new(prefix.clone()).expect("row namespace fits"),
474 |key| row_key(entity.id, key.into_row_key()),
475 );
476 let lower = if after.is_some() {
477 std::ops::Bound::Excluded(start)
478 } else {
479 std::ops::Bound::Included(start)
480 };
481 let mut entries = self.map.range((lower, std::ops::Bound::Unbounded));
482 let key_type = entity.key_type()?;
483 let mut rows = Vec::new();
484 let mut last = None;
485 for _ in 0..limit {
486 let Some((id, bytes)) = next_primary(&mut entries, &prefix, key_type)? else {
487 break;
488 };
489 let id = E::Key::from_row_key(id)?;
490 let row = E::decode(&bytes)?;
491 if row.key() != id {
492 return Err(Error::Corrupt);
493 }
494 rows.push(row);
495 last = Some(id);
496 }
497 Ok(Page {
498 next_after: if rows.len() == limit { last } else { None },
499 rows,
500 })
501 }
502
503 #[inline]
511 pub fn index_prefix<E: Entity>(
512 &self,
513 index: &str,
514 values: &[IndexValue<'_>],
515 limit: usize,
516 ) -> Result<Vec<E>, Error> {
517 let entity = self.schema.admits(E::SCHEMA)?;
518 self.index_prefix_typed::<E>(entity, index, values, limit)
519 }
520
521 #[inline(never)]
522 fn index_prefix_typed<E: Entity>(
523 &self,
524 entity: &EntitySchema,
525 index: &str,
526 values: &[IndexValue<'_>],
527 limit: usize,
528 ) -> Result<Vec<E>, Error> {
529 let prefix = index_prefix_key(entity, index, values, limit)?;
530 let mut rows = Vec::new();
531 let mut entries = self.map.range(prefix.clone()..);
532 let key_type = entity.key_type()?;
533 for _ in 0..limit {
534 let Some((key, id, bytes)) =
535 next_index(&self.map, &mut entries, &prefix, entity.id, key_type)?
536 else {
537 break;
538 };
539 let row = E::decode(&bytes)?;
540 validate_index_entry(entity, &row.__row_info(), id, &key)?;
541 rows.push(row);
542 }
543 Ok(rows)
544 }
545
546 pub fn commit(&mut self, batch: Batch) -> Result<(), Error> {
555 let mut targets = BTreeSet::new();
556 let mut removes = BTreeSet::new();
557 let mut writes = BTreeMap::new();
558 let mut unique = BTreeSet::new();
559 let mut entities = BTreeMap::new();
562 let mut required = BTreeSet::new();
563 let mut deleted = Vec::new();
564 for mut mutation in batch.mutations {
565 self.schema.admits(mutation.entity)?;
566 let key = row_key(mutation.entity.id, mutation.key);
567 if !targets.insert(key.clone()) {
568 return Err(Error::DuplicateTarget);
569 }
570 let old = self.map.get(&key);
571 match (&mutation.kind, &old) {
572 (Kind::Insert(..) | Kind::CopyInsert(..), Some(_)) => return Err(Error::Exists),
573 (Kind::Replace(..) | Kind::Delete, None) => return Err(Error::Missing),
574 _ => {}
575 }
576 if mutation.entity.has_managed() {
577 match &mut mutation.kind {
578 Kind::Insert(bytes, _) => crate::managed::validate_insert(
579 mutation.entity,
580 bytes,
581 batch.operation_time.ok_or(Error::MissingOperationTime)?,
582 )?,
583 Kind::Replace(bytes, info) => {
584 if crate::managed::replace(
585 mutation.entity,
586 bytes,
587 old.as_deref().ok_or(Error::Missing)?,
588 batch.operation_time.ok_or(Error::MissingOperationTime)?,
589 )? {
590 *info = mutation.entity.inspect_row(bytes)?;
591 }
592 }
593 Kind::CopyInsert(bytes, _, expected) => {
594 if crate::managed::values(mutation.entity, bytes)? != *expected {
595 return Err(Error::ManagedField);
596 }
597 }
598 Kind::Delete => {}
599 }
600 }
601 let mut after_indexes = match &mutation.kind {
604 Kind::Insert(_, info) | Kind::CopyInsert(_, info, _) | Kind::Replace(_, info) => {
605 index_entries(mutation.entity, info)?
606 }
607 Kind::Delete => Vec::new(),
608 };
609 let (_, changed, delta) = match entities.entry(mutation.entity.id) {
610 std::collections::btree_map::Entry::Occupied(entry) => entry.into_mut(),
611 std::collections::btree_map::Entry::Vacant(entry) => entry.insert((
612 read_entity_state(&self.map, mutation.entity.id)?,
613 false,
614 0_i64,
615 )),
616 };
617 if let (Kind::Replace(bytes, _), Some(old)) = (&mutation.kind, &old)
618 && bytes == old
619 {
620 continue;
621 }
622 if let Some(old) = old {
623 let info = mutation.entity.inspect_row(&old)?;
624 if info.key != mutation.key {
625 return Err(Error::Corrupt);
626 }
627 let owner = info.key.encode();
628 for (key, _) in index_entries(mutation.entity, &info)? {
629 if self.map.get(&key).as_deref() != Some(owner.as_slice()) {
630 return Err(Error::Corrupt);
631 }
632 if let Some(position) =
635 after_indexes.iter().position(|(after, _)| *after == key)
636 {
637 after_indexes.remove(position);
638 } else {
639 removes.insert(key);
640 }
641 }
642 }
643 *changed = true;
644 *delta += match &mutation.kind {
645 Kind::Insert(..) | Kind::CopyInsert(..) => 1,
646 Kind::Delete => -1,
647 Kind::Replace(..) => 0,
648 };
649 let copy_insert = matches!(&mutation.kind, Kind::CopyInsert(..));
652 match mutation.kind {
653 Kind::Delete => {
654 deleted.push((mutation.entity.id, mutation.key));
655 removes.insert(key);
656 }
657 Kind::Insert(bytes, info)
658 | Kind::CopyInsert(bytes, info, _)
659 | Kind::Replace(bytes, info) => {
660 writes.insert(key, bytes);
661 for (key, is_unique) in after_indexes {
662 if is_unique && !unique.insert(key.clone()) {
663 return Err(Error::UniqueViolation);
664 }
665 writes.insert(key, info.key.encode());
666 }
667 if !copy_insert {
668 collect_references(mutation.entity, &info, &mut required)?;
669 }
670 }
671 }
672 }
673 for key in unique {
675 if self.map.contains_key(&key) && !removes.contains(&key) {
676 return Err(Error::UniqueViolation);
677 }
678 }
679 self.validate_references(&required, &deleted, &removes, &writes)?;
680 for (entity, (mut state, changed, delta)) in entities {
681 if changed {
682 state.revision = state.revision.checked_add(1).ok_or(Error::Limit)?;
683 state.count = if delta >= 0 {
684 state.count.checked_add(delta as u64).ok_or(Error::Limit)?
685 } else {
686 state
687 .count
688 .checked_sub((-delta) as u64)
689 .ok_or(Error::Corrupt)?
690 };
691 writes.insert(entity_state_key(entity), state.encode());
692 }
693 }
694 for key in removes {
696 self.map.remove(&key);
697 }
698 for (key, value) in writes {
699 self.map.insert(key, value);
700 }
701 Ok(())
702 }
703
704 fn validate_references(
707 &self,
708 required: &BTreeSet<(u32, RowKey)>,
709 deleted: &[(u32, RowKey)],
710 removes: &BTreeSet<StoreKey>,
711 writes: &BTreeMap<StoreKey, Vec<u8>>,
712 ) -> Result<(), Error> {
713 for &(entity, id) in required {
714 let key = row_key(entity, id);
715 if writes.contains_key(&key) {
716 continue;
717 } if removes.contains(&key) {
719 return Err(Error::ReferenceViolation);
720 }
721 validate_reference_target(&self.map, &self.schema, entity, id)?;
722 }
723 for &(target, id) in deleted {
724 for entity in &self.schema.entities {
725 for field in entity.fields {
726 let Some(reference) = field.reference.filter(|value| value.entity == target)
727 else {
728 continue;
729 };
730 let mut prefix = index_prefix(entity.id, reference.index);
731 id.index_value()
732 .append_component(field.optional, &mut prefix);
733 let prefix = StoreKey::new(prefix)?;
734 for (position, entry) in self
737 .map
738 .range(prefix.clone()..)
739 .take_while(|entry| entry.key().starts_with(&prefix))
740 .take(MAX_BATCH + 1)
741 .enumerate()
742 {
743 if removes.contains(entry.key()) {
744 if position == MAX_BATCH {
745 return Err(Error::Corrupt);
746 }
747 continue;
748 }
749 let owner = RowKey::decode(&entry.value(), entity.key_type()?)?;
750 let bytes = self
751 .map
752 .get(&row_key(entity.id, owner))
753 .ok_or(Error::Corrupt)?;
754 let info = entity.inspect_row(&bytes)?;
755 validate_index_entry(entity, &info, owner, entry.key())?;
756 return Err(Error::ReferenceViolation);
757 }
758 }
759 }
760 }
761 Ok(())
762 }
763}
764
765fn prefix(tag: u8, entity: u32) -> Vec<u8> {
766 let mut key = vec![tag];
767 key.extend(entity.to_be_bytes());
768 key
769}
770
771fn entity_state_key(entity: u32) -> StoreKey {
772 StoreKey::new(prefix(1, entity)).expect("entity state key fits")
773}
774
775fn read_revision<M: Memory>(map: &Map<M>, entity: u32) -> Result<u64, Error> {
776 Ok(read_entity_state(map, entity)?.revision)
777}
778
779#[derive(Default)]
781struct EntityState {
782 revision: u64,
783 count: u64,
784}
785impl EntityState {
786 fn encode(&self) -> Vec<u8> {
787 let mut bytes = self.revision.to_le_bytes().to_vec();
788 bytes.extend(self.count.to_le_bytes());
789 bytes
790 }
791}
792fn read_entity_state<M: Memory>(map: &Map<M>, entity: u32) -> Result<EntityState, Error> {
793 let bytes = map.get(&entity_state_key(entity)).ok_or(Error::Corrupt)?;
794 if bytes.len() != 16 {
795 return Err(Error::Corrupt);
796 }
797 Ok(EntityState {
798 revision: u64::from_le_bytes(bytes[..8].try_into().map_err(|_| Error::Corrupt)?),
799 count: u64::from_le_bytes(bytes[8..].try_into().map_err(|_| Error::Corrupt)?),
800 })
801}
802
803fn row_key(entity: u32, id: RowKey) -> StoreKey {
804 let mut key = prefix(2, entity);
805 id.append_to(&mut key);
806 StoreKey::new(key).expect("bounded primary key fits")
807}
808const INDEX_PREFIX_BYTES: usize = 9; fn index_prefix(entity: u32, index: u32) -> Vec<u8> {
810 let mut key = prefix(3, entity);
811 key.extend(index.to_be_bytes());
812 key
813}
814fn admit_index_prefix(
816 entity: &EntitySchema,
817 index: &crate::IndexSchema,
818 values: &[IndexValue<'_>],
819) -> Result<Vec<u8>, Error> {
820 if values.len() > index.fields.len() {
821 return Err(Error::Limit);
822 }
823 let mut prefix = index_prefix(entity.id, index.id);
824 for (value, name) in values.iter().zip(index.fields) {
825 let field = entity
826 .fields
827 .iter()
828 .find(|field| field.name == *name)
829 .ok_or(Error::InvalidSchema)?;
830 value.admit(field.value, field.optional)?;
831 if index.present_only && *value == IndexValue::Absent {
832 return Err(Error::InvalidOperand);
833 }
834 value.append_component(field.optional, &mut prefix);
835 if prefix.len() > crate::MAX_INDEX_KEY_BYTES {
836 return Err(Error::Limit);
837 }
838 }
839 let mut completion = if index.unique {
840 0
841 } else {
842 key::minimum_bytes(entity.key_type()?)?
843 };
844 for name in &index.fields[values.len()..] {
845 let field = entity
846 .fields
847 .iter()
848 .find(|field| field.name == *name)
849 .ok_or(Error::InvalidSchema)?;
850 completion += if field.optional && !index.present_only {
851 1
852 } else {
853 key::minimum_bytes(field.value)? + usize::from(field.optional)
854 };
855 }
856 if prefix.len() + completion > crate::MAX_INDEX_KEY_BYTES {
857 return Err(Error::Limit);
858 }
859 Ok(prefix)
860}
861fn visit_index_components(
863 entity: &EntitySchema,
864 info: &RowInfo,
865 mut visit: impl FnMut(&crate::IndexSchema, &[u8]) -> Result<(), Error>,
866) -> Result<(), Error> {
867 if info.indexes.len() != entity.indexes.len() {
868 return Err(Error::Corrupt);
869 }
870 for (index, values) in entity.indexes.iter().zip(&info.indexes) {
871 let Some(values) = values else {
872 if index.present_only {
873 continue;
874 }
875 return Err(Error::Corrupt);
876 };
877 let mut remaining = values.as_slice();
878 for name in index.fields {
879 let field = entity
880 .fields
881 .iter()
882 .find(|field| field.name == *name)
883 .ok_or(Error::Corrupt)?;
884 if field.optional {
885 let (&presence, rest) = remaining.split_first().ok_or(Error::Corrupt)?;
886 remaining = rest;
887 match presence {
888 0 if !index.present_only => continue,
889 1 => {}
890 _ => return Err(Error::Corrupt),
891 }
892 }
893 key::consume(&mut remaining, field.value)?;
894 }
895 if !remaining.is_empty() {
896 return Err(Error::Corrupt);
897 }
898 visit(index, values)?;
899 }
900 Ok(())
901}
902
903fn index_entries(entity: &EntitySchema, info: &RowInfo) -> Result<Vec<(StoreKey, bool)>, Error> {
904 let mut entries = Vec::new();
905 visit_index_components(entity, info, |index, values| {
906 let mut key = index_prefix(entity.id, index.id);
907 key.extend_from_slice(values);
908 if !index.unique {
909 info.key.append_to(&mut key);
910 }
911 entries.push((StoreKey::new(key)?, index.unique));
912 Ok(())
913 })?;
914 Ok(entries)
915}
916
917fn validate_index_entry(
920 entity: &EntitySchema,
921 info: &RowInfo,
922 owner: RowKey,
923 key: &[u8],
924) -> Result<(), Error> {
925 if info.key != owner {
926 return Err(Error::Corrupt);
927 }
928 let (header, payload) = key
929 .split_at_checked(INDEX_PREFIX_BYTES)
930 .ok_or(Error::Corrupt)?;
931 if header[0] != 3 || header[1..5] != entity.id.to_be_bytes() {
932 return Err(Error::Corrupt);
933 }
934 let mut matches = false;
935 let owner = owner.encode();
936 visit_index_components(entity, info, |index, values| {
937 let suffix = if index.unique {
938 &[][..]
939 } else {
940 owner.as_slice()
941 };
942 if INDEX_PREFIX_BYTES + values.len() + suffix.len() > crate::MAX_INDEX_KEY_BYTES {
943 return Err(Error::Limit);
944 }
945 if header[5..] == index.id.to_be_bytes() {
946 matches = payload.strip_prefix(values) == Some(suffix);
947 }
948 Ok(())
949 })?;
950 if !matches {
951 return Err(Error::Corrupt);
952 }
953 Ok(())
954}