package filter

import (
	"bytes"
	_ "embed"
	"encoding/hex"
	"encoding/json"
	"fmt"
	"math/bits"
	"slices"
	"testing"
)

// bip158VectorsJSON holds all ten official BIP158 basic filter vectors from
// https://github.com/bitcoin/bips/blob/master/bip-0158/testnet-19.json
// (testnet heights 0, 2, 3, 15007, 49291, 180480, 926485, 987876, 1263442,
// and 1414221). The embedded objects keep the original height, block hash,
// block, prevOutputScripts, filter, and note fields; the two filter-header
// fields are not needed here.
//
//go:embed testdata/bip158_testnet19.json
var bip158VectorsJSON []byte

type bip158Vector struct {
	Height            uint32   `json:"height"`
	BlockHash         string   `json:"blockHash"`
	Block             string   `json:"block"`
	PrevOutputScripts []string `json:"prevOutputScripts"`
	Filter            string   `json:"filter"`
	Note              string   `json:"note"`
}

// TestBIP158OfficialVectors rebuilds each official testnet filter from the block
// and previous output scripts and checks the exact serialized bytes against the
// vector, then checks that every element matches. This covers OP_RETURN
// exclusion, empty scripts, duplicate scripts, witness transactions, and the
// empty filter.
func TestBIP158OfficialVectors(t *testing.T) {
	var vectors []bip158Vector
	if err := json.Unmarshal(bip158VectorsJSON, &vectors); err != nil {
		t.Fatalf("parse test vectors: %v", err)
	}
	if len(vectors) == 0 {
		t.Fatal("no test vectors")
	}

	for _, v := range vectors {
		v := v
		t.Run(fmt.Sprintf("height_%d", v.Height), func(t *testing.T) {
			block, err := hex.DecodeString(v.Block)
			if err != nil {
				t.Fatalf("decode block: %v", err)
			}
			outputs, err := blockOutputScripts(block)
			if err != nil {
				t.Fatalf("parse block: %v", err)
			}
			prev, err := decodeHexScripts(v.PrevOutputScripts)
			if err != nil {
				t.Fatalf("decode prev scripts: %v", err)
			}
			hash, err := internalBlockHash(v.BlockHash)
			if err != nil {
				t.Fatalf("block hash: %v", err)
			}
			want, err := hex.DecodeString(v.Filter)
			if err != nil {
				t.Fatalf("decode filter: %v", err)
			}

			// The BIP158 element set excludes OP_RETURN outputs (already
			// dropped by blockOutputScripts), empty scripts, and exact
			// duplicates. Height 926485 exercises duplicate scripts.
			raw := make([][]byte, 0, len(prev)+len(outputs))
			raw = append(raw, prev...)
			raw = append(raw, outputs...)
			elements := dedupeScripts(raw)

			if got := Build(elements, hash); !bytes.Equal(got, want) {
				t.Fatalf("Build mismatch\n got %x\nwant %x", got, want)
			}
			if got := BuildFromScripts(raw, hash); !bytes.Equal(got, want) {
				t.Fatalf("BuildFromScripts mismatch\n got %x\nwant %x", got, want)
			}
			if len(raw) != len(elements) {
				if got := Build(raw, hash); bytes.Equal(got, want) {
					t.Fatal("Build(raw) unexpectedly equals filter with duplicate items")
				}
			}

			values, n, err := Decode(want)
			if err != nil {
				t.Fatalf("Decode: %v", err)
			}
			if n != uint64(len(elements)) || len(values) != len(elements) {
				t.Fatalf("decoded N=%d values=%d, want %d", n, len(values), len(elements))
			}
			if !slices.IsSorted(values) {
				t.Fatal("decoded values are not sorted")
			}

			for _, element := range elements {
				ok, err := Match(want, hash, [][]byte{element})
				if err != nil {
					t.Fatalf("Match element: %v", err)
				}
				if !ok {
					t.Fatalf("Match(%x) = false, want true", element)
				}
				ok, err = MatchScript(want, hash, [][]byte{element})
				if err != nil || !ok {
					t.Fatalf("MatchScript(%x) = %v, %v; want true, nil", element, ok, err)
				}
			}

			if len(elements) == 0 {
				ok, err := Match(want, hash, nil)
				if err != nil || !ok {
					t.Fatalf("Match(empty filter, nil query) = %v, %v; want true, nil", ok, err)
				}
				ok, err = Match(want, hash, [][]byte{[]byte("x")})
				if err != nil || ok {
					t.Fatalf("Match(empty filter, query) = %v, %v; want false, nil", ok, err)
				}
				return
			}

			// Find a query whose mapped value is absent from the filter and
			// verify Match rejects it. Skipping values present in the filter
			// avoids asserting on a legitimate 1/M false positive.
			var key [16]byte
			copy(key[:], hash[:16])
			f := uint64(len(elements)) * M
			found := false
			for i := 0; i < 100; i++ {
				q := []byte(fmt.Sprintf("nostrino-bip158-negative/%d/%d", v.Height, i))
				h := siphash24(key, q)
				hi, _ := bits.Mul64(h, f)
				if slices.Contains(values, hi) {
					continue
				}
				ok, err := Match(want, hash, [][]byte{q})
				if err != nil {
					t.Fatalf("Match negative query: %v", err)
				}
				if ok {
					t.Fatalf("Match(%q) = true, want false", q)
				}
				found = true
				break
			}
			if !found {
				t.Fatal("could not find a query value absent from the filter")
			}
		})
	}
}

