sva_engine/refs/
identity.rs

1// Concern: content-addresses one node, whatever representation it holds | Non-concern: composing a closed form across a ref (mod.rs) | IO: (NodeId) -> Hash
2
3use sva_formula::{
4    Body, ClosedForm, ContentHasher, Hash, HashDomain, NodeId, Var, hash_written_with,
5};
6
7use sva_samples::Params;
8
9use crate::error::EngineError;
10use crate::index::Round;
11use crate::typing::{Step, SumSlot, Typing, Value, When};
12
13use super::cyclic;
14
15/// What one node is, whatever it holds: its definition and the identities of what it reads,
16/// never where a reader places it.
17pub fn identity(typing: &Typing, node: NodeId) -> Result<Hash, EngineError> {
18    let folds = typing.folds();
19    for read in typing.unfolded(node, |id| folds.identity(id).is_some()) {
20        if read != node {
21            let _ = identity_of(typing, read, &mut Vec::new());
22        }
23    }
24    identity_of(typing, node, &mut Vec::new())
25}
26
27/// A cycle's refusal depends on where the walk entered it, so only an identity is kept.
28fn identity_of(typing: &Typing, node: NodeId, open: &mut Vec<NodeId>) -> Result<Hash, EngineError> {
29    if let Some(held) = typing.folds().identity(node) {
30        return Ok(held);
31    }
32    let found = match typing.sum_slots(node) {
33        Some(slots) => {
34            let mut sink = node_identity_hasher();
35            sink.text("terms");
36            for slot in slots {
37                sink.hash(match slot {
38                    SumSlot::Node(id) if *id == node => built(typing, node, open)?,
39                    SumSlot::Node(id) => identity_of(typing, *id, open)?,
40                    SumSlot::Retired(_) => continue,
41                });
42            }
43            sink.finish()
44        }
45        None => built(typing, node, open)?,
46    };
47    typing.folds().keep_identity(node, found);
48    Ok(found)
49}
50
51/// A form named as the same form written as a node is, each ref by `named` with the variable
52/// it holds: a ref to a form of the other variable reads across its transform.
53pub(super) fn written(
54    form: &ClosedForm,
55    named: &mut dyn FnMut(NodeId) -> Result<(Hash, Var), EngineError>,
56) -> Result<Hash, EngineError> {
57    let mut refused = None;
58    let hash = hash_written_with(form, &mut |id| match named(id) {
59        Ok((held, var)) if var == form.var => held,
60        Ok((held, _)) => {
61            let mut sink = node_identity_hasher();
62            sink.text("across");
63            sink.hash(held);
64            sink.finish()
65        }
66        Err(e) => {
67            refused.get_or_insert(e);
68            Hash(0, 0)
69        }
70    });
71    refused.map_or(Ok(hash), Err)
72}
73
74/// A subterm named as written, which decides its samples, bound and support alike.
75pub(crate) fn subterm_identity(typing: &Typing, form: &ClosedForm) -> Result<Hash, EngineError> {
76    written(form, &mut |id| Ok((identity(typing, id)?, typing.var(id))))
77}
78
79/// A solver, its varying fields named by their nodes: one name, held or read to a switch.
80pub(super) fn solver(params: &Params, varying: &[(&str, Hash)]) -> Hash {
81    let mut held = params.clone();
82    for (key, _) in varying {
83        *crate::lower::field(&mut held, key).expect("a varying field") = f64::NAN;
84    }
85    let mut sink = node_identity_hasher();
86    sink.text("solver");
87    held.words().into_iter().for_each(|w| sink.word(w));
88    for (key, at) in varying {
89        sink.text(key);
90        sink.hash(*at);
91    }
92    sink.finish()
93}
94
95fn built(typing: &Typing, node: NodeId, open: &mut Vec<NodeId>) -> Result<Hash, EngineError> {
96    if open.contains(&node) {
97        return Err(cyclic(typing, node));
98    }
99    open.push(node);
100    let found = shape(typing, node, &mut |id| identity_of(typing, id, open));
101    open.pop();
102    found
103}
104
105/// Its own value's shape over what it reads, each named by `named`.
106pub(crate) fn shape(
107    typing: &Typing,
108    node: NodeId,
109    named: &mut dyn FnMut(NodeId) -> Result<Hash, EngineError>,
110) -> Result<Hash, EngineError> {
111    let mut sink = node_identity_hasher();
112    match typing.value(node) {
113        Value::ClosedForm(form) => {
114            return written(form, &mut |id| Ok((named(id)?, typing.var(id))));
115        }
116        Value::Read { .. } if let Some(source) = passes(typing, node) => {
117            return named(source);
118        }
119        Value::Cast(cast, source) => {
120            sink.text(cast.name());
121            sink.hash(named(*source)?);
122        }
123        Value::Read { source, at, .. } => {
124            sink.text("read");
125            sink.hash(named(*source)?);
126            when(&mut sink, typing, at)?;
127        }
128        Value::SelfAt { at, .. } => {
129            sink.text("self");
130            when(&mut sink, typing, at)?;
131        }
132        Value::Noise(seed) => {
133            sink.text("noise");
134            sink.word(*seed);
135        }
136        Value::Recorded(recording) => {
137            sink.text("recorded");
138            sink.word(u64::from(recording.rate));
139            sink.word(recording.planes.len() as u64);
140            for plane in recording.planes.iter() {
141                sink.word(plane.len() as u64);
142                plane.iter().for_each(|v| sink.word(u64::from(v.to_bits())));
143            }
144        }
145        Value::Solver { params, varying } => {
146            let mut read = Vec::with_capacity(varying.len());
147            for (key, arg) in varying {
148                read.push((*key, named(*arg)?));
149            }
150            return Ok(solver(params, &read));
151        }
152        Value::Filter {
153            shape,
154            x,
155            cutoff,
156            q,
157            gain,
158        } => {
159            sink.text(crate::vocabulary::shape_name(*shape));
160            for operand in [x, cutoff, q, gain] {
161                sink.hash(named(*operand)?);
162            }
163        }
164        Value::Op { name, args } => {
165            sink.text(name);
166            let mut held = Vec::with_capacity(args.len());
167            for arg in args {
168                held.push(named(*arg)?);
169            }
170            if matches!(name.as_str(), "+" | "*") {
171                sva_formula::either_order(&mut held);
172            }
173            held.into_iter().for_each(|h| sink.hash(h));
174        }
175    }
176    Ok(sink.finish())
177}
178
179/// The node `node` only passes on, read at its own instant and grid: that value itself.
180pub(crate) fn passes(typing: &Typing, node: NodeId) -> Option<NodeId> {
181    if typing.sum_slots(node).is_some() {
182        return None;
183    }
184    match typing.value(node) {
185        Value::Read {
186            source,
187            at: When::At(time),
188            ..
189        } if *time == crate::time::Affine::NOW && typing.grid(*source) == typing.grid(node) => {
190            Some(*source)
191        }
192        Value::ClosedForm(form) => match &form.body {
193            Body::Node(read) if typing.var(*read) == form.var => Some(*read),
194            _ => None,
195        },
196        _ => None,
197    }
198}
199
200/// A moving time is named by its closed form, which holds no ref back to the reader.
201pub(super) fn when(
202    sink: &mut ContentHasher,
203    typing: &Typing,
204    at: &When,
205) -> Result<(), EngineError> {
206    sink.text("at");
207    match at {
208        When::At(time) => {
209            sink.text("time");
210            affine(sink, *time);
211        }
212        When::Moving(id) => sink.hash(identity(typing, *id)?),
213        When::Index(index) => exact(sink, *index),
214        When::Step(step) => {
215            sink.text("step");
216            stepped(sink, typing, step)?;
217        }
218    }
219    Ok(())
220}
221
222fn exact(sink: &mut ContentHasher, index: crate::index::Index) {
223    round(sink, "index", index.round);
224    match index.time {
225        Some(time) => affine(sink, time),
226        None => sink.text("count"),
227    }
228    sink.word(index.plus as u64);
229}
230
231fn stepped(sink: &mut ContentHasher, typing: &Typing, step: &Step) -> Result<(), EngineError> {
232    let each = |sink: &mut ContentHasher, what: &str, parts: &[Step]| {
233        sink.text(what);
234        sink.word(parts.len() as u64);
235        parts.iter().try_for_each(|p| stepped(sink, typing, p))
236    };
237    match step {
238        Step::Index(index) => exact(sink, *index),
239        Step::Nearest(time, how) => {
240            round(sink, "nearest", *how);
241            sink.hash(identity(typing, *time)?);
242        }
243        Step::Add(parts) => each(sink, "sum", parts)?,
244        Step::Mul(parts) => each(sink, "product", parts)?,
245        Step::Neg(part) => {
246            sink.text("negated");
247            stepped(sink, typing, part)?;
248        }
249    }
250    Ok(())
251}
252
253fn round(sink: &mut ContentHasher, what: &str, round: Round) {
254    let how = match round {
255        Round::Even => "",
256        Round::Floor => " floor",
257        Round::Ceil => " ceil",
258    };
259    sink.text(&format!("{what}{how}"));
260}
261
262fn affine(sink: &mut ContentHasher, time: crate::time::Affine) {
263    for q in [time.scale, time.shift] {
264        rational(sink, q);
265    }
266}
267
268/// Both words of each side: a denominator reaches past 64 bits.
269fn rational(sink: &mut ContentHasher, q: crate::time::Q) {
270    for side in [q.num(), q.den()] {
271        sink.word(side as u64);
272        sink.word((side >> 64) as u64);
273    }
274}
275
276fn node_identity_hasher() -> ContentHasher {
277    ContentHasher::new(HashDomain::NodeIdentity)
278}
279
280#[cfg(test)]
281mod tests {
282    use super::{node_identity_hasher, rational};
283    use crate::time::Q;
284
285    fn named(q: Q) -> sva_formula::Hash {
286        let mut sink = node_identity_hasher();
287        rational(&mut sink, q);
288        sink.finish()
289    }
290
291    /// Two denominators alike in their low 64 bits name two rationals.
292    #[test]
293    fn a_rational_is_named_by_its_whole_denominator() {
294        let low = (1_i128 << 64) + 3;
295        let a = Q::new(1, 3).expect("a rational");
296        let b = Q::new(1, low).expect("a rational");
297        assert_ne!(named(a), named(b));
298    }
299}
sva_engine/refs/identity.rs

sva_engine/refs/
identity.rs
