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

sva_engine/render/
mod.rs
