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 mut 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                let owner = info.key.encode();
596                for (key, _) in index_entries(mutation.entity, &info)? {
597                    if self.map.get(&key).as_deref() != Some(owner.as_slice()) {
598                        return Err(Error::Corrupt);
599                    }
600                    // Same physical key and owner: leave the verified entry in place.
601                    // Its unique value remains occupied during final-state admission.
602                    if let Some(position) =
603                        after_indexes.iter().position(|(after, _)| *after == key)
604                    {
605                        after_indexes.remove(position);
606                    } else {
607                        removes.insert(key);
608                    }
609                }
610            }
611            *changed = true;
612            *delta += match &mutation.kind {
613                Kind::Insert(..) | Kind::CopyInsert(..) => 1,
614                Kind::Delete => -1,
615                Kind::Replace(..) => 0,
616            };
617            // Private migration inserts may precede their targets. The frozen
618            // complete target validates references before it can be published.
619            let copy_insert = matches!(&mutation.kind, Kind::CopyInsert(..));
620            match mutation.kind {
621                Kind::Delete => {
622                    deleted.push((mutation.entity.id, mutation.key));
623                    removes.insert(key);
624                }
625                Kind::Insert(bytes, info)
626                | Kind::CopyInsert(bytes, info, _)
627                | Kind::Replace(bytes, info) => {
628                    writes.insert(key, bytes);
629                    for (key, is_unique) in after_indexes {
630                        if is_unique && !unique.insert(key.clone()) {
631                            return Err(Error::UniqueViolation);
632                        }
633                        writes.insert(key, info.key.encode());
634                    }
635                    if !copy_insert {
636                        collect_references(mutation.entity, &info, &mut required)?;
637                    }
638                }
639            }
640        }
641        // Check existing owners only after all releases in this batch are known.
642        for key in unique {
643            if self.map.contains_key(&key) && !removes.contains(&key) {
644                return Err(Error::UniqueViolation);
645            }
646        }
647        self.validate_references(&required, &deleted, &removes, &writes)?;
648        for (entity, (mut state, changed, delta)) in entities {
649            if changed {
650                state.revision = state.revision.checked_add(1).ok_or(Error::Limit)?;
651                state.count = if delta >= 0 {
652                    state.count.checked_add(delta as u64).ok_or(Error::Limit)?
653                } else {
654                    state
655                        .count
656                        .checked_sub((-delta) as u64)
657                        .ok_or(Error::Corrupt)?
658                };
659                writes.insert(entity_state_key(entity), state.encode());
660            }
661        }
662        // Proven IC rollback boundary: no recoverable Result branch below this line.
663        for key in removes {
664            self.map.remove(&key);
665        }
666        for (key, value) in writes {
667            self.map.insert(key, value);
668        }
669        Ok(())
670    }
671
672    // Reuse the prepared final rows and ordinary index changes. No durable
673    // relationship catalog or second mutation executor is involved.
674    fn validate_references(
675        &self,
676        required: &BTreeSet<(u32, RowKey)>,
677        deleted: &[(u32, RowKey)],
678        removes: &BTreeSet<StoreKey>,
679        writes: &BTreeMap<StoreKey, Vec<u8>>,
680    ) -> Result<(), Error> {
681        for &(entity, id) in required {
682            let key = row_key(entity, id);
683            if writes.contains_key(&key) {
684                continue;
685            } // prepared, validated final target
686            if removes.contains(&key) {
687                return Err(Error::ReferenceViolation);
688            }
689            validate_reference_target(&self.map, &self.schema, entity, id)?;
690        }
691        for &(target, id) in deleted {
692            for entity in &self.schema.entities {
693                for field in entity.fields {
694                    let Some(reference) = field.reference.filter(|value| value.entity == target)
695                    else {
696                        continue;
697                    };
698                    let mut prefix = index_prefix(entity.id, reference.index);
699                    id.index_value()
700                        .append_component(field.optional, &mut prefix);
701                    let prefix = StoreKey::new(prefix)?;
702                    // Each skipped entry belongs to a distinct changed row in
703                    // this range. At most MAX_BATCH skips plus one survivor.
704                    for (position, entry) in self
705                        .map
706                        .range(prefix.clone()..)
707                        .take_while(|entry| entry.key().starts_with(&prefix))
708                        .take(MAX_BATCH + 1)
709                        .enumerate()
710                    {
711                        if removes.contains(entry.key()) {
712                            if position == MAX_BATCH {
713                                return Err(Error::Corrupt);
714                            }
715                            continue;
716                        }
717                        let owner = RowKey::decode(&entry.value(), entity.key_type()?)?;
718                        let bytes = self
719                            .map
720                            .get(&row_key(entity.id, owner))
721                            .ok_or(Error::Corrupt)?;
722                        let info = entity.inspect_row(&bytes)?;
723                        validate_index_entry(entity, &info, owner, entry.key())?;
724                        return Err(Error::ReferenceViolation);
725                    }
726                }
727            }
728        }
729        Ok(())
730    }
731}
732
733fn prefix(tag: u8, entity: u32) -> Vec<u8> {
734    let mut key = vec![tag];
735    key.extend(entity.to_be_bytes());
736    key
737}
738fn entity_state_key(entity: u32) -> StoreKey {
739    StoreKey::new(prefix(1, entity)).expect("entity state key fits")
740}
741fn read_revision<M: Memory>(map: &Map<M>, entity: u32) -> Result<u64, Error> {
742    Ok(read_entity_state(map, entity)?.revision)
743}
744
745/// One atomic metadata record; neither value is reconstructed during ordinary open.
746#[derive(Default)]
747struct EntityState {
748    revision: u64,
749    count: u64,
750}
751impl EntityState {
752    fn encode(&self) -> Vec<u8> {
753        let mut bytes = self.revision.to_le_bytes().to_vec();
754        bytes.extend(self.count.to_le_bytes());
755        bytes
756    }
757}
758fn read_entity_state<M: Memory>(map: &Map<M>, entity: u32) -> Result<EntityState, Error> {
759    let bytes = map.get(&entity_state_key(entity)).ok_or(Error::Corrupt)?;
760    if bytes.len() != 16 {
761        return Err(Error::Corrupt);
762    }
763    Ok(EntityState {
764        revision: u64::from_le_bytes(bytes[..8].try_into().map_err(|_| Error::Corrupt)?),
765        count: u64::from_le_bytes(bytes[8..].try_into().map_err(|_| Error::Corrupt)?),
766    })
767}
768fn row_key(entity: u32, id: RowKey) -> StoreKey {
769    let mut key = prefix(2, entity);
770    id.append_to(&mut key);
771    StoreKey::new(key).expect("bounded primary key fits")
772}
773const INDEX_PREFIX_BYTES: usize = 9; // namespace tag, entity handle and index handle
774fn index_prefix(entity: u32, index: u32) -> Vec<u8> {
775    let mut key = prefix(3, entity);
776    key.extend(index.to_be_bytes());
777    key
778}
779// Direct lookups and fluent reads share exact prefix admission and completion bounds.
780fn admit_index_prefix(
781    entity: &EntitySchema,
782    index: &crate::IndexSchema,
783    values: &[IndexValue<'_>],
784) -> Result<Vec<u8>, Error> {
785    if values.len() > index.fields.len() {
786        return Err(Error::Limit);
787    }
788    let mut prefix = index_prefix(entity.id, index.id);
789    for (value, name) in values.iter().zip(index.fields) {
790        let field = entity
791            .fields
792            .iter()
793            .find(|field| field.name == *name)
794            .ok_or(Error::InvalidSchema)?;
795        value.admit(field.value, field.optional)?;
796        if index.present_only && *value == IndexValue::Absent {
797            return Err(Error::InvalidOperand);
798        }
799        value.append_component(field.optional, &mut prefix);
800        if prefix.len() > crate::MAX_INDEX_KEY_BYTES {
801            return Err(Error::Limit);
802        }
803    }
804    let mut completion = if index.unique {
805        0
806    } else {
807        key::minimum_bytes(entity.key_type()?)?
808    };
809    for name in &index.fields[values.len()..] {
810        let field = entity
811            .fields
812            .iter()
813            .find(|field| field.name == *name)
814            .ok_or(Error::InvalidSchema)?;
815        completion += if field.optional && !index.present_only {
816            1
817        } else {
818            key::minimum_bytes(field.value)? + usize::from(field.optional)
819        };
820    }
821    if prefix.len() + completion > crate::MAX_INDEX_KEY_BYTES {
822        return Err(Error::Limit);
823    }
824    Ok(prefix)
825}
826// RowInfo may come from a generated entity or the shared stored-row decoder.
827fn visit_index_components(
828    entity: &EntitySchema,
829    info: &RowInfo,
830    mut visit: impl FnMut(&crate::IndexSchema, &[u8]) -> Result<(), Error>,
831) -> Result<(), Error> {
832    if info.indexes.len() != entity.indexes.len() {
833        return Err(Error::Corrupt);
834    }
835    for (index, values) in entity.indexes.iter().zip(&info.indexes) {
836        let Some(values) = values else {
837            if index.present_only {
838                continue;
839            }
840            return Err(Error::Corrupt);
841        };
842        let mut remaining = values.as_slice();
843        for name in index.fields {
844            let field = entity
845                .fields
846                .iter()
847                .find(|field| field.name == *name)
848                .ok_or(Error::Corrupt)?;
849            if field.optional {
850                let (&presence, rest) = remaining.split_first().ok_or(Error::Corrupt)?;
851                remaining = rest;
852                match presence {
853                    0 if !index.present_only => continue,
854                    1 => {}
855                    _ => return Err(Error::Corrupt),
856                }
857            }
858            key::consume(&mut remaining, field.value)?;
859        }
860        if !remaining.is_empty() {
861            return Err(Error::Corrupt);
862        }
863        visit(index, values)?;
864    }
865    Ok(())
866}
867
868fn index_entries(entity: &EntitySchema, info: &RowInfo) -> Result<Vec<(StoreKey, bool)>, Error> {
869    let mut entries = Vec::new();
870    visit_index_components(entity, info, |index, values| {
871        let mut key = index_prefix(entity.id, index.id);
872        key.extend_from_slice(values);
873        if !index.unique {
874            info.key.append_to(&mut key);
875        }
876        entries.push((StoreKey::new(key)?, index.unique));
877        Ok(())
878    })?;
879    Ok(entries)
880}
881
882// A visited entry must agree with its owner in namespace, components and suffix.
883// Unrelated entries retain their framing and size checks without building physical keys.
884fn validate_index_entry(
885    entity: &EntitySchema,
886    info: &RowInfo,
887    owner: RowKey,
888    key: &[u8],
889) -> Result<(), Error> {
890    if info.key != owner {
891        return Err(Error::Corrupt);
892    }
893    let (header, payload) = key
894        .split_at_checked(INDEX_PREFIX_BYTES)
895        .ok_or(Error::Corrupt)?;
896    if header[0] != 3 || header[1..5] != entity.id.to_be_bytes() {
897        return Err(Error::Corrupt);
898    }
899    let mut matches = false;
900    let owner = owner.encode();
901    visit_index_components(entity, info, |index, values| {
902        let suffix = if index.unique {
903            &[][..]
904        } else {
905            owner.as_slice()
906        };
907        if INDEX_PREFIX_BYTES + values.len() + suffix.len() > crate::MAX_INDEX_KEY_BYTES {
908            return Err(Error::Limit);
909        }
910        if header[5..] == index.id.to_be_bytes() {
911            matches = payload.strip_prefix(values) == Some(suffix);
912        }
913        Ok(())
914    })?;
915    if !matches {
916        return Err(Error::Corrupt);
917    }
918    Ok(())
919}