// calcMinRelayFee retuns the minimum transaction fee required for the passed
// transaction to be accepted into the memory pool and relayed.
func calcMinRelayFee(tx *btcutil.Tx) int64 {
	// Most miners allow a free transaction area in blocks they mine to go
	// alongside the area used for high-priority transactions as well as
	// transactions with fees.  A transaction size of up to 1000 bytes is
	// considered safe to go into this section.  Further, the minimum fee
	// calculated below on its own would encourage several small
	// transactions to avoid fees rather than one single larger transaction
	// which is more desirable.  Therefore, as long as the size of the
	// transaction does not exceeed 1000 less than the reserved space for
	// high-priority transactions, don't require a fee for it.
	serializedLen := int64(tx.MsgTx().SerializeSize())
	if serializedLen < (defaultBlockPrioritySize - 1000) {
		return 0
	}

	// Calculate the minimum fee for a transaction to be allowed into the
	// mempool and relayed by scaling the base fee (which is the minimum
	// free transaction relay fee).  minTxRelayFee is in Satoshi/KB, so
	// divide the transaction size by 1000 to convert to kilobytes.  Also,
	// integer division is used so fees only increase on full kilobyte
	// boundaries.
	minFee := (1 + serializedLen/1000) * minTxRelayFee

	// Set the minimum fee to the maximum possible value if the calculated
	// fee is not in the valid range for monetary amounts.
	if minFee < 0 || minFee > btcutil.MaxSatoshi {
		minFee = btcutil.MaxSatoshi
	}

	return minFee
}

// checkSerializedHeight checks if the signature script in the passed
// transaction starts with the serialized block height of wantHeight.
func checkSerializedHeight(coinbaseTx *btcutil.Tx, wantHeight int64) error {
	sigScript := coinbaseTx.MsgTx().TxIn[0].SignatureScript
	if len(sigScript) < 1 {
		str := "the coinbase signature script for blocks of " +
			"version %d or greater must start with the " +
			"length of the serialized block height"
		str = fmt.Sprintf(str, serializedHeightVersion)
		return RuleError(str)
	}

	serializedLen := int(sigScript[0])
	if len(sigScript[1:]) < serializedLen {
		str := "the coinbase signature script for blocks of " +
			"version %d or greater must start with the " +
			"serialized block height"
		str = fmt.Sprintf(str, serializedLen)
		return RuleError(str)
	}

	serializedHeightBytes := make([]byte, 8, 8)
	copy(serializedHeightBytes, sigScript[1:serializedLen+1])
	serializedHeight := binary.LittleEndian.Uint64(serializedHeightBytes)
	if int64(serializedHeight) != wantHeight {
		str := fmt.Sprintf("the coinbase signature script serialized "+
			"block height is %d when %d was expected",
			serializedHeight, wantHeight)
		return RuleError(str)
	}

	return nil
}

func (c *blockTxCollection) txRecordForInserts(tx *btcutil.Tx) *txRecord {
	if i, ok := c.txIndexes[tx.Index()]; ok {
		return c.txs[i]
	}
	record := &txRecord{tx: tx}

	// If this new transaction record cannot be appended to the end of the
	// txs slice (which would disobey ordering transactions by their block
	// index), reslice and update the block's map of block indexes to txs
	// slice indexes.
	if len(c.txs) > 0 && c.txs[len(c.txs)-1].Tx().Index() > tx.Index() {
		i := uint32(len(c.txs))
		for i != 0 && c.txs[i-1].Tx().Index() >= tx.Index() {
			i--
		}
		detached := c.txs[i:]
		c.txs = append(c.txs[:i], record)
		c.txIndexes[tx.Index()] = i
		for i, r := range detached {
			newIndex := uint32(i + len(c.txs))
			c.txIndexes[r.Tx().Index()] = newIndex
			if _, ok := c.unspent[r.Tx().Index()]; ok {
				c.unspent[r.Tx().Index()] = newIndex
			}
		}
		c.txs = append(c.txs, detached...)
	} else {
		c.txIndexes[tx.Index()] = uint32(len(c.txs))
		c.txs = append(c.txs, record)
	}
	return record
}

// ValidateTransactionScripts validates the scripts for the passed transaction
// using multiple goroutines.
func ValidateTransactionScripts(tx *btcutil.Tx, txStore TxStore, flags btcscript.ScriptFlags) error {
	// Collect all of the transaction inputs and required information for
	// validation.
	txIns := tx.MsgTx().TxIn
	txValItems := make([]*txValidateItem, 0, len(txIns))
	for txInIdx, txIn := range txIns {
		// Skip coinbases.
		if txIn.PreviousOutpoint.Index == math.MaxUint32 {
			continue
		}

		txVI := &txValidateItem{
			txInIndex: txInIdx,
			txIn:      txIn,
			tx:        tx,
		}
		txValItems = append(txValItems, txVI)
	}

	// Validate all of the inputs.
	validator := newTxValidator(txStore, flags)
	if err := validator.Validate(txValItems); err != nil {
		return err
	}

	return nil

}

