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    /// Read up to 32 primary keys, returning one slot per input position.
421    /// Missing keys yield `None`; repeated keys repeat the row at each position.
422    /// # Errors
423    /// Returns `Limit` for oversized input, or the same errors as [`Self::get`].
424    pub fn get_many<E: Entity>(&self, keys: &[E::Key]) -> Result<Vec<Option<E>>, Error> {
425        if keys.len() > 32 {
426            return Err(Error::Limit);
427        }
428        let entity = self.schema.admits(E::SCHEMA)?;
429        keys.iter()
430            .map(|&key| self.get_typed::<E>(entity, key))
431            .collect()
432    }
433
434    // Keep traversal separate from the static type's admission call. Passing
435    // its admitted descriptor lets compatible typed readers share machine code.
436    #[inline(never)]
437    fn get_typed<E: Entity>(&self, entity: &EntitySchema, key: E::Key) -> Result<Option<E>, Error> {
438        self.map
439            .get(&row_key(entity.id, key.into_row_key()))
440            .map(|bytes| {
441                let row = E::decode(&bytes)?;
442                if row.key() != key {
443                    return Err(Error::Corrupt);
444                }
445                Ok(row)
446            })
447            .transpose()
448    }
449
450    /// Read at most 32 rows in primary-key order; continuation is live, not a snapshot.
451    /// # Errors
452    /// Refuses zero/oversized limits, unadmitted types or corrupt rows.
453    /// # Panics
454    /// Supplier corruption, including overlong stored keys, traps without repair.
455    #[inline]
456    pub fn page<E: Entity>(&self, after: Option<E::Key>, limit: usize) -> Result<Page<E>, Error> {
457        let entity = self.schema.admits(E::SCHEMA)?;
458        self.page_typed::<E>(entity, after, limit)
459    }
460
461    #[inline(never)]
462    fn page_typed<E: Entity>(
463        &self,
464        entity: &EntitySchema,
465        after: Option<E::Key>,
466        limit: usize,
467    ) -> Result<Page<E>, Error> {
468        if !(1..=32).contains(&limit) {
469            return Err(Error::Limit);
470        }
471        let prefix = prefix(2, entity.id);
472        let start = after.map_or_else(
473            || StoreKey::new(prefix.clone()).expect("row namespace fits"),
474            |key| row_key(entity.id, key.into_row_key()),
475        );
476        let lower = if after.is_some() {
477            std::ops::Bound::Excluded(start)
478        } else {
479            std::ops::Bound::Included(start)
480        };
481        let mut entries = self.map.range((lower, std::ops::Bound::Unbounded));
482        let key_type = entity.key_type()?;
483        let mut rows = Vec::new();
484        let mut last = None;
485        for _ in 0..limit {
486            let Some((id, bytes)) = next_primary(&mut entries, &prefix, key_type)? else {
487                break;
488            };
489            let id = E::Key::from_row_key(id)?;
490            let row = E::decode(&bytes)?;
491            if row.key() != id {
492                return Err(Error::Corrupt);
493            }
494            rows.push(row);
495            last = Some(id);
496        }
497        Ok(Page {
498            next_after: if rows.len() == limit { last } else { None },
499            rows,
500        })
501    }
502
503    /// Read the first bounded collection under an exact, nonempty leading index prefix.
504    /// Exact operands obey field bounds and the 512-byte complete-key budget.
505    /// Use `IndexValue::Absent` for an absent optional component. A present-only
506    /// unique index refuses absent operands because it does not enumerate those rows.
507    /// # Errors
508    /// Refuses unknown indexes, mismatched operand types, invalid prefix/limit or
509    /// inconsistent index entries. This method does not yet return continuation.
510    #[inline]
511    pub fn index_prefix<E: Entity>(
512        &self,
513        index: &str,
514        values: &[IndexValue<'_>],
515        limit: usize,
516    ) -> Result<Vec<E>, Error> {
517        let entity = self.schema.admits(E::SCHEMA)?;
518        self.index_prefix_typed::<E>(entity, index, values, limit)
519    }
520
521    #[inline(never)]
522    fn index_prefix_typed<E: Entity>(
523        &self,
524        entity: &EntitySchema,
525        index: &str,
526        values: &[IndexValue<'_>],
527        limit: usize,
528    ) -> Result<Vec<E>, Error> {
529        let prefix = index_prefix_key(entity, index, values, limit)?;
530        let mut rows = Vec::new();
531        let mut entries = self.map.range(prefix.clone()..);
532        let key_type = entity.key_type()?;
533        for _ in 0..limit {
534            let Some((key, id, bytes)) =
535                next_index(&self.map, &mut entries, &prefix, entity.id, key_type)?
536            else {
537                break;
538            };
539            let row = E::decode(&bytes)?;
540            validate_index_entry(entity, &row.__row_info(), id, &key)?;
541            rows.push(row);
542        }
543        Ok(rows)
544    }
545
546    /// Prepare final state, then synchronously apply rows, indexes, revisions and counts.
547    /// A normal refusal occurs before persistent writes. Success is not a separate
548    /// durability point from the surrounding IC message. Empty/no-op batches preserve revisions.
549    /// # Errors
550    /// Refuses missing/existing rows, duplicate targets, uniqueness/reference violations,
551    /// corruption or limits. References use the intended final batch state.
552    /// # Panics
553    /// Supplier failures after the first mutation trap; never catch and continue an IC commit.
554    pub fn commit(&mut self, batch: Batch) -> Result<(), Error> {
555        let mut targets = BTreeSet::new();
556        let mut removes = BTreeSet::new();
557        let mut writes = BTreeMap::new();
558        let mut unique = BTreeSet::new();
559        // Observe each entity once, then apply its final net row delta. A balanced
560        // delete/insert batch must not depend on mutation order. No state survives calls.
561        let mut entities = BTreeMap::new();
562        let mut required = BTreeSet::new();
563        let mut deleted = Vec::new();
564        for mut mutation in batch.mutations {
565            self.schema.admits(mutation.entity)?;
566            let key = row_key(mutation.entity.id, mutation.key);
567            if !targets.insert(key.clone()) {
568                return Err(Error::DuplicateTarget);
569            }
570            let old = self.map.get(&key);
571            match (&mutation.kind, &old) {
572                (Kind::Insert(..) | Kind::CopyInsert(..), Some(_)) => return Err(Error::Exists),
573                (Kind::Replace(..) | Kind::Delete, None) => return Err(Error::Missing),
574                _ => {}
575            }
576            if mutation.entity.has_managed() {
577                match &mut mutation.kind {
578                    Kind::Insert(bytes, _) => crate::managed::validate_insert(
579                        mutation.entity,
580                        bytes,
581                        batch.operation_time.ok_or(Error::MissingOperationTime)?,
582                    )?,
583                    Kind::Replace(bytes, info) => {
584                        if crate::managed::replace(
585                            mutation.entity,
586                            bytes,
587                            old.as_deref().ok_or(Error::Missing)?,
588                            batch.operation_time.ok_or(Error::MissingOperationTime)?,
589                        )? {
590                            *info = mutation.entity.inspect_row(bytes)?;
591                        }
592                    }
593                    Kind::CopyInsert(bytes, _, expected) => {
594                        if crate::managed::values(mutation.entity, bytes)? != *expected {
595                            return Err(Error::ManagedField);
596                        }
597                    }
598                    Kind::Delete => {}
599                }
600            }
601            // Admit complete after-image keys even when the row is a no-op.
602            // Retain these buffers for publication instead of encoding twice.
603            let mut after_indexes = match &mutation.kind {
604                Kind::Insert(_, info) | Kind::CopyInsert(_, info, _) | Kind::Replace(_, info) => {
605                    index_entries(mutation.entity, info)?
606                }
607                Kind::Delete => Vec::new(),
608            };
609            let (_, changed, delta) = match entities.entry(mutation.entity.id) {
610                std::collections::btree_map::Entry::Occupied(entry) => entry.into_mut(),
611                std::collections::btree_map::Entry::Vacant(entry) => entry.insert((
612                    read_entity_state(&self.map, mutation.entity.id)?,
613                    false,
614                    0_i64,
615                )),
616            };
617            if let (Kind::Replace(bytes, _), Some(old)) = (&mutation.kind, &old)
618                && bytes == old
619            {
620                continue;
621            }
622            if let Some(old) = old {
623                let info = mutation.entity.inspect_row(&old)?;
624                if info.key != mutation.key {
625                    return Err(Error::Corrupt);
626                }
627                let owner = info.key.encode();
628                for (key, _) in index_entries(mutation.entity, &info)? {
629                    if self.map.get(&key).as_deref() != Some(owner.as_slice()) {
630                        return Err(Error::Corrupt);
631                    }
632                    // Same physical key and owner: leave the verified entry in place.
633                    // Its unique value remains occupied during final-state admission.
634                    if let Some(position) =
635                        after_indexes.iter().position(|(after, _)| *after == key)
636                    {
637                        after_indexes.remove(position);
638                    } else {
639                        removes.insert(key);
640                    }
641                }
642            }
643            *changed = true;
644            *delta += match &mutation.kind {
645                Kind::Insert(..) | Kind::CopyInsert(..) => 1,
646                Kind::Delete => -1,
647                Kind::Replace(..) => 0,
648            };
649            // Private migration inserts may precede their targets. The frozen
650            // complete target validates references before it can be published.
651            let copy_insert = matches!(&mutation.kind, Kind::CopyInsert(..));
652            match mutation.kind {
653                Kind::Delete => {
654                    deleted.push((mutation.entity.id, mutation.key));
655                    removes.insert(key);
656                }
657                Kind::Insert(bytes, info)
658                | Kind::CopyInsert(bytes, info, _)
659                | Kind::Replace(bytes, info) => {
660                    writes.insert(key, bytes);
661                    for (key, is_unique) in after_indexes {
662                        if is_unique && !unique.insert(key.clone()) {
663                            return Err(Error::UniqueViolation);
664                        }
665                        writes.insert(key, info.key.encode());
666                    }
667                    if !copy_insert {
668                        collect_references(mutation.entity, &info, &mut required)?;
669                    }
670                }
671            }
672        }
673        // Check existing owners only after all releases in this batch are known.
674        for key in unique {
675            if self.map.contains_key(&key) && !removes.contains(&key) {
676                return Err(Error::UniqueViolation);
677            }
678        }
679        self.validate_references(&required, &deleted, &removes, &writes)?;
680        for (entity, (mut state, changed, delta)) in entities {
681            if changed {
682                state.revision = state.revision.checked_add(1).ok_or(Error::Limit)?;
683                state.count = if delta >= 0 {
684                    state.count.checked_add(delta as u64).ok_or(Error::Limit)?
685                } else {
686                    state
687                        .count
688                        .checked_sub((-delta) as u64)
689                        .ok_or(Error::Corrupt)?
690                };
691                writes.insert(entity_state_key(entity), state.encode());
692            }
693        }
694        // Proven IC rollback boundary: no recoverable Result branch below this line.
695        for key in removes {
696            self.map.remove(&key);
697        }
698        for (key, value) in writes {
699            self.map.insert(key, value);
700        }
701        Ok(())
702    }
703
704    // Reuse the prepared final rows and ordinary index changes. No durable
705    // relationship catalog or second mutation executor is involved.
706    fn validate_references(
707        &self,
708        required: &BTreeSet<(u32, RowKey)>,
709        deleted: &[(u32, RowKey)],
710        removes: &BTreeSet<StoreKey>,
711        writes: &BTreeMap<StoreKey, Vec<u8>>,
712    ) -> Result<(), Error> {
713        for &(entity, id) in required {
714            let key = row_key(entity, id);
715            if writes.contains_key(&key) {
716                continue;
717            } // prepared, validated final target
718            if removes.contains(&key) {
719                return Err(Error::ReferenceViolation);
720            }
721            validate_reference_target(&self.map, &self.schema, entity, id)?;
722        }
723        for &(target, id) in deleted {
724            for entity in &self.schema.entities {
725                for field in entity.fields {
726                    let Some(reference) = field.reference.filter(|value| value.entity == target)
727                    else {
728                        continue;
729                    };
730                    let mut prefix = index_prefix(entity.id, reference.index);
731                    id.index_value()
732                        .append_component(field.optional, &mut prefix);
733                    let prefix = StoreKey::new(prefix)?;
734                    // Each skipped entry belongs to a distinct changed row in
735                    // this range. At most MAX_BATCH skips plus one survivor.
736                    for (position, entry) in self
737                        .map
738                        .range(prefix.clone()..)
739                        .take_while(|entry| entry.key().starts_with(&prefix))
740                        .take(MAX_BATCH + 1)
741                        .enumerate()
742                    {
743                        if removes.contains(entry.key()) {
744                            if position == MAX_BATCH {
745                                return Err(Error::Corrupt);
746                            }
747                            continue;
748                        }
749                        let owner = RowKey::decode(&entry.value(), entity.key_type()?)?;
750                        let bytes = self
751                            .map
752                            .get(&row_key(entity.id, owner))
753                            .ok_or(Error::Corrupt)?;
754                        let info = entity.inspect_row(&bytes)?;
755                        validate_index_entry(entity, &info, owner, entry.key())?;
756                        return Err(Error::ReferenceViolation);
757                    }
758                }
759            }
760        }
761        Ok(())
762    }
763}
764
765fn prefix(tag: u8, entity: u32) -> Vec<u8> {
766    let mut key = vec![tag];
767    key.extend(entity.to_be_bytes());
768    key
769}
770
771fn entity_state_key(entity: u32) -> StoreKey {
772    StoreKey::new(prefix(1, entity)).expect("entity state key fits")
773}
774
775fn read_revision<M: Memory>(map: &Map<M>, entity: u32) -> Result<u64, Error> {
776    Ok(read_entity_state(map, entity)?.revision)
777}
778
779/// One atomic metadata record; neither value is reconstructed during ordinary open.
780#[derive(Default)]
781struct EntityState {
782    revision: u64,
783    count: u64,
784}
785impl EntityState {
786    fn encode(&self) -> Vec<u8> {
787        let mut bytes = self.revision.to_le_bytes().to_vec();
788        bytes.extend(self.count.to_le_bytes());
789        bytes
790    }
791}
792fn read_entity_state<M: Memory>(map: &Map<M>, entity: u32) -> Result<EntityState, Error> {
793    let bytes = map.get(&entity_state_key(entity)).ok_or(Error::Corrupt)?;
794    if bytes.len() != 16 {
795        return Err(Error::Corrupt);
796    }
797    Ok(EntityState {
798        revision: u64::from_le_bytes(bytes[..8].try_into().map_err(|_| Error::Corrupt)?),
799        count: u64::from_le_bytes(bytes[8..].try_into().map_err(|_| Error::Corrupt)?),
800    })
801}
802
803fn row_key(entity: u32, id: RowKey) -> StoreKey {
804    let mut key = prefix(2, entity);
805    id.append_to(&mut key);
806    StoreKey::new(key).expect("bounded primary key fits")
807}
808const INDEX_PREFIX_BYTES: usize = 9; // namespace tag, entity handle and index handle
809fn index_prefix(entity: u32, index: u32) -> Vec<u8> {
810    let mut key = prefix(3, entity);
811    key.extend(index.to_be_bytes());
812    key
813}
814// Direct lookups and fluent reads share exact prefix admission and completion bounds.
815fn admit_index_prefix(
816    entity: &EntitySchema,
817    index: &crate::IndexSchema,
818    values: &[IndexValue<'_>],
819) -> Result<Vec<u8>, Error> {
820    if values.len() > index.fields.len() {
821        return Err(Error::Limit);
822    }
823    let mut prefix = index_prefix(entity.id, index.id);
824    for (value, name) in values.iter().zip(index.fields) {
825        let field = entity
826            .fields
827            .iter()
828            .find(|field| field.name == *name)
829            .ok_or(Error::InvalidSchema)?;
830        value.admit(field.value, field.optional)?;
831        if index.present_only && *value == IndexValue::Absent {
832            return Err(Error::InvalidOperand);
833        }
834        value.append_component(field.optional, &mut prefix);
835        if prefix.len() > crate::MAX_INDEX_KEY_BYTES {
836            return Err(Error::Limit);
837        }
838    }
839    let mut completion = if index.unique {
840        0
841    } else {
842        key::minimum_bytes(entity.key_type()?)?
843    };
844    for name in &index.fields[values.len()..] {
845        let field = entity
846            .fields
847            .iter()
848            .find(|field| field.name == *name)
849            .ok_or(Error::InvalidSchema)?;
850        completion += if field.optional && !index.present_only {
851            1
852        } else {
853            key::minimum_bytes(field.value)? + usize::from(field.optional)
854        };
855    }
856    if prefix.len() + completion > crate::MAX_INDEX_KEY_BYTES {
857        return Err(Error::Limit);
858    }
859    Ok(prefix)
860}
861// RowInfo may come from a generated entity or the shared stored-row decoder.
862fn visit_index_components(
863    entity: &EntitySchema,
864    info: &RowInfo,
865    mut visit: impl FnMut(&crate::IndexSchema, &[u8]) -> Result<(), Error>,
866) -> Result<(), Error> {
867    if info.indexes.len() != entity.indexes.len() {
868        return Err(Error::Corrupt);
869    }
870    for (index, values) in entity.indexes.iter().zip(&info.indexes) {
871        let Some(values) = values else {
872            if index.present_only {
873                continue;
874            }
875            return Err(Error::Corrupt);
876        };
877        let mut remaining = values.as_slice();
878        for name in index.fields {
879            let field = entity
880                .fields
881                .iter()
882                .find(|field| field.name == *name)
883                .ok_or(Error::Corrupt)?;
884            if field.optional {
885                let (&presence, rest) = remaining.split_first().ok_or(Error::Corrupt)?;
886                remaining = rest;
887                match presence {
888                    0 if !index.present_only => continue,
889                    1 => {}
890                    _ => return Err(Error::Corrupt),
891                }
892            }
893            key::consume(&mut remaining, field.value)?;
894        }
895        if !remaining.is_empty() {
896            return Err(Error::Corrupt);
897        }
898        visit(index, values)?;
899    }
900    Ok(())
901}
902
903fn index_entries(entity: &EntitySchema, info: &RowInfo) -> Result<Vec<(StoreKey, bool)>, Error> {
904    let mut entries = Vec::new();
905    visit_index_components(entity, info, |index, values| {
906        let mut key = index_prefix(entity.id, index.id);
907        key.extend_from_slice(values);
908        if !index.unique {
909            info.key.append_to(&mut key);
910        }
911        entries.push((StoreKey::new(key)?, index.unique));
912        Ok(())
913    })?;
914    Ok(entries)
915}
916
917// A visited entry must agree with its owner in namespace, components and suffix.
918// Unrelated entries retain their framing and size checks without building physical keys.
919fn validate_index_entry(
920    entity: &EntitySchema,
921    info: &RowInfo,
922    owner: RowKey,
923    key: &[u8],
924) -> Result<(), Error> {
925    if info.key != owner {
926        return Err(Error::Corrupt);
927    }
928    let (header, payload) = key
929        .split_at_checked(INDEX_PREFIX_BYTES)
930        .ok_or(Error::Corrupt)?;
931    if header[0] != 3 || header[1..5] != entity.id.to_be_bytes() {
932        return Err(Error::Corrupt);
933    }
934    let mut matches = false;
935    let owner = owner.encode();
936    visit_index_components(entity, info, |index, values| {
937        let suffix = if index.unique {
938            &[][..]
939        } else {
940            owner.as_slice()
941        };
942        if INDEX_PREFIX_BYTES + values.len() + suffix.len() > crate::MAX_INDEX_KEY_BYTES {
943            return Err(Error::Limit);
944        }
945        if header[5..] == index.id.to_be_bytes() {
946            matches = payload.strip_prefix(values) == Some(suffix);
947        }
948        Ok(())
949    })?;
950    if !matches {
951        return Err(Error::Corrupt);
952    }
953    Ok(())
954}