import { dataStructures } from '@liskhq/lisk-utils' ; import { Transaction } from './types' ; export interface TransactionListOptions { readonly maxSize ? : number ; readonly minReplacementFeeDifference ? : bigint ; } const DEFAULT_MAX_SIZE = 64 ; export const DEFAULT_MINIMUM_REPLACEMENT_FEE_DIFFERENCE = BigInt ( 10 ) ; type AddStatus = { added : true ; removedID ? : Buffer ; reason ? : undefined ; } | { added : false ; removedID ? : Buffer ; reason : string ; } ; export class TransactionList { public readonly address : Buffer ; private _processable : Array < bigint > ; private readonly _transactions : { [ nonce ] : Transaction ; } ; private readonly _nonceHeap : dataStructures . MinHeap < undefined , bigint > ; private readonly _maxSize : number ; private readonly _minReplacementFeeDifference : bigint ; public constructor ( address , options ? ) { this . address = address ; this . _transactions = { } ; this . _nonceHeap = new dataStructures . MinHeap < undefined , bigint > ( ) ; this . _processable = [ ] ; this . _maxSize = options ?. maxSize ?? DEFAULT_MAX_SIZE ; this . _minReplacementFeeDifference = options ?. minReplacementFeeDifference ?? DEFAULT_MINIMUM_REPLACEMENT_FEE_DIFFERENCE ; } public get ( nonce ) { return this . _transactions [ nonce . toString ( ) ] ; } public add ( incomingTx , processable = false ) { const existingTx = this . _transactions [ incomingTx . nonce . toString ( ) ] ; if ( existingTx ) { if ( incomingTx . fee < existingTx . fee + this . _minReplacementFeeDifference ) { return { added : false , reason : 'Incoming transaction fee is not sufficient to replace existing transaction' , } ; } this . _demoteAfter ( incomingTx . nonce ) ; this . _transactions [ incomingTx . nonce . toString ( ) ] = incomingTx ; return { added : true , removedID : existingTx . id } ; } const highestNonce = this . _highestNonce ( ) ; let removedID ; if ( this . _nonceHeap . count >= this . _maxSize ) { if ( incomingTx . nonce > highestNonce ) { return { added : false , reason : 'Incoming transaction exceeds maximum transaction limit per account' , } ; } removedID = this . remove ( highestNonce ) ; } this . _transactions [ incomingTx . nonce . toString ( ) ] = incomingTx ; this . _nonceHeap . push ( incomingTx . nonce , undefined ) ; if ( processable && this . _processable . length === 0 ) { this . _processable . push ( incomingTx . nonce ) ; } return { added : true , removedID } ; } public remove ( nonce ) { const removingTx = this . _transactions [ nonce . toString ( ) ] ; if ( ! removingTx ) { return undefined ; } delete this . _transactions [ nonce . toString ( ) ] ; const { keys } = this . _nonceHeap ; this . _nonceHeap . clear ( ) ; for ( const key of keys ) { if ( key !== nonce ) { this . _nonceHeap . push ( key , undefined ) ; } } this . _demoteAfter ( nonce ) ; return removingTx . id ; } public promote ( txs ) { const promotingNonces = [ ] ; for ( const tx of txs ) { const promotingTx = this . _transactions [ tx . nonce . toString ( ) ] ; if ( ! promotingTx ) { return false ; } if ( tx . id !== promotingTx . id ) { return false ; } promotingNonces . push ( tx . nonce ) ; } this . _processable = Array . from ( new Set ( [ ... this . _processable , ... promotingNonces ] ) ) ; this . _sortProcessable ( ) ; return true ; } public get size ( ) : number { return this . _nonceHeap . count ; } public getProcessable ( ) { const txs = [ ] ; for ( const nonce of this . _processable ) { txs . push ( this . _transactions [ nonce . toString ( ) ] ) ; } return txs ; } public getUnprocessable ( ) { if ( this . _nonceHeap . count === 0 ) { return [ ] ; } if ( this . _processable . length === this . _nonceHeap . count ) { return [ ] ; } const clonedHeap = this . _nonceHeap . clone ( ) ; for ( const _ of this . _processable ) { clonedHeap . pop ( ) ; } const remainingCount = clonedHeap . count ; const unprocessableTx = [ ] ; for ( let i = 0 ; i < remainingCount ; i += 1 ) { const { key } = clonedHeap . pop ( ) as { key : bigint ; } ; unprocessableTx . push ( this . _transactions [ key . toString ( ) ] ) ; } return unprocessableTx ; } public getPromotable ( ) { if ( this . _nonceHeap . count === 0 ) { return [ ] ; } if ( this . _processable . length === this . _nonceHeap . count ) { return [ ] ; } const clonedHeap = this . _nonceHeap . clone ( ) ; for ( const _ of this . _processable ) { clonedHeap . pop ( ) ; } const firstUnprocessable = clonedHeap . pop ( ) ; if ( ! firstUnprocessable ) { return [ ] ; } if ( this . _processable . length !== 0 ) { const highestProcessableNonce = this . _processable [ this . _processable . length - 1 ] ; if ( firstUnprocessable . key !== highestProcessableNonce + BigInt ( 1 ) ) { return [ ] ; } } const promotableTx = [ this . _transactions [ firstUnprocessable . key . toString ( ) ] ] ; const remainingNonces = clonedHeap . count ; let lastPromotedNonce = this . _transactions [ firstUnprocessable . key . toString ( ) ] . nonce ; for ( let i = 0 ; i < remainingNonces ; i += 1 ) { const { key } = clonedHeap . pop ( ) as { key : bigint ; } ; if ( lastPromotedNonce + BigInt ( 1 ) === key ) { promotableTx . push ( this . _transactions [ key . toString ( ) ] ) ; lastPromotedNonce = this . _transactions [ key . toString ( ) ] . nonce ; } } return promotableTx ; } private _demoteAfter ( nonce ) { this . _processable = this . _processable . filter ( processableNonce => processableNonce < nonce ) ; this . _sortProcessable ( ) ; } private _highestNonce ( ) { const highestNonce = BigInt ( - 1 ) ; const { keys } = this . _nonceHeap ; if ( ! keys ) { return highestNonce ; } return keys . reduce ( ( prev , current ) => { if ( current > prev ) { return current ; } return prev ; } , highestNonce ) ; } private _sortProcessable ( ) { this . _processable . sort ( ( a , b ) => { if ( a - b > BigInt ( 0 ) ) { return 1 ; } if ( a - b < BigInt ( 0 ) ) { return - 1 ; } return 0 ; } ) ; } }