package filter

import (
	"bytes"
	"errors"
	"fmt"
	"math/bits"
	"math/rand"
	"slices"
	"testing"
)

// golombBits is a test helper that encodes values with the given P and returns
// the raw bit string, so bit ordering can be asserted explicitly.
func golombBits(values []uint64, p uint) string {
	var w bitWriter
	for _, v := range values {
		w.writeGolomb(v, p)
	}
	w.flush()
	var s string
	for _, b := range w.buf {
		s += fmt.Sprintf("%08b", b)
	}
	return s
}

// bitsToBytes converts a string of '0' and '1' characters into packed bytes.
func bitsToBytes(t *testing.T, s string) []byte {
	t.Helper()
	if len(s)%8 != 0 {
		t.Fatalf("bit string length %d is not a whole number of bytes", len(s))
	}
	out := make([]byte, len(s)/8)
	for i := range s {
		bit := byte(0)
		switch s[i] {
		case '0':
		case '1':
			bit = 1
		default:
			t.Fatalf("invalid bit %q at %d", s[i], i)
		}
		out[i/8] = out[i/8]<<1 | bit
	}
	return out
}

func TestGolombEncoding(t *testing.T) {
	// BIP158's P=2 table: 0..9 encode as q unary bits followed by the
	// big-endian remainder.
	// The 38 bits above are zero-padded to 40 bits (5 bytes).
	want := "000" + "001" + "010" + "011" +
		"1000" + "1001" + "1010" + "1011" +
		"11000" + "11001" + "00"
	values := make([]uint64, 10)
	for i := range values {
		values[i] = uint64(i)
	}
	if got := golombBits(values, 2); got != want {
		t.Fatalf("P=2 encoding = %s, want %s", got, want)
	}

	for _, p := range []uint{2, 4, 19} {
		values := []uint64{0, 1, 2, 3, 7, 8, 15, 1 << p, 1<<p - 1, 1<<p + 12345}
		encoded := golombBits(values, p)
		encodedBytes := bitsToBytes(t, encoded)

		r := bitReader{data: encodedBytes}
		for i, want := range values {
			got, err := r.readGolomb(p)
			if err != nil {
				t.Fatalf("P=%d read %d: %v", p, i, err)
			}
			if got != want {
				t.Fatalf("P=%d read %d = %d, want %d", p, i, got, want)
			}
		}
		if err := r.checkPadding(); err != nil {
			t.Fatalf("P=%d padding: %v", p, err)
		}
	}
}

func TestBuildDecodeRoundTrip(t *testing.T) {
	blockHash := [32]byte{}
	blockHash[0] = 0xaa

	tests := []struct {
		name  string
		items [][]byte
	}{
		{"single", [][]byte{[]byte("hello")}},
		{"duplicates", [][]byte{[]byte("a"), []byte("b"), []byte("a"), []byte("a")}},
		{"empty item", [][]byte{{}, []byte("x")}},
		{"many", func() [][]byte {
			items := make([][]byte, 0, 300)
			for i := 0; i < 300; i++ {
				items = append(items, []byte(fmt.Sprintf("item-%d", i)))
			}
			return items
		}()},
	}

	for _, tc := range tests {
		t.Run(tc.name, func(t *testing.T) {
			f := Build(tc.items, blockHash)
			values, n, err := Decode(f)
			if err != nil {
				t.Fatalf("Decode: %v", err)
			}
			if n != uint64(len(tc.items)) {
				t.Fatalf("N = %d, want %d", n, len(tc.items))
			}
			if len(values) != len(tc.items) {
				t.Fatalf("decoded %d values, want %d", len(values), len(tc.items))
			}
			if !slices.IsSorted(values) {
				t.Fatal("decoded values are not sorted")
			}

			for _, item := range tc.items {
				ok, err := Match(f, blockHash, [][]byte{item})
				if err != nil {
					t.Fatalf("Match(%q): %v", item, err)
				}
				if !ok {
					t.Fatalf("Match(%q) = false, want true", item)
				}
			}

			// A different key must not (generally) interpret the same set.
			other := blockHash
			other[0] ^= 0xff
			ok, err := Match(f, other, [][]byte{[]byte("definitely-not-present")})
			if err != nil {
				t.Fatalf("Match other key: %v", err)
			}
			if ok {
				t.Fatal("query unexpectedly matched under a different key")
			}
		})
	}

	// Duplicate items map to the same value, so at least one decoded delta is
	// zero. N still counts the raw items.
	f := Build([][]byte{[]byte("dup"), []byte("dup"), []byte("dup")}, blockHash)
	values, n, err := Decode(f)
	if err != nil {
		t.Fatal(err)
	}
	if n != 3 || len(values) != 3 {
		t.Fatalf("N=%d len(values)=%d, want 3,3", n, len(values))
	}
	if values[0] != values[1] || values[1] != values[2] {
		t.Fatalf("duplicate values not equal: %v", values)
	}
}

