package edge

import (
	"container/list"
	"net/http"
	"sync"
	"time"
)

// Admission caps that bound how much of the cache any single URL or path can
// occupy, independent of the global LRU. The global LRU alone does not stop
// one URL from being pumped full of noise entries that then evict OTHER
// hosts' useful entries — a crawler sending Accept-Language: xx-1 … xx-4096
// (distinct Vary variants) or ?x=1 … ?x=4096 (distinct query strings, part of
// the key because correctness requires it: different query strings can mean
// different content) would otherwise flush the whole cache on demand.
//
// Two caps, because the two floods land on different key components:
//   - maxVaryVariantsPerURL bounds the Vary variants of one exact URL
//     (host+method+path+query) — every variant of it, across every Vary scheme
//     its responses have used, so a URL that varies conditionally gets one
//     allowance rather than one per scheme. It is also what keeps the lookup
//     scan in selectLocked short: a handful of candidates, never a search.
//   - maxEntriesPerPath bounds everything under one path regardless of query
//     string or variant, which is what actually bounds a query-string flood.
//
// Both evict the oldest entry in their group (by StoredAt) when exceeded.
const (
	maxVaryVariantsPerURL = 8
	maxEntriesPerPath     = 32
)

// CacheKey is the full key for a cached response, including Host, Method, Path, RawQuery,
// and VaryValue (concatenation of request-header values named by the response's Vary header).
type CacheKey struct {
	Host      string // request Host header, exact match
	Method    string // "GET" or "HEAD"
	Path      string
	RawQuery  string
	VaryValue string // concatenation of request-header values named by the response's own Vary header; "" if Vary absent
}

// CachedResponse holds a cached HTTP response along with TTL and storage time.
type CachedResponse struct {
	StatusCode int
	Header     http.Header
	Body       []byte
	StoredAt   time.Time
	TTL        time.Duration
	// Route and Gen tag an entry with the RESOLVED serving route (the
	// instance host, whatever name the request used: an alias, a wildcard,
	// a path-routed front door) and the generation of it that produced the
	// response (zero-downtime spec §7.2). Empty Route: untagged, which is
	// every entry with generations off and every route the activator does
	// not manage. A tagged entry is live only while Gen is still the
	// route's newest generation (SetGenerations).
	Route string
	Gen   uint64
}

// Cache is an in-memory, per-host response cache for cacheable GET/HEAD
// responses. It exists to let the edge answer bot/crawler/repeat traffic
// without invoking the hibernation activator (edge.go's ServeHTTP checks
// it before ever reaching the activator) — see
// docs/superpowers/specs/2026-08-02-edge-cache-before-wake-design.md.
// A nil *Cache disables caching entirely; callers must nil-check before use.
type Cache struct {
	mu           sync.Mutex
	maxEntries   int
	maxBodyBytes int
	order        *list.List // MRU at front, LRU at back
	entries      map[cacheFullKey]*list.Element
	byURL        map[cacheURLKey]map[cacheFullKey]*list.Element  // urlKey -> its Vary variants
	byPath       map[cachePathKey]map[cacheFullKey]*list.Element // pathKey -> every entry under that path
	byHost       map[string]map[cacheFullKey]*list.Element       // host -> every entry for that host
	// genOf answers a tagged entry's route's newest generation
	// (SetGenerations); nil with generations off. Called under mu, so it
	// must take no lock its own side holds while calling into the cache.
	genOf func(route string) (uint64, bool)
}

type cacheURLKey struct {
	Host, Method, Path, RawQuery string
}

type cachePathKey struct {
	Host, Method, Path string
}

// cacheFullKey identifies one stored variant. It carries BOTH halves of the
// Vary contract — which headers the response was selected on and the values
// those names resolved to for the request that elicited it — because a variant
// is only reusable for a request that agrees on both. RFC 9111 §4.1.
//
// What the two components guarantee, precisely:
//
//   - Vary holds the CANONICAL name list (canonicalVary: trimmed, deduped,
//     case-canonicalized, sorted), so two responses selecting on the same
//     headers share one slot however they spelled or ordered them, and two
//     responses selecting on DIFFERENT headers never share one.
//   - VaryValue is injective over request-header values FOR A GIVEN Vary: the
//     length prefix varyValue writes ahead of each value means a distinct tuple
//     of values always renders a distinct string, since no value's content can
//     be read as the separator structure around it (see varyValue).
//
// Injectivity is stated per-Vary because that is all the key needs: Vary is a
// key component in its own right, so agreement on the rendered values is only
// ever consulted between entries that already agree on the name list.
type cacheFullKey struct {
	cacheURLKey
	Vary      string // canonicalVary of the response's Vary field value; "" if it carried none
	VaryValue string
}

