use std::{any::Any, collections::HashMap};
use alloy::primitives::{address, Address, U256};
use num_bigint::BigUint;
use serde::{Deserialize, Serialize};
use tycho_common::{
dto::ProtocolStateDelta,
models::token::Token,
simulation::{
errors::{SimulationError, TransitionError},
protocol_sim::{Balances, GetAmountOutResult, PoolSwap, ProtocolSim, QueryPoolSwapParams},
},
Bytes,
};
use crate::{
book::{
component::PairState,
sim::{self, SwapDirection},
},
evm::protocol::{
u256_num::{biguint_to_u256, u256_to_biguint},
utils::solidity_math::mul_div,
},
pamm::protocols::baibai::math::{invalid, Curve, Side},
};
const BASE_SWAP_GAS: u64 = 115_400;
const GAS_PER_KNOT_BELOW_CURSOR: u64 = 1_550;
const GAS_PER_KNOT_BOUGHT_THROUGH: u64 = 1_360;
const BASE_TRANSFER_GAS: [(Address, u64, u64); 1] =
[(address!("cbB7C0000aB88B473b1f5aFd9ef808440eed33Bf"), 17_100, 15_400)];
const FEE_DENOMINATOR: u32 = 1_000_000;
#[derive(Clone, derive_more::Debug, PartialEq, Serialize, Deserialize)]
pub struct BaibaiState {
pub(super) base_token: Token,
pub(super) quote_token: Token,
pub(super) mid: U256,
pub(super) q_unit: U256,
pub(super) c_unit: U256,
#[debug("{{ filled: {}, {} knots }}", ask.filled, ask.knots.len())]
pub(super) ask: Side,
#[debug("{{ filled: {}, {} knots }}", bid.filled, bid.knots.len())]
pub(super) bid: Side,
pub(super) available: [U256; 2],
pub(super) fee_pips: u32,
}
impl BaibaiState {
pub(super) fn validated(self) -> Result<Self, SimulationError> {
if self.mid == U256::ZERO || self.q_unit == U256::ZERO || self.c_unit == U256::ZERO {
return Err(invalid("curve has no mid price or unit"));
}
self.kept_pips()?;
self.curve(SwapDirection::BaseToQuote)?;
self.curve(SwapDirection::QuoteToBase)?;
Ok(self)
}
fn curve(&self, direction: SwapDirection) -> Result<Curve, SimulationError> {
let (side, asks) = match direction {
SwapDirection::BaseToQuote => (&self.bid, false),
SwapDirection::QuoteToBase => (&self.ask, true),
};
Curve::new(side, self.mid, self.q_unit, self.c_unit, asks)
}
fn custody(direction: SwapDirection) -> (usize, usize) {
match direction {
SwapDirection::BaseToQuote => (0, 1),
SwapDirection::QuoteToBase => (1, 0),
}
}
fn kept_pips(&self) -> Result<u32, SimulationError> {
if self.fee_pips >= FEE_DENOMINATOR {
return Err(invalid(format!("fee of {} pips takes the whole output", self.fee_pips)));
}
Ok(FEE_DENOMINATOR - self.fee_pips)
}
fn after_fee(&self, gross: U256) -> Result<U256, SimulationError> {
let kept = self.kept_pips()?;
mul_div(gross, U256::from(kept), U256::from(FEE_DENOMINATOR))
}
fn gas(&self, curve: &Curve, direction: SwapDirection, cursor: U256) -> u64 {
let below = curve.knots_below(cursor);
let bought_through = match direction {
SwapDirection::BaseToQuote => 0,
SwapDirection::QuoteToBase => below - curve.knots_below(curve.filled),
};
let transfers = BASE_TRANSFER_GAS
.iter()
.find(|(base, _, _)| self.base_token.address.as_ref() == base.as_slice())
.map_or(0, |(_, selling, buying)| match direction {
SwapDirection::BaseToQuote => *selling,
SwapDirection::QuoteToBase => *buying,
});
BASE_SWAP_GAS +
transfers +
GAS_PER_KNOT_BELOW_CURSOR * below +
GAS_PER_KNOT_BOUGHT_THROUGH * bought_through
}
fn sells(&self, direction: SwapDirection) -> bool {
let (_, out) = Self::custody(direction);
self.kept_pips().is_ok() &&
self.available[out] > U256::ZERO &&
self.curve(direction)
.and_then(|curve| curve.capacity())
.is_ok_and(|capacity| capacity > U256::ZERO)
}
}
impl PairState for BaibaiState {
fn base_token(&self) -> &Token {
&self.base_token
}
fn quote_token(&self) -> &Token {
&self.quote_token
}
fn directions(&self) -> Vec<(Bytes, Bytes)> {
sim::directions(
&self.base_token,
&self.quote_token,
self.sells(SwapDirection::BaseToQuote),
self.sells(SwapDirection::QuoteToBase),
)
}
}
#[typetag::serde]
impl ProtocolSim for BaibaiState {
fn fee(&self) -> f64 {
f64::from(self.fee_pips) / f64::from(FEE_DENOMINATOR)
}
fn spot_price(&self, base: &Token, quote: &Token) -> Result<f64, SimulationError> {
let direction = SwapDirection::require(
&self.base_token,
&self.quote_token,
&base.address,
"e.address,
)?;
let (_, out) = Self::custody(direction);
if self.available[out] == U256::ZERO {
return Err(invalid("no custody to pay out"));
}
let atomic = self
.curve(direction)?
.marginal_price()?;
let decimals = 10f64.powf(f64::from(base.decimals) - f64::from(quote.decimals));
let kept = f64::from(self.kept_pips()?) / f64::from(FEE_DENOMINATOR);
Ok(atomic * decimals * kept)
}
fn get_amount_out(
&self,
amount_in: BigUint,
token_in: &Token,
token_out: &Token,
) -> Result<GetAmountOutResult, SimulationError> {
sim::require_positive_amount(&amount_in)?;
let direction = SwapDirection::require(
&self.base_token,
&self.quote_token,
&token_in.address,
&token_out.address,
)?;
if amount_in.bits() > 256 {
return Err(invalid("amount exceeds uint256"));
}
let input = biguint_to_u256(&amount_in);
let curve = self.curve(direction)?;
let (gross, cursor) = curve.quote(input)?;
let output = self.after_fee(gross)?;
if output == U256::ZERO {
return Err(invalid("input below the curve's atomic precision"));
}
let (paid_in, paid_out) = Self::custody(direction);
if output > self.available[paid_out] {
return Err(invalid(format!(
"output {output} exceeds the custodian's available {}",
self.available[paid_out]
)));
}
let mut next = self.clone();
match direction {
SwapDirection::BaseToQuote => next.bid.filled = cursor,
SwapDirection::QuoteToBase => next.ask.filled = cursor,
}
next.available[paid_in] = next.available[paid_in].saturating_add(input);
next.available[paid_out] -= output;
Ok(GetAmountOutResult::new(
u256_to_biguint(output),
BigUint::from(self.gas(&curve, direction, cursor)),
Box::new(next),
))
}
fn get_limits(
&self,
sell_token: Bytes,
buy_token: Bytes,
) -> Result<(BigUint, BigUint), SimulationError> {
let direction =
SwapDirection::require(&self.base_token, &self.quote_token, &sell_token, &buy_token)?;
let (paid_in, paid_out) = Self::custody(direction);
let available = self.available[paid_out];
if available == U256::ZERO {
return Ok((BigUint::ZERO, BigUint::ZERO));
}
let curve = self.curve(direction)?;
let mut high = curve
.capacity()?
.min(U256::MAX - self.available[paid_in]);
let full_output = self.after_fee(curve.quote(high)?.0)?;
if full_output == U256::ZERO {
return Ok((BigUint::ZERO, BigUint::ZERO));
}
if self.after_fee(curve.output_bound(high)?)? <= available {
return Ok((u256_to_biguint(high), u256_to_biguint(full_output)));
}
let mut low = U256::ZERO;
while low < high {
let mid = low + (high - low).div_ceil(U256::from(2));
if self.after_fee(curve.output_bound(mid)?)? <= available {
low = mid;
} else {
high = mid - U256::from(1);
}
}
let output = self.after_fee(curve.quote(low)?.0)?;
if output == U256::ZERO {
return Ok((BigUint::ZERO, BigUint::ZERO));
}
Ok((u256_to_biguint(low), u256_to_biguint(output)))
}
fn delta_transition(
&mut self,
_delta: ProtocolStateDelta,
_tokens: &HashMap<Bytes, Token>,
_balances: &Balances,
) -> Result<(), TransitionError> {
Err(TransitionError::DecodeError(
"BaiBai state is read whole every poll and does not take deltas".into(),
))
}
fn query_pool_swap(&self, params: &QueryPoolSwapParams) -> Result<PoolSwap, SimulationError> {
crate::evm::query_pool_swap::query_pool_swap(self, params)
}
fn clone_box(&self) -> Box<dyn ProtocolSim> {
Box::new(self.clone())
}
fn as_any(&self) -> &dyn Any {
self
}
fn as_any_mut(&mut self) -> &mut dyn Any {
self
}
fn eq(&self, other: &dyn ProtocolSim) -> bool {
other.as_any().downcast_ref::<Self>() == Some(self)
}
}
#[cfg(test)]
mod tests {
use rstest::rstest;
use super::*;
use crate::pamm::protocols::baibai::{
math::Knot,
test_support::{fee_charging_fixture, fixture, fixtures, state, token, weth_state},
BASE_DEPLOYMENT,
};
fn quote() -> Token {
token(BASE_DEPLOYMENT.quote)
}
#[test]
fn quotes_match_the_entrypoint_wei_for_wei() {
let mut priced = 0;
for fixture in fixtures() {
for pair in &fixture.pairs {
let state = state(&fixture, pair);
for case in &pair.cases {
let (token_in, token_out) = if case.sell_base {
(state.base_token.clone(), quote())
} else {
(quote(), state.base_token.clone())
};
let amount_in = u256_to_biguint(case.amount_in);
match state.get_amount_out(amount_in, &token_in, &token_out) {
Ok(result) => {
assert_eq!(result.amount, u256_to_biguint(case.amount_out), "{case:?}");
priced += 1;
}
Err(error) => {
assert_eq!(case.amount_out, U256::ZERO, "{case:?}: {error}")
}
}
}
}
}
assert_eq!(priced, 116, "the recordings' fillable cases");
}
#[test]
fn a_feeless_state_matches_the_curve_book() {
for fixture in fixtures() {
for pair in &fixture.pairs {
let mut state = state(&fixture, pair);
state.fee_pips = 0;
for case in pair
.cases
.iter()
.filter(|case| case.curve_out != U256::ZERO)
{
let (token_in, token_out) = if case.sell_base {
(state.base_token.clone(), quote())
} else {
(quote(), state.base_token.clone())
};
let result = state
.get_amount_out(u256_to_biguint(case.amount_in), &token_in, &token_out)
.unwrap();
assert_eq!(result.amount, u256_to_biguint(case.curve_out), "{case:?}");
}
}
}
}
#[test]
fn the_fee_is_in_millionths_of_the_output() {
let fixture = fee_charging_fixture();
assert_eq!(state(&fixture, &fixture.pairs[0]).fee(), 0.00005);
}
#[test]
fn the_router_pays_no_fee_since_its_whitelist() {
let state = weth_state();
let result = state
.get_amount_out(BigUint::from(10u64).pow(18), &state.base_token.clone(), "e())
.unwrap();
assert_eq!(state.fee(), 0.0);
assert_eq!(result.amount, BigUint::from(2_416_825_836u64));
}
#[test]
fn a_swap_advances_the_cursor_and_moves_custody() {
let state = weth_state();
let weth = state.base_token.clone();
let amount = BigUint::from(10u64).pow(17);
let result = state
.get_amount_out(amount.clone(), &weth, "e())
.unwrap();
let next = result
.new_state
.as_any()
.downcast_ref::<BaibaiState>()
.unwrap();
assert_eq!(next.bid.filled, U256::from(10u64).pow(U256::from(17)));
assert_eq!(next.ask.filled, state.ask.filled);
assert_eq!(
u256_to_biguint(next.available[0]),
u256_to_biguint(state.available[0]) + amount
);
assert_eq!(
u256_to_biguint(next.available[1]),
u256_to_biguint(state.available[1]) - &result.amount
);
let again = next
.get_amount_out(BigUint::from(10u64).pow(17), &weth, "e())
.unwrap();
assert!(again.amount <= result.amount);
}
#[rstest]
#[case::selling_within_the_first_segment(true, 2u64 * 10u64.pow(17), 115_400)]
#[case::selling_past_two_knots(true, 2u64 * 10u64.pow(18), 118_500)]
#[case::buying_within_the_first_segment(false, 500_000_000, 115_400)]
#[case::buying_past_one_knot(false, 1_000_000_000, 118_310)]
fn gas_grows_with_the_knots_a_swap_passes(
#[case] sell_base: bool,
#[case] amount: u64,
#[case] expected: u64,
) {
let state = weth_state();
let (token_in, token_out) = if sell_base {
(state.base_token.clone(), quote())
} else {
(quote(), state.base_token.clone())
};
let gas = state
.get_amount_out(BigUint::from(amount), &token_in, &token_out)
.unwrap()
.gas;
assert_eq!(gas, BigUint::from(expected));
}
#[rstest]
#[case::selling(true, 1_000_000, 115_400 + 17_100)]
#[case::buying(false, 500_000_000, 115_400 + 15_400)]
fn cbbtc_swaps_add_its_transfer_gas(
#[case] sell_base: bool,
#[case] amount: u64,
#[case] expected: u64,
) {
let fixture = fixture();
let state = state(&fixture, &fixture.pairs[1]);
assert_eq!(state.base_token.symbol, "cbBTC");
let (token_in, token_out) = if sell_base {
(state.base_token.clone(), quote())
} else {
(quote(), state.base_token.clone())
};
let gas = state
.get_amount_out(BigUint::from(amount), &token_in, &token_out)
.unwrap()
.gas;
assert_eq!(gas, BigUint::from(expected));
}
#[test]
fn knots_behind_the_cursor_still_cost_gas() {
let mut state = weth_state();
state.ask.filled = U256::from(5u64) * U256::from(10u64).pow(U256::from(17));
let gas = state
.get_amount_out(BigUint::from(1_000_000u64), "e(), &state.base_token.clone())
.unwrap()
.gas;
assert_eq!(gas, BigUint::from(115_400u64 + 1_550));
}
#[test]
fn a_bid_past_its_paying_depth_is_refused() {
let mut state = weth_state();
state.bid.knots = vec![Knot { q: 1_000, extra: 0 }, Knot { q: 2_000, extra: 46_000_000 }];
let weth = state.base_token.clone();
let (max_in, max_out) = state
.get_limits(weth.address.clone(), quote().address)
.unwrap();
let at_limit = state
.get_amount_out(max_in.clone(), &weth, "e())
.unwrap();
assert_eq!(at_limit.amount, max_out);
let error = state
.get_amount_out(max_in + 1u32, &weth, "e())
.unwrap_err();
assert!(
error
.to_string()
.contains("paying depth"),
"{error}"
);
}
#[rstest]
#[case::the_whole_output(1_000_000)]
#[case::more_than_the_output(1_000_001)]
fn a_fee_of_the_whole_output_trades_nothing(#[case] fee_pips: u32) {
let mut state = weth_state();
state.fee_pips = fee_pips;
let weth = state.base_token.clone();
let quoted = state
.get_amount_out(BigUint::from(10u64).pow(16), &weth, "e())
.unwrap_err();
let priced = state
.spot_price(&weth, "e())
.unwrap_err();
for error in [quoted, priced] {
assert!(
error
.to_string()
.contains("takes the whole output"),
"{error}"
);
}
assert!(state.directions().is_empty());
assert!(state.validated().is_err());
}
#[test]
fn output_beyond_custody_is_refused() {
let mut state = weth_state();
state.available[1] = U256::from(1_000_000);
let error = state
.get_amount_out(BigUint::from(10u64).pow(17), &state.base_token.clone(), "e())
.unwrap_err();
assert!(error.to_string().contains("available"), "{error}");
}
#[rstest]
#[case::zero_amount(0u64, true)]
#[case::unrelated_tokens(1_000u64, false)]
fn invalid_requests_are_refused(#[case] amount: u64, #[case] own_tokens: bool) {
let state = weth_state();
let token_in = if own_tokens {
state.base_token.clone()
} else {
token(alloy::primitives::Address::repeat_byte(0x11))
};
let error = state
.get_amount_out(BigUint::from(amount), &token_in, "e())
.unwrap_err();
assert!(matches!(error, SimulationError::InvalidInput(..)), "{error}");
}
#[rstest]
#[case::sell_base(true)]
#[case::buy_base(false)]
fn the_limits_are_fillable_and_tight(#[case] sell_base: bool) {
let state = weth_state();
let (token_in, token_out) = if sell_base {
(state.base_token.clone(), quote())
} else {
(quote(), state.base_token.clone())
};
let (max_in, max_out) = state
.get_limits(token_in.address.clone(), token_out.address.clone())
.unwrap();
let at_limit = state
.get_amount_out(max_in.clone(), &token_in, &token_out)
.unwrap();
assert_eq!(at_limit.amount, max_out);
assert!(state
.get_amount_out(max_in + 1u32, &token_in, &token_out)
.is_err());
}
fn bid_paying_depth(state: &BaibaiState) -> U256 {
let side = &state.bid;
let wad = U256::from(10u64).pow(U256::from(18));
let bps = U256::from(10_000u64);
let scale = U256::from(u64::try_from(10_000 + i64::from(side.spread_bps)).unwrap());
let price = state.mid * scale / bps;
let last_q = side
.knots
.last()
.map_or(U256::ZERO, |knot| U256::from(knot.q) * state.q_unit);
let depth = last_q * U256::from(side.depth_bps) / bps;
let mut reach = side.filled;
let (mut prev_q, mut prev_c) = (U256::ZERO, U256::ZERO);
for knot in &side.knots {
let q = U256::from(knot.q) * state.q_unit;
let c = U256::from(knot.extra) * state.c_unit;
if q > side.filled && reach < depth {
if price * (q - prev_q) <= (c - prev_c) * wad {
break;
}
reach = q.min(depth);
}
(prev_q, prev_c) = (q, c);
}
reach.saturating_sub(side.filled)
}
fn assert_tight_limits(
state: &BaibaiState,
direction: SwapDirection,
refusal: &str,
flat_allowed: bool,
context: &str,
) -> (BigUint, BigUint) {
let (token_in, token_out) = match direction {
SwapDirection::BaseToQuote => (state.base_token.clone(), quote()),
SwapDirection::QuoteToBase => (quote(), state.base_token.clone()),
};
let (max_in, max_out) = state
.get_limits(token_in.address.clone(), token_out.address.clone())
.unwrap();
if max_in == BigUint::ZERO {
return (max_in, max_out);
}
let at_limit = state
.get_amount_out(max_in.clone(), &token_in, &token_out)
.unwrap_or_else(|e| panic!("{context}: the limit {max_in} is refused: {e}"));
assert_eq!(at_limit.amount, max_out, "{context}");
match state.get_amount_out(max_in.clone() + 1u32, &token_in, &token_out) {
Err(error) => assert!(error.to_string().contains(refusal), "{context}: {error}"),
Ok(past) => assert!(
flat_allowed && past.amount == max_out,
"{context}: one atom past the limit {max_in} pays {}",
past.amount
),
}
(max_in, max_out)
}
#[rstest]
#[case::as_recorded(|_: &mut BaibaiState| {})]
#[case::with_a_fee(|s: &mut BaibaiState| s.fee_pips = 1_000)]
#[case::with_spreads(|s: &mut BaibaiState| {
s.ask.spread_bps = 25;
s.bid.spread_bps = -25;
})]
#[case::at_half_depth(|s: &mut BaibaiState| {
s.ask.depth_bps = 5_000;
s.bid.depth_bps = 5_000;
})]
fn the_limits_hold_on_every_recording(#[case] vary: fn(&mut BaibaiState)) {
let (mut curve_bound, mut custody_bound) = (0, 0);
for fixture in fixtures() {
for pair in &fixture.pairs {
let mut state = state(&fixture, pair);
vary(&mut state);
let state = state.validated().unwrap();
for (direction, beyond_curve) in [
(SwapDirection::BaseToQuote, "beyond the bid's paying depth"),
(SwapDirection::QuoteToBase, "beyond ask depth"),
] {
let context = format!("{direction:?} at block {}", fixture.block);
let (max_in, max_out) =
assert_tight_limits(&state, direction, beyond_curve, false, &context);
if direction == SwapDirection::BaseToQuote {
assert_eq!(biguint_to_u256(&max_in), bid_paying_depth(&state), "{context}");
}
if max_out < BigUint::from(2u32) {
continue;
}
curve_bound += 1;
let mut short = state.clone();
let available = biguint_to_u256(&max_out) / U256::from(2);
short.available[BaibaiState::custody(direction).1] = available;
let (short_in, short_out) = assert_tight_limits(
&short,
direction,
"exceeds the custodian's",
true,
&context,
);
assert!(short_out <= u256_to_biguint(available), "{context}");
assert!(short_in < max_in, "{context}");
custody_bound += 1;
}
}
}
assert!(curve_bound > 0, "no limit was bound by the curve");
assert!(custody_bound > 0, "no limit was bound by custody");
}
#[test]
fn an_empty_custody_trades_neither_way() {
let mut state = weth_state();
state.available = [U256::ZERO, U256::ZERO];
assert!(state.directions().is_empty());
let limits = state
.get_limits(state.base_token.address.clone(), quote().address)
.unwrap();
assert_eq!(limits, (BigUint::ZERO, BigUint::ZERO));
assert!(state
.spot_price(&state.base_token.clone(), "e())
.is_err());
}
#[test]
fn spot_prices_bracket_the_mid() {
let state = weth_state();
let weth = state.base_token.clone();
let mid = 2_417.07;
let bid = state
.spot_price(&weth, "e())
.unwrap();
let ask = 1.0 /
state
.spot_price("e(), &weth)
.unwrap();
assert!(bid < ask, "bid {bid} ask {ask}");
assert!((bid - mid).abs() / mid < 0.01, "bid {bid}");
assert!((ask - mid).abs() / mid < 0.01, "ask {ask}");
}
#[rstest]
#[case::fee_takes_everything(|s: &mut BaibaiState| s.fee_pips = 1_000_000)]
#[case::no_mid(|s: &mut BaibaiState| s.mid = U256::ZERO)]
#[case::too_many_knots(|s: &mut BaibaiState| s.ask.knots = (1..=37).map(|i| Knot { q: i, extra: i }).collect())]
#[case::falling_cost(|s: &mut BaibaiState| s.bid.knots = vec![Knot { q: 1, extra: 5 }, Knot { q: 2, extra: 4 }])]
#[case::repeated_quantity(|s: &mut BaibaiState| s.bid.knots = vec![Knot { q: 1, extra: 0 }, Knot { q: 1, extra: 1 }])]
#[case::depth_over_100_percent(|s: &mut BaibaiState| s.ask.depth_bps = 10_001)]
#[case::spread_of_minus_100_percent(|s: &mut BaibaiState| s.bid.spread_bps = -10_000)]
#[case::spread_below_minus_100_percent(|s: &mut BaibaiState| s.ask.spread_bps = i16::MIN)]
fn malformed_states_are_rejected(#[case] corrupt: fn(&mut BaibaiState)) {
let mut state = weth_state();
corrupt(&mut state);
assert!(state.validated().is_err());
}
#[test]
fn a_state_round_trips_through_serde() {
let state: Box<dyn ProtocolSim> = Box::new(weth_state());
let json = serde_json::to_string(&state).unwrap();
let back: Box<dyn ProtocolSim> = serde_json::from_str(&json).unwrap();
assert!(back.eq(state.as_ref()));
}
}