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

sva_engine/render/
mod.rs
