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::Solver { params, varying } => {
137            let mut read = Vec::with_capacity(varying.len());
138            for (key, arg) in varying {
139                read.push((*key, named(*arg)?));
140            }
141            return Ok(solver(params, &read));
142        }
143        Value::Filter {
144            shape,
145            x,
146            cutoff,
147            q,
148            gain,
149        } => {
150            sink.text(crate::vocabulary::shape_name(*shape));
151            for operand in [x, cutoff, q, gain] {
152                sink.hash(named(*operand)?);
153            }
154        }
155        Value::Op { name, args } => {
156            sink.text(name);
157            let mut held = Vec::with_capacity(args.len());
158            for arg in args {
159                held.push(named(*arg)?);
160            }
161            if matches!(name.as_str(), "+" | "*") {
162                sva_formula::either_order(&mut held);
163            }
164            held.into_iter().for_each(|h| sink.hash(h));
165        }
166    }
167    Ok(sink.finish())
168}
169
170/// The node `node` only passes on, read at its own instant and grid: that value itself.
171pub(crate) fn passes(typing: &Typing, node: NodeId) -> Option<NodeId> {
172    if typing.sum_slots(node).is_some() {
173        return None;
174    }
175    match typing.value(node) {
176        Value::Read {
177            source,
178            at: When::At(time),
179            ..
180        } if *time == crate::time::Affine::NOW && typing.grid(*source) == typing.grid(node) => {
181            Some(*source)
182        }
183        Value::ClosedForm(form) => match &form.body {
184            Body::Node(read) if typing.var(*read) == form.var => Some(*read),
185            _ => None,
186        },
187        _ => None,
188    }
189}
190
191/// A moving time is named by its closed form, which holds no ref back to the reader.
192pub(super) fn when(
193    sink: &mut ContentHasher,
194    typing: &Typing,
195    at: &When,
196) -> Result<(), EngineError> {
197    sink.text("at");
198    match at {
199        When::At(time) => {
200            sink.text("time");
201            affine(sink, *time);
202        }
203        When::Moving(id) => sink.hash(identity(typing, *id)?),
204        When::Index(index) => exact(sink, *index),
205        When::Step(step) => {
206            sink.text("step");
207            stepped(sink, typing, step)?;
208        }
209    }
210    Ok(())
211}
212
213fn exact(sink: &mut ContentHasher, index: crate::index::Index) {
214    round(sink, "index", index.round);
215    match index.time {
216        Some(time) => affine(sink, time),
217        None => sink.text("count"),
218    }
219    sink.word(index.plus as u64);
220}
221
222fn stepped(sink: &mut ContentHasher, typing: &Typing, step: &Step) -> Result<(), EngineError> {
223    let each = |sink: &mut ContentHasher, what: &str, parts: &[Step]| {
224        sink.text(what);
225        sink.word(parts.len() as u64);
226        parts.iter().try_for_each(|p| stepped(sink, typing, p))
227    };
228    match step {
229        Step::Index(index) => exact(sink, *index),
230        Step::Nearest(time, how) => {
231            round(sink, "nearest", *how);
232            sink.hash(identity(typing, *time)?);
233        }
234        Step::Add(parts) => each(sink, "sum", parts)?,
235        Step::Mul(parts) => each(sink, "product", parts)?,
236        Step::Neg(part) => {
237            sink.text("negated");
238            stepped(sink, typing, part)?;
239        }
240    }
241    Ok(())
242}
243
244fn round(sink: &mut ContentHasher, what: &str, round: Round) {
245    let how = match round {
246        Round::Even => "",
247        Round::Floor => " floor",
248        Round::Ceil => " ceil",
249    };
250    sink.text(&format!("{what}{how}"));
251}
252
253fn affine(sink: &mut ContentHasher, time: crate::time::Affine) {
254    for q in [time.scale, time.shift] {
255        rational(sink, q);
256    }
257}
258
259/// Both words of each side: a denominator reaches past 64 bits.
260fn rational(sink: &mut ContentHasher, q: crate::time::Q) {
261    for side in [q.num(), q.den()] {
262        sink.word(side as u64);
263        sink.word((side >> 64) as u64);
264    }
265}
266
267fn node_identity_hasher() -> ContentHasher {
268    ContentHasher::new(HashDomain::NodeIdentity)
269}
270
271#[cfg(test)]
272mod tests {
273    use super::{node_identity_hasher, rational};
274    use crate::time::Q;
275
276    fn named(q: Q) -> sva_formula::Hash {
277        let mut sink = node_identity_hasher();
278        rational(&mut sink, q);
279        sink.finish()
280    }
281
282    /// Two denominators alike in their low 64 bits name two rationals.
283    #[test]
284    fn a_rational_is_named_by_its_whole_denominator() {
285        let low = (1_i128 << 64) + 3;
286        let a = Q::new(1, 3).expect("a rational");
287        let b = Q::new(1, low).expect("a rational");
288        assert_ne!(named(a), named(b));
289    }
290}
sva_engine/refs/identity.rs

sva_engine/refs/
identity.rs
