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

Playground

gnomod.toml

module = "gno.land/p/moul/x/pair/v0"
gno = "0.9"

[addpkg]
  creator = "g1manfred47kzduec920z88wfr64ylksmdcedlf5"
  height = 272406
  max_deposit = "10000000ugnot"

pair.gno

// Package pair is the whole behaviour of one constant-product AMM pair, as a
// pure package, so that a realm holding a single pair can be twenty lines of
// glue.
//
// It is the shared half of the instance-per-realm pattern: deploy this once,
// then deploy one tiny realm per token couple, each owning its own state, its
// own funds and its own storage deposit, all running this identical code. The
// Ethereum shape it copies (a factory spawning one UniswapV2Pair per couple)
// needs EIP-1167 clones to make the duplication affordable; an import makes it
// free.
//
// # How an instance uses it
//
//	var p *pair.Pair
//
//	func init(cur realm) {
//		p = pair.New(keyA, keyB, grc20reg.MustGet(keyA), grc20reg.MustGet(keyB))
//		pairreg.Register(cross(cur), p)
//	}
//
//	func Swap(cur realm, keyIn string, amountIn, minOut int64) int64 {
//		return p.Swap(0, cur, keyIn, amountIn, minOut)
//	}
//
// # Why the methods look like that
//
// Every state-changing method is shaped (_ int, rlm realm, ...). The leading
// dummy is mandatory: gno rejects a function whose FIRST parameter is realm
// when it is declared in a pure package ("crossing function declared in
// non-realm package"), and the parameter cannot be named cur either. Same
// reason grc20's tellers are Transfer(_ int, rlm realm, ...). The realm value
// arrives non-crossing, which is exactly what is wanted: the frame stays the
// instance realm, so funds move to and from the INSTANCE's address, and
// rlm.IsCurrent() still holds for grc20's spoof check.
//
// A pure package also cannot import a realm at all, so this package never
// resolves a token by path. The instance passes *grc20.Token handles in.
//
// # The economics, unchanged from the single-realm design
//
// Constant product x*y=k with a 30 bps fee kept by the pool, reserves stored
// and never derived from BalanceOf (so a direct transfer to the realm is
// inert, and permanently stuck), first deposit minting shares equal to the
// token-A amount with no sqrt and no MINIMUM_LIQUIDITY burn, and every reserve
// capped so the int64 arithmetic cannot overflow. The reasoning behind each of
// those is in https://github.com/moul/gno-contracts/issues/135 and is not
// repeated here; this package is that design with one pool per realm instead
// of many pools in one realm.
//
// Consequence worth repeating, because it bites: with a 1000x fee denominator
// on int64 amounts, this is unusable with 18-decimal tokens. Six to nine
// decimals is the practical band.
package pair

import (
	"chain"
	"math"
	"math/bits"
	"strconv"

	"gno.land/p/nt/avl/v0"
	"gno.land/p/nt/grc20/v0"
	"gno.land/p/nt/ufmt/v0"
)

const (
	// feeNum/feeDen is the swap fee kept by the pool: 997/1000, i.e. 30 bps.
	feeNum = 997
	feeDen = 1000

	// maxReserve is the largest reserve a pair will hold, in base units.
	//
	// Pricing computes den = reserveIn*feeDen + amountIn*feeNum in plain
	// int64 before handing off to the 128-bit mulDiv. Capping every reserve,
	// and every post-swap reserve, at MaxInt64/feeDen makes that sum provably
	// safe:
	//
	//	den < (reserveIn + amountIn) * feeDen <= maxReserve * feeDen
	//	    = 9223372036854775000 <= MaxInt64 = 9223372036854775807
	MaxReserve = math.MaxInt64 / feeDen // 9223372036854775
)

// Pair is one token couple and its liquidity. Fields are concrete by design:
// the registry realm holds a live pointer to this struct and reads it while
// rendering, so an interface or a func field here would let a hostile
// instance hand foreign code to the registry's frame.
//
// keyA < keyB always holds; New canonicalises.
type Pair struct {
	keyA, keyB  string
	tokA, tokB  *grc20.Token
	resA, resB  int64
	totalShares int64
	shares      *avl.Tree // address string -> int64
}

