Skip to main content

ic_db/store/
mod.rs

1//! Shared commit and traversal over one supplier-owned collection.
2//! Typed codecs stay at the boundary; no executor is generated per entity.
3
4use 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// Share supplier advancement and physical-key decoding without buffering a page
29// or moving the typed row/key consistency check out of the public terminal.
30#[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// The typed caller checks the decoded row's index components against this key.
47#[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
84// Both ordinary batches and complete-target migration validation derive present
85// references from the same admitted reverse-index components.
86fn 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                // Absence has no target; zero remains an ordinary target key.
106                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/// A bounded synchronous batch; preparation is internal to `Database::commit`.
152#[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    // Only maintenance can construct this; ordinary insert policies stay intact.
166    CopyInsert(Vec<u8>, RowInfo, [Option<crate::Timestamp>; 2]),
167    Replace(Vec<u8>, RowInfo),
168    Delete,
169}
170
171impl Batch {
172    /// Begin an empty batch without persistent effects.
173    #[must_use]
174    pub fn new() -> Self {
175        Self::default()
176    }
177    /// Begin a batch with one host-captured operation time for all managed fields.
178    /// The database reads no clock; this value remains fixed for the whole batch.
179    #[must_use]
180    pub fn at(time: crate::Timestamp) -> Self {
181        Self {
182            operation_time: Some(time),
183            ..Self::default()
184        }
185    }
186    /// Insert a typed record. Primary-key/uniqueness admission happens at commit.
187    /// # Errors
188    /// Refuses managed-field entities (use `insert_input`), encoding or batch capacity.
189    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    /// Resolve a typed insert input, append it to this batch and return its full row.
196    /// This is preparation, not a commit; the returned row is not yet persistent.
197    /// Explicit `None` remains absence, while omitted fields select their declared
198    /// literal default or optional absence. No defaults run during replacement.
199    /// # Errors
200    /// Refuses missing required values, field/row bounds or batch capacity.
201    /// A refused input appends no mutation to the batch.
202    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    /// Replace an existing typed record, retaining its primary key.
208    /// Managed fields must echo the current stored values; commit sets update time
209    /// only on a real change. Read the row after commit to obtain that assigned time.
210    /// # Errors
211    /// Refuses missing operation time, encoding or batch capacity before mutation.
212    pub fn replace<E: Entity>(&mut self, row: &E) -> Result<(), Error> {
213        self.put(row, Kind::Replace)
214    }
215    /// Delete an existing primary key; no recursive cascades are implied.
216    /// # Errors
217    /// Refuses batch capacity before persistent mutation.
218    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        // encode() admitted field/row bounds. Keys come from that same typed
238        // value; decoding freshly encoded bytes would duplicate codec work.
239        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
268/// A page with explicit progress; a full page may require an empty final call.
269pub struct Page<E: Entity> {
270    /// Typed records from this bounded primary-key traversal.
271    pub rows: Vec<E>,
272    /// Last processed key, when further traversal may remain.
273    pub next_after: Option<E::Key>,
274}
275
276/// Admitted database owning the supplier's exclusive collection lease.
277pub struct Database<M: Memory = DefaultMemoryImpl> {
278    map: Map<M>,
279    schema: Schema,
280    incarnation: [u8; 16],
281}
282
283impl<M: Memory> Database<M> {
284    /// Create in a proven empty governed allocation. Never resets existing data.
285    /// # Errors
286    /// Refuses an all-zero incarnation or nonempty/unsupported supplier allocation.
287    /// # Panics
288    /// Supplier failures after initialization starts trap the enclosing IC message.
289    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    /// Open only an exact manifest/compiled-contract match, without mutation.
315    /// This is not a whole-database integrity scan. Entity metadata is checked
316    /// when read explicitly or when preparing a write to that entity.
317    /// # Errors
318    /// Refuses active maintenance, missing/corrupt manifests, foreign contracts or supplier formats.
319    /// # Panics
320    /// Supplier corruption, including overlong stored keys, traps without repair.
321    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    /// Borrow the admitted executable description for inspection.
347    #[must_use]
348    pub const fn schema(&self) -> &Schema {
349        &self.schema
350    }
351    /// Durable database identity, distinct from schema identity.
352    #[must_use]
353    pub const fn incarnation(&self) -> [u8; 16] {
354        self.incarnation
355    }
356    /// Read the atomic revision of one admitted entity.
357    /// # Errors
358    /// Refuses unknown entities and malformed revision metadata.
359    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    /// Read the exact maintained whole-entity row count without scanning rows.
364    /// This trusts atomic entity metadata; it does not validate row/index integrity.
365    /// Filtered counts and row-validating enumeration use the fluent query API.
366    /// # Errors
367    /// Refuses unadmitted entities and missing or malformed entity metadata.
368    /// # Panics
369    /// Supplier corruption may trap; this operation never repairs storage.
370    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    /// Inspect the maintained whole-entity count by exact admitted schema name.
375    /// Like [`Self::cardinality`], this reads metadata without validating rows or indexes.
376    /// # Errors
377    /// Refuses unknown names and missing or malformed entity metadata.
378    /// # Panics
379    /// Supplier corruption may trap; this operation never repairs storage.
380    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    /// Read a typed primary key without planning a scan.
396    /// # Errors
397    /// Refuses unadmitted types or malformed rows.
398    #[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    // Keep traversal separate from the static type's admission call. Passing
405    // its admitted descriptor lets compatible typed readers share machine code.
406    #[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    /// Read at most 32 rows in primary-key order; continuation is live, not a snapshot.
420    /// # Errors
421    /// Refuses zero/oversized limits, unadmitted types or corrupt rows.
422    /// # Panics
423    /// Supplier corruption, including overlong stored keys, traps without repair.
424    #[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    /// Read the first bounded collection under an exact, nonempty leading index prefix.
472    /// Exact operands obey field bounds and the 512-byte complete-key budget.
473    /// Use `IndexValue::Absent` for an absent optional component. A present-only
474    /// unique index refuses absent operands because it does not enumerate those rows.
475    /// # Errors
476    /// Refuses unknown indexes, mismatched operand types, invalid prefix/limit or
477    /// inconsistent index entries. This method does not yet return continuation.
478    #[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    /// Prepare final state, then synchronously apply rows, indexes, revisions and counts.
515    /// A normal refusal occurs before persistent writes. Success is not a separate
516    /// durability point from the surrounding IC message. Empty/no-op batches preserve revisions.
517    /// # Errors
518    /// Refuses missing/existing rows, duplicate targets, uniqueness/reference violations,
519    /// corruption or limits. References use the intended final batch state.
520    /// # Panics
521    /// Supplier failures after the first mutation trap; never catch and continue an IC commit.
522    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        // Observe each entity once, then apply its final net row delta. A balanced
528        // delete/insert batch must not depend on mutation order. No state survives calls.
529        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            // Admit complete after-image keys even when the row is a no-op.
570            // Retain these buffers for publication instead of encoding twice.
571            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            // Private migration inserts may precede their targets. The frozen
609            // complete target validates references before it can be published.
610            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        // Check existing owners only after all releases in this batch are known.
633        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        // Proven IC rollback boundary: no recoverable Result branch below this line.
654        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    // Reuse the prepared final rows and ordinary index changes. No durable
664    // relationship catalog or second mutation executor is involved.
665    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            } // prepared, validated final target
677            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                    // Each skipped entry belongs to a distinct changed row in
694                    // this range. At most MAX_BATCH skips plus one survivor.
695                    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/// One atomic metadata record; neither value is reconstructed during ordinary open.
737#[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}
769// Direct lookups and fluent reads share exact prefix admission and completion bounds.
770fn 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
859// Both indexed reads and reverse-reference checks must prove the physical entry
860// belongs to the decoded row, rather than trusting a valid-looking owner alone.
861fn 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}