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