path: root/internal/calendar/transfer_plan_cache.go

package calendar

import (
	"container/list"
	"crypto/sha256"
	"io"
	"sort"
	"sync"
	"time"
)

// efTransferPlanCacheCap bounds the memoised EF transfer-plan cache (below)
// so a long-running gomobile process cannot grow it without bound as a user
// scrolls through many years -- capacity 8417 (the whole 1583-9999 domain)
// would be a real, if small, leak risk over a long enough session; 64 keeps
// memory negligible (each entry is a handful of time.Time values) while
// still giving a warm cache for the realistic access pattern, a week/month
// view moving through nearby dates.
const efTransferPlanCacheCap = 64

// efTransferPlanCacheKey is everything efTransferPlan's result -- and, since
// ef_transfer_plan_cache.go v2, efOccupancyIndex's result -- actually depend
// on, established by reading efTransferPlan, celebrationDate, temporalEF and
// resolveDate rather than assumed. Both the plan and the occupancy index are
// pure functions of exactly these three inputs (see efOccupancyIndex's own
// doc comment for occupancy specifically), so one key correctly covers both:
//
//   - year: efTransferPlan's own first argument (Easter, the transfer
//     window, every celebrationDate call).
//   - sel: passed through to celebrationDate on every candidate, which
//     currently ignores it (resolveDate never reads its sel parameter) --
//     so it is a dead dependency TODAY. It is still part of the key: the
//     parameter exists on the signature for a reason, and keying on it now
//     costs nothing (Selection is four small strings) while protecting
//     against a future change that makes EF date resolution
//     Selection-sensitive silently poisoning a cache that never accounted
//     for it.
//   - a content hash of merged: efTransferPlan's real data dependency.
//     merged is a map -- not itself comparable, so cannot be a map key
//     field -- and mergeLayers rebuilds a brand-new map with fresh Go map
//     iteration order on every call even when the underlying layers are
//     unchanged, so identity/pointer comparison cannot be used either only
//     a hash of merged's actual content is both correct (invalidates
//     whenever the content genuinely differs -- a user overlay edited, a
//     different layer stack) and cache-friendly (hits whenever it does not,
//     regardless of which Layer objects or map iteration produced it). See
//     hashMergedForPlan for what is and is not hashed.
type efTransferPlanCacheKey struct {
	year int
	sel  Selection
	hash [32]byte
}

// efTransferPlanCacheEntry is one memoised (plan, occupancy index) pair,
// doubling as the LRU list's payload so eviction and lookup share one map.
// The two are cached together because they are built from the same data in
// one pass and share the same cache key -- see efTransferPlanCacheKey.
type efTransferPlanCacheEntry struct {
	key       efTransferPlanCacheKey
	plan      map[string]time.Time
	occupancy efOccupancyIndex
}

// efTransferPlanCache is a small, bounded, thread-safe LRU in front of
// efTransferPlan. gomobile may call Day/Days in from multiple goroutines, so
// the map and list are guarded by one mutex; efTransferPlan itself (the
// expensive part) runs OUTSIDE the lock so concurrent misses on different
// keys do not serialise behind each other -- see efTransferPlanCached.
var efTransferPlanCache = struct {
	mu      sync.Mutex
	entries map[efTransferPlanCacheKey]*list.Element
	order   *list.List // front = most recently used
}{entries: map[efTransferPlanCacheKey]*list.Element{}, order: list.New()}

// efOccupancyEntry is one merged entry's slug and rank, indexed under its own
// ORIGINAL (untransferred) date -- see efOccupancyIndex.
type efOccupancyEntry struct {
	slug string
	rank Rank
}

