price_limit.gno
11.13 Kb · 313 lines
1package impl
2
3import (
4 "time"
5
6 pdca "gno.land/p/gnoswap/order/dca/v0"
7 u256 "gno.land/p/gnoswap/uint256/v1"
8 bptree "gno.land/p/nt/bptree/v0"
9 ufmt "gno.land/p/nt/ufmt/v0"
10
11 "gno.land/r/gnoswap/pool"
12)
13
14// Pair price limits.
15//
16// A pair direction (inputToken -> outputToken) trades only with a price limit
17// set by the pool manager from an oracle price: minOutputPerInputX128,
18// the least pool output, in raw outputToken units before the execution fee,
19// per raw inputToken unit, in Q128.
20//
21// Every quote and swap of the pair passes it to the pool as sqrtPriceLimitX96,
22// after removing the pool's fee tier, so that:
23// - each unit of input is filled at a marginal rate of at least the limit,
24// which bounds what a round can lose to a moved pool price,
25// even when the keeper passes a loose amountOutMin;
26// - the pool walks ticks only between its current price and the limit,
27// which bounds the gas of a quote or a round on a pool without enough
28// liquidity near its price.
29//
30// A pool whose price is already past the limit is ineligible: it would have
31// to sell at a worse rate than the limit from the first unit.
32//
33// A pool whose price sits far on the favorable side of the limit is
34// ineligible too (Config.MaxPoolPriceDeviationRate): the limit derives from an
35// oracle price, not from each pool's price, so a pool displaced far from the
36// oracle price, such as an empty pool or one pushed past its liquidity, would
37// make its quote or swap walk every tick between its price and the limit.
38//
39// A limit set more than Config.MaxPairPriceLimitAge seconds ago leaves every
40// pool ineligible: the oracle price behind it may be gone, so rounds wait for
41// the pool manager to refresh it instead of trading at a stale price.
42
43// Sqrt price bounds a swap price limit is clamped to; the pool requires
44// a limit strictly inside (MIN_SQRT_RATIO, MAX_SQRT_RATIO).
45const (
46 minSqrtRatioPlusOne = "4295128740"
47 maxSqrtRatioMinusOne = "1461446703485210103287273052203988822378723970341"
48)
49
50// poolFeeDenominator is the denominator of pool fee tiers (3000 is 0.3%).
51const poolFeeDenominator uint64 = 1_000_000
52
53const q96Shift uint = 96
54
55// Ineligibility codes of a candidate pool, reported by GetExecutionQuote as
56// ineligibleCode next to the human-readable ineligibleReason. Keepers classify
57// a blocked round by code, never by reason text; "" means eligible.
58const (
59 codeNoPriceLimit = "no_price_limit" // the pair direction has no limit
60 codePriceLimitStale = "price_limit_stale" // the limit is older than its maximum age
61 codePricePastLimit = "price_past_limit" // the pool price is already past the limit
62 codePriceDisplaced = "price_displaced" // the pool price is too far on the favorable side
63 codePriceUnavailable = "price_unavailable" // the pool price could not be read
64 codePartialFill = "partial_fill" // the quote fills only part of the input
65 codeNoOutput = "no_output" // the quote returns no output
66 codeQuoteFailed = "quote_failed" // the pool rejected the quote
67)
68
69const (
70 reasonNoPriceLimit = "no price limit for the pair"
71 reasonPriceLimitStale = "pair price limit is older than its maximum age"
72 reasonInvalidLimitAge = "invalid max pair price limit age"
73 reasonPricePastLimit = "pool price is past the pair price limit"
74 reasonPriceDisplaced = "pool price deviates too far from the pair price limit"
75 reasonPoolPriceAbsent = "pool price unavailable"
76 reasonInvalidDeviation = "invalid max pool price deviation rate"
77)
78
79// getPairPriceLimit returns the price limit of selling inputToken for
80// outputToken, or nil if none is set.
81func getPairPriceLimit(pairPriceLimits *bptree.BPTree, inputToken string, outputToken string) *pdca.PairPriceLimit {
82 value := pairPriceLimits.Get(pdca.PairKey(inputToken, outputToken))
83 if value == nil {
84 return nil
85 }
86
87 return value.(*pdca.PairPriceLimit)
88}
89
90// calculateSqrtPriceLimitX96 converts minOutputPerInputX128 into the sqrt
91// price limit of a swap on a pool of fee tier fee in the given direction,
92// clamped to the range the pool accepts.
93//
94// The pool takes its fee from the input, so the marginal rate of a unit of
95// input is P*(1-fee) selling token0 (P = token1 per token0) and (1-fee)/P
96// selling token1. Requiring that rate to stay at or above L gives:
97//
98// zeroForOne: P >= L/(1-fee), a lower bound, rounded up
99// oneForZero: P <= (1-fee)/L, an upper bound, rounded down
100//
101// so the rounding never loosens the limit.
102func calculateSqrtPriceLimitX96(minOutputPerInputX128 *u256.Uint, fee uint32, zeroForOne bool) *u256.Uint {
103 minSqrtPrice := u256.MustFromDecimal(minSqrtRatioPlusOne)
104 maxSqrtPrice := u256.MustFromDecimal(maxSqrtRatioMinusOne)
105
106 if minOutputPerInputX128.IsZero() {
107 // No output floor: the bound the pool never reaches.
108 if zeroForOne {
109 return minSqrtPrice
110 }
111
112 return maxSqrtPrice
113 }
114
115 feeDenominator := u256.NewUint(poolFeeDenominator)
116 feeComplement := u256.NewUint(poolFeeDenominator - uint64(fee))
117
118 var priceX128 *u256.Uint
119
120 if zeroForOne {
121 // priceX128 = L_X128 / (1-fee), rounded up.
122 if minOutputPerInputX128.BitLen() > 250 {
123 return maxSqrtPrice
124 }
125
126 priceX128 = u256.MulDivRoundingUp(minOutputPerInputX128, feeDenominator, feeComplement)
127 } else {
128 // priceX128 = (2^256 / L_X128) * (1-fee), rounded down.
129 if minOutputPerInputX128.Lt(u256.NewUint(2)) {
130 return maxSqrtPrice
131 }
132
133 q128 := u256.One().Lsh(u256.One(), 128)
134 inverseX128 := u256.MulDiv(q128, q128, minOutputPerInputX128)
135 priceX128 = u256.MulDiv(inverseX128, feeComplement, feeDenominator)
136 }
137
138 sqrtPriceX96 := sqrtX128ToSqrtX96(priceX128, zeroForOne)
139
140 if sqrtPriceX96.Lt(minSqrtPrice) {
141 return minSqrtPrice
142 }
143
144 if sqrtPriceX96.Gt(maxSqrtPrice) {
145 return maxSqrtPrice
146 }
147
148 return sqrtPriceX96
149}
150
151// sqrtX128ToSqrtX96 returns sqrt(priceX128 / 2^128) * 2^96,
152// that is sqrt(priceX128 * 2^64), rounded up when roundUp is set.
153// A priceX128 too large to shift by 64 bits is shifted by 64-2k bits and the
154// root by k bits instead, which keeps the result within one part in 2^96.
155func sqrtX128ToSqrtX96(priceX128 *u256.Uint, roundUp bool) *u256.Uint {
156 k := uint(0)
157 if bitLen := priceX128.BitLen() + 64; bitLen > 255 {
158 k = uint(bitLen-255+1) / 2
159 }
160
161 var value *u256.Uint
162 if 2*k <= 64 {
163 value = u256.Zero().Lsh(priceX128, 64-2*k)
164 } else {
165 value = u256.Zero().Rsh(priceX128, 2*k-64)
166 }
167
168 root := sqrtUint256(value)
169
170 if roundUp && !u256.Zero().Mul(root, root).Eq(value) {
171 root = u256.Zero().Add(root, u256.One())
172 }
173
174 return u256.Zero().Lsh(root, k)
175}
176
177// sqrtUint256 returns floor(sqrt(x)) by Newton's method.
178func sqrtUint256(x *u256.Uint) *u256.Uint {
179 if x.IsZero() {
180 return u256.Zero()
181 }
182
183 // Start above the root: 2^ceil(bitLen/2).
184 z := u256.Zero().Lsh(u256.One(), uint((x.BitLen()+1)/2))
185
186 for {
187 // next = (z + x/z) / 2
188 next := u256.Zero().Add(z, u256.Zero().Div(x, z))
189 next = next.Rsh(next, 1)
190
191 if next.Gte(z) {
192 return z
193 }
194
195 z = next
196 }
197}
198
199// poolSqrtPriceLimit returns the sqrt price limit of selling on poolPath under
200// limit, or why the pool cannot trade under it. maxDeviationRate, in basis
201// points of price, bounds how far the pool's price may sit on the favorable
202// side of the limit (see isDisplacedPool); 0 disables that check.
203// maxLimitAge, in seconds, is how old the limit may be (see isStalePriceLimit).
204//
205// It returns the limit, or the ineligibility code and reason.
206func poolSqrtPriceLimit(poolPath string, fee uint32, zeroForOne bool, limit *pdca.PairPriceLimit, maxDeviationRate int64, maxLimitAge int64) (string, string, string) {
207 if limit == nil {
208 return "", codeNoPriceLimit, reasonNoPriceLimit
209 }
210
211 stale, err := isStalePriceLimit(limit, maxLimitAge, time.Now().Unix())
212 if err != nil {
213 // The age is validated when set; an invalid one excludes the pool.
214 return "", codePriceLimitStale, reasonInvalidLimitAge
215 }
216
217 if stale {
218 return "", codePriceLimitStale, reasonPriceLimitStale
219 }
220
221 currentSqrtPrice, err := pool.GetSlot0SqrtPriceX96(poolPath)
222 if err != nil {
223 return "", codePriceUnavailable, reasonPoolPriceAbsent
224 }
225
226 current, err := u256.FromDecimal(currentSqrtPrice)
227 if err != nil {
228 return "", codePriceUnavailable, reasonPoolPriceAbsent
229 }
230
231 sqrtPriceLimit := calculateSqrtPriceLimitX96(limit.MinOutputPerInputX128(), fee, zeroForOne)
232
233 // The pool requires the limit strictly on the side the price moves to.
234 if zeroForOne && !sqrtPriceLimit.Lt(current) {
235 return "", codePricePastLimit, reasonPricePastLimit
236 }
237
238 if !zeroForOne && !sqrtPriceLimit.Gt(current) {
239 return "", codePricePastLimit, reasonPricePastLimit
240 }
241
242 displaced, err := isDisplacedPool(current, sqrtPriceLimit, zeroForOne, maxDeviationRate)
243 if err != nil {
244 // The rate is validated when set; an invalid one excludes the pool.
245 return "", codePriceDisplaced, reasonInvalidDeviation
246 }
247
248 if displaced {
249 return "", codePriceDisplaced, reasonPriceDisplaced
250 }
251
252 return sqrtPriceLimit.ToString(), "", ""
253}
254
255// isStalePriceLimit reports whether limit was set more than maxLimitAge
256// seconds before currentTimestamp. A non-positive maxLimitAge is invalid:
257// a stored config without the age fails closed instead of disabling the check.
258func isStalePriceLimit(limit *pdca.PairPriceLimit, maxLimitAge int64, currentTimestamp int64) (bool, error) {
259 if maxLimitAge <= 0 {
260 return false, makeErrorWithDetails(errInvalidConfig, ufmt.Sprintf("maxPairPriceLimitAge(%d)", maxLimitAge))
261 }
262
263 return currentTimestamp-limit.UpdatedAt() > maxLimitAge, nil
264}
265
266// isDisplacedPool reports whether the pool price sits more than
267// maxDeviationRate, in basis points of price, on the favorable side of the
268// swap price limit; 0 disables the check.
269//
270// Prices are compared through their square roots:
271// P_current / P_limit > 1 + rate <=> sqrtCurrent > sqrtLimit * sqrt(1 + rate)
272// when selling token0, and the reciprocal when selling token1.
273func isDisplacedPool(currentSqrtPriceX96 *u256.Uint, sqrtPriceLimitX96 *u256.Uint, zeroForOne bool, maxDeviationRate int64) (bool, error) {
274 if maxDeviationRate == 0 {
275 return false, nil
276 }
277
278 if maxDeviationRate < 0 || maxDeviationRate > pdca.BasisPointDenominator {
279 return false, makeErrorWithDetails(errInvalidConfig, ufmt.Sprintf("maxPoolPriceDeviationRate(%d)", maxDeviationRate))
280 }
281
282 // factorX96 = sqrt(1 + rate) * 2^96, rounded down.
283 ratioX192 := u256.MulDiv(
284 u256.NewUint(uint64(pdca.BasisPointDenominator+maxDeviationRate)),
285 u256.Zero().Lsh(u256.One(), 2*q96Shift),
286 u256.NewUint(uint64(pdca.BasisPointDenominator)),
287 )
288 factorX96 := sqrtUint256(ratioX192)
289 q96 := u256.Zero().Lsh(u256.One(), q96Shift)
290
291 if zeroForOne {
292 // The price falls toward the limit: displaced when the pool price is
293 // above limit * (1 + rate).
294 threshold := u256.MulDiv(sqrtPriceLimitX96, factorX96, q96)
295 return currentSqrtPriceX96.Gt(threshold), nil
296 }
297
298 // The price rises toward the limit: displaced when the pool price is
299 // below limit / (1 + rate).
300 scaledCurrent := u256.MulDiv(currentSqrtPriceX96, factorX96, q96)
301
302 return scaledCurrent.Lt(sqrtPriceLimitX96), nil
303}
304
305// parseMinOutputPerInputX128 parses a decimal Q128 price limit.
306func parseMinOutputPerInputX128(value string) (*u256.Uint, error) {
307 parsed, err := u256.FromDecimal(value)
308 if err != nil {
309 return nil, makeErrorWithDetails(errInvalidPriceLimit, ufmt.Sprintf("minOutputPerInputX128(%s): %s", value, err.Error()))
310 }
311
312 return parsed, nil
313}