func TestEmptyFilter(t *testing.T) {
	var hash [32]byte
	f := Build(nil, hash)
	if !bytes.Equal(f, []byte{0x00}) {
		t.Fatalf("Build(nil) = %x, want 00", f)
	}
	if f := Build([][]byte{}, hash); !bytes.Equal(f, []byte{0x00}) {
		t.Fatalf("Build(empty) = %x, want 00", f)
	}

	ok, err := Match([]byte{0x00}, hash, [][]byte{[]byte("anything")})
	if err != nil || ok {
		t.Fatalf("Match(empty, query) = %v, %v; want false, nil", ok, err)
	}
	ok, err = MatchScript([]byte{0x00}, hash, [][]byte{[]byte("anything")})
	if err != nil || ok {
		t.Fatalf("MatchScript(empty, query) = %v, %v; want false, nil", ok, err)
	}
	ok, err = MatchAny([]byte{0x00}, hash, [][]byte{[]byte("anything")})
	if err != nil || ok {
		t.Fatalf("MatchAny(empty, query) = %v, %v; want false, nil", ok, err)
	}

	// Per the package contract, an empty query against an empty filter matches.
	ok, err = Match([]byte{0x00}, hash, nil)
	if err != nil || !ok {
		t.Fatalf("Match(empty, nil query) = %v, %v; want true, nil", ok, err)
	}

	values, n, err := Decode([]byte{0x00})
	if err != nil || n != 0 || values != nil {
		t.Fatalf("Decode(empty) = %v, %d, %v; want nil, 0, nil", values, n, err)
	}
}

func TestMatchMultipleQueries(t *testing.T) {
	var hash [32]byte
	items := [][]byte{[]byte("alpha"), []byte("beta"), []byte("gamma")}
	f := Build(items, hash)

	ok, err := Match(f, hash, [][]byte{[]byte("nope"), []byte("beta")})
	if err != nil || !ok {
		t.Fatalf("multi query = %v, %v; want true, nil", ok, err)
	}
	ok, err = Match(f, hash, [][]byte{[]byte("nope"), []byte("also-nope")})
	if err != nil || ok {
		t.Fatalf("negative multi query = %v, %v; want false, nil", ok, err)
	}
}

