package assetcache

import (
	"errors"
	"fmt"
	"os"
	"path/filepath"
	"strings"
	"sync"
	"testing"
	"time"
)

// The eviction tests use a budget of 1000000 bytes and 20000-byte bodies. A
// committed entry holds its body plus a .meta of a few hundred bytes, and a
// fill of such a body reserves 2*20000 + metaReserve, so a store can be
// filled to a little over 90% before the next fill has to evict. A test
// that wants the next fill to evict reserves for bigBody instead.

const evictBudget = 1000000

var (
	evictBody = []byte(strings.Repeat("x", 20000))
	bigBody   = []byte(strings.Repeat("y", 100000))
)

// evictStore opens a store with the eviction budget over a fake FS with
// plenty of room. Tests using it are not acceptance.
func evictStore(t *testing.T) (*Store, string) {
	t.Helper()
	s, _, dir := entryStore(t, evictBudget)
	return s, dir
}

// commitN commits n entries /<prefix>0 .. /<prefix>n-1 for app, oldest first.
func commitN(t *testing.T, s *Store, app, prefix string, n int) {
	t.Helper()
	for i := 0; i < n; i++ {
		commit(t, s, testKey(app, fmt.Sprintf("/%s%d", prefix, i)), evictBody, cssHeader("1"), false)
	}
}

// present reports whether the entry is indexed, without marking it used.
func present(s *Store, app, path string) bool {
	s.mu.Lock()
	defer s.mu.Unlock()
	e := s.entries[testKey(app, path).ID()]
	return e != nil
}

func mustBePresent(t *testing.T, s *Store, app, path string) {
	t.Helper()
	if !present(s, app, path) {
		t.Fatalf("%s %s was evicted, want kept", app, path)
	}
}

func mustBeGone(t *testing.T, s *Store, app, path string) {
	t.Helper()
	if present(s, app, path) {
		t.Fatalf("%s %s survived, want evicted", app, path)
	}
}

func mustFitBudget(t *testing.T, s *Store) {
	t.Helper()
	if st := s.Stats(); st.Bytes+st.Reserved > evictBudget {
		t.Fatalf("Stats = %+v, over the budget %d", st, evictBudget)
	}
}

// TestEvictionTakesFromTheAppFurthestOverItsShare is not acceptance: it uses
// a fake FS.
func TestEvictionTakesFromTheAppFurthestOverItsShare(t *testing.T) {
	s, _ := evictStore(t)
	commitN(t, s, "shop", "s", 36) // about 73% of the budget
	commitN(t, s, "blog", "b", 5)  // about 10%
	// Use shop's oldest: it is no longer the least recently used.
	mustGet(t, s, testKey("shop", "/s0"))

	f, err := s.Reserve(testKey("blog", "/b5"), int64(len(bigBody)))
	if err != nil {
		t.Fatalf("Reserve: %v", err)
	}
	defer f.Abort()

	mustBePresent(t, s, "shop", "/s0") // used since: spared
	mustBeGone(t, s, "shop", "/s1")
	mustBeGone(t, s, "shop", "/s2")
	mustBePresent(t, s, "shop", "/s35")
	for i := 0; i < 5; i++ {
		mustBePresent(t, s, "blog", fmt.Sprintf("/b%d", i))
	}
	mustFitBudget(t, s)
}

// TestOneAppWalkingUniqueQueriesEvictsItself is not acceptance: it uses a
// fake FS.
func TestOneAppWalkingUniqueQueriesEvictsItself(t *testing.T) {
	s, _ := evictStore(t)
	commitN(t, s, "blog", "b", 1)
	for i := 0; i < 70; i++ {
		commit(t, s, testKey("shop", fmt.Sprintf("/q%d", i)), evictBody, cssHeader("1"), false)
		mustFitBudget(t, s)
	}
	mustBePresent(t, s, "blog", "/b0")
	mustBeGone(t, s, "shop", "/q0")
	mustBePresent(t, s, "shop", "/q69")
	if st := s.Stats(); st.Entries < 20 {
		t.Fatalf("Stats = %+v, want shop to keep filling its own room", st)
	}
}

// TestNewAppEvictsTheAppOverItsShare is not acceptance: it uses a fake FS.
// The second app has no entries yet. Its fill is admitted by evicting the
// first app's oldest entries, not refused.
func TestNewAppEvictsTheAppOverItsShare(t *testing.T) {
	s, _ := evictStore(t)
	commitN(t, s, "shop", "s", 40) // about 80% of the budget
	mustFitBudget(t, s)

	commit(t, s, testKey("blog", "/b0"), bigBody, cssHeader("1"), false)

	mustBePresent(t, s, "blog", "/b0")
	mustBeGone(t, s, "shop", "/s0")
	mustBeGone(t, s, "shop", "/s1")
	mustBePresent(t, s, "shop", "/s39")
	mustFitBudget(t, s)
}

