diff options
| -rw-r--r-- | internal/calendar/calendar.go | 9 | ||||
| -rw-r--r-- | internal/calendar/transfer_plan_cache.go | 187 | ||||
| -rw-r--r-- | internal/calendar/transfer_plan_cache_test.go | 191 |
3 files changed, 386 insertions, 1 deletions
diff --git a/internal/calendar/calendar.go b/internal/calendar/calendar.go index d918547..00048b7 100644 --- a/internal/calendar/calendar.go +++ b/internal/calendar/calendar.go @@ -67,7 +67,14 @@ func computeEF(date time.Time, sel Selection, layers []Layer) LiturgicalDay { // RG 97/98: the year's impeded I-class transfers are resolved as a set, // not one at a time, so two feasts impeded by the same early Easter cannot // both claim the same free day and lose one of themselves. - plan := efTransferPlan(year, merged, sel, occ1, occ1Or2) + // + // efTransferPlan is pure in (year, merged content, sel) and identical for + // every day of the year it is asked about -- computeEF runs once PER DAY, + // so a multi-day view (mobile.Days's week, a month view) was rebuilding + // it from scratch on every single one. efTransferPlanCached memoises it; + // see transfer_plan_cache.go for the cache key and why each of its three + // parts is load-bearing. + plan := efTransferPlanCached(year, merged, sel, occ1, occ1Or2) cands := []candidate{{Cel: td.Cel, Temporal: true, Season: td.Season, Sunday: td.Sunday}} for slug, rc := range merged { cel := buildCelebration(slug, rc) diff --git a/internal/calendar/transfer_plan_cache.go b/internal/calendar/transfer_plan_cache.go new file mode 100644 index 0000000..fdf62f7 --- /dev/null +++ b/internal/calendar/transfer_plan_cache.go @@ -0,0 +1,187 @@ +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 actually +// depends on, established by reading efTransferPlan, celebrationDate, +// temporalEF and resolveDate rather than assumed: +// +// - 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, doubling as the LRU list's +// payload so eviction and lookup share one map. +type efTransferPlanCacheEntry struct { + key efTransferPlanCacheKey + plan map[string]time.Time +} + +// 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()} + +// efTransferPlanCached is efTransferPlan, memoised 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 itself 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 map is a fresh +// copy per call (clonePlan), never the cached instance itself, so no caller +// can mutate shared cache state even though computeEF's own use of the +// result is read-only today. +func efTransferPlanCached(year int, merged map[string]RawCelebration, sel Selection, + occupiedByClass1, occupiedByClass1Or2 func(time.Time, string) bool) map[string]time.Time { + + key := efTransferPlanCacheKey{year: year, sel: sel, hash: hashMergedForPlan(merged)} + + efTransferPlanCache.mu.Lock() + if el, ok := efTransferPlanCache.entries[key]; ok { + efTransferPlanCache.order.MoveToFront(el) + plan := el.Value.(*efTransferPlanCacheEntry).plan + efTransferPlanCache.mu.Unlock() + return clonePlan(plan) + } + efTransferPlanCache.mu.Unlock() + + // Compute outside the lock: efTransferPlan is the expensive call 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. + plan := efTransferPlan(year, merged, sel, occupiedByClass1, occupiedByClass1Or2) + + 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) + return clonePlan(el.Value.(*efTransferPlanCacheEntry).plan) + } + el := efTransferPlanCache.order.PushFront(&efTransferPlanCacheEntry{key: key, plan: plan}) + 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) +} + +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 efTransferPlan's +// own read path happens to touch today (Rank, Date via celebrationDate). +// occupiedByClass1/Or2 (closures over merged, passed in by computeEF) scan +// ALL of merged looking for competing entries of any rank, 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 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}) + } +} diff --git a/internal/calendar/transfer_plan_cache_test.go b/internal/calendar/transfer_plan_cache_test.go new file mode 100644 index 0000000..6b3b48b --- /dev/null +++ b/internal/calendar/transfer_plan_cache_test.go @@ -0,0 +1,191 @@ +package calendar_test + +// Tests for the memoised EF transfer plan (transfer_plan_cache.go). These +// live in the external test package (calendar_test), exercising the real +// tridentine sanctoral data through the public Compute entry point, the same +// style precedence_ef_repro_test.go already uses -- the risk this cache +// introduces is entirely about whether the CACHE KEY captures every real +// input, which can only be demonstrated by varying an input through Compute +// and checking the observed office actually changes, not by testing the +// cache's internals in isolation. + +import ( + "sync" + "testing" + "time" + + "github.com/lukaszkasprzak/lectio/internal/caldata" + "github.com/lukaszkasprzak/lectio/internal/calendar" +) + +// TestEFTransferPlanCacheInvalidatesOnOverlay is THE bad-key test: it warms +// the memoised plan for (2008, EF, the shipped calendar) across a whole +// week -- mobile.Days's own access pattern -- then asks the SAME year +// through a layer stack with ONE user overlay added (suppressing the +// Annunciation) and asserts the observed office on 31 March and 1 April +// CHANGES accordingly. +// +// What is varied: the layer stack / merged sanctoral content (a user +// overlay), holding year and Selection fixed. This is deliberately not a +// synthetic scenario: with the Annunciation present, its RG 96(a) proper +// seat (the Monday after Low Sunday, RG 97/98) forces St Joseph -- also +// impeded that year -- to walk one day further, to 1 April +// (TestEFTwoTransfersDoNotCollide already pins this). Suppress the +// Annunciation and it no longer claims that Monday, so Joseph lands ON it, +// 31 March, and 1 April reverts to an ordinary feria. Verified empirically +// against the pre-cache code before this test was written (both outcomes +// reproduced exactly as asserted below). +// +// A cache keyed on year alone -- or on year+sel without the merged content +// -- would serve 2008's BASE-CALENDAR plan back for the overlaid query too, +// since both share every other key component; this test fails loudly if +// that happens (it would see 1 April still reporting Joseph, and 31 March +// still reporting the Annunciation, from the first, unrelated warm-up). +func TestEFTransferPlanCacheInvalidatesOnOverlay(t *testing.T) { + sel := calendar.DefaultSelection() + sel.Form = "old" + base := caldata.Tridentine() + baseLayers := []calendar.Layer{base} + + compute := func(layers []calendar.Layer, date string) string { + d, err := time.Parse("2006-01-02", date) + if err != nil { + t.Fatalf("bad test date %q: %v", date, err) + } + return calendar.Compute(d.UTC(), sel, layers).Observed.Slug + } + + // Warm the cache for (2008, sel, base-only-hash) across a whole week, + // exactly like mobile.Days resolving seven consecutive dates against the + // same Prepared layer stack. + for _, date := range []string{ + "2008-03-26", "2008-03-27", "2008-03-28", "2008-03-29", + "2008-03-30", "2008-03-31", "2008-04-01", "2008-04-02", + } { + compute(baseLayers, date) + } + if got := compute(baseLayers, "2008-03-31"); got != "annunciation-of-the-blessed-virgin-mary" { + t.Fatalf("baseline 2008-03-31 = %q, want annunciation-of-the-blessed-virgin-mary", got) + } + if got := compute(baseLayers, "2008-04-01"); got != "joseph-spouse-of-the-bl-virgin-mary" { + t.Fatalf("baseline 2008-04-01 = %q, want joseph-spouse-of-the-bl-virgin-mary", got) + } + + // Same year, same Selection, ONE overlay layer added: suppress the + // Annunciation. If the cache key omitted the sanctoral content, these + // two calls would silently return the baseline plan warmed above. + overlay := calendar.Layer{ID: "user", Cels: map[string]calendar.RawCelebration{ + "annunciation-of-the-blessed-virgin-mary": { + Fields: map[string]string{"suppress": "true"}, + Variants: map[string]map[string]string{}, + }, + }} + overlaid := []calendar.Layer{base, overlay} + + if got := compute(overlaid, "2008-03-31"); got != "joseph-spouse-of-the-bl-virgin-mary" { + t.Errorf("overlaid 2008-03-31 = %q, want joseph-spouse-of-the-bl-virgin-mary (Joseph now lands here, the Annunciation no longer claims it)", got) + } + if got := compute(overlaid, "2008-04-01"); got == "joseph-spouse-of-the-bl-virgin-mary" { + t.Errorf("overlaid 2008-04-01 = %q, want NOT joseph (a stale cache hit from the base-calendar warm-up)", got) + } + + // And the base calendar's own answer must be unaffected by having since + // computed the overlaid one -- the two keys must not collide either way. + if got := compute(baseLayers, "2008-03-31"); got != "annunciation-of-the-blessed-virgin-mary" { + t.Errorf("base calendar 2008-03-31 after overlaid query = %q, want annunciation-of-the-blessed-virgin-mary (unaffected)", got) + } + if got := compute(baseLayers, "2008-04-01"); got != "joseph-spouse-of-the-bl-virgin-mary" { + t.Errorf("base calendar 2008-04-01 after overlaid query = %q, want joseph-spouse-of-the-bl-virgin-mary (unaffected)", got) + } +} + +// TestEFTransferPlanCacheInvalidatesOnYear is a lighter companion: the same +// week-then-query pattern, varying the YEAR instead of the overlay (2008 vs +// 2035, both real Joseph/Annunciation collision years -- see +// TestEFTwoTransfersDoNotCollide -- but with different transfer targets). +// year is an explicit field of the cache key already, so this mainly guards +// against a key struct refactor accidentally dropping it; the overlay test +// above is the one guarding the field that is easy to omit by mistake. +func TestEFTransferPlanCacheInvalidatesOnYear(t *testing.T) { + sel := calendar.DefaultSelection() + sel.Form = "old" + layers := []calendar.Layer{caldata.Tridentine()} + + compute := func(date string) string { + d, err := time.Parse("2006-01-02", date) + if err != nil { + t.Fatalf("bad test date %q: %v", date, err) + } + return calendar.Compute(d.UTC(), sel, layers).Observed.Slug + } + + if got := compute("2008-04-01"); got != "joseph-spouse-of-the-bl-virgin-mary" { + t.Fatalf("2008-04-01 = %q, want joseph-spouse-of-the-bl-virgin-mary", got) + } + // 2035's Joseph lands on 2035-04-03, not 04-01 (a later Easter shifts the + // whole window). If the cache ignored the year, this would wrongly + // return 2008's plan. + if got := compute("2035-04-01"); got == "joseph-spouse-of-the-bl-virgin-mary" { + t.Errorf("2035-04-01 = %q, want NOT joseph (that is 2008's landing day, not 2035's)", got) + } + if got := compute("2035-04-03"); got != "joseph-spouse-of-the-bl-virgin-mary" { + t.Errorf("2035-04-03 = %q, want joseph-spouse-of-the-bl-virgin-mary", got) + } +} + +// TestEFTransferPlanCacheConcurrentUse exercises the memoised plan from many +// goroutines at once -- gomobile may call Day/Days in from multiple threads, +// and none of the tests above (all sequential) can catch a data race on the +// shared cache map/list. Run with -race; it is the actual proof of the +// "thread-safe" claim, not merely built with a mutex and assumed correct. +func TestEFTransferPlanCacheConcurrentUse(t *testing.T) { + sel := calendar.DefaultSelection() + sel.Form = "old" + base := caldata.Tridentine() + overlay := calendar.Layer{ID: "user", Cels: map[string]calendar.RawCelebration{ + "annunciation-of-the-blessed-virgin-mary": { + Fields: map[string]string{"suppress": "true"}, + Variants: map[string]map[string]string{}, + }, + }} + baseLayers := []calendar.Layer{base} + overlaidLayers := []calendar.Layer{base, overlay} + + years := []int{2008, 2011, 2035, 2046} + + var wg sync.WaitGroup + for g := 0; g < 12; g++ { + g := g + wg.Add(1) + go func() { + defer wg.Done() + layers := baseLayers + if g%2 == 0 { + layers = overlaidLayers // different goroutines hammer different cache keys + } + for i := 0; i < 6; i++ { + y := years[(g+i)%len(years)] + for _, md := range []string{"03-19", "03-31", "04-01"} { + d, err := time.Parse("2006-01-02", time.Date(y, 1, 1, 0, 0, 0, 0, time.UTC).Format("2006")+"-"+md) + if err != nil { + t.Errorf("bad date: %v", err) + return + } + _ = calendar.Compute(d.UTC(), sel, layers).Observed.Slug + } + } + }() + } + wg.Wait() + + // After the concurrent hammering, correctness must still hold for both + // keys -- the concurrency test is not a substitute for the correctness + // test above, so re-assert both outcomes here too. + d, _ := time.Parse("2006-01-02", "2008-04-01") + if got := calendar.Compute(d.UTC(), sel, baseLayers).Observed.Slug; got != "joseph-spouse-of-the-bl-virgin-mary" { + t.Errorf("after concurrent use, base 2008-04-01 = %q, want joseph-spouse-of-the-bl-virgin-mary", got) + } + if got := calendar.Compute(d.UTC(), sel, overlaidLayers).Observed.Slug; got == "joseph-spouse-of-the-bl-virgin-mary" { + t.Errorf("after concurrent use, overlaid 2008-04-01 = %q, want NOT joseph", got) + } +} |