type cacheEntry struct {
	key  cacheFullKey
	resp *CachedResponse
}

// matches reports whether this stored variant is reusable for r: every header
// named by the response's own Vary field resolves, for r, to the same values
// the stored response was selected under.
//
// An entry stored from a response with no Vary matches every request for the
// URL — that is precisely what "no Vary" means. The empty-Vary branch is
// explicit rather than left to varyValue (which renders "" for an empty name
// list, and so would agree) so that an entry claiming no Vary can never match
// on a non-empty VaryValue it should not be holding.
func (e *cacheEntry) matches(r *http.Request) bool {
	if e.key.Vary == "" {
		return e.key.VaryValue == ""
	}
	return varyValue(r, e.key.Vary) == e.key.VaryValue
}

// specificity counts the headers a variant was selected on: the canonical name
// list, so duplicate, empty and differently-spelled tokens cannot inflate it
// past the number of headers actually consulted. It orders candidates when
// several match one request — see selectLocked.
func (e *cacheEntry) specificity() int {
	return len(canonicalVaryNames(e.key.Vary))
}

// NewCache creates a new cache with the given capacity (max entries) and max body size.
func NewCache(maxEntries, maxBodyBytes int) *Cache {
	return &Cache{
		maxEntries:   maxEntries,
		maxBodyBytes: maxBodyBytes,
		order:        list.New(),
		entries:      make(map[cacheFullKey]*list.Element),
		byURL:        make(map[cacheURLKey]map[cacheFullKey]*list.Element),
		byPath:       make(map[cachePathKey]map[cacheFullKey]*list.Element),
		byHost:       make(map[string]map[cacheFullKey]*list.Element),
	}
}

// SetGenerations arms the generation guard (spec §7.2): a tagged entry is
// refused at Put, and treated as a miss at lookup, unless its Gen is
// genOf(Route). The edge calls it once, from EnableCache, only with
// generations on.
func (c *Cache) SetGenerations(genOf func(route string) (uint64, bool)) {
	c.mu.Lock()
	defer c.mu.Unlock()
	c.genOf = genOf
}

// genCurrentLocked reports whether resp may be served or stored: untagged,
// or tagged with its route's newest generation. A tagged entry with no
// guard armed is not current: it cannot be vouched for. Caller holds c.mu.
func (c *Cache) genCurrentLocked(resp *CachedResponse) bool {
	if resp.Route == "" {
		return true
	}
	if c.genOf == nil {
		return false
	}
	n, ok := c.genOf(resp.Route)
	return ok && n == resp.Gen
}

func (k CacheKey) urlKey() cacheURLKey {
	return cacheURLKey{Host: k.Host, Method: k.Method, Path: k.Path, RawQuery: k.RawQuery}
}

func (k CacheKey) fullKey(vary string) cacheFullKey {
	return cacheFullKey{cacheURLKey: k.urlKey(), Vary: vary, VaryValue: k.VaryValue}
}

func (k cacheURLKey) pathKey() cachePathKey {
	return cachePathKey{Host: k.Host, Method: k.Method, Path: k.Path}
}

// get retrieves a cached variant by an already-resolved VaryValue, if one
// exists and has not expired. Returns (nil, false) for a miss or an expired
// entry. Expired entries are evicted lazily on lookup, not swept on a timer.
//
// Deliberately unexported: every request-handling caller must go through
// GetFor, which matches on the stored Vary names rather than a VaryValue the
// caller had to guess — a request cannot know the response's Vary header until
// the response exists, so an exported by-VaryValue lookup is an invitation to
// guess "" and silently miss (or, worse, hit the wrong variant). get exists for
// the package's own probes and tests, which already hold the exact variant
// string; when several Vary schemes happen to render the same VaryValue it
// picks between them by selectLocked's ordering.
func (c *Cache) get(key CacheKey) (*CachedResponse, bool) {
	c.mu.Lock()
	defer c.mu.Unlock()
	return c.selectLocked(key.urlKey(), func(e *cacheEntry) bool {
		return e.key.VaryValue == key.VaryValue
	})
}