// calcPriority returns a transaction priority given a transaction and the sum
// of each of its input values multiplied by their age (# of confirmations).
// Thus, the final formula for the priority is:
// sum(inputValue * inputAge) / adjustedTxSize
func calcPriority(tx *btcutil.Tx, serializedTxSize int, inputValueAge float64) float64 {
	// In order to encourage spending multiple old unspent transaction
	// outputs thereby reducing the total set, don't count the constant
	// overhead for each input as well as enough bytes of the signature
	// script to cover a pay-to-script-hash redemption with a compressed
	// pubkey.  This makes additional inputs free by boosting the priority
	// of the transaction accordingly.  No more incentive is given to avoid
	// encouraging gaming future transactions through the use of junk
	// outputs.  This is the same logic used in the reference
	// implementation.
	//
	// The constant overhead for a txin is 41 bytes since the previous
	// outpoint is 36 bytes + 4 bytes for the sequence + 1 byte the
	// signature script length.
	//
	// A compressed pubkey pay-to-script-hash redemption with a maximum len
	// signature is of the form:
	// [OP_DATA_73 <73-byte sig> + OP_DATA_35 + {OP_DATA_33
	// <33 byte compresed pubkey> + OP_CHECKSIG}]
	//
	// Thus 1 + 73 + 1 + 1 + 33 + 1 = 110
	overhead := 0
	for _, txIn := range tx.MsgTx().TxIn {
		// Max inputs + size can't possibly overflow here.
		overhead += 41 + minInt(110, len(txIn.SignatureScript))
	}

	if overhead >= serializedTxSize {
		return 0.0
	}

	return inputValueAge / float64(serializedTxSize-overhead)
}

// IsFinalizedTransaction determines whether or not a transaction is finalized.
func IsFinalizedTransaction(tx *btcutil.Tx, blockHeight int64, blockTime time.Time) bool {
	msgTx := tx.MsgTx()

	// Lock time of zero means the transaction is finalized.
	lockTime := msgTx.LockTime
	if lockTime == 0 {
		return true
	}

	// The lock time field of a transaction is either a block height at
	// which the transaction is finalized or a timestamp depending on if the
	// value is before the lockTimeThreshold.  When it is under the
	// threshold it is a block height.
	blockTimeOrHeight := int64(0)
	if lockTime < lockTimeThreshold {
		blockTimeOrHeight = blockHeight
	} else {
		blockTimeOrHeight = blockTime.Unix()
	}
	if int64(lockTime) < blockTimeOrHeight {
		return true
	}

	// At this point, the transaction's lock time hasn't occured yet, but
	// the transaction might still be finalized if the sequence number
	// for all transaction inputs is maxed out.
	for _, txIn := range msgTx.TxIn {
		if txIn.Sequence != math.MaxUint32 {
			return false
		}
	}
	return true
}

// newBlockNotifyCheckTxIn is a helper function to iterate through
// each transaction input of a new block and perform any checks and
// notify listening frontends when necessary.
func (s *rpcServer) newBlockNotifyCheckTxIn(tx *btcutil.Tx) {
	for wltNtfn, cxt := range s.ws.requests.m {
		for _, txin := range tx.MsgTx().TxIn {
			for op, id := range cxt.spentRequests {
				if txin.PreviousOutpoint != op {
					continue
				}

				reply := &btcjson.Reply{
					Result: struct {
						TxHash string `json:"txhash"`
						Index  uint32 `json:"index"`
					}{
						TxHash: op.Hash.String(),
						Index:  uint32(op.Index),
					},
					Error: nil,
					Id:    &id,
				}
				replyBytes, err := json.Marshal(reply)
				if err != nil {
					log.Errorf("RPCS: Unable to marshal spent notification: %v", err)
					continue
				}
				wltNtfn <- replyBytes
				s.ws.requests.RemoveSpentRequest(wltNtfn, &op)
			}
		}
	}
}

func (u *unconfirmedStore) findDoubleSpend(tx *btcutil.Tx) *txRecord {
	for _, input := range tx.MsgTx().TxIn {
		if r, ok := u.previousOutpoints[input.PreviousOutpoint]; ok {
			return r
		}
	}
	return nil
}

