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

sva_engine/refs/
identity.rs
