sva_engine/refs/
mod.rs

1// Concern: what reading another node yields, per the representation it holds | Non-concern: ordering the reads (schedule.rs), collapsing a closed form (sva-samples) | IO: (NodeId, Var) -> SpectralSum
2
3use std::borrow::Cow;
4
5use sva_formula::closed_form::children;
6use sva_formula::spectral_sum::atom::Indicator;
7use sva_formula::spectral_sum::build::{multiply_lanes, sole_constant};
8use sva_formula::spectral_sum::image;
9use sva_formula::spectral_sum::merge::simplify;
10use sva_formula::{
11    Body, C64, ClosedForm, Lane, Left, NodeId, Part, SpectralSum, Var, dual, inverse,
12    normalize_closed_form,
13};
14
15use crate::cast::Cast;
16use crate::error::{Diagnostic, EngineError, Located};
17use crate::typing::{Typing, Value};
18
19mod identity;
20mod prefix;
21
22pub(crate) use identity::{formula_identity, identity_in};
23pub use identity::{identity, symbolic_hash};
24pub(crate) use prefix::switches;
25
26/// The spectral sum of one node read on `want`'s axis, with every ref it holds already
27/// composed in. A pair answers on either axis; anything else answers on its own.
28pub fn spectral_sum_of(
29    typing: &Typing,
30    node: NodeId,
31    want: Var,
32) -> Result<SpectralSum, EngineError> {
33    composed(typing, node, want, &mut Vec::new())
34}
35
36/// `open` is the chain of refs still being composed: a form reaching itself through
37/// another is a loop no substitution closes.
38fn composed(
39    typing: &Typing,
40    node: NodeId,
41    want: Var,
42    open: &mut Vec<NodeId>,
43) -> Result<SpectralSum, EngineError> {
44    if open.contains(&node) {
45        return Err(cyclic(typing, node));
46    }
47    open.push(node);
48    let held = match typing.value(node) {
49        Value::ClosedForm(form) => {
50            let body = fold_constants(typing, &form.body);
51            compose(typing, &body, form.var, open)?
52        }
53        Value::Cast(Cast::Fourier, source) => {
54            let inner = composed(typing, *source, Var::T, open)?;
55            turn(typing, node, dual(&inner))?
56        }
57        Value::Cast(Cast::IFourier, source) => {
58            let inner = composed(typing, *source, Var::F, open)?;
59            turn(typing, node, inverse(&inner))?
60        }
61        Value::Op { name, .. } if typing.ty(node).is_closed_form() => {
62            return Err(across(typing, node, name));
63        }
64        _ => return Err(no_closed_form(typing, node)),
65    };
66    open.pop();
67    on_axis(typing, node, held, typing.var(node), want)
68}
69
70pub(crate) fn cyclic(typing: &Typing, node: NodeId) -> EngineError {
71    EngineError::refused(Diagnostic {
72        code: "engine.cyclic_substitution".to_string(),
73        message: format!(
74            "`{}` reads itself around a loop of refs.",
75            typing.name(node)
76        ),
77        location: Located::at(typing.name(node), None),
78        help: "write the loop with self(...), which the engine classifies".to_string(),
79    })
80}
81
82fn on_axis(
83    typing: &Typing,
84    node: NodeId,
85    held: SpectralSum,
86    axis: Var,
87    want: Var,
88) -> Result<SpectralSum, EngineError> {
89    if axis == want {
90        return Ok(held);
91    }
92    let turned = match want {
93        Var::F => dual(&held),
94        Var::T => inverse(&held),
95    };
96    turn(typing, node, turned)
97}
98
99fn turn(
100    typing: &Typing,
101    node: NodeId,
102    turned: Result<SpectralSum, Left>,
103) -> Result<SpectralSum, EngineError> {
104    turned.map_err(|left| {
105        EngineError::of_closed_form(
106            &left.refusal(),
107            typing.locate(left.origin),
108            format!(
109                "write `{}` inside sample(...) to leave A deliberately",
110                typing.name(node)
111            ),
112        )
113    })
114}
115
116/// A form whose operands crossed a cast is held as an operation over values, and only
117/// the written form itself has atoms to compose.
118pub(crate) fn across(typing: &Typing, node: NodeId, call: &str) -> EngineError {
119    no_spectral_sum(typing.name(node), call)
120}
121
122/// An exact reading answers off a spectral sum, so a term that reaches none says which
123/// subterm blocked it rather than which reading asked.
124fn no_spectral_sum(node: &str, blocking: &str) -> EngineError {
125    EngineError::refused(Diagnostic {
126        code: "read.no_spectral_sum".to_string(),
127        message: format!(
128            "`{node}` has no spectral sum to read: `{blocking}` composes no value across a ref."
129        ),
130        location: Located::at(node, None),
131        help: "write the construct inside the node it reads, or read it off sample(...)"
132            .to_string(),
133    })
134}
135
136fn no_closed_form(typing: &Typing, node: NodeId) -> EngineError {
137    EngineError::refused(Diagnostic {
138        code: "type.samples_in_closed_form".to_string(),
139        message: format!(
140            "`{}` is samples; nothing returns from samples to a closed form",
141            typing.name(node)
142        ),
143        location: Located::at(typing.name(node), None),
144        help: "read it as samples, or build the closed form without it".to_string(),
145    })
146}
147
148/// Every ref naming one number, replaced by that number. A constant is the same value on
149/// either axis and under every construct, so it folds where no form would substitute.
150pub(crate) fn fold_constants<'a>(typing: &Typing, f: &'a Body) -> Cow<'a, Body> {
151    let fold = &mut Folding::default();
152    match names_number(typing, f, fold) {
153        true => Cow::Owned(folded(typing, f, fold)),
154        false => Cow::Borrowed(f),
155    }
156}
157
158fn names_number(typing: &Typing, f: &Body, fold: &mut Folding) -> bool {
159    match f {
160        Body::Node(id) => number(typing, *id, fold).is_some(),
161        _ => children(f)
162            .into_iter()
163            .any(|p| names_number(typing, &p.body, fold)),
164    }
165}
166
167/// The chain of refs still being folded, and whether a fold met one of them again: a number
168/// that loop cut short is not the node's own, so it is not kept.
169#[derive(Default)]
170struct Folding {
171    open: Vec<NodeId>,
172    cut: bool,
173}
174
175fn folded(typing: &Typing, f: &Body, fold: &mut Folding) -> Body {
176    let Body::Node(id) = f else {
177        return sva_formula::closed_form::map_children(f, |p| {
178            Part::new(p.origin, folded(typing, &p.body, fold))
179        });
180    };
181    match number(typing, *id, fold) {
182        Some(c) => Body::Const(c),
183        None => f.clone(),
184    }
185}
186
187/// The one number a node holds, or `None` where it holds a form, samples or a ref loop.
188fn number(typing: &Typing, node: NodeId, fold: &mut Folding) -> Option<C64> {
189    if let Some(held) = typing.folded_number(node) {
190        return held;
191    }
192    if fold.open.contains(&node) {
193        fold.cut = true;
194        return None;
195    }
196    let Value::ClosedForm(form) = typing.value(node) else {
197        return None;
198    };
199    if let Body::Const(c) = form.body {
200        return Some(c);
201    }
202    let outer = std::mem::take(&mut fold.cut);
203    fold.open.push(node);
204    let folded = names_number(typing, &form.body, fold).then(|| ClosedForm {
205        body: folded(typing, &form.body, fold),
206        ..*form
207    });
208    fold.open.pop();
209    let number = normalize_closed_form(folded.as_ref().unwrap_or(form))
210        .ok()
211        .and_then(|sum| sole_constant(&sum));
212    if !fold.cut {
213        typing.fold_number(node, number);
214    }
215    fold.cut |= outer;
216    number
217}
218
219/// A node reference is not a `Body`, so a term holding one is normalized by composing
220/// the pieces around it rather than by handing the whole tree to `normalize`.
221fn compose(
222    typing: &Typing,
223    body: &Body,
224    var: Var,
225    open: &mut Vec<NodeId>,
226) -> Result<SpectralSum, EngineError> {
227    let here = *open
228        .last()
229        .expect("compose runs inside the node it composes");
230    if !holds_node(body) {
231        return normalize_here(typing, body, var);
232    }
233    match body {
234        Body::Node(id) => composed(typing, *id, var, open),
235        Body::Add(parts) => {
236            let mut lanes: Vec<Lane> = Vec::new();
237            for part in parts {
238                add_into(&mut lanes, compose(typing, &part.body, var, open)?);
239            }
240            Ok(sum(var, lanes))
241        }
242        Body::Mul(parts) => {
243            let mut acc: Option<SpectralSum> = None;
244            for part in parts {
245                let next = compose(typing, &part.body, var, open)?;
246                acc = Some(match acc {
247                    None => next,
248                    Some(held) => multiply(typing, &held, &next, var)?,
249                });
250            }
251            Ok(acc.unwrap_or_else(|| sum(var, Vec::new())))
252        }
253        Body::Shift { by, of } => {
254            let held = compose(typing, &of.body, var, open)?;
255            image::shift(held, *by).map_err(|left| left_of(typing, left))
256        }
257        Body::Crop {
258            of,
259            l,
260            r,
261            rise,
262            fall,
263        } if *rise > 0.0 || *fall > 0.0 => {
264            let held = compose(typing, &of.body, var, open)?;
265            let window = image::crop_window(*l, *r, *rise, *fall, of.origin, var);
266            multiply(typing, &held, &window, var)
267        }
268        Body::Crop { of, l, r, .. } => {
269            let held = compose(typing, &of.body, var, open)?;
270            image::crop(held, Indicator { l: *l, r: *r }).map_err(|left| left_of(typing, left))
271        }
272        Body::Div(num, den) => {
273            let over = compose(typing, &den.body, var, open)?;
274            let numerator = compose(typing, &num.body, var, open)?;
275            multiply(typing, &numerator, &reciprocal(typing, here, &over)?, var)
276        }
277        Body::Join(parts) => {
278            let mut lanes = Vec::new();
279            for part in parts {
280                lanes.extend(compose(typing, &part.body, var, open)?.lanes);
281            }
282            Ok(sum(var, lanes))
283        }
284        Body::Channel(of, k) => {
285            let held = compose(typing, &of.body, var, open)?;
286            match held.lanes.into_iter().nth(usize::from(*k)) {
287                Some(lane) => Ok(sum(var, vec![lane])),
288                None => Err(unsubstituted(typing, here, body)),
289            }
290        }
291        // Inlined, every other construct is what it was written as, and normalizes.
292        other => match inlined(typing, other, var, &mut open.clone()) {
293            Some(written) => normalize_here(typing, &written, var),
294            None => Err(unsubstituted(typing, here, other)),
295        },
296    }
297}
298
299/// A divisor a ref reaches has to be one number: a reciprocal is not an atom sum.
300fn reciprocal(
301    typing: &Typing,
302    node: NodeId,
303    over: &SpectralSum,
304) -> Result<SpectralSum, EngineError> {
305    let divided = || no_spectral_sum(typing.name(node), "a division by a closed form");
306    let [lane] = over.lanes.as_slice() else {
307        return Err(divided());
308    };
309    match lane.atoms.as_slice() {
310        [atom] if atom.is_bare() => Ok(SpectralSum::mono(
311            over.var,
312            vec![sva_formula::spectral_sum::atom::SpectralAtom::constant(
313                atom.c.inv(),
314                atom.origin,
315            )],
316        )),
317        _ => Err(divided()),
318    }
319}
320
321fn left_of(typing: &Typing, left: Left) -> EngineError {
322    EngineError::of_closed_form(
323        &left.refusal(),
324        typing.locate(left.origin),
325        "write the subterm inside sample(...) to leave A deliberately",
326    )
327}
328
329fn normalize_here(typing: &Typing, body: &Body, var: Var) -> Result<SpectralSum, EngineError> {
330    normalize_closed_form(&ClosedForm {
331        var,
332        body: body.clone(),
333        origin: sva_formula::Origin::UNKNOWN,
334    })
335    .map_err(|left| {
336        EngineError::of_closed_form(
337            &left.refusal(),
338            typing.locate(left.origin),
339            "write the subterm inside sample(...) to leave A deliberately",
340        )
341    })
342}
343
344/// A ref reaching a value no substitution inlines, under a construct with no lane rule of
345/// its own: the reading has a name and nothing to read it off.
346fn unsubstituted(typing: &Typing, node: NodeId, body: &Body) -> EngineError {
347    no_spectral_sum(typing.name(node), named(body))
348}
349
350fn named(body: &Body) -> &'static str {
351    match body {
352        Body::Apply(op, _) => op.name(),
353        Body::Pow(..) => "pow",
354        Body::Fold(..) => "max, min or mod",
355        Body::Join(_) => "join",
356        Body::Channel(..) => "ch",
357        Body::Series(_) => "sum",
358        Body::Delta { .. } => "delta",
359        Body::Pv(_) => "pv",
360        Body::Deriv { .. } => "a derivative",
361        Body::Warp { .. } => "a warped time",
362        _ => "a construct",
363    }
364}
365
366/// Every node a written form names, in written order, so a caller answers each one.
367pub fn nodes_in(f: &Body) -> Vec<NodeId> {
368    let mut out = Vec::new();
369    collect_nodes(f, &mut out);
370    out
371}
372
373fn collect_nodes(f: &Body, out: &mut Vec<NodeId>) {
374    if let Body::Node(id) = f {
375        if !out.contains(id) {
376            out.push(*id);
377        }
378        return;
379    }
380    for part in children(f) {
381        collect_nodes(&part.body, out);
382    }
383}
384
385fn holds_node(f: &Body) -> bool {
386    matches!(f, Body::Node(_)) || children(f).iter().any(|p| holds_node(&p.body))
387}
388
389fn sum(var: Var, mut lanes: Vec<Lane>) -> SpectralSum {
390    for lane in &mut lanes {
391        simplify(lane);
392    }
393    SpectralSum::of(var, lanes)
394}
395
396/// A width-1 operand broadcasts into every lane of the wider one, at the operator.
397fn add_into(lanes: &mut Vec<Lane>, other: SpectralSum) {
398    if other.lanes.is_empty() {
399        return;
400    }
401    let width = lanes.len().max(other.lanes.len());
402    if lanes.len() == 1 {
403        let held = lanes[0].clone();
404        lanes.resize(width, held);
405    }
406    for at in 0..width {
407        let lane = lane_at(&other, at).clone();
408        match lanes.get_mut(at) {
409            Some(held) => {
410                held.atoms.extend(lane.atoms);
411                held.series.extend(lane.series);
412                held.modal.extend(lane.modal);
413            }
414            None => lanes.push(lane),
415        }
416    }
417}
418
419fn multiply(
420    typing: &Typing,
421    a: &SpectralSum,
422    b: &SpectralSum,
423    var: Var,
424) -> Result<SpectralSum, EngineError> {
425    let width = a.lanes.len().max(b.lanes.len());
426    let mut lanes = Vec::with_capacity(width);
427    for at in 0..width {
428        let held = multiply_lanes(lane_at(a, at).clone(), lane_at(b, at).clone());
429        lanes.push(held.map_err(|left| {
430            EngineError::of_closed_form(
431                &left.refusal(),
432                typing.locate(left.origin),
433                "write one of the factors inside sample(...)",
434            )
435        })?);
436    }
437    Ok(sum(var, lanes))
438}
439
440fn lane_at(n: &SpectralSum, at: usize) -> &Lane {
441    n.lanes.get(at).unwrap_or(&n.lanes[0])
442}
443
444/// Every ref inlined, where each is a form on the same axis; a crossing answers `None`.
445pub fn substituted_closed_form(typing: &Typing, node: NodeId) -> Option<ClosedForm> {
446    let Value::ClosedForm(form) = typing.value(node) else {
447        return None;
448    };
449    Some(ClosedForm {
450        var: form.var,
451        body: substituted_body(typing, node, &form.body)?,
452        origin: form.origin,
453    })
454}
455
456/// The same substitution over one body of `node`'s own form.
457pub(crate) fn substituted_body(typing: &Typing, node: NodeId, body: &Body) -> Option<Body> {
458    let Value::ClosedForm(form) = typing.value(node) else {
459        return None;
460    };
461    inlined(typing, body, form.var, &mut vec![node])
462}
463
464fn inlined(typing: &Typing, f: &Body, var: Var, open: &mut Vec<NodeId>) -> Option<Body> {
465    match f {
466        Body::Node(id) if open.contains(id) => None,
467        Body::Node(id) => match typing.value(*id) {
468            Value::ClosedForm(form) if form.var == var => {
469                open.push(*id);
470                let out = inlined(typing, &form.body, var, open);
471                open.pop();
472                out
473            }
474            _ => None,
475        },
476        other => {
477            let mut ok = true;
478            let out = sva_formula::closed_form::map_children(other, |p| {
479                match inlined(typing, &p.body, var, open) {
480                    Some(body) => sva_formula::Part::new(p.origin, body),
481                    None => {
482                        ok = false;
483                        p.clone()
484                    }
485                }
486            });
487            ok.then_some(out)
488        }
489    }
490}
sva_engine/refs/mod.rs

sva_engine/refs/
mod.rs
