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

sva_engine/instantiate/
mod.rs