// findPreviousCredits searches for all unspent credits that make up the inputs
// for tx.
func (s *Store) findPreviousCredits(tx *btcutil.Tx) ([]Credit, error) {
	type createdCredit struct {
		credit Credit
		err    error
	}

	inputs := tx.MsgTx().TxIn
	creditChans := make([]chan createdCredit, len(inputs))
	for i, txIn := range inputs {
		creditChans[i] = make(chan createdCredit)
		go func(i int, op btcwire.OutPoint) {
			key, ok := s.unspent[op]
			if !ok {
				// Does this input spend an unconfirmed output?
				r, ok := s.unconfirmed.txs[op.Hash]
				switch {
				// Not an unconfirmed tx.
				case !ok:
					fallthrough
				// Output isn't a credit.
				case len(r.credits) <= int(op.Index):
					fallthrough
				// Output isn't a credit.
				case r.credits[op.Index] == nil:
					fallthrough
				// Credit already spent.
				case s.unconfirmed.spentUnconfirmed[op] != nil:
					close(creditChans[i])
					return
				}
				t := &TxRecord{BlockTxKey{BlockHeight: -1}, r, s}
				c := Credit{t, op.Index}
				creditChans[i] <- createdCredit{credit: c}
				return
			}
			r, err := s.lookupBlockTx(key)
			if err != nil {
				creditChans[i] <- createdCredit{err: err}
				return
			}
			t := &TxRecord{key, r, s}
			c := Credit{t, op.Index}
			creditChans[i] <- createdCredit{credit: c}
		}(i, txIn.PreviousOutpoint)
	}
	spent := make([]Credit, 0, len(inputs))
	for _, c := range creditChans {
		cc, ok := <-c
		if !ok {
			continue
		}
		if cc.err != nil {
			return nil, cc.err
		}
		spent = append(spent, cc.credit)
	}
	return spent, nil
}

// newBlockNotifyCheckTxOut is a helper function to iterate through
// each transaction output of a new block and perform any checks and
// notify listening frontends when necessary.
func (s *rpcServer) newBlockNotifyCheckTxOut(block *btcutil.Block, tx *btcutil.Tx, spent []bool) {
	for wltNtfn, cxt := range s.ws.requests.m {
		for i, txout := range tx.MsgTx().TxOut {
			_, txaddrhash, err := btcscript.ScriptToAddrHash(txout.PkScript)
			if err != nil {
				log.Debug("Error getting payment address from tx; dropping any Tx notifications.")
				break
			}
			for addr, id := range cxt.txRequests {
				if !bytes.Equal(addr[:], txaddrhash) {
					continue
				}
				blkhash, err := block.Sha()
				if err != nil {
					log.Error("Error getting block sha; dropping Tx notification.")
					break
				}
				txaddr, err := btcutil.EncodeAddress(txaddrhash, s.server.btcnet)
				if err != nil {
					log.Error("Error encoding address; dropping Tx notification.")
					break
				}
				reply := &btcjson.Reply{
					Result: struct {
						Sender    string `json:"sender"`
						Receiver  string `json:"receiver"`
						BlockHash string `json:"blockhash"`
						Height    int64  `json:"height"`
						TxHash    string `json:"txhash"`
						Index     uint32 `json:"index"`
						Amount    int64  `json:"amount"`
						PkScript  string `json:"pkscript"`
						Spent     bool   `json:"spent"`
					}{
						Sender:    "Unknown", // TODO(jrick)
						Receiver:  txaddr,
						BlockHash: blkhash.String(),
						Height:    block.Height(),
						TxHash:    tx.Sha().String(),
						Index:     uint32(i),
						Amount:    txout.Value,
						PkScript:  btcutil.Base58Encode(txout.PkScript),
						Spent:     spent[i],
					},
					Error: nil,
					Id:    &id,
				}
				replyBytes, err := json.Marshal(reply)
				if err != nil {
					log.Errorf("RPCS: Unable to marshal tx notification: %v", err)
					continue
				}
				wltNtfn <- replyBytes
			}
		}
	}
}

func (r *txRecord) setDebitsSpends(spends []*BlockOutputKey, tx *btcutil.Tx) error {
	if r.debits.spends != nil {
		if *r.tx.Sha() == *tx.Sha() {
			return ErrDuplicateInsert
		}
		return ErrInconsistentStore
	}
	r.debits.spends = spends
	return nil
}

// logSkippedDeps logs any dependencies which are also skipped as a result of
// skipping a transaction while generating a block template at the trace level.
func logSkippedDeps(tx *btcutil.Tx, deps *list.List) {
	if deps == nil {
		return
	}

	for e := deps.Front(); e != nil; e = e.Next() {
		item := e.Value.(*txPrioItem)
		minrLog.Tracef("Skipping tx %s since it depends on %s\n",
			item.tx.Sha(), tx.Sha())
	}
}