// efOccupancyIndex answers exactly the question computeEF's old
// occupiedByRank closure scanned all of merged for on every single call:
// "does some entry other than exceptSlug, with a rank `allowed` accepts,
// resolve to date d this year?" -- but as a precomputed lookup instead of a
// fresh O(len(merged)) scan.
//
// BE PRECISE ABOUT WHAT "OCCUPIED" DEPENDS ON, because this is the question
// that decides whether precomputing it is safe: an entry's ORIGINAL date
// (buildCelebration + celebrationDate, exactly as this index computes it) is
// a pure function of (merged content, year, sel) alone -- it never considers
// whether that entry has since been TRANSFERRED (celebrationDate calls
// resolveDate directly; nothing about transfer resolution feeds into it) and
// never depends on `date`, the day computeEF happens to be resolving. That
// is what makes one index, built once per (year, merged, sel) and reused for
// every day and every candidate resolved against it, correct.
//
// This is a DIFFERENT question from efTransferPlan's own `claimed` map,
// which tracks which TARGET days a transfer walk has already assigned
// DURING one planning pass -- claimed genuinely mutates as planning
// proceeds and has no meaning outside that single call, so it is (correctly)
// still computed fresh inside efTransferPlan every time, never cached here.
// Conflating the two -- treating "is some entry's ORIGINAL date d" as if it
// captured "has some transfer already CLAIMED d" -- would be the exact
// silent-wrong-answer failure mode this comment exists to rule out; they are
// checked as three independent conditions everywhere they are used
// together (see efTransferPlan's own forward-walk loop).
type efOccupancyIndex map[string][]efOccupancyEntry // "2006-01-02" -> entries

// buildEFOccupancyIndex computes the index in one O(len(merged)) pass.
func buildEFOccupancyIndex(merged map[string]RawCelebration, year int, sel Selection) efOccupancyIndex {
	idx := efOccupancyIndex{}
	for slug, rc := range merged {
		cel := buildCelebration(slug, rc)
		when, ok := celebrationDate(cel, year, sel)
		if !ok {
			continue
		}
		key := when.Format("2006-01-02")
		idx[key] = append(idx[key], efOccupancyEntry{slug: slug, rank: cel.Rank})
	}
	return idx
}

// occupied reports whether some entry other than exceptSlug at date d has a
// rank allowed accepts -- computeEF's former occupiedByRank closure's exact
// semantics, read from the precomputed index instead of a fresh scan. Safe
// to call concurrently: idx is never mutated after buildEFOccupancyIndex
// returns it (Go's map type permits unlimited concurrent reads with no
// concurrent write).
func (idx efOccupancyIndex) occupied(d time.Time, exceptSlug string, allowed func(Rank) bool) bool {
	for _, e := range idx[d.Format("2006-01-02")] {
		if e.slug == exceptSlug {
			continue
		}
		if allowed(e.rank) {
			return true
		}
	}
	return false
}

// efTransferPlanCached is (efTransferPlan, buildEFOccupancyIndex), memoised
// together by (year, sel, merged content). It is safe and correct to share
// across every caller in the process: two calls with the SAME key are, by
// construction of the key, calls efTransferPlan/buildEFOccupancyIndex
// themselves would resolve identically (same year, same Selection, same
// sanctoral content), so returning a cached result changes nothing about
// what is computed -- only when. The returned plan is a fresh copy per call
// (clonePlan), never the cached instance, so no caller can mutate shared
// cache state even though computeEF's own use of it is read-only today. The
// occupancy index is returned WITHOUT copying (unlike plan, it can hold one
// entry per merged slug, up to ~330 on shipped data, so copying it on every
// call -- most of them hits -- would give back a real slice of the win this
// exists to capture); this is safe only because it is genuinely immutable
// after construction (see efOccupancyIndex's own doc comment) and no code
// anywhere writes to a returned index.
func efTransferPlanCached(year int, merged map[string]RawCelebration, sel Selection) (map[string]time.Time, efOccupancyIndex) {

	key := efTransferPlanCacheKey{year: year, sel: sel, hash: hashMergedForPlan(merged)}

	efTransferPlanCache.mu.Lock()
	if el, ok := efTransferPlanCache.entries[key]; ok {
		efTransferPlanCache.order.MoveToFront(el)
		entry := el.Value.(*efTransferPlanCacheEntry)
		plan, occ := entry.plan, entry.occupancy
		efTransferPlanCache.mu.Unlock()
		return clonePlan(plan), occ
	}
	efTransferPlanCache.mu.Unlock()

	// Compute outside the lock: building the index and the plan is the
	// expensive work this cache exists to avoid repeating, and holding the
	// mutex across it would serialise every concurrent miss on DIFFERENT
	// keys, not just protect the shared map/list.
	occ := buildEFOccupancyIndex(merged, year, sel)
	plan := efTransferPlan(year, merged, sel, occ)

	efTransferPlanCache.mu.Lock()
	defer efTransferPlanCache.mu.Unlock()
	if el, ok := efTransferPlanCache.entries[key]; ok {
		// Lost a race: another goroutine populated this exact key while we
		// were computing our own copy unlocked. Same key => same result by
		// construction, so keep the existing entry and just bump recency.
		efTransferPlanCache.order.MoveToFront(el)
		entry := el.Value.(*efTransferPlanCacheEntry)
		return clonePlan(entry.plan), entry.occupancy
	}
	el := efTransferPlanCache.order.PushFront(&efTransferPlanCacheEntry{key: key, plan: plan, occupancy: occ})
	efTransferPlanCache.entries[key] = el
	if efTransferPlanCache.order.Len() > efTransferPlanCacheCap {
		oldest := efTransferPlanCache.order.Back()
		efTransferPlanCache.order.Remove(oldest)
		delete(efTransferPlanCache.entries, oldest.Value.(*efTransferPlanCacheEntry).key)
	}
	return clonePlan(plan), occ
}

