package mempool

import (
	"encoding/hex"
	"github.com/p9c/p9/pkg/amt"
	"github.com/p9c/p9/pkg/btcaddr"
	"reflect"
	"runtime"
	"sync"
	"testing"
	"time"
	
	"github.com/p9c/p9/pkg/blockchain"
	"github.com/p9c/p9/pkg/chaincfg"
	"github.com/p9c/p9/pkg/chainhash"
	"github.com/p9c/p9/pkg/ecc"
	"github.com/p9c/p9/pkg/txscript"
	"github.com/p9c/p9/pkg/util"
	"github.com/p9c/p9/pkg/wire"
)

// fakeChain is used by the pool harness to provide generated test utxos and a current faked chain height to the pool
// callbacks. This, in turn, allows transactions to appear as though they are spending completely valid utxos.
type fakeChain struct {
	sync.RWMutex
	utxos          *blockchain.UtxoViewpoint
	currentHeight  int32
	medianTimePast time.Time
}

// FetchUtxoView loads utxo details about the inputs referenced by the passed transaction from the point of view of the
// fake chain. It also attempts to fetch the utxos for the outputs of the transaction itself so the returned view can be
// examined for duplicate transactions. This function is safe for concurrent access however the returned view is NOT.
func (s *fakeChain) FetchUtxoView(tx *util.Tx) (*blockchain.UtxoViewpoint, error) {
	s.RLock()
	defer s.RUnlock()
	// All entries are cloned to ensure modifications to the returned view do not affect the fake chain's view. Add an
	// entry for the tx itself to the new view.
	viewpoint := blockchain.NewUtxoViewpoint()
	prevOut := wire.OutPoint{Hash: *tx.Hash()}
	for txOutIdx := range tx.MsgTx().TxOut {
		prevOut.Index = uint32(txOutIdx)
		entry := s.utxos.LookupEntry(prevOut)
		viewpoint.Entries()[prevOut] = entry.Clone()
	}
	// Add entries for all of the inputs to the tx to the new view.
	for _, txIn := range tx.MsgTx().TxIn {
		entry := s.utxos.LookupEntry(txIn.PreviousOutPoint)
		viewpoint.Entries()[txIn.PreviousOutPoint] = entry.Clone()
	}
	return viewpoint, nil
}

// BestHeight returns the current height associated with the fake chain instance.
func (s *fakeChain) BestHeight() int32 {
	s.RLock()
	height := s.currentHeight
	s.RUnlock()
	return height
}

// SetHeight sets the current height associated with the fake chain instance.
func (s *fakeChain) SetHeight(height int32) {
	s.Lock()
	s.currentHeight = height
	s.Unlock()
}

// MedianTimePast returns the current median time past associated with the fake chain instance.
func (s *fakeChain) MedianTimePast() time.Time {
	s.RLock()
	mtp := s.medianTimePast
	s.RUnlock()
	return mtp
}

// SetMedianTimePast sets the current median time past associated with the fake chain instance.
func (s *fakeChain) SetMedianTimePast(mtp time.Time) {
	s.Lock()
	s.medianTimePast = mtp
	s.Unlock()
}

// // CalcSequenceLock returns the current sequence lock for the passed transaction associated with the fake chain
// // instance.
// func (s *fakeChain) CalcSequenceLock(tx *util.Tx,
// 	view *blockchain.UtxoViewpoint) (*blockchain.SequenceLock, error) {
// 	return &blockchain.SequenceLock{
// 		Seconds:     -1,
// 		BlockHeight: -1,
// 	}, nil
// }

// spendableOutput is a convenience type that houses a particular utxo and the amount associated with it.
type spendableOutput struct {
	outPoint wire.OutPoint
	amount   amt.Amount
}

// txOutToSpendableOut returns a spendable output given a transaction and index of the output to use. This is useful as
// a convenience when creating test transactions.
func txOutToSpendableOut(tx *util.Tx, outputNum uint32) spendableOutput {
	return spendableOutput{
		outPoint: wire.OutPoint{Hash: *tx.Hash(), Index: outputNum},
		amount:   amt.Amount(tx.MsgTx().TxOut[outputNum].Value),
	}
}