// GetFor is the request-time lookup. baseKey carries everything known before
// the response exists (host, method, path, query) with VaryValue left empty;
// which variant r belongs to is decided by the Vary names each stored entry
// recorded for itself.
//
// The Vary header names live on the RESPONSE, so they cannot be known from r
// alone — which is why they travel with the entry (RFC 9111 §4.1). Every
// candidate for this URL evaluates its OWN names against r, so responses that
// vary by different headers, or that vary only sometimes, coexist under one
// URL instead of overwriting each other's notion of how the URL varies.
//
// The scan is bounded by maxVaryVariantsPerURL, so it is a handful of string
// comparisons, not a search. Both this and maybeStore render the variant
// through varyValue, so store and lookup cannot drift apart — that drift
// (storing under varyValue(request, vary) while looking up under "") is the
// bug that once made every Vary-carrying response a permanent miss.
func (c *Cache) GetFor(baseKey CacheKey, r *http.Request) (*CachedResponse, bool) {
	c.mu.Lock()
	defer c.mu.Unlock()
	return c.selectLocked(baseKey.urlKey(), func(e *cacheEntry) bool {
		return e.matches(r)
	})
}

// selectLocked returns the best live entry for uk that satisfies want, evicting
// any expired entry it walks past. Caller must hold c.mu.
//
// "Best", because several stored variants can satisfy one request: an entry
// from a response with no Vary matches every request for the URL, so it
// overlaps every varying entry beside it. RFC 9111 §4 leaves the choice among
// suitable responses to freshness order; that rule assumes one Vary scheme per
// URI, and under mixed schemes it would hand the non-varying entry to
// everybody the moment it was the newest — a CORS response cached without its
// Access-Control-Allow-Origin, served to the cross-origin requests that needed
// it. So the ordering is most-specific-first: among matches, the entry
// selected on the most headers wins, because it is the one whose stored
// response actually depended on this request's headers. Equal specificity
// falls back to the most recently stored, which is RFC 9111 §4's rule.
//
// The accepted cost of that ordering is stale shadowing: a more-specific
// variant outranks a strictly NEWER general one that also matches, so an older
// `Vary: Accept-Encoding` entry keeps being served to gzip-accepting requests
// even after a fresher no-Vary response for the same URL has been stored beside
// it. Pinned by TestCacheOlderSpecificVariantShadowsNewerGeneralUntilItExpires.
//
// This is knowingly kept, and no recency heuristic is layered on top:
//
//   - It is bounded by the shadowing entry's own TTL. maybeStore clamps every
//     TTL to DefaultCacheMaxTTL, so the window is short and self-healing — the
//     stale entry is dropped by the expiry sweep in this very loop, after which
//     the general entry is the only match left. Bounded staleness is the whole
//     bargain of a cache, and PurgeURL/PurgeHost cut it short on deploy.
//   - The alternative is unbounded WRONGNESS. "Newest wins" hands the
//     non-varying entry to every request the moment it is newest, including the
//     cross-origin ones whose stored response carried an
//     Access-Control-Allow-Origin the new one does not — a correctness failure
//     no TTL bounds, because the newest entry keeps being the newest.
//
// Serving a slightly older response that was selected on this request's actual
// headers is the safe side of that trade.
func (c *Cache) selectLocked(uk cacheURLKey, want func(*cacheEntry) bool) (*CachedResponse, bool) {
	var best *list.Element
	var bestEntry *cacheEntry
	var expired []*list.Element
	for _, el := range c.byURL[uk] {
		e := el.Value.(*cacheEntry)
		if time.Since(e.resp.StoredAt) > e.resp.TTL {
			expired = append(expired, el)
			continue
		}
		if !want(e) {
			continue
		}
		// A generation that is no longer its route's newest is a miss for
		// every name the route answers to (spec §7.2). Left in place: the
		// switch's purge, the TTL or the LRU reclaims it.
		if !c.genCurrentLocked(e.resp) {
			continue
		}
		if bestEntry == nil || better(e, bestEntry) {
			best, bestEntry = el, e
		}
	}
	// Removal is deferred out of the loop: removeLocked deletes from the very
	// map being ranged over, and can drop c.byURL[uk] entirely once its last
	// entry goes.
	for _, el := range expired {
		c.removeLocked(el)
	}
	if best == nil {
		return nil, false
	}
	c.order.MoveToFront(best)
	return bestEntry.resp, true
}

