memo.gno

  1// Package memo provides a simple memoization utility to cache function results.
  2//
  3// The package offers a Memoizer type that can cache function results based on keys,
  4// with optional validation of cached values. This is useful for expensive computations
  5// that need to be cached and potentially invalidated based on custom conditions.
  6//
  7// It is the B+ tree successor to [gno.land/p/moul/memo/v0] (which is backed by
  8// an AVL tree): a bump to v3 because the backing data structure — and thus the
  9// on-chain storage layout — changed. The exported API is identical to v2
 10// (New/Memoize/MemoizeWithValidator/Invalidate/Clear/Size). A B+ tree packs
 11// many entries per persisted node, so it costs materially less storage and gas
 12// per cached entry — prefer v3 when the cache is part of persisted realm state.
 13//
 14// Because the B+ tree backing mutates in place (the AVL backing was
 15// copy-on-write), do NOT invalidate or add entries to the same Memoizer from
 16// inside a callback that is iterating it, and do NOT copy a non-zero Memoizer
 17// by value.
 18//
 19// /!\ Important Warning for Gno Usage:
 20// In Gno, storage updates only persist during transactions. This means:
 21//   - Cache entries created during queries will NOT persist
 22//   - Creating cache entries during queries will actually decrease performance
 23//     as it wastes resources trying to save data that won't be saved
 24//
 25// Best Practices:
 26// - Use this pattern in transaction-driven contexts rather than query/render scenarios
 27// - Consider controlled cache updates, e.g., by specific accounts (like oracles)
 28// - Ideal for cases where cache updates happen every N blocks or on specific events
 29// - Carefully evaluate if caching will actually improve performance in your use case
 30//
 31// Basic usage example:
 32//
 33//	m := memo.New()
 34//
 35//	// Cache expensive computation
 36//	result := m.Memoize("key", func() any {
 37//	    // expensive operation
 38//	    return "computed-value"
 39//	})
 40//
 41//	// Subsequent calls with same key return cached result
 42//	result = m.Memoize("key", func() any {
 43//	    // function won't be called, cached value is returned
 44//	    return "computed-value"
 45//	})
 46//
 47// Example with validation:
 48//
 49//	type TimestampedValue struct {
 50//	    Value     string
 51//	    Timestamp time.Time
 52//	}
 53//
 54//	m := memo.New()
 55//
 56//	// Cache value with timestamp
 57//	result := m.MemoizeWithValidator(
 58//	    "key",
 59//	    func() any {
 60//	        return TimestampedValue{
 61//	            Value:     "data",
 62//	            Timestamp: time.Now(),
 63//	        }
 64//	    },
 65//	    func(cached any) bool {
 66//	        // Validate that the cached value is not older than 1 hour
 67//	        if tv, ok := cached.(TimestampedValue); ok {
 68//	            return time.Since(tv.Timestamp) < time.Hour
 69//	        }
 70//	        return false
 71//	    },
 72//	)
 73package memo
 74
 75import (
 76	"gno.land/p/nt/bptree/v0"
 77	"gno.land/p/nt/ufmt/v0"
 78)
 79
 80// keyString derives a stable string key from an arbitrary value. Keys are
 81// compared by their string representation, mirroring the previous ordering
 82// behavior.
 83func keyString(key any) string {
 84	return ufmt.Sprintf("%v", key)
 85}
 86
 87// Memoizer is a structure to handle memoization of function results.
 88type Memoizer struct {
 89	cache *bptree.BPTree
 90}
 91
 92// New creates a new Memoizer instance.
 93func New() *Memoizer {
 94	return &Memoizer{
 95		cache: bptree.NewBPTree32(),
 96	}
 97}
 98
 99// Memoize ensures the result of the given function is cached for the specified key.
100func (m *Memoizer) Memoize(key any, fn func() any) any {
101	k := keyString(key)
102	if m.cache.Has(k) {
103		return m.cache.Get(k)
104	}
105
106	value := fn()
107	m.cache.Set(k, value)
108	return value
109}
110
111// MemoizeWithValidator ensures the result is cached and valid according to the validator function.
112func (m *Memoizer) MemoizeWithValidator(key any, fn func() any, isValid func(any) bool) any {
113	k := keyString(key)
114	if m.cache.Has(k) {
115		cached := m.cache.Get(k)
116		if isValid(cached) {
117			return cached
118		}
119	}
120
121	value := fn()
122	m.cache.Set(k, value)
123	return value
124}
125
126// Invalidate removes the cached value for the specified key.
127func (m *Memoizer) Invalidate(key any) {
128	m.cache.Remove(keyString(key))
129}
130
131// Clear clears all cached values.
132func (m *Memoizer) Clear() {
133	m.cache = bptree.NewBPTree32()
134}
135
136// Size returns the number of items currently in the cache.
137func (m *Memoizer) Size() int {
138	return m.cache.Size()
139}