sva_engine/render/
through.rs

1// Concern: renders from the root down through a persistent store, staging what it computes | Non-concern: the store's medium and commit, a render with no store | IO: (&Graph, target, Store) -> Render
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, Outcome, Recording, Store, Stored};
12use crate::error::{Diagnostic, EngineError, Located};
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.
20pub async fn render_through<B: Backend>(
21    graph: &Graph,
22    target: &str,
23    config: RenderConfig,
24    store: &Store<B>,
25) -> Result<Render, EngineError> {
26    let instances = instantiate::instantiate(graph, target, config.rate)?;
27    let root = instances.instance_of(target)?;
28    let order = schedule::schedule_from(&instances, std::slice::from_ref(&root))?;
29    let keys = keys(graph, &instances, &order, &config);
30    let mut found = frontier::Frontier::from((&instances, &order), &keys, &root, &config);
31    let (mut held, typed) = loop {
32        found.walk(store).await;
33        let tys = typing::infer_over(&instances, &order.within(&found.visited), &found.stored)?;
34        let id = tys
35            .id(&root)
36            .ok_or_else(|| EngineError::UnknownNode(root.clone()))?;
37        let bounds: BTreeSet<NodeId> = keys
38            .keys()
39            .filter_map(|path| tys.id(path))
40            .filter(|id| readable(&tys, *id))
41            .collect();
42        let typed = tys.lowered().to_vec();
43        let held = planned_over(&instances, (tys, id), config.clone(), &bounds)?;
44        let short = match (&held.table, held.range) {
45            (Some(table), Some(range)) => short(table, range),
46            _ => Vec::new(),
47        };
48        if short.is_empty() {
49            break (held, typed);
50        }
51        for path in short {
52            found.reopen(&path);
53        }
54    };
55    let staging = staging(&held, &keys, &found);
56    let mut kept = BTreeSet::new();
57    if let Some(mut driver) = driving(&mut held, Recording::over(None, None))? {
58        driver.spill = Some(Spill::over(staging));
59        while spilled(&mut driver, store, &mut kept).await? {}
60        let rest = driver.spill.take().map(|mut s| s.rest(&driver.table));
61        for (key, meta) in rest.into_iter().flatten() {
62            store.stage_meta(key, &meta).await.map_err(unstaged)?;
63            kept.insert(key);
64        }
65        drove(&mut held, driver);
66    }
67    let computed = held.table.as_ref().map_or(Vec::new(), |table| {
68        let computed = table.values.iter();
69        let computed = computed.filter(|v| !matches!(v.kind, table::Kind::Stored { .. }));
70        computed.map(|v| v.name.clone()).collect()
71    });
72    let mut lookups = found.lookups;
73    for lookup in &mut lookups {
74        if lookup.outcome == Outcome::ComputedNotStored && kept.contains(&lookup.key) {
75            lookup.outcome = Outcome::ComputedStored;
76        }
77    }
78    let reached = held.cache_stats.take().map_or(Vec::new(), |stats| {
79        let walked = lookups.len();
80        stats.reached.iter().map(|(at, _)| (*at, walked)).collect()
81    });
82    held.cache_stats = Some(CacheStats {
83        lookups,
84        reached,
85        typed,
86        planned: computed,
87        ..CacheStats::default()
88    });
89    closed(&mut held)?;
90    Ok(held)
91}
92
93/// Each instance's store key: its source identity at the render's rate and profile.
94pub(crate) fn keys(
95    graph: &Graph,
96    instances: &instantiate::Instances,
97    order: &schedule::Order,
98    config: &RenderConfig,
99) -> BTreeMap<String, Hash> {
100    crate::source::identities(graph, instances, order)
101        .into_iter()
102        .map(|(path, identity)| {
103            let key = crate::cache::node_key(identity, config.rate, &config.profile);
104            (path, key)
105        })
106        .collect()
107}
108
109/// Each stored node whose samples miss some its readers ask over `range`.
110pub(crate) fn short(table: &Table, range: sva_samples::Extent) -> Vec<String> {
111    let needs = table.demand(range);
112    table
113        .values
114        .iter()
115        .zip(&needs)
116        .filter(|(value, need)| {
117            matches!(value.kind, table::Kind::Stored { .. }) && !need.compute.is_empty()
118        })
119        .map(|(value, _)| value.name.clone())
120        .collect()
121}
122
123/// One block pulled, and what it handed out moved into the staging area.
124async fn spilled<B: Backend>(
125    driver: &mut drive::Driver,
126    store: &Store<B>,
127    kept: &mut BTreeSet<Hash>,
128) -> Result<bool, EngineError> {
129    let more = driver.pull()?;
130    let spill = driver
131        .spill
132        .as_mut()
133        .expect("a render through a store spills");
134    for (key, samples) in std::mem::take(&mut spill.samples) {
135        store.stage(key, &samples).await.map_err(unstaged)?;
136    }
137    for (key, meta) in spill.whole(&driver.table) {
138        store.stage_meta(key, &meta).await.map_err(unstaged)?;
139        kept.insert(key);
140    }
141    Ok(more)
142}
143
144fn unstaged(why: String) -> EngineError {
145    EngineError::refused(Diagnostic {
146        code: "store.unwritable".to_string(),
147        message: format!("what the render computed could not be staged beside the store: {why}"),
148        location: Located::default(),
149        help: "free the store's disk, move it with `--cache <path>`, or pass `--cache none`"
150            .to_string(),
151    })
152}
153
154/// A node another may read as its samples alone: samples, and nothing that reads it between
155/// them.
156fn readable(tys: &Typing, id: NodeId) -> bool {
157    tys.ty(id).held == Representation::Sampled && !schedule::anywhere(tys, id)
158}
159
160/// Each value a missed node computes, at its own node's key: the root whatever it is, any
161/// other where a reader may take its samples.
162fn staging(
163    held: &Render,
164    keys: &BTreeMap<String, Hash>,
165    found: &frontier::Frontier<'_>,
166) -> Vec<(usize, Hash, Stored)> {
167    let Some(table) = &held.table else {
168        return Vec::new();
169    };
170    let tys = &held.tys;
171    let mut out = Vec::new();
172    for (path, key) in keys {
173        if found.stored.contains_key(path) || !found.visited.contains(path) {
174            continue;
175        }
176        let Some((id, at)) = tys.id(path).and_then(|id| Some((id, table.of(id)?))) else {
177            continue;
178        };
179        let value = &table.values[at];
180        let own = tys.name(id) == path;
181        let readable = readable(tys, id) && value.alias().is_none();
182        let kept = value.pure
183            && value.period.is_none()
184            && !matches!(value.kind, table::Kind::Frames { .. });
185        if !own || !kept || !(at == table.root || readable) {
186            continue;
187        }
188        let (priced, moved) = under(table, at);
189        let ty = tys.ty(id);
190        let meta = Stored {
191            key: *key,
192            segments: Vec::new(),
193            label: table.label(at),
194            width: u8::try_from(value.width).expect("a width the typing held"),
195            codomain: ty.codomain,
196            rate: ty.rate,
197            grid: tys.grid(id),
198            support: value.support,
199            priced,
200            moved,
201            readable,
202        };
203        out.push((at, *key, meta));
204    }
205    out
206}
207
208/// What a value and every value under it cost over the range, and the most any moved a read.
209fn under(table: &Table, at: usize) -> (u128, f64) {
210    let (mut seen, mut open) = (BTreeSet::from([at]), vec![at]);
211    let (mut priced, mut moved) = (0u128, 0.0f64);
212    while let Some(at) = open.pop() {
213        priced += table.planned[at];
214        moved = moved.max(table.values[at].moved);
215        open.extend(
216            table.values[at]
217                .reads
218                .iter()
219                .filter(|read| seen.insert(**read)),
220        );
221    }
222    (priced, moved)
223}
sva_engine/render/through.rs

sva_engine/render/
through.rs
