1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
#![feature(
async_fn_in_trait,
thread_id_value,
return_position_impl_trait_in_trait
)]
/*!
Incria is a library for incremental computation.
It lets you record what a calculation depends on and then only re-run that calculation once one of those dependencies has changed.
This is similar to the [query system used by the Rust compiler](https://rustc-dev-guide.rust-lang.org/query.html), but implemented using async.
By seperating the tracking of dependencies from the calculation logic, you can write clean code that re-runs only when it needs to, and can be parallelised with little extra work.
# Concepts
## Mappings
A mapping associates a key with a value. This can include:
* Functions
* Reading from a file
* Data from another part of the program, such as a UI
A [mapper](`self::Mapper`) is responsible for exposing this mapping, and for caching and invalidating the mapping as appropriate.
## Dependencies
For mappings that use other mappings to get a value (most commonly functions), we need some way of knowing what mappings they depend on, and when those mappings have changed.
To do this, we use a directed acyclic graph (DAG).
Each mapping is represented by a node on this graph.
An edge from A to B means that the result of A's mapping depends on the result of B's mapping, and so A should be recomputed if B may have changed.
If we only have functions as mappings, then we will construct this graph and probably never use it.
In the more likely case that we have some 'impure' parts, such as reading a file, then we will eventually need to say that a mapping's value may have changed. We do this by marking the node as 'dirty'.
When a node is marked dirty, any node that depends on it directly or indirectly is also marked dirty.
The next time the mapping corresponding to a dirty node is requested, it should be recomputed and not cached.
# Usage
## Functions
To memoise computations, you can normally use a [`ThunkMapper`](`self::thunk::ThunkMapper`).
This memoises a given 'thunk', which is simply a function with one input, one output, and that is pure except for its use of other mappers.
```rust
use incria::{thunk::{Thunk, ThunkMapper}, Mapper};
# use std::{future::Future, pin::Pin};
#[derive(Default)]
struct ExampleThunk;
impl Thunk<usize, usize> for ExampleThunk {
fn compute(&self, key: usize) -> Pin<Box<dyn Future<Output = usize> + Send + '_>> {
Box::pin(async move {
key
})
}
}
type ExampleMapper = ThunkMapper<usize, usize, ExampleThunk>;
# async fn example() {
assert_eq!(*ExampleMapper::default().get(&1).await, 1);
# }
```
# Writing Mappers
When writing mappers, you will need to interface with the [dependency API](`self::deps`) directly.
See the module-level documentation for details on which functions to call and when.
Normally, you will keep track of dependency IDs alongside some other information, then expose some poll function externally that will mark all the required nodes dirty.
*/
pub mod deps;
mod lazy_mapping;
mod mapping;
pub mod thunk;
pub use mapping::Mapper;
|
