// Package block parses a raw block far enough to check it.
//
// A compact filter can say a block mentions one of the wallet's scripts, but not what the block
// contains. Fetching the block only helps if the wallet can prove it is the block a header
// committed to: the header's merkle root is that commitment, and everything here exists to
// rebuild the root from the transactions the block actually carries.
package block

import (
	"crypto/sha256"
	"encoding/binary"
	"errors"
	"fmt"
)

// Errors the parser refuses.
var (
	// ErrShort is a block that ends before its structure does.
	ErrShort = errors.New("block: truncated")
	// ErrNoTransactions is a block with no coinbase.
	ErrNoTransactions = errors.New("block: no transactions")
	// ErrMerkleMismatch is a block whose transactions do not hash to its header's root.
	ErrMerkleMismatch = errors.New("block: the transactions do not match the header's merkle root")
)

// HeaderLen is the fixed header size.
const HeaderLen = 80

// Block is a parsed block.
type Block struct {
	// Hash is the double SHA-256 of the header, in wire order.
	Hash [32]byte
	// MerkleRoot is the root the header commits to, in wire order.
	MerkleRoot [32]byte
	// TxIDs are the transaction ids, in the order the block lists them.
	TxIDs [][32]byte
	// Outputs are each transaction's outputs, in the same order as TxIDs.
	Outputs [][]Output
}

// Output is one transaction output.
type Output struct {
	// Value is the amount in satoshis.
	Value uint64
	// Script is the scriptPubKey.
	Script []byte
}

// Match is one output that pays a script the caller asked about.
type Match struct {
	// TxID is the transaction that created it, in wire order.
	TxID [32]byte
	// Vout is its position in that transaction.
	Vout uint32
	// Value is the amount in satoshis.
	Value uint64
	// Script is the scriptPubKey that matched.
	Script []byte
}

// Match returns the outputs of this block that pay any of the scripts.
//
// This is what turns a filter hit into a coin: the filter said the block mentions a script, and
// this says which output, in which transaction, for how much.
func (b *Block) Match(scripts [][]byte) []Match {
	wanted := make(map[string]bool, len(scripts))

	for _, script := range scripts {
		wanted[string(script)] = true
	}

	var matches []Match

	for index, outputs := range b.Outputs {
		for vout, output := range outputs {
			if !wanted[string(output.Script)] {
				continue
			}

			matches = append(matches, Match{
				TxID:   b.TxIDs[index],
				Vout:   uint32(vout),
				Value:  output.Value,
				Script: output.Script,
			})
		}
	}

	return matches
}

// Parse reads a block's header and transactions.
func Parse(raw []byte) (*Block, error) {
	if len(raw) < HeaderLen+1 {
		return nil, fmt.Errorf("%w: %d bytes", ErrShort, len(raw))
	}

	block := &Block{
		Hash:       doubleSHA256(raw[:HeaderLen]),
		MerkleRoot: toArray(raw[36:68]),
	}

	at := HeaderLen
	count, next, err := compactSize(raw, at)

	if err != nil {
		return nil, err
	}

	at = next

	if count == 0 {
		return nil, ErrNoTransactions
	}

	for index := 0; index < count; index++ {
		id, outputs, next, err := scanTx(raw, at)

		if err != nil {
			return nil, fmt.Errorf("block: transaction %d: %w", index, err)
		}

		block.TxIDs = append(block.TxIDs, id)
		block.Outputs = append(block.Outputs, outputs)
		at = next
	}

	return block, nil
}

// VerifyMerkle rebuilds the root and compares it with the header's.
func (b *Block) VerifyMerkle() error {
	root, err := merkleRoot(b.TxIDs)

	if err != nil {
		return err
	}

	if root != b.MerkleRoot {
		return fmt.Errorf("%w: the header says %x, the transactions hash to %x",
			ErrMerkleMismatch, b.MerkleRoot, root)
	}

	return nil
}