// poolHarness provides a harness that includes functionality for creating and signing transactions as well as a fake
// chain that provides utxos for use in generating valid transactions.
type poolHarness struct {
	// signKey is the signing key used for creating transactions throughout the tests. payAddr is the p2sh address for
	// the signing key and is used for the payment address throughout the tests.
	signKey     *ecc.PrivateKey
	payAddr     btcaddr.Address
	payScript   []byte
	chainParams *chaincfg.Params
	chain       *fakeChain
	txPool      *TxPool
}

// CreateCoinbaseTx returns a coinbase transaction with the requested number of outputs paying an appropriate subsidy
// based on the passed block height to the address associated with the harness. It automatically uses a standard
// signature script that starts with the block height that is required by version 2 blocks.
func (p *poolHarness) CreateCoinbaseTx(blockHeight int32, numOutputs uint32, version int32) (*util.Tx, error) {
	// Create standard coinbase script.
	extraNonce := int64(0)
	coinbaseScript, e := txscript.NewScriptBuilder().
		AddInt64(int64(blockHeight)).AddInt64(extraNonce).Script()
	if e != nil {
		return nil, e
	}
	tx := wire.NewMsgTx(wire.TxVersion)
	tx.AddTxIn(
		&wire.TxIn{
			// Coinbase transactions have no inputs, so previous outpoint is zero hash and max index.
			PreviousOutPoint: *wire.NewOutPoint(
				&chainhash.Hash{},
				wire.MaxPrevOutIndex,
			),
			SignatureScript: coinbaseScript,
			Sequence:        wire.MaxTxInSequenceNum,
		},
	)
	totalInput := blockchain.CalcBlockSubsidy(blockHeight, p.chainParams, version)
	amountPerOutput := totalInput / int64(numOutputs)
	remainder := totalInput - amountPerOutput*int64(numOutputs)
	for i := uint32(0); i < numOutputs; i++ {
		// Ensure the final output accounts for any remainder that might be left from splitting the input amount.
		amount := amountPerOutput
		if i == numOutputs-1 {
			amount = amountPerOutput + remainder
		}
		tx.AddTxOut(
			&wire.TxOut{
				PkScript: p.payScript,
				Value:    amount,
			},
		)
	}
	return util.NewTx(tx), nil
}

// CreateSignedTx creates a new signed transaction that consumes the provided inputs and generates the provided number
// of outputs by evenly splitting the total input amount. All outputs will be to the payment script associated with the
// harness and all inputs are assumed to do the same.
func (p *poolHarness) CreateSignedTx(inputs []spendableOutput, numOutputs uint32) (*util.Tx, error) {
	// Calculate the total input amount and split it amongst the requested number of outputs.
	var totalInput amt.Amount
	for _, input := range inputs {
		totalInput += input.amount
	}
	amountPerOutput := int64(totalInput) / int64(numOutputs)
	remainder := int64(totalInput) - amountPerOutput*int64(numOutputs)
	tx := wire.NewMsgTx(wire.TxVersion)
	for _, input := range inputs {
		tx.AddTxIn(
			&wire.TxIn{
				PreviousOutPoint: input.outPoint,
				SignatureScript:  nil,
				Sequence:         wire.MaxTxInSequenceNum,
			},
		)
	}
	for i := uint32(0); i < numOutputs; i++ {
		// Ensure the final output accounts for any remainder that might be left from splitting the input amount.
		amount := amountPerOutput
		if i == numOutputs-1 {
			amount = amountPerOutput + remainder
		}
		tx.AddTxOut(
			&wire.TxOut{
				PkScript: p.payScript,
				Value:    amount,
			},
		)
	}
	// Sign the new transaction.
	for i := range tx.TxIn {
		sigScript, e := txscript.SignatureScript(
			tx, i, p.payScript,
			txscript.SigHashAll, p.signKey, true,
		)
		if e != nil {
			return nil, e
		}
		tx.TxIn[i].SignatureScript = sigScript
	}
	return util.NewTx(tx), nil
}

