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

sva_engine/instantiate/
mod.rs
