1use std::sync::{Arc, Mutex, PoisonError};
16
17use dive_ir::{BuiltinOp, ConstId, DeclId, DefId, ExprId, StdOp};
18use dive_value::Value;
19
20use crate::lazy::LazyFcn;
21
22pub(crate) mod control {
24 pub(crate) const KEEP_LAZY: u8 = 1;
26 pub(crate) const PRIMED: u8 = 1 << 1;
28 pub(crate) const ENABLED: u8 = 1 << 2;
30 pub(crate) const INIT: u8 = 1 << 3;
32 pub(crate) const CONST: u8 = 1 << 4;
34 pub(crate) const DIAGNOSTIC: u8 = 1 << 5;
37 pub(crate) const PRECOMPUTE: u8 = 1 << 6;
40 pub(crate) const CLEAR: u8 = 0;
42
43 pub(crate) fn equivalent(a: u8, b: u8) -> bool {
46 let mask = !(KEEP_LAZY | INIT | CONST | DIAGNOSTIC);
47 a & mask == b & mask
48 }
49}
50
51#[derive(Clone, Debug, Default)]
56pub enum StateRef {
57 Null,
59 #[default]
61 Empty,
62 Vals(Arc<[Option<Value>]>),
64 Named(Arc<crate::NamedState>),
66}
67
68impl StateRef {
69 pub(crate) fn includes(&self, cached: &Self) -> bool {
74 match (self, cached) {
75 (_, Self::Null | Self::Empty) => true,
76 (Self::Vals(s), Self::Vals(c)) => {
77 Arc::ptr_eq(s, c)
78 || c.iter().enumerate().all(|(i, cv)| {
79 cv.as_ref()
80 .is_none_or(|cv| s.get(i).and_then(Option::as_ref) == Some(cv))
81 })
82 }
83 (Self::Named(s), Self::Named(c)) => {
84 std::sync::Weak::ptr_eq(&s.context, &c.context)
85 && (Arc::ptr_eq(s, c)
86 || s.context.upgrade().is_some_and(|core| {
87 core.ir.vars().iter().all(|decl| {
88 let name = core.ir.decl(*decl).name.as_str();
89 c.get(name).is_none_or(|value| s.get(name) == Some(value))
90 })
91 }))
92 }
93 (Self::Null | Self::Empty, Self::Vals(c)) => c.iter().all(Option::is_none),
94 _ => false,
95 }
96 }
97}
98
99#[derive(Clone, Debug, Default)]
102pub struct St {
103 pub s0: StateRef,
105 pub s1: StateRef,
107 pub(crate) control: u8,
108}
109
110impl St {
111 #[must_use]
116 pub fn diagnostic(&self) -> Self {
117 self.with_control(self.control | control::DIAGNOSTIC)
118 }
119
120 #[must_use]
123 pub fn constant() -> Self {
124 Self {
125 s0: StateRef::Empty,
126 s1: StateRef::Empty,
127 control: control::CONST,
128 }
129 }
130
131 #[must_use]
135 pub fn empty() -> Self {
136 Self {
137 s0: StateRef::Empty,
138 s1: StateRef::Empty,
139 control: control::CLEAR,
140 }
141 }
142
143 #[must_use]
145 pub fn state(state: Arc<[Option<Value>]>) -> Self {
146 Self {
147 s0: StateRef::Vals(state),
148 s1: StateRef::Empty,
149 control: control::CLEAR,
150 }
151 }
152
153 #[must_use]
165 pub fn initial(state: Arc<[Option<Value>]>) -> Self {
166 Self {
167 control: control::INIT,
168 ..Self::state(state)
169 }
170 }
171
172 #[must_use]
174 pub fn action(s0: Arc<[Option<Value>]>, s1: Arc<[Option<Value>]>) -> Self {
175 Self {
176 s0: StateRef::Vals(s0),
177 s1: StateRef::Vals(s1),
178 control: control::CLEAR,
179 }
180 }
181
182 #[must_use]
185 pub fn enabled_candidate(&self, successor: Arc<crate::NamedState>) -> Self {
186 Self {
187 s1: StateRef::Named(successor),
188 control: control::ENABLED,
189 ..self.clone()
190 }
191 }
192
193 #[must_use]
195 pub fn enabled_current(&self) -> Self {
196 Self {
197 s1: StateRef::Empty,
198 control: control::ENABLED,
199 ..self.clone()
200 }
201 }
202
203 #[must_use]
206 pub fn primed_successor(&self) -> Self {
207 Self {
208 s0: self.s1.clone(),
209 s1: StateRef::Null,
210 control: Self::primed_if_enabled(self.control),
211 }
212 }
213
214 pub(crate) fn with_control(&self, control: u8) -> Self {
215 Self {
216 control,
217 ..self.clone()
218 }
219 }
220
221 pub(crate) fn keep_lazy(&self) -> Self {
222 self.with_control(self.control | control::KEEP_LAZY)
223 }
224
225 pub(crate) fn is(&self, flag: u8) -> bool {
226 self.control & flag != 0
227 }
228
229 pub(crate) fn primed_if_enabled(control: u8) -> u8 {
231 if control & control::ENABLED != 0 {
232 control | control::PRIMED
233 } else {
234 control
235 }
236 }
237}
238
239#[derive(Clone, Debug)]
242pub enum Ev {
243 V(Value),
245 F(Arc<LazyFcn>),
247}
248
249impl From<Value> for Ev {
250 fn from(v: Value) -> Self {
251 Self::V(v)
252 }
253}
254
255#[derive(Clone, Debug)]
258pub(crate) enum OpVal {
259 Def {
262 def: DefId,
263 parent: Option<Arc<Frame>>,
264 dynamic: Option<Dyn>,
267 },
268 Std(StdOp),
270 Builtin(BuiltinOp),
272 Const(ConstId),
274 Unbound(Arc<str>),
276}
277
278#[derive(Clone, Debug, Default)]
280pub(crate) enum Sv {
281 #[default]
283 Unset,
284 Val(Value),
286 AnalysisBound,
288 AnalysisConstant,
291 Fcn(Arc<LazyFcn>),
293 Thunk(Arc<Thunk>),
295 Op(Box<OpVal>),
297}
298
299impl Sv {
300 pub(crate) fn op(op: OpVal) -> Self {
302 Self::Op(Box::new(op))
303 }
304}
305
306impl From<Ev> for Sv {
307 fn from(ev: Ev) -> Self {
308 match ev {
309 Ev::V(v) => Self::Val(v),
310 Ev::F(f) => Self::Fcn(f),
311 }
312 }
313}
314
315const _: () = assert!(std::mem::size_of::<Sv>() <= 24);
318
319const INLINE_SLOTS: usize = 4;
323
324#[derive(Clone, Debug)]
327pub(crate) enum Slots {
328 Inline { len: u8, items: [Sv; INLINE_SLOTS] },
329 Heap(Vec<Sv>),
330}
331
332impl Slots {
333 fn unset(n: usize) -> Self {
335 match u8::try_from(n) {
336 Ok(len) if n <= INLINE_SLOTS => Self::Inline {
337 len,
338 items: Default::default(),
339 },
340 _ => Self::Heap(vec![Sv::Unset; n]),
341 }
342 }
343
344 fn ensure_len(&mut self, n: usize) {
346 if n <= self.len() {
347 return;
348 }
349 match self {
350 Self::Inline { len, .. } if n <= INLINE_SLOTS => {
351 *len = u8::try_from(n).unwrap_or(u8::MAX);
353 }
354 Self::Inline { len, items } => {
355 let mut v: Vec<Sv> = items[..usize::from(*len)]
356 .iter_mut()
357 .map(std::mem::take)
358 .collect();
359 v.resize(n, Sv::Unset);
360 *self = Self::Heap(v);
361 }
362 Self::Heap(v) => v.resize(n, Sv::Unset),
363 }
364 }
365}
366
367impl std::ops::Deref for Slots {
368 type Target = [Sv];
369 fn deref(&self) -> &[Sv] {
370 match self {
371 Self::Inline { len, items } => &items[..usize::from(*len)],
372 Self::Heap(v) => v,
373 }
374 }
375}
376
377impl std::ops::DerefMut for Slots {
378 fn deref_mut(&mut self) -> &mut [Sv] {
379 match self {
380 Self::Inline { len, items } => &mut items[..usize::from(*len)],
381 Self::Heap(v) => v,
382 }
383 }
384}
385
386impl<'a> IntoIterator for &'a Slots {
387 type Item = &'a Sv;
388 type IntoIter = std::slice::Iter<'a, Sv>;
389 fn into_iter(self) -> Self::IntoIter {
390 self.iter()
391 }
392}
393
394#[derive(Clone, Debug)]
396pub(crate) struct Frame {
397 pub(crate) def: DefId,
399 pub(crate) depth: u32,
401 pub(crate) slots: Slots,
402 pub(crate) parent: Option<Arc<Frame>>,
404}
405
406#[derive(Debug)]
408pub(crate) struct SubstLink {
409 pub(crate) decl: DeclId,
410 pub(crate) val: Sv,
411 pub(crate) depth: usize,
413 pub(crate) next: Option<Arc<SubstLink>>,
414}
415
416#[derive(Clone, Debug, Default)]
418pub(crate) struct Dyn {
419 pub(crate) subst: Option<Arc<SubstLink>>,
420 pub(crate) at: Option<Value>,
421 pub(crate) cut: Option<usize>,
426}
427
428impl Dyn {
429 pub(crate) fn lookup(&self, decl: DeclId) -> Option<&Sv> {
430 self.lookup_cut(decl, false)
431 }
432
433 pub(crate) fn lookup_cut(&self, decl: DeclId, cutoff: bool) -> Option<&Sv> {
435 let floor = if cutoff { self.cut.unwrap_or(0) } else { 0 };
436 let mut cur = self.subst.as_deref();
437 while let Some(link) = cur {
438 if link.depth <= floor {
439 return None;
440 }
441 if link.decl == decl {
442 return Some(&link.val);
443 }
444 cur = link.next.as_deref();
445 }
446 None
447 }
448
449 pub(crate) fn push(&mut self, decl: DeclId, val: Sv) {
451 let next = self.subst.take();
452 let depth = next.as_ref().map_or(0, |l| l.depth) + 1;
453 self.subst = Some(Arc::new(SubstLink {
454 decl,
455 val,
456 depth,
457 next,
458 }));
459 }
460
461 pub(crate) fn branch(&mut self) {
463 self.cut = Some(self.subst.as_ref().map_or(0, |l| l.depth));
464 }
465}
466
467#[derive(Clone, Debug)]
469pub(crate) struct Env {
470 pub(crate) frame: Arc<Frame>,
471 pub(crate) dynamic: Dyn,
472}
473
474impl Env {
475 pub(crate) fn new(
477 def: DefId,
478 depth: u32,
479 slots: usize,
480 parent: Option<Arc<Frame>>,
481 dynamic: Dyn,
482 ) -> Self {
483 Self {
484 frame: Arc::new(Frame {
485 def,
486 depth,
487 slots: Slots::unset(slots),
488 parent,
489 }),
490 dynamic,
491 }
492 }
493
494 pub(crate) fn bind(&mut self, slot: usize, v: Sv) {
496 let frame = Arc::make_mut(&mut self.frame);
497 frame.slots.ensure_len(slot + 1);
498 if let Some(target) = frame.slots.get_mut(slot) {
499 *target = v;
500 }
501 }
502
503 pub(crate) fn frame_up(&self, up: u32) -> Option<&Arc<Frame>> {
505 let mut f = &self.frame;
506 for _ in 0..up {
507 f = f.parent.as_ref()?;
508 }
509 Some(f)
510 }
511
512 pub(crate) fn frame_at_depth(&self, depth: u32) -> Option<&Arc<Frame>> {
514 let mut f = &self.frame;
515 while f.depth > depth {
516 f = f.parent.as_ref()?;
517 }
518 (f.depth == depth).then_some(f)
519 }
520}
521
522#[derive(Debug)]
524pub(crate) struct Cached {
525 pub(crate) val: Ev,
526 pub(crate) s0: StateRef,
527 pub(crate) s1: StateRef,
528 pub(crate) control: u8,
529 pub(crate) domain: u64,
531}
532
533#[derive(Debug)]
540pub(crate) struct Thunk {
541 pub(crate) expr: ExprId,
542 pub(crate) env: Env,
543 pub(crate) cachable: bool,
544 pub(crate) cache: Mutex<Option<Cached>>,
545 foreign: Mutex<Option<Cached>>,
546}
547
548impl Thunk {
549 pub(crate) fn stored_caches(&self) -> [Option<(Ev, StateRef, StateRef)>; 2] {
552 let snapshot = |slot: &Mutex<Option<Cached>>| {
553 slot.lock()
554 .unwrap_or_else(PoisonError::into_inner)
555 .as_ref()
556 .map(|cached| (cached.val.clone(), cached.s0.clone(), cached.s1.clone()))
557 };
558 [snapshot(&self.cache), snapshot(&self.foreign)]
559 }
560
561 pub(crate) fn new(expr: ExprId, env: Env, cachable: bool) -> Arc<Self> {
562 Arc::new(Self {
563 expr,
564 env,
565 cachable,
566 cache: Mutex::new(None),
567 foreign: Mutex::new(None),
568 })
569 }
570
571 fn slot(&self, domain: u64) -> &Mutex<Option<Cached>> {
572 if domain == 0 {
573 &self.cache
574 } else {
575 &self.foreign
576 }
577 }
578
579 pub(crate) fn cached(&self, st: &St, domain: u64) -> Option<Ev> {
581 if !self.cachable {
582 return None;
583 }
584 let cache = self
585 .slot(domain)
586 .lock()
587 .unwrap_or_else(PoisonError::into_inner);
588 let c = cache.as_ref()?;
589 (c.domain == domain
590 && st.s0.includes(&c.s0)
591 && st.s1.includes(&c.s1)
592 && control::equivalent(st.control, c.control))
593 .then(|| c.val.clone())
594 }
595
596 pub(crate) fn store(&self, st: &St, val: &Ev, domain: u64) {
598 if !self.cachable {
599 return;
600 }
601 let mut cache = self
602 .slot(domain)
603 .lock()
604 .unwrap_or_else(PoisonError::into_inner);
605 *cache = Some(Cached {
606 val: val.clone(),
607 s0: st.s0.clone(),
608 s1: st.s1.clone(),
609 control: st.control,
610 domain,
611 });
612 }
613}
614
615pub(crate) fn shares_side_effects(ir: &dive_ir::Ir, env: &Env) -> bool {
619 captures_with_effects(ir, env, dive_ir::Effects::IMPURE, false, None)
620}
621
622pub(crate) fn filter_has_unproved_captures(
626 ir: &dive_ir::Ir,
627 env: &Env,
628 forbidden: dive_ir::Effects,
629) -> bool {
630 captures_with_effects(ir, env, forbidden, true, None)
631}
632
633pub(crate) fn scope_has_effects(
636 ir: &dive_ir::Ir,
637 env: &Env,
638 callable_effects: &dyn Fn(&OpVal) -> bool,
639) -> bool {
640 captures_with_effects(
641 ir,
642 env,
643 dive_ir::Effects::IMPURE.union(dive_ir::Effects::LIVE_TLCGET),
644 false,
645 Some(callable_effects),
646 )
647}
648
649fn captures_with_effects(
650 ir: &dive_ir::Ir,
651 env: &Env,
652 forbidden: dive_ir::Effects,
653 reject_operators: bool,
654 callable_effects: Option<&dyn Fn(&OpVal) -> bool>,
655) -> bool {
656 let mut seen = std::collections::HashSet::new();
657 let mut frames: Vec<&Arc<Frame>> = vec![&env.frame];
658 let mut svs: Vec<&Sv> = Vec::new();
659 let mut dyns: Vec<&Dyn> = vec![&env.dynamic];
660 let impure = |e: ExprId| {
661 ir.nodes()
662 .get(e.index())
663 .map_or(reject_operators, |n| n.effects.intersects(forbidden))
664 };
665 loop {
666 if let Some(f) = frames.pop() {
667 if seen.insert(Arc::as_ptr(f) as usize) {
668 svs.extend(f.slots.iter());
669 if let Some(p) = &f.parent {
670 frames.push(p);
671 }
672 }
673 } else if let Some(d) = dyns.pop() {
674 let mut cur = d.subst.as_deref();
675 while let Some(link) = cur {
676 if !seen.insert(std::ptr::from_ref(link) as usize) {
677 break;
678 }
679 svs.push(&link.val);
680 cur = link.next.as_deref();
681 }
682 } else if let Some(sv) = svs.pop() {
683 match sv {
684 Sv::Thunk(t) => {
685 if seen.insert(Arc::as_ptr(t) as usize) {
686 if (reject_operators || callable_effects.is_some() || t.cachable)
687 && impure(t.expr)
688 {
689 return true;
690 }
691 frames.push(&t.env.frame);
692 dyns.push(&t.env.dynamic);
693 }
694 }
695 Sv::Fcn(f) => {
696 if seen.insert(Arc::as_ptr(f) as usize) {
697 if impure(f.body) {
698 return true;
699 }
700 frames.push(&f.env.frame);
701 dyns.push(&f.env.dynamic);
702 }
703 }
704 Sv::Op(op)
705 if reject_operators || callable_effects.is_some_and(|effects| effects(op)) =>
706 {
707 return true;
708 }
709 Sv::Op(op) => {
710 if let OpVal::Def {
711 parent, dynamic, ..
712 } = &**op
713 {
714 if let Some(p) = parent {
715 frames.push(p);
716 }
717 if let Some(d) = dynamic {
718 dyns.push(d);
719 }
720 }
721 }
722 Sv::Unset | Sv::Val(_) | Sv::AnalysisBound | Sv::AnalysisConstant => {}
723 }
724 } else {
725 return false;
726 }
727 }
728}
729
730#[cfg(test)]
731mod tests {
732 use super::{INLINE_SLOTS, Slots, Sv};
733 use dive_value::Value;
734
735 #[test]
736 fn slots_grow_from_inline_to_heap_keeping_bindings() {
737 let mut slots = Slots::unset(1);
738 assert!(matches!(slots, Slots::Inline { len: 1, .. }));
739 slots[0] = Sv::Val(Value::Int(7));
740 slots.ensure_len(INLINE_SLOTS);
741 assert!(matches!(slots, Slots::Inline { .. }));
742 assert_eq!(slots.len(), INLINE_SLOTS);
743 slots.ensure_len(INLINE_SLOTS + 2);
744 assert!(matches!(slots, Slots::Heap(_)));
745 assert_eq!(slots.len(), INLINE_SLOTS + 2);
746 assert!(matches!(&slots[0], Sv::Val(Value::Int(7))));
747 assert!(slots[1..].iter().all(|s| matches!(s, Sv::Unset)));
748 slots.ensure_len(1);
749 assert_eq!(slots.len(), INLINE_SLOTS + 2);
750 assert!(matches!(Slots::unset(INLINE_SLOTS + 1), Slots::Heap(_)));
751 }
752}