// CreateTxChain creates a chain of zero-fee transactions (each subsequent transaction spends the entire amount from the
// previous one) with the first one spending the provided outpoint. Each transaction spends the entire amount of the
// previous one and as such does not include any fees.
func (p *poolHarness) CreateTxChain(firstOutput spendableOutput, numTxns uint32) ([]*util.Tx, error) {
	txChain := make([]*util.Tx, 0, numTxns)
	prevOutPoint := firstOutput.outPoint
	spendableAmount := firstOutput.amount
	for i := uint32(0); i < numTxns; i++ {
		// Create the transaction using the previous transaction output and paying the full amount to the payment
		// address associated with the harness.
		tx := wire.NewMsgTx(wire.TxVersion)
		tx.AddTxIn(
			&wire.TxIn{
				PreviousOutPoint: prevOutPoint,
				SignatureScript:  nil,
				Sequence:         wire.MaxTxInSequenceNum,
			},
		)
		tx.AddTxOut(
			&wire.TxOut{
				PkScript: p.payScript,
				Value:    int64(spendableAmount),
			},
		)
		// Sign the new transaction.
		sigScript, e := txscript.SignatureScript(
			tx, 0, p.payScript,
			txscript.SigHashAll, p.signKey, true,
		)
		if e != nil {
			return nil, e
		}
		tx.TxIn[0].SignatureScript = sigScript
		txChain = append(txChain, util.NewTx(tx))
		// Next transaction uses outputs from this one.
		prevOutPoint = wire.OutPoint{Hash: tx.TxHash(), Index: 0}
	}
	return txChain, nil
}

// newPoolHarness returns a new instance of a pool harness initialized with a fake chain and a TxPool bound to it that
// is configured with a policy suitable for testing. Also the fake chain is populated with the returned spendable
// outputs so the caller can easily create new valid transactions which podbuild off of it.
func newPoolHarness(chainParams *chaincfg.Params) (*poolHarness, []spendableOutput, error) {
	// Use a hard coded key pair for deterministic results.
	keyBytes, e := hex.DecodeString(
		"700868df1838811ffbdf918fb482c1f7e" +
			"ad62db4b97bd7012c23e726485e577d",
	)
	if e != nil {
		return nil, nil, e
	}
	signKey, signPub := ecc.PrivKeyFromBytes(ecc.S256(), keyBytes)
	// Generate associated pay-to-script-hash address and resulting payment script.
	pubKeyBytes := signPub.SerializeCompressed()
	payPubKeyAddr, e := btcaddr.NewPubKey(pubKeyBytes, chainParams)
	if e != nil {
		return nil, nil, e
	}
	payAddr := payPubKeyAddr.PubKeyHash()
	pkScript, e := txscript.PayToAddrScript(payAddr)
	if e != nil {
		return nil, nil, e
	}
	// Create a new fake chain and harness bound to it.
	chain := &fakeChain{utxos: blockchain.NewUtxoViewpoint()}
	harness := poolHarness{
		signKey:     signKey,
		payAddr:     payAddr,
		payScript:   pkScript,
		chainParams: chainParams,
		chain:       chain,
		txPool: New(
			&Config{
				Policy: Policy{
					DisableRelayPriority: true,
					FreeTxRelayLimit:     15.0,
					MaxOrphanTxs:         5,
					MaxOrphanTxSize:      1000,
					MaxSigOpCostPerTx:    blockchain.MaxBlockSigOpsCost / 4,
					MinRelayTxFee:        1000, // 1 Satoshi per byte
					MaxTxVersion:         1,
				},
				ChainParams:    chainParams,
				FetchUtxoView:  chain.FetchUtxoView,
				BestHeight:     chain.BestHeight,
				MedianTimePast: chain.MedianTimePast,
				// CalcSequenceLock: chain.CalcSequenceLock,
				SigCache:  nil,
				AddrIndex: nil,
			},
		),
	}
	// Create a single coinbase transaction and add it to the harness chain's utxo set and set the harness chain height
	// such that the coinbase will mature in the next block. This ensures the txpool accepts transactions which spend
	// immature coinbases that will become mature in the next block.
	numOutputs := uint32(1)
	outputs := make([]spendableOutput, 0, numOutputs)
	curHeight := harness.chain.BestHeight()
	coinbase, e := harness.CreateCoinbaseTx(curHeight+1, numOutputs, 0)
	if e != nil {
		return nil, nil, e
	}
	harness.chain.utxos.AddTxOuts(coinbase, curHeight+1)
	for i := uint32(0); i < numOutputs; i++ {
		outputs = append(outputs, txOutToSpendableOut(coinbase, i))
	}
	harness.chain.SetHeight(int32(chainParams.CoinbaseMaturity) + curHeight)
	harness.chain.SetMedianTimePast(time.Now())
	return &harness, outputs, nil
}