func clonePlan(plan map[string]time.Time) map[string]time.Time {
	out := make(map[string]time.Time, len(plan))
	for k, v := range plan {
		out[k] = v
	}
	return out
}

// hashMergedForPlan hashes merged's full content deterministically. Go's map
// iteration order is randomised per-process, so slugs (and, within each
// entry, its Fields and Variant keys) are sorted before hashing -- the same
// logical content always hashes identically, regardless of which Layer
// stack produced it or what order ranging over it visits entries.
//
// EVERY field of every entry is hashed, not just the ones the plan's or the
// occupancy index's own read paths happen to touch today (Rank, Date via
// celebrationDate). efOccupancyIndex indexes ALL of merged at every rank
// (not just class-1/2 -- occ.occupied's `allowed` parameter is arbitrary),
// and which entries even qualify as class-1 in the first place is ITSELF
// computed from this data (buildCelebration's "rank" field) -- so hashing
// only a subset of fields would risk exactly the silent-stale-cache bug this
// function exists to prevent: a user overlay that changes, say, a
// "suppress" or an unrelated feast's rank would not change the hash, and a
// stale plan or index would keep being served.
func hashMergedForPlan(merged map[string]RawCelebration) [32]byte {
	slugs := make([]string, 0, len(merged))
	for slug := range merged {
		slugs = append(slugs, slug)
	}
	sort.Strings(slugs)

	h := sha256.New()
	for _, slug := range slugs {
		rc := merged[slug]
		io.WriteString(h, "slug=")
		io.WriteString(h, slug)
		h.Write([]byte{0})
		writeSortedFields(h, rc.Fields)
		variants := make([]string, 0, len(rc.Variants))
		for v := range rc.Variants {
			variants = append(variants, v)
		}
		sort.Strings(variants)
		for _, v := range variants {
			io.WriteString(h, "variant=")
			io.WriteString(h, v)
			h.Write([]byte{0})
			writeSortedFields(h, rc.Variants[v])
		}
		h.Write([]byte{1}) // record separator, so "ab"+"c" cannot collide with "a"+"bc"
	}
	var sum [32]byte
	copy(sum[:], h.Sum(nil))
	return sum
}

// writeSortedFields writes fields into h as sorted "key=value\x00" records
// (see hashMergedForPlan).
func writeSortedFields(h io.Writer, fields map[string]string) {
	keys := make([]string, 0, len(fields))
	for k := range fields {
		keys = append(keys, k)
	}
	sort.Strings(keys)
	for _, k := range keys {
		io.WriteString(h, k)
		h.Write([]byte{'='})
		io.WriteString(h, fields[k])
		h.Write([]byte{0})
	}
}