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
215/// A name the language answers, so no binding reaches it.
216pub(crate) fn is_free_name(name: &str) -> bool {
217    matches!(name, "t" | "f" | "i" | "pi" | "inf") || note::frequency(name).is_some()
218}
219
220pub fn is_reserved(name: &str) -> bool {
221    is_free_name(name) || name == "self" || is_builtin(name)
222}
223
224impl<'g> Instances<'g> {
225    #[inline]
226    pub(crate) fn binds(&self, scope: ScopeId, name: &str) -> Option<Thunk<'g>> {
227        self.scopes[scope as usize].get(name, packed(name))
228    }
229
230    /// A bound name continues in what it stands for; anything else is read where it stands.
231    #[inline]
232    pub fn follow<'a, R>(
233        &'a self,
234        e: &'a Expr,
235        cx: Cx<'a>,
236        go: impl FnOnce(&'a Expr, Cx<'_>) -> R,
237    ) -> Option<R> {
238        match self.step(e, cx)? {
239            Move::Here(e2, cx2) => Some(go(e2, cx2)),
240            Move::Shifted(e2, scope, when) => {
241                let moved = Time { expr: when, cx };
242                Some(go(
243                    e2,
244                    Cx {
245                        scope,
246                        time: Some(&moved),
247                    },
248                ))
249            }
250        }
251    }
252
253    /// A walk of two at once needs both shifts in one frame, so it cannot take the closure.
254    #[inline(always)]
255    fn step<'a>(&'a self, e: &'a Expr, cx: Cx<'a>) -> Option<Move<'a>> {
256        match e {
257            Expr::Var(name) if name == "t" => cx.time.map(|t| Move::Here(t.expr, t.cx)),
258            Expr::Var(name) => self
259                .binds(cx.scope, name)
260                .map(|b| Move::Here(b.expr, cx.under(b.scope))),
261            Expr::Call { name, args, .. } => {
262                let bound = self.binds(cx.scope, name)?;
263                let [Arg::Pos(when)] = args.as_slice() else {
264                    return None;
265                };
266                Some(Move::Shifted(bound.expr, bound.scope, when))
267            }
268            _ => None,
269        }
270    }
271
272    #[inline]
273    pub fn node<'a>(&'a self, e: &'a Expr, cx: Cx<'_>) -> Node<'a> {
274        match e {
275            Expr::Lit(l) => Node::Lit(l),
276            Expr::Var(name) => Node::Name(name),
277            Expr::Bin(op, l, r) => Node::Bin(*op, l, r),
278            Expr::SelfRef { arg, span } => Node::Own { arg, span: *span },
279            Expr::Ref {
280                path, arg, span, ..
281            } => Node::Read {
282                path: self.site(e, cx.scope, path),
283                arg,
284                span: *span,
285            },
286            Expr::Call { name, args, span } if is_builtin(name) => Node::Call {
287                name,
288                args,
289                span: *span,
290            },
291            Expr::Call { name, span, .. } => Node::Read {
292                path: self.site(e, cx.scope, name),
293                arg: &self.time,
294                span: *span,
295            },
296        }
297    }
298
299    fn site<'a>(&'a self, e: &Expr, scope: ScopeId, written: &'a str) -> &'a str {
300        match self.sites.get(&(std::ptr::from_ref(e) as usize, scope)) {
301            Some(child) => child,
302            None => written,
303        }
304    }
305
306    pub(crate) fn is_now(&self, e: &Expr, cx: Cx) -> bool {
307        if let Some(r) = self.follow(e, cx, |e2, cx2| self.is_now(e2, cx2)) {
308            return r;
309        }
310        matches!(self.node(e, cx), Node::Name(n) if n == "t")
311    }
312
313    pub fn reads_self(&self, path: &str) -> bool {
314        self.at(path).is_some_and(|(e, cx)| self.holds_self(e, cx))
315    }
316
317    pub(crate) fn holds_self(&self, e: &Expr, cx: Cx) -> bool {
318        if let Some(r) = self.follow(e, cx, |e2, cx2| self.holds_self(e2, cx2)) {
319            return r;
320        }
321        match self.node(e, cx) {
322            Node::Lit(_) | Node::Name(_) => false,
323            Node::Own { .. } => true,
324            Node::Bin(_, l, r) => self.holds_self(l, cx) || self.holds_self(r, cx),
325            Node::Read { arg, .. } => self.holds_self(arg, cx),
326            Node::Call { args, .. } => args.iter().any(|a| {
327                let (Arg::Pos(x) | Arg::Named(_, x)) = a;
328                self.holds_self(x, cx)
329            }),
330        }
331    }
332
333    /// A value depending on WHICH sample is written rather than on the time handed to it.
334    pub(crate) fn position_dependent(&self, e: &Expr, cx: Cx) -> Option<String> {
335        if let Some(r) = self.follow(e, cx, |e2, cx2| self.position_dependent(e2, cx2)) {
336            return r;
337        }
338        match self.node(e, cx) {
339            Node::Lit(_) | Node::Name(_) => None,
340            Node::Own { .. } => Some("self".to_string()),
341            Node::Bin(_, l, r) => self
342                .position_dependent(l, cx)
343                .or_else(|| self.position_dependent(r, cx)),
344            Node::Read { arg, .. } => self.position_dependent(arg, cx),
345            Node::Call { name, args, .. } => {
346                if Shape::from_name(name).is_some() || name == "crop" {
347                    return Some(name.to_string());
348                }
349                args.iter().find_map(|a| {
350                    let (Arg::Pos(x) | Arg::Named(_, x)) = a;
351                    self.position_dependent(x, cx)
352                })
353            }
354        }
355    }
356
357    /// Two arguments are one tuple when they MEAN the same, walked both at once.
358    pub(crate) fn same<'x, 'y>(&self, a: &Expr, ax: Cx<'x>, b: &Expr, by: Cx<'y>) -> bool {
359        if let Some(moved) = self.step(a, ax) {
360            return match moved {
361                Move::Here(a2, ax2) => self.same(a2, ax2, b, by),
362                Move::Shifted(a2, scope, when) => {
363                    let moved = Time { expr: when, cx: ax };
364                    self.same(
365                        a2,
366                        Cx {
367                            scope,
368                            time: Some(&moved),
369                        },
370                        b,
371                        by,
372                    )
373                }
374            };
375        }
376        if let Some(moved) = self.step(b, by) {
377            return match moved {
378                Move::Here(b2, by2) => self.same(a, ax, b2, by2),
379                Move::Shifted(b2, scope, when) => {
380                    let moved = Time { expr: when, cx: by };
381                    self.same(
382                        a,
383                        ax,
384                        b2,
385                        Cx {
386                            scope,
387                            time: Some(&moved),
388                        },
389                    )
390                }
391            };
392        }
393        match (self.node(a, ax), self.node(b, by)) {
394            (Node::Lit(x), Node::Lit(y)) => x == y,
395            (Node::Name(x), Node::Name(y)) => x == y,
396            (Node::Bin(o1, l1, r1), Node::Bin(o2, l2, r2)) => {
397                o1 == o2 && self.same(l1, ax, l2, by) && self.same(r1, ax, r2, by)
398            }
399            (Node::Own { arg: x, .. }, Node::Own { arg: y, .. }) => self.same(x, ax, y, by),
400            (
401                Node::Read {
402                    path: p, arg: x, ..
403                },
404                Node::Read {
405                    path: q, arg: y, ..
406                },
407            ) => p == q && self.same(x, ax, y, by),
408            (
409                Node::Call {
410                    name: n1, args: a1, ..
411                },
412                Node::Call {
413                    name: n2, args: a2, ..
414                },
415            ) => {
416                n1 == n2
417                    && a1.len() == a2.len()
418                    && a1.iter().zip(a2).all(|(x, y)| match (x, y) {
419                        (Arg::Pos(x), Arg::Pos(y)) => self.same(x, ax, y, by),
420                        (Arg::Named(k1, x), Arg::Named(k2, y)) => {
421                            k1 == k2 && self.same(x, ax, y, by)
422                        }
423                        _ => false,
424                    })
425            }
426            _ => false,
427        }
428    }
429
430    pub(crate) fn same_binds(&self, scope: ScopeId, binds: &[(String, Thunk<'g>)]) -> bool {
431        let held = &self.scopes[scope as usize].vars;
432        held.len() == binds.len()
433            && held.iter().zip(binds).all(|((k1, v1), (k2, v2))| {
434                k1 == k2 && self.same(v1.expr, Cx::root(v1.scope), v2.expr, Cx::root(v2.scope))
435            })
436    }
437}
sva_engine/instantiate/mod.rs

sva_engine/instantiate/
mod.rs