// testContext houses a test-related state that is useful to pass to helper functions as a single argument.
type testContext struct {
	t       *testing.T
	harness *poolHarness
}

// testPoolMembership tests the transaction pool associated with the provided test context to determine if the passed
// transaction matches the provided orphan pool and transaction pool status. It also further determines if it should be
// reported as available by the HaveTransaction function based upon the two flags and tests that condition as well.
func testPoolMembership(tc *testContext, tx *util.Tx, inOrphanPool, inTxPool bool) {
	txHash := tx.Hash()
	gotOrphanPool := tc.harness.txPool.IsOrphanInPool(txHash)
	if inOrphanPool != gotOrphanPool {
		_, file, line, _ := runtime.Caller(1)
		tc.t.Fatalf(
			"%s:%d -- IsOrphanInPool: want %v, got %v", file,
			line, inOrphanPool, gotOrphanPool,
		)
	}
	gotTxPool := tc.harness.txPool.IsTransactionInPool(txHash)
	if inTxPool != gotTxPool {
		_, file, line, _ := runtime.Caller(1)
		tc.t.Fatalf(
			"%s:%d -- IsTransactionInPool: want %v, got %v",
			file, line, inTxPool, gotTxPool,
		)
	}
	gotHaveTx := tc.harness.txPool.HaveTransaction(txHash)
	wantHaveTx := inOrphanPool || inTxPool
	if wantHaveTx != gotHaveTx {
		_, file, line, _ := runtime.Caller(1)
		tc.t.Fatalf(
			"%s:%d -- HaveTransaction: want %v, got %v", file,
			line, wantHaveTx, gotHaveTx,
		)
	}
}

// TestSimpleOrphanChain ensures that a simple chain of orphans is handled properly. In particular, it generates a chain
// of single input, single output transactions and inserts them while skipping the first linking transaction so they are
// all orphans. Finally, it adds the linking transaction and ensures the entire orphan chain is moved to the transaction
// pool.
func TestSimpleOrphanChain(t *testing.T) {
	t.Parallel()
	harness, spendableOuts, e := newPoolHarness(&chaincfg.MainNetParams)
	if e != nil {
		t.Fatalf("unable to create test pool: %v", e)
	}
	tc := &testContext{t, harness}
	// Create a chain of transactions rooted with the first spendable output provided by the harness.
	maxOrphans := uint32(harness.txPool.cfg.Policy.MaxOrphanTxs)
	chainedTxns, e := harness.CreateTxChain(spendableOuts[0], maxOrphans+1)
	if e != nil {
		t.Fatalf("unable to create transaction chain: %v", e)
	}
	// Ensure the orphans are accepted (only up to the maximum allowed so none are evicted).
	for _, tx := range chainedTxns[1 : maxOrphans+1] {
		var acceptedTxns []*TxDesc
		acceptedTxns, e = harness.txPool.ProcessTransaction(
			nil, tx, true,
			false, 0,
		)
		if e != nil {
			t.Fatalf(
				"ProcessTransaction: failed to accept valid "+
					"orphan %v", e,
			)
		}
		// Ensure no transactions were reported as accepted.
		if len(acceptedTxns) != 0 {
			t.Fatalf(
				"ProcessTransaction: reported %d accepted "+
					"transactions from what should be an orphan",
				len(acceptedTxns),
			)
		}
		// Ensure the transaction is in the orphan pool, is not in the transaction pool, and is reported as available.
		testPoolMembership(tc, tx, true, false)
	}
	// Add the transaction which completes the orphan chain and ensure they all get accepted. Notice the accept orphans
	// flag is also false here to ensure it has no bearing on whether or not already existing orphans in the pool are
	// linked.
	acceptedTxns, e := harness.txPool.ProcessTransaction(
		nil, chainedTxns[0],
		false, false, 0,
	)
	if e != nil {
		t.Fatalf(
			"ProcessTransaction: failed to accept valid "+
				"orphan %v", e,
		)
	}
	if len(acceptedTxns) != len(chainedTxns) {
		t.Fatalf(
			"ProcessTransaction: reported accepted transactions "+
				"length does not match expected -- got %d, want %d",
			len(acceptedTxns), len(chainedTxns),
		)
	}
	for _, txD := range acceptedTxns {
		// Ensure the transaction is no longer in the orphan pool, is now in the transaction pool, and is reported as
		// available.
		testPoolMembership(tc, txD.Tx, false, true)
	}
}

