sva_engine/
loops.rs

1// Concern: classifies a self-reference, and folds the shift one reads at to a constant | Non-concern: running either kind (sva-samples), lowering the rest (lower/) | IO: (body, Cx) -> SelfKind, Shift
2
3use sva_ast::{Arg, BinOp, ByteSpan, Expr, Literal};
4use sva_formula::closed_form::{map_children, read_at};
5use sva_formula::{Body, C64, IndexId, Part, Series, Var};
6
7use crate::arguments::Chosen;
8use crate::error::{Diagnostic, EngineError, Located};
9use crate::instantiate::{Cx, Instances, Node};
10
11/// A sampled loop's step count is only known once an observation names a rate.
12#[derive(Clone, Copy, Debug, PartialEq)]
13pub enum Delay {
14    Steps(u32),
15    Secs(f64),
16    /// A delay written as a closed form of `t`, which only the grid can follow.
17    Varying,
18}
19
20#[derive(Clone, Debug, PartialEq)]
21pub(crate) enum SelfKind {
22    Series { gain: C64, delay: f64 },
23    Sampled,
24    Refuse(Box<EngineError>),
25}
26
27/// Linear in `self`, a constant delay in seconds and `abs(g) < 1` is a series, and the same
28/// loop at unit gain or above settles nowhere. A delay in `sp` is row three of FORMAT 11 and
29/// runs on the grid at unit gain, a running sum being a value; above it, nothing settles.
30pub(crate) fn classify(inst: &Instances, e: &Expr, cx: Cx, at: &str) -> SelfKind {
31    match read(inst, e, cx, C64::ONE) {
32        Reading::Refused(tap) => SelfKind::Refuse(Box::new(
33            tap_refusal(tap, Located::at(at, None)).expect("a refused tap names its reason"),
34        )),
35        Reading::Free | Reading::Nonlinear => SelfKind::Sampled,
36        Reading::Linear {
37            gain,
38            delay: Delay::Steps(_),
39        } if gain.abs() > 1.0 => SelfKind::Refuse(Box::new(unbounded(gain, at))),
40        Reading::Linear {
41            delay: Delay::Steps(_) | Delay::Varying,
42            ..
43        } => SelfKind::Sampled,
44        Reading::Linear {
45            gain,
46            delay: Delay::Secs(secs),
47        } => match gain.abs() < 1.0 {
48            true => SelfKind::Series { gain, delay: secs },
49            false => SelfKind::Refuse(Box::new(unbounded(gain, at))),
50        },
51    }
52}
53
54/// What one `self(...)` call site reads: a usable delay, or the reason it is not one.
55#[derive(Clone, Copy, Debug, PartialEq)]
56pub(crate) enum Tap {
57    At(Delay),
58    Zero,
59    Forward,
60    Fractional,
61}
62
63/// The one reading of a self-reference's time, so classification and lowering cannot drift.
64pub(crate) fn tap_of(inst: &Instances, arg: &Expr, cx: Cx) -> Tap {
65    match shift_of(inst, arg, cx) {
66        None => Tap::At(Delay::Varying),
67        Some(Shift::Now) => Tap::Zero,
68        Some(Shift::Secs(secs)) if secs > 0.0 => Tap::At(Delay::Secs(secs)),
69        Some(Shift::Steps(steps)) if steps > 0.0 && steps.fract() == 0.0 => {
70            Tap::At(Delay::Steps(steps as u32))
71        }
72        Some(Shift::Steps(steps)) if steps > 0.0 => Tap::Fractional,
73        Some(_) => Tap::Forward,
74    }
75}
76
77pub(crate) fn tap_refusal(tap: Tap, at: Located) -> Option<EngineError> {
78    let (code, message, help) = match tap {
79        Tap::At(_) => return None,
80        Tap::Zero => (
81            "samples.zero_delay_loop",
82            "a loop reaches no sample it has already written.",
83            "write self(t - 1sp) for a one-step loop",
84        ),
85        Tap::Forward => (
86            "engine.forward_self_read",
87            "a loop reads its own output before it is written.",
88            "write self at an earlier time, as in self(t - 1sp)",
89        ),
90        Tap::Fractional => (
91            "ref.fractional_shift_on_samples",
92            "a read on the grid moves by whole samples.",
93            "write a whole number of sp, or the delay in seconds",
94        ),
95    };
96    Some(EngineError::refused(Diagnostic {
97        code: code.to_string(),
98        message: message.to_string(),
99        location: at,
100        help: help.to_string(),
101    }))
102}
103
104fn unbounded(gain: C64, at: &str) -> EngineError {
105    EngineError::refused(Diagnostic {
106        code: "type.self_gain_unbounded".to_string(),
107        message: format!("loop gain {} does not settle.", gain.abs()),
108        location: Located::at(at, None),
109        help: "write self(t - 1sp) for a sampled loop".to_string(),
110    })
111}
112
113/// What one subterm gives: nothing, one scaled delayed read, or a shape no series expands.
114enum Reading {
115    Free,
116    Linear { gain: C64, delay: Delay },
117    Refused(Tap),
118    Nonlinear,
119}
120
121fn read(inst: &Instances, e: &Expr, cx: Cx, gain: C64) -> Reading {
122    if let Some(r) = inst.follow(e, cx, |e2, cx2| read(inst, e2, cx2, gain)) {
123        return r;
124    }
125    match inst.node(e, cx) {
126        Node::Own { arg, .. } => match tap_of(inst, arg, cx) {
127            Tap::At(delay) => Reading::Linear { gain, delay },
128            refused => Reading::Refused(refused),
129        },
130        Node::Bin(op @ (BinOp::Add | BinOp::Sub), l, r) => {
131            let right = if op == BinOp::Sub { -gain } else { gain };
132            join(read(inst, l, cx, gain), read(inst, r, cx, right))
133        }
134        Node::Bin(BinOp::Mul, l, r) => match (holds(inst, l, cx), holds(inst, r, cx)) {
135            (false, true) => match constant(inst, l, cx) {
136                Some(k) => read(inst, r, cx, gain * k),
137                None => Reading::Nonlinear,
138            },
139            (true, false) => match constant(inst, r, cx) {
140                Some(k) => read(inst, l, cx, gain * k),
141                None => Reading::Nonlinear,
142            },
143            (false, false) => Reading::Free,
144            (true, true) => Reading::Nonlinear,
145        },
146        Node::Bin(BinOp::Div, l, r) => match (holds(inst, l, cx), holds(inst, r, cx)) {
147            (true, false) => match constant(inst, r, cx) {
148                Some(k) if !k.is_zero() => read(inst, l, cx, gain / k),
149                _ => Reading::Nonlinear,
150            },
151            (false, false) => Reading::Free,
152            _ => Reading::Nonlinear,
153        },
154        other => match holds_in(inst, &other, cx) {
155            true => Reading::Nonlinear,
156            false => Reading::Free,
157        },
158    }
159}
160
161fn join(a: Reading, b: Reading) -> Reading {
162    match (a, b) {
163        (Reading::Refused(tap), _) | (_, Reading::Refused(tap)) => Reading::Refused(tap),
164        (Reading::Nonlinear, _) | (_, Reading::Nonlinear) => Reading::Nonlinear,
165        (Reading::Free, other) | (other, Reading::Free) => other,
166        (
167            Reading::Linear {
168                gain: g1,
169                delay: d1,
170            },
171            Reading::Linear {
172                gain: g2,
173                delay: d2,
174            },
175        ) if d1 == d2 => Reading::Linear {
176            gain: g1 + g2,
177            delay: d1,
178        },
179        _ => Reading::Nonlinear,
180    }
181}
182
183fn holds(inst: &Instances, e: &Expr, cx: Cx) -> bool {
184    holds_in(inst, &inst.node(e, cx), cx) || inst.holds_self(e, cx)
185}
186
187fn holds_in(inst: &Instances, node: &Node, cx: Cx) -> bool {
188    match node {
189        Node::Own { .. } => true,
190        Node::Read { arg, .. } => inst.holds_self(arg, cx),
191        Node::Call { args, .. } => args.iter().any(|a| {
192            let (sva_ast::Arg::Pos(x) | sva_ast::Arg::Named(_, x)) = a;
193            inst.holds_self(x, cx)
194        }),
195        Node::Bin(_, l, r) => inst.holds_self(l, cx) || inst.holds_self(r, cx),
196        Node::Lit(_) | Node::Name(_) => false,
197    }
198}
199
200fn constant(inst: &Instances, e: &Expr, cx: Cx) -> Option<C64> {
201    plain(amount(inst, e, cx)?).map(C64::real)
202}
203
204/// `sum(k, 0, inf, g^k * rest(t - k*d))`, with the shift written into the body and the
205/// product distributed, so each addend of the body is one readable wave.
206pub(crate) fn neumann(rest: &Body, gain: C64, delay: f64, index: IndexId) -> Body {
207    let log = C64::new(gain.abs().ln(), gain.im.atan2(gain.re));
208    let power = Body::Apply(
209        sva_formula::Unary::Exp,
210        Part::bare(Body::Mul(vec![
211            Part::bare(Body::Index(index)),
212            Part::bare(Body::Const(log)),
213        ])),
214    );
215    let addends: Vec<&Body> = match rest {
216        Body::Add(parts) => parts.iter().map(|p| &*p.body).collect(),
217        other => vec![other],
218    };
219    let scaled: Vec<Part> = addends
220        .into_iter()
221        .map(|addend| {
222            Part::bare(Body::Mul(vec![
223                Part::bare(power.clone()),
224                Part::bare(moved(addend, index, delay)),
225            ]))
226        })
227        .collect();
228    let term = match scaled.as_slice() {
229        [only] => (*only.body).clone(),
230        _ => Body::Add(scaled),
231    };
232    Body::Series(Box::new(Series {
233        index,
234        lo: 0,
235        hi: sva_formula::Bound::Infinite,
236        term: Part::bare(term),
237    }))
238}
239
240/// `t -> t - k*d`, windows and all.
241fn moved(f: &Body, index: IndexId, delay: f64) -> Body {
242    let at = Body::Add(vec![
243        Part::bare(Body::Line),
244        Part::bare(Body::Mul(vec![
245            Part::bare(Body::Const(C64::real(-delay))),
246            Part::bare(Body::Index(index)),
247        ])),
248    ]);
249    read_at(f, &at)
250}
251
252/// A series term holds the body inline, so a node left inside it would normalize to nothing.
253pub(crate) fn expandable(
254    f: &Body,
255    var: Var,
256    of: &dyn Fn(sva_formula::NodeId) -> Option<(Body, Var)>,
257) -> Option<Body> {
258    match f {
259        Body::Node(id) => {
260            let (body, held) = of(*id)?;
261            match held == var {
262                true => expandable(&body, var, of),
263                false => None,
264            }
265        }
266        other => {
267            let mut ok = true;
268            let out = map_children(other, |p| match expandable(&p.body, var, of) {
269                Some(body) => Part::new(p.origin, body),
270                None => {
271                    ok = false;
272                    p.clone()
273                }
274            });
275            ok.then_some(out)
276        }
277    }
278}
279
280/// A read at the sample being written, at a constant delay in seconds, or at whole steps.
281#[derive(Clone, Copy, Debug, PartialEq)]
282pub enum Shift {
283    Now,
284    Secs(f64),
285    Steps(f64),
286}
287
288/// `t` offset by a constant is the whole grammar of a read's time; the constant may be
289/// written in seconds or in grid steps, but never in both.
290pub fn shift_of(inst: &Instances, e: &Expr, cx: Cx) -> Option<Shift> {
291    let (time, secs, steps) = walk(inst, e, cx, 1.0)?;
292    if !time {
293        return None;
294    }
295    match (secs, steps) {
296        (0.0, 0.0) => Some(Shift::Now),
297        (secs, 0.0) => Some(Shift::Secs(-secs)),
298        (0.0, steps) => Some(Shift::Steps(-steps)),
299        _ => None,
300    }
301}
302
303/// `(reads t, seconds offset, grid-step offset)`, signed as written.
304fn walk(inst: &Instances, e: &Expr, cx: Cx, sign: f64) -> Option<(bool, f64, f64)> {
305    if let Some(r) = inst.follow(e, cx, |e2, cx2| walk(inst, e2, cx2, sign)) {
306        return r;
307    }
308    match inst.node(e, cx) {
309        Node::Name("t") => Some((true, 0.0, 0.0)),
310        Node::Bin(op @ (BinOp::Add | BinOp::Sub), l, r) => {
311            let (lt, ls, lg) = walk(inst, l, cx, sign)?;
312            let flip = if op == BinOp::Sub { -sign } else { sign };
313            let (rt, rs, rg) = walk(inst, r, cx, flip)?;
314            Some((lt || rt, ls + rs, lg + rg))
315        }
316        _ => {
317            let (secs, steps) = amount(inst, e, cx)?;
318            Some((false, sign * secs, sign * steps))
319        }
320    }
321}
322
323/// A written duration over every operator FORMAT 3.3 folds, seconds and grid steps kept
324/// apart. What this drops is defaulted, never refused.
325pub(crate) fn amount(inst: &Instances, e: &Expr, cx: Cx) -> Option<(f64, f64)> {
326    folded(inst, e, cx, &mut None)
327}
328
329/// `amount`, noting each `min`/`max` written in the text it starts in.
330pub(crate) fn amount_choosing(
331    inst: &Instances,
332    e: &Expr,
333    cx: Cx,
334    chosen: &mut Vec<Chosen>,
335) -> Option<(f64, f64)> {
336    folded(inst, e, cx, &mut Some(chosen))
337}
338
339/// A followed name continues in another text, with spans of its own.
340fn folded(
341    inst: &Instances,
342    e: &Expr,
343    cx: Cx,
344    chosen: &mut Option<&mut Vec<Chosen>>,
345) -> Option<(f64, f64)> {
346    if let Some(r) = inst.follow(e, cx, |e2, cx2| folded(inst, e2, cx2, &mut None)) {
347        return r;
348    }
349    match inst.node(e, cx) {
350        Node::Lit(Literal::Num(n)) => Some((*n, 0.0)),
351        Node::Lit(Literal::Samples(n)) => Some((0.0, *n)),
352        Node::Name("pi") => Some((std::f64::consts::PI, 0.0)),
353        Node::Name(other) => sva_formula::note::frequency(other).map(|hz| (hz, 0.0)),
354        Node::Bin(op, l, r) => {
355            let (a, b) = (folded(inst, l, cx, chosen)?, folded(inst, r, cx, chosen)?);
356            Some(match op {
357                BinOp::Add => (a.0 + b.0, a.1 + b.1),
358                BinOp::Sub => (a.0 - b.0, a.1 - b.1),
359                BinOp::Mul => scaled(a, b)?,
360                BinOp::Div => {
361                    let by = plain(b)?;
362                    (a.0 / by, a.1 / by)
363                }
364                BinOp::Mod => (crate::lower::constant_modulo(plain(a)?, plain(b)?)?, 0.0),
365            })
366        }
367        Node::Call { name, args, span } => called(inst, (name, span), args, cx, chosen),
368        // FORMAT 15.3: a ref naming one number is that number, read at bare `t`.
369        Node::Read { path, arg, .. } if inst.is_now(arg, cx) => {
370            let (body, held) = inst.at(path)?;
371            folded(inst, body, held, &mut None)
372        }
373        _ => None,
374    }
375}
376
377/// One side of a product carries the unit and the other is the plain number scaling it.
378fn scaled(a: (f64, f64), b: (f64, f64)) -> Option<(f64, f64)> {
379    match (plain(a), plain(b)) {
380        (Some(k), _) => Some((k * b.0, k * b.1)),
381        (_, Some(k)) => Some((k * a.0, k * a.1)),
382        _ => None,
383    }
384}
385
386fn called(
387    inst: &Instances,
388    (name, at): (&str, ByteSpan),
389    args: &[Arg],
390    cx: Cx,
391    chosen: &mut Option<&mut Vec<Chosen>>,
392) -> Option<(f64, f64)> {
393    let mut positional = Vec::new();
394    let mut named = Vec::new();
395    for arg in args {
396        match arg {
397            Arg::Pos(x) => positional.push(plain(folded(inst, x, cx, chosen)?)?),
398            Arg::Named(key, x) => {
399                named.push((key.as_str(), plain(folded(inst, x, cx, chosen)?)?));
400            }
401        }
402    }
403    let n = crate::lower::constant_call(name, &positional, &named)?;
404    let won = positional.iter().position(|v| v.to_bits() == n.to_bits());
405    if let (Some(held), "min" | "max", Some(won)) = (chosen.as_mut(), name, won) {
406        held.push(Chosen {
407            name: name.to_string(),
408            at,
409            operands: positional,
410            chosen: won,
411        });
412    }
413    Some((n, 0.0))
414}
415
416pub(crate) fn plain(amount: (f64, f64)) -> Option<f64> {
417    (amount.1 == 0.0 && amount.0.is_finite()).then_some(amount.0)
418}
sva_engine/loops.rs

sva_engine/
loops.rs
