1// Package pair is the whole behaviour of one constant-product AMM pair, as a2// pure package, so that a realm holding a single pair can be twenty lines of3// glue.4//5// It is the shared half of the instance-per-realm pattern: deploy this once,6// then deploy one tiny realm per token couple, each owning its own state, its7// own funds and its own storage deposit, all running this identical code. The8// Ethereum shape it copies (a factory spawning one UniswapV2Pair per couple)9// needs EIP-1167 clones to make the duplication affordable; an import makes it10// free.11//12// # How an instance uses it13//14// var p *pair.Pair15//16// func init(cur realm) {17// p = pair.New(keyA, keyB, grc20reg.MustGet(keyA), grc20reg.MustGet(keyB))18// pairreg.Register(cross(cur), p)19// }20//21// func Swap(cur realm, keyIn string, amountIn, minOut int64) int64 {22// return p.Swap(0, cur, keyIn, amountIn, minOut)23// }24//25// # Why the methods look like that26//27// Every state-changing method is shaped (_ int, rlm realm, ...). The leading28// dummy is mandatory: gno rejects a function whose FIRST parameter is realm29// when it is declared in a pure package ("crossing function declared in30// non-realm package"), and the parameter cannot be named cur either. Same31// reason grc20's tellers are Transfer(_ int, rlm realm, ...). The realm value32// arrives non-crossing, which is exactly what is wanted: the frame stays the33// instance realm, so funds move to and from the INSTANCE's address, and34// rlm.IsCurrent() still holds for grc20's spoof check.35//36// A pure package also cannot import a realm at all, so this package never37// resolves a token by path. The instance passes *grc20.Token handles in.38//39// # The economics, unchanged from the single-realm design40//41// Constant product x*y=k with a 30 bps fee kept by the pool, reserves stored42// and never derived from BalanceOf (so a direct transfer to the realm is43// inert, and permanently stuck), first deposit minting shares equal to the44// token-A amount with no sqrt and no MINIMUM_LIQUIDITY burn, and every reserve45// capped so the int64 arithmetic cannot overflow. The reasoning behind each of46// those is in https://github.com/moul/gno-contracts/issues/135 and is not47// repeated here; this package is that design with one pool per realm instead48// of many pools in one realm.49//50// Consequence worth repeating, because it bites: with a 1000x fee denominator51// on int64 amounts, this is unusable with 18-decimal tokens. Six to nine52// decimals is the practical band.53package pair5455import (56 "chain"57 "math"58 "math/bits"59 "strconv"6061 "gno.land/p/nt/avl/v0"62 "gno.land/p/nt/grc20/v0"63 "gno.land/p/nt/ufmt/v0"64)6566const (67 // feeNum/feeDen is the swap fee kept by the pool: 997/1000, i.e. 30 bps.68 feeNum = 99769 feeDen = 10007071 // maxReserve is the largest reserve a pair will hold, in base units.72 //73 // Pricing computes den = reserveIn*feeDen + amountIn*feeNum in plain74 // int64 before handing off to the 128-bit mulDiv. Capping every reserve,75 // and every post-swap reserve, at MaxInt64/feeDen makes that sum provably76 // safe:77 //78 // den < (reserveIn + amountIn) * feeDen <= maxReserve * feeDen79 // = 9223372036854775000 <= MaxInt64 = 922337203685477580780 MaxReserve = math.MaxInt64 / feeDen // 922337203685477581)8283// Pair is one token couple and its liquidity. Fields are concrete by design:84// the registry realm holds a live pointer to this struct and reads it while85// rendering, so an interface or a func field here would let a hostile86// instance hand foreign code to the registry's frame.87//88// keyA < keyB always holds; New canonicalises.89type Pair struct {90 keyA, keyB string91 tokA, tokB *grc20.Token92 resA, resB int6493 totalShares int6494 shares *avl.Tree // address string -> int6495}9697// New builds an empty pair from two grc20reg keys and the matching token98// handles, in canonical order. The caller (the instance realm) is responsible99// for resolving the handles, because a pure package cannot import the100// registry realm that holds them.101func New(keyA, keyB string, tokA, tokB *grc20.Token) *Pair {102 if keyA == "" || keyB == "" {103 panic("pair: empty token key")104 }105 if keyA == keyB {106 panic("pair: a pair needs two different tokens")107 }108 if tokA == nil || tokB == nil {109 panic("pair: nil token")110 }111 if keyA > keyB {112 keyA, keyB = keyB, keyA113 tokA, tokB = tokB, tokA114 }115 return &Pair{keyA: keyA, keyB: keyB, tokA: tokA, tokB: tokB, shares: avl.NewTree()}116}117118//119// Writes. Each one takes the instance realm's own cur, forwarded.120//121122// AddLiquidity deposits up to maxA of token A and maxB of token B and mints LP123// shares to the caller. On an existing pair the deposit is trimmed to the124// current reserve ratio, so pass the amounts you are willing to spend, not the125// amounts you insist on spending.126//127// The caller must first Approve the INSTANCE realm's address on both tokens.128// Returns the shares minted.129func (p *Pair) AddLiquidity(_ int, rlm realm, maxA, maxB int64) int64 {130 if maxA <= 0 || maxB <= 0 {131 panic("pair: both deposit amounts must be > 0")132 }133 amtA, amtB := maxA, maxB134135 var minted int64136 if p.totalShares == 0 {137 // First position: the depositor sets the price and the share unit is138 // token A at seed time. No sqrt, no MINIMUM_LIQUIDITY burn.139 minted = amtA140 } else {141 // Trim to the current ratio, then mint from whichever side is scarcer.142 // Both divisions floor, and taking the minimum means an off-ratio143 // deposit is rounded against the depositor, never against the pool.144 if want := mulDiv(amtA, p.resB, p.resA); want <= amtB {145 amtB = want146 } else {147 amtA = mulDiv(amtB, p.resA, p.resB)148 }149 if amtA <= 0 || amtB <= 0 {150 panic("pair: deposit too small for the current ratio")151 }152 minted = min64(153 mulDiv(amtA, p.totalShares, p.resA),154 mulDiv(amtB, p.totalShares, p.resB),155 )156 }157 if minted <= 0 {158 panic("pair: deposit mints zero shares")159 }160 if p.resA+amtA > MaxReserve || p.resB+amtB > MaxReserve {161 panic("pair: reserve cap exceeded")162 }163164 provider := rlm.Previous().Address()165 self := rlm.Address()166 pull(0, rlm, p.tokA, provider, self, amtA)167 pull(0, rlm, p.tokB, provider, self, amtB)168169 p.resA += amtA170 p.resB += amtB171 p.totalShares += minted172 p.setShares(provider, p.SharesOf(provider)+minted)173174 chain.Emit("AddLiquidity",175 "pair", p.ID(),176 "provider", provider.String(),177 "amountA", itoa(amtA),178 "amountB", itoa(amtB),179 "shares", itoa(minted),180 )181 return minted182}183184// RemoveLiquidity burns shares held by the caller and returns the185// proportional amounts of both tokens, in (A, B) order.186//187// Burning the entire share supply pays out the whole reserve, so the last188// provider out leaves nothing unclaimable behind and the pair can be reseeded189// at a fresh price.190func (p *Pair) RemoveLiquidity(_ int, rlm realm, shares int64) (int64, int64) {191 if shares <= 0 {192 panic("pair: shares must be > 0")193 }194 owner := rlm.Previous().Address()195 held := p.SharesOf(owner)196 if held < shares {197 panic("pair: insufficient shares")198 }199200 var amtA, amtB int64201 if shares == p.totalShares {202 amtA, amtB = p.resA, p.resB203 } else {204 amtA = mulDiv(shares, p.resA, p.totalShares)205 amtB = mulDiv(shares, p.resB, p.totalShares)206 }207 if amtA <= 0 || amtB <= 0 {208 panic("pair: burn would return nothing on one side")209 }210211 p.resA -= amtA212 p.resB -= amtB213 p.totalShares -= shares214 p.setShares(owner, held-shares)215216 push(0, rlm, p.tokA, owner, amtA)217 push(0, rlm, p.tokB, owner, amtB)218219 chain.Emit("RemoveLiquidity",220 "pair", p.ID(),221 "provider", owner.String(),222 "amountA", itoa(amtA),223 "amountB", itoa(amtB),224 "shares", itoa(shares),225 )226 return amtA, amtB227}228229// Swap sells amountIn of keyIn for the other token and aborts unless at least230// minOut comes back. The caller must first Approve the instance realm's231// address on keyIn.232//233// minOut is the only protection against being sandwiched or against the pair234// moving between quoting and execution. Pass a real bound; passing 0 means235// accepting any price at all.236func (p *Pair) Swap(_ int, rlm realm, keyIn string, amountIn, minOut int64) int64 {237 if amountIn <= 0 {238 panic("pair: amountIn must be > 0")239 }240 if minOut < 0 {241 panic("pair: minOut must be >= 0")242 }243 flipped := p.mustSide(keyIn)244245 resIn, resOut := p.resA, p.resB246 tokIn, tokOut := p.tokA, p.tokB247 if flipped {248 resIn, resOut = p.resB, p.resA249 tokIn, tokOut = p.tokB, p.tokA250 }251252 out := AmountOut(amountIn, resIn, resOut)253 if out <= 0 {254 panic("pair: output rounds to zero")255 }256 if out < minOut {257 panic("pair: slippage, output below minOut")258 }259260 trader := rlm.Previous().Address()261 pull(0, rlm, tokIn, trader, rlm.Address(), amountIn)262263 newIn, newOut := resIn+amountIn, resOut-out264 // The invariant holds by construction (out is floored), so this can only265 // fire if the pricing above is ever edited into being wrong. It is exact:266 // both products are compared in 128 bits.267 if cmpProd(newIn, newOut, resIn, resOut) < 0 {268 panic("pair: constant product regression")269 }270 if flipped {271 p.resB, p.resA = newIn, newOut272 } else {273 p.resA, p.resB = newIn, newOut274 }275276 push(0, rlm, tokOut, trader, out)277278 chain.Emit("Swap",279 "pair", p.ID(),280 "trader", trader.String(),281 "tokenIn", tokIn.GetSymbol(),282 "amountIn", itoa(amountIn),283 "amountOut", itoa(out),284 )285 return out286}287288//289// Reads. Safe for the registry realm to call on another realm's Pair.290//291292// AmountOut is the pricing function, fee included, as a pure function of the293// two reserves. Exported so a caller can quote off chain against reserves it294// already holds, and so the arithmetic is testable on its own.295func AmountOut(amountIn, reserveIn, reserveOut int64) int64 {296 if amountIn <= 0 {297 panic("pair: amountIn must be > 0")298 }299 if reserveIn <= 0 || reserveOut <= 0 {300 panic("pair: pair has an empty reserve")301 }302 if reserveIn > MaxReserve || reserveOut > MaxReserve {303 panic("pair: reserve above cap")304 }305 if amountIn > MaxReserve-reserveIn {306 panic("pair: reserve cap exceeded")307 }308 inFee := amountIn * feeNum309 den := reserveIn*feeDen + inFee310 return mulDiv(inFee, reserveOut, den)311}312313// Quote prices amountIn of keyIn against the live reserves. It is the number314// Swap would return right now, which is not a promise about the next block.315func (p *Pair) Quote(keyIn string, amountIn int64) int64 {316 if p.totalShares == 0 {317 return 0318 }319 if p.mustSide(keyIn) {320 return AmountOut(amountIn, p.resB, p.resA)321 }322 return AmountOut(amountIn, p.resA, p.resB)323}324325// Keys returns the two grc20reg keys in canonical order.326func (p *Pair) Keys() (string, string) { return p.keyA, p.keyB }327328// Symbols returns the two token symbols in canonical order.329func (p *Pair) Symbols() (string, string) { return p.tokA.GetSymbol(), p.tokB.GetSymbol() }330331// ID is the canonical identifier of the couple, "keyA~keyB". The separator is332// "~" and not "|": a "|" inside a markdown table cell breaks the row.333func (p *Pair) ID() string { return p.keyA + "~" + p.keyB }334335// Reserves returns the two reserves in canonical order.336func (p *Pair) Reserves() (int64, int64) { return p.resA, p.resB }337338// TotalShares returns the LP share supply.339func (p *Pair) TotalShares() int64 { return p.totalShares }340341// Providers returns how many addresses hold shares.342func (p *Pair) Providers() int { return p.shares.Size() }343344// SharesOf returns owner's LP shares.345func (p *Pair) SharesOf(owner address) int64 {346 v := p.shares.Get(owner.String())347 if v == nil {348 return 0349 }350 return v.(int64)351}352353// Render is the instance realm's whole page: what the couple is, what it354// holds, and how to trade it.355func (p *Pair) Render(path string) string {356 symA, symB := p.Symbols()357 out := "# " + symA + " / " + symB + "\n\n"358 out += "One constant-product pair, `x*y=k`, 30 bps to the liquidity providers. "359 out += "Logic lives in [p/moul/x/pair/v0](/p/moul/x/pair/v0); this realm is the instance.\n\n"360361 if p.totalShares == 0 {362 out += "_Empty. The first `AddLiquidity` sets the price._\n\n"363 } else {364 out += ufmt.Sprintf("| side | reserve | key |\n|---|---|---|\n| %s | %d | `%s` |\n| %s | %d | `%s` |\n\n",365 symA, p.resA, p.keyA, symB, p.resB, p.keyB)366 out += ufmt.Sprintf("- LP shares: **%d** across %d provider(s)\n",367 p.totalShares, p.shares.Size())368 out += ufmt.Sprintf("- Spot: 1 %s buys ~%d %s (before fee and slippage)\n\n",369 symA, p.spot(), symB)370 }371 out += "Approve this realm's address on the token you are selling, then call `Swap`.\n"372 return out373}374375//376// Internals.377//378379// spot is the display-only mid price, floor(resB/resA). Never price anything380// off it: it is a spot reserve ratio that any trader can move in one tx.381func (p *Pair) spot() int64 {382 if p.resA == 0 {383 return 0384 }385 return p.resB / p.resA386}387388// mustSide reports whether key is the B side, and panics if it is neither.389func (p *Pair) mustSide(key string) bool {390 switch key {391 case p.keyA:392 return false393 case p.keyB:394 return true395 }396 panic("pair: " + key + " is not in this pair")397}398399func (p *Pair) setShares(owner address, n int64) {400 if n == 0 {401 p.shares.Remove(owner.String())402 return403 }404 p.shares.Set(owner.String(), n)405}406407// pull moves amount of tok from `from` into the instance realm, spending the408// allowance `from` granted to the instance realm's address.409//410// Non-crossing on purpose: `_ int, rlm realm` is the only shape a pure411// package can declare, and it keeps rlm the instance's own live frame.412// RealmTeller binds the spender eagerly to rlm.Address(), which is therefore413// the instance, not this package (a pure package has no address at all).414func pull(_ int, rlm realm, tok *grc20.Token, from, to address, amount int64) {415 err := tok.RealmTeller(0, rlm).TransferFrom(0, rlm, from, to, amount)416 if err != nil {417 panic("pair: cannot take " + tok.GetSymbol() + ": " + err.Error())418 }419}420421// push sends amount of tok from the instance realm to `to`.422func push(_ int, rlm realm, tok *grc20.Token, to address, amount int64) {423 err := tok.RealmTeller(0, rlm).Transfer(0, rlm, to, amount)424 if err != nil {425 panic("pair: cannot send " + tok.GetSymbol() + ": " + err.Error())426 }427}428429// mulDiv returns floor(a*b/c) through a 128-bit intermediate, which plain430// int64 arithmetic cannot do: a*b is routinely wider than 63 bits here even431// when the quotient is small.432func mulDiv(a, b, c int64) int64 {433 if a < 0 || b < 0 {434 panic("pair: negative operand")435 }436 if c <= 0 {437 panic("pair: division by a non-positive value")438 }439 hi, lo := bits.Mul64(uint64(a), uint64(b))440 // bits.Div64 panics for y <= hi; refusing here turns that into a named441 // abort and also covers every quotient that would not fit in 64 bits.442 if hi >= uint64(c) {443 panic("pair: quotient overflows int64")444 }445 q, _ := bits.Div64(hi, lo, uint64(c))446 if q > uint64(math.MaxInt64) {447 panic("pair: quotient overflows int64")448 }449 return int64(q)450}451452// cmpProd compares a*b with c*d exactly, in 128 bits, and returns -1, 0 or 1.453func cmpProd(a, b, c, d int64) int {454 h1, l1 := bits.Mul64(uint64(a), uint64(b))455 h2, l2 := bits.Mul64(uint64(c), uint64(d))456 if h1 != h2 {457 if h1 < h2 {458 return -1459 }460 return 1461 }462 if l1 != l2 {463 if l1 < l2 {464 return -1465 }466 return 1467 }468 return 0469}470471func min64(a, b int64) int64 {472 if a < b {473 return a474 }475 return b476}477478func itoa(v int64) string { return strconv.FormatInt(v, 10) }479Signatures reconstructed verbatim from vm/qfuncs — interface params keep their inline definitions.