// TestOrphanReject ensures that orphans are properly rejected when the allow orphans flag is not set on
// ProcessTransaction.
func TestOrphanReject(t *testing.T) {
	t.Parallel()
	harness, outputs, e := newPoolHarness(&chaincfg.MainNetParams)
	if e != nil {
		t.Fatalf("unable to create test pool: %v", e)
	}
	tc := &testContext{t, harness}
	// Create a chain of transactions rooted with the first spendable output provided by the harness.
	maxOrphans := uint32(harness.txPool.cfg.Policy.MaxOrphanTxs)
	chainedTxns, e := harness.CreateTxChain(outputs[0], maxOrphans+1)
	if e != nil {
		t.Fatalf("unable to create transaction chain: %v", e)
	}
	// Ensure orphans are rejected when the allow orphans flag is not set.
	for _, tx := range chainedTxns[1:] {
		acceptedTxns, e := harness.txPool.ProcessTransaction(
			nil, tx, false,
			false, 0,
		)
		if e == nil {
			t.Fatalf(
				"ProcessTransaction: did not fail on orphan "+
					"%v when allow orphans flag is false", tx.Hash(),
			)
		}
		expectedErr := RuleError{}
		if reflect.TypeOf(e) != reflect.TypeOf(expectedErr) {
			t.Fatalf(
				"ProcessTransaction: wrong error got: <%T> %v, "+
					"want: <%T>", e, e, expectedErr,
			)
		}
		code, extracted := extractRejectCode(e)
		if !extracted {
			t.Fatalf(
				"ProcessTransaction: failed to extract reject "+
					"code from error %q", e,
			)
		}
		if code != wire.RejectDuplicate {
			t.Fatalf(
				"ProcessTransaction: unexpected reject code "+
					"-- got %v, want %v", code, wire.RejectDuplicate,
			)
		}
		// Ensure no transactions were reported as accepted.
		if len(acceptedTxns) != 0 {
			t.Fatalf(
				"ProcessTransaction: reported %d accepted "+
					"transactions from failed orphan attempt",
				len(acceptedTxns),
			)
		}
		// Ensure the transaction is not in the orphan pool, not in the transaction pool, and not reported as available
		testPoolMembership(tc, tx, false, false)
	}
}

// TestOrphanEviction ensures that exceeding the maximum number of orphans evicts entries to make room for the new ones.
func TestOrphanEviction(t *testing.T) {
	t.Parallel()
	harness, outputs, e := newPoolHarness(&chaincfg.MainNetParams)
	if e != nil {
		t.Fatalf("unable to create test pool: %v", e)
	}
	tc := &testContext{t, harness}
	// Create a chain of transactions rooted with the first spendable output provided by the harness that is long enough
	// to be able to force several orphan evictions.
	maxOrphans := uint32(harness.txPool.cfg.Policy.MaxOrphanTxs)
	chainedTxns, e := harness.CreateTxChain(outputs[0], maxOrphans+5)
	if e != nil {
		t.Fatalf("unable to create transaction chain: %v", e)
	}
	// Add enough orphans to exceed the max allowed while ensuring they are all accepted.  This will cause an eviction.
	for _, tx := range chainedTxns[1:] {
		acceptedTxns, e := harness.txPool.ProcessTransaction(
			nil, tx, true,
			false, 0,
		)
		if e != nil {
			t.Fatalf(
				"ProcessTransaction: failed to accept valid "+
					"orphan %v", e,
			)
		}
		// Ensure no transactions were reported as accepted.
		if len(acceptedTxns) != 0 {
			t.Fatalf(
				"ProcessTransaction: reported %d accepted "+
					"transactions from what should be an orphan",
				len(acceptedTxns),
			)
		}
		// Ensure the transaction is in the orphan pool, is not in the transaction pool, and is reported as available.
		testPoolMembership(tc, tx, true, false)
	}
	// Figure out which transactions were evicted and make sure the number evicted matches the expected number.
	var evictedTxns []*util.Tx
	for _, tx := range chainedTxns[1:] {
		if !harness.txPool.IsOrphanInPool(tx.Hash()) {
			evictedTxns = append(evictedTxns, tx)
		}
	}
	expectedEvictions := len(chainedTxns) - 1 - int(maxOrphans)
	if len(evictedTxns) != expectedEvictions {
		t.Fatalf(
			"unexpected number of evictions -- got %d, want %d",
			len(evictedTxns), expectedEvictions,
		)
	}
	// Ensure none of the evicted transactions ended up in the transaction pool.
	for _, tx := range evictedTxns {
		testPoolMembership(tc, tx, false, false)
	}
}

