Skip to main content

dive_core/stdlib/
mod.rs

1//! Standard and CommunityModules operators of the core, by TLC's override
2//! table ([`dive_ir::StdOp`]).
3//!
4//! The compiler asks [`implements`] for a standard operator it does not
5//! compile itself and emits `Node::Lib`; the evaluator evaluates
6//! the arguments (normalized) and calls [`call`]. Semantics, error points
7//! and error classes are `dive-eval`'s (its `community` and `std`
8//! modules), which follow TLC's Java overrides. Where `dive-eval` refuses a case, so
9//! does the core.
10//!
11//! Every operator here is pure except `Print` and `PrintT` ([`effectful`]),
12//! whose calls the compiler never folds, memoizes or skips.
13
14use dive_ir::StdOp;
15
16use crate::eval::Machine;
17use crate::node::Kind;
18use crate::plan::{Code, P};
19use crate::{Error, Handle, TlcClass};
20
21mod bags;
22mod community;
23mod graphs;
24mod higher;
25mod tlc;
26
27/// Whether the core implements `op` here.
28#[must_use]
29pub fn implements(op: StdOp) -> bool {
30    deferred(op)
31        || bags::implements(op)
32        || tlc::implements(op)
33        || community::implements(op)
34        || graphs::implements(op)
35}
36
37/// Whether a call of `op` has an effect TLC performs once per evaluation
38/// (output, registers, randomness): such a call is never folded or
39/// memoized. Of the operators implemented here, `Print` and `PrintT`.
40#[must_use]
41pub fn effectful(op: StdOp) -> bool {
42    implements(op) && op.impure() && !deferred(op)
43}
44
45/// Whether `op` compiles to a call that refuses when it is evaluated, before
46/// its arguments are: TLC's trace introspection (`TLCExt!Trace`,
47/// `TLCExt!CounterExample`) and the `Json` and `IOUtils` operators, which
48/// the core does not reproduce. A specification often guards them behind a
49/// disjunct TLC evaluates only after a violation (to export the trace), so
50/// refusing at compile time would refuse runs that never reach them. The
51/// call never yields a value and performs no I/O, so it is neither an
52/// effect nor a value a fold or memo could keep.
53#[must_use]
54pub(crate) fn deferred(op: StdOp) -> bool {
55    matches!(op, StdOp::TlcExtTrace | StdOp::TlcExtCounterExample)
56        || (matches!(op.module(), "Json" | "IOUtils")
57            && !(bags::implements(op)
58                || tlc::implements(op)
59                || community::implements(op)
60                || graphs::implements(op)))
61}
62
63/// The refusal of an evaluated [`deferred`] call of `op`.
64#[must_use]
65pub(crate) fn deferred_refusal(op: StdOp) -> Error {
66    let what = if op.module() == "TLCExt" {
67        "trace introspection operators"
68    } else {
69        "Json and IOUtils operators"
70    };
71    refuse(
72        op,
73        &format!("evaluated; {what} are not implemented (M1 core)"),
74    )
75}
76
77/// Whether the core implements `op` here as an operator with operator
78/// arguments (`Node::LibHo`).
79#[must_use]
80pub fn higher_order(op: StdOp) -> bool {
81    higher::implements(op)
82}
83
84/// The arity of argument `i` of a higher-order operator when it is an
85/// operator argument; `None` for a value argument.
86#[must_use]
87pub fn op_arity(op: StdOp, i: usize) -> Option<usize> {
88    higher::op_arity(op, i)
89}
90
91/// Whether `op` takes its operator argument as TLC's `OpValue`, which TLC
92/// cannot apply when the operator's body is a constant: the compiler
93/// refuses such a call.
94#[must_use]
95pub fn takes_op_value(op: StdOp) -> bool {
96    higher::takes_op_value(op)
97}
98
99/// An operator argument, compiled: its parameters' slots and its body.
100#[derive(Clone, Copy, Debug)]
101pub struct OpFn<'a> {
102    code: &'a Code,
103    params: &'a [u32],
104    body: P,
105}
106
107impl<'a> OpFn<'a> {
108    /// The operator whose parameters are `params` and whose body is `body`.
109    #[must_use]
110    pub fn new(code: &'a Code, params: &'a [u32], body: P) -> Self {
111        Self { code, params, body }
112    }
113
114    /// Applies the operator to `args`, as TLC applies an operator argument
115    /// from a Java override: the parameters are bound to the values, the
116    /// body is evaluated (normalized), and the slots are restored.
117    ///
118    /// # Errors
119    /// The body's evaluation errors; internal for an arity mismatch.
120    pub fn apply(&self, m: &mut Machine, args: &[Handle]) -> Result<Handle, Error> {
121        if args.len() != self.params.len() {
122            return Err(Error::internal("an operator argument's arity"));
123        }
124        let saved: Vec<Handle> = self.params.iter().map(|&s| m.slot(s)).collect();
125        for (&s, &v) in self.params.iter().zip(args) {
126            m.set_slot(s, v);
127        }
128        let r = m.eval_norm(self.code, self.body);
129        for (&s, &v) in self.params.iter().zip(&saved) {
130            m.set_slot(s, v);
131        }
132        r
133    }
134}
135
136/// An argument of a higher-order operator at the call.
137#[derive(Clone, Copy, Debug)]
138pub enum Ho<'a> {
139    /// A normalized value.
140    Value(Handle),
141    /// An operator.
142    Op(OpFn<'a>),
143}
144
145/// Calls the higher-order operator `op`.
146///
147/// # Errors
148/// As [`call`].
149pub fn call_ho(m: &mut Machine, op: StdOp, args: &[Ho<'_>]) -> Result<Handle, Error> {
150    higher::call(m, op, args)
151}
152
153/// Calls `op` on normalized arguments.
154///
155/// # Errors
156/// TLC's evaluation error, with its class; `unsupported` for a case the
157/// core does not reproduce; internal for an operator not implemented here.
158pub fn call(m: &mut Machine, op: StdOp, args: &[Handle]) -> Result<Handle, Error> {
159    if deferred(op) {
160        return Err(deferred_refusal(op));
161    }
162    if bags::implements(op) {
163        return bags::call(m, op, args);
164    }
165    if tlc::implements(op) {
166        return tlc::call(m, op, args);
167    }
168    if community::implements(op) {
169        return community::call(m, op, args);
170    }
171    if graphs::implements(op) {
172        return graphs::call(m, op, args);
173    }
174    Err(Error::internal(format!(
175        "{} is not a core library operator",
176        op.qualified_name()
177    )))
178}
179
180/// The elements of a set TLC enumerates (`Enumerable`: not `Nat`, `Int`
181/// or `Seq(S)`, and finite); `None` for any other value.
182///
183/// # Errors
184/// `unsupported` for a set the core keeps lazy.
185fn enumerable(m: &mut Machine, op: StdOp, s: Handle) -> Result<Option<Vec<Handle>>, Error> {
186    let set = s.is_compound()
187        && !matches!(
188            m.heap.view(s).kind,
189            Kind::IntFcn
190                | Kind::Fcn
191                | Kind::Lambda
192                | Kind::BigInt
193                | Kind::Nat
194                | Kind::Int
195                | Kind::SeqSet
196        );
197    if !set || !m.heap.is_finite(s) {
198        return Ok(None);
199    }
200    if m.heap.is_lazy(s) {
201        return Err(refuse(op, "a set the core keeps lazy"));
202    }
203    m.work_elements(s).map(Some)
204}
205
206/// Argument `i`.
207fn arg(args: &[Handle], i: usize) -> Result<Handle, Error> {
208    args.get(i)
209        .copied()
210        .ok_or_else(|| Error::internal("missing argument"))
211}
212
213/// An `EvalException` of TLC class `code`.
214fn exc(code: u32, what: impl Into<String>) -> Error {
215    Error::eval_class(TlcClass::eval_exception(code), what)
216}
217
218/// `EC.TLC_MODULE_APPLYING_TO_WRONG_VALUE` (2176).
219fn wrong_value(op: &str, what: &str) -> Error {
220    exc(
221        2176,
222        format!("Applying {op} to the following value,\nwhich is not {what}:"),
223    )
224}
225
226/// `EC.TLC_MODULE_ARGUMENT_ERROR` (2169).
227fn arg_error(which: &str, op: &str, what: &str) -> Error {
228    exc(
229        2169,
230        format!("The {which} argument of {op} should be a {what}, but instead it is:"),
231    )
232}
233
234/// A case of `op` the core refuses, as `dive-eval` does.
235fn refuse(op: StdOp, why: &str) -> Error {
236    Error::unsupported(format!("{} ({why})", op.qualified_name()))
237}