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 carry;
4
5use std::cell::RefCell;
6use std::collections::{BTreeMap, BTreeSet};
7use std::sync::Arc;
8
9use sva_formula::filter::Shape;
10use sva_formula::{C64, ClosedForm, Codomain, Env, Held, NodeId, Origin, ParamId, Ty, Var, infer};
11use sva_samples::Params;
12
13use crate::arguments::{Arguments, Called, Chosen};
14use crate::cache::Stored;
15use crate::cast::Cast;
16use crate::error::{Diagnostic, EngineError, Located};
17use crate::instantiate::Instances;
18use crate::lower;
19use crate::schedule::Order;
20use crate::time::Grid;
21
22use carry::Span;
23pub(crate) use carry::{Carried, Prior};
24
25/// A closed form is cast-free on one axis; every crossing is its own node.
26#[derive(Clone, Debug, PartialEq)]
27pub enum Value {
28    ClosedForm(ClosedForm),
29    Cast(Cast, NodeId),
30    Op {
31        name: String,
32        args: Vec<NodeId>,
33    },
34    SelfAt {
35        at: When,
36    },
37    Read {
38        source: NodeId,
39        at: When,
40        site: Origin,
41    },
42    Noise(u64),
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    /// Samples the store answered in place of the node's own source, which is never typed.
56    Stored(Arc<Stored>),
57}
58
59/// A read's instant: the exact time `k*t + s` written; a closed form of `t` held as a node;
60/// or an integer each sample evaluates.
61#[derive(Clone, Debug, PartialEq)]
62pub enum When {
63    At(crate::time::Affine),
64    Moving(NodeId),
65    Index(crate::index::Index),
66    Step(Step),
67}
68
69/// An integer no one map spells: exact indices, `idx(time, round)` of a time that moves, and
70/// sums, negations and products of them.
71#[derive(Clone, Debug, PartialEq)]
72pub enum Step {
73    Index(crate::index::Index),
74    Nearest(NodeId, crate::index::Round),
75    Add(Vec<Step>),
76    Neg(Box<Step>),
77    Mul(Vec<Step>),
78}
79
80impl Step {
81    /// Every time that moves in it.
82    pub(crate) fn times(&self, out: &mut Vec<NodeId>) {
83        match self {
84            Step::Index(_) => {}
85            Step::Nearest(time, _) => out.push(*time),
86            Step::Add(parts) | Step::Mul(parts) => parts.iter().for_each(|p| p.times(out)),
87            Step::Neg(p) => p.times(out),
88        }
89    }
90}
91
92impl When {
93    /// Every node it evaluates each sample.
94    pub(crate) fn moving(&self) -> Vec<NodeId> {
95        let mut out = Vec::new();
96        match self {
97            When::Moving(id) => out.push(*id),
98            When::Step(step) => step.times(&mut out),
99            When::At(_) | When::Index(_) => {}
100        }
101        out
102    }
103}
104
105#[derive(Clone, Debug, PartialEq)]
106pub struct Node {
107    pub name: String,
108    pub ty: Ty,
109    pub var: Var,
110    pub value: Value,
111    pub grid: Grid,
112}
113
114#[derive(Clone, Debug, Default, PartialEq)]
115pub struct Typing {
116    nodes: Vec<Node>,
117    arguments: BTreeMap<String, Arguments>,
118    by_path: BTreeMap<String, NodeId>,
119    copies: BTreeMap<(String, Grid), NodeId>,
120    lowering: BTreeSet<String>,
121    files: BTreeMap<String, Vec<NodeId>>,
122    origins: Vec<(u32, Option<sva_ast::ByteSpan>)>,
123    sites: Vec<String>,
124    site_ids: BTreeMap<String, u32>,
125    pending: BTreeSet<NodeId>,
126    indices: u32,
127    sum: Option<(NodeId, Vec<SumSlot>)>,
128    numbers: Numbers,
129    /// Every node lowered from its source, in order.
130    lowered: Vec<String>,
131    /// What each path's group wrote, lowered or taken from a prior typing.
132    spans: BTreeMap<String, Span>,
133}
134
135/// Each node's folded number, derived from the nodes alone; a settle evicts it all.
136#[derive(Clone, Debug, Default)]
137struct Numbers(RefCell<BTreeMap<NodeId, Option<C64>>>);
138
139impl PartialEq for Numbers {
140    fn eq(&self, _: &Numbers) -> bool {
141        true
142    }
143}
144
145/// One term of a stream's note sum: its node, or the hull of the supports of those it retired.
146#[derive(Clone, Copy, Debug, PartialEq)]
147pub(crate) enum SumSlot {
148    Node(NodeId),
149    Retired(sva_samples::Extent),
150}
151
152impl Typing {
153    /// `node` named by its terms in place.
154    pub(crate) fn name_sum(&mut self, node: NodeId, slots: Vec<SumSlot>) {
155        self.sum = Some((node, slots));
156    }
157
158    /// The note sum, where it holds a term it retired.
159    pub(crate) fn retired_sum(&self) -> Option<NodeId> {
160        let (sum, slots) = self.sum.as_ref()?;
161        let retired = slots.iter().any(|slot| matches!(slot, SumSlot::Retired(_)));
162        retired.then_some(*sum)
163    }
164
165    /// The edges a node's identity is hashed over.
166    pub(crate) fn operands(&self, id: NodeId) -> Vec<NodeId> {
167        match self.value(id) {
168            Value::ClosedForm(form) => crate::refs::nodes_in(&form.body),
169            Value::Cast(_, source) | Value::Read { source, .. } => vec![*source],
170            Value::Op { args, .. } => args.clone(),
171            Value::Filter {
172                x, cutoff, q, gain, ..
173            } => vec![*x, *cutoff, *q, *gain],
174            Value::Solver { varying, .. } => varying.iter().map(|(_, a)| *a).collect(),
175            Value::SelfAt { .. } | Value::Noise(_) | Value::Stored(_) => Vec::new(),
176        }
177    }
178
179    /// Whether `id` reads `of`, however far down.
180    pub(crate) fn reads(&self, id: NodeId, of: NodeId) -> bool {
181        let (mut open, mut seen) = (vec![id], BTreeSet::new());
182        while let Some(at) = open.pop() {
183            if at == of {
184                return true;
185            }
186            if seen.insert(at) {
187                open.extend(self.operands(at));
188            }
189        }
190        false
191    }
192
193    pub(crate) fn sum_slots(&self, node: NodeId) -> Option<&[SumSlot]> {
194        self.sum
195            .as_ref()
196            .filter(|(held, _)| *held == node)
197            .map(|(_, slots)| slots.as_slice())
198    }
199
200    pub(crate) fn lowering(&mut self, path: &str) {
201        self.lowered.push(path.to_string());
202    }
203
204    pub(crate) fn lowered(&self) -> &[String] {
205        &self.lowered
206    }
207
208    pub(crate) fn next_index(&mut self) -> sva_formula::IndexId {
209        self.indices += 1;
210        sva_formula::IndexId(self.indices)
211    }
212
213    /// A call lowered twice is noted once, at its latest lowering.
214    pub(crate) fn note(&mut self, node: &str, call: Option<Called>, chosen: Vec<Chosen>) {
215        let held = self
216            .arguments
217            .entry(node.to_string())
218            .or_insert_with(|| Arguments {
219                node: node.to_string(),
220                ..Arguments::default()
221            });
222        if let Some(call) = call {
223            held.calls
224                .retain(|c| (c.at.start, &c.name) != (call.at.start, &call.name));
225            held.calls.push(call);
226        }
227        for one in chosen {
228            held.chosen.retain(|c| c.at.start != one.at.start);
229            held.chosen.push(one);
230        }
231    }
232
233    pub fn arguments(&self, node: &str) -> Option<&Arguments> {
234        self.arguments.get(node)
235    }
236
237    pub fn ty(&self, n: NodeId) -> Ty {
238        self.at(n).ty
239    }
240
241    pub fn var(&self, n: NodeId) -> Var {
242        self.at(n).var
243    }
244
245    pub fn value(&self, n: NodeId) -> &Value {
246        &self.at(n).value
247    }
248
249    pub fn name(&self, n: NodeId) -> &str {
250        &self.at(n).name
251    }
252
253    pub fn grid(&self, n: NodeId) -> Grid {
254        self.at(n).grid
255    }
256
257    pub(crate) fn copy(&self, path: &str, grid: Grid) -> Option<NodeId> {
258        self.copies.get(&(path.to_string(), grid)).copied()
259    }
260
261    pub(crate) fn copied(&mut self, path: &str, grid: Grid, id: NodeId) {
262        self.copies.insert((path.to_string(), grid), id);
263    }
264
265    /// `false` where a copy of `path` is already being lowered: a loop of refs.
266    pub(crate) fn opened(&mut self, path: &str) -> bool {
267        self.lowering.insert(path.to_string())
268    }
269
270    pub(crate) fn closed(&mut self, path: &str) {
271        self.lowering.remove(path);
272    }
273
274    pub fn at(&self, n: NodeId) -> &Node {
275        &self.nodes[n.0 as usize]
276    }
277
278    pub(crate) fn len(&self) -> usize {
279        self.nodes.len()
280    }
281
282    pub fn id(&self, path: &str) -> Option<NodeId> {
283        self.by_path.get(path).copied()
284    }
285
286    pub fn paths(&self) -> impl Iterator<Item = (&str, NodeId)> {
287        self.by_path.iter().map(|(p, id)| (p.as_str(), *id))
288    }
289
290    /// The node a reading asks for, by instance path or by the file a composer wrote.
291    pub fn resolve(&self, path: &str) -> Result<NodeId, EngineError> {
292        if let Some(id) = self.id(path) {
293            return Ok(id);
294        }
295        let held = self.files.get(path).cloned().unwrap_or_default();
296        crate::instantiate::sole(
297            path,
298            held.into_iter()
299                .map(|id| (self.name(id).to_string(), id))
300                .collect(),
301        )
302    }
303
304    /// Every `Origin` a term carries was stamped here.
305    pub fn locate(&self, origin: Origin) -> Located {
306        self.origins
307            .get(origin.token() as usize)
308            .map(|&(site, span)| Located::at(self.sites[site as usize].as_str(), span))
309            .unwrap_or_default()
310    }
311
312    pub(crate) fn mark(&mut self, node: &str, span: Option<sva_ast::ByteSpan>) -> Origin {
313        let site = match self.site_ids.get(node) {
314            Some(&site) => site,
315            None => {
316                let site = self.sites.len() as u32;
317                self.sites.push(node.to_string());
318                self.site_ids.insert(node.to_string(), site);
319                site
320            }
321        };
322        self.origins.push((site, span));
323        Origin::new((self.origins.len() - 1) as u32)
324    }
325
326    pub(crate) fn seed(&mut self, path: &str, held: Held, grid: Grid) -> NodeId {
327        if let Some(id) = self.id(path) {
328            return id;
329        }
330        let id = self.push(
331            Node {
332                name: path.to_string(),
333                ty: Ty {
334                    dual: held.is_closed_form(),
335                    ..Ty::discrete(held, Codomain::Real)
336                },
337                var: Var::T,
338                value: Value::Op {
339                    name: "loop".to_string(),
340                    args: Vec::new(),
341                },
342                grid,
343            },
344            Some(path),
345        );
346        self.pending.insert(id);
347        id
348    }
349
350    pub(crate) fn pending(&self, id: NodeId) -> bool {
351        self.pending.contains(&id)
352    }
353
354    pub(crate) fn settle(&mut self, id: NodeId, node: Node) {
355        self.nodes[id.0 as usize] = node;
356        self.pending.remove(&id);
357        self.numbers.0.get_mut().clear();
358    }
359
360    pub(crate) fn folded_number(&self, id: NodeId) -> Option<Option<C64>> {
361        self.numbers.0.borrow().get(&id).copied()
362    }
363
364    pub(crate) fn fold_number(&self, id: NodeId, number: Option<C64>) {
365        self.numbers.0.borrow_mut().insert(id, number);
366    }
367
368    pub(crate) fn alias(&mut self, path: &str, id: NodeId) {
369        self.by_path.insert(path.to_string(), id);
370    }
371
372    pub(crate) fn push(&mut self, node: Node, path: Option<&str>) -> NodeId {
373        let id = NodeId(self.nodes.len() as u32);
374        self.nodes.push(node);
375        if let Some(path) = path {
376            self.by_path.insert(path.to_string(), id);
377        }
378        id
379    }
380
381    pub(crate) fn infer_closed_form(&self, form: &ClosedForm) -> Result<Ty, EngineError> {
382        infer(form, &Table(&self.nodes)).map_err(|r| {
383            EngineError::of_closed_form(
384                &r,
385                self.locate(r.origin),
386                "write the subterm inside sample(...) to leave A deliberately",
387            )
388        })
389    }
390}
391
392struct Table<'a>(&'a [Node]);
393
394impl Env for Table<'_> {
395    fn node(&self, id: NodeId) -> Ty {
396        self.0[id.0 as usize].ty
397    }
398
399    /// Substituted per instance before a closed form reaches sva-formula, so no term holds one.
400    fn param(&self, _: ParamId) -> Ty {
401        Ty::form(Var::T, true, Codomain::Real)
402    }
403}
404
405/// Dependencies first, so a ref reads a type already decided.
406pub fn infer_all(inst: &Instances, order: &Order) -> Result<Typing, EngineError> {
407    infer_over(inst, order, &BTreeMap::new())
408}
409
410/// Each node `stored` names stands as its samples, and nothing under it is typed.
411pub(crate) fn infer_over(
412    inst: &Instances,
413    order: &Order,
414    stored: &BTreeMap<String, Arc<Stored>>,
415) -> Result<Typing, EngineError> {
416    Ok(inferred(inst, order, stored, None)?.0)
417}
418
419/// Each group `prior` typed from the same sources, reading only groups taken too, taken from
420/// it as it was lowered there; the rest lowered.
421pub(crate) fn infer_beside(
422    inst: &Instances,
423    order: &Order,
424    prior: &Prior<'_>,
425) -> Result<(Typing, Carried), EngineError> {
426    let (typing, carried) = inferred(inst, order, &BTreeMap::new(), Some(prior))?;
427    Ok((typing, carried.expect("a prior to take from")))
428}
429
430fn inferred(
431    inst: &Instances,
432    order: &Order,
433    stored: &BTreeMap<String, Arc<Stored>>,
434    prior: Option<&Prior<'_>>,
435) -> Result<(Typing, Option<Carried>), EngineError> {
436    let mut typing = Typing::default();
437    let mut carried = prior.map(|prior| Carried::over(prior.typing));
438    if let Some(prior) = prior {
439        typing.indices = prior.typing.indices;
440    }
441    for group in &order.groups {
442        let (nodes, origins) = (typing.nodes.len() as u32, typing.origins.len() as u32);
443        let taken = match (prior, &mut carried) {
444            (Some(prior), Some(carried)) => typing.carry(prior, order, group, carried),
445            _ => false,
446        };
447        match (taken, order.is_loop(group), group.as_slice()) {
448            (true, _, _) => {}
449            (false, false, [path]) if let Some(held) = stored.get(path) => {
450                typing.push(standing(path, held), Some(path));
451            }
452            (false, true, _) => settle_loop(&mut typing, inst, group)?,
453            (false, false, _) => {
454                for path in group {
455                    lower::node(path, inst, &mut typing)?;
456                }
457            }
458        }
459        let span = Span {
460            nodes: nodes..typing.nodes.len() as u32,
461            origins: origins..typing.origins.len() as u32,
462        };
463        for path in group {
464            typing.spans.insert(path.clone(), span.clone());
465        }
466    }
467    name_files(&mut typing, inst);
468    Ok((typing, carried))
469}
470
471fn standing(path: &str, held: &Arc<Stored>) -> Node {
472    Node {
473        name: path.to_string(),
474        ty: Ty {
475            width: held.width,
476            rate: held.rate,
477            ..Ty::discrete(Held::Sampled, held.codomain)
478        },
479        var: Var::T,
480        value: Value::Stored(Arc::clone(held)),
481        grid: held.grid,
482    }
483}
484
485const SEEDS: [Held; 2] = [Held::Form(Var::T), Held::Sampled];
486
487/// A group's members type together, so the seed a pass starts from is a guess the pass
488/// either reaches again or replaces with what its members held.
489fn settle_loop(typing: &mut Typing, inst: &Instances, group: &[String]) -> Result<(), EngineError> {
490    let mut seed = SEEDS[0];
491    let mut refusal = None;
492    for _ in 0..=SEEDS.len() {
493        let mut attempt = typing.clone();
494        for path in group {
495            attempt.seed(path, seed, inst.grid());
496        }
497        let walked = group
498            .iter()
499            .try_for_each(|path| lower::node(path, inst, &mut attempt).map(|_| ()));
500        match walked {
501            Ok(()) => match held_by(&attempt, group) {
502                reached if reached == seed => {
503                    *typing = attempt;
504                    return Ok(());
505                }
506                reached => seed = reached,
507            },
508            Err(e) => {
509                refusal = Some(e);
510                seed = elsewhere(seed);
511            }
512        }
513    }
514    Err(refusal.unwrap_or_else(|| mixed(group)))
515}
516
517/// The seed a refused pass did not try.
518fn elsewhere(seed: Held) -> Held {
519    match seed {
520        Held::Sampled => Held::Form(Var::T),
521        _ => Held::Sampled,
522    }
523}
524
525/// One representation for the whole group: samples where any member reached them.
526fn held_by(typing: &Typing, group: &[String]) -> Held {
527    let sampled = group
528        .iter()
529        .filter_map(|path| typing.id(path))
530        .any(|id| !typing.ty(id).is_closed_form());
531    match sampled {
532        true => Held::Sampled,
533        false => Held::Form(Var::T),
534    }
535}
536
537/// A group that settles in no representation holds both.
538fn mixed(group: &[String]) -> EngineError {
539    let at = group.first().map_or("", String::as_str);
540    EngineError::refused(Diagnostic {
541        code: "type.samples_in_closed_form".to_string(),
542        message: format!(
543            "the loop over `{}` holds a closed form and samples at once.",
544            group.join("`, `")
545        ),
546        location: Located::at(at, None),
547        help: "write sample(...) on the members that are closed forms, so the whole loop runs \
548               on the grid"
549            .to_string(),
550    })
551}
552
553/// A file with one instance answers to its own name too.
554fn name_files(typing: &mut Typing, inst: &Instances) {
555    let files: Vec<String> = inst
556        .paths()
557        .filter_map(|p| inst.origin(p))
558        .map(str::to_string)
559        .collect();
560    for file in files {
561        if typing.files.contains_key(&file) {
562            continue;
563        }
564        let held: Vec<NodeId> = inst
565            .instances_of(&file)
566            .filter_map(|p| typing.id(&p))
567            .collect();
568        if let ([only], None) = (held.as_slice(), typing.id(&file)) {
569            typing.alias(&file, *only);
570        }
571        typing.files.insert(file, held);
572    }
573}
sva_engine/typing/mod.rs

sva_engine/typing/
mod.rs