// checkPoolDoubleSpend checks whether or not the passed transaction is
// attempting to spend coins already spent by other transactions in the pool.
// Note it does not check for double spends against transactions already in the
// main chain.
//
// This function MUST be called with the mempool lock held (for reads).
func (mp *txMemPool) checkPoolDoubleSpend(tx *btcutil.Tx) error {
	for _, txIn := range tx.MsgTx().TxIn {
		if txR, exists := mp.outpoints[txIn.PreviousOutpoint]; exists {
			str := fmt.Sprintf("transaction %v in the pool "+
				"already spends the same coins", txR.Sha())
			return TxRuleError(str)
		}
	}

	return nil
}

// Bitcoin specific type checking
func isClassA(tx *btcutil.Tx) bool {
	mtx := tx.MsgTx()
	for _, txOut := range mtx.TxOut {
		_, scriptType := mscutil.GetAddrs(txOut.PkScript)
		if scriptType == btcscript.MultiSigTy {
			return false
		}
	}

	// If it wasn't multi sig it's class a
	return true
}

func notifySpentData(n ntfnChan, txhash *btcwire.ShaHash, index uint32,
	spender *btcutil.Tx) {

	var buf bytes.Buffer
	// Ignore Serialize's error, as writing to a bytes.buffer
	// cannot fail.
	spender.MsgTx().Serialize(&buf)
	txStr := hex.EncodeToString(buf.Bytes())

	ntfn := btcws.NewTxSpentNtfn(txhash.String(), int(index), txStr)
	n <- ntfn
}

// isNonstandardTransaction determines whether a transaction contains any
// scripts which are not one of the standard types.
func isNonstandardTransaction(tx *btcutil.Tx) bool {
	// TODO(davec): Should there be checks for the input signature scripts?

	// Check all of the output public key scripts for non-standard scripts.
	for _, txOut := range tx.MsgTx().TxOut {
		scriptClass := btcscript.GetScriptClass(txOut.PkScript)
		if scriptClass == btcscript.NonStandardTy {
			return true
		}
	}
	return false
}

// RemoveDoubleSpends removes all transactions which spend outputs spent by the
// passed transaction from the memory pool.  Removing those transactions then
// leads to removing all transactions which rely on them, recursively.  This is
// necessary when a block is connected to the main chain because the block may
// contain transactions which were previously unknown to the memory pool
//
// This function is safe for concurrent access.
func (mp *txMemPool) RemoveDoubleSpends(tx *btcutil.Tx) {
	// Protect concurrent access.
	mp.Lock()
	defer mp.Unlock()

	for _, txIn := range tx.MsgTx().TxIn {
		if txRedeemer, ok := mp.outpoints[txIn.PreviousOutpoint]; ok {
			if !txRedeemer.Sha().IsEqual(tx.Sha()) {
				mp.removeTransaction(txRedeemer)
			}
		}
	}
}

// addTransaction adds the passed transaction to the memory pool.  It should
// not be called directly as it doesn't perform any validation.  This is a
// helper for maybeAcceptTransaction.
//
// This function MUST be called with the mempool lock held (for writes).
func (mp *txMemPool) addTransaction(tx *btcutil.Tx, height, fee int64) {
	// Add the transaction to the pool and mark the referenced outpoints
	// as spent by the pool.
	mp.pool[*tx.Sha()] = &TxDesc{
		Tx:     tx,
		Added:  time.Now(),
		Height: height,
		Fee:    fee,
	}
	for _, txIn := range tx.MsgTx().TxIn {
		mp.outpoints[txIn.PreviousOutpoint] = tx
	}
}

func (r *txRecord) setCredit(c *credit, index uint32, tx *btcutil.Tx) error {
	if len(r.credits) <= int(index) {
		r.credits = extendCredits(r.credits, index)
	}
	if r.credits[index] != nil {
		if *r.tx.Sha() == *tx.Sha() {
			return ErrDuplicateInsert
		}
		return ErrInconsistentStore
	}

	r.credits[index] = c
	return nil
}

// newBlockNotifyCheckTxIn is a helper function to iterate through
// each transaction input of a new block and perform any checks and
// notify listening frontends when necessary.
func (s *rpcServer) newBlockNotifyCheckTxIn(tx *btcutil.Tx) {
	for _, txin := range tx.MsgTx().TxIn {
		if clist, ok := s.ws.spentNotifications[txin.PreviousOutpoint]; ok {
			var enext *list.Element
			for e := clist.Front(); e != nil; e = enext {
				enext = e.Next()
				c := e.Value.(walletChan)
				notifySpentData(c, &txin.PreviousOutpoint.Hash,
					txin.PreviousOutpoint.Index, tx)
				s.ws.RemoveSpentRequest(c, &txin.PreviousOutpoint)
			}
		}
	}
}