// TestBasicOrphanRemoval ensure that orphan removal works as expected when an orphan that doesn't exist is removed both
// when there is another orphan that redeems it and when there is not.
func TestBasicOrphanRemoval(t *testing.T) {
	t.Parallel()
	const maxOrphans = 4
	harness, spendableOuts, e := newPoolHarness(&chaincfg.MainNetParams)
	if e != nil {
		t.Fatalf("unable to create test pool: %v", e)
	}
	harness.txPool.cfg.Policy.MaxOrphanTxs = maxOrphans
	tc := &testContext{t, harness}
	// Create a chain of transactions rooted with the first spendable output provided by the harness.
	chainedTxns, e := harness.CreateTxChain(spendableOuts[0], maxOrphans+1)
	if e != nil {
		t.Fatalf("unable to create transaction chain: %v", e)
	}
	// Ensure the orphans are accepted (only up to the maximum allowed so none are evicted).
	for _, tx := range chainedTxns[1 : maxOrphans+1] {
		var acceptedTxns []*TxDesc
		acceptedTxns, e = harness.txPool.ProcessTransaction(
			nil, tx, true,
			false, 0,
		)
		if e != nil {
			t.Fatalf(
				"ProcessTransaction: failed to accept valid "+
					"orphan %v", e,
			)
		}
		// Ensure no transactions were reported as accepted.
		if len(acceptedTxns) != 0 {
			t.Fatalf(
				"ProcessTransaction: reported %d accepted "+
					"transactions from what should be an orphan",
				len(acceptedTxns),
			)
		}
		// Ensure the transaction is in the orphan pool, not in the transaction pool, and reported as available.
		testPoolMembership(tc, tx, true, false)
	}
	// Attempt to remove an orphan that has no redeemers and is not present, and ensure the state of all other orphans
	// are unaffected.
	nonChainedOrphanTx, e := harness.CreateSignedTx(
		[]spendableOutput{
			{
				amount:   amt.Amount(5000000000),
				outPoint: wire.OutPoint{Hash: chainhash.Hash{}, Index: 0},
			},
		}, 1,
	)
	if e != nil {
		t.Fatalf("unable to create signed tx: %v", e)
	}
	harness.txPool.RemoveOrphan(nonChainedOrphanTx)
	testPoolMembership(tc, nonChainedOrphanTx, false, false)
	for _, tx := range chainedTxns[1 : maxOrphans+1] {
		testPoolMembership(tc, tx, true, false)
	}
	// Attempt to remove an orphan that has a existing redeemer but itself is not present and ensure the state of all
	// other orphans (including the one that redeems it) are unaffected.
	harness.txPool.RemoveOrphan(chainedTxns[0])
	testPoolMembership(tc, chainedTxns[0], false, false)
	for _, tx := range chainedTxns[1 : maxOrphans+1] {
		testPoolMembership(tc, tx, true, false)
	}
	// Remove each orphan one-by-one and ensure they are removed as expected.
	for _, tx := range chainedTxns[1 : maxOrphans+1] {
		harness.txPool.RemoveOrphan(tx)
		testPoolMembership(tc, tx, false, false)
	}
}