func TestMalformedFilters(t *testing.T) {
	var hash [32]byte

	// A valid one-element filter for the value 0 (delta 0, P=19): 20 bits.
	validZero := []byte{0x01, 0x00, 0x00, 0x00}
	if _, _, err := Decode(validZero); err != nil {
		t.Fatalf("valid zero filter: %v", err)
	}

	tests := []struct {
		name   string
		filter []byte
		target error
	}{
		{"empty input", nil, ErrInvalidFilter},
		{"truncated CompactSize", []byte{0xfd, 0x01}, ErrInvalidFilter},
		{"non-canonical CompactSize", []byte{0xfd, 0x01, 0x00}, ErrInvalidFilter},
		{"absurd N", []byte{0xfe, 0x00, 0x00, 0x20, 0x00}, ErrTooManyElements},
		{"missing payload", []byte{0x01}, ErrInvalidFilter},
		{"truncated payload", []byte{0x01, 0x00}, ErrInvalidFilter},
		{"non-zero padding", []byte{0x01, 0x00, 0x00, 0x01}, ErrInvalidFilter},
		{"trailing zero byte", []byte{0x01, 0x00, 0x00, 0x00, 0x00}, ErrInvalidFilter},
		{"empty filter trailing byte", []byte{0x00, 0x00}, ErrInvalidFilter},
		{"zero element with payload", []byte{0x00, 0x01}, ErrInvalidFilter},
	}
	for _, tc := range tests {
		t.Run(tc.name, func(t *testing.T) {
			if _, _, err := Decode(tc.filter); !errors.Is(err, tc.target) {
				t.Fatalf("Decode = %v, want %v", err, tc.target)
			}
			if _, err := Match(tc.filter, hash, [][]byte{[]byte("x")}); !errors.Is(err, tc.target) {
				t.Fatalf("Match = %v, want %v", err, tc.target)
			}
			if _, err := Match(tc.filter, hash, nil); !errors.Is(err, tc.target) {
				t.Fatalf("Match(nil query) = %v, want %v", err, tc.target)
			}
		})
	}
}

// TestRandomInputsNeverPanic exercises Match and Decode with arbitrary short
// byte strings to ensure malformed filters cannot panic.
func TestRandomInputsNeverPanic(t *testing.T) {
	rng := rand.New(rand.NewSource(0x158))
	var hash [32]byte
	for i := 0; i < 5000; i++ {
		data := make([]byte, rng.Intn(64))
		if _, err := rng.Read(data); err != nil {
			t.Fatal(err)
		}
		query := make([][]byte, rng.Intn(4))
		for j := range query {
			query[j] = make([]byte, rng.Intn(8))
			if _, err := rng.Read(query[j]); err != nil {
				t.Fatal(err)
			}
		}
		_, _ = Match(data, hash, query)
		_, _ = Match(data, hash, nil)
		_, _, _ = Decode(data)
	}
}

func FuzzMatch(f *testing.F) {
	f.Add([]byte{0x00}, []byte("x"))
	f.Add([]byte{0x01, 0x00, 0x00, 0x00}, []byte("x"))
	f.Add([]byte{0xfd, 0x01, 0x00, 0x00}, []byte(""))
	f.Fuzz(func(t *testing.T, filter, query []byte) {
		var hash [32]byte
		_, _ = Match(filter, hash, [][]byte{query})
		_, _, _ = Decode(filter)
	})
}

// TestHashMapping checks the (hash * F) >> 64 mapping against a big.Int
// reference for a few values.
func TestHashMapping(t *testing.T) {
	var hash [32]byte
	hash[0] = 1
	var key [16]byte
	copy(key[:], hash[:16])
	items := [][]byte{[]byte("a"), []byte("b"), []byte("c"), []byte("d")}
	f := uint64(len(items)) * M
	for _, item := range items {
		h := siphash24(key, item)
		// Compute the top 64 bits of h*F with math/bits, then compare with a
		// shift/add decomposition that does not use Mul64.
		hi, lo := bits.Mul64(h, f)
		if hi != mulHiRef(h, f) || lo != mulLoRef(h, f) {
			t.Fatalf("mapping for %q mismatch", item)
		}
	}
}

func mulHiRef(a, b uint64) uint64 {
	// 32-bit limb decomposition of the high 64 bits of a*b.
	a0, a1 := a&0xffffffff, a>>32
	b0, b1 := b&0xffffffff, b>>32
	p00 := a0 * b0
	p01 := a0 * b1
	p10 := a1 * b0
	p11 := a1 * b1
	mid := (p00 >> 32) + (p01 & 0xffffffff) + (p10 & 0xffffffff)
	return p11 + (p01 >> 32) + (p10 >> 32) + (mid >> 32)
}

func mulLoRef(a, b uint64) uint64 {
	a0, a1 := a&0xffffffff, a>>32
	b0, b1 := b&0xffffffff, b>>32
	return a0*b0 + ((a0*b1 + a1*b0) << 32)
}