Skip to main content

dogwood_local_engine/
lib.rs

1#![doc = include_str!("../README.md")]
2
3mod clock;
4mod codec;
5mod durable;
6#[cfg(feature = "fault-injection")]
7#[doc(hidden)]
8pub mod fault_injection;
9mod identity;
10mod incremental;
11pub mod log;
12mod partition;
13mod policy_store;
14mod record;
15mod rel;
16mod rows;
17mod shard;
18mod shared;
19mod snapshot;
20mod sync;
21mod tick;
22
23pub use codec::{event_from_json, event_to_json};
24pub use identity::leaf_key;
25pub use log::{DurableLog, LogError, Pruned, Snapshot, Write};
26pub use tick::TickRate;
27
28// The durable-engine assembly: the crash-consistent, event-sourced decision
29// service layered over `DurableLog` + `LocalTemporalEngine`.
30pub use clock::{Clock, WallClock};
31pub use durable::{
32    Applied, BatchResult, DecisionDiagnostics, DecisionResponse, Durability, DurableConfig,
33    DurableError, DurableTemporalEngine, Installed, Outcome, PolicyAttribution, Status, Submitted,
34};
35pub use policy_store::{BatchError, PolicyEntry, PolicyId, PolicySet, PolicyToken, Verb};
36#[doc(hidden)]
37pub use policy_store::{FoldOutcome, FoldedRecord};
38pub use record::{Record, SnapshotPayload};
39pub use shard::ShardPlan;
40
41use std::sync::Arc;
42
43use dogwood_language::cedar::Schema;
44use dogwood_language::{
45    DecisionLeafMap, Error, Event, EventSignature, TemporalBindings, TemporalEngine, TemporalField,
46};
47
48/// A single-machine [`TemporalEngine`]: evaluates each temporal leaf at the
49/// current decision timepoint.
50#[derive(Default)]
51pub struct LocalTemporalEngine {
52    /// The temporal leaves to evaluate, installed at `prepare`.
53    leaves: Vec<TemporalField>,
54    /// The stable [`PolicyId`] of each installed policy, indexed by the policy's
55    /// **source position** (`policy_N` in a leaf's `id`). Set by [`set_policy_ids`](Self::set_policy_ids) after `prepare`, so
56    /// the keyed-state transplant can key each leaf by `(stable policy id,
57    /// within-policy clause ordinal)` rather than by content — which is what makes
58    /// retention scope to the *policy* (no cross-policy window sharing) and survive
59    /// a policy's source position shifting when another is added or deleted. Empty
60    /// until set; a leaf whose origin cannot be resolved keys fail-safe (matches
61    /// nothing, so it starts empty).
62    policy_ids: Vec<PolicyId>,
63    /// The most recently observed event: the decision point every `evaluate`
64    /// anchors on.
65    ///
66    /// `None` before the first `observe`, and after a snapshot-based recovery
67    /// until a live event arrives — `step_monitors` deliberately advances
68    /// monitors without it.
69    latest: Option<Event>,
70    /// The unit the timestamps this engine is fed are in, used to convert each
71    /// declared window into the same domain (see [`TickRate`]). Seconds by
72    /// default, matching `dogwood_language`'s interpreter and the corpus.
73    tick_rate: TickRate,
74    /// Per-leaf incremental monitor, same length and order as `leaves`, stepped
75    /// on every `observe`.
76    ///
77    /// Not optional: `prepare` refuses a policy set containing a leaf it cannot
78    /// compile, so every leaf has one by construction.
79    ///
80    /// Behind an [`Arc`] so a policy change can hand a leaf's accumulated window
81    /// to the engine replacing it **without copying or serializing it**. Every
82    /// mutation goes through `Arc::make_mut`, which clones only while a handle is
83    /// genuinely shared — and sharing is momentary: the old engine is dropped as
84    /// soon as the new set is installed, so the refcount is 1 and stepping is
85    /// free from then on.
86    monitors: Vec<Arc<incremental::Monitor>>,
87    /// Aggregate-memo kill switch (inverted so `derive(Default)` means
88    /// ENABLED): set via `disable_agg_memo()` or, fleet-wide, the
89    /// DOGWOOD_DISABLE_AGG_MEMO env var (checked at prepare).
90    agg_memo_disabled: bool,
91    /// Partition keys: non-empty ⇒
92    /// partitioned mode — `prepare` builds ShardedMonitors from the
93    /// NON-relativized leaves the caller passes, and every event routes
94    /// to its pin's shard.
95    partition_keys: Vec<dogwood_language::PartitionKey>,
96    /// Per-leaf sharded state (parallel to `leaves`; partitioned mode).
97    sharded: Vec<partition::ShardedMonitor>,
98    /// Where the most recent event routed (the oracle's `last`).
99    last_pin: Option<String>,
100    /// The pin-set fingerprint, cached at set_partition_keys (used by
101    /// the keyed-state transplant verification).
102    partition_keys_fingerprint_cached: Vec<u8>,
103    /// Max observed event timestamp — the sweep's clock. The engine's
104    /// existing contract is a nondecreasing event stream; in partitioned
105    /// mode a violation would make the sweep DELETE a live shard (worse
106    /// than global mode's mis-windowing), so the clock is max-folded and
107    /// debug-asserted rather than trusted per-event.
108    global_now: i64,
109    /// The background dropper: dead shards are MOVED here for
110    /// off-thread deallocation (spawned lazily; None until first use).
111    dropper: Option<sync::mpsc::Sender<incremental::Monitor>>,
112    /// Cumulative leaf verdicts actually computed.
113    verdicts_computed: u64,
114    /// Leaf ids reachable by each decision, rebuilt at every `prepare`.
115    leaf_map: DecisionLeafMap,
116    /// Operational and test kill switch for verdict slicing.
117    slicing_disabled: bool,
118}
119
120impl LocalTemporalEngine {
121    /// A fresh engine with no observed history, interpreting timestamps in
122    /// whole seconds. Use [`with_tick_rate`](Self::with_tick_rate) for a store
123    /// that assigns them at another resolution.
124    pub fn new() -> Self {
125        Self::default()
126    }
127
128    /// Set the unit of the timestamps this engine will be fed, which is the unit
129    /// its windows are compared in. See [`TickRate`].
130    ///
131    /// Must be set BEFORE `prepare`: the conversion is applied when the monitors
132    /// are built, so a later change would leave
133    /// already-built windows in the old unit.
134    pub fn with_tick_rate(mut self, rate: TickRate) -> Self {
135        self.tick_rate = rate;
136        self
137    }
138}
139
140impl TemporalEngine for LocalTemporalEngine {
141    /// `events` (the declared event signatures) is unused.
142    /// `schema` supplies the actions used to rebuild the leaf map.
143    fn prepare(
144        &mut self,
145        leaves: &[TemporalField],
146        schema: &Schema,
147        _events: &[EventSignature],
148    ) -> Result<(), Error> {
149        self.leaves = leaves.to_vec();
150        // Build an incremental monitor per leaf, and refuse the whole policy set
151        // if any leaf cannot be compiled.
152        let mut monitors = Vec::with_capacity(self.leaves.len());
153        for leaf in &self.leaves {
154            match incremental::Monitor::build(&leaf.condition.condition, self.tick_rate) {
155                Some(mut monitor) => {
156                    if self.agg_memo_disabled || std::env::var("DOGWOOD_DISABLE_AGG_MEMO").is_ok() {
157                        monitor.disable_agg_memo();
158                    }
159                    monitors.push(Arc::new(monitor));
160                }
161                None => {
162                    return Err(Error::Leaf {
163                        id: leaf.id.clone(),
164                        message: "cannot be compiled: the condition still contains a macro \
165                                  call, a condition sigil, or a field-injection refinement, so \
166                                  macro expansion did not run over it. Refusing the policy set \
167                                  rather than accepting a leaf that cannot be evaluated."
168                            .to_string(),
169                    });
170                }
171            }
172        }
173        // Re-prepare drops the previous mode's state entirely: stale
174        // shards/monitors would otherwise be double-counted by the
175        // diagnostics, and a stale sweep clock could mis-sweep.
176        self.sharded.clear();
177        self.monitors.clear();
178        self.global_now = i64::MIN;
179        self.last_pin = None;
180        self.latest = None;
181        // The id↔position mapping belongs to the *previous* leaf set; the caller
182        // re-establishes it via `set_policy_ids` after this prepare. Until then a
183        // composite key falls back to the fail-safe (matches nothing) path.
184        self.policy_ids.clear();
185        // The map and leaves must always describe the same prepared policy set.
186        self.slicing_disabled |= std::env::var("DOGWOOD_DISABLE_SLICING").is_ok();
187        self.leaf_map = if self.slicing_disabled {
188            DecisionLeafMap::default()
189        } else {
190            DecisionLeafMap::build(&self.leaves, schema)
191        };
192        if self.partition_keys.is_empty() {
193            self.monitors = monitors;
194        } else {
195            // Partitioned mode: the monitors just built (from the
196            // NON-relativized leaves the caller passes per the trait
197            // contract) become shard TEMPLATES.
198            self.sharded = monitors
199                .into_iter()
200                .map(|m| {
201                    partition::ShardedMonitor::new(
202                        Arc::try_unwrap(m).unwrap_or_else(|a| (*a).clone()),
203                    )
204                })
205                .collect();
206        }
207        Ok(())
208    }
209
210    fn observe(&mut self, event: &Event) {
211        if !self.partition_keys.is_empty() {
212            let ts = event.timestamp();
213            debug_assert!(
214                self.global_now == i64::MIN || ts >= self.global_now,
215                "partitioned mode requires a nondecreasing event stream \
216                 (got {ts} after {}): the stale-shard sweep's clock depends on it",
217                self.global_now
218            );
219            self.global_now = self.global_now.max(ts);
220            let now = self.global_now;
221            let pin = partition::partition_value_of(event, &self.partition_keys);
222            let dropper = self.dropper_handle();
223            for sm in self.sharded.iter_mut() {
224                sm.step(event, &pin, now, dropper.as_ref());
225            }
226            self.last_pin = Some(pin);
227            self.latest = Some(event.clone());
228            return;
229        }
230        // Advance every incremental monitor by this event.
231        for m in self.monitors.iter_mut() {
232            Arc::make_mut(m).step(event);
233        }
234        self.latest = Some(event.clone());
235    }
236
237    /// Compute leaves reachable by this decision's action. A map miss
238    /// conservatively computes every leaf.
239    fn evaluate(&mut self) -> Result<TemporalBindings, String> {
240        let needed = self
241            .latest
242            .as_ref()
243            .and_then(|event| self.leaf_map.needed_for(event));
244        // Held as an owned `Arc` handle, not a borrow: `evaluate_leaves` takes
245        // `&mut self`, which a reference into `self.leaf_map` could not survive.
246        match &needed {
247            Some(set) => self.evaluate_leaves(Plan::Only(set)),
248            None => self.evaluate_leaves(Plan::All),
249        }
250    }
251
252    fn supports_partitioning(&self) -> bool {
253        true
254    }
255
256    /// Install the pins (called before `prepare` per the trait contract;
257    /// the leaves subsequently handed to `prepare` are non-relativized).
258    fn set_partition_keys(&mut self, keys: &[dogwood_language::PartitionKey]) {
259        // The trait contract: called BEFORE prepare. Accepting keys after
260        // prepare would leave observe iterating an empty shard list and
261        // evaluate returning EMPTY bindings — verdicts silently vanish
262        // (a fail-open at the authorization boundary). Refuse loudly.
263        assert!(
264            self.monitors.is_empty() && self.sharded.is_empty(),
265            "set_partition_keys must be called before prepare"
266        );
267        self.partition_keys = keys.to_vec();
268        self.partition_keys_fingerprint_cached = self.keys_fingerprint();
269    }
270}
271
272fn unresolved_composite_key(leaf_content_key: &str) -> String {
273    format!("?:{leaf_content_key}")
274}
275
276/// A leaf's transplant key: `"{policy id}:{clause ordinal}:{leaf_content_key}"`.
277///
278/// The `(stable policy id, within-policy clause ordinal)` prefix is the
279/// retention identity; the trailing `leaf_content_key` is content, kept
280/// as a **defensive guard** folded into the key so a match requires the formula
281/// itself to still agree (a disagreement resets rather than carrying, never panicking in
282/// release). Because the policy id and ordinal are colon-free digit runs, the
283/// two leading colons are unambiguous separators, so the key is injective in
284/// `(id, ordinal, content)` regardless of what the content contains.
285///
286/// If the leaf's origin cannot be resolved (an unexpected `leaf_id` shape, or
287/// `policy_ids` unset — the case for a bare [`LocalTemporalEngine`] used
288/// outside the durable layer), the key degrades to a `?:{content}` form. That
289/// is still sound (a key can only match another key with the same content),
290/// but loses the cross-policy-sharing guard the composite provides. The
291/// durable layer's [`DurableTemporalEngine::rebuild`] always calls
292/// [`LocalTemporalEngine::set_policy_ids`], so it never lands here.
293fn composite_key(policy_ids: &[PolicyId], leaf_id: &str, leaf_content_key: &str) -> String {
294    match parse_leaf_origin(leaf_id) {
295        Some((source_position, clause_ordinal)) if source_position < policy_ids.len() => {
296            composite_transplant_key(
297                policy_ids[source_position],
298                clause_ordinal,
299                leaf_content_key,
300            )
301        }
302        _ => unresolved_composite_key(leaf_content_key),
303    }
304}
305
306const KEYED_STATE_MAGIC: [u8; 5] = *b"DLEK1";
307const KEYED_STATE_GLOBAL: u8 = 0;
308const KEYED_STATE_PARTITIONED: u8 = 1;
309
310fn encode_keyed_state(body: Vec<u8>, fingerprint: Option<&[u8]>) -> Vec<u8> {
311    let fingerprint_len = fingerprint.map_or(0, |value| value.len());
312    let mut encoded = Vec::with_capacity(
313        KEYED_STATE_MAGIC.len()
314            + 1
315            + if fingerprint.is_some() {
316                8 + fingerprint_len
317            } else {
318                0
319            }
320            + body.len(),
321    );
322    encoded.extend_from_slice(&KEYED_STATE_MAGIC);
323    match fingerprint {
324        None => encoded.push(KEYED_STATE_GLOBAL),
325        Some(value) => {
326            encoded.push(KEYED_STATE_PARTITIONED);
327            encoded.extend_from_slice(&(value.len() as u64).to_le_bytes());
328            encoded.extend_from_slice(value);
329        }
330    }
331    encoded.extend_from_slice(&body);
332    encoded
333}
334
335fn decode_keyed_state<'a>(
336    encoded: &'a [u8],
337    expected_fingerprint: Option<&[u8]>,
338) -> Option<&'a [u8]> {
339    let body_start = KEYED_STATE_MAGIC.len() + 1;
340    if encoded.get(..KEYED_STATE_MAGIC.len())? != KEYED_STATE_MAGIC.as_slice() {
341        return None;
342    }
343    let mode = *encoded.get(KEYED_STATE_MAGIC.len())?;
344    match (mode, expected_fingerprint) {
345        (KEYED_STATE_GLOBAL, None) => encoded.get(body_start..),
346        (KEYED_STATE_PARTITIONED, Some(expected)) => {
347            let length_end = body_start.checked_add(8)?;
348            let length_bytes = encoded.get(body_start..length_end)?;
349            let fingerprint_len =
350                usize::try_from(u64::from_le_bytes(length_bytes.try_into().ok()?)).ok()?;
351            let fingerprint_end = length_end.checked_add(fingerprint_len)?;
352            if encoded.get(length_end..fingerprint_end)? != expected {
353                return None;
354            }
355            encoded.get(fingerprint_end..)
356        }
357        _ => None,
358    }
359}
360
361fn clone_shared_leaf_state(monitor: &Arc<incremental::Monitor>) -> LeafState {
362    LeafState(Arc::clone(monitor))
363}
364
365fn install_shared_leaf_state(monitor: &mut Arc<incremental::Monitor>, state: &LeafState) {
366    *monitor = Arc::clone(&state.0);
367}
368
369fn string_contents_equal(left: &String, right: &String) -> bool {
370    left.eq(right)
371}
372
373fn first_matching_leaf_state(entries: &[(String, LeafState)], key: &String) -> Option<usize> {
374    let mut index = 0usize;
375    while index < entries.len() {
376        if string_contents_equal(&entries[index].0, key) {
377            return Some(index);
378        }
379        index += 1;
380    }
381    None
382}
383
384fn first_matching_serialized_entry(entries: &[(String, Vec<u8>)], key: &String) -> Option<usize> {
385    let mut index = 0usize;
386    while index < entries.len() {
387        if string_contents_equal(&entries[index].0, key) {
388            return Some(index);
389        }
390        index += 1;
391    }
392    None
393}
394
395fn load_global_keyed_bytes(monitor: &mut Arc<incremental::Monitor>, encoded: &[u8]) -> bool {
396    let Some(body) = decode_keyed_state(encoded, None) else {
397        return false;
398    };
399    Arc::make_mut(monitor).load(body)
400}
401
402fn load_sharded_keyed_bytes(
403    monitor: &mut partition::ShardedMonitor,
404    encoded: &[u8],
405    fingerprint: &[u8],
406) -> bool {
407    let Some(body) = decode_keyed_state(encoded, Some(fingerprint)) else {
408        return false;
409    };
410    let mut pos = 0usize;
411    monitor.load(body, &mut pos).is_some() && pos == body.len()
412}
413
414fn load_global_serialized_by_key(
415    keys: &[String],
416    monitors: &mut Vec<Arc<incremental::Monitor>>,
417    entries: &[(String, Vec<u8>)],
418) -> Option<usize> {
419    if keys.len() != monitors.len() {
420        return None;
421    }
422    let mut restored = 0usize;
423    let mut index = 0usize;
424    while index < keys.len() {
425        if let Some(source_index) = first_matching_serialized_entry(entries, &keys[index]) {
426            if load_global_keyed_bytes(&mut monitors[index], &entries[source_index].1) {
427                restored += 1;
428            }
429        }
430        index += 1;
431    }
432    Some(restored)
433}
434
435fn load_sharded_serialized_by_key(
436    keys: &[String],
437    monitors: &mut Vec<partition::ShardedMonitor>,
438    entries: &[(String, Vec<u8>)],
439    fingerprint: &[u8],
440    initial_max_ts: i64,
441) -> Option<(usize, i64)> {
442    if keys.len() != monitors.len() {
443        return None;
444    }
445    let mut restored = 0usize;
446    let mut max_ts = initial_max_ts;
447    let mut index = 0usize;
448    while index < keys.len() {
449        if let Some(source_index) = first_matching_serialized_entry(entries, &keys[index]) {
450            if load_sharded_keyed_bytes(&mut monitors[index], &entries[source_index].1, fingerprint)
451            {
452                restored += 1;
453                max_ts = max_ts.max(monitors[index].newest_shard_ts().unwrap_or(i64::MIN));
454            }
455        }
456        index += 1;
457    }
458    Some((restored, max_ts))
459}
460
461fn share_leaf_states_by_key(
462    keys: Vec<String>,
463    monitors: &Vec<Arc<incremental::Monitor>>,
464) -> Vec<(String, LeafState)> {
465    let mut shared = Vec::with_capacity(keys.len());
466    for key in keys {
467        let index = shared.len();
468        let state = clone_shared_leaf_state(&monitors[index]);
469        shared.push((key, state));
470    }
471    shared
472}
473
474fn adopt_leaf_states_by_key(
475    keys: &Vec<String>,
476    monitors: &mut Vec<Arc<incremental::Monitor>>,
477    entries: &[(String, LeafState)],
478) -> usize {
479    let mut restored = 0usize;
480    let mut index = 0usize;
481    while index < keys.len() {
482        let match_index = first_matching_leaf_state(entries, &keys[index]);
483        if let Some(source_index) = match_index {
484            install_shared_leaf_state(&mut monitors[index], &entries[source_index].1);
485            restored += 1;
486        }
487        index += 1;
488    }
489    restored
490}
491
492/// Leaves to compute. Both plans bind every installed leaf.
493#[derive(Clone, Copy, Debug)]
494enum Plan<'a> {
495    All,
496    Only(&'a std::collections::BTreeSet<String>),
497}
498
499impl LocalTemporalEngine {
500    /// Skipped leaves are bound `false`; only computed leaves are counted.
501    fn evaluate_leaves(&mut self, plan: Plan<'_>) -> Result<TemporalBindings, String> {
502        // The current decision point is the most recently observed event.
503        let decision = self.latest.as_ref().ok_or("no event observed")?;
504        let wanted = |id: &str| match plan {
505            Plan::All => true,
506            Plan::Only(needed) => needed.contains(id),
507        };
508        let mut computed = 0u64;
509        let bindings = if !self.partition_keys.is_empty() {
510            let pin = self.last_pin.as_ref().ok_or("no event observed")?;
511            self.leaves
512                .iter()
513                .zip(&self.sharded)
514                .map(|(leaf, sm)| {
515                    let verdict = if wanted(&leaf.id) {
516                        computed += 1;
517                        sm.verdict(decision, pin)
518                    } else {
519                        false
520                    };
521                    (leaf.id.clone(), verdict)
522                })
523                .collect::<TemporalBindings>()
524        } else {
525            self.leaves
526                .iter()
527                .zip(&self.monitors)
528                // The request is seeded into the monitor's env from the decision
529                // event at verdict time.
530                .map(|(leaf, monitor)| {
531                    let verdict = if wanted(&leaf.id) {
532                        computed += 1;
533                        monitor.verdict(decision)
534                    } else {
535                        false
536                    };
537                    (leaf.id.clone(), verdict)
538                })
539                .collect::<TemporalBindings>()
540        };
541        self.verdicts_computed += computed;
542        Ok(bindings)
543    }
544
545    /// Cumulative count of leaf verdicts actually computed.
546    #[doc(hidden)]
547    pub fn verdicts_computed(&self) -> u64 {
548        self.verdicts_computed
549    }
550
551    /// Turn verdict slicing off so every `evaluate` computes every leaf.
552    ///
553    /// Effective before or after `prepare`. Also settable with
554    /// `DOGWOOD_DISABLE_SLICING`.
555    #[doc(hidden)]
556    pub fn disable_slicing(&mut self) {
557        self.slicing_disabled = true;
558        self.leaf_map = DecisionLeafMap::default();
559    }
560
561    /// Number of decisions the leaf map can answer without falling back.
562    #[doc(hidden)]
563    pub fn leaf_map_entries(&self) -> usize {
564        self.leaf_map.entry_count()
565    }
566
567    /// Leaves whose action scopes could not be resolved to concrete actions.
568    #[doc(hidden)]
569    pub fn unresolved_action_scopes(&self) -> Vec<(String, &'static str)> {
570        self.leaf_map.unresolved().to_vec()
571    }
572
573    /// How many installed leaves run on the incremental path.
574    /// A diagnostic — and the hook tests use to prove the
575    /// incremental operators are actually exercised. Valid after `prepare`.
576    pub fn incremental_leaf_count(&self) -> usize {
577        if self.partition_keys.is_empty() {
578            self.monitors.len()
579        } else {
580            self.sharded.len()
581        }
582    }
583
584    /// The pin set's identity (field paths, ordered).
585    fn keys_fingerprint(&self) -> Vec<u8> {
586        let mut out = Vec::new();
587        for k in &self.partition_keys {
588            let path = k.field_path.join(".");
589            out.extend_from_slice(&(path.len() as u64).to_le_bytes());
590            out.extend_from_slice(path.as_bytes());
591        }
592        out
593    }
594
595    /// The identity of the leaf set this engine's snapshot state describes: each
596    /// installed leaf's [`leaf_key`], length-prefixed and concatenated in
597    /// `leaves` order.
598    ///
599    /// [`save_snapshot`](Self::save_snapshot) embeds this and
600    /// [`load_snapshot`](Self::load_snapshot) refuses a snapshot whose embedded
601    /// value disagrees. That check is what makes snapshot recovery safe, because
602    /// the snapshot payload is **positional**: it restores the k-th monitor's
603    /// state into the k-th leaf, and validates only arity and byte framing. Two
604    /// different leaf sets of the same arity — a plausible pair, since editing one
605    /// rule's condition leaves the count unchanged — would otherwise load into
606    /// each other, binding one formula's history to another. That is not a
607    /// corrupt-data problem but a wrong-verdict one: a `formerly` would hold at
608    /// timepoints where its own predicate never matched.
609    ///
610    /// The keys are length-prefixed for the same reason [`leaf_key`] prefixes its
611    /// own payloads: so no combination of key contents can imitate a different
612    /// sequence.
613    fn state_fingerprint(&self) -> Vec<u8> {
614        let mut out = Vec::new();
615        // The MODE + pin set are part of the identity: a global snapshot
616        // must not load into a partitioned engine (or vice versa), and a
617        // partitioned one must not load under a different key set — the
618        // shard payloads would be misread positionally.
619        // Preamble ONLY in partitioned mode.
620        //
621        // WHY cross-mode fingerprints can never collide (the precise
622        // invariant — re-verify before ANY change to this encoding, it
623        // guards a security-critical refusal): it is NOT merely
624        // "count vs length" on the leading u64 (with ≥10 keys those can
625        // coincide). After the count, the partitioned preamble emits u64
626        // PATH-LENGTH prefixes whose high bytes are 0x00 at fixed
627        // offsets, whereas a global fingerprint holds NUL-free ASCII
628        // leaf-key content at those offsets (leaf keys are rendered
629        // conditions, min ~10 bytes, no NULs) — the byte streams diverge
630        // within the first ~9 bytes regardless of key counts. Do not
631        // switch to varint lengths or reorder fields without a new
632        // collision argument.
633        if !self.partition_keys.is_empty() {
634            out.extend_from_slice(&(self.partition_keys.len() as u64).to_le_bytes());
635            for k in &self.partition_keys {
636                let path = k.field_path.join(".");
637                out.extend_from_slice(&(path.len() as u64).to_le_bytes());
638                out.extend_from_slice(path.as_bytes());
639            }
640        }
641        for leaf in &self.leaves {
642            let key = leaf_key(leaf);
643            out.extend_from_slice(&(key.len() as u64).to_le_bytes());
644            out.extend_from_slice(key.as_bytes());
645        }
646        out
647    }
648
649    /// Kill switch for the aggregate memo.
650    /// Effective in either order: before `prepare` (sets the default
651    /// for built monitors) or after (disables the live ones). Also
652    /// settable fleet-wide via `DOGWOOD_DISABLE_AGG_MEMO`.
653    #[doc(hidden)]
654    pub fn disable_agg_memo(&mut self) {
655        self.agg_memo_disabled = true;
656        for m in self.monitors.iter_mut() {
657            std::sync::Arc::make_mut(m).disable_agg_memo();
658        }
659        for sm in self.sharded.iter_mut() {
660            sm.disable_agg_memo();
661        }
662    }
663
664    /// Total memo entries across monitors (steady-state boundedness).
665    #[doc(hidden)]
666    pub fn agg_memo_len(&self) -> usize {
667        self.monitors
668            .iter()
669            .map(|m| m.agg_memo_len())
670            .sum::<usize>()
671            + self
672                .sharded
673                .iter()
674                .map(|sm| sm.agg_memo_len())
675                .sum::<usize>()
676    }
677
678    /// (hits, misses) summed across monitors.
679    #[doc(hidden)]
680    pub fn agg_memo_stats(&self) -> (u64, u64) {
681        let base = self.monitors.iter().fold((0, 0), |(h, m), mon| {
682            let (a, b) = mon.agg_memo_stats();
683            (h + a, m + b)
684        });
685        self.sharded.iter().fold(base, |(h, m), sm| {
686            let (a, b) = sm.agg_memo_stats();
687            (h + a, m + b)
688        })
689    }
690
691    /// Whether this engine runs in partitioned mode (pins installed).
692    #[doc(hidden)]
693    pub fn is_partitioned(&self) -> bool {
694        !self.partition_keys.is_empty()
695    }
696
697    /// Live shard count across leaves (0 in global mode).
698    #[doc(hidden)]
699    pub fn shard_count(&self) -> usize {
700        self.sharded.iter().map(|sm| sm.shard_count()).sum()
701    }
702
703    /// The newest timestamp represented by serialized monitor state.
704    ///
705    /// The durable snapshot envelope uses this to validate that its `last_ts`
706    /// high-water mark cannot fall behind the engine state it encloses.
707    pub(crate) fn latest_state_timestamp(&self) -> i64 {
708        if !self.partition_keys.is_empty() {
709            return self.global_now;
710        }
711        self.monitors
712            .iter()
713            .filter_map(|monitor| monitor.last_event_ts())
714            .max()
715            .unwrap_or(i64::MIN)
716    }
717
718    /// Drain the stale-shard sweep completely, dropping synchronously —
719    /// the host's idle-maintenance hook (the engine has no clock of its
720    /// own; observe-driven sweeps are bounded, this one is exhaustive).
721    #[doc(hidden)]
722    pub fn maintain_all(&mut self) {
723        // Gate on the sweep CLOCK, not `latest`: recovery
724        // replays through step_monitors, which advances global_now but
725        // never sets latest.
726        if self.global_now == i64::MIN {
727            return;
728        }
729        let now = self.global_now;
730        for sm in self.sharded.iter_mut() {
731            sm.sweep_all(now);
732        }
733    }
734
735    /// The background dropper's sender, spawning the thread on first
736    /// use. Dead shards are MOVED here; the thread only receives and
737    /// drops (background freeing — no engine state is shared).
738    fn dropper_handle(&mut self) -> Option<sync::mpsc::Sender<incremental::Monitor>> {
739        if self.dropper.is_none() {
740            let (tx, rx) = sync::mpsc::channel::<incremental::Monitor>();
741            sync::thread::Builder::new()
742                .name("dogwood-shard-dropper".into())
743                .spawn(move || while rx.recv().is_ok() {})
744                .ok()?;
745            self.dropper = Some(tx);
746        }
747        self.dropper.clone()
748    }
749
750    /// Serialize every incremental monitor's derived state,
751    /// length-prefixed per leaf in `leaves` order, so a restart can restore the
752    /// monitors without replaying the whole log — the only way to bound
753    /// recovery (and log pruning) for **unbounded** operators, whose window
754    /// never expires. Valid after `prepare`.
755    ///
756    /// Prefixed with the leaf set's identity (`state_fingerprint`), so a
757    /// snapshot cannot be loaded into a different leaf set.
758    pub fn save_snapshot(&self) -> Vec<u8> {
759        let mut out = Vec::new();
760        let fingerprint = self.state_fingerprint();
761        out.extend_from_slice(&(fingerprint.len() as u64).to_le_bytes());
762        out.extend_from_slice(&fingerprint);
763        if !self.partition_keys.is_empty() {
764            // Format v2: global_now, then one
765            // sharded body per leaf. The fingerprint above already binds
766            // mode + keys, so a v1 reader refuses before touching this.
767            out.extend_from_slice(&self.global_now.to_le_bytes());
768            out.extend_from_slice(&(self.sharded.len() as u64).to_le_bytes());
769            for sm in &self.sharded {
770                let bytes = sm.save(self.global_now);
771                out.extend_from_slice(&(bytes.len() as u64).to_le_bytes());
772                out.extend_from_slice(&bytes);
773            }
774            return out;
775        }
776        out.extend_from_slice(&(self.monitors.len() as u64).to_le_bytes());
777        for m in &self.monitors {
778            let bytes = m.save();
779            out.extend_from_slice(&(bytes.len() as u64).to_le_bytes());
780            out.extend_from_slice(&bytes);
781        }
782        out
783    }
784
785    /// Restore monitor state produced by [`save_snapshot`](Self::save_snapshot)
786    /// into the (already-`prepare`d, same-leaves) engine. Returns `false` on
787    /// any mismatch/corruption without changing existing monitor state, so the
788    /// caller can safely fall back to full replay.
789    pub fn load_snapshot(&mut self, bytes: &[u8]) -> bool {
790        let mut pos = 0usize;
791        let read_u64 = |b: &[u8], p: &mut usize| -> Option<u64> {
792            let end = p.checked_add(8)?;
793            let v = u64::from_le_bytes(b.get(*p..end)?.try_into().ok()?);
794            *p = end;
795            Some(v)
796        };
797        let read_usize =
798            |b: &[u8], p: &mut usize| -> Option<usize> { usize::try_from(read_u64(b, p)?).ok() };
799        // Refuse a snapshot describing a DIFFERENT leaf set before restoring any
800        // state. The payload below is positional, so without this a stale
801        // snapshot of equal arity would load successfully and hand one formula
802        // another's history — see `state_fingerprint`.
803        let Some(fp_len) = read_usize(bytes, &mut pos) else {
804            return false;
805        };
806        let fp_end = match pos.checked_add(fp_len) {
807            Some(e) if e <= bytes.len() => e,
808            _ => return false,
809        };
810        if bytes[pos..fp_end] != self.state_fingerprint()[..] {
811            return false;
812        }
813        pos = fp_end;
814
815        if !self.partition_keys.is_empty() {
816            // Format v2: the fingerprint (mode + keys + leaves) matched,
817            // so the body is per-leaf sharded state.
818            let Some(now_end) = pos.checked_add(8) else {
819                return false;
820            };
821            let Some(now_bytes) = bytes.get(pos..now_end) else {
822                return false;
823            };
824            let global_now = i64::from_le_bytes(now_bytes.try_into().expect("8 bytes"));
825            pos = now_end;
826            let Some(count) = read_usize(bytes, &mut pos) else {
827                return false;
828            };
829            if count != self.sharded.len() {
830                return false;
831            }
832            let mut sharded: Vec<_> = self
833                .sharded
834                .iter()
835                .map(partition::ShardedMonitor::empty_for_restore)
836                .collect();
837            for sm in sharded.iter_mut() {
838                let Some(len) = read_usize(bytes, &mut pos) else {
839                    return false;
840                };
841                let end = match pos.checked_add(len) {
842                    Some(e) if e <= bytes.len() => e,
843                    _ => return false,
844                };
845                let mut inner = 0usize;
846                if sm.load(&bytes[pos..end], &mut inner).is_none() || inner != end - pos {
847                    return false;
848                }
849                pos = end;
850            }
851            if pos != bytes.len() {
852                return false;
853            }
854            if sharded.iter().any(|monitor| {
855                monitor
856                    .newest_shard_ts()
857                    .is_some_and(|timestamp| timestamp > global_now)
858            }) {
859                return false;
860            }
861            self.sharded = sharded;
862            self.global_now = global_now;
863            return true;
864        }
865
866        let Some(count) = read_usize(bytes, &mut pos) else {
867            return false;
868        };
869        if count != self.monitors.len() {
870            return false;
871        }
872        let mut monitors = self.monitors.clone();
873        for m in monitors.iter_mut() {
874            let Some(len) = read_usize(bytes, &mut pos) else {
875                return false;
876            };
877            let end = match pos.checked_add(len) {
878                Some(e) if e <= bytes.len() => e,
879                _ => return false,
880            };
881            if !Arc::make_mut(m).load(&bytes[pos..end]) {
882                return false;
883            }
884            pos = end;
885        }
886        if pos != bytes.len() {
887            return false;
888        }
889        self.monitors = monitors;
890        true
891    }
892
893    /// Advance only the incremental monitors by `event`, for replaying
894    /// post-snapshot events during recovery.
895    pub fn step_monitors(&mut self, event: &Event) {
896        // Partitioned mode: route the
897        // event exactly as observe does, advancing the sweep clock, but
898        // deliberately NOT touching `latest`/`last_pin` — this method's
899        // contract is "advance state without a decision context".
900        if !self.partition_keys.is_empty() {
901            let ts = event.timestamp();
902            self.global_now = self.global_now.max(ts);
903            let now = self.global_now;
904            let pin = partition::partition_value_of(event, &self.partition_keys);
905            let dropper = self.dropper_handle();
906            for sm in self.sharded.iter_mut() {
907                sm.step(event, &pin, now, dropper.as_ref());
908            }
909            return;
910        }
911        for m in self.monitors.iter_mut() {
912            Arc::make_mut(m).step(event);
913        }
914    }
915
916    // ─── Keyed state: the prospective-install mechanism ──────────
917
918    /// Record the stable [`PolicyId`] of each installed policy, indexed by source
919    /// position — the map the composite keyed-state key needs.
920    /// Call after `prepare`, before any
921    /// transplant. `ids[N]` is the policy whose leaves carry `policy_N` in their
922    /// `id`, i.e. the N-th policy in the combined source (ascending id order).
923    pub fn set_policy_ids(&mut self, ids: &[PolicyId]) {
924        self.policy_ids = ids.to_vec();
925    }
926
927    /// Hand every leaf's accumulated state to another engine **without copying
928    /// it**, keyed by content-derived identity ([`leaf_key`]) exactly as
929    /// [`save_keyed_state`](Self::save_keyed_state) is.
930    ///
931    /// This is the in-memory counterpart of the serialized form, and the one a
932    /// policy change should use. Sharing an [`Arc`] is O(1) per leaf and converts no formats.
933    ///
934    /// Use [`save_keyed_state`](Self::save_keyed_state) when the destination is a
935    /// disk; use this when it is another engine.
936    pub fn share_leaf_state(&self) -> Result<Vec<(String, LeafState)>, LeafStateTransferError> {
937        // Partitioned engines have no per-leaf monitor to transplant —
938        // iterating self.monitors here would SILENTLY LOSE every shard
939        // on a policy apply (masked by prospective-install semantics).
940        self.validate_leaf_state_transfer()?;
941        let keys: Vec<String> = self
942            .leaves
943            .iter()
944            .map(|leaf| {
945                let content = leaf_key(leaf);
946                composite_key(&self.policy_ids, &leaf.id, &content)
947            })
948            .collect();
949        Ok(share_leaf_states_by_key(keys, &self.monitors))
950    }
951
952    /// Adopt shared leaf state, matched by [`leaf_key`]. Returns how many leaves
953    /// were given a window; the rest retain their prior state. Policy rebuild
954    /// callers use a freshly prepared destination, so those unmatched leaves
955    /// remain empty, which is prospective-install semantics.
956    ///
957    /// The adopting engine shares each monitor with whoever handed it over until
958    /// the first mutation, and `Arc::make_mut` only copies while both are alive.
959    /// In the case this exists for — a policy change, where the previous set is
960    /// dropped as it is replaced — nothing is ever copied.
961    pub fn adopt_leaf_state(
962        &mut self,
963        entries: &[(String, LeafState)],
964    ) -> Result<usize, LeafStateTransferError> {
965        // Partitioned engines have no per-leaf monitor to transplant —
966        // iterating self.monitors here would SILENTLY LOSE every shard
967        // on a policy apply (masked by prospective-install semantics).
968        self.validate_leaf_state_transfer()?;
969        // Precompute the composite keys before mutably borrowing the monitors.
970        let keys: Vec<String> = self
971            .leaves
972            .iter()
973            .map(|leaf| {
974                let content = leaf_key(leaf);
975                composite_key(&self.policy_ids, &leaf.id, &content)
976            })
977            .collect();
978        Ok(adopt_leaf_states_by_key(&keys, &mut self.monitors, entries))
979    }
980
981    fn validate_leaf_state_transfer(&self) -> Result<(), LeafStateTransferError> {
982        if !self.partition_keys.is_empty() {
983            return Err(LeafStateTransferError::PartitionedEngine);
984        }
985        validate_leaf_monitor_count(self.leaves.len(), self.monitors.len())
986    }
987
988    /// Serialize each incremental monitor's state **keyed by its leaf's
989    /// content-derived identity** ([`leaf_key`]) rather than by position.
990    ///
991    /// This is what makes prospective policy installs correct.
992    /// [`save_snapshot`](Self::save_snapshot) is positional, so it is
993    /// only valid when reloaded into an engine prepared with the *identical*
994    /// leaf list — fine for crash recovery, wrong across a policy change, where
995    /// inserting a rule shifts every later leaf's index and would hand one
996    /// formula's accumulated window to a different formula. Keying by formula
997    /// content instead means:
998    ///
999    /// - an **unchanged** leaf finds its key and resumes with its window intact;
1000    /// - a **new** leaf finds no key and starts empty — exactly the prospective
1001    ///   semantics, with no epoch bookkeeping needed in the state itself;
1002    /// - a **removed** leaf's entry is simply never claimed.
1003    pub fn save_keyed_state(&self) -> Vec<(String, Vec<u8>)> {
1004        if !self.partition_keys.is_empty() {
1005            // Partitioned: each leaf's entry is its SHARDED body (the v2
1006            // per-leaf encoding — sweep-filtered), wrapped in an explicit
1007            // partitioned envelope with the pin-set fingerprint. The mode tag
1008            // makes cross-mode refusal structural rather than relying on the
1009            // monitor decoders to reject another format accidentally.
1010            let kfp = self.keys_fingerprint();
1011            return self
1012                .leaves
1013                .iter()
1014                .zip(&self.sharded)
1015                .map(|(leaf, sm)| {
1016                    let bytes = encode_keyed_state(sm.save(self.global_now), Some(kfp.as_slice()));
1017                    let content = leaf_key(leaf);
1018                    (composite_key(&self.policy_ids, &leaf.id, &content), bytes)
1019                })
1020                .collect();
1021        }
1022        self.leaves
1023            .iter()
1024            .zip(&self.monitors)
1025            .map(|(leaf, monitor)| {
1026                let content = leaf_key(leaf);
1027                (
1028                    composite_key(&self.policy_ids, &leaf.id, &content),
1029                    encode_keyed_state(monitor.save(), None),
1030                )
1031            })
1032            .collect()
1033    }
1034
1035    /// Restore keyed state from [`save_keyed_state`](Self::save_keyed_state)
1036    /// into this (already-`prepare`d) engine, matching leaves by content
1037    /// identity. Returns the number of leaves whose state was restored; leaves
1038    /// with no matching entry keep their fresh (empty) state, which is the
1039    /// prospective-install path. A destination whose leaf and monitor counts
1040    /// disagree is rejected before any monitor is changed.
1041    ///
1042    /// An entry whose bytes fail to load is skipped, leaving that leaf empty
1043    /// rather than half-loaded — a leaf that under-reports history is the
1044    /// fail-safe direction (it can only fail to fire a `formerly`, matching a
1045    /// freshly-installed rule's warm-up window).
1046    pub fn load_keyed_state(
1047        &mut self,
1048        entries: &[(String, Vec<u8>)],
1049    ) -> Result<usize, LeafStateTransferError> {
1050        // Precompute composite keys before mutably borrowing monitor state.
1051        let keys: Vec<String> = self
1052            .leaves
1053            .iter()
1054            .map(|leaf| {
1055                let content = leaf_key(leaf);
1056                composite_key(&self.policy_ids, &leaf.id, &content)
1057            })
1058            .collect();
1059        if !self.partition_keys.is_empty() {
1060            let Some((restored, max_ts)) = load_sharded_serialized_by_key(
1061                &keys,
1062                &mut self.sharded,
1063                entries,
1064                self.partition_keys_fingerprint_cached.as_slice(),
1065                self.global_now,
1066            ) else {
1067                return Err(LeafStateTransferError::LeafMonitorCountMismatch {
1068                    leaves: self.leaves.len(),
1069                    monitors: self.sharded.len(),
1070                });
1071            };
1072            self.global_now = max_ts;
1073            return Ok(restored);
1074        }
1075        load_global_serialized_by_key(&keys, &mut self.monitors, entries).ok_or(
1076            LeafStateTransferError::LeafMonitorCountMismatch {
1077                leaves: self.leaves.len(),
1078                monitors: self.monitors.len(),
1079            },
1080        )
1081    }
1082
1083    /// The content-derived identity of every installed leaf, in `leaves` order —
1084    /// a **diagnostic**.
1085    pub fn leaf_keys(&self) -> Vec<String> {
1086        self.leaves.iter().map(leaf_key).collect()
1087    }
1088
1089    /// The leaves' **composite** transplant keys — the composite key builder
1090    /// for each, i.e. the resolved `"{policy id}:{ordinal}:{content}"` form, or
1091    /// the `"?:{content}"` fallback when a leaf's origin cannot be resolved
1092    /// (an unexpected id shape, or [`policy_ids`](Self::set_policy_ids) too short
1093    /// for its `policy_N`). Unlike [`leaf_keys`](Self::leaf_keys) — which returns
1094    /// the bare *content* key and so never carries the `?:` sentinel — this
1095    /// reflects the actual retention key, so the durable layer can scan it to
1096    /// refuse a transplant whose state it could not scope to a policy.
1097    pub fn composite_leaf_keys(&self) -> Vec<String> {
1098        self.leaves
1099            .iter()
1100            .map(|leaf| {
1101                let content = leaf_key(leaf);
1102                composite_key(&self.policy_ids, &leaf.id, &content)
1103            })
1104            .collect()
1105    }
1106}
1107
1108/// Parse a leaf's generated `id` (`policy_N__temporal_M` or an equivalent
1109/// distincter-prefixed spelling) into `(N, M)`.
1110///
1111/// The frontend emits leaf ids as `{rule_key}__temporal_{ordinal}`, where
1112/// `rule_key` is `policy_{N}` under the default lowering (or
1113/// `{distincter}_{N}` when a distincter is set) and `ordinal` is the leaf's
1114/// position among *all* hoisted leaves in that policy — a temporal+provider
1115/// shared counter, so it is not a dense temporal-only index. That is exactly
1116/// what we want here: the composite key must survive a policy edit that adds or
1117/// removes an unrelated provider leaf, so long as the *remaining* temporal
1118/// clauses keep their traversal positions, which they do when the policy is
1119/// unchanged.
1120///
1121/// This is the same id [`identity.rs`](crate::leaf_key) documents as
1122/// **positional**: that module's `__temporal_M` is the `ordinal` read here (it
1123/// shifts when a rule is inserted ahead of the leaf), and the `policy_N` prefix
1124/// — which that doc elides — names the owning policy. `composite_key` keys on the
1125/// pair, so a shifted `ordinal` alone does not change the retention identity.
1126///
1127/// Returns `None` on any deviation from the expected shape — which the durable
1128/// transplant guard turns into a fail-closed rejection, so a lowering change to
1129/// the id format surfaces loudly rather than silently mis-scoping history.
1130#[doc(hidden)]
1131pub fn parse_leaf_origin(id: &str) -> Option<(usize, usize)> {
1132    // Find the `__temporal_` seam, then require the exact
1133    // `{cedar_identifier}_{policy_index}` rule-key shape emitted by lowering.
1134    let (prefix, suffix) = id.rsplit_once("__temporal_")?;
1135    let ordinal: usize = suffix.parse().ok()?;
1136    let (distincter, policy_index) = prefix.rsplit_once('_')?;
1137    let mut chars = distincter.chars();
1138    let first = chars.next()?;
1139    if !(first == '_' || first.is_ascii_alphabetic())
1140        || !chars.all(|ch| ch == '_' || ch.is_ascii_alphanumeric())
1141    {
1142        return None;
1143    }
1144    let policy_index: usize = policy_index.parse().ok()?;
1145    Some((policy_index, ordinal))
1146}
1147
1148/// Construct the resolved transplant key from its independently meaningful
1149/// parts. Kept public-but-hidden so the external property suite can exhaust
1150/// delimiter and injectivity adversaries without constructing monitor state.
1151#[doc(hidden)]
1152pub fn composite_transplant_key(
1153    policy_id: PolicyId,
1154    clause_ordinal: usize,
1155    leaf_content_key: &str,
1156) -> String {
1157    format!("{}:{clause_ordinal}:{leaf_content_key}", policy_id.0)
1158}
1159
1160/// One leaf's accumulated monitor state, shared rather than copied.
1161///
1162/// Opaque on purpose: the monitor's internals are an implementation detail, and a
1163/// consumer only needs to be able to carry this from one engine to another. Cheap
1164/// to clone — it is a refcount.
1165#[derive(Clone)]
1166pub struct LeafState(Arc<incremental::Monitor>);
1167
1168impl std::fmt::Debug for LeafState {
1169    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
1170        f.write_str("LeafState(..)")
1171    }
1172}
1173
1174/// A leaf-state transfer cannot be performed without risking lost or
1175/// incorrectly associated monitor history.
1176#[derive(Debug, Clone, PartialEq, Eq)]
1177pub enum LeafStateTransferError {
1178    /// Partitioned engines store state in shards rather than `monitors`.
1179    PartitionedEngine,
1180    /// An engine violated its parallel leaf/monitor vector invariant.
1181    LeafMonitorCountMismatch {
1182        /// Installed leaves.
1183        leaves: usize,
1184        /// Monitors the engine holds.
1185        monitors: usize,
1186    },
1187}
1188
1189impl std::fmt::Display for LeafStateTransferError {
1190    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
1191        match self {
1192            LeafStateTransferError::PartitionedEngine => {
1193                write!(
1194                    f,
1195                    "leaf-state transfer is not supported on a partitioned engine"
1196                )
1197            }
1198            LeafStateTransferError::LeafMonitorCountMismatch { leaves, monitors } => {
1199                write!(
1200                    f,
1201                    "leaf and monitor counts diverged \
1202                     (leaves: {leaves}, monitors: {monitors})"
1203                )
1204            }
1205        }
1206    }
1207}
1208
1209impl std::error::Error for LeafStateTransferError {}
1210
1211fn validate_leaf_monitor_count(
1212    leaves: usize,
1213    monitors: usize,
1214) -> Result<(), LeafStateTransferError> {
1215    if leaves != monitors {
1216        return Err(LeafStateTransferError::LeafMonitorCountMismatch { leaves, monitors });
1217    }
1218    Ok(())
1219}
1220
1221#[cfg(test)]
1222mod tests {
1223    use dogwood_language::{
1224        Event, LoweredPolicySet, PolicySchema, ServiceSchema, TemporalEngine, Value,
1225    };
1226
1227    use super::{
1228        KEYED_STATE_MAGIC, KEYED_STATE_PARTITIONED, LeafStateTransferError, LocalTemporalEngine,
1229        PolicyId, composite_key, decode_keyed_state, encode_keyed_state,
1230        load_global_serialized_by_key, load_sharded_serialized_by_key, parse_leaf_origin,
1231        validate_leaf_monitor_count,
1232    };
1233
1234    const KEYED_LOAD_SCHEMA: &str = r#"
1235namespace Test {
1236  type LoginInput = { user: String };
1237  type LoginOutput = { result: Bool };
1238  type TransferInput = { user: String };
1239  entity Gateway;
1240  entity User;
1241  action "Login" appliesTo {
1242    principal: [User], resource: [Gateway],
1243    context: { input: LoginInput, output: LoginOutput }
1244  };
1245  action "Transfer" appliesTo {
1246    principal: [User], resource: [Gateway],
1247    context: { input: TransferInput }
1248  };
1249}
1250"#;
1251
1252    const KEYED_LOAD_POLICY: &str = r#"
1253permit (principal, action == Test::Action::"Transfer", resource)
1254when temporal {
1255    formerly within 24h Test::Action::"Login"::response{ output.result: true }
1256};
1257"#;
1258
1259    const TWO_LEAF_KEYED_LOAD_POLICY: &str = r#"
1260permit (principal, action == Test::Action::"Transfer", resource)
1261when temporal {
1262    formerly within 1h Test::Action::"Login"::response{ output.result: true }
1263};
1264
1265permit (principal, action == Test::Action::"Transfer", resource)
1266when temporal {
1267    formerly within 24h Test::Action::"Login"::response{ output.result: true }
1268};
1269"#;
1270
1271    fn keyed_load_engine(policy: &str, partitioned: bool) -> LocalTemporalEngine {
1272        let schema = PolicySchema::from_cedarschema_str(KEYED_LOAD_SCHEMA).expect("schema builds");
1273        let service = ServiceSchema::builder()
1274            .build()
1275            .expect("default service builds");
1276        let lowered = LoweredPolicySet::from_str(policy, &service, &schema).expect("policy lowers");
1277        let leaves: Vec<_> = if partitioned {
1278            lowered.nonrelativized_temporal_fields().cloned().collect()
1279        } else {
1280            lowered.temporal_fields().cloned().collect()
1281        };
1282        let signatures = lowered.event_signatures().collect::<Vec<_>>();
1283        let mut engine = LocalTemporalEngine::new();
1284        if partitioned {
1285            engine.set_partition_keys(lowered.partition_keys());
1286        }
1287        engine
1288            .prepare(&leaves, lowered.cedar_schema(), &signatures)
1289            .expect("engine prepares");
1290        engine
1291    }
1292
1293    fn keyed_load_login(timestamp: i64, pin: &str) -> Event {
1294        Event::builder("Test::Action::Login", "response")
1295            .timestamp(timestamp)
1296            .principal(&format!("Test::User::\"{pin}\""))
1297            .resource("Test::Gateway::\"gw\"")
1298            .field("input", "user", Value::String(pin.to_string()))
1299            .field("output", "result", Value::Bool(true))
1300            .request_context("input", "user", Value::String(pin.to_string()))
1301            .build()
1302    }
1303
1304    fn keyed_load_probe(timestamp: i64, pin: &str) -> Event {
1305        Event::builder("Test::Action::Transfer", "request")
1306            .timestamp(timestamp)
1307            .principal(&format!("Test::User::\"{pin}\""))
1308            .resource("Test::Gateway::\"gw\"")
1309            .field("input", "user", Value::String(pin.to_string()))
1310            .request_context("input", "user", Value::String(pin.to_string()))
1311            .build()
1312    }
1313
1314    /// The id shapes the frontend actually emits parse to `(policy index, ordinal)`.
1315    #[test]
1316    fn leaf_origin_parses_the_frontend_id_shapes() {
1317        // Default lowering: `policy_{N}__temporal_{M}`.
1318        assert_eq!(parse_leaf_origin("policy_0__temporal_0"), Some((0, 0)));
1319        assert_eq!(parse_leaf_origin("policy_12__temporal_3"), Some((12, 3)));
1320        // Distincter-prefixed rule key (`{distincter}_{N}`): the policy index is the
1321        // trailing decimal run, whatever word precedes it.
1322        assert_eq!(parse_leaf_origin("batch_5__temporal_2"), Some((5, 2)));
1323    }
1324
1325    /// Shapes it cannot scope return `None`. The durable transplant guard turns
1326    /// that into a fail-closed rejection rather than mis-scoped history — so this
1327    /// pins the contract, and a future lowering change that broke it would fail
1328    /// here (targeted) instead of as a mysterious rebuild/recovery rejection.
1329    #[test]
1330    fn leaf_origin_rejects_shapes_it_cannot_scope() {
1331        assert_eq!(parse_leaf_origin("policy_0"), None); // no `__temporal_` seam
1332        assert_eq!(parse_leaf_origin("__temporal_0"), None); // empty rule key
1333        assert_eq!(parse_leaf_origin("policyX__temporal_0"), None); // no trailing decimal
1334        assert_eq!(parse_leaf_origin("policy_0__temporal_x"), None); // non-numeric ordinal
1335        assert_eq!(parse_leaf_origin("0__temporal_0"), None); // no distincter
1336        assert_eq!(parse_leaf_origin("bad-_0__temporal_0"), None); // invalid Cedar identifier
1337        assert_eq!(parse_leaf_origin("é_0__temporal_0"), None); // non-ASCII distincter
1338    }
1339
1340    #[test]
1341    fn composite_key_resolves_only_an_in_range_frontend_origin() {
1342        let ids = vec![PolicyId(7), PolicyId(u64::MAX)];
1343
1344        assert_eq!(
1345            composite_key(&ids, "policy_1__temporal_3", "content:with:colons"),
1346            format!("{}:3:content:with:colons", u64::MAX),
1347        );
1348        assert_eq!(
1349            composite_key(&ids, "policy_2__temporal_0", "leaf"),
1350            "?:leaf",
1351        );
1352        assert_eq!(composite_key(&ids, "malformed", "leaf"), "?:leaf");
1353    }
1354
1355    #[test]
1356    fn keyed_state_envelope_requires_the_destination_mode_and_fingerprint() {
1357        let global_body = b"global state".to_vec();
1358        let partitioned_body = b"partitioned state".to_vec();
1359        let fingerprint = b"callerPrincipal";
1360        let global = encode_keyed_state(global_body.clone(), None);
1361        let partitioned = encode_keyed_state(partitioned_body.clone(), Some(fingerprint));
1362
1363        assert_eq!(
1364            decode_keyed_state(&global, None),
1365            Some(global_body.as_slice())
1366        );
1367        assert_eq!(
1368            decode_keyed_state(&partitioned, Some(fingerprint)),
1369            Some(partitioned_body.as_slice())
1370        );
1371        assert_eq!(decode_keyed_state(&global, Some(fingerprint)), None);
1372        assert_eq!(decode_keyed_state(&partitioned, None), None);
1373        assert_eq!(decode_keyed_state(&partitioned, Some(b"sessionId")), None);
1374    }
1375
1376    #[test]
1377    fn keyed_state_envelope_rejects_malformed_headers() {
1378        let global = encode_keyed_state(Vec::new(), None);
1379        for end in 0..KEYED_STATE_MAGIC.len() + 1 {
1380            assert_eq!(decode_keyed_state(&global[..end], None), None);
1381        }
1382
1383        let mut bad_magic = global.clone();
1384        bad_magic[0] ^= 0xff;
1385        assert_eq!(decode_keyed_state(&bad_magic, None), None);
1386
1387        let mut unknown_mode = global;
1388        unknown_mode[KEYED_STATE_MAGIC.len()] = 0xff;
1389        assert_eq!(decode_keyed_state(&unknown_mode, None), None);
1390
1391        let mut impossible_length = Vec::from(KEYED_STATE_MAGIC.as_slice());
1392        impossible_length.push(KEYED_STATE_PARTITIONED);
1393        impossible_length.extend_from_slice(&u64::MAX.to_le_bytes());
1394        assert_eq!(
1395            decode_keyed_state(&impossible_length, Some(b"fingerprint")),
1396            None
1397        );
1398
1399        let partitioned = encode_keyed_state(Vec::new(), Some(b"fingerprint"));
1400        let missing_fingerprint_byte = partitioned.len() - 1;
1401        assert_eq!(
1402            decode_keyed_state(
1403                &partitioned[..missing_fingerprint_byte],
1404                Some(b"fingerprint"),
1405            ),
1406            None
1407        );
1408    }
1409
1410    #[test]
1411    fn leaf_monitor_count_mismatch_is_a_transfer_error() {
1412        assert_eq!(
1413            validate_leaf_monitor_count(1, 0),
1414            Err(LeafStateTransferError::LeafMonitorCountMismatch {
1415                leaves: 1,
1416                monitors: 0,
1417            })
1418        );
1419        assert_eq!(validate_leaf_monitor_count(2, 2), Ok(()));
1420    }
1421
1422    #[test]
1423    fn global_keyed_load_rejects_count_mismatch_before_mutation() {
1424        let keys = vec!["1:0:leaf".to_string()];
1425        let entries = vec![("1:0:leaf".to_string(), vec![0xff])];
1426        let mut monitors = Vec::new();
1427
1428        assert_eq!(
1429            load_global_serialized_by_key(&keys, &mut monitors, &entries),
1430            None,
1431        );
1432        assert!(monitors.is_empty());
1433    }
1434
1435    #[test]
1436    fn partitioned_keyed_load_rejects_count_mismatch_before_mutation() {
1437        let keys = vec!["1:0:leaf".to_string()];
1438        let entries = vec![("1:0:leaf".to_string(), vec![0xff])];
1439        let mut monitors = Vec::new();
1440
1441        assert_eq!(
1442            load_sharded_serialized_by_key(&keys, &mut monitors, &entries, b"fingerprint", 17,),
1443            None,
1444        );
1445        assert!(monitors.is_empty());
1446    }
1447
1448    #[test]
1449    fn public_global_keyed_load_rejects_count_mismatch_before_mutation() {
1450        let mut source = keyed_load_engine(TWO_LEAF_KEYED_LOAD_POLICY, false);
1451        source.observe(&keyed_load_login(20, "source"));
1452        let entries = source.save_keyed_state();
1453
1454        let mut destination = keyed_load_engine(TWO_LEAF_KEYED_LOAD_POLICY, false);
1455        destination.observe(&keyed_load_login(10, "destination"));
1456        destination.monitors.pop();
1457        let before = destination.save_keyed_state();
1458
1459        assert_eq!(
1460            destination.load_keyed_state(&entries),
1461            Err(LeafStateTransferError::LeafMonitorCountMismatch {
1462                leaves: 2,
1463                monitors: 1,
1464            })
1465        );
1466        assert_eq!(destination.save_keyed_state(), before);
1467    }
1468
1469    #[test]
1470    fn public_partitioned_keyed_load_rejects_count_mismatch_before_mutation() {
1471        let mut source = keyed_load_engine(TWO_LEAF_KEYED_LOAD_POLICY, true);
1472        source.observe(&keyed_load_login(20, "source"));
1473        let entries = source.save_keyed_state();
1474
1475        let mut destination = keyed_load_engine(TWO_LEAF_KEYED_LOAD_POLICY, true);
1476        destination.observe(&keyed_load_login(10, "destination"));
1477        destination.sharded.pop();
1478        let before = destination.save_keyed_state();
1479        let before_now = destination.global_now;
1480
1481        assert_eq!(
1482            destination.load_keyed_state(&entries),
1483            Err(LeafStateTransferError::LeafMonitorCountMismatch {
1484                leaves: 2,
1485                monitors: 1,
1486            })
1487        );
1488        assert_eq!(destination.save_keyed_state(), before);
1489        assert_eq!(destination.global_now, before_now);
1490    }
1491
1492    #[test]
1493    fn partitioned_keyed_load_uses_the_first_duplicate_entry() {
1494        let mut first = keyed_load_engine(KEYED_LOAD_POLICY, true);
1495        first.observe(&keyed_load_login(10, "alice"));
1496        let first_entry = first.save_keyed_state().pop().expect("one leaf");
1497
1498        let mut second = keyed_load_engine(KEYED_LOAD_POLICY, true);
1499        second.observe(&keyed_load_login(20, "bob"));
1500        let second_entry = second.save_keyed_state().pop().expect("one leaf");
1501        assert_eq!(first_entry.0, second_entry.0);
1502
1503        let mut destination = keyed_load_engine(KEYED_LOAD_POLICY, true);
1504        assert_eq!(
1505            destination.load_keyed_state(&[first_entry, second_entry]),
1506            Ok(1)
1507        );
1508        assert_eq!(destination.global_now, 10);
1509
1510        destination.observe(&keyed_load_probe(30, "alice"));
1511        assert!(
1512            destination
1513                .evaluate()
1514                .expect("alice evaluates")
1515                .values()
1516                .all(|value| *value)
1517        );
1518        destination.observe(&keyed_load_probe(40, "bob"));
1519        assert!(
1520            destination
1521                .evaluate()
1522                .expect("bob evaluates")
1523                .values()
1524                .all(|value| !value)
1525        );
1526    }
1527
1528    #[test]
1529    fn partitioned_keyed_load_max_folds_the_restored_and_destination_clocks() {
1530        let mut source = keyed_load_engine(KEYED_LOAD_POLICY, true);
1531        source.observe(&keyed_load_login(40, "source"));
1532        let entries = source.save_keyed_state();
1533
1534        let mut fresh_destination = keyed_load_engine(KEYED_LOAD_POLICY, true);
1535        assert_eq!(fresh_destination.load_keyed_state(&entries), Ok(1));
1536        assert_eq!(fresh_destination.global_now, 40);
1537
1538        let mut later_destination = keyed_load_engine(KEYED_LOAD_POLICY, true);
1539        later_destination.observe(&keyed_load_login(90, "destination"));
1540        assert_eq!(later_destination.load_keyed_state(&entries), Ok(1));
1541        assert_eq!(later_destination.global_now, 90);
1542    }
1543}