sva_engine/
loops.rs

1// Concern: classifies a self-reference, and folds a read's time or a number to its exact value | Non-concern: running a loop (sva-samples), lowering (lower/) | IO: (body, Cx) -> SelfKind, Affine
2
3use sva_ast::{Address, Arg, BinOp, ByteSpan, Expr, Literal};
4use sva_formula::closed_form::read_at;
5use sva_formula::{Body, C64, IndexId, Part, Series};
6
7use crate::arguments::Chosen;
8use crate::error::{Diagnostic, EngineError, Located};
9use crate::instantiate::{Cx, Instances, Node};
10use crate::time::{Affine, Lattice, Q};
11
12#[derive(Clone, Debug, PartialEq)]
13pub(crate) enum SelfKind {
14    Series {
15        gain: C64,
16        delay: f64,
17    },
18    /// A sequence stepped on the grid its reader induces; `why` names the construct that
19    /// makes it one.
20    Discrete {
21        why: String,
22    },
23    Refuse(Box<EngineError>),
24}
25
26/// Decided before any rate is. One linear `self` a constant delay back at `abs(g) < 1` over a
27/// closed form is continuous, its series. Any other loop is discrete and names why: a call or
28/// product over `self`, a moving or second delay, or `discrete`, samples already in its body.
29pub(crate) fn classify(
30    inst: &Instances,
31    e: &Expr,
32    cx: Cx,
33    at: &str,
34    discrete: Option<String>,
35) -> SelfKind {
36    let (taps, apart) = match read(inst, e, cx, C64::ONE) {
37        Reading::Refused(tap) => {
38            return SelfKind::Refuse(Box::new(
39                tap_refusal(tap, Located::at(at, None)).expect("a refused tap names its reason"),
40            ));
41        }
42        Reading::Nonlinear(why) => return SelfKind::Discrete { why },
43        Reading::Free => (Vec::new(), None),
44        Reading::Linear { taps, apart } => (taps, apart),
45    };
46    match (&discrete, &apart, taps.as_slice()) {
47        (None, None, [(g, Tap::Back(delay))]) if g.abs() < 1.0 => {
48            return SelfKind::Series {
49                gain: *g,
50                delay: delay.to_f64(),
51            };
52        }
53        (None, None, [(g, Tap::Back(_))]) => return SelfKind::Refuse(Box::new(unbounded(*g, at))),
54        (Some(_), None, [(g, Tap::Back(_))]) if g.abs() > 1.0 => {
55            return SelfKind::Refuse(Box::new(unbounded(*g, at)));
56        }
57        _ => {}
58    }
59    let moving = taps
60        .iter()
61        .any(|(_, tap)| *tap == Tap::Moving)
62        .then(|| "a delay that moves".to_string());
63    let second = (taps.len() > 1).then(|| "a second delay of `self`".to_string());
64    let why = moving
65        .or(apart)
66        .or(discrete)
67        .or(second)
68        .expect("a loop that is no series holds what makes it discrete");
69    SelfKind::Discrete { why }
70}
71
72/// What one `self(...)` call site reads: a constant delay back, a time that moves, whole
73/// samples at a delay that moves, or the reason it reads nothing already written.
74#[derive(Clone, Copy, Debug, PartialEq)]
75pub(crate) enum Tap {
76    Back(Q),
77    Moving,
78    Indexed,
79    Zero,
80    Forward,
81}
82
83/// The one reading of a self-reference's time, so classification and lowering cannot drift.
84pub(crate) fn tap_of(inst: &Instances, arg: &Expr, address: Address, cx: Cx) -> Tap {
85    if address == Address::Index {
86        return indexed_tap(inst, arg, cx);
87    }
88    let Some(time) = time_of(inst, arg, cx) else {
89        return Tap::Moving;
90    };
91    if time.scale != Q::ONE {
92        return Tap::Moving;
93    }
94    match time.shift.neg() {
95        d if d.is_zero() => Tap::Zero,
96        d if d > Q::ZERO => Tap::Back(d),
97        _ => Tap::Forward,
98    }
99}
100
101/// A loop steps at the rate in use, so its index reads one delay back or a delay that moves.
102/// An index no one map spells reads as one that moves.
103fn indexed_tap(inst: &Instances, arg: &Expr, cx: Cx) -> Tap {
104    let map = crate::index::read(inst, arg, cx).and_then(|ix| ix.map(cx.grid));
105    let Some(map) = map.filter(|m| m.a == m.d) else {
106        return Tap::Indexed;
107    };
108    match (map.least(), map.lead()) {
109        (_, most) if most > 0 => Tap::Forward,
110        (_, 0) => Tap::Zero,
111        (least, most) if least == most => cx
112            .grid
113            .steps(Q::int(-least))
114            .map_or(Tap::Indexed, Tap::Back),
115        _ => Tap::Indexed,
116    }
117}
118
119pub(crate) fn tap_refusal(tap: Tap, at: Located) -> Option<EngineError> {
120    let (code, message, help) = match tap {
121        Tap::Back(_) | Tap::Moving | Tap::Indexed => return None,
122        Tap::Zero => (
123            "samples.zero_delay_loop",
124            "a loop reaches no sample it has already written.",
125            "write self[idx(t) - 1] for a one-step loop",
126        ),
127        Tap::Forward => (
128            "engine.forward_self_read",
129            "a loop reads its own output before it is written.",
130            "read an earlier sample, as in self[idx(t) - 1]",
131        ),
132    };
133    Some(EngineError::refused(Diagnostic {
134        code: code.to_string(),
135        message: message.to_string(),
136        location: at,
137        help: help.to_string(),
138    }))
139}
140
141fn unbounded(gain: C64, at: &str) -> EngineError {
142    EngineError::refused(Diagnostic {
143        code: "type.self_gain_unbounded".to_string(),
144        message: format!("loop gain {} does not settle.", gain.abs()),
145        location: Located::at(at, None),
146        help: "write a gain under 1, or step a running sum as a discrete loop, as in \
147               self[idx(t) - 1]"
148            .to_string(),
149    })
150}
151
152/// What one subterm gives: nothing, scaled reads of `self`, or a construct no series spells,
153/// named. A component taken or joined keeps its taps, but `apart` names the call that took
154/// them out of one series.
155enum Reading {
156    Free,
157    Linear {
158        taps: Vec<(C64, Tap)>,
159        apart: Option<String>,
160    },
161    Refused(Tap),
162    Nonlinear(String),
163}
164
165fn read(inst: &Instances, e: &Expr, cx: Cx, gain: C64) -> Reading {
166    if let Some(r) = inst.follow(e, cx, |e2, cx2| read(inst, e2, cx2, gain)) {
167        return r;
168    }
169    let product = || Reading::Nonlinear("`self` times a factor that moves".to_string());
170    match inst.node(e, cx) {
171        Node::Own { arg, address, .. } => match tap_of(inst, arg, address, cx) {
172            tap @ (Tap::Back(_) | Tap::Moving | Tap::Indexed) => Reading::Linear {
173                taps: vec![(gain, tap)],
174                apart: None,
175            },
176            refused => Reading::Refused(refused),
177        },
178        Node::Bin(op @ (BinOp::Add | BinOp::Sub), l, r) => {
179            let right = if op == BinOp::Sub { -gain } else { gain };
180            join(read(inst, l, cx, gain), read(inst, r, cx, right))
181        }
182        Node::Bin(BinOp::Mul, l, r) => match (holds(inst, l, cx), holds(inst, r, cx)) {
183            (false, true) => match constant(inst, l, cx) {
184                Some(k) => read(inst, r, cx, gain * k),
185                None => product(),
186            },
187            (true, false) => match constant(inst, r, cx) {
188                Some(k) => read(inst, l, cx, gain * k),
189                None => product(),
190            },
191            (false, false) => Reading::Free,
192            (true, true) => product(),
193        },
194        Node::Bin(BinOp::Div, l, r) => match (holds(inst, l, cx), holds(inst, r, cx)) {
195            (true, false) => match constant(inst, r, cx) {
196                Some(k) if !k.is_zero() => read(inst, l, cx, gain / k),
197                _ => Reading::Nonlinear("`self` over a divisor that moves".to_string()),
198            },
199            (false, false) => Reading::Free,
200            _ => Reading::Nonlinear("a division by `self`".to_string()),
201        },
202        Node::Call { name, args, .. } if name == sva_ast::CHANNEL => match args {
203            [Arg::Pos(x), Arg::Pos(k)] if !holds(inst, k, cx) => {
204                opaque(read(inst, x, cx, gain), name)
205            }
206            _ => construct(name),
207        },
208        Node::Call { name, args, .. } if name == sva_ast::JOIN => args
209            .iter()
210            .map(|a| match a {
211                Arg::Pos(x) => opaque(read(inst, x, cx, gain), name),
212                Arg::Named(..) => construct(name),
213            })
214            .fold(Reading::Free, join),
215        other => match (holds_in(inst, &other, cx), &other) {
216            (false, _) => Reading::Free,
217            (true, Node::Call { name, .. }) => construct(name),
218            (true, Node::Read { path, .. }) => {
219                Reading::Nonlinear(format!("`@{path}` read at a time `self` moves"))
220            }
221            (true, Node::Signal { name, .. }) => {
222                Reading::Nonlinear(format!("`{name}` read at an index `self` moves"))
223            }
224            (true, _) => Reading::Nonlinear("`%` over `self`".to_string()),
225        },
226    }
227}
228
229/// A call over the loop's own past: a filter, which holds state of its own, or any other,
230/// which no series expands.
231fn construct(name: &str) -> Reading {
232    Reading::Nonlinear(match crate::vocabulary::shape(name) {
233        Some(_) => format!("the filter `{name}(...)`"),
234        None => format!("`{name}(...)` over `self`"),
235    })
236}
237
238fn opaque(r: Reading, by: &str) -> Reading {
239    match r {
240        Reading::Linear { taps, apart } => Reading::Linear {
241            taps,
242            apart: apart.or_else(|| Some(format!("`{by}(...)` over `self`"))),
243        },
244        other => other,
245    }
246}
247
248fn join(a: Reading, b: Reading) -> Reading {
249    match (a, b) {
250        (Reading::Refused(tap), _) | (_, Reading::Refused(tap)) => Reading::Refused(tap),
251        (Reading::Nonlinear(why), _) | (_, Reading::Nonlinear(why)) => Reading::Nonlinear(why),
252        (Reading::Free, other) | (other, Reading::Free) => other,
253        (
254            Reading::Linear {
255                taps: mut held,
256                apart: a1,
257            },
258            Reading::Linear {
259                taps: more,
260                apart: a2,
261            },
262        ) => {
263            for (g, tap) in more {
264                match held
265                    .iter_mut()
266                    .find(|(_, t)| *t == tap && matches!(tap, Tap::Back(_)))
267                {
268                    Some((sum, _)) => *sum = *sum + g,
269                    None => held.push((g, tap)),
270                }
271            }
272            Reading::Linear {
273                taps: held,
274                apart: a1.or(a2),
275            }
276        }
277    }
278}
279
280fn holds(inst: &Instances, e: &Expr, cx: Cx) -> bool {
281    holds_in(inst, &inst.node(e, cx), cx) || inst.holds_self(e, cx)
282}
283
284fn holds_in(inst: &Instances, node: &Node, cx: Cx) -> bool {
285    match node {
286        Node::Own { .. } => true,
287        Node::Read { arg, .. } | Node::Signal { arg, .. } => inst.holds_self(arg, cx),
288        Node::Call { args, .. } => args.iter().any(|a| {
289            let (sva_ast::Arg::Pos(x) | sva_ast::Arg::Named(_, x)) = a;
290            inst.holds_self(x, cx)
291        }),
292        Node::Bin(_, l, r) => inst.holds_self(l, cx) || inst.holds_self(r, cx),
293        Node::Lit(_) | Node::Name(_) => false,
294    }
295}
296
297fn constant(inst: &Instances, e: &Expr, cx: Cx) -> Option<C64> {
298    plain(amount(inst, e, cx)?).map(C64::real)
299}
300
301/// `sum(k, 0, inf, g^k * rest(t - k*d))`, with the shift written into the body and the
302/// product distributed, so each addend of the body is one readable wave.
303pub(crate) fn neumann(rest: &Body, gain: C64, delay: f64, index: IndexId) -> Body {
304    let log = C64::new(gain.abs().ln(), gain.im.atan2(gain.re));
305    let power = Body::Apply(
306        sva_formula::Unary::Exp,
307        Part::bare(Body::Mul(vec![
308            Part::bare(Body::Index(index)),
309            Part::bare(Body::Const(log)),
310        ])),
311    );
312    let addends: Vec<&Body> = match rest {
313        Body::Add(parts) => parts.iter().map(|p| &*p.body).collect(),
314        other => vec![other],
315    };
316    let scaled: Vec<Part> = addends
317        .into_iter()
318        .map(|addend| {
319            Part::bare(Body::Mul(vec![
320                Part::bare(power.clone()),
321                Part::bare(moved(addend, index, delay)),
322            ]))
323        })
324        .collect();
325    let term = match scaled.as_slice() {
326        [only] => (*only.body).clone(),
327        _ => Body::Add(scaled),
328    };
329    Body::Series(Box::new(Series {
330        index,
331        lo: 0,
332        hi: sva_formula::Bound::Infinite,
333        term: Part::bare(term),
334    }))
335}
336
337/// `t -> t - k*d`, windows and all.
338fn moved(f: &Body, index: IndexId, delay: f64) -> Body {
339    let at = Body::Add(vec![
340        Part::bare(Body::Line),
341        Part::bare(Body::Mul(vec![
342            Part::bare(Body::Const(C64::real(-delay))),
343            Part::bare(Body::Index(index)),
344        ])),
345    ]);
346    read_at(f, &at)
347}
348
349/// `t` scaled by a constant and moved by constants, each exact; `None` where the time is no
350/// such line, or where a constant in it has no exact value.
351pub fn time_of(inst: &Instances, e: &Expr, cx: Cx) -> Option<Affine> {
352    match walk(inst, e, cx)? {
353        Term::Line(line) => Some(line),
354        Term::Number(shift) => Some(Affine {
355            scale: Q::ZERO,
356            shift,
357        }),
358    }
359}
360
361/// A term of a time: a line in `t`, or one exact number.
362enum Term {
363    Line(Affine),
364    Number(Q),
365}
366
367impl Term {
368    fn parts(&self) -> (Q, Q) {
369        match self {
370            Term::Line(a) => (a.scale, a.shift),
371            Term::Number(q) => (Q::ZERO, *q),
372        }
373    }
374
375    fn of(scale: Q, shift: Q) -> Term {
376        match scale.is_zero() {
377            true => Term::Number(shift),
378            false => Term::Line(Affine { scale, shift }),
379        }
380    }
381}
382
383fn walk(inst: &Instances, e: &Expr, cx: Cx) -> Option<Term> {
384    if let Some(r) = inst.follow(e, cx, |e2, cx2| walk(inst, e2, cx2)) {
385        return r;
386    }
387    match inst.node(e, cx) {
388        Node::Name("t") => Some(Term::Line(Affine::NOW)),
389        Node::Bin(op @ (BinOp::Add | BinOp::Sub), l, r) => {
390            let ((a, b), (c, d)) = (walk(inst, l, cx)?.parts(), walk(inst, r, cx)?.parts());
391            let (c, d) = match op {
392                BinOp::Sub => (c.neg(), d.neg()),
393                _ => (c, d),
394            };
395            Some(Term::of(a.add(c)?, b.add(d)?))
396        }
397        Node::Bin(BinOp::Mul, l, r) => match (walk(inst, l, cx)?, walk(inst, r, cx)?) {
398            (Term::Number(k), other) | (other, Term::Number(k)) => {
399                let (a, b) = other.parts();
400                Some(Term::of(a.mul(k)?, b.mul(k)?))
401            }
402            _ => None,
403        },
404        Node::Bin(BinOp::Div, l, r) => {
405            let Term::Number(by) = walk(inst, r, cx)? else {
406                return None;
407            };
408            let (a, b) = walk(inst, l, cx)?.parts();
409            Some(Term::of(a.div(by)?, b.div(by)?))
410        }
411        Node::Bin(BinOp::Mod, l, r) => match (walk(inst, l, cx)?, walk(inst, r, cx)?) {
412            (Term::Number(a), Term::Number(b)) => Some(Term::Number(a.rem(b)?)),
413            _ => None,
414        },
415        Node::Lit(Literal::Num(n)) => Q::decimal(*n).map(Term::Number),
416        Node::Lit(Literal::Samples(n)) => Some(Term::Number(cx.grid.steps(Q::decimal(*n)?)?)),
417        _ => Q::decimal(plain(amount(inst, e, cx)?)?).map(Term::Number),
418    }
419}
420
421/// A written number over every operator FORMAT 3.3 folds. What this drops is defaulted, never
422/// refused.
423pub(crate) fn amount(inst: &Instances, e: &Expr, cx: Cx) -> Option<f64> {
424    folded(inst, e, cx, &mut None)
425}
426
427/// `amount`, noting each `min`/`max` written in the text it starts in.
428pub(crate) fn amount_choosing(
429    inst: &Instances,
430    e: &Expr,
431    cx: Cx,
432    chosen: &mut Vec<Chosen>,
433) -> Option<f64> {
434    folded(inst, e, cx, &mut Some(chosen))
435}
436
437/// A followed name continues in another text, with spans of its own.
438fn folded(
439    inst: &Instances,
440    e: &Expr,
441    cx: Cx,
442    chosen: &mut Option<&mut Vec<Chosen>>,
443) -> Option<f64> {
444    if let Some(r) = inst.follow(e, cx, |e2, cx2| folded(inst, e2, cx2, &mut None)) {
445        return r;
446    }
447    match inst.node(e, cx) {
448        Node::Lit(Literal::Num(n)) => Some(*n),
449        Node::Lit(Literal::Samples(n)) => Some(cx.grid.steps_f64(*n)),
450        Node::Name("pi") => Some(std::f64::consts::PI),
451        Node::Name("inf") => Some(f64::INFINITY),
452        Node::Name(other) => crate::vocabulary::note_hz(other),
453        Node::Bin(op, l, r) => {
454            let (a, b) = (folded(inst, l, cx, chosen)?, folded(inst, r, cx, chosen)?);
455            Some(match op {
456                BinOp::Add => a + b,
457                BinOp::Sub => a - b,
458                BinOp::Mul => a * b,
459                BinOp::Div => a / b,
460                BinOp::Mod => crate::lower::constant_modulo(a, b)?,
461            })
462        }
463        Node::Call { name, args, span } => called(inst, (name, span), args, cx, chosen),
464        // FORMAT 15.3: a ref naming one number is that number, read at bare `t`.
465        Node::Read {
466            path,
467            arg,
468            address: Address::Time,
469            ..
470        } if inst.is_now(arg, cx) => {
471            let (body, held) = inst.at(path)?;
472            folded(inst, body, held, &mut None)
473        }
474        _ => None,
475    }
476}
477
478fn called(
479    inst: &Instances,
480    (name, at): (&str, ByteSpan),
481    args: &[Arg],
482    cx: Cx,
483    chosen: &mut Option<&mut Vec<Chosen>>,
484) -> Option<f64> {
485    if name == "rand" {
486        return drawn(inst, args, cx);
487    }
488    let mut positional = Vec::new();
489    let mut named = Vec::new();
490    for arg in args {
491        match arg {
492            Arg::Pos(x) => positional.push(folded(inst, x, cx, chosen)?),
493            Arg::Named(key, x) => named.push((key.as_str(), folded(inst, x, cx, chosen)?)),
494        }
495    }
496    let n = crate::lower::constant_call(name, &positional, &named)?;
497    let won = positional.iter().position(|v| v.to_bits() == n.to_bits());
498    if let (Some(held), "min" | "max", Some(won)) = (chosen.as_mut(), name, won) {
499        held.push(Chosen {
500            name: name.to_string(),
501            at,
502            operands: positional,
503            chosen: won,
504        });
505    }
506    Some(n)
507}
508
509/// A constant key is one instant of the noise, read there.
510fn drawn(inst: &Instances, args: &[Arg], cx: Cx) -> Option<f64> {
511    let (key, seed) = crate::lower::rand_arguments(args, |x| amount(inst, x, cx))?;
512    let at = time_of(inst, key, cx)?;
513    at.scale
514        .is_zero()
515        .then(|| crate::lower::noise_at(seed, at.shift, inst.rate()))
516}
517
518pub(crate) fn plain(amount: f64) -> Option<f64> {
519    amount.is_finite().then_some(amount)
520}
sva_engine/loops.rs

sva_engine/
loops.rs
