use std::sync::{Arc, Mutex, PoisonError};
use dive_ir::{BuiltinOp, ConstId, DeclId, DefId, ExprId, StdOp};
use dive_value::Value;
use crate::lazy::LazyFcn;
pub(crate) mod control {
pub(crate) const KEEP_LAZY: u8 = 1;
pub(crate) const PRIMED: u8 = 1 << 1;
pub(crate) const ENABLED: u8 = 1 << 2;
pub(crate) const INIT: u8 = 1 << 3;
pub(crate) const CONST: u8 = 1 << 4;
pub(crate) const DIAGNOSTIC: u8 = 1 << 5;
pub(crate) const PRECOMPUTE: u8 = 1 << 6;
pub(crate) const CLEAR: u8 = 0;
pub(crate) fn equivalent(a: u8, b: u8) -> bool {
let mask = !(KEEP_LAZY | INIT | CONST | DIAGNOSTIC);
a & mask == b & mask
}
}
#[derive(Clone, Debug, Default)]
pub enum StateRef {
Null,
#[default]
Empty,
Vals(Arc<[Option<Value>]>),
Named(Arc<crate::NamedState>),
}
impl StateRef {
pub(crate) fn includes(&self, cached: &Self) -> bool {
match (self, cached) {
(_, Self::Null | Self::Empty) => true,
(Self::Vals(s), Self::Vals(c)) => {
Arc::ptr_eq(s, c)
|| c.iter().enumerate().all(|(i, cv)| {
cv.as_ref()
.is_none_or(|cv| s.get(i).and_then(Option::as_ref) == Some(cv))
})
}
(Self::Named(s), Self::Named(c)) => {
std::sync::Weak::ptr_eq(&s.context, &c.context)
&& (Arc::ptr_eq(s, c)
|| s.context.upgrade().is_some_and(|core| {
core.ir.vars().iter().all(|decl| {
let name = core.ir.decl(*decl).name.as_str();
c.get(name).is_none_or(|value| s.get(name) == Some(value))
})
}))
}
(Self::Null | Self::Empty, Self::Vals(c)) => c.iter().all(Option::is_none),
_ => false,
}
}
}
#[derive(Clone, Debug, Default)]
pub struct St {
pub s0: StateRef,
pub s1: StateRef,
pub(crate) control: u8,
}
impl St {
#[must_use]
pub fn diagnostic(&self) -> Self {
self.with_control(self.control | control::DIAGNOSTIC)
}
#[must_use]
pub fn constant() -> Self {
Self {
s0: StateRef::Empty,
s1: StateRef::Empty,
control: control::CONST,
}
}
#[must_use]
pub fn empty() -> Self {
Self {
s0: StateRef::Empty,
s1: StateRef::Empty,
control: control::CLEAR,
}
}
#[must_use]
pub fn state(state: Arc<[Option<Value>]>) -> Self {
Self {
s0: StateRef::Vals(state),
s1: StateRef::Empty,
control: control::CLEAR,
}
}
#[must_use]
pub fn initial(state: Arc<[Option<Value>]>) -> Self {
Self {
control: control::INIT,
..Self::state(state)
}
}
#[must_use]
pub fn action(s0: Arc<[Option<Value>]>, s1: Arc<[Option<Value>]>) -> Self {
Self {
s0: StateRef::Vals(s0),
s1: StateRef::Vals(s1),
control: control::CLEAR,
}
}
#[must_use]
pub fn enabled_candidate(&self, successor: Arc<crate::NamedState>) -> Self {
Self {
s1: StateRef::Named(successor),
control: control::ENABLED,
..self.clone()
}
}
#[must_use]
pub fn enabled_current(&self) -> Self {
Self {
s1: StateRef::Empty,
control: control::ENABLED,
..self.clone()
}
}
#[must_use]
pub fn primed_successor(&self) -> Self {
Self {
s0: self.s1.clone(),
s1: StateRef::Null,
control: Self::primed_if_enabled(self.control),
}
}
pub(crate) fn with_control(&self, control: u8) -> Self {
Self {
control,
..self.clone()
}
}
pub(crate) fn keep_lazy(&self) -> Self {
self.with_control(self.control | control::KEEP_LAZY)
}
pub(crate) fn is(&self, flag: u8) -> bool {
self.control & flag != 0
}
pub(crate) fn primed_if_enabled(control: u8) -> u8 {
if control & control::ENABLED != 0 {
control | control::PRIMED
} else {
control
}
}
}
#[derive(Clone, Debug)]
pub enum Ev {
V(Value),
F(Arc<LazyFcn>),
}
impl From<Value> for Ev {
fn from(v: Value) -> Self {
Self::V(v)
}
}
#[derive(Clone, Debug)]
pub(crate) enum OpVal {
Def {
def: DefId,
parent: Option<Arc<Frame>>,
dynamic: Option<Dyn>,
},
Std(StdOp),
Builtin(BuiltinOp),
Const(ConstId),
Unbound(Arc<str>),
}
#[derive(Clone, Debug, Default)]
pub(crate) enum Sv {
#[default]
Unset,
Val(Value),
AnalysisBound,
AnalysisConstant,
Fcn(Arc<LazyFcn>),
Thunk(Arc<Thunk>),
Op(Box<OpVal>),
}
impl Sv {
pub(crate) fn op(op: OpVal) -> Self {
Self::Op(Box::new(op))
}
}
impl From<Ev> for Sv {
fn from(ev: Ev) -> Self {
match ev {
Ev::V(v) => Self::Val(v),
Ev::F(f) => Self::Fcn(f),
}
}
}
const _: () = assert!(std::mem::size_of::<Sv>() <= 24);
const INLINE_SLOTS: usize = 4;
#[derive(Clone, Debug)]
pub(crate) enum Slots {
Inline { len: u8, items: [Sv; INLINE_SLOTS] },
Heap(Vec<Sv>),
}
impl Slots {
fn unset(n: usize) -> Self {
match u8::try_from(n) {
Ok(len) if n <= INLINE_SLOTS => Self::Inline {
len,
items: Default::default(),
},
_ => Self::Heap(vec![Sv::Unset; n]),
}
}
fn ensure_len(&mut self, n: usize) {
if n <= self.len() {
return;
}
match self {
Self::Inline { len, .. } if n <= INLINE_SLOTS => {
*len = u8::try_from(n).unwrap_or(u8::MAX);
}
Self::Inline { len, items } => {
let mut v: Vec<Sv> = items[..usize::from(*len)]
.iter_mut()
.map(std::mem::take)
.collect();
v.resize(n, Sv::Unset);
*self = Self::Heap(v);
}
Self::Heap(v) => v.resize(n, Sv::Unset),
}
}
}
impl std::ops::Deref for Slots {
type Target = [Sv];
fn deref(&self) -> &[Sv] {
match self {
Self::Inline { len, items } => &items[..usize::from(*len)],
Self::Heap(v) => v,
}
}
}
impl std::ops::DerefMut for Slots {
fn deref_mut(&mut self) -> &mut [Sv] {
match self {
Self::Inline { len, items } => &mut items[..usize::from(*len)],
Self::Heap(v) => v,
}
}
}
impl<'a> IntoIterator for &'a Slots {
type Item = &'a Sv;
type IntoIter = std::slice::Iter<'a, Sv>;
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
#[derive(Clone, Debug)]
pub(crate) struct Frame {
pub(crate) def: DefId,
pub(crate) depth: u32,
pub(crate) slots: Slots,
pub(crate) parent: Option<Arc<Frame>>,
}
#[derive(Debug)]
pub(crate) struct SubstLink {
pub(crate) decl: DeclId,
pub(crate) val: Sv,
pub(crate) depth: usize,
pub(crate) next: Option<Arc<SubstLink>>,
}
#[derive(Clone, Debug, Default)]
pub(crate) struct Dyn {
pub(crate) subst: Option<Arc<SubstLink>>,
pub(crate) at: Option<Value>,
pub(crate) cut: Option<usize>,
}
impl Dyn {
pub(crate) fn lookup(&self, decl: DeclId) -> Option<&Sv> {
self.lookup_cut(decl, false)
}
pub(crate) fn lookup_cut(&self, decl: DeclId, cutoff: bool) -> Option<&Sv> {
let floor = if cutoff { self.cut.unwrap_or(0) } else { 0 };
let mut cur = self.subst.as_deref();
while let Some(link) = cur {
if link.depth <= floor {
return None;
}
if link.decl == decl {
return Some(&link.val);
}
cur = link.next.as_deref();
}
None
}
pub(crate) fn push(&mut self, decl: DeclId, val: Sv) {
let next = self.subst.take();
let depth = next.as_ref().map_or(0, |l| l.depth) + 1;
self.subst = Some(Arc::new(SubstLink {
decl,
val,
depth,
next,
}));
}
pub(crate) fn branch(&mut self) {
self.cut = Some(self.subst.as_ref().map_or(0, |l| l.depth));
}
}
#[derive(Clone, Debug)]
pub(crate) struct Env {
pub(crate) frame: Arc<Frame>,
pub(crate) dynamic: Dyn,
}
impl Env {
pub(crate) fn new(
def: DefId,
depth: u32,
slots: usize,
parent: Option<Arc<Frame>>,
dynamic: Dyn,
) -> Self {
Self {
frame: Arc::new(Frame {
def,
depth,
slots: Slots::unset(slots),
parent,
}),
dynamic,
}
}
pub(crate) fn bind(&mut self, slot: usize, v: Sv) {
let frame = Arc::make_mut(&mut self.frame);
frame.slots.ensure_len(slot + 1);
if let Some(target) = frame.slots.get_mut(slot) {
*target = v;
}
}
pub(crate) fn frame_up(&self, up: u32) -> Option<&Arc<Frame>> {
let mut f = &self.frame;
for _ in 0..up {
f = f.parent.as_ref()?;
}
Some(f)
}
pub(crate) fn frame_at_depth(&self, depth: u32) -> Option<&Arc<Frame>> {
let mut f = &self.frame;
while f.depth > depth {
f = f.parent.as_ref()?;
}
(f.depth == depth).then_some(f)
}
}
#[derive(Debug)]
pub(crate) struct Cached {
pub(crate) val: Ev,
pub(crate) s0: StateRef,
pub(crate) s1: StateRef,
pub(crate) control: u8,
pub(crate) domain: u64,
}
#[derive(Debug)]
pub(crate) struct Thunk {
pub(crate) expr: ExprId,
pub(crate) env: Env,
pub(crate) cachable: bool,
pub(crate) cache: Mutex<Option<Cached>>,
foreign: Mutex<Option<Cached>>,
}
impl Thunk {
pub(crate) fn stored_caches(&self) -> [Option<(Ev, StateRef, StateRef)>; 2] {
let snapshot = |slot: &Mutex<Option<Cached>>| {
slot.lock()
.unwrap_or_else(PoisonError::into_inner)
.as_ref()
.map(|cached| (cached.val.clone(), cached.s0.clone(), cached.s1.clone()))
};
[snapshot(&self.cache), snapshot(&self.foreign)]
}
pub(crate) fn new(expr: ExprId, env: Env, cachable: bool) -> Arc<Self> {
Arc::new(Self {
expr,
env,
cachable,
cache: Mutex::new(None),
foreign: Mutex::new(None),
})
}
fn slot(&self, domain: u64) -> &Mutex<Option<Cached>> {
if domain == 0 {
&self.cache
} else {
&self.foreign
}
}
pub(crate) fn cached(&self, st: &St, domain: u64) -> Option<Ev> {
if !self.cachable {
return None;
}
let cache = self
.slot(domain)
.lock()
.unwrap_or_else(PoisonError::into_inner);
let c = cache.as_ref()?;
(c.domain == domain
&& st.s0.includes(&c.s0)
&& st.s1.includes(&c.s1)
&& control::equivalent(st.control, c.control))
.then(|| c.val.clone())
}
pub(crate) fn store(&self, st: &St, val: &Ev, domain: u64) {
if !self.cachable {
return;
}
let mut cache = self
.slot(domain)
.lock()
.unwrap_or_else(PoisonError::into_inner);
*cache = Some(Cached {
val: val.clone(),
s0: st.s0.clone(),
s1: st.s1.clone(),
control: st.control,
domain,
});
}
}
pub(crate) fn shares_side_effects(ir: &dive_ir::Ir, env: &Env) -> bool {
captures_with_effects(ir, env, dive_ir::Effects::IMPURE, false, None)
}
pub(crate) fn filter_has_unproved_captures(
ir: &dive_ir::Ir,
env: &Env,
forbidden: dive_ir::Effects,
) -> bool {
captures_with_effects(ir, env, forbidden, true, None)
}
pub(crate) fn scope_has_effects(
ir: &dive_ir::Ir,
env: &Env,
callable_effects: &dyn Fn(&OpVal) -> bool,
) -> bool {
captures_with_effects(
ir,
env,
dive_ir::Effects::IMPURE.union(dive_ir::Effects::LIVE_TLCGET),
false,
Some(callable_effects),
)
}
fn captures_with_effects(
ir: &dive_ir::Ir,
env: &Env,
forbidden: dive_ir::Effects,
reject_operators: bool,
callable_effects: Option<&dyn Fn(&OpVal) -> bool>,
) -> bool {
let mut seen = std::collections::HashSet::new();
let mut frames: Vec<&Arc<Frame>> = vec![&env.frame];
let mut svs: Vec<&Sv> = Vec::new();
let mut dyns: Vec<&Dyn> = vec![&env.dynamic];
let impure = |e: ExprId| {
ir.nodes()
.get(e.index())
.map_or(reject_operators, |n| n.effects.intersects(forbidden))
};
loop {
if let Some(f) = frames.pop() {
if seen.insert(Arc::as_ptr(f) as usize) {
svs.extend(f.slots.iter());
if let Some(p) = &f.parent {
frames.push(p);
}
}
} else if let Some(d) = dyns.pop() {
let mut cur = d.subst.as_deref();
while let Some(link) = cur {
if !seen.insert(std::ptr::from_ref(link) as usize) {
break;
}
svs.push(&link.val);
cur = link.next.as_deref();
}
} else if let Some(sv) = svs.pop() {
match sv {
Sv::Thunk(t) => {
if seen.insert(Arc::as_ptr(t) as usize) {
if (reject_operators || callable_effects.is_some() || t.cachable)
&& impure(t.expr)
{
return true;
}
frames.push(&t.env.frame);
dyns.push(&t.env.dynamic);
}
}
Sv::Fcn(f) => {
if seen.insert(Arc::as_ptr(f) as usize) {
if impure(f.body) {
return true;
}
frames.push(&f.env.frame);
dyns.push(&f.env.dynamic);
}
}
Sv::Op(op)
if reject_operators || callable_effects.is_some_and(|effects| effects(op)) =>
{
return true;
}
Sv::Op(op) => {
if let OpVal::Def {
parent, dynamic, ..
} = &**op
{
if let Some(p) = parent {
frames.push(p);
}
if let Some(d) = dynamic {
dyns.push(d);
}
}
}
Sv::Unset | Sv::Val(_) | Sv::AnalysisBound | Sv::AnalysisConstant => {}
}
} else {
return false;
}
}
}
#[cfg(test)]
mod tests {
use super::{INLINE_SLOTS, Slots, Sv};
use dive_value::Value;
#[test]
fn slots_grow_from_inline_to_heap_keeping_bindings() {
let mut slots = Slots::unset(1);
assert!(matches!(slots, Slots::Inline { len: 1, .. }));
slots[0] = Sv::Val(Value::Int(7));
slots.ensure_len(INLINE_SLOTS);
assert!(matches!(slots, Slots::Inline { .. }));
assert_eq!(slots.len(), INLINE_SLOTS);
slots.ensure_len(INLINE_SLOTS + 2);
assert!(matches!(slots, Slots::Heap(_)));
assert_eq!(slots.len(), INLINE_SLOTS + 2);
assert!(matches!(&slots[0], Sv::Val(Value::Int(7))));
assert!(slots[1..].iter().all(|s| matches!(s, Sv::Unset)));
slots.ensure_len(1);
assert_eq!(slots.len(), INLINE_SLOTS + 2);
assert!(matches!(Slots::unset(INLINE_SLOTS + 1), Slots::Heap(_)));
}
}