// TestOrphanChainRemoval ensure that orphan chains (orphans that spend outputs from other orphans) are removed as
// expected.
func TestOrphanChainRemoval(t *testing.T) {
	t.Parallel()
	const maxOrphans = 10
	harness, spendableOuts, e := newPoolHarness(&chaincfg.MainNetParams)
	if e != nil {
		t.Fatalf("unable to create test pool: %v", e)
	}
	harness.txPool.cfg.Policy.MaxOrphanTxs = maxOrphans
	tc := &testContext{t, harness}
	// Create a chain of transactions rooted with the first spendable output provided by the harness.
	chainedTxns, e := harness.CreateTxChain(spendableOuts[0], maxOrphans+1)
	if e != nil {
		t.Fatalf("unable to create transaction chain: %v", e)
	}
	// Ensure the orphans are accepted (only up to the maximum allowed so none are evicted).
	for _, tx := range chainedTxns[1 : maxOrphans+1] {
		acceptedTxns, e := harness.txPool.ProcessTransaction(
			nil, tx, true,
			false, 0,
		)
		if e != nil {
			t.Fatalf(
				"ProcessTransaction: failed to accept valid "+
					"orphan %v", e,
			)
		}
		// Ensure no transactions were reported as accepted.
		if len(acceptedTxns) != 0 {
			t.Fatalf(
				"ProcessTransaction: reported %d accepted "+
					"transactions from what should be an orphan",
				len(acceptedTxns),
			)
		}
		// Ensure the transaction is in the orphan pool, not in the transaction pool, and reported as available.
		testPoolMembership(tc, tx, true, false)
	}
	// Remove the first orphan that starts the orphan chain without the remove redeemer flag set and ensure that only
	// the first orphan was removed.
	harness.txPool.mtx.Lock()
	harness.txPool.removeOrphan(chainedTxns[1], false)
	harness.txPool.mtx.Unlock()
	testPoolMembership(tc, chainedTxns[1], false, false)
	for _, tx := range chainedTxns[2 : maxOrphans+1] {
		testPoolMembership(tc, tx, true, false)
	}
	// Remove the first remaining orphan that starts the orphan chain with the remove redeemer flag set and ensure they
	// are all removed.
	harness.txPool.mtx.Lock()
	harness.txPool.removeOrphan(chainedTxns[2], true)
	harness.txPool.mtx.Unlock()
	for _, tx := range chainedTxns[2 : maxOrphans+1] {
		testPoolMembership(tc, tx, false, false)
	}
}

// TestMultiInputOrphanDoubleSpend ensures that orphans that spend from an output that is spend by another transaction
// entering the pool are removed.
func TestMultiInputOrphanDoubleSpend(t *testing.T) {
	t.Parallel()
	const maxOrphans = 4
	harness, outputs, e := newPoolHarness(&chaincfg.MainNetParams)
	if e != nil {
		t.Fatalf("unable to create test pool: %v", e)
	}
	harness.txPool.cfg.Policy.MaxOrphanTxs = maxOrphans
	tc := &testContext{t, harness}
	// Create a chain of transactions rooted with the first spendable output provided by the harness.
	chainedTxns, e := harness.CreateTxChain(outputs[0], maxOrphans+1)
	if e != nil {
		t.Fatalf("unable to create transaction chain: %v", e)
	}
	// Start by adding the orphan transactions from the generated chain except the final one.
	for _, tx := range chainedTxns[1:maxOrphans] {
		var acceptedTxns []*TxDesc
		acceptedTxns, e = harness.txPool.ProcessTransaction(
			nil, tx, true,
			false, 0,
		)
		if e != nil {
			t.Fatalf(
				"ProcessTransaction: failed to accept valid "+
					"orphan %v", e,
			)
		}
		if len(acceptedTxns) != 0 {
			t.Fatalf(
				"ProcessTransaction: reported %d accepted transactions "+
					"from what should be an orphan", len(acceptedTxns),
			)
		}
		testPoolMembership(tc, tx, true, false)
	}
	// Ensure a transaction that contains a double spend of the same output as the second orphan that was just added as
	// well as a valid spend from that last orphan in the chain generated above (and is not in the orphan pool) is
	// accepted to the orphan pool. This must be allowed since it would otherwise be possible for a malicious actor to
	// disrupt tx chains.
	doubleSpendTx, e := harness.CreateSignedTx(
		[]spendableOutput{
			txOutToSpendableOut(chainedTxns[1], 0),
			txOutToSpendableOut(chainedTxns[maxOrphans], 0),
		}, 1,
	)
	if e != nil {
		t.Fatalf("unable to create signed tx: %v", e)
	}
	acceptedTxns, e := harness.txPool.ProcessTransaction(
		nil, doubleSpendTx,
		true, false, 0,
	)
	if e != nil {
		t.Fatalf(
			"ProcessTransaction: failed to accept valid orphan %v",
			e,
		)
	}
	if len(acceptedTxns) != 0 {
		t.Fatalf(
			"ProcessTransaction: reported %d accepted transactions "+
				"from what should be an orphan", len(acceptedTxns),
		)
	}
	testPoolMembership(tc, doubleSpendTx, true, false)
	// Add the transaction which completes the orphan chain and ensure the chain gets accepted. Notice the accept
	// orphans flag is also false here to ensure it has no bearing on whether or not already existing orphans in the
	// pool are linked. This will cause the shared output to become a concrete spend which will in turn must cause the
	// double spending orphan to be removed.
	acceptedTxns, e = harness.txPool.ProcessTransaction(
		nil, chainedTxns[0],
		false, false, 0,
	)
	if e != nil {
		t.Fatalf("ProcessTransaction: failed to accept valid tx %v", e)
	}
	if len(acceptedTxns) != maxOrphans {
		t.Fatalf(
			"ProcessTransaction: reported accepted transactions "+
				"length does not match expected -- got %d, want %d",
			len(acceptedTxns), maxOrphans,
		)
	}
	for _, txD := range acceptedTxns {
		// Ensure the transaction is no longer in the orphan pool, is in the transaction pool, and is reported as
		// available.
		testPoolMembership(tc, txD.Tx, false, true)
	}
	// Ensure the double spending orphan is no longer in the orphan pool and was not moved to the transaction pool.
	testPoolMembership(tc, doubleSpendTx, false, false)
}

