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

sva_engine/
loops.rs
