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

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}