// New builds an empty pair from two grc20reg keys and the matching token
// handles, in canonical order. The caller (the instance realm) is responsible
// for resolving the handles, because a pure package cannot import the
// registry realm that holds them.
func New(keyA, keyB string, tokA, tokB *grc20.Token) *Pair {
	if keyA == "" || keyB == "" {
		panic("pair: empty token key")
	}
	if keyA == keyB {
		panic("pair: a pair needs two different tokens")
	}
	if tokA == nil || tokB == nil {
		panic("pair: nil token")
	}
	if keyA > keyB {
		keyA, keyB = keyB, keyA
		tokA, tokB = tokB, tokA
	}
	return &Pair{keyA: keyA, keyB: keyB, tokA: tokA, tokB: tokB, shares: avl.NewTree()}
}

//
// Writes. Each one takes the instance realm's own cur, forwarded.
//

// AddLiquidity deposits up to maxA of token A and maxB of token B and mints LP
// shares to the caller. On an existing pair the deposit is trimmed to the
// current reserve ratio, so pass the amounts you are willing to spend, not the
// amounts you insist on spending.
//
// The caller must first Approve the INSTANCE realm's address on both tokens.
// Returns the shares minted.
func (p *Pair) AddLiquidity(_ int, rlm realm, maxA, maxB int64) int64 {
	if maxA <= 0 || maxB <= 0 {
		panic("pair: both deposit amounts must be > 0")
	}
	amtA, amtB := maxA, maxB

	var minted int64
	if p.totalShares == 0 {
		// First position: the depositor sets the price and the share unit is
		// token A at seed time. No sqrt, no MINIMUM_LIQUIDITY burn.
		minted = amtA
	} else {
		// Trim to the current ratio, then mint from whichever side is scarcer.
		// Both divisions floor, and taking the minimum means an off-ratio
		// deposit is rounded against the depositor, never against the pool.
		if want := mulDiv(amtA, p.resB, p.resA); want <= amtB {
			amtB = want
		} else {
			amtA = mulDiv(amtB, p.resA, p.resB)
		}
		if amtA <= 0 || amtB <= 0 {
			panic("pair: deposit too small for the current ratio")
		}
		minted = min64(
			mulDiv(amtA, p.totalShares, p.resA),
			mulDiv(amtB, p.totalShares, p.resB),
		)
	}
	if minted <= 0 {
		panic("pair: deposit mints zero shares")
	}
	if p.resA+amtA > MaxReserve || p.resB+amtB > MaxReserve {
		panic("pair: reserve cap exceeded")
	}

	provider := rlm.Previous().Address()
	self := rlm.Address()
	pull(0, rlm, p.tokA, provider, self, amtA)
	pull(0, rlm, p.tokB, provider, self, amtB)

	p.resA += amtA
	p.resB += amtB
	p.totalShares += minted
	p.setShares(provider, p.SharesOf(provider)+minted)

	chain.Emit("AddLiquidity",
		"pair", p.ID(),
		"provider", provider.String(),
		"amountA", itoa(amtA),
		"amountB", itoa(amtB),
		"shares", itoa(minted),
	)
	return minted
}

// RemoveLiquidity burns shares held by the caller and returns the
// proportional amounts of both tokens, in (A, B) order.
//
// Burning the entire share supply pays out the whole reserve, so the last
// provider out leaves nothing unclaimable behind and the pair can be reseeded
// at a fresh price.
func (p *Pair) RemoveLiquidity(_ int, rlm realm, shares int64) (int64, int64) {
	if shares <= 0 {
		panic("pair: shares must be > 0")
	}
	owner := rlm.Previous().Address()
	held := p.SharesOf(owner)
	if held < shares {
		panic("pair: insufficient shares")
	}

	var amtA, amtB int64
	if shares == p.totalShares {
		amtA, amtB = p.resA, p.resB
	} else {
		amtA = mulDiv(shares, p.resA, p.totalShares)
		amtB = mulDiv(shares, p.resB, p.totalShares)
	}
	if amtA <= 0 || amtB <= 0 {
		panic("pair: burn would return nothing on one side")
	}

	p.resA -= amtA
	p.resB -= amtB
	p.totalShares -= shares
	p.setShares(owner, held-shares)

	push(0, rlm, p.tokA, owner, amtA)
	push(0, rlm, p.tokB, owner, amtB)

	chain.Emit("RemoveLiquidity",
		"pair", p.ID(),
		"provider", owner.String(),
		"amountA", itoa(amtA),
		"amountB", itoa(amtB),
		"shares", itoa(shares),
	)
	return amtA, amtB
}

