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 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236
#![no_std]
//! Single-threaded lazy evaluation.
//!
//! Lazy evaluation allows you to define computations whose
//! evaluation is deferred to when they are actually needed.
//! This can be also achieved with closures; however,
//! in case of lazy evaluation, the output of computations is
//! calculated only once and stored in a cache.
//!
//! Lazy evaluation is useful if you have an expensive computation
//! of which you might need the result more than once during runtime,
//! but you do not know in advance whether you will need it at all.
//!
//! Let us consider an example, where we first use a closure to defer evaluation:
//!
//! ~~~
//! fn expensive() -> i32 {
//! println!("I am expensive to evaluate!"); 7
//! }
//!
//! fn main() {
//! let a = || expensive(); // Nothing is printed.
//!
//! assert_eq!(a(), 7); // "I am expensive to evaluate!" is printed here
//!
//! let b = [a(), a()]; // "I am expensive to evaluate!" is printed twice
//! assert_eq!(b, [7, 7]);
//! }
//! ~~~
//!
//! Contrast this with using lazy evaluation:
//!
//! ~~~
//! # use lazy_st::lazy;
//! fn expensive() -> i32 {
//! println!("I am expensive to evaluate!"); 7
//! }
//!
//! fn main() {
//! let a = lazy!(expensive()); // Nothing is printed.
//!
//! // Thunks are just smart pointers!
//! assert_eq!(*a, 7); // "I am expensive to evaluate!" is printed here
//!
//! let b = [*a, *a]; // Nothing is printed.
//! assert_eq!(b, [7, 7]);
//! }
//! ~~~
//!
//! Lazy values from this crate cannot be shared between threads.
//! If you need this, please consider using the `lazy-mt` crate.
extern crate alloc;
use alloc::boxed::Box;
use core::cell::UnsafeCell;
use core::ops::{Deref, DerefMut};
use self::Inner::{Evaluating, Unevaluated, Value};
/// A lazily evaluated value.
#[derive(Debug)]
pub struct Thunk<E, V>(UnsafeCell<Inner<E, V>>);
/// A lazily evaluated value produced from a closure.
pub type Lazy<T> = Thunk<Box<dyn FnOnce() -> T>, T>;
/// Construct a lazily evaluated value using a closure.
///
/// ~~~
/// # use lazy_st::lazy;
/// let val = lazy!(7);
/// assert_eq!(*val, 7);
/// ~~~
#[macro_export]
macro_rules! lazy {
($e:expr) => {
$crate::Thunk::new(Box::new(move || $e))
};
}
impl<E, V> Thunk<E, V>
where
E: Evaluate<V>,
{
/// Create a lazily evaluated value from
/// a value implementing the `Evaluate` trait.
///
/// The `lazy!` macro is preferred if you want to
/// construct values from closures.
///
/// ~~~
/// # use lazy_st::Thunk;
/// let expensive = Thunk::new(|| { println!("Evaluated!"); 7 });
/// assert_eq!(*expensive, 7); // "Evaluated!" gets printed here.
/// assert_eq!(*expensive, 7); // Nothing printed.
/// ~~~
pub fn new(e: E) -> Thunk<E, V> {
Thunk(UnsafeCell::new(Unevaluated(e)))
}
/// Create a new, evaluated, thunk from a value.
///
/// ~~~
/// # use lazy_st::{Thunk, Lazy};
/// let x: Lazy<u32> = Thunk::evaluated(10);
/// assert_eq!(*x, 10);
/// ~~~
pub fn evaluated(v: V) -> Thunk<E, V> {
Thunk(UnsafeCell::new(Value(v)))
}
/// Force evaluation of a thunk.
pub fn force(&self) {
match unsafe { &*self.0.get() } {
Value(_) => return,
Evaluating => panic!("Thunk::force called during evaluation."),
Unevaluated(_) => (),
}
unsafe {
match core::ptr::replace(self.0.get(), Evaluating) {
Unevaluated(e) => *self.0.get() = Value(e.evaluate()),
_ => unreachable!(),
};
}
}
/// Force the evaluation of a thunk and get the value, consuming the thunk.
///
/// ~~~
/// # use lazy_st::lazy;
/// let val = lazy!(7);
/// assert_eq!(val.unwrap(), 7);
/// ~~~
pub fn unwrap(self) -> V {
self.force();
match self.0.into_inner() {
Value(v) => v,
_ => unreachable!(),
}
}
}
/// Generalisation of lazy evaluation to other types than closures.
///
/// The main use case for implementing this trait is the following:
/// Let us suppose that you construct a large number of lazy values using
/// only one function `f` with different values `x1`, ..., `xn` of type `T`,
/// i.e. `lazy!(f(x1))`, ..., `lazy!(f(xn))`.
/// In this case, you may consider implementing `Evaluate` for `T` such that
/// `evaluate(x)` yields `f(x)`.
/// This allows you to use `Thunk::new(x)` instead of `lazy!(f(x))`,
/// saving time and space because
/// any such `Thunk` will contain only `x` instead of both `f` and `x`.
///
/// Let us look at an example:
///
/// ~~~
/// # use lazy_st::{Thunk, Evaluate};
/// struct User(usize);
///
/// impl Evaluate<String> for User {
/// fn evaluate(self) -> String {
/// format!("User no. {}", self.0)
/// }
/// }
///
/// let root = Thunk::new(User(0));
/// let mere_mortal = Thunk::evaluated(String::from("Someone else"));
/// let user = if true { root } else { mere_mortal };
/// assert_eq!(*user, "User no. 0");
/// ~~~
///
/// Note that this trait is quite similar to the `Into` trait.
/// Unfortunately, it seems that we cannot use `Into` here,
/// because we cannot implement it for instances of `FnOnce`,
/// which is necessary for `Lazy`.
pub trait Evaluate<T> {
fn evaluate(self) -> T;
}
impl<A: FnOnce() -> B, B> Evaluate<B> for A {
fn evaluate(self) -> B {
self()
}
}
#[derive(Debug)]
enum Inner<E, V> {
Unevaluated(E),
Evaluating,
Value(V),
}
impl<E, V> Clone for Thunk<E, V>
where
E: Clone,
V: Clone,
{
fn clone(&self) -> Self {
match unsafe { &*self.0.get() } {
Unevaluated(e) => Thunk(UnsafeCell::new(Unevaluated(e.clone()))),
Evaluating => panic!("Cloning thunk during evaluation."),
Value(v) => Thunk(UnsafeCell::new(Value(v.clone()))),
}
}
}
impl<E, V> Deref for Thunk<E, V>
where
E: Evaluate<V>,
{
type Target = V;
fn deref(&self) -> &V {
self.force();
match unsafe { &*self.0.get() } {
Value(ref v) => v,
_ => unreachable!(),
}
}
}
impl<E, V> DerefMut for Thunk<E, V>
where
E: Evaluate<V>,
{
fn deref_mut(&mut self) -> &mut V {
self.force();
match unsafe { &mut *self.0.get() } {
Value(ref mut v) => v,
_ => unreachable!(),
}
}
}