sva_engine/render/
mod.rs

1// Concern: holds a composition's decided types, the buffers a reading needed and each label | Non-concern: computing a value (table/), what a reading asks (schedule.rs) | IO: (&Graph, target) -> Render
2
3mod answer;
4pub(crate) mod bound;
5mod drive;
6mod frontier;
7mod slots;
8mod stream;
9pub(crate) mod table;
10mod terms;
11mod through;
12pub mod until;
13mod volatile;
14
15use std::collections::{BTreeMap, BTreeSet};
16
17use sva_ast::Graph;
18use sva_formula::{NodeId, SpectralSum};
19use sva_samples::{
20    AliasScore, Buffer, Extent, FilterTrace, Frames, Label, PSYCHOACOUSTIC_V1, Profile,
21};
22
23use crate::bindings::Binding;
24use crate::cache::{Cache, CachePolicy, CacheStats, Recording};
25use crate::error::{Diagnostic, EngineError, Located};
26use crate::instantiate;
27use crate::query::Ask;
28use crate::refs;
29use crate::schedule::{self, Schedule};
30use crate::typing::{self, Typing};
31use table::Table;
32use table::support::Supports;
33
34/// Where a target is read, in samples from t = 0. Unstated, the root's own support.
35#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
36pub struct Range {
37    pub start: Option<i64>,
38    pub end: Option<i64>,
39}
40
41#[derive(Clone, Debug, PartialEq)]
42pub struct RenderConfig {
43    pub rate: u32,
44    pub range: Range,
45    /// Where the render stops before the range ends.
46    pub until: Option<Until>,
47    pub profile: Profile,
48    /// What the caller means to read. An empty list is audio out, which collapses the root.
49    pub asks: Vec<Ask>,
50    /// The operation count this render may pay.
51    pub flop_budget: u128,
52    /// What reads one of these keeps one value in the store, its last.
53    pub volatile: Vec<String>,
54    pub cache_policy: Option<CachePolicy>,
55}
56
57impl RenderConfig {
58    pub fn at(rate: u32) -> RenderConfig {
59        RenderConfig {
60            rate,
61            range: Range::default(),
62            until: None,
63            profile: PSYCHOACOUSTIC_V1,
64            asks: Vec::new(),
65            flop_budget: PSYCHOACOUSTIC_V1.flop_budget,
66            volatile: Vec::new(),
67            cache_policy: None,
68        }
69    }
70
71    pub fn seconds(rate: u32, secs: f64) -> RenderConfig {
72        let end = (secs * f64::from(rate)).round() as i64;
73        RenderConfig {
74            range: Range {
75                start: Some(0),
76                end: Some(end),
77            },
78            ..RenderConfig::at(rate)
79        }
80    }
81
82    pub fn asking(mut self, asks: Vec<Ask>) -> RenderConfig {
83        self.asks = asks;
84        self
85    }
86}
87
88pub use answer::{answer, answer_buffer, sketch_atom};
89pub use drive::Block;
90pub use stream::{Change, Changed, Counts, LATEST, Placed, STREAMED, Stream, StreamConfig, change};
91pub use terms::{Handle, NOTES};
92pub use through::{render_through, warm};
93pub use until::Until;
94
95/// Samples a whole render pulls at once; any size writes the same bits.
96const BLOCK: usize = 1 << 12;
97
98pub struct Render {
99    pub root: NodeId,
100    pub tys: Typing,
101    pub buffers: BTreeMap<NodeId, Buffer>,
102    pub frames: BTreeMap<NodeId, Frames>,
103    pub symbolic: BTreeMap<NodeId, SpectralSum>,
104    pub labels: BTreeMap<NodeId, Label>,
105    pub traces: Vec<FilterTrace>,
106    pub config: RenderConfig,
107    pub schedule: Schedule,
108    pub bindings: BTreeMap<NodeId, Vec<Binding>>,
109    pub cache_stats: Option<CacheStats>,
110    /// The most bytes the table held at once, samples and state.
111    pub held_bytes: usize,
112    /// The samples the root was read over; `None` where no reading needed any.
113    pub range: Option<Extent>,
114    pub(crate) unranged: Option<EngineError>,
115    /// Every value the render read, each over the segments it computed.
116    pub(crate) table: Option<Table>,
117}
118
119impl Render {
120    pub(crate) fn shell(
121        tys: Typing,
122        root: NodeId,
123        config: RenderConfig,
124        schedule: Schedule,
125    ) -> Self {
126        Render {
127            root,
128            tys,
129            buffers: BTreeMap::new(),
130            frames: BTreeMap::new(),
131            symbolic: BTreeMap::new(),
132            labels: BTreeMap::new(),
133            traces: Vec::new(),
134            config,
135            schedule,
136            bindings: BTreeMap::new(),
137            cache_stats: None,
138            held_bytes: 0,
139            range: None,
140            unranged: None,
141            table: None,
142        }
143    }
144
145    pub(crate) fn rate(&self) -> u32 {
146        self.config.rate
147    }
148
149    /// What its schedule prices: every value once over the range, whatever the store answered.
150    pub fn work(&self) -> crate::flops::Work {
151        crate::flops::Work {
152            samples: self.range.map_or(0, |range| range.len() as u64),
153            priced_flops: crate::flops::total(self),
154            waves: None,
155        }
156    }
157
158    /// A node's samples over the range, zero where it holds none.
159    pub fn output(&self, node: NodeId) -> Result<Buffer, EngineError> {
160        match (self.buffers.get(&node), self.range) {
161            (Some(held), Some(range)) => Ok(held.over(range, held.extent())),
162            _ => Err(answer::unheld(self, node)),
163        }
164    }
165
166    pub fn buffer(&self, node: NodeId) -> Option<&Buffer> {
167        self.buffers.get(&node)
168    }
169
170    pub fn id(&self, path: &str) -> Option<NodeId> {
171        self.tys.id(path)
172    }
173
174    /// The node a reading names, refusing by name where a file expanded into several.
175    pub fn node(&self, path: &str) -> Result<NodeId, EngineError> {
176        self.tys.resolve(path)
177    }
178
179    /// Each segment the render computed of `node`'s value, in order: a sample in two was
180    /// computed twice.
181    pub fn evaluated(&self, node: NodeId) -> Vec<Extent> {
182        let Some(table) = &self.table else {
183            return Vec::new();
184        };
185        table
186            .of(node)
187            .map_or(Vec::new(), |at| table.values[at].evaluated.clone())
188    }
189
190    /// The multiple a reading asks this node's score against, where one asks for a score at all.
191    pub fn alias_oversample(&self, node: NodeId) -> Option<u32> {
192        self.config
193            .asks
194            .iter()
195            .find_map(|ask| match ask.representation {
196                crate::query::Representation::Alias { oversample }
197                    if self.node(&ask.node).is_ok_and(|asked| asked == node) =>
198                {
199                    Some(oversample)
200                }
201                _ => None,
202            })
203    }
204
205    pub fn alias_score(&self, node: NodeId) -> AliasScore {
206        match self.alias_oversample(node) {
207            Some(_) => AliasScore::Asked,
208            None => AliasScore::NotAsked,
209        }
210    }
211}
212
213/// Nothing is materialized that no reading asked for.
214pub fn render(
215    graph: &Graph,
216    target: &str,
217    config: RenderConfig,
218    cache: Option<&Cache>,
219) -> Result<Render, EngineError> {
220    let recording = Recording::over(cache, config.cache_policy);
221    let mut held = planned(
222        prepared(graph, target, config.rate)?,
223        config,
224        &BTreeSet::new(),
225    )?;
226    pulled(&mut held, recording)?;
227    closed(&mut held)?;
228    Ok(held)
229}
230
231fn closed(held: &mut Render) -> Result<(), EngineError> {
232    scored(held)?;
233    compose_read(held);
234    stamp(held);
235    Ok(())
236}
237
238pub(crate) struct Prepared<'g> {
239    pub(crate) instances: instantiate::Instances<'g>,
240    pub(crate) tys: Typing,
241    pub(crate) root: NodeId,
242}
243
244pub(crate) fn prepared<'g>(
245    graph: &'g Graph,
246    target: &str,
247    rate: u32,
248) -> Result<Prepared<'g>, EngineError> {
249    let instances = instantiate::instantiate(graph, target, rate)?;
250    let held = instances.instance_of(target)?;
251    let order = schedule::schedule_from(&instances, std::slice::from_ref(&held))?;
252    let tys = typing::infer_all(&instances, &order)?;
253    let root = tys
254        .id(&held)
255        .ok_or_else(|| EngineError::UnknownNode(held.clone()))?;
256    Ok(Prepared {
257        instances,
258        tys,
259        root,
260    })
261}
262
263fn planned(
264    prepared: Prepared<'_>,
265    config: RenderConfig,
266    bounds: &BTreeSet<NodeId>,
267) -> Result<Render, EngineError> {
268    let Prepared {
269        instances,
270        tys,
271        root,
272    } = prepared;
273    planned_over(&instances, (tys, root), config, bounds)
274}
275
276fn planned_over(
277    instances: &instantiate::Instances,
278    (tys, root): (Typing, NodeId),
279    config: RenderConfig,
280    bounds: &BTreeSet<NodeId>,
281) -> Result<Render, EngineError> {
282    let schedule = schedule::plan(&tys, root, &config.asks);
283    let bindings = tys
284        .paths()
285        .filter_map(|(path, id)| Some((id, resolved(instances, path)?)))
286        .collect();
287    let mut held = Render::shell(tys, root, config, schedule);
288    held.bindings = bindings;
289    ranged(&mut held, bounds)?;
290    let target = held.tys.name(held.root).to_string();
291    let volatile = volatile::mark(instances, &held, &target)?;
292    if let Some(table) = &mut held.table {
293        table.slots(|id| volatile.slot(id));
294    }
295    Ok(held)
296}
297
298/// The range and every value a render of `target` would compute, and no sample.
299pub fn plan(graph: &Graph, target: &str, config: RenderConfig) -> Result<Render, EngineError> {
300    planned(
301        prepared(graph, target, config.rate)?,
302        config,
303        &BTreeSet::new(),
304    )
305}
306
307/// The sample each of `roots` read bare would end at, `None` where its support, pruning
308/// included, never ends and such a render refuses for it. Typed together, and no sample.
309pub fn ends(
310    graph: &Graph,
311    roots: &[String],
312    config: &RenderConfig,
313) -> Result<Vec<Option<i64>>, EngineError> {
314    let (instances, named) = instantiate::from_roots(graph, roots, config.rate)?;
315    let order = schedule::schedule_from(&instances, &named)?;
316    let tys = typing::infer_all(&instances, &order)?;
317    let supports = Supports::new(&tys, &config.profile);
318    named
319        .iter()
320        .map(|held| {
321            let id = tys
322                .id(held)
323                .ok_or_else(|| EngineError::UnknownNode(held.clone()))?;
324            Ok(default_end(supports.of(id)))
325        })
326        .collect()
327}
328
329/// A reading of samples or of their cost needs the range; lines and structure never do.
330fn ranged(held: &mut Render, bounds: &BTreeSet<NodeId>) -> Result<(), EngineError> {
331    let counts = counts(&held.config.asks);
332    let envelope = held.config.asks.iter().any(|ask| {
333        matches!(
334            ask.representation,
335            crate::query::Representation::Envelope { .. }
336        )
337    });
338    if !materializes(held) && !counts {
339        if envelope && let Err(refused) = range_of(held, Ends::Refused) {
340            held.unranged = Some(refused);
341        } else if envelope {
342            held.range = Some(range_of(held, Ends::Refused)?);
343        }
344        return Ok(());
345    }
346    held.range = Some(range_of(held, Ends::Refused)?);
347    let wanted: Vec<NodeId> = held.schedule.wanted.clone();
348    let root = (held.root, wanted.as_slice());
349    let mut table = Table::bounded(&held.tys, root, &held.config.profile, bounds)?;
350    table.plan(held.range.expect("a range was decided"));
351    held.table = Some(table);
352    Ok(())
353}
354
355fn materializes(held: &Render) -> bool {
356    !held.schedule.wanted.is_empty()
357}
358
359pub(crate) enum Ends {
360    Refused,
361    Pulled,
362}
363
364pub(crate) fn range_of(held: &Render, ends: Ends) -> Result<Extent, EngineError> {
365    let support = Supports::new(&held.tys, &held.config.profile).of(held.root);
366    let start = held
367        .config
368        .range
369        .start
370        .unwrap_or_else(|| default_start(support));
371    let end = match held.config.range.end.or(default_end(support)) {
372        Some(end) => end,
373        None => match ends {
374            Ends::Pulled => i64::MAX,
375            Ends::Refused => return Err(endless(held)),
376        },
377    };
378    Ok(Extent::new(start, end.max(start)))
379}
380
381fn default_start(support: Extent) -> i64 {
382    match support.is_empty() || support.start == i64::MIN || support.start > 0 {
383        true => 0,
384        false => support.start,
385    }
386}
387
388fn default_end(support: Extent) -> Option<i64> {
389    (support.end != i64::MAX).then_some(support.end)
390}
391
392fn endless(held: &Render) -> EngineError {
393    let name = held.tys.name(held.root);
394    EngineError::refused(Diagnostic {
395        code: "render.no_end".to_string(),
396        message: format!(
397            "`{name}` is read over an interval with no end, and its support never ends"
398        ),
399        location: Located::at(name, None),
400        help: "give the interval an end, as `[0, 2s]`, or crop it".to_string(),
401    })
402}
403
404/// A `flops` reading counts what the audio render would run.
405fn counts(asks: &[Ask]) -> bool {
406    asks.iter()
407        .any(|ask| ask.representation == crate::query::Representation::Flops)
408}
409
410/// A reading that materializes nothing is never refused for cost; a count past the budget
411/// refuses before a sample is computed.
412fn affordable(held: &Render) -> Result<(), EngineError> {
413    if !materializes(held) {
414        return Ok(());
415    }
416    let total = crate::flops::total(held);
417    if total <= held.config.flop_budget {
418        return Ok(());
419    }
420    let counted = crate::flops::tree(held);
421    let over = crate::flops::dominating(&counted).expect("a counted tree holds its root");
422    Err(EngineError::refused(Diagnostic {
423        code: "collapse.over_budget".to_string(),
424        message: format!(
425            "this render counts {} operations, over the budget of {}; `{}` dominates it at {} \
426             by {}",
427            counted.total, counted.budget, over.node, over.subtree, over.route
428        ),
429        location: Located::at(held.tys.name(held.root), None),
430        help: format!("pass --flop-budget {total} to render it anyway"),
431    }))
432}
433
434/// Every wanted value pulled over the range, block by block, until `until` stops it.
435fn pulled(held: &mut Render, recording: Recording) -> Result<(), EngineError> {
436    if let Some(mut driver) = driving(held, recording)? {
437        while driver.pull()? {}
438        drove(held, driver, true);
439    }
440    Ok(())
441}
442
443/// What pulls a render's table, where it materializes one at all.
444fn driving(held: &mut Render, recording: Recording) -> Result<Option<drive::Driver>, EngineError> {
445    affordable(held)?;
446    let (Some(table), Some(range)) = (held.table.take(), held.range) else {
447        return Ok(None);
448    };
449    if !materializes(held) {
450        held.table = Some(table);
451        return Ok(None);
452    }
453    Ok(Some(drive::Driver::new(
454        table,
455        range,
456        BLOCK,
457        &held.config,
458        recording,
459    )))
460}
461
462/// `keep`: each wanted value's samples copied out of the table.
463fn drove(held: &mut Render, driver: drive::Driver, keep: bool) {
464    let range = held.range.expect("a pulled render has a range");
465    held.held_bytes = driver.most_bytes();
466    held.cache_stats = Some(driver.recording.stats());
467    if let Some(stop) = driver.stop().filter(|stop| *stop < range.end) {
468        held.range = Some(Extent::new(range.start, stop));
469    }
470    let range = held.range.expect("a pulled render has a range");
471    let table = driver.table;
472    let wanted = held.schedule.wanted.iter().filter(|_| keep);
473    for (id, at) in wanted.map(|id| (*id, table.of(*id))) {
474        let Some(at) = at else {
475            continue;
476        };
477        match &table.values[at].held {
478            table::Held::Frames(Some(frames)) => {
479                held.frames.insert(id, (**frames).clone());
480            }
481            _ => {
482                held.buffers.insert(id, table.samples(at, range));
483                held.labels.insert(id, table.label(at));
484            }
485        }
486    }
487    held.table = Some(table);
488}
489
490/// A closed form's value `fine` times finer than the render's step: what an alias score
491/// reads against.
492pub(crate) fn finer(
493    render: &Render,
494    node: NodeId,
495    fine: u32,
496    over: Extent,
497) -> Result<Buffer, EngineError> {
498    let profile = &render.config.profile;
499    let mut table = Table::finer(&render.tys, node, &[node], profile, i128::from(fine))?;
500    let at = table.root;
501    table.pull(over, &mut Recording::over(None, None))?;
502    let mut held = table.samples(at, over);
503    held.rate = render.config.rate * fine;
504    Ok(held)
505}
506
507/// A point sampling a reading asks the score of says in its label what the grid lost.
508fn scored(held: &mut Render) -> Result<(), EngineError> {
509    let asked: Vec<NodeId> = held
510        .labels
511        .keys()
512        .copied()
513        .filter(|id| held.alias_oversample(*id).is_some())
514        .collect();
515    for id in asked {
516        let sva_samples::Detail::Point {
517            rule,
518            alias_db: None,
519        } = held.labels[&id].detail
520        else {
521            continue;
522        };
523        let buffer = held.output(id)?;
524        let alias_db = Some(answer::alias_db(held, id, &buffer)?);
525        let label = held.labels.get_mut(&id).expect("an asked label");
526        label.detail = sva_samples::Detail::Point { rule, alias_db };
527    }
528    Ok(())
529}
530
531/// `render` with every read its own value, as if each were written out where it is read.
532#[cfg(test)]
533pub(crate) fn render_apart(
534    graph: &Graph,
535    target: &str,
536    config: RenderConfig,
537) -> Result<Render, EngineError> {
538    let mut held = planned(
539        prepared(graph, target, config.rate)?,
540        config,
541        &BTreeSet::new(),
542    )?;
543    if let (Some(range), Some(_)) = (held.range, &held.table) {
544        let wanted = held.schedule.wanted.clone();
545        let mut table = Table::apart(&held.tys, held.root, &wanted, &held.config.profile)?;
546        table.plan(range);
547        held.table = Some(table);
548    }
549    pulled(&mut held, Recording::over(None, None))?;
550    Ok(held)
551}
552
553/// A node's value pulled over `over` in a table of its own.
554pub(crate) fn sampled(render: &Render, node: NodeId, over: Extent) -> Result<Buffer, EngineError> {
555    let mut table = Table::build(&render.tys, node, &[node], &render.config.profile)?;
556    let at = table.root;
557    table.pull(over, &mut Recording::over(None, None))?;
558    Ok(table.samples(at, over))
559}
560
561/// FORMAT 9.3: the render's own label says what it cost and what it was allowed.
562fn stamp(held: &mut Render) {
563    let root = held.root;
564    let Some(label) = held.labels.remove(&root) else {
565        return;
566    };
567    let counted = crate::flops::total(held);
568    let label = sva_samples::Label {
569        rate: held.config.rate,
570        moved: held.table.as_ref().map(|table| table.moved),
571        pruned: held.table.as_ref().map(|table| table.pruned()),
572        ..label.costing(counted, held.config.flop_budget)
573    };
574    held.labels.insert(root, label);
575}
576
577/// One render, every reading: a closed form a reading asks for is composed once here; one
578/// that refuses is left for the reading to raise.
579fn compose_read(held: &mut Render) {
580    for id in held.schedule.compose.clone() {
581        if held.symbolic.contains_key(&id) {
582            continue;
583        }
584        if let Ok(sum) = refs::spectral_sum_of(&held.tys, id, held.tys.var(id)) {
585            held.symbolic.insert(id, sum);
586        }
587    }
588}
589
590fn resolved(instances: &instantiate::Instances, path: &str) -> Option<Vec<Binding>> {
591    Some(
592        instances
593            .bindings(path)?
594            .into_iter()
595            .map(|(name, expr, cx)| Binding {
596                name: name.to_string(),
597                source: instances.render(expr, cx),
598            })
599            .collect(),
600    )
601}
sva_engine/render/mod.rs

sva_engine/render/
mod.rs
