sva_engine/instantiate/
mod.rs

1// Concern: holds one instance per argument tuple and resolves a name inside one | Non-concern: building the table (build.rs), writing a resolved walk out (resolved.rs) | IO: (path) -> a body, a Node
2
3mod build;
4mod resolved;
5
6use std::collections::{BTreeMap, HashMap};
7
8use sva_ast::{Address, Arg, BinOp, ByteSpan, Expr, Literal};
9use sva_formula::filter::Shape;
10use sva_formula::note;
11
12use crate::error::EngineError;
13use crate::time::Grid;
14use crate::vocabulary::is_builtin;
15
16pub use build::{from_roots, has_free_parameter, instantiate};
17
18pub(crate) type ScopeId = u32;
19
20/// Scope 0 binds nothing, reserved for defaults: a default stands outside every invocation.
21pub(crate) const NO_PARAMS: ScopeId = 0;
22
23#[derive(Clone, Copy, Debug)]
24pub struct Thunk<'g> {
25    pub(crate) expr: &'g Expr,
26    pub(crate) scope: ScopeId,
27}
28
29/// Sorted by name: the tuple names the instance, not the call order.
30#[derive(Debug)]
31pub(crate) struct Scope<'g> {
32    pub(crate) vars: Vec<(String, Thunk<'g>)>,
33    keys: Vec<u64>,
34    seen: u64,
35}
36
37/// A name's length and first seven bytes in one word, so a lookup costs integer compares.
38#[inline]
39pub(crate) fn packed(name: &str) -> u64 {
40    let bytes = name.as_bytes();
41    let mut key = (bytes.len() as u64) << 56;
42    for (at, byte) in bytes.iter().take(7).enumerate() {
43        key |= u64::from(*byte) << (at * 8);
44    }
45    key
46}
47
48#[inline]
49fn bit(key: u64) -> u64 {
50    1u64 << ((key ^ (key >> 32)) & 63)
51}
52
53impl<'g> Scope<'g> {
54    pub(crate) fn new(vars: Vec<(String, Thunk<'g>)>) -> Scope<'g> {
55        let keys: Vec<u64> = vars.iter().map(|(k, _)| packed(k)).collect();
56        let seen = keys.iter().fold(0, |acc, k| acc | bit(*k));
57        Scope { vars, keys, seen }
58    }
59
60    /// One bit says no before a key is read. Two names of a length share a key past the
61    /// seventh byte, so every match is offered the name.
62    #[inline]
63    pub(crate) fn get(&self, name: &str, key: u64) -> Option<Thunk<'g>> {
64        if self.seen & bit(key) == 0 {
65            return None;
66        }
67        self.keys
68            .iter()
69            .enumerate()
70            .find(|(at, k)| **k == key && (name.len() <= 7 || self.vars[*at].0 == name))
71            .map(|(at, _)| self.vars[at].1)
72    }
73}
74
75/// `time` is DYNAMIC: `p(t - d)` moves every `t` under the parameter, however deep. `sp` is a
76/// step of `grid`.
77#[derive(Clone, Copy)]
78pub struct Cx<'a> {
79    pub(crate) scope: ScopeId,
80    pub(crate) time: Option<&'a Time<'a>>,
81    pub(crate) grid: Grid,
82}
83
84pub(crate) struct Time<'a> {
85    pub(crate) expr: &'a Expr,
86    pub(crate) cx: Cx<'a>,
87}
88
89enum Move<'a> {
90    Here(&'a Expr, Cx<'a>),
91    Shifted(&'a Expr, ScopeId, &'a Expr),
92}
93
94impl<'a> Cx<'a> {
95    pub(crate) fn under(self, scope: ScopeId) -> Cx<'a> {
96        Cx { scope, ..self }
97    }
98
99    pub(crate) fn on(self, grid: Grid) -> Cx<'a> {
100        Cx { grid, ..self }
101    }
102}
103
104/// Read from sva-ast so the two crates cannot resolve a path two ways.
105pub fn resolve_ref_path(referencing: &str, ref_path: &str) -> Result<String, EngineError> {
106    sva_ast::resolve_ref_path(referencing, ref_path)
107        .ok_or_else(|| EngineError::RefAboveRoot(referencing.to_string(), ref_path.to_string()))
108}
109
110/// `@kick.comb(delay=0.03)` is `@comb(t, x=@kick, delay=0.03)`: one name, so a file never
111/// states a parameter order.
112pub const SIGNAL_PARAM: &str = "x";
113
114/// Bounds BREADTH: a chain of functions each invoking the next several times multiplies.
115pub const MAX_INSTANCES: usize = 4096;
116
117/// A `Read` names the child INSTANCE, so this is reachable only past [`Instances::follow`].
118#[derive(Clone, Copy)]
119pub enum Node<'a> {
120    Lit(&'a Literal),
121    Name(&'a str),
122    Bin(BinOp, &'a Expr, &'a Expr),
123    Call {
124        name: &'a str,
125        args: &'a [Arg],
126        span: ByteSpan,
127    },
128    Read {
129        path: &'a str,
130        arg: &'a Expr,
131        address: Address,
132        span: ByteSpan,
133    },
134    Own {
135        arg: &'a Expr,
136        address: Address,
137        span: ByteSpan,
138    },
139    /// `x[i]`: `of`, what `x` is bound to, read at index `arg`.
140    Signal {
141        name: &'a str,
142        of: Thunk<'a>,
143        arg: &'a Expr,
144        span: ByteSpan,
145    },
146}
147
148/// One file's body beside what its parameters stand for: the body is shared, the scope is not.
149#[derive(Debug)]
150pub struct Instances<'g> {
151    pub(crate) scopes: Vec<Scope<'g>>,
152    pub(crate) sites: HashMap<(usize, ScopeId), String>,
153    pub(crate) nodes: BTreeMap<String, Thunk<'g>>,
154    pub(crate) origin: BTreeMap<String, String>,
155    pub(crate) own_terms: BTreeMap<String, String>,
156    pub(crate) root: String,
157    pub(crate) time: Expr,
158    /// The rate in use, whose step `sp` is.
159    pub(crate) rate: u32,
160}
161
162impl<'g> Instances<'g> {
163    pub(crate) fn rate(&self) -> u32 {
164        self.rate
165    }
166
167    pub(crate) fn grid(&self) -> Grid {
168        Grid::of(self.rate)
169    }
170
171    pub(crate) fn cx(&self, scope: ScopeId) -> Cx<'_> {
172        Cx {
173            scope,
174            time: None,
175            grid: self.grid(),
176        }
177    }
178
179    pub fn origin(&self, instance: &str) -> Option<&str> {
180        self.origin.get(instance).map(String::as_str)
181    }
182
183    pub fn paths(&self) -> impl Iterator<Item = &str> {
184        self.nodes.keys().map(String::as_str)
185    }
186
187    pub fn holds(&self, path: &str) -> bool {
188        self.nodes.contains_key(path)
189    }
190
191    /// A bare file name is the file read as a root, on its own terms; a call site's
192    /// instance carries the bindings that made it.
193    pub fn instance_of(&self, target: &str) -> Result<String, EngineError> {
194        if self.holds(target) {
195            return Ok(target.to_string());
196        }
197        if let Some(own) = self.own_terms.get(target) {
198            return Ok(own.clone());
199        }
200        sole(
201            target,
202            self.instances_of(target).map(|p| (p.clone(), p)).collect(),
203        )
204    }
205
206    pub fn instances_of<'a>(&'a self, file: &'a str) -> impl Iterator<Item = String> + 'a {
207        self.paths()
208            .filter(move |p| self.origin(p) == Some(file))
209            .map(str::to_string)
210    }
211
212    pub fn at<'a>(&'a self, path: &str) -> Option<(&'a Expr, Cx<'a>)> {
213        let thunk = *self.nodes.get(path)?;
214        Some((thunk.expr, self.cx(thunk.scope)))
215    }
216
217    pub fn bindings<'a>(&'a self, path: &str) -> Option<Vec<(&'a str, &'a Expr, Cx<'a>)>> {
218        let thunk = *self.nodes.get(path)?;
219        Some(
220            self.scopes[thunk.scope as usize]
221                .vars
222                .iter()
223                .map(|(name, value)| (name.as_str(), value.expr, self.cx(value.scope)))
224                .collect(),
225        )
226    }
227}
228
229/// The one node a written name stands for: a file one argument tuple expanded is that
230/// instance, and a file several tuples share is none of them.
231pub(crate) fn sole<T>(target: &str, mut held: Vec<(String, T)>) -> Result<T, EngineError> {
232    match held.len() {
233        0 => Err(EngineError::UnknownNode(target.to_string())),
234        1 => Ok(held.remove(0).1),
235        _ => Err(EngineError::AmbiguousNode(
236            target.to_string(),
237            held.into_iter().map(|(name, _)| name).collect(),
238        )),
239    }
240}
241
242/// A name the language answers, so no binding reaches it.
243pub(crate) fn is_free_name(name: &str) -> bool {
244    let reserved = crate::vocabulary::RESERVED
245        .iter()
246        .any(|(held, _)| *held == name);
247    (reserved && name != crate::vocabulary::SELF) || note::frequency(name).is_some()
248}
249
250fn implicit_time(name: &str) -> bool {
251    crate::overload::FINITE_DIFFERENCE.contains(&name)
252        || crate::lower::physics::MODAL.contains(&name)
253        || matches!(name, "noise" | "stft" | "istft")
254}
255
256pub fn is_reserved(name: &str) -> bool {
257    is_free_name(name) || name == crate::vocabulary::SELF || is_builtin(name)
258}
259
260impl<'g> Instances<'g> {
261    #[inline]
262    pub(crate) fn binds(&self, scope: ScopeId, name: &str) -> Option<Thunk<'g>> {
263        self.scopes[scope as usize].get(name, packed(name))
264    }
265
266    /// A bound name continues in what it stands for; anything else is read where it stands.
267    #[inline]
268    pub fn follow<'a, R>(
269        &'a self,
270        e: &'a Expr,
271        cx: Cx<'a>,
272        go: impl FnOnce(&'a Expr, Cx<'_>) -> R,
273    ) -> Option<R> {
274        match self.step(e, cx)? {
275            Move::Here(e2, cx2) => Some(go(e2, cx2)),
276            Move::Shifted(e2, scope, when) => {
277                let moved = Time { expr: when, cx };
278                Some(go(
279                    e2,
280                    Cx {
281                        scope,
282                        time: Some(&moved),
283                        grid: cx.grid,
284                    },
285                ))
286            }
287        }
288    }
289
290    /// A walk of two at once needs both shifts in one frame, so it cannot take the closure.
291    #[inline(always)]
292    fn step<'a>(&'a self, e: &'a Expr, cx: Cx<'a>) -> Option<Move<'a>> {
293        match e {
294            Expr::Var(name) if name == "t" => cx.time.map(|t| Move::Here(t.expr, t.cx)),
295            Expr::Var(name) => self
296                .binds(cx.scope, name)
297                .map(|b| Move::Here(b.expr, cx.under(b.scope))),
298            Expr::Call { name, args, .. } => {
299                let bound = self.binds(cx.scope, name)?;
300                let [Arg::Pos(when)] = args.as_slice() else {
301                    return None;
302                };
303                Some(Move::Shifted(bound.expr, bound.scope, when))
304            }
305            _ => None,
306        }
307    }
308
309    #[inline]
310    pub fn node<'a>(&'a self, e: &'a Expr, cx: Cx<'_>) -> Node<'a> {
311        match e {
312            Expr::Lit(l) => Node::Lit(l),
313            Expr::Var(name) => Node::Name(name),
314            Expr::Bin(op, l, r) => Node::Bin(*op, l, r),
315            Expr::SelfRef { arg, address, span } => Node::Own {
316                arg,
317                address: *address,
318                span: *span,
319            },
320            Expr::Ref {
321                path,
322                arg,
323                address,
324                span,
325                ..
326            } => Node::Read {
327                path: self.site(e, cx.scope, path),
328                arg,
329                address: *address,
330                span: *span,
331            },
332            Expr::Indexed { name, arg, span } => match self.binds(cx.scope, name) {
333                Some(of) => Node::Signal {
334                    name,
335                    of,
336                    arg,
337                    span: *span,
338                },
339                None => Node::Name(name),
340            },
341            Expr::Call { name, args, span } if is_builtin(name) => Node::Call {
342                name,
343                args,
344                span: *span,
345            },
346            Expr::Call { name, span, .. } => Node::Read {
347                path: self.site(e, cx.scope, name),
348                arg: &self.time,
349                address: Address::Time,
350                span: *span,
351            },
352        }
353    }
354
355    fn site<'a>(&'a self, e: &Expr, scope: ScopeId, written: &'a str) -> &'a str {
356        match self.sites.get(&(std::ptr::from_ref(e) as usize, scope)) {
357            Some(child) => child,
358            None => written,
359        }
360    }
361
362    /// A parameter's signal at the reader's own `t`: no shift the reader is under moves it.
363    pub(crate) fn signal<'a>(&self, of: Thunk<'a>, cx: Cx<'a>) -> Cx<'a> {
364        Cx {
365            scope: of.scope,
366            time: None,
367            grid: cx.grid,
368        }
369    }
370
371    pub(crate) fn is_now(&self, e: &Expr, cx: Cx) -> bool {
372        if let Some(r) = self.follow(e, cx, |e2, cx2| self.is_now(e2, cx2)) {
373            return r;
374        }
375        matches!(self.node(e, cx), Node::Name(n) if n == "t")
376    }
377
378    pub fn reads_self(&self, path: &str) -> bool {
379        self.at(path).is_some_and(|(e, cx)| self.holds_self(e, cx))
380    }
381
382    pub(crate) fn holds_self(&self, e: &Expr, cx: Cx) -> bool {
383        if let Some(r) = self.follow(e, cx, |e2, cx2| self.holds_self(e2, cx2)) {
384            return r;
385        }
386        match self.node(e, cx) {
387            Node::Lit(_) | Node::Name(_) => false,
388            Node::Own { .. } => true,
389            Node::Bin(_, l, r) => self.holds_self(l, cx) || self.holds_self(r, cx),
390            Node::Read { arg, .. } | Node::Signal { arg, .. } => self.holds_self(arg, cx),
391            Node::Call { args, .. } => args.iter().any(|a| {
392                let (Arg::Pos(x) | Arg::Named(_, x)) = a;
393                self.holds_self(x, cx)
394            }),
395        }
396    }
397
398    /// A value depending on WHICH sample is written rather than on the time handed to it.
399    pub(crate) fn position_dependent(&self, e: &Expr, cx: Cx) -> Option<String> {
400        if let Some(r) = self.follow(e, cx, |e2, cx2| self.position_dependent(e2, cx2)) {
401            return r;
402        }
403        match self.node(e, cx) {
404            Node::Lit(_) | Node::Name(_) => None,
405            Node::Own { .. } => Some("self".to_string()),
406            Node::Bin(_, l, r) => self
407                .position_dependent(l, cx)
408                .or_else(|| self.position_dependent(r, cx)),
409            Node::Read { arg, .. } | Node::Signal { arg, .. } => self.position_dependent(arg, cx),
410            Node::Call { name, args, .. } => {
411                if Shape::from_name(name).is_some() || name == "crop" || implicit_time(name) {
412                    return Some(name.to_string());
413                }
414                args.iter().find_map(|a| {
415                    let (Arg::Pos(x) | Arg::Named(_, x)) = a;
416                    self.position_dependent(x, cx)
417                })
418            }
419        }
420    }
421
422    /// Two arguments are one tuple when they MEAN the same, walked both at once.
423    pub(crate) fn same<'x, 'y>(&self, a: &Expr, ax: Cx<'x>, b: &Expr, by: Cx<'y>) -> bool {
424        if let Some(moved) = self.step(a, ax) {
425            return match moved {
426                Move::Here(a2, ax2) => self.same(a2, ax2, b, by),
427                Move::Shifted(a2, scope, when) => {
428                    let moved = Time { expr: when, cx: ax };
429                    self.same(
430                        a2,
431                        Cx {
432                            scope,
433                            time: Some(&moved),
434                            grid: ax.grid,
435                        },
436                        b,
437                        by,
438                    )
439                }
440            };
441        }
442        if let Some(moved) = self.step(b, by) {
443            return match moved {
444                Move::Here(b2, by2) => self.same(a, ax, b2, by2),
445                Move::Shifted(b2, scope, when) => {
446                    let moved = Time { expr: when, cx: by };
447                    self.same(
448                        a,
449                        ax,
450                        b2,
451                        Cx {
452                            scope,
453                            time: Some(&moved),
454                            grid: by.grid,
455                        },
456                    )
457                }
458            };
459        }
460        match (self.node(a, ax), self.node(b, by)) {
461            (Node::Lit(x), Node::Lit(y)) => x == y,
462            (Node::Name(x), Node::Name(y)) => x == y,
463            (Node::Bin(o1, l1, r1), Node::Bin(o2, l2, r2)) => {
464                o1 == o2 && self.same(l1, ax, l2, by) && self.same(r1, ax, r2, by)
465            }
466            (
467                Node::Own {
468                    arg: x, address: i, ..
469                },
470                Node::Own {
471                    arg: y, address: j, ..
472                },
473            ) => i == j && self.same(x, ax, y, by),
474            (
475                Node::Read {
476                    path: p,
477                    arg: x,
478                    address: i,
479                    ..
480                },
481                Node::Read {
482                    path: q,
483                    arg: y,
484                    address: j,
485                    ..
486                },
487            ) => p == q && i == j && self.same(x, ax, y, by),
488            (Node::Signal { of: f, arg: x, .. }, Node::Signal { of: g, arg: y, .. }) => {
489                self.same(f.expr, self.signal(f, ax), g.expr, self.signal(g, by))
490                    && self.same(x, ax, y, by)
491            }
492            (
493                Node::Call {
494                    name: n1, args: a1, ..
495                },
496                Node::Call {
497                    name: n2, args: a2, ..
498                },
499            ) => {
500                n1 == n2
501                    && a1.len() == a2.len()
502                    && a1.iter().zip(a2).all(|(x, y)| match (x, y) {
503                        (Arg::Pos(x), Arg::Pos(y)) => self.same(x, ax, y, by),
504                        (Arg::Named(k1, x), Arg::Named(k2, y)) => {
505                            k1 == k2 && self.same(x, ax, y, by)
506                        }
507                        _ => false,
508                    })
509            }
510            _ => false,
511        }
512    }
513
514    pub(crate) fn same_binds(&self, scope: ScopeId, binds: &[(String, Thunk<'g>)]) -> bool {
515        let held = &self.scopes[scope as usize].vars;
516        held.len() == binds.len()
517            && held.iter().zip(binds).all(|((k1, v1), (k2, v2))| {
518                k1 == k2 && self.same(v1.expr, self.cx(v1.scope), v2.expr, self.cx(v2.scope))
519            })
520    }
521}
sva_engine/instantiate/mod.rs

sva_engine/instantiate/
mod.rs
