sva_engine/typing/
mod.rs

1// Concern: gives every node one Ty and the value it lowered to | Non-concern: the per-term judgment (sva-formula), lowering (lower/) | IO: (Instances, Order) -> Ty per node
2
3mod draft;
4mod folds;
5
6use std::collections::{BTreeMap, BTreeSet};
7use std::sync::Arc;
8
9use sva_formula::filter::Shape;
10use sva_formula::{ClosedForm, Codomain, Env, Held, NodeId, Origin, ParamId, Ty, Var, infer};
11use sva_samples::Params;
12
13use crate::arguments::{Arguments, Called, Chosen};
14use crate::cast::Cast;
15use crate::error::{Diagnostic, EngineError, Located};
16use crate::instantiate::Instances;
17use crate::lower;
18use crate::schedule::Order;
19use crate::time::Grid;
20
21use draft::{Draft, Entry, Units};
22
23/// A closed form is cast-free on one axis; every crossing is its own node.
24#[derive(Clone, Debug, PartialEq)]
25pub enum Value {
26    ClosedForm(ClosedForm),
27    Cast(Cast, NodeId),
28    Op {
29        name: String,
30        args: Vec<NodeId>,
31    },
32    SelfAt {
33        at: When,
34    },
35    Read {
36        source: NodeId,
37        at: When,
38        site: Origin,
39    },
40    Noise(u64),
41    /// A front end's decoded file, read on the grid it was lowered for.
42    Recorded(std::sync::Arc<sva_ast::Recording>),
43    /// The signal and its three arguments, each a node of its own.
44    Filter {
45        shape: Shape,
46        x: NodeId,
47        cutoff: NodeId,
48        q: NodeId,
49        gain: NodeId,
50    },
51    Solver {
52        params: Box<Params>,
53        varying: Vec<(&'static str, NodeId)>,
54    },
55}
56
57/// A read's instant: the exact time `k*t + s` written; a closed form of `t` held as a node;
58/// or an integer each sample evaluates.
59#[derive(Clone, Debug, PartialEq)]
60pub enum When {
61    At(crate::time::Affine),
62    Moving(NodeId),
63    Index(crate::index::Index),
64    Step(Step),
65}
66
67/// An integer no one map spells: exact indices, `idx(time, round)` of a time that moves, and
68/// sums, negations and products of them.
69#[derive(Clone, Debug, PartialEq)]
70pub enum Step {
71    Index(crate::index::Index),
72    Nearest(NodeId, crate::index::Round),
73    Add(Vec<Step>),
74    Neg(Box<Step>),
75    Mul(Vec<Step>),
76}
77
78impl Step {
79    /// Every time that moves in it.
80    pub(crate) fn times(&self, out: &mut Vec<NodeId>) {
81        match self {
82            Step::Index(_) => {}
83            Step::Nearest(time, _) => out.push(*time),
84            Step::Add(parts) | Step::Mul(parts) => parts.iter().for_each(|p| p.times(out)),
85            Step::Neg(p) => p.times(out),
86        }
87    }
88}
89
90impl When {
91    /// Every node it evaluates each sample.
92    pub(crate) fn moving(&self) -> Vec<NodeId> {
93        let mut out = Vec::new();
94        match self {
95            When::Moving(id) => out.push(*id),
96            When::Step(step) => step.times(&mut out),
97            When::At(_) | When::Index(_) => {}
98        }
99        out
100    }
101}
102
103#[derive(Clone, Debug, PartialEq)]
104pub struct Node {
105    pub name: Arc<str>,
106    pub ty: Ty,
107    pub var: Var,
108    pub value: Value,
109    pub grid: Grid,
110}
111
112/// Every node keeps one id while held; a node lowered anew takes a free one.
113#[derive(Clone, Debug, Default, PartialEq)]
114pub struct Typing {
115    nodes: Vec<Option<Node>>,
116    free: Vec<u32>,
117    arguments: BTreeMap<String, Arguments>,
118    by_path: BTreeMap<String, NodeId>,
119    /// Paths `by_path` holds for a file's one instance.
120    aliases: BTreeSet<String>,
121    copies: BTreeMap<String, BTreeMap<Grid, NodeId>>,
122    lowering: BTreeSet<String>,
123    files: BTreeMap<String, Vec<NodeId>>,
124    origins: Vec<Option<(u32, Option<sva_ast::ByteSpan>)>>,
125    free_origins: Vec<u32>,
126    /// Each node name origins mark, and how many.
127    sites: Vec<Option<(String, u32)>>,
128    free_sites: Vec<u32>,
129    site_ids: BTreeMap<String, u32>,
130    pending: BTreeSet<NodeId>,
131    indices: u32,
132    sum: Option<(NodeId, Vec<SumSlot>)>,
133    folds: folds::Folds,
134    /// Each node every held node reads, mapped to those reading it.
135    readers: BTreeMap<NodeId, BTreeSet<NodeId>>,
136    /// Every node the latest draft lowered, in order.
137    lowered: Vec<String>,
138    units: BTreeMap<String, Units>,
139    making: Vec<(Arc<str>, Grid)>,
140    draft: Draft,
141}
142
143/// One term of a stream's note sum: its node, or the hull of the supports of those it retired.
144#[derive(Clone, Copy, Debug, PartialEq)]
145pub(crate) enum SumSlot {
146    Node(NodeId),
147    Retired(sva_samples::Extent),
148}
149
150impl Typing {
151    /// A copy to change while a render still holds this one: the copy takes every fold, and
152    /// this one folds anew.
153    pub(crate) fn parted(&self) -> Typing {
154        let mut copy = self.clone();
155        copy.folds = self.folds.parted();
156        copy
157    }
158
159    /// `node` named by its terms in place.
160    pub(crate) fn name_sum(&mut self, node: NodeId, slots: Vec<SumSlot>) {
161        self.draft.sum = Some(Some((node, slots)));
162        self.forget([node]);
163    }
164
165    /// The folds of each of `changed` and of every node reading one, however far up, let go.
166    pub(crate) fn forget(&mut self, changed: impl IntoIterator<Item = NodeId>) {
167        let mut gone: BTreeSet<NodeId> = changed.into_iter().collect();
168        if gone.is_empty() {
169            return;
170        }
171        let mut open: Vec<NodeId> = gone.iter().copied().collect();
172        while let Some(at) = open.pop() {
173            let summed = self
174                .summed()
175                .filter(|(_, slots)| slots.contains(&SumSlot::Node(at)));
176            let held = self.readers.get(&at).into_iter().flatten().copied();
177            for reader in held.chain(summed.map(|(sum, _)| *sum)) {
178                if gone.insert(reader) {
179                    open.push(reader);
180                }
181            }
182        }
183        self.folds.forget(&gone);
184    }
185
186    /// `node` held at `id` in place of what was, each edge it reads recorded.
187    pub(super) fn place(&mut self, id: NodeId, node: Option<Node>) {
188        if self.nodes[id.0 as usize].is_some() {
189            for read in self.own_edges(id) {
190                if let Some(held) = self.readers.get_mut(&read)
191                    && held.remove(&id)
192                    && held.is_empty()
193                {
194                    self.readers.remove(&read);
195                }
196            }
197        }
198        self.nodes[id.0 as usize] = node;
199        if self.nodes[id.0 as usize].is_some() {
200            for read in self.own_edges(id) {
201                self.readers.entry(read).or_default().insert(id);
202            }
203        }
204    }
205
206    /// Each node whose own value reads `id` one hop up.
207    pub(crate) fn readers_of(&self, id: NodeId) -> impl Iterator<Item = NodeId> + '_ {
208        self.readers.get(&id).into_iter().flatten().copied()
209    }
210
211    fn summed(&self) -> Option<&(NodeId, Vec<SumSlot>)> {
212        match &self.draft.sum {
213            Some(staged) => staged.as_ref(),
214            None => self.sum.as_ref(),
215        }
216    }
217
218    /// The note sum, where it holds a term it retired.
219    pub(crate) fn retired_sum(&self) -> Option<NodeId> {
220        let (sum, slots) = self.summed()?;
221        let retired = slots.iter().any(|slot| matches!(slot, SumSlot::Retired(_)));
222        retired.then_some(*sum)
223    }
224
225    /// The values a node's own value is computed from.
226    pub(crate) fn operands(&self, id: NodeId) -> Vec<NodeId> {
227        match self.value(id) {
228            Value::ClosedForm(form) => crate::refs::nodes_in(&form.body),
229            Value::Cast(_, source) | Value::Read { source, .. } => vec![*source],
230            Value::Op { args, .. } => args.clone(),
231            Value::Filter {
232                x, cutoff, q, gain, ..
233            } => vec![*x, *cutoff, *q, *gain],
234            Value::Solver { varying, .. } => varying.iter().map(|(_, a)| *a).collect(),
235            Value::SelfAt { .. } | Value::Noise(_) | Value::Recorded(_) => Vec::new(),
236        }
237    }
238
239    /// Whether `id` reads `of`, however far down.
240    pub(crate) fn reads(&self, id: NodeId, of: NodeId) -> bool {
241        let (mut open, mut seen) = (vec![id], BTreeSet::new());
242        while let Some(at) = open.pop() {
243            if at == of {
244                return true;
245            }
246            if seen.insert(at) {
247                open.extend(self.edges(at));
248            }
249        }
250        false
251    }
252
253    /// `root` and each node under it that `held` lacks, readers after what they read: a fold
254    /// asked in this order recurses one ref deep.
255    pub(crate) fn unfolded(&self, root: NodeId, held: impl Fn(NodeId) -> bool) -> Vec<NodeId> {
256        self.unfolded_over(root, |id| self.edges(id), held)
257    }
258
259    pub(crate) fn unfolded_over(
260        &self,
261        root: NodeId,
262        reads: impl Fn(NodeId) -> Vec<NodeId>,
263        held: impl Fn(NodeId) -> bool,
264    ) -> Vec<NodeId> {
265        let mut order = Vec::new();
266        let mut seen = BTreeSet::new();
267        let mut open = vec![(root, false)];
268        while let Some((at, read)) = open.pop() {
269            if read {
270                order.push(at);
271                continue;
272            }
273            if held(at) || !seen.insert(at) {
274                continue;
275            }
276            open.push((at, true));
277            open.extend(reads(at).into_iter().rev().map(|n| (n, false)));
278        }
279        order
280    }
281
282    /// Its operands and the times it reads at: the edges its own value holds.
283    fn own_edges(&self, id: NodeId) -> Vec<NodeId> {
284        let mut out = self.operands(id);
285        if let Value::Read { at, .. } | Value::SelfAt { at, .. } = self.value(id) {
286            out.extend(at.moving());
287        }
288        out
289    }
290
291    /// Every edge its identity is hashed over: its own and the note sum's terms.
292    fn edges(&self, id: NodeId) -> Vec<NodeId> {
293        let mut out = self.own_edges(id);
294        let slots = self.sum_slots(id).unwrap_or_default().iter();
295        out.extend(slots.filter_map(|slot| match slot {
296            SumSlot::Node(read) if *read != id => Some(*read),
297            _ => None,
298        }));
299        out
300    }
301
302    pub(crate) fn sum_slots(&self, node: NodeId) -> Option<&[SumSlot]> {
303        self.summed()
304            .filter(|(held, _)| *held == node)
305            .map(|(_, slots)| slots.as_slice())
306    }
307
308    pub(crate) fn lowering(&mut self, path: &str) {
309        self.lowered.push(path.to_string());
310    }
311
312    pub(crate) fn lowered(&self) -> &[String] {
313        &self.lowered
314    }
315
316    pub(crate) fn next_index(&mut self) -> sva_formula::IndexId {
317        self.indices += 1;
318        sva_formula::IndexId(self.indices)
319    }
320
321    /// A call lowered twice is noted once, at its latest lowering.
322    pub(crate) fn note(&mut self, node: &str, call: Option<Called>, chosen: Vec<Chosen>) {
323        let mut held = self.arguments(node).cloned().unwrap_or_else(|| Arguments {
324            node: node.to_string(),
325            ..Arguments::default()
326        });
327        if let Some(call) = call {
328            held.calls
329                .retain(|c| (c.at.start, &c.name) != (call.at.start, &call.name));
330            held.calls.push(call);
331        }
332        for one in chosen {
333            held.chosen.retain(|c| c.at.start != one.at.start);
334            held.chosen.push(one);
335        }
336        let old = self.draft.arguments.insert(node.to_string(), held);
337        self.draft.journal.push(Entry::Noted(node.to_string(), old));
338    }
339
340    pub fn arguments(&self, node: &str) -> Option<&Arguments> {
341        match self.draft.arguments.get(node) {
342            Some(held) => Some(held),
343            None if self.draft.hidden.contains(node) => None,
344            None => self.arguments.get(node),
345        }
346    }
347
348    pub fn ty(&self, n: NodeId) -> Ty {
349        self.at(n).ty
350    }
351
352    pub fn var(&self, n: NodeId) -> Var {
353        self.at(n).var
354    }
355
356    pub fn value(&self, n: NodeId) -> &Value {
357        &self.at(n).value
358    }
359
360    pub fn name(&self, n: NodeId) -> &str {
361        &self.at(n).name
362    }
363
364    pub fn grid(&self, n: NodeId) -> Grid {
365        self.at(n).grid
366    }
367
368    pub(crate) fn copy(&self, path: &str, grid: Grid) -> Option<NodeId> {
369        let key = (path.to_string(), grid);
370        match self.draft.copies.get(&key) {
371            Some(id) => Some(*id),
372            None if self.draft.hidden.contains(path) => None,
373            None => self
374                .copies
375                .get(path)
376                .and_then(|held| held.get(&grid))
377                .copied(),
378        }
379    }
380
381    pub(crate) fn copied(&mut self, path: &str, grid: Grid, id: NodeId) {
382        let key = (path.to_string(), grid);
383        let old = self.draft.copies.insert(key.clone(), id);
384        self.draft.journal.push(Entry::Copy(key, old));
385    }
386
387    /// `false` where a copy of `path` is already being lowered: a loop of refs.
388    pub(crate) fn opened(&mut self, path: &str) -> bool {
389        self.lowering.insert(path.to_string())
390    }
391
392    pub(crate) fn closed(&mut self, path: &str) {
393        self.lowering.remove(path);
394    }
395
396    pub fn at(&self, n: NodeId) -> &Node {
397        self.nodes[n.0 as usize]
398            .as_ref()
399            .expect("a node the typing holds")
400    }
401
402    pub fn ids(&self) -> impl Iterator<Item = NodeId> + '_ {
403        let held = self.nodes.iter().enumerate();
404        held.filter(|(_, n)| n.is_some())
405            .map(|(at, _)| NodeId(at as u32))
406    }
407
408    #[cfg(test)]
409    pub(crate) fn len(&self) -> usize {
410        self.nodes.len() - self.free.len()
411    }
412
413    pub fn id(&self, path: &str) -> Option<NodeId> {
414        match self.draft.by_path.get(path) {
415            Some(id) => Some(*id),
416            None if self.draft.hidden.contains(path) => None,
417            None => self.by_path.get(path).copied(),
418        }
419    }
420
421    /// Every path named, the draft's over the rest.
422    pub fn paths(&self) -> impl Iterator<Item = (&str, NodeId)> {
423        let drafted = self.draft.by_path.iter();
424        let kept = self.by_path.iter().filter(|(path, _)| {
425            !self.draft.hidden.contains(*path) && !self.draft.by_path.contains_key(*path)
426        });
427        let all: BTreeMap<&String, &NodeId> = drafted.chain(kept).collect();
428        all.into_iter().map(|(p, id)| (p.as_str(), *id))
429    }
430
431    /// The node a reading asks for, by instance path or by the file a composer wrote.
432    pub fn resolve(&self, path: &str) -> Result<NodeId, EngineError> {
433        if let Some(id) = self.id(path) {
434            return Ok(id);
435        }
436        let held = self.files.get(path).cloned().unwrap_or_default();
437        let file = path.split_once('(').map(|(file, _)| file);
438        let spelt = file.and_then(|file| self.files.get(file));
439        if let Some(ids) = spelt.filter(|_| held.is_empty()) {
440            let names = ids.iter().map(|id| self.name(*id).to_string()).collect();
441            return Err(EngineError::UnknownInstance(path.to_string(), names));
442        }
443        crate::instantiate::sole(
444            path,
445            held.into_iter()
446                .map(|id| (self.name(id).to_string(), id))
447                .collect(),
448        )
449    }
450
451    /// Every `Origin` a term carries was stamped here.
452    pub fn locate(&self, origin: Origin) -> Located {
453        let held = self.origins.get(origin.token() as usize).copied().flatten();
454        held.and_then(|(site, span)| {
455            let (name, _) = self.sites[site as usize].as_ref()?;
456            Some(Located::at(name.as_str(), span))
457        })
458        .unwrap_or_default()
459    }
460
461    pub(crate) fn mark(&mut self, node: &str, span: Option<sva_ast::ByteSpan>) -> Origin {
462        let site = match self.site_ids.get(node) {
463            Some(&site) => site,
464            None => {
465                let held = Some((node.to_string(), 0));
466                let site = match self.free_sites.pop() {
467                    Some(site) => {
468                        self.sites[site as usize] = held;
469                        site
470                    }
471                    None => {
472                        self.sites.push(held);
473                        (self.sites.len() - 1) as u32
474                    }
475                };
476                self.site_ids.insert(node.to_string(), site);
477                site
478            }
479        };
480        self.sites[site as usize].as_mut().expect("a site").1 += 1;
481        let token = match self.free_origins.pop() {
482            Some(token) => {
483                self.origins[token as usize] = Some((site, span));
484                token
485            }
486            None => {
487                self.origins.push(Some((site, span)));
488                (self.origins.len() - 1) as u32
489            }
490        };
491        let unit = self.unit();
492        self.draft.journal.push(Entry::Origin(token, unit));
493        Origin::new(token)
494    }
495
496    pub(crate) fn seed(&mut self, path: &str, held: Held, grid: Grid) -> NodeId {
497        if let Some(id) = self.id(path) {
498            return id;
499        }
500        let name = self.begin(path, grid);
501        let id = self.push(
502            Node {
503                name,
504                ty: Ty {
505                    dual: held.is_closed_form(),
506                    ..Ty::discrete(held, Codomain::Real)
507                },
508                var: Var::T,
509                value: Value::Op {
510                    name: "loop".to_string(),
511                    args: Vec::new(),
512                },
513                grid,
514            },
515            Some(path),
516        );
517        self.end();
518        self.pending.insert(id);
519        self.draft.journal.push(Entry::Pending(id));
520        id
521    }
522
523    pub(crate) fn pending(&self, id: NodeId) -> bool {
524        self.pending.contains(&id)
525    }
526
527    /// Settles a seed this draft made.
528    pub(crate) fn settle(&mut self, id: NodeId, node: Node) {
529        self.place(id, Some(node));
530        self.pending.remove(&id);
531        self.forget([id]);
532    }
533
534    pub(crate) fn folds(&self) -> &folds::Folds {
535        &self.folds
536    }
537
538    pub(crate) fn alias(&mut self, path: &str, id: NodeId) {
539        let old = self.draft.by_path.insert(path.to_string(), id);
540        self.draft.journal.push(Entry::Path(path.to_string(), old));
541    }
542
543    pub(crate) fn push(&mut self, node: Node, path: Option<&str>) -> NodeId {
544        let id = match self.free.pop() {
545            Some(at) => NodeId(at),
546            None => {
547                self.nodes.push(None);
548                NodeId((self.nodes.len() - 1) as u32)
549            }
550        };
551        self.place(id, Some(node));
552        let unit = self.unit();
553        self.draft.journal.push(Entry::Node(id, unit));
554        if let Some(path) = path {
555            self.alias(path, id);
556        }
557        id
558    }
559
560    /// What is made until `end` is `path`'s, on `grid`.
561    /// The name all it makes until `end` share.
562    pub(crate) fn begin(&mut self, path: &str, grid: Grid) -> Arc<str> {
563        let name: Arc<str> = path.into();
564        self.making.push((Arc::clone(&name), grid));
565        name
566    }
567
568    pub(crate) fn end(&mut self) {
569        self.making.pop();
570    }
571
572    fn unit(&self) -> (Arc<str>, Grid) {
573        self.making
574            .last()
575            .cloned()
576            .unwrap_or_else(|| (Arc::from(""), Grid::of(1)))
577    }
578
579    pub(crate) fn infer_closed_form(&self, form: &ClosedForm) -> Result<Ty, EngineError> {
580        let inferred = crate::refs::read_through(self, |through| {
581            infer(form, &TypedNodesEnv(&self.nodes, through))
582        });
583        inferred.map_err(|r| {
584            EngineError::of_closed_form(
585                &r,
586                self.locate(r.origin),
587                "write the subterm inside sample(...) to leave A deliberately",
588            )
589        })
590    }
591}
592
593struct TypedNodesEnv<'a>(&'a [Option<Node>], &'a dyn sva_formula::Reads);
594
595impl Env for TypedNodesEnv<'_> {
596    fn node(&self, id: NodeId) -> Ty {
597        self.0[id.0 as usize]
598            .as_ref()
599            .expect("a node the typing holds")
600            .ty
601    }
602
603    /// Substituted per instance before a closed form reaches sva-formula, so no term holds one.
604    fn param(&self, _: ParamId) -> Ty {
605        Ty::form(Var::T, true, Codomain::Real)
606    }
607
608    fn reads(&self) -> &dyn sva_formula::Reads {
609        self.1
610    }
611}
612
613/// Dependencies first, so a ref reads a type already decided.
614pub fn infer_all(inst: &Instances, order: &Order) -> Result<Typing, EngineError> {
615    let mut typing = Typing::default();
616    typing.lower(inst, &order.groups, &|_| ())?;
617    typing.commit(inst);
618    Ok(typing)
619}
620
621impl Typing {
622    /// Lowers `groups`, dependencies first, beside what is held, each path hidden first; how
623    /// many paths are lowered is told to `told` group by group.
624    pub(crate) fn lower(
625        &mut self,
626        inst: &Instances,
627        groups: &[Vec<String>],
628        told: &dyn Fn(usize),
629    ) -> Result<(), EngineError> {
630        self.lowered.clear();
631        self.hide(groups.iter().flatten().cloned());
632        let mut typed = 0;
633        for group in groups {
634            typed += group.len();
635            match crate::schedule::is_loop(inst, group) {
636                true => settle_loop(self, inst, group)?,
637                false => {
638                    for path in group {
639                        lower::node(path, inst, self)?;
640                    }
641                }
642            }
643            told(typed);
644        }
645        Ok(())
646    }
647}
648
649const SEEDS: [Held; 2] = [Held::Form(Var::T), Held::Sampled];
650
651/// A group's members type together, so the seed a pass starts from is a guess the pass
652/// either reaches again or replaces with what its members held.
653fn settle_loop(typing: &mut Typing, inst: &Instances, group: &[String]) -> Result<(), EngineError> {
654    let mut seed = SEEDS[0];
655    let mut refusal = None;
656    for _ in 0..=SEEDS.len() {
657        let mark = typing.checkpoint();
658        for path in group {
659            typing.seed(path, seed, inst.grid());
660        }
661        let walked = group
662            .iter()
663            .try_for_each(|path| lower::node(path, inst, typing).map(|_| ()));
664        match walked {
665            Ok(()) => match held_by(typing, group) {
666                reached if reached == seed => return Ok(()),
667                reached => seed = reached,
668            },
669            Err(e) => {
670                refusal = Some(e);
671                seed = elsewhere(seed);
672            }
673        }
674        typing.rollback(mark);
675    }
676    Err(refusal.unwrap_or_else(|| mixed(group)))
677}
678
679/// The seed a refused pass did not try.
680fn elsewhere(seed: Held) -> Held {
681    match seed {
682        Held::Sampled => Held::Form(Var::T),
683        _ => Held::Sampled,
684    }
685}
686
687/// One representation for the whole group: samples where any member reached them.
688fn held_by(typing: &Typing, group: &[String]) -> Held {
689    let sampled = group
690        .iter()
691        .filter_map(|path| typing.id(path))
692        .any(|id| !typing.ty(id).is_closed_form());
693    match sampled {
694        true => Held::Sampled,
695        false => Held::Form(Var::T),
696    }
697}
698
699/// A group that settles in no representation holds both.
700fn mixed(group: &[String]) -> EngineError {
701    let at = group.first().map_or("", String::as_str);
702    EngineError::refused(Diagnostic {
703        code: "type.samples_in_closed_form".to_string(),
704        message: format!(
705            "the loop over `{}` holds a closed form and samples at once.",
706            group.join("`, `")
707        ),
708        location: Located::at(at, None),
709        help: "write sample(...) on the members that are closed forms, so the whole loop runs \
710               on the grid"
711            .to_string(),
712    })
713}
sva_engine/typing/mod.rs

sva_engine/typing/
mod.rs