// TestCheckSpend tests that CheckSpend returns the expected spends found in the mempool.
func TestCheckSpend(t *testing.T) {
	t.Parallel()
	harness, outputs, e := newPoolHarness(&chaincfg.MainNetParams)
	if e != nil {
		t.Fatalf("unable to create test pool: %v", e)
	}
	// The mempool is empty, so none of the spendable outputs should have a spend there.
	for _, op := range outputs {
		spend := harness.txPool.CheckSpend(op.outPoint)
		if spend != nil {
			t.Fatalf("Unexpeced spend found in pool: %v", spend)
		}
	}
	// Create a chain of transactions rooted with the first spendable output provided by the harness.
	const txChainLength = 5
	chainedTxns, e := harness.CreateTxChain(outputs[0], txChainLength)
	if e != nil {
		t.Fatalf("unable to create transaction chain: %v", e)
	}
	for _, tx := range chainedTxns {
		_, e := harness.txPool.ProcessTransaction(
			nil, tx, true,
			false, 0,
		)
		if e != nil {
			t.Fatalf(
				"ProcessTransaction: failed to accept "+
					"tx: %v", e,
			)
		}
	}
	// The first tx in the chain should be the spend of the spendable output.
	op := outputs[0].outPoint
	spend := harness.txPool.CheckSpend(op)
	if spend != chainedTxns[0] {
		t.Fatalf(
			"expected %v to be spent by %v, instead "+
				"got %v", op, chainedTxns[0], spend,
		)
	}
	// Now all but the last tx should be spent by the next.
	for i := 0; i < len(chainedTxns)-1; i++ {
		op = wire.OutPoint{
			Hash:  *chainedTxns[i].Hash(),
			Index: 0,
		}
		expSpend := chainedTxns[i+1]
		spend = harness.txPool.CheckSpend(op)
		if spend != expSpend {
			t.Fatalf(
				"expected %v to be spent by %v, instead "+
					"got %v", op, expSpend, spend,
			)
		}
	}
	// The last tx should have no spend.
	op = wire.OutPoint{
		Hash:  *chainedTxns[txChainLength-1].Hash(),
		Index: 0,
	}
	spend = harness.txPool.CheckSpend(op)
	if spend != nil {
		t.Fatalf("Unexpeced spend found in pool: %v", spend)
	}
}