1use crate::{
5 __private::RowInfo, Entity, EntitySchema, Error, FieldType, IndexValue, PrimaryKey, Schema,
6 key, primary::RowKey, store_key::StoreKey,
7};
8use ic_storage::{
9 DefaultMemoryImpl, 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, QueryPage, SortDirection,
20};
21
22const MANIFEST: &[u8] = b"ICDBMF02";
23const MAX_BATCH: usize = 32;
24const MAX_BATCH_BYTES: usize = 128 * 1024;
25type Map<M> = StableBTreeMap<StoreKey, Vec<u8>, M>;
26
27#[inline(never)]
30fn next_primary<M: Memory>(
31 entries: &mut MapIter<'_, StoreKey, Vec<u8>, M>,
32 prefix: &[u8],
33 key_type: FieldType,
34) -> Result<Option<(RowKey, Vec<u8>)>, Error> {
35 let Some(entry) = entries.next() else {
36 return Ok(None);
37 };
38 if !entry.key().starts_with(prefix) {
39 return Ok(None);
40 }
41 let id = RowKey::decode(&entry.key()[5..], key_type)?;
42 Ok(Some((id, entry.value())))
43}
44
45#[inline(never)]
47fn next_index<M: Memory>(
48 map: &Map<M>,
49 entries: &mut MapIter<'_, StoreKey, Vec<u8>, M>,
50 prefix: &[u8],
51 entity: u32,
52 key_type: FieldType,
53) -> Result<Option<(StoreKey, RowKey, Vec<u8>)>, Error> {
54 let Some(entry) = entries.next() else {
55 return Ok(None);
56 };
57 if !entry.key().starts_with(prefix) {
58 return Ok(None);
59 }
60 let id = RowKey::decode(&entry.value(), key_type)?;
61 let bytes = map.get(&row_key(entity, id)).ok_or(Error::Corrupt)?;
62 Ok(Some((entry.key().clone(), id, bytes)))
63}
64
65#[inline(never)]
66fn index_prefix_key(
67 entity: &EntitySchema,
68 index: &str,
69 values: &[IndexValue<'_>],
70 limit: usize,
71) -> Result<StoreKey, Error> {
72 let index = entity
73 .indexes
74 .iter()
75 .find(|value| value.name == index)
76 .ok_or(Error::InvalidSchema)?;
77 if values.is_empty() || values.len() > index.fields.len() || !(1..=32).contains(&limit) {
78 return Err(Error::Limit);
79 }
80 StoreKey::new(admit_index_prefix(entity, index, values)?)
81}
82
83fn collect_references(
86 entity: &EntitySchema,
87 info: &RowInfo,
88 required: &mut BTreeSet<(u32, RowKey)>,
89) -> Result<(), Error> {
90 for field in entity.fields {
91 if let Some(reference) = field.reference {
92 let position = entity
93 .indexes
94 .iter()
95 .position(|index| index.id == reference.index)
96 .ok_or(Error::Corrupt)?;
97 let mut bytes = info
98 .indexes
99 .get(position)
100 .and_then(Option::as_ref)
101 .map(Vec::as_slice)
102 .ok_or(Error::Corrupt)?;
103 if field.optional {
104 match bytes.split_first() {
106 Some((0, _)) => continue,
107 Some((1, rest)) => bytes = rest,
108 _ => return Err(Error::Corrupt),
109 }
110 }
111 let mut remaining = bytes;
112 key::consume(&mut remaining, field.value)?;
113 let target = RowKey::decode(&bytes[..bytes.len() - remaining.len()], field.value)?;
114 required.insert((reference.entity, target));
115 }
116 }
117 Ok(())
118}
119
120fn validate_reference_target<M: Memory>(
121 map: &Map<M>,
122 schema: &Schema,
123 entity: u32,
124 id: RowKey,
125) -> Result<(), Error> {
126 let bytes = map
127 .get(&row_key(entity, id))
128 .ok_or(Error::ReferenceViolation)?;
129 let entity = schema
130 .entities()
131 .iter()
132 .find(|value| value.id == entity)
133 .ok_or(Error::Corrupt)?;
134 if entity.inspect_row(&bytes)?.key != id {
135 return Err(Error::Corrupt);
136 }
137 Ok(())
138}
139
140fn manifest_key() -> StoreKey {
141 StoreKey::new(vec![0]).expect("manifest key fits")
142}
143fn live_manifest(schema: [u8; 32], incarnation: [u8; 16]) -> Vec<u8> {
144 let mut bytes = MANIFEST.to_vec();
145 bytes.extend(schema);
146 bytes.extend(incarnation);
147 bytes
148}
149
150#[derive(Default)]
152pub struct Batch {
153 operation_time: Option<crate::Timestamp>,
154 mutations: Vec<Mutation>,
155 bytes: usize,
156}
157struct Mutation {
158 entity: &'static EntitySchema,
159 key: RowKey,
160 kind: Kind,
161}
162enum Kind {
163 Insert(Vec<u8>, RowInfo),
164 CopyInsert(Vec<u8>, RowInfo, [Option<crate::Timestamp>; 2]),
166 Replace(Vec<u8>, RowInfo),
167 Delete,
168}
169
170impl Batch {
171 #[must_use]
173 pub fn new() -> Self {
174 Self::default()
175 }
176 #[must_use]
179 pub fn at(time: crate::Timestamp) -> Self {
180 Self {
181 operation_time: Some(time),
182 ..Self::default()
183 }
184 }
185 pub fn insert<E: Entity>(&mut self, row: &E) -> Result<(), Error> {
189 if E::SCHEMA.has_managed() {
190 return Err(Error::ManagedField);
191 }
192 self.put(row, Kind::Insert)
193 }
194 pub fn insert_input<I: crate::InsertInput>(&mut self, input: I) -> Result<I::Entity, Error> {
202 let row = input.__into_entity(self.operation_time)?;
203 self.put(&row, Kind::Insert)?;
204 Ok(row)
205 }
206 pub fn replace<E: Entity>(&mut self, row: &E) -> Result<(), Error> {
212 self.put(row, Kind::Replace)
213 }
214 pub fn delete<E: Entity>(&mut self, key: E::Key) -> Result<(), Error> {
218 self.push(
219 Mutation {
220 entity: E::SCHEMA,
221 key: key.into_row_key(),
222 kind: Kind::Delete,
223 },
224 0,
225 )
226 }
227 fn put<E: Entity>(
228 &mut self,
229 row: &E,
230 kind: impl FnOnce(Vec<u8>, RowInfo) -> Kind,
231 ) -> Result<(), Error> {
232 let bytes = row.encode()?;
233 if bytes.len() > crate::__private::MAX_ROW_BYTES {
234 return Err(Error::Limit);
235 }
236 let info = row.__row_info();
239 let key = info.key;
240 let len = bytes.len();
241 let kind = kind(bytes, info);
242 if E::SCHEMA.has_managed()
243 && self.operation_time.is_none()
244 && !matches!(kind, Kind::CopyInsert(..))
245 {
246 return Err(Error::MissingOperationTime);
247 }
248 self.push(
249 Mutation {
250 entity: E::SCHEMA,
251 key,
252 kind,
253 },
254 len,
255 )
256 }
257 fn push(&mut self, mutation: Mutation, bytes: usize) -> Result<(), Error> {
258 if self.mutations.len() == MAX_BATCH || bytes > MAX_BATCH_BYTES - self.bytes {
259 return Err(Error::Limit);
260 }
261 self.bytes += bytes;
262 self.mutations.push(mutation);
263 Ok(())
264 }
265}
266
267pub struct Page<E: Entity> {
269 pub rows: Vec<E>,
271 pub next_after: Option<E::Key>,
273}
274
275pub struct Database<M: Memory = DefaultMemoryImpl> {
277 map: Map<M>,
278 schema: Schema,
279 incarnation: [u8; 16],
280}
281
282impl<M: Memory> Database<M> {
283 pub fn create(
289 memory: RuntimeMemory<M>,
290 schema: Schema,
291 incarnation: [u8; 16],
292 ) -> Result<Self, Error> {
293 if incarnation == [0; 16] {
294 return Err(Error::InvalidSchema);
295 }
296 if memory.size() != 0 {
297 return Err(Error::Exists);
298 }
299 let mut map = Map::create(memory);
300 map.insert(
301 manifest_key(),
302 live_manifest(schema.fingerprint, incarnation),
303 );
304 for entity in &schema.entities {
305 map.insert(entity_state_key(entity.id), EntityState::default().encode());
306 }
307 Ok(Self {
308 map,
309 schema,
310 incarnation,
311 })
312 }
313 pub fn open(memory: RuntimeMemory<M>, schema: Schema) -> Result<Self, Error> {
321 if memory.size() == 0 {
322 return Err(Error::Corrupt);
323 }
324 let map = Map::load(memory);
325 let manifest = map.get(&manifest_key()).ok_or(Error::Corrupt)?;
326 if maintenance::admits_gate(&manifest)? {
327 return Err(Error::Maintenance);
328 }
329 if manifest.len() != 56 {
330 return Err(Error::Corrupt);
331 }
332 if &manifest[..8] != MANIFEST || manifest[8..40] != schema.fingerprint {
333 return Err(Error::IncompatibleSchema);
334 }
335 let incarnation = manifest[40..].try_into().map_err(|_| Error::Corrupt)?;
336 if incarnation == [0; 16] {
337 return Err(Error::Corrupt);
338 }
339 Ok(Self {
340 map,
341 schema,
342 incarnation,
343 })
344 }
345 #[must_use]
347 pub const fn schema(&self) -> &Schema {
348 &self.schema
349 }
350 #[must_use]
352 pub const fn incarnation(&self) -> [u8; 16] {
353 self.incarnation
354 }
355 pub fn revision<E: Entity>(&self) -> Result<u64, Error> {
359 let entity = self.schema.admits(E::SCHEMA)?;
360 read_revision(&self.map, entity.id)
361 }
362 pub fn cardinality<E: Entity>(&self) -> Result<u64, Error> {
370 let entity = self.schema.admits(E::SCHEMA)?;
371 Ok(read_entity_state(&self.map, entity.id)?.count)
372 }
373 pub fn cardinality_by_name(&self, name: &str) -> Result<u64, Error> {
380 let entity = self
381 .schema
382 .entities
383 .iter()
384 .find(|entity| entity.name == name)
385 .ok_or(Error::UnknownEntity)?;
386 Ok(read_entity_state(&self.map, entity.id)?.count)
387 }
388 fn revision_by_id(&self, entity: u32) -> Result<u64, Error> {
389 if !self.schema.entities.iter().any(|value| value.id == entity) {
390 return Err(Error::UnknownEntity);
391 }
392 read_revision(&self.map, entity)
393 }
394 #[inline]
398 pub fn get<E: Entity>(&self, key: E::Key) -> Result<Option<E>, Error> {
399 let entity = self.schema.admits(E::SCHEMA)?;
400 self.get_typed::<E>(entity, key)
401 }
402
403 #[inline(never)]
406 fn get_typed<E: Entity>(&self, entity: &EntitySchema, key: E::Key) -> Result<Option<E>, Error> {
407 self.map
408 .get(&row_key(entity.id, key.into_row_key()))
409 .map(|bytes| {
410 let row = E::decode(&bytes)?;
411 if row.key() != key {
412 return Err(Error::Corrupt);
413 }
414 Ok(row)
415 })
416 .transpose()
417 }
418 #[inline]
424 pub fn page<E: Entity>(&self, after: Option<E::Key>, limit: usize) -> Result<Page<E>, Error> {
425 let entity = self.schema.admits(E::SCHEMA)?;
426 self.page_typed::<E>(entity, after, limit)
427 }
428
429 #[inline(never)]
430 fn page_typed<E: Entity>(
431 &self,
432 entity: &EntitySchema,
433 after: Option<E::Key>,
434 limit: usize,
435 ) -> Result<Page<E>, Error> {
436 if !(1..=32).contains(&limit) {
437 return Err(Error::Limit);
438 }
439 let prefix = prefix(2, entity.id);
440 let start = after.map_or_else(
441 || StoreKey::new(prefix.clone()).expect("row namespace fits"),
442 |key| row_key(entity.id, key.into_row_key()),
443 );
444 let lower = if after.is_some() {
445 std::ops::Bound::Excluded(start)
446 } else {
447 std::ops::Bound::Included(start)
448 };
449 let mut entries = self.map.range((lower, std::ops::Bound::Unbounded));
450 let key_type = entity.key_type()?;
451 let mut rows = Vec::new();
452 let mut last = None;
453 for _ in 0..limit {
454 let Some((id, bytes)) = next_primary(&mut entries, &prefix, key_type)? else {
455 break;
456 };
457 let id = E::Key::from_row_key(id)?;
458 let row = E::decode(&bytes)?;
459 if row.key() != id {
460 return Err(Error::Corrupt);
461 }
462 rows.push(row);
463 last = Some(id);
464 }
465 Ok(Page {
466 next_after: if rows.len() == limit { last } else { None },
467 rows,
468 })
469 }
470 #[inline]
478 pub fn index_prefix<E: Entity>(
479 &self,
480 index: &str,
481 values: &[IndexValue<'_>],
482 limit: usize,
483 ) -> Result<Vec<E>, Error> {
484 let entity = self.schema.admits(E::SCHEMA)?;
485 self.index_prefix_typed::<E>(entity, index, values, limit)
486 }
487
488 #[inline(never)]
489 fn index_prefix_typed<E: Entity>(
490 &self,
491 entity: &EntitySchema,
492 index: &str,
493 values: &[IndexValue<'_>],
494 limit: usize,
495 ) -> Result<Vec<E>, Error> {
496 let prefix = index_prefix_key(entity, index, values, limit)?;
497 let mut rows = Vec::new();
498 let mut entries = self.map.range(prefix.clone()..);
499 let key_type = entity.key_type()?;
500 for _ in 0..limit {
501 let Some((key, id, bytes)) =
502 next_index(&self.map, &mut entries, &prefix, entity.id, key_type)?
503 else {
504 break;
505 };
506 let row = E::decode(&bytes)?;
507 validate_index_entry(entity, &row.__row_info(), id, &key)?;
508 rows.push(row);
509 }
510 Ok(rows)
511 }
512
513 pub fn commit(&mut self, batch: Batch) -> Result<(), Error> {
522 let mut targets = BTreeSet::new();
523 let mut removes = BTreeSet::new();
524 let mut writes = BTreeMap::new();
525 let mut unique = BTreeSet::new();
526 let mut entities = BTreeMap::new();
529 let mut required = BTreeSet::new();
530 let mut deleted = Vec::new();
531 for mut mutation in batch.mutations {
532 self.schema.admits(mutation.entity)?;
533 let key = row_key(mutation.entity.id, mutation.key);
534 if !targets.insert(key.clone()) {
535 return Err(Error::DuplicateTarget);
536 }
537 let old = self.map.get(&key);
538 match (&mutation.kind, &old) {
539 (Kind::Insert(..) | Kind::CopyInsert(..), Some(_)) => return Err(Error::Exists),
540 (Kind::Replace(..) | Kind::Delete, None) => return Err(Error::Missing),
541 _ => {}
542 }
543 if mutation.entity.has_managed() {
544 match &mut mutation.kind {
545 Kind::Insert(bytes, _) => crate::managed::validate_insert(
546 mutation.entity,
547 bytes,
548 batch.operation_time.ok_or(Error::MissingOperationTime)?,
549 )?,
550 Kind::Replace(bytes, info) => {
551 if crate::managed::replace(
552 mutation.entity,
553 bytes,
554 old.as_deref().ok_or(Error::Missing)?,
555 batch.operation_time.ok_or(Error::MissingOperationTime)?,
556 )? {
557 *info = mutation.entity.inspect_row(bytes)?;
558 }
559 }
560 Kind::CopyInsert(bytes, _, expected) => {
561 if crate::managed::values(mutation.entity, bytes)? != *expected {
562 return Err(Error::ManagedField);
563 }
564 }
565 Kind::Delete => {}
566 }
567 }
568 let after_indexes = match &mutation.kind {
571 Kind::Insert(_, info) | Kind::CopyInsert(_, info, _) | Kind::Replace(_, info) => {
572 index_entries(mutation.entity, info)?
573 }
574 Kind::Delete => Vec::new(),
575 };
576 let (_, changed, delta) = match entities.entry(mutation.entity.id) {
577 std::collections::btree_map::Entry::Occupied(entry) => entry.into_mut(),
578 std::collections::btree_map::Entry::Vacant(entry) => entry.insert((
579 read_entity_state(&self.map, mutation.entity.id)?,
580 false,
581 0_i64,
582 )),
583 };
584 if let (Kind::Replace(bytes, _), Some(old)) = (&mutation.kind, &old)
585 && bytes == old
586 {
587 continue;
588 }
589 if let Some(old) = old {
590 let info = mutation.entity.inspect_row(&old)?;
591 if info.key != mutation.key {
592 return Err(Error::Corrupt);
593 }
594 for (key, _) in index_entries(mutation.entity, &info)? {
595 if self.map.get(&key) != Some(info.key.encode()) {
596 return Err(Error::Corrupt);
597 }
598 removes.insert(key);
599 }
600 }
601 *changed = true;
602 *delta += match &mutation.kind {
603 Kind::Insert(..) | Kind::CopyInsert(..) => 1,
604 Kind::Delete => -1,
605 Kind::Replace(..) => 0,
606 };
607 let copy_insert = matches!(&mutation.kind, Kind::CopyInsert(..));
610 match mutation.kind {
611 Kind::Delete => {
612 deleted.push((mutation.entity.id, mutation.key));
613 removes.insert(key);
614 }
615 Kind::Insert(bytes, info)
616 | Kind::CopyInsert(bytes, info, _)
617 | Kind::Replace(bytes, info) => {
618 writes.insert(key, bytes);
619 for (key, is_unique) in after_indexes {
620 if is_unique && !unique.insert(key.clone()) {
621 return Err(Error::UniqueViolation);
622 }
623 writes.insert(key, info.key.encode());
624 }
625 if !copy_insert {
626 collect_references(mutation.entity, &info, &mut required)?;
627 }
628 }
629 }
630 }
631 for key in unique {
633 if self.map.contains_key(&key) && !removes.contains(&key) {
634 return Err(Error::UniqueViolation);
635 }
636 }
637 self.validate_references(&required, &deleted, &removes, &writes)?;
638 for (entity, (mut state, changed, delta)) in entities {
639 if changed {
640 state.revision = state.revision.checked_add(1).ok_or(Error::Limit)?;
641 state.count = if delta >= 0 {
642 state.count.checked_add(delta as u64).ok_or(Error::Limit)?
643 } else {
644 state
645 .count
646 .checked_sub((-delta) as u64)
647 .ok_or(Error::Corrupt)?
648 };
649 writes.insert(entity_state_key(entity), state.encode());
650 }
651 }
652 for key in removes {
654 self.map.remove(&key);
655 }
656 for (key, value) in writes {
657 self.map.insert(key, value);
658 }
659 Ok(())
660 }
661
662 fn validate_references(
665 &self,
666 required: &BTreeSet<(u32, RowKey)>,
667 deleted: &[(u32, RowKey)],
668 removes: &BTreeSet<StoreKey>,
669 writes: &BTreeMap<StoreKey, Vec<u8>>,
670 ) -> Result<(), Error> {
671 for &(entity, id) in required {
672 let key = row_key(entity, id);
673 if writes.contains_key(&key) {
674 continue;
675 } if removes.contains(&key) {
677 return Err(Error::ReferenceViolation);
678 }
679 validate_reference_target(&self.map, &self.schema, entity, id)?;
680 }
681 for &(target, id) in deleted {
682 for entity in &self.schema.entities {
683 for field in entity.fields {
684 let Some(reference) = field.reference.filter(|value| value.entity == target)
685 else {
686 continue;
687 };
688 let mut prefix = index_prefix(entity.id, reference.index);
689 id.index_value()
690 .append_component(field.optional, &mut prefix);
691 let prefix = StoreKey::new(prefix)?;
692 for (position, entry) in self
695 .map
696 .range(prefix.clone()..)
697 .take_while(|entry| entry.key().starts_with(&prefix))
698 .take(MAX_BATCH + 1)
699 .enumerate()
700 {
701 if removes.contains(entry.key()) {
702 if position == MAX_BATCH {
703 return Err(Error::Corrupt);
704 }
705 continue;
706 }
707 let owner = RowKey::decode(&entry.value(), entity.key_type()?)?;
708 let bytes = self
709 .map
710 .get(&row_key(entity.id, owner))
711 .ok_or(Error::Corrupt)?;
712 let info = entity.inspect_row(&bytes)?;
713 validate_index_entry(entity, &info, owner, entry.key())?;
714 return Err(Error::ReferenceViolation);
715 }
716 }
717 }
718 }
719 Ok(())
720 }
721}
722
723fn prefix(tag: u8, entity: u32) -> Vec<u8> {
724 let mut key = vec![tag];
725 key.extend(entity.to_be_bytes());
726 key
727}
728fn entity_state_key(entity: u32) -> StoreKey {
729 StoreKey::new(prefix(1, entity)).expect("entity state key fits")
730}
731fn read_revision<M: Memory>(map: &Map<M>, entity: u32) -> Result<u64, Error> {
732 Ok(read_entity_state(map, entity)?.revision)
733}
734
735#[derive(Default)]
737struct EntityState {
738 revision: u64,
739 count: u64,
740}
741impl EntityState {
742 fn encode(&self) -> Vec<u8> {
743 let mut bytes = self.revision.to_le_bytes().to_vec();
744 bytes.extend(self.count.to_le_bytes());
745 bytes
746 }
747}
748fn read_entity_state<M: Memory>(map: &Map<M>, entity: u32) -> Result<EntityState, Error> {
749 let bytes = map.get(&entity_state_key(entity)).ok_or(Error::Corrupt)?;
750 if bytes.len() != 16 {
751 return Err(Error::Corrupt);
752 }
753 Ok(EntityState {
754 revision: u64::from_le_bytes(bytes[..8].try_into().map_err(|_| Error::Corrupt)?),
755 count: u64::from_le_bytes(bytes[8..].try_into().map_err(|_| Error::Corrupt)?),
756 })
757}
758fn row_key(entity: u32, id: RowKey) -> StoreKey {
759 let mut key = prefix(2, entity);
760 id.append_to(&mut key);
761 StoreKey::new(key).expect("bounded primary key fits")
762}
763fn index_prefix(entity: u32, index: u32) -> Vec<u8> {
764 let mut key = prefix(3, entity);
765 key.extend(index.to_be_bytes());
766 key
767}
768fn admit_index_prefix(
770 entity: &EntitySchema,
771 index: &crate::IndexSchema,
772 values: &[IndexValue<'_>],
773) -> Result<Vec<u8>, Error> {
774 if values.len() > index.fields.len() {
775 return Err(Error::Limit);
776 }
777 let mut prefix = index_prefix(entity.id, index.id);
778 for (value, name) in values.iter().zip(index.fields) {
779 let field = entity
780 .fields
781 .iter()
782 .find(|field| field.name == *name)
783 .ok_or(Error::InvalidSchema)?;
784 value.admit(field.value, field.optional)?;
785 if index.present_only && *value == IndexValue::Absent {
786 return Err(Error::InvalidOperand);
787 }
788 value.append_component(field.optional, &mut prefix);
789 if prefix.len() > crate::MAX_INDEX_KEY_BYTES {
790 return Err(Error::Limit);
791 }
792 }
793 let mut completion = if index.unique {
794 0
795 } else {
796 key::minimum_bytes(entity.key_type()?)?
797 };
798 for name in &index.fields[values.len()..] {
799 let field = entity
800 .fields
801 .iter()
802 .find(|field| field.name == *name)
803 .ok_or(Error::InvalidSchema)?;
804 completion += if field.optional && !index.present_only {
805 1
806 } else {
807 key::minimum_bytes(field.value)? + usize::from(field.optional)
808 };
809 }
810 if prefix.len() + completion > crate::MAX_INDEX_KEY_BYTES {
811 return Err(Error::Limit);
812 }
813 Ok(prefix)
814}
815fn index_entries(entity: &EntitySchema, info: &RowInfo) -> Result<Vec<(StoreKey, bool)>, Error> {
816 if info.indexes.len() != entity.indexes.len() {
817 return Err(Error::Corrupt);
818 }
819 let mut entries = Vec::new();
820 for (index, values) in entity.indexes.iter().zip(&info.indexes) {
821 let Some(values) = values else {
822 if index.present_only {
823 continue;
824 }
825 return Err(Error::Corrupt);
826 };
827 let mut remaining = values.as_slice();
828 for name in index.fields {
829 let field = entity
830 .fields
831 .iter()
832 .find(|field| field.name == *name)
833 .ok_or(Error::Corrupt)?;
834 if field.optional {
835 let (&presence, rest) = remaining.split_first().ok_or(Error::Corrupt)?;
836 remaining = rest;
837 match presence {
838 0 if !index.present_only => continue,
839 1 => {}
840 _ => return Err(Error::Corrupt),
841 }
842 }
843 key::consume(&mut remaining, field.value)?;
844 }
845 if !remaining.is_empty() {
846 return Err(Error::Corrupt);
847 }
848 let mut key = index_prefix(entity.id, index.id);
849 key.extend(values);
850 if !index.unique {
851 info.key.append_to(&mut key);
852 }
853 entries.push((StoreKey::new(key)?, index.unique));
854 }
855 Ok(entries)
856}
857
858fn validate_index_entry(
861 entity: &EntitySchema,
862 info: &RowInfo,
863 owner: RowKey,
864 key: &[u8],
865) -> Result<(), Error> {
866 if info.key != owner
867 || !index_entries(entity, info)?
868 .iter()
869 .any(|(entry, _)| &entry[..] == key)
870 {
871 return Err(Error::Corrupt);
872 }
873 Ok(())
874}