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