feather_ui/
persist.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: 2025 Fundament Research Institute <https://fundament.institute>
3
4use derive_where::derive_where;
5use std::default::Default;
6use std::marker::PhantomData;
7
8pub struct Persist<Args, Output, T: FnMut(&Args) -> Output>(
9    pub T,
10    pub PhantomData<Args>,
11    pub PhantomData<Output>,
12);
13
14impl<Arg1, Output, T: FnMut(&Arg1) -> Output> Persist<Arg1, Output, T> {
15    pub fn new(t: T) -> Self {
16        Self(t, PhantomData, PhantomData)
17    }
18}
19
20pub struct Persist2<Arg1, Arg2, Output, T: FnMut(Arg1, Arg2) -> Output>(
21    pub T,
22    pub PhantomData<Arg1>,
23    pub PhantomData<Arg2>,
24    pub PhantomData<Output>,
25);
26
27impl<Arg1, Arg2, Output, T: FnMut(Arg1, Arg2) -> Output> Persist2<Arg1, Arg2, Output, T> {
28    pub fn new(t: T) -> Self {
29        Self(t, PhantomData, PhantomData, PhantomData)
30    }
31}
32
33/// This represents the storage of a persistent function. This trait is shared
34/// between all [`FnPersist`] traits for each distinct number of arguments. The
35/// storage type must satisfy [`Clone`] and should ideally be built using
36/// persistent data structures. In order to allow a persistent function to work
37/// correctly, Store should have space to store both the *input arguments* and
38/// the *output result* of a persistent function. This is essential to allowing
39/// a persistent function to detect that it's arguments are the same
40/// as the previous invocation and return the previous output without any
41/// additional computation.
42///
43/// # Examples
44///
45/// ```
46/// use feather_ui::persist::{FnPersist, FnPersistStore};
47///
48/// #[derive(Clone)]
49/// struct MyStore {
50///     arg: i32,
51///     result: i32,
52/// }
53///
54/// struct MyPersistFn {
55///     ratio: i32,
56/// }
57///
58/// impl FnPersistStore for MyPersistFn {
59///     type Store = MyStore;
60/// }
61///
62/// impl FnPersist<i32, i32> for MyPersistFn {
63///     // Return a version of Self::Store that is either illegal or extremely unlikely to be called.
64///     fn init(&self) -> Self::Store { Self::Store{ arg: i32::MIN, result: i32::MIN } }
65///
66///     fn call(&mut self, mut store: Self::Store, arg: &i32) -> (Self::Store, i32) {
67///         if *arg != store.arg {
68///             store.result = *arg * self.ratio;
69///         }
70///         
71///         let result = store.result;
72///         (store, result)
73///     }
74/// }
75/// ```
76pub trait FnPersistStore {
77    type Store: Clone;
78}
79
80/// This represents a persistent function that takes one argument. This includes
81/// the main Feather outline function and the [`MapPersist`] operation. A
82/// persistent function stores it's own previous internal state and output,
83/// which allows it to return it's previous output if the arguments match. This
84/// essentially `memoizes` the function with an LRU of size 1, meaning it will
85/// only memoize if the current function call is exactly the same as the
86/// previous call. These functions harmonize nicely with persistent data
87/// structures that allow these comparisons to be done quickly.
88///
89/// Unfortunately, Rust [does not allow implementing Fn traits](https://github.com/rust-lang/rust/issues/29625), so
90/// this implementation is a bit annoying to use. [`FnPersist::init`] is called
91/// when Self::Store doesn't exist, and is meant to return a minimal empty store
92/// state that won't ever conflict with a real result from calling the function.
93/// [`FnPersist::call`] then represents calling the persistent function with
94/// both it's additional storage parameter and both arguments. It must then
95/// return both the `Output` of evaluating the function, and the new storage
96/// object. Note that the storage object is constrained by [`FnPersistStore`].
97///
98/// **IMPORTANT:** Due to missing features in the [`im`] crate, Feather
99/// currently cannot properly support all the intended features of persistent
100/// functions. As a result, many operations such as `VectorFold` are not
101/// actually persistent or optimized correctly. This will be [addressed in a future update](https://github.com/Fundament-Institute/feather-ui/issues/124).
102///
103/// # Examples
104///
105/// See [`FnPersistStore`]
106pub trait FnPersist<Args, Output>: FnPersistStore {
107    fn init(&self) -> Self::Store;
108    fn call(&mut self, store: Self::Store, args: &Args) -> (Self::Store, Output);
109}
110
111impl<Args, Output, T: FnMut(&Args) -> Output> FnPersist<Args, Output> for Persist<Args, Output, T> {
112    fn init(&self) -> Self::Store {}
113    fn call(&mut self, _: Self::Store, args: &Args) -> (Self::Store, Output) {
114        ((), (self.0)(args))
115    }
116}
117
118impl<Args, Output, T: FnMut(&Args) -> Output> FnPersistStore for Persist<Args, Output, T> {
119    type Store = ();
120}
121
122/// This represents a persistent function that takes 2 arguments. This includes
123/// the main Feather outline function and the [`FoldPersist`] operation. A
124/// persistent function stores it's own previous internal state and output,
125/// which allows it to return it's previous output if the arguments match. This
126/// essentially `memoizes` the function with an LRU of size 1, meaning it will
127/// only memoize if the current function call is exactly the same as the
128/// previous call. These functions harmonize nicely with persistent data
129/// structures that allow these comparisons to be done quickly.
130///
131/// Unfortunately, Rust [does not allow implementing Fn traits](https://github.com/rust-lang/rust/issues/29625), so
132/// this implementation is a bit annoying to use. [`FnPersist2::init`] is called
133/// when Self::Store doesn't exist, and is meant to return a minimal empty store
134/// state that won't ever conflict with a real result from calling the function.
135/// [`FnPersist2::call`] then represents calling the persistent function with
136/// both it's additional storage parameter and both arguments. It must then
137/// return both the `Output` of evaluating the function, and the new storage
138/// object. Note that the storage object is constrained by [`FnPersistStore`].
139///
140/// **IMPORTANT:** Due to missing features in the [`im`] crate, Feather
141/// currently cannot properly support all the intended features of persistent
142/// functions. As a result, many operations such as `VectorFold` are not
143/// actually persistent or optimized correctly. This will be [addressed in a future update](https://github.com/Fundament-Institute/feather-ui/issues/124).
144///
145/// # Examples
146///
147/// See [`FnPersistStore`]
148pub trait FnPersist2<Arg1, Arg2, Output>: FnPersistStore {
149    fn init(&self) -> Self::Store;
150    fn call(&mut self, store: Self::Store, arg1: Arg1, arg2: Arg2) -> (Self::Store, Output);
151}
152
153impl<Arg1, Arg2, Output, T: FnMut(Arg1, Arg2) -> Output> FnPersist2<Arg1, Arg2, Output>
154    for Persist2<Arg1, Arg2, Output, T>
155{
156    fn init(&self) -> Self::Store {}
157    fn call(&mut self, _: Self::Store, arg1: Arg1, arg2: Arg2) -> (Self::Store, Output) {
158        ((), (self.0)(arg1, arg2))
159    }
160}
161
162impl<Arg1, Arg2, Output, T: FnMut(Arg1, Arg2) -> Output> FnPersistStore
163    for Persist2<Arg1, Arg2, Output, T>
164{
165    type Store = ();
166}
167
168pub trait MapPersist<T, U> {
169    type C<A>;
170
171    fn map<F: FnPersist<T, U>>(f: F) -> impl FnPersist<Self::C<T>, Self::C<U>>;
172}
173
174pub trait FoldPersist<'a, T: 'a, U> {
175    type C<A>: 'a
176    where
177        A: 'a;
178
179    fn fold<F: FnPersist2<U, &'a T, U>>(f: F) -> impl FnPersist2<U, &'a Self::C<T>, U>;
180}
181
182/*pub fn vector_map<T, U: Clone, F: FnPersist<T, U>>(
183    cache: (im::Vector<T>, im::Vector<F::Store>, im::Vector<U>),
184    input: im::Vector<T>,
185    f: F,
186) -> (im::Vector<T>, im::Vector<F::Store>, im::Vector<U>)
187where
188    F::Store: Clone,
189{
190    let internal = cache.1.clone();
191    let output = cache.2.clone();
192    // Get the difference between the items passed in and the cache of what we passed in last
193    for item in cache.0.diff(&input) {
194        match item {
195            DoesNotExist::Insert(i, x) => {
196                let (store, result) = f.call(Default::default(), *x);
197                internal.insert(i, store);
198                output.insert(i, result);
199            }
200            DoesNotExist::Update(i, old, new) => {
201                let (store, result) = f.call(*cache.1.get(i).unwrap(), *new);
202                internal.set(i, store);
203                output.set(i, result);
204            }
205            DoesNotExist::Remove(i, _) => {
206                internal.remove(i);
207                output.remove(i);
208            }
209        }
210    }
211
212    (input, internal, output)
213}
214
215// Special case where the applying function has no state and can therefore be a lambda
216pub fn vector_map_lamba<T, U: Clone, F: Fn(T) -> U>(
217    cache: (im::Vector<T>, im::Vector<U>),
218    input: im::Vector<T>,
219    f: F,
220) -> (im::Vector<T>, im::Vector<U>)
221where
222    F::Store: Clone,
223{
224    let output = cache.2.clone();
225    // Get the difference between the items passed in and the cache of what we passed in last
226    for item in cache.0.diff(&input) {
227        match item {
228            DoesNotExist::Insert(i, x) => {
229                let (store, result) = f.call(Default::default(), *x);
230                output.insert(i, result);
231            }
232            DoesNotExist::Update(i, old, new) => {
233                let (store, result) = f.call(*cache.1.get(i).unwrap(), *new);
234                output.set(i, result);
235            }
236            DoesNotExist::Remove(i, _) => {
237                output.remove(i);
238            }
239        }
240    }
241
242    (input, internal, output)
243}
244
245pub fn vector_fold<T, U: Clone, F: FnPersist<(T, T), U>>(
246    cache: (im::Vector<T>, im::Vector<F::Store>, U),
247    input: im::Vector<T>,
248    f: F,
249    init: T,
250) -> (im::Vector<T>, im::Vector<F::Store>, U)
251where
252    F::Store: Clone,
253{
254    // From our diff, we figure out the start point, and then fold from there
255}*/
256
257#[derive_where(Clone, Default)]
258pub struct ConcatStore<T: Clone>(im::Vector<T>, im::Vector<T>, im::Vector<T>);
259pub struct Concat<T> {
260    _phantom: PhantomData<T>,
261}
262
263impl<T: Clone> FnPersistStore for Concat<T> {
264    type Store = ConcatStore<T>;
265}
266
267impl<T: Clone> FnPersist<(im::Vector<T>, im::Vector<T>), im::Vector<T>> for Concat<T> {
268    fn init(&self) -> Self::Store {
269        Default::default()
270    }
271    fn call(
272        &mut self,
273        mut store: Self::Store,
274        args: &(im::Vector<T>, im::Vector<T>),
275    ) -> (Self::Store, im::Vector<T>) {
276        // TODO: we need pointer only vector equality checks
277        //if store.0 != args.0 || store.1 != args.1 {
278        store.0 = args.0.clone();
279        store.1 = args.1.clone();
280        store.2 = args.0.clone();
281        store.2.append(store.1.clone());
282        //}
283        let r = store.2.clone();
284        (store, r)
285    }
286}
287
288#[derive_where(Clone, Default)]
289pub struct OrdSetMapStore<T: Clone, U: Clone, F: FnPersist<T, U>> {
290    arg: im::OrdSet<T>,
291    result: im::OrdSet<U>,
292    store: im::OrdMap<T, F::Store>,
293}
294
295pub struct OrdSetMap<T, U, F: FnPersist<T, U>> {
296    f: F,
297    phantom_t: PhantomData<T>,
298    phantom_u: PhantomData<U>,
299}
300
301impl<T: Ord + Clone, U: Ord + Clone, F: FnPersist<T, U>> OrdSetMap<T, U, F> {
302    pub fn new(f: F) -> Self {
303        Self {
304            f,
305            phantom_t: PhantomData,
306            phantom_u: PhantomData,
307        }
308    }
309}
310
311impl<T: Ord + Clone, U: Ord + Clone, F: FnPersist<T, U>> From<F> for OrdSetMap<T, U, F> {
312    fn from(f: F) -> Self {
313        Self::new(f)
314    }
315}
316
317impl<T: Clone, U: Clone, F: FnPersist<T, U>> FnPersistStore for OrdSetMap<T, U, F> {
318    type Store = OrdSetMapStore<T, U, F>;
319}
320
321impl<T: Ord + Clone, U: Ord + Clone, F: FnPersist<T, U>> FnPersist<im::OrdSet<T>, im::OrdSet<U>>
322    for OrdSetMap<T, U, F>
323{
324    fn init(&self) -> Self::Store {
325        Default::default()
326    }
327    fn call(&mut self, cache: Self::Store, input: &im::OrdSet<T>) -> (Self::Store, im::OrdSet<U>) {
328        let mut internal = cache.store.clone();
329        let mut output = cache.result.clone();
330        // Get the difference between the items passed in and the cache of what we
331        // passed in last
332        for item in cache.arg.diff(input) {
333            match item {
334                im::ordset::DiffItem::Add(x) => {
335                    let (store, result) = self.f.call(self.f.init(), x);
336                    internal.insert(x.clone(), store);
337                    output.insert(result);
338                }
339                im::ordset::DiffItem::Update { old, new } => {
340                    let (prevstore, prev) = self.f.call(internal.remove(old).unwrap(), old);
341                    output.remove(&prev);
342                    let (store, result) = self.f.call(prevstore, new);
343                    internal.insert(new.clone(), store);
344                    output.insert(result);
345                }
346                im::ordset::DiffItem::Remove(x) => {
347                    let (_, prev) = self.f.call(internal.remove(x).unwrap(), x);
348                    output.remove(&prev);
349                }
350            }
351        }
352
353        (
354            Self::Store {
355                arg: input.clone(),
356                store: internal,
357                result: output.clone(),
358            },
359            output,
360        )
361    }
362}
363
364#[allow(refining_impl_trait)]
365impl<T: Ord + Clone, U: Ord + Clone> MapPersist<T, U> for im::OrdSet<T> {
366    type C<A> = im::OrdSet<A>;
367    fn map<F: FnPersist<T, U>>(f: F) -> OrdSetMap<T, U, F> {
368        f.into()
369    }
370}
371
372#[derive_where(Clone, Default)]
373pub struct OrdMapMapStore<K: Clone, V, U: Clone, F: FnPersist<V, U>> {
374    arg: im::OrdMap<K, V>,
375    result: im::OrdMap<K, U>,
376    store: im::OrdMap<K, F::Store>,
377}
378
379pub struct OrdMapMap<K, V, U, F: FnPersist<V, U>> {
380    f: F,
381    phantom_k: PhantomData<K>,
382    phantom_v: PhantomData<V>,
383    phantom_u: PhantomData<U>,
384}
385
386impl<K, V, U, F: FnPersist<V, U>> OrdMapMap<K, V, U, F> {
387    pub fn new(f: F) -> Self {
388        Self {
389            f,
390            phantom_k: PhantomData,
391            phantom_v: PhantomData,
392            phantom_u: PhantomData,
393        }
394    }
395}
396
397impl<K, V, U, F: FnPersist<V, U>> From<F> for OrdMapMap<K, V, U, F> {
398    fn from(f: F) -> Self {
399        Self::new(f)
400    }
401}
402
403impl<K: Clone, V, U: Clone, F: FnPersist<V, U>> FnPersistStore for OrdMapMap<K, V, U, F> {
404    type Store = OrdMapMapStore<K, V, U, F>;
405}
406
407impl<
408    K: Ord + std::cmp::PartialEq + Clone,
409    V: std::cmp::PartialEq,
410    U: Ord + Clone,
411    F: FnPersist<V, U>,
412> FnPersist<im::OrdMap<K, V>, im::OrdMap<K, U>> for OrdMapMap<K, V, U, F>
413where
414    F::Store: Clone,
415{
416    fn init(&self) -> Self::Store {
417        Default::default()
418    }
419    fn call(
420        &mut self,
421        cache: Self::Store,
422        input: &im::OrdMap<K, V>,
423    ) -> (Self::Store, im::OrdMap<K, U>) {
424        let mut internal = cache.store.clone();
425        let mut output = cache.result.clone();
426        // Get the difference between the items passed in and the cache of what we
427        // passed in last
428        for item in cache.arg.diff(input) {
429            match item {
430                im::ordmap::DiffItem::Add(x, v) => {
431                    let (store, result) = self.f.call(self.f.init(), v);
432                    internal.insert(x.clone(), store);
433                    output.insert(x.clone(), result);
434                }
435                im::ordmap::DiffItem::Remove(x, _) => {
436                    output.remove(x);
437                }
438                im::ordmap::DiffItem::Update { old, new } => {
439                    let (store, result) = self.f.call(internal.get(old.0).unwrap().clone(), new.1);
440                    internal.insert(new.0.clone(), store);
441                    output.insert(new.0.clone(), result);
442                }
443            }
444        }
445
446        (
447            Self::Store {
448                arg: input.clone(),
449                result: output.clone(),
450                store: internal,
451            },
452            output,
453        )
454    }
455}
456
457#[allow(refining_impl_trait)]
458impl<K: Ord + std::cmp::PartialEq + Clone, V: std::cmp::PartialEq, U: Ord + Clone> MapPersist<V, U>
459    for im::OrdMap<K, V>
460{
461    type C<A> = im::OrdMap<K, A>;
462
463    fn map<F: FnPersist<V, U>>(f: F) -> OrdMapMap<K, V, U, F> {
464        f.into()
465    }
466}
467
468#[allow(dead_code)]
469#[derive_where(Clone, Default)]
470pub struct VectorMapStore<V: Clone, U: Clone, F: FnPersist<V, U>> {
471    arg: im::Vector<V>,
472    result: im::Vector<U>,
473    store: im::Vector<F::Store>,
474}
475
476pub struct VectorMap<V, U, F: FnPersist<V, U>> {
477    f: F,
478    phantom_v: PhantomData<V>,
479    phantom_u: PhantomData<U>,
480}
481
482impl<V: Clone, U: Clone, F: FnPersist<V, U>> VectorMap<V, U, F> {
483    pub fn new(f: F) -> Self {
484        Self {
485            f,
486            phantom_v: PhantomData,
487            phantom_u: PhantomData,
488        }
489    }
490}
491
492impl<V: Clone, U: Clone, F: FnPersist<V, U>> From<F> for VectorMap<V, U, F> {
493    fn from(f: F) -> Self {
494        Self::new(f)
495    }
496}
497
498impl<V: Clone, U: Clone, F: FnPersist<V, U>> FnPersistStore for VectorMap<V, U, F> {
499    type Store = VectorMapStore<V, U, F>;
500}
501
502impl<V: Clone, U: Clone, F: FnPersist<V, U>> FnPersist<im::Vector<V>, im::Vector<U>>
503    for VectorMap<V, U, F>
504{
505    fn init(&self) -> Self::Store {
506        Default::default()
507    }
508    fn call(
509        &mut self,
510        mut store: Self::Store,
511        args: &im::Vector<V>,
512    ) -> (Self::Store, im::Vector<U>) {
513        // TODO: We can't implement this properly because tracking the storage requires
514        // access to im::Vector internals, and we can't even compare the two vectors
515        // either if store.arg != *args {
516        store.result.clear();
517        for v in args.iter() {
518            let (_, item) = self.f.call(self.f.init(), v);
519            store.result.push_back(item);
520        }
521        //}
522        let result = store.result.clone();
523        (store, result)
524    }
525}
526
527#[allow(refining_impl_trait)]
528impl<V: Clone, U: Clone> MapPersist<V, U> for im::Vector<V> {
529    type C<A> = im::Vector<A>;
530
531    fn map<F: FnPersist<V, U>>(f: F) -> VectorMap<V, U, F> {
532        f.into()
533    }
534}
535
536#[allow(dead_code)]
537#[derive_where(Clone)]
538pub struct VectorFoldStore<T: Clone, U: Clone, Store: Clone> {
539    arg: im::Vector<T>,
540    result: Option<U>,
541    store: im::Vector<Store>,
542}
543
544pub struct VectorFold<T, U, F> {
545    f: F,
546    phantom_t: PhantomData<T>,
547    phantom_u: PhantomData<U>,
548}
549
550impl<'a, T: 'a, U, F: FnPersist2<U, &'a T, U>> VectorFold<T, U, F> {
551    pub fn new(f: F) -> Self {
552        Self {
553            f,
554            phantom_t: PhantomData,
555            phantom_u: PhantomData,
556        }
557    }
558}
559
560impl<'a, T: 'a + Clone, U: Clone, F: FnPersist2<U, &'a T, U>> FnPersistStore
561    for VectorFold<T, U, F>
562{
563    type Store = VectorFoldStore<T, U, <F as FnPersistStore>::Store>;
564}
565
566impl<'a, T: 'a + Clone, U: Clone, F: FnPersist2<U, &'a T, U>> FnPersist2<U, &'a im::Vector<T>, U>
567    for VectorFold<T, U, F>
568{
569    fn init(&self) -> Self::Store {
570        Self::Store {
571            arg: Default::default(),
572            result: None,
573            store: Default::default(),
574        }
575    }
576
577    fn call(&mut self, store: Self::Store, arg1: U, arg2: &'a im::Vector<T>) -> (Self::Store, U) {
578        let mut seed = arg1.clone();
579
580        for item in arg2.iter() {
581            let (_, result) = self.f.call(self.f.init(), seed, item);
582            seed = result;
583        }
584
585        (store, seed)
586    }
587}
588
589impl<'a, T: 'a + Clone, U: Clone, F: FnPersist2<U, &'a T, U>> From<F> for VectorFold<T, U, F> {
590    fn from(f: F) -> Self {
591        Self::new(f)
592    }
593}
594
595#[allow(refining_impl_trait)]
596impl<'a, T: 'a + Clone, U: Clone> FoldPersist<'a, T, U> for im::Vector<T> {
597    type C<A>
598        = im::Vector<A>
599    where
600        A: 'a;
601
602    fn fold<F: FnPersist2<U, &'a T, U>>(f: F) -> VectorFold<T, U, F> {
603        f.into()
604    }
605}
feather_ui/persist.rs

feather_ui/
persist.rs
