Files
zoo/zdk/test/multiroutingcomplex.test.ts
2023-02-18 15:03:39 -06:00

466 lines
15 KiB
TypeScript

// @ts-ignore
import seedrandom from 'seedrandom'
import { findMultiRouting, Graph } from '../src/entities/MultiRouter'
import {
RConstantProductPool,
Pool,
RToken,
MultiRoute,
RouteStatus,
RouteLeg,
RHybridPool
} from '../src/types/MultiRouterTypes'
import { getBigNumber } from '../src/utils/MultiRouterMath'
import { checkRouteResult } from './snapshots/snapshot'
const testSeed = '2' // Change it to change random generator values
const rnd: () => number = seedrandom(testSeed) // random [0, 1)
const GAS_PRICE = 1 * 200 * 1e-9
const MIN_TOKEN_PRICE = 1e-6
const MAX_TOKEN_PRICE = 1e6
const STABLE_TOKEN_PRICE = 1
const MIN_POOL_RESERVE = 1e9
const MAX_POOL_RESERVE = 1e31
const MIN_POOL_IMBALANCE = 1 / (1 + 1e-3)
const MAX_POOL_IMBALANCE = 1 + 1e-3
const MIN_LIQUIDITY = 1000
const MAX_LIQUIDITY = Math.pow(2, 110)
const MIN_HYBRID_A = 200
const MAX_HYBRID_A = 300000
interface Variants {
[key: string]: number
}
function choice(rnd: () => number, obj: Variants) {
let total = 0
Object.entries(obj).forEach(([_, p]) => (total += p))
if (total <= 0) throw new Error('Error 62')
const val = rnd() * total
let past = 0
for (let k in obj) {
past += obj[k]
if (past >= val) return k
}
throw new Error('Error 70')
}
function getRandom(rnd: () => number, min: number, max: number) {
const minL = Math.log(min)
const maxL = Math.log(max)
const v = rnd() * (maxL - minL) + minL
const res = Math.exp(v)
console.assert(res <= max && res >= min, 'Random value is out of the range')
return res
}
function getTokenPrice(rnd: () => number) {
const price = getRandom(rnd, MIN_TOKEN_PRICE, MAX_TOKEN_PRICE)
return price
}
function getPoolReserve(rnd: () => number) {
return getRandom(rnd, MIN_POOL_RESERVE, MAX_POOL_RESERVE)
}
function getPoolFee(rnd: () => number) {
const fees = [0.003, 0.001, 0.0005]
const cmd = choice(rnd, {
0: 1,
1: 1,
2: 1
})
return fees[parseInt(cmd)]
}
function getPoolImbalance(rnd: () => number) {
return getRandom(rnd, MIN_POOL_IMBALANCE, MAX_POOL_IMBALANCE)
}
function getCPPool(rnd: () => number, t0: RToken, t1: RToken, price: number) {
if (rnd() < 0.5) {
const t = t0
t0 = t1
t1 = t
price = 1 / price
}
const fee = getPoolFee(rnd)
const imbalance = getPoolImbalance(rnd)
let reserve0 = getPoolReserve(rnd)
let reserve1 = reserve0 * price * imbalance
const maxReserve = Math.max(reserve0, reserve1)
if (maxReserve > MAX_LIQUIDITY) {
const reduceRate = (maxReserve / MAX_LIQUIDITY) * 1.00000001
reserve0 /= reduceRate
reserve1 /= reduceRate
}
const minReserve = Math.min(reserve0, reserve1)
if (minReserve < MIN_LIQUIDITY) {
const raseRate = (MIN_LIQUIDITY / minReserve) * 1.00000001
reserve0 *= raseRate
reserve1 *= raseRate
}
console.assert(reserve0 >= MIN_LIQUIDITY && reserve0 <= MAX_LIQUIDITY, 'Error reserve0 clculation')
console.assert(reserve1 >= MIN_LIQUIDITY && reserve1 <= MAX_LIQUIDITY, 'Error reserve1 clculation ' + reserve1)
return new RConstantProductPool({
token0: t0,
token1: t1,
address: `pool cp ${t0.name} ${t1.name} ${reserve0} ${price} ${fee}`,
reserve0: getBigNumber(undefined, reserve0),
reserve1: getBigNumber(undefined, reserve1),
fee
})
}
function getPoolA(rnd: () => number) {
return Math.floor(getRandom(rnd, MIN_HYBRID_A, MAX_HYBRID_A))
}
// price is always 1
function getHybridPool(rnd: () => number, t0: RToken, t1: RToken) {
const fee = getPoolFee(rnd)
const imbalance = getPoolImbalance(rnd)
const A = getPoolA(rnd)
let reserve0 = getPoolReserve(rnd)
let reserve1 = reserve0 * STABLE_TOKEN_PRICE * imbalance
const maxReserve = Math.max(reserve0, reserve1)
if (maxReserve > MAX_LIQUIDITY) {
const reduceRate = (maxReserve / MAX_LIQUIDITY) * 1.00000001
reserve0 /= reduceRate
reserve1 /= reduceRate
}
const minReserve = Math.min(reserve0, reserve1)
if (minReserve < MIN_LIQUIDITY) {
const raseRate = (MIN_LIQUIDITY / minReserve) * 1.00000001
reserve0 *= raseRate
reserve1 *= raseRate
}
console.assert(reserve0 >= MIN_LIQUIDITY && reserve0 <= MAX_LIQUIDITY, 'Error reserve0 clculation')
console.assert(reserve1 >= MIN_LIQUIDITY && reserve1 <= MAX_LIQUIDITY, 'Error reserve1 clculation ' + reserve1)
return new RHybridPool({
token0: t0,
token1: t1,
address: `pool hb ${t0.name} ${t1.name} ${reserve0} ${1} ${fee}`,
reserve0: getBigNumber(undefined, reserve0),
reserve1: getBigNumber(undefined, reserve1),
fee,
A
})
}
function getRandomPool(rnd: () => number, t0: RToken, t1: RToken, price: number) {
if (price !== STABLE_TOKEN_PRICE) return getCPPool(rnd, t0, t1, price)
if (rnd() < 0.5) getCPPool(rnd, t0, t1, price)
return getHybridPool(rnd, t0, t1)
}
interface Network {
tokens: RToken[]
prices: number[]
pools: Pool[]
gasPrice: number
}
function createNetwork(rnd: () => number, tokenNumber: number, density: number): Network {
const tokens = []
const prices = []
for (var i = 0; i < tokenNumber; ++i) {
tokens.push({ name: '' + i, address: '' + i })
if (i <= tokenNumber * 0.3) prices.push(STABLE_TOKEN_PRICE)
else prices.push(getTokenPrice(rnd))
}
const pools: Pool[] = []
for (i = 0; i < tokenNumber; ++i) {
for (var j = i + 1; j < tokenNumber; ++j) {
const r = rnd()
if (r < density) {
pools.push(getRandomPool(rnd, tokens[i], tokens[j], prices[i] / prices[j]))
}
if (r < density * density) {
// second pool
pools.push(getRandomPool(rnd, tokens[i], tokens[j], prices[i] / prices[j]))
}
if (r < density * density * density) {
// third pool
pools.push(getRandomPool(rnd, tokens[i], tokens[j], prices[i] / prices[j]))
}
if (r < Math.pow(density, 4)) {
// third pool
pools.push(getRandomPool(rnd, tokens[i], tokens[j], prices[i] / prices[j]))
}
if (r < Math.pow(density, 5)) {
// third pool
pools.push(getRandomPool(rnd, tokens[i], tokens[j], prices[i] / prices[j]))
}
}
}
return {
tokens,
prices,
pools,
gasPrice: GAS_PRICE
}
}
function expectToBeClose(a: number, b: number, max: number) {
expect(Math.abs(a / b - 1)).toBeLessThan(max)
}
function getTokenPools(network: Network): Map<RToken, Pool[]> {
const tokenPools = new Map<RToken, Pool[]>()
network.pools.forEach(p => {
const pools0 = tokenPools.get(p.token0)
if (pools0) {
pools0.push(p)
} else {
tokenPools.set(p.token0, [p])
}
const pools1 = tokenPools.get(p.token1)
if (pools1) {
pools1.push(p)
} else {
tokenPools.set(p.token1, [p])
}
})
return tokenPools
}
function getAllConnectedTokens(start: RToken, tokenPools: Map<RToken, Pool[]>): Set<RToken> {
const connected = new Set<RToken>()
const nextTokens = [start]
while (nextTokens.length) {
const token = nextTokens.pop() as RToken
if (connected.has(token)) {
continue
}
connected.add(token)
tokenPools.get(token)?.forEach(p => {
const token2 = token == p.token0 ? p.token1 : p.token0
nextTokens.push(token2)
})
}
return connected
}
function checkRoute(
network: Network,
from: RToken,
to: RToken,
amountIn: number,
baseToken: RToken,
gasPrice: number,
route: MultiRoute
) {
const tokenPools = getTokenPools(network)
const connectedTokens = getAllConnectedTokens(from, tokenPools)
if (!connectedTokens.has(to)) {
expect(route.status).toEqual(RouteStatus.NoWay)
return
}
const basePricesAreSet = connectedTokens.has(baseToken)
// amountIn checks
if (route.status === RouteStatus.Success) expectToBeClose(route.amountIn, amountIn, 1e-13)
else if (route.status === RouteStatus.Partial) {
expect(route.amountIn).toBeLessThan(amountIn)
expect(route.amountIn).toBeGreaterThan(0)
}
// amountOut checks
if (route.status !== RouteStatus.NoWay) expect(route.amountOut).toBeGreaterThan(0)
const outPriceToIn = network.prices[parseInt(to.name)] / network.prices[parseInt(from.name)]
// Slippage is always not-negative
expect(route.amountOut).toBeLessThanOrEqual((route.amountIn / outPriceToIn) * 1.002)
// gasSpent checks
const poolMap = new Map<string, Pool>()
network.pools.forEach(p => poolMap.set(p.address, p))
const expectedGasSpent = route.legs.reduce((a, b) => a + (poolMap.get(b.address)?.swapGasCost as number), 0)
expect(route.gasSpent).toEqual(expectedGasSpent)
// totalAmountOut checks
if (route.status === RouteStatus.NoWay) {
expect(route.totalAmountOut).toEqual(0)
} else if (basePricesAreSet) {
const outPriceToBase = network.prices[parseInt(baseToken.name)] / network.prices[parseInt(to.name)]
const expectedTotalAmountOut = route.amountOut - route.gasSpent * gasPrice * outPriceToBase
expectToBeClose(route.totalAmountOut, expectedTotalAmountOut, MAX_POOL_IMBALANCE + 1e-7)
} else {
expect(route.totalAmountOut).toEqual(route.amountOut)
}
// legs checks
if (route.status !== RouteStatus.NoWay) expect(route.legs.length).toBeGreaterThan(0)
const usedPools = new Map<string, boolean>()
const usedTokens = new Map<RToken, RouteLeg[]>()
route.legs.forEach(l => {
expect(usedPools.get(l.address)).toBeUndefined()
usedPools.set(l.address, true)
const pool = poolMap.get(l.address) as Pool
usedTokens.set(pool.token0, usedTokens.get(pool.token0) || [])
usedTokens.get(pool.token0)?.push(l)
usedTokens.set(pool.token1, usedTokens.get(pool.token1) || [])
usedTokens.get(pool.token1)?.push(l)
})
usedTokens.forEach((legs, t) => {
if (t === from) {
expect(legs.length).toBeGreaterThan(0)
expect(legs.every(l => l.token === from)).toBeTruthy()
expect(legs[legs.length - 1].swapPortion).toEqual(1)
} else if (t === to) {
expect(legs.length).toBeGreaterThan(0)
expect(legs.some(l => l.token === to)).toBeFalsy()
} else {
expect(legs.length).toBeGreaterThanOrEqual(2)
expect(legs[0].token).not.toEqual(t)
expect(legs[legs.length - 1].token).toEqual(t)
expect(legs[legs.length - 1].swapPortion).toEqual(1)
let inputFlag = true
let absolutePortion = 0
legs.forEach(l => {
if (l.token !== t) {
expect(inputFlag).toBeTruthy()
} else {
inputFlag = false
absolutePortion += l.absolutePortion
expect(l.swapPortion).toBeGreaterThan(0)
expect(l.swapPortion).toBeLessThanOrEqual(1)
}
})
expectToBeClose(absolutePortion, 1, 1e-12)
}
})
}
// Just for testing
// @ts-ignore
function exportNetwork(network: Network, from: RToken, to: RToken, route: MultiRoute) {
const allPools = new Map<string, Pool>()
network.pools.forEach(p => allPools.set(p.address, p))
const usedPools = new Map<string, boolean>()
route.legs.forEach(l => usedPools.set(l.address, l.token === allPools.get(l.address)?.token0))
function edgeStyle(p: Pool) {
const u = usedPools.get(p.address)
if (u === undefined) return ''
if (u) return ', value: 2, arrows: "to"'
else return ', value: 2, arrows: "from"'
}
function nodeLabel(t: RToken) {
if (t === from) return `${t.name}: ${route.amountIn}`
if (t === to) return `${t.name}: ${route.amountOut}`
return t.name
}
const nodes = `var nodes = new vis.DataSet([
${network.tokens.map(t => `{ id: ${t.name}, label: "${nodeLabel(t)}"}`).join(',\n\t\t')}
]);\n`
const edges = `var edges = new vis.DataSet([
${network.pools.map(p => `{ from: ${p.token0.name}, to: ${p.token1.name}${edgeStyle(p)}}`).join(',\n\t\t')}
]);\n`
const data = `var data = {
nodes: nodes,
edges: edges,
};\n`
const fs = require('fs')
fs.writeFileSync('D:/Info/Notes/GraphVisualization/data.js', nodes + edges + data)
}
function chooseRandomTokens(rnd: () => number, network: Network): [RToken, RToken, RToken] {
const num = network.tokens.length
const token0 = Math.floor(rnd() * num)
const token1 = (token0 + 1 + Math.floor(rnd() * (num - 1))) % num
expect(token0).not.toEqual(token1)
const tokenBase = Math.floor(rnd() * num)
return [network.tokens[token0], network.tokens[token1], network.tokens[tokenBase]]
}
const network = createNetwork(rnd, 20, 0.3)
it('Token price calculation is correct', () => {
const baseTokenIndex = 0
const g = new Graph(network.pools, network.tokens[baseTokenIndex], network.gasPrice)
g.vertices.forEach(v => {
const tokenIndex = parseInt(v.token.name)
if (tokenIndex === baseTokenIndex) {
expectToBeClose(v.price, 1, 1e-10)
}
if (v.price !== 0) {
expectToBeClose(
v.price,
network.prices[tokenIndex] / network.prices[baseTokenIndex],
5 * (MAX_POOL_IMBALANCE - 1)
)
}
})
})
it(`Multirouter for ${network.tokens.length} tokens and ${network.pools.length} pools (200 times)`, () => {
for (var i = 0; i < 200; ++i) {
const [t0, t1, tBase] = chooseRandomTokens(rnd, network)
const amountIn = getRandom(rnd, 1e6, 1e24)
const route = findMultiRouting(t0, t1, amountIn, network.pools, tBase, network.gasPrice)
checkRoute(network, t0, t1, amountIn, tBase, network.gasPrice, route)
checkRouteResult('top20-' + i, route.totalAmountOut)
}
})
it(`Multirouter-100 for ${network.tokens.length} tokens and ${network.pools.length} pools`, () => {
for (var i = 0; i < 10; ++i) {
const [t0, t1, tBase] = chooseRandomTokens(rnd, network)
const amountIn = getRandom(rnd, 1e6, 1e24)
const route = findMultiRouting(t0, t1, amountIn, network.pools, tBase, network.gasPrice, 100)
checkRoute(network, t0, t1, amountIn, tBase, network.gasPrice, route)
checkRouteResult('m100-' + i, route.totalAmountOut)
}
})
it(`Multirouter path quantity check`, () => {
const rndInternal: () => number = seedrandom('00')
const steps = [1, 2, 4, 10, 20, 40, 100]
for (var i = 0; i < 5; ++i) {
const [t0, t1, tBase] = chooseRandomTokens(rndInternal, network)
const amountIn = getRandom(rndInternal, 1e6, 1e24)
let prevAmountOut = -1
steps.forEach(s => {
const route = findMultiRouting(t0, t1, amountIn, network.pools, tBase, network.gasPrice, s)
checkRoute(network, t0, t1, amountIn, tBase, network.gasPrice, route)
expect(route.totalAmountOut).toBeGreaterThan(prevAmountOut / 1.001)
prevAmountOut = route.totalAmountOut
checkRouteResult(`st-${i}-${s}`, route.totalAmountOut)
})
}
})
function makeTestForTiming(tokens: number, density: number, tests: number) {
const network2 = createNetwork(rnd, tokens, density)
it(`Multirouter timing test for ${tokens} tokens and ${network2.pools.length} pools (${tests} times)`, () => {
for (var i = 0; i < tests; ++i) {
const [t0, t1, tBase] = chooseRandomTokens(rnd, network)
const amountIn = getRandom(rnd, 1e6, 1e24)
findMultiRouting(t0, t1, amountIn, network2.pools, tBase, network2.gasPrice)
}
})
}
makeTestForTiming(10, 0.5, 1000)
makeTestForTiming(10, 0.9, 1000)