sva_formula/
through.rs

1// Concern: reads each ref of a written form as the form it names, each answer kept per node | Non-concern: which refs a caller lets it read (sva-engine) | IO: (NodeId) -> each reading of its form
2
3use std::cell::{Cell, RefCell};
4use std::collections::HashMap;
5use std::ops::Deref;
6use std::rc::Rc;
7
8use crate::affine::{Axis, Coeff, Reading, key_moves_read, polynomial_read};
9use crate::closed_form::{Body, IndexId, Var, map_children, read_at, read_at_with, shift_line};
10use crate::env::NodeId;
11use crate::hash::{Hash, hash_time};
12use crate::origin::Origin;
13use crate::refusal::{Factor, Left, LeftReason};
14use crate::series::IndexGrowth;
15use crate::spectral_sum::SpectralSum;
16use crate::spectral_sum::build::{lower, timeless};
17use crate::spectral_sum::image::left;
18use crate::spectral_sum::kink;
19pub use crate::spectral_sum::kink::{Crossing, Line};
20
21/// What a ref in a written form answers each reading of it with, as the form it names would.
22pub trait Reads {
23    fn lowered(&self, id: NodeId, origin: Origin, var: Var) -> Result<SpectralSum, Left>;
24    fn polynomial(&self, id: NodeId, reading: Reading) -> Option<Vec<Coeff>>;
25    fn timeless(&self, id: NodeId) -> bool;
26    fn key_moves(&self, id: NodeId) -> bool;
27    fn mentions_line(&self, id: NodeId) -> bool;
28    fn axis(&self, id: NodeId) -> Option<Axis>;
29    fn line(&self, id: NodeId) -> Option<Line>;
30    fn kink(&self, id: NodeId) -> Option<(Body, Crossing)>;
31    /// A node standing for `id` with `kink` read as `with` throughout, where it reaches one.
32    fn replaced(&self, id: NodeId, scope: usize, kink: &Body, with: &Body) -> Option<NodeId>;
33    /// A node standing for `id` read at `at`, the time written through its form.
34    fn moved(&self, id: NodeId, at: &Body) -> Option<NodeId>;
35    fn stand_for(&self, body: Body) -> Option<NodeId>;
36    fn scope(&self) -> usize;
37    /// The form `id` names as `read` reads it, one level down: its own refs still refs.
38    fn view(&self, id: NodeId, read: &Read) -> Option<Form<'_>>;
39    /// How the form `id` names grows in `k`, read at a time `k` moves.
40    fn growth(&self, id: NodeId, at: &Body, k: IndexId) -> Option<IndexGrowth>;
41}
42
43/// How a ref is read where it stands: as written, at a time, or shifted.
44pub enum Read<'t> {
45    As,
46    At(&'t Body),
47    By(f64),
48}
49
50/// A ref read as nothing but itself: a name whose form is unknown here.
51pub struct Opaque;
52
53impl Reads for Opaque {
54    fn lowered(&self, _: NodeId, origin: Origin, _: Var) -> Result<SpectralSum, Left> {
55        Err(left(origin, Factor::Value, LeftReason::Unsubstituted))
56    }
57
58    fn polynomial(&self, _: NodeId, _: Reading) -> Option<Vec<Coeff>> {
59        None
60    }
61
62    fn timeless(&self, _: NodeId) -> bool {
63        false
64    }
65
66    fn key_moves(&self, _: NodeId) -> bool {
67        true
68    }
69
70    fn mentions_line(&self, _: NodeId) -> bool {
71        false
72    }
73
74    fn axis(&self, _: NodeId) -> Option<Axis> {
75        None
76    }
77
78    fn line(&self, _: NodeId) -> Option<Line> {
79        None
80    }
81
82    fn kink(&self, _: NodeId) -> Option<(Body, Crossing)> {
83        None
84    }
85
86    fn replaced(&self, _: NodeId, _: usize, _: &Body, _: &Body) -> Option<NodeId> {
87        None
88    }
89
90    fn moved(&self, _: NodeId, _: &Body) -> Option<NodeId> {
91        None
92    }
93
94    fn stand_for(&self, _: Body) -> Option<NodeId> {
95        None
96    }
97
98    fn scope(&self) -> usize {
99        0
100    }
101
102    fn view(&self, _: NodeId, _: &Read) -> Option<Form<'_>> {
103        None
104    }
105
106    fn growth(&self, _: NodeId, _: &Body, _: IndexId) -> Option<IndexGrowth> {
107        None
108    }
109}
110
111/// Each reading of each node, kept by whoever holds the nodes for as long as they hold.
112#[derive(Debug, Default)]
113pub struct Kept {
114    lowered: Each<(NodeId, Var), Result<SpectralSum, Left>>,
115    polynomials: Each<(NodeId, Reading), Option<Vec<Coeff>>>,
116    timeless: Each<NodeId, bool>,
117    key_moves: Each<NodeId, bool>,
118    mentions_line: Each<NodeId, bool>,
119    axes: Each<NodeId, Axis>,
120    lines: Each<NodeId, Option<Line>>,
121    kinks: Each<NodeId, Option<(Body, Crossing)>>,
122    views: Each<(NodeId, View), Rc<Body>>,
123    growths: Each<(NodeId, IndexId, Hash), IndexGrowth>,
124}
125
126type Each<K, V> = RefCell<HashMap<K, V>>;
127
128/// Which rewritten reading of a form a view is.
129#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
130enum View {
131    At(Hash),
132    By(u64),
133}
134
135impl Kept {
136    /// Every answer it holds, moved out: this one answers anew.
137    pub fn parted(&self) -> Kept {
138        Kept {
139            lowered: RefCell::new(self.lowered.take()),
140            polynomials: RefCell::new(self.polynomials.take()),
141            timeless: RefCell::new(self.timeless.take()),
142            key_moves: RefCell::new(self.key_moves.take()),
143            mentions_line: RefCell::new(self.mentions_line.take()),
144            axes: RefCell::new(self.axes.take()),
145            lines: RefCell::new(self.lines.take()),
146            kinks: RefCell::new(self.kinks.take()),
147            views: RefCell::new(self.views.take()),
148            growths: RefCell::new(self.growths.take()),
149        }
150    }
151
152    /// Every answer about a node `gone` names let go; the rest kept.
153    pub fn forget(&mut self, gone: &dyn Fn(NodeId) -> bool) {
154        self.lowered.get_mut().retain(|(id, _), _| !gone(*id));
155        self.polynomials.get_mut().retain(|(id, _), _| !gone(*id));
156        self.timeless.get_mut().retain(|id, _| !gone(*id));
157        self.key_moves.get_mut().retain(|id, _| !gone(*id));
158        self.mentions_line.get_mut().retain(|id, _| !gone(*id));
159        self.axes.get_mut().retain(|id, _| !gone(*id));
160        self.lines.get_mut().retain(|id, _| !gone(*id));
161        self.kinks.get_mut().retain(|id, _| !gone(*id));
162        self.views.get_mut().retain(|(id, _), _| !gone(*id));
163        self.growths.get_mut().retain(|(id, _, _), _| !gone(*id));
164    }
165}
166
167/// The written form each node names, `None` where the caller reads no form through it.
168pub type Written<'a> = &'a dyn Fn(NodeId) -> Option<(&'a Body, Origin)>;
169
170/// Reads refs through `written`, keeping each node's answers in `kept`. A form rewritten
171/// below a ref stands in as a node of its own, numbered from the top of the ids down, kept
172/// only while this reading lasts.
173pub struct Through<'a> {
174    written: Written<'a>,
175    kept: &'a Kept,
176    standing: Kept,
177    stand_ins: RefCell<Vec<Rc<Body>>>,
178    replacing: RefCell<HashMap<(NodeId, usize), Option<NodeId>>>,
179    moving: Each<NodeId, Vec<(Body, Option<NodeId>)>>,
180    scopes: Cell<usize>,
181}
182
183/// A form a reader hands out: one a node names, or one standing in for a rewritten form.
184pub enum Form<'a> {
185    Node(&'a Body),
186    Stand(Rc<Body>),
187}
188
189impl Deref for Form<'_> {
190    type Target = Body;
191
192    fn deref(&self) -> &Body {
193        match self {
194            Form::Node(body) => body,
195            Form::Stand(body) => body,
196        }
197    }
198}
199
200impl<'a> Through<'a> {
201    pub fn new(written: Written<'a>, kept: &'a Kept) -> Through<'a> {
202        Through {
203            written,
204            kept,
205            standing: Kept::default(),
206            stand_ins: RefCell::default(),
207            replacing: RefCell::default(),
208            moving: RefCell::default(),
209            scopes: Cell::new(0),
210        }
211    }
212
213    fn stand_in(id: NodeId) -> Option<usize> {
214        let at = u32::MAX - id.0;
215        (at < u32::MAX / 2).then_some(at as usize)
216    }
217
218    fn form(&self, id: NodeId) -> Option<(Form<'a>, Origin)> {
219        match Through::stand_in(id) {
220            Some(at) => {
221                let body = Rc::clone(self.stand_ins.borrow().get(at)?);
222                Some((Form::Stand(body), Origin::UNKNOWN))
223            }
224            None => (self.written)(id).map(|(body, origin)| (Form::Node(body), origin)),
225        }
226    }
227
228    fn kept(&self, id: NodeId) -> &Kept {
229        match Through::stand_in(id) {
230            Some(_) => &self.standing,
231            None => self.kept,
232        }
233    }
234
235    /// A node of its own standing for `body`, read through like any other.
236    pub fn stand(&self, body: Body) -> NodeId {
237        let mut held = self.stand_ins.borrow_mut();
238        held.push(Rc::new(body));
239        NodeId(u32::MAX - (held.len() - 1) as u32)
240    }
241
242    /// `with` handed the written form `id` names, where it names one.
243    pub fn read<R>(&self, id: NodeId, with: impl FnOnce(&Body) -> R) -> Option<R> {
244        self.form(id).map(|(form, _)| with(&form))
245    }
246
247    pub fn stands(id: NodeId) -> bool {
248        Through::stand_in(id).is_some()
249    }
250}
251
252fn once<K: std::hash::Hash + Eq, V: Clone>(
253    table: &Each<K, V>,
254    key: K,
255    of: impl FnOnce() -> V,
256) -> V {
257    if let Some(held) = table.borrow().get(&key) {
258        return held.clone();
259    }
260    let found = of();
261    table.borrow_mut().insert(key, found.clone());
262    found
263}
264
265impl Reads for Through<'_> {
266    fn lowered(&self, id: NodeId, origin: Origin, var: Var) -> Result<SpectralSum, Left> {
267        let Some((form, own)) = self.form(id) else {
268            return Opaque.lowered(id, origin, var);
269        };
270        once(&self.kept(id).lowered, (id, var), || {
271            lower(&form, own, var, self)
272        })
273    }
274
275    fn polynomial(&self, id: NodeId, reading: Reading) -> Option<Vec<Coeff>> {
276        let (form, _) = self.form(id)?;
277        once(&self.kept(id).polynomials, (id, reading), || {
278            polynomial_read(&form, reading, self)
279        })
280    }
281
282    fn timeless(&self, id: NodeId) -> bool {
283        let Some((form, _)) = self.form(id) else {
284            return Opaque.timeless(id);
285        };
286        once(&self.kept(id).timeless, id, || timeless(&form, self))
287    }
288
289    fn key_moves(&self, id: NodeId) -> bool {
290        let Some((form, _)) = self.form(id) else {
291            return Opaque.key_moves(id);
292        };
293        once(&self.kept(id).key_moves, id, || key_moves_read(&form, self))
294    }
295
296    fn mentions_line(&self, id: NodeId) -> bool {
297        let Some((form, _)) = self.form(id) else {
298            return Opaque.mentions_line(id);
299        };
300        once(&self.kept(id).mentions_line, id, || {
301            crate::series::mentions_line_read(&form, self)
302        })
303    }
304
305    fn axis(&self, id: NodeId) -> Option<Axis> {
306        let (form, _) = self.form(id)?;
307        Some(once(&self.kept(id).axes, id, || {
308            crate::affine::axis_read(&form, &Within(self), self)
309        }))
310    }
311
312    fn line(&self, id: NodeId) -> Option<Line> {
313        let (form, _) = self.form(id)?;
314        once(&self.kept(id).lines, id, || kink::line(&form, self))
315    }
316
317    fn kink(&self, id: NodeId) -> Option<(Body, Crossing)> {
318        let (form, _) = self.form(id)?;
319        once(&self.kept(id).kinks, id, || kink::first(&form, self))
320    }
321
322    fn replaced(&self, id: NodeId, scope: usize, kink: &Body, with: &Body) -> Option<NodeId> {
323        let (form, _) = self.form(id)?;
324        if let Some(held) = self.replacing.borrow().get(&(id, scope)) {
325            return *held;
326        }
327        let rewritten = match &*form == kink {
328            true => Some(with.clone()),
329            false => kink::in_time(&form)
330                .then(|| map_children(&form, |p| kink::replaced_part(p, (scope, kink, with), self)))
331                .filter(|body| body != &*form),
332        };
333        let stand = rewritten.map(|body| self.stand(body));
334        self.replacing.borrow_mut().insert((id, scope), stand);
335        stand
336    }
337
338    fn moved(&self, id: NodeId, at: &Body) -> Option<NodeId> {
339        let held = self.moving.borrow().get(&id).and_then(|read| {
340            read.iter()
341                .find_map(|(time, stand)| (time == at).then_some(*stand))
342        });
343        if let Some(held) = held {
344            return held;
345        }
346        let (form, _) = self.form(id)?;
347        let moved = read_at_with(&form, at, &|node| self.moved(node, at));
348        let stand = Some(self.stand(moved));
349        let mut moving = self.moving.borrow_mut();
350        moving.entry(id).or_default().push((at.clone(), stand));
351        stand
352    }
353
354    fn stand_for(&self, body: Body) -> Option<NodeId> {
355        Some(self.stand(body))
356    }
357
358    fn scope(&self) -> usize {
359        self.scopes.set(self.scopes.get() + 1);
360        self.scopes.get()
361    }
362
363    fn view(&self, id: NodeId, read: &Read) -> Option<Form<'_>> {
364        let (form, _) = self.form(id)?;
365        let key = match read {
366            Read::As => return Some(form),
367            Read::At(at) => View::At(hash_time(at)),
368            Read::By(by) => View::By(by.to_bits()),
369        };
370        let views = &self.kept(id).views;
371        if let Some(held) = views.borrow().get(&(id, key)) {
372            return Some(Form::Stand(Rc::clone(held)));
373        }
374        let seen = Rc::new(match read {
375            Read::As => unreachable!("a form read as written is handed out as it stands"),
376            Read::At(at) => read_at(&form, at),
377            Read::By(by) => shift_line(&form, *by),
378        });
379        views.borrow_mut().insert((id, key), Rc::clone(&seen));
380        Some(Form::Stand(seen))
381    }
382
383    fn growth(&self, id: NodeId, at: &Body, k: IndexId) -> Option<IndexGrowth> {
384        let (form, _) = self.form(id)?;
385        Some(once(&self.kept(id).growths, (id, k, hash_time(at)), || {
386            crate::series::growth(&read_at(&form, at), k, &Within(self))
387        }))
388    }
389}
390
391/// Types nothing a reader reads through: a ref sits where its form does, and no parameter
392/// reaches a form read through.
393struct Within<'r>(&'r dyn Reads);
394
395impl crate::env::Env for Within<'_> {
396    fn node(&self, _: NodeId) -> crate::ty::Ty {
397        crate::ty::Ty::form(Var::T, false, crate::ty::Codomain::Complex)
398    }
399
400    fn param(&self, _: crate::env::ParamId) -> crate::ty::Ty {
401        crate::ty::Ty::form(Var::T, false, crate::ty::Codomain::Complex)
402    }
403
404    fn reads(&self) -> &dyn Reads {
405        self.0
406    }
407}
408
409/// `f` as a reader of its shape sees it: a ref is the form it names, each level kept per node
410/// and time as the reader walks into it.
411pub fn looked<'b>(f: &'b Body, reads: &'b dyn Reads) -> Seen<'b> {
412    let mut seen = Seen::Here(f);
413    loop {
414        let read = match &*seen {
415            Body::Node(id) => Some((*id, Read::As)),
416            Body::Warp { at, of } => match &*of.body {
417                Body::Node(id) => Some((*id, Read::At(&at.body))),
418                _ => None,
419            },
420            Body::Shift { by, of } => match &*of.body {
421                Body::Node(id) => Some((*id, Read::By(*by))),
422                _ => None,
423            },
424            _ => None,
425        };
426        let Some(form) = read.and_then(|(id, read)| reads.view(id, &read)) else {
427            return seen;
428        };
429        seen = Seen::Form(form);
430    }
431}
432
433/// A body as a reader sees it: written where it stands, or the form a ref there names.
434pub enum Seen<'b> {
435    Here(&'b Body),
436    Form(Form<'b>),
437}
438
439impl Deref for Seen<'_> {
440    type Target = Body;
441
442    fn deref(&self) -> &Body {
443        match self {
444            Seen::Here(body) => body,
445            Seen::Form(form) => form,
446        }
447    }
448}
sva_formula/through.rs

sva_formula/
through.rs
