inc_complete/lib.rs
1//! # Inc-Complete
2//!
3//! inc-complete is a library for incremental compilation supporting serialization from the ground
4//! up.
5//!
6//! In inc-complete, a central `Db` object is used to query and cache the result of _pure_
7//! functions. The functions being pure is key. If there are side-effects performed then
8//! they will not be re-performed when the computation's result is later cached and returned again.
9//!
10//! Before we create the `Db` object however, we need to define a tuple of all the computations
11//! we want to cache. In inc-complete, each computation is its own type and is either an input
12//! (if it has no dependencies) or an intermediate computation. For this example we're going to
13//! model the following spreadsheet:
14//!
15//! ```text
16//! [ A ] [ B ]
17//! [ 1 ] [ 12 ] [ =A1 + 8 ]
18//! [ 2 ] [ 4 ] [ =B1 + A2 ]
19//! ```
20//!
21//! We will have two inputs: `A1` and `A2`, and two intermediates: `B1` and `B2` where
22//! `B1` depends on `A1` and `B2` depends on `B1` and `A2` directly, and `A1` transitively.
23//! Let's start by defining these types:
24//!
25//! ```
26//! #[derive(Clone, Debug, Default)]
27//! struct A1;
28//!
29//! #[derive(Clone, Debug, Default)]
30//! struct A2;
31//!
32//! #[derive(Clone, PartialEq, Eq, Hash, Default)]
33//! struct B1;
34//!
35//! #[derive(Clone, PartialEq, Eq, Hash, Default)]
36//! struct B2;
37//! ```
38//!
39//! The derives are all necessary for some traits we'll implement later.
40//!
41//! Now we can define a type alias for the tuple containing all our computation types:
42//!
43//! ```
44//! # #[derive(Clone, Debug, Default)]
45//! # struct A1;
46//! # #[derive(Clone, Debug, Default)]
47//! # struct A2;
48//! # #[derive(Clone, PartialEq, Eq, Hash, Default)]
49//! # struct B1;
50//! # #[derive(Clone, PartialEq, Eq, Hash, Default)]
51//! # struct B2;
52//! use inc_complete::{ Input, Intermediate, SingletonStorage };
53//!
54//! type Spreadsheet = (
55//! SingletonStorage<Input<A1>>,
56//! SingletonStorage<Input<A2>>,
57//! SingletonStorage<Intermediate<B1>>,
58//! SingletonStorage<Intermediate<B2>>,
59//! );
60//! ```
61//!
62//! Note that we have to tell inc-complete both how we want to store our computation cache and
63//! whether the computation itself is an input or an intermediate computation derived from inputs or
64//! other intermediates. In this example, we're using `SingletonStorage` for all of our
65//! computations because all of `A1`, `A2`, `B1`, and `B2` are singleton values like `()` with
66//! only a single value in their type. This lets us store them with an `Option<T>` instead of a
67//! `HashMap<K, V>`. If you are unsure which storage type to choose, `HashMapStorage<T>` or
68//! `BTreeMapStorage<T>` are good defaults. Even if used on singletons they will give you correct
69//! behavior, just with slightly less performance than `SingletonStorage<T>`.
70//!
71//! Also note that the storage type wrapper goes on the outside of the `Input`/`Intermediate` type,
72//! you'll get trait errors if you try to define them the other way around.
73//!
74//! Let's also take the time now to create some `new` functions so we don't have to construct these
75//! wrappers each time:
76//!
77//! ```
78//! # #[derive(Clone, Debug, Default)]
79//! # struct A1;
80//! # #[derive(Clone, Debug, Default)]
81//! # struct A2;
82//! # #[derive(Clone, PartialEq, Eq, Hash, Default)]
83//! # struct B1;
84//! # #[derive(Clone, PartialEq, Eq, Hash, Default)]
85//! # struct B2;
86//! # use inc_complete::{ Input, Intermediate, SingletonStorage };
87//! impl A1 {
88//! fn new() -> SingletonStorage<Input<A1>> {
89//! Default::default()
90//! }
91//! }
92//!
93//! impl A2 {
94//! fn new() -> SingletonStorage<Input<A2>> {
95//! Default::default()
96//! }
97//! }
98//!
99//! impl B1 {
100//! fn new() -> SingletonStorage<Intermediate<B1>> {
101//! Default::default()
102//! }
103//! }
104//!
105//! impl B2 {
106//! fn new() -> SingletonStorage<Intermediate<B2>> {
107//! Default::default()
108//! }
109//! }
110//! ```
111//!
112//! It's true that we can just call `Default::default` in each, but having the output type
113//! be known helps for calls to `DbHandle::get::<T>(&mut self, computation: T)` which we'll see later.
114//!
115//! Next, for `Input` types we now need to define what type the input is. For this spreadsheet example
116//! all our types are `i64`:
117//!
118//! ```
119//! # #[derive(Clone, Debug, Default)]
120//! # struct A1;
121//! # #[derive(Clone, Debug, Default)]
122//! # struct A2;
123//! use inc_complete::OutputTypeForInput;
124//!
125//! impl OutputTypeForInput for A1 {
126//! type Output = i64;
127//! }
128//!
129//! impl OutputTypeForInput for A2 {
130//! type Output = i64;
131//! }
132//! ```
133//!
134//! For `Intermediate` types we need to provide a `run` function to compute their result. This function
135//! will have access to the computation type itself (which often store parameters as data) and
136//! a `DbHandle` object to query sub-computations with:
137//!
138//! ```
139//! # #[derive(Clone, Debug, Default)]
140//! # struct A1;
141//! # #[derive(Clone, Debug, Default)]
142//! # struct A2;
143//! # #[derive(Clone, PartialEq, Eq, Hash, Default)]
144//! # struct B1;
145//! # #[derive(Clone, PartialEq, Eq, Hash, Default)]
146//! # struct B2;
147//! # impl inc_complete::OutputTypeForInput for A1 {
148//! # type Output = i64;
149//! # }
150//! # impl inc_complete::OutputTypeForInput for A2 {
151//! # type Output = i64;
152//! # }
153//! # use inc_complete::{ Input, Intermediate, SingletonStorage };
154//! # impl A1 {
155//! # fn new() -> SingletonStorage<Input<A1>> {
156//! # Default::default()
157//! # }
158//! # }
159//! # impl A2 {
160//! # fn new() -> SingletonStorage<Input<A2>> {
161//! # Default::default()
162//! # }
163//! # }
164//! # impl B1 {
165//! # fn new() -> SingletonStorage<Intermediate<B1>> {
166//! # Default::default()
167//! # }
168//! # }
169//! # impl B2 {
170//! # fn new() -> SingletonStorage<Intermediate<B2>> {
171//! # Default::default()
172//! # }
173//! # }
174//! use inc_complete::{ Run, DbHandle, Computation };
175//!
176//! impl Run for B1 {
177//! type Output = i64;
178//!
179//! fn run(&self, handle: &mut DbHandle<impl Computation>) -> Self::Output {
180//! // These functions should be pure but we're going to cheat here to
181//! // make it obvious when a function is recomputed
182//! println!("Computing B1!");
183//! *handle.get(A1::new()) + 8
184//! }
185//! }
186//!
187//! impl Run for B2 {
188//! type Output = i64;
189//!
190//! fn run(&self, handle: &mut DbHandle<impl Computation>) -> Self::Output {
191//! println!("Computing B2!");
192//! *handle.get(B1::new()) + *handle.get(A2::new())
193//! }
194//! }
195//! ```
196//!
197//! Ceremony aside - this code should be relatively straight-forward. We `get` the value of
198//! any sub-computations we need and the `DbHandle` object automatically gives us the most
199//! up to date version of those computations - we'll examine this claim a bit closer later.
200//!
201//! Those `new` functions are also coming in handy now. Another approach would have been to make
202//! a wrapper function accepting a `DbHandle`:
203//!
204//! ```
205//! # #[derive(Clone, PartialEq, Eq, Hash, Default)]
206//! # struct B1;
207//! # use inc_complete::{ Input, Run, Intermediate, SingletonStorage, DbHandle, Computation };
208//! # #[derive(Clone, Debug, Default)]
209//! # struct A1;
210//! # impl inc_complete::OutputTypeForInput for A1 {
211//! # type Output = i64;
212//! # }
213//! # impl A1 {
214//! # fn new() -> SingletonStorage<Input<A1>> {
215//! # Default::default()
216//! # }
217//! # }
218//! # impl B1 {
219//! # fn new() -> SingletonStorage<Intermediate<B1>> {
220//! # Default::default()
221//! # }
222//! # }
223//! # impl Run for B1 {
224//! # type Output = i64;
225//! # fn run(&self, handle: &mut DbHandle<impl Computation>) -> Self::Output {
226//! # println!("Computing B1!");
227//! # *handle.get(A1::new()) + 8
228//! # }
229//! # }
230//! fn b1(handle: &mut DbHandle<impl Computation>) -> i64 {
231//! // Assuming we didn't have `B1::new()`
232//! *handle.get(SingletonStorage::new(Intermediate::new(B1)))
233//! // Now we can use `b1(handle)`
234//! }
235//! ```
236//!
237//! With that out of the way though, we can finally create our `Db`, set the initial values for our
238//! inputs, and run our program:
239//!
240//! ```
241//! # #[derive(Clone, Debug, Default)]
242//! # struct A1;
243//! # #[derive(Clone, Debug, Default)]
244//! # struct A2;
245//! # #[derive(Clone, PartialEq, Eq, Hash, Default)]
246//! # struct B1;
247//! # #[derive(Clone, PartialEq, Eq, Hash, Default)]
248//! # struct B2;
249//! # impl inc_complete::OutputTypeForInput for A1 {
250//! # type Output = i64;
251//! # }
252//! # impl inc_complete::OutputTypeForInput for A2 {
253//! # type Output = i64;
254//! # }
255//! # use inc_complete::{ Input, Intermediate, SingletonStorage };
256//! # impl A1 {
257//! # fn new() -> SingletonStorage<Input<A1>> {
258//! # Default::default()
259//! # }
260//! # }
261//! # impl A2 {
262//! # fn new() -> SingletonStorage<Input<A2>> {
263//! # Default::default()
264//! # }
265//! # }
266//! # impl B1 {
267//! # fn new() -> SingletonStorage<Intermediate<B1>> {
268//! # Default::default()
269//! # }
270//! # }
271//! # impl B2 {
272//! # fn new() -> SingletonStorage<Intermediate<B2>> {
273//! # Default::default()
274//! # }
275//! # }
276//! # impl inc_complete::Run for B1 {
277//! # type Output = i64;
278//! # fn run(&self, handle: &mut inc_complete::DbHandle<impl inc_complete::Computation>) -> Self::Output {
279//! # println!("Computing B1!");
280//! # *handle.get(A1::new()) + 8
281//! # }
282//! # }
283//! # impl inc_complete::Run for B2 {
284//! # type Output = i64;
285//! # fn run(&self, handle: &mut inc_complete::DbHandle<impl inc_complete::Computation>) -> Self::Output {
286//! # println!("Computing B2!");
287//! # *handle.get(B1::new()) + *handle.get(A2::new())
288//! # }
289//! # }
290//! # type Spreadsheet = (
291//! # SingletonStorage<Input<A1>>,
292//! # SingletonStorage<Input<A2>>,
293//! # SingletonStorage<Intermediate<B1>>,
294//! # SingletonStorage<Intermediate<B2>>,
295//! # );
296//! use inc_complete::Db;
297//! type SpreadsheetDb = Db<Spreadsheet>;
298//!
299//! fn main() {
300//! let mut db = SpreadsheetDb::new();
301//! db.update_input(A1::new(), 12);
302//! db.update_input(A2::new(), 4);
303//!
304//! // Output:
305//! // Computing B2!
306//! // Computing B1!
307//! let b2 = *db.get(B2::new());
308//! assert_eq!(b2, 24);
309//!
310//! // No output, result of B2 is cached
311//! let b2 = *db.get(B2::new());
312//! assert_eq!(b2, 24);
313//!
314//! // Now lets update an input
315//! db.update_input(A2::new(), 10);
316//!
317//! // B2 is now stale and gets recomputed, but crucially B1
318//! // does not depend on A2 and does not get recomputed.
319//! // Output:
320//! // Computing B2!
321//! let b2 = *db.get(B2::new());
322//! assert_eq!(b2, 30);
323//! }
324//! ```
325//!
326//! ...And that's it for basic usage! If you want to delve deeper you can implement
327//! your own `Input`, `Intermediate`, or storage type wrapper to have more control over how your
328//! type is cached by implementing the `Computation` trait.
329//!
330//! This example did not show it but you can also use structs with fields in your computations, e.g:
331//!
332//! ```
333//! use inc_complete::{ Intermediate, Run, DbHandle, Computation, HashMapStorage };
334//!
335//! // a fibonacci function with cached sub-results
336//! #[derive(Clone, PartialEq, Eq, Hash)]
337//! struct Fibonacci { x: u32 }
338//!
339//! impl Fibonacci {
340//! fn new(x: u32) -> HashMapStorage<Intermediate<Fibonacci>> {
341//! HashMapStorage::new(Intermediate::new(Fibonacci { x }))
342//! }
343//! }
344//!
345//! impl Run for Fibonacci {
346//! type Output = u32;
347//!
348//! fn run(&self, handle: &mut DbHandle<impl Computation>) -> Self::Output {
349//! let x = self.x;
350//! if x <= 1 {
351//! x
352//! } else {
353//! // Not exponential time since each sub-computation will be cached!
354//! *handle.get(Fibonacci::new(x - 1)) + handle.get(Fibonacci::new(x - 2))
355//! }
356//! }
357//! }
358//! ```
359//!
360//! These fields often correspond to parameters of the function being modeled, in
361//! this case the integer input to `fibonacci`.
362mod cell;
363#[macro_use]
364mod computation;
365mod db;
366mod interned;
367
368pub use ::paste;
369
370pub use cell::Cell;
371pub use computation::{
372 BTreeMapStorage, Computation, HashMapStorage, Input, Intermediate, OutputTypeForInput, Run,
373 SingletonStorage,
374};
375pub use db::{Db, DbHandle};