// scanTx walks one transaction and returns its id and the offset after it.
//
// The id is the hash of the transaction without its witness: the marker, flag and witness
// stacks are not part of what identifies it, so they are skipped while the rest is hashed.
func scanTx(raw []byte, at int) ([32]byte, []Output, int, error) {
	var zero [32]byte

	if at+4 > len(raw) {
		return zero, nil, 0, ErrShort
	}

	version := raw[at : at+4]
	body := at + 4
	witness := false

	if body >= len(raw) {
		return zero, nil, 0, ErrShort
	}

	// A zero input count is the segwit marker; the flag follows, then the real input count.
	if raw[body] == 0x00 && body+1 < len(raw) && raw[body+1] == 0x01 {
		witness = true
		body += 2
	}

	inputs, next, err := compactSize(raw, body)

	if err != nil {
		return zero, nil, 0, err
	}

	at = next

	for index := 0; index < inputs; index++ {
		if at+36 > len(raw) {
			return zero, nil, 0, ErrShort
		}

		at += 36

		length, next, err := compactSize(raw, at)

		if err != nil {
			return zero, nil, 0, err
		}

		at = next + length

		if at+4 > len(raw) {
			return zero, nil, 0, ErrShort
		}

		at += 4
	}

	outputCount, next, err := compactSize(raw, at)

	if err != nil {
		return zero, nil, 0, err
	}

	at = next

	outputs := make([]Output, 0, outputCount)

	for index := 0; index < outputCount; index++ {
		if at+8 > len(raw) {
			return zero, nil, 0, ErrShort
		}

		value := binary.LittleEndian.Uint64(raw[at:])
		at += 8

		length, next, err := compactSize(raw, at)

		if err != nil {
			return zero, nil, 0, err
		}

		at = next

		if at+length > len(raw) {
			return zero, nil, 0, ErrShort
		}

		outputs = append(outputs, Output{Value: value, Script: raw[at : at+length]})
		at += length
	}

	end := at

	if witness {
		for index := 0; index < inputs; index++ {
			if at >= len(raw) {
				return zero, nil, 0, ErrShort
			}

			items, next, err := compactSize(raw, at)

			if err != nil {
				return zero, nil, 0, err
			}

			at = next

			for item := 0; item < items; item++ {
				length, next, err := compactSize(raw, at)

				if err != nil {
					return zero, nil, 0, err
				}

				at = next + length

				if at > len(raw) {
					return zero, nil, 0, ErrShort
				}
			}
		}
	}

	if at+4 > len(raw) {
		return zero, nil, 0, ErrShort
	}

	locktime := raw[at : at+4]
	at += 4

	// The id commits to version, inputs, outputs and locktime, in that order, with no witness.
	plain := make([]byte, 0, len(version)+(end-body)+4)
	plain = append(plain, version...)
	plain = append(plain, raw[body:end]...)
	plain = append(plain, locktime...)

	return doubleSHA256(plain), outputs, at, nil
}

// merkleRoot rebuilds the root, pairing an odd last hash with itself.
func merkleRoot(txids [][32]byte) ([32]byte, error) {
	if len(txids) == 0 {
		return [32]byte{}, ErrNoTransactions
	}

	level := make([][32]byte, len(txids))
	copy(level, txids)

	for len(level) > 1 {
		if len(level)%2 == 1 {
			level = append(level, level[len(level)-1])
		}

		next := make([][32]byte, 0, len(level)/2)

		for index := 0; index < len(level); index += 2 {
			pair := make([]byte, 0, 64)
			pair = append(pair, level[index][:]...)
			pair = append(pair, level[index+1][:]...)
			next = append(next, doubleSHA256(pair))
		}

		level = next
	}

	return level[0], nil
}

// compactSize reads Bitcoin's length prefix.
func compactSize(raw []byte, at int) (int, int, error) {
	if at >= len(raw) {
		return 0, 0, ErrShort
	}

	first := raw[at]
	at++

	switch first {
	case 0xfd:
		if at+2 > len(raw) {
			return 0, 0, ErrShort
		}

		return int(binary.LittleEndian.Uint16(raw[at:])), at + 2, nil
	case 0xfe:
		if at+4 > len(raw) {
			return 0, 0, ErrShort
		}

		return int(binary.LittleEndian.Uint32(raw[at:])), at + 4, nil
	case 0xff:
		if at+8 > len(raw) {
			return 0, 0, ErrShort
		}

		return int(binary.LittleEndian.Uint64(raw[at:])), at + 8, nil
	}

	return int(first), at, nil
}

// doubleSHA256 is Bitcoin's hash.
func doubleSHA256(raw []byte) [32]byte {
	first := sha256.Sum256(raw)

	return sha256.Sum256(first[:])
}

// toArray copies a slice into a fixed-size hash.
func toArray(raw []byte) [32]byte {
	var out [32]byte

	copy(out[:], raw)

	return out
}