sva_engine/
schedule.rs

1// Concern: orders nodes dependencies-first and picks which a reading materializes | Non-concern: what a held node contains (render.rs), reading one (refs.rs) | IO: (Instances, asks) -> Schedule
2
3use std::collections::{BTreeSet, HashMap};
4
5use sva_formula::{Held, NodeId, Var};
6
7use crate::cast::Cast;
8use crate::error::EngineError;
9use crate::instantiate::Instances;
10use crate::query::Ask;
11use crate::typing::{Typing, Value, When};
12
13/// One dependencies-first walk: the groups, and which are loops.
14pub struct Order<'i> {
15    pub groups: Vec<Vec<String>>,
16    inst: &'i Instances,
17}
18
19impl<'i> Order<'i> {
20    pub fn deps(&self, path: &str) -> &'i [String] {
21        self.inst.deps(path)
22    }
23
24    pub(crate) fn within(&self, kept: &BTreeSet<String>) -> Order<'i> {
25        Order {
26            groups: self
27                .groups
28                .iter()
29                .filter(|group| group.iter().all(|path| kept.contains(path)))
30                .cloned()
31                .collect(),
32            inst: self.inst,
33        }
34    }
35
36    /// A group of one not reading itself is no loop; any other is.
37    pub fn is_loop(&self, group: &[String]) -> bool {
38        is_loop(self.inst, group)
39    }
40}
41
42pub(crate) fn is_loop(inst: &Instances, group: &[String]) -> bool {
43    match group {
44        [only] => inst.deps(only).iter().any(|d| d == only),
45        _ => true,
46    }
47}
48
49struct Frame {
50    node: String,
51    refs: Vec<String>,
52    idx: usize,
53}
54
55/// A node two roots reach is grouped once, whichever reached it first.
56pub fn schedule_from<'i>(inst: &'i Instances, roots: &[String]) -> Result<Order<'i>, EngineError> {
57    let mut walk = Walk {
58        inst,
59        within: &|_| true,
60        index: HashMap::new(),
61        low: HashMap::new(),
62        open: Vec::new(),
63        next: 0,
64        groups: Vec::new(),
65    };
66    for root in roots {
67        if !inst.holds(root) {
68            return Err(EngineError::UnknownNode(root.to_string()));
69        }
70        walk.from(root);
71    }
72    Ok(Order {
73        groups: walk.groups,
74        inst,
75    })
76}
77
78/// The groups of `region`, dependencies first.
79pub(crate) fn grouped(
80    inst: &Instances,
81    starts: &[String],
82    region: &dyn Fn(&str) -> bool,
83) -> Vec<Vec<String>> {
84    let mut walk = Walk {
85        inst,
86        within: region,
87        index: HashMap::new(),
88        low: HashMap::new(),
89        open: Vec::new(),
90        next: 0,
91        groups: Vec::new(),
92    };
93    for start in starts.iter().filter(|s| region(s)) {
94        walk.from(start);
95    }
96    walk.groups
97}
98
99struct Walk<'a> {
100    inst: &'a Instances,
101    within: &'a dyn Fn(&str) -> bool,
102    index: HashMap<String, usize>,
103    low: HashMap<String, usize>,
104    open: Vec<String>,
105    next: usize,
106    groups: Vec<Vec<String>>,
107}
108
109impl Walk<'_> {
110    fn reads(&self, node: &str) -> Vec<String> {
111        let reads = self.inst.deps(node).iter();
112        reads.filter(|read| (self.within)(read)).cloned().collect()
113    }
114
115    fn from(&mut self, root: &str) {
116        if self.index.contains_key(root) {
117            return;
118        }
119        self.index.insert(root.to_string(), self.next);
120        self.low.insert(root.to_string(), self.next);
121        self.next += 1;
122        self.open.push(root.to_string());
123        let seed = self.reads(root);
124        let mut stack = vec![Frame {
125            node: root.to_string(),
126            refs: seed,
127            idx: 0,
128        }];
129
130        while let Some(frame) = stack.last_mut() {
131            if frame.idx < frame.refs.len() {
132                let target = frame.refs[frame.idx].clone();
133                let node = frame.node.clone();
134                frame.idx += 1;
135                match self.index.get(&target).copied() {
136                    None => {
137                        self.index.insert(target.clone(), self.next);
138                        self.low.insert(target.clone(), self.next);
139                        self.next += 1;
140                        self.open.push(target.clone());
141                        let refs = self.reads(&target);
142                        stack.push(Frame {
143                            node: target,
144                            refs,
145                            idx: 0,
146                        });
147                    }
148                    Some(at) if self.open.contains(&target) => {
149                        let mine = self.low[&node];
150                        self.low.insert(node, mine.min(at));
151                    }
152                    Some(_) => {}
153                }
154                continue;
155            }
156
157            let node = frame.node.clone();
158            let mine = self.low[&node];
159            stack.pop();
160            if let Some(parent) = stack.last() {
161                let above = self.low[&parent.node];
162                self.low.insert(parent.node.clone(), above.min(mine));
163            }
164            if mine == self.index[&node] {
165                let at = self
166                    .open
167                    .iter()
168                    .rposition(|n| *n == node)
169                    .expect("a root of its group is still open");
170                let mut group = self.open.split_off(at);
171                group.sort();
172                self.groups.push(group);
173            }
174        }
175    }
176}
177
178/// What a render has to hold, and what it can leave as a closed form.
179#[derive(Clone, Debug, Default, PartialEq)]
180pub struct Schedule {
181    /// What a reading holds for itself, the root among them.
182    pub wanted: Vec<NodeId>,
183    /// The nodes a reading asked a closed form of, none already held.
184    pub compose: Vec<NodeId>,
185}
186
187/// A closed form is held as samples only under a buffer reading, a ledger, or the root.
188pub fn plan(typing: &Typing, root: NodeId, asks: &[Ask]) -> Schedule {
189    let mut wanted: BTreeSet<NodeId> = BTreeSet::new();
190    let mut compose: Vec<NodeId> = Vec::new();
191    let audio = asks.is_empty();
192    for ask in asks {
193        let Some(id) = typing.id(&ask.node) else {
194            continue;
195        };
196        // FORMAT 14.2: `bindings` and `arguments` are structural and `flops` counts; none composes.
197        if matches!(
198            ask.representation,
199            crate::query::Representation::Bindings
200                | crate::query::Representation::Arguments
201                | crate::query::Representation::Flops
202        ) {
203            continue;
204        }
205        match ask.representation.consumes(typing.ty(id).is_closed_form()) {
206            sva_samples::Consumes::ClosedForm if !compose.contains(&id) => compose.push(id),
207            sva_samples::Consumes::ClosedForm => {}
208            _ => {
209                wanted.insert(id);
210            }
211        }
212        if let crate::query::Representation::Ledger { depth } = ask.representation {
213            attributed(typing, id, depth, &mut wanted);
214        }
215    }
216    if audio || !wanted.is_empty() {
217        wanted.insert(root);
218    }
219    compose.retain(|id| !wanted.contains(id));
220    Schedule {
221        wanted: wanted.into_iter().collect(),
222        compose,
223    }
224}
225
226/// A ledger names every ref under its target, so each is a buffer of its own.
227fn attributed(typing: &Typing, id: NodeId, depth: usize, wanted: &mut BTreeSet<NodeId>) {
228    // Level by level, as the reading walks: a node is held at its shortest chain's depth.
229    let mut seen = BTreeSet::from([id]);
230    let mut level = vec![id];
231    for _ in 0..depth {
232        let mut next = Vec::new();
233        while let Some(held) = level.pop() {
234            for operand in read_operands(typing, held) {
235                if !seen.insert(operand) {
236                    continue;
237                }
238                wanted.insert(operand);
239                match typing.name(operand) == typing.name(held) {
240                    true => level.push(operand),
241                    false => next.push(operand),
242                }
243            }
244        }
245        level = next;
246    }
247}
248
249/// A node reading its own output is one program, whatever its width: a component on its own
250/// would read the loop at its own width.
251pub(crate) fn holds_self(typing: &Typing, id: NodeId, seen: &mut BTreeSet<NodeId>) -> bool {
252    if !seen.insert(id) {
253        return false;
254    }
255    match typing.value(id) {
256        Value::SelfAt { .. } => true,
257        Value::Cast(Cast::Sample, _) | Value::Read { .. } => false,
258        Value::Cast(_, source) => holds_self(typing, *source, seen),
259        Value::Op { args, .. } => args.iter().any(|a| holds_self(typing, *a, seen)),
260        Value::Filter {
261            x, cutoff, q, gain, ..
262        } => [x, cutoff, q, gain]
263            .into_iter()
264            .any(|operand| holds_self(typing, *operand, seen)),
265        Value::Solver { varying, .. } => varying.iter().any(|(_, a)| holds_self(typing, *a, seen)),
266        Value::ClosedForm(_) | Value::Noise(_) | Value::Stored(_) => false,
267    }
268}
269
270/// Which nodes under `id` a render has to hold before it can hold `id` itself: the buffers its
271/// program reads, an operation, filter or read under it being part of that program.
272pub(crate) fn materialized_operands(typing: &Typing, id: NodeId) -> Vec<NodeId> {
273    let sampled = |set: Vec<NodeId>| -> Vec<NodeId> {
274        let mut out = Vec::new();
275        for op in set {
276            if typing.ty(op).is_closed_form() {
277                continue;
278            }
279            let inlined = matches!(
280                typing.value(op),
281                Value::Op { .. } | Value::Filter { .. } | Value::Read { .. }
282            );
283            match inlined || holds_self(typing, op, &mut BTreeSet::new()) {
284                true => out.extend(materialized_operands(typing, op)),
285                false => out.push(op),
286            }
287        }
288        out
289    };
290    match typing.value(id) {
291        Value::ClosedForm(_) | Value::Noise(_) | Value::Stored(_) => Vec::new(),
292        Value::SelfAt { at, .. } => sampled(at.moving()),
293        Value::Solver { varying, .. } => sampled(varying.iter().map(|(_, a)| *a).collect()),
294        Value::Cast(Cast::Sample, source) => vec![*source],
295        Value::Read { source, at, .. } => {
296            let mut out = match (at, anywhere(typing, *source)) {
297                (When::Moving(_) | When::Step(_), true) => Vec::new(),
298                _ => vec![*source],
299            };
300            out.extend(sampled(at.moving()));
301            out
302        }
303        Value::Cast(_, source) => sampled(vec![*source]),
304        Value::Op { args, .. } => sampled(args.clone()),
305        Value::Filter {
306            x, cutoff, q, gain, ..
307        } => sampled(vec![*x, *cutoff, *q, *gain]),
308    }
309}
310
311/// Whether a read of `id` has a value at any instant, stored or not.
312pub(crate) fn anywhere(typing: &Typing, id: NodeId) -> bool {
313    match typing.value(id) {
314        Value::Noise(_) => true,
315        Value::Cast(Cast::Sample, of) => typing.ty(*of).held == Held::Form(Var::T),
316        Value::ClosedForm(form) => form.var == Var::T,
317        _ => false,
318    }
319}
320
321/// Every ref one node reads; `materialized_operands` answers a narrower one.
322pub(crate) fn read_operands(typing: &Typing, id: NodeId) -> Vec<NodeId> {
323    match typing.value(id) {
324        Value::ClosedForm(form) => crate::refs::nodes_in(&form.body),
325        _ if typing.ty(id).is_closed_form() => {
326            let mut out = Vec::new();
327            reads_under(typing, id, &mut BTreeSet::new(), &mut out);
328            out.dedup();
329            out
330        }
331        _ => materialized_operands(typing, id),
332    }
333}
334
335/// A closed-form-typed node that holds no written one still reads refs through its operands.
336fn reads_under(typing: &Typing, id: NodeId, seen: &mut BTreeSet<NodeId>, out: &mut Vec<NodeId>) {
337    if !seen.insert(id) {
338        return;
339    }
340    match typing.value(id) {
341        Value::ClosedForm(form) => out.extend(crate::refs::nodes_in(&form.body)),
342        Value::Read { source, .. } => out.push(*source),
343        Value::Cast(_, source) => read_through(typing, *source, seen, out),
344        Value::Op { args, .. } => {
345            for arg in args {
346                read_through(typing, *arg, seen, out);
347            }
348        }
349        Value::Filter {
350            x, cutoff, q, gain, ..
351        } => {
352            for operand in [x, cutoff, q, gain] {
353                read_through(typing, *operand, seen, out);
354            }
355        }
356        Value::Solver { varying, .. } => {
357            for (_, arg) in varying {
358                read_through(typing, *arg, seen, out);
359            }
360        }
361        Value::SelfAt { .. } | Value::Noise(_) | Value::Stored(_) => {}
362    }
363}
364
365/// A written form under an operand is the term read, whatever transform sits between.
366fn read_through(typing: &Typing, id: NodeId, seen: &mut BTreeSet<NodeId>, out: &mut Vec<NodeId>) {
367    let Value::ClosedForm(_) = typing.value(id) else {
368        return reads_under(typing, id, seen, out);
369    };
370    if seen.insert(id) {
371        out.push(id);
372    }
373}
sva_engine/schedule.rs

sva_engine/
schedule.rs
