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}