// Swap sells amountIn of keyIn for the other token and aborts unless at least
// minOut comes back. The caller must first Approve the instance realm's
// address on keyIn.
//
// minOut is the only protection against being sandwiched or against the pair
// moving between quoting and execution. Pass a real bound; passing 0 means
// accepting any price at all.
func (p *Pair) Swap(_ int, rlm realm, keyIn string, amountIn, minOut int64) int64 {
	if amountIn <= 0 {
		panic("pair: amountIn must be > 0")
	}
	if minOut < 0 {
		panic("pair: minOut must be >= 0")
	}
	flipped := p.mustSide(keyIn)

	resIn, resOut := p.resA, p.resB
	tokIn, tokOut := p.tokA, p.tokB
	if flipped {
		resIn, resOut = p.resB, p.resA
		tokIn, tokOut = p.tokB, p.tokA
	}

	out := AmountOut(amountIn, resIn, resOut)
	if out <= 0 {
		panic("pair: output rounds to zero")
	}
	if out < minOut {
		panic("pair: slippage, output below minOut")
	}

	trader := rlm.Previous().Address()
	pull(0, rlm, tokIn, trader, rlm.Address(), amountIn)

	newIn, newOut := resIn+amountIn, resOut-out
	// The invariant holds by construction (out is floored), so this can only
	// fire if the pricing above is ever edited into being wrong. It is exact:
	// both products are compared in 128 bits.
	if cmpProd(newIn, newOut, resIn, resOut) < 0 {
		panic("pair: constant product regression")
	}
	if flipped {
		p.resB, p.resA = newIn, newOut
	} else {
		p.resA, p.resB = newIn, newOut
	}

	push(0, rlm, tokOut, trader, out)

	chain.Emit("Swap",
		"pair", p.ID(),
		"trader", trader.String(),
		"tokenIn", tokIn.GetSymbol(),
		"amountIn", itoa(amountIn),
		"amountOut", itoa(out),
	)
	return out
}

//
// Reads. Safe for the registry realm to call on another realm's Pair.
//

// AmountOut is the pricing function, fee included, as a pure function of the
// two reserves. Exported so a caller can quote off chain against reserves it
// already holds, and so the arithmetic is testable on its own.
func AmountOut(amountIn, reserveIn, reserveOut int64) int64 {
	if amountIn <= 0 {
		panic("pair: amountIn must be > 0")
	}
	if reserveIn <= 0 || reserveOut <= 0 {
		panic("pair: pair has an empty reserve")
	}
	if reserveIn > MaxReserve || reserveOut > MaxReserve {
		panic("pair: reserve above cap")
	}
	if amountIn > MaxReserve-reserveIn {
		panic("pair: reserve cap exceeded")
	}
	inFee := amountIn * feeNum
	den := reserveIn*feeDen + inFee
	return mulDiv(inFee, reserveOut, den)
}

// Quote prices amountIn of keyIn against the live reserves. It is the number
// Swap would return right now, which is not a promise about the next block.
func (p *Pair) Quote(keyIn string, amountIn int64) int64 {
	if p.totalShares == 0 {
		return 0
	}
	if p.mustSide(keyIn) {
		return AmountOut(amountIn, p.resB, p.resA)
	}
	return AmountOut(amountIn, p.resA, p.resB)
}

// Keys returns the two grc20reg keys in canonical order.
func (p *Pair) Keys() (string, string) { return p.keyA, p.keyB }

// Symbols returns the two token symbols in canonical order.
func (p *Pair) Symbols() (string, string) { return p.tokA.GetSymbol(), p.tokB.GetSymbol() }

// ID is the canonical identifier of the couple, "keyA~keyB". The separator is
// "~" and not "|": a "|" inside a markdown table cell breaks the row.
func (p *Pair) ID() string { return p.keyA + "~" + p.keyB }

// Reserves returns the two reserves in canonical order.
func (p *Pair) Reserves() (int64, int64) { return p.resA, p.resB }

// TotalShares returns the LP share supply.
func (p *Pair) TotalShares() int64 { return p.totalShares }

// Providers returns how many addresses hold shares.
func (p *Pair) Providers() int { return p.shares.Size() }

// SharesOf returns owner's LP shares.
func (p *Pair) SharesOf(owner address) int64 {
	v := p.shares.Get(owner.String())
	if v == nil {
		return 0
	}
	return v.(int64)
}

