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
28pub 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#[derive(Default)]
51pub struct LocalTemporalEngine {
52 leaves: Vec<TemporalField>,
54 policy_ids: Vec<PolicyId>,
63 latest: Option<Event>,
70 tick_rate: TickRate,
74 monitors: Vec<Arc<incremental::Monitor>>,
87 agg_memo_disabled: bool,
91 partition_keys: Vec<dogwood_language::PartitionKey>,
96 sharded: Vec<partition::ShardedMonitor>,
98 last_pin: Option<String>,
100 partition_keys_fingerprint_cached: Vec<u8>,
103 global_now: i64,
109 dropper: Option<sync::mpsc::Sender<incremental::Monitor>>,
112 verdicts_computed: u64,
114 leaf_map: DecisionLeafMap,
116 slicing_disabled: bool,
118}
119
120impl LocalTemporalEngine {
121 pub fn new() -> Self {
125 Self::default()
126 }
127
128 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 fn prepare(
144 &mut self,
145 leaves: &[TemporalField],
146 schema: &Schema,
147 _events: &[EventSignature],
148 ) -> Result<(), Error> {
149 self.leaves = leaves.to_vec();
150 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 self.sharded.clear();
177 self.monitors.clear();
178 self.global_now = i64::MIN;
179 self.last_pin = None;
180 self.latest = None;
181 self.policy_ids.clear();
185 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 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 for m in self.monitors.iter_mut() {
232 Arc::make_mut(m).step(event);
233 }
234 self.latest = Some(event.clone());
235 }
236
237 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 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 fn set_partition_keys(&mut self, keys: &[dogwood_language::PartitionKey]) {
259 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
276fn 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#[derive(Clone, Copy, Debug)]
494enum Plan<'a> {
495 All,
496 Only(&'a std::collections::BTreeSet<String>),
497}
498
499impl LocalTemporalEngine {
500 fn evaluate_leaves(&mut self, plan: Plan<'_>) -> Result<TemporalBindings, String> {
502 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 .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 #[doc(hidden)]
547 pub fn verdicts_computed(&self) -> u64 {
548 self.verdicts_computed
549 }
550
551 #[doc(hidden)]
556 pub fn disable_slicing(&mut self) {
557 self.slicing_disabled = true;
558 self.leaf_map = DecisionLeafMap::default();
559 }
560
561 #[doc(hidden)]
563 pub fn leaf_map_entries(&self) -> usize {
564 self.leaf_map.entry_count()
565 }
566
567 #[doc(hidden)]
569 pub fn unresolved_action_scopes(&self) -> Vec<(String, &'static str)> {
570 self.leaf_map.unresolved().to_vec()
571 }
572
573 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 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 fn state_fingerprint(&self) -> Vec<u8> {
614 let mut out = Vec::new();
615 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 #[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 #[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 #[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 #[doc(hidden)]
693 pub fn is_partitioned(&self) -> bool {
694 !self.partition_keys.is_empty()
695 }
696
697 #[doc(hidden)]
699 pub fn shard_count(&self) -> usize {
700 self.sharded.iter().map(|sm| sm.shard_count()).sum()
701 }
702
703 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 #[doc(hidden)]
722 pub fn maintain_all(&mut self) {
723 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 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 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 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 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 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 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 pub fn step_monitors(&mut self, event: &Event) {
896 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 pub fn set_policy_ids(&mut self, ids: &[PolicyId]) {
924 self.policy_ids = ids.to_vec();
925 }
926
927 pub fn share_leaf_state(&self) -> Result<Vec<(String, LeafState)>, LeafStateTransferError> {
937 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 pub fn adopt_leaf_state(
962 &mut self,
963 entries: &[(String, LeafState)],
964 ) -> Result<usize, LeafStateTransferError> {
965 self.validate_leaf_state_transfer()?;
969 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 pub fn save_keyed_state(&self) -> Vec<(String, Vec<u8>)> {
1004 if !self.partition_keys.is_empty() {
1005 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 pub fn load_keyed_state(
1047 &mut self,
1048 entries: &[(String, Vec<u8>)],
1049 ) -> Result<usize, LeafStateTransferError> {
1050 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 pub fn leaf_keys(&self) -> Vec<String> {
1086 self.leaves.iter().map(leaf_key).collect()
1087 }
1088
1089 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#[doc(hidden)]
1131pub fn parse_leaf_origin(id: &str) -> Option<(usize, usize)> {
1132 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#[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#[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#[derive(Debug, Clone, PartialEq, Eq)]
1177pub enum LeafStateTransferError {
1178 PartitionedEngine,
1180 LeafMonitorCountMismatch {
1182 leaves: usize,
1184 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 #[test]
1316 fn leaf_origin_parses_the_frontend_id_shapes() {
1317 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 assert_eq!(parse_leaf_origin("batch_5__temporal_2"), Some((5, 2)));
1323 }
1324
1325 #[test]
1330 fn leaf_origin_rejects_shapes_it_cannot_scope() {
1331 assert_eq!(parse_leaf_origin("policy_0"), None); assert_eq!(parse_leaf_origin("__temporal_0"), None); assert_eq!(parse_leaf_origin("policyX__temporal_0"), None); assert_eq!(parse_leaf_origin("policy_0__temporal_x"), None); assert_eq!(parse_leaf_origin("0__temporal_0"), None); assert_eq!(parse_leaf_origin("bad-_0__temporal_0"), None); assert_eq!(parse_leaf_origin("é_0__temporal_0"), None); }
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}