Skip to main content

datumesh_engine/
whatif.rs

1//! Scenarios (Build 2 Part 3, E1 and E2; SPEC 5.9): [`Engine::whatif`] evaluates a cell as of
2//! an asof with overrides in place, and writes nothing. The solver ([`Solve`]) finds the value
3//! of one number cell that makes another equal a number, by bisection.
4//!
5//! A scenario answer is not an [`Answer`](crate::Answer): it has no receipt and is never
6//! stored, signed or memoised. Cells that do not depend on the overrides answer as `get` would,
7//! from the memo and the store; the dependent ones are evaluated in the request's scope.
8
9use std::collections::{HashMap, HashSet};
10use std::sync::Arc;
11
12use datumesh_core::{lexical, Arg, Cell, CellRef, FunctionDescriptor, Scalar, Type};
13
14use crate::check::{check_args, check_no_slice};
15use crate::engine::{Engine, STORED};
16use crate::error::{EngineError, StoreError};
17use crate::eval::{Done, Req};
18use crate::runtime::{Budget, Pattern, SlicePattern};
19use crate::slice::cells_slice;
20
21/// The most overrides a scenario may have (SPEC 5.9).
22const MAX_OVERRIDES: usize = 64;
23
24/// The overrides of a scenario: value overrides and slice overrides, in the order given.
25#[derive(Clone, Debug, Default)]
26pub struct Overrides {
27    items: Vec<Override>,
28}
29
30#[derive(Clone, Debug)]
31enum Override {
32    Value { cell: CellRef, value: Scalar },
33    Slice { slice: CellRef, add: Vec<(CellRef, Scalar)>, remove: Vec<CellRef> },
34}
35
36impl Overrides {
37    /// No overrides.
38    pub fn new() -> Overrides {
39        Overrides::default()
40    }
41
42    /// `cell` answers `value` (of the function's return type) in the scenario.
43    pub fn value(mut self, cell: CellRef, value: Scalar) -> Overrides {
44        self.items.push(Override::Value { cell, value });
45        self
46    }
47
48    /// The members of the stored slice `slice` (a cell reference with its open arguments left
49    /// open) change: `add` are new members with their values, `remove` are members that go.
50    pub fn slice(mut self, slice: CellRef, add: Vec<(CellRef, Scalar)>, remove: Vec<CellRef>) -> Overrides {
51        self.items.push(Override::Slice { slice, add, remove });
52        self
53    }
54
55    /// The number of overrides.
56    pub fn len(&self) -> usize {
57        self.items.len()
58    }
59
60    /// Whether there are no overrides.
61    pub fn is_empty(&self) -> bool {
62        self.items.is_empty()
63    }
64}
65
66/// A solve for [`Engine::whatif`]: find the value of `vary` (a number cell) in `[lo, hi]` at
67/// which `target` (a number cell) equals `equals`. All four are number scalars. The value found
68/// carries 15 significant digits (rounded half-even), and the answer is the requested cell's
69/// value under it: the target's, when the requested cell is the target.
70#[derive(Clone, Debug)]
71pub struct Solve {
72    vary: CellRef,
73    target: CellRef,
74    equals: Scalar,
75    lo: Scalar,
76    hi: Scalar,
77}
78
79impl Solve {
80    /// The solve of `target = equals` over `vary` in `[lo, hi]`.
81    pub fn new(vary: CellRef, target: CellRef, equals: Scalar, lo: Scalar, hi: Scalar) -> Solve {
82        Solve { vary, target, equals, lo, hi }
83    }
84}
85
86/// A scenario's answer ([`Engine::whatif`]): the value of the cell as of the asof, with the
87/// overrides in place. It is labelled a scenario: it has no receipt and is never stored.
88#[non_exhaustive]
89#[derive(Clone, Debug, PartialEq)]
90pub struct ScenarioAnswer {
91    /// The cell asked for.
92    pub cell: Cell,
93    /// Its type (the function's return type).
94    pub ty: Type,
95    /// Its value in the scenario.
96    pub value: Scalar,
97    /// The asof: the one asked for, else the clock's now.
98    pub asof: String,
99    /// The overrides, sorted by [`ScenarioOverride::id`].
100    pub overrides: Vec<ScenarioOverride>,
101    /// The solved cell and the value found for it, when the request had a solve.
102    pub solved: Option<(Cell, Scalar)>,
103}
104
105/// An override of a scenario, as its answer lists it.
106#[non_exhaustive]
107#[derive(Clone, Debug, PartialEq)]
108pub enum ScenarioOverride {
109    /// A cell with a value.
110    Value {
111        /// The cell.
112        cell: Cell,
113        /// Its value.
114        value: Scalar,
115    },
116    /// A stored slice with members added and removed; both sorted by cell id.
117    Slice {
118        /// The slice (its open arguments are [`Arg::Slice`]).
119        slice: Cell,
120        /// The added members, with their values.
121        add: Vec<(Cell, Scalar)>,
122        /// The removed members.
123        remove: Vec<Cell>,
124    },
125}
126
127impl ScenarioOverride {
128    /// The id of the overridden cell, or of the slice.
129    pub fn id(&self) -> String {
130        match self {
131            ScenarioOverride::Value { cell, .. } => cell.id(),
132            ScenarioOverride::Slice { slice, .. } => slice.id(),
133        }
134    }
135}
136
137/// The overrides of one scenario, validated and resolved, as the evaluation reads them.
138#[derive(Clone, Debug, Default)]
139pub(crate) struct Scope {
140    /// The overridden cells, by cell id.
141    pub(crate) values: HashMap<String, (Cell, Scalar)>,
142    /// The overridden slices, by slice id.
143    pub(crate) slices: HashMap<String, SliceOverride>,
144    /// The names of the overridden functions.
145    pub(crate) affected: HashSet<String>,
146}
147
148/// A slice override: the members added, and the cell ids of those removed.
149#[derive(Clone, Debug)]
150pub(crate) struct SliceOverride {
151    pub(crate) add: Vec<(Cell, Scalar)>,
152    pub(crate) remove: HashSet<String>,
153}
154
155impl Scope {
156    /// This scope with `cell` overridden to `value` as well (the solver's trial values).
157    pub(crate) fn with_value(&self, cell: Cell, value: Scalar) -> Scope {
158        let mut s = self.clone();
159        s.affected.insert(cell.function_name());
160        s.values.insert(cell.id(), (cell, value));
161        s
162    }
163}
164
165impl Engine {
166    /// The value of `cell` as of `asof` (else `cell.asof`, else now) with `overrides` in place.
167    /// With `solve`, `vary` is first set to the value that makes its `target` equal its `equals`
168    /// (bisection within its interval; see [`Solve`]), and `cell`'s value is then that under the
169    /// solved `vary`; the answer's `solved` says what was found.
170    ///
171    /// The overridden cells answer their values; a slice override changes a stored slice's
172    /// members. A cell that does not depend on the overrides answers from the memo and the
173    /// store as [`get`](Engine::get) would; a dependent cell is evaluated in the request's scope.
174    /// Nothing is written: no receipt, computed version, memo entry or signature. The answer
175    /// is labelled a scenario, not a fact.
176    ///
177    /// Errors: [`EngineError::Override`] for overrides that are not valid (or more than 64),
178    /// [`EngineError::NotCovered`] when the cell has no value (a fault in scope included), and
179    /// [`EngineError::WhatifNoSolution`] for a solve without a solution or out of fuel. The
180    /// usual request errors (asof, arguments, unlicensed, budget) are those of `get`.
181    pub fn whatif(
182        &self,
183        cell: &CellRef,
184        asof: Option<&str>,
185        overrides: &Overrides,
186        solve: Option<&Solve>,
187    ) -> Result<ScenarioAnswer, EngineError> {
188        let now = self.clock.now();
189        let a = asof.or(cell.asof.as_deref()).unwrap_or(&now).to_string();
190        lexical::check_instant(&a, "$.asof").map_err(EngineError::Invalid)?;
191        check_no_slice(&cell.args)?;
192        if overrides.len() > MAX_OVERRIDES {
193            return Err(EngineError::Override("E_CANON_LIMIT".into()));
194        }
195        let Some((fn_hash, desc)) = self.function_as_of(&cell.ns, &cell.fn_name, &a)? else {
196            return Err(EngineError::NotCovered { fault: None });
197        };
198        let target = cell.resolve(&fn_hash).map_err(EngineError::Invalid)?;
199        check_args(&target, &desc).map_err(EngineError::Invalid)?;
200        let (scope, list) = self.build_scope(overrides, &a)?;
201        let scope = Arc::new(scope);
202        // One budget for the whole request: a solve's iterations share its fuel.
203        let budget = Budget::with_work(self.fuel, self.work_limit);
204        let ty = desc.signature.returns.ty;
205        let (value, solved) = match solve {
206            None => (self.scope_value(&target, &desc, &a, &now, &scope, &budget)?, None),
207            Some(s) => self.solve(s, &target, &desc, &a, &now, &scope, &budget)?,
208        };
209        Ok(ScenarioAnswer { cell: target, ty, value, asof: a, overrides: list, solved })
210    }
211
212    /// The function `<ns>/<fn_name>` means as of `asof`: its hash and descriptor, or none when
213    /// the name is unbound or has no descriptor.
214    fn function_as_of(
215        &self,
216        ns: &str,
217        fn_name: &str,
218        asof: &str,
219    ) -> Result<Option<(String, Arc<FunctionDescriptor>)>, EngineError> {
220        let name = format!("{ns}/{fn_name}");
221        let Some(hash) = self.store.resolve_name(&name, asof).map_err(|e| StoreError::new("resolve_name", e))? else {
222            return Ok(None);
223        };
224        Ok(self.descriptor_of(&hash)?.map(|d| (hash, d)))
225    }
226
227    /// A cell reference resolved as of `asof`, with its arguments checked against the signature.
228    fn resolve_cell(&self, c: &CellRef, asof: &str) -> Result<(Cell, Arc<FunctionDescriptor>), EngineError> {
229        check_no_slice(&c.args)?;
230        let Some((hash, desc)) = self.function_as_of(&c.ns, &c.fn_name, asof)? else {
231            return Err(EngineError::NameUnresolved { fn_name: format!("{}/{}", c.ns, c.fn_name), asof: asof.into() });
232        };
233        let cell = c.resolve(&hash).map_err(EngineError::Invalid)?;
234        check_args(&cell, &desc).map_err(EngineError::Invalid)?;
235        Ok((cell, desc))
236    }
237
238    /// Validates the overrides as of `asof` (SPEC 5.9) and makes the scope and the sorted list
239    /// the answer shows.
240    fn build_scope(&self, overrides: &Overrides, asof: &str) -> Result<(Scope, Vec<ScenarioOverride>), EngineError> {
241        let refused = |code: &str| EngineError::Override(code.to_string());
242        let mut scope = Scope::default();
243        let mut list = Vec::new();
244        for o in &overrides.items {
245            match o {
246                Override::Value { cell, value } => {
247                    let (c, desc) = self.resolve_cell(cell, asof)?;
248                    if value.ty() != desc.signature.returns.ty {
249                        return Err(refused("E_CANON_TYPE"));
250                    }
251                    let id = c.id();
252                    if scope.values.contains_key(&id) {
253                        return Err(refused("E_CANON_ARG_DUPLICATE"));
254                    }
255                    scope.affected.insert(c.function_name());
256                    scope.values.insert(id, (c.clone(), value.clone()));
257                    list.push(ScenarioOverride::Value { cell: c, value: value.clone() });
258                }
259                Override::Slice { slice, add, remove } => {
260                    let Some((hash, desc)) = self.function_as_of(&slice.ns, &slice.fn_name, asof)? else {
261                        return Err(EngineError::NameUnresolved {
262                            fn_name: format!("{}/{}", slice.ns, slice.fn_name),
263                            asof: asof.into(),
264                        });
265                    };
266                    let fn_name = format!("{}/{}", slice.ns, slice.fn_name);
267                    // Only stored slices change by membership.
268                    if desc.lang != STORED {
269                        return Err(refused("E_SLICE_MEMBER"));
270                    }
271                    let pattern: SlicePattern = slice
272                        .args
273                        .iter()
274                        .map(|(k, a)| {
275                            let p = match a {
276                                Arg::Value(v) => Pattern::Value(v.clone()),
277                                Arg::Slice => Pattern::Open,
278                            };
279                            (k.clone(), p)
280                        })
281                        .collect();
282                    let s = cells_slice(&fn_name, &hash, &desc, &pattern).map_err(EngineError::Invalid)?;
283                    let sid = s.id().to_string();
284                    if scope.slices.contains_key(&sid) {
285                        return Err(refused("E_CANON_ARG_DUPLICATE"));
286                    }
287                    let slice_cell = slice.resolve(&hash).map_err(EngineError::Invalid)?;
288                    let mut adds: Vec<(Cell, Scalar)> = Vec::with_capacity(add.len());
289                    for (c, v) in add {
290                        let cell = c.resolve(&hash).map_err(EngineError::Invalid)?;
291                        check_args(&cell, &desc).map_err(EngineError::Invalid)?;
292                        if cell.function_name() != fn_name {
293                            return Err(refused("E_SLICE_MEMBER"));
294                        }
295                        adds.push((cell, v.clone()));
296                    }
297                    let mut removes: Vec<Cell> = Vec::with_capacity(remove.len());
298                    for c in remove {
299                        let cell = c.resolve(&hash).map_err(EngineError::Invalid)?;
300                        check_args(&cell, &desc).map_err(EngineError::Invalid)?;
301                        if cell.function_name() != fn_name {
302                            return Err(refused("E_SLICE_MEMBER"));
303                        }
304                        removes.push(cell);
305                    }
306                    let mut add_ids = HashSet::new();
307                    for (c, _) in &adds {
308                        if !add_ids.insert(c.id()) {
309                            return Err(refused("E_CANON_ARG_DUPLICATE"));
310                        }
311                    }
312                    let mut remove_ids = HashSet::new();
313                    for c in &removes {
314                        if !remove_ids.insert(c.id()) {
315                            return Err(refused("E_CANON_ARG_DUPLICATE"));
316                        }
317                    }
318                    if adds.iter().any(|(c, _)| remove_ids.contains(&c.id())) {
319                        return Err(refused("E_SLICE_MEMBER"));
320                    }
321                    let members: HashSet<String> = self
322                        .store
323                        .slice_values(&s, asof)
324                        .map_err(|e| StoreError::new("slice_values", e))?
325                        .into_iter()
326                        .map(|v| v.version.cell_id)
327                        .collect();
328                    for c in &removes {
329                        if !matches(&pattern, c) || !members.contains(&c.id()) {
330                            return Err(refused("E_SLICE_MEMBER"));
331                        }
332                    }
333                    for (c, v) in &adds {
334                        if !matches(&pattern, c) || members.contains(&c.id()) {
335                            return Err(refused("E_SLICE_MEMBER"));
336                        }
337                        if v.ty() != desc.signature.returns.ty {
338                            return Err(refused("E_CANON_TYPE"));
339                        }
340                        // Read alone, an added member answers its value, as an overridden cell does.
341                        scope.values.insert(c.id(), (c.clone(), v.clone()));
342                    }
343                    scope.affected.insert(fn_name);
344                    scope.slices.insert(sid, SliceOverride { add: adds.clone(), remove: remove_ids });
345                    let mut add_sorted = adds;
346                    add_sorted.sort_by_key(|(c, _)| c.id());
347                    removes.sort_by_key(|c| c.id());
348                    list.push(ScenarioOverride::Slice { slice: slice_cell, add: add_sorted, remove: removes });
349                }
350            }
351        }
352        list.sort_by_key(|o| o.id());
353        Ok((scope, list))
354    }
355
356    /// The value of `target` in `scope` as of `asof`: the override's value when it is
357    /// overridden, else what the scenario evaluation gives.
358    fn scope_value(
359        &self,
360        target: &Cell,
361        desc: &Arc<FunctionDescriptor>,
362        asof: &str,
363        now: &str,
364        scope: &Arc<Scope>,
365        budget: &Budget,
366    ) -> Result<Scalar, EngineError> {
367        if let Some((_, v)) = scope.values.get(&target.id()) {
368            return Ok(v.clone());
369        }
370        let mut req = Req::scoped(self, asof, now, scope.clone(), budget);
371        match req.scope_run(target.clone(), desc.clone())? {
372            Done::Value(a) => Ok(a.value.clone()),
373            Done::Fault(f) => Err(EngineError::NotCovered { fault: Some(f.fault) }),
374            Done::NotCovered | Done::Unsigned(..) => Err(EngineError::NotCovered { fault: None }),
375        }
376    }
377
378    /// The solve of [`Engine::whatif`] (E2): bisection of `target - equals` over `vary`. Out of
379    /// fuel, or no sign change, is `WhatifNoSolution`.
380    #[allow(clippy::too_many_arguments)]
381    fn solve(
382        &self,
383        s: &Solve,
384        target: &Cell,
385        desc: &Arc<FunctionDescriptor>,
386        asof: &str,
387        now: &str,
388        scope: &Arc<Scope>,
389        budget: &Budget,
390    ) -> Result<(Scalar, Option<(Cell, Scalar)>), EngineError> {
391        // The bisection is on the solve's `target`; the answer is the requested cell's value.
392        let (vary, vary_desc) = self.resolve_cell(&s.vary, asof)?;
393        let (solve_target, solve_desc) = self.resolve_cell(&s.target, asof)?;
394        let number = Type::Number;
395        if vary_desc.signature.returns.ty != number
396            || solve_desc.signature.returns.ty != number
397            || [&s.equals, &s.lo, &s.hi].iter().any(|x| x.ty() != number)
398        {
399            return Err(EngineError::Override("E_CANON_TYPE".into()));
400        }
401        let result = (|| {
402            let num = |x: &Scalar| -> f64 { x.lexical().parse().unwrap_or(f64::NAN) };
403            let (eq, lo, hi) = (num(&s.equals), num(&s.lo), num(&s.hi));
404            if lo > hi {
405                return Err(EngineError::WhatifNoSolution);
406            }
407            // The scope with `vary` at `x`, rounded as the answer will carry it.
408            let trial = |x: f64| -> Result<(Scalar, Arc<Scope>), EngineError> {
409                let text = decimal15(x).ok_or(EngineError::WhatifNoSolution)?;
410                let value = Scalar::from_lexical(number, &text).map_err(|_| EngineError::WhatifNoSolution)?;
411                Ok((value.clone(), Arc::new(scope.with_value(vary.clone(), value))))
412            };
413            let f = |x: f64| -> Result<f64, EngineError> {
414                let (_, sc) = trial(x)?;
415                let v = self.scope_value(&solve_target, &solve_desc, asof, now, &sc, budget)?;
416                Ok(num(&v) - eq)
417            };
418            let flo = f(lo)?;
419            let x = if flo == 0.0 {
420                lo
421            } else {
422                let fhi = f(hi)?;
423                if fhi == 0.0 {
424                    hi
425                } else {
426                    if (flo < 0.0) == (fhi < 0.0) {
427                        return Err(EngineError::WhatifNoSolution);
428                    }
429                    let (mut a, mut fa, mut b, mut fb) = (lo, flo, hi, fhi);
430                    loop {
431                        let mid = a + (b - a) / 2.0;
432                        if mid <= a || mid >= b {
433                            // The interval holds no double between its ends: the nearer one.
434                            break if fa.abs() <= fb.abs() { a } else { b };
435                        }
436                        let fm = f(mid)?;
437                        if fm.abs() <= 1e-12 * eq.abs().max(1.0)
438                            || (b - a).abs() <= 1e-12 * a.abs().max(b.abs()).max(1.0)
439                        {
440                            break mid;
441                        }
442                        if (fm < 0.0) == (fa < 0.0) {
443                            a = mid;
444                            fa = fm;
445                        } else {
446                            b = mid;
447                            fb = fm;
448                        }
449                    }
450                }
451            };
452            let (value, sc) = trial(x)?;
453            let v = self.scope_value(target, desc, asof, now, &sc, budget)?;
454            Ok((v, Some((vary.clone(), value))))
455        })();
456        match result {
457            Err(EngineError::BudgetExceeded { .. } | EngineError::WorkExceeded { .. }) => {
458                Err(EngineError::WhatifNoSolution)
459            }
460            other => other,
461        }
462    }
463}
464
465/// The hash standing for an unsigned scenario answer (an overridden value, or a member a
466/// scenario changed): not a receipt's, but distinct for each cell and value.
467pub(crate) fn scoped_hash(id: &str, value: &Scalar) -> String {
468    datumesh_core::sha256_hex(format!("scenario {id} {} {}", value.ty().as_str(), value.lexical()).as_bytes())
469}
470
471/// Whether `cell`'s arguments match `pattern` (a bound argument equal, an open one anything).
472fn matches(pattern: &SlicePattern, cell: &Cell) -> bool {
473    pattern.iter().all(|(k, p)| match (cell.args.get(k), p) {
474        (Some(Arg::Value(v)), Pattern::Value(pv)) => v == pv,
475        (Some(Arg::Value(_)), Pattern::Open) => true,
476        _ => false,
477    })
478}
479
480/// A finite number rounded to 15 significant digits, half-even (the rounding of the Rust float
481/// formatter on the exact binary value), as a canonical decimal (SPEC 3.1: no exponent, no
482/// trailing zeros). Solve values carry these digits: the bisection runs on binary doubles, and
483/// 15 digits are what a double holds deterministically. `None` for a non-finite value or one
484/// whose text is too long.
485fn decimal15(x: f64) -> Option<String> {
486    if !x.is_finite() {
487        return None;
488    }
489    if x == 0.0 {
490        return Some("0".into());
491    }
492    let text = format!("{:.14e}", x.abs());
493    let (mantissa, exp) = text.split_once('e')?;
494    let exp: i64 = exp.parse().ok()?;
495    let digits: String = mantissa.chars().filter(char::is_ascii_digit).collect();
496    let digits = digits.trim_end_matches('0');
497    let mut out = String::new();
498    if x < 0.0 {
499        out.push('-');
500    }
501    if exp >= 0 {
502        let int_len = usize::try_from(exp).ok()? + 1;
503        if digits.len() <= int_len {
504            out.push_str(digits);
505            out.extend(std::iter::repeat_n('0', int_len - digits.len()));
506        } else {
507            out.push_str(&digits[..int_len]);
508            out.push('.');
509            out.push_str(&digits[int_len..]);
510        }
511    } else {
512        out.push_str("0.");
513        out.extend(std::iter::repeat_n('0', usize::try_from(-exp - 1).ok()?));
514        out.push_str(digits);
515    }
516    (out.len() <= 128).then_some(out)
517}
518
519#[cfg(test)]
520mod tests {
521    use super::decimal15;
522
523    #[test]
524    fn decimals_are_canonical() {
525        assert_eq!(decimal15(3.0).as_deref(), Some("3"));
526        assert_eq!(decimal15(-0.5).as_deref(), Some("-0.5"));
527        assert_eq!(decimal15(0.0).as_deref(), Some("0"));
528        assert_eq!(decimal15(1e-5).as_deref(), Some("0.00001"));
529        assert_eq!(decimal15(120.0).as_deref(), Some("120"));
530        assert_eq!(decimal15(2f64.sqrt()).as_deref(), Some("1.4142135623731"));
531    }
532}