# evolution-0002: Calendar Search Hit Cache Dedup O(N^2) in cal_searching_got_instance_cb

## Target
GNOME Evolution email/calendar client

## Severity
MEDIUM

## MOAD
0001 (CWE-407: Inefficient Algorithmic Complexity)

## Location
`src/modules/calendar/e-cal-shell-view-private.c` — `cal_searching_got_instance_cb()`

## Description
`cal_searching_got_instance_cb()` is the per-instance callback for Evolution's
calendar "next/previous occurrence" search. It is invoked once per calendar
event instance as `e_cal_client_generate_instances_for_object()` expands
recurring events over a search window.

Inside the callback, each new instance is deduplicated against
`priv->search_hit_cache` (a GSList of `time_t *`) using `g_slist_find_custom()`.
As instances accumulate the list grows, so the I-th instance check scans up to
I-1 entries: O(1) + O(2) + ... + O(N-1) = O(N^2/2) total comparisons.

A search over multiple subscribed calendars each containing long-running weekly
recurring events (e.g., a team standup repeated since 2020) easily reaches
hundreds to thousands of instances per search invocation. Navigation
("next occurrence") triggers this search repeatedly.

## Fix
Add a parallel `GHashTable *search_hit_cache_set` (keyed on `time_t` cast to
`gpointer`) to `ECalShellViewPrivate`. Membership check in
`cal_searching_got_instance_cb()` becomes an O(1) `g_hash_table_contains()`.
Clear and destroy the hash table wherever the GSList is freed.

## Speedup
| N instances | Ops defective | Ops fixed | Ratio |
|-------------|---------------|-----------|-------|
| 50          | 1225          | 50        | 24.5x |
| 100         | 4950          | 100       | 49.5x |
| 200         | 19900         | 200       | 99.5x |
| 500         | 124750        | 500       | 249.5x |
| 1000        | 499500        | 1000      | 499.5x |

## MOAD-0002 (Intertangle)
See evolution-0001 SCAN-NOTES.md — `mail-send-recv.c` static globals
(`send_data`, `glob_ongoing_downsyncs`) are shared mutable state with no mutex.
Architectural finding, not patched here.

## MOAD-0003
CLEAN. No ThreadLocal or GPrivate request-scoped identity leakage beyond
what was identified in evolution-0001 scan.

## MOAD-0004
CLEAN. No credential values (passwords, tokens) logged verbatim. Debug
messages reference password operations by description only.

## MOAD-0005
CLEAN. Evolution uses GLib main loop (single UI thread). No concurrent
cache-get+put race conditions.