// TestShareNeverExceedsAQuarter is not acceptance: it uses a fake FS. One app
// alone has the whole budget to itself by division, but its share stops at a
// quarter.
func TestShareNeverExceedsAQuarter(t *testing.T) {
	s, _ := evictStore(t)
	for apps, want := range map[int]int64{1: evictBudget / 4, 2: evictBudget / 4, 4: evictBudget / 4, 8: evictBudget / 8, 100: evictBudget / 100} {
		if got := s.shareOf(apps); got != want {
			t.Errorf("shareOf(%d) = %d, want %d", apps, got, want)
		}
	}

	// One app alone passes 25% and is evicted (itself) when room is needed.
	commitN(t, s, "shop", "s", 40)
	commit(t, s, testKey("shop", "/new"), bigBody, cssHeader("1"), false)
	mustBeGone(t, s, "shop", "/s0")
	mustBePresent(t, s, "shop", "/new")
	mustFitBudget(t, s)
}

// TestEvictionKeepsLeasedBytesCounted is not acceptance: it uses a fake FS.
// Eviction goes through drop, so a body a Reader holds stays counted and
// makeRoom stops when nothing is left to evict.
func TestEvictionKeepsLeasedBytesCounted(t *testing.T) {
	s, _ := evictStore(t)
	commitN(t, s, "shop", "s", 3)
	var readers []*Reader
	for i := 0; i < 3; i++ {
		r, err := mustGet(t, s, testKey("shop", fmt.Sprintf("/s%d", i))).Open(false)
		if err != nil {
			t.Fatal(err)
		}
		readers = append(readers, r)
	}
	s.makeRoom(10 * evictBudget) // cannot fit; evicts everything it can
	st := s.Stats()
	if st.Entries != 0 || st.Retired != 3*int64(len(evictBody)) || st.Bytes != st.Retired {
		t.Fatalf("Stats = %+v, want no entries and the three leased bodies counted", st)
	}
	for _, r := range readers {
		r.Close()
	}
	if st := s.Stats(); st.Bytes != 0 || st.Retired != 0 {
		t.Fatalf("Stats after Close = %+v, want 0", st)
	}
}

// TestRetainDeletesRejectedKeys is not acceptance: it uses a fake FS.
func TestRetainDeletesRejectedKeys(t *testing.T) {
	s, dir := evictStore(t)
	commitN(t, s, "shop", "s", 3)
	commitN(t, s, "blog", "b", 2)

	n := s.Retain(func(k Key) bool { return k.App == "blog" || k.Path == "/s1" })
	if n != 2 {
		t.Fatalf("Retain = %d, want 2", n)
	}
	mustBeGone(t, s, "shop", "/s0")
	mustBePresent(t, s, "shop", "/s1")
	mustBeGone(t, s, "shop", "/s2")
	mustBePresent(t, s, "blog", "/b0")
	mustBePresent(t, s, "blog", "/b1")
	if st := s.Stats(); st.Entries != 3 || st.Retired != 0 {
		t.Fatalf("Stats = %+v, want 3 entries", st)
	}
	// Nothing of the deleted entries is left on disk: three entries' files.
	if got := listDir(t, dir); len(got) != 6 {
		t.Fatalf("files = %v, want .meta and .body for 3 entries", got)
	}
	if n := s.Retain(func(Key) bool { return true }); n != 0 {
		t.Fatalf("second Retain = %d, want 0", n)
	}
	if n := s.Retain(func(Key) bool { return false }); n != 3 {
		t.Fatalf("reject-all Retain = %d, want 3", n)
	}
	if st := s.Stats(); st.Entries != 0 || st.Bytes != 0 || st.Apps != 0 {
		t.Fatalf("Stats = %+v, want empty", st)
	}
}