// better reports whether candidate outranks incumbent as the variant to serve:
// more selecting headers first, then more recently stored, and finally by key
// so the answer never depends on map iteration order.
//
// That last step is not cosmetic. selectLocked ranges over a Go map, whose
// order is randomized per iteration, so two entries tied on both specificity
// and StoredAt — same-millisecond stores, or timestamps a test or a restore
// path set by hand — would otherwise serve a different body from one request to
// the next for no visible reason. A cache that answers the same question two
// ways is unreproducible in exactly the situation where it matters. Comparing
// the key components (which are unique per entry: two entries agreeing on both
// are the same map key) makes selection a pure function of what is stored.
func better(candidate, incumbent *cacheEntry) bool {
	cs, is := candidate.specificity(), incumbent.specificity()
	if cs != is {
		return cs > is
	}
	if !candidate.resp.StoredAt.Equal(incumbent.resp.StoredAt) {
		return candidate.resp.StoredAt.After(incumbent.resp.StoredAt)
	}
	if candidate.key.VaryValue != incumbent.key.VaryValue {
		return candidate.key.VaryValue < incumbent.key.VaryValue
	}
	return candidate.key.Vary < incumbent.key.Vary
}

// Put stores a response in the cache. Silently drops a response whose body
// exceeds maxBodyBytes. Evicts the least-recently-used entry when at
// maxEntries, and enforces the per-URL and per-path admission caps so no
// single URL or path can flood the cache (see the cap constants above).
//
// vary is the response's Vary field value — every line of it, comma-joined —
// and "" when the response carried no Vary header at all. It is a separate
// parameter rather than something read back off resp.Header because the caller
// must have computed key.VaryValue from this exact string (edge.go's maybeStore
// does, via varyValue), and because key.VaryValue == "" cannot stand in for
// "no Vary": a response may vary on a header the request never sent, which
// computes an empty value from a very real Vary header.
//
// vary is stored WITH the entry, as part of its key, in the canonical form
// canonicalVary produces — the same normalization varyValue applied when it
// rendered key.VaryValue, so the two halves of the key agree by construction
// and a scheme spelled "accept-encoding" cannot open a second slot beside the
// one "Accept-Encoding" already holds. A URL whose responses vary
// conditionally — CORS middleware emitting Vary: Origin only for
// Origin-bearing requests, content negotiation emitting Vary: Accept-Language
// only when it negotiates — therefore accumulates one variant per DISTINCT
// scheme rather than having each flip invalidate the last, and each request is
// matched against the scheme its own shape produced. The per-URL cap still
// bounds the total, now across schemes rather than within one.
func (c *Cache) Put(key CacheKey, vary string, resp *CachedResponse) {
	if len(resp.Body) > c.maxBodyBytes {
		return
	}
	c.mu.Lock()
	defer c.mu.Unlock()
	// A response whose generation stopped being current while it was in
	// flight (a late answer from a draining process) never fills the cache
	// after the switch (spec §7.2).
	if !c.genCurrentLocked(resp) {
		return
	}
	fk := key.fullKey(canonicalVary(vary))
	uk := fk.cacheURLKey
	if el, ok := c.entries[fk]; ok {
		el.Value.(*cacheEntry).resp = resp
		c.order.MoveToFront(el)
		return
	}
	el := c.order.PushFront(&cacheEntry{key: fk, resp: resp})
	c.entries[fk] = el
	if c.byURL[uk] == nil {
		c.byURL[uk] = make(map[cacheFullKey]*list.Element)
	}
	c.byURL[uk][fk] = el
	pk := uk.pathKey()
	if c.byPath[pk] == nil {
		c.byPath[pk] = make(map[cacheFullKey]*list.Element)
	}
	c.byPath[pk][fk] = el
	if c.byHost[uk.Host] == nil {
		c.byHost[uk.Host] = make(map[cacheFullKey]*list.Element)
	}
	c.byHost[uk.Host][fk] = el

	c.capGroupLocked(c.byURL[uk], maxVaryVariantsPerURL, el)
	c.capGroupLocked(c.byPath[pk], maxEntriesPerPath, el)
	for len(c.entries) > c.maxEntries {
		victim := c.order.Back()
		if victim == nil {
			break
		}
		c.removeLocked(victim)
	}
}

