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

sva_engine/render/
mod.rs
