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