Skip to main content

dive_eval/
lazy.rs

1//! Values TLC keeps lazy: functions it holds as lambdas (`FcnLambdaValue`) and
2//! the set constructions it does not compute eagerly (`SetPredValue`,
3//! `SetCupValue`, `SetCapValue`, `SetDiffValue`, `UnionValue`).
4//!
5//! Lazy sets live inside [`Value`]s through `dive-value`'s [`DeferredSet`]
6//! hook. Lazy functions are evaluator values ([`crate::env::Ev::F`]): they can be
7//! applied, have a domain and take `EXCEPT`s without being computed, exactly
8//! as TLC's `FcnLambdaValue` (`tlc2/value/impl/FcnLambdaValue.java`).
9
10use std::fmt;
11use std::sync::{Arc, Mutex, OnceLock, PoisonError};
12
13use dive_ir::ExprId;
14use dive_value::{Ctx, DeferredKind, DeferredSet, Result as VResult, Value, ValueError, tlc};
15
16use crate::core::Core;
17use crate::env::{Env, Ev, St, Sv};
18use crate::error::EvalError;
19
20/// One bound group of a function constructor, with its evaluated domain.
21#[derive(Clone, Debug)]
22pub(crate) struct BoundVal {
23    pub(crate) slots: Vec<usize>,
24    pub(crate) tuple: bool,
25    pub(crate) domain: Value,
26}
27
28/// One pending `EXCEPT` of a lazy function (TLC's `ValueExcept`): the path,
29/// the position in it the function is at, and the new value.
30#[derive(Clone, Debug)]
31pub(crate) struct Except {
32    pub(crate) path: Arc<[Value]>,
33    pub(crate) idx: usize,
34    pub(crate) value: Ev,
35}
36
37impl Except {
38    pub(crate) fn current(&self) -> &Value {
39        &self.path[self.idx]
40    }
41
42    pub(crate) fn is_last(&self) -> bool {
43        self.idx + 1 == self.path.len()
44    }
45
46    pub(crate) fn advanced(&self) -> Self {
47        Self {
48            path: self.path.clone(),
49            idx: self.idx + 1,
50            value: self.value.clone(),
51        }
52    }
53}
54
55/// TLC's `FcnLambdaValue`: `[x \in S |-> e]` kept as a lambda, or a recursive
56/// function `f[x \in S] == e`.
57pub struct LazyFcn {
58    pub(crate) core: Arc<Core>,
59    /// The constructor node, for error locations.
60    pub(crate) node: ExprId,
61    /// Source attached to this actual receiver by diagnostic construction.
62    /// `CallStackTool`'s returned-lambda copy deliberately does not retain it.
63    pub(crate) source: Option<ExprId>,
64    pub(crate) bounds: Vec<BoundVal>,
65    pub(crate) body: ExprId,
66    pub(crate) env: Env,
67    pub(crate) st: St,
68    /// The slot that names the function inside its own body (recursive
69    /// functions).
70    pub(crate) rec_slot: Option<usize>,
71    pub(crate) excepts: Vec<Except>,
72    /// `fcnRcd`: the computed function, once materialized.
73    pub(crate) materialized: Materialized,
74}
75
76/// `fcnRcd`, kept per cache domain ([`crate::Host::expression_cache_domain`]):
77/// ordinary evaluation (domain 0) shares one value set at most once, as TLC
78/// does; evaluation under another domain (independent replay) keeps its own,
79/// so neither supplies the other's answer.
80#[derive(Debug, Default)]
81pub(crate) struct Materialized {
82    ordinary: OnceLock<Value>,
83    foreign: Mutex<Option<(u64, Value)>>,
84}
85
86impl Clone for Materialized {
87    fn clone(&self) -> Self {
88        Self {
89            ordinary: self.ordinary.clone(),
90            foreign: Mutex::new(
91                self.foreign
92                    .lock()
93                    .unwrap_or_else(PoisonError::into_inner)
94                    .clone(),
95            ),
96        }
97    }
98}
99
100impl Materialized {
101    /// The function materialized in cache `domain`, if any.
102    pub(crate) fn get(&self, domain: u64) -> Option<Value> {
103        if domain == 0 {
104            return self.ordinary.get().cloned();
105        }
106        let foreign = self.foreign.lock().unwrap_or_else(PoisonError::into_inner);
107        foreign
108            .as_ref()
109            .and_then(|(d, v)| (*d == domain).then(|| v.clone()))
110    }
111
112    /// Records the function materialized in cache `domain`.
113    pub(crate) fn set(&self, domain: u64, v: Value) {
114        if domain == 0 {
115            let _ = self.ordinary.set(v);
116        } else {
117            let mut foreign = self.foreign.lock().unwrap_or_else(PoisonError::into_inner);
118            if foreign.as_ref().is_none_or(|(d, _)| *d != domain) {
119                *foreign = Some((domain, v));
120            }
121        }
122    }
123}
124
125impl fmt::Debug for LazyFcn {
126    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
127        f.debug_struct("LazyFcn")
128            .field("node", &self.node)
129            .field("bounds", &self.bounds)
130            .field("excepts", &self.excepts.len())
131            .finish_non_exhaustive()
132    }
133}
134
135impl LazyFcn {
136    /// The number of arguments (`FcnParams.length()`).
137    pub(crate) fn arity(&self) -> usize {
138        self.bounds
139            .iter()
140            .map(|b| if b.tuple { 1 } else { b.slots.len() })
141            .sum()
142    }
143
144    /// A copy with one more `EXCEPT` (`FcnLambdaValue.takeExcept`).
145    pub(crate) fn with_except(self: &Arc<Self>, ex: Except) -> Arc<Self> {
146        let mut excepts = self.excepts.clone();
147        excepts.push(ex);
148        Arc::new(Self {
149            core: self.core.clone(),
150            node: self.node,
151            source: None,
152            bounds: self.bounds.clone(),
153            body: self.body,
154            env: self.env.clone(),
155            st: self.st.clone(),
156            rec_slot: self.rec_slot,
157            excepts,
158            materialized: Materialized::default(),
159        })
160    }
161
162    /// The environment for evaluating the body: the captured one, with the
163    /// recursive name bound to the function itself.
164    pub(crate) fn body_env(self: &Arc<Self>) -> Env {
165        let mut env = self.env.clone();
166        if let Some(slot) = self.rec_slot {
167            env.bind(slot, Sv::Fcn(self.clone()));
168        }
169        env
170    }
171
172    /// CallStackTool.eval's lambda copy: rebind the tool, not the source field.
173    pub(crate) fn diagnostic_copy(self: &Arc<Self>) -> Arc<Self> {
174        Arc::new(Self {
175            core: self.core.clone(),
176            node: self.node,
177            source: None,
178            bounds: self.bounds.clone(),
179            body: self.body,
180            env: self.env.clone(),
181            st: self.st.diagnostic(),
182            rec_slot: self.rec_slot,
183            excepts: self.excepts.clone(),
184            materialized: self.materialized.clone(),
185        })
186    }
187}
188
189// ---------------------------------------------------------------------------------
190// Deferred sets
191// ---------------------------------------------------------------------------------
192
193/// `{x \in S : P}` over a set TLC cannot reduce (`SetPredValue`).
194pub(crate) struct Filter {
195    pub(crate) core: Arc<Core>,
196    pub(crate) node: ExprId,
197    pub(crate) slots: Vec<usize>,
198    pub(crate) tuple: bool,
199    pub(crate) in_val: Value,
200    pub(crate) pred: ExprId,
201    pub(crate) env: Env,
202    pub(crate) st: St,
203}
204
205impl fmt::Debug for Filter {
206    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
207        f.debug_struct("Filter")
208            .field("node", &self.node)
209            .finish_non_exhaustive()
210    }
211}
212
213/// Converts an evaluation error into the value layer's error type, keeping
214/// it recoverable on the other side ([`crate::core::unwrap_deferred`]).
215pub(crate) fn to_value_error(e: EvalError) -> ValueError {
216    crate::error::stash(e)
217}
218
219impl DeferredSet for Filter {
220    fn kind(&self) -> DeferredKind {
221        DeferredKind::Filter
222    }
223
224    fn elements(&self, _ctx: Ctx) -> VResult<Vec<Value>> {
225        self.core.filter_elements(self).map_err(to_value_error)
226    }
227
228    fn member(&self, elem: &Value, _ctx: Ctx) -> Option<VResult<bool>> {
229        Some(self.core.filter_member(self, elem).map_err(to_value_error))
230    }
231
232    fn key(&self) -> Vec<Value> {
233        vec![self.in_val.clone(), Value::Int(i64::from(self.pred.0))]
234    }
235
236    fn as_any(&self) -> Option<&dyn std::any::Any> {
237        Some(self)
238    }
239}
240
241/// `S \cup T`, `S \cap T`, `S \ T` of sets TLC keeps lazy.
242pub(crate) struct SetOp {
243    pub(crate) core: Arc<Core>,
244    pub(crate) kind: DeferredKind,
245    pub(crate) a: Value,
246    pub(crate) b: Value,
247}
248
249impl fmt::Debug for SetOp {
250    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
251        f.debug_struct("SetOp")
252            .field("kind", &self.kind)
253            .finish_non_exhaustive()
254    }
255}
256
257/// The operand visited by TLC's `SetPredValue.deepNormalize` method.
258///
259/// Only evaluator-owned filters are recognized. Direct
260/// [`std::any::Any`] downcasts establish that authority without calling any
261/// provider method, evaluating a predicate, or enumerating a set. The returned
262/// operand is the bound set; the predicate and captured environment are not
263/// visited. Lazy set operations are not admitted here because their additional
264/// materialized-cache normalization contract is separate.
265/// Unknown providers return `None` and must not be assumed safe to normalize.
266#[must_use]
267pub fn deferred_filter_normalization_operand(provider: &dyn DeferredSet) -> Option<&Value> {
268    let any: &dyn std::any::Any = provider;
269    if let Some(filter) = any.downcast_ref::<Filter>() {
270        Some(&filter.in_val)
271    } else {
272        None
273    }
274}
275
276impl DeferredSet for SetOp {
277    fn kind(&self) -> DeferredKind {
278        self.kind
279    }
280
281    fn elements(&self, _ctx: Ctx) -> VResult<Vec<Value>> {
282        self.core.setop_elements(self).map_err(to_value_error)
283    }
284
285    fn member(&self, elem: &Value, ctx: Ctx) -> Option<VResult<bool>> {
286        Some(match self.kind {
287            DeferredKind::Cup => tlc::member(elem, &self.a, ctx).and_then(|m| {
288                if m {
289                    Ok(true)
290                } else {
291                    tlc::member(elem, &self.b, ctx)
292                }
293            }),
294            DeferredKind::Cap => tlc::member(elem, &self.a, ctx).and_then(|m| {
295                if m {
296                    tlc::member(elem, &self.b, ctx)
297                } else {
298                    Ok(false)
299                }
300            }),
301            DeferredKind::Diff => tlc::member(elem, &self.a, ctx).and_then(|m| {
302                if m {
303                    tlc::member(elem, &self.b, ctx).map(|n| !n)
304                } else {
305                    Ok(false)
306                }
307            }),
308            DeferredKind::Union => self
309                .core
310                .union_member(&self.a, elem)
311                .map_err(to_value_error),
312            DeferredKind::Filter | DeferredKind::Map => Ok(false),
313        })
314    }
315
316    fn key(&self) -> Vec<Value> {
317        vec![self.a.clone(), self.b.clone()]
318    }
319
320    fn as_any(&self) -> Option<&dyn std::any::Any> {
321        Some(self)
322    }
323}
324
325#[cfg(test)]
326#[path = "recursive_tests.rs"]
327mod recursive_tests;