func decodeHexScripts(in []string) ([][]byte, error) {
	out := make([][]byte, len(in))
	for i, s := range in {
		b, err := hex.DecodeString(s)
		if err != nil {
			return nil, fmt.Errorf("script %d: %w", i, err)
		}
		out[i] = b
	}
	return out, nil
}

func internalBlockHash(display string) ([32]byte, error) {
	var hash [32]byte
	b, err := hex.DecodeString(display)
	if err != nil {
		return hash, err
	}
	if len(b) != len(hash) {
		return hash, fmt.Errorf("block hash length %d, want %d", len(b), len(hash))
	}
	for i := range hash {
		hash[i] = b[len(b)-1-i]
	}
	return hash, nil
}

func dedupeScripts(scripts [][]byte) [][]byte {
	seen := make(map[string]struct{}, len(scripts))
	out := make([][]byte, 0, len(scripts))
	for _, script := range scripts {
		if len(script) == 0 {
			continue
		}
		if _, ok := seen[string(script)]; ok {
			continue
		}
		seen[string(script)] = struct{}{}
		out = append(out, script)
	}
	return out
}

// blockOutputScripts extracts non-empty scriptPubKeys that are not OP_RETURN
// from a serialized Bitcoin block. It understands the BIP144 witness marker and
// flag. This is deliberately test-only: the package does not parse transactions.
func blockOutputScripts(block []byte) ([][]byte, error) {
	r := &blockReader{data: block}
	_ = r.take(80) // block header
	txCount := r.compact()
	var outputs [][]byte
	for i := uint64(0); i < txCount && r.err == nil; i++ {
		_ = r.take(4) // version
		vin := r.compact()
		segwit := false
		if vin == 0 {
			flag := r.take(1)
			if r.err == nil && (len(flag) != 1 || flag[0] == 0) {
				return nil, fmt.Errorf("invalid segwit marker/flag in tx %d", i)
			}
			segwit = true
			vin = r.compact()
		}

		for j := uint64(0); j < vin && r.err == nil; j++ {
			_ = r.take(36) // previous outpoint
			scriptLen := r.compact()
			_ = r.take64(scriptLen)
			_ = r.take(4) // sequence
		}

		vout := r.compact()
		for j := uint64(0); j < vout && r.err == nil; j++ {
			_ = r.take(8) // value
			scriptLen := r.compact()
			script := r.take64(scriptLen)
			if r.err == nil && len(script) > 0 && script[0] != 0x6a {
				outputs = append(outputs, script)
			}
		}

		if segwit {
			for j := uint64(0); j < vin && r.err == nil; j++ {
				items := r.compact()
				for k := uint64(0); k < items && r.err == nil; k++ {
					itemLen := r.compact()
					_ = r.take64(itemLen)
				}
			}
		}
		_ = r.take(4) // lock time
	}
	if r.err != nil {
		return nil, r.err
	}
	if r.pos != len(block) {
		return nil, fmt.Errorf("block has %d trailing bytes", len(block)-r.pos)
	}
	return outputs, nil
}

type blockReader struct {
	data []byte
	pos  int
	err  error
}

func (r *blockReader) take(n int) []byte {
	if r.err != nil {
		return nil
	}
	if n < 0 || r.pos+n > len(r.data) {
		r.err = fmt.Errorf("truncated block at offset %d (need %d bytes)", r.pos, n)
		return nil
	}
	b := r.data[r.pos : r.pos+n]
	r.pos += n
	return b
}

func (r *blockReader) take64(n uint64) []byte {
	if r.err != nil {
		return nil
	}
	if n > uint64(len(r.data)-r.pos) {
		r.err = fmt.Errorf("truncated block at offset %d (need %d bytes)", r.pos, n)
		return nil
	}
	return r.take(int(n))
}

func (r *blockReader) compact() uint64 {
	if r.err != nil {
		return 0
	}
	n, size, err := readCompactSize(r.data[r.pos:])
	if err != nil {
		r.err = err
		return 0
	}
	r.pos += size
	return n
}