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, bytes) = index_owner(map, entity, key_type, &entry.value())?;
62 Ok(Some((entry.key().clone(), id, bytes)))
63}
64
65fn index_owner<M: Memory>(
66 map: &Map<M>,
67 entity: u32,
68 key_type: FieldType,
69 owner: &[u8],
70) -> Result<(RowKey, Vec<u8>), Error> {
71 let id = RowKey::decode(owner, key_type)?;
72 let bytes = map.get(&row_key(entity, id)).ok_or(Error::Corrupt)?;
73 Ok((id, bytes))
74}
75
76#[inline(never)]
77fn index_prefix_key(
78 entity: &EntitySchema,
79 index: &str,
80 values: &[IndexValue<'_>],
81 limit: usize,
82) -> Result<StoreKey, Error> {
83 let index = entity
84 .indexes
85 .iter()
86 .find(|value| value.name == index)
87 .ok_or(Error::InvalidSchema)?;
88 if values.is_empty() || values.len() > index.fields.len() || !(1..=32).contains(&limit) {
89 return Err(Error::Limit);
90 }
91 StoreKey::new(admit_index_prefix(entity, index, values)?)
92}
93
94fn collect_references(
97 entity: &EntitySchema,
98 info: &RowInfo,
99 required: &mut BTreeSet<(u32, RowKey)>,
100) -> Result<(), Error> {
101 for field in entity.fields {
102 if let Some(reference) = field.reference {
103 let position = entity
104 .indexes
105 .iter()
106 .position(|index| index.id == reference.index)
107 .ok_or(Error::Corrupt)?;
108 let mut bytes = info
109 .indexes
110 .get(position)
111 .and_then(Option::as_ref)
112 .map(Vec::as_slice)
113 .ok_or(Error::Corrupt)?;
114 if field.optional {
115 match bytes.split_first() {
117 Some((0, _)) => continue,
118 Some((1, rest)) => bytes = rest,
119 _ => return Err(Error::Corrupt),
120 }
121 }
122 let mut remaining = bytes;
123 key::consume(&mut remaining, field.value)?;
124 let target = RowKey::decode(&bytes[..bytes.len() - remaining.len()], field.value)?;
125 required.insert((reference.entity, target));
126 }
127 }
128 Ok(())
129}
130
131fn validate_reference_target<M: Memory>(
132 map: &Map<M>,
133 schema: &Schema,
134 entity: u32,
135 id: RowKey,
136) -> Result<(), Error> {
137 let bytes = map
138 .get(&row_key(entity, id))
139 .ok_or(Error::ReferenceViolation)?;
140 let entity = schema
141 .entities()
142 .iter()
143 .find(|value| value.id == entity)
144 .ok_or(Error::Corrupt)?;
145 if entity.inspect_row(&bytes)?.key != id {
146 return Err(Error::Corrupt);
147 }
148 Ok(())
149}
150
151fn manifest_key() -> StoreKey {
152 StoreKey::new(vec![0]).expect("manifest key fits")
153}
154
155fn live_manifest(schema: [u8; 32], incarnation: [u8; 16]) -> Vec<u8> {
156 let mut bytes = MANIFEST.to_vec();
157 bytes.extend(schema);
158 bytes.extend(incarnation);
159 bytes
160}
161
162#[derive(Default)]
164pub struct Batch {
165 operation_time: Option<crate::Timestamp>,
166 mutations: Vec<Mutation>,
167 bytes: usize,
168}
169struct Mutation {
170 entity: &'static EntitySchema,
171 key: RowKey,
172 kind: Kind,
173}
174enum Kind {
175 Insert(Vec<u8>, RowInfo),
176 CopyInsert(Vec<u8>, RowInfo, [Option<crate::Timestamp>; 2]),
178 Replace(Vec<u8>, RowInfo),
179 Delete,
180}
181
182impl Batch {
183 #[must_use]
185 pub fn new() -> Self {
186 Self::default()
187 }
188
189 #[must_use]
192 pub fn at(time: crate::Timestamp) -> Self {
193 Self {
194 operation_time: Some(time),
195 ..Self::default()
196 }
197 }
198
199 pub fn insert<E: Entity>(&mut self, row: &E) -> Result<(), Error> {
203 if E::SCHEMA.has_managed() {
204 return Err(Error::ManagedField);
205 }
206 self.put(row, Kind::Insert)
207 }
208
209 pub fn insert_input<I: crate::InsertInput>(&mut self, input: I) -> Result<I::Entity, Error> {
217 let row = input.__into_entity(self.operation_time)?;
218 self.put(&row, Kind::Insert)?;
219 Ok(row)
220 }
221
222 pub fn replace<E: Entity>(&mut self, row: &E) -> Result<(), Error> {
228 self.put(row, Kind::Replace)
229 }
230
231 pub fn delete<E: Entity>(&mut self, key: E::Key) -> Result<(), Error> {
235 self.push(
236 Mutation {
237 entity: E::SCHEMA,
238 key: key.into_row_key(),
239 kind: Kind::Delete,
240 },
241 0,
242 )
243 }
244
245 fn put<E: Entity>(
246 &mut self,
247 row: &E,
248 kind: impl FnOnce(Vec<u8>, RowInfo) -> Kind,
249 ) -> Result<(), Error> {
250 let bytes = row.encode()?;
251 if bytes.len() > crate::__private::MAX_ROW_BYTES {
252 return Err(Error::Limit);
253 }
254 let info = row.__row_info();
257 let key = info.key;
258 let len = bytes.len();
259 let kind = kind(bytes, info);
260 if E::SCHEMA.has_managed()
261 && self.operation_time.is_none()
262 && !matches!(kind, Kind::CopyInsert(..))
263 {
264 return Err(Error::MissingOperationTime);
265 }
266 self.push(
267 Mutation {
268 entity: E::SCHEMA,
269 key,
270 kind,
271 },
272 len,
273 )
274 }
275
276 fn push(&mut self, mutation: Mutation, bytes: usize) -> Result<(), Error> {
277 if self.mutations.len() == MAX_BATCH || bytes > MAX_BATCH_BYTES - self.bytes {
278 return Err(Error::Limit);
279 }
280 self.bytes += bytes;
281 self.mutations.push(mutation);
282 Ok(())
283 }
284}
285
286pub struct Page<E: Entity> {
288 pub rows: Vec<E>,
290 pub next_after: Option<E::Key>,
292}
293
294pub struct Database<M: Memory> {
296 map: Map<M>,
297 schema: Schema,
298 incarnation: [u8; 16],
299}
300
301impl<M: Memory> Database<M> {
302 pub fn create(
308 memory: RuntimeMemory<M>,
309 schema: Schema,
310 incarnation: [u8; 16],
311 ) -> Result<Self, Error> {
312 if incarnation == [0; 16] {
313 return Err(Error::InvalidSchema);
314 }
315 if memory.size() != 0 {
316 return Err(Error::Exists);
317 }
318 let mut map = Map::create(memory);
319 map.insert(
320 manifest_key(),
321 live_manifest(schema.fingerprint, incarnation),
322 );
323 for entity in &schema.entities {
324 map.insert(entity_state_key(entity.id), EntityState::default().encode());
325 }
326 Ok(Self {
327 map,
328 schema,
329 incarnation,
330 })
331 }
332
333 pub fn open(memory: RuntimeMemory<M>, schema: Schema) -> Result<Self, Error> {
341 if memory.size() == 0 {
342 return Err(Error::Corrupt);
343 }
344 let map = Map::load(memory);
345 let manifest = map.get(&manifest_key()).ok_or(Error::Corrupt)?;
346 if maintenance::admits_gate(&manifest)? {
347 return Err(Error::Maintenance);
348 }
349 if manifest.len() != 56 {
350 return Err(Error::Corrupt);
351 }
352 if &manifest[..8] != MANIFEST || manifest[8..40] != schema.fingerprint {
353 return Err(Error::IncompatibleSchema);
354 }
355 let incarnation = manifest[40..].try_into().map_err(|_| Error::Corrupt)?;
356 if incarnation == [0; 16] {
357 return Err(Error::Corrupt);
358 }
359 Ok(Self {
360 map,
361 schema,
362 incarnation,
363 })
364 }
365
366 #[must_use]
368 pub const fn schema(&self) -> &Schema {
369 &self.schema
370 }
371
372 #[must_use]
374 pub const fn incarnation(&self) -> [u8; 16] {
375 self.incarnation
376 }
377
378 pub fn revision<E: Entity>(&self) -> Result<u64, Error> {
382 let entity = self.schema.admits(E::SCHEMA)?;
383 read_revision(&self.map, entity.id)
384 }
385
386 pub fn cardinality<E: Entity>(&self) -> Result<u64, Error> {
394 let entity = self.schema.admits(E::SCHEMA)?;
395 Ok(read_entity_state(&self.map, entity.id)?.count)
396 }
397
398 pub fn cardinality_by_name(&self, name: &str) -> Result<u64, Error> {
405 let entity = self
406 .schema
407 .entities
408 .iter()
409 .find(|entity| entity.name == name)
410 .ok_or(Error::UnknownEntity)?;
411 Ok(read_entity_state(&self.map, entity.id)?.count)
412 }
413
414 fn revision_by_id(&self, entity: u32) -> Result<u64, Error> {
415 if !self.schema.entities.iter().any(|value| value.id == entity) {
416 return Err(Error::UnknownEntity);
417 }
418 read_revision(&self.map, entity)
419 }
420
421 #[inline]
425 pub fn get<E: Entity>(&self, key: E::Key) -> Result<Option<E>, Error> {
426 let entity = self.schema.admits(E::SCHEMA)?;
427 self.get_typed::<E>(entity, key)
428 }
429
430 #[inline(never)]
433 fn get_typed<E: Entity>(&self, entity: &EntitySchema, key: E::Key) -> Result<Option<E>, Error> {
434 self.map
435 .get(&row_key(entity.id, key.into_row_key()))
436 .map(|bytes| {
437 let row = E::decode(&bytes)?;
438 if row.key() != key {
439 return Err(Error::Corrupt);
440 }
441 Ok(row)
442 })
443 .transpose()
444 }
445
446 #[inline]
452 pub fn page<E: Entity>(&self, after: Option<E::Key>, limit: usize) -> Result<Page<E>, Error> {
453 let entity = self.schema.admits(E::SCHEMA)?;
454 self.page_typed::<E>(entity, after, limit)
455 }
456
457 #[inline(never)]
458 fn page_typed<E: Entity>(
459 &self,
460 entity: &EntitySchema,
461 after: Option<E::Key>,
462 limit: usize,
463 ) -> Result<Page<E>, Error> {
464 if !(1..=32).contains(&limit) {
465 return Err(Error::Limit);
466 }
467 let prefix = prefix(2, entity.id);
468 let start = after.map_or_else(
469 || StoreKey::new(prefix.clone()).expect("row namespace fits"),
470 |key| row_key(entity.id, key.into_row_key()),
471 );
472 let lower = if after.is_some() {
473 std::ops::Bound::Excluded(start)
474 } else {
475 std::ops::Bound::Included(start)
476 };
477 let mut entries = self.map.range((lower, std::ops::Bound::Unbounded));
478 let key_type = entity.key_type()?;
479 let mut rows = Vec::new();
480 let mut last = None;
481 for _ in 0..limit {
482 let Some((id, bytes)) = next_primary(&mut entries, &prefix, key_type)? else {
483 break;
484 };
485 let id = E::Key::from_row_key(id)?;
486 let row = E::decode(&bytes)?;
487 if row.key() != id {
488 return Err(Error::Corrupt);
489 }
490 rows.push(row);
491 last = Some(id);
492 }
493 Ok(Page {
494 next_after: if rows.len() == limit { last } else { None },
495 rows,
496 })
497 }
498
499 pub fn get_by_unique<E: Entity>(
505 &self,
506 index: &str,
507 values: &[IndexValue<'_>],
508 ) -> Result<Option<E>, Error> {
509 let entity = self.schema.admits(E::SCHEMA)?;
510 let index = entity
511 .indexes
512 .iter()
513 .find(|i| i.name == index)
514 .ok_or(Error::InvalidSchema)?;
515 if !index.unique || values.len() != index.fields.len() {
516 return Err(Error::InvalidQuery);
517 }
518 let key = StoreKey::new(admit_index_prefix(entity, index, values)?)?;
519 let Some(owner) = self.map.get(&key) else {
520 return Ok(None);
521 };
522 let (id, bytes) = index_owner(&self.map, entity.id, entity.key_type()?, &owner)?;
523 let row = E::decode(&bytes)?;
524 validate_index_entry(entity, &row.__row_info(), id, &key)?;
525 Ok(Some(row))
526 }
527
528 #[inline]
536 pub fn index_prefix<E: Entity>(
537 &self,
538 index: &str,
539 values: &[IndexValue<'_>],
540 limit: usize,
541 ) -> Result<Vec<E>, Error> {
542 let entity = self.schema.admits(E::SCHEMA)?;
543 self.index_prefix_typed::<E>(entity, index, values, limit)
544 }
545
546 #[inline(never)]
547 fn index_prefix_typed<E: Entity>(
548 &self,
549 entity: &EntitySchema,
550 index: &str,
551 values: &[IndexValue<'_>],
552 limit: usize,
553 ) -> Result<Vec<E>, Error> {
554 let prefix = index_prefix_key(entity, index, values, limit)?;
555 let mut rows = Vec::new();
556 let mut entries = self.map.range(prefix.clone()..);
557 let key_type = entity.key_type()?;
558 for _ in 0..limit {
559 let Some((key, id, bytes)) =
560 next_index(&self.map, &mut entries, &prefix, entity.id, key_type)?
561 else {
562 break;
563 };
564 let row = E::decode(&bytes)?;
565 validate_index_entry(entity, &row.__row_info(), id, &key)?;
566 rows.push(row);
567 }
568 Ok(rows)
569 }
570
571 pub fn commit(&mut self, batch: Batch) -> Result<(), Error> {
580 let mut targets = BTreeSet::new();
581 let mut removes = BTreeSet::new();
582 let mut writes = BTreeMap::new();
583 let mut unique = BTreeSet::new();
584 let mut entities = BTreeMap::new();
587 let mut required = BTreeSet::new();
588 let mut deleted = Vec::new();
589 for mut mutation in batch.mutations {
590 self.schema.admits(mutation.entity)?;
591 let key = row_key(mutation.entity.id, mutation.key);
592 if !targets.insert(key.clone()) {
593 return Err(Error::DuplicateTarget);
594 }
595 let old = self.map.get(&key);
596 match (&mutation.kind, &old) {
597 (Kind::Insert(..) | Kind::CopyInsert(..), Some(_)) => return Err(Error::Exists),
598 (Kind::Replace(..) | Kind::Delete, None) => return Err(Error::Missing),
599 _ => {}
600 }
601 if mutation.entity.has_managed() {
602 match &mut mutation.kind {
603 Kind::Insert(bytes, _) => crate::managed::validate_insert(
604 mutation.entity,
605 bytes,
606 batch.operation_time.ok_or(Error::MissingOperationTime)?,
607 )?,
608 Kind::Replace(bytes, info) => {
609 if crate::managed::replace(
610 mutation.entity,
611 bytes,
612 old.as_deref().ok_or(Error::Missing)?,
613 batch.operation_time.ok_or(Error::MissingOperationTime)?,
614 )? {
615 *info = mutation.entity.inspect_row(bytes)?;
616 }
617 }
618 Kind::CopyInsert(bytes, _, expected) => {
619 if crate::managed::values(mutation.entity, bytes)? != *expected {
620 return Err(Error::ManagedField);
621 }
622 }
623 Kind::Delete => {}
624 }
625 }
626 let mut after_indexes = match &mutation.kind {
629 Kind::Insert(_, info) | Kind::CopyInsert(_, info, _) | Kind::Replace(_, info) => {
630 index_entries(mutation.entity, info)?
631 }
632 Kind::Delete => Vec::new(),
633 };
634 let (_, changed, delta) = match entities.entry(mutation.entity.id) {
635 std::collections::btree_map::Entry::Occupied(entry) => entry.into_mut(),
636 std::collections::btree_map::Entry::Vacant(entry) => entry.insert((
637 read_entity_state(&self.map, mutation.entity.id)?,
638 false,
639 0_i64,
640 )),
641 };
642 if let (Kind::Replace(bytes, _), Some(old)) = (&mutation.kind, &old)
643 && bytes == old
644 {
645 continue;
646 }
647 if let Some(old) = old {
648 let info = mutation.entity.inspect_row(&old)?;
649 if info.key != mutation.key {
650 return Err(Error::Corrupt);
651 }
652 let owner = info.key.encode();
653 for (key, _) in index_entries(mutation.entity, &info)? {
654 if self.map.get(&key).as_deref() != Some(owner.as_slice()) {
655 return Err(Error::Corrupt);
656 }
657 if let Some(position) =
660 after_indexes.iter().position(|(after, _)| *after == key)
661 {
662 after_indexes.remove(position);
663 } else {
664 removes.insert(key);
665 }
666 }
667 }
668 *changed = true;
669 *delta += match &mutation.kind {
670 Kind::Insert(..) | Kind::CopyInsert(..) => 1,
671 Kind::Delete => -1,
672 Kind::Replace(..) => 0,
673 };
674 let copy_insert = matches!(&mutation.kind, Kind::CopyInsert(..));
677 match mutation.kind {
678 Kind::Delete => {
679 deleted.push((mutation.entity.id, mutation.key));
680 removes.insert(key);
681 }
682 Kind::Insert(bytes, info)
683 | Kind::CopyInsert(bytes, info, _)
684 | Kind::Replace(bytes, info) => {
685 writes.insert(key, bytes);
686 for (key, is_unique) in after_indexes {
687 if is_unique && !unique.insert(key.clone()) {
688 return Err(Error::UniqueViolation);
689 }
690 writes.insert(key, info.key.encode());
691 }
692 if !copy_insert {
693 collect_references(mutation.entity, &info, &mut required)?;
694 }
695 }
696 }
697 }
698 for key in unique {
700 if self.map.contains_key(&key) && !removes.contains(&key) {
701 return Err(Error::UniqueViolation);
702 }
703 }
704 self.validate_references(&required, &deleted, &removes, &writes)?;
705 for (entity, (mut state, changed, delta)) in entities {
706 if changed {
707 state.revision = state.revision.checked_add(1).ok_or(Error::Limit)?;
708 state.count = if delta >= 0 {
709 state.count.checked_add(delta as u64).ok_or(Error::Limit)?
710 } else {
711 state
712 .count
713 .checked_sub((-delta) as u64)
714 .ok_or(Error::Corrupt)?
715 };
716 writes.insert(entity_state_key(entity), state.encode());
717 }
718 }
719 for key in removes {
721 self.map.remove(&key);
722 }
723 for (key, value) in writes {
724 self.map.insert(key, value);
725 }
726 Ok(())
727 }
728
729 fn validate_references(
732 &self,
733 required: &BTreeSet<(u32, RowKey)>,
734 deleted: &[(u32, RowKey)],
735 removes: &BTreeSet<StoreKey>,
736 writes: &BTreeMap<StoreKey, Vec<u8>>,
737 ) -> Result<(), Error> {
738 for &(entity, id) in required {
739 let key = row_key(entity, id);
740 if writes.contains_key(&key) {
741 continue;
742 } if removes.contains(&key) {
744 return Err(Error::ReferenceViolation);
745 }
746 validate_reference_target(&self.map, &self.schema, entity, id)?;
747 }
748 for &(target, id) in deleted {
749 for entity in &self.schema.entities {
750 for field in entity.fields {
751 let Some(reference) = field.reference.filter(|value| value.entity == target)
752 else {
753 continue;
754 };
755 let mut prefix = index_prefix(entity.id, reference.index);
756 id.index_value()
757 .append_component(field.optional, &mut prefix);
758 let prefix = StoreKey::new(prefix)?;
759 for (position, entry) in self
762 .map
763 .range(prefix.clone()..)
764 .take_while(|entry| entry.key().starts_with(&prefix))
765 .take(MAX_BATCH + 1)
766 .enumerate()
767 {
768 if removes.contains(entry.key()) {
769 if position == MAX_BATCH {
770 return Err(Error::Corrupt);
771 }
772 continue;
773 }
774 let owner = RowKey::decode(&entry.value(), entity.key_type()?)?;
775 let bytes = self
776 .map
777 .get(&row_key(entity.id, owner))
778 .ok_or(Error::Corrupt)?;
779 let info = entity.inspect_row(&bytes)?;
780 validate_index_entry(entity, &info, owner, entry.key())?;
781 return Err(Error::ReferenceViolation);
782 }
783 }
784 }
785 }
786 Ok(())
787 }
788}
789
790fn prefix(tag: u8, entity: u32) -> Vec<u8> {
791 let mut key = vec![tag];
792 key.extend(entity.to_be_bytes());
793 key
794}
795
796fn entity_state_key(entity: u32) -> StoreKey {
797 StoreKey::new(prefix(1, entity)).expect("entity state key fits")
798}
799
800fn read_revision<M: Memory>(map: &Map<M>, entity: u32) -> Result<u64, Error> {
801 Ok(read_entity_state(map, entity)?.revision)
802}
803
804#[derive(Default)]
806struct EntityState {
807 revision: u64,
808 count: u64,
809}
810impl EntityState {
811 fn encode(&self) -> Vec<u8> {
812 let mut bytes = self.revision.to_le_bytes().to_vec();
813 bytes.extend(self.count.to_le_bytes());
814 bytes
815 }
816}
817fn read_entity_state<M: Memory>(map: &Map<M>, entity: u32) -> Result<EntityState, Error> {
818 let bytes = map.get(&entity_state_key(entity)).ok_or(Error::Corrupt)?;
819 if bytes.len() != 16 {
820 return Err(Error::Corrupt);
821 }
822 Ok(EntityState {
823 revision: u64::from_le_bytes(bytes[..8].try_into().map_err(|_| Error::Corrupt)?),
824 count: u64::from_le_bytes(bytes[8..].try_into().map_err(|_| Error::Corrupt)?),
825 })
826}
827
828fn row_key(entity: u32, id: RowKey) -> StoreKey {
829 let mut key = prefix(2, entity);
830 id.append_to(&mut key);
831 StoreKey::new(key).expect("bounded primary key fits")
832}
833const INDEX_PREFIX_BYTES: usize = 9; fn index_prefix(entity: u32, index: u32) -> Vec<u8> {
835 let mut key = prefix(3, entity);
836 key.extend(index.to_be_bytes());
837 key
838}
839fn admit_index_prefix(
841 entity: &EntitySchema,
842 index: &crate::IndexSchema,
843 values: &[IndexValue<'_>],
844) -> Result<Vec<u8>, Error> {
845 if values.len() > index.fields.len() {
846 return Err(Error::Limit);
847 }
848 let mut prefix = index_prefix(entity.id, index.id);
849 for (value, name) in values.iter().zip(index.fields) {
850 let field = entity
851 .fields
852 .iter()
853 .find(|field| field.name == *name)
854 .ok_or(Error::InvalidSchema)?;
855 value.admit(field.value, field.optional)?;
856 if index.present_only && *value == IndexValue::Absent {
857 return Err(Error::InvalidOperand);
858 }
859 value.append_component(field.optional, &mut prefix);
860 if prefix.len() > crate::MAX_INDEX_KEY_BYTES {
861 return Err(Error::Limit);
862 }
863 }
864 let mut completion = if index.unique {
865 0
866 } else {
867 key::minimum_bytes(entity.key_type()?)?
868 };
869 for name in &index.fields[values.len()..] {
870 let field = entity
871 .fields
872 .iter()
873 .find(|field| field.name == *name)
874 .ok_or(Error::InvalidSchema)?;
875 completion += if field.optional && !index.present_only {
876 1
877 } else {
878 key::minimum_bytes(field.value)? + usize::from(field.optional)
879 };
880 }
881 if prefix.len() + completion > crate::MAX_INDEX_KEY_BYTES {
882 return Err(Error::Limit);
883 }
884 Ok(prefix)
885}
886fn visit_index_components(
888 entity: &EntitySchema,
889 info: &RowInfo,
890 mut visit: impl FnMut(&crate::IndexSchema, &[u8]) -> Result<(), Error>,
891) -> Result<(), Error> {
892 if info.indexes.len() != entity.indexes.len() {
893 return Err(Error::Corrupt);
894 }
895 for (index, values) in entity.indexes.iter().zip(&info.indexes) {
896 let Some(values) = values else {
897 if index.present_only {
898 continue;
899 }
900 return Err(Error::Corrupt);
901 };
902 let mut remaining = values.as_slice();
903 for name in index.fields {
904 let field = entity
905 .fields
906 .iter()
907 .find(|field| field.name == *name)
908 .ok_or(Error::Corrupt)?;
909 if field.optional {
910 let (&presence, rest) = remaining.split_first().ok_or(Error::Corrupt)?;
911 remaining = rest;
912 match presence {
913 0 if !index.present_only => continue,
914 1 => {}
915 _ => return Err(Error::Corrupt),
916 }
917 }
918 key::consume(&mut remaining, field.value)?;
919 }
920 if !remaining.is_empty() {
921 return Err(Error::Corrupt);
922 }
923 visit(index, values)?;
924 }
925 Ok(())
926}
927
928fn index_entries(entity: &EntitySchema, info: &RowInfo) -> Result<Vec<(StoreKey, bool)>, Error> {
929 let mut entries = Vec::new();
930 visit_index_components(entity, info, |index, values| {
931 let mut key = index_prefix(entity.id, index.id);
932 key.extend_from_slice(values);
933 if !index.unique {
934 info.key.append_to(&mut key);
935 }
936 entries.push((StoreKey::new(key)?, index.unique));
937 Ok(())
938 })?;
939 Ok(entries)
940}
941
942fn validate_index_entry(
945 entity: &EntitySchema,
946 info: &RowInfo,
947 owner: RowKey,
948 key: &[u8],
949) -> Result<(), Error> {
950 if info.key != owner {
951 return Err(Error::Corrupt);
952 }
953 let (header, payload) = key
954 .split_at_checked(INDEX_PREFIX_BYTES)
955 .ok_or(Error::Corrupt)?;
956 if header[0] != 3 || header[1..5] != entity.id.to_be_bytes() {
957 return Err(Error::Corrupt);
958 }
959 let mut matches = false;
960 let owner = owner.encode();
961 visit_index_components(entity, info, |index, values| {
962 let suffix = if index.unique {
963 &[][..]
964 } else {
965 owner.as_slice()
966 };
967 if INDEX_PREFIX_BYTES + values.len() + suffix.len() > crate::MAX_INDEX_KEY_BYTES {
968 return Err(Error::Limit);
969 }
970 if header[5..] == index.id.to_be_bytes() {
971 matches = payload.strip_prefix(values) == Some(suffix);
972 }
973 Ok(())
974 })?;
975 if !matches {
976 return Err(Error::Corrupt);
977 }
978 Ok(())
979}