comemo_macros/lib.rs
1extern crate proc_macro;
2
3/// Return an error at the given item.
4macro_rules! bail {
5 ($item:expr, $fmt:literal $($tts:tt)*) => {
6 return Err(Error::new_spanned(
7 &$item,
8 format!(concat!("comemo: ", $fmt) $($tts)*)
9 ))
10 }
11}
12
13mod memoize;
14mod track;
15mod utils;
16
17use proc_macro::TokenStream as BoundaryStream;
18use proc_macro2::TokenStream;
19use quote::{quote, quote_spanned};
20use syn::spanned::Spanned;
21use syn::{Error, Result, parse_quote};
22
23/// Memoize a function.
24///
25/// This attribute can be applied to free-standing functions as well as methods
26/// in inherent and trait impls.
27///
28/// # Kinds of arguments
29/// Memoized functions can take three different kinds of arguments:
30///
31/// - _Hashed:_ This is the default. These arguments are hashed into a
32/// high-quality 128-bit hash, which is used as a cache key.
33///
34/// - _Immutably tracked:_ The argument is of the form `Tracked<T>`. These
35/// arguments enjoy fine-grained access tracking. This allows cache hits to
36/// occur even if the value of `T` is different than previously as long as the
37/// difference isn't observed.
38///
39/// - _Mutably tracked:_ The argument is of the form `TrackedMut<T>`. Through
40/// this type, you can safely mutate an argument from within a memoized
41/// function. If there is a cache hit, comemo will replay all mutations.
42/// Mutable tracked methods cannot have return values.
43///
44/// # Restrictions
45/// The following restrictions apply to memoized functions:
46///
47/// - For the memoization to be correct, the [`Hash`](std::hash::Hash)
48/// implementations of your arguments **must feed all the information they
49/// expose to the hasher**. Otherwise, memoized results might get reused
50/// invalidly.
51///
52/// - The **only observable impurity memoized functions may exhibit are
53/// mutations through `TrackedMut<T>` arguments.** Comemo stops you from using
54/// basic mutable arguments, but it cannot determine all sources of impurity,
55/// so this is your responsibility.
56///
57/// - Memoized functions must **call tracked methods in _reorderably
58/// deterministic_ fashion.** Consider two executions A and B of a memoized
59/// function. We define the following two properties:
60///
61/// - _In-order deterministic:_ If the first N tracked calls and their results
62/// are the same in A and B, then the N+1th call must also be the same. This
63/// is a fairly natural property as far as deterministic functions go, as,
64/// if the first N calls and their results were the same across two
65/// execution, the available information for choosing the N+1th call is the
66/// same. However, this property is a bit too restrictive in practice. For
67/// instance, a function that internally uses multi-threading may call
68/// tracked methods out-of-order while still producing a deterministic
69/// result.
70///
71/// - _Reorderably deterministic:_ If, for the first N calls in A, B has
72/// matching calls (same arguments, same return value) somewhere in its call
73/// sequence, then the N+1th call invoked by A must also occur _somewhere_
74/// in the call sequence of B. This is a somewhat relaxed version of
75/// in-order determinism that still allows comemo to perform internal
76/// optimizations while permitting memoization of many more functions (e.g.
77/// ones that use internal multi-threading in an outwardly deterministic
78/// fashion).
79///
80/// Reorderable determinism is necessary for efficient cache lookups. If a
81/// memoized function is not reorderably determinstic, comemo may panic in
82/// debug mode to bring your attention to this. Meanwhile, in release mode,
83/// memoized functions will still yield correct results, but caching may prove
84/// ineffective.
85///
86/// - The output of a memoized function must be `Send` and `Sync` because it is
87/// stored in the global cache.
88///
89/// Furthermore, memoized functions cannot use destructuring patterns in their
90/// arguments.
91///
92/// # Example
93/// ```
94/// /// Evaluate a `.calc` script.
95/// #[comemo::memoize]
96/// fn evaluate(script: &str, files: comemo::Tracked<Files>) -> i32 {
97/// script
98/// .split('+')
99/// .map(str::trim)
100/// .map(|part| match part.strip_prefix("eval ") {
101/// Some(path) => evaluate(&files.read(path), files),
102/// None => part.parse::<i32>().unwrap(),
103/// })
104/// .sum()
105/// }
106/// ```
107///
108/// # Disabling memoization conditionally
109/// If you want to enable or disable memoization for a function conditionally,
110/// you can use the `enabled` attribute. This is useful for cheap function calls
111/// where dealing with the caching is more expensive than recomputing the
112/// result. This allows you to bypass hashing and constraint validation while
113/// still dealing with the same function signature. And allows saving memory and
114/// time.
115///
116/// By default, all functions are unconditionally memoized. To disable
117/// memoization conditionally, you must specify an `enabled = <expr>` attribute.
118/// The expression can use the parameters and must evaluate to a boolean value.
119/// If the expression is `false`, the function will be executed without hashing
120/// and caching.
121///
122/// ## Example
123/// ```
124/// /// Compute the sum of a slice of floats, but only memoize if the slice is
125/// /// longer than 1024 elements.
126/// #[comemo::memoize(enabled = add.len() > 1024)]
127/// fn evaluate(add: &[f32]) -> f32 {
128/// add.iter().copied().sum()
129/// }
130/// ```
131///
132#[proc_macro_attribute]
133pub fn memoize(args: BoundaryStream, stream: BoundaryStream) -> BoundaryStream {
134 let args = syn::parse_macro_input!(args as TokenStream);
135 let func = syn::parse_macro_input!(stream as syn::Item);
136 memoize::expand(args, &func)
137 .unwrap_or_else(|err| err.to_compile_error())
138 .into()
139}
140
141/// Make a type trackable.
142///
143/// This attribute can be applied to an inherent implementation block or trait
144/// definition. It implements the `Track` trait for the type or trait object.
145///
146/// # Tracking immutably and mutably
147/// This allows you to
148///
149/// - call `track()` on that type, producing a `Tracked<T>` container. Used as
150/// an argument to a memoized function, these containers enjoy fine-grained
151/// access tracking instead of blunt hashing.
152///
153/// - call `track_mut()` on that type, producing a `TrackedMut<T>`. For mutable
154/// arguments, tracking is the only option, so that comemo can replay the side
155/// effects when there is a cache hit.
156///
157/// # Restrictions
158/// Tracked impl blocks or traits may not be generic and may only contain
159/// methods. Just like with memoized functions, certain restrictions apply to
160/// tracked methods:
161///
162/// - The **only obversable impurity tracked methods may exhibit are mutations
163/// through `&mut self`.** Comemo stops you from using basic mutable arguments
164/// and return values, but it cannot determine all sources of impurity, so
165/// this is your responsibility. Tracked methods also must not return mutable
166/// references or other types which allow untracked mutation. You _are_
167/// allowed to use interior mutability if it is not observable (even in
168/// immutable methods, as long as they stay idempotent).
169///
170/// - The return values of tracked methods must implement
171/// [`Hash`](std::hash::Hash) and **must feed all the information they expose
172/// to the hasher**. Otherwise, memoized results might get reused invalidly.
173///
174/// - Mutable tracked methods must not have a return value.
175///
176/// - A tracked implementation cannot have a mix of mutable and immutable
177/// methods.
178///
179/// - The arguments to a tracked method must be `Send` and `Sync` because they
180/// are stored in the global cache.
181///
182/// Furthermore:
183/// - Tracked methods cannot be generic.
184/// - They cannot be `unsafe`, `async` or `const`.
185/// - They must take an `&self` or `&mut self` parameter.
186/// - Their arguments must implement [`ToOwned`].
187/// - Their return values must implement [`Hash`](std::hash::Hash).
188/// - They cannot use destructuring patterns in their arguments.
189///
190/// # Example
191/// ```
192/// /// File storage.
193/// struct Files(HashMap<PathBuf, String>);
194///
195/// #[comemo::track]
196/// impl Files {
197/// /// Load a file from storage.
198/// fn read(&self, path: &str) -> String {
199/// self.0.get(Path::new(path)).cloned().unwrap_or_default()
200/// }
201/// }
202///
203/// impl Files {
204/// /// Write a file to storage.
205/// fn write(&mut self, path: &str, text: &str) {
206/// self.0.insert(path.into(), text.into());
207/// }
208/// }
209/// ```
210#[proc_macro_attribute]
211pub fn track(_: BoundaryStream, stream: BoundaryStream) -> BoundaryStream {
212 let block = syn::parse_macro_input!(stream as syn::Item);
213 track::expand(&block)
214 .unwrap_or_else(|err| err.to_compile_error())
215 .into()
216}