// TestEvictionRacesFillsGetsAndRetain is not acceptance: it uses a fake FS.
// Fills in two apps, Gets and Retain run together under -race; afterwards
// the per-app lists and byte counts agree with the index.
func TestEvictionRacesFillsGetsAndRetain(t *testing.T) {
	s, _ := evictStore(t)
	body := evictBody
	// Retain rejects every worker's fourth entry. It starts at the first
	// commit and runs until the last fill is done, and each worker waits
	// after committing its fourth entry until that entry is gone, so Retain
	// deletes while the other workers' fills are in flight.
	rejected := func(k Key) bool { return strings.HasSuffix(k.Path, "-3") }
	firstCommit, fillsDone := make(chan struct{}), make(chan struct{})
	var once sync.Once
	var fills, wg sync.WaitGroup
	for _, app := range []string{"shop", "blog"} {
		for w := 0; w < 3; w++ {
			fills.Add(1)
			go func() {
				defer fills.Done()
				for i := 0; i < 15; i++ {
					k := testKey(app, fmt.Sprintf("/w%d-%d", w, i))
					f, err := s.Reserve(k, int64(len(body)))
					if err != nil {
						if !errors.Is(err, ErrNoRoom) && !errors.Is(err, ErrBusy) {
							t.Errorf("Reserve: %v", err)
						}
						continue
					}
					if _, err := f.Write(body); err != nil {
						t.Errorf("Write: %v", err)
					}
					if err := f.Commit(Meta{Header: cssHeader("1"), Lifetime: time.Hour, Expires: testNow.Add(time.Hour)}, false); err != nil {
						t.Errorf("Commit: %v", err)
					}
					once.Do(func() { close(firstCommit) })
					if rejected(k) {
						for deadline := time.Now().Add(10 * time.Second); present(s, app, k.Path); time.Sleep(time.Millisecond) {
							if time.Now().After(deadline) {
								t.Errorf("%s %s still indexed while Retain runs", app, k.Path)
								break
							}
						}
					}
					s.Get(testKey(app, fmt.Sprintf("/w%d-%d", w, i/2)))
				}
			}()
		}
	}
	go func() {
		fills.Wait()
		close(fillsDone)
	}()
	deleted := 0
	wg.Add(1)
	go func() {
		defer wg.Done()
		select {
		case <-firstCommit:
		case <-fillsDone:
			return
		}
		for {
			select {
			case <-fillsDone:
				return
			default:
				deleted += s.Retain(func(k Key) bool { return !rejected(k) })
			}
		}
	}()
	wg.Wait()
	if deleted == 0 {
		t.Fatal("Retain deleted nothing while the fills ran")
	}

	s.mu.Lock()
	defer s.mu.Unlock()
	if s.reserved != 0 || s.used > evictBudget {
		t.Fatalf("reserved %d used %d, want 0 and within %d", s.reserved, s.used, evictBudget)
	}
	listed := 0
	for scope, app := range s.apps {
		var sum int64
		for el := app.lru.Front(); el != nil; el = el.Next() {
			e := el.Value.(*entry)
			if s.entries[e.id] != e || e.elem != el || e.meta.Key.AppScope() != scope {
				t.Fatalf("list of %s holds an entry the index does not", scope)
			}
			sum += e.bytes()
			listed++
		}
		if sum != app.bytes {
			t.Fatalf("%s bytes = %d, its entries hold %d", scope, app.bytes, sum)
		}
	}
	if listed != len(s.entries) {
		t.Fatalf("lists hold %d entries, index %d", listed, len(s.entries))
	}
}

// mustKeepEverything fails unless every entry and byte in before is still
// there: a refused reservation evicted nothing.
func mustKeepEverything(t *testing.T, s *Store, before Stats) {
	t.Helper()
	if after := s.Stats(); after != before {
		t.Fatalf("Stats after the refusal = %+v, want %+v: nothing evicted", after, before)
	}
}

// TestReserveLargerThanTheBudgetEvictsNothing is not acceptance: it uses a
// fake FS. With a valid 32 MiB budget a fill of unknown length reserves
// about 64 MiB, which no eviction can make room for: it is refused before
// anything is evicted for it.
func TestReserveLargerThanTheBudgetEvictsNothing(t *testing.T) {
	s, _, _ := entryStore(t, 32<<20)
	commitN(t, s, "shop", "s", 3)
	commitN(t, s, "blog", "b", 2)
	before := s.Stats()
	if _, err := s.Reserve(testKey("shop", "/big"), -1); !errors.Is(err, ErrNoRoom) {
		t.Fatalf("err = %v, want ErrNoRoom", err)
	}
	mustKeepEverything(t, s, before)
}

// TestReserveCrowdedOutByOtherFillsEvictsNothing is not acceptance: it uses
// a fake FS. The reservation fits the budget alone, but not beside another
// fill's outstanding reservation, which eviction cannot free.
func TestReserveCrowdedOutByOtherFillsEvictsNothing(t *testing.T) {
	s, _ := evictStore(t)
	commitN(t, s, "shop", "s", 5)
	a, err := s.Reserve(testKey("blog", "/a"), 300000)
	if err != nil {
		t.Fatal(err)
	}
	before := s.Stats()
	if _, err := s.Reserve(testKey("shop", "/b"), 200000); !errors.Is(err, ErrNoRoom) {
		t.Fatalf("err = %v, want ErrNoRoom", err)
	}
	mustKeepEverything(t, s, before)
	a.Abort()
	b, err := s.Reserve(testKey("shop", "/b"), 200000)
	if err != nil {
		t.Fatalf("after the other fill aborted: %v", err)
	}
	b.Abort()
}