// Render is the instance realm's whole page: what the couple is, what it
// holds, and how to trade it.
func (p *Pair) Render(path string) string {
	symA, symB := p.Symbols()
	out := "# " + symA + " / " + symB + "\n\n"
	out += "One constant-product pair, `x*y=k`, 30 bps to the liquidity providers. "
	out += "Logic lives in [p/moul/x/pair/v0](/p/moul/x/pair/v0); this realm is the instance.\n\n"

	if p.totalShares == 0 {
		out += "_Empty. The first `AddLiquidity` sets the price._\n\n"
	} else {
		out += ufmt.Sprintf("| side | reserve | key |\n|---|---|---|\n| %s | %d | `%s` |\n| %s | %d | `%s` |\n\n",
			symA, p.resA, p.keyA, symB, p.resB, p.keyB)
		out += ufmt.Sprintf("- LP shares: **%d** across %d provider(s)\n",
			p.totalShares, p.shares.Size())
		out += ufmt.Sprintf("- Spot: 1 %s buys ~%d %s (before fee and slippage)\n\n",
			symA, p.spot(), symB)
	}
	out += "Approve this realm's address on the token you are selling, then call `Swap`.\n"
	return out
}

//
// Internals.
//

// spot is the display-only mid price, floor(resB/resA). Never price anything
// off it: it is a spot reserve ratio that any trader can move in one tx.
func (p *Pair) spot() int64 {
	if p.resA == 0 {
		return 0
	}
	return p.resB / p.resA
}

// mustSide reports whether key is the B side, and panics if it is neither.
func (p *Pair) mustSide(key string) bool {
	switch key {
	case p.keyA:
		return false
	case p.keyB:
		return true
	}
	panic("pair: " + key + " is not in this pair")
}

func (p *Pair) setShares(owner address, n int64) {
	if n == 0 {
		p.shares.Remove(owner.String())
		return
	}
	p.shares.Set(owner.String(), n)
}

// pull moves amount of tok from `from` into the instance realm, spending the
// allowance `from` granted to the instance realm's address.
//
// Non-crossing on purpose: `_ int, rlm realm` is the only shape a pure
// package can declare, and it keeps rlm the instance's own live frame.
// RealmTeller binds the spender eagerly to rlm.Address(), which is therefore
// the instance, not this package (a pure package has no address at all).
func pull(_ int, rlm realm, tok *grc20.Token, from, to address, amount int64) {
	err := tok.RealmTeller(0, rlm).TransferFrom(0, rlm, from, to, amount)
	if err != nil {
		panic("pair: cannot take " + tok.GetSymbol() + ": " + err.Error())
	}
}

// push sends amount of tok from the instance realm to `to`.
func push(_ int, rlm realm, tok *grc20.Token, to address, amount int64) {
	err := tok.RealmTeller(0, rlm).Transfer(0, rlm, to, amount)
	if err != nil {
		panic("pair: cannot send " + tok.GetSymbol() + ": " + err.Error())
	}
}

// mulDiv returns floor(a*b/c) through a 128-bit intermediate, which plain
// int64 arithmetic cannot do: a*b is routinely wider than 63 bits here even
// when the quotient is small.
func mulDiv(a, b, c int64) int64 {
	if a < 0 || b < 0 {
		panic("pair: negative operand")
	}
	if c <= 0 {
		panic("pair: division by a non-positive value")
	}
	hi, lo := bits.Mul64(uint64(a), uint64(b))
	// bits.Div64 panics for y <= hi; refusing here turns that into a named
	// abort and also covers every quotient that would not fit in 64 bits.
	if hi >= uint64(c) {
		panic("pair: quotient overflows int64")
	}
	q, _ := bits.Div64(hi, lo, uint64(c))
	if q > uint64(math.MaxInt64) {
		panic("pair: quotient overflows int64")
	}
	return int64(q)
}

// cmpProd compares a*b with c*d exactly, in 128 bits, and returns -1, 0 or 1.
func cmpProd(a, b, c, d int64) int {
	h1, l1 := bits.Mul64(uint64(a), uint64(b))
	h2, l2 := bits.Mul64(uint64(c), uint64(d))
	if h1 != h2 {
		if h1 < h2 {
			return -1
		}
		return 1
	}
	if l1 != l2 {
		if l1 < l2 {
			return -1
		}
		return 1
	}
	return 0
}

func min64(a, b int64) int64 {
	if a < b {
		return a
	}
	return b
}

