mod_memoize/
lib.rs

1use config::epoch::{get_current_epoch, ConfigEpoch};
2use config::{any_err, from_lua_value, get_or_create_module, load_config, serialize_options};
3use dashmap::DashMap;
4use kumo_prometheus::declare_metric;
5use kumo_prometheus::prometheus::Counter;
6use lruttl::{ItemLookup, LruCacheWithTtl, PopulateAbandoned};
7use mlua::{
8    FromLua, Function, IntoLua, Lua, LuaSerdeExt, MetaMethod, MultiValue, UserData,
9    UserDataMethods, UserDataRef,
10};
11use parking_lot::Mutex;
12use serde::{Deserialize, Serialize};
13use std::collections::HashMap;
14use std::sync::{Arc, LazyLock};
15use std::time::Duration;
16
17/// Memoized is a helper type that allows native Rust types to be captured
18/// in memoization caches.
19/// Unfortunately, we cannot automatically make that work for all UserData
20/// that are exported to lua, but we can make it simple for a type to opt-in
21/// to that behavior.
22///
23/// When you impl UserData for your type, you can call
24/// `Memoized::impl_memoize(methods)` from your add_methods impl.
25/// That will add a metamethod to your UserData type that will clone your
26/// value and wrap it into a Memoized wrapper.
27///
28/// Since Clone is used, it is recommended that you use an Arc inside your
29/// type to avoid making large or expensive clones.
30#[derive(Clone, mlua::FromLua)]
31pub struct Memoized {
32    pub to_value: Arc<dyn Fn(&Lua) -> mlua::Result<mlua::Value> + Send + Sync>,
33}
34
35impl PartialEq for Memoized {
36    fn eq(&self, other: &Self) -> bool {
37        Arc::ptr_eq(&self.to_value, &other.to_value)
38    }
39}
40
41impl Memoized {
42    /// Call this from your `UserData::add_methods` implementation to
43    /// enable memoization for your UserData type
44    pub fn impl_memoize<T, M>(methods: &mut M)
45    where
46        T: UserData + Send + Sync + Clone + 'static,
47        M: UserDataMethods<T>,
48    {
49        methods.add_meta_method(
50            "__memoize",
51            move |_lua, this, _: ()| -> mlua::Result<Memoized> {
52                let this = this.clone();
53                Ok(Memoized {
54                    to_value: Arc::new(move |lua| this.clone().into_lua(lua)),
55                })
56            },
57        );
58    }
59}
60
61impl UserData for Memoized {}
62
63#[derive(Serialize, Deserialize, Clone, Debug, PartialEq, Eq)]
64#[serde(deny_unknown_fields)]
65pub struct MemoizeParams {
66    #[serde(with = "duration_serde")]
67    pub ttl: Duration,
68    pub capacity: usize,
69    pub name: String,
70    #[serde(default)]
71    pub invalidate_with_epoch: bool,
72    #[serde(default)]
73    pub retry_on_populate_timeout: bool,
74    #[serde(default, with = "duration_serde")]
75    pub populate_timeout: Option<Duration>,
76    #[serde(default)]
77    pub allow_stale_reads: bool,
78    #[serde(default)]
79    pub detached: Option<bool>,
80}
81
82#[derive(Clone, Hash, Eq, PartialEq)]
83pub enum MapKey {
84    Integer(mlua::Integer),
85    String(Vec<u8>),
86}
87
88impl MapKey {
89    pub fn from_lua(v: mlua::Value) -> Option<Self> {
90        match v {
91            mlua::Value::String(s) => Some(Self::String(s.as_bytes().to_vec())),
92            mlua::Value::Integer(n) => Some(Self::Integer(n)),
93            _ => None,
94        }
95    }
96
97    pub fn as_lua(self, lua: &Lua) -> mlua::Result<mlua::Value> {
98        match self {
99            Self::Integer(j) => Ok(mlua::Value::Integer(j)),
100            Self::String(b) => Ok(mlua::Value::String(lua.create_string(b)?)),
101        }
102    }
103}
104
105#[derive(Clone, PartialEq)]
106pub enum CacheValue {
107    Table(Arc<HashMap<MapKey, CacheValue>>),
108    Json(serde_json::Value),
109    Memoized(Memoized),
110}
111
112impl std::fmt::Debug for CacheValue {
113    fn fmt(&self, fmt: &mut std::fmt::Formatter) -> std::fmt::Result {
114        fmt.debug_struct("CacheValue").finish()
115    }
116}
117
118impl FromLua for CacheValue {
119    fn from_lua(value: mlua::Value, lua: &Lua) -> mlua::Result<Self> {
120        match value {
121            mlua::Value::UserData(ud) => {
122                let mt = ud.metatable()?;
123                let func: Function = mt.get("__memoize")?;
124                let m: Memoized = func.call(mlua::Value::UserData(ud))?;
125                Ok(Self::Memoized(m))
126            }
127            mlua::Value::Table(tbl) => {
128                let mut map = HashMap::new();
129                for pair in tbl.pairs::<mlua::Value, mlua::Value>() {
130                    let (key, value) = pair?;
131                    let key = match key {
132                        mlua::Value::Integer(n) => MapKey::Integer(n),
133                        mlua::Value::String(n) => MapKey::String(n.as_bytes().to_vec()),
134                        _ => {
135                            return Err(anyhow::anyhow!(
136                                "table key {key:?} cannot be used as a key in a memoizable table"
137                            ))
138                            .map_err(any_err)
139                        }
140                    };
141                    let value = CacheValue::from_lua(value, lua)?;
142                    map.insert(key, value);
143                }
144                Ok(Self::Table(map.into()))
145            }
146            _ => Ok(Self::Json(from_lua_value(lua, value)?)),
147        }
148    }
149}
150
151impl IntoLua for CacheValue {
152    fn into_lua(self, lua: &Lua) -> mlua::Result<mlua::Value> {
153        self.as_lua(lua)
154    }
155}
156
157impl CacheValue {
158    pub fn as_lua(&self, lua: &Lua) -> mlua::Result<mlua::Value> {
159        match self {
160            Self::Json(j) => lua.to_value_with(j, serialize_options()),
161            Self::Memoized(m) => (m.to_value)(lua),
162            Self::Table(m) => Ok(mlua::Value::UserData(
163                lua.create_userdata(MemoizedTable::Shared(m.clone()))?,
164            )),
165        }
166    }
167}
168
169/// MemoizedTable is a helper type that is returned to represent
170/// cached table values.  We'll return the Shared variant by
171/// default as that presents the cheapest way to return the cached
172/// data--only a clone of the underlying Arc is required to return
173/// the value.
174///
175/// This type implements __index, __newindex, __len, and __pairs
176/// metamethods which allow reading and iterating the table.
177///
178/// Writing to the table via __newindex will "unshare" the table in
179/// a similar manner to the Cow type, creating a mutable copy of the top
180/// level of the table.
181enum MemoizedTable {
182    Shared(Arc<HashMap<MapKey, CacheValue>>),
183    Mut(HashMap<MapKey, CacheValue>),
184}
185
186impl MemoizedTable {
187    /// Get a reference to the table, facilitating get() and iter(),
188    /// regardless of whether we are Shared or Mut.
189    fn table(&self) -> &HashMap<MapKey, CacheValue> {
190        match self {
191            Self::Shared(s) => s,
192            Self::Mut(s) => s,
193        }
194    }
195
196    /// Transform Shared -> Mut
197    fn unshare(&mut self) -> &mut HashMap<MapKey, CacheValue> {
198        if let Self::Shared(t) = self {
199            *self = Self::Mut(t.iter().map(|(k, v)| (k.clone(), v.clone())).collect());
200        }
201
202        match self {
203            Self::Shared(_) => unreachable!(),
204            Self::Mut(map) => map,
205        }
206    }
207}
208
209impl UserData for MemoizedTable {
210    fn add_methods<M: UserDataMethods<Self>>(methods: &mut M) {
211        // Index allows reading fields of the table
212        methods.add_meta_method(MetaMethod::Index, move |lua, this, key: mlua::Value| {
213            match MapKey::from_lua(key) {
214                Some(key) => match this.table().get(&key) {
215                    Some(value) => value.as_lua(lua),
216                    None => Ok(mlua::Value::Nil),
217                },
218                None => Ok(mlua::Value::Nil),
219            }
220        });
221
222        // NewIndex allows writing fields of the table
223        methods.add_meta_method_mut(
224            MetaMethod::NewIndex,
225            move |lua, this, (key, value): (mlua::Value, mlua::Value)| match MapKey::from_lua(key) {
226                Some(key) => {
227                    let value = CacheValue::from_lua(value, lua)?;
228                    this.unshare().insert(key, value);
229                    Ok(())
230                }
231                None => Err(mlua::Error::external(
232                    "invalid key type while trying to call __newindex and assign a value",
233                )),
234            },
235        );
236        methods.add_meta_method(MetaMethod::Len, move |_lua, this, ()| {
237            Ok(this.table().len())
238        });
239
240        // Pairs iterates the keys of the table.
241        // We use add_meta_function rather than add_meta_method here
242        // because we need to return `this` as the "state" parameter
243        // for use in a generic-for statement
244        methods.add_meta_function(MetaMethod::Pairs, move |lua, this: mlua::Value| {
245            // Maintain our own local idea of the control variable,
246            // as it is much cheaper and simpler to iterate based
247            // on skipping than to keep comparing keys
248            let mut idx = 0;
249
250            let iter_func =
251                lua.create_function_mut(
252                    move |lua, (state, _control): (UserDataRef<MemoizedTable>, mlua::Value)| {
253                        match state.table().iter().nth(idx) {
254                            Some((key, value)) => {
255                                idx += 1;
256                                let key = key.clone().as_lua(lua)?;
257                                let value = value.as_lua(lua)?;
258                                Ok((key, value))
259                            }
260                            None => Ok((mlua::Value::Nil, mlua::Value::Nil)),
261                        }
262                    },
263                )?;
264
265            // Return the iterator, state and control values.
266            // The state and control will be passed back into iter_func
267            // as the for-loop iterates.
268            // Control is Nil here because we track our own idx
269            // value in the iter_func closure.
270            Ok((mlua::Value::Function(iter_func), this, mlua::Value::Nil))
271        });
272    }
273}
274
275#[derive(Clone, Debug)]
276enum CacheEntry {
277    Null,
278    Single(CacheValue),
279    Multi(Vec<CacheValue>),
280}
281
282impl CacheEntry {
283    fn to_value(&self, lua: &Lua) -> mlua::Result<mlua::Value> {
284        match self {
285            Self::Null => Ok(mlua::Value::Nil),
286            Self::Single(value) => value.as_lua(lua),
287            Self::Multi(values) => {
288                let mut result = vec![];
289                for v in values {
290                    result.push(v.as_lua(lua)?);
291                }
292                result.into_lua(lua)
293            }
294        }
295    }
296
297    fn from_multi_value(lua: &Lua, multi: MultiValue) -> mlua::Result<Self> {
298        let mut values = multi.into_vec();
299        if values.is_empty() {
300            Ok(Self::Null)
301        } else if values.len() == 1 {
302            Ok(Self::Single(CacheValue::from_lua(
303                values.pop().unwrap(),
304                lua,
305            )?))
306        } else {
307            let mut cvalues = vec![];
308            for v in values.into_iter() {
309                cvalues.push(CacheValue::from_lua(v, lua)?);
310            }
311            Ok(Self::Multi(cvalues))
312        }
313    }
314}
315
316struct MemoizeCache {
317    params: MemoizeParams,
318    cache: Arc<LruCacheWithTtl<CacheKey, CacheEntry>>,
319}
320
321static CACHES: LazyLock<DashMap<String, MemoizeCache>> = LazyLock::new(DashMap::new);
322
323type CacheKey = (Option<ConfigEpoch>, String);
324
325fn get_cache_by_name(
326    name: &str,
327) -> Option<(Arc<LruCacheWithTtl<CacheKey, CacheEntry>>, Duration, bool)> {
328    CACHES.get(name).map(|item| {
329        (
330            item.cache.clone(),
331            item.params.ttl,
332            item.params.invalidate_with_epoch,
333        )
334    })
335}
336
337declare_metric! {
338/// How many times a memoize cache lookup was initiated for a given cache.
339///
340/// Redundant with the newer [lruttl_lookup_count](lruttl_lookup_count.md) metric.
341static CACHE_LOOKUP: CounterVec(
342        "memoize_cache_lookup_count",
343        &["cache_name"]);
344}
345
346declare_metric! {
347/// How many times a memoize cache lookup was a hit for a given cache.
348///
349/// Redundant with the newer [lruttl_hit_count](lruttl_hit_count.md) metric.
350static CACHE_HIT: CounterVec(
351        "memoize_cache_hit_count",
352        &["cache_name"]);
353}
354
355declare_metric! {
356/// How many times a memoize cache lookup was a miss for a given cache
357///
358/// Redundant with the newer [lruttl_miss_count](lruttl_miss_count.md) metric.
359static CACHE_MISS: CounterVec(
360        "memoize_cache_miss_count",
361        &["cache_name"]);
362}
363
364declare_metric! {
365/// How many times a memoize cache lookup resulted in performing the work to populate the entry
366///
367/// Redundant with the newer [lruttl_populated_count](lruttl_populated_count.md) metric.
368static CACHE_POPULATED: CounterVec(
369        "memoize_cache_populated_count",
370        &["cache_name"]);
371}
372
373/// Returns the call arguments as a JSON array with one entry per argument,
374/// preserving the argument count, unlike the collapsed JSON value that
375/// `multi_value_to_json_value` builds for the cache key.
376fn multi_value_to_json_args(lua: &Lua, multi: MultiValue) -> mlua::Result<Vec<serde_json::Value>> {
377    multi
378        .into_vec()
379        .into_iter()
380        .map(|v| from_lua_value(lua, v))
381        .collect()
382}
383
384/// Returns the name of the event handler the current call is running inside,
385/// or None when the call is running at top-level policy scope.
386fn calling_event_handler(lua: &Lua) -> Option<String> {
387    lua.globals().get::<String>("_KUMO_CURRENT_EVENT").ok()
388}
389
390fn multi_value_to_json_value(lua: &Lua, multi: MultiValue) -> mlua::Result<serde_json::Value> {
391    let mut values = multi.into_vec();
392    if values.is_empty() {
393        Ok(serde_json::Value::Null)
394    } else if values.len() == 1 {
395        from_lua_value(lua, values.pop().unwrap())
396    } else {
397        let mut jvalues = vec![];
398        for v in values.into_iter() {
399            jvalues.push(from_lua_value(lua, v)?);
400        }
401        Ok(serde_json::Value::Array(jvalues))
402    }
403}
404
405/// Looks up `key`, populating it on the calling task on a miss. Has no
406/// timeout of its own: a slow populate runs for as long as it takes and its
407/// result is still cached. If the caller is cancelled while the populate is
408/// running, the populate is aborted and nothing is cached.
409async fn populate_inline(
410    cache: &LruCacheWithTtl<CacheKey, CacheEntry>,
411    key: &CacheKey,
412    ttl: Duration,
413    lua: &Lua,
414    func: Function,
415    params: &MultiValue,
416    populate_counter: &Counter,
417) -> Result<ItemLookup<CacheEntry>, Arc<anyhow::Error>> {
418    cache
419        .get_or_try_insert(key, |_| ttl, async {
420            tracing::trace!("populate {key:?}");
421            populate_counter.inc();
422            let result: MultiValue = func.call_async(params.clone()).await?;
423            CacheEntry::from_multi_value(lua, result)
424        })
425        .await
426}
427
428/// Looks up `key`, populating it on a separate task on a miss. The populate
429/// outlives a cancelled caller and its result is still cached. A populate
430/// that exceeds `populate_timeout` is cancelled, cached as a failure, and
431/// reported here as an error.
432async fn populate_detached(
433    cache: &LruCacheWithTtl<CacheKey, CacheEntry>,
434    key: &CacheKey,
435    ttl: Duration,
436    cache_name: String,
437    registry_name: String,
438    args: Vec<serde_json::Value>,
439    populate_counter: Counter,
440) -> Result<ItemLookup<CacheEntry>, Arc<anyhow::Error>> {
441    if let Some(hit) = cache.lookup(key) {
442        return Ok(hit);
443    }
444
445    // We must load the config before this entry's populate permit is taken, in
446    // order to avoid a deadlock if the policy contains a file-scope lookup for
447    // the same cache entry as the one we're working to resolve here.
448    let config = load_config().await?;
449    // The populate task takes the context out of `handoff`. If the populate
450    // never runs because another caller satisfied the entry first, the context
451    // is still in `handoff` afterwards and goes back to the pool below.
452    let handoff = Arc::new(Mutex::new(Some(config)));
453
454    // populate_timeout reuses the sema timeout of the cache, set from
455    // MemoizeParams::populate_timeout. get_or_try_insert_detached hard-cancels
456    // the populate once it elapses: it caches a Failed entry with a 60-second
457    // TTL in place of a result, and the next lookup spawns a new populate.
458    let populate_timeout = cache.get_sema_timeout();
459    let make_fut = {
460        let handoff = handoff.clone();
461        move || async move {
462            let config = handoff
463                .lock()
464                .take()
465                .ok_or_else(|| anyhow::anyhow!("detached populate context already taken"))?;
466            let entry = {
467                let lua = config.lua()?;
468                // The function called here can be the newer policy's version
469                // if a reload re-ran the kumo.memoize call before this point.
470                // We still cache its result under the key built from
471                // epoch_at_start, not the newer epoch: we want a result
472                // produced under an older policy never mistaken for one that
473                // reflects the current policy, which is what tagging it with
474                // the newer epoch would do.
475                let func: Function = lua.named_registry_value(&registry_name).map_err(|_| {
476                    anyhow::anyhow!(
477                        "memoize populate function for cache {cache_name} is not registered in \
478                         a freshly loaded config context. This usually means the kumo.memoize \
479                         call does not run at top-level policy scope, where a config reload \
480                         would re-run it and re-register the function; it can also happen if a \
481                         policy reload removed the kumo.memoize call"
482                    )
483                })?;
484                let mut arg_vec = Vec::with_capacity(args.len());
485                for a in &args {
486                    arg_vec.push(lua.to_value_with(a, serialize_options())?);
487                }
488                populate_counter.inc();
489                let result: MultiValue = func.call_async(MultiValue::from_vec(arg_vec)).await?;
490                CacheEntry::from_multi_value(lua, result)?
491            };
492            config.put();
493            Ok::<_, anyhow::Error>(entry)
494        }
495    };
496    let result = cache
497        .get_or_try_insert_detached(key, move |_| ttl, make_fut, populate_timeout)
498        .await;
499    if let Some(config) = handoff.lock().take() {
500        config.put();
501    }
502    result
503}
504
505pub fn register(lua: &Lua) -> anyhow::Result<()> {
506    let kumo_mod = get_or_create_module(lua, "kumo")?;
507
508    kumo_mod.set(
509        "memoize",
510        lua.create_function(move |lua, (func, params): (mlua::Function, mlua::Value)| {
511            let params: MemoizeParams = from_lua_value(lua, params)?;
512
513            let cache_name = params.name.to_string();
514
515            if !lruttl::is_name_available(&cache_name) {
516                return Err(mlua::Error::external(format!(
517                    "cannot use name `{cache_name}` for a memoize cache, \
518                    as it collides with a built-in cache. \
519                    Suggestion: prefix your cache name with `user.` to \
520                    avoid conflicts with current and future caches."
521                )));
522            }
523
524            CACHES.remove_if(&params.name, |_k, item| {
525                let changed = item.params != params;
526                if changed {
527                    tracing::trace!("memoize parameters changed, replacing old cache {params:?}");
528                }
529                changed
530            });
531            CACHES.entry(cache_name.to_string()).or_insert_with(|| {
532                let cache = LruCacheWithTtl::new(cache_name.clone(), params.capacity);
533                if let Some(duration) = params.populate_timeout {
534                    cache.set_sema_timeout(duration);
535                }
536                cache.set_allow_stale_reads(params.allow_stale_reads);
537
538                MemoizeCache {
539                    params: params.clone(),
540                    cache: Arc::new(cache),
541                }
542            });
543
544            let lookup_counter = CACHE_LOOKUP
545                .get_metric_with_label_values(&[&cache_name])
546                .map_err(any_err)?;
547            let hit_counter = CACHE_HIT
548                .get_metric_with_label_values(&[&cache_name])
549                .map_err(any_err)?;
550            let miss_counter = CACHE_MISS
551                .get_metric_with_label_values(&[&cache_name])
552                .map_err(any_err)?;
553            let populate_counter = CACHE_POPULATED
554                .get_metric_with_label_values(&[&cache_name])
555                .map_err(any_err)?;
556            let retry_on_populate_timeout = params.retry_on_populate_timeout;
557            let allow_stale_reads = params.allow_stale_reads;
558            // The populate mode, fixed once here for the life of this wrapper.
559            let detached = match params.detached {
560                Some(true) => {
561                    if let Some(event) = calling_event_handler(lua) {
562                        return Err(mlua::Error::external(format!(
563                            "kumo.memoize cache `{cache_name}` sets `detached = true`, but is \
564                            being called from within the `{event}` event handler. A detached \
565                            populate reloads the policy to re-establish the populate function, \
566                            and reloading runs only top-level policy code, not event handlers. \
567                            Move this kumo.memoize call to top-level policy scope, or set \
568                            `detached = false` if the populate is fast enough to run inline."
569                        )));
570                    }
571                    true
572                }
573                Some(false) => false,
574                None => calling_event_handler(lua).is_none(),
575            };
576            let detached_explicit = params.detached;
577
578            let registry_name = format!("kumo-memoize-fn.{cache_name}");
579            lua.set_named_registry_value(&registry_name, func.clone())?;
580
581            let func_ref = lua.create_registry_value(func)?;
582
583            lua.create_async_function(move |lua, params: MultiValue| {
584                let cache_name = cache_name.clone();
585                let registry_name = registry_name.clone();
586                let func = lua.registry_value::<mlua::Function>(&func_ref);
587                let lookup_counter = lookup_counter.clone();
588                let hit_counter = hit_counter.clone();
589                let miss_counter = miss_counter.clone();
590                let populate_counter = populate_counter.clone();
591                async move {
592                    lookup_counter.inc();
593                    let key = multi_value_to_json_value(&lua, params.clone())?;
594
595                    let func = func?;
596
597                    let policy_loading = config::is_policy_loading();
598                    if policy_loading && detached_explicit == Some(true) {
599                        return Err(mlua::Error::external(format!(
600                            "kumo.memoize cache `{cache_name}` sets `detached = true`, but the \
601                            cached function is being called at file scope while the policy is \
602                            still loading. A detached populate reloads the policy to \
603                            re-establish the populate function, which would re-enter the \
604                            in-progress load and deadlock. Call this cached function from an \
605                            event handler instead, or set `detached = false` if the populate is \
606                            fast enough to run inline."
607                        )));
608                    }
609                    let run_detached = detached && !policy_loading;
610
611                    let mut last_failure = None;
612
613                    for _attempt in 0..3 {
614                        // We use the epoch from the start of the lookup as part
615                        // of the cache key. If the epoch changes while we are in
616                        // the middle of computing this value then subsequent calls
617                        // through to the cached function will see the newer epoch
618                        // and encounter a cache miss. This prevents a race condition
619                        // poisoning the cache with a stale value during an epoch
620                        // bump. The caller will still observe the stale value, so
621                        // ultimately should have some accommodation for detecting
622                        // the epoch change and retrying their call through here,
623                        // if it is important to not see a stale value.
624                        let epoch_at_start = get_current_epoch();
625
626                        let (cache, ttl, invalidate_with_epoch) = get_cache_by_name(&cache_name)
627                            .ok_or_else(|| anyhow::anyhow!("cache is somehow undefined!?"))
628                            .map_err(any_err)?;
629
630                        let epoch_key = if invalidate_with_epoch && !allow_stale_reads {
631                            Some(epoch_at_start)
632                        } else {
633                            None
634                        };
635                        let key = serde_json::to_string(&key).map_err(any_err)?;
636                        let key = (epoch_key, key);
637
638                        let value_result = if run_detached {
639                            let args = multi_value_to_json_args(&lua, params.clone())?;
640                            populate_detached(
641                                &cache,
642                                &key,
643                                ttl,
644                                cache_name.clone(),
645                                registry_name.clone(),
646                                args,
647                                populate_counter.clone(),
648                            )
649                            .await
650                        } else {
651                            populate_inline(
652                                &cache,
653                                &key,
654                                ttl,
655                                &lua,
656                                func.clone(),
657                                &params,
658                                &populate_counter,
659                            )
660                            .await
661                        };
662
663                        match value_result {
664                            Ok(lookup) => {
665                                if lookup.is_fresh {
666                                    miss_counter.inc();
667                                } else {
668                                    hit_counter.inc();
669                                }
670                                return lookup.item.to_value(&lua);
671                            }
672                            Err(err) => {
673                                tracing::error!("{cache_name} {key:?} failed: {err:#}");
674                                let error = format!("{err:#}");
675                                // Retry an abandoned populate even when
676                                // retry_on_populate_timeout is unset: the cache
677                                // is still empty for this key.
678                                let abandoned = err.downcast_ref::<PopulateAbandoned>().is_some();
679                                if !retry_on_populate_timeout && !abandoned {
680                                    return Err(mlua::Error::external(error));
681                                }
682                                last_failure.replace(error);
683                            }
684                        }
685                    }
686
687                    Err(mlua::Error::external(
688                        last_failure.expect("last_failure to always be set in loop above"),
689                    ))
690                }
691            })
692        })?,
693    )?;
694
695    Ok(())
696}
697
698#[cfg(test)]
699mod test {
700    use super::*;
701    use mlua::UserDataMethods;
702    use std::sync::atomic::{AtomicUsize, Ordering};
703
704    #[tokio::test]
705    async fn test_memoize() {
706        let lua = Lua::new();
707        register(&lua).unwrap();
708
709        let call_count = Arc::new(AtomicUsize::new(0));
710
711        let globals = lua.globals();
712        let counter = Arc::clone(&call_count);
713        globals
714            .set(
715                "do_thing",
716                lua.create_function(move |_lua, _: ()| {
717                    let count = counter.fetch_add(1, Ordering::SeqCst);
718                    Ok(count)
719                })
720                .unwrap(),
721            )
722            .unwrap();
723
724        let result: usize = lua
725            .load(
726                r#"
727            local kumo = require 'kumo';
728            -- make cached_do_thing a global for use in the expiry test below
729            cached_do_thing = kumo.memoize(do_thing, {
730                ttl = "1s",
731                capacity = 4,
732                name = "test_memoize_do_thing",
733                -- bare test Lua has no policy for load_config to reload, so
734                -- exercise the inline populate
735                detached = false,
736            })
737            return cached_do_thing() + cached_do_thing() + cached_do_thing()
738        "#,
739            )
740            .eval_async()
741            .await
742            .unwrap();
743
744        assert_eq!(result, 0);
745        assert_eq!(call_count.load(Ordering::SeqCst), 1);
746
747        // And confirm that expiry works
748        tokio::time::sleep(tokio::time::Duration::from_secs(2)).await;
749
750        let result: usize = lua
751            .load(
752                r#"
753            return cached_do_thing()
754        "#,
755            )
756            .eval()
757            .unwrap();
758
759        assert_eq!(result, 1);
760        assert_eq!(call_count.load(Ordering::SeqCst), 2);
761    }
762
763    #[tokio::test]
764    async fn test_memoize_rust() {
765        let lua = Lua::new();
766        register(&lua).unwrap();
767
768        let call_count = Arc::new(AtomicUsize::new(0));
769
770        #[derive(Clone)]
771        struct Foo {
772            value: usize,
773        }
774
775        impl UserData for Foo {
776            fn add_methods<M: UserDataMethods<Self>>(methods: &mut M) {
777                Memoized::impl_memoize(methods);
778                methods.add_method("get_value", move |_lua, this, _: ()| Ok(this.value));
779            }
780        }
781
782        let globals = lua.globals();
783        let counter = Arc::clone(&call_count);
784        globals
785            .set(
786                "make_foo",
787                lua.create_function(move |_lua, _: ()| {
788                    let count = counter.fetch_add(1, Ordering::SeqCst);
789                    Ok(Foo { value: count })
790                })
791                .unwrap(),
792            )
793            .unwrap();
794
795        let result: usize = lua
796            .load(
797                r#"
798            local kumo = require 'kumo';
799            local cached_make_foo = kumo.memoize(make_foo, {
800                ttl = "1s",
801                capacity = 4,
802                name = "test_memoize_make_foo",
803                -- bare test Lua has no policy for load_config to reload, so
804                -- exercise the inline populate
805                detached = false,
806            })
807            return cached_make_foo():get_value() +
808                   cached_make_foo():get_value() +
809                   cached_make_foo():get_value()
810        "#,
811            )
812            .eval()
813            .unwrap();
814
815        assert_eq!(result, 0);
816        assert_eq!(call_count.load(Ordering::SeqCst), 1);
817    }
818
819    #[tokio::test]
820    #[test_log::test]
821    async fn test_memoize_blocked() {
822        use std::sync::Mutex;
823        use tokio::sync::Notify;
824
825        let call_count = Arc::new(AtomicUsize::new(0));
826        let notify = Arc::new(Notify::new());
827        let shared_notify = Arc::new(Mutex::new(Some(Arc::clone(&notify))));
828
829        async fn setup_lua(
830            call_count: &Arc<AtomicUsize>,
831            notify: Arc<Mutex<Option<Arc<Notify>>>>,
832        ) -> Lua {
833            let lua = Lua::new();
834            register(&lua).unwrap();
835            let globals = lua.globals();
836            let counter = Arc::clone(&call_count);
837
838            fn take_notify(n: &Arc<Mutex<Option<Arc<Notify>>>>) -> Option<Arc<Notify>> {
839                n.lock().unwrap().take()
840            }
841
842            globals
843                .set(
844                    "do_thing",
845                    lua.create_async_function(move |_lua, _: ()| {
846                        let counter = counter.clone();
847                        let notify = notify.clone();
848                        async move {
849                            eprintln!("do_thing called!");
850                            match dbg!(take_notify(&notify)) {
851                                Some(notify) => {
852                                    eprintln!("do_thing: wait for notify");
853                                    notify.notified().await;
854                                    eprintln!("notified!");
855                                }
856                                None => {
857                                    eprintln!("do_thing: sleeping");
858                                    tokio::time::sleep(Duration::from_secs(1)).await;
859                                    eprintln!("do_thing: slept");
860                                }
861                            };
862                            eprintln!("do_thing: increment");
863                            let count = counter.fetch_add(1, Ordering::SeqCst);
864                            Ok(count)
865                        }
866                    })
867                    .unwrap(),
868                )
869                .unwrap();
870
871            let init = r#"
872            local kumo = require 'kumo';
873            -- make cached_do_thing a global for use in the expiry test below
874            cached_do_thing = kumo.memoize(do_thing, {
875                ttl = "1s",
876                capacity = 4,
877                name = "test_memoize_do_thing",
878                populate_timeout = "2s",
879                -- bare test Lua has no policy for load_config to reload, so
880                -- exercise the inline populate
881                detached = false,
882            })
883        "#;
884
885            let () = lua.load(init).eval_async().await.unwrap();
886            lua
887        }
888
889        let lua = setup_lua(&call_count, shared_notify.clone()).await;
890        async fn do_thing(lua: Lua) -> mlua::Result<usize> {
891            lua.load("return cached_do_thing()").eval_async().await
892        }
893
894        // Set up a future that will get far enough to own the lookup,
895        // but that won't complete until we notify it to do so.
896        eprintln!("spawning first call to do_thing");
897        let first_future = tokio::spawn(do_thing(lua));
898        // Let it progress to await on the notifier
899        tokio::task::yield_now().await;
900
901        // Now setup a second call; we expect this one to time out
902        // because the first one owns the lookup
903        let lua = setup_lua(&call_count, shared_notify.clone()).await;
904        eprintln!("second call to do_thing");
905
906        let res = do_thing(lua).await;
907        eprintln!("second_future is done!");
908        let error = res.unwrap_err().to_string();
909        assert!(
910            error.contains(
911                "timed out after 2s on semaphore acquire while waiting for cache to populate"
912            ),
913            "error: {error}"
914        );
915
916        // The third call will succeed because we've de-coupled the
917        // original lookup from the herd protection
918        eprintln!("third call to do_thing");
919        let lua = setup_lua(&call_count, shared_notify.clone()).await;
920        let result = do_thing(lua).await.unwrap();
921        assert_eq!(result, 0);
922
923        // Now wake up the original future and verify what it returns
924        notify.notify_one();
925        assert_eq!(first_future.await.unwrap().unwrap(), 1);
926    }
927}