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

sva_engine/refs/
mod.rs