func itoa(v int64) string { return strconv.FormatInt(v, 10) }

pair_test.gno

package pair

import (
	"testing"

	"gno.land/p/nt/uassert/v0"
)

// The pricing function, on its own, is the part worth pinning numerically: it
// is pure, it is where the 128-bit arithmetic lives, and every instance in the
// ecosystem runs this exact code.
func TestAmountOut(t *testing.T) {
	cases := []struct {
		name                    string
		in, resIn, resOut, want int64
	}{
		{"balanced pool, small trade", 1_000, 1_000_000, 1_000_000, 996},
		{"balanced pool, 1%", 10_000, 1_000_000, 1_000_000, 9_871},
		{"balanced pool, 10%", 100_000, 1_000_000, 1_000_000, 90_661},
		{"balanced pool, 50%", 500_000, 1_000_000, 1_000_000, 332_665},
		{"skewed pool", 100_000, 1_000_000, 4_000_000, 362_644},
		{"near drain", 1_000, 1, 1_000_000, 998_997},
		{"dust rounds to zero", 1, 1_000_000, 1_000_000, 0},
		{"reserves at the cap", MaxReserve / 2, MaxReserve / 2, MaxReserve, 4_604_758_097_518_382},
	}
	for _, tc := range cases {
		got := AmountOut(tc.in, tc.resIn, tc.resOut)
		uassert.Equal(t, tc.want, got, tc.name)
	}
}

// The fee is what stays behind: k must never decrease across a swap.
func TestConstantProductNeverRegresses(t *testing.T) {
	resIn, resOut := int64(1_000_000), int64(4_000_000)
	for _, in := range []int64{1, 1_000, 100_000, 999_999} {
		out := AmountOut(in, resIn, resOut)
		uassert.True(t, cmpProd(resIn+in, resOut-out, resIn, resOut) >= 0,
			"k must not regress")
	}
}

func TestAmountOutGuards(t *testing.T) {
	mustPanic(t, "pair: amountIn must be > 0", func() {
		AmountOut(0, 1_000, 1_000)
	})
	mustPanic(t, "pair: pair has an empty reserve", func() {
		AmountOut(1, 0, 1_000)
	})
	mustPanic(t, "pair: reserve above cap", func() {
		AmountOut(1, MaxReserve+1, 1_000)
	})
	mustPanic(t, "pair: reserve cap exceeded", func() {
		AmountOut(2, MaxReserve-1, 1_000)
	})
}

// mulDiv is the only place a 128-bit intermediate is required, and the only
// place bits.Div64 could panic. Both ends are asserted rather than argued.
func TestMulDiv(t *testing.T) {
	uassert.Equal(t, int64(2), mulDiv(4, 3, 6))
	uassert.Equal(t, int64(0), mulDiv(1, 1, 3), "floors")
	uassert.Equal(t, int64(4_611_686_018_427_387_903), mulDiv(9_223_372_036_854_775_807, 1, 2),
		"operands near MaxInt64 stay exact through the 128-bit path")

	mustPanic(t, "pair: division by a non-positive value", func() {
		mulDiv(1, 1, 0)
	})
	mustPanic(t, "pair: quotient overflows int64", func() {
		mulDiv(9_223_372_036_854_775_807, 9_223_372_036_854_775_807, 1)
	})
}

func TestCmpProd(t *testing.T) {
	uassert.Equal(t, 0, cmpProd(6, 7, 42, 1))
	uassert.Equal(t, -1, cmpProd(6, 6, 42, 1))
	uassert.Equal(t, 1, cmpProd(7, 7, 42, 1))
	// Both products exceed int64 and differ only in the low word.
	uassert.Equal(t, -1, cmpProd(4_000_000_000, 4_000_000_000, 4_000_000_000, 4_000_000_001))
}

// mustPanic is uassert.PanicsWithMessage without the realm argument: a pure
// package cannot produce a `cur` to hand it, since it can never declare a
// crossing function in the first place.
func mustPanic(t *testing.T, want string, f func()) {
	t.Helper()
	defer func() {
		r := recover()
		if r == nil {
			t.Errorf("expected panic %q, got none", want)
			return
		}
		got, ok := r.(string)
		if !ok {
			t.Errorf("expected a string panic %q, got %v", want, r)
			return
		}
		if got != want {
			t.Errorf("expected panic %q, got %q", want, got)
		}
	}()
	f()
}