sva_engine/render/
through.rs

1// Concern: renders or warms from the root down through a persistent store, staging what it computes | Non-concern: the store's medium and commit | IO: (&Graph, target, Store) -> Render or CacheStats
2
3use std::collections::{BTreeMap, BTreeSet};
4
5use sva_ast::Graph;
6use sva_formula::{Hash, Held as Representation, NodeId};
7
8use super::table::spill::Spill;
9use super::table::{self, Table};
10use super::{Render, RenderConfig, closed, drive, driving, drove, frontier, planned_over};
11use crate::cache::{Backend, CacheStats, Lookup, Outcome, Recording, Store, Stored, Through};
12use crate::error::EngineError;
13use crate::instantiate;
14use crate::schedule;
15use crate::typing::{self, Typing};
16
17/// `render` through `store`, from the root down: a node the store answers stands as its
18/// samples, and nothing under it is typed, planned or looked up. What the rest computes is
19/// staged beside the store as the render drops it; only `persist` writes the store. A failing
20/// store fails no render: it stages nothing more, and its stats say why.
21pub async fn render_through<B: Backend>(
22    graph: &Graph,
23    target: &str,
24    config: RenderConfig,
25    store: &Store<B>,
26) -> Result<Render, EngineError> {
27    match through(graph, target, config, store, Keep::Wanted).await? {
28        Reached::Render(held) => Ok(*held),
29        Reached::Held(_) => unreachable!("a render reads a stored root's samples"),
30    }
31}
32
33/// `render_through`'s staging alone, `config` asking nothing: a stored root ends it unread.
34pub async fn warm<B: Backend>(
35    graph: &Graph,
36    target: &str,
37    config: RenderConfig,
38    store: &Store<B>,
39) -> Result<CacheStats, EngineError> {
40    Ok(
41        match through(graph, target, config, store, Keep::Nothing).await? {
42            Reached::Render(mut held) => held.cache_stats.take().expect("a render through a store"),
43            Reached::Held(lookups) => CacheStats {
44                lookups,
45                ..CacheStats::default()
46            },
47        },
48    )
49}
50
51#[derive(Clone, Copy, PartialEq, Eq)]
52enum Keep {
53    Wanted,
54    Nothing,
55}
56
57enum Reached {
58    Render(Box<Render>),
59    Held(Vec<Lookup>),
60}
61
62async fn through<B: Backend>(
63    graph: &Graph,
64    target: &str,
65    config: RenderConfig,
66    store: &Store<B>,
67    keep: Keep,
68) -> Result<Reached, EngineError> {
69    let instances = instantiate::instantiate(graph, target, config.rate)?;
70    let root = instances.instance_of(target)?;
71    let order = schedule::schedule_from(&instances, std::slice::from_ref(&root))?;
72    let keys = keys(graph, &instances, &order, &config);
73    let mut found = frontier::Frontier::from((&instances, &order), &keys, &root, (&config, false));
74    let mut known = frontier::Known::new();
75    found.walked(&mut known, store).await;
76    if keep == Keep::Nothing && found.stored.contains_key(&root) {
77        return Ok(Reached::Held(found.lookups));
78    }
79    let (mut held, typed) = loop {
80        found.walked(&mut known, store).await;
81        let tys = typing::infer_over(&instances, &order.within(&found.visited), &found.stored)?;
82        let id = tys
83            .id(&root)
84            .ok_or_else(|| EngineError::UnknownNode(root.clone()))?;
85        let bounds: BTreeSet<NodeId> = keys
86            .keys()
87            .filter_map(|path| tys.id(path))
88            .filter(|id| readable(&tys, *id))
89            .collect();
90        let typed = tys.lowered().to_vec();
91        let mut held = planned_over(&instances, (tys, id), config.clone(), &bounds)?;
92        let short = match (&mut held.table, held.range) {
93            (Some(table), Some(range)) => {
94                load(table, store, range, &BTreeSet::new()).await;
95                short(table, range)
96            }
97            _ => Vec::new(),
98        };
99        if short.is_empty() {
100            break (held, typed);
101        }
102        for path in short {
103            found.reopen(&path);
104        }
105    };
106    let staging = staging(&held, &keys, &found);
107    let mut kept = BTreeSet::new();
108    let mut unstaged = None;
109    if let Some(mut driver) = driving(&mut held, Recording::over(None, None))? {
110        driver.spill = Some(Spill::over(staging));
111        while spilled(&mut driver, store, &mut kept, &mut unstaged).await? {}
112        let rest = driver.spill.take().map(|mut s| s.rest(&driver.table));
113        for (key, meta) in rest.into_iter().flatten() {
114            if staged(&mut unstaged, store.stage_meta(key, &meta)).await {
115                kept.insert(key);
116            }
117        }
118        drove(&mut held, driver, keep == Keep::Wanted);
119    }
120    let computed = held.table.as_ref().map_or(Vec::new(), |table| {
121        let computed = table.values.iter();
122        let computed = computed.filter(|v| !matches!(v.kind, table::Kind::Stored { .. }));
123        computed.map(|v| v.name.clone()).collect()
124    });
125    let mut lookups = found.lookups;
126    for lookup in &mut lookups {
127        if lookup.outcome == Outcome::ComputedNotStored && kept.contains(&lookup.key) {
128            lookup.outcome = Outcome::ComputedStored;
129        }
130    }
131    let reached = held.cache_stats.take().map_or(Vec::new(), |stats| {
132        let walked = lookups.len();
133        stats.reached.iter().map(|(at, _)| (*at, walked)).collect()
134    });
135    held.cache_stats = Some(CacheStats {
136        lookups,
137        reached,
138        typed,
139        planned: computed,
140        unstaged,
141        ..CacheStats::default()
142    });
143    closed(&mut held)?;
144    Ok(Reached::Render(Box::new(held)))
145}
146
147/// Each instance's store key: its source identity at the render's rate and profile.
148pub(crate) fn keys(
149    graph: &Graph,
150    instances: &instantiate::Instances,
151    order: &schedule::Order,
152    config: &RenderConfig,
153) -> BTreeMap<String, Hash> {
154    crate::source::identities(graph, instances, order)
155        .into_iter()
156        .map(|(path, identity)| {
157            let key = crate::cache::node_key(identity, config.rate, &config.profile);
158            (path, key)
159        })
160        .collect()
161}
162
163/// What `window` asks of each stored value's samples but those under `skip`, read off `store`;
164/// what it cannot read stays short.
165pub(crate) async fn load(
166    table: &mut Table,
167    store: &impl Through,
168    window: sva_samples::Extent,
169    skip: &BTreeSet<Hash>,
170) {
171    for (stored, over) in table.wants(window) {
172        if skip.contains(&stored.key) {
173            continue;
174        }
175        if let Some(samples) = store.read(&stored, over).await {
176            table.took(stored.key, &samples);
177        }
178    }
179}
180
181/// Each stored node whose samples miss some its readers ask over `range`.
182fn short(table: &Table, range: sva_samples::Extent) -> Vec<String> {
183    let needs = table.demand(range);
184    table
185        .values
186        .iter()
187        .zip(&needs)
188        .filter(|(value, need)| {
189            matches!(value.kind, table::Kind::Stored { .. }) && !need.compute.is_empty()
190        })
191        .map(|(value, _)| value.name.clone())
192        .collect()
193}
194
195/// One block pulled, and what it handed out moved into the staging area.
196async fn spilled<B: Backend>(
197    driver: &mut drive::Driver,
198    store: &Store<B>,
199    kept: &mut BTreeSet<Hash>,
200    unstaged: &mut Option<String>,
201) -> Result<bool, EngineError> {
202    let more = driver.pull()?;
203    let spill = driver
204        .spill
205        .as_mut()
206        .expect("a render through a store spills");
207    for (key, samples) in std::mem::take(&mut spill.samples) {
208        staged(unstaged, store.stage(key, &samples)).await;
209    }
210    for (key, meta) in spill.whole(&driver.table) {
211        if staged(unstaged, store.stage_meta(key, &meta)).await {
212            kept.insert(key);
213        }
214    }
215    Ok(more)
216}
217
218/// `stage` done, unless one before it failed.
219async fn staged(
220    unstaged: &mut Option<String>,
221    stage: impl Future<Output = Result<(), String>>,
222) -> bool {
223    if unstaged.is_some() {
224        return false;
225    }
226    match stage.await {
227        Ok(()) => true,
228        Err(why) => {
229            *unstaged = Some(why);
230            false
231        }
232    }
233}
234
235/// A node another may read as its samples alone: samples, and nothing that reads it between
236/// them.
237fn readable(tys: &Typing, id: NodeId) -> bool {
238    tys.ty(id).held == Representation::Sampled && !schedule::anywhere(tys, id)
239}
240
241/// Each value a missed node computes, at its own node's key: the root whatever it is, any
242/// other where a reader may take its samples. One that only moves a value stored or staged
243/// stands for that value's samples, holding none of its own.
244fn staging(
245    held: &Render,
246    keys: &BTreeMap<String, Hash>,
247    found: &frontier::Frontier<'_>,
248) -> Vec<(usize, Hash, Stored)> {
249    let Some(table) = &held.table else {
250        return Vec::new();
251    };
252    let tys = &held.tys;
253    let mut out = Vec::new();
254    for (path, key) in keys {
255        if found.stored.contains_key(path) || !found.visited.contains(path) {
256            continue;
257        }
258        let Some((id, at)) = tys.id(path).and_then(|id| Some((id, table.of(id)?))) else {
259            continue;
260        };
261        let value = &table.values[at];
262        let own = tys.name(id) == path;
263        let readable = readable(tys, id) && value.alias().is_none();
264        let kept = value.pure
265            && value.period.is_none()
266            && !matches!(value.kind, table::Kind::Frames { .. });
267        if !own || !kept || !(at == table.root || readable) {
268            continue;
269        }
270        let (priced, moved) = under(table, at);
271        let ty = tys.ty(id);
272        let meta = Stored {
273            key: *key,
274            samples: Default::default(),
275            label: table.label(at),
276            width: u8::try_from(value.width).expect("a width the typing held"),
277            codomain: ty.codomain,
278            rate: ty.rate,
279            grid: tys.grid(id),
280            support: value.support,
281            priced,
282            moved,
283            readable,
284        };
285        out.push((at, *key, meta));
286    }
287    let staged: BTreeMap<usize, Hash> = out.iter().map(|(at, key, _)| (*at, *key)).collect();
288    for (at, _, meta) in &mut out {
289        let Some((moved, by)) = moves(table, *at) else {
290            continue;
291        };
292        let stored = table.values[moved].node.and_then(|id| {
293            let (file, shift) = found.stored.get(tys.name(id))?.file()?;
294            Some((file, by - shift))
295        });
296        let staged = staged.get(&moved).map(|key| (*key, by));
297        if let Some((of, by)) = staged.or(stored) {
298            *meta = meta.clone().referring(of, by);
299        }
300    }
301    out
302}
303
304/// The value `at` only moves, through every move between, and by how much.
305fn moves(table: &Table, at: usize) -> Option<(usize, i64)> {
306    let (mut read, mut by) = table.values[at].moves()?;
307    while let Some((next, shift)) = table.values[read].moves() {
308        (read, by) = (next, by + shift);
309    }
310    Some((read, by))
311}
312
313/// What a value and every value under it cost over the range, and the most any moved a read.
314fn under(table: &Table, at: usize) -> (u128, f64) {
315    let (mut seen, mut open) = (BTreeSet::from([at]), vec![at]);
316    let (mut priced, mut moved) = (0u128, 0.0f64);
317    while let Some(at) = open.pop() {
318        priced += table.planned[at];
319        moved = moved.max(table.values[at].moved);
320        open.extend(
321            table.values[at]
322                .reads
323                .iter()
324                .filter(|read| seen.insert(**read)),
325        );
326    }
327    (priced, moved)
328}
sva_engine/render/through.rs

sva_engine/render/
through.rs
