sva_engine/
typing.rs

1// Concern: gives every node one Ty, the value it lowered to, and how it reads release | Non-concern: the per-term judgment (sva-formula), lowering (lower/) | IO: (Instances, Order) -> Ty per node
2
3use crate::release::Use;
4use std::collections::{BTreeMap, BTreeSet};
5
6use sva_formula::filter::Shape;
7use sva_formula::{ClosedForm, Codomain, Env, Held, NodeId, Origin, ParamId, Ty, Var, infer};
8use sva_samples::Params;
9
10use crate::arguments::{Arguments, Called, Chosen};
11use crate::cast::Cast;
12use crate::error::{Diagnostic, EngineError, Located};
13use crate::instantiate::Instances;
14use crate::loops::Delay;
15use crate::lower;
16use crate::offset::Offset;
17use crate::schedule::Order;
18
19/// A closed form is cast-free on one axis; every crossing is its own node.
20#[derive(Clone, Debug, PartialEq)]
21pub enum Value {
22    ClosedForm(ClosedForm),
23    Cast(Cast, NodeId),
24    Op {
25        name: String,
26        args: Vec<NodeId>,
27    },
28    /// One read of this node's own output, at the delay the call site wrote.
29    SelfAt(Delay),
30    /// A count of samples read as a duration, which only a rate turns into seconds.
31    Grid(f64),
32    Read {
33        source: NodeId,
34        at: Offset,
35        site: Origin,
36    },
37    /// The signal and its three arguments, each a node of its own.
38    Filter {
39        shape: Shape,
40        x: NodeId,
41        cutoff: NodeId,
42        q: NodeId,
43        gain: NodeId,
44    },
45    Solver(Box<Params>),
46}
47
48#[derive(Clone, Debug, PartialEq)]
49pub struct Node {
50    pub name: String,
51    pub ty: Ty,
52    pub var: Var,
53    pub value: Value,
54}
55
56#[derive(Clone, Debug, Default, PartialEq)]
57pub struct Typing {
58    nodes: Vec<Node>,
59    arguments: BTreeMap<String, Arguments>,
60    by_path: BTreeMap<String, NodeId>,
61    files: BTreeMap<String, Vec<NodeId>>,
62    origins: Vec<Located>,
63    pending: BTreeSet<NodeId>,
64    indices: u32,
65    release: BTreeMap<String, Use>,
66}
67
68impl Typing {
69    /// How a lowered node reads `release`; one still lowering in the same loop reads it
70    /// at most causally, which is all a past read of it needs.
71    pub(crate) fn release_use(&self, path: &str) -> Use {
72        self.release.get(path).copied().unwrap_or(Use::Causal)
73    }
74
75    pub(crate) fn note_release(&mut self, path: &str, reads: Use) {
76        self.release.insert(path.to_string(), reads);
77    }
78
79    pub(crate) fn next_index(&mut self) -> sva_formula::IndexId {
80        self.indices += 1;
81        sva_formula::IndexId(self.indices)
82    }
83
84    /// A call lowered twice is noted once, at its latest lowering.
85    pub(crate) fn note(&mut self, node: &str, call: Option<Called>, chosen: Vec<Chosen>) {
86        let held = self
87            .arguments
88            .entry(node.to_string())
89            .or_insert_with(|| Arguments {
90                node: node.to_string(),
91                ..Arguments::default()
92            });
93        if let Some(call) = call {
94            held.calls
95                .retain(|c| (c.at.start, &c.name) != (call.at.start, &call.name));
96            held.calls.push(call);
97        }
98        for one in chosen {
99            held.chosen.retain(|c| c.at.start != one.at.start);
100            held.chosen.push(one);
101        }
102    }
103
104    pub fn arguments(&self, node: &str) -> Option<&Arguments> {
105        self.arguments.get(node)
106    }
107
108    pub fn ty(&self, n: NodeId) -> Ty {
109        self.at(n).ty
110    }
111
112    pub fn var(&self, n: NodeId) -> Var {
113        self.at(n).var
114    }
115
116    pub fn value(&self, n: NodeId) -> &Value {
117        &self.at(n).value
118    }
119
120    pub fn name(&self, n: NodeId) -> &str {
121        &self.at(n).name
122    }
123
124    pub fn at(&self, n: NodeId) -> &Node {
125        &self.nodes[n.0 as usize]
126    }
127
128    pub(crate) fn len(&self) -> usize {
129        self.nodes.len()
130    }
131
132    pub fn id(&self, path: &str) -> Option<NodeId> {
133        self.by_path.get(path).copied()
134    }
135
136    pub fn paths(&self) -> impl Iterator<Item = (&str, NodeId)> {
137        self.by_path.iter().map(|(p, id)| (p.as_str(), *id))
138    }
139
140    /// The node a reading asks for, by instance path or by the file a composer wrote.
141    pub fn resolve(&self, path: &str) -> Result<NodeId, EngineError> {
142        if let Some(id) = self.id(path) {
143            return Ok(id);
144        }
145        let held = self.files.get(path).cloned().unwrap_or_default();
146        crate::instantiate::sole(
147            path,
148            held.into_iter()
149                .map(|id| (self.name(id).to_string(), id))
150                .collect(),
151        )
152    }
153
154    /// Every `Origin` a term carries was stamped here.
155    pub fn locate(&self, origin: Origin) -> Located {
156        self.origins
157            .get(origin.token() as usize)
158            .cloned()
159            .unwrap_or_default()
160    }
161
162    pub(crate) fn mark(&mut self, at: Located) -> Origin {
163        self.origins.push(at);
164        Origin::new((self.origins.len() - 1) as u32)
165    }
166
167    pub(crate) fn seed(&mut self, path: &str, held: Held) -> NodeId {
168        if let Some(id) = self.id(path) {
169            return id;
170        }
171        let id = self.push(
172            Node {
173                name: path.to_string(),
174                ty: Ty {
175                    dual: held.is_closed_form(),
176                    ..Ty::discrete(held, Codomain::Real)
177                },
178                var: Var::T,
179                value: Value::Op {
180                    name: "loop".to_string(),
181                    args: Vec::new(),
182                },
183            },
184            Some(path),
185        );
186        self.pending.insert(id);
187        id
188    }
189
190    pub(crate) fn pending(&self, id: NodeId) -> bool {
191        self.pending.contains(&id)
192    }
193
194    pub(crate) fn settle(&mut self, id: NodeId, node: Node) {
195        self.nodes[id.0 as usize] = node;
196        self.pending.remove(&id);
197    }
198
199    pub(crate) fn alias(&mut self, path: &str, id: NodeId) {
200        self.by_path.insert(path.to_string(), id);
201    }
202
203    pub(crate) fn push(&mut self, node: Node, path: Option<&str>) -> NodeId {
204        let id = NodeId(self.nodes.len() as u32);
205        self.nodes.push(node);
206        if let Some(path) = path {
207            self.by_path.insert(path.to_string(), id);
208        }
209        id
210    }
211
212    pub(crate) fn infer_closed_form(&self, form: &ClosedForm) -> Result<Ty, EngineError> {
213        infer(form, &Table(&self.nodes)).map_err(|r| {
214            EngineError::of_closed_form(
215                &r,
216                self.locate(r.origin),
217                "write the subterm inside sample(...) to leave A deliberately",
218            )
219        })
220    }
221}
222
223struct Table<'a>(&'a [Node]);
224
225impl Env for Table<'_> {
226    fn node(&self, id: NodeId) -> Ty {
227        self.0[id.0 as usize].ty
228    }
229
230    /// Substituted per instance before a closed form reaches sva-formula, so no term holds one.
231    fn param(&self, _: ParamId) -> Ty {
232        Ty::form(Var::T, true, Codomain::Real)
233    }
234}
235
236/// Dependencies first, so a ref reads a type already decided.
237pub fn infer_all(inst: &Instances, order: &Order) -> Result<Typing, EngineError> {
238    let mut typing = Typing::default();
239    for group in &order.groups {
240        match order.is_loop(group) {
241            true => settle_loop(&mut typing, inst, group)?,
242            false => {
243                for path in group {
244                    lower::node(path, inst, &mut typing)?;
245                }
246            }
247        }
248    }
249    name_files(&mut typing, inst);
250    Ok(typing)
251}
252
253const SEEDS: [Held; 2] = [Held::Form(Var::T), Held::Sampled];
254
255/// A group's members type together, so the seed a pass starts from is a guess the pass
256/// either reaches again or replaces with what its members held.
257fn settle_loop(typing: &mut Typing, inst: &Instances, group: &[String]) -> Result<(), EngineError> {
258    let mut seed = SEEDS[0];
259    let mut refusal = None;
260    for _ in 0..=SEEDS.len() {
261        let mut attempt = typing.clone();
262        for path in group {
263            attempt.seed(path, seed);
264        }
265        let walked = group
266            .iter()
267            .try_for_each(|path| lower::node(path, inst, &mut attempt).map(|_| ()));
268        match walked {
269            Ok(()) => match held_by(&attempt, group) {
270                reached if reached == seed => {
271                    *typing = attempt;
272                    return Ok(());
273                }
274                reached => seed = reached,
275            },
276            Err(e) => {
277                refusal = Some(e);
278                seed = elsewhere(seed);
279            }
280        }
281    }
282    Err(refusal.unwrap_or_else(|| mixed(group)))
283}
284
285/// The seed a refused pass did not try.
286fn elsewhere(seed: Held) -> Held {
287    match seed {
288        Held::Sampled => Held::Form(Var::T),
289        _ => Held::Sampled,
290    }
291}
292
293/// One representation for the whole group: samples where any member reached them.
294fn held_by(typing: &Typing, group: &[String]) -> Held {
295    let sampled = group
296        .iter()
297        .filter_map(|path| typing.id(path))
298        .any(|id| !typing.ty(id).is_closed_form());
299    match sampled {
300        true => Held::Sampled,
301        false => Held::Form(Var::T),
302    }
303}
304
305/// A group that settles in no representation holds both.
306fn mixed(group: &[String]) -> EngineError {
307    let at = group.first().map_or("", String::as_str);
308    EngineError::refused(Diagnostic {
309        code: "type.samples_in_closed_form".to_string(),
310        message: format!(
311            "the loop over `{}` holds a closed form and samples at once.",
312            group.join("`, `")
313        ),
314        location: Located::at(at, None),
315        help: "write sample(...) on the members that are closed forms, so the whole loop runs \
316               on the grid"
317            .to_string(),
318    })
319}
320
321/// A file with one instance answers to its own name too.
322fn name_files(typing: &mut Typing, inst: &Instances) {
323    let files: Vec<String> = inst
324        .paths()
325        .filter_map(|p| inst.origin(p))
326        .map(str::to_string)
327        .collect();
328    for file in files {
329        if typing.files.contains_key(&file) {
330            continue;
331        }
332        let held: Vec<NodeId> = inst
333            .instances_of(&file)
334            .filter_map(|p| typing.id(&p))
335            .collect();
336        if let ([only], None) = (held.as_slice(), typing.id(&file)) {
337            typing.alias(&file, *only);
338        }
339        typing.files.insert(file, held);
340    }
341}
sva_engine/typing.rs

sva_engine/
typing.rs
