Skip to content Search Apps Documentation Source Content Run Reset Eval Playground File Folder Download Copy Actions State String Boolean Number Struct Map Slice Pointer Function Closure Reference Nil Package Type Interface Unknown

pool_selection.gno

7.75 Kb · 238 lines
  1package impl
  2
  3import (
  4	"errors"
  5	"sort"
  6	"strconv"
  7
  8	pdca "gno.land/p/gnoswap/order/dca/v0"
  9	ufmt "gno.land/p/nt/ufmt/v0"
 10
 11	"gno.land/r/gnoswap/pool"
 12)
 13
 14// Pool selection.
 15//
 16// A round trades on one direct pool of the pair, chosen at execution time:
 17//
 18//  1. candidates: whitelisted pools of the pair, one per fee tier, by fee
 19//  2. price limit: each pool sells only down to the pair price limit
 20//     (see price_limit.gno); a pair direction without a limit, a pool
 21//     already past it, or a pool displaced far on its favorable side
 22//     (Config.MaxPoolPriceDeviationRate) is ineligible without a quote, and
 23//     so is every pool while the limit is older than
 24//     Config.MaxPairPriceLimitAge
 25//  3. ranking: the pool whose DrySwap of the full round amount, within its
 26//     price limit, returns the most output, consuming all input;
 27//     ties keep the lower fee
 28//
 29// The price limit bounds the ticks a quote or a swap may cross, so a pool
 30// without liquidity near its price costs bounded gas and is simply ineligible
 31// when it cannot fill the round within the limit. Liquidity outside the
 32// current tick still counts.
 33//
 34// To save gas, a round quotes only when the pair has two or more pools.
 35// A single pool is used directly; the round reverts
 36// if that pool cannot absorb the full input within the limit.
 37
 38// poolCandidate is one pool of the pair and its evaluation for a round.
 39type poolCandidate struct {
 40	poolPath          string
 41	fee               uint32
 42	sqrtPriceLimitX96 string // swap price limit under the pair price limit
 43	ineligibleCode    string // why the pool is ineligible, as a code; "" when eligible
 44	ineligibleReason  string // ineligibleCode in words, with details
 45	isQuoted          bool
 46	quotedAmountOut   int64 // pool output for the full round
 47	partialAmountOut  int64 // pool output of the consumed input of a partial fill; 0 otherwise
 48}
 49
 50func (c *poolCandidate) isEligible() bool { return c.ineligibleCode == "" }
 51
 52// poolWhitelist is the read-only membership contract used by pool selection.
 53// Production passes the common whitelist realm's read-only view; focused
 54// selection tests use an in-memory tree.
 55type poolWhitelist interface {
 56	Has(key string) bool
 57}
 58
 59// getCandidatePools returns the whitelisted pools of the pair,
 60// ordered by fee tier.
 61func getCandidatePools(whitelistedPools poolWhitelist, inputToken string, outputToken string) []*poolCandidate {
 62	tickSpacings := pool.GetFeeAmountTickSpacings()
 63
 64	fees := make([]int, 0, len(tickSpacings))
 65	for fee := range tickSpacings {
 66		fees = append(fees, int(fee))
 67	}
 68
 69	sort.Ints(fees)
 70
 71	candidates := []*poolCandidate{}
 72
 73	for _, fee := range fees {
 74		poolPath := pool.GetPoolPath(inputToken, outputToken, uint32(fee))
 75		if whitelistedPools.Has(poolPath) && pool.ExistsPoolPath(poolPath) {
 76			candidates = append(candidates, &poolCandidate{poolPath: poolPath, fee: uint32(fee)})
 77		}
 78	}
 79
 80	return candidates
 81}
 82
 83// selectPool evaluates the pair's whitelisted pools for a round of amountIn
 84// under limit, the pair price limit (nil if none is set), and
 85// maxDeviationRate (Config.MaxPoolPriceDeviationRate), and maxLimitAge
 86// (Config.MaxPairPriceLimitAge), and returns the chosen
 87// pool (nil if none can fill it) with all candidates.
 88// quoteAll quotes every pool, even when the pair has only one.
 89func selectPool(
 90	whitelistedPools poolWhitelist,
 91	limit *pdca.PairPriceLimit,
 92	maxDeviationRate int64,
 93	maxLimitAge int64,
 94	inputToken string,
 95	outputToken string,
 96	amountIn int64,
 97	quoteAll bool,
 98) (*poolCandidate, []*poolCandidate) {
 99	candidates := getCandidatePools(whitelistedPools, inputToken, outputToken)
100	if len(candidates) == 0 {
101		return nil, candidates
102	}
103
104	zeroForOne, _, _ := swapDirection(inputToken, outputToken)
105	for _, candidate := range candidates {
106		candidate.sqrtPriceLimitX96, candidate.ineligibleCode, candidate.ineligibleReason = poolSqrtPriceLimit(
107			candidate.poolPath, candidate.fee, zeroForOne, limit, maxDeviationRate, maxLimitAge,
108		)
109	}
110
111	if len(candidates) == 1 && !quoteAll {
112		if !candidates[0].isEligible() {
113			return nil, candidates
114		}
115
116		return candidates[0], candidates
117	}
118
119	var bestCandidate *poolCandidate
120
121	for _, candidate := range candidates {
122		if !candidate.isEligible() {
123			continue
124		}
125
126		quotedAmountOut, code, err := quoteExactIn(inputToken, outputToken, candidate.fee, candidate.sqrtPriceLimitX96, amountIn)
127		if err != nil {
128			candidate.ineligibleCode = code
129			candidate.ineligibleReason = err.Error()
130
131			if code == codePartialFill {
132				candidate.partialAmountOut = quotedAmountOut
133			}
134
135			continue
136		}
137
138		candidate.isQuoted = true
139		candidate.quotedAmountOut = quotedAmountOut
140
141		if bestCandidate == nil || quotedAmountOut > bestCandidate.quotedAmountOut {
142			bestCandidate = candidate
143		}
144	}
145
146	return bestCandidate, candidates
147}
148
149// quoteReferenceAmountOut quotes selling amountIn at once, now, on the pair's
150// best whitelisted pool within the pair price limit: what a one-off swap of
151// the whole order would return. Order fills are measured against it. It is 0
152// when no pool can absorb the whole amount within the limit.
153func quoteReferenceAmountOut(
154	whitelistedPools poolWhitelist,
155	limit *pdca.PairPriceLimit,
156	maxDeviationRate int64,
157	maxLimitAge int64,
158	inputToken string,
159	outputToken string,
160	amountIn int64,
161) int64 {
162	selectedPool, _ := selectPool(whitelistedPools, limit, maxDeviationRate, maxLimitAge, inputToken, outputToken, amountIn, true)
163	if selectedPool == nil {
164		return 0
165	}
166
167	return selectedPool.quotedAmountOut
168}
169
170// selectRoundPool is selectPool for execution. When no pool can fill the
171// round, it returns an error listing each candidate's reason.
172// A pair without a whitelisted pool has no candidates.
173func selectRoundPool(
174	whitelistedPools poolWhitelist,
175	limit *pdca.PairPriceLimit,
176	maxDeviationRate int64,
177	maxLimitAge int64,
178	group *pdca.Group,
179	amountIn int64,
180) (*poolCandidate, error) {
181	selectedPool, candidates := selectPool(whitelistedPools, limit, maxDeviationRate, maxLimitAge, group.InputToken(), group.OutputToken(), amountIn, false)
182	if selectedPool != nil {
183		return selectedPool, nil
184	}
185
186	details := ufmt.Sprintf("groupId(%s)", group.ID())
187	for _, candidate := range candidates {
188		details += ufmt.Sprintf("; %s: %s", candidate.poolPath, candidate.ineligibleReason)
189	}
190
191	return nil, makeErrorWithDetails(errNoEligiblePool, details)
192}
193
194// quoteExactIn simulates selling amountIn on the pair's pool of fee tier fee,
195// down to sqrtPriceLimitX96, and returns the pool output.
196// It fails unless the whole input is consumed within the limit, and then
197// also returns the ineligibility code of the failure. A partial fill
198// (codePartialFill) returns the output of the input it consumed, 0 when the
199// pool swapped nothing, such as one without liquidity; every other failure
200// returns 0.
201func quoteExactIn(inputToken string, outputToken string, fee uint32, sqrtPriceLimitX96 string, amountIn int64) (int64, string, error) {
202	zeroForOne, token0, token1 := swapDirection(inputToken, outputToken)
203
204	amount0, amount1, err := pool.DrySwap(token0, token1, fee, zeroForOne, strconv.FormatInt(amountIn, 10), sqrtPriceLimitX96)
205	if err != nil {
206		return 0, codeQuoteFailed, err
207	}
208
209	consumedAmount, outputAmount := amount0, amount1
210	if !zeroForOne {
211		consumedAmount, outputAmount = amount1, amount0
212	}
213
214	consumedAmountIn, err := strconv.ParseInt(consumedAmount, 10, 64)
215	if err != nil {
216		return 0, codeQuoteFailed, err
217	}
218
219	amountOut, err := strconv.ParseInt(outputAmount, 10, 64)
220	if err != nil {
221		return 0, codeQuoteFailed, err
222	}
223
224	if consumedAmountIn != amountIn {
225		partialAmountOut := int64(0)
226		if consumedAmountIn > 0 && amountOut < 0 {
227			partialAmountOut = -amountOut
228		}
229
230		return partialAmountOut, codePartialFill, ufmt.Errorf("quote consumed %d of %d input", consumedAmountIn, amountIn)
231	}
232
233	if amountOut >= 0 {
234		return 0, codeNoOutput, errors.New("quote returned no output")
235	}
236
237	return -amountOut, "", nil
238}