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    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}
144
145fn live_manifest(schema: [u8; 32], incarnation: [u8; 16]) -> Vec<u8> {
146    let mut bytes = MANIFEST.to_vec();
147    bytes.extend(schema);
148    bytes.extend(incarnation);
149    bytes
150}
151
152/// A bounded synchronous batch; preparation is internal to `Database::commit`.
153#[derive(Default)]
154pub struct Batch {
155    operation_time: Option<crate::Timestamp>,
156    mutations: Vec<Mutation>,
157    bytes: usize,
158}
159struct Mutation {
160    entity: &'static EntitySchema,
161    key: RowKey,
162    kind: Kind,
163}
164enum Kind {
165    Insert(Vec<u8>, RowInfo),
166    // Only maintenance can construct this; ordinary insert policies stay intact.
167    CopyInsert(Vec<u8>, RowInfo, [Option<crate::Timestamp>; 2]),
168    Replace(Vec<u8>, RowInfo),
169    Delete,
170}
171
172impl Batch {
173    /// Begin an empty batch without persistent effects.
174    #[must_use]
175    pub fn new() -> Self {
176        Self::default()
177    }
178
179    /// Begin a batch with one host-captured operation time for all managed fields.
180    /// The database reads no clock; this value remains fixed for the whole batch.
181    #[must_use]
182    pub fn at(time: crate::Timestamp) -> Self {
183        Self {
184            operation_time: Some(time),
185            ..Self::default()
186        }
187    }
188
189    /// Insert a typed record. Primary-key/uniqueness admission happens at commit.
190    /// # Errors
191    /// Refuses managed-field entities (use `insert_input`), encoding or batch capacity.
192    pub fn insert<E: Entity>(&mut self, row: &E) -> Result<(), Error> {
193        if E::SCHEMA.has_managed() {
194            return Err(Error::ManagedField);
195        }
196        self.put(row, Kind::Insert)
197    }
198
199    /// Resolve a typed insert input, append it to this batch and return its full row.
200    /// This is preparation, not a commit; the returned row is not yet persistent.
201    /// Explicit `None` remains absence, while omitted fields select their declared
202    /// literal default or optional absence. No defaults run during replacement.
203    /// # Errors
204    /// Refuses missing required values, field/row bounds or batch capacity.
205    /// A refused input appends no mutation to the batch.
206    pub fn insert_input<I: crate::InsertInput>(&mut self, input: I) -> Result<I::Entity, Error> {
207        let row = input.__into_entity(self.operation_time)?;
208        self.put(&row, Kind::Insert)?;
209        Ok(row)
210    }
211
212    /// Replace an existing typed record, retaining its primary key.
213    /// Managed fields must echo the current stored values; commit sets update time
214    /// only on a real change. Read the row after commit to obtain that assigned time.
215    /// # Errors
216    /// Refuses missing operation time, encoding or batch capacity before mutation.
217    pub fn replace<E: Entity>(&mut self, row: &E) -> Result<(), Error> {
218        self.put(row, Kind::Replace)
219    }
220
221    /// Delete an existing primary key; no recursive cascades are implied.
222    /// # Errors
223    /// Refuses batch capacity before persistent mutation.
224    pub fn delete<E: Entity>(&mut self, key: E::Key) -> Result<(), Error> {
225        self.push(
226            Mutation {
227                entity: E::SCHEMA,
228                key: key.into_row_key(),
229                kind: Kind::Delete,
230            },
231            0,
232        )
233    }
234
235    fn put<E: Entity>(
236        &mut self,
237        row: &E,
238        kind: impl FnOnce(Vec<u8>, RowInfo) -> Kind,
239    ) -> Result<(), Error> {
240        let bytes = row.encode()?;
241        if bytes.len() > crate::__private::MAX_ROW_BYTES {
242            return Err(Error::Limit);
243        }
244        // encode() admitted field/row bounds. Keys come from that same typed
245        // value; decoding freshly encoded bytes would duplicate codec work.
246        let info = row.__row_info();
247        let key = info.key;
248        let len = bytes.len();
249        let kind = kind(bytes, info);
250        if E::SCHEMA.has_managed()
251            && self.operation_time.is_none()
252            && !matches!(kind, Kind::CopyInsert(..))
253        {
254            return Err(Error::MissingOperationTime);
255        }
256        self.push(
257            Mutation {
258                entity: E::SCHEMA,
259                key,
260                kind,
261            },
262            len,
263        )
264    }
265
266    fn push(&mut self, mutation: Mutation, bytes: usize) -> Result<(), Error> {
267        if self.mutations.len() == MAX_BATCH || bytes > MAX_BATCH_BYTES - self.bytes {
268            return Err(Error::Limit);
269        }
270        self.bytes += bytes;
271        self.mutations.push(mutation);
272        Ok(())
273    }
274}
275
276/// A page with explicit progress; a full page may require an empty final call.
277pub struct Page<E: Entity> {
278    /// Typed records from this bounded primary-key traversal.
279    pub rows: Vec<E>,
280    /// Last processed key, when further traversal may remain.
281    pub next_after: Option<E::Key>,
282}
283
284/// Admitted database owning the supplier's exclusive collection lease.
285pub struct Database<M: Memory> {
286    map: Map<M>,
287    schema: Schema,
288    incarnation: [u8; 16],
289}
290
291impl<M: Memory> Database<M> {
292    /// Create in a proven empty governed allocation. Never resets existing data.
293    /// # Errors
294    /// Refuses an all-zero incarnation or nonempty/unsupported supplier allocation.
295    /// # Panics
296    /// Supplier failures after initialization starts trap the enclosing IC message.
297    pub fn create(
298        memory: RuntimeMemory<M>,
299        schema: Schema,
300        incarnation: [u8; 16],
301    ) -> Result<Self, Error> {
302        if incarnation == [0; 16] {
303            return Err(Error::InvalidSchema);
304        }
305        if memory.size() != 0 {
306            return Err(Error::Exists);
307        }
308        let mut map = Map::create(memory);
309        map.insert(
310            manifest_key(),
311            live_manifest(schema.fingerprint, incarnation),
312        );
313        for entity in &schema.entities {
314            map.insert(entity_state_key(entity.id), EntityState::default().encode());
315        }
316        Ok(Self {
317            map,
318            schema,
319            incarnation,
320        })
321    }
322
323    /// Open only an exact manifest/compiled-contract match, without mutation.
324    /// This is not a whole-database integrity scan. Entity metadata is checked
325    /// when read explicitly or when preparing a write to that entity.
326    /// # Errors
327    /// Refuses active maintenance, missing/corrupt manifests, foreign contracts or supplier formats.
328    /// # Panics
329    /// Supplier corruption, including overlong stored keys, traps without repair.
330    pub fn open(memory: RuntimeMemory<M>, schema: Schema) -> Result<Self, Error> {
331        if memory.size() == 0 {
332            return Err(Error::Corrupt);
333        }
334        let map = Map::load(memory);
335        let manifest = map.get(&manifest_key()).ok_or(Error::Corrupt)?;
336        if maintenance::admits_gate(&manifest)? {
337            return Err(Error::Maintenance);
338        }
339        if manifest.len() != 56 {
340            return Err(Error::Corrupt);
341        }
342        if &manifest[..8] != MANIFEST || manifest[8..40] != schema.fingerprint {
343            return Err(Error::IncompatibleSchema);
344        }
345        let incarnation = manifest[40..].try_into().map_err(|_| Error::Corrupt)?;
346        if incarnation == [0; 16] {
347            return Err(Error::Corrupt);
348        }
349        Ok(Self {
350            map,
351            schema,
352            incarnation,
353        })
354    }
355
356    /// Borrow the admitted executable description for inspection.
357    #[must_use]
358    pub const fn schema(&self) -> &Schema {
359        &self.schema
360    }
361
362    /// Durable database identity, distinct from schema identity.
363    #[must_use]
364    pub const fn incarnation(&self) -> [u8; 16] {
365        self.incarnation
366    }
367
368    /// Read the atomic revision of one admitted entity.
369    /// # Errors
370    /// Refuses unknown entities and malformed revision metadata.
371    pub fn revision<E: Entity>(&self) -> Result<u64, Error> {
372        let entity = self.schema.admits(E::SCHEMA)?;
373        read_revision(&self.map, entity.id)
374    }
375
376    /// Read the exact maintained whole-entity row count without scanning rows.
377    /// This trusts atomic entity metadata; it does not validate row/index integrity.
378    /// Filtered counts and row-validating enumeration use the fluent query API.
379    /// # Errors
380    /// Refuses unadmitted entities and missing or malformed entity metadata.
381    /// # Panics
382    /// Supplier corruption may trap; this operation never repairs storage.
383    pub fn cardinality<E: Entity>(&self) -> Result<u64, Error> {
384        let entity = self.schema.admits(E::SCHEMA)?;
385        Ok(read_entity_state(&self.map, entity.id)?.count)
386    }
387
388    /// Inspect the maintained whole-entity count by exact admitted schema name.
389    /// Like [`Self::cardinality`], this reads metadata without validating rows or indexes.
390    /// # Errors
391    /// Refuses unknown names and missing or malformed entity metadata.
392    /// # Panics
393    /// Supplier corruption may trap; this operation never repairs storage.
394    pub fn cardinality_by_name(&self, name: &str) -> Result<u64, Error> {
395        let entity = self
396            .schema
397            .entities
398            .iter()
399            .find(|entity| entity.name == name)
400            .ok_or(Error::UnknownEntity)?;
401        Ok(read_entity_state(&self.map, entity.id)?.count)
402    }
403
404    fn revision_by_id(&self, entity: u32) -> Result<u64, Error> {
405        if !self.schema.entities.iter().any(|value| value.id == entity) {
406            return Err(Error::UnknownEntity);
407        }
408        read_revision(&self.map, entity)
409    }
410
411    /// Read a typed primary key without planning a scan.
412    /// # Errors
413    /// Refuses unadmitted types or malformed rows.
414    #[inline]
415    pub fn get<E: Entity>(&self, key: E::Key) -> Result<Option<E>, Error> {
416        let entity = self.schema.admits(E::SCHEMA)?;
417        self.get_typed::<E>(entity, key)
418    }
419
420    // Keep traversal separate from the static type's admission call. Passing
421    // its admitted descriptor lets compatible typed readers share machine code.
422    #[inline(never)]
423    fn get_typed<E: Entity>(&self, entity: &EntitySchema, key: E::Key) -> Result<Option<E>, Error> {
424        self.map
425            .get(&row_key(entity.id, key.into_row_key()))
426            .map(|bytes| {
427                let row = E::decode(&bytes)?;
428                if row.key() != key {
429                    return Err(Error::Corrupt);
430                }
431                Ok(row)
432            })
433            .transpose()
434    }
435
436    /// Read at most 32 rows in primary-key order; continuation is live, not a snapshot.
437    /// # Errors
438    /// Refuses zero/oversized limits, unadmitted types or corrupt rows.
439    /// # Panics
440    /// Supplier corruption, including overlong stored keys, traps without repair.
441    #[inline]
442    pub fn page<E: Entity>(&self, after: Option<E::Key>, limit: usize) -> Result<Page<E>, Error> {
443        let entity = self.schema.admits(E::SCHEMA)?;
444        self.page_typed::<E>(entity, after, limit)
445    }
446
447    #[inline(never)]
448    fn page_typed<E: Entity>(
449        &self,
450        entity: &EntitySchema,
451        after: Option<E::Key>,
452        limit: usize,
453    ) -> Result<Page<E>, Error> {
454        if !(1..=32).contains(&limit) {
455            return Err(Error::Limit);
456        }
457        let prefix = prefix(2, entity.id);
458        let start = after.map_or_else(
459            || StoreKey::new(prefix.clone()).expect("row namespace fits"),
460            |key| row_key(entity.id, key.into_row_key()),
461        );
462        let lower = if after.is_some() {
463            std::ops::Bound::Excluded(start)
464        } else {
465            std::ops::Bound::Included(start)
466        };
467        let mut entries = self.map.range((lower, std::ops::Bound::Unbounded));
468        let key_type = entity.key_type()?;
469        let mut rows = Vec::new();
470        let mut last = None;
471        for _ in 0..limit {
472            let Some((id, bytes)) = next_primary(&mut entries, &prefix, key_type)? else {
473                break;
474            };
475            let id = E::Key::from_row_key(id)?;
476            let row = E::decode(&bytes)?;
477            if row.key() != id {
478                return Err(Error::Corrupt);
479            }
480            rows.push(row);
481            last = Some(id);
482        }
483        Ok(Page {
484            next_after: if rows.len() == limit { last } else { None },
485            rows,
486        })
487    }
488
489    /// Read the first bounded collection under an exact, nonempty leading index prefix.
490    /// Exact operands obey field bounds and the 512-byte complete-key budget.
491    /// Use `IndexValue::Absent` for an absent optional component. A present-only
492    /// unique index refuses absent operands because it does not enumerate those rows.
493    /// # Errors
494    /// Refuses unknown indexes, mismatched operand types, invalid prefix/limit or
495    /// inconsistent index entries. This method does not yet return continuation.
496    #[inline]
497    pub fn index_prefix<E: Entity>(
498        &self,
499        index: &str,
500        values: &[IndexValue<'_>],
501        limit: usize,
502    ) -> Result<Vec<E>, Error> {
503        let entity = self.schema.admits(E::SCHEMA)?;
504        self.index_prefix_typed::<E>(entity, index, values, limit)
505    }
506
507    #[inline(never)]
508    fn index_prefix_typed<E: Entity>(
509        &self,
510        entity: &EntitySchema,
511        index: &str,
512        values: &[IndexValue<'_>],
513        limit: usize,
514    ) -> Result<Vec<E>, Error> {
515        let prefix = index_prefix_key(entity, index, values, limit)?;
516        let mut rows = Vec::new();
517        let mut entries = self.map.range(prefix.clone()..);
518        let key_type = entity.key_type()?;
519        for _ in 0..limit {
520            let Some((key, id, bytes)) =
521                next_index(&self.map, &mut entries, &prefix, entity.id, key_type)?
522            else {
523                break;
524            };
525            let row = E::decode(&bytes)?;
526            validate_index_entry(entity, &row.__row_info(), id, &key)?;
527            rows.push(row);
528        }
529        Ok(rows)
530    }
531
532    /// Prepare final state, then synchronously apply rows, indexes, revisions and counts.
533    /// A normal refusal occurs before persistent writes. Success is not a separate
534    /// durability point from the surrounding IC message. Empty/no-op batches preserve revisions.
535    /// # Errors
536    /// Refuses missing/existing rows, duplicate targets, uniqueness/reference violations,
537    /// corruption or limits. References use the intended final batch state.
538    /// # Panics
539    /// Supplier failures after the first mutation trap; never catch and continue an IC commit.
540    pub fn commit(&mut self, batch: Batch) -> Result<(), Error> {
541        let mut targets = BTreeSet::new();
542        let mut removes = BTreeSet::new();
543        let mut writes = BTreeMap::new();
544        let mut unique = BTreeSet::new();
545        // Observe each entity once, then apply its final net row delta. A balanced
546        // delete/insert batch must not depend on mutation order. No state survives calls.
547        let mut entities = BTreeMap::new();
548        let mut required = BTreeSet::new();
549        let mut deleted = Vec::new();
550        for mut mutation in batch.mutations {
551            self.schema.admits(mutation.entity)?;
552            let key = row_key(mutation.entity.id, mutation.key);
553            if !targets.insert(key.clone()) {
554                return Err(Error::DuplicateTarget);
555            }
556            let old = self.map.get(&key);
557            match (&mutation.kind, &old) {
558                (Kind::Insert(..) | Kind::CopyInsert(..), Some(_)) => return Err(Error::Exists),
559                (Kind::Replace(..) | Kind::Delete, None) => return Err(Error::Missing),
560                _ => {}
561            }
562            if mutation.entity.has_managed() {
563                match &mut mutation.kind {
564                    Kind::Insert(bytes, _) => crate::managed::validate_insert(
565                        mutation.entity,
566                        bytes,
567                        batch.operation_time.ok_or(Error::MissingOperationTime)?,
568                    )?,
569                    Kind::Replace(bytes, info) => {
570                        if crate::managed::replace(
571                            mutation.entity,
572                            bytes,
573                            old.as_deref().ok_or(Error::Missing)?,
574                            batch.operation_time.ok_or(Error::MissingOperationTime)?,
575                        )? {
576                            *info = mutation.entity.inspect_row(bytes)?;
577                        }
578                    }
579                    Kind::CopyInsert(bytes, _, expected) => {
580                        if crate::managed::values(mutation.entity, bytes)? != *expected {
581                            return Err(Error::ManagedField);
582                        }
583                    }
584                    Kind::Delete => {}
585                }
586            }
587            // Admit complete after-image keys even when the row is a no-op.
588            // Retain these buffers for publication instead of encoding twice.
589            let mut after_indexes = match &mutation.kind {
590                Kind::Insert(_, info) | Kind::CopyInsert(_, info, _) | Kind::Replace(_, info) => {
591                    index_entries(mutation.entity, info)?
592                }
593                Kind::Delete => Vec::new(),
594            };
595            let (_, changed, delta) = match entities.entry(mutation.entity.id) {
596                std::collections::btree_map::Entry::Occupied(entry) => entry.into_mut(),
597                std::collections::btree_map::Entry::Vacant(entry) => entry.insert((
598                    read_entity_state(&self.map, mutation.entity.id)?,
599                    false,
600                    0_i64,
601                )),
602            };
603            if let (Kind::Replace(bytes, _), Some(old)) = (&mutation.kind, &old)
604                && bytes == old
605            {
606                continue;
607            }
608            if let Some(old) = old {
609                let info = mutation.entity.inspect_row(&old)?;
610                if info.key != mutation.key {
611                    return Err(Error::Corrupt);
612                }
613                let owner = info.key.encode();
614                for (key, _) in index_entries(mutation.entity, &info)? {
615                    if self.map.get(&key).as_deref() != Some(owner.as_slice()) {
616                        return Err(Error::Corrupt);
617                    }
618                    // Same physical key and owner: leave the verified entry in place.
619                    // Its unique value remains occupied during final-state admission.
620                    if let Some(position) =
621                        after_indexes.iter().position(|(after, _)| *after == key)
622                    {
623                        after_indexes.remove(position);
624                    } else {
625                        removes.insert(key);
626                    }
627                }
628            }
629            *changed = true;
630            *delta += match &mutation.kind {
631                Kind::Insert(..) | Kind::CopyInsert(..) => 1,
632                Kind::Delete => -1,
633                Kind::Replace(..) => 0,
634            };
635            // Private migration inserts may precede their targets. The frozen
636            // complete target validates references before it can be published.
637            let copy_insert = matches!(&mutation.kind, Kind::CopyInsert(..));
638            match mutation.kind {
639                Kind::Delete => {
640                    deleted.push((mutation.entity.id, mutation.key));
641                    removes.insert(key);
642                }
643                Kind::Insert(bytes, info)
644                | Kind::CopyInsert(bytes, info, _)
645                | Kind::Replace(bytes, info) => {
646                    writes.insert(key, bytes);
647                    for (key, is_unique) in after_indexes {
648                        if is_unique && !unique.insert(key.clone()) {
649                            return Err(Error::UniqueViolation);
650                        }
651                        writes.insert(key, info.key.encode());
652                    }
653                    if !copy_insert {
654                        collect_references(mutation.entity, &info, &mut required)?;
655                    }
656                }
657            }
658        }
659        // Check existing owners only after all releases in this batch are known.
660        for key in unique {
661            if self.map.contains_key(&key) && !removes.contains(&key) {
662                return Err(Error::UniqueViolation);
663            }
664        }
665        self.validate_references(&required, &deleted, &removes, &writes)?;
666        for (entity, (mut state, changed, delta)) in entities {
667            if changed {
668                state.revision = state.revision.checked_add(1).ok_or(Error::Limit)?;
669                state.count = if delta >= 0 {
670                    state.count.checked_add(delta as u64).ok_or(Error::Limit)?
671                } else {
672                    state
673                        .count
674                        .checked_sub((-delta) as u64)
675                        .ok_or(Error::Corrupt)?
676                };
677                writes.insert(entity_state_key(entity), state.encode());
678            }
679        }
680        // Proven IC rollback boundary: no recoverable Result branch below this line.
681        for key in removes {
682            self.map.remove(&key);
683        }
684        for (key, value) in writes {
685            self.map.insert(key, value);
686        }
687        Ok(())
688    }
689
690    // Reuse the prepared final rows and ordinary index changes. No durable
691    // relationship catalog or second mutation executor is involved.
692    fn validate_references(
693        &self,
694        required: &BTreeSet<(u32, RowKey)>,
695        deleted: &[(u32, RowKey)],
696        removes: &BTreeSet<StoreKey>,
697        writes: &BTreeMap<StoreKey, Vec<u8>>,
698    ) -> Result<(), Error> {
699        for &(entity, id) in required {
700            let key = row_key(entity, id);
701            if writes.contains_key(&key) {
702                continue;
703            } // prepared, validated final target
704            if removes.contains(&key) {
705                return Err(Error::ReferenceViolation);
706            }
707            validate_reference_target(&self.map, &self.schema, entity, id)?;
708        }
709        for &(target, id) in deleted {
710            for entity in &self.schema.entities {
711                for field in entity.fields {
712                    let Some(reference) = field.reference.filter(|value| value.entity == target)
713                    else {
714                        continue;
715                    };
716                    let mut prefix = index_prefix(entity.id, reference.index);
717                    id.index_value()
718                        .append_component(field.optional, &mut prefix);
719                    let prefix = StoreKey::new(prefix)?;
720                    // Each skipped entry belongs to a distinct changed row in
721                    // this range. At most MAX_BATCH skips plus one survivor.
722                    for (position, entry) in self
723                        .map
724                        .range(prefix.clone()..)
725                        .take_while(|entry| entry.key().starts_with(&prefix))
726                        .take(MAX_BATCH + 1)
727                        .enumerate()
728                    {
729                        if removes.contains(entry.key()) {
730                            if position == MAX_BATCH {
731                                return Err(Error::Corrupt);
732                            }
733                            continue;
734                        }
735                        let owner = RowKey::decode(&entry.value(), entity.key_type()?)?;
736                        let bytes = self
737                            .map
738                            .get(&row_key(entity.id, owner))
739                            .ok_or(Error::Corrupt)?;
740                        let info = entity.inspect_row(&bytes)?;
741                        validate_index_entry(entity, &info, owner, entry.key())?;
742                        return Err(Error::ReferenceViolation);
743                    }
744                }
745            }
746        }
747        Ok(())
748    }
749}
750
751fn prefix(tag: u8, entity: u32) -> Vec<u8> {
752    let mut key = vec![tag];
753    key.extend(entity.to_be_bytes());
754    key
755}
756
757fn entity_state_key(entity: u32) -> StoreKey {
758    StoreKey::new(prefix(1, entity)).expect("entity state key fits")
759}
760
761fn read_revision<M: Memory>(map: &Map<M>, entity: u32) -> Result<u64, Error> {
762    Ok(read_entity_state(map, entity)?.revision)
763}
764
765/// One atomic metadata record; neither value is reconstructed during ordinary open.
766#[derive(Default)]
767struct EntityState {
768    revision: u64,
769    count: u64,
770}
771impl EntityState {
772    fn encode(&self) -> Vec<u8> {
773        let mut bytes = self.revision.to_le_bytes().to_vec();
774        bytes.extend(self.count.to_le_bytes());
775        bytes
776    }
777}
778fn read_entity_state<M: Memory>(map: &Map<M>, entity: u32) -> Result<EntityState, Error> {
779    let bytes = map.get(&entity_state_key(entity)).ok_or(Error::Corrupt)?;
780    if bytes.len() != 16 {
781        return Err(Error::Corrupt);
782    }
783    Ok(EntityState {
784        revision: u64::from_le_bytes(bytes[..8].try_into().map_err(|_| Error::Corrupt)?),
785        count: u64::from_le_bytes(bytes[8..].try_into().map_err(|_| Error::Corrupt)?),
786    })
787}
788
789fn row_key(entity: u32, id: RowKey) -> StoreKey {
790    let mut key = prefix(2, entity);
791    id.append_to(&mut key);
792    StoreKey::new(key).expect("bounded primary key fits")
793}
794const INDEX_PREFIX_BYTES: usize = 9; // namespace tag, entity handle and index handle
795fn index_prefix(entity: u32, index: u32) -> Vec<u8> {
796    let mut key = prefix(3, entity);
797    key.extend(index.to_be_bytes());
798    key
799}
800// Direct lookups and fluent reads share exact prefix admission and completion bounds.
801fn admit_index_prefix(
802    entity: &EntitySchema,
803    index: &crate::IndexSchema,
804    values: &[IndexValue<'_>],
805) -> Result<Vec<u8>, Error> {
806    if values.len() > index.fields.len() {
807        return Err(Error::Limit);
808    }
809    let mut prefix = index_prefix(entity.id, index.id);
810    for (value, name) in values.iter().zip(index.fields) {
811        let field = entity
812            .fields
813            .iter()
814            .find(|field| field.name == *name)
815            .ok_or(Error::InvalidSchema)?;
816        value.admit(field.value, field.optional)?;
817        if index.present_only && *value == IndexValue::Absent {
818            return Err(Error::InvalidOperand);
819        }
820        value.append_component(field.optional, &mut prefix);
821        if prefix.len() > crate::MAX_INDEX_KEY_BYTES {
822            return Err(Error::Limit);
823        }
824    }
825    let mut completion = if index.unique {
826        0
827    } else {
828        key::minimum_bytes(entity.key_type()?)?
829    };
830    for name in &index.fields[values.len()..] {
831        let field = entity
832            .fields
833            .iter()
834            .find(|field| field.name == *name)
835            .ok_or(Error::InvalidSchema)?;
836        completion += if field.optional && !index.present_only {
837            1
838        } else {
839            key::minimum_bytes(field.value)? + usize::from(field.optional)
840        };
841    }
842    if prefix.len() + completion > crate::MAX_INDEX_KEY_BYTES {
843        return Err(Error::Limit);
844    }
845    Ok(prefix)
846}
847// RowInfo may come from a generated entity or the shared stored-row decoder.
848fn visit_index_components(
849    entity: &EntitySchema,
850    info: &RowInfo,
851    mut visit: impl FnMut(&crate::IndexSchema, &[u8]) -> Result<(), Error>,
852) -> Result<(), Error> {
853    if info.indexes.len() != entity.indexes.len() {
854        return Err(Error::Corrupt);
855    }
856    for (index, values) in entity.indexes.iter().zip(&info.indexes) {
857        let Some(values) = values else {
858            if index.present_only {
859                continue;
860            }
861            return Err(Error::Corrupt);
862        };
863        let mut remaining = values.as_slice();
864        for name in index.fields {
865            let field = entity
866                .fields
867                .iter()
868                .find(|field| field.name == *name)
869                .ok_or(Error::Corrupt)?;
870            if field.optional {
871                let (&presence, rest) = remaining.split_first().ok_or(Error::Corrupt)?;
872                remaining = rest;
873                match presence {
874                    0 if !index.present_only => continue,
875                    1 => {}
876                    _ => return Err(Error::Corrupt),
877                }
878            }
879            key::consume(&mut remaining, field.value)?;
880        }
881        if !remaining.is_empty() {
882            return Err(Error::Corrupt);
883        }
884        visit(index, values)?;
885    }
886    Ok(())
887}
888
889fn index_entries(entity: &EntitySchema, info: &RowInfo) -> Result<Vec<(StoreKey, bool)>, Error> {
890    let mut entries = Vec::new();
891    visit_index_components(entity, info, |index, values| {
892        let mut key = index_prefix(entity.id, index.id);
893        key.extend_from_slice(values);
894        if !index.unique {
895            info.key.append_to(&mut key);
896        }
897        entries.push((StoreKey::new(key)?, index.unique));
898        Ok(())
899    })?;
900    Ok(entries)
901}
902
903// A visited entry must agree with its owner in namespace, components and suffix.
904// Unrelated entries retain their framing and size checks without building physical keys.
905fn validate_index_entry(
906    entity: &EntitySchema,
907    info: &RowInfo,
908    owner: RowKey,
909    key: &[u8],
910) -> Result<(), Error> {
911    if info.key != owner {
912        return Err(Error::Corrupt);
913    }
914    let (header, payload) = key
915        .split_at_checked(INDEX_PREFIX_BYTES)
916        .ok_or(Error::Corrupt)?;
917    if header[0] != 3 || header[1..5] != entity.id.to_be_bytes() {
918        return Err(Error::Corrupt);
919    }
920    let mut matches = false;
921    let owner = owner.encode();
922    visit_index_components(entity, info, |index, values| {
923        let suffix = if index.unique {
924            &[][..]
925        } else {
926            owner.as_slice()
927        };
928        if INDEX_PREFIX_BYTES + values.len() + suffix.len() > crate::MAX_INDEX_KEY_BYTES {
929            return Err(Error::Limit);
930        }
931        if header[5..] == index.id.to_be_bytes() {
932            matches = payload.strip_prefix(values) == Some(suffix);
933        }
934        Ok(())
935    })?;
936    if !matches {
937        return Err(Error::Corrupt);
938    }
939    Ok(())
940}