import cloneDeep from 'lodash.clonedeep' ; import { PRICE_ERROR_TOLERANCE } from '../config' ; import { BigNumber as OldBigNumber , bnum , ZERO , ONE , INFINITY , } from '../utils/bignumber' ; import { SwapTypes , NewPath , Swap } from '../types' ; import { getEffectivePriceSwapForPath , getSpotPriceAfterSwapForPath , getDerivativeSpotPriceAfterSwapForPath , getOutputAmountSwapForPath , EVMgetOutputAmountSwap , } from './helpersClass' ; import { BigNumber , formatFixed } from '@ethersproject/bignumber' ; export const optimizeSwapAmounts = ( paths , swapType , totalSwapAmount , initialSwapAmounts , highestLimitAmounts , inputDecimals , outputDecimals , initialNumPaths , maxPools , costReturnToken ) : [ NewPath [ ] , OldBigNumber [ ] , OldBigNumber ] => { let bestTotalReturnConsideringFees = swapType === SwapTypes . SwapExactIn ? INFINITY . times ( - 1 ) : INFINITY ; let bestSwapAmounts = [ ] ; let bestPaths = [ ] ; let swapAmounts = initialSwapAmounts . map ( ( amount ) => bnum ( formatFixed ( amount , inputDecimals ) ) ) ; for ( let b = initialNumPaths ; b <= paths . length ; b ++ ) { if ( b != initialNumPaths ) { const humanTotalSwapAmount = formatFixed ( totalSwapAmount , inputDecimals ) ; const newSwapAmount = OldBigNumber . min . apply ( null , [ bnum ( humanTotalSwapAmount ) . times ( bnum ( 1 / b ) ) , formatFixed ( highestLimitAmounts [ b - 1 ] , inputDecimals ) , ] ) ; swapAmounts . forEach ( ( swapAmount , i ) => { swapAmounts [ i ] = swapAmount . times ( ONE . minus ( newSwapAmount . div ( humanTotalSwapAmount ) ) ) ; } ) ; swapAmounts . push ( newSwapAmount ) ; } const { paths : selectedPaths , swapAmounts : bestAmounts } = optimizePathDistribution ( paths , swapType , totalSwapAmount , swapAmounts , inputDecimals ) ; swapAmounts = bestAmounts ; const totalReturn = calcTotalReturn ( selectedPaths , swapType , swapAmounts , inputDecimals ) ; const totalNumberOfPools = selectedPaths . reduce ( ( acc , path ) => acc + path . swaps . length , 0 ) ; const costReturnTokenHuman = formatFixed ( costReturnToken , outputDecimals ) ; let improvementCondition = false ; let totalReturnConsideringFees = ZERO ; const gasFees = bnum ( totalNumberOfPools ) . times ( costReturnTokenHuman ) ; if ( swapType === SwapTypes . SwapExactIn ) { totalReturnConsideringFees = totalReturn . minus ( gasFees ) ; improvementCondition = totalReturnConsideringFees . isGreaterThan ( bestTotalReturnConsideringFees ) ; } else { totalReturnConsideringFees = totalReturn . plus ( gasFees ) ; improvementCondition = totalReturnConsideringFees . isLessThan ( bestTotalReturnConsideringFees ) ; } if ( ! improvementCondition ) break ; bestSwapAmounts = [ ... swapAmounts ] ; bestPaths = [ ... selectedPaths ] ; bestTotalReturnConsideringFees = totalReturnConsideringFees ; if ( totalNumberOfPools >= maxPools ) break ; } bestPaths = bestPaths . filter ( ( _ , i ) => ! bestSwapAmounts [ i ] . isZero ( ) ) ; bestSwapAmounts = bestSwapAmounts . filter ( ( swapAmount ) => ! swapAmount . isZero ( ) ) ; return [ bestPaths , bestSwapAmounts , bestTotalReturnConsideringFees ] ; } ; /**
 * For a fixed number of possible paths, finds the optimal distribution of swap amounts to maximise output
 */ const optimizePathDistribution = ( allPaths , swapType , totalSwapAmount , initialSwapAmounts , inputDecimals ) : { paths : NewPath [ ] ; swapAmounts : OldBigNumber [ ] ; } => { let [ selectedPaths , exceedingAmounts ] = getBestPathIds ( allPaths , swapType , initialSwapAmounts , inputDecimals ) ; let swapAmounts = initialSwapAmounts ; if ( initialSwapAmounts . length === 1 ) { return { swapAmounts , paths : selectedPaths , } ; } const humanTotalSwapAmount = bnum ( formatFixed ( totalSwapAmount , inputDecimals ) ) ; let newSelectedPaths = selectedPaths ; const historyOfSortedPathIds = [ ] ; let sortedPathIdsJSON = JSON . stringify ( newSelectedPaths . map ( ( { id } ) => id ) . sort ( ) ) ; while ( ! historyOfSortedPathIds . includes ( sortedPathIdsJSON ) ) { historyOfSortedPathIds . push ( sortedPathIdsJSON ) ; selectedPaths = newSelectedPaths ; [ swapAmounts , exceedingAmounts ] = iterateSwapAmounts ( selectedPaths , swapType , humanTotalSwapAmount , swapAmounts , exceedingAmounts ) ; [ newSelectedPaths , exceedingAmounts ] = getBestPathIds ( allPaths , swapType , swapAmounts , inputDecimals ) ; if ( newSelectedPaths . length === 0 ) break ; const pathIds = newSelectedPaths . map ( ( { id } ) => id ) . sort ( ) ; sortedPathIdsJSON = JSON . stringify ( pathIds ) ; } return { swapAmounts , paths : selectedPaths , } ; } ; export const formatSwaps = ( bestPaths , swapType , totalSwapAmount , bestSwapAmounts ) : [ Swap [ ] [ ] , OldBigNumber , OldBigNumber ] => { const swaps = [ ] ; let highestSwapAmt = bestSwapAmounts [ 0 ] ; let largestSwapPath = bestPaths [ 0 ] ; let bestTotalReturn = ZERO ; bestPaths . forEach ( ( path , i ) => { const swapAmount = bestSwapAmounts [ i ] ; if ( swapAmount . gt ( highestSwapAmt ) ) { highestSwapAmt = swapAmount ; largestSwapPath = path ; } const poolPairData = path . poolPairData ; const pathSwaps = [ ] ; const amounts = [ ] ; let returnAmount ; const n = poolPairData . length ; amounts . push ( swapAmount ) ; if ( swapType === SwapTypes . SwapExactIn ) { for ( let i = 0 ; i < n ; i ++ ) { amounts . push ( EVMgetOutputAmountSwap ( path . pools [ i ] , poolPairData [ i ] , SwapTypes . SwapExactIn , amounts [ amounts . length - 1 ] ) ) ; const swap = { pool : path . swaps [ i ] . pool , tokenIn : path . swaps [ i ] . tokenIn , tokenOut : path . swaps [ i ] . tokenOut , swapAmount : amounts [ i ] . toString ( ) , tokenInDecimals : path . poolPairData [ i ] . decimalsIn , tokenOutDecimals : path . poolPairData [ i ] . decimalsOut , } ; pathSwaps . push ( swap ) ; } returnAmount = amounts [ n ] ; } else { for ( let i = 0 ; i < n ; i ++ ) { amounts . unshift ( EVMgetOutputAmountSwap ( path . pools [ n - 1 - i ] , poolPairData [ n - 1 - i ] , SwapTypes . SwapExactOut , amounts [ 0 ] ) ) ; const swap = { pool : path . swaps [ n - 1 - i ] . pool , tokenIn : path . swaps [ n - 1 - i ] . tokenIn , tokenOut : path . swaps [ n - 1 - i ] . tokenOut , swapAmount : amounts [ 1 ] . toString ( ) , tokenInDecimals : path . poolPairData [ n - 1 - i ] . decimalsIn , tokenOutDecimals : path . poolPairData [ n - 1 - i ] . decimalsOut , } ; pathSwaps . unshift ( swap ) ; } returnAmount = amounts [ 0 ] ; } swaps . push ( pathSwaps ) ; bestTotalReturn = bestTotalReturn . plus ( returnAmount ) ; } ) ; if ( swaps . length > 0 ) { const totalSwapAmountWithRoundingErrors = bestSwapAmounts . reduce ( ( a , b ) => a . plus ( b ) , ZERO ) ; const dust = totalSwapAmount . minus ( totalSwapAmountWithRoundingErrors ) ; if ( swapType === SwapTypes . SwapExactIn ) { swaps [ 0 ] [ 0 ] . swapAmount = bnum ( swaps [ 0 ] [ 0 ] . swapAmount as string ) . plus ( dust ) . toString ( ) ; } else { const firstPathLastPoolIndex = bestPaths [ 0 ] . swaps . length - 1 ; swaps [ 0 ] [ firstPathLastPoolIndex ] . swapAmount = bnum ( swaps [ 0 ] [ firstPathLastPoolIndex ] . swapAmount as string ) . plus ( dust ) . toString ( ) ; } } if ( bestTotalReturn . eq ( 0 ) ) return [ [ ] , ZERO , ZERO ] ; const marketSp = getSpotPriceAfterSwapForPath ( largestSwapPath , swapType , ZERO ) ; return [ swaps , bestTotalReturn , marketSp ] ; } ; function getBestPathIds ( originalPaths , swapType , swapAmounts , inputDecimals ) { const selectedPaths = [ ] ; const selectedPathExceedingAmounts = [ ] ; const paths = cloneDeep ( originalPaths ) ; const sortedSwapAmounts = [ ... swapAmounts ] . sort ( ( a , b ) => { return b . minus ( a ) . toNumber ( ) ; } ) ; sortedSwapAmounts . forEach ( ( swapAmount ) => { let bestPathIndex = - 1 ; let bestEffectivePrice = INFINITY ; paths . forEach ( ( path , i ) => { if ( bnum ( formatFixed ( path . limitAmount , inputDecimals ) ) . gte ( swapAmount ) ) { let effectivePrice ; if ( bnum ( formatFixed ( path . limitAmount , inputDecimals ) ) . eq ( swapAmount ) ) { effectivePrice = INFINITY ; } else { effectivePrice = getEffectivePriceSwapForPath ( path , swapType , swapAmount , inputDecimals ) ; } if ( effectivePrice . lte ( bestEffectivePrice ) ) { bestEffectivePrice = effectivePrice ; bestPathIndex = i ; } } } ) ; if ( bestPathIndex === - 1 ) { return [ [ ] , [ ] ] ; } selectedPaths . push ( paths [ bestPathIndex ] ) ; selectedPathExceedingAmounts . push ( swapAmount . minus ( bnum ( formatFixed ( paths [ bestPathIndex ] . limitAmount , inputDecimals ) ) ) ) ; paths . splice ( bestPathIndex , 1 ) ; } ) ; return [ selectedPaths , selectedPathExceedingAmounts ] ; } function iterateSwapAmounts ( selectedPaths , swapType , totalSwapAmount , swapAmounts , exceedingAmounts ) { let priceError = ONE ; let prices = [ ] ; let iterationCount = 0 ; while ( priceError . isGreaterThan ( PRICE_ERROR_TOLERANCE ) ) { [ prices , swapAmounts , exceedingAmounts ] = iterateSwapAmountsApproximation ( selectedPaths , swapType , totalSwapAmount , swapAmounts , exceedingAmounts , iterationCount ) ; const maxPrice = OldBigNumber . max . apply ( null , prices ) ; const minPrice = OldBigNumber . min . apply ( null , prices ) ; priceError = maxPrice . minus ( minPrice ) . div ( minPrice ) ; iterationCount ++ ; if ( iterationCount > 100 ) break ; } return [ swapAmounts , exceedingAmounts ] ; } function iterateSwapAmountsApproximation ( selectedPaths , swapType , totalSwapAmount , swapAmounts , exceedingAmounts , iterationCount ) { let sumInverseDerivativeSPaSs = ZERO ; let sumSPaSDividedByDerivativeSPaSs = ZERO ; const SPaSs = [ ] ; const derivativeSPaSs = [ ] ; swapAmounts . forEach ( ( swapAmount , i ) => { if ( ( iterationCount == 0 && swapAmount . gte ( ZERO ) && exceedingAmounts [ i ] . lte ( ZERO ) ) || ( iterationCount != 0 && swapAmount . gt ( ZERO ) && exceedingAmounts [ i ] . lt ( ZERO ) ) ) { const path = selectedPaths [ i ] ; const SPaS = getSpotPriceAfterSwapForPath ( path , swapType , swapAmount ) ; SPaSs . push ( SPaS ) ; const derivative_SPaS = getDerivativeSpotPriceAfterSwapForPath ( path , swapType , swapAmount ) ; derivativeSPaSs . push ( derivative_SPaS ) ; sumInverseDerivativeSPaSs = sumInverseDerivativeSPaSs . plus ( ONE . div ( derivative_SPaS ) ) ; sumSPaSDividedByDerivativeSPaSs = sumSPaSDividedByDerivativeSPaSs . plus ( SPaS . div ( derivative_SPaS ) ) ; } else { derivativeSPaSs . push ( bnum ( 'NaN' ) ) ; SPaSs . push ( bnum ( 'NaN' ) ) ; } } ) ; const weighted_average_SPaS = bnum ( sumSPaSDividedByDerivativeSPaSs . toNumber ( ) / sumInverseDerivativeSPaSs . toNumber ( ) ) ; swapAmounts . forEach ( ( swapAmount , i ) => { if ( ( iterationCount == 0 && swapAmount . gte ( ZERO ) && exceedingAmounts [ i ] . lte ( ZERO ) ) || ( iterationCount != 0 && swapAmount . gt ( ZERO ) && exceedingAmounts [ i ] . lt ( ZERO ) ) ) { const deltaSwapAmount = weighted_average_SPaS . minus ( SPaSs [ i ] ) . div ( derivativeSPaSs [ i ] ) ; swapAmounts [ i ] = swapAmounts [ i ] . plus ( deltaSwapAmount ) ; exceedingAmounts [ i ] = exceedingAmounts [ i ] . plus ( deltaSwapAmount ) ; } } ) ; while ( OldBigNumber . min . apply ( null , swapAmounts ) . lt ( ZERO ) || OldBigNumber . max . apply ( null , exceedingAmounts ) . gt ( ZERO ) ) { [ swapAmounts , exceedingAmounts ] = redistributeInputAmounts ( swapAmounts , exceedingAmounts , derivativeSPaSs ) ; } const pricesForViableAmounts = [ ] ; let swapAmountsSumWithRoundingErrors = ZERO ; swapAmounts . forEach ( ( swapAmount , i ) => { swapAmountsSumWithRoundingErrors = swapAmountsSumWithRoundingErrors . plus ( swapAmount ) ; if ( ( iterationCount == 0 && swapAmount . gte ( ZERO ) && exceedingAmounts [ i ] . lte ( ZERO ) ) || ( iterationCount != 0 && swapAmount . gt ( ZERO ) && exceedingAmounts [ i ] . lt ( ZERO ) ) ) pricesForViableAmounts . push ( getSpotPriceAfterSwapForPath ( selectedPaths [ i ] , swapType , swapAmount ) ) ; } ) ; const roundingError = totalSwapAmount . minus ( swapAmountsSumWithRoundingErrors ) ; for ( let i = 0 ; i < swapAmounts . length ; ++ i ) { if ( swapAmounts [ i ] . gt ( ZERO ) && exceedingAmounts [ i ] . lt ( ZERO ) ) { if ( swapAmounts [ i ] . plus ( roundingError ) . gt ( ZERO ) && exceedingAmounts [ i ] . plus ( roundingError ) . lt ( ZERO ) ) { swapAmounts [ i ] = swapAmounts [ i ] . plus ( roundingError ) ; exceedingAmounts [ i ] = exceedingAmounts [ i ] . plus ( roundingError ) ; break ; } } } return [ pricesForViableAmounts , swapAmounts , exceedingAmounts ] ; } function redistributeInputAmounts ( swapAmounts , exceedingAmounts , derivativeSPaSs ) { let sumInverseDerivativeSPaSsForViableAmounts = ZERO ; let sumInverseDerivativeSPaSsForNegativeAmounts = ZERO ; let sumInverseDerivativeSPaSsForExceedingAmounts = ZERO ; let sumNegativeOrExceedingSwapAmounts = ZERO ; swapAmounts . forEach ( ( swapAmount , i ) => { if ( swapAmount . lte ( ZERO ) ) { sumNegativeOrExceedingSwapAmounts = sumNegativeOrExceedingSwapAmounts . plus ( swapAmount ) ; sumInverseDerivativeSPaSsForNegativeAmounts = sumInverseDerivativeSPaSsForNegativeAmounts . plus ( ONE . div ( derivativeSPaSs [ i ] ) ) ; } else if ( exceedingAmounts [ i ] . gte ( ZERO ) ) { sumNegativeOrExceedingSwapAmounts = sumNegativeOrExceedingSwapAmounts . plus ( exceedingAmounts [ i ] ) ; sumInverseDerivativeSPaSsForExceedingAmounts = sumInverseDerivativeSPaSsForExceedingAmounts . plus ( ONE . div ( derivativeSPaSs [ i ] ) ) ; } else sumInverseDerivativeSPaSsForViableAmounts = sumInverseDerivativeSPaSsForViableAmounts . plus ( ONE . div ( derivativeSPaSs [ i ] ) ) ; } ) ; swapAmounts . forEach ( ( swapAmount , i ) => { if ( swapAmount . lte ( ZERO ) ) { swapAmounts [ i ] = ZERO ; exceedingAmounts [ i ] = exceedingAmounts [ i ] . minus ( swapAmount ) ; } else if ( exceedingAmounts [ i ] . gte ( ZERO ) ) { swapAmounts [ i ] = swapAmounts [ i ] . minus ( exceedingAmounts [ i ] ) ; exceedingAmounts [ i ] = ZERO ; } else { const deltaSwapAmount = sumNegativeOrExceedingSwapAmounts . times ( ONE . div ( derivativeSPaSs [ i ] ) ) . div ( sumInverseDerivativeSPaSsForViableAmounts ) ; swapAmounts [ i ] = swapAmounts [ i ] . plus ( deltaSwapAmount ) ; exceedingAmounts [ i ] = exceedingAmounts [ i ] . plus ( deltaSwapAmount ) ; } } ) ; if ( sumInverseDerivativeSPaSsForViableAmounts . isZero ( ) ) { if ( sumNegativeOrExceedingSwapAmounts . lt ( ZERO ) ) { swapAmounts . forEach ( ( swapAmount , i ) => { if ( exceedingAmounts [ i ] . isZero ( ) ) { const deltaSwapAmount = sumNegativeOrExceedingSwapAmounts . times ( ONE . div ( derivativeSPaSs [ i ] ) ) . div ( sumInverseDerivativeSPaSsForExceedingAmounts ) ; swapAmounts [ i ] = swapAmounts [ i ] . plus ( deltaSwapAmount ) ; exceedingAmounts [ i ] = exceedingAmounts [ i ] . plus ( deltaSwapAmount ) ; } } ) ; } else { swapAmounts . forEach ( ( swapAmount , i ) => { if ( swapAmounts [ i ] . isZero ( ) ) { const deltaSwapAmount = sumNegativeOrExceedingSwapAmounts . times ( ONE . div ( derivativeSPaSs [ i ] ) ) . div ( sumInverseDerivativeSPaSsForNegativeAmounts ) ; swapAmounts [ i ] = swapAmounts [ i ] . plus ( deltaSwapAmount ) ; exceedingAmounts [ i ] = exceedingAmounts [ i ] . plus ( deltaSwapAmount ) ; } } ) ; } } return [ swapAmounts , exceedingAmounts ] ; } export const calcTotalReturn = ( paths , swapType , swapAmounts , inputDecimals ) : OldBigNumber => { let totalReturn = new OldBigNumber ( 0 ) ; paths . forEach ( ( path , i ) => { totalReturn = totalReturn . plus ( getOutputAmountSwapForPath ( path , swapType , swapAmounts [ i ] , inputDecimals ) ) ; } ) ; return totalReturn ; } ;