// capGroupLocked drops the oldest entries (by StoredAt) from one admission
// group until it holds at most max, never dropping keep (the entry just
// inserted — evicting it would make the flood self-defeating in the wrong
// direction, turning every request into a permanent miss AND a permanent
// insert). Caller must hold c.mu.
func (c *Cache) capGroupLocked(group map[cacheFullKey]*list.Element, max int, keep *list.Element) {
	for len(group) > max {
		var oldest *list.Element
		for _, el := range group {
			if el == keep {
				continue
			}
			if oldest == nil || el.Value.(*cacheEntry).resp.StoredAt.Before(oldest.Value.(*cacheEntry).resp.StoredAt) {
				oldest = el
			}
		}
		if oldest == nil {
			return
		}
		c.removeLocked(oldest)
	}
}

// removeLocked drops el from every index. Caller must hold c.mu.
func (c *Cache) removeLocked(el *list.Element) {
	e := el.Value.(*cacheEntry)
	c.order.Remove(el)
	delete(c.entries, e.key)
	uk := e.key.cacheURLKey
	if variants := c.byURL[uk]; variants != nil {
		delete(variants, e.key)
		if len(variants) == 0 {
			delete(c.byURL, uk)
		}
	}
	pk := uk.pathKey()
	if group := c.byPath[pk]; group != nil {
		delete(group, e.key)
		if len(group) == 0 {
			delete(c.byPath, pk)
		}
	}
	if group := c.byHost[uk.Host]; group != nil {
		delete(group, e.key)
		if len(group) == 0 {
			delete(c.byHost, uk.Host)
		}
	}
}

// PurgeURL drops every cached variant (every VaryValue) of (host, path, rawQuery)
// for both GET and HEAD methods and returns how many entries it actually removed.
// Returns 0 if none were cached — not an error.
func (c *Cache) PurgeURL(host, path, rawQuery string) int {
	c.mu.Lock()
	defer c.mu.Unlock()
	n := 0
	// GET and HEAD are purged together — a write invalidates both.
	for _, method := range [...]string{"GET", "HEAD"} {
		uk := cacheURLKey{Host: host, Method: method, Path: path, RawQuery: rawQuery}
		for _, el := range elementsOf(c.byURL[uk]) {
			c.removeLocked(el)
			n++
		}
	}
	return n
}

// PurgePath drops every cached entry for (host, path) REGARDLESS of query
// string — every query variant and every Vary variant of each, for both GET
// and HEAD — and returns how many it removed.
//
// This is the primitive behind a bare-path Carlos-Purge target. PurgeURL
// needs the exact RawQuery, so an app that wrote to /events/42 and purged
// "/events/42" left /events/42?utm_source=newsletter serving the pre-write
// body until its TTL ran out — the cached copies a campaign or a locale
// switcher created are exactly the ones a reader is most likely to land on.
//
// It rides the byPath index, which already groups entries by
// (Host, Method, Path) for the per-path admission cap, so this costs two map
// lookups rather than a scan. Both method keys are purged for the same reason
// PurgeURL does it: a write invalidates the GET and the HEAD alike.
func (c *Cache) PurgePath(host, path string) int {
	c.mu.Lock()
	defer c.mu.Unlock()
	n := 0
	for _, method := range [...]string{"GET", "HEAD"} {
		pk := cachePathKey{Host: host, Method: method, Path: path}
		for _, el := range elementsOf(c.byPath[pk]) {
			c.removeLocked(el)
			n++
		}
	}
	return n
}

// PurgeHost drops every cached entry for host — all paths, all query strings,
// all Vary variants — and returns how many it removed. A deploy calls this: a
// fresh process for a host means new code and potentially new content, so
// everything cached from the old one is suspect.
//
// It is no longer only a deploy-time cost, though, and so no longer a
// whole-cache scan: a Carlos-Purge header that names more targets than the
// 64-target/8KiB caps allow degrades to PurgeHost (see purge_header.go),
// which puts it on the request path. It rides the byHost index instead — the
// same discipline byURL and byPath already keep in Put/removeLocked — so a
// misbehaving or hostile app declaring an oversized purge cannot turn every
// response into a scan of the entire cache.
func (c *Cache) PurgeHost(host string) int {
	c.mu.Lock()
	defer c.mu.Unlock()
	els := elementsOf(c.byHost[host])
	for _, el := range els {
		c.removeLocked(el)
	}
	return len(els)
}

// elementsOf snapshots a group's elements so the caller can remove them while
// iterating (removeLocked mutates the very map being ranged over).
func elementsOf(group map[cacheFullKey]*list.Element) []*list.Element {
	els := make([]*list.Element, 0, len(group))
	for _, el := range group {
		els = append(els, el)
	}
	return els
}