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)]
27//! struct A1;
28//!
29//! #[derive(Clone, Debug)]
30//! struct A2;
31//!
32//! #[derive(Clone, PartialEq, Eq, Hash)]
33//! struct B1;
34//!
35//! #[derive(Clone, PartialEq, Eq, Hash)]
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)]
45//! # struct A1;
46//! # #[derive(Clone, Debug)]
47//! # struct A2;
48//! # #[derive(Clone, PartialEq, Eq, Hash)]
49//! # struct B1;
50//! # #[derive(Clone, PartialEq, Eq, Hash)]
51//! # struct B2;
52//! use inc_complete::{ Input, Cached };
53//!
54//! type Spreadsheet = (
55//! Input<A1>,
56//! Input<A2>,
57//! Cached<B1>,
58//! Cached<B2>,
59//! );
60//! ```
61//!
62//! Note that we have to tell inc-complete whether this computation is an input or not.
63//! Among other things, this affects the storage type these values are cached in. For `Input` types we
64//! now need to define what type the input is. For this spreadsheet example all
65//! our types are `i64`:
66//!
67//! ```
68//! # #[derive(Clone, Debug)]
69//! # struct A1;
70//! # #[derive(Clone, Debug)]
71//! # struct A2;
72//! # #[derive(Clone, PartialEq, Eq, Hash)]
73//! # struct B1;
74//! # #[derive(Clone, PartialEq, Eq, Hash)]
75//! # struct B2;
76//! use inc_complete::OutputTypeForInput;
77//!
78//! impl OutputTypeForInput for A1 {
79//! type Output = i64;
80//! }
81//!
82//! impl OutputTypeForInput for A2 {
83//! type Output = i64;
84//! }
85//! ```
86//!
87//! For `Cached` types we need to provide a `run` function to compute their result. This function
88//! will have access to the computation type itself (which often store parameters as data) and
89//! a `DbHandle` object to query sub-computations with:
90//!
91//! ```
92//! # #[derive(Clone, Debug)]
93//! # struct A1;
94//! # #[derive(Clone, Debug)]
95//! # struct A2;
96//! # #[derive(Clone, PartialEq, Eq, Hash)]
97//! # struct B1;
98//! # #[derive(Clone, PartialEq, Eq, Hash)]
99//! # struct B2;
100//! # impl inc_complete::OutputTypeForInput for A1 {
101//! # type Output = i64;
102//! # }
103//! # impl inc_complete::OutputTypeForInput for A2 {
104//! # type Output = i64;
105//! # }
106//! # use inc_complete::{ Input, Cached };
107//! use inc_complete::{ Run, DbHandle, Computation };
108//!
109//! impl Run for B1 {
110//! type Output = i64;
111//!
112//! fn run(&self, handle: &mut DbHandle<impl Computation>) -> Self::Output {
113//! // These functions should be pure but we're going to cheat here to
114//! // make it obvious when a function is recomputed
115//! println!("Computing B1!");
116//! *handle.get(Input::<A1>::new()) + 8
117//! }
118//! }
119//!
120//! impl Run for B2 {
121//! type Output = i64;
122//!
123//! fn run(&self, handle: &mut DbHandle<impl Computation>) -> Self::Output {
124//! println!("Computing B2!");
125//! *handle.get(Cached::new(B1)) + *handle.get(Input::<A2>::new())
126//! }
127//! }
128//! ```
129//!
130//! Having to wrap computations in an `Input` or `Cached` wrapper each time can be
131//! burdensome so in a real program we may want to define `new` functions which do this for us.
132//!
133//! With that out of the way, we can finally create our `Db`, set the initial values for our
134//! inputs, and run our program:
135//!
136//! ```
137//! # #[derive(Clone, Debug)]
138//! # struct A1;
139//! # #[derive(Clone, Debug)]
140//! # struct A2;
141//! # #[derive(Clone, PartialEq, Eq, Hash)]
142//! # struct B1;
143//! # #[derive(Clone, PartialEq, Eq, Hash)]
144//! # struct B2;
145//! # impl inc_complete::OutputTypeForInput for A1 {
146//! # type Output = i64;
147//! # }
148//! # impl inc_complete::OutputTypeForInput for A2 {
149//! # type Output = i64;
150//! # }
151//! # impl inc_complete::Run for B1 {
152//! # type Output = i64;
153//! # fn run(&self, handle: &mut inc_complete::DbHandle<impl inc_complete::Computation>) -> Self::Output {
154//! # // These functions should be pure but we're going to cheat here to
155//! # // make it obvious when a function is recomputed
156//! # println!("Computing B1!");
157//! # *handle.get(inc_complete::Input::<A1>::new()) + 8
158//! # }
159//! # }
160//! # impl inc_complete::Run for B2 {
161//! # type Output = i64;
162//! # fn run(&self, handle: &mut inc_complete::DbHandle<impl inc_complete::Computation>) -> Self::Output {
163//! # println!("Computing B2!");
164//! # *handle.get(inc_complete::Cached::new(B1)) + *handle.get(inc_complete::Input::<A2>::new())
165//! # }
166//! # }
167//! # type Spreadsheet = (
168//! # inc_complete::Input<A1>,
169//! # inc_complete::Input<A2>,
170//! # inc_complete::Cached<B1>,
171//! # inc_complete::Cached<B2>,
172//! # );
173//! # use inc_complete::{ Input, Cached };
174//! use inc_complete::Db;
175//! type SpreadsheetDb = Db<Spreadsheet>;
176//!
177//! fn main() {
178//! let mut db = SpreadsheetDb::new();
179//! db.update_input(Input::<A1>::new(), 12);
180//! db.update_input(Input::<A2>::new(), 4);
181//!
182//! // Output:
183//! // Computing B2!
184//! // Computing B1!
185//! let b2 = *db.get(Cached::new(B2));
186//! assert_eq!(b2, 24);
187//!
188//! // No output, result of B2 is cached
189//! let b2 = *db.get(Cached::new(B2));
190//! assert_eq!(b2, 24);
191//!
192//! // Now lets update an input
193//! db.update_input(Input::<A2>::new(), 10);
194//!
195//! // B2 is now stale and gets recomputed, but crucially B1
196//! // does not depend on A2 and does not get recomputed.
197//! // Output:
198//! // Computing B2!
199//! let b2 = *db.get(Cached::new(B2));
200//! assert_eq!(b2, 30);
201//! }
202//! ```
203//!
204//! ...And that's it for basic usage! If you want to delve deeper you can implement
205//! your own `Input` or `Cached`-like wrapper to have more control over how your
206//! type is cached by implementing the `Computation` trait.
207//!
208//! This example did not show it but you can also use structs with fields in your computations, e.g:
209//!
210//! ```
211//! # use inc_complete::{ Cached, Run, DbHandle, Computation };
212//! // a fibonacci function with cached sub-results
213//! #[derive(Clone, PartialEq, Eq, Hash)]
214//! struct Fibonacci { x: u32 }
215//!
216//! impl Fibonacci {
217//! fn new(x: u32) -> Cached<Fibonacci> {
218//! Cached::new(Fibonacci { x })
219//! }
220//! }
221//!
222//! impl Run for Fibonacci {
223//! type Output = u32;
224//!
225//! fn run(&self, handle: &mut DbHandle<impl Computation>) -> Self::Output {
226//! let x = self.x;
227//! if x <= 1 {
228//! x
229//! } else {
230//! // Not exponential time since each sub-computation will be cached!
231//! *handle.get(Fibonacci::new(x - 1)) + handle.get(Fibonacci::new(x - 2))
232//! }
233//! }
234//! }
235//! ```
236//!
237//! These fields often correspond to parameters of the function being modeled, in
238//! this case the integer input to `fibonacci`.
239mod cell;
240mod computation;
241mod db;
242mod interned;
243
244pub use cell::Cell;
245pub use computation::{Cached, Computation, Input, OutputTypeForInput, Run};
246pub use db::{Db, DbHandle};