// TestReserveBelowTheFloorEvictsNothing is not acceptance: it uses a fake
// FS. The store is full enough that the fill would have to evict, but the
// disk is at its floor, so it is refused before anything is evicted.
func TestReserveBelowTheFloorEvictsNothing(t *testing.T) {
	s, _ := evictStore(t)
	fs := s.cfg.FS.(*fakeFS)
	commitN(t, s, "shop", "s", 40) // about 80% of the budget
	fs.mu.Lock()
	fs.total = 8 << 30
	fs.mu.Unlock()
	fs.setFree(8 << 30 * floorPercent / 100)
	before := s.Stats()
	if _, err := s.Reserve(testKey("blog", "/b"), int64(len(bigBody))); !errors.Is(err, ErrBelowFloor) {
		t.Fatalf("err = %v, want ErrBelowFloor", err)
	}
	mustKeepEverything(t, s, before)
	// With room on the disk the same fill evicts and is admitted.
	fs.setFree(4 << 30)
	f, err := s.Reserve(testKey("blog", "/b"), int64(len(bigBody)))
	if err != nil {
		t.Fatalf("with room on the disk: %v", err)
	}
	defer f.Abort()
	mustBeGone(t, s, "shop", "/s0")
	mustFitBudget(t, s)
}

// stuckBody commits one 100000-byte entry into a 300000-byte store, makes its
// body impossible to unlink (the name becomes a directory holding a file, so
// remove fails) and deletes the entry: its .meta goes, its body is stuck and
// its bytes stay counted. It returns the file whose removal clears the fault.
func stuckBody(t *testing.T) (*Store, string) {
	t.Helper()
	s, _, dir := entryStore(t, 300000)
	k := testKey("shop", "/a.css")
	commit(t, s, k, bigBody, cssHeader("1"), false)
	body := filepath.Join(dir, bodyName(k.ID(), mustGet(t, s, k).Meta.Version))
	if err := os.Remove(body); err != nil {
		t.Fatal(err)
	}
	if err := os.Mkdir(body, 0o700); err != nil {
		t.Fatal(err)
	}
	pin := filepath.Join(body, "pin")
	writeFile(t, pin, []byte("x"))
	if n := s.Retain(func(Key) bool { return false }); n != 1 {
		t.Fatalf("Retain = %d, want the entry deleted", n)
	}
	if st := s.Stats(); st.Entries != 0 || st.Retired != int64(len(bigBody)) || st.Bytes != st.Retired {
		t.Fatalf("Stats = %+v, want only the stuck body counted", st)
	}
	return s, pin
}

// TestReserveRetriesAFailedUnlinkBeforeRefusing is not acceptance: it uses a
// fake FS. A body whose unlink failed holds bytes no eviction can free. While
// the fault lasts the fill is refused; once it clears, the same reservation
// succeeds with no other commit or deletion in between, because Reserve
// retries the unlink before it concludes there is no room.
func TestReserveRetriesAFailedUnlinkBeforeRefusing(t *testing.T) {
	s, pin := stuckBody(t)
	before := s.Stats()
	// 2*90000 + metaReserve fits the budget, but not beside the stuck body.
	probe := testKey("blog", "/b.css")
	if _, err := s.Reserve(probe, 90000); !errors.Is(err, ErrNoRoom) {
		t.Fatalf("while the unlink fails: err = %v, want ErrNoRoom", err)
	}
	mustKeepEverything(t, s, before)
	if err := os.Remove(pin); err != nil {
		t.Fatal(err)
	}
	f, err := s.Reserve(probe, 90000)
	if err != nil {
		t.Fatalf("once the fault cleared: %v", err)
	}
	defer f.Abort()
	if st := s.Stats(); st.Retired != 0 || st.Bytes != 0 {
		t.Fatalf("Stats = %+v, want the stuck body gone", st)
	}
}

// TestRetainRetriesAFailedUnlinkOnAnEmptyIndex is not acceptance: it uses a
// fake FS. The sweep retries stuck unlinks even when there is no entry left
// for it to judge.
func TestRetainRetriesAFailedUnlinkOnAnEmptyIndex(t *testing.T) {
	s, pin := stuckBody(t)
	if err := os.Remove(pin); err != nil {
		t.Fatal(err)
	}
	if n := s.Retain(func(Key) bool { return true }); n != 0 {
		t.Fatalf("Retain = %d, want 0", n)
	}
	if st := s.Stats(); st.Retired != 0 || st.Bytes != 0 {
		t.Fatalf("Stats = %+v, want the